Bug Summary

File:src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/ScaledNumber.h
Warning:line 790, column 14
The result of the left shift is undefined due to shifting by '16383', which is greater or equal to the width of type 'unsigned long long'

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple amd64-unknown-openbsd7.0 -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ModuleSummaryAnalysis.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 1 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -resource-dir /usr/local/lib/clang/13.0.0 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/AMDGPU -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Analysis -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ASMParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/BinaryFormat -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitcode -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Bitstream -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /include/llvm/CodeGen -I /include/llvm/CodeGen/PBQP -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Coroutines -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData/Coverage -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/CodeView -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/DWARF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/MSF -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/PDB -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Demangle -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/JITLink -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ExecutionEngine/Orc -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenACC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Frontend/OpenMP -I /include/llvm/CodeGen/GlobalISel -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IRReader -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/Transforms/InstCombine -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/LTO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Linker -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/MC/MCParser -I /include/llvm/CodeGen/MIRParser -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Object -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Option -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Passes -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ProfileData -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Scalar -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/ADT -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/DebugInfo/Symbolize -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Target -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Utils -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/Vectorize -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include/llvm/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Target/X86 -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Transforms/IPO -I /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include -I /usr/src/gnu/usr.bin/clang/libLLVM/../include -I /usr/src/gnu/usr.bin/clang/libLLVM/obj -I /usr/src/gnu/usr.bin/clang/libLLVM/obj/../include -D NDEBUG -D __STDC_LIMIT_MACROS -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D LLVM_PREFIX="/usr" -D PIC -internal-isystem /usr/include/c++/v1 -internal-isystem /usr/local/lib/clang/13.0.0/include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/usr/src/gnu/usr.bin/clang/libLLVM/obj -ferror-limit 19 -fvisibility-inlines-hidden -fwrapv -D_RET_PROTECTOR -ret-protector -fno-rtti -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -fno-builtin-malloc -fno-builtin-calloc -fno-builtin-realloc -fno-builtin-valloc -fno-builtin-free -fno-builtin-strdup -fno-builtin-strndup -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /home/ben/Projects/vmm/scan-build/2022-01-12-194120-40624-1 -x c++ /usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Analysis/ModuleSummaryAnalysis.cpp

