LLVM API Documentation
00001 //===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements the SelectionDAGISel class. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #define DEBUG_TYPE "isel" 00015 #include "ScheduleDAGSDNodes.h" 00016 #include "SelectionDAGBuild.h" 00017 #include "llvm/CodeGen/SelectionDAGISel.h" 00018 #include "llvm/Analysis/AliasAnalysis.h" 00019 #include "llvm/Constants.h" 00020 #include "llvm/CallingConv.h" 00021 #include "llvm/DerivedTypes.h" 00022 #include "llvm/Function.h" 00023 #include "llvm/GlobalVariable.h" 00024 #include "llvm/InlineAsm.h" 00025 #include "llvm/Instructions.h" 00026 #include "llvm/Intrinsics.h" 00027 #include "llvm/IntrinsicInst.h" 00028 #include "llvm/CodeGen/FastISel.h" 00029 #include "llvm/CodeGen/GCStrategy.h" 00030 #include "llvm/CodeGen/GCMetadata.h" 00031 #include "llvm/CodeGen/MachineFunction.h" 00032 #include "llvm/CodeGen/MachineFunctionAnalysis.h" 00033 #include "llvm/CodeGen/MachineFrameInfo.h" 00034 #include "llvm/CodeGen/MachineInstrBuilder.h" 00035 #include "llvm/CodeGen/MachineJumpTableInfo.h" 00036 #include "llvm/CodeGen/MachineModuleInfo.h" 00037 #include "llvm/CodeGen/MachineRegisterInfo.h" 00038 #include "llvm/CodeGen/ScheduleHazardRecognizer.h" 00039 #include "llvm/CodeGen/SchedulerRegistry.h" 00040 #include "llvm/CodeGen/SelectionDAG.h" 00041 #include "llvm/CodeGen/DwarfWriter.h" 00042 #include "llvm/Target/TargetRegisterInfo.h" 00043 #include "llvm/Target/TargetData.h" 00044 #include "llvm/Target/TargetFrameInfo.h" 00045 #include "llvm/Target/TargetInstrInfo.h" 00046 #include "llvm/Target/TargetLowering.h" 00047 #include "llvm/Target/TargetMachine.h" 00048 #include "llvm/Target/TargetOptions.h" 00049 #include "llvm/Support/Compiler.h" 00050 #include "llvm/Support/Debug.h" 00051 #include "llvm/Support/ErrorHandling.h" 00052 #include "llvm/Support/MathExtras.h" 00053 #include "llvm/Support/Timer.h" 00054 #include "llvm/Support/raw_ostream.h" 00055 #include <algorithm> 00056 using namespace llvm; 00057 00058 static cl::opt<bool> 00059 DisableLegalizeTypes("disable-legalize-types", cl::Hidden); 00060 static cl::opt<bool> 00061 EnableFastISelVerbose("fast-isel-verbose", cl::Hidden, 00062 cl::desc("Enable verbose messages in the \"fast\" " 00063 "instruction selector")); 00064 static cl::opt<bool> 00065 EnableFastISelAbort("fast-isel-abort", cl::Hidden, 00066 cl::desc("Enable abort calls when \"fast\" instruction fails")); 00067 static cl::opt<bool> 00068 SchedLiveInCopies("schedule-livein-copies", 00069 cl::desc("Schedule copies of livein registers"), 00070 cl::init(false)); 00071 00072 #ifndef NDEBUG 00073 static cl::opt<bool> 00074 ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden, 00075 cl::desc("Pop up a window to show dags before the first " 00076 "dag combine pass")); 00077 static cl::opt<bool> 00078 ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden, 00079 cl::desc("Pop up a window to show dags before legalize types")); 00080 static cl::opt<bool> 00081 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden, 00082 cl::desc("Pop up a window to show dags before legalize")); 00083 static cl::opt<bool> 00084 ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden, 00085 cl::desc("Pop up a window to show dags before the second " 00086 "dag combine pass")); 00087 static cl::opt<bool> 00088 ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden, 00089 cl::desc("Pop up a window to show dags before the post legalize types" 00090 " dag combine pass")); 00091 static cl::opt<bool> 00092 ViewISelDAGs("view-isel-dags", cl::Hidden, 00093 cl::desc("Pop up a window to show isel dags as they are selected")); 00094 static cl::opt<bool> 00095 ViewSchedDAGs("view-sched-dags", cl::Hidden, 00096 cl::desc("Pop up a window to show sched dags as they are processed")); 00097 static cl::opt<bool> 00098 ViewSUnitDAGs("view-sunit-dags", cl::Hidden, 00099 cl::desc("Pop up a window to show SUnit dags after they are processed")); 00100 #else 00101 static const bool ViewDAGCombine1 = false, 00102 ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false, 00103 ViewDAGCombine2 = false, 00104 ViewDAGCombineLT = false, 00105 ViewISelDAGs = false, ViewSchedDAGs = false, 00106 ViewSUnitDAGs = false; 00107 #endif 00108 00109 //===---------------------------------------------------------------------===// 00110 /// 00111 /// RegisterScheduler class - Track the registration of instruction schedulers. 00112 /// 00113 //===---------------------------------------------------------------------===// 00114 MachinePassRegistry RegisterScheduler::Registry; 00115 00116 //===---------------------------------------------------------------------===// 00117 /// 00118 /// ISHeuristic command line option for instruction schedulers. 00119 /// 00120 //===---------------------------------------------------------------------===// 00121 static cl::opt<RegisterScheduler::FunctionPassCtor, false, 00122 RegisterPassParser<RegisterScheduler> > 00123 ISHeuristic("pre-RA-sched", 00124 cl::init(&createDefaultScheduler), 00125 cl::desc("Instruction schedulers available (before register" 00126 " allocation):")); 00127 00128 static RegisterScheduler 00129 defaultListDAGScheduler("default", "Best scheduler for the target", 00130 createDefaultScheduler); 00131 00132 namespace llvm { 00133 //===--------------------------------------------------------------------===// 00134 /// createDefaultScheduler - This creates an instruction scheduler appropriate 00135 /// for the target. 00136 ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS, 00137 CodeGenOpt::Level OptLevel) { 00138 const TargetLowering &TLI = IS->getTargetLowering(); 00139 00140 if (OptLevel == CodeGenOpt::None) 00141 return createFastDAGScheduler(IS, OptLevel); 00142 if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) 00143 return createTDListDAGScheduler(IS, OptLevel); 00144 assert(TLI.getSchedulingPreference() == 00145 TargetLowering::SchedulingForRegPressure && "Unknown sched type!"); 00146 return createBURRListDAGScheduler(IS, OptLevel); 00147 } 00148 } 00149 00150 // EmitInstrWithCustomInserter - This method should be implemented by targets 00151 // that mark instructions with the 'usesCustomDAGSchedInserter' flag. These 00152 // instructions are special in various ways, which require special support to 00153 // insert. The specified MachineInstr is created but not inserted into any 00154 // basic blocks, and the scheduler passes ownership of it to this method. 00155 MachineBasicBlock *TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI, 00156 MachineBasicBlock *MBB) const { 00157 #ifndef NDEBUG 00158 cerr << "If a target marks an instruction with " 00159 "'usesCustomDAGSchedInserter', it must implement " 00160 "TargetLowering::EmitInstrWithCustomInserter!"; 00161 #endif 00162 llvm_unreachable(0); 00163 return 0; 00164 } 00165 00166 /// EmitLiveInCopy - Emit a copy for a live in physical register. If the 00167 /// physical register has only a single copy use, then coalesced the copy 00168 /// if possible. 00169 static void EmitLiveInCopy(MachineBasicBlock *MBB, 00170 MachineBasicBlock::iterator &InsertPos, 00171 unsigned VirtReg, unsigned PhysReg, 00172 const TargetRegisterClass *RC, 00173 DenseMap<MachineInstr*, unsigned> &CopyRegMap, 00174 const MachineRegisterInfo &MRI, 00175 const TargetRegisterInfo &TRI, 00176 const TargetInstrInfo &TII) { 00177 unsigned NumUses = 0; 00178 MachineInstr *UseMI = NULL; 00179 for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(VirtReg), 00180 UE = MRI.use_end(); UI != UE; ++UI) { 00181 UseMI = &*UI; 00182 if (++NumUses > 1) 00183 break; 00184 } 00185 00186 // If the number of uses is not one, or the use is not a move instruction, 00187 // don't coalesce. Also, only coalesce away a virtual register to virtual 00188 // register copy. 00189 bool Coalesced = false; 00190 unsigned SrcReg, DstReg, SrcSubReg, DstSubReg; 00191 if (NumUses == 1 && 00192 TII.isMoveInstr(*UseMI, SrcReg, DstReg, SrcSubReg, DstSubReg) && 00193 TargetRegisterInfo::isVirtualRegister(DstReg)) { 00194 VirtReg = DstReg; 00195 Coalesced = true; 00196 } 00197 00198 // Now find an ideal location to insert the copy. 00199 MachineBasicBlock::iterator Pos = InsertPos; 00200 while (Pos != MBB->begin()) { 00201 MachineInstr *PrevMI = prior(Pos); 00202 DenseMap<MachineInstr*, unsigned>::iterator RI = CopyRegMap.find(PrevMI); 00203 // copyRegToReg might emit multiple instructions to do a copy. 00204 unsigned CopyDstReg = (RI == CopyRegMap.end()) ? 0 : RI->second; 00205 if (CopyDstReg && !TRI.regsOverlap(CopyDstReg, PhysReg)) 00206 // This is what the BB looks like right now: 00207 // r1024 = mov r0 00208 // ... 00209 // r1 = mov r1024 00210 // 00211 // We want to insert "r1025 = mov r1". Inserting this copy below the 00212 // move to r1024 makes it impossible for that move to be coalesced. 00213 // 00214 // r1025 = mov r1 00215 // r1024 = mov r0 00216 // ... 00217 // r1 = mov 1024 00218 // r2 = mov 1025 00219 break; // Woot! Found a good location. 00220 --Pos; 00221 } 00222 00223 bool Emitted = TII.copyRegToReg(*MBB, Pos, VirtReg, PhysReg, RC, RC); 00224 assert(Emitted && "Unable to issue a live-in copy instruction!\n"); 00225 (void) Emitted; 00226 00227 CopyRegMap.insert(std::make_pair(prior(Pos), VirtReg)); 00228 if (Coalesced) { 00229 if (&*InsertPos == UseMI) ++InsertPos; 00230 MBB->erase(UseMI); 00231 } 00232 } 00233 00234 /// EmitLiveInCopies - If this is the first basic block in the function, 00235 /// and if it has live ins that need to be copied into vregs, emit the 00236 /// copies into the block. 00237 static void EmitLiveInCopies(MachineBasicBlock *EntryMBB, 00238 const MachineRegisterInfo &MRI, 00239 const TargetRegisterInfo &TRI, 00240 const TargetInstrInfo &TII) { 00241 if (SchedLiveInCopies) { 00242 // Emit the copies at a heuristically-determined location in the block. 00243 DenseMap<MachineInstr*, unsigned> CopyRegMap; 00244 MachineBasicBlock::iterator InsertPos = EntryMBB->begin(); 00245 for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(), 00246 E = MRI.livein_end(); LI != E; ++LI) 00247 if (LI->second) { 00248 const TargetRegisterClass *RC = MRI.getRegClass(LI->second); 00249 EmitLiveInCopy(EntryMBB, InsertPos, LI->second, LI->first, 00250 RC, CopyRegMap, MRI, TRI, TII); 00251 } 00252 } else { 00253 // Emit the copies into the top of the block. 00254 for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(), 00255 E = MRI.livein_end(); LI != E; ++LI) 00256 if (LI->second) { 00257 const TargetRegisterClass *RC = MRI.getRegClass(LI->second); 00258 bool Emitted = TII.copyRegToReg(*EntryMBB, EntryMBB->begin(), 00259 LI->second, LI->first, RC, RC); 00260 assert(Emitted && "Unable to issue a live-in copy instruction!\n"); 00261 (void) Emitted; 00262 } 00263 } 00264 } 00265 00266 //===----------------------------------------------------------------------===// 00267 // SelectionDAGISel code 00268 //===----------------------------------------------------------------------===// 00269 00270 SelectionDAGISel::SelectionDAGISel(TargetMachine &tm, CodeGenOpt::Level OL) : 00271 MachineFunctionPass(&ID), TM(tm), TLI(*tm.getTargetLowering()), 00272 FuncInfo(new FunctionLoweringInfo(TLI)), 00273 CurDAG(new SelectionDAG(TLI, *FuncInfo)), 00274 SDL(new SelectionDAGLowering(*CurDAG, TLI, *FuncInfo, OL)), 00275 GFI(), 00276 OptLevel(OL), 00277 DAGSize(0) 00278 {} 00279 00280 SelectionDAGISel::~SelectionDAGISel() { 00281 delete SDL; 00282 delete CurDAG; 00283 delete FuncInfo; 00284 } 00285 00286 unsigned SelectionDAGISel::MakeReg(EVT VT) { 00287 return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT)); 00288 } 00289 00290 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { 00291 AU.addRequired<AliasAnalysis>(); 00292 AU.addPreserved<AliasAnalysis>(); 00293 AU.addRequired<GCModuleInfo>(); 00294 AU.addPreserved<GCModuleInfo>(); 00295 AU.addRequired<DwarfWriter>(); 00296 AU.addPreserved<DwarfWriter>(); 00297 MachineFunctionPass::getAnalysisUsage(AU); 00298 } 00299 00300 bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) { 00301 Function &Fn = *mf.getFunction(); 00302 00303 // Do some sanity-checking on the command-line options. 00304 assert((!EnableFastISelVerbose || EnableFastISel) && 00305 "-fast-isel-verbose requires -fast-isel"); 00306 assert((!EnableFastISelAbort || EnableFastISel) && 00307 "-fast-isel-abort requires -fast-isel"); 00308 00309 // Get alias analysis for load/store combining. 00310 AA = &getAnalysis<AliasAnalysis>(); 00311 00312 MF = &mf; 00313 const TargetInstrInfo &TII = *TM.getInstrInfo(); 00314 const TargetRegisterInfo &TRI = *TM.getRegisterInfo(); 00315 00316 if (Fn.hasGC()) 00317 GFI = &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn); 00318 else 00319 GFI = 0; 00320 RegInfo = &MF->getRegInfo(); 00321 DEBUG(errs() << "\n\n\n=== " << Fn.getName() << "\n"); 00322 00323 MachineModuleInfo *MMI = getAnalysisIfAvailable<MachineModuleInfo>(); 00324 DwarfWriter *DW = getAnalysisIfAvailable<DwarfWriter>(); 00325 CurDAG->init(*MF, MMI, DW); 00326 FuncInfo->set(Fn, *MF, *CurDAG, EnableFastISel); 00327 SDL->init(GFI, *AA); 00328 00329 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 00330 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator())) 00331 // Mark landing pad. 00332 FuncInfo->MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad(); 00333 00334 SelectAllBasicBlocks(Fn, *MF, MMI, DW, TII); 00335 00336 // If the first basic block in the function has live ins that need to be 00337 // copied into vregs, emit the copies into the top of the block before 00338 // emitting the code for the block. 00339 EmitLiveInCopies(MF->begin(), *RegInfo, TRI, TII); 00340 00341 // Add function live-ins to entry block live-in set. 00342 for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(), 00343 E = RegInfo->livein_end(); I != E; ++I) 00344 MF->begin()->addLiveIn(I->first); 00345 00346 #ifndef NDEBUG 00347 assert(FuncInfo->CatchInfoFound.size() == FuncInfo->CatchInfoLost.size() && 00348 "Not all catch info was assigned to a landing pad!"); 00349 #endif 00350 00351 FuncInfo->clear(); 00352 00353 return true; 00354 } 00355 00356 static void copyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB, 00357 MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) { 00358 for (BasicBlock::iterator I = SrcBB->begin(), E = --SrcBB->end(); I != E; ++I) 00359 if (EHSelectorInst *EHSel = dyn_cast<EHSelectorInst>(I)) { 00360 // Apply the catch info to DestBB. 00361 AddCatchInfo(*EHSel, MMI, FLI.MBBMap[DestBB]); 00362 #ifndef NDEBUG 00363 if (!FLI.MBBMap[SrcBB]->isLandingPad()) 00364 FLI.CatchInfoFound.insert(EHSel); 00365 #endif 00366 } 00367 } 00368 00369 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, 00370 BasicBlock::iterator Begin, 00371 BasicBlock::iterator End) { 00372 SDL->setCurrentBasicBlock(BB); 00373 00374 // Lower all of the non-terminator instructions. If a call is emitted 00375 // as a tail call, cease emitting nodes for this block. 00376 for (BasicBlock::iterator I = Begin; I != End && !SDL->HasTailCall; ++I) 00377 if (!isa<TerminatorInst>(I)) 00378 SDL->visit(*I); 00379 00380 if (!SDL->HasTailCall) { 00381 // Ensure that all instructions which are used outside of their defining 00382 // blocks are available as virtual registers. Invoke is handled elsewhere. 00383 for (BasicBlock::iterator I = Begin; I != End; ++I) 00384 if (!isa<PHINode>(I) && !isa<InvokeInst>(I)) 00385 SDL->CopyToExportRegsIfNeeded(I); 00386 00387 // Handle PHI nodes in successor blocks. 00388 if (End == LLVMBB->end()) { 00389 HandlePHINodesInSuccessorBlocks(LLVMBB); 00390 00391 // Lower the terminator after the copies are emitted. 00392 SDL->visit(*LLVMBB->getTerminator()); 00393 } 00394 } 00395 00396 // Make sure the root of the DAG is up-to-date. 00397 CurDAG->setRoot(SDL->getControlRoot()); 00398 00399 // Final step, emit the lowered DAG as machine code. 00400 CodeGenAndEmitDAG(); 00401 SDL->clear(); 00402 } 00403 00404 void SelectionDAGISel::ComputeLiveOutVRegInfo() { 00405 SmallPtrSet<SDNode*, 128> VisitedNodes; 00406 SmallVector<SDNode*, 128> Worklist; 00407 00408 Worklist.push_back(CurDAG->getRoot().getNode()); 00409 00410 APInt Mask; 00411 APInt KnownZero; 00412 APInt KnownOne; 00413 00414 while (!Worklist.empty()) { 00415 SDNode *N = Worklist.back(); 00416 Worklist.pop_back(); 00417 00418 // If we've already seen this node, ignore it. 00419 if (!VisitedNodes.insert(N)) 00420 continue; 00421 00422 // Otherwise, add all chain operands to the worklist. 00423 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 00424 if (N->getOperand(i).getValueType() == MVT::Other) 00425 Worklist.push_back(N->getOperand(i).getNode()); 00426 00427 // If this is a CopyToReg with a vreg dest, process it. 00428 if (N->getOpcode() != ISD::CopyToReg) 00429 continue; 00430 00431 unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg(); 00432 if (!TargetRegisterInfo::isVirtualRegister(DestReg)) 00433 continue; 00434 00435 // Ignore non-scalar or non-integer values. 00436 SDValue Src = N->getOperand(2); 00437 EVT SrcVT = Src.getValueType(); 00438 if (!SrcVT.isInteger() || SrcVT.isVector()) 00439 continue; 00440 00441 unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src); 00442 Mask = APInt::getAllOnesValue(SrcVT.getSizeInBits()); 00443 CurDAG->ComputeMaskedBits(Src, Mask, KnownZero, KnownOne); 00444 00445 // Only install this information if it tells us something. 00446 if (NumSignBits != 1 || KnownZero != 0 || KnownOne != 0) { 00447 DestReg -= TargetRegisterInfo::FirstVirtualRegister; 00448 if (DestReg >= FuncInfo->LiveOutRegInfo.size()) 00449 FuncInfo->LiveOutRegInfo.resize(DestReg+1); 00450 FunctionLoweringInfo::LiveOutInfo &LOI = 00451 FuncInfo->LiveOutRegInfo[DestReg]; 00452 LOI.NumSignBits = NumSignBits; 00453 LOI.KnownOne = KnownOne; 00454 LOI.KnownZero = KnownZero; 00455 } 00456 } 00457 } 00458 00459 void SelectionDAGISel::CodeGenAndEmitDAG() { 00460 std::string GroupName; 00461 if (TimePassesIsEnabled) 00462 GroupName = "Instruction Selection and Scheduling"; 00463 std::string BlockName; 00464 if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs || 00465 ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs || 00466 ViewSUnitDAGs) 00467 BlockName = MF->getFunction()->getNameStr() + ":" + 00468 BB->getBasicBlock()->getNameStr(); 00469 00470 DOUT << "Initial selection DAG:\n"; 00471 DEBUG(CurDAG->dump()); 00472 00473 if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName); 00474 00475 // Run the DAG combiner in pre-legalize mode. 00476 if (TimePassesIsEnabled) { 00477 NamedRegionTimer T("DAG Combining 1", GroupName); 00478 CurDAG->Combine(Unrestricted, *AA, OptLevel); 00479 } else { 00480 CurDAG->Combine(Unrestricted, *AA, OptLevel); 00481 } 00482 00483 DOUT << "Optimized lowered selection DAG:\n"; 00484 DEBUG(CurDAG->dump()); 00485 00486 // Second step, hack on the DAG until it only uses operations and types that 00487 // the target supports. 00488 if (!DisableLegalizeTypes) { 00489 if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " + 00490 BlockName); 00491 00492 bool Changed; 00493 if (TimePassesIsEnabled) { 00494 NamedRegionTimer T("Type Legalization", GroupName); 00495 Changed = CurDAG->LegalizeTypes(); 00496 } else { 00497 Changed = CurDAG->LegalizeTypes(); 00498 } 00499 00500 DOUT << "Type-legalized selection DAG:\n"; 00501 DEBUG(CurDAG->dump()); 00502 00503 if (Changed) { 00504 if (ViewDAGCombineLT) 00505 CurDAG->viewGraph("dag-combine-lt input for " + BlockName); 00506 00507 // Run the DAG combiner in post-type-legalize mode. 00508 if (TimePassesIsEnabled) { 00509 NamedRegionTimer T("DAG Combining after legalize types", GroupName); 00510 CurDAG->Combine(NoIllegalTypes, *AA, OptLevel); 00511 } else { 00512 CurDAG->Combine(NoIllegalTypes, *AA, OptLevel); 00513 } 00514 00515 DOUT << "Optimized type-legalized selection DAG:\n"; 00516 DEBUG(CurDAG->dump()); 00517 } 00518 00519 if (TimePassesIsEnabled) { 00520 NamedRegionTimer T("Vector Legalization", GroupName); 00521 Changed = CurDAG->LegalizeVectors(); 00522 } else { 00523 Changed = CurDAG->LegalizeVectors(); 00524 } 00525 00526 if (Changed) { 00527 if (TimePassesIsEnabled) { 00528 NamedRegionTimer T("Type Legalization 2", GroupName); 00529 Changed = CurDAG->LegalizeTypes(); 00530 } else { 00531 Changed = CurDAG->LegalizeTypes(); 00532 } 00533 00534 if (ViewDAGCombineLT) 00535 CurDAG->viewGraph("dag-combine-lv input for " + BlockName); 00536 00537 // Run the DAG combiner in post-type-legalize mode. 00538 if (TimePassesIsEnabled) { 00539 NamedRegionTimer T("DAG Combining after legalize vectors", GroupName); 00540 CurDAG->Combine(NoIllegalOperations, *AA, OptLevel); 00541 } else { 00542 CurDAG->Combine(NoIllegalOperations, *AA, OptLevel); 00543 } 00544 00545 DOUT << "Optimized vector-legalized selection DAG:\n"; 00546 DEBUG(CurDAG->dump()); 00547 } 00548 } 00549 00550 if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName); 00551 00552 if (TimePassesIsEnabled) { 00553 NamedRegionTimer T("DAG Legalization", GroupName); 00554 CurDAG->Legalize(DisableLegalizeTypes, OptLevel); 00555 } else { 00556 CurDAG->Legalize(DisableLegalizeTypes, OptLevel); 00557 } 00558 00559 DOUT << "Legalized selection DAG:\n"; 00560 DEBUG(CurDAG->dump()); 00561 00562 if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName); 00563 00564 // Run the DAG combiner in post-legalize mode. 00565 if (TimePassesIsEnabled) { 00566 NamedRegionTimer T("DAG Combining 2", GroupName); 00567 CurDAG->Combine(NoIllegalOperations, *AA, OptLevel); 00568 } else { 00569 CurDAG->Combine(NoIllegalOperations, *AA, OptLevel); 00570 } 00571 00572 DOUT << "Optimized legalized selection DAG:\n"; 00573 DEBUG(CurDAG->dump()); 00574 00575 if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName); 00576 00577 if (OptLevel != CodeGenOpt::None) 00578 ComputeLiveOutVRegInfo(); 00579 00580 // Third, instruction select all of the operations to machine code, adding the 00581 // code to the MachineBasicBlock. 00582 if (TimePassesIsEnabled) { 00583 NamedRegionTimer T("Instruction Selection", GroupName); 00584 InstructionSelect(); 00585 } else { 00586 InstructionSelect(); 00587 } 00588 00589 DOUT << "Selected selection DAG:\n"; 00590 DEBUG(CurDAG->dump()); 00591 00592 if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName); 00593 00594 // Schedule machine code. 00595 ScheduleDAGSDNodes *Scheduler = CreateScheduler(); 00596 if (TimePassesIsEnabled) { 00597 NamedRegionTimer T("Instruction Scheduling", GroupName); 00598 Scheduler->Run(CurDAG, BB, BB->end()); 00599 } else { 00600 Scheduler->Run(CurDAG, BB, BB->end()); 00601 } 00602 00603 if (ViewSUnitDAGs) Scheduler->viewGraph(); 00604 00605 // Emit machine code to BB. This can change 'BB' to the last block being 00606 // inserted into. 00607 if (TimePassesIsEnabled) { 00608 NamedRegionTimer T("Instruction Creation", GroupName); 00609 BB = Scheduler->EmitSchedule(); 00610 } else { 00611 BB = Scheduler->EmitSchedule(); 00612 } 00613 00614 // Free the scheduler state. 00615 if (TimePassesIsEnabled) { 00616 NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName); 00617 delete Scheduler; 00618 } else { 00619 delete Scheduler; 00620 } 00621 00622 DOUT << "Selected machine code:\n"; 00623 DEBUG(BB->dump()); 00624 } 00625 00626 void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, 00627 MachineFunction &MF, 00628 MachineModuleInfo *MMI, 00629 DwarfWriter *DW, 00630 const TargetInstrInfo &TII) { 00631 // Initialize the Fast-ISel state, if needed. 00632 FastISel *FastIS = 0; 00633 if (EnableFastISel) 00634 FastIS = TLI.createFastISel(MF, MMI, DW, 00635 FuncInfo->ValueMap, 00636 FuncInfo->MBBMap, 00637 FuncInfo->StaticAllocaMap 00638 #ifndef NDEBUG 00639 , FuncInfo->CatchInfoLost 00640 #endif 00641 ); 00642 00643 // Iterate over all basic blocks in the function. 00644 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) { 00645 BasicBlock *LLVMBB = &*I; 00646 BB = FuncInfo->MBBMap[LLVMBB]; 00647 00648 BasicBlock::iterator const Begin = LLVMBB->begin(); 00649 BasicBlock::iterator const End = LLVMBB->end(); 00650 BasicBlock::iterator BI = Begin; 00651 00652 // Lower any arguments needed in this block if this is the entry block. 00653 bool SuppressFastISel = false; 00654 if (LLVMBB == &Fn.getEntryBlock()) { 00655 LowerArguments(LLVMBB); 00656 00657 // If any of the arguments has the byval attribute, forgo 00658 // fast-isel in the entry block. 00659 if (FastIS) { 00660 unsigned j = 1; 00661 for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end(); 00662 I != E; ++I, ++j) 00663 if (Fn.paramHasAttr(j, Attribute::ByVal)) { 00664 if (EnableFastISelVerbose || EnableFastISelAbort) 00665 cerr << "FastISel skips entry block due to byval argument\n"; 00666 SuppressFastISel = true; 00667 break; 00668 } 00669 } 00670 } 00671 00672 if (MMI && BB->isLandingPad()) { 00673 // Add a label to mark the beginning of the landing pad. Deletion of the 00674 // landing pad can thus be detected via the MachineModuleInfo. 00675 unsigned LabelID = MMI->addLandingPad(BB); 00676 00677 const TargetInstrDesc &II = TII.get(TargetInstrInfo::EH_LABEL); 00678 BuildMI(BB, SDL->getCurDebugLoc(), II).addImm(LabelID); 00679 00680 // Mark exception register as live in. 00681 unsigned Reg = TLI.getExceptionAddressRegister(); 00682 if (Reg) BB->addLiveIn(Reg); 00683 00684 // Mark exception selector register as live in. 00685 Reg = TLI.getExceptionSelectorRegister(); 00686 if (Reg) BB->addLiveIn(Reg); 00687 00688 // FIXME: Hack around an exception handling flaw (PR1508): the personality 00689 // function and list of typeids logically belong to the invoke (or, if you 00690 // like, the basic block containing the invoke), and need to be associated 00691 // with it in the dwarf exception handling tables. Currently however the 00692 // information is provided by an intrinsic (eh.selector) that can be moved 00693 // to unexpected places by the optimizers: if the unwind edge is critical, 00694 // then breaking it can result in the intrinsics being in the successor of 00695 // the landing pad, not the landing pad itself. This results in exceptions 00696 // not being caught because no typeids are associated with the invoke. 00697 // This may not be the only way things can go wrong, but it is the only way 00698 // we try to work around for the moment. 00699 BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator()); 00700 00701 if (Br && Br->isUnconditional()) { // Critical edge? 00702 BasicBlock::iterator I, E; 00703 for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I) 00704 if (isa<EHSelectorInst>(I)) 00705 break; 00706 00707 if (I == E) 00708 // No catch info found - try to extract some from the successor. 00709 copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, *FuncInfo); 00710 } 00711 } 00712 00713 // Before doing SelectionDAG ISel, see if FastISel has been requested. 00714 if (FastIS && !SuppressFastISel) { 00715 // Emit code for any incoming arguments. This must happen before 00716 // beginning FastISel on the entry block. 00717 if (LLVMBB == &Fn.getEntryBlock()) { 00718 CurDAG->setRoot(SDL->getControlRoot()); 00719 CodeGenAndEmitDAG(); 00720 SDL->clear(); 00721 } 00722 FastIS->startNewBlock(BB); 00723 // Do FastISel on as many instructions as possible. 00724 for (; BI != End; ++BI) { 00725 // Just before the terminator instruction, insert instructions to 00726 // feed PHI nodes in successor blocks. 00727 if (isa<TerminatorInst>(BI)) 00728 if (!HandlePHINodesInSuccessorBlocksFast(LLVMBB, FastIS)) { 00729 if (EnableFastISelVerbose || EnableFastISelAbort) { 00730 cerr << "FastISel miss: "; 00731 BI->dump(); 00732 } 00733 assert(!EnableFastISelAbort && 00734 "FastISel didn't handle a PHI in a successor"); 00735 break; 00736 } 00737 00738 // First try normal tablegen-generated "fast" selection. 00739 if (FastIS->SelectInstruction(BI)) 00740 continue; 00741 00742 // Next, try calling the target to attempt to handle the instruction. 00743 if (FastIS->TargetSelectInstruction(BI)) 00744 continue; 00745 00746 // Then handle certain instructions as single-LLVM-Instruction blocks. 00747 if (isa<CallInst>(BI)) { 00748 if (EnableFastISelVerbose || EnableFastISelAbort) { 00749 cerr << "FastISel missed call: "; 00750 BI->dump(); 00751 } 00752 00753 if (BI->getType() != Type::getVoidTy(*CurDAG->getContext())) { 00754 unsigned &R = FuncInfo->ValueMap[BI]; 00755 if (!R) 00756 R = FuncInfo->CreateRegForValue(BI); 00757 } 00758 00759 SDL->setCurDebugLoc(FastIS->getCurDebugLoc()); 00760 SelectBasicBlock(LLVMBB, BI, next(BI)); 00761 // If the instruction was codegen'd with multiple blocks, 00762 // inform the FastISel object where to resume inserting. 00763 FastIS->setCurrentBlock(BB); 00764 continue; 00765 } 00766 00767 // Otherwise, give up on FastISel for the rest of the block. 00768 // For now, be a little lenient about non-branch terminators. 00769 if (!isa<TerminatorInst>(BI) || isa<BranchInst>(BI)) { 00770 if (EnableFastISelVerbose || EnableFastISelAbort) { 00771 cerr << "FastISel miss: "; 00772 BI->dump(); 00773 } 00774 if (EnableFastISelAbort) 00775 // The "fast" selector couldn't handle something and bailed. 00776 // For the purpose of debugging, just abort. 00777 llvm_unreachable("FastISel didn't select the entire block"); 00778 } 00779 break; 00780 } 00781 } 00782 00783 // Run SelectionDAG instruction selection on the remainder of the block 00784 // not handled by FastISel. If FastISel is not run, this is the entire 00785 // block. 00786 if (BI != End) { 00787 // If FastISel is run and it has known DebugLoc then use it. 00788 if (FastIS && !FastIS->getCurDebugLoc().isUnknown()) 00789 SDL->setCurDebugLoc(FastIS->getCurDebugLoc()); 00790 SelectBasicBlock(LLVMBB, BI, End); 00791 } 00792 00793 FinishBasicBlock(); 00794 } 00795 00796 delete FastIS; 00797 } 00798 00799 void 00800 SelectionDAGISel::FinishBasicBlock() { 00801 00802 DOUT << "Target-post-processed machine code:\n"; 00803 DEBUG(BB->dump()); 00804 00805 DOUT << "Total amount of phi nodes to update: " 00806 << SDL->PHINodesToUpdate.size() << "\n"; 00807 DEBUG(for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) 00808 DOUT << "Node " << i << " : (" << SDL->PHINodesToUpdate[i].first 00809 << ", " << SDL->PHINodesToUpdate[i].second << ")\n";); 00810 00811 // Next, now that we know what the last MBB the LLVM BB expanded is, update 00812 // PHI nodes in successors. 00813 if (SDL->SwitchCases.empty() && 00814 SDL->JTCases.empty() && 00815 SDL->BitTestCases.empty()) { 00816 for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) { 00817 MachineInstr *PHI = SDL->PHINodesToUpdate[i].first; 00818 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 00819 "This is not a machine PHI node that we are updating!"); 00820 PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[i].second, 00821 false)); 00822 PHI->addOperand(MachineOperand::CreateMBB(BB)); 00823 } 00824 SDL->PHINodesToUpdate.clear(); 00825 return; 00826 } 00827 00828 for (unsigned i = 0, e = SDL->BitTestCases.size(); i != e; ++i) { 00829 // Lower header first, if it wasn't already lowered 00830 if (!SDL->BitTestCases[i].Emitted) { 00831 // Set the current basic block to the mbb we wish to insert the code into 00832 BB = SDL->BitTestCases[i].Parent; 00833 SDL->setCurrentBasicBlock(BB); 00834 // Emit the code 00835 SDL->visitBitTestHeader(SDL->BitTestCases[i]); 00836 CurDAG->setRoot(SDL->getRoot()); 00837 CodeGenAndEmitDAG(); 00838 SDL->clear(); 00839 } 00840 00841 for (unsigned j = 0, ej = SDL->BitTestCases[i].Cases.size(); j != ej; ++j) { 00842 // Set the current basic block to the mbb we wish to insert the code into 00843 BB = SDL->BitTestCases[i].Cases[j].ThisBB; 00844 SDL->setCurrentBasicBlock(BB); 00845 // Emit the code 00846 if (j+1 != ej) 00847 SDL->visitBitTestCase(SDL->BitTestCases[i].Cases[j+1].ThisBB, 00848 SDL->BitTestCases[i].Reg, 00849 SDL->BitTestCases[i].Cases[j]); 00850 else 00851 SDL->visitBitTestCase(SDL->BitTestCases[i].Default, 00852 SDL->BitTestCases[i].Reg, 00853 SDL->BitTestCases[i].Cases[j]); 00854 00855 00856 CurDAG->setRoot(SDL->getRoot()); 00857 CodeGenAndEmitDAG(); 00858 SDL->clear(); 00859 } 00860 00861 // Update PHI Nodes 00862 for (unsigned pi = 0, pe = SDL->PHINodesToUpdate.size(); pi != pe; ++pi) { 00863 MachineInstr *PHI = SDL->PHINodesToUpdate[pi].first; 00864 MachineBasicBlock *PHIBB = PHI->getParent(); 00865 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 00866 "This is not a machine PHI node that we are updating!"); 00867 // This is "default" BB. We have two jumps to it. From "header" BB and 00868 // from last "case" BB. 00869 if (PHIBB == SDL->BitTestCases[i].Default) { 00870 PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 00871 false)); 00872 PHI->addOperand(MachineOperand::CreateMBB(SDL->BitTestCases[i].Parent)); 00873 PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 00874 false)); 00875 PHI->addOperand(MachineOperand::CreateMBB(SDL->BitTestCases[i].Cases. 00876 back().ThisBB)); 00877 } 00878 // One of "cases" BB. 00879 for (unsigned j = 0, ej = SDL->BitTestCases[i].Cases.size(); 00880 j != ej; ++j) { 00881 MachineBasicBlock* cBB = SDL->BitTestCases[i].Cases[j].ThisBB; 00882 if (cBB->succ_end() != 00883 std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) { 00884 PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 00885 false)); 00886 PHI->addOperand(MachineOperand::CreateMBB(cBB)); 00887 } 00888 } 00889 } 00890 } 00891 SDL->BitTestCases.clear(); 00892 00893 // If the JumpTable record is filled in, then we need to emit a jump table. 00894 // Updating the PHI nodes is tricky in this case, since we need to determine 00895 // whether the PHI is a successor of the range check MBB or the jump table MBB 00896 for (unsigned i = 0, e = SDL->JTCases.size(); i != e; ++i) { 00897 // Lower header first, if it wasn't already lowered 00898 if (!SDL->JTCases[i].first.Emitted) { 00899 // Set the current basic block to the mbb we wish to insert the code into 00900 BB = SDL->JTCases[i].first.HeaderBB; 00901 SDL->setCurrentBasicBlock(BB); 00902 // Emit the code 00903 SDL->visitJumpTableHeader(SDL->JTCases[i].second, SDL->JTCases[i].first); 00904 CurDAG->setRoot(SDL->getRoot()); 00905 CodeGenAndEmitDAG(); 00906 SDL->clear(); 00907 } 00908 00909 // Set the current basic block to the mbb we wish to insert the code into 00910 BB = SDL->JTCases[i].second.MBB; 00911 SDL->setCurrentBasicBlock(BB); 00912 // Emit the code 00913 SDL->visitJumpTable(SDL->JTCases[i].second); 00914 CurDAG->setRoot(SDL->getRoot()); 00915 CodeGenAndEmitDAG(); 00916 SDL->clear(); 00917 00918 // Update PHI Nodes 00919 for (unsigned pi = 0, pe = SDL->PHINodesToUpdate.size(); pi != pe; ++pi) { 00920 MachineInstr *PHI = SDL->PHINodesToUpdate[pi].first; 00921 MachineBasicBlock *PHIBB = PHI->getParent(); 00922 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 00923 "This is not a machine PHI node that we are updating!"); 00924 // "default" BB. We can go there only from header BB. 00925 if (PHIBB == SDL->JTCases[i].second.Default) { 00926 PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 00927 false)); 00928 PHI->addOperand(MachineOperand::CreateMBB(SDL->JTCases[i].first.HeaderBB)); 00929 } 00930 // JT BB. Just iterate over successors here 00931 if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) { 00932 PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second, 00933 false)); 00934 PHI->addOperand(MachineOperand::CreateMBB(BB)); 00935 } 00936 } 00937 } 00938 SDL->JTCases.clear(); 00939 00940 // If the switch block involved a branch to one of the actual successors, we 00941 // need to update PHI nodes in that block. 00942 for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) { 00943 MachineInstr *PHI = SDL->PHINodesToUpdate[i].first; 00944 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 00945 "This is not a machine PHI node that we are updating!"); 00946 if (BB->isSuccessor(PHI->getParent())) { 00947 PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[i].second, 00948 false)); 00949 PHI->addOperand(MachineOperand::CreateMBB(BB)); 00950 } 00951 } 00952 00953 // If we generated any switch lowering information, build and codegen any 00954 // additional DAGs necessary. 00955 for (unsigned i = 0, e = SDL->SwitchCases.size(); i != e; ++i) { 00956 // Set the current basic block to the mbb we wish to insert the code into 00957 BB = SDL->SwitchCases[i].ThisBB; 00958 SDL->setCurrentBasicBlock(BB); 00959 00960 // Emit the code 00961 SDL->visitSwitchCase(SDL->SwitchCases[i]); 00962 CurDAG->setRoot(SDL->getRoot()); 00963 CodeGenAndEmitDAG(); 00964 SDL->clear(); 00965 00966 // Handle any PHI nodes in successors of this chunk, as if we were coming 00967 // from the original BB before switch expansion. Note that PHI nodes can 00968 // occur multiple times in PHINodesToUpdate. We have to be very careful to 00969 // handle them the right number of times. 00970 while ((BB = SDL->SwitchCases[i].TrueBB)) { // Handle LHS and RHS. 00971 for (MachineBasicBlock::iterator Phi = BB->begin(); 00972 Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){ 00973 // This value for this PHI node is recorded in PHINodesToUpdate, get it. 00974 for (unsigned pn = 0; ; ++pn) { 00975 assert(pn != SDL->PHINodesToUpdate.size() && 00976 "Didn't find PHI entry!"); 00977 if (SDL->PHINodesToUpdate[pn].first == Phi) { 00978 Phi->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pn]. 00979 second, false)); 00980 Phi->addOperand(MachineOperand::CreateMBB(SDL->SwitchCases[i].ThisBB)); 00981 break; 00982 } 00983 } 00984 } 00985 00986 // Don't process RHS if same block as LHS. 00987 if (BB == SDL->SwitchCases[i].FalseBB) 00988 SDL->SwitchCases[i].FalseBB = 0; 00989 00990 // If we haven't handled the RHS, do so now. Otherwise, we're done. 00991 SDL->SwitchCases[i].TrueBB = SDL->SwitchCases[i].FalseBB; 00992 SDL->SwitchCases[i].FalseBB = 0; 00993 } 00994 assert(SDL->SwitchCases[i].TrueBB == 0 && SDL->SwitchCases[i].FalseBB == 0); 00995 } 00996 SDL->SwitchCases.clear(); 00997 00998 SDL->PHINodesToUpdate.clear(); 00999 } 01000 01001 01002 /// Create the scheduler. If a specific scheduler was specified 01003 /// via the SchedulerRegistry, use it, otherwise select the 01004 /// one preferred by the target. 01005 /// 01006 ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() { 01007 RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault(); 01008 01009 if (!Ctor) { 01010 Ctor = ISHeuristic; 01011 RegisterScheduler::setDefault(Ctor); 01012 } 01013 01014 return Ctor(this, OptLevel); 01015 } 01016 01017 ScheduleHazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() { 01018 return new ScheduleHazardRecognizer(); 01019 } 01020 01021 //===----------------------------------------------------------------------===// 01022 // Helper functions used by the generated instruction selector. 01023 //===----------------------------------------------------------------------===// 01024 // Calls to these methods are generated by tblgen. 01025 01026 /// CheckAndMask - The isel is trying to match something like (and X, 255). If 01027 /// the dag combiner simplified the 255, we still want to match. RHS is the 01028 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value 01029 /// specified in the .td file (e.g. 255). 01030 bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS, 01031 int64_t DesiredMaskS) const { 01032 const APInt &ActualMask = RHS->getAPIntValue(); 01033 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 01034 01035 // If the actual mask exactly matches, success! 01036 if (ActualMask == DesiredMask) 01037 return true; 01038 01039 // If the actual AND mask is allowing unallowed bits, this doesn't match. 01040 if (ActualMask.intersects(~DesiredMask)) 01041 return false; 01042 01043 // Otherwise, the DAG Combiner may have proven that the value coming in is 01044 // either already zero or is not demanded. Check for known zero input bits. 01045 APInt NeededMask = DesiredMask & ~ActualMask; 01046 if (CurDAG->MaskedValueIsZero(LHS, NeededMask)) 01047 return true; 01048 01049 // TODO: check to see if missing bits are just not demanded. 01050 01051 // Otherwise, this pattern doesn't match. 01052 return false; 01053 } 01054 01055 /// CheckOrMask - The isel is trying to match something like (or X, 255). If 01056 /// the dag combiner simplified the 255, we still want to match. RHS is the 01057 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value 01058 /// specified in the .td file (e.g. 255). 01059 bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS, 01060 int64_t DesiredMaskS) const { 01061 const APInt &ActualMask = RHS->getAPIntValue(); 01062 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 01063 01064 // If the actual mask exactly matches, success! 01065 if (ActualMask == DesiredMask) 01066 return true; 01067 01068 // If the actual AND mask is allowing unallowed bits, this doesn't match. 01069 if (ActualMask.intersects(~DesiredMask)) 01070 return false; 01071 01072 // Otherwise, the DAG Combiner may have proven that the value coming in is 01073 // either already zero or is not demanded. Check for known zero input bits. 01074 APInt NeededMask = DesiredMask & ~ActualMask; 01075 01076 APInt KnownZero, KnownOne; 01077 CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne); 01078 01079 // If all the missing bits in the or are already known to be set, match! 01080 if ((NeededMask & KnownOne) == NeededMask) 01081 return true; 01082 01083 // TODO: check to see if missing bits are just not demanded. 01084 01085 // Otherwise, this pattern doesn't match. 01086 return false; 01087 } 01088 01089 01090 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated 01091 /// by tblgen. Others should not call it. 01092 void SelectionDAGISel:: 01093 SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops) { 01094 std::vector<SDValue> InOps; 01095 std::swap(InOps, Ops); 01096 01097 Ops.push_back(InOps[0]); // input chain. 01098 Ops.push_back(InOps[1]); // input asm string. 01099 01100 unsigned i = 2, e = InOps.size(); 01101 if (InOps[e-1].getValueType() == MVT::Flag) 01102 --e; // Don't process a flag operand if it is here. 01103 01104 while (i != e) { 01105 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue(); 01106 if ((Flags & 7) != 4 /*MEM*/) { 01107 // Just skip over this operand, copying the operands verbatim. 01108 Ops.insert(Ops.end(), InOps.begin()+i, 01109 InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1); 01110 i += InlineAsm::getNumOperandRegisters(Flags) + 1; 01111 } else { 01112 assert(InlineAsm::getNumOperandRegisters(Flags) == 1 && 01113 "Memory operand with multiple values?"); 01114 // Otherwise, this is a memory operand. Ask the target to select it. 01115 std::vector<SDValue> SelOps; 01116 if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps)) { 01117 llvm_report_error("Could not match memory address. Inline asm" 01118 " failure!"); 01119 } 01120 01121 // Add this to the output node. 01122 EVT IntPtrTy = TLI.getPointerTy(); 01123 Ops.push_back(CurDAG->getTargetConstant(4/*MEM*/ | (SelOps.size()<< 3), 01124 IntPtrTy)); 01125 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end()); 01126 i += 2; 01127 } 01128 } 01129 01130 // Add the flag input back if present. 01131 if (e != InOps.size()) 01132 Ops.push_back(InOps.back()); 01133 } 01134 01135 /// findFlagUse - Return use of EVT::Flag value produced by the specified 01136 /// SDNode. 01137 /// 01138 static SDNode *findFlagUse(SDNode *N) { 01139 unsigned FlagResNo = N->getNumValues()-1; 01140 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { 01141 SDUse &Use = I.getUse(); 01142 if (Use.getResNo() == FlagResNo) 01143 return Use.getUser(); 01144 } 01145 return NULL; 01146 } 01147 01148 /// findNonImmUse - Return true if "Use" is a non-immediate use of "Def". 01149 /// This function recursively traverses up the operand chain, ignoring 01150 /// certain nodes. 01151 static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse, 01152 SDNode *Root, 01153 SmallPtrSet<SDNode*, 16> &Visited) { 01154 if (Use->getNodeId() < Def->getNodeId() || 01155 !Visited.insert(Use)) 01156 return false; 01157 01158 for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) { 01159 SDNode *N = Use->getOperand(i).getNode(); 01160 if (N == Def) { 01161 if (Use == ImmedUse || Use == Root) 01162 continue; // We are not looking for immediate use. 01163 assert(N != Root); 01164 return true; 01165 } 01166 01167 // Traverse up the operand chain. 01168 if (findNonImmUse(N, Def, ImmedUse, Root, Visited)) 01169 return true; 01170 } 01171 return false; 01172 } 01173 01174 /// isNonImmUse - Start searching from Root up the DAG to check is Def can 01175 /// be reached. Return true if that's the case. However, ignore direct uses 01176 /// by ImmedUse (which would be U in the example illustrated in 01177 /// IsLegalAndProfitableToFold) and by Root (which can happen in the store 01178 /// case). 01179 /// FIXME: to be really generic, we should allow direct use by any node 01180 /// that is being folded. But realisticly since we only fold loads which 01181 /// have one non-chain use, we only need to watch out for load/op/store 01182 /// and load/op/cmp case where the root (store / cmp) may reach the load via 01183 /// its chain operand. 01184 static inline bool isNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse) { 01185 SmallPtrSet<SDNode*, 16> Visited; 01186 return findNonImmUse(Root, Def, ImmedUse, Root, Visited); 01187 } 01188 01189 /// IsLegalAndProfitableToFold - Returns true if the specific operand node N of 01190 /// U can be folded during instruction selection that starts at Root and 01191 /// folding N is profitable. 01192 bool SelectionDAGISel::IsLegalAndProfitableToFold(SDNode *N, SDNode *U, 01193 SDNode *Root) const { 01194 if (OptLevel == CodeGenOpt::None) return false; 01195 01196 // If Root use can somehow reach N through a path that that doesn't contain 01197 // U then folding N would create a cycle. e.g. In the following 01198 // diagram, Root can reach N through X. If N is folded into into Root, then 01199 // X is both a predecessor and a successor of U. 01200 // 01201 // [N*] // 01202 // ^ ^ // 01203 // / \ // 01204 // [U*] [X]? // 01205 // ^ ^ // 01206 // \ / // 01207 // \ / // 01208 // [Root*] // 01209 // 01210 // * indicates nodes to be folded together. 01211 // 01212 // If Root produces a flag, then it gets (even more) interesting. Since it 01213 // will be "glued" together with its flag use in the scheduler, we need to 01214 // check if it might reach N. 01215 // 01216 // [N*] // 01217 // ^ ^ // 01218 // / \ // 01219 // [U*] [X]? // 01220 // ^ ^ // 01221 // \ \ // 01222 // \ | // 01223 // [Root*] | // 01224 // ^ | // 01225 // f | // 01226 // | / // 01227 // [Y] / // 01228 // ^ / // 01229 // f / // 01230 // | / // 01231 // [FU] // 01232 // 01233 // If FU (flag use) indirectly reaches N (the load), and Root folds N 01234 // (call it Fold), then X is a predecessor of FU and a successor of 01235 // Fold. But since Fold and FU are flagged together, this will create 01236 // a cycle in the scheduling graph. 01237 01238 EVT VT = Root->getValueType(Root->getNumValues()-1); 01239 while (VT == MVT::Flag) { 01240 SDNode *FU = findFlagUse(Root); 01241 if (FU == NULL) 01242 break; 01243 Root = FU; 01244 VT = Root->getValueType(Root->getNumValues()-1); 01245 } 01246 01247 return !isNonImmUse(Root, N, U); 01248 } 01249 01250 01251 char SelectionDAGISel::ID = 0;