Bug Summary

File:llvm/lib/Transforms/IPO/GlobalOpt.cpp
Warning:line 2212, 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 -clear-ast-before-backend -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 -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20220103100629+c40049d6d7f1/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~++20220103100629+c40049d6d7f1/llvm/lib/Transforms/IPO -I include -I /build/llvm-toolchain-snapshot-14~++20220103100629+c40049d6d7f1/llvm/include -D _FORTIFY_SOURCE=2 -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 -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220103100629+c40049d6d7f1/build-llvm=build-llvm -fmacro-prefix-map=/build/llvm-toolchain-snapshot-14~++20220103100629+c40049d6d7f1/= -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220103100629+c40049d6d7f1/build-llvm=build-llvm -fcoverage-prefix-map=/build/llvm-toolchain-snapshot-14~++20220103100629+c40049d6d7f1/= -O3 -Wno-unused-command-line-argument -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~++20220103100629+c40049d6d7f1/build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220103100629+c40049d6d7f1/build-llvm=build-llvm -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20220103100629+c40049d6d7f1/= -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -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-2022-01-03-232337-130088-1 -x c++ /build/llvm-toolchain-snapshot-14~++20220103100629+c40049d6d7f1/llvm/lib/Transforms/IPO/GlobalOpt.cpp

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

/build/llvm-toolchain-snapshot-14~++20220103100629+c40049d6d7f1/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()", "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\""
, "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\""
, "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\""
, "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()", "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()", "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()", "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()", "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()", "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()", "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 return;
594
595 if (N < this->size()) {
596 this->truncate(N);
597 return;
598 }
599
600 this->reserve(N);
601 for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
602 if (ForOverwrite)
603 new (&*I) T;
604 else
605 new (&*I) T();
606 this->set_size(N);
607 }
608
609public:
610 void resize(size_type N) { resizeImpl<false>(N); }
611
612 /// Like resize, but \ref T is POD, the new values won't be initialized.
613 void resize_for_overwrite(size_type N) { resizeImpl<true>(N); }
614
615 /// Like resize, but requires that \p N is less than \a size().
616 void truncate(size_type N) {
617 assert(this->size() >= N && "Cannot increase size with truncate")(static_cast <bool> (this->size() >= N &&
"Cannot increase size with truncate") ? void (0) : __assert_fail
("this->size() >= N && \"Cannot increase size with truncate\""
, "llvm/include/llvm/ADT/SmallVector.h", 617, __extension__ __PRETTY_FUNCTION__
))
;
618 this->destroy_range(this->begin() + N, this->end());
619 this->set_size(N);
620 }
621
622 void resize(size_type N, ValueParamT NV) {
623 if (N == this->size())
624 return;
625
626 if (N < this->size()) {
627 this->truncate(N);
628 return;
629 }
630
631 // N > this->size(). Defer to append.
632 this->append(N - this->size(), NV);
633 }
634
635 void reserve(size_type N) {
636 if (this->capacity() < N)
637 this->grow(N);
638 }
639
640 void pop_back_n(size_type NumItems) {
641 assert(this->size() >= NumItems)(static_cast <bool> (this->size() >= NumItems) ? void
(0) : __assert_fail ("this->size() >= NumItems", "llvm/include/llvm/ADT/SmallVector.h"
, 641, __extension__ __PRETTY_FUNCTION__))
;
642 truncate(this->size() - NumItems);
643 }
644
645 LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() {
646 T Result = ::std::move(this->back());
647 this->pop_back();
648 return Result;
649 }
650
651 void swap(SmallVectorImpl &RHS);
652
653 /// Add the specified range to the end of the SmallVector.
654 template <typename in_iter,
655 typename = std::enable_if_t<std::is_convertible<
656 typename std::iterator_traits<in_iter>::iterator_category,
657 std::input_iterator_tag>::value>>
658 void append(in_iter in_start, in_iter in_end) {
659 this->assertSafeToAddRange(in_start, in_end);
660 size_type NumInputs = std::distance(in_start, in_end);
661 this->reserve(this->size() + NumInputs);
662 this->uninitialized_copy(in_start, in_end, this->end());
663 this->set_size(this->size() + NumInputs);
664 }
665
666 /// Append \p NumInputs copies of \p Elt to the end.
667 void append(size_type NumInputs, ValueParamT Elt) {
668 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumInputs);
669 std::uninitialized_fill_n(this->end(), NumInputs, *EltPtr);
670 this->set_size(this->size() + NumInputs);
671 }
672
673 void append(std::initializer_list<T> IL) {
674 append(IL.begin(), IL.end());
675 }
676
677 void append(const SmallVectorImpl &RHS) { append(RHS.begin(), RHS.end()); }
678
679 void assign(size_type NumElts, ValueParamT Elt) {
680 // Note that Elt could be an internal reference.
681 if (NumElts > this->capacity()) {
682 this->growAndAssign(NumElts, Elt);
683 return;
684 }
685
686 // Assign over existing elements.
687 std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
688 if (NumElts > this->size())
689 std::uninitialized_fill_n(this->end(), NumElts - this->size(), Elt);
690 else if (NumElts < this->size())
691 this->destroy_range(this->begin() + NumElts, this->end());
692 this->set_size(NumElts);
693 }
694
695 // FIXME: Consider assigning over existing elements, rather than clearing &
696 // re-initializing them - for all assign(...) variants.
697
698 template <typename in_iter,
699 typename = std::enable_if_t<std::is_convertible<
700 typename std::iterator_traits<in_iter>::iterator_category,
701 std::input_iterator_tag>::value>>
702 void assign(in_iter in_start, in_iter in_end) {
703 this->assertSafeToReferenceAfterClear(in_start, in_end);
704 clear();
705 append(in_start, in_end);
706 }
707
708 void assign(std::initializer_list<T> IL) {
709 clear();
710 append(IL);
711 }
712
713 void assign(const SmallVectorImpl &RHS) { assign(RHS.begin(), RHS.end()); }
714
715 iterator erase(const_iterator CI) {
716 // Just cast away constness because this is a non-const member function.
717 iterator I = const_cast<iterator>(CI);
718
719 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.\""
, "llvm/include/llvm/ADT/SmallVector.h", 719, __extension__ __PRETTY_FUNCTION__
))
;
720
721 iterator N = I;
722 // Shift all elts down one.
723 std::move(I+1, this->end(), I);
724 // Drop the last elt.
725 this->pop_back();
726 return(N);
727 }
728
729 iterator erase(const_iterator CS, const_iterator CE) {
730 // Just cast away constness because this is a non-const member function.
731 iterator S = const_cast<iterator>(CS);
732 iterator E = const_cast<iterator>(CE);
733
734 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.\""
, "llvm/include/llvm/ADT/SmallVector.h", 734, __extension__ __PRETTY_FUNCTION__
))
;
735
736 iterator N = S;
737 // Shift all elts down.
738 iterator I = std::move(E, this->end(), S);
739 // Drop the last elts.
740 this->destroy_range(I, this->end());
741 this->set_size(I - this->begin());
742 return(N);
743 }
744
745private:
746 template <class ArgType> iterator insert_one_impl(iterator I, ArgType &&Elt) {
747 // Callers ensure that ArgType is derived from T.
748 static_assert(
749 std::is_same<std::remove_const_t<std::remove_reference_t<ArgType>>,
750 T>::value,
751 "ArgType must be derived from T!");
752
753 if (I == this->end()) { // Important special case for empty vector.
754 this->push_back(::std::forward<ArgType>(Elt));
755 return this->end()-1;
756 }
757
758 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.\""
, "llvm/include/llvm/ADT/SmallVector.h", 758, __extension__ __PRETTY_FUNCTION__
))
;
759
760 // Grow if necessary.
761 size_t Index = I - this->begin();
762 std::remove_reference_t<ArgType> *EltPtr =
763 this->reserveForParamAndGetAddress(Elt);
764 I = this->begin() + Index;
765
766 ::new ((void*) this->end()) T(::std::move(this->back()));
767 // Push everything else over.
768 std::move_backward(I, this->end()-1, this->end());
769 this->set_size(this->size() + 1);
770
771 // If we just moved the element we're inserting, be sure to update
772 // the reference (never happens if TakesParamByValue).
773 static_assert(!TakesParamByValue || std::is_same<ArgType, T>::value,
774 "ArgType must be 'T' when taking by value!");
775 if (!TakesParamByValue && this->isReferenceToRange(EltPtr, I, this->end()))
776 ++EltPtr;
777
778 *I = ::std::forward<ArgType>(*EltPtr);
779 return I;
780 }
781
782public:
783 iterator insert(iterator I, T &&Elt) {
784 return insert_one_impl(I, this->forward_value_param(std::move(Elt)));
785 }
786
787 iterator insert(iterator I, const T &Elt) {
788 return insert_one_impl(I, this->forward_value_param(Elt));
789 }
790
791 iterator insert(iterator I, size_type NumToInsert, ValueParamT Elt) {
792 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
793 size_t InsertElt = I - this->begin();
794
795 if (I == this->end()) { // Important special case for empty vector.
796 append(NumToInsert, Elt);
797 return this->begin()+InsertElt;
798 }
799
800 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.\""
, "llvm/include/llvm/ADT/SmallVector.h", 800, __extension__ __PRETTY_FUNCTION__
))
;
801
802 // Ensure there is enough space, and get the (maybe updated) address of
803 // Elt.
804 const T *EltPtr = this->reserveForParamAndGetAddress(Elt, NumToInsert);
805
806 // Uninvalidate the iterator.
807 I = this->begin()+InsertElt;
808
809 // If there are more elements between the insertion point and the end of the
810 // range than there are being inserted, we can use a simple approach to
811 // insertion. Since we already reserved space, we know that this won't
812 // reallocate the vector.
813 if (size_t(this->end()-I) >= NumToInsert) {
814 T *OldEnd = this->end();
815 append(std::move_iterator<iterator>(this->end() - NumToInsert),
816 std::move_iterator<iterator>(this->end()));
817
818 // Copy the existing elements that get replaced.
819 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
820
821 // If we just moved the element we're inserting, be sure to update
822 // the reference (never happens if TakesParamByValue).
823 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
824 EltPtr += NumToInsert;
825
826 std::fill_n(I, NumToInsert, *EltPtr);
827 return I;
828 }
829
830 // Otherwise, we're inserting more elements than exist already, and we're
831 // not inserting at the end.
832
833 // Move over the elements that we're about to overwrite.
834 T *OldEnd = this->end();
835 this->set_size(this->size() + NumToInsert);
836 size_t NumOverwritten = OldEnd-I;
837 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
838
839 // If we just moved the element we're inserting, be sure to update
840 // the reference (never happens if TakesParamByValue).
841 if (!TakesParamByValue && I <= EltPtr && EltPtr < this->end())
842 EltPtr += NumToInsert;
843
844 // Replace the overwritten part.
845 std::fill_n(I, NumOverwritten, *EltPtr);
846
847 // Insert the non-overwritten middle part.
848 std::uninitialized_fill_n(OldEnd, NumToInsert - NumOverwritten, *EltPtr);
849 return I;
850 }
851
852 template <typename ItTy,
853 typename = std::enable_if_t<std::is_convertible<
854 typename std::iterator_traits<ItTy>::iterator_category,
855 std::input_iterator_tag>::value>>
856 iterator insert(iterator I, ItTy From, ItTy To) {
857 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
858 size_t InsertElt = I - this->begin();
859
860 if (I == this->end()) { // Important special case for empty vector.
861 append(From, To);
862 return this->begin()+InsertElt;
863 }
864
865 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.\""
, "llvm/include/llvm/ADT/SmallVector.h", 865, __extension__ __PRETTY_FUNCTION__
))
;
866
867 // Check that the reserve that follows doesn't invalidate the iterators.
868 this->assertSafeToAddRange(From, To);
869
870 size_t NumToInsert = std::distance(From, To);
871
872 // Ensure there is enough space.
873 reserve(this->size() + NumToInsert);
874
875 // Uninvalidate the iterator.
876 I = this->begin()+InsertElt;
877
878 // If there are more elements between the insertion point and the end of the
879 // range than there are being inserted, we can use a simple approach to
880 // insertion. Since we already reserved space, we know that this won't
881 // reallocate the vector.
882 if (size_t(this->end()-I) >= NumToInsert) {
883 T *OldEnd = this->end();
884 append(std::move_iterator<iterator>(this->end() - NumToInsert),
885 std::move_iterator<iterator>(this->end()));
886
887 // Copy the existing elements that get replaced.
888 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
889
890 std::copy(From, To, I);
891 return I;
892 }
893
894 // Otherwise, we're inserting more elements than exist already, and we're
895 // not inserting at the end.
896
897 // Move over the elements that we're about to overwrite.
898 T *OldEnd = this->end();
899 this->set_size(this->size() + NumToInsert);
900 size_t NumOverwritten = OldEnd-I;
901 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
902
903 // Replace the overwritten part.
904 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
905 *J = *From;
906 ++J; ++From;
907 }
908
909 // Insert the non-overwritten middle part.
910 this->uninitialized_copy(From, To, OldEnd);
911 return I;
912 }
913
914 void insert(iterator I, std::initializer_list<T> IL) {
915 insert(I, IL.begin(), IL.end());
916 }
917
918 template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
919 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
920 return this->growAndEmplaceBack(std::forward<ArgTypes>(Args)...);
921
922 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
923 this->set_size(this->size() + 1);
924 return this->back();
925 }
926
927 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
928
929 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
930
931 bool operator==(const SmallVectorImpl &RHS) const {
932 if (this->size() != RHS.size()) return false;
933 return std::equal(this->begin(), this->end(), RHS.begin());
934 }
935 bool operator!=(const SmallVectorImpl &RHS) const {
936 return !(*this == RHS);
937 }
938
939 bool operator<(const SmallVectorImpl &RHS) const {
940 return std::lexicographical_compare(this->begin(), this->end(),
941 RHS.begin(), RHS.end());
942 }
943};
944
945template <typename T>
946void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
947 if (this == &RHS) return;
948
949 // We can only avoid copying elements if neither vector is small.
950 if (!this->isSmall() && !RHS.isSmall()) {
951 std::swap(this->BeginX, RHS.BeginX);
952 std::swap(this->Size, RHS.Size);
953 std::swap(this->Capacity, RHS.Capacity);
954 return;
955 }
956 this->reserve(RHS.size());
957 RHS.reserve(this->size());
958
959 // Swap the shared elements.
960 size_t NumShared = this->size();
961 if (NumShared > RHS.size()) NumShared = RHS.size();
962 for (size_type i = 0; i != NumShared; ++i)
963 std::swap((*this)[i], RHS[i]);
964
965 // Copy over the extra elts.
966 if (this->size() > RHS.size()) {
967 size_t EltDiff = this->size() - RHS.size();
968 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
969 RHS.set_size(RHS.size() + EltDiff);
970 this->destroy_range(this->begin()+NumShared, this->end());
971 this->set_size(NumShared);
972 } else if (RHS.size() > this->size()) {
973 size_t EltDiff = RHS.size() - this->size();
974 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
975 this->set_size(this->size() + EltDiff);
976 this->destroy_range(RHS.begin()+NumShared, RHS.end());
977 RHS.set_size(NumShared);
978 }
979}
980
981template <typename T>
982SmallVectorImpl<T> &SmallVectorImpl<T>::
983 operator=(const SmallVectorImpl<T> &RHS) {
984 // Avoid self-assignment.
985 if (this == &RHS) return *this;
986
987 // If we already have sufficient space, assign the common elements, then
988 // destroy any excess.
989 size_t RHSSize = RHS.size();
990 size_t CurSize = this->size();
991 if (CurSize >= RHSSize) {
992 // Assign common elements.
993 iterator NewEnd;
994 if (RHSSize)
995 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
996 else
997 NewEnd = this->begin();
998
999 // Destroy excess elements.
1000 this->destroy_range(NewEnd, this->end());
1001
1002 // Trim.
1003 this->set_size(RHSSize);
1004 return *this;
1005 }
1006
1007 // If we have to grow to have enough elements, destroy the current elements.
1008 // This allows us to avoid copying them during the grow.
1009 // FIXME: don't do this if they're efficiently moveable.
1010 if (this->capacity() < RHSSize) {
1011 // Destroy current elements.
1012 this->clear();
1013 CurSize = 0;
1014 this->grow(RHSSize);
1015 } else if (CurSize) {
1016 // Otherwise, use assignment for the already-constructed elements.
1017 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
1018 }
1019
1020 // Copy construct the new elements in place.
1021 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
1022 this->begin()+CurSize);
1023
1024 // Set end.
1025 this->set_size(RHSSize);
1026 return *this;
1027}
1028
1029template <typename T>
1030SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
1031 // Avoid self-assignment.
1032 if (this == &RHS) return *this;
1033
1034 // If the RHS isn't small, clear this vector and then steal its buffer.
1035 if (!RHS.isSmall()) {
1036 this->destroy_range(this->begin(), this->end());
1037 if (!this->isSmall()) free(this->begin());
1038 this->BeginX = RHS.BeginX;
1039 this->Size = RHS.Size;
1040 this->Capacity = RHS.Capacity;
1041 RHS.resetToSmall();
1042 return *this;
1043 }
1044
1045 // If we already have sufficient space, assign the common elements, then
1046 // destroy any excess.
1047 size_t RHSSize = RHS.size();
1048 size_t CurSize = this->size();
1049 if (CurSize >= RHSSize) {
1050 // Assign common elements.
1051 iterator NewEnd = this->begin();
1052 if (RHSSize)
1053 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
1054
1055 // Destroy excess elements and trim the bounds.
1056 this->destroy_range(NewEnd, this->end());
1057 this->set_size(RHSSize);
1058
1059 // Clear the RHS.
1060 RHS.clear();
1061
1062 return *this;
1063 }
1064
1065 // If we have to grow to have enough elements, destroy the current elements.
1066 // This allows us to avoid copying them during the grow.
1067 // FIXME: this may not actually make any sense if we can efficiently move
1068 // elements.
1069 if (this->capacity() < RHSSize) {
1070 // Destroy current elements.
1071 this->clear();
1072 CurSize = 0;
1073 this->grow(RHSSize);
1074 } else if (CurSize) {
1075 // Otherwise, use assignment for the already-constructed elements.
1076 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
1077 }
1078
1079 // Move-construct the new elements in place.
1080 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
1081 this->begin()+CurSize);
1082
1083 // Set end.
1084 this->set_size(RHSSize);
1085
1086 RHS.clear();
1087 return *this;
1088}
1089
1090/// Storage for the SmallVector elements. This is specialized for the N=0 case
1091/// to avoid allocating unnecessary storage.
1092template <typename T, unsigned N>
1093struct SmallVectorStorage {
1094 alignas(T) char InlineElts[N * sizeof(T)];
1095};
1096
1097/// We need the storage to be properly aligned even for small-size of 0 so that
1098/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
1099/// well-defined.
1100template <typename T> struct alignas(T) SmallVectorStorage<T, 0> {};
1101
1102/// Forward declaration of SmallVector so that
1103/// calculateSmallVectorDefaultInlinedElements can reference
1104/// `sizeof(SmallVector<T, 0>)`.
1105template <typename T, unsigned N> class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector;
1106
1107/// Helper class for calculating the default number of inline elements for
1108/// `SmallVector<T>`.
1109///
1110/// This should be migrated to a constexpr function when our minimum
1111/// compiler support is enough for multi-statement constexpr functions.
1112template <typename T> struct CalculateSmallVectorDefaultInlinedElements {
1113 // Parameter controlling the default number of inlined elements
1114 // for `SmallVector<T>`.
1115 //
1116 // The default number of inlined elements ensures that
1117 // 1. There is at least one inlined element.
1118 // 2. `sizeof(SmallVector<T>) <= kPreferredSmallVectorSizeof` unless
1119 // it contradicts 1.
1120 static constexpr size_t kPreferredSmallVectorSizeof = 64;
1121
1122 // static_assert that sizeof(T) is not "too big".
1123 //
1124 // Because our policy guarantees at least one inlined element, it is possible
1125 // for an arbitrarily large inlined element to allocate an arbitrarily large
1126 // amount of inline storage. We generally consider it an antipattern for a
1127 // SmallVector to allocate an excessive amount of inline storage, so we want
1128 // to call attention to these cases and make sure that users are making an
1129 // intentional decision if they request a lot of inline storage.
1130 //
1131 // We want this assertion to trigger in pathological cases, but otherwise
1132 // not be too easy to hit. To accomplish that, the cutoff is actually somewhat
1133 // larger than kPreferredSmallVectorSizeof (otherwise,
1134 // `SmallVector<SmallVector<T>>` would be one easy way to trip it, and that
1135 // pattern seems useful in practice).
1136 //
1137 // One wrinkle is that this assertion is in theory non-portable, since
1138 // sizeof(T) is in general platform-dependent. However, we don't expect this
1139 // to be much of an issue, because most LLVM development happens on 64-bit
1140 // hosts, and therefore sizeof(T) is expected to *decrease* when compiled for
1141 // 32-bit hosts, dodging the issue. The reverse situation, where development
1142 // happens on a 32-bit host and then fails due to sizeof(T) *increasing* on a
1143 // 64-bit host, is expected to be very rare.
1144 static_assert(
1145 sizeof(T) <= 256,
1146 "You are trying to use a default number of inlined elements for "
1147 "`SmallVector<T>` but `sizeof(T)` is really big! Please use an "
1148 "explicit number of inlined elements with `SmallVector<T, N>` to make "
1149 "sure you really want that much inline storage.");
1150
1151 // Discount the size of the header itself when calculating the maximum inline
1152 // bytes.
1153 static constexpr size_t PreferredInlineBytes =
1154 kPreferredSmallVectorSizeof - sizeof(SmallVector<T, 0>);
1155 static constexpr size_t NumElementsThatFit = PreferredInlineBytes / sizeof(T);
1156 static constexpr size_t value =
1157 NumElementsThatFit == 0 ? 1 : NumElementsThatFit;
1158};
1159
1160/// This is a 'vector' (really, a variable-sized array), optimized
1161/// for the case when the array is small. It contains some number of elements
1162/// in-place, which allows it to avoid heap allocation when the actual number of
1163/// elements is below that threshold. This allows normal "small" cases to be
1164/// fast without losing generality for large inputs.
1165///
1166/// \note
1167/// In the absence of a well-motivated choice for the number of inlined
1168/// elements \p N, it is recommended to use \c SmallVector<T> (that is,
1169/// omitting the \p N). This will choose a default number of inlined elements
1170/// reasonable for allocation on the stack (for example, trying to keep \c
1171/// sizeof(SmallVector<T>) around 64 bytes).
1172///
1173/// \warning This does not attempt to be exception safe.
1174///
1175/// \see https://llvm.org/docs/ProgrammersManual.html#llvm-adt-smallvector-h
1176template <typename T,
1177 unsigned N = CalculateSmallVectorDefaultInlinedElements<T>::value>
1178class LLVM_GSL_OWNER[[gsl::Owner]] SmallVector : public SmallVectorImpl<T>,
1179 SmallVectorStorage<T, N> {
1180public:
1181 SmallVector() : SmallVectorImpl<T>(N) {}
1182
1183 ~SmallVector() {
1184 // Destroy the constructed elements in the vector.
1185 this->destroy_range(this->begin(), this->end());
1186 }
1187
1188 explicit SmallVector(size_t Size, const T &Value = T())
1189 : SmallVectorImpl<T>(N) {
1190 this->assign(Size, Value);
1191 }
1192
1193 template <typename ItTy,
1194 typename = std::enable_if_t<std::is_convertible<
1195 typename std::iterator_traits<ItTy>::iterator_category,
1196 std::input_iterator_tag>::value>>
1197 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
1198 this->append(S, E);
1199 }
1200
1201 template <typename RangeTy>
1202 explicit SmallVector(const iterator_range<RangeTy> &R)
1203 : SmallVectorImpl<T>(N) {
1204 this->append(R.begin(), R.end());
1205 }
1206
1207 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
1208 this->assign(IL);
1209 }
1210
1211 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
1212 if (!RHS.empty())
1213 SmallVectorImpl<T>::operator=(RHS);
1214 }
1215
1216 SmallVector &operator=(const SmallVector &RHS) {
1217 SmallVectorImpl<T>::operator=(RHS);
1218 return *this;
1219 }
1220
1221 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
1222 if (!RHS.empty())
1223 SmallVectorImpl<T>::operator=(::std::move(RHS));
1224 }
1225
1226 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
1227 if (!RHS.empty())
1228 SmallVectorImpl<T>::operator=(::std::move(RHS));
1229 }
1230
1231 SmallVector &operator=(SmallVector &&RHS) {
1232 SmallVectorImpl<T>::operator=(::std::move(RHS));
1233 return *this;
1234 }
1235
1236 SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
1237 SmallVectorImpl<T>::operator=(::std::move(RHS));
1238 return *this;
1239 }
1240
1241 SmallVector &operator=(std::initializer_list<T> IL) {
1242 this->assign(IL);
1243 return *this;
1244 }
1245};
1246
1247template <typename T, unsigned N>
1248inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
1249 return X.capacity_in_bytes();
1250}
1251
1252template <typename RangeType>
1253using ValueTypeFromRangeType =
1254 typename std::remove_const<typename std::remove_reference<
1255 decltype(*std::begin(std::declval<RangeType &>()))>::type>::type;
1256
1257/// Given a range of type R, iterate the entire range and return a
1258/// SmallVector with elements of the vector. This is useful, for example,
1259/// when you want to iterate a range and then sort the results.
1260template <unsigned Size, typename R>
1261SmallVector<ValueTypeFromRangeType<R>, Size> to_vector(R &&Range) {
1262 return {std::begin(Range), std::end(Range)};
1263}
1264template <typename R>
1265SmallVector<ValueTypeFromRangeType<R>,
1266 CalculateSmallVectorDefaultInlinedElements<
1267 ValueTypeFromRangeType<R>>::value>
1268to_vector(R &&Range) {
1269 return {std::begin(Range), std::end(Range)};
1270}
1271
1272} // end namespace llvm
1273
1274namespace std {
1275
1276 /// Implement std::swap in terms of SmallVector swap.
1277 template<typename T>
1278 inline void
1279 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
1280 LHS.swap(RHS);
1281 }
1282
1283 /// Implement std::swap in terms of SmallVector swap.
1284 template<typename T, unsigned N>
1285 inline void
1286 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
1287 LHS.swap(RHS);
1288 }
1289
1290} // end namespace std
1291
1292#endif // LLVM_ADT_SMALLVECTOR_H