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 | |
13 | #include "llvm/Analysis/CodeMetrics.h" |
14 | #include "llvm/ADT/SmallPtrSet.h" |
15 | #include "llvm/Analysis/AssumptionCache.h" |
16 | #include "llvm/Analysis/LoopInfo.h" |
17 | #include "llvm/Analysis/TargetTransformInfo.h" |
18 | #include "llvm/IR/Function.h" |
19 | #include "llvm/Support/Debug.h" |
20 | #include "llvm/Support/InstructionCost.h" |
21 | |
22 | #define DEBUG_TYPE "code-metrics" |
23 | |
24 | using namespace llvm; |
25 | |
26 | static void |
27 | appendSpeculatableOperands(const Value *V, |
28 | SmallPtrSetImpl<const Value *> &Visited, |
29 | SmallVectorImpl<const Value *> &Worklist) { |
30 | const User *U = dyn_cast<User>(Val: V); |
31 | if (!U) |
32 | return; |
33 | |
34 | for (const Value *Operand : U->operands()) |
35 | if (Visited.insert(Ptr: Operand).second) |
36 | if (const auto *I = dyn_cast<Instruction>(Val: Operand)) |
37 | if (!I->mayHaveSideEffects() && !I->isTerminator()) |
38 | Worklist.push_back(Elt: I); |
39 | } |
40 | |
41 | static void completeEphemeralValues(SmallPtrSetImpl<const Value *> &Visited, |
42 | SmallVectorImpl<const Value *> &Worklist, |
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(Range: V->users(), P: [&](const User *U) { return EphValues.count(Ptr: U); })) |
59 | continue; |
60 | |
61 | EphValues.insert(Ptr: 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. |
70 | void CodeMetrics::collectEphemeralValues( |
71 | const Loop *L, AssumptionCache *AC, |
72 | SmallPtrSetImpl<const Value *> &EphValues) { |
73 | SmallPtrSet<const Value *, 32> Visited; |
74 | SmallVector<const Value *, 16> Worklist; |
75 | |
76 | for (auto &AssumeVH : AC->assumptions()) { |
77 | if (!AssumeVH) |
78 | continue; |
79 | Instruction *I = cast<Instruction>(Val&: 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(BB: I->getParent())) |
85 | continue; |
86 | |
87 | if (EphValues.insert(Ptr: I).second) |
88 | appendSpeculatableOperands(V: I, Visited, Worklist); |
89 | } |
90 | |
91 | completeEphemeralValues(Visited, Worklist, EphValues); |
92 | } |
93 | |
94 | void CodeMetrics::collectEphemeralValues( |
95 | const Function *F, AssumptionCache *AC, |
96 | SmallPtrSetImpl<const Value *> &EphValues) { |
97 | SmallPtrSet<const Value *, 32> Visited; |
98 | SmallVector<const Value *, 16> Worklist; |
99 | |
100 | for (auto &AssumeVH : AC->assumptions()) { |
101 | if (!AssumeVH) |
102 | continue; |
103 | Instruction *I = cast<Instruction>(Val&: AssumeVH); |
104 | assert(I->getParent()->getParent() == F && |
105 | "Found assumption for the wrong function!" ); |
106 | |
107 | if (EphValues.insert(Ptr: I).second) |
108 | appendSpeculatableOperands(V: 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. |
116 | void CodeMetrics::analyzeBasicBlock( |
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(Ptr: &I)) |
124 | continue; |
125 | |
126 | // Special handling for calls. |
127 | if (const auto *Call = dyn_cast<CallBase>(Val: &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)) { |
138 | ++NumInlineCandidates; |
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>(Val: &I)) { |
159 | if (!AI->isStaticAlloca()) |
160 | this->usesDynamicAlloca = true; |
161 | } |
162 | |
163 | if (isa<ExtractElementInst>(Val: 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>(Val: &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>(Val: &I)) |
177 | if (InvI->cannotDuplicate()) |
178 | notDuplicatable = true; |
179 | |
180 | NumInsts += TTI.getInstructionCost(U: &I, CostKind: TargetTransformInfo::TCK_CodeSize); |
181 | } |
182 | |
183 | if (isa<ReturnInst>(Val: 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>(Val: BB->getTerminator()); |
198 | |
199 | // Remember NumInsts for this BB. |
200 | InstructionCost NumInstsThisBB = NumInsts - NumInstsBeforeThisBB; |
201 | NumBBInsts[BB] = NumInstsThisBB; |
202 | } |
203 | |