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