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