Bug Summary

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