1 //===-- Analysis.cpp - CodeGen LLVM IR Analysis Utilities -----------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines several CodeGen-specific LLVM IR analysis utilties. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/Analysis.h" 15 #include "llvm/Analysis/ValueTracking.h" 16 #include "llvm/DerivedTypes.h" 17 #include "llvm/Function.h" 18 #include "llvm/Instructions.h" 19 #include "llvm/IntrinsicInst.h" 20 #include "llvm/LLVMContext.h" 21 #include "llvm/Module.h" 22 #include "llvm/CodeGen/MachineFunction.h" 23 #include "llvm/CodeGen/SelectionDAG.h" 24 #include "llvm/Target/TargetData.h" 25 #include "llvm/Target/TargetLowering.h" 26 #include "llvm/Target/TargetOptions.h" 27 #include "llvm/Support/ErrorHandling.h" 28 #include "llvm/Support/MathExtras.h" 29 using namespace llvm; 30 31 /// ComputeLinearIndex - Given an LLVM IR aggregate type and a sequence 32 /// of insertvalue or extractvalue indices that identify a member, return 33 /// the linearized index of the start of the member. 34 /// 35 unsigned llvm::ComputeLinearIndex(Type *Ty, 36 const unsigned *Indices, 37 const unsigned *IndicesEnd, 38 unsigned CurIndex) { 39 // Base case: We're done. 40 if (Indices && Indices == IndicesEnd) 41 return CurIndex; 42 43 // Given a struct type, recursively traverse the elements. 44 if (StructType *STy = dyn_cast<StructType>(Ty)) { 45 for (StructType::element_iterator EB = STy->element_begin(), 46 EI = EB, 47 EE = STy->element_end(); 48 EI != EE; ++EI) { 49 if (Indices && *Indices == unsigned(EI - EB)) 50 return ComputeLinearIndex(*EI, Indices+1, IndicesEnd, CurIndex); 51 CurIndex = ComputeLinearIndex(*EI, 0, 0, CurIndex); 52 } 53 return CurIndex; 54 } 55 // Given an array type, recursively traverse the elements. 56 else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 57 Type *EltTy = ATy->getElementType(); 58 for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) { 59 if (Indices && *Indices == i) 60 return ComputeLinearIndex(EltTy, Indices+1, IndicesEnd, CurIndex); 61 CurIndex = ComputeLinearIndex(EltTy, 0, 0, CurIndex); 62 } 63 return CurIndex; 64 } 65 // We haven't found the type we're looking for, so keep searching. 66 return CurIndex + 1; 67 } 68 69 /// ComputeValueVTs - Given an LLVM IR type, compute a sequence of 70 /// EVTs that represent all the individual underlying 71 /// non-aggregate types that comprise it. 72 /// 73 /// If Offsets is non-null, it points to a vector to be filled in 74 /// with the in-memory offsets of each of the individual values. 75 /// 76 void llvm::ComputeValueVTs(const TargetLowering &TLI, Type *Ty, 77 SmallVectorImpl<EVT> &ValueVTs, 78 SmallVectorImpl<uint64_t> *Offsets, 79 uint64_t StartingOffset) { 80 // Given a struct type, recursively traverse the elements. 81 if (StructType *STy = dyn_cast<StructType>(Ty)) { 82 const StructLayout *SL = TLI.getTargetData()->getStructLayout(STy); 83 for (StructType::element_iterator EB = STy->element_begin(), 84 EI = EB, 85 EE = STy->element_end(); 86 EI != EE; ++EI) 87 ComputeValueVTs(TLI, *EI, ValueVTs, Offsets, 88 StartingOffset + SL->getElementOffset(EI - EB)); 89 return; 90 } 91 // Given an array type, recursively traverse the elements. 92 if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 93 Type *EltTy = ATy->getElementType(); 94 uint64_t EltSize = TLI.getTargetData()->getTypeAllocSize(EltTy); 95 for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) 96 ComputeValueVTs(TLI, EltTy, ValueVTs, Offsets, 97 StartingOffset + i * EltSize); 98 return; 99 } 100 // Interpret void as zero return values. 101 if (Ty->isVoidTy()) 102 return; 103 // Base case: we can get an EVT for this LLVM IR type. 104 ValueVTs.push_back(TLI.getValueType(Ty)); 105 if (Offsets) 106 Offsets->push_back(StartingOffset); 107 } 108 109 /// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V. 110 GlobalVariable *llvm::ExtractTypeInfo(Value *V) { 111 V = V->stripPointerCasts(); 112 GlobalVariable *GV = dyn_cast<GlobalVariable>(V); 113 114 if (GV && GV->getName() == "llvm.eh.catch.all.value") { 115 assert(GV->hasInitializer() && 116 "The EH catch-all value must have an initializer"); 117 Value *Init = GV->getInitializer(); 118 GV = dyn_cast<GlobalVariable>(Init); 119 if (!GV) V = cast<ConstantPointerNull>(Init); 120 } 121 122 assert((GV || isa<ConstantPointerNull>(V)) && 123 "TypeInfo must be a global variable or NULL"); 124 return GV; 125 } 126 127 /// hasInlineAsmMemConstraint - Return true if the inline asm instruction being 128 /// processed uses a memory 'm' constraint. 129 bool 130 llvm::hasInlineAsmMemConstraint(InlineAsm::ConstraintInfoVector &CInfos, 131 const TargetLowering &TLI) { 132 for (unsigned i = 0, e = CInfos.size(); i != e; ++i) { 133 InlineAsm::ConstraintInfo &CI = CInfos[i]; 134 for (unsigned j = 0, ee = CI.Codes.size(); j != ee; ++j) { 135 TargetLowering::ConstraintType CType = TLI.getConstraintType(CI.Codes[j]); 136 if (CType == TargetLowering::C_Memory) 137 return true; 138 } 139 140 // Indirect operand accesses access memory. 141 if (CI.isIndirect) 142 return true; 143 } 144 145 return false; 146 } 147 148 /// getFCmpCondCode - Return the ISD condition code corresponding to 149 /// the given LLVM IR floating-point condition code. This includes 150 /// consideration of global floating-point math flags. 151 /// 152 ISD::CondCode llvm::getFCmpCondCode(FCmpInst::Predicate Pred) { 153 switch (Pred) { 154 case FCmpInst::FCMP_FALSE: return ISD::SETFALSE; 155 case FCmpInst::FCMP_OEQ: return ISD::SETOEQ; 156 case FCmpInst::FCMP_OGT: return ISD::SETOGT; 157 case FCmpInst::FCMP_OGE: return ISD::SETOGE; 158 case FCmpInst::FCMP_OLT: return ISD::SETOLT; 159 case FCmpInst::FCMP_OLE: return ISD::SETOLE; 160 case FCmpInst::FCMP_ONE: return ISD::SETONE; 161 case FCmpInst::FCMP_ORD: return ISD::SETO; 162 case FCmpInst::FCMP_UNO: return ISD::SETUO; 163 case FCmpInst::FCMP_UEQ: return ISD::SETUEQ; 164 case FCmpInst::FCMP_UGT: return ISD::SETUGT; 165 case FCmpInst::FCMP_UGE: return ISD::SETUGE; 166 case FCmpInst::FCMP_ULT: return ISD::SETULT; 167 case FCmpInst::FCMP_ULE: return ISD::SETULE; 168 case FCmpInst::FCMP_UNE: return ISD::SETUNE; 169 case FCmpInst::FCMP_TRUE: return ISD::SETTRUE; 170 default: llvm_unreachable("Invalid FCmp predicate opcode!"); 171 } 172 } 173 174 ISD::CondCode llvm::getFCmpCodeWithoutNaN(ISD::CondCode CC) { 175 switch (CC) { 176 case ISD::SETOEQ: case ISD::SETUEQ: return ISD::SETEQ; 177 case ISD::SETONE: case ISD::SETUNE: return ISD::SETNE; 178 case ISD::SETOLT: case ISD::SETULT: return ISD::SETLT; 179 case ISD::SETOLE: case ISD::SETULE: return ISD::SETLE; 180 case ISD::SETOGT: case ISD::SETUGT: return ISD::SETGT; 181 case ISD::SETOGE: case ISD::SETUGE: return ISD::SETGE; 182 default: return CC; 183 } 184 } 185 186 /// getICmpCondCode - Return the ISD condition code corresponding to 187 /// the given LLVM IR integer condition code. 188 /// 189 ISD::CondCode llvm::getICmpCondCode(ICmpInst::Predicate Pred) { 190 switch (Pred) { 191 case ICmpInst::ICMP_EQ: return ISD::SETEQ; 192 case ICmpInst::ICMP_NE: return ISD::SETNE; 193 case ICmpInst::ICMP_SLE: return ISD::SETLE; 194 case ICmpInst::ICMP_ULE: return ISD::SETULE; 195 case ICmpInst::ICMP_SGE: return ISD::SETGE; 196 case ICmpInst::ICMP_UGE: return ISD::SETUGE; 197 case ICmpInst::ICMP_SLT: return ISD::SETLT; 198 case ICmpInst::ICMP_ULT: return ISD::SETULT; 199 case ICmpInst::ICMP_SGT: return ISD::SETGT; 200 case ICmpInst::ICMP_UGT: return ISD::SETUGT; 201 default: 202 llvm_unreachable("Invalid ICmp predicate opcode!"); 203 } 204 } 205 206 207 /// getNoopInput - If V is a noop (i.e., lowers to no machine code), look 208 /// through it (and any transitive noop operands to it) and return its input 209 /// value. This is used to determine if a tail call can be formed. 210 /// 211 static const Value *getNoopInput(const Value *V, const TargetLowering &TLI) { 212 // If V is not an instruction, it can't be looked through. 213 const Instruction *I = dyn_cast<Instruction>(V); 214 if (I == 0 || !I->hasOneUse() || I->getNumOperands() == 0) return V; 215 216 Value *Op = I->getOperand(0); 217 218 // Look through truly no-op truncates. 219 if (isa<TruncInst>(I) && 220 TLI.isTruncateFree(I->getOperand(0)->getType(), I->getType())) 221 return getNoopInput(I->getOperand(0), TLI); 222 223 // Look through truly no-op bitcasts. 224 if (isa<BitCastInst>(I)) { 225 // No type change at all. 226 if (Op->getType() == I->getType()) 227 return getNoopInput(Op, TLI); 228 229 // Pointer to pointer cast. 230 if (Op->getType()->isPointerTy() && I->getType()->isPointerTy()) 231 return getNoopInput(Op, TLI); 232 233 if (isa<VectorType>(Op->getType()) && isa<VectorType>(I->getType()) && 234 TLI.isTypeLegal(EVT::getEVT(Op->getType())) && 235 TLI.isTypeLegal(EVT::getEVT(I->getType()))) 236 return getNoopInput(Op, TLI); 237 } 238 239 // Look through inttoptr. 240 if (isa<IntToPtrInst>(I) && !isa<VectorType>(I->getType())) { 241 // Make sure this isn't a truncating or extending cast. We could support 242 // this eventually, but don't bother for now. 243 if (TLI.getPointerTy().getSizeInBits() == 244 cast<IntegerType>(Op->getType())->getBitWidth()) 245 return getNoopInput(Op, TLI); 246 } 247 248 // Look through ptrtoint. 249 if (isa<PtrToIntInst>(I) && !isa<VectorType>(I->getType())) { 250 // Make sure this isn't a truncating or extending cast. We could support 251 // this eventually, but don't bother for now. 252 if (TLI.getPointerTy().getSizeInBits() == 253 cast<IntegerType>(I->getType())->getBitWidth()) 254 return getNoopInput(Op, TLI); 255 } 256 257 258 // Otherwise it's not something we can look through. 259 return V; 260 } 261 262 263 /// Test if the given instruction is in a position to be optimized 264 /// with a tail-call. This roughly means that it's in a block with 265 /// a return and there's nothing that needs to be scheduled 266 /// between it and the return. 267 /// 268 /// This function only tests target-independent requirements. 269 bool llvm::isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr, 270 const TargetLowering &TLI) { 271 const Instruction *I = CS.getInstruction(); 272 const BasicBlock *ExitBB = I->getParent(); 273 const TerminatorInst *Term = ExitBB->getTerminator(); 274 const ReturnInst *Ret = dyn_cast<ReturnInst>(Term); 275 276 // The block must end in a return statement or unreachable. 277 // 278 // FIXME: Decline tailcall if it's not guaranteed and if the block ends in 279 // an unreachable, for now. The way tailcall optimization is currently 280 // implemented means it will add an epilogue followed by a jump. That is 281 // not profitable. Also, if the callee is a special function (e.g. 282 // longjmp on x86), it can end up causing miscompilation that has not 283 // been fully understood. 284 if (!Ret && 285 (!TLI.getTargetMachine().Options.GuaranteedTailCallOpt || 286 !isa<UnreachableInst>(Term))) 287 return false; 288 289 // If I will have a chain, make sure no other instruction that will have a 290 // chain interposes between I and the return. 291 if (I->mayHaveSideEffects() || I->mayReadFromMemory() || 292 !isSafeToSpeculativelyExecute(I)) 293 for (BasicBlock::const_iterator BBI = prior(prior(ExitBB->end())); ; 294 --BBI) { 295 if (&*BBI == I) 296 break; 297 // Debug info intrinsics do not get in the way of tail call optimization. 298 if (isa<DbgInfoIntrinsic>(BBI)) 299 continue; 300 if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() || 301 !isSafeToSpeculativelyExecute(BBI)) 302 return false; 303 } 304 305 // If the block ends with a void return or unreachable, it doesn't matter 306 // what the call's return type is. 307 if (!Ret || Ret->getNumOperands() == 0) return true; 308 309 // If the return value is undef, it doesn't matter what the call's 310 // return type is. 311 if (isa<UndefValue>(Ret->getOperand(0))) return true; 312 313 // Conservatively require the attributes of the call to match those of 314 // the return. Ignore noalias because it doesn't affect the call sequence. 315 const Function *F = ExitBB->getParent(); 316 Attributes CallerRetAttr = F->getAttributes().getRetAttributes(); 317 if ((CalleeRetAttr ^ CallerRetAttr) & ~Attribute::NoAlias) 318 return false; 319 320 // It's not safe to eliminate the sign / zero extension of the return value. 321 if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt)) 322 return false; 323 324 // Otherwise, make sure the unmodified return value of I is the return value. 325 // We handle two cases: multiple return values + scalars. 326 Value *RetVal = Ret->getOperand(0); 327 if (!isa<InsertValueInst>(RetVal) || !isa<StructType>(RetVal->getType())) 328 // Handle scalars first. 329 return getNoopInput(Ret->getOperand(0), TLI) == I; 330 331 // If this is an aggregate return, look through the insert/extract values and 332 // see if each is transparent. 333 for (unsigned i = 0, e =cast<StructType>(RetVal->getType())->getNumElements(); 334 i != e; ++i) { 335 const Value *InScalar = FindInsertedValue(RetVal, i); 336 if (InScalar == 0) return false; 337 InScalar = getNoopInput(InScalar, TLI); 338 339 // If the scalar value being inserted is an extractvalue of the right index 340 // from the call, then everything is good. 341 const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(InScalar); 342 if (EVI == 0 || EVI->getOperand(0) != I || EVI->getNumIndices() != 1 || 343 EVI->getIndices()[0] != i) 344 return false; 345 } 346 347 return true; 348 } 349 350 bool llvm::isInTailCallPosition(SelectionDAG &DAG, SDNode *Node, 351 SDValue &Chain, const TargetLowering &TLI) { 352 const Function *F = DAG.getMachineFunction().getFunction(); 353 354 // Conservatively require the attributes of the call to match those of 355 // the return. Ignore noalias because it doesn't affect the call sequence. 356 Attributes CallerRetAttr = F->getAttributes().getRetAttributes(); 357 if (CallerRetAttr & ~Attribute::NoAlias) 358 return false; 359 360 // It's not safe to eliminate the sign / zero extension of the return value. 361 if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt)) 362 return false; 363 364 // Check if the only use is a function return node. 365 return TLI.isUsedByReturnOnly(Node, Chain); 366 } 367
