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