→
1//===- ModuleSummaryAnalysis.cpp - Module summary index builder -----------===//
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 pass builds a ModuleSummaryIndex object for the module, to be written
10// to bitcode or LLVM assembly.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/Analysis/ModuleSummaryAnalysis.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/DenseSet.h"
17#include "llvm/ADT/MapVector.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SetVector.h"
20#include "llvm/ADT/SmallPtrSet.h"
21#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/StringRef.h"
23#include "llvm/Analysis/BlockFrequencyInfo.h"
24#include "llvm/Analysis/BranchProbabilityInfo.h"
25#include "llvm/Analysis/IndirectCallPromotionAnalysis.h"
26#include "llvm/Analysis/LoopInfo.h"
27#include "llvm/Analysis/ProfileSummaryInfo.h"
28#include "llvm/Analysis/StackSafetyAnalysis.h"
29#include "llvm/Analysis/TypeMetadataUtils.h"
30#include "llvm/IR/Attributes.h"
31#include "llvm/IR/BasicBlock.h"
32#include "llvm/IR/Constant.h"
33#include "llvm/IR/Constants.h"
34#include "llvm/IR/Dominators.h"
35#include "llvm/IR/Function.h"
36#include "llvm/IR/GlobalAlias.h"
37#include "llvm/IR/GlobalValue.h"
38#include "llvm/IR/GlobalVariable.h"
39#include "llvm/IR/Instructions.h"
40#include "llvm/IR/IntrinsicInst.h"
41#include "llvm/IR/Intrinsics.h"
42#include "llvm/IR/Metadata.h"
43#include "llvm/IR/Module.h"
44#include "llvm/IR/ModuleSummaryIndex.h"
45#include "llvm/IR/Use.h"
46#include "llvm/IR/User.h"
47#include "llvm/InitializePasses.h"
48#include "llvm/Object/ModuleSymbolTable.h"
49#include "llvm/Object/SymbolicFile.h"
50#include "llvm/Pass.h"
51#include "llvm/Support/Casting.h"
52#include "llvm/Support/CommandLine.h"
53#include "llvm/Support/FileSystem.h"
54#include <algorithm>
55#include <cassert>
56#include <cstdint>
57#include <vector>
58
59using namespace llvm;
60
61#define DEBUG_TYPE"module-summary-analysis" "module-summary-analysis"
62
63// Option to force edges cold which will block importing when the
64// -import-cold-multiplier is set to 0. Useful for debugging.
65FunctionSummary::ForceSummaryHotnessType ForceSummaryEdgesCold =
66 FunctionSummary::FSHT_None;
67cl::opt<FunctionSummary::ForceSummaryHotnessType, true> FSEC(
68 "force-summary-edges-cold", cl::Hidden, cl::location(ForceSummaryEdgesCold),
69 cl::desc("Force all edges in the function summary to cold"),
70 cl::values(clEnumValN(FunctionSummary::FSHT_None, "none", "None.")llvm::cl::OptionEnumValue { "none", int(FunctionSummary::FSHT_None
), "None." },
71 clEnumValN(FunctionSummary::FSHT_AllNonCritical,llvm::cl::OptionEnumValue { "all-non-critical", int(FunctionSummary
::FSHT_AllNonCritical), "All non-critical edges." }
72 "all-non-critical", "All non-critical edges.")llvm::cl::OptionEnumValue { "all-non-critical", int(FunctionSummary
::FSHT_AllNonCritical), "All non-critical edges." },
73 clEnumValN(FunctionSummary::FSHT_All, "all", "All edges.")llvm::cl::OptionEnumValue { "all", int(FunctionSummary::FSHT_All
), "All edges." }));
74
75cl::opt<std::string> ModuleSummaryDotFile(
76 "module-summary-dot-file", cl::init(""), cl::Hidden,
77 cl::value_desc("filename"),
78 cl::desc("File to emit dot graph of new summary into."));
79
80// Walk through the operands of a given User via worklist iteration and populate
81// the set of GlobalValue references encountered. Invoked either on an
82// Instruction or a GlobalVariable (which walks its initializer).
83// Return true if any of the operands contains blockaddress. This is important
84// to know when computing summary for global var, because if global variable
85// references basic block address we can't import it separately from function
86// containing that basic block. For simplicity we currently don't import such
87// global vars at all. When importing function we aren't interested if any
88// instruction in it takes an address of any basic block, because instruction
89// can only take an address of basic block located in the same function.
90static bool findRefEdges(ModuleSummaryIndex &Index, const User *CurUser,
91 SetVector<ValueInfo> &RefEdges,
92 SmallPtrSet<const User *, 8> &Visited) {
93 bool HasBlockAddress = false;
94 SmallVector<const User *, 32> Worklist;
95 if (Visited.insert(CurUser).second)
96 Worklist.push_back(CurUser);
97
98 while (!Worklist.empty()) {
99 const User *U = Worklist.pop_back_val();
100 const auto *CB = dyn_cast<CallBase>(U);
101
102 for (const auto &OI : U->operands()) {
103 const User *Operand = dyn_cast<User>(OI);
104 if (!Operand)
105 continue;
106 if (isa<BlockAddress>(Operand)) {
107 HasBlockAddress = true;
108 continue;
109 }
110 if (auto *GV = dyn_cast<GlobalValue>(Operand)) {
111 // We have a reference to a global value. This should be added to
112 // the reference set unless it is a callee. Callees are handled
113 // specially by WriteFunction and are added to a separate list.
114 if (!(CB && CB->isCallee(&OI)))
115 RefEdges.insert(Index.getOrInsertValueInfo(GV));
116 continue;
117 }
118 if (Visited.insert(Operand).second)
119 Worklist.push_back(Operand);
120 }
121 }
122 return HasBlockAddress;
123}
124
125static CalleeInfo::HotnessType getHotness(uint64_t ProfileCount,
126 ProfileSummaryInfo *PSI) {
127 if (!PSI)
128 return CalleeInfo::HotnessType::Unknown;
129 if (PSI->isHotCount(ProfileCount))
130 return CalleeInfo::HotnessType::Hot;
131 if (PSI->isColdCount(ProfileCount))
132 return CalleeInfo::HotnessType::Cold;
133 return CalleeInfo::HotnessType::None;
134}
135
136static bool isNonRenamableLocal(const GlobalValue &GV) {
137 return GV.hasSection() && GV.hasLocalLinkage();
138}
139
140/// Determine whether this call has all constant integer arguments (excluding
141/// "this") and summarize it to VCalls or ConstVCalls as appropriate.
142static void addVCallToSet(DevirtCallSite Call, GlobalValue::GUID Guid,
143 SetVector<FunctionSummary::VFuncId> &VCalls,
144 SetVector<FunctionSummary::ConstVCall> &ConstVCalls) {
145 std::vector<uint64_t> Args;
146 // Start from the second argument to skip the "this" pointer.
147 for (auto &Arg : drop_begin(Call.CB.args())) {
148 auto *CI = dyn_cast<ConstantInt>(Arg);
149 if (!CI || CI->getBitWidth() > 64) {
150 VCalls.insert({Guid, Call.Offset});
151 return;
152 }
153 Args.push_back(CI->getZExtValue());
154 }
155 ConstVCalls.insert({{Guid, Call.Offset}, std::move(Args)});
156}
157
158/// If this intrinsic call requires that we add information to the function
159/// summary, do so via the non-constant reference arguments.
160static void addIntrinsicToSummary(
161 const CallInst *CI, SetVector<GlobalValue::GUID> &TypeTests,
162 SetVector<FunctionSummary::VFuncId> &TypeTestAssumeVCalls,
163 SetVector<FunctionSummary::VFuncId> &TypeCheckedLoadVCalls,
164 SetVector<FunctionSummary::ConstVCall> &TypeTestAssumeConstVCalls,
165 SetVector<FunctionSummary::ConstVCall> &TypeCheckedLoadConstVCalls,
166 DominatorTree &DT) {
167 switch (CI->getCalledFunction()->getIntrinsicID()) {
168 case Intrinsic::type_test: {
169 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(1));
170 auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
171 if (!TypeId)
172 break;
173 GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
174
175 // Produce a summary from type.test intrinsics. We only summarize type.test
176 // intrinsics that are used other than by an llvm.assume intrinsic.
177 // Intrinsics that are assumed are relevant only to the devirtualization
178 // pass, not the type test lowering pass.
179 bool HasNonAssumeUses = llvm::any_of(CI->uses(), [](const Use &CIU) {
180 return !isa<AssumeInst>(CIU.getUser());
181 });
182 if (HasNonAssumeUses)
183 TypeTests.insert(Guid);
184
185 SmallVector<DevirtCallSite, 4> DevirtCalls;
186 SmallVector<CallInst *, 4> Assumes;
187 findDevirtualizableCallsForTypeTest(DevirtCalls, Assumes, CI, DT);
188 for (auto &Call : DevirtCalls)
189 addVCallToSet(Call, Guid, TypeTestAssumeVCalls,
190 TypeTestAssumeConstVCalls);
191
192 break;
193 }
194
195 case Intrinsic::type_checked_load: {
196 auto *TypeMDVal = cast<MetadataAsValue>(CI->getArgOperand(2));
197 auto *TypeId = dyn_cast<MDString>(TypeMDVal->getMetadata());
198 if (!TypeId)
199 break;
200 GlobalValue::GUID Guid = GlobalValue::getGUID(TypeId->getString());
201
202 SmallVector<DevirtCallSite, 4> DevirtCalls;
203 SmallVector<Instruction *, 4> LoadedPtrs;
204 SmallVector<Instruction *, 4> Preds;
205 bool HasNonCallUses = false;
206 findDevirtualizableCallsForTypeCheckedLoad(DevirtCalls, LoadedPtrs, Preds,
207 HasNonCallUses, CI, DT);
208 // Any non-call uses of the result of llvm.type.checked.load will
209 // prevent us from optimizing away the llvm.type.test.
210 if (HasNonCallUses)
211 TypeTests.insert(Guid);
212 for (auto &Call : DevirtCalls)
213 addVCallToSet(Call, Guid, TypeCheckedLoadVCalls,
214 TypeCheckedLoadConstVCalls);
215
216 break;
217 }
218 default:
219 break;
220 }
221}
222
223static bool isNonVolatileLoad(const Instruction *I) {
224 if (const auto *LI = dyn_cast<LoadInst>(I))
225 return !LI->isVolatile();
226
227 return false;
228}
229
230static bool isNonVolatileStore(const Instruction *I) {
231 if (const auto *SI = dyn_cast<StoreInst>(I))
232 return !SI->isVolatile();
233
234 return false;
235}
236
237static void computeFunctionSummary(
238 ModuleSummaryIndex &Index, const Module &M, const Function &F,
239 BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI, DominatorTree &DT,
240 bool HasLocalsInUsedOrAsm, DenseSet<GlobalValue::GUID> &CantBePromoted,
241 bool IsThinLTO,
242 std::function<const StackSafetyInfo *(const Function &F)> GetSSICallback) {
243 // Summary not currently supported for anonymous functions, they should
244 // have been named.
245 assert(F.hasName())((void)0);
246
247 unsigned NumInsts = 0;
248 // Map from callee ValueId to profile count. Used to accumulate profile
249 // counts for all static calls to a given callee.
250 MapVector<ValueInfo, CalleeInfo> CallGraphEdges;
251 SetVector<ValueInfo> RefEdges, LoadRefEdges, StoreRefEdges;
252 SetVector<GlobalValue::GUID> TypeTests;
253 SetVector<FunctionSummary::VFuncId> TypeTestAssumeVCalls,
254 TypeCheckedLoadVCalls;
255 SetVector<FunctionSummary::ConstVCall> TypeTestAssumeConstVCalls,
256 TypeCheckedLoadConstVCalls;
257 ICallPromotionAnalysis ICallAnalysis;
258 SmallPtrSet<const User *, 8> Visited;
259
260 // Add personality function, prefix data and prologue data to function's ref
261 // list.
262 findRefEdges(Index, &F, RefEdges, Visited);
263 std::vector<const Instruction *> NonVolatileLoads;
264 std::vector<const Instruction *> NonVolatileStores;
265
266 bool HasInlineAsmMaybeReferencingInternal = false;
267 for (const BasicBlock &BB : F)
268 for (const Instruction &I : BB) {
269 if (isa<DbgInfoIntrinsic>(I))
11
←
Assuming 'I' is not a 'DbgInfoIntrinsic'
→
12
←
Taking false branch
→
270 continue;
271 ++NumInsts;
272 // Regular LTO module doesn't participate in ThinLTO import,
273 // so no reference from it can be read/writeonly, since this
274 // would require importing variable as local copy
275 if (IsThinLTO
12.1
'IsThinLTO' is true
12.1
'IsThinLTO' is true
12.1
'IsThinLTO' is true
) {
13
←
Taking true branch
→
276 if (isNonVolatileLoad(&I)) {
14
←
Taking false branch
→
277 // Postpone processing of non-volatile load instructions
278 // See comments below
279 Visited.insert(&I);
280 NonVolatileLoads.push_back(&I);
281 continue;
282 } else if (isNonVolatileStore(&I)) {
15
←
Taking false branch
→
283 Visited.insert(&I);
284 NonVolatileStores.push_back(&I);
285 // All references from second operand of store (destination address)
286 // can be considered write-only if they're not referenced by any
287 // non-store instruction. References from first operand of store
288 // (stored value) can't be treated either as read- or as write-only
289 // so we add them to RefEdges as we do with all other instructions
290 // except non-volatile load.
291 Value *Stored = I.getOperand(0);
292 if (auto *GV = dyn_cast<GlobalValue>(Stored))
293 // findRefEdges will try to examine GV operands, so instead
294 // of calling it we should add GV to RefEdges directly.
295 RefEdges.insert(Index.getOrInsertValueInfo(GV));
296 else if (auto *U = dyn_cast<User>(Stored))
297 findRefEdges(Index, U, RefEdges, Visited);
298 continue;
299 }
300 }
301 findRefEdges(Index, &I, RefEdges, Visited);
302 const auto *CB = dyn_cast<CallBase>(&I);
16
←
Assuming the object is a 'CallBase'
→
303 if (!CB
16.1
'CB' is non-null
16.1
'CB' is non-null
16.1
'CB' is non-null
)
17
←
Taking false branch
→
304 continue;
305
306 const auto *CI = dyn_cast<CallInst>(&I);
18
←
Assuming the object is not a 'CallInst'
→
307 // Since we don't know exactly which local values are referenced in inline
308 // assembly, conservatively mark the function as possibly referencing
309 // a local value from inline assembly to ensure we don't export a
310 // reference (which would require renaming and promotion of the
311 // referenced value).
312 if (HasLocalsInUsedOrAsm
18.1
'HasLocalsInUsedOrAsm' is true
18.1
'HasLocalsInUsedOrAsm' is true
18.1
'HasLocalsInUsedOrAsm' is true
 && CI
18.2
'CI' is null
18.2
'CI' is null
18.2
'CI' is null
 && CI->isInlineAsm())
313 HasInlineAsmMaybeReferencingInternal = true;
314
315 auto *CalledValue = CB->getCalledOperand();
316 auto *CalledFunction = CB->getCalledFunction();
317 if (CalledValue
18.3
'CalledValue' is null
18.3
'CalledValue' is null
18.3
'CalledValue' is null
 && !CalledFunction) {
318 CalledValue = CalledValue->stripPointerCasts();
319 // Stripping pointer casts can reveal a called function.
320 CalledFunction = dyn_cast<Function>(CalledValue);
321 }
322 // Check if this is an alias to a function. If so, get the
323 // called aliasee for the checks below.
324 if (auto *GA = dyn_cast<GlobalAlias>(CalledValue)) {
19
←
Assuming 'GA' is non-null
→
20
←
Taking true branch
→
325 assert(!CalledFunction && "Expected null called function in callsite for alias")((void)0);
326 CalledFunction = dyn_cast<Function>(GA->getBaseObject());
21
←
Assuming the object is a 'Function'
→
327 }
328 // Check if this is a direct call to a known function or a known
329 // intrinsic, or an indirect call with profile data.
330 if (CalledFunction
21.1
'CalledFunction' is non-null
21.1
'CalledFunction' is non-null
21.1
'CalledFunction' is non-null
) {
22
←
Taking true branch
→
331 if (CI
22.1
'CI' is null
22.1
'CI' is null
22.1
'CI' is null
 && CalledFunction->isIntrinsic()) {
332 addIntrinsicToSummary(
333 CI, TypeTests, TypeTestAssumeVCalls, TypeCheckedLoadVCalls,
334 TypeTestAssumeConstVCalls, TypeCheckedLoadConstVCalls, DT);
335 continue;
336 }
337 // We should have named any anonymous globals
338 assert(CalledFunction->hasName())((void)0);
339 auto ScaledCount = PSI->getProfileCount(*CB, BFI);
340 auto Hotness = ScaledCount ? getHotness(ScaledCount.getValue(), PSI)
23
←
Assuming the condition is false
→
24
←
'?' condition is false
→
341 : CalleeInfo::HotnessType::Unknown;
342 if (ForceSummaryEdgesCold != FunctionSummary::FSHT_None)
25
←
Assuming 'ForceSummaryEdgesCold' is equal to FSHT_None
→
26
←
Taking false branch
→
343 Hotness = CalleeInfo::HotnessType::Cold;
344
345 // Use the original CalledValue, in case it was an alias. We want
346 // to record the call edge to the alias in that case. Eventually
347 // an alias summary will be created to associate the alias and
348 // aliasee.
349 auto &ValueInfo = CallGraphEdges[Index.getOrInsertValueInfo(
350 cast<GlobalValue>(CalledValue))];
351 ValueInfo.updateHotness(Hotness);
352 // Add the relative block frequency to CalleeInfo if there is no profile
353 // information.
354 if (BFI != nullptr && Hotness
26.1
'Hotness' is equal to Unknown
26.1
'Hotness' is equal to Unknown
26.1
'Hotness' is equal to Unknown
 == CalleeInfo::HotnessType::Unknown) {
27
←
Taking true branch
→
355 uint64_t BBFreq = BFI->getBlockFreq(&BB).getFrequency();
356 uint64_t EntryFreq = BFI->getEntryFreq();
357 ValueInfo.updateRelBlockFreq(BBFreq, EntryFreq);
28
←
Calling 'CalleeInfo::updateRelBlockFreq'
→
358 }
359 } else {
360 // Skip inline assembly calls.
361 if (CI && CI->isInlineAsm())
362 continue;
363 // Skip direct calls.
364 if (!CalledValue || isa<Constant>(CalledValue))
365 continue;
366
367 // Check if the instruction has a callees metadata. If so, add callees
368 // to CallGraphEdges to reflect the references from the metadata, and
369 // to enable importing for subsequent indirect call promotion and
370 // inlining.
371 if (auto *MD = I.getMetadata(LLVMContext::MD_callees)) {
372 for (auto &Op : MD->operands()) {
373 Function *Callee = mdconst::extract_or_null<Function>(Op);
374 if (Callee)
375 CallGraphEdges[Index.getOrInsertValueInfo(Callee)];
376 }
377 }
378
379 uint32_t NumVals, NumCandidates;
380 uint64_t TotalCount;
381 auto CandidateProfileData =
382 ICallAnalysis.getPromotionCandidatesForInstruction(
383 &I, NumVals, TotalCount, NumCandidates);
384 for (auto &Candidate : CandidateProfileData)
385 CallGraphEdges[Index.getOrInsertValueInfo(Candidate.Value)]
386 .updateHotness(getHotness(Candidate.Count, PSI));
387 }
388 }
389 Index.addBlockCount(F.size());
390
391 std::vector<ValueInfo> Refs;
392 if (IsThinLTO) {
393 auto AddRefEdges = [&](const std::vector<const Instruction *> &Instrs,
394 SetVector<ValueInfo> &Edges,
395 SmallPtrSet<const User *, 8> &Cache) {
396 for (const auto *I : Instrs) {
397 Cache.erase(I);
398 findRefEdges(Index, I, Edges, Cache);
399 }
400 };
401
402 // By now we processed all instructions in a function, except
403 // non-volatile loads and non-volatile value stores. Let's find
404 // ref edges for both of instruction sets
405 AddRefEdges(NonVolatileLoads, LoadRefEdges, Visited);
406 // We can add some values to the Visited set when processing load
407 // instructions which are also used by stores in NonVolatileStores.
408 // For example this can happen if we have following code:
409 //
410 // store %Derived* @foo, %Derived** bitcast (%Base** @bar to %Derived**)
411 // %42 = load %Derived*, %Derived** bitcast (%Base** @bar to %Derived**)
412 //
413 // After processing loads we'll add bitcast to the Visited set, and if
414 // we use the same set while processing stores, we'll never see store
415 // to @bar and @bar will be mistakenly treated as readonly.
416 SmallPtrSet<const llvm::User *, 8> StoreCache;
417 AddRefEdges(NonVolatileStores, StoreRefEdges, StoreCache);
418
419 // If both load and store instruction reference the same variable
420 // we won't be able to optimize it. Add all such reference edges
421 // to RefEdges set.
422 for (auto &VI : StoreRefEdges)
423 if (LoadRefEdges.remove(VI))
424 RefEdges.insert(VI);
425
426 unsigned RefCnt = RefEdges.size();
427 // All new reference edges inserted in two loops below are either
428 // read or write only. They will be grouped in the end of RefEdges
429 // vector, so we can use a single integer value to identify them.
430 for (auto &VI : LoadRefEdges)
431 RefEdges.insert(VI);
432
433 unsigned FirstWORef = RefEdges.size();
434 for (auto &VI : StoreRefEdges)
435 RefEdges.insert(VI);
436
437 Refs = RefEdges.takeVector();
438 for (; RefCnt < FirstWORef; ++RefCnt)
439 Refs[RefCnt].setReadOnly();
440
441 for (; RefCnt < Refs.size(); ++RefCnt)
442 Refs[RefCnt].setWriteOnly();
443 } else {
444 Refs = RefEdges.takeVector();
445 }
446 // Explicit add hot edges to enforce importing for designated GUIDs for
447 // sample PGO, to enable the same inlines as the profiled optimized binary.
448 for (auto &I : F.getImportGUIDs())
449 CallGraphEdges[Index.getOrInsertValueInfo(I)].updateHotness(
450 ForceSummaryEdgesCold == FunctionSummary::FSHT_All
451 ? CalleeInfo::HotnessType::Cold
452 : CalleeInfo::HotnessType::Critical);
453
454 bool NonRenamableLocal = isNonRenamableLocal(F);
455 bool NotEligibleForImport =
456 NonRenamableLocal || HasInlineAsmMaybeReferencingInternal;
457 GlobalValueSummary::GVFlags Flags(
458 F.getLinkage(), F.getVisibility(), NotEligibleForImport,
459 /* Live = */ false, F.isDSOLocal(),
460 F.hasLinkOnceODRLinkage() && F.hasGlobalUnnamedAddr());
461 FunctionSummary::FFlags FunFlags{
462 F.hasFnAttribute(Attribute::ReadNone),
463 F.hasFnAttribute(Attribute::ReadOnly),
464 F.hasFnAttribute(Attribute::NoRecurse), F.returnDoesNotAlias(),
465 // FIXME: refactor this to use the same code that inliner is using.
466 // Don't try to import functions with noinline attribute.
467 F.getAttributes().hasFnAttribute(Attribute::NoInline),
468 F.hasFnAttribute(Attribute::AlwaysInline)};
469 std::vector<FunctionSummary::ParamAccess> ParamAccesses;
470 if (auto *SSI = GetSSICallback(F))
471 ParamAccesses = SSI->getParamAccesses(Index);
472 auto FuncSummary = std::make_unique<FunctionSummary>(
473 Flags, NumInsts, FunFlags, /*EntryCount=*/0, std::move(Refs),
474 CallGraphEdges.takeVector(), TypeTests.takeVector(),
475 TypeTestAssumeVCalls.takeVector(), TypeCheckedLoadVCalls.takeVector(),
476 TypeTestAssumeConstVCalls.takeVector(),
477 TypeCheckedLoadConstVCalls.takeVector(), std::move(ParamAccesses));
478 if (NonRenamableLocal)
479 CantBePromoted.insert(F.getGUID());
480 Index.addGlobalValueSummary(F, std::move(FuncSummary));
481}
482
483/// Find function pointers referenced within the given vtable initializer
484/// (or subset of an initializer) \p I. The starting offset of \p I within
485/// the vtable initializer is \p StartingOffset. Any discovered function
486/// pointers are added to \p VTableFuncs along with their cumulative offset
487/// within the initializer.
488static void findFuncPointers(const Constant *I, uint64_t StartingOffset,
489 const Module &M, ModuleSummaryIndex &Index,
490 VTableFuncList &VTableFuncs) {
491 // First check if this is a function pointer.
492 if (I->getType()->isPointerTy()) {
493 auto Fn = dyn_cast<Function>(I->stripPointerCasts());
494 // We can disregard __cxa_pure_virtual as a possible call target, as
495 // calls to pure virtuals are UB.
496 if (Fn && Fn->getName() != "__cxa_pure_virtual")
497 VTableFuncs.push_back({Index.getOrInsertValueInfo(Fn), StartingOffset});
498 return;
499 }
500
501 // Walk through the elements in the constant struct or array and recursively
502 // look for virtual function pointers.
503 const DataLayout &DL = M.getDataLayout();
504 if (auto *C = dyn_cast<ConstantStruct>(I)) {
505 StructType *STy = dyn_cast<StructType>(C->getType());
506 assert(STy)((void)0);
507 const StructLayout *SL = DL.getStructLayout(C->getType());
508
509 for (auto EI : llvm::enumerate(STy->elements())) {
510 auto Offset = SL->getElementOffset(EI.index());
511 unsigned Op = SL->getElementContainingOffset(Offset);
512 findFuncPointers(cast<Constant>(I->getOperand(Op)),
513 StartingOffset + Offset, M, Index, VTableFuncs);
514 }
515 } else if (auto *C = dyn_cast<ConstantArray>(I)) {
516 ArrayType *ATy = C->getType();
517 Type *EltTy = ATy->getElementType();
518 uint64_t EltSize = DL.getTypeAllocSize(EltTy);
519 for (unsigned i = 0, e = ATy->getNumElements(); i != e; ++i) {
520 findFuncPointers(cast<Constant>(I->getOperand(i)),
521 StartingOffset + i * EltSize, M, Index, VTableFuncs);
522 }
523 }
524}
525
526// Identify the function pointers referenced by vtable definition \p V.
527static void computeVTableFuncs(ModuleSummaryIndex &Index,
528 const GlobalVariable &V, const Module &M,
529 VTableFuncList &VTableFuncs) {
530 if (!V.isConstant())
531 return;
532
533 findFuncPointers(V.getInitializer(), /*StartingOffset=*/0, M, Index,
534 VTableFuncs);
535
536#ifndef NDEBUG1
537 // Validate that the VTableFuncs list is ordered by offset.
538 uint64_t PrevOffset = 0;
539 for (auto &P : VTableFuncs) {
540 // The findVFuncPointers traversal should have encountered the
541 // functions in offset order. We need to use ">=" since PrevOffset
542 // starts at 0.
543 assert(P.VTableOffset >= PrevOffset)((void)0);
544 PrevOffset = P.VTableOffset;
545 }
546#endif
547}
548
549/// Record vtable definition \p V for each type metadata it references.
550static void
551recordTypeIdCompatibleVtableReferences(ModuleSummaryIndex &Index,
552 const GlobalVariable &V,
553 SmallVectorImpl<MDNode *> &Types) {
554 for (MDNode *Type : Types) {
555 auto TypeID = Type->getOperand(1).get();
556
557 uint64_t Offset =
558 cast<ConstantInt>(
559 cast<ConstantAsMetadata>(Type->getOperand(0))->getValue())
560 ->getZExtValue();
561
562 if (auto *TypeId = dyn_cast<MDString>(TypeID))
563 Index.getOrInsertTypeIdCompatibleVtableSummary(TypeId->getString())
564 .push_back({Offset, Index.getOrInsertValueInfo(&V)});
565 }
566}
567
568static void computeVariableSummary(ModuleSummaryIndex &Index,
569 const GlobalVariable &V,
570 DenseSet<GlobalValue::GUID> &CantBePromoted,
571 const Module &M,
572 SmallVectorImpl<MDNode *> &Types) {
573 SetVector<ValueInfo> RefEdges;
574 SmallPtrSet<const User *, 8> Visited;
575 bool HasBlockAddress = findRefEdges(Index, &V, RefEdges, Visited);
576 bool NonRenamableLocal = isNonRenamableLocal(V);
577 GlobalValueSummary::GVFlags Flags(
578 V.getLinkage(), V.getVisibility(), NonRenamableLocal,
579 /* Live = */ false, V.isDSOLocal(),
580 V.hasLinkOnceODRLinkage() && V.hasGlobalUnnamedAddr());
581
582 VTableFuncList VTableFuncs;
583 // If splitting is not enabled, then we compute the summary information
584 // necessary for index-based whole program devirtualization.
585 if (!Index.enableSplitLTOUnit()) {
586 Types.clear();
587 V.getMetadata(LLVMContext::MD_type, Types);
588 if (!Types.empty()) {
589 // Identify the function pointers referenced by this vtable definition.
590 computeVTableFuncs(Index, V, M, VTableFuncs);
591
592 // Record this vtable definition for each type metadata it references.
593 recordTypeIdCompatibleVtableReferences(Index, V, Types);
594 }
595 }
596
597 // Don't mark variables we won't be able to internalize as read/write-only.
598 bool CanBeInternalized =
599 !V.hasComdat() && !V.hasAppendingLinkage() && !V.isInterposable() &&
600 !V.hasAvailableExternallyLinkage() && !V.hasDLLExportStorageClass();
601 bool Constant = V.isConstant();
602 GlobalVarSummary::GVarFlags VarFlags(CanBeInternalized,
603 Constant ? false : CanBeInternalized,
604 Constant, V.getVCallVisibility());
605 auto GVarSummary = std::make_unique<GlobalVarSummary>(Flags, VarFlags,
606 RefEdges.takeVector());
607 if (NonRenamableLocal)
608 CantBePromoted.insert(V.getGUID());
609 if (HasBlockAddress)
610 GVarSummary->setNotEligibleToImport();
611 if (!VTableFuncs.empty())
612 GVarSummary->setVTableFuncs(VTableFuncs);
613 Index.addGlobalValueSummary(V, std::move(GVarSummary));
614}
615
616static void
617computeAliasSummary(ModuleSummaryIndex &Index, const GlobalAlias &A,
618 DenseSet<GlobalValue::GUID> &CantBePromoted) {
619 bool NonRenamableLocal = isNonRenamableLocal(A);
620 GlobalValueSummary::GVFlags Flags(
621 A.getLinkage(), A.getVisibility(), NonRenamableLocal,
622 /* Live = */ false, A.isDSOLocal(),
623 A.hasLinkOnceODRLinkage() && A.hasGlobalUnnamedAddr());
624 auto AS = std::make_unique<AliasSummary>(Flags);
625 auto *Aliasee = A.getBaseObject();
626 auto AliaseeVI = Index.getValueInfo(Aliasee->getGUID());
627 assert(AliaseeVI && "Alias expects aliasee summary to be available")((void)0);
628 assert(AliaseeVI.getSummaryList().size() == 1 &&((void)0)
629 "Expected a single entry per aliasee in per-module index")((void)0);
630 AS->setAliasee(AliaseeVI, AliaseeVI.getSummaryList()[0].get());
631 if (NonRenamableLocal)
632 CantBePromoted.insert(A.getGUID());
633 Index.addGlobalValueSummary(A, std::move(AS));
634}
635
636// Set LiveRoot flag on entries matching the given value name.
637static void setLiveRoot(ModuleSummaryIndex &Index, StringRef Name) {
638 if (ValueInfo VI = Index.getValueInfo(GlobalValue::getGUID(Name)))
639 for (auto &Summary : VI.getSummaryList())
640 Summary->setLive(true);
641}
642
643ModuleSummaryIndex llvm::buildModuleSummaryIndex(
644 const Module &M,
645 std::function<BlockFrequencyInfo *(const Function &F)> GetBFICallback,
646 ProfileSummaryInfo *PSI,
647 std::function<const StackSafetyInfo *(const Function &F)> GetSSICallback) {
648 assert(PSI)((void)0);
649 bool EnableSplitLTOUnit = false;
650 if (auto *MD
1.1
'MD' is null
1.1
'MD' is null
1.1
'MD' is null
 = mdconst::extract_or_null<ConstantInt>(
2
←
Taking false branch
→
651 M.getModuleFlag("EnableSplitLTOUnit")))
652 EnableSplitLTOUnit = MD->getZExtValue();
653 ModuleSummaryIndex Index(/*HaveGVs=*/true, EnableSplitLTOUnit);
654
655 // Identify the local values in the llvm.used and llvm.compiler.used sets,
656 // which should not be exported as they would then require renaming and
657 // promotion, but we may have opaque uses e.g. in inline asm. We collect them
658 // here because we use this information to mark functions containing inline
659 // assembly calls as not importable.
660 SmallPtrSet<GlobalValue *, 4> LocalsUsed;
661 SmallVector<GlobalValue *, 4> Used;
662 // First collect those in the llvm.used set.
663 collectUsedGlobalVariables(M, Used, /*CompilerUsed=*/false);
664 // Next collect those in the llvm.compiler.used set.
665 collectUsedGlobalVariables(M, Used, /*CompilerUsed=*/true);
666 DenseSet<GlobalValue::GUID> CantBePromoted;
667 for (auto *V : Used) {
3
←
Assuming '__begin1' is equal to '__end1'
→
668 if (V->hasLocalLinkage()) {
669 LocalsUsed.insert(V);
670 CantBePromoted.insert(V->getGUID());
671 }
672 }
673
674 bool HasLocalInlineAsmSymbol = false;
675 if (!M.getModuleInlineAsm().empty()) {
4
←
Assuming the condition is false
→
5
←
Taking false branch
→
676 // Collect the local values defined by module level asm, and set up
677 // summaries for these symbols so that they can be marked as NoRename,
678 // to prevent export of any use of them in regular IR that would require
679 // renaming within the module level asm. Note we don't need to create a
680 // summary for weak or global defs, as they don't need to be flagged as
681 // NoRename, and defs in module level asm can't be imported anyway.
682 // Also, any values used but not defined within module level asm should
683 // be listed on the llvm.used or llvm.compiler.used global and marked as
684 // referenced from there.
685 ModuleSymbolTable::CollectAsmSymbols(
686 M, [&](StringRef Name, object::BasicSymbolRef::Flags Flags) {
687 // Symbols not marked as Weak or Global are local definitions.
688 if (Flags & (object::BasicSymbolRef::SF_Weak |
689 object::BasicSymbolRef::SF_Global))
690 return;
691 HasLocalInlineAsmSymbol = true;
692 GlobalValue *GV = M.getNamedValue(Name);
693 if (!GV)
694 return;
695 assert(GV->isDeclaration() && "Def in module asm already has definition")((void)0);
696 GlobalValueSummary::GVFlags GVFlags(
697 GlobalValue::InternalLinkage, GlobalValue::DefaultVisibility,
698 /* NotEligibleToImport = */ true,
699 /* Live = */ true,
700 /* Local */ GV->isDSOLocal(),
701 GV->hasLinkOnceODRLinkage() && GV->hasGlobalUnnamedAddr());
702 CantBePromoted.insert(GV->getGUID());
703 // Create the appropriate summary type.
704 if (Function *F = dyn_cast<Function>(GV)) {
705 std::unique_ptr<FunctionSummary> Summary =
706 std::make_unique<FunctionSummary>(
707 GVFlags, /*InstCount=*/0,
708 FunctionSummary::FFlags{
709 F->hasFnAttribute(Attribute::ReadNone),
710 F->hasFnAttribute(Attribute::ReadOnly),
711 F->hasFnAttribute(Attribute::NoRecurse),
712 F->returnDoesNotAlias(),
713 /* NoInline = */ false,
714 F->hasFnAttribute(Attribute::AlwaysInline)},
715 /*EntryCount=*/0, ArrayRef<ValueInfo>{},
716 ArrayRef<FunctionSummary::EdgeTy>{},
717 ArrayRef<GlobalValue::GUID>{},
718 ArrayRef<FunctionSummary::VFuncId>{},
719 ArrayRef<FunctionSummary::VFuncId>{},
720 ArrayRef<FunctionSummary::ConstVCall>{},
721 ArrayRef<FunctionSummary::ConstVCall>{},
722 ArrayRef<FunctionSummary::ParamAccess>{});
723 Index.addGlobalValueSummary(*GV, std::move(Summary));
724 } else {
725 std::unique_ptr<GlobalVarSummary> Summary =
726 std::make_unique<GlobalVarSummary>(
727 GVFlags,
728 GlobalVarSummary::GVarFlags(
729 false, false, cast<GlobalVariable>(GV)->isConstant(),
730 GlobalObject::VCallVisibilityPublic),
731 ArrayRef<ValueInfo>{});
732 Index.addGlobalValueSummary(*GV, std::move(Summary));
733 }
734 });
735 }
736
737 bool IsThinLTO = true;
738 if (auto *MD
5.1
'MD' is null
5.1
'MD' is null
5.1
'MD' is null
 =
6
←
Taking false branch
→
739 mdconst::extract_or_null<ConstantInt>(M.getModuleFlag("ThinLTO")))
740 IsThinLTO = MD->getZExtValue();
741
742 // Compute summaries for all functions defined in module, and save in the
743 // index.
744 for (auto &F : M) {
745 if (F.isDeclaration())
7
←
Assuming the condition is false
→
8
←
Taking false branch
→
746 continue;
747
748 DominatorTree DT(const_cast<Function &>(F));
749 BlockFrequencyInfo *BFI = nullptr;
750 std::unique_ptr<BlockFrequencyInfo> BFIPtr;
751 if (GetBFICallback)
9
←
Taking true branch
→
752 BFI = GetBFICallback(F);
753 else if (F.hasProfileData()) {
754 LoopInfo LI{DT};
755 BranchProbabilityInfo BPI{F, LI};
756 BFIPtr = std::make_unique<BlockFrequencyInfo>(F, BPI, LI);
757 BFI = BFIPtr.get();
758 }
759
760 computeFunctionSummary(Index, M, F, BFI, PSI, DT,
10
←
Calling 'computeFunctionSummary'
→
761 !LocalsUsed.empty() || HasLocalInlineAsmSymbol,
762 CantBePromoted, IsThinLTO, GetSSICallback);
763 }
764
765 // Compute summaries for all variables defined in module, and save in the
766 // index.
767 SmallVector<MDNode *, 2> Types;
768 for (const GlobalVariable &G : M.globals()) {
769 if (G.isDeclaration())
770 continue;
771 computeVariableSummary(Index, G, CantBePromoted, M, Types);
772 }
773
774 // Compute summaries for all aliases defined in module, and save in the
775 // index.
776 for (const GlobalAlias &A : M.aliases())
777 computeAliasSummary(Index, A, CantBePromoted);
778
779 for (auto *V : LocalsUsed) {
780 auto *Summary = Index.getGlobalValueSummary(*V);
781 assert(Summary && "Missing summary for global value")((void)0);
782 Summary->setNotEligibleToImport();
783 }
784
785 // The linker doesn't know about these LLVM produced values, so we need
786 // to flag them as live in the index to ensure index-based dead value
787 // analysis treats them as live roots of the analysis.
788 setLiveRoot(Index, "llvm.used");
789 setLiveRoot(Index, "llvm.compiler.used");
790 setLiveRoot(Index, "llvm.global_ctors");
791 setLiveRoot(Index, "llvm.global_dtors");
792 setLiveRoot(Index, "llvm.global.annotations");
793
794 for (auto &GlobalList : Index) {
795 // Ignore entries for references that are undefined in the current module.
796 if (GlobalList.second.SummaryList.empty())
797 continue;
798
799 assert(GlobalList.second.SummaryList.size() == 1 &&((void)0)
800 "Expected module's index to have one summary per GUID")((void)0);
801 auto &Summary = GlobalList.second.SummaryList[0];
802 if (!IsThinLTO) {
803 Summary->setNotEligibleToImport();
804 continue;
805 }
806
807 bool AllRefsCanBeExternallyReferenced =
808 llvm::all_of(Summary->refs(), [&](const ValueInfo &VI) {
809 return !CantBePromoted.count(VI.getGUID());
810 });
811 if (!AllRefsCanBeExternallyReferenced) {
812 Summary->setNotEligibleToImport();
813 continue;
814 }
815
816 if (auto *FuncSummary = dyn_cast<FunctionSummary>(Summary.get())) {
817 bool AllCallsCanBeExternallyReferenced = llvm::all_of(
818 FuncSummary->calls(), [&](const FunctionSummary::EdgeTy &Edge) {
819 return !CantBePromoted.count(Edge.first.getGUID());
820 });
821 if (!AllCallsCanBeExternallyReferenced)
822 Summary->setNotEligibleToImport();
823 }
824 }
825
826 if (!ModuleSummaryDotFile.empty()) {
827 std::error_code EC;
828 raw_fd_ostream OSDot(ModuleSummaryDotFile, EC, sys::fs::OpenFlags::OF_None);
829 if (EC)
830 report_fatal_error(Twine("Failed to open dot file ") +
831 ModuleSummaryDotFile + ": " + EC.message() + "\n");
832 Index.exportToDot(OSDot, {});
833 }
834
835 return Index;
836}
837
838AnalysisKey ModuleSummaryIndexAnalysis::Key;
839
840ModuleSummaryIndex
841ModuleSummaryIndexAnalysis::run(Module &M, ModuleAnalysisManager &AM) {
842 ProfileSummaryInfo &PSI = AM.getResult<ProfileSummaryAnalysis>(M);
843 auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
844 bool NeedSSI = needsParamAccessSummary(M);
845 return buildModuleSummaryIndex(
846 M,
847 [&FAM](const Function &F) {
848 return &FAM.getResult<BlockFrequencyAnalysis>(
849 *const_cast<Function *>(&F));
850 },
851 &PSI,
852 [&FAM, NeedSSI](const Function &F) -> const StackSafetyInfo * {
853 return NeedSSI ? &FAM.getResult<StackSafetyAnalysis>(
854 const_cast<Function &>(F))
855 : nullptr;
856 });
857}
858
859char ModuleSummaryIndexWrapperPass::ID = 0;
860
861INITIALIZE_PASS_BEGIN(ModuleSummaryIndexWrapperPass, "module-summary-analysis",static void *initializeModuleSummaryIndexWrapperPassPassOnce(
PassRegistry &Registry) {
862 "Module Summary Analysis", false, true)static void *initializeModuleSummaryIndexWrapperPassPassOnce(
PassRegistry &Registry) {
863INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)initializeBlockFrequencyInfoWrapperPassPass(Registry);
864INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)initializeProfileSummaryInfoWrapperPassPass(Registry);
865INITIALIZE_PASS_DEPENDENCY(StackSafetyInfoWrapperPass)initializeStackSafetyInfoWrapperPassPass(Registry);
866INITIALIZE_PASS_END(ModuleSummaryIndexWrapperPass, "module-summary-analysis",PassInfo *PI = new PassInfo( "Module Summary Analysis", "module-summary-analysis"
, &ModuleSummaryIndexWrapperPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<ModuleSummaryIndexWrapperPass>), false
, true); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeModuleSummaryIndexWrapperPassPassFlag
; void llvm::initializeModuleSummaryIndexWrapperPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeModuleSummaryIndexWrapperPassPassFlag
, initializeModuleSummaryIndexWrapperPassPassOnce, std::ref(Registry
)); }
867 "Module Summary Analysis", false, true)PassInfo *PI = new PassInfo( "Module Summary Analysis", "module-summary-analysis"
, &ModuleSummaryIndexWrapperPass::ID, PassInfo::NormalCtor_t
(callDefaultCtor<ModuleSummaryIndexWrapperPass>), false
, true); Registry.registerPass(*PI, true); return PI; } static
llvm::once_flag InitializeModuleSummaryIndexWrapperPassPassFlag
; void llvm::initializeModuleSummaryIndexWrapperPassPass(PassRegistry
&Registry) { llvm::call_once(InitializeModuleSummaryIndexWrapperPassPassFlag
, initializeModuleSummaryIndexWrapperPassPassOnce, std::ref(Registry
)); }
868
869ModulePass *llvm::createModuleSummaryIndexWrapperPass() {
870 return new ModuleSummaryIndexWrapperPass();
871}
872
873ModuleSummaryIndexWrapperPass::ModuleSummaryIndexWrapperPass()
874 : ModulePass(ID) {
875 initializeModuleSummaryIndexWrapperPassPass(*PassRegistry::getPassRegistry());
876}
877
878bool ModuleSummaryIndexWrapperPass::runOnModule(Module &M) {
879 auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
880 bool NeedSSI = needsParamAccessSummary(M);
881 Index.emplace(buildModuleSummaryIndex(
1
Calling 'buildModuleSummaryIndex'
→
882 M,
883 [this](const Function &F) {
884 return &(this->getAnalysis<BlockFrequencyInfoWrapperPass>(
885 *const_cast<Function *>(&F))
886 .getBFI());
887 },
888 PSI,
889 [&](const Function &F) -> const StackSafetyInfo * {
890 return NeedSSI ? &getAnalysis<StackSafetyInfoWrapperPass>(
891 const_cast<Function &>(F))
892 .getResult()
893 : nullptr;
894 }));
895 return false;
896}
897
898bool ModuleSummaryIndexWrapperPass::doFinalization(Module &M) {
899 Index.reset();
900 return false;
901}
902
903void ModuleSummaryIndexWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
904 AU.setPreservesAll();
905 AU.addRequired<BlockFrequencyInfoWrapperPass>();
906 AU.addRequired<ProfileSummaryInfoWrapperPass>();
907 AU.addRequired<StackSafetyInfoWrapperPass>();
908}
909
910char ImmutableModuleSummaryIndexWrapperPass::ID = 0;
911
912ImmutableModuleSummaryIndexWrapperPass::ImmutableModuleSummaryIndexWrapperPass(
913 const ModuleSummaryIndex *Index)
914 : ImmutablePass(ID), Index(Index) {
915 initializeImmutableModuleSummaryIndexWrapperPassPass(
916 *PassRegistry::getPassRegistry());
917}
918
919void ImmutableModuleSummaryIndexWrapperPass::getAnalysisUsage(
920 AnalysisUsage &AU) const {
921 AU.setPreservesAll();
922}
923
924ImmutablePass *llvm::createImmutableModuleSummaryIndexWrapperPass(
925 const ModuleSummaryIndex *Index) {
926 return new ImmutableModuleSummaryIndexWrapperPass(Index);
927}
928
929INITIALIZE_PASS(ImmutableModuleSummaryIndexWrapperPass, "module-summary-info",static void *initializeImmutableModuleSummaryIndexWrapperPassPassOnce
(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "Module summary info"
, "module-summary-info", &ImmutableModuleSummaryIndexWrapperPass
::ID, PassInfo::NormalCtor_t(callDefaultCtor<ImmutableModuleSummaryIndexWrapperPass
>), false, true); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeImmutableModuleSummaryIndexWrapperPassPassFlag
; void llvm::initializeImmutableModuleSummaryIndexWrapperPassPass
(PassRegistry &Registry) { llvm::call_once(InitializeImmutableModuleSummaryIndexWrapperPassPassFlag
, initializeImmutableModuleSummaryIndexWrapperPassPassOnce, std
::ref(Registry)); }
930 "Module summary info", false, true)static void *initializeImmutableModuleSummaryIndexWrapperPassPassOnce
(PassRegistry &Registry) { PassInfo *PI = new PassInfo( "Module summary info"
, "module-summary-info", &ImmutableModuleSummaryIndexWrapperPass
::ID, PassInfo::NormalCtor_t(callDefaultCtor<ImmutableModuleSummaryIndexWrapperPass
>), false, true); Registry.registerPass(*PI, true); return
PI; } static llvm::once_flag InitializeImmutableModuleSummaryIndexWrapperPassPassFlag
; void llvm::initializeImmutableModuleSummaryIndexWrapperPassPass
(PassRegistry &Registry) { llvm::call_once(InitializeImmutableModuleSummaryIndexWrapperPassPassFlag
, initializeImmutableModuleSummaryIndexWrapperPassPassOnce, std
::ref(Registry)); }
←

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/IR/ModuleSummaryIndex.h

