LLVM API Documentation

SelectionDAGISel.cpp

Go to the documentation of this file.
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;