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