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