LLVM  14.0.0git
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 
14 #include "llvm/ADT/SmallPtrSet.h"
16 #include "llvm/Analysis/LoopInfo.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 (const auto *I = dyn_cast<Instruction>(Operand))
38  if (!I->mayHaveSideEffects() && !I->isTerminator())
39  Worklist.push_back(I);
40 }
41 
44  SmallPtrSetImpl<const Value *> &EphValues) {
45  // Note: We don't speculate PHIs here, so we'll miss instruction chains kept
46  // alive only by ephemeral values.
47 
48  // Walk the worklist using an index but without caching the size so we can
49  // append more entries as we process the worklist. This forms a queue without
50  // quadratic behavior by just leaving processed nodes at the head of the
51  // worklist forever.
52  for (int i = 0; i < (int)Worklist.size(); ++i) {
53  const Value *V = Worklist[i];
54 
55  assert(Visited.count(V) &&
56  "Failed to add a worklist entry to our visited set!");
57 
58  // If all uses of this value are ephemeral, then so is this value.
59  if (!all_of(V->users(), [&](const User *U) { return EphValues.count(U); }))
60  continue;
61 
62  EphValues.insert(V);
63  LLVM_DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n");
64 
65  // Append any more operands to consider.
66  appendSpeculatableOperands(V, Visited, Worklist);
67  }
68 }
69 
70 // Find all ephemeral values.
72  const Loop *L, AssumptionCache *AC,
73  SmallPtrSetImpl<const Value *> &EphValues) {
76 
77  for (auto &AssumeVH : AC->assumptions()) {
78  if (!AssumeVH)
79  continue;
80  Instruction *I = cast<Instruction>(AssumeVH);
81 
82  // Filter out call sites outside of the loop so we don't do a function's
83  // worth of work for each of its loops (and, in the common case, ephemeral
84  // values in the loop are likely due to @llvm.assume calls in the loop).
85  if (!L->contains(I->getParent()))
86  continue;
87 
88  if (EphValues.insert(I).second)
89  appendSpeculatableOperands(I, Visited, Worklist);
90  }
91 
92  completeEphemeralValues(Visited, Worklist, EphValues);
93 }
94 
96  const Function *F, AssumptionCache *AC,
97  SmallPtrSetImpl<const Value *> &EphValues) {
100 
101  for (auto &AssumeVH : AC->assumptions()) {
102  if (!AssumeVH)
103  continue;
104  Instruction *I = cast<Instruction>(AssumeVH);
105  assert(I->getParent()->getParent() == F &&
106  "Found assumption for the wrong function!");
107 
108  if (EphValues.insert(I).second)
109  appendSpeculatableOperands(I, Visited, Worklist);
110  }
111 
112  completeEphemeralValues(Visited, Worklist, EphValues);
113 }
114 
115 /// Fill in the current structure with information gleaned from the specified
116 /// block.
118  const BasicBlock *BB, const TargetTransformInfo &TTI,
119  const SmallPtrSetImpl<const Value *> &EphValues, bool PrepareForLTO) {
120  ++NumBlocks;
121  // Use a proxy variable for NumInsts of type InstructionCost, so that it can
122  // use InstructionCost's arithmetic properties such as saturation when this
123  // feature is added to InstructionCost.
124  // When storing the value back to NumInsts, we can assume all costs are Valid
125  // because the IR should not contain any nodes that cannot be costed. If that
126  // happens the cost-model is broken.
127  InstructionCost NumInstsProxy = NumInsts;
128  InstructionCost NumInstsBeforeThisBB = NumInsts;
129  for (const Instruction &I : *BB) {
130  // Skip ephemeral values.
131  if (EphValues.count(&I))
132  continue;
133 
134  // Special handling for calls.
135  if (const auto *Call = dyn_cast<CallBase>(&I)) {
136  if (const Function *F = Call->getCalledFunction()) {
137  bool IsLoweredToCall = TTI.isLoweredToCall(F);
138  // If a function is both internal and has a single use, then it is
139  // extremely likely to get inlined in the future (it was probably
140  // exposed by an interleaved devirtualization pass).
141  // When preparing for LTO, liberally consider calls as inline
142  // candidates.
143  if (!Call->isNoInline() && IsLoweredToCall &&
144  ((F->hasInternalLinkage() && F->hasOneUse()) || PrepareForLTO)) {
146  }
147 
148  // If this call is to function itself, then the function is recursive.
149  // Inlining it into other functions is a bad idea, because this is
150  // basically just a form of loop peeling, and our metrics aren't useful
151  // for that case.
152  if (F == BB->getParent())
153  isRecursive = true;
154 
155  if (IsLoweredToCall)
156  ++NumCalls;
157  } else {
158  // We don't want inline asm to count as a call - that would prevent loop
159  // unrolling. The argument setup cost is still real, though.
160  if (!Call->isInlineAsm())
161  ++NumCalls;
162  }
163  }
164 
165  if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {
166  if (!AI->isStaticAlloca())
167  this->usesDynamicAlloca = true;
168  }
169 
170  if (isa<ExtractElementInst>(I) || I.getType()->isVectorTy())
171  ++NumVectorInsts;
172 
173  if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
174  notDuplicatable = true;
175 
176  if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
177  if (CI->cannotDuplicate())
178  notDuplicatable = true;
179  if (CI->isConvergent())
180  convergent = true;
181  }
182 
183  if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
184  if (InvI->cannotDuplicate())
185  notDuplicatable = true;
186 
188  NumInsts = *NumInstsProxy.getValue();
189  }
190 
191  if (isa<ReturnInst>(BB->getTerminator()))
192  ++NumRets;
193 
194  // We never want to inline functions that contain an indirectbr. This is
195  // incorrect because all the blockaddress's (in static global initializers
196  // for example) would be referring to the original function, and this indirect
197  // jump would jump from the inlined copy of the function into the original
198  // function which is extremely undefined behavior.
199  // FIXME: This logic isn't really right; we can safely inline functions
200  // with indirectbr's as long as no other function or global references the
201  // blockaddress of a block within the current function. And as a QOI issue,
202  // if someone is using a blockaddress without an indirectbr, and that
203  // reference somehow ends up in another function or global, we probably
204  // don't want to inline this function.
205  notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());
206 
207  // Remember NumInsts for this BB.
208  InstructionCost NumInstsThisBB = NumInstsProxy - NumInstsBeforeThisBB;
209  NumBBInsts[BB] = *NumInstsThisBB.getValue();
210 }
i
i
Definition: README.txt:29
llvm::InstructionCost
Definition: InstructionCost.h:29
AssumptionCache.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::InstructionCost::getValue
Optional< CostType > getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
Definition: InstructionCost.h:87
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::Function
Definition: Function.h:62
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:122
completeEphemeralValues
static void completeEphemeralValues(SmallPtrSetImpl< const Value * > &Visited, SmallVectorImpl< const Value * > &Worklist, SmallPtrSetImpl< const Value * > &EphValues)
Definition: CodeMetrics.cpp:42
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1177
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
ValueTracking.h
llvm::CodeMetrics::NumInsts
unsigned NumInsts
Number of instructions in the analyzed blocks.
Definition: CodeMetrics.h:51
llvm::TargetTransformInfo::TCK_CodeSize
@ TCK_CodeSize
Instruction code size.
Definition: TargetTransformInfo.h:214
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::CodeMetrics::convergent
bool convergent
True if this function contains a call to a convergent function.
Definition: CodeMetrics.h:45
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CodeMetrics.h
llvm::all_of
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:1649
llvm::User
Definition: User.h:44
int
Clang compiles this i1 i64 store i64 i64 store i64 i64 store i64 i64 store i64 align Which gets codegen d xmm0 movaps rbp movaps rbp movaps rbp movaps rbp rbp rbp rbp rbp It would be better to have movq s of instead of the movaps s LLVM produces ret int
Definition: README.txt:536
llvm::CodeMetrics::usesDynamicAlloca
bool usesDynamicAlloca
True if this function calls alloca (in the C sense).
Definition: CodeMetrics.h:48
llvm::Instruction
Definition: Instruction.h:45
llvm::CodeMetrics::collectEphemeralValues
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
Definition: CodeMetrics.cpp:71
SmallPtrSet.h
LoopInfo.h
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3769
llvm::CodeMetrics::NumBlocks
unsigned NumBlocks
Number of analyzed blocks.
Definition: CodeMetrics.h:54
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::CodeMetrics::notDuplicatable
bool notDuplicatable
True if this function cannot be duplicated.
Definition: CodeMetrics.h:42
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CodeMetrics::NumBBInsts
DenseMap< const BasicBlock *, unsigned > NumBBInsts
Keeps track of basic block code size estimates.
Definition: CodeMetrics.h:57
llvm::TargetTransformInfo::isLoweredToCall
bool isLoweredToCall(const Function *F) const
Test whether calls to a function lower to actual program function calls.
Definition: TargetTransformInfo.cpp:281
llvm::CodeMetrics::analyzeBasicBlock
void analyzeBasicBlock(const BasicBlock *BB, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value * > &EphValues, bool PrepareForLTO=false)
Add information about a block to the current state.
Definition: CodeMetrics.cpp:117
llvm::CodeMetrics::isRecursive
bool isRecursive
True if this function calls itself.
Definition: CodeMetrics.h:36
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
InstructionCost.h
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::TargetTransformInfo::getUserCost
InstructionCost getUserCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
Definition: TargetTransformInfo.cpp:219
llvm::CodeMetrics::NumCalls
unsigned NumCalls
Keep track of the number of calls to 'big' functions.
Definition: CodeMetrics.h:60
Function.h
llvm::CodeMetrics::NumRets
unsigned NumRets
How many 'ret' instructions the blocks contain.
Definition: CodeMetrics.h:74
llvm::AssumptionCache::assumptions
MutableArrayRef< ResultElem > assumptions()
Access the list of assumption handles currently tracked for this function.
Definition: AssumptionCache.h:150
TargetTransformInfo.h
appendSpeculatableOperands
static void appendSpeculatableOperands(const Value *V, SmallPtrSetImpl< const Value * > &Visited, SmallVectorImpl< const Value * > &Worklist)
Definition: CodeMetrics.cpp:28
llvm::SmallVectorImpl< const Value * >
llvm::SmallPtrSetImpl< const Value * >
llvm::CodeMetrics::NumVectorInsts
unsigned NumVectorInsts
How many instructions produce vector values.
Definition: CodeMetrics.h:71
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1478
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:62
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::CodeMetrics::NumInlineCandidates
unsigned NumInlineCandidates
The number of calls to internal functions with a single caller.
Definition: CodeMetrics.h:66
llvm::SmallPtrSetImpl::insert
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:364