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