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