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