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