LLVM  15.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"
18 #include "llvm/IR/Function.h"
19 #include "llvm/Support/Debug.h"
21 
22 #define DEBUG_TYPE "code-metrics"
23 
24 using namespace llvm;
25 
26 static void
30  const User *U = dyn_cast<User>(V);
31  if (!U)
32  return;
33 
34  for (const Value *Operand : U->operands())
35  if (Visited.insert(Operand).second)
36  if (const auto *I = dyn_cast<Instruction>(Operand))
37  if (!I->mayHaveSideEffects() && !I->isTerminator())
38  Worklist.push_back(I);
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 BasicBlock *BB, const TargetTransformInfo &TTI,
118  const SmallPtrSetImpl<const Value *> &EphValues, bool PrepareForLTO) {
119  ++NumBlocks;
120  InstructionCost 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  bool IsLoweredToCall = TTI.isLoweredToCall(F);
130  // If a function is both internal and has a single use, then it is
131  // extremely likely to get inlined in the future (it was probably
132  // exposed by an interleaved devirtualization pass).
133  // When preparing for LTO, liberally consider calls as inline
134  // candidates.
135  if (!Call->isNoInline() && IsLoweredToCall &&
136  ((F->hasInternalLinkage() && F->hasOneUse()) || PrepareForLTO)) {
138  }
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 (IsLoweredToCall)
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 (!Call->isInlineAsm())
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 
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  InstructionCost NumInstsThisBB = NumInsts - NumInstsBeforeThisBB;
200  NumBBInsts[BB] = NumInstsThisBB;
201 }
i
i
Definition: README.txt:29
llvm::InstructionCost
Definition: InstructionCost.h:29
AssumptionCache.h
llvm::CodeMetrics::NumInsts
InstructionCost NumInsts
Code size cost of the analyzed blocks.
Definition: CodeMetrics.h:52
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::LoopBase::contains
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
Definition: LoopInfo.h:138
completeEphemeralValues
static void completeEphemeralValues(SmallPtrSetImpl< const Value * > &Visited, SmallVectorImpl< const Value * > &Worklist, SmallPtrSetImpl< const Value * > &EphValues)
Definition: CodeMetrics.cpp:41
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:168
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:450
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:55
llvm::CodeMetrics::convergent
bool convergent
True if this function contains a call to a convergent function.
Definition: CodeMetrics.h:46
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:1617
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:49
llvm::Instruction
Definition: Instruction.h:42
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:70
SmallPtrSet.h
LoopInfo.h
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3763
llvm::CodeMetrics::NumBlocks
unsigned NumBlocks
Number of analyzed blocks.
Definition: CodeMetrics.h:55
llvm::CodeMetrics::NumBBInsts
DenseMap< const BasicBlock *, InstructionCost > NumBBInsts
Keeps track of basic block code size estimates.
Definition: CodeMetrics.h:58
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:43
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::TargetTransformInfo::isLoweredToCall
bool isLoweredToCall(const Function *F) const
Test whether calls to a function lower to actual program function calls.
Definition: TargetTransformInfo.cpp:284
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:116
llvm::CodeMetrics::isRecursive
bool isRecursive
True if this function calls itself.
Definition: CodeMetrics.h:37
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:383
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:222
llvm::CodeMetrics::NumCalls
unsigned NumCalls
Keep track of the number of calls to 'big' functions.
Definition: CodeMetrics.h:61
Function.h
llvm::CodeMetrics::NumRets
unsigned NumRets
How many 'ret' instructions the blocks contain.
Definition: CodeMetrics.h:75
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:27
llvm::SmallVectorImpl< const Value * >
llvm::SmallPtrSetImpl< const Value * >
llvm::CodeMetrics::NumVectorInsts
unsigned NumVectorInsts
How many instructions produce vector values.
Definition: CodeMetrics.h:72
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1461
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:58
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:67
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:365