LCOV - code coverage report
Current view: top level - lib/CodeGen - Analysis.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 268 284 94.4 %
Date: 2017-09-14 15:23:50 Functions: 17 18 94.4 %
Legend: Lines: hit not hit

          Line data    Source code
       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 utilities.
      11             : //
      12             : //===----------------------------------------------------------------------===//
      13             : 
      14             : #include "llvm/CodeGen/Analysis.h"
      15             : #include "llvm/Analysis/ValueTracking.h"
      16             : #include "llvm/CodeGen/MachineFunction.h"
      17             : #include "llvm/CodeGen/MachineModuleInfo.h"
      18             : #include "llvm/IR/DataLayout.h"
      19             : #include "llvm/IR/DerivedTypes.h"
      20             : #include "llvm/IR/Function.h"
      21             : #include "llvm/IR/Instructions.h"
      22             : #include "llvm/IR/IntrinsicInst.h"
      23             : #include "llvm/IR/LLVMContext.h"
      24             : #include "llvm/IR/Module.h"
      25             : #include "llvm/Support/ErrorHandling.h"
      26             : #include "llvm/Support/MathExtras.h"
      27             : #include "llvm/Target/TargetInstrInfo.h"
      28             : #include "llvm/Target/TargetLowering.h"
      29             : #include "llvm/Target/TargetSubtargetInfo.h"
      30             : #include "llvm/Transforms/Utils/GlobalStatus.h"
      31             : 
      32             : using namespace llvm;
      33             : 
      34             : /// Compute the linearized index of a member in a nested aggregate/struct/array
      35             : /// by recursing and accumulating CurIndex as long as there are indices in the
      36             : /// index list.
      37       59756 : unsigned llvm::ComputeLinearIndex(Type *Ty,
      38             :                                   const unsigned *Indices,
      39             :                                   const unsigned *IndicesEnd,
      40             :                                   unsigned CurIndex) {
      41             :   // Base case: We're done.
      42      100792 :   if (Indices && Indices == IndicesEnd)
      43             :     return CurIndex;
      44             : 
      45             :   // Given a struct type, recursively traverse the elements.
      46       40736 :   if (StructType *STy = dyn_cast<StructType>(Ty)) {
      47       59264 :     for (StructType::element_iterator EB = STy->element_begin(),
      48       40736 :                                       EI = EB,
      49       40736 :                                       EE = STy->element_end();
      50       59264 :         EI != EE; ++EI) {
      51       59251 :       if (Indices && *Indices == unsigned(EI - EB))
      52       40723 :         return ComputeLinearIndex(*EI, Indices+1, IndicesEnd, CurIndex);
      53       18528 :       CurIndex = ComputeLinearIndex(*EI, nullptr, nullptr, CurIndex);
      54             :     }
      55             :     assert(!Indices && "Unexpected out of bound");
      56             :     return CurIndex;
      57             :   }
      58             :   // Given an array type, recursively traverse the elements.
      59         321 :   else if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
      60         321 :     Type *EltTy = ATy->getElementType();
      61         321 :     unsigned NumElts = ATy->getNumElements();
      62             :     // Compute the Linear offset when jumping one element of the array
      63         321 :     unsigned EltLinearOffset = ComputeLinearIndex(EltTy, nullptr, nullptr, 0);
      64         321 :     if (Indices) {
      65             :       assert(*Indices < NumElts && "Unexpected out of bound");
      66             :       // If the indice is inside the array, compute the index to the requested
      67             :       // elt and recurse inside the element with the end of the indices list
      68         313 :       CurIndex += EltLinearOffset* *Indices;
      69         313 :       return ComputeLinearIndex(EltTy, Indices+1, IndicesEnd, CurIndex);
      70             :     }
      71           8 :     CurIndex += EltLinearOffset*NumElts;
      72           8 :     return CurIndex;
      73             :   }
      74             :   // We haven't found the type we're looking for, so keep searching.
      75       18828 :   return CurIndex + 1;
      76             : }
      77             : 
      78             : /// ComputeValueVTs - Given an LLVM IR type, compute a sequence of
      79             : /// EVTs that represent all the individual underlying
      80             : /// non-aggregate types that comprise it.
      81             : ///
      82             : /// If Offsets is non-null, it points to a vector to be filled in
      83             : /// with the in-memory offsets of each of the individual values.
      84             : ///
      85     2828882 : void llvm::ComputeValueVTs(const TargetLowering &TLI, const DataLayout &DL,
      86             :                            Type *Ty, SmallVectorImpl<EVT> &ValueVTs,
      87             :                            SmallVectorImpl<uint64_t> *Offsets,
      88             :                            uint64_t StartingOffset) {
      89             :   // Given a struct type, recursively traverse the elements.
      90       32866 :   if (StructType *STy = dyn_cast<StructType>(Ty)) {
      91       32866 :     const StructLayout *SL = DL.getStructLayout(STy);
      92      104370 :     for (StructType::element_iterator EB = STy->element_begin(),
      93       32866 :                                       EI = EB,
      94       32866 :                                       EE = STy->element_end();
      95      104370 :          EI != EE; ++EI)
      96       71504 :       ComputeValueVTs(TLI, DL, *EI, ValueVTs, Offsets,
      97      143008 :                       StartingOffset + SL->getElementOffset(EI - EB));
      98             :     return;
      99             :   }
     100             :   // Given an array type, recursively traverse the elements.
     101        2037 :   if (ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
     102        2037 :     Type *EltTy = ATy->getElementType();
     103        2037 :     uint64_t EltSize = DL.getTypeAllocSize(EltTy);
     104       14498 :     for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i)
     105       12461 :       ComputeValueVTs(TLI, DL, EltTy, ValueVTs, Offsets,
     106       12461 :                       StartingOffset + i * EltSize);
     107             :     return;
     108             :   }
     109             :   // Interpret void as zero return values.
     110     2793979 :   if (Ty->isVoidTy())
     111             :     return;
     112             :   // Base case: we can get an EVT for this LLVM IR type.
     113     2417740 :   ValueVTs.push_back(TLI.getValueType(DL, Ty));
     114     2417740 :   if (Offsets)
     115      592538 :     Offsets->push_back(StartingOffset);
     116             : }
     117             : 
     118             : /// ExtractTypeInfo - Returns the type info, possibly bitcast, encoded in V.
     119          72 : GlobalValue *llvm::ExtractTypeInfo(Value *V) {
     120          72 :   V = V->stripPointerCasts();
     121          72 :   GlobalValue *GV = dyn_cast<GlobalValue>(V);
     122          69 :   GlobalVariable *Var = dyn_cast<GlobalVariable>(V);
     123             : 
     124          69 :   if (Var && Var->getName() == "llvm.eh.catch.all.value") {
     125             :     assert(Var->hasInitializer() &&
     126             :            "The EH catch-all value must have an initializer");
     127           0 :     Value *Init = Var->getInitializer();
     128             :     GV = dyn_cast<GlobalValue>(Init);
     129             :     if (!GV) V = cast<ConstantPointerNull>(Init);
     130             :   }
     131             : 
     132             :   assert((GV || isa<ConstantPointerNull>(V)) &&
     133             :          "TypeInfo must be a global variable or NULL");
     134          72 :   return GV;
     135             : }
     136             : 
     137             : /// hasInlineAsmMemConstraint - Return true if the inline asm instruction being
     138             : /// processed uses a memory 'm' constraint.
     139             : bool
     140           0 : llvm::hasInlineAsmMemConstraint(InlineAsm::ConstraintInfoVector &CInfos,
     141             :                                 const TargetLowering &TLI) {
     142           0 :   for (unsigned i = 0, e = CInfos.size(); i != e; ++i) {
     143           0 :     InlineAsm::ConstraintInfo &CI = CInfos[i];
     144           0 :     for (unsigned j = 0, ee = CI.Codes.size(); j != ee; ++j) {
     145           0 :       TargetLowering::ConstraintType CType = TLI.getConstraintType(CI.Codes[j]);
     146           0 :       if (CType == TargetLowering::C_Memory)
     147             :         return true;
     148             :     }
     149             : 
     150             :     // Indirect operand accesses access memory.
     151           0 :     if (CI.isIndirect)
     152             :       return true;
     153             :   }
     154             : 
     155             :   return false;
     156             : }
     157             : 
     158             : /// getFCmpCondCode - Return the ISD condition code corresponding to
     159             : /// the given LLVM IR floating-point condition code.  This includes
     160             : /// consideration of global floating-point math flags.
     161             : ///
     162        5637 : ISD::CondCode llvm::getFCmpCondCode(FCmpInst::Predicate Pred) {
     163        5637 :   switch (Pred) {
     164             :   case FCmpInst::FCMP_FALSE: return ISD::SETFALSE;
     165        1218 :   case FCmpInst::FCMP_OEQ:   return ISD::SETOEQ;
     166        1094 :   case FCmpInst::FCMP_OGT:   return ISD::SETOGT;
     167         336 :   case FCmpInst::FCMP_OGE:   return ISD::SETOGE;
     168         729 :   case FCmpInst::FCMP_OLT:   return ISD::SETOLT;
     169         275 :   case FCmpInst::FCMP_OLE:   return ISD::SETOLE;
     170         200 :   case FCmpInst::FCMP_ONE:   return ISD::SETONE;
     171         153 :   case FCmpInst::FCMP_ORD:   return ISD::SETO;
     172         201 :   case FCmpInst::FCMP_UNO:   return ISD::SETUO;
     173         149 :   case FCmpInst::FCMP_UEQ:   return ISD::SETUEQ;
     174         238 :   case FCmpInst::FCMP_UGT:   return ISD::SETUGT;
     175         249 :   case FCmpInst::FCMP_UGE:   return ISD::SETUGE;
     176         230 :   case FCmpInst::FCMP_ULT:   return ISD::SETULT;
     177         160 :   case FCmpInst::FCMP_ULE:   return ISD::SETULE;
     178         339 :   case FCmpInst::FCMP_UNE:   return ISD::SETUNE;
     179          33 :   case FCmpInst::FCMP_TRUE:  return ISD::SETTRUE;
     180           0 :   default: llvm_unreachable("Invalid FCmp predicate opcode!");
     181             :   }
     182             : }
     183             : 
     184         285 : ISD::CondCode llvm::getFCmpCodeWithoutNaN(ISD::CondCode CC) {
     185         285 :   switch (CC) {
     186             :     case ISD::SETOEQ: case ISD::SETUEQ: return ISD::SETEQ;
     187           1 :     case ISD::SETONE: case ISD::SETUNE: return ISD::SETNE;
     188          66 :     case ISD::SETOLT: case ISD::SETULT: return ISD::SETLT;
     189          60 :     case ISD::SETOLE: case ISD::SETULE: return ISD::SETLE;
     190          73 :     case ISD::SETOGT: case ISD::SETUGT: return ISD::SETGT;
     191          60 :     case ISD::SETOGE: case ISD::SETUGE: return ISD::SETGE;
     192           0 :     default: return CC;
     193             :   }
     194             : }
     195             : 
     196             : /// getICmpCondCode - Return the ISD condition code corresponding to
     197             : /// the given LLVM IR integer condition code.
     198             : ///
     199       49098 : ISD::CondCode llvm::getICmpCondCode(ICmpInst::Predicate Pred) {
     200       49098 :   switch (Pred) {
     201             :   case ICmpInst::ICMP_EQ:  return ISD::SETEQ;
     202       13707 :   case ICmpInst::ICMP_NE:  return ISD::SETNE;
     203         847 :   case ICmpInst::ICMP_SLE: return ISD::SETLE;
     204         829 :   case ICmpInst::ICMP_ULE: return ISD::SETULE;
     205        1068 :   case ICmpInst::ICMP_SGE: return ISD::SETGE;
     206         742 :   case ICmpInst::ICMP_UGE: return ISD::SETUGE;
     207        2768 :   case ICmpInst::ICMP_SLT: return ISD::SETLT;
     208        5598 :   case ICmpInst::ICMP_ULT: return ISD::SETULT;
     209        3833 :   case ICmpInst::ICMP_SGT: return ISD::SETGT;
     210        2560 :   case ICmpInst::ICMP_UGT: return ISD::SETUGT;
     211           0 :   default:
     212           0 :     llvm_unreachable("Invalid ICmp predicate opcode!");
     213             :   }
     214             : }
     215             : 
     216          81 : static bool isNoopBitcast(Type *T1, Type *T2,
     217             :                           const TargetLoweringBase& TLI) {
     218         123 :   return T1 == T2 || (T1->isPointerTy() && T2->isPointerTy()) ||
     219           3 :          (isa<VectorType>(T1) && isa<VectorType>(T2) &&
     220          83 :           TLI.isTypeLegal(EVT::getEVT(T1)) && TLI.isTypeLegal(EVT::getEVT(T2)));
     221             : }
     222             : 
     223             : /// Look through operations that will be free to find the earliest source of
     224             : /// this value.
     225             : ///
     226             : /// @param ValLoc If V has aggegate type, we will be interested in a particular
     227             : /// scalar component. This records its address; the reverse of this list gives a
     228             : /// sequence of indices appropriate for an extractvalue to locate the important
     229             : /// value. This value is updated during the function and on exit will indicate
     230             : /// similar information for the Value returned.
     231             : ///
     232             : /// @param DataBits If this function looks through truncate instructions, this
     233             : /// will record the smallest size attained.
     234        3416 : static const Value *getNoopInput(const Value *V,
     235             :                                  SmallVectorImpl<unsigned> &ValLoc,
     236             :                                  unsigned &DataBits,
     237             :                                  const TargetLoweringBase &TLI,
     238             :                                  const DataLayout &DL) {
     239             :   while (true) {
     240             :     // Try to look through V1; if V1 is not an instruction, it can't be looked
     241             :     // through.
     242        3349 :     const Instruction *I = dyn_cast<Instruction>(V);
     243       10114 :     if (!I || I->getNumOperands() == 0) return V;
     244        3349 :     const Value *NoopInput = nullptr;
     245             : 
     246        6698 :     Value *Op = I->getOperand(0);
     247        6698 :     if (isa<BitCastInst>(I)) {
     248             :       // Look through truly no-op bitcasts.
     249          22 :       if (isNoopBitcast(Op->getType(), I->getType(), TLI))
     250             :         NoopInput = Op;
     251        6654 :     } else if (isa<GetElementPtrInst>(I)) {
     252             :       // Look through getelementptr
     253           8 :       if (cast<GetElementPtrInst>(I)->hasAllZeroIndices())
     254             :         NoopInput = Op;
     255        6646 :     } else if (isa<IntToPtrInst>(I)) {
     256             :       // Look through inttoptr.
     257             :       // Make sure this isn't a truncating or extending cast.  We could
     258             :       // support this eventually, but don't bother for now.
     259          18 :       if (!isa<VectorType>(I->getType()) &&
     260           6 :           DL.getPointerSizeInBits() ==
     261          18 :               cast<IntegerType>(Op->getType())->getBitWidth())
     262             :         NoopInput = Op;
     263        6634 :     } else if (isa<PtrToIntInst>(I)) {
     264             :       // Look through ptrtoint.
     265             :       // Make sure this isn't a truncating or extending cast.  We could
     266             :       // support this eventually, but don't bother for now.
     267           0 :       if (!isa<VectorType>(I->getType()) &&
     268           0 :           DL.getPointerSizeInBits() ==
     269           0 :               cast<IntegerType>(I->getType())->getBitWidth())
     270             :         NoopInput = Op;
     271        6660 :     } else if (isa<TruncInst>(I) &&
     272          26 :                TLI.allowTruncateForTailCall(Op->getType(), I->getType())) {
     273          44 :       DataBits = std::min(DataBits, I->getType()->getPrimitiveSizeInBits());
     274          22 :       NoopInput = Op;
     275        9885 :     } else if (auto CS = ImmutableCallSite(I)) {
     276        2876 :       const Value *ReturnedOp = CS.getReturnedArgOperand();
     277        2876 :       if (ReturnedOp && isNoopBitcast(ReturnedOp->getType(), I->getType(), TLI))
     278             :         NoopInput = ReturnedOp;
     279          75 :     } else if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(V)) {
     280             :       // Value may come from either the aggregate or the scalar
     281          75 :       ArrayRef<unsigned> InsertLoc = IVI->getIndices();
     282         223 :       if (ValLoc.size() >= InsertLoc.size() &&
     283         292 :           std::equal(InsertLoc.begin(), InsertLoc.end(), ValLoc.rbegin())) {
     284             :         // The type being inserted is a nested sub-type of the aggregate; we
     285             :         // have to remove those initial indices to get the location we're
     286             :         // interested in for the operand.
     287          88 :         ValLoc.resize(ValLoc.size() - InsertLoc.size());
     288           0 :         NoopInput = IVI->getInsertedValueOperand();
     289             :       } else {
     290             :         // The struct we're inserting into has the value we're interested in, no
     291             :         // change of address.
     292             :         NoopInput = Op;
     293             :       }
     294          40 :     } else if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(V)) {
     295             :       // The part we're interested in will inevitably be some sub-section of the
     296             :       // previous aggregate. Combine the two paths to obtain the true address of
     297             :       // our element.
     298          40 :       ArrayRef<unsigned> ExtractLoc = EVI->getIndices();
     299          80 :       ValLoc.append(ExtractLoc.rbegin(), ExtractLoc.rend());
     300          40 :       NoopInput = Op;
     301             :     }
     302             :     // Terminate if we couldn't find anything to look through.
     303         224 :     if (!NoopInput)
     304             :       return V;
     305             : 
     306             :     V = NoopInput;
     307             :   }
     308             : }
     309             : 
     310             : /// Return true if this scalar return value only has bits discarded on its path
     311             : /// from the "tail call" to the "ret". This includes the obvious noop
     312             : /// instructions handled by getNoopInput above as well as free truncations (or
     313             : /// extensions prior to the call).
     314        1709 : static bool slotOnlyDiscardsData(const Value *RetVal, const Value *CallVal,
     315             :                                  SmallVectorImpl<unsigned> &RetIndices,
     316             :                                  SmallVectorImpl<unsigned> &CallIndices,
     317             :                                  bool AllowDifferingSizes,
     318             :                                  const TargetLoweringBase &TLI,
     319             :                                  const DataLayout &DL) {
     320             : 
     321             :   // Trace the sub-value needed by the return value as far back up the graph as
     322             :   // possible, in the hope that it will intersect with the value produced by the
     323             :   // call. In the simple case with no "returned" attribute, the hope is actually
     324             :   // that we end up back at the tail call instruction itself.
     325        1709 :   unsigned BitsRequired = UINT_MAX;
     326        1709 :   RetVal = getNoopInput(RetVal, RetIndices, BitsRequired, TLI, DL);
     327             : 
     328             :   // If this slot in the value returned is undef, it doesn't matter what the
     329             :   // call puts there, it'll be fine.
     330        3418 :   if (isa<UndefValue>(RetVal))
     331             :     return true;
     332             : 
     333             :   // Now do a similar search up through the graph to find where the value
     334             :   // actually returned by the "tail call" comes from. In the simple case without
     335             :   // a "returned" attribute, the search will be blocked immediately and the loop
     336             :   // a Noop.
     337        1707 :   unsigned BitsProvided = UINT_MAX;
     338        1707 :   CallVal = getNoopInput(CallVal, CallIndices, BitsProvided, TLI, DL);
     339             : 
     340             :   // There's no hope if we can't actually trace them to (the same part of!) the
     341             :   // same value.
     342        2873 :   if (CallVal != RetVal || CallIndices != RetIndices)
     343             :     return false;
     344             : 
     345             :   // However, intervening truncates may have made the call non-tail. Make sure
     346             :   // all the bits that are needed by the "ret" have been provided by the "tail
     347             :   // call". FIXME: with sufficiently cunning bit-tracking, we could look through
     348             :   // extensions too.
     349        1165 :   if (BitsProvided < BitsRequired ||
     350          70 :       (!AllowDifferingSizes && BitsProvided != BitsRequired))
     351             :     return false;
     352             : 
     353        1162 :   return true;
     354             : }
     355             : 
     356             : /// For an aggregate type, determine whether a given index is within bounds or
     357             : /// not.
     358             : static bool indexReallyValid(CompositeType *T, unsigned Idx) {
     359          26 :   if (ArrayType *AT = dyn_cast<ArrayType>(T))
     360          26 :     return Idx < AT->getNumElements();
     361             : 
     362         278 :   return Idx < cast<StructType>(T)->getNumElements();
     363             : }
     364             : 
     365             : /// Move the given iterators to the next leaf type in depth first traversal.
     366             : ///
     367             : /// Performs a depth-first traversal of the type as specified by its arguments,
     368             : /// stopping at the next leaf node (which may be a legitimate scalar type or an
     369             : /// empty struct or array).
     370             : ///
     371             : /// @param SubTypes List of the partial components making up the type from
     372             : /// outermost to innermost non-empty aggregate. The element currently
     373             : /// represented is SubTypes.back()->getTypeAtIndex(Path.back() - 1).
     374             : ///
     375             : /// @param Path Set of extractvalue indices leading from the outermost type
     376             : /// (SubTypes[0]) to the leaf node currently represented.
     377             : ///
     378             : /// @returns true if a new type was found, false otherwise. Calling this
     379             : /// function again on a finished iterator will repeatedly return
     380             : /// false. SubTypes.back()->getTypeAtIndex(Path.back()) is either an empty
     381             : /// aggregate or a non-aggregate
     382        2334 : static bool advanceToNextLeafType(SmallVectorImpl<CompositeType *> &SubTypes,
     383             :                                   SmallVectorImpl<unsigned> &Path) {
     384             :   // First march back up the tree until we can successfully increment one of the
     385             :   // coordinates in Path.
     386        3003 :   while (!Path.empty() && !indexReallyValid(SubTypes.back(), Path.back() + 1)) {
     387         156 :     Path.pop_back();
     388          78 :     SubTypes.pop_back();
     389             :   }
     390             : 
     391             :   // If we reached the top, then the iterator is done.
     392        2334 :   if (Path.empty())
     393             :     return false;
     394             : 
     395             :   // We know there's *some* valid leaf now, so march back down the tree picking
     396             :   // out the left-most element at each node.
     397         238 :   ++Path.back();
     398         357 :   Type *DeeperType = SubTypes.back()->getTypeAtIndex(Path.back());
     399          22 :   while (DeeperType->isAggregateType()) {
     400          26 :     CompositeType *CT = cast<CompositeType>(DeeperType);
     401          52 :     if (!indexReallyValid(CT, 0))
     402           4 :       return true;
     403             : 
     404          22 :     SubTypes.push_back(CT);
     405          22 :     Path.push_back(0);
     406             : 
     407          22 :     DeeperType = CT->getTypeAtIndex(0U);
     408             :   }
     409             : 
     410             :   return true;
     411             : }
     412             : 
     413             : /// Find the first non-empty, scalar-like type in Next and setup the iterator
     414             : /// components.
     415             : ///
     416             : /// Assuming Next is an aggregate of some kind, this function will traverse the
     417             : /// tree from left to right (i.e. depth-first) looking for the first
     418             : /// non-aggregate type which will play a role in function return.
     419             : ///
     420             : /// For example, if Next was {[0 x i64], {{}, i32, {}}, i32} then we would setup
     421             : /// Path as [1, 1] and SubTypes as [Next, {{}, i32, {}}] to represent the first
     422             : /// i32 in that type.
     423        3308 : static bool firstRealType(Type *Next,
     424             :                           SmallVectorImpl<CompositeType *> &SubTypes,
     425             :                           SmallVectorImpl<unsigned> &Path) {
     426             :   // First initialise the iterator components to the first "leaf" node
     427             :   // (i.e. node with no valid sub-type at any index, so {} does count as a leaf
     428             :   // despite nominally being an aggregate).
     429         160 :   while (Next->isAggregateType() &&
     430         162 :          indexReallyValid(cast<CompositeType>(Next), 0)) {
     431         158 :     SubTypes.push_back(cast<CompositeType>(Next));
     432          79 :     Path.push_back(0);
     433          79 :     Next = cast<CompositeType>(Next)->getTypeAtIndex(0U);
     434             :   }
     435             : 
     436             :   // If there's no Path now, Next was originally scalar already (or empty
     437             :   // leaf). We're done.
     438        3308 :   if (Path.empty())
     439             :     return true;
     440             : 
     441             :   // Otherwise, use normal iteration to keep looking through the tree until we
     442             :   // find a non-aggregate type.
     443         234 :   while (SubTypes.back()->getTypeAtIndex(Path.back())->isAggregateType()) {
     444           4 :     if (!advanceToNextLeafType(SubTypes, Path))
     445             :       return false;
     446             :   }
     447             : 
     448             :   return true;
     449             : }
     450             : 
     451             : /// Set the iterator data-structures to the next non-empty, non-aggregate
     452             : /// subtype.
     453        2328 : static bool nextRealType(SmallVectorImpl<CompositeType *> &SubTypes,
     454             :                          SmallVectorImpl<unsigned> &Path) {
     455             :   do {
     456        2330 :     if (!advanceToNextLeafType(SubTypes, Path))
     457             :       return false;
     458             : 
     459             :     assert(!Path.empty() && "found a leaf but didn't set the path?");
     460         345 :   } while (SubTypes.back()->getTypeAtIndex(Path.back())->isAggregateType());
     461             : 
     462             :   return true;
     463             : }
     464             : 
     465             : 
     466             : /// Test if the given instruction is in a position to be optimized
     467             : /// with a tail-call. This roughly means that it's in a block with
     468             : /// a return and there's nothing that needs to be scheduled
     469             : /// between it and the return.
     470             : ///
     471             : /// This function only tests target-independent requirements.
     472       60032 : bool llvm::isInTailCallPosition(ImmutableCallSite CS, const TargetMachine &TM) {
     473       60032 :   const Instruction *I = CS.getInstruction();
     474       60032 :   const BasicBlock *ExitBB = I->getParent();
     475       60032 :   const TerminatorInst *Term = ExitBB->getTerminator();
     476       60032 :   const ReturnInst *Ret = dyn_cast<ReturnInst>(Term);
     477             : 
     478             :   // The block must end in a return statement or unreachable.
     479             :   //
     480             :   // FIXME: Decline tailcall if it's not guaranteed and if the block ends in
     481             :   // an unreachable, for now. The way tailcall optimization is currently
     482             :   // implemented means it will add an epilogue followed by a jump. That is
     483             :   // not profitable. Also, if the callee is a special function (e.g.
     484             :   // longjmp on x86), it can end up causing miscompilation that has not
     485             :   // been fully understood.
     486       11097 :   if (!Ret &&
     487       11099 :       (!TM.Options.GuaranteedTailCallOpt || !isa<UnreachableInst>(Term)))
     488             :     return false;
     489             : 
     490             :   // If I will have a chain, make sure no other instruction that will have a
     491             :   // chain interposes between I and the return.
     492       49060 :   if (I->mayHaveSideEffects() || I->mayReadFromMemory() ||
     493         124 :       !isSafeToSpeculativelyExecute(I))
     494       97872 :     for (BasicBlock::const_iterator BBI = std::prev(ExitBB->end(), 2);; --BBI) {
     495       49916 :       if (&*BBI == I)
     496             :         break;
     497             :       // Debug info intrinsics do not get in the way of tail call optimization.
     498       45201 :       if (isa<DbgInfoIntrinsic>(BBI))
     499           8 :         continue;
     500       47307 :       if (BBI->mayHaveSideEffects() || BBI->mayReadFromMemory() ||
     501        1052 :           !isSafeToSpeculativelyExecute(&*BBI))
     502       44221 :         return false;
     503             :     }
     504             : 
     505        4715 :   const Function *F = ExitBB->getParent();
     506        4715 :   return returnTypeIsEligibleForTailCall(
     507        9430 :       F, I, Ret, *TM.getSubtargetImpl(*F)->getTargetLowering());
     508             : }
     509             : 
     510        2068 : bool llvm::attributesPermitTailCall(const Function *F, const Instruction *I,
     511             :                                     const ReturnInst *Ret,
     512             :                                     const TargetLoweringBase &TLI,
     513             :                                     bool *AllowDifferingSizes) {
     514             :   // ADS may be null, so don't write to it directly.
     515             :   bool DummyADS;
     516        2068 :   bool &ADS = AllowDifferingSizes ? *AllowDifferingSizes : DummyADS;
     517        2068 :   ADS = true;
     518             : 
     519        4136 :   AttrBuilder CallerAttrs(F->getAttributes(), AttributeList::ReturnIndex);
     520             :   AttrBuilder CalleeAttrs(cast<CallInst>(I)->getAttributes(),
     521        4136 :                           AttributeList::ReturnIndex);
     522             : 
     523             :   // Noalias is completely benign as far as calling convention goes, it
     524             :   // shouldn't affect whether the call is a tail call.
     525        2068 :   CallerAttrs.removeAttribute(Attribute::NoAlias);
     526        2068 :   CalleeAttrs.removeAttribute(Attribute::NoAlias);
     527             : 
     528        2068 :   if (CallerAttrs.contains(Attribute::ZExt)) {
     529          70 :     if (!CalleeAttrs.contains(Attribute::ZExt))
     530             :       return false;
     531             : 
     532          58 :     ADS = false;
     533          58 :     CallerAttrs.removeAttribute(Attribute::ZExt);
     534          58 :     CalleeAttrs.removeAttribute(Attribute::ZExt);
     535        1998 :   } else if (CallerAttrs.contains(Attribute::SExt)) {
     536          32 :     if (!CalleeAttrs.contains(Attribute::SExt))
     537             :       return false;
     538             : 
     539          29 :     ADS = false;
     540          29 :     CallerAttrs.removeAttribute(Attribute::SExt);
     541          29 :     CalleeAttrs.removeAttribute(Attribute::SExt);
     542             :   }
     543             : 
     544             :   // If they're still different, there's some facet we don't understand
     545             :   // (currently only "inreg", but in future who knows). It may be OK but the
     546             :   // only safe option is to reject the tail call.
     547        2053 :   return CallerAttrs == CalleeAttrs;
     548             : }
     549             : 
     550        4715 : bool llvm::returnTypeIsEligibleForTailCall(const Function *F,
     551             :                                            const Instruction *I,
     552             :                                            const ReturnInst *Ret,
     553             :                                            const TargetLoweringBase &TLI) {
     554             :   // If the block ends with a void return or unreachable, it doesn't matter
     555             :   // what the call's return type is.
     556        9429 :   if (!Ret || Ret->getNumOperands() == 0) return true;
     557             : 
     558             :   // If the return value is undef, it doesn't matter what the call's
     559             :   // return type is.
     560        3410 :   if (isa<UndefValue>(Ret->getOperand(0))) return true;
     561             : 
     562             :   // Make sure the attributes attached to each return are compatible.
     563             :   bool AllowDifferingSizes;
     564        1686 :   if (!attributesPermitTailCall(F, I, Ret, TLI, &AllowDifferingSizes))
     565             :     return false;
     566             : 
     567        1661 :   const Value *RetVal = Ret->getOperand(0), *CallVal = I;
     568             :   // Intrinsic like llvm.memcpy has no return value, but the expanded
     569             :   // libcall may or may not have return value. On most platforms, it
     570             :   // will be expanded as memcpy in libc, which returns the first
     571             :   // argument. On other platforms like arm-none-eabi, memcpy may be
     572             :   // expanded as library call without return value, like __aeabi_memcpy.
     573        1661 :   const CallInst *Call = cast<CallInst>(I);
     574        1453 :   if (Function *F = Call->getCalledFunction()) {
     575        1453 :     Intrinsic::ID IID = F->getIntrinsicID();
     576             :     if (((IID == Intrinsic::memcpy &&
     577        1482 :           TLI.getLibcallName(RTLIB::MEMCPY) == StringRef("memcpy")) ||
     578             :          (IID == Intrinsic::memmove &&
     579        1447 :           TLI.getLibcallName(RTLIB::MEMMOVE) == StringRef("memmove")) ||
     580             :          (IID == Intrinsic::memset &&
     581        1475 :           TLI.getLibcallName(RTLIB::MEMSET) == StringRef("memset"))) &&
     582          16 :         RetVal == Call->getArgOperand(0))
     583             :       return true;
     584             :   }
     585             : 
     586        4962 :   SmallVector<unsigned, 4> RetPath, CallPath;
     587        6616 :   SmallVector<CompositeType *, 4> RetSubTypes, CallSubTypes;
     588             : 
     589        1654 :   bool RetEmpty = !firstRealType(RetVal->getType(), RetSubTypes, RetPath);
     590        1654 :   bool CallEmpty = !firstRealType(CallVal->getType(), CallSubTypes, CallPath);
     591             : 
     592             :   // Nothing's actually returned, it doesn't matter what the callee put there
     593             :   // it's a valid tail call.
     594        1654 :   if (RetEmpty)
     595             :     return true;
     596             : 
     597             :   // Iterate pairwise through each of the value types making up the tail call
     598             :   // and the corresponding return. For each one we want to know whether it's
     599             :   // essentially going directly from the tail call to the ret, via operations
     600             :   // that end up not generating any code.
     601             :   //
     602             :   // We allow a certain amount of covariance here. For example it's permitted
     603             :   // for the tail call to define more bits than the ret actually cares about
     604             :   // (e.g. via a truncate).
     605             :   do {
     606        1709 :     if (CallEmpty) {
     607             :       // We've exhausted the values produced by the tail call instruction, the
     608             :       // rest are essentially undef. The type doesn't really matter, but we need
     609             :       // *something*.
     610           6 :       Type *SlotType = RetSubTypes.back()->getTypeAtIndex(RetPath.back());
     611           2 :       CallVal = UndefValue::get(SlotType);
     612             :     }
     613             : 
     614             :     // The manipulations performed when we're looking through an insertvalue or
     615             :     // an extractvalue would happen at the front of the RetPath list, so since
     616             :     // we have to copy it anyway it's more efficient to create a reversed copy.
     617        8000 :     SmallVector<unsigned, 4> TmpRetPath(RetPath.rbegin(), RetPath.rend());
     618        8000 :     SmallVector<unsigned, 4> TmpCallPath(CallPath.rbegin(), CallPath.rend());
     619             : 
     620             :     // Finally, we can check whether the value produced by the tail call at this
     621             :     // index is compatible with the value we return.
     622        1709 :     if (!slotOnlyDiscardsData(RetVal, CallVal, TmpRetPath, TmpCallPath,
     623             :                               AllowDifferingSizes, TLI,
     624             :                               F->getParent()->getDataLayout()))
     625        1090 :       return false;
     626             : 
     627        1164 :     CallEmpty  = !nextRealType(CallSubTypes, CallPath);
     628        1164 :   } while(nextRealType(RetSubTypes, RetPath));
     629             : 
     630             :   return true;
     631             : }
     632             : 
     633        1419 : static void collectFuncletMembers(
     634             :     DenseMap<const MachineBasicBlock *, int> &FuncletMembership, int Funclet,
     635             :     const MachineBasicBlock *MBB) {
     636        4257 :   SmallVector<const MachineBasicBlock *, 16> Worklist = {MBB};
     637        4458 :   while (!Worklist.empty()) {
     638        3039 :     const MachineBasicBlock *Visiting = Worklist.pop_back_val();
     639             :     // Don't follow blocks which start new funclets.
     640        3039 :     if (Visiting->isEHPad() && Visiting != MBB)
     641        2720 :       continue;
     642             : 
     643             :     // Add this MBB to our funclet.
     644        7032 :     auto P = FuncletMembership.insert(std::make_pair(Visiting, Funclet));
     645             : 
     646             :     // Don't revisit blocks.
     647        2344 :     if (!P.second) {
     648             :       assert(P.first->second == Funclet && "MBB is part of two funclets!");
     649         632 :       continue;
     650             :     }
     651             : 
     652             :     // Returns are boundaries where funclet transfer can occur, don't follow
     653             :     // successors.
     654        1712 :     if (Visiting->isReturnBlock())
     655         698 :       continue;
     656             : 
     657        4662 :     for (const MachineBasicBlock *Succ : Visiting->successors())
     658        1620 :       Worklist.push_back(Succ);
     659             :   }
     660        1419 : }
     661             : 
     662             : DenseMap<const MachineBasicBlock *, int>
     663      466030 : llvm::getFuncletMembership(const MachineFunction &MF) {
     664      466030 :   DenseMap<const MachineBasicBlock *, int> FuncletMembership;
     665             : 
     666             :   // We don't have anything to do if there aren't any EH pads.
     667      466030 :   if (!MF.hasEHFunclets())
     668             :     return FuncletMembership;
     669             : 
     670         351 :   int EntryBBNumber = MF.front().getNumber();
     671         351 :   bool IsSEH = isAsynchronousEHPersonality(
     672         702 :       classifyEHPersonality(MF.getFunction()->getPersonalityFn()));
     673             : 
     674         351 :   const TargetInstrInfo *TII = MF.getSubtarget().getInstrInfo();
     675         351 :   SmallVector<const MachineBasicBlock *, 16> FuncletBlocks;
     676         702 :   SmallVector<const MachineBasicBlock *, 16> UnreachableBlocks;
     677         702 :   SmallVector<const MachineBasicBlock *, 16> SEHCatchPads;
     678         702 :   SmallVector<std::pair<const MachineBasicBlock *, int>, 16> CatchRetSuccessors;
     679        3009 :   for (const MachineBasicBlock &MBB : MF) {
     680        1956 :     if (MBB.isEHFuncletEntry()) {
     681         520 :       FuncletBlocks.push_back(&MBB);
     682        1436 :     } else if (IsSEH && MBB.isEHPad()) {
     683         115 :       SEHCatchPads.push_back(&MBB);
     684        1321 :     } else if (MBB.pred_empty()) {
     685         351 :       UnreachableBlocks.push_back(&MBB);
     686             :     }
     687             : 
     688        1956 :     MachineBasicBlock::const_iterator MBBI = MBB.getFirstTerminator();
     689             : 
     690             :     // CatchPads are not funclets for SEH so do not consider CatchRet to
     691             :     // transfer control to another funclet.
     692        7993 :     if (MBBI == MBB.end() || MBBI->getOpcode() != TII->getCatchReturnOpcode())
     693        1673 :       continue;
     694             : 
     695             :     // FIXME: SEH CatchPads are not necessarily in the parent function:
     696             :     // they could be inside a finally block.
     697         283 :     const MachineBasicBlock *Successor = MBBI->getOperand(0).getMBB();
     698         283 :     const MachineBasicBlock *SuccessorColor = MBBI->getOperand(1).getMBB();
     699         283 :     CatchRetSuccessors.push_back(
     700         566 :         {Successor, IsSEH ? EntryBBNumber : SuccessorColor->getNumber()});
     701             :   }
     702             : 
     703             :   // We don't have anything to do if there aren't any EH pads.
     704         351 :   if (FuncletBlocks.empty())
     705             :     return FuncletMembership;
     706             : 
     707             :   // Identify all the basic blocks reachable from the function entry.
     708         295 :   collectFuncletMembers(FuncletMembership, EntryBBNumber, &MF.front());
     709             :   // All blocks not part of a funclet are in the parent function.
     710        1180 :   for (const MachineBasicBlock *MBB : UnreachableBlocks)
     711         295 :     collectFuncletMembers(FuncletMembership, EntryBBNumber, MBB);
     712             :   // Next, identify all the blocks inside the funclets.
     713        1405 :   for (const MachineBasicBlock *MBB : FuncletBlocks)
     714         520 :     collectFuncletMembers(FuncletMembership, MBB->getNumber(), MBB);
     715             :   // SEH CatchPads aren't really funclets, handle them separately.
     716         911 :   for (const MachineBasicBlock *MBB : SEHCatchPads)
     717          26 :     collectFuncletMembers(FuncletMembership, EntryBBNumber, MBB);
     718             :   // Finally, identify all the targets of a catchret.
     719         566 :   for (std::pair<const MachineBasicBlock *, int> CatchRetPair :
     720         885 :        CatchRetSuccessors)
     721         283 :     collectFuncletMembers(FuncletMembership, CatchRetPair.second,
     722             :                           CatchRetPair.first);
     723         295 :   return FuncletMembership;
     724             : }

Generated by: LCOV version 1.13