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 /// Test if the given instruction is in a position to be optimized 207 /// with a tail-call. This roughly means that it's in a block with 208 /// a return and there's nothing that needs to be scheduled 209 /// between it and the return. 210 /// 211 /// This function only tests target-independent requirements. 212 bool llvm::isInTailCallPosition(ImmutableCallSite CS, Attributes CalleeRetAttr, 213 const TargetLowering &TLI) { 214 const Instruction *I = CS.getInstruction(); 215 const BasicBlock *ExitBB = I->getParent(); 216 const TerminatorInst *Term = ExitBB->getTerminator(); 217 const ReturnInst *Ret = dyn_cast<ReturnInst>(Term); 218 219 // The block must end in a return statement or unreachable. 220 // 221 // FIXME: Decline tailcall if it's not guaranteed and if the block ends in 222 // an unreachable, for now. The way tailcall optimization is currently 223 // implemented means it will add an epilogue followed by a jump. That is 224 // not profitable. Also, if the callee is a special function (e.g. 225 // longjmp on x86), it can end up causing miscompilation that has not 226 // been fully understood. 227 if (!Ret && 228 (!TLI.getTargetMachine().Options.GuaranteedTailCallOpt || 229 !isa<UnreachableInst>(Term))) return false; 230 231 // If I will have a chain, make sure no other instruction that will have a 232 // chain interposes between I and the return. 233 if (I->mayHaveSideEffects() || I->mayReadFromMemory() || 234 !isSafeToSpeculativelyExecute(I)) 235 for (BasicBlock::const_iterator BBI = prior(prior(ExitBB->end())); ; 236 --BBI) { 237 if (&*BBI == I) 238 break; 239 // Debug info intrinsics do not get in the way of tail call optimization. 240 if (isa<DbgInfoIntrinsic>(BBI)) 241 continue; 242 if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() || 243 !isSafeToSpeculativelyExecute(BBI)) 244 return false; 245 } 246 247 // If the block ends with a void return or unreachable, it doesn't matter 248 // what the call's return type is. 249 if (!Ret || Ret->getNumOperands() == 0) return true; 250 251 // If the return value is undef, it doesn't matter what the call's 252 // return type is. 253 if (isa<UndefValue>(Ret->getOperand(0))) return true; 254 255 // Conservatively require the attributes of the call to match those of 256 // the return. Ignore noalias because it doesn't affect the call sequence. 257 const Function *F = ExitBB->getParent(); 258 Attributes CallerRetAttr = F->getAttributes().getRetAttributes(); 259 if ((CalleeRetAttr ^ CallerRetAttr) & ~Attribute::NoAlias) 260 return false; 261 262 // It's not safe to eliminate the sign / zero extension of the return value. 263 if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt)) 264 return false; 265 266 // Otherwise, make sure the unmodified return value of I is the return value. 267 for (const Instruction *U = dyn_cast<Instruction>(Ret->getOperand(0)); ; 268 U = dyn_cast<Instruction>(U->getOperand(0))) { 269 if (!U) 270 return false; 271 if (!U->hasOneUse()) 272 return false; 273 if (U == I) 274 break; 275 // Check for a truly no-op truncate. 276 if (isa<TruncInst>(U) && 277 TLI.isTruncateFree(U->getOperand(0)->getType(), U->getType())) 278 continue; 279 // Check for a truly no-op bitcast. 280 if (isa<BitCastInst>(U) && 281 (U->getOperand(0)->getType() == U->getType() || 282 (U->getOperand(0)->getType()->isPointerTy() && 283 U->getType()->isPointerTy()))) 284 continue; 285 // Otherwise it's not a true no-op. 286 return false; 287 } 288 289 return true; 290 } 291 292 bool llvm::isInTailCallPosition(SelectionDAG &DAG, SDNode *Node, 293 SDValue &Chain, const TargetLowering &TLI) { 294 const Function *F = DAG.getMachineFunction().getFunction(); 295 296 // Conservatively require the attributes of the call to match those of 297 // the return. Ignore noalias because it doesn't affect the call sequence. 298 Attributes CallerRetAttr = F->getAttributes().getRetAttributes(); 299 if (CallerRetAttr & ~Attribute::NoAlias) 300 return false; 301 302 // It's not safe to eliminate the sign / zero extension of the return value. 303 if ((CallerRetAttr & Attribute::ZExt) || (CallerRetAttr & Attribute::SExt)) 304 return false; 305 306 // Check if the only use is a function return node. 307 return TLI.isUsedByReturnOnly(Node, Chain); 308 } 309
