SelectionDAGISel.cpp revision 6ccbbd89906157187ac04b2b3237c4aee7acd095
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/ADT/BitVector.h" 16#include "llvm/Analysis/AliasAnalysis.h" 17#include "llvm/CodeGen/SelectionDAGISel.h" 18#include "llvm/CodeGen/ScheduleDAG.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/Collector.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/SchedulerRegistry.h" 37#include "llvm/CodeGen/SelectionDAG.h" 38#include "llvm/Target/TargetRegisterInfo.h" 39#include "llvm/Target/TargetData.h" 40#include "llvm/Target/TargetFrameInfo.h" 41#include "llvm/Target/TargetInstrInfo.h" 42#include "llvm/Target/TargetLowering.h" 43#include "llvm/Target/TargetMachine.h" 44#include "llvm/Target/TargetOptions.h" 45#include "llvm/Support/MathExtras.h" 46#include "llvm/Support/Debug.h" 47#include "llvm/Support/Compiler.h" 48#include <algorithm> 49using namespace llvm; 50 51#ifndef NDEBUG 52static cl::opt<bool> 53ViewISelDAGs("view-isel-dags", cl::Hidden, 54 cl::desc("Pop up a window to show isel dags as they are selected")); 55static cl::opt<bool> 56ViewSchedDAGs("view-sched-dags", cl::Hidden, 57 cl::desc("Pop up a window to show sched dags as they are processed")); 58static cl::opt<bool> 59ViewSUnitDAGs("view-sunit-dags", cl::Hidden, 60 cl::desc("Pop up a window to show SUnit dags after they are processed")); 61#else 62static const bool ViewISelDAGs = 0, ViewSchedDAGs = 0, ViewSUnitDAGs = 0; 63#endif 64 65//===---------------------------------------------------------------------===// 66/// 67/// RegisterScheduler class - Track the registration of instruction schedulers. 68/// 69//===---------------------------------------------------------------------===// 70MachinePassRegistry RegisterScheduler::Registry; 71 72//===---------------------------------------------------------------------===// 73/// 74/// ISHeuristic command line option for instruction schedulers. 75/// 76//===---------------------------------------------------------------------===// 77namespace { 78 cl::opt<RegisterScheduler::FunctionPassCtor, false, 79 RegisterPassParser<RegisterScheduler> > 80 ISHeuristic("pre-RA-sched", 81 cl::init(&createDefaultScheduler), 82 cl::desc("Instruction schedulers available (before register" 83 " allocation):")); 84 85 static RegisterScheduler 86 defaultListDAGScheduler("default", " Best scheduler for the target", 87 createDefaultScheduler); 88} // namespace 89 90namespace { struct SDISelAsmOperandInfo; } 91 92namespace { 93 /// RegsForValue - This struct represents the physical registers that a 94 /// particular value is assigned and the type information about the value. 95 /// This is needed because values can be promoted into larger registers and 96 /// expanded into multiple smaller registers than the value. 97 struct VISIBILITY_HIDDEN RegsForValue { 98 /// Regs - This list holds the register (for legal and promoted values) 99 /// or register set (for expanded values) that the value should be assigned 100 /// to. 101 std::vector<unsigned> Regs; 102 103 /// RegVT - The value type of each register. 104 /// 105 MVT::ValueType RegVT; 106 107 /// ValueVT - The value type of the LLVM value, which may be promoted from 108 /// RegVT or made from merging the two expanded parts. 109 MVT::ValueType ValueVT; 110 111 RegsForValue() : RegVT(MVT::Other), ValueVT(MVT::Other) {} 112 113 RegsForValue(unsigned Reg, MVT::ValueType regvt, MVT::ValueType valuevt) 114 : RegVT(regvt), ValueVT(valuevt) { 115 Regs.push_back(Reg); 116 } 117 RegsForValue(const std::vector<unsigned> ®s, 118 MVT::ValueType regvt, MVT::ValueType valuevt) 119 : Regs(regs), RegVT(regvt), ValueVT(valuevt) { 120 } 121 122 /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from 123 /// this value and returns the result as a ValueVT value. This uses 124 /// Chain/Flag as the input and updates them for the output Chain/Flag. 125 /// If the Flag pointer is NULL, no flag is used. 126 SDOperand getCopyFromRegs(SelectionDAG &DAG, 127 SDOperand &Chain, SDOperand *Flag) const; 128 129 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the 130 /// specified value into the registers specified by this object. This uses 131 /// Chain/Flag as the input and updates them for the output Chain/Flag. 132 /// If the Flag pointer is NULL, no flag is used. 133 void getCopyToRegs(SDOperand Val, SelectionDAG &DAG, 134 SDOperand &Chain, SDOperand *Flag) const; 135 136 /// AddInlineAsmOperands - Add this value to the specified inlineasm node 137 /// operand list. This adds the code marker and includes the number of 138 /// values added into it. 139 void AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG, 140 std::vector<SDOperand> &Ops) const; 141 }; 142} 143 144namespace llvm { 145 //===--------------------------------------------------------------------===// 146 /// createDefaultScheduler - This creates an instruction scheduler appropriate 147 /// for the target. 148 ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, 149 SelectionDAG *DAG, 150 MachineBasicBlock *BB) { 151 TargetLowering &TLI = IS->getTargetLowering(); 152 153 if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) { 154 return createTDListDAGScheduler(IS, DAG, BB); 155 } else { 156 assert(TLI.getSchedulingPreference() == 157 TargetLowering::SchedulingForRegPressure && "Unknown sched type!"); 158 return createBURRListDAGScheduler(IS, DAG, BB); 159 } 160 } 161 162 163 //===--------------------------------------------------------------------===// 164 /// FunctionLoweringInfo - This contains information that is global to a 165 /// function that is used when lowering a region of the function. 166 class FunctionLoweringInfo { 167 public: 168 TargetLowering &TLI; 169 Function &Fn; 170 MachineFunction &MF; 171 MachineRegisterInfo &RegInfo; 172 173 FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF); 174 175 /// MBBMap - A mapping from LLVM basic blocks to their machine code entry. 176 std::map<const BasicBlock*, MachineBasicBlock *> MBBMap; 177 178 /// ValueMap - Since we emit code for the function a basic block at a time, 179 /// we must remember which virtual registers hold the values for 180 /// cross-basic-block values. 181 DenseMap<const Value*, unsigned> ValueMap; 182 183 /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in 184 /// the entry block. This allows the allocas to be efficiently referenced 185 /// anywhere in the function. 186 std::map<const AllocaInst*, int> StaticAllocaMap; 187 188#ifndef NDEBUG 189 SmallSet<Instruction*, 8> CatchInfoLost; 190 SmallSet<Instruction*, 8> CatchInfoFound; 191#endif 192 193 unsigned MakeReg(MVT::ValueType VT) { 194 return RegInfo.createVirtualRegister(TLI.getRegClassFor(VT)); 195 } 196 197 /// isExportedInst - Return true if the specified value is an instruction 198 /// exported from its block. 199 bool isExportedInst(const Value *V) { 200 return ValueMap.count(V); 201 } 202 203 unsigned CreateRegForValue(const Value *V); 204 205 unsigned InitializeRegForValue(const Value *V) { 206 unsigned &R = ValueMap[V]; 207 assert(R == 0 && "Already initialized this value register!"); 208 return R = CreateRegForValue(V); 209 } 210 }; 211} 212 213/// isSelector - Return true if this instruction is a call to the 214/// eh.selector intrinsic. 215static bool isSelector(Instruction *I) { 216 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(I)) 217 return (II->getIntrinsicID() == Intrinsic::eh_selector_i32 || 218 II->getIntrinsicID() == Intrinsic::eh_selector_i64); 219 return false; 220} 221 222/// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by 223/// PHI nodes or outside of the basic block that defines it, or used by a 224/// switch or atomic instruction, which may expand to multiple basic blocks. 225static bool isUsedOutsideOfDefiningBlock(Instruction *I) { 226 if (isa<PHINode>(I)) return true; 227 BasicBlock *BB = I->getParent(); 228 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) 229 if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI) || 230 // FIXME: Remove switchinst special case. 231 isa<SwitchInst>(*UI)) 232 return true; 233 return false; 234} 235 236/// isOnlyUsedInEntryBlock - If the specified argument is only used in the 237/// entry block, return true. This includes arguments used by switches, since 238/// the switch may expand into multiple basic blocks. 239static bool isOnlyUsedInEntryBlock(Argument *A) { 240 BasicBlock *Entry = A->getParent()->begin(); 241 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI) 242 if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI)) 243 return false; // Use not in entry block. 244 return true; 245} 246 247FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli, 248 Function &fn, MachineFunction &mf) 249 : TLI(tli), Fn(fn), MF(mf), RegInfo(MF.getRegInfo()) { 250 251 // Create a vreg for each argument register that is not dead and is used 252 // outside of the entry block for the function. 253 for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end(); 254 AI != E; ++AI) 255 if (!isOnlyUsedInEntryBlock(AI)) 256 InitializeRegForValue(AI); 257 258 // Initialize the mapping of values to registers. This is only set up for 259 // instruction values that are used outside of the block that defines 260 // them. 261 Function::iterator BB = Fn.begin(), EB = Fn.end(); 262 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 263 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 264 if (ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) { 265 const Type *Ty = AI->getAllocatedType(); 266 uint64_t TySize = TLI.getTargetData()->getABITypeSize(Ty); 267 unsigned Align = 268 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), 269 AI->getAlignment()); 270 271 TySize *= CUI->getZExtValue(); // Get total allocated size. 272 if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects. 273 StaticAllocaMap[AI] = 274 MF.getFrameInfo()->CreateStackObject(TySize, Align); 275 } 276 277 for (; BB != EB; ++BB) 278 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 279 if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I)) 280 if (!isa<AllocaInst>(I) || 281 !StaticAllocaMap.count(cast<AllocaInst>(I))) 282 InitializeRegForValue(I); 283 284 // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This 285 // also creates the initial PHI MachineInstrs, though none of the input 286 // operands are populated. 287 for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) { 288 MachineBasicBlock *MBB = new MachineBasicBlock(BB); 289 MBBMap[BB] = MBB; 290 MF.getBasicBlockList().push_back(MBB); 291 292 // Create Machine PHI nodes for LLVM PHI nodes, lowering them as 293 // appropriate. 294 PHINode *PN; 295 for (BasicBlock::iterator I = BB->begin();(PN = dyn_cast<PHINode>(I)); ++I){ 296 if (PN->use_empty()) continue; 297 298 MVT::ValueType VT = TLI.getValueType(PN->getType()); 299 unsigned NumRegisters = TLI.getNumRegisters(VT); 300 unsigned PHIReg = ValueMap[PN]; 301 assert(PHIReg && "PHI node does not have an assigned virtual register!"); 302 const TargetInstrInfo *TII = TLI.getTargetMachine().getInstrInfo(); 303 for (unsigned i = 0; i != NumRegisters; ++i) 304 BuildMI(MBB, TII->get(TargetInstrInfo::PHI), PHIReg+i); 305 } 306 } 307} 308 309/// CreateRegForValue - Allocate the appropriate number of virtual registers of 310/// the correctly promoted or expanded types. Assign these registers 311/// consecutive vreg numbers and return the first assigned number. 312unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) { 313 MVT::ValueType VT = TLI.getValueType(V->getType()); 314 315 unsigned NumRegisters = TLI.getNumRegisters(VT); 316 MVT::ValueType RegisterVT = TLI.getRegisterType(VT); 317 318 unsigned R = MakeReg(RegisterVT); 319 for (unsigned i = 1; i != NumRegisters; ++i) 320 MakeReg(RegisterVT); 321 322 return R; 323} 324 325//===----------------------------------------------------------------------===// 326/// SelectionDAGLowering - This is the common target-independent lowering 327/// implementation that is parameterized by a TargetLowering object. 328/// Also, targets can overload any lowering method. 329/// 330namespace llvm { 331class SelectionDAGLowering { 332 MachineBasicBlock *CurMBB; 333 334 DenseMap<const Value*, SDOperand> NodeMap; 335 336 /// PendingLoads - Loads are not emitted to the program immediately. We bunch 337 /// them up and then emit token factor nodes when possible. This allows us to 338 /// get simple disambiguation between loads without worrying about alias 339 /// analysis. 340 std::vector<SDOperand> PendingLoads; 341 342 /// PendingExports - CopyToReg nodes that copy values to virtual registers 343 /// for export to other blocks need to be emitted before any terminator 344 /// instruction, but they have no other ordering requirements. We bunch them 345 /// up and the emit a single tokenfactor for them just before terminator 346 /// instructions. 347 std::vector<SDOperand> PendingExports; 348 349 /// Case - A struct to record the Value for a switch case, and the 350 /// case's target basic block. 351 struct Case { 352 Constant* Low; 353 Constant* High; 354 MachineBasicBlock* BB; 355 356 Case() : Low(0), High(0), BB(0) { } 357 Case(Constant* low, Constant* high, MachineBasicBlock* bb) : 358 Low(low), High(high), BB(bb) { } 359 uint64_t size() const { 360 uint64_t rHigh = cast<ConstantInt>(High)->getSExtValue(); 361 uint64_t rLow = cast<ConstantInt>(Low)->getSExtValue(); 362 return (rHigh - rLow + 1ULL); 363 } 364 }; 365 366 struct CaseBits { 367 uint64_t Mask; 368 MachineBasicBlock* BB; 369 unsigned Bits; 370 371 CaseBits(uint64_t mask, MachineBasicBlock* bb, unsigned bits): 372 Mask(mask), BB(bb), Bits(bits) { } 373 }; 374 375 typedef std::vector<Case> CaseVector; 376 typedef std::vector<CaseBits> CaseBitsVector; 377 typedef CaseVector::iterator CaseItr; 378 typedef std::pair<CaseItr, CaseItr> CaseRange; 379 380 /// CaseRec - A struct with ctor used in lowering switches to a binary tree 381 /// of conditional branches. 382 struct CaseRec { 383 CaseRec(MachineBasicBlock *bb, Constant *lt, Constant *ge, CaseRange r) : 384 CaseBB(bb), LT(lt), GE(ge), Range(r) {} 385 386 /// CaseBB - The MBB in which to emit the compare and branch 387 MachineBasicBlock *CaseBB; 388 /// LT, GE - If nonzero, we know the current case value must be less-than or 389 /// greater-than-or-equal-to these Constants. 390 Constant *LT; 391 Constant *GE; 392 /// Range - A pair of iterators representing the range of case values to be 393 /// processed at this point in the binary search tree. 394 CaseRange Range; 395 }; 396 397 typedef std::vector<CaseRec> CaseRecVector; 398 399 /// The comparison function for sorting the switch case values in the vector. 400 /// WARNING: Case ranges should be disjoint! 401 struct CaseCmp { 402 bool operator () (const Case& C1, const Case& C2) { 403 assert(isa<ConstantInt>(C1.Low) && isa<ConstantInt>(C2.High)); 404 const ConstantInt* CI1 = cast<const ConstantInt>(C1.Low); 405 const ConstantInt* CI2 = cast<const ConstantInt>(C2.High); 406 return CI1->getValue().slt(CI2->getValue()); 407 } 408 }; 409 410 struct CaseBitsCmp { 411 bool operator () (const CaseBits& C1, const CaseBits& C2) { 412 return C1.Bits > C2.Bits; 413 } 414 }; 415 416 unsigned Clusterify(CaseVector& Cases, const SwitchInst &SI); 417 418public: 419 // TLI - This is information that describes the available target features we 420 // need for lowering. This indicates when operations are unavailable, 421 // implemented with a libcall, etc. 422 TargetLowering &TLI; 423 SelectionDAG &DAG; 424 const TargetData *TD; 425 AliasAnalysis &AA; 426 427 /// SwitchCases - Vector of CaseBlock structures used to communicate 428 /// SwitchInst code generation information. 429 std::vector<SelectionDAGISel::CaseBlock> SwitchCases; 430 /// JTCases - Vector of JumpTable structures used to communicate 431 /// SwitchInst code generation information. 432 std::vector<SelectionDAGISel::JumpTableBlock> JTCases; 433 std::vector<SelectionDAGISel::BitTestBlock> BitTestCases; 434 435 /// FuncInfo - Information about the function as a whole. 436 /// 437 FunctionLoweringInfo &FuncInfo; 438 439 /// GCI - Garbage collection metadata for the function. 440 CollectorMetadata *GCI; 441 442 SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli, 443 AliasAnalysis &aa, 444 FunctionLoweringInfo &funcinfo, 445 CollectorMetadata *gci) 446 : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()), AA(aa), 447 FuncInfo(funcinfo), GCI(gci) { 448 } 449 450 /// getRoot - Return the current virtual root of the Selection DAG, 451 /// flushing any PendingLoad items. This must be done before emitting 452 /// a store or any other node that may need to be ordered after any 453 /// prior load instructions. 454 /// 455 SDOperand getRoot() { 456 if (PendingLoads.empty()) 457 return DAG.getRoot(); 458 459 if (PendingLoads.size() == 1) { 460 SDOperand Root = PendingLoads[0]; 461 DAG.setRoot(Root); 462 PendingLoads.clear(); 463 return Root; 464 } 465 466 // Otherwise, we have to make a token factor node. 467 SDOperand Root = DAG.getNode(ISD::TokenFactor, MVT::Other, 468 &PendingLoads[0], PendingLoads.size()); 469 PendingLoads.clear(); 470 DAG.setRoot(Root); 471 return Root; 472 } 473 474 /// getControlRoot - Similar to getRoot, but instead of flushing all the 475 /// PendingLoad items, flush all the PendingExports items. It is necessary 476 /// to do this before emitting a terminator instruction. 477 /// 478 SDOperand getControlRoot() { 479 SDOperand Root = DAG.getRoot(); 480 481 if (PendingExports.empty()) 482 return Root; 483 484 // Turn all of the CopyToReg chains into one factored node. 485 if (Root.getOpcode() != ISD::EntryToken) { 486 unsigned i = 0, e = PendingExports.size(); 487 for (; i != e; ++i) { 488 assert(PendingExports[i].Val->getNumOperands() > 1); 489 if (PendingExports[i].Val->getOperand(0) == Root) 490 break; // Don't add the root if we already indirectly depend on it. 491 } 492 493 if (i == e) 494 PendingExports.push_back(Root); 495 } 496 497 Root = DAG.getNode(ISD::TokenFactor, MVT::Other, 498 &PendingExports[0], 499 PendingExports.size()); 500 PendingExports.clear(); 501 DAG.setRoot(Root); 502 return Root; 503 } 504 505 void CopyValueToVirtualRegister(Value *V, unsigned Reg); 506 507 void visit(Instruction &I) { visit(I.getOpcode(), I); } 508 509 void visit(unsigned Opcode, User &I) { 510 // Note: this doesn't use InstVisitor, because it has to work with 511 // ConstantExpr's in addition to instructions. 512 switch (Opcode) { 513 default: assert(0 && "Unknown instruction type encountered!"); 514 abort(); 515 // Build the switch statement using the Instruction.def file. 516#define HANDLE_INST(NUM, OPCODE, CLASS) \ 517 case Instruction::OPCODE:return visit##OPCODE((CLASS&)I); 518#include "llvm/Instruction.def" 519 } 520 } 521 522 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; } 523 524 SDOperand getLoadFrom(const Type *Ty, SDOperand Ptr, 525 const Value *SV, SDOperand Root, 526 bool isVolatile, unsigned Alignment); 527 528 SDOperand getValue(const Value *V); 529 530 void setValue(const Value *V, SDOperand NewN) { 531 SDOperand &N = NodeMap[V]; 532 assert(N.Val == 0 && "Already set a value for this node!"); 533 N = NewN; 534 } 535 536 void GetRegistersForValue(SDISelAsmOperandInfo &OpInfo, bool HasEarlyClobber, 537 std::set<unsigned> &OutputRegs, 538 std::set<unsigned> &InputRegs); 539 540 void FindMergedConditions(Value *Cond, MachineBasicBlock *TBB, 541 MachineBasicBlock *FBB, MachineBasicBlock *CurBB, 542 unsigned Opc); 543 bool isExportableFromCurrentBlock(Value *V, const BasicBlock *FromBB); 544 void ExportFromCurrentBlock(Value *V); 545 void LowerCallTo(CallSite CS, SDOperand Callee, bool IsTailCall, 546 MachineBasicBlock *LandingPad = NULL); 547 548 // Terminator instructions. 549 void visitRet(ReturnInst &I); 550 void visitBr(BranchInst &I); 551 void visitSwitch(SwitchInst &I); 552 void visitUnreachable(UnreachableInst &I) { /* noop */ } 553 554 // Helpers for visitSwitch 555 bool handleSmallSwitchRange(CaseRec& CR, 556 CaseRecVector& WorkList, 557 Value* SV, 558 MachineBasicBlock* Default); 559 bool handleJTSwitchCase(CaseRec& CR, 560 CaseRecVector& WorkList, 561 Value* SV, 562 MachineBasicBlock* Default); 563 bool handleBTSplitSwitchCase(CaseRec& CR, 564 CaseRecVector& WorkList, 565 Value* SV, 566 MachineBasicBlock* Default); 567 bool handleBitTestsSwitchCase(CaseRec& CR, 568 CaseRecVector& WorkList, 569 Value* SV, 570 MachineBasicBlock* Default); 571 void visitSwitchCase(SelectionDAGISel::CaseBlock &CB); 572 void visitBitTestHeader(SelectionDAGISel::BitTestBlock &B); 573 void visitBitTestCase(MachineBasicBlock* NextMBB, 574 unsigned Reg, 575 SelectionDAGISel::BitTestCase &B); 576 void visitJumpTable(SelectionDAGISel::JumpTable &JT); 577 void visitJumpTableHeader(SelectionDAGISel::JumpTable &JT, 578 SelectionDAGISel::JumpTableHeader &JTH); 579 580 // These all get lowered before this pass. 581 void visitInvoke(InvokeInst &I); 582 void visitUnwind(UnwindInst &I); 583 584 void visitBinary(User &I, unsigned OpCode); 585 void visitShift(User &I, unsigned Opcode); 586 void visitAdd(User &I) { 587 if (I.getType()->isFPOrFPVector()) 588 visitBinary(I, ISD::FADD); 589 else 590 visitBinary(I, ISD::ADD); 591 } 592 void visitSub(User &I); 593 void visitMul(User &I) { 594 if (I.getType()->isFPOrFPVector()) 595 visitBinary(I, ISD::FMUL); 596 else 597 visitBinary(I, ISD::MUL); 598 } 599 void visitURem(User &I) { visitBinary(I, ISD::UREM); } 600 void visitSRem(User &I) { visitBinary(I, ISD::SREM); } 601 void visitFRem(User &I) { visitBinary(I, ISD::FREM); } 602 void visitUDiv(User &I) { visitBinary(I, ISD::UDIV); } 603 void visitSDiv(User &I) { visitBinary(I, ISD::SDIV); } 604 void visitFDiv(User &I) { visitBinary(I, ISD::FDIV); } 605 void visitAnd (User &I) { visitBinary(I, ISD::AND); } 606 void visitOr (User &I) { visitBinary(I, ISD::OR); } 607 void visitXor (User &I) { visitBinary(I, ISD::XOR); } 608 void visitShl (User &I) { visitShift(I, ISD::SHL); } 609 void visitLShr(User &I) { visitShift(I, ISD::SRL); } 610 void visitAShr(User &I) { visitShift(I, ISD::SRA); } 611 void visitICmp(User &I); 612 void visitFCmp(User &I); 613 // Visit the conversion instructions 614 void visitTrunc(User &I); 615 void visitZExt(User &I); 616 void visitSExt(User &I); 617 void visitFPTrunc(User &I); 618 void visitFPExt(User &I); 619 void visitFPToUI(User &I); 620 void visitFPToSI(User &I); 621 void visitUIToFP(User &I); 622 void visitSIToFP(User &I); 623 void visitPtrToInt(User &I); 624 void visitIntToPtr(User &I); 625 void visitBitCast(User &I); 626 627 void visitExtractElement(User &I); 628 void visitInsertElement(User &I); 629 void visitShuffleVector(User &I); 630 631 void visitGetElementPtr(User &I); 632 void visitSelect(User &I); 633 634 void visitMalloc(MallocInst &I); 635 void visitFree(FreeInst &I); 636 void visitAlloca(AllocaInst &I); 637 void visitLoad(LoadInst &I); 638 void visitStore(StoreInst &I); 639 void visitPHI(PHINode &I) { } // PHI nodes are handled specially. 640 void visitCall(CallInst &I); 641 void visitInlineAsm(CallSite CS); 642 const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic); 643 void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic); 644 645 void visitVAStart(CallInst &I); 646 void visitVAArg(VAArgInst &I); 647 void visitVAEnd(CallInst &I); 648 void visitVACopy(CallInst &I); 649 650 void visitGetResult(GetResultInst &I); 651 652 void visitUserOp1(Instruction &I) { 653 assert(0 && "UserOp1 should not exist at instruction selection time!"); 654 abort(); 655 } 656 void visitUserOp2(Instruction &I) { 657 assert(0 && "UserOp2 should not exist at instruction selection time!"); 658 abort(); 659 } 660}; 661} // end namespace llvm 662 663 664/// getCopyFromParts - Create a value that contains the specified legal parts 665/// combined into the value they represent. If the parts combine to a type 666/// larger then ValueVT then AssertOp can be used to specify whether the extra 667/// bits are known to be zero (ISD::AssertZext) or sign extended from ValueVT 668/// (ISD::AssertSext). 669static SDOperand getCopyFromParts(SelectionDAG &DAG, 670 const SDOperand *Parts, 671 unsigned NumParts, 672 MVT::ValueType PartVT, 673 MVT::ValueType ValueVT, 674 ISD::NodeType AssertOp = ISD::DELETED_NODE) { 675 assert(NumParts > 0 && "No parts to assemble!"); 676 TargetLowering &TLI = DAG.getTargetLoweringInfo(); 677 SDOperand Val = Parts[0]; 678 679 if (NumParts > 1) { 680 // Assemble the value from multiple parts. 681 if (!MVT::isVector(ValueVT)) { 682 unsigned PartBits = MVT::getSizeInBits(PartVT); 683 unsigned ValueBits = MVT::getSizeInBits(ValueVT); 684 685 // Assemble the power of 2 part. 686 unsigned RoundParts = NumParts & (NumParts - 1) ? 687 1 << Log2_32(NumParts) : NumParts; 688 unsigned RoundBits = PartBits * RoundParts; 689 MVT::ValueType RoundVT = RoundBits == ValueBits ? 690 ValueVT : MVT::getIntegerType(RoundBits); 691 SDOperand Lo, Hi; 692 693 if (RoundParts > 2) { 694 MVT::ValueType HalfVT = MVT::getIntegerType(RoundBits/2); 695 Lo = getCopyFromParts(DAG, Parts, RoundParts/2, PartVT, HalfVT); 696 Hi = getCopyFromParts(DAG, Parts+RoundParts/2, RoundParts/2, 697 PartVT, HalfVT); 698 } else { 699 Lo = Parts[0]; 700 Hi = Parts[1]; 701 } 702 if (TLI.isBigEndian()) 703 std::swap(Lo, Hi); 704 Val = DAG.getNode(ISD::BUILD_PAIR, RoundVT, Lo, Hi); 705 706 if (RoundParts < NumParts) { 707 // Assemble the trailing non-power-of-2 part. 708 unsigned OddParts = NumParts - RoundParts; 709 MVT::ValueType OddVT = MVT::getIntegerType(OddParts * PartBits); 710 Hi = getCopyFromParts(DAG, Parts+RoundParts, OddParts, PartVT, OddVT); 711 712 // Combine the round and odd parts. 713 Lo = Val; 714 if (TLI.isBigEndian()) 715 std::swap(Lo, Hi); 716 MVT::ValueType TotalVT = MVT::getIntegerType(NumParts * PartBits); 717 Hi = DAG.getNode(ISD::ANY_EXTEND, TotalVT, Hi); 718 Hi = DAG.getNode(ISD::SHL, TotalVT, Hi, 719 DAG.getConstant(MVT::getSizeInBits(Lo.getValueType()), 720 TLI.getShiftAmountTy())); 721 Lo = DAG.getNode(ISD::ZERO_EXTEND, TotalVT, Lo); 722 Val = DAG.getNode(ISD::OR, TotalVT, Lo, Hi); 723 } 724 } else { 725 // Handle a multi-element vector. 726 MVT::ValueType IntermediateVT, RegisterVT; 727 unsigned NumIntermediates; 728 unsigned NumRegs = 729 TLI.getVectorTypeBreakdown(ValueVT, IntermediateVT, NumIntermediates, 730 RegisterVT); 731 732 assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!"); 733 assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!"); 734 assert(RegisterVT == Parts[0].getValueType() && 735 "Part type doesn't match part!"); 736 737 // Assemble the parts into intermediate operands. 738 SmallVector<SDOperand, 8> Ops(NumIntermediates); 739 if (NumIntermediates == NumParts) { 740 // If the register was not expanded, truncate or copy the value, 741 // as appropriate. 742 for (unsigned i = 0; i != NumParts; ++i) 743 Ops[i] = getCopyFromParts(DAG, &Parts[i], 1, 744 PartVT, IntermediateVT); 745 } else if (NumParts > 0) { 746 // If the intermediate type was expanded, build the intermediate operands 747 // from the parts. 748 assert(NumParts % NumIntermediates == 0 && 749 "Must expand into a divisible number of parts!"); 750 unsigned Factor = NumParts / NumIntermediates; 751 for (unsigned i = 0; i != NumIntermediates; ++i) 752 Ops[i] = getCopyFromParts(DAG, &Parts[i * Factor], Factor, 753 PartVT, IntermediateVT); 754 } 755 756 // Build a vector with BUILD_VECTOR or CONCAT_VECTORS from the intermediate 757 // operands. 758 Val = DAG.getNode(MVT::isVector(IntermediateVT) ? 759 ISD::CONCAT_VECTORS : ISD::BUILD_VECTOR, 760 ValueVT, &Ops[0], NumIntermediates); 761 } 762 } 763 764 // There is now one part, held in Val. Correct it to match ValueVT. 765 PartVT = Val.getValueType(); 766 767 if (PartVT == ValueVT) 768 return Val; 769 770 if (MVT::isVector(PartVT)) { 771 assert(MVT::isVector(ValueVT) && "Unknown vector conversion!"); 772 return DAG.getNode(ISD::BIT_CONVERT, ValueVT, Val); 773 } 774 775 if (MVT::isVector(ValueVT)) { 776 assert(MVT::getVectorElementType(ValueVT) == PartVT && 777 MVT::getVectorNumElements(ValueVT) == 1 && 778 "Only trivial scalar-to-vector conversions should get here!"); 779 return DAG.getNode(ISD::BUILD_VECTOR, ValueVT, Val); 780 } 781 782 if (MVT::isInteger(PartVT) && 783 MVT::isInteger(ValueVT)) { 784 if (MVT::getSizeInBits(ValueVT) < MVT::getSizeInBits(PartVT)) { 785 // For a truncate, see if we have any information to 786 // indicate whether the truncated bits will always be 787 // zero or sign-extension. 788 if (AssertOp != ISD::DELETED_NODE) 789 Val = DAG.getNode(AssertOp, PartVT, Val, 790 DAG.getValueType(ValueVT)); 791 return DAG.getNode(ISD::TRUNCATE, ValueVT, Val); 792 } else { 793 return DAG.getNode(ISD::ANY_EXTEND, ValueVT, Val); 794 } 795 } 796 797 if (MVT::isFloatingPoint(PartVT) && MVT::isFloatingPoint(ValueVT)) { 798 if (ValueVT < Val.getValueType()) 799 // FP_ROUND's are always exact here. 800 return DAG.getNode(ISD::FP_ROUND, ValueVT, Val, 801 DAG.getIntPtrConstant(1)); 802 return DAG.getNode(ISD::FP_EXTEND, ValueVT, Val); 803 } 804 805 if (MVT::getSizeInBits(PartVT) == MVT::getSizeInBits(ValueVT)) 806 return DAG.getNode(ISD::BIT_CONVERT, ValueVT, Val); 807 808 assert(0 && "Unknown mismatch!"); 809 return SDOperand(); 810} 811 812/// getCopyToParts - Create a series of nodes that contain the specified value 813/// split into legal parts. If the parts contain more bits than Val, then, for 814/// integers, ExtendKind can be used to specify how to generate the extra bits. 815static void getCopyToParts(SelectionDAG &DAG, 816 SDOperand Val, 817 SDOperand *Parts, 818 unsigned NumParts, 819 MVT::ValueType PartVT, 820 ISD::NodeType ExtendKind = ISD::ANY_EXTEND) { 821 TargetLowering &TLI = DAG.getTargetLoweringInfo(); 822 MVT::ValueType PtrVT = TLI.getPointerTy(); 823 MVT::ValueType ValueVT = Val.getValueType(); 824 unsigned PartBits = MVT::getSizeInBits(PartVT); 825 assert(TLI.isTypeLegal(PartVT) && "Copying to an illegal type!"); 826 827 if (!NumParts) 828 return; 829 830 if (!MVT::isVector(ValueVT)) { 831 if (PartVT == ValueVT) { 832 assert(NumParts == 1 && "No-op copy with multiple parts!"); 833 Parts[0] = Val; 834 return; 835 } 836 837 if (NumParts * PartBits > MVT::getSizeInBits(ValueVT)) { 838 // If the parts cover more bits than the value has, promote the value. 839 if (MVT::isFloatingPoint(PartVT) && MVT::isFloatingPoint(ValueVT)) { 840 assert(NumParts == 1 && "Do not know what to promote to!"); 841 Val = DAG.getNode(ISD::FP_EXTEND, PartVT, Val); 842 } else if (MVT::isInteger(PartVT) && MVT::isInteger(ValueVT)) { 843 ValueVT = MVT::getIntegerType(NumParts * PartBits); 844 Val = DAG.getNode(ExtendKind, ValueVT, Val); 845 } else { 846 assert(0 && "Unknown mismatch!"); 847 } 848 } else if (PartBits == MVT::getSizeInBits(ValueVT)) { 849 // Different types of the same size. 850 assert(NumParts == 1 && PartVT != ValueVT); 851 Val = DAG.getNode(ISD::BIT_CONVERT, PartVT, Val); 852 } else if (NumParts * PartBits < MVT::getSizeInBits(ValueVT)) { 853 // If the parts cover less bits than value has, truncate the value. 854 if (MVT::isInteger(PartVT) && MVT::isInteger(ValueVT)) { 855 ValueVT = MVT::getIntegerType(NumParts * PartBits); 856 Val = DAG.getNode(ISD::TRUNCATE, ValueVT, Val); 857 } else { 858 assert(0 && "Unknown mismatch!"); 859 } 860 } 861 862 // The value may have changed - recompute ValueVT. 863 ValueVT = Val.getValueType(); 864 assert(NumParts * PartBits == MVT::getSizeInBits(ValueVT) && 865 "Failed to tile the value with PartVT!"); 866 867 if (NumParts == 1) { 868 assert(PartVT == ValueVT && "Type conversion failed!"); 869 Parts[0] = Val; 870 return; 871 } 872 873 // Expand the value into multiple parts. 874 if (NumParts & (NumParts - 1)) { 875 // The number of parts is not a power of 2. Split off and copy the tail. 876 assert(MVT::isInteger(PartVT) && MVT::isInteger(ValueVT) && 877 "Do not know what to expand to!"); 878 unsigned RoundParts = 1 << Log2_32(NumParts); 879 unsigned RoundBits = RoundParts * PartBits; 880 unsigned OddParts = NumParts - RoundParts; 881 SDOperand OddVal = DAG.getNode(ISD::SRL, ValueVT, Val, 882 DAG.getConstant(RoundBits, 883 TLI.getShiftAmountTy())); 884 getCopyToParts(DAG, OddVal, Parts + RoundParts, OddParts, PartVT); 885 if (TLI.isBigEndian()) 886 // The odd parts were reversed by getCopyToParts - unreverse them. 887 std::reverse(Parts + RoundParts, Parts + NumParts); 888 NumParts = RoundParts; 889 ValueVT = MVT::getIntegerType(NumParts * PartBits); 890 Val = DAG.getNode(ISD::TRUNCATE, ValueVT, Val); 891 } 892 893 // The number of parts is a power of 2. Repeatedly bisect the value using 894 // EXTRACT_ELEMENT. 895 Parts[0] = DAG.getNode(ISD::BIT_CONVERT, 896 MVT::getIntegerType(MVT::getSizeInBits(ValueVT)), 897 Val); 898 for (unsigned StepSize = NumParts; StepSize > 1; StepSize /= 2) { 899 for (unsigned i = 0; i < NumParts; i += StepSize) { 900 unsigned ThisBits = StepSize * PartBits / 2; 901 MVT::ValueType ThisVT = MVT::getIntegerType (ThisBits); 902 SDOperand &Part0 = Parts[i]; 903 SDOperand &Part1 = Parts[i+StepSize/2]; 904 905 Part1 = DAG.getNode(ISD::EXTRACT_ELEMENT, ThisVT, Part0, 906 DAG.getConstant(1, PtrVT)); 907 Part0 = DAG.getNode(ISD::EXTRACT_ELEMENT, ThisVT, Part0, 908 DAG.getConstant(0, PtrVT)); 909 910 if (ThisBits == PartBits && ThisVT != PartVT) { 911 Part0 = DAG.getNode(ISD::BIT_CONVERT, PartVT, Part0); 912 Part1 = DAG.getNode(ISD::BIT_CONVERT, PartVT, Part1); 913 } 914 } 915 } 916 917 if (TLI.isBigEndian()) 918 std::reverse(Parts, Parts + NumParts); 919 920 return; 921 } 922 923 // Vector ValueVT. 924 if (NumParts == 1) { 925 if (PartVT != ValueVT) { 926 if (MVT::isVector(PartVT)) { 927 Val = DAG.getNode(ISD::BIT_CONVERT, PartVT, Val); 928 } else { 929 assert(MVT::getVectorElementType(ValueVT) == PartVT && 930 MVT::getVectorNumElements(ValueVT) == 1 && 931 "Only trivial vector-to-scalar conversions should get here!"); 932 Val = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, PartVT, Val, 933 DAG.getConstant(0, PtrVT)); 934 } 935 } 936 937 Parts[0] = Val; 938 return; 939 } 940 941 // Handle a multi-element vector. 942 MVT::ValueType IntermediateVT, RegisterVT; 943 unsigned NumIntermediates; 944 unsigned NumRegs = 945 DAG.getTargetLoweringInfo() 946 .getVectorTypeBreakdown(ValueVT, IntermediateVT, NumIntermediates, 947 RegisterVT); 948 unsigned NumElements = MVT::getVectorNumElements(ValueVT); 949 950 assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!"); 951 assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!"); 952 953 // Split the vector into intermediate operands. 954 SmallVector<SDOperand, 8> Ops(NumIntermediates); 955 for (unsigned i = 0; i != NumIntermediates; ++i) 956 if (MVT::isVector(IntermediateVT)) 957 Ops[i] = DAG.getNode(ISD::EXTRACT_SUBVECTOR, 958 IntermediateVT, Val, 959 DAG.getConstant(i * (NumElements / NumIntermediates), 960 PtrVT)); 961 else 962 Ops[i] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, 963 IntermediateVT, Val, 964 DAG.getConstant(i, PtrVT)); 965 966 // Split the intermediate operands into legal parts. 967 if (NumParts == NumIntermediates) { 968 // If the register was not expanded, promote or copy the value, 969 // as appropriate. 970 for (unsigned i = 0; i != NumParts; ++i) 971 getCopyToParts(DAG, Ops[i], &Parts[i], 1, PartVT); 972 } else if (NumParts > 0) { 973 // If the intermediate type was expanded, split each the value into 974 // legal parts. 975 assert(NumParts % NumIntermediates == 0 && 976 "Must expand into a divisible number of parts!"); 977 unsigned Factor = NumParts / NumIntermediates; 978 for (unsigned i = 0; i != NumIntermediates; ++i) 979 getCopyToParts(DAG, Ops[i], &Parts[i * Factor], Factor, PartVT); 980 } 981} 982 983 984SDOperand SelectionDAGLowering::getValue(const Value *V) { 985 SDOperand &N = NodeMap[V]; 986 if (N.Val) return N; 987 988 const Type *VTy = V->getType(); 989 MVT::ValueType VT = TLI.getValueType(VTy); 990 if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) { 991 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 992 visit(CE->getOpcode(), *CE); 993 SDOperand N1 = NodeMap[V]; 994 assert(N1.Val && "visit didn't populate the ValueMap!"); 995 return N1; 996 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) { 997 return N = DAG.getGlobalAddress(GV, VT); 998 } else if (isa<ConstantPointerNull>(C)) { 999 return N = DAG.getConstant(0, TLI.getPointerTy()); 1000 } else if (isa<UndefValue>(C)) { 1001 if (!isa<VectorType>(VTy)) 1002 return N = DAG.getNode(ISD::UNDEF, VT); 1003 1004 // Create a BUILD_VECTOR of undef nodes. 1005 const VectorType *PTy = cast<VectorType>(VTy); 1006 unsigned NumElements = PTy->getNumElements(); 1007 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType()); 1008 1009 SmallVector<SDOperand, 8> Ops; 1010 Ops.assign(NumElements, DAG.getNode(ISD::UNDEF, PVT)); 1011 1012 // Create a VConstant node with generic Vector type. 1013 MVT::ValueType VT = MVT::getVectorType(PVT, NumElements); 1014 return N = DAG.getNode(ISD::BUILD_VECTOR, VT, 1015 &Ops[0], Ops.size()); 1016 } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) { 1017 return N = DAG.getConstantFP(CFP->getValueAPF(), VT); 1018 } else if (const VectorType *PTy = dyn_cast<VectorType>(VTy)) { 1019 unsigned NumElements = PTy->getNumElements(); 1020 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType()); 1021 1022 // Now that we know the number and type of the elements, push a 1023 // Constant or ConstantFP node onto the ops list for each element of 1024 // the vector constant. 1025 SmallVector<SDOperand, 8> Ops; 1026 if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) { 1027 for (unsigned i = 0; i != NumElements; ++i) 1028 Ops.push_back(getValue(CP->getOperand(i))); 1029 } else { 1030 assert(isa<ConstantAggregateZero>(C) && "Unknown vector constant!"); 1031 SDOperand Op; 1032 if (MVT::isFloatingPoint(PVT)) 1033 Op = DAG.getConstantFP(0, PVT); 1034 else 1035 Op = DAG.getConstant(0, PVT); 1036 Ops.assign(NumElements, Op); 1037 } 1038 1039 // Create a BUILD_VECTOR node. 1040 MVT::ValueType VT = MVT::getVectorType(PVT, NumElements); 1041 return NodeMap[V] = DAG.getNode(ISD::BUILD_VECTOR, VT, &Ops[0], 1042 Ops.size()); 1043 } else { 1044 // Canonicalize all constant ints to be unsigned. 1045 return N = DAG.getConstant(cast<ConstantInt>(C)->getValue(),VT); 1046 } 1047 } 1048 1049 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 1050 std::map<const AllocaInst*, int>::iterator SI = 1051 FuncInfo.StaticAllocaMap.find(AI); 1052 if (SI != FuncInfo.StaticAllocaMap.end()) 1053 return DAG.getFrameIndex(SI->second, TLI.getPointerTy()); 1054 } 1055 1056 unsigned InReg = FuncInfo.ValueMap[V]; 1057 assert(InReg && "Value not in map!"); 1058 1059 MVT::ValueType RegisterVT = TLI.getRegisterType(VT); 1060 unsigned NumRegs = TLI.getNumRegisters(VT); 1061 1062 std::vector<unsigned> Regs(NumRegs); 1063 for (unsigned i = 0; i != NumRegs; ++i) 1064 Regs[i] = InReg + i; 1065 1066 RegsForValue RFV(Regs, RegisterVT, VT); 1067 SDOperand Chain = DAG.getEntryNode(); 1068 1069 return RFV.getCopyFromRegs(DAG, Chain, NULL); 1070} 1071 1072 1073void SelectionDAGLowering::visitRet(ReturnInst &I) { 1074 if (I.getNumOperands() == 0) { 1075 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getControlRoot())); 1076 return; 1077 } 1078 SmallVector<SDOperand, 8> NewValues; 1079 NewValues.push_back(getControlRoot()); 1080 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 1081 SDOperand RetOp = getValue(I.getOperand(i)); 1082 MVT::ValueType VT = RetOp.getValueType(); 1083 1084 // FIXME: C calling convention requires the return type to be promoted to 1085 // at least 32-bit. But this is not necessary for non-C calling conventions. 1086 if (MVT::isInteger(VT)) { 1087 MVT::ValueType MinVT = TLI.getRegisterType(MVT::i32); 1088 if (MVT::getSizeInBits(VT) < MVT::getSizeInBits(MinVT)) 1089 VT = MinVT; 1090 } 1091 1092 unsigned NumParts = TLI.getNumRegisters(VT); 1093 MVT::ValueType PartVT = TLI.getRegisterType(VT); 1094 SmallVector<SDOperand, 4> Parts(NumParts); 1095 ISD::NodeType ExtendKind = ISD::ANY_EXTEND; 1096 1097 const Function *F = I.getParent()->getParent(); 1098 if (F->paramHasAttr(0, ParamAttr::SExt)) 1099 ExtendKind = ISD::SIGN_EXTEND; 1100 else if (F->paramHasAttr(0, ParamAttr::ZExt)) 1101 ExtendKind = ISD::ZERO_EXTEND; 1102 1103 getCopyToParts(DAG, RetOp, &Parts[0], NumParts, PartVT, ExtendKind); 1104 1105 for (unsigned i = 0; i < NumParts; ++i) { 1106 NewValues.push_back(Parts[i]); 1107 NewValues.push_back(DAG.getArgFlags(ISD::ArgFlagsTy())); 1108 } 1109 } 1110 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, 1111 &NewValues[0], NewValues.size())); 1112} 1113 1114/// ExportFromCurrentBlock - If this condition isn't known to be exported from 1115/// the current basic block, add it to ValueMap now so that we'll get a 1116/// CopyTo/FromReg. 1117void SelectionDAGLowering::ExportFromCurrentBlock(Value *V) { 1118 // No need to export constants. 1119 if (!isa<Instruction>(V) && !isa<Argument>(V)) return; 1120 1121 // Already exported? 1122 if (FuncInfo.isExportedInst(V)) return; 1123 1124 unsigned Reg = FuncInfo.InitializeRegForValue(V); 1125 CopyValueToVirtualRegister(V, Reg); 1126} 1127 1128bool SelectionDAGLowering::isExportableFromCurrentBlock(Value *V, 1129 const BasicBlock *FromBB) { 1130 // The operands of the setcc have to be in this block. We don't know 1131 // how to export them from some other block. 1132 if (Instruction *VI = dyn_cast<Instruction>(V)) { 1133 // Can export from current BB. 1134 if (VI->getParent() == FromBB) 1135 return true; 1136 1137 // Is already exported, noop. 1138 return FuncInfo.isExportedInst(V); 1139 } 1140 1141 // If this is an argument, we can export it if the BB is the entry block or 1142 // if it is already exported. 1143 if (isa<Argument>(V)) { 1144 if (FromBB == &FromBB->getParent()->getEntryBlock()) 1145 return true; 1146 1147 // Otherwise, can only export this if it is already exported. 1148 return FuncInfo.isExportedInst(V); 1149 } 1150 1151 // Otherwise, constants can always be exported. 1152 return true; 1153} 1154 1155static bool InBlock(const Value *V, const BasicBlock *BB) { 1156 if (const Instruction *I = dyn_cast<Instruction>(V)) 1157 return I->getParent() == BB; 1158 return true; 1159} 1160 1161/// FindMergedConditions - If Cond is an expression like 1162void SelectionDAGLowering::FindMergedConditions(Value *Cond, 1163 MachineBasicBlock *TBB, 1164 MachineBasicBlock *FBB, 1165 MachineBasicBlock *CurBB, 1166 unsigned Opc) { 1167 // If this node is not part of the or/and tree, emit it as a branch. 1168 Instruction *BOp = dyn_cast<Instruction>(Cond); 1169 1170 if (!BOp || !(isa<BinaryOperator>(BOp) || isa<CmpInst>(BOp)) || 1171 (unsigned)BOp->getOpcode() != Opc || !BOp->hasOneUse() || 1172 BOp->getParent() != CurBB->getBasicBlock() || 1173 !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) || 1174 !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) { 1175 const BasicBlock *BB = CurBB->getBasicBlock(); 1176 1177 // If the leaf of the tree is a comparison, merge the condition into 1178 // the caseblock. 1179 if ((isa<ICmpInst>(Cond) || isa<FCmpInst>(Cond)) && 1180 // The operands of the cmp have to be in this block. We don't know 1181 // how to export them from some other block. If this is the first block 1182 // of the sequence, no exporting is needed. 1183 (CurBB == CurMBB || 1184 (isExportableFromCurrentBlock(BOp->getOperand(0), BB) && 1185 isExportableFromCurrentBlock(BOp->getOperand(1), BB)))) { 1186 BOp = cast<Instruction>(Cond); 1187 ISD::CondCode Condition; 1188 if (ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) { 1189 switch (IC->getPredicate()) { 1190 default: assert(0 && "Unknown icmp predicate opcode!"); 1191 case ICmpInst::ICMP_EQ: Condition = ISD::SETEQ; break; 1192 case ICmpInst::ICMP_NE: Condition = ISD::SETNE; break; 1193 case ICmpInst::ICMP_SLE: Condition = ISD::SETLE; break; 1194 case ICmpInst::ICMP_ULE: Condition = ISD::SETULE; break; 1195 case ICmpInst::ICMP_SGE: Condition = ISD::SETGE; break; 1196 case ICmpInst::ICMP_UGE: Condition = ISD::SETUGE; break; 1197 case ICmpInst::ICMP_SLT: Condition = ISD::SETLT; break; 1198 case ICmpInst::ICMP_ULT: Condition = ISD::SETULT; break; 1199 case ICmpInst::ICMP_SGT: Condition = ISD::SETGT; break; 1200 case ICmpInst::ICMP_UGT: Condition = ISD::SETUGT; break; 1201 } 1202 } else if (FCmpInst *FC = dyn_cast<FCmpInst>(Cond)) { 1203 ISD::CondCode FPC, FOC; 1204 switch (FC->getPredicate()) { 1205 default: assert(0 && "Unknown fcmp predicate opcode!"); 1206 case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break; 1207 case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break; 1208 case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break; 1209 case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break; 1210 case FCmpInst::FCMP_OLT: FOC = ISD::SETLT; FPC = ISD::SETOLT; break; 1211 case FCmpInst::FCMP_OLE: FOC = ISD::SETLE; FPC = ISD::SETOLE; break; 1212 case FCmpInst::FCMP_ONE: FOC = ISD::SETNE; FPC = ISD::SETONE; break; 1213 case FCmpInst::FCMP_ORD: FOC = ISD::SETEQ; FPC = ISD::SETO; break; 1214 case FCmpInst::FCMP_UNO: FOC = ISD::SETNE; FPC = ISD::SETUO; break; 1215 case FCmpInst::FCMP_UEQ: FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break; 1216 case FCmpInst::FCMP_UGT: FOC = ISD::SETGT; FPC = ISD::SETUGT; break; 1217 case FCmpInst::FCMP_UGE: FOC = ISD::SETGE; FPC = ISD::SETUGE; break; 1218 case FCmpInst::FCMP_ULT: FOC = ISD::SETLT; FPC = ISD::SETULT; break; 1219 case FCmpInst::FCMP_ULE: FOC = ISD::SETLE; FPC = ISD::SETULE; break; 1220 case FCmpInst::FCMP_UNE: FOC = ISD::SETNE; FPC = ISD::SETUNE; break; 1221 case FCmpInst::FCMP_TRUE: FOC = FPC = ISD::SETTRUE; break; 1222 } 1223 if (FiniteOnlyFPMath()) 1224 Condition = FOC; 1225 else 1226 Condition = FPC; 1227 } else { 1228 Condition = ISD::SETEQ; // silence warning. 1229 assert(0 && "Unknown compare instruction"); 1230 } 1231 1232 SelectionDAGISel::CaseBlock CB(Condition, BOp->getOperand(0), 1233 BOp->getOperand(1), NULL, TBB, FBB, CurBB); 1234 SwitchCases.push_back(CB); 1235 return; 1236 } 1237 1238 // Create a CaseBlock record representing this branch. 1239 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(), 1240 NULL, TBB, FBB, CurBB); 1241 SwitchCases.push_back(CB); 1242 return; 1243 } 1244 1245 1246 // Create TmpBB after CurBB. 1247 MachineFunction::iterator BBI = CurBB; 1248 MachineBasicBlock *TmpBB = new MachineBasicBlock(CurBB->getBasicBlock()); 1249 CurBB->getParent()->getBasicBlockList().insert(++BBI, TmpBB); 1250 1251 if (Opc == Instruction::Or) { 1252 // Codegen X | Y as: 1253 // jmp_if_X TBB 1254 // jmp TmpBB 1255 // TmpBB: 1256 // jmp_if_Y TBB 1257 // jmp FBB 1258 // 1259 1260 // Emit the LHS condition. 1261 FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, Opc); 1262 1263 // Emit the RHS condition into TmpBB. 1264 FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc); 1265 } else { 1266 assert(Opc == Instruction::And && "Unknown merge op!"); 1267 // Codegen X & Y as: 1268 // jmp_if_X TmpBB 1269 // jmp FBB 1270 // TmpBB: 1271 // jmp_if_Y TBB 1272 // jmp FBB 1273 // 1274 // This requires creation of TmpBB after CurBB. 1275 1276 // Emit the LHS condition. 1277 FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, Opc); 1278 1279 // Emit the RHS condition into TmpBB. 1280 FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc); 1281 } 1282} 1283 1284/// If the set of cases should be emitted as a series of branches, return true. 1285/// If we should emit this as a bunch of and/or'd together conditions, return 1286/// false. 1287static bool 1288ShouldEmitAsBranches(const std::vector<SelectionDAGISel::CaseBlock> &Cases) { 1289 if (Cases.size() != 2) return true; 1290 1291 // If this is two comparisons of the same values or'd or and'd together, they 1292 // will get folded into a single comparison, so don't emit two blocks. 1293 if ((Cases[0].CmpLHS == Cases[1].CmpLHS && 1294 Cases[0].CmpRHS == Cases[1].CmpRHS) || 1295 (Cases[0].CmpRHS == Cases[1].CmpLHS && 1296 Cases[0].CmpLHS == Cases[1].CmpRHS)) { 1297 return false; 1298 } 1299 1300 return true; 1301} 1302 1303void SelectionDAGLowering::visitBr(BranchInst &I) { 1304 // Update machine-CFG edges. 1305 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)]; 1306 1307 // Figure out which block is immediately after the current one. 1308 MachineBasicBlock *NextBlock = 0; 1309 MachineFunction::iterator BBI = CurMBB; 1310 if (++BBI != CurMBB->getParent()->end()) 1311 NextBlock = BBI; 1312 1313 if (I.isUnconditional()) { 1314 // If this is not a fall-through branch, emit the branch. 1315 if (Succ0MBB != NextBlock) 1316 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getControlRoot(), 1317 DAG.getBasicBlock(Succ0MBB))); 1318 1319 // Update machine-CFG edges. 1320 CurMBB->addSuccessor(Succ0MBB); 1321 return; 1322 } 1323 1324 // If this condition is one of the special cases we handle, do special stuff 1325 // now. 1326 Value *CondVal = I.getCondition(); 1327 MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)]; 1328 1329 // If this is a series of conditions that are or'd or and'd together, emit 1330 // this as a sequence of branches instead of setcc's with and/or operations. 1331 // For example, instead of something like: 1332 // cmp A, B 1333 // C = seteq 1334 // cmp D, E 1335 // F = setle 1336 // or C, F 1337 // jnz foo 1338 // Emit: 1339 // cmp A, B 1340 // je foo 1341 // cmp D, E 1342 // jle foo 1343 // 1344 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(CondVal)) { 1345 if (BOp->hasOneUse() && 1346 (BOp->getOpcode() == Instruction::And || 1347 BOp->getOpcode() == Instruction::Or)) { 1348 FindMergedConditions(BOp, Succ0MBB, Succ1MBB, CurMBB, BOp->getOpcode()); 1349 // If the compares in later blocks need to use values not currently 1350 // exported from this block, export them now. This block should always 1351 // be the first entry. 1352 assert(SwitchCases[0].ThisBB == CurMBB && "Unexpected lowering!"); 1353 1354 // Allow some cases to be rejected. 1355 if (ShouldEmitAsBranches(SwitchCases)) { 1356 for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) { 1357 ExportFromCurrentBlock(SwitchCases[i].CmpLHS); 1358 ExportFromCurrentBlock(SwitchCases[i].CmpRHS); 1359 } 1360 1361 // Emit the branch for this block. 1362 visitSwitchCase(SwitchCases[0]); 1363 SwitchCases.erase(SwitchCases.begin()); 1364 return; 1365 } 1366 1367 // Okay, we decided not to do this, remove any inserted MBB's and clear 1368 // SwitchCases. 1369 for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) 1370 CurMBB->getParent()->getBasicBlockList().erase(SwitchCases[i].ThisBB); 1371 1372 SwitchCases.clear(); 1373 } 1374 } 1375 1376 // Create a CaseBlock record representing this branch. 1377 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, CondVal, ConstantInt::getTrue(), 1378 NULL, Succ0MBB, Succ1MBB, CurMBB); 1379 // Use visitSwitchCase to actually insert the fast branch sequence for this 1380 // cond branch. 1381 visitSwitchCase(CB); 1382} 1383 1384/// visitSwitchCase - Emits the necessary code to represent a single node in 1385/// the binary search tree resulting from lowering a switch instruction. 1386void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) { 1387 SDOperand Cond; 1388 SDOperand CondLHS = getValue(CB.CmpLHS); 1389 1390 // Build the setcc now. 1391 if (CB.CmpMHS == NULL) { 1392 // Fold "(X == true)" to X and "(X == false)" to !X to 1393 // handle common cases produced by branch lowering. 1394 if (CB.CmpRHS == ConstantInt::getTrue() && CB.CC == ISD::SETEQ) 1395 Cond = CondLHS; 1396 else if (CB.CmpRHS == ConstantInt::getFalse() && CB.CC == ISD::SETEQ) { 1397 SDOperand True = DAG.getConstant(1, CondLHS.getValueType()); 1398 Cond = DAG.getNode(ISD::XOR, CondLHS.getValueType(), CondLHS, True); 1399 } else 1400 Cond = DAG.getSetCC(MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC); 1401 } else { 1402 assert(CB.CC == ISD::SETLE && "Can handle only LE ranges now"); 1403 1404 uint64_t Low = cast<ConstantInt>(CB.CmpLHS)->getSExtValue(); 1405 uint64_t High = cast<ConstantInt>(CB.CmpRHS)->getSExtValue(); 1406 1407 SDOperand CmpOp = getValue(CB.CmpMHS); 1408 MVT::ValueType VT = CmpOp.getValueType(); 1409 1410 if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) { 1411 Cond = DAG.getSetCC(MVT::i1, CmpOp, DAG.getConstant(High, VT), ISD::SETLE); 1412 } else { 1413 SDOperand SUB = DAG.getNode(ISD::SUB, VT, CmpOp, DAG.getConstant(Low, VT)); 1414 Cond = DAG.getSetCC(MVT::i1, SUB, 1415 DAG.getConstant(High-Low, VT), ISD::SETULE); 1416 } 1417 1418 } 1419 1420 // Set NextBlock to be the MBB immediately after the current one, if any. 1421 // This is used to avoid emitting unnecessary branches to the next block. 1422 MachineBasicBlock *NextBlock = 0; 1423 MachineFunction::iterator BBI = CurMBB; 1424 if (++BBI != CurMBB->getParent()->end()) 1425 NextBlock = BBI; 1426 1427 // If the lhs block is the next block, invert the condition so that we can 1428 // fall through to the lhs instead of the rhs block. 1429 if (CB.TrueBB == NextBlock) { 1430 std::swap(CB.TrueBB, CB.FalseBB); 1431 SDOperand True = DAG.getConstant(1, Cond.getValueType()); 1432 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True); 1433 } 1434 SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, getControlRoot(), Cond, 1435 DAG.getBasicBlock(CB.TrueBB)); 1436 if (CB.FalseBB == NextBlock) 1437 DAG.setRoot(BrCond); 1438 else 1439 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond, 1440 DAG.getBasicBlock(CB.FalseBB))); 1441 // Update successor info 1442 CurMBB->addSuccessor(CB.TrueBB); 1443 CurMBB->addSuccessor(CB.FalseBB); 1444} 1445 1446/// visitJumpTable - Emit JumpTable node in the current MBB 1447void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) { 1448 // Emit the code for the jump table 1449 assert(JT.Reg != -1U && "Should lower JT Header first!"); 1450 MVT::ValueType PTy = TLI.getPointerTy(); 1451 SDOperand Index = DAG.getCopyFromReg(getControlRoot(), JT.Reg, PTy); 1452 SDOperand Table = DAG.getJumpTable(JT.JTI, PTy); 1453 DAG.setRoot(DAG.getNode(ISD::BR_JT, MVT::Other, Index.getValue(1), 1454 Table, Index)); 1455 return; 1456} 1457 1458/// visitJumpTableHeader - This function emits necessary code to produce index 1459/// in the JumpTable from switch case. 1460void SelectionDAGLowering::visitJumpTableHeader(SelectionDAGISel::JumpTable &JT, 1461 SelectionDAGISel::JumpTableHeader &JTH) { 1462 // Subtract the lowest switch case value from the value being switched on 1463 // and conditional branch to default mbb if the result is greater than the 1464 // difference between smallest and largest cases. 1465 SDOperand SwitchOp = getValue(JTH.SValue); 1466 MVT::ValueType VT = SwitchOp.getValueType(); 1467 SDOperand SUB = DAG.getNode(ISD::SUB, VT, SwitchOp, 1468 DAG.getConstant(JTH.First, VT)); 1469 1470 // The SDNode we just created, which holds the value being switched on 1471 // minus the the smallest case value, needs to be copied to a virtual 1472 // register so it can be used as an index into the jump table in a 1473 // subsequent basic block. This value may be smaller or larger than the 1474 // target's pointer type, and therefore require extension or truncating. 1475 if (MVT::getSizeInBits(VT) > MVT::getSizeInBits(TLI.getPointerTy())) 1476 SwitchOp = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), SUB); 1477 else 1478 SwitchOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), SUB); 1479 1480 unsigned JumpTableReg = FuncInfo.MakeReg(TLI.getPointerTy()); 1481 SDOperand CopyTo = DAG.getCopyToReg(getControlRoot(), JumpTableReg, SwitchOp); 1482 JT.Reg = JumpTableReg; 1483 1484 // Emit the range check for the jump table, and branch to the default 1485 // block for the switch statement if the value being switched on exceeds 1486 // the largest case in the switch. 1487 SDOperand CMP = DAG.getSetCC(TLI.getSetCCResultType(SUB), SUB, 1488 DAG.getConstant(JTH.Last-JTH.First,VT), 1489 ISD::SETUGT); 1490 1491 // Set NextBlock to be the MBB immediately after the current one, if any. 1492 // This is used to avoid emitting unnecessary branches to the next block. 1493 MachineBasicBlock *NextBlock = 0; 1494 MachineFunction::iterator BBI = CurMBB; 1495 if (++BBI != CurMBB->getParent()->end()) 1496 NextBlock = BBI; 1497 1498 SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, CMP, 1499 DAG.getBasicBlock(JT.Default)); 1500 1501 if (JT.MBB == NextBlock) 1502 DAG.setRoot(BrCond); 1503 else 1504 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond, 1505 DAG.getBasicBlock(JT.MBB))); 1506 1507 return; 1508} 1509 1510/// visitBitTestHeader - This function emits necessary code to produce value 1511/// suitable for "bit tests" 1512void SelectionDAGLowering::visitBitTestHeader(SelectionDAGISel::BitTestBlock &B) { 1513 // Subtract the minimum value 1514 SDOperand SwitchOp = getValue(B.SValue); 1515 MVT::ValueType VT = SwitchOp.getValueType(); 1516 SDOperand SUB = DAG.getNode(ISD::SUB, VT, SwitchOp, 1517 DAG.getConstant(B.First, VT)); 1518 1519 // Check range 1520 SDOperand RangeCmp = DAG.getSetCC(TLI.getSetCCResultType(SUB), SUB, 1521 DAG.getConstant(B.Range, VT), 1522 ISD::SETUGT); 1523 1524 SDOperand ShiftOp; 1525 if (MVT::getSizeInBits(VT) > MVT::getSizeInBits(TLI.getShiftAmountTy())) 1526 ShiftOp = DAG.getNode(ISD::TRUNCATE, TLI.getShiftAmountTy(), SUB); 1527 else 1528 ShiftOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getShiftAmountTy(), SUB); 1529 1530 // Make desired shift 1531 SDOperand SwitchVal = DAG.getNode(ISD::SHL, TLI.getPointerTy(), 1532 DAG.getConstant(1, TLI.getPointerTy()), 1533 ShiftOp); 1534 1535 unsigned SwitchReg = FuncInfo.MakeReg(TLI.getPointerTy()); 1536 SDOperand CopyTo = DAG.getCopyToReg(getControlRoot(), SwitchReg, SwitchVal); 1537 B.Reg = SwitchReg; 1538 1539 SDOperand BrRange = DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, RangeCmp, 1540 DAG.getBasicBlock(B.Default)); 1541 1542 // Set NextBlock to be the MBB immediately after the current one, if any. 1543 // This is used to avoid emitting unnecessary branches to the next block. 1544 MachineBasicBlock *NextBlock = 0; 1545 MachineFunction::iterator BBI = CurMBB; 1546 if (++BBI != CurMBB->getParent()->end()) 1547 NextBlock = BBI; 1548 1549 MachineBasicBlock* MBB = B.Cases[0].ThisBB; 1550 if (MBB == NextBlock) 1551 DAG.setRoot(BrRange); 1552 else 1553 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, CopyTo, 1554 DAG.getBasicBlock(MBB))); 1555 1556 CurMBB->addSuccessor(B.Default); 1557 CurMBB->addSuccessor(MBB); 1558 1559 return; 1560} 1561 1562/// visitBitTestCase - this function produces one "bit test" 1563void SelectionDAGLowering::visitBitTestCase(MachineBasicBlock* NextMBB, 1564 unsigned Reg, 1565 SelectionDAGISel::BitTestCase &B) { 1566 // Emit bit tests and jumps 1567 SDOperand SwitchVal = DAG.getCopyFromReg(getControlRoot(), Reg, TLI.getPointerTy()); 1568 1569 SDOperand AndOp = DAG.getNode(ISD::AND, TLI.getPointerTy(), 1570 SwitchVal, 1571 DAG.getConstant(B.Mask, 1572 TLI.getPointerTy())); 1573 SDOperand AndCmp = DAG.getSetCC(TLI.getSetCCResultType(AndOp), AndOp, 1574 DAG.getConstant(0, TLI.getPointerTy()), 1575 ISD::SETNE); 1576 SDOperand BrAnd = DAG.getNode(ISD::BRCOND, MVT::Other, getControlRoot(), 1577 AndCmp, DAG.getBasicBlock(B.TargetBB)); 1578 1579 // Set NextBlock to be the MBB immediately after the current one, if any. 1580 // This is used to avoid emitting unnecessary branches to the next block. 1581 MachineBasicBlock *NextBlock = 0; 1582 MachineFunction::iterator BBI = CurMBB; 1583 if (++BBI != CurMBB->getParent()->end()) 1584 NextBlock = BBI; 1585 1586 if (NextMBB == NextBlock) 1587 DAG.setRoot(BrAnd); 1588 else 1589 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrAnd, 1590 DAG.getBasicBlock(NextMBB))); 1591 1592 CurMBB->addSuccessor(B.TargetBB); 1593 CurMBB->addSuccessor(NextMBB); 1594 1595 return; 1596} 1597 1598void SelectionDAGLowering::visitInvoke(InvokeInst &I) { 1599 // Retrieve successors. 1600 MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)]; 1601 MachineBasicBlock *LandingPad = FuncInfo.MBBMap[I.getSuccessor(1)]; 1602 1603 if (isa<InlineAsm>(I.getCalledValue())) 1604 visitInlineAsm(&I); 1605 else 1606 LowerCallTo(&I, getValue(I.getOperand(0)), false, LandingPad); 1607 1608 // If the value of the invoke is used outside of its defining block, make it 1609 // available as a virtual register. 1610 if (!I.use_empty()) { 1611 DenseMap<const Value*, unsigned>::iterator VMI = FuncInfo.ValueMap.find(&I); 1612 if (VMI != FuncInfo.ValueMap.end()) 1613 CopyValueToVirtualRegister(&I, VMI->second); 1614 } 1615 1616 // Drop into normal successor. 1617 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getControlRoot(), 1618 DAG.getBasicBlock(Return))); 1619 1620 // Update successor info 1621 CurMBB->addSuccessor(Return); 1622 CurMBB->addSuccessor(LandingPad); 1623} 1624 1625void SelectionDAGLowering::visitUnwind(UnwindInst &I) { 1626} 1627 1628/// handleSmallSwitchCaseRange - Emit a series of specific tests (suitable for 1629/// small case ranges). 1630bool SelectionDAGLowering::handleSmallSwitchRange(CaseRec& CR, 1631 CaseRecVector& WorkList, 1632 Value* SV, 1633 MachineBasicBlock* Default) { 1634 Case& BackCase = *(CR.Range.second-1); 1635 1636 // Size is the number of Cases represented by this range. 1637 unsigned Size = CR.Range.second - CR.Range.first; 1638 if (Size > 3) 1639 return false; 1640 1641 // Get the MachineFunction which holds the current MBB. This is used when 1642 // inserting any additional MBBs necessary to represent the switch. 1643 MachineFunction *CurMF = CurMBB->getParent(); 1644 1645 // Figure out which block is immediately after the current one. 1646 MachineBasicBlock *NextBlock = 0; 1647 MachineFunction::iterator BBI = CR.CaseBB; 1648 1649 if (++BBI != CurMBB->getParent()->end()) 1650 NextBlock = BBI; 1651 1652 // TODO: If any two of the cases has the same destination, and if one value 1653 // is the same as the other, but has one bit unset that the other has set, 1654 // use bit manipulation to do two compares at once. For example: 1655 // "if (X == 6 || X == 4)" -> "if ((X|2) == 6)" 1656 1657 // Rearrange the case blocks so that the last one falls through if possible. 1658 if (NextBlock && Default != NextBlock && BackCase.BB != NextBlock) { 1659 // The last case block won't fall through into 'NextBlock' if we emit the 1660 // branches in this order. See if rearranging a case value would help. 1661 for (CaseItr I = CR.Range.first, E = CR.Range.second-1; I != E; ++I) { 1662 if (I->BB == NextBlock) { 1663 std::swap(*I, BackCase); 1664 break; 1665 } 1666 } 1667 } 1668 1669 // Create a CaseBlock record representing a conditional branch to 1670 // the Case's target mbb if the value being switched on SV is equal 1671 // to C. 1672 MachineBasicBlock *CurBlock = CR.CaseBB; 1673 for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++I) { 1674 MachineBasicBlock *FallThrough; 1675 if (I != E-1) { 1676 FallThrough = new MachineBasicBlock(CurBlock->getBasicBlock()); 1677 CurMF->getBasicBlockList().insert(BBI, FallThrough); 1678 } else { 1679 // If the last case doesn't match, go to the default block. 1680 FallThrough = Default; 1681 } 1682 1683 Value *RHS, *LHS, *MHS; 1684 ISD::CondCode CC; 1685 if (I->High == I->Low) { 1686 // This is just small small case range :) containing exactly 1 case 1687 CC = ISD::SETEQ; 1688 LHS = SV; RHS = I->High; MHS = NULL; 1689 } else { 1690 CC = ISD::SETLE; 1691 LHS = I->Low; MHS = SV; RHS = I->High; 1692 } 1693 SelectionDAGISel::CaseBlock CB(CC, LHS, RHS, MHS, 1694 I->BB, FallThrough, CurBlock); 1695 1696 // If emitting the first comparison, just call visitSwitchCase to emit the 1697 // code into the current block. Otherwise, push the CaseBlock onto the 1698 // vector to be later processed by SDISel, and insert the node's MBB 1699 // before the next MBB. 1700 if (CurBlock == CurMBB) 1701 visitSwitchCase(CB); 1702 else 1703 SwitchCases.push_back(CB); 1704 1705 CurBlock = FallThrough; 1706 } 1707 1708 return true; 1709} 1710 1711static inline bool areJTsAllowed(const TargetLowering &TLI) { 1712 return (TLI.isOperationLegal(ISD::BR_JT, MVT::Other) || 1713 TLI.isOperationLegal(ISD::BRIND, MVT::Other)); 1714} 1715 1716/// handleJTSwitchCase - Emit jumptable for current switch case range 1717bool SelectionDAGLowering::handleJTSwitchCase(CaseRec& CR, 1718 CaseRecVector& WorkList, 1719 Value* SV, 1720 MachineBasicBlock* Default) { 1721 Case& FrontCase = *CR.Range.first; 1722 Case& BackCase = *(CR.Range.second-1); 1723 1724 int64_t First = cast<ConstantInt>(FrontCase.Low)->getSExtValue(); 1725 int64_t Last = cast<ConstantInt>(BackCase.High)->getSExtValue(); 1726 1727 uint64_t TSize = 0; 1728 for (CaseItr I = CR.Range.first, E = CR.Range.second; 1729 I!=E; ++I) 1730 TSize += I->size(); 1731 1732 if (!areJTsAllowed(TLI) || TSize <= 3) 1733 return false; 1734 1735 double Density = (double)TSize / (double)((Last - First) + 1ULL); 1736 if (Density < 0.4) 1737 return false; 1738 1739 DOUT << "Lowering jump table\n" 1740 << "First entry: " << First << ". Last entry: " << Last << "\n" 1741 << "Size: " << TSize << ". Density: " << Density << "\n\n"; 1742 1743 // Get the MachineFunction which holds the current MBB. This is used when 1744 // inserting any additional MBBs necessary to represent the switch. 1745 MachineFunction *CurMF = CurMBB->getParent(); 1746 1747 // Figure out which block is immediately after the current one. 1748 MachineBasicBlock *NextBlock = 0; 1749 MachineFunction::iterator BBI = CR.CaseBB; 1750 1751 if (++BBI != CurMBB->getParent()->end()) 1752 NextBlock = BBI; 1753 1754 const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock(); 1755 1756 // Create a new basic block to hold the code for loading the address 1757 // of the jump table, and jumping to it. Update successor information; 1758 // we will either branch to the default case for the switch, or the jump 1759 // table. 1760 MachineBasicBlock *JumpTableBB = new MachineBasicBlock(LLVMBB); 1761 CurMF->getBasicBlockList().insert(BBI, JumpTableBB); 1762 CR.CaseBB->addSuccessor(Default); 1763 CR.CaseBB->addSuccessor(JumpTableBB); 1764 1765 // Build a vector of destination BBs, corresponding to each target 1766 // of the jump table. If the value of the jump table slot corresponds to 1767 // a case statement, push the case's BB onto the vector, otherwise, push 1768 // the default BB. 1769 std::vector<MachineBasicBlock*> DestBBs; 1770 int64_t TEI = First; 1771 for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++TEI) { 1772 int64_t Low = cast<ConstantInt>(I->Low)->getSExtValue(); 1773 int64_t High = cast<ConstantInt>(I->High)->getSExtValue(); 1774 1775 if ((Low <= TEI) && (TEI <= High)) { 1776 DestBBs.push_back(I->BB); 1777 if (TEI==High) 1778 ++I; 1779 } else { 1780 DestBBs.push_back(Default); 1781 } 1782 } 1783 1784 // Update successor info. Add one edge to each unique successor. 1785 BitVector SuccsHandled(CR.CaseBB->getParent()->getNumBlockIDs()); 1786 for (std::vector<MachineBasicBlock*>::iterator I = DestBBs.begin(), 1787 E = DestBBs.end(); I != E; ++I) { 1788 if (!SuccsHandled[(*I)->getNumber()]) { 1789 SuccsHandled[(*I)->getNumber()] = true; 1790 JumpTableBB->addSuccessor(*I); 1791 } 1792 } 1793 1794 // Create a jump table index for this jump table, or return an existing 1795 // one. 1796 unsigned JTI = CurMF->getJumpTableInfo()->getJumpTableIndex(DestBBs); 1797 1798 // Set the jump table information so that we can codegen it as a second 1799 // MachineBasicBlock 1800 SelectionDAGISel::JumpTable JT(-1U, JTI, JumpTableBB, Default); 1801 SelectionDAGISel::JumpTableHeader JTH(First, Last, SV, CR.CaseBB, 1802 (CR.CaseBB == CurMBB)); 1803 if (CR.CaseBB == CurMBB) 1804 visitJumpTableHeader(JT, JTH); 1805 1806 JTCases.push_back(SelectionDAGISel::JumpTableBlock(JTH, JT)); 1807 1808 return true; 1809} 1810 1811/// handleBTSplitSwitchCase - emit comparison and split binary search tree into 1812/// 2 subtrees. 1813bool SelectionDAGLowering::handleBTSplitSwitchCase(CaseRec& CR, 1814 CaseRecVector& WorkList, 1815 Value* SV, 1816 MachineBasicBlock* Default) { 1817 // Get the MachineFunction which holds the current MBB. This is used when 1818 // inserting any additional MBBs necessary to represent the switch. 1819 MachineFunction *CurMF = CurMBB->getParent(); 1820 1821 // Figure out which block is immediately after the current one. 1822 MachineBasicBlock *NextBlock = 0; 1823 MachineFunction::iterator BBI = CR.CaseBB; 1824 1825 if (++BBI != CurMBB->getParent()->end()) 1826 NextBlock = BBI; 1827 1828 Case& FrontCase = *CR.Range.first; 1829 Case& BackCase = *(CR.Range.second-1); 1830 const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock(); 1831 1832 // Size is the number of Cases represented by this range. 1833 unsigned Size = CR.Range.second - CR.Range.first; 1834 1835 int64_t First = cast<ConstantInt>(FrontCase.Low)->getSExtValue(); 1836 int64_t Last = cast<ConstantInt>(BackCase.High)->getSExtValue(); 1837 double FMetric = 0; 1838 CaseItr Pivot = CR.Range.first + Size/2; 1839 1840 // Select optimal pivot, maximizing sum density of LHS and RHS. This will 1841 // (heuristically) allow us to emit JumpTable's later. 1842 uint64_t TSize = 0; 1843 for (CaseItr I = CR.Range.first, E = CR.Range.second; 1844 I!=E; ++I) 1845 TSize += I->size(); 1846 1847 uint64_t LSize = FrontCase.size(); 1848 uint64_t RSize = TSize-LSize; 1849 DOUT << "Selecting best pivot: \n" 1850 << "First: " << First << ", Last: " << Last <<"\n" 1851 << "LSize: " << LSize << ", RSize: " << RSize << "\n"; 1852 for (CaseItr I = CR.Range.first, J=I+1, E = CR.Range.second; 1853 J!=E; ++I, ++J) { 1854 int64_t LEnd = cast<ConstantInt>(I->High)->getSExtValue(); 1855 int64_t RBegin = cast<ConstantInt>(J->Low)->getSExtValue(); 1856 assert((RBegin-LEnd>=1) && "Invalid case distance"); 1857 double LDensity = (double)LSize / (double)((LEnd - First) + 1ULL); 1858 double RDensity = (double)RSize / (double)((Last - RBegin) + 1ULL); 1859 double Metric = Log2_64(RBegin-LEnd)*(LDensity+RDensity); 1860 // Should always split in some non-trivial place 1861 DOUT <<"=>Step\n" 1862 << "LEnd: " << LEnd << ", RBegin: " << RBegin << "\n" 1863 << "LDensity: " << LDensity << ", RDensity: " << RDensity << "\n" 1864 << "Metric: " << Metric << "\n"; 1865 if (FMetric < Metric) { 1866 Pivot = J; 1867 FMetric = Metric; 1868 DOUT << "Current metric set to: " << FMetric << "\n"; 1869 } 1870 1871 LSize += J->size(); 1872 RSize -= J->size(); 1873 } 1874 if (areJTsAllowed(TLI)) { 1875 // If our case is dense we *really* should handle it earlier! 1876 assert((FMetric > 0) && "Should handle dense range earlier!"); 1877 } else { 1878 Pivot = CR.Range.first + Size/2; 1879 } 1880 1881 CaseRange LHSR(CR.Range.first, Pivot); 1882 CaseRange RHSR(Pivot, CR.Range.second); 1883 Constant *C = Pivot->Low; 1884 MachineBasicBlock *FalseBB = 0, *TrueBB = 0; 1885 1886 // We know that we branch to the LHS if the Value being switched on is 1887 // less than the Pivot value, C. We use this to optimize our binary 1888 // tree a bit, by recognizing that if SV is greater than or equal to the 1889 // LHS's Case Value, and that Case Value is exactly one less than the 1890 // Pivot's Value, then we can branch directly to the LHS's Target, 1891 // rather than creating a leaf node for it. 1892 if ((LHSR.second - LHSR.first) == 1 && 1893 LHSR.first->High == CR.GE && 1894 cast<ConstantInt>(C)->getSExtValue() == 1895 (cast<ConstantInt>(CR.GE)->getSExtValue() + 1LL)) { 1896 TrueBB = LHSR.first->BB; 1897 } else { 1898 TrueBB = new MachineBasicBlock(LLVMBB); 1899 CurMF->getBasicBlockList().insert(BBI, TrueBB); 1900 WorkList.push_back(CaseRec(TrueBB, C, CR.GE, LHSR)); 1901 } 1902 1903 // Similar to the optimization above, if the Value being switched on is 1904 // known to be less than the Constant CR.LT, and the current Case Value 1905 // is CR.LT - 1, then we can branch directly to the target block for 1906 // the current Case Value, rather than emitting a RHS leaf node for it. 1907 if ((RHSR.second - RHSR.first) == 1 && CR.LT && 1908 cast<ConstantInt>(RHSR.first->Low)->getSExtValue() == 1909 (cast<ConstantInt>(CR.LT)->getSExtValue() - 1LL)) { 1910 FalseBB = RHSR.first->BB; 1911 } else { 1912 FalseBB = new MachineBasicBlock(LLVMBB); 1913 CurMF->getBasicBlockList().insert(BBI, FalseBB); 1914 WorkList.push_back(CaseRec(FalseBB,CR.LT,C,RHSR)); 1915 } 1916 1917 // Create a CaseBlock record representing a conditional branch to 1918 // the LHS node if the value being switched on SV is less than C. 1919 // Otherwise, branch to LHS. 1920 SelectionDAGISel::CaseBlock CB(ISD::SETLT, SV, C, NULL, 1921 TrueBB, FalseBB, CR.CaseBB); 1922 1923 if (CR.CaseBB == CurMBB) 1924 visitSwitchCase(CB); 1925 else 1926 SwitchCases.push_back(CB); 1927 1928 return true; 1929} 1930 1931/// handleBitTestsSwitchCase - if current case range has few destination and 1932/// range span less, than machine word bitwidth, encode case range into series 1933/// of masks and emit bit tests with these masks. 1934bool SelectionDAGLowering::handleBitTestsSwitchCase(CaseRec& CR, 1935 CaseRecVector& WorkList, 1936 Value* SV, 1937 MachineBasicBlock* Default){ 1938 unsigned IntPtrBits = MVT::getSizeInBits(TLI.getPointerTy()); 1939 1940 Case& FrontCase = *CR.Range.first; 1941 Case& BackCase = *(CR.Range.second-1); 1942 1943 // Get the MachineFunction which holds the current MBB. This is used when 1944 // inserting any additional MBBs necessary to represent the switch. 1945 MachineFunction *CurMF = CurMBB->getParent(); 1946 1947 unsigned numCmps = 0; 1948 for (CaseItr I = CR.Range.first, E = CR.Range.second; 1949 I!=E; ++I) { 1950 // Single case counts one, case range - two. 1951 if (I->Low == I->High) 1952 numCmps +=1; 1953 else 1954 numCmps +=2; 1955 } 1956 1957 // Count unique destinations 1958 SmallSet<MachineBasicBlock*, 4> Dests; 1959 for (CaseItr I = CR.Range.first, E = CR.Range.second; I!=E; ++I) { 1960 Dests.insert(I->BB); 1961 if (Dests.size() > 3) 1962 // Don't bother the code below, if there are too much unique destinations 1963 return false; 1964 } 1965 DOUT << "Total number of unique destinations: " << Dests.size() << "\n" 1966 << "Total number of comparisons: " << numCmps << "\n"; 1967 1968 // Compute span of values. 1969 Constant* minValue = FrontCase.Low; 1970 Constant* maxValue = BackCase.High; 1971 uint64_t range = cast<ConstantInt>(maxValue)->getSExtValue() - 1972 cast<ConstantInt>(minValue)->getSExtValue(); 1973 DOUT << "Compare range: " << range << "\n" 1974 << "Low bound: " << cast<ConstantInt>(minValue)->getSExtValue() << "\n" 1975 << "High bound: " << cast<ConstantInt>(maxValue)->getSExtValue() << "\n"; 1976 1977 if (range>=IntPtrBits || 1978 (!(Dests.size() == 1 && numCmps >= 3) && 1979 !(Dests.size() == 2 && numCmps >= 5) && 1980 !(Dests.size() >= 3 && numCmps >= 6))) 1981 return false; 1982 1983 DOUT << "Emitting bit tests\n"; 1984 int64_t lowBound = 0; 1985 1986 // Optimize the case where all the case values fit in a 1987 // word without having to subtract minValue. In this case, 1988 // we can optimize away the subtraction. 1989 if (cast<ConstantInt>(minValue)->getSExtValue() >= 0 && 1990 cast<ConstantInt>(maxValue)->getSExtValue() < IntPtrBits) { 1991 range = cast<ConstantInt>(maxValue)->getSExtValue(); 1992 } else { 1993 lowBound = cast<ConstantInt>(minValue)->getSExtValue(); 1994 } 1995 1996 CaseBitsVector CasesBits; 1997 unsigned i, count = 0; 1998 1999 for (CaseItr I = CR.Range.first, E = CR.Range.second; I!=E; ++I) { 2000 MachineBasicBlock* Dest = I->BB; 2001 for (i = 0; i < count; ++i) 2002 if (Dest == CasesBits[i].BB) 2003 break; 2004 2005 if (i == count) { 2006 assert((count < 3) && "Too much destinations to test!"); 2007 CasesBits.push_back(CaseBits(0, Dest, 0)); 2008 count++; 2009 } 2010 2011 uint64_t lo = cast<ConstantInt>(I->Low)->getSExtValue() - lowBound; 2012 uint64_t hi = cast<ConstantInt>(I->High)->getSExtValue() - lowBound; 2013 2014 for (uint64_t j = lo; j <= hi; j++) { 2015 CasesBits[i].Mask |= 1ULL << j; 2016 CasesBits[i].Bits++; 2017 } 2018 2019 } 2020 std::sort(CasesBits.begin(), CasesBits.end(), CaseBitsCmp()); 2021 2022 SelectionDAGISel::BitTestInfo BTC; 2023 2024 // Figure out which block is immediately after the current one. 2025 MachineFunction::iterator BBI = CR.CaseBB; 2026 ++BBI; 2027 2028 const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock(); 2029 2030 DOUT << "Cases:\n"; 2031 for (unsigned i = 0, e = CasesBits.size(); i!=e; ++i) { 2032 DOUT << "Mask: " << CasesBits[i].Mask << ", Bits: " << CasesBits[i].Bits 2033 << ", BB: " << CasesBits[i].BB << "\n"; 2034 2035 MachineBasicBlock *CaseBB = new MachineBasicBlock(LLVMBB); 2036 CurMF->getBasicBlockList().insert(BBI, CaseBB); 2037 BTC.push_back(SelectionDAGISel::BitTestCase(CasesBits[i].Mask, 2038 CaseBB, 2039 CasesBits[i].BB)); 2040 } 2041 2042 SelectionDAGISel::BitTestBlock BTB(lowBound, range, SV, 2043 -1U, (CR.CaseBB == CurMBB), 2044 CR.CaseBB, Default, BTC); 2045 2046 if (CR.CaseBB == CurMBB) 2047 visitBitTestHeader(BTB); 2048 2049 BitTestCases.push_back(BTB); 2050 2051 return true; 2052} 2053 2054 2055/// Clusterify - Transform simple list of Cases into list of CaseRange's 2056unsigned SelectionDAGLowering::Clusterify(CaseVector& Cases, 2057 const SwitchInst& SI) { 2058 unsigned numCmps = 0; 2059 2060 // Start with "simple" cases 2061 for (unsigned i = 1; i < SI.getNumSuccessors(); ++i) { 2062 MachineBasicBlock *SMBB = FuncInfo.MBBMap[SI.getSuccessor(i)]; 2063 Cases.push_back(Case(SI.getSuccessorValue(i), 2064 SI.getSuccessorValue(i), 2065 SMBB)); 2066 } 2067 std::sort(Cases.begin(), Cases.end(), CaseCmp()); 2068 2069 // Merge case into clusters 2070 if (Cases.size()>=2) 2071 // Must recompute end() each iteration because it may be 2072 // invalidated by erase if we hold on to it 2073 for (CaseItr I=Cases.begin(), J=++(Cases.begin()); J!=Cases.end(); ) { 2074 int64_t nextValue = cast<ConstantInt>(J->Low)->getSExtValue(); 2075 int64_t currentValue = cast<ConstantInt>(I->High)->getSExtValue(); 2076 MachineBasicBlock* nextBB = J->BB; 2077 MachineBasicBlock* currentBB = I->BB; 2078 2079 // If the two neighboring cases go to the same destination, merge them 2080 // into a single case. 2081 if ((nextValue-currentValue==1) && (currentBB == nextBB)) { 2082 I->High = J->High; 2083 J = Cases.erase(J); 2084 } else { 2085 I = J++; 2086 } 2087 } 2088 2089 for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { 2090 if (I->Low != I->High) 2091 // A range counts double, since it requires two compares. 2092 ++numCmps; 2093 } 2094 2095 return numCmps; 2096} 2097 2098void SelectionDAGLowering::visitSwitch(SwitchInst &SI) { 2099 // Figure out which block is immediately after the current one. 2100 MachineBasicBlock *NextBlock = 0; 2101 MachineFunction::iterator BBI = CurMBB; 2102 2103 MachineBasicBlock *Default = FuncInfo.MBBMap[SI.getDefaultDest()]; 2104 2105 // If there is only the default destination, branch to it if it is not the 2106 // next basic block. Otherwise, just fall through. 2107 if (SI.getNumOperands() == 2) { 2108 // Update machine-CFG edges. 2109 2110 // If this is not a fall-through branch, emit the branch. 2111 if (Default != NextBlock) 2112 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getControlRoot(), 2113 DAG.getBasicBlock(Default))); 2114 2115 CurMBB->addSuccessor(Default); 2116 return; 2117 } 2118 2119 // If there are any non-default case statements, create a vector of Cases 2120 // representing each one, and sort the vector so that we can efficiently 2121 // create a binary search tree from them. 2122 CaseVector Cases; 2123 unsigned numCmps = Clusterify(Cases, SI); 2124 DOUT << "Clusterify finished. Total clusters: " << Cases.size() 2125 << ". Total compares: " << numCmps << "\n"; 2126 2127 // Get the Value to be switched on and default basic blocks, which will be 2128 // inserted into CaseBlock records, representing basic blocks in the binary 2129 // search tree. 2130 Value *SV = SI.getOperand(0); 2131 2132 // Push the initial CaseRec onto the worklist 2133 CaseRecVector WorkList; 2134 WorkList.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end()))); 2135 2136 while (!WorkList.empty()) { 2137 // Grab a record representing a case range to process off the worklist 2138 CaseRec CR = WorkList.back(); 2139 WorkList.pop_back(); 2140 2141 if (handleBitTestsSwitchCase(CR, WorkList, SV, Default)) 2142 continue; 2143 2144 // If the range has few cases (two or less) emit a series of specific 2145 // tests. 2146 if (handleSmallSwitchRange(CR, WorkList, SV, Default)) 2147 continue; 2148 2149 // If the switch has more than 5 blocks, and at least 40% dense, and the 2150 // target supports indirect branches, then emit a jump table rather than 2151 // lowering the switch to a binary tree of conditional branches. 2152 if (handleJTSwitchCase(CR, WorkList, SV, Default)) 2153 continue; 2154 2155 // Emit binary tree. We need to pick a pivot, and push left and right ranges 2156 // onto the worklist. Leafs are handled via handleSmallSwitchRange() call. 2157 handleBTSplitSwitchCase(CR, WorkList, SV, Default); 2158 } 2159} 2160 2161 2162void SelectionDAGLowering::visitSub(User &I) { 2163 // -0.0 - X --> fneg 2164 const Type *Ty = I.getType(); 2165 if (isa<VectorType>(Ty)) { 2166 if (ConstantVector *CV = dyn_cast<ConstantVector>(I.getOperand(0))) { 2167 const VectorType *DestTy = cast<VectorType>(I.getType()); 2168 const Type *ElTy = DestTy->getElementType(); 2169 if (ElTy->isFloatingPoint()) { 2170 unsigned VL = DestTy->getNumElements(); 2171 std::vector<Constant*> NZ(VL, ConstantFP::getNegativeZero(ElTy)); 2172 Constant *CNZ = ConstantVector::get(&NZ[0], NZ.size()); 2173 if (CV == CNZ) { 2174 SDOperand Op2 = getValue(I.getOperand(1)); 2175 setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2)); 2176 return; 2177 } 2178 } 2179 } 2180 } 2181 if (Ty->isFloatingPoint()) { 2182 if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0))) 2183 if (CFP->isExactlyValue(ConstantFP::getNegativeZero(Ty)->getValueAPF())) { 2184 SDOperand Op2 = getValue(I.getOperand(1)); 2185 setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2)); 2186 return; 2187 } 2188 } 2189 2190 visitBinary(I, Ty->isFPOrFPVector() ? ISD::FSUB : ISD::SUB); 2191} 2192 2193void SelectionDAGLowering::visitBinary(User &I, unsigned OpCode) { 2194 SDOperand Op1 = getValue(I.getOperand(0)); 2195 SDOperand Op2 = getValue(I.getOperand(1)); 2196 2197 setValue(&I, DAG.getNode(OpCode, Op1.getValueType(), Op1, Op2)); 2198} 2199 2200void SelectionDAGLowering::visitShift(User &I, unsigned Opcode) { 2201 SDOperand Op1 = getValue(I.getOperand(0)); 2202 SDOperand Op2 = getValue(I.getOperand(1)); 2203 2204 if (MVT::getSizeInBits(TLI.getShiftAmountTy()) < 2205 MVT::getSizeInBits(Op2.getValueType())) 2206 Op2 = DAG.getNode(ISD::TRUNCATE, TLI.getShiftAmountTy(), Op2); 2207 else if (TLI.getShiftAmountTy() > Op2.getValueType()) 2208 Op2 = DAG.getNode(ISD::ANY_EXTEND, TLI.getShiftAmountTy(), Op2); 2209 2210 setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2)); 2211} 2212 2213void SelectionDAGLowering::visitICmp(User &I) { 2214 ICmpInst::Predicate predicate = ICmpInst::BAD_ICMP_PREDICATE; 2215 if (ICmpInst *IC = dyn_cast<ICmpInst>(&I)) 2216 predicate = IC->getPredicate(); 2217 else if (ConstantExpr *IC = dyn_cast<ConstantExpr>(&I)) 2218 predicate = ICmpInst::Predicate(IC->getPredicate()); 2219 SDOperand Op1 = getValue(I.getOperand(0)); 2220 SDOperand Op2 = getValue(I.getOperand(1)); 2221 ISD::CondCode Opcode; 2222 switch (predicate) { 2223 case ICmpInst::ICMP_EQ : Opcode = ISD::SETEQ; break; 2224 case ICmpInst::ICMP_NE : Opcode = ISD::SETNE; break; 2225 case ICmpInst::ICMP_UGT : Opcode = ISD::SETUGT; break; 2226 case ICmpInst::ICMP_UGE : Opcode = ISD::SETUGE; break; 2227 case ICmpInst::ICMP_ULT : Opcode = ISD::SETULT; break; 2228 case ICmpInst::ICMP_ULE : Opcode = ISD::SETULE; break; 2229 case ICmpInst::ICMP_SGT : Opcode = ISD::SETGT; break; 2230 case ICmpInst::ICMP_SGE : Opcode = ISD::SETGE; break; 2231 case ICmpInst::ICMP_SLT : Opcode = ISD::SETLT; break; 2232 case ICmpInst::ICMP_SLE : Opcode = ISD::SETLE; break; 2233 default: 2234 assert(!"Invalid ICmp predicate value"); 2235 Opcode = ISD::SETEQ; 2236 break; 2237 } 2238 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode)); 2239} 2240 2241void SelectionDAGLowering::visitFCmp(User &I) { 2242 FCmpInst::Predicate predicate = FCmpInst::BAD_FCMP_PREDICATE; 2243 if (FCmpInst *FC = dyn_cast<FCmpInst>(&I)) 2244 predicate = FC->getPredicate(); 2245 else if (ConstantExpr *FC = dyn_cast<ConstantExpr>(&I)) 2246 predicate = FCmpInst::Predicate(FC->getPredicate()); 2247 SDOperand Op1 = getValue(I.getOperand(0)); 2248 SDOperand Op2 = getValue(I.getOperand(1)); 2249 ISD::CondCode Condition, FOC, FPC; 2250 switch (predicate) { 2251 case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break; 2252 case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break; 2253 case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break; 2254 case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break; 2255 case FCmpInst::FCMP_OLT: FOC = ISD::SETLT; FPC = ISD::SETOLT; break; 2256 case FCmpInst::FCMP_OLE: FOC = ISD::SETLE; FPC = ISD::SETOLE; break; 2257 case FCmpInst::FCMP_ONE: FOC = ISD::SETNE; FPC = ISD::SETONE; break; 2258 case FCmpInst::FCMP_ORD: FOC = ISD::SETEQ; FPC = ISD::SETO; break; 2259 case FCmpInst::FCMP_UNO: FOC = ISD::SETNE; FPC = ISD::SETUO; break; 2260 case FCmpInst::FCMP_UEQ: FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break; 2261 case FCmpInst::FCMP_UGT: FOC = ISD::SETGT; FPC = ISD::SETUGT; break; 2262 case FCmpInst::FCMP_UGE: FOC = ISD::SETGE; FPC = ISD::SETUGE; break; 2263 case FCmpInst::FCMP_ULT: FOC = ISD::SETLT; FPC = ISD::SETULT; break; 2264 case FCmpInst::FCMP_ULE: FOC = ISD::SETLE; FPC = ISD::SETULE; break; 2265 case FCmpInst::FCMP_UNE: FOC = ISD::SETNE; FPC = ISD::SETUNE; break; 2266 case FCmpInst::FCMP_TRUE: FOC = FPC = ISD::SETTRUE; break; 2267 default: 2268 assert(!"Invalid FCmp predicate value"); 2269 FOC = FPC = ISD::SETFALSE; 2270 break; 2271 } 2272 if (FiniteOnlyFPMath()) 2273 Condition = FOC; 2274 else 2275 Condition = FPC; 2276 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Condition)); 2277} 2278 2279void SelectionDAGLowering::visitSelect(User &I) { 2280 SDOperand Cond = getValue(I.getOperand(0)); 2281 SDOperand TrueVal = getValue(I.getOperand(1)); 2282 SDOperand FalseVal = getValue(I.getOperand(2)); 2283 setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond, 2284 TrueVal, FalseVal)); 2285} 2286 2287 2288void SelectionDAGLowering::visitTrunc(User &I) { 2289 // TruncInst cannot be a no-op cast because sizeof(src) > sizeof(dest). 2290 SDOperand N = getValue(I.getOperand(0)); 2291 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 2292 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N)); 2293} 2294 2295void SelectionDAGLowering::visitZExt(User &I) { 2296 // ZExt cannot be a no-op cast because sizeof(src) < sizeof(dest). 2297 // ZExt also can't be a cast to bool for same reason. So, nothing much to do 2298 SDOperand N = getValue(I.getOperand(0)); 2299 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 2300 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N)); 2301} 2302 2303void SelectionDAGLowering::visitSExt(User &I) { 2304 // SExt cannot be a no-op cast because sizeof(src) < sizeof(dest). 2305 // SExt also can't be a cast to bool for same reason. So, nothing much to do 2306 SDOperand N = getValue(I.getOperand(0)); 2307 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 2308 setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestVT, N)); 2309} 2310 2311void SelectionDAGLowering::visitFPTrunc(User &I) { 2312 // FPTrunc is never a no-op cast, no need to check 2313 SDOperand N = getValue(I.getOperand(0)); 2314 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 2315 setValue(&I, DAG.getNode(ISD::FP_ROUND, DestVT, N, DAG.getIntPtrConstant(0))); 2316} 2317 2318void SelectionDAGLowering::visitFPExt(User &I){ 2319 // FPTrunc is never a no-op cast, no need to check 2320 SDOperand N = getValue(I.getOperand(0)); 2321 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 2322 setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestVT, N)); 2323} 2324 2325void SelectionDAGLowering::visitFPToUI(User &I) { 2326 // FPToUI is never a no-op cast, no need to check 2327 SDOperand N = getValue(I.getOperand(0)); 2328 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 2329 setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestVT, N)); 2330} 2331 2332void SelectionDAGLowering::visitFPToSI(User &I) { 2333 // FPToSI is never a no-op cast, no need to check 2334 SDOperand N = getValue(I.getOperand(0)); 2335 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 2336 setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestVT, N)); 2337} 2338 2339void SelectionDAGLowering::visitUIToFP(User &I) { 2340 // UIToFP is never a no-op cast, no need to check 2341 SDOperand N = getValue(I.getOperand(0)); 2342 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 2343 setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestVT, N)); 2344} 2345 2346void SelectionDAGLowering::visitSIToFP(User &I){ 2347 // UIToFP is never a no-op cast, no need to check 2348 SDOperand N = getValue(I.getOperand(0)); 2349 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 2350 setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestVT, N)); 2351} 2352 2353void SelectionDAGLowering::visitPtrToInt(User &I) { 2354 // What to do depends on the size of the integer and the size of the pointer. 2355 // We can either truncate, zero extend, or no-op, accordingly. 2356 SDOperand N = getValue(I.getOperand(0)); 2357 MVT::ValueType SrcVT = N.getValueType(); 2358 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 2359 SDOperand Result; 2360 if (MVT::getSizeInBits(DestVT) < MVT::getSizeInBits(SrcVT)) 2361 Result = DAG.getNode(ISD::TRUNCATE, DestVT, N); 2362 else 2363 // Note: ZERO_EXTEND can handle cases where the sizes are equal too 2364 Result = DAG.getNode(ISD::ZERO_EXTEND, DestVT, N); 2365 setValue(&I, Result); 2366} 2367 2368void SelectionDAGLowering::visitIntToPtr(User &I) { 2369 // What to do depends on the size of the integer and the size of the pointer. 2370 // We can either truncate, zero extend, or no-op, accordingly. 2371 SDOperand N = getValue(I.getOperand(0)); 2372 MVT::ValueType SrcVT = N.getValueType(); 2373 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 2374 if (MVT::getSizeInBits(DestVT) < MVT::getSizeInBits(SrcVT)) 2375 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N)); 2376 else 2377 // Note: ZERO_EXTEND can handle cases where the sizes are equal too 2378 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N)); 2379} 2380 2381void SelectionDAGLowering::visitBitCast(User &I) { 2382 SDOperand N = getValue(I.getOperand(0)); 2383 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 2384 2385 // BitCast assures us that source and destination are the same size so this 2386 // is either a BIT_CONVERT or a no-op. 2387 if (DestVT != N.getValueType()) 2388 setValue(&I, DAG.getNode(ISD::BIT_CONVERT, DestVT, N)); // convert types 2389 else 2390 setValue(&I, N); // noop cast. 2391} 2392 2393void SelectionDAGLowering::visitInsertElement(User &I) { 2394 SDOperand InVec = getValue(I.getOperand(0)); 2395 SDOperand InVal = getValue(I.getOperand(1)); 2396 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), 2397 getValue(I.getOperand(2))); 2398 2399 setValue(&I, DAG.getNode(ISD::INSERT_VECTOR_ELT, 2400 TLI.getValueType(I.getType()), 2401 InVec, InVal, InIdx)); 2402} 2403 2404void SelectionDAGLowering::visitExtractElement(User &I) { 2405 SDOperand InVec = getValue(I.getOperand(0)); 2406 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), 2407 getValue(I.getOperand(1))); 2408 setValue(&I, DAG.getNode(ISD::EXTRACT_VECTOR_ELT, 2409 TLI.getValueType(I.getType()), InVec, InIdx)); 2410} 2411 2412void SelectionDAGLowering::visitShuffleVector(User &I) { 2413 SDOperand V1 = getValue(I.getOperand(0)); 2414 SDOperand V2 = getValue(I.getOperand(1)); 2415 SDOperand Mask = getValue(I.getOperand(2)); 2416 2417 setValue(&I, DAG.getNode(ISD::VECTOR_SHUFFLE, 2418 TLI.getValueType(I.getType()), 2419 V1, V2, Mask)); 2420} 2421 2422 2423void SelectionDAGLowering::visitGetElementPtr(User &I) { 2424 SDOperand N = getValue(I.getOperand(0)); 2425 const Type *Ty = I.getOperand(0)->getType(); 2426 2427 for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end(); 2428 OI != E; ++OI) { 2429 Value *Idx = *OI; 2430 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 2431 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue(); 2432 if (Field) { 2433 // N = N + Offset 2434 uint64_t Offset = TD->getStructLayout(StTy)->getElementOffset(Field); 2435 N = DAG.getNode(ISD::ADD, N.getValueType(), N, 2436 DAG.getIntPtrConstant(Offset)); 2437 } 2438 Ty = StTy->getElementType(Field); 2439 } else { 2440 Ty = cast<SequentialType>(Ty)->getElementType(); 2441 2442 // If this is a constant subscript, handle it quickly. 2443 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 2444 if (CI->getZExtValue() == 0) continue; 2445 uint64_t Offs = 2446 TD->getABITypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue(); 2447 N = DAG.getNode(ISD::ADD, N.getValueType(), N, 2448 DAG.getIntPtrConstant(Offs)); 2449 continue; 2450 } 2451 2452 // N = N + Idx * ElementSize; 2453 uint64_t ElementSize = TD->getABITypeSize(Ty); 2454 SDOperand IdxN = getValue(Idx); 2455 2456 // If the index is smaller or larger than intptr_t, truncate or extend 2457 // it. 2458 if (IdxN.getValueType() < N.getValueType()) { 2459 IdxN = DAG.getNode(ISD::SIGN_EXTEND, N.getValueType(), IdxN); 2460 } else if (IdxN.getValueType() > N.getValueType()) 2461 IdxN = DAG.getNode(ISD::TRUNCATE, N.getValueType(), IdxN); 2462 2463 // If this is a multiply by a power of two, turn it into a shl 2464 // immediately. This is a very common case. 2465 if (isPowerOf2_64(ElementSize)) { 2466 unsigned Amt = Log2_64(ElementSize); 2467 IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN, 2468 DAG.getConstant(Amt, TLI.getShiftAmountTy())); 2469 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN); 2470 continue; 2471 } 2472 2473 SDOperand Scale = DAG.getIntPtrConstant(ElementSize); 2474 IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale); 2475 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN); 2476 } 2477 } 2478 setValue(&I, N); 2479} 2480 2481void SelectionDAGLowering::visitAlloca(AllocaInst &I) { 2482 // If this is a fixed sized alloca in the entry block of the function, 2483 // allocate it statically on the stack. 2484 if (FuncInfo.StaticAllocaMap.count(&I)) 2485 return; // getValue will auto-populate this. 2486 2487 const Type *Ty = I.getAllocatedType(); 2488 uint64_t TySize = TLI.getTargetData()->getABITypeSize(Ty); 2489 unsigned Align = 2490 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), 2491 I.getAlignment()); 2492 2493 SDOperand AllocSize = getValue(I.getArraySize()); 2494 MVT::ValueType IntPtr = TLI.getPointerTy(); 2495 if (IntPtr < AllocSize.getValueType()) 2496 AllocSize = DAG.getNode(ISD::TRUNCATE, IntPtr, AllocSize); 2497 else if (IntPtr > AllocSize.getValueType()) 2498 AllocSize = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, AllocSize); 2499 2500 AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize, 2501 DAG.getIntPtrConstant(TySize)); 2502 2503 // Handle alignment. If the requested alignment is less than or equal to 2504 // the stack alignment, ignore it. If the size is greater than or equal to 2505 // the stack alignment, we note this in the DYNAMIC_STACKALLOC node. 2506 unsigned StackAlign = 2507 TLI.getTargetMachine().getFrameInfo()->getStackAlignment(); 2508 if (Align <= StackAlign) 2509 Align = 0; 2510 2511 // Round the size of the allocation up to the stack alignment size 2512 // by add SA-1 to the size. 2513 AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize, 2514 DAG.getIntPtrConstant(StackAlign-1)); 2515 // Mask out the low bits for alignment purposes. 2516 AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize, 2517 DAG.getIntPtrConstant(~(uint64_t)(StackAlign-1))); 2518 2519 SDOperand Ops[] = { getRoot(), AllocSize, DAG.getIntPtrConstant(Align) }; 2520 const MVT::ValueType *VTs = DAG.getNodeValueTypes(AllocSize.getValueType(), 2521 MVT::Other); 2522 SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, 2, Ops, 3); 2523 setValue(&I, DSA); 2524 DAG.setRoot(DSA.getValue(1)); 2525 2526 // Inform the Frame Information that we have just allocated a variable-sized 2527 // object. 2528 CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject(); 2529} 2530 2531void SelectionDAGLowering::visitLoad(LoadInst &I) { 2532 SDOperand Ptr = getValue(I.getOperand(0)); 2533 2534 SDOperand Root; 2535 if (I.isVolatile()) 2536 Root = getRoot(); 2537 else { 2538 // Do not serialize non-volatile loads against each other. 2539 Root = DAG.getRoot(); 2540 } 2541 2542 setValue(&I, getLoadFrom(I.getType(), Ptr, I.getOperand(0), 2543 Root, I.isVolatile(), I.getAlignment())); 2544} 2545 2546SDOperand SelectionDAGLowering::getLoadFrom(const Type *Ty, SDOperand Ptr, 2547 const Value *SV, SDOperand Root, 2548 bool isVolatile, 2549 unsigned Alignment) { 2550 SDOperand L = 2551 DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SV, 0, 2552 isVolatile, Alignment); 2553 2554 if (isVolatile) 2555 DAG.setRoot(L.getValue(1)); 2556 else 2557 PendingLoads.push_back(L.getValue(1)); 2558 2559 return L; 2560} 2561 2562 2563void SelectionDAGLowering::visitStore(StoreInst &I) { 2564 Value *SrcV = I.getOperand(0); 2565 SDOperand Src = getValue(SrcV); 2566 SDOperand Ptr = getValue(I.getOperand(1)); 2567 DAG.setRoot(DAG.getStore(getRoot(), Src, Ptr, I.getOperand(1), 0, 2568 I.isVolatile(), I.getAlignment())); 2569} 2570 2571/// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC 2572/// node. 2573void SelectionDAGLowering::visitTargetIntrinsic(CallInst &I, 2574 unsigned Intrinsic) { 2575 bool HasChain = !I.doesNotAccessMemory(); 2576 bool OnlyLoad = HasChain && I.onlyReadsMemory(); 2577 2578 // Build the operand list. 2579 SmallVector<SDOperand, 8> Ops; 2580 if (HasChain) { // If this intrinsic has side-effects, chainify it. 2581 if (OnlyLoad) { 2582 // We don't need to serialize loads against other loads. 2583 Ops.push_back(DAG.getRoot()); 2584 } else { 2585 Ops.push_back(getRoot()); 2586 } 2587 } 2588 2589 // Add the intrinsic ID as an integer operand. 2590 Ops.push_back(DAG.getConstant(Intrinsic, TLI.getPointerTy())); 2591 2592 // Add all operands of the call to the operand list. 2593 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) { 2594 SDOperand Op = getValue(I.getOperand(i)); 2595 assert(TLI.isTypeLegal(Op.getValueType()) && 2596 "Intrinsic uses a non-legal type?"); 2597 Ops.push_back(Op); 2598 } 2599 2600 std::vector<MVT::ValueType> VTs; 2601 if (I.getType() != Type::VoidTy) { 2602 MVT::ValueType VT = TLI.getValueType(I.getType()); 2603 if (MVT::isVector(VT)) { 2604 const VectorType *DestTy = cast<VectorType>(I.getType()); 2605 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType()); 2606 2607 VT = MVT::getVectorType(EltVT, DestTy->getNumElements()); 2608 assert(VT != MVT::Other && "Intrinsic uses a non-legal type?"); 2609 } 2610 2611 assert(TLI.isTypeLegal(VT) && "Intrinsic uses a non-legal type?"); 2612 VTs.push_back(VT); 2613 } 2614 if (HasChain) 2615 VTs.push_back(MVT::Other); 2616 2617 const MVT::ValueType *VTList = DAG.getNodeValueTypes(VTs); 2618 2619 // Create the node. 2620 SDOperand Result; 2621 if (!HasChain) 2622 Result = DAG.getNode(ISD::INTRINSIC_WO_CHAIN, VTList, VTs.size(), 2623 &Ops[0], Ops.size()); 2624 else if (I.getType() != Type::VoidTy) 2625 Result = DAG.getNode(ISD::INTRINSIC_W_CHAIN, VTList, VTs.size(), 2626 &Ops[0], Ops.size()); 2627 else 2628 Result = DAG.getNode(ISD::INTRINSIC_VOID, VTList, VTs.size(), 2629 &Ops[0], Ops.size()); 2630 2631 if (HasChain) { 2632 SDOperand Chain = Result.getValue(Result.Val->getNumValues()-1); 2633 if (OnlyLoad) 2634 PendingLoads.push_back(Chain); 2635 else 2636 DAG.setRoot(Chain); 2637 } 2638 if (I.getType() != Type::VoidTy) { 2639 if (const VectorType *PTy = dyn_cast<VectorType>(I.getType())) { 2640 MVT::ValueType VT = TLI.getValueType(PTy); 2641 Result = DAG.getNode(ISD::BIT_CONVERT, VT, Result); 2642 } 2643 setValue(&I, Result); 2644 } 2645} 2646 2647/// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V. 2648static GlobalVariable *ExtractTypeInfo (Value *V) { 2649 V = IntrinsicInst::StripPointerCasts(V); 2650 GlobalVariable *GV = dyn_cast<GlobalVariable>(V); 2651 assert ((GV || isa<ConstantPointerNull>(V)) && 2652 "TypeInfo must be a global variable or NULL"); 2653 return GV; 2654} 2655 2656/// addCatchInfo - Extract the personality and type infos from an eh.selector 2657/// call, and add them to the specified machine basic block. 2658static void addCatchInfo(CallInst &I, MachineModuleInfo *MMI, 2659 MachineBasicBlock *MBB) { 2660 // Inform the MachineModuleInfo of the personality for this landing pad. 2661 ConstantExpr *CE = cast<ConstantExpr>(I.getOperand(2)); 2662 assert(CE->getOpcode() == Instruction::BitCast && 2663 isa<Function>(CE->getOperand(0)) && 2664 "Personality should be a function"); 2665 MMI->addPersonality(MBB, cast<Function>(CE->getOperand(0))); 2666 2667 // Gather all the type infos for this landing pad and pass them along to 2668 // MachineModuleInfo. 2669 std::vector<GlobalVariable *> TyInfo; 2670 unsigned N = I.getNumOperands(); 2671 2672 for (unsigned i = N - 1; i > 2; --i) { 2673 if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(i))) { 2674 unsigned FilterLength = CI->getZExtValue(); 2675 unsigned FirstCatch = i + FilterLength + !FilterLength; 2676 assert (FirstCatch <= N && "Invalid filter length"); 2677 2678 if (FirstCatch < N) { 2679 TyInfo.reserve(N - FirstCatch); 2680 for (unsigned j = FirstCatch; j < N; ++j) 2681 TyInfo.push_back(ExtractTypeInfo(I.getOperand(j))); 2682 MMI->addCatchTypeInfo(MBB, TyInfo); 2683 TyInfo.clear(); 2684 } 2685 2686 if (!FilterLength) { 2687 // Cleanup. 2688 MMI->addCleanup(MBB); 2689 } else { 2690 // Filter. 2691 TyInfo.reserve(FilterLength - 1); 2692 for (unsigned j = i + 1; j < FirstCatch; ++j) 2693 TyInfo.push_back(ExtractTypeInfo(I.getOperand(j))); 2694 MMI->addFilterTypeInfo(MBB, TyInfo); 2695 TyInfo.clear(); 2696 } 2697 2698 N = i; 2699 } 2700 } 2701 2702 if (N > 3) { 2703 TyInfo.reserve(N - 3); 2704 for (unsigned j = 3; j < N; ++j) 2705 TyInfo.push_back(ExtractTypeInfo(I.getOperand(j))); 2706 MMI->addCatchTypeInfo(MBB, TyInfo); 2707 } 2708} 2709 2710/// visitIntrinsicCall - Lower the call to the specified intrinsic function. If 2711/// we want to emit this as a call to a named external function, return the name 2712/// otherwise lower it and return null. 2713const char * 2714SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { 2715 switch (Intrinsic) { 2716 default: 2717 // By default, turn this into a target intrinsic node. 2718 visitTargetIntrinsic(I, Intrinsic); 2719 return 0; 2720 case Intrinsic::vastart: visitVAStart(I); return 0; 2721 case Intrinsic::vaend: visitVAEnd(I); return 0; 2722 case Intrinsic::vacopy: visitVACopy(I); return 0; 2723 case Intrinsic::returnaddress: 2724 setValue(&I, DAG.getNode(ISD::RETURNADDR, TLI.getPointerTy(), 2725 getValue(I.getOperand(1)))); 2726 return 0; 2727 case Intrinsic::frameaddress: 2728 setValue(&I, DAG.getNode(ISD::FRAMEADDR, TLI.getPointerTy(), 2729 getValue(I.getOperand(1)))); 2730 return 0; 2731 case Intrinsic::setjmp: 2732 return "_setjmp"+!TLI.usesUnderscoreSetJmp(); 2733 break; 2734 case Intrinsic::longjmp: 2735 return "_longjmp"+!TLI.usesUnderscoreLongJmp(); 2736 break; 2737 case Intrinsic::memcpy_i32: 2738 case Intrinsic::memcpy_i64: { 2739 SDOperand Op1 = getValue(I.getOperand(1)); 2740 SDOperand Op2 = getValue(I.getOperand(2)); 2741 SDOperand Op3 = getValue(I.getOperand(3)); 2742 unsigned Align = cast<ConstantInt>(I.getOperand(4))->getZExtValue(); 2743 DAG.setRoot(DAG.getMemcpy(getRoot(), Op1, Op2, Op3, Align, false, 2744 I.getOperand(1), 0, I.getOperand(2), 0)); 2745 return 0; 2746 } 2747 case Intrinsic::memset_i32: 2748 case Intrinsic::memset_i64: { 2749 SDOperand Op1 = getValue(I.getOperand(1)); 2750 SDOperand Op2 = getValue(I.getOperand(2)); 2751 SDOperand Op3 = getValue(I.getOperand(3)); 2752 unsigned Align = cast<ConstantInt>(I.getOperand(4))->getZExtValue(); 2753 DAG.setRoot(DAG.getMemset(getRoot(), Op1, Op2, Op3, Align, 2754 I.getOperand(1), 0)); 2755 return 0; 2756 } 2757 case Intrinsic::memmove_i32: 2758 case Intrinsic::memmove_i64: { 2759 SDOperand Op1 = getValue(I.getOperand(1)); 2760 SDOperand Op2 = getValue(I.getOperand(2)); 2761 SDOperand Op3 = getValue(I.getOperand(3)); 2762 unsigned Align = cast<ConstantInt>(I.getOperand(4))->getZExtValue(); 2763 2764 // If the source and destination are known to not be aliases, we can 2765 // lower memmove as memcpy. 2766 uint64_t Size = -1ULL; 2767 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op3)) 2768 Size = C->getValue(); 2769 if (AA.alias(I.getOperand(1), Size, I.getOperand(2), Size) == 2770 AliasAnalysis::NoAlias) { 2771 DAG.setRoot(DAG.getMemcpy(getRoot(), Op1, Op2, Op3, Align, false, 2772 I.getOperand(1), 0, I.getOperand(2), 0)); 2773 return 0; 2774 } 2775 2776 DAG.setRoot(DAG.getMemmove(getRoot(), Op1, Op2, Op3, Align, 2777 I.getOperand(1), 0, I.getOperand(2), 0)); 2778 return 0; 2779 } 2780 case Intrinsic::dbg_stoppoint: { 2781 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 2782 DbgStopPointInst &SPI = cast<DbgStopPointInst>(I); 2783 if (MMI && SPI.getContext() && MMI->Verify(SPI.getContext())) { 2784 SDOperand Ops[5]; 2785 2786 Ops[0] = getRoot(); 2787 Ops[1] = getValue(SPI.getLineValue()); 2788 Ops[2] = getValue(SPI.getColumnValue()); 2789 2790 DebugInfoDesc *DD = MMI->getDescFor(SPI.getContext()); 2791 assert(DD && "Not a debug information descriptor"); 2792 CompileUnitDesc *CompileUnit = cast<CompileUnitDesc>(DD); 2793 2794 Ops[3] = DAG.getString(CompileUnit->getFileName()); 2795 Ops[4] = DAG.getString(CompileUnit->getDirectory()); 2796 2797 DAG.setRoot(DAG.getNode(ISD::LOCATION, MVT::Other, Ops, 5)); 2798 } 2799 2800 return 0; 2801 } 2802 case Intrinsic::dbg_region_start: { 2803 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 2804 DbgRegionStartInst &RSI = cast<DbgRegionStartInst>(I); 2805 if (MMI && RSI.getContext() && MMI->Verify(RSI.getContext())) { 2806 unsigned LabelID = MMI->RecordRegionStart(RSI.getContext()); 2807 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(), 2808 DAG.getConstant(LabelID, MVT::i32), 2809 DAG.getConstant(0, MVT::i32))); 2810 } 2811 2812 return 0; 2813 } 2814 case Intrinsic::dbg_region_end: { 2815 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 2816 DbgRegionEndInst &REI = cast<DbgRegionEndInst>(I); 2817 if (MMI && REI.getContext() && MMI->Verify(REI.getContext())) { 2818 unsigned LabelID = MMI->RecordRegionEnd(REI.getContext()); 2819 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(), 2820 DAG.getConstant(LabelID, MVT::i32), 2821 DAG.getConstant(0, MVT::i32))); 2822 } 2823 2824 return 0; 2825 } 2826 case Intrinsic::dbg_func_start: { 2827 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 2828 if (!MMI) return 0; 2829 DbgFuncStartInst &FSI = cast<DbgFuncStartInst>(I); 2830 Value *SP = FSI.getSubprogram(); 2831 if (SP && MMI->Verify(SP)) { 2832 // llvm.dbg.func.start implicitly defines a dbg_stoppoint which is 2833 // what (most?) gdb expects. 2834 DebugInfoDesc *DD = MMI->getDescFor(SP); 2835 assert(DD && "Not a debug information descriptor"); 2836 SubprogramDesc *Subprogram = cast<SubprogramDesc>(DD); 2837 const CompileUnitDesc *CompileUnit = Subprogram->getFile(); 2838 unsigned SrcFile = MMI->RecordSource(CompileUnit->getDirectory(), 2839 CompileUnit->getFileName()); 2840 // Record the source line but does create a label. It will be emitted 2841 // at asm emission time. 2842 MMI->RecordSourceLine(Subprogram->getLine(), 0, SrcFile); 2843 } 2844 2845 return 0; 2846 } 2847 case Intrinsic::dbg_declare: { 2848 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 2849 DbgDeclareInst &DI = cast<DbgDeclareInst>(I); 2850 Value *Variable = DI.getVariable(); 2851 if (MMI && Variable && MMI->Verify(Variable)) 2852 DAG.setRoot(DAG.getNode(ISD::DECLARE, MVT::Other, getRoot(), 2853 getValue(DI.getAddress()), getValue(Variable))); 2854 return 0; 2855 } 2856 2857 case Intrinsic::eh_exception: { 2858 if (!CurMBB->isLandingPad()) { 2859 // FIXME: Mark exception register as live in. Hack for PR1508. 2860 unsigned Reg = TLI.getExceptionAddressRegister(); 2861 if (Reg) CurMBB->addLiveIn(Reg); 2862 } 2863 // Insert the EXCEPTIONADDR instruction. 2864 SDVTList VTs = DAG.getVTList(TLI.getPointerTy(), MVT::Other); 2865 SDOperand Ops[1]; 2866 Ops[0] = DAG.getRoot(); 2867 SDOperand Op = DAG.getNode(ISD::EXCEPTIONADDR, VTs, Ops, 1); 2868 setValue(&I, Op); 2869 DAG.setRoot(Op.getValue(1)); 2870 return 0; 2871 } 2872 2873 case Intrinsic::eh_selector_i32: 2874 case Intrinsic::eh_selector_i64: { 2875 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 2876 MVT::ValueType VT = (Intrinsic == Intrinsic::eh_selector_i32 ? 2877 MVT::i32 : MVT::i64); 2878 2879 if (MMI) { 2880 if (CurMBB->isLandingPad()) 2881 addCatchInfo(I, MMI, CurMBB); 2882 else { 2883#ifndef NDEBUG 2884 FuncInfo.CatchInfoLost.insert(&I); 2885#endif 2886 // FIXME: Mark exception selector register as live in. Hack for PR1508. 2887 unsigned Reg = TLI.getExceptionSelectorRegister(); 2888 if (Reg) CurMBB->addLiveIn(Reg); 2889 } 2890 2891 // Insert the EHSELECTION instruction. 2892 SDVTList VTs = DAG.getVTList(VT, MVT::Other); 2893 SDOperand Ops[2]; 2894 Ops[0] = getValue(I.getOperand(1)); 2895 Ops[1] = getRoot(); 2896 SDOperand Op = DAG.getNode(ISD::EHSELECTION, VTs, Ops, 2); 2897 setValue(&I, Op); 2898 DAG.setRoot(Op.getValue(1)); 2899 } else { 2900 setValue(&I, DAG.getConstant(0, VT)); 2901 } 2902 2903 return 0; 2904 } 2905 2906 case Intrinsic::eh_typeid_for_i32: 2907 case Intrinsic::eh_typeid_for_i64: { 2908 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 2909 MVT::ValueType VT = (Intrinsic == Intrinsic::eh_typeid_for_i32 ? 2910 MVT::i32 : MVT::i64); 2911 2912 if (MMI) { 2913 // Find the type id for the given typeinfo. 2914 GlobalVariable *GV = ExtractTypeInfo(I.getOperand(1)); 2915 2916 unsigned TypeID = MMI->getTypeIDFor(GV); 2917 setValue(&I, DAG.getConstant(TypeID, VT)); 2918 } else { 2919 // Return something different to eh_selector. 2920 setValue(&I, DAG.getConstant(1, VT)); 2921 } 2922 2923 return 0; 2924 } 2925 2926 case Intrinsic::eh_return: { 2927 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 2928 2929 if (MMI) { 2930 MMI->setCallsEHReturn(true); 2931 DAG.setRoot(DAG.getNode(ISD::EH_RETURN, 2932 MVT::Other, 2933 getControlRoot(), 2934 getValue(I.getOperand(1)), 2935 getValue(I.getOperand(2)))); 2936 } else { 2937 setValue(&I, DAG.getConstant(0, TLI.getPointerTy())); 2938 } 2939 2940 return 0; 2941 } 2942 2943 case Intrinsic::eh_unwind_init: { 2944 if (MachineModuleInfo *MMI = DAG.getMachineModuleInfo()) { 2945 MMI->setCallsUnwindInit(true); 2946 } 2947 2948 return 0; 2949 } 2950 2951 case Intrinsic::eh_dwarf_cfa: { 2952 MVT::ValueType VT = getValue(I.getOperand(1)).getValueType(); 2953 SDOperand CfaArg; 2954 if (MVT::getSizeInBits(VT) > MVT::getSizeInBits(TLI.getPointerTy())) 2955 CfaArg = DAG.getNode(ISD::TRUNCATE, 2956 TLI.getPointerTy(), getValue(I.getOperand(1))); 2957 else 2958 CfaArg = DAG.getNode(ISD::SIGN_EXTEND, 2959 TLI.getPointerTy(), getValue(I.getOperand(1))); 2960 2961 SDOperand Offset = DAG.getNode(ISD::ADD, 2962 TLI.getPointerTy(), 2963 DAG.getNode(ISD::FRAME_TO_ARGS_OFFSET, 2964 TLI.getPointerTy()), 2965 CfaArg); 2966 setValue(&I, DAG.getNode(ISD::ADD, 2967 TLI.getPointerTy(), 2968 DAG.getNode(ISD::FRAMEADDR, 2969 TLI.getPointerTy(), 2970 DAG.getConstant(0, 2971 TLI.getPointerTy())), 2972 Offset)); 2973 return 0; 2974 } 2975 2976 case Intrinsic::sqrt: 2977 setValue(&I, DAG.getNode(ISD::FSQRT, 2978 getValue(I.getOperand(1)).getValueType(), 2979 getValue(I.getOperand(1)))); 2980 return 0; 2981 case Intrinsic::powi: 2982 setValue(&I, DAG.getNode(ISD::FPOWI, 2983 getValue(I.getOperand(1)).getValueType(), 2984 getValue(I.getOperand(1)), 2985 getValue(I.getOperand(2)))); 2986 return 0; 2987 case Intrinsic::sin: 2988 setValue(&I, DAG.getNode(ISD::FSIN, 2989 getValue(I.getOperand(1)).getValueType(), 2990 getValue(I.getOperand(1)))); 2991 return 0; 2992 case Intrinsic::cos: 2993 setValue(&I, DAG.getNode(ISD::FCOS, 2994 getValue(I.getOperand(1)).getValueType(), 2995 getValue(I.getOperand(1)))); 2996 return 0; 2997 case Intrinsic::pow: 2998 setValue(&I, DAG.getNode(ISD::FPOW, 2999 getValue(I.getOperand(1)).getValueType(), 3000 getValue(I.getOperand(1)), 3001 getValue(I.getOperand(2)))); 3002 return 0; 3003 case Intrinsic::pcmarker: { 3004 SDOperand Tmp = getValue(I.getOperand(1)); 3005 DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp)); 3006 return 0; 3007 } 3008 case Intrinsic::readcyclecounter: { 3009 SDOperand Op = getRoot(); 3010 SDOperand Tmp = DAG.getNode(ISD::READCYCLECOUNTER, 3011 DAG.getNodeValueTypes(MVT::i64, MVT::Other), 2, 3012 &Op, 1); 3013 setValue(&I, Tmp); 3014 DAG.setRoot(Tmp.getValue(1)); 3015 return 0; 3016 } 3017 case Intrinsic::part_select: { 3018 // Currently not implemented: just abort 3019 assert(0 && "part_select intrinsic not implemented"); 3020 abort(); 3021 } 3022 case Intrinsic::part_set: { 3023 // Currently not implemented: just abort 3024 assert(0 && "part_set intrinsic not implemented"); 3025 abort(); 3026 } 3027 case Intrinsic::bswap: 3028 setValue(&I, DAG.getNode(ISD::BSWAP, 3029 getValue(I.getOperand(1)).getValueType(), 3030 getValue(I.getOperand(1)))); 3031 return 0; 3032 case Intrinsic::cttz: { 3033 SDOperand Arg = getValue(I.getOperand(1)); 3034 MVT::ValueType Ty = Arg.getValueType(); 3035 SDOperand result = DAG.getNode(ISD::CTTZ, Ty, Arg); 3036 setValue(&I, result); 3037 return 0; 3038 } 3039 case Intrinsic::ctlz: { 3040 SDOperand Arg = getValue(I.getOperand(1)); 3041 MVT::ValueType Ty = Arg.getValueType(); 3042 SDOperand result = DAG.getNode(ISD::CTLZ, Ty, Arg); 3043 setValue(&I, result); 3044 return 0; 3045 } 3046 case Intrinsic::ctpop: { 3047 SDOperand Arg = getValue(I.getOperand(1)); 3048 MVT::ValueType Ty = Arg.getValueType(); 3049 SDOperand result = DAG.getNode(ISD::CTPOP, Ty, Arg); 3050 setValue(&I, result); 3051 return 0; 3052 } 3053 case Intrinsic::stacksave: { 3054 SDOperand Op = getRoot(); 3055 SDOperand Tmp = DAG.getNode(ISD::STACKSAVE, 3056 DAG.getNodeValueTypes(TLI.getPointerTy(), MVT::Other), 2, &Op, 1); 3057 setValue(&I, Tmp); 3058 DAG.setRoot(Tmp.getValue(1)); 3059 return 0; 3060 } 3061 case Intrinsic::stackrestore: { 3062 SDOperand Tmp = getValue(I.getOperand(1)); 3063 DAG.setRoot(DAG.getNode(ISD::STACKRESTORE, MVT::Other, getRoot(), Tmp)); 3064 return 0; 3065 } 3066 case Intrinsic::var_annotation: 3067 // Discard annotate attributes 3068 return 0; 3069 3070 case Intrinsic::init_trampoline: { 3071 const Function *F = 3072 cast<Function>(IntrinsicInst::StripPointerCasts(I.getOperand(2))); 3073 3074 SDOperand Ops[6]; 3075 Ops[0] = getRoot(); 3076 Ops[1] = getValue(I.getOperand(1)); 3077 Ops[2] = getValue(I.getOperand(2)); 3078 Ops[3] = getValue(I.getOperand(3)); 3079 Ops[4] = DAG.getSrcValue(I.getOperand(1)); 3080 Ops[5] = DAG.getSrcValue(F); 3081 3082 SDOperand Tmp = DAG.getNode(ISD::TRAMPOLINE, 3083 DAG.getNodeValueTypes(TLI.getPointerTy(), 3084 MVT::Other), 2, 3085 Ops, 6); 3086 3087 setValue(&I, Tmp); 3088 DAG.setRoot(Tmp.getValue(1)); 3089 return 0; 3090 } 3091 3092 case Intrinsic::gcroot: 3093 if (GCI) { 3094 Value *Alloca = I.getOperand(1); 3095 Constant *TypeMap = cast<Constant>(I.getOperand(2)); 3096 3097 FrameIndexSDNode *FI = cast<FrameIndexSDNode>(getValue(Alloca).Val); 3098 GCI->addStackRoot(FI->getIndex(), TypeMap); 3099 } 3100 return 0; 3101 3102 case Intrinsic::gcread: 3103 case Intrinsic::gcwrite: 3104 assert(0 && "Collector failed to lower gcread/gcwrite intrinsics!"); 3105 return 0; 3106 3107 case Intrinsic::flt_rounds: { 3108 setValue(&I, DAG.getNode(ISD::FLT_ROUNDS_, MVT::i32)); 3109 return 0; 3110 } 3111 3112 case Intrinsic::trap: { 3113 DAG.setRoot(DAG.getNode(ISD::TRAP, MVT::Other, getRoot())); 3114 return 0; 3115 } 3116 case Intrinsic::prefetch: { 3117 SDOperand Ops[4]; 3118 Ops[0] = getRoot(); 3119 Ops[1] = getValue(I.getOperand(1)); 3120 Ops[2] = getValue(I.getOperand(2)); 3121 Ops[3] = getValue(I.getOperand(3)); 3122 DAG.setRoot(DAG.getNode(ISD::PREFETCH, MVT::Other, &Ops[0], 4)); 3123 return 0; 3124 } 3125 3126 case Intrinsic::memory_barrier: { 3127 SDOperand Ops[6]; 3128 Ops[0] = getRoot(); 3129 for (int x = 1; x < 6; ++x) 3130 Ops[x] = getValue(I.getOperand(x)); 3131 3132 DAG.setRoot(DAG.getNode(ISD::MEMBARRIER, MVT::Other, &Ops[0], 6)); 3133 return 0; 3134 } 3135 case Intrinsic::atomic_lcs: { 3136 SDOperand Root = getRoot(); 3137 SDOperand O3 = getValue(I.getOperand(3)); 3138 SDOperand L = DAG.getAtomic(ISD::ATOMIC_LCS, Root, 3139 getValue(I.getOperand(1)), 3140 getValue(I.getOperand(2)), 3141 O3, O3.getValueType()); 3142 setValue(&I, L); 3143 DAG.setRoot(L.getValue(1)); 3144 return 0; 3145 } 3146 case Intrinsic::atomic_las: { 3147 SDOperand Root = getRoot(); 3148 SDOperand O2 = getValue(I.getOperand(2)); 3149 SDOperand L = DAG.getAtomic(ISD::ATOMIC_LAS, Root, 3150 getValue(I.getOperand(1)), 3151 O2, O2.getValueType()); 3152 setValue(&I, L); 3153 DAG.setRoot(L.getValue(1)); 3154 return 0; 3155 } 3156 case Intrinsic::atomic_swap: { 3157 SDOperand Root = getRoot(); 3158 SDOperand O2 = getValue(I.getOperand(2)); 3159 SDOperand L = DAG.getAtomic(ISD::ATOMIC_SWAP, Root, 3160 getValue(I.getOperand(1)), 3161 O2, O2.getValueType()); 3162 setValue(&I, L); 3163 DAG.setRoot(L.getValue(1)); 3164 return 0; 3165 } 3166 3167 } 3168} 3169 3170 3171void SelectionDAGLowering::LowerCallTo(CallSite CS, SDOperand Callee, 3172 bool IsTailCall, 3173 MachineBasicBlock *LandingPad) { 3174 const PointerType *PT = cast<PointerType>(CS.getCalledValue()->getType()); 3175 const FunctionType *FTy = cast<FunctionType>(PT->getElementType()); 3176 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 3177 unsigned BeginLabel = 0, EndLabel = 0; 3178 3179 TargetLowering::ArgListTy Args; 3180 TargetLowering::ArgListEntry Entry; 3181 Args.reserve(CS.arg_size()); 3182 for (CallSite::arg_iterator i = CS.arg_begin(), e = CS.arg_end(); 3183 i != e; ++i) { 3184 SDOperand ArgNode = getValue(*i); 3185 Entry.Node = ArgNode; Entry.Ty = (*i)->getType(); 3186 3187 unsigned attrInd = i - CS.arg_begin() + 1; 3188 Entry.isSExt = CS.paramHasAttr(attrInd, ParamAttr::SExt); 3189 Entry.isZExt = CS.paramHasAttr(attrInd, ParamAttr::ZExt); 3190 Entry.isInReg = CS.paramHasAttr(attrInd, ParamAttr::InReg); 3191 Entry.isSRet = CS.paramHasAttr(attrInd, ParamAttr::StructRet); 3192 Entry.isNest = CS.paramHasAttr(attrInd, ParamAttr::Nest); 3193 Entry.isByVal = CS.paramHasAttr(attrInd, ParamAttr::ByVal); 3194 Entry.Alignment = CS.getParamAlignment(attrInd); 3195 Args.push_back(Entry); 3196 } 3197 3198 if (LandingPad && MMI) { 3199 // Insert a label before the invoke call to mark the try range. This can be 3200 // used to detect deletion of the invoke via the MachineModuleInfo. 3201 BeginLabel = MMI->NextLabelID(); 3202 // Both PendingLoads and PendingExports must be flushed here; 3203 // this call might not return. 3204 (void)getRoot(); 3205 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getControlRoot(), 3206 DAG.getConstant(BeginLabel, MVT::i32), 3207 DAG.getConstant(1, MVT::i32))); 3208 } 3209 3210 std::pair<SDOperand,SDOperand> Result = 3211 TLI.LowerCallTo(getRoot(), CS.getType(), 3212 CS.paramHasAttr(0, ParamAttr::SExt), 3213 CS.paramHasAttr(0, ParamAttr::ZExt), 3214 FTy->isVarArg(), CS.getCallingConv(), IsTailCall, 3215 Callee, Args, DAG); 3216 if (CS.getType() != Type::VoidTy) 3217 setValue(CS.getInstruction(), Result.first); 3218 DAG.setRoot(Result.second); 3219 3220 if (LandingPad && MMI) { 3221 // Insert a label at the end of the invoke call to mark the try range. This 3222 // can be used to detect deletion of the invoke via the MachineModuleInfo. 3223 EndLabel = MMI->NextLabelID(); 3224 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(), 3225 DAG.getConstant(EndLabel, MVT::i32), 3226 DAG.getConstant(1, MVT::i32))); 3227 3228 // Inform MachineModuleInfo of range. 3229 MMI->addInvoke(LandingPad, BeginLabel, EndLabel); 3230 } 3231} 3232 3233 3234void SelectionDAGLowering::visitCall(CallInst &I) { 3235 const char *RenameFn = 0; 3236 if (Function *F = I.getCalledFunction()) { 3237 if (F->isDeclaration()) { 3238 if (unsigned IID = F->getIntrinsicID()) { 3239 RenameFn = visitIntrinsicCall(I, IID); 3240 if (!RenameFn) 3241 return; 3242 } 3243 } 3244 3245 // Check for well-known libc/libm calls. If the function is internal, it 3246 // can't be a library call. 3247 unsigned NameLen = F->getNameLen(); 3248 if (!F->hasInternalLinkage() && NameLen) { 3249 const char *NameStr = F->getNameStart(); 3250 if (NameStr[0] == 'c' && 3251 ((NameLen == 8 && !strcmp(NameStr, "copysign")) || 3252 (NameLen == 9 && !strcmp(NameStr, "copysignf")))) { 3253 if (I.getNumOperands() == 3 && // Basic sanity checks. 3254 I.getOperand(1)->getType()->isFloatingPoint() && 3255 I.getType() == I.getOperand(1)->getType() && 3256 I.getType() == I.getOperand(2)->getType()) { 3257 SDOperand LHS = getValue(I.getOperand(1)); 3258 SDOperand RHS = getValue(I.getOperand(2)); 3259 setValue(&I, DAG.getNode(ISD::FCOPYSIGN, LHS.getValueType(), 3260 LHS, RHS)); 3261 return; 3262 } 3263 } else if (NameStr[0] == 'f' && 3264 ((NameLen == 4 && !strcmp(NameStr, "fabs")) || 3265 (NameLen == 5 && !strcmp(NameStr, "fabsf")) || 3266 (NameLen == 5 && !strcmp(NameStr, "fabsl")))) { 3267 if (I.getNumOperands() == 2 && // Basic sanity checks. 3268 I.getOperand(1)->getType()->isFloatingPoint() && 3269 I.getType() == I.getOperand(1)->getType()) { 3270 SDOperand Tmp = getValue(I.getOperand(1)); 3271 setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp)); 3272 return; 3273 } 3274 } else if (NameStr[0] == 's' && 3275 ((NameLen == 3 && !strcmp(NameStr, "sin")) || 3276 (NameLen == 4 && !strcmp(NameStr, "sinf")) || 3277 (NameLen == 4 && !strcmp(NameStr, "sinl")))) { 3278 if (I.getNumOperands() == 2 && // Basic sanity checks. 3279 I.getOperand(1)->getType()->isFloatingPoint() && 3280 I.getType() == I.getOperand(1)->getType()) { 3281 SDOperand Tmp = getValue(I.getOperand(1)); 3282 setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp)); 3283 return; 3284 } 3285 } else if (NameStr[0] == 'c' && 3286 ((NameLen == 3 && !strcmp(NameStr, "cos")) || 3287 (NameLen == 4 && !strcmp(NameStr, "cosf")) || 3288 (NameLen == 4 && !strcmp(NameStr, "cosl")))) { 3289 if (I.getNumOperands() == 2 && // Basic sanity checks. 3290 I.getOperand(1)->getType()->isFloatingPoint() && 3291 I.getType() == I.getOperand(1)->getType()) { 3292 SDOperand Tmp = getValue(I.getOperand(1)); 3293 setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp)); 3294 return; 3295 } 3296 } 3297 } 3298 } else if (isa<InlineAsm>(I.getOperand(0))) { 3299 visitInlineAsm(&I); 3300 return; 3301 } 3302 3303 SDOperand Callee; 3304 if (!RenameFn) 3305 Callee = getValue(I.getOperand(0)); 3306 else 3307 Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy()); 3308 3309 LowerCallTo(&I, Callee, I.isTailCall()); 3310} 3311 3312 3313void SelectionDAGLowering::visitGetResult(GetResultInst &I) { 3314 SDOperand Call = getValue(I.getOperand(0)); 3315 setValue(&I, SDOperand(Call.Val, I.getIndex())); 3316} 3317 3318 3319/// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from 3320/// this value and returns the result as a ValueVT value. This uses 3321/// Chain/Flag as the input and updates them for the output Chain/Flag. 3322/// If the Flag pointer is NULL, no flag is used. 3323SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG, 3324 SDOperand &Chain, SDOperand *Flag)const{ 3325 // Copy the legal parts from the registers. 3326 unsigned NumParts = Regs.size(); 3327 SmallVector<SDOperand, 8> Parts(NumParts); 3328 for (unsigned i = 0; i != NumParts; ++i) { 3329 SDOperand Part = Flag ? 3330 DAG.getCopyFromReg(Chain, Regs[i], RegVT, *Flag) : 3331 DAG.getCopyFromReg(Chain, Regs[i], RegVT); 3332 Chain = Part.getValue(1); 3333 if (Flag) 3334 *Flag = Part.getValue(2); 3335 Parts[i] = Part; 3336 } 3337 3338 // Assemble the legal parts into the final value. 3339 return getCopyFromParts(DAG, &Parts[0], NumParts, RegVT, ValueVT); 3340} 3341 3342/// getCopyToRegs - Emit a series of CopyToReg nodes that copies the 3343/// specified value into the registers specified by this object. This uses 3344/// Chain/Flag as the input and updates them for the output Chain/Flag. 3345/// If the Flag pointer is NULL, no flag is used. 3346void RegsForValue::getCopyToRegs(SDOperand Val, SelectionDAG &DAG, 3347 SDOperand &Chain, SDOperand *Flag) const { 3348 // Get the list of the values's legal parts. 3349 unsigned NumParts = Regs.size(); 3350 SmallVector<SDOperand, 8> Parts(NumParts); 3351 getCopyToParts(DAG, Val, &Parts[0], NumParts, RegVT); 3352 3353 // Copy the parts into the registers. 3354 for (unsigned i = 0; i != NumParts; ++i) { 3355 SDOperand Part = Flag ? 3356 DAG.getCopyToReg(Chain, Regs[i], Parts[i], *Flag) : 3357 DAG.getCopyToReg(Chain, Regs[i], Parts[i]); 3358 Chain = Part.getValue(0); 3359 if (Flag) 3360 *Flag = Part.getValue(1); 3361 } 3362} 3363 3364/// AddInlineAsmOperands - Add this value to the specified inlineasm node 3365/// operand list. This adds the code marker and includes the number of 3366/// values added into it. 3367void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG, 3368 std::vector<SDOperand> &Ops) const { 3369 MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy(); 3370 Ops.push_back(DAG.getTargetConstant(Code | (Regs.size() << 3), IntPtrTy)); 3371 for (unsigned i = 0, e = Regs.size(); i != e; ++i) 3372 Ops.push_back(DAG.getRegister(Regs[i], RegVT)); 3373} 3374 3375/// isAllocatableRegister - If the specified register is safe to allocate, 3376/// i.e. it isn't a stack pointer or some other special register, return the 3377/// register class for the register. Otherwise, return null. 3378static const TargetRegisterClass * 3379isAllocatableRegister(unsigned Reg, MachineFunction &MF, 3380 const TargetLowering &TLI, 3381 const TargetRegisterInfo *TRI) { 3382 MVT::ValueType FoundVT = MVT::Other; 3383 const TargetRegisterClass *FoundRC = 0; 3384 for (TargetRegisterInfo::regclass_iterator RCI = TRI->regclass_begin(), 3385 E = TRI->regclass_end(); RCI != E; ++RCI) { 3386 MVT::ValueType ThisVT = MVT::Other; 3387 3388 const TargetRegisterClass *RC = *RCI; 3389 // If none of the the value types for this register class are valid, we 3390 // can't use it. For example, 64-bit reg classes on 32-bit targets. 3391 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end(); 3392 I != E; ++I) { 3393 if (TLI.isTypeLegal(*I)) { 3394 // If we have already found this register in a different register class, 3395 // choose the one with the largest VT specified. For example, on 3396 // PowerPC, we favor f64 register classes over f32. 3397 if (FoundVT == MVT::Other || 3398 MVT::getSizeInBits(FoundVT) < MVT::getSizeInBits(*I)) { 3399 ThisVT = *I; 3400 break; 3401 } 3402 } 3403 } 3404 3405 if (ThisVT == MVT::Other) continue; 3406 3407 // NOTE: This isn't ideal. In particular, this might allocate the 3408 // frame pointer in functions that need it (due to them not being taken 3409 // out of allocation, because a variable sized allocation hasn't been seen 3410 // yet). This is a slight code pessimization, but should still work. 3411 for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF), 3412 E = RC->allocation_order_end(MF); I != E; ++I) 3413 if (*I == Reg) { 3414 // We found a matching register class. Keep looking at others in case 3415 // we find one with larger registers that this physreg is also in. 3416 FoundRC = RC; 3417 FoundVT = ThisVT; 3418 break; 3419 } 3420 } 3421 return FoundRC; 3422} 3423 3424 3425namespace { 3426/// AsmOperandInfo - This contains information for each constraint that we are 3427/// lowering. 3428struct SDISelAsmOperandInfo : public TargetLowering::AsmOperandInfo { 3429 /// CallOperand - If this is the result output operand or a clobber 3430 /// this is null, otherwise it is the incoming operand to the CallInst. 3431 /// This gets modified as the asm is processed. 3432 SDOperand CallOperand; 3433 3434 /// AssignedRegs - If this is a register or register class operand, this 3435 /// contains the set of register corresponding to the operand. 3436 RegsForValue AssignedRegs; 3437 3438 SDISelAsmOperandInfo(const InlineAsm::ConstraintInfo &info) 3439 : TargetLowering::AsmOperandInfo(info), CallOperand(0,0) { 3440 } 3441 3442 /// MarkAllocatedRegs - Once AssignedRegs is set, mark the assigned registers 3443 /// busy in OutputRegs/InputRegs. 3444 void MarkAllocatedRegs(bool isOutReg, bool isInReg, 3445 std::set<unsigned> &OutputRegs, 3446 std::set<unsigned> &InputRegs, 3447 const TargetRegisterInfo &TRI) const { 3448 if (isOutReg) { 3449 for (unsigned i = 0, e = AssignedRegs.Regs.size(); i != e; ++i) 3450 MarkRegAndAliases(AssignedRegs.Regs[i], OutputRegs, TRI); 3451 } 3452 if (isInReg) { 3453 for (unsigned i = 0, e = AssignedRegs.Regs.size(); i != e; ++i) 3454 MarkRegAndAliases(AssignedRegs.Regs[i], InputRegs, TRI); 3455 } 3456 } 3457 3458private: 3459 /// MarkRegAndAliases - Mark the specified register and all aliases in the 3460 /// specified set. 3461 static void MarkRegAndAliases(unsigned Reg, std::set<unsigned> &Regs, 3462 const TargetRegisterInfo &TRI) { 3463 assert(TargetRegisterInfo::isPhysicalRegister(Reg) && "Isn't a physreg"); 3464 Regs.insert(Reg); 3465 if (const unsigned *Aliases = TRI.getAliasSet(Reg)) 3466 for (; *Aliases; ++Aliases) 3467 Regs.insert(*Aliases); 3468 } 3469}; 3470} // end anon namespace. 3471 3472 3473/// GetRegistersForValue - Assign registers (virtual or physical) for the 3474/// specified operand. We prefer to assign virtual registers, to allow the 3475/// register allocator handle the assignment process. However, if the asm uses 3476/// features that we can't model on machineinstrs, we have SDISel do the 3477/// allocation. This produces generally horrible, but correct, code. 3478/// 3479/// OpInfo describes the operand. 3480/// HasEarlyClobber is true if there are any early clobber constraints (=&r) 3481/// or any explicitly clobbered registers. 3482/// Input and OutputRegs are the set of already allocated physical registers. 3483/// 3484void SelectionDAGLowering:: 3485GetRegistersForValue(SDISelAsmOperandInfo &OpInfo, bool HasEarlyClobber, 3486 std::set<unsigned> &OutputRegs, 3487 std::set<unsigned> &InputRegs) { 3488 // Compute whether this value requires an input register, an output register, 3489 // or both. 3490 bool isOutReg = false; 3491 bool isInReg = false; 3492 switch (OpInfo.Type) { 3493 case InlineAsm::isOutput: 3494 isOutReg = true; 3495 3496 // If this is an early-clobber output, or if there is an input 3497 // constraint that matches this, we need to reserve the input register 3498 // so no other inputs allocate to it. 3499 isInReg = OpInfo.isEarlyClobber || OpInfo.hasMatchingInput; 3500 break; 3501 case InlineAsm::isInput: 3502 isInReg = true; 3503 isOutReg = false; 3504 break; 3505 case InlineAsm::isClobber: 3506 isOutReg = true; 3507 isInReg = true; 3508 break; 3509 } 3510 3511 3512 MachineFunction &MF = DAG.getMachineFunction(); 3513 std::vector<unsigned> Regs; 3514 3515 // If this is a constraint for a single physreg, or a constraint for a 3516 // register class, find it. 3517 std::pair<unsigned, const TargetRegisterClass*> PhysReg = 3518 TLI.getRegForInlineAsmConstraint(OpInfo.ConstraintCode, 3519 OpInfo.ConstraintVT); 3520 3521 unsigned NumRegs = 1; 3522 if (OpInfo.ConstraintVT != MVT::Other) 3523 NumRegs = TLI.getNumRegisters(OpInfo.ConstraintVT); 3524 MVT::ValueType RegVT; 3525 MVT::ValueType ValueVT = OpInfo.ConstraintVT; 3526 3527 3528 // If this is a constraint for a specific physical register, like {r17}, 3529 // assign it now. 3530 if (PhysReg.first) { 3531 if (OpInfo.ConstraintVT == MVT::Other) 3532 ValueVT = *PhysReg.second->vt_begin(); 3533 3534 // Get the actual register value type. This is important, because the user 3535 // may have asked for (e.g.) the AX register in i32 type. We need to 3536 // remember that AX is actually i16 to get the right extension. 3537 RegVT = *PhysReg.second->vt_begin(); 3538 3539 // This is a explicit reference to a physical register. 3540 Regs.push_back(PhysReg.first); 3541 3542 // If this is an expanded reference, add the rest of the regs to Regs. 3543 if (NumRegs != 1) { 3544 TargetRegisterClass::iterator I = PhysReg.second->begin(); 3545 TargetRegisterClass::iterator E = PhysReg.second->end(); 3546 for (; *I != PhysReg.first; ++I) 3547 assert(I != E && "Didn't find reg!"); 3548 3549 // Already added the first reg. 3550 --NumRegs; ++I; 3551 for (; NumRegs; --NumRegs, ++I) { 3552 assert(I != E && "Ran out of registers to allocate!"); 3553 Regs.push_back(*I); 3554 } 3555 } 3556 OpInfo.AssignedRegs = RegsForValue(Regs, RegVT, ValueVT); 3557 const TargetRegisterInfo *TRI = DAG.getTarget().getRegisterInfo(); 3558 OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs, *TRI); 3559 return; 3560 } 3561 3562 // Otherwise, if this was a reference to an LLVM register class, create vregs 3563 // for this reference. 3564 std::vector<unsigned> RegClassRegs; 3565 const TargetRegisterClass *RC = PhysReg.second; 3566 if (RC) { 3567 // If this is an early clobber or tied register, our regalloc doesn't know 3568 // how to maintain the constraint. If it isn't, go ahead and create vreg 3569 // and let the regalloc do the right thing. 3570 if (!OpInfo.hasMatchingInput && !OpInfo.isEarlyClobber && 3571 // If there is some other early clobber and this is an input register, 3572 // then we are forced to pre-allocate the input reg so it doesn't 3573 // conflict with the earlyclobber. 3574 !(OpInfo.Type == InlineAsm::isInput && HasEarlyClobber)) { 3575 RegVT = *PhysReg.second->vt_begin(); 3576 3577 if (OpInfo.ConstraintVT == MVT::Other) 3578 ValueVT = RegVT; 3579 3580 // Create the appropriate number of virtual registers. 3581 MachineRegisterInfo &RegInfo = MF.getRegInfo(); 3582 for (; NumRegs; --NumRegs) 3583 Regs.push_back(RegInfo.createVirtualRegister(PhysReg.second)); 3584 3585 OpInfo.AssignedRegs = RegsForValue(Regs, RegVT, ValueVT); 3586 return; 3587 } 3588 3589 // Otherwise, we can't allocate it. Let the code below figure out how to 3590 // maintain these constraints. 3591 RegClassRegs.assign(PhysReg.second->begin(), PhysReg.second->end()); 3592 3593 } else { 3594 // This is a reference to a register class that doesn't directly correspond 3595 // to an LLVM register class. Allocate NumRegs consecutive, available, 3596 // registers from the class. 3597 RegClassRegs = TLI.getRegClassForInlineAsmConstraint(OpInfo.ConstraintCode, 3598 OpInfo.ConstraintVT); 3599 } 3600 3601 const TargetRegisterInfo *TRI = DAG.getTarget().getRegisterInfo(); 3602 unsigned NumAllocated = 0; 3603 for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) { 3604 unsigned Reg = RegClassRegs[i]; 3605 // See if this register is available. 3606 if ((isOutReg && OutputRegs.count(Reg)) || // Already used. 3607 (isInReg && InputRegs.count(Reg))) { // Already used. 3608 // Make sure we find consecutive registers. 3609 NumAllocated = 0; 3610 continue; 3611 } 3612 3613 // Check to see if this register is allocatable (i.e. don't give out the 3614 // stack pointer). 3615 if (RC == 0) { 3616 RC = isAllocatableRegister(Reg, MF, TLI, TRI); 3617 if (!RC) { // Couldn't allocate this register. 3618 // Reset NumAllocated to make sure we return consecutive registers. 3619 NumAllocated = 0; 3620 continue; 3621 } 3622 } 3623 3624 // Okay, this register is good, we can use it. 3625 ++NumAllocated; 3626 3627 // If we allocated enough consecutive registers, succeed. 3628 if (NumAllocated == NumRegs) { 3629 unsigned RegStart = (i-NumAllocated)+1; 3630 unsigned RegEnd = i+1; 3631 // Mark all of the allocated registers used. 3632 for (unsigned i = RegStart; i != RegEnd; ++i) 3633 Regs.push_back(RegClassRegs[i]); 3634 3635 OpInfo.AssignedRegs = RegsForValue(Regs, *RC->vt_begin(), 3636 OpInfo.ConstraintVT); 3637 OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs, *TRI); 3638 return; 3639 } 3640 } 3641 3642 // Otherwise, we couldn't allocate enough registers for this. 3643 return; 3644} 3645 3646 3647/// visitInlineAsm - Handle a call to an InlineAsm object. 3648/// 3649void SelectionDAGLowering::visitInlineAsm(CallSite CS) { 3650 InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue()); 3651 3652 /// ConstraintOperands - Information about all of the constraints. 3653 std::vector<SDISelAsmOperandInfo> ConstraintOperands; 3654 3655 SDOperand Chain = getRoot(); 3656 SDOperand Flag; 3657 3658 std::set<unsigned> OutputRegs, InputRegs; 3659 3660 // Do a prepass over the constraints, canonicalizing them, and building up the 3661 // ConstraintOperands list. 3662 std::vector<InlineAsm::ConstraintInfo> 3663 ConstraintInfos = IA->ParseConstraints(); 3664 3665 // SawEarlyClobber - Keep track of whether we saw an earlyclobber output 3666 // constraint. If so, we can't let the register allocator allocate any input 3667 // registers, because it will not know to avoid the earlyclobbered output reg. 3668 bool SawEarlyClobber = false; 3669 3670 unsigned ArgNo = 0; // ArgNo - The argument of the CallInst. 3671 for (unsigned i = 0, e = ConstraintInfos.size(); i != e; ++i) { 3672 ConstraintOperands.push_back(SDISelAsmOperandInfo(ConstraintInfos[i])); 3673 SDISelAsmOperandInfo &OpInfo = ConstraintOperands.back(); 3674 3675 MVT::ValueType OpVT = MVT::Other; 3676 3677 // Compute the value type for each operand. 3678 switch (OpInfo.Type) { 3679 case InlineAsm::isOutput: 3680 if (!OpInfo.isIndirect) { 3681 // The return value of the call is this value. As such, there is no 3682 // corresponding argument. 3683 assert(CS.getType() != Type::VoidTy && "Bad inline asm!"); 3684 OpVT = TLI.getValueType(CS.getType()); 3685 } else { 3686 OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 3687 } 3688 break; 3689 case InlineAsm::isInput: 3690 OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 3691 break; 3692 case InlineAsm::isClobber: 3693 // Nothing to do. 3694 break; 3695 } 3696 3697 // If this is an input or an indirect output, process the call argument. 3698 // BasicBlocks are labels, currently appearing only in asm's. 3699 if (OpInfo.CallOperandVal) { 3700 if (isa<BasicBlock>(OpInfo.CallOperandVal)) 3701 OpInfo.CallOperand = 3702 DAG.getBasicBlock(FuncInfo.MBBMap[cast<BasicBlock>( 3703 OpInfo.CallOperandVal)]); 3704 else { 3705 OpInfo.CallOperand = getValue(OpInfo.CallOperandVal); 3706 const Type *OpTy = OpInfo.CallOperandVal->getType(); 3707 // If this is an indirect operand, the operand is a pointer to the 3708 // accessed type. 3709 if (OpInfo.isIndirect) 3710 OpTy = cast<PointerType>(OpTy)->getElementType(); 3711 3712 // If OpTy is not a first-class value, it may be a struct/union that we 3713 // can tile with integers. 3714 if (!OpTy->isFirstClassType() && OpTy->isSized()) { 3715 unsigned BitSize = TD->getTypeSizeInBits(OpTy); 3716 switch (BitSize) { 3717 default: break; 3718 case 1: 3719 case 8: 3720 case 16: 3721 case 32: 3722 case 64: 3723 OpTy = IntegerType::get(BitSize); 3724 break; 3725 } 3726 } 3727 3728 OpVT = TLI.getValueType(OpTy, true); 3729 } 3730 } 3731 3732 OpInfo.ConstraintVT = OpVT; 3733 3734 // Compute the constraint code and ConstraintType to use. 3735 OpInfo.ComputeConstraintToUse(TLI); 3736 3737 // Keep track of whether we see an earlyclobber. 3738 SawEarlyClobber |= OpInfo.isEarlyClobber; 3739 3740 // If we see a clobber of a register, it is an early clobber. 3741 if (!SawEarlyClobber && 3742 OpInfo.Type == InlineAsm::isClobber && 3743 OpInfo.ConstraintType == TargetLowering::C_Register) { 3744 // Note that we want to ignore things that we don't trick here, like 3745 // dirflag, fpsr, flags, etc. 3746 std::pair<unsigned, const TargetRegisterClass*> PhysReg = 3747 TLI.getRegForInlineAsmConstraint(OpInfo.ConstraintCode, 3748 OpInfo.ConstraintVT); 3749 if (PhysReg.first || PhysReg.second) { 3750 // This is a register we know of. 3751 SawEarlyClobber = true; 3752 } 3753 } 3754 3755 // If this is a memory input, and if the operand is not indirect, do what we 3756 // need to to provide an address for the memory input. 3757 if (OpInfo.ConstraintType == TargetLowering::C_Memory && 3758 !OpInfo.isIndirect) { 3759 assert(OpInfo.Type == InlineAsm::isInput && 3760 "Can only indirectify direct input operands!"); 3761 3762 // Memory operands really want the address of the value. If we don't have 3763 // an indirect input, put it in the constpool if we can, otherwise spill 3764 // it to a stack slot. 3765 3766 // If the operand is a float, integer, or vector constant, spill to a 3767 // constant pool entry to get its address. 3768 Value *OpVal = OpInfo.CallOperandVal; 3769 if (isa<ConstantFP>(OpVal) || isa<ConstantInt>(OpVal) || 3770 isa<ConstantVector>(OpVal)) { 3771 OpInfo.CallOperand = DAG.getConstantPool(cast<Constant>(OpVal), 3772 TLI.getPointerTy()); 3773 } else { 3774 // Otherwise, create a stack slot and emit a store to it before the 3775 // asm. 3776 const Type *Ty = OpVal->getType(); 3777 uint64_t TySize = TLI.getTargetData()->getABITypeSize(Ty); 3778 unsigned Align = TLI.getTargetData()->getPrefTypeAlignment(Ty); 3779 MachineFunction &MF = DAG.getMachineFunction(); 3780 int SSFI = MF.getFrameInfo()->CreateStackObject(TySize, Align); 3781 SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy()); 3782 Chain = DAG.getStore(Chain, OpInfo.CallOperand, StackSlot, NULL, 0); 3783 OpInfo.CallOperand = StackSlot; 3784 } 3785 3786 // There is no longer a Value* corresponding to this operand. 3787 OpInfo.CallOperandVal = 0; 3788 // It is now an indirect operand. 3789 OpInfo.isIndirect = true; 3790 } 3791 3792 // If this constraint is for a specific register, allocate it before 3793 // anything else. 3794 if (OpInfo.ConstraintType == TargetLowering::C_Register) 3795 GetRegistersForValue(OpInfo, SawEarlyClobber, OutputRegs, InputRegs); 3796 } 3797 ConstraintInfos.clear(); 3798 3799 3800 // Second pass - Loop over all of the operands, assigning virtual or physregs 3801 // to registerclass operands. 3802 for (unsigned i = 0, e = ConstraintOperands.size(); i != e; ++i) { 3803 SDISelAsmOperandInfo &OpInfo = ConstraintOperands[i]; 3804 3805 // C_Register operands have already been allocated, Other/Memory don't need 3806 // to be. 3807 if (OpInfo.ConstraintType == TargetLowering::C_RegisterClass) 3808 GetRegistersForValue(OpInfo, SawEarlyClobber, OutputRegs, InputRegs); 3809 } 3810 3811 // AsmNodeOperands - The operands for the ISD::INLINEASM node. 3812 std::vector<SDOperand> AsmNodeOperands; 3813 AsmNodeOperands.push_back(SDOperand()); // reserve space for input chain 3814 AsmNodeOperands.push_back( 3815 DAG.getTargetExternalSymbol(IA->getAsmString().c_str(), MVT::Other)); 3816 3817 3818 // Loop over all of the inputs, copying the operand values into the 3819 // appropriate registers and processing the output regs. 3820 RegsForValue RetValRegs; 3821 3822 // IndirectStoresToEmit - The set of stores to emit after the inline asm node. 3823 std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit; 3824 3825 for (unsigned i = 0, e = ConstraintOperands.size(); i != e; ++i) { 3826 SDISelAsmOperandInfo &OpInfo = ConstraintOperands[i]; 3827 3828 switch (OpInfo.Type) { 3829 case InlineAsm::isOutput: { 3830 if (OpInfo.ConstraintType != TargetLowering::C_RegisterClass && 3831 OpInfo.ConstraintType != TargetLowering::C_Register) { 3832 // Memory output, or 'other' output (e.g. 'X' constraint). 3833 assert(OpInfo.isIndirect && "Memory output must be indirect operand"); 3834 3835 // Add information to the INLINEASM node to know about this output. 3836 unsigned ResOpType = 4/*MEM*/ | (1 << 3); 3837 AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 3838 TLI.getPointerTy())); 3839 AsmNodeOperands.push_back(OpInfo.CallOperand); 3840 break; 3841 } 3842 3843 // Otherwise, this is a register or register class output. 3844 3845 // Copy the output from the appropriate register. Find a register that 3846 // we can use. 3847 if (OpInfo.AssignedRegs.Regs.empty()) { 3848 cerr << "Couldn't allocate output reg for contraint '" 3849 << OpInfo.ConstraintCode << "'!\n"; 3850 exit(1); 3851 } 3852 3853 if (!OpInfo.isIndirect) { 3854 // This is the result value of the call. 3855 assert(RetValRegs.Regs.empty() && 3856 "Cannot have multiple output constraints yet!"); 3857 assert(CS.getType() != Type::VoidTy && "Bad inline asm!"); 3858 RetValRegs = OpInfo.AssignedRegs; 3859 } else { 3860 IndirectStoresToEmit.push_back(std::make_pair(OpInfo.AssignedRegs, 3861 OpInfo.CallOperandVal)); 3862 } 3863 3864 // Add information to the INLINEASM node to know that this register is 3865 // set. 3866 OpInfo.AssignedRegs.AddInlineAsmOperands(2 /*REGDEF*/, DAG, 3867 AsmNodeOperands); 3868 break; 3869 } 3870 case InlineAsm::isInput: { 3871 SDOperand InOperandVal = OpInfo.CallOperand; 3872 3873 if (isdigit(OpInfo.ConstraintCode[0])) { // Matching constraint? 3874 // If this is required to match an output register we have already set, 3875 // just use its register. 3876 unsigned OperandNo = atoi(OpInfo.ConstraintCode.c_str()); 3877 3878 // Scan until we find the definition we already emitted of this operand. 3879 // When we find it, create a RegsForValue operand. 3880 unsigned CurOp = 2; // The first operand. 3881 for (; OperandNo; --OperandNo) { 3882 // Advance to the next operand. 3883 unsigned NumOps = 3884 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue(); 3885 assert(((NumOps & 7) == 2 /*REGDEF*/ || 3886 (NumOps & 7) == 4 /*MEM*/) && 3887 "Skipped past definitions?"); 3888 CurOp += (NumOps>>3)+1; 3889 } 3890 3891 unsigned NumOps = 3892 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue(); 3893 if ((NumOps & 7) == 2 /*REGDEF*/) { 3894 // Add NumOps>>3 registers to MatchedRegs. 3895 RegsForValue MatchedRegs; 3896 MatchedRegs.ValueVT = InOperandVal.getValueType(); 3897 MatchedRegs.RegVT = AsmNodeOperands[CurOp+1].getValueType(); 3898 for (unsigned i = 0, e = NumOps>>3; i != e; ++i) { 3899 unsigned Reg = 3900 cast<RegisterSDNode>(AsmNodeOperands[++CurOp])->getReg(); 3901 MatchedRegs.Regs.push_back(Reg); 3902 } 3903 3904 // Use the produced MatchedRegs object to 3905 MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, &Flag); 3906 MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands); 3907 break; 3908 } else { 3909 assert((NumOps & 7) == 4/*MEM*/ && "Unknown matching constraint!"); 3910 assert((NumOps >> 3) == 1 && "Unexpected number of operands"); 3911 // Add information to the INLINEASM node to know about this input. 3912 unsigned ResOpType = 4/*MEM*/ | (1 << 3); 3913 AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 3914 TLI.getPointerTy())); 3915 AsmNodeOperands.push_back(AsmNodeOperands[CurOp+1]); 3916 break; 3917 } 3918 } 3919 3920 if (OpInfo.ConstraintType == TargetLowering::C_Other) { 3921 assert(!OpInfo.isIndirect && 3922 "Don't know how to handle indirect other inputs yet!"); 3923 3924 std::vector<SDOperand> Ops; 3925 TLI.LowerAsmOperandForConstraint(InOperandVal, OpInfo.ConstraintCode[0], 3926 Ops, DAG); 3927 if (Ops.empty()) { 3928 cerr << "Invalid operand for inline asm constraint '" 3929 << OpInfo.ConstraintCode << "'!\n"; 3930 exit(1); 3931 } 3932 3933 // Add information to the INLINEASM node to know about this input. 3934 unsigned ResOpType = 3 /*IMM*/ | (Ops.size() << 3); 3935 AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 3936 TLI.getPointerTy())); 3937 AsmNodeOperands.insert(AsmNodeOperands.end(), Ops.begin(), Ops.end()); 3938 break; 3939 } else if (OpInfo.ConstraintType == TargetLowering::C_Memory) { 3940 assert(OpInfo.isIndirect && "Operand must be indirect to be a mem!"); 3941 assert(InOperandVal.getValueType() == TLI.getPointerTy() && 3942 "Memory operands expect pointer values"); 3943 3944 // Add information to the INLINEASM node to know about this input. 3945 unsigned ResOpType = 4/*MEM*/ | (1 << 3); 3946 AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 3947 TLI.getPointerTy())); 3948 AsmNodeOperands.push_back(InOperandVal); 3949 break; 3950 } 3951 3952 assert((OpInfo.ConstraintType == TargetLowering::C_RegisterClass || 3953 OpInfo.ConstraintType == TargetLowering::C_Register) && 3954 "Unknown constraint type!"); 3955 assert(!OpInfo.isIndirect && 3956 "Don't know how to handle indirect register inputs yet!"); 3957 3958 // Copy the input into the appropriate registers. 3959 assert(!OpInfo.AssignedRegs.Regs.empty() && 3960 "Couldn't allocate input reg!"); 3961 3962 OpInfo.AssignedRegs.getCopyToRegs(InOperandVal, DAG, Chain, &Flag); 3963 3964 OpInfo.AssignedRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG, 3965 AsmNodeOperands); 3966 break; 3967 } 3968 case InlineAsm::isClobber: { 3969 // Add the clobbered value to the operand list, so that the register 3970 // allocator is aware that the physreg got clobbered. 3971 if (!OpInfo.AssignedRegs.Regs.empty()) 3972 OpInfo.AssignedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG, 3973 AsmNodeOperands); 3974 break; 3975 } 3976 } 3977 } 3978 3979 // Finish up input operands. 3980 AsmNodeOperands[0] = Chain; 3981 if (Flag.Val) AsmNodeOperands.push_back(Flag); 3982 3983 Chain = DAG.getNode(ISD::INLINEASM, 3984 DAG.getNodeValueTypes(MVT::Other, MVT::Flag), 2, 3985 &AsmNodeOperands[0], AsmNodeOperands.size()); 3986 Flag = Chain.getValue(1); 3987 3988 // If this asm returns a register value, copy the result from that register 3989 // and set it as the value of the call. 3990 if (!RetValRegs.Regs.empty()) { 3991 SDOperand Val = RetValRegs.getCopyFromRegs(DAG, Chain, &Flag); 3992 3993 // If the result of the inline asm is a vector, it may have the wrong 3994 // width/num elts. Make sure to convert it to the right type with 3995 // bit_convert. 3996 if (MVT::isVector(Val.getValueType())) { 3997 const VectorType *VTy = cast<VectorType>(CS.getType()); 3998 MVT::ValueType DesiredVT = TLI.getValueType(VTy); 3999 4000 Val = DAG.getNode(ISD::BIT_CONVERT, DesiredVT, Val); 4001 } 4002 4003 setValue(CS.getInstruction(), Val); 4004 } 4005 4006 std::vector<std::pair<SDOperand, Value*> > StoresToEmit; 4007 4008 // Process indirect outputs, first output all of the flagged copies out of 4009 // physregs. 4010 for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) { 4011 RegsForValue &OutRegs = IndirectStoresToEmit[i].first; 4012 Value *Ptr = IndirectStoresToEmit[i].second; 4013 SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, &Flag); 4014 StoresToEmit.push_back(std::make_pair(OutVal, Ptr)); 4015 } 4016 4017 // Emit the non-flagged stores from the physregs. 4018 SmallVector<SDOperand, 8> OutChains; 4019 for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i) 4020 OutChains.push_back(DAG.getStore(Chain, StoresToEmit[i].first, 4021 getValue(StoresToEmit[i].second), 4022 StoresToEmit[i].second, 0)); 4023 if (!OutChains.empty()) 4024 Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, 4025 &OutChains[0], OutChains.size()); 4026 DAG.setRoot(Chain); 4027} 4028 4029 4030void SelectionDAGLowering::visitMalloc(MallocInst &I) { 4031 SDOperand Src = getValue(I.getOperand(0)); 4032 4033 MVT::ValueType IntPtr = TLI.getPointerTy(); 4034 4035 if (IntPtr < Src.getValueType()) 4036 Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src); 4037 else if (IntPtr > Src.getValueType()) 4038 Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src); 4039 4040 // Scale the source by the type size. 4041 uint64_t ElementSize = TD->getABITypeSize(I.getType()->getElementType()); 4042 Src = DAG.getNode(ISD::MUL, Src.getValueType(), 4043 Src, DAG.getIntPtrConstant(ElementSize)); 4044 4045 TargetLowering::ArgListTy Args; 4046 TargetLowering::ArgListEntry Entry; 4047 Entry.Node = Src; 4048 Entry.Ty = TLI.getTargetData()->getIntPtrType(); 4049 Args.push_back(Entry); 4050 4051 std::pair<SDOperand,SDOperand> Result = 4052 TLI.LowerCallTo(getRoot(), I.getType(), false, false, false, CallingConv::C, 4053 true, DAG.getExternalSymbol("malloc", IntPtr), Args, DAG); 4054 setValue(&I, Result.first); // Pointers always fit in registers 4055 DAG.setRoot(Result.second); 4056} 4057 4058void SelectionDAGLowering::visitFree(FreeInst &I) { 4059 TargetLowering::ArgListTy Args; 4060 TargetLowering::ArgListEntry Entry; 4061 Entry.Node = getValue(I.getOperand(0)); 4062 Entry.Ty = TLI.getTargetData()->getIntPtrType(); 4063 Args.push_back(Entry); 4064 MVT::ValueType IntPtr = TLI.getPointerTy(); 4065 std::pair<SDOperand,SDOperand> Result = 4066 TLI.LowerCallTo(getRoot(), Type::VoidTy, false, false, false, 4067 CallingConv::C, true, 4068 DAG.getExternalSymbol("free", IntPtr), Args, DAG); 4069 DAG.setRoot(Result.second); 4070} 4071 4072// EmitInstrWithCustomInserter - This method should be implemented by targets 4073// that mark instructions with the 'usesCustomDAGSchedInserter' flag. These 4074// instructions are special in various ways, which require special support to 4075// insert. The specified MachineInstr is created but not inserted into any 4076// basic blocks, and the scheduler passes ownership of it to this method. 4077MachineBasicBlock *TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI, 4078 MachineBasicBlock *MBB) { 4079 cerr << "If a target marks an instruction with " 4080 << "'usesCustomDAGSchedInserter', it must implement " 4081 << "TargetLowering::EmitInstrWithCustomInserter!\n"; 4082 abort(); 4083 return 0; 4084} 4085 4086void SelectionDAGLowering::visitVAStart(CallInst &I) { 4087 DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(), 4088 getValue(I.getOperand(1)), 4089 DAG.getSrcValue(I.getOperand(1)))); 4090} 4091 4092void SelectionDAGLowering::visitVAArg(VAArgInst &I) { 4093 SDOperand V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(), 4094 getValue(I.getOperand(0)), 4095 DAG.getSrcValue(I.getOperand(0))); 4096 setValue(&I, V); 4097 DAG.setRoot(V.getValue(1)); 4098} 4099 4100void SelectionDAGLowering::visitVAEnd(CallInst &I) { 4101 DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(), 4102 getValue(I.getOperand(1)), 4103 DAG.getSrcValue(I.getOperand(1)))); 4104} 4105 4106void SelectionDAGLowering::visitVACopy(CallInst &I) { 4107 DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(), 4108 getValue(I.getOperand(1)), 4109 getValue(I.getOperand(2)), 4110 DAG.getSrcValue(I.getOperand(1)), 4111 DAG.getSrcValue(I.getOperand(2)))); 4112} 4113 4114/// TargetLowering::LowerArguments - This is the default LowerArguments 4115/// implementation, which just inserts a FORMAL_ARGUMENTS node. FIXME: When all 4116/// targets are migrated to using FORMAL_ARGUMENTS, this hook should be 4117/// integrated into SDISel. 4118std::vector<SDOperand> 4119TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) { 4120 // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node. 4121 std::vector<SDOperand> Ops; 4122 Ops.push_back(DAG.getRoot()); 4123 Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy())); 4124 Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy())); 4125 4126 // Add one result value for each formal argument. 4127 std::vector<MVT::ValueType> RetVals; 4128 unsigned j = 1; 4129 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); 4130 I != E; ++I, ++j) { 4131 MVT::ValueType VT = getValueType(I->getType()); 4132 ISD::ArgFlagsTy Flags; 4133 unsigned OriginalAlignment = 4134 getTargetData()->getABITypeAlignment(I->getType()); 4135 4136 if (F.paramHasAttr(j, ParamAttr::ZExt)) 4137 Flags.setZExt(); 4138 if (F.paramHasAttr(j, ParamAttr::SExt)) 4139 Flags.setSExt(); 4140 if (F.paramHasAttr(j, ParamAttr::InReg)) 4141 Flags.setInReg(); 4142 if (F.paramHasAttr(j, ParamAttr::StructRet)) 4143 Flags.setSRet(); 4144 if (F.paramHasAttr(j, ParamAttr::ByVal)) { 4145 Flags.setByVal(); 4146 const PointerType *Ty = cast<PointerType>(I->getType()); 4147 const Type *ElementTy = Ty->getElementType(); 4148 unsigned FrameAlign = getByValTypeAlignment(ElementTy); 4149 unsigned FrameSize = getTargetData()->getABITypeSize(ElementTy); 4150 // For ByVal, alignment should be passed from FE. BE will guess if 4151 // this info is not there but there are cases it cannot get right. 4152 if (F.getParamAlignment(j)) 4153 FrameAlign = F.getParamAlignment(j); 4154 Flags.setByValAlign(FrameAlign); 4155 Flags.setByValSize(FrameSize); 4156 } 4157 if (F.paramHasAttr(j, ParamAttr::Nest)) 4158 Flags.setNest(); 4159 Flags.setOrigAlign(OriginalAlignment); 4160 4161 MVT::ValueType RegisterVT = getRegisterType(VT); 4162 unsigned NumRegs = getNumRegisters(VT); 4163 for (unsigned i = 0; i != NumRegs; ++i) { 4164 RetVals.push_back(RegisterVT); 4165 ISD::ArgFlagsTy MyFlags = Flags; 4166 if (NumRegs > 1 && i == 0) 4167 MyFlags.setSplit(); 4168 // if it isn't first piece, alignment must be 1 4169 else if (i > 0) 4170 MyFlags.setOrigAlign(1); 4171 Ops.push_back(DAG.getArgFlags(MyFlags)); 4172 } 4173 } 4174 4175 RetVals.push_back(MVT::Other); 4176 4177 // Create the node. 4178 SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS, 4179 DAG.getVTList(&RetVals[0], RetVals.size()), 4180 &Ops[0], Ops.size()).Val; 4181 4182 // Prelower FORMAL_ARGUMENTS. This isn't required for functionality, but 4183 // allows exposing the loads that may be part of the argument access to the 4184 // first DAGCombiner pass. 4185 SDOperand TmpRes = LowerOperation(SDOperand(Result, 0), DAG); 4186 4187 // The number of results should match up, except that the lowered one may have 4188 // an extra flag result. 4189 assert((Result->getNumValues() == TmpRes.Val->getNumValues() || 4190 (Result->getNumValues()+1 == TmpRes.Val->getNumValues() && 4191 TmpRes.getValue(Result->getNumValues()).getValueType() == MVT::Flag)) 4192 && "Lowering produced unexpected number of results!"); 4193 Result = TmpRes.Val; 4194 4195 unsigned NumArgRegs = Result->getNumValues() - 1; 4196 DAG.setRoot(SDOperand(Result, NumArgRegs)); 4197 4198 // Set up the return result vector. 4199 Ops.clear(); 4200 unsigned i = 0; 4201 unsigned Idx = 1; 4202 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; 4203 ++I, ++Idx) { 4204 MVT::ValueType VT = getValueType(I->getType()); 4205 MVT::ValueType PartVT = getRegisterType(VT); 4206 4207 unsigned NumParts = getNumRegisters(VT); 4208 SmallVector<SDOperand, 4> Parts(NumParts); 4209 for (unsigned j = 0; j != NumParts; ++j) 4210 Parts[j] = SDOperand(Result, i++); 4211 4212 ISD::NodeType AssertOp = ISD::DELETED_NODE; 4213 if (F.paramHasAttr(Idx, ParamAttr::SExt)) 4214 AssertOp = ISD::AssertSext; 4215 else if (F.paramHasAttr(Idx, ParamAttr::ZExt)) 4216 AssertOp = ISD::AssertZext; 4217 4218 Ops.push_back(getCopyFromParts(DAG, &Parts[0], NumParts, PartVT, VT, 4219 AssertOp)); 4220 } 4221 assert(i == NumArgRegs && "Argument register count mismatch!"); 4222 return Ops; 4223} 4224 4225 4226/// TargetLowering::LowerCallTo - This is the default LowerCallTo 4227/// implementation, which just inserts an ISD::CALL node, which is later custom 4228/// lowered by the target to something concrete. FIXME: When all targets are 4229/// migrated to using ISD::CALL, this hook should be integrated into SDISel. 4230std::pair<SDOperand, SDOperand> 4231TargetLowering::LowerCallTo(SDOperand Chain, const Type *RetTy, 4232 bool RetSExt, bool RetZExt, bool isVarArg, 4233 unsigned CallingConv, bool isTailCall, 4234 SDOperand Callee, 4235 ArgListTy &Args, SelectionDAG &DAG) { 4236 SmallVector<SDOperand, 32> Ops; 4237 Ops.push_back(Chain); // Op#0 - Chain 4238 Ops.push_back(DAG.getConstant(CallingConv, getPointerTy())); // Op#1 - CC 4239 Ops.push_back(DAG.getConstant(isVarArg, getPointerTy())); // Op#2 - VarArg 4240 Ops.push_back(DAG.getConstant(isTailCall, getPointerTy())); // Op#3 - Tail 4241 Ops.push_back(Callee); 4242 4243 // Handle all of the outgoing arguments. 4244 for (unsigned i = 0, e = Args.size(); i != e; ++i) { 4245 MVT::ValueType VT = getValueType(Args[i].Ty); 4246 SDOperand Op = Args[i].Node; 4247 ISD::ArgFlagsTy Flags; 4248 unsigned OriginalAlignment = 4249 getTargetData()->getABITypeAlignment(Args[i].Ty); 4250 4251 if (Args[i].isZExt) 4252 Flags.setZExt(); 4253 if (Args[i].isSExt) 4254 Flags.setSExt(); 4255 if (Args[i].isInReg) 4256 Flags.setInReg(); 4257 if (Args[i].isSRet) 4258 Flags.setSRet(); 4259 if (Args[i].isByVal) { 4260 Flags.setByVal(); 4261 const PointerType *Ty = cast<PointerType>(Args[i].Ty); 4262 const Type *ElementTy = Ty->getElementType(); 4263 unsigned FrameAlign = getByValTypeAlignment(ElementTy); 4264 unsigned FrameSize = getTargetData()->getABITypeSize(ElementTy); 4265 // For ByVal, alignment should come from FE. BE will guess if this 4266 // info is not there but there are cases it cannot get right. 4267 if (Args[i].Alignment) 4268 FrameAlign = Args[i].Alignment; 4269 Flags.setByValAlign(FrameAlign); 4270 Flags.setByValSize(FrameSize); 4271 } 4272 if (Args[i].isNest) 4273 Flags.setNest(); 4274 Flags.setOrigAlign(OriginalAlignment); 4275 4276 MVT::ValueType PartVT = getRegisterType(VT); 4277 unsigned NumParts = getNumRegisters(VT); 4278 SmallVector<SDOperand, 4> Parts(NumParts); 4279 ISD::NodeType ExtendKind = ISD::ANY_EXTEND; 4280 4281 if (Args[i].isSExt) 4282 ExtendKind = ISD::SIGN_EXTEND; 4283 else if (Args[i].isZExt) 4284 ExtendKind = ISD::ZERO_EXTEND; 4285 4286 getCopyToParts(DAG, Op, &Parts[0], NumParts, PartVT, ExtendKind); 4287 4288 for (unsigned i = 0; i != NumParts; ++i) { 4289 // if it isn't first piece, alignment must be 1 4290 ISD::ArgFlagsTy MyFlags = Flags; 4291 if (NumParts > 1 && i == 0) 4292 MyFlags.setSplit(); 4293 else if (i != 0) 4294 MyFlags.setOrigAlign(1); 4295 4296 Ops.push_back(Parts[i]); 4297 Ops.push_back(DAG.getArgFlags(MyFlags)); 4298 } 4299 } 4300 4301 // Figure out the result value types. We start by making a list of 4302 // the high-level LLVM return types. 4303 SmallVector<const Type *, 4> LLVMRetTys; 4304 if (const StructType *ST = dyn_cast<StructType>(RetTy)) 4305 // A struct return type in the LLVM IR means we have multiple return values. 4306 LLVMRetTys.insert(LLVMRetTys.end(), ST->element_begin(), ST->element_end()); 4307 else 4308 LLVMRetTys.push_back(RetTy); 4309 4310 // Then we translate that to a list of lowered codegen result types. 4311 SmallVector<MVT::ValueType, 4> LoweredRetTys; 4312 SmallVector<MVT::ValueType, 4> RetTys; 4313 for (unsigned I = 0, E = LLVMRetTys.size(); I != E; ++I) { 4314 MVT::ValueType VT = getValueType(LLVMRetTys[I]); 4315 RetTys.push_back(VT); 4316 4317 MVT::ValueType RegisterVT = getRegisterType(VT); 4318 unsigned NumRegs = getNumRegisters(VT); 4319 for (unsigned i = 0; i != NumRegs; ++i) 4320 LoweredRetTys.push_back(RegisterVT); 4321 } 4322 4323 LoweredRetTys.push_back(MVT::Other); // Always has a chain. 4324 4325 // Create the CALL node. 4326 SDOperand Res = DAG.getNode(ISD::CALL, 4327 DAG.getVTList(&LoweredRetTys[0], 4328 LoweredRetTys.size()), 4329 &Ops[0], Ops.size()); 4330 Chain = Res.getValue(LoweredRetTys.size() - 1); 4331 4332 // Gather up the call result into a single value. 4333 if (RetTy != Type::VoidTy) { 4334 ISD::NodeType AssertOp = ISD::DELETED_NODE; 4335 4336 if (RetSExt) 4337 AssertOp = ISD::AssertSext; 4338 else if (RetZExt) 4339 AssertOp = ISD::AssertZext; 4340 4341 SmallVector<SDOperand, 4> ReturnValues; 4342 unsigned RegNo = 0; 4343 for (unsigned I = 0, E = LLVMRetTys.size(); I != E; ++I) { 4344 MVT::ValueType VT = getValueType(LLVMRetTys[I]); 4345 MVT::ValueType RegisterVT = getRegisterType(VT); 4346 unsigned NumRegs = getNumRegisters(VT); 4347 unsigned RegNoEnd = NumRegs + RegNo; 4348 SmallVector<SDOperand, 4> Results; 4349 for (; RegNo != RegNoEnd; ++RegNo) 4350 Results.push_back(Res.getValue(RegNo)); 4351 SDOperand ReturnValue = 4352 getCopyFromParts(DAG, &Results[0], NumRegs, RegisterVT, VT, 4353 AssertOp); 4354 ReturnValues.push_back(ReturnValue); 4355 } 4356 Res = ReturnValues.size() == 1 ? ReturnValues.front() : 4357 DAG.getNode(ISD::MERGE_VALUES, 4358 DAG.getVTList(&RetTys[0], RetTys.size()), 4359 &ReturnValues[0], ReturnValues.size()); 4360 } 4361 4362 return std::make_pair(Res, Chain); 4363} 4364 4365SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) { 4366 assert(0 && "LowerOperation not implemented for this target!"); 4367 abort(); 4368 return SDOperand(); 4369} 4370 4371SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op, 4372 SelectionDAG &DAG) { 4373 assert(0 && "CustomPromoteOperation not implemented for this target!"); 4374 abort(); 4375 return SDOperand(); 4376} 4377 4378//===----------------------------------------------------------------------===// 4379// SelectionDAGISel code 4380//===----------------------------------------------------------------------===// 4381 4382unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) { 4383 return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT)); 4384} 4385 4386void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { 4387 AU.addRequired<AliasAnalysis>(); 4388 AU.addRequired<CollectorModuleMetadata>(); 4389 AU.setPreservesAll(); 4390} 4391 4392 4393 4394bool SelectionDAGISel::runOnFunction(Function &Fn) { 4395 // Get alias analysis for load/store combining. 4396 AA = &getAnalysis<AliasAnalysis>(); 4397 4398 MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine()); 4399 if (MF.getFunction()->hasCollector()) 4400 GCI = &getAnalysis<CollectorModuleMetadata>().get(*MF.getFunction()); 4401 else 4402 GCI = 0; 4403 RegInfo = &MF.getRegInfo(); 4404 DOUT << "\n\n\n=== " << Fn.getName() << "\n"; 4405 4406 FunctionLoweringInfo FuncInfo(TLI, Fn, MF); 4407 4408 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 4409 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator())) 4410 // Mark landing pad. 4411 FuncInfo.MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad(); 4412 4413 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 4414 SelectBasicBlock(I, MF, FuncInfo); 4415 4416 // Add function live-ins to entry block live-in set. 4417 BasicBlock *EntryBB = &Fn.getEntryBlock(); 4418 BB = FuncInfo.MBBMap[EntryBB]; 4419 if (!RegInfo->livein_empty()) 4420 for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(), 4421 E = RegInfo->livein_end(); I != E; ++I) 4422 BB->addLiveIn(I->first); 4423 4424#ifndef NDEBUG 4425 assert(FuncInfo.CatchInfoFound.size() == FuncInfo.CatchInfoLost.size() && 4426 "Not all catch info was assigned to a landing pad!"); 4427#endif 4428 4429 return true; 4430} 4431 4432void SelectionDAGLowering::CopyValueToVirtualRegister(Value *V, 4433 unsigned Reg) { 4434 SDOperand Op = getValue(V); 4435 assert((Op.getOpcode() != ISD::CopyFromReg || 4436 cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) && 4437 "Copy from a reg to the same reg!"); 4438 assert(!TargetRegisterInfo::isPhysicalRegister(Reg) && "Is a physreg"); 4439 4440 MVT::ValueType SrcVT = Op.getValueType(); 4441 MVT::ValueType RegisterVT = TLI.getRegisterType(SrcVT); 4442 unsigned NumRegs = TLI.getNumRegisters(SrcVT); 4443 SmallVector<SDOperand, 8> Regs(NumRegs); 4444 SmallVector<SDOperand, 8> Chains(NumRegs); 4445 4446 // Copy the value by legal parts into sequential virtual registers. 4447 getCopyToParts(DAG, Op, &Regs[0], NumRegs, RegisterVT); 4448 for (unsigned i = 0; i != NumRegs; ++i) 4449 Chains[i] = DAG.getCopyToReg(DAG.getEntryNode(), Reg + i, Regs[i]); 4450 SDOperand Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, &Chains[0], NumRegs); 4451 PendingExports.push_back(Ch); 4452} 4453 4454void SelectionDAGISel:: 4455LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL) { 4456 // If this is the entry block, emit arguments. 4457 Function &F = *LLVMBB->getParent(); 4458 FunctionLoweringInfo &FuncInfo = SDL.FuncInfo; 4459 SDOperand OldRoot = SDL.DAG.getRoot(); 4460 std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG); 4461 4462 unsigned a = 0; 4463 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 4464 AI != E; ++AI, ++a) 4465 if (!AI->use_empty()) { 4466 SDL.setValue(AI, Args[a]); 4467 4468 // If this argument is live outside of the entry block, insert a copy from 4469 // whereever we got it to the vreg that other BB's will reference it as. 4470 DenseMap<const Value*, unsigned>::iterator VMI=FuncInfo.ValueMap.find(AI); 4471 if (VMI != FuncInfo.ValueMap.end()) { 4472 SDL.CopyValueToVirtualRegister(AI, VMI->second); 4473 } 4474 } 4475 4476 // Finally, if the target has anything special to do, allow it to do so. 4477 // FIXME: this should insert code into the DAG! 4478 EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction()); 4479} 4480 4481static void copyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB, 4482 MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) { 4483 for (BasicBlock::iterator I = SrcBB->begin(), E = --SrcBB->end(); I != E; ++I) 4484 if (isSelector(I)) { 4485 // Apply the catch info to DestBB. 4486 addCatchInfo(cast<CallInst>(*I), MMI, FLI.MBBMap[DestBB]); 4487#ifndef NDEBUG 4488 if (!FLI.MBBMap[SrcBB]->isLandingPad()) 4489 FLI.CatchInfoFound.insert(I); 4490#endif 4491 } 4492} 4493 4494/// CheckDAGForTailCallsAndFixThem - This Function looks for CALL nodes in the 4495/// DAG and fixes their tailcall attribute operand. 4496static void CheckDAGForTailCallsAndFixThem(SelectionDAG &DAG, 4497 TargetLowering& TLI) { 4498 SDNode * Ret = NULL; 4499 SDOperand Terminator = DAG.getRoot(); 4500 4501 // Find RET node. 4502 if (Terminator.getOpcode() == ISD::RET) { 4503 Ret = Terminator.Val; 4504 } 4505 4506 // Fix tail call attribute of CALL nodes. 4507 for (SelectionDAG::allnodes_iterator BE = DAG.allnodes_begin(), 4508 BI = prior(DAG.allnodes_end()); BI != BE; --BI) { 4509 if (BI->getOpcode() == ISD::CALL) { 4510 SDOperand OpRet(Ret, 0); 4511 SDOperand OpCall(static_cast<SDNode*>(BI), 0); 4512 bool isMarkedTailCall = 4513 cast<ConstantSDNode>(OpCall.getOperand(3))->getValue() != 0; 4514 // If CALL node has tail call attribute set to true and the call is not 4515 // eligible (no RET or the target rejects) the attribute is fixed to 4516 // false. The TargetLowering::IsEligibleForTailCallOptimization function 4517 // must correctly identify tail call optimizable calls. 4518 if (isMarkedTailCall && 4519 (Ret==NULL || 4520 !TLI.IsEligibleForTailCallOptimization(OpCall, OpRet, DAG))) { 4521 SmallVector<SDOperand, 32> Ops; 4522 unsigned idx=0; 4523 for(SDNode::op_iterator I =OpCall.Val->op_begin(), 4524 E=OpCall.Val->op_end(); I!=E; I++, idx++) { 4525 if (idx!=3) 4526 Ops.push_back(*I); 4527 else 4528 Ops.push_back(DAG.getConstant(false, TLI.getPointerTy())); 4529 } 4530 DAG.UpdateNodeOperands(OpCall, Ops.begin(), Ops.size()); 4531 } 4532 } 4533 } 4534} 4535 4536void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB, 4537 std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate, 4538 FunctionLoweringInfo &FuncInfo) { 4539 SelectionDAGLowering SDL(DAG, TLI, *AA, FuncInfo, GCI); 4540 4541 // Lower any arguments needed in this block if this is the entry block. 4542 if (LLVMBB == &LLVMBB->getParent()->getEntryBlock()) 4543 LowerArguments(LLVMBB, SDL); 4544 4545 BB = FuncInfo.MBBMap[LLVMBB]; 4546 SDL.setCurrentBasicBlock(BB); 4547 4548 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 4549 4550 if (MMI && BB->isLandingPad()) { 4551 // Add a label to mark the beginning of the landing pad. Deletion of the 4552 // landing pad can thus be detected via the MachineModuleInfo. 4553 unsigned LabelID = MMI->addLandingPad(BB); 4554 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, DAG.getEntryNode(), 4555 DAG.getConstant(LabelID, MVT::i32), 4556 DAG.getConstant(1, MVT::i32))); 4557 4558 // Mark exception register as live in. 4559 unsigned Reg = TLI.getExceptionAddressRegister(); 4560 if (Reg) BB->addLiveIn(Reg); 4561 4562 // Mark exception selector register as live in. 4563 Reg = TLI.getExceptionSelectorRegister(); 4564 if (Reg) BB->addLiveIn(Reg); 4565 4566 // FIXME: Hack around an exception handling flaw (PR1508): the personality 4567 // function and list of typeids logically belong to the invoke (or, if you 4568 // like, the basic block containing the invoke), and need to be associated 4569 // with it in the dwarf exception handling tables. Currently however the 4570 // information is provided by an intrinsic (eh.selector) that can be moved 4571 // to unexpected places by the optimizers: if the unwind edge is critical, 4572 // then breaking it can result in the intrinsics being in the successor of 4573 // the landing pad, not the landing pad itself. This results in exceptions 4574 // not being caught because no typeids are associated with the invoke. 4575 // This may not be the only way things can go wrong, but it is the only way 4576 // we try to work around for the moment. 4577 BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator()); 4578 4579 if (Br && Br->isUnconditional()) { // Critical edge? 4580 BasicBlock::iterator I, E; 4581 for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I) 4582 if (isSelector(I)) 4583 break; 4584 4585 if (I == E) 4586 // No catch info found - try to extract some from the successor. 4587 copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, FuncInfo); 4588 } 4589 } 4590 4591 // Lower all of the non-terminator instructions. 4592 for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end(); 4593 I != E; ++I) 4594 SDL.visit(*I); 4595 4596 // Ensure that all instructions which are used outside of their defining 4597 // blocks are available as virtual registers. Invoke is handled elsewhere. 4598 for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I) 4599 if (!I->use_empty() && !isa<PHINode>(I) && !isa<InvokeInst>(I)) { 4600 DenseMap<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I); 4601 if (VMI != FuncInfo.ValueMap.end()) 4602 SDL.CopyValueToVirtualRegister(I, VMI->second); 4603 } 4604 4605 // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to 4606 // ensure constants are generated when needed. Remember the virtual registers 4607 // that need to be added to the Machine PHI nodes as input. We cannot just 4608 // directly add them, because expansion might result in multiple MBB's for one 4609 // BB. As such, the start of the BB might correspond to a different MBB than 4610 // the end. 4611 // 4612 TerminatorInst *TI = LLVMBB->getTerminator(); 4613 4614 // Emit constants only once even if used by multiple PHI nodes. 4615 std::map<Constant*, unsigned> ConstantsOut; 4616 4617 // Vector bool would be better, but vector<bool> is really slow. 4618 std::vector<unsigned char> SuccsHandled; 4619 if (TI->getNumSuccessors()) 4620 SuccsHandled.resize(BB->getParent()->getNumBlockIDs()); 4621 4622 // Check successor nodes' PHI nodes that expect a constant to be available 4623 // from this block. 4624 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { 4625 BasicBlock *SuccBB = TI->getSuccessor(succ); 4626 if (!isa<PHINode>(SuccBB->begin())) continue; 4627 MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB]; 4628 4629 // If this terminator has multiple identical successors (common for 4630 // switches), only handle each succ once. 4631 unsigned SuccMBBNo = SuccMBB->getNumber(); 4632 if (SuccsHandled[SuccMBBNo]) continue; 4633 SuccsHandled[SuccMBBNo] = true; 4634 4635 MachineBasicBlock::iterator MBBI = SuccMBB->begin(); 4636 PHINode *PN; 4637 4638 // At this point we know that there is a 1-1 correspondence between LLVM PHI 4639 // nodes and Machine PHI nodes, but the incoming operands have not been 4640 // emitted yet. 4641 for (BasicBlock::iterator I = SuccBB->begin(); 4642 (PN = dyn_cast<PHINode>(I)); ++I) { 4643 // Ignore dead phi's. 4644 if (PN->use_empty()) continue; 4645 4646 unsigned Reg; 4647 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 4648 4649 if (Constant *C = dyn_cast<Constant>(PHIOp)) { 4650 unsigned &RegOut = ConstantsOut[C]; 4651 if (RegOut == 0) { 4652 RegOut = FuncInfo.CreateRegForValue(C); 4653 SDL.CopyValueToVirtualRegister(C, RegOut); 4654 } 4655 Reg = RegOut; 4656 } else { 4657 Reg = FuncInfo.ValueMap[PHIOp]; 4658 if (Reg == 0) { 4659 assert(isa<AllocaInst>(PHIOp) && 4660 FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) && 4661 "Didn't codegen value into a register!??"); 4662 Reg = FuncInfo.CreateRegForValue(PHIOp); 4663 SDL.CopyValueToVirtualRegister(PHIOp, Reg); 4664 } 4665 } 4666 4667 // Remember that this register needs to added to the machine PHI node as 4668 // the input for this MBB. 4669 MVT::ValueType VT = TLI.getValueType(PN->getType()); 4670 unsigned NumRegisters = TLI.getNumRegisters(VT); 4671 for (unsigned i = 0, e = NumRegisters; i != e; ++i) 4672 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i)); 4673 } 4674 } 4675 ConstantsOut.clear(); 4676 4677 // Lower the terminator after the copies are emitted. 4678 SDL.visit(*LLVMBB->getTerminator()); 4679 4680 // Copy over any CaseBlock records that may now exist due to SwitchInst 4681 // lowering, as well as any jump table information. 4682 SwitchCases.clear(); 4683 SwitchCases = SDL.SwitchCases; 4684 JTCases.clear(); 4685 JTCases = SDL.JTCases; 4686 BitTestCases.clear(); 4687 BitTestCases = SDL.BitTestCases; 4688 4689 // Make sure the root of the DAG is up-to-date. 4690 DAG.setRoot(SDL.getControlRoot()); 4691 4692 // Check whether calls in this block are real tail calls. Fix up CALL nodes 4693 // with correct tailcall attribute so that the target can rely on the tailcall 4694 // attribute indicating whether the call is really eligible for tail call 4695 // optimization. 4696 CheckDAGForTailCallsAndFixThem(DAG, TLI); 4697} 4698 4699void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) { 4700 DOUT << "Lowered selection DAG:\n"; 4701 DEBUG(DAG.dump()); 4702 4703 // Run the DAG combiner in pre-legalize mode. 4704 DAG.Combine(false, *AA); 4705 4706 DOUT << "Optimized lowered selection DAG:\n"; 4707 DEBUG(DAG.dump()); 4708 4709 // Second step, hack on the DAG until it only uses operations and types that 4710 // the target supports. 4711#if 0 // Enable this some day. 4712 DAG.LegalizeTypes(); 4713 // Someday even later, enable a dag combine pass here. 4714#endif 4715 DAG.Legalize(); 4716 4717 DOUT << "Legalized selection DAG:\n"; 4718 DEBUG(DAG.dump()); 4719 4720 // Run the DAG combiner in post-legalize mode. 4721 DAG.Combine(true, *AA); 4722 4723 DOUT << "Optimized legalized selection DAG:\n"; 4724 DEBUG(DAG.dump()); 4725 4726 if (ViewISelDAGs) DAG.viewGraph(); 4727 4728 // Third, instruction select all of the operations to machine code, adding the 4729 // code to the MachineBasicBlock. 4730 InstructionSelectBasicBlock(DAG); 4731 4732 DOUT << "Selected machine code:\n"; 4733 DEBUG(BB->dump()); 4734} 4735 4736void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, 4737 FunctionLoweringInfo &FuncInfo) { 4738 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate; 4739 { 4740 SelectionDAG DAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4741 CurDAG = &DAG; 4742 4743 // First step, lower LLVM code to some DAG. This DAG may use operations and 4744 // types that are not supported by the target. 4745 BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo); 4746 4747 // Second step, emit the lowered DAG as machine code. 4748 CodeGenAndEmitDAG(DAG); 4749 } 4750 4751 DOUT << "Total amount of phi nodes to update: " 4752 << PHINodesToUpdate.size() << "\n"; 4753 DEBUG(for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) 4754 DOUT << "Node " << i << " : (" << PHINodesToUpdate[i].first 4755 << ", " << PHINodesToUpdate[i].second << ")\n";); 4756 4757 // Next, now that we know what the last MBB the LLVM BB expanded is, update 4758 // PHI nodes in successors. 4759 if (SwitchCases.empty() && JTCases.empty() && BitTestCases.empty()) { 4760 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) { 4761 MachineInstr *PHI = PHINodesToUpdate[i].first; 4762 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 4763 "This is not a machine PHI node that we are updating!"); 4764 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[i].second, 4765 false)); 4766 PHI->addOperand(MachineOperand::CreateMBB(BB)); 4767 } 4768 return; 4769 } 4770 4771 for (unsigned i = 0, e = BitTestCases.size(); i != e; ++i) { 4772 // Lower header first, if it wasn't already lowered 4773 if (!BitTestCases[i].Emitted) { 4774 SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4775 CurDAG = &HSDAG; 4776 SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI); 4777 // Set the current basic block to the mbb we wish to insert the code into 4778 BB = BitTestCases[i].Parent; 4779 HSDL.setCurrentBasicBlock(BB); 4780 // Emit the code 4781 HSDL.visitBitTestHeader(BitTestCases[i]); 4782 HSDAG.setRoot(HSDL.getRoot()); 4783 CodeGenAndEmitDAG(HSDAG); 4784 } 4785 4786 for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) { 4787 SelectionDAG BSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4788 CurDAG = &BSDAG; 4789 SelectionDAGLowering BSDL(BSDAG, TLI, *AA, FuncInfo, GCI); 4790 // Set the current basic block to the mbb we wish to insert the code into 4791 BB = BitTestCases[i].Cases[j].ThisBB; 4792 BSDL.setCurrentBasicBlock(BB); 4793 // Emit the code 4794 if (j+1 != ej) 4795 BSDL.visitBitTestCase(BitTestCases[i].Cases[j+1].ThisBB, 4796 BitTestCases[i].Reg, 4797 BitTestCases[i].Cases[j]); 4798 else 4799 BSDL.visitBitTestCase(BitTestCases[i].Default, 4800 BitTestCases[i].Reg, 4801 BitTestCases[i].Cases[j]); 4802 4803 4804 BSDAG.setRoot(BSDL.getRoot()); 4805 CodeGenAndEmitDAG(BSDAG); 4806 } 4807 4808 // Update PHI Nodes 4809 for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) { 4810 MachineInstr *PHI = PHINodesToUpdate[pi].first; 4811 MachineBasicBlock *PHIBB = PHI->getParent(); 4812 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 4813 "This is not a machine PHI node that we are updating!"); 4814 // This is "default" BB. We have two jumps to it. From "header" BB and 4815 // from last "case" BB. 4816 if (PHIBB == BitTestCases[i].Default) { 4817 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, 4818 false)); 4819 PHI->addOperand(MachineOperand::CreateMBB(BitTestCases[i].Parent)); 4820 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, 4821 false)); 4822 PHI->addOperand(MachineOperand::CreateMBB(BitTestCases[i].Cases. 4823 back().ThisBB)); 4824 } 4825 // One of "cases" BB. 4826 for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) { 4827 MachineBasicBlock* cBB = BitTestCases[i].Cases[j].ThisBB; 4828 if (cBB->succ_end() != 4829 std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) { 4830 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, 4831 false)); 4832 PHI->addOperand(MachineOperand::CreateMBB(cBB)); 4833 } 4834 } 4835 } 4836 } 4837 4838 // If the JumpTable record is filled in, then we need to emit a jump table. 4839 // Updating the PHI nodes is tricky in this case, since we need to determine 4840 // whether the PHI is a successor of the range check MBB or the jump table MBB 4841 for (unsigned i = 0, e = JTCases.size(); i != e; ++i) { 4842 // Lower header first, if it wasn't already lowered 4843 if (!JTCases[i].first.Emitted) { 4844 SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4845 CurDAG = &HSDAG; 4846 SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI); 4847 // Set the current basic block to the mbb we wish to insert the code into 4848 BB = JTCases[i].first.HeaderBB; 4849 HSDL.setCurrentBasicBlock(BB); 4850 // Emit the code 4851 HSDL.visitJumpTableHeader(JTCases[i].second, JTCases[i].first); 4852 HSDAG.setRoot(HSDL.getRoot()); 4853 CodeGenAndEmitDAG(HSDAG); 4854 } 4855 4856 SelectionDAG JSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4857 CurDAG = &JSDAG; 4858 SelectionDAGLowering JSDL(JSDAG, TLI, *AA, FuncInfo, GCI); 4859 // Set the current basic block to the mbb we wish to insert the code into 4860 BB = JTCases[i].second.MBB; 4861 JSDL.setCurrentBasicBlock(BB); 4862 // Emit the code 4863 JSDL.visitJumpTable(JTCases[i].second); 4864 JSDAG.setRoot(JSDL.getRoot()); 4865 CodeGenAndEmitDAG(JSDAG); 4866 4867 // Update PHI Nodes 4868 for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) { 4869 MachineInstr *PHI = PHINodesToUpdate[pi].first; 4870 MachineBasicBlock *PHIBB = PHI->getParent(); 4871 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 4872 "This is not a machine PHI node that we are updating!"); 4873 // "default" BB. We can go there only from header BB. 4874 if (PHIBB == JTCases[i].second.Default) { 4875 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, 4876 false)); 4877 PHI->addOperand(MachineOperand::CreateMBB(JTCases[i].first.HeaderBB)); 4878 } 4879 // JT BB. Just iterate over successors here 4880 if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) { 4881 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, 4882 false)); 4883 PHI->addOperand(MachineOperand::CreateMBB(BB)); 4884 } 4885 } 4886 } 4887 4888 // If the switch block involved a branch to one of the actual successors, we 4889 // need to update PHI nodes in that block. 4890 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) { 4891 MachineInstr *PHI = PHINodesToUpdate[i].first; 4892 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 4893 "This is not a machine PHI node that we are updating!"); 4894 if (BB->isSuccessor(PHI->getParent())) { 4895 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[i].second, 4896 false)); 4897 PHI->addOperand(MachineOperand::CreateMBB(BB)); 4898 } 4899 } 4900 4901 // If we generated any switch lowering information, build and codegen any 4902 // additional DAGs necessary. 4903 for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) { 4904 SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4905 CurDAG = &SDAG; 4906 SelectionDAGLowering SDL(SDAG, TLI, *AA, FuncInfo, GCI); 4907 4908 // Set the current basic block to the mbb we wish to insert the code into 4909 BB = SwitchCases[i].ThisBB; 4910 SDL.setCurrentBasicBlock(BB); 4911 4912 // Emit the code 4913 SDL.visitSwitchCase(SwitchCases[i]); 4914 SDAG.setRoot(SDL.getRoot()); 4915 CodeGenAndEmitDAG(SDAG); 4916 4917 // Handle any PHI nodes in successors of this chunk, as if we were coming 4918 // from the original BB before switch expansion. Note that PHI nodes can 4919 // occur multiple times in PHINodesToUpdate. We have to be very careful to 4920 // handle them the right number of times. 4921 while ((BB = SwitchCases[i].TrueBB)) { // Handle LHS and RHS. 4922 for (MachineBasicBlock::iterator Phi = BB->begin(); 4923 Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){ 4924 // This value for this PHI node is recorded in PHINodesToUpdate, get it. 4925 for (unsigned pn = 0; ; ++pn) { 4926 assert(pn != PHINodesToUpdate.size() && "Didn't find PHI entry!"); 4927 if (PHINodesToUpdate[pn].first == Phi) { 4928 Phi->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pn]. 4929 second, false)); 4930 Phi->addOperand(MachineOperand::CreateMBB(SwitchCases[i].ThisBB)); 4931 break; 4932 } 4933 } 4934 } 4935 4936 // Don't process RHS if same block as LHS. 4937 if (BB == SwitchCases[i].FalseBB) 4938 SwitchCases[i].FalseBB = 0; 4939 4940 // If we haven't handled the RHS, do so now. Otherwise, we're done. 4941 SwitchCases[i].TrueBB = SwitchCases[i].FalseBB; 4942 SwitchCases[i].FalseBB = 0; 4943 } 4944 assert(SwitchCases[i].TrueBB == 0 && SwitchCases[i].FalseBB == 0); 4945 } 4946} 4947 4948 4949//===----------------------------------------------------------------------===// 4950/// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each 4951/// target node in the graph. 4952void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) { 4953 if (ViewSchedDAGs) DAG.viewGraph(); 4954 4955 RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault(); 4956 4957 if (!Ctor) { 4958 Ctor = ISHeuristic; 4959 RegisterScheduler::setDefault(Ctor); 4960 } 4961 4962 ScheduleDAG *SL = Ctor(this, &DAG, BB); 4963 BB = SL->Run(); 4964 4965 if (ViewSUnitDAGs) SL->viewGraph(); 4966 4967 delete SL; 4968} 4969 4970 4971HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() { 4972 return new HazardRecognizer(); 4973} 4974 4975//===----------------------------------------------------------------------===// 4976// Helper functions used by the generated instruction selector. 4977//===----------------------------------------------------------------------===// 4978// Calls to these methods are generated by tblgen. 4979 4980/// CheckAndMask - The isel is trying to match something like (and X, 255). If 4981/// the dag combiner simplified the 255, we still want to match. RHS is the 4982/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value 4983/// specified in the .td file (e.g. 255). 4984bool SelectionDAGISel::CheckAndMask(SDOperand LHS, ConstantSDNode *RHS, 4985 int64_t DesiredMaskS) const { 4986 const APInt &ActualMask = RHS->getAPIntValue(); 4987 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 4988 4989 // If the actual mask exactly matches, success! 4990 if (ActualMask == DesiredMask) 4991 return true; 4992 4993 // If the actual AND mask is allowing unallowed bits, this doesn't match. 4994 if (ActualMask.intersects(~DesiredMask)) 4995 return false; 4996 4997 // Otherwise, the DAG Combiner may have proven that the value coming in is 4998 // either already zero or is not demanded. Check for known zero input bits. 4999 APInt NeededMask = DesiredMask & ~ActualMask; 5000 if (CurDAG->MaskedValueIsZero(LHS, NeededMask)) 5001 return true; 5002 5003 // TODO: check to see if missing bits are just not demanded. 5004 5005 // Otherwise, this pattern doesn't match. 5006 return false; 5007} 5008 5009/// CheckOrMask - The isel is trying to match something like (or X, 255). If 5010/// the dag combiner simplified the 255, we still want to match. RHS is the 5011/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value 5012/// specified in the .td file (e.g. 255). 5013bool SelectionDAGISel::CheckOrMask(SDOperand LHS, ConstantSDNode *RHS, 5014 int64_t DesiredMaskS) const { 5015 const APInt &ActualMask = RHS->getAPIntValue(); 5016 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 5017 5018 // If the actual mask exactly matches, success! 5019 if (ActualMask == DesiredMask) 5020 return true; 5021 5022 // If the actual AND mask is allowing unallowed bits, this doesn't match. 5023 if (ActualMask.intersects(~DesiredMask)) 5024 return false; 5025 5026 // Otherwise, the DAG Combiner may have proven that the value coming in is 5027 // either already zero or is not demanded. Check for known zero input bits. 5028 APInt NeededMask = DesiredMask & ~ActualMask; 5029 5030 APInt KnownZero, KnownOne; 5031 CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne); 5032 5033 // If all the missing bits in the or are already known to be set, match! 5034 if ((NeededMask & KnownOne) == NeededMask) 5035 return true; 5036 5037 // TODO: check to see if missing bits are just not demanded. 5038 5039 // Otherwise, this pattern doesn't match. 5040 return false; 5041} 5042 5043 5044/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated 5045/// by tblgen. Others should not call it. 5046void SelectionDAGISel:: 5047SelectInlineAsmMemoryOperands(std::vector<SDOperand> &Ops, SelectionDAG &DAG) { 5048 std::vector<SDOperand> InOps; 5049 std::swap(InOps, Ops); 5050 5051 Ops.push_back(InOps[0]); // input chain. 5052 Ops.push_back(InOps[1]); // input asm string. 5053 5054 unsigned i = 2, e = InOps.size(); 5055 if (InOps[e-1].getValueType() == MVT::Flag) 5056 --e; // Don't process a flag operand if it is here. 5057 5058 while (i != e) { 5059 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue(); 5060 if ((Flags & 7) != 4 /*MEM*/) { 5061 // Just skip over this operand, copying the operands verbatim. 5062 Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1); 5063 i += (Flags >> 3) + 1; 5064 } else { 5065 assert((Flags >> 3) == 1 && "Memory operand with multiple values?"); 5066 // Otherwise, this is a memory operand. Ask the target to select it. 5067 std::vector<SDOperand> SelOps; 5068 if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) { 5069 cerr << "Could not match memory address. Inline asm failure!\n"; 5070 exit(1); 5071 } 5072 5073 // Add this to the output node. 5074 MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy(); 5075 Ops.push_back(DAG.getTargetConstant(4/*MEM*/ | (SelOps.size() << 3), 5076 IntPtrTy)); 5077 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end()); 5078 i += 2; 5079 } 5080 } 5081 5082 // Add the flag input back if present. 5083 if (e != InOps.size()) 5084 Ops.push_back(InOps.back()); 5085} 5086 5087char SelectionDAGISel::ID = 0; 5088