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