SelectionDAGISel.cpp revision 10e4bdf5d1cf60d1c7bbfbb780996290fc2b94a7
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 if (UndefValue *UV = dyn_cast<UndefValue>(I.getOperand(0))) { 3315 SDOperand Undef = DAG.getNode(ISD::UNDEF, TLI.getValueType(I.getType())); 3316 setValue(&I, Undef); 3317 } else { 3318 SDOperand Call = getValue(I.getOperand(0)); 3319 setValue(&I, SDOperand(Call.Val, I.getIndex())); 3320 } 3321} 3322 3323 3324/// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from 3325/// this value and returns the result as a ValueVT value. This uses 3326/// Chain/Flag as the input and updates them for the output Chain/Flag. 3327/// If the Flag pointer is NULL, no flag is used. 3328SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG, 3329 SDOperand &Chain, SDOperand *Flag)const{ 3330 // Copy the legal parts from the registers. 3331 unsigned NumParts = Regs.size(); 3332 SmallVector<SDOperand, 8> Parts(NumParts); 3333 for (unsigned i = 0; i != NumParts; ++i) { 3334 SDOperand Part = Flag ? 3335 DAG.getCopyFromReg(Chain, Regs[i], RegVT, *Flag) : 3336 DAG.getCopyFromReg(Chain, Regs[i], RegVT); 3337 Chain = Part.getValue(1); 3338 if (Flag) 3339 *Flag = Part.getValue(2); 3340 Parts[i] = Part; 3341 } 3342 3343 // Assemble the legal parts into the final value. 3344 return getCopyFromParts(DAG, &Parts[0], NumParts, RegVT, ValueVT); 3345} 3346 3347/// getCopyToRegs - Emit a series of CopyToReg nodes that copies the 3348/// specified value into the registers specified by this object. This uses 3349/// Chain/Flag as the input and updates them for the output Chain/Flag. 3350/// If the Flag pointer is NULL, no flag is used. 3351void RegsForValue::getCopyToRegs(SDOperand Val, SelectionDAG &DAG, 3352 SDOperand &Chain, SDOperand *Flag) const { 3353 // Get the list of the values's legal parts. 3354 unsigned NumParts = Regs.size(); 3355 SmallVector<SDOperand, 8> Parts(NumParts); 3356 getCopyToParts(DAG, Val, &Parts[0], NumParts, RegVT); 3357 3358 // Copy the parts into the registers. 3359 for (unsigned i = 0; i != NumParts; ++i) { 3360 SDOperand Part = Flag ? 3361 DAG.getCopyToReg(Chain, Regs[i], Parts[i], *Flag) : 3362 DAG.getCopyToReg(Chain, Regs[i], Parts[i]); 3363 Chain = Part.getValue(0); 3364 if (Flag) 3365 *Flag = Part.getValue(1); 3366 } 3367} 3368 3369/// AddInlineAsmOperands - Add this value to the specified inlineasm node 3370/// operand list. This adds the code marker and includes the number of 3371/// values added into it. 3372void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG, 3373 std::vector<SDOperand> &Ops) const { 3374 MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy(); 3375 Ops.push_back(DAG.getTargetConstant(Code | (Regs.size() << 3), IntPtrTy)); 3376 for (unsigned i = 0, e = Regs.size(); i != e; ++i) 3377 Ops.push_back(DAG.getRegister(Regs[i], RegVT)); 3378} 3379 3380/// isAllocatableRegister - If the specified register is safe to allocate, 3381/// i.e. it isn't a stack pointer or some other special register, return the 3382/// register class for the register. Otherwise, return null. 3383static const TargetRegisterClass * 3384isAllocatableRegister(unsigned Reg, MachineFunction &MF, 3385 const TargetLowering &TLI, 3386 const TargetRegisterInfo *TRI) { 3387 MVT::ValueType FoundVT = MVT::Other; 3388 const TargetRegisterClass *FoundRC = 0; 3389 for (TargetRegisterInfo::regclass_iterator RCI = TRI->regclass_begin(), 3390 E = TRI->regclass_end(); RCI != E; ++RCI) { 3391 MVT::ValueType ThisVT = MVT::Other; 3392 3393 const TargetRegisterClass *RC = *RCI; 3394 // If none of the the value types for this register class are valid, we 3395 // can't use it. For example, 64-bit reg classes on 32-bit targets. 3396 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end(); 3397 I != E; ++I) { 3398 if (TLI.isTypeLegal(*I)) { 3399 // If we have already found this register in a different register class, 3400 // choose the one with the largest VT specified. For example, on 3401 // PowerPC, we favor f64 register classes over f32. 3402 if (FoundVT == MVT::Other || 3403 MVT::getSizeInBits(FoundVT) < MVT::getSizeInBits(*I)) { 3404 ThisVT = *I; 3405 break; 3406 } 3407 } 3408 } 3409 3410 if (ThisVT == MVT::Other) continue; 3411 3412 // NOTE: This isn't ideal. In particular, this might allocate the 3413 // frame pointer in functions that need it (due to them not being taken 3414 // out of allocation, because a variable sized allocation hasn't been seen 3415 // yet). This is a slight code pessimization, but should still work. 3416 for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF), 3417 E = RC->allocation_order_end(MF); I != E; ++I) 3418 if (*I == Reg) { 3419 // We found a matching register class. Keep looking at others in case 3420 // we find one with larger registers that this physreg is also in. 3421 FoundRC = RC; 3422 FoundVT = ThisVT; 3423 break; 3424 } 3425 } 3426 return FoundRC; 3427} 3428 3429 3430namespace { 3431/// AsmOperandInfo - This contains information for each constraint that we are 3432/// lowering. 3433struct SDISelAsmOperandInfo : public TargetLowering::AsmOperandInfo { 3434 /// CallOperand - If this is the result output operand or a clobber 3435 /// this is null, otherwise it is the incoming operand to the CallInst. 3436 /// This gets modified as the asm is processed. 3437 SDOperand CallOperand; 3438 3439 /// AssignedRegs - If this is a register or register class operand, this 3440 /// contains the set of register corresponding to the operand. 3441 RegsForValue AssignedRegs; 3442 3443 SDISelAsmOperandInfo(const InlineAsm::ConstraintInfo &info) 3444 : TargetLowering::AsmOperandInfo(info), CallOperand(0,0) { 3445 } 3446 3447 /// MarkAllocatedRegs - Once AssignedRegs is set, mark the assigned registers 3448 /// busy in OutputRegs/InputRegs. 3449 void MarkAllocatedRegs(bool isOutReg, bool isInReg, 3450 std::set<unsigned> &OutputRegs, 3451 std::set<unsigned> &InputRegs, 3452 const TargetRegisterInfo &TRI) const { 3453 if (isOutReg) { 3454 for (unsigned i = 0, e = AssignedRegs.Regs.size(); i != e; ++i) 3455 MarkRegAndAliases(AssignedRegs.Regs[i], OutputRegs, TRI); 3456 } 3457 if (isInReg) { 3458 for (unsigned i = 0, e = AssignedRegs.Regs.size(); i != e; ++i) 3459 MarkRegAndAliases(AssignedRegs.Regs[i], InputRegs, TRI); 3460 } 3461 } 3462 3463private: 3464 /// MarkRegAndAliases - Mark the specified register and all aliases in the 3465 /// specified set. 3466 static void MarkRegAndAliases(unsigned Reg, std::set<unsigned> &Regs, 3467 const TargetRegisterInfo &TRI) { 3468 assert(TargetRegisterInfo::isPhysicalRegister(Reg) && "Isn't a physreg"); 3469 Regs.insert(Reg); 3470 if (const unsigned *Aliases = TRI.getAliasSet(Reg)) 3471 for (; *Aliases; ++Aliases) 3472 Regs.insert(*Aliases); 3473 } 3474}; 3475} // end anon namespace. 3476 3477 3478/// GetRegistersForValue - Assign registers (virtual or physical) for the 3479/// specified operand. We prefer to assign virtual registers, to allow the 3480/// register allocator handle the assignment process. However, if the asm uses 3481/// features that we can't model on machineinstrs, we have SDISel do the 3482/// allocation. This produces generally horrible, but correct, code. 3483/// 3484/// OpInfo describes the operand. 3485/// HasEarlyClobber is true if there are any early clobber constraints (=&r) 3486/// or any explicitly clobbered registers. 3487/// Input and OutputRegs are the set of already allocated physical registers. 3488/// 3489void SelectionDAGLowering:: 3490GetRegistersForValue(SDISelAsmOperandInfo &OpInfo, bool HasEarlyClobber, 3491 std::set<unsigned> &OutputRegs, 3492 std::set<unsigned> &InputRegs) { 3493 // Compute whether this value requires an input register, an output register, 3494 // or both. 3495 bool isOutReg = false; 3496 bool isInReg = false; 3497 switch (OpInfo.Type) { 3498 case InlineAsm::isOutput: 3499 isOutReg = true; 3500 3501 // If this is an early-clobber output, or if there is an input 3502 // constraint that matches this, we need to reserve the input register 3503 // so no other inputs allocate to it. 3504 isInReg = OpInfo.isEarlyClobber || OpInfo.hasMatchingInput; 3505 break; 3506 case InlineAsm::isInput: 3507 isInReg = true; 3508 isOutReg = false; 3509 break; 3510 case InlineAsm::isClobber: 3511 isOutReg = true; 3512 isInReg = true; 3513 break; 3514 } 3515 3516 3517 MachineFunction &MF = DAG.getMachineFunction(); 3518 std::vector<unsigned> Regs; 3519 3520 // If this is a constraint for a single physreg, or a constraint for a 3521 // register class, find it. 3522 std::pair<unsigned, const TargetRegisterClass*> PhysReg = 3523 TLI.getRegForInlineAsmConstraint(OpInfo.ConstraintCode, 3524 OpInfo.ConstraintVT); 3525 3526 unsigned NumRegs = 1; 3527 if (OpInfo.ConstraintVT != MVT::Other) 3528 NumRegs = TLI.getNumRegisters(OpInfo.ConstraintVT); 3529 MVT::ValueType RegVT; 3530 MVT::ValueType ValueVT = OpInfo.ConstraintVT; 3531 3532 3533 // If this is a constraint for a specific physical register, like {r17}, 3534 // assign it now. 3535 if (PhysReg.first) { 3536 if (OpInfo.ConstraintVT == MVT::Other) 3537 ValueVT = *PhysReg.second->vt_begin(); 3538 3539 // Get the actual register value type. This is important, because the user 3540 // may have asked for (e.g.) the AX register in i32 type. We need to 3541 // remember that AX is actually i16 to get the right extension. 3542 RegVT = *PhysReg.second->vt_begin(); 3543 3544 // This is a explicit reference to a physical register. 3545 Regs.push_back(PhysReg.first); 3546 3547 // If this is an expanded reference, add the rest of the regs to Regs. 3548 if (NumRegs != 1) { 3549 TargetRegisterClass::iterator I = PhysReg.second->begin(); 3550 TargetRegisterClass::iterator E = PhysReg.second->end(); 3551 for (; *I != PhysReg.first; ++I) 3552 assert(I != E && "Didn't find reg!"); 3553 3554 // Already added the first reg. 3555 --NumRegs; ++I; 3556 for (; NumRegs; --NumRegs, ++I) { 3557 assert(I != E && "Ran out of registers to allocate!"); 3558 Regs.push_back(*I); 3559 } 3560 } 3561 OpInfo.AssignedRegs = RegsForValue(Regs, RegVT, ValueVT); 3562 const TargetRegisterInfo *TRI = DAG.getTarget().getRegisterInfo(); 3563 OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs, *TRI); 3564 return; 3565 } 3566 3567 // Otherwise, if this was a reference to an LLVM register class, create vregs 3568 // for this reference. 3569 std::vector<unsigned> RegClassRegs; 3570 const TargetRegisterClass *RC = PhysReg.second; 3571 if (RC) { 3572 // If this is an early clobber or tied register, our regalloc doesn't know 3573 // how to maintain the constraint. If it isn't, go ahead and create vreg 3574 // and let the regalloc do the right thing. 3575 if (!OpInfo.hasMatchingInput && !OpInfo.isEarlyClobber && 3576 // If there is some other early clobber and this is an input register, 3577 // then we are forced to pre-allocate the input reg so it doesn't 3578 // conflict with the earlyclobber. 3579 !(OpInfo.Type == InlineAsm::isInput && HasEarlyClobber)) { 3580 RegVT = *PhysReg.second->vt_begin(); 3581 3582 if (OpInfo.ConstraintVT == MVT::Other) 3583 ValueVT = RegVT; 3584 3585 // Create the appropriate number of virtual registers. 3586 MachineRegisterInfo &RegInfo = MF.getRegInfo(); 3587 for (; NumRegs; --NumRegs) 3588 Regs.push_back(RegInfo.createVirtualRegister(PhysReg.second)); 3589 3590 OpInfo.AssignedRegs = RegsForValue(Regs, RegVT, ValueVT); 3591 return; 3592 } 3593 3594 // Otherwise, we can't allocate it. Let the code below figure out how to 3595 // maintain these constraints. 3596 RegClassRegs.assign(PhysReg.second->begin(), PhysReg.second->end()); 3597 3598 } else { 3599 // This is a reference to a register class that doesn't directly correspond 3600 // to an LLVM register class. Allocate NumRegs consecutive, available, 3601 // registers from the class. 3602 RegClassRegs = TLI.getRegClassForInlineAsmConstraint(OpInfo.ConstraintCode, 3603 OpInfo.ConstraintVT); 3604 } 3605 3606 const TargetRegisterInfo *TRI = DAG.getTarget().getRegisterInfo(); 3607 unsigned NumAllocated = 0; 3608 for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) { 3609 unsigned Reg = RegClassRegs[i]; 3610 // See if this register is available. 3611 if ((isOutReg && OutputRegs.count(Reg)) || // Already used. 3612 (isInReg && InputRegs.count(Reg))) { // Already used. 3613 // Make sure we find consecutive registers. 3614 NumAllocated = 0; 3615 continue; 3616 } 3617 3618 // Check to see if this register is allocatable (i.e. don't give out the 3619 // stack pointer). 3620 if (RC == 0) { 3621 RC = isAllocatableRegister(Reg, MF, TLI, TRI); 3622 if (!RC) { // Couldn't allocate this register. 3623 // Reset NumAllocated to make sure we return consecutive registers. 3624 NumAllocated = 0; 3625 continue; 3626 } 3627 } 3628 3629 // Okay, this register is good, we can use it. 3630 ++NumAllocated; 3631 3632 // If we allocated enough consecutive registers, succeed. 3633 if (NumAllocated == NumRegs) { 3634 unsigned RegStart = (i-NumAllocated)+1; 3635 unsigned RegEnd = i+1; 3636 // Mark all of the allocated registers used. 3637 for (unsigned i = RegStart; i != RegEnd; ++i) 3638 Regs.push_back(RegClassRegs[i]); 3639 3640 OpInfo.AssignedRegs = RegsForValue(Regs, *RC->vt_begin(), 3641 OpInfo.ConstraintVT); 3642 OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs, *TRI); 3643 return; 3644 } 3645 } 3646 3647 // Otherwise, we couldn't allocate enough registers for this. 3648 return; 3649} 3650 3651 3652/// visitInlineAsm - Handle a call to an InlineAsm object. 3653/// 3654void SelectionDAGLowering::visitInlineAsm(CallSite CS) { 3655 InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue()); 3656 3657 /// ConstraintOperands - Information about all of the constraints. 3658 std::vector<SDISelAsmOperandInfo> ConstraintOperands; 3659 3660 SDOperand Chain = getRoot(); 3661 SDOperand Flag; 3662 3663 std::set<unsigned> OutputRegs, InputRegs; 3664 3665 // Do a prepass over the constraints, canonicalizing them, and building up the 3666 // ConstraintOperands list. 3667 std::vector<InlineAsm::ConstraintInfo> 3668 ConstraintInfos = IA->ParseConstraints(); 3669 3670 // SawEarlyClobber - Keep track of whether we saw an earlyclobber output 3671 // constraint. If so, we can't let the register allocator allocate any input 3672 // registers, because it will not know to avoid the earlyclobbered output reg. 3673 bool SawEarlyClobber = false; 3674 3675 unsigned ArgNo = 0; // ArgNo - The argument of the CallInst. 3676 for (unsigned i = 0, e = ConstraintInfos.size(); i != e; ++i) { 3677 ConstraintOperands.push_back(SDISelAsmOperandInfo(ConstraintInfos[i])); 3678 SDISelAsmOperandInfo &OpInfo = ConstraintOperands.back(); 3679 3680 MVT::ValueType OpVT = MVT::Other; 3681 3682 // Compute the value type for each operand. 3683 switch (OpInfo.Type) { 3684 case InlineAsm::isOutput: 3685 if (!OpInfo.isIndirect) { 3686 // The return value of the call is this value. As such, there is no 3687 // corresponding argument. 3688 assert(CS.getType() != Type::VoidTy && "Bad inline asm!"); 3689 OpVT = TLI.getValueType(CS.getType()); 3690 } else { 3691 OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 3692 } 3693 break; 3694 case InlineAsm::isInput: 3695 OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 3696 break; 3697 case InlineAsm::isClobber: 3698 // Nothing to do. 3699 break; 3700 } 3701 3702 // If this is an input or an indirect output, process the call argument. 3703 // BasicBlocks are labels, currently appearing only in asm's. 3704 if (OpInfo.CallOperandVal) { 3705 if (isa<BasicBlock>(OpInfo.CallOperandVal)) 3706 OpInfo.CallOperand = 3707 DAG.getBasicBlock(FuncInfo.MBBMap[cast<BasicBlock>( 3708 OpInfo.CallOperandVal)]); 3709 else { 3710 OpInfo.CallOperand = getValue(OpInfo.CallOperandVal); 3711 const Type *OpTy = OpInfo.CallOperandVal->getType(); 3712 // If this is an indirect operand, the operand is a pointer to the 3713 // accessed type. 3714 if (OpInfo.isIndirect) 3715 OpTy = cast<PointerType>(OpTy)->getElementType(); 3716 3717 // If OpTy is not a first-class value, it may be a struct/union that we 3718 // can tile with integers. 3719 if (!OpTy->isFirstClassType() && OpTy->isSized()) { 3720 unsigned BitSize = TD->getTypeSizeInBits(OpTy); 3721 switch (BitSize) { 3722 default: break; 3723 case 1: 3724 case 8: 3725 case 16: 3726 case 32: 3727 case 64: 3728 OpTy = IntegerType::get(BitSize); 3729 break; 3730 } 3731 } 3732 3733 OpVT = TLI.getValueType(OpTy, true); 3734 } 3735 } 3736 3737 OpInfo.ConstraintVT = OpVT; 3738 3739 // Compute the constraint code and ConstraintType to use. 3740 OpInfo.ComputeConstraintToUse(TLI); 3741 3742 // Keep track of whether we see an earlyclobber. 3743 SawEarlyClobber |= OpInfo.isEarlyClobber; 3744 3745 // If we see a clobber of a register, it is an early clobber. 3746 if (!SawEarlyClobber && 3747 OpInfo.Type == InlineAsm::isClobber && 3748 OpInfo.ConstraintType == TargetLowering::C_Register) { 3749 // Note that we want to ignore things that we don't trick here, like 3750 // dirflag, fpsr, flags, etc. 3751 std::pair<unsigned, const TargetRegisterClass*> PhysReg = 3752 TLI.getRegForInlineAsmConstraint(OpInfo.ConstraintCode, 3753 OpInfo.ConstraintVT); 3754 if (PhysReg.first || PhysReg.second) { 3755 // This is a register we know of. 3756 SawEarlyClobber = true; 3757 } 3758 } 3759 3760 // If this is a memory input, and if the operand is not indirect, do what we 3761 // need to to provide an address for the memory input. 3762 if (OpInfo.ConstraintType == TargetLowering::C_Memory && 3763 !OpInfo.isIndirect) { 3764 assert(OpInfo.Type == InlineAsm::isInput && 3765 "Can only indirectify direct input operands!"); 3766 3767 // Memory operands really want the address of the value. If we don't have 3768 // an indirect input, put it in the constpool if we can, otherwise spill 3769 // it to a stack slot. 3770 3771 // If the operand is a float, integer, or vector constant, spill to a 3772 // constant pool entry to get its address. 3773 Value *OpVal = OpInfo.CallOperandVal; 3774 if (isa<ConstantFP>(OpVal) || isa<ConstantInt>(OpVal) || 3775 isa<ConstantVector>(OpVal)) { 3776 OpInfo.CallOperand = DAG.getConstantPool(cast<Constant>(OpVal), 3777 TLI.getPointerTy()); 3778 } else { 3779 // Otherwise, create a stack slot and emit a store to it before the 3780 // asm. 3781 const Type *Ty = OpVal->getType(); 3782 uint64_t TySize = TLI.getTargetData()->getABITypeSize(Ty); 3783 unsigned Align = TLI.getTargetData()->getPrefTypeAlignment(Ty); 3784 MachineFunction &MF = DAG.getMachineFunction(); 3785 int SSFI = MF.getFrameInfo()->CreateStackObject(TySize, Align); 3786 SDOperand StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy()); 3787 Chain = DAG.getStore(Chain, OpInfo.CallOperand, StackSlot, NULL, 0); 3788 OpInfo.CallOperand = StackSlot; 3789 } 3790 3791 // There is no longer a Value* corresponding to this operand. 3792 OpInfo.CallOperandVal = 0; 3793 // It is now an indirect operand. 3794 OpInfo.isIndirect = true; 3795 } 3796 3797 // If this constraint is for a specific register, allocate it before 3798 // anything else. 3799 if (OpInfo.ConstraintType == TargetLowering::C_Register) 3800 GetRegistersForValue(OpInfo, SawEarlyClobber, OutputRegs, InputRegs); 3801 } 3802 ConstraintInfos.clear(); 3803 3804 3805 // Second pass - Loop over all of the operands, assigning virtual or physregs 3806 // to registerclass operands. 3807 for (unsigned i = 0, e = ConstraintOperands.size(); i != e; ++i) { 3808 SDISelAsmOperandInfo &OpInfo = ConstraintOperands[i]; 3809 3810 // C_Register operands have already been allocated, Other/Memory don't need 3811 // to be. 3812 if (OpInfo.ConstraintType == TargetLowering::C_RegisterClass) 3813 GetRegistersForValue(OpInfo, SawEarlyClobber, OutputRegs, InputRegs); 3814 } 3815 3816 // AsmNodeOperands - The operands for the ISD::INLINEASM node. 3817 std::vector<SDOperand> AsmNodeOperands; 3818 AsmNodeOperands.push_back(SDOperand()); // reserve space for input chain 3819 AsmNodeOperands.push_back( 3820 DAG.getTargetExternalSymbol(IA->getAsmString().c_str(), MVT::Other)); 3821 3822 3823 // Loop over all of the inputs, copying the operand values into the 3824 // appropriate registers and processing the output regs. 3825 RegsForValue RetValRegs; 3826 3827 // IndirectStoresToEmit - The set of stores to emit after the inline asm node. 3828 std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit; 3829 3830 for (unsigned i = 0, e = ConstraintOperands.size(); i != e; ++i) { 3831 SDISelAsmOperandInfo &OpInfo = ConstraintOperands[i]; 3832 3833 switch (OpInfo.Type) { 3834 case InlineAsm::isOutput: { 3835 if (OpInfo.ConstraintType != TargetLowering::C_RegisterClass && 3836 OpInfo.ConstraintType != TargetLowering::C_Register) { 3837 // Memory output, or 'other' output (e.g. 'X' constraint). 3838 assert(OpInfo.isIndirect && "Memory output must be indirect operand"); 3839 3840 // Add information to the INLINEASM node to know about this output. 3841 unsigned ResOpType = 4/*MEM*/ | (1 << 3); 3842 AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 3843 TLI.getPointerTy())); 3844 AsmNodeOperands.push_back(OpInfo.CallOperand); 3845 break; 3846 } 3847 3848 // Otherwise, this is a register or register class output. 3849 3850 // Copy the output from the appropriate register. Find a register that 3851 // we can use. 3852 if (OpInfo.AssignedRegs.Regs.empty()) { 3853 cerr << "Couldn't allocate output reg for contraint '" 3854 << OpInfo.ConstraintCode << "'!\n"; 3855 exit(1); 3856 } 3857 3858 if (!OpInfo.isIndirect) { 3859 // This is the result value of the call. 3860 assert(RetValRegs.Regs.empty() && 3861 "Cannot have multiple output constraints yet!"); 3862 assert(CS.getType() != Type::VoidTy && "Bad inline asm!"); 3863 RetValRegs = OpInfo.AssignedRegs; 3864 } else { 3865 IndirectStoresToEmit.push_back(std::make_pair(OpInfo.AssignedRegs, 3866 OpInfo.CallOperandVal)); 3867 } 3868 3869 // Add information to the INLINEASM node to know that this register is 3870 // set. 3871 OpInfo.AssignedRegs.AddInlineAsmOperands(2 /*REGDEF*/, DAG, 3872 AsmNodeOperands); 3873 break; 3874 } 3875 case InlineAsm::isInput: { 3876 SDOperand InOperandVal = OpInfo.CallOperand; 3877 3878 if (isdigit(OpInfo.ConstraintCode[0])) { // Matching constraint? 3879 // If this is required to match an output register we have already set, 3880 // just use its register. 3881 unsigned OperandNo = atoi(OpInfo.ConstraintCode.c_str()); 3882 3883 // Scan until we find the definition we already emitted of this operand. 3884 // When we find it, create a RegsForValue operand. 3885 unsigned CurOp = 2; // The first operand. 3886 for (; OperandNo; --OperandNo) { 3887 // Advance to the next operand. 3888 unsigned NumOps = 3889 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue(); 3890 assert(((NumOps & 7) == 2 /*REGDEF*/ || 3891 (NumOps & 7) == 4 /*MEM*/) && 3892 "Skipped past definitions?"); 3893 CurOp += (NumOps>>3)+1; 3894 } 3895 3896 unsigned NumOps = 3897 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue(); 3898 if ((NumOps & 7) == 2 /*REGDEF*/) { 3899 // Add NumOps>>3 registers to MatchedRegs. 3900 RegsForValue MatchedRegs; 3901 MatchedRegs.ValueVT = InOperandVal.getValueType(); 3902 MatchedRegs.RegVT = AsmNodeOperands[CurOp+1].getValueType(); 3903 for (unsigned i = 0, e = NumOps>>3; i != e; ++i) { 3904 unsigned Reg = 3905 cast<RegisterSDNode>(AsmNodeOperands[++CurOp])->getReg(); 3906 MatchedRegs.Regs.push_back(Reg); 3907 } 3908 3909 // Use the produced MatchedRegs object to 3910 MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, &Flag); 3911 MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands); 3912 break; 3913 } else { 3914 assert((NumOps & 7) == 4/*MEM*/ && "Unknown matching constraint!"); 3915 assert((NumOps >> 3) == 1 && "Unexpected number of operands"); 3916 // Add information to the INLINEASM node to know about this input. 3917 unsigned ResOpType = 4/*MEM*/ | (1 << 3); 3918 AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 3919 TLI.getPointerTy())); 3920 AsmNodeOperands.push_back(AsmNodeOperands[CurOp+1]); 3921 break; 3922 } 3923 } 3924 3925 if (OpInfo.ConstraintType == TargetLowering::C_Other) { 3926 assert(!OpInfo.isIndirect && 3927 "Don't know how to handle indirect other inputs yet!"); 3928 3929 std::vector<SDOperand> Ops; 3930 TLI.LowerAsmOperandForConstraint(InOperandVal, OpInfo.ConstraintCode[0], 3931 Ops, DAG); 3932 if (Ops.empty()) { 3933 cerr << "Invalid operand for inline asm constraint '" 3934 << OpInfo.ConstraintCode << "'!\n"; 3935 exit(1); 3936 } 3937 3938 // Add information to the INLINEASM node to know about this input. 3939 unsigned ResOpType = 3 /*IMM*/ | (Ops.size() << 3); 3940 AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 3941 TLI.getPointerTy())); 3942 AsmNodeOperands.insert(AsmNodeOperands.end(), Ops.begin(), Ops.end()); 3943 break; 3944 } else if (OpInfo.ConstraintType == TargetLowering::C_Memory) { 3945 assert(OpInfo.isIndirect && "Operand must be indirect to be a mem!"); 3946 assert(InOperandVal.getValueType() == TLI.getPointerTy() && 3947 "Memory operands expect pointer values"); 3948 3949 // Add information to the INLINEASM node to know about this input. 3950 unsigned ResOpType = 4/*MEM*/ | (1 << 3); 3951 AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 3952 TLI.getPointerTy())); 3953 AsmNodeOperands.push_back(InOperandVal); 3954 break; 3955 } 3956 3957 assert((OpInfo.ConstraintType == TargetLowering::C_RegisterClass || 3958 OpInfo.ConstraintType == TargetLowering::C_Register) && 3959 "Unknown constraint type!"); 3960 assert(!OpInfo.isIndirect && 3961 "Don't know how to handle indirect register inputs yet!"); 3962 3963 // Copy the input into the appropriate registers. 3964 assert(!OpInfo.AssignedRegs.Regs.empty() && 3965 "Couldn't allocate input reg!"); 3966 3967 OpInfo.AssignedRegs.getCopyToRegs(InOperandVal, DAG, Chain, &Flag); 3968 3969 OpInfo.AssignedRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG, 3970 AsmNodeOperands); 3971 break; 3972 } 3973 case InlineAsm::isClobber: { 3974 // Add the clobbered value to the operand list, so that the register 3975 // allocator is aware that the physreg got clobbered. 3976 if (!OpInfo.AssignedRegs.Regs.empty()) 3977 OpInfo.AssignedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG, 3978 AsmNodeOperands); 3979 break; 3980 } 3981 } 3982 } 3983 3984 // Finish up input operands. 3985 AsmNodeOperands[0] = Chain; 3986 if (Flag.Val) AsmNodeOperands.push_back(Flag); 3987 3988 Chain = DAG.getNode(ISD::INLINEASM, 3989 DAG.getNodeValueTypes(MVT::Other, MVT::Flag), 2, 3990 &AsmNodeOperands[0], AsmNodeOperands.size()); 3991 Flag = Chain.getValue(1); 3992 3993 // If this asm returns a register value, copy the result from that register 3994 // and set it as the value of the call. 3995 if (!RetValRegs.Regs.empty()) { 3996 SDOperand Val = RetValRegs.getCopyFromRegs(DAG, Chain, &Flag); 3997 3998 // If the result of the inline asm is a vector, it may have the wrong 3999 // width/num elts. Make sure to convert it to the right type with 4000 // bit_convert. 4001 if (MVT::isVector(Val.getValueType())) { 4002 const VectorType *VTy = cast<VectorType>(CS.getType()); 4003 MVT::ValueType DesiredVT = TLI.getValueType(VTy); 4004 4005 Val = DAG.getNode(ISD::BIT_CONVERT, DesiredVT, Val); 4006 } 4007 4008 setValue(CS.getInstruction(), Val); 4009 } 4010 4011 std::vector<std::pair<SDOperand, Value*> > StoresToEmit; 4012 4013 // Process indirect outputs, first output all of the flagged copies out of 4014 // physregs. 4015 for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) { 4016 RegsForValue &OutRegs = IndirectStoresToEmit[i].first; 4017 Value *Ptr = IndirectStoresToEmit[i].second; 4018 SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, &Flag); 4019 StoresToEmit.push_back(std::make_pair(OutVal, Ptr)); 4020 } 4021 4022 // Emit the non-flagged stores from the physregs. 4023 SmallVector<SDOperand, 8> OutChains; 4024 for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i) 4025 OutChains.push_back(DAG.getStore(Chain, StoresToEmit[i].first, 4026 getValue(StoresToEmit[i].second), 4027 StoresToEmit[i].second, 0)); 4028 if (!OutChains.empty()) 4029 Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, 4030 &OutChains[0], OutChains.size()); 4031 DAG.setRoot(Chain); 4032} 4033 4034 4035void SelectionDAGLowering::visitMalloc(MallocInst &I) { 4036 SDOperand Src = getValue(I.getOperand(0)); 4037 4038 MVT::ValueType IntPtr = TLI.getPointerTy(); 4039 4040 if (IntPtr < Src.getValueType()) 4041 Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src); 4042 else if (IntPtr > Src.getValueType()) 4043 Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src); 4044 4045 // Scale the source by the type size. 4046 uint64_t ElementSize = TD->getABITypeSize(I.getType()->getElementType()); 4047 Src = DAG.getNode(ISD::MUL, Src.getValueType(), 4048 Src, DAG.getIntPtrConstant(ElementSize)); 4049 4050 TargetLowering::ArgListTy Args; 4051 TargetLowering::ArgListEntry Entry; 4052 Entry.Node = Src; 4053 Entry.Ty = TLI.getTargetData()->getIntPtrType(); 4054 Args.push_back(Entry); 4055 4056 std::pair<SDOperand,SDOperand> Result = 4057 TLI.LowerCallTo(getRoot(), I.getType(), false, false, false, CallingConv::C, 4058 true, DAG.getExternalSymbol("malloc", IntPtr), Args, DAG); 4059 setValue(&I, Result.first); // Pointers always fit in registers 4060 DAG.setRoot(Result.second); 4061} 4062 4063void SelectionDAGLowering::visitFree(FreeInst &I) { 4064 TargetLowering::ArgListTy Args; 4065 TargetLowering::ArgListEntry Entry; 4066 Entry.Node = getValue(I.getOperand(0)); 4067 Entry.Ty = TLI.getTargetData()->getIntPtrType(); 4068 Args.push_back(Entry); 4069 MVT::ValueType IntPtr = TLI.getPointerTy(); 4070 std::pair<SDOperand,SDOperand> Result = 4071 TLI.LowerCallTo(getRoot(), Type::VoidTy, false, false, false, 4072 CallingConv::C, true, 4073 DAG.getExternalSymbol("free", IntPtr), Args, DAG); 4074 DAG.setRoot(Result.second); 4075} 4076 4077// EmitInstrWithCustomInserter - This method should be implemented by targets 4078// that mark instructions with the 'usesCustomDAGSchedInserter' flag. These 4079// instructions are special in various ways, which require special support to 4080// insert. The specified MachineInstr is created but not inserted into any 4081// basic blocks, and the scheduler passes ownership of it to this method. 4082MachineBasicBlock *TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI, 4083 MachineBasicBlock *MBB) { 4084 cerr << "If a target marks an instruction with " 4085 << "'usesCustomDAGSchedInserter', it must implement " 4086 << "TargetLowering::EmitInstrWithCustomInserter!\n"; 4087 abort(); 4088 return 0; 4089} 4090 4091void SelectionDAGLowering::visitVAStart(CallInst &I) { 4092 DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(), 4093 getValue(I.getOperand(1)), 4094 DAG.getSrcValue(I.getOperand(1)))); 4095} 4096 4097void SelectionDAGLowering::visitVAArg(VAArgInst &I) { 4098 SDOperand V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(), 4099 getValue(I.getOperand(0)), 4100 DAG.getSrcValue(I.getOperand(0))); 4101 setValue(&I, V); 4102 DAG.setRoot(V.getValue(1)); 4103} 4104 4105void SelectionDAGLowering::visitVAEnd(CallInst &I) { 4106 DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(), 4107 getValue(I.getOperand(1)), 4108 DAG.getSrcValue(I.getOperand(1)))); 4109} 4110 4111void SelectionDAGLowering::visitVACopy(CallInst &I) { 4112 DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(), 4113 getValue(I.getOperand(1)), 4114 getValue(I.getOperand(2)), 4115 DAG.getSrcValue(I.getOperand(1)), 4116 DAG.getSrcValue(I.getOperand(2)))); 4117} 4118 4119/// TargetLowering::LowerArguments - This is the default LowerArguments 4120/// implementation, which just inserts a FORMAL_ARGUMENTS node. FIXME: When all 4121/// targets are migrated to using FORMAL_ARGUMENTS, this hook should be 4122/// integrated into SDISel. 4123std::vector<SDOperand> 4124TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) { 4125 // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node. 4126 std::vector<SDOperand> Ops; 4127 Ops.push_back(DAG.getRoot()); 4128 Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy())); 4129 Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy())); 4130 4131 // Add one result value for each formal argument. 4132 std::vector<MVT::ValueType> RetVals; 4133 unsigned j = 1; 4134 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); 4135 I != E; ++I, ++j) { 4136 MVT::ValueType VT = getValueType(I->getType()); 4137 ISD::ArgFlagsTy Flags; 4138 unsigned OriginalAlignment = 4139 getTargetData()->getABITypeAlignment(I->getType()); 4140 4141 if (F.paramHasAttr(j, ParamAttr::ZExt)) 4142 Flags.setZExt(); 4143 if (F.paramHasAttr(j, ParamAttr::SExt)) 4144 Flags.setSExt(); 4145 if (F.paramHasAttr(j, ParamAttr::InReg)) 4146 Flags.setInReg(); 4147 if (F.paramHasAttr(j, ParamAttr::StructRet)) 4148 Flags.setSRet(); 4149 if (F.paramHasAttr(j, ParamAttr::ByVal)) { 4150 Flags.setByVal(); 4151 const PointerType *Ty = cast<PointerType>(I->getType()); 4152 const Type *ElementTy = Ty->getElementType(); 4153 unsigned FrameAlign = getByValTypeAlignment(ElementTy); 4154 unsigned FrameSize = getTargetData()->getABITypeSize(ElementTy); 4155 // For ByVal, alignment should be passed from FE. BE will guess if 4156 // this info is not there but there are cases it cannot get right. 4157 if (F.getParamAlignment(j)) 4158 FrameAlign = F.getParamAlignment(j); 4159 Flags.setByValAlign(FrameAlign); 4160 Flags.setByValSize(FrameSize); 4161 } 4162 if (F.paramHasAttr(j, ParamAttr::Nest)) 4163 Flags.setNest(); 4164 Flags.setOrigAlign(OriginalAlignment); 4165 4166 MVT::ValueType RegisterVT = getRegisterType(VT); 4167 unsigned NumRegs = getNumRegisters(VT); 4168 for (unsigned i = 0; i != NumRegs; ++i) { 4169 RetVals.push_back(RegisterVT); 4170 ISD::ArgFlagsTy MyFlags = Flags; 4171 if (NumRegs > 1 && i == 0) 4172 MyFlags.setSplit(); 4173 // if it isn't first piece, alignment must be 1 4174 else if (i > 0) 4175 MyFlags.setOrigAlign(1); 4176 Ops.push_back(DAG.getArgFlags(MyFlags)); 4177 } 4178 } 4179 4180 RetVals.push_back(MVT::Other); 4181 4182 // Create the node. 4183 SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS, 4184 DAG.getVTList(&RetVals[0], RetVals.size()), 4185 &Ops[0], Ops.size()).Val; 4186 4187 // Prelower FORMAL_ARGUMENTS. This isn't required for functionality, but 4188 // allows exposing the loads that may be part of the argument access to the 4189 // first DAGCombiner pass. 4190 SDOperand TmpRes = LowerOperation(SDOperand(Result, 0), DAG); 4191 4192 // The number of results should match up, except that the lowered one may have 4193 // an extra flag result. 4194 assert((Result->getNumValues() == TmpRes.Val->getNumValues() || 4195 (Result->getNumValues()+1 == TmpRes.Val->getNumValues() && 4196 TmpRes.getValue(Result->getNumValues()).getValueType() == MVT::Flag)) 4197 && "Lowering produced unexpected number of results!"); 4198 Result = TmpRes.Val; 4199 4200 unsigned NumArgRegs = Result->getNumValues() - 1; 4201 DAG.setRoot(SDOperand(Result, NumArgRegs)); 4202 4203 // Set up the return result vector. 4204 Ops.clear(); 4205 unsigned i = 0; 4206 unsigned Idx = 1; 4207 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; 4208 ++I, ++Idx) { 4209 MVT::ValueType VT = getValueType(I->getType()); 4210 MVT::ValueType PartVT = getRegisterType(VT); 4211 4212 unsigned NumParts = getNumRegisters(VT); 4213 SmallVector<SDOperand, 4> Parts(NumParts); 4214 for (unsigned j = 0; j != NumParts; ++j) 4215 Parts[j] = SDOperand(Result, i++); 4216 4217 ISD::NodeType AssertOp = ISD::DELETED_NODE; 4218 if (F.paramHasAttr(Idx, ParamAttr::SExt)) 4219 AssertOp = ISD::AssertSext; 4220 else if (F.paramHasAttr(Idx, ParamAttr::ZExt)) 4221 AssertOp = ISD::AssertZext; 4222 4223 Ops.push_back(getCopyFromParts(DAG, &Parts[0], NumParts, PartVT, VT, 4224 AssertOp)); 4225 } 4226 assert(i == NumArgRegs && "Argument register count mismatch!"); 4227 return Ops; 4228} 4229 4230 4231/// TargetLowering::LowerCallTo - This is the default LowerCallTo 4232/// implementation, which just inserts an ISD::CALL node, which is later custom 4233/// lowered by the target to something concrete. FIXME: When all targets are 4234/// migrated to using ISD::CALL, this hook should be integrated into SDISel. 4235std::pair<SDOperand, SDOperand> 4236TargetLowering::LowerCallTo(SDOperand Chain, const Type *RetTy, 4237 bool RetSExt, bool RetZExt, bool isVarArg, 4238 unsigned CallingConv, bool isTailCall, 4239 SDOperand Callee, 4240 ArgListTy &Args, SelectionDAG &DAG) { 4241 SmallVector<SDOperand, 32> Ops; 4242 Ops.push_back(Chain); // Op#0 - Chain 4243 Ops.push_back(DAG.getConstant(CallingConv, getPointerTy())); // Op#1 - CC 4244 Ops.push_back(DAG.getConstant(isVarArg, getPointerTy())); // Op#2 - VarArg 4245 Ops.push_back(DAG.getConstant(isTailCall, getPointerTy())); // Op#3 - Tail 4246 Ops.push_back(Callee); 4247 4248 // Handle all of the outgoing arguments. 4249 for (unsigned i = 0, e = Args.size(); i != e; ++i) { 4250 MVT::ValueType VT = getValueType(Args[i].Ty); 4251 SDOperand Op = Args[i].Node; 4252 ISD::ArgFlagsTy Flags; 4253 unsigned OriginalAlignment = 4254 getTargetData()->getABITypeAlignment(Args[i].Ty); 4255 4256 if (Args[i].isZExt) 4257 Flags.setZExt(); 4258 if (Args[i].isSExt) 4259 Flags.setSExt(); 4260 if (Args[i].isInReg) 4261 Flags.setInReg(); 4262 if (Args[i].isSRet) 4263 Flags.setSRet(); 4264 if (Args[i].isByVal) { 4265 Flags.setByVal(); 4266 const PointerType *Ty = cast<PointerType>(Args[i].Ty); 4267 const Type *ElementTy = Ty->getElementType(); 4268 unsigned FrameAlign = getByValTypeAlignment(ElementTy); 4269 unsigned FrameSize = getTargetData()->getABITypeSize(ElementTy); 4270 // For ByVal, alignment should come from FE. BE will guess if this 4271 // info is not there but there are cases it cannot get right. 4272 if (Args[i].Alignment) 4273 FrameAlign = Args[i].Alignment; 4274 Flags.setByValAlign(FrameAlign); 4275 Flags.setByValSize(FrameSize); 4276 } 4277 if (Args[i].isNest) 4278 Flags.setNest(); 4279 Flags.setOrigAlign(OriginalAlignment); 4280 4281 MVT::ValueType PartVT = getRegisterType(VT); 4282 unsigned NumParts = getNumRegisters(VT); 4283 SmallVector<SDOperand, 4> Parts(NumParts); 4284 ISD::NodeType ExtendKind = ISD::ANY_EXTEND; 4285 4286 if (Args[i].isSExt) 4287 ExtendKind = ISD::SIGN_EXTEND; 4288 else if (Args[i].isZExt) 4289 ExtendKind = ISD::ZERO_EXTEND; 4290 4291 getCopyToParts(DAG, Op, &Parts[0], NumParts, PartVT, ExtendKind); 4292 4293 for (unsigned i = 0; i != NumParts; ++i) { 4294 // if it isn't first piece, alignment must be 1 4295 ISD::ArgFlagsTy MyFlags = Flags; 4296 if (NumParts > 1 && i == 0) 4297 MyFlags.setSplit(); 4298 else if (i != 0) 4299 MyFlags.setOrigAlign(1); 4300 4301 Ops.push_back(Parts[i]); 4302 Ops.push_back(DAG.getArgFlags(MyFlags)); 4303 } 4304 } 4305 4306 // Figure out the result value types. We start by making a list of 4307 // the high-level LLVM return types. 4308 SmallVector<const Type *, 4> LLVMRetTys; 4309 if (const StructType *ST = dyn_cast<StructType>(RetTy)) 4310 // A struct return type in the LLVM IR means we have multiple return values. 4311 LLVMRetTys.insert(LLVMRetTys.end(), ST->element_begin(), ST->element_end()); 4312 else 4313 LLVMRetTys.push_back(RetTy); 4314 4315 // Then we translate that to a list of lowered codegen result types. 4316 SmallVector<MVT::ValueType, 4> LoweredRetTys; 4317 SmallVector<MVT::ValueType, 4> RetTys; 4318 for (unsigned I = 0, E = LLVMRetTys.size(); I != E; ++I) { 4319 MVT::ValueType VT = getValueType(LLVMRetTys[I]); 4320 RetTys.push_back(VT); 4321 4322 MVT::ValueType RegisterVT = getRegisterType(VT); 4323 unsigned NumRegs = getNumRegisters(VT); 4324 for (unsigned i = 0; i != NumRegs; ++i) 4325 LoweredRetTys.push_back(RegisterVT); 4326 } 4327 4328 LoweredRetTys.push_back(MVT::Other); // Always has a chain. 4329 4330 // Create the CALL node. 4331 SDOperand Res = DAG.getNode(ISD::CALL, 4332 DAG.getVTList(&LoweredRetTys[0], 4333 LoweredRetTys.size()), 4334 &Ops[0], Ops.size()); 4335 Chain = Res.getValue(LoweredRetTys.size() - 1); 4336 4337 // Gather up the call result into a single value. 4338 if (RetTy != Type::VoidTy) { 4339 ISD::NodeType AssertOp = ISD::DELETED_NODE; 4340 4341 if (RetSExt) 4342 AssertOp = ISD::AssertSext; 4343 else if (RetZExt) 4344 AssertOp = ISD::AssertZext; 4345 4346 SmallVector<SDOperand, 4> ReturnValues; 4347 unsigned RegNo = 0; 4348 for (unsigned I = 0, E = LLVMRetTys.size(); I != E; ++I) { 4349 MVT::ValueType VT = getValueType(LLVMRetTys[I]); 4350 MVT::ValueType RegisterVT = getRegisterType(VT); 4351 unsigned NumRegs = getNumRegisters(VT); 4352 unsigned RegNoEnd = NumRegs + RegNo; 4353 SmallVector<SDOperand, 4> Results; 4354 for (; RegNo != RegNoEnd; ++RegNo) 4355 Results.push_back(Res.getValue(RegNo)); 4356 SDOperand ReturnValue = 4357 getCopyFromParts(DAG, &Results[0], NumRegs, RegisterVT, VT, 4358 AssertOp); 4359 ReturnValues.push_back(ReturnValue); 4360 } 4361 Res = ReturnValues.size() == 1 ? ReturnValues.front() : 4362 DAG.getNode(ISD::MERGE_VALUES, 4363 DAG.getVTList(&RetTys[0], RetTys.size()), 4364 &ReturnValues[0], ReturnValues.size()); 4365 } 4366 4367 return std::make_pair(Res, Chain); 4368} 4369 4370SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) { 4371 assert(0 && "LowerOperation not implemented for this target!"); 4372 abort(); 4373 return SDOperand(); 4374} 4375 4376SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op, 4377 SelectionDAG &DAG) { 4378 assert(0 && "CustomPromoteOperation not implemented for this target!"); 4379 abort(); 4380 return SDOperand(); 4381} 4382 4383//===----------------------------------------------------------------------===// 4384// SelectionDAGISel code 4385//===----------------------------------------------------------------------===// 4386 4387unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) { 4388 return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT)); 4389} 4390 4391void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { 4392 AU.addRequired<AliasAnalysis>(); 4393 AU.addRequired<CollectorModuleMetadata>(); 4394 AU.setPreservesAll(); 4395} 4396 4397 4398 4399bool SelectionDAGISel::runOnFunction(Function &Fn) { 4400 // Get alias analysis for load/store combining. 4401 AA = &getAnalysis<AliasAnalysis>(); 4402 4403 MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine()); 4404 if (MF.getFunction()->hasCollector()) 4405 GCI = &getAnalysis<CollectorModuleMetadata>().get(*MF.getFunction()); 4406 else 4407 GCI = 0; 4408 RegInfo = &MF.getRegInfo(); 4409 DOUT << "\n\n\n=== " << Fn.getName() << "\n"; 4410 4411 FunctionLoweringInfo FuncInfo(TLI, Fn, MF); 4412 4413 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 4414 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(I->getTerminator())) 4415 // Mark landing pad. 4416 FuncInfo.MBBMap[Invoke->getSuccessor(1)]->setIsLandingPad(); 4417 4418 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 4419 SelectBasicBlock(I, MF, FuncInfo); 4420 4421 // Add function live-ins to entry block live-in set. 4422 BasicBlock *EntryBB = &Fn.getEntryBlock(); 4423 BB = FuncInfo.MBBMap[EntryBB]; 4424 if (!RegInfo->livein_empty()) 4425 for (MachineRegisterInfo::livein_iterator I = RegInfo->livein_begin(), 4426 E = RegInfo->livein_end(); I != E; ++I) 4427 BB->addLiveIn(I->first); 4428 4429#ifndef NDEBUG 4430 assert(FuncInfo.CatchInfoFound.size() == FuncInfo.CatchInfoLost.size() && 4431 "Not all catch info was assigned to a landing pad!"); 4432#endif 4433 4434 return true; 4435} 4436 4437void SelectionDAGLowering::CopyValueToVirtualRegister(Value *V, 4438 unsigned Reg) { 4439 SDOperand Op = getValue(V); 4440 assert((Op.getOpcode() != ISD::CopyFromReg || 4441 cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) && 4442 "Copy from a reg to the same reg!"); 4443 assert(!TargetRegisterInfo::isPhysicalRegister(Reg) && "Is a physreg"); 4444 4445 MVT::ValueType SrcVT = Op.getValueType(); 4446 MVT::ValueType RegisterVT = TLI.getRegisterType(SrcVT); 4447 unsigned NumRegs = TLI.getNumRegisters(SrcVT); 4448 SmallVector<SDOperand, 8> Regs(NumRegs); 4449 SmallVector<SDOperand, 8> Chains(NumRegs); 4450 4451 // Copy the value by legal parts into sequential virtual registers. 4452 getCopyToParts(DAG, Op, &Regs[0], NumRegs, RegisterVT); 4453 for (unsigned i = 0; i != NumRegs; ++i) 4454 Chains[i] = DAG.getCopyToReg(DAG.getEntryNode(), Reg + i, Regs[i]); 4455 SDOperand Ch = DAG.getNode(ISD::TokenFactor, MVT::Other, &Chains[0], NumRegs); 4456 PendingExports.push_back(Ch); 4457} 4458 4459void SelectionDAGISel:: 4460LowerArguments(BasicBlock *LLVMBB, SelectionDAGLowering &SDL) { 4461 // If this is the entry block, emit arguments. 4462 Function &F = *LLVMBB->getParent(); 4463 FunctionLoweringInfo &FuncInfo = SDL.FuncInfo; 4464 SDOperand OldRoot = SDL.DAG.getRoot(); 4465 std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG); 4466 4467 unsigned a = 0; 4468 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 4469 AI != E; ++AI, ++a) 4470 if (!AI->use_empty()) { 4471 SDL.setValue(AI, Args[a]); 4472 4473 // If this argument is live outside of the entry block, insert a copy from 4474 // whereever we got it to the vreg that other BB's will reference it as. 4475 DenseMap<const Value*, unsigned>::iterator VMI=FuncInfo.ValueMap.find(AI); 4476 if (VMI != FuncInfo.ValueMap.end()) { 4477 SDL.CopyValueToVirtualRegister(AI, VMI->second); 4478 } 4479 } 4480 4481 // Finally, if the target has anything special to do, allow it to do so. 4482 // FIXME: this should insert code into the DAG! 4483 EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction()); 4484} 4485 4486static void copyCatchInfo(BasicBlock *SrcBB, BasicBlock *DestBB, 4487 MachineModuleInfo *MMI, FunctionLoweringInfo &FLI) { 4488 for (BasicBlock::iterator I = SrcBB->begin(), E = --SrcBB->end(); I != E; ++I) 4489 if (isSelector(I)) { 4490 // Apply the catch info to DestBB. 4491 addCatchInfo(cast<CallInst>(*I), MMI, FLI.MBBMap[DestBB]); 4492#ifndef NDEBUG 4493 if (!FLI.MBBMap[SrcBB]->isLandingPad()) 4494 FLI.CatchInfoFound.insert(I); 4495#endif 4496 } 4497} 4498 4499/// CheckDAGForTailCallsAndFixThem - This Function looks for CALL nodes in the 4500/// DAG and fixes their tailcall attribute operand. 4501static void CheckDAGForTailCallsAndFixThem(SelectionDAG &DAG, 4502 TargetLowering& TLI) { 4503 SDNode * Ret = NULL; 4504 SDOperand Terminator = DAG.getRoot(); 4505 4506 // Find RET node. 4507 if (Terminator.getOpcode() == ISD::RET) { 4508 Ret = Terminator.Val; 4509 } 4510 4511 // Fix tail call attribute of CALL nodes. 4512 for (SelectionDAG::allnodes_iterator BE = DAG.allnodes_begin(), 4513 BI = prior(DAG.allnodes_end()); BI != BE; --BI) { 4514 if (BI->getOpcode() == ISD::CALL) { 4515 SDOperand OpRet(Ret, 0); 4516 SDOperand OpCall(static_cast<SDNode*>(BI), 0); 4517 bool isMarkedTailCall = 4518 cast<ConstantSDNode>(OpCall.getOperand(3))->getValue() != 0; 4519 // If CALL node has tail call attribute set to true and the call is not 4520 // eligible (no RET or the target rejects) the attribute is fixed to 4521 // false. The TargetLowering::IsEligibleForTailCallOptimization function 4522 // must correctly identify tail call optimizable calls. 4523 if (isMarkedTailCall && 4524 (Ret==NULL || 4525 !TLI.IsEligibleForTailCallOptimization(OpCall, OpRet, DAG))) { 4526 SmallVector<SDOperand, 32> Ops; 4527 unsigned idx=0; 4528 for(SDNode::op_iterator I =OpCall.Val->op_begin(), 4529 E=OpCall.Val->op_end(); I!=E; I++, idx++) { 4530 if (idx!=3) 4531 Ops.push_back(*I); 4532 else 4533 Ops.push_back(DAG.getConstant(false, TLI.getPointerTy())); 4534 } 4535 DAG.UpdateNodeOperands(OpCall, Ops.begin(), Ops.size()); 4536 } 4537 } 4538 } 4539} 4540 4541void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB, 4542 std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate, 4543 FunctionLoweringInfo &FuncInfo) { 4544 SelectionDAGLowering SDL(DAG, TLI, *AA, FuncInfo, GCI); 4545 4546 // Lower any arguments needed in this block if this is the entry block. 4547 if (LLVMBB == &LLVMBB->getParent()->getEntryBlock()) 4548 LowerArguments(LLVMBB, SDL); 4549 4550 BB = FuncInfo.MBBMap[LLVMBB]; 4551 SDL.setCurrentBasicBlock(BB); 4552 4553 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 4554 4555 if (MMI && BB->isLandingPad()) { 4556 // Add a label to mark the beginning of the landing pad. Deletion of the 4557 // landing pad can thus be detected via the MachineModuleInfo. 4558 unsigned LabelID = MMI->addLandingPad(BB); 4559 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, DAG.getEntryNode(), 4560 DAG.getConstant(LabelID, MVT::i32), 4561 DAG.getConstant(1, MVT::i32))); 4562 4563 // Mark exception register as live in. 4564 unsigned Reg = TLI.getExceptionAddressRegister(); 4565 if (Reg) BB->addLiveIn(Reg); 4566 4567 // Mark exception selector register as live in. 4568 Reg = TLI.getExceptionSelectorRegister(); 4569 if (Reg) BB->addLiveIn(Reg); 4570 4571 // FIXME: Hack around an exception handling flaw (PR1508): the personality 4572 // function and list of typeids logically belong to the invoke (or, if you 4573 // like, the basic block containing the invoke), and need to be associated 4574 // with it in the dwarf exception handling tables. Currently however the 4575 // information is provided by an intrinsic (eh.selector) that can be moved 4576 // to unexpected places by the optimizers: if the unwind edge is critical, 4577 // then breaking it can result in the intrinsics being in the successor of 4578 // the landing pad, not the landing pad itself. This results in exceptions 4579 // not being caught because no typeids are associated with the invoke. 4580 // This may not be the only way things can go wrong, but it is the only way 4581 // we try to work around for the moment. 4582 BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator()); 4583 4584 if (Br && Br->isUnconditional()) { // Critical edge? 4585 BasicBlock::iterator I, E; 4586 for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I) 4587 if (isSelector(I)) 4588 break; 4589 4590 if (I == E) 4591 // No catch info found - try to extract some from the successor. 4592 copyCatchInfo(Br->getSuccessor(0), LLVMBB, MMI, FuncInfo); 4593 } 4594 } 4595 4596 // Lower all of the non-terminator instructions. 4597 for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end(); 4598 I != E; ++I) 4599 SDL.visit(*I); 4600 4601 // Ensure that all instructions which are used outside of their defining 4602 // blocks are available as virtual registers. Invoke is handled elsewhere. 4603 for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I) 4604 if (!I->use_empty() && !isa<PHINode>(I) && !isa<InvokeInst>(I)) { 4605 DenseMap<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I); 4606 if (VMI != FuncInfo.ValueMap.end()) 4607 SDL.CopyValueToVirtualRegister(I, VMI->second); 4608 } 4609 4610 // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to 4611 // ensure constants are generated when needed. Remember the virtual registers 4612 // that need to be added to the Machine PHI nodes as input. We cannot just 4613 // directly add them, because expansion might result in multiple MBB's for one 4614 // BB. As such, the start of the BB might correspond to a different MBB than 4615 // the end. 4616 // 4617 TerminatorInst *TI = LLVMBB->getTerminator(); 4618 4619 // Emit constants only once even if used by multiple PHI nodes. 4620 std::map<Constant*, unsigned> ConstantsOut; 4621 4622 // Vector bool would be better, but vector<bool> is really slow. 4623 std::vector<unsigned char> SuccsHandled; 4624 if (TI->getNumSuccessors()) 4625 SuccsHandled.resize(BB->getParent()->getNumBlockIDs()); 4626 4627 // Check successor nodes' PHI nodes that expect a constant to be available 4628 // from this block. 4629 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { 4630 BasicBlock *SuccBB = TI->getSuccessor(succ); 4631 if (!isa<PHINode>(SuccBB->begin())) continue; 4632 MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB]; 4633 4634 // If this terminator has multiple identical successors (common for 4635 // switches), only handle each succ once. 4636 unsigned SuccMBBNo = SuccMBB->getNumber(); 4637 if (SuccsHandled[SuccMBBNo]) continue; 4638 SuccsHandled[SuccMBBNo] = true; 4639 4640 MachineBasicBlock::iterator MBBI = SuccMBB->begin(); 4641 PHINode *PN; 4642 4643 // At this point we know that there is a 1-1 correspondence between LLVM PHI 4644 // nodes and Machine PHI nodes, but the incoming operands have not been 4645 // emitted yet. 4646 for (BasicBlock::iterator I = SuccBB->begin(); 4647 (PN = dyn_cast<PHINode>(I)); ++I) { 4648 // Ignore dead phi's. 4649 if (PN->use_empty()) continue; 4650 4651 unsigned Reg; 4652 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 4653 4654 if (Constant *C = dyn_cast<Constant>(PHIOp)) { 4655 unsigned &RegOut = ConstantsOut[C]; 4656 if (RegOut == 0) { 4657 RegOut = FuncInfo.CreateRegForValue(C); 4658 SDL.CopyValueToVirtualRegister(C, RegOut); 4659 } 4660 Reg = RegOut; 4661 } else { 4662 Reg = FuncInfo.ValueMap[PHIOp]; 4663 if (Reg == 0) { 4664 assert(isa<AllocaInst>(PHIOp) && 4665 FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) && 4666 "Didn't codegen value into a register!??"); 4667 Reg = FuncInfo.CreateRegForValue(PHIOp); 4668 SDL.CopyValueToVirtualRegister(PHIOp, Reg); 4669 } 4670 } 4671 4672 // Remember that this register needs to added to the machine PHI node as 4673 // the input for this MBB. 4674 MVT::ValueType VT = TLI.getValueType(PN->getType()); 4675 unsigned NumRegisters = TLI.getNumRegisters(VT); 4676 for (unsigned i = 0, e = NumRegisters; i != e; ++i) 4677 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i)); 4678 } 4679 } 4680 ConstantsOut.clear(); 4681 4682 // Lower the terminator after the copies are emitted. 4683 SDL.visit(*LLVMBB->getTerminator()); 4684 4685 // Copy over any CaseBlock records that may now exist due to SwitchInst 4686 // lowering, as well as any jump table information. 4687 SwitchCases.clear(); 4688 SwitchCases = SDL.SwitchCases; 4689 JTCases.clear(); 4690 JTCases = SDL.JTCases; 4691 BitTestCases.clear(); 4692 BitTestCases = SDL.BitTestCases; 4693 4694 // Make sure the root of the DAG is up-to-date. 4695 DAG.setRoot(SDL.getControlRoot()); 4696 4697 // Check whether calls in this block are real tail calls. Fix up CALL nodes 4698 // with correct tailcall attribute so that the target can rely on the tailcall 4699 // attribute indicating whether the call is really eligible for tail call 4700 // optimization. 4701 CheckDAGForTailCallsAndFixThem(DAG, TLI); 4702} 4703 4704void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) { 4705 DOUT << "Lowered selection DAG:\n"; 4706 DEBUG(DAG.dump()); 4707 4708 // Run the DAG combiner in pre-legalize mode. 4709 DAG.Combine(false, *AA); 4710 4711 DOUT << "Optimized lowered selection DAG:\n"; 4712 DEBUG(DAG.dump()); 4713 4714 // Second step, hack on the DAG until it only uses operations and types that 4715 // the target supports. 4716#if 0 // Enable this some day. 4717 DAG.LegalizeTypes(); 4718 // Someday even later, enable a dag combine pass here. 4719#endif 4720 DAG.Legalize(); 4721 4722 DOUT << "Legalized selection DAG:\n"; 4723 DEBUG(DAG.dump()); 4724 4725 // Run the DAG combiner in post-legalize mode. 4726 DAG.Combine(true, *AA); 4727 4728 DOUT << "Optimized legalized selection DAG:\n"; 4729 DEBUG(DAG.dump()); 4730 4731 if (ViewISelDAGs) DAG.viewGraph(); 4732 4733 // Third, instruction select all of the operations to machine code, adding the 4734 // code to the MachineBasicBlock. 4735 InstructionSelectBasicBlock(DAG); 4736 4737 DOUT << "Selected machine code:\n"; 4738 DEBUG(BB->dump()); 4739} 4740 4741void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, 4742 FunctionLoweringInfo &FuncInfo) { 4743 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate; 4744 { 4745 SelectionDAG DAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4746 CurDAG = &DAG; 4747 4748 // First step, lower LLVM code to some DAG. This DAG may use operations and 4749 // types that are not supported by the target. 4750 BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo); 4751 4752 // Second step, emit the lowered DAG as machine code. 4753 CodeGenAndEmitDAG(DAG); 4754 } 4755 4756 DOUT << "Total amount of phi nodes to update: " 4757 << PHINodesToUpdate.size() << "\n"; 4758 DEBUG(for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) 4759 DOUT << "Node " << i << " : (" << PHINodesToUpdate[i].first 4760 << ", " << PHINodesToUpdate[i].second << ")\n";); 4761 4762 // Next, now that we know what the last MBB the LLVM BB expanded is, update 4763 // PHI nodes in successors. 4764 if (SwitchCases.empty() && JTCases.empty() && BitTestCases.empty()) { 4765 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) { 4766 MachineInstr *PHI = PHINodesToUpdate[i].first; 4767 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 4768 "This is not a machine PHI node that we are updating!"); 4769 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[i].second, 4770 false)); 4771 PHI->addOperand(MachineOperand::CreateMBB(BB)); 4772 } 4773 return; 4774 } 4775 4776 for (unsigned i = 0, e = BitTestCases.size(); i != e; ++i) { 4777 // Lower header first, if it wasn't already lowered 4778 if (!BitTestCases[i].Emitted) { 4779 SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4780 CurDAG = &HSDAG; 4781 SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI); 4782 // Set the current basic block to the mbb we wish to insert the code into 4783 BB = BitTestCases[i].Parent; 4784 HSDL.setCurrentBasicBlock(BB); 4785 // Emit the code 4786 HSDL.visitBitTestHeader(BitTestCases[i]); 4787 HSDAG.setRoot(HSDL.getRoot()); 4788 CodeGenAndEmitDAG(HSDAG); 4789 } 4790 4791 for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) { 4792 SelectionDAG BSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4793 CurDAG = &BSDAG; 4794 SelectionDAGLowering BSDL(BSDAG, TLI, *AA, FuncInfo, GCI); 4795 // Set the current basic block to the mbb we wish to insert the code into 4796 BB = BitTestCases[i].Cases[j].ThisBB; 4797 BSDL.setCurrentBasicBlock(BB); 4798 // Emit the code 4799 if (j+1 != ej) 4800 BSDL.visitBitTestCase(BitTestCases[i].Cases[j+1].ThisBB, 4801 BitTestCases[i].Reg, 4802 BitTestCases[i].Cases[j]); 4803 else 4804 BSDL.visitBitTestCase(BitTestCases[i].Default, 4805 BitTestCases[i].Reg, 4806 BitTestCases[i].Cases[j]); 4807 4808 4809 BSDAG.setRoot(BSDL.getRoot()); 4810 CodeGenAndEmitDAG(BSDAG); 4811 } 4812 4813 // Update PHI Nodes 4814 for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) { 4815 MachineInstr *PHI = PHINodesToUpdate[pi].first; 4816 MachineBasicBlock *PHIBB = PHI->getParent(); 4817 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 4818 "This is not a machine PHI node that we are updating!"); 4819 // This is "default" BB. We have two jumps to it. From "header" BB and 4820 // from last "case" BB. 4821 if (PHIBB == BitTestCases[i].Default) { 4822 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, 4823 false)); 4824 PHI->addOperand(MachineOperand::CreateMBB(BitTestCases[i].Parent)); 4825 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, 4826 false)); 4827 PHI->addOperand(MachineOperand::CreateMBB(BitTestCases[i].Cases. 4828 back().ThisBB)); 4829 } 4830 // One of "cases" BB. 4831 for (unsigned j = 0, ej = BitTestCases[i].Cases.size(); j != ej; ++j) { 4832 MachineBasicBlock* cBB = BitTestCases[i].Cases[j].ThisBB; 4833 if (cBB->succ_end() != 4834 std::find(cBB->succ_begin(),cBB->succ_end(), PHIBB)) { 4835 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, 4836 false)); 4837 PHI->addOperand(MachineOperand::CreateMBB(cBB)); 4838 } 4839 } 4840 } 4841 } 4842 4843 // If the JumpTable record is filled in, then we need to emit a jump table. 4844 // Updating the PHI nodes is tricky in this case, since we need to determine 4845 // whether the PHI is a successor of the range check MBB or the jump table MBB 4846 for (unsigned i = 0, e = JTCases.size(); i != e; ++i) { 4847 // Lower header first, if it wasn't already lowered 4848 if (!JTCases[i].first.Emitted) { 4849 SelectionDAG HSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4850 CurDAG = &HSDAG; 4851 SelectionDAGLowering HSDL(HSDAG, TLI, *AA, FuncInfo, GCI); 4852 // Set the current basic block to the mbb we wish to insert the code into 4853 BB = JTCases[i].first.HeaderBB; 4854 HSDL.setCurrentBasicBlock(BB); 4855 // Emit the code 4856 HSDL.visitJumpTableHeader(JTCases[i].second, JTCases[i].first); 4857 HSDAG.setRoot(HSDL.getRoot()); 4858 CodeGenAndEmitDAG(HSDAG); 4859 } 4860 4861 SelectionDAG JSDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4862 CurDAG = &JSDAG; 4863 SelectionDAGLowering JSDL(JSDAG, TLI, *AA, FuncInfo, GCI); 4864 // Set the current basic block to the mbb we wish to insert the code into 4865 BB = JTCases[i].second.MBB; 4866 JSDL.setCurrentBasicBlock(BB); 4867 // Emit the code 4868 JSDL.visitJumpTable(JTCases[i].second); 4869 JSDAG.setRoot(JSDL.getRoot()); 4870 CodeGenAndEmitDAG(JSDAG); 4871 4872 // Update PHI Nodes 4873 for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) { 4874 MachineInstr *PHI = PHINodesToUpdate[pi].first; 4875 MachineBasicBlock *PHIBB = PHI->getParent(); 4876 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 4877 "This is not a machine PHI node that we are updating!"); 4878 // "default" BB. We can go there only from header BB. 4879 if (PHIBB == JTCases[i].second.Default) { 4880 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, 4881 false)); 4882 PHI->addOperand(MachineOperand::CreateMBB(JTCases[i].first.HeaderBB)); 4883 } 4884 // JT BB. Just iterate over successors here 4885 if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) { 4886 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pi].second, 4887 false)); 4888 PHI->addOperand(MachineOperand::CreateMBB(BB)); 4889 } 4890 } 4891 } 4892 4893 // If the switch block involved a branch to one of the actual successors, we 4894 // need to update PHI nodes in that block. 4895 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) { 4896 MachineInstr *PHI = PHINodesToUpdate[i].first; 4897 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 4898 "This is not a machine PHI node that we are updating!"); 4899 if (BB->isSuccessor(PHI->getParent())) { 4900 PHI->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[i].second, 4901 false)); 4902 PHI->addOperand(MachineOperand::CreateMBB(BB)); 4903 } 4904 } 4905 4906 // If we generated any switch lowering information, build and codegen any 4907 // additional DAGs necessary. 4908 for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) { 4909 SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4910 CurDAG = &SDAG; 4911 SelectionDAGLowering SDL(SDAG, TLI, *AA, FuncInfo, GCI); 4912 4913 // Set the current basic block to the mbb we wish to insert the code into 4914 BB = SwitchCases[i].ThisBB; 4915 SDL.setCurrentBasicBlock(BB); 4916 4917 // Emit the code 4918 SDL.visitSwitchCase(SwitchCases[i]); 4919 SDAG.setRoot(SDL.getRoot()); 4920 CodeGenAndEmitDAG(SDAG); 4921 4922 // Handle any PHI nodes in successors of this chunk, as if we were coming 4923 // from the original BB before switch expansion. Note that PHI nodes can 4924 // occur multiple times in PHINodesToUpdate. We have to be very careful to 4925 // handle them the right number of times. 4926 while ((BB = SwitchCases[i].TrueBB)) { // Handle LHS and RHS. 4927 for (MachineBasicBlock::iterator Phi = BB->begin(); 4928 Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){ 4929 // This value for this PHI node is recorded in PHINodesToUpdate, get it. 4930 for (unsigned pn = 0; ; ++pn) { 4931 assert(pn != PHINodesToUpdate.size() && "Didn't find PHI entry!"); 4932 if (PHINodesToUpdate[pn].first == Phi) { 4933 Phi->addOperand(MachineOperand::CreateReg(PHINodesToUpdate[pn]. 4934 second, false)); 4935 Phi->addOperand(MachineOperand::CreateMBB(SwitchCases[i].ThisBB)); 4936 break; 4937 } 4938 } 4939 } 4940 4941 // Don't process RHS if same block as LHS. 4942 if (BB == SwitchCases[i].FalseBB) 4943 SwitchCases[i].FalseBB = 0; 4944 4945 // If we haven't handled the RHS, do so now. Otherwise, we're done. 4946 SwitchCases[i].TrueBB = SwitchCases[i].FalseBB; 4947 SwitchCases[i].FalseBB = 0; 4948 } 4949 assert(SwitchCases[i].TrueBB == 0 && SwitchCases[i].FalseBB == 0); 4950 } 4951} 4952 4953 4954//===----------------------------------------------------------------------===// 4955/// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each 4956/// target node in the graph. 4957void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) { 4958 if (ViewSchedDAGs) DAG.viewGraph(); 4959 4960 RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault(); 4961 4962 if (!Ctor) { 4963 Ctor = ISHeuristic; 4964 RegisterScheduler::setDefault(Ctor); 4965 } 4966 4967 ScheduleDAG *SL = Ctor(this, &DAG, BB); 4968 BB = SL->Run(); 4969 4970 if (ViewSUnitDAGs) SL->viewGraph(); 4971 4972 delete SL; 4973} 4974 4975 4976HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() { 4977 return new HazardRecognizer(); 4978} 4979 4980//===----------------------------------------------------------------------===// 4981// Helper functions used by the generated instruction selector. 4982//===----------------------------------------------------------------------===// 4983// Calls to these methods are generated by tblgen. 4984 4985/// CheckAndMask - The isel is trying to match something like (and X, 255). If 4986/// the dag combiner simplified the 255, we still want to match. RHS is the 4987/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value 4988/// specified in the .td file (e.g. 255). 4989bool SelectionDAGISel::CheckAndMask(SDOperand LHS, ConstantSDNode *RHS, 4990 int64_t DesiredMaskS) const { 4991 const APInt &ActualMask = RHS->getAPIntValue(); 4992 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 4993 4994 // If the actual mask exactly matches, success! 4995 if (ActualMask == DesiredMask) 4996 return true; 4997 4998 // If the actual AND mask is allowing unallowed bits, this doesn't match. 4999 if (ActualMask.intersects(~DesiredMask)) 5000 return false; 5001 5002 // Otherwise, the DAG Combiner may have proven that the value coming in is 5003 // either already zero or is not demanded. Check for known zero input bits. 5004 APInt NeededMask = DesiredMask & ~ActualMask; 5005 if (CurDAG->MaskedValueIsZero(LHS, NeededMask)) 5006 return true; 5007 5008 // TODO: check to see if missing bits are just not demanded. 5009 5010 // Otherwise, this pattern doesn't match. 5011 return false; 5012} 5013 5014/// CheckOrMask - The isel is trying to match something like (or X, 255). If 5015/// the dag combiner simplified the 255, we still want to match. RHS is the 5016/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value 5017/// specified in the .td file (e.g. 255). 5018bool SelectionDAGISel::CheckOrMask(SDOperand LHS, ConstantSDNode *RHS, 5019 int64_t DesiredMaskS) const { 5020 const APInt &ActualMask = RHS->getAPIntValue(); 5021 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 5022 5023 // If the actual mask exactly matches, success! 5024 if (ActualMask == DesiredMask) 5025 return true; 5026 5027 // If the actual AND mask is allowing unallowed bits, this doesn't match. 5028 if (ActualMask.intersects(~DesiredMask)) 5029 return false; 5030 5031 // Otherwise, the DAG Combiner may have proven that the value coming in is 5032 // either already zero or is not demanded. Check for known zero input bits. 5033 APInt NeededMask = DesiredMask & ~ActualMask; 5034 5035 APInt KnownZero, KnownOne; 5036 CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne); 5037 5038 // If all the missing bits in the or are already known to be set, match! 5039 if ((NeededMask & KnownOne) == NeededMask) 5040 return true; 5041 5042 // TODO: check to see if missing bits are just not demanded. 5043 5044 // Otherwise, this pattern doesn't match. 5045 return false; 5046} 5047 5048 5049/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated 5050/// by tblgen. Others should not call it. 5051void SelectionDAGISel:: 5052SelectInlineAsmMemoryOperands(std::vector<SDOperand> &Ops, SelectionDAG &DAG) { 5053 std::vector<SDOperand> InOps; 5054 std::swap(InOps, Ops); 5055 5056 Ops.push_back(InOps[0]); // input chain. 5057 Ops.push_back(InOps[1]); // input asm string. 5058 5059 unsigned i = 2, e = InOps.size(); 5060 if (InOps[e-1].getValueType() == MVT::Flag) 5061 --e; // Don't process a flag operand if it is here. 5062 5063 while (i != e) { 5064 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue(); 5065 if ((Flags & 7) != 4 /*MEM*/) { 5066 // Just skip over this operand, copying the operands verbatim. 5067 Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1); 5068 i += (Flags >> 3) + 1; 5069 } else { 5070 assert((Flags >> 3) == 1 && "Memory operand with multiple values?"); 5071 // Otherwise, this is a memory operand. Ask the target to select it. 5072 std::vector<SDOperand> SelOps; 5073 if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) { 5074 cerr << "Could not match memory address. Inline asm failure!\n"; 5075 exit(1); 5076 } 5077 5078 // Add this to the output node. 5079 MVT::ValueType IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy(); 5080 Ops.push_back(DAG.getTargetConstant(4/*MEM*/ | (SelOps.size() << 3), 5081 IntPtrTy)); 5082 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end()); 5083 i += 2; 5084 } 5085 } 5086 5087 // Add the flag input back if present. 5088 if (e != InOps.size()) 5089 Ops.push_back(InOps.back()); 5090} 5091 5092char SelectionDAGISel::ID = 0; 5093