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