LLVM  16.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->hasOneLiveUse()) ||
137  PrepareForLTO)) {
139  }
140 
141  // If this call is to function itself, then the function is recursive.
142  // Inlining it into other functions is a bad idea, because this is
143  // basically just a form of loop peeling, and our metrics aren't useful
144  // for that case.
145  if (F == BB->getParent())
146  isRecursive = true;
147 
148  if (IsLoweredToCall)
149  ++NumCalls;
150  } else {
151  // We don't want inline asm to count as a call - that would prevent loop
152  // unrolling. The argument setup cost is still real, though.
153  if (!Call->isInlineAsm())
154  ++NumCalls;
155  }
156  }
157 
158  if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {
159  if (!AI->isStaticAlloca())
160  this->usesDynamicAlloca = true;
161  }
162 
163  if (isa<ExtractElementInst>(I) || I.getType()->isVectorTy())
164  ++NumVectorInsts;
165 
166  if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
167  notDuplicatable = true;
168 
169  if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
170  if (CI->cannotDuplicate())
171  notDuplicatable = true;
172  if (CI->isConvergent())
173  convergent = true;
174  }
175 
176  if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
177  if (InvI->cannotDuplicate())
178  notDuplicatable = true;
179 
181  }
182 
183  if (isa<ReturnInst>(BB->getTerminator()))
184  ++NumRets;
185 
186  // We never want to inline functions that contain an indirectbr. This is
187  // incorrect because all the blockaddress's (in static global initializers
188  // for example) would be referring to the original function, and this indirect
189  // jump would jump from the inlined copy of the function into the original
190  // function which is extremely undefined behavior.
191  // FIXME: This logic isn't really right; we can safely inline functions
192  // with indirectbr's as long as no other function or global references the
193  // blockaddress of a block within the current function. And as a QOI issue,
194  // if someone is using a blockaddress without an indirectbr, and that
195  // reference somehow ends up in another function or global, we probably
196  // don't want to inline this function.
197  notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());
198 
199  // Remember NumInsts for this BB.
200  InstructionCost NumInstsThisBB = NumInsts - NumInstsBeforeThisBB;
201  NumBBInsts[BB] = NumInstsThisBB;
202 }
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:18
llvm::TargetTransformInfo::getInstructionCost
InstructionCost getInstructionCost(const User *U, ArrayRef< const Value * > Operands, TargetCostKind CostKind) const
Estimate the cost of a given IR user when lowered.
Definition: TargetTransformInfo.cpp:224
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:1182
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:172
llvm::TargetTransformInfo::TCK_CodeSize
@ TCK_CodeSize
Instruction code size.
Definition: TargetTransformInfo.h:220
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:1590
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:3811
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:286
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::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:1474
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:59
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