Bug Summary

File:llvm/lib/Transforms/IPO/GlobalOpt.cpp
Warning:line 2244, column 22
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name GlobalOpt.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 -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/build-llvm -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO -I include -I /build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-command-line-argument -Wno-unknown-warning-option -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/build-llvm -ferror-limit 19 -fvisibility-inlines-hidden -fgnuc-version=4.2.1 -fcolor-diagnostics -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-26-234817-15343-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp

/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp

1//===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
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 transforms simple global variables that never have their address
10// taken. If obviously true, it marks read/write globals as constant, deletes
11// variables only stored to, etc.
12//
13//===----------------------------------------------------------------------===//
14
15#include "llvm/Transforms/IPO/GlobalOpt.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/STLExtras.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/ADT/Statistic.h"
21#include "llvm/ADT/Twine.h"
22#include "llvm/ADT/iterator_range.h"
23#include "llvm/Analysis/BlockFrequencyInfo.h"
24#include "llvm/Analysis/ConstantFolding.h"
25#include "llvm/Analysis/MemoryBuiltins.h"
26#include "llvm/Analysis/TargetLibraryInfo.h"
27#include "llvm/Analysis/TargetTransformInfo.h"
28#include "llvm/BinaryFormat/Dwarf.h"
29#include "llvm/IR/Attributes.h"
30#include "llvm/IR/BasicBlock.h"
31#include "llvm/IR/CallingConv.h"
32#include "llvm/IR/Constant.h"
33#include "llvm/IR/Constants.h"
34#include "llvm/IR/DataLayout.h"
35#include "llvm/IR/DebugInfoMetadata.h"
36#include "llvm/IR/DerivedTypes.h"
37#include "llvm/IR/Dominators.h"
38#include "llvm/IR/Function.h"
39#include "llvm/IR/GetElementPtrTypeIterator.h"
40#include "llvm/IR/GlobalAlias.h"
41#include "llvm/IR/GlobalValue.h"
42#include "llvm/IR/GlobalVariable.h"
43#include "llvm/IR/IRBuilder.h"
44#include "llvm/IR/InstrTypes.h"
45#include "llvm/IR/Instruction.h"
46#include "llvm/IR/Instructions.h"
47#include "llvm/IR/IntrinsicInst.h"
48#include "llvm/IR/Module.h"
49#include "llvm/IR/Operator.h"
50#include "llvm/IR/Type.h"
51#include "llvm/IR/Use.h"
52#include "llvm/IR/User.h"
53#include "llvm/IR/Value.h"
54#include "llvm/IR/ValueHandle.h"
55#include "llvm/InitializePasses.h"
56#include "llvm/Pass.h"
57#include "llvm/Support/AtomicOrdering.h"
58#include "llvm/Support/Casting.h"
59#include "llvm/Support/CommandLine.h"
60#include "llvm/Support/Debug.h"
61#include "llvm/Support/ErrorHandling.h"
62#include "llvm/Support/MathExtras.h"
63#include "llvm/Support/raw_ostream.h"
64#include "llvm/Transforms/IPO.h"
65#include "llvm/Transforms/Utils/CtorUtils.h"
66#include "llvm/Transforms/Utils/Evaluator.h"
67#include "llvm/Transforms/Utils/GlobalStatus.h"
68#include "llvm/Transforms/Utils/Local.h"
69#include <cassert>
70#include <cstdint>
71#include <utility>
72#include <vector>
73
74using namespace llvm;
75
76#define DEBUG_TYPE"globalopt" "globalopt"
77
78STATISTIC(NumMarked , "Number of globals marked constant")static llvm::Statistic NumMarked = {"globalopt", "NumMarked",
"Number of globals marked constant"}
;
79STATISTIC(NumUnnamed , "Number of globals marked unnamed_addr")static llvm::Statistic NumUnnamed = {"globalopt", "NumUnnamed"
, "Number of globals marked unnamed_addr"}
;
80STATISTIC(NumSRA , "Number of aggregate globals broken into scalars")static llvm::Statistic NumSRA = {"globalopt", "NumSRA", "Number of aggregate globals broken into scalars"
}
;
81STATISTIC(NumSubstitute,"Number of globals with initializers stored into them")static llvm::Statistic NumSubstitute = {"globalopt", "NumSubstitute"
, "Number of globals with initializers stored into them"}
;
82STATISTIC(NumDeleted , "Number of globals deleted")static llvm::Statistic NumDeleted = {"globalopt", "NumDeleted"
, "Number of globals deleted"}
;
83STATISTIC(NumGlobUses , "Number of global uses devirtualized")static llvm::Statistic NumGlobUses = {"globalopt", "NumGlobUses"
, "Number of global uses devirtualized"}
;
84STATISTIC(NumLocalized , "Number of globals localized")static llvm::Statistic NumLocalized = {"globalopt", "NumLocalized"
, "Number of globals localized"}
;
85STATISTIC(NumShrunkToBool , "Number of global vars shrunk to booleans")static llvm::Statistic NumShrunkToBool = {"globalopt", "NumShrunkToBool"
, "Number of global vars shrunk to booleans"}
;
86STATISTIC(NumFastCallFns , "Number of functions converted to fastcc")static llvm::Statistic NumFastCallFns = {"globalopt", "NumFastCallFns"
, "Number of functions converted to fastcc"}
;
87STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated")static llvm::Statistic NumCtorsEvaluated = {"globalopt", "NumCtorsEvaluated"
, "Number of static ctors evaluated"}
;
88STATISTIC(NumNestRemoved , "Number of nest attributes removed")static llvm::Statistic NumNestRemoved = {"globalopt", "NumNestRemoved"
, "Number of nest attributes removed"}
;
89STATISTIC(NumAliasesResolved, "Number of global aliases resolved")static llvm::Statistic NumAliasesResolved = {"globalopt", "NumAliasesResolved"
, "Number of global aliases resolved"}
;
90STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated")static llvm::Statistic NumAliasesRemoved = {"globalopt", "NumAliasesRemoved"
, "Number of global aliases eliminated"}
;
91STATISTIC(NumCXXDtorsRemoved, "Number of global C++ destructors removed")static llvm::Statistic NumCXXDtorsRemoved = {"globalopt", "NumCXXDtorsRemoved"
, "Number of global C++ destructors removed"}
;
92STATISTIC(NumInternalFunc, "Number of internal functions")static llvm::Statistic NumInternalFunc = {"globalopt", "NumInternalFunc"
, "Number of internal functions"}
;
93STATISTIC(NumColdCC, "Number of functions marked coldcc")static llvm::Statistic NumColdCC = {"globalopt", "NumColdCC",
"Number of functions marked coldcc"}
;
94
95static cl::opt<bool>
96 EnableColdCCStressTest("enable-coldcc-stress-test",
97 cl::desc("Enable stress test of coldcc by adding "
98 "calling conv to all internal functions."),
99 cl::init(false), cl::Hidden);
100
101static cl::opt<int> ColdCCRelFreq(
102 "coldcc-rel-freq", cl::Hidden, cl::init(2), cl::ZeroOrMore,
103 cl::desc(
104 "Maximum block frequency, expressed as a percentage of caller's "
105 "entry frequency, for a call site to be considered cold for enabling"
106 "coldcc"));
107
108/// Is this global variable possibly used by a leak checker as a root? If so,
109/// we might not really want to eliminate the stores to it.
110static bool isLeakCheckerRoot(GlobalVariable *GV) {
111 // A global variable is a root if it is a pointer, or could plausibly contain
112 // a pointer. There are two challenges; one is that we could have a struct
113 // the has an inner member which is a pointer. We recurse through the type to
114 // detect these (up to a point). The other is that we may actually be a union
115 // of a pointer and another type, and so our LLVM type is an integer which
116 // gets converted into a pointer, or our type is an [i8 x #] with a pointer
117 // potentially contained here.
118
119 if (GV->hasPrivateLinkage())
120 return false;
121
122 SmallVector<Type *, 4> Types;
123 Types.push_back(GV->getValueType());
124
125 unsigned Limit = 20;
126 do {
127 Type *Ty = Types.pop_back_val();
128 switch (Ty->getTypeID()) {
129 default: break;
130 case Type::PointerTyID:
131 return true;
132 case Type::FixedVectorTyID:
133 case Type::ScalableVectorTyID:
134 if (cast<VectorType>(Ty)->getElementType()->isPointerTy())
135 return true;
136 break;
137 case Type::ArrayTyID:
138 Types.push_back(cast<ArrayType>(Ty)->getElementType());
139 break;
140 case Type::StructTyID: {
141 StructType *STy = cast<StructType>(Ty);
142 if (STy->isOpaque()) return true;
143 for (StructType::element_iterator I = STy->element_begin(),
144 E = STy->element_end(); I != E; ++I) {
145 Type *InnerTy = *I;
146 if (isa<PointerType>(InnerTy)) return true;
147 if (isa<StructType>(InnerTy) || isa<ArrayType>(InnerTy) ||
148 isa<VectorType>(InnerTy))
149 Types.push_back(InnerTy);
150 }
151 break;
152 }
153 }
154 if (--Limit == 0) return true;
155 } while (!Types.empty());
156 return false;
157}
158
159/// Given a value that is stored to a global but never read, determine whether
160/// it's safe to remove the store and the chain of computation that feeds the
161/// store.
162static bool IsSafeComputationToRemove(
163 Value *V, function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
164 do {
165 if (isa<Constant>(V))
166 return true;
167 if (!V->hasOneUse())
168 return false;
169 if (isa<LoadInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V) ||
170 isa<GlobalValue>(V))
171 return false;
172 if (isAllocationFn(V, GetTLI))
173 return true;
174
175 Instruction *I = cast<Instruction>(V);
176 if (I->mayHaveSideEffects())
177 return false;
178 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
179 if (!GEP->hasAllConstantIndices())
180 return false;
181 } else if (I->getNumOperands() != 1) {
182 return false;
183 }
184
185 V = I->getOperand(0);
186 } while (true);
187}
188
189/// This GV is a pointer root. Loop over all users of the global and clean up
190/// any that obviously don't assign the global a value that isn't dynamically
191/// allocated.
192static bool
193CleanupPointerRootUsers(GlobalVariable *GV,
194 function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
195 // A brief explanation of leak checkers. The goal is to find bugs where
196 // pointers are forgotten, causing an accumulating growth in memory
197 // usage over time. The common strategy for leak checkers is to explicitly
198 // allow the memory pointed to by globals at exit. This is popular because it
199 // also solves another problem where the main thread of a C++ program may shut
200 // down before other threads that are still expecting to use those globals. To
201 // handle that case, we expect the program may create a singleton and never
202 // destroy it.
203
204 bool Changed = false;
205
206 // If Dead[n].first is the only use of a malloc result, we can delete its
207 // chain of computation and the store to the global in Dead[n].second.
208 SmallVector<std::pair<Instruction *, Instruction *>, 32> Dead;
209
210 // Constants can't be pointers to dynamically allocated memory.
211 for (User *U : llvm::make_early_inc_range(GV->users())) {
212 if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
213 Value *V = SI->getValueOperand();
214 if (isa<Constant>(V)) {
215 Changed = true;
216 SI->eraseFromParent();
217 } else if (Instruction *I = dyn_cast<Instruction>(V)) {
218 if (I->hasOneUse())
219 Dead.push_back(std::make_pair(I, SI));
220 }
221 } else if (MemSetInst *MSI = dyn_cast<MemSetInst>(U)) {
222 if (isa<Constant>(MSI->getValue())) {
223 Changed = true;
224 MSI->eraseFromParent();
225 } else if (Instruction *I = dyn_cast<Instruction>(MSI->getValue())) {
226 if (I->hasOneUse())
227 Dead.push_back(std::make_pair(I, MSI));
228 }
229 } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(U)) {
230 GlobalVariable *MemSrc = dyn_cast<GlobalVariable>(MTI->getSource());
231 if (MemSrc && MemSrc->isConstant()) {
232 Changed = true;
233 MTI->eraseFromParent();
234 } else if (Instruction *I = dyn_cast<Instruction>(MemSrc)) {
235 if (I->hasOneUse())
236 Dead.push_back(std::make_pair(I, MTI));
237 }
238 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
239 if (CE->use_empty()) {
240 CE->destroyConstant();
241 Changed = true;
242 }
243 } else if (Constant *C = dyn_cast<Constant>(U)) {
244 if (isSafeToDestroyConstant(C)) {
245 C->destroyConstant();
246 // This could have invalidated UI, start over from scratch.
247 Dead.clear();
248 CleanupPointerRootUsers(GV, GetTLI);
249 return true;
250 }
251 }
252 }
253
254 for (int i = 0, e = Dead.size(); i != e; ++i) {
255 if (IsSafeComputationToRemove(Dead[i].first, GetTLI)) {
256 Dead[i].second->eraseFromParent();
257 Instruction *I = Dead[i].first;
258 do {
259 if (isAllocationFn(I, GetTLI))
260 break;
261 Instruction *J = dyn_cast<Instruction>(I->getOperand(0));
262 if (!J)
263 break;
264 I->eraseFromParent();
265 I = J;
266 } while (true);
267 I->eraseFromParent();
268 Changed = true;
269 }
270 }
271
272 return Changed;
273}
274
275/// We just marked GV constant. Loop over all users of the global, cleaning up
276/// the obvious ones. This is largely just a quick scan over the use list to
277/// clean up the easy and obvious cruft. This returns true if it made a change.
278static bool CleanupConstantGlobalUsers(
279 Value *V, Constant *Init, const DataLayout &DL,
280 function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
281 bool Changed = false;
282 // Note that we need to use a weak value handle for the worklist items. When
283 // we delete a constant array, we may also be holding pointer to one of its
284 // elements (or an element of one of its elements if we're dealing with an
285 // array of arrays) in the worklist.
286 SmallVector<WeakTrackingVH, 8> WorkList(V->users());
287 while (!WorkList.empty()) {
288 Value *UV = WorkList.pop_back_val();
289 if (!UV)
290 continue;
291
292 User *U = cast<User>(UV);
293
294 if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
295 if (Init) {
296 if (auto *Casted =
297 ConstantFoldLoadThroughBitcast(Init, LI->getType(), DL)) {
298 // Replace the load with the initializer.
299 LI->replaceAllUsesWith(Casted);
300 LI->eraseFromParent();
301 Changed = true;
302 }
303 }
304 } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
305 // Store must be unreachable or storing Init into the global.
306 SI->eraseFromParent();
307 Changed = true;
308 } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
309 if (CE->getOpcode() == Instruction::GetElementPtr) {
310 Constant *SubInit = nullptr;
311 if (Init)
312 SubInit = ConstantFoldLoadThroughGEPConstantExpr(
313 Init, CE, V->getType()->getPointerElementType(), DL);
314 Changed |= CleanupConstantGlobalUsers(CE, SubInit, DL, GetTLI);
315 } else if ((CE->getOpcode() == Instruction::BitCast &&
316 CE->getType()->isPointerTy()) ||
317 CE->getOpcode() == Instruction::AddrSpaceCast) {
318 // Pointer cast, delete any stores and memsets to the global.
319 Changed |= CleanupConstantGlobalUsers(CE, nullptr, DL, GetTLI);
320 }
321
322 if (CE->use_empty()) {
323 CE->destroyConstant();
324 Changed = true;
325 }
326 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
327 // Do not transform "gepinst (gep constexpr (GV))" here, because forming
328 // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold
329 // and will invalidate our notion of what Init is.
330 Constant *SubInit = nullptr;
331 if (!isa<ConstantExpr>(GEP->getOperand(0))) {
332 ConstantExpr *CE = dyn_cast_or_null<ConstantExpr>(
333 ConstantFoldInstruction(GEP, DL, &GetTLI(*GEP->getFunction())));
334 if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr)
335 SubInit = ConstantFoldLoadThroughGEPConstantExpr(
336 Init, CE, V->getType()->getPointerElementType(), DL);
337
338 // If the initializer is an all-null value and we have an inbounds GEP,
339 // we already know what the result of any load from that GEP is.
340 // TODO: Handle splats.
341 if (Init && isa<ConstantAggregateZero>(Init) && GEP->isInBounds())
342 SubInit = Constant::getNullValue(GEP->getResultElementType());
343 }
344 Changed |= CleanupConstantGlobalUsers(GEP, SubInit, DL, GetTLI);
345
346 if (GEP->use_empty()) {
347 GEP->eraseFromParent();
348 Changed = true;
349 }
350 } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv
351 if (MI->getRawDest() == V) {
352 MI->eraseFromParent();
353 Changed = true;
354 }
355
356 } else if (Constant *C = dyn_cast<Constant>(U)) {
357 // If we have a chain of dead constantexprs or other things dangling from
358 // us, and if they are all dead, nuke them without remorse.
359 if (isSafeToDestroyConstant(C)) {
360 C->destroyConstant();
361 CleanupConstantGlobalUsers(V, Init, DL, GetTLI);
362 return true;
363 }
364 }
365 }
366 return Changed;
367}
368
369static bool isSafeSROAElementUse(Value *V);
370
371/// Return true if the specified GEP is a safe user of a derived
372/// expression from a global that we want to SROA.
373static bool isSafeSROAGEP(User *U) {
374 // Check to see if this ConstantExpr GEP is SRA'able. In particular, we
375 // don't like < 3 operand CE's, and we don't like non-constant integer
376 // indices. This enforces that all uses are 'gep GV, 0, C, ...' for some
377 // value of C.
378 if (U->getNumOperands() < 3 || !isa<Constant>(U->getOperand(1)) ||
379 !cast<Constant>(U->getOperand(1))->isNullValue())
380 return false;
381
382 gep_type_iterator GEPI = gep_type_begin(U), E = gep_type_end(U);
383 ++GEPI; // Skip over the pointer index.
384
385 // For all other level we require that the indices are constant and inrange.
386 // In particular, consider: A[0][i]. We cannot know that the user isn't doing
387 // invalid things like allowing i to index an out-of-range subscript that
388 // accesses A[1]. This can also happen between different members of a struct
389 // in llvm IR.
390 for (; GEPI != E; ++GEPI) {
391 if (GEPI.isStruct())
392 continue;
393
394 ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand());
395 if (!IdxVal || (GEPI.isBoundedSequential() &&
396 IdxVal->getZExtValue() >= GEPI.getSequentialNumElements()))
397 return false;
398 }
399
400 return llvm::all_of(U->users(),
401 [](User *UU) { return isSafeSROAElementUse(UU); });
402}
403
404/// Return true if the specified instruction is a safe user of a derived
405/// expression from a global that we want to SROA.
406static bool isSafeSROAElementUse(Value *V) {
407 // We might have a dead and dangling constant hanging off of here.
408 if (Constant *C = dyn_cast<Constant>(V))
409 return isSafeToDestroyConstant(C);
410
411 Instruction *I = dyn_cast<Instruction>(V);
412 if (!I) return false;
413
414 // Loads are ok.
415 if (isa<LoadInst>(I)) return true;
416
417 // Stores *to* the pointer are ok.
418 if (StoreInst *SI = dyn_cast<StoreInst>(I))
419 return SI->getOperand(0) != V;
420
421 // Otherwise, it must be a GEP. Check it and its users are safe to SRA.
422 return isa<GetElementPtrInst>(I) && isSafeSROAGEP(I);
423}
424
425/// Look at all uses of the global and decide whether it is safe for us to
426/// perform this transformation.
427static bool GlobalUsersSafeToSRA(GlobalValue *GV) {
428 for (User *U : GV->users()) {
429 // The user of the global must be a GEP Inst or a ConstantExpr GEP.
430 if (!isa<GetElementPtrInst>(U) &&
431 (!isa<ConstantExpr>(U) ||
432 cast<ConstantExpr>(U)->getOpcode() != Instruction::GetElementPtr))
433 return false;
434
435 // Check the gep and it's users are safe to SRA
436 if (!isSafeSROAGEP(U))
437 return false;
438 }
439
440 return true;
441}
442
443static bool IsSRASequential(Type *T) {
444 return isa<ArrayType>(T) || isa<VectorType>(T);
445}
446static uint64_t GetSRASequentialNumElements(Type *T) {
447 if (ArrayType *AT = dyn_cast<ArrayType>(T))
448 return AT->getNumElements();
449 return cast<FixedVectorType>(T)->getNumElements();
450}
451static Type *GetSRASequentialElementType(Type *T) {
452 if (ArrayType *AT = dyn_cast<ArrayType>(T))
453 return AT->getElementType();
454 return cast<VectorType>(T)->getElementType();
455}
456static bool CanDoGlobalSRA(GlobalVariable *GV) {
457 Constant *Init = GV->getInitializer();
458
459 if (isa<StructType>(Init->getType())) {
460 // nothing to check
461 } else if (IsSRASequential(Init->getType())) {
462 if (GetSRASequentialNumElements(Init->getType()) > 16 &&
463 GV->hasNUsesOrMore(16))
464 return false; // It's not worth it.
465 } else
466 return false;
467
468 return GlobalUsersSafeToSRA(GV);
469}
470
471/// Copy over the debug info for a variable to its SRA replacements.
472static void transferSRADebugInfo(GlobalVariable *GV, GlobalVariable *NGV,
473 uint64_t FragmentOffsetInBits,
474 uint64_t FragmentSizeInBits,
475 uint64_t VarSize) {
476 SmallVector<DIGlobalVariableExpression *, 1> GVs;
477 GV->getDebugInfo(GVs);
478 for (auto *GVE : GVs) {
479 DIVariable *Var = GVE->getVariable();
480 DIExpression *Expr = GVE->getExpression();
481 // If the FragmentSize is smaller than the variable,
482 // emit a fragment expression.
483 if (FragmentSizeInBits < VarSize) {
484 if (auto E = DIExpression::createFragmentExpression(
485 Expr, FragmentOffsetInBits, FragmentSizeInBits))
486 Expr = *E;
487 else
488 return;
489 }
490 auto *NGVE = DIGlobalVariableExpression::get(GVE->getContext(), Var, Expr);
491 NGV->addDebugInfo(NGVE);
492 }
493}
494
495/// Perform scalar replacement of aggregates on the specified global variable.
496/// This opens the door for other optimizations by exposing the behavior of the
497/// program in a more fine-grained way. We have determined that this
498/// transformation is safe already. We return the first global variable we
499/// insert so that the caller can reprocess it.
500static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &DL) {
501 // Make sure this global only has simple uses that we can SRA.
502 if (!CanDoGlobalSRA(GV))
503 return nullptr;
504
505 assert(GV->hasLocalLinkage())(static_cast <bool> (GV->hasLocalLinkage()) ? void (
0) : __assert_fail ("GV->hasLocalLinkage()", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 505, __extension__ __PRETTY_FUNCTION__))
;
506 Constant *Init = GV->getInitializer();
507 Type *Ty = Init->getType();
508 uint64_t VarSize = DL.getTypeSizeInBits(Ty);
509
510 std::map<unsigned, GlobalVariable *> NewGlobals;
511
512 // Get the alignment of the global, either explicit or target-specific.
513 Align StartAlignment =
514 DL.getValueOrABITypeAlignment(GV->getAlign(), GV->getType());
515
516 // Loop over all users and create replacement variables for used aggregate
517 // elements.
518 for (User *GEP : GV->users()) {
519 assert(((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode() ==(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
cast<ConstantExpr>(GEP)->getOpcode() == Instruction
::GetElementPtr) || isa<GetElementPtrInst>(GEP)) &&
"NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode() == Instruction::GetElementPtr) || isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 522, __extension__ __PRETTY_FUNCTION__))
520 Instruction::GetElementPtr) ||(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
cast<ConstantExpr>(GEP)->getOpcode() == Instruction
::GetElementPtr) || isa<GetElementPtrInst>(GEP)) &&
"NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode() == Instruction::GetElementPtr) || isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 522, __extension__ __PRETTY_FUNCTION__))
521 isa<GetElementPtrInst>(GEP)) &&(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
cast<ConstantExpr>(GEP)->getOpcode() == Instruction
::GetElementPtr) || isa<GetElementPtrInst>(GEP)) &&
"NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode() == Instruction::GetElementPtr) || isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 522, __extension__ __PRETTY_FUNCTION__))
522 "NonGEP CE's are not SRAable!")(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
cast<ConstantExpr>(GEP)->getOpcode() == Instruction
::GetElementPtr) || isa<GetElementPtrInst>(GEP)) &&
"NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode() == Instruction::GetElementPtr) || isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 522, __extension__ __PRETTY_FUNCTION__))
;
523
524 // Ignore the 1th operand, which has to be zero or else the program is quite
525 // broken (undefined). Get the 2nd operand, which is the structure or array
526 // index.
527 unsigned ElementIdx = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
528 if (NewGlobals.count(ElementIdx) == 1)
529 continue; // we`ve already created replacement variable
530 assert(NewGlobals.count(ElementIdx) == 0)(static_cast <bool> (NewGlobals.count(ElementIdx) == 0)
? void (0) : __assert_fail ("NewGlobals.count(ElementIdx) == 0"
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 530, __extension__ __PRETTY_FUNCTION__))
;
531
532 Type *ElTy = nullptr;
533 if (StructType *STy = dyn_cast<StructType>(Ty))
534 ElTy = STy->getElementType(ElementIdx);
535 else
536 ElTy = GetSRASequentialElementType(Ty);
537 assert(ElTy)(static_cast <bool> (ElTy) ? void (0) : __assert_fail (
"ElTy", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 537, __extension__ __PRETTY_FUNCTION__))
;
538
539 Constant *In = Init->getAggregateElement(ElementIdx);
540 assert(In && "Couldn't get element of initializer?")(static_cast <bool> (In && "Couldn't get element of initializer?"
) ? void (0) : __assert_fail ("In && \"Couldn't get element of initializer?\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 540, __extension__ __PRETTY_FUNCTION__))
;
541
542 GlobalVariable *NGV = new GlobalVariable(
543 ElTy, false, GlobalVariable::InternalLinkage, In,
544 GV->getName() + "." + Twine(ElementIdx), GV->getThreadLocalMode(),
545 GV->getType()->getAddressSpace());
546 NGV->setExternallyInitialized(GV->isExternallyInitialized());
547 NGV->copyAttributesFrom(GV);
548 NewGlobals.insert(std::make_pair(ElementIdx, NGV));
549
550 if (StructType *STy = dyn_cast<StructType>(Ty)) {
551 const StructLayout &Layout = *DL.getStructLayout(STy);
552
553 // Calculate the known alignment of the field. If the original aggregate
554 // had 256 byte alignment for example, something might depend on that:
555 // propagate info to each field.
556 uint64_t FieldOffset = Layout.getElementOffset(ElementIdx);
557 Align NewAlign = commonAlignment(StartAlignment, FieldOffset);
558 if (NewAlign > DL.getABITypeAlign(STy->getElementType(ElementIdx)))
559 NGV->setAlignment(NewAlign);
560
561 // Copy over the debug info for the variable.
562 uint64_t Size = DL.getTypeAllocSizeInBits(NGV->getValueType());
563 uint64_t FragmentOffsetInBits = Layout.getElementOffsetInBits(ElementIdx);
564 transferSRADebugInfo(GV, NGV, FragmentOffsetInBits, Size, VarSize);
565 } else {
566 uint64_t EltSize = DL.getTypeAllocSize(ElTy);
567 Align EltAlign = DL.getABITypeAlign(ElTy);
568 uint64_t FragmentSizeInBits = DL.getTypeAllocSizeInBits(ElTy);
569
570 // Calculate the known alignment of the field. If the original aggregate
571 // had 256 byte alignment for example, something might depend on that:
572 // propagate info to each field.
573 Align NewAlign = commonAlignment(StartAlignment, EltSize * ElementIdx);
574 if (NewAlign > EltAlign)
575 NGV->setAlignment(NewAlign);
576 transferSRADebugInfo(GV, NGV, FragmentSizeInBits * ElementIdx,
577 FragmentSizeInBits, VarSize);
578 }
579 }
580
581 if (NewGlobals.empty())
582 return nullptr;
583
584 Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
585 for (auto NewGlobalVar : NewGlobals)
586 Globals.push_back(NewGlobalVar.second);
587
588 LLVM_DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "PERFORMING GLOBAL SRA ON: "
<< *GV << "\n"; } } while (false)
;
589
590 Constant *NullInt =Constant::getNullValue(Type::getInt32Ty(GV->getContext()));
591
592 // Loop over all of the uses of the global, replacing the constantexpr geps,
593 // with smaller constantexpr geps or direct references.
594 while (!GV->use_empty()) {
595 User *GEP = GV->user_back();
596 assert(((isa<ConstantExpr>(GEP) &&(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
cast<ConstantExpr>(GEP)->getOpcode()==Instruction::
GetElementPtr)|| isa<GetElementPtrInst>(GEP)) &&
"NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 598, __extension__ __PRETTY_FUNCTION__))
597 cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)||(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
cast<ConstantExpr>(GEP)->getOpcode()==Instruction::
GetElementPtr)|| isa<GetElementPtrInst>(GEP)) &&
"NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 598, __extension__ __PRETTY_FUNCTION__))
598 isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!")(static_cast <bool> (((isa<ConstantExpr>(GEP) &&
cast<ConstantExpr>(GEP)->getOpcode()==Instruction::
GetElementPtr)|| isa<GetElementPtrInst>(GEP)) &&
"NonGEP CE's are not SRAable!") ? void (0) : __assert_fail (
"((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| isa<GetElementPtrInst>(GEP)) && \"NonGEP CE's are not SRAable!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 598, __extension__ __PRETTY_FUNCTION__))
;
599
600 // Ignore the 1th operand, which has to be zero or else the program is quite
601 // broken (undefined). Get the 2nd operand, which is the structure or array
602 // index.
603 unsigned ElementIdx = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
604 assert(NewGlobals.count(ElementIdx) == 1)(static_cast <bool> (NewGlobals.count(ElementIdx) == 1)
? void (0) : __assert_fail ("NewGlobals.count(ElementIdx) == 1"
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 604, __extension__ __PRETTY_FUNCTION__))
;
605
606 Value *NewPtr = NewGlobals[ElementIdx];
607 Type *NewTy = NewGlobals[ElementIdx]->getValueType();
608
609 // Form a shorter GEP if needed.
610 if (GEP->getNumOperands() > 3) {
611 if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) {
612 SmallVector<Constant*, 8> Idxs;
613 Idxs.push_back(NullInt);
614 for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
615 Idxs.push_back(CE->getOperand(i));
616 NewPtr =
617 ConstantExpr::getGetElementPtr(NewTy, cast<Constant>(NewPtr), Idxs);
618 } else {
619 GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP);
620 SmallVector<Value*, 8> Idxs;
621 Idxs.push_back(NullInt);
622 for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i)
623 Idxs.push_back(GEPI->getOperand(i));
624 NewPtr = GetElementPtrInst::Create(
625 NewTy, NewPtr, Idxs, GEPI->getName() + "." + Twine(ElementIdx),
626 GEPI);
627 }
628 }
629 GEP->replaceAllUsesWith(NewPtr);
630
631 // We changed the pointer of any memory access user. Recalculate alignments.
632 for (User *U : NewPtr->users()) {
633 if (auto *Load = dyn_cast<LoadInst>(U)) {
634 Align PrefAlign = DL.getPrefTypeAlign(Load->getType());
635 Align NewAlign = getOrEnforceKnownAlignment(Load->getPointerOperand(),
636 PrefAlign, DL, Load);
637 Load->setAlignment(NewAlign);
638 }
639 if (auto *Store = dyn_cast<StoreInst>(U)) {
640 Align PrefAlign =
641 DL.getPrefTypeAlign(Store->getValueOperand()->getType());
642 Align NewAlign = getOrEnforceKnownAlignment(Store->getPointerOperand(),
643 PrefAlign, DL, Store);
644 Store->setAlignment(NewAlign);
645 }
646 }
647
648 if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP))
649 GEPI->eraseFromParent();
650 else
651 cast<ConstantExpr>(GEP)->destroyConstant();
652 }
653
654 // Delete the old global, now that it is dead.
655 Globals.erase(GV);
656 ++NumSRA;
657
658 assert(NewGlobals.size() > 0)(static_cast <bool> (NewGlobals.size() > 0) ? void (
0) : __assert_fail ("NewGlobals.size() > 0", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 658, __extension__ __PRETTY_FUNCTION__))
;
659 return NewGlobals.begin()->second;
660}
661
662/// Return true if all users of the specified value will trap if the value is
663/// dynamically null. PHIs keeps track of any phi nodes we've seen to avoid
664/// reprocessing them.
665static bool AllUsesOfValueWillTrapIfNull(const Value *V,
666 SmallPtrSetImpl<const PHINode*> &PHIs) {
667 for (const User *U : V->users()) {
668 if (const Instruction *I = dyn_cast<Instruction>(U)) {
669 // If null pointer is considered valid, then all uses are non-trapping.
670 // Non address-space 0 globals have already been pruned by the caller.
671 if (NullPointerIsDefined(I->getFunction()))
672 return false;
673 }
674 if (isa<LoadInst>(U)) {
675 // Will trap.
676 } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
677 if (SI->getOperand(0) == V) {
678 //cerr << "NONTRAPPING USE: " << *U;
679 return false; // Storing the value.
680 }
681 } else if (const CallInst *CI = dyn_cast<CallInst>(U)) {
682 if (CI->getCalledOperand() != V) {
683 //cerr << "NONTRAPPING USE: " << *U;
684 return false; // Not calling the ptr
685 }
686 } else if (const InvokeInst *II = dyn_cast<InvokeInst>(U)) {
687 if (II->getCalledOperand() != V) {
688 //cerr << "NONTRAPPING USE: " << *U;
689 return false; // Not calling the ptr
690 }
691 } else if (const BitCastInst *CI = dyn_cast<BitCastInst>(U)) {
692 if (!AllUsesOfValueWillTrapIfNull(CI, PHIs)) return false;
693 } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
694 if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false;
695 } else if (const PHINode *PN = dyn_cast<PHINode>(U)) {
696 // If we've already seen this phi node, ignore it, it has already been
697 // checked.
698 if (PHIs.insert(PN).second && !AllUsesOfValueWillTrapIfNull(PN, PHIs))
699 return false;
700 } else if (isa<ICmpInst>(U) &&
701 !ICmpInst::isSigned(cast<ICmpInst>(U)->getPredicate()) &&
702 isa<LoadInst>(U->getOperand(0)) &&
703 isa<ConstantPointerNull>(U->getOperand(1))) {
704 assert(isa<GlobalValue>(cast<LoadInst>(U->getOperand(0))(static_cast <bool> (isa<GlobalValue>(cast<LoadInst
>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts
()) && "Should be GlobalVariable") ? void (0) : __assert_fail
("isa<GlobalValue>(cast<LoadInst>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts()) && \"Should be GlobalVariable\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 707, __extension__ __PRETTY_FUNCTION__))
705 ->getPointerOperand()(static_cast <bool> (isa<GlobalValue>(cast<LoadInst
>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts
()) && "Should be GlobalVariable") ? void (0) : __assert_fail
("isa<GlobalValue>(cast<LoadInst>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts()) && \"Should be GlobalVariable\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 707, __extension__ __PRETTY_FUNCTION__))
706 ->stripPointerCasts()) &&(static_cast <bool> (isa<GlobalValue>(cast<LoadInst
>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts
()) && "Should be GlobalVariable") ? void (0) : __assert_fail
("isa<GlobalValue>(cast<LoadInst>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts()) && \"Should be GlobalVariable\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 707, __extension__ __PRETTY_FUNCTION__))
707 "Should be GlobalVariable")(static_cast <bool> (isa<GlobalValue>(cast<LoadInst
>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts
()) && "Should be GlobalVariable") ? void (0) : __assert_fail
("isa<GlobalValue>(cast<LoadInst>(U->getOperand(0)) ->getPointerOperand() ->stripPointerCasts()) && \"Should be GlobalVariable\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 707, __extension__ __PRETTY_FUNCTION__))
;
708 // This and only this kind of non-signed ICmpInst is to be replaced with
709 // the comparing of the value of the created global init bool later in
710 // optimizeGlobalAddressOfMalloc for the global variable.
711 } else {
712 //cerr << "NONTRAPPING USE: " << *U;
713 return false;
714 }
715 }
716 return true;
717}
718
719/// Return true if all uses of any loads from GV will trap if the loaded value
720/// is null. Note that this also permits comparisons of the loaded value
721/// against null, as a special case.
722static bool allUsesOfLoadedValueWillTrapIfNull(const GlobalVariable *GV) {
723 SmallVector<const Value *, 4> Worklist;
724 Worklist.push_back(GV);
725 while (!Worklist.empty()) {
726 const Value *P = Worklist.pop_back_val();
727 for (auto *U : P->users()) {
728 if (auto *LI = dyn_cast<LoadInst>(U)) {
729 SmallPtrSet<const PHINode *, 8> PHIs;
730 if (!AllUsesOfValueWillTrapIfNull(LI, PHIs))
731 return false;
732 } else if (auto *SI = dyn_cast<StoreInst>(U)) {
733 // Ignore stores to the global.
734 if (SI->getPointerOperand() != P)
735 return false;
736 } else if (auto *CE = dyn_cast<ConstantExpr>(U)) {
737 if (CE->stripPointerCasts() != GV)
738 return false;
739 // Check further the ConstantExpr.
740 Worklist.push_back(CE);
741 } else {
742 // We don't know or understand this user, bail out.
743 return false;
744 }
745 }
746 }
747
748 return true;
749}
750
751/// Get all the loads/store uses for global variable \p GV.
752static void allUsesOfLoadAndStores(GlobalVariable *GV,
753 SmallVector<Value *, 4> &Uses) {
754 SmallVector<Value *, 4> Worklist;
755 Worklist.push_back(GV);
756 while (!Worklist.empty()) {
757 auto *P = Worklist.pop_back_val();
758 for (auto *U : P->users()) {
759 if (auto *CE = dyn_cast<ConstantExpr>(U)) {
760 Worklist.push_back(CE);
761 continue;
762 }
763
764 assert((isa<LoadInst>(U) || isa<StoreInst>(U)) &&(static_cast <bool> ((isa<LoadInst>(U) || isa<
StoreInst>(U)) && "Expect only load or store instructions"
) ? void (0) : __assert_fail ("(isa<LoadInst>(U) || isa<StoreInst>(U)) && \"Expect only load or store instructions\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 765, __extension__ __PRETTY_FUNCTION__))
765 "Expect only load or store instructions")(static_cast <bool> ((isa<LoadInst>(U) || isa<
StoreInst>(U)) && "Expect only load or store instructions"
) ? void (0) : __assert_fail ("(isa<LoadInst>(U) || isa<StoreInst>(U)) && \"Expect only load or store instructions\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 765, __extension__ __PRETTY_FUNCTION__))
;
766 Uses.push_back(U);
767 }
768 }
769}
770
771static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) {
772 bool Changed = false;
773 for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) {
774 Instruction *I = cast<Instruction>(*UI++);
775 // Uses are non-trapping if null pointer is considered valid.
776 // Non address-space 0 globals are already pruned by the caller.
777 if (NullPointerIsDefined(I->getFunction()))
778 return false;
779 if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
780 LI->setOperand(0, NewV);
781 Changed = true;
782 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
783 if (SI->getOperand(1) == V) {
784 SI->setOperand(1, NewV);
785 Changed = true;
786 }
787 } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
788 CallBase *CB = cast<CallBase>(I);
789 if (CB->getCalledOperand() == V) {
790 // Calling through the pointer! Turn into a direct call, but be careful
791 // that the pointer is not also being passed as an argument.
792 CB->setCalledOperand(NewV);
793 Changed = true;
794 bool PassedAsArg = false;
795 for (unsigned i = 0, e = CB->arg_size(); i != e; ++i)
796 if (CB->getArgOperand(i) == V) {
797 PassedAsArg = true;
798 CB->setArgOperand(i, NewV);
799 }
800
801 if (PassedAsArg) {
802 // Being passed as an argument also. Be careful to not invalidate UI!
803 UI = V->user_begin();
804 }
805 }
806 } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
807 Changed |= OptimizeAwayTrappingUsesOfValue(CI,
808 ConstantExpr::getCast(CI->getOpcode(),
809 NewV, CI->getType()));
810 if (CI->use_empty()) {
811 Changed = true;
812 CI->eraseFromParent();
813 }
814 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
815 // Should handle GEP here.
816 SmallVector<Constant*, 8> Idxs;
817 Idxs.reserve(GEPI->getNumOperands()-1);
818 for (User::op_iterator i = GEPI->op_begin() + 1, e = GEPI->op_end();
819 i != e; ++i)
820 if (Constant *C = dyn_cast<Constant>(*i))
821 Idxs.push_back(C);
822 else
823 break;
824 if (Idxs.size() == GEPI->getNumOperands()-1)
825 Changed |= OptimizeAwayTrappingUsesOfValue(
826 GEPI, ConstantExpr::getGetElementPtr(GEPI->getSourceElementType(),
827 NewV, Idxs));
828 if (GEPI->use_empty()) {
829 Changed = true;
830 GEPI->eraseFromParent();
831 }
832 }
833 }
834
835 return Changed;
836}
837
838/// The specified global has only one non-null value stored into it. If there
839/// are uses of the loaded value that would trap if the loaded value is
840/// dynamically null, then we know that they cannot be reachable with a null
841/// optimize away the load.
842static bool OptimizeAwayTrappingUsesOfLoads(
843 GlobalVariable *GV, Constant *LV, const DataLayout &DL,
844 function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
845 bool Changed = false;
846
847 // Keep track of whether we are able to remove all the uses of the global
848 // other than the store that defines it.
849 bool AllNonStoreUsesGone = true;
850
851 // Replace all uses of loads with uses of uses of the stored value.
852 for (User *GlobalUser : llvm::make_early_inc_range(GV->users())) {
853 if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) {
854 Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV);
855 // If we were able to delete all uses of the loads
856 if (LI->use_empty()) {
857 LI->eraseFromParent();
858 Changed = true;
859 } else {
860 AllNonStoreUsesGone = false;
861 }
862 } else if (isa<StoreInst>(GlobalUser)) {
863 // Ignore the store that stores "LV" to the global.
864 assert(GlobalUser->getOperand(1) == GV &&(static_cast <bool> (GlobalUser->getOperand(1) == GV
&& "Must be storing *to* the global") ? void (0) : __assert_fail
("GlobalUser->getOperand(1) == GV && \"Must be storing *to* the global\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 865, __extension__ __PRETTY_FUNCTION__))
865 "Must be storing *to* the global")(static_cast <bool> (GlobalUser->getOperand(1) == GV
&& "Must be storing *to* the global") ? void (0) : __assert_fail
("GlobalUser->getOperand(1) == GV && \"Must be storing *to* the global\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 865, __extension__ __PRETTY_FUNCTION__))
;
866 } else {
867 AllNonStoreUsesGone = false;
868
869 // If we get here we could have other crazy uses that are transitively
870 // loaded.
871 assert((isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) ||(static_cast <bool> ((isa<PHINode>(GlobalUser) ||
isa<SelectInst>(GlobalUser) || isa<ConstantExpr>
(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst
>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser))
&& "Only expect load and stores!") ? void (0) : __assert_fail
("(isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser)) && \"Only expect load and stores!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 875, __extension__ __PRETTY_FUNCTION__))
872 isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) ||(static_cast <bool> ((isa<PHINode>(GlobalUser) ||
isa<SelectInst>(GlobalUser) || isa<ConstantExpr>
(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst
>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser))
&& "Only expect load and stores!") ? void (0) : __assert_fail
("(isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser)) && \"Only expect load and stores!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 875, __extension__ __PRETTY_FUNCTION__))
873 isa<BitCastInst>(GlobalUser) ||(static_cast <bool> ((isa<PHINode>(GlobalUser) ||
isa<SelectInst>(GlobalUser) || isa<ConstantExpr>
(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst
>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser))
&& "Only expect load and stores!") ? void (0) : __assert_fail
("(isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser)) && \"Only expect load and stores!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 875, __extension__ __PRETTY_FUNCTION__))
874 isa<GetElementPtrInst>(GlobalUser)) &&(static_cast <bool> ((isa<PHINode>(GlobalUser) ||
isa<SelectInst>(GlobalUser) || isa<ConstantExpr>
(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst
>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser))
&& "Only expect load and stores!") ? void (0) : __assert_fail
("(isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser)) && \"Only expect load and stores!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 875, __extension__ __PRETTY_FUNCTION__))
875 "Only expect load and stores!")(static_cast <bool> ((isa<PHINode>(GlobalUser) ||
isa<SelectInst>(GlobalUser) || isa<ConstantExpr>
(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst
>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser))
&& "Only expect load and stores!") ? void (0) : __assert_fail
("(isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) || isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) || isa<BitCastInst>(GlobalUser) || isa<GetElementPtrInst>(GlobalUser)) && \"Only expect load and stores!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 875, __extension__ __PRETTY_FUNCTION__))
;
876 }
877 }
878
879 if (Changed) {
880 LLVM_DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GVdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: "
<< *GV << "\n"; } } while (false)
881 << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: "
<< *GV << "\n"; } } while (false)
;
882 ++NumGlobUses;
883 }
884
885 // If we nuked all of the loads, then none of the stores are needed either,
886 // nor is the global.
887 if (AllNonStoreUsesGone) {
888 if (isLeakCheckerRoot(GV)) {
889 Changed |= CleanupPointerRootUsers(GV, GetTLI);
890 } else {
891 Changed = true;
892 CleanupConstantGlobalUsers(GV, nullptr, DL, GetTLI);
893 }
894 if (GV->use_empty()) {
895 LLVM_DEBUG(dbgs() << " *** GLOBAL NOW DEAD!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << " *** GLOBAL NOW DEAD!\n"; }
} while (false)
;
896 Changed = true;
897 GV->eraseFromParent();
898 ++NumDeleted;
899 }
900 }
901 return Changed;
902}
903
904/// Walk the use list of V, constant folding all of the instructions that are
905/// foldable.
906static void ConstantPropUsersOf(Value *V, const DataLayout &DL,
907 TargetLibraryInfo *TLI) {
908 for (Value::user_iterator UI = V->user_begin(), E = V->user_end(); UI != E; )
909 if (Instruction *I = dyn_cast<Instruction>(*UI++))
910 if (Constant *NewC = ConstantFoldInstruction(I, DL, TLI)) {
911 I->replaceAllUsesWith(NewC);
912
913 // Advance UI to the next non-I use to avoid invalidating it!
914 // Instructions could multiply use V.
915 while (UI != E && *UI == I)
916 ++UI;
917 if (isInstructionTriviallyDead(I, TLI))
918 I->eraseFromParent();
919 }
920}
921
922/// This function takes the specified global variable, and transforms the
923/// program as if it always contained the result of the specified malloc.
924/// Because it is always the result of the specified malloc, there is no reason
925/// to actually DO the malloc. Instead, turn the malloc into a global, and any
926/// loads of GV as uses of the new global.
927static GlobalVariable *
928OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, CallInst *CI, Type *AllocTy,
929 ConstantInt *NElements, const DataLayout &DL,
930 TargetLibraryInfo *TLI) {
931 LLVM_DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << " CALL = " << *CIdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { errs() << "PROMOTING GLOBAL: " <<
*GV << " CALL = " << *CI << '\n'; } } while
(false)
932 << '\n')do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { errs() << "PROMOTING GLOBAL: " <<
*GV << " CALL = " << *CI << '\n'; } } while
(false)
;
933
934 Type *GlobalType;
935 if (NElements->getZExtValue() == 1)
936 GlobalType = AllocTy;
937 else
938 // If we have an array allocation, the global variable is of an array.
939 GlobalType = ArrayType::get(AllocTy, NElements->getZExtValue());
940
941 // Create the new global variable. The contents of the malloc'd memory is
942 // undefined, so initialize with an undef value.
943 GlobalVariable *NewGV = new GlobalVariable(
944 *GV->getParent(), GlobalType, false, GlobalValue::InternalLinkage,
945 UndefValue::get(GlobalType), GV->getName() + ".body", nullptr,
946 GV->getThreadLocalMode());
947
948 // If there are bitcast users of the malloc (which is typical, usually we have
949 // a malloc + bitcast) then replace them with uses of the new global. Update
950 // other users to use the global as well.
951 BitCastInst *TheBC = nullptr;
952 while (!CI->use_empty()) {
953 Instruction *User = cast<Instruction>(CI->user_back());
954 if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) {
955 if (BCI->getType() == NewGV->getType()) {
956 BCI->replaceAllUsesWith(NewGV);
957 BCI->eraseFromParent();
958 } else {
959 BCI->setOperand(0, NewGV);
960 }
961 } else {
962 if (!TheBC)
963 TheBC = new BitCastInst(NewGV, CI->getType(), "newgv", CI);
964 User->replaceUsesOfWith(CI, TheBC);
965 }
966 }
967
968 SmallPtrSet<Constant *, 1> RepValues;
969 RepValues.insert(NewGV);
970
971 // If there is a comparison against null, we will insert a global bool to
972 // keep track of whether the global was initialized yet or not.
973 GlobalVariable *InitBool =
974 new GlobalVariable(Type::getInt1Ty(GV->getContext()), false,
975 GlobalValue::InternalLinkage,
976 ConstantInt::getFalse(GV->getContext()),
977 GV->getName()+".init", GV->getThreadLocalMode());
978 bool InitBoolUsed = false;
979
980 // Loop over all instruction uses of GV, processing them in turn.
981 SmallVector<Value *, 4> Guses;
982 allUsesOfLoadAndStores(GV, Guses);
983 for (auto *U : Guses) {
984 if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
985 // The global is initialized when the store to it occurs. If the stored
986 // value is null value, the global bool is set to false, otherwise true.
987 new StoreInst(ConstantInt::getBool(
988 GV->getContext(),
989 !isa<ConstantPointerNull>(SI->getValueOperand())),
990 InitBool, false, Align(1), SI->getOrdering(),
991 SI->getSyncScopeID(), SI);
992 SI->eraseFromParent();
993 continue;
994 }
995
996 LoadInst *LI = cast<LoadInst>(U);
997 while (!LI->use_empty()) {
998 Use &LoadUse = *LI->use_begin();
999 ICmpInst *ICI = dyn_cast<ICmpInst>(LoadUse.getUser());
1000 if (!ICI) {
1001 auto *CE = ConstantExpr::getBitCast(NewGV, LI->getType());
1002 RepValues.insert(CE);
1003 LoadUse.set(CE);
1004 continue;
1005 }
1006
1007 // Replace the cmp X, 0 with a use of the bool value.
1008 Value *LV = new LoadInst(InitBool->getValueType(), InitBool,
1009 InitBool->getName() + ".val", false, Align(1),
1010 LI->getOrdering(), LI->getSyncScopeID(), LI);
1011 InitBoolUsed = true;
1012 switch (ICI->getPredicate()) {
1013 default: llvm_unreachable("Unknown ICmp Predicate!")::llvm::llvm_unreachable_internal("Unknown ICmp Predicate!", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1013)
;
1014 case ICmpInst::ICMP_ULT: // X < null -> always false
1015 LV = ConstantInt::getFalse(GV->getContext());
1016 break;
1017 case ICmpInst::ICMP_UGE: // X >= null -> always true
1018 LV = ConstantInt::getTrue(GV->getContext());
1019 break;
1020 case ICmpInst::ICMP_ULE:
1021 case ICmpInst::ICMP_EQ:
1022 LV = BinaryOperator::CreateNot(LV, "notinit", ICI);
1023 break;
1024 case ICmpInst::ICMP_NE:
1025 case ICmpInst::ICMP_UGT:
1026 break; // no change.
1027 }
1028 ICI->replaceAllUsesWith(LV);
1029 ICI->eraseFromParent();
1030 }
1031 LI->eraseFromParent();
1032 }
1033
1034 // If the initialization boolean was used, insert it, otherwise delete it.
1035 if (!InitBoolUsed) {
1036 while (!InitBool->use_empty()) // Delete initializations
1037 cast<StoreInst>(InitBool->user_back())->eraseFromParent();
1038 delete InitBool;
1039 } else
1040 GV->getParent()->getGlobalList().insert(GV->getIterator(), InitBool);
1041
1042 // Now the GV is dead, nuke it and the malloc..
1043 GV->eraseFromParent();
1044 CI->eraseFromParent();
1045
1046 // To further other optimizations, loop over all users of NewGV and try to
1047 // constant prop them. This will promote GEP instructions with constant
1048 // indices into GEP constant-exprs, which will allow global-opt to hack on it.
1049 for (auto *CE : RepValues)
1050 ConstantPropUsersOf(CE, DL, TLI);
1051
1052 return NewGV;
1053}
1054
1055/// Scan the use-list of GV checking to make sure that there are no complex uses
1056/// of GV. We permit simple things like dereferencing the pointer, but not
1057/// storing through the address, unless it is to the specified global.
1058static bool
1059valueIsOnlyUsedLocallyOrStoredToOneGlobal(const CallInst *CI,
1060 const GlobalVariable *GV) {
1061 SmallPtrSet<const Value *, 4> Visited;
1062 SmallVector<const Value *, 4> Worklist;
1063 Worklist.push_back(CI);
1064
1065 while (!Worklist.empty()) {
1066 const Value *V = Worklist.pop_back_val();
1067 if (!Visited.insert(V).second)
1068 continue;
1069
1070 for (const Use &VUse : V->uses()) {
1071 const User *U = VUse.getUser();
1072 if (isa<LoadInst>(U) || isa<CmpInst>(U))
1073 continue; // Fine, ignore.
1074
1075 if (auto *SI = dyn_cast<StoreInst>(U)) {
1076 if (SI->getValueOperand() == V &&
1077 SI->getPointerOperand()->stripPointerCasts() != GV)
1078 return false; // Storing the pointer not into GV... bad.
1079 continue; // Otherwise, storing through it, or storing into GV... fine.
1080 }
1081
1082 if (auto *BCI = dyn_cast<BitCastInst>(U)) {
1083 Worklist.push_back(BCI);
1084 continue;
1085 }
1086
1087 if (auto *GEPI = dyn_cast<GetElementPtrInst>(U)) {
1088 Worklist.push_back(GEPI);
1089 continue;
1090 }
1091
1092 return false;
1093 }
1094 }
1095
1096 return true;
1097}
1098
1099/// This function is called when we see a pointer global variable with a single
1100/// value stored it that is a malloc or cast of malloc.
1101static bool tryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, CallInst *CI,
1102 Type *AllocTy,
1103 AtomicOrdering Ordering,
1104 const DataLayout &DL,
1105 TargetLibraryInfo *TLI) {
1106 // If this is a malloc of an abstract type, don't touch it.
1107 if (!AllocTy->isSized())
1108 return false;
1109
1110 // We can't optimize this global unless all uses of it are *known* to be
1111 // of the malloc value, not of the null initializer value (consider a use
1112 // that compares the global's value against zero to see if the malloc has
1113 // been reached). To do this, we check to see if all uses of the global
1114 // would trap if the global were null: this proves that they must all
1115 // happen after the malloc.
1116 if (!allUsesOfLoadedValueWillTrapIfNull(GV))
1117 return false;
1118
1119 // We can't optimize this if the malloc itself is used in a complex way,
1120 // for example, being stored into multiple globals. This allows the
1121 // malloc to be stored into the specified global, loaded, gep, icmp'd.
1122 // These are all things we could transform to using the global for.
1123 if (!valueIsOnlyUsedLocallyOrStoredToOneGlobal(CI, GV))
1124 return false;
1125
1126 // If we have a global that is only initialized with a fixed size malloc,
1127 // transform the program to use global memory instead of malloc'd memory.
1128 // This eliminates dynamic allocation, avoids an indirection accessing the
1129 // data, and exposes the resultant global to further GlobalOpt.
1130 // We cannot optimize the malloc if we cannot determine malloc array size.
1131 Value *NElems = getMallocArraySize(CI, DL, TLI, true);
1132 if (!NElems)
1133 return false;
1134
1135 if (ConstantInt *NElements = dyn_cast<ConstantInt>(NElems))
1136 // Restrict this transformation to only working on small allocations
1137 // (2048 bytes currently), as we don't want to introduce a 16M global or
1138 // something.
1139 if (NElements->getZExtValue() * DL.getTypeAllocSize(AllocTy) < 2048) {
1140 OptimizeGlobalAddressOfMalloc(GV, CI, AllocTy, NElements, DL, TLI);
1141 return true;
1142 }
1143
1144 return false;
1145}
1146
1147// Try to optimize globals based on the knowledge that only one value (besides
1148// its initializer) is ever stored to the global.
1149static bool
1150optimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal,
1151 AtomicOrdering Ordering, const DataLayout &DL,
1152 function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
1153 // Ignore no-op GEPs and bitcasts.
1154 StoredOnceVal = StoredOnceVal->stripPointerCasts();
1155
1156 // If we are dealing with a pointer global that is initialized to null and
1157 // only has one (non-null) value stored into it, then we can optimize any
1158 // users of the loaded value (often calls and loads) that would trap if the
1159 // value was null.
1160 if (GV->getInitializer()->getType()->isPointerTy() &&
1161 GV->getInitializer()->isNullValue() &&
1162 StoredOnceVal->getType()->isPointerTy() &&
1163 !NullPointerIsDefined(
1164 nullptr /* F */,
1165 GV->getInitializer()->getType()->getPointerAddressSpace())) {
1166 if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
1167 if (GV->getInitializer()->getType() != SOVC->getType())
1168 SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
1169
1170 // Optimize away any trapping uses of the loaded value.
1171 if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, DL, GetTLI))
1172 return true;
1173 } else if (CallInst *CI = extractMallocCall(StoredOnceVal, GetTLI)) {
1174 auto *TLI = &GetTLI(*CI->getFunction());
1175 Type *MallocType = getMallocAllocatedType(CI, TLI);
1176 if (MallocType && tryToOptimizeStoreOfMallocToGlobal(GV, CI, MallocType,
1177 Ordering, DL, TLI))
1178 return true;
1179 }
1180 }
1181
1182 return false;
1183}
1184
1185/// At this point, we have learned that the only two values ever stored into GV
1186/// are its initializer and OtherVal. See if we can shrink the global into a
1187/// boolean and select between the two values whenever it is used. This exposes
1188/// the values to other scalar optimizations.
1189static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) {
1190 Type *GVElType = GV->getValueType();
1191
1192 // If GVElType is already i1, it is already shrunk. If the type of the GV is
1193 // an FP value, pointer or vector, don't do this optimization because a select
1194 // between them is very expensive and unlikely to lead to later
1195 // simplification. In these cases, we typically end up with "cond ? v1 : v2"
1196 // where v1 and v2 both require constant pool loads, a big loss.
1197 if (GVElType == Type::getInt1Ty(GV->getContext()) ||
1198 GVElType->isFloatingPointTy() ||
1199 GVElType->isPointerTy() || GVElType->isVectorTy())
1200 return false;
1201
1202 // Walk the use list of the global seeing if all the uses are load or store.
1203 // If there is anything else, bail out.
1204 for (User *U : GV->users())
1205 if (!isa<LoadInst>(U) && !isa<StoreInst>(U))
1206 return false;
1207
1208 LLVM_DEBUG(dbgs() << " *** SHRINKING TO BOOL: " << *GV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << " *** SHRINKING TO BOOL: "
<< *GV << "\n"; } } while (false)
;
1209
1210 // Create the new global, initializing it to false.
1211 GlobalVariable *NewGV = new GlobalVariable(Type::getInt1Ty(GV->getContext()),
1212 false,
1213 GlobalValue::InternalLinkage,
1214 ConstantInt::getFalse(GV->getContext()),
1215 GV->getName()+".b",
1216 GV->getThreadLocalMode(),
1217 GV->getType()->getAddressSpace());
1218 NewGV->copyAttributesFrom(GV);
1219 GV->getParent()->getGlobalList().insert(GV->getIterator(), NewGV);
1220
1221 Constant *InitVal = GV->getInitializer();
1222 assert(InitVal->getType() != Type::getInt1Ty(GV->getContext()) &&(static_cast <bool> (InitVal->getType() != Type::getInt1Ty
(GV->getContext()) && "No reason to shrink to bool!"
) ? void (0) : __assert_fail ("InitVal->getType() != Type::getInt1Ty(GV->getContext()) && \"No reason to shrink to bool!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1223, __extension__ __PRETTY_FUNCTION__))
1223 "No reason to shrink to bool!")(static_cast <bool> (InitVal->getType() != Type::getInt1Ty
(GV->getContext()) && "No reason to shrink to bool!"
) ? void (0) : __assert_fail ("InitVal->getType() != Type::getInt1Ty(GV->getContext()) && \"No reason to shrink to bool!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1223, __extension__ __PRETTY_FUNCTION__))
;
1224
1225 SmallVector<DIGlobalVariableExpression *, 1> GVs;
1226 GV->getDebugInfo(GVs);
1227
1228 // If initialized to zero and storing one into the global, we can use a cast
1229 // instead of a select to synthesize the desired value.
1230 bool IsOneZero = false;
1231 bool EmitOneOrZero = true;
1232 auto *CI = dyn_cast<ConstantInt>(OtherVal);
1233 if (CI && CI->getValue().getActiveBits() <= 64) {
1234 IsOneZero = InitVal->isNullValue() && CI->isOne();
1235
1236 auto *CIInit = dyn_cast<ConstantInt>(GV->getInitializer());
1237 if (CIInit && CIInit->getValue().getActiveBits() <= 64) {
1238 uint64_t ValInit = CIInit->getZExtValue();
1239 uint64_t ValOther = CI->getZExtValue();
1240 uint64_t ValMinus = ValOther - ValInit;
1241
1242 for(auto *GVe : GVs){
1243 DIGlobalVariable *DGV = GVe->getVariable();
1244 DIExpression *E = GVe->getExpression();
1245 const DataLayout &DL = GV->getParent()->getDataLayout();
1246 unsigned SizeInOctets =
1247 DL.getTypeAllocSizeInBits(NewGV->getValueType()) / 8;
1248
1249 // It is expected that the address of global optimized variable is on
1250 // top of the stack. After optimization, value of that variable will
1251 // be ether 0 for initial value or 1 for other value. The following
1252 // expression should return constant integer value depending on the
1253 // value at global object address:
1254 // val * (ValOther - ValInit) + ValInit:
1255 // DW_OP_deref DW_OP_constu <ValMinus>
1256 // DW_OP_mul DW_OP_constu <ValInit> DW_OP_plus DW_OP_stack_value
1257 SmallVector<uint64_t, 12> Ops = {
1258 dwarf::DW_OP_deref_size, SizeInOctets,
1259 dwarf::DW_OP_constu, ValMinus,
1260 dwarf::DW_OP_mul, dwarf::DW_OP_constu, ValInit,
1261 dwarf::DW_OP_plus};
1262 bool WithStackValue = true;
1263 E = DIExpression::prependOpcodes(E, Ops, WithStackValue);
1264 DIGlobalVariableExpression *DGVE =
1265 DIGlobalVariableExpression::get(NewGV->getContext(), DGV, E);
1266 NewGV->addDebugInfo(DGVE);
1267 }
1268 EmitOneOrZero = false;
1269 }
1270 }
1271
1272 if (EmitOneOrZero) {
1273 // FIXME: This will only emit address for debugger on which will
1274 // be written only 0 or 1.
1275 for(auto *GV : GVs)
1276 NewGV->addDebugInfo(GV);
1277 }
1278
1279 while (!GV->use_empty()) {
1280 Instruction *UI = cast<Instruction>(GV->user_back());
1281 if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
1282 // Change the store into a boolean store.
1283 bool StoringOther = SI->getOperand(0) == OtherVal;
1284 // Only do this if we weren't storing a loaded value.
1285 Value *StoreVal;
1286 if (StoringOther || SI->getOperand(0) == InitVal) {
1287 StoreVal = ConstantInt::get(Type::getInt1Ty(GV->getContext()),
1288 StoringOther);
1289 } else {
1290 // Otherwise, we are storing a previously loaded copy. To do this,
1291 // change the copy from copying the original value to just copying the
1292 // bool.
1293 Instruction *StoredVal = cast<Instruction>(SI->getOperand(0));
1294
1295 // If we've already replaced the input, StoredVal will be a cast or
1296 // select instruction. If not, it will be a load of the original
1297 // global.
1298 if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
1299 assert(LI->getOperand(0) == GV && "Not a copy!")(static_cast <bool> (LI->getOperand(0) == GV &&
"Not a copy!") ? void (0) : __assert_fail ("LI->getOperand(0) == GV && \"Not a copy!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1299, __extension__ __PRETTY_FUNCTION__))
;
1300 // Insert a new load, to preserve the saved value.
1301 StoreVal = new LoadInst(NewGV->getValueType(), NewGV,
1302 LI->getName() + ".b", false, Align(1),
1303 LI->getOrdering(), LI->getSyncScopeID(), LI);
1304 } else {
1305 assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) &&(static_cast <bool> ((isa<CastInst>(StoredVal) ||
isa<SelectInst>(StoredVal)) && "This is not a form that we understand!"
) ? void (0) : __assert_fail ("(isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) && \"This is not a form that we understand!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1306, __extension__ __PRETTY_FUNCTION__))
1306 "This is not a form that we understand!")(static_cast <bool> ((isa<CastInst>(StoredVal) ||
isa<SelectInst>(StoredVal)) && "This is not a form that we understand!"
) ? void (0) : __assert_fail ("(isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) && \"This is not a form that we understand!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1306, __extension__ __PRETTY_FUNCTION__))
;
1307 StoreVal = StoredVal->getOperand(0);
1308 assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!")(static_cast <bool> (isa<LoadInst>(StoreVal) &&
"Not a load of NewGV!") ? void (0) : __assert_fail ("isa<LoadInst>(StoreVal) && \"Not a load of NewGV!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1308, __extension__ __PRETTY_FUNCTION__))
;
1309 }
1310 }
1311 StoreInst *NSI =
1312 new StoreInst(StoreVal, NewGV, false, Align(1), SI->getOrdering(),
1313 SI->getSyncScopeID(), SI);
1314 NSI->setDebugLoc(SI->getDebugLoc());
1315 } else {
1316 // Change the load into a load of bool then a select.
1317 LoadInst *LI = cast<LoadInst>(UI);
1318 LoadInst *NLI = new LoadInst(NewGV->getValueType(), NewGV,
1319 LI->getName() + ".b", false, Align(1),
1320 LI->getOrdering(), LI->getSyncScopeID(), LI);
1321 Instruction *NSI;
1322 if (IsOneZero)
1323 NSI = new ZExtInst(NLI, LI->getType(), "", LI);
1324 else
1325 NSI = SelectInst::Create(NLI, OtherVal, InitVal, "", LI);
1326 NSI->takeName(LI);
1327 // Since LI is split into two instructions, NLI and NSI both inherit the
1328 // same DebugLoc
1329 NLI->setDebugLoc(LI->getDebugLoc());
1330 NSI->setDebugLoc(LI->getDebugLoc());
1331 LI->replaceAllUsesWith(NSI);
1332 }
1333 UI->eraseFromParent();
1334 }
1335
1336 // Retain the name of the old global variable. People who are debugging their
1337 // programs may expect these variables to be named the same.
1338 NewGV->takeName(GV);
1339 GV->eraseFromParent();
1340 return true;
1341}
1342
1343static bool deleteIfDead(
1344 GlobalValue &GV, SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
1345 GV.removeDeadConstantUsers();
1346
1347 if (!GV.isDiscardableIfUnused() && !GV.isDeclaration())
1348 return false;
1349
1350 if (const Comdat *C = GV.getComdat())
1351 if (!GV.hasLocalLinkage() && NotDiscardableComdats.count(C))
1352 return false;
1353
1354 bool Dead;
1355 if (auto *F = dyn_cast<Function>(&GV))
1356 Dead = (F->isDeclaration() && F->use_empty()) || F->isDefTriviallyDead();
1357 else
1358 Dead = GV.use_empty();
1359 if (!Dead)
1360 return false;
1361
1362 LLVM_DEBUG(dbgs() << "GLOBAL DEAD: " << GV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "GLOBAL DEAD: " << GV <<
"\n"; } } while (false)
;
1363 GV.eraseFromParent();
1364 ++NumDeleted;
1365 return true;
1366}
1367
1368static bool isPointerValueDeadOnEntryToFunction(
1369 const Function *F, GlobalValue *GV,
1370 function_ref<DominatorTree &(Function &)> LookupDomTree) {
1371 // Find all uses of GV. We expect them all to be in F, and if we can't
1372 // identify any of the uses we bail out.
1373 //
1374 // On each of these uses, identify if the memory that GV points to is
1375 // used/required/live at the start of the function. If it is not, for example
1376 // if the first thing the function does is store to the GV, the GV can
1377 // possibly be demoted.
1378 //
1379 // We don't do an exhaustive search for memory operations - simply look
1380 // through bitcasts as they're quite common and benign.
1381 const DataLayout &DL = GV->getParent()->getDataLayout();
1382 SmallVector<LoadInst *, 4> Loads;
1383 SmallVector<StoreInst *, 4> Stores;
1384 for (auto *U : GV->users()) {
1385 if (Operator::getOpcode(U) == Instruction::BitCast) {
1386 for (auto *UU : U->users()) {
1387 if (auto *LI = dyn_cast<LoadInst>(UU))
1388 Loads.push_back(LI);
1389 else if (auto *SI = dyn_cast<StoreInst>(UU))
1390 Stores.push_back(SI);
1391 else
1392 return false;
1393 }
1394 continue;
1395 }
1396
1397 Instruction *I = dyn_cast<Instruction>(U);
1398 if (!I)
1399 return false;
1400 assert(I->getParent()->getParent() == F)(static_cast <bool> (I->getParent()->getParent() ==
F) ? void (0) : __assert_fail ("I->getParent()->getParent() == F"
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1400, __extension__ __PRETTY_FUNCTION__))
;
1401
1402 if (auto *LI = dyn_cast<LoadInst>(I))
1403 Loads.push_back(LI);
1404 else if (auto *SI = dyn_cast<StoreInst>(I))
1405 Stores.push_back(SI);
1406 else
1407 return false;
1408 }
1409
1410 // We have identified all uses of GV into loads and stores. Now check if all
1411 // of them are known not to depend on the value of the global at the function
1412 // entry point. We do this by ensuring that every load is dominated by at
1413 // least one store.
1414 auto &DT = LookupDomTree(*const_cast<Function *>(F));
1415
1416 // The below check is quadratic. Check we're not going to do too many tests.
1417 // FIXME: Even though this will always have worst-case quadratic time, we
1418 // could put effort into minimizing the average time by putting stores that
1419 // have been shown to dominate at least one load at the beginning of the
1420 // Stores array, making subsequent dominance checks more likely to succeed
1421 // early.
1422 //
1423 // The threshold here is fairly large because global->local demotion is a
1424 // very powerful optimization should it fire.
1425 const unsigned Threshold = 100;
1426 if (Loads.size() * Stores.size() > Threshold)
1427 return false;
1428
1429 for (auto *L : Loads) {
1430 auto *LTy = L->getType();
1431 if (none_of(Stores, [&](const StoreInst *S) {
1432 auto *STy = S->getValueOperand()->getType();
1433 // The load is only dominated by the store if DomTree says so
1434 // and the number of bits loaded in L is less than or equal to
1435 // the number of bits stored in S.
1436 return DT.dominates(S, L) &&
1437 DL.getTypeStoreSize(LTy).getFixedSize() <=
1438 DL.getTypeStoreSize(STy).getFixedSize();
1439 }))
1440 return false;
1441 }
1442 // All loads have known dependences inside F, so the global can be localized.
1443 return true;
1444}
1445
1446/// C may have non-instruction users. Can all of those users be turned into
1447/// instructions?
1448static bool allNonInstructionUsersCanBeMadeInstructions(Constant *C) {
1449 // We don't do this exhaustively. The most common pattern that we really need
1450 // to care about is a constant GEP or constant bitcast - so just looking
1451 // through one single ConstantExpr.
1452 //
1453 // The set of constants that this function returns true for must be able to be
1454 // handled by makeAllConstantUsesInstructions.
1455 for (auto *U : C->users()) {
1456 if (isa<Instruction>(U))
1457 continue;
1458 if (!isa<ConstantExpr>(U))
1459 // Non instruction, non-constantexpr user; cannot convert this.
1460 return false;
1461 for (auto *UU : U->users())
1462 if (!isa<Instruction>(UU))
1463 // A constantexpr used by another constant. We don't try and recurse any
1464 // further but just bail out at this point.
1465 return false;
1466 }
1467
1468 return true;
1469}
1470
1471/// C may have non-instruction users, and
1472/// allNonInstructionUsersCanBeMadeInstructions has returned true. Convert the
1473/// non-instruction users to instructions.
1474static void makeAllConstantUsesInstructions(Constant *C) {
1475 SmallVector<ConstantExpr*,4> Users;
1476 for (auto *U : C->users()) {
1477 if (isa<ConstantExpr>(U))
1478 Users.push_back(cast<ConstantExpr>(U));
1479 else
1480 // We should never get here; allNonInstructionUsersCanBeMadeInstructions
1481 // should not have returned true for C.
1482 assert((static_cast <bool> (isa<Instruction>(U) &&
"Can't transform non-constantexpr non-instruction to instruction!"
) ? void (0) : __assert_fail ("isa<Instruction>(U) && \"Can't transform non-constantexpr non-instruction to instruction!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1484, __extension__ __PRETTY_FUNCTION__))
1483 isa<Instruction>(U) &&(static_cast <bool> (isa<Instruction>(U) &&
"Can't transform non-constantexpr non-instruction to instruction!"
) ? void (0) : __assert_fail ("isa<Instruction>(U) && \"Can't transform non-constantexpr non-instruction to instruction!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1484, __extension__ __PRETTY_FUNCTION__))
1484 "Can't transform non-constantexpr non-instruction to instruction!")(static_cast <bool> (isa<Instruction>(U) &&
"Can't transform non-constantexpr non-instruction to instruction!"
) ? void (0) : __assert_fail ("isa<Instruction>(U) && \"Can't transform non-constantexpr non-instruction to instruction!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1484, __extension__ __PRETTY_FUNCTION__))
;
1485 }
1486
1487 SmallVector<Value*,4> UUsers;
1488 for (auto *U : Users) {
1489 UUsers.clear();
1490 append_range(UUsers, U->users());
1491 for (auto *UU : UUsers) {
1492 Instruction *UI = cast<Instruction>(UU);
1493 Instruction *NewU = U->getAsInstruction();
1494 NewU->insertBefore(UI);
1495 UI->replaceUsesOfWith(U, NewU);
1496 }
1497 // We've replaced all the uses, so destroy the constant. (destroyConstant
1498 // will update value handles and metadata.)
1499 U->destroyConstant();
1500 }
1501}
1502
1503/// Analyze the specified global variable and optimize
1504/// it if possible. If we make a change, return true.
1505static bool
1506processInternalGlobal(GlobalVariable *GV, const GlobalStatus &GS,
1507 function_ref<TargetTransformInfo &(Function &)> GetTTI,
1508 function_ref<TargetLibraryInfo &(Function &)> GetTLI,
1509 function_ref<DominatorTree &(Function &)> LookupDomTree) {
1510 auto &DL = GV->getParent()->getDataLayout();
1511 // If this is a first class global and has only one accessing function and
1512 // this function is non-recursive, we replace the global with a local alloca
1513 // in this function.
1514 //
1515 // NOTE: It doesn't make sense to promote non-single-value types since we
1516 // are just replacing static memory to stack memory.
1517 //
1518 // If the global is in different address space, don't bring it to stack.
1519 if (!GS.HasMultipleAccessingFunctions &&
1520 GS.AccessingFunction &&
1521 GV->getValueType()->isSingleValueType() &&
1522 GV->getType()->getAddressSpace() == 0 &&
1523 !GV->isExternallyInitialized() &&
1524 allNonInstructionUsersCanBeMadeInstructions(GV) &&
1525 GS.AccessingFunction->doesNotRecurse() &&
1526 isPointerValueDeadOnEntryToFunction(GS.AccessingFunction, GV,
1527 LookupDomTree)) {
1528 const DataLayout &DL = GV->getParent()->getDataLayout();
1529
1530 LLVM_DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "LOCALIZING GLOBAL: " <<
*GV << "\n"; } } while (false)
;
1531 Instruction &FirstI = const_cast<Instruction&>(*GS.AccessingFunction
1532 ->getEntryBlock().begin());
1533 Type *ElemTy = GV->getValueType();
1534 // FIXME: Pass Global's alignment when globals have alignment
1535 AllocaInst *Alloca = new AllocaInst(ElemTy, DL.getAllocaAddrSpace(), nullptr,
1536 GV->getName(), &FirstI);
1537 if (!isa<UndefValue>(GV->getInitializer()))
1538 new StoreInst(GV->getInitializer(), Alloca, &FirstI);
1539
1540 makeAllConstantUsesInstructions(GV);
1541
1542 GV->replaceAllUsesWith(Alloca);
1543 GV->eraseFromParent();
1544 ++NumLocalized;
1545 return true;
1546 }
1547
1548 bool Changed = false;
1549
1550 // If the global is never loaded (but may be stored to), it is dead.
1551 // Delete it now.
1552 if (!GS.IsLoaded) {
1553 LLVM_DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "GLOBAL NEVER LOADED: " <<
*GV << "\n"; } } while (false)
;
1554
1555 if (isLeakCheckerRoot(GV)) {
1556 // Delete any constant stores to the global.
1557 Changed = CleanupPointerRootUsers(GV, GetTLI);
1558 } else {
1559 // Delete any stores we can find to the global. We may not be able to
1560 // make it completely dead though.
1561 Changed =
1562 CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, GetTLI);
1563 }
1564
1565 // If the global is dead now, delete it.
1566 if (GV->use_empty()) {
1567 GV->eraseFromParent();
1568 ++NumDeleted;
1569 Changed = true;
1570 }
1571 return Changed;
1572
1573 }
1574 if (GS.StoredType <= GlobalStatus::InitializerStored) {
1575 LLVM_DEBUG(dbgs() << "MARKING CONSTANT: " << *GV << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "MARKING CONSTANT: " <<
*GV << "\n"; } } while (false)
;
1576
1577 // Don't actually mark a global constant if it's atomic because atomic loads
1578 // are implemented by a trivial cmpxchg in some edge-cases and that usually
1579 // requires write access to the variable even if it's not actually changed.
1580 if (GS.Ordering == AtomicOrdering::NotAtomic) {
1581 assert(!GV->isConstant() && "Expected a non-constant global")(static_cast <bool> (!GV->isConstant() && "Expected a non-constant global"
) ? void (0) : __assert_fail ("!GV->isConstant() && \"Expected a non-constant global\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1581, __extension__ __PRETTY_FUNCTION__))
;
1582 GV->setConstant(true);
1583 Changed = true;
1584 }
1585
1586 // Clean up any obviously simplifiable users now.
1587 Changed |= CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, GetTLI);
1588
1589 // If the global is dead now, just nuke it.
1590 if (GV->use_empty()) {
1591 LLVM_DEBUG(dbgs() << " *** Marking constant allowed us to simplify "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << " *** Marking constant allowed us to simplify "
<< "all users and delete global!\n"; } } while (false)
1592 << "all users and delete global!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << " *** Marking constant allowed us to simplify "
<< "all users and delete global!\n"; } } while (false)
;
1593 GV->eraseFromParent();
1594 ++NumDeleted;
1595 return true;
1596 }
1597
1598 // Fall through to the next check; see if we can optimize further.
1599 ++NumMarked;
1600 }
1601 if (!GV->getInitializer()->getType()->isSingleValueType()) {
1602 const DataLayout &DL = GV->getParent()->getDataLayout();
1603 if (SRAGlobal(GV, DL))
1604 return true;
1605 }
1606 Value *StoredOnceValue = GS.getStoredOnceValue();
1607 if (GS.StoredType == GlobalStatus::StoredOnce && StoredOnceValue) {
1608 // Avoid speculating constant expressions that might trap (div/rem).
1609 auto *SOVConstant = dyn_cast<Constant>(StoredOnceValue);
1610 if (SOVConstant && SOVConstant->canTrap())
1611 return Changed;
1612
1613 Function &StoreFn =
1614 const_cast<Function &>(*GS.StoredOnceStore->getFunction());
1615 bool CanHaveNonUndefGlobalInitializer =
1616 GetTTI(StoreFn).canHaveNonUndefGlobalInitializerInAddressSpace(
1617 GV->getType()->getAddressSpace());
1618 // If the initial value for the global was an undef value, and if only
1619 // one other value was stored into it, we can just change the
1620 // initializer to be the stored value, then delete all stores to the
1621 // global. This allows us to mark it constant.
1622 // This is restricted to address spaces that allow globals to have
1623 // initializers. NVPTX, for example, does not support initializers for
1624 // shared memory (AS 3).
1625 if (SOVConstant && SOVConstant->getType() == GV->getValueType() &&
1626 isa<UndefValue>(GV->getInitializer()) &&
1627 CanHaveNonUndefGlobalInitializer) {
1628 // Change the initial value here.
1629 GV->setInitializer(SOVConstant);
1630
1631 // Clean up any obviously simplifiable users now.
1632 CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, GetTLI);
1633
1634 if (GV->use_empty()) {
1635 LLVM_DEBUG(dbgs() << " *** Substituting initializer allowed us to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << " *** Substituting initializer allowed us to "
<< "simplify all users and delete global!\n"; } } while
(false)
1636 << "simplify all users and delete global!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << " *** Substituting initializer allowed us to "
<< "simplify all users and delete global!\n"; } } while
(false)
;
1637 GV->eraseFromParent();
1638 ++NumDeleted;
1639 }
1640 ++NumSubstitute;
1641 return true;
1642 }
1643
1644 // Try to optimize globals based on the knowledge that only one value
1645 // (besides its initializer) is ever stored to the global.
1646 if (optimizeOnceStoredGlobal(GV, StoredOnceValue, GS.Ordering, DL, GetTLI))
1647 return true;
1648
1649 // Otherwise, if the global was not a boolean, we can shrink it to be a
1650 // boolean. Skip this optimization for AS that doesn't allow an initializer.
1651 if (SOVConstant && GS.Ordering == AtomicOrdering::NotAtomic &&
1652 (!isa<UndefValue>(GV->getInitializer()) ||
1653 CanHaveNonUndefGlobalInitializer)) {
1654 if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) {
1655 ++NumShrunkToBool;
1656 return true;
1657 }
1658 }
1659 }
1660
1661 return Changed;
1662}
1663
1664/// Analyze the specified global variable and optimize it if possible. If we
1665/// make a change, return true.
1666static bool
1667processGlobal(GlobalValue &GV,
1668 function_ref<TargetTransformInfo &(Function &)> GetTTI,
1669 function_ref<TargetLibraryInfo &(Function &)> GetTLI,
1670 function_ref<DominatorTree &(Function &)> LookupDomTree) {
1671 if (GV.getName().startswith("llvm."))
1672 return false;
1673
1674 GlobalStatus GS;
1675
1676 if (GlobalStatus::analyzeGlobal(&GV, GS))
1677 return false;
1678
1679 bool Changed = false;
1680 if (!GS.IsCompared && !GV.hasGlobalUnnamedAddr()) {
1681 auto NewUnnamedAddr = GV.hasLocalLinkage() ? GlobalValue::UnnamedAddr::Global
1682 : GlobalValue::UnnamedAddr::Local;
1683 if (NewUnnamedAddr != GV.getUnnamedAddr()) {
1684 GV.setUnnamedAddr(NewUnnamedAddr);
1685 NumUnnamed++;
1686 Changed = true;
1687 }
1688 }
1689
1690 // Do more involved optimizations if the global is internal.
1691 if (!GV.hasLocalLinkage())
1692 return Changed;
1693
1694 auto *GVar = dyn_cast<GlobalVariable>(&GV);
1695 if (!GVar)
1696 return Changed;
1697
1698 if (GVar->isConstant() || !GVar->hasInitializer())
1699 return Changed;
1700
1701 return processInternalGlobal(GVar, GS, GetTTI, GetTLI, LookupDomTree) ||
1702 Changed;
1703}
1704
1705/// Walk all of the direct calls of the specified function, changing them to
1706/// FastCC.
1707static void ChangeCalleesToFastCall(Function *F) {
1708 for (User *U : F->users()) {
1709 if (isa<BlockAddress>(U))
1710 continue;
1711 cast<CallBase>(U)->setCallingConv(CallingConv::Fast);
1712 }
1713}
1714
1715static AttributeList StripAttr(LLVMContext &C, AttributeList Attrs,
1716 Attribute::AttrKind A) {
1717 unsigned AttrIndex;
1718 if (Attrs.hasAttrSomewhere(A, &AttrIndex))
1719 return Attrs.removeAttributeAtIndex(C, AttrIndex, A);
1720 return Attrs;
1721}
1722
1723static void RemoveAttribute(Function *F, Attribute::AttrKind A) {
1724 F->setAttributes(StripAttr(F->getContext(), F->getAttributes(), A));
1725 for (User *U : F->users()) {
1726 if (isa<BlockAddress>(U))
1727 continue;
1728 CallBase *CB = cast<CallBase>(U);
1729 CB->setAttributes(StripAttr(F->getContext(), CB->getAttributes(), A));
1730 }
1731}
1732
1733/// Return true if this is a calling convention that we'd like to change. The
1734/// idea here is that we don't want to mess with the convention if the user
1735/// explicitly requested something with performance implications like coldcc,
1736/// GHC, or anyregcc.
1737static bool hasChangeableCC(Function *F) {
1738 CallingConv::ID CC = F->getCallingConv();
1739
1740 // FIXME: Is it worth transforming x86_stdcallcc and x86_fastcallcc?
1741 if (CC != CallingConv::C && CC != CallingConv::X86_ThisCall)
1742 return false;
1743
1744 // FIXME: Change CC for the whole chain of musttail calls when possible.
1745 //
1746 // Can't change CC of the function that either has musttail calls, or is a
1747 // musttail callee itself
1748 for (User *U : F->users()) {
1749 if (isa<BlockAddress>(U))
1750 continue;
1751 CallInst* CI = dyn_cast<CallInst>(U);
1752 if (!CI)
1753 continue;
1754
1755 if (CI->isMustTailCall())
1756 return false;
1757 }
1758
1759 for (BasicBlock &BB : *F)
1760 if (BB.getTerminatingMustTailCall())
1761 return false;
1762
1763 return true;
1764}
1765
1766/// Return true if the block containing the call site has a BlockFrequency of
1767/// less than ColdCCRelFreq% of the entry block.
1768static bool isColdCallSite(CallBase &CB, BlockFrequencyInfo &CallerBFI) {
1769 const BranchProbability ColdProb(ColdCCRelFreq, 100);
1770 auto *CallSiteBB = CB.getParent();
1771 auto CallSiteFreq = CallerBFI.getBlockFreq(CallSiteBB);
1772 auto CallerEntryFreq =
1773 CallerBFI.getBlockFreq(&(CB.getCaller()->getEntryBlock()));
1774 return CallSiteFreq < CallerEntryFreq * ColdProb;
1775}
1776
1777// This function checks if the input function F is cold at all call sites. It
1778// also looks each call site's containing function, returning false if the
1779// caller function contains other non cold calls. The input vector AllCallsCold
1780// contains a list of functions that only have call sites in cold blocks.
1781static bool
1782isValidCandidateForColdCC(Function &F,
1783 function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
1784 const std::vector<Function *> &AllCallsCold) {
1785
1786 if (F.user_empty())
1787 return false;
1788
1789 for (User *U : F.users()) {
1790 if (isa<BlockAddress>(U))
1791 continue;
1792
1793 CallBase &CB = cast<CallBase>(*U);
1794 Function *CallerFunc = CB.getParent()->getParent();
1795 BlockFrequencyInfo &CallerBFI = GetBFI(*CallerFunc);
1796 if (!isColdCallSite(CB, CallerBFI))
1797 return false;
1798 if (!llvm::is_contained(AllCallsCold, CallerFunc))
1799 return false;
1800 }
1801 return true;
1802}
1803
1804static void changeCallSitesToColdCC(Function *F) {
1805 for (User *U : F->users()) {
1806 if (isa<BlockAddress>(U))
1807 continue;
1808 cast<CallBase>(U)->setCallingConv(CallingConv::Cold);
1809 }
1810}
1811
1812// This function iterates over all the call instructions in the input Function
1813// and checks that all call sites are in cold blocks and are allowed to use the
1814// coldcc calling convention.
1815static bool
1816hasOnlyColdCalls(Function &F,
1817 function_ref<BlockFrequencyInfo &(Function &)> GetBFI) {
1818 for (BasicBlock &BB : F) {
1819 for (Instruction &I : BB) {
1820 if (CallInst *CI = dyn_cast<CallInst>(&I)) {
1821 // Skip over isline asm instructions since they aren't function calls.
1822 if (CI->isInlineAsm())
1823 continue;
1824 Function *CalledFn = CI->getCalledFunction();
1825 if (!CalledFn)
1826 return false;
1827 if (!CalledFn->hasLocalLinkage())
1828 return false;
1829 // Skip over instrinsics since they won't remain as function calls.
1830 if (CalledFn->getIntrinsicID() != Intrinsic::not_intrinsic)
1831 continue;
1832 // Check if it's valid to use coldcc calling convention.
1833 if (!hasChangeableCC(CalledFn) || CalledFn->isVarArg() ||
1834 CalledFn->hasAddressTaken())
1835 return false;
1836 BlockFrequencyInfo &CallerBFI = GetBFI(F);
1837 if (!isColdCallSite(*CI, CallerBFI))
1838 return false;
1839 }
1840 }
1841 }
1842 return true;
1843}
1844
1845static bool hasMustTailCallers(Function *F) {
1846 for (User *U : F->users()) {
1847 CallBase *CB = dyn_cast<CallBase>(U);
1848 if (!CB) {
1849 assert(isa<BlockAddress>(U) &&(static_cast <bool> (isa<BlockAddress>(U) &&
"Expected either CallBase or BlockAddress") ? void (0) : __assert_fail
("isa<BlockAddress>(U) && \"Expected either CallBase or BlockAddress\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1850, __extension__ __PRETTY_FUNCTION__))
1850 "Expected either CallBase or BlockAddress")(static_cast <bool> (isa<BlockAddress>(U) &&
"Expected either CallBase or BlockAddress") ? void (0) : __assert_fail
("isa<BlockAddress>(U) && \"Expected either CallBase or BlockAddress\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1850, __extension__ __PRETTY_FUNCTION__))
;
1851 continue;
1852 }
1853 if (CB->isMustTailCall())
1854 return true;
1855 }
1856 return false;
1857}
1858
1859static bool hasInvokeCallers(Function *F) {
1860 for (User *U : F->users())
1861 if (isa<InvokeInst>(U))
1862 return true;
1863 return false;
1864}
1865
1866static void RemovePreallocated(Function *F) {
1867 RemoveAttribute(F, Attribute::Preallocated);
1868
1869 auto *M = F->getParent();
1870
1871 IRBuilder<> Builder(M->getContext());
1872
1873 // Cannot modify users() while iterating over it, so make a copy.
1874 SmallVector<User *, 4> PreallocatedCalls(F->users());
1875 for (User *U : PreallocatedCalls) {
1876 CallBase *CB = dyn_cast<CallBase>(U);
1877 if (!CB)
1878 continue;
1879
1880 assert((static_cast <bool> (!CB->isMustTailCall() &&
"Shouldn't call RemotePreallocated() on a musttail preallocated call"
) ? void (0) : __assert_fail ("!CB->isMustTailCall() && \"Shouldn't call RemotePreallocated() on a musttail preallocated call\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1882, __extension__ __PRETTY_FUNCTION__))
1881 !CB->isMustTailCall() &&(static_cast <bool> (!CB->isMustTailCall() &&
"Shouldn't call RemotePreallocated() on a musttail preallocated call"
) ? void (0) : __assert_fail ("!CB->isMustTailCall() && \"Shouldn't call RemotePreallocated() on a musttail preallocated call\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1882, __extension__ __PRETTY_FUNCTION__))
1882 "Shouldn't call RemotePreallocated() on a musttail preallocated call")(static_cast <bool> (!CB->isMustTailCall() &&
"Shouldn't call RemotePreallocated() on a musttail preallocated call"
) ? void (0) : __assert_fail ("!CB->isMustTailCall() && \"Shouldn't call RemotePreallocated() on a musttail preallocated call\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1882, __extension__ __PRETTY_FUNCTION__))
;
1883 // Create copy of call without "preallocated" operand bundle.
1884 SmallVector<OperandBundleDef, 1> OpBundles;
1885 CB->getOperandBundlesAsDefs(OpBundles);
1886 CallBase *PreallocatedSetup = nullptr;
1887 for (auto *It = OpBundles.begin(); It != OpBundles.end(); ++It) {
1888 if (It->getTag() == "preallocated") {
1889 PreallocatedSetup = cast<CallBase>(*It->input_begin());
1890 OpBundles.erase(It);
1891 break;
1892 }
1893 }
1894 assert(PreallocatedSetup && "Did not find preallocated bundle")(static_cast <bool> (PreallocatedSetup && "Did not find preallocated bundle"
) ? void (0) : __assert_fail ("PreallocatedSetup && \"Did not find preallocated bundle\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1894, __extension__ __PRETTY_FUNCTION__))
;
1895 uint64_t ArgCount =
1896 cast<ConstantInt>(PreallocatedSetup->getArgOperand(0))->getZExtValue();
1897
1898 assert((isa<CallInst>(CB) || isa<InvokeInst>(CB)) &&(static_cast <bool> ((isa<CallInst>(CB) || isa<
InvokeInst>(CB)) && "Unknown indirect call type") ?
void (0) : __assert_fail ("(isa<CallInst>(CB) || isa<InvokeInst>(CB)) && \"Unknown indirect call type\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1899, __extension__ __PRETTY_FUNCTION__))
1899 "Unknown indirect call type")(static_cast <bool> ((isa<CallInst>(CB) || isa<
InvokeInst>(CB)) && "Unknown indirect call type") ?
void (0) : __assert_fail ("(isa<CallInst>(CB) || isa<InvokeInst>(CB)) && \"Unknown indirect call type\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1899, __extension__ __PRETTY_FUNCTION__))
;
1900 CallBase *NewCB = CallBase::Create(CB, OpBundles, CB);
1901 CB->replaceAllUsesWith(NewCB);
1902 NewCB->takeName(CB);
1903 CB->eraseFromParent();
1904
1905 Builder.SetInsertPoint(PreallocatedSetup);
1906 auto *StackSave =
1907 Builder.CreateCall(Intrinsic::getDeclaration(M, Intrinsic::stacksave));
1908
1909 Builder.SetInsertPoint(NewCB->getNextNonDebugInstruction());
1910 Builder.CreateCall(Intrinsic::getDeclaration(M, Intrinsic::stackrestore),
1911 StackSave);
1912
1913 // Replace @llvm.call.preallocated.arg() with alloca.
1914 // Cannot modify users() while iterating over it, so make a copy.
1915 // @llvm.call.preallocated.arg() can be called with the same index multiple
1916 // times. So for each @llvm.call.preallocated.arg(), we see if we have
1917 // already created a Value* for the index, and if not, create an alloca and
1918 // bitcast right after the @llvm.call.preallocated.setup() so that it
1919 // dominates all uses.
1920 SmallVector<Value *, 2> ArgAllocas(ArgCount);
1921 SmallVector<User *, 2> PreallocatedArgs(PreallocatedSetup->users());
1922 for (auto *User : PreallocatedArgs) {
1923 auto *UseCall = cast<CallBase>(User);
1924 assert(UseCall->getCalledFunction()->getIntrinsicID() ==(static_cast <bool> (UseCall->getCalledFunction()->
getIntrinsicID() == Intrinsic::call_preallocated_arg &&
"preallocated token use was not a llvm.call.preallocated.arg"
) ? void (0) : __assert_fail ("UseCall->getCalledFunction()->getIntrinsicID() == Intrinsic::call_preallocated_arg && \"preallocated token use was not a llvm.call.preallocated.arg\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1926, __extension__ __PRETTY_FUNCTION__))
1925 Intrinsic::call_preallocated_arg &&(static_cast <bool> (UseCall->getCalledFunction()->
getIntrinsicID() == Intrinsic::call_preallocated_arg &&
"preallocated token use was not a llvm.call.preallocated.arg"
) ? void (0) : __assert_fail ("UseCall->getCalledFunction()->getIntrinsicID() == Intrinsic::call_preallocated_arg && \"preallocated token use was not a llvm.call.preallocated.arg\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1926, __extension__ __PRETTY_FUNCTION__))
1926 "preallocated token use was not a llvm.call.preallocated.arg")(static_cast <bool> (UseCall->getCalledFunction()->
getIntrinsicID() == Intrinsic::call_preallocated_arg &&
"preallocated token use was not a llvm.call.preallocated.arg"
) ? void (0) : __assert_fail ("UseCall->getCalledFunction()->getIntrinsicID() == Intrinsic::call_preallocated_arg && \"preallocated token use was not a llvm.call.preallocated.arg\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 1926, __extension__ __PRETTY_FUNCTION__))
;
1927 uint64_t AllocArgIndex =
1928 cast<ConstantInt>(UseCall->getArgOperand(1))->getZExtValue();
1929 Value *AllocaReplacement = ArgAllocas[AllocArgIndex];
1930 if (!AllocaReplacement) {
1931 auto AddressSpace = UseCall->getType()->getPointerAddressSpace();
1932 auto *ArgType =
1933 UseCall->getFnAttr(Attribute::Preallocated).getValueAsType();
1934 auto *InsertBefore = PreallocatedSetup->getNextNonDebugInstruction();
1935 Builder.SetInsertPoint(InsertBefore);
1936 auto *Alloca =
1937 Builder.CreateAlloca(ArgType, AddressSpace, nullptr, "paarg");
1938 auto *BitCast = Builder.CreateBitCast(
1939 Alloca, Type::getInt8PtrTy(M->getContext()), UseCall->getName());
1940 ArgAllocas[AllocArgIndex] = BitCast;
1941 AllocaReplacement = BitCast;
1942 }
1943
1944 UseCall->replaceAllUsesWith(AllocaReplacement);
1945 UseCall->eraseFromParent();
1946 }
1947 // Remove @llvm.call.preallocated.setup().
1948 cast<Instruction>(PreallocatedSetup)->eraseFromParent();
1949 }
1950}
1951
1952static bool
1953OptimizeFunctions(Module &M,
1954 function_ref<TargetLibraryInfo &(Function &)> GetTLI,
1955 function_ref<TargetTransformInfo &(Function &)> GetTTI,
1956 function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
1957 function_ref<DominatorTree &(Function &)> LookupDomTree,
1958 SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
1959
1960 bool Changed = false;
1961
1962 std::vector<Function *> AllCallsCold;
1963 for (Function &F : llvm::make_early_inc_range(M))
1964 if (hasOnlyColdCalls(F, GetBFI))
1965 AllCallsCold.push_back(&F);
1966
1967 // Optimize functions.
1968 for (Function &F : llvm::make_early_inc_range(M)) {
1969 // Don't perform global opt pass on naked functions; we don't want fast
1970 // calling conventions for naked functions.
1971 if (F.hasFnAttribute(Attribute::Naked))
1972 continue;
1973
1974 // Functions without names cannot be referenced outside this module.
1975 if (!F.hasName() && !F.isDeclaration() && !F.hasLocalLinkage())
1976 F.setLinkage(GlobalValue::InternalLinkage);
1977
1978 if (deleteIfDead(F, NotDiscardableComdats)) {
1979 Changed = true;
1980 continue;
1981 }
1982
1983 // LLVM's definition of dominance allows instructions that are cyclic
1984 // in unreachable blocks, e.g.:
1985 // %pat = select i1 %condition, @global, i16* %pat
1986 // because any instruction dominates an instruction in a block that's
1987 // not reachable from entry.
1988 // So, remove unreachable blocks from the function, because a) there's
1989 // no point in analyzing them and b) GlobalOpt should otherwise grow
1990 // some more complicated logic to break these cycles.
1991 // Removing unreachable blocks might invalidate the dominator so we
1992 // recalculate it.
1993 if (!F.isDeclaration()) {
1994 if (removeUnreachableBlocks(F)) {
1995 auto &DT = LookupDomTree(F);
1996 DT.recalculate(F);
1997 Changed = true;
1998 }
1999 }
2000
2001 Changed |= processGlobal(F, GetTTI, GetTLI, LookupDomTree);
2002
2003 if (!F.hasLocalLinkage())
2004 continue;
2005
2006 // If we have an inalloca parameter that we can safely remove the
2007 // inalloca attribute from, do so. This unlocks optimizations that
2008 // wouldn't be safe in the presence of inalloca.
2009 // FIXME: We should also hoist alloca affected by this to the entry
2010 // block if possible.
2011 if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca) &&
2012 !F.hasAddressTaken() && !hasMustTailCallers(&F)) {
2013 RemoveAttribute(&F, Attribute::InAlloca);
2014 Changed = true;
2015 }
2016
2017 // FIXME: handle invokes
2018 // FIXME: handle musttail
2019 if (F.getAttributes().hasAttrSomewhere(Attribute::Preallocated)) {
2020 if (!F.hasAddressTaken() && !hasMustTailCallers(&F) &&
2021 !hasInvokeCallers(&F)) {
2022 RemovePreallocated(&F);
2023 Changed = true;
2024 }
2025 continue;
2026 }
2027
2028 if (hasChangeableCC(&F) && !F.isVarArg() && !F.hasAddressTaken()) {
2029 NumInternalFunc++;
2030 TargetTransformInfo &TTI = GetTTI(F);
2031 // Change the calling convention to coldcc if either stress testing is
2032 // enabled or the target would like to use coldcc on functions which are
2033 // cold at all call sites and the callers contain no other non coldcc
2034 // calls.
2035 if (EnableColdCCStressTest ||
2036 (TTI.useColdCCForColdCall(F) &&
2037 isValidCandidateForColdCC(F, GetBFI, AllCallsCold))) {
2038 F.setCallingConv(CallingConv::Cold);
2039 changeCallSitesToColdCC(&F);
2040 Changed = true;
2041 NumColdCC++;
2042 }
2043 }
2044
2045 if (hasChangeableCC(&F) && !F.isVarArg() && !F.hasAddressTaken()) {
2046 // If this function has a calling convention worth changing, is not a
2047 // varargs function, and is only called directly, promote it to use the
2048 // Fast calling convention.
2049 F.setCallingConv(CallingConv::Fast);
2050 ChangeCalleesToFastCall(&F);
2051 ++NumFastCallFns;
2052 Changed = true;
2053 }
2054
2055 if (F.getAttributes().hasAttrSomewhere(Attribute::Nest) &&
2056 !F.hasAddressTaken()) {
2057 // The function is not used by a trampoline intrinsic, so it is safe
2058 // to remove the 'nest' attribute.
2059 RemoveAttribute(&F, Attribute::Nest);
2060 ++NumNestRemoved;
2061 Changed = true;
2062 }
2063 }
2064 return Changed;
2065}
2066
2067static bool
2068OptimizeGlobalVars(Module &M,
2069 function_ref<TargetTransformInfo &(Function &)> GetTTI,
2070 function_ref<TargetLibraryInfo &(Function &)> GetTLI,
2071 function_ref<DominatorTree &(Function &)> LookupDomTree,
2072 SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
2073 bool Changed = false;
2074
2075 for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) {
2076 // Global variables without names cannot be referenced outside this module.
2077 if (!GV.hasName() && !GV.isDeclaration() && !GV.hasLocalLinkage())
2078 GV.setLinkage(GlobalValue::InternalLinkage);
2079 // Simplify the initializer.
2080 if (GV.hasInitializer())
2081 if (auto *C = dyn_cast<Constant>(GV.getInitializer())) {
2082 auto &DL = M.getDataLayout();
2083 // TLI is not used in the case of a Constant, so use default nullptr
2084 // for that optional parameter, since we don't have a Function to
2085 // provide GetTLI anyway.
2086 Constant *New = ConstantFoldConstant(C, DL, /*TLI*/ nullptr);
2087 if (New != C)
2088 GV.setInitializer(New);
2089 }
2090
2091 if (deleteIfDead(GV, NotDiscardableComdats)) {
2092 Changed = true;
2093 continue;
2094 }
2095
2096 Changed |= processGlobal(GV, GetTTI, GetTLI, LookupDomTree);
2097 }
2098 return Changed;
2099}
2100
2101/// Evaluate a piece of a constantexpr store into a global initializer. This
2102/// returns 'Init' modified to reflect 'Val' stored into it. At this point, the
2103/// GEP operands of Addr [0, OpNo) have been stepped into.
2104static Constant *EvaluateStoreInto(Constant *Init, Constant *Val,
2105 ConstantExpr *Addr, unsigned OpNo) {
2106 // Base case of the recursion.
2107 if (OpNo == Addr->getNumOperands()) {
2108 assert(Val->getType() == Init->getType() && "Type mismatch!")(static_cast <bool> (Val->getType() == Init->getType
() && "Type mismatch!") ? void (0) : __assert_fail ("Val->getType() == Init->getType() && \"Type mismatch!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2108, __extension__ __PRETTY_FUNCTION__))
;
2109 return Val;
2110 }
2111
2112 SmallVector<Constant*, 32> Elts;
2113 if (StructType *STy = dyn_cast<StructType>(Init->getType())) {
2114 // Break up the constant into its elements.
2115 for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
2116 Elts.push_back(Init->getAggregateElement(i));
2117
2118 // Replace the element that we are supposed to.
2119 ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo));
2120 unsigned Idx = CU->getZExtValue();
2121 assert(Idx < STy->getNumElements() && "Struct index out of range!")(static_cast <bool> (Idx < STy->getNumElements() &&
"Struct index out of range!") ? void (0) : __assert_fail ("Idx < STy->getNumElements() && \"Struct index out of range!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2121, __extension__ __PRETTY_FUNCTION__))
;
2122 Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1);
2123
2124 // Return the modified struct.
2125 return ConstantStruct::get(STy, Elts);
2126 }
2127
2128 ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo));
2129 uint64_t NumElts;
2130 if (ArrayType *ATy = dyn_cast<ArrayType>(Init->getType()))
2131 NumElts = ATy->getNumElements();
2132 else
2133 NumElts = cast<FixedVectorType>(Init->getType())->getNumElements();
2134
2135 // Break up the array into elements.
2136 for (uint64_t i = 0, e = NumElts; i != e; ++i)
2137 Elts.push_back(Init->getAggregateElement(i));
2138
2139 assert(CI->getZExtValue() < NumElts)(static_cast <bool> (CI->getZExtValue() < NumElts
) ? void (0) : __assert_fail ("CI->getZExtValue() < NumElts"
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2139, __extension__ __PRETTY_FUNCTION__))
;
2140 Elts[CI->getZExtValue()] =
2141 EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1);
2142
2143 if (Init->getType()->isArrayTy())
2144 return ConstantArray::get(cast<ArrayType>(Init->getType()), Elts);
2145 return ConstantVector::get(Elts);
2146}
2147
2148/// We have decided that Addr (which satisfies the predicate
2149/// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen.
2150static void CommitValueTo(Constant *Val, Constant *Addr) {
2151 if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
2152 assert(GV->hasInitializer())(static_cast <bool> (GV->hasInitializer()) ? void (0
) : __assert_fail ("GV->hasInitializer()", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2152, __extension__ __PRETTY_FUNCTION__))
;
2153 GV->setInitializer(Val);
2154 return;
2155 }
2156
2157 ConstantExpr *CE = cast<ConstantExpr>(Addr);
2158 GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
2159 GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2));
2160}
2161
2162/// Given a map of address -> value, where addresses are expected to be some form
2163/// of either a global or a constant GEP, set the initializer for the address to
2164/// be the value. This performs mostly the same function as CommitValueTo()
2165/// and EvaluateStoreInto() but is optimized to be more efficient for the common
2166/// case where the set of addresses are GEPs sharing the same underlying global,
2167/// processing the GEPs in batches rather than individually.
2168///
2169/// To give an example, consider the following C++ code adapted from the clang
2170/// regression tests:
2171/// struct S {
2172/// int n = 10;
2173/// int m = 2 * n;
2174/// S(int a) : n(a) {}
2175/// };
2176///
2177/// template<typename T>
2178/// struct U {
2179/// T *r = &q;
2180/// T q = 42;
2181/// U *p = this;
2182/// };
2183///
2184/// U<S> e;
2185///
2186/// The global static constructor for 'e' will need to initialize 'r' and 'p' of
2187/// the outer struct, while also initializing the inner 'q' structs 'n' and 'm'
2188/// members. This batch algorithm will simply use general CommitValueTo() method
2189/// to handle the complex nested S struct initialization of 'q', before
2190/// processing the outermost members in a single batch. Using CommitValueTo() to
2191/// handle member in the outer struct is inefficient when the struct/array is
2192/// very large as we end up creating and destroy constant arrays for each
2193/// initialization.
2194/// For the above case, we expect the following IR to be generated:
2195///
2196/// %struct.U = type { %struct.S*, %struct.S, %struct.U* }
2197/// %struct.S = type { i32, i32 }
2198/// @e = global %struct.U { %struct.S* gep inbounds (%struct.U, %struct.U* @e,
2199/// i64 0, i32 1),
2200/// %struct.S { i32 42, i32 84 }, %struct.U* @e }
2201/// The %struct.S { i32 42, i32 84 } inner initializer is treated as a complex
2202/// constant expression, while the other two elements of @e are "simple".
2203static void BatchCommitValueTo(const DenseMap<Constant*, Constant*> &Mem) {
2204 SmallVector<std::pair<GlobalVariable*, Constant*>, 32> GVs;
2205 SmallVector<std::pair<ConstantExpr*, Constant*>, 32> ComplexCEs;
2206 SmallVector<std::pair<ConstantExpr*, Constant*>, 32> SimpleCEs;
2207 SimpleCEs.reserve(Mem.size());
2208
2209 for (const auto &I : Mem) {
2210 if (auto *GV = dyn_cast<GlobalVariable>(I.first)) {
2211 GVs.push_back(std::make_pair(GV, I.second));
2212 } else {
2213 ConstantExpr *GEP = cast<ConstantExpr>(I.first);
2214 // We don't handle the deeply recursive case using the batch method.
2215 if (GEP->getNumOperands() > 3)
2216 ComplexCEs.push_back(std::make_pair(GEP, I.second));
2217 else
2218 SimpleCEs.push_back(std::make_pair(GEP, I.second));
2219 }
2220 }
2221
2222 // The algorithm below doesn't handle cases like nested structs, so use the
2223 // slower fully general method if we have to.
2224 for (auto ComplexCE : ComplexCEs)
7
Assuming '__begin1' is equal to '__end1'
2225 CommitValueTo(ComplexCE.second, ComplexCE.first);
2226
2227 for (auto GVPair : GVs) {
8
Assuming '__begin1' is equal to '__end1'
2228 assert(GVPair.first->hasInitializer())(static_cast <bool> (GVPair.first->hasInitializer())
? void (0) : __assert_fail ("GVPair.first->hasInitializer()"
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2228, __extension__ __PRETTY_FUNCTION__))
;
2229 GVPair.first->setInitializer(GVPair.second);
2230 }
2231
2232 if (SimpleCEs.empty())
9
Calling 'SmallVectorBase::empty'
12
Returning from 'SmallVectorBase::empty'
13
Taking false branch
2233 return;
2234
2235 // We cache a single global's initializer elements in the case where the
2236 // subsequent address/val pair uses the same one. This avoids throwing away and
2237 // rebuilding the constant struct/vector/array just because one element is
2238 // modified at a time.
2239 SmallVector<Constant *, 32> Elts;
2240 Elts.reserve(SimpleCEs.size());
2241 GlobalVariable *CurrentGV = nullptr;
14
'CurrentGV' initialized to a null pointer value
2242
2243 auto commitAndSetupCache = [&](GlobalVariable *GV, bool Update) {
2244 Constant *Init = GV->getInitializer();
18
Called C++ object pointer is null
2245 Type *Ty = Init->getType();
2246 if (Update) {
2247 if (CurrentGV) {
2248 assert(CurrentGV && "Expected a GV to commit to!")(static_cast <bool> (CurrentGV && "Expected a GV to commit to!"
) ? void (0) : __assert_fail ("CurrentGV && \"Expected a GV to commit to!\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2248, __extension__ __PRETTY_FUNCTION__))
;
2249 Type *CurrentInitTy = CurrentGV->getInitializer()->getType();
2250 // We have a valid cache that needs to be committed.
2251 if (StructType *STy = dyn_cast<StructType>(CurrentInitTy))
2252 CurrentGV->setInitializer(ConstantStruct::get(STy, Elts));
2253 else if (ArrayType *ArrTy = dyn_cast<ArrayType>(CurrentInitTy))
2254 CurrentGV->setInitializer(ConstantArray::get(ArrTy, Elts));
2255 else
2256 CurrentGV->setInitializer(ConstantVector::get(Elts));
2257 }
2258 if (CurrentGV == GV)
2259 return;
2260 // Need to clear and set up cache for new initializer.
2261 CurrentGV = GV;
2262 Elts.clear();
2263 unsigned NumElts;
2264 if (auto *STy = dyn_cast<StructType>(Ty))
2265 NumElts = STy->getNumElements();
2266 else if (auto *ATy = dyn_cast<ArrayType>(Ty))
2267 NumElts = ATy->getNumElements();
2268 else
2269 NumElts = cast<FixedVectorType>(Ty)->getNumElements();
2270 for (unsigned i = 0, e = NumElts; i != e; ++i)
2271 Elts.push_back(Init->getAggregateElement(i));
2272 }
2273 };
2274
2275 for (auto CEPair : SimpleCEs) {
15
Assuming '__begin1' is equal to '__end1'
2276 ConstantExpr *GEP = CEPair.first;
2277 Constant *Val = CEPair.second;
2278
2279 GlobalVariable *GV = cast<GlobalVariable>(GEP->getOperand(0));
2280 commitAndSetupCache(GV, GV != CurrentGV);
2281 ConstantInt *CI = cast<ConstantInt>(GEP->getOperand(2));
2282 Elts[CI->getZExtValue()] = Val;
2283 }
2284 // The last initializer in the list needs to be committed, others
2285 // will be committed on a new initializer being processed.
2286 commitAndSetupCache(CurrentGV, true);
16
Passing null pointer value via 1st parameter 'GV'
17
Calling 'operator()'
2287}
2288
2289/// Evaluate static constructors in the function, if we can. Return true if we
2290/// can, false otherwise.
2291static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL,
2292 TargetLibraryInfo *TLI) {
2293 // Call the function.
2294 Evaluator Eval(DL, TLI);
2295 Constant *RetValDummy;
2296 bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy,
2297 SmallVector<Constant*, 0>());
2298
2299 if (EvalSuccess) {
2
Assuming 'EvalSuccess' is true
3
Taking true branch
2300 ++NumCtorsEvaluated;
2301
2302 // We succeeded at evaluation: commit the result.
2303 LLVM_DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
<< F->getName() << "' to " << Eval.getMutatedMemory
().size() << " stores.\n"; } } while (false)
4
Assuming 'DebugFlag' is false
5
Loop condition is false. Exiting loop
2304 << F->getName() << "' to "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
<< F->getName() << "' to " << Eval.getMutatedMemory
().size() << " stores.\n"; } } while (false)
2305 << Eval.getMutatedMemory().size() << " stores.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("globalopt")) { dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
<< F->getName() << "' to " << Eval.getMutatedMemory
().size() << " stores.\n"; } } while (false)
;
2306 BatchCommitValueTo(Eval.getMutatedMemory());
6
Calling 'BatchCommitValueTo'
2307 for (GlobalVariable *GV : Eval.getInvariants())
2308 GV->setConstant(true);
2309 }
2310
2311 return EvalSuccess;
2312}
2313
2314static int compareNames(Constant *const *A, Constant *const *B) {
2315 Value *AStripped = (*A)->stripPointerCasts();
2316 Value *BStripped = (*B)->stripPointerCasts();
2317 return AStripped->getName().compare(BStripped->getName());
2318}
2319
2320static void setUsedInitializer(GlobalVariable &V,
2321 const SmallPtrSetImpl<GlobalValue *> &Init) {
2322 if (Init.empty()) {
2323 V.eraseFromParent();
2324 return;
2325 }
2326
2327 // Type of pointer to the array of pointers.
2328 PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext(), 0);
2329
2330 SmallVector<Constant *, 8> UsedArray;
2331 for (GlobalValue *GV : Init) {
2332 Constant *Cast
2333 = ConstantExpr::getPointerBitCastOrAddrSpaceCast(GV, Int8PtrTy);
2334 UsedArray.push_back(Cast);
2335 }
2336 // Sort to get deterministic order.
2337 array_pod_sort(UsedArray.begin(), UsedArray.end(), compareNames);
2338 ArrayType *ATy = ArrayType::get(Int8PtrTy, UsedArray.size());
2339
2340 Module *M = V.getParent();
2341 V.removeFromParent();
2342 GlobalVariable *NV =
2343 new GlobalVariable(*M, ATy, false, GlobalValue::AppendingLinkage,
2344 ConstantArray::get(ATy, UsedArray), "");
2345 NV->takeName(&V);
2346 NV->setSection("llvm.metadata");
2347 delete &V;
2348}
2349
2350namespace {
2351
2352/// An easy to access representation of llvm.used and llvm.compiler.used.
2353class LLVMUsed {
2354 SmallPtrSet<GlobalValue *, 4> Used;
2355 SmallPtrSet<GlobalValue *, 4> CompilerUsed;
2356 GlobalVariable *UsedV;
2357 GlobalVariable *CompilerUsedV;
2358
2359public:
2360 LLVMUsed(Module &M) {
2361 SmallVector<GlobalValue *, 4> Vec;
2362 UsedV = collectUsedGlobalVariables(M, Vec, false);
2363 Used = {Vec.begin(), Vec.end()};
2364 Vec.clear();
2365 CompilerUsedV = collectUsedGlobalVariables(M, Vec, true);
2366 CompilerUsed = {Vec.begin(), Vec.end()};
2367 }
2368
2369 using iterator = SmallPtrSet<GlobalValue *, 4>::iterator;
2370 using used_iterator_range = iterator_range<iterator>;
2371
2372 iterator usedBegin() { return Used.begin(); }
2373 iterator usedEnd() { return Used.end(); }
2374
2375 used_iterator_range used() {
2376 return used_iterator_range(usedBegin(), usedEnd());
2377 }
2378
2379 iterator compilerUsedBegin() { return CompilerUsed.begin(); }
2380 iterator compilerUsedEnd() { return CompilerUsed.end(); }
2381
2382 used_iterator_range compilerUsed() {
2383 return used_iterator_range(compilerUsedBegin(), compilerUsedEnd());
2384 }
2385
2386 bool usedCount(GlobalValue *GV) const { return Used.count(GV); }
2387
2388 bool compilerUsedCount(GlobalValue *GV) const {
2389 return CompilerUsed.count(GV);
2390 }
2391
2392 bool usedErase(GlobalValue *GV) { return Used.erase(GV); }
2393 bool compilerUsedErase(GlobalValue *GV) { return CompilerUsed.erase(GV); }
2394 bool usedInsert(GlobalValue *GV) { return Used.insert(GV).second; }
2395
2396 bool compilerUsedInsert(GlobalValue *GV) {
2397 return CompilerUsed.insert(GV).second;
2398 }
2399
2400 void syncVariablesAndSets() {
2401 if (UsedV)
2402 setUsedInitializer(*UsedV, Used);
2403 if (CompilerUsedV)
2404 setUsedInitializer(*CompilerUsedV, CompilerUsed);
2405 }
2406};
2407
2408} // end anonymous namespace
2409
2410static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U) {
2411 if (GA.use_empty()) // No use at all.
2412 return false;
2413
2414 assert((!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) &&(static_cast <bool> ((!U.usedCount(&GA) || !U.compilerUsedCount
(&GA)) && "We should have removed the duplicated "
"element from llvm.compiler.used") ? void (0) : __assert_fail
("(!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) && \"We should have removed the duplicated \" \"element from llvm.compiler.used\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2416, __extension__ __PRETTY_FUNCTION__))
2415 "We should have removed the duplicated "(static_cast <bool> ((!U.usedCount(&GA) || !U.compilerUsedCount
(&GA)) && "We should have removed the duplicated "
"element from llvm.compiler.used") ? void (0) : __assert_fail
("(!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) && \"We should have removed the duplicated \" \"element from llvm.compiler.used\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2416, __extension__ __PRETTY_FUNCTION__))
2416 "element from llvm.compiler.used")(static_cast <bool> ((!U.usedCount(&GA) || !U.compilerUsedCount
(&GA)) && "We should have removed the duplicated "
"element from llvm.compiler.used") ? void (0) : __assert_fail
("(!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) && \"We should have removed the duplicated \" \"element from llvm.compiler.used\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2416, __extension__ __PRETTY_FUNCTION__))
;
2417 if (!GA.hasOneUse())
2418 // Strictly more than one use. So at least one is not in llvm.used and
2419 // llvm.compiler.used.
2420 return true;
2421
2422 // Exactly one use. Check if it is in llvm.used or llvm.compiler.used.
2423 return !U.usedCount(&GA) && !U.compilerUsedCount(&GA);
2424}
2425
2426static bool hasMoreThanOneUseOtherThanLLVMUsed(GlobalValue &V,
2427 const LLVMUsed &U) {
2428 unsigned N = 2;
2429 assert((!U.usedCount(&V) || !U.compilerUsedCount(&V)) &&(static_cast <bool> ((!U.usedCount(&V) || !U.compilerUsedCount
(&V)) && "We should have removed the duplicated "
"element from llvm.compiler.used") ? void (0) : __assert_fail
("(!U.usedCount(&V) || !U.compilerUsedCount(&V)) && \"We should have removed the duplicated \" \"element from llvm.compiler.used\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2431, __extension__ __PRETTY_FUNCTION__))
2430 "We should have removed the duplicated "(static_cast <bool> ((!U.usedCount(&V) || !U.compilerUsedCount
(&V)) && "We should have removed the duplicated "
"element from llvm.compiler.used") ? void (0) : __assert_fail
("(!U.usedCount(&V) || !U.compilerUsedCount(&V)) && \"We should have removed the duplicated \" \"element from llvm.compiler.used\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2431, __extension__ __PRETTY_FUNCTION__))
2431 "element from llvm.compiler.used")(static_cast <bool> ((!U.usedCount(&V) || !U.compilerUsedCount
(&V)) && "We should have removed the duplicated "
"element from llvm.compiler.used") ? void (0) : __assert_fail
("(!U.usedCount(&V) || !U.compilerUsedCount(&V)) && \"We should have removed the duplicated \" \"element from llvm.compiler.used\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/lib/Transforms/IPO/GlobalOpt.cpp"
, 2431, __extension__ __PRETTY_FUNCTION__))
;
2432 if (U.usedCount(&V) || U.compilerUsedCount(&V))
2433 ++N;
2434 return V.hasNUsesOrMore(N);
2435}
2436
2437static bool mayHaveOtherReferences(GlobalAlias &GA, const LLVMUsed &U) {
2438 if (!GA.hasLocalLinkage())
2439 return true;
2440
2441 return U.usedCount(&GA) || U.compilerUsedCount(&GA);
2442}
2443
2444static bool hasUsesToReplace(GlobalAlias &GA, const LLVMUsed &U,
2445 bool &RenameTarget) {
2446 RenameTarget = false;
2447 bool Ret = false;
2448 if (hasUseOtherThanLLVMUsed(GA, U))
2449 Ret = true;
2450
2451 // If the alias is externally visible, we may still be able to simplify it.
2452 if (!mayHaveOtherReferences(GA, U))
2453 return Ret;
2454
2455 // If the aliasee has internal linkage, give it the name and linkage
2456 // of the alias, and delete the alias. This turns:
2457 // define internal ... @f(...)
2458 // @a = alias ... @f
2459 // into:
2460 // define ... @a(...)
2461 Constant *Aliasee = GA.getAliasee();
2462 GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts());
2463 if (!Target->hasLocalLinkage())
2464 return Ret;
2465
2466 // Do not perform the transform if multiple aliases potentially target the
2467 // aliasee. This check also ensures that it is safe to replace the section
2468 // and other attributes of the aliasee with those of the alias.
2469 if (hasMoreThanOneUseOtherThanLLVMUsed(*Target, U))
2470 return Ret;
2471
2472 RenameTarget = true;
2473 return true;
2474}
2475
2476static bool
2477OptimizeGlobalAliases(Module &M,
2478 SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
2479 bool Changed = false;
2480 LLVMUsed Used(M);
2481
2482 for (GlobalValue *GV : Used.used())
2483 Used.compilerUsedErase(GV);
2484
2485 for (GlobalAlias &J : llvm::make_early_inc_range(M.aliases())) {
2486 // Aliases without names cannot be referenced outside this module.
2487 if (!J.hasName() && !J.isDeclaration() && !J.hasLocalLinkage())
2488 J.setLinkage(GlobalValue::InternalLinkage);
2489
2490 if (deleteIfDead(J, NotDiscardableComdats)) {
2491 Changed = true;
2492 continue;
2493 }
2494
2495 // If the alias can change at link time, nothing can be done - bail out.
2496 if (J.isInterposable())
2497 continue;
2498
2499 Constant *Aliasee = J.getAliasee();
2500 GlobalValue *Target = dyn_cast<GlobalValue>(Aliasee->stripPointerCasts());
2501 // We can't trivially replace the alias with the aliasee if the aliasee is
2502 // non-trivial in some way. We also can't replace the alias with the aliasee
2503 // if the aliasee is interposable because aliases point to the local
2504 // definition.
2505 // TODO: Try to handle non-zero GEPs of local aliasees.
2506 if (!Target || Target->isInterposable())
2507 continue;
2508 Target->removeDeadConstantUsers();
2509
2510 // Make all users of the alias use the aliasee instead.
2511 bool RenameTarget;
2512 if (!hasUsesToReplace(J, Used, RenameTarget))
2513 continue;
2514
2515 J.replaceAllUsesWith(ConstantExpr::getBitCast(Aliasee, J.getType()));
2516 ++NumAliasesResolved;
2517 Changed = true;
2518
2519 if (RenameTarget) {
2520 // Give the aliasee the name, linkage and other attributes of the alias.
2521 Target->takeName(&J);
2522 Target->setLinkage(J.getLinkage());
2523 Target->setDSOLocal(J.isDSOLocal());
2524 Target->setVisibility(J.getVisibility());
2525 Target->setDLLStorageClass(J.getDLLStorageClass());
2526
2527 if (Used.usedErase(&J))
2528 Used.usedInsert(Target);
2529
2530 if (Used.compilerUsedErase(&J))
2531 Used.compilerUsedInsert(Target);
2532 } else if (mayHaveOtherReferences(J, Used))
2533 continue;
2534
2535 // Delete the alias.
2536 M.getAliasList().erase(&J);
2537 ++NumAliasesRemoved;
2538 Changed = true;
2539 }
2540
2541 Used.syncVariablesAndSets();
2542
2543 return Changed;
2544}
2545
2546static Function *
2547FindCXAAtExit(Module &M, function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
2548 // Hack to get a default TLI before we have actual Function.
2549 auto FuncIter = M.begin();
2550 if (FuncIter == M.end())
2551 return nullptr;
2552 auto *TLI = &GetTLI(*FuncIter);
2553
2554 LibFunc F = LibFunc_cxa_atexit;
2555 if (!TLI->has(F))
2556 return nullptr;
2557
2558 Function *Fn = M.getFunction(TLI->getName(F));
2559 if (!Fn)
2560 return nullptr;
2561
2562 // Now get the actual TLI for Fn.
2563 TLI = &GetTLI(*Fn);
2564
2565 // Make sure that the function has the correct prototype.
2566 if (!TLI->getLibFunc(*Fn, F) || F != LibFunc_cxa_atexit)
2567 return nullptr;
2568
2569 return Fn;
2570}
2571
2572/// Returns whether the given function is an empty C++ destructor and can
2573/// therefore be eliminated.
2574/// Note that we assume that other optimization passes have already simplified
2575/// the code so we simply check for 'ret'.
2576static bool cxxDtorIsEmpty(const Function &Fn) {
2577 // FIXME: We could eliminate C++ destructors if they're readonly/readnone and
2578 // nounwind, but that doesn't seem worth doing.
2579 if (Fn.isDeclaration())
2580 return false;
2581
2582 for (auto &I : Fn.getEntryBlock()) {
2583 if (isa<DbgInfoIntrinsic>(I))
2584 continue;
2585 if (isa<ReturnInst>(I))
2586 return true;
2587 break;
2588 }
2589 return false;
2590}
2591
2592static bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) {
2593 /// Itanium C++ ABI p3.3.5:
2594 ///
2595 /// After constructing a global (or local static) object, that will require
2596 /// destruction on exit, a termination function is registered as follows:
2597 ///
2598 /// extern "C" int __cxa_atexit ( void (*f)(void *), void *p, void *d );
2599 ///
2600 /// This registration, e.g. __cxa_atexit(f,p,d), is intended to cause the
2601 /// call f(p) when DSO d is unloaded, before all such termination calls
2602 /// registered before this one. It returns zero if registration is
2603 /// successful, nonzero on failure.
2604
2605 // This pass will look for calls to __cxa_atexit where the function is trivial
2606 // and remove them.
2607 bool Changed = false;
2608
2609 for (auto I = CXAAtExitFn->user_begin(), E = CXAAtExitFn->user_end();
2610 I != E;) {
2611 // We're only interested in calls. Theoretically, we could handle invoke
2612 // instructions as well, but neither llvm-gcc nor clang generate invokes
2613 // to __cxa_atexit.
2614 CallInst *CI = dyn_cast<CallInst>(*I++);
2615 if (!CI)
2616 continue;
2617
2618 Function *DtorFn =
2619 dyn_cast<Function>(CI->getArgOperand(0)->stripPointerCasts());
2620 if (!DtorFn || !cxxDtorIsEmpty(*DtorFn))
2621 continue;
2622
2623 // Just remove the call.
2624 CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
2625 CI->eraseFromParent();
2626
2627 ++NumCXXDtorsRemoved;
2628
2629 Changed |= true;
2630 }
2631
2632 return Changed;
2633}
2634
2635static bool optimizeGlobalsInModule(
2636 Module &M, const DataLayout &DL,
2637 function_ref<TargetLibraryInfo &(Function &)> GetTLI,
2638 function_ref<TargetTransformInfo &(Function &)> GetTTI,
2639 function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
2640 function_ref<DominatorTree &(Function &)> LookupDomTree) {
2641 SmallPtrSet<const Comdat *, 8> NotDiscardableComdats;
2642 bool Changed = false;
2643 bool LocalChange = true;
2644 while (LocalChange) {
2645 LocalChange = false;
2646
2647 NotDiscardableComdats.clear();
2648 for (const GlobalVariable &GV : M.globals())
2649 if (const Comdat *C = GV.getComdat())
2650 if (!GV.isDiscardableIfUnused() || !GV.use_empty())
2651 NotDiscardableComdats.insert(C);
2652 for (Function &F : M)
2653 if (const Comdat *C = F.getComdat())
2654 if (!F.isDefTriviallyDead())
2655 NotDiscardableComdats.insert(C);
2656 for (GlobalAlias &GA : M.aliases())
2657 if (const Comdat *C = GA.getComdat())
2658 if (!GA.isDiscardableIfUnused() || !GA.use_empty())
2659 NotDiscardableComdats.insert(C);
2660
2661 // Delete functions that are trivially dead, ccc -> fastcc
2662 LocalChange |= OptimizeFunctions(M, GetTLI, GetTTI, GetBFI, LookupDomTree,
2663 NotDiscardableComdats);
2664
2665 // Optimize global_ctors list.
2666 LocalChange |= optimizeGlobalCtorsList(M, [&](Function *F) {
2667 return EvaluateStaticConstructor(F, DL, &GetTLI(*F));
1
Calling 'EvaluateStaticConstructor'
2668 });
2669
2670 // Optimize non-address-taken globals.
2671 LocalChange |= OptimizeGlobalVars(M, GetTTI, GetTLI, LookupDomTree,
2672 NotDiscardableComdats);
2673
2674 // Resolve aliases, when possible.
2675 LocalChange |= OptimizeGlobalAliases(M, NotDiscardableComdats);
2676
2677 // Try to remove trivial global destructors if they are not removed
2678 // already.
2679 Function *CXAAtExitFn = FindCXAAtExit(M, GetTLI);
2680 if (CXAAtExitFn)
2681 LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn);
2682
2683 Changed |= LocalChange;
2684 }
2685
2686 // TODO: Move all global ctors functions to the end of the module for code
2687 // layout.
2688
2689 return Changed;
2690}
2691
2692PreservedAnalyses GlobalOptPass::run(Module &M, ModuleAnalysisManager &AM) {
2693 auto &DL = M.getDataLayout();
2694 auto &FAM =
2695 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
2696 auto LookupDomTree = [&FAM](Function &F) -> DominatorTree &{
2697 return FAM.getResult<DominatorTreeAnalysis>(F);
2698 };
2699 auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
2700 return FAM.getResult<TargetLibraryAnalysis>(F);
2701 };
2702 auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {
2703 return FAM.getResult<TargetIRAnalysis>(F);
2704 };
2705
2706 auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & {
2707 return FAM.getResult<BlockFrequencyAnalysis>(F);
2708 };
2709
2710 if (!optimizeGlobalsInModule(M, DL, GetTLI, GetTTI, GetBFI, LookupDomTree))
2711 return PreservedAnalyses::all();
2712 return PreservedAnalyses::none();
2713}
2714
2715namespace {
2716
2717struct GlobalOptLegacyPass : public ModulePass {
2718 static char ID; // Pass identification, replacement for typeid
2719
2720 GlobalOptLegacyPass() : ModulePass(ID) {
2721 initializeGlobalOptLegacyPassPass(*PassRegistry::getPassRegistry());
2722 }
2723
2724 bool runOnModule(Module &M) override {
2725 if (skipModule(M))
2726 return false;
2727
2728 auto &DL = M.getDataLayout();
2729 auto LookupDomTree = [this](Function &F) -> DominatorTree & {
2730 return this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
2731 };
2732 auto GetTLI = [this](Function &F) -> TargetLibraryInfo & {
2733 return this->getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
2734 };
2735 auto GetTTI = [this](Function &F) -> TargetTransformInfo & {
2736 return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
2737 };
2738
2739 auto GetBFI = [this](Function &F) -> BlockFrequencyInfo & {
2740 return this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
2741 };
2742
2743 return optimizeGlobalsInModule(M, DL, GetTLI, GetTTI, GetBFI,
2744 LookupDomTree);
2745 }
2746
2747 void getAnalysisUsage(AnalysisUsage &AU) const override {
2748 AU.addRequired<TargetLibraryInfoWrapperPass>();
2749 AU.addRequired<TargetTransformInfoWrapperPass>();
2750 AU.addRequired<DominatorTreeWrapperPass>();
2751 AU.addRequired<BlockFrequencyInfoWrapperPass>();
2752 }
2753};
2754
2755} // end anonymous namespace
2756
2757char GlobalOptLegacyPass::ID = 0;
2758
2759INITIALIZE_PASS_BEGIN(GlobalOptLegacyPass, "globalopt",static void *initializeGlobalOptLegacyPassPassOnce(PassRegistry
&Registry) {
2760 "Global Variable Optimizer", false, false)static void *initializeGlobalOptLegacyPassPassOnce(PassRegistry
&Registry) {
2761INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)initializeTargetLibraryInfoWrapperPassPass(Registry);
2762INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry);
2763INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)initializeBlockFrequencyInfoWrapperPassPass(Registry);
2764INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry);
2765INITIALIZE_PASS_END(GlobalOptLegacyPass, "globalopt",PassInfo *PI = new PassInfo( "Global Variable Optimizer", "globalopt"
, &GlobalOptLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<GlobalOptLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeGlobalOptLegacyPassPassFlag
; void llvm::initializeGlobalOptLegacyPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeGlobalOptLegacyPassPassFlag
, initializeGlobalOptLegacyPassPassOnce, std::ref(Registry));
}
2766 "Global Variable Optimizer", false, false)PassInfo *PI = new PassInfo( "Global Variable Optimizer", "globalopt"
, &GlobalOptLegacyPass::ID, PassInfo::NormalCtor_t(callDefaultCtor
<GlobalOptLegacyPass>), false, false); Registry.registerPass
(*PI, true); return PI; } static llvm::once_flag InitializeGlobalOptLegacyPassPassFlag
; void llvm::initializeGlobalOptLegacyPassPass(PassRegistry &
Registry) { llvm::call_once(InitializeGlobalOptLegacyPassPassFlag
, initializeGlobalOptLegacyPassPassOnce, std::ref(Registry));
}
2767
2768ModulePass *llvm::createGlobalOptimizerPass() {
2769 return new GlobalOptLegacyPass();
2770}

/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h

1//===- llvm/ADT/SmallVector.h - 'Normally small' vectors --------*- 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 defines the SmallVector class.
10//
11//===----------------------------------------------------------------------===//
12
13#ifndef LLVM_ADT_SMALLVECTOR_H
14#define LLVM_ADT_SMALLVECTOR_H
15
16#include "llvm/ADT/iterator_range.h"
17#include "llvm/Support/Compiler.h"
18#include "llvm/Support/ErrorHandling.h"
19#include "llvm/Support/MemAlloc.h"
20#include "llvm/Support/type_traits.h"
21#include <algorithm>
22#include <cassert>
23#include <cstddef>
24#include <cstdlib>
25#include <cstring>
26#include <functional>
27#include <initializer_list>
28#include <iterator>
29#include <limits>
30#include <memory>
31#include <new>
32#include <type_traits>
33#include <utility>
34
35namespace llvm {
36
37/// This is all the stuff common to all SmallVectors.
38///
39/// The template parameter specifies the type which should be used to hold the
40/// Size and Capacity of the SmallVector, so it can be adjusted.
41/// Using 32 bit size is desirable to shrink the size of the SmallVector.
42/// Using 64 bit size is desirable for cases like SmallVector<char>, where a
43/// 32 bit size would limit the vector to ~4GB. SmallVectors are used for
44/// buffering bitcode output - which can exceed 4GB.
45template <class Size_T> class SmallVectorBase {
46protected:
47 void *BeginX;
48 Size_T Size = 0, Capacity;
49
50 /// The maximum value of the Size_T used.
51 static constexpr size_t SizeTypeMax() {
52 return std::numeric_limits<Size_T>::max();
53 }
54
55 SmallVectorBase() = delete;
56 SmallVectorBase(void *FirstEl, size_t TotalCapacity)
57 : BeginX(FirstEl), Capacity(TotalCapacity) {}
58
59 /// This is a helper for \a grow() that's out of line to reduce code
60 /// duplication. This function will report a fatal error if it can't grow at
61 /// least to \p MinSize.
62 void *mallocForGrow(size_t MinSize, size_t TSize, size_t &NewCapacity);
63
64 /// This is an implementation of the grow() method which only works
65 /// on POD-like data types and is out of line to reduce code duplication.
66 /// This function will report a fatal error if it cannot increase capacity.
67 void grow_pod(void *FirstEl, size_t MinSize, size_t TSize);
68
69public:
70 size_t size() const { return Size; }
71 size_t capacity() const { return Capacity; }
72
73 LLVM_NODISCARD[[clang::warn_unused_result]] bool empty() const { return !Size; }
10
Assuming field 'Size' is not equal to 0
11
Returning zero, which participates in a condition later
74
75 /// Set the array size to \p N, which the current array must have enough
76 /// capacity for.
77 ///
78 /// This does not construct or destroy any elements in the vector.
79 ///
80 /// Clients can use this in conjunction with capacity() to write past the end
81 /// of the buffer when they know that more elements are available, and only
82 /// update the size later. This avoids the cost of value initializing elements
83 /// which will only be overwritten.
84 void set_size(size_t N) {
85 assert(N <= capacity())(static_cast <bool> (N <= capacity()) ? void (0) : __assert_fail
("N <= capacity()", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 85, __extension__ __PRETTY_FUNCTION__))
;
86 Size = N;
87 }
88};
89
90template <class T>
91using SmallVectorSizeType =
92 typename std::conditional<sizeof(T) < 4 && sizeof(void *) >= 8, uint64_t,
93 uint32_t>::type;
94
95/// Figure out the offset of the first element.
96template <class T, typename = void> struct SmallVectorAlignmentAndSize {
97 alignas(SmallVectorBase<SmallVectorSizeType<T>>) char Base[sizeof(
98 SmallVectorBase<SmallVectorSizeType<T>>)];
99 alignas(T) char FirstEl[sizeof(T)];
100};
101
102/// This is the part of SmallVectorTemplateBase which does not depend on whether
103/// the type T is a POD. The extra dummy template argument is used by ArrayRef
104/// to avoid unnecessarily requiring T to be complete.
105template <typename T, typename = void>
106class SmallVectorTemplateCommon
107 : public SmallVectorBase<SmallVectorSizeType<T>> {
108 using Base = SmallVectorBase<SmallVectorSizeType<T>>;
109
110 /// Find the address of the first element. For this pointer math to be valid
111 /// with small-size of 0 for T with lots of alignment, it's important that
112 /// SmallVectorStorage is properly-aligned even for small-size of 0.
113 void *getFirstEl() const {
114 return const_cast<void *>(reinterpret_cast<const void *>(
115 reinterpret_cast<const char *>(this) +
116 offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)__builtin_offsetof(SmallVectorAlignmentAndSize<T>, FirstEl
)
));
117 }
118 // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
119
120protected:
121 SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}
122
123 void grow_pod(size_t MinSize, size_t TSize) {
124 Base::grow_pod(getFirstEl(), MinSize, TSize);
125 }
126
127 /// Return true if this is a smallvector which has not had dynamic
128 /// memory allocated for it.
129 bool isSmall() const { return this->BeginX == getFirstEl(); }
130
131 /// Put this vector in a state of being small.
132 void resetToSmall() {
133 this->BeginX = getFirstEl();
134 this->Size = this->Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
135 }
136
137 /// Return true if V is an internal reference to the given range.
138 bool isReferenceToRange(const void *V, const void *First, const void *Last) const {
139 // Use std::less to avoid UB.
140 std::less<> LessThan;
141 return !LessThan(V, First) && LessThan(V, Last);
142 }
143
144 /// Return true if V is an internal reference to this vector.
145 bool isReferenceToStorage(const void *V) const {
146 return isReferenceToRange(V, this->begin(), this->end());
147 }
148
149 /// Return true if First and Last form a valid (possibly empty) range in this
150 /// vector's storage.
151 bool isRangeInStorage(const void *First, const void *Last) const {
152 // Use std::less to avoid UB.
153 std::less<> LessThan;
154 return !LessThan(First, this->begin()) && !LessThan(Last, First) &&
155 !LessThan(this->end(), Last);
156 }
157
158 /// Return true unless Elt will be invalidated by resizing the vector to
159 /// NewSize.
160 bool isSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
161 // Past the end.
162 if (LLVM_LIKELY(!isReferenceToStorage(Elt))__builtin_expect((bool)(!isReferenceToStorage(Elt)), true))
163 return true;
164
165 // Return false if Elt will be destroyed by shrinking.
166 if (NewSize <= this->size())
167 return Elt < this->begin() + NewSize;
168
169 // Return false if we need to grow.
170 return NewSize <= this->capacity();
171 }
172
173 /// Check whether Elt will be invalidated by resizing the vector to NewSize.
174 void assertSafeToReferenceAfterResize(const void *Elt, size_t NewSize) {
175 assert(isSafeToReferenceAfterResize(Elt, NewSize) &&(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize
) && "Attempting to reference an element of the vector in an operation "
"that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 177, __extension__ __PRETTY_FUNCTION__))
176 "Attempting to reference an element of the vector in an operation "(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize
) && "Attempting to reference an element of the vector in an operation "
"that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 177, __extension__ __PRETTY_FUNCTION__))
177 "that invalidates it")(static_cast <bool> (isSafeToReferenceAfterResize(Elt, NewSize
) && "Attempting to reference an element of the vector in an operation "
"that invalidates it") ? void (0) : __assert_fail ("isSafeToReferenceAfterResize(Elt, NewSize) && \"Attempting to reference an element of the vector in an operation \" \"that invalidates it\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 177, __extension__ __PRETTY_FUNCTION__))
;
178 }
179
180 /// Check whether Elt will be invalidated by increasing the size of the
181 /// vector by N.
182 void assertSafeToAdd(const void *Elt, size_t N = 1) {
183 this->assertSafeToReferenceAfterResize(Elt, this->size() + N);
184 }
185
186 /// Check whether any part of the range will be invalidated by clearing.
187 void assertSafeToReferenceAfterClear(const T *From, const T *To) {
188 if (From == To)
189 return;
190 this->assertSafeToReferenceAfterResize(From, 0);
191 this->assertSafeToReferenceAfterResize(To - 1, 0);
192 }
193 template <
194 class ItTy,
195 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
196 bool> = false>
197 void assertSafeToReferenceAfterClear(ItTy, ItTy) {}
198
199 /// Check whether any part of the range will be invalidated by growing.
200 void assertSafeToAddRange(const T *From, const T *To) {
201 if (From == To)
202 return;
203 this->assertSafeToAdd(From, To - From);
204 this->assertSafeToAdd(To - 1, To - From);
205 }
206 template <
207 class ItTy,
208 std::enable_if_t<!std::is_same<std::remove_const_t<ItTy>, T *>::value,
209 bool> = false>
210 void assertSafeToAddRange(ItTy, ItTy) {}
211
212 /// Reserve enough space to add one element, and return the updated element
213 /// pointer in case it was a reference to the storage.
214 template <class U>
215 static const T *reserveForParamAndGetAddressImpl(U *This, const T &Elt,
216 size_t N) {
217 size_t NewSize = This->size() + N;
218 if (LLVM_LIKELY(NewSize <= This->capacity())__builtin_expect((bool)(NewSize <= This->capacity()), true
)
)
219 return &Elt;
220
221 bool ReferencesStorage = false;
222 int64_t Index = -1;
223 if (!U::TakesParamByValue) {
224 if (LLVM_UNLIKELY(This->isReferenceToStorage(&Elt))__builtin_expect((bool)(This->isReferenceToStorage(&Elt
)), false)
) {
225 ReferencesStorage = true;
226 Index = &Elt - This->begin();
227 }
228 }
229 This->grow(NewSize);
230 return ReferencesStorage ? This->begin() + Index : &Elt;
231 }
232
233public:
234 using size_type = size_t;
235 using difference_type = ptrdiff_t;
236 using value_type = T;
237 using iterator = T *;
238 using const_iterator = const T *;
239
240 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
241 using reverse_iterator = std::reverse_iterator<iterator>;
242
243 using reference = T &;
244 using const_reference = const T &;
245 using pointer = T *;
246 using const_pointer = const T *;
247
248 using Base::capacity;
249 using Base::empty;
250 using Base::size;
251
252 // forward iterator creation methods.
253 iterator begin() { return (iterator)this->BeginX; }
254 const_iterator begin() const { return (const_iterator)this->BeginX; }
255 iterator end() { return begin() + size(); }
256 const_iterator end() const { return begin() + size(); }
257
258 // reverse iterator creation methods.
259 reverse_iterator rbegin() { return reverse_iterator(end()); }
260 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
261 reverse_iterator rend() { return reverse_iterator(begin()); }
262 const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
263
264 size_type size_in_bytes() const { return size() * sizeof(T); }
265 size_type max_size() const {
266 return std::min(this->SizeTypeMax(), size_type(-1) / sizeof(T));
267 }
268
269 size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
270
271 /// Return a pointer to the vector's buffer, even if empty().
272 pointer data() { return pointer(begin()); }
273 /// Return a pointer to the vector's buffer, even if empty().
274 const_pointer data() const { return const_pointer(begin()); }
275
276 reference operator[](size_type idx) {
277 assert(idx < size())(static_cast <bool> (idx < size()) ? void (0) : __assert_fail
("idx < size()", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 277, __extension__ __PRETTY_FUNCTION__))
;
278 return begin()[idx];
279 }
280 const_reference operator[](size_type idx) const {
281 assert(idx < size())(static_cast <bool> (idx < size()) ? void (0) : __assert_fail
("idx < size()", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 281, __extension__ __PRETTY_FUNCTION__))
;
282 return begin()[idx];
283 }
284
285 reference front() {
286 assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
("!empty()", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 286, __extension__ __PRETTY_FUNCTION__))
;
287 return begin()[0];
288 }
289 const_reference front() const {
290 assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
("!empty()", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 290, __extension__ __PRETTY_FUNCTION__))
;
291 return begin()[0];
292 }
293
294 reference back() {
295 assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
("!empty()", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 295, __extension__ __PRETTY_FUNCTION__))
;
296 return end()[-1];
297 }
298 const_reference back() const {
299 assert(!empty())(static_cast <bool> (!empty()) ? void (0) : __assert_fail
("!empty()", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 299, __extension__ __PRETTY_FUNCTION__))
;
300 return end()[-1];
301 }
302};
303
304/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put
305/// method implementations that are designed to work with non-trivial T's.
306///
307/// We approximate is_trivially_copyable with trivial move/copy construction and
308/// trivial destruction. While the standard doesn't specify that you're allowed
309/// copy these types with memcpy, there is no way for the type to observe this.
310/// This catches the important case of std::pair<POD, POD>, which is not
311/// trivially assignable.
312template <typename T, bool = (is_trivially_copy_constructible<T>::value) &&
313 (is_trivially_move_constructible<T>::value) &&
314 std::is_trivially_destructible<T>::value>
315class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
316 friend class SmallVectorTemplateCommon<T>;
317
318protected:
319 static constexpr bool TakesParamByValue = false;
320 using ValueParamT = const T &;
321
322 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
323
324 static void destroy_range(T *S, T *E) {
325 while (S != E) {
326 --E;
327 E->~T();
328 }
329 }
330
331 /// Move the range [I, E) into the uninitialized memory starting with "Dest",
332 /// constructing elements as needed.
333 template<typename It1, typename It2>
334 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
335 std::uninitialized_copy(std::make_move_iterator(I),
336 std::make_move_iterator(E), Dest);
337 }
338
339 /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
340 /// constructing elements as needed.
341 template<typename It1, typename It2>
342 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
343 std::uninitialized_copy(I, E, Dest);
344 }
345
346 /// Grow the allocated memory (without initializing new elements), doubling
347 /// the size of the allocated memory. Guarantees space for at least one more
348 /// element, or MinSize more elements if specified.
349 void grow(size_t MinSize = 0);
350
351 /// Create a new allocation big enough for \p MinSize and pass back its size
352 /// in \p NewCapacity. This is the first section of \a grow().
353 T *mallocForGrow(size_t MinSize, size_t &NewCapacity) {
354 return static_cast<T *>(
355 SmallVectorBase<SmallVectorSizeType<T>>::mallocForGrow(
356 MinSize, sizeof(T), NewCapacity));
357 }
358
359 /// Move existing elements over to the new allocation \p NewElts, the middle
360 /// section of \a grow().
361 void moveElementsForGrow(T *NewElts);
362
363 /// Transfer ownership of the allocation, finishing up \a grow().
364 void takeAllocationForGrow(T *NewElts, size_t NewCapacity);
365
366 /// Reserve enough space to add one element, and return the updated element
367 /// pointer in case it was a reference to the storage.
368 const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
369 return this->reserveForParamAndGetAddressImpl(this, Elt, N);
370 }
371
372 /// Reserve enough space to add one element, and return the updated element
373 /// pointer in case it was a reference to the storage.
374 T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
375 return const_cast<T *>(
376 this->reserveForParamAndGetAddressImpl(this, Elt, N));
377 }
378
379 static T &&forward_value_param(T &&V) { return std::move(V); }
380 static const T &forward_value_param(const T &V) { return V; }
381
382 void growAndAssign(size_t NumElts, const T &Elt) {
383 // Grow manually in case Elt is an internal reference.
384 size_t NewCapacity;
385 T *NewElts = mallocForGrow(NumElts, NewCapacity);
386 std::uninitialized_fill_n(NewElts, NumElts, Elt);
387 this->destroy_range(this->begin(), this->end());
388 takeAllocationForGrow(NewElts, NewCapacity);
389 this->set_size(NumElts);
390 }
391
392 template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
393 // Grow manually in case one of Args is an internal reference.
394 size_t NewCapacity;
395 T *NewElts = mallocForGrow(0, NewCapacity);
396 ::new ((void *)(NewElts + this->size())) T(std::forward<ArgTypes>(Args)...);
397 moveElementsForGrow(NewElts);
398 takeAllocationForGrow(NewElts, NewCapacity);
399 this->set_size(this->size() + 1);
400 return this->back();
401 }
402
403public:
404 void push_back(const T &Elt) {
405 const T *EltPtr = reserveForParamAndGetAddress(Elt);
406 ::new ((void *)this->end()) T(*EltPtr);
407 this->set_size(this->size() + 1);
408 }
409
410 void push_back(T &&Elt) {
411 T *EltPtr = reserveForParamAndGetAddress(Elt);
412 ::new ((void *)this->end()) T(::std::move(*EltPtr));
413 this->set_size(this->size() + 1);
414 }
415
416 void pop_back() {
417 this->set_size(this->size() - 1);
418 this->end()->~T();
419 }
420};
421
422// Define this out-of-line to dissuade the C++ compiler from inlining it.
423template <typename T, bool TriviallyCopyable>
424void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
425 size_t NewCapacity;
426 T *NewElts = mallocForGrow(MinSize, NewCapacity);
427 moveElementsForGrow(NewElts);
428 takeAllocationForGrow(NewElts, NewCapacity);
429}
430
431// Define this out-of-line to dissuade the C++ compiler from inlining it.
432template <typename T, bool TriviallyCopyable>
433void SmallVectorTemplateBase<T, TriviallyCopyable>::moveElementsForGrow(
434 T *NewElts) {
435 // Move the elements over.
436 this->uninitialized_move(this->begin(), this->end(), NewElts);
437
438 // Destroy the original elements.
439 destroy_range(this->begin(), this->end());
440}
441
442// Define this out-of-line to dissuade the C++ compiler from inlining it.
443template <typename T, bool TriviallyCopyable>
444void SmallVectorTemplateBase<T, TriviallyCopyable>::takeAllocationForGrow(
445 T *NewElts, size_t NewCapacity) {
446 // If this wasn't grown from the inline copy, deallocate the old space.
447 if (!this->isSmall())
448 free(this->begin());
449
450 this->BeginX = NewElts;
451 this->Capacity = NewCapacity;
452}
453
454/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
455/// method implementations that are designed to work with trivially copyable
456/// T's. This allows using memcpy in place of copy/move construction and
457/// skipping destruction.
458template <typename T>
459class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
460 friend class SmallVectorTemplateCommon<T>;
461
462protected:
463 /// True if it's cheap enough to take parameters by value. Doing so avoids
464 /// overhead related to mitigations for reference invalidation.
465 static constexpr bool TakesParamByValue = sizeof(T) <= 2 * sizeof(void *);
466
467 /// Either const T& or T, depending on whether it's cheap enough to take
468 /// parameters by value.
469 using ValueParamT =
470 typename std::conditional<TakesParamByValue, T, const T &>::type;
471
472 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
473
474 // No need to do a destroy loop for POD's.
475 static void destroy_range(T *, T *) {}
476
477 /// Move the range [I, E) onto the uninitialized memory
478 /// starting with "Dest", constructing elements into it as needed.
479 template<typename It1, typename It2>
480 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
481 // Just do a copy.
482 uninitialized_copy(I, E, Dest);
483 }
484
485 /// Copy the range [I, E) onto the uninitialized memory
486 /// starting with "Dest", constructing elements into it as needed.
487 template<typename It1, typename It2>
488 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
489 // Arbitrary iterator types; just use the basic implementation.
490 std::uninitialized_copy(I, E, Dest);
491 }
492
493 /// Copy the range [I, E) onto the uninitialized memory
494 /// starting with "Dest", constructing elements into it as needed.
495 template <typename T1, typename T2>
496 static void uninitialized_copy(
497 T1 *I, T1 *E, T2 *Dest,
498 std::enable_if_t<std::is_same<typename std::remove_const<T1>::type,
499 T2>::value> * = nullptr) {
500 // Use memcpy for PODs iterated by pointers (which includes SmallVector
501 // iterators): std::uninitialized_copy optimizes to memmove, but we can
502 // use memcpy here. Note that I and E are iterators and thus might be
503 // invalid for memcpy if they are equal.
504 if (I != E)
505 memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
506 }
507
508 /// Double the size of the allocated memory, guaranteeing space for at
509 /// least one more element or MinSize if specified.
510 void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
511
512 /// Reserve enough space to add one element, and return the updated element
513 /// pointer in case it was a reference to the storage.
514 const T *reserveForParamAndGetAddress(const T &Elt, size_t N = 1) {
515 return this->reserveForParamAndGetAddressImpl(this, Elt, N);
516 }
517
518 /// Reserve enough space to add one element, and return the updated element
519 /// pointer in case it was a reference to the storage.
520 T *reserveForParamAndGetAddress(T &Elt, size_t N = 1) {
521 return const_cast<T *>(
522 this->reserveForParamAndGetAddressImpl(this, Elt, N));
523 }
524
525 /// Copy \p V or return a reference, depending on \a ValueParamT.
526 static ValueParamT forward_value_param(ValueParamT V) { return V; }
527
528 void growAndAssign(size_t NumElts, T Elt) {
529 // Elt has been copied in case it's an internal reference, side-stepping
530 // reference invalidation problems without losing the realloc optimization.
531 this->set_size(0);
532 this->grow(NumElts);
533 std::uninitialized_fill_n(this->begin(), NumElts, Elt);
534 this->set_size(NumElts);
535 }
536
537 template <typename... ArgTypes> T &growAndEmplaceBack(ArgTypes &&... Args) {
538 // Use push_back with a copy in case Args has an internal reference,
539 // side-stepping reference invalidation problems without losing the realloc
540 // optimization.
541 push_back(T(std::forward<ArgTypes>(Args)...));
542 return this->back();
543 }
544
545public:
546 void push_back(ValueParamT Elt) {
547 const T *EltPtr = reserveForParamAndGetAddress(Elt);
548 memcpy(reinterpret_cast<void *>(this->end()), EltPtr, sizeof(T));
549 this->set_size(this->size() + 1);
550 }
551
552 void pop_back() { this->set_size(this->size() - 1); }
553};
554
555/// This class consists of common code factored out of the SmallVector class to
556/// reduce code duplication based on the SmallVector 'N' template parameter.
557template <typename T>
558class SmallVectorImpl : public SmallVectorTemplateBase<T> {
559 using SuperClass = SmallVectorTemplateBase<T>;
560
561public:
562 using iterator = typename SuperClass::iterator;
563 using const_iterator = typename SuperClass::const_iterator;
564 using reference = typename SuperClass::reference;
565 using size_type = typename SuperClass::size_type;
566
567protected:
568 using SmallVectorTemplateBase<T>::TakesParamByValue;
569 using ValueParamT = typename SuperClass::ValueParamT;
570
571 // Default ctor - Initialize to empty.
572 explicit SmallVectorImpl(unsigned N)
573 : SmallVectorTemplateBase<T>(N) {}
574
575public:
576 SmallVectorImpl(const SmallVectorImpl &) = delete;
577
578 ~SmallVectorImpl() {
579 // Subclass has already destructed this vector's elements.
580 // If this wasn't grown from the inline copy, deallocate the old space.
581 if (!this->isSmall())
582 free(this->begin());
583 }
584
585 void clear() {
586 this->destroy_range(this->begin(), this->end());
587 this->Size = 0;
588 }
589
590private:
591 template <bool ForOverwrite> void resizeImpl(size_type N) {
592 if (N < this->size()) {
593 this->pop_back_n(this->size() - N);
594 } else if (N > this->size()) {
595 this->reserve(N);
596 for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
597 if (ForOverwrite)
598 new (&*I) T;
599 else
600 new (&*I) T();
601 this->set_size(N);
602 }
603 }
604
605public:
606 void resize(size_type N) { resizeImpl<false>(N); }
607
608 /// Like resize, but \ref T is POD, the new values won't be initialized.
609 void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
610
611 void resize(size_type N, ValueParamT NV) {
612 if (N == this->size())
613 return;
614
615 if (N < this->size()) {
616 this->pop_back_n(this->size() - N);
617 return;
618 }
619
620 // N > this->size(). Defer to append.
621 this->append(N - this->size(), NV);
622 }
623
624 void reserve(size_type N) {
625 if (this->capacity() < N)
626 this->grow(N);
627 }
628
629 void pop_back_n(size_type NumItems) {
630 assert(this->size() >= NumItems)(static_cast <bool> (this->size() >= NumItems) ? void
(0) : __assert_fail ("this->size() >= NumItems", "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 630, __extension__ __PRETTY_FUNCTION__))
;
631 this->destroy_range(this->end() - NumItems, this->end());
632 this->set_size(this->size() - NumItems);
633 }
634
635 LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() {
636 T Result = ::std::move(this->back());
637 this->pop_back();
638 return Result;
639 }
640
641 void swap(SmallVectorImpl &RHS);
642
643 /// Add the specified range to the end of the SmallVector.
644 template <typename in_iter,
645 typename = std::enable_if_t<std::is_convertible<
646 typename std::iterator_traits<in_iter>::iterator_category,
647 std::input_iterator_tag>::value>>
648 void append(in_iter in_start, in_iter in_end) {
649 this->assertSafeToAddRange(in_start, in_end);
650 size_type NumInputs = std::distance(in_start, in_end);
651 this->reserve(this->size() + NumInputs);
652 this->uninitialized_copy(in_start, in_end, this->end());
653 this->set_size(this->size() + NumInputs);
654 }
655
656 /// Append \p NumInputs copies of \p Elt to the end.
657 void append(size_type NumInputs, ValueParamT Elt) {
658 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);
659 std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
660 this->set_size(this->size() + NumInputs);
661 }
662
663 void append(std::initializer_list<T> IL) {
664 append(IL.begin(), IL.end());
665 }
666
667 void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); }
668
669 void assign(size_type NumElts, ValueParamT Elt) {
670 // Note that Elt could be an internal reference.
671 if (NumElts > this->capacity()) {
672 this->growAndAssign(NumElts, Elt);
673 return;
674 }
675
676 // Assign over existing elements.
677 std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
678 if (NumElts > this->size())
679 std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);
680 else if (NumElts < this->size())
681 this->destroy_range(this->begin() + NumElts, this->end());
682 this->set_size(NumElts);
683 }
684
685 // FIXME: Consider assigning over existing elements, rather than clearing &
686 // re-initializing them - for all assign(...) variants.
687
688 template <typename in_iter,
689 typename = std::enable_if_t<std::is_convertible<
690 typename std::iterator_traits<in_iter>::iterator_category,
691 std::input_iterator_tag>::value>>
692 void assign(in_iter in_start, in_iter in_end) {
693 this->assertSafeToReferenceAfterClear(in_start, in_end);
694 clear();
695 append(in_start, in_end);
696 }
697
698 void assign(std::initializer_list<T> IL) {
699 clear();
700 append(IL);
701 }
702
703 void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); }
704
705 iterator erase(const_iterator CI) {
706 // Just cast away constness because this is a non-const member function.
707 iterator I = const_cast<iterator>(CI);
708
709 assert(this->isReferenceToStorage(CI) && "Iterator to erase is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(CI) &&
"Iterator to erase is out of bounds.") ? void (0) : __assert_fail
("this->isReferenceToStorage(CI) && \"Iterator to erase is out of bounds.\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 709, __extension__ __PRETTY_FUNCTION__))
;
710
711 iterator N = I;
712 // Shift all elts down one.
713 std::move(I+1, this->end(), I);
714 // Drop the last elt.
715 this->pop_back();
716 return(N);
717 }
718
719 iterator erase(const_iterator CS, const_iterator CE) {
720 // Just cast away constness because this is a non-const member function.
721 iterator S = const_cast<iterator>(CS);
722 iterator E = const_cast<iterator>(CE);
723
724 assert(this->isRangeInStorage(S, E) && "Range to erase is out of bounds.")(static_cast <bool> (this->isRangeInStorage(S, E) &&
"Range to erase is out of bounds.") ? void (0) : __assert_fail
("this->isRangeInStorage(S, E) && \"Range to erase is out of bounds.\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 724, __extension__ __PRETTY_FUNCTION__))
;
725
726 iterator N = S;
727 // Shift all elts down.
728 iterator I = std::move(E, this->end(), S);
729 // Drop the last elts.
730 this->destroy_range(I, this->end());
731 this->set_size(I - this->begin());
732 return(N);
733 }
734
735private:
736 template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
737 // Callers ensure that ArgType is derived from T.
738 static_assert(
739 std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
740 T>::value,
741 "ArgType must be derived from T!");
742
743 if (I == this->end()) { // Important special case for empty vector.
744 this->push_back(::std::forward<ArgType>(Elt));
745 return this->end()-1;
746 }
747
748 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) &&
"Insertion iterator is out of bounds.") ? void (0) : __assert_fail
("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 748, __extension__ __PRETTY_FUNCTION__))
;
749
750 // Grow if necessary.
751 size_t Index = I - this->begin();
752 std::remove_reference_t<ArgType> *EltPtr =
753 this->reserveForParamAndGetAddress(Elt);
754 I = this->begin() + Index;
755
756 ::new ((void*) this->end()) T(::std::move(this->back()));
757 // Push everything else over.
758 std::move_backward(I, this->end()-1, this->end());
759 this->set_size(this->size() + 1);
760
761 // If we just moved the element we're inserting, be sure to update
762 // the reference (never happens if TakesParamByValue).
763 static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value,
764 "ArgType must be 'T' when taking by value!");
765 if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end()))
766 ++EltPtr;
767
768 *I = ::std::forward<ArgType>(*EltPtr);
769 return I;
770 }
771
772public:
773 iterator insert(iterator I, T &&Elt) {
774 return insert_one_impl(I, this->forward_value_param(std::move(Elt)));
775 }
776
777 iterator insert(iterator I, const T &Elt) {
778 return insert_one_impl(I, this->forward_value_param(Elt));
779 }
780
781 iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) {
782 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
783 size_t InsertElt = I - this->begin();
784
785 if (I == this->end()) { // Important special case for empty vector.
786 append(NumToInsert, Elt);
787 return this->begin()+InsertElt;
788 }
789
790 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) &&
"Insertion iterator is out of bounds.") ? void (0) : __assert_fail
("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 790, __extension__ __PRETTY_FUNCTION__))
;
791
792 // Ensure there is enough space, and get the (maybe updated) address of
793 // Elt.
794 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert);
795
796 // Uninvalidate the iterator.
797 I = this->begin()+InsertElt;
798
799 // If there are more elements between the insertion point and the end of the
800 // range than there are being inserted, we can use a simple approach to
801 // insertion. Since we already reserved space, we know that this won't
802 // reallocate the vector.
803 if (size_t(this->end()-I) >= NumToInsert) {
804 T *OldEnd = this->end();
805 append(std::move_iterator<iterator>(this->end() - NumToInsert),
806 std::move_iterator<iterator>(this->end()));
807
808 // Copy the existing elements that get replaced.
809 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
810
811 // If we just moved the element we're inserting, be sure to update
812 // the reference (never happens if TakesParamByValue).
813 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
814 EltPtr += NumToInsert;
815
816 std::fill_n(I, NumToInsert, *EltPtr);
817 return I;
818 }
819
820 // Otherwise, we're inserting more elements than exist already, and we're
821 // not inserting at the end.
822
823 // Move over the elements that we're about to overwrite.
824 T *OldEnd = this->end();
825 this->set_size(this->size() + NumToInsert);
826 size_t NumOverwritten = OldEnd-I;
827 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
828
829 // If we just moved the element we're inserting, be sure to update
830 // the reference (never happens if TakesParamByValue).
831 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
832 EltPtr += NumToInsert;
833
834 // Replace the overwritten part.
835 std::fill_n(I, NumOverwritten, *EltPtr);
836
837 // Insert the non-overwritten middle part.
838 std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
839 return I;
840 }
841
842 template <typename ItTy,
843 typename = std::enable_if_t<std::is_convertible<
844 typename std::iterator_traits<ItTy>::iterator_category,
845 std::input_iterator_tag>::value>>
846 iterator insert(iterator I, ItTy From, ItTy To) {
847 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
848 size_t InsertElt = I - this->begin();
849
850 if (I == this->end()) { // Important special case for empty vector.
851 append(From, To);
852 return this->begin()+InsertElt;
853 }
854
855 assert(this->isReferenceToStorage(I) && "Insertion iterator is out of bounds.")(static_cast <bool> (this->isReferenceToStorage(I) &&
"Insertion iterator is out of bounds.") ? void (0) : __assert_fail
("this->isReferenceToStorage(I) && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-14~++20210926122410+d23fd8ae8906/llvm/include/llvm/ADT/SmallVector.h"
, 855, __extension__ __PRETTY_FUNCTION__))
;
856
857 // Check that the reserve that follows doesn't invalidate the iterators.
858 this->assertSafeToAddRange(From, To);
859
860 size_t NumToInsert = std::distance(From, To);
861
862 // Ensure there is enough space.
863 reserve(this->size() + NumToInsert);
864
865 // Uninvalidate the iterator.
866 I = this->begin()+InsertElt;
867
868 // If there are more elements between the insertion point and the end of the
869 // range than there are being inserted, we can use a simple approach to
870 // insertion. Since we already reserved space, we know that this won't
871 // reallocate the vector.
872 if (size_t(this->end()-I) >= NumToInsert) {
873 T *OldEnd = this->end();
874 append(std::move_iterator<iterator>(this->end() - NumToInsert),
875 std::move_iterator<iterator>(this->end()));
876
877 // Copy the existing elements that get replaced.
878 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
879
880 std::copy(From, To, I);
881 return I;
882 }
883
884 // Otherwise, we're inserting more elements than exist already, and we're
885 // not inserting at the end.
886
887 // Move over the elements that we're about to overwrite.
888 T *OldEnd = this->end();
889 this->set_size(this->size() + NumToInsert);
890 size_t NumOverwritten = OldEnd-I;
891 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
892
893 // Replace the overwritten part.
894 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
895 *J = *From;
896 ++J; ++From;
897 }
898
899 // Insert the non-overwritten middle part.
900 this->uninitialized_copy(From, To, OldEnd);
901 return I;
902 }
903
904 void insert(iterator I, std::initializer_list<T> IL) {
905 insert(I, IL.begin(), IL.end());
906 }
907
908 template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
909 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
910 return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...);
911
912 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
913 this->set_size(this->size() + 1);
914 return this->back();
915 }
916
917 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
918
919 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
920
921 bool operator==(const SmallVectorImpl &RHS) const {
922 if (this->size() != RHS.size()) return false;
923 return std::equal(this->begin(), this->end(), RHS.begin());
924 }
925 bool operator!=(const SmallVectorImpl &RHS) const {
926 return !(*this == RHS);
927 }
928
929 bool operator<(const SmallVectorImpl &RHS) const {
930 return std::lexicographical_compare(this->begin(), this->end(),
931 RHS.begin(), RHS.end());
932 }
933};
934
935template <typename T>
936void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
937 if (this == &RHS) return;
938
939 // We can only avoid copying elements if neither vector is small.
940 if (!this->isSmall() && !RHS.isSmall()) {
941 std::swap(this->BeginX, RHS.BeginX);
942 std::swap(this->Size, RHS.Size);
943 std::swap(this->Capacity, RHS.Capacity);
944 return;
945 }
946 this->reserve(RHS.size());
947 RHS.reserve(this->size());
948
949 // Swap the shared elements.
950 size_t NumShared = this->size();
951 if (NumShared > RHS.size()) NumShared = RHS.size();
952 for (size_type i = 0; i != NumShared; ++i)
953 std::swap((*this)[i], RHS[i]);
954
955 // Copy over the extra elts.
956 if (this->size() > RHS.size()) {
957 size_t EltDiff = this->size() - RHS.size();
958 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
959 RHS.set_size(RHS.size() + EltDiff);
960 this->destroy_range(this->begin()+NumShared, this->end());
961 this->set_size(NumShared);
962 } else if (RHS.size() > this->size()) {
963 size_t EltDiff = RHS.size() - this->size();
964 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
965 this->set_size(this->size() + EltDiff);
966 this->destroy_range(RHS.begin()+NumShared, RHS.end());
967 RHS.set_size(NumShared);
968 }
969}
970
971template <typename T>
972SmallVectorImpl<T> &SmallVectorImpl<T>::
973 operator=(const SmallVectorImpl<T> &RHS) {
974 // Avoid self-assignment.
975 if (this == &RHS) return *this;
976
977 // If we already have sufficient space, assign the common elements, then
978 // destroy any excess.
979 size_t RHSSize = RHS.size();
980 size_t CurSize = this->size();
981 if (CurSize >= RHSSize) {
982 // Assign common elements.
983 iterator NewEnd;
984 if (RHSSize)
985 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
986 else
987 NewEnd = this->begin();
988
989 // Destroy excess elements.
990 this->destroy_range(NewEnd, this->end());
991
992 // Trim.
993 this->set_size(RHSSize);
994 return *this;
995 }
996
997 // If we have to grow to have enough elements, destroy the current elements.
998 // This allows us to avoid copying them during the grow.
999 // FIXME: don't do this if they're efficiently moveable.
1000 if (this->capacity() < RHSSize) {
1001 // Destroy current elements.
1002 this->clear();
1003 CurSize = 0;
1004 this->grow(RHSSize);
1005 } else if (CurSize) {
1006 // Otherwise, use assignment for the already-constructed elements.
1007 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
1008 }
1009
1010 // Copy construct the new elements in place.
1011 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
1012 this->begin()+CurSize);
1013
1014 // Set end.
1015 this->set_size(RHSSize);
1016 return *this;
1017}
1018
1019template <typename T>
1020SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
1021 // Avoid self-assignment.
1022 if (this == &RHS) return *this;
1023
1024 // If the RHS isn't small, clear this vector and then steal its buffer.
1025 if (!RHS.isSmall()) {
1026 this->destroy_range(this->begin(), this->end());
1027 if (!this->isSmall()) free(this->begin());
1028 this->BeginX = RHS.BeginX;
1029 this->Size = RHS.Size;
1030 this->Capacity = RHS.Capacity;
1031 RHS.resetToSmall();
1032 return *this;
1033 }
1034
1035 // If we already have sufficient space, assign the common elements, then
1036 // destroy any excess.
1037 size_t RHSSize = RHS.size();
1038 size_t CurSize = this->size();
1039 if (CurSize >= RHSSize) {
1040 // Assign common elements.
1041 iterator NewEnd = this->begin();
1042 if (RHSSize)
1043 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
1044
1045 // Destroy excess elements and trim the bounds.
1046 this->destroy_range(NewEnd, this->end());
1047 this->set_size(RHSSize);
1048
1049 // Clear the RHS.
1050 RHS.clear();
1051
1052 return *this;
1053 }
1054
1055 // If we have to grow to have enough elements, destroy the current elements.
1056 // This allows us to avoid copying them during the grow.
1057 // FIXME: this may not actually make any sense if we can efficiently move
1058 // elements.
1059 if (this->capacity() < RHSSize) {
1060 // Destroy current elements.
1061 this->clear();
1062 CurSize = 0;
1063 this->grow(RHSSize);
1064 } else if (CurSize) {
1065 // Otherwise, use assignment for the already-constructed elements.
1066 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
1067 }
1068
1069 // Move-construct the new elements in place.
1070 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
1071 this->begin()+CurSize);
1072
1073 // Set end.
1074 this->set_size(RHSSize);
1075
1076 RHS.clear();
1077 return *this;
1078}
1079
1080/// Storage for the SmallVector elements. This is specialized for the N=0 case
1081/// to avoid allocating unnecessary storage.
1082template <typename T, unsigned N>
1083struct SmallVectorStorage {
1084 alignas(T) char InlineElts[N * sizeof(T)];
1085};
1086
1087/// We need the storage to be properly aligned even for small-size of 0 so that
1088/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
1089/// well-defined.
1090template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};
1091
1092/// Forward declaration of SmallVector so that
1093/// calculateSmallVectorDefaultInlinedElements can reference
1094/// `sizeof(SmallVector<T, 0>)`.
1095template <typename T, unsigned N> class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector;
1096
1097/// Helper class for calculating the default number of inline elements for
1098/// `SmallVector<T>`.
1099///
1100/// This should be migrated to a constexpr function when our minimum
1101/// compiler support is enough for multi-statement constexpr functions.
1102template <typename T> struct CalculateSmallVectorDefaultInlinedElements {
1103 // Parameter controlling the default number of inlined elements
1104 // for `SmallVector<T>`.
1105 //
1106 // The default number of inlined elements ensures that
1107 // 1. There is at least one inlined element.
1108 // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
1109 // it contradicts 1.
1110 static constexpr size_t kPreferredSmallVectorSizeof = 64;
1111
1112 // static_assert that sizeof(T) is not "too big".
1113 //
1114 // Because our policy guarantees at least one inlined element, it is possible
1115 // for an arbitrarily large inlined element to allocate an arbitrarily large
1116 // amount of inline storage. We generally consider it an antipattern for a
1117 // SmallVector to allocate an excessive amount of inline storage, so we want
1118 // to call attention to these cases and make sure that users are making an
1119 // intentional decision if they request a lot of inline storage.
1120 //
1121 // We want this assertion to trigger in pathological cases, but otherwise
1122 // not be too easy to hit. To accomplish that, the cutoff is actually somewhat
1123 // larger than kPreferredSmallVectorSizeof (otherwise,
1124 // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
1125 // pattern seems useful in practice).
1126 //
1127 // One wrinkle is that this assertion is in theory non-portable, since
1128 // sizeof(T) is in general platform-dependent. However, we don't expect this
1129 // to be much of an issue, because most LLVM development happens on 64-bit
1130 // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for
1131 // 32-bit hosts, dodging the issue. The reverse situation, where development
1132 // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a
1133 // 64-bit host, is expected to be very rare.
1134 static_assert(
1135 sizeof(T) <= 256,
1136 "You are trying to use a default number of inlined elements for "
1137 "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
1138 "explicit number of inlined elements with `SmallVector<T, N>` to make "
1139 "sure you really want that much inline storage.");
1140
1141 // Discount the size of the header itself when calculating the maximum inline
1142 // bytes.
1143 static constexpr size_t PreferredInlineBytes =
1144 kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
1145 static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T);
1146 static constexpr size_t value =
1147 NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
1148};
1149
1150/// This is a 'vector' (really, a variable-sized array), optimized
1151/// for the case when the array is small. It contains some number of elements
1152/// in-place, which allows it to avoid heap allocation when the actual number of
1153/// elements is below that threshold. This allows normal "small" cases to be
1154/// fast without losing generality for large inputs.
1155///
1156/// \note
1157/// In the absence of a well-motivated choice for the number of inlined
1158/// elements \p N, it is recommended to use \c SmallVector<T> (that is,
1159/// omitting the \p N). This will choose a default number of inlined elements
1160/// reasonable for allocation on the stack (for example, trying to keep \c
1161/// sizeof(SmallVector<T>) around 64 bytes).
1162///
1163/// \warning This does not attempt to be exception safe.
1164///
1165/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h
1166template <typename T,
1167 unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value>
1168class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector : public SmallVectorImpl<T>,
1169 SmallVectorStorage<T, N> {
1170public:
1171 SmallVector() : SmallVectorImpl<T>(N) {}
1172
1173 ~SmallVector() {
1174 // Destroy the constructed elements in the vector.
1175 this->destroy_range(this->begin(), this->end());
1176 }
1177
1178 explicit SmallVector(size_t Size, const T &Value = T())
1179 : SmallVectorImpl<T>(N) {
1180 this->assign(Size, Value);
1181 }
1182
1183 template <typename ItTy,
1184 typename = std::enable_if_t<std::is_convertible<
1185 typename std::iterator_traits<ItTy>::iterator_category,
1186 std::input_iterator_tag>::value>>
1187 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
1188 this->append(S, E);
1189 }
1190
1191 template <typename RangeTy>
1192 explicit SmallVector(const iterator_range<RangeTy> &R)
1193 : SmallVectorImpl<T>(N) {
1194 this->append(R.begin(), R.end());
1195 }
1196
1197 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
1198 this->assign(IL);
1199 }
1200
1201 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
1202 if (!RHS.empty())
1203 SmallVectorImpl<T>::operator=(RHS);
1204 }
1205
1206 SmallVector &operator=(const SmallVector &RHS) {
1207 SmallVectorImpl<T>::operator=(RHS);
1208 return *this;
1209 }
1210
1211 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
1212 if (!RHS.empty())
1213 SmallVectorImpl<T>::operator=(::std::move(RHS));
1214 }
1215
1216 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
1217 if (!RHS.empty())
1218 SmallVectorImpl<T>::operator=(::std::move(RHS));
1219 }
1220
1221 SmallVector &operator=(SmallVector &&RHS) {
1222 SmallVectorImpl<T>::operator=(::std::move(RHS));
1223 return *this;
1224 }
1225
1226 SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
1227 SmallVectorImpl<T>::operator=(::std::move(RHS));
1228 return *this;
1229 }
1230
1231 SmallVector &operator=(std::initializer_list<T> IL) {
1232 this->assign(IL);
1233 return *this;
1234 }
1235};
1236
1237template <typename T, unsigned N>
1238inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
1239 return X.capacity_in_bytes();
1240}
1241
1242/// Given a range of type R, iterate the entire range and return a
1243/// SmallVector with elements of the vector. This is useful, for example,
1244/// when you want to iterate a range and then sort the results.
1245template <unsigned Size, typename R>
1246SmallVector<typename std::remove_const<typename std::remove_reference<
1247 decltype(*std::begin(std::declval<R &>()))>::type>::type,
1248 Size>
1249to_vector(R &&Range) {
1250 return {std::begin(Range), std::end(Range)};
1251}
1252
1253} // end namespace llvm
1254
1255namespace std {
1256
1257 /// Implement std::swap in terms of SmallVector swap.
1258 template<typename T>
1259 inline void
1260 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
1261 LHS.swap(RHS);
1262 }
1263
1264 /// Implement std::swap in terms of SmallVector swap.
1265 template<typename T, unsigned N>
1266 inline void
1267 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
1268 LHS.swap(RHS);
1269 }
1270
1271} // end namespace std
1272
1273#endif // LLVM_ADT_SMALLVECTOR_H