LLVM  13.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 (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 BasicBlock *BB, const TargetTransformInfo &TTI,
118  const SmallPtrSetImpl<const Value *> &EphValues, bool PrepareForLTO) {
119  ++NumBlocks;
120  // Use a proxy variable for NumInsts of type InstructionCost, so that it can
121  // use InstructionCost's arithmetic properties such as saturation when this
122  // feature is added to InstructionCost.
123  // When storing the value back to NumInsts, we can assume all costs are Valid
124  // because the IR should not contain any nodes that cannot be costed. If that
125  // happens the cost-model is broken.
126  InstructionCost NumInstsProxy = NumInsts;
127  InstructionCost NumInstsBeforeThisBB = NumInsts;
128  for (const Instruction &I : *BB) {
129  // Skip ephemeral values.
130  if (EphValues.count(&I))
131  continue;
132 
133  // Special handling for calls.
134  if (const auto *Call = dyn_cast<CallBase>(&I)) {
135  if (const Function *F = Call->getCalledFunction()) {
136  bool IsLoweredToCall = TTI.isLoweredToCall(F);
137  // If a function is both internal and has a single use, then it is
138  // extremely likely to get inlined in the future (it was probably
139  // exposed by an interleaved devirtualization pass).
140  // When preparing for LTO, liberally consider calls as inline
141  // candidates.
142  if (!Call->isNoInline() && IsLoweredToCall &&
143  ((F->hasInternalLinkage() && F->hasOneUse()) || PrepareForLTO)) {
145  }
146 
147  // If this call is to function itself, then the function is recursive.
148  // Inlining it into other functions is a bad idea, because this is
149  // basically just a form of loop peeling, and our metrics aren't useful
150  // for that case.
151  if (F == BB->getParent())
152  isRecursive = true;
153 
154  if (IsLoweredToCall)
155  ++NumCalls;
156  } else {
157  // We don't want inline asm to count as a call - that would prevent loop
158  // unrolling. The argument setup cost is still real, though.
159  if (!Call->isInlineAsm())
160  ++NumCalls;
161  }
162  }
163 
164  if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {
165  if (!AI->isStaticAlloca())
166  this->usesDynamicAlloca = true;
167  }
168 
169  if (isa<ExtractElementInst>(I) || I.getType()->isVectorTy())
170  ++NumVectorInsts;
171 
172  if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
173  notDuplicatable = true;
174 
175  if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
176  if (CI->cannotDuplicate())
177  notDuplicatable = true;
178  if (CI->isConvergent())
179  convergent = true;
180  }
181 
182  if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
183  if (InvI->cannotDuplicate())
184  notDuplicatable = true;
185 
187  NumInsts = *NumInstsProxy.getValue();
188  }
189 
190  if (isa<ReturnInst>(BB->getTerminator()))
191  ++NumRets;
192 
193  // We never want to inline functions that contain an indirectbr. This is
194  // incorrect because all the blockaddress's (in static global initializers
195  // for example) would be referring to the original function, and this indirect
196  // jump would jump from the inlined copy of the function into the original
197  // function which is extremely undefined behavior.
198  // FIXME: This logic isn't really right; we can safely inline functions
199  // with indirectbr's as long as no other function or global references the
200  // blockaddress of a block within the current function. And as a QOI issue,
201  // if someone is using a blockaddress without an indirectbr, and that
202  // reference somehow ends up in another function or global, we probably
203  // don't want to inline this function.
204  notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());
205 
206  // Remember NumInsts for this BB.
207  InstructionCost NumInstsThisBB = NumInstsProxy - NumInstsBeforeThisBB;
208  NumBBInsts[BB] = *NumInstsThisBB.getValue();
209 }
i
i
Definition: README.txt:29
llvm::InstructionCost
Definition: InstructionCost.h:26
AssumptionCache.h
llvm
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:68
llvm::User::operands
op_range operands()
Definition: User.h:242
llvm::isSafeToSpeculativelyExecute
bool isSafeToSpeculativelyExecute(const Value *V, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
Definition: ValueTracking.cpp:4499
llvm::Function
Definition: Function.h:61
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:41
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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:122
F
#define F(x, y, z)
Definition: MD5.cpp:56
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:132
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:1505
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:70
SmallPtrSet.h
LoopInfo.h
llvm::InvokeInst
Invoke instruction.
Definition: Instructions.h:3686
llvm::CodeMetrics::NumBlocks
unsigned NumBlocks
Number of analyzed blocks.
Definition: CodeMetrics.h:54
I
#define I(x, y, z)
Definition: MD5.cpp:59
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:275
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: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:41
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:223
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:146
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:1450
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:61
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
Debug.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:434
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