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/Analysis/ValueTracking.h"
19 #include "llvm/IR/Function.h"
20 #include "llvm/Support/Debug.h"
21
22 #define DEBUG_TYPE "code-metrics"
23
24 using namespace llvm;
25
26 static void
appendSpeculatableOperands(const Value * V,SmallPtrSetImpl<const Value * > & Visited,SmallVectorImpl<const Value * > & Worklist)27 appendSpeculatableOperands(const Value *V,
28 SmallPtrSetImpl<const Value *> &Visited,
29 SmallVectorImpl<const Value *> &Worklist) {
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 (isSafeToSpeculativelyExecute(Operand))
37 Worklist.push_back(Operand);
38 }
39
completeEphemeralValues(SmallPtrSetImpl<const Value * > & Visited,SmallVectorImpl<const Value * > & Worklist,SmallPtrSetImpl<const Value * > & EphValues)40 static void completeEphemeralValues(SmallPtrSetImpl<const Value *> &Visited,
41 SmallVectorImpl<const Value *> &Worklist,
42 SmallPtrSetImpl<const Value *> &EphValues) {
43 // Note: We don't speculate PHIs here, so we'll miss instruction chains kept
44 // alive only by ephemeral values.
45
46 // Walk the worklist using an index but without caching the size so we can
47 // append more entries as we process the worklist. This forms a queue without
48 // quadratic behavior by just leaving processed nodes at the head of the
49 // worklist forever.
50 for (int i = 0; i < (int)Worklist.size(); ++i) {
51 const Value *V = Worklist[i];
52
53 assert(Visited.count(V) &&
54 "Failed to add a worklist entry to our visited set!");
55
56 // If all uses of this value are ephemeral, then so is this value.
57 if (!all_of(V->users(), [&](const User *U) { return EphValues.count(U); }))
58 continue;
59
60 EphValues.insert(V);
61 LLVM_DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n");
62
63 // Append any more operands to consider.
64 appendSpeculatableOperands(V, Visited, Worklist);
65 }
66 }
67
68 // Find all ephemeral values.
collectEphemeralValues(const Loop * L,AssumptionCache * AC,SmallPtrSetImpl<const Value * > & EphValues)69 void CodeMetrics::collectEphemeralValues(
70 const Loop *L, AssumptionCache *AC,
71 SmallPtrSetImpl<const Value *> &EphValues) {
72 SmallPtrSet<const Value *, 32> Visited;
73 SmallVector<const Value *, 16> Worklist;
74
75 for (auto &AssumeVH : AC->assumptions()) {
76 if (!AssumeVH)
77 continue;
78 Instruction *I = cast<Instruction>(AssumeVH);
79
80 // Filter out call sites outside of the loop so we don't do a function's
81 // worth of work for each of its loops (and, in the common case, ephemeral
82 // values in the loop are likely due to @llvm.assume calls in the loop).
83 if (!L->contains(I->getParent()))
84 continue;
85
86 if (EphValues.insert(I).second)
87 appendSpeculatableOperands(I, Visited, Worklist);
88 }
89
90 completeEphemeralValues(Visited, Worklist, EphValues);
91 }
92
collectEphemeralValues(const Function * F,AssumptionCache * AC,SmallPtrSetImpl<const Value * > & EphValues)93 void CodeMetrics::collectEphemeralValues(
94 const Function *F, AssumptionCache *AC,
95 SmallPtrSetImpl<const Value *> &EphValues) {
96 SmallPtrSet<const Value *, 32> Visited;
97 SmallVector<const Value *, 16> Worklist;
98
99 for (auto &AssumeVH : AC->assumptions()) {
100 if (!AssumeVH)
101 continue;
102 Instruction *I = cast<Instruction>(AssumeVH);
103 assert(I->getParent()->getParent() == F &&
104 "Found assumption for the wrong function!");
105
106 if (EphValues.insert(I).second)
107 appendSpeculatableOperands(I, Visited, Worklist);
108 }
109
110 completeEphemeralValues(Visited, Worklist, EphValues);
111 }
112
113 /// Fill in the current structure with information gleaned from the specified
114 /// block.
analyzeBasicBlock(const BasicBlock * BB,const TargetTransformInfo & TTI,const SmallPtrSetImpl<const Value * > & EphValues)115 void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB,
116 const TargetTransformInfo &TTI,
117 const SmallPtrSetImpl<const Value*> &EphValues) {
118 ++NumBlocks;
119 unsigned NumInstsBeforeThisBB = NumInsts;
120 for (const Instruction &I : *BB) {
121 // Skip ephemeral values.
122 if (EphValues.count(&I))
123 continue;
124
125 // Special handling for calls.
126 if (const auto *Call = dyn_cast<CallBase>(&I)) {
127 if (const Function *F = Call->getCalledFunction()) {
128 // If a function is both internal and has a single use, then it is
129 // extremely likely to get inlined in the future (it was probably
130 // exposed by an interleaved devirtualization pass).
131 if (!Call->isNoInline() && F->hasInternalLinkage() && F->hasOneUse())
132 ++NumInlineCandidates;
133
134 // If this call is to function itself, then the function is recursive.
135 // Inlining it into other functions is a bad idea, because this is
136 // basically just a form of loop peeling, and our metrics aren't useful
137 // for that case.
138 if (F == BB->getParent())
139 isRecursive = true;
140
141 if (TTI.isLoweredToCall(F))
142 ++NumCalls;
143 } else {
144 // We don't want inline asm to count as a call - that would prevent loop
145 // unrolling. The argument setup cost is still real, though.
146 if (!Call->isInlineAsm())
147 ++NumCalls;
148 }
149 }
150
151 if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {
152 if (!AI->isStaticAlloca())
153 this->usesDynamicAlloca = true;
154 }
155
156 if (isa<ExtractElementInst>(I) || I.getType()->isVectorTy())
157 ++NumVectorInsts;
158
159 if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
160 notDuplicatable = true;
161
162 if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
163 if (CI->cannotDuplicate())
164 notDuplicatable = true;
165 if (CI->isConvergent())
166 convergent = true;
167 }
168
169 if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
170 if (InvI->cannotDuplicate())
171 notDuplicatable = true;
172
173 NumInsts += TTI.getUserCost(&I, TargetTransformInfo::TCK_CodeSize);
174 }
175
176 if (isa<ReturnInst>(BB->getTerminator()))
177 ++NumRets;
178
179 // We never want to inline functions that contain an indirectbr. This is
180 // incorrect because all the blockaddress's (in static global initializers
181 // for example) would be referring to the original function, and this indirect
182 // jump would jump from the inlined copy of the function into the original
183 // function which is extremely undefined behavior.
184 // FIXME: This logic isn't really right; we can safely inline functions
185 // with indirectbr's as long as no other function or global references the
186 // blockaddress of a block within the current function. And as a QOI issue,
187 // if someone is using a blockaddress without an indirectbr, and that
188 // reference somehow ends up in another function or global, we probably
189 // don't want to inline this function.
190 notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());
191
192 // Remember NumInsts for this BB.
193 NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB;
194 }
195