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