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