→
1//===- llvm/ModuleSummaryIndex.h - Module Summary Index ---------*- C++ -*-===//
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/// @file
10/// ModuleSummaryIndex.h This file contains the declarations the classes that
11/// hold the module index and summary for function importing.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_IR_MODULESUMMARYINDEX_H
16#define LLVM_IR_MODULESUMMARYINDEX_H
17
18#include "llvm/ADT/ArrayRef.h"
19#include "llvm/ADT/DenseMap.h"
20#include "llvm/ADT/STLExtras.h"
21#include "llvm/ADT/SmallString.h"
22#include "llvm/ADT/StringExtras.h"
23#include "llvm/ADT/StringMap.h"
24#include "llvm/ADT/StringRef.h"
25#include "llvm/ADT/TinyPtrVector.h"
26#include "llvm/IR/ConstantRange.h"
27#include "llvm/IR/GlobalValue.h"
28#include "llvm/IR/Module.h"
29#include "llvm/Support/Allocator.h"
30#include "llvm/Support/MathExtras.h"
31#include "llvm/Support/ScaledNumber.h"
32#include "llvm/Support/StringSaver.h"
33#include "llvm/Support/raw_ostream.h"
34#include <algorithm>
35#include <array>
36#include <cassert>
37#include <cstddef>
38#include <cstdint>
39#include <map>
40#include <memory>
41#include <set>
42#include <string>
43#include <utility>
44#include <vector>
45
46namespace llvm {
47
48template <class GraphType> struct GraphTraits;
49
50namespace yaml {
51
52template <typename T> struct MappingTraits;
53
54} // end namespace yaml
55
56/// Class to accumulate and hold information about a callee.
57struct CalleeInfo {
58 enum class HotnessType : uint8_t {
59 Unknown = 0,
60 Cold = 1,
61 None = 2,
62 Hot = 3,
63 Critical = 4
64 };
65
66 // The size of the bit-field might need to be adjusted if more values are
67 // added to HotnessType enum.
68 uint32_t Hotness : 3;
69
70 /// The value stored in RelBlockFreq has to be interpreted as the digits of
71 /// a scaled number with a scale of \p -ScaleShift.
72 uint32_t RelBlockFreq : 29;
73 static constexpr int32_t ScaleShift = 8;
74 static constexpr uint64_t MaxRelBlockFreq = (1 << 29) - 1;
75
76 CalleeInfo()
77 : Hotness(static_cast<uint32_t>(HotnessType::Unknown)), RelBlockFreq(0) {}
78 explicit CalleeInfo(HotnessType Hotness, uint64_t RelBF)
79 : Hotness(static_cast<uint32_t>(Hotness)), RelBlockFreq(RelBF) {}
80
81 void updateHotness(const HotnessType OtherHotness) {
82 Hotness = std::max(Hotness, static_cast<uint32_t>(OtherHotness));
83 }
84
85 HotnessType getHotness() const { return HotnessType(Hotness); }
86
87 /// Update \p RelBlockFreq from \p BlockFreq and \p EntryFreq
88 ///
89 /// BlockFreq is divided by EntryFreq and added to RelBlockFreq. To represent
90 /// fractional values, the result is represented as a fixed point number with
91 /// scale of -ScaleShift.
92 void updateRelBlockFreq(uint64_t BlockFreq, uint64_t EntryFreq) {
93 if (EntryFreq == 0)
29
←
Assuming 'EntryFreq' is not equal to 0
→
30
←
Taking false branch
→
94 return;
95 using Scaled64 = ScaledNumber<uint64_t>;
96 Scaled64 Temp(BlockFreq, ScaleShift);
97 Temp /= Scaled64::get(EntryFreq);
31
←
Calling 'ScaledNumber::operator/='
→
46
←
Returning from 'ScaledNumber::operator/='
→
98
99 uint64_t Sum =
100 SaturatingAdd<uint64_t>(Temp.toInt<uint64_t>(), RelBlockFreq);
47
←
Calling 'ScaledNumber::toInt'
→
101 Sum = std::min(Sum, uint64_t(MaxRelBlockFreq));
102 RelBlockFreq = static_cast<uint32_t>(Sum);
103 }
104};
105
106inline const char *getHotnessName(CalleeInfo::HotnessType HT) {
107 switch (HT) {
108 case CalleeInfo::HotnessType::Unknown:
109 return "unknown";
110 case CalleeInfo::HotnessType::Cold:
111 return "cold";
112 case CalleeInfo::HotnessType::None:
113 return "none";
114 case CalleeInfo::HotnessType::Hot:
115 return "hot";
116 case CalleeInfo::HotnessType::Critical:
117 return "critical";
118 }
119 llvm_unreachable("invalid hotness")__builtin_unreachable();
120}
121
122class GlobalValueSummary;
123
124using GlobalValueSummaryList = std::vector<std::unique_ptr<GlobalValueSummary>>;
125
126struct alignas(8) GlobalValueSummaryInfo {
127 union NameOrGV {
128 NameOrGV(bool HaveGVs) {
129 if (HaveGVs)
130 GV = nullptr;
131 else
132 Name = "";
133 }
134
135 /// The GlobalValue corresponding to this summary. This is only used in
136 /// per-module summaries and when the IR is available. E.g. when module
137 /// analysis is being run, or when parsing both the IR and the summary
138 /// from assembly.
139 const GlobalValue *GV;
140
141 /// Summary string representation. This StringRef points to BC module
142 /// string table and is valid until module data is stored in memory.
143 /// This is guaranteed to happen until runThinLTOBackend function is
144 /// called, so it is safe to use this field during thin link. This field
145 /// is only valid if summary index was loaded from BC file.
146 StringRef Name;
147 } U;
148
149 GlobalValueSummaryInfo(bool HaveGVs) : U(HaveGVs) {}
150
151 /// List of global value summary structures for a particular value held
152 /// in the GlobalValueMap. Requires a vector in the case of multiple
153 /// COMDAT values of the same name.
154 GlobalValueSummaryList SummaryList;
155};
156
157/// Map from global value GUID to corresponding summary structures. Use a
158/// std::map rather than a DenseMap so that pointers to the map's value_type
159/// (which are used by ValueInfo) are not invalidated by insertion. Also it will
160/// likely incur less overhead, as the value type is not very small and the size
161/// of the map is unknown, resulting in inefficiencies due to repeated
162/// insertions and resizing.
163using GlobalValueSummaryMapTy =
164 std::map<GlobalValue::GUID, GlobalValueSummaryInfo>;
165
166/// Struct that holds a reference to a particular GUID in a global value
167/// summary.
168struct ValueInfo {
169 enum Flags { HaveGV = 1, ReadOnly = 2, WriteOnly = 4 };
170 PointerIntPair<const GlobalValueSummaryMapTy::value_type *, 3, int>
171 RefAndFlags;
172
173 ValueInfo() = default;
174 ValueInfo(bool HaveGVs, const GlobalValueSummaryMapTy::value_type *R) {
175 RefAndFlags.setPointer(R);
176 RefAndFlags.setInt(HaveGVs);
177 }
178
179 explicit operator bool() const { return getRef(); }
180
181 GlobalValue::GUID getGUID() const { return getRef()->first; }
182 const GlobalValue *getValue() const {
183 assert(haveGVs())((void)0);
184 return getRef()->second.U.GV;
185 }
186
187 ArrayRef<std::unique_ptr<GlobalValueSummary>> getSummaryList() const {
188 return getRef()->second.SummaryList;
189 }
190
191 StringRef name() const {
192 return haveGVs() ? getRef()->second.U.GV->getName()
193 : getRef()->second.U.Name;
194 }
195
196 bool haveGVs() const { return RefAndFlags.getInt() & HaveGV; }
197 bool isReadOnly() const {
198 assert(isValidAccessSpecifier())((void)0);
199 return RefAndFlags.getInt() & ReadOnly;
200 }
201 bool isWriteOnly() const {
202 assert(isValidAccessSpecifier())((void)0);
203 return RefAndFlags.getInt() & WriteOnly;
204 }
205 unsigned getAccessSpecifier() const {
206 assert(isValidAccessSpecifier())((void)0);
207 return RefAndFlags.getInt() & (ReadOnly | WriteOnly);
208 }
209 bool isValidAccessSpecifier() const {
210 unsigned BadAccessMask = ReadOnly | WriteOnly;
211 return (RefAndFlags.getInt() & BadAccessMask) != BadAccessMask;
212 }
213 void setReadOnly() {
214 // We expect ro/wo attribute to set only once during
215 // ValueInfo lifetime.
216 assert(getAccessSpecifier() == 0)((void)0);
217 RefAndFlags.setInt(RefAndFlags.getInt() | ReadOnly);
218 }
219 void setWriteOnly() {
220 assert(getAccessSpecifier() == 0)((void)0);
221 RefAndFlags.setInt(RefAndFlags.getInt() | WriteOnly);
222 }
223
224 const GlobalValueSummaryMapTy::value_type *getRef() const {
225 return RefAndFlags.getPointer();
226 }
227
228 /// Returns the most constraining visibility among summaries. The
229 /// visibilities, ordered from least to most constraining, are: default,
230 /// protected and hidden.
231 GlobalValue::VisibilityTypes getELFVisibility() const;
232
233 /// Checks if all summaries are DSO local (have the flag set). When DSOLocal
234 /// propagation has been done, set the parameter to enable fast check.
235 bool isDSOLocal(bool WithDSOLocalPropagation = false) const;
236
237 /// Checks if all copies are eligible for auto-hiding (have flag set).
238 bool canAutoHide() const;
239};
240
241inline raw_ostream &operator<<(raw_ostream &OS, const ValueInfo &VI) {
242 OS << VI.getGUID();
243 if (!VI.name().empty())
244 OS << " (" << VI.name() << ")";
245 return OS;
246}
247
248inline bool operator==(const ValueInfo &A, const ValueInfo &B) {
249 assert(A.getRef() && B.getRef() &&((void)0)
250 "Need ValueInfo with non-null Ref for comparison")((void)0);
251 return A.getRef() == B.getRef();
252}
253
254inline bool operator!=(const ValueInfo &A, const ValueInfo &B) {
255 assert(A.getRef() && B.getRef() &&((void)0)
256 "Need ValueInfo with non-null Ref for comparison")((void)0);
257 return A.getRef() != B.getRef();
258}
259
260inline bool operator<(const ValueInfo &A, const ValueInfo &B) {
261 assert(A.getRef() && B.getRef() &&((void)0)
262 "Need ValueInfo with non-null Ref to compare GUIDs")((void)0);
263 return A.getGUID() < B.getGUID();
264}
265
266template <> struct DenseMapInfo<ValueInfo> {
267 static inline ValueInfo getEmptyKey() {
268 return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-8);
269 }
270
271 static inline ValueInfo getTombstoneKey() {
272 return ValueInfo(false, (GlobalValueSummaryMapTy::value_type *)-16);
273 }
274
275 static inline bool isSpecialKey(ValueInfo V) {
276 return V == getTombstoneKey() || V == getEmptyKey();
277 }
278
279 static bool isEqual(ValueInfo L, ValueInfo R) {
280 // We are not supposed to mix ValueInfo(s) with different HaveGVs flag
281 // in a same container.
282 assert(isSpecialKey(L) || isSpecialKey(R) || (L.haveGVs() == R.haveGVs()))((void)0);
283 return L.getRef() == R.getRef();
284 }
285 static unsigned getHashValue(ValueInfo I) { return (uintptr_t)I.getRef(); }
286};
287
288/// Function and variable summary information to aid decisions and
289/// implementation of importing.
290class GlobalValueSummary {
291public:
292 /// Sububclass discriminator (for dyn_cast<> et al.)
293 enum SummaryKind : unsigned { AliasKind, FunctionKind, GlobalVarKind };
294
295 /// Group flags (Linkage, NotEligibleToImport, etc.) as a bitfield.
296 struct GVFlags {
297 /// The linkage type of the associated global value.
298 ///
299 /// One use is to flag values that have local linkage types and need to
300 /// have module identifier appended before placing into the combined
301 /// index, to disambiguate from other values with the same name.
302 /// In the future this will be used to update and optimize linkage
303 /// types based on global summary-based analysis.
304 unsigned Linkage : 4;
305
306 /// Indicates the visibility.
307 unsigned Visibility : 2;
308
309 /// Indicate if the global value cannot be imported (e.g. it cannot
310 /// be renamed or references something that can't be renamed).
311 unsigned NotEligibleToImport : 1;
312
313 /// In per-module summary, indicate that the global value must be considered
314 /// a live root for index-based liveness analysis. Used for special LLVM
315 /// values such as llvm.global_ctors that the linker does not know about.
316 ///
317 /// In combined summary, indicate that the global value is live.
318 unsigned Live : 1;
319
320 /// Indicates that the linker resolved the symbol to a definition from
321 /// within the same linkage unit.
322 unsigned DSOLocal : 1;
323
324 /// In the per-module summary, indicates that the global value is
325 /// linkonce_odr and global unnamed addr (so eligible for auto-hiding
326 /// via hidden visibility). In the combined summary, indicates that the
327 /// prevailing linkonce_odr copy can be auto-hidden via hidden visibility
328 /// when it is upgraded to weak_odr in the backend. This is legal when
329 /// all copies are eligible for auto-hiding (i.e. all copies were
330 /// linkonce_odr global unnamed addr. If any copy is not (e.g. it was
331 /// originally weak_odr, we cannot auto-hide the prevailing copy as it
332 /// means the symbol was externally visible.
333 unsigned CanAutoHide : 1;
334
335 /// Convenience Constructors
336 explicit GVFlags(GlobalValue::LinkageTypes Linkage,
337 GlobalValue::VisibilityTypes Visibility,
338 bool NotEligibleToImport, bool Live, bool IsLocal,
339 bool CanAutoHide)
340 : Linkage(Linkage), Visibility(Visibility),
341 NotEligibleToImport(NotEligibleToImport), Live(Live),
342 DSOLocal(IsLocal), CanAutoHide(CanAutoHide) {}
343 };
344
345private:
346 /// Kind of summary for use in dyn_cast<> et al.
347 SummaryKind Kind;
348
349 GVFlags Flags;
350
351 /// This is the hash of the name of the symbol in the original file. It is
352 /// identical to the GUID for global symbols, but differs for local since the
353 /// GUID includes the module level id in the hash.
354 GlobalValue::GUID OriginalName = 0;
355
356 /// Path of module IR containing value's definition, used to locate
357 /// module during importing.
358 ///
359 /// This is only used during parsing of the combined index, or when
360 /// parsing the per-module index for creation of the combined summary index,
361 /// not during writing of the per-module index which doesn't contain a
362 /// module path string table.
363 StringRef ModulePath;
364
365 /// List of values referenced by this global value's definition
366 /// (either by the initializer of a global variable, or referenced
367 /// from within a function). This does not include functions called, which
368 /// are listed in the derived FunctionSummary object.
369 std::vector<ValueInfo> RefEdgeList;
370
371protected:
372 GlobalValueSummary(SummaryKind K, GVFlags Flags, std::vector<ValueInfo> Refs)
373 : Kind(K), Flags(Flags), RefEdgeList(std::move(Refs)) {
374 assert((K != AliasKind || Refs.empty()) &&((void)0)
375 "Expect no references for AliasSummary")((void)0);
376 }
377
378public:
379 virtual ~GlobalValueSummary() = default;
380
381 /// Returns the hash of the original name, it is identical to the GUID for
382 /// externally visible symbols, but not for local ones.
383 GlobalValue::GUID getOriginalName() const { return OriginalName; }
384
385 /// Initialize the original name hash in this summary.
386 void setOriginalName(GlobalValue::GUID Name) { OriginalName = Name; }
387
388 /// Which kind of summary subclass this is.
389 SummaryKind getSummaryKind() const { return Kind; }
390
391 /// Set the path to the module containing this function, for use in
392 /// the combined index.
393 void setModulePath(StringRef ModPath) { ModulePath = ModPath; }
394
395 /// Get the path to the module containing this function.
396 StringRef modulePath() const { return ModulePath; }
397
398 /// Get the flags for this GlobalValue (see \p struct GVFlags).
399 GVFlags flags() const { return Flags; }
400
401 /// Return linkage type recorded for this global value.
402 GlobalValue::LinkageTypes linkage() const {
403 return static_cast<GlobalValue::LinkageTypes>(Flags.Linkage);
404 }
405
406 /// Sets the linkage to the value determined by global summary-based
407 /// optimization. Will be applied in the ThinLTO backends.
408 void setLinkage(GlobalValue::LinkageTypes Linkage) {
409 Flags.Linkage = Linkage;
410 }
411
412 /// Return true if this global value can't be imported.
413 bool notEligibleToImport() const { return Flags.NotEligibleToImport; }
414
415 bool isLive() const { return Flags.Live; }
416
417 void setLive(bool Live) { Flags.Live = Live; }
418
419 void setDSOLocal(bool Local) { Flags.DSOLocal = Local; }
420
421 bool isDSOLocal() const { return Flags.DSOLocal; }
422
423 void setCanAutoHide(bool CanAutoHide) { Flags.CanAutoHide = CanAutoHide; }
424
425 bool canAutoHide() const { return Flags.CanAutoHide; }
426
427 GlobalValue::VisibilityTypes getVisibility() const {
428 return (GlobalValue::VisibilityTypes)Flags.Visibility;
429 }
430 void setVisibility(GlobalValue::VisibilityTypes Vis) {
431 Flags.Visibility = (unsigned)Vis;
432 }
433
434 /// Flag that this global value cannot be imported.
435 void setNotEligibleToImport() { Flags.NotEligibleToImport = true; }
436
437 /// Return the list of values referenced by this global value definition.
438 ArrayRef<ValueInfo> refs() const { return RefEdgeList; }
439
440 /// If this is an alias summary, returns the summary of the aliased object (a
441 /// global variable or function), otherwise returns itself.
442 GlobalValueSummary *getBaseObject();
443 const GlobalValueSummary *getBaseObject() const;
444
445 friend class ModuleSummaryIndex;
446};
447
448/// Alias summary information.
449class AliasSummary : public GlobalValueSummary {
450 ValueInfo AliaseeValueInfo;
451
452 /// This is the Aliasee in the same module as alias (could get from VI, trades
453 /// memory for time). Note that this pointer may be null (and the value info
454 /// empty) when we have a distributed index where the alias is being imported
455 /// (as a copy of the aliasee), but the aliasee is not.
456 GlobalValueSummary *AliaseeSummary;
457
458public:
459 AliasSummary(GVFlags Flags)
460 : GlobalValueSummary(AliasKind, Flags, ArrayRef<ValueInfo>{}),
461 AliaseeSummary(nullptr) {}
462
463 /// Check if this is an alias summary.
464 static bool classof(const GlobalValueSummary *GVS) {
465 return GVS->getSummaryKind() == AliasKind;
466 }
467
468 void setAliasee(ValueInfo &AliaseeVI, GlobalValueSummary *Aliasee) {
469 AliaseeValueInfo = AliaseeVI;
470 AliaseeSummary = Aliasee;
471 }
472
473 bool hasAliasee() const {
474 assert(!!AliaseeSummary == (AliaseeValueInfo &&((void)0)
475 !AliaseeValueInfo.getSummaryList().empty()) &&((void)0)
476 "Expect to have both aliasee summary and summary list or neither")((void)0);
477 return !!AliaseeSummary;
478 }
479
480 const GlobalValueSummary &getAliasee() const {
481 assert(AliaseeSummary && "Unexpected missing aliasee summary")((void)0);
482 return *AliaseeSummary;
483 }
484
485 GlobalValueSummary &getAliasee() {
486 return const_cast<GlobalValueSummary &>(
487 static_cast<const AliasSummary *>(this)->getAliasee());
488 }
489 ValueInfo getAliaseeVI() const {
490 assert(AliaseeValueInfo && "Unexpected missing aliasee")((void)0);
491 return AliaseeValueInfo;
492 }
493 GlobalValue::GUID getAliaseeGUID() const {
494 assert(AliaseeValueInfo && "Unexpected missing aliasee")((void)0);
495 return AliaseeValueInfo.getGUID();
496 }
497};
498
499const inline GlobalValueSummary *GlobalValueSummary::getBaseObject() const {
500 if (auto *AS = dyn_cast<AliasSummary>(this))
501 return &AS->getAliasee();
502 return this;
503}
504
505inline GlobalValueSummary *GlobalValueSummary::getBaseObject() {
506 if (auto *AS = dyn_cast<AliasSummary>(this))
507 return &AS->getAliasee();
508 return this;
509}
510
511/// Function summary information to aid decisions and implementation of
512/// importing.
513class FunctionSummary : public GlobalValueSummary {
514public:
515 /// <CalleeValueInfo, CalleeInfo> call edge pair.
516 using EdgeTy = std::pair<ValueInfo, CalleeInfo>;
517
518 /// Types for -force-summary-edges-cold debugging option.
519 enum ForceSummaryHotnessType : unsigned {
520 FSHT_None,
521 FSHT_AllNonCritical,
522 FSHT_All
523 };
524
525 /// An "identifier" for a virtual function. This contains the type identifier
526 /// represented as a GUID and the offset from the address point to the virtual
527 /// function pointer, where "address point" is as defined in the Itanium ABI:
528 /// https://itanium-cxx-abi.github.io/cxx-abi/abi.html#vtable-general
529 struct VFuncId {
530 GlobalValue::GUID GUID;
531 uint64_t Offset;
532 };
533
534 /// A specification for a virtual function call with all constant integer
535 /// arguments. This is used to perform virtual constant propagation on the
536 /// summary.
537 struct ConstVCall {
538 VFuncId VFunc;
539 std::vector<uint64_t> Args;
540 };
541
542 /// All type identifier related information. Because these fields are
543 /// relatively uncommon we only allocate space for them if necessary.
544 struct TypeIdInfo {
545 /// List of type identifiers used by this function in llvm.type.test
546 /// intrinsics referenced by something other than an llvm.assume intrinsic,
547 /// represented as GUIDs.
548 std::vector<GlobalValue::GUID> TypeTests;
549
550 /// List of virtual calls made by this function using (respectively)
551 /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics that do
552 /// not have all constant integer arguments.
553 std::vector<VFuncId> TypeTestAssumeVCalls, TypeCheckedLoadVCalls;
554
555 /// List of virtual calls made by this function using (respectively)
556 /// llvm.assume(llvm.type.test) or llvm.type.checked.load intrinsics with
557 /// all constant integer arguments.
558 std::vector<ConstVCall> TypeTestAssumeConstVCalls,
559 TypeCheckedLoadConstVCalls;
560 };
561
562 /// Flags specific to function summaries.
563 struct FFlags {
564 // Function attribute flags. Used to track if a function accesses memory,
565 // recurses or aliases.
566 unsigned ReadNone : 1;
567 unsigned ReadOnly : 1;
568 unsigned NoRecurse : 1;
569 unsigned ReturnDoesNotAlias : 1;
570
571 // Indicate if the global value cannot be inlined.
572 unsigned NoInline : 1;
573 // Indicate if function should be always inlined.
574 unsigned AlwaysInline : 1;
575 };
576
577 /// Describes the uses of a parameter by the function.
578 struct ParamAccess {
579 static constexpr uint32_t RangeWidth = 64;
580
581 /// Describes the use of a value in a call instruction, specifying the
582 /// call's target, the value's parameter number, and the possible range of
583 /// offsets from the beginning of the value that are passed.
584 struct Call {
585 uint64_t ParamNo = 0;
586 ValueInfo Callee;
587 ConstantRange Offsets{/*BitWidth=*/RangeWidth, /*isFullSet=*/true};
588
589 Call() = default;
590 Call(uint64_t ParamNo, ValueInfo Callee, const ConstantRange &Offsets)
591 : ParamNo(ParamNo), Callee(Callee), Offsets(Offsets) {}
592 };
593
594 uint64_t ParamNo = 0;
595 /// The range contains byte offsets from the parameter pointer which
596 /// accessed by the function. In the per-module summary, it only includes
597 /// accesses made by the function instructions. In the combined summary, it
598 /// also includes accesses by nested function calls.
599 ConstantRange Use{/*BitWidth=*/RangeWidth, /*isFullSet=*/true};
600 /// In the per-module summary, it summarizes the byte offset applied to each
601 /// pointer parameter before passing to each corresponding callee.
602 /// In the combined summary, it's empty and information is propagated by
603 /// inter-procedural analysis and applied to the Use field.
604 std::vector<Call> Calls;
605
606 ParamAccess() = default;
607 ParamAccess(uint64_t ParamNo, const ConstantRange &Use)
608 : ParamNo(ParamNo), Use(Use) {}
609 };
610
611 /// Create an empty FunctionSummary (with specified call edges).
612 /// Used to represent external nodes and the dummy root node.
613 static FunctionSummary
614 makeDummyFunctionSummary(std::vector<FunctionSummary::EdgeTy> Edges) {
615 return FunctionSummary(
616 FunctionSummary::GVFlags(
617 GlobalValue::LinkageTypes::AvailableExternallyLinkage,
618 GlobalValue::DefaultVisibility,
619 /*NotEligibleToImport=*/true, /*Live=*/true, /*IsLocal=*/false,
620 /*CanAutoHide=*/false),
621 /*NumInsts=*/0, FunctionSummary::FFlags{}, /*EntryCount=*/0,
622 std::vector<ValueInfo>(), std::move(Edges),
623 std::vector<GlobalValue::GUID>(),
624 std::vector<FunctionSummary::VFuncId>(),
625 std::vector<FunctionSummary::VFuncId>(),
626 std::vector<FunctionSummary::ConstVCall>(),
627 std::vector<FunctionSummary::ConstVCall>(),
628 std::vector<FunctionSummary::ParamAccess>());
629 }
630
631 /// A dummy node to reference external functions that aren't in the index
632 static FunctionSummary ExternalNode;
633
634private:
635 /// Number of instructions (ignoring debug instructions, e.g.) computed
636 /// during the initial compile step when the summary index is first built.
637 unsigned InstCount;
638
639 /// Function summary specific flags.
640 FFlags FunFlags;
641
642 /// The synthesized entry count of the function.
643 /// This is only populated during ThinLink phase and remains unused while
644 /// generating per-module summaries.
645 uint64_t EntryCount = 0;
646
647 /// List of <CalleeValueInfo, CalleeInfo> call edge pairs from this function.
648 std::vector<EdgeTy> CallGraphEdgeList;
649
650 std::unique_ptr<TypeIdInfo> TIdInfo;
651
652 /// Uses for every parameter to this function.
653 using ParamAccessesTy = std::vector<ParamAccess>;
654 std::unique_ptr<ParamAccessesTy> ParamAccesses;
655
656public:
657 FunctionSummary(GVFlags Flags, unsigned NumInsts, FFlags FunFlags,
658 uint64_t EntryCount, std::vector<ValueInfo> Refs,
659 std::vector<EdgeTy> CGEdges,
660 std::vector<GlobalValue::GUID> TypeTests,
661 std::vector<VFuncId> TypeTestAssumeVCalls,
662 std::vector<VFuncId> TypeCheckedLoadVCalls,
663 std::vector<ConstVCall> TypeTestAssumeConstVCalls,
664 std::vector<ConstVCall> TypeCheckedLoadConstVCalls,
665 std::vector<ParamAccess> Params)
666 : GlobalValueSummary(FunctionKind, Flags, std::move(Refs)),
667 InstCount(NumInsts), FunFlags(FunFlags), EntryCount(EntryCount),
668 CallGraphEdgeList(std::move(CGEdges)) {
669 if (!TypeTests.empty() || !TypeTestAssumeVCalls.empty() ||
670 !TypeCheckedLoadVCalls.empty() || !TypeTestAssumeConstVCalls.empty() ||
671 !TypeCheckedLoadConstVCalls.empty())
672 TIdInfo = std::make_unique<TypeIdInfo>(
673 TypeIdInfo{std::move(TypeTests), std::move(TypeTestAssumeVCalls),
674 std::move(TypeCheckedLoadVCalls),
675 std::move(TypeTestAssumeConstVCalls),
676 std::move(TypeCheckedLoadConstVCalls)});
677 if (!Params.empty())
678 ParamAccesses = std::make_unique<ParamAccessesTy>(std::move(Params));
679 }
680 // Gets the number of readonly and writeonly refs in RefEdgeList
681 std::pair<unsigned, unsigned> specialRefCounts() const;
682
683 /// Check if this is a function summary.
684 static bool classof(const GlobalValueSummary *GVS) {
685 return GVS->getSummaryKind() == FunctionKind;
686 }
687
688 /// Get function summary flags.
689 FFlags fflags() const { return FunFlags; }
690
691 /// Get the instruction count recorded for this function.
692 unsigned instCount() const { return InstCount; }
693
694 /// Get the synthetic entry count for this function.
695 uint64_t entryCount() const { return EntryCount; }
696
697 /// Set the synthetic entry count for this function.
698 void setEntryCount(uint64_t EC) { EntryCount = EC; }
699
700 /// Return the list of <CalleeValueInfo, CalleeInfo> pairs.
701 ArrayRef<EdgeTy> calls() const { return CallGraphEdgeList; }
702
703 void addCall(EdgeTy E) { CallGraphEdgeList.push_back(E); }
704
705 /// Returns the list of type identifiers used by this function in
706 /// llvm.type.test intrinsics other than by an llvm.assume intrinsic,
707 /// represented as GUIDs.
708 ArrayRef<GlobalValue::GUID> type_tests() const {
709 if (TIdInfo)
710 return TIdInfo->TypeTests;
711 return {};
712 }
713
714 /// Returns the list of virtual calls made by this function using
715 /// llvm.assume(llvm.type.test) intrinsics that do not have all constant
716 /// integer arguments.
717 ArrayRef<VFuncId> type_test_assume_vcalls() const {
718 if (TIdInfo)
719 return TIdInfo->TypeTestAssumeVCalls;
720 return {};
721 }
722
723 /// Returns the list of virtual calls made by this function using
724 /// llvm.type.checked.load intrinsics that do not have all constant integer
725 /// arguments.
726 ArrayRef<VFuncId> type_checked_load_vcalls() const {
727 if (TIdInfo)
728 return TIdInfo->TypeCheckedLoadVCalls;
729 return {};
730 }
731
732 /// Returns the list of virtual calls made by this function using
733 /// llvm.assume(llvm.type.test) intrinsics with all constant integer
734 /// arguments.
735 ArrayRef<ConstVCall> type_test_assume_const_vcalls() const {
736 if (TIdInfo)
737 return TIdInfo->TypeTestAssumeConstVCalls;
738 return {};
739 }
740
741 /// Returns the list of virtual calls made by this function using
742 /// llvm.type.checked.load intrinsics with all constant integer arguments.
743 ArrayRef<ConstVCall> type_checked_load_const_vcalls() const {
744 if (TIdInfo)
745 return TIdInfo->TypeCheckedLoadConstVCalls;
746 return {};
747 }
748
749 /// Returns the list of known uses of pointer parameters.
750 ArrayRef<ParamAccess> paramAccesses() const {
751 if (ParamAccesses)
752 return *ParamAccesses;
753 return {};
754 }
755
756 /// Sets the list of known uses of pointer parameters.
757 void setParamAccesses(std::vector<ParamAccess> NewParams) {
758 if (NewParams.empty())
759 ParamAccesses.reset();
760 else if (ParamAccesses)
761 *ParamAccesses = std::move(NewParams);
762 else
763 ParamAccesses = std::make_unique<ParamAccessesTy>(std::move(NewParams));
764 }
765
766 /// Add a type test to the summary. This is used by WholeProgramDevirt if we
767 /// were unable to devirtualize a checked call.
768 void addTypeTest(GlobalValue::GUID Guid) {
769 if (!TIdInfo)
770 TIdInfo = std::make_unique<TypeIdInfo>();
771 TIdInfo->TypeTests.push_back(Guid);
772 }
773
774 const TypeIdInfo *getTypeIdInfo() const { return TIdInfo.get(); };
775
776 friend struct GraphTraits<ValueInfo>;
777};
778
779template <> struct DenseMapInfo<FunctionSummary::VFuncId> {
780 static FunctionSummary::VFuncId getEmptyKey() { return {0, uint64_t(-1)}; }
781
782 static FunctionSummary::VFuncId getTombstoneKey() {
783 return {0, uint64_t(-2)};
784 }
785
786 static bool isEqual(FunctionSummary::VFuncId L, FunctionSummary::VFuncId R) {
787 return L.GUID == R.GUID && L.Offset == R.Offset;
788 }
789
790 static unsigned getHashValue(FunctionSummary::VFuncId I) { return I.GUID; }
791};
792
793template <> struct DenseMapInfo<FunctionSummary::ConstVCall> {
794 static FunctionSummary::ConstVCall getEmptyKey() {
795 return {{0, uint64_t(-1)}, {}};
796 }
797
798 static FunctionSummary::ConstVCall getTombstoneKey() {
799 return {{0, uint64_t(-2)}, {}};
800 }
801
802 static bool isEqual(FunctionSummary::ConstVCall L,
803 FunctionSummary::ConstVCall R) {
804 return DenseMapInfo<FunctionSummary::VFuncId>::isEqual(L.VFunc, R.VFunc) &&
805 L.Args == R.Args;
806 }
807
808 static unsigned getHashValue(FunctionSummary::ConstVCall I) {
809 return I.VFunc.GUID;
810 }
811};
812
813/// The ValueInfo and offset for a function within a vtable definition
814/// initializer array.
815struct VirtFuncOffset {
816 VirtFuncOffset(ValueInfo VI, uint64_t Offset)
817 : FuncVI(VI), VTableOffset(Offset) {}
818
819 ValueInfo FuncVI;
820 uint64_t VTableOffset;
821};
822/// List of functions referenced by a particular vtable definition.
823using VTableFuncList = std::vector<VirtFuncOffset>;
824
825/// Global variable summary information to aid decisions and
826/// implementation of importing.
827///
828/// Global variable summary has two extra flag, telling if it is
829/// readonly or writeonly. Both readonly and writeonly variables
830/// can be optimized in the backed: readonly variables can be
831/// const-folded, while writeonly vars can be completely eliminated
832/// together with corresponding stores. We let both things happen
833/// by means of internalizing such variables after ThinLTO import.
834class GlobalVarSummary : public GlobalValueSummary {
835private:
836 /// For vtable definitions this holds the list of functions and
837 /// their corresponding offsets within the initializer array.
838 std::unique_ptr<VTableFuncList> VTableFuncs;
839
840public:
841 struct GVarFlags {
842 GVarFlags(bool ReadOnly, bool WriteOnly, bool Constant,
843 GlobalObject::VCallVisibility Vis)
844 : MaybeReadOnly(ReadOnly), MaybeWriteOnly(WriteOnly),
845 Constant(Constant), VCallVisibility(Vis) {}
846
847 // If true indicates that this global variable might be accessed
848 // purely by non-volatile load instructions. This in turn means
849 // it can be internalized in source and destination modules during
850 // thin LTO import because it neither modified nor its address
851 // is taken.
852 unsigned MaybeReadOnly : 1;
853 // If true indicates that variable is possibly only written to, so
854 // its value isn't loaded and its address isn't taken anywhere.
855 // False, when 'Constant' attribute is set.
856 unsigned MaybeWriteOnly : 1;
857 // Indicates that value is a compile-time constant. Global variable
858 // can be 'Constant' while not being 'ReadOnly' on several occasions:
859 // - it is volatile, (e.g mapped device address)
860 // - its address is taken, meaning that unlike 'ReadOnly' vars we can't
861 // internalize it.
862 // Constant variables are always imported thus giving compiler an
863 // opportunity to make some extra optimizations. Readonly constants
864 // are also internalized.
865 unsigned Constant : 1;
866 // Set from metadata on vtable definitions during the module summary
867 // analysis.
868 unsigned VCallVisibility : 2;
869 } VarFlags;
870
871 GlobalVarSummary(GVFlags Flags, GVarFlags VarFlags,
872 std::vector<ValueInfo> Refs)
873 : GlobalValueSummary(GlobalVarKind, Flags, std::move(Refs)),
874 VarFlags(VarFlags) {}
875
876 /// Check if this is a global variable summary.
877 static bool classof(const GlobalValueSummary *GVS) {
878 return GVS->getSummaryKind() == GlobalVarKind;
879 }
880
881 GVarFlags varflags() const { return VarFlags; }
882 void setReadOnly(bool RO) { VarFlags.MaybeReadOnly = RO; }
883 void setWriteOnly(bool WO) { VarFlags.MaybeWriteOnly = WO; }
884 bool maybeReadOnly() const { return VarFlags.MaybeReadOnly; }
885 bool maybeWriteOnly() const { return VarFlags.MaybeWriteOnly; }
886 bool isConstant() const { return VarFlags.Constant; }
887 void setVCallVisibility(GlobalObject::VCallVisibility Vis) {
888 VarFlags.VCallVisibility = Vis;
889 }
890 GlobalObject::VCallVisibility getVCallVisibility() const {
891 return (GlobalObject::VCallVisibility)VarFlags.VCallVisibility;
892 }
893
894 void setVTableFuncs(VTableFuncList Funcs) {
895 assert(!VTableFuncs)((void)0);
896 VTableFuncs = std::make_unique<VTableFuncList>(std::move(Funcs));
897 }
898
899 ArrayRef<VirtFuncOffset> vTableFuncs() const {
900 if (VTableFuncs)
901 return *VTableFuncs;
902 return {};
903 }
904};
905
906struct TypeTestResolution {
907 /// Specifies which kind of type check we should emit for this byte array.
908 /// See http://clang.llvm.org/docs/ControlFlowIntegrityDesign.html for full
909 /// details on each kind of check; the enumerators are described with
910 /// reference to that document.
911 enum Kind {
912 Unsat, ///< Unsatisfiable type (i.e. no global has this type metadata)
913 ByteArray, ///< Test a byte array (first example)
914 Inline, ///< Inlined bit vector ("Short Inline Bit Vectors")
915 Single, ///< Single element (last example in "Short Inline Bit Vectors")
916 AllOnes, ///< All-ones bit vector ("Eliminating Bit Vector Checks for
917 /// All-Ones Bit Vectors")
918 Unknown, ///< Unknown (analysis not performed, don't lower)
919 } TheKind = Unknown;
920
921 /// Range of size-1 expressed as a bit width. For example, if the size is in
922 /// range [1,256], this number will be 8. This helps generate the most compact
923 /// instruction sequences.
924 unsigned SizeM1BitWidth = 0;
925
926 // The following fields are only used if the target does not support the use
927 // of absolute symbols to store constants. Their meanings are the same as the
928 // corresponding fields in LowerTypeTestsModule::TypeIdLowering in
929 // LowerTypeTests.cpp.
930
931 uint64_t AlignLog2 = 0;
932 uint64_t SizeM1 = 0;
933 uint8_t BitMask = 0;
934 uint64_t InlineBits = 0;
935};
936
937struct WholeProgramDevirtResolution {
938 enum Kind {
939 Indir, ///< Just do a regular virtual call
940 SingleImpl, ///< Single implementation devirtualization
941 BranchFunnel, ///< When retpoline mitigation is enabled, use a branch funnel
942 ///< that is defined in the merged module. Otherwise same as
943 ///< Indir.
944 } TheKind = Indir;
945
946 std::string SingleImplName;
947
948 struct ByArg {
949 enum Kind {
950 Indir, ///< Just do a regular virtual call
951 UniformRetVal, ///< Uniform return value optimization
952 UniqueRetVal, ///< Unique return value optimization
953 VirtualConstProp, ///< Virtual constant propagation
954 } TheKind = Indir;
955
956 /// Additional information for the resolution:
957 /// - UniformRetVal: the uniform return value.
958 /// - UniqueRetVal: the return value associated with the unique vtable (0 or
959 /// 1).
960 uint64_t Info = 0;
961
962 // The following fields are only used if the target does not support the use
963 // of absolute symbols to store constants.
964
965 uint32_t Byte = 0;
966 uint32_t Bit = 0;
967 };
968
969 /// Resolutions for calls with all constant integer arguments (excluding the
970 /// first argument, "this"), where the key is the argument vector.
971 std::map<std::vector<uint64_t>, ByArg> ResByArg;
972};
973
974struct TypeIdSummary {
975 TypeTestResolution TTRes;
976
977 /// Mapping from byte offset to whole-program devirt resolution for that
978 /// (typeid, byte offset) pair.
979 std::map<uint64_t, WholeProgramDevirtResolution> WPDRes;
980};
981
982/// 160 bits SHA1
983using ModuleHash = std::array<uint32_t, 5>;
984
985/// Type used for iterating through the global value summary map.
986using const_gvsummary_iterator = GlobalValueSummaryMapTy::const_iterator;
987using gvsummary_iterator = GlobalValueSummaryMapTy::iterator;
988
989/// String table to hold/own module path strings, which additionally holds the
990/// module ID assigned to each module during the plugin step, as well as a hash
991/// of the module. The StringMap makes a copy of and owns inserted strings.
992using ModulePathStringTableTy = StringMap<std::pair<uint64_t, ModuleHash>>;
993
994/// Map of global value GUID to its summary, used to identify values defined in
995/// a particular module, and provide efficient access to their summary.
996using GVSummaryMapTy = DenseMap<GlobalValue::GUID, GlobalValueSummary *>;
997
998/// Map of a type GUID to type id string and summary (multimap used
999/// in case of GUID conflicts).
1000using TypeIdSummaryMapTy =
1001 std::multimap<GlobalValue::GUID, std::pair<std::string, TypeIdSummary>>;
1002
1003/// The following data structures summarize type metadata information.
1004/// For type metadata overview see https://llvm.org/docs/TypeMetadata.html.
1005/// Each type metadata includes both the type identifier and the offset of
1006/// the address point of the type (the address held by objects of that type
1007/// which may not be the beginning of the virtual table). Vtable definitions
1008/// are decorated with type metadata for the types they are compatible with.
1009///
1010/// Holds information about vtable definitions decorated with type metadata:
1011/// the vtable definition value and its address point offset in a type
1012/// identifier metadata it is decorated (compatible) with.
1013struct TypeIdOffsetVtableInfo {
1014 TypeIdOffsetVtableInfo(uint64_t Offset, ValueInfo VI)
1015 : AddressPointOffset(Offset), VTableVI(VI) {}
1016
1017 uint64_t AddressPointOffset;
1018 ValueInfo VTableVI;
1019};
1020/// List of vtable definitions decorated by a particular type identifier,
1021/// and their corresponding offsets in that type identifier's metadata.
1022/// Note that each type identifier may be compatible with multiple vtables, due
1023/// to inheritance, which is why this is a vector.
1024using TypeIdCompatibleVtableInfo = std::vector<TypeIdOffsetVtableInfo>;
1025
1026/// Class to hold module path string table and global value map,
1027/// and encapsulate methods for operating on them.
1028class ModuleSummaryIndex {
1029private:
1030 /// Map from value name to list of summary instances for values of that
1031 /// name (may be duplicates in the COMDAT case, e.g.).
1032 GlobalValueSummaryMapTy GlobalValueMap;
1033
1034 /// Holds strings for combined index, mapping to the corresponding module ID.
1035 ModulePathStringTableTy ModulePathStringTable;
1036
1037 /// Mapping from type identifier GUIDs to type identifier and its summary
1038 /// information. Produced by thin link.
1039 TypeIdSummaryMapTy TypeIdMap;
1040
1041 /// Mapping from type identifier to information about vtables decorated
1042 /// with that type identifier's metadata. Produced by per module summary
1043 /// analysis and consumed by thin link. For more information, see description
1044 /// above where TypeIdCompatibleVtableInfo is defined.
1045 std::map<std::string, TypeIdCompatibleVtableInfo, std::less<>>
1046 TypeIdCompatibleVtableMap;
1047
1048 /// Mapping from original ID to GUID. If original ID can map to multiple
1049 /// GUIDs, it will be mapped to 0.
1050 std::map<GlobalValue::GUID, GlobalValue::GUID> OidGuidMap;
1051
1052 /// Indicates that summary-based GlobalValue GC has run, and values with
1053 /// GVFlags::Live==false are really dead. Otherwise, all values must be
1054 /// considered live.
1055 bool WithGlobalValueDeadStripping = false;
1056
1057 /// Indicates that summary-based attribute propagation has run and
1058 /// GVarFlags::MaybeReadonly / GVarFlags::MaybeWriteonly are really
1059 /// read/write only.
1060 bool WithAttributePropagation = false;
1061
1062 /// Indicates that summary-based DSOLocal propagation has run and the flag in
1063 /// every summary of a GV is synchronized.
1064 bool WithDSOLocalPropagation = false;
1065
1066 /// Indicates that summary-based synthetic entry count propagation has run
1067 bool HasSyntheticEntryCounts = false;
1068
1069 /// Indicates that distributed backend should skip compilation of the
1070 /// module. Flag is suppose to be set by distributed ThinLTO indexing
1071 /// when it detected that the module is not needed during the final
1072 /// linking. As result distributed backend should just output a minimal
1073 /// valid object file.
1074 bool SkipModuleByDistributedBackend = false;
1075
1076 /// If true then we're performing analysis of IR module, or parsing along with
1077 /// the IR from assembly. The value of 'false' means we're reading summary
1078 /// from BC or YAML source. Affects the type of value stored in NameOrGV
1079 /// union.
1080 bool HaveGVs;
1081
1082 // True if the index was created for a module compiled with -fsplit-lto-unit.
1083 bool EnableSplitLTOUnit;
1084
1085 // True if some of the modules were compiled with -fsplit-lto-unit and
1086 // some were not. Set when the combined index is created during the thin link.
1087 bool PartiallySplitLTOUnits = false;
1088
1089 /// True if some of the FunctionSummary contains a ParamAccess.
1090 bool HasParamAccess = false;
1091
1092 std::set<std::string> CfiFunctionDefs;
1093 std::set<std::string> CfiFunctionDecls;
1094
1095 // Used in cases where we want to record the name of a global, but
1096 // don't have the string owned elsewhere (e.g. the Strtab on a module).
1097 StringSaver Saver;
1098 BumpPtrAllocator Alloc;
1099
1100 // The total number of basic blocks in the module in the per-module summary or
1101 // the total number of basic blocks in the LTO unit in the combined index.
1102 uint64_t BlockCount;
1103
1104 // YAML I/O support.
1105 friend yaml::MappingTraits<ModuleSummaryIndex>;
1106
1107 GlobalValueSummaryMapTy::value_type *
1108 getOrInsertValuePtr(GlobalValue::GUID GUID) {
1109 return &*GlobalValueMap.emplace(GUID, GlobalValueSummaryInfo(HaveGVs))
1110 .first;
1111 }
1112
1113public:
1114 // See HaveGVs variable comment.
1115 ModuleSummaryIndex(bool HaveGVs, bool EnableSplitLTOUnit = false)
1116 : HaveGVs(HaveGVs), EnableSplitLTOUnit(EnableSplitLTOUnit), Saver(Alloc),
1117 BlockCount(0) {}
1118
1119 // Current version for the module summary in bitcode files.
1120 // The BitcodeSummaryVersion should be bumped whenever we introduce changes
1121 // in the way some record are interpreted, like flags for instance.
1122 // Note that incrementing this may require changes in both BitcodeReader.cpp
1123 // and BitcodeWriter.cpp.
1124 static constexpr uint64_t BitcodeSummaryVersion = 9;
1125
1126 // Regular LTO module name for ASM writer
1127 static constexpr const char *getRegularLTOModuleName() {
1128 return "[Regular LTO]";
1129 }
1130
1131 bool haveGVs() const { return HaveGVs; }
1132
1133 uint64_t getFlags() const;
1134 void setFlags(uint64_t Flags);
1135
1136 uint64_t getBlockCount() const { return BlockCount; }
1137 void addBlockCount(uint64_t C) { BlockCount += C; }
1138 void setBlockCount(uint64_t C) { BlockCount = C; }
1139
1140 gvsummary_iterator begin() { return GlobalValueMap.begin(); }
1141 const_gvsummary_iterator begin() const { return GlobalValueMap.begin(); }
1142 gvsummary_iterator end() { return GlobalValueMap.end(); }
1143 const_gvsummary_iterator end() const { return GlobalValueMap.end(); }
1144 size_t size() const { return GlobalValueMap.size(); }
1145
1146 /// Convenience function for doing a DFS on a ValueInfo. Marks the function in
1147 /// the FunctionHasParent map.
1148 static void discoverNodes(ValueInfo V,
1149 std::map<ValueInfo, bool> &FunctionHasParent) {
1150 if (!V.getSummaryList().size())
1151 return; // skip external functions that don't have summaries
1152
1153 // Mark discovered if we haven't yet
1154 auto S = FunctionHasParent.emplace(V, false);
1155
1156 // Stop if we've already discovered this node
1157 if (!S.second)
1158 return;
1159
1160 FunctionSummary *F =
1161 dyn_cast<FunctionSummary>(V.getSummaryList().front().get());
1162 assert(F != nullptr && "Expected FunctionSummary node")((void)0);
1163
1164 for (auto &C : F->calls()) {
1165 // Insert node if necessary
1166 auto S = FunctionHasParent.emplace(C.first, true);
1167
1168 // Skip nodes that we're sure have parents
1169 if (!S.second && S.first->second)
1170 continue;
1171
1172 if (S.second)
1173 discoverNodes(C.first, FunctionHasParent);
1174 else
1175 S.first->second = true;
1176 }
1177 }
1178
1179 // Calculate the callgraph root
1180 FunctionSummary calculateCallGraphRoot() {
1181 // Functions that have a parent will be marked in FunctionHasParent pair.
1182 // Once we've marked all functions, the functions in the map that are false
1183 // have no parent (so they're the roots)
1184 std::map<ValueInfo, bool> FunctionHasParent;
1185
1186 for (auto &S : *this) {
1187 // Skip external functions
1188 if (!S.second.SummaryList.size() ||
1189 !isa<FunctionSummary>(S.second.SummaryList.front().get()))
1190 continue;
1191 discoverNodes(ValueInfo(HaveGVs, &S), FunctionHasParent);
1192 }
1193
1194 std::vector<FunctionSummary::EdgeTy> Edges;
1195 // create edges to all roots in the Index
1196 for (auto &P : FunctionHasParent) {
1197 if (P.second)
1198 continue; // skip over non-root nodes
1199 Edges.push_back(std::make_pair(P.first, CalleeInfo{}));
1200 }
1201 if (Edges.empty()) {
1202 // Failed to find root - return an empty node
1203 return FunctionSummary::makeDummyFunctionSummary({});
1204 }
1205 auto CallGraphRoot = FunctionSummary::makeDummyFunctionSummary(Edges);
1206 return CallGraphRoot;
1207 }
1208
1209 bool withGlobalValueDeadStripping() const {
1210 return WithGlobalValueDeadStripping;
1211 }
1212 void setWithGlobalValueDeadStripping() {
1213 WithGlobalValueDeadStripping = true;
1214 }
1215
1216 bool withAttributePropagation() const { return WithAttributePropagation; }
1217 void setWithAttributePropagation() {
1218 WithAttributePropagation = true;
1219 }
1220
1221 bool withDSOLocalPropagation() const { return WithDSOLocalPropagation; }
1222 void setWithDSOLocalPropagation() { WithDSOLocalPropagation = true; }
1223
1224 bool isReadOnly(const GlobalVarSummary *GVS) const {
1225 return WithAttributePropagation && GVS->maybeReadOnly();
1226 }
1227 bool isWriteOnly(const GlobalVarSummary *GVS) const {
1228 return WithAttributePropagation && GVS->maybeWriteOnly();
1229 }
1230
1231 bool hasSyntheticEntryCounts() const { return HasSyntheticEntryCounts; }
1232 void setHasSyntheticEntryCounts() { HasSyntheticEntryCounts = true; }
1233
1234 bool skipModuleByDistributedBackend() const {
1235 return SkipModuleByDistributedBackend;
1236 }
1237 void setSkipModuleByDistributedBackend() {
1238 SkipModuleByDistributedBackend = true;
1239 }
1240
1241 bool enableSplitLTOUnit() const { return EnableSplitLTOUnit; }
1242 void setEnableSplitLTOUnit() { EnableSplitLTOUnit = true; }
1243
1244 bool partiallySplitLTOUnits() const { return PartiallySplitLTOUnits; }
1245 void setPartiallySplitLTOUnits() { PartiallySplitLTOUnits = true; }
1246
1247 bool hasParamAccess() const { return HasParamAccess; }
1248
1249 bool isGlobalValueLive(const GlobalValueSummary *GVS) const {
1250 return !WithGlobalValueDeadStripping || GVS->isLive();
1251 }
1252 bool isGUIDLive(GlobalValue::GUID GUID) const;
1253
1254 /// Return a ValueInfo for the index value_type (convenient when iterating
1255 /// index).
1256 ValueInfo getValueInfo(const GlobalValueSummaryMapTy::value_type &R) const {
1257 return ValueInfo(HaveGVs, &R);
1258 }
1259
1260 /// Return a ValueInfo for GUID if it exists, otherwise return ValueInfo().
1261 ValueInfo getValueInfo(GlobalValue::GUID GUID) const {
1262 auto I = GlobalValueMap.find(GUID);
1263 return ValueInfo(HaveGVs, I == GlobalValueMap.end() ? nullptr : &*I);
1264 }
1265
1266 /// Return a ValueInfo for \p GUID.
1267 ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID) {
1268 return ValueInfo(HaveGVs, getOrInsertValuePtr(GUID));
1269 }
1270
1271 // Save a string in the Index. Use before passing Name to
1272 // getOrInsertValueInfo when the string isn't owned elsewhere (e.g. on the
1273 // module's Strtab).
1274 StringRef saveString(StringRef String) { return Saver.save(String); }
1275
1276 /// Return a ValueInfo for \p GUID setting value \p Name.
1277 ValueInfo getOrInsertValueInfo(GlobalValue::GUID GUID, StringRef Name) {
1278 assert(!HaveGVs)((void)0);
1279 auto VP = getOrInsertValuePtr(GUID);
1280 VP->second.U.Name = Name;
1281 return ValueInfo(HaveGVs, VP);
1282 }
1283
1284 /// Return a ValueInfo for \p GV and mark it as belonging to GV.
1285 ValueInfo getOrInsertValueInfo(const GlobalValue *GV) {
1286 assert(HaveGVs)((void)0);
1287 auto VP = getOrInsertValuePtr(GV->getGUID());
1288 VP->second.U.GV = GV;
1289 return ValueInfo(HaveGVs, VP);
1290 }
1291
1292 /// Return the GUID for \p OriginalId in the OidGuidMap.
1293 GlobalValue::GUID getGUIDFromOriginalID(GlobalValue::GUID OriginalID) const {
1294 const auto I = OidGuidMap.find(OriginalID);
1295 return I == OidGuidMap.end() ? 0 : I->second;
1296 }
1297
1298 std::set<std::string> &cfiFunctionDefs() { return CfiFunctionDefs; }
1299 const std::set<std::string> &cfiFunctionDefs() const { return CfiFunctionDefs; }
1300
1301 std::set<std::string> &cfiFunctionDecls() { return CfiFunctionDecls; }
1302 const std::set<std::string> &cfiFunctionDecls() const { return CfiFunctionDecls; }
1303
1304 /// Add a global value summary for a value.
1305 void addGlobalValueSummary(const GlobalValue &GV,
1306 std::unique_ptr<GlobalValueSummary> Summary) {
1307 addGlobalValueSummary(getOrInsertValueInfo(&GV), std::move(Summary));
1308 }
1309
1310 /// Add a global value summary for a value of the given name.
1311 void addGlobalValueSummary(StringRef ValueName,
1312 std::unique_ptr<GlobalValueSummary> Summary) {
1313 addGlobalValueSummary(getOrInsertValueInfo(GlobalValue::getGUID(ValueName)),
1314 std::move(Summary));
1315 }
1316
1317 /// Add a global value summary for the given ValueInfo.
1318 void addGlobalValueSummary(ValueInfo VI,
1319 std::unique_ptr<GlobalValueSummary> Summary) {
1320 if (const FunctionSummary *FS = dyn_cast<FunctionSummary>(Summary.get()))
1321 HasParamAccess |= !FS->paramAccesses().empty();
1322 addOriginalName(VI.getGUID(), Summary->getOriginalName());
1323 // Here we have a notionally const VI, but the value it points to is owned
1324 // by the non-const *this.
1325 const_cast<GlobalValueSummaryMapTy::value_type *>(VI.getRef())
1326 ->second.SummaryList.push_back(std::move(Summary));
1327 }
1328
1329 /// Add an original name for the value of the given GUID.
1330 void addOriginalName(GlobalValue::GUID ValueGUID,
1331 GlobalValue::GUID OrigGUID) {
1332 if (OrigGUID == 0 || ValueGUID == OrigGUID)
1333 return;
1334 if (OidGuidMap.count(OrigGUID) && OidGuidMap[OrigGUID] != ValueGUID)
1335 OidGuidMap[OrigGUID] = 0;
1336 else
1337 OidGuidMap[OrigGUID] = ValueGUID;
1338 }
1339
1340 /// Find the summary for ValueInfo \p VI in module \p ModuleId, or nullptr if
1341 /// not found.
1342 GlobalValueSummary *findSummaryInModule(ValueInfo VI, StringRef ModuleId) const {
1343 auto SummaryList = VI.getSummaryList();
1344 auto Summary =
1345 llvm::find_if(SummaryList,
1346 [&](const std::unique_ptr<GlobalValueSummary> &Summary) {
1347 return Summary->modulePath() == ModuleId;
1348 });
1349 if (Summary == SummaryList.end())
1350 return nullptr;
1351 return Summary->get();
1352 }
1353
1354 /// Find the summary for global \p GUID in module \p ModuleId, or nullptr if
1355 /// not found.
1356 GlobalValueSummary *findSummaryInModule(GlobalValue::GUID ValueGUID,
1357 StringRef ModuleId) const {
1358 auto CalleeInfo = getValueInfo(ValueGUID);
1359 if (!CalleeInfo)
1360 return nullptr; // This function does not have a summary
1361 return findSummaryInModule(CalleeInfo, ModuleId);
1362 }
1363
1364 /// Returns the first GlobalValueSummary for \p GV, asserting that there
1365 /// is only one if \p PerModuleIndex.
1366 GlobalValueSummary *getGlobalValueSummary(const GlobalValue &GV,
1367 bool PerModuleIndex = true) const {
1368 assert(GV.hasName() && "Can't get GlobalValueSummary for GV with no name")((void)0);
1369 return getGlobalValueSummary(GV.getGUID(), PerModuleIndex);
1370 }
1371
1372 /// Returns the first GlobalValueSummary for \p ValueGUID, asserting that
1373 /// there
1374 /// is only one if \p PerModuleIndex.
1375 GlobalValueSummary *getGlobalValueSummary(GlobalValue::GUID ValueGUID,
1376 bool PerModuleIndex = true) const;
1377
1378 /// Table of modules, containing module hash and id.
1379 const StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() const {
1380 return ModulePathStringTable;
1381 }
1382
1383 /// Table of modules, containing hash and id.
1384 StringMap<std::pair<uint64_t, ModuleHash>> &modulePaths() {
1385 return ModulePathStringTable;
1386 }
1387
1388 /// Get the module ID recorded for the given module path.
1389 uint64_t getModuleId(const StringRef ModPath) const {
1390 return ModulePathStringTable.lookup(ModPath).first;
1391 }
1392
1393 /// Get the module SHA1 hash recorded for the given module path.
1394 const ModuleHash &getModuleHash(const StringRef ModPath) const {
1395 auto It = ModulePathStringTable.find(ModPath);
1396 assert(It != ModulePathStringTable.end() && "Module not registered")((void)0);
1397 return It->second.second;
1398 }
1399
1400 /// Convenience method for creating a promoted global name
1401 /// for the given value name of a local, and its original module's ID.
1402 static std::string getGlobalNameForLocal(StringRef Name, ModuleHash ModHash) {
1403 SmallString<256> NewName(Name);
1404 NewName += ".llvm.";
1405 NewName += utostr((uint64_t(ModHash[0]) << 32) |
1406 ModHash[1]); // Take the first 64 bits
1407 return std::string(NewName.str());
1408 }
1409
1410 /// Helper to obtain the unpromoted name for a global value (or the original
1411 /// name if not promoted). Split off the rightmost ".llvm.${hash}" suffix,
1412 /// because it is possible in certain clients (not clang at the moment) for
1413 /// two rounds of ThinLTO optimization and therefore promotion to occur.
1414 static StringRef getOriginalNameBeforePromote(StringRef Name) {
1415 std::pair<StringRef, StringRef> Pair = Name.rsplit(".llvm.");
1416 return Pair.first;
1417 }
1418
1419 typedef ModulePathStringTableTy::value_type ModuleInfo;
1420
1421 /// Add a new module with the given \p Hash, mapped to the given \p
1422 /// ModID, and return a reference to the module.
1423 ModuleInfo *addModule(StringRef ModPath, uint64_t ModId,
1424 ModuleHash Hash = ModuleHash{{0}}) {
1425 return &*ModulePathStringTable.insert({ModPath, {ModId, Hash}}).first;
1426 }
1427
1428 /// Return module entry for module with the given \p ModPath.
1429 ModuleInfo *getModule(StringRef ModPath) {
1430 auto It = ModulePathStringTable.find(ModPath);
1431 assert(It != ModulePathStringTable.end() && "Module not registered")((void)0);
1432 return &*It;
1433 }
1434
1435 /// Check if the given Module has any functions available for exporting
1436 /// in the index. We consider any module present in the ModulePathStringTable
1437 /// to have exported functions.
1438 bool hasExportedFunctions(const Module &M) const {
1439 return ModulePathStringTable.count(M.getModuleIdentifier());
1440 }
1441
1442 const TypeIdSummaryMapTy &typeIds() const { return TypeIdMap; }
1443
1444 /// Return an existing or new TypeIdSummary entry for \p TypeId.
1445 /// This accessor can mutate the map and therefore should not be used in
1446 /// the ThinLTO backends.
1447 TypeIdSummary &getOrInsertTypeIdSummary(StringRef TypeId) {
1448 auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1449 for (auto It = TidIter.first; It != TidIter.second; ++It)
1450 if (It->second.first == TypeId)
1451 return It->second.second;
1452 auto It = TypeIdMap.insert(
1453 {GlobalValue::getGUID(TypeId), {std::string(TypeId), TypeIdSummary()}});
1454 return It->second.second;
1455 }
1456
1457 /// This returns either a pointer to the type id summary (if present in the
1458 /// summary map) or null (if not present). This may be used when importing.
1459 const TypeIdSummary *getTypeIdSummary(StringRef TypeId) const {
1460 auto TidIter = TypeIdMap.equal_range(GlobalValue::getGUID(TypeId));
1461 for (auto It = TidIter.first; It != TidIter.second; ++It)
1462 if (It->second.first == TypeId)
1463 return &It->second.second;
1464 return nullptr;
1465 }
1466
1467 TypeIdSummary *getTypeIdSummary(StringRef TypeId) {
1468 return const_cast<TypeIdSummary *>(
1469 static_cast<const ModuleSummaryIndex *>(this)->getTypeIdSummary(
1470 TypeId));
1471 }
1472
1473 const auto &typeIdCompatibleVtableMap() const {
1474 return TypeIdCompatibleVtableMap;
1475 }
1476
1477 /// Return an existing or new TypeIdCompatibleVtableMap entry for \p TypeId.
1478 /// This accessor can mutate the map and therefore should not be used in
1479 /// the ThinLTO backends.
1480 TypeIdCompatibleVtableInfo &
1481 getOrInsertTypeIdCompatibleVtableSummary(StringRef TypeId) {
1482 return TypeIdCompatibleVtableMap[std::string(TypeId)];
1483 }
1484
1485 /// For the given \p TypeId, this returns the TypeIdCompatibleVtableMap
1486 /// entry if present in the summary map. This may be used when importing.
1487 Optional<TypeIdCompatibleVtableInfo>
1488 getTypeIdCompatibleVtableSummary(StringRef TypeId) const {
1489 auto I = TypeIdCompatibleVtableMap.find(TypeId);
1490 if (I == TypeIdCompatibleVtableMap.end())
1491 return None;
1492 return I->second;
1493 }
1494
1495 /// Collect for the given module the list of functions it defines
1496 /// (GUID -> Summary).
1497 void collectDefinedFunctionsForModule(StringRef ModulePath,
1498 GVSummaryMapTy &GVSummaryMap) const;
1499
1500 /// Collect for each module the list of Summaries it defines (GUID ->
1501 /// Summary).
1502 template <class Map>
1503 void
1504 collectDefinedGVSummariesPerModule(Map &ModuleToDefinedGVSummaries) const {
1505 for (auto &GlobalList : *this) {
1506 auto GUID = GlobalList.first;
1507 for (auto &Summary : GlobalList.second.SummaryList) {
1508 ModuleToDefinedGVSummaries[Summary->modulePath()][GUID] = Summary.get();
1509 }
1510 }
1511 }
1512
1513 /// Print to an output stream.
1514 void print(raw_ostream &OS, bool IsForDebug = false) const;
1515
1516 /// Dump to stderr (for debugging).
1517 void dump() const;
1518
1519 /// Export summary to dot file for GraphViz.
1520 void
1521 exportToDot(raw_ostream &OS,
1522 const DenseSet<GlobalValue::GUID> &GUIDPreservedSymbols) const;
1523
1524 /// Print out strongly connected components for debugging.
1525 void dumpSCCs(raw_ostream &OS);
1526
1527 /// Do the access attribute and DSOLocal propagation in combined index.
1528 void propagateAttributes(const DenseSet<GlobalValue::GUID> &PreservedSymbols);
1529
1530 /// Checks if we can import global variable from another module.
1531 bool canImportGlobalVar(GlobalValueSummary *S, bool AnalyzeRefs) const;
1532};
1533
1534/// GraphTraits definition to build SCC for the index
1535template <> struct GraphTraits<ValueInfo> {
1536 typedef ValueInfo NodeRef;
1537 using EdgeRef = FunctionSummary::EdgeTy &;
1538
1539 static NodeRef valueInfoFromEdge(FunctionSummary::EdgeTy &P) {
1540 return P.first;
1541 }
1542 using ChildIteratorType =
1543 mapped_iterator<std::vector<FunctionSummary::EdgeTy>::iterator,
1544 decltype(&valueInfoFromEdge)>;
1545
1546 using ChildEdgeIteratorType = std::vector<FunctionSummary::EdgeTy>::iterator;
1547
1548 static NodeRef getEntryNode(ValueInfo V) { return V; }
1549
1550 static ChildIteratorType child_begin(NodeRef N) {
1551 if (!N.getSummaryList().size()) // handle external function
1552 return ChildIteratorType(
1553 FunctionSummary::ExternalNode.CallGraphEdgeList.begin(),
1554 &valueInfoFromEdge);
1555 FunctionSummary *F =
1556 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1557 return ChildIteratorType(F->CallGraphEdgeList.begin(), &valueInfoFromEdge);
1558 }
1559
1560 static ChildIteratorType child_end(NodeRef N) {
1561 if (!N.getSummaryList().size()) // handle external function
1562 return ChildIteratorType(
1563 FunctionSummary::ExternalNode.CallGraphEdgeList.end(),
1564 &valueInfoFromEdge);
1565 FunctionSummary *F =
1566 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1567 return ChildIteratorType(F->CallGraphEdgeList.end(), &valueInfoFromEdge);
1568 }
1569
1570 static ChildEdgeIteratorType child_edge_begin(NodeRef N) {
1571 if (!N.getSummaryList().size()) // handle external function
1572 return FunctionSummary::ExternalNode.CallGraphEdgeList.begin();
1573
1574 FunctionSummary *F =
1575 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1576 return F->CallGraphEdgeList.begin();
1577 }
1578
1579 static ChildEdgeIteratorType child_edge_end(NodeRef N) {
1580 if (!N.getSummaryList().size()) // handle external function
1581 return FunctionSummary::ExternalNode.CallGraphEdgeList.end();
1582
1583 FunctionSummary *F =
1584 cast<FunctionSummary>(N.getSummaryList().front()->getBaseObject());
1585 return F->CallGraphEdgeList.end();
1586 }
1587
1588 static NodeRef edge_dest(EdgeRef E) { return E.first; }
1589};
1590
1591template <>
1592struct GraphTraits<ModuleSummaryIndex *> : public GraphTraits<ValueInfo> {
1593 static NodeRef getEntryNode(ModuleSummaryIndex *I) {
1594 std::unique_ptr<GlobalValueSummary> Root =
1595 std::make_unique<FunctionSummary>(I->calculateCallGraphRoot());
1596 GlobalValueSummaryInfo G(I->haveGVs());
1597 G.SummaryList.push_back(std::move(Root));
1598 static auto P =
1599 GlobalValueSummaryMapTy::value_type(GlobalValue::GUID(0), std::move(G));
1600 return ValueInfo(I->haveGVs(), &P);
1601 }
1602};
1603} // end namespace llvm
1604
1605#endif // LLVM_IR_MODULESUMMARYINDEX_H
←

