1234353Sdim//===-- Analysis.cpp - CodeGen LLVM IR Analysis Utilities -----------------===// 2207618Srdivacky// 3207618Srdivacky// The LLVM Compiler Infrastructure 4207618Srdivacky// 5207618Srdivacky// This file is distributed under the University of Illinois Open Source 6207618Srdivacky// License. See LICENSE.TXT for details. 7207618Srdivacky// 8207618Srdivacky//===----------------------------------------------------------------------===// 9207618Srdivacky// 10207618Srdivacky// This file defines several CodeGen-specific LLVM IR analysis utilties. 11207618Srdivacky// 12207618Srdivacky//===----------------------------------------------------------------------===// 13207618Srdivacky 14207618Srdivacky#include "llvm/CodeGen/Analysis.h" 15234353Sdim#include "llvm/Analysis/ValueTracking.h" 16207618Srdivacky#include "llvm/CodeGen/MachineFunction.h" 17249423Sdim#include "llvm/IR/DataLayout.h" 18249423Sdim#include "llvm/IR/DerivedTypes.h" 19249423Sdim#include "llvm/IR/Function.h" 20249423Sdim#include "llvm/IR/Instructions.h" 21249423Sdim#include "llvm/IR/IntrinsicInst.h" 22249423Sdim#include "llvm/IR/LLVMContext.h" 23249423Sdim#include "llvm/IR/Module.h" 24207618Srdivacky#include "llvm/Support/ErrorHandling.h" 25207618Srdivacky#include "llvm/Support/MathExtras.h" 26249423Sdim#include "llvm/Target/TargetLowering.h" 27207618Srdivackyusing namespace llvm; 28207618Srdivacky 29207618Srdivacky/// ComputeLinearIndex - Given an LLVM IR aggregate type and a sequence 30207618Srdivacky/// of insertvalue or extractvalue indices that identify a member, return 31207618Srdivacky/// the linearized index of the start of the member. 32207618Srdivacky/// 33226633Sdimunsigned llvm::ComputeLinearIndex(Type *Ty, 34207618Srdivacky const unsigned *Indices, 35207618Srdivacky const unsigned *IndicesEnd, 36207618Srdivacky unsigned CurIndex) { 37207618Srdivacky // Base case: We're done. 38207618Srdivacky if (Indices && Indices == IndicesEnd) 39207618Srdivacky return CurIndex; 40207618Srdivacky 41207618Srdivacky // Given a struct type, recursively traverse the elements. 42226633Sdim if (StructType *STy = dyn_cast<StructType>(Ty)) { 43207618Srdivacky for (StructType::element_iterator EB = STy->element_begin(), 44207618Srdivacky EI = EB, 45207618Srdivacky EE = STy->element_end(); 46207618Srdivacky EI != EE; ++EI) { 47207618Srdivacky if (Indices && *Indices == unsigned(EI - EB)) 48218893Sdim return ComputeLinearIndex(*EI, Indices+1, IndicesEnd, CurIndex); 49218893Sdim CurIndex = ComputeLinearIndex(*EI, 0, 0, CurIndex); 50207618Srdivacky } 51207618Srdivacky return CurIndex; 52207618Srdivacky } 53207618Srdivacky // Given an array type, recursively traverse the elements. 54226633Sdim else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 55226633Sdim Type *EltTy = ATy->getElementType(); 56207618Srdivacky for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) { 57207618Srdivacky if (Indices && *Indices == i) 58218893Sdim return ComputeLinearIndex(EltTy, Indices+1, IndicesEnd, CurIndex); 59218893Sdim CurIndex = ComputeLinearIndex(EltTy, 0, 0, CurIndex); 60207618Srdivacky } 61207618Srdivacky return CurIndex; 62207618Srdivacky } 63207618Srdivacky // We haven't found the type we're looking for, so keep searching. 64207618Srdivacky return CurIndex + 1; 65207618Srdivacky} 66207618Srdivacky 67207618Srdivacky/// ComputeValueVTs - Given an LLVM IR type, compute a sequence of 68207618Srdivacky/// EVTs that represent all the individual underlying 69207618Srdivacky/// non-aggregate types that comprise it. 70207618Srdivacky/// 71207618Srdivacky/// If Offsets is non-null, it points to a vector to be filled in 72207618Srdivacky/// with the in-memory offsets of each of the individual values. 73207618Srdivacky/// 74226633Sdimvoid llvm::ComputeValueVTs(const TargetLowering &TLI, Type *Ty, 75207618Srdivacky SmallVectorImpl<EVT> &ValueVTs, 76207618Srdivacky SmallVectorImpl<uint64_t> *Offsets, 77207618Srdivacky uint64_t StartingOffset) { 78207618Srdivacky // Given a struct type, recursively traverse the elements. 79226633Sdim if (StructType *STy = dyn_cast<StructType>(Ty)) { 80243830Sdim const StructLayout *SL = TLI.getDataLayout()->getStructLayout(STy); 81207618Srdivacky for (StructType::element_iterator EB = STy->element_begin(), 82207618Srdivacky EI = EB, 83207618Srdivacky EE = STy->element_end(); 84207618Srdivacky EI != EE; ++EI) 85207618Srdivacky ComputeValueVTs(TLI, *EI, ValueVTs, Offsets, 86207618Srdivacky StartingOffset + SL->getElementOffset(EI - EB)); 87207618Srdivacky return; 88207618Srdivacky } 89207618Srdivacky // Given an array type, recursively traverse the elements. 90226633Sdim if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) { 91226633Sdim Type *EltTy = ATy->getElementType(); 92243830Sdim uint64_t EltSize = TLI.getDataLayout()->getTypeAllocSize(EltTy); 93207618Srdivacky for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) 94207618Srdivacky ComputeValueVTs(TLI, EltTy, ValueVTs, Offsets, 95207618Srdivacky StartingOffset + i * EltSize); 96207618Srdivacky return; 97207618Srdivacky } 98207618Srdivacky // Interpret void as zero return values. 99207618Srdivacky if (Ty->isVoidTy()) 100207618Srdivacky return; 101207618Srdivacky // Base case: we can get an EVT for this LLVM IR type. 102207618Srdivacky ValueVTs.push_back(TLI.getValueType(Ty)); 103207618Srdivacky if (Offsets) 104207618Srdivacky Offsets->push_back(StartingOffset); 105207618Srdivacky} 106207618Srdivacky 107207618Srdivacky/// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V. 108207618SrdivackyGlobalVariable *llvm::ExtractTypeInfo(Value *V) { 109207618Srdivacky V = V->stripPointerCasts(); 110207618Srdivacky GlobalVariable *GV = dyn_cast<GlobalVariable>(V); 111207618Srdivacky 112212904Sdim if (GV && GV->getName() == "llvm.eh.catch.all.value") { 113207618Srdivacky assert(GV->hasInitializer() && 114207618Srdivacky "The EH catch-all value must have an initializer"); 115207618Srdivacky Value *Init = GV->getInitializer(); 116207618Srdivacky GV = dyn_cast<GlobalVariable>(Init); 117207618Srdivacky if (!GV) V = cast<ConstantPointerNull>(Init); 118207618Srdivacky } 119207618Srdivacky 120207618Srdivacky assert((GV || isa<ConstantPointerNull>(V)) && 121207618Srdivacky "TypeInfo must be a global variable or NULL"); 122207618Srdivacky return GV; 123207618Srdivacky} 124207618Srdivacky 125207618Srdivacky/// hasInlineAsmMemConstraint - Return true if the inline asm instruction being 126207618Srdivacky/// processed uses a memory 'm' constraint. 127207618Srdivackybool 128218893Sdimllvm::hasInlineAsmMemConstraint(InlineAsm::ConstraintInfoVector &CInfos, 129207618Srdivacky const TargetLowering &TLI) { 130207618Srdivacky for (unsigned i = 0, e = CInfos.size(); i != e; ++i) { 131207618Srdivacky InlineAsm::ConstraintInfo &CI = CInfos[i]; 132207618Srdivacky for (unsigned j = 0, ee = CI.Codes.size(); j != ee; ++j) { 133207618Srdivacky TargetLowering::ConstraintType CType = TLI.getConstraintType(CI.Codes[j]); 134207618Srdivacky if (CType == TargetLowering::C_Memory) 135207618Srdivacky return true; 136207618Srdivacky } 137207618Srdivacky 138207618Srdivacky // Indirect operand accesses access memory. 139207618Srdivacky if (CI.isIndirect) 140207618Srdivacky return true; 141207618Srdivacky } 142207618Srdivacky 143207618Srdivacky return false; 144207618Srdivacky} 145207618Srdivacky 146207618Srdivacky/// getFCmpCondCode - Return the ISD condition code corresponding to 147207618Srdivacky/// the given LLVM IR floating-point condition code. This includes 148207618Srdivacky/// consideration of global floating-point math flags. 149207618Srdivacky/// 150207618SrdivackyISD::CondCode llvm::getFCmpCondCode(FCmpInst::Predicate Pred) { 151207618Srdivacky switch (Pred) { 152234353Sdim case FCmpInst::FCMP_FALSE: return ISD::SETFALSE; 153234353Sdim case FCmpInst::FCMP_OEQ: return ISD::SETOEQ; 154234353Sdim case FCmpInst::FCMP_OGT: return ISD::SETOGT; 155234353Sdim case FCmpInst::FCMP_OGE: return ISD::SETOGE; 156234353Sdim case FCmpInst::FCMP_OLT: return ISD::SETOLT; 157234353Sdim case FCmpInst::FCMP_OLE: return ISD::SETOLE; 158234353Sdim case FCmpInst::FCMP_ONE: return ISD::SETONE; 159234353Sdim case FCmpInst::FCMP_ORD: return ISD::SETO; 160234353Sdim case FCmpInst::FCMP_UNO: return ISD::SETUO; 161234353Sdim case FCmpInst::FCMP_UEQ: return ISD::SETUEQ; 162234353Sdim case FCmpInst::FCMP_UGT: return ISD::SETUGT; 163234353Sdim case FCmpInst::FCMP_UGE: return ISD::SETUGE; 164234353Sdim case FCmpInst::FCMP_ULT: return ISD::SETULT; 165234353Sdim case FCmpInst::FCMP_ULE: return ISD::SETULE; 166234353Sdim case FCmpInst::FCMP_UNE: return ISD::SETUNE; 167234353Sdim case FCmpInst::FCMP_TRUE: return ISD::SETTRUE; 168234353Sdim default: llvm_unreachable("Invalid FCmp predicate opcode!"); 169207618Srdivacky } 170207618Srdivacky} 171207618Srdivacky 172234353SdimISD::CondCode llvm::getFCmpCodeWithoutNaN(ISD::CondCode CC) { 173234353Sdim switch (CC) { 174234353Sdim case ISD::SETOEQ: case ISD::SETUEQ: return ISD::SETEQ; 175234353Sdim case ISD::SETONE: case ISD::SETUNE: return ISD::SETNE; 176234353Sdim case ISD::SETOLT: case ISD::SETULT: return ISD::SETLT; 177234353Sdim case ISD::SETOLE: case ISD::SETULE: return ISD::SETLE; 178234353Sdim case ISD::SETOGT: case ISD::SETUGT: return ISD::SETGT; 179234353Sdim case ISD::SETOGE: case ISD::SETUGE: return ISD::SETGE; 180234353Sdim default: return CC; 181234353Sdim } 182234353Sdim} 183234353Sdim 184207618Srdivacky/// getICmpCondCode - Return the ISD condition code corresponding to 185207618Srdivacky/// the given LLVM IR integer condition code. 186207618Srdivacky/// 187207618SrdivackyISD::CondCode llvm::getICmpCondCode(ICmpInst::Predicate Pred) { 188207618Srdivacky switch (Pred) { 189207618Srdivacky case ICmpInst::ICMP_EQ: return ISD::SETEQ; 190207618Srdivacky case ICmpInst::ICMP_NE: return ISD::SETNE; 191207618Srdivacky case ICmpInst::ICMP_SLE: return ISD::SETLE; 192207618Srdivacky case ICmpInst::ICMP_ULE: return ISD::SETULE; 193207618Srdivacky case ICmpInst::ICMP_SGE: return ISD::SETGE; 194207618Srdivacky case ICmpInst::ICMP_UGE: return ISD::SETUGE; 195207618Srdivacky case ICmpInst::ICMP_SLT: return ISD::SETLT; 196207618Srdivacky case ICmpInst::ICMP_ULT: return ISD::SETULT; 197207618Srdivacky case ICmpInst::ICMP_SGT: return ISD::SETGT; 198207618Srdivacky case ICmpInst::ICMP_UGT: return ISD::SETUGT; 199207618Srdivacky default: 200207618Srdivacky llvm_unreachable("Invalid ICmp predicate opcode!"); 201207618Srdivacky } 202207618Srdivacky} 203207618Srdivacky 204251662Sdimstatic bool isNoopBitcast(Type *T1, Type *T2, 205263508Sdim const TargetLoweringBase& TLI) { 206251662Sdim return T1 == T2 || (T1->isPointerTy() && T2->isPointerTy()) || 207251662Sdim (isa<VectorType>(T1) && isa<VectorType>(T2) && 208251662Sdim TLI.isTypeLegal(EVT::getEVT(T1)) && TLI.isTypeLegal(EVT::getEVT(T2))); 209251662Sdim} 210239462Sdim 211263508Sdim/// Look through operations that will be free to find the earliest source of 212263508Sdim/// this value. 213263508Sdim/// 214263508Sdim/// @param ValLoc If V has aggegate type, we will be interested in a particular 215263508Sdim/// scalar component. This records its address; the reverse of this list gives a 216263508Sdim/// sequence of indices appropriate for an extractvalue to locate the important 217263508Sdim/// value. This value is updated during the function and on exit will indicate 218263508Sdim/// similar information for the Value returned. 219263508Sdim/// 220263508Sdim/// @param DataBits If this function looks through truncate instructions, this 221263508Sdim/// will record the smallest size attained. 222263508Sdimstatic const Value *getNoopInput(const Value *V, 223263508Sdim SmallVectorImpl<unsigned> &ValLoc, 224263508Sdim unsigned &DataBits, 225263508Sdim const TargetLoweringBase &TLI) { 226251662Sdim while (true) { 227251662Sdim // Try to look through V1; if V1 is not an instruction, it can't be looked 228251662Sdim // through. 229263508Sdim const Instruction *I = dyn_cast<Instruction>(V); 230263508Sdim if (!I || I->getNumOperands() == 0) return V; 231251662Sdim const Value *NoopInput = 0; 232263508Sdim 233263508Sdim Value *Op = I->getOperand(0); 234263508Sdim if (isa<BitCastInst>(I)) { 235263508Sdim // Look through truly no-op bitcasts. 236263508Sdim if (isNoopBitcast(Op->getType(), I->getType(), TLI)) 237263508Sdim NoopInput = Op; 238263508Sdim } else if (isa<GetElementPtrInst>(I)) { 239263508Sdim // Look through getelementptr 240263508Sdim if (cast<GetElementPtrInst>(I)->hasAllZeroIndices()) 241263508Sdim NoopInput = Op; 242263508Sdim } else if (isa<IntToPtrInst>(I)) { 243263508Sdim // Look through inttoptr. 244263508Sdim // Make sure this isn't a truncating or extending cast. We could 245263508Sdim // support this eventually, but don't bother for now. 246263508Sdim if (!isa<VectorType>(I->getType()) && 247263508Sdim TLI.getPointerTy().getSizeInBits() == 248263508Sdim cast<IntegerType>(Op->getType())->getBitWidth()) 249263508Sdim NoopInput = Op; 250263508Sdim } else if (isa<PtrToIntInst>(I)) { 251263508Sdim // Look through ptrtoint. 252263508Sdim // Make sure this isn't a truncating or extending cast. We could 253263508Sdim // support this eventually, but don't bother for now. 254263508Sdim if (!isa<VectorType>(I->getType()) && 255263508Sdim TLI.getPointerTy().getSizeInBits() == 256263508Sdim cast<IntegerType>(I->getType())->getBitWidth()) 257263508Sdim NoopInput = Op; 258263508Sdim } else if (isa<TruncInst>(I) && 259263508Sdim TLI.allowTruncateForTailCall(Op->getType(), I->getType())) { 260263508Sdim DataBits = std::min(DataBits, I->getType()->getPrimitiveSizeInBits()); 261263508Sdim NoopInput = Op; 262263508Sdim } else if (isa<CallInst>(I)) { 263263508Sdim // Look through call (skipping callee) 264263508Sdim for (User::const_op_iterator i = I->op_begin(), e = I->op_end() - 1; 265263508Sdim i != e; ++i) { 266263508Sdim unsigned attrInd = i - I->op_begin() + 1; 267263508Sdim if (cast<CallInst>(I)->paramHasAttr(attrInd, Attribute::Returned) && 268263508Sdim isNoopBitcast((*i)->getType(), I->getType(), TLI)) { 269263508Sdim NoopInput = *i; 270263508Sdim break; 271251662Sdim } 272263508Sdim } 273263508Sdim } else if (isa<InvokeInst>(I)) { 274263508Sdim // Look through invoke (skipping BB, BB, Callee) 275263508Sdim for (User::const_op_iterator i = I->op_begin(), e = I->op_end() - 3; 276263508Sdim i != e; ++i) { 277263508Sdim unsigned attrInd = i - I->op_begin() + 1; 278263508Sdim if (cast<InvokeInst>(I)->paramHasAttr(attrInd, Attribute::Returned) && 279263508Sdim isNoopBitcast((*i)->getType(), I->getType(), TLI)) { 280263508Sdim NoopInput = *i; 281263508Sdim break; 282251662Sdim } 283251662Sdim } 284263508Sdim } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(V)) { 285263508Sdim // Value may come from either the aggregate or the scalar 286263508Sdim ArrayRef<unsigned> InsertLoc = IVI->getIndices(); 287263508Sdim if (std::equal(InsertLoc.rbegin(), InsertLoc.rend(), 288263508Sdim ValLoc.rbegin())) { 289263508Sdim // The type being inserted is a nested sub-type of the aggregate; we 290263508Sdim // have to remove those initial indices to get the location we're 291263508Sdim // interested in for the operand. 292263508Sdim ValLoc.resize(ValLoc.size() - InsertLoc.size()); 293263508Sdim NoopInput = IVI->getInsertedValueOperand(); 294263508Sdim } else { 295263508Sdim // The struct we're inserting into has the value we're interested in, no 296263508Sdim // change of address. 297263508Sdim NoopInput = Op; 298263508Sdim } 299263508Sdim } else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(V)) { 300263508Sdim // The part we're interested in will inevitably be some sub-section of the 301263508Sdim // previous aggregate. Combine the two paths to obtain the true address of 302263508Sdim // our element. 303263508Sdim ArrayRef<unsigned> ExtractLoc = EVI->getIndices(); 304263508Sdim std::copy(ExtractLoc.rbegin(), ExtractLoc.rend(), 305263508Sdim std::back_inserter(ValLoc)); 306263508Sdim NoopInput = Op; 307251662Sdim } 308263508Sdim // Terminate if we couldn't find anything to look through. 309263508Sdim if (!NoopInput) 310263508Sdim return V; 311239462Sdim 312263508Sdim V = NoopInput; 313263508Sdim } 314263508Sdim} 315251662Sdim 316263508Sdim/// Return true if this scalar return value only has bits discarded on its path 317263508Sdim/// from the "tail call" to the "ret". This includes the obvious noop 318263508Sdim/// instructions handled by getNoopInput above as well as free truncations (or 319263508Sdim/// extensions prior to the call). 320263508Sdimstatic bool slotOnlyDiscardsData(const Value *RetVal, const Value *CallVal, 321263508Sdim SmallVectorImpl<unsigned> &RetIndices, 322263508Sdim SmallVectorImpl<unsigned> &CallIndices, 323263508Sdim bool AllowDifferingSizes, 324263508Sdim const TargetLoweringBase &TLI) { 325251662Sdim 326263508Sdim // Trace the sub-value needed by the return value as far back up the graph as 327263508Sdim // possible, in the hope that it will intersect with the value produced by the 328263508Sdim // call. In the simple case with no "returned" attribute, the hope is actually 329263508Sdim // that we end up back at the tail call instruction itself. 330263508Sdim unsigned BitsRequired = UINT_MAX; 331263508Sdim RetVal = getNoopInput(RetVal, RetIndices, BitsRequired, TLI); 332263508Sdim 333263508Sdim // If this slot in the value returned is undef, it doesn't matter what the 334263508Sdim // call puts there, it'll be fine. 335263508Sdim if (isa<UndefValue>(RetVal)) 336263508Sdim return true; 337263508Sdim 338263508Sdim // Now do a similar search up through the graph to find where the value 339263508Sdim // actually returned by the "tail call" comes from. In the simple case without 340263508Sdim // a "returned" attribute, the search will be blocked immediately and the loop 341263508Sdim // a Noop. 342263508Sdim unsigned BitsProvided = UINT_MAX; 343263508Sdim CallVal = getNoopInput(CallVal, CallIndices, BitsProvided, TLI); 344263508Sdim 345263508Sdim // There's no hope if we can't actually trace them to (the same part of!) the 346263508Sdim // same value. 347263508Sdim if (CallVal != RetVal || CallIndices != RetIndices) 348263508Sdim return false; 349263508Sdim 350263508Sdim // However, intervening truncates may have made the call non-tail. Make sure 351263508Sdim // all the bits that are needed by the "ret" have been provided by the "tail 352263508Sdim // call". FIXME: with sufficiently cunning bit-tracking, we could look through 353263508Sdim // extensions too. 354263508Sdim if (BitsProvided < BitsRequired || 355263508Sdim (!AllowDifferingSizes && BitsProvided != BitsRequired)) 356263508Sdim return false; 357263508Sdim 358263508Sdim return true; 359263508Sdim} 360263508Sdim 361263508Sdim/// For an aggregate type, determine whether a given index is within bounds or 362263508Sdim/// not. 363263508Sdimstatic bool indexReallyValid(CompositeType *T, unsigned Idx) { 364263508Sdim if (ArrayType *AT = dyn_cast<ArrayType>(T)) 365263508Sdim return Idx < AT->getNumElements(); 366263508Sdim 367263508Sdim return Idx < cast<StructType>(T)->getNumElements(); 368263508Sdim} 369263508Sdim 370263508Sdim/// Move the given iterators to the next leaf type in depth first traversal. 371263508Sdim/// 372263508Sdim/// Performs a depth-first traversal of the type as specified by its arguments, 373263508Sdim/// stopping at the next leaf node (which may be a legitimate scalar type or an 374263508Sdim/// empty struct or array). 375263508Sdim/// 376263508Sdim/// @param SubTypes List of the partial components making up the type from 377263508Sdim/// outermost to innermost non-empty aggregate. The element currently 378263508Sdim/// represented is SubTypes.back()->getTypeAtIndex(Path.back() - 1). 379263508Sdim/// 380263508Sdim/// @param Path Set of extractvalue indices leading from the outermost type 381263508Sdim/// (SubTypes[0]) to the leaf node currently represented. 382263508Sdim/// 383263508Sdim/// @returns true if a new type was found, false otherwise. Calling this 384263508Sdim/// function again on a finished iterator will repeatedly return 385263508Sdim/// false. SubTypes.back()->getTypeAtIndex(Path.back()) is either an empty 386263508Sdim/// aggregate or a non-aggregate 387263508Sdimstatic bool advanceToNextLeafType(SmallVectorImpl<CompositeType *> &SubTypes, 388263508Sdim SmallVectorImpl<unsigned> &Path) { 389263508Sdim // First march back up the tree until we can successfully increment one of the 390263508Sdim // coordinates in Path. 391263508Sdim while (!Path.empty() && !indexReallyValid(SubTypes.back(), Path.back() + 1)) { 392263508Sdim Path.pop_back(); 393263508Sdim SubTypes.pop_back(); 394239462Sdim } 395239462Sdim 396263508Sdim // If we reached the top, then the iterator is done. 397263508Sdim if (Path.empty()) 398263508Sdim return false; 399251662Sdim 400263508Sdim // We know there's *some* valid leaf now, so march back down the tree picking 401263508Sdim // out the left-most element at each node. 402263508Sdim ++Path.back(); 403263508Sdim Type *DeeperType = SubTypes.back()->getTypeAtIndex(Path.back()); 404263508Sdim while (DeeperType->isAggregateType()) { 405263508Sdim CompositeType *CT = cast<CompositeType>(DeeperType); 406263508Sdim if (!indexReallyValid(CT, 0)) 407263508Sdim return true; 408263508Sdim 409263508Sdim SubTypes.push_back(CT); 410263508Sdim Path.push_back(0); 411263508Sdim 412263508Sdim DeeperType = CT->getTypeAtIndex(0U); 413239462Sdim } 414239462Sdim 415263508Sdim return true; 416239462Sdim} 417239462Sdim 418263508Sdim/// Find the first non-empty, scalar-like type in Next and setup the iterator 419263508Sdim/// components. 420263508Sdim/// 421263508Sdim/// Assuming Next is an aggregate of some kind, this function will traverse the 422263508Sdim/// tree from left to right (i.e. depth-first) looking for the first 423263508Sdim/// non-aggregate type which will play a role in function return. 424263508Sdim/// 425263508Sdim/// For example, if Next was {[0 x i64], {{}, i32, {}}, i32} then we would setup 426263508Sdim/// Path as [1, 1] and SubTypes as [Next, {{}, i32, {}}] to represent the first 427263508Sdim/// i32 in that type. 428263508Sdimstatic bool firstRealType(Type *Next, 429263508Sdim SmallVectorImpl<CompositeType *> &SubTypes, 430263508Sdim SmallVectorImpl<unsigned> &Path) { 431263508Sdim // First initialise the iterator components to the first "leaf" node 432263508Sdim // (i.e. node with no valid sub-type at any index, so {} does count as a leaf 433263508Sdim // despite nominally being an aggregate). 434263508Sdim while (Next->isAggregateType() && 435263508Sdim indexReallyValid(cast<CompositeType>(Next), 0)) { 436263508Sdim SubTypes.push_back(cast<CompositeType>(Next)); 437263508Sdim Path.push_back(0); 438263508Sdim Next = cast<CompositeType>(Next)->getTypeAtIndex(0U); 439263508Sdim } 440263508Sdim 441263508Sdim // If there's no Path now, Next was originally scalar already (or empty 442263508Sdim // leaf). We're done. 443263508Sdim if (Path.empty()) 444263508Sdim return true; 445263508Sdim 446263508Sdim // Otherwise, use normal iteration to keep looking through the tree until we 447263508Sdim // find a non-aggregate type. 448263508Sdim while (SubTypes.back()->getTypeAtIndex(Path.back())->isAggregateType()) { 449263508Sdim if (!advanceToNextLeafType(SubTypes, Path)) 450263508Sdim return false; 451263508Sdim } 452263508Sdim 453263508Sdim return true; 454263508Sdim} 455263508Sdim 456263508Sdim/// Set the iterator data-structures to the next non-empty, non-aggregate 457263508Sdim/// subtype. 458263508Sdimstatic bool nextRealType(SmallVectorImpl<CompositeType *> &SubTypes, 459263508Sdim SmallVectorImpl<unsigned> &Path) { 460263508Sdim do { 461263508Sdim if (!advanceToNextLeafType(SubTypes, Path)) 462263508Sdim return false; 463263508Sdim 464263508Sdim assert(!Path.empty() && "found a leaf but didn't set the path?"); 465263508Sdim } while (SubTypes.back()->getTypeAtIndex(Path.back())->isAggregateType()); 466263508Sdim 467263508Sdim return true; 468263508Sdim} 469263508Sdim 470263508Sdim 471207618Srdivacky/// Test if the given instruction is in a position to be optimized 472207618Srdivacky/// with a tail-call. This roughly means that it's in a block with 473207618Srdivacky/// a return and there's nothing that needs to be scheduled 474207618Srdivacky/// between it and the return. 475207618Srdivacky/// 476207618Srdivacky/// This function only tests target-independent requirements. 477251662Sdimbool llvm::isInTailCallPosition(ImmutableCallSite CS, 478251662Sdim const TargetLowering &TLI) { 479207618Srdivacky const Instruction *I = CS.getInstruction(); 480207618Srdivacky const BasicBlock *ExitBB = I->getParent(); 481207618Srdivacky const TerminatorInst *Term = ExitBB->getTerminator(); 482207618Srdivacky const ReturnInst *Ret = dyn_cast<ReturnInst>(Term); 483207618Srdivacky 484207618Srdivacky // The block must end in a return statement or unreachable. 485207618Srdivacky // 486207618Srdivacky // FIXME: Decline tailcall if it's not guaranteed and if the block ends in 487207618Srdivacky // an unreachable, for now. The way tailcall optimization is currently 488207618Srdivacky // implemented means it will add an epilogue followed by a jump. That is 489207618Srdivacky // not profitable. Also, if the callee is a special function (e.g. 490207618Srdivacky // longjmp on x86), it can end up causing miscompilation that has not 491207618Srdivacky // been fully understood. 492207618Srdivacky if (!Ret && 493234353Sdim (!TLI.getTargetMachine().Options.GuaranteedTailCallOpt || 494239462Sdim !isa<UnreachableInst>(Term))) 495239462Sdim return false; 496207618Srdivacky 497207618Srdivacky // If I will have a chain, make sure no other instruction that will have a 498207618Srdivacky // chain interposes between I and the return. 499207618Srdivacky if (I->mayHaveSideEffects() || I->mayReadFromMemory() || 500234353Sdim !isSafeToSpeculativelyExecute(I)) 501207618Srdivacky for (BasicBlock::const_iterator BBI = prior(prior(ExitBB->end())); ; 502207618Srdivacky --BBI) { 503207618Srdivacky if (&*BBI == I) 504207618Srdivacky break; 505207618Srdivacky // Debug info intrinsics do not get in the way of tail call optimization. 506207618Srdivacky if (isa<DbgInfoIntrinsic>(BBI)) 507207618Srdivacky continue; 508207618Srdivacky if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() || 509234353Sdim !isSafeToSpeculativelyExecute(BBI)) 510207618Srdivacky return false; 511207618Srdivacky } 512207618Srdivacky 513263508Sdim return returnTypeIsEligibleForTailCall(ExitBB->getParent(), I, Ret, TLI); 514263508Sdim} 515263508Sdim 516263508Sdimbool llvm::returnTypeIsEligibleForTailCall(const Function *F, 517263508Sdim const Instruction *I, 518263508Sdim const ReturnInst *Ret, 519263508Sdim const TargetLoweringBase &TLI) { 520207618Srdivacky // If the block ends with a void return or unreachable, it doesn't matter 521207618Srdivacky // what the call's return type is. 522207618Srdivacky if (!Ret || Ret->getNumOperands() == 0) return true; 523207618Srdivacky 524207618Srdivacky // If the return value is undef, it doesn't matter what the call's 525207618Srdivacky // return type is. 526207618Srdivacky if (isa<UndefValue>(Ret->getOperand(0))) return true; 527207618Srdivacky 528263508Sdim // Make sure the attributes attached to each return are compatible. 529263508Sdim AttrBuilder CallerAttrs(F->getAttributes(), 530263508Sdim AttributeSet::ReturnIndex); 531263508Sdim AttrBuilder CalleeAttrs(cast<CallInst>(I)->getAttributes(), 532263508Sdim AttributeSet::ReturnIndex); 533207618Srdivacky 534263508Sdim // Noalias is completely benign as far as calling convention goes, it 535263508Sdim // shouldn't affect whether the call is a tail call. 536263508Sdim CallerAttrs = CallerAttrs.removeAttribute(Attribute::NoAlias); 537263508Sdim CalleeAttrs = CalleeAttrs.removeAttribute(Attribute::NoAlias); 538263508Sdim 539263508Sdim bool AllowDifferingSizes = true; 540263508Sdim if (CallerAttrs.contains(Attribute::ZExt)) { 541263508Sdim if (!CalleeAttrs.contains(Attribute::ZExt)) 542263508Sdim return false; 543263508Sdim 544263508Sdim AllowDifferingSizes = false; 545263508Sdim CallerAttrs.removeAttribute(Attribute::ZExt); 546263508Sdim CalleeAttrs.removeAttribute(Attribute::ZExt); 547263508Sdim } else if (CallerAttrs.contains(Attribute::SExt)) { 548263508Sdim if (!CalleeAttrs.contains(Attribute::SExt)) 549263508Sdim return false; 550263508Sdim 551263508Sdim AllowDifferingSizes = false; 552263508Sdim CallerAttrs.removeAttribute(Attribute::SExt); 553263508Sdim CalleeAttrs.removeAttribute(Attribute::SExt); 554263508Sdim } 555263508Sdim 556263508Sdim // If they're still different, there's some facet we don't understand 557263508Sdim // (currently only "inreg", but in future who knows). It may be OK but the 558263508Sdim // only safe option is to reject the tail call. 559263508Sdim if (CallerAttrs != CalleeAttrs) 560207618Srdivacky return false; 561207618Srdivacky 562263508Sdim const Value *RetVal = Ret->getOperand(0), *CallVal = I; 563263508Sdim SmallVector<unsigned, 4> RetPath, CallPath; 564263508Sdim SmallVector<CompositeType *, 4> RetSubTypes, CallSubTypes; 565263508Sdim 566263508Sdim bool RetEmpty = !firstRealType(RetVal->getType(), RetSubTypes, RetPath); 567263508Sdim bool CallEmpty = !firstRealType(CallVal->getType(), CallSubTypes, CallPath); 568263508Sdim 569263508Sdim // Nothing's actually returned, it doesn't matter what the callee put there 570263508Sdim // it's a valid tail call. 571263508Sdim if (RetEmpty) 572263508Sdim return true; 573263508Sdim 574263508Sdim // Iterate pairwise through each of the value types making up the tail call 575263508Sdim // and the corresponding return. For each one we want to know whether it's 576263508Sdim // essentially going directly from the tail call to the ret, via operations 577263508Sdim // that end up not generating any code. 578263508Sdim // 579263508Sdim // We allow a certain amount of covariance here. For example it's permitted 580263508Sdim // for the tail call to define more bits than the ret actually cares about 581263508Sdim // (e.g. via a truncate). 582263508Sdim do { 583263508Sdim if (CallEmpty) { 584263508Sdim // We've exhausted the values produced by the tail call instruction, the 585263508Sdim // rest are essentially undef. The type doesn't really matter, but we need 586263508Sdim // *something*. 587263508Sdim Type *SlotType = RetSubTypes.back()->getTypeAtIndex(RetPath.back()); 588263508Sdim CallVal = UndefValue::get(SlotType); 589263508Sdim } 590263508Sdim 591263508Sdim // The manipulations performed when we're looking through an insertvalue or 592263508Sdim // an extractvalue would happen at the front of the RetPath list, so since 593263508Sdim // we have to copy it anyway it's more efficient to create a reversed copy. 594263508Sdim using std::copy; 595263508Sdim SmallVector<unsigned, 4> TmpRetPath, TmpCallPath; 596263508Sdim copy(RetPath.rbegin(), RetPath.rend(), std::back_inserter(TmpRetPath)); 597263508Sdim copy(CallPath.rbegin(), CallPath.rend(), std::back_inserter(TmpCallPath)); 598263508Sdim 599263508Sdim // Finally, we can check whether the value produced by the tail call at this 600263508Sdim // index is compatible with the value we return. 601263508Sdim if (!slotOnlyDiscardsData(RetVal, CallVal, TmpRetPath, TmpCallPath, 602263508Sdim AllowDifferingSizes, TLI)) 603263508Sdim return false; 604263508Sdim 605263508Sdim CallEmpty = !nextRealType(CallSubTypes, CallPath); 606263508Sdim } while(nextRealType(RetSubTypes, RetPath)); 607263508Sdim 608263508Sdim return true; 609207618Srdivacky} 610