LLVM  6.0.0svn
CodeMetrics.cpp
Go to the documentation of this file.
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 
16 #include "llvm/Analysis/LoopInfo.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"
25 
26 #define DEBUG_TYPE "code-metrics"
27 
28 using namespace llvm;
29 
30 static void
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 
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.
74  const Loop *L, AssumptionCache *AC,
75  SmallPtrSetImpl<const Value *> &EphValues) {
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 
98  const Function *F, AssumptionCache *AC,
99  SmallPtrSetImpl<const Value *> &EphValues) {
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.
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())
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 }
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value *> &EphValues)
Collect a loop&#39;s ephemeral values (those used only by an assume or similar intrinsics in the loop)...
Definition: CodeMetrics.cpp:73
void push_back(const T &Elt)
Definition: SmallVector.h:212
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
bool convergent
True if this function contains a call to a convergent function.
Definition: CodeMetrics.h:57
LLVM_ATTRIBUTE_ALWAYS_INLINE size_type size() const
Definition: SmallVector.h:136
bool isRecursive
True if this function calls itself.
Definition: CodeMetrics.h:48
unsigned NumVectorInsts
How many instructions produce vector values.
Definition: CodeMetrics.h:83
unsigned NumCalls
Keep track of the number of calls to &#39;big&#39; functions.
Definition: CodeMetrics.h:72
This class represents a function call, abstracting a target machine&#39;s calling convention.
A cache of .assume calls within a function.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:816
unsigned NumInlineCandidates
The number of calls to internal functions with a single caller.
Definition: CodeMetrics.h:78
F(f)
bool notDuplicatable
True if this function cannot be duplicated.
Definition: CodeMetrics.h:54
bool isNoInline() const
Return true if the call should not be inlined.
Definition: CallSite.h:438
MutableArrayRef< WeakTrackingVH > assumptions()
Access the list of assumption handles currently tracked for this function.
unsigned NumBlocks
Number of analyzed blocks.
Definition: CodeMetrics.h:66
ValTy * getCalledValue() const
Return the pointer to function that is being called.
Definition: CallSite.h:100
static void appendSpeculatableOperands(const Value *V, SmallPtrSetImpl< const Value *> &Visited, SmallVectorImpl< const Value *> &Worklist)
Definition: CodeMetrics.cpp:31
bool usesDynamicAlloca
True if this function calls alloca (in the C sense).
Definition: CodeMetrics.h:60
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:363
void analyzeBasicBlock(const BasicBlock *BB, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value *> &EphValues)
Add information about a block to the current state.
op_range operands()
Definition: User.h:222
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:374
DenseMap< const BasicBlock *, unsigned > NumBBInsts
Keeps track of basic block code size estimates.
Definition: CodeMetrics.h:69
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:117
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:410
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
iterator_range< user_iterator > users()
Definition: Value.h:395
int getUserCost(const User *U, ArrayRef< const Value *> Operands) const
Estimate the cost of a given IR user when lowered.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:404
Establish a view to a call site for examination.
Definition: CallSite.h:695
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned NumRets
How many &#39;ret&#39; instructions the blocks contain.
Definition: CodeMetrics.h:86
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
FunTy * getCalledFunction() const
Return the function being called if this is a direct call, otherwise return null (if it&#39;s an indirect...
Definition: CallSite.h:107
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static void completeEphemeralValues(SmallPtrSetImpl< const Value *> &Visited, SmallVectorImpl< const Value *> &Worklist, SmallPtrSetImpl< const Value *> &EphValues)
Definition: CodeMetrics.cpp:44
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
LLVM Value Representation.
Definition: Value.h:73
bool isLoweredToCall(const Function *F) const
Test whether calls to a function lower to actual program function calls.
Invoke instruction.
#define DEBUG(X)
Definition: Debug.h:118
This pass exposes codegen information to IR-level passes.
unsigned NumInsts
Number of instructions in the analyzed blocks.
Definition: CodeMetrics.h:63
const BasicBlock * getParent() const
Definition: Instruction.h:66
an instruction to allocate memory on the stack
Definition: Instructions.h:60