Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name GlobalOpt.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -fno-rounding-math -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/build-llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Transforms/IPO -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/build-llvm/include -I /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/build-llvm/lib/Transforms/IPO -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2019-12-11-181444-25759-1 -x c++ /build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Transforms/IPO/GlobalOpt.cpp

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

/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/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/AlignOf.h"
18#include "llvm/Support/Compiler.h"
19#include "llvm/Support/MathExtras.h"
20#include "llvm/Support/MemAlloc.h"
21#include "llvm/Support/type_traits.h"
22#include "llvm/Support/ErrorHandling.h"
23#include <algorithm>
24#include <cassert>
25#include <cstddef>
26#include <cstdlib>
27#include <cstring>
28#include <initializer_list>
29#include <iterator>
30#include <memory>
31#include <new>
32#include <type_traits>
33#include <utility>
34
35namespace llvm {
36
37/// This is all the non-templated stuff common to all SmallVectors.
38class SmallVectorBase {
39protected:
40 void *BeginX;
41 unsigned Size = 0, Capacity;
42
43 SmallVectorBase() = delete;
44 SmallVectorBase(void *FirstEl, size_t TotalCapacity)
45 : BeginX(FirstEl), Capacity(TotalCapacity) {}
46
47 /// This is an implementation of the grow() method which only works
48 /// on POD-like data types and is out of line to reduce code duplication.
49 void grow_pod(void *FirstEl, size_t MinCapacity, size_t TSize);
50
51public:
52 size_t size() const { return Size; }
53 size_t capacity() const { return Capacity; }
54
55 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
56
57 /// Set the array size to \p N, which the current array must have enough
58 /// capacity for.
59 ///
60 /// This does not construct or destroy any elements in the vector.
61 ///
62 /// Clients can use this in conjunction with capacity() to write past the end
63 /// of the buffer when they know that more elements are available, and only
64 /// update the size later. This avoids the cost of value initializing elements
65 /// which will only be overwritten.
66 void set_size(size_t N) {
67 assert(N <= capacity())((N <= capacity()) ? static_cast<void> (0) : __assert_fail
("N <= capacity()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 67, __PRETTY_FUNCTION__))
;
68 Size = N;
69 }
70};
71
72/// Figure out the offset of the first element.
73template <class T, typename = void> struct SmallVectorAlignmentAndSize {
74 AlignedCharArrayUnion<SmallVectorBase> Base;
75 AlignedCharArrayUnion<T> FirstEl;
76};
77
78/// This is the part of SmallVectorTemplateBase which does not depend on whether
79/// the type T is a POD. The extra dummy template argument is used by ArrayRef
80/// to avoid unnecessarily requiring T to be complete.
81template <typename T, typename = void>
82class SmallVectorTemplateCommon : public SmallVectorBase {
83 /// Find the address of the first element. For this pointer math to be valid
84 /// with small-size of 0 for T with lots of alignment, it's important that
85 /// SmallVectorStorage is properly-aligned even for small-size of 0.
86 void *getFirstEl() const {
87 return const_cast<void *>(reinterpret_cast<const void *>(
88 reinterpret_cast<const char *>(this) +
89 offsetof(SmallVectorAlignmentAndSize<T>, FirstEl)__builtin_offsetof(SmallVectorAlignmentAndSize<T>, FirstEl
)
));
90 }
91 // Space after 'FirstEl' is clobbered, do not add any instance vars after it.
92
93protected:
94 SmallVectorTemplateCommon(size_t Size)
95 : SmallVectorBase(getFirstEl(), Size) {}
96
97 void grow_pod(size_t MinCapacity, size_t TSize) {
98 SmallVectorBase::grow_pod(getFirstEl(), MinCapacity, TSize);
99 }
100
101 /// Return true if this is a smallvector which has not had dynamic
102 /// memory allocated for it.
103 bool isSmall() const { return BeginX == getFirstEl(); }
104
105 /// Put this vector in a state of being small.
106 void resetToSmall() {
107 BeginX = getFirstEl();
108 Size = Capacity = 0; // FIXME: Setting Capacity to 0 is suspect.
109 }
110
111public:
112 using size_type = size_t;
113 using difference_type = ptrdiff_t;
114 using value_type = T;
115 using iterator = T *;
116 using const_iterator = const T *;
117
118 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
119 using reverse_iterator = std::reverse_iterator<iterator>;
120
121 using reference = T &;
122 using const_reference = const T &;
123 using pointer = T *;
124 using const_pointer = const T *;
125
126 // forward iterator creation methods.
127 iterator begin() { return (iterator)this->BeginX; }
128 const_iterator begin() const { return (const_iterator)this->BeginX; }
129 iterator end() { return begin() + size(); }
130 const_iterator end() const { return begin() + size(); }
131
132 // reverse iterator creation methods.
133 reverse_iterator rbegin() { return reverse_iterator(end()); }
134 const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
135 reverse_iterator rend() { return reverse_iterator(begin()); }
136 const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
137
138 size_type size_in_bytes() const { return size() * sizeof(T); }
139 size_type max_size() const { return size_type(-1) / sizeof(T); }
140
141 size_t capacity_in_bytes() const { return capacity() * sizeof(T); }
142
143 /// Return a pointer to the vector's buffer, even if empty().
144 pointer data() { return pointer(begin()); }
145 /// Return a pointer to the vector's buffer, even if empty().
146 const_pointer data() const { return const_pointer(begin()); }
147
148 reference operator[](size_type idx) {
149 assert(idx < size())((idx < size()) ? static_cast<void> (0) : __assert_fail
("idx < size()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 149, __PRETTY_FUNCTION__))
;
150 return begin()[idx];
151 }
152 const_reference operator[](size_type idx) const {
153 assert(idx < size())((idx < size()) ? static_cast<void> (0) : __assert_fail
("idx < size()", "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 153, __PRETTY_FUNCTION__))
;
154 return begin()[idx];
155 }
156
157 reference front() {
158 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 158, __PRETTY_FUNCTION__))
;
159 return begin()[0];
160 }
161 const_reference front() const {
162 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 162, __PRETTY_FUNCTION__))
;
163 return begin()[0];
164 }
165
166 reference back() {
167 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 167, __PRETTY_FUNCTION__))
;
168 return end()[-1];
169 }
170 const_reference back() const {
171 assert(!empty())((!empty()) ? static_cast<void> (0) : __assert_fail ("!empty()"
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 171, __PRETTY_FUNCTION__))
;
172 return end()[-1];
173 }
174};
175
176/// SmallVectorTemplateBase<TriviallyCopyable = false> - This is where we put method
177/// implementations that are designed to work with non-POD-like T's.
178template <typename T, bool = is_trivially_copyable<T>::value>
179class SmallVectorTemplateBase : public SmallVectorTemplateCommon<T> {
180protected:
181 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
182
183 static void destroy_range(T *S, T *E) {
184 while (S != E) {
185 --E;
186 E->~T();
187 }
188 }
189
190 /// Move the range [I, E) into the uninitialized memory starting with "Dest",
191 /// constructing elements as needed.
192 template<typename It1, typename It2>
193 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
194 std::uninitialized_copy(std::make_move_iterator(I),
195 std::make_move_iterator(E), Dest);
196 }
197
198 /// Copy the range [I, E) onto the uninitialized memory starting with "Dest",
199 /// constructing elements as needed.
200 template<typename It1, typename It2>
201 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
202 std::uninitialized_copy(I, E, Dest);
203 }
204
205 /// Grow the allocated memory (without initializing new elements), doubling
206 /// the size of the allocated memory. Guarantees space for at least one more
207 /// element, or MinSize more elements if specified.
208 void grow(size_t MinSize = 0);
209
210public:
211 void push_back(const T &Elt) {
212 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
213 this->grow();
214 ::new ((void*) this->end()) T(Elt);
215 this->set_size(this->size() + 1);
216 }
217
218 void push_back(T &&Elt) {
219 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
220 this->grow();
221 ::new ((void*) this->end()) T(::std::move(Elt));
222 this->set_size(this->size() + 1);
223 }
224
225 void pop_back() {
226 this->set_size(this->size() - 1);
227 this->end()->~T();
228 }
229};
230
231// Define this out-of-line to dissuade the C++ compiler from inlining it.
232template <typename T, bool TriviallyCopyable>
233void SmallVectorTemplateBase<T, TriviallyCopyable>::grow(size_t MinSize) {
234 if (MinSize > UINT32_MAX(4294967295U))
235 report_bad_alloc_error("SmallVector capacity overflow during allocation");
236
237 // Always grow, even from zero.
238 size_t NewCapacity = size_t(NextPowerOf2(this->capacity() + 2));
239 NewCapacity = std::min(std::max(NewCapacity, MinSize), size_t(UINT32_MAX(4294967295U)));
240 T *NewElts = static_cast<T*>(llvm::safe_malloc(NewCapacity*sizeof(T)));
241
242 // Move the elements over.
243 this->uninitialized_move(this->begin(), this->end(), NewElts);
244
245 // Destroy the original elements.
246 destroy_range(this->begin(), this->end());
247
248 // If this wasn't grown from the inline copy, deallocate the old space.
249 if (!this->isSmall())
250 free(this->begin());
251
252 this->BeginX = NewElts;
253 this->Capacity = NewCapacity;
254}
255
256/// SmallVectorTemplateBase<TriviallyCopyable = true> - This is where we put
257/// method implementations that are designed to work with POD-like T's.
258template <typename T>
259class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon<T> {
260protected:
261 SmallVectorTemplateBase(size_t Size) : SmallVectorTemplateCommon<T>(Size) {}
262
263 // No need to do a destroy loop for POD's.
264 static void destroy_range(T *, T *) {}
265
266 /// Move the range [I, E) onto the uninitialized memory
267 /// starting with "Dest", constructing elements into it as needed.
268 template<typename It1, typename It2>
269 static void uninitialized_move(It1 I, It1 E, It2 Dest) {
270 // Just do a copy.
271 uninitialized_copy(I, E, Dest);
272 }
273
274 /// Copy the range [I, E) onto the uninitialized memory
275 /// starting with "Dest", constructing elements into it as needed.
276 template<typename It1, typename It2>
277 static void uninitialized_copy(It1 I, It1 E, It2 Dest) {
278 // Arbitrary iterator types; just use the basic implementation.
279 std::uninitialized_copy(I, E, Dest);
280 }
281
282 /// Copy the range [I, E) onto the uninitialized memory
283 /// starting with "Dest", constructing elements into it as needed.
284 template <typename T1, typename T2>
285 static void uninitialized_copy(
286 T1 *I, T1 *E, T2 *Dest,
287 typename std::enable_if<std::is_same<typename std::remove_const<T1>::type,
288 T2>::value>::type * = nullptr) {
289 // Use memcpy for PODs iterated by pointers (which includes SmallVector
290 // iterators): std::uninitialized_copy optimizes to memmove, but we can
291 // use memcpy here. Note that I and E are iterators and thus might be
292 // invalid for memcpy if they are equal.
293 if (I != E)
294 memcpy(reinterpret_cast<void *>(Dest), I, (E - I) * sizeof(T));
295 }
296
297 /// Double the size of the allocated memory, guaranteeing space for at
298 /// least one more element or MinSize if specified.
299 void grow(size_t MinSize = 0) { this->grow_pod(MinSize, sizeof(T)); }
300
301public:
302 void push_back(const T &Elt) {
303 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
304 this->grow();
305 memcpy(reinterpret_cast<void *>(this->end()), &Elt, sizeof(T));
306 this->set_size(this->size() + 1);
307 }
308
309 void pop_back() { this->set_size(this->size() - 1); }
310};
311
312/// This class consists of common code factored out of the SmallVector class to
313/// reduce code duplication based on the SmallVector 'N' template parameter.
314template <typename T>
315class SmallVectorImpl : public SmallVectorTemplateBase<T> {
316 using SuperClass = SmallVectorTemplateBase<T>;
317
318public:
319 using iterator = typename SuperClass::iterator;
320 using const_iterator = typename SuperClass::const_iterator;
321 using reference = typename SuperClass::reference;
322 using size_type = typename SuperClass::size_type;
323
324protected:
325 // Default ctor - Initialize to empty.
326 explicit SmallVectorImpl(unsigned N)
327 : SmallVectorTemplateBase<T>(N) {}
328
329public:
330 SmallVectorImpl(const SmallVectorImpl &) = delete;
331
332 ~SmallVectorImpl() {
333 // Subclass has already destructed this vector's elements.
334 // If this wasn't grown from the inline copy, deallocate the old space.
335 if (!this->isSmall())
336 free(this->begin());
337 }
338
339 void clear() {
340 this->destroy_range(this->begin(), this->end());
341 this->Size = 0;
342 }
343
344 void resize(size_type N) {
345 if (N < this->size()) {
346 this->destroy_range(this->begin()+N, this->end());
347 this->set_size(N);
348 } else if (N > this->size()) {
349 if (this->capacity() < N)
350 this->grow(N);
351 for (auto I = this->end(), E = this->begin() + N; I != E; ++I)
352 new (&*I) T();
353 this->set_size(N);
354 }
355 }
356
357 void resize(size_type N, const T &NV) {
358 if (N < this->size()) {
359 this->destroy_range(this->begin()+N, this->end());
360 this->set_size(N);
361 } else if (N > this->size()) {
362 if (this->capacity() < N)
363 this->grow(N);
364 std::uninitialized_fill(this->end(), this->begin()+N, NV);
365 this->set_size(N);
366 }
367 }
368
369 void reserve(size_type N) {
370 if (this->capacity() < N)
371 this->grow(N);
372 }
373
374 LLVM_NODISCARD[[clang::warn_unused_result]] T pop_back_val() {
375 T Result = ::std::move(this->back());
376 this->pop_back();
377 return Result;
378 }
379
380 void swap(SmallVectorImpl &RHS);
381
382 /// Add the specified range to the end of the SmallVector.
383 template <typename in_iter,
384 typename = typename std::enable_if<std::is_convertible<
385 typename std::iterator_traits<in_iter>::iterator_category,
386 std::input_iterator_tag>::value>::type>
387 void append(in_iter in_start, in_iter in_end) {
388 size_type NumInputs = std::distance(in_start, in_end);
389 if (NumInputs > this->capacity() - this->size())
390 this->grow(this->size()+NumInputs);
391
392 this->uninitialized_copy(in_start, in_end, this->end());
393 this->set_size(this->size() + NumInputs);
394 }
395
396 /// Append \p NumInputs copies of \p Elt to the end.
397 void append(size_type NumInputs, const T &Elt) {
398 if (NumInputs > this->capacity() - this->size())
399 this->grow(this->size()+NumInputs);
400
401 std::uninitialized_fill_n(this->end(), NumInputs, Elt);
402 this->set_size(this->size() + NumInputs);
403 }
404
405 void append(std::initializer_list<T> IL) {
406 append(IL.begin(), IL.end());
407 }
408
409 // FIXME: Consider assigning over existing elements, rather than clearing &
410 // re-initializing them - for all assign(...) variants.
411
412 void assign(size_type NumElts, const T &Elt) {
413 clear();
414 if (this->capacity() < NumElts)
415 this->grow(NumElts);
416 this->set_size(NumElts);
417 std::uninitialized_fill(this->begin(), this->end(), Elt);
418 }
419
420 template <typename in_iter,
421 typename = typename std::enable_if<std::is_convertible<
422 typename std::iterator_traits<in_iter>::iterator_category,
423 std::input_iterator_tag>::value>::type>
424 void assign(in_iter in_start, in_iter in_end) {
425 clear();
426 append(in_start, in_end);
427 }
428
429 void assign(std::initializer_list<T> IL) {
430 clear();
431 append(IL);
432 }
433
434 iterator erase(const_iterator CI) {
435 // Just cast away constness because this is a non-const member function.
436 iterator I = const_cast<iterator>(CI);
437
438 assert(I >= this->begin() && "Iterator to erase is out of bounds.")((I >= this->begin() && "Iterator to erase is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Iterator to erase is out of bounds.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 438, __PRETTY_FUNCTION__))
;
439 assert(I < this->end() && "Erasing at past-the-end iterator.")((I < this->end() && "Erasing at past-the-end iterator."
) ? static_cast<void> (0) : __assert_fail ("I < this->end() && \"Erasing at past-the-end iterator.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 439, __PRETTY_FUNCTION__))
;
440
441 iterator N = I;
442 // Shift all elts down one.
443 std::move(I+1, this->end(), I);
444 // Drop the last elt.
445 this->pop_back();
446 return(N);
447 }
448
449 iterator erase(const_iterator CS, const_iterator CE) {
450 // Just cast away constness because this is a non-const member function.
451 iterator S = const_cast<iterator>(CS);
452 iterator E = const_cast<iterator>(CE);
453
454 assert(S >= this->begin() && "Range to erase is out of bounds.")((S >= this->begin() && "Range to erase is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("S >= this->begin() && \"Range to erase is out of bounds.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 454, __PRETTY_FUNCTION__))
;
455 assert(S <= E && "Trying to erase invalid range.")((S <= E && "Trying to erase invalid range.") ? static_cast
<void> (0) : __assert_fail ("S <= E && \"Trying to erase invalid range.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 455, __PRETTY_FUNCTION__))
;
456 assert(E <= this->end() && "Trying to erase past the end.")((E <= this->end() && "Trying to erase past the end."
) ? static_cast<void> (0) : __assert_fail ("E <= this->end() && \"Trying to erase past the end.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 456, __PRETTY_FUNCTION__))
;
457
458 iterator N = S;
459 // Shift all elts down.
460 iterator I = std::move(E, this->end(), S);
461 // Drop the last elts.
462 this->destroy_range(I, this->end());
463 this->set_size(I - this->begin());
464 return(N);
465 }
466
467 iterator insert(iterator I, T &&Elt) {
468 if (I == this->end()) { // Important special case for empty vector.
469 this->push_back(::std::move(Elt));
470 return this->end()-1;
471 }
472
473 assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 473, __PRETTY_FUNCTION__))
;
474 assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector."
) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 474, __PRETTY_FUNCTION__))
;
475
476 if (this->size() >= this->capacity()) {
477 size_t EltNo = I-this->begin();
478 this->grow();
479 I = this->begin()+EltNo;
480 }
481
482 ::new ((void*) this->end()) T(::std::move(this->back()));
483 // Push everything else over.
484 std::move_backward(I, this->end()-1, this->end());
485 this->set_size(this->size() + 1);
486
487 // If we just moved the element we're inserting, be sure to update
488 // the reference.
489 T *EltPtr = &Elt;
490 if (I <= EltPtr && EltPtr < this->end())
491 ++EltPtr;
492
493 *I = ::std::move(*EltPtr);
494 return I;
495 }
496
497 iterator insert(iterator I, const T &Elt) {
498 if (I == this->end()) { // Important special case for empty vector.
499 this->push_back(Elt);
500 return this->end()-1;
501 }
502
503 assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 503, __PRETTY_FUNCTION__))
;
504 assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector."
) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 504, __PRETTY_FUNCTION__))
;
505
506 if (this->size() >= this->capacity()) {
507 size_t EltNo = I-this->begin();
508 this->grow();
509 I = this->begin()+EltNo;
510 }
511 ::new ((void*) this->end()) T(std::move(this->back()));
512 // Push everything else over.
513 std::move_backward(I, this->end()-1, this->end());
514 this->set_size(this->size() + 1);
515
516 // If we just moved the element we're inserting, be sure to update
517 // the reference.
518 const T *EltPtr = &Elt;
519 if (I <= EltPtr && EltPtr < this->end())
520 ++EltPtr;
521
522 *I = *EltPtr;
523 return I;
524 }
525
526 iterator insert(iterator I, size_type NumToInsert, const T &Elt) {
527 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
528 size_t InsertElt = I - this->begin();
529
530 if (I == this->end()) { // Important special case for empty vector.
531 append(NumToInsert, Elt);
532 return this->begin()+InsertElt;
533 }
534
535 assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 535, __PRETTY_FUNCTION__))
;
536 assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector."
) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 536, __PRETTY_FUNCTION__))
;
537
538 // Ensure there is enough space.
539 reserve(this->size() + NumToInsert);
540
541 // Uninvalidate the iterator.
542 I = this->begin()+InsertElt;
543
544 // If there are more elements between the insertion point and the end of the
545 // range than there are being inserted, we can use a simple approach to
546 // insertion. Since we already reserved space, we know that this won't
547 // reallocate the vector.
548 if (size_t(this->end()-I) >= NumToInsert) {
549 T *OldEnd = this->end();
550 append(std::move_iterator<iterator>(this->end() - NumToInsert),
551 std::move_iterator<iterator>(this->end()));
552
553 // Copy the existing elements that get replaced.
554 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
555
556 std::fill_n(I, NumToInsert, Elt);
557 return I;
558 }
559
560 // Otherwise, we're inserting more elements than exist already, and we're
561 // not inserting at the end.
562
563 // Move over the elements that we're about to overwrite.
564 T *OldEnd = this->end();
565 this->set_size(this->size() + NumToInsert);
566 size_t NumOverwritten = OldEnd-I;
567 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
568
569 // Replace the overwritten part.
570 std::fill_n(I, NumOverwritten, Elt);
571
572 // Insert the non-overwritten middle part.
573 std::uninitialized_fill_n(OldEnd, NumToInsert-NumOverwritten, Elt);
574 return I;
575 }
576
577 template <typename ItTy,
578 typename = typename std::enable_if<std::is_convertible<
579 typename std::iterator_traits<ItTy>::iterator_category,
580 std::input_iterator_tag>::value>::type>
581 iterator insert(iterator I, ItTy From, ItTy To) {
582 // Convert iterator to elt# to avoid invalidating iterator when we reserve()
583 size_t InsertElt = I - this->begin();
584
585 if (I == this->end()) { // Important special case for empty vector.
586 append(From, To);
587 return this->begin()+InsertElt;
588 }
589
590 assert(I >= this->begin() && "Insertion iterator is out of bounds.")((I >= this->begin() && "Insertion iterator is out of bounds."
) ? static_cast<void> (0) : __assert_fail ("I >= this->begin() && \"Insertion iterator is out of bounds.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 590, __PRETTY_FUNCTION__))
;
591 assert(I <= this->end() && "Inserting past the end of the vector.")((I <= this->end() && "Inserting past the end of the vector."
) ? static_cast<void> (0) : __assert_fail ("I <= this->end() && \"Inserting past the end of the vector.\""
, "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/include/llvm/ADT/SmallVector.h"
, 591, __PRETTY_FUNCTION__))
;
592
593 size_t NumToInsert = std::distance(From, To);
594
595 // Ensure there is enough space.
596 reserve(this->size() + NumToInsert);
597
598 // Uninvalidate the iterator.
599 I = this->begin()+InsertElt;
600
601 // If there are more elements between the insertion point and the end of the
602 // range than there are being inserted, we can use a simple approach to
603 // insertion. Since we already reserved space, we know that this won't
604 // reallocate the vector.
605 if (size_t(this->end()-I) >= NumToInsert) {
606 T *OldEnd = this->end();
607 append(std::move_iterator<iterator>(this->end() - NumToInsert),
608 std::move_iterator<iterator>(this->end()));
609
610 // Copy the existing elements that get replaced.
611 std::move_backward(I, OldEnd-NumToInsert, OldEnd);
612
613 std::copy(From, To, I);
614 return I;
615 }
616
617 // Otherwise, we're inserting more elements than exist already, and we're
618 // not inserting at the end.
619
620 // Move over the elements that we're about to overwrite.
621 T *OldEnd = this->end();
622 this->set_size(this->size() + NumToInsert);
623 size_t NumOverwritten = OldEnd-I;
624 this->uninitialized_move(I, OldEnd, this->end()-NumOverwritten);
625
626 // Replace the overwritten part.
627 for (T *J = I; NumOverwritten > 0; --NumOverwritten) {
628 *J = *From;
629 ++J; ++From;
630 }
631
632 // Insert the non-overwritten middle part.
633 this->uninitialized_copy(From, To, OldEnd);
634 return I;
635 }
636
637 void insert(iterator I, std::initializer_list<T> IL) {
638 insert(I, IL.begin(), IL.end());
639 }
640
641 template <typename... ArgTypes> reference emplace_back(ArgTypes &&... Args) {
642 if (LLVM_UNLIKELY(this->size() >= this->capacity())__builtin_expect((bool)(this->size() >= this->capacity
()), false)
)
643 this->grow();
644 ::new ((void *)this->end()) T(std::forward<ArgTypes>(Args)...);
645 this->set_size(this->size() + 1);
646 return this->back();
647 }
648
649 SmallVectorImpl &operator=(const SmallVectorImpl &RHS);
650
651 SmallVectorImpl &operator=(SmallVectorImpl &&RHS);
652
653 bool operator==(const SmallVectorImpl &RHS) const {
654 if (this->size() != RHS.size()) return false;
655 return std::equal(this->begin(), this->end(), RHS.begin());
656 }
657 bool operator!=(const SmallVectorImpl &RHS) const {
658 return !(*this == RHS);
659 }
660
661 bool operator<(const SmallVectorImpl &RHS) const {
662 return std::lexicographical_compare(this->begin(), this->end(),
663 RHS.begin(), RHS.end());
664 }
665};
666
667template <typename T>
668void SmallVectorImpl<T>::swap(SmallVectorImpl<T> &RHS) {
669 if (this == &RHS) return;
670
671 // We can only avoid copying elements if neither vector is small.
672 if (!this->isSmall() && !RHS.isSmall()) {
673 std::swap(this->BeginX, RHS.BeginX);
674 std::swap(this->Size, RHS.Size);
675 std::swap(this->Capacity, RHS.Capacity);
676 return;
677 }
678 if (RHS.size() > this->capacity())
679 this->grow(RHS.size());
680 if (this->size() > RHS.capacity())
681 RHS.grow(this->size());
682
683 // Swap the shared elements.
684 size_t NumShared = this->size();
685 if (NumShared > RHS.size()) NumShared = RHS.size();
686 for (size_type i = 0; i != NumShared; ++i)
687 std::swap((*this)[i], RHS[i]);
688
689 // Copy over the extra elts.
690 if (this->size() > RHS.size()) {
691 size_t EltDiff = this->size() - RHS.size();
692 this->uninitialized_copy(this->begin()+NumShared, this->end(), RHS.end());
693 RHS.set_size(RHS.size() + EltDiff);
694 this->destroy_range(this->begin()+NumShared, this->end());
695 this->set_size(NumShared);
696 } else if (RHS.size() > this->size()) {
697 size_t EltDiff = RHS.size() - this->size();
698 this->uninitialized_copy(RHS.begin()+NumShared, RHS.end(), this->end());
699 this->set_size(this->size() + EltDiff);
700 this->destroy_range(RHS.begin()+NumShared, RHS.end());
701 RHS.set_size(NumShared);
702 }
703}
704
705template <typename T>
706SmallVectorImpl<T> &SmallVectorImpl<T>::
707 operator=(const SmallVectorImpl<T> &RHS) {
708 // Avoid self-assignment.
709 if (this == &RHS) return *this;
710
711 // If we already have sufficient space, assign the common elements, then
712 // destroy any excess.
713 size_t RHSSize = RHS.size();
714 size_t CurSize = this->size();
715 if (CurSize >= RHSSize) {
716 // Assign common elements.
717 iterator NewEnd;
718 if (RHSSize)
719 NewEnd = std::copy(RHS.begin(), RHS.begin()+RHSSize, this->begin());
720 else
721 NewEnd = this->begin();
722
723 // Destroy excess elements.
724 this->destroy_range(NewEnd, this->end());
725
726 // Trim.
727 this->set_size(RHSSize);
728 return *this;
729 }
730
731 // If we have to grow to have enough elements, destroy the current elements.
732 // This allows us to avoid copying them during the grow.
733 // FIXME: don't do this if they're efficiently moveable.
734 if (this->capacity() < RHSSize) {
735 // Destroy current elements.
736 this->destroy_range(this->begin(), this->end());
737 this->set_size(0);
738 CurSize = 0;
739 this->grow(RHSSize);
740 } else if (CurSize) {
741 // Otherwise, use assignment for the already-constructed elements.
742 std::copy(RHS.begin(), RHS.begin()+CurSize, this->begin());
743 }
744
745 // Copy construct the new elements in place.
746 this->uninitialized_copy(RHS.begin()+CurSize, RHS.end(),
747 this->begin()+CurSize);
748
749 // Set end.
750 this->set_size(RHSSize);
751 return *this;
752}
753
754template <typename T>
755SmallVectorImpl<T> &SmallVectorImpl<T>::operator=(SmallVectorImpl<T> &&RHS) {
756 // Avoid self-assignment.
757 if (this == &RHS) return *this;
758
759 // If the RHS isn't small, clear this vector and then steal its buffer.
760 if (!RHS.isSmall()) {
761 this->destroy_range(this->begin(), this->end());
762 if (!this->isSmall()) free(this->begin());
763 this->BeginX = RHS.BeginX;
764 this->Size = RHS.Size;
765 this->Capacity = RHS.Capacity;
766 RHS.resetToSmall();
767 return *this;
768 }
769
770 // If we already have sufficient space, assign the common elements, then
771 // destroy any excess.
772 size_t RHSSize = RHS.size();
773 size_t CurSize = this->size();
774 if (CurSize >= RHSSize) {
775 // Assign common elements.
776 iterator NewEnd = this->begin();
777 if (RHSSize)
778 NewEnd = std::move(RHS.begin(), RHS.end(), NewEnd);
779
780 // Destroy excess elements and trim the bounds.
781 this->destroy_range(NewEnd, this->end());
782 this->set_size(RHSSize);
783
784 // Clear the RHS.
785 RHS.clear();
786
787 return *this;
788 }
789
790 // If we have to grow to have enough elements, destroy the current elements.
791 // This allows us to avoid copying them during the grow.
792 // FIXME: this may not actually make any sense if we can efficiently move
793 // elements.
794 if (this->capacity() < RHSSize) {
795 // Destroy current elements.
796 this->destroy_range(this->begin(), this->end());
797 this->set_size(0);
798 CurSize = 0;
799 this->grow(RHSSize);
800 } else if (CurSize) {
801 // Otherwise, use assignment for the already-constructed elements.
802 std::move(RHS.begin(), RHS.begin()+CurSize, this->begin());
803 }
804
805 // Move-construct the new elements in place.
806 this->uninitialized_move(RHS.begin()+CurSize, RHS.end(),
807 this->begin()+CurSize);
808
809 // Set end.
810 this->set_size(RHSSize);
811
812 RHS.clear();
813 return *this;
814}
815
816/// Storage for the SmallVector elements. This is specialized for the N=0 case
817/// to avoid allocating unnecessary storage.
818template <typename T, unsigned N>
819struct SmallVectorStorage {
820 AlignedCharArrayUnion<T> InlineElts[N];
821};
822
823/// We need the storage to be properly aligned even for small-size of 0 so that
824/// the pointer math in \a SmallVectorTemplateCommon::getFirstEl() is
825/// well-defined.
826template <typename T> struct alignas(alignof(T)) SmallVectorStorage<T, 0> {};
827
828/// This is a 'vector' (really, a variable-sized array), optimized
829/// for the case when the array is small. It contains some number of elements
830/// in-place, which allows it to avoid heap allocation when the actual number of
831/// elements is below that threshold. This allows normal "small" cases to be
832/// fast without losing generality for large inputs.
833///
834/// Note that this does not attempt to be exception safe.
835///
836template <typename T, unsigned N>
837class SmallVector : public SmallVectorImpl<T>, SmallVectorStorage<T, N> {
838public:
839 SmallVector() : SmallVectorImpl<T>(N) {}
840
841 ~SmallVector() {
842 // Destroy the constructed elements in the vector.
843 this->destroy_range(this->begin(), this->end());
844 }
845
846 explicit SmallVector(size_t Size, const T &Value = T())
847 : SmallVectorImpl<T>(N) {
848 this->assign(Size, Value);
849 }
850
851 template <typename ItTy,
852 typename = typename std::enable_if<std::is_convertible<
853 typename std::iterator_traits<ItTy>::iterator_category,
854 std::input_iterator_tag>::value>::type>
855 SmallVector(ItTy S, ItTy E) : SmallVectorImpl<T>(N) {
856 this->append(S, E);
857 }
858
859 template <typename RangeTy>
860 explicit SmallVector(const iterator_range<RangeTy> &R)
861 : SmallVectorImpl<T>(N) {
862 this->append(R.begin(), R.end());
863 }
864
865 SmallVector(std::initializer_list<T> IL) : SmallVectorImpl<T>(N) {
866 this->assign(IL);
867 }
868
869 SmallVector(const SmallVector &RHS) : SmallVectorImpl<T>(N) {
870 if (!RHS.empty())
871 SmallVectorImpl<T>::operator=(RHS);
872 }
873
874 const SmallVector &operator=(const SmallVector &RHS) {
875 SmallVectorImpl<T>::operator=(RHS);
876 return *this;
877 }
878
879 SmallVector(SmallVector &&RHS) : SmallVectorImpl<T>(N) {
880 if (!RHS.empty())
881 SmallVectorImpl<T>::operator=(::std::move(RHS));
882 }
883
884 SmallVector(SmallVectorImpl<T> &&RHS) : SmallVectorImpl<T>(N) {
885 if (!RHS.empty())
886 SmallVectorImpl<T>::operator=(::std::move(RHS));
887 }
888
889 const SmallVector &operator=(SmallVector &&RHS) {
890 SmallVectorImpl<T>::operator=(::std::move(RHS));
891 return *this;
892 }
893
894 const SmallVector &operator=(SmallVectorImpl<T> &&RHS) {
895 SmallVectorImpl<T>::operator=(::std::move(RHS));
896 return *this;
897 }
898
899 const SmallVector &operator=(std::initializer_list<T> IL) {
900 this->assign(IL);
901 return *this;
902 }
903};
904
905template <typename T, unsigned N>
906inline size_t capacity_in_bytes(const SmallVector<T, N> &X) {
907 return X.capacity_in_bytes();
908}
909
910} // end namespace llvm
911
912namespace std {
913
914 /// Implement std::swap in terms of SmallVector swap.
915 template<typename T>
916 inline void
917 swap(llvm::SmallVectorImpl<T> &LHS, llvm::SmallVectorImpl<T> &RHS) {
918 LHS.swap(RHS);
919 }
920
921 /// Implement std::swap in terms of SmallVector swap.
922 template<typename T, unsigned N>
923 inline void
924 swap(llvm::SmallVector<T, N> &LHS, llvm::SmallVector<T, N> &RHS) {
925 LHS.swap(RHS);
926 }
927
928} // end namespace std
929
930#endif // LLVM_ADT_SMALLVECTOR_H