SelectionDAGISel.cpp revision bcc5f36765e8111c13873a0c0dc874c92385d808
1//===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file was developed by the LLVM research group and is distributed under 6// the University of Illinois Open Source 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/Analysis/AliasAnalysis.h" 16#include "llvm/CodeGen/SelectionDAGISel.h" 17#include "llvm/CodeGen/ScheduleDAG.h" 18#include "llvm/CallingConv.h" 19#include "llvm/Constants.h" 20#include "llvm/DerivedTypes.h" 21#include "llvm/Function.h" 22#include "llvm/GlobalVariable.h" 23#include "llvm/InlineAsm.h" 24#include "llvm/Instructions.h" 25#include "llvm/Intrinsics.h" 26#include "llvm/IntrinsicInst.h" 27#include "llvm/CodeGen/MachineModuleInfo.h" 28#include "llvm/CodeGen/MachineFunction.h" 29#include "llvm/CodeGen/MachineFrameInfo.h" 30#include "llvm/CodeGen/MachineJumpTableInfo.h" 31#include "llvm/CodeGen/MachineInstrBuilder.h" 32#include "llvm/CodeGen/SchedulerRegistry.h" 33#include "llvm/CodeGen/SelectionDAG.h" 34#include "llvm/CodeGen/SSARegMap.h" 35#include "llvm/Target/MRegisterInfo.h" 36#include "llvm/Target/TargetAsmInfo.h" 37#include "llvm/Target/TargetData.h" 38#include "llvm/Target/TargetFrameInfo.h" 39#include "llvm/Target/TargetInstrInfo.h" 40#include "llvm/Target/TargetLowering.h" 41#include "llvm/Target/TargetMachine.h" 42#include "llvm/Target/TargetOptions.h" 43#include "llvm/Transforms/Utils/BasicBlockUtils.h" 44#include "llvm/Support/MathExtras.h" 45#include "llvm/Support/Debug.h" 46#include "llvm/Support/Compiler.h" 47#include <algorithm> 48using namespace llvm; 49 50#ifndef NDEBUG 51static cl::opt<bool> 52ViewISelDAGs("view-isel-dags", cl::Hidden, 53 cl::desc("Pop up a window to show isel dags as they are selected")); 54static cl::opt<bool> 55ViewSchedDAGs("view-sched-dags", cl::Hidden, 56 cl::desc("Pop up a window to show sched dags as they are processed")); 57#else 58static const bool ViewISelDAGs = 0, ViewSchedDAGs = 0; 59#endif 60 61 62//===---------------------------------------------------------------------===// 63/// 64/// RegisterScheduler class - Track the registration of instruction schedulers. 65/// 66//===---------------------------------------------------------------------===// 67MachinePassRegistry RegisterScheduler::Registry; 68 69//===---------------------------------------------------------------------===// 70/// 71/// ISHeuristic command line option for instruction schedulers. 72/// 73//===---------------------------------------------------------------------===// 74namespace { 75 cl::opt<RegisterScheduler::FunctionPassCtor, false, 76 RegisterPassParser<RegisterScheduler> > 77 ISHeuristic("sched", 78 cl::init(&createDefaultScheduler), 79 cl::desc("Instruction schedulers available:")); 80 81 static RegisterScheduler 82 defaultListDAGScheduler("default", " Best scheduler for the target", 83 createDefaultScheduler); 84} // namespace 85 86namespace { 87 /// RegsForValue - This struct represents the physical registers that a 88 /// particular value is assigned and the type information about the value. 89 /// This is needed because values can be promoted into larger registers and 90 /// expanded into multiple smaller registers than the value. 91 struct VISIBILITY_HIDDEN RegsForValue { 92 /// Regs - This list hold the register (for legal and promoted values) 93 /// or register set (for expanded values) that the value should be assigned 94 /// to. 95 std::vector<unsigned> Regs; 96 97 /// RegVT - The value type of each register. 98 /// 99 MVT::ValueType RegVT; 100 101 /// ValueVT - The value type of the LLVM value, which may be promoted from 102 /// RegVT or made from merging the two expanded parts. 103 MVT::ValueType ValueVT; 104 105 RegsForValue() : RegVT(MVT::Other), ValueVT(MVT::Other) {} 106 107 RegsForValue(unsigned Reg, MVT::ValueType regvt, MVT::ValueType valuevt) 108 : RegVT(regvt), ValueVT(valuevt) { 109 Regs.push_back(Reg); 110 } 111 RegsForValue(const std::vector<unsigned> ®s, 112 MVT::ValueType regvt, MVT::ValueType valuevt) 113 : Regs(regs), RegVT(regvt), ValueVT(valuevt) { 114 } 115 116 /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from 117 /// this value and returns the result as a ValueVT value. This uses 118 /// Chain/Flag as the input and updates them for the output Chain/Flag. 119 SDOperand getCopyFromRegs(SelectionDAG &DAG, 120 SDOperand &Chain, SDOperand &Flag) const; 121 122 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the 123 /// specified value into the registers specified by this object. This uses 124 /// Chain/Flag as the input and updates them for the output Chain/Flag. 125 void getCopyToRegs(SDOperand Val, SelectionDAG &DAG, 126 SDOperand &Chain, SDOperand &Flag, 127 MVT::ValueType PtrVT) const; 128 129 /// AddInlineAsmOperands - Add this value to the specified inlineasm node 130 /// operand list. This adds the code marker and includes the number of 131 /// values added into it. 132 void AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG, 133 std::vector<SDOperand> &Ops) const; 134 }; 135} 136 137namespace llvm { 138 //===--------------------------------------------------------------------===// 139 /// createDefaultScheduler - This creates an instruction scheduler appropriate 140 /// for the target. 141 ScheduleDAG* createDefaultScheduler(SelectionDAGISel *IS, 142 SelectionDAG *DAG, 143 MachineBasicBlock *BB) { 144 TargetLowering &TLI = IS->getTargetLowering(); 145 146 if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) { 147 return createTDListDAGScheduler(IS, DAG, BB); 148 } else { 149 assert(TLI.getSchedulingPreference() == 150 TargetLowering::SchedulingForRegPressure && "Unknown sched type!"); 151 return createBURRListDAGScheduler(IS, DAG, BB); 152 } 153 } 154 155 156 //===--------------------------------------------------------------------===// 157 /// FunctionLoweringInfo - This contains information that is global to a 158 /// function that is used when lowering a region of the function. 159 class FunctionLoweringInfo { 160 public: 161 TargetLowering &TLI; 162 Function &Fn; 163 MachineFunction &MF; 164 SSARegMap *RegMap; 165 166 FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF); 167 168 /// MBBMap - A mapping from LLVM basic blocks to their machine code entry. 169 std::map<const BasicBlock*, MachineBasicBlock *> MBBMap; 170 171 /// ValueMap - Since we emit code for the function a basic block at a time, 172 /// we must remember which virtual registers hold the values for 173 /// cross-basic-block values. 174 std::map<const Value*, unsigned> ValueMap; 175 176 /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in 177 /// the entry block. This allows the allocas to be efficiently referenced 178 /// anywhere in the function. 179 std::map<const AllocaInst*, int> StaticAllocaMap; 180 181 unsigned MakeReg(MVT::ValueType VT) { 182 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT)); 183 } 184 185 /// isExportedInst - Return true if the specified value is an instruction 186 /// exported from its block. 187 bool isExportedInst(const Value *V) { 188 return ValueMap.count(V); 189 } 190 191 unsigned CreateRegForValue(const Value *V); 192 193 unsigned InitializeRegForValue(const Value *V) { 194 unsigned &R = ValueMap[V]; 195 assert(R == 0 && "Already initialized this value register!"); 196 return R = CreateRegForValue(V); 197 } 198 }; 199} 200 201/// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by 202/// PHI nodes or outside of the basic block that defines it, or used by a 203/// switch instruction, which may expand to multiple basic blocks. 204static bool isUsedOutsideOfDefiningBlock(Instruction *I) { 205 if (isa<PHINode>(I)) return true; 206 BasicBlock *BB = I->getParent(); 207 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) 208 if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI) || 209 // FIXME: Remove switchinst special case. 210 isa<SwitchInst>(*UI)) 211 return true; 212 return false; 213} 214 215/// isOnlyUsedInEntryBlock - If the specified argument is only used in the 216/// entry block, return true. This includes arguments used by switches, since 217/// the switch may expand into multiple basic blocks. 218static bool isOnlyUsedInEntryBlock(Argument *A) { 219 BasicBlock *Entry = A->getParent()->begin(); 220 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI) 221 if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI)) 222 return false; // Use not in entry block. 223 return true; 224} 225 226FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli, 227 Function &fn, MachineFunction &mf) 228 : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) { 229 230 // Create a vreg for each argument register that is not dead and is used 231 // outside of the entry block for the function. 232 for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end(); 233 AI != E; ++AI) 234 if (!isOnlyUsedInEntryBlock(AI)) 235 InitializeRegForValue(AI); 236 237 // Initialize the mapping of values to registers. This is only set up for 238 // instruction values that are used outside of the block that defines 239 // them. 240 Function::iterator BB = Fn.begin(), EB = Fn.end(); 241 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 242 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 243 if (ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) { 244 const Type *Ty = AI->getAllocatedType(); 245 uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty); 246 unsigned Align = 247 std::max((unsigned)TLI.getTargetData()->getTypeAlignmentPref(Ty), 248 AI->getAlignment()); 249 250 TySize *= CUI->getZExtValue(); // Get total allocated size. 251 if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects. 252 StaticAllocaMap[AI] = 253 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align); 254 } 255 256 for (; BB != EB; ++BB) 257 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 258 if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I)) 259 if (!isa<AllocaInst>(I) || 260 !StaticAllocaMap.count(cast<AllocaInst>(I))) 261 InitializeRegForValue(I); 262 263 // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This 264 // also creates the initial PHI MachineInstrs, though none of the input 265 // operands are populated. 266 for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) { 267 MachineBasicBlock *MBB = new MachineBasicBlock(BB); 268 MBBMap[BB] = MBB; 269 MF.getBasicBlockList().push_back(MBB); 270 271 // Create Machine PHI nodes for LLVM PHI nodes, lowering them as 272 // appropriate. 273 PHINode *PN; 274 for (BasicBlock::iterator I = BB->begin();(PN = dyn_cast<PHINode>(I)); ++I){ 275 if (PN->use_empty()) continue; 276 277 MVT::ValueType VT = TLI.getValueType(PN->getType()); 278 unsigned NumElements; 279 if (VT != MVT::Vector) 280 NumElements = TLI.getNumElements(VT); 281 else { 282 MVT::ValueType VT1,VT2; 283 NumElements = 284 TLI.getPackedTypeBreakdown(cast<PackedType>(PN->getType()), 285 VT1, VT2); 286 } 287 unsigned PHIReg = ValueMap[PN]; 288 assert(PHIReg && "PHI node does not have an assigned virtual register!"); 289 const TargetInstrInfo *TII = TLI.getTargetMachine().getInstrInfo(); 290 for (unsigned i = 0; i != NumElements; ++i) 291 BuildMI(MBB, TII->get(TargetInstrInfo::PHI), PHIReg+i); 292 } 293 } 294} 295 296/// CreateRegForValue - Allocate the appropriate number of virtual registers of 297/// the correctly promoted or expanded types. Assign these registers 298/// consecutive vreg numbers and return the first assigned number. 299unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) { 300 MVT::ValueType VT = TLI.getValueType(V->getType()); 301 302 // The number of multiples of registers that we need, to, e.g., split up 303 // a <2 x int64> -> 4 x i32 registers. 304 unsigned NumVectorRegs = 1; 305 306 // If this is a packed type, figure out what type it will decompose into 307 // and how many of the elements it will use. 308 if (VT == MVT::Vector) { 309 const PackedType *PTy = cast<PackedType>(V->getType()); 310 unsigned NumElts = PTy->getNumElements(); 311 MVT::ValueType EltTy = TLI.getValueType(PTy->getElementType()); 312 313 // Divide the input until we get to a supported size. This will always 314 // end with a scalar if the target doesn't support vectors. 315 while (NumElts > 1 && !TLI.isTypeLegal(getVectorType(EltTy, NumElts))) { 316 NumElts >>= 1; 317 NumVectorRegs <<= 1; 318 } 319 if (NumElts == 1) 320 VT = EltTy; 321 else 322 VT = getVectorType(EltTy, NumElts); 323 } 324 325 // The common case is that we will only create one register for this 326 // value. If we have that case, create and return the virtual register. 327 unsigned NV = TLI.getNumElements(VT); 328 if (NV == 1) { 329 // If we are promoting this value, pick the next largest supported type. 330 MVT::ValueType PromotedType = TLI.getTypeToTransformTo(VT); 331 unsigned Reg = MakeReg(PromotedType); 332 // If this is a vector of supported or promoted types (e.g. 4 x i16), 333 // create all of the registers. 334 for (unsigned i = 1; i != NumVectorRegs; ++i) 335 MakeReg(PromotedType); 336 return Reg; 337 } 338 339 // If this value is represented with multiple target registers, make sure 340 // to create enough consecutive registers of the right (smaller) type. 341 VT = TLI.getTypeToExpandTo(VT); 342 unsigned R = MakeReg(VT); 343 for (unsigned i = 1; i != NV*NumVectorRegs; ++i) 344 MakeReg(VT); 345 return R; 346} 347 348//===----------------------------------------------------------------------===// 349/// SelectionDAGLowering - This is the common target-independent lowering 350/// implementation that is parameterized by a TargetLowering object. 351/// Also, targets can overload any lowering method. 352/// 353namespace llvm { 354class SelectionDAGLowering { 355 MachineBasicBlock *CurMBB; 356 357 std::map<const Value*, SDOperand> NodeMap; 358 359 /// PendingLoads - Loads are not emitted to the program immediately. We bunch 360 /// them up and then emit token factor nodes when possible. This allows us to 361 /// get simple disambiguation between loads without worrying about alias 362 /// analysis. 363 std::vector<SDOperand> PendingLoads; 364 365 /// Case - A pair of values to record the Value for a switch case, and the 366 /// case's target basic block. 367 typedef std::pair<Constant*, MachineBasicBlock*> Case; 368 typedef std::vector<Case>::iterator CaseItr; 369 typedef std::pair<CaseItr, CaseItr> CaseRange; 370 371 /// CaseRec - A struct with ctor used in lowering switches to a binary tree 372 /// of conditional branches. 373 struct CaseRec { 374 CaseRec(MachineBasicBlock *bb, Constant *lt, Constant *ge, CaseRange r) : 375 CaseBB(bb), LT(lt), GE(ge), Range(r) {} 376 377 /// CaseBB - The MBB in which to emit the compare and branch 378 MachineBasicBlock *CaseBB; 379 /// LT, GE - If nonzero, we know the current case value must be less-than or 380 /// greater-than-or-equal-to these Constants. 381 Constant *LT; 382 Constant *GE; 383 /// Range - A pair of iterators representing the range of case values to be 384 /// processed at this point in the binary search tree. 385 CaseRange Range; 386 }; 387 388 /// The comparison function for sorting Case values. 389 struct CaseCmp { 390 bool operator () (const Case& C1, const Case& C2) { 391 assert(isa<ConstantInt>(C1.first) && isa<ConstantInt>(C2.first)); 392 return cast<const ConstantInt>(C1.first)->getSExtValue() < 393 cast<const ConstantInt>(C2.first)->getSExtValue(); 394 } 395 }; 396 397public: 398 // TLI - This is information that describes the available target features we 399 // need for lowering. This indicates when operations are unavailable, 400 // implemented with a libcall, etc. 401 TargetLowering &TLI; 402 SelectionDAG &DAG; 403 const TargetData *TD; 404 405 /// SwitchCases - Vector of CaseBlock structures used to communicate 406 /// SwitchInst code generation information. 407 std::vector<SelectionDAGISel::CaseBlock> SwitchCases; 408 SelectionDAGISel::JumpTable JT; 409 410 /// FuncInfo - Information about the function as a whole. 411 /// 412 FunctionLoweringInfo &FuncInfo; 413 414 SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli, 415 FunctionLoweringInfo &funcinfo) 416 : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()), 417 JT(0,0,0,0), FuncInfo(funcinfo) { 418 } 419 420 /// getRoot - Return the current virtual root of the Selection DAG. 421 /// 422 SDOperand getRoot() { 423 if (PendingLoads.empty()) 424 return DAG.getRoot(); 425 426 if (PendingLoads.size() == 1) { 427 SDOperand Root = PendingLoads[0]; 428 DAG.setRoot(Root); 429 PendingLoads.clear(); 430 return Root; 431 } 432 433 // Otherwise, we have to make a token factor node. 434 SDOperand Root = DAG.getNode(ISD::TokenFactor, MVT::Other, 435 &PendingLoads[0], PendingLoads.size()); 436 PendingLoads.clear(); 437 DAG.setRoot(Root); 438 return Root; 439 } 440 441 SDOperand CopyValueToVirtualRegister(Value *V, unsigned Reg); 442 443 void visit(Instruction &I) { visit(I.getOpcode(), I); } 444 445 void visit(unsigned Opcode, User &I) { 446 // Note: this doesn't use InstVisitor, because it has to work with 447 // ConstantExpr's in addition to instructions. 448 switch (Opcode) { 449 default: assert(0 && "Unknown instruction type encountered!"); 450 abort(); 451 // Build the switch statement using the Instruction.def file. 452#define HANDLE_INST(NUM, OPCODE, CLASS) \ 453 case Instruction::OPCODE:return visit##OPCODE((CLASS&)I); 454#include "llvm/Instruction.def" 455 } 456 } 457 458 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; } 459 460 SDOperand getLoadFrom(const Type *Ty, SDOperand Ptr, 461 const Value *SV, SDOperand Root, 462 bool isVolatile); 463 464 SDOperand getIntPtrConstant(uint64_t Val) { 465 return DAG.getConstant(Val, TLI.getPointerTy()); 466 } 467 468 SDOperand getValue(const Value *V); 469 470 const SDOperand &setValue(const Value *V, SDOperand NewN) { 471 SDOperand &N = NodeMap[V]; 472 assert(N.Val == 0 && "Already set a value for this node!"); 473 return N = NewN; 474 } 475 476 RegsForValue GetRegistersForValue(const std::string &ConstrCode, 477 MVT::ValueType VT, 478 bool OutReg, bool InReg, 479 std::set<unsigned> &OutputRegs, 480 std::set<unsigned> &InputRegs); 481 482 void FindMergedConditions(Value *Cond, MachineBasicBlock *TBB, 483 MachineBasicBlock *FBB, MachineBasicBlock *CurBB, 484 unsigned Opc); 485 bool isExportableFromCurrentBlock(Value *V, const BasicBlock *FromBB); 486 void ExportFromCurrentBlock(Value *V); 487 488 // Terminator instructions. 489 void visitRet(ReturnInst &I); 490 void visitBr(BranchInst &I); 491 void visitSwitch(SwitchInst &I); 492 void visitUnreachable(UnreachableInst &I) { /* noop */ } 493 494 // Helper for visitSwitch 495 void visitSwitchCase(SelectionDAGISel::CaseBlock &CB); 496 void visitJumpTable(SelectionDAGISel::JumpTable &JT); 497 498 // These all get lowered before this pass. 499 void visitInvoke(InvokeInst &I) { assert(0 && "TODO"); } 500 void visitUnwind(UnwindInst &I) { assert(0 && "TODO"); } 501 502 void visitScalarBinary(User &I, unsigned OpCode); 503 void visitVectorBinary(User &I, unsigned OpCode); 504 void visitEitherBinary(User &I, unsigned ScalarOp, unsigned VectorOp); 505 void visitShift(User &I, unsigned Opcode); 506 void visitAdd(User &I) { 507 if (isa<PackedType>(I.getType())) 508 visitVectorBinary(I, ISD::VADD); 509 else if (I.getType()->isFloatingPoint()) 510 visitScalarBinary(I, ISD::FADD); 511 else 512 visitScalarBinary(I, ISD::ADD); 513 } 514 void visitSub(User &I); 515 void visitMul(User &I) { 516 if (isa<PackedType>(I.getType())) 517 visitVectorBinary(I, ISD::VMUL); 518 else if (I.getType()->isFloatingPoint()) 519 visitScalarBinary(I, ISD::FMUL); 520 else 521 visitScalarBinary(I, ISD::MUL); 522 } 523 void visitURem(User &I) { visitScalarBinary(I, ISD::UREM); } 524 void visitSRem(User &I) { visitScalarBinary(I, ISD::SREM); } 525 void visitFRem(User &I) { visitScalarBinary(I, ISD::FREM); } 526 void visitUDiv(User &I) { visitEitherBinary(I, ISD::UDIV, ISD::VUDIV); } 527 void visitSDiv(User &I) { visitEitherBinary(I, ISD::SDIV, ISD::VSDIV); } 528 void visitFDiv(User &I) { visitEitherBinary(I, ISD::FDIV, ISD::VSDIV); } 529 void visitAnd (User &I) { visitEitherBinary(I, ISD::AND, ISD::VAND ); } 530 void visitOr (User &I) { visitEitherBinary(I, ISD::OR, ISD::VOR ); } 531 void visitXor (User &I) { visitEitherBinary(I, ISD::XOR, ISD::VXOR ); } 532 void visitShl (User &I) { visitShift(I, ISD::SHL); } 533 void visitLShr(User &I) { visitShift(I, ISD::SRL); } 534 void visitAShr(User &I) { visitShift(I, ISD::SRA); } 535 void visitICmp(User &I); 536 void visitFCmp(User &I); 537 // Visit the conversion instructions 538 void visitTrunc(User &I); 539 void visitZExt(User &I); 540 void visitSExt(User &I); 541 void visitFPTrunc(User &I); 542 void visitFPExt(User &I); 543 void visitFPToUI(User &I); 544 void visitFPToSI(User &I); 545 void visitUIToFP(User &I); 546 void visitSIToFP(User &I); 547 void visitPtrToInt(User &I); 548 void visitIntToPtr(User &I); 549 void visitBitCast(User &I); 550 551 void visitExtractElement(User &I); 552 void visitInsertElement(User &I); 553 void visitShuffleVector(User &I); 554 555 void visitGetElementPtr(User &I); 556 void visitSelect(User &I); 557 558 void visitMalloc(MallocInst &I); 559 void visitFree(FreeInst &I); 560 void visitAlloca(AllocaInst &I); 561 void visitLoad(LoadInst &I); 562 void visitStore(StoreInst &I); 563 void visitPHI(PHINode &I) { } // PHI nodes are handled specially. 564 void visitCall(CallInst &I); 565 void visitInlineAsm(CallInst &I); 566 const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic); 567 void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic); 568 569 void visitVAStart(CallInst &I); 570 void visitVAArg(VAArgInst &I); 571 void visitVAEnd(CallInst &I); 572 void visitVACopy(CallInst &I); 573 574 void visitMemIntrinsic(CallInst &I, unsigned Op); 575 576 void visitUserOp1(Instruction &I) { 577 assert(0 && "UserOp1 should not exist at instruction selection time!"); 578 abort(); 579 } 580 void visitUserOp2(Instruction &I) { 581 assert(0 && "UserOp2 should not exist at instruction selection time!"); 582 abort(); 583 } 584}; 585} // end namespace llvm 586 587SDOperand SelectionDAGLowering::getValue(const Value *V) { 588 SDOperand &N = NodeMap[V]; 589 if (N.Val) return N; 590 591 const Type *VTy = V->getType(); 592 MVT::ValueType VT = TLI.getValueType(VTy); 593 if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) { 594 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 595 visit(CE->getOpcode(), *CE); 596 assert(N.Val && "visit didn't populate the ValueMap!"); 597 return N; 598 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) { 599 return N = DAG.getGlobalAddress(GV, VT); 600 } else if (isa<ConstantPointerNull>(C)) { 601 return N = DAG.getConstant(0, TLI.getPointerTy()); 602 } else if (isa<UndefValue>(C)) { 603 if (!isa<PackedType>(VTy)) 604 return N = DAG.getNode(ISD::UNDEF, VT); 605 606 // Create a VBUILD_VECTOR of undef nodes. 607 const PackedType *PTy = cast<PackedType>(VTy); 608 unsigned NumElements = PTy->getNumElements(); 609 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType()); 610 611 SmallVector<SDOperand, 8> Ops; 612 Ops.assign(NumElements, DAG.getNode(ISD::UNDEF, PVT)); 613 614 // Create a VConstant node with generic Vector type. 615 Ops.push_back(DAG.getConstant(NumElements, MVT::i32)); 616 Ops.push_back(DAG.getValueType(PVT)); 617 return N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, 618 &Ops[0], Ops.size()); 619 } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) { 620 return N = DAG.getConstantFP(CFP->getValue(), VT); 621 } else if (const PackedType *PTy = dyn_cast<PackedType>(VTy)) { 622 unsigned NumElements = PTy->getNumElements(); 623 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType()); 624 625 // Now that we know the number and type of the elements, push a 626 // Constant or ConstantFP node onto the ops list for each element of 627 // the packed constant. 628 SmallVector<SDOperand, 8> Ops; 629 if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C)) { 630 for (unsigned i = 0; i != NumElements; ++i) 631 Ops.push_back(getValue(CP->getOperand(i))); 632 } else { 633 assert(isa<ConstantAggregateZero>(C) && "Unknown packed constant!"); 634 SDOperand Op; 635 if (MVT::isFloatingPoint(PVT)) 636 Op = DAG.getConstantFP(0, PVT); 637 else 638 Op = DAG.getConstant(0, PVT); 639 Ops.assign(NumElements, Op); 640 } 641 642 // Create a VBUILD_VECTOR node with generic Vector type. 643 Ops.push_back(DAG.getConstant(NumElements, MVT::i32)); 644 Ops.push_back(DAG.getValueType(PVT)); 645 return N = DAG.getNode(ISD::VBUILD_VECTOR,MVT::Vector,&Ops[0],Ops.size()); 646 } else { 647 // Canonicalize all constant ints to be unsigned. 648 return N = DAG.getConstant(cast<ConstantInt>(C)->getZExtValue(),VT); 649 } 650 } 651 652 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 653 std::map<const AllocaInst*, int>::iterator SI = 654 FuncInfo.StaticAllocaMap.find(AI); 655 if (SI != FuncInfo.StaticAllocaMap.end()) 656 return DAG.getFrameIndex(SI->second, TLI.getPointerTy()); 657 } 658 659 std::map<const Value*, unsigned>::const_iterator VMI = 660 FuncInfo.ValueMap.find(V); 661 assert(VMI != FuncInfo.ValueMap.end() && "Value not in map!"); 662 663 unsigned InReg = VMI->second; 664 665 // If this type is not legal, make it so now. 666 if (VT != MVT::Vector) { 667 if (TLI.getTypeAction(VT) == TargetLowering::Expand) { 668 // Source must be expanded. This input value is actually coming from the 669 // register pair VMI->second and VMI->second+1. 670 MVT::ValueType DestVT = TLI.getTypeToExpandTo(VT); 671 unsigned NumVals = TLI.getNumElements(VT); 672 N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT); 673 if (NumVals == 1) 674 N = DAG.getNode(ISD::BIT_CONVERT, VT, N); 675 else { 676 assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!"); 677 N = DAG.getNode(ISD::BUILD_PAIR, VT, N, 678 DAG.getCopyFromReg(DAG.getEntryNode(), InReg+1, DestVT)); 679 } 680 } else { 681 MVT::ValueType DestVT = TLI.getTypeToTransformTo(VT); 682 N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT); 683 if (TLI.getTypeAction(VT) == TargetLowering::Promote) // Promotion case 684 N = MVT::isFloatingPoint(VT) 685 ? DAG.getNode(ISD::FP_ROUND, VT, N) 686 : DAG.getNode(ISD::TRUNCATE, VT, N); 687 } 688 } else { 689 // Otherwise, if this is a vector, make it available as a generic vector 690 // here. 691 MVT::ValueType PTyElementVT, PTyLegalElementVT; 692 const PackedType *PTy = cast<PackedType>(VTy); 693 unsigned NE = TLI.getPackedTypeBreakdown(PTy, PTyElementVT, 694 PTyLegalElementVT); 695 696 // Build a VBUILD_VECTOR with the input registers. 697 SmallVector<SDOperand, 8> Ops; 698 if (PTyElementVT == PTyLegalElementVT) { 699 // If the value types are legal, just VBUILD the CopyFromReg nodes. 700 for (unsigned i = 0; i != NE; ++i) 701 Ops.push_back(DAG.getCopyFromReg(DAG.getEntryNode(), InReg++, 702 PTyElementVT)); 703 } else if (PTyElementVT < PTyLegalElementVT) { 704 // If the register was promoted, use TRUNCATE of FP_ROUND as appropriate. 705 for (unsigned i = 0; i != NE; ++i) { 706 SDOperand Op = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++, 707 PTyElementVT); 708 if (MVT::isFloatingPoint(PTyElementVT)) 709 Op = DAG.getNode(ISD::FP_ROUND, PTyElementVT, Op); 710 else 711 Op = DAG.getNode(ISD::TRUNCATE, PTyElementVT, Op); 712 Ops.push_back(Op); 713 } 714 } else { 715 // If the register was expanded, use BUILD_PAIR. 716 assert((NE & 1) == 0 && "Must expand into a multiple of 2 elements!"); 717 for (unsigned i = 0; i != NE/2; ++i) { 718 SDOperand Op0 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++, 719 PTyElementVT); 720 SDOperand Op1 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++, 721 PTyElementVT); 722 Ops.push_back(DAG.getNode(ISD::BUILD_PAIR, VT, Op0, Op1)); 723 } 724 } 725 726 Ops.push_back(DAG.getConstant(NE, MVT::i32)); 727 Ops.push_back(DAG.getValueType(PTyLegalElementVT)); 728 N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, &Ops[0], Ops.size()); 729 730 // Finally, use a VBIT_CONVERT to make this available as the appropriate 731 // vector type. 732 N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N, 733 DAG.getConstant(PTy->getNumElements(), 734 MVT::i32), 735 DAG.getValueType(TLI.getValueType(PTy->getElementType()))); 736 } 737 738 return N; 739} 740 741 742void SelectionDAGLowering::visitRet(ReturnInst &I) { 743 if (I.getNumOperands() == 0) { 744 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getRoot())); 745 return; 746 } 747 SmallVector<SDOperand, 8> NewValues; 748 NewValues.push_back(getRoot()); 749 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 750 SDOperand RetOp = getValue(I.getOperand(i)); 751 752 // If this is an integer return value, we need to promote it ourselves to 753 // the full width of a register, since LegalizeOp will use ANY_EXTEND rather 754 // than sign/zero. 755 // FIXME: C calling convention requires the return type to be promoted to 756 // at least 32-bit. But this is not necessary for non-C calling conventions. 757 if (MVT::isInteger(RetOp.getValueType()) && 758 RetOp.getValueType() < MVT::i64) { 759 MVT::ValueType TmpVT; 760 if (TLI.getTypeAction(MVT::i32) == TargetLowering::Promote) 761 TmpVT = TLI.getTypeToTransformTo(MVT::i32); 762 else 763 TmpVT = MVT::i32; 764 const FunctionType *FTy = I.getParent()->getParent()->getFunctionType(); 765 ISD::NodeType ExtendKind = ISD::ANY_EXTEND; 766 if (FTy->paramHasAttr(0, FunctionType::SExtAttribute)) 767 ExtendKind = ISD::SIGN_EXTEND; 768 if (FTy->paramHasAttr(0, FunctionType::ZExtAttribute)) 769 ExtendKind = ISD::ZERO_EXTEND; 770 RetOp = DAG.getNode(ExtendKind, TmpVT, RetOp); 771 } 772 NewValues.push_back(RetOp); 773 NewValues.push_back(DAG.getConstant(false, MVT::i32)); 774 } 775 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, 776 &NewValues[0], NewValues.size())); 777} 778 779/// ExportFromCurrentBlock - If this condition isn't known to be exported from 780/// the current basic block, add it to ValueMap now so that we'll get a 781/// CopyTo/FromReg. 782void SelectionDAGLowering::ExportFromCurrentBlock(Value *V) { 783 // No need to export constants. 784 if (!isa<Instruction>(V) && !isa<Argument>(V)) return; 785 786 // Already exported? 787 if (FuncInfo.isExportedInst(V)) return; 788 789 unsigned Reg = FuncInfo.InitializeRegForValue(V); 790 PendingLoads.push_back(CopyValueToVirtualRegister(V, Reg)); 791} 792 793bool SelectionDAGLowering::isExportableFromCurrentBlock(Value *V, 794 const BasicBlock *FromBB) { 795 // The operands of the setcc have to be in this block. We don't know 796 // how to export them from some other block. 797 if (Instruction *VI = dyn_cast<Instruction>(V)) { 798 // Can export from current BB. 799 if (VI->getParent() == FromBB) 800 return true; 801 802 // Is already exported, noop. 803 return FuncInfo.isExportedInst(V); 804 } 805 806 // If this is an argument, we can export it if the BB is the entry block or 807 // if it is already exported. 808 if (isa<Argument>(V)) { 809 if (FromBB == &FromBB->getParent()->getEntryBlock()) 810 return true; 811 812 // Otherwise, can only export this if it is already exported. 813 return FuncInfo.isExportedInst(V); 814 } 815 816 // Otherwise, constants can always be exported. 817 return true; 818} 819 820static bool InBlock(const Value *V, const BasicBlock *BB) { 821 if (const Instruction *I = dyn_cast<Instruction>(V)) 822 return I->getParent() == BB; 823 return true; 824} 825 826/// FindMergedConditions - If Cond is an expression like 827void SelectionDAGLowering::FindMergedConditions(Value *Cond, 828 MachineBasicBlock *TBB, 829 MachineBasicBlock *FBB, 830 MachineBasicBlock *CurBB, 831 unsigned Opc) { 832 // If this node is not part of the or/and tree, emit it as a branch. 833 Instruction *BOp = dyn_cast<Instruction>(Cond); 834 835 if (!BOp || !(isa<BinaryOperator>(BOp) || isa<CmpInst>(BOp)) || 836 (unsigned)BOp->getOpcode() != Opc || !BOp->hasOneUse() || 837 BOp->getParent() != CurBB->getBasicBlock() || 838 !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) || 839 !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) { 840 const BasicBlock *BB = CurBB->getBasicBlock(); 841 842 // If the leaf of the tree is a comparison, merge the condition into 843 // the caseblock. 844 if ((isa<ICmpInst>(Cond) || isa<FCmpInst>(Cond)) && 845 // The operands of the cmp have to be in this block. We don't know 846 // how to export them from some other block. If this is the first block 847 // of the sequence, no exporting is needed. 848 (CurBB == CurMBB || 849 (isExportableFromCurrentBlock(BOp->getOperand(0), BB) && 850 isExportableFromCurrentBlock(BOp->getOperand(1), BB)))) { 851 BOp = cast<Instruction>(Cond); 852 ISD::CondCode Condition; 853 if (ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) { 854 switch (IC->getPredicate()) { 855 default: assert(0 && "Unknown icmp predicate opcode!"); 856 case ICmpInst::ICMP_EQ: Condition = ISD::SETEQ; break; 857 case ICmpInst::ICMP_NE: Condition = ISD::SETNE; break; 858 case ICmpInst::ICMP_SLE: Condition = ISD::SETLE; break; 859 case ICmpInst::ICMP_ULE: Condition = ISD::SETULE; break; 860 case ICmpInst::ICMP_SGE: Condition = ISD::SETGE; break; 861 case ICmpInst::ICMP_UGE: Condition = ISD::SETUGE; break; 862 case ICmpInst::ICMP_SLT: Condition = ISD::SETLT; break; 863 case ICmpInst::ICMP_ULT: Condition = ISD::SETULT; break; 864 case ICmpInst::ICMP_SGT: Condition = ISD::SETGT; break; 865 case ICmpInst::ICMP_UGT: Condition = ISD::SETUGT; break; 866 } 867 } else if (FCmpInst *FC = dyn_cast<FCmpInst>(Cond)) { 868 ISD::CondCode FPC, FOC; 869 switch (FC->getPredicate()) { 870 default: assert(0 && "Unknown fcmp predicate opcode!"); 871 case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break; 872 case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break; 873 case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break; 874 case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break; 875 case FCmpInst::FCMP_OLT: FOC = ISD::SETLT; FPC = ISD::SETOLT; break; 876 case FCmpInst::FCMP_OLE: FOC = ISD::SETLE; FPC = ISD::SETOLE; break; 877 case FCmpInst::FCMP_ONE: FOC = ISD::SETNE; FPC = ISD::SETONE; break; 878 case FCmpInst::FCMP_ORD: FOC = ISD::SETEQ; FPC = ISD::SETO; break; 879 case FCmpInst::FCMP_UNO: FOC = ISD::SETNE; FPC = ISD::SETUO; break; 880 case FCmpInst::FCMP_UEQ: FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break; 881 case FCmpInst::FCMP_UGT: FOC = ISD::SETGT; FPC = ISD::SETUGT; break; 882 case FCmpInst::FCMP_UGE: FOC = ISD::SETGE; FPC = ISD::SETUGE; break; 883 case FCmpInst::FCMP_ULT: FOC = ISD::SETLT; FPC = ISD::SETULT; break; 884 case FCmpInst::FCMP_ULE: FOC = ISD::SETLE; FPC = ISD::SETULE; break; 885 case FCmpInst::FCMP_UNE: FOC = ISD::SETNE; FPC = ISD::SETUNE; break; 886 case FCmpInst::FCMP_TRUE: FOC = FPC = ISD::SETTRUE; break; 887 } 888 if (FiniteOnlyFPMath()) 889 Condition = FOC; 890 else 891 Condition = FPC; 892 } else { 893 assert(0 && "Unknown compare instruction"); 894 } 895 896 SelectionDAGISel::CaseBlock CB(Condition, BOp->getOperand(0), 897 BOp->getOperand(1), TBB, FBB, CurBB); 898 SwitchCases.push_back(CB); 899 return; 900 } 901 902 // Create a CaseBlock record representing this branch. 903 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(), 904 TBB, FBB, CurBB); 905 SwitchCases.push_back(CB); 906 return; 907 } 908 909 910 // Create TmpBB after CurBB. 911 MachineFunction::iterator BBI = CurBB; 912 MachineBasicBlock *TmpBB = new MachineBasicBlock(CurBB->getBasicBlock()); 913 CurBB->getParent()->getBasicBlockList().insert(++BBI, TmpBB); 914 915 if (Opc == Instruction::Or) { 916 // Codegen X | Y as: 917 // jmp_if_X TBB 918 // jmp TmpBB 919 // TmpBB: 920 // jmp_if_Y TBB 921 // jmp FBB 922 // 923 924 // Emit the LHS condition. 925 FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, Opc); 926 927 // Emit the RHS condition into TmpBB. 928 FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc); 929 } else { 930 assert(Opc == Instruction::And && "Unknown merge op!"); 931 // Codegen X & Y as: 932 // jmp_if_X TmpBB 933 // jmp FBB 934 // TmpBB: 935 // jmp_if_Y TBB 936 // jmp FBB 937 // 938 // This requires creation of TmpBB after CurBB. 939 940 // Emit the LHS condition. 941 FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, Opc); 942 943 // Emit the RHS condition into TmpBB. 944 FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc); 945 } 946} 947 948/// If the set of cases should be emitted as a series of branches, return true. 949/// If we should emit this as a bunch of and/or'd together conditions, return 950/// false. 951static bool 952ShouldEmitAsBranches(const std::vector<SelectionDAGISel::CaseBlock> &Cases) { 953 if (Cases.size() != 2) return true; 954 955 // If this is two comparisons of the same values or'd or and'd together, they 956 // will get folded into a single comparison, so don't emit two blocks. 957 if ((Cases[0].CmpLHS == Cases[1].CmpLHS && 958 Cases[0].CmpRHS == Cases[1].CmpRHS) || 959 (Cases[0].CmpRHS == Cases[1].CmpLHS && 960 Cases[0].CmpLHS == Cases[1].CmpRHS)) { 961 return false; 962 } 963 964 return true; 965} 966 967void SelectionDAGLowering::visitBr(BranchInst &I) { 968 // Update machine-CFG edges. 969 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)]; 970 971 // Figure out which block is immediately after the current one. 972 MachineBasicBlock *NextBlock = 0; 973 MachineFunction::iterator BBI = CurMBB; 974 if (++BBI != CurMBB->getParent()->end()) 975 NextBlock = BBI; 976 977 if (I.isUnconditional()) { 978 // If this is not a fall-through branch, emit the branch. 979 if (Succ0MBB != NextBlock) 980 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(), 981 DAG.getBasicBlock(Succ0MBB))); 982 983 // Update machine-CFG edges. 984 CurMBB->addSuccessor(Succ0MBB); 985 986 return; 987 } 988 989 // If this condition is one of the special cases we handle, do special stuff 990 // now. 991 Value *CondVal = I.getCondition(); 992 MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)]; 993 994 // If this is a series of conditions that are or'd or and'd together, emit 995 // this as a sequence of branches instead of setcc's with and/or operations. 996 // For example, instead of something like: 997 // cmp A, B 998 // C = seteq 999 // cmp D, E 1000 // F = setle 1001 // or C, F 1002 // jnz foo 1003 // Emit: 1004 // cmp A, B 1005 // je foo 1006 // cmp D, E 1007 // jle foo 1008 // 1009 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(CondVal)) { 1010 if (BOp->hasOneUse() && 1011 (BOp->getOpcode() == Instruction::And || 1012 BOp->getOpcode() == Instruction::Or)) { 1013 FindMergedConditions(BOp, Succ0MBB, Succ1MBB, CurMBB, BOp->getOpcode()); 1014 // If the compares in later blocks need to use values not currently 1015 // exported from this block, export them now. This block should always 1016 // be the first entry. 1017 assert(SwitchCases[0].ThisBB == CurMBB && "Unexpected lowering!"); 1018 1019 // Allow some cases to be rejected. 1020 if (ShouldEmitAsBranches(SwitchCases)) { 1021 for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) { 1022 ExportFromCurrentBlock(SwitchCases[i].CmpLHS); 1023 ExportFromCurrentBlock(SwitchCases[i].CmpRHS); 1024 } 1025 1026 // Emit the branch for this block. 1027 visitSwitchCase(SwitchCases[0]); 1028 SwitchCases.erase(SwitchCases.begin()); 1029 return; 1030 } 1031 1032 // Okay, we decided not to do this, remove any inserted MBB's and clear 1033 // SwitchCases. 1034 for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) 1035 CurMBB->getParent()->getBasicBlockList().erase(SwitchCases[i].ThisBB); 1036 1037 SwitchCases.clear(); 1038 } 1039 } 1040 1041 // Create a CaseBlock record representing this branch. 1042 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, CondVal, ConstantInt::getTrue(), 1043 Succ0MBB, Succ1MBB, CurMBB); 1044 // Use visitSwitchCase to actually insert the fast branch sequence for this 1045 // cond branch. 1046 visitSwitchCase(CB); 1047} 1048 1049/// visitSwitchCase - Emits the necessary code to represent a single node in 1050/// the binary search tree resulting from lowering a switch instruction. 1051void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) { 1052 SDOperand Cond; 1053 SDOperand CondLHS = getValue(CB.CmpLHS); 1054 1055 // Build the setcc now, fold "(X == true)" to X and "(X == false)" to !X to 1056 // handle common cases produced by branch lowering. 1057 if (CB.CmpRHS == ConstantInt::getTrue() && CB.CC == ISD::SETEQ) 1058 Cond = CondLHS; 1059 else if (CB.CmpRHS == ConstantInt::getFalse() && CB.CC == ISD::SETEQ) { 1060 SDOperand True = DAG.getConstant(1, CondLHS.getValueType()); 1061 Cond = DAG.getNode(ISD::XOR, CondLHS.getValueType(), CondLHS, True); 1062 } else 1063 Cond = DAG.getSetCC(MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC); 1064 1065 // Set NextBlock to be the MBB immediately after the current one, if any. 1066 // This is used to avoid emitting unnecessary branches to the next block. 1067 MachineBasicBlock *NextBlock = 0; 1068 MachineFunction::iterator BBI = CurMBB; 1069 if (++BBI != CurMBB->getParent()->end()) 1070 NextBlock = BBI; 1071 1072 // If the lhs block is the next block, invert the condition so that we can 1073 // fall through to the lhs instead of the rhs block. 1074 if (CB.TrueBB == NextBlock) { 1075 std::swap(CB.TrueBB, CB.FalseBB); 1076 SDOperand True = DAG.getConstant(1, Cond.getValueType()); 1077 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True); 1078 } 1079 SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), Cond, 1080 DAG.getBasicBlock(CB.TrueBB)); 1081 if (CB.FalseBB == NextBlock) 1082 DAG.setRoot(BrCond); 1083 else 1084 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond, 1085 DAG.getBasicBlock(CB.FalseBB))); 1086 // Update successor info 1087 CurMBB->addSuccessor(CB.TrueBB); 1088 CurMBB->addSuccessor(CB.FalseBB); 1089} 1090 1091void SelectionDAGLowering::visitJumpTable(SelectionDAGISel::JumpTable &JT) { 1092 // Emit the code for the jump table 1093 MVT::ValueType PTy = TLI.getPointerTy(); 1094 SDOperand Index = DAG.getCopyFromReg(getRoot(), JT.Reg, PTy); 1095 SDOperand Table = DAG.getJumpTable(JT.JTI, PTy); 1096 DAG.setRoot(DAG.getNode(ISD::BR_JT, MVT::Other, Index.getValue(1), 1097 Table, Index)); 1098 return; 1099} 1100 1101void SelectionDAGLowering::visitSwitch(SwitchInst &I) { 1102 // Figure out which block is immediately after the current one. 1103 MachineBasicBlock *NextBlock = 0; 1104 MachineFunction::iterator BBI = CurMBB; 1105 1106 if (++BBI != CurMBB->getParent()->end()) 1107 NextBlock = BBI; 1108 1109 MachineBasicBlock *Default = FuncInfo.MBBMap[I.getDefaultDest()]; 1110 1111 // If there is only the default destination, branch to it if it is not the 1112 // next basic block. Otherwise, just fall through. 1113 if (I.getNumOperands() == 2) { 1114 // Update machine-CFG edges. 1115 1116 // If this is not a fall-through branch, emit the branch. 1117 if (Default != NextBlock) 1118 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(), 1119 DAG.getBasicBlock(Default))); 1120 1121 CurMBB->addSuccessor(Default); 1122 return; 1123 } 1124 1125 // If there are any non-default case statements, create a vector of Cases 1126 // representing each one, and sort the vector so that we can efficiently 1127 // create a binary search tree from them. 1128 std::vector<Case> Cases; 1129 1130 for (unsigned i = 1; i < I.getNumSuccessors(); ++i) { 1131 MachineBasicBlock *SMBB = FuncInfo.MBBMap[I.getSuccessor(i)]; 1132 Cases.push_back(Case(I.getSuccessorValue(i), SMBB)); 1133 } 1134 1135 std::sort(Cases.begin(), Cases.end(), CaseCmp()); 1136 1137 // Get the Value to be switched on and default basic blocks, which will be 1138 // inserted into CaseBlock records, representing basic blocks in the binary 1139 // search tree. 1140 Value *SV = I.getOperand(0); 1141 1142 // Get the MachineFunction which holds the current MBB. This is used during 1143 // emission of jump tables, and when inserting any additional MBBs necessary 1144 // to represent the switch. 1145 MachineFunction *CurMF = CurMBB->getParent(); 1146 const BasicBlock *LLVMBB = CurMBB->getBasicBlock(); 1147 1148 // If the switch has few cases (two or less) emit a series of specific 1149 // tests. 1150 if (Cases.size() < 3) { 1151 // TODO: If any two of the cases has the same destination, and if one value 1152 // is the same as the other, but has one bit unset that the other has set, 1153 // use bit manipulation to do two compares at once. For example: 1154 // "if (X == 6 || X == 4)" -> "if ((X|2) == 6)" 1155 1156 // Rearrange the case blocks so that the last one falls through if possible. 1157 if (NextBlock && Default != NextBlock && Cases.back().second != NextBlock) { 1158 // The last case block won't fall through into 'NextBlock' if we emit the 1159 // branches in this order. See if rearranging a case value would help. 1160 for (unsigned i = 0, e = Cases.size()-1; i != e; ++i) { 1161 if (Cases[i].second == NextBlock) { 1162 std::swap(Cases[i], Cases.back()); 1163 break; 1164 } 1165 } 1166 } 1167 1168 // Create a CaseBlock record representing a conditional branch to 1169 // the Case's target mbb if the value being switched on SV is equal 1170 // to C. 1171 MachineBasicBlock *CurBlock = CurMBB; 1172 for (unsigned i = 0, e = Cases.size(); i != e; ++i) { 1173 MachineBasicBlock *FallThrough; 1174 if (i != e-1) { 1175 FallThrough = new MachineBasicBlock(CurMBB->getBasicBlock()); 1176 CurMF->getBasicBlockList().insert(BBI, FallThrough); 1177 } else { 1178 // If the last case doesn't match, go to the default block. 1179 FallThrough = Default; 1180 } 1181 1182 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, SV, Cases[i].first, 1183 Cases[i].second, FallThrough, CurBlock); 1184 1185 // If emitting the first comparison, just call visitSwitchCase to emit the 1186 // code into the current block. Otherwise, push the CaseBlock onto the 1187 // vector to be later processed by SDISel, and insert the node's MBB 1188 // before the next MBB. 1189 if (CurBlock == CurMBB) 1190 visitSwitchCase(CB); 1191 else 1192 SwitchCases.push_back(CB); 1193 1194 CurBlock = FallThrough; 1195 } 1196 return; 1197 } 1198 1199 // If the switch has more than 5 blocks, and at least 31.25% dense, and the 1200 // target supports indirect branches, then emit a jump table rather than 1201 // lowering the switch to a binary tree of conditional branches. 1202 if ((TLI.isOperationLegal(ISD::BR_JT, MVT::Other) || 1203 TLI.isOperationLegal(ISD::BRIND, MVT::Other)) && 1204 Cases.size() > 5) { 1205 uint64_t First =cast<ConstantInt>(Cases.front().first)->getZExtValue(); 1206 uint64_t Last = cast<ConstantInt>(Cases.back().first)->getZExtValue(); 1207 double Density = (double)Cases.size() / (double)((Last - First) + 1ULL); 1208 1209 if (Density >= 0.3125) { 1210 // Create a new basic block to hold the code for loading the address 1211 // of the jump table, and jumping to it. Update successor information; 1212 // we will either branch to the default case for the switch, or the jump 1213 // table. 1214 MachineBasicBlock *JumpTableBB = new MachineBasicBlock(LLVMBB); 1215 CurMF->getBasicBlockList().insert(BBI, JumpTableBB); 1216 CurMBB->addSuccessor(Default); 1217 CurMBB->addSuccessor(JumpTableBB); 1218 1219 // Subtract the lowest switch case value from the value being switched on 1220 // and conditional branch to default mbb if the result is greater than the 1221 // difference between smallest and largest cases. 1222 SDOperand SwitchOp = getValue(SV); 1223 MVT::ValueType VT = SwitchOp.getValueType(); 1224 SDOperand SUB = DAG.getNode(ISD::SUB, VT, SwitchOp, 1225 DAG.getConstant(First, VT)); 1226 1227 // The SDNode we just created, which holds the value being switched on 1228 // minus the the smallest case value, needs to be copied to a virtual 1229 // register so it can be used as an index into the jump table in a 1230 // subsequent basic block. This value may be smaller or larger than the 1231 // target's pointer type, and therefore require extension or truncating. 1232 if (VT > TLI.getPointerTy()) 1233 SwitchOp = DAG.getNode(ISD::TRUNCATE, TLI.getPointerTy(), SUB); 1234 else 1235 SwitchOp = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), SUB); 1236 1237 unsigned JumpTableReg = FuncInfo.MakeReg(TLI.getPointerTy()); 1238 SDOperand CopyTo = DAG.getCopyToReg(getRoot(), JumpTableReg, SwitchOp); 1239 1240 // Emit the range check for the jump table, and branch to the default 1241 // block for the switch statement if the value being switched on exceeds 1242 // the largest case in the switch. 1243 SDOperand CMP = DAG.getSetCC(TLI.getSetCCResultTy(), SUB, 1244 DAG.getConstant(Last-First,VT), ISD::SETUGT); 1245 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, CopyTo, CMP, 1246 DAG.getBasicBlock(Default))); 1247 1248 // Build a vector of destination BBs, corresponding to each target 1249 // of the jump table. If the value of the jump table slot corresponds to 1250 // a case statement, push the case's BB onto the vector, otherwise, push 1251 // the default BB. 1252 std::vector<MachineBasicBlock*> DestBBs; 1253 uint64_t TEI = First; 1254 for (CaseItr ii = Cases.begin(), ee = Cases.end(); ii != ee; ++TEI) 1255 if (cast<ConstantInt>(ii->first)->getZExtValue() == TEI) { 1256 DestBBs.push_back(ii->second); 1257 ++ii; 1258 } else { 1259 DestBBs.push_back(Default); 1260 } 1261 1262 // Update successor info. Add one edge to each unique successor. 1263 // Vector bool would be better, but vector<bool> is really slow. 1264 std::vector<unsigned char> SuccsHandled; 1265 SuccsHandled.resize(CurMBB->getParent()->getNumBlockIDs()); 1266 1267 for (std::vector<MachineBasicBlock*>::iterator I = DestBBs.begin(), 1268 E = DestBBs.end(); I != E; ++I) { 1269 if (!SuccsHandled[(*I)->getNumber()]) { 1270 SuccsHandled[(*I)->getNumber()] = true; 1271 JumpTableBB->addSuccessor(*I); 1272 } 1273 } 1274 1275 // Create a jump table index for this jump table, or return an existing 1276 // one. 1277 unsigned JTI = CurMF->getJumpTableInfo()->getJumpTableIndex(DestBBs); 1278 1279 // Set the jump table information so that we can codegen it as a second 1280 // MachineBasicBlock 1281 JT.Reg = JumpTableReg; 1282 JT.JTI = JTI; 1283 JT.MBB = JumpTableBB; 1284 JT.Default = Default; 1285 return; 1286 } 1287 } 1288 1289 // Push the initial CaseRec onto the worklist 1290 std::vector<CaseRec> CaseVec; 1291 CaseVec.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end()))); 1292 1293 while (!CaseVec.empty()) { 1294 // Grab a record representing a case range to process off the worklist 1295 CaseRec CR = CaseVec.back(); 1296 CaseVec.pop_back(); 1297 1298 // Size is the number of Cases represented by this range. If Size is 1, 1299 // then we are processing a leaf of the binary search tree. Otherwise, 1300 // we need to pick a pivot, and push left and right ranges onto the 1301 // worklist. 1302 unsigned Size = CR.Range.second - CR.Range.first; 1303 1304 if (Size == 1) { 1305 // Create a CaseBlock record representing a conditional branch to 1306 // the Case's target mbb if the value being switched on SV is equal 1307 // to C. Otherwise, branch to default. 1308 Constant *C = CR.Range.first->first; 1309 MachineBasicBlock *Target = CR.Range.first->second; 1310 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, SV, C, Target, Default, 1311 CR.CaseBB); 1312 1313 // If the MBB representing the leaf node is the current MBB, then just 1314 // call visitSwitchCase to emit the code into the current block. 1315 // Otherwise, push the CaseBlock onto the vector to be later processed 1316 // by SDISel, and insert the node's MBB before the next MBB. 1317 if (CR.CaseBB == CurMBB) 1318 visitSwitchCase(CB); 1319 else 1320 SwitchCases.push_back(CB); 1321 } else { 1322 // split case range at pivot 1323 CaseItr Pivot = CR.Range.first + (Size / 2); 1324 CaseRange LHSR(CR.Range.first, Pivot); 1325 CaseRange RHSR(Pivot, CR.Range.second); 1326 Constant *C = Pivot->first; 1327 MachineBasicBlock *FalseBB = 0, *TrueBB = 0; 1328 1329 // We know that we branch to the LHS if the Value being switched on is 1330 // less than the Pivot value, C. We use this to optimize our binary 1331 // tree a bit, by recognizing that if SV is greater than or equal to the 1332 // LHS's Case Value, and that Case Value is exactly one less than the 1333 // Pivot's Value, then we can branch directly to the LHS's Target, 1334 // rather than creating a leaf node for it. 1335 if ((LHSR.second - LHSR.first) == 1 && 1336 LHSR.first->first == CR.GE && 1337 cast<ConstantInt>(C)->getZExtValue() == 1338 (cast<ConstantInt>(CR.GE)->getZExtValue() + 1ULL)) { 1339 TrueBB = LHSR.first->second; 1340 } else { 1341 TrueBB = new MachineBasicBlock(LLVMBB); 1342 CurMF->getBasicBlockList().insert(BBI, TrueBB); 1343 CaseVec.push_back(CaseRec(TrueBB, C, CR.GE, LHSR)); 1344 } 1345 1346 // Similar to the optimization above, if the Value being switched on is 1347 // known to be less than the Constant CR.LT, and the current Case Value 1348 // is CR.LT - 1, then we can branch directly to the target block for 1349 // the current Case Value, rather than emitting a RHS leaf node for it. 1350 if ((RHSR.second - RHSR.first) == 1 && CR.LT && 1351 cast<ConstantInt>(RHSR.first->first)->getZExtValue() == 1352 (cast<ConstantInt>(CR.LT)->getZExtValue() - 1ULL)) { 1353 FalseBB = RHSR.first->second; 1354 } else { 1355 FalseBB = new MachineBasicBlock(LLVMBB); 1356 CurMF->getBasicBlockList().insert(BBI, FalseBB); 1357 CaseVec.push_back(CaseRec(FalseBB,CR.LT,C,RHSR)); 1358 } 1359 1360 // Create a CaseBlock record representing a conditional branch to 1361 // the LHS node if the value being switched on SV is less than C. 1362 // Otherwise, branch to LHS. 1363 ISD::CondCode CC = ISD::SETLT; 1364 SelectionDAGISel::CaseBlock CB(CC, SV, C, TrueBB, FalseBB, CR.CaseBB); 1365 1366 if (CR.CaseBB == CurMBB) 1367 visitSwitchCase(CB); 1368 else 1369 SwitchCases.push_back(CB); 1370 } 1371 } 1372} 1373 1374void SelectionDAGLowering::visitSub(User &I) { 1375 // -0.0 - X --> fneg 1376 const Type *Ty = I.getType(); 1377 if (isa<PackedType>(Ty)) { 1378 visitVectorBinary(I, ISD::VSUB); 1379 } else if (Ty->isFloatingPoint()) { 1380 if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0))) 1381 if (CFP->isExactlyValue(-0.0)) { 1382 SDOperand Op2 = getValue(I.getOperand(1)); 1383 setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2)); 1384 return; 1385 } 1386 visitScalarBinary(I, ISD::FSUB); 1387 } else 1388 visitScalarBinary(I, ISD::SUB); 1389} 1390 1391void SelectionDAGLowering::visitScalarBinary(User &I, unsigned OpCode) { 1392 SDOperand Op1 = getValue(I.getOperand(0)); 1393 SDOperand Op2 = getValue(I.getOperand(1)); 1394 1395 setValue(&I, DAG.getNode(OpCode, Op1.getValueType(), Op1, Op2)); 1396} 1397 1398void 1399SelectionDAGLowering::visitVectorBinary(User &I, unsigned OpCode) { 1400 assert(isa<PackedType>(I.getType())); 1401 const PackedType *Ty = cast<PackedType>(I.getType()); 1402 SDOperand Typ = DAG.getValueType(TLI.getValueType(Ty->getElementType())); 1403 1404 setValue(&I, DAG.getNode(OpCode, MVT::Vector, 1405 getValue(I.getOperand(0)), 1406 getValue(I.getOperand(1)), 1407 DAG.getConstant(Ty->getNumElements(), MVT::i32), 1408 Typ)); 1409} 1410 1411void SelectionDAGLowering::visitEitherBinary(User &I, unsigned ScalarOp, 1412 unsigned VectorOp) { 1413 if (isa<PackedType>(I.getType())) 1414 visitVectorBinary(I, VectorOp); 1415 else 1416 visitScalarBinary(I, ScalarOp); 1417} 1418 1419void SelectionDAGLowering::visitShift(User &I, unsigned Opcode) { 1420 SDOperand Op1 = getValue(I.getOperand(0)); 1421 SDOperand Op2 = getValue(I.getOperand(1)); 1422 1423 Op2 = DAG.getNode(ISD::ANY_EXTEND, TLI.getShiftAmountTy(), Op2); 1424 1425 setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2)); 1426} 1427 1428void SelectionDAGLowering::visitICmp(User &I) { 1429 ICmpInst::Predicate predicate = ICmpInst::BAD_ICMP_PREDICATE; 1430 if (ICmpInst *IC = dyn_cast<ICmpInst>(&I)) 1431 predicate = IC->getPredicate(); 1432 else if (ConstantExpr *IC = dyn_cast<ConstantExpr>(&I)) 1433 predicate = ICmpInst::Predicate(IC->getPredicate()); 1434 SDOperand Op1 = getValue(I.getOperand(0)); 1435 SDOperand Op2 = getValue(I.getOperand(1)); 1436 ISD::CondCode Opcode; 1437 switch (predicate) { 1438 case ICmpInst::ICMP_EQ : Opcode = ISD::SETEQ; break; 1439 case ICmpInst::ICMP_NE : Opcode = ISD::SETNE; break; 1440 case ICmpInst::ICMP_UGT : Opcode = ISD::SETUGT; break; 1441 case ICmpInst::ICMP_UGE : Opcode = ISD::SETUGE; break; 1442 case ICmpInst::ICMP_ULT : Opcode = ISD::SETULT; break; 1443 case ICmpInst::ICMP_ULE : Opcode = ISD::SETULE; break; 1444 case ICmpInst::ICMP_SGT : Opcode = ISD::SETGT; break; 1445 case ICmpInst::ICMP_SGE : Opcode = ISD::SETGE; break; 1446 case ICmpInst::ICMP_SLT : Opcode = ISD::SETLT; break; 1447 case ICmpInst::ICMP_SLE : Opcode = ISD::SETLE; break; 1448 default: 1449 assert(!"Invalid ICmp predicate value"); 1450 Opcode = ISD::SETEQ; 1451 break; 1452 } 1453 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode)); 1454} 1455 1456void SelectionDAGLowering::visitFCmp(User &I) { 1457 FCmpInst::Predicate predicate = FCmpInst::BAD_FCMP_PREDICATE; 1458 if (FCmpInst *FC = dyn_cast<FCmpInst>(&I)) 1459 predicate = FC->getPredicate(); 1460 else if (ConstantExpr *FC = dyn_cast<ConstantExpr>(&I)) 1461 predicate = FCmpInst::Predicate(FC->getPredicate()); 1462 SDOperand Op1 = getValue(I.getOperand(0)); 1463 SDOperand Op2 = getValue(I.getOperand(1)); 1464 ISD::CondCode Condition, FOC, FPC; 1465 switch (predicate) { 1466 case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break; 1467 case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break; 1468 case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break; 1469 case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break; 1470 case FCmpInst::FCMP_OLT: FOC = ISD::SETLT; FPC = ISD::SETOLT; break; 1471 case FCmpInst::FCMP_OLE: FOC = ISD::SETLE; FPC = ISD::SETOLE; break; 1472 case FCmpInst::FCMP_ONE: FOC = ISD::SETNE; FPC = ISD::SETONE; break; 1473 case FCmpInst::FCMP_ORD: FOC = ISD::SETEQ; FPC = ISD::SETO; break; 1474 case FCmpInst::FCMP_UNO: FOC = ISD::SETNE; FPC = ISD::SETUO; break; 1475 case FCmpInst::FCMP_UEQ: FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break; 1476 case FCmpInst::FCMP_UGT: FOC = ISD::SETGT; FPC = ISD::SETUGT; break; 1477 case FCmpInst::FCMP_UGE: FOC = ISD::SETGE; FPC = ISD::SETUGE; break; 1478 case FCmpInst::FCMP_ULT: FOC = ISD::SETLT; FPC = ISD::SETULT; break; 1479 case FCmpInst::FCMP_ULE: FOC = ISD::SETLE; FPC = ISD::SETULE; break; 1480 case FCmpInst::FCMP_UNE: FOC = ISD::SETNE; FPC = ISD::SETUNE; break; 1481 case FCmpInst::FCMP_TRUE: FOC = FPC = ISD::SETTRUE; break; 1482 default: 1483 assert(!"Invalid FCmp predicate value"); 1484 FOC = FPC = ISD::SETFALSE; 1485 break; 1486 } 1487 if (FiniteOnlyFPMath()) 1488 Condition = FOC; 1489 else 1490 Condition = FPC; 1491 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Condition)); 1492} 1493 1494void SelectionDAGLowering::visitSelect(User &I) { 1495 SDOperand Cond = getValue(I.getOperand(0)); 1496 SDOperand TrueVal = getValue(I.getOperand(1)); 1497 SDOperand FalseVal = getValue(I.getOperand(2)); 1498 if (!isa<PackedType>(I.getType())) { 1499 setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond, 1500 TrueVal, FalseVal)); 1501 } else { 1502 setValue(&I, DAG.getNode(ISD::VSELECT, MVT::Vector, Cond, TrueVal, FalseVal, 1503 *(TrueVal.Val->op_end()-2), 1504 *(TrueVal.Val->op_end()-1))); 1505 } 1506} 1507 1508 1509void SelectionDAGLowering::visitTrunc(User &I) { 1510 // TruncInst cannot be a no-op cast because sizeof(src) > sizeof(dest). 1511 SDOperand N = getValue(I.getOperand(0)); 1512 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 1513 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N)); 1514} 1515 1516void SelectionDAGLowering::visitZExt(User &I) { 1517 // ZExt cannot be a no-op cast because sizeof(src) < sizeof(dest). 1518 // ZExt also can't be a cast to bool for same reason. So, nothing much to do 1519 SDOperand N = getValue(I.getOperand(0)); 1520 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 1521 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N)); 1522} 1523 1524void SelectionDAGLowering::visitSExt(User &I) { 1525 // SExt cannot be a no-op cast because sizeof(src) < sizeof(dest). 1526 // SExt also can't be a cast to bool for same reason. So, nothing much to do 1527 SDOperand N = getValue(I.getOperand(0)); 1528 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 1529 setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestVT, N)); 1530} 1531 1532void SelectionDAGLowering::visitFPTrunc(User &I) { 1533 // FPTrunc is never a no-op cast, no need to check 1534 SDOperand N = getValue(I.getOperand(0)); 1535 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 1536 setValue(&I, DAG.getNode(ISD::FP_ROUND, DestVT, N)); 1537} 1538 1539void SelectionDAGLowering::visitFPExt(User &I){ 1540 // FPTrunc is never a no-op cast, no need to check 1541 SDOperand N = getValue(I.getOperand(0)); 1542 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 1543 setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestVT, N)); 1544} 1545 1546void SelectionDAGLowering::visitFPToUI(User &I) { 1547 // FPToUI is never a no-op cast, no need to check 1548 SDOperand N = getValue(I.getOperand(0)); 1549 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 1550 setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestVT, N)); 1551} 1552 1553void SelectionDAGLowering::visitFPToSI(User &I) { 1554 // FPToSI is never a no-op cast, no need to check 1555 SDOperand N = getValue(I.getOperand(0)); 1556 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 1557 setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestVT, N)); 1558} 1559 1560void SelectionDAGLowering::visitUIToFP(User &I) { 1561 // UIToFP is never a no-op cast, no need to check 1562 SDOperand N = getValue(I.getOperand(0)); 1563 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 1564 setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestVT, N)); 1565} 1566 1567void SelectionDAGLowering::visitSIToFP(User &I){ 1568 // UIToFP is never a no-op cast, no need to check 1569 SDOperand N = getValue(I.getOperand(0)); 1570 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 1571 setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestVT, N)); 1572} 1573 1574void SelectionDAGLowering::visitPtrToInt(User &I) { 1575 // What to do depends on the size of the integer and the size of the pointer. 1576 // We can either truncate, zero extend, or no-op, accordingly. 1577 SDOperand N = getValue(I.getOperand(0)); 1578 MVT::ValueType SrcVT = N.getValueType(); 1579 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 1580 SDOperand Result; 1581 if (MVT::getSizeInBits(DestVT) < MVT::getSizeInBits(SrcVT)) 1582 Result = DAG.getNode(ISD::TRUNCATE, DestVT, N); 1583 else 1584 // Note: ZERO_EXTEND can handle cases where the sizes are equal too 1585 Result = DAG.getNode(ISD::ZERO_EXTEND, DestVT, N); 1586 setValue(&I, Result); 1587} 1588 1589void SelectionDAGLowering::visitIntToPtr(User &I) { 1590 // What to do depends on the size of the integer and the size of the pointer. 1591 // We can either truncate, zero extend, or no-op, accordingly. 1592 SDOperand N = getValue(I.getOperand(0)); 1593 MVT::ValueType SrcVT = N.getValueType(); 1594 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 1595 if (MVT::getSizeInBits(DestVT) < MVT::getSizeInBits(SrcVT)) 1596 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N)); 1597 else 1598 // Note: ZERO_EXTEND can handle cases where the sizes are equal too 1599 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N)); 1600} 1601 1602void SelectionDAGLowering::visitBitCast(User &I) { 1603 SDOperand N = getValue(I.getOperand(0)); 1604 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 1605 if (DestVT == MVT::Vector) { 1606 // This is a cast to a vector from something else. 1607 // Get information about the output vector. 1608 const PackedType *DestTy = cast<PackedType>(I.getType()); 1609 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType()); 1610 setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N, 1611 DAG.getConstant(DestTy->getNumElements(),MVT::i32), 1612 DAG.getValueType(EltVT))); 1613 return; 1614 } 1615 MVT::ValueType SrcVT = N.getValueType(); 1616 if (SrcVT == MVT::Vector) { 1617 // This is a cast from a vctor to something else. 1618 // Get information about the input vector. 1619 setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N)); 1620 return; 1621 } 1622 1623 // BitCast assures us that source and destination are the same size so this 1624 // is either a BIT_CONVERT or a no-op. 1625 if (DestVT != N.getValueType()) 1626 setValue(&I, DAG.getNode(ISD::BIT_CONVERT, DestVT, N)); // convert types 1627 else 1628 setValue(&I, N); // noop cast. 1629} 1630 1631void SelectionDAGLowering::visitInsertElement(User &I) { 1632 SDOperand InVec = getValue(I.getOperand(0)); 1633 SDOperand InVal = getValue(I.getOperand(1)); 1634 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), 1635 getValue(I.getOperand(2))); 1636 1637 SDOperand Num = *(InVec.Val->op_end()-2); 1638 SDOperand Typ = *(InVec.Val->op_end()-1); 1639 setValue(&I, DAG.getNode(ISD::VINSERT_VECTOR_ELT, MVT::Vector, 1640 InVec, InVal, InIdx, Num, Typ)); 1641} 1642 1643void SelectionDAGLowering::visitExtractElement(User &I) { 1644 SDOperand InVec = getValue(I.getOperand(0)); 1645 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), 1646 getValue(I.getOperand(1))); 1647 SDOperand Typ = *(InVec.Val->op_end()-1); 1648 setValue(&I, DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, 1649 TLI.getValueType(I.getType()), InVec, InIdx)); 1650} 1651 1652void SelectionDAGLowering::visitShuffleVector(User &I) { 1653 SDOperand V1 = getValue(I.getOperand(0)); 1654 SDOperand V2 = getValue(I.getOperand(1)); 1655 SDOperand Mask = getValue(I.getOperand(2)); 1656 1657 SDOperand Num = *(V1.Val->op_end()-2); 1658 SDOperand Typ = *(V2.Val->op_end()-1); 1659 setValue(&I, DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, 1660 V1, V2, Mask, Num, Typ)); 1661} 1662 1663 1664void SelectionDAGLowering::visitGetElementPtr(User &I) { 1665 SDOperand N = getValue(I.getOperand(0)); 1666 const Type *Ty = I.getOperand(0)->getType(); 1667 1668 for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end(); 1669 OI != E; ++OI) { 1670 Value *Idx = *OI; 1671 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 1672 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue(); 1673 if (Field) { 1674 // N = N + Offset 1675 uint64_t Offset = TD->getStructLayout(StTy)->MemberOffsets[Field]; 1676 N = DAG.getNode(ISD::ADD, N.getValueType(), N, 1677 getIntPtrConstant(Offset)); 1678 } 1679 Ty = StTy->getElementType(Field); 1680 } else { 1681 Ty = cast<SequentialType>(Ty)->getElementType(); 1682 1683 // If this is a constant subscript, handle it quickly. 1684 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 1685 if (CI->getZExtValue() == 0) continue; 1686 uint64_t Offs = 1687 TD->getTypeSize(Ty)*cast<ConstantInt>(CI)->getSExtValue(); 1688 N = DAG.getNode(ISD::ADD, N.getValueType(), N, getIntPtrConstant(Offs)); 1689 continue; 1690 } 1691 1692 // N = N + Idx * ElementSize; 1693 uint64_t ElementSize = TD->getTypeSize(Ty); 1694 SDOperand IdxN = getValue(Idx); 1695 1696 // If the index is smaller or larger than intptr_t, truncate or extend 1697 // it. 1698 if (IdxN.getValueType() < N.getValueType()) { 1699 IdxN = DAG.getNode(ISD::SIGN_EXTEND, N.getValueType(), IdxN); 1700 } else if (IdxN.getValueType() > N.getValueType()) 1701 IdxN = DAG.getNode(ISD::TRUNCATE, N.getValueType(), IdxN); 1702 1703 // If this is a multiply by a power of two, turn it into a shl 1704 // immediately. This is a very common case. 1705 if (isPowerOf2_64(ElementSize)) { 1706 unsigned Amt = Log2_64(ElementSize); 1707 IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN, 1708 DAG.getConstant(Amt, TLI.getShiftAmountTy())); 1709 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN); 1710 continue; 1711 } 1712 1713 SDOperand Scale = getIntPtrConstant(ElementSize); 1714 IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale); 1715 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN); 1716 } 1717 } 1718 setValue(&I, N); 1719} 1720 1721void SelectionDAGLowering::visitAlloca(AllocaInst &I) { 1722 // If this is a fixed sized alloca in the entry block of the function, 1723 // allocate it statically on the stack. 1724 if (FuncInfo.StaticAllocaMap.count(&I)) 1725 return; // getValue will auto-populate this. 1726 1727 const Type *Ty = I.getAllocatedType(); 1728 uint64_t TySize = TLI.getTargetData()->getTypeSize(Ty); 1729 unsigned Align = 1730 std::max((unsigned)TLI.getTargetData()->getTypeAlignmentPref(Ty), 1731 I.getAlignment()); 1732 1733 SDOperand AllocSize = getValue(I.getArraySize()); 1734 MVT::ValueType IntPtr = TLI.getPointerTy(); 1735 if (IntPtr < AllocSize.getValueType()) 1736 AllocSize = DAG.getNode(ISD::TRUNCATE, IntPtr, AllocSize); 1737 else if (IntPtr > AllocSize.getValueType()) 1738 AllocSize = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, AllocSize); 1739 1740 AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize, 1741 getIntPtrConstant(TySize)); 1742 1743 // Handle alignment. If the requested alignment is less than or equal to the 1744 // stack alignment, ignore it and round the size of the allocation up to the 1745 // stack alignment size. If the size is greater than the stack alignment, we 1746 // note this in the DYNAMIC_STACKALLOC node. 1747 unsigned StackAlign = 1748 TLI.getTargetMachine().getFrameInfo()->getStackAlignment(); 1749 if (Align <= StackAlign) { 1750 Align = 0; 1751 // Add SA-1 to the size. 1752 AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize, 1753 getIntPtrConstant(StackAlign-1)); 1754 // Mask out the low bits for alignment purposes. 1755 AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize, 1756 getIntPtrConstant(~(uint64_t)(StackAlign-1))); 1757 } 1758 1759 SDOperand Ops[] = { getRoot(), AllocSize, getIntPtrConstant(Align) }; 1760 const MVT::ValueType *VTs = DAG.getNodeValueTypes(AllocSize.getValueType(), 1761 MVT::Other); 1762 SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, 2, Ops, 3); 1763 DAG.setRoot(setValue(&I, DSA).getValue(1)); 1764 1765 // Inform the Frame Information that we have just allocated a variable-sized 1766 // object. 1767 CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject(); 1768} 1769 1770void SelectionDAGLowering::visitLoad(LoadInst &I) { 1771 SDOperand Ptr = getValue(I.getOperand(0)); 1772 1773 SDOperand Root; 1774 if (I.isVolatile()) 1775 Root = getRoot(); 1776 else { 1777 // Do not serialize non-volatile loads against each other. 1778 Root = DAG.getRoot(); 1779 } 1780 1781 setValue(&I, getLoadFrom(I.getType(), Ptr, I.getOperand(0), 1782 Root, I.isVolatile())); 1783} 1784 1785SDOperand SelectionDAGLowering::getLoadFrom(const Type *Ty, SDOperand Ptr, 1786 const Value *SV, SDOperand Root, 1787 bool isVolatile) { 1788 SDOperand L; 1789 if (const PackedType *PTy = dyn_cast<PackedType>(Ty)) { 1790 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType()); 1791 L = DAG.getVecLoad(PTy->getNumElements(), PVT, Root, Ptr, 1792 DAG.getSrcValue(SV)); 1793 } else { 1794 L = DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SV, 0, isVolatile); 1795 } 1796 1797 if (isVolatile) 1798 DAG.setRoot(L.getValue(1)); 1799 else 1800 PendingLoads.push_back(L.getValue(1)); 1801 1802 return L; 1803} 1804 1805 1806void SelectionDAGLowering::visitStore(StoreInst &I) { 1807 Value *SrcV = I.getOperand(0); 1808 SDOperand Src = getValue(SrcV); 1809 SDOperand Ptr = getValue(I.getOperand(1)); 1810 DAG.setRoot(DAG.getStore(getRoot(), Src, Ptr, I.getOperand(1), 0, 1811 I.isVolatile())); 1812} 1813 1814/// IntrinsicCannotAccessMemory - Return true if the specified intrinsic cannot 1815/// access memory and has no other side effects at all. 1816static bool IntrinsicCannotAccessMemory(unsigned IntrinsicID) { 1817#define GET_NO_MEMORY_INTRINSICS 1818#include "llvm/Intrinsics.gen" 1819#undef GET_NO_MEMORY_INTRINSICS 1820 return false; 1821} 1822 1823// IntrinsicOnlyReadsMemory - Return true if the specified intrinsic doesn't 1824// have any side-effects or if it only reads memory. 1825static bool IntrinsicOnlyReadsMemory(unsigned IntrinsicID) { 1826#define GET_SIDE_EFFECT_INFO 1827#include "llvm/Intrinsics.gen" 1828#undef GET_SIDE_EFFECT_INFO 1829 return false; 1830} 1831 1832/// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC 1833/// node. 1834void SelectionDAGLowering::visitTargetIntrinsic(CallInst &I, 1835 unsigned Intrinsic) { 1836 bool HasChain = !IntrinsicCannotAccessMemory(Intrinsic); 1837 bool OnlyLoad = HasChain && IntrinsicOnlyReadsMemory(Intrinsic); 1838 1839 // Build the operand list. 1840 SmallVector<SDOperand, 8> Ops; 1841 if (HasChain) { // If this intrinsic has side-effects, chainify it. 1842 if (OnlyLoad) { 1843 // We don't need to serialize loads against other loads. 1844 Ops.push_back(DAG.getRoot()); 1845 } else { 1846 Ops.push_back(getRoot()); 1847 } 1848 } 1849 1850 // Add the intrinsic ID as an integer operand. 1851 Ops.push_back(DAG.getConstant(Intrinsic, TLI.getPointerTy())); 1852 1853 // Add all operands of the call to the operand list. 1854 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) { 1855 SDOperand Op = getValue(I.getOperand(i)); 1856 1857 // If this is a vector type, force it to the right packed type. 1858 if (Op.getValueType() == MVT::Vector) { 1859 const PackedType *OpTy = cast<PackedType>(I.getOperand(i)->getType()); 1860 MVT::ValueType EltVT = TLI.getValueType(OpTy->getElementType()); 1861 1862 MVT::ValueType VVT = MVT::getVectorType(EltVT, OpTy->getNumElements()); 1863 assert(VVT != MVT::Other && "Intrinsic uses a non-legal type?"); 1864 Op = DAG.getNode(ISD::VBIT_CONVERT, VVT, Op); 1865 } 1866 1867 assert(TLI.isTypeLegal(Op.getValueType()) && 1868 "Intrinsic uses a non-legal type?"); 1869 Ops.push_back(Op); 1870 } 1871 1872 std::vector<MVT::ValueType> VTs; 1873 if (I.getType() != Type::VoidTy) { 1874 MVT::ValueType VT = TLI.getValueType(I.getType()); 1875 if (VT == MVT::Vector) { 1876 const PackedType *DestTy = cast<PackedType>(I.getType()); 1877 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType()); 1878 1879 VT = MVT::getVectorType(EltVT, DestTy->getNumElements()); 1880 assert(VT != MVT::Other && "Intrinsic uses a non-legal type?"); 1881 } 1882 1883 assert(TLI.isTypeLegal(VT) && "Intrinsic uses a non-legal type?"); 1884 VTs.push_back(VT); 1885 } 1886 if (HasChain) 1887 VTs.push_back(MVT::Other); 1888 1889 const MVT::ValueType *VTList = DAG.getNodeValueTypes(VTs); 1890 1891 // Create the node. 1892 SDOperand Result; 1893 if (!HasChain) 1894 Result = DAG.getNode(ISD::INTRINSIC_WO_CHAIN, VTList, VTs.size(), 1895 &Ops[0], Ops.size()); 1896 else if (I.getType() != Type::VoidTy) 1897 Result = DAG.getNode(ISD::INTRINSIC_W_CHAIN, VTList, VTs.size(), 1898 &Ops[0], Ops.size()); 1899 else 1900 Result = DAG.getNode(ISD::INTRINSIC_VOID, VTList, VTs.size(), 1901 &Ops[0], Ops.size()); 1902 1903 if (HasChain) { 1904 SDOperand Chain = Result.getValue(Result.Val->getNumValues()-1); 1905 if (OnlyLoad) 1906 PendingLoads.push_back(Chain); 1907 else 1908 DAG.setRoot(Chain); 1909 } 1910 if (I.getType() != Type::VoidTy) { 1911 if (const PackedType *PTy = dyn_cast<PackedType>(I.getType())) { 1912 MVT::ValueType EVT = TLI.getValueType(PTy->getElementType()); 1913 Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result, 1914 DAG.getConstant(PTy->getNumElements(), MVT::i32), 1915 DAG.getValueType(EVT)); 1916 } 1917 setValue(&I, Result); 1918 } 1919} 1920 1921/// visitIntrinsicCall - Lower the call to the specified intrinsic function. If 1922/// we want to emit this as a call to a named external function, return the name 1923/// otherwise lower it and return null. 1924const char * 1925SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { 1926 switch (Intrinsic) { 1927 default: 1928 // By default, turn this into a target intrinsic node. 1929 visitTargetIntrinsic(I, Intrinsic); 1930 return 0; 1931 case Intrinsic::vastart: visitVAStart(I); return 0; 1932 case Intrinsic::vaend: visitVAEnd(I); return 0; 1933 case Intrinsic::vacopy: visitVACopy(I); return 0; 1934 case Intrinsic::returnaddress: 1935 setValue(&I, DAG.getNode(ISD::RETURNADDR, TLI.getPointerTy(), 1936 getValue(I.getOperand(1)))); 1937 return 0; 1938 case Intrinsic::frameaddress: 1939 setValue(&I, DAG.getNode(ISD::FRAMEADDR, TLI.getPointerTy(), 1940 getValue(I.getOperand(1)))); 1941 return 0; 1942 case Intrinsic::setjmp: 1943 return "_setjmp"+!TLI.usesUnderscoreSetJmp(); 1944 break; 1945 case Intrinsic::longjmp: 1946 return "_longjmp"+!TLI.usesUnderscoreLongJmp(); 1947 break; 1948 case Intrinsic::memcpy_i32: 1949 case Intrinsic::memcpy_i64: 1950 visitMemIntrinsic(I, ISD::MEMCPY); 1951 return 0; 1952 case Intrinsic::memset_i32: 1953 case Intrinsic::memset_i64: 1954 visitMemIntrinsic(I, ISD::MEMSET); 1955 return 0; 1956 case Intrinsic::memmove_i32: 1957 case Intrinsic::memmove_i64: 1958 visitMemIntrinsic(I, ISD::MEMMOVE); 1959 return 0; 1960 1961 case Intrinsic::dbg_stoppoint: { 1962 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 1963 DbgStopPointInst &SPI = cast<DbgStopPointInst>(I); 1964 if (MMI && SPI.getContext() && MMI->Verify(SPI.getContext())) { 1965 SDOperand Ops[5]; 1966 1967 Ops[0] = getRoot(); 1968 Ops[1] = getValue(SPI.getLineValue()); 1969 Ops[2] = getValue(SPI.getColumnValue()); 1970 1971 DebugInfoDesc *DD = MMI->getDescFor(SPI.getContext()); 1972 assert(DD && "Not a debug information descriptor"); 1973 CompileUnitDesc *CompileUnit = cast<CompileUnitDesc>(DD); 1974 1975 Ops[3] = DAG.getString(CompileUnit->getFileName()); 1976 Ops[4] = DAG.getString(CompileUnit->getDirectory()); 1977 1978 DAG.setRoot(DAG.getNode(ISD::LOCATION, MVT::Other, Ops, 5)); 1979 } 1980 1981 return 0; 1982 } 1983 case Intrinsic::dbg_region_start: { 1984 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 1985 DbgRegionStartInst &RSI = cast<DbgRegionStartInst>(I); 1986 if (MMI && RSI.getContext() && MMI->Verify(RSI.getContext())) { 1987 unsigned LabelID = MMI->RecordRegionStart(RSI.getContext()); 1988 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, getRoot(), 1989 DAG.getConstant(LabelID, MVT::i32))); 1990 } 1991 1992 return 0; 1993 } 1994 case Intrinsic::dbg_region_end: { 1995 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 1996 DbgRegionEndInst &REI = cast<DbgRegionEndInst>(I); 1997 if (MMI && REI.getContext() && MMI->Verify(REI.getContext())) { 1998 unsigned LabelID = MMI->RecordRegionEnd(REI.getContext()); 1999 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, 2000 getRoot(), DAG.getConstant(LabelID, MVT::i32))); 2001 } 2002 2003 return 0; 2004 } 2005 case Intrinsic::dbg_func_start: { 2006 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 2007 DbgFuncStartInst &FSI = cast<DbgFuncStartInst>(I); 2008 if (MMI && FSI.getSubprogram() && 2009 MMI->Verify(FSI.getSubprogram())) { 2010 unsigned LabelID = MMI->RecordRegionStart(FSI.getSubprogram()); 2011 DAG.setRoot(DAG.getNode(ISD::LABEL, MVT::Other, 2012 getRoot(), DAG.getConstant(LabelID, MVT::i32))); 2013 } 2014 2015 return 0; 2016 } 2017 case Intrinsic::dbg_declare: { 2018 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 2019 DbgDeclareInst &DI = cast<DbgDeclareInst>(I); 2020 if (MMI && DI.getVariable() && MMI->Verify(DI.getVariable())) { 2021 SDOperand AddressOp = getValue(DI.getAddress()); 2022 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(AddressOp)) 2023 MMI->RecordVariable(DI.getVariable(), FI->getIndex()); 2024 } 2025 2026 return 0; 2027 } 2028 2029 case Intrinsic::sqrt_f32: 2030 case Intrinsic::sqrt_f64: 2031 setValue(&I, DAG.getNode(ISD::FSQRT, 2032 getValue(I.getOperand(1)).getValueType(), 2033 getValue(I.getOperand(1)))); 2034 return 0; 2035 case Intrinsic::powi_f32: 2036 case Intrinsic::powi_f64: 2037 setValue(&I, DAG.getNode(ISD::FPOWI, 2038 getValue(I.getOperand(1)).getValueType(), 2039 getValue(I.getOperand(1)), 2040 getValue(I.getOperand(2)))); 2041 return 0; 2042 case Intrinsic::pcmarker: { 2043 SDOperand Tmp = getValue(I.getOperand(1)); 2044 DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp)); 2045 return 0; 2046 } 2047 case Intrinsic::readcyclecounter: { 2048 SDOperand Op = getRoot(); 2049 SDOperand Tmp = DAG.getNode(ISD::READCYCLECOUNTER, 2050 DAG.getNodeValueTypes(MVT::i64, MVT::Other), 2, 2051 &Op, 1); 2052 setValue(&I, Tmp); 2053 DAG.setRoot(Tmp.getValue(1)); 2054 return 0; 2055 } 2056 case Intrinsic::bswap_i16: 2057 case Intrinsic::bswap_i32: 2058 case Intrinsic::bswap_i64: 2059 setValue(&I, DAG.getNode(ISD::BSWAP, 2060 getValue(I.getOperand(1)).getValueType(), 2061 getValue(I.getOperand(1)))); 2062 return 0; 2063 case Intrinsic::cttz_i8: 2064 case Intrinsic::cttz_i16: 2065 case Intrinsic::cttz_i32: 2066 case Intrinsic::cttz_i64: 2067 setValue(&I, DAG.getNode(ISD::CTTZ, 2068 getValue(I.getOperand(1)).getValueType(), 2069 getValue(I.getOperand(1)))); 2070 return 0; 2071 case Intrinsic::ctlz_i8: 2072 case Intrinsic::ctlz_i16: 2073 case Intrinsic::ctlz_i32: 2074 case Intrinsic::ctlz_i64: 2075 setValue(&I, DAG.getNode(ISD::CTLZ, 2076 getValue(I.getOperand(1)).getValueType(), 2077 getValue(I.getOperand(1)))); 2078 return 0; 2079 case Intrinsic::ctpop_i8: 2080 case Intrinsic::ctpop_i16: 2081 case Intrinsic::ctpop_i32: 2082 case Intrinsic::ctpop_i64: 2083 setValue(&I, DAG.getNode(ISD::CTPOP, 2084 getValue(I.getOperand(1)).getValueType(), 2085 getValue(I.getOperand(1)))); 2086 return 0; 2087 case Intrinsic::stacksave: { 2088 SDOperand Op = getRoot(); 2089 SDOperand Tmp = DAG.getNode(ISD::STACKSAVE, 2090 DAG.getNodeValueTypes(TLI.getPointerTy(), MVT::Other), 2, &Op, 1); 2091 setValue(&I, Tmp); 2092 DAG.setRoot(Tmp.getValue(1)); 2093 return 0; 2094 } 2095 case Intrinsic::stackrestore: { 2096 SDOperand Tmp = getValue(I.getOperand(1)); 2097 DAG.setRoot(DAG.getNode(ISD::STACKRESTORE, MVT::Other, getRoot(), Tmp)); 2098 return 0; 2099 } 2100 case Intrinsic::prefetch: 2101 // FIXME: Currently discarding prefetches. 2102 return 0; 2103 } 2104} 2105 2106 2107void SelectionDAGLowering::visitCall(CallInst &I) { 2108 const char *RenameFn = 0; 2109 if (Function *F = I.getCalledFunction()) { 2110 if (F->isExternal()) 2111 if (unsigned IID = F->getIntrinsicID()) { 2112 RenameFn = visitIntrinsicCall(I, IID); 2113 if (!RenameFn) 2114 return; 2115 } else { // Not an LLVM intrinsic. 2116 const std::string &Name = F->getName(); 2117 if (Name[0] == 'c' && (Name == "copysign" || Name == "copysignf")) { 2118 if (I.getNumOperands() == 3 && // Basic sanity checks. 2119 I.getOperand(1)->getType()->isFloatingPoint() && 2120 I.getType() == I.getOperand(1)->getType() && 2121 I.getType() == I.getOperand(2)->getType()) { 2122 SDOperand LHS = getValue(I.getOperand(1)); 2123 SDOperand RHS = getValue(I.getOperand(2)); 2124 setValue(&I, DAG.getNode(ISD::FCOPYSIGN, LHS.getValueType(), 2125 LHS, RHS)); 2126 return; 2127 } 2128 } else if (Name[0] == 'f' && (Name == "fabs" || Name == "fabsf")) { 2129 if (I.getNumOperands() == 2 && // Basic sanity checks. 2130 I.getOperand(1)->getType()->isFloatingPoint() && 2131 I.getType() == I.getOperand(1)->getType()) { 2132 SDOperand Tmp = getValue(I.getOperand(1)); 2133 setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp)); 2134 return; 2135 } 2136 } else if (Name[0] == 's' && (Name == "sin" || Name == "sinf")) { 2137 if (I.getNumOperands() == 2 && // Basic sanity checks. 2138 I.getOperand(1)->getType()->isFloatingPoint() && 2139 I.getType() == I.getOperand(1)->getType()) { 2140 SDOperand Tmp = getValue(I.getOperand(1)); 2141 setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp)); 2142 return; 2143 } 2144 } else if (Name[0] == 'c' && (Name == "cos" || Name == "cosf")) { 2145 if (I.getNumOperands() == 2 && // Basic sanity checks. 2146 I.getOperand(1)->getType()->isFloatingPoint() && 2147 I.getType() == I.getOperand(1)->getType()) { 2148 SDOperand Tmp = getValue(I.getOperand(1)); 2149 setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp)); 2150 return; 2151 } 2152 } 2153 } 2154 } else if (isa<InlineAsm>(I.getOperand(0))) { 2155 visitInlineAsm(I); 2156 return; 2157 } 2158 2159 const PointerType *PT = cast<PointerType>(I.getCalledValue()->getType()); 2160 const FunctionType *FTy = cast<FunctionType>(PT->getElementType()); 2161 2162 SDOperand Callee; 2163 if (!RenameFn) 2164 Callee = getValue(I.getOperand(0)); 2165 else 2166 Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy()); 2167 TargetLowering::ArgListTy Args; 2168 TargetLowering::ArgListEntry Entry; 2169 Args.reserve(I.getNumOperands()); 2170 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) { 2171 Value *Arg = I.getOperand(i); 2172 SDOperand ArgNode = getValue(Arg); 2173 Entry.Node = ArgNode; Entry.Ty = Arg->getType(); 2174 Entry.isSigned = FTy->paramHasAttr(i, FunctionType::SExtAttribute); 2175 Entry.isInReg = FTy->paramHasAttr(i, FunctionType::InRegAttribute); 2176 Entry.isSRet = FTy->paramHasAttr(i, FunctionType::StructRetAttribute); 2177 Args.push_back(Entry); 2178 } 2179 2180 std::pair<SDOperand,SDOperand> Result = 2181 TLI.LowerCallTo(getRoot(), I.getType(), 2182 FTy->paramHasAttr(0,FunctionType::SExtAttribute), 2183 FTy->isVarArg(), I.getCallingConv(), I.isTailCall(), 2184 Callee, Args, DAG); 2185 if (I.getType() != Type::VoidTy) 2186 setValue(&I, Result.first); 2187 DAG.setRoot(Result.second); 2188} 2189 2190SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG, 2191 SDOperand &Chain, SDOperand &Flag)const{ 2192 SDOperand Val = DAG.getCopyFromReg(Chain, Regs[0], RegVT, Flag); 2193 Chain = Val.getValue(1); 2194 Flag = Val.getValue(2); 2195 2196 // If the result was expanded, copy from the top part. 2197 if (Regs.size() > 1) { 2198 assert(Regs.size() == 2 && 2199 "Cannot expand to more than 2 elts yet!"); 2200 SDOperand Hi = DAG.getCopyFromReg(Chain, Regs[1], RegVT, Flag); 2201 Chain = Hi.getValue(1); 2202 Flag = Hi.getValue(2); 2203 if (DAG.getTargetLoweringInfo().isLittleEndian()) 2204 return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Val, Hi); 2205 else 2206 return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Hi, Val); 2207 } 2208 2209 // Otherwise, if the return value was promoted or extended, truncate it to the 2210 // appropriate type. 2211 if (RegVT == ValueVT) 2212 return Val; 2213 2214 if (MVT::isInteger(RegVT)) { 2215 if (ValueVT < RegVT) 2216 return DAG.getNode(ISD::TRUNCATE, ValueVT, Val); 2217 else 2218 return DAG.getNode(ISD::ANY_EXTEND, ValueVT, Val); 2219 } else { 2220 return DAG.getNode(ISD::FP_ROUND, ValueVT, Val); 2221 } 2222} 2223 2224/// getCopyToRegs - Emit a series of CopyToReg nodes that copies the 2225/// specified value into the registers specified by this object. This uses 2226/// Chain/Flag as the input and updates them for the output Chain/Flag. 2227void RegsForValue::getCopyToRegs(SDOperand Val, SelectionDAG &DAG, 2228 SDOperand &Chain, SDOperand &Flag, 2229 MVT::ValueType PtrVT) const { 2230 if (Regs.size() == 1) { 2231 // If there is a single register and the types differ, this must be 2232 // a promotion. 2233 if (RegVT != ValueVT) { 2234 if (MVT::isInteger(RegVT)) { 2235 if (RegVT < ValueVT) 2236 Val = DAG.getNode(ISD::TRUNCATE, RegVT, Val); 2237 else 2238 Val = DAG.getNode(ISD::ANY_EXTEND, RegVT, Val); 2239 } else 2240 Val = DAG.getNode(ISD::FP_EXTEND, RegVT, Val); 2241 } 2242 Chain = DAG.getCopyToReg(Chain, Regs[0], Val, Flag); 2243 Flag = Chain.getValue(1); 2244 } else { 2245 std::vector<unsigned> R(Regs); 2246 if (!DAG.getTargetLoweringInfo().isLittleEndian()) 2247 std::reverse(R.begin(), R.end()); 2248 2249 for (unsigned i = 0, e = R.size(); i != e; ++i) { 2250 SDOperand Part = DAG.getNode(ISD::EXTRACT_ELEMENT, RegVT, Val, 2251 DAG.getConstant(i, PtrVT)); 2252 Chain = DAG.getCopyToReg(Chain, R[i], Part, Flag); 2253 Flag = Chain.getValue(1); 2254 } 2255 } 2256} 2257 2258/// AddInlineAsmOperands - Add this value to the specified inlineasm node 2259/// operand list. This adds the code marker and includes the number of 2260/// values added into it. 2261void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG, 2262 std::vector<SDOperand> &Ops) const { 2263 Ops.push_back(DAG.getConstant(Code | (Regs.size() << 3), MVT::i32)); 2264 for (unsigned i = 0, e = Regs.size(); i != e; ++i) 2265 Ops.push_back(DAG.getRegister(Regs[i], RegVT)); 2266} 2267 2268/// isAllocatableRegister - If the specified register is safe to allocate, 2269/// i.e. it isn't a stack pointer or some other special register, return the 2270/// register class for the register. Otherwise, return null. 2271static const TargetRegisterClass * 2272isAllocatableRegister(unsigned Reg, MachineFunction &MF, 2273 const TargetLowering &TLI, const MRegisterInfo *MRI) { 2274 MVT::ValueType FoundVT = MVT::Other; 2275 const TargetRegisterClass *FoundRC = 0; 2276 for (MRegisterInfo::regclass_iterator RCI = MRI->regclass_begin(), 2277 E = MRI->regclass_end(); RCI != E; ++RCI) { 2278 MVT::ValueType ThisVT = MVT::Other; 2279 2280 const TargetRegisterClass *RC = *RCI; 2281 // If none of the the value types for this register class are valid, we 2282 // can't use it. For example, 64-bit reg classes on 32-bit targets. 2283 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end(); 2284 I != E; ++I) { 2285 if (TLI.isTypeLegal(*I)) { 2286 // If we have already found this register in a different register class, 2287 // choose the one with the largest VT specified. For example, on 2288 // PowerPC, we favor f64 register classes over f32. 2289 if (FoundVT == MVT::Other || 2290 MVT::getSizeInBits(FoundVT) < MVT::getSizeInBits(*I)) { 2291 ThisVT = *I; 2292 break; 2293 } 2294 } 2295 } 2296 2297 if (ThisVT == MVT::Other) continue; 2298 2299 // NOTE: This isn't ideal. In particular, this might allocate the 2300 // frame pointer in functions that need it (due to them not being taken 2301 // out of allocation, because a variable sized allocation hasn't been seen 2302 // yet). This is a slight code pessimization, but should still work. 2303 for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF), 2304 E = RC->allocation_order_end(MF); I != E; ++I) 2305 if (*I == Reg) { 2306 // We found a matching register class. Keep looking at others in case 2307 // we find one with larger registers that this physreg is also in. 2308 FoundRC = RC; 2309 FoundVT = ThisVT; 2310 break; 2311 } 2312 } 2313 return FoundRC; 2314} 2315 2316RegsForValue SelectionDAGLowering:: 2317GetRegistersForValue(const std::string &ConstrCode, 2318 MVT::ValueType VT, bool isOutReg, bool isInReg, 2319 std::set<unsigned> &OutputRegs, 2320 std::set<unsigned> &InputRegs) { 2321 std::pair<unsigned, const TargetRegisterClass*> PhysReg = 2322 TLI.getRegForInlineAsmConstraint(ConstrCode, VT); 2323 std::vector<unsigned> Regs; 2324 2325 unsigned NumRegs = VT != MVT::Other ? TLI.getNumElements(VT) : 1; 2326 MVT::ValueType RegVT; 2327 MVT::ValueType ValueVT = VT; 2328 2329 // If this is a constraint for a specific physical register, like {r17}, 2330 // assign it now. 2331 if (PhysReg.first) { 2332 if (VT == MVT::Other) 2333 ValueVT = *PhysReg.second->vt_begin(); 2334 2335 // Get the actual register value type. This is important, because the user 2336 // may have asked for (e.g.) the AX register in i32 type. We need to 2337 // remember that AX is actually i16 to get the right extension. 2338 RegVT = *PhysReg.second->vt_begin(); 2339 2340 // This is a explicit reference to a physical register. 2341 Regs.push_back(PhysReg.first); 2342 2343 // If this is an expanded reference, add the rest of the regs to Regs. 2344 if (NumRegs != 1) { 2345 TargetRegisterClass::iterator I = PhysReg.second->begin(); 2346 TargetRegisterClass::iterator E = PhysReg.second->end(); 2347 for (; *I != PhysReg.first; ++I) 2348 assert(I != E && "Didn't find reg!"); 2349 2350 // Already added the first reg. 2351 --NumRegs; ++I; 2352 for (; NumRegs; --NumRegs, ++I) { 2353 assert(I != E && "Ran out of registers to allocate!"); 2354 Regs.push_back(*I); 2355 } 2356 } 2357 return RegsForValue(Regs, RegVT, ValueVT); 2358 } 2359 2360 // Otherwise, if this was a reference to an LLVM register class, create vregs 2361 // for this reference. 2362 std::vector<unsigned> RegClassRegs; 2363 if (PhysReg.second) { 2364 // If this is an early clobber or tied register, our regalloc doesn't know 2365 // how to maintain the constraint. If it isn't, go ahead and create vreg 2366 // and let the regalloc do the right thing. 2367 if (!isOutReg || !isInReg) { 2368 if (VT == MVT::Other) 2369 ValueVT = *PhysReg.second->vt_begin(); 2370 RegVT = *PhysReg.second->vt_begin(); 2371 2372 // Create the appropriate number of virtual registers. 2373 SSARegMap *RegMap = DAG.getMachineFunction().getSSARegMap(); 2374 for (; NumRegs; --NumRegs) 2375 Regs.push_back(RegMap->createVirtualRegister(PhysReg.second)); 2376 2377 return RegsForValue(Regs, RegVT, ValueVT); 2378 } 2379 2380 // Otherwise, we can't allocate it. Let the code below figure out how to 2381 // maintain these constraints. 2382 RegClassRegs.assign(PhysReg.second->begin(), PhysReg.second->end()); 2383 2384 } else { 2385 // This is a reference to a register class that doesn't directly correspond 2386 // to an LLVM register class. Allocate NumRegs consecutive, available, 2387 // registers from the class. 2388 RegClassRegs = TLI.getRegClassForInlineAsmConstraint(ConstrCode, VT); 2389 } 2390 2391 const MRegisterInfo *MRI = DAG.getTarget().getRegisterInfo(); 2392 MachineFunction &MF = *CurMBB->getParent(); 2393 unsigned NumAllocated = 0; 2394 for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) { 2395 unsigned Reg = RegClassRegs[i]; 2396 // See if this register is available. 2397 if ((isOutReg && OutputRegs.count(Reg)) || // Already used. 2398 (isInReg && InputRegs.count(Reg))) { // Already used. 2399 // Make sure we find consecutive registers. 2400 NumAllocated = 0; 2401 continue; 2402 } 2403 2404 // Check to see if this register is allocatable (i.e. don't give out the 2405 // stack pointer). 2406 const TargetRegisterClass *RC = isAllocatableRegister(Reg, MF, TLI, MRI); 2407 if (!RC) { 2408 // Make sure we find consecutive registers. 2409 NumAllocated = 0; 2410 continue; 2411 } 2412 2413 // Okay, this register is good, we can use it. 2414 ++NumAllocated; 2415 2416 // If we allocated enough consecutive 2417 if (NumAllocated == NumRegs) { 2418 unsigned RegStart = (i-NumAllocated)+1; 2419 unsigned RegEnd = i+1; 2420 // Mark all of the allocated registers used. 2421 for (unsigned i = RegStart; i != RegEnd; ++i) { 2422 unsigned Reg = RegClassRegs[i]; 2423 Regs.push_back(Reg); 2424 if (isOutReg) OutputRegs.insert(Reg); // Mark reg used. 2425 if (isInReg) InputRegs.insert(Reg); // Mark reg used. 2426 } 2427 2428 return RegsForValue(Regs, *RC->vt_begin(), VT); 2429 } 2430 } 2431 2432 // Otherwise, we couldn't allocate enough registers for this. 2433 return RegsForValue(); 2434} 2435 2436 2437/// visitInlineAsm - Handle a call to an InlineAsm object. 2438/// 2439void SelectionDAGLowering::visitInlineAsm(CallInst &I) { 2440 InlineAsm *IA = cast<InlineAsm>(I.getOperand(0)); 2441 2442 SDOperand AsmStr = DAG.getTargetExternalSymbol(IA->getAsmString().c_str(), 2443 MVT::Other); 2444 2445 std::vector<InlineAsm::ConstraintInfo> Constraints = IA->ParseConstraints(); 2446 std::vector<MVT::ValueType> ConstraintVTs; 2447 2448 /// AsmNodeOperands - A list of pairs. The first element is a register, the 2449 /// second is a bitfield where bit #0 is set if it is a use and bit #1 is set 2450 /// if it is a def of that register. 2451 std::vector<SDOperand> AsmNodeOperands; 2452 AsmNodeOperands.push_back(SDOperand()); // reserve space for input chain 2453 AsmNodeOperands.push_back(AsmStr); 2454 2455 SDOperand Chain = getRoot(); 2456 SDOperand Flag; 2457 2458 // We fully assign registers here at isel time. This is not optimal, but 2459 // should work. For register classes that correspond to LLVM classes, we 2460 // could let the LLVM RA do its thing, but we currently don't. Do a prepass 2461 // over the constraints, collecting fixed registers that we know we can't use. 2462 std::set<unsigned> OutputRegs, InputRegs; 2463 unsigned OpNum = 1; 2464 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { 2465 assert(Constraints[i].Codes.size() == 1 && "Only handles one code so far!"); 2466 std::string &ConstraintCode = Constraints[i].Codes[0]; 2467 2468 MVT::ValueType OpVT; 2469 2470 // Compute the value type for each operand and add it to ConstraintVTs. 2471 switch (Constraints[i].Type) { 2472 case InlineAsm::isOutput: 2473 if (!Constraints[i].isIndirectOutput) { 2474 assert(I.getType() != Type::VoidTy && "Bad inline asm!"); 2475 OpVT = TLI.getValueType(I.getType()); 2476 } else { 2477 const Type *OpTy = I.getOperand(OpNum)->getType(); 2478 OpVT = TLI.getValueType(cast<PointerType>(OpTy)->getElementType()); 2479 OpNum++; // Consumes a call operand. 2480 } 2481 break; 2482 case InlineAsm::isInput: 2483 OpVT = TLI.getValueType(I.getOperand(OpNum)->getType()); 2484 OpNum++; // Consumes a call operand. 2485 break; 2486 case InlineAsm::isClobber: 2487 OpVT = MVT::Other; 2488 break; 2489 } 2490 2491 ConstraintVTs.push_back(OpVT); 2492 2493 if (TLI.getRegForInlineAsmConstraint(ConstraintCode, OpVT).first == 0) 2494 continue; // Not assigned a fixed reg. 2495 2496 // Build a list of regs that this operand uses. This always has a single 2497 // element for promoted/expanded operands. 2498 RegsForValue Regs = GetRegistersForValue(ConstraintCode, OpVT, 2499 false, false, 2500 OutputRegs, InputRegs); 2501 2502 switch (Constraints[i].Type) { 2503 case InlineAsm::isOutput: 2504 // We can't assign any other output to this register. 2505 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 2506 // If this is an early-clobber output, it cannot be assigned to the same 2507 // value as the input reg. 2508 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput) 2509 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 2510 break; 2511 case InlineAsm::isInput: 2512 // We can't assign any other input to this register. 2513 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 2514 break; 2515 case InlineAsm::isClobber: 2516 // Clobbered regs cannot be used as inputs or outputs. 2517 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 2518 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 2519 break; 2520 } 2521 } 2522 2523 // Loop over all of the inputs, copying the operand values into the 2524 // appropriate registers and processing the output regs. 2525 RegsForValue RetValRegs; 2526 std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit; 2527 OpNum = 1; 2528 2529 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { 2530 assert(Constraints[i].Codes.size() == 1 && "Only handles one code so far!"); 2531 std::string &ConstraintCode = Constraints[i].Codes[0]; 2532 2533 switch (Constraints[i].Type) { 2534 case InlineAsm::isOutput: { 2535 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass; 2536 if (ConstraintCode.size() == 1) // not a physreg name. 2537 CTy = TLI.getConstraintType(ConstraintCode[0]); 2538 2539 if (CTy == TargetLowering::C_Memory) { 2540 // Memory output. 2541 SDOperand InOperandVal = getValue(I.getOperand(OpNum)); 2542 2543 // Check that the operand (the address to store to) isn't a float. 2544 if (!MVT::isInteger(InOperandVal.getValueType())) 2545 assert(0 && "MATCH FAIL!"); 2546 2547 if (!Constraints[i].isIndirectOutput) 2548 assert(0 && "MATCH FAIL!"); 2549 2550 OpNum++; // Consumes a call operand. 2551 2552 // Extend/truncate to the right pointer type if needed. 2553 MVT::ValueType PtrType = TLI.getPointerTy(); 2554 if (InOperandVal.getValueType() < PtrType) 2555 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal); 2556 else if (InOperandVal.getValueType() > PtrType) 2557 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal); 2558 2559 // Add information to the INLINEASM node to know about this output. 2560 unsigned ResOpType = 4/*MEM*/ | (1 << 3); 2561 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32)); 2562 AsmNodeOperands.push_back(InOperandVal); 2563 break; 2564 } 2565 2566 // Otherwise, this is a register output. 2567 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!"); 2568 2569 // If this is an early-clobber output, or if there is an input 2570 // constraint that matches this, we need to reserve the input register 2571 // so no other inputs allocate to it. 2572 bool UsesInputRegister = false; 2573 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput) 2574 UsesInputRegister = true; 2575 2576 // Copy the output from the appropriate register. Find a register that 2577 // we can use. 2578 RegsForValue Regs = 2579 GetRegistersForValue(ConstraintCode, ConstraintVTs[i], 2580 true, UsesInputRegister, 2581 OutputRegs, InputRegs); 2582 if (Regs.Regs.empty()) { 2583 cerr << "Couldn't allocate output reg for contraint '" 2584 << ConstraintCode << "'!\n"; 2585 exit(1); 2586 } 2587 2588 if (!Constraints[i].isIndirectOutput) { 2589 assert(RetValRegs.Regs.empty() && 2590 "Cannot have multiple output constraints yet!"); 2591 assert(I.getType() != Type::VoidTy && "Bad inline asm!"); 2592 RetValRegs = Regs; 2593 } else { 2594 IndirectStoresToEmit.push_back(std::make_pair(Regs, 2595 I.getOperand(OpNum))); 2596 OpNum++; // Consumes a call operand. 2597 } 2598 2599 // Add information to the INLINEASM node to know that this register is 2600 // set. 2601 Regs.AddInlineAsmOperands(2 /*REGDEF*/, DAG, AsmNodeOperands); 2602 break; 2603 } 2604 case InlineAsm::isInput: { 2605 SDOperand InOperandVal = getValue(I.getOperand(OpNum)); 2606 OpNum++; // Consumes a call operand. 2607 2608 if (isdigit(ConstraintCode[0])) { // Matching constraint? 2609 // If this is required to match an output register we have already set, 2610 // just use its register. 2611 unsigned OperandNo = atoi(ConstraintCode.c_str()); 2612 2613 // Scan until we find the definition we already emitted of this operand. 2614 // When we find it, create a RegsForValue operand. 2615 unsigned CurOp = 2; // The first operand. 2616 for (; OperandNo; --OperandNo) { 2617 // Advance to the next operand. 2618 unsigned NumOps = 2619 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue(); 2620 assert(((NumOps & 7) == 2 /*REGDEF*/ || 2621 (NumOps & 7) == 4 /*MEM*/) && 2622 "Skipped past definitions?"); 2623 CurOp += (NumOps>>3)+1; 2624 } 2625 2626 unsigned NumOps = 2627 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue(); 2628 assert((NumOps & 7) == 2 /*REGDEF*/ && 2629 "Skipped past definitions?"); 2630 2631 // Add NumOps>>3 registers to MatchedRegs. 2632 RegsForValue MatchedRegs; 2633 MatchedRegs.ValueVT = InOperandVal.getValueType(); 2634 MatchedRegs.RegVT = AsmNodeOperands[CurOp+1].getValueType(); 2635 for (unsigned i = 0, e = NumOps>>3; i != e; ++i) { 2636 unsigned Reg=cast<RegisterSDNode>(AsmNodeOperands[++CurOp])->getReg(); 2637 MatchedRegs.Regs.push_back(Reg); 2638 } 2639 2640 // Use the produced MatchedRegs object to 2641 MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag, 2642 TLI.getPointerTy()); 2643 MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands); 2644 break; 2645 } 2646 2647 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass; 2648 if (ConstraintCode.size() == 1) // not a physreg name. 2649 CTy = TLI.getConstraintType(ConstraintCode[0]); 2650 2651 if (CTy == TargetLowering::C_Other) { 2652 InOperandVal = TLI.isOperandValidForConstraint(InOperandVal, 2653 ConstraintCode[0], DAG); 2654 if (!InOperandVal.Val) { 2655 cerr << "Invalid operand for inline asm constraint '" 2656 << ConstraintCode << "'!\n"; 2657 exit(1); 2658 } 2659 2660 // Add information to the INLINEASM node to know about this input. 2661 unsigned ResOpType = 3 /*IMM*/ | (1 << 3); 2662 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32)); 2663 AsmNodeOperands.push_back(InOperandVal); 2664 break; 2665 } else if (CTy == TargetLowering::C_Memory) { 2666 // Memory input. 2667 2668 // Check that the operand isn't a float. 2669 if (!MVT::isInteger(InOperandVal.getValueType())) 2670 assert(0 && "MATCH FAIL!"); 2671 2672 // Extend/truncate to the right pointer type if needed. 2673 MVT::ValueType PtrType = TLI.getPointerTy(); 2674 if (InOperandVal.getValueType() < PtrType) 2675 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal); 2676 else if (InOperandVal.getValueType() > PtrType) 2677 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal); 2678 2679 // Add information to the INLINEASM node to know about this input. 2680 unsigned ResOpType = 4/*MEM*/ | (1 << 3); 2681 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32)); 2682 AsmNodeOperands.push_back(InOperandVal); 2683 break; 2684 } 2685 2686 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!"); 2687 2688 // Copy the input into the appropriate registers. 2689 RegsForValue InRegs = 2690 GetRegistersForValue(ConstraintCode, ConstraintVTs[i], 2691 false, true, OutputRegs, InputRegs); 2692 // FIXME: should be match fail. 2693 assert(!InRegs.Regs.empty() && "Couldn't allocate input reg!"); 2694 2695 InRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag, TLI.getPointerTy()); 2696 2697 InRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG, AsmNodeOperands); 2698 break; 2699 } 2700 case InlineAsm::isClobber: { 2701 RegsForValue ClobberedRegs = 2702 GetRegistersForValue(ConstraintCode, MVT::Other, false, false, 2703 OutputRegs, InputRegs); 2704 // Add the clobbered value to the operand list, so that the register 2705 // allocator is aware that the physreg got clobbered. 2706 if (!ClobberedRegs.Regs.empty()) 2707 ClobberedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG, AsmNodeOperands); 2708 break; 2709 } 2710 } 2711 } 2712 2713 // Finish up input operands. 2714 AsmNodeOperands[0] = Chain; 2715 if (Flag.Val) AsmNodeOperands.push_back(Flag); 2716 2717 Chain = DAG.getNode(ISD::INLINEASM, 2718 DAG.getNodeValueTypes(MVT::Other, MVT::Flag), 2, 2719 &AsmNodeOperands[0], AsmNodeOperands.size()); 2720 Flag = Chain.getValue(1); 2721 2722 // If this asm returns a register value, copy the result from that register 2723 // and set it as the value of the call. 2724 if (!RetValRegs.Regs.empty()) 2725 setValue(&I, RetValRegs.getCopyFromRegs(DAG, Chain, Flag)); 2726 2727 std::vector<std::pair<SDOperand, Value*> > StoresToEmit; 2728 2729 // Process indirect outputs, first output all of the flagged copies out of 2730 // physregs. 2731 for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) { 2732 RegsForValue &OutRegs = IndirectStoresToEmit[i].first; 2733 Value *Ptr = IndirectStoresToEmit[i].second; 2734 SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, Flag); 2735 StoresToEmit.push_back(std::make_pair(OutVal, Ptr)); 2736 } 2737 2738 // Emit the non-flagged stores from the physregs. 2739 SmallVector<SDOperand, 8> OutChains; 2740 for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i) 2741 OutChains.push_back(DAG.getStore(Chain, StoresToEmit[i].first, 2742 getValue(StoresToEmit[i].second), 2743 StoresToEmit[i].second, 0)); 2744 if (!OutChains.empty()) 2745 Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, 2746 &OutChains[0], OutChains.size()); 2747 DAG.setRoot(Chain); 2748} 2749 2750 2751void SelectionDAGLowering::visitMalloc(MallocInst &I) { 2752 SDOperand Src = getValue(I.getOperand(0)); 2753 2754 MVT::ValueType IntPtr = TLI.getPointerTy(); 2755 2756 if (IntPtr < Src.getValueType()) 2757 Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src); 2758 else if (IntPtr > Src.getValueType()) 2759 Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src); 2760 2761 // Scale the source by the type size. 2762 uint64_t ElementSize = TD->getTypeSize(I.getType()->getElementType()); 2763 Src = DAG.getNode(ISD::MUL, Src.getValueType(), 2764 Src, getIntPtrConstant(ElementSize)); 2765 2766 TargetLowering::ArgListTy Args; 2767 TargetLowering::ArgListEntry Entry; 2768 Entry.Node = Src; 2769 Entry.Ty = TLI.getTargetData()->getIntPtrType(); 2770 Entry.isSigned = false; 2771 Entry.isInReg = false; 2772 Entry.isSRet = false; 2773 Args.push_back(Entry); 2774 2775 std::pair<SDOperand,SDOperand> Result = 2776 TLI.LowerCallTo(getRoot(), I.getType(), false, false, CallingConv::C, true, 2777 DAG.getExternalSymbol("malloc", IntPtr), 2778 Args, DAG); 2779 setValue(&I, Result.first); // Pointers always fit in registers 2780 DAG.setRoot(Result.second); 2781} 2782 2783void SelectionDAGLowering::visitFree(FreeInst &I) { 2784 TargetLowering::ArgListTy Args; 2785 TargetLowering::ArgListEntry Entry; 2786 Entry.Node = getValue(I.getOperand(0)); 2787 Entry.Ty = TLI.getTargetData()->getIntPtrType(); 2788 Entry.isSigned = false; 2789 Entry.isInReg = false; 2790 Entry.isSRet = false; 2791 Args.push_back(Entry); 2792 MVT::ValueType IntPtr = TLI.getPointerTy(); 2793 std::pair<SDOperand,SDOperand> Result = 2794 TLI.LowerCallTo(getRoot(), Type::VoidTy, false, false, CallingConv::C, true, 2795 DAG.getExternalSymbol("free", IntPtr), Args, DAG); 2796 DAG.setRoot(Result.second); 2797} 2798 2799// InsertAtEndOfBasicBlock - This method should be implemented by targets that 2800// mark instructions with the 'usesCustomDAGSchedInserter' flag. These 2801// instructions are special in various ways, which require special support to 2802// insert. The specified MachineInstr is created but not inserted into any 2803// basic blocks, and the scheduler passes ownership of it to this method. 2804MachineBasicBlock *TargetLowering::InsertAtEndOfBasicBlock(MachineInstr *MI, 2805 MachineBasicBlock *MBB) { 2806 cerr << "If a target marks an instruction with " 2807 << "'usesCustomDAGSchedInserter', it must implement " 2808 << "TargetLowering::InsertAtEndOfBasicBlock!\n"; 2809 abort(); 2810 return 0; 2811} 2812 2813void SelectionDAGLowering::visitVAStart(CallInst &I) { 2814 DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(), 2815 getValue(I.getOperand(1)), 2816 DAG.getSrcValue(I.getOperand(1)))); 2817} 2818 2819void SelectionDAGLowering::visitVAArg(VAArgInst &I) { 2820 SDOperand V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(), 2821 getValue(I.getOperand(0)), 2822 DAG.getSrcValue(I.getOperand(0))); 2823 setValue(&I, V); 2824 DAG.setRoot(V.getValue(1)); 2825} 2826 2827void SelectionDAGLowering::visitVAEnd(CallInst &I) { 2828 DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(), 2829 getValue(I.getOperand(1)), 2830 DAG.getSrcValue(I.getOperand(1)))); 2831} 2832 2833void SelectionDAGLowering::visitVACopy(CallInst &I) { 2834 DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(), 2835 getValue(I.getOperand(1)), 2836 getValue(I.getOperand(2)), 2837 DAG.getSrcValue(I.getOperand(1)), 2838 DAG.getSrcValue(I.getOperand(2)))); 2839} 2840 2841/// ExpandScalarFormalArgs - Recursively expand the formal_argument node, either 2842/// bit_convert it or join a pair of them with a BUILD_PAIR when appropriate. 2843static SDOperand ExpandScalarFormalArgs(MVT::ValueType VT, SDNode *Arg, 2844 unsigned &i, SelectionDAG &DAG, 2845 TargetLowering &TLI) { 2846 if (TLI.getTypeAction(VT) != TargetLowering::Expand) 2847 return SDOperand(Arg, i++); 2848 2849 MVT::ValueType EVT = TLI.getTypeToTransformTo(VT); 2850 unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT); 2851 if (NumVals == 1) { 2852 return DAG.getNode(ISD::BIT_CONVERT, VT, 2853 ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI)); 2854 } else if (NumVals == 2) { 2855 SDOperand Lo = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI); 2856 SDOperand Hi = ExpandScalarFormalArgs(EVT, Arg, i, DAG, TLI); 2857 if (!TLI.isLittleEndian()) 2858 std::swap(Lo, Hi); 2859 return DAG.getNode(ISD::BUILD_PAIR, VT, Lo, Hi); 2860 } else { 2861 // Value scalarized into many values. Unimp for now. 2862 assert(0 && "Cannot expand i64 -> i16 yet!"); 2863 } 2864 return SDOperand(); 2865} 2866 2867/// TargetLowering::LowerArguments - This is the default LowerArguments 2868/// implementation, which just inserts a FORMAL_ARGUMENTS node. FIXME: When all 2869/// targets are migrated to using FORMAL_ARGUMENTS, this hook should be 2870/// integrated into SDISel. 2871std::vector<SDOperand> 2872TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) { 2873 const FunctionType *FTy = F.getFunctionType(); 2874 // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node. 2875 std::vector<SDOperand> Ops; 2876 Ops.push_back(DAG.getRoot()); 2877 Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy())); 2878 Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy())); 2879 2880 // Add one result value for each formal argument. 2881 std::vector<MVT::ValueType> RetVals; 2882 unsigned j = 1; 2883 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); 2884 I != E; ++I, ++j) { 2885 MVT::ValueType VT = getValueType(I->getType()); 2886 bool isInReg = FTy->paramHasAttr(j, FunctionType::InRegAttribute); 2887 bool isSRet = FTy->paramHasAttr(j, FunctionType::StructRetAttribute); 2888 unsigned Flags = (isInReg << 1) | (isSRet << 2); 2889 2890 switch (getTypeAction(VT)) { 2891 default: assert(0 && "Unknown type action!"); 2892 case Legal: 2893 RetVals.push_back(VT); 2894 Ops.push_back(DAG.getConstant(Flags, MVT::i32)); 2895 break; 2896 case Promote: 2897 RetVals.push_back(getTypeToTransformTo(VT)); 2898 Ops.push_back(DAG.getConstant(Flags, MVT::i32)); 2899 break; 2900 case Expand: 2901 if (VT != MVT::Vector) { 2902 // If this is a large integer, it needs to be broken up into small 2903 // integers. Figure out what the destination type is and how many small 2904 // integers it turns into. 2905 MVT::ValueType NVT = getTypeToExpandTo(VT); 2906 unsigned NumVals = getNumElements(VT); 2907 for (unsigned i = 0; i != NumVals; ++i) { 2908 RetVals.push_back(NVT); 2909 Ops.push_back(DAG.getConstant(Flags, MVT::i32)); 2910 } 2911 } else { 2912 // Otherwise, this is a vector type. We only support legal vectors 2913 // right now. 2914 unsigned NumElems = cast<PackedType>(I->getType())->getNumElements(); 2915 const Type *EltTy = cast<PackedType>(I->getType())->getElementType(); 2916 2917 // Figure out if there is a Packed type corresponding to this Vector 2918 // type. If so, convert to the packed type. 2919 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems); 2920 if (TVT != MVT::Other && isTypeLegal(TVT)) { 2921 RetVals.push_back(TVT); 2922 Ops.push_back(DAG.getConstant(Flags, MVT::i32)); 2923 } else { 2924 assert(0 && "Don't support illegal by-val vector arguments yet!"); 2925 } 2926 } 2927 break; 2928 } 2929 } 2930 2931 RetVals.push_back(MVT::Other); 2932 2933 // Create the node. 2934 SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS, 2935 DAG.getNodeValueTypes(RetVals), RetVals.size(), 2936 &Ops[0], Ops.size()).Val; 2937 2938 DAG.setRoot(SDOperand(Result, Result->getNumValues()-1)); 2939 2940 // Set up the return result vector. 2941 Ops.clear(); 2942 unsigned i = 0; 2943 unsigned Idx = 1; 2944 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; 2945 ++I, ++Idx) { 2946 MVT::ValueType VT = getValueType(I->getType()); 2947 2948 switch (getTypeAction(VT)) { 2949 default: assert(0 && "Unknown type action!"); 2950 case Legal: 2951 Ops.push_back(SDOperand(Result, i++)); 2952 break; 2953 case Promote: { 2954 SDOperand Op(Result, i++); 2955 if (MVT::isInteger(VT)) { 2956 if (FTy->paramHasAttr(Idx, FunctionType::SExtAttribute)) 2957 Op = DAG.getNode(ISD::AssertSext, Op.getValueType(), Op, 2958 DAG.getValueType(VT)); 2959 else if (FTy->paramHasAttr(Idx, FunctionType::ZExtAttribute)) 2960 Op = DAG.getNode(ISD::AssertZext, Op.getValueType(), Op, 2961 DAG.getValueType(VT)); 2962 Op = DAG.getNode(ISD::TRUNCATE, VT, Op); 2963 } else { 2964 assert(MVT::isFloatingPoint(VT) && "Not int or FP?"); 2965 Op = DAG.getNode(ISD::FP_ROUND, VT, Op); 2966 } 2967 Ops.push_back(Op); 2968 break; 2969 } 2970 case Expand: 2971 if (VT != MVT::Vector) { 2972 // If this is a large integer or a floating point node that needs to be 2973 // expanded, it needs to be reassembled from small integers. Figure out 2974 // what the source elt type is and how many small integers it is. 2975 Ops.push_back(ExpandScalarFormalArgs(VT, Result, i, DAG, *this)); 2976 } else { 2977 // Otherwise, this is a vector type. We only support legal vectors 2978 // right now. 2979 const PackedType *PTy = cast<PackedType>(I->getType()); 2980 unsigned NumElems = PTy->getNumElements(); 2981 const Type *EltTy = PTy->getElementType(); 2982 2983 // Figure out if there is a Packed type corresponding to this Vector 2984 // type. If so, convert to the packed type. 2985 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems); 2986 if (TVT != MVT::Other && isTypeLegal(TVT)) { 2987 SDOperand N = SDOperand(Result, i++); 2988 // Handle copies from generic vectors to registers. 2989 N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N, 2990 DAG.getConstant(NumElems, MVT::i32), 2991 DAG.getValueType(getValueType(EltTy))); 2992 Ops.push_back(N); 2993 } else { 2994 assert(0 && "Don't support illegal by-val vector arguments yet!"); 2995 abort(); 2996 } 2997 } 2998 break; 2999 } 3000 } 3001 return Ops; 3002} 3003 3004 3005/// ExpandScalarCallArgs - Recursively expand call argument node by 3006/// bit_converting it or extract a pair of elements from the larger node. 3007static void ExpandScalarCallArgs(MVT::ValueType VT, SDOperand Arg, 3008 unsigned Flags, 3009 SmallVector<SDOperand, 32> &Ops, 3010 SelectionDAG &DAG, 3011 TargetLowering &TLI) { 3012 if (TLI.getTypeAction(VT) != TargetLowering::Expand) { 3013 Ops.push_back(Arg); 3014 Ops.push_back(DAG.getConstant(Flags, MVT::i32)); 3015 return; 3016 } 3017 3018 MVT::ValueType EVT = TLI.getTypeToTransformTo(VT); 3019 unsigned NumVals = MVT::getSizeInBits(VT) / MVT::getSizeInBits(EVT); 3020 if (NumVals == 1) { 3021 Arg = DAG.getNode(ISD::BIT_CONVERT, EVT, Arg); 3022 ExpandScalarCallArgs(EVT, Arg, Flags, Ops, DAG, TLI); 3023 } else if (NumVals == 2) { 3024 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg, 3025 DAG.getConstant(0, TLI.getPointerTy())); 3026 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, EVT, Arg, 3027 DAG.getConstant(1, TLI.getPointerTy())); 3028 if (!TLI.isLittleEndian()) 3029 std::swap(Lo, Hi); 3030 ExpandScalarCallArgs(EVT, Lo, Flags, Ops, DAG, TLI); 3031 ExpandScalarCallArgs(EVT, Hi, Flags, Ops, DAG, TLI); 3032 } else { 3033 // Value scalarized into many values. Unimp for now. 3034 assert(0 && "Cannot expand i64 -> i16 yet!"); 3035 } 3036} 3037 3038/// TargetLowering::LowerCallTo - This is the default LowerCallTo 3039/// implementation, which just inserts an ISD::CALL node, which is later custom 3040/// lowered by the target to something concrete. FIXME: When all targets are 3041/// migrated to using ISD::CALL, this hook should be integrated into SDISel. 3042std::pair<SDOperand, SDOperand> 3043TargetLowering::LowerCallTo(SDOperand Chain, const Type *RetTy, 3044 bool RetTyIsSigned, bool isVarArg, 3045 unsigned CallingConv, bool isTailCall, 3046 SDOperand Callee, 3047 ArgListTy &Args, SelectionDAG &DAG) { 3048 SmallVector<SDOperand, 32> Ops; 3049 Ops.push_back(Chain); // Op#0 - Chain 3050 Ops.push_back(DAG.getConstant(CallingConv, getPointerTy())); // Op#1 - CC 3051 Ops.push_back(DAG.getConstant(isVarArg, getPointerTy())); // Op#2 - VarArg 3052 Ops.push_back(DAG.getConstant(isTailCall, getPointerTy())); // Op#3 - Tail 3053 Ops.push_back(Callee); 3054 3055 // Handle all of the outgoing arguments. 3056 for (unsigned i = 0, e = Args.size(); i != e; ++i) { 3057 MVT::ValueType VT = getValueType(Args[i].Ty); 3058 SDOperand Op = Args[i].Node; 3059 bool isSigned = Args[i].isSigned; 3060 bool isInReg = Args[i].isInReg; 3061 bool isSRet = Args[i].isSRet; 3062 unsigned Flags = (isSRet << 2) | (isInReg << 1) | isSigned; 3063 switch (getTypeAction(VT)) { 3064 default: assert(0 && "Unknown type action!"); 3065 case Legal: 3066 Ops.push_back(Op); 3067 Ops.push_back(DAG.getConstant(Flags, MVT::i32)); 3068 break; 3069 case Promote: 3070 if (MVT::isInteger(VT)) { 3071 unsigned ExtOp = isSigned ? ISD::SIGN_EXTEND : ISD::ZERO_EXTEND; 3072 Op = DAG.getNode(ExtOp, getTypeToTransformTo(VT), Op); 3073 } else { 3074 assert(MVT::isFloatingPoint(VT) && "Not int or FP?"); 3075 Op = DAG.getNode(ISD::FP_EXTEND, getTypeToTransformTo(VT), Op); 3076 } 3077 Ops.push_back(Op); 3078 Ops.push_back(DAG.getConstant(Flags, MVT::i32)); 3079 break; 3080 case Expand: 3081 if (VT != MVT::Vector) { 3082 // If this is a large integer, it needs to be broken down into small 3083 // integers. Figure out what the source elt type is and how many small 3084 // integers it is. 3085 ExpandScalarCallArgs(VT, Op, Flags, Ops, DAG, *this); 3086 } else { 3087 // Otherwise, this is a vector type. We only support legal vectors 3088 // right now. 3089 const PackedType *PTy = cast<PackedType>(Args[i].Ty); 3090 unsigned NumElems = PTy->getNumElements(); 3091 const Type *EltTy = PTy->getElementType(); 3092 3093 // Figure out if there is a Packed type corresponding to this Vector 3094 // type. If so, convert to the packed type. 3095 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems); 3096 if (TVT != MVT::Other && isTypeLegal(TVT)) { 3097 // Insert a VBIT_CONVERT of the MVT::Vector type to the packed type. 3098 Op = DAG.getNode(ISD::VBIT_CONVERT, TVT, Op); 3099 Ops.push_back(Op); 3100 Ops.push_back(DAG.getConstant(Flags, MVT::i32)); 3101 } else { 3102 assert(0 && "Don't support illegal by-val vector call args yet!"); 3103 abort(); 3104 } 3105 } 3106 break; 3107 } 3108 } 3109 3110 // Figure out the result value types. 3111 SmallVector<MVT::ValueType, 4> RetTys; 3112 3113 if (RetTy != Type::VoidTy) { 3114 MVT::ValueType VT = getValueType(RetTy); 3115 switch (getTypeAction(VT)) { 3116 default: assert(0 && "Unknown type action!"); 3117 case Legal: 3118 RetTys.push_back(VT); 3119 break; 3120 case Promote: 3121 RetTys.push_back(getTypeToTransformTo(VT)); 3122 break; 3123 case Expand: 3124 if (VT != MVT::Vector) { 3125 // If this is a large integer, it needs to be reassembled from small 3126 // integers. Figure out what the source elt type is and how many small 3127 // integers it is. 3128 MVT::ValueType NVT = getTypeToExpandTo(VT); 3129 unsigned NumVals = getNumElements(VT); 3130 for (unsigned i = 0; i != NumVals; ++i) 3131 RetTys.push_back(NVT); 3132 } else { 3133 // Otherwise, this is a vector type. We only support legal vectors 3134 // right now. 3135 const PackedType *PTy = cast<PackedType>(RetTy); 3136 unsigned NumElems = PTy->getNumElements(); 3137 const Type *EltTy = PTy->getElementType(); 3138 3139 // Figure out if there is a Packed type corresponding to this Vector 3140 // type. If so, convert to the packed type. 3141 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems); 3142 if (TVT != MVT::Other && isTypeLegal(TVT)) { 3143 RetTys.push_back(TVT); 3144 } else { 3145 assert(0 && "Don't support illegal by-val vector call results yet!"); 3146 abort(); 3147 } 3148 } 3149 } 3150 } 3151 3152 RetTys.push_back(MVT::Other); // Always has a chain. 3153 3154 // Finally, create the CALL node. 3155 SDOperand Res = DAG.getNode(ISD::CALL, 3156 DAG.getVTList(&RetTys[0], RetTys.size()), 3157 &Ops[0], Ops.size()); 3158 3159 // This returns a pair of operands. The first element is the 3160 // return value for the function (if RetTy is not VoidTy). The second 3161 // element is the outgoing token chain. 3162 SDOperand ResVal; 3163 if (RetTys.size() != 1) { 3164 MVT::ValueType VT = getValueType(RetTy); 3165 if (RetTys.size() == 2) { 3166 ResVal = Res; 3167 3168 // If this value was promoted, truncate it down. 3169 if (ResVal.getValueType() != VT) { 3170 if (VT == MVT::Vector) { 3171 // Insert a VBITCONVERT to convert from the packed result type to the 3172 // MVT::Vector type. 3173 unsigned NumElems = cast<PackedType>(RetTy)->getNumElements(); 3174 const Type *EltTy = cast<PackedType>(RetTy)->getElementType(); 3175 3176 // Figure out if there is a Packed type corresponding to this Vector 3177 // type. If so, convert to the packed type. 3178 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems); 3179 if (TVT != MVT::Other && isTypeLegal(TVT)) { 3180 // Insert a VBIT_CONVERT of the FORMAL_ARGUMENTS to a 3181 // "N x PTyElementVT" MVT::Vector type. 3182 ResVal = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, ResVal, 3183 DAG.getConstant(NumElems, MVT::i32), 3184 DAG.getValueType(getValueType(EltTy))); 3185 } else { 3186 abort(); 3187 } 3188 } else if (MVT::isInteger(VT)) { 3189 unsigned AssertOp = ISD::AssertSext; 3190 if (!RetTyIsSigned) 3191 AssertOp = ISD::AssertZext; 3192 ResVal = DAG.getNode(AssertOp, ResVal.getValueType(), ResVal, 3193 DAG.getValueType(VT)); 3194 ResVal = DAG.getNode(ISD::TRUNCATE, VT, ResVal); 3195 } else { 3196 assert(MVT::isFloatingPoint(VT)); 3197 if (getTypeAction(VT) == Expand) 3198 ResVal = DAG.getNode(ISD::BIT_CONVERT, VT, ResVal); 3199 else 3200 ResVal = DAG.getNode(ISD::FP_ROUND, VT, ResVal); 3201 } 3202 } 3203 } else if (RetTys.size() == 3) { 3204 ResVal = DAG.getNode(ISD::BUILD_PAIR, VT, 3205 Res.getValue(0), Res.getValue(1)); 3206 3207 } else { 3208 assert(0 && "Case not handled yet!"); 3209 } 3210 } 3211 3212 return std::make_pair(ResVal, Res.getValue(Res.Val->getNumValues()-1)); 3213} 3214 3215SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) { 3216 assert(0 && "LowerOperation not implemented for this target!"); 3217 abort(); 3218 return SDOperand(); 3219} 3220 3221SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op, 3222 SelectionDAG &DAG) { 3223 assert(0 && "CustomPromoteOperation not implemented for this target!"); 3224 abort(); 3225 return SDOperand(); 3226} 3227 3228/// getMemsetValue - Vectorized representation of the memset value 3229/// operand. 3230static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT, 3231 SelectionDAG &DAG) { 3232 MVT::ValueType CurVT = VT; 3233 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) { 3234 uint64_t Val = C->getValue() & 255; 3235 unsigned Shift = 8; 3236 while (CurVT != MVT::i8) { 3237 Val = (Val << Shift) | Val; 3238 Shift <<= 1; 3239 CurVT = (MVT::ValueType)((unsigned)CurVT - 1); 3240 } 3241 return DAG.getConstant(Val, VT); 3242 } else { 3243 Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value); 3244 unsigned Shift = 8; 3245 while (CurVT != MVT::i8) { 3246 Value = 3247 DAG.getNode(ISD::OR, VT, 3248 DAG.getNode(ISD::SHL, VT, Value, 3249 DAG.getConstant(Shift, MVT::i8)), Value); 3250 Shift <<= 1; 3251 CurVT = (MVT::ValueType)((unsigned)CurVT - 1); 3252 } 3253 3254 return Value; 3255 } 3256} 3257 3258/// getMemsetStringVal - Similar to getMemsetValue. Except this is only 3259/// used when a memcpy is turned into a memset when the source is a constant 3260/// string ptr. 3261static SDOperand getMemsetStringVal(MVT::ValueType VT, 3262 SelectionDAG &DAG, TargetLowering &TLI, 3263 std::string &Str, unsigned Offset) { 3264 uint64_t Val = 0; 3265 unsigned MSB = getSizeInBits(VT) / 8; 3266 if (TLI.isLittleEndian()) 3267 Offset = Offset + MSB - 1; 3268 for (unsigned i = 0; i != MSB; ++i) { 3269 Val = (Val << 8) | (unsigned char)Str[Offset]; 3270 Offset += TLI.isLittleEndian() ? -1 : 1; 3271 } 3272 return DAG.getConstant(Val, VT); 3273} 3274 3275/// getMemBasePlusOffset - Returns base and offset node for the 3276static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset, 3277 SelectionDAG &DAG, TargetLowering &TLI) { 3278 MVT::ValueType VT = Base.getValueType(); 3279 return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT)); 3280} 3281 3282/// MeetsMaxMemopRequirement - Determines if the number of memory ops required 3283/// to replace the memset / memcpy is below the threshold. It also returns the 3284/// types of the sequence of memory ops to perform memset / memcpy. 3285static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps, 3286 unsigned Limit, uint64_t Size, 3287 unsigned Align, TargetLowering &TLI) { 3288 MVT::ValueType VT; 3289 3290 if (TLI.allowsUnalignedMemoryAccesses()) { 3291 VT = MVT::i64; 3292 } else { 3293 switch (Align & 7) { 3294 case 0: 3295 VT = MVT::i64; 3296 break; 3297 case 4: 3298 VT = MVT::i32; 3299 break; 3300 case 2: 3301 VT = MVT::i16; 3302 break; 3303 default: 3304 VT = MVT::i8; 3305 break; 3306 } 3307 } 3308 3309 MVT::ValueType LVT = MVT::i64; 3310 while (!TLI.isTypeLegal(LVT)) 3311 LVT = (MVT::ValueType)((unsigned)LVT - 1); 3312 assert(MVT::isInteger(LVT)); 3313 3314 if (VT > LVT) 3315 VT = LVT; 3316 3317 unsigned NumMemOps = 0; 3318 while (Size != 0) { 3319 unsigned VTSize = getSizeInBits(VT) / 8; 3320 while (VTSize > Size) { 3321 VT = (MVT::ValueType)((unsigned)VT - 1); 3322 VTSize >>= 1; 3323 } 3324 assert(MVT::isInteger(VT)); 3325 3326 if (++NumMemOps > Limit) 3327 return false; 3328 MemOps.push_back(VT); 3329 Size -= VTSize; 3330 } 3331 3332 return true; 3333} 3334 3335void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) { 3336 SDOperand Op1 = getValue(I.getOperand(1)); 3337 SDOperand Op2 = getValue(I.getOperand(2)); 3338 SDOperand Op3 = getValue(I.getOperand(3)); 3339 SDOperand Op4 = getValue(I.getOperand(4)); 3340 unsigned Align = (unsigned)cast<ConstantSDNode>(Op4)->getValue(); 3341 if (Align == 0) Align = 1; 3342 3343 if (ConstantSDNode *Size = dyn_cast<ConstantSDNode>(Op3)) { 3344 std::vector<MVT::ValueType> MemOps; 3345 3346 // Expand memset / memcpy to a series of load / store ops 3347 // if the size operand falls below a certain threshold. 3348 SmallVector<SDOperand, 8> OutChains; 3349 switch (Op) { 3350 default: break; // Do nothing for now. 3351 case ISD::MEMSET: { 3352 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(), 3353 Size->getValue(), Align, TLI)) { 3354 unsigned NumMemOps = MemOps.size(); 3355 unsigned Offset = 0; 3356 for (unsigned i = 0; i < NumMemOps; i++) { 3357 MVT::ValueType VT = MemOps[i]; 3358 unsigned VTSize = getSizeInBits(VT) / 8; 3359 SDOperand Value = getMemsetValue(Op2, VT, DAG); 3360 SDOperand Store = DAG.getStore(getRoot(), Value, 3361 getMemBasePlusOffset(Op1, Offset, DAG, TLI), 3362 I.getOperand(1), Offset); 3363 OutChains.push_back(Store); 3364 Offset += VTSize; 3365 } 3366 } 3367 break; 3368 } 3369 case ISD::MEMCPY: { 3370 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemcpy(), 3371 Size->getValue(), Align, TLI)) { 3372 unsigned NumMemOps = MemOps.size(); 3373 unsigned SrcOff = 0, DstOff = 0, SrcDelta = 0; 3374 GlobalAddressSDNode *G = NULL; 3375 std::string Str; 3376 bool CopyFromStr = false; 3377 3378 if (Op2.getOpcode() == ISD::GlobalAddress) 3379 G = cast<GlobalAddressSDNode>(Op2); 3380 else if (Op2.getOpcode() == ISD::ADD && 3381 Op2.getOperand(0).getOpcode() == ISD::GlobalAddress && 3382 Op2.getOperand(1).getOpcode() == ISD::Constant) { 3383 G = cast<GlobalAddressSDNode>(Op2.getOperand(0)); 3384 SrcDelta = cast<ConstantSDNode>(Op2.getOperand(1))->getValue(); 3385 } 3386 if (G) { 3387 GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal()); 3388 if (GV && GV->isConstant()) { 3389 Str = GV->getStringValue(false); 3390 if (!Str.empty()) { 3391 CopyFromStr = true; 3392 SrcOff += SrcDelta; 3393 } 3394 } 3395 } 3396 3397 for (unsigned i = 0; i < NumMemOps; i++) { 3398 MVT::ValueType VT = MemOps[i]; 3399 unsigned VTSize = getSizeInBits(VT) / 8; 3400 SDOperand Value, Chain, Store; 3401 3402 if (CopyFromStr) { 3403 Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff); 3404 Chain = getRoot(); 3405 Store = 3406 DAG.getStore(Chain, Value, 3407 getMemBasePlusOffset(Op1, DstOff, DAG, TLI), 3408 I.getOperand(1), DstOff); 3409 } else { 3410 Value = DAG.getLoad(VT, getRoot(), 3411 getMemBasePlusOffset(Op2, SrcOff, DAG, TLI), 3412 I.getOperand(2), SrcOff); 3413 Chain = Value.getValue(1); 3414 Store = 3415 DAG.getStore(Chain, Value, 3416 getMemBasePlusOffset(Op1, DstOff, DAG, TLI), 3417 I.getOperand(1), DstOff); 3418 } 3419 OutChains.push_back(Store); 3420 SrcOff += VTSize; 3421 DstOff += VTSize; 3422 } 3423 } 3424 break; 3425 } 3426 } 3427 3428 if (!OutChains.empty()) { 3429 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, 3430 &OutChains[0], OutChains.size())); 3431 return; 3432 } 3433 } 3434 3435 DAG.setRoot(DAG.getNode(Op, MVT::Other, getRoot(), Op1, Op2, Op3, Op4)); 3436} 3437 3438//===----------------------------------------------------------------------===// 3439// SelectionDAGISel code 3440//===----------------------------------------------------------------------===// 3441 3442unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) { 3443 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT)); 3444} 3445 3446void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { 3447 // FIXME: we only modify the CFG to split critical edges. This 3448 // updates dom and loop info. 3449 AU.addRequired<AliasAnalysis>(); 3450} 3451 3452 3453/// OptimizeNoopCopyExpression - We have determined that the specified cast 3454/// instruction is a noop copy (e.g. it's casting from one pointer type to 3455/// another, int->uint, or int->sbyte on PPC. 3456/// 3457/// Return true if any changes are made. 3458static bool OptimizeNoopCopyExpression(CastInst *CI) { 3459 BasicBlock *DefBB = CI->getParent(); 3460 3461 /// InsertedCasts - Only insert a cast in each block once. 3462 std::map<BasicBlock*, CastInst*> InsertedCasts; 3463 3464 bool MadeChange = false; 3465 for (Value::use_iterator UI = CI->use_begin(), E = CI->use_end(); 3466 UI != E; ) { 3467 Use &TheUse = UI.getUse(); 3468 Instruction *User = cast<Instruction>(*UI); 3469 3470 // Figure out which BB this cast is used in. For PHI's this is the 3471 // appropriate predecessor block. 3472 BasicBlock *UserBB = User->getParent(); 3473 if (PHINode *PN = dyn_cast<PHINode>(User)) { 3474 unsigned OpVal = UI.getOperandNo()/2; 3475 UserBB = PN->getIncomingBlock(OpVal); 3476 } 3477 3478 // Preincrement use iterator so we don't invalidate it. 3479 ++UI; 3480 3481 // If this user is in the same block as the cast, don't change the cast. 3482 if (UserBB == DefBB) continue; 3483 3484 // If we have already inserted a cast into this block, use it. 3485 CastInst *&InsertedCast = InsertedCasts[UserBB]; 3486 3487 if (!InsertedCast) { 3488 BasicBlock::iterator InsertPt = UserBB->begin(); 3489 while (isa<PHINode>(InsertPt)) ++InsertPt; 3490 3491 InsertedCast = 3492 CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(), "", 3493 InsertPt); 3494 MadeChange = true; 3495 } 3496 3497 // Replace a use of the cast with a use of the new casat. 3498 TheUse = InsertedCast; 3499 } 3500 3501 // If we removed all uses, nuke the cast. 3502 if (CI->use_empty()) 3503 CI->eraseFromParent(); 3504 3505 return MadeChange; 3506} 3507 3508/// InsertGEPComputeCode - Insert code into BB to compute Ptr+PtrOffset, 3509/// casting to the type of GEPI. 3510static Instruction *InsertGEPComputeCode(Instruction *&V, BasicBlock *BB, 3511 Instruction *GEPI, Value *Ptr, 3512 Value *PtrOffset) { 3513 if (V) return V; // Already computed. 3514 3515 // Figure out the insertion point 3516 BasicBlock::iterator InsertPt; 3517 if (BB == GEPI->getParent()) { 3518 // If GEP is already inserted into BB, insert right after the GEP. 3519 InsertPt = GEPI; 3520 ++InsertPt; 3521 } else { 3522 // Otherwise, insert at the top of BB, after any PHI nodes 3523 InsertPt = BB->begin(); 3524 while (isa<PHINode>(InsertPt)) ++InsertPt; 3525 } 3526 3527 // If Ptr is itself a cast, but in some other BB, emit a copy of the cast into 3528 // BB so that there is only one value live across basic blocks (the cast 3529 // operand). 3530 if (CastInst *CI = dyn_cast<CastInst>(Ptr)) 3531 if (CI->getParent() != BB && isa<PointerType>(CI->getOperand(0)->getType())) 3532 Ptr = CastInst::create(CI->getOpcode(), CI->getOperand(0), CI->getType(), 3533 "", InsertPt); 3534 3535 // Add the offset, cast it to the right type. 3536 Ptr = BinaryOperator::createAdd(Ptr, PtrOffset, "", InsertPt); 3537 // Ptr is an integer type, GEPI is pointer type ==> IntToPtr 3538 return V = CastInst::create(Instruction::IntToPtr, Ptr, GEPI->getType(), 3539 "", InsertPt); 3540} 3541 3542/// ReplaceUsesOfGEPInst - Replace all uses of RepPtr with inserted code to 3543/// compute its value. The RepPtr value can be computed with Ptr+PtrOffset. One 3544/// trivial way of doing this would be to evaluate Ptr+PtrOffset in RepPtr's 3545/// block, then ReplaceAllUsesWith'ing everything. However, we would prefer to 3546/// sink PtrOffset into user blocks where doing so will likely allow us to fold 3547/// the constant add into a load or store instruction. Additionally, if a user 3548/// is a pointer-pointer cast, we look through it to find its users. 3549static void ReplaceUsesOfGEPInst(Instruction *RepPtr, Value *Ptr, 3550 Constant *PtrOffset, BasicBlock *DefBB, 3551 GetElementPtrInst *GEPI, 3552 std::map<BasicBlock*,Instruction*> &InsertedExprs) { 3553 while (!RepPtr->use_empty()) { 3554 Instruction *User = cast<Instruction>(RepPtr->use_back()); 3555 3556 // If the user is a Pointer-Pointer cast, recurse. Only BitCast can be 3557 // used for a Pointer-Pointer cast. 3558 if (isa<BitCastInst>(User)) { 3559 ReplaceUsesOfGEPInst(User, Ptr, PtrOffset, DefBB, GEPI, InsertedExprs); 3560 3561 // Drop the use of RepPtr. The cast is dead. Don't delete it now, else we 3562 // could invalidate an iterator. 3563 User->setOperand(0, UndefValue::get(RepPtr->getType())); 3564 continue; 3565 } 3566 3567 // If this is a load of the pointer, or a store through the pointer, emit 3568 // the increment into the load/store block. 3569 Instruction *NewVal; 3570 if (isa<LoadInst>(User) || 3571 (isa<StoreInst>(User) && User->getOperand(0) != RepPtr)) { 3572 NewVal = InsertGEPComputeCode(InsertedExprs[User->getParent()], 3573 User->getParent(), GEPI, 3574 Ptr, PtrOffset); 3575 } else { 3576 // If this use is not foldable into the addressing mode, use a version 3577 // emitted in the GEP block. 3578 NewVal = InsertGEPComputeCode(InsertedExprs[DefBB], DefBB, GEPI, 3579 Ptr, PtrOffset); 3580 } 3581 3582 if (GEPI->getType() != RepPtr->getType()) { 3583 BasicBlock::iterator IP = NewVal; 3584 ++IP; 3585 // NewVal must be a GEP which must be pointer type, so BitCast 3586 NewVal = new BitCastInst(NewVal, RepPtr->getType(), "", IP); 3587 } 3588 User->replaceUsesOfWith(RepPtr, NewVal); 3589 } 3590} 3591 3592 3593/// OptimizeGEPExpression - Since we are doing basic-block-at-a-time instruction 3594/// selection, we want to be a bit careful about some things. In particular, if 3595/// we have a GEP instruction that is used in a different block than it is 3596/// defined, the addressing expression of the GEP cannot be folded into loads or 3597/// stores that use it. In this case, decompose the GEP and move constant 3598/// indices into blocks that use it. 3599static bool OptimizeGEPExpression(GetElementPtrInst *GEPI, 3600 const TargetData *TD) { 3601 // If this GEP is only used inside the block it is defined in, there is no 3602 // need to rewrite it. 3603 bool isUsedOutsideDefBB = false; 3604 BasicBlock *DefBB = GEPI->getParent(); 3605 for (Value::use_iterator UI = GEPI->use_begin(), E = GEPI->use_end(); 3606 UI != E; ++UI) { 3607 if (cast<Instruction>(*UI)->getParent() != DefBB) { 3608 isUsedOutsideDefBB = true; 3609 break; 3610 } 3611 } 3612 if (!isUsedOutsideDefBB) return false; 3613 3614 // If this GEP has no non-zero constant indices, there is nothing we can do, 3615 // ignore it. 3616 bool hasConstantIndex = false; 3617 bool hasVariableIndex = false; 3618 for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1, 3619 E = GEPI->op_end(); OI != E; ++OI) { 3620 if (ConstantInt *CI = dyn_cast<ConstantInt>(*OI)) { 3621 if (CI->getZExtValue()) { 3622 hasConstantIndex = true; 3623 break; 3624 } 3625 } else { 3626 hasVariableIndex = true; 3627 } 3628 } 3629 3630 // If this is a "GEP X, 0, 0, 0", turn this into a cast. 3631 if (!hasConstantIndex && !hasVariableIndex) { 3632 /// The GEP operand must be a pointer, so must its result -> BitCast 3633 Value *NC = new BitCastInst(GEPI->getOperand(0), GEPI->getType(), 3634 GEPI->getName(), GEPI); 3635 GEPI->replaceAllUsesWith(NC); 3636 GEPI->eraseFromParent(); 3637 return true; 3638 } 3639 3640 // If this is a GEP &Alloca, 0, 0, forward subst the frame index into uses. 3641 if (!hasConstantIndex && !isa<AllocaInst>(GEPI->getOperand(0))) 3642 return false; 3643 3644 // Otherwise, decompose the GEP instruction into multiplies and adds. Sum the 3645 // constant offset (which we now know is non-zero) and deal with it later. 3646 uint64_t ConstantOffset = 0; 3647 const Type *UIntPtrTy = TD->getIntPtrType(); 3648 Value *Ptr = new PtrToIntInst(GEPI->getOperand(0), UIntPtrTy, "", GEPI); 3649 const Type *Ty = GEPI->getOperand(0)->getType(); 3650 3651 for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1, 3652 E = GEPI->op_end(); OI != E; ++OI) { 3653 Value *Idx = *OI; 3654 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 3655 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue(); 3656 if (Field) 3657 ConstantOffset += TD->getStructLayout(StTy)->MemberOffsets[Field]; 3658 Ty = StTy->getElementType(Field); 3659 } else { 3660 Ty = cast<SequentialType>(Ty)->getElementType(); 3661 3662 // Handle constant subscripts. 3663 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 3664 if (CI->getZExtValue() == 0) continue; 3665 ConstantOffset += (int64_t)TD->getTypeSize(Ty)*CI->getSExtValue(); 3666 continue; 3667 } 3668 3669 // Ptr = Ptr + Idx * ElementSize; 3670 3671 // Cast Idx to UIntPtrTy if needed. 3672 Idx = CastInst::createIntegerCast(Idx, UIntPtrTy, true/*SExt*/, "", GEPI); 3673 3674 uint64_t ElementSize = TD->getTypeSize(Ty); 3675 // Mask off bits that should not be set. 3676 ElementSize &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits()); 3677 Constant *SizeCst = ConstantInt::get(UIntPtrTy, ElementSize); 3678 3679 // Multiply by the element size and add to the base. 3680 Idx = BinaryOperator::createMul(Idx, SizeCst, "", GEPI); 3681 Ptr = BinaryOperator::createAdd(Ptr, Idx, "", GEPI); 3682 } 3683 } 3684 3685 // Make sure that the offset fits in uintptr_t. 3686 ConstantOffset &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits()); 3687 Constant *PtrOffset = ConstantInt::get(UIntPtrTy, ConstantOffset); 3688 3689 // Okay, we have now emitted all of the variable index parts to the BB that 3690 // the GEP is defined in. Loop over all of the using instructions, inserting 3691 // an "add Ptr, ConstantOffset" into each block that uses it and update the 3692 // instruction to use the newly computed value, making GEPI dead. When the 3693 // user is a load or store instruction address, we emit the add into the user 3694 // block, otherwise we use a canonical version right next to the gep (these 3695 // won't be foldable as addresses, so we might as well share the computation). 3696 3697 std::map<BasicBlock*,Instruction*> InsertedExprs; 3698 ReplaceUsesOfGEPInst(GEPI, Ptr, PtrOffset, DefBB, GEPI, InsertedExprs); 3699 3700 // Finally, the GEP is dead, remove it. 3701 GEPI->eraseFromParent(); 3702 3703 return true; 3704} 3705 3706 3707/// SplitEdgeNicely - Split the critical edge from TI to it's specified 3708/// successor if it will improve codegen. We only do this if the successor has 3709/// phi nodes (otherwise critical edges are ok). If there is already another 3710/// predecessor of the succ that is empty (and thus has no phi nodes), use it 3711/// instead of introducing a new block. 3712static void SplitEdgeNicely(TerminatorInst *TI, unsigned SuccNum, Pass *P) { 3713 BasicBlock *TIBB = TI->getParent(); 3714 BasicBlock *Dest = TI->getSuccessor(SuccNum); 3715 assert(isa<PHINode>(Dest->begin()) && 3716 "This should only be called if Dest has a PHI!"); 3717 3718 /// TIPHIValues - This array is lazily computed to determine the values of 3719 /// PHIs in Dest that TI would provide. 3720 std::vector<Value*> TIPHIValues; 3721 3722 // Check to see if Dest has any blocks that can be used as a split edge for 3723 // this terminator. 3724 for (pred_iterator PI = pred_begin(Dest), E = pred_end(Dest); PI != E; ++PI) { 3725 BasicBlock *Pred = *PI; 3726 // To be usable, the pred has to end with an uncond branch to the dest. 3727 BranchInst *PredBr = dyn_cast<BranchInst>(Pred->getTerminator()); 3728 if (!PredBr || !PredBr->isUnconditional() || 3729 // Must be empty other than the branch. 3730 &Pred->front() != PredBr) 3731 continue; 3732 3733 // Finally, since we know that Dest has phi nodes in it, we have to make 3734 // sure that jumping to Pred will have the same affect as going to Dest in 3735 // terms of PHI values. 3736 PHINode *PN; 3737 unsigned PHINo = 0; 3738 bool FoundMatch = true; 3739 for (BasicBlock::iterator I = Dest->begin(); 3740 (PN = dyn_cast<PHINode>(I)); ++I, ++PHINo) { 3741 if (PHINo == TIPHIValues.size()) 3742 TIPHIValues.push_back(PN->getIncomingValueForBlock(TIBB)); 3743 3744 // If the PHI entry doesn't work, we can't use this pred. 3745 if (TIPHIValues[PHINo] != PN->getIncomingValueForBlock(Pred)) { 3746 FoundMatch = false; 3747 break; 3748 } 3749 } 3750 3751 // If we found a workable predecessor, change TI to branch to Succ. 3752 if (FoundMatch) { 3753 Dest->removePredecessor(TIBB); 3754 TI->setSuccessor(SuccNum, Pred); 3755 return; 3756 } 3757 } 3758 3759 SplitCriticalEdge(TI, SuccNum, P, true); 3760} 3761 3762 3763bool SelectionDAGISel::runOnFunction(Function &Fn) { 3764 MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine()); 3765 RegMap = MF.getSSARegMap(); 3766 DOUT << "\n\n\n=== " << Fn.getName() << "\n"; 3767 3768 // First, split all critical edges. 3769 // 3770 // In this pass we also look for GEP and cast instructions that are used 3771 // across basic blocks and rewrite them to improve basic-block-at-a-time 3772 // selection. 3773 // 3774 bool MadeChange = true; 3775 while (MadeChange) { 3776 MadeChange = false; 3777 for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 3778 // Split all critical edges where the dest block has a PHI. 3779 TerminatorInst *BBTI = BB->getTerminator(); 3780 if (BBTI->getNumSuccessors() > 1) { 3781 for (unsigned i = 0, e = BBTI->getNumSuccessors(); i != e; ++i) 3782 if (isa<PHINode>(BBTI->getSuccessor(i)->begin()) && 3783 isCriticalEdge(BBTI, i, true)) 3784 SplitEdgeNicely(BBTI, i, this); 3785 } 3786 3787 3788 for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) { 3789 Instruction *I = BBI++; 3790 3791 if (CallInst *CI = dyn_cast<CallInst>(I)) { 3792 // If we found an inline asm expession, and if the target knows how to 3793 // lower it to normal LLVM code, do so now. 3794 if (isa<InlineAsm>(CI->getCalledValue())) 3795 if (const TargetAsmInfo *TAI = 3796 TLI.getTargetMachine().getTargetAsmInfo()) { 3797 if (TAI->ExpandInlineAsm(CI)) 3798 BBI = BB->begin(); 3799 } 3800 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) { 3801 MadeChange |= OptimizeGEPExpression(GEPI, TLI.getTargetData()); 3802 } else if (CastInst *CI = dyn_cast<CastInst>(I)) { 3803 // If the source of the cast is a constant, then this should have 3804 // already been constant folded. The only reason NOT to constant fold 3805 // it is if something (e.g. LSR) was careful to place the constant 3806 // evaluation in a block other than then one that uses it (e.g. to hoist 3807 // the address of globals out of a loop). If this is the case, we don't 3808 // want to forward-subst the cast. 3809 if (isa<Constant>(CI->getOperand(0))) 3810 continue; 3811 3812 // If this is a noop copy, sink it into user blocks to reduce the number 3813 // of virtual registers that must be created and coallesced. 3814 MVT::ValueType SrcVT = TLI.getValueType(CI->getOperand(0)->getType()); 3815 MVT::ValueType DstVT = TLI.getValueType(CI->getType()); 3816 3817 // This is an fp<->int conversion? 3818 if (MVT::isInteger(SrcVT) != MVT::isInteger(DstVT)) 3819 continue; 3820 3821 // If this is an extension, it will be a zero or sign extension, which 3822 // isn't a noop. 3823 if (SrcVT < DstVT) continue; 3824 3825 // If these values will be promoted, find out what they will be promoted 3826 // to. This helps us consider truncates on PPC as noop copies when they 3827 // are. 3828 if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) 3829 SrcVT = TLI.getTypeToTransformTo(SrcVT); 3830 if (TLI.getTypeAction(DstVT) == TargetLowering::Promote) 3831 DstVT = TLI.getTypeToTransformTo(DstVT); 3832 3833 // If, after promotion, these are the same types, this is a noop copy. 3834 if (SrcVT == DstVT) 3835 MadeChange |= OptimizeNoopCopyExpression(CI); 3836 } 3837 } 3838 } 3839 } 3840 3841 FunctionLoweringInfo FuncInfo(TLI, Fn, MF); 3842 3843 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 3844 SelectBasicBlock(I, MF, FuncInfo); 3845 3846 return true; 3847} 3848 3849SDOperand SelectionDAGLowering::CopyValueToVirtualRegister(Value *V, 3850 unsigned Reg) { 3851 SDOperand Op = getValue(V); 3852 assert((Op.getOpcode() != ISD::CopyFromReg || 3853 cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) && 3854 "Copy from a reg to the same reg!"); 3855 3856 // If this type is not legal, we must make sure to not create an invalid 3857 // register use. 3858 MVT::ValueType SrcVT = Op.getValueType(); 3859 MVT::ValueType DestVT = TLI.getTypeToTransformTo(SrcVT); 3860 if (SrcVT == DestVT) { 3861 return DAG.getCopyToReg(getRoot(), Reg, Op); 3862 } else if (SrcVT == MVT::Vector) { 3863 // Handle copies from generic vectors to registers. 3864 MVT::ValueType PTyElementVT, PTyLegalElementVT; 3865 unsigned NE = TLI.getPackedTypeBreakdown(cast<PackedType>(V->getType()), 3866 PTyElementVT, PTyLegalElementVT); 3867 3868 // Insert a VBIT_CONVERT of the input vector to a "N x PTyElementVT" 3869 // MVT::Vector type. 3870 Op = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Op, 3871 DAG.getConstant(NE, MVT::i32), 3872 DAG.getValueType(PTyElementVT)); 3873 3874 // Loop over all of the elements of the resultant vector, 3875 // VEXTRACT_VECTOR_ELT'ing them, converting them to PTyLegalElementVT, then 3876 // copying them into output registers. 3877 SmallVector<SDOperand, 8> OutChains; 3878 SDOperand Root = getRoot(); 3879 for (unsigned i = 0; i != NE; ++i) { 3880 SDOperand Elt = DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, PTyElementVT, 3881 Op, DAG.getConstant(i, TLI.getPointerTy())); 3882 if (PTyElementVT == PTyLegalElementVT) { 3883 // Elements are legal. 3884 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt)); 3885 } else if (PTyLegalElementVT > PTyElementVT) { 3886 // Elements are promoted. 3887 if (MVT::isFloatingPoint(PTyLegalElementVT)) 3888 Elt = DAG.getNode(ISD::FP_EXTEND, PTyLegalElementVT, Elt); 3889 else 3890 Elt = DAG.getNode(ISD::ANY_EXTEND, PTyLegalElementVT, Elt); 3891 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt)); 3892 } else { 3893 // Elements are expanded. 3894 // The src value is expanded into multiple registers. 3895 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT, 3896 Elt, DAG.getConstant(0, TLI.getPointerTy())); 3897 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT, 3898 Elt, DAG.getConstant(1, TLI.getPointerTy())); 3899 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Lo)); 3900 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Hi)); 3901 } 3902 } 3903 return DAG.getNode(ISD::TokenFactor, MVT::Other, 3904 &OutChains[0], OutChains.size()); 3905 } else if (TLI.getTypeAction(SrcVT) == TargetLowering::Promote) { 3906 // The src value is promoted to the register. 3907 if (MVT::isFloatingPoint(SrcVT)) 3908 Op = DAG.getNode(ISD::FP_EXTEND, DestVT, Op); 3909 else 3910 Op = DAG.getNode(ISD::ANY_EXTEND, DestVT, Op); 3911 return DAG.getCopyToReg(getRoot(), Reg, Op); 3912 } else { 3913 DestVT = TLI.getTypeToExpandTo(SrcVT); 3914 unsigned NumVals = TLI.getNumElements(SrcVT); 3915 if (NumVals == 1) 3916 return DAG.getCopyToReg(getRoot(), Reg, 3917 DAG.getNode(ISD::BIT_CONVERT, DestVT, Op)); 3918 assert(NumVals == 2 && "1 to 4 (and more) expansion not implemented!"); 3919 // The src value is expanded into multiple registers. 3920 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT, 3921 Op, DAG.getConstant(0, TLI.getPointerTy())); 3922 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT, 3923 Op, DAG.getConstant(1, TLI.getPointerTy())); 3924 Op = DAG.getCopyToReg(getRoot(), Reg, Lo); 3925 return DAG.getCopyToReg(Op, Reg+1, Hi); 3926 } 3927} 3928 3929void SelectionDAGISel:: 3930LowerArguments(BasicBlock *BB, SelectionDAGLowering &SDL, 3931 std::vector<SDOperand> &UnorderedChains) { 3932 // If this is the entry block, emit arguments. 3933 Function &F = *BB->getParent(); 3934 FunctionLoweringInfo &FuncInfo = SDL.FuncInfo; 3935 SDOperand OldRoot = SDL.DAG.getRoot(); 3936 std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG); 3937 3938 unsigned a = 0; 3939 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 3940 AI != E; ++AI, ++a) 3941 if (!AI->use_empty()) { 3942 SDL.setValue(AI, Args[a]); 3943 3944 // If this argument is live outside of the entry block, insert a copy from 3945 // whereever we got it to the vreg that other BB's will reference it as. 3946 if (FuncInfo.ValueMap.count(AI)) { 3947 SDOperand Copy = 3948 SDL.CopyValueToVirtualRegister(AI, FuncInfo.ValueMap[AI]); 3949 UnorderedChains.push_back(Copy); 3950 } 3951 } 3952 3953 // Finally, if the target has anything special to do, allow it to do so. 3954 // FIXME: this should insert code into the DAG! 3955 EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction()); 3956} 3957 3958void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB, 3959 std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate, 3960 FunctionLoweringInfo &FuncInfo) { 3961 SelectionDAGLowering SDL(DAG, TLI, FuncInfo); 3962 3963 std::vector<SDOperand> UnorderedChains; 3964 3965 // Lower any arguments needed in this block if this is the entry block. 3966 if (LLVMBB == &LLVMBB->getParent()->front()) 3967 LowerArguments(LLVMBB, SDL, UnorderedChains); 3968 3969 BB = FuncInfo.MBBMap[LLVMBB]; 3970 SDL.setCurrentBasicBlock(BB); 3971 3972 // Lower all of the non-terminator instructions. 3973 for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end(); 3974 I != E; ++I) 3975 SDL.visit(*I); 3976 3977 // Ensure that all instructions which are used outside of their defining 3978 // blocks are available as virtual registers. 3979 for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I) 3980 if (!I->use_empty() && !isa<PHINode>(I)) { 3981 std::map<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I); 3982 if (VMI != FuncInfo.ValueMap.end()) 3983 UnorderedChains.push_back( 3984 SDL.CopyValueToVirtualRegister(I, VMI->second)); 3985 } 3986 3987 // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to 3988 // ensure constants are generated when needed. Remember the virtual registers 3989 // that need to be added to the Machine PHI nodes as input. We cannot just 3990 // directly add them, because expansion might result in multiple MBB's for one 3991 // BB. As such, the start of the BB might correspond to a different MBB than 3992 // the end. 3993 // 3994 TerminatorInst *TI = LLVMBB->getTerminator(); 3995 3996 // Emit constants only once even if used by multiple PHI nodes. 3997 std::map<Constant*, unsigned> ConstantsOut; 3998 3999 // Vector bool would be better, but vector<bool> is really slow. 4000 std::vector<unsigned char> SuccsHandled; 4001 if (TI->getNumSuccessors()) 4002 SuccsHandled.resize(BB->getParent()->getNumBlockIDs()); 4003 4004 // Check successor nodes PHI nodes that expect a constant to be available from 4005 // this block. 4006 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { 4007 BasicBlock *SuccBB = TI->getSuccessor(succ); 4008 if (!isa<PHINode>(SuccBB->begin())) continue; 4009 MachineBasicBlock *SuccMBB = FuncInfo.MBBMap[SuccBB]; 4010 4011 // If this terminator has multiple identical successors (common for 4012 // switches), only handle each succ once. 4013 unsigned SuccMBBNo = SuccMBB->getNumber(); 4014 if (SuccsHandled[SuccMBBNo]) continue; 4015 SuccsHandled[SuccMBBNo] = true; 4016 4017 MachineBasicBlock::iterator MBBI = SuccMBB->begin(); 4018 PHINode *PN; 4019 4020 // At this point we know that there is a 1-1 correspondence between LLVM PHI 4021 // nodes and Machine PHI nodes, but the incoming operands have not been 4022 // emitted yet. 4023 for (BasicBlock::iterator I = SuccBB->begin(); 4024 (PN = dyn_cast<PHINode>(I)); ++I) { 4025 // Ignore dead phi's. 4026 if (PN->use_empty()) continue; 4027 4028 unsigned Reg; 4029 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 4030 4031 if (Constant *C = dyn_cast<Constant>(PHIOp)) { 4032 unsigned &RegOut = ConstantsOut[C]; 4033 if (RegOut == 0) { 4034 RegOut = FuncInfo.CreateRegForValue(C); 4035 UnorderedChains.push_back( 4036 SDL.CopyValueToVirtualRegister(C, RegOut)); 4037 } 4038 Reg = RegOut; 4039 } else { 4040 Reg = FuncInfo.ValueMap[PHIOp]; 4041 if (Reg == 0) { 4042 assert(isa<AllocaInst>(PHIOp) && 4043 FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) && 4044 "Didn't codegen value into a register!??"); 4045 Reg = FuncInfo.CreateRegForValue(PHIOp); 4046 UnorderedChains.push_back( 4047 SDL.CopyValueToVirtualRegister(PHIOp, Reg)); 4048 } 4049 } 4050 4051 // Remember that this register needs to added to the machine PHI node as 4052 // the input for this MBB. 4053 MVT::ValueType VT = TLI.getValueType(PN->getType()); 4054 unsigned NumElements; 4055 if (VT != MVT::Vector) 4056 NumElements = TLI.getNumElements(VT); 4057 else { 4058 MVT::ValueType VT1,VT2; 4059 NumElements = 4060 TLI.getPackedTypeBreakdown(cast<PackedType>(PN->getType()), 4061 VT1, VT2); 4062 } 4063 for (unsigned i = 0, e = NumElements; i != e; ++i) 4064 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i)); 4065 } 4066 } 4067 ConstantsOut.clear(); 4068 4069 // Turn all of the unordered chains into one factored node. 4070 if (!UnorderedChains.empty()) { 4071 SDOperand Root = SDL.getRoot(); 4072 if (Root.getOpcode() != ISD::EntryToken) { 4073 unsigned i = 0, e = UnorderedChains.size(); 4074 for (; i != e; ++i) { 4075 assert(UnorderedChains[i].Val->getNumOperands() > 1); 4076 if (UnorderedChains[i].Val->getOperand(0) == Root) 4077 break; // Don't add the root if we already indirectly depend on it. 4078 } 4079 4080 if (i == e) 4081 UnorderedChains.push_back(Root); 4082 } 4083 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, 4084 &UnorderedChains[0], UnorderedChains.size())); 4085 } 4086 4087 // Lower the terminator after the copies are emitted. 4088 SDL.visit(*LLVMBB->getTerminator()); 4089 4090 // Copy over any CaseBlock records that may now exist due to SwitchInst 4091 // lowering, as well as any jump table information. 4092 SwitchCases.clear(); 4093 SwitchCases = SDL.SwitchCases; 4094 JT = SDL.JT; 4095 4096 // Make sure the root of the DAG is up-to-date. 4097 DAG.setRoot(SDL.getRoot()); 4098} 4099 4100void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) { 4101 // Get alias analysis for load/store combining. 4102 AliasAnalysis &AA = getAnalysis<AliasAnalysis>(); 4103 4104 // Run the DAG combiner in pre-legalize mode. 4105 DAG.Combine(false, AA); 4106 4107 DOUT << "Lowered selection DAG:\n"; 4108 DEBUG(DAG.dump()); 4109 4110 // Second step, hack on the DAG until it only uses operations and types that 4111 // the target supports. 4112 DAG.Legalize(); 4113 4114 DOUT << "Legalized selection DAG:\n"; 4115 DEBUG(DAG.dump()); 4116 4117 // Run the DAG combiner in post-legalize mode. 4118 DAG.Combine(true, AA); 4119 4120 if (ViewISelDAGs) DAG.viewGraph(); 4121 4122 // Third, instruction select all of the operations to machine code, adding the 4123 // code to the MachineBasicBlock. 4124 InstructionSelectBasicBlock(DAG); 4125 4126 DOUT << "Selected machine code:\n"; 4127 DEBUG(BB->dump()); 4128} 4129 4130void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, 4131 FunctionLoweringInfo &FuncInfo) { 4132 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate; 4133 { 4134 SelectionDAG DAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4135 CurDAG = &DAG; 4136 4137 // First step, lower LLVM code to some DAG. This DAG may use operations and 4138 // types that are not supported by the target. 4139 BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo); 4140 4141 // Second step, emit the lowered DAG as machine code. 4142 CodeGenAndEmitDAG(DAG); 4143 } 4144 4145 // Next, now that we know what the last MBB the LLVM BB expanded is, update 4146 // PHI nodes in successors. 4147 if (SwitchCases.empty() && JT.Reg == 0) { 4148 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) { 4149 MachineInstr *PHI = PHINodesToUpdate[i].first; 4150 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 4151 "This is not a machine PHI node that we are updating!"); 4152 PHI->addRegOperand(PHINodesToUpdate[i].second, false); 4153 PHI->addMachineBasicBlockOperand(BB); 4154 } 4155 return; 4156 } 4157 4158 // If the JumpTable record is filled in, then we need to emit a jump table. 4159 // Updating the PHI nodes is tricky in this case, since we need to determine 4160 // whether the PHI is a successor of the range check MBB or the jump table MBB 4161 if (JT.Reg) { 4162 assert(SwitchCases.empty() && "Cannot have jump table and lowered switch"); 4163 SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4164 CurDAG = &SDAG; 4165 SelectionDAGLowering SDL(SDAG, TLI, FuncInfo); 4166 MachineBasicBlock *RangeBB = BB; 4167 // Set the current basic block to the mbb we wish to insert the code into 4168 BB = JT.MBB; 4169 SDL.setCurrentBasicBlock(BB); 4170 // Emit the code 4171 SDL.visitJumpTable(JT); 4172 SDAG.setRoot(SDL.getRoot()); 4173 CodeGenAndEmitDAG(SDAG); 4174 // Update PHI Nodes 4175 for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) { 4176 MachineInstr *PHI = PHINodesToUpdate[pi].first; 4177 MachineBasicBlock *PHIBB = PHI->getParent(); 4178 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 4179 "This is not a machine PHI node that we are updating!"); 4180 if (PHIBB == JT.Default) { 4181 PHI->addRegOperand(PHINodesToUpdate[pi].second, false); 4182 PHI->addMachineBasicBlockOperand(RangeBB); 4183 } 4184 if (BB->succ_end() != std::find(BB->succ_begin(),BB->succ_end(), PHIBB)) { 4185 PHI->addRegOperand(PHINodesToUpdate[pi].second, false); 4186 PHI->addMachineBasicBlockOperand(BB); 4187 } 4188 } 4189 return; 4190 } 4191 4192 // If the switch block involved a branch to one of the actual successors, we 4193 // need to update PHI nodes in that block. 4194 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) { 4195 MachineInstr *PHI = PHINodesToUpdate[i].first; 4196 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 4197 "This is not a machine PHI node that we are updating!"); 4198 if (BB->isSuccessor(PHI->getParent())) { 4199 PHI->addRegOperand(PHINodesToUpdate[i].second, false); 4200 PHI->addMachineBasicBlockOperand(BB); 4201 } 4202 } 4203 4204 // If we generated any switch lowering information, build and codegen any 4205 // additional DAGs necessary. 4206 for (unsigned i = 0, e = SwitchCases.size(); i != e; ++i) { 4207 SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineModuleInfo>()); 4208 CurDAG = &SDAG; 4209 SelectionDAGLowering SDL(SDAG, TLI, FuncInfo); 4210 4211 // Set the current basic block to the mbb we wish to insert the code into 4212 BB = SwitchCases[i].ThisBB; 4213 SDL.setCurrentBasicBlock(BB); 4214 4215 // Emit the code 4216 SDL.visitSwitchCase(SwitchCases[i]); 4217 SDAG.setRoot(SDL.getRoot()); 4218 CodeGenAndEmitDAG(SDAG); 4219 4220 // Handle any PHI nodes in successors of this chunk, as if we were coming 4221 // from the original BB before switch expansion. Note that PHI nodes can 4222 // occur multiple times in PHINodesToUpdate. We have to be very careful to 4223 // handle them the right number of times. 4224 while ((BB = SwitchCases[i].TrueBB)) { // Handle LHS and RHS. 4225 for (MachineBasicBlock::iterator Phi = BB->begin(); 4226 Phi != BB->end() && Phi->getOpcode() == TargetInstrInfo::PHI; ++Phi){ 4227 // This value for this PHI node is recorded in PHINodesToUpdate, get it. 4228 for (unsigned pn = 0; ; ++pn) { 4229 assert(pn != PHINodesToUpdate.size() && "Didn't find PHI entry!"); 4230 if (PHINodesToUpdate[pn].first == Phi) { 4231 Phi->addRegOperand(PHINodesToUpdate[pn].second, false); 4232 Phi->addMachineBasicBlockOperand(SwitchCases[i].ThisBB); 4233 break; 4234 } 4235 } 4236 } 4237 4238 // Don't process RHS if same block as LHS. 4239 if (BB == SwitchCases[i].FalseBB) 4240 SwitchCases[i].FalseBB = 0; 4241 4242 // If we haven't handled the RHS, do so now. Otherwise, we're done. 4243 SwitchCases[i].TrueBB = SwitchCases[i].FalseBB; 4244 SwitchCases[i].FalseBB = 0; 4245 } 4246 assert(SwitchCases[i].TrueBB == 0 && SwitchCases[i].FalseBB == 0); 4247 } 4248} 4249 4250 4251//===----------------------------------------------------------------------===// 4252/// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each 4253/// target node in the graph. 4254void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) { 4255 if (ViewSchedDAGs) DAG.viewGraph(); 4256 4257 RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault(); 4258 4259 if (!Ctor) { 4260 Ctor = ISHeuristic; 4261 RegisterScheduler::setDefault(Ctor); 4262 } 4263 4264 ScheduleDAG *SL = Ctor(this, &DAG, BB); 4265 BB = SL->Run(); 4266 delete SL; 4267} 4268 4269 4270HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() { 4271 return new HazardRecognizer(); 4272} 4273 4274//===----------------------------------------------------------------------===// 4275// Helper functions used by the generated instruction selector. 4276//===----------------------------------------------------------------------===// 4277// Calls to these methods are generated by tblgen. 4278 4279/// CheckAndMask - The isel is trying to match something like (and X, 255). If 4280/// the dag combiner simplified the 255, we still want to match. RHS is the 4281/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value 4282/// specified in the .td file (e.g. 255). 4283bool SelectionDAGISel::CheckAndMask(SDOperand LHS, ConstantSDNode *RHS, 4284 int64_t DesiredMaskS) { 4285 uint64_t ActualMask = RHS->getValue(); 4286 uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType()); 4287 4288 // If the actual mask exactly matches, success! 4289 if (ActualMask == DesiredMask) 4290 return true; 4291 4292 // If the actual AND mask is allowing unallowed bits, this doesn't match. 4293 if (ActualMask & ~DesiredMask) 4294 return false; 4295 4296 // Otherwise, the DAG Combiner may have proven that the value coming in is 4297 // either already zero or is not demanded. Check for known zero input bits. 4298 uint64_t NeededMask = DesiredMask & ~ActualMask; 4299 if (getTargetLowering().MaskedValueIsZero(LHS, NeededMask)) 4300 return true; 4301 4302 // TODO: check to see if missing bits are just not demanded. 4303 4304 // Otherwise, this pattern doesn't match. 4305 return false; 4306} 4307 4308/// CheckOrMask - The isel is trying to match something like (or X, 255). If 4309/// the dag combiner simplified the 255, we still want to match. RHS is the 4310/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value 4311/// specified in the .td file (e.g. 255). 4312bool SelectionDAGISel::CheckOrMask(SDOperand LHS, ConstantSDNode *RHS, 4313 int64_t DesiredMaskS) { 4314 uint64_t ActualMask = RHS->getValue(); 4315 uint64_t DesiredMask =DesiredMaskS & MVT::getIntVTBitMask(LHS.getValueType()); 4316 4317 // If the actual mask exactly matches, success! 4318 if (ActualMask == DesiredMask) 4319 return true; 4320 4321 // If the actual AND mask is allowing unallowed bits, this doesn't match. 4322 if (ActualMask & ~DesiredMask) 4323 return false; 4324 4325 // Otherwise, the DAG Combiner may have proven that the value coming in is 4326 // either already zero or is not demanded. Check for known zero input bits. 4327 uint64_t NeededMask = DesiredMask & ~ActualMask; 4328 4329 uint64_t KnownZero, KnownOne; 4330 getTargetLowering().ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne); 4331 4332 // If all the missing bits in the or are already known to be set, match! 4333 if ((NeededMask & KnownOne) == NeededMask) 4334 return true; 4335 4336 // TODO: check to see if missing bits are just not demanded. 4337 4338 // Otherwise, this pattern doesn't match. 4339 return false; 4340} 4341 4342 4343/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated 4344/// by tblgen. Others should not call it. 4345void SelectionDAGISel:: 4346SelectInlineAsmMemoryOperands(std::vector<SDOperand> &Ops, SelectionDAG &DAG) { 4347 std::vector<SDOperand> InOps; 4348 std::swap(InOps, Ops); 4349 4350 Ops.push_back(InOps[0]); // input chain. 4351 Ops.push_back(InOps[1]); // input asm string. 4352 4353 unsigned i = 2, e = InOps.size(); 4354 if (InOps[e-1].getValueType() == MVT::Flag) 4355 --e; // Don't process a flag operand if it is here. 4356 4357 while (i != e) { 4358 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue(); 4359 if ((Flags & 7) != 4 /*MEM*/) { 4360 // Just skip over this operand, copying the operands verbatim. 4361 Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1); 4362 i += (Flags >> 3) + 1; 4363 } else { 4364 assert((Flags >> 3) == 1 && "Memory operand with multiple values?"); 4365 // Otherwise, this is a memory operand. Ask the target to select it. 4366 std::vector<SDOperand> SelOps; 4367 if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) { 4368 cerr << "Could not match memory address. Inline asm failure!\n"; 4369 exit(1); 4370 } 4371 4372 // Add this to the output node. 4373 Ops.push_back(DAG.getTargetConstant(4/*MEM*/ | (SelOps.size() << 3), 4374 MVT::i32)); 4375 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end()); 4376 i += 2; 4377 } 4378 } 4379 4380 // Add the flag input back if present. 4381 if (e != InOps.size()) 4382 Ops.push_back(InOps.back()); 4383} 4384