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