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