/usr/src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/Support/ScaledNumber.h

1//===- llvm/Support/ScaledNumber.h - Support for scaled numbers -*- C++ -*-===//
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 contains functions (and a class) useful for working with scaled
10// numbers -- in particular, pairs of integers where one represents digits and
11// another represents a scale. The functions are helpers and live in the
12// namespace ScaledNumbers. The class ScaledNumber is useful for modelling
13// certain cost metrics that need simple, integer-like semantics that are easy
14// to reason about.
15//
16// These might remind you of soft-floats. If you want one of those, you're in
17// the wrong place. Look at include/llvm/ADT/APFloat.h instead.
18//
19//===----------------------------------------------------------------------===//
20
21#ifndef LLVM_SUPPORT_SCALEDNUMBER_H
22#define LLVM_SUPPORT_SCALEDNUMBER_H
23
24#include "llvm/Support/MathExtras.h"
25#include <algorithm>
26#include <cstdint>
27#include <limits>
28#include <string>
29#include <tuple>
30#include <utility>
31
32namespace llvm {
33namespace ScaledNumbers {
34
35/// Maximum scale; same as APFloat for easy debug printing.
36const int32_t MaxScale = 16383;
37
38/// Maximum scale; same as APFloat for easy debug printing.
39const int32_t MinScale = -16382;
40
41/// Get the width of a number.
42template <class DigitsT> inline int getWidth() { return sizeof(DigitsT) * 8; }
43
44/// Conditionally round up a scaled number.
45///
46/// Given \c Digits and \c Scale, round up iff \c ShouldRound is \c true.
47/// Always returns \c Scale unless there's an overflow, in which case it
48/// returns \c 1+Scale.
49///
50/// \pre adding 1 to \c Scale will not overflow INT16_MAX.
51template <class DigitsT>
52inline std::pair<DigitsT, int16_t> getRounded(DigitsT Digits, int16_t Scale,
53 bool ShouldRound) {
54 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
55
56 if (ShouldRound)
57 if (!++Digits)
58 // Overflow.
59 return std::make_pair(DigitsT(1) << (getWidth<DigitsT>() - 1), Scale + 1);
60 return std::make_pair(Digits, Scale);
61}
62
63/// Convenience helper for 32-bit rounding.
64inline std::pair<uint32_t, int16_t> getRounded32(uint32_t Digits, int16_t Scale,
65 bool ShouldRound) {
66 return getRounded(Digits, Scale, ShouldRound);
67}
68
69/// Convenience helper for 64-bit rounding.
70inline std::pair<uint64_t, int16_t> getRounded64(uint64_t Digits, int16_t Scale,
71 bool ShouldRound) {
72 return getRounded(Digits, Scale, ShouldRound);
73}
74
75/// Adjust a 64-bit scaled number down to the appropriate width.
76///
77/// \pre Adding 64 to \c Scale will not overflow INT16_MAX.
78template <class DigitsT>
79inline std::pair<DigitsT, int16_t> getAdjusted(uint64_t Digits,
80 int16_t Scale = 0) {
81 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
82
83 const int Width = getWidth<DigitsT>();
84 if (Width == 64 || Digits <= std::numeric_limits<DigitsT>::max())
85 return std::make_pair(Digits, Scale);
86
87 // Shift right and round.
88 int Shift = 64 - Width - countLeadingZeros(Digits);
89 return getRounded<DigitsT>(Digits >> Shift, Scale + Shift,
90 Digits & (UINT64_C(1)1ULL << (Shift - 1)));
91}
92
93/// Convenience helper for adjusting to 32 bits.
94inline std::pair<uint32_t, int16_t> getAdjusted32(uint64_t Digits,
95 int16_t Scale = 0) {
96 return getAdjusted<uint32_t>(Digits, Scale);
97}
98
99/// Convenience helper for adjusting to 64 bits.
100inline std::pair<uint64_t, int16_t> getAdjusted64(uint64_t Digits,
101 int16_t Scale = 0) {
102 return getAdjusted<uint64_t>(Digits, Scale);
103}
104
105/// Multiply two 64-bit integers to create a 64-bit scaled number.
106///
107/// Implemented with four 64-bit integer multiplies.
108std::pair<uint64_t, int16_t> multiply64(uint64_t LHS, uint64_t RHS);
109
110/// Multiply two 32-bit integers to create a 32-bit scaled number.
111///
112/// Implemented with one 64-bit integer multiply.
113template <class DigitsT>
114inline std::pair<DigitsT, int16_t> getProduct(DigitsT LHS, DigitsT RHS) {
115 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
116
117 if (getWidth<DigitsT>() <= 32 || (LHS <= UINT32_MAX0xffffffffU && RHS <= UINT32_MAX0xffffffffU))
118 return getAdjusted<DigitsT>(uint64_t(LHS) * RHS);
119
120 return multiply64(LHS, RHS);
121}
122
123/// Convenience helper for 32-bit product.
124inline std::pair<uint32_t, int16_t> getProduct32(uint32_t LHS, uint32_t RHS) {
125 return getProduct(LHS, RHS);
126}
127
128/// Convenience helper for 64-bit product.
129inline std::pair<uint64_t, int16_t> getProduct64(uint64_t LHS, uint64_t RHS) {
130 return getProduct(LHS, RHS);
131}
132
133/// Divide two 64-bit integers to create a 64-bit scaled number.
134///
135/// Implemented with long division.
136///
137/// \pre \c Dividend and \c Divisor are non-zero.
138std::pair<uint64_t, int16_t> divide64(uint64_t Dividend, uint64_t Divisor);
139
140/// Divide two 32-bit integers to create a 32-bit scaled number.
141///
142/// Implemented with one 64-bit integer divide/remainder pair.
143///
144/// \pre \c Dividend and \c Divisor are non-zero.
145std::pair<uint32_t, int16_t> divide32(uint32_t Dividend, uint32_t Divisor);
146
147/// Divide two 32-bit numbers to create a 32-bit scaled number.
148///
149/// Implemented with one 64-bit integer divide/remainder pair.
150///
151/// Returns \c (DigitsT_MAX, MaxScale) for divide-by-zero (0 for 0/0).
152template <class DigitsT>
153std::pair<DigitsT, int16_t> getQuotient(DigitsT Dividend, DigitsT Divisor) {
154 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
155 static_assert(sizeof(DigitsT) == 4 || sizeof(DigitsT) == 8,
156 "expected 32-bit or 64-bit digits");
157
158 // Check for zero.
159 if (!Dividend)
160 return std::make_pair(0, 0);
161 if (!Divisor)
162 return std::make_pair(std::numeric_limits<DigitsT>::max(), MaxScale);
163
164 if (getWidth<DigitsT>() == 64)
165 return divide64(Dividend, Divisor);
166 return divide32(Dividend, Divisor);
167}
168
169/// Convenience helper for 32-bit quotient.
170inline std::pair<uint32_t, int16_t> getQuotient32(uint32_t Dividend,
171 uint32_t Divisor) {
172 return getQuotient(Dividend, Divisor);
173}
174
175/// Convenience helper for 64-bit quotient.
176inline std::pair<uint64_t, int16_t> getQuotient64(uint64_t Dividend,
177 uint64_t Divisor) {
178 return getQuotient(Dividend, Divisor);
179}
180
181/// Implementation of getLg() and friends.
182///
183/// Returns the rounded lg of \c Digits*2^Scale and an int specifying whether
184/// this was rounded up (1), down (-1), or exact (0).
185///
186/// Returns \c INT32_MIN when \c Digits is zero.
187template <class DigitsT>
188inline std::pair<int32_t, int> getLgImpl(DigitsT Digits, int16_t Scale) {
189 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
190
191 if (!Digits)
192 return std::make_pair(INT32_MIN(-0x7fffffff - 1), 0);
193
194 // Get the floor of the lg of Digits.
195 int32_t LocalFloor = sizeof(Digits) * 8 - countLeadingZeros(Digits) - 1;
196
197 // Get the actual floor.
198 int32_t Floor = Scale + LocalFloor;
199 if (Digits == UINT64_C(1)1ULL << LocalFloor)
200 return std::make_pair(Floor, 0);
201
202 // Round based on the next digit.
203 assert(LocalFloor >= 1)((void)0);
204 bool Round = Digits & UINT64_C(1)1ULL << (LocalFloor - 1);
205 return std::make_pair(Floor + Round, Round ? 1 : -1);
206}
207
208/// Get the lg (rounded) of a scaled number.
209///
210/// Get the lg of \c Digits*2^Scale.
211///
212/// Returns \c INT32_MIN when \c Digits is zero.
213template <class DigitsT> int32_t getLg(DigitsT Digits, int16_t Scale) {
214 return getLgImpl(Digits, Scale).first;
215}
216
217/// Get the lg floor of a scaled number.
218///
219/// Get the floor of the lg of \c Digits*2^Scale.
220///
221/// Returns \c INT32_MIN when \c Digits is zero.
222template <class DigitsT> int32_t getLgFloor(DigitsT Digits, int16_t Scale) {
223 auto Lg = getLgImpl(Digits, Scale);
224 return Lg.first - (Lg.second > 0);
225}
226
227/// Get the lg ceiling of a scaled number.
228///
229/// Get the ceiling of the lg of \c Digits*2^Scale.
230///
231/// Returns \c INT32_MIN when \c Digits is zero.
232template <class DigitsT> int32_t getLgCeiling(DigitsT Digits, int16_t Scale) {
233 auto Lg = getLgImpl(Digits, Scale);
234 return Lg.first + (Lg.second < 0);
235}
236
237/// Implementation for comparing scaled numbers.
238///
239/// Compare two 64-bit numbers with different scales. Given that the scale of
240/// \c L is higher than that of \c R by \c ScaleDiff, compare them. Return -1,
241/// 1, and 0 for less than, greater than, and equal, respectively.
242///
243/// \pre 0 <= ScaleDiff < 64.
244int compareImpl(uint64_t L, uint64_t R, int ScaleDiff);
245
246/// Compare two scaled numbers.
247///
248/// Compare two scaled numbers. Returns 0 for equal, -1 for less than, and 1
249/// for greater than.
250template <class DigitsT>
251int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale) {
252 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
253
254 // Check for zero.
255 if (!LDigits)
256 return RDigits ? -1 : 0;
257 if (!RDigits)
258 return 1;
259
260 // Check for the scale. Use getLgFloor to be sure that the scale difference
261 // is always lower than 64.
262 int32_t lgL = getLgFloor(LDigits, LScale), lgR = getLgFloor(RDigits, RScale);
263 if (lgL != lgR)
264 return lgL < lgR ? -1 : 1;
265
266 // Compare digits.
267 if (LScale < RScale)
268 return compareImpl(LDigits, RDigits, RScale - LScale);
269
270 return -compareImpl(RDigits, LDigits, LScale - RScale);
271}
272
273/// Match scales of two numbers.
274///
275/// Given two scaled numbers, match up their scales. Change the digits and
276/// scales in place. Shift the digits as necessary to form equivalent numbers,
277/// losing precision only when necessary.
278///
279/// If the output value of \c LDigits (\c RDigits) is \c 0, the output value of
280/// \c LScale (\c RScale) is unspecified.
281///
282/// As a convenience, returns the matching scale. If the output value of one
283/// number is zero, returns the scale of the other. If both are zero, which
284/// scale is returned is unspecified.
285template <class DigitsT>
286int16_t matchScales(DigitsT &LDigits, int16_t &LScale, DigitsT &RDigits,
287 int16_t &RScale) {
288 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
289
290 if (LScale < RScale)
291 // Swap arguments.
292 return matchScales(RDigits, RScale, LDigits, LScale);
293 if (!LDigits)
294 return RScale;
295 if (!RDigits || LScale == RScale)
296 return LScale;
297
298 // Now LScale > RScale. Get the difference.
299 int32_t ScaleDiff = int32_t(LScale) - RScale;
300 if (ScaleDiff >= 2 * getWidth<DigitsT>()) {
301 // Don't bother shifting. RDigits will get zero-ed out anyway.
302 RDigits = 0;
303 return LScale;
304 }
305
306 // Shift LDigits left as much as possible, then shift RDigits right.
307 int32_t ShiftL = std::min<int32_t>(countLeadingZeros(LDigits), ScaleDiff);
308 assert(ShiftL < getWidth<DigitsT>() && "can't shift more than width")((void)0);
309
310 int32_t ShiftR = ScaleDiff - ShiftL;
311 if (ShiftR >= getWidth<DigitsT>()) {
312 // Don't bother shifting. RDigits will get zero-ed out anyway.
313 RDigits = 0;
314 return LScale;
315 }
316
317 LDigits <<= ShiftL;
318 RDigits >>= ShiftR;
319
320 LScale -= ShiftL;
321 RScale += ShiftR;
322 assert(LScale == RScale && "scales should match")((void)0);
323 return LScale;
324}
325
326/// Get the sum of two scaled numbers.
327///
328/// Get the sum of two scaled numbers with as much precision as possible.
329///
330/// \pre Adding 1 to \c LScale (or \c RScale) will not overflow INT16_MAX.
331template <class DigitsT>
332std::pair<DigitsT, int16_t> getSum(DigitsT LDigits, int16_t LScale,
333 DigitsT RDigits, int16_t RScale) {
334 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
335
336 // Check inputs up front. This is only relevant if addition overflows, but
337 // testing here should catch more bugs.
338 assert(LScale < INT16_MAX && "scale too large")((void)0);
339 assert(RScale < INT16_MAX && "scale too large")((void)0);
340
341 // Normalize digits to match scales.
342 int16_t Scale = matchScales(LDigits, LScale, RDigits, RScale);
343
344 // Compute sum.
345 DigitsT Sum = LDigits + RDigits;
346 if (Sum >= RDigits)
347 return std::make_pair(Sum, Scale);
348
349 // Adjust sum after arithmetic overflow.
350 DigitsT HighBit = DigitsT(1) << (getWidth<DigitsT>() - 1);
351 return std::make_pair(HighBit | Sum >> 1, Scale + 1);
352}
353
354/// Convenience helper for 32-bit sum.
355inline std::pair<uint32_t, int16_t> getSum32(uint32_t LDigits, int16_t LScale,
356 uint32_t RDigits, int16_t RScale) {
357 return getSum(LDigits, LScale, RDigits, RScale);
358}
359
360/// Convenience helper for 64-bit sum.
361inline std::pair<uint64_t, int16_t> getSum64(uint64_t LDigits, int16_t LScale,
362 uint64_t RDigits, int16_t RScale) {
363 return getSum(LDigits, LScale, RDigits, RScale);
364}
365
366/// Get the difference of two scaled numbers.
367///
368/// Get LHS minus RHS with as much precision as possible.
369///
370/// Returns \c (0, 0) if the RHS is larger than the LHS.
371template <class DigitsT>
372std::pair<DigitsT, int16_t> getDifference(DigitsT LDigits, int16_t LScale,
373 DigitsT RDigits, int16_t RScale) {
374 static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
375
376 // Normalize digits to match scales.
377 const DigitsT SavedRDigits = RDigits;
378 const int16_t SavedRScale = RScale;
379 matchScales(LDigits, LScale, RDigits, RScale);
380
381 // Compute difference.
382 if (LDigits <= RDigits)
383 return std::make_pair(0, 0);
384 if (RDigits || !SavedRDigits)
385 return std::make_pair(LDigits - RDigits, LScale);
386
387 // Check if RDigits just barely lost its last bit. E.g., for 32-bit:
388 //
389 // 1*2^32 - 1*2^0 == 0xffffffff != 1*2^32
390 const auto RLgFloor = getLgFloor(SavedRDigits, SavedRScale);
391 if (!compare(LDigits, LScale, DigitsT(1), RLgFloor + getWidth<DigitsT>()))
392 return std::make_pair(std::numeric_limits<DigitsT>::max(), RLgFloor);
393
394 return std::make_pair(LDigits, LScale);
395}
396
397/// Convenience helper for 32-bit difference.
398inline std::pair<uint32_t, int16_t> getDifference32(uint32_t LDigits,
399 int16_t LScale,
400 uint32_t RDigits,
401 int16_t RScale) {
402 return getDifference(LDigits, LScale, RDigits, RScale);
403}
404
405/// Convenience helper for 64-bit difference.
406inline std::pair<uint64_t, int16_t> getDifference64(uint64_t LDigits,
407 int16_t LScale,
408 uint64_t RDigits,
409 int16_t RScale) {
410 return getDifference(LDigits, LScale, RDigits, RScale);
411}
412
413} // end namespace ScaledNumbers
414} // end namespace llvm
415
416namespace llvm {
417
418class raw_ostream;
419class ScaledNumberBase {
420public:
421 static constexpr int DefaultPrecision = 10;
422
423 static void dump(uint64_t D, int16_t E, int Width);
424 static raw_ostream &print(raw_ostream &OS, uint64_t D, int16_t E, int Width,
425 unsigned Precision);
426 static std::string toString(uint64_t D, int16_t E, int Width,
427 unsigned Precision);
428 static int countLeadingZeros32(uint32_t N) { return countLeadingZeros(N); }
429 static int countLeadingZeros64(uint64_t N) { return countLeadingZeros(N); }
430 static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
431
432 static std::pair<uint64_t, bool> splitSigned(int64_t N) {
433 if (N >= 0)
434 return std::make_pair(N, false);
435 uint64_t Unsigned = N == INT64_MIN(-0x7fffffffffffffffLL - 1) ? UINT64_C(1)1ULL << 63 : uint64_t(-N);
436 return std::make_pair(Unsigned, true);
437 }
438 static int64_t joinSigned(uint64_t U, bool IsNeg) {
439 if (U > uint64_t(INT64_MAX0x7fffffffffffffffLL))
440 return IsNeg ? INT64_MIN(-0x7fffffffffffffffLL - 1) : INT64_MAX0x7fffffffffffffffLL;
441 return IsNeg ? -int64_t(U) : int64_t(U);
442 }
443};
444
445/// Simple representation of a scaled number.
446///
447/// ScaledNumber is a number represented by digits and a scale. It uses simple
448/// saturation arithmetic and every operation is well-defined for every value.
449/// It's somewhat similar in behaviour to a soft-float, but is *not* a
450/// replacement for one. If you're doing numerics, look at \a APFloat instead.
451/// Nevertheless, we've found these semantics useful for modelling certain cost
452/// metrics.
453///
454/// The number is split into a signed scale and unsigned digits. The number
455/// represented is \c getDigits()*2^getScale(). In this way, the digits are
456/// much like the mantissa in the x87 long double, but there is no canonical
457/// form so the same number can be represented by many bit representations.
458///
459/// ScaledNumber is templated on the underlying integer type for digits, which
460/// is expected to be unsigned.
461///
462/// Unlike APFloat, ScaledNumber does not model architecture floating point
463/// behaviour -- while this might make it a little faster and easier to reason
464/// about, it certainly makes it more dangerous for general numerics.
465///
466/// ScaledNumber is totally ordered. However, there is no canonical form, so
467/// there are multiple representations of most scalars. E.g.:
468///
469/// ScaledNumber(8u, 0) == ScaledNumber(4u, 1)
470/// ScaledNumber(4u, 1) == ScaledNumber(2u, 2)
471/// ScaledNumber(2u, 2) == ScaledNumber(1u, 3)
472///
473/// ScaledNumber implements most arithmetic operations. Precision is kept
474/// where possible. Uses simple saturation arithmetic, so that operations
475/// saturate to 0.0 or getLargest() rather than under or overflowing. It has
476/// some extra arithmetic for unit inversion. 0.0/0.0 is defined to be 0.0.
477/// Any other division by 0.0 is defined to be getLargest().
478///
479/// As a convenience for modifying the exponent, left and right shifting are
480/// both implemented, and both interpret negative shifts as positive shifts in
481/// the opposite direction.
482///
483/// Scales are limited to the range accepted by x87 long double. This makes
484/// it trivial to add functionality to convert to APFloat (this is already
485/// relied on for the implementation of printing).
486///
487/// Possible (and conflicting) future directions:
488///
489/// 1. Turn this into a wrapper around \a APFloat.
490/// 2. Share the algorithm implementations with \a APFloat.
491/// 3. Allow \a ScaledNumber to represent a signed number.
492template <class DigitsT> class ScaledNumber : ScaledNumberBase {
493public:
494 static_assert(!std::numeric_limits<DigitsT>::is_signed,
495 "only unsigned floats supported");
496
497 typedef DigitsT DigitsType;
498
499private:
500 typedef std::numeric_limits<DigitsType> DigitsLimits;
501
502 static constexpr int Width = sizeof(DigitsType) * 8;
503 static_assert(Width <= 64, "invalid integer width for digits");
504
505private:
506 DigitsType Digits = 0;
507 int16_t Scale = 0;
508
509public:
510 ScaledNumber() = default;
511
512 constexpr ScaledNumber(DigitsType Digits, int16_t Scale)
513 : Digits(Digits), Scale(Scale) {}
514
515private:
516 ScaledNumber(const std::pair<DigitsT, int16_t> &X)
517 : Digits(X.first), Scale(X.second) {}
518
519public:
520 static ScaledNumber getZero() { return ScaledNumber(0, 0); }
521 static ScaledNumber getOne() { return ScaledNumber(1, 0); }
522 static ScaledNumber getLargest() {
523 return ScaledNumber(DigitsLimits::max(), ScaledNumbers::MaxScale);
524 }
525 static ScaledNumber get(uint64_t N) { return adjustToWidth(N, 0); }
526 static ScaledNumber getInverse(uint64_t N) {
527 return get(N).invert();
528 }
529 static ScaledNumber getFraction(DigitsType N, DigitsType D) {
530 return getQuotient(N, D);
531 }
532
533 int16_t getScale() const { return Scale; }
534 DigitsType getDigits() const { return Digits; }
535
536 /// Convert to the given integer type.
537 ///
538 /// Convert to \c IntT using simple saturating arithmetic, truncating if
539 /// necessary.
540 template <class IntT> IntT toInt() const;
541
542 bool isZero() const { return !Digits; }
543 bool isLargest() const { return *this == getLargest(); }
544 bool isOne() const {
545 if (Scale > 0 || Scale <= -Width)
546 return false;
547 return Digits == DigitsType(1) << -Scale;
548 }
549
550 /// The log base 2, rounded.
551 ///
552 /// Get the lg of the scalar. lg 0 is defined to be INT32_MIN.
553 int32_t lg() const { return ScaledNumbers::getLg(Digits, Scale); }
554
555 /// The log base 2, rounded towards INT32_MIN.
556 ///
557 /// Get the lg floor. lg 0 is defined to be INT32_MIN.
558 int32_t lgFloor() const { return ScaledNumbers::getLgFloor(Digits, Scale); }
559
560 /// The log base 2, rounded towards INT32_MAX.
561 ///
562 /// Get the lg ceiling. lg 0 is defined to be INT32_MIN.
563 int32_t lgCeiling() const {
564 return ScaledNumbers::getLgCeiling(Digits, Scale);
565 }
566
567 bool operator==(const ScaledNumber &X) const { return compare(X) == 0; }
568 bool operator<(const ScaledNumber &X) const { return compare(X) < 0; }
569 bool operator!=(const ScaledNumber &X) const { return compare(X) != 0; }
570 bool operator>(const ScaledNumber &X) const { return compare(X) > 0; }
571 bool operator<=(const ScaledNumber &X) const { return compare(X) <= 0; }
572 bool operator>=(const ScaledNumber &X) const { return compare(X) >= 0; }
573
574 bool operator!() const { return isZero(); }
575
576 /// Convert to a decimal representation in a string.
577 ///
578 /// Convert to a string. Uses scientific notation for very large/small
579 /// numbers. Scientific notation is used roughly for numbers outside of the
580 /// range 2^-64 through 2^64.
581 ///
582 /// \c Precision indicates the number of decimal digits of precision to use;
583 /// 0 requests the maximum available.
584 ///
585 /// As a special case to make debugging easier, if the number is small enough
586 /// to convert without scientific notation and has more than \c Precision
587 /// digits before the decimal place, it's printed accurately to the first
588 /// digit past zero. E.g., assuming 10 digits of precision:
589 ///
590 /// 98765432198.7654... => 98765432198.8
591 /// 8765432198.7654... => 8765432198.8
592 /// 765432198.7654... => 765432198.8
593 /// 65432198.7654... => 65432198.77
594 /// 5432198.7654... => 5432198.765
595 std::string toString(unsigned Precision = DefaultPrecision) {
596 return ScaledNumberBase::toString(Digits, Scale, Width, Precision);
597 }
598
599 /// Print a decimal representation.
600 ///
601 /// Print a string. See toString for documentation.
602 raw_ostream &print(raw_ostream &OS,
603 unsigned Precision = DefaultPrecision) const {
604 return ScaledNumberBase::print(OS, Digits, Scale, Width, Precision);
605 }
606 void dump() const { return ScaledNumberBase::dump(Digits, Scale, Width); }
607
608 ScaledNumber &operator+=(const ScaledNumber &X) {
609 std::tie(Digits, Scale) =
610 ScaledNumbers::getSum(Digits, Scale, X.Digits, X.Scale);
611 // Check for exponent past MaxScale.
612 if (Scale > ScaledNumbers::MaxScale)
613 *this = getLargest();
614 return *this;
615 }
616 ScaledNumber &operator-=(const ScaledNumber &X) {
617 std::tie(Digits, Scale) =
618 ScaledNumbers::getDifference(Digits, Scale, X.Digits, X.Scale);
619 return *this;
620 }
621 ScaledNumber &operator*=(const ScaledNumber &X);
622 ScaledNumber &operator/=(const ScaledNumber &X);
623 ScaledNumber &operator<<=(int16_t Shift) {
624 shiftLeft(Shift);
35
←
Calling 'ScaledNumber::shiftLeft'
→
44
←
Returning from 'ScaledNumber::shiftLeft'
→
625 return *this;
626 }
627 ScaledNumber &operator>>=(int16_t Shift) {
628 shiftRight(Shift);
629 return *this;
630 }
631
632private:
633 void shiftLeft(int32_t Shift);
634 void shiftRight(int32_t Shift);
635
636 /// Adjust two floats to have matching exponents.
637 ///
638 /// Adjust \c this and \c X to have matching exponents. Returns the new \c X
639 /// by value. Does nothing if \a isZero() for either.
640 ///
641 /// The value that compares smaller will lose precision, and possibly become
642 /// \a isZero().
643 ScaledNumber matchScales(ScaledNumber X) {
644 ScaledNumbers::matchScales(Digits, Scale, X.Digits, X.Scale);
645 return X;
646 }
647
648public:
649 /// Scale a large number accurately.
650 ///
651 /// Scale N (multiply it by this). Uses full precision multiplication, even
652 /// if Width is smaller than 64, so information is not lost.
653 uint64_t scale(uint64_t N) const;
654 uint64_t scaleByInverse(uint64_t N) const {
655 // TODO: implement directly, rather than relying on inverse. Inverse is
656 // expensive.
657 return inverse().scale(N);
658 }
659 int64_t scale(int64_t N) const {
660 std::pair<uint64_t, bool> Unsigned = splitSigned(N);
661 return joinSigned(scale(Unsigned.first), Unsigned.second);
662 }
663 int64_t scaleByInverse(int64_t N) const {
664 std::pair<uint64_t, bool> Unsigned = splitSigned(N);
665 return joinSigned(scaleByInverse(Unsigned.first), Unsigned.second);
666 }
667
668 int compare(const ScaledNumber &X) const {
669 return ScaledNumbers::compare(Digits, Scale, X.Digits, X.Scale);
670 }
671 int compareTo(uint64_t N) const {
672 return ScaledNumbers::compare<uint64_t>(Digits, Scale, N, 0);
673 }
674 int compareTo(int64_t N) const { return N < 0 ? 1 : compareTo(uint64_t(N)); }
675
676 ScaledNumber &invert() { return *this = ScaledNumber::get(1) / *this; }
677 ScaledNumber inverse() const { return ScaledNumber(*this).invert(); }
678
679private:
680 static ScaledNumber getProduct(DigitsType LHS, DigitsType RHS) {
681 return ScaledNumbers::getProduct(LHS, RHS);
682 }
683 static ScaledNumber getQuotient(DigitsType Dividend, DigitsType Divisor) {
684 return ScaledNumbers::getQuotient(Dividend, Divisor);
685 }
686
687 static int countLeadingZerosWidth(DigitsType Digits) {
688 if (Width == 64)
689 return countLeadingZeros64(Digits);
690 if (Width == 32)
691 return countLeadingZeros32(Digits);
692 return countLeadingZeros32(Digits) + Width - 32;
693 }
694
695 /// Adjust a number to width, rounding up if necessary.
696 ///
697 /// Should only be called for \c Shift close to zero.
698 ///
699 /// \pre Shift >= MinScale && Shift + 64 <= MaxScale.
700 static ScaledNumber adjustToWidth(uint64_t N, int32_t Shift) {
701 assert(Shift >= ScaledNumbers::MinScale && "Shift should be close to 0")((void)0);
702 assert(Shift <= ScaledNumbers::MaxScale - 64 &&((void)0)
703 "Shift should be close to 0")((void)0);
704 auto Adjusted = ScaledNumbers::getAdjusted<DigitsT>(N, Shift);
705 return Adjusted;
706 }
707
708 static ScaledNumber getRounded(ScaledNumber P, bool Round) {
709 // Saturate.
710 if (P.isLargest())
711 return P;
712
713 return ScaledNumbers::getRounded(P.Digits, P.Scale, Round);
714 }
715};
716
717#define SCALED_NUMBER_BOP(op, base) \
718 template <class DigitsT> \
719 ScaledNumber<DigitsT> operator op(const ScaledNumber<DigitsT> &L, \
720 const ScaledNumber<DigitsT> &R) { \
721 return ScaledNumber<DigitsT>(L) base R; \
722 }
723SCALED_NUMBER_BOP(+, += )
724SCALED_NUMBER_BOP(-, -= )
725SCALED_NUMBER_BOP(*, *= )
726SCALED_NUMBER_BOP(/, /= )
727#undef SCALED_NUMBER_BOP
728
729template <class DigitsT>
730ScaledNumber<DigitsT> operator<<(const ScaledNumber<DigitsT> &L,
731 int16_t Shift) {
732 return ScaledNumber<DigitsT>(L) <<= Shift;
733}
734
735template <class DigitsT>
736ScaledNumber<DigitsT> operator>>(const ScaledNumber<DigitsT> &L,
737 int16_t Shift) {
738 return ScaledNumber<DigitsT>(L) >>= Shift;
739}
740
741template <class DigitsT>
742raw_ostream &operator<<(raw_ostream &OS, const ScaledNumber<DigitsT> &X) {
743 return X.print(OS, 10);
744}
745
746#define SCALED_NUMBER_COMPARE_TO_TYPE(op, T1, T2) \
747 template <class DigitsT> \
748 bool operator op(const ScaledNumber<DigitsT> &L, T1 R) { \
749 return L.compareTo(T2(R)) op 0; \
750 } \
751 template <class DigitsT> \
752 bool operator op(T1 L, const ScaledNumber<DigitsT> &R) { \
753 return 0 op R.compareTo(T2(L)); \
754 }
755#define SCALED_NUMBER_COMPARE_TO(op) \
756 SCALED_NUMBER_COMPARE_TO_TYPE(op, uint64_t, uint64_t) \
757 SCALED_NUMBER_COMPARE_TO_TYPE(op, uint32_t, uint64_t) \
758 SCALED_NUMBER_COMPARE_TO_TYPE(op, int64_t, int64_t) \
759 SCALED_NUMBER_COMPARE_TO_TYPE(op, int32_t, int64_t)
760SCALED_NUMBER_COMPARE_TO(< )
49
←
Assuming the condition is false
→
50
←
Returning zero, which participates in a condition later
→
761SCALED_NUMBER_COMPARE_TO(> )
762SCALED_NUMBER_COMPARE_TO(== )
763SCALED_NUMBER_COMPARE_TO(!= )
764SCALED_NUMBER_COMPARE_TO(<= )
765SCALED_NUMBER_COMPARE_TO(>= )
766#undef SCALED_NUMBER_COMPARE_TO
767#undef SCALED_NUMBER_COMPARE_TO_TYPE
768
769template <class DigitsT>
770uint64_t ScaledNumber<DigitsT>::scale(uint64_t N) const {
771 if (Width == 64 || N <= DigitsLimits::max())
772 return (get(N) * *this).template toInt<uint64_t>();
773
774 // Defer to the 64-bit version.
775 return ScaledNumber<uint64_t>(Digits, Scale).scale(N);
776}
777
778template <class DigitsT>
779template <class IntT>
780IntT ScaledNumber<DigitsT>::toInt() const {
781 typedef std::numeric_limits<IntT> Limits;
782 if (*this < 1)
48
←
Calling 'operator<<unsigned long long>'
→
51
←
Returning from 'operator<<unsigned long long>'
→
52
←
Taking false branch
→
783 return 0;
784 if (*this >= Limits::max())
53
←
Assuming the condition is false
→
54
←
Taking false branch
→
785 return Limits::max();
786
787 IntT N = Digits;
788 if (Scale
54.1
Field 'Scale' is > 0
54.1
Field 'Scale' is > 0
54.1
Field 'Scale' is > 0
 > 0) {
55
←
Taking true branch
→
789 assert(size_t(Scale) < sizeof(IntT) * 8)((void)0);
790 return N << Scale;
56
←
The result of the left shift is undefined due to shifting by '16383', which is greater or equal to the width of type 'unsigned long long'
791 }
792 if (Scale < 0) {
793 assert(size_t(-Scale) < sizeof(IntT) * 8)((void)0);
794 return N >> -Scale;
795 }
796 return N;
797}
798
799template <class DigitsT>
800ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
801operator*=(const ScaledNumber &X) {
802 if (isZero())
803 return *this;
804 if (X.isZero())
805 return *this = X;
806
807 // Save the exponents.
808 int32_t Scales = int32_t(Scale) + int32_t(X.Scale);
809
810 // Get the raw product.
811 *this = getProduct(Digits, X.Digits);
812
813 // Combine with exponents.
814 return *this <<= Scales;
815}
816template <class DigitsT>
817ScaledNumber<DigitsT> &ScaledNumber<DigitsT>::
818operator/=(const ScaledNumber &X) {
819 if (isZero())
32
←
Taking false branch
→
820 return *this;
821 if (X.isZero())
33
←
Taking false branch
→
822 return *this = getLargest();
823
824 // Save the exponents.
825 int32_t Scales = int32_t(Scale) - int32_t(X.Scale);
826
827 // Get the raw quotient.
828 *this = getQuotient(Digits, X.Digits);
829
830 // Combine with exponents.
831 return *this <<= Scales;
34
←
Calling 'ScaledNumber::operator<<='
→
45
←
Returning from 'ScaledNumber::operator<<='
→
832}
833template <class DigitsT> void ScaledNumber<DigitsT>::shiftLeft(int32_t Shift) {
834 if (!Shift
35.1
'Shift' is 8
35.1
'Shift' is 8
35.1
'Shift' is 8
 || isZero())
36
←
Taking false branch
→
835 return;
836 assert(Shift != INT32_MIN)((void)0);
837 if (Shift
36.1
'Shift' is >= 0
36.1
'Shift' is >= 0
36.1
'Shift' is >= 0
 < 0) {
37
←
Taking false branch
→
838 shiftRight(-Shift);
839 return;
840 }
841
842 // Shift as much as we can in the exponent.
843 int32_t ScaleShift = std::min(Shift, ScaledNumbers::MaxScale - Scale);
844 Scale += ScaleShift;
845 if (ScaleShift == Shift)
38
←
Assuming 'ScaleShift' is not equal to 'Shift'
→
39
←
Taking false branch
→
846 return;
847
848 // Check this late, since it's rare.
849 if (isLargest())
40
←
Taking false branch
→
850 return;
851
852 // Shift the digits themselves.
853 Shift -= ScaleShift;
854 if (Shift > countLeadingZerosWidth(Digits)) {
41
←
Assuming the condition is true
→
42
←
Taking true branch
→
855 // Saturate.
856 *this = getLargest();
43
←
The value 16383 is assigned to 'Temp.Scale'
→
857 return;
858 }
859
860 Digits <<= Shift;
861}
862
863template <class DigitsT> void ScaledNumber<DigitsT>::shiftRight(int32_t Shift) {
864 if (!Shift || isZero())
865 return;
866 assert(Shift != INT32_MIN)((void)0);
867 if (Shift < 0) {
868 shiftLeft(-Shift);
869 return;
870 }
871
872 // Shift as much as we can in the exponent.
873 int32_t ScaleShift = std::min(Shift, Scale - ScaledNumbers::MinScale);
874 Scale -= ScaleShift;
875 if (ScaleShift == Shift)
876 return;
877
878 // Shift the digits themselves.
879 Shift -= ScaleShift;
880 if (Shift >= Width) {
881 // Saturate.
882 *this = getZero();
883 return;
884 }
885
886 Digits >>= Shift;
887}
888
889
890} // end namespace llvm
891
892#endif // LLVM_SUPPORT_SCALEDNUMBER_H