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