lib/Analysis/CodeMetrics.cpp

   1 //===- CodeMetrics.cpp - Code cost measurements ---------------------------===//
   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 implements code cost measurement utilities.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Analysis/AssumptionCache.h"
  15 #include "llvm/Analysis/CodeMetrics.h"
  16 #include "llvm/Analysis/LoopInfo.h"
  17 #include "llvm/Analysis/TargetTransformInfo.h"
  18 #include "llvm/Analysis/ValueTracking.h"
  19 #include "llvm/IR/CallSite.h"
  20 #include "llvm/IR/DataLayout.h"
  21 #include "llvm/IR/Function.h"
  22 #include "llvm/IR/IntrinsicInst.h"
  23 #include "llvm/Support/Debug.h"
  24 #include "llvm/Support/raw_ostream.h"
  25
  26 #define DEBUG_TYPE "code-metrics"
  27
  28 using namespace llvm;
  29
  30 static void
  31 appendSpeculatableOperands(const Value *V,
  32                            SmallPtrSetImpl<const Value *> &Visited,
  33                            SmallVectorImpl<const Value *> &Worklist) {
  34   const User *U = dyn_cast<User>(V);
  35   if (!U)
  36     return;
  37
  38   for (const Value *Operand : U->operands())
  39     if (Visited.insert(Operand).second)
  40       if (isSafeToSpeculativelyExecute(Operand))
  41         Worklist.push_back(Operand);
  42 }
  43
  44 static void completeEphemeralValues(SmallPtrSetImpl<const Value *> &Visited,
  45                                     SmallVectorImpl<const Value *> &Worklist,
  46                                     SmallPtrSetImpl<const Value *> &EphValues) {
  47   // Note: We don't speculate PHIs here, so we'll miss instruction chains kept
  48   // alive only by ephemeral values.
  49
  50   // Walk the worklist using an index but without caching the size so we can
  51   // append more entries as we process the worklist. This forms a queue without
  52   // quadratic behavior by just leaving processed nodes at the head of the
  53   // worklist forever.
  54   for (int i = 0; i < (int)Worklist.size(); ++i) {
  55     const Value *V = Worklist[i];
  56
  57     assert(Visited.count(V) &&
  58            "Failed to add a worklist entry to our visited set!");
  59
  60     // If all uses of this value are ephemeral, then so is this value.
  61     if (!all_of(V->users(), [&](const User *U) { return EphValues.count(U); }))
  62       continue;
  63
  64     EphValues.insert(V);
  65     DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n");
  66
  67     // Append any more operands to consider.
  68     appendSpeculatableOperands(V, Visited, Worklist);
  69   }
  70 }
  71
  72 // Find all ephemeral values.
  73 void CodeMetrics::collectEphemeralValues(
  74     const Loop *L, AssumptionCache *AC,
  75     SmallPtrSetImpl<const Value *> &EphValues) {
  76   SmallPtrSet<const Value *, 32> Visited;
  77   SmallVector<const Value *, 16> Worklist;
  78
  79   for (auto &AssumeVH : AC->assumptions()) {
  80     if (!AssumeVH)
  81       continue;
  82     Instruction *I = cast<Instruction>(AssumeVH);
  83
  84     // Filter out call sites outside of the loop so we don't do a function's
  85     // worth of work for each of its loops (and, in the common case, ephemeral
  86     // values in the loop are likely due to @llvm.assume calls in the loop).
  87     if (!L->contains(I->getParent()))
  88       continue;
  89
  90     if (EphValues.insert(I).second)
  91       appendSpeculatableOperands(I, Visited, Worklist);
  92   }
  93
  94   completeEphemeralValues(Visited, Worklist, EphValues);
  95 }
  96
  97 void CodeMetrics::collectEphemeralValues(
  98     const Function *F, AssumptionCache *AC,
  99     SmallPtrSetImpl<const Value *> &EphValues) {
 100   SmallPtrSet<const Value *, 32> Visited;
 101   SmallVector<const Value *, 16> Worklist;
 102
 103   for (auto &AssumeVH : AC->assumptions()) {
 104     if (!AssumeVH)
 105       continue;
 106     Instruction *I = cast<Instruction>(AssumeVH);
 107     assert(I->getParent()->getParent() == F &&
 108            "Found assumption for the wrong function!");
 109
 110     if (EphValues.insert(I).second)
 111       appendSpeculatableOperands(I, Visited, Worklist);
 112   }
 113
 114   completeEphemeralValues(Visited, Worklist, EphValues);
 115 }
 116
 117 /// Fill in the current structure with information gleaned from the specified
 118 /// block.
 119 void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB,
 120                                     const TargetTransformInfo &TTI,
 121                                     const SmallPtrSetImpl<const Value*> &EphValues) {
 122   ++NumBlocks;
 123   unsigned NumInstsBeforeThisBB = NumInsts;
 124   for (const Instruction &I : *BB) {
 125     // Skip ephemeral values.
 126     if (EphValues.count(&I))
 127       continue;
 128
 129     // Special handling for calls.
 130     if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
 131       ImmutableCallSite CS(&I);
 132
 133       if (const Function *F = CS.getCalledFunction()) {
 134         // If a function is both internal and has a single use, then it is
 135         // extremely likely to get inlined in the future (it was probably
 136         // exposed by an interleaved devirtualization pass).
 137         if (!CS.isNoInline() && F->hasInternalLinkage() && F->hasOneUse())
 138           ++NumInlineCandidates;
 139
 140         // If this call is to function itself, then the function is recursive.
 141         // Inlining it into other functions is a bad idea, because this is
 142         // basically just a form of loop peeling, and our metrics aren't useful
 143         // for that case.
 144         if (F == BB->getParent())
 145           isRecursive = true;
 146
 147         if (TTI.isLoweredToCall(F))
 148           ++NumCalls;
 149       } else {
 150         // We don't want inline asm to count as a call - that would prevent loop
 151         // unrolling. The argument setup cost is still real, though.
 152         if (!isa<InlineAsm>(CS.getCalledValue()))
 153           ++NumCalls;
 154       }
 155     }
 156
 157     if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {
 158       if (!AI->isStaticAlloca())
 159         this->usesDynamicAlloca = true;
 160     }
 161
 162     if (isa<ExtractElementInst>(I) || I.getType()->isVectorTy())
 163       ++NumVectorInsts;
 164
 165     if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
 166       notDuplicatable = true;
 167
 168     if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
 169       if (CI->cannotDuplicate())
 170         notDuplicatable = true;
 171       if (CI->isConvergent())
 172         convergent = true;
 173     }
 174
 175     if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
 176       if (InvI->cannotDuplicate())
 177         notDuplicatable = true;
 178
 179     NumInsts += TTI.getUserCost(&I);
 180   }
 181
 182   if (isa<ReturnInst>(BB->getTerminator()))
 183     ++NumRets;
 184
 185   // We never want to inline functions that contain an indirectbr.  This is
 186   // incorrect because all the blockaddress's (in static global initializers
 187   // for example) would be referring to the original function, and this indirect
 188   // jump would jump from the inlined copy of the function into the original
 189   // function which is extremely undefined behavior.
 190   // FIXME: This logic isn't really right; we can safely inline functions
 191   // with indirectbr's as long as no other function or global references the
 192   // blockaddress of a block within the current function.  And as a QOI issue,
 193   // if someone is using a blockaddress without an indirectbr, and that
 194   // reference somehow ends up in another function or global, we probably
 195   // don't want to inline this function.
 196   notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());
 197
 198   // Remember NumInsts for this BB.
 199   NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB;
 200 }