LLVM API Documentation
00001 //===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements the SelectionDAGISel class. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #define DEBUG_TYPE "isel" 00015 #include "llvm/CodeGen/SelectionDAGISel.h" 00016 #include "llvm/CodeGen/ScheduleDAG.h" 00017 #include "llvm/CallingConv.h" 00018 #include "llvm/Constants.h" 00019 #include "llvm/DerivedTypes.h" 00020 #include "llvm/Function.h" 00021 #include "llvm/GlobalVariable.h" 00022 #include "llvm/InlineAsm.h" 00023 #include "llvm/Instructions.h" 00024 #include "llvm/Intrinsics.h" 00025 #include "llvm/IntrinsicInst.h" 00026 #include "llvm/CodeGen/IntrinsicLowering.h" 00027 #include "llvm/CodeGen/MachineDebugInfo.h" 00028 #include "llvm/CodeGen/MachineFunction.h" 00029 #include "llvm/CodeGen/MachineFrameInfo.h" 00030 #include "llvm/CodeGen/MachineInstrBuilder.h" 00031 #include "llvm/CodeGen/SelectionDAG.h" 00032 #include "llvm/CodeGen/SSARegMap.h" 00033 #include "llvm/Target/MRegisterInfo.h" 00034 #include "llvm/Target/TargetData.h" 00035 #include "llvm/Target/TargetFrameInfo.h" 00036 #include "llvm/Target/TargetInstrInfo.h" 00037 #include "llvm/Target/TargetLowering.h" 00038 #include "llvm/Target/TargetMachine.h" 00039 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 00040 #include "llvm/Support/CommandLine.h" 00041 #include "llvm/Support/MathExtras.h" 00042 #include "llvm/Support/Debug.h" 00043 #include <map> 00044 #include <set> 00045 #include <iostream> 00046 #include <algorithm> 00047 using namespace llvm; 00048 00049 #ifndef NDEBUG 00050 static cl::opt<bool> 00051 ViewISelDAGs("view-isel-dags", cl::Hidden, 00052 cl::desc("Pop up a window to show isel dags as they are selected")); 00053 static cl::opt<bool> 00054 ViewSchedDAGs("view-sched-dags", cl::Hidden, 00055 cl::desc("Pop up a window to show sched dags as they are processed")); 00056 #else 00057 static const bool ViewISelDAGs = 0, ViewSchedDAGs = 0; 00058 #endif 00059 00060 // Scheduling heuristics 00061 enum SchedHeuristics { 00062 defaultScheduling, // Let the target specify its preference. 00063 noScheduling, // No scheduling, emit breadth first sequence. 00064 simpleScheduling, // Two pass, min. critical path, max. utilization. 00065 simpleNoItinScheduling, // Same as above exact using generic latency. 00066 listSchedulingBURR, // Bottom up reg reduction list scheduling. 00067 listSchedulingTD // Top-down list scheduler. 00068 }; 00069 00070 namespace { 00071 cl::opt<SchedHeuristics> 00072 ISHeuristic( 00073 "sched", 00074 cl::desc("Choose scheduling style"), 00075 cl::init(defaultScheduling), 00076 cl::values( 00077 clEnumValN(defaultScheduling, "default", 00078 "Target preferred scheduling style"), 00079 clEnumValN(noScheduling, "none", 00080 "No scheduling: breadth first sequencing"), 00081 clEnumValN(simpleScheduling, "simple", 00082 "Simple two pass scheduling: minimize critical path " 00083 "and maximize processor utilization"), 00084 clEnumValN(simpleNoItinScheduling, "simple-noitin", 00085 "Simple two pass scheduling: Same as simple " 00086 "except using generic latency"), 00087 clEnumValN(listSchedulingBURR, "list-burr", 00088 "Bottom up register reduction list scheduling"), 00089 clEnumValN(listSchedulingTD, "list-td", 00090 "Top-down list scheduler"), 00091 clEnumValEnd)); 00092 } // namespace 00093 00094 namespace { 00095 /// RegsForValue - This struct represents the physical registers that a 00096 /// particular value is assigned and the type information about the value. 00097 /// This is needed because values can be promoted into larger registers and 00098 /// expanded into multiple smaller registers than the value. 00099 struct RegsForValue { 00100 /// Regs - This list hold the register (for legal and promoted values) 00101 /// or register set (for expanded values) that the value should be assigned 00102 /// to. 00103 std::vector<unsigned> Regs; 00104 00105 /// RegVT - The value type of each register. 00106 /// 00107 MVT::ValueType RegVT; 00108 00109 /// ValueVT - The value type of the LLVM value, which may be promoted from 00110 /// RegVT or made from merging the two expanded parts. 00111 MVT::ValueType ValueVT; 00112 00113 RegsForValue() : RegVT(MVT::Other), ValueVT(MVT::Other) {} 00114 00115 RegsForValue(unsigned Reg, MVT::ValueType regvt, MVT::ValueType valuevt) 00116 : RegVT(regvt), ValueVT(valuevt) { 00117 Regs.push_back(Reg); 00118 } 00119 RegsForValue(const std::vector<unsigned> ®s, 00120 MVT::ValueType regvt, MVT::ValueType valuevt) 00121 : Regs(regs), RegVT(regvt), ValueVT(valuevt) { 00122 } 00123 00124 /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from 00125 /// this value and returns the result as a ValueVT value. This uses 00126 /// Chain/Flag as the input and updates them for the output Chain/Flag. 00127 SDOperand getCopyFromRegs(SelectionDAG &DAG, 00128 SDOperand &Chain, SDOperand &Flag) const; 00129 00130 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the 00131 /// specified value into the registers specified by this object. This uses 00132 /// Chain/Flag as the input and updates them for the output Chain/Flag. 00133 void getCopyToRegs(SDOperand Val, SelectionDAG &DAG, 00134 SDOperand &Chain, SDOperand &Flag) const; 00135 00136 /// AddInlineAsmOperands - Add this value to the specified inlineasm node 00137 /// operand list. This adds the code marker and includes the number of 00138 /// values added into it. 00139 void AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG, 00140 std::vector<SDOperand> &Ops) const; 00141 }; 00142 } 00143 00144 namespace llvm { 00145 //===--------------------------------------------------------------------===// 00146 /// FunctionLoweringInfo - This contains information that is global to a 00147 /// function that is used when lowering a region of the function. 00148 class FunctionLoweringInfo { 00149 public: 00150 TargetLowering &TLI; 00151 Function &Fn; 00152 MachineFunction &MF; 00153 SSARegMap *RegMap; 00154 00155 FunctionLoweringInfo(TargetLowering &TLI, Function &Fn,MachineFunction &MF); 00156 00157 /// MBBMap - A mapping from LLVM basic blocks to their machine code entry. 00158 std::map<const BasicBlock*, MachineBasicBlock *> MBBMap; 00159 00160 /// ValueMap - Since we emit code for the function a basic block at a time, 00161 /// we must remember which virtual registers hold the values for 00162 /// cross-basic-block values. 00163 std::map<const Value*, unsigned> ValueMap; 00164 00165 /// StaticAllocaMap - Keep track of frame indices for fixed sized allocas in 00166 /// the entry block. This allows the allocas to be efficiently referenced 00167 /// anywhere in the function. 00168 std::map<const AllocaInst*, int> StaticAllocaMap; 00169 00170 unsigned MakeReg(MVT::ValueType VT) { 00171 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT)); 00172 } 00173 00174 unsigned CreateRegForValue(const Value *V); 00175 00176 unsigned InitializeRegForValue(const Value *V) { 00177 unsigned &R = ValueMap[V]; 00178 assert(R == 0 && "Already initialized this value register!"); 00179 return R = CreateRegForValue(V); 00180 } 00181 }; 00182 } 00183 00184 /// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by 00185 /// PHI nodes or outside of the basic block that defines it, or used by a 00186 /// switch instruction, which may expand to multiple basic blocks. 00187 static bool isUsedOutsideOfDefiningBlock(Instruction *I) { 00188 if (isa<PHINode>(I)) return true; 00189 BasicBlock *BB = I->getParent(); 00190 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) 00191 if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI) || 00192 isa<SwitchInst>(*UI)) 00193 return true; 00194 return false; 00195 } 00196 00197 /// isOnlyUsedInEntryBlock - If the specified argument is only used in the 00198 /// entry block, return true. This includes arguments used by switches, since 00199 /// the switch may expand into multiple basic blocks. 00200 static bool isOnlyUsedInEntryBlock(Argument *A) { 00201 BasicBlock *Entry = A->getParent()->begin(); 00202 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI) 00203 if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI)) 00204 return false; // Use not in entry block. 00205 return true; 00206 } 00207 00208 FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli, 00209 Function &fn, MachineFunction &mf) 00210 : TLI(tli), Fn(fn), MF(mf), RegMap(MF.getSSARegMap()) { 00211 00212 // Create a vreg for each argument register that is not dead and is used 00213 // outside of the entry block for the function. 00214 for (Function::arg_iterator AI = Fn.arg_begin(), E = Fn.arg_end(); 00215 AI != E; ++AI) 00216 if (!isOnlyUsedInEntryBlock(AI)) 00217 InitializeRegForValue(AI); 00218 00219 // Initialize the mapping of values to registers. This is only set up for 00220 // instruction values that are used outside of the block that defines 00221 // them. 00222 Function::iterator BB = Fn.begin(), EB = Fn.end(); 00223 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00224 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 00225 if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(AI->getArraySize())) { 00226 const Type *Ty = AI->getAllocatedType(); 00227 uint64_t TySize = TLI.getTargetData().getTypeSize(Ty); 00228 unsigned Align = 00229 std::max((unsigned)TLI.getTargetData().getTypeAlignment(Ty), 00230 AI->getAlignment()); 00231 00232 // If the alignment of the value is smaller than the size of the value, 00233 // and if the size of the value is particularly small (<= 8 bytes), 00234 // round up to the size of the value for potentially better performance. 00235 // 00236 // FIXME: This could be made better with a preferred alignment hook in 00237 // TargetData. It serves primarily to 8-byte align doubles for X86. 00238 if (Align < TySize && TySize <= 8) Align = TySize; 00239 TySize *= CUI->getValue(); // Get total allocated size. 00240 if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects. 00241 StaticAllocaMap[AI] = 00242 MF.getFrameInfo()->CreateStackObject((unsigned)TySize, Align); 00243 } 00244 00245 for (; BB != EB; ++BB) 00246 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00247 if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I)) 00248 if (!isa<AllocaInst>(I) || 00249 !StaticAllocaMap.count(cast<AllocaInst>(I))) 00250 InitializeRegForValue(I); 00251 00252 // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This 00253 // also creates the initial PHI MachineInstrs, though none of the input 00254 // operands are populated. 00255 for (BB = Fn.begin(), EB = Fn.end(); BB != EB; ++BB) { 00256 MachineBasicBlock *MBB = new MachineBasicBlock(BB); 00257 MBBMap[BB] = MBB; 00258 MF.getBasicBlockList().push_back(MBB); 00259 00260 // Create Machine PHI nodes for LLVM PHI nodes, lowering them as 00261 // appropriate. 00262 PHINode *PN; 00263 for (BasicBlock::iterator I = BB->begin(); 00264 (PN = dyn_cast<PHINode>(I)); ++I) 00265 if (!PN->use_empty()) { 00266 MVT::ValueType VT = TLI.getValueType(PN->getType()); 00267 unsigned NumElements; 00268 if (VT != MVT::Vector) 00269 NumElements = TLI.getNumElements(VT); 00270 else { 00271 MVT::ValueType VT1,VT2; 00272 NumElements = 00273 TLI.getPackedTypeBreakdown(cast<PackedType>(PN->getType()), 00274 VT1, VT2); 00275 } 00276 unsigned PHIReg = ValueMap[PN]; 00277 assert(PHIReg &&"PHI node does not have an assigned virtual register!"); 00278 for (unsigned i = 0; i != NumElements; ++i) 00279 BuildMI(MBB, TargetInstrInfo::PHI, PN->getNumOperands(), PHIReg+i); 00280 } 00281 } 00282 } 00283 00284 /// CreateRegForValue - Allocate the appropriate number of virtual registers of 00285 /// the correctly promoted or expanded types. Assign these registers 00286 /// consecutive vreg numbers and return the first assigned number. 00287 unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) { 00288 MVT::ValueType VT = TLI.getValueType(V->getType()); 00289 00290 // The number of multiples of registers that we need, to, e.g., split up 00291 // a <2 x int64> -> 4 x i32 registers. 00292 unsigned NumVectorRegs = 1; 00293 00294 // If this is a packed type, figure out what type it will decompose into 00295 // and how many of the elements it will use. 00296 if (VT == MVT::Vector) { 00297 const PackedType *PTy = cast<PackedType>(V->getType()); 00298 unsigned NumElts = PTy->getNumElements(); 00299 MVT::ValueType EltTy = TLI.getValueType(PTy->getElementType()); 00300 00301 // Divide the input until we get to a supported size. This will always 00302 // end with a scalar if the target doesn't support vectors. 00303 while (NumElts > 1 && !TLI.isTypeLegal(getVectorType(EltTy, NumElts))) { 00304 NumElts >>= 1; 00305 NumVectorRegs <<= 1; 00306 } 00307 if (NumElts == 1) 00308 VT = EltTy; 00309 else 00310 VT = getVectorType(EltTy, NumElts); 00311 } 00312 00313 // The common case is that we will only create one register for this 00314 // value. If we have that case, create and return the virtual register. 00315 unsigned NV = TLI.getNumElements(VT); 00316 if (NV == 1) { 00317 // If we are promoting this value, pick the next largest supported type. 00318 MVT::ValueType PromotedType = TLI.getTypeToTransformTo(VT); 00319 unsigned Reg = MakeReg(PromotedType); 00320 // If this is a vector of supported or promoted types (e.g. 4 x i16), 00321 // create all of the registers. 00322 for (unsigned i = 1; i != NumVectorRegs; ++i) 00323 MakeReg(PromotedType); 00324 return Reg; 00325 } 00326 00327 // If this value is represented with multiple target registers, make sure 00328 // to create enough consecutive registers of the right (smaller) type. 00329 unsigned NT = VT-1; // Find the type to use. 00330 while (TLI.getNumElements((MVT::ValueType)NT) != 1) 00331 --NT; 00332 00333 unsigned R = MakeReg((MVT::ValueType)NT); 00334 for (unsigned i = 1; i != NV*NumVectorRegs; ++i) 00335 MakeReg((MVT::ValueType)NT); 00336 return R; 00337 } 00338 00339 //===----------------------------------------------------------------------===// 00340 /// SelectionDAGLowering - This is the common target-independent lowering 00341 /// implementation that is parameterized by a TargetLowering object. 00342 /// Also, targets can overload any lowering method. 00343 /// 00344 namespace llvm { 00345 class SelectionDAGLowering { 00346 MachineBasicBlock *CurMBB; 00347 00348 std::map<const Value*, SDOperand> NodeMap; 00349 00350 /// PendingLoads - Loads are not emitted to the program immediately. We bunch 00351 /// them up and then emit token factor nodes when possible. This allows us to 00352 /// get simple disambiguation between loads without worrying about alias 00353 /// analysis. 00354 std::vector<SDOperand> PendingLoads; 00355 00356 /// Case - A pair of values to record the Value for a switch case, and the 00357 /// case's target basic block. 00358 typedef std::pair<Constant*, MachineBasicBlock*> Case; 00359 typedef std::vector<Case>::iterator CaseItr; 00360 typedef std::pair<CaseItr, CaseItr> CaseRange; 00361 00362 /// CaseRec - A struct with ctor used in lowering switches to a binary tree 00363 /// of conditional branches. 00364 struct CaseRec { 00365 CaseRec(MachineBasicBlock *bb, Constant *lt, Constant *ge, CaseRange r) : 00366 CaseBB(bb), LT(lt), GE(ge), Range(r) {} 00367 00368 /// CaseBB - The MBB in which to emit the compare and branch 00369 MachineBasicBlock *CaseBB; 00370 /// LT, GE - If nonzero, we know the current case value must be less-than or 00371 /// greater-than-or-equal-to these Constants. 00372 Constant *LT; 00373 Constant *GE; 00374 /// Range - A pair of iterators representing the range of case values to be 00375 /// processed at this point in the binary search tree. 00376 CaseRange Range; 00377 }; 00378 00379 /// The comparison function for sorting Case values. 00380 struct CaseCmp { 00381 bool operator () (const Case& C1, const Case& C2) { 00382 if (const ConstantUInt* U1 = dyn_cast<const ConstantUInt>(C1.first)) 00383 return U1->getValue() < cast<const ConstantUInt>(C2.first)->getValue(); 00384 00385 const ConstantSInt* S1 = dyn_cast<const ConstantSInt>(C1.first); 00386 return S1->getValue() < cast<const ConstantSInt>(C2.first)->getValue(); 00387 } 00388 }; 00389 00390 public: 00391 // TLI - This is information that describes the available target features we 00392 // need for lowering. This indicates when operations are unavailable, 00393 // implemented with a libcall, etc. 00394 TargetLowering &TLI; 00395 SelectionDAG &DAG; 00396 const TargetData &TD; 00397 00398 /// SwitchCases - Vector of CaseBlock structures used to communicate 00399 /// SwitchInst code generation information. 00400 std::vector<SelectionDAGISel::CaseBlock> SwitchCases; 00401 00402 /// FuncInfo - Information about the function as a whole. 00403 /// 00404 FunctionLoweringInfo &FuncInfo; 00405 00406 SelectionDAGLowering(SelectionDAG &dag, TargetLowering &tli, 00407 FunctionLoweringInfo &funcinfo) 00408 : TLI(tli), DAG(dag), TD(DAG.getTarget().getTargetData()), 00409 FuncInfo(funcinfo) { 00410 } 00411 00412 /// getRoot - Return the current virtual root of the Selection DAG. 00413 /// 00414 SDOperand getRoot() { 00415 if (PendingLoads.empty()) 00416 return DAG.getRoot(); 00417 00418 if (PendingLoads.size() == 1) { 00419 SDOperand Root = PendingLoads[0]; 00420 DAG.setRoot(Root); 00421 PendingLoads.clear(); 00422 return Root; 00423 } 00424 00425 // Otherwise, we have to make a token factor node. 00426 SDOperand Root = DAG.getNode(ISD::TokenFactor, MVT::Other, PendingLoads); 00427 PendingLoads.clear(); 00428 DAG.setRoot(Root); 00429 return Root; 00430 } 00431 00432 void visit(Instruction &I) { visit(I.getOpcode(), I); } 00433 00434 void visit(unsigned Opcode, User &I) { 00435 switch (Opcode) { 00436 default: assert(0 && "Unknown instruction type encountered!"); 00437 abort(); 00438 // Build the switch statement using the Instruction.def file. 00439 #define HANDLE_INST(NUM, OPCODE, CLASS) \ 00440 case Instruction::OPCODE:return visit##OPCODE((CLASS&)I); 00441 #include "llvm/Instruction.def" 00442 } 00443 } 00444 00445 void setCurrentBasicBlock(MachineBasicBlock *MBB) { CurMBB = MBB; } 00446 00447 SDOperand getLoadFrom(const Type *Ty, SDOperand Ptr, 00448 SDOperand SrcValue, SDOperand Root, 00449 bool isVolatile); 00450 00451 SDOperand getIntPtrConstant(uint64_t Val) { 00452 return DAG.getConstant(Val, TLI.getPointerTy()); 00453 } 00454 00455 SDOperand getValue(const Value *V); 00456 00457 const SDOperand &setValue(const Value *V, SDOperand NewN) { 00458 SDOperand &N = NodeMap[V]; 00459 assert(N.Val == 0 && "Already set a value for this node!"); 00460 return N = NewN; 00461 } 00462 00463 RegsForValue GetRegistersForValue(const std::string &ConstrCode, 00464 MVT::ValueType VT, 00465 bool OutReg, bool InReg, 00466 std::set<unsigned> &OutputRegs, 00467 std::set<unsigned> &InputRegs); 00468 00469 // Terminator instructions. 00470 void visitRet(ReturnInst &I); 00471 void visitBr(BranchInst &I); 00472 void visitSwitch(SwitchInst &I); 00473 void visitUnreachable(UnreachableInst &I) { /* noop */ } 00474 00475 // Helper for visitSwitch 00476 void visitSwitchCase(SelectionDAGISel::CaseBlock &CB); 00477 00478 // These all get lowered before this pass. 00479 void visitInvoke(InvokeInst &I) { assert(0 && "TODO"); } 00480 void visitUnwind(UnwindInst &I) { assert(0 && "TODO"); } 00481 00482 void visitBinary(User &I, unsigned IntOp, unsigned FPOp, unsigned VecOp); 00483 void visitShift(User &I, unsigned Opcode); 00484 void visitAdd(User &I) { 00485 visitBinary(I, ISD::ADD, ISD::FADD, ISD::VADD); 00486 } 00487 void visitSub(User &I); 00488 void visitMul(User &I) { 00489 visitBinary(I, ISD::MUL, ISD::FMUL, ISD::VMUL); 00490 } 00491 void visitDiv(User &I) { 00492 const Type *Ty = I.getType(); 00493 visitBinary(I, 00494 Ty->isSigned() ? ISD::SDIV : ISD::UDIV, ISD::FDIV, 00495 Ty->isSigned() ? ISD::VSDIV : ISD::VUDIV); 00496 } 00497 void visitRem(User &I) { 00498 const Type *Ty = I.getType(); 00499 visitBinary(I, Ty->isSigned() ? ISD::SREM : ISD::UREM, ISD::FREM, 0); 00500 } 00501 void visitAnd(User &I) { visitBinary(I, ISD::AND, 0, ISD::VAND); } 00502 void visitOr (User &I) { visitBinary(I, ISD::OR, 0, ISD::VOR); } 00503 void visitXor(User &I) { visitBinary(I, ISD::XOR, 0, ISD::VXOR); } 00504 void visitShl(User &I) { visitShift(I, ISD::SHL); } 00505 void visitShr(User &I) { 00506 visitShift(I, I.getType()->isUnsigned() ? ISD::SRL : ISD::SRA); 00507 } 00508 00509 void visitSetCC(User &I, ISD::CondCode SignedOpc, ISD::CondCode UnsignedOpc); 00510 void visitSetEQ(User &I) { visitSetCC(I, ISD::SETEQ, ISD::SETEQ); } 00511 void visitSetNE(User &I) { visitSetCC(I, ISD::SETNE, ISD::SETNE); } 00512 void visitSetLE(User &I) { visitSetCC(I, ISD::SETLE, ISD::SETULE); } 00513 void visitSetGE(User &I) { visitSetCC(I, ISD::SETGE, ISD::SETUGE); } 00514 void visitSetLT(User &I) { visitSetCC(I, ISD::SETLT, ISD::SETULT); } 00515 void visitSetGT(User &I) { visitSetCC(I, ISD::SETGT, ISD::SETUGT); } 00516 00517 void visitExtractElement(User &I); 00518 void visitInsertElement(User &I); 00519 void visitShuffleVector(User &I); 00520 00521 void visitGetElementPtr(User &I); 00522 void visitCast(User &I); 00523 void visitSelect(User &I); 00524 00525 void visitMalloc(MallocInst &I); 00526 void visitFree(FreeInst &I); 00527 void visitAlloca(AllocaInst &I); 00528 void visitLoad(LoadInst &I); 00529 void visitStore(StoreInst &I); 00530 void visitPHI(PHINode &I) { } // PHI nodes are handled specially. 00531 void visitCall(CallInst &I); 00532 void visitInlineAsm(CallInst &I); 00533 const char *visitIntrinsicCall(CallInst &I, unsigned Intrinsic); 00534 void visitTargetIntrinsic(CallInst &I, unsigned Intrinsic); 00535 00536 void visitVAStart(CallInst &I); 00537 void visitVAArg(VAArgInst &I); 00538 void visitVAEnd(CallInst &I); 00539 void visitVACopy(CallInst &I); 00540 void visitFrameReturnAddress(CallInst &I, bool isFrameAddress); 00541 00542 void visitMemIntrinsic(CallInst &I, unsigned Op); 00543 00544 void visitUserOp1(Instruction &I) { 00545 assert(0 && "UserOp1 should not exist at instruction selection time!"); 00546 abort(); 00547 } 00548 void visitUserOp2(Instruction &I) { 00549 assert(0 && "UserOp2 should not exist at instruction selection time!"); 00550 abort(); 00551 } 00552 }; 00553 } // end namespace llvm 00554 00555 SDOperand SelectionDAGLowering::getValue(const Value *V) { 00556 SDOperand &N = NodeMap[V]; 00557 if (N.Val) return N; 00558 00559 const Type *VTy = V->getType(); 00560 MVT::ValueType VT = TLI.getValueType(VTy); 00561 if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) { 00562 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 00563 visit(CE->getOpcode(), *CE); 00564 assert(N.Val && "visit didn't populate the ValueMap!"); 00565 return N; 00566 } else if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) { 00567 return N = DAG.getGlobalAddress(GV, VT); 00568 } else if (isa<ConstantPointerNull>(C)) { 00569 return N = DAG.getConstant(0, TLI.getPointerTy()); 00570 } else if (isa<UndefValue>(C)) { 00571 if (!isa<PackedType>(VTy)) 00572 return N = DAG.getNode(ISD::UNDEF, VT); 00573 00574 // Create a VBUILD_VECTOR of undef nodes. 00575 const PackedType *PTy = cast<PackedType>(VTy); 00576 unsigned NumElements = PTy->getNumElements(); 00577 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType()); 00578 00579 std::vector<SDOperand> Ops; 00580 Ops.assign(NumElements, DAG.getNode(ISD::UNDEF, PVT)); 00581 00582 // Create a VConstant node with generic Vector type. 00583 Ops.push_back(DAG.getConstant(NumElements, MVT::i32)); 00584 Ops.push_back(DAG.getValueType(PVT)); 00585 return N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, Ops); 00586 } else if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) { 00587 return N = DAG.getConstantFP(CFP->getValue(), VT); 00588 } else if (const PackedType *PTy = dyn_cast<PackedType>(VTy)) { 00589 unsigned NumElements = PTy->getNumElements(); 00590 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType()); 00591 00592 // Now that we know the number and type of the elements, push a 00593 // Constant or ConstantFP node onto the ops list for each element of 00594 // the packed constant. 00595 std::vector<SDOperand> Ops; 00596 if (ConstantPacked *CP = dyn_cast<ConstantPacked>(C)) { 00597 for (unsigned i = 0; i != NumElements; ++i) 00598 Ops.push_back(getValue(CP->getOperand(i))); 00599 } else { 00600 assert(isa<ConstantAggregateZero>(C) && "Unknown packed constant!"); 00601 SDOperand Op; 00602 if (MVT::isFloatingPoint(PVT)) 00603 Op = DAG.getConstantFP(0, PVT); 00604 else 00605 Op = DAG.getConstant(0, PVT); 00606 Ops.assign(NumElements, Op); 00607 } 00608 00609 // Create a VBUILD_VECTOR node with generic Vector type. 00610 Ops.push_back(DAG.getConstant(NumElements, MVT::i32)); 00611 Ops.push_back(DAG.getValueType(PVT)); 00612 return N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, Ops); 00613 } else { 00614 // Canonicalize all constant ints to be unsigned. 00615 return N = DAG.getConstant(cast<ConstantIntegral>(C)->getRawValue(),VT); 00616 } 00617 } 00618 00619 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 00620 std::map<const AllocaInst*, int>::iterator SI = 00621 FuncInfo.StaticAllocaMap.find(AI); 00622 if (SI != FuncInfo.StaticAllocaMap.end()) 00623 return DAG.getFrameIndex(SI->second, TLI.getPointerTy()); 00624 } 00625 00626 std::map<const Value*, unsigned>::const_iterator VMI = 00627 FuncInfo.ValueMap.find(V); 00628 assert(VMI != FuncInfo.ValueMap.end() && "Value not in map!"); 00629 00630 unsigned InReg = VMI->second; 00631 00632 // If this type is not legal, make it so now. 00633 if (VT != MVT::Vector) { 00634 MVT::ValueType DestVT = TLI.getTypeToTransformTo(VT); 00635 00636 N = DAG.getCopyFromReg(DAG.getEntryNode(), InReg, DestVT); 00637 if (DestVT < VT) { 00638 // Source must be expanded. This input value is actually coming from the 00639 // register pair VMI->second and VMI->second+1. 00640 N = DAG.getNode(ISD::BUILD_PAIR, VT, N, 00641 DAG.getCopyFromReg(DAG.getEntryNode(), InReg+1, DestVT)); 00642 } else if (DestVT > VT) { // Promotion case 00643 if (MVT::isFloatingPoint(VT)) 00644 N = DAG.getNode(ISD::FP_ROUND, VT, N); 00645 else 00646 N = DAG.getNode(ISD::TRUNCATE, VT, N); 00647 } 00648 } else { 00649 // Otherwise, if this is a vector, make it available as a generic vector 00650 // here. 00651 MVT::ValueType PTyElementVT, PTyLegalElementVT; 00652 const PackedType *PTy = cast<PackedType>(VTy); 00653 unsigned NE = TLI.getPackedTypeBreakdown(PTy, PTyElementVT, 00654 PTyLegalElementVT); 00655 00656 // Build a VBUILD_VECTOR with the input registers. 00657 std::vector<SDOperand> Ops; 00658 if (PTyElementVT == PTyLegalElementVT) { 00659 // If the value types are legal, just VBUILD the CopyFromReg nodes. 00660 for (unsigned i = 0; i != NE; ++i) 00661 Ops.push_back(DAG.getCopyFromReg(DAG.getEntryNode(), InReg++, 00662 PTyElementVT)); 00663 } else if (PTyElementVT < PTyLegalElementVT) { 00664 // If the register was promoted, use TRUNCATE of FP_ROUND as appropriate. 00665 for (unsigned i = 0; i != NE; ++i) { 00666 SDOperand Op = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++, 00667 PTyElementVT); 00668 if (MVT::isFloatingPoint(PTyElementVT)) 00669 Op = DAG.getNode(ISD::FP_ROUND, PTyElementVT, Op); 00670 else 00671 Op = DAG.getNode(ISD::TRUNCATE, PTyElementVT, Op); 00672 Ops.push_back(Op); 00673 } 00674 } else { 00675 // If the register was expanded, use BUILD_PAIR. 00676 assert((NE & 1) == 0 && "Must expand into a multiple of 2 elements!"); 00677 for (unsigned i = 0; i != NE/2; ++i) { 00678 SDOperand Op0 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++, 00679 PTyElementVT); 00680 SDOperand Op1 = DAG.getCopyFromReg(DAG.getEntryNode(), InReg++, 00681 PTyElementVT); 00682 Ops.push_back(DAG.getNode(ISD::BUILD_PAIR, VT, Op0, Op1)); 00683 } 00684 } 00685 00686 Ops.push_back(DAG.getConstant(NE, MVT::i32)); 00687 Ops.push_back(DAG.getValueType(PTyLegalElementVT)); 00688 N = DAG.getNode(ISD::VBUILD_VECTOR, MVT::Vector, Ops); 00689 00690 // Finally, use a VBIT_CONVERT to make this available as the appropriate 00691 // vector type. 00692 N = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, N, 00693 DAG.getConstant(PTy->getNumElements(), 00694 MVT::i32), 00695 DAG.getValueType(TLI.getValueType(PTy->getElementType()))); 00696 } 00697 00698 return N; 00699 } 00700 00701 00702 void SelectionDAGLowering::visitRet(ReturnInst &I) { 00703 if (I.getNumOperands() == 0) { 00704 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, getRoot())); 00705 return; 00706 } 00707 std::vector<SDOperand> NewValues; 00708 NewValues.push_back(getRoot()); 00709 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 00710 SDOperand RetOp = getValue(I.getOperand(i)); 00711 00712 // If this is an integer return value, we need to promote it ourselves to 00713 // the full width of a register, since LegalizeOp will use ANY_EXTEND rather 00714 // than sign/zero. 00715 if (MVT::isInteger(RetOp.getValueType()) && 00716 RetOp.getValueType() < MVT::i64) { 00717 MVT::ValueType TmpVT; 00718 if (TLI.getTypeAction(MVT::i32) == TargetLowering::Promote) 00719 TmpVT = TLI.getTypeToTransformTo(MVT::i32); 00720 else 00721 TmpVT = MVT::i32; 00722 00723 if (I.getOperand(i)->getType()->isSigned()) 00724 RetOp = DAG.getNode(ISD::SIGN_EXTEND, TmpVT, RetOp); 00725 else 00726 RetOp = DAG.getNode(ISD::ZERO_EXTEND, TmpVT, RetOp); 00727 } 00728 NewValues.push_back(RetOp); 00729 } 00730 DAG.setRoot(DAG.getNode(ISD::RET, MVT::Other, NewValues)); 00731 } 00732 00733 void SelectionDAGLowering::visitBr(BranchInst &I) { 00734 // Update machine-CFG edges. 00735 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)]; 00736 CurMBB->addSuccessor(Succ0MBB); 00737 00738 // Figure out which block is immediately after the current one. 00739 MachineBasicBlock *NextBlock = 0; 00740 MachineFunction::iterator BBI = CurMBB; 00741 if (++BBI != CurMBB->getParent()->end()) 00742 NextBlock = BBI; 00743 00744 if (I.isUnconditional()) { 00745 // If this is not a fall-through branch, emit the branch. 00746 if (Succ0MBB != NextBlock) 00747 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(), 00748 DAG.getBasicBlock(Succ0MBB))); 00749 } else { 00750 MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)]; 00751 CurMBB->addSuccessor(Succ1MBB); 00752 00753 SDOperand Cond = getValue(I.getCondition()); 00754 if (Succ1MBB == NextBlock) { 00755 // If the condition is false, fall through. This means we should branch 00756 // if the condition is true to Succ #0. 00757 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), 00758 Cond, DAG.getBasicBlock(Succ0MBB))); 00759 } else if (Succ0MBB == NextBlock) { 00760 // If the condition is true, fall through. This means we should branch if 00761 // the condition is false to Succ #1. Invert the condition first. 00762 SDOperand True = DAG.getConstant(1, Cond.getValueType()); 00763 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True); 00764 DAG.setRoot(DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), 00765 Cond, DAG.getBasicBlock(Succ1MBB))); 00766 } else { 00767 std::vector<SDOperand> Ops; 00768 Ops.push_back(getRoot()); 00769 // If the false case is the current basic block, then this is a self 00770 // loop. We do not want to emit "Loop: ... brcond Out; br Loop", as it 00771 // adds an extra instruction in the loop. Instead, invert the 00772 // condition and emit "Loop: ... br!cond Loop; br Out. 00773 if (CurMBB == Succ1MBB) { 00774 std::swap(Succ0MBB, Succ1MBB); 00775 SDOperand True = DAG.getConstant(1, Cond.getValueType()); 00776 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True); 00777 } 00778 SDOperand True = DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), Cond, 00779 DAG.getBasicBlock(Succ0MBB)); 00780 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, True, 00781 DAG.getBasicBlock(Succ1MBB))); 00782 } 00783 } 00784 } 00785 00786 /// visitSwitchCase - Emits the necessary code to represent a single node in 00787 /// the binary search tree resulting from lowering a switch instruction. 00788 void SelectionDAGLowering::visitSwitchCase(SelectionDAGISel::CaseBlock &CB) { 00789 SDOperand SwitchOp = getValue(CB.SwitchV); 00790 SDOperand CaseOp = getValue(CB.CaseC); 00791 SDOperand Cond = DAG.getSetCC(MVT::i1, SwitchOp, CaseOp, CB.CC); 00792 00793 // Set NextBlock to be the MBB immediately after the current one, if any. 00794 // This is used to avoid emitting unnecessary branches to the next block. 00795 MachineBasicBlock *NextBlock = 0; 00796 MachineFunction::iterator BBI = CurMBB; 00797 if (++BBI != CurMBB->getParent()->end()) 00798 NextBlock = BBI; 00799 00800 // If the lhs block is the next block, invert the condition so that we can 00801 // fall through to the lhs instead of the rhs block. 00802 if (CB.LHSBB == NextBlock) { 00803 std::swap(CB.LHSBB, CB.RHSBB); 00804 SDOperand True = DAG.getConstant(1, Cond.getValueType()); 00805 Cond = DAG.getNode(ISD::XOR, Cond.getValueType(), Cond, True); 00806 } 00807 SDOperand BrCond = DAG.getNode(ISD::BRCOND, MVT::Other, getRoot(), Cond, 00808 DAG.getBasicBlock(CB.LHSBB)); 00809 if (CB.RHSBB == NextBlock) 00810 DAG.setRoot(BrCond); 00811 else 00812 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, BrCond, 00813 DAG.getBasicBlock(CB.RHSBB))); 00814 // Update successor info 00815 CurMBB->addSuccessor(CB.LHSBB); 00816 CurMBB->addSuccessor(CB.RHSBB); 00817 } 00818 00819 void SelectionDAGLowering::visitSwitch(SwitchInst &I) { 00820 // Figure out which block is immediately after the current one. 00821 MachineBasicBlock *NextBlock = 0; 00822 MachineFunction::iterator BBI = CurMBB; 00823 if (++BBI != CurMBB->getParent()->end()) 00824 NextBlock = BBI; 00825 00826 // If there is only the default destination, branch to it if it is not the 00827 // next basic block. Otherwise, just fall through. 00828 if (I.getNumOperands() == 2) { 00829 // Update machine-CFG edges. 00830 MachineBasicBlock *DefaultMBB = FuncInfo.MBBMap[I.getDefaultDest()]; 00831 // If this is not a fall-through branch, emit the branch. 00832 if (DefaultMBB != NextBlock) 00833 DAG.setRoot(DAG.getNode(ISD::BR, MVT::Other, getRoot(), 00834 DAG.getBasicBlock(DefaultMBB))); 00835 return; 00836 } 00837 00838 // If there are any non-default case statements, create a vector of Cases 00839 // representing each one, and sort the vector so that we can efficiently 00840 // create a binary search tree from them. 00841 std::vector<Case> Cases; 00842 for (unsigned i = 1; i < I.getNumSuccessors(); ++i) { 00843 MachineBasicBlock *SMBB = FuncInfo.MBBMap[I.getSuccessor(i)]; 00844 Cases.push_back(Case(I.getSuccessorValue(i), SMBB)); 00845 } 00846 std::sort(Cases.begin(), Cases.end(), CaseCmp()); 00847 00848 // Get the Value to be switched on and default basic blocks, which will be 00849 // inserted into CaseBlock records, representing basic blocks in the binary 00850 // search tree. 00851 Value *SV = I.getOperand(0); 00852 MachineBasicBlock *Default = FuncInfo.MBBMap[I.getDefaultDest()]; 00853 00854 // Get the current MachineFunction and LLVM basic block, for use in creating 00855 // and inserting new MBBs during the creation of the binary search tree. 00856 MachineFunction *CurMF = CurMBB->getParent(); 00857 const BasicBlock *LLVMBB = CurMBB->getBasicBlock(); 00858 00859 // Push the initial CaseRec onto the worklist 00860 std::vector<CaseRec> CaseVec; 00861 CaseVec.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end()))); 00862 00863 while (!CaseVec.empty()) { 00864 // Grab a record representing a case range to process off the worklist 00865 CaseRec CR = CaseVec.back(); 00866 CaseVec.pop_back(); 00867 00868 // Size is the number of Cases represented by this range. If Size is 1, 00869 // then we are processing a leaf of the binary search tree. Otherwise, 00870 // we need to pick a pivot, and push left and right ranges onto the 00871 // worklist. 00872 unsigned Size = CR.Range.second - CR.Range.first; 00873 00874 if (Size == 1) { 00875 // Create a CaseBlock record representing a conditional branch to 00876 // the Case's target mbb if the value being switched on SV is equal 00877 // to C. Otherwise, branch to default. 00878 Constant *C = CR.Range.first->first; 00879 MachineBasicBlock *Target = CR.Range.first->second; 00880 SelectionDAGISel::CaseBlock CB(ISD::SETEQ, SV, C, Target, Default, 00881 CR.CaseBB); 00882 // If the MBB representing the leaf node is the current MBB, then just 00883 // call visitSwitchCase to emit the code into the current block. 00884 // Otherwise, push the CaseBlock onto the vector to be later processed 00885 // by SDISel, and insert the node's MBB before the next MBB. 00886 if (CR.CaseBB == CurMBB) 00887 visitSwitchCase(CB); 00888 else { 00889 SwitchCases.push_back(CB); 00890 CurMF->getBasicBlockList().insert(BBI, CR.CaseBB); 00891 } 00892 } else { 00893 // split case range at pivot 00894 CaseItr Pivot = CR.Range.first + (Size / 2); 00895 CaseRange LHSR(CR.Range.first, Pivot); 00896 CaseRange RHSR(Pivot, CR.Range.second); 00897 Constant *C = Pivot->first; 00898 MachineBasicBlock *RHSBB = 0, *LHSBB = 0; 00899 // We know that we branch to the LHS if the Value being switched on is 00900 // less than the Pivot value, C. We use this to optimize our binary 00901 // tree a bit, by recognizing that if SV is greater than or equal to the 00902 // LHS's Case Value, and that Case Value is exactly one less than the 00903 // Pivot's Value, then we can branch directly to the LHS's Target, 00904 // rather than creating a leaf node for it. 00905 if ((LHSR.second - LHSR.first) == 1 && 00906 LHSR.first->first == CR.GE && 00907 cast<ConstantIntegral>(C)->getRawValue() == 00908 (cast<ConstantIntegral>(CR.GE)->getRawValue() + 1ULL)) { 00909 LHSBB = LHSR.first->second; 00910 } else { 00911 LHSBB = new MachineBasicBlock(LLVMBB); 00912 CaseVec.push_back(CaseRec(LHSBB,C,CR.GE,LHSR)); 00913 } 00914 // Similar to the optimization above, if the Value being switched on is 00915 // known to be less than the Constant CR.LT, and the current Case Value 00916 // is CR.LT - 1, then we can branch directly to the target block for 00917 // the current Case Value, rather than emitting a RHS leaf node for it. 00918 if ((RHSR.second - RHSR.first) == 1 && CR.LT && 00919 cast<ConstantIntegral>(RHSR.first->first)->getRawValue() == 00920 (cast<ConstantIntegral>(CR.LT)->getRawValue() - 1ULL)) { 00921 RHSBB = RHSR.first->second; 00922 } else { 00923 RHSBB = new MachineBasicBlock(LLVMBB); 00924 CaseVec.push_back(CaseRec(RHSBB,CR.LT,C,RHSR)); 00925 } 00926 // Create a CaseBlock record representing a conditional branch to 00927 // the LHS node if the value being switched on SV is less than C. 00928 // Otherwise, branch to LHS. 00929 ISD::CondCode CC = C->getType()->isSigned() ? ISD::SETLT : ISD::SETULT; 00930 SelectionDAGISel::CaseBlock CB(CC, SV, C, LHSBB, RHSBB, CR.CaseBB); 00931 if (CR.CaseBB == CurMBB) 00932 visitSwitchCase(CB); 00933 else { 00934 SwitchCases.push_back(CB); 00935 CurMF->getBasicBlockList().insert(BBI, CR.CaseBB); 00936 } 00937 } 00938 } 00939 } 00940 00941 void SelectionDAGLowering::visitSub(User &I) { 00942 // -0.0 - X --> fneg 00943 if (I.getType()->isFloatingPoint()) { 00944 if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0))) 00945 if (CFP->isExactlyValue(-0.0)) { 00946 SDOperand Op2 = getValue(I.getOperand(1)); 00947 setValue(&I, DAG.getNode(ISD::FNEG, Op2.getValueType(), Op2)); 00948 return; 00949 } 00950 } 00951 visitBinary(I, ISD::SUB, ISD::FSUB, ISD::VSUB); 00952 } 00953 00954 void SelectionDAGLowering::visitBinary(User &I, unsigned IntOp, unsigned FPOp, 00955 unsigned VecOp) { 00956 const Type *Ty = I.getType(); 00957 SDOperand Op1 = getValue(I.getOperand(0)); 00958 SDOperand Op2 = getValue(I.getOperand(1)); 00959 00960 if (Ty->isIntegral()) { 00961 setValue(&I, DAG.getNode(IntOp, Op1.getValueType(), Op1, Op2)); 00962 } else if (Ty->isFloatingPoint()) { 00963 setValue(&I, DAG.getNode(FPOp, Op1.getValueType(), Op1, Op2)); 00964 } else { 00965 const PackedType *PTy = cast<PackedType>(Ty); 00966 SDOperand Num = DAG.getConstant(PTy->getNumElements(), MVT::i32); 00967 SDOperand Typ = DAG.getValueType(TLI.getValueType(PTy->getElementType())); 00968 setValue(&I, DAG.getNode(VecOp, MVT::Vector, Op1, Op2, Num, Typ)); 00969 } 00970 } 00971 00972 void SelectionDAGLowering::visitShift(User &I, unsigned Opcode) { 00973 SDOperand Op1 = getValue(I.getOperand(0)); 00974 SDOperand Op2 = getValue(I.getOperand(1)); 00975 00976 Op2 = DAG.getNode(ISD::ANY_EXTEND, TLI.getShiftAmountTy(), Op2); 00977 00978 setValue(&I, DAG.getNode(Opcode, Op1.getValueType(), Op1, Op2)); 00979 } 00980 00981 void SelectionDAGLowering::visitSetCC(User &I,ISD::CondCode SignedOpcode, 00982 ISD::CondCode UnsignedOpcode) { 00983 SDOperand Op1 = getValue(I.getOperand(0)); 00984 SDOperand Op2 = getValue(I.getOperand(1)); 00985 ISD::CondCode Opcode = SignedOpcode; 00986 if (I.getOperand(0)->getType()->isUnsigned()) 00987 Opcode = UnsignedOpcode; 00988 setValue(&I, DAG.getSetCC(MVT::i1, Op1, Op2, Opcode)); 00989 } 00990 00991 void SelectionDAGLowering::visitSelect(User &I) { 00992 SDOperand Cond = getValue(I.getOperand(0)); 00993 SDOperand TrueVal = getValue(I.getOperand(1)); 00994 SDOperand FalseVal = getValue(I.getOperand(2)); 00995 if (!isa<PackedType>(I.getType())) { 00996 setValue(&I, DAG.getNode(ISD::SELECT, TrueVal.getValueType(), Cond, 00997 TrueVal, FalseVal)); 00998 } else { 00999 setValue(&I, DAG.getNode(ISD::VSELECT, MVT::Vector, Cond, TrueVal, FalseVal, 01000 *(TrueVal.Val->op_end()-2), 01001 *(TrueVal.Val->op_end()-1))); 01002 } 01003 } 01004 01005 void SelectionDAGLowering::visitCast(User &I) { 01006 SDOperand N = getValue(I.getOperand(0)); 01007 MVT::ValueType SrcVT = N.getValueType(); 01008 MVT::ValueType DestVT = TLI.getValueType(I.getType()); 01009 01010 if (DestVT == MVT::Vector) { 01011 // This is a cast to a vector from something else. This is always a bit 01012 // convert. Get information about the input vector. 01013 const PackedType *DestTy = cast<PackedType>(I.getType()); 01014 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType()); 01015 setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N, 01016 DAG.getConstant(DestTy->getNumElements(),MVT::i32), 01017 DAG.getValueType(EltVT))); 01018 } else if (SrcVT == DestVT) { 01019 setValue(&I, N); // noop cast. 01020 } else if (DestVT == MVT::i1) { 01021 // Cast to bool is a comparison against zero, not truncation to zero. 01022 SDOperand Zero = isInteger(SrcVT) ? DAG.getConstant(0, N.getValueType()) : 01023 DAG.getConstantFP(0.0, N.getValueType()); 01024 setValue(&I, DAG.getSetCC(MVT::i1, N, Zero, ISD::SETNE)); 01025 } else if (isInteger(SrcVT)) { 01026 if (isInteger(DestVT)) { // Int -> Int cast 01027 if (DestVT < SrcVT) // Truncating cast? 01028 setValue(&I, DAG.getNode(ISD::TRUNCATE, DestVT, N)); 01029 else if (I.getOperand(0)->getType()->isSigned()) 01030 setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, DestVT, N)); 01031 else 01032 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, DestVT, N)); 01033 } else if (isFloatingPoint(DestVT)) { // Int -> FP cast 01034 if (I.getOperand(0)->getType()->isSigned()) 01035 setValue(&I, DAG.getNode(ISD::SINT_TO_FP, DestVT, N)); 01036 else 01037 setValue(&I, DAG.getNode(ISD::UINT_TO_FP, DestVT, N)); 01038 } else { 01039 assert(0 && "Unknown cast!"); 01040 } 01041 } else if (isFloatingPoint(SrcVT)) { 01042 if (isFloatingPoint(DestVT)) { // FP -> FP cast 01043 if (DestVT < SrcVT) // Rounding cast? 01044 setValue(&I, DAG.getNode(ISD::FP_ROUND, DestVT, N)); 01045 else 01046 setValue(&I, DAG.getNode(ISD::FP_EXTEND, DestVT, N)); 01047 } else if (isInteger(DestVT)) { // FP -> Int cast. 01048 if (I.getType()->isSigned()) 01049 setValue(&I, DAG.getNode(ISD::FP_TO_SINT, DestVT, N)); 01050 else 01051 setValue(&I, DAG.getNode(ISD::FP_TO_UINT, DestVT, N)); 01052 } else { 01053 assert(0 && "Unknown cast!"); 01054 } 01055 } else { 01056 assert(SrcVT == MVT::Vector && "Unknown cast!"); 01057 assert(DestVT != MVT::Vector && "Casts to vector already handled!"); 01058 // This is a cast from a vector to something else. This is always a bit 01059 // convert. Get information about the input vector. 01060 setValue(&I, DAG.getNode(ISD::VBIT_CONVERT, DestVT, N)); 01061 } 01062 } 01063 01064 void SelectionDAGLowering::visitInsertElement(User &I) { 01065 SDOperand InVec = getValue(I.getOperand(0)); 01066 SDOperand InVal = getValue(I.getOperand(1)); 01067 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), 01068 getValue(I.getOperand(2))); 01069 01070 SDOperand Num = *(InVec.Val->op_end()-2); 01071 SDOperand Typ = *(InVec.Val->op_end()-1); 01072 setValue(&I, DAG.getNode(ISD::VINSERT_VECTOR_ELT, MVT::Vector, 01073 InVec, InVal, InIdx, Num, Typ)); 01074 } 01075 01076 void SelectionDAGLowering::visitExtractElement(User &I) { 01077 SDOperand InVec = getValue(I.getOperand(0)); 01078 SDOperand InIdx = DAG.getNode(ISD::ZERO_EXTEND, TLI.getPointerTy(), 01079 getValue(I.getOperand(1))); 01080 SDOperand Typ = *(InVec.Val->op_end()-1); 01081 setValue(&I, DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, 01082 TLI.getValueType(I.getType()), InVec, InIdx)); 01083 } 01084 01085 void SelectionDAGLowering::visitShuffleVector(User &I) { 01086 SDOperand V1 = getValue(I.getOperand(0)); 01087 SDOperand V2 = getValue(I.getOperand(1)); 01088 SDOperand Mask = getValue(I.getOperand(2)); 01089 01090 SDOperand Num = *(V1.Val->op_end()-2); 01091 SDOperand Typ = *(V2.Val->op_end()-1); 01092 setValue(&I, DAG.getNode(ISD::VVECTOR_SHUFFLE, MVT::Vector, 01093 V1, V2, Mask, Num, Typ)); 01094 } 01095 01096 01097 void SelectionDAGLowering::visitGetElementPtr(User &I) { 01098 SDOperand N = getValue(I.getOperand(0)); 01099 const Type *Ty = I.getOperand(0)->getType(); 01100 const Type *UIntPtrTy = TD.getIntPtrType(); 01101 01102 for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end(); 01103 OI != E; ++OI) { 01104 Value *Idx = *OI; 01105 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 01106 unsigned Field = cast<ConstantUInt>(Idx)->getValue(); 01107 if (Field) { 01108 // N = N + Offset 01109 uint64_t Offset = TD.getStructLayout(StTy)->MemberOffsets[Field]; 01110 N = DAG.getNode(ISD::ADD, N.getValueType(), N, 01111 getIntPtrConstant(Offset)); 01112 } 01113 Ty = StTy->getElementType(Field); 01114 } else { 01115 Ty = cast<SequentialType>(Ty)->getElementType(); 01116 01117 // If this is a constant subscript, handle it quickly. 01118 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 01119 if (CI->getRawValue() == 0) continue; 01120 01121 uint64_t Offs; 01122 if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(CI)) 01123 Offs = (int64_t)TD.getTypeSize(Ty)*CSI->getValue(); 01124 else 01125 Offs = TD.getTypeSize(Ty)*cast<ConstantUInt>(CI)->getValue(); 01126 N = DAG.getNode(ISD::ADD, N.getValueType(), N, getIntPtrConstant(Offs)); 01127 continue; 01128 } 01129 01130 // N = N + Idx * ElementSize; 01131 uint64_t ElementSize = TD.getTypeSize(Ty); 01132 SDOperand IdxN = getValue(Idx); 01133 01134 // If the index is smaller or larger than intptr_t, truncate or extend 01135 // it. 01136 if (IdxN.getValueType() < N.getValueType()) { 01137 if (Idx->getType()->isSigned()) 01138 IdxN = DAG.getNode(ISD::SIGN_EXTEND, N.getValueType(), IdxN); 01139 else 01140 IdxN = DAG.getNode(ISD::ZERO_EXTEND, N.getValueType(), IdxN); 01141 } else if (IdxN.getValueType() > N.getValueType()) 01142 IdxN = DAG.getNode(ISD::TRUNCATE, N.getValueType(), IdxN); 01143 01144 // If this is a multiply by a power of two, turn it into a shl 01145 // immediately. This is a very common case. 01146 if (isPowerOf2_64(ElementSize)) { 01147 unsigned Amt = Log2_64(ElementSize); 01148 IdxN = DAG.getNode(ISD::SHL, N.getValueType(), IdxN, 01149 DAG.getConstant(Amt, TLI.getShiftAmountTy())); 01150 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN); 01151 continue; 01152 } 01153 01154 SDOperand Scale = getIntPtrConstant(ElementSize); 01155 IdxN = DAG.getNode(ISD::MUL, N.getValueType(), IdxN, Scale); 01156 N = DAG.getNode(ISD::ADD, N.getValueType(), N, IdxN); 01157 } 01158 } 01159 setValue(&I, N); 01160 } 01161 01162 void SelectionDAGLowering::visitAlloca(AllocaInst &I) { 01163 // If this is a fixed sized alloca in the entry block of the function, 01164 // allocate it statically on the stack. 01165 if (FuncInfo.StaticAllocaMap.count(&I)) 01166 return; // getValue will auto-populate this. 01167 01168 const Type *Ty = I.getAllocatedType(); 01169 uint64_t TySize = TLI.getTargetData().getTypeSize(Ty); 01170 unsigned Align = std::max((unsigned)TLI.getTargetData().getTypeAlignment(Ty), 01171 I.getAlignment()); 01172 01173 SDOperand AllocSize = getValue(I.getArraySize()); 01174 MVT::ValueType IntPtr = TLI.getPointerTy(); 01175 if (IntPtr < AllocSize.getValueType()) 01176 AllocSize = DAG.getNode(ISD::TRUNCATE, IntPtr, AllocSize); 01177 else if (IntPtr > AllocSize.getValueType()) 01178 AllocSize = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, AllocSize); 01179 01180 AllocSize = DAG.getNode(ISD::MUL, IntPtr, AllocSize, 01181 getIntPtrConstant(TySize)); 01182 01183 // Handle alignment. If the requested alignment is less than or equal to the 01184 // stack alignment, ignore it and round the size of the allocation up to the 01185 // stack alignment size. If the size is greater than the stack alignment, we 01186 // note this in the DYNAMIC_STACKALLOC node. 01187 unsigned StackAlign = 01188 TLI.getTargetMachine().getFrameInfo()->getStackAlignment(); 01189 if (Align <= StackAlign) { 01190 Align = 0; 01191 // Add SA-1 to the size. 01192 AllocSize = DAG.getNode(ISD::ADD, AllocSize.getValueType(), AllocSize, 01193 getIntPtrConstant(StackAlign-1)); 01194 // Mask out the low bits for alignment purposes. 01195 AllocSize = DAG.getNode(ISD::AND, AllocSize.getValueType(), AllocSize, 01196 getIntPtrConstant(~(uint64_t)(StackAlign-1))); 01197 } 01198 01199 std::vector<MVT::ValueType> VTs; 01200 VTs.push_back(AllocSize.getValueType()); 01201 VTs.push_back(MVT::Other); 01202 std::vector<SDOperand> Ops; 01203 Ops.push_back(getRoot()); 01204 Ops.push_back(AllocSize); 01205 Ops.push_back(getIntPtrConstant(Align)); 01206 SDOperand DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, VTs, Ops); 01207 DAG.setRoot(setValue(&I, DSA).getValue(1)); 01208 01209 // Inform the Frame Information that we have just allocated a variable-sized 01210 // object. 01211 CurMBB->getParent()->getFrameInfo()->CreateVariableSizedObject(); 01212 } 01213 01214 void SelectionDAGLowering::visitLoad(LoadInst &I) { 01215 SDOperand Ptr = getValue(I.getOperand(0)); 01216 01217 SDOperand Root; 01218 if (I.isVolatile()) 01219 Root = getRoot(); 01220 else { 01221 // Do not serialize non-volatile loads against each other. 01222 Root = DAG.getRoot(); 01223 } 01224 01225 setValue(&I, getLoadFrom(I.getType(), Ptr, DAG.getSrcValue(I.getOperand(0)), 01226 Root, I.isVolatile())); 01227 } 01228 01229 SDOperand SelectionDAGLowering::getLoadFrom(const Type *Ty, SDOperand Ptr, 01230 SDOperand SrcValue, SDOperand Root, 01231 bool isVolatile) { 01232 SDOperand L; 01233 if (const PackedType *PTy = dyn_cast<PackedType>(Ty)) { 01234 MVT::ValueType PVT = TLI.getValueType(PTy->getElementType()); 01235 L = DAG.getVecLoad(PTy->getNumElements(), PVT, Root, Ptr, SrcValue); 01236 } else { 01237 L = DAG.getLoad(TLI.getValueType(Ty), Root, Ptr, SrcValue); 01238 } 01239 01240 if (isVolatile) 01241 DAG.setRoot(L.getValue(1)); 01242 else 01243 PendingLoads.push_back(L.getValue(1)); 01244 01245 return L; 01246 } 01247 01248 01249 void SelectionDAGLowering::visitStore(StoreInst &I) { 01250 Value *SrcV = I.getOperand(0); 01251 SDOperand Src = getValue(SrcV); 01252 SDOperand Ptr = getValue(I.getOperand(1)); 01253 DAG.setRoot(DAG.getNode(ISD::STORE, MVT::Other, getRoot(), Src, Ptr, 01254 DAG.getSrcValue(I.getOperand(1)))); 01255 } 01256 01257 /// IntrinsicCannotAccessMemory - Return true if the specified intrinsic cannot 01258 /// access memory and has no other side effects at all. 01259 static bool IntrinsicCannotAccessMemory(unsigned IntrinsicID) { 01260 #define GET_NO_MEMORY_INTRINSICS 01261 #include "llvm/Intrinsics.gen" 01262 #undef GET_NO_MEMORY_INTRINSICS 01263 return false; 01264 } 01265 01266 // IntrinsicOnlyReadsMemory - Return true if the specified intrinsic doesn't 01267 // have any side-effects or if it only reads memory. 01268 static bool IntrinsicOnlyReadsMemory(unsigned IntrinsicID) { 01269 #define GET_SIDE_EFFECT_INFO 01270 #include "llvm/Intrinsics.gen" 01271 #undef GET_SIDE_EFFECT_INFO 01272 return false; 01273 } 01274 01275 /// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC 01276 /// node. 01277 void SelectionDAGLowering::visitTargetIntrinsic(CallInst &I, 01278 unsigned Intrinsic) { 01279 bool HasChain = !IntrinsicCannotAccessMemory(Intrinsic); 01280 bool OnlyLoad = HasChain && IntrinsicOnlyReadsMemory(Intrinsic); 01281 01282 // Build the operand list. 01283 std::vector<SDOperand> Ops; 01284 if (HasChain) { // If this intrinsic has side-effects, chainify it. 01285 if (OnlyLoad) { 01286 // We don't need to serialize loads against other loads. 01287 Ops.push_back(DAG.getRoot()); 01288 } else { 01289 Ops.push_back(getRoot()); 01290 } 01291 } 01292 01293 // Add the intrinsic ID as an integer operand. 01294 Ops.push_back(DAG.getConstant(Intrinsic, TLI.getPointerTy())); 01295 01296 // Add all operands of the call to the operand list. 01297 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) { 01298 SDOperand Op = getValue(I.getOperand(i)); 01299 01300 // If this is a vector type, force it to the right packed type. 01301 if (Op.getValueType() == MVT::Vector) { 01302 const PackedType *OpTy = cast<PackedType>(I.getOperand(i)->getType()); 01303 MVT::ValueType EltVT = TLI.getValueType(OpTy->getElementType()); 01304 01305 MVT::ValueType VVT = MVT::getVectorType(EltVT, OpTy->getNumElements()); 01306 assert(VVT != MVT::Other && "Intrinsic uses a non-legal type?"); 01307 Op = DAG.getNode(ISD::VBIT_CONVERT, VVT, Op); 01308 } 01309 01310 assert(TLI.isTypeLegal(Op.getValueType()) && 01311 "Intrinsic uses a non-legal type?"); 01312 Ops.push_back(Op); 01313 } 01314 01315 std::vector<MVT::ValueType> VTs; 01316 if (I.getType() != Type::VoidTy) { 01317 MVT::ValueType VT = TLI.getValueType(I.getType()); 01318 if (VT == MVT::Vector) { 01319 const PackedType *DestTy = cast<PackedType>(I.getType()); 01320 MVT::ValueType EltVT = TLI.getValueType(DestTy->getElementType()); 01321 01322 VT = MVT::getVectorType(EltVT, DestTy->getNumElements()); 01323 assert(VT != MVT::Other && "Intrinsic uses a non-legal type?"); 01324 } 01325 01326 assert(TLI.isTypeLegal(VT) && "Intrinsic uses a non-legal type?"); 01327 VTs.push_back(VT); 01328 } 01329 if (HasChain) 01330 VTs.push_back(MVT::Other); 01331 01332 // Create the node. 01333 SDOperand Result; 01334 if (!HasChain) 01335 Result = DAG.getNode(ISD::INTRINSIC_WO_CHAIN, VTs, Ops); 01336 else if (I.getType() != Type::VoidTy) 01337 Result = DAG.getNode(ISD::INTRINSIC_W_CHAIN, VTs, Ops); 01338 else 01339 Result = DAG.getNode(ISD::INTRINSIC_VOID, VTs, Ops); 01340 01341 if (HasChain) { 01342 SDOperand Chain = Result.getValue(Result.Val->getNumValues()-1); 01343 if (OnlyLoad) 01344 PendingLoads.push_back(Chain); 01345 else 01346 DAG.setRoot(Chain); 01347 } 01348 if (I.getType() != Type::VoidTy) { 01349 if (const PackedType *PTy = dyn_cast<PackedType>(I.getType())) { 01350 MVT::ValueType EVT = TLI.getValueType(PTy->getElementType()); 01351 Result = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Result, 01352 DAG.getConstant(PTy->getNumElements(), MVT::i32), 01353 DAG.getValueType(EVT)); 01354 } 01355 setValue(&I, Result); 01356 } 01357 } 01358 01359 /// visitIntrinsicCall - Lower the call to the specified intrinsic function. If 01360 /// we want to emit this as a call to a named external function, return the name 01361 /// otherwise lower it and return null. 01362 const char * 01363 SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { 01364 switch (Intrinsic) { 01365 default: 01366 // By default, turn this into a target intrinsic node. 01367 visitTargetIntrinsic(I, Intrinsic); 01368 return 0; 01369 case Intrinsic::vastart: visitVAStart(I); return 0; 01370 case Intrinsic::vaend: visitVAEnd(I); return 0; 01371 case Intrinsic::vacopy: visitVACopy(I); return 0; 01372 case Intrinsic::returnaddress: visitFrameReturnAddress(I, false); return 0; 01373 case Intrinsic::frameaddress: visitFrameReturnAddress(I, true); return 0; 01374 case Intrinsic::setjmp: 01375 return "_setjmp"+!TLI.usesUnderscoreSetJmpLongJmp(); 01376 break; 01377 case Intrinsic::longjmp: 01378 return "_longjmp"+!TLI.usesUnderscoreSetJmpLongJmp(); 01379 break; 01380 case Intrinsic::memcpy_i32: 01381 case Intrinsic::memcpy_i64: 01382 visitMemIntrinsic(I, ISD::MEMCPY); 01383 return 0; 01384 case Intrinsic::memset_i32: 01385 case Intrinsic::memset_i64: 01386 visitMemIntrinsic(I, ISD::MEMSET); 01387 return 0; 01388 case Intrinsic::memmove_i32: 01389 case Intrinsic::memmove_i64: 01390 visitMemIntrinsic(I, ISD::MEMMOVE); 01391 return 0; 01392 01393 case Intrinsic::dbg_stoppoint: { 01394 MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo(); 01395 DbgStopPointInst &SPI = cast<DbgStopPointInst>(I); 01396 if (DebugInfo && SPI.getContext() && DebugInfo->Verify(SPI.getContext())) { 01397 std::vector<SDOperand> Ops; 01398 01399 Ops.push_back(getRoot()); 01400 Ops.push_back(getValue(SPI.getLineValue())); 01401 Ops.push_back(getValue(SPI.getColumnValue())); 01402 01403 DebugInfoDesc *DD = DebugInfo->getDescFor(SPI.getContext()); 01404 assert(DD && "Not a debug information descriptor"); 01405 CompileUnitDesc *CompileUnit = cast<CompileUnitDesc>(DD); 01406 01407 Ops.push_back(DAG.getString(CompileUnit->getFileName())); 01408 Ops.push_back(DAG.getString(CompileUnit->getDirectory())); 01409 01410 DAG.setRoot(DAG.getNode(ISD::LOCATION, MVT::Other, Ops)); 01411 } 01412 01413 return 0; 01414 } 01415 case Intrinsic::dbg_region_start: { 01416 MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo(); 01417 DbgRegionStartInst &RSI = cast<DbgRegionStartInst>(I); 01418 if (DebugInfo && RSI.getContext() && DebugInfo->Verify(RSI.getContext())) { 01419 std::vector<SDOperand> Ops; 01420 01421 unsigned LabelID = DebugInfo->RecordRegionStart(RSI.getContext()); 01422 01423 Ops.push_back(getRoot()); 01424 Ops.push_back(DAG.getConstant(LabelID, MVT::i32)); 01425 01426 DAG.setRoot(DAG.getNode(ISD::DEBUG_LABEL, MVT::Other, Ops)); 01427 } 01428 01429 return 0; 01430 } 01431 case Intrinsic::dbg_region_end: { 01432 MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo(); 01433 DbgRegionEndInst &REI = cast<DbgRegionEndInst>(I); 01434 if (DebugInfo && REI.getContext() && DebugInfo->Verify(REI.getContext())) { 01435 std::vector<SDOperand> Ops; 01436 01437 unsigned LabelID = DebugInfo->RecordRegionEnd(REI.getContext()); 01438 01439 Ops.push_back(getRoot()); 01440 Ops.push_back(DAG.getConstant(LabelID, MVT::i32)); 01441 01442 DAG.setRoot(DAG.getNode(ISD::DEBUG_LABEL, MVT::Other, Ops)); 01443 } 01444 01445 return 0; 01446 } 01447 case Intrinsic::dbg_func_start: { 01448 MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo(); 01449 DbgFuncStartInst &FSI = cast<DbgFuncStartInst>(I); 01450 if (DebugInfo && FSI.getSubprogram() && 01451 DebugInfo->Verify(FSI.getSubprogram())) { 01452 std::vector<SDOperand> Ops; 01453 01454 unsigned LabelID = DebugInfo->RecordRegionStart(FSI.getSubprogram()); 01455 01456 Ops.push_back(getRoot()); 01457 Ops.push_back(DAG.getConstant(LabelID, MVT::i32)); 01458 01459 DAG.setRoot(DAG.getNode(ISD::DEBUG_LABEL, MVT::Other, Ops)); 01460 } 01461 01462 return 0; 01463 } 01464 case Intrinsic::dbg_declare: { 01465 MachineDebugInfo *DebugInfo = DAG.getMachineDebugInfo(); 01466 DbgDeclareInst &DI = cast<DbgDeclareInst>(I); 01467 if (DebugInfo && DI.getVariable() && DebugInfo->Verify(DI.getVariable())) { 01468 std::vector<SDOperand> Ops; 01469 01470 SDOperand AddressOp = getValue(DI.getAddress()); 01471 if (FrameIndexSDNode *FI = dyn_cast<FrameIndexSDNode>(AddressOp)) { 01472 DebugInfo->RecordVariable(DI.getVariable(), FI->getIndex()); 01473 } 01474 } 01475 01476 return 0; 01477 } 01478 01479 case Intrinsic::isunordered_f32: 01480 case Intrinsic::isunordered_f64: 01481 setValue(&I, DAG.getSetCC(MVT::i1,getValue(I.getOperand(1)), 01482 getValue(I.getOperand(2)), ISD::SETUO)); 01483 return 0; 01484 01485 case Intrinsic::sqrt_f32: 01486 case Intrinsic::sqrt_f64: 01487 setValue(&I, DAG.getNode(ISD::FSQRT, 01488 getValue(I.getOperand(1)).getValueType(), 01489 getValue(I.getOperand(1)))); 01490 return 0; 01491 case Intrinsic::pcmarker: { 01492 SDOperand Tmp = getValue(I.getOperand(1)); 01493 DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Tmp)); 01494 return 0; 01495 } 01496 case Intrinsic::readcyclecounter: { 01497 std::vector<MVT::ValueType> VTs; 01498 VTs.push_back(MVT::i64); 01499 VTs.push_back(MVT::Other); 01500 std::vector<SDOperand> Ops; 01501 Ops.push_back(getRoot()); 01502 SDOperand Tmp = DAG.getNode(ISD::READCYCLECOUNTER, VTs, Ops); 01503 setValue(&I, Tmp); 01504 DAG.setRoot(Tmp.getValue(1)); 01505 return 0; 01506 } 01507 case Intrinsic::bswap_i16: 01508 case Intrinsic::bswap_i32: 01509 case Intrinsic::bswap_i64: 01510 setValue(&I, DAG.getNode(ISD::BSWAP, 01511 getValue(I.getOperand(1)).getValueType(), 01512 getValue(I.getOperand(1)))); 01513 return 0; 01514 case Intrinsic::cttz_i8: 01515 case Intrinsic::cttz_i16: 01516 case Intrinsic::cttz_i32: 01517 case Intrinsic::cttz_i64: 01518 setValue(&I, DAG.getNode(ISD::CTTZ, 01519 getValue(I.getOperand(1)).getValueType(), 01520 getValue(I.getOperand(1)))); 01521 return 0; 01522 case Intrinsic::ctlz_i8: 01523 case Intrinsic::ctlz_i16: 01524 case Intrinsic::ctlz_i32: 01525 case Intrinsic::ctlz_i64: 01526 setValue(&I, DAG.getNode(ISD::CTLZ, 01527 getValue(I.getOperand(1)).getValueType(), 01528 getValue(I.getOperand(1)))); 01529 return 0; 01530 case Intrinsic::ctpop_i8: 01531 case Intrinsic::ctpop_i16: 01532 case Intrinsic::ctpop_i32: 01533 case Intrinsic::ctpop_i64: 01534 setValue(&I, DAG.getNode(ISD::CTPOP, 01535 getValue(I.getOperand(1)).getValueType(), 01536 getValue(I.getOperand(1)))); 01537 return 0; 01538 case Intrinsic::stacksave: { 01539 std::vector<MVT::ValueType> VTs; 01540 VTs.push_back(TLI.getPointerTy()); 01541 VTs.push_back(MVT::Other); 01542 std::vector<SDOperand> Ops; 01543 Ops.push_back(getRoot()); 01544 SDOperand Tmp = DAG.getNode(ISD::STACKSAVE, VTs, Ops); 01545 setValue(&I, Tmp); 01546 DAG.setRoot(Tmp.getValue(1)); 01547 return 0; 01548 } 01549 case Intrinsic::stackrestore: { 01550 SDOperand Tmp = getValue(I.getOperand(1)); 01551 DAG.setRoot(DAG.getNode(ISD::STACKRESTORE, MVT::Other, getRoot(), Tmp)); 01552 return 0; 01553 } 01554 case Intrinsic::prefetch: 01555 // FIXME: Currently discarding prefetches. 01556 return 0; 01557 } 01558 } 01559 01560 01561 void SelectionDAGLowering::visitCall(CallInst &I) { 01562 const char *RenameFn = 0; 01563 if (Function *F = I.getCalledFunction()) { 01564 if (F->isExternal()) 01565 if (unsigned IID = F->getIntrinsicID()) { 01566 RenameFn = visitIntrinsicCall(I, IID); 01567 if (!RenameFn) 01568 return; 01569 } else { // Not an LLVM intrinsic. 01570 const std::string &Name = F->getName(); 01571 if (Name[0] == 'c' && (Name == "copysign" || Name == "copysignf")) { 01572 if (I.getNumOperands() == 3 && // Basic sanity checks. 01573 I.getOperand(1)->getType()->isFloatingPoint() && 01574 I.getType() == I.getOperand(1)->getType() && 01575 I.getType() == I.getOperand(2)->getType()) { 01576 SDOperand LHS = getValue(I.getOperand(1)); 01577 SDOperand RHS = getValue(I.getOperand(2)); 01578 setValue(&I, DAG.getNode(ISD::FCOPYSIGN, LHS.getValueType(), 01579 LHS, RHS)); 01580 return; 01581 } 01582 } else if (Name[0] == 'f' && (Name == "fabs" || Name == "fabsf")) { 01583 if (I.getNumOperands() == 2 && // Basic sanity checks. 01584 I.getOperand(1)->getType()->isFloatingPoint() && 01585 I.getType() == I.getOperand(1)->getType()) { 01586 SDOperand Tmp = getValue(I.getOperand(1)); 01587 setValue(&I, DAG.getNode(ISD::FABS, Tmp.getValueType(), Tmp)); 01588 return; 01589 } 01590 } else if (Name[0] == 's' && (Name == "sin" || Name == "sinf")) { 01591 if (I.getNumOperands() == 2 && // Basic sanity checks. 01592 I.getOperand(1)->getType()->isFloatingPoint() && 01593 I.getType() == I.getOperand(1)->getType()) { 01594 SDOperand Tmp = getValue(I.getOperand(1)); 01595 setValue(&I, DAG.getNode(ISD::FSIN, Tmp.getValueType(), Tmp)); 01596 return; 01597 } 01598 } else if (Name[0] == 'c' && (Name == "cos" || Name == "cosf")) { 01599 if (I.getNumOperands() == 2 && // Basic sanity checks. 01600 I.getOperand(1)->getType()->isFloatingPoint() && 01601 I.getType() == I.getOperand(1)->getType()) { 01602 SDOperand Tmp = getValue(I.getOperand(1)); 01603 setValue(&I, DAG.getNode(ISD::FCOS, Tmp.getValueType(), Tmp)); 01604 return; 01605 } 01606 } 01607 } 01608 } else if (isa<InlineAsm>(I.getOperand(0))) { 01609 visitInlineAsm(I); 01610 return; 01611 } 01612 01613 SDOperand Callee; 01614 if (!RenameFn) 01615 Callee = getValue(I.getOperand(0)); 01616 else 01617 Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy()); 01618 std::vector<std::pair<SDOperand, const Type*> > Args; 01619 Args.reserve(I.getNumOperands()); 01620 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) { 01621 Value *Arg = I.getOperand(i); 01622 SDOperand ArgNode = getValue(Arg); 01623 Args.push_back(std::make_pair(ArgNode, Arg->getType())); 01624 } 01625 01626 const PointerType *PT = cast<PointerType>(I.getCalledValue()->getType()); 01627 const FunctionType *FTy = cast<FunctionType>(PT->getElementType()); 01628 01629 std::pair<SDOperand,SDOperand> Result = 01630 TLI.LowerCallTo(getRoot(), I.getType(), FTy->isVarArg(), I.getCallingConv(), 01631 I.isTailCall(), Callee, Args, DAG); 01632 if (I.getType() != Type::VoidTy) 01633 setValue(&I, Result.first); 01634 DAG.setRoot(Result.second); 01635 } 01636 01637 SDOperand RegsForValue::getCopyFromRegs(SelectionDAG &DAG, 01638 SDOperand &Chain, SDOperand &Flag)const{ 01639 SDOperand Val = DAG.getCopyFromReg(Chain, Regs[0], RegVT, Flag); 01640 Chain = Val.getValue(1); 01641 Flag = Val.getValue(2); 01642 01643 // If the result was expanded, copy from the top part. 01644 if (Regs.size() > 1) { 01645 assert(Regs.size() == 2 && 01646 "Cannot expand to more than 2 elts yet!"); 01647 SDOperand Hi = DAG.getCopyFromReg(Chain, Regs[1], RegVT, Flag); 01648 Chain = Val.getValue(1); 01649 Flag = Val.getValue(2); 01650 if (DAG.getTargetLoweringInfo().isLittleEndian()) 01651 return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Val, Hi); 01652 else 01653 return DAG.getNode(ISD::BUILD_PAIR, ValueVT, Hi, Val); 01654 } 01655 01656 // Otherwise, if the return value was promoted, truncate it to the 01657 // appropriate type. 01658 if (RegVT == ValueVT) 01659 return Val; 01660 01661 if (MVT::isInteger(RegVT)) 01662 return DAG.getNode(ISD::TRUNCATE, ValueVT, Val); 01663 else 01664 return DAG.getNode(ISD::FP_ROUND, ValueVT, Val); 01665 } 01666 01667 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the 01668 /// specified value into the registers specified by this object. This uses 01669 /// Chain/Flag as the input and updates them for the output Chain/Flag. 01670 void RegsForValue::getCopyToRegs(SDOperand Val, SelectionDAG &DAG, 01671 SDOperand &Chain, SDOperand &Flag) const { 01672 if (Regs.size() == 1) { 01673 // If there is a single register and the types differ, this must be 01674 // a promotion. 01675 if (RegVT != ValueVT) { 01676 if (MVT::isInteger(RegVT)) 01677 Val = DAG.getNode(ISD::ANY_EXTEND, RegVT, Val); 01678 else 01679 Val = DAG.getNode(ISD::FP_EXTEND, RegVT, Val); 01680 } 01681 Chain = DAG.getCopyToReg(Chain, Regs[0], Val, Flag); 01682 Flag = Chain.getValue(1); 01683 } else { 01684 std::vector<unsigned> R(Regs); 01685 if (!DAG.getTargetLoweringInfo().isLittleEndian()) 01686 std::reverse(R.begin(), R.end()); 01687 01688 for (unsigned i = 0, e = R.size(); i != e; ++i) { 01689 SDOperand Part = DAG.getNode(ISD::EXTRACT_ELEMENT, RegVT, Val, 01690 DAG.getConstant(i, MVT::i32)); 01691 Chain = DAG.getCopyToReg(Chain, R[i], Part, Flag); 01692 Flag = Chain.getValue(1); 01693 } 01694 } 01695 } 01696 01697 /// AddInlineAsmOperands - Add this value to the specified inlineasm node 01698 /// operand list. This adds the code marker and includes the number of 01699 /// values added into it. 01700 void RegsForValue::AddInlineAsmOperands(unsigned Code, SelectionDAG &DAG, 01701 std::vector<SDOperand> &Ops) const { 01702 Ops.push_back(DAG.getConstant(Code | (Regs.size() << 3), MVT::i32)); 01703 for (unsigned i = 0, e = Regs.size(); i != e; ++i) 01704 Ops.push_back(DAG.getRegister(Regs[i], RegVT)); 01705 } 01706 01707 /// isAllocatableRegister - If the specified register is safe to allocate, 01708 /// i.e. it isn't a stack pointer or some other special register, return the 01709 /// register class for the register. Otherwise, return null. 01710 static const TargetRegisterClass * 01711 isAllocatableRegister(unsigned Reg, MachineFunction &MF, 01712 const TargetLowering &TLI, const MRegisterInfo *MRI) { 01713 MVT::ValueType FoundVT = MVT::Other; 01714 const TargetRegisterClass *FoundRC = 0; 01715 for (MRegisterInfo::regclass_iterator RCI = MRI->regclass_begin(), 01716 E = MRI->regclass_end(); RCI != E; ++RCI) { 01717 MVT::ValueType ThisVT = MVT::Other; 01718 01719 const TargetRegisterClass *RC = *RCI; 01720 // If none of the the value types for this register class are valid, we 01721 // can't use it. For example, 64-bit reg classes on 32-bit targets. 01722 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end(); 01723 I != E; ++I) { 01724 if (TLI.isTypeLegal(*I)) { 01725 // If we have already found this register in a different register class, 01726 // choose the one with the largest VT specified. For example, on 01727 // PowerPC, we favor f64 register classes over f32. 01728 if (FoundVT == MVT::Other || 01729 MVT::getSizeInBits(FoundVT) < MVT::getSizeInBits(*I)) { 01730 ThisVT = *I; 01731 break; 01732 } 01733 } 01734 } 01735 01736 if (ThisVT == MVT::Other) continue; 01737 01738 // NOTE: This isn't ideal. In particular, this might allocate the 01739 // frame pointer in functions that need it (due to them not being taken 01740 // out of allocation, because a variable sized allocation hasn't been seen 01741 // yet). This is a slight code pessimization, but should still work. 01742 for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF), 01743 E = RC->allocation_order_end(MF); I != E; ++I) 01744 if (*I == Reg) { 01745 // We found a matching register class. Keep looking at others in case 01746 // we find one with larger registers that this physreg is also in. 01747 FoundRC = RC; 01748 FoundVT = ThisVT; 01749 break; 01750 } 01751 } 01752 return FoundRC; 01753 } 01754 01755 RegsForValue SelectionDAGLowering:: 01756 GetRegistersForValue(const std::string &ConstrCode, 01757 MVT::ValueType VT, bool isOutReg, bool isInReg, 01758 std::set<unsigned> &OutputRegs, 01759 std::set<unsigned> &InputRegs) { 01760 std::pair<unsigned, const TargetRegisterClass*> PhysReg = 01761 TLI.getRegForInlineAsmConstraint(ConstrCode, VT); 01762 std::vector<unsigned> Regs; 01763 01764 unsigned NumRegs = VT != MVT::Other ? TLI.getNumElements(VT) : 1; 01765 MVT::ValueType RegVT; 01766 MVT::ValueType ValueVT = VT; 01767 01768 if (PhysReg.first) { 01769 if (VT == MVT::Other) 01770 ValueVT = *PhysReg.second->vt_begin(); 01771 RegVT = VT; 01772 01773 // This is a explicit reference to a physical register. 01774 Regs.push_back(PhysReg.first); 01775 01776 // If this is an expanded reference, add the rest of the regs to Regs. 01777 if (NumRegs != 1) { 01778 RegVT = *PhysReg.second->vt_begin(); 01779 TargetRegisterClass::iterator I = PhysReg.second->begin(); 01780 TargetRegisterClass::iterator E = PhysReg.second->end(); 01781 for (; *I != PhysReg.first; ++I) 01782 assert(I != E && "Didn't find reg!"); 01783 01784 // Already added the first reg. 01785 --NumRegs; ++I; 01786 for (; NumRegs; --NumRegs, ++I) { 01787 assert(I != E && "Ran out of registers to allocate!"); 01788 Regs.push_back(*I); 01789 } 01790 } 01791 return RegsForValue(Regs, RegVT, ValueVT); 01792 } 01793 01794 // This is a reference to a register class. Allocate NumRegs consecutive, 01795 // available, registers from the class. 01796 std::vector<unsigned> RegClassRegs = 01797 TLI.getRegClassForInlineAsmConstraint(ConstrCode, VT); 01798 01799 const MRegisterInfo *MRI = DAG.getTarget().getRegisterInfo(); 01800 MachineFunction &MF = *CurMBB->getParent(); 01801 unsigned NumAllocated = 0; 01802 for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) { 01803 unsigned Reg = RegClassRegs[i]; 01804 // See if this register is available. 01805 if ((isOutReg && OutputRegs.count(Reg)) || // Already used. 01806 (isInReg && InputRegs.count(Reg))) { // Already used. 01807 // Make sure we find consecutive registers. 01808 NumAllocated = 0; 01809 continue; 01810 } 01811 01812 // Check to see if this register is allocatable (i.e. don't give out the 01813 // stack pointer). 01814 const TargetRegisterClass *RC = isAllocatableRegister(Reg, MF, TLI, MRI); 01815 if (!RC) { 01816 // Make sure we find consecutive registers. 01817 NumAllocated = 0; 01818 continue; 01819 } 01820 01821 // Okay, this register is good, we can use it. 01822 ++NumAllocated; 01823 01824 // If we allocated enough consecutive 01825 if (NumAllocated == NumRegs) { 01826 unsigned RegStart = (i-NumAllocated)+1; 01827 unsigned RegEnd = i+1; 01828 // Mark all of the allocated registers used. 01829 for (unsigned i = RegStart; i != RegEnd; ++i) { 01830 unsigned Reg = RegClassRegs[i]; 01831 Regs.push_back(Reg); 01832 if (isOutReg) OutputRegs.insert(Reg); // Mark reg used. 01833 if (isInReg) InputRegs.insert(Reg); // Mark reg used. 01834 } 01835 01836 return RegsForValue(Regs, *RC->vt_begin(), VT); 01837 } 01838 } 01839 01840 // Otherwise, we couldn't allocate enough registers for this. 01841 return RegsForValue(); 01842 } 01843 01844 01845 /// visitInlineAsm - Handle a call to an InlineAsm object. 01846 /// 01847 void SelectionDAGLowering::visitInlineAsm(CallInst &I) { 01848 InlineAsm *IA = cast<InlineAsm>(I.getOperand(0)); 01849 01850 SDOperand AsmStr = DAG.getTargetExternalSymbol(IA->getAsmString().c_str(), 01851 MVT::Other); 01852 01853 // Note, we treat inline asms both with and without side-effects as the same. 01854 // If an inline asm doesn't have side effects and doesn't access memory, we 01855 // could not choose to not chain it. 01856 bool hasSideEffects = IA->hasSideEffects(); 01857 01858 std::vector<InlineAsm::ConstraintInfo> Constraints = IA->ParseConstraints(); 01859 std::vector<MVT::ValueType> ConstraintVTs; 01860 01861 /// AsmNodeOperands - A list of pairs. The first element is a register, the 01862 /// second is a bitfield where bit #0 is set if it is a use and bit #1 is set 01863 /// if it is a def of that register. 01864 std::vector<SDOperand> AsmNodeOperands; 01865 AsmNodeOperands.push_back(SDOperand()); // reserve space for input chain 01866 AsmNodeOperands.push_back(AsmStr); 01867 01868 SDOperand Chain = getRoot(); 01869 SDOperand Flag; 01870 01871 // We fully assign registers here at isel time. This is not optimal, but 01872 // should work. For register classes that correspond to LLVM classes, we 01873 // could let the LLVM RA do its thing, but we currently don't. Do a prepass 01874 // over the constraints, collecting fixed registers that we know we can't use. 01875 std::set<unsigned> OutputRegs, InputRegs; 01876 unsigned OpNum = 1; 01877 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { 01878 assert(Constraints[i].Codes.size() == 1 && "Only handles one code so far!"); 01879 std::string &ConstraintCode = Constraints[i].Codes[0]; 01880 01881 MVT::ValueType OpVT; 01882 01883 // Compute the value type for each operand and add it to ConstraintVTs. 01884 switch (Constraints[i].Type) { 01885 case InlineAsm::isOutput: 01886 if (!Constraints[i].isIndirectOutput) { 01887 assert(I.getType() != Type::VoidTy && "Bad inline asm!"); 01888 OpVT = TLI.getValueType(I.getType()); 01889 } else { 01890 const Type *OpTy = I.getOperand(OpNum)->getType(); 01891 OpVT = TLI.getValueType(cast<PointerType>(OpTy)->getElementType()); 01892 OpNum++; // Consumes a call operand. 01893 } 01894 break; 01895 case InlineAsm::isInput: 01896 OpVT = TLI.getValueType(I.getOperand(OpNum)->getType()); 01897 OpNum++; // Consumes a call operand. 01898 break; 01899 case InlineAsm::isClobber: 01900 OpVT = MVT::Other; 01901 break; 01902 } 01903 01904 ConstraintVTs.push_back(OpVT); 01905 01906 if (TLI.getRegForInlineAsmConstraint(ConstraintCode, OpVT).first == 0) 01907 continue; // Not assigned a fixed reg. 01908 01909 // Build a list of regs that this operand uses. This always has a single 01910 // element for promoted/expanded operands. 01911 RegsForValue Regs = GetRegistersForValue(ConstraintCode, OpVT, 01912 false, false, 01913 OutputRegs, InputRegs); 01914 01915 switch (Constraints[i].Type) { 01916 case InlineAsm::isOutput: 01917 // We can't assign any other output to this register. 01918 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 01919 // If this is an early-clobber output, it cannot be assigned to the same 01920 // value as the input reg. 01921 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput) 01922 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 01923 break; 01924 case InlineAsm::isInput: 01925 // We can't assign any other input to this register. 01926 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 01927 break; 01928 case InlineAsm::isClobber: 01929 // Clobbered regs cannot be used as inputs or outputs. 01930 InputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 01931 OutputRegs.insert(Regs.Regs.begin(), Regs.Regs.end()); 01932 break; 01933 } 01934 } 01935 01936 // Loop over all of the inputs, copying the operand values into the 01937 // appropriate registers and processing the output regs. 01938 RegsForValue RetValRegs; 01939 std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit; 01940 OpNum = 1; 01941 01942 for (unsigned i = 0, e = Constraints.size(); i != e; ++i) { 01943 assert(Constraints[i].Codes.size() == 1 && "Only handles one code so far!"); 01944 std::string &ConstraintCode = Constraints[i].Codes[0]; 01945 01946 switch (Constraints[i].Type) { 01947 case InlineAsm::isOutput: { 01948 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass; 01949 if (ConstraintCode.size() == 1) // not a physreg name. 01950 CTy = TLI.getConstraintType(ConstraintCode[0]); 01951 01952 if (CTy == TargetLowering::C_Memory) { 01953 // Memory output. 01954 SDOperand InOperandVal = getValue(I.getOperand(OpNum)); 01955 01956 // Check that the operand (the address to store to) isn't a float. 01957 if (!MVT::isInteger(InOperandVal.getValueType())) 01958 assert(0 && "MATCH FAIL!"); 01959 01960 if (!Constraints[i].isIndirectOutput) 01961 assert(0 && "MATCH FAIL!"); 01962 01963 OpNum++; // Consumes a call operand. 01964 01965 // Extend/truncate to the right pointer type if needed. 01966 MVT::ValueType PtrType = TLI.getPointerTy(); 01967 if (InOperandVal.getValueType() < PtrType) 01968 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal); 01969 else if (InOperandVal.getValueType() > PtrType) 01970 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal); 01971 01972 // Add information to the INLINEASM node to know about this output. 01973 unsigned ResOpType = 4/*MEM*/ | (1 << 3); 01974 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32)); 01975 AsmNodeOperands.push_back(InOperandVal); 01976 break; 01977 } 01978 01979 // Otherwise, this is a register output. 01980 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!"); 01981 01982 // If this is an early-clobber output, or if there is an input 01983 // constraint that matches this, we need to reserve the input register 01984 // so no other inputs allocate to it. 01985 bool UsesInputRegister = false; 01986 if (Constraints[i].isEarlyClobber || Constraints[i].hasMatchingInput) 01987 UsesInputRegister = true; 01988 01989 // Copy the output from the appropriate register. Find a register that 01990 // we can use. 01991 RegsForValue Regs = 01992 GetRegistersForValue(ConstraintCode, ConstraintVTs[i], 01993 true, UsesInputRegister, 01994 OutputRegs, InputRegs); 01995 assert(!Regs.Regs.empty() && "Couldn't allocate output reg!"); 01996 01997 if (!Constraints[i].isIndirectOutput) { 01998 assert(RetValRegs.Regs.empty() && 01999 "Cannot have multiple output constraints yet!"); 02000 assert(I.getType() != Type::VoidTy && "Bad inline asm!"); 02001 RetValRegs = Regs; 02002 } else { 02003 IndirectStoresToEmit.push_back(std::make_pair(Regs, 02004 I.getOperand(OpNum))); 02005 OpNum++; // Consumes a call operand. 02006 } 02007 02008 // Add information to the INLINEASM node to know that this register is 02009 // set. 02010 Regs.AddInlineAsmOperands(2 /*REGDEF*/, DAG, AsmNodeOperands); 02011 break; 02012 } 02013 case InlineAsm::isInput: { 02014 SDOperand InOperandVal = getValue(I.getOperand(OpNum)); 02015 OpNum++; // Consumes a call operand. 02016 02017 if (isdigit(ConstraintCode[0])) { // Matching constraint? 02018 // If this is required to match an output register we have already set, 02019 // just use its register. 02020 unsigned OperandNo = atoi(ConstraintCode.c_str()); 02021 02022 // Scan until we find the definition we already emitted of this operand. 02023 // When we find it, create a RegsForValue operand. 02024 unsigned CurOp = 2; // The first operand. 02025 for (; OperandNo; --OperandNo) { 02026 // Advance to the next operand. 02027 unsigned NumOps = 02028 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue(); 02029 assert((NumOps & 7) == 2 /*REGDEF*/ && 02030 "Skipped past definitions?"); 02031 CurOp += (NumOps>>3)+1; 02032 } 02033 02034 unsigned NumOps = 02035 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getValue(); 02036 assert((NumOps & 7) == 2 /*REGDEF*/ && 02037 "Skipped past definitions?"); 02038 02039 // Add NumOps>>3 registers to MatchedRegs. 02040 RegsForValue MatchedRegs; 02041 MatchedRegs.ValueVT = InOperandVal.getValueType(); 02042 MatchedRegs.RegVT = AsmNodeOperands[CurOp+1].getValueType(); 02043 for (unsigned i = 0, e = NumOps>>3; i != e; ++i) { 02044 unsigned Reg=cast<RegisterSDNode>(AsmNodeOperands[++CurOp])->getReg(); 02045 MatchedRegs.Regs.push_back(Reg); 02046 } 02047 02048 // Use the produced MatchedRegs object to 02049 MatchedRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag); 02050 MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, DAG, AsmNodeOperands); 02051 break; 02052 } 02053 02054 TargetLowering::ConstraintType CTy = TargetLowering::C_RegisterClass; 02055 if (ConstraintCode.size() == 1) // not a physreg name. 02056 CTy = TLI.getConstraintType(ConstraintCode[0]); 02057 02058 if (CTy == TargetLowering::C_Other) { 02059 if (!TLI.isOperandValidForConstraint(InOperandVal, ConstraintCode[0])) 02060 assert(0 && "MATCH FAIL!"); 02061 02062 // Add information to the INLINEASM node to know about this input. 02063 unsigned ResOpType = 3 /*IMM*/ | (1 << 3); 02064 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32)); 02065 AsmNodeOperands.push_back(InOperandVal); 02066 break; 02067 } else if (CTy == TargetLowering::C_Memory) { 02068 // Memory input. 02069 02070 // Check that the operand isn't a float. 02071 if (!MVT::isInteger(InOperandVal.getValueType())) 02072 assert(0 && "MATCH FAIL!"); 02073 02074 // Extend/truncate to the right pointer type if needed. 02075 MVT::ValueType PtrType = TLI.getPointerTy(); 02076 if (InOperandVal.getValueType() < PtrType) 02077 InOperandVal = DAG.getNode(ISD::ZERO_EXTEND, PtrType, InOperandVal); 02078 else if (InOperandVal.getValueType() > PtrType) 02079 InOperandVal = DAG.getNode(ISD::TRUNCATE, PtrType, InOperandVal); 02080 02081 // Add information to the INLINEASM node to know about this input. 02082 unsigned ResOpType = 4/*MEM*/ | (1 << 3); 02083 AsmNodeOperands.push_back(DAG.getConstant(ResOpType, MVT::i32)); 02084 AsmNodeOperands.push_back(InOperandVal); 02085 break; 02086 } 02087 02088 assert(CTy == TargetLowering::C_RegisterClass && "Unknown op type!"); 02089 02090 // Copy the input into the appropriate registers. 02091 RegsForValue InRegs = 02092 GetRegistersForValue(ConstraintCode, ConstraintVTs[i], 02093 false, true, OutputRegs, InputRegs); 02094 // FIXME: should be match fail. 02095 assert(!InRegs.Regs.empty() && "Couldn't allocate input reg!"); 02096 02097 InRegs.getCopyToRegs(InOperandVal, DAG, Chain, Flag); 02098 02099 InRegs.AddInlineAsmOperands(1/*REGUSE*/, DAG, AsmNodeOperands); 02100 break; 02101 } 02102 case InlineAsm::isClobber: { 02103 RegsForValue ClobberedRegs = 02104 GetRegistersForValue(ConstraintCode, MVT::Other, false, false, 02105 OutputRegs, InputRegs); 02106 // Add the clobbered value to the operand list, so that the register 02107 // allocator is aware that the physreg got clobbered. 02108 if (!ClobberedRegs.Regs.empty()) 02109 ClobberedRegs.AddInlineAsmOperands(2/*REGDEF*/, DAG, AsmNodeOperands); 02110 break; 02111 } 02112 } 02113 } 02114 02115 // Finish up input operands. 02116 AsmNodeOperands[0] = Chain; 02117 if (Flag.Val) AsmNodeOperands.push_back(Flag); 02118 02119 std::vector<MVT::ValueType> VTs; 02120 VTs.push_back(MVT::Other); 02121 VTs.push_back(MVT::Flag); 02122 Chain = DAG.getNode(ISD::INLINEASM, VTs, AsmNodeOperands); 02123 Flag = Chain.getValue(1); 02124 02125 // If this asm returns a register value, copy the result from that register 02126 // and set it as the value of the call. 02127 if (!RetValRegs.Regs.empty()) 02128 setValue(&I, RetValRegs.getCopyFromRegs(DAG, Chain, Flag)); 02129 02130 std::vector<std::pair<SDOperand, Value*> > StoresToEmit; 02131 02132 // Process indirect outputs, first output all of the flagged copies out of 02133 // physregs. 02134 for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) { 02135 RegsForValue &OutRegs = IndirectStoresToEmit[i].first; 02136 Value *Ptr = IndirectStoresToEmit[i].second; 02137 SDOperand OutVal = OutRegs.getCopyFromRegs(DAG, Chain, Flag); 02138 StoresToEmit.push_back(std::make_pair(OutVal, Ptr)); 02139 } 02140 02141 // Emit the non-flagged stores from the physregs. 02142 std::vector<SDOperand> OutChains; 02143 for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i) 02144 OutChains.push_back(DAG.getNode(ISD::STORE, MVT::Other, Chain, 02145 StoresToEmit[i].first, 02146 getValue(StoresToEmit[i].second), 02147 DAG.getSrcValue(StoresToEmit[i].second))); 02148 if (!OutChains.empty()) 02149 Chain = DAG.getNode(ISD::TokenFactor, MVT::Other, OutChains); 02150 DAG.setRoot(Chain); 02151 } 02152 02153 02154 void SelectionDAGLowering::visitMalloc(MallocInst &I) { 02155 SDOperand Src = getValue(I.getOperand(0)); 02156 02157 MVT::ValueType IntPtr = TLI.getPointerTy(); 02158 02159 if (IntPtr < Src.getValueType()) 02160 Src = DAG.getNode(ISD::TRUNCATE, IntPtr, Src); 02161 else if (IntPtr > Src.getValueType()) 02162 Src = DAG.getNode(ISD::ZERO_EXTEND, IntPtr, Src); 02163 02164 // Scale the source by the type size. 02165 uint64_t ElementSize = TD.getTypeSize(I.getType()->getElementType()); 02166 Src = DAG.getNode(ISD::MUL, Src.getValueType(), 02167 Src, getIntPtrConstant(ElementSize)); 02168 02169 std::vector<std::pair<SDOperand, const Type*> > Args; 02170 Args.push_back(std::make_pair(Src, TLI.getTargetData().getIntPtrType())); 02171 02172 std::pair<SDOperand,SDOperand> Result = 02173 TLI.LowerCallTo(getRoot(), I.getType(), false, CallingConv::C, true, 02174 DAG.getExternalSymbol("malloc", IntPtr), 02175 Args, DAG); 02176 setValue(&I, Result.first); // Pointers always fit in registers 02177 DAG.setRoot(Result.second); 02178 } 02179 02180 void SelectionDAGLowering::visitFree(FreeInst &I) { 02181 std::vector<std::pair<SDOperand, const Type*> > Args; 02182 Args.push_back(std::make_pair(getValue(I.getOperand(0)), 02183 TLI.getTargetData().getIntPtrType())); 02184 MVT::ValueType IntPtr = TLI.getPointerTy(); 02185 std::pair<SDOperand,SDOperand> Result = 02186 TLI.LowerCallTo(getRoot(), Type::VoidTy, false, CallingConv::C, true, 02187 DAG.getExternalSymbol("free", IntPtr), Args, DAG); 02188 DAG.setRoot(Result.second); 02189 } 02190 02191 // InsertAtEndOfBasicBlock - This method should be implemented by targets that 02192 // mark instructions with the 'usesCustomDAGSchedInserter' flag. These 02193 // instructions are special in various ways, which require special support to 02194 // insert. The specified MachineInstr is created but not inserted into any 02195 // basic blocks, and the scheduler passes ownership of it to this method. 02196 MachineBasicBlock *TargetLowering::InsertAtEndOfBasicBlock(MachineInstr *MI, 02197 MachineBasicBlock *MBB) { 02198 std::cerr << "If a target marks an instruction with " 02199 "'usesCustomDAGSchedInserter', it must implement " 02200 "TargetLowering::InsertAtEndOfBasicBlock!\n"; 02201 abort(); 02202 return 0; 02203 } 02204 02205 void SelectionDAGLowering::visitVAStart(CallInst &I) { 02206 DAG.setRoot(DAG.getNode(ISD::VASTART, MVT::Other, getRoot(), 02207 getValue(I.getOperand(1)), 02208 DAG.getSrcValue(I.getOperand(1)))); 02209 } 02210 02211 void SelectionDAGLowering::visitVAArg(VAArgInst &I) { 02212 SDOperand V = DAG.getVAArg(TLI.getValueType(I.getType()), getRoot(), 02213 getValue(I.getOperand(0)), 02214 DAG.getSrcValue(I.getOperand(0))); 02215 setValue(&I, V); 02216 DAG.setRoot(V.getValue(1)); 02217 } 02218 02219 void SelectionDAGLowering::visitVAEnd(CallInst &I) { 02220 DAG.setRoot(DAG.getNode(ISD::VAEND, MVT::Other, getRoot(), 02221 getValue(I.getOperand(1)), 02222 DAG.getSrcValue(I.getOperand(1)))); 02223 } 02224 02225 void SelectionDAGLowering::visitVACopy(CallInst &I) { 02226 DAG.setRoot(DAG.getNode(ISD::VACOPY, MVT::Other, getRoot(), 02227 getValue(I.getOperand(1)), 02228 getValue(I.getOperand(2)), 02229 DAG.getSrcValue(I.getOperand(1)), 02230 DAG.getSrcValue(I.getOperand(2)))); 02231 } 02232 02233 /// TargetLowering::LowerArguments - This is the default LowerArguments 02234 /// implementation, which just inserts a FORMAL_ARGUMENTS node. FIXME: When all 02235 /// targets are migrated to using FORMAL_ARGUMENTS, this hook should be removed. 02236 std::vector<SDOperand> 02237 TargetLowering::LowerArguments(Function &F, SelectionDAG &DAG) { 02238 // Add CC# and isVararg as operands to the FORMAL_ARGUMENTS node. 02239 std::vector<SDOperand> Ops; 02240 Ops.push_back(DAG.getConstant(F.getCallingConv(), getPointerTy())); 02241 Ops.push_back(DAG.getConstant(F.isVarArg(), getPointerTy())); 02242 02243 // Add one result value for each formal argument. 02244 std::vector<MVT::ValueType> RetVals; 02245 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) { 02246 MVT::ValueType VT = getValueType(I->getType()); 02247 02248 switch (getTypeAction(VT)) { 02249 default: assert(0 && "Unknown type action!"); 02250 case Legal: 02251 RetVals.push_back(VT); 02252 break; 02253 case Promote: 02254 RetVals.push_back(getTypeToTransformTo(VT)); 02255 break; 02256 case Expand: 02257 if (VT != MVT::Vector) { 02258 // If this is a large integer, it needs to be broken up into small 02259 // integers. Figure out what the destination type is and how many small 02260 // integers it turns into. 02261 MVT::ValueType NVT = getTypeToTransformTo(VT); 02262 unsigned NumVals = MVT::getSizeInBits(VT)/MVT::getSizeInBits(NVT); 02263 for (unsigned i = 0; i != NumVals; ++i) 02264 RetVals.push_back(NVT); 02265 } else { 02266 // Otherwise, this is a vector type. We only support legal vectors 02267 // right now. 02268 unsigned NumElems = cast<PackedType>(I->getType())->getNumElements(); 02269 const Type *EltTy = cast<PackedType>(I->getType())->getElementType(); 02270 02271 // Figure out if there is a Packed type corresponding to this Vector 02272 // type. If so, convert to the packed type. 02273 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems); 02274 if (TVT != MVT::Other && isTypeLegal(TVT)) { 02275 RetVals.push_back(TVT); 02276 } else { 02277 assert(0 && "Don't support illegal by-val vector arguments yet!"); 02278 } 02279 } 02280 break; 02281 } 02282 } 02283 02284 // Create the node. 02285 SDNode *Result = DAG.getNode(ISD::FORMAL_ARGUMENTS, RetVals, Ops).Val; 02286 02287 // Set up the return result vector. 02288 Ops.clear(); 02289 unsigned i = 0; 02290 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; ++I) { 02291 MVT::ValueType VT = getValueType(I->getType()); 02292 02293 switch (getTypeAction(VT)) { 02294 default: assert(0 && "Unknown type action!"); 02295 case Legal: 02296 Ops.push_back(SDOperand(Result, i++)); 02297 break; 02298 case Promote: { 02299 SDOperand Op(Result, i++); 02300 if (MVT::isInteger(VT)) { 02301 unsigned AssertOp = I->getType()->isSigned() ? ISD::AssertSext 02302 : ISD::AssertZext; 02303 Op = DAG.getNode(AssertOp, Op.getValueType(), Op, DAG.getValueType(VT)); 02304 Op = DAG.getNode(ISD::TRUNCATE, VT, Op); 02305 } else { 02306 assert(MVT::isFloatingPoint(VT) && "Not int or FP?"); 02307 Op = DAG.getNode(ISD::FP_ROUND, VT, Op); 02308 } 02309 Ops.push_back(Op); 02310 break; 02311 } 02312 case Expand: 02313 if (VT != MVT::Vector) { 02314 // If this is a large integer, it needs to be reassembled from small 02315 // integers. Figure out what the source elt type is and how many small 02316 // integers it is. 02317 MVT::ValueType NVT = getTypeToTransformTo(VT); 02318 unsigned NumVals = MVT::getSizeInBits(VT)/MVT::getSizeInBits(NVT); 02319 if (NumVals == 2) { 02320 SDOperand Lo = SDOperand(Result, i++); 02321 SDOperand Hi = SDOperand(Result, i++); 02322 02323 if (!isLittleEndian()) 02324 std::swap(Lo, Hi); 02325 02326 Ops.push_back(DAG.getNode(ISD::BUILD_PAIR, VT, Lo, Hi)); 02327 } else { 02328 // Value scalarized into many values. Unimp for now. 02329 assert(0 && "Cannot expand i64 -> i16 yet!"); 02330 } 02331 } else { 02332 // Otherwise, this is a vector type. We only support legal vectors 02333 // right now. 02334 unsigned NumElems = cast<PackedType>(I->getType())->getNumElements(); 02335 const Type *EltTy = cast<PackedType>(I->getType())->getElementType(); 02336 02337 // Figure out if there is a Packed type corresponding to this Vector 02338 // type. If so, convert to the packed type. 02339 MVT::ValueType TVT = MVT::getVectorType(getValueType(EltTy), NumElems); 02340 if (TVT != MVT::Other && isTypeLegal(TVT)) { 02341 Ops.push_back(SDOperand(Result, i++)); 02342 } else { 02343 assert(0 && "Don't support illegal by-val vector arguments yet!"); 02344 } 02345 } 02346 break; 02347 } 02348 } 02349 return Ops; 02350 } 02351 02352 // It is always conservatively correct for llvm.returnaddress and 02353 // llvm.frameaddress to return 0. 02354 std::pair<SDOperand, SDOperand> 02355 TargetLowering::LowerFrameReturnAddress(bool isFrameAddr, SDOperand Chain, 02356 unsigned Depth, SelectionDAG &DAG) { 02357 return std::make_pair(DAG.getConstant(0, getPointerTy()), Chain); 02358 } 02359 02360 SDOperand TargetLowering::LowerOperation(SDOperand Op, SelectionDAG &DAG) { 02361 assert(0 && "LowerOperation not implemented for this target!"); 02362 abort(); 02363 return SDOperand(); 02364 } 02365 02366 SDOperand TargetLowering::CustomPromoteOperation(SDOperand Op, 02367 SelectionDAG &DAG) { 02368 assert(0 && "CustomPromoteOperation not implemented for this target!"); 02369 abort(); 02370 return SDOperand(); 02371 } 02372 02373 void SelectionDAGLowering::visitFrameReturnAddress(CallInst &I, bool isFrame) { 02374 unsigned Depth = (unsigned)cast<ConstantUInt>(I.getOperand(1))->getValue(); 02375 std::pair<SDOperand,SDOperand> Result = 02376 TLI.LowerFrameReturnAddress(isFrame, getRoot(), Depth, DAG); 02377 setValue(&I, Result.first); 02378 DAG.setRoot(Result.second); 02379 } 02380 02381 /// getMemsetValue - Vectorized representation of the memset value 02382 /// operand. 02383 static SDOperand getMemsetValue(SDOperand Value, MVT::ValueType VT, 02384 SelectionDAG &DAG) { 02385 MVT::ValueType CurVT = VT; 02386 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Value)) { 02387 uint64_t Val = C->getValue() & 255; 02388 unsigned Shift = 8; 02389 while (CurVT != MVT::i8) { 02390 Val = (Val << Shift) | Val; 02391 Shift <<= 1; 02392 CurVT = (MVT::ValueType)((unsigned)CurVT - 1); 02393 } 02394 return DAG.getConstant(Val, VT); 02395 } else { 02396 Value = DAG.getNode(ISD::ZERO_EXTEND, VT, Value); 02397 unsigned Shift = 8; 02398 while (CurVT != MVT::i8) { 02399 Value = 02400 DAG.getNode(ISD::OR, VT, 02401 DAG.getNode(ISD::SHL, VT, Value, 02402 DAG.getConstant(Shift, MVT::i8)), Value); 02403 Shift <<= 1; 02404 CurVT = (MVT::ValueType)((unsigned)CurVT - 1); 02405 } 02406 02407 return Value; 02408 } 02409 } 02410 02411 /// getMemsetStringVal - Similar to getMemsetValue. Except this is only 02412 /// used when a memcpy is turned into a memset when the source is a constant 02413 /// string ptr. 02414 static SDOperand getMemsetStringVal(MVT::ValueType VT, 02415 SelectionDAG &DAG, TargetLowering &TLI, 02416 std::string &Str, unsigned Offset) { 02417 MVT::ValueType CurVT = VT; 02418 uint64_t Val = 0; 02419 unsigned MSB = getSizeInBits(VT) / 8; 02420 if (TLI.isLittleEndian()) 02421 Offset = Offset + MSB - 1; 02422 for (unsigned i = 0; i != MSB; ++i) { 02423 Val = (Val << 8) | Str[Offset]; 02424 Offset += TLI.isLittleEndian() ? -1 : 1; 02425 } 02426 return DAG.getConstant(Val, VT); 02427 } 02428 02429 /// getMemBasePlusOffset - Returns base and offset node for the 02430 static SDOperand getMemBasePlusOffset(SDOperand Base, unsigned Offset, 02431 SelectionDAG &DAG, TargetLowering &TLI) { 02432 MVT::ValueType VT = Base.getValueType(); 02433 return DAG.getNode(ISD::ADD, VT, Base, DAG.getConstant(Offset, VT)); 02434 } 02435 02436 /// MeetsMaxMemopRequirement - Determines if the number of memory ops required 02437 /// to replace the memset / memcpy is below the threshold. It also returns the 02438 /// types of the sequence of memory ops to perform memset / memcpy. 02439 static bool MeetsMaxMemopRequirement(std::vector<MVT::ValueType> &MemOps, 02440 unsigned Limit, uint64_t Size, 02441 unsigned Align, TargetLowering &TLI) { 02442 MVT::ValueType VT; 02443 02444 if (TLI.allowsUnalignedMemoryAccesses()) { 02445 VT = MVT::i64; 02446 } else { 02447 switch (Align & 7) { 02448 case 0: 02449 VT = MVT::i64; 02450 break; 02451 case 4: 02452 VT = MVT::i32; 02453 break; 02454 case 2: 02455 VT = MVT::i16; 02456 break; 02457 default: 02458 VT = MVT::i8; 02459 break; 02460 } 02461 } 02462 02463 MVT::ValueType LVT = MVT::i64; 02464 while (!TLI.isTypeLegal(LVT)) 02465 LVT = (MVT::ValueType)((unsigned)LVT - 1); 02466 assert(MVT::isInteger(LVT)); 02467 02468 if (VT > LVT) 02469 VT = LVT; 02470 02471 unsigned NumMemOps = 0; 02472 while (Size != 0) { 02473 unsigned VTSize = getSizeInBits(VT) / 8; 02474 while (VTSize > Size) { 02475 VT = (MVT::ValueType)((unsigned)VT - 1); 02476 VTSize >>= 1; 02477 } 02478 assert(MVT::isInteger(VT)); 02479 02480 if (++NumMemOps > Limit) 02481 return false; 02482 MemOps.push_back(VT); 02483 Size -= VTSize; 02484 } 02485 02486 return true; 02487 } 02488 02489 void SelectionDAGLowering::visitMemIntrinsic(CallInst &I, unsigned Op) { 02490 SDOperand Op1 = getValue(I.getOperand(1)); 02491 SDOperand Op2 = getValue(I.getOperand(2)); 02492 SDOperand Op3 = getValue(I.getOperand(3)); 02493 SDOperand Op4 = getValue(I.getOperand(4)); 02494 unsigned Align = (unsigned)cast<ConstantSDNode>(Op4)->getValue(); 02495 if (Align == 0) Align = 1; 02496 02497 if (ConstantSDNode *Size = dyn_cast<ConstantSDNode>(Op3)) { 02498 std::vector<MVT::ValueType> MemOps; 02499 02500 // Expand memset / memcpy to a series of load / store ops 02501 // if the size operand falls below a certain threshold. 02502 std::vector<SDOperand> OutChains; 02503 switch (Op) { 02504 default: break; // Do nothing for now. 02505 case ISD::MEMSET: { 02506 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemset(), 02507 Size->getValue(), Align, TLI)) { 02508 unsigned NumMemOps = MemOps.size(); 02509 unsigned Offset = 0; 02510 for (unsigned i = 0; i < NumMemOps; i++) { 02511 MVT::ValueType VT = MemOps[i]; 02512 unsigned VTSize = getSizeInBits(VT) / 8; 02513 SDOperand Value = getMemsetValue(Op2, VT, DAG); 02514 SDOperand Store = DAG.getNode(ISD::STORE, MVT::Other, getRoot(), 02515 Value, 02516 getMemBasePlusOffset(Op1, Offset, DAG, TLI), 02517 DAG.getSrcValue(I.getOperand(1), Offset)); 02518 OutChains.push_back(Store); 02519 Offset += VTSize; 02520 } 02521 } 02522 break; 02523 } 02524 case ISD::MEMCPY: { 02525 if (MeetsMaxMemopRequirement(MemOps, TLI.getMaxStoresPerMemcpy(), 02526 Size->getValue(), Align, TLI)) { 02527 unsigned NumMemOps = MemOps.size(); 02528 unsigned SrcOff = 0, DstOff = 0, SrcDelta = 0; 02529 GlobalAddressSDNode *G = NULL; 02530 std::string Str; 02531 bool CopyFromStr = false; 02532 02533 if (Op2.getOpcode() == ISD::GlobalAddress) 02534 G = cast<GlobalAddressSDNode>(Op2); 02535 else if (Op2.getOpcode() == ISD::ADD && 02536 Op2.getOperand(0).getOpcode() == ISD::GlobalAddress && 02537 Op2.getOperand(1).getOpcode() == ISD::Constant) { 02538 G = cast<GlobalAddressSDNode>(Op2.getOperand(0)); 02539 SrcDelta = cast<ConstantSDNode>(Op2.getOperand(1))->getValue(); 02540 } 02541 if (G) { 02542 GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getGlobal()); 02543 if (GV) { 02544 Str = GV->getStringValue(false); 02545 if (!Str.empty()) { 02546 CopyFromStr = true; 02547 SrcOff += SrcDelta; 02548 } 02549 } 02550 } 02551 02552 for (unsigned i = 0; i < NumMemOps; i++) { 02553 MVT::ValueType VT = MemOps[i]; 02554 unsigned VTSize = getSizeInBits(VT) / 8; 02555 SDOperand Value, Chain, Store; 02556 02557 if (CopyFromStr) { 02558 Value = getMemsetStringVal(VT, DAG, TLI, Str, SrcOff); 02559 Chain = getRoot(); 02560 Store = 02561 DAG.getNode(ISD::STORE, MVT::Other, Chain, Value, 02562 getMemBasePlusOffset(Op1, DstOff, DAG, TLI), 02563 DAG.getSrcValue(I.getOperand(1), DstOff)); 02564 } else { 02565 Value = DAG.getLoad(VT, getRoot(), 02566 getMemBasePlusOffset(Op2, SrcOff, DAG, TLI), 02567 DAG.getSrcValue(I.getOperand(2), SrcOff)); 02568 Chain = Value.getValue(1); 02569 Store = 02570 DAG.getNode(ISD::STORE, MVT::Other, Chain, Value, 02571 getMemBasePlusOffset(Op1, DstOff, DAG, TLI), 02572 DAG.getSrcValue(I.getOperand(1), DstOff)); 02573 } 02574 OutChains.push_back(Store); 02575 SrcOff += VTSize; 02576 DstOff += VTSize; 02577 } 02578 } 02579 break; 02580 } 02581 } 02582 02583 if (!OutChains.empty()) { 02584 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, OutChains)); 02585 return; 02586 } 02587 } 02588 02589 std::vector<SDOperand> Ops; 02590 Ops.push_back(getRoot()); 02591 Ops.push_back(Op1); 02592 Ops.push_back(Op2); 02593 Ops.push_back(Op3); 02594 Ops.push_back(Op4); 02595 DAG.setRoot(DAG.getNode(Op, MVT::Other, Ops)); 02596 } 02597 02598 //===----------------------------------------------------------------------===// 02599 // SelectionDAGISel code 02600 //===----------------------------------------------------------------------===// 02601 02602 unsigned SelectionDAGISel::MakeReg(MVT::ValueType VT) { 02603 return RegMap->createVirtualRegister(TLI.getRegClassFor(VT)); 02604 } 02605 02606 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { 02607 // FIXME: we only modify the CFG to split critical edges. This 02608 // updates dom and loop info. 02609 } 02610 02611 02612 /// InsertGEPComputeCode - Insert code into BB to compute Ptr+PtrOffset, 02613 /// casting to the type of GEPI. 02614 static Value *InsertGEPComputeCode(Value *&V, BasicBlock *BB, Instruction *GEPI, 02615 Value *Ptr, Value *PtrOffset) { 02616 if (V) return V; // Already computed. 02617 02618 BasicBlock::iterator InsertPt; 02619 if (BB == GEPI->getParent()) { 02620 // If insert into the GEP's block, insert right after the GEP. 02621 InsertPt = GEPI; 02622 ++InsertPt; 02623 } else { 02624 // Otherwise, insert at the top of BB, after any PHI nodes 02625 InsertPt = BB->begin(); 02626 while (isa<PHINode>(InsertPt)) ++InsertPt; 02627 } 02628 02629 // If Ptr is itself a cast, but in some other BB, emit a copy of the cast into 02630 // BB so that there is only one value live across basic blocks (the cast 02631 // operand). 02632 if (CastInst *CI = dyn_cast<CastInst>(Ptr)) 02633 if (CI->getParent() != BB && isa<PointerType>(CI->getOperand(0)->getType())) 02634 Ptr = new CastInst(CI->getOperand(0), CI->getType(), "", InsertPt); 02635 02636 // Add the offset, cast it to the right type. 02637 Ptr = BinaryOperator::createAdd(Ptr, PtrOffset, "", InsertPt); 02638 Ptr = new CastInst(Ptr, GEPI->getType(), "", InsertPt); 02639 return V = Ptr; 02640 } 02641 02642 02643 /// OptimizeGEPExpression - Since we are doing basic-block-at-a-time instruction 02644 /// selection, we want to be a bit careful about some things. In particular, if 02645 /// we have a GEP instruction that is used in a different block than it is 02646 /// defined, the addressing expression of the GEP cannot be folded into loads or 02647 /// stores that use it. In this case, decompose the GEP and move constant 02648 /// indices into blocks that use it. 02649 static void OptimizeGEPExpression(GetElementPtrInst *GEPI, 02650 const TargetData &TD) { 02651 // If this GEP is only used inside the block it is defined in, there is no 02652 // need to rewrite it. 02653 bool isUsedOutsideDefBB = false; 02654 BasicBlock *DefBB = GEPI->getParent(); 02655 for (Value::use_iterator UI = GEPI->use_begin(), E = GEPI->use_end(); 02656 UI != E; ++UI) { 02657 if (cast<Instruction>(*UI)->getParent() != DefBB) { 02658 isUsedOutsideDefBB = true; 02659 break; 02660 } 02661 } 02662 if (!isUsedOutsideDefBB) return; 02663 02664 // If this GEP has no non-zero constant indices, there is nothing we can do, 02665 // ignore it. 02666 bool hasConstantIndex = false; 02667 for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1, 02668 E = GEPI->op_end(); OI != E; ++OI) { 02669 if (ConstantInt *CI = dyn_cast<ConstantInt>(*OI)) 02670 if (CI->getRawValue()) { 02671 hasConstantIndex = true; 02672 break; 02673 } 02674 } 02675 // If this is a GEP &Alloca, 0, 0, forward subst the frame index into uses. 02676 if (!hasConstantIndex && !isa<AllocaInst>(GEPI->getOperand(0))) return; 02677 02678 // Otherwise, decompose the GEP instruction into multiplies and adds. Sum the 02679 // constant offset (which we now know is non-zero) and deal with it later. 02680 uint64_t ConstantOffset = 0; 02681 const Type *UIntPtrTy = TD.getIntPtrType(); 02682 Value *Ptr = new CastInst(GEPI->getOperand(0), UIntPtrTy, "", GEPI); 02683 const Type *Ty = GEPI->getOperand(0)->getType(); 02684 02685 for (GetElementPtrInst::op_iterator OI = GEPI->op_begin()+1, 02686 E = GEPI->op_end(); OI != E; ++OI) { 02687 Value *Idx = *OI; 02688 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 02689 unsigned Field = cast<ConstantUInt>(Idx)->getValue(); 02690 if (Field) 02691 ConstantOffset += TD.getStructLayout(StTy)->MemberOffsets[Field]; 02692 Ty = StTy->getElementType(Field); 02693 } else { 02694 Ty = cast<SequentialType>(Ty)->getElementType(); 02695 02696 // Handle constant subscripts. 02697 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 02698 if (CI->getRawValue() == 0) continue; 02699 02700 if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(CI)) 02701 ConstantOffset += (int64_t)TD.getTypeSize(Ty)*CSI->getValue(); 02702 else 02703 ConstantOffset+=TD.getTypeSize(Ty)*cast<ConstantUInt>(CI)->getValue(); 02704 continue; 02705 } 02706 02707 // Ptr = Ptr + Idx * ElementSize; 02708 02709 // Cast Idx to UIntPtrTy if needed. 02710 Idx = new CastInst(Idx, UIntPtrTy, "", GEPI); 02711 02712 uint64_t ElementSize = TD.getTypeSize(Ty); 02713 // Mask off bits that should not be set. 02714 ElementSize &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits()); 02715 Constant *SizeCst = ConstantUInt::get(UIntPtrTy, ElementSize); 02716 02717 // Multiply by the element size and add to the base. 02718 Idx = BinaryOperator::createMul(Idx, SizeCst, "", GEPI); 02719 Ptr = BinaryOperator::createAdd(Ptr, Idx, "", GEPI); 02720 } 02721 } 02722 02723 // Make sure that the offset fits in uintptr_t. 02724 ConstantOffset &= ~0ULL >> (64-UIntPtrTy->getPrimitiveSizeInBits()); 02725 Constant *PtrOffset = ConstantUInt::get(UIntPtrTy, ConstantOffset); 02726 02727 // Okay, we have now emitted all of the variable index parts to the BB that 02728 // the GEP is defined in. Loop over all of the using instructions, inserting 02729 // an "add Ptr, ConstantOffset" into each block that uses it and update the 02730 // instruction to use the newly computed value, making GEPI dead. When the 02731 // user is a load or store instruction address, we emit the add into the user 02732 // block, otherwise we use a canonical version right next to the gep (these 02733 // won't be foldable as addresses, so we might as well share the computation). 02734 02735 std::map<BasicBlock*,Value*> InsertedExprs; 02736 while (!GEPI->use_empty()) { 02737 Instruction *User = cast<Instruction>(GEPI->use_back()); 02738 02739 // If this use is not foldable into the addressing mode, use a version 02740 // emitted in the GEP block. 02741 Value *NewVal; 02742 if (!isa<LoadInst>(User) && 02743 (!isa<StoreInst>(User) || User->getOperand(0) == GEPI)) { 02744 NewVal = InsertGEPComputeCode(InsertedExprs[DefBB], DefBB, GEPI, 02745 Ptr, PtrOffset); 02746 } else { 02747 // Otherwise, insert the code in the User's block so it can be folded into 02748 // any users in that block. 02749 NewVal = InsertGEPComputeCode(InsertedExprs[User->getParent()], 02750 User->getParent(), GEPI, 02751 Ptr, PtrOffset); 02752 } 02753 User->replaceUsesOfWith(GEPI, NewVal); 02754 } 02755 02756 // Finally, the GEP is dead, remove it. 02757 GEPI->eraseFromParent(); 02758 } 02759 02760 bool SelectionDAGISel::runOnFunction(Function &Fn) { 02761 MachineFunction &MF = MachineFunction::construct(&Fn, TLI.getTargetMachine()); 02762 RegMap = MF.getSSARegMap(); 02763 DEBUG(std::cerr << "\n\n\n=== " << Fn.getName() << "\n"); 02764 02765 // First, split all critical edges for PHI nodes with incoming values that are 02766 // constants, this way the load of the constant into a vreg will not be placed 02767 // into MBBs that are used some other way. 02768 // 02769 // In this pass we also look for GEP instructions that are used across basic 02770 // blocks and rewrites them to improve basic-block-at-a-time selection. 02771 // 02772 for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 02773 PHINode *PN; 02774 BasicBlock::iterator BBI; 02775 for (BBI = BB->begin(); (PN = dyn_cast<PHINode>(BBI)); ++BBI) 02776 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 02777 if (isa<Constant>(PN->getIncomingValue(i))) 02778 SplitCriticalEdge(PN->getIncomingBlock(i), BB); 02779 02780 for (BasicBlock::iterator E = BB->end(); BBI != E; ) 02781 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(BBI++)) 02782 OptimizeGEPExpression(GEPI, TLI.getTargetData()); 02783 } 02784 02785 FunctionLoweringInfo FuncInfo(TLI, Fn, MF); 02786 02787 for (Function::iterator I = Fn.begin(), E = Fn.end(); I != E; ++I) 02788 SelectBasicBlock(I, MF, FuncInfo); 02789 02790 return true; 02791 } 02792 02793 02794 SDOperand SelectionDAGISel:: 02795 CopyValueToVirtualRegister(SelectionDAGLowering &SDL, Value *V, unsigned Reg) { 02796 SDOperand Op = SDL.getValue(V); 02797 assert((Op.getOpcode() != ISD::CopyFromReg || 02798 cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) && 02799 "Copy from a reg to the same reg!"); 02800 02801 // If this type is not legal, we must make sure to not create an invalid 02802 // register use. 02803 MVT::ValueType SrcVT = Op.getValueType(); 02804 MVT::ValueType DestVT = TLI.getTypeToTransformTo(SrcVT); 02805 SelectionDAG &DAG = SDL.DAG; 02806 if (SrcVT == DestVT) { 02807 return DAG.getCopyToReg(SDL.getRoot(), Reg, Op); 02808 } else if (SrcVT == MVT::Vector) { 02809 // Handle copies from generic vectors to registers. 02810 MVT::ValueType PTyElementVT, PTyLegalElementVT; 02811 unsigned NE = TLI.getPackedTypeBreakdown(cast<PackedType>(V->getType()), 02812 PTyElementVT, PTyLegalElementVT); 02813 02814 // Insert a VBIT_CONVERT of the input vector to a "N x PTyElementVT" 02815 // MVT::Vector type. 02816 Op = DAG.getNode(ISD::VBIT_CONVERT, MVT::Vector, Op, 02817 DAG.getConstant(NE, MVT::i32), 02818 DAG.getValueType(PTyElementVT)); 02819 02820 // Loop over all of the elements of the resultant vector, 02821 // VEXTRACT_VECTOR_ELT'ing them, converting them to PTyLegalElementVT, then 02822 // copying them into output registers. 02823 std::vector<SDOperand> OutChains; 02824 SDOperand Root = SDL.getRoot(); 02825 for (unsigned i = 0; i != NE; ++i) { 02826 SDOperand Elt = DAG.getNode(ISD::VEXTRACT_VECTOR_ELT, PTyElementVT, 02827 Op, DAG.getConstant(i, MVT::i32)); 02828 if (PTyElementVT == PTyLegalElementVT) { 02829 // Elements are legal. 02830 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt)); 02831 } else if (PTyLegalElementVT > PTyElementVT) { 02832 // Elements are promoted. 02833 if (MVT::isFloatingPoint(PTyLegalElementVT)) 02834 Elt = DAG.getNode(ISD::FP_EXTEND, PTyLegalElementVT, Elt); 02835 else 02836 Elt = DAG.getNode(ISD::ANY_EXTEND, PTyLegalElementVT, Elt); 02837 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Elt)); 02838 } else { 02839 // Elements are expanded. 02840 // The src value is expanded into multiple registers. 02841 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT, 02842 Elt, DAG.getConstant(0, MVT::i32)); 02843 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, PTyLegalElementVT, 02844 Elt, DAG.getConstant(1, MVT::i32)); 02845 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Lo)); 02846 OutChains.push_back(DAG.getCopyToReg(Root, Reg++, Hi)); 02847 } 02848 } 02849 return DAG.getNode(ISD::TokenFactor, MVT::Other, OutChains); 02850 } else if (SrcVT < DestVT) { 02851 // The src value is promoted to the register. 02852 if (MVT::isFloatingPoint(SrcVT)) 02853 Op = DAG.getNode(ISD::FP_EXTEND, DestVT, Op); 02854 else 02855 Op = DAG.getNode(ISD::ANY_EXTEND, DestVT, Op); 02856 return DAG.getCopyToReg(SDL.getRoot(), Reg, Op); 02857 } else { 02858 // The src value is expanded into multiple registers. 02859 SDOperand Lo = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT, 02860 Op, DAG.getConstant(0, MVT::i32)); 02861 SDOperand Hi = DAG.getNode(ISD::EXTRACT_ELEMENT, DestVT, 02862 Op, DAG.getConstant(1, MVT::i32)); 02863 Op = DAG.getCopyToReg(SDL.getRoot(), Reg, Lo); 02864 return DAG.getCopyToReg(Op, Reg+1, Hi); 02865 } 02866 } 02867 02868 void SelectionDAGISel:: 02869 LowerArguments(BasicBlock *BB, SelectionDAGLowering &SDL, 02870 std::vector<SDOperand> &UnorderedChains) { 02871 // If this is the entry block, emit arguments. 02872 Function &F = *BB->getParent(); 02873 FunctionLoweringInfo &FuncInfo = SDL.FuncInfo; 02874 SDOperand OldRoot = SDL.DAG.getRoot(); 02875 std::vector<SDOperand> Args = TLI.LowerArguments(F, SDL.DAG); 02876 02877 unsigned a = 0; 02878 for (Function::arg_iterator AI = F.arg_begin(), E = F.arg_end(); 02879 AI != E; ++AI, ++a) 02880 if (!AI->use_empty()) { 02881 SDL.setValue(AI, Args[a]); 02882 02883 // If this argument is live outside of the entry block, insert a copy from 02884 // whereever we got it to the vreg that other BB's will reference it as. 02885 if (FuncInfo.ValueMap.count(AI)) { 02886 SDOperand Copy = 02887 CopyValueToVirtualRegister(SDL, AI, FuncInfo.ValueMap[AI]); 02888 UnorderedChains.push_back(Copy); 02889 } 02890 } 02891 02892 // Next, if the function has live ins that need to be copied into vregs, 02893 // emit the copies now, into the top of the block. 02894 MachineFunction &MF = SDL.DAG.getMachineFunction(); 02895 if (MF.livein_begin() != MF.livein_end()) { 02896 SSARegMap *RegMap = MF.getSSARegMap(); 02897 const MRegisterInfo &MRI = *MF.getTarget().getRegisterInfo(); 02898 for (MachineFunction::livein_iterator LI = MF.livein_begin(), 02899 E = MF.livein_end(); LI != E; ++LI) 02900 if (LI->second) 02901 MRI.copyRegToReg(*MF.begin(), MF.begin()->end(), LI->second, 02902 LI->first, RegMap->getRegClass(LI->second)); 02903 } 02904 02905 // Finally, if the target has anything special to do, allow it to do so. 02906 EmitFunctionEntryCode(F, SDL.DAG.getMachineFunction()); 02907 } 02908 02909 02910 void SelectionDAGISel::BuildSelectionDAG(SelectionDAG &DAG, BasicBlock *LLVMBB, 02911 std::vector<std::pair<MachineInstr*, unsigned> > &PHINodesToUpdate, 02912 FunctionLoweringInfo &FuncInfo) { 02913 SelectionDAGLowering SDL(DAG, TLI, FuncInfo); 02914 02915 std::vector<SDOperand> UnorderedChains; 02916 02917 // Lower any arguments needed in this block if this is the entry block. 02918 if (LLVMBB == &LLVMBB->getParent()->front()) 02919 LowerArguments(LLVMBB, SDL, UnorderedChains); 02920 02921 BB = FuncInfo.MBBMap[LLVMBB]; 02922 SDL.setCurrentBasicBlock(BB); 02923 02924 // Lower all of the non-terminator instructions. 02925 for (BasicBlock::iterator I = LLVMBB->begin(), E = --LLVMBB->end(); 02926 I != E; ++I) 02927 SDL.visit(*I); 02928 02929 // Ensure that all instructions which are used outside of their defining 02930 // blocks are available as virtual registers. 02931 for (BasicBlock::iterator I = LLVMBB->begin(), E = LLVMBB->end(); I != E;++I) 02932 if (!I->use_empty() && !isa<PHINode>(I)) { 02933 std::map<const Value*, unsigned>::iterator VMI =FuncInfo.ValueMap.find(I); 02934 if (VMI != FuncInfo.ValueMap.end()) 02935 UnorderedChains.push_back( 02936 CopyValueToVirtualRegister(SDL, I, VMI->second)); 02937 } 02938 02939 // Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to 02940 // ensure constants are generated when needed. Remember the virtual registers 02941 // that need to be added to the Machine PHI nodes as input. We cannot just 02942 // directly add them, because expansion might result in multiple MBB's for one 02943 // BB. As such, the start of the BB might correspond to a different MBB than 02944 // the end. 02945 // 02946 02947 // Emit constants only once even if used by multiple PHI nodes. 02948 std::map<Constant*, unsigned> ConstantsOut; 02949 02950 // Check successor nodes PHI nodes that expect a constant to be available from 02951 // this block. 02952 TerminatorInst *TI = LLVMBB->getTerminator(); 02953 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { 02954 BasicBlock *SuccBB = TI->getSuccessor(succ); 02955 MachineBasicBlock::iterator MBBI = FuncInfo.MBBMap[SuccBB]->begin(); 02956 PHINode *PN; 02957 02958 // At this point we know that there is a 1-1 correspondence between LLVM PHI 02959 // nodes and Machine PHI nodes, but the incoming operands have not been 02960 // emitted yet. 02961 for (BasicBlock::iterator I = SuccBB->begin(); 02962 (PN = dyn_cast<PHINode>(I)); ++I) 02963 if (!PN->use_empty()) { 02964 unsigned Reg; 02965 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 02966 if (Constant *C = dyn_cast<Constant>(PHIOp)) { 02967 unsigned &RegOut = ConstantsOut[C]; 02968 if (RegOut == 0) { 02969 RegOut = FuncInfo.CreateRegForValue(C); 02970 UnorderedChains.push_back( 02971 CopyValueToVirtualRegister(SDL, C, RegOut)); 02972 } 02973 Reg = RegOut; 02974 } else { 02975 Reg = FuncInfo.ValueMap[PHIOp]; 02976 if (Reg == 0) { 02977 assert(isa<AllocaInst>(PHIOp) && 02978 FuncInfo.StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) && 02979 "Didn't codegen value into a register!??"); 02980 Reg = FuncInfo.CreateRegForValue(PHIOp); 02981 UnorderedChains.push_back( 02982 CopyValueToVirtualRegister(SDL, PHIOp, Reg)); 02983 } 02984 } 02985 02986 // Remember that this register needs to added to the machine PHI node as 02987 // the input for this MBB. 02988 MVT::ValueType VT = TLI.getValueType(PN->getType()); 02989 unsigned NumElements; 02990 if (VT != MVT::Vector) 02991 NumElements = TLI.getNumElements(VT); 02992 else { 02993 MVT::ValueType VT1,VT2; 02994 NumElements = 02995 TLI.getPackedTypeBreakdown(cast<PackedType>(PN->getType()), 02996 VT1, VT2); 02997 } 02998 for (unsigned i = 0, e = NumElements; i != e; ++i) 02999 PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i)); 03000 } 03001 } 03002 ConstantsOut.clear(); 03003 03004 // Turn all of the unordered chains into one factored node. 03005 if (!UnorderedChains.empty()) { 03006 SDOperand Root = SDL.getRoot(); 03007 if (Root.getOpcode() != ISD::EntryToken) { 03008 unsigned i = 0, e = UnorderedChains.size(); 03009 for (; i != e; ++i) { 03010 assert(UnorderedChains[i].Val->getNumOperands() > 1); 03011 if (UnorderedChains[i].Val->getOperand(0) == Root) 03012 break; // Don't add the root if we already indirectly depend on it. 03013 } 03014 03015 if (i == e) 03016 UnorderedChains.push_back(Root); 03017 } 03018 DAG.setRoot(DAG.getNode(ISD::TokenFactor, MVT::Other, UnorderedChains)); 03019 } 03020 03021 // Lower the terminator after the copies are emitted. 03022 SDL.visit(*LLVMBB->getTerminator()); 03023 03024 // Copy over any CaseBlock records that may now exist due to SwitchInst 03025 // lowering. 03026 SwitchCases.clear(); 03027 SwitchCases = SDL.SwitchCases; 03028 03029 // Make sure the root of the DAG is up-to-date. 03030 DAG.setRoot(SDL.getRoot()); 03031 } 03032 03033 void SelectionDAGISel::CodeGenAndEmitDAG(SelectionDAG &DAG) { 03034 // Run the DAG combiner in pre-legalize mode. 03035 DAG.Combine(false); 03036 03037 DEBUG(std::cerr << "Lowered selection DAG:\n"); 03038 DEBUG(DAG.dump()); 03039 03040 // Second step, hack on the DAG until it only uses operations and types that 03041 // the target supports. 03042 DAG.Legalize(); 03043 03044 DEBUG(std::cerr << "Legalized selection DAG:\n"); 03045 DEBUG(DAG.dump()); 03046 03047 // Run the DAG combiner in post-legalize mode. 03048 DAG.Combine(true); 03049 03050 if (ViewISelDAGs) DAG.viewGraph(); 03051 03052 // Third, instruction select all of the operations to machine code, adding the 03053 // code to the MachineBasicBlock. 03054 InstructionSelectBasicBlock(DAG); 03055 03056 DEBUG(std::cerr << "Selected machine code:\n"); 03057 DEBUG(BB->dump()); 03058 } 03059 03060 void SelectionDAGISel::SelectBasicBlock(BasicBlock *LLVMBB, MachineFunction &MF, 03061 FunctionLoweringInfo &FuncInfo) { 03062 std::vector<std::pair<MachineInstr*, unsigned> > PHINodesToUpdate; 03063 { 03064 SelectionDAG DAG(TLI, MF, getAnalysisToUpdate<MachineDebugInfo>()); 03065 CurDAG = &DAG; 03066 03067 // First step, lower LLVM code to some DAG. This DAG may use operations and 03068 // types that are not supported by the target. 03069 BuildSelectionDAG(DAG, LLVMBB, PHINodesToUpdate, FuncInfo); 03070 03071 // Second step, emit the lowered DAG as machine code. 03072 CodeGenAndEmitDAG(DAG); 03073 } 03074 03075 // Next, now that we know what the last MBB the LLVM BB expanded is, update 03076 // PHI nodes in successors. 03077 if (SwitchCases.empty()) { 03078 for (unsigned i = 0, e = PHINodesToUpdate.size(); i != e; ++i) { 03079 MachineInstr *PHI = PHINodesToUpdate[i].first; 03080 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 03081 "This is not a machine PHI node that we are updating!"); 03082 PHI->addRegOperand(PHINodesToUpdate[i].second); 03083 PHI->addMachineBasicBlockOperand(BB); 03084 } 03085 return; 03086 } 03087 03088 // If we generated any switch lowering information, build and codegen any 03089 // additional DAGs necessary. 03090 for(unsigned i = 0, e = SwitchCases.size(); i != e; ++i) { 03091 SelectionDAG SDAG(TLI, MF, getAnalysisToUpdate<MachineDebugInfo>()); 03092 CurDAG = &SDAG; 03093 SelectionDAGLowering SDL(SDAG, TLI, FuncInfo); 03094 // Set the current basic block to the mbb we wish to insert the code into 03095 BB = SwitchCases[i].ThisBB; 03096 SDL.setCurrentBasicBlock(BB); 03097 // Emit the code 03098 SDL.visitSwitchCase(SwitchCases[i]); 03099 SDAG.setRoot(SDL.getRoot()); 03100 CodeGenAndEmitDAG(SDAG); 03101 // Iterate over the phi nodes, if there is a phi node in a successor of this 03102 // block (for instance, the default block), then add a pair of operands to 03103 // the phi node for this block, as if we were coming from the original 03104 // BB before switch expansion. 03105 for (unsigned pi = 0, pe = PHINodesToUpdate.size(); pi != pe; ++pi) { 03106 MachineInstr *PHI = PHINodesToUpdate[pi].first; 03107 MachineBasicBlock *PHIBB = PHI->getParent(); 03108 assert(PHI->getOpcode() == TargetInstrInfo::PHI && 03109 "This is not a machine PHI node that we are updating!"); 03110 if (PHIBB == SwitchCases[i].LHSBB || PHIBB == SwitchCases[i].RHSBB) { 03111 PHI->addRegOperand(PHINodesToUpdate[pi].second); 03112 PHI->addMachineBasicBlockOperand(BB); 03113 } 03114 } 03115 } 03116 } 03117 03118 //===----------------------------------------------------------------------===// 03119 /// ScheduleAndEmitDAG - Pick a safe ordering and emit instructions for each 03120 /// target node in the graph. 03121 void SelectionDAGISel::ScheduleAndEmitDAG(SelectionDAG &DAG) { 03122 if (ViewSchedDAGs) DAG.viewGraph(); 03123 ScheduleDAG *SL = NULL; 03124 03125 switch (ISHeuristic) { 03126 default: assert(0 && "Unrecognized scheduling heuristic"); 03127 case defaultScheduling: 03128 if (TLI.getSchedulingPreference() == TargetLowering::SchedulingForLatency) 03129 SL = createSimpleDAGScheduler(noScheduling, DAG, BB); 03130 else /* TargetLowering::SchedulingForRegPressure */ 03131 SL = createBURRListDAGScheduler(DAG, BB); 03132 break; 03133 case noScheduling: 03134 SL = createBFS_DAGScheduler(DAG, BB); 03135 break; 03136 case simpleScheduling: 03137 SL = createSimpleDAGScheduler(false, DAG, BB); 03138 break; 03139 case simpleNoItinScheduling: 03140 SL = createSimpleDAGScheduler(true, DAG, BB); 03141 break; 03142 case listSchedulingBURR: 03143 SL = createBURRListDAGScheduler(DAG, BB); 03144 break; 03145 case listSchedulingTD: 03146 SL = createTDListDAGScheduler(DAG, BB, CreateTargetHazardRecognizer()); 03147 break; 03148 } 03149 BB = SL->Run(); 03150 delete SL; 03151 } 03152 03153 HazardRecognizer *SelectionDAGISel::CreateTargetHazardRecognizer() { 03154 return new HazardRecognizer(); 03155 } 03156 03157 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated 03158 /// by tblgen. Others should not call it. 03159 void SelectionDAGISel:: 03160 SelectInlineAsmMemoryOperands(std::vector<SDOperand> &Ops, SelectionDAG &DAG) { 03161 std::vector<SDOperand> InOps; 03162 std::swap(InOps, Ops); 03163 03164 Ops.push_back(InOps[0]); // input chain. 03165 Ops.push_back(InOps[1]); // input asm string. 03166 03167 const char *AsmStr = cast<ExternalSymbolSDNode>(InOps[1])->getSymbol(); 03168 unsigned i = 2, e = InOps.size(); 03169 if (InOps[e-1].getValueType() == MVT::Flag) 03170 --e; // Don't process a flag operand if it is here. 03171 03172 while (i != e) { 03173 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getValue(); 03174 if ((Flags & 7) != 4 /*MEM*/) { 03175 // Just skip over this operand, copying the operands verbatim. 03176 Ops.insert(Ops.end(), InOps.begin()+i, InOps.begin()+i+(Flags >> 3) + 1); 03177 i += (Flags >> 3) + 1; 03178 } else { 03179 assert((Flags >> 3) == 1 && "Memory operand with multiple values?"); 03180 // Otherwise, this is a memory operand. Ask the target to select it. 03181 std::vector<SDOperand> SelOps; 03182 if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps, DAG)) { 03183 std::cerr << "Could not match memory address. Inline asm failure!\n"; 03184 exit(1); 03185 } 03186 03187 // Add this to the output node. 03188 Ops.push_back(DAG.getConstant(4/*MEM*/ | (SelOps.size() << 3), MVT::i32)); 03189 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end()); 03190 i += 2; 03191 } 03192 } 03193 03194 // Add the flag input back if present. 03195 if (e != InOps.size()) 03196 Ops.push_back(InOps.back()); 03197 }