LLVM API Documentation
00001 //===-- SelectionDAGBuild.cpp - Selection-DAG building --------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This implements routines for translating from LLVM IR into SelectionDAG IR. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #define DEBUG_TYPE "isel" 00015 #include "SelectionDAGBuild.h" 00016 #include "llvm/ADT/BitVector.h" 00017 #include "llvm/ADT/SmallSet.h" 00018 #include "llvm/Analysis/AliasAnalysis.h" 00019 #include "llvm/Constants.h" 00020 #include "llvm/Constants.h" 00021 #include "llvm/CallingConv.h" 00022 #include "llvm/DerivedTypes.h" 00023 #include "llvm/Function.h" 00024 #include "llvm/GlobalVariable.h" 00025 #include "llvm/InlineAsm.h" 00026 #include "llvm/Instructions.h" 00027 #include "llvm/Intrinsics.h" 00028 #include "llvm/IntrinsicInst.h" 00029 #include "llvm/Module.h" 00030 #include "llvm/CodeGen/FastISel.h" 00031 #include "llvm/CodeGen/GCStrategy.h" 00032 #include "llvm/CodeGen/GCMetadata.h" 00033 #include "llvm/CodeGen/MachineFunction.h" 00034 #include "llvm/CodeGen/MachineFrameInfo.h" 00035 #include "llvm/CodeGen/MachineInstrBuilder.h" 00036 #include "llvm/CodeGen/MachineJumpTableInfo.h" 00037 #include "llvm/CodeGen/MachineModuleInfo.h" 00038 #include "llvm/CodeGen/MachineRegisterInfo.h" 00039 #include "llvm/CodeGen/PseudoSourceValue.h" 00040 #include "llvm/CodeGen/SelectionDAG.h" 00041 #include "llvm/CodeGen/DwarfWriter.h" 00042 #include "llvm/Analysis/DebugInfo.h" 00043 #include "llvm/Target/TargetRegisterInfo.h" 00044 #include "llvm/Target/TargetData.h" 00045 #include "llvm/Target/TargetFrameInfo.h" 00046 #include "llvm/Target/TargetInstrInfo.h" 00047 #include "llvm/Target/TargetIntrinsicInfo.h" 00048 #include "llvm/Target/TargetLowering.h" 00049 #include "llvm/Target/TargetOptions.h" 00050 #include "llvm/Support/Compiler.h" 00051 #include "llvm/Support/CommandLine.h" 00052 #include "llvm/Support/Debug.h" 00053 #include "llvm/Support/ErrorHandling.h" 00054 #include "llvm/Support/MathExtras.h" 00055 #include "llvm/Support/raw_ostream.h" 00056 #include <algorithm> 00057 using namespace llvm; 00058 00059 /// LimitFloatPrecision - Generate low-precision inline sequences for 00060 /// some float libcalls (6, 8 or 12 bits). 00061 static unsigned LimitFloatPrecision; 00062 00063 static cl::opt<unsigned, true> 00064 LimitFPPrecision("limit-float-precision", 00065 cl::desc("Generate low-precision inline sequences " 00066 "for some float libcalls"), 00067 cl::location(LimitFloatPrecision), 00068 cl::init(0)); 00069 00070 /// ComputeLinearIndex - Given an LLVM IR aggregate type and a sequence 00071 /// of insertvalue or extractvalue indices that identify a member, return 00072 /// the linearized index of the start of the member. 00073 /// 00074 static unsigned ComputeLinearIndex(const TargetLowering &TLI, const Type *Ty, 00075 const unsigned *Indices, 00076 const unsigned *IndicesEnd, 00077 unsigned CurIndex = 0) { 00078 // Base case: We're done. 00079 if (Indices && Indices == IndicesEnd) 00080 return CurIndex; 00081 00082 // Given a struct type, recursively traverse the elements. 00083 if (const StructType *STy = dyn_cast<StructType>(Ty)) { 00084 for (StructType::element_iterator EB = STy->element_begin(), 00085 EI = EB, 00086 EE = STy->element_end(); 00087 EI != EE; ++EI) { 00088 if (Indices && *Indices == unsigned(EI - EB)) 00089 return ComputeLinearIndex(TLI, *EI, Indices+1, IndicesEnd, CurIndex); 00090 CurIndex = ComputeLinearIndex(TLI, *EI, 0, 0, CurIndex); 00091 } 00092 return CurIndex; 00093 } 00094 // Given an array type, recursively traverse the elements. 00095 else if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 00096 const Type *EltTy = ATy->getElementType(); 00097 for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) { 00098 if (Indices && *Indices == i) 00099 return ComputeLinearIndex(TLI, EltTy, Indices+1, IndicesEnd, CurIndex); 00100 CurIndex = ComputeLinearIndex(TLI, EltTy, 0, 0, CurIndex); 00101 } 00102 return CurIndex; 00103 } 00104 // We haven't found the type we're looking for, so keep searching. 00105 return CurIndex + 1; 00106 } 00107 00108 /// ComputeValueVTs - Given an LLVM IR type, compute a sequence of 00109 /// EVTs that represent all the individual underlying 00110 /// non-aggregate types that comprise it. 00111 /// 00112 /// If Offsets is non-null, it points to a vector to be filled in 00113 /// with the in-memory offsets of each of the individual values. 00114 /// 00115 static void ComputeValueVTs(const TargetLowering &TLI, const Type *Ty, 00116 SmallVectorImpl<EVT> &ValueVTs, 00117 SmallVectorImpl<uint64_t> *Offsets = 0, 00118 uint64_t StartingOffset = 0) { 00119 // Given a struct type, recursively traverse the elements. 00120 if (const StructType *STy = dyn_cast<StructType>(Ty)) { 00121 const StructLayout *SL = TLI.getTargetData()->getStructLayout(STy); 00122 for (StructType::element_iterator EB = STy->element_begin(), 00123 EI = EB, 00124 EE = STy->element_end(); 00125 EI != EE; ++EI) 00126 ComputeValueVTs(TLI, *EI, ValueVTs, Offsets, 00127 StartingOffset + SL->getElementOffset(EI - EB)); 00128 return; 00129 } 00130 // Given an array type, recursively traverse the elements. 00131 if (const ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 00132 const Type *EltTy = ATy->getElementType(); 00133 uint64_t EltSize = TLI.getTargetData()->getTypeAllocSize(EltTy); 00134 for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) 00135 ComputeValueVTs(TLI, EltTy, ValueVTs, Offsets, 00136 StartingOffset + i * EltSize); 00137 return; 00138 } 00139 // Interpret void as zero return values. 00140 if (Ty == Type::getVoidTy(Ty->getContext())) 00141 return; 00142 // Base case: we can get an EVT for this LLVM IR type. 00143 ValueVTs.push_back(TLI.getValueType(Ty)); 00144 if (Offsets) 00145 Offsets->push_back(StartingOffset); 00146 } 00147 00148 namespace llvm { 00149 /// RegsForValue - This struct represents the registers (physical or virtual) 00150 /// that a particular set of values is assigned, and the type information about 00151 /// the value. The most common situation is to represent one value at a time, 00152 /// but struct or array values are handled element-wise as multiple values. 00153 /// The splitting of aggregates is performed recursively, so that we never 00154 /// have aggregate-typed registers. The values at this point do not necessarily 00155 /// have legal types, so each value may require one or more registers of some 00156 /// legal type. 00157 /// 00158 struct VISIBILITY_HIDDEN RegsForValue { 00159 /// TLI - The TargetLowering object. 00160 /// 00161 const TargetLowering *TLI; 00162 00163 /// ValueVTs - The value types of the values, which may not be legal, and 00164 /// may need be promoted or synthesized from one or more registers. 00165 /// 00166 SmallVector<EVT, 4> ValueVTs; 00167 00168 /// RegVTs - The value types of the registers. This is the same size as 00169 /// ValueVTs and it records, for each value, what the type of the assigned 00170 /// register or registers are. (Individual values are never synthesized 00171 /// from more than one type of register.) 00172 /// 00173 /// With virtual registers, the contents of RegVTs is redundant with TLI's 00174 /// getRegisterType member function, however when with physical registers 00175 /// it is necessary to have a separate record of the types. 00176 /// 00177 SmallVector<EVT, 4> RegVTs; 00178 00179 /// Regs - This list holds the registers assigned to the values. 00180 /// Each legal or promoted value requires one register, and each 00181 /// expanded value requires multiple registers. 00182 /// 00183 SmallVector<unsigned, 4> Regs; 00184 00185 RegsForValue() : TLI(0) {} 00186 00187 RegsForValue(const TargetLowering &tli, 00188 const SmallVector<unsigned, 4> ®s, 00189 EVT regvt, EVT valuevt) 00190 : TLI(&tli), ValueVTs(1, valuevt), RegVTs(1, regvt), Regs(regs) {} 00191 RegsForValue(const TargetLowering &tli, 00192 const SmallVector<unsigned, 4> ®s, 00193 const SmallVector<EVT, 4> ®vts, 00194 const SmallVector<EVT, 4> &valuevts) 00195 : TLI(&tli), ValueVTs(valuevts), RegVTs(regvts), Regs(regs) {} 00196 RegsForValue(LLVMContext &Context, const TargetLowering &tli, 00197 unsigned Reg, const Type *Ty) : TLI(&tli) { 00198 ComputeValueVTs(tli, Ty, ValueVTs); 00199 00200 for (unsigned Value = 0, e = ValueVTs.size(); Value != e; ++Value) { 00201 EVT ValueVT = ValueVTs[Value]; 00202 unsigned NumRegs = TLI->getNumRegisters(Context, ValueVT); 00203 EVT RegisterVT = TLI->getRegisterType(Context, ValueVT); 00204 for (unsigned i = 0; i != NumRegs; ++i) 00205 Regs.push_back(Reg + i); 00206 RegVTs.push_back(RegisterVT); 00207 Reg += NumRegs; 00208 } 00209 } 00210 00211 /// append - Add the specified values to this one. 00212 void append(const RegsForValue &RHS) { 00213 TLI = RHS.TLI; 00214 ValueVTs.append(RHS.ValueVTs.begin(), RHS.ValueVTs.end()); 00215 RegVTs.append(RHS.RegVTs.begin(), RHS.RegVTs.end()); 00216 Regs.append(RHS.Regs.begin(), RHS.Regs.end()); 00217 } 00218 00219 00220 /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from 00221 /// this value and returns the result as a ValueVTs value. This uses 00222 /// Chain/Flag as the input and updates them for the output Chain/Flag. 00223 /// If the Flag pointer is NULL, no flag is used. 00224 SDValue getCopyFromRegs(SelectionDAG &DAG, DebugLoc dl, 00225 SDValue &Chain, SDValue *Flag) const; 00226 00227 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the 00228 /// specified value into the registers specified by this object. This uses 00229 /// Chain/Flag as the input and updates them for the output Chain/Flag. 00230 /// If the Flag pointer is NULL, no flag is used. 00231 void getCopyToRegs(SDValue Val, SelectionDAG &DAG, DebugLoc dl, 00232 SDValue &Chain, SDValue *Flag) const; 00233 00234 /// AddInlineAsmOperands - Add this value to the specified inlineasm node 00235 /// operand list. This adds the code marker, matching input operand index 00236 /// (if applicable), and includes the number of values added into it. 00237 void AddInlineAsmOperands(unsigned Code, 00238 bool HasMatching, unsigned MatchingIdx, 00239 SelectionDAG &DAG, std::vector<SDValue> &Ops) const; 00240 }; 00241 } 00242 00243 /// isUsedOutsideOfDefiningBlock - Return true if this instruction is used by 00244 /// PHI nodes or outside of the basic block that defines it, or used by a 00245 /// switch or atomic instruction, which may expand to multiple basic blocks. 00246 static bool isUsedOutsideOfDefiningBlock(Instruction *I) { 00247 if (isa<PHINode>(I)) return true; 00248 BasicBlock *BB = I->getParent(); 00249 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; ++UI) 00250 if (cast<Instruction>(*UI)->getParent() != BB || isa<PHINode>(*UI)) 00251 return true; 00252 return false; 00253 } 00254 00255 /// isOnlyUsedInEntryBlock - If the specified argument is only used in the 00256 /// entry block, return true. This includes arguments used by switches, since 00257 /// the switch may expand into multiple basic blocks. 00258 static bool isOnlyUsedInEntryBlock(Argument *A, bool EnableFastISel) { 00259 // With FastISel active, we may be splitting blocks, so force creation 00260 // of virtual registers for all non-dead arguments. 00261 // Don't force virtual registers for byval arguments though, because 00262 // fast-isel can't handle those in all cases. 00263 if (EnableFastISel && !A->hasByValAttr()) 00264 return A->use_empty(); 00265 00266 BasicBlock *Entry = A->getParent()->begin(); 00267 for (Value::use_iterator UI = A->use_begin(), E = A->use_end(); UI != E; ++UI) 00268 if (cast<Instruction>(*UI)->getParent() != Entry || isa<SwitchInst>(*UI)) 00269 return false; // Use not in entry block. 00270 return true; 00271 } 00272 00273 FunctionLoweringInfo::FunctionLoweringInfo(TargetLowering &tli) 00274 : TLI(tli) { 00275 } 00276 00277 void FunctionLoweringInfo::set(Function &fn, MachineFunction &mf, 00278 SelectionDAG &DAG, 00279 bool EnableFastISel) { 00280 Fn = &fn; 00281 MF = &mf; 00282 RegInfo = &MF->getRegInfo(); 00283 00284 // Create a vreg for each argument register that is not dead and is used 00285 // outside of the entry block for the function. 00286 for (Function::arg_iterator AI = Fn->arg_begin(), E = Fn->arg_end(); 00287 AI != E; ++AI) 00288 if (!isOnlyUsedInEntryBlock(AI, EnableFastISel)) 00289 InitializeRegForValue(AI); 00290 00291 // Initialize the mapping of values to registers. This is only set up for 00292 // instruction values that are used outside of the block that defines 00293 // them. 00294 Function::iterator BB = Fn->begin(), EB = Fn->end(); 00295 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00296 if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) 00297 if (ConstantInt *CUI = dyn_cast<ConstantInt>(AI->getArraySize())) { 00298 const Type *Ty = AI->getAllocatedType(); 00299 uint64_t TySize = TLI.getTargetData()->getTypeAllocSize(Ty); 00300 unsigned Align = 00301 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), 00302 AI->getAlignment()); 00303 00304 TySize *= CUI->getZExtValue(); // Get total allocated size. 00305 if (TySize == 0) TySize = 1; // Don't create zero-sized stack objects. 00306 StaticAllocaMap[AI] = 00307 MF->getFrameInfo()->CreateStackObject(TySize, Align); 00308 } 00309 00310 for (; BB != EB; ++BB) 00311 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) 00312 if (!I->use_empty() && isUsedOutsideOfDefiningBlock(I)) 00313 if (!isa<AllocaInst>(I) || 00314 !StaticAllocaMap.count(cast<AllocaInst>(I))) 00315 InitializeRegForValue(I); 00316 00317 // Create an initial MachineBasicBlock for each LLVM BasicBlock in F. This 00318 // also creates the initial PHI MachineInstrs, though none of the input 00319 // operands are populated. 00320 for (BB = Fn->begin(), EB = Fn->end(); BB != EB; ++BB) { 00321 MachineBasicBlock *MBB = mf.CreateMachineBasicBlock(BB); 00322 MBBMap[BB] = MBB; 00323 MF->push_back(MBB); 00324 00325 // Create Machine PHI nodes for LLVM PHI nodes, lowering them as 00326 // appropriate. 00327 PHINode *PN; 00328 DebugLoc DL; 00329 for (BasicBlock::iterator 00330 I = BB->begin(), E = BB->end(); I != E; ++I) { 00331 if (CallInst *CI = dyn_cast<CallInst>(I)) { 00332 if (Function *F = CI->getCalledFunction()) { 00333 switch (F->getIntrinsicID()) { 00334 default: break; 00335 case Intrinsic::dbg_stoppoint: { 00336 DbgStopPointInst *SPI = cast<DbgStopPointInst>(I); 00337 if (isValidDebugInfoIntrinsic(*SPI, CodeGenOpt::Default)) 00338 DL = ExtractDebugLocation(*SPI, MF->getDebugLocInfo()); 00339 break; 00340 } 00341 case Intrinsic::dbg_func_start: { 00342 DbgFuncStartInst *FSI = cast<DbgFuncStartInst>(I); 00343 if (isValidDebugInfoIntrinsic(*FSI, CodeGenOpt::Default)) 00344 DL = ExtractDebugLocation(*FSI, MF->getDebugLocInfo()); 00345 break; 00346 } 00347 } 00348 } 00349 } 00350 00351 PN = dyn_cast<PHINode>(I); 00352 if (!PN || PN->use_empty()) continue; 00353 00354 unsigned PHIReg = ValueMap[PN]; 00355 assert(PHIReg && "PHI node does not have an assigned virtual register!"); 00356 00357 SmallVector<EVT, 4> ValueVTs; 00358 ComputeValueVTs(TLI, PN->getType(), ValueVTs); 00359 for (unsigned vti = 0, vte = ValueVTs.size(); vti != vte; ++vti) { 00360 EVT VT = ValueVTs[vti]; 00361 unsigned NumRegisters = TLI.getNumRegisters(*DAG.getContext(), VT); 00362 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 00363 for (unsigned i = 0; i != NumRegisters; ++i) 00364 BuildMI(MBB, DL, TII->get(TargetInstrInfo::PHI), PHIReg + i); 00365 PHIReg += NumRegisters; 00366 } 00367 } 00368 } 00369 } 00370 00371 unsigned FunctionLoweringInfo::MakeReg(EVT VT) { 00372 return RegInfo->createVirtualRegister(TLI.getRegClassFor(VT)); 00373 } 00374 00375 /// CreateRegForValue - Allocate the appropriate number of virtual registers of 00376 /// the correctly promoted or expanded types. Assign these registers 00377 /// consecutive vreg numbers and return the first assigned number. 00378 /// 00379 /// In the case that the given value has struct or array type, this function 00380 /// will assign registers for each member or element. 00381 /// 00382 unsigned FunctionLoweringInfo::CreateRegForValue(const Value *V) { 00383 SmallVector<EVT, 4> ValueVTs; 00384 ComputeValueVTs(TLI, V->getType(), ValueVTs); 00385 00386 unsigned FirstReg = 0; 00387 for (unsigned Value = 0, e = ValueVTs.size(); Value != e; ++Value) { 00388 EVT ValueVT = ValueVTs[Value]; 00389 EVT RegisterVT = TLI.getRegisterType(V->getContext(), ValueVT); 00390 00391 unsigned NumRegs = TLI.getNumRegisters(V->getContext(), ValueVT); 00392 for (unsigned i = 0; i != NumRegs; ++i) { 00393 unsigned R = MakeReg(RegisterVT); 00394 if (!FirstReg) FirstReg = R; 00395 } 00396 } 00397 return FirstReg; 00398 } 00399 00400 /// getCopyFromParts - Create a value that contains the specified legal parts 00401 /// combined into the value they represent. If the parts combine to a type 00402 /// larger then ValueVT then AssertOp can be used to specify whether the extra 00403 /// bits are known to be zero (ISD::AssertZext) or sign extended from ValueVT 00404 /// (ISD::AssertSext). 00405 static SDValue getCopyFromParts(SelectionDAG &DAG, DebugLoc dl, 00406 const SDValue *Parts, 00407 unsigned NumParts, EVT PartVT, EVT ValueVT, 00408 ISD::NodeType AssertOp = ISD::DELETED_NODE) { 00409 assert(NumParts > 0 && "No parts to assemble!"); 00410 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 00411 SDValue Val = Parts[0]; 00412 00413 if (NumParts > 1) { 00414 // Assemble the value from multiple parts. 00415 if (!ValueVT.isVector() && ValueVT.isInteger()) { 00416 unsigned PartBits = PartVT.getSizeInBits(); 00417 unsigned ValueBits = ValueVT.getSizeInBits(); 00418 00419 // Assemble the power of 2 part. 00420 unsigned RoundParts = NumParts & (NumParts - 1) ? 00421 1 << Log2_32(NumParts) : NumParts; 00422 unsigned RoundBits = PartBits * RoundParts; 00423 EVT RoundVT = RoundBits == ValueBits ? 00424 ValueVT : EVT::getIntegerVT(*DAG.getContext(), RoundBits); 00425 SDValue Lo, Hi; 00426 00427 EVT HalfVT = EVT::getIntegerVT(*DAG.getContext(), RoundBits/2); 00428 00429 if (RoundParts > 2) { 00430 Lo = getCopyFromParts(DAG, dl, Parts, RoundParts/2, PartVT, HalfVT); 00431 Hi = getCopyFromParts(DAG, dl, Parts+RoundParts/2, RoundParts/2, 00432 PartVT, HalfVT); 00433 } else { 00434 Lo = DAG.getNode(ISD::BIT_CONVERT, dl, HalfVT, Parts[0]); 00435 Hi = DAG.getNode(ISD::BIT_CONVERT, dl, HalfVT, Parts[1]); 00436 } 00437 if (TLI.isBigEndian()) 00438 std::swap(Lo, Hi); 00439 Val = DAG.getNode(ISD::BUILD_PAIR, dl, RoundVT, Lo, Hi); 00440 00441 if (RoundParts < NumParts) { 00442 // Assemble the trailing non-power-of-2 part. 00443 unsigned OddParts = NumParts - RoundParts; 00444 EVT OddVT = EVT::getIntegerVT(*DAG.getContext(), OddParts * PartBits); 00445 Hi = getCopyFromParts(DAG, dl, 00446 Parts+RoundParts, OddParts, PartVT, OddVT); 00447 00448 // Combine the round and odd parts. 00449 Lo = Val; 00450 if (TLI.isBigEndian()) 00451 std::swap(Lo, Hi); 00452 EVT TotalVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits); 00453 Hi = DAG.getNode(ISD::ANY_EXTEND, dl, TotalVT, Hi); 00454 Hi = DAG.getNode(ISD::SHL, dl, TotalVT, Hi, 00455 DAG.getConstant(Lo.getValueType().getSizeInBits(), 00456 TLI.getPointerTy())); 00457 Lo = DAG.getNode(ISD::ZERO_EXTEND, dl, TotalVT, Lo); 00458 Val = DAG.getNode(ISD::OR, dl, TotalVT, Lo, Hi); 00459 } 00460 } else if (ValueVT.isVector()) { 00461 // Handle a multi-element vector. 00462 EVT IntermediateVT, RegisterVT; 00463 unsigned NumIntermediates; 00464 unsigned NumRegs = 00465 TLI.getVectorTypeBreakdown(*DAG.getContext(), ValueVT, IntermediateVT, 00466 NumIntermediates, RegisterVT); 00467 assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!"); 00468 NumParts = NumRegs; // Silence a compiler warning. 00469 assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!"); 00470 assert(RegisterVT == Parts[0].getValueType() && 00471 "Part type doesn't match part!"); 00472 00473 // Assemble the parts into intermediate operands. 00474 SmallVector<SDValue, 8> Ops(NumIntermediates); 00475 if (NumIntermediates == NumParts) { 00476 // If the register was not expanded, truncate or copy the value, 00477 // as appropriate. 00478 for (unsigned i = 0; i != NumParts; ++i) 00479 Ops[i] = getCopyFromParts(DAG, dl, &Parts[i], 1, 00480 PartVT, IntermediateVT); 00481 } else if (NumParts > 0) { 00482 // If the intermediate type was expanded, build the intermediate operands 00483 // from the parts. 00484 assert(NumParts % NumIntermediates == 0 && 00485 "Must expand into a divisible number of parts!"); 00486 unsigned Factor = NumParts / NumIntermediates; 00487 for (unsigned i = 0; i != NumIntermediates; ++i) 00488 Ops[i] = getCopyFromParts(DAG, dl, &Parts[i * Factor], Factor, 00489 PartVT, IntermediateVT); 00490 } 00491 00492 // Build a vector with BUILD_VECTOR or CONCAT_VECTORS from the intermediate 00493 // operands. 00494 Val = DAG.getNode(IntermediateVT.isVector() ? 00495 ISD::CONCAT_VECTORS : ISD::BUILD_VECTOR, dl, 00496 ValueVT, &Ops[0], NumIntermediates); 00497 } else if (PartVT.isFloatingPoint()) { 00498 // FP split into multiple FP parts (for ppcf128) 00499 assert(ValueVT == EVT(MVT::ppcf128) && PartVT == EVT(MVT::f64) && 00500 "Unexpected split"); 00501 SDValue Lo, Hi; 00502 Lo = DAG.getNode(ISD::BIT_CONVERT, dl, EVT(MVT::f64), Parts[0]); 00503 Hi = DAG.getNode(ISD::BIT_CONVERT, dl, EVT(MVT::f64), Parts[1]); 00504 if (TLI.isBigEndian()) 00505 std::swap(Lo, Hi); 00506 Val = DAG.getNode(ISD::BUILD_PAIR, dl, ValueVT, Lo, Hi); 00507 } else { 00508 // FP split into integer parts (soft fp) 00509 assert(ValueVT.isFloatingPoint() && PartVT.isInteger() && 00510 !PartVT.isVector() && "Unexpected split"); 00511 EVT IntVT = EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits()); 00512 Val = getCopyFromParts(DAG, dl, Parts, NumParts, PartVT, IntVT); 00513 } 00514 } 00515 00516 // There is now one part, held in Val. Correct it to match ValueVT. 00517 PartVT = Val.getValueType(); 00518 00519 if (PartVT == ValueVT) 00520 return Val; 00521 00522 if (PartVT.isVector()) { 00523 assert(ValueVT.isVector() && "Unknown vector conversion!"); 00524 return DAG.getNode(ISD::BIT_CONVERT, dl, ValueVT, Val); 00525 } 00526 00527 if (ValueVT.isVector()) { 00528 assert(ValueVT.getVectorElementType() == PartVT && 00529 ValueVT.getVectorNumElements() == 1 && 00530 "Only trivial scalar-to-vector conversions should get here!"); 00531 return DAG.getNode(ISD::BUILD_VECTOR, dl, ValueVT, Val); 00532 } 00533 00534 if (PartVT.isInteger() && 00535 ValueVT.isInteger()) { 00536 if (ValueVT.bitsLT(PartVT)) { 00537 // For a truncate, see if we have any information to 00538 // indicate whether the truncated bits will always be 00539 // zero or sign-extension. 00540 if (AssertOp != ISD::DELETED_NODE) 00541 Val = DAG.getNode(AssertOp, dl, PartVT, Val, 00542 DAG.getValueType(ValueVT)); 00543 return DAG.getNode(ISD::TRUNCATE, dl, ValueVT, Val); 00544 } else { 00545 return DAG.getNode(ISD::ANY_EXTEND, dl, ValueVT, Val); 00546 } 00547 } 00548 00549 if (PartVT.isFloatingPoint() && ValueVT.isFloatingPoint()) { 00550 if (ValueVT.bitsLT(Val.getValueType())) 00551 // FP_ROUND's are always exact here. 00552 return DAG.getNode(ISD::FP_ROUND, dl, ValueVT, Val, 00553 DAG.getIntPtrConstant(1)); 00554 return DAG.getNode(ISD::FP_EXTEND, dl, ValueVT, Val); 00555 } 00556 00557 if (PartVT.getSizeInBits() == ValueVT.getSizeInBits()) 00558 return DAG.getNode(ISD::BIT_CONVERT, dl, ValueVT, Val); 00559 00560 llvm_unreachable("Unknown mismatch!"); 00561 return SDValue(); 00562 } 00563 00564 /// getCopyToParts - Create a series of nodes that contain the specified value 00565 /// split into legal parts. If the parts contain more bits than Val, then, for 00566 /// integers, ExtendKind can be used to specify how to generate the extra bits. 00567 static void getCopyToParts(SelectionDAG &DAG, DebugLoc dl, SDValue Val, 00568 SDValue *Parts, unsigned NumParts, EVT PartVT, 00569 ISD::NodeType ExtendKind = ISD::ANY_EXTEND) { 00570 const TargetLowering &TLI = DAG.getTargetLoweringInfo(); 00571 EVT PtrVT = TLI.getPointerTy(); 00572 EVT ValueVT = Val.getValueType(); 00573 unsigned PartBits = PartVT.getSizeInBits(); 00574 unsigned OrigNumParts = NumParts; 00575 assert(TLI.isTypeLegal(PartVT) && "Copying to an illegal type!"); 00576 00577 if (!NumParts) 00578 return; 00579 00580 if (!ValueVT.isVector()) { 00581 if (PartVT == ValueVT) { 00582 assert(NumParts == 1 && "No-op copy with multiple parts!"); 00583 Parts[0] = Val; 00584 return; 00585 } 00586 00587 if (NumParts * PartBits > ValueVT.getSizeInBits()) { 00588 // If the parts cover more bits than the value has, promote the value. 00589 if (PartVT.isFloatingPoint() && ValueVT.isFloatingPoint()) { 00590 assert(NumParts == 1 && "Do not know what to promote to!"); 00591 Val = DAG.getNode(ISD::FP_EXTEND, dl, PartVT, Val); 00592 } else if (PartVT.isInteger() && ValueVT.isInteger()) { 00593 ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits); 00594 Val = DAG.getNode(ExtendKind, dl, ValueVT, Val); 00595 } else { 00596 llvm_unreachable("Unknown mismatch!"); 00597 } 00598 } else if (PartBits == ValueVT.getSizeInBits()) { 00599 // Different types of the same size. 00600 assert(NumParts == 1 && PartVT != ValueVT); 00601 Val = DAG.getNode(ISD::BIT_CONVERT, dl, PartVT, Val); 00602 } else if (NumParts * PartBits < ValueVT.getSizeInBits()) { 00603 // If the parts cover less bits than value has, truncate the value. 00604 if (PartVT.isInteger() && ValueVT.isInteger()) { 00605 ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits); 00606 Val = DAG.getNode(ISD::TRUNCATE, dl, ValueVT, Val); 00607 } else { 00608 llvm_unreachable("Unknown mismatch!"); 00609 } 00610 } 00611 00612 // The value may have changed - recompute ValueVT. 00613 ValueVT = Val.getValueType(); 00614 assert(NumParts * PartBits == ValueVT.getSizeInBits() && 00615 "Failed to tile the value with PartVT!"); 00616 00617 if (NumParts == 1) { 00618 assert(PartVT == ValueVT && "Type conversion failed!"); 00619 Parts[0] = Val; 00620 return; 00621 } 00622 00623 // Expand the value into multiple parts. 00624 if (NumParts & (NumParts - 1)) { 00625 // The number of parts is not a power of 2. Split off and copy the tail. 00626 assert(PartVT.isInteger() && ValueVT.isInteger() && 00627 "Do not know what to expand to!"); 00628 unsigned RoundParts = 1 << Log2_32(NumParts); 00629 unsigned RoundBits = RoundParts * PartBits; 00630 unsigned OddParts = NumParts - RoundParts; 00631 SDValue OddVal = DAG.getNode(ISD::SRL, dl, ValueVT, Val, 00632 DAG.getConstant(RoundBits, 00633 TLI.getPointerTy())); 00634 getCopyToParts(DAG, dl, OddVal, Parts + RoundParts, OddParts, PartVT); 00635 if (TLI.isBigEndian()) 00636 // The odd parts were reversed by getCopyToParts - unreverse them. 00637 std::reverse(Parts + RoundParts, Parts + NumParts); 00638 NumParts = RoundParts; 00639 ValueVT = EVT::getIntegerVT(*DAG.getContext(), NumParts * PartBits); 00640 Val = DAG.getNode(ISD::TRUNCATE, dl, ValueVT, Val); 00641 } 00642 00643 // The number of parts is a power of 2. Repeatedly bisect the value using 00644 // EXTRACT_ELEMENT. 00645 Parts[0] = DAG.getNode(ISD::BIT_CONVERT, dl, 00646 EVT::getIntegerVT(*DAG.getContext(), ValueVT.getSizeInBits()), 00647 Val); 00648 for (unsigned StepSize = NumParts; StepSize > 1; StepSize /= 2) { 00649 for (unsigned i = 0; i < NumParts; i += StepSize) { 00650 unsigned ThisBits = StepSize * PartBits / 2; 00651 EVT ThisVT = EVT::getIntegerVT(*DAG.getContext(), ThisBits); 00652 SDValue &Part0 = Parts[i]; 00653 SDValue &Part1 = Parts[i+StepSize/2]; 00654 00655 Part1 = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, 00656 ThisVT, Part0, 00657 DAG.getConstant(1, PtrVT)); 00658 Part0 = DAG.getNode(ISD::EXTRACT_ELEMENT, dl, 00659 ThisVT, Part0, 00660 DAG.getConstant(0, PtrVT)); 00661 00662 if (ThisBits == PartBits && ThisVT != PartVT) { 00663 Part0 = DAG.getNode(ISD::BIT_CONVERT, dl, 00664 PartVT, Part0); 00665 Part1 = DAG.getNode(ISD::BIT_CONVERT, dl, 00666 PartVT, Part1); 00667 } 00668 } 00669 } 00670 00671 if (TLI.isBigEndian()) 00672 std::reverse(Parts, Parts + OrigNumParts); 00673 00674 return; 00675 } 00676 00677 // Vector ValueVT. 00678 if (NumParts == 1) { 00679 if (PartVT != ValueVT) { 00680 if (PartVT.isVector()) { 00681 Val = DAG.getNode(ISD::BIT_CONVERT, dl, PartVT, Val); 00682 } else { 00683 assert(ValueVT.getVectorElementType() == PartVT && 00684 ValueVT.getVectorNumElements() == 1 && 00685 "Only trivial vector-to-scalar conversions should get here!"); 00686 Val = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, 00687 PartVT, Val, 00688 DAG.getConstant(0, PtrVT)); 00689 } 00690 } 00691 00692 Parts[0] = Val; 00693 return; 00694 } 00695 00696 // Handle a multi-element vector. 00697 EVT IntermediateVT, RegisterVT; 00698 unsigned NumIntermediates; 00699 unsigned NumRegs = TLI.getVectorTypeBreakdown(*DAG.getContext(), ValueVT, 00700 IntermediateVT, NumIntermediates, RegisterVT); 00701 unsigned NumElements = ValueVT.getVectorNumElements(); 00702 00703 assert(NumRegs == NumParts && "Part count doesn't match vector breakdown!"); 00704 NumParts = NumRegs; // Silence a compiler warning. 00705 assert(RegisterVT == PartVT && "Part type doesn't match vector breakdown!"); 00706 00707 // Split the vector into intermediate operands. 00708 SmallVector<SDValue, 8> Ops(NumIntermediates); 00709 for (unsigned i = 0; i != NumIntermediates; ++i) 00710 if (IntermediateVT.isVector()) 00711 Ops[i] = DAG.getNode(ISD::EXTRACT_SUBVECTOR, dl, 00712 IntermediateVT, Val, 00713 DAG.getConstant(i * (NumElements / NumIntermediates), 00714 PtrVT)); 00715 else 00716 Ops[i] = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, 00717 IntermediateVT, Val, 00718 DAG.getConstant(i, PtrVT)); 00719 00720 // Split the intermediate operands into legal parts. 00721 if (NumParts == NumIntermediates) { 00722 // If the register was not expanded, promote or copy the value, 00723 // as appropriate. 00724 for (unsigned i = 0; i != NumParts; ++i) 00725 getCopyToParts(DAG, dl, Ops[i], &Parts[i], 1, PartVT); 00726 } else if (NumParts > 0) { 00727 // If the intermediate type was expanded, split each the value into 00728 // legal parts. 00729 assert(NumParts % NumIntermediates == 0 && 00730 "Must expand into a divisible number of parts!"); 00731 unsigned Factor = NumParts / NumIntermediates; 00732 for (unsigned i = 0; i != NumIntermediates; ++i) 00733 getCopyToParts(DAG, dl, Ops[i], &Parts[i * Factor], Factor, PartVT); 00734 } 00735 } 00736 00737 00738 void SelectionDAGLowering::init(GCFunctionInfo *gfi, AliasAnalysis &aa) { 00739 AA = &aa; 00740 GFI = gfi; 00741 TD = DAG.getTarget().getTargetData(); 00742 } 00743 00744 /// clear - Clear out the curret SelectionDAG and the associated 00745 /// state and prepare this SelectionDAGLowering object to be used 00746 /// for a new block. This doesn't clear out information about 00747 /// additional blocks that are needed to complete switch lowering 00748 /// or PHI node updating; that information is cleared out as it is 00749 /// consumed. 00750 void SelectionDAGLowering::clear() { 00751 NodeMap.clear(); 00752 PendingLoads.clear(); 00753 PendingExports.clear(); 00754 DAG.clear(); 00755 CurDebugLoc = DebugLoc::getUnknownLoc(); 00756 HasTailCall = false; 00757 } 00758 00759 /// getRoot - Return the current virtual root of the Selection DAG, 00760 /// flushing any PendingLoad items. This must be done before emitting 00761 /// a store or any other node that may need to be ordered after any 00762 /// prior load instructions. 00763 /// 00764 SDValue SelectionDAGLowering::getRoot() { 00765 if (PendingLoads.empty()) 00766 return DAG.getRoot(); 00767 00768 if (PendingLoads.size() == 1) { 00769 SDValue Root = PendingLoads[0]; 00770 DAG.setRoot(Root); 00771 PendingLoads.clear(); 00772 return Root; 00773 } 00774 00775 // Otherwise, we have to make a token factor node. 00776 SDValue Root = DAG.getNode(ISD::TokenFactor, getCurDebugLoc(), MVT::Other, 00777 &PendingLoads[0], PendingLoads.size()); 00778 PendingLoads.clear(); 00779 DAG.setRoot(Root); 00780 return Root; 00781 } 00782 00783 /// getControlRoot - Similar to getRoot, but instead of flushing all the 00784 /// PendingLoad items, flush all the PendingExports items. It is necessary 00785 /// to do this before emitting a terminator instruction. 00786 /// 00787 SDValue SelectionDAGLowering::getControlRoot() { 00788 SDValue Root = DAG.getRoot(); 00789 00790 if (PendingExports.empty()) 00791 return Root; 00792 00793 // Turn all of the CopyToReg chains into one factored node. 00794 if (Root.getOpcode() != ISD::EntryToken) { 00795 unsigned i = 0, e = PendingExports.size(); 00796 for (; i != e; ++i) { 00797 assert(PendingExports[i].getNode()->getNumOperands() > 1); 00798 if (PendingExports[i].getNode()->getOperand(0) == Root) 00799 break; // Don't add the root if we already indirectly depend on it. 00800 } 00801 00802 if (i == e) 00803 PendingExports.push_back(Root); 00804 } 00805 00806 Root = DAG.getNode(ISD::TokenFactor, getCurDebugLoc(), MVT::Other, 00807 &PendingExports[0], 00808 PendingExports.size()); 00809 PendingExports.clear(); 00810 DAG.setRoot(Root); 00811 return Root; 00812 } 00813 00814 void SelectionDAGLowering::visit(Instruction &I) { 00815 visit(I.getOpcode(), I); 00816 } 00817 00818 void SelectionDAGLowering::visit(unsigned Opcode, User &I) { 00819 // Note: this doesn't use InstVisitor, because it has to work with 00820 // ConstantExpr's in addition to instructions. 00821 switch (Opcode) { 00822 default: llvm_unreachable("Unknown instruction type encountered!"); 00823 // Build the switch statement using the Instruction.def file. 00824 #define HANDLE_INST(NUM, OPCODE, CLASS) \ 00825 case Instruction::OPCODE:return visit##OPCODE((CLASS&)I); 00826 #include "llvm/Instruction.def" 00827 } 00828 } 00829 00830 SDValue SelectionDAGLowering::getValue(const Value *V) { 00831 SDValue &N = NodeMap[V]; 00832 if (N.getNode()) return N; 00833 00834 if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(V))) { 00835 EVT VT = TLI.getValueType(V->getType(), true); 00836 00837 if (ConstantInt *CI = dyn_cast<ConstantInt>(C)) 00838 return N = DAG.getConstant(*CI, VT); 00839 00840 if (GlobalValue *GV = dyn_cast<GlobalValue>(C)) 00841 return N = DAG.getGlobalAddress(GV, VT); 00842 00843 if (isa<ConstantPointerNull>(C)) 00844 return N = DAG.getConstant(0, TLI.getPointerTy()); 00845 00846 if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) 00847 return N = DAG.getConstantFP(*CFP, VT); 00848 00849 if (isa<UndefValue>(C) && !V->getType()->isAggregateType()) 00850 return N = DAG.getUNDEF(VT); 00851 00852 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { 00853 visit(CE->getOpcode(), *CE); 00854 SDValue N1 = NodeMap[V]; 00855 assert(N1.getNode() && "visit didn't populate the ValueMap!"); 00856 return N1; 00857 } 00858 00859 if (isa<ConstantStruct>(C) || isa<ConstantArray>(C)) { 00860 SmallVector<SDValue, 4> Constants; 00861 for (User::const_op_iterator OI = C->op_begin(), OE = C->op_end(); 00862 OI != OE; ++OI) { 00863 SDNode *Val = getValue(*OI).getNode(); 00864 for (unsigned i = 0, e = Val->getNumValues(); i != e; ++i) 00865 Constants.push_back(SDValue(Val, i)); 00866 } 00867 return DAG.getMergeValues(&Constants[0], Constants.size(), 00868 getCurDebugLoc()); 00869 } 00870 00871 if (isa<StructType>(C->getType()) || isa<ArrayType>(C->getType())) { 00872 assert((isa<ConstantAggregateZero>(C) || isa<UndefValue>(C)) && 00873 "Unknown struct or array constant!"); 00874 00875 SmallVector<EVT, 4> ValueVTs; 00876 ComputeValueVTs(TLI, C->getType(), ValueVTs); 00877 unsigned NumElts = ValueVTs.size(); 00878 if (NumElts == 0) 00879 return SDValue(); // empty struct 00880 SmallVector<SDValue, 4> Constants(NumElts); 00881 for (unsigned i = 0; i != NumElts; ++i) { 00882 EVT EltVT = ValueVTs[i]; 00883 if (isa<UndefValue>(C)) 00884 Constants[i] = DAG.getUNDEF(EltVT); 00885 else if (EltVT.isFloatingPoint()) 00886 Constants[i] = DAG.getConstantFP(0, EltVT); 00887 else 00888 Constants[i] = DAG.getConstant(0, EltVT); 00889 } 00890 return DAG.getMergeValues(&Constants[0], NumElts, getCurDebugLoc()); 00891 } 00892 00893 const VectorType *VecTy = cast<VectorType>(V->getType()); 00894 unsigned NumElements = VecTy->getNumElements(); 00895 00896 // Now that we know the number and type of the elements, get that number of 00897 // elements into the Ops array based on what kind of constant it is. 00898 SmallVector<SDValue, 16> Ops; 00899 if (ConstantVector *CP = dyn_cast<ConstantVector>(C)) { 00900 for (unsigned i = 0; i != NumElements; ++i) 00901 Ops.push_back(getValue(CP->getOperand(i))); 00902 } else { 00903 assert(isa<ConstantAggregateZero>(C) && "Unknown vector constant!"); 00904 EVT EltVT = TLI.getValueType(VecTy->getElementType()); 00905 00906 SDValue Op; 00907 if (EltVT.isFloatingPoint()) 00908 Op = DAG.getConstantFP(0, EltVT); 00909 else 00910 Op = DAG.getConstant(0, EltVT); 00911 Ops.assign(NumElements, Op); 00912 } 00913 00914 // Create a BUILD_VECTOR node. 00915 return NodeMap[V] = DAG.getNode(ISD::BUILD_VECTOR, getCurDebugLoc(), 00916 VT, &Ops[0], Ops.size()); 00917 } 00918 00919 // If this is a static alloca, generate it as the frameindex instead of 00920 // computation. 00921 if (const AllocaInst *AI = dyn_cast<AllocaInst>(V)) { 00922 DenseMap<const AllocaInst*, int>::iterator SI = 00923 FuncInfo.StaticAllocaMap.find(AI); 00924 if (SI != FuncInfo.StaticAllocaMap.end()) 00925 return DAG.getFrameIndex(SI->second, TLI.getPointerTy()); 00926 } 00927 00928 unsigned InReg = FuncInfo.ValueMap[V]; 00929 assert(InReg && "Value not in map!"); 00930 00931 RegsForValue RFV(*DAG.getContext(), TLI, InReg, V->getType()); 00932 SDValue Chain = DAG.getEntryNode(); 00933 return RFV.getCopyFromRegs(DAG, getCurDebugLoc(), Chain, NULL); 00934 } 00935 00936 00937 void SelectionDAGLowering::visitRet(ReturnInst &I) { 00938 SDValue Chain = getControlRoot(); 00939 SmallVector<ISD::OutputArg, 8> Outs; 00940 for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i) { 00941 SmallVector<EVT, 4> ValueVTs; 00942 ComputeValueVTs(TLI, I.getOperand(i)->getType(), ValueVTs); 00943 unsigned NumValues = ValueVTs.size(); 00944 if (NumValues == 0) continue; 00945 00946 SDValue RetOp = getValue(I.getOperand(i)); 00947 for (unsigned j = 0, f = NumValues; j != f; ++j) { 00948 EVT VT = ValueVTs[j]; 00949 00950 ISD::NodeType ExtendKind = ISD::ANY_EXTEND; 00951 00952 const Function *F = I.getParent()->getParent(); 00953 if (F->paramHasAttr(0, Attribute::SExt)) 00954 ExtendKind = ISD::SIGN_EXTEND; 00955 else if (F->paramHasAttr(0, Attribute::ZExt)) 00956 ExtendKind = ISD::ZERO_EXTEND; 00957 00958 // FIXME: C calling convention requires the return type to be promoted to 00959 // at least 32-bit. But this is not necessary for non-C calling 00960 // conventions. The frontend should mark functions whose return values 00961 // require promoting with signext or zeroext attributes. 00962 if (ExtendKind != ISD::ANY_EXTEND && VT.isInteger()) { 00963 EVT MinVT = TLI.getRegisterType(*DAG.getContext(), MVT::i32); 00964 if (VT.bitsLT(MinVT)) 00965 VT = MinVT; 00966 } 00967 00968 unsigned NumParts = TLI.getNumRegisters(*DAG.getContext(), VT); 00969 EVT PartVT = TLI.getRegisterType(*DAG.getContext(), VT); 00970 SmallVector<SDValue, 4> Parts(NumParts); 00971 getCopyToParts(DAG, getCurDebugLoc(), 00972 SDValue(RetOp.getNode(), RetOp.getResNo() + j), 00973 &Parts[0], NumParts, PartVT, ExtendKind); 00974 00975 // 'inreg' on function refers to return value 00976 ISD::ArgFlagsTy Flags = ISD::ArgFlagsTy(); 00977 if (F->paramHasAttr(0, Attribute::InReg)) 00978 Flags.setInReg(); 00979 00980 // Propagate extension type if any 00981 if (F->paramHasAttr(0, Attribute::SExt)) 00982 Flags.setSExt(); 00983 else if (F->paramHasAttr(0, Attribute::ZExt)) 00984 Flags.setZExt(); 00985 00986 for (unsigned i = 0; i < NumParts; ++i) 00987 Outs.push_back(ISD::OutputArg(Flags, Parts[i], /*isfixed=*/true)); 00988 } 00989 } 00990 00991 bool isVarArg = DAG.getMachineFunction().getFunction()->isVarArg(); 00992 unsigned CallConv = DAG.getMachineFunction().getFunction()->getCallingConv(); 00993 Chain = TLI.LowerReturn(Chain, CallConv, isVarArg, 00994 Outs, getCurDebugLoc(), DAG); 00995 00996 // Verify that the target's LowerReturn behaved as expected. 00997 assert(Chain.getNode() && Chain.getValueType() == MVT::Other && 00998 "LowerReturn didn't return a valid chain!"); 00999 01000 // Update the DAG with the new chain value resulting from return lowering. 01001 DAG.setRoot(Chain); 01002 } 01003 01004 /// CopyToExportRegsIfNeeded - If the given value has virtual registers 01005 /// created for it, emit nodes to copy the value into the virtual 01006 /// registers. 01007 void SelectionDAGLowering::CopyToExportRegsIfNeeded(Value *V) { 01008 if (!V->use_empty()) { 01009 DenseMap<const Value *, unsigned>::iterator VMI = FuncInfo.ValueMap.find(V); 01010 if (VMI != FuncInfo.ValueMap.end()) 01011 CopyValueToVirtualRegister(V, VMI->second); 01012 } 01013 } 01014 01015 /// ExportFromCurrentBlock - If this condition isn't known to be exported from 01016 /// the current basic block, add it to ValueMap now so that we'll get a 01017 /// CopyTo/FromReg. 01018 void SelectionDAGLowering::ExportFromCurrentBlock(Value *V) { 01019 // No need to export constants. 01020 if (!isa<Instruction>(V) && !isa<Argument>(V)) return; 01021 01022 // Already exported? 01023 if (FuncInfo.isExportedInst(V)) return; 01024 01025 unsigned Reg = FuncInfo.InitializeRegForValue(V); 01026 CopyValueToVirtualRegister(V, Reg); 01027 } 01028 01029 bool SelectionDAGLowering::isExportableFromCurrentBlock(Value *V, 01030 const BasicBlock *FromBB) { 01031 // The operands of the setcc have to be in this block. We don't know 01032 // how to export them from some other block. 01033 if (Instruction *VI = dyn_cast<Instruction>(V)) { 01034 // Can export from current BB. 01035 if (VI->getParent() == FromBB) 01036 return true; 01037 01038 // Is already exported, noop. 01039 return FuncInfo.isExportedInst(V); 01040 } 01041 01042 // If this is an argument, we can export it if the BB is the entry block or 01043 // if it is already exported. 01044 if (isa<Argument>(V)) { 01045 if (FromBB == &FromBB->getParent()->getEntryBlock()) 01046 return true; 01047 01048 // Otherwise, can only export this if it is already exported. 01049 return FuncInfo.isExportedInst(V); 01050 } 01051 01052 // Otherwise, constants can always be exported. 01053 return true; 01054 } 01055 01056 static bool InBlock(const Value *V, const BasicBlock *BB) { 01057 if (const Instruction *I = dyn_cast<Instruction>(V)) 01058 return I->getParent() == BB; 01059 return true; 01060 } 01061 01062 /// getFCmpCondCode - Return the ISD condition code corresponding to 01063 /// the given LLVM IR floating-point condition code. This includes 01064 /// consideration of global floating-point math flags. 01065 /// 01066 static ISD::CondCode getFCmpCondCode(FCmpInst::Predicate Pred) { 01067 ISD::CondCode FPC, FOC; 01068 switch (Pred) { 01069 case FCmpInst::FCMP_FALSE: FOC = FPC = ISD::SETFALSE; break; 01070 case FCmpInst::FCMP_OEQ: FOC = ISD::SETEQ; FPC = ISD::SETOEQ; break; 01071 case FCmpInst::FCMP_OGT: FOC = ISD::SETGT; FPC = ISD::SETOGT; break; 01072 case FCmpInst::FCMP_OGE: FOC = ISD::SETGE; FPC = ISD::SETOGE; break; 01073 case FCmpInst::FCMP_OLT: FOC = ISD::SETLT; FPC = ISD::SETOLT; break; 01074 case FCmpInst::FCMP_OLE: FOC = ISD::SETLE; FPC = ISD::SETOLE; break; 01075 case FCmpInst::FCMP_ONE: FOC = ISD::SETNE; FPC = ISD::SETONE; break; 01076 case FCmpInst::FCMP_ORD: FOC = FPC = ISD::SETO; break; 01077 case FCmpInst::FCMP_UNO: FOC = FPC = ISD::SETUO; break; 01078 case FCmpInst::FCMP_UEQ: FOC = ISD::SETEQ; FPC = ISD::SETUEQ; break; 01079 case FCmpInst::FCMP_UGT: FOC = ISD::SETGT; FPC = ISD::SETUGT; break; 01080 case FCmpInst::FCMP_UGE: FOC = ISD::SETGE; FPC = ISD::SETUGE; break; 01081 case FCmpInst::FCMP_ULT: FOC = ISD::SETLT; FPC = ISD::SETULT; break; 01082 case FCmpInst::FCMP_ULE: FOC = ISD::SETLE; FPC = ISD::SETULE; break; 01083 case FCmpInst::FCMP_UNE: FOC = ISD::SETNE; FPC = ISD::SETUNE; break; 01084 case FCmpInst::FCMP_TRUE: FOC = FPC = ISD::SETTRUE; break; 01085 default: 01086 llvm_unreachable("Invalid FCmp predicate opcode!"); 01087 FOC = FPC = ISD::SETFALSE; 01088 break; 01089 } 01090 if (FiniteOnlyFPMath()) 01091 return FOC; 01092 else 01093 return FPC; 01094 } 01095 01096 /// getICmpCondCode - Return the ISD condition code corresponding to 01097 /// the given LLVM IR integer condition code. 01098 /// 01099 static ISD::CondCode getICmpCondCode(ICmpInst::Predicate Pred) { 01100 switch (Pred) { 01101 case ICmpInst::ICMP_EQ: return ISD::SETEQ; 01102 case ICmpInst::ICMP_NE: return ISD::SETNE; 01103 case ICmpInst::ICMP_SLE: return ISD::SETLE; 01104 case ICmpInst::ICMP_ULE: return ISD::SETULE; 01105 case ICmpInst::ICMP_SGE: return ISD::SETGE; 01106 case ICmpInst::ICMP_UGE: return ISD::SETUGE; 01107 case ICmpInst::ICMP_SLT: return ISD::SETLT; 01108 case ICmpInst::ICMP_ULT: return ISD::SETULT; 01109 case ICmpInst::ICMP_SGT: return ISD::SETGT; 01110 case ICmpInst::ICMP_UGT: return ISD::SETUGT; 01111 default: 01112 llvm_unreachable("Invalid ICmp predicate opcode!"); 01113 return ISD::SETNE; 01114 } 01115 } 01116 01117 /// EmitBranchForMergedCondition - Helper method for FindMergedConditions. 01118 /// This function emits a branch and is used at the leaves of an OR or an 01119 /// AND operator tree. 01120 /// 01121 void 01122 SelectionDAGLowering::EmitBranchForMergedCondition(Value *Cond, 01123 MachineBasicBlock *TBB, 01124 MachineBasicBlock *FBB, 01125 MachineBasicBlock *CurBB) { 01126 const BasicBlock *BB = CurBB->getBasicBlock(); 01127 01128 // If the leaf of the tree is a comparison, merge the condition into 01129 // the caseblock. 01130 if (CmpInst *BOp = dyn_cast<CmpInst>(Cond)) { 01131 // The operands of the cmp have to be in this block. We don't know 01132 // how to export them from some other block. If this is the first block 01133 // of the sequence, no exporting is needed. 01134 if (CurBB == CurMBB || 01135 (isExportableFromCurrentBlock(BOp->getOperand(0), BB) && 01136 isExportableFromCurrentBlock(BOp->getOperand(1), BB))) { 01137 ISD::CondCode Condition; 01138 if (ICmpInst *IC = dyn_cast<ICmpInst>(Cond)) { 01139 Condition = getICmpCondCode(IC->getPredicate()); 01140 } else if (FCmpInst *FC = dyn_cast<FCmpInst>(Cond)) { 01141 Condition = getFCmpCondCode(FC->getPredicate()); 01142 } else { 01143 Condition = ISD::SETEQ; // silence warning. 01144 llvm_unreachable("Unknown compare instruction"); 01145 } 01146 01147 CaseBlock CB(Condition, BOp->getOperand(0), 01148 BOp->getOperand(1), NULL, TBB, FBB, CurBB); 01149 SwitchCases.push_back(CB); 01150 return; 01151 } 01152 } 01153 01154 // Create a CaseBlock record representing this branch. 01155 CaseBlock CB(ISD::SETEQ, Cond, ConstantInt::getTrue(*DAG.getContext()), 01156 NULL, TBB, FBB, CurBB); 01157 SwitchCases.push_back(CB); 01158 } 01159 01160 /// FindMergedConditions - If Cond is an expression like 01161 void SelectionDAGLowering::FindMergedConditions(Value *Cond, 01162 MachineBasicBlock *TBB, 01163 MachineBasicBlock *FBB, 01164 MachineBasicBlock *CurBB, 01165 unsigned Opc) { 01166 // If this node is not part of the or/and tree, emit it as a branch. 01167 Instruction *BOp = dyn_cast<Instruction>(Cond); 01168 if (!BOp || !(isa<BinaryOperator>(BOp) || isa<CmpInst>(BOp)) || 01169 (unsigned)BOp->getOpcode() != Opc || !BOp->hasOneUse() || 01170 BOp->getParent() != CurBB->getBasicBlock() || 01171 !InBlock(BOp->getOperand(0), CurBB->getBasicBlock()) || 01172 !InBlock(BOp->getOperand(1), CurBB->getBasicBlock())) { 01173 EmitBranchForMergedCondition(Cond, TBB, FBB, CurBB); 01174 return; 01175 } 01176 01177 // Create TmpBB after CurBB. 01178 MachineFunction::iterator BBI = CurBB; 01179 MachineFunction &MF = DAG.getMachineFunction(); 01180 MachineBasicBlock *TmpBB = MF.CreateMachineBasicBlock(CurBB->getBasicBlock()); 01181 CurBB->getParent()->insert(++BBI, TmpBB); 01182 01183 if (Opc == Instruction::Or) { 01184 // Codegen X | Y as: 01185 // jmp_if_X TBB 01186 // jmp TmpBB 01187 // TmpBB: 01188 // jmp_if_Y TBB 01189 // jmp FBB 01190 // 01191 01192 // Emit the LHS condition. 01193 FindMergedConditions(BOp->getOperand(0), TBB, TmpBB, CurBB, Opc); 01194 01195 // Emit the RHS condition into TmpBB. 01196 FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc); 01197 } else { 01198 assert(Opc == Instruction::And && "Unknown merge op!"); 01199 // Codegen X & Y as: 01200 // jmp_if_X TmpBB 01201 // jmp FBB 01202 // TmpBB: 01203 // jmp_if_Y TBB 01204 // jmp FBB 01205 // 01206 // This requires creation of TmpBB after CurBB. 01207 01208 // Emit the LHS condition. 01209 FindMergedConditions(BOp->getOperand(0), TmpBB, FBB, CurBB, Opc); 01210 01211 // Emit the RHS condition into TmpBB. 01212 FindMergedConditions(BOp->getOperand(1), TBB, FBB, TmpBB, Opc); 01213 } 01214 } 01215 01216 /// If the set of cases should be emitted as a series of branches, return true. 01217 /// If we should emit this as a bunch of and/or'd together conditions, return 01218 /// false. 01219 bool 01220 SelectionDAGLowering::ShouldEmitAsBranches(const std::vector<CaseBlock> &Cases){ 01221 if (Cases.size() != 2) return true; 01222 01223 // If this is two comparisons of the same values or'd or and'd together, they 01224 // will get folded into a single comparison, so don't emit two blocks. 01225 if ((Cases[0].CmpLHS == Cases[1].CmpLHS && 01226 Cases[0].CmpRHS == Cases[1].CmpRHS) || 01227 (Cases[0].CmpRHS == Cases[1].CmpLHS && 01228 Cases[0].CmpLHS == Cases[1].CmpRHS)) { 01229 return false; 01230 } 01231 01232 return true; 01233 } 01234 01235 void SelectionDAGLowering::visitBr(BranchInst &I) { 01236 // Update machine-CFG edges. 01237 MachineBasicBlock *Succ0MBB = FuncInfo.MBBMap[I.getSuccessor(0)]; 01238 01239 // Figure out which block is immediately after the current one. 01240 MachineBasicBlock *NextBlock = 0; 01241 MachineFunction::iterator BBI = CurMBB; 01242 if (++BBI != FuncInfo.MF->end()) 01243 NextBlock = BBI; 01244 01245 if (I.isUnconditional()) { 01246 // Update machine-CFG edges. 01247 CurMBB->addSuccessor(Succ0MBB); 01248 01249 // If this is not a fall-through branch, emit the branch. 01250 if (Succ0MBB != NextBlock) 01251 DAG.setRoot(DAG.getNode(ISD::BR, getCurDebugLoc(), 01252 MVT::Other, getControlRoot(), 01253 DAG.getBasicBlock(Succ0MBB))); 01254 return; 01255 } 01256 01257 // If this condition is one of the special cases we handle, do special stuff 01258 // now. 01259 Value *CondVal = I.getCondition(); 01260 MachineBasicBlock *Succ1MBB = FuncInfo.MBBMap[I.getSuccessor(1)]; 01261 01262 // If this is a series of conditions that are or'd or and'd together, emit 01263 // this as a sequence of branches instead of setcc's with and/or operations. 01264 // For example, instead of something like: 01265 // cmp A, B 01266 // C = seteq 01267 // cmp D, E 01268 // F = setle 01269 // or C, F 01270 // jnz foo 01271 // Emit: 01272 // cmp A, B 01273 // je foo 01274 // cmp D, E 01275 // jle foo 01276 // 01277 if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(CondVal)) { 01278 if (BOp->hasOneUse() && 01279 (BOp->getOpcode() == Instruction::And || 01280 BOp->getOpcode() == Instruction::Or)) { 01281 FindMergedConditions(BOp, Succ0MBB, Succ1MBB, CurMBB, BOp->getOpcode()); 01282 // If the compares in later blocks need to use values not currently 01283 // exported from this block, export them now. This block should always 01284 // be the first entry. 01285 assert(SwitchCases[0].ThisBB == CurMBB && "Unexpected lowering!"); 01286 01287 // Allow some cases to be rejected. 01288 if (ShouldEmitAsBranches(SwitchCases)) { 01289 for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) { 01290 ExportFromCurrentBlock(SwitchCases[i].CmpLHS); 01291 ExportFromCurrentBlock(SwitchCases[i].CmpRHS); 01292 } 01293 01294 // Emit the branch for this block. 01295 visitSwitchCase(SwitchCases[0]); 01296 SwitchCases.erase(SwitchCases.begin()); 01297 return; 01298 } 01299 01300 // Okay, we decided not to do this, remove any inserted MBB's and clear 01301 // SwitchCases. 01302 for (unsigned i = 1, e = SwitchCases.size(); i != e; ++i) 01303 FuncInfo.MF->erase(SwitchCases[i].ThisBB); 01304 01305 SwitchCases.clear(); 01306 } 01307 } 01308 01309 // Create a CaseBlock record representing this branch. 01310 CaseBlock CB(ISD::SETEQ, CondVal, ConstantInt::getTrue(*DAG.getContext()), 01311 NULL, Succ0MBB, Succ1MBB, CurMBB); 01312 // Use visitSwitchCase to actually insert the fast branch sequence for this 01313 // cond branch. 01314 visitSwitchCase(CB); 01315 } 01316 01317 /// visitSwitchCase - Emits the necessary code to represent a single node in 01318 /// the binary search tree resulting from lowering a switch instruction. 01319 void SelectionDAGLowering::visitSwitchCase(CaseBlock &CB) { 01320 SDValue Cond; 01321 SDValue CondLHS = getValue(CB.CmpLHS); 01322 DebugLoc dl = getCurDebugLoc(); 01323 01324 // Build the setcc now. 01325 if (CB.CmpMHS == NULL) { 01326 // Fold "(X == true)" to X and "(X == false)" to !X to 01327 // handle common cases produced by branch lowering. 01328 if (CB.CmpRHS == ConstantInt::getTrue(*DAG.getContext()) && 01329 CB.CC == ISD::SETEQ) 01330 Cond = CondLHS; 01331 else if (CB.CmpRHS == ConstantInt::getFalse(*DAG.getContext()) && 01332 CB.CC == ISD::SETEQ) { 01333 SDValue True = DAG.getConstant(1, CondLHS.getValueType()); 01334 Cond = DAG.getNode(ISD::XOR, dl, CondLHS.getValueType(), CondLHS, True); 01335 } else 01336 Cond = DAG.getSetCC(dl, MVT::i1, CondLHS, getValue(CB.CmpRHS), CB.CC); 01337 } else { 01338 assert(CB.CC == ISD::SETLE && "Can handle only LE ranges now"); 01339 01340 const APInt& Low = cast<ConstantInt>(CB.CmpLHS)->getValue(); 01341 const APInt& High = cast<ConstantInt>(CB.CmpRHS)->getValue(); 01342 01343 SDValue CmpOp = getValue(CB.CmpMHS); 01344 EVT VT = CmpOp.getValueType(); 01345 01346 if (cast<ConstantInt>(CB.CmpLHS)->isMinValue(true)) { 01347 Cond = DAG.getSetCC(dl, MVT::i1, CmpOp, DAG.getConstant(High, VT), 01348 ISD::SETLE); 01349 } else { 01350 SDValue SUB = DAG.getNode(ISD::SUB, dl, 01351 VT, CmpOp, DAG.getConstant(Low, VT)); 01352 Cond = DAG.getSetCC(dl, MVT::i1, SUB, 01353 DAG.getConstant(High-Low, VT), ISD::SETULE); 01354 } 01355 } 01356 01357 // Update successor info 01358 CurMBB->addSuccessor(CB.TrueBB); 01359 CurMBB->addSuccessor(CB.FalseBB); 01360 01361 // Set NextBlock to be the MBB immediately after the current one, if any. 01362 // This is used to avoid emitting unnecessary branches to the next block. 01363 MachineBasicBlock *NextBlock = 0; 01364 MachineFunction::iterator BBI = CurMBB; 01365 if (++BBI != FuncInfo.MF->end()) 01366 NextBlock = BBI; 01367 01368 // If the lhs block is the next block, invert the condition so that we can 01369 // fall through to the lhs instead of the rhs block. 01370 if (CB.TrueBB == NextBlock) { 01371 std::swap(CB.TrueBB, CB.FalseBB); 01372 SDValue True = DAG.getConstant(1, Cond.getValueType()); 01373 Cond = DAG.getNode(ISD::XOR, dl, Cond.getValueType(), Cond, True); 01374 } 01375 SDValue BrCond = DAG.getNode(ISD::BRCOND, dl, 01376 MVT::Other, getControlRoot(), Cond, 01377 DAG.getBasicBlock(CB.TrueBB)); 01378 01379 // If the branch was constant folded, fix up the CFG. 01380 if (BrCond.getOpcode() == ISD::BR) { 01381 CurMBB->removeSuccessor(CB.FalseBB); 01382 DAG.setRoot(BrCond); 01383 } else { 01384 // Otherwise, go ahead and insert the false branch. 01385 if (BrCond == getControlRoot()) 01386 CurMBB->removeSuccessor(CB.TrueBB); 01387 01388 if (CB.FalseBB == NextBlock) 01389 DAG.setRoot(BrCond); 01390 else 01391 DAG.setRoot(DAG.getNode(ISD::BR, dl, MVT::Other, BrCond, 01392 DAG.getBasicBlock(CB.FalseBB))); 01393 } 01394 } 01395 01396 /// visitJumpTable - Emit JumpTable node in the current MBB 01397 void SelectionDAGLowering::visitJumpTable(JumpTable &JT) { 01398 // Emit the code for the jump table 01399 assert(JT.Reg != -1U && "Should lower JT Header first!"); 01400 EVT PTy = TLI.getPointerTy(); 01401 SDValue Index = DAG.getCopyFromReg(getControlRoot(), getCurDebugLoc(), 01402 JT.Reg, PTy); 01403 SDValue Table = DAG.getJumpTable(JT.JTI, PTy); 01404 DAG.setRoot(DAG.getNode(ISD::BR_JT, getCurDebugLoc(), 01405 MVT::Other, Index.getValue(1), 01406 Table, Index)); 01407 } 01408 01409 /// visitJumpTableHeader - This function emits necessary code to produce index 01410 /// in the JumpTable from switch case. 01411 void SelectionDAGLowering::visitJumpTableHeader(JumpTable &JT, 01412 JumpTableHeader &JTH) { 01413 // Subtract the lowest switch case value from the value being switched on and 01414 // conditional branch to default mbb if the result is greater than the 01415 // difference between smallest and largest cases. 01416 SDValue SwitchOp = getValue(JTH.SValue); 01417 EVT VT = SwitchOp.getValueType(); 01418 SDValue SUB = DAG.getNode(ISD::SUB, getCurDebugLoc(), VT, SwitchOp, 01419 DAG.getConstant(JTH.First, VT)); 01420 01421 // The SDNode we just created, which holds the value being switched on minus 01422 // the the smallest case value, needs to be copied to a virtual register so it 01423 // can be used as an index into the jump table in a subsequent basic block. 01424 // This value may be smaller or larger than the target's pointer type, and 01425 // therefore require extension or truncating. 01426 if (VT.bitsGT(TLI.getPointerTy())) 01427 SwitchOp = DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(), 01428 TLI.getPointerTy(), SUB); 01429 else 01430 SwitchOp = DAG.getNode(ISD::ZERO_EXTEND, getCurDebugLoc(), 01431 TLI.getPointerTy(), SUB); 01432 01433 unsigned JumpTableReg = FuncInfo.MakeReg(TLI.getPointerTy()); 01434 SDValue CopyTo = DAG.getCopyToReg(getControlRoot(), getCurDebugLoc(), 01435 JumpTableReg, SwitchOp); 01436 JT.Reg = JumpTableReg; 01437 01438 // Emit the range check for the jump table, and branch to the default block 01439 // for the switch statement if the value being switched on exceeds the largest 01440 // case in the switch. 01441 SDValue CMP = DAG.getSetCC(getCurDebugLoc(), 01442 TLI.getSetCCResultType(SUB.getValueType()), SUB, 01443 DAG.getConstant(JTH.Last-JTH.First,VT), 01444 ISD::SETUGT); 01445 01446 // Set NextBlock to be the MBB immediately after the current one, if any. 01447 // This is used to avoid emitting unnecessary branches to the next block. 01448 MachineBasicBlock *NextBlock = 0; 01449 MachineFunction::iterator BBI = CurMBB; 01450 if (++BBI != FuncInfo.MF->end()) 01451 NextBlock = BBI; 01452 01453 SDValue BrCond = DAG.getNode(ISD::BRCOND, getCurDebugLoc(), 01454 MVT::Other, CopyTo, CMP, 01455 DAG.getBasicBlock(JT.Default)); 01456 01457 if (JT.MBB == NextBlock) 01458 DAG.setRoot(BrCond); 01459 else 01460 DAG.setRoot(DAG.getNode(ISD::BR, getCurDebugLoc(), MVT::Other, BrCond, 01461 DAG.getBasicBlock(JT.MBB))); 01462 } 01463 01464 /// visitBitTestHeader - This function emits necessary code to produce value 01465 /// suitable for "bit tests" 01466 void SelectionDAGLowering::visitBitTestHeader(BitTestBlock &B) { 01467 // Subtract the minimum value 01468 SDValue SwitchOp = getValue(B.SValue); 01469 EVT VT = SwitchOp.getValueType(); 01470 SDValue SUB = DAG.getNode(ISD::SUB, getCurDebugLoc(), VT, SwitchOp, 01471 DAG.getConstant(B.First, VT)); 01472 01473 // Check range 01474 SDValue RangeCmp = DAG.getSetCC(getCurDebugLoc(), 01475 TLI.getSetCCResultType(SUB.getValueType()), 01476 SUB, DAG.getConstant(B.Range, VT), 01477 ISD::SETUGT); 01478 01479 SDValue ShiftOp; 01480 if (VT.bitsGT(TLI.getPointerTy())) 01481 ShiftOp = DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(), 01482 TLI.getPointerTy(), SUB); 01483 else 01484 ShiftOp = DAG.getNode(ISD::ZERO_EXTEND, getCurDebugLoc(), 01485 TLI.getPointerTy(), SUB); 01486 01487 B.Reg = FuncInfo.MakeReg(TLI.getPointerTy()); 01488 SDValue CopyTo = DAG.getCopyToReg(getControlRoot(), getCurDebugLoc(), 01489 B.Reg, ShiftOp); 01490 01491 // Set NextBlock to be the MBB immediately after the current one, if any. 01492 // This is used to avoid emitting unnecessary branches to the next block. 01493 MachineBasicBlock *NextBlock = 0; 01494 MachineFunction::iterator BBI = CurMBB; 01495 if (++BBI != FuncInfo.MF->end()) 01496 NextBlock = BBI; 01497 01498 MachineBasicBlock* MBB = B.Cases[0].ThisBB; 01499 01500 CurMBB->addSuccessor(B.Default); 01501 CurMBB->addSuccessor(MBB); 01502 01503 SDValue BrRange = DAG.getNode(ISD::BRCOND, getCurDebugLoc(), 01504 MVT::Other, CopyTo, RangeCmp, 01505 DAG.getBasicBlock(B.Default)); 01506 01507 if (MBB == NextBlock) 01508 DAG.setRoot(BrRange); 01509 else 01510 DAG.setRoot(DAG.getNode(ISD::BR, getCurDebugLoc(), MVT::Other, CopyTo, 01511 DAG.getBasicBlock(MBB))); 01512 } 01513 01514 /// visitBitTestCase - this function produces one "bit test" 01515 void SelectionDAGLowering::visitBitTestCase(MachineBasicBlock* NextMBB, 01516 unsigned Reg, 01517 BitTestCase &B) { 01518 // Make desired shift 01519 SDValue ShiftOp = DAG.getCopyFromReg(getControlRoot(), getCurDebugLoc(), Reg, 01520 TLI.getPointerTy()); 01521 SDValue SwitchVal = DAG.getNode(ISD::SHL, getCurDebugLoc(), 01522 TLI.getPointerTy(), 01523 DAG.getConstant(1, TLI.getPointerTy()), 01524 ShiftOp); 01525 01526 // Emit bit tests and jumps 01527 SDValue AndOp = DAG.getNode(ISD::AND, getCurDebugLoc(), 01528 TLI.getPointerTy(), SwitchVal, 01529 DAG.getConstant(B.Mask, TLI.getPointerTy())); 01530 SDValue AndCmp = DAG.getSetCC(getCurDebugLoc(), 01531 TLI.getSetCCResultType(AndOp.getValueType()), 01532 AndOp, DAG.getConstant(0, TLI.getPointerTy()), 01533 ISD::SETNE); 01534 01535 CurMBB->addSuccessor(B.TargetBB); 01536 CurMBB->addSuccessor(NextMBB); 01537 01538 SDValue BrAnd = DAG.getNode(ISD::BRCOND, getCurDebugLoc(), 01539 MVT::Other, getControlRoot(), 01540 AndCmp, DAG.getBasicBlock(B.TargetBB)); 01541 01542 // Set NextBlock to be the MBB immediately after the current one, if any. 01543 // This is used to avoid emitting unnecessary branches to the next block. 01544 MachineBasicBlock *NextBlock = 0; 01545 MachineFunction::iterator BBI = CurMBB; 01546 if (++BBI != FuncInfo.MF->end()) 01547 NextBlock = BBI; 01548 01549 if (NextMBB == NextBlock) 01550 DAG.setRoot(BrAnd); 01551 else 01552 DAG.setRoot(DAG.getNode(ISD::BR, getCurDebugLoc(), MVT::Other, BrAnd, 01553 DAG.getBasicBlock(NextMBB))); 01554 } 01555 01556 void SelectionDAGLowering::visitInvoke(InvokeInst &I) { 01557 // Retrieve successors. 01558 MachineBasicBlock *Return = FuncInfo.MBBMap[I.getSuccessor(0)]; 01559 MachineBasicBlock *LandingPad = FuncInfo.MBBMap[I.getSuccessor(1)]; 01560 01561 const Value *Callee(I.getCalledValue()); 01562 if (isa<InlineAsm>(Callee)) 01563 visitInlineAsm(&I); 01564 else 01565 LowerCallTo(&I, getValue(Callee), false, LandingPad); 01566 01567 // If the value of the invoke is used outside of its defining block, make it 01568 // available as a virtual register. 01569 CopyToExportRegsIfNeeded(&I); 01570 01571 // Update successor info 01572 CurMBB->addSuccessor(Return); 01573 CurMBB->addSuccessor(LandingPad); 01574 01575 // Drop into normal successor. 01576 DAG.setRoot(DAG.getNode(ISD::BR, getCurDebugLoc(), 01577 MVT::Other, getControlRoot(), 01578 DAG.getBasicBlock(Return))); 01579 } 01580 01581 void SelectionDAGLowering::visitUnwind(UnwindInst &I) { 01582 } 01583 01584 /// handleSmallSwitchCaseRange - Emit a series of specific tests (suitable for 01585 /// small case ranges). 01586 bool SelectionDAGLowering::handleSmallSwitchRange(CaseRec& CR, 01587 CaseRecVector& WorkList, 01588 Value* SV, 01589 MachineBasicBlock* Default) { 01590 Case& BackCase = *(CR.Range.second-1); 01591 01592 // Size is the number of Cases represented by this range. 01593 size_t Size = CR.Range.second - CR.Range.first; 01594 if (Size > 3) 01595 return false; 01596 01597 // Get the MachineFunction which holds the current MBB. This is used when 01598 // inserting any additional MBBs necessary to represent the switch. 01599 MachineFunction *CurMF = FuncInfo.MF; 01600 01601 // Figure out which block is immediately after the current one. 01602 MachineBasicBlock *NextBlock = 0; 01603 MachineFunction::iterator BBI = CR.CaseBB; 01604 01605 if (++BBI != FuncInfo.MF->end()) 01606 NextBlock = BBI; 01607 01608 // TODO: If any two of the cases has the same destination, and if one value 01609 // is the same as the other, but has one bit unset that the other has set, 01610 // use bit manipulation to do two compares at once. For example: 01611 // "if (X == 6 || X == 4)" -> "if ((X|2) == 6)" 01612 01613 // Rearrange the case blocks so that the last one falls through if possible. 01614 if (NextBlock && Default != NextBlock && BackCase.BB != NextBlock) { 01615 // The last case block won't fall through into 'NextBlock' if we emit the 01616 // branches in this order. See if rearranging a case value would help. 01617 for (CaseItr I = CR.Range.first, E = CR.Range.second-1; I != E; ++I) { 01618 if (I->BB == NextBlock) { 01619 std::swap(*I, BackCase); 01620 break; 01621 } 01622 } 01623 } 01624 01625 // Create a CaseBlock record representing a conditional branch to 01626 // the Case's target mbb if the value being switched on SV is equal 01627 // to C. 01628 MachineBasicBlock *CurBlock = CR.CaseBB; 01629 for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++I) { 01630 MachineBasicBlock *FallThrough; 01631 if (I != E-1) { 01632 FallThrough = CurMF->CreateMachineBasicBlock(CurBlock->getBasicBlock()); 01633 CurMF->insert(BBI, FallThrough); 01634 01635 // Put SV in a virtual register to make it available from the new blocks. 01636 ExportFromCurrentBlock(SV); 01637 } else { 01638 // If the last case doesn't match, go to the default block. 01639 FallThrough = Default; 01640 } 01641 01642 Value *RHS, *LHS, *MHS; 01643 ISD::CondCode CC; 01644 if (I->High == I->Low) { 01645 // This is just small small case range :) containing exactly 1 case 01646 CC = ISD::SETEQ; 01647 LHS = SV; RHS = I->High; MHS = NULL; 01648 } else { 01649 CC = ISD::SETLE; 01650 LHS = I->Low; MHS = SV; RHS = I->High; 01651 } 01652 CaseBlock CB(CC, LHS, RHS, MHS, I->BB, FallThrough, CurBlock); 01653 01654 // If emitting the first comparison, just call visitSwitchCase to emit the 01655 // code into the current block. Otherwise, push the CaseBlock onto the 01656 // vector to be later processed by SDISel, and insert the node's MBB 01657 // before the next MBB. 01658 if (CurBlock == CurMBB) 01659 visitSwitchCase(CB); 01660 else 01661 SwitchCases.push_back(CB); 01662 01663 CurBlock = FallThrough; 01664 } 01665 01666 return true; 01667 } 01668 01669 static inline bool areJTsAllowed(const TargetLowering &TLI) { 01670 return !DisableJumpTables && 01671 (TLI.isOperationLegalOrCustom(ISD::BR_JT, MVT::Other) || 01672 TLI.isOperationLegalOrCustom(ISD::BRIND, MVT::Other)); 01673 } 01674 01675 static APInt ComputeRange(const APInt &First, const APInt &Last) { 01676 APInt LastExt(Last), FirstExt(First); 01677 uint32_t BitWidth = std::max(Last.getBitWidth(), First.getBitWidth()) + 1; 01678 LastExt.sext(BitWidth); FirstExt.sext(BitWidth); 01679 return (LastExt - FirstExt + 1ULL); 01680 } 01681 01682 /// handleJTSwitchCase - Emit jumptable for current switch case range 01683 bool SelectionDAGLowering::handleJTSwitchCase(CaseRec& CR, 01684 CaseRecVector& WorkList, 01685 Value* SV, 01686 MachineBasicBlock* Default) { 01687 Case& FrontCase = *CR.Range.first; 01688 Case& BackCase = *(CR.Range.second-1); 01689 01690 const APInt& First = cast<ConstantInt>(FrontCase.Low)->getValue(); 01691 const APInt& Last = cast<ConstantInt>(BackCase.High)->getValue(); 01692 01693 size_t TSize = 0; 01694 for (CaseItr I = CR.Range.first, E = CR.Range.second; 01695 I!=E; ++I) 01696 TSize += I->size(); 01697 01698 if (!areJTsAllowed(TLI) || TSize <= 3) 01699 return false; 01700 01701 APInt Range = ComputeRange(First, Last); 01702 double Density = (double)TSize / Range.roundToDouble(); 01703 if (Density < 0.4) 01704 return false; 01705 01706 DEBUG(errs() << "Lowering jump table\n" 01707 << "First entry: " << First << ". Last entry: " << Last << '\n' 01708 << "Range: " << Range 01709 << "Size: " << TSize << ". Density: " << Density << "\n\n"); 01710 01711 // Get the MachineFunction which holds the current MBB. This is used when 01712 // inserting any additional MBBs necessary to represent the switch. 01713 MachineFunction *CurMF = FuncInfo.MF; 01714 01715 // Figure out which block is immediately after the current one. 01716 MachineBasicBlock *NextBlock = 0; 01717 MachineFunction::iterator BBI = CR.CaseBB; 01718 01719 if (++BBI != FuncInfo.MF->end()) 01720 NextBlock = BBI; 01721 01722 const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock(); 01723 01724 // Create a new basic block to hold the code for loading the address 01725 // of the jump table, and jumping to it. Update successor information; 01726 // we will either branch to the default case for the switch, or the jump 01727 // table. 01728 MachineBasicBlock *JumpTableBB = CurMF->CreateMachineBasicBlock(LLVMBB); 01729 CurMF->insert(BBI, JumpTableBB); 01730 CR.CaseBB->addSuccessor(Default); 01731 CR.CaseBB->addSuccessor(JumpTableBB); 01732 01733 // Build a vector of destination BBs, corresponding to each target 01734 // of the jump table. If the value of the jump table slot corresponds to 01735 // a case statement, push the case's BB onto the vector, otherwise, push 01736 // the default BB. 01737 std::vector<MachineBasicBlock*> DestBBs; 01738 APInt TEI = First; 01739 for (CaseItr I = CR.Range.first, E = CR.Range.second; I != E; ++TEI) { 01740 const APInt& Low = cast<ConstantInt>(I->Low)->getValue(); 01741 const APInt& High = cast<ConstantInt>(I->High)->getValue(); 01742 01743 if (Low.sle(TEI) && TEI.sle(High)) { 01744 DestBBs.push_back(I->BB); 01745 if (TEI==High) 01746 ++I; 01747 } else { 01748 DestBBs.push_back(Default); 01749 } 01750 } 01751 01752 // Update successor info. Add one edge to each unique successor. 01753 BitVector SuccsHandled(CR.CaseBB->getParent()->getNumBlockIDs()); 01754 for (std::vector<MachineBasicBlock*>::iterator I = DestBBs.begin(), 01755 E = DestBBs.end(); I != E; ++I) { 01756 if (!SuccsHandled[(*I)->getNumber()]) { 01757 SuccsHandled[(*I)->getNumber()] = true; 01758 JumpTableBB->addSuccessor(*I); 01759 } 01760 } 01761 01762 // Create a jump table index for this jump table, or return an existing 01763 // one. 01764 unsigned JTI = CurMF->getJumpTableInfo()->getJumpTableIndex(DestBBs); 01765 01766 // Set the jump table information so that we can codegen it as a second 01767 // MachineBasicBlock 01768 JumpTable JT(-1U, JTI, JumpTableBB, Default); 01769 JumpTableHeader JTH(First, Last, SV, CR.CaseBB, (CR.CaseBB == CurMBB)); 01770 if (CR.CaseBB == CurMBB) 01771 visitJumpTableHeader(JT, JTH); 01772 01773 JTCases.push_back(JumpTableBlock(JTH, JT)); 01774 01775 return true; 01776 } 01777 01778 /// handleBTSplitSwitchCase - emit comparison and split binary search tree into 01779 /// 2 subtrees. 01780 bool SelectionDAGLowering::handleBTSplitSwitchCase(CaseRec& CR, 01781 CaseRecVector& WorkList, 01782 Value* SV, 01783 MachineBasicBlock* Default) { 01784 // Get the MachineFunction which holds the current MBB. This is used when 01785 // inserting any additional MBBs necessary to represent the switch. 01786 MachineFunction *CurMF = FuncInfo.MF; 01787 01788 // Figure out which block is immediately after the current one. 01789 MachineBasicBlock *NextBlock = 0; 01790 MachineFunction::iterator BBI = CR.CaseBB; 01791 01792 if (++BBI != FuncInfo.MF->end()) 01793 NextBlock = BBI; 01794 01795 Case& FrontCase = *CR.Range.first; 01796 Case& BackCase = *(CR.Range.second-1); 01797 const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock(); 01798 01799 // Size is the number of Cases represented by this range. 01800 unsigned Size = CR.Range.second - CR.Range.first; 01801 01802 const APInt& First = cast<ConstantInt>(FrontCase.Low)->getValue(); 01803 const APInt& Last = cast<ConstantInt>(BackCase.High)->getValue(); 01804 double FMetric = 0; 01805 CaseItr Pivot = CR.Range.first + Size/2; 01806 01807 // Select optimal pivot, maximizing sum density of LHS and RHS. This will 01808 // (heuristically) allow us to emit JumpTable's later. 01809 size_t TSize = 0; 01810 for (CaseItr I = CR.Range.first, E = CR.Range.second; 01811 I!=E; ++I) 01812 TSize += I->size(); 01813 01814 size_t LSize = FrontCase.size(); 01815 size_t RSize = TSize-LSize; 01816 DEBUG(errs() << "Selecting best pivot: \n" 01817 << "First: " << First << ", Last: " << Last <<'\n' 01818 << "LSize: " << LSize << ", RSize: " << RSize << '\n'); 01819 for (CaseItr I = CR.Range.first, J=I+1, E = CR.Range.second; 01820 J!=E; ++I, ++J) { 01821 const APInt& LEnd = cast<ConstantInt>(I->High)->getValue(); 01822 const APInt& RBegin = cast<ConstantInt>(J->Low)->getValue(); 01823 APInt Range = ComputeRange(LEnd, RBegin); 01824 assert((Range - 2ULL).isNonNegative() && 01825 "Invalid case distance"); 01826 double LDensity = (double)LSize / (LEnd - First + 1ULL).roundToDouble(); 01827 double RDensity = (double)RSize / (Last - RBegin + 1ULL).roundToDouble(); 01828 double Metric = Range.logBase2()*(LDensity+RDensity); 01829 // Should always split in some non-trivial place 01830 DEBUG(errs() <<"=>Step\n" 01831 << "LEnd: " << LEnd << ", RBegin: " << RBegin << '\n' 01832 << "LDensity: " << LDensity 01833 << ", RDensity: " << RDensity << '\n' 01834 << "Metric: " << Metric << '\n'); 01835 if (FMetric < Metric) { 01836 Pivot = J; 01837 FMetric = Metric; 01838 DEBUG(errs() << "Current metric set to: " << FMetric << '\n'); 01839 } 01840 01841 LSize += J->size(); 01842 RSize -= J->size(); 01843 } 01844 if (areJTsAllowed(TLI)) { 01845 // If our case is dense we *really* should handle it earlier! 01846 assert((FMetric > 0) && "Should handle dense range earlier!"); 01847 } else { 01848 Pivot = CR.Range.first + Size/2; 01849 } 01850 01851 CaseRange LHSR(CR.Range.first, Pivot); 01852 CaseRange RHSR(Pivot, CR.Range.second); 01853 Constant *C = Pivot->Low; 01854 MachineBasicBlock *FalseBB = 0, *TrueBB = 0; 01855 01856 // We know that we branch to the LHS if the Value being switched on is 01857 // less than the Pivot value, C. We use this to optimize our binary 01858 // tree a bit, by recognizing that if SV is greater than or equal to the 01859 // LHS's Case Value, and that Case Value is exactly one less than the 01860 // Pivot's Value, then we can branch directly to the LHS's Target, 01861 // rather than creating a leaf node for it. 01862 if ((LHSR.second - LHSR.first) == 1 && 01863 LHSR.first->High == CR.GE && 01864 cast<ConstantInt>(C)->getValue() == 01865 (cast<ConstantInt>(CR.GE)->getValue() + 1LL)) { 01866 TrueBB = LHSR.first->BB; 01867 } else { 01868 TrueBB = CurMF->CreateMachineBasicBlock(LLVMBB); 01869 CurMF->insert(BBI, TrueBB); 01870 WorkList.push_back(CaseRec(TrueBB, C, CR.GE, LHSR)); 01871 01872 // Put SV in a virtual register to make it available from the new blocks. 01873 ExportFromCurrentBlock(SV); 01874 } 01875 01876 // Similar to the optimization above, if the Value being switched on is 01877 // known to be less than the Constant CR.LT, and the current Case Value 01878 // is CR.LT - 1, then we can branch directly to the target block for 01879 // the current Case Value, rather than emitting a RHS leaf node for it. 01880 if ((RHSR.second - RHSR.first) == 1 && CR.LT && 01881 cast<ConstantInt>(RHSR.first->Low)->getValue() == 01882 (cast<ConstantInt>(CR.LT)->getValue() - 1LL)) { 01883 FalseBB = RHSR.first->BB; 01884 } else { 01885 FalseBB = CurMF->CreateMachineBasicBlock(LLVMBB); 01886 CurMF->insert(BBI, FalseBB); 01887 WorkList.push_back(CaseRec(FalseBB,CR.LT,C,RHSR)); 01888 01889 // Put SV in a virtual register to make it available from the new blocks. 01890 ExportFromCurrentBlock(SV); 01891 } 01892 01893 // Create a CaseBlock record representing a conditional branch to 01894 // the LHS node if the value being switched on SV is less than C. 01895 // Otherwise, branch to LHS. 01896 CaseBlock CB(ISD::SETLT, SV, C, NULL, TrueBB, FalseBB, CR.CaseBB); 01897 01898 if (CR.CaseBB == CurMBB) 01899 visitSwitchCase(CB); 01900 else 01901 SwitchCases.push_back(CB); 01902 01903 return true; 01904 } 01905 01906 /// handleBitTestsSwitchCase - if current case range has few destination and 01907 /// range span less, than machine word bitwidth, encode case range into series 01908 /// of masks and emit bit tests with these masks. 01909 bool SelectionDAGLowering::handleBitTestsSwitchCase(CaseRec& CR, 01910 CaseRecVector& WorkList, 01911 Value* SV, 01912 MachineBasicBlock* Default){ 01913 EVT PTy = TLI.getPointerTy(); 01914 unsigned IntPtrBits = PTy.getSizeInBits(); 01915 01916 Case& FrontCase = *CR.Range.first; 01917 Case& BackCase = *(CR.Range.second-1); 01918 01919 // Get the MachineFunction which holds the current MBB. This is used when 01920 // inserting any additional MBBs necessary to represent the switch. 01921 MachineFunction *CurMF = FuncInfo.MF; 01922 01923 // If target does not have legal shift left, do not emit bit tests at all. 01924 if (!TLI.isOperationLegal(ISD::SHL, TLI.getPointerTy())) 01925 return false; 01926 01927 size_t numCmps = 0; 01928 for (CaseItr I = CR.Range.first, E = CR.Range.second; 01929 I!=E; ++I) { 01930 // Single case counts one, case range - two. 01931 numCmps += (I->Low == I->High ? 1 : 2); 01932 } 01933 01934 // Count unique destinations 01935 SmallSet<MachineBasicBlock*, 4> Dests; 01936 for (CaseItr I = CR.Range.first, E = CR.Range.second; I!=E; ++I) { 01937 Dests.insert(I->BB); 01938 if (Dests.size() > 3) 01939 // Don't bother the code below, if there are too much unique destinations 01940 return false; 01941 } 01942 DEBUG(errs() << "Total number of unique destinations: " << Dests.size() << '\n' 01943 << "Total number of comparisons: " << numCmps << '\n'); 01944 01945 // Compute span of values. 01946 const APInt& minValue = cast<ConstantInt>(FrontCase.Low)->getValue(); 01947 const APInt& maxValue = cast<ConstantInt>(BackCase.High)->getValue(); 01948 APInt cmpRange = maxValue - minValue; 01949 01950 DEBUG(errs() << "Compare range: " << cmpRange << '\n' 01951 << "Low bound: " << minValue << '\n' 01952 << "High bound: " << maxValue << '\n'); 01953 01954 if (cmpRange.uge(APInt(cmpRange.getBitWidth(), IntPtrBits)) || 01955 (!(Dests.size() == 1 && numCmps >= 3) && 01956 !(Dests.size() == 2 && numCmps >= 5) && 01957 !(Dests.size() >= 3 && numCmps >= 6))) 01958 return false; 01959 01960 DEBUG(errs() << "Emitting bit tests\n"); 01961 APInt lowBound = APInt::getNullValue(cmpRange.getBitWidth()); 01962 01963 // Optimize the case where all the case values fit in a 01964 // word without having to subtract minValue. In this case, 01965 // we can optimize away the subtraction. 01966 if (minValue.isNonNegative() && 01967 maxValue.slt(APInt(maxValue.getBitWidth(), IntPtrBits))) { 01968 cmpRange = maxValue; 01969 } else { 01970 lowBound = minValue; 01971 } 01972 01973 CaseBitsVector CasesBits; 01974 unsigned i, count = 0; 01975 01976 for (CaseItr I = CR.Range.first, E = CR.Range.second; I!=E; ++I) { 01977 MachineBasicBlock* Dest = I->BB; 01978 for (i = 0; i < count; ++i) 01979 if (Dest == CasesBits[i].BB) 01980 break; 01981 01982 if (i == count) { 01983 assert((count < 3) && "Too much destinations to test!"); 01984 CasesBits.push_back(CaseBits(0, Dest, 0)); 01985 count++; 01986 } 01987 01988 const APInt& lowValue = cast<ConstantInt>(I->Low)->getValue(); 01989 const APInt& highValue = cast<ConstantInt>(I->High)->getValue(); 01990 01991 uint64_t lo = (lowValue - lowBound).getZExtValue(); 01992 uint64_t hi = (highValue - lowBound).getZExtValue(); 01993 01994 for (uint64_t j = lo; j <= hi; j++) { 01995 CasesBits[i].Mask |= 1ULL << j; 01996 CasesBits[i].Bits++; 01997 } 01998 01999 } 02000 std::sort(CasesBits.begin(), CasesBits.end(), CaseBitsCmp()); 02001 02002 BitTestInfo BTC; 02003 02004 // Figure out which block is immediately after the current one. 02005 MachineFunction::iterator BBI = CR.CaseBB; 02006 ++BBI; 02007 02008 const BasicBlock *LLVMBB = CR.CaseBB->getBasicBlock(); 02009 02010 DEBUG(errs() << "Cases:\n"); 02011 for (unsigned i = 0, e = CasesBits.size(); i!=e; ++i) { 02012 DEBUG(errs() << "Mask: " << CasesBits[i].Mask 02013 << ", Bits: " << CasesBits[i].Bits 02014 << ", BB: " << CasesBits[i].BB << '\n'); 02015 02016 MachineBasicBlock *CaseBB = CurMF->CreateMachineBasicBlock(LLVMBB); 02017 CurMF->insert(BBI, CaseBB); 02018 BTC.push_back(BitTestCase(CasesBits[i].Mask, 02019 CaseBB, 02020 CasesBits[i].BB)); 02021 02022 // Put SV in a virtual register to make it available from the new blocks. 02023 ExportFromCurrentBlock(SV); 02024 } 02025 02026 BitTestBlock BTB(lowBound, cmpRange, SV, 02027 -1U, (CR.CaseBB == CurMBB), 02028 CR.CaseBB, Default, BTC); 02029 02030 if (CR.CaseBB == CurMBB) 02031 visitBitTestHeader(BTB); 02032 02033 BitTestCases.push_back(BTB); 02034 02035 return true; 02036 } 02037 02038 02039 /// Clusterify - Transform simple list of Cases into list of CaseRange's 02040 size_t SelectionDAGLowering::Clusterify(CaseVector& Cases, 02041 const SwitchInst& SI) { 02042 size_t numCmps = 0; 02043 02044 // Start with "simple" cases 02045 for (size_t i = 1; i < SI.getNumSuccessors(); ++i) { 02046 MachineBasicBlock *SMBB = FuncInfo.MBBMap[SI.getSuccessor(i)]; 02047 Cases.push_back(Case(SI.getSuccessorValue(i), 02048 SI.getSuccessorValue(i), 02049 SMBB)); 02050 } 02051 std::sort(Cases.begin(), Cases.end(), CaseCmp()); 02052 02053 // Merge case into clusters 02054 if (Cases.size() >= 2) 02055 // Must recompute end() each iteration because it may be 02056 // invalidated by erase if we hold on to it 02057 for (CaseItr I = Cases.begin(), J = ++(Cases.begin()); J != Cases.end(); ) { 02058 const APInt& nextValue = cast<ConstantInt>(J->Low)->getValue(); 02059 const APInt& currentValue = cast<ConstantInt>(I->High)->getValue(); 02060 MachineBasicBlock* nextBB = J->BB; 02061 MachineBasicBlock* currentBB = I->BB; 02062 02063 // If the two neighboring cases go to the same destination, merge them 02064 // into a single case. 02065 if ((nextValue - currentValue == 1) && (currentBB == nextBB)) { 02066 I->High = J->High; 02067 J = Cases.erase(J); 02068 } else { 02069 I = J++; 02070 } 02071 } 02072 02073 for (CaseItr I=Cases.begin(), E=Cases.end(); I!=E; ++I, ++numCmps) { 02074 if (I->Low != I->High) 02075 // A range counts double, since it requires two compares. 02076 ++numCmps; 02077 } 02078 02079 return numCmps; 02080 } 02081 02082 void SelectionDAGLowering::visitSwitch(SwitchInst &SI) { 02083 // Figure out which block is immediately after the current one. 02084 MachineBasicBlock *NextBlock = 0; 02085 02086 MachineBasicBlock *Default = FuncInfo.MBBMap[SI.getDefaultDest()]; 02087 02088 // If there is only the default destination, branch to it if it is not the 02089 // next basic block. Otherwise, just fall through. 02090 if (SI.getNumOperands() == 2) { 02091 // Update machine-CFG edges. 02092 02093 // If this is not a fall-through branch, emit the branch. 02094 CurMBB->addSuccessor(Default); 02095 if (Default != NextBlock) 02096 DAG.setRoot(DAG.getNode(ISD::BR, getCurDebugLoc(), 02097 MVT::Other, getControlRoot(), 02098 DAG.getBasicBlock(Default))); 02099 return; 02100 } 02101 02102 // If there are any non-default case statements, create a vector of Cases 02103 // representing each one, and sort the vector so that we can efficiently 02104 // create a binary search tree from them. 02105 CaseVector Cases; 02106 size_t numCmps = Clusterify(Cases, SI); 02107 DEBUG(errs() << "Clusterify finished. Total clusters: " << Cases.size() 02108 << ". Total compares: " << numCmps << '\n'); 02109 numCmps = 0; 02110 02111 // Get the Value to be switched on and default basic blocks, which will be 02112 // inserted into CaseBlock records, representing basic blocks in the binary 02113 // search tree. 02114 Value *SV = SI.getOperand(0); 02115 02116 // Push the initial CaseRec onto the worklist 02117 CaseRecVector WorkList; 02118 WorkList.push_back(CaseRec(CurMBB,0,0,CaseRange(Cases.begin(),Cases.end()))); 02119 02120 while (!WorkList.empty()) { 02121 // Grab a record representing a case range to process off the worklist 02122 CaseRec CR = WorkList.back(); 02123 WorkList.pop_back(); 02124 02125 if (handleBitTestsSwitchCase(CR, WorkList, SV, Default)) 02126 continue; 02127 02128 // If the range has few cases (two or less) emit a series of specific 02129 // tests. 02130 if (handleSmallSwitchRange(CR, WorkList, SV, Default)) 02131 continue; 02132 02133 // If the switch has more than 5 blocks, and at least 40% dense, and the 02134 // target supports indirect branches, then emit a jump table rather than 02135 // lowering the switch to a binary tree of conditional branches. 02136 if (handleJTSwitchCase(CR, WorkList, SV, Default)) 02137 continue; 02138 02139 // Emit binary tree. We need to pick a pivot, and push left and right ranges 02140 // onto the worklist. Leafs are handled via handleSmallSwitchRange() call. 02141 handleBTSplitSwitchCase(CR, WorkList, SV, Default); 02142 } 02143 } 02144 02145 02146 void SelectionDAGLowering::visitFSub(User &I) { 02147 // -0.0 - X --> fneg 02148 const Type *Ty = I.getType(); 02149 if (isa<VectorType>(Ty)) { 02150 if (ConstantVector *CV = dyn_cast<ConstantVector>(I.getOperand(0))) { 02151 const VectorType *DestTy = cast<VectorType>(I.getType()); 02152 const Type *ElTy = DestTy->getElementType(); 02153 unsigned VL = DestTy->getNumElements(); 02154 std::vector<Constant*> NZ(VL, ConstantFP::getNegativeZero(ElTy)); 02155 Constant *CNZ = ConstantVector::get(&NZ[0], NZ.size()); 02156 if (CV == CNZ) { 02157 SDValue Op2 = getValue(I.getOperand(1)); 02158 setValue(&I, DAG.getNode(ISD::FNEG, getCurDebugLoc(), 02159 Op2.getValueType(), Op2)); 02160 return; 02161 } 02162 } 02163 } 02164 if (ConstantFP *CFP = dyn_cast<ConstantFP>(I.getOperand(0))) 02165 if (CFP->isExactlyValue(ConstantFP::getNegativeZero(Ty)->getValueAPF())) { 02166 SDValue Op2 = getValue(I.getOperand(1)); 02167 setValue(&I, DAG.getNode(ISD::FNEG, getCurDebugLoc(), 02168 Op2.getValueType(), Op2)); 02169 return; 02170 } 02171 02172 visitBinary(I, ISD::FSUB); 02173 } 02174 02175 void SelectionDAGLowering::visitBinary(User &I, unsigned OpCode) { 02176 SDValue Op1 = getValue(I.getOperand(0)); 02177 SDValue Op2 = getValue(I.getOperand(1)); 02178 02179 setValue(&I, DAG.getNode(OpCode, getCurDebugLoc(), 02180 Op1.getValueType(), Op1, Op2)); 02181 } 02182 02183 void SelectionDAGLowering::visitShift(User &I, unsigned Opcode) { 02184 SDValue Op1 = getValue(I.getOperand(0)); 02185 SDValue Op2 = getValue(I.getOperand(1)); 02186 if (!isa<VectorType>(I.getType()) && 02187 Op2.getValueType() != TLI.getShiftAmountTy()) { 02188 // If the operand is smaller than the shift count type, promote it. 02189 EVT PTy = TLI.getPointerTy(); 02190 EVT STy = TLI.getShiftAmountTy(); 02191 if (STy.bitsGT(Op2.getValueType())) 02192 Op2 = DAG.getNode(ISD::ANY_EXTEND, getCurDebugLoc(), 02193 TLI.getShiftAmountTy(), Op2); 02194 // If the operand is larger than the shift count type but the shift 02195 // count type has enough bits to represent any shift value, truncate 02196 // it now. This is a common case and it exposes the truncate to 02197 // optimization early. 02198 else if (STy.getSizeInBits() >= 02199 Log2_32_Ceil(Op2.getValueType().getSizeInBits())) 02200 Op2 = DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(), 02201 TLI.getShiftAmountTy(), Op2); 02202 // Otherwise we'll need to temporarily settle for some other 02203 // convenient type; type legalization will make adjustments as 02204 // needed. 02205 else if (PTy.bitsLT(Op2.getValueType())) 02206 Op2 = DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(), 02207 TLI.getPointerTy(), Op2); 02208 else if (PTy.bitsGT(Op2.getValueType())) 02209 Op2 = DAG.getNode(ISD::ANY_EXTEND, getCurDebugLoc(), 02210 TLI.getPointerTy(), Op2); 02211 } 02212 02213 setValue(&I, DAG.getNode(Opcode, getCurDebugLoc(), 02214 Op1.getValueType(), Op1, Op2)); 02215 } 02216 02217 void SelectionDAGLowering::visitICmp(User &I) { 02218 ICmpInst::Predicate predicate = ICmpInst::BAD_ICMP_PREDICATE; 02219 if (ICmpInst *IC = dyn_cast<ICmpInst>(&I)) 02220 predicate = IC->getPredicate(); 02221 else if (ConstantExpr *IC = dyn_cast<ConstantExpr>(&I)) 02222 predicate = ICmpInst::Predicate(IC->getPredicate()); 02223 SDValue Op1 = getValue(I.getOperand(0)); 02224 SDValue Op2 = getValue(I.getOperand(1)); 02225 ISD::CondCode Opcode = getICmpCondCode(predicate); 02226 02227 EVT DestVT = TLI.getValueType(I.getType()); 02228 setValue(&I, DAG.getSetCC(getCurDebugLoc(), DestVT, Op1, Op2, Opcode)); 02229 } 02230 02231 void SelectionDAGLowering::visitFCmp(User &I) { 02232 FCmpInst::Predicate predicate = FCmpInst::BAD_FCMP_PREDICATE; 02233 if (FCmpInst *FC = dyn_cast<FCmpInst>(&I)) 02234 predicate = FC->getPredicate(); 02235 else if (ConstantExpr *FC = dyn_cast<ConstantExpr>(&I)) 02236 predicate = FCmpInst::Predicate(FC->getPredicate()); 02237 SDValue Op1 = getValue(I.getOperand(0)); 02238 SDValue Op2 = getValue(I.getOperand(1)); 02239 ISD::CondCode Condition = getFCmpCondCode(predicate); 02240 EVT DestVT = TLI.getValueType(I.getType()); 02241 setValue(&I, DAG.getSetCC(getCurDebugLoc(), DestVT, Op1, Op2, Condition)); 02242 } 02243 02244 void SelectionDAGLowering::visitSelect(User &I) { 02245 SmallVector<EVT, 4> ValueVTs; 02246 ComputeValueVTs(TLI, I.getType(), ValueVTs); 02247 unsigned NumValues = ValueVTs.size(); 02248 if (NumValues != 0) { 02249 SmallVector<SDValue, 4> Values(NumValues); 02250 SDValue Cond = getValue(I.getOperand(0)); 02251 SDValue TrueVal = getValue(I.getOperand(1)); 02252 SDValue FalseVal = getValue(I.getOperand(2)); 02253 02254 for (unsigned i = 0; i != NumValues; ++i) 02255 Values[i] = DAG.getNode(ISD::SELECT, getCurDebugLoc(), 02256 TrueVal.getValueType(), Cond, 02257 SDValue(TrueVal.getNode(), TrueVal.getResNo() + i), 02258 SDValue(FalseVal.getNode(), FalseVal.getResNo() + i)); 02259 02260 setValue(&I, DAG.getNode(ISD::MERGE_VALUES, getCurDebugLoc(), 02261 DAG.getVTList(&ValueVTs[0], NumValues), 02262 &Values[0], NumValues)); 02263 } 02264 } 02265 02266 02267 void SelectionDAGLowering::visitTrunc(User &I) { 02268 // TruncInst cannot be a no-op cast because sizeof(src) > sizeof(dest). 02269 SDValue N = getValue(I.getOperand(0)); 02270 EVT DestVT = TLI.getValueType(I.getType()); 02271 setValue(&I, DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(), DestVT, N)); 02272 } 02273 02274 void SelectionDAGLowering::visitZExt(User &I) { 02275 // ZExt cannot be a no-op cast because sizeof(src) < sizeof(dest). 02276 // ZExt also can't be a cast to bool for same reason. So, nothing much to do 02277 SDValue N = getValue(I.getOperand(0)); 02278 EVT DestVT = TLI.getValueType(I.getType()); 02279 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, getCurDebugLoc(), DestVT, N)); 02280 } 02281 02282 void SelectionDAGLowering::visitSExt(User &I) { 02283 // SExt cannot be a no-op cast because sizeof(src) < sizeof(dest). 02284 // SExt also can't be a cast to bool for same reason. So, nothing much to do 02285 SDValue N = getValue(I.getOperand(0)); 02286 EVT DestVT = TLI.getValueType(I.getType()); 02287 setValue(&I, DAG.getNode(ISD::SIGN_EXTEND, getCurDebugLoc(), DestVT, N)); 02288 } 02289 02290 void SelectionDAGLowering::visitFPTrunc(User &I) { 02291 // FPTrunc is never a no-op cast, no need to check 02292 SDValue N = getValue(I.getOperand(0)); 02293 EVT DestVT = TLI.getValueType(I.getType()); 02294 setValue(&I, DAG.getNode(ISD::FP_ROUND, getCurDebugLoc(), 02295 DestVT, N, DAG.getIntPtrConstant(0))); 02296 } 02297 02298 void SelectionDAGLowering::visitFPExt(User &I){ 02299 // FPTrunc is never a no-op cast, no need to check 02300 SDValue N = getValue(I.getOperand(0)); 02301 EVT DestVT = TLI.getValueType(I.getType()); 02302 setValue(&I, DAG.getNode(ISD::FP_EXTEND, getCurDebugLoc(), DestVT, N)); 02303 } 02304 02305 void SelectionDAGLowering::visitFPToUI(User &I) { 02306 // FPToUI is never a no-op cast, no need to check 02307 SDValue N = getValue(I.getOperand(0)); 02308 EVT DestVT = TLI.getValueType(I.getType()); 02309 setValue(&I, DAG.getNode(ISD::FP_TO_UINT, getCurDebugLoc(), DestVT, N)); 02310 } 02311 02312 void SelectionDAGLowering::visitFPToSI(User &I) { 02313 // FPToSI is never a no-op cast, no need to check 02314 SDValue N = getValue(I.getOperand(0)); 02315 EVT DestVT = TLI.getValueType(I.getType()); 02316 setValue(&I, DAG.getNode(ISD::FP_TO_SINT, getCurDebugLoc(), DestVT, N)); 02317 } 02318 02319 void SelectionDAGLowering::visitUIToFP(User &I) { 02320 // UIToFP is never a no-op cast, no need to check 02321 SDValue N = getValue(I.getOperand(0)); 02322 EVT DestVT = TLI.getValueType(I.getType()); 02323 setValue(&I, DAG.getNode(ISD::UINT_TO_FP, getCurDebugLoc(), DestVT, N)); 02324 } 02325 02326 void SelectionDAGLowering::visitSIToFP(User &I){ 02327 // SIToFP is never a no-op cast, no need to check 02328 SDValue N = getValue(I.getOperand(0)); 02329 EVT DestVT = TLI.getValueType(I.getType()); 02330 setValue(&I, DAG.getNode(ISD::SINT_TO_FP, getCurDebugLoc(), DestVT, N)); 02331 } 02332 02333 void SelectionDAGLowering::visitPtrToInt(User &I) { 02334 // What to do depends on the size of the integer and the size of the pointer. 02335 // We can either truncate, zero extend, or no-op, accordingly. 02336 SDValue N = getValue(I.getOperand(0)); 02337 EVT SrcVT = N.getValueType(); 02338 EVT DestVT = TLI.getValueType(I.getType()); 02339 SDValue Result; 02340 if (DestVT.bitsLT(SrcVT)) 02341 Result = DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(), DestVT, N); 02342 else 02343 // Note: ZERO_EXTEND can handle cases where the sizes are equal too 02344 Result = DAG.getNode(ISD::ZERO_EXTEND, getCurDebugLoc(), DestVT, N); 02345 setValue(&I, Result); 02346 } 02347 02348 void SelectionDAGLowering::visitIntToPtr(User &I) { 02349 // What to do depends on the size of the integer and the size of the pointer. 02350 // We can either truncate, zero extend, or no-op, accordingly. 02351 SDValue N = getValue(I.getOperand(0)); 02352 EVT SrcVT = N.getValueType(); 02353 EVT DestVT = TLI.getValueType(I.getType()); 02354 if (DestVT.bitsLT(SrcVT)) 02355 setValue(&I, DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(), DestVT, N)); 02356 else 02357 // Note: ZERO_EXTEND can handle cases where the sizes are equal too 02358 setValue(&I, DAG.getNode(ISD::ZERO_EXTEND, getCurDebugLoc(), 02359 DestVT, N)); 02360 } 02361 02362 void SelectionDAGLowering::visitBitCast(User &I) { 02363 SDValue N = getValue(I.getOperand(0)); 02364 EVT DestVT = TLI.getValueType(I.getType()); 02365 02366 // BitCast assures us that source and destination are the same size so this 02367 // is either a BIT_CONVERT or a no-op. 02368 if (DestVT != N.getValueType()) 02369 setValue(&I, DAG.getNode(ISD::BIT_CONVERT, getCurDebugLoc(), 02370 DestVT, N)); // convert types 02371 else 02372 setValue(&I, N); // noop cast. 02373 } 02374 02375 void SelectionDAGLowering::visitInsertElement(User &I) { 02376 SDValue InVec = getValue(I.getOperand(0)); 02377 SDValue InVal = getValue(I.getOperand(1)); 02378 SDValue InIdx = DAG.getNode(ISD::ZERO_EXTEND, getCurDebugLoc(), 02379 TLI.getPointerTy(), 02380 getValue(I.getOperand(2))); 02381 02382 setValue(&I, DAG.getNode(ISD::INSERT_VECTOR_ELT, getCurDebugLoc(), 02383 TLI.getValueType(I.getType()), 02384 InVec, InVal, InIdx)); 02385 } 02386 02387 void SelectionDAGLowering::visitExtractElement(User &I) { 02388 SDValue InVec = getValue(I.getOperand(0)); 02389 SDValue InIdx = DAG.getNode(ISD::ZERO_EXTEND, getCurDebugLoc(), 02390 TLI.getPointerTy(), 02391 getValue(I.getOperand(1))); 02392 setValue(&I, DAG.getNode(ISD::EXTRACT_VECTOR_ELT, getCurDebugLoc(), 02393 TLI.getValueType(I.getType()), InVec, InIdx)); 02394 } 02395 02396 02397 // Utility for visitShuffleVector - Returns true if the mask is mask starting 02398 // from SIndx and increasing to the element length (undefs are allowed). 02399 static bool SequentialMask(SmallVectorImpl<int> &Mask, unsigned SIndx) { 02400 unsigned MaskNumElts = Mask.size(); 02401 for (unsigned i = 0; i != MaskNumElts; ++i) 02402 if ((Mask[i] >= 0) && (Mask[i] != (int)(i + SIndx))) 02403 return false; 02404 return true; 02405 } 02406 02407 void SelectionDAGLowering::visitShuffleVector(User &I) { 02408 SmallVector<int, 8> Mask; 02409 SDValue Src1 = getValue(I.getOperand(0)); 02410 SDValue Src2 = getValue(I.getOperand(1)); 02411 02412 // Convert the ConstantVector mask operand into an array of ints, with -1 02413 // representing undef values. 02414 SmallVector<Constant*, 8> MaskElts; 02415 cast<Constant>(I.getOperand(2))->getVectorElements(*DAG.getContext(), 02416 MaskElts); 02417 unsigned MaskNumElts = MaskElts.size(); 02418 for (unsigned i = 0; i != MaskNumElts; ++i) { 02419 if (isa<UndefValue>(MaskElts[i])) 02420 Mask.push_back(-1); 02421 else 02422 Mask.push_back(cast<ConstantInt>(MaskElts[i])->getSExtValue()); 02423 } 02424 02425 EVT VT = TLI.getValueType(I.getType()); 02426 EVT SrcVT = Src1.getValueType(); 02427 unsigned SrcNumElts = SrcVT.getVectorNumElements(); 02428 02429 if (SrcNumElts == MaskNumElts) { 02430 setValue(&I, DAG.getVectorShuffle(VT, getCurDebugLoc(), Src1, Src2, 02431 &Mask[0])); 02432 return; 02433 } 02434 02435 // Normalize the shuffle vector since mask and vector length don't match. 02436 if (SrcNumElts < MaskNumElts && MaskNumElts % SrcNumElts == 0) { 02437 // Mask is longer than the source vectors and is a multiple of the source 02438 // vectors. We can use concatenate vector to make the mask and vectors 02439 // lengths match. 02440 if (SrcNumElts*2 == MaskNumElts && SequentialMask(Mask, 0)) { 02441 // The shuffle is concatenating two vectors together. 02442 setValue(&I, DAG.getNode(ISD::CONCAT_VECTORS, getCurDebugLoc(), 02443 VT, Src1, Src2)); 02444 return; 02445 } 02446 02447 // Pad both vectors with undefs to make them the same length as the mask. 02448 unsigned NumConcat = MaskNumElts / SrcNumElts; 02449 bool Src1U = Src1.getOpcode() == ISD::UNDEF; 02450 bool Src2U = Src2.getOpcode() == ISD::UNDEF; 02451 SDValue UndefVal = DAG.getUNDEF(SrcVT); 02452 02453 SmallVector<SDValue, 8> MOps1(NumConcat, UndefVal); 02454 SmallVector<SDValue, 8> MOps2(NumConcat, UndefVal); 02455 MOps1[0] = Src1; 02456 MOps2[0] = Src2; 02457 02458 Src1 = Src1U ? DAG.getUNDEF(VT) : DAG.getNode(ISD::CONCAT_VECTORS, 02459 getCurDebugLoc(), VT, 02460 &MOps1[0], NumConcat); 02461 Src2 = Src2U ? DAG.getUNDEF(VT) : DAG.getNode(ISD::CONCAT_VECTORS, 02462 getCurDebugLoc(), VT, 02463 &MOps2[0], NumConcat); 02464 02465 // Readjust mask for new input vector length. 02466 SmallVector<int, 8> MappedOps; 02467 for (unsigned i = 0; i != MaskNumElts; ++i) { 02468 int Idx = Mask[i]; 02469 if (Idx < (int)SrcNumElts) 02470 MappedOps.push_back(Idx); 02471 else 02472 MappedOps.push_back(Idx + MaskNumElts - SrcNumElts); 02473 } 02474 setValue(&I, DAG.getVectorShuffle(VT, getCurDebugLoc(), Src1, Src2, 02475 &MappedOps[0])); 02476 return; 02477 } 02478 02479 if (SrcNumElts > MaskNumElts) { 02480 // Analyze the access pattern of the vector to see if we can extract 02481 // two subvectors and do the shuffle. The analysis is done by calculating 02482 // the range of elements the mask access on both vectors. 02483 int MinRange[2] = { SrcNumElts+1, SrcNumElts+1}; 02484 int MaxRange[2] = {-1, -1}; 02485 02486 for (unsigned i = 0; i != MaskNumElts; ++i) { 02487 int Idx = Mask[i]; 02488 int Input = 0; 02489 if (Idx < 0) 02490 continue; 02491 02492 if (Idx >= (int)SrcNumElts) { 02493 Input = 1; 02494 Idx -= SrcNumElts; 02495 } 02496 if (Idx > MaxRange[Input]) 02497 MaxRange[Input] = Idx; 02498 if (Idx < MinRange[Input]) 02499 MinRange[Input] = Idx; 02500 } 02501 02502 // Check if the access is smaller than the vector size and can we find 02503 // a reasonable extract index. 02504 int RangeUse[2] = { 2, 2 }; // 0 = Unused, 1 = Extract, 2 = Can not Extract. 02505 int StartIdx[2]; // StartIdx to extract from 02506 for (int Input=0; Input < 2; ++Input) { 02507 if (MinRange[Input] == (int)(SrcNumElts+1) && MaxRange[Input] == -1) { 02508 RangeUse[Input] = 0; // Unused 02509 StartIdx[Input] = 0; 02510 } else if (MaxRange[Input] - MinRange[Input] < (int)MaskNumElts) { 02511 // Fits within range but we should see if we can find a good 02512 // start index that is a multiple of the mask length. 02513 if (MaxRange[Input] < (int)MaskNumElts) { 02514 RangeUse[Input] = 1; // Extract from beginning of the vector 02515 StartIdx[Input] = 0; 02516 } else { 02517 StartIdx[Input] = (MinRange[Input]/MaskNumElts)*MaskNumElts; 02518 if (MaxRange[Input] - StartIdx[Input] < (int)MaskNumElts && 02519 StartIdx[Input] + MaskNumElts < SrcNumElts) 02520 RangeUse[Input] = 1; // Extract from a multiple of the mask length. 02521 } 02522 } 02523 } 02524 02525 if (RangeUse[0] == 0 && RangeUse[1] == 0) { 02526 setValue(&I, DAG.getUNDEF(VT)); // Vectors are not used. 02527 return; 02528 } 02529 else if (RangeUse[0] < 2 && RangeUse[1] < 2) { 02530 // Extract appropriate subvector and generate a vector shuffle 02531 for (int Input=0; Input < 2; ++Input) { 02532 SDValue& Src = Input == 0 ? Src1 : Src2; 02533 if (RangeUse[Input] == 0) { 02534 Src = DAG.getUNDEF(VT); 02535 } else { 02536 Src = DAG.getNode(ISD::EXTRACT_SUBVECTOR, getCurDebugLoc(), VT, 02537 Src, DAG.getIntPtrConstant(StartIdx[Input])); 02538 } 02539 } 02540 // Calculate new mask. 02541 SmallVector<int, 8> MappedOps; 02542 for (unsigned i = 0; i != MaskNumElts; ++i) { 02543 int Idx = Mask[i]; 02544 if (Idx < 0) 02545 MappedOps.push_back(Idx); 02546 else if (Idx < (int)SrcNumElts) 02547 MappedOps.push_back(Idx - StartIdx[0]); 02548 else 02549 MappedOps.push_back(Idx - SrcNumElts - StartIdx[1] + MaskNumElts); 02550 } 02551 setValue(&I, DAG.getVectorShuffle(VT, getCurDebugLoc(), Src1, Src2, 02552 &MappedOps[0])); 02553 return; 02554 } 02555 } 02556 02557 // We can't use either concat vectors or extract subvectors so fall back to 02558 // replacing the shuffle with extract and build vector. 02559 // to insert and build vector. 02560 EVT EltVT = VT.getVectorElementType(); 02561 EVT PtrVT = TLI.getPointerTy(); 02562 SmallVector<SDValue,8> Ops; 02563 for (unsigned i = 0; i != MaskNumElts; ++i) { 02564 if (Mask[i] < 0) { 02565 Ops.push_back(DAG.getUNDEF(EltVT)); 02566 } else { 02567 int Idx = Mask[i]; 02568 if (Idx < (int)SrcNumElts) 02569 Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, getCurDebugLoc(), 02570 EltVT, Src1, DAG.getConstant(Idx, PtrVT))); 02571 else 02572 Ops.push_back(DAG.getNode(ISD::EXTRACT_VECTOR_ELT, getCurDebugLoc(), 02573 EltVT, Src2, 02574 DAG.getConstant(Idx - SrcNumElts, PtrVT))); 02575 } 02576 } 02577 setValue(&I, DAG.getNode(ISD::BUILD_VECTOR, getCurDebugLoc(), 02578 VT, &Ops[0], Ops.size())); 02579 } 02580 02581 void SelectionDAGLowering::visitInsertValue(InsertValueInst &I) { 02582 const Value *Op0 = I.getOperand(0); 02583 const Value *Op1 = I.getOperand(1); 02584 const Type *AggTy = I.getType(); 02585 const Type *ValTy = Op1->getType(); 02586 bool IntoUndef = isa<UndefValue>(Op0); 02587 bool FromUndef = isa<UndefValue>(Op1); 02588 02589 unsigned LinearIndex = ComputeLinearIndex(TLI, AggTy, 02590 I.idx_begin(), I.idx_end()); 02591 02592 SmallVector<EVT, 4> AggValueVTs; 02593 ComputeValueVTs(TLI, AggTy, AggValueVTs); 02594 SmallVector<EVT, 4> ValValueVTs; 02595 ComputeValueVTs(TLI, ValTy, ValValueVTs); 02596 02597 unsigned NumAggValues = AggValueVTs.size(); 02598 unsigned NumValValues = ValValueVTs.size(); 02599 SmallVector<SDValue, 4> Values(NumAggValues); 02600 02601 SDValue Agg = getValue(Op0); 02602 SDValue Val = getValue(Op1); 02603 unsigned i = 0; 02604 // Copy the beginning value(s) from the original aggregate. 02605 for (; i != LinearIndex; ++i) 02606 Values[i] = IntoUndef ? DAG.getUNDEF(AggValueVTs[i]) : 02607 SDValue(Agg.getNode(), Agg.getResNo() + i); 02608 // Copy values from the inserted value(s). 02609 for (; i != LinearIndex + NumValValues; ++i) 02610 Values[i] = FromUndef ? DAG.getUNDEF(AggValueVTs[i]) : 02611 SDValue(Val.getNode(), Val.getResNo() + i - LinearIndex); 02612 // Copy remaining value(s) from the original aggregate. 02613 for (; i != NumAggValues; ++i) 02614 Values[i] = IntoUndef ? DAG.getUNDEF(AggValueVTs[i]) : 02615 SDValue(Agg.getNode(), Agg.getResNo() + i); 02616 02617 setValue(&I, DAG.getNode(ISD::MERGE_VALUES, getCurDebugLoc(), 02618 DAG.getVTList(&AggValueVTs[0], NumAggValues), 02619 &Values[0], NumAggValues)); 02620 } 02621 02622 void SelectionDAGLowering::visitExtractValue(ExtractValueInst &I) { 02623 const Value *Op0 = I.getOperand(0); 02624 const Type *AggTy = Op0->getType(); 02625 const Type *ValTy = I.getType(); 02626 bool OutOfUndef = isa<UndefValue>(Op0); 02627 02628 unsigned LinearIndex = ComputeLinearIndex(TLI, AggTy, 02629 I.idx_begin(), I.idx_end()); 02630 02631 SmallVector<EVT, 4> ValValueVTs; 02632 ComputeValueVTs(TLI, ValTy, ValValueVTs); 02633 02634 unsigned NumValValues = ValValueVTs.size(); 02635 SmallVector<SDValue, 4> Values(NumValValues); 02636 02637 SDValue Agg = getValue(Op0); 02638 // Copy out the selected value(s). 02639 for (unsigned i = LinearIndex; i != LinearIndex + NumValValues; ++i) 02640 Values[i - LinearIndex] = 02641 OutOfUndef ? 02642 DAG.getUNDEF(Agg.getNode()->getValueType(Agg.getResNo() + i)) : 02643 SDValue(Agg.getNode(), Agg.getResNo() + i); 02644 02645 setValue(&I, DAG.getNode(ISD::MERGE_VALUES, getCurDebugLoc(), 02646 DAG.getVTList(&ValValueVTs[0], NumValValues), 02647 &Values[0], NumValValues)); 02648 } 02649 02650 02651 void SelectionDAGLowering::visitGetElementPtr(User &I) { 02652 SDValue N = getValue(I.getOperand(0)); 02653 const Type *Ty = I.getOperand(0)->getType(); 02654 02655 for (GetElementPtrInst::op_iterator OI = I.op_begin()+1, E = I.op_end(); 02656 OI != E; ++OI) { 02657 Value *Idx = *OI; 02658 if (const StructType *StTy = dyn_cast<StructType>(Ty)) { 02659 unsigned Field = cast<ConstantInt>(Idx)->getZExtValue(); 02660 if (Field) { 02661 // N = N + Offset 02662 uint64_t Offset = TD->getStructLayout(StTy)->getElementOffset(Field); 02663 N = DAG.getNode(ISD::ADD, getCurDebugLoc(), N.getValueType(), N, 02664 DAG.getIntPtrConstant(Offset)); 02665 } 02666 Ty = StTy->getElementType(Field); 02667 } else { 02668 Ty = cast<SequentialType>(Ty)->getElementType(); 02669 02670 // If this is a constant subscript, handle it quickly. 02671 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) { 02672 if (CI->getZExtValue() == 0) continue; 02673 uint64_t Offs = 02674 TD->getTypeAllocSize(Ty)*cast<ConstantInt>(CI)->getSExtValue(); 02675 SDValue OffsVal; 02676 EVT PTy = TLI.getPointerTy(); 02677 unsigned PtrBits = PTy.getSizeInBits(); 02678 if (PtrBits < 64) { 02679 OffsVal = DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(), 02680 TLI.getPointerTy(), 02681 DAG.getConstant(Offs, MVT::i64)); 02682 } else 02683 OffsVal = DAG.getIntPtrConstant(Offs); 02684 N = DAG.getNode(ISD::ADD, getCurDebugLoc(), N.getValueType(), N, 02685 OffsVal); 02686 continue; 02687 } 02688 02689 // N = N + Idx * ElementSize; 02690 uint64_t ElementSize = TD->getTypeAllocSize(Ty); 02691 SDValue IdxN = getValue(Idx); 02692 02693 // If the index is smaller or larger than intptr_t, truncate or extend 02694 // it. 02695 if (IdxN.getValueType().bitsLT(N.getValueType())) 02696 IdxN = DAG.getNode(ISD::SIGN_EXTEND, getCurDebugLoc(), 02697 N.getValueType(), IdxN); 02698 else if (IdxN.getValueType().bitsGT(N.getValueType())) 02699 IdxN = DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(), 02700 N.getValueType(), IdxN); 02701 02702 // If this is a multiply by a power of two, turn it into a shl 02703 // immediately. This is a very common case. 02704 if (ElementSize != 1) { 02705 if (isPowerOf2_64(ElementSize)) { 02706 unsigned Amt = Log2_64(ElementSize); 02707 IdxN = DAG.getNode(ISD::SHL, getCurDebugLoc(), 02708 N.getValueType(), IdxN, 02709 DAG.getConstant(Amt, TLI.getPointerTy())); 02710 } else { 02711 SDValue Scale = DAG.getIntPtrConstant(ElementSize); 02712 IdxN = DAG.getNode(ISD::MUL, getCurDebugLoc(), 02713 N.getValueType(), IdxN, Scale); 02714 } 02715 } 02716 02717 N = DAG.getNode(ISD::ADD, getCurDebugLoc(), 02718 N.getValueType(), N, IdxN); 02719 } 02720 } 02721 setValue(&I, N); 02722 } 02723 02724 void SelectionDAGLowering::visitAlloca(AllocaInst &I) { 02725 // If this is a fixed sized alloca in the entry block of the function, 02726 // allocate it statically on the stack. 02727 if (FuncInfo.StaticAllocaMap.count(&I)) 02728 return; // getValue will auto-populate this. 02729 02730 const Type *Ty = I.getAllocatedType(); 02731 uint64_t TySize = TLI.getTargetData()->getTypeAllocSize(Ty); 02732 unsigned Align = 02733 std::max((unsigned)TLI.getTargetData()->getPrefTypeAlignment(Ty), 02734 I.getAlignment()); 02735 02736 SDValue AllocSize = getValue(I.getArraySize()); 02737 02738 AllocSize = DAG.getNode(ISD::MUL, getCurDebugLoc(), AllocSize.getValueType(), 02739 AllocSize, 02740 DAG.getConstant(TySize, AllocSize.getValueType())); 02741 02742 02743 02744 EVT IntPtr = TLI.getPointerTy(); 02745 if (IntPtr.bitsLT(AllocSize.getValueType())) 02746 AllocSize = DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(), 02747 IntPtr, AllocSize); 02748 else if (IntPtr.bitsGT(AllocSize.getValueType())) 02749 AllocSize = DAG.getNode(ISD::ZERO_EXTEND, getCurDebugLoc(), 02750 IntPtr, AllocSize); 02751 02752 // Handle alignment. If the requested alignment is less than or equal to 02753 // the stack alignment, ignore it. If the size is greater than or equal to 02754 // the stack alignment, we note this in the DYNAMIC_STACKALLOC node. 02755 unsigned StackAlign = 02756 TLI.getTargetMachine().getFrameInfo()->getStackAlignment(); 02757 if (Align <= StackAlign) 02758 Align = 0; 02759 02760 // Round the size of the allocation up to the stack alignment size 02761 // by add SA-1 to the size. 02762 AllocSize = DAG.getNode(ISD::ADD, getCurDebugLoc(), 02763 AllocSize.getValueType(), AllocSize, 02764 DAG.getIntPtrConstant(StackAlign-1)); 02765 // Mask out the low bits for alignment purposes. 02766 AllocSize = DAG.getNode(ISD::AND, getCurDebugLoc(), 02767 AllocSize.getValueType(), AllocSize, 02768 DAG.getIntPtrConstant(~(uint64_t)(StackAlign-1))); 02769 02770 SDValue Ops[] = { getRoot(), AllocSize, DAG.getIntPtrConstant(Align) }; 02771 SDVTList VTs = DAG.getVTList(AllocSize.getValueType(), MVT::Other); 02772 SDValue DSA = DAG.getNode(ISD::DYNAMIC_STACKALLOC, getCurDebugLoc(), 02773 VTs, Ops, 3); 02774 setValue(&I, DSA); 02775 DAG.setRoot(DSA.getValue(1)); 02776 02777 // Inform the Frame Information that we have just allocated a variable-sized 02778 // object. 02779 FuncInfo.MF->getFrameInfo()->CreateVariableSizedObject(); 02780 } 02781 02782 void SelectionDAGLowering::visitLoad(LoadInst &I) { 02783 const Value *SV = I.getOperand(0); 02784 SDValue Ptr = getValue(SV); 02785 02786 const Type *Ty = I.getType(); 02787 bool isVolatile = I.isVolatile(); 02788 unsigned Alignment = I.getAlignment(); 02789 02790 SmallVector<EVT, 4> ValueVTs; 02791 SmallVector<uint64_t, 4> Offsets; 02792 ComputeValueVTs(TLI, Ty, ValueVTs, &Offsets); 02793 unsigned NumValues = ValueVTs.size(); 02794 if (NumValues == 0) 02795 return; 02796 02797 SDValue Root; 02798 bool ConstantMemory = false; 02799 if (I.isVolatile()) 02800 // Serialize volatile loads with other side effects. 02801 Root = getRoot(); 02802 else if (AA->pointsToConstantMemory(SV)) { 02803 // Do not serialize (non-volatile) loads of constant memory with anything. 02804 Root = DAG.getEntryNode(); 02805 ConstantMemory = true; 02806 } else { 02807 // Do not serialize non-volatile loads against each other. 02808 Root = DAG.getRoot(); 02809 } 02810 02811 SmallVector<SDValue, 4> Values(NumValues); 02812 SmallVector<SDValue, 4> Chains(NumValues); 02813 EVT PtrVT = Ptr.getValueType(); 02814 for (unsigned i = 0; i != NumValues; ++i) { 02815 SDValue L = DAG.getLoad(ValueVTs[i], getCurDebugLoc(), Root, 02816 DAG.getNode(ISD::ADD, getCurDebugLoc(), 02817 PtrVT, Ptr, 02818 DAG.getConstant(Offsets[i], PtrVT)), 02819 SV, Offsets[i], 02820 isVolatile, Alignment); 02821 Values[i] = L; 02822 Chains[i] = L.getValue(1); 02823 } 02824 02825 if (!ConstantMemory) { 02826 SDValue Chain = DAG.getNode(ISD::TokenFactor, getCurDebugLoc(), 02827 MVT::Other, 02828 &Chains[0], NumValues); 02829 if (isVolatile) 02830 DAG.setRoot(Chain); 02831 else 02832 PendingLoads.push_back(Chain); 02833 } 02834 02835 setValue(&I, DAG.getNode(ISD::MERGE_VALUES, getCurDebugLoc(), 02836 DAG.getVTList(&ValueVTs[0], NumValues), 02837 &Values[0], NumValues)); 02838 } 02839 02840 02841 void SelectionDAGLowering::visitStore(StoreInst &I) { 02842 Value *SrcV = I.getOperand(0); 02843 Value *PtrV = I.getOperand(1); 02844 02845 SmallVector<EVT, 4> ValueVTs; 02846 SmallVector<uint64_t, 4> Offsets; 02847 ComputeValueVTs(TLI, SrcV->getType(), ValueVTs, &Offsets); 02848 unsigned NumValues = ValueVTs.size(); 02849 if (NumValues == 0) 02850 return; 02851 02852 // Get the lowered operands. Note that we do this after 02853 // checking if NumResults is zero, because with zero results 02854 // the operands won't have values in the map. 02855 SDValue Src = getValue(SrcV); 02856 SDValue Ptr = getValue(PtrV); 02857 02858 SDValue Root = getRoot(); 02859 SmallVector<SDValue, 4> Chains(NumValues); 02860 EVT PtrVT = Ptr.getValueType(); 02861 bool isVolatile = I.isVolatile(); 02862 unsigned Alignment = I.getAlignment(); 02863 for (unsigned i = 0; i != NumValues; ++i) 02864 Chains[i] = DAG.getStore(Root, getCurDebugLoc(), 02865 SDValue(Src.getNode(), Src.getResNo() + i), 02866 DAG.getNode(ISD::ADD, getCurDebugLoc(), 02867 PtrVT, Ptr, 02868 DAG.getConstant(Offsets[i], PtrVT)), 02869 PtrV, Offsets[i], 02870 isVolatile, Alignment); 02871 02872 DAG.setRoot(DAG.getNode(ISD::TokenFactor, getCurDebugLoc(), 02873 MVT::Other, &Chains[0], NumValues)); 02874 } 02875 02876 /// visitTargetIntrinsic - Lower a call of a target intrinsic to an INTRINSIC 02877 /// node. 02878 void SelectionDAGLowering::visitTargetIntrinsic(CallInst &I, 02879 unsigned Intrinsic) { 02880 bool HasChain = !I.doesNotAccessMemory(); 02881 bool OnlyLoad = HasChain && I.onlyReadsMemory(); 02882 02883 // Build the operand list. 02884 SmallVector<SDValue, 8> Ops; 02885 if (HasChain) { // If this intrinsic has side-effects, chainify it. 02886 if (OnlyLoad) { 02887 // We don't need to serialize loads against other loads. 02888 Ops.push_back(DAG.getRoot()); 02889 } else { 02890 Ops.push_back(getRoot()); 02891 } 02892 } 02893 02894 // Info is set by getTgtMemInstrinsic 02895 TargetLowering::IntrinsicInfo Info; 02896 bool IsTgtIntrinsic = TLI.getTgtMemIntrinsic(Info, I, Intrinsic); 02897 02898 // Add the intrinsic ID as an integer operand if it's not a target intrinsic. 02899 if (!IsTgtIntrinsic) 02900 Ops.push_back(DAG.getConstant(Intrinsic, TLI.getPointerTy())); 02901 02902 // Add all operands of the call to the operand list. 02903 for (unsigned i = 1, e = I.getNumOperands(); i != e; ++i) { 02904 SDValue Op = getValue(I.getOperand(i)); 02905 assert(TLI.isTypeLegal(Op.getValueType()) && 02906 "Intrinsic uses a non-legal type?"); 02907 Ops.push_back(Op); 02908 } 02909 02910 SmallVector<EVT, 4> ValueVTs; 02911 ComputeValueVTs(TLI, I.getType(), ValueVTs); 02912 #ifndef NDEBUG 02913 for (unsigned Val = 0, E = ValueVTs.size(); Val != E; ++Val) { 02914 assert(TLI.isTypeLegal(ValueVTs[Val]) && 02915 "Intrinsic uses a non-legal type?"); 02916 } 02917 #endif // NDEBUG 02918 if (HasChain) 02919 ValueVTs.push_back(MVT::Other); 02920 02921 SDVTList VTs = DAG.getVTList(ValueVTs.data(), ValueVTs.size()); 02922 02923 // Create the node. 02924 SDValue Result; 02925 if (IsTgtIntrinsic) { 02926 // This is target intrinsic that touches memory 02927 Result = DAG.getMemIntrinsicNode(Info.opc, getCurDebugLoc(), 02928 VTs, &Ops[0], Ops.size(), 02929 Info.memVT, Info.ptrVal, Info.offset, 02930 Info.align, Info.vol, 02931 Info.readMem, Info.writeMem); 02932 } 02933 else if (!HasChain) 02934 Result = DAG.getNode(ISD::INTRINSIC_WO_CHAIN, getCurDebugLoc(), 02935 VTs, &Ops[0], Ops.size()); 02936 else if (I.getType() != Type::getVoidTy(*DAG.getContext())) 02937 Result = DAG.getNode(ISD::INTRINSIC_W_CHAIN, getCurDebugLoc(), 02938 VTs, &Ops[0], Ops.size()); 02939 else 02940 Result = DAG.getNode(ISD::INTRINSIC_VOID, getCurDebugLoc(), 02941 VTs, &Ops[0], Ops.size()); 02942 02943 if (HasChain) { 02944 SDValue Chain = Result.getValue(Result.getNode()->getNumValues()-1); 02945 if (OnlyLoad) 02946 PendingLoads.push_back(Chain); 02947 else 02948 DAG.setRoot(Chain); 02949 } 02950 if (I.getType() != Type::getVoidTy(*DAG.getContext())) { 02951 if (const VectorType *PTy = dyn_cast<VectorType>(I.getType())) { 02952 EVT VT = TLI.getValueType(PTy); 02953 Result = DAG.getNode(ISD::BIT_CONVERT, getCurDebugLoc(), VT, Result); 02954 } 02955 setValue(&I, Result); 02956 } 02957 } 02958 02959 /// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V. 02960 static GlobalVariable *ExtractTypeInfo(Value *V) { 02961 V = V->stripPointerCasts(); 02962 GlobalVariable *GV = dyn_cast<GlobalVariable>(V); 02963 assert ((GV || isa<ConstantPointerNull>(V)) && 02964 "TypeInfo must be a global variable or NULL"); 02965 return GV; 02966 } 02967 02968 namespace llvm { 02969 02970 /// AddCatchInfo - Extract the personality and type infos from an eh.selector 02971 /// call, and add them to the specified machine basic block. 02972 void AddCatchInfo(CallInst &I, MachineModuleInfo *MMI, 02973 MachineBasicBlock *MBB) { 02974 // Inform the MachineModuleInfo of the personality for this landing pad. 02975 ConstantExpr *CE = cast<ConstantExpr>(I.getOperand(2)); 02976 assert(CE->getOpcode() == Instruction::BitCast && 02977 isa<Function>(CE->getOperand(0)) && 02978 "Personality should be a function"); 02979 MMI->addPersonality(MBB, cast<Function>(CE->getOperand(0))); 02980 02981 // Gather all the type infos for this landing pad and pass them along to 02982 // MachineModuleInfo. 02983 std::vector<GlobalVariable *> TyInfo; 02984 unsigned N = I.getNumOperands(); 02985 02986 for (unsigned i = N - 1; i > 2; --i) { 02987 if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand(i))) { 02988 unsigned FilterLength = CI->getZExtValue(); 02989 unsigned FirstCatch = i + FilterLength + !FilterLength; 02990 assert (FirstCatch <= N && "Invalid filter length"); 02991 02992 if (FirstCatch < N) { 02993 TyInfo.reserve(N - FirstCatch); 02994 for (unsigned j = FirstCatch; j < N; ++j) 02995 TyInfo.push_back(ExtractTypeInfo(I.getOperand(j))); 02996 MMI->addCatchTypeInfo(MBB, TyInfo); 02997 TyInfo.clear(); 02998 } 02999 03000 if (!FilterLength) { 03001 // Cleanup. 03002 MMI->addCleanup(MBB); 03003 } else { 03004 // Filter. 03005 TyInfo.reserve(FilterLength - 1); 03006 for (unsigned j = i + 1; j < FirstCatch; ++j) 03007 TyInfo.push_back(ExtractTypeInfo(I.getOperand(j))); 03008 MMI->addFilterTypeInfo(MBB, TyInfo); 03009 TyInfo.clear(); 03010 } 03011 03012 N = i; 03013 } 03014 } 03015 03016 if (N > 3) { 03017 TyInfo.reserve(N - 3); 03018 for (unsigned j = 3; j < N; ++j) 03019 TyInfo.push_back(ExtractTypeInfo(I.getOperand(j))); 03020 MMI->addCatchTypeInfo(MBB, TyInfo); 03021 } 03022 } 03023 03024 } 03025 03026 /// GetSignificand - Get the significand and build it into a floating-point 03027 /// number with exponent of 1: 03028 /// 03029 /// Op = (Op & 0x007fffff) | 0x3f800000; 03030 /// 03031 /// where Op is the hexidecimal representation of floating point value. 03032 static SDValue 03033 GetSignificand(SelectionDAG &DAG, SDValue Op, DebugLoc dl) { 03034 SDValue t1 = DAG.getNode(ISD::AND, dl, MVT::i32, Op, 03035 DAG.getConstant(0x007fffff, MVT::i32)); 03036 SDValue t2 = DAG.getNode(ISD::OR, dl, MVT::i32, t1, 03037 DAG.getConstant(0x3f800000, MVT::i32)); 03038 return DAG.getNode(ISD::BIT_CONVERT, dl, MVT::f32, t2); 03039 } 03040 03041 /// GetExponent - Get the exponent: 03042 /// 03043 /// (float)(int)(((Op & 0x7f800000) >> 23) - 127); 03044 /// 03045 /// where Op is the hexidecimal representation of floating point value. 03046 static SDValue 03047 GetExponent(SelectionDAG &DAG, SDValue Op, const TargetLowering &TLI, 03048 DebugLoc dl) { 03049 SDValue t0 = DAG.getNode(ISD::AND, dl, MVT::i32, Op, 03050 DAG.getConstant(0x7f800000, MVT::i32)); 03051 SDValue t1 = DAG.getNode(ISD::SRL, dl, MVT::i32, t0, 03052 DAG.getConstant(23, TLI.getPointerTy())); 03053 SDValue t2 = DAG.getNode(ISD::SUB, dl, MVT::i32, t1, 03054 DAG.getConstant(127, MVT::i32)); 03055 return DAG.getNode(ISD::SINT_TO_FP, dl, MVT::f32, t2); 03056 } 03057 03058 /// getF32Constant - Get 32-bit floating point constant. 03059 static SDValue 03060 getF32Constant(SelectionDAG &DAG, unsigned Flt) { 03061 return DAG.getConstantFP(APFloat(APInt(32, Flt)), MVT::f32); 03062 } 03063 03064 /// Inlined utility function to implement binary input atomic intrinsics for 03065 /// visitIntrinsicCall: I is a call instruction 03066 /// Op is the associated NodeType for I 03067 const char * 03068 SelectionDAGLowering::implVisitBinaryAtomic(CallInst& I, ISD::NodeType Op) { 03069 SDValue Root = getRoot(); 03070 SDValue L = 03071 DAG.getAtomic(Op, getCurDebugLoc(), 03072 getValue(I.getOperand(2)).getValueType().getSimpleVT(), 03073 Root, 03074 getValue(I.getOperand(1)), 03075 getValue(I.getOperand(2)), 03076 I.getOperand(1)); 03077 setValue(&I, L); 03078 DAG.setRoot(L.getValue(1)); 03079 return 0; 03080 } 03081 03082 // implVisitAluOverflow - Lower arithmetic overflow instrinsics. 03083 const char * 03084 SelectionDAGLowering::implVisitAluOverflow(CallInst &I, ISD::NodeType Op) { 03085 SDValue Op1 = getValue(I.getOperand(1)); 03086 SDValue Op2 = getValue(I.getOperand(2)); 03087 03088 SDVTList VTs = DAG.getVTList(Op1.getValueType(), MVT::i1); 03089 SDValue Result = DAG.getNode(Op, getCurDebugLoc(), VTs, Op1, Op2); 03090 03091 setValue(&I, Result); 03092 return 0; 03093 } 03094 03095 /// visitExp - Lower an exp intrinsic. Handles the special sequences for 03096 /// limited-precision mode. 03097 void 03098 SelectionDAGLowering::visitExp(CallInst &I) { 03099 SDValue result; 03100 DebugLoc dl = getCurDebugLoc(); 03101 03102 if (getValue(I.getOperand(1)).getValueType() == MVT::f32 && 03103 LimitFloatPrecision > 0 && LimitFloatPrecision <= 18) { 03104 SDValue Op = getValue(I.getOperand(1)); 03105 03106 // Put the exponent in the right bit position for later addition to the 03107 // final result: 03108 // 03109 // #define LOG2OFe 1.4426950f 03110 // IntegerPartOfX = ((int32_t)(X * LOG2OFe)); 03111 SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, Op, 03112 getF32Constant(DAG, 0x3fb8aa3b)); 03113 SDValue IntegerPartOfX = DAG.getNode(ISD::FP_TO_SINT, dl, MVT::i32, t0); 03114 03115 // FractionalPartOfX = (X * LOG2OFe) - (float)IntegerPartOfX; 03116 SDValue t1 = DAG.getNode(ISD::SINT_TO_FP, dl, MVT::f32, IntegerPartOfX); 03117 SDValue X = DAG.getNode(ISD::FSUB, dl, MVT::f32, t0, t1); 03118 03119 // IntegerPartOfX <<= 23; 03120 IntegerPartOfX = DAG.getNode(ISD::SHL, dl, MVT::i32, IntegerPartOfX, 03121 DAG.getConstant(23, TLI.getPointerTy())); 03122 03123 if (LimitFloatPrecision <= 6) { 03124 // For floating-point precision of 6: 03125 // 03126 // TwoToFractionalPartOfX = 03127 // 0.997535578f + 03128 // (0.735607626f + 0.252464424f * x) * x; 03129 // 03130 // error 0.0144103317, which is 6 bits 03131 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03132 getF32Constant(DAG, 0x3e814304)); 03133 SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2, 03134 getF32Constant(DAG, 0x3f3c50c8)); 03135 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03136 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03137 getF32Constant(DAG, 0x3f7f5e7e)); 03138 SDValue TwoToFracPartOfX = DAG.getNode(ISD::BIT_CONVERT, dl,MVT::i32, t5); 03139 03140 // Add the exponent into the result in integer domain. 03141 SDValue t6 = DAG.getNode(ISD::ADD, dl, MVT::i32, 03142 TwoToFracPartOfX, IntegerPartOfX); 03143 03144 result = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::f32, t6); 03145 } else if (LimitFloatPrecision > 6 && LimitFloatPrecision <= 12) { 03146 // For floating-point precision of 12: 03147 // 03148 // TwoToFractionalPartOfX = 03149 // 0.999892986f + 03150 // (0.696457318f + 03151 // (0.224338339f + 0.792043434e-1f * x) * x) * x; 03152 // 03153 // 0.000107046256 error, which is 13 to 14 bits 03154 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03155 getF32Constant(DAG, 0x3da235e3)); 03156 SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2, 03157 getF32Constant(DAG, 0x3e65b8f3)); 03158 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03159 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03160 getF32Constant(DAG, 0x3f324b07)); 03161 SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X); 03162 SDValue t7 = DAG.getNode(ISD::FADD, dl, MVT::f32, t6, 03163 getF32Constant(DAG, 0x3f7ff8fd)); 03164 SDValue TwoToFracPartOfX = DAG.getNode(ISD::BIT_CONVERT, dl,MVT::i32, t7); 03165 03166 // Add the exponent into the result in integer domain. 03167 SDValue t8 = DAG.getNode(ISD::ADD, dl, MVT::i32, 03168 TwoToFracPartOfX, IntegerPartOfX); 03169 03170 result = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::f32, t8); 03171 } else { // LimitFloatPrecision > 12 && LimitFloatPrecision <= 18 03172 // For floating-point precision of 18: 03173 // 03174 // TwoToFractionalPartOfX = 03175 // 0.999999982f + 03176 // (0.693148872f + 03177 // (0.240227044f + 03178 // (0.554906021e-1f + 03179 // (0.961591928e-2f + 03180 // (0.136028312e-2f + 0.157059148e-3f *x)*x)*x)*x)*x)*x; 03181 // 03182 // error 2.47208000*10^(-7), which is better than 18 bits 03183 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03184 getF32Constant(DAG, 0x3924b03e)); 03185 SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2, 03186 getF32Constant(DAG, 0x3ab24b87)); 03187 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03188 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03189 getF32Constant(DAG, 0x3c1d8c17)); 03190 SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X); 03191 SDValue t7 = DAG.getNode(ISD::FADD, dl, MVT::f32, t6, 03192 getF32Constant(DAG, 0x3d634a1d)); 03193 SDValue t8 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t7, X); 03194 SDValue t9 = DAG.getNode(ISD::FADD, dl, MVT::f32, t8, 03195 getF32Constant(DAG, 0x3e75fe14)); 03196 SDValue t10 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t9, X); 03197 SDValue t11 = DAG.getNode(ISD::FADD, dl, MVT::f32, t10, 03198 getF32Constant(DAG, 0x3f317234)); 03199 SDValue t12 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t11, X); 03200 SDValue t13 = DAG.getNode(ISD::FADD, dl, MVT::f32, t12, 03201 getF32Constant(DAG, 0x3f800000)); 03202 SDValue TwoToFracPartOfX = DAG.getNode(ISD::BIT_CONVERT, dl, 03203 MVT::i32, t13); 03204 03205 // Add the exponent into the result in integer domain. 03206 SDValue t14 = DAG.getNode(ISD::ADD, dl, MVT::i32, 03207 TwoToFracPartOfX, IntegerPartOfX); 03208 03209 result = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::f32, t14); 03210 } 03211 } else { 03212 // No special expansion. 03213 result = DAG.getNode(ISD::FEXP, dl, 03214 getValue(I.getOperand(1)).getValueType(), 03215 getValue(I.getOperand(1))); 03216 } 03217 03218 setValue(&I, result); 03219 } 03220 03221 /// visitLog - Lower a log intrinsic. Handles the special sequences for 03222 /// limited-precision mode. 03223 void 03224 SelectionDAGLowering::visitLog(CallInst &I) { 03225 SDValue result; 03226 DebugLoc dl = getCurDebugLoc(); 03227 03228 if (getValue(I.getOperand(1)).getValueType() == MVT::f32 && 03229 LimitFloatPrecision > 0 && LimitFloatPrecision <= 18) { 03230 SDValue Op = getValue(I.getOperand(1)); 03231 SDValue Op1 = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::i32, Op); 03232 03233 // Scale the exponent by log(2) [0.69314718f]. 03234 SDValue Exp = GetExponent(DAG, Op1, TLI, dl); 03235 SDValue LogOfExponent = DAG.getNode(ISD::FMUL, dl, MVT::f32, Exp, 03236 getF32Constant(DAG, 0x3f317218)); 03237 03238 // Get the significand and build it into a floating-point number with 03239 // exponent of 1. 03240 SDValue X = GetSignificand(DAG, Op1, dl); 03241 03242 if (LimitFloatPrecision <= 6) { 03243 // For floating-point precision of 6: 03244 // 03245 // LogofMantissa = 03246 // -1.1609546f + 03247 // (1.4034025f - 0.23903021f * x) * x; 03248 // 03249 // error 0.0034276066, which is better than 8 bits 03250 SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03251 getF32Constant(DAG, 0xbe74c456)); 03252 SDValue t1 = DAG.getNode(ISD::FADD, dl, MVT::f32, t0, 03253 getF32Constant(DAG, 0x3fb3a2b1)); 03254 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X); 03255 SDValue LogOfMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t2, 03256 getF32Constant(DAG, 0x3f949a29)); 03257 03258 result = DAG.getNode(ISD::FADD, dl, 03259 MVT::f32, LogOfExponent, LogOfMantissa); 03260 } else if (LimitFloatPrecision > 6 && LimitFloatPrecision <= 12) { 03261 // For floating-point precision of 12: 03262 // 03263 // LogOfMantissa = 03264 // -1.7417939f + 03265 // (2.8212026f + 03266 // (-1.4699568f + 03267 // (0.44717955f - 0.56570851e-1f * x) * x) * x) * x; 03268 // 03269 // error 0.000061011436, which is 14 bits 03270 SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03271 getF32Constant(DAG, 0xbd67b6d6)); 03272 SDValue t1 = DAG.getNode(ISD::FADD, dl, MVT::f32, t0, 03273 getF32Constant(DAG, 0x3ee4f4b8)); 03274 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X); 03275 SDValue t3 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t2, 03276 getF32Constant(DAG, 0x3fbc278b)); 03277 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03278 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03279 getF32Constant(DAG, 0x40348e95)); 03280 SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X); 03281 SDValue LogOfMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t6, 03282 getF32Constant(DAG, 0x3fdef31a)); 03283 03284 result = DAG.getNode(ISD::FADD, dl, 03285 MVT::f32, LogOfExponent, LogOfMantissa); 03286 } else { // LimitFloatPrecision > 12 && LimitFloatPrecision <= 18 03287 // For floating-point precision of 18: 03288 // 03289 // LogOfMantissa = 03290 // -2.1072184f + 03291 // (4.2372794f + 03292 // (-3.7029485f + 03293 // (2.2781945f + 03294 // (-0.87823314f + 03295 // (0.19073739f - 0.17809712e-1f * x) * x) * x) * x) * x)*x; 03296 // 03297 // error 0.0000023660568, which is better than 18 bits 03298 SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03299 getF32Constant(DAG, 0xbc91e5ac)); 03300 SDValue t1 = DAG.getNode(ISD::FADD, dl, MVT::f32, t0, 03301 getF32Constant(DAG, 0x3e4350aa)); 03302 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X); 03303 SDValue t3 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t2, 03304 getF32Constant(DAG, 0x3f60d3e3)); 03305 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03306 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03307 getF32Constant(DAG, 0x4011cdf0)); 03308 SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X); 03309 SDValue t7 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t6, 03310 getF32Constant(DAG, 0x406cfd1c)); 03311 SDValue t8 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t7, X); 03312 SDValue t9 = DAG.getNode(ISD::FADD, dl, MVT::f32, t8, 03313 getF32Constant(DAG, 0x408797cb)); 03314 SDValue t10 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t9, X); 03315 SDValue LogOfMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t10, 03316 getF32Constant(DAG, 0x4006dcab)); 03317 03318 result = DAG.getNode(ISD::FADD, dl, 03319 MVT::f32, LogOfExponent, LogOfMantissa); 03320 } 03321 } else { 03322 // No special expansion. 03323 result = DAG.getNode(ISD::FLOG, dl, 03324 getValue(I.getOperand(1)).getValueType(), 03325 getValue(I.getOperand(1))); 03326 } 03327 03328 setValue(&I, result); 03329 } 03330 03331 /// visitLog2 - Lower a log2 intrinsic. Handles the special sequences for 03332 /// limited-precision mode. 03333 void 03334 SelectionDAGLowering::visitLog2(CallInst &I) { 03335 SDValue result; 03336 DebugLoc dl = getCurDebugLoc(); 03337 03338 if (getValue(I.getOperand(1)).getValueType() == MVT::f32 && 03339 LimitFloatPrecision > 0 && LimitFloatPrecision <= 18) { 03340 SDValue Op = getValue(I.getOperand(1)); 03341 SDValue Op1 = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::i32, Op); 03342 03343 // Get the exponent. 03344 SDValue LogOfExponent = GetExponent(DAG, Op1, TLI, dl); 03345 03346 // Get the significand and build it into a floating-point number with 03347 // exponent of 1. 03348 SDValue X = GetSignificand(DAG, Op1, dl); 03349 03350 // Different possible minimax approximations of significand in 03351 // floating-point for various degrees of accuracy over [1,2]. 03352 if (LimitFloatPrecision <= 6) { 03353 // For floating-point precision of 6: 03354 // 03355 // Log2ofMantissa = -1.6749035f + (2.0246817f - .34484768f * x) * x; 03356 // 03357 // error 0.0049451742, which is more than 7 bits 03358 SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03359 getF32Constant(DAG, 0xbeb08fe0)); 03360 SDValue t1 = DAG.getNode(ISD::FADD, dl, MVT::f32, t0, 03361 getF32Constant(DAG, 0x40019463)); 03362 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X); 03363 SDValue Log2ofMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t2, 03364 getF32Constant(DAG, 0x3fd6633d)); 03365 03366 result = DAG.getNode(ISD::FADD, dl, 03367 MVT::f32, LogOfExponent, Log2ofMantissa); 03368 } else if (LimitFloatPrecision > 6 && LimitFloatPrecision <= 12) { 03369 // For floating-point precision of 12: 03370 // 03371 // Log2ofMantissa = 03372 // -2.51285454f + 03373 // (4.07009056f + 03374 // (-2.12067489f + 03375 // (.645142248f - 0.816157886e-1f * x) * x) * x) * x; 03376 // 03377 // error 0.0000876136000, which is better than 13 bits 03378 SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03379 getF32Constant(DAG, 0xbda7262e)); 03380 SDValue t1 = DAG.getNode(ISD::FADD, dl, MVT::f32, t0, 03381 getF32Constant(DAG, 0x3f25280b)); 03382 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X); 03383 SDValue t3 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t2, 03384 getF32Constant(DAG, 0x4007b923)); 03385 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03386 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03387 getF32Constant(DAG, 0x40823e2f)); 03388 SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X); 03389 SDValue Log2ofMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t6, 03390 getF32Constant(DAG, 0x4020d29c)); 03391 03392 result = DAG.getNode(ISD::FADD, dl, 03393 MVT::f32, LogOfExponent, Log2ofMantissa); 03394 } else { // LimitFloatPrecision > 12 && LimitFloatPrecision <= 18 03395 // For floating-point precision of 18: 03396 // 03397 // Log2ofMantissa = 03398 // -3.0400495f + 03399 // (6.1129976f + 03400 // (-5.3420409f + 03401 // (3.2865683f + 03402 // (-1.2669343f + 03403 // (0.27515199f - 03404 // 0.25691327e-1f * x) * x) * x) * x) * x) * x; 03405 // 03406 // error 0.0000018516, which is better than 18 bits 03407 SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03408 getF32Constant(DAG, 0xbcd2769e)); 03409 SDValue t1 = DAG.getNode(ISD::FADD, dl, MVT::f32, t0, 03410 getF32Constant(DAG, 0x3e8ce0b9)); 03411 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X); 03412 SDValue t3 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t2, 03413 getF32Constant(DAG, 0x3fa22ae7)); 03414 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03415 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03416 getF32Constant(DAG, 0x40525723)); 03417 SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X); 03418 SDValue t7 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t6, 03419 getF32Constant(DAG, 0x40aaf200)); 03420 SDValue t8 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t7, X); 03421 SDValue t9 = DAG.getNode(ISD::FADD, dl, MVT::f32, t8, 03422 getF32Constant(DAG, 0x40c39dad)); 03423 SDValue t10 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t9, X); 03424 SDValue Log2ofMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t10, 03425 getF32Constant(DAG, 0x4042902c)); 03426 03427 result = DAG.getNode(ISD::FADD, dl, 03428 MVT::f32, LogOfExponent, Log2ofMantissa); 03429 } 03430 } else { 03431 // No special expansion. 03432 result = DAG.getNode(ISD::FLOG2, dl, 03433 getValue(I.getOperand(1)).getValueType(), 03434 getValue(I.getOperand(1))); 03435 } 03436 03437 setValue(&I, result); 03438 } 03439 03440 /// visitLog10 - Lower a log10 intrinsic. Handles the special sequences for 03441 /// limited-precision mode. 03442 void 03443 SelectionDAGLowering::visitLog10(CallInst &I) { 03444 SDValue result; 03445 DebugLoc dl = getCurDebugLoc(); 03446 03447 if (getValue(I.getOperand(1)).getValueType() == MVT::f32 && 03448 LimitFloatPrecision > 0 && LimitFloatPrecision <= 18) { 03449 SDValue Op = getValue(I.getOperand(1)); 03450 SDValue Op1 = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::i32, Op); 03451 03452 // Scale the exponent by log10(2) [0.30102999f]. 03453 SDValue Exp = GetExponent(DAG, Op1, TLI, dl); 03454 SDValue LogOfExponent = DAG.getNode(ISD::FMUL, dl, MVT::f32, Exp, 03455 getF32Constant(DAG, 0x3e9a209a)); 03456 03457 // Get the significand and build it into a floating-point number with 03458 // exponent of 1. 03459 SDValue X = GetSignificand(DAG, Op1, dl); 03460 03461 if (LimitFloatPrecision <= 6) { 03462 // For floating-point precision of 6: 03463 // 03464 // Log10ofMantissa = 03465 // -0.50419619f + 03466 // (0.60948995f - 0.10380950f * x) * x; 03467 // 03468 // error 0.0014886165, which is 6 bits 03469 SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03470 getF32Constant(DAG, 0xbdd49a13)); 03471 SDValue t1 = DAG.getNode(ISD::FADD, dl, MVT::f32, t0, 03472 getF32Constant(DAG, 0x3f1c0789)); 03473 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X); 03474 SDValue Log10ofMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t2, 03475 getF32Constant(DAG, 0x3f011300)); 03476 03477 result = DAG.getNode(ISD::FADD, dl, 03478 MVT::f32, LogOfExponent, Log10ofMantissa); 03479 } else if (LimitFloatPrecision > 6 && LimitFloatPrecision <= 12) { 03480 // For floating-point precision of 12: 03481 // 03482 // Log10ofMantissa = 03483 // -0.64831180f + 03484 // (0.91751397f + 03485 // (-0.31664806f + 0.47637168e-1f * x) * x) * x; 03486 // 03487 // error 0.00019228036, which is better than 12 bits 03488 SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03489 getF32Constant(DAG, 0x3d431f31)); 03490 SDValue t1 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t0, 03491 getF32Constant(DAG, 0x3ea21fb2)); 03492 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X); 03493 SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2, 03494 getF32Constant(DAG, 0x3f6ae232)); 03495 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03496 SDValue Log10ofMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t4, 03497 getF32Constant(DAG, 0x3f25f7c3)); 03498 03499 result = DAG.getNode(ISD::FADD, dl, 03500 MVT::f32, LogOfExponent, Log10ofMantissa); 03501 } else { // LimitFloatPrecision > 12 && LimitFloatPrecision <= 18 03502 // For floating-point precision of 18: 03503 // 03504 // Log10ofMantissa = 03505 // -0.84299375f + 03506 // (1.5327582f + 03507 // (-1.0688956f + 03508 // (0.49102474f + 03509 // (-0.12539807f + 0.13508273e-1f * x) * x) * x) * x) * x; 03510 // 03511 // error 0.0000037995730, which is better than 18 bits 03512 SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03513 getF32Constant(DAG, 0x3c5d51ce)); 03514 SDValue t1 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t0, 03515 getF32Constant(DAG, 0x3e00685a)); 03516 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t1, X); 03517 SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2, 03518 getF32Constant(DAG, 0x3efb6798)); 03519 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03520 SDValue t5 = DAG.getNode(ISD::FSUB, dl, MVT::f32, t4, 03521 getF32Constant(DAG, 0x3f88d192)); 03522 SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X); 03523 SDValue t7 = DAG.getNode(ISD::FADD, dl, MVT::f32, t6, 03524 getF32Constant(DAG, 0x3fc4316c)); 03525 SDValue t8 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t7, X); 03526 SDValue Log10ofMantissa = DAG.getNode(ISD::FSUB, dl, MVT::f32, t8, 03527 getF32Constant(DAG, 0x3f57ce70)); 03528 03529 result = DAG.getNode(ISD::FADD, dl, 03530 MVT::f32, LogOfExponent, Log10ofMantissa); 03531 } 03532 } else { 03533 // No special expansion. 03534 result = DAG.getNode(ISD::FLOG10, dl, 03535 getValue(I.getOperand(1)).getValueType(), 03536 getValue(I.getOperand(1))); 03537 } 03538 03539 setValue(&I, result); 03540 } 03541 03542 /// visitExp2 - Lower an exp2 intrinsic. Handles the special sequences for 03543 /// limited-precision mode. 03544 void 03545 SelectionDAGLowering::visitExp2(CallInst &I) { 03546 SDValue result; 03547 DebugLoc dl = getCurDebugLoc(); 03548 03549 if (getValue(I.getOperand(1)).getValueType() == MVT::f32 && 03550 LimitFloatPrecision > 0 && LimitFloatPrecision <= 18) { 03551 SDValue Op = getValue(I.getOperand(1)); 03552 03553 SDValue IntegerPartOfX = DAG.getNode(ISD::FP_TO_SINT, dl, MVT::i32, Op); 03554 03555 // FractionalPartOfX = x - (float)IntegerPartOfX; 03556 SDValue t1 = DAG.getNode(ISD::SINT_TO_FP, dl, MVT::f32, IntegerPartOfX); 03557 SDValue X = DAG.getNode(ISD::FSUB, dl, MVT::f32, Op, t1); 03558 03559 // IntegerPartOfX <<= 23; 03560 IntegerPartOfX = DAG.getNode(ISD::SHL, dl, MVT::i32, IntegerPartOfX, 03561 DAG.getConstant(23, TLI.getPointerTy())); 03562 03563 if (LimitFloatPrecision <= 6) { 03564 // For floating-point precision of 6: 03565 // 03566 // TwoToFractionalPartOfX = 03567 // 0.997535578f + 03568 // (0.735607626f + 0.252464424f * x) * x; 03569 // 03570 // error 0.0144103317, which is 6 bits 03571 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03572 getF32Constant(DAG, 0x3e814304)); 03573 SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2, 03574 getF32Constant(DAG, 0x3f3c50c8)); 03575 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03576 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03577 getF32Constant(DAG, 0x3f7f5e7e)); 03578 SDValue t6 = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::i32, t5); 03579 SDValue TwoToFractionalPartOfX = 03580 DAG.getNode(ISD::ADD, dl, MVT::i32, t6, IntegerPartOfX); 03581 03582 result = DAG.getNode(ISD::BIT_CONVERT, dl, 03583 MVT::f32, TwoToFractionalPartOfX); 03584 } else if (LimitFloatPrecision > 6 && LimitFloatPrecision <= 12) { 03585 // For floating-point precision of 12: 03586 // 03587 // TwoToFractionalPartOfX = 03588 // 0.999892986f + 03589 // (0.696457318f + 03590 // (0.224338339f + 0.792043434e-1f * x) * x) * x; 03591 // 03592 // error 0.000107046256, which is 13 to 14 bits 03593 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03594 getF32Constant(DAG, 0x3da235e3)); 03595 SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2, 03596 getF32Constant(DAG, 0x3e65b8f3)); 03597 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03598 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03599 getF32Constant(DAG, 0x3f324b07)); 03600 SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X); 03601 SDValue t7 = DAG.getNode(ISD::FADD, dl, MVT::f32, t6, 03602 getF32Constant(DAG, 0x3f7ff8fd)); 03603 SDValue t8 = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::i32, t7); 03604 SDValue TwoToFractionalPartOfX = 03605 DAG.getNode(ISD::ADD, dl, MVT::i32, t8, IntegerPartOfX); 03606 03607 result = DAG.getNode(ISD::BIT_CONVERT, dl, 03608 MVT::f32, TwoToFractionalPartOfX); 03609 } else { // LimitFloatPrecision > 12 && LimitFloatPrecision <= 18 03610 // For floating-point precision of 18: 03611 // 03612 // TwoToFractionalPartOfX = 03613 // 0.999999982f + 03614 // (0.693148872f + 03615 // (0.240227044f + 03616 // (0.554906021e-1f + 03617 // (0.961591928e-2f + 03618 // (0.136028312e-2f + 0.157059148e-3f *x)*x)*x)*x)*x)*x; 03619 // error 2.47208000*10^(-7), which is better than 18 bits 03620 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03621 getF32Constant(DAG, 0x3924b03e)); 03622 SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2, 03623 getF32Constant(DAG, 0x3ab24b87)); 03624 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03625 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03626 getF32Constant(DAG, 0x3c1d8c17)); 03627 SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X); 03628 SDValue t7 = DAG.getNode(ISD::FADD, dl, MVT::f32, t6, 03629 getF32Constant(DAG, 0x3d634a1d)); 03630 SDValue t8 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t7, X); 03631 SDValue t9 = DAG.getNode(ISD::FADD, dl, MVT::f32, t8, 03632 getF32Constant(DAG, 0x3e75fe14)); 03633 SDValue t10 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t9, X); 03634 SDValue t11 = DAG.getNode(ISD::FADD, dl, MVT::f32, t10, 03635 getF32Constant(DAG, 0x3f317234)); 03636 SDValue t12 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t11, X); 03637 SDValue t13 = DAG.getNode(ISD::FADD, dl, MVT::f32, t12, 03638 getF32Constant(DAG, 0x3f800000)); 03639 SDValue t14 = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::i32, t13); 03640 SDValue TwoToFractionalPartOfX = 03641 DAG.getNode(ISD::ADD, dl, MVT::i32, t14, IntegerPartOfX); 03642 03643 result = DAG.getNode(ISD::BIT_CONVERT, dl, 03644 MVT::f32, TwoToFractionalPartOfX); 03645 } 03646 } else { 03647 // No special expansion. 03648 result = DAG.getNode(ISD::FEXP2, dl, 03649 getValue(I.getOperand(1)).getValueType(), 03650 getValue(I.getOperand(1))); 03651 } 03652 03653 setValue(&I, result); 03654 } 03655 03656 /// visitPow - Lower a pow intrinsic. Handles the special sequences for 03657 /// limited-precision mode with x == 10.0f. 03658 void 03659 SelectionDAGLowering::visitPow(CallInst &I) { 03660 SDValue result; 03661 Value *Val = I.getOperand(1); 03662 DebugLoc dl = getCurDebugLoc(); 03663 bool IsExp10 = false; 03664 03665 if (getValue(Val).getValueType() == MVT::f32 && 03666 getValue(I.getOperand(2)).getValueType() == MVT::f32 && 03667 LimitFloatPrecision > 0 && LimitFloatPrecision <= 18) { 03668 if (Constant *C = const_cast<Constant*>(dyn_cast<Constant>(Val))) { 03669 if (ConstantFP *CFP = dyn_cast<ConstantFP>(C)) { 03670 APFloat Ten(10.0f); 03671 IsExp10 = CFP->getValueAPF().bitwiseIsEqual(Ten); 03672 } 03673 } 03674 } 03675 03676 if (IsExp10 && LimitFloatPrecision > 0 && LimitFloatPrecision <= 18) { 03677 SDValue Op = getValue(I.getOperand(2)); 03678 03679 // Put the exponent in the right bit position for later addition to the 03680 // final result: 03681 // 03682 // #define LOG2OF10 3.3219281f 03683 // IntegerPartOfX = (int32_t)(x * LOG2OF10); 03684 SDValue t0 = DAG.getNode(ISD::FMUL, dl, MVT::f32, Op, 03685 getF32Constant(DAG, 0x40549a78)); 03686 SDValue IntegerPartOfX = DAG.getNode(ISD::FP_TO_SINT, dl, MVT::i32, t0); 03687 03688 // FractionalPartOfX = x - (float)IntegerPartOfX; 03689 SDValue t1 = DAG.getNode(ISD::SINT_TO_FP, dl, MVT::f32, IntegerPartOfX); 03690 SDValue X = DAG.getNode(ISD::FSUB, dl, MVT::f32, t0, t1); 03691 03692 // IntegerPartOfX <<= 23; 03693 IntegerPartOfX = DAG.getNode(ISD::SHL, dl, MVT::i32, IntegerPartOfX, 03694 DAG.getConstant(23, TLI.getPointerTy())); 03695 03696 if (LimitFloatPrecision <= 6) { 03697 // For floating-point precision of 6: 03698 // 03699 // twoToFractionalPartOfX = 03700 // 0.997535578f + 03701 // (0.735607626f + 0.252464424f * x) * x; 03702 // 03703 // error 0.0144103317, which is 6 bits 03704 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03705 getF32Constant(DAG, 0x3e814304)); 03706 SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2, 03707 getF32Constant(DAG, 0x3f3c50c8)); 03708 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03709 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03710 getF32Constant(DAG, 0x3f7f5e7e)); 03711 SDValue t6 = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::i32, t5); 03712 SDValue TwoToFractionalPartOfX = 03713 DAG.getNode(ISD::ADD, dl, MVT::i32, t6, IntegerPartOfX); 03714 03715 result = DAG.getNode(ISD::BIT_CONVERT, dl, 03716 MVT::f32, TwoToFractionalPartOfX); 03717 } else if (LimitFloatPrecision > 6 && LimitFloatPrecision <= 12) { 03718 // For floating-point precision of 12: 03719 // 03720 // TwoToFractionalPartOfX = 03721 // 0.999892986f + 03722 // (0.696457318f + 03723 // (0.224338339f + 0.792043434e-1f * x) * x) * x; 03724 // 03725 // error 0.000107046256, which is 13 to 14 bits 03726 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03727 getF32Constant(DAG, 0x3da235e3)); 03728 SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2, 03729 getF32Constant(DAG, 0x3e65b8f3)); 03730 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03731 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03732 getF32Constant(DAG, 0x3f324b07)); 03733 SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X); 03734 SDValue t7 = DAG.getNode(ISD::FADD, dl, MVT::f32, t6, 03735 getF32Constant(DAG, 0x3f7ff8fd)); 03736 SDValue t8 = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::i32, t7); 03737 SDValue TwoToFractionalPartOfX = 03738 DAG.getNode(ISD::ADD, dl, MVT::i32, t8, IntegerPartOfX); 03739 03740 result = DAG.getNode(ISD::BIT_CONVERT, dl, 03741 MVT::f32, TwoToFractionalPartOfX); 03742 } else { // LimitFloatPrecision > 12 && LimitFloatPrecision <= 18 03743 // For floating-point precision of 18: 03744 // 03745 // TwoToFractionalPartOfX = 03746 // 0.999999982f + 03747 // (0.693148872f + 03748 // (0.240227044f + 03749 // (0.554906021e-1f + 03750 // (0.961591928e-2f + 03751 // (0.136028312e-2f + 0.157059148e-3f *x)*x)*x)*x)*x)*x; 03752 // error 2.47208000*10^(-7), which is better than 18 bits 03753 SDValue t2 = DAG.getNode(ISD::FMUL, dl, MVT::f32, X, 03754 getF32Constant(DAG, 0x3924b03e)); 03755 SDValue t3 = DAG.getNode(ISD::FADD, dl, MVT::f32, t2, 03756 getF32Constant(DAG, 0x3ab24b87)); 03757 SDValue t4 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t3, X); 03758 SDValue t5 = DAG.getNode(ISD::FADD, dl, MVT::f32, t4, 03759 getF32Constant(DAG, 0x3c1d8c17)); 03760 SDValue t6 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t5, X); 03761 SDValue t7 = DAG.getNode(ISD::FADD, dl, MVT::f32, t6, 03762 getF32Constant(DAG, 0x3d634a1d)); 03763 SDValue t8 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t7, X); 03764 SDValue t9 = DAG.getNode(ISD::FADD, dl, MVT::f32, t8, 03765 getF32Constant(DAG, 0x3e75fe14)); 03766 SDValue t10 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t9, X); 03767 SDValue t11 = DAG.getNode(ISD::FADD, dl, MVT::f32, t10, 03768 getF32Constant(DAG, 0x3f317234)); 03769 SDValue t12 = DAG.getNode(ISD::FMUL, dl, MVT::f32, t11, X); 03770 SDValue t13 = DAG.getNode(ISD::FADD, dl, MVT::f32, t12, 03771 getF32Constant(DAG, 0x3f800000)); 03772 SDValue t14 = DAG.getNode(ISD::BIT_CONVERT, dl, MVT::i32, t13); 03773 SDValue TwoToFractionalPartOfX = 03774 DAG.getNode(ISD::ADD, dl, MVT::i32, t14, IntegerPartOfX); 03775 03776 result = DAG.getNode(ISD::BIT_CONVERT, dl, 03777 MVT::f32, TwoToFractionalPartOfX); 03778 } 03779 } else { 03780 // No special expansion. 03781 result = DAG.getNode(ISD::FPOW, dl, 03782 getValue(I.getOperand(1)).getValueType(), 03783 getValue(I.getOperand(1)), 03784 getValue(I.getOperand(2))); 03785 } 03786 03787 setValue(&I, result); 03788 } 03789 03790 /// visitIntrinsicCall - Lower the call to the specified intrinsic function. If 03791 /// we want to emit this as a call to a named external function, return the name 03792 /// otherwise lower it and return null. 03793 const char * 03794 SelectionDAGLowering::visitIntrinsicCall(CallInst &I, unsigned Intrinsic) { 03795 DebugLoc dl = getCurDebugLoc(); 03796 switch (Intrinsic) { 03797 default: 03798 // By default, turn this into a target intrinsic node. 03799 visitTargetIntrinsic(I, Intrinsic); 03800 return 0; 03801 case Intrinsic::vastart: visitVAStart(I); return 0; 03802 case Intrinsic::vaend: visitVAEnd(I); return 0; 03803 case Intrinsic::vacopy: visitVACopy(I); return 0; 03804 case Intrinsic::returnaddress: 03805 setValue(&I, DAG.getNode(ISD::RETURNADDR, dl, TLI.getPointerTy(), 03806 getValue(I.getOperand(1)))); 03807 return 0; 03808 case Intrinsic::frameaddress: 03809 setValue(&I, DAG.getNode(ISD::FRAMEADDR, dl, TLI.getPointerTy(), 03810 getValue(I.getOperand(1)))); 03811 return 0; 03812 case Intrinsic::setjmp: 03813 return "_setjmp"+!TLI.usesUnderscoreSetJmp(); 03814 break; 03815 case Intrinsic::longjmp: 03816 return "_longjmp"+!TLI.usesUnderscoreLongJmp(); 03817 break; 03818 case Intrinsic::memcpy: { 03819 SDValue Op1 = getValue(I.getOperand(1)); 03820 SDValue Op2 = getValue(I.getOperand(2)); 03821 SDValue Op3 = getValue(I.getOperand(3)); 03822 unsigned Align = cast<ConstantInt>(I.getOperand(4))->getZExtValue(); 03823 DAG.setRoot(DAG.getMemcpy(getRoot(), dl, Op1, Op2, Op3, Align, false, 03824 I.getOperand(1), 0, I.getOperand(2), 0)); 03825 return 0; 03826 } 03827 case Intrinsic::memset: { 03828 SDValue Op1 = getValue(I.getOperand(1)); 03829 SDValue Op2 = getValue(I.getOperand(2)); 03830 SDValue Op3 = getValue(I.getOperand(3)); 03831 unsigned Align = cast<ConstantInt>(I.getOperand(4))->getZExtValue(); 03832 DAG.setRoot(DAG.getMemset(getRoot(), dl, Op1, Op2, Op3, Align, 03833 I.getOperand(1), 0)); 03834 return 0; 03835 } 03836 case Intrinsic::memmove: { 03837 SDValue Op1 = getValue(I.getOperand(1)); 03838 SDValue Op2 = getValue(I.getOperand(2)); 03839 SDValue Op3 = getValue(I.getOperand(3)); 03840 unsigned Align = cast<ConstantInt>(I.getOperand(4))->getZExtValue(); 03841 03842 // If the source and destination are known to not be aliases, we can 03843 // lower memmove as memcpy. 03844 uint64_t Size = -1ULL; 03845 if (ConstantSDNode *C = dyn_cast<ConstantSDNode>(Op3)) 03846 Size = C->getZExtValue(); 03847 if (AA->alias(I.getOperand(1), Size, I.getOperand(2), Size) == 03848 AliasAnalysis::NoAlias) { 03849 DAG.setRoot(DAG.getMemcpy(getRoot(), dl, Op1, Op2, Op3, Align, false, 03850 I.getOperand(1), 0, I.getOperand(2), 0)); 03851 return 0; 03852 } 03853 03854 DAG.setRoot(DAG.getMemmove(getRoot(), dl, Op1, Op2, Op3, Align, 03855 I.getOperand(1), 0, I.getOperand(2), 0)); 03856 return 0; 03857 } 03858 case Intrinsic::dbg_stoppoint: { 03859 DbgStopPointInst &SPI = cast<DbgStopPointInst>(I); 03860 if (isValidDebugInfoIntrinsic(SPI, CodeGenOpt::Default)) { 03861 MachineFunction &MF = DAG.getMachineFunction(); 03862 DebugLoc Loc = ExtractDebugLocation(SPI, MF.getDebugLocInfo()); 03863 setCurDebugLoc(Loc); 03864 03865 if (OptLevel == CodeGenOpt::None) 03866 DAG.setRoot(DAG.getDbgStopPoint(Loc, getRoot(), 03867 SPI.getLine(), 03868 SPI.getColumn(), 03869 SPI.getContext())); 03870 } 03871 return 0; 03872 } 03873 case Intrinsic::dbg_region_start: { 03874 DwarfWriter *DW = DAG.getDwarfWriter(); 03875 DbgRegionStartInst &RSI = cast<DbgRegionStartInst>(I); 03876 if (isValidDebugInfoIntrinsic(RSI, OptLevel) && DW 03877 && DW->ShouldEmitDwarfDebug()) { 03878 unsigned LabelID = 03879 DW->RecordRegionStart(cast<GlobalVariable>(RSI.getContext())); 03880 DAG.setRoot(DAG.getLabel(ISD::DBG_LABEL, getCurDebugLoc(), 03881 getRoot(), LabelID)); 03882 } 03883 return 0; 03884 } 03885 case Intrinsic::dbg_region_end: { 03886 DwarfWriter *DW = DAG.getDwarfWriter(); 03887 DbgRegionEndInst &REI = cast<DbgRegionEndInst>(I); 03888 03889 if (!isValidDebugInfoIntrinsic(REI, OptLevel) || !DW 03890 || !DW->ShouldEmitDwarfDebug()) 03891 return 0; 03892 03893 MachineFunction &MF = DAG.getMachineFunction(); 03894 DISubprogram Subprogram(cast<GlobalVariable>(REI.getContext())); 03895 03896 if (isInlinedFnEnd(REI, MF.getFunction())) { 03897 // This is end of inlined function. Debugging information for inlined 03898 // function is not handled yet (only supported by FastISel). 03899 if (OptLevel == CodeGenOpt::None) { 03900 unsigned ID = DW->RecordInlinedFnEnd(Subprogram); 03901 if (ID != 0) 03902 // Returned ID is 0 if this is unbalanced "end of inlined 03903 // scope". This could happen if optimizer eats dbg intrinsics or 03904 // "beginning of inlined scope" is not recoginized due to missing 03905 // location info. In such cases, do ignore this region.end. 03906 DAG.setRoot(DAG.getLabel(ISD::DBG_LABEL, getCurDebugLoc(), 03907 getRoot(), ID)); 03908 } 03909 return 0; 03910 } 03911 03912 unsigned LabelID = 03913 DW->RecordRegionEnd(cast<GlobalVariable>(REI.getContext())); 03914 DAG.setRoot(DAG.getLabel(ISD::DBG_LABEL, getCurDebugLoc(), 03915 getRoot(), LabelID)); 03916 return 0; 03917 } 03918 case Intrinsic::dbg_func_start: { 03919 DwarfWriter *DW = DAG.getDwarfWriter(); 03920 DbgFuncStartInst &FSI = cast<DbgFuncStartInst>(I); 03921 if (!isValidDebugInfoIntrinsic(FSI, CodeGenOpt::None)) 03922 return 0; 03923 03924 MachineFunction &MF = DAG.getMachineFunction(); 03925 // This is a beginning of an inlined function. 03926 if (isInlinedFnStart(FSI, MF.getFunction())) { 03927 if (OptLevel != CodeGenOpt::None) 03928 // FIXME: Debugging informaation for inlined function is only 03929 // supported at CodeGenOpt::Node. 03930 return 0; 03931 03932 DebugLoc PrevLoc = CurDebugLoc; 03933 // If llvm.dbg.func.start is seen in a new block before any 03934 // llvm.dbg.stoppoint intrinsic then the location info is unknown. 03935 // FIXME : Why DebugLoc is reset at the beginning of each block ? 03936 if (PrevLoc.isUnknown()) 03937 return 0; 03938 03939 // Record the source line. 03940 setCurDebugLoc(ExtractDebugLocation(FSI, MF.getDebugLocInfo())); 03941 03942 if (!DW || !DW->ShouldEmitDwarfDebug()) 03943 return 0; 03944 DebugLocTuple PrevLocTpl = MF.getDebugLocTuple(PrevLoc); 03945 DISubprogram SP(cast<GlobalVariable>(FSI.getSubprogram())); 03946 DICompileUnit CU(PrevLocTpl.CompileUnit); 03947 unsigned LabelID = DW->RecordInlinedFnStart(SP, CU, 03948 PrevLocTpl.Line, 03949 PrevLocTpl.Col); 03950 DAG.setRoot(DAG.getLabel(ISD::DBG_LABEL, getCurDebugLoc(), 03951 getRoot(), LabelID)); 03952 return 0; 03953 } 03954 03955 // This is a beginning of a new function. 03956 MF.setDefaultDebugLoc(ExtractDebugLocation(FSI, MF.getDebugLocInfo())); 03957 03958 if (!DW || !DW->ShouldEmitDwarfDebug()) 03959 return 0; 03960 // llvm.dbg.func_start also defines beginning of function scope. 03961 DW->RecordRegionStart(cast<GlobalVariable>(FSI.getSubprogram())); 03962 return 0; 03963 } 03964 case Intrinsic::dbg_declare: { 03965 if (OptLevel != CodeGenOpt::None) 03966 // FIXME: Variable debug info is not supported here. 03967 return 0; 03968 03969 DbgDeclareInst &DI = cast<DbgDeclareInst>(I); 03970 if (!isValidDebugInfoIntrinsic(DI, CodeGenOpt::None)) 03971 return 0; 03972 03973 Value *Variable = DI.getVariable(); 03974 DAG.setRoot(DAG.getNode(ISD::DECLARE, dl, MVT::Other, getRoot(), 03975 getValue(DI.getAddress()), getValue(Variable))); 03976 return 0; 03977 } 03978 case Intrinsic::eh_exception: { 03979 // Insert the EXCEPTIONADDR instruction. 03980 assert(CurMBB->isLandingPad() &&"Call to eh.exception not in landing pad!"); 03981 SDVTList VTs = DAG.getVTList(TLI.getPointerTy(), MVT::Other); 03982 SDValue Ops[1]; 03983 Ops[0] = DAG.getRoot(); 03984 SDValue Op = DAG.getNode(ISD::EXCEPTIONADDR, dl, VTs, Ops, 1); 03985 setValue(&I, Op); 03986 DAG.setRoot(Op.getValue(1)); 03987 return 0; 03988 } 03989 03990 case Intrinsic::eh_selector_i32: 03991 case Intrinsic::eh_selector_i64: { 03992 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 03993 EVT VT = (Intrinsic == Intrinsic::eh_selector_i32 ? MVT::i32 : MVT::i64); 03994 03995 if (MMI) { 03996 if (CurMBB->isLandingPad()) 03997 AddCatchInfo(I, MMI, CurMBB); 03998 else { 03999 #ifndef NDEBUG 04000 FuncInfo.CatchInfoLost.insert(&I); 04001 #endif 04002 // FIXME: Mark exception selector register as live in. Hack for PR1508. 04003 unsigned Reg = TLI.getExceptionSelectorRegister(); 04004 if (Reg) CurMBB->addLiveIn(Reg); 04005 } 04006 04007 // Insert the EHSELECTION instruction. 04008 SDVTList VTs = DAG.getVTList(VT, MVT::Other); 04009 SDValue Ops[2]; 04010 Ops[0] = getValue(I.getOperand(1)); 04011 Ops[1] = getRoot(); 04012 SDValue Op = DAG.getNode(ISD::EHSELECTION, dl, VTs, Ops, 2); 04013 setValue(&I, Op); 04014 DAG.setRoot(Op.getValue(1)); 04015 } else { 04016 setValue(&I, DAG.getConstant(0, VT)); 04017 } 04018 04019 return 0; 04020 } 04021 04022 case Intrinsic::eh_typeid_for_i32: 04023 case Intrinsic::eh_typeid_for_i64: { 04024 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 04025 EVT VT = (Intrinsic == Intrinsic::eh_typeid_for_i32 ? 04026 MVT::i32 : MVT::i64); 04027 04028 if (MMI) { 04029 // Find the type id for the given typeinfo. 04030 GlobalVariable *GV = ExtractTypeInfo(I.getOperand(1)); 04031 04032 unsigned TypeID = MMI->getTypeIDFor(GV); 04033 setValue(&I, DAG.getConstant(TypeID, VT)); 04034 } else { 04035 // Return something different to eh_selector. 04036 setValue(&I, DAG.getConstant(1, VT)); 04037 } 04038 04039 return 0; 04040 } 04041 04042 case Intrinsic::eh_return_i32: 04043 case Intrinsic::eh_return_i64: 04044 if (MachineModuleInfo *MMI = DAG.getMachineModuleInfo()) { 04045 MMI->setCallsEHReturn(true); 04046 DAG.setRoot(DAG.getNode(ISD::EH_RETURN, dl, 04047 MVT::Other, 04048 getControlRoot(), 04049 getValue(I.getOperand(1)), 04050 getValue(I.getOperand(2)))); 04051 } else { 04052 setValue(&I, DAG.getConstant(0, TLI.getPointerTy())); 04053 } 04054 04055 return 0; 04056 case Intrinsic::eh_unwind_init: 04057 if (MachineModuleInfo *MMI = DAG.getMachineModuleInfo()) { 04058 MMI->setCallsUnwindInit(true); 04059 } 04060 04061 return 0; 04062 04063 case Intrinsic::eh_dwarf_cfa: { 04064 EVT VT = getValue(I.getOperand(1)).getValueType(); 04065 SDValue CfaArg; 04066 if (VT.bitsGT(TLI.getPointerTy())) 04067 CfaArg = DAG.getNode(ISD::TRUNCATE, dl, 04068 TLI.getPointerTy(), getValue(I.getOperand(1))); 04069 else 04070 CfaArg = DAG.getNode(ISD::SIGN_EXTEND, dl, 04071 TLI.getPointerTy(), getValue(I.getOperand(1))); 04072 04073 SDValue Offset = DAG.getNode(ISD::ADD, dl, 04074 TLI.getPointerTy(), 04075 DAG.getNode(ISD::FRAME_TO_ARGS_OFFSET, dl, 04076 TLI.getPointerTy()), 04077 CfaArg); 04078 setValue(&I, DAG.getNode(ISD::ADD, dl, 04079 TLI.getPointerTy(), 04080 DAG.getNode(ISD::FRAMEADDR, dl, 04081 TLI.getPointerTy(), 04082 DAG.getConstant(0, 04083 TLI.getPointerTy())), 04084 Offset)); 04085 return 0; 04086 } 04087 case Intrinsic::convertff: 04088 case Intrinsic::convertfsi: 04089 case Intrinsic::convertfui: 04090 case Intrinsic::convertsif: 04091 case Intrinsic::convertuif: 04092 case Intrinsic::convertss: 04093 case Intrinsic::convertsu: 04094 case Intrinsic::convertus: 04095 case Intrinsic::convertuu: { 04096 ISD::CvtCode Code = ISD::CVT_INVALID; 04097 switch (Intrinsic) { 04098 case Intrinsic::convertff: Code = ISD::CVT_FF; break; 04099 case Intrinsic::convertfsi: Code = ISD::CVT_FS; break; 04100 case Intrinsic::convertfui: Code = ISD::CVT_FU; break; 04101 case Intrinsic::convertsif: Code = ISD::CVT_SF; break; 04102 case Intrinsic::convertuif: Code = ISD::CVT_UF; break; 04103 case Intrinsic::convertss: Code = ISD::CVT_SS; break; 04104 case Intrinsic::convertsu: Code = ISD::CVT_SU; break; 04105 case Intrinsic::convertus: Code = ISD::CVT_US; break; 04106 case Intrinsic::convertuu: Code = ISD::CVT_UU; break; 04107 } 04108 EVT DestVT = TLI.getValueType(I.getType()); 04109 Value* Op1 = I.getOperand(1); 04110 setValue(&I, DAG.getConvertRndSat(DestVT, getCurDebugLoc(), getValue(Op1), 04111 DAG.getValueType(DestVT), 04112 DAG.getValueType(getValue(Op1).getValueType()), 04113 getValue(I.getOperand(2)), 04114 getValue(I.getOperand(3)), 04115 Code)); 04116 return 0; 04117 } 04118 04119 case Intrinsic::sqrt: 04120 setValue(&I, DAG.getNode(ISD::FSQRT, dl, 04121 getValue(I.getOperand(1)).getValueType(), 04122 getValue(I.getOperand(1)))); 04123 return 0; 04124 case Intrinsic::powi: 04125 setValue(&I, DAG.getNode(ISD::FPOWI, dl, 04126 getValue(I.getOperand(1)).getValueType(), 04127 getValue(I.getOperand(1)), 04128 getValue(I.getOperand(2)))); 04129 return 0; 04130 case Intrinsic::sin: 04131 setValue(&I, DAG.getNode(ISD::FSIN, dl, 04132 getValue(I.getOperand(1)).getValueType(), 04133 getValue(I.getOperand(1)))); 04134 return 0; 04135 case Intrinsic::cos: 04136 setValue(&I, DAG.getNode(ISD::FCOS, dl, 04137 getValue(I.getOperand(1)).getValueType(), 04138 getValue(I.getOperand(1)))); 04139 return 0; 04140 case Intrinsic::log: 04141 visitLog(I); 04142 return 0; 04143 case Intrinsic::log2: 04144 visitLog2(I); 04145 return 0; 04146 case Intrinsic::log10: 04147 visitLog10(I); 04148 return 0; 04149 case Intrinsic::exp: 04150 visitExp(I); 04151 return 0; 04152 case Intrinsic::exp2: 04153 visitExp2(I); 04154 return 0; 04155 case Intrinsic::pow: 04156 visitPow(I); 04157 return 0; 04158 case Intrinsic::pcmarker: { 04159 SDValue Tmp = getValue(I.getOperand(1)); 04160 DAG.setRoot(DAG.getNode(ISD::PCMARKER, dl, MVT::Other, getRoot(), Tmp)); 04161 return 0; 04162 } 04163 case Intrinsic::readcyclecounter: { 04164 SDValue Op = getRoot(); 04165 SDValue Tmp = DAG.getNode(ISD::READCYCLECOUNTER, dl, 04166 DAG.getVTList(MVT::i64, MVT::Other), 04167 &Op, 1); 04168 setValue(&I, Tmp); 04169 DAG.setRoot(Tmp.getValue(1)); 04170 return 0; 04171 } 04172 case Intrinsic::bswap: 04173 setValue(&I, DAG.getNode(ISD::BSWAP, dl, 04174 getValue(I.getOperand(1)).getValueType(), 04175 getValue(I.getOperand(1)))); 04176 return 0; 04177 case Intrinsic::cttz: { 04178 SDValue Arg = getValue(I.getOperand(1)); 04179 EVT Ty = Arg.getValueType(); 04180 SDValue result = DAG.getNode(ISD::CTTZ, dl, Ty, Arg); 04181 setValue(&I, result); 04182 return 0; 04183 } 04184 case Intrinsic::ctlz: { 04185 SDValue Arg = getValue(I.getOperand(1)); 04186 EVT Ty = Arg.getValueType(); 04187 SDValue result = DAG.getNode(ISD::CTLZ, dl, Ty, Arg); 04188 setValue(&I, result); 04189 return 0; 04190 } 04191 case Intrinsic::ctpop: { 04192 SDValue Arg = getValue(I.getOperand(1)); 04193 EVT Ty = Arg.getValueType(); 04194 SDValue result = DAG.getNode(ISD::CTPOP, dl, Ty, Arg); 04195 setValue(&I, result); 04196 return 0; 04197 } 04198 case Intrinsic::stacksave: { 04199 SDValue Op = getRoot(); 04200 SDValue Tmp = DAG.getNode(ISD::STACKSAVE, dl, 04201 DAG.getVTList(TLI.getPointerTy(), MVT::Other), &Op, 1); 04202 setValue(&I, Tmp); 04203 DAG.setRoot(Tmp.getValue(1)); 04204 return 0; 04205 } 04206 case Intrinsic::stackrestore: { 04207 SDValue Tmp = getValue(I.getOperand(1)); 04208 DAG.setRoot(DAG.getNode(ISD::STACKRESTORE, dl, MVT::Other, getRoot(), Tmp)); 04209 return 0; 04210 } 04211 case Intrinsic::stackprotector: { 04212 // Emit code into the DAG to store the stack guard onto the stack. 04213 MachineFunction &MF = DAG.getMachineFunction(); 04214 MachineFrameInfo *MFI = MF.getFrameInfo(); 04215 EVT PtrTy = TLI.getPointerTy(); 04216 04217 SDValue Src = getValue(I.getOperand(1)); // The guard's value. 04218 AllocaInst *Slot = cast<AllocaInst>(I.getOperand(2)); 04219 04220 int FI = FuncInfo.StaticAllocaMap[Slot]; 04221 MFI->setStackProtectorIndex(FI); 04222 04223 SDValue FIN = DAG.getFrameIndex(FI, PtrTy); 04224 04225 // Store the stack protector onto the stack. 04226 SDValue Result = DAG.getStore(getRoot(), getCurDebugLoc(), Src, FIN, 04227 PseudoSourceValue::getFixedStack(FI), 04228 0, true); 04229 setValue(&I, Result); 04230 DAG.setRoot(Result); 04231 return 0; 04232 } 04233 case Intrinsic::var_annotation: 04234 // Discard annotate attributes 04235 return 0; 04236 04237 case Intrinsic::init_trampoline: { 04238 const Function *F = cast<Function>(I.getOperand(2)->stripPointerCasts()); 04239 04240 SDValue Ops[6]; 04241 Ops[0] = getRoot(); 04242 Ops[1] = getValue(I.getOperand(1)); 04243 Ops[2] = getValue(I.getOperand(2)); 04244 Ops[3] = getValue(I.getOperand(3)); 04245 Ops[4] = DAG.getSrcValue(I.getOperand(1)); 04246 Ops[5] = DAG.getSrcValue(F); 04247 04248 SDValue Tmp = DAG.getNode(ISD::TRAMPOLINE, dl, 04249 DAG.getVTList(TLI.getPointerTy(), MVT::Other), 04250 Ops, 6); 04251 04252 setValue(&I, Tmp); 04253 DAG.setRoot(Tmp.getValue(1)); 04254 return 0; 04255 } 04256 04257 case Intrinsic::gcroot: 04258 if (GFI) { 04259 Value *Alloca = I.getOperand(1); 04260 Constant *TypeMap = cast<Constant>(I.getOperand(2)); 04261 04262 FrameIndexSDNode *FI = cast<FrameIndexSDNode>(getValue(Alloca).getNode()); 04263 GFI->addStackRoot(FI->getIndex(), TypeMap); 04264 } 04265 return 0; 04266 04267 case Intrinsic::gcread: 04268 case Intrinsic::gcwrite: 04269 llvm_unreachable("GC failed to lower gcread/gcwrite intrinsics!"); 04270 return 0; 04271 04272 case Intrinsic::flt_rounds: { 04273 setValue(&I, DAG.getNode(ISD::FLT_ROUNDS_, dl, MVT::i32)); 04274 return 0; 04275 } 04276 04277 case Intrinsic::trap: { 04278 DAG.setRoot(DAG.getNode(ISD::TRAP, dl,MVT::Other, getRoot())); 04279 return 0; 04280 } 04281 04282 case Intrinsic::uadd_with_overflow: 04283 return implVisitAluOverflow(I, ISD::UADDO); 04284 case Intrinsic::sadd_with_overflow: 04285 return implVisitAluOverflow(I, ISD::SADDO); 04286 case Intrinsic::usub_with_overflow: 04287 return implVisitAluOverflow(I, ISD::USUBO); 04288 case Intrinsic::ssub_with_overflow: 04289 return implVisitAluOverflow(I, ISD::SSUBO); 04290 case Intrinsic::umul_with_overflow: 04291 return implVisitAluOverflow(I, ISD::UMULO); 04292 case Intrinsic::smul_with_overflow: 04293 return implVisitAluOverflow(I, ISD::SMULO); 04294 04295 case Intrinsic::prefetch: { 04296 SDValue Ops[4]; 04297 Ops[0] = getRoot(); 04298 Ops[1] = getValue(I.getOperand(1)); 04299 Ops[2] = getValue(I.getOperand(2)); 04300 Ops[3] = getValue(I.getOperand(3)); 04301 DAG.setRoot(DAG.getNode(ISD::PREFETCH, dl, MVT::Other, &Ops[0], 4)); 04302 return 0; 04303 } 04304 04305 case Intrinsic::memory_barrier: { 04306 SDValue Ops[6]; 04307 Ops[0] = getRoot(); 04308 for (int x = 1; x < 6; ++x) 04309 Ops[x] = getValue(I.getOperand(x)); 04310 04311 DAG.setRoot(DAG.getNode(ISD::MEMBARRIER, dl, MVT::Other, &Ops[0], 6)); 04312 return 0; 04313 } 04314 case Intrinsic::atomic_cmp_swap: { 04315 SDValue Root = getRoot(); 04316 SDValue L = 04317 DAG.getAtomic(ISD::ATOMIC_CMP_SWAP, getCurDebugLoc(), 04318 getValue(I.getOperand(2)).getValueType().getSimpleVT(), 04319 Root, 04320 getValue(I.getOperand(1)), 04321 getValue(I.getOperand(2)), 04322 getValue(I.getOperand(3)), 04323 I.getOperand(1)); 04324 setValue(&I, L); 04325 DAG.setRoot(L.getValue(1)); 04326 return 0; 04327 } 04328 case Intrinsic::atomic_load_add: 04329 return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_ADD); 04330 case Intrinsic::atomic_load_sub: 04331 return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_SUB); 04332 case Intrinsic::atomic_load_or: 04333 return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_OR); 04334 case Intrinsic::atomic_load_xor: 04335 return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_XOR); 04336 case Intrinsic::atomic_load_and: 04337 return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_AND); 04338 case Intrinsic::atomic_load_nand: 04339 return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_NAND); 04340 case Intrinsic::atomic_load_max: 04341 return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MAX); 04342 case Intrinsic::atomic_load_min: 04343 return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_MIN); 04344 case Intrinsic::atomic_load_umin: 04345 return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMIN); 04346 case Intrinsic::atomic_load_umax: 04347 return implVisitBinaryAtomic(I, ISD::ATOMIC_LOAD_UMAX); 04348 case Intrinsic::atomic_swap: 04349 return implVisitBinaryAtomic(I, ISD::ATOMIC_SWAP); 04350 } 04351 } 04352 04353 /// Test if the given instruction is in a position to be optimized 04354 /// with a tail-call. This roughly means that it's in a block with 04355 /// a return and there's nothing that needs to be scheduled 04356 /// between it and the return. 04357 /// 04358 /// This function only tests target-independent requirements. 04359 /// For target-dependent requirements, a target should override 04360 /// TargetLowering::IsEligibleForTailCallOptimization. 04361 /// 04362 static bool 04363 isInTailCallPosition(const Instruction *I, Attributes RetAttr, 04364 const TargetLowering &TLI) { 04365 const BasicBlock *ExitBB = I->getParent(); 04366 const TerminatorInst *Term = ExitBB->getTerminator(); 04367 const ReturnInst *Ret = dyn_cast<ReturnInst>(Term); 04368 const Function *F = ExitBB->getParent(); 04369 04370 // The block must end in a return statement or an unreachable. 04371 if (!Ret && !isa<UnreachableInst>(Term)) return false; 04372 04373 // If I will have a chain, make sure no other instruction that will have a 04374 // chain interposes between I and the return. 04375 if (I->mayHaveSideEffects() || I->mayReadFromMemory() || 04376 !I->isSafeToSpeculativelyExecute()) 04377 for (BasicBlock::const_iterator BBI = prior(prior(ExitBB->end())); ; 04378 --BBI) { 04379 if (&*BBI == I) 04380 break; 04381 if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() || 04382 !BBI->isSafeToSpeculativelyExecute()) 04383 return false; 04384 } 04385 04386 // If the block ends with a void return or unreachable, it doesn't matter 04387 // what the call's return type is. 04388 if (!Ret || Ret->getNumOperands() == 0) return true; 04389 04390 // Conservatively require the attributes of the call to match those of 04391 // the return. 04392 if (F->getAttributes().getRetAttributes() != RetAttr) 04393 return false; 04394 04395 // Otherwise, make sure the unmodified return value of I is the return value. 04396 for (const Instruction *U = dyn_cast<Instruction>(Ret->getOperand(0)); ; 04397 U = dyn_cast<Instruction>(U->getOperand(0))) { 04398 if (!U) 04399 return false; 04400 if (!U->hasOneUse()) 04401 return false; 04402 if (U == I) 04403 break; 04404 // Check for a truly no-op truncate. 04405 if (isa<TruncInst>(U) && 04406 TLI.isTruncateFree(U->getOperand(0)->getType(), U->getType())) 04407 continue; 04408 // Check for a truly no-op bitcast. 04409 if (isa<BitCastInst>(U) && 04410 (U->getOperand(0)->getType() == U->getType() || 04411 (isa<PointerType>(U->getOperand(0)->getType()) && 04412 isa<PointerType>(U->getType())))) 04413 continue; 04414 // Otherwise it's not a true no-op. 04415 return false; 04416 } 04417 04418 return true; 04419 } 04420 04421 void SelectionDAGLowering::LowerCallTo(CallSite CS, SDValue Callee, 04422 bool isTailCall, 04423 MachineBasicBlock *LandingPad) { 04424 const PointerType *PT = cast<PointerType>(CS.getCalledValue()->getType()); 04425 const FunctionType *FTy = cast<FunctionType>(PT->getElementType()); 04426 MachineModuleInfo *MMI = DAG.getMachineModuleInfo(); 04427 unsigned BeginLabel = 0, EndLabel = 0; 04428 04429 TargetLowering::ArgListTy Args; 04430 TargetLowering::ArgListEntry Entry; 04431 Args.reserve(CS.arg_size()); 04432 unsigned j = 1; 04433 for (CallSite::arg_iterator i = CS.arg_begin(), e = CS.arg_end(); 04434 i != e; ++i, ++j) { 04435 SDValue ArgNode = getValue(*i); 04436 Entry.Node = ArgNode; Entry.Ty = (*i)->getType(); 04437 04438 unsigned attrInd = i - CS.arg_begin() + 1; 04439 Entry.isSExt = CS.paramHasAttr(attrInd, Attribute::SExt); 04440 Entry.isZExt = CS.paramHasAttr(attrInd, Attribute::ZExt); 04441 Entry.isInReg = CS.paramHasAttr(attrInd, Attribute::InReg); 04442 Entry.isSRet = CS.paramHasAttr(attrInd, Attribute::StructRet); 04443 Entry.isNest = CS.paramHasAttr(attrInd, Attribute::Nest); 04444 Entry.isByVal = CS.paramHasAttr(attrInd, Attribute::ByVal); 04445 Entry.Alignment = CS.getParamAlignment(attrInd); 04446 Args.push_back(Entry); 04447 } 04448 04449 if (LandingPad && MMI) { 04450 // Insert a label before the invoke call to mark the try range. This can be 04451 // used to detect deletion of the invoke via the MachineModuleInfo. 04452 BeginLabel = MMI->NextLabelID(); 04453 04454 // Both PendingLoads and PendingExports must be flushed here; 04455 // this call might not return. 04456 (void)getRoot(); 04457 DAG.setRoot(DAG.getLabel(ISD::EH_LABEL, getCurDebugLoc(), 04458 getControlRoot(), BeginLabel)); 04459 } 04460 04461 // Check if target-independent constraints permit a tail call here. 04462 // Target-dependent constraints are checked within TLI.LowerCallTo. 04463 if (isTailCall && 04464 !isInTailCallPosition(CS.getInstruction(), 04465 CS.getAttributes().getRetAttributes(), 04466 TLI)) 04467 isTailCall = false; 04468 04469 std::pair<SDValue,SDValue> Result = 04470 TLI.LowerCallTo(getRoot(), CS.getType(), 04471 CS.paramHasAttr(0, Attribute::SExt), 04472 CS.paramHasAttr(0, Attribute::ZExt), FTy->isVarArg(), 04473 CS.paramHasAttr(0, Attribute::InReg), FTy->getNumParams(), 04474 CS.getCallingConv(), 04475 isTailCall, 04476 !CS.getInstruction()->use_empty(), 04477 Callee, Args, DAG, getCurDebugLoc()); 04478 assert((isTailCall || Result.second.getNode()) && 04479 "Non-null chain expected with non-tail call!"); 04480 assert((Result.second.getNode() || !Result.first.getNode()) && 04481 "Null value expected with tail call!"); 04482 if (Result.first.getNode()) 04483 setValue(CS.getInstruction(), Result.first); 04484 // As a special case, a null chain means that a tail call has 04485 // been emitted and the DAG root is already updated. 04486 if (Result.second.getNode()) 04487 DAG.setRoot(Result.second); 04488 else 04489 HasTailCall = true; 04490 04491 if (LandingPad && MMI) { 04492 // Insert a label at the end of the invoke call to mark the try range. This 04493 // can be used to detect deletion of the invoke via the MachineModuleInfo. 04494 EndLabel = MMI->NextLabelID(); 04495 DAG.setRoot(DAG.getLabel(ISD::EH_LABEL, getCurDebugLoc(), 04496 getRoot(), EndLabel)); 04497 04498 // Inform MachineModuleInfo of range. 04499 MMI->addInvoke(LandingPad, BeginLabel, EndLabel); 04500 } 04501 } 04502 04503 04504 void SelectionDAGLowering::visitCall(CallInst &I) { 04505 const char *RenameFn = 0; 04506 if (Function *F = I.getCalledFunction()) { 04507 if (F->isDeclaration()) { 04508 const TargetIntrinsicInfo *II = TLI.getTargetMachine().getIntrinsicInfo(); 04509 if (II) { 04510 if (unsigned IID = II->getIntrinsicID(F)) { 04511 RenameFn = visitIntrinsicCall(I, IID); 04512 if (!RenameFn) 04513 return; 04514 } 04515 } 04516 if (unsigned IID = F->getIntrinsicID()) { 04517 RenameFn = visitIntrinsicCall(I, IID); 04518 if (!RenameFn) 04519 return; 04520 } 04521 } 04522 04523 // Check for well-known libc/libm calls. If the function is internal, it 04524 // can't be a library call. 04525 if (!F->hasLocalLinkage() && F->hasName()) { 04526 StringRef Name = F->getName(); 04527 if (Name == "copysign" || Name == "copysignf") { 04528 if (I.getNumOperands() == 3 && // Basic sanity checks. 04529 I.getOperand(1)->getType()->isFloatingPoint() && 04530 I.getType() == I.getOperand(1)->getType() && 04531 I.getType() == I.getOperand(2)->getType()) { 04532 SDValue LHS = getValue(I.getOperand(1)); 04533 SDValue RHS = getValue(I.getOperand(2)); 04534 setValue(&I, DAG.getNode(ISD::FCOPYSIGN, getCurDebugLoc(), 04535 LHS.getValueType(), LHS, RHS)); 04536 return; 04537 } 04538 } else if (Name == "fabs" || Name == "fabsf" || Name == "fabsl") { 04539 if (I.getNumOperands() == 2 && // Basic sanity checks. 04540 I.getOperand(1)->getType()->isFloatingPoint() && 04541 I.getType() == I.getOperand(1)->getType()) { 04542 SDValue Tmp = getValue(I.getOperand(1)); 04543 setValue(&I, DAG.getNode(ISD::FABS, getCurDebugLoc(), 04544 Tmp.getValueType(), Tmp)); 04545 return; 04546 } 04547 } else if (Name == "sin" || Name == "sinf" || Name == "sinl") { 04548 if (I.getNumOperands() == 2 && // Basic sanity checks. 04549 I.getOperand(1)->getType()->isFloatingPoint() && 04550 I.getType() == I.getOperand(1)->getType()) { 04551 SDValue Tmp = getValue(I.getOperand(1)); 04552 setValue(&I, DAG.getNode(ISD::FSIN, getCurDebugLoc(), 04553 Tmp.getValueType(), Tmp)); 04554 return; 04555 } 04556 } else if (Name == "cos" || Name == "cosf" || Name == "cosl") { 04557 if (I.getNumOperands() == 2 && // Basic sanity checks. 04558 I.getOperand(1)->getType()->isFloatingPoint() && 04559 I.getType() == I.getOperand(1)->getType()) { 04560 SDValue Tmp = getValue(I.getOperand(1)); 04561 setValue(&I, DAG.getNode(ISD::FCOS, getCurDebugLoc(), 04562 Tmp.getValueType(), Tmp)); 04563 return; 04564 } 04565 } 04566 } 04567 } else if (isa<InlineAsm>(I.getOperand(0))) { 04568 visitInlineAsm(&I); 04569 return; 04570 } 04571 04572 SDValue Callee; 04573 if (!RenameFn) 04574 Callee = getValue(I.getOperand(0)); 04575 else 04576 Callee = DAG.getExternalSymbol(RenameFn, TLI.getPointerTy()); 04577 04578 // Check if we can potentially perform a tail call. More detailed 04579 // checking is be done within LowerCallTo, after more information 04580 // about the call is known. 04581 bool isTailCall = PerformTailCallOpt && I.isTailCall(); 04582 04583 LowerCallTo(&I, Callee, isTailCall); 04584 } 04585 04586 04587 /// getCopyFromRegs - Emit a series of CopyFromReg nodes that copies from 04588 /// this value and returns the result as a ValueVT value. This uses 04589 /// Chain/Flag as the input and updates them for the output Chain/Flag. 04590 /// If the Flag pointer is NULL, no flag is used. 04591 SDValue RegsForValue::getCopyFromRegs(SelectionDAG &DAG, DebugLoc dl, 04592 SDValue &Chain, 04593 SDValue *Flag) const { 04594 // Assemble the legal parts into the final values. 04595 SmallVector<SDValue, 4> Values(ValueVTs.size()); 04596 SmallVector<SDValue, 8> Parts; 04597 for (unsigned Value = 0, Part = 0, e = ValueVTs.size(); Value != e; ++Value) { 04598 // Copy the legal parts from the registers. 04599 EVT ValueVT = ValueVTs[Value]; 04600 unsigned NumRegs = TLI->getNumRegisters(*DAG.getContext(), ValueVT); 04601 EVT RegisterVT = RegVTs[Value]; 04602 04603 Parts.resize(NumRegs); 04604 for (unsigned i = 0; i != NumRegs; ++i) { 04605 SDValue P; 04606 if (Flag == 0) 04607 P = DAG.getCopyFromReg(Chain, dl, Regs[Part+i], RegisterVT); 04608 else { 04609 P = DAG.getCopyFromReg(Chain, dl, Regs[Part+i], RegisterVT, *Flag); 04610 *Flag = P.getValue(2); 04611 } 04612 Chain = P.getValue(1); 04613 04614 // If the source register was virtual and if we know something about it, 04615 // add an assert node. 04616 if (TargetRegisterInfo::isVirtualRegister(Regs[Part+i]) && 04617 RegisterVT.isInteger() && !RegisterVT.isVector()) { 04618 unsigned SlotNo = Regs[Part+i]-TargetRegisterInfo::FirstVirtualRegister; 04619 FunctionLoweringInfo &FLI = DAG.getFunctionLoweringInfo(); 04620 if (FLI.LiveOutRegInfo.size() > SlotNo) { 04621 FunctionLoweringInfo::LiveOutInfo &LOI = FLI.LiveOutRegInfo[SlotNo]; 04622 04623 unsigned RegSize = RegisterVT.getSizeInBits(); 04624 unsigned NumSignBits = LOI.NumSignBits; 04625 unsigned NumZeroBits = LOI.KnownZero.countLeadingOnes(); 04626 04627 // FIXME: We capture more information than the dag can represent. For 04628 // now, just use the tightest assertzext/assertsext possible. 04629 bool isSExt = true; 04630 EVT FromVT(MVT::Other); 04631 if (NumSignBits == RegSize) 04632 isSExt = true, FromVT = MVT::i1; // ASSERT SEXT 1 04633 else if (NumZeroBits >= RegSize-1) 04634 isSExt = false, FromVT = MVT::i1; // ASSERT ZEXT 1 04635 else if (NumSignBits > RegSize-8) 04636 isSExt = true, FromVT = MVT::i8; // ASSERT SEXT 8 04637 else if (NumZeroBits >= RegSize-8) 04638 isSExt = false, FromVT = MVT::i8; // ASSERT ZEXT 8 04639 else if (NumSignBits > RegSize-16) 04640 isSExt = true, FromVT = MVT::i16; // ASSERT SEXT 16 04641 else if (NumZeroBits >= RegSize-16) 04642 isSExt = false, FromVT = MVT::i16; // ASSERT ZEXT 16 04643 else if (NumSignBits > RegSize-32) 04644 isSExt = true, FromVT = MVT::i32; // ASSERT SEXT 32 04645 else if (NumZeroBits >= RegSize-32) 04646 isSExt = false, FromVT = MVT::i32; // ASSERT ZEXT 32 04647 04648 if (FromVT != MVT::Other) { 04649 P = DAG.getNode(isSExt ? ISD::AssertSext : ISD::AssertZext, dl, 04650 RegisterVT, P, DAG.getValueType(FromVT)); 04651 04652 } 04653 } 04654 } 04655 04656 Parts[i] = P; 04657 } 04658 04659 Values[Value] = getCopyFromParts(DAG, dl, Parts.begin(), 04660 NumRegs, RegisterVT, ValueVT); 04661 Part += NumRegs; 04662 Parts.clear(); 04663 } 04664 04665 return DAG.getNode(ISD::MERGE_VALUES, dl, 04666 DAG.getVTList(&ValueVTs[0], ValueVTs.size()), 04667 &Values[0], ValueVTs.size()); 04668 } 04669 04670 /// getCopyToRegs - Emit a series of CopyToReg nodes that copies the 04671 /// specified value into the registers specified by this object. This uses 04672 /// Chain/Flag as the input and updates them for the output Chain/Flag. 04673 /// If the Flag pointer is NULL, no flag is used. 04674 void RegsForValue::getCopyToRegs(SDValue Val, SelectionDAG &DAG, DebugLoc dl, 04675 SDValue &Chain, SDValue *Flag) const { 04676 // Get the list of the values's legal parts. 04677 unsigned NumRegs = Regs.size(); 04678 SmallVector<SDValue, 8> Parts(NumRegs); 04679 for (unsigned Value = 0, Part = 0, e = ValueVTs.size(); Value != e; ++Value) { 04680 EVT ValueVT = ValueVTs[Value]; 04681 unsigned NumParts = TLI->getNumRegisters(*DAG.getContext(), ValueVT); 04682 EVT RegisterVT = RegVTs[Value]; 04683 04684 getCopyToParts(DAG, dl, Val.getValue(Val.getResNo() + Value), 04685 &Parts[Part], NumParts, RegisterVT); 04686 Part += NumParts; 04687 } 04688 04689 // Copy the parts into the registers. 04690 SmallVector<SDValue, 8> Chains(NumRegs); 04691 for (unsigned i = 0; i != NumRegs; ++i) { 04692 SDValue Part; 04693 if (Flag == 0) 04694 Part = DAG.getCopyToReg(Chain, dl, Regs[i], Parts[i]); 04695 else { 04696 Part = DAG.getCopyToReg(Chain, dl, Regs[i], Parts[i], *Flag); 04697 *Flag = Part.getValue(1); 04698 } 04699 Chains[i] = Part.getValue(0); 04700 } 04701 04702 if (NumRegs == 1 || Flag) 04703 // If NumRegs > 1 && Flag is used then the use of the last CopyToReg is 04704 // flagged to it. That is the CopyToReg nodes and the user are considered 04705 // a single scheduling unit. If we create a TokenFactor and return it as 04706 // chain, then the TokenFactor is both a predecessor (operand) of the 04707 // user as well as a successor (the TF operands are flagged to the user). 04708 // c1, f1 = CopyToReg 04709 // c2, f2 = CopyToReg 04710 // c3 = TokenFactor c1, c2 04711 // ... 04712 // = op c3, ..., f2 04713 Chain = Chains[NumRegs-1]; 04714 else 04715 Chain = DAG.getNode(ISD::TokenFactor, dl, MVT::Other, &Chains[0], NumRegs); 04716 } 04717 04718 /// AddInlineAsmOperands - Add this value to the specified inlineasm node 04719 /// operand list. This adds the code marker and includes the number of 04720 /// values added into it. 04721 void RegsForValue::AddInlineAsmOperands(unsigned Code, 04722 bool HasMatching,unsigned MatchingIdx, 04723 SelectionDAG &DAG, 04724 std::vector<SDValue> &Ops) const { 04725 EVT IntPtrTy = DAG.getTargetLoweringInfo().getPointerTy(); 04726 assert(Regs.size() < (1 << 13) && "Too many inline asm outputs!"); 04727 unsigned Flag = Code | (Regs.size() << 3); 04728 if (HasMatching) 04729 Flag |= 0x80000000 | (MatchingIdx << 16); 04730 Ops.push_back(DAG.getTargetConstant(Flag, IntPtrTy)); 04731 for (unsigned Value = 0, Reg = 0, e = ValueVTs.size(); Value != e; ++Value) { 04732 unsigned NumRegs = TLI->getNumRegisters(*DAG.getContext(), ValueVTs[Value]); 04733 EVT RegisterVT = RegVTs[Value]; 04734 for (unsigned i = 0; i != NumRegs; ++i) { 04735 assert(Reg < Regs.size() && "Mismatch in # registers expected"); 04736 Ops.push_back(DAG.getRegister(Regs[Reg++], RegisterVT)); 04737 } 04738 } 04739 } 04740 04741 /// isAllocatableRegister - If the specified register is safe to allocate, 04742 /// i.e. it isn't a stack pointer or some other special register, return the 04743 /// register class for the register. Otherwise, return null. 04744 static const TargetRegisterClass * 04745 isAllocatableRegister(unsigned Reg, MachineFunction &MF, 04746 const TargetLowering &TLI, 04747 const TargetRegisterInfo *TRI) { 04748 EVT FoundVT = MVT::Other; 04749 const TargetRegisterClass *FoundRC = 0; 04750 for (TargetRegisterInfo::regclass_iterator RCI = TRI->regclass_begin(), 04751 E = TRI->regclass_end(); RCI != E; ++RCI) { 04752 EVT ThisVT = MVT::Other; 04753 04754 const TargetRegisterClass *RC = *RCI; 04755 // If none of the the value types for this register class are valid, we 04756 // can't use it. For example, 64-bit reg classes on 32-bit targets. 04757 for (TargetRegisterClass::vt_iterator I = RC->vt_begin(), E = RC->vt_end(); 04758 I != E; ++I) { 04759 if (TLI.isTypeLegal(*I)) { 04760 // If we have already found this register in a different register class, 04761 // choose the one with the largest VT specified. For example, on 04762 // PowerPC, we favor f64 register classes over f32. 04763 if (FoundVT == MVT::Other || FoundVT.bitsLT(*I)) { 04764 ThisVT = *I; 04765 break; 04766 } 04767 } 04768 } 04769 04770 if (ThisVT == MVT::Other) continue; 04771 04772 // NOTE: This isn't ideal. In particular, this might allocate the 04773 // frame pointer in functions that need it (due to them not being taken 04774 // out of allocation, because a variable sized allocation hasn't been seen 04775 // yet). This is a slight code pessimization, but should still work. 04776 for (TargetRegisterClass::iterator I = RC->allocation_order_begin(MF), 04777 E = RC->allocation_order_end(MF); I != E; ++I) 04778 if (*I == Reg) { 04779 // We found a matching register class. Keep looking at others in case 04780 // we find one with larger registers that this physreg is also in. 04781 FoundRC = RC; 04782 FoundVT = ThisVT; 04783 break; 04784 } 04785 } 04786 return FoundRC; 04787 } 04788 04789 04790 namespace llvm { 04791 /// AsmOperandInfo - This contains information for each constraint that we are 04792 /// lowering. 04793 class VISIBILITY_HIDDEN SDISelAsmOperandInfo : 04794 public TargetLowering::AsmOperandInfo { 04795 public: 04796 /// CallOperand - If this is the result output operand or a clobber 04797 /// this is null, otherwise it is the incoming operand to the CallInst. 04798 /// This gets modified as the asm is processed. 04799 SDValue CallOperand; 04800 04801 /// AssignedRegs - If this is a register or register class operand, this 04802 /// contains the set of register corresponding to the operand. 04803 RegsForValue AssignedRegs; 04804 04805 explicit SDISelAsmOperandInfo(const InlineAsm::ConstraintInfo &info) 04806 : TargetLowering::AsmOperandInfo(info), CallOperand(0,0) { 04807 } 04808 04809 /// MarkAllocatedRegs - Once AssignedRegs is set, mark the assigned registers 04810 /// busy in OutputRegs/InputRegs. 04811 void MarkAllocatedRegs(bool isOutReg, bool isInReg, 04812 std::set<unsigned> &OutputRegs, 04813 std::set<unsigned> &InputRegs, 04814 const TargetRegisterInfo &TRI) const { 04815 if (isOutReg) { 04816 for (unsigned i = 0, e = AssignedRegs.Regs.size(); i != e; ++i) 04817 MarkRegAndAliases(AssignedRegs.Regs[i], OutputRegs, TRI); 04818 } 04819 if (isInReg) { 04820 for (unsigned i = 0, e = AssignedRegs.Regs.size(); i != e; ++i) 04821 MarkRegAndAliases(AssignedRegs.Regs[i], InputRegs, TRI); 04822 } 04823 } 04824 04825 /// getCallOperandValEVT - Return the EVT of the Value* that this operand 04826 /// corresponds to. If there is no Value* for this operand, it returns 04827 /// MVT::Other. 04828 EVT getCallOperandValEVT(LLVMContext &Context, 04829 const TargetLowering &TLI, 04830 const TargetData *TD) const { 04831 if (CallOperandVal == 0) return MVT::Other; 04832 04833 if (isa<BasicBlock>(CallOperandVal)) 04834 return TLI.getPointerTy(); 04835 04836 const llvm::Type *OpTy = CallOperandVal->getType(); 04837 04838 // If this is an indirect operand, the operand is a pointer to the 04839 // accessed type. 04840 if (isIndirect) 04841 OpTy = cast<PointerType>(OpTy)->getElementType(); 04842 04843 // If OpTy is not a single value, it may be a struct/union that we 04844 // can tile with integers. 04845 if (!OpTy->isSingleValueType() && OpTy->isSized()) { 04846 unsigned BitSize = TD->getTypeSizeInBits(OpTy); 04847 switch (BitSize) { 04848 default: break; 04849 case 1: 04850 case 8: 04851 case 16: 04852 case 32: 04853 case 64: 04854 case 128: 04855 OpTy = IntegerType::get(Context, BitSize); 04856 break; 04857 } 04858 } 04859 04860 return TLI.getValueType(OpTy, true); 04861 } 04862 04863 private: 04864 /// MarkRegAndAliases - Mark the specified register and all aliases in the 04865 /// specified set. 04866 static void MarkRegAndAliases(unsigned Reg, std::set<unsigned> &Regs, 04867 const TargetRegisterInfo &TRI) { 04868 assert(TargetRegisterInfo::isPhysicalRegister(Reg) && "Isn't a physreg"); 04869 Regs.insert(Reg); 04870 if (const unsigned *Aliases = TRI.getAliasSet(Reg)) 04871 for (; *Aliases; ++Aliases) 04872 Regs.insert(*Aliases); 04873 } 04874 }; 04875 } // end llvm namespace. 04876 04877 04878 /// GetRegistersForValue - Assign registers (virtual or physical) for the 04879 /// specified operand. We prefer to assign virtual registers, to allow the 04880 /// register allocator handle the assignment process. However, if the asm uses 04881 /// features that we can't model on machineinstrs, we have SDISel do the 04882 /// allocation. This produces generally horrible, but correct, code. 04883 /// 04884 /// OpInfo describes the operand. 04885 /// Input and OutputRegs are the set of already allocated physical registers. 04886 /// 04887 void SelectionDAGLowering:: 04888 GetRegistersForValue(SDISelAsmOperandInfo &OpInfo, 04889 std::set<unsigned> &OutputRegs, 04890 std::set<unsigned> &InputRegs) { 04891 LLVMContext &Context = FuncInfo.Fn->getContext(); 04892 04893 // Compute whether this value requires an input register, an output register, 04894 // or both. 04895 bool isOutReg = false; 04896 bool isInReg = false; 04897 switch (OpInfo.Type) { 04898 case InlineAsm::isOutput: 04899 isOutReg = true; 04900 04901 // If there is an input constraint that matches this, we need to reserve 04902 // the input register so no other inputs allocate to it. 04903 isInReg = OpInfo.hasMatchingInput(); 04904 break; 04905 case InlineAsm::isInput: 04906 isInReg = true; 04907 isOutReg = false; 04908 break; 04909 case InlineAsm::isClobber: 04910 isOutReg = true; 04911 isInReg = true; 04912 break; 04913 } 04914 04915 04916 MachineFunction &MF = DAG.getMachineFunction(); 04917 SmallVector<unsigned, 4> Regs; 04918 04919 // If this is a constraint for a single physreg, or a constraint for a 04920 // register class, find it. 04921 std::pair<unsigned, const TargetRegisterClass*> PhysReg = 04922 TLI.getRegForInlineAsmConstraint(OpInfo.ConstraintCode, 04923 OpInfo.ConstraintVT); 04924 04925 unsigned NumRegs = 1; 04926 if (OpInfo.ConstraintVT != MVT::Other) { 04927 // If this is a FP input in an integer register (or visa versa) insert a bit 04928 // cast of the input value. More generally, handle any case where the input 04929 // value disagrees with the register class we plan to stick this in. 04930 if (OpInfo.Type == InlineAsm::isInput && 04931 PhysReg.second && !PhysReg.second->hasType(OpInfo.ConstraintVT)) { 04932 // Try to convert to the first EVT that the reg class contains. If the 04933 // types are identical size, use a bitcast to convert (e.g. two differing 04934 // vector types). 04935 EVT RegVT = *PhysReg.second->vt_begin(); 04936 if (RegVT.getSizeInBits() == OpInfo.ConstraintVT.getSizeInBits()) { 04937 OpInfo.CallOperand = DAG.getNode(ISD::BIT_CONVERT, getCurDebugLoc(), 04938 RegVT, OpInfo.CallOperand); 04939 OpInfo.ConstraintVT = RegVT; 04940 } else if (RegVT.isInteger() && OpInfo.ConstraintVT.isFloatingPoint()) { 04941 // If the input is a FP value and we want it in FP registers, do a 04942 // bitcast to the corresponding integer type. This turns an f64 value 04943 // into i64, which can be passed with two i32 values on a 32-bit 04944 // machine. 04945 RegVT = EVT::getIntegerVT(Context, 04946 OpInfo.ConstraintVT.getSizeInBits()); 04947 OpInfo.CallOperand = DAG.getNode(ISD::BIT_CONVERT, getCurDebugLoc(), 04948 RegVT, OpInfo.CallOperand); 04949 OpInfo.ConstraintVT = RegVT; 04950 } 04951 } 04952 04953 NumRegs = TLI.getNumRegisters(Context, OpInfo.ConstraintVT); 04954 } 04955 04956 EVT RegVT; 04957 EVT ValueVT = OpInfo.ConstraintVT; 04958 04959 // If this is a constraint for a specific physical register, like {r17}, 04960 // assign it now. 04961 if (unsigned AssignedReg = PhysReg.first) { 04962 const TargetRegisterClass *RC = PhysReg.second; 04963 if (OpInfo.ConstraintVT == MVT::Other) 04964 ValueVT = *RC->vt_begin(); 04965 04966 // Get the actual register value type. This is important, because the user 04967 // may have asked for (e.g.) the AX register in i32 type. We need to 04968 // remember that AX is actually i16 to get the right extension. 04969 RegVT = *RC->vt_begin(); 04970 04971 // This is a explicit reference to a physical register. 04972 Regs.push_back(AssignedReg); 04973 04974 // If this is an expanded reference, add the rest of the regs to Regs. 04975 if (NumRegs != 1) { 04976 TargetRegisterClass::iterator I = RC->begin(); 04977 for (; *I != AssignedReg; ++I) 04978 assert(I != RC->end() && "Didn't find reg!"); 04979 04980 // Already added the first reg. 04981 --NumRegs; ++I; 04982 for (; NumRegs; --NumRegs, ++I) { 04983 assert(I != RC->end() && "Ran out of registers to allocate!"); 04984 Regs.push_back(*I); 04985 } 04986 } 04987 OpInfo.AssignedRegs = RegsForValue(TLI, Regs, RegVT, ValueVT); 04988 const TargetRegisterInfo *TRI = DAG.getTarget().getRegisterInfo(); 04989 OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs, *TRI); 04990 return; 04991 } 04992 04993 // Otherwise, if this was a reference to an LLVM register class, create vregs 04994 // for this reference. 04995 if (const TargetRegisterClass *RC = PhysReg.second) { 04996 RegVT = *RC->vt_begin(); 04997 if (OpInfo.ConstraintVT == MVT::Other) 04998 ValueVT = RegVT; 04999 05000 // Create the appropriate number of virtual registers. 05001 MachineRegisterInfo &RegInfo = MF.getRegInfo(); 05002 for (; NumRegs; --NumRegs) 05003 Regs.push_back(RegInfo.createVirtualRegister(RC)); 05004 05005 OpInfo.AssignedRegs = RegsForValue(TLI, Regs, RegVT, ValueVT); 05006 return; 05007 } 05008 05009 // This is a reference to a register class that doesn't directly correspond 05010 // to an LLVM register class. Allocate NumRegs consecutive, available, 05011 // registers from the class. 05012 std::vector<unsigned> RegClassRegs 05013 = TLI.getRegClassForInlineAsmConstraint(OpInfo.ConstraintCode, 05014 OpInfo.ConstraintVT); 05015 05016 const TargetRegisterInfo *TRI = DAG.getTarget().getRegisterInfo(); 05017 unsigned NumAllocated = 0; 05018 for (unsigned i = 0, e = RegClassRegs.size(); i != e; ++i) { 05019 unsigned Reg = RegClassRegs[i]; 05020 // See if this register is available. 05021 if ((isOutReg && OutputRegs.count(Reg)) || // Already used. 05022 (isInReg && InputRegs.count(Reg))) { // Already used. 05023 // Make sure we find consecutive registers. 05024 NumAllocated = 0; 05025 continue; 05026 } 05027 05028 // Check to see if this register is allocatable (i.e. don't give out the 05029 // stack pointer). 05030 const TargetRegisterClass *RC = isAllocatableRegister(Reg, MF, TLI, TRI); 05031 if (!RC) { // Couldn't allocate this register. 05032 // Reset NumAllocated to make sure we return consecutive registers. 05033 NumAllocated = 0; 05034 continue; 05035 } 05036 05037 // Okay, this register is good, we can use it. 05038 ++NumAllocated; 05039 05040 // If we allocated enough consecutive registers, succeed. 05041 if (NumAllocated == NumRegs) { 05042 unsigned RegStart = (i-NumAllocated)+1; 05043 unsigned RegEnd = i+1; 05044 // Mark all of the allocated registers used. 05045 for (unsigned i = RegStart; i != RegEnd; ++i) 05046 Regs.push_back(RegClassRegs[i]); 05047 05048 OpInfo.AssignedRegs = RegsForValue(TLI, Regs, *RC->vt_begin(), 05049 OpInfo.ConstraintVT); 05050 OpInfo.MarkAllocatedRegs(isOutReg, isInReg, OutputRegs, InputRegs, *TRI); 05051 return; 05052 } 05053 } 05054 05055 // Otherwise, we couldn't allocate enough registers for this. 05056 } 05057 05058 /// hasInlineAsmMemConstraint - Return true if the inline asm instruction being 05059 /// processed uses a memory 'm' constraint. 05060 static bool 05061 hasInlineAsmMemConstraint(std::vector<InlineAsm::ConstraintInfo> &CInfos, 05062 const TargetLowering &TLI) { 05063 for (unsigned i = 0, e = CInfos.size(); i != e; ++i) { 05064 InlineAsm::ConstraintInfo &CI = CInfos[i]; 05065 for (unsigned j = 0, ee = CI.Codes.size(); j != ee; ++j) { 05066 TargetLowering::ConstraintType CType = TLI.getConstraintType(CI.Codes[j]); 05067 if (CType == TargetLowering::C_Memory) 05068 return true; 05069 } 05070 05071 // Indirect operand accesses access memory. 05072 if (CI.isIndirect) 05073 return true; 05074 } 05075 05076 return false; 05077 } 05078 05079 /// visitInlineAsm - Handle a call to an InlineAsm object. 05080 /// 05081 void SelectionDAGLowering::visitInlineAsm(CallSite CS) { 05082 InlineAsm *IA = cast<InlineAsm>(CS.getCalledValue()); 05083 05084 /// ConstraintOperands - Information about all of the constraints. 05085 std::vector<SDISelAsmOperandInfo> ConstraintOperands; 05086 05087 std::set<unsigned> OutputRegs, InputRegs; 05088 05089 // Do a prepass over the constraints, canonicalizing them, and building up the 05090 // ConstraintOperands list. 05091 std::vector<InlineAsm::ConstraintInfo> 05092 ConstraintInfos = IA->ParseConstraints(); 05093 05094 bool hasMemory = hasInlineAsmMemConstraint(ConstraintInfos, TLI); 05095 05096 SDValue Chain, Flag; 05097 05098 // We won't need to flush pending loads if this asm doesn't touch 05099 // memory and is nonvolatile. 05100 if (hasMemory || IA->hasSideEffects()) 05101 Chain = getRoot(); 05102 else 05103 Chain = DAG.getRoot(); 05104 05105 unsigned ArgNo = 0; // ArgNo - The argument of the CallInst. 05106 unsigned ResNo = 0; // ResNo - The result number of the next output. 05107 for (unsigned i = 0, e = ConstraintInfos.size(); i != e; ++i) { 05108 ConstraintOperands.push_back(SDISelAsmOperandInfo(ConstraintInfos[i])); 05109 SDISelAsmOperandInfo &OpInfo = ConstraintOperands.back(); 05110 05111 EVT OpVT = MVT::Other; 05112 05113 // Compute the value type for each operand. 05114 switch (OpInfo.Type) { 05115 case InlineAsm::isOutput: 05116 // Indirect outputs just consume an argument. 05117 if (OpInfo.isIndirect) { 05118 OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 05119 break; 05120 } 05121 05122 // The return value of the call is this value. As such, there is no 05123 // corresponding argument. 05124 assert(CS.getType() != Type::getVoidTy(*DAG.getContext()) && 05125 "Bad inline asm!"); 05126 if (const StructType *STy = dyn_cast<StructType>(CS.getType())) { 05127 OpVT = TLI.getValueType(STy->getElementType(ResNo)); 05128 } else { 05129 assert(ResNo == 0 && "Asm only has one result!"); 05130 OpVT = TLI.getValueType(CS.getType()); 05131 } 05132 ++ResNo; 05133 break; 05134 case InlineAsm::isInput: 05135 OpInfo.CallOperandVal = CS.getArgument(ArgNo++); 05136 break; 05137 case InlineAsm::isClobber: 05138 // Nothing to do. 05139 break; 05140 } 05141 05142 // If this is an input or an indirect output, process the call argument. 05143 // BasicBlocks are labels, currently appearing only in asm's. 05144 if (OpInfo.CallOperandVal) { 05145 // Strip bitcasts, if any. This mostly comes up for functions. 05146 OpInfo.CallOperandVal = OpInfo.CallOperandVal->stripPointerCasts(); 05147 05148 if (BasicBlock *BB = dyn_cast<BasicBlock>(OpInfo.CallOperandVal)) { 05149 OpInfo.CallOperand = DAG.getBasicBlock(FuncInfo.MBBMap[BB]); 05150 } else { 05151 OpInfo.CallOperand = getValue(OpInfo.CallOperandVal); 05152 } 05153 05154 OpVT = OpInfo.getCallOperandValEVT(*DAG.getContext(), TLI, TD); 05155 } 05156 05157 OpInfo.ConstraintVT = OpVT; 05158 } 05159 05160 // Second pass over the constraints: compute which constraint option to use 05161 // and assign registers to constraints that want a specific physreg. 05162 for (unsigned i = 0, e = ConstraintInfos.size(); i != e; ++i) { 05163 SDISelAsmOperandInfo &OpInfo = ConstraintOperands[i]; 05164 05165 // If this is an output operand with a matching input operand, look up the 05166 // matching input. If their types mismatch, e.g. one is an integer, the 05167 // other is floating point, or their sizes are different, flag it as an 05168 // error. 05169 if (OpInfo.hasMatchingInput()) { 05170 SDISelAsmOperandInfo &Input = ConstraintOperands[OpInfo.MatchingInput]; 05171 if (OpInfo.ConstraintVT != Input.ConstraintVT) { 05172 if ((OpInfo.ConstraintVT.isInteger() != 05173 Input.ConstraintVT.isInteger()) || 05174 (OpInfo.ConstraintVT.getSizeInBits() != 05175 Input.ConstraintVT.getSizeInBits())) { 05176 llvm_report_error("Unsupported asm: input constraint" 05177 " with a matching output constraint of incompatible" 05178 " type!"); 05179 } 05180 Input.ConstraintVT = OpInfo.ConstraintVT; 05181 } 05182 } 05183 05184 // Compute the constraint code and ConstraintType to use. 05185 TLI.ComputeConstraintToUse(OpInfo, OpInfo.CallOperand, hasMemory, &DAG); 05186 05187 // If this is a memory input, and if the operand is not indirect, do what we 05188 // need to to provide an address for the memory input. 05189 if (OpInfo.ConstraintType == TargetLowering::C_Memory && 05190 !OpInfo.isIndirect) { 05191 assert(OpInfo.Type == InlineAsm::isInput && 05192 "Can only indirectify direct input operands!"); 05193 05194 // Memory operands really want the address of the value. If we don't have 05195 // an indirect input, put it in the constpool if we can, otherwise spill 05196 // it to a stack slot. 05197 05198 // If the operand is a float, integer, or vector constant, spill to a 05199 // constant pool entry to get its address. 05200 Value *OpVal = OpInfo.CallOperandVal; 05201 if (isa<ConstantFP>(OpVal) || isa<ConstantInt>(OpVal) || 05202 isa<ConstantVector>(OpVal)) { 05203 OpInfo.CallOperand = DAG.getConstantPool(cast<Constant>(OpVal), 05204 TLI.getPointerTy()); 05205 } else { 05206 // Otherwise, create a stack slot and emit a store to it before the 05207 // asm. 05208 const Type *Ty = OpVal->getType(); 05209 uint64_t TySize = TLI.getTargetData()->getTypeAllocSize(Ty); 05210 unsigned Align = TLI.getTargetData()->getPrefTypeAlignment(Ty); 05211 MachineFunction &MF = DAG.getMachineFunction(); 05212 int SSFI = MF.getFrameInfo()->CreateStackObject(TySize, Align); 05213 SDValue StackSlot = DAG.getFrameIndex(SSFI, TLI.getPointerTy()); 05214 Chain = DAG.getStore(Chain, getCurDebugLoc(), 05215 OpInfo.CallOperand, StackSlot, NULL, 0); 05216 OpInfo.CallOperand = StackSlot; 05217 } 05218 05219 // There is no longer a Value* corresponding to this operand. 05220 OpInfo.CallOperandVal = 0; 05221 // It is now an indirect operand. 05222 OpInfo.isIndirect = true; 05223 } 05224 05225 // If this constraint is for a specific register, allocate it before 05226 // anything else. 05227 if (OpInfo.ConstraintType == TargetLowering::C_Register) 05228 GetRegistersForValue(OpInfo, OutputRegs, InputRegs); 05229 } 05230 ConstraintInfos.clear(); 05231 05232 05233 // Second pass - Loop over all of the operands, assigning virtual or physregs 05234 // to register class operands. 05235 for (unsigned i = 0, e = ConstraintOperands.size(); i != e; ++i) { 05236 SDISelAsmOperandInfo &OpInfo = ConstraintOperands[i]; 05237 05238 // C_Register operands have already been allocated, Other/Memory don't need 05239 // to be. 05240 if (OpInfo.ConstraintType == TargetLowering::C_RegisterClass) 05241 GetRegistersForValue(OpInfo, OutputRegs, InputRegs); 05242 } 05243 05244 // AsmNodeOperands - The operands for the ISD::INLINEASM node. 05245 std::vector<SDValue> AsmNodeOperands; 05246 AsmNodeOperands.push_back(SDValue()); // reserve space for input chain 05247 AsmNodeOperands.push_back( 05248 DAG.getTargetExternalSymbol(IA->getAsmString().c_str(), MVT::Other)); 05249 05250 05251 // Loop over all of the inputs, copying the operand values into the 05252 // appropriate registers and processing the output regs. 05253 RegsForValue RetValRegs; 05254 05255 // IndirectStoresToEmit - The set of stores to emit after the inline asm node. 05256 std::vector<std::pair<RegsForValue, Value*> > IndirectStoresToEmit; 05257 05258 for (unsigned i = 0, e = ConstraintOperands.size(); i != e; ++i) { 05259 SDISelAsmOperandInfo &OpInfo = ConstraintOperands[i]; 05260 05261 switch (OpInfo.Type) { 05262 case InlineAsm::isOutput: { 05263 if (OpInfo.ConstraintType != TargetLowering::C_RegisterClass && 05264 OpInfo.ConstraintType != TargetLowering::C_Register) { 05265 // Memory output, or 'other' output (e.g. 'X' constraint). 05266 assert(OpInfo.isIndirect && "Memory output must be indirect operand"); 05267 05268 // Add information to the INLINEASM node to know about this output. 05269 unsigned ResOpType = 4/*MEM*/ | (1<<3); 05270 AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 05271 TLI.getPointerTy())); 05272 AsmNodeOperands.push_back(OpInfo.CallOperand); 05273 break; 05274 } 05275 05276 // Otherwise, this is a register or register class output. 05277 05278 // Copy the output from the appropriate register. Find a register that 05279 // we can use. 05280 if (OpInfo.AssignedRegs.Regs.empty()) { 05281 llvm_report_error("Couldn't allocate output reg for" 05282 " constraint '" + OpInfo.ConstraintCode + "'!"); 05283 } 05284 05285 // If this is an indirect operand, store through the pointer after the 05286 // asm. 05287 if (OpInfo.isIndirect) { 05288 IndirectStoresToEmit.push_back(std::make_pair(OpInfo.AssignedRegs, 05289 OpInfo.CallOperandVal)); 05290 } else { 05291 // This is the result value of the call. 05292 assert(CS.getType() != Type::getVoidTy(*DAG.getContext()) && 05293 "Bad inline asm!"); 05294 // Concatenate this output onto the outputs list. 05295 RetValRegs.append(OpInfo.AssignedRegs); 05296 } 05297 05298 // Add information to the INLINEASM node to know that this register is 05299 // set. 05300 OpInfo.AssignedRegs.AddInlineAsmOperands(OpInfo.isEarlyClobber ? 05301 6 /* EARLYCLOBBER REGDEF */ : 05302 2 /* REGDEF */ , 05303 false, 05304 0, 05305 DAG, AsmNodeOperands); 05306 break; 05307 } 05308 case InlineAsm::isInput: { 05309 SDValue InOperandVal = OpInfo.CallOperand; 05310 05311 if (OpInfo.isMatchingInputConstraint()) { // Matching constraint? 05312 // If this is required to match an output register we have already set, 05313 // just use its register. 05314 unsigned OperandNo = OpInfo.getMatchedOperand(); 05315 05316 // Scan until we find the definition we already emitted of this operand. 05317 // When we find it, create a RegsForValue operand. 05318 unsigned CurOp = 2; // The first operand. 05319 for (; OperandNo; --OperandNo) { 05320 // Advance to the next operand. 05321 unsigned OpFlag = 05322 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getZExtValue(); 05323 assert(((OpFlag & 7) == 2 /*REGDEF*/ || 05324 (OpFlag & 7) == 6 /*EARLYCLOBBER REGDEF*/ || 05325 (OpFlag & 7) == 4 /*MEM*/) && 05326 "Skipped past definitions?"); 05327 CurOp += InlineAsm::getNumOperandRegisters(OpFlag)+1; 05328 } 05329 05330 unsigned OpFlag = 05331 cast<ConstantSDNode>(AsmNodeOperands[CurOp])->getZExtValue(); 05332 if ((OpFlag & 7) == 2 /*REGDEF*/ 05333 || (OpFlag & 7) == 6 /* EARLYCLOBBER REGDEF */) { 05334 // Add (OpFlag&0xffff)>>3 registers to MatchedRegs. 05335 if (OpInfo.isIndirect) { 05336 llvm_report_error("Don't know how to handle tied indirect " 05337 "register inputs yet!"); 05338 } 05339 RegsForValue MatchedRegs; 05340 MatchedRegs.TLI = &TLI; 05341 MatchedRegs.ValueVTs.push_back(InOperandVal.getValueType()); 05342 EVT RegVT = AsmNodeOperands[CurOp+1].getValueType(); 05343 MatchedRegs.RegVTs.push_back(RegVT); 05344 MachineRegisterInfo &RegInfo = DAG.getMachineFunction().getRegInfo(); 05345 for (unsigned i = 0, e = InlineAsm::getNumOperandRegisters(OpFlag); 05346 i != e; ++i) 05347 MatchedRegs.Regs. 05348 push_back(RegInfo.createVirtualRegister(TLI.getRegClassFor(RegVT))); 05349 05350 // Use the produced MatchedRegs object to 05351 MatchedRegs.getCopyToRegs(InOperandVal, DAG, getCurDebugLoc(), 05352 Chain, &Flag); 05353 MatchedRegs.AddInlineAsmOperands(1 /*REGUSE*/, 05354 true, OpInfo.getMatchedOperand(), 05355 DAG, AsmNodeOperands); 05356 break; 05357 } else { 05358 assert(((OpFlag & 7) == 4) && "Unknown matching constraint!"); 05359 assert((InlineAsm::getNumOperandRegisters(OpFlag)) == 1 && 05360 "Unexpected number of operands"); 05361 // Add information to the INLINEASM node to know about this input. 05362 // See InlineAsm.h isUseOperandTiedToDef. 05363 OpFlag |= 0x80000000 | (OpInfo.getMatchedOperand() << 16); 05364 AsmNodeOperands.push_back(DAG.getTargetConstant(OpFlag, 05365 TLI.getPointerTy())); 05366 AsmNodeOperands.push_back(AsmNodeOperands[CurOp+1]); 05367 break; 05368 } 05369 } 05370 05371 if (OpInfo.ConstraintType == TargetLowering::C_Other) { 05372 assert(!OpInfo.isIndirect && 05373 "Don't know how to handle indirect other inputs yet!"); 05374 05375 std::vector<SDValue> Ops; 05376 TLI.LowerAsmOperandForConstraint(InOperandVal, OpInfo.ConstraintCode[0], 05377 hasMemory, Ops, DAG); 05378 if (Ops.empty()) { 05379 llvm_report_error("Invalid operand for inline asm" 05380 " constraint '" + OpInfo.ConstraintCode + "'!"); 05381 } 05382 05383 // Add information to the INLINEASM node to know about this input. 05384 unsigned ResOpType = 3 /*IMM*/ | (Ops.size() << 3); 05385 AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 05386 TLI.getPointerTy())); 05387 AsmNodeOperands.insert(AsmNodeOperands.end(), Ops.begin(), Ops.end()); 05388 break; 05389 } else if (OpInfo.ConstraintType == TargetLowering::C_Memory) { 05390 assert(OpInfo.isIndirect && "Operand must be indirect to be a mem!"); 05391 assert(InOperandVal.getValueType() == TLI.getPointerTy() && 05392 "Memory operands expect pointer values"); 05393 05394 // Add information to the INLINEASM node to know about this input. 05395 unsigned ResOpType = 4/*MEM*/ | (1<<3); 05396 AsmNodeOperands.push_back(DAG.getTargetConstant(ResOpType, 05397 TLI.getPointerTy())); 05398 AsmNodeOperands.push_back(InOperandVal); 05399 break; 05400 } 05401 05402 assert((OpInfo.ConstraintType == TargetLowering::C_RegisterClass || 05403 OpInfo.ConstraintType == TargetLowering::C_Register) && 05404 "Unknown constraint type!"); 05405 assert(!OpInfo.isIndirect && 05406 "Don't know how to handle indirect register inputs yet!"); 05407 05408 // Copy the input into the appropriate registers. 05409 if (OpInfo.AssignedRegs.Regs.empty()) { 05410 llvm_report_error("Couldn't allocate input reg for" 05411 " constraint '"+ OpInfo.ConstraintCode +"'!"); 05412 } 05413 05414 OpInfo.AssignedRegs.getCopyToRegs(InOperandVal, DAG, getCurDebugLoc(), 05415 Chain, &Flag); 05416 05417 OpInfo.AssignedRegs.AddInlineAsmOperands(1/*REGUSE*/, false, 0, 05418 DAG, AsmNodeOperands); 05419 break; 05420 } 05421 case InlineAsm::isClobber: { 05422 // Add the clobbered value to the operand list, so that the register 05423 // allocator is aware that the physreg got clobbered. 05424 if (!OpInfo.AssignedRegs.Regs.empty()) 05425 OpInfo.AssignedRegs.AddInlineAsmOperands(6 /* EARLYCLOBBER REGDEF */, 05426 false, 0, DAG,AsmNodeOperands); 05427 break; 05428 } 05429 } 05430 } 05431 05432 // Finish up input operands. 05433 AsmNodeOperands[0] = Chain; 05434 if (Flag.getNode()) AsmNodeOperands.push_back(Flag); 05435 05436 Chain = DAG.getNode(ISD::INLINEASM, getCurDebugLoc(), 05437 DAG.getVTList(MVT::Other, MVT::Flag), 05438 &AsmNodeOperands[0], AsmNodeOperands.size()); 05439 Flag = Chain.getValue(1); 05440 05441 // If this asm returns a register value, copy the result from that register 05442 // and set it as the value of the call. 05443 if (!RetValRegs.Regs.empty()) { 05444 SDValue Val = RetValRegs.getCopyFromRegs(DAG, getCurDebugLoc(), 05445 Chain, &Flag); 05446 05447 // FIXME: Why don't we do this for inline asms with MRVs? 05448 if (CS.getType()->isSingleValueType() && CS.getType()->isSized()) { 05449 EVT ResultType = TLI.getValueType(CS.getType()); 05450 05451 // If any of the results of the inline asm is a vector, it may have the 05452 // wrong width/num elts. This can happen for register classes that can 05453 // contain multiple different value types. The preg or vreg allocated may 05454 // not have the same VT as was expected. Convert it to the right type 05455 // with bit_convert. 05456 if (ResultType != Val.getValueType() && Val.getValueType().isVector()) { 05457 Val = DAG.getNode(ISD::BIT_CONVERT, getCurDebugLoc(), 05458 ResultType, Val); 05459 05460 } else if (ResultType != Val.getValueType() && 05461 ResultType.isInteger() && Val.getValueType().isInteger()) { 05462 // If a result value was tied to an input value, the computed result may 05463 // have a wider width than the expected result. Extract the relevant 05464 // portion. 05465 Val = DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(), ResultType, Val); 05466 } 05467 05468 assert(ResultType == Val.getValueType() && "Asm result value mismatch!"); 05469 } 05470 05471 setValue(CS.getInstruction(), Val); 05472 // Don't need to use this as a chain in this case. 05473 if (!IA->hasSideEffects() && !hasMemory && IndirectStoresToEmit.empty()) 05474 return; 05475 } 05476 05477 std::vector<std::pair<SDValue, Value*> > StoresToEmit; 05478 05479 // Process indirect outputs, first output all of the flagged copies out of 05480 // physregs. 05481 for (unsigned i = 0, e = IndirectStoresToEmit.size(); i != e; ++i) { 05482 RegsForValue &OutRegs = IndirectStoresToEmit[i].first; 05483 Value *Ptr = IndirectStoresToEmit[i].second; 05484 SDValue OutVal = OutRegs.getCopyFromRegs(DAG, getCurDebugLoc(), 05485 Chain, &Flag); 05486 StoresToEmit.push_back(std::make_pair(OutVal, Ptr)); 05487 05488 } 05489 05490 // Emit the non-flagged stores from the physregs. 05491 SmallVector<SDValue, 8> OutChains; 05492 for (unsigned i = 0, e = StoresToEmit.size(); i != e; ++i) 05493 OutChains.push_back(DAG.getStore(Chain, getCurDebugLoc(), 05494 StoresToEmit[i].first, 05495 getValue(StoresToEmit[i].second), 05496 StoresToEmit[i].second, 0)); 05497 if (!OutChains.empty()) 05498 Chain = DAG.getNode(ISD::TokenFactor, getCurDebugLoc(), MVT::Other, 05499 &OutChains[0], OutChains.size()); 05500 DAG.setRoot(Chain); 05501 } 05502 05503 05504 void SelectionDAGLowering::visitMalloc(MallocInst &I) { 05505 SDValue Src = getValue(I.getOperand(0)); 05506 05507 // Scale up by the type size in the original i32 type width. Various 05508 // mid-level optimizers may make assumptions about demanded bits etc from the 05509 // i32-ness of the optimizer: we do not want to promote to i64 and then 05510 // multiply on 64-bit targets. 05511 // FIXME: Malloc inst should go away: PR715. 05512 uint64_t ElementSize = TD->getTypeAllocSize(I.getType()->getElementType()); 05513 if (ElementSize != 1) { 05514 // Src is always 32-bits, make sure the constant fits. 05515 assert(Src.getValueType() == MVT::i32); 05516 ElementSize = (uint32_t)ElementSize; 05517 Src = DAG.getNode(ISD::MUL, getCurDebugLoc(), Src.getValueType(), 05518 Src, DAG.getConstant(ElementSize, Src.getValueType())); 05519 } 05520 05521 EVT IntPtr = TLI.getPointerTy(); 05522 05523 if (IntPtr.bitsLT(Src.getValueType())) 05524 Src = DAG.getNode(ISD::TRUNCATE, getCurDebugLoc(), IntPtr, Src); 05525 else if (IntPtr.bitsGT(Src.getValueType())) 05526 Src = DAG.getNode(ISD::ZERO_EXTEND, getCurDebugLoc(), IntPtr, Src); 05527 05528 TargetLowering::ArgListTy Args; 05529 TargetLowering::ArgListEntry Entry; 05530 Entry.Node = Src; 05531 Entry.Ty = TLI.getTargetData()->getIntPtrType(*DAG.getContext()); 05532 Args.push_back(Entry); 05533 05534 bool isTailCall = PerformTailCallOpt && 05535 isInTailCallPosition(&I, Attribute::None, TLI); 05536 std::pair<SDValue,SDValue> Result = 05537 TLI.LowerCallTo(getRoot(), I.getType(), false, false, false, false, 05538 0, CallingConv::C, isTailCall, 05539 /*isReturnValueUsed=*/true, 05540 DAG.getExternalSymbol("malloc", IntPtr), 05541 Args, DAG, getCurDebugLoc()); 05542 if (Result.first.getNode()) 05543 setValue(&I, Result.first); // Pointers always fit in registers 05544 if (Result.second.getNode()) 05545 DAG.setRoot(Result.second); 05546 } 05547 05548 void SelectionDAGLowering::visitFree(FreeInst &I) { 05549 TargetLowering::ArgListTy Args; 05550 TargetLowering::ArgListEntry Entry; 05551 Entry.Node = getValue(I.getOperand(0)); 05552 Entry.Ty = TLI.getTargetData()->getIntPtrType(*DAG.getContext()); 05553 Args.push_back(Entry); 05554 EVT IntPtr = TLI.getPointerTy(); 05555 bool isTailCall = PerformTailCallOpt && 05556 isInTailCallPosition(&I, Attribute::None, TLI); 05557 std::pair<SDValue,SDValue> Result = 05558 TLI.LowerCallTo(getRoot(), Type::getVoidTy(*DAG.getContext()), 05559 false, false, false, false, 05560 0, CallingConv::C, isTailCall, 05561 /*isReturnValueUsed=*/true, 05562 DAG.getExternalSymbol("free", IntPtr), Args, DAG, 05563 getCurDebugLoc()); 05564 if (Result.second.getNode()) 05565 DAG.setRoot(Result.second); 05566 } 05567 05568 void SelectionDAGLowering::visitVAStart(CallInst &I) { 05569 DAG.setRoot(DAG.getNode(ISD::VASTART, getCurDebugLoc(), 05570 MVT::Other, getRoot(), 05571 getValue(I.getOperand(1)), 05572 DAG.getSrcValue(I.getOperand(1)))); 05573 } 05574 05575 void SelectionDAGLowering::visitVAArg(VAArgInst &I) { 05576 SDValue V = DAG.getVAArg(TLI.getValueType(I.getType()), getCurDebugLoc(), 05577 getRoot(), getValue(I.getOperand(0)), 05578 DAG.getSrcValue(I.getOperand(0))); 05579 setValue(&I, V); 05580 DAG.setRoot(V.getValue(1)); 05581 } 05582 05583 void SelectionDAGLowering::visitVAEnd(CallInst &I) { 05584 DAG.setRoot(DAG.getNode(ISD::VAEND, getCurDebugLoc(), 05585 MVT::Other, getRoot(), 05586 getValue(I.getOperand(1)), 05587 DAG.getSrcValue(I.getOperand(1)))); 05588 } 05589 05590 void SelectionDAGLowering::visitVACopy(CallInst &I) { 05591 DAG.setRoot(DAG.getNode(ISD::VACOPY, getCurDebugLoc(), 05592 MVT::Other, getRoot(), 05593 getValue(I.getOperand(1)), 05594 getValue(I.getOperand(2)), 05595 DAG.getSrcValue(I.getOperand(1)), 05596 DAG.getSrcValue(I.getOperand(2)))); 05597 } 05598 05599 /// TargetLowering::LowerCallTo - This is the default LowerCallTo 05600 /// implementation, which just calls LowerCall. 05601 /// FIXME: When all targets are 05602 /// migrated to using LowerCall, this hook should be integrated into SDISel. 05603 std::pair<SDValue, SDValue> 05604 TargetLowering::LowerCallTo(SDValue Chain, const Type *RetTy, 05605 bool RetSExt, bool RetZExt, bool isVarArg, 05606 bool isInreg, unsigned NumFixedArgs, 05607 unsigned CallConv, bool isTailCall, 05608 bool isReturnValueUsed, 05609 SDValue Callee, 05610 ArgListTy &Args, SelectionDAG &DAG, DebugLoc dl) { 05611 05612 assert((!isTailCall || PerformTailCallOpt) && 05613 "isTailCall set when tail-call optimizations are disabled!"); 05614 05615 // Handle all of the outgoing arguments. 05616 SmallVector<ISD::OutputArg, 32> Outs; 05617 for (unsigned i = 0, e = Args.size(); i != e; ++i) { 05618 SmallVector<EVT, 4> ValueVTs; 05619 ComputeValueVTs(*this, Args[i].Ty, ValueVTs); 05620 for (unsigned Value = 0, NumValues = ValueVTs.size(); 05621 Value != NumValues; ++Value) { 05622 EVT VT = ValueVTs[Value]; 05623 const Type *ArgTy = VT.getTypeForEVT(RetTy->getContext()); 05624 SDValue Op = SDValue(Args[i].Node.getNode(), 05625 Args[i].Node.getResNo() + Value); 05626 ISD::ArgFlagsTy Flags; 05627 unsigned OriginalAlignment = 05628 getTargetData()->getABITypeAlignment(ArgTy); 05629 05630 if (Args[i].isZExt) 05631 Flags.setZExt(); 05632 if (Args[i].isSExt) 05633 Flags.setSExt(); 05634 if (Args[i].isInReg) 05635 Flags.setInReg(); 05636 if (Args[i].isSRet) 05637 Flags.setSRet(); 05638 if (Args[i].isByVal) { 05639 Flags.setByVal(); 05640 const PointerType *Ty = cast<PointerType>(Args[i].Ty); 05641 const Type *ElementTy = Ty->getElementType(); 05642 unsigned FrameAlign = getByValTypeAlignment(ElementTy); 05643 unsigned FrameSize = getTargetData()->getTypeAllocSize(ElementTy); 05644 // For ByVal, alignment should come from FE. BE will guess if this 05645 // info is not there but there are cases it cannot get right. 05646 if (Args[i].Alignment) 05647 FrameAlign = Args[i].Alignment; 05648 Flags.setByValAlign(FrameAlign); 05649 Flags.setByValSize(FrameSize); 05650 } 05651 if (Args[i].isNest) 05652 Flags.setNest(); 05653 Flags.setOrigAlign(OriginalAlignment); 05654 05655 EVT PartVT = getRegisterType(RetTy->getContext(), VT); 05656 unsigned NumParts = getNumRegisters(RetTy->getContext(), VT); 05657 SmallVector<SDValue, 4> Parts(NumParts); 05658 ISD::NodeType ExtendKind = ISD::ANY_EXTEND; 05659 05660 if (Args[i].isSExt) 05661 ExtendKind = ISD::SIGN_EXTEND; 05662 else if (Args[i].isZExt) 05663 ExtendKind = ISD::ZERO_EXTEND; 05664 05665 getCopyToParts(DAG, dl, Op, &Parts[0], NumParts, PartVT, ExtendKind); 05666 05667 for (unsigned j = 0; j != NumParts; ++j) { 05668 // if it isn't first piece, alignment must be 1 05669 ISD::OutputArg MyFlags(Flags, Parts[j], i < NumFixedArgs); 05670 if (NumParts > 1 && j == 0) 05671 MyFlags.Flags.setSplit(); 05672 else if (j != 0) 05673 MyFlags.Flags.setOrigAlign(1); 05674 05675 Outs.push_back(MyFlags); 05676 } 05677 } 05678 } 05679 05680 // Handle the incoming return values from the call. 05681 SmallVector<ISD::InputArg, 32> Ins; 05682 SmallVector<EVT, 4> RetTys; 05683 ComputeValueVTs(*this, RetTy, RetTys); 05684 for (unsigned I = 0, E = RetTys.size(); I != E; ++I) { 05685 EVT VT = RetTys[I]; 05686 EVT RegisterVT = getRegisterType(RetTy->getContext(), VT); 05687 unsigned NumRegs = getNumRegisters(RetTy->getContext(), VT); 05688 for (unsigned i = 0; i != NumRegs; ++i) { 05689 ISD::InputArg MyFlags; 05690 MyFlags.VT = RegisterVT; 05691 MyFlags.Used = isReturnValueUsed; 05692 if (RetSExt) 05693 MyFlags.Flags.setSExt(); 05694 if (RetZExt) 05695 MyFlags.Flags.setZExt(); 05696 if (isInreg) 05697 MyFlags.Flags.setInReg(); 05698 Ins.push_back(MyFlags); 05699 } 05700 } 05701 05702 // Check if target-dependent constraints permit a tail call here. 05703 // Target-independent constraints should be checked by the caller. 05704 if (isTailCall && 05705 !IsEligibleForTailCallOptimization(Callee, CallConv, isVarArg, Ins, DAG)) 05706 isTailCall = false; 05707 05708 SmallVector<SDValue, 4> InVals; 05709 Chain = LowerCall(Chain, Callee, CallConv, isVarArg, isTailCall, 05710 Outs, Ins, dl, DAG, InVals); 05711 05712 // Verify that the target's LowerCall behaved as expected. 05713 assert(Chain.getNode() && Chain.getValueType() == MVT::Other && 05714 "LowerCall didn't return a valid chain!"); 05715 assert((!isTailCall || InVals.empty()) && 05716 "LowerCall emitted a return value for a tail call!"); 05717 assert((isTailCall || InVals.size() == Ins.size()) && 05718 "LowerCall didn't emit the correct number of values!"); 05719 DEBUG(for (unsigned i = 0, e = Ins.size(); i != e; ++i) { 05720 assert(InVals[i].getNode() && 05721 "LowerCall emitted a null value!"); 05722 assert(Ins[i].VT == InVals[i].getValueType() && 05723 "LowerCall emitted a value with the wrong type!"); 05724 }); 05725 05726 // For a tail call, the return value is merely live-out and there aren't 05727 // any nodes in the DAG representing it. Return a special value to 05728 // indicate that a tail call has been emitted and no more Instructions 05729 // should be processed in the current block. 05730 if (isTailCall) { 05731 DAG.setRoot(Chain); 05732 return std::make_pair(SDValue(), SDValue()); 05733 } 05734 05735 // Collect the legal value parts into potentially illegal values 05736 // that correspond to the original function's return values. 05737 ISD::NodeType AssertOp = ISD::DELETED_NODE; 05738 if (RetSExt) 05739 AssertOp = ISD::AssertSext; 05740 else if (RetZExt) 05741 AssertOp = ISD::AssertZext; 05742 SmallVector<SDValue, 4> ReturnValues; 05743 unsigned CurReg = 0; 05744 for (unsigned I = 0, E = RetTys.size(); I != E; ++I) { 05745 EVT VT = RetTys[I]; 05746 EVT RegisterVT = getRegisterType(RetTy->getContext(), VT); 05747 unsigned NumRegs = getNumRegisters(RetTy->getContext(), VT); 05748 05749 SDValue ReturnValue = 05750 getCopyFromParts(DAG, dl, &InVals[CurReg], NumRegs, RegisterVT, VT, 05751 AssertOp); 05752 ReturnValues.push_back(ReturnValue); 05753 CurReg += NumRegs; 05754 } 05755 05756 // For a function returning void, there is no return value. We can't create 05757 // such a node, so we just return a null return value in that case. In 05758 // that case, nothing will actualy look at the value. 05759 if (ReturnValues.empty()) 05760 return std::make_pair(SDValue(), Chain); 05761 05762 SDValue Res = DAG.getNode(ISD::MERGE_VALUES, dl, 05763 DAG.getVTList(&RetTys[0], RetTys.size()), 05764 &ReturnValues[0], ReturnValues.size()); 05765 05766 return std::make_pair(Res, Chain); 05767 } 05768 05769 void TargetLowering::LowerOperationWrapper(SDNode *N, 05770 SmallVectorImpl<SDValue> &Results, 05771 SelectionDAG &DAG) { 05772 SDValue Res = LowerOperation(SDValue(N, 0), DAG); 05773 if (Res.getNode()) 05774 Results.push_back(Res); 05775 } 05776 05777 SDValue TargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) { 05778 llvm_unreachable("LowerOperation not implemented for this target!"); 05779 return SDValue(); 05780 } 05781 05782 05783 void SelectionDAGLowering::CopyValueToVirtualRegister(Value *V, unsigned Reg) { 05784 SDValue Op = getValue(V); 05785 assert((Op.getOpcode() != ISD::CopyFromReg || 05786 cast<RegisterSDNode>(Op.getOperand(1))->getReg() != Reg) && 05787 "Copy from a reg to the same reg!"); 05788 assert(!TargetRegisterInfo::isPhysicalRegister(Reg) && "Is a physreg"); 05789 05790 RegsForValue RFV(V->getContext(), TLI, Reg, V->getType()); 05791 SDValue Chain = DAG.getEntryNode(); 05792 RFV.getCopyToRegs(Op, DAG, getCurDebugLoc(), Chain, 0); 05793 PendingExports.push_back(Chain); 05794 } 05795 05796 #include "llvm/CodeGen/SelectionDAGISel.h" 05797 05798 void SelectionDAGISel:: 05799 LowerArguments(BasicBlock *LLVMBB) { 05800 // If this is the entry block, emit arguments. 05801 Function &F = *LLVMBB->getParent(); 05802 SelectionDAG &DAG = SDL->DAG; 05803 SDValue OldRoot = DAG.getRoot(); 05804 DebugLoc dl = SDL->getCurDebugLoc(); 05805 const TargetData *TD = TLI.getTargetData(); 05806 05807 // Set up the incoming argument description vector. 05808 SmallVector<ISD::InputArg, 16> Ins; 05809 unsigned Idx = 1; 05810 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); 05811 I != E; ++I, ++Idx) { 05812 SmallVector<EVT, 4> ValueVTs; 05813 ComputeValueVTs(TLI, I->getType(), ValueVTs); 05814 bool isArgValueUsed = !I->use_empty(); 05815 for (unsigned Value = 0, NumValues = ValueVTs.size(); 05816 Value != NumValues; ++Value) { 05817 EVT VT = ValueVTs[Value]; 05818 const Type *ArgTy = VT.getTypeForEVT(*DAG.getContext()); 05819 ISD::ArgFlagsTy Flags; 05820 unsigned OriginalAlignment = 05821 TD->getABITypeAlignment(ArgTy); 05822 05823 if (F.paramHasAttr(Idx, Attribute::ZExt)) 05824 Flags.setZExt(); 05825 if (F.paramHasAttr(Idx, Attribute::SExt)) 05826 Flags.setSExt(); 05827 if (F.paramHasAttr(Idx, Attribute::InReg)) 05828 Flags.setInReg(); 05829 if (F.paramHasAttr(Idx, Attribute::StructRet)) 05830 Flags.setSRet(); 05831 if (F.paramHasAttr(Idx, Attribute::ByVal)) { 05832 Flags.setByVal(); 05833 const PointerType *Ty = cast<PointerType>(I->getType()); 05834 const Type *ElementTy = Ty->getElementType(); 05835 unsigned FrameAlign = TLI.getByValTypeAlignment(ElementTy); 05836 unsigned FrameSize = TD->getTypeAllocSize(ElementTy); 05837 // For ByVal, alignment should be passed from FE. BE will guess if 05838 // this info is not there but there are cases it cannot get right. 05839 if (F.getParamAlignment(Idx)) 05840 FrameAlign = F.getParamAlignment(Idx); 05841 Flags.setByValAlign(FrameAlign); 05842 Flags.setByValSize(FrameSize); 05843 } 05844 if (F.paramHasAttr(Idx, Attribute::Nest)) 05845 Flags.setNest(); 05846 Flags.setOrigAlign(OriginalAlignment); 05847 05848 EVT RegisterVT = TLI.getRegisterType(*CurDAG->getContext(), VT); 05849 unsigned NumRegs = TLI.getNumRegisters(*CurDAG->getContext(), VT); 05850 for (unsigned i = 0; i != NumRegs; ++i) { 05851 ISD::InputArg MyFlags(Flags, RegisterVT, isArgValueUsed); 05852 if (NumRegs > 1 && i == 0) 05853 MyFlags.Flags.setSplit(); 05854 // if it isn't first piece, alignment must be 1 05855 else if (i > 0) 05856 MyFlags.Flags.setOrigAlign(1); 05857 Ins.push_back(MyFlags); 05858 } 05859 } 05860 } 05861 05862 // Call the target to set up the argument values. 05863 SmallVector<SDValue, 8> InVals; 05864 SDValue NewRoot = TLI.LowerFormalArguments(DAG.getRoot(), F.getCallingConv(), 05865 F.isVarArg(), Ins, 05866 dl, DAG, InVals); 05867 05868 // Verify that the target's LowerFormalArguments behaved as expected. 05869 assert(NewRoot.getNode() && NewRoot.getValueType() == MVT::Other && 05870 "LowerFormalArguments didn't return a valid chain!"); 05871 assert(InVals.size() == Ins.size() && 05872 "LowerFormalArguments didn't emit the correct number of values!"); 05873 DEBUG(for (unsigned i = 0, e = Ins.size(); i != e; ++i) { 05874 assert(InVals[i].getNode() && 05875 "LowerFormalArguments emitted a null value!"); 05876 assert(Ins[i].VT == InVals[i].getValueType() && 05877 "LowerFormalArguments emitted a value with the wrong type!"); 05878 }); 05879 05880 // Update the DAG with the new chain value resulting from argument lowering. 05881 DAG.setRoot(NewRoot); 05882 05883 // Set up the argument values. 05884 unsigned i = 0; 05885 Idx = 1; 05886 for (Function::arg_iterator I = F.arg_begin(), E = F.arg_end(); I != E; 05887 ++I, ++Idx) { 05888 SmallVector<SDValue, 4> ArgValues; 05889 SmallVector<EVT, 4> ValueVTs; 05890 ComputeValueVTs(TLI, I->getType(), ValueVTs); 05891 unsigned NumValues = ValueVTs.size(); 05892 for (unsigned Value = 0; Value != NumValues; ++Value) { 05893 EVT VT = ValueVTs[Value]; 05894 EVT PartVT = TLI.getRegisterType(*CurDAG->getContext(), VT); 05895 unsigned NumParts = TLI.getNumRegisters(*CurDAG->getContext(), VT); 05896 05897 if (!I->use_empty()) { 05898 ISD::NodeType AssertOp = ISD::DELETED_NODE; 05899 if (F.paramHasAttr(Idx, Attribute::SExt)) 05900 AssertOp = ISD::AssertSext; 05901 else if (F.paramHasAttr(Idx, Attribute::ZExt)) 05902 AssertOp = ISD::AssertZext; 05903 05904 ArgValues.push_back(getCopyFromParts(DAG, dl, &InVals[i], NumParts, 05905 PartVT, VT, AssertOp)); 05906 } 05907 i += NumParts; 05908 } 05909 if (!I->use_empty()) { 05910 SDL->setValue(I, DAG.getMergeValues(&ArgValues[0], NumValues, 05911 SDL->getCurDebugLoc())); 05912 // If this argument is live outside of the entry block, insert a copy from 05913 // whereever we got it to the vreg that other BB's will reference it as. 05914 SDL->CopyToExportRegsIfNeeded(I); 05915 } 05916 } 05917 assert(i == InVals.size() && "Argument register count mismatch!"); 05918 05919 // Finally, if the target has anything special to do, allow it to do so. 05920 // FIXME: this should insert code into the DAG! 05921 EmitFunctionEntryCode(F, SDL->DAG.getMachineFunction()); 05922 } 05923 05924 /// Handle PHI nodes in successor blocks. Emit code into the SelectionDAG to 05925 /// ensure constants are generated when needed. Remember the virtual registers 05926 /// that need to be added to the Machine PHI nodes as input. We cannot just 05927 /// directly add them, because expansion might result in multiple MBB's for one 05928 /// BB. As such, the start of the BB might correspond to a different MBB than 05929 /// the end. 05930 /// 05931 void 05932 SelectionDAGISel::HandlePHINodesInSuccessorBlocks(BasicBlock *LLVMBB) { 05933 TerminatorInst *TI = LLVMBB->getTerminator(); 05934 05935 SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled; 05936 05937 // Check successor nodes' PHI nodes that expect a constant to be available 05938 // from this block. 05939 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { 05940 BasicBlock *SuccBB = TI->getSuccessor(succ); 05941 if (!isa<PHINode>(SuccBB->begin())) continue; 05942 MachineBasicBlock *SuccMBB = FuncInfo->MBBMap[SuccBB]; 05943 05944 // If this terminator has multiple identical successors (common for 05945 // switches), only handle each succ once. 05946 if (!SuccsHandled.insert(SuccMBB)) continue; 05947 05948 MachineBasicBlock::iterator MBBI = SuccMBB->begin(); 05949 PHINode *PN; 05950 05951 // At this point we know that there is a 1-1 correspondence between LLVM PHI 05952 // nodes and Machine PHI nodes, but the incoming operands have not been 05953 // emitted yet. 05954 for (BasicBlock::iterator I = SuccBB->begin(); 05955 (PN = dyn_cast<PHINode>(I)); ++I) { 05956 // Ignore dead phi's. 05957 if (PN->use_empty()) continue; 05958 05959 unsigned Reg; 05960 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 05961 05962 if (Constant *C = dyn_cast<Constant>(PHIOp)) { 05963 unsigned &RegOut = SDL->ConstantsOut[C]; 05964 if (RegOut == 0) { 05965 RegOut = FuncInfo->CreateRegForValue(C); 05966 SDL->CopyValueToVirtualRegister(C, RegOut); 05967 } 05968 Reg = RegOut; 05969 } else { 05970 Reg = FuncInfo->ValueMap[PHIOp]; 05971 if (Reg == 0) { 05972 assert(isa<AllocaInst>(PHIOp) && 05973 FuncInfo->StaticAllocaMap.count(cast<AllocaInst>(PHIOp)) && 05974 "Didn't codegen value into a register!??"); 05975 Reg = FuncInfo->CreateRegForValue(PHIOp); 05976 SDL->CopyValueToVirtualRegister(PHIOp, Reg); 05977 } 05978 } 05979 05980 // Remember that this register needs to added to the machine PHI node as 05981 // the input for this MBB. 05982 SmallVector<EVT, 4> ValueVTs; 05983 ComputeValueVTs(TLI, PN->getType(), ValueVTs); 05984 for (unsigned vti = 0, vte = ValueVTs.size(); vti != vte; ++vti) { 05985 EVT VT = ValueVTs[vti]; 05986 unsigned NumRegisters = TLI.getNumRegisters(*CurDAG->getContext(), VT); 05987 for (unsigned i = 0, e = NumRegisters; i != e; ++i) 05988 SDL->PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg+i)); 05989 Reg += NumRegisters; 05990 } 05991 } 05992 } 05993 SDL->ConstantsOut.clear(); 05994 } 05995 05996 /// This is the Fast-ISel version of HandlePHINodesInSuccessorBlocks. It only 05997 /// supports legal types, and it emits MachineInstrs directly instead of 05998 /// creating SelectionDAG nodes. 05999 /// 06000 bool 06001 SelectionDAGISel::HandlePHINodesInSuccessorBlocksFast(BasicBlock *LLVMBB, 06002 FastISel *F) { 06003 TerminatorInst *TI = LLVMBB->getTerminator(); 06004 06005 SmallPtrSet<MachineBasicBlock *, 4> SuccsHandled; 06006 unsigned OrigNumPHINodesToUpdate = SDL->PHINodesToUpdate.size(); 06007 06008 // Check successor nodes' PHI nodes that expect a constant to be available 06009 // from this block. 06010 for (unsigned succ = 0, e = TI->getNumSuccessors(); succ != e; ++succ) { 06011 BasicBlock *SuccBB = TI->getSuccessor(succ); 06012 if (!isa<PHINode>(SuccBB->begin())) continue; 06013 MachineBasicBlock *SuccMBB = FuncInfo->MBBMap[SuccBB]; 06014 06015 // If this terminator has multiple identical successors (common for 06016 // switches), only handle each succ once. 06017 if (!SuccsHandled.insert(SuccMBB)) continue; 06018 06019 MachineBasicBlock::iterator MBBI = SuccMBB->begin(); 06020 PHINode *PN; 06021 06022 // At this point we know that there is a 1-1 correspondence between LLVM PHI 06023 // nodes and Machine PHI nodes, but the incoming operands have not been 06024 // emitted yet. 06025 for (BasicBlock::iterator I = SuccBB->begin(); 06026 (PN = dyn_cast<PHINode>(I)); ++I) { 06027 // Ignore dead phi's. 06028 if (PN->use_empty()) continue; 06029 06030 // Only handle legal types. Two interesting things to note here. First, 06031 // by bailing out early, we may leave behind some dead instructions, 06032 // since SelectionDAG's HandlePHINodesInSuccessorBlocks will insert its 06033 // own moves. Second, this check is necessary becuase FastISel doesn't 06034 // use CreateRegForValue to create registers, so it always creates 06035 // exactly one register for each non-void instruction. 06036 EVT VT = TLI.getValueType(PN->getType(), /*AllowUnknown=*/true); 06037 if (VT == MVT::Other || !TLI.isTypeLegal(VT)) { 06038 // Promote MVT::i1. 06039 if (VT == MVT::i1) 06040 VT = TLI.getTypeToTransformTo(*CurDAG->getContext(), VT); 06041 else { 06042 SDL->PHINodesToUpdate.resize(OrigNumPHINodesToUpdate); 06043 return false; 06044 } 06045 } 06046 06047 Value *PHIOp = PN->getIncomingValueForBlock(LLVMBB); 06048 06049 unsigned Reg = F->getRegForValue(PHIOp); 06050 if (Reg == 0) { 06051 SDL->PHINodesToUpdate.resize(OrigNumPHINodesToUpdate); 06052 return false; 06053 } 06054 SDL->PHINodesToUpdate.push_back(std::make_pair(MBBI++, Reg)); 06055 } 06056 } 06057 06058 return true; 06059 }