1//===- CodeMetrics.cpp - Code cost measurements ---------------------------===//
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
7//===----------------------------------------------------------------------===//
9// This file implements code cost measurement utilities.
11//===----------------------------------------------------------------------===//
23 #define DEBUG_TYPE "code-metrics"
35 for (
const Value *Operand : U->operands())
36 if (Visited.
insert(Operand).second)
38 if (!
I->mayHaveSideEffects() && !
I->isTerminator())
45 // Note: We don't speculate PHIs here, so we'll miss instruction chains kept
46 // alive only by ephemeral values.
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
52 for (
int i = 0; i < (int)Worklist.
size(); ++i) {
53 const Value *V = Worklist[i];
56 "Failed to add a worklist entry to our visited set!");
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); }))
65 // Append any more operands to consider.
70// Find all ephemeral values.
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()))
105 assert(
I->getParent()->getParent() ==
F &&
106 "Found assumption for the wrong function!");
108 if (EphValues.
insert(
I).second)
120 for (
const auto *U :
I.users()) {
127/// Fill in the current structure with information gleaned from the specified
136 // Skip ephemeral values.
140 // Special handling for calls.
143 bool IsLoweredToCall =
TTI.isLoweredToCall(
F);
144 // If a function is both internal and has a single use, then it is
145 // extremely likely to get inlined in the future (it was probably
146 // exposed by an interleaved devirtualization pass).
147 // When preparing for LTO, liberally consider calls as inline
149 if (!
Call->isNoInline() && IsLoweredToCall &&
150 ((
F->hasInternalLinkage() &&
F->hasOneLiveUse()) ||
155 // If this call is to function itself, then the function is recursive.
156 // Inlining it into other functions is a bad idea, because this is
157 // basically just a form of loop peeling, and our metrics aren't useful
165 // We don't want inline asm to count as a call - that would prevent loop
166 // unrolling. The argument setup cost is still real, though.
167 if (!
Call->isInlineAsm())
173 if (!AI->isStaticAlloca())
181 I.isUsedOutsideOfBlock(BB)) {
183 <<
"\n Cannot duplicate a token value used outside "
184 "the current block (except convergence control).\n");
189 if (CB->cannotDuplicate())
191 // Compute a meet over the visited blocks for the following partial order:
193 // None -> { Controlled, ExtendedLoop, Uncontrolled}
194 // Controlled -> ExtendedLoop
197 CB->getConvergenceControlToken()) {
219 // We never want to inline functions that contain an indirectbr. This is
220 // incorrect because all the blockaddress's (in static global initializers
221 // for example) would be referring to the original function, and this indirect
222 // jump would jump from the inlined copy of the function into the original
223 // function which is extremely undefined behavior.
224 // FIXME: This logic isn't really right; we can safely inline functions
225 // with indirectbr's as long as no other function or global references the
226 // blockaddress of a block within the current function. And as a QOI issue,
227 // if someone is using a blockaddress without an indirectbr, and that
228 // reference somehow ends up in another function or global, we probably
229 // don't want to inline this function.
232 // Remember NumInsts for this BB.
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static bool extendsConvergenceOutsideLoop(const Instruction &I, const Loop *L)
static void appendSpeculatableOperands(const Value *V, SmallPtrSetImpl< const Value * > &Visited, SmallVectorImpl< const Value * > &Worklist)
static void completeEphemeralValues(SmallPtrSetImpl< const Value * > &Visited, SmallVectorImpl< const Value * > &Worklist, SmallPtrSetImpl< const Value * > &EphValues)
This file defines an InstructionCost class that is used when calculating the cost of an instruction,...
This file defines the SmallPtrSet class.
an instruction to allocate memory on the stack
A cache of @llvm.assume calls within a function.
MutableArrayRef< WeakVH > assumptions()
Access the list of assumption handles currently tracked for this function.
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Represents a single loop in the control flow graph.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
LLVM Value Representation.
This is an optimization pass for GlobalISel generic memory operations.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
bool usesDynamicAlloca
True if this function calls alloca (in the C sense).
unsigned NumBlocks
Number of analyzed blocks.
ConvergenceKind Convergence
The kind of convergence specified in this function.
bool notDuplicatable
True if this function cannot be duplicated.
unsigned NumInlineCandidates
The number of calls to internal functions with a single caller.
bool isRecursive
True if this function calls itself.
static LLVM_ABI 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).
unsigned NumRets
How many 'ret' instructions the blocks contain.
DenseMap< const BasicBlock *, InstructionCost > NumBBInsts
Keeps track of basic block code size estimates.
LLVM_ABI void analyzeBasicBlock(const BasicBlock *BB, const TargetTransformInfo &TTI, const SmallPtrSetImpl< const Value * > &EphValues, bool PrepareForLTO=false, const Loop *L=nullptr)
Add information about a block to the current state.
unsigned NumCalls
Keep track of the number of calls to 'big' functions.
unsigned NumVectorInsts
How many instructions produce vector values.
InstructionCost NumInsts
Code size cost of the analyzed blocks.