lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

   1 //===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements the SelectionDAGISel class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "isel"
  15 #include "llvm/CodeGen/SelectionDAGISel.h"
  16 #include "SelectionDAGBuild.h"
  17 #include "llvm/Analysis/AliasAnalysis.h"
  18 #include "llvm/Constants.h"
  19 #include "llvm/CallingConv.h"
  20 #include "llvm/DerivedTypes.h"
  21 #include "llvm/Function.h"
  22 #include "llvm/GlobalVariable.h"
  23 #include "llvm/InlineAsm.h"
  24 #include "llvm/Instructions.h"
  25 #include "llvm/Intrinsics.h"
  26 #include "llvm/IntrinsicInst.h"
  27 #include "llvm/CodeGen/FastISel.h"
  28 #include "llvm/CodeGen/GCStrategy.h"
  29 #include "llvm/CodeGen/GCMetadata.h"
  30 #include "llvm/CodeGen/MachineFunction.h"
  31 #include "llvm/CodeGen/MachineFrameInfo.h"
  32 #include "llvm/CodeGen/MachineInstrBuilder.h"
  33 #include "llvm/CodeGen/MachineJumpTableInfo.h"
  34 #include "llvm/CodeGen/MachineModuleInfo.h"
  35 #include "llvm/CodeGen/MachineRegisterInfo.h"
  36 #include "llvm/CodeGen/ScheduleDAGSDNodes.h"
  37 #include "llvm/CodeGen/SchedulerRegistry.h"
  38 #include "llvm/CodeGen/SelectionDAG.h"
  39 #include "llvm/Target/TargetRegisterInfo.h"
  40 #include "llvm/Target/TargetData.h"
  41 #include "llvm/Target/TargetFrameInfo.h"
  42 #include "llvm/Target/TargetInstrInfo.h"
  43 #include "llvm/Target/TargetLowering.h"
  44 #include "llvm/Target/TargetMachine.h"
  45 #include "llvm/Target/TargetOptions.h"
  46 #include "llvm/Support/Compiler.h"
  47 #include "llvm/Support/Debug.h"
  48 #include "llvm/Support/MathExtras.h"
  49 #include "llvm/Support/Timer.h"
  50 #include <algorithm>
  51 using namespace llvm;
  52
  53 static cl::opt<bool>
  54 EnableValueProp("enable-value-prop", cl::Hidden);
  55 static cl::opt<bool>
  56 DisableLegalizeTypes("disable-legalize-types", cl::Hidden);
  57 #ifndef NDEBUG
  58 static cl::opt<bool>
  59 EnableFastISelVerbose("fast-isel-verbose", cl::Hidden,
  60           cl::desc("Enable verbose messages in the \"fast\" "
  61                    "instruction selector"));
  62 static cl::opt<bool>
  63 EnableFastISelAbort("fast-isel-abort", cl::Hidden,
  64           cl::desc("Enable abort calls when \"fast\" instruction fails"));
  65 #else
  66 static const bool EnableFastISelVerbose = false,
  67                   EnableFastISelAbort = false;
  68 #endif
  69 static cl::opt<bool>
  70 SchedLiveInCopies("schedule-livein-copies",
  71                   cl::desc("Schedule copies of livein registers"),
  72                   cl::init(false));
  73
  74 #ifndef NDEBUG
  75 static cl::opt<bool>
  76 ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
  77           cl::desc("Pop up a window to show dags before the first "
  78                    "dag combine pass"));
  79 static cl::opt<bool>
  80 ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
  81           cl::desc("Pop up a window to show dags before legalize types"));
  82 static cl::opt<bool>
  83 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
  84           cl::desc("Pop up a window to show dags before legalize"));
  85 static cl::opt<bool>
  86 ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
  87           cl::desc("Pop up a window to show dags before the second "
  88                    "dag combine pass"));
  89 static cl::opt<bool>
  90 ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,
  91           cl::desc("Pop up a window to show dags before the post legalize types"
  92                    " dag combine pass"));
  93 static cl::opt<bool>
  94 ViewISelDAGs("view-isel-dags", cl::Hidden,
  95           cl::desc("Pop up a window to show isel dags as they are selected"));
  96 static cl::opt<bool>
  97 ViewSchedDAGs("view-sched-dags", cl::Hidden,
  98           cl::desc("Pop up a window to show sched dags as they are processed"));
  99 static cl::opt<bool>
 100 ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
 101       cl::desc("Pop up a window to show SUnit dags after they are processed"));
 102 #else
 103 static const bool ViewDAGCombine1 = false,
 104                   ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false,
 105                   ViewDAGCombine2 = false,
 106                   ViewDAGCombineLT = false,
 107                   ViewISelDAGs = false, ViewSchedDAGs = false,
 108                   ViewSUnitDAGs = false;
 109 #endif
 110
 111 //===---------------------------------------------------------------------===//
 112 ///
 113 /// RegisterScheduler class - Track the registration of instruction schedulers.
 114 ///
 115 //===---------------------------------------------------------------------===//
 116 MachinePassRegistry RegisterScheduler::Registry;
 117
 118 //===---------------------------------------------------------------------===//
 119 ///
 120 /// ISHeuristic command line option for instruction schedulers.
 121 ///
 122 //===---------------------------------------------------------------------===//
 123 static cl::opt<RegisterScheduler::FunctionPassCtor, false,
 124                RegisterPassParser<RegisterScheduler> >
 125 ISHeuristic("pre-RA-sched",
 126             cl::init(&createDefaultScheduler),
 127             cl::desc("Instruction schedulers available (before register"
 128                      " allocation):"));
 129
 130 static RegisterScheduler
 131 defaultListDAGScheduler("default", "Best scheduler for the target",
 132                         createDefaultScheduler);
 133
 134 namespace llvm {
 135   //===--------------------------------------------------------------------===//
 136   /// createDefaultScheduler - This creates an instruction scheduler appropriate
 137   /// for the target.
 138   ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS,
 139                                       SelectionDAG *DAG,
 140                                       const TargetMachine *TM,
 141                                       MachineBasicBlock *BB,
 142                                       bool Fast) {
 143     TargetLowering &TLI = IS->getTargetLowering();
 144
 145     if (Fast)
 146       return createFastDAGScheduler(IS, DAG, TM, BB, Fast);
 147     if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency)
 148       return createTDListDAGScheduler(IS, DAG, TM, BB, Fast);
 149     assert(TLI.getSchedulingPreference() ==
 150          TargetLowering::SchedulingForRegPressure && "Unknown sched type!");
 151     return createBURRListDAGScheduler(IS, DAG, TM, BB, Fast);
 152   }
 153 }
 154
 155 // EmitInstrWithCustomInserter - This method should be implemented by targets
 156 // that mark instructions with the 'usesCustomDAGSchedInserter' flag.  These
 157 // instructions are special in various ways, which require special support to
 158 // insert.  The specified MachineInstr is created but not inserted into any
 159 // basic blocks, and the scheduler passes ownership of it to this method.
 160 MachineBasicBlock *TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI,
 161                                                        MachineBasicBlock *MBB) {
 162   cerr << "If a target marks an instruction with "
 163        << "'usesCustomDAGSchedInserter', it must implement "
 164        << "TargetLowering::EmitInstrWithCustomInserter!\n";
 165   abort();
 166   return 0;
 167 }
 168
 169 /// EmitLiveInCopy - Emit a copy for a live in physical register. If the
 170 /// physical register has only a single copy use, then coalesced the copy
 171 /// if possible.
 172 static void EmitLiveInCopy(MachineBasicBlock *MBB,
 173                            MachineBasicBlock::iterator &InsertPos,
 174                            unsigned VirtReg, unsigned PhysReg,
 175                            const TargetRegisterClass *RC,
 176                            DenseMap<MachineInstr*, unsigned> &CopyRegMap,
 177                            const MachineRegisterInfo &MRI,
 178                            const TargetRegisterInfo &TRI,
 179                            const TargetInstrInfo &TII) {
 180   unsigned NumUses = 0;
 181   MachineInstr *UseMI = NULL;
 182   for (MachineRegisterInfo::use_iterator UI = MRI.use_begin(VirtReg),
 183          UE = MRI.use_end(); UI != UE; ++UI) {
 184     UseMI = &*UI;
 185     if (++NumUses > 1)
 186       break;
 187   }
 188
 189   // If the number of uses is not one, or the use is not a move instruction,
 190   // don't coalesce. Also, only coalesce away a virtual register to virtual
 191   // register copy.
 192   bool Coalesced = false;
 193   unsigned SrcReg, DstReg;
 194   if (NumUses == 1 &&
 195       TII.isMoveInstr(*UseMI, SrcReg, DstReg) &&
 196       TargetRegisterInfo::isVirtualRegister(DstReg)) {
 197     VirtReg = DstReg;
 198     Coalesced = true;
 199   }
 200
 201   // Now find an ideal location to insert the copy.
 202   MachineBasicBlock::iterator Pos = InsertPos;
 203   while (Pos != MBB->begin()) {
 204     MachineInstr *PrevMI = prior(Pos);
 205     DenseMap<MachineInstr*, unsigned>::iterator RI = CopyRegMap.find(PrevMI);
 206     // copyRegToReg might emit multiple instructions to do a copy.
 207     unsigned CopyDstReg = (RI == CopyRegMap.end()) ? 0 : RI->second;
 208     if (CopyDstReg && !TRI.regsOverlap(CopyDstReg, PhysReg))
 209       // This is what the BB looks like right now:
 210       // r1024 = mov r0
 211       // ...
 212       // r1    = mov r1024
 213       //
 214       // We want to insert "r1025 = mov r1". Inserting this copy below the
 215       // move to r1024 makes it impossible for that move to be coalesced.
 216       //
 217       // r1025 = mov r1
 218       // r1024 = mov r0
 219       // ...
 220       // r1    = mov 1024
 221       // r2    = mov 1025
 222       break; // Woot! Found a good location.
 223     --Pos;
 224   }
 225
 226   TII.copyRegToReg(*MBB, Pos, VirtReg, PhysReg, RC, RC);
 227   CopyRegMap.insert(std::make_pair(prior(Pos), VirtReg));
 228   if (Coalesced) {
 229     if (&*InsertPos == UseMI) ++InsertPos;
 230     MBB->erase(UseMI);
 231   }
 232 }
 233
 234 /// EmitLiveInCopies - If this is the first basic block in the function,
 235 /// and if it has live ins that need to be copied into vregs, emit the
 236 /// copies into the block.
 237 static void EmitLiveInCopies(MachineBasicBlock *EntryMBB,
 238                              const MachineRegisterInfo &MRI,
 239                              const TargetRegisterInfo &TRI,
 240                              const TargetInstrInfo &TII) {
 241   if (SchedLiveInCopies) {
 242     // Emit the copies at a heuristically-determined location in the block.
 243     DenseMap<MachineInstr*, unsigned> CopyRegMap;
 244     MachineBasicBlock::iterator InsertPos = EntryMBB->begin();
 245     for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(),
 246            E = MRI.livein_end(); LI != E; ++LI)
 247       if (LI->second) {
 248         const TargetRegisterClass *RC = MRI.getRegClass(LI->second);
 249         EmitLiveInCopy(EntryMBB, InsertPos, LI->second, LI->first,
 250                        RC, CopyRegMap, MRI, TRI, TII);
 251       }
 252   } else {
 253     // Emit the copies into the top of the block.
 254     for (MachineRegisterInfo::livein_iterator LI = MRI.livein_begin(),
 255            E = MRI.livein_end(); LI != E; ++LI)
 256       if (LI->second) {
 257         const TargetRegisterClass *RC = MRI.getRegClass(LI->second);
 258         TII.copyRegToReg(*EntryMBB, EntryMBB->begin(),
 259                          LI->second, LI->first, RC, RC);
 260       }
 261   }
 262 }
 263
 264 //===----------------------------------------------------------------------===//
 265 // SelectionDAGISel code
 266 //===----------------------------------------------------------------------===//
 267
 268 SelectionDAGISel::SelectionDAGISel(TargetLowering &tli, bool fast) :
 269   FunctionPass(&ID), TLI(tli),
 270   FuncInfo(new FunctionLoweringInfo(TLI)),
 271   CurDAG(new SelectionDAG(TLI, *FuncInfo)),
 272   SDL(new SelectionDAGLowering(*CurDAG, TLI, *FuncInfo)),
 273   GFI(),
 274   Fast(fast),
 275   DAGSize(0)
 276 {}
 277
 278 SelectionDAGISel::~SelectionDAGISel() {
 279   delete SDL;
 280   delete CurDAG;
 281   delete FuncInfo;
 282 }
 283
 284 unsigned SelectionDAGISel::MakeReg(MVT VT) {
 285   return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT));
 286 }
 287
 288 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
 289   AU.addRequired<AliasAnalysis>();
 290   AU.addRequired<GCModuleInfo>();
 291   AU.setPreservesAll();
 292 }
 293
 294 bool SelectionDAGISel::runOnFunction(Function &Fn) {
 295   // Do some sanity-checking on the command-line options.
 296   assert((!EnableFastISelVerbose || EnableFastISel) &&
 297          "-fast-isel-verbose requires -fast-isel");
 298   assert((!EnableFastISelAbort || EnableFastISel) &&
 299          "-fast-isel-abort requires -fast-isel");
 300
 301   // Get alias analysis for load/store combining.
 302   AA = &getAnalysis<AliasAnalysis>();
 303
 304   TargetMachine &TM = TLI.getTargetMachine();
 305   MachineFunction &MF = MachineFunction::construct(&Fn, TM);
 306   const MachineRegisterInfo &MRI = MF.getRegInfo();
 307   const TargetInstrInfo &TII = *TM.getInstrInfo();
 308   const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
 309
 310   if (MF.getFunction()->hasGC())
 311     GFI = &getAnalysis<GCModuleInfo>().getFunctionInfo(*MF.getFunction());
 312   else
 313     GFI = 0;
 314   RegInfo = &MF.getRegInfo();
 315   DOUT << "\n\n\n=== " << Fn.getName() << "\n";
 316
 317   FuncInfo->set(Fn, MF, EnableFastISel);
 318   MachineModuleInfo *MMI = getAnalysisToUpdate<MachineModuleInfo>();
 319   CurDAG->init(MF, MMI);
 320   SDL->init(GFI, *AA);
 321
 322   for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I)
 323     if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator()))
 324       // Mark landing pad.
 325       FuncInfo->MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad();
 326
 327   SelectAllBasicBlocks(Fn, MF, MMI, TII);
 328
 329   // If the first basic block in the function has live ins that need to be
 330   // copied into vregs, emit the copies into the top of the block before
 331   // emitting the code for the block.
 332   EmitLiveInCopies(MF.begin(), MRI, TRI, TII);
 333
 334   // Add function live-ins to entry block live-in set.
 335   for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(),
 336          E = RegInfo->livein_end(); I != E; ++I)
 337     MF.begin()->addLiveIn(I->first);
 338
 339 #ifndef NDEBUG
 340   assert(FuncInfo->CatchInfoFound.size() == FuncInfo->CatchInfoLost.size() &&
 341          "Not all catch info was assigned to a landing pad!");
 342 #endif
 343
 344   FuncInfo->clear();
 345
 346   return true;
 347 }
 348
 349 static void copyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB,
 350                           MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) {
 351   for (BasicBlock::iterator I = SrcBB->begin(), E = --SrcBB->end(); I != E; ++I)
 352     if (EHSelectorInst *EHSel = dyn_cast<EHSelectorInst>(I)) {
 353       // Apply the catch info to DestBB.
 354       AddCatchInfo(*EHSel, MMI, FLI.MBBMap[DestBB]);
 355 #ifndef NDEBUG
 356       if (!FLI.MBBMap[SrcBB]->isLandingPad())
 357         FLI.CatchInfoFound.insert(EHSel);
 358 #endif
 359     }
 360 }
 361
 362 /// IsFixedFrameObjectWithPosOffset - Check if object is a fixed frame object and
 363 /// whether object offset >= 0.
 364 static bool
 365 IsFixedFrameObjectWithPosOffset(MachineFrameInfo * MFI, SDValue Op) {
 366   if (!isa<FrameIndexSDNode>(Op)) return false;
 367
 368   FrameIndexSDNode * FrameIdxNode = dyn_cast<FrameIndexSDNode>(Op);
 369   int FrameIdx =  FrameIdxNode->getIndex();
 370   return MFI->isFixedObjectIndex(FrameIdx) &&
 371     MFI->getObjectOffset(FrameIdx) >= 0;
 372 }
 373
 374 /// IsPossiblyOverwrittenArgumentOfTailCall - Check if the operand could
 375 /// possibly be overwritten when lowering the outgoing arguments in a tail
 376 /// call. Currently the implementation of this call is very conservative and
 377 /// assumes all arguments sourcing from FORMAL_ARGUMENTS or a CopyFromReg with
 378 /// virtual registers would be overwritten by direct lowering.
 379 static bool IsPossiblyOverwrittenArgumentOfTailCall(SDValue Op,
 380                                                     MachineFrameInfo * MFI) {
 381   RegisterSDNode * OpReg = NULL;
 382   if (Op.getOpcode() == ISD::FORMAL_ARGUMENTS ||
 383       (Op.getOpcode()== ISD::CopyFromReg &&
 384        (OpReg = dyn_cast<RegisterSDNode>(Op.getOperand(1))) &&
 385        (OpReg->getReg() >= TargetRegisterInfo::FirstVirtualRegister)) ||
 386       (Op.getOpcode() == ISD::LOAD &&
 387        IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(1))) ||
 388       (Op.getOpcode() == ISD::MERGE_VALUES &&
 389        Op.getOperand(Op.getResNo()).getOpcode() == ISD::LOAD &&
 390        IsFixedFrameObjectWithPosOffset(MFI, Op.getOperand(Op.getResNo()).
 391                                        getOperand(1))))
 392     return true;
 393   return false;
 394 }
 395
 396 /// CheckDAGForTailCallsAndFixThem - This Function looks for CALL nodes in the
 397 /// DAG and fixes their tailcall attribute operand.
 398 static void CheckDAGForTailCallsAndFixThem(SelectionDAG &DAG,
 399                                            TargetLowering& TLI) {
 400   SDNode * Ret = NULL;
 401   SDValue Terminator = DAG.getRoot();
 402
 403   // Find RET node.
 404   if (Terminator.getOpcode() == ISD::RET) {
 405     Ret = Terminator.getNode();
 406   }
 407
 408   // Fix tail call attribute of CALL nodes.
 409   for (SelectionDAG::allnodes_iterator BE = DAG.allnodes_begin(),
 410          BI = DAG.allnodes_end(); BI != BE; ) {
 411     --BI;
 412     if (CallSDNode *TheCall = dyn_cast<CallSDNode>(BI)) {
 413       SDValue OpRet(Ret, 0);
 414       SDValue OpCall(BI, 0);
 415       bool isMarkedTailCall = TheCall->isTailCall();
 416       // If CALL node has tail call attribute set to true and the call is not
 417       // eligible (no RET or the target rejects) the attribute is fixed to
 418       // false. The TargetLowering::IsEligibleForTailCallOptimization function
 419       // must correctly identify tail call optimizable calls.
 420       if (!isMarkedTailCall) continue;
 421       if (Ret==NULL ||
 422           !TLI.IsEligibleForTailCallOptimization(TheCall, OpRet, DAG)) {
 423         // Not eligible. Mark CALL node as non tail call. Note that we
 424         // can modify the call node in place since calls are not CSE'd.
 425         TheCall->setNotTailCall();
 426       } else {
 427         // Look for tail call clobbered arguments. Emit a series of
 428         // copyto/copyfrom virtual register nodes to protect them.
 429         SmallVector<SDValue, 32> Ops;
 430         SDValue Chain = TheCall->getChain(), InFlag;
 431         Ops.push_back(Chain);
 432         Ops.push_back(TheCall->getCallee());
 433         for (unsigned i = 0, e = TheCall->getNumArgs(); i != e; ++i) {
 434           SDValue Arg = TheCall->getArg(i);
 435           bool isByVal = TheCall->getArgFlags(i).isByVal();
 436           MachineFunction &MF = DAG.getMachineFunction();
 437           MachineFrameInfo *MFI = MF.getFrameInfo();
 438           if (!isByVal &&
 439               IsPossiblyOverwrittenArgumentOfTailCall(Arg, MFI)) {
 440             MVT VT = Arg.getValueType();
 441             unsigned VReg = MF.getRegInfo().
 442               createVirtualRegister(TLI.getRegClassFor(VT));
 443             Chain = DAG.getCopyToReg(Chain, VReg, Arg, InFlag);
 444             InFlag = Chain.getValue(1);
 445             Arg = DAG.getCopyFromReg(Chain, VReg, VT, InFlag);
 446             Chain = Arg.getValue(1);
 447             InFlag = Arg.getValue(2);
 448           }
 449           Ops.push_back(Arg);
 450           Ops.push_back(TheCall->getArgFlagsVal(i));
 451         }
 452         // Link in chain of CopyTo/CopyFromReg.
 453         Ops[0] = Chain;
 454         DAG.UpdateNodeOperands(OpCall, Ops.begin(), Ops.size());
 455       }
 456     }
 457   }
 458 }
 459
 460 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB,
 461                                         BasicBlock::iterator Begin,
 462                                         BasicBlock::iterator End) {
 463   SDL->setCurrentBasicBlock(BB);
 464
 465   // Lower all of the non-terminator instructions.
 466   for (BasicBlock::iterator I = Begin; I != End; ++I)
 467     if (!isa<TerminatorInst>(I))
 468       SDL->visit(*I);
 469
 470   // Ensure that all instructions which are used outside of their defining
 471   // blocks are available as virtual registers.  Invoke is handled elsewhere.
 472   for (BasicBlock::iterator I = Begin; I != End; ++I)
 473     if (!I->use_empty() && !isa<PHINode>(I) && !isa<InvokeInst>(I)) {
 474       DenseMap<const Value*,unsigned>::iterator VMI =FuncInfo->ValueMap.find(I);
 475       if (VMI != FuncInfo->ValueMap.end())
 476         SDL->CopyValueToVirtualRegister(I, VMI->second);
 477     }
 478
 479   // Handle PHI nodes in successor blocks.
 480   if (End == LLVMBB->end()) {
 481     HandlePHINodesInSuccessorBlocks(LLVMBB);
 482
 483     // Lower the terminator after the copies are emitted.
 484     SDL->visit(*LLVMBB->getTerminator());
 485   }
 486
 487   // Make sure the root of the DAG is up-to-date.
 488   CurDAG->setRoot(SDL->getControlRoot());
 489
 490   // Check whether calls in this block are real tail calls. Fix up CALL nodes
 491   // with correct tailcall attribute so that the target can rely on the tailcall
 492   // attribute indicating whether the call is really eligible for tail call
 493   // optimization.
 494   if (PerformTailCallOpt)
 495     CheckDAGForTailCallsAndFixThem(*CurDAG, TLI);
 496
 497   // Final step, emit the lowered DAG as machine code.
 498   CodeGenAndEmitDAG();
 499   SDL->clear();
 500 }
 501
 502 void SelectionDAGISel::ComputeLiveOutVRegInfo() {
 503   SmallPtrSet<SDNode*, 128> VisitedNodes;
 504   SmallVector<SDNode*, 128> Worklist;
 505
 506   Worklist.push_back(CurDAG->getRoot().getNode());
 507
 508   APInt Mask;
 509   APInt KnownZero;
 510   APInt KnownOne;
 511
 512   while (!Worklist.empty()) {
 513     SDNode *N = Worklist.back();
 514     Worklist.pop_back();
 515
 516     // If we've already seen this node, ignore it.
 517     if (!VisitedNodes.insert(N))
 518       continue;
 519
 520     // Otherwise, add all chain operands to the worklist.
 521     for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
 522       if (N->getOperand(i).getValueType() == MVT::Other)
 523         Worklist.push_back(N->getOperand(i).getNode());
 524
 525     // If this is a CopyToReg with a vreg dest, process it.
 526     if (N->getOpcode() != ISD::CopyToReg)
 527       continue;
 528
 529     unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
 530     if (!TargetRegisterInfo::isVirtualRegister(DestReg))
 531       continue;
 532
 533     // Ignore non-scalar or non-integer values.
 534     SDValue Src = N->getOperand(2);
 535     MVT SrcVT = Src.getValueType();
 536     if (!SrcVT.isInteger() || SrcVT.isVector())
 537       continue;
 538
 539     unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
 540     Mask = APInt::getAllOnesValue(SrcVT.getSizeInBits());
 541     CurDAG->ComputeMaskedBits(Src, Mask, KnownZero, KnownOne);
 542
 543     // Only install this information if it tells us something.
 544     if (NumSignBits != 1 || KnownZero != 0 || KnownOne != 0) {
 545       DestReg -= TargetRegisterInfo::FirstVirtualRegister;
 546       FunctionLoweringInfo &FLI = CurDAG->getFunctionLoweringInfo();
 547       if (DestReg >= FLI.LiveOutRegInfo.size())
 548         FLI.LiveOutRegInfo.resize(DestReg+1);
 549       FunctionLoweringInfo::LiveOutInfo &LOI = FLI.LiveOutRegInfo[DestReg];
 550       LOI.NumSignBits = NumSignBits;
 551       LOI.KnownOne = NumSignBits;
 552       LOI.KnownZero = NumSignBits;
 553     }
 554   }
 555 }
 556
 557 void SelectionDAGISel::CodeGenAndEmitDAG() {
 558   std::string GroupName;
 559   if (TimePassesIsEnabled)
 560     GroupName = "Instruction Selection and Scheduling";
 561   std::string BlockName;
 562   if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs ||
 563       ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs ||
 564       ViewSUnitDAGs)
 565     BlockName = CurDAG->getMachineFunction().getFunction()->getName() + ':' +
 566                 BB->getBasicBlock()->getName();
 567
 568   DOUT << "Initial selection DAG:\n";
 569   DEBUG(CurDAG->dump());
 570
 571   if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName);
 572
 573   // Run the DAG combiner in pre-legalize mode.
 574   if (TimePassesIsEnabled) {
 575     NamedRegionTimer T("DAG Combining 1", GroupName);
 576     CurDAG->Combine(Unrestricted, *AA, Fast);
 577   } else {
 578     CurDAG->Combine(Unrestricted, *AA, Fast);
 579   }
 580
 581   DOUT << "Optimized lowered selection DAG:\n";
 582   DEBUG(CurDAG->dump());
 583
 584   // Second step, hack on the DAG until it only uses operations and types that
 585   // the target supports.
 586   if (!DisableLegalizeTypes) {
 587     if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " +
 588                                                  BlockName);
 589
 590     bool Changed;
 591     if (TimePassesIsEnabled) {
 592       NamedRegionTimer T("Type Legalization", GroupName);
 593       Changed = CurDAG->LegalizeTypes();
 594     } else {
 595       Changed = CurDAG->LegalizeTypes();
 596     }
 597
 598     DOUT << "Type-legalized selection DAG:\n";
 599     DEBUG(CurDAG->dump());
 600
 601     if (Changed) {
 602       if (ViewDAGCombineLT)
 603         CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
 604
 605       // Run the DAG combiner in post-type-legalize mode.
 606       if (TimePassesIsEnabled) {
 607         NamedRegionTimer T("DAG Combining after legalize types", GroupName);
 608         CurDAG->Combine(NoIllegalTypes, *AA, Fast);
 609       } else {
 610         CurDAG->Combine(NoIllegalTypes, *AA, Fast);
 611       }
 612
 613       DOUT << "Optimized type-legalized selection DAG:\n";
 614       DEBUG(CurDAG->dump());
 615     }
 616   }
 617
 618   if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName);
 619
 620   if (TimePassesIsEnabled) {
 621     NamedRegionTimer T("DAG Legalization", GroupName);
 622     CurDAG->Legalize(DisableLegalizeTypes);
 623   } else {
 624     CurDAG->Legalize(DisableLegalizeTypes);
 625   }
 626
 627   DOUT << "Legalized selection DAG:\n";
 628   DEBUG(CurDAG->dump());
 629
 630   if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName);
 631
 632   // Run the DAG combiner in post-legalize mode.
 633   if (TimePassesIsEnabled) {
 634     NamedRegionTimer T("DAG Combining 2", GroupName);
 635     CurDAG->Combine(NoIllegalOperations, *AA, Fast);
 636   } else {
 637     CurDAG->Combine(NoIllegalOperations, *AA, Fast);
 638   }
 639
 640   DOUT << "Optimized legalized selection DAG:\n";
 641   DEBUG(CurDAG->dump());
 642
 643   if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName);
 644
 645   if (!Fast && EnableValueProp)
 646     ComputeLiveOutVRegInfo();
 647
 648   // Third, instruction select all of the operations to machine code, adding the
 649   // code to the MachineBasicBlock.
 650   if (TimePassesIsEnabled) {
 651     NamedRegionTimer T("Instruction Selection", GroupName);
 652     InstructionSelect();
 653   } else {
 654     InstructionSelect();
 655   }
 656
 657   DOUT << "Selected selection DAG:\n";
 658   DEBUG(CurDAG->dump());
 659
 660   if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName);
 661
 662   // Schedule machine code.
 663   ScheduleDAG *Scheduler;
 664   if (TimePassesIsEnabled) {
 665     NamedRegionTimer T("Instruction Scheduling", GroupName);
 666     Scheduler = Schedule();
 667   } else {
 668     Scheduler = Schedule();
 669   }
 670
 671   if (ViewSUnitDAGs) Scheduler->viewGraph();
 672
 673   // Emit machine code to BB.  This can change 'BB' to the last block being
 674   // inserted into.
 675   if (TimePassesIsEnabled) {
 676     NamedRegionTimer T("Instruction Creation", GroupName);
 677     BB = Scheduler->EmitSchedule();
 678   } else {
 679     BB = Scheduler->EmitSchedule();
 680   }
 681
 682   // Free the scheduler state.
 683   if (TimePassesIsEnabled) {
 684     NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName);
 685     delete Scheduler;
 686   } else {
 687     delete Scheduler;
 688   }
 689
 690   DOUT << "Selected machine code:\n";
 691   DEBUG(BB->dump());
 692 }
 693
 694 void SelectionDAGISel::SelectAllBasicBlocks(Function &Fn, MachineFunction &MF,
 695                                             MachineModuleInfo *MMI,
 696                                             const TargetInstrInfo &TII) {
 697   // Initialize the Fast-ISel state, if needed.
 698   FastISel *FastIS = 0;
 699   if (EnableFastISel)
 700     FastIS = TLI.createFastISel(*FuncInfo->MF, MMI,
 701                                 FuncInfo->ValueMap,
 702                                 FuncInfo->MBBMap,
 703                                 FuncInfo->StaticAllocaMap
 704 #ifndef NDEBUG
 705                                 , FuncInfo->CatchInfoLost
 706 #endif
 707                                 );
 708
 709   // Iterate over all basic blocks in the function.
 710   for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) {
 711     BasicBlock *LLVMBB = &*I;
 712     BB = FuncInfo->MBBMap[LLVMBB];
 713
 714     BasicBlock::iterator const Begin = LLVMBB->begin();
 715     BasicBlock::iterator const End = LLVMBB->end();
 716     BasicBlock::iterator BI = Begin;
 717
 718     // Lower any arguments needed in this block if this is the entry block.
 719     bool SuppressFastISel = false;
 720     if (LLVMBB == &Fn.getEntryBlock()) {
 721       LowerArguments(LLVMBB);
 722
 723       // If any of the arguments has the byval attribute, forgo
 724       // fast-isel in the entry block.
 725       if (FastIS) {
 726         unsigned j = 1;
 727         for (Function::arg_iterator I = Fn.arg_begin(), E = Fn.arg_end();
 728              I != E; ++I, ++j)
 729           if (Fn.paramHasAttr(j, Attribute::ByVal)) {
 730             if (EnableFastISelVerbose || EnableFastISelAbort)
 731               cerr << "FastISel skips entry block due to byval argument\n";
 732             SuppressFastISel = true;
 733             break;
 734           }
 735       }
 736     }
 737
 738     if (MMI && BB->isLandingPad()) {
 739       // Add a label to mark the beginning of the landing pad.  Deletion of the
 740       // landing pad can thus be detected via the MachineModuleInfo.
 741       unsigned LabelID = MMI->addLandingPad(BB);
 742
 743       const TargetInstrDesc &II = TII.get(TargetInstrInfo::EH_LABEL);
 744       BuildMI(BB, II).addImm(LabelID);
 745
 746       // Mark exception register as live in.
 747       unsigned Reg = TLI.getExceptionAddressRegister();
 748       if (Reg) BB->addLiveIn(Reg);
 749
 750       // Mark exception selector register as live in.
 751       Reg = TLI.getExceptionSelectorRegister();
 752       if (Reg) BB->addLiveIn(Reg);
 753
 754       // FIXME: Hack around an exception handling flaw (PR1508): the personality
 755       // function and list of typeids logically belong to the invoke (or, if you
 756       // like, the basic block containing the invoke), and need to be associated
 757       // with it in the dwarf exception handling tables.  Currently however the
 758       // information is provided by an intrinsic (eh.selector) that can be moved
 759       // to unexpected places by the optimizers: if the unwind edge is critical,
 760       // then breaking it can result in the intrinsics being in the successor of
 761       // the landing pad, not the landing pad itself.  This results in exceptions
 762       // not being caught because no typeids are associated with the invoke.
 763       // This may not be the only way things can go wrong, but it is the only way
 764       // we try to work around for the moment.
 765       BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator());
 766
 767       if (Br && Br->isUnconditional()) { // Critical edge?
 768         BasicBlock::iterator I, E;
 769         for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I)
 770           if (isa<EHSelectorInst>(I))
 771             break;
 772
 773         if (I == E)
 774           // No catch info found - try to extract some from the successor.
 775           copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, *FuncInfo);
 776       }
 777     }
 778
 779     // Before doing SelectionDAG ISel, see if FastISel has been requested.
 780     if (FastIS && !SuppressFastISel) {
 781       // Emit code for any incoming arguments. This must happen before
 782       // beginning FastISel on the entry block.
 783       if (LLVMBB == &Fn.getEntryBlock()) {
 784         CurDAG->setRoot(SDL->getControlRoot());
 785         CodeGenAndEmitDAG();
 786         SDL->clear();
 787       }
 788       FastIS->startNewBlock(BB);
 789       // Do FastISel on as many instructions as possible.
 790       for (; BI != End; ++BI) {
 791         // Just before the terminator instruction, insert instructions to
 792         // feed PHI nodes in successor blocks.
 793         if (isa<TerminatorInst>(BI))
 794           if (!HandlePHINodesInSuccessorBlocksFast(LLVMBB, FastIS)) {
 795             if (EnableFastISelVerbose || EnableFastISelAbort) {
 796               cerr << "FastISel miss: ";
 797               BI->dump();
 798             }
 799             if (EnableFastISelAbort)
 800               assert(0 && "FastISel didn't handle a PHI in a successor");
 801             break;
 802           }
 803
 804         // First try normal tablegen-generated "fast" selection.
 805         if (FastIS->SelectInstruction(BI))
 806           continue;
 807
 808         // Next, try calling the target to attempt to handle the instruction.
 809         if (FastIS->TargetSelectInstruction(BI))
 810           continue;
 811
 812         // Then handle certain instructions as single-LLVM-Instruction blocks.
 813         if (isa<CallInst>(BI)) {
 814           if (EnableFastISelVerbose || EnableFastISelAbort) {
 815             cerr << "FastISel missed call: ";
 816             BI->dump();
 817           }
 818
 819           if (BI->getType() != Type::VoidTy) {
 820             unsigned &R = FuncInfo->ValueMap[BI];
 821             if (!R)
 822               R = FuncInfo->CreateRegForValue(BI);
 823           }
 824
 825           SelectBasicBlock(LLVMBB, BI, next(BI));
 826           // If the instruction was codegen'd with multiple blocks,
 827           // inform the FastISel object where to resume inserting.
 828           FastIS->setCurrentBlock(BB);
 829           continue;
 830         }
 831
 832         // Otherwise, give up on FastISel for the rest of the block.
 833         // For now, be a little lenient about non-branch terminators.
 834         if (!isa<TerminatorInst>(BI) || isa<BranchInst>(BI)) {
 835           if (EnableFastISelVerbose || EnableFastISelAbort) {
 836             cerr << "FastISel miss: ";
 837             BI->dump();
 838           }
 839           if (EnableFastISelAbort)
 840             // The "fast" selector couldn't handle something and bailed.
 841             // For the purpose of debugging, just abort.
 842             assert(0 && "FastISel didn't select the entire block");
 843         }
 844         break;
 845       }
 846     }
 847
 848     // Run SelectionDAG instruction selection on the remainder of the block
 849     // not handled by FastISel. If FastISel is not run, this is the entire
 850     // block.
 851     if (BI != End)
 852       SelectBasicBlock(LLVMBB, BI, End);
 853
 854     FinishBasicBlock();
 855   }
 856
 857   delete FastIS;
 858 }
 859
 860 void
 861 SelectionDAGISel::FinishBasicBlock() {
 862
 863   DOUT << "Target-post-processed machine code:\n";
 864   DEBUG(BB->dump());
 865
 866   DOUT << "Total amount of phi nodes to update: "
 867        << SDL->PHINodesToUpdate.size() << "\n";
 868   DEBUG(for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i)
 869           DOUT << "Node " << i << " : (" << SDL->PHINodesToUpdate[i].first
 870                << ", " << SDL->PHINodesToUpdate[i].second << ")\n";);
 871
 872   // Next, now that we know what the last MBB the LLVM BB expanded is, update
 873   // PHI nodes in successors.
 874   if (SDL->SwitchCases.empty() &&
 875       SDL->JTCases.empty() &&
 876       SDL->BitTestCases.empty()) {
 877     for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) {
 878       MachineInstr *PHI = SDL->PHINodesToUpdate[i].first;
 879       assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
 880              "This is not a machine PHI node that we are updating!");
 881       PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[i].second,
 882                                                 false));
 883       PHI->addOperand(MachineOperand::CreateMBB(BB));
 884     }
 885     SDL->PHINodesToUpdate.clear();
 886     return;
 887   }
 888
 889   for (unsigned i = 0, e = SDL->BitTestCases.size(); i != e; ++i) {
 890     // Lower header first, if it wasn't already lowered
 891     if (!SDL->BitTestCases[i].Emitted) {
 892       // Set the current basic block to the mbb we wish to insert the code into
 893       BB = SDL->BitTestCases[i].Parent;
 894       SDL->setCurrentBasicBlock(BB);
 895       // Emit the code
 896       SDL->visitBitTestHeader(SDL->BitTestCases[i]);
 897       CurDAG->setRoot(SDL->getRoot());
 898       CodeGenAndEmitDAG();
 899       SDL->clear();
 900     }
 901
 902     for (unsigned j = 0, ej = SDL->BitTestCases[i].Cases.size(); j != ej; ++j) {
 903       // Set the current basic block to the mbb we wish to insert the code into
 904       BB = SDL->BitTestCases[i].Cases[j].ThisBB;
 905       SDL->setCurrentBasicBlock(BB);
 906       // Emit the code
 907       if (j+1 != ej)
 908         SDL->visitBitTestCase(SDL->BitTestCases[i].Cases[j+1].ThisBB,
 909                               SDL->BitTestCases[i].Reg,
 910                               SDL->BitTestCases[i].Cases[j]);
 911       else
 912         SDL->visitBitTestCase(SDL->BitTestCases[i].Default,
 913                               SDL->BitTestCases[i].Reg,
 914                               SDL->BitTestCases[i].Cases[j]);
 915
 916
 917       CurDAG->setRoot(SDL->getRoot());
 918       CodeGenAndEmitDAG();
 919       SDL->clear();
 920     }
 921
 922     // Update PHI Nodes
 923     for (unsigned pi = 0, pe = SDL->PHINodesToUpdate.size(); pi != pe; ++pi) {
 924       MachineInstr *PHI = SDL->PHINodesToUpdate[pi].first;
 925       MachineBasicBlock *PHIBB = PHI->getParent();
 926       assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
 927              "This is not a machine PHI node that we are updating!");
 928       // This is "default" BB. We have two jumps to it. From "header" BB and
 929       // from last "case" BB.
 930       if (PHIBB == SDL->BitTestCases[i].Default) {
 931         PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second,
 932                                                   false));
 933         PHI->addOperand(MachineOperand::CreateMBB(SDL->BitTestCases[i].Parent));
 934         PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second,
 935                                                   false));
 936         PHI->addOperand(MachineOperand::CreateMBB(SDL->BitTestCases[i].Cases.
 937                                                   back().ThisBB));
 938       }
 939       // One of "cases" BB.
 940       for (unsigned j = 0, ej = SDL->BitTestCases[i].Cases.size();
 941            j != ej; ++j) {
 942         MachineBasicBlock* cBB = SDL->BitTestCases[i].Cases[j].ThisBB;
 943         if (cBB->succ_end() !=
 944             std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) {
 945           PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second,
 946                                                     false));
 947           PHI->addOperand(MachineOperand::CreateMBB(cBB));
 948         }
 949       }
 950     }
 951   }
 952   SDL->BitTestCases.clear();
 953
 954   // If the JumpTable record is filled in, then we need to emit a jump table.
 955   // Updating the PHI nodes is tricky in this case, since we need to determine
 956   // whether the PHI is a successor of the range check MBB or the jump table MBB
 957   for (unsigned i = 0, e = SDL->JTCases.size(); i != e; ++i) {
 958     // Lower header first, if it wasn't already lowered
 959     if (!SDL->JTCases[i].first.Emitted) {
 960       // Set the current basic block to the mbb we wish to insert the code into
 961       BB = SDL->JTCases[i].first.HeaderBB;
 962       SDL->setCurrentBasicBlock(BB);
 963       // Emit the code
 964       SDL->visitJumpTableHeader(SDL->JTCases[i].second, SDL->JTCases[i].first);
 965       CurDAG->setRoot(SDL->getRoot());
 966       CodeGenAndEmitDAG();
 967       SDL->clear();
 968     }
 969
 970     // Set the current basic block to the mbb we wish to insert the code into
 971     BB = SDL->JTCases[i].second.MBB;
 972     SDL->setCurrentBasicBlock(BB);
 973     // Emit the code
 974     SDL->visitJumpTable(SDL->JTCases[i].second);
 975     CurDAG->setRoot(SDL->getRoot());
 976     CodeGenAndEmitDAG();
 977     SDL->clear();
 978
 979     // Update PHI Nodes
 980     for (unsigned pi = 0, pe = SDL->PHINodesToUpdate.size(); pi != pe; ++pi) {
 981       MachineInstr *PHI = SDL->PHINodesToUpdate[pi].first;
 982       MachineBasicBlock *PHIBB = PHI->getParent();
 983       assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
 984              "This is not a machine PHI node that we are updating!");
 985       // "default" BB. We can go there only from header BB.
 986       if (PHIBB == SDL->JTCases[i].second.Default) {
 987         PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second,
 988                                                   false));
 989         PHI->addOperand(MachineOperand::CreateMBB(SDL->JTCases[i].first.HeaderBB));
 990       }
 991       // JT BB. Just iterate over successors here
 992       if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) {
 993         PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pi].second,
 994                                                   false));
 995         PHI->addOperand(MachineOperand::CreateMBB(BB));
 996       }
 997     }
 998   }
 999   SDL->JTCases.clear();
1000
1001   // If the switch block involved a branch to one of the actual successors, we
1002   // need to update PHI nodes in that block.
1003   for (unsigned i = 0, e = SDL->PHINodesToUpdate.size(); i != e; ++i) {
1004     MachineInstr *PHI = SDL->PHINodesToUpdate[i].first;
1005     assert(PHI->getOpcode() == TargetInstrInfo::PHI &&
1006            "This is not a machine PHI node that we are updating!");
1007     if (BB->isSuccessor(PHI->getParent())) {
1008       PHI->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[i].second,
1009                                                 false));
1010       PHI->addOperand(MachineOperand::CreateMBB(BB));
1011     }
1012   }
1013
1014   // If we generated any switch lowering information, build and codegen any
1015   // additional DAGs necessary.
1016   for (unsigned i = 0, e = SDL->SwitchCases.size(); i != e; ++i) {
1017     // Set the current basic block to the mbb we wish to insert the code into
1018     BB = SDL->SwitchCases[i].ThisBB;
1019     SDL->setCurrentBasicBlock(BB);
1020
1021     // Emit the code
1022     SDL->visitSwitchCase(SDL->SwitchCases[i]);
1023     CurDAG->setRoot(SDL->getRoot());
1024     CodeGenAndEmitDAG();
1025     SDL->clear();
1026
1027     // Handle any PHI nodes in successors of this chunk, as if we were coming
1028     // from the original BB before switch expansion.  Note that PHI nodes can
1029     // occur multiple times in PHINodesToUpdate.  We have to be very careful to
1030     // handle them the right number of times.
1031     while ((BB = SDL->SwitchCases[i].TrueBB)) {  // Handle LHS and RHS.
1032       for (MachineBasicBlock::iterator Phi = BB->begin();
1033            Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){
1034         // This value for this PHI node is recorded in PHINodesToUpdate, get it.
1035         for (unsigned pn = 0; ; ++pn) {
1036           assert(pn != SDL->PHINodesToUpdate.size() &&
1037                  "Didn't find PHI entry!");
1038           if (SDL->PHINodesToUpdate[pn].first == Phi) {
1039             Phi->addOperand(MachineOperand::CreateReg(SDL->PHINodesToUpdate[pn].
1040                                                       second, false));
1041             Phi->addOperand(MachineOperand::CreateMBB(SDL->SwitchCases[i].ThisBB));
1042             break;
1043           }
1044         }
1045       }
1046
1047       // Don't process RHS if same block as LHS.
1048       if (BB == SDL->SwitchCases[i].FalseBB)
1049         SDL->SwitchCases[i].FalseBB = 0;
1050
1051       // If we haven't handled the RHS, do so now.  Otherwise, we're done.
1052       SDL->SwitchCases[i].TrueBB = SDL->SwitchCases[i].FalseBB;
1053       SDL->SwitchCases[i].FalseBB = 0;
1054     }
1055     assert(SDL->SwitchCases[i].TrueBB == 0 && SDL->SwitchCases[i].FalseBB == 0);
1056   }
1057   SDL->SwitchCases.clear();
1058
1059   SDL->PHINodesToUpdate.clear();
1060 }
1061
1062
1063 /// Schedule - Pick a safe ordering for instructions for each
1064 /// target node in the graph.
1065 ///
1066 ScheduleDAG *SelectionDAGISel::Schedule() {
1067   RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
1068
1069   if (!Ctor) {
1070     Ctor = ISHeuristic;
1071     RegisterScheduler::setDefault(Ctor);
1072   }
1073
1074   TargetMachine &TM = getTargetLowering().getTargetMachine();
1075   ScheduleDAG *Scheduler = Ctor(this, CurDAG, &TM, BB, Fast);
1076   Scheduler->Run();
1077
1078   return Scheduler;
1079 }
1080
1081
1082 HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() {
1083   return new HazardRecognizer();
1084 }
1085
1086 //===----------------------------------------------------------------------===//
1087 // Helper functions used by the generated instruction selector.
1088 //===----------------------------------------------------------------------===//
1089 // Calls to these methods are generated by tblgen.
1090
1091 /// CheckAndMask - The isel is trying to match something like (and X, 255).  If
1092 /// the dag combiner simplified the 255, we still want to match.  RHS is the
1093 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
1094 /// specified in the .td file (e.g. 255).
1095 bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
1096                                     int64_t DesiredMaskS) const {
1097   const APInt &ActualMask = RHS->getAPIntValue();
1098   const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
1099
1100   // If the actual mask exactly matches, success!
1101   if (ActualMask == DesiredMask)
1102     return true;
1103
1104   // If the actual AND mask is allowing unallowed bits, this doesn't match.
1105   if (ActualMask.intersects(~DesiredMask))
1106     return false;
1107
1108   // Otherwise, the DAG Combiner may have proven that the value coming in is
1109   // either already zero or is not demanded.  Check for known zero input bits.
1110   APInt NeededMask = DesiredMask & ~ActualMask;
1111   if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
1112     return true;
1113
1114   // TODO: check to see if missing bits are just not demanded.
1115
1116   // Otherwise, this pattern doesn't match.
1117   return false;
1118 }
1119
1120 /// CheckOrMask - The isel is trying to match something like (or X, 255).  If
1121 /// the dag combiner simplified the 255, we still want to match.  RHS is the
1122 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
1123 /// specified in the .td file (e.g. 255).
1124 bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
1125                                    int64_t DesiredMaskS) const {
1126   const APInt &ActualMask = RHS->getAPIntValue();
1127   const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
1128
1129   // If the actual mask exactly matches, success!
1130   if (ActualMask == DesiredMask)
1131     return true;
1132
1133   // If the actual AND mask is allowing unallowed bits, this doesn't match.
1134   if (ActualMask.intersects(~DesiredMask))
1135     return false;
1136
1137   // Otherwise, the DAG Combiner may have proven that the value coming in is
1138   // either already zero or is not demanded.  Check for known zero input bits.
1139   APInt NeededMask = DesiredMask & ~ActualMask;
1140
1141   APInt KnownZero, KnownOne;
1142   CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne);
1143
1144   // If all the missing bits in the or are already known to be set, match!
1145   if ((NeededMask & KnownOne) == NeededMask)
1146     return true;
1147
1148   // TODO: check to see if missing bits are just not demanded.
1149
1150   // Otherwise, this pattern doesn't match.
1151   return false;
1152 }
1153
1154
1155 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
1156 /// by tblgen.  Others should not call it.
1157 void SelectionDAGISel::
1158 SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops) {
1159   std::vector<SDValue> InOps;
1160   std::swap(InOps, Ops);
1161
1162   Ops.push_back(InOps[0]);  // input chain.
1163   Ops.push_back(InOps[1]);  // input asm string.
1164
1165   unsigned i = 2, e = InOps.size();
1166   if (InOps[e-1].getValueType() == MVT::Flag)
1167     --e;  // Don't process a flag operand if it is here.
1168
1169   while (i != e) {
1170     unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue();
1171     if ((Flags & 7) != 4 /*MEM*/) {
1172       // Just skip over this operand, copying the operands verbatim.
1173       Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1);
1174       i += (Flags >> 3) + 1;
1175     } else {
1176       assert((Flags >> 3) == 1 && "Memory operand with multiple values?");
1177       // Otherwise, this is a memory operand.  Ask the target to select it.
1178       std::vector<SDValue> SelOps;
1179       if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps)) {
1180         cerr << "Could not match memory address.  Inline asm failure!\n";
1181         exit(1);
1182       }
1183
1184       // Add this to the output node.
1185       MVT IntPtrTy = CurDAG->getTargetLoweringInfo().getPointerTy();
1186       Ops.push_back(CurDAG->getTargetConstant(4/*MEM*/ | (SelOps.size()<< 3),
1187                                               IntPtrTy));
1188       Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
1189       i += 2;
1190     }
1191   }
1192
1193   // Add the flag input back if present.
1194   if (e != InOps.size())
1195     Ops.push_back(InOps.back());
1196 }
1197
1198 char SelectionDAGISel::ID = 0;