LLVM  10.0.0svn
CodeMetrics.cpp
Go to the documentation of this file.
1 //===- CodeMetrics.cpp - Code cost measurements ---------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements code cost measurement utilities.
10 //
11 //===----------------------------------------------------------------------===//
12 
15 #include "llvm/Analysis/LoopInfo.h"
18 #include "llvm/IR/DataLayout.h"
19 #include "llvm/IR/Function.h"
20 #include "llvm/Support/Debug.h"
22 
23 #define DEBUG_TYPE "code-metrics"
24 
25 using namespace llvm;
26 
27 static void
31  const User *U = dyn_cast<User>(V);
32  if (!U)
33  return;
34 
35  for (const Value *Operand : U->operands())
36  if (Visited.insert(Operand).second)
37  if (isSafeToSpeculativelyExecute(Operand))
38  Worklist.push_back(Operand);
39 }
40 
43  SmallPtrSetImpl<const Value *> &EphValues) {
44  // Note: We don't speculate PHIs here, so we'll miss instruction chains kept
45  // alive only by ephemeral values.
46 
47  // Walk the worklist using an index but without caching the size so we can
48  // append more entries as we process the worklist. This forms a queue without
49  // quadratic behavior by just leaving processed nodes at the head of the
50  // worklist forever.
51  for (int i = 0; i < (int)Worklist.size(); ++i) {
52  const Value *V = Worklist[i];
53 
54  assert(Visited.count(V) &&
55  "Failed to add a worklist entry to our visited set!");
56 
57  // If all uses of this value are ephemeral, then so is this value.
58  if (!all_of(V->users(), [&](const User *U) { return EphValues.count(U); }))
59  continue;
60 
61  EphValues.insert(V);
62  LLVM_DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n");
63 
64  // Append any more operands to consider.
65  appendSpeculatableOperands(V, Visited, Worklist);
66  }
67 }
68 
69 // Find all ephemeral values.
71  const Loop *L, AssumptionCache *AC,
72  SmallPtrSetImpl<const Value *> &EphValues) {
75 
76  for (auto &AssumeVH : AC->assumptions()) {
77  if (!AssumeVH)
78  continue;
79  Instruction *I = cast<Instruction>(AssumeVH);
80 
81  // Filter out call sites outside of the loop so we don't do a function's
82  // worth of work for each of its loops (and, in the common case, ephemeral
83  // values in the loop are likely due to @llvm.assume calls in the loop).
84  if (!L->contains(I->getParent()))
85  continue;
86 
87  if (EphValues.insert(I).second)
88  appendSpeculatableOperands(I, Visited, Worklist);
89  }
90 
91  completeEphemeralValues(Visited, Worklist, EphValues);
92 }
93 
95  const Function *F, AssumptionCache *AC,
96  SmallPtrSetImpl<const Value *> &EphValues) {
99 
100  for (auto &AssumeVH : AC->assumptions()) {
101  if (!AssumeVH)
102  continue;
103  Instruction *I = cast<Instruction>(AssumeVH);
104  assert(I->getParent()->getParent() == F &&
105  "Found assumption for the wrong function!");
106 
107  if (EphValues.insert(I).second)
108  appendSpeculatableOperands(I, Visited, Worklist);
109  }
110 
111  completeEphemeralValues(Visited, Worklist, EphValues);
112 }
113 
114 /// Fill in the current structure with information gleaned from the specified
115 /// block.
117  const TargetTransformInfo &TTI,
118  const SmallPtrSetImpl<const Value*> &EphValues) {
119  ++NumBlocks;
120  unsigned NumInstsBeforeThisBB = NumInsts;
121  for (const Instruction &I : *BB) {
122  // Skip ephemeral values.
123  if (EphValues.count(&I))
124  continue;
125 
126  // Special handling for calls.
127  if (const auto *Call = dyn_cast<CallBase>(&I)) {
128  if (const Function *F = Call->getCalledFunction()) {
129  // If a function is both internal and has a single use, then it is
130  // extremely likely to get inlined in the future (it was probably
131  // exposed by an interleaved devirtualization pass).
132  if (!Call->isNoInline() && F->hasInternalLinkage() && F->hasOneUse())
134 
135  // If this call is to function itself, then the function is recursive.
136  // Inlining it into other functions is a bad idea, because this is
137  // basically just a form of loop peeling, and our metrics aren't useful
138  // for that case.
139  if (F == BB->getParent())
140  isRecursive = true;
141 
142  if (TTI.isLoweredToCall(F))
143  ++NumCalls;
144  } else {
145  // We don't want inline asm to count as a call - that would prevent loop
146  // unrolling. The argument setup cost is still real, though.
147  if (!Call->isInlineAsm())
148  ++NumCalls;
149  }
150  }
151 
152  if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {
153  if (!AI->isStaticAlloca())
154  this->usesDynamicAlloca = true;
155  }
156 
157  if (isa<ExtractElementInst>(I) || I.getType()->isVectorTy())
158  ++NumVectorInsts;
159 
160  if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
161  notDuplicatable = true;
162 
163  if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
164  if (CI->cannotDuplicate())
165  notDuplicatable = true;
166  if (CI->isConvergent())
167  convergent = true;
168  }
169 
170  if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
171  if (InvI->cannotDuplicate())
172  notDuplicatable = true;
173 
174  NumInsts += TTI.getUserCost(&I);
175  }
176 
177  if (isa<ReturnInst>(BB->getTerminator()))
178  ++NumRets;
179 
180  // We never want to inline functions that contain an indirectbr. This is
181  // incorrect because all the blockaddress's (in static global initializers
182  // for example) would be referring to the original function, and this indirect
183  // jump would jump from the inlined copy of the function into the original
184  // function which is extremely undefined behavior.
185  // FIXME: This logic isn't really right; we can safely inline functions
186  // with indirectbr's as long as no other function or global references the
187  // blockaddress of a block within the current function. And as a QOI issue,
188  // if someone is using a blockaddress without an indirectbr, and that
189  // reference somehow ends up in another function or global, we probably
190  // don't want to inline this function.
191  notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());
192 
193  // Remember NumInsts for this BB.
194  NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB;
195 }
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:70
This class represents lattice values for constants.
Definition: AllocatorList.h:23
bool convergent
True if this function contains a call to a convergent function.
Definition: CodeMetrics.h:47
bool isRecursive
True if this function calls itself.
Definition: CodeMetrics.h:38
unsigned NumVectorInsts
How many instructions produce vector values.
Definition: CodeMetrics.h:73
void push_back(const T &Elt)
Definition: SmallVector.h:211
unsigned NumCalls
Keep track of the number of calls to &#39;big&#39; functions.
Definition: CodeMetrics.h:62
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:1165
unsigned NumInlineCandidates
The number of calls to internal functions with a single caller.
Definition: CodeMetrics.h:68
F(f)
bool notDuplicatable
True if this function cannot be duplicated.
Definition: CodeMetrics.h:44
MutableArrayRef< WeakTrackingVH > assumptions()
Access the list of assumption handles currently tracked for this function.
unsigned NumBlocks
Number of analyzed blocks.
Definition: CodeMetrics.h:56
static void appendSpeculatableOperands(const Value *V, SmallPtrSetImpl< const Value *> &Visited, SmallVectorImpl< const Value *> &Worklist)
Definition: CodeMetrics.cpp:28
bool usesDynamicAlloca
True if this function calls alloca (in the C sense).
Definition: CodeMetrics.h:50
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
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:370
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:237
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
size_t size() const
Definition: SmallVector.h:52
DenseMap< const BasicBlock *, unsigned > NumBBInsts
Keeps track of basic block code size estimates.
Definition: CodeMetrics.h:59
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:115
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
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:837
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:419
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:509
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:106
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned NumRets
How many &#39;ret&#39; instructions the blocks contain.
Definition: CodeMetrics.h:76
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:332
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:41
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:122
unsigned NumInsts
Number of instructions in the analyzed blocks.
Definition: CodeMetrics.h:53
const BasicBlock * getParent() const
Definition: Instruction.h:66
an instruction to allocate memory on the stack
Definition: Instructions.h:59