1 //===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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.
14 //===----------------------------------------------------------------------===//
16 #include "llvm/Transforms/IPO.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/Statistic.h"
23 #include "llvm/Analysis/ConstantFolding.h"
24 #include "llvm/Analysis/MemoryBuiltins.h"
25 #include "llvm/IR/CallSite.h"
26 #include "llvm/IR/CallingConv.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/DataLayout.h"
29 #include "llvm/IR/DerivedTypes.h"
30 #include "llvm/IR/GetElementPtrTypeIterator.h"
31 #include "llvm/IR/Instructions.h"
32 #include "llvm/IR/IntrinsicInst.h"
33 #include "llvm/IR/Module.h"
34 #include "llvm/IR/Operator.h"
35 #include "llvm/IR/ValueHandle.h"
36 #include "llvm/Pass.h"
37 #include "llvm/Support/Debug.h"
38 #include "llvm/Support/ErrorHandling.h"
39 #include "llvm/Support/MathExtras.h"
40 #include "llvm/Support/raw_ostream.h"
41 #include "llvm/Target/TargetLibraryInfo.h"
42 #include "llvm/Transforms/Utils/CtorUtils.h"
43 #include "llvm/Transforms/Utils/GlobalStatus.h"
44 #include "llvm/Transforms/Utils/ModuleUtils.h"
49 #define DEBUG_TYPE "globalopt"
51 STATISTIC(NumMarked
, "Number of globals marked constant");
52 STATISTIC(NumUnnamed
, "Number of globals marked unnamed_addr");
53 STATISTIC(NumSRA
, "Number of aggregate globals broken into scalars");
54 STATISTIC(NumHeapSRA
, "Number of heap objects SRA'd");
55 STATISTIC(NumSubstitute
,"Number of globals with initializers stored into them");
56 STATISTIC(NumDeleted
, "Number of globals deleted");
57 STATISTIC(NumFnDeleted
, "Number of functions deleted");
58 STATISTIC(NumGlobUses
, "Number of global uses devirtualized");
59 STATISTIC(NumLocalized
, "Number of globals localized");
60 STATISTIC(NumShrunkToBool
, "Number of global vars shrunk to booleans");
61 STATISTIC(NumFastCallFns
, "Number of functions converted to fastcc");
62 STATISTIC(NumCtorsEvaluated
, "Number of static ctors evaluated");
63 STATISTIC(NumNestRemoved
, "Number of nest attributes removed");
64 STATISTIC(NumAliasesResolved
, "Number of global aliases resolved");
65 STATISTIC(NumAliasesRemoved
, "Number of global aliases eliminated");
66 STATISTIC(NumCXXDtorsRemoved
, "Number of global C++ destructors removed");
69 struct GlobalOpt
: public ModulePass
{
70 void getAnalysisUsage(AnalysisUsage
&AU
) const override
{
71 AU
.addRequired
<TargetLibraryInfo
>();
73 static char ID
; // Pass identification, replacement for typeid
74 GlobalOpt() : ModulePass(ID
) {
75 initializeGlobalOptPass(*PassRegistry::getPassRegistry());
78 bool runOnModule(Module
&M
) override
;
81 bool OptimizeFunctions(Module
&M
);
82 bool OptimizeGlobalVars(Module
&M
);
83 bool OptimizeGlobalAliases(Module
&M
);
84 bool ProcessGlobal(GlobalVariable
*GV
,Module::global_iterator
&GVI
);
85 bool ProcessInternalGlobal(GlobalVariable
*GV
,Module::global_iterator
&GVI
,
86 const GlobalStatus
&GS
);
87 bool OptimizeEmptyGlobalCXXDtors(Function
*CXAAtExitFn
);
90 TargetLibraryInfo
*TLI
;
91 SmallSet
<const Comdat
*, 8> NotDiscardableComdats
;
95 char GlobalOpt::ID
= 0;
96 INITIALIZE_PASS_BEGIN(GlobalOpt
, "globalopt",
97 "Global Variable Optimizer", false, false)
98 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo
)
99 INITIALIZE_PASS_END(GlobalOpt
, "globalopt",
100 "Global Variable Optimizer", false, false)
102 ModulePass
*llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
104 /// isLeakCheckerRoot - Is this global variable possibly used by a leak checker
105 /// as a root? If so, we might not really want to eliminate the stores to it.
106 static bool isLeakCheckerRoot(GlobalVariable
*GV
) {
107 // A global variable is a root if it is a pointer, or could plausibly contain
108 // a pointer. There are two challenges; one is that we could have a struct
109 // the has an inner member which is a pointer. We recurse through the type to
110 // detect these (up to a point). The other is that we may actually be a union
111 // of a pointer and another type, and so our LLVM type is an integer which
112 // gets converted into a pointer, or our type is an [i8 x #] with a pointer
113 // potentially contained here.
115 if (GV
->hasPrivateLinkage())
118 SmallVector
<Type
*, 4> Types
;
119 Types
.push_back(cast
<PointerType
>(GV
->getType())->getElementType());
123 Type
*Ty
= Types
.pop_back_val();
124 switch (Ty
->getTypeID()) {
126 case Type::PointerTyID
: return true;
127 case Type::ArrayTyID
:
128 case Type::VectorTyID
: {
129 SequentialType
*STy
= cast
<SequentialType
>(Ty
);
130 Types
.push_back(STy
->getElementType());
133 case Type::StructTyID
: {
134 StructType
*STy
= cast
<StructType
>(Ty
);
135 if (STy
->isOpaque()) return true;
136 for (StructType::element_iterator I
= STy
->element_begin(),
137 E
= STy
->element_end(); I
!= E
; ++I
) {
139 if (isa
<PointerType
>(InnerTy
)) return true;
140 if (isa
<CompositeType
>(InnerTy
))
141 Types
.push_back(InnerTy
);
146 if (--Limit
== 0) return true;
147 } while (!Types
.empty());
151 /// Given a value that is stored to a global but never read, determine whether
152 /// it's safe to remove the store and the chain of computation that feeds the
154 static bool IsSafeComputationToRemove(Value
*V
, const TargetLibraryInfo
*TLI
) {
156 if (isa
<Constant
>(V
))
160 if (isa
<LoadInst
>(V
) || isa
<InvokeInst
>(V
) || isa
<Argument
>(V
) ||
163 if (isAllocationFn(V
, TLI
))
166 Instruction
*I
= cast
<Instruction
>(V
);
167 if (I
->mayHaveSideEffects())
169 if (GetElementPtrInst
*GEP
= dyn_cast
<GetElementPtrInst
>(I
)) {
170 if (!GEP
->hasAllConstantIndices())
172 } else if (I
->getNumOperands() != 1) {
176 V
= I
->getOperand(0);
180 /// CleanupPointerRootUsers - This GV is a pointer root. Loop over all users
181 /// of the global and clean up any that obviously don't assign the global a
182 /// value that isn't dynamically allocated.
184 static bool CleanupPointerRootUsers(GlobalVariable
*GV
,
185 const TargetLibraryInfo
*TLI
) {
186 // A brief explanation of leak checkers. The goal is to find bugs where
187 // pointers are forgotten, causing an accumulating growth in memory
188 // usage over time. The common strategy for leak checkers is to whitelist the
189 // memory pointed to by globals at exit. This is popular because it also
190 // solves another problem where the main thread of a C++ program may shut down
191 // before other threads that are still expecting to use those globals. To
192 // handle that case, we expect the program may create a singleton and never
195 bool Changed
= false;
197 // If Dead[n].first is the only use of a malloc result, we can delete its
198 // chain of computation and the store to the global in Dead[n].second.
199 SmallVector
<std::pair
<Instruction
*, Instruction
*>, 32> Dead
;
201 // Constants can't be pointers to dynamically allocated memory.
202 for (Value::user_iterator UI
= GV
->user_begin(), E
= GV
->user_end();
205 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(U
)) {
206 Value
*V
= SI
->getValueOperand();
207 if (isa
<Constant
>(V
)) {
209 SI
->eraseFromParent();
210 } else if (Instruction
*I
= dyn_cast
<Instruction
>(V
)) {
212 Dead
.push_back(std::make_pair(I
, SI
));
214 } else if (MemSetInst
*MSI
= dyn_cast
<MemSetInst
>(U
)) {
215 if (isa
<Constant
>(MSI
->getValue())) {
217 MSI
->eraseFromParent();
218 } else if (Instruction
*I
= dyn_cast
<Instruction
>(MSI
->getValue())) {
220 Dead
.push_back(std::make_pair(I
, MSI
));
222 } else if (MemTransferInst
*MTI
= dyn_cast
<MemTransferInst
>(U
)) {
223 GlobalVariable
*MemSrc
= dyn_cast
<GlobalVariable
>(MTI
->getSource());
224 if (MemSrc
&& MemSrc
->isConstant()) {
226 MTI
->eraseFromParent();
227 } else if (Instruction
*I
= dyn_cast
<Instruction
>(MemSrc
)) {
229 Dead
.push_back(std::make_pair(I
, MTI
));
231 } else if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(U
)) {
232 if (CE
->use_empty()) {
233 CE
->destroyConstant();
236 } else if (Constant
*C
= dyn_cast
<Constant
>(U
)) {
237 if (isSafeToDestroyConstant(C
)) {
238 C
->destroyConstant();
239 // This could have invalidated UI, start over from scratch.
241 CleanupPointerRootUsers(GV
, TLI
);
247 for (int i
= 0, e
= Dead
.size(); i
!= e
; ++i
) {
248 if (IsSafeComputationToRemove(Dead
[i
].first
, TLI
)) {
249 Dead
[i
].second
->eraseFromParent();
250 Instruction
*I
= Dead
[i
].first
;
252 if (isAllocationFn(I
, TLI
))
254 Instruction
*J
= dyn_cast
<Instruction
>(I
->getOperand(0));
257 I
->eraseFromParent();
260 I
->eraseFromParent();
267 /// CleanupConstantGlobalUsers - We just marked GV constant. Loop over all
268 /// users of the global, cleaning up the obvious ones. This is largely just a
269 /// quick scan over the use list to clean up the easy and obvious cruft. This
270 /// returns true if it made a change.
271 static bool CleanupConstantGlobalUsers(Value
*V
, Constant
*Init
,
272 const DataLayout
*DL
,
273 TargetLibraryInfo
*TLI
) {
274 bool Changed
= false;
275 // Note that we need to use a weak value handle for the worklist items. When
276 // we delete a constant array, we may also be holding pointer to one of its
277 // elements (or an element of one of its elements if we're dealing with an
278 // array of arrays) in the worklist.
279 SmallVector
<WeakVH
, 8> WorkList(V
->user_begin(), V
->user_end());
280 while (!WorkList
.empty()) {
281 Value
*UV
= WorkList
.pop_back_val();
285 User
*U
= cast
<User
>(UV
);
287 if (LoadInst
*LI
= dyn_cast
<LoadInst
>(U
)) {
289 // Replace the load with the initializer.
290 LI
->replaceAllUsesWith(Init
);
291 LI
->eraseFromParent();
294 } else if (StoreInst
*SI
= dyn_cast
<StoreInst
>(U
)) {
295 // Store must be unreachable or storing Init into the global.
296 SI
->eraseFromParent();
298 } else if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(U
)) {
299 if (CE
->getOpcode() == Instruction::GetElementPtr
) {
300 Constant
*SubInit
= nullptr;
302 SubInit
= ConstantFoldLoadThroughGEPConstantExpr(Init
, CE
);
303 Changed
|= CleanupConstantGlobalUsers(CE
, SubInit
, DL
, TLI
);
304 } else if ((CE
->getOpcode() == Instruction::BitCast
&&
305 CE
->getType()->isPointerTy()) ||
306 CE
->getOpcode() == Instruction::AddrSpaceCast
) {
307 // Pointer cast, delete any stores and memsets to the global.
308 Changed
|= CleanupConstantGlobalUsers(CE
, nullptr, DL
, TLI
);
311 if (CE
->use_empty()) {
312 CE
->destroyConstant();
315 } else if (GetElementPtrInst
*GEP
= dyn_cast
<GetElementPtrInst
>(U
)) {
316 // Do not transform "gepinst (gep constexpr (GV))" here, because forming
317 // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold
318 // and will invalidate our notion of what Init is.
319 Constant
*SubInit
= nullptr;
320 if (!isa
<ConstantExpr
>(GEP
->getOperand(0))) {
322 dyn_cast_or_null
<ConstantExpr
>(ConstantFoldInstruction(GEP
, DL
, TLI
));
323 if (Init
&& CE
&& CE
->getOpcode() == Instruction::GetElementPtr
)
324 SubInit
= ConstantFoldLoadThroughGEPConstantExpr(Init
, CE
);
326 // If the initializer is an all-null value and we have an inbounds GEP,
327 // we already know what the result of any load from that GEP is.
328 // TODO: Handle splats.
329 if (Init
&& isa
<ConstantAggregateZero
>(Init
) && GEP
->isInBounds())
330 SubInit
= Constant::getNullValue(GEP
->getType()->getElementType());
332 Changed
|= CleanupConstantGlobalUsers(GEP
, SubInit
, DL
, TLI
);
334 if (GEP
->use_empty()) {
335 GEP
->eraseFromParent();
338 } else if (MemIntrinsic
*MI
= dyn_cast
<MemIntrinsic
>(U
)) { // memset/cpy/mv
339 if (MI
->getRawDest() == V
) {
340 MI
->eraseFromParent();
344 } else if (Constant
*C
= dyn_cast
<Constant
>(U
)) {
345 // If we have a chain of dead constantexprs or other things dangling from
346 // us, and if they are all dead, nuke them without remorse.
347 if (isSafeToDestroyConstant(C
)) {
348 C
->destroyConstant();
349 CleanupConstantGlobalUsers(V
, Init
, DL
, TLI
);
357 /// isSafeSROAElementUse - Return true if the specified instruction is a safe
358 /// user of a derived expression from a global that we want to SROA.
359 static bool isSafeSROAElementUse(Value
*V
) {
360 // We might have a dead and dangling constant hanging off of here.
361 if (Constant
*C
= dyn_cast
<Constant
>(V
))
362 return isSafeToDestroyConstant(C
);
364 Instruction
*I
= dyn_cast
<Instruction
>(V
);
365 if (!I
) return false;
368 if (isa
<LoadInst
>(I
)) return true;
370 // Stores *to* the pointer are ok.
371 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(I
))
372 return SI
->getOperand(0) != V
;
374 // Otherwise, it must be a GEP.
375 GetElementPtrInst
*GEPI
= dyn_cast
<GetElementPtrInst
>(I
);
376 if (!GEPI
) return false;
378 if (GEPI
->getNumOperands() < 3 || !isa
<Constant
>(GEPI
->getOperand(1)) ||
379 !cast
<Constant
>(GEPI
->getOperand(1))->isNullValue())
382 for (User
*U
: GEPI
->users())
383 if (!isSafeSROAElementUse(U
))
389 /// IsUserOfGlobalSafeForSRA - U is a direct user of the specified global value.
390 /// Look at it and its uses and decide whether it is safe to SROA this global.
392 static bool IsUserOfGlobalSafeForSRA(User
*U
, GlobalValue
*GV
) {
393 // The user of the global must be a GEP Inst or a ConstantExpr GEP.
394 if (!isa
<GetElementPtrInst
>(U
) &&
395 (!isa
<ConstantExpr
>(U
) ||
396 cast
<ConstantExpr
>(U
)->getOpcode() != Instruction::GetElementPtr
))
399 // Check to see if this ConstantExpr GEP is SRA'able. In particular, we
400 // don't like < 3 operand CE's, and we don't like non-constant integer
401 // indices. This enforces that all uses are 'gep GV, 0, C, ...' for some
403 if (U
->getNumOperands() < 3 || !isa
<Constant
>(U
->getOperand(1)) ||
404 !cast
<Constant
>(U
->getOperand(1))->isNullValue() ||
405 !isa
<ConstantInt
>(U
->getOperand(2)))
408 gep_type_iterator GEPI
= gep_type_begin(U
), E
= gep_type_end(U
);
409 ++GEPI
; // Skip over the pointer index.
411 // If this is a use of an array allocation, do a bit more checking for sanity.
412 if (ArrayType
*AT
= dyn_cast
<ArrayType
>(*GEPI
)) {
413 uint64_t NumElements
= AT
->getNumElements();
414 ConstantInt
*Idx
= cast
<ConstantInt
>(U
->getOperand(2));
416 // Check to make sure that index falls within the array. If not,
417 // something funny is going on, so we won't do the optimization.
419 if (Idx
->getZExtValue() >= NumElements
)
422 // We cannot scalar repl this level of the array unless any array
423 // sub-indices are in-range constants. In particular, consider:
424 // A[0][i]. We cannot know that the user isn't doing invalid things like
425 // allowing i to index an out-of-range subscript that accesses A[1].
427 // Scalar replacing *just* the outer index of the array is probably not
428 // going to be a win anyway, so just give up.
429 for (++GEPI
; // Skip array index.
432 uint64_t NumElements
;
433 if (ArrayType
*SubArrayTy
= dyn_cast
<ArrayType
>(*GEPI
))
434 NumElements
= SubArrayTy
->getNumElements();
435 else if (VectorType
*SubVectorTy
= dyn_cast
<VectorType
>(*GEPI
))
436 NumElements
= SubVectorTy
->getNumElements();
438 assert((*GEPI
)->isStructTy() &&
439 "Indexed GEP type is not array, vector, or struct!");
443 ConstantInt
*IdxVal
= dyn_cast
<ConstantInt
>(GEPI
.getOperand());
444 if (!IdxVal
|| IdxVal
->getZExtValue() >= NumElements
)
449 for (User
*UU
: U
->users())
450 if (!isSafeSROAElementUse(UU
))
456 /// GlobalUsersSafeToSRA - Look at all uses of the global and decide whether it
457 /// is safe for us to perform this transformation.
459 static bool GlobalUsersSafeToSRA(GlobalValue
*GV
) {
460 for (User
*U
: GV
->users())
461 if (!IsUserOfGlobalSafeForSRA(U
, GV
))
468 /// SRAGlobal - Perform scalar replacement of aggregates on the specified global
469 /// variable. This opens the door for other optimizations by exposing the
470 /// behavior of the program in a more fine-grained way. We have determined that
471 /// this transformation is safe already. We return the first global variable we
472 /// insert so that the caller can reprocess it.
473 static GlobalVariable
*SRAGlobal(GlobalVariable
*GV
, const DataLayout
&DL
) {
474 // Make sure this global only has simple uses that we can SRA.
475 if (!GlobalUsersSafeToSRA(GV
))
478 assert(GV
->hasLocalLinkage() && !GV
->isConstant());
479 Constant
*Init
= GV
->getInitializer();
480 Type
*Ty
= Init
->getType();
482 std::vector
<GlobalVariable
*> NewGlobals
;
483 Module::GlobalListType
&Globals
= GV
->getParent()->getGlobalList();
485 // Get the alignment of the global, either explicit or target-specific.
486 unsigned StartAlignment
= GV
->getAlignment();
487 if (StartAlignment
== 0)
488 StartAlignment
= DL
.getABITypeAlignment(GV
->getType());
490 if (StructType
*STy
= dyn_cast
<StructType
>(Ty
)) {
491 NewGlobals
.reserve(STy
->getNumElements());
492 const StructLayout
&Layout
= *DL
.getStructLayout(STy
);
493 for (unsigned i
= 0, e
= STy
->getNumElements(); i
!= e
; ++i
) {
494 Constant
*In
= Init
->getAggregateElement(i
);
495 assert(In
&& "Couldn't get element of initializer?");
496 GlobalVariable
*NGV
= new GlobalVariable(STy
->getElementType(i
), false,
497 GlobalVariable::InternalLinkage
,
498 In
, GV
->getName()+"."+Twine(i
),
499 GV
->getThreadLocalMode(),
500 GV
->getType()->getAddressSpace());
501 Globals
.insert(GV
, NGV
);
502 NewGlobals
.push_back(NGV
);
504 // Calculate the known alignment of the field. If the original aggregate
505 // had 256 byte alignment for example, something might depend on that:
506 // propagate info to each field.
507 uint64_t FieldOffset
= Layout
.getElementOffset(i
);
508 unsigned NewAlign
= (unsigned)MinAlign(StartAlignment
, FieldOffset
);
509 if (NewAlign
> DL
.getABITypeAlignment(STy
->getElementType(i
)))
510 NGV
->setAlignment(NewAlign
);
512 } else if (SequentialType
*STy
= dyn_cast
<SequentialType
>(Ty
)) {
513 unsigned NumElements
= 0;
514 if (ArrayType
*ATy
= dyn_cast
<ArrayType
>(STy
))
515 NumElements
= ATy
->getNumElements();
517 NumElements
= cast
<VectorType
>(STy
)->getNumElements();
519 if (NumElements
> 16 && GV
->hasNUsesOrMore(16))
520 return nullptr; // It's not worth it.
521 NewGlobals
.reserve(NumElements
);
523 uint64_t EltSize
= DL
.getTypeAllocSize(STy
->getElementType());
524 unsigned EltAlign
= DL
.getABITypeAlignment(STy
->getElementType());
525 for (unsigned i
= 0, e
= NumElements
; i
!= e
; ++i
) {
526 Constant
*In
= Init
->getAggregateElement(i
);
527 assert(In
&& "Couldn't get element of initializer?");
529 GlobalVariable
*NGV
= new GlobalVariable(STy
->getElementType(), false,
530 GlobalVariable::InternalLinkage
,
531 In
, GV
->getName()+"."+Twine(i
),
532 GV
->getThreadLocalMode(),
533 GV
->getType()->getAddressSpace());
534 Globals
.insert(GV
, NGV
);
535 NewGlobals
.push_back(NGV
);
537 // Calculate the known alignment of the field. If the original aggregate
538 // had 256 byte alignment for example, something might depend on that:
539 // propagate info to each field.
540 unsigned NewAlign
= (unsigned)MinAlign(StartAlignment
, EltSize
*i
);
541 if (NewAlign
> EltAlign
)
542 NGV
->setAlignment(NewAlign
);
546 if (NewGlobals
.empty())
549 DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV
);
551 Constant
*NullInt
=Constant::getNullValue(Type::getInt32Ty(GV
->getContext()));
553 // Loop over all of the uses of the global, replacing the constantexpr geps,
554 // with smaller constantexpr geps or direct references.
555 while (!GV
->use_empty()) {
556 User
*GEP
= GV
->user_back();
557 assert(((isa
<ConstantExpr
>(GEP
) &&
558 cast
<ConstantExpr
>(GEP
)->getOpcode()==Instruction::GetElementPtr
)||
559 isa
<GetElementPtrInst
>(GEP
)) && "NonGEP CE's are not SRAable!");
561 // Ignore the 1th operand, which has to be zero or else the program is quite
562 // broken (undefined). Get the 2nd operand, which is the structure or array
564 unsigned Val
= cast
<ConstantInt
>(GEP
->getOperand(2))->getZExtValue();
565 if (Val
>= NewGlobals
.size()) Val
= 0; // Out of bound array access.
567 Value
*NewPtr
= NewGlobals
[Val
];
569 // Form a shorter GEP if needed.
570 if (GEP
->getNumOperands() > 3) {
571 if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(GEP
)) {
572 SmallVector
<Constant
*, 8> Idxs
;
573 Idxs
.push_back(NullInt
);
574 for (unsigned i
= 3, e
= CE
->getNumOperands(); i
!= e
; ++i
)
575 Idxs
.push_back(CE
->getOperand(i
));
576 NewPtr
= ConstantExpr::getGetElementPtr(cast
<Constant
>(NewPtr
), Idxs
);
578 GetElementPtrInst
*GEPI
= cast
<GetElementPtrInst
>(GEP
);
579 SmallVector
<Value
*, 8> Idxs
;
580 Idxs
.push_back(NullInt
);
581 for (unsigned i
= 3, e
= GEPI
->getNumOperands(); i
!= e
; ++i
)
582 Idxs
.push_back(GEPI
->getOperand(i
));
583 NewPtr
= GetElementPtrInst::Create(NewPtr
, Idxs
,
584 GEPI
->getName()+"."+Twine(Val
),GEPI
);
587 GEP
->replaceAllUsesWith(NewPtr
);
589 if (GetElementPtrInst
*GEPI
= dyn_cast
<GetElementPtrInst
>(GEP
))
590 GEPI
->eraseFromParent();
592 cast
<ConstantExpr
>(GEP
)->destroyConstant();
595 // Delete the old global, now that it is dead.
599 // Loop over the new globals array deleting any globals that are obviously
600 // dead. This can arise due to scalarization of a structure or an array that
601 // has elements that are dead.
602 unsigned FirstGlobal
= 0;
603 for (unsigned i
= 0, e
= NewGlobals
.size(); i
!= e
; ++i
)
604 if (NewGlobals
[i
]->use_empty()) {
605 Globals
.erase(NewGlobals
[i
]);
606 if (FirstGlobal
== i
) ++FirstGlobal
;
609 return FirstGlobal
!= NewGlobals
.size() ? NewGlobals
[FirstGlobal
] : nullptr;
612 /// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified
613 /// value will trap if the value is dynamically null. PHIs keeps track of any
614 /// phi nodes we've seen to avoid reprocessing them.
615 static bool AllUsesOfValueWillTrapIfNull(const Value
*V
,
616 SmallPtrSetImpl
<const PHINode
*> &PHIs
) {
617 for (const User
*U
: V
->users())
618 if (isa
<LoadInst
>(U
)) {
620 } else if (const StoreInst
*SI
= dyn_cast
<StoreInst
>(U
)) {
621 if (SI
->getOperand(0) == V
) {
622 //cerr << "NONTRAPPING USE: " << *U;
623 return false; // Storing the value.
625 } else if (const CallInst
*CI
= dyn_cast
<CallInst
>(U
)) {
626 if (CI
->getCalledValue() != V
) {
627 //cerr << "NONTRAPPING USE: " << *U;
628 return false; // Not calling the ptr
630 } else if (const InvokeInst
*II
= dyn_cast
<InvokeInst
>(U
)) {
631 if (II
->getCalledValue() != V
) {
632 //cerr << "NONTRAPPING USE: " << *U;
633 return false; // Not calling the ptr
635 } else if (const BitCastInst
*CI
= dyn_cast
<BitCastInst
>(U
)) {
636 if (!AllUsesOfValueWillTrapIfNull(CI
, PHIs
)) return false;
637 } else if (const GetElementPtrInst
*GEPI
= dyn_cast
<GetElementPtrInst
>(U
)) {
638 if (!AllUsesOfValueWillTrapIfNull(GEPI
, PHIs
)) return false;
639 } else if (const PHINode
*PN
= dyn_cast
<PHINode
>(U
)) {
640 // If we've already seen this phi node, ignore it, it has already been
642 if (PHIs
.insert(PN
).second
&& !AllUsesOfValueWillTrapIfNull(PN
, PHIs
))
644 } else if (isa
<ICmpInst
>(U
) &&
645 isa
<ConstantPointerNull
>(U
->getOperand(1))) {
646 // Ignore icmp X, null
648 //cerr << "NONTRAPPING USE: " << *U;
655 /// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads
656 /// from GV will trap if the loaded value is null. Note that this also permits
657 /// comparisons of the loaded value against null, as a special case.
658 static bool AllUsesOfLoadedValueWillTrapIfNull(const GlobalVariable
*GV
) {
659 for (const User
*U
: GV
->users())
660 if (const LoadInst
*LI
= dyn_cast
<LoadInst
>(U
)) {
661 SmallPtrSet
<const PHINode
*, 8> PHIs
;
662 if (!AllUsesOfValueWillTrapIfNull(LI
, PHIs
))
664 } else if (isa
<StoreInst
>(U
)) {
665 // Ignore stores to the global.
667 // We don't know or understand this user, bail out.
668 //cerr << "UNKNOWN USER OF GLOBAL!: " << *U;
674 static bool OptimizeAwayTrappingUsesOfValue(Value
*V
, Constant
*NewV
) {
675 bool Changed
= false;
676 for (auto UI
= V
->user_begin(), E
= V
->user_end(); UI
!= E
; ) {
677 Instruction
*I
= cast
<Instruction
>(*UI
++);
678 if (LoadInst
*LI
= dyn_cast
<LoadInst
>(I
)) {
679 LI
->setOperand(0, NewV
);
681 } else if (StoreInst
*SI
= dyn_cast
<StoreInst
>(I
)) {
682 if (SI
->getOperand(1) == V
) {
683 SI
->setOperand(1, NewV
);
686 } else if (isa
<CallInst
>(I
) || isa
<InvokeInst
>(I
)) {
688 if (CS
.getCalledValue() == V
) {
689 // Calling through the pointer! Turn into a direct call, but be careful
690 // that the pointer is not also being passed as an argument.
691 CS
.setCalledFunction(NewV
);
693 bool PassedAsArg
= false;
694 for (unsigned i
= 0, e
= CS
.arg_size(); i
!= e
; ++i
)
695 if (CS
.getArgument(i
) == V
) {
697 CS
.setArgument(i
, NewV
);
701 // Being passed as an argument also. Be careful to not invalidate UI!
702 UI
= V
->user_begin();
705 } else if (CastInst
*CI
= dyn_cast
<CastInst
>(I
)) {
706 Changed
|= OptimizeAwayTrappingUsesOfValue(CI
,
707 ConstantExpr::getCast(CI
->getOpcode(),
708 NewV
, CI
->getType()));
709 if (CI
->use_empty()) {
711 CI
->eraseFromParent();
713 } else if (GetElementPtrInst
*GEPI
= dyn_cast
<GetElementPtrInst
>(I
)) {
714 // Should handle GEP here.
715 SmallVector
<Constant
*, 8> Idxs
;
716 Idxs
.reserve(GEPI
->getNumOperands()-1);
717 for (User::op_iterator i
= GEPI
->op_begin() + 1, e
= GEPI
->op_end();
719 if (Constant
*C
= dyn_cast
<Constant
>(*i
))
723 if (Idxs
.size() == GEPI
->getNumOperands()-1)
724 Changed
|= OptimizeAwayTrappingUsesOfValue(GEPI
,
725 ConstantExpr::getGetElementPtr(NewV
, Idxs
));
726 if (GEPI
->use_empty()) {
728 GEPI
->eraseFromParent();
737 /// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null
738 /// value stored into it. If there are uses of the loaded value that would trap
739 /// if the loaded value is dynamically null, then we know that they cannot be
740 /// reachable with a null optimize away the load.
741 static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable
*GV
, Constant
*LV
,
742 const DataLayout
*DL
,
743 TargetLibraryInfo
*TLI
) {
744 bool Changed
= false;
746 // Keep track of whether we are able to remove all the uses of the global
747 // other than the store that defines it.
748 bool AllNonStoreUsesGone
= true;
750 // Replace all uses of loads with uses of uses of the stored value.
751 for (Value::user_iterator GUI
= GV
->user_begin(), E
= GV
->user_end(); GUI
!= E
;){
752 User
*GlobalUser
= *GUI
++;
753 if (LoadInst
*LI
= dyn_cast
<LoadInst
>(GlobalUser
)) {
754 Changed
|= OptimizeAwayTrappingUsesOfValue(LI
, LV
);
755 // If we were able to delete all uses of the loads
756 if (LI
->use_empty()) {
757 LI
->eraseFromParent();
760 AllNonStoreUsesGone
= false;
762 } else if (isa
<StoreInst
>(GlobalUser
)) {
763 // Ignore the store that stores "LV" to the global.
764 assert(GlobalUser
->getOperand(1) == GV
&&
765 "Must be storing *to* the global");
767 AllNonStoreUsesGone
= false;
769 // If we get here we could have other crazy uses that are transitively
771 assert((isa
<PHINode
>(GlobalUser
) || isa
<SelectInst
>(GlobalUser
) ||
772 isa
<ConstantExpr
>(GlobalUser
) || isa
<CmpInst
>(GlobalUser
) ||
773 isa
<BitCastInst
>(GlobalUser
) ||
774 isa
<GetElementPtrInst
>(GlobalUser
)) &&
775 "Only expect load and stores!");
780 DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV
);
784 // If we nuked all of the loads, then none of the stores are needed either,
785 // nor is the global.
786 if (AllNonStoreUsesGone
) {
787 if (isLeakCheckerRoot(GV
)) {
788 Changed
|= CleanupPointerRootUsers(GV
, TLI
);
791 CleanupConstantGlobalUsers(GV
, nullptr, DL
, TLI
);
793 if (GV
->use_empty()) {
794 DEBUG(dbgs() << " *** GLOBAL NOW DEAD!\n");
796 GV
->eraseFromParent();
803 /// ConstantPropUsersOf - Walk the use list of V, constant folding all of the
804 /// instructions that are foldable.
805 static void ConstantPropUsersOf(Value
*V
, const DataLayout
*DL
,
806 TargetLibraryInfo
*TLI
) {
807 for (Value::user_iterator UI
= V
->user_begin(), E
= V
->user_end(); UI
!= E
; )
808 if (Instruction
*I
= dyn_cast
<Instruction
>(*UI
++))
809 if (Constant
*NewC
= ConstantFoldInstruction(I
, DL
, TLI
)) {
810 I
->replaceAllUsesWith(NewC
);
812 // Advance UI to the next non-I use to avoid invalidating it!
813 // Instructions could multiply use V.
814 while (UI
!= E
&& *UI
== I
)
816 I
->eraseFromParent();
820 /// OptimizeGlobalAddressOfMalloc - This function takes the specified global
821 /// variable, and transforms the program as if it always contained the result of
822 /// the specified malloc. Because it is always the result of the specified
823 /// malloc, there is no reason to actually DO the malloc. Instead, turn the
824 /// malloc into a global, and any loads of GV as uses of the new global.
825 static GlobalVariable
*OptimizeGlobalAddressOfMalloc(GlobalVariable
*GV
,
828 ConstantInt
*NElements
,
829 const DataLayout
*DL
,
830 TargetLibraryInfo
*TLI
) {
831 DEBUG(errs() << "PROMOTING GLOBAL: " << *GV
<< " CALL = " << *CI
<< '\n');
834 if (NElements
->getZExtValue() == 1)
835 GlobalType
= AllocTy
;
837 // If we have an array allocation, the global variable is of an array.
838 GlobalType
= ArrayType::get(AllocTy
, NElements
->getZExtValue());
840 // Create the new global variable. The contents of the malloc'd memory is
841 // undefined, so initialize with an undef value.
842 GlobalVariable
*NewGV
= new GlobalVariable(*GV
->getParent(),
844 GlobalValue::InternalLinkage
,
845 UndefValue::get(GlobalType
),
846 GV
->getName()+".body",
848 GV
->getThreadLocalMode());
850 // If there are bitcast users of the malloc (which is typical, usually we have
851 // a malloc + bitcast) then replace them with uses of the new global. Update
852 // other users to use the global as well.
853 BitCastInst
*TheBC
= nullptr;
854 while (!CI
->use_empty()) {
855 Instruction
*User
= cast
<Instruction
>(CI
->user_back());
856 if (BitCastInst
*BCI
= dyn_cast
<BitCastInst
>(User
)) {
857 if (BCI
->getType() == NewGV
->getType()) {
858 BCI
->replaceAllUsesWith(NewGV
);
859 BCI
->eraseFromParent();
861 BCI
->setOperand(0, NewGV
);
865 TheBC
= new BitCastInst(NewGV
, CI
->getType(), "newgv", CI
);
866 User
->replaceUsesOfWith(CI
, TheBC
);
870 Constant
*RepValue
= NewGV
;
871 if (NewGV
->getType() != GV
->getType()->getElementType())
872 RepValue
= ConstantExpr::getBitCast(RepValue
,
873 GV
->getType()->getElementType());
875 // If there is a comparison against null, we will insert a global bool to
876 // keep track of whether the global was initialized yet or not.
877 GlobalVariable
*InitBool
=
878 new GlobalVariable(Type::getInt1Ty(GV
->getContext()), false,
879 GlobalValue::InternalLinkage
,
880 ConstantInt::getFalse(GV
->getContext()),
881 GV
->getName()+".init", GV
->getThreadLocalMode());
882 bool InitBoolUsed
= false;
884 // Loop over all uses of GV, processing them in turn.
885 while (!GV
->use_empty()) {
886 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(GV
->user_back())) {
887 // The global is initialized when the store to it occurs.
888 new StoreInst(ConstantInt::getTrue(GV
->getContext()), InitBool
, false, 0,
889 SI
->getOrdering(), SI
->getSynchScope(), SI
);
890 SI
->eraseFromParent();
894 LoadInst
*LI
= cast
<LoadInst
>(GV
->user_back());
895 while (!LI
->use_empty()) {
896 Use
&LoadUse
= *LI
->use_begin();
897 ICmpInst
*ICI
= dyn_cast
<ICmpInst
>(LoadUse
.getUser());
903 // Replace the cmp X, 0 with a use of the bool value.
904 // Sink the load to where the compare was, if atomic rules allow us to.
905 Value
*LV
= new LoadInst(InitBool
, InitBool
->getName()+".val", false, 0,
906 LI
->getOrdering(), LI
->getSynchScope(),
907 LI
->isUnordered() ? (Instruction
*)ICI
: LI
);
909 switch (ICI
->getPredicate()) {
910 default: llvm_unreachable("Unknown ICmp Predicate!");
911 case ICmpInst::ICMP_ULT
:
912 case ICmpInst::ICMP_SLT
: // X < null -> always false
913 LV
= ConstantInt::getFalse(GV
->getContext());
915 case ICmpInst::ICMP_ULE
:
916 case ICmpInst::ICMP_SLE
:
917 case ICmpInst::ICMP_EQ
:
918 LV
= BinaryOperator::CreateNot(LV
, "notinit", ICI
);
920 case ICmpInst::ICMP_NE
:
921 case ICmpInst::ICMP_UGE
:
922 case ICmpInst::ICMP_SGE
:
923 case ICmpInst::ICMP_UGT
:
924 case ICmpInst::ICMP_SGT
:
927 ICI
->replaceAllUsesWith(LV
);
928 ICI
->eraseFromParent();
930 LI
->eraseFromParent();
933 // If the initialization boolean was used, insert it, otherwise delete it.
935 while (!InitBool
->use_empty()) // Delete initializations
936 cast
<StoreInst
>(InitBool
->user_back())->eraseFromParent();
939 GV
->getParent()->getGlobalList().insert(GV
, InitBool
);
941 // Now the GV is dead, nuke it and the malloc..
942 GV
->eraseFromParent();
943 CI
->eraseFromParent();
945 // To further other optimizations, loop over all users of NewGV and try to
946 // constant prop them. This will promote GEP instructions with constant
947 // indices into GEP constant-exprs, which will allow global-opt to hack on it.
948 ConstantPropUsersOf(NewGV
, DL
, TLI
);
949 if (RepValue
!= NewGV
)
950 ConstantPropUsersOf(RepValue
, DL
, TLI
);
955 /// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking
956 /// to make sure that there are no complex uses of V. We permit simple things
957 /// like dereferencing the pointer, but not storing through the address, unless
958 /// it is to the specified global.
959 static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(const Instruction
*V
,
960 const GlobalVariable
*GV
,
961 SmallPtrSetImpl
<const PHINode
*> &PHIs
) {
962 for (const User
*U
: V
->users()) {
963 const Instruction
*Inst
= cast
<Instruction
>(U
);
965 if (isa
<LoadInst
>(Inst
) || isa
<CmpInst
>(Inst
)) {
966 continue; // Fine, ignore.
969 if (const StoreInst
*SI
= dyn_cast
<StoreInst
>(Inst
)) {
970 if (SI
->getOperand(0) == V
&& SI
->getOperand(1) != GV
)
971 return false; // Storing the pointer itself... bad.
972 continue; // Otherwise, storing through it, or storing into GV... fine.
975 // Must index into the array and into the struct.
976 if (isa
<GetElementPtrInst
>(Inst
) && Inst
->getNumOperands() >= 3) {
977 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Inst
, GV
, PHIs
))
982 if (const PHINode
*PN
= dyn_cast
<PHINode
>(Inst
)) {
983 // PHIs are ok if all uses are ok. Don't infinitely recurse through PHI
985 if (PHIs
.insert(PN
).second
)
986 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(PN
, GV
, PHIs
))
991 if (const BitCastInst
*BCI
= dyn_cast
<BitCastInst
>(Inst
)) {
992 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(BCI
, GV
, PHIs
))
1002 /// ReplaceUsesOfMallocWithGlobal - The Alloc pointer is stored into GV
1003 /// somewhere. Transform all uses of the allocation into loads from the
1004 /// global and uses of the resultant pointer. Further, delete the store into
1005 /// GV. This assumes that these value pass the
1006 /// 'ValueIsOnlyUsedLocallyOrStoredToOneGlobal' predicate.
1007 static void ReplaceUsesOfMallocWithGlobal(Instruction
*Alloc
,
1008 GlobalVariable
*GV
) {
1009 while (!Alloc
->use_empty()) {
1010 Instruction
*U
= cast
<Instruction
>(*Alloc
->user_begin());
1011 Instruction
*InsertPt
= U
;
1012 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(U
)) {
1013 // If this is the store of the allocation into the global, remove it.
1014 if (SI
->getOperand(1) == GV
) {
1015 SI
->eraseFromParent();
1018 } else if (PHINode
*PN
= dyn_cast
<PHINode
>(U
)) {
1019 // Insert the load in the corresponding predecessor, not right before the
1021 InsertPt
= PN
->getIncomingBlock(*Alloc
->use_begin())->getTerminator();
1022 } else if (isa
<BitCastInst
>(U
)) {
1023 // Must be bitcast between the malloc and store to initialize the global.
1024 ReplaceUsesOfMallocWithGlobal(U
, GV
);
1025 U
->eraseFromParent();
1027 } else if (GetElementPtrInst
*GEPI
= dyn_cast
<GetElementPtrInst
>(U
)) {
1028 // If this is a "GEP bitcast" and the user is a store to the global, then
1029 // just process it as a bitcast.
1030 if (GEPI
->hasAllZeroIndices() && GEPI
->hasOneUse())
1031 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(GEPI
->user_back()))
1032 if (SI
->getOperand(1) == GV
) {
1033 // Must be bitcast GEP between the malloc and store to initialize
1035 ReplaceUsesOfMallocWithGlobal(GEPI
, GV
);
1036 GEPI
->eraseFromParent();
1041 // Insert a load from the global, and use it instead of the malloc.
1042 Value
*NL
= new LoadInst(GV
, GV
->getName()+".val", InsertPt
);
1043 U
->replaceUsesOfWith(Alloc
, NL
);
1047 /// LoadUsesSimpleEnoughForHeapSRA - Verify that all uses of V (a load, or a phi
1048 /// of a load) are simple enough to perform heap SRA on. This permits GEP's
1049 /// that index through the array and struct field, icmps of null, and PHIs.
1050 static bool LoadUsesSimpleEnoughForHeapSRA(const Value
*V
,
1051 SmallPtrSetImpl
<const PHINode
*> &LoadUsingPHIs
,
1052 SmallPtrSetImpl
<const PHINode
*> &LoadUsingPHIsPerLoad
) {
1053 // We permit two users of the load: setcc comparing against the null
1054 // pointer, and a getelementptr of a specific form.
1055 for (const User
*U
: V
->users()) {
1056 const Instruction
*UI
= cast
<Instruction
>(U
);
1058 // Comparison against null is ok.
1059 if (const ICmpInst
*ICI
= dyn_cast
<ICmpInst
>(UI
)) {
1060 if (!isa
<ConstantPointerNull
>(ICI
->getOperand(1)))
1065 // getelementptr is also ok, but only a simple form.
1066 if (const GetElementPtrInst
*GEPI
= dyn_cast
<GetElementPtrInst
>(UI
)) {
1067 // Must index into the array and into the struct.
1068 if (GEPI
->getNumOperands() < 3)
1071 // Otherwise the GEP is ok.
1075 if (const PHINode
*PN
= dyn_cast
<PHINode
>(UI
)) {
1076 if (!LoadUsingPHIsPerLoad
.insert(PN
).second
)
1077 // This means some phi nodes are dependent on each other.
1078 // Avoid infinite looping!
1080 if (!LoadUsingPHIs
.insert(PN
).second
)
1081 // If we have already analyzed this PHI, then it is safe.
1084 // Make sure all uses of the PHI are simple enough to transform.
1085 if (!LoadUsesSimpleEnoughForHeapSRA(PN
,
1086 LoadUsingPHIs
, LoadUsingPHIsPerLoad
))
1092 // Otherwise we don't know what this is, not ok.
1100 /// AllGlobalLoadUsesSimpleEnoughForHeapSRA - If all users of values loaded from
1101 /// GV are simple enough to perform HeapSRA, return true.
1102 static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(const GlobalVariable
*GV
,
1103 Instruction
*StoredVal
) {
1104 SmallPtrSet
<const PHINode
*, 32> LoadUsingPHIs
;
1105 SmallPtrSet
<const PHINode
*, 32> LoadUsingPHIsPerLoad
;
1106 for (const User
*U
: GV
->users())
1107 if (const LoadInst
*LI
= dyn_cast
<LoadInst
>(U
)) {
1108 if (!LoadUsesSimpleEnoughForHeapSRA(LI
, LoadUsingPHIs
,
1109 LoadUsingPHIsPerLoad
))
1111 LoadUsingPHIsPerLoad
.clear();
1114 // If we reach here, we know that all uses of the loads and transitive uses
1115 // (through PHI nodes) are simple enough to transform. However, we don't know
1116 // that all inputs the to the PHI nodes are in the same equivalence sets.
1117 // Check to verify that all operands of the PHIs are either PHIS that can be
1118 // transformed, loads from GV, or MI itself.
1119 for (const PHINode
*PN
: LoadUsingPHIs
) {
1120 for (unsigned op
= 0, e
= PN
->getNumIncomingValues(); op
!= e
; ++op
) {
1121 Value
*InVal
= PN
->getIncomingValue(op
);
1123 // PHI of the stored value itself is ok.
1124 if (InVal
== StoredVal
) continue;
1126 if (const PHINode
*InPN
= dyn_cast
<PHINode
>(InVal
)) {
1127 // One of the PHIs in our set is (optimistically) ok.
1128 if (LoadUsingPHIs
.count(InPN
))
1133 // Load from GV is ok.
1134 if (const LoadInst
*LI
= dyn_cast
<LoadInst
>(InVal
))
1135 if (LI
->getOperand(0) == GV
)
1140 // Anything else is rejected.
1148 static Value
*GetHeapSROAValue(Value
*V
, unsigned FieldNo
,
1149 DenseMap
<Value
*, std::vector
<Value
*> > &InsertedScalarizedValues
,
1150 std::vector
<std::pair
<PHINode
*, unsigned> > &PHIsToRewrite
) {
1151 std::vector
<Value
*> &FieldVals
= InsertedScalarizedValues
[V
];
1153 if (FieldNo
>= FieldVals
.size())
1154 FieldVals
.resize(FieldNo
+1);
1156 // If we already have this value, just reuse the previously scalarized
1158 if (Value
*FieldVal
= FieldVals
[FieldNo
])
1161 // Depending on what instruction this is, we have several cases.
1163 if (LoadInst
*LI
= dyn_cast
<LoadInst
>(V
)) {
1164 // This is a scalarized version of the load from the global. Just create
1165 // a new Load of the scalarized global.
1166 Result
= new LoadInst(GetHeapSROAValue(LI
->getOperand(0), FieldNo
,
1167 InsertedScalarizedValues
,
1169 LI
->getName()+".f"+Twine(FieldNo
), LI
);
1170 } else if (PHINode
*PN
= dyn_cast
<PHINode
>(V
)) {
1171 // PN's type is pointer to struct. Make a new PHI of pointer to struct
1174 PointerType
*PTy
= cast
<PointerType
>(PN
->getType());
1175 StructType
*ST
= cast
<StructType
>(PTy
->getElementType());
1177 unsigned AS
= PTy
->getAddressSpace();
1179 PHINode::Create(PointerType::get(ST
->getElementType(FieldNo
), AS
),
1180 PN
->getNumIncomingValues(),
1181 PN
->getName()+".f"+Twine(FieldNo
), PN
);
1183 PHIsToRewrite
.push_back(std::make_pair(PN
, FieldNo
));
1185 llvm_unreachable("Unknown usable value");
1188 return FieldVals
[FieldNo
] = Result
;
1191 /// RewriteHeapSROALoadUser - Given a load instruction and a value derived from
1192 /// the load, rewrite the derived value to use the HeapSRoA'd load.
1193 static 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)));
1199 // If we have a setcc of the loaded pointer, we can use a setcc of any
1201 Value
*NPtr
= GetHeapSROAValue(SCI
->getOperand(0), 0,
1202 InsertedScalarizedValues
, PHIsToRewrite
);
1204 Value
*New
= new ICmpInst(SCI
, SCI
->getPredicate(), NPtr
,
1205 Constant::getNullValue(NPtr
->getType()),
1207 SCI
->replaceAllUsesWith(New
);
1208 SCI
->eraseFromParent();
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))
1215 && "Unexpected GEPI!");
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
);
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());
1227 Value
*NGEPI
= GetElementPtrInst::Create(NewPtr
, GEPIdx
,
1228 GEPI
->getName(), GEPI
);
1229 GEPI
->replaceAllUsesWith(NGEPI
);
1230 GEPI
->eraseFromParent();
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
1240 PHINode
*PN
= cast
<PHINode
>(LoadUser
);
1241 if (!InsertedScalarizedValues
.insert(std::make_pair(PN
,
1242 std::vector
<Value
*>())).second
)
1245 // If this is the first time we've seen this PHI, recursively process all
1247 for (auto UI
= PN
->user_begin(), E
= PN
->user_end(); UI
!= E
;) {
1248 Instruction
*User
= cast
<Instruction
>(*UI
++);
1249 RewriteHeapSROALoadUser(User
, InsertedScalarizedValues
, PHIsToRewrite
);
1253 /// RewriteUsesOfLoadForHeapSRoA - We are performing Heap SRoA on a global. Ptr
1254 /// is a value loaded from the global. Eliminate all uses of Ptr, making them
1255 /// use FieldGlobals instead. All uses of loaded values satisfy
1256 /// AllGlobalLoadUsesSimpleEnoughForHeapSRA.
1257 static void RewriteUsesOfLoadForHeapSRoA(LoadInst
*Load
,
1258 DenseMap
<Value
*, std::vector
<Value
*> > &InsertedScalarizedValues
,
1259 std::vector
<std::pair
<PHINode
*, unsigned> > &PHIsToRewrite
) {
1260 for (auto UI
= Load
->user_begin(), E
= Load
->user_end(); UI
!= E
;) {
1261 Instruction
*User
= cast
<Instruction
>(*UI
++);
1262 RewriteHeapSROALoadUser(User
, InsertedScalarizedValues
, PHIsToRewrite
);
1265 if (Load
->use_empty()) {
1266 Load
->eraseFromParent();
1267 InsertedScalarizedValues
.erase(Load
);
1271 /// PerformHeapAllocSRoA - CI is an allocation of an array of structures. Break
1272 /// it up into multiple allocations of arrays of the fields.
1273 static GlobalVariable
*PerformHeapAllocSRoA(GlobalVariable
*GV
, CallInst
*CI
,
1274 Value
*NElems
, const DataLayout
*DL
,
1275 const TargetLibraryInfo
*TLI
) {
1276 DEBUG(dbgs() << "SROA HEAP ALLOC: " << *GV
<< " MALLOC = " << *CI
<< '\n');
1277 Type
*MAT
= getMallocAllocatedType(CI
, TLI
);
1278 StructType
*STy
= cast
<StructType
>(MAT
);
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
1284 ReplaceUsesOfMallocWithGlobal(CI
, GV
);
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
;
1291 unsigned AS
= GV
->getType()->getPointerAddressSpace();
1292 for (unsigned FieldNo
= 0, e
= STy
->getNumElements(); FieldNo
!= e
;++FieldNo
){
1293 Type
*FieldTy
= STy
->getElementType(FieldNo
);
1294 PointerType
*PFieldTy
= PointerType::get(FieldTy
, AS
);
1296 GlobalVariable
*NGV
=
1297 new GlobalVariable(*GV
->getParent(),
1298 PFieldTy
, false, GlobalValue::InternalLinkage
,
1299 Constant::getNullValue(PFieldTy
),
1300 GV
->getName() + ".f" + Twine(FieldNo
), GV
,
1301 GV
->getThreadLocalMode());
1302 FieldGlobals
.push_back(NGV
);
1304 unsigned TypeSize
= DL
->getTypeAllocSize(FieldTy
);
1305 if (StructType
*ST
= dyn_cast
<StructType
>(FieldTy
))
1306 TypeSize
= DL
->getStructLayout(ST
)->getSizeInBytes();
1307 Type
*IntPtrTy
= DL
->getIntPtrType(CI
->getType());
1308 Value
*NMI
= CallInst::CreateMalloc(CI
, IntPtrTy
, FieldTy
,
1309 ConstantInt::get(IntPtrTy
, TypeSize
),
1311 CI
->getName() + ".f" + Twine(FieldNo
));
1312 FieldMallocs
.push_back(NMI
);
1313 new StoreInst(NMI
, NGV
, CI
);
1316 // The tricky aspect of this transformation is handling the case when malloc
1317 // fails. In the original code, malloc failing would set the result pointer
1318 // of malloc to null. In this case, some mallocs could succeed and others
1319 // could fail. As such, we emit code that looks like this:
1320 // F0 = malloc(field0)
1321 // F1 = malloc(field1)
1322 // F2 = malloc(field2)
1323 // if (F0 == 0 || F1 == 0 || F2 == 0) {
1324 // if (F0) { free(F0); F0 = 0; }
1325 // if (F1) { free(F1); F1 = 0; }
1326 // if (F2) { free(F2); F2 = 0; }
1328 // The malloc can also fail if its argument is too large.
1329 Constant
*ConstantZero
= ConstantInt::get(CI
->getArgOperand(0)->getType(), 0);
1330 Value
*RunningOr
= new ICmpInst(CI
, ICmpInst::ICMP_SLT
, CI
->getArgOperand(0),
1331 ConstantZero
, "isneg");
1332 for (unsigned i
= 0, e
= FieldMallocs
.size(); i
!= e
; ++i
) {
1333 Value
*Cond
= new ICmpInst(CI
, ICmpInst::ICMP_EQ
, FieldMallocs
[i
],
1334 Constant::getNullValue(FieldMallocs
[i
]->getType()),
1336 RunningOr
= BinaryOperator::CreateOr(RunningOr
, Cond
, "tmp", CI
);
1339 // Split the basic block at the old malloc.
1340 BasicBlock
*OrigBB
= CI
->getParent();
1341 BasicBlock
*ContBB
= OrigBB
->splitBasicBlock(CI
, "malloc_cont");
1343 // Create the block to check the first condition. Put all these blocks at the
1344 // end of the function as they are unlikely to be executed.
1345 BasicBlock
*NullPtrBlock
= BasicBlock::Create(OrigBB
->getContext(),
1347 OrigBB
->getParent());
1349 // Remove the uncond branch from OrigBB to ContBB, turning it into a cond
1350 // branch on RunningOr.
1351 OrigBB
->getTerminator()->eraseFromParent();
1352 BranchInst::Create(NullPtrBlock
, ContBB
, RunningOr
, OrigBB
);
1354 // Within the NullPtrBlock, we need to emit a comparison and branch for each
1355 // pointer, because some may be null while others are not.
1356 for (unsigned i
= 0, e
= FieldGlobals
.size(); i
!= e
; ++i
) {
1357 Value
*GVVal
= new LoadInst(FieldGlobals
[i
], "tmp", NullPtrBlock
);
1358 Value
*Cmp
= new ICmpInst(*NullPtrBlock
, ICmpInst::ICMP_NE
, GVVal
,
1359 Constant::getNullValue(GVVal
->getType()));
1360 BasicBlock
*FreeBlock
= BasicBlock::Create(Cmp
->getContext(), "free_it",
1361 OrigBB
->getParent());
1362 BasicBlock
*NextBlock
= BasicBlock::Create(Cmp
->getContext(), "next",
1363 OrigBB
->getParent());
1364 Instruction
*BI
= BranchInst::Create(FreeBlock
, NextBlock
,
1367 // Fill in FreeBlock.
1368 CallInst::CreateFree(GVVal
, BI
);
1369 new StoreInst(Constant::getNullValue(GVVal
->getType()), FieldGlobals
[i
],
1371 BranchInst::Create(NextBlock
, FreeBlock
);
1373 NullPtrBlock
= NextBlock
;
1376 BranchInst::Create(ContBB
, NullPtrBlock
);
1378 // CI is no longer needed, remove it.
1379 CI
->eraseFromParent();
1381 /// InsertedScalarizedLoads - As we process loads, if we can't immediately
1382 /// update all uses of the load, keep track of what scalarized loads are
1383 /// inserted for a given load.
1384 DenseMap
<Value
*, std::vector
<Value
*> > InsertedScalarizedValues
;
1385 InsertedScalarizedValues
[GV
] = FieldGlobals
;
1387 std::vector
<std::pair
<PHINode
*, unsigned> > PHIsToRewrite
;
1389 // Okay, the malloc site is completely handled. All of the uses of GV are now
1390 // loads, and all uses of those loads are simple. Rewrite them to use loads
1391 // of the per-field globals instead.
1392 for (auto UI
= GV
->user_begin(), E
= GV
->user_end(); UI
!= E
;) {
1393 Instruction
*User
= cast
<Instruction
>(*UI
++);
1395 if (LoadInst
*LI
= dyn_cast
<LoadInst
>(User
)) {
1396 RewriteUsesOfLoadForHeapSRoA(LI
, InsertedScalarizedValues
, PHIsToRewrite
);
1400 // Must be a store of null.
1401 StoreInst
*SI
= cast
<StoreInst
>(User
);
1402 assert(isa
<ConstantPointerNull
>(SI
->getOperand(0)) &&
1403 "Unexpected heap-sra user!");
1405 // Insert a store of null into each global.
1406 for (unsigned i
= 0, e
= FieldGlobals
.size(); i
!= e
; ++i
) {
1407 PointerType
*PT
= cast
<PointerType
>(FieldGlobals
[i
]->getType());
1408 Constant
*Null
= Constant::getNullValue(PT
->getElementType());
1409 new StoreInst(Null
, FieldGlobals
[i
], SI
);
1411 // Erase the original store.
1412 SI
->eraseFromParent();
1415 // While we have PHIs that are interesting to rewrite, do it.
1416 while (!PHIsToRewrite
.empty()) {
1417 PHINode
*PN
= PHIsToRewrite
.back().first
;
1418 unsigned FieldNo
= PHIsToRewrite
.back().second
;
1419 PHIsToRewrite
.pop_back();
1420 PHINode
*FieldPN
= cast
<PHINode
>(InsertedScalarizedValues
[PN
][FieldNo
]);
1421 assert(FieldPN
->getNumIncomingValues() == 0 &&"Already processed this phi");
1423 // Add all the incoming values. This can materialize more phis.
1424 for (unsigned i
= 0, e
= PN
->getNumIncomingValues(); i
!= e
; ++i
) {
1425 Value
*InVal
= PN
->getIncomingValue(i
);
1426 InVal
= GetHeapSROAValue(InVal
, FieldNo
, InsertedScalarizedValues
,
1428 FieldPN
->addIncoming(InVal
, PN
->getIncomingBlock(i
));
1432 // Drop all inter-phi links and any loads that made it this far.
1433 for (DenseMap
<Value
*, std::vector
<Value
*> >::iterator
1434 I
= InsertedScalarizedValues
.begin(), E
= InsertedScalarizedValues
.end();
1436 if (PHINode
*PN
= dyn_cast
<PHINode
>(I
->first
))
1437 PN
->dropAllReferences();
1438 else if (LoadInst
*LI
= dyn_cast
<LoadInst
>(I
->first
))
1439 LI
->dropAllReferences();
1442 // Delete all the phis and loads now that inter-references are dead.
1443 for (DenseMap
<Value
*, std::vector
<Value
*> >::iterator
1444 I
= InsertedScalarizedValues
.begin(), E
= InsertedScalarizedValues
.end();
1446 if (PHINode
*PN
= dyn_cast
<PHINode
>(I
->first
))
1447 PN
->eraseFromParent();
1448 else if (LoadInst
*LI
= dyn_cast
<LoadInst
>(I
->first
))
1449 LI
->eraseFromParent();
1452 // The old global is now dead, remove it.
1453 GV
->eraseFromParent();
1456 return cast
<GlobalVariable
>(FieldGlobals
[0]);
1459 /// TryToOptimizeStoreOfMallocToGlobal - This function is called when we see a
1460 /// pointer global variable with a single value stored it that is a malloc or
1462 static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable
*GV
,
1465 AtomicOrdering Ordering
,
1466 Module::global_iterator
&GVI
,
1467 const DataLayout
*DL
,
1468 TargetLibraryInfo
*TLI
) {
1472 // If this is a malloc of an abstract type, don't touch it.
1473 if (!AllocTy
->isSized())
1476 // We can't optimize this global unless all uses of it are *known* to be
1477 // of the malloc value, not of the null initializer value (consider a use
1478 // that compares the global's value against zero to see if the malloc has
1479 // been reached). To do this, we check to see if all uses of the global
1480 // would trap if the global were null: this proves that they must all
1481 // happen after the malloc.
1482 if (!AllUsesOfLoadedValueWillTrapIfNull(GV
))
1485 // We can't optimize this if the malloc itself is used in a complex way,
1486 // for example, being stored into multiple globals. This allows the
1487 // malloc to be stored into the specified global, loaded icmp'd, and
1488 // GEP'd. These are all things we could transform to using the global
1490 SmallPtrSet
<const PHINode
*, 8> PHIs
;
1491 if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(CI
, GV
, PHIs
))
1494 // If we have a global that is only initialized with a fixed size malloc,
1495 // transform the program to use global memory instead of malloc'd memory.
1496 // This eliminates dynamic allocation, avoids an indirection accessing the
1497 // data, and exposes the resultant global to further GlobalOpt.
1498 // We cannot optimize the malloc if we cannot determine malloc array size.
1499 Value
*NElems
= getMallocArraySize(CI
, DL
, TLI
, true);
1503 if (ConstantInt
*NElements
= dyn_cast
<ConstantInt
>(NElems
))
1504 // Restrict this transformation to only working on small allocations
1505 // (2048 bytes currently), as we don't want to introduce a 16M global or
1507 if (NElements
->getZExtValue() * DL
->getTypeAllocSize(AllocTy
) < 2048) {
1508 GVI
= OptimizeGlobalAddressOfMalloc(GV
, CI
, AllocTy
, NElements
, DL
, TLI
);
1512 // If the allocation is an array of structures, consider transforming this
1513 // into multiple malloc'd arrays, one for each field. This is basically
1514 // SRoA for malloc'd memory.
1516 if (Ordering
!= NotAtomic
)
1519 // If this is an allocation of a fixed size array of structs, analyze as a
1520 // variable size array. malloc [100 x struct],1 -> malloc struct, 100
1521 if (NElems
== ConstantInt::get(CI
->getArgOperand(0)->getType(), 1))
1522 if (ArrayType
*AT
= dyn_cast
<ArrayType
>(AllocTy
))
1523 AllocTy
= AT
->getElementType();
1525 StructType
*AllocSTy
= dyn_cast
<StructType
>(AllocTy
);
1529 // This the structure has an unreasonable number of fields, leave it
1531 if (AllocSTy
->getNumElements() <= 16 && AllocSTy
->getNumElements() != 0 &&
1532 AllGlobalLoadUsesSimpleEnoughForHeapSRA(GV
, CI
)) {
1534 // If this is a fixed size array, transform the Malloc to be an alloc of
1535 // structs. malloc [100 x struct],1 -> malloc struct, 100
1536 if (ArrayType
*AT
= dyn_cast
<ArrayType
>(getMallocAllocatedType(CI
, TLI
))) {
1537 Type
*IntPtrTy
= DL
->getIntPtrType(CI
->getType());
1538 unsigned TypeSize
= DL
->getStructLayout(AllocSTy
)->getSizeInBytes();
1539 Value
*AllocSize
= ConstantInt::get(IntPtrTy
, TypeSize
);
1540 Value
*NumElements
= ConstantInt::get(IntPtrTy
, AT
->getNumElements());
1541 Instruction
*Malloc
= CallInst::CreateMalloc(CI
, IntPtrTy
, AllocSTy
,
1542 AllocSize
, NumElements
,
1543 nullptr, CI
->getName());
1544 Instruction
*Cast
= new BitCastInst(Malloc
, CI
->getType(), "tmp", CI
);
1545 CI
->replaceAllUsesWith(Cast
);
1546 CI
->eraseFromParent();
1547 if (BitCastInst
*BCI
= dyn_cast
<BitCastInst
>(Malloc
))
1548 CI
= cast
<CallInst
>(BCI
->getOperand(0));
1550 CI
= cast
<CallInst
>(Malloc
);
1553 GVI
= PerformHeapAllocSRoA(GV
, CI
, getMallocArraySize(CI
, DL
, TLI
, true),
1561 // OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge
1562 // that only one value (besides its initializer) is ever stored to the global.
1563 static bool OptimizeOnceStoredGlobal(GlobalVariable
*GV
, Value
*StoredOnceVal
,
1564 AtomicOrdering Ordering
,
1565 Module::global_iterator
&GVI
,
1566 const DataLayout
*DL
,
1567 TargetLibraryInfo
*TLI
) {
1568 // Ignore no-op GEPs and bitcasts.
1569 StoredOnceVal
= StoredOnceVal
->stripPointerCasts();
1571 // If we are dealing with a pointer global that is initialized to null and
1572 // only has one (non-null) value stored into it, then we can optimize any
1573 // users of the loaded value (often calls and loads) that would trap if the
1575 if (GV
->getInitializer()->getType()->isPointerTy() &&
1576 GV
->getInitializer()->isNullValue()) {
1577 if (Constant
*SOVC
= dyn_cast
<Constant
>(StoredOnceVal
)) {
1578 if (GV
->getInitializer()->getType() != SOVC
->getType())
1579 SOVC
= ConstantExpr::getBitCast(SOVC
, GV
->getInitializer()->getType());
1581 // Optimize away any trapping uses of the loaded value.
1582 if (OptimizeAwayTrappingUsesOfLoads(GV
, SOVC
, DL
, TLI
))
1584 } else if (CallInst
*CI
= extractMallocCall(StoredOnceVal
, TLI
)) {
1585 Type
*MallocType
= getMallocAllocatedType(CI
, TLI
);
1587 TryToOptimizeStoreOfMallocToGlobal(GV
, CI
, MallocType
, Ordering
, GVI
,
1596 /// TryToShrinkGlobalToBoolean - At this point, we have learned that the only
1597 /// two values ever stored into GV are its initializer and OtherVal. See if we
1598 /// can shrink the global into a boolean and select between the two values
1599 /// whenever it is used. This exposes the values to other scalar optimizations.
1600 static bool TryToShrinkGlobalToBoolean(GlobalVariable
*GV
, Constant
*OtherVal
) {
1601 Type
*GVElType
= GV
->getType()->getElementType();
1603 // If GVElType is already i1, it is already shrunk. If the type of the GV is
1604 // an FP value, pointer or vector, don't do this optimization because a select
1605 // between them is very expensive and unlikely to lead to later
1606 // simplification. In these cases, we typically end up with "cond ? v1 : v2"
1607 // where v1 and v2 both require constant pool loads, a big loss.
1608 if (GVElType
== Type::getInt1Ty(GV
->getContext()) ||
1609 GVElType
->isFloatingPointTy() ||
1610 GVElType
->isPointerTy() || GVElType
->isVectorTy())
1613 // Walk the use list of the global seeing if all the uses are load or store.
1614 // If there is anything else, bail out.
1615 for (User
*U
: GV
->users())
1616 if (!isa
<LoadInst
>(U
) && !isa
<StoreInst
>(U
))
1619 DEBUG(dbgs() << " *** SHRINKING TO BOOL: " << *GV
);
1621 // Create the new global, initializing it to false.
1622 GlobalVariable
*NewGV
= new GlobalVariable(Type::getInt1Ty(GV
->getContext()),
1624 GlobalValue::InternalLinkage
,
1625 ConstantInt::getFalse(GV
->getContext()),
1627 GV
->getThreadLocalMode(),
1628 GV
->getType()->getAddressSpace());
1629 GV
->getParent()->getGlobalList().insert(GV
, NewGV
);
1631 Constant
*InitVal
= GV
->getInitializer();
1632 assert(InitVal
->getType() != Type::getInt1Ty(GV
->getContext()) &&
1633 "No reason to shrink to bool!");
1635 // If initialized to zero and storing one into the global, we can use a cast
1636 // instead of a select to synthesize the desired value.
1637 bool IsOneZero
= false;
1638 if (ConstantInt
*CI
= dyn_cast
<ConstantInt
>(OtherVal
))
1639 IsOneZero
= InitVal
->isNullValue() && CI
->isOne();
1641 while (!GV
->use_empty()) {
1642 Instruction
*UI
= cast
<Instruction
>(GV
->user_back());
1643 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(UI
)) {
1644 // Change the store into a boolean store.
1645 bool StoringOther
= SI
->getOperand(0) == OtherVal
;
1646 // Only do this if we weren't storing a loaded value.
1648 if (StoringOther
|| SI
->getOperand(0) == InitVal
) {
1649 StoreVal
= ConstantInt::get(Type::getInt1Ty(GV
->getContext()),
1652 // Otherwise, we are storing a previously loaded copy. To do this,
1653 // change the copy from copying the original value to just copying the
1655 Instruction
*StoredVal
= cast
<Instruction
>(SI
->getOperand(0));
1657 // If we've already replaced the input, StoredVal will be a cast or
1658 // select instruction. If not, it will be a load of the original
1660 if (LoadInst
*LI
= dyn_cast
<LoadInst
>(StoredVal
)) {
1661 assert(LI
->getOperand(0) == GV
&& "Not a copy!");
1662 // Insert a new load, to preserve the saved value.
1663 StoreVal
= new LoadInst(NewGV
, LI
->getName()+".b", false, 0,
1664 LI
->getOrdering(), LI
->getSynchScope(), LI
);
1666 assert((isa
<CastInst
>(StoredVal
) || isa
<SelectInst
>(StoredVal
)) &&
1667 "This is not a form that we understand!");
1668 StoreVal
= StoredVal
->getOperand(0);
1669 assert(isa
<LoadInst
>(StoreVal
) && "Not a load of NewGV!");
1672 new StoreInst(StoreVal
, NewGV
, false, 0,
1673 SI
->getOrdering(), SI
->getSynchScope(), SI
);
1675 // Change the load into a load of bool then a select.
1676 LoadInst
*LI
= cast
<LoadInst
>(UI
);
1677 LoadInst
*NLI
= new LoadInst(NewGV
, LI
->getName()+".b", false, 0,
1678 LI
->getOrdering(), LI
->getSynchScope(), LI
);
1681 NSI
= new ZExtInst(NLI
, LI
->getType(), "", LI
);
1683 NSI
= SelectInst::Create(NLI
, OtherVal
, InitVal
, "", LI
);
1685 LI
->replaceAllUsesWith(NSI
);
1687 UI
->eraseFromParent();
1690 // Retain the name of the old global variable. People who are debugging their
1691 // programs may expect these variables to be named the same.
1692 NewGV
->takeName(GV
);
1693 GV
->eraseFromParent();
1698 /// ProcessGlobal - Analyze the specified global variable and optimize it if
1699 /// possible. If we make a change, return true.
1700 bool GlobalOpt::ProcessGlobal(GlobalVariable
*GV
,
1701 Module::global_iterator
&GVI
) {
1702 // Do more involved optimizations if the global is internal.
1703 GV
->removeDeadConstantUsers();
1705 if (GV
->use_empty()) {
1706 DEBUG(dbgs() << "GLOBAL DEAD: " << *GV
);
1707 GV
->eraseFromParent();
1712 if (!GV
->hasLocalLinkage())
1717 if (GlobalStatus::analyzeGlobal(GV
, GS
))
1720 if (!GS
.IsCompared
&& !GV
->hasUnnamedAddr()) {
1721 GV
->setUnnamedAddr(true);
1725 if (GV
->isConstant() || !GV
->hasInitializer())
1728 return ProcessInternalGlobal(GV
, GVI
, GS
);
1731 /// ProcessInternalGlobal - Analyze the specified global variable and optimize
1732 /// it if possible. If we make a change, return true.
1733 bool GlobalOpt::ProcessInternalGlobal(GlobalVariable
*GV
,
1734 Module::global_iterator
&GVI
,
1735 const GlobalStatus
&GS
) {
1736 // If this is a first class global and has only one accessing function
1737 // and this function is main (which we know is not recursive), we replace
1738 // the global with a local alloca in this function.
1740 // NOTE: It doesn't make sense to promote non-single-value types since we
1741 // are just replacing static memory to stack memory.
1743 // If the global is in different address space, don't bring it to stack.
1744 if (!GS
.HasMultipleAccessingFunctions
&&
1745 GS
.AccessingFunction
&& !GS
.HasNonInstructionUser
&&
1746 GV
->getType()->getElementType()->isSingleValueType() &&
1747 GS
.AccessingFunction
->getName() == "main" &&
1748 GS
.AccessingFunction
->hasExternalLinkage() &&
1749 GV
->getType()->getAddressSpace() == 0) {
1750 DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV
);
1751 Instruction
&FirstI
= const_cast<Instruction
&>(*GS
.AccessingFunction
1752 ->getEntryBlock().begin());
1753 Type
*ElemTy
= GV
->getType()->getElementType();
1754 // FIXME: Pass Global's alignment when globals have alignment
1755 AllocaInst
*Alloca
= new AllocaInst(ElemTy
, nullptr,
1756 GV
->getName(), &FirstI
);
1757 if (!isa
<UndefValue
>(GV
->getInitializer()))
1758 new StoreInst(GV
->getInitializer(), Alloca
, &FirstI
);
1760 GV
->replaceAllUsesWith(Alloca
);
1761 GV
->eraseFromParent();
1766 // If the global is never loaded (but may be stored to), it is dead.
1769 DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV
);
1772 if (isLeakCheckerRoot(GV
)) {
1773 // Delete any constant stores to the global.
1774 Changed
= CleanupPointerRootUsers(GV
, TLI
);
1776 // Delete any stores we can find to the global. We may not be able to
1777 // make it completely dead though.
1778 Changed
= CleanupConstantGlobalUsers(GV
, GV
->getInitializer(), DL
, TLI
);
1781 // If the global is dead now, delete it.
1782 if (GV
->use_empty()) {
1783 GV
->eraseFromParent();
1789 } else if (GS
.StoredType
<= GlobalStatus::InitializerStored
) {
1790 DEBUG(dbgs() << "MARKING CONSTANT: " << *GV
<< "\n");
1791 GV
->setConstant(true);
1793 // Clean up any obviously simplifiable users now.
1794 CleanupConstantGlobalUsers(GV
, GV
->getInitializer(), DL
, TLI
);
1796 // If the global is dead now, just nuke it.
1797 if (GV
->use_empty()) {
1798 DEBUG(dbgs() << " *** Marking constant allowed us to simplify "
1799 << "all users and delete global!\n");
1800 GV
->eraseFromParent();
1806 } else if (!GV
->getInitializer()->getType()->isSingleValueType()) {
1807 if (DataLayoutPass
*DLP
= getAnalysisIfAvailable
<DataLayoutPass
>()) {
1808 const DataLayout
&DL
= DLP
->getDataLayout();
1809 if (GlobalVariable
*FirstNewGV
= SRAGlobal(GV
, DL
)) {
1810 GVI
= FirstNewGV
; // Don't skip the newly produced globals!
1814 } else if (GS
.StoredType
== GlobalStatus::StoredOnce
) {
1815 // If the initial value for the global was an undef value, and if only
1816 // one other value was stored into it, we can just change the
1817 // initializer to be the stored value, then delete all stores to the
1818 // global. This allows us to mark it constant.
1819 if (Constant
*SOVConstant
= dyn_cast
<Constant
>(GS
.StoredOnceValue
))
1820 if (isa
<UndefValue
>(GV
->getInitializer())) {
1821 // Change the initial value here.
1822 GV
->setInitializer(SOVConstant
);
1824 // Clean up any obviously simplifiable users now.
1825 CleanupConstantGlobalUsers(GV
, GV
->getInitializer(), DL
, TLI
);
1827 if (GV
->use_empty()) {
1828 DEBUG(dbgs() << " *** Substituting initializer allowed us to "
1829 << "simplify all users and delete global!\n");
1830 GV
->eraseFromParent();
1839 // Try to optimize globals based on the knowledge that only one value
1840 // (besides its initializer) is ever stored to the global.
1841 if (OptimizeOnceStoredGlobal(GV
, GS
.StoredOnceValue
, GS
.Ordering
, GVI
,
1845 // Otherwise, if the global was not a boolean, we can shrink it to be a
1847 if (Constant
*SOVConstant
= dyn_cast
<Constant
>(GS
.StoredOnceValue
)) {
1848 if (GS
.Ordering
== NotAtomic
) {
1849 if (TryToShrinkGlobalToBoolean(GV
, SOVConstant
)) {
1860 /// ChangeCalleesToFastCall - Walk all of the direct calls of the specified
1861 /// function, changing them to FastCC.
1862 static void ChangeCalleesToFastCall(Function
*F
) {
1863 for (User
*U
: F
->users()) {
1864 if (isa
<BlockAddress
>(U
))
1866 CallSite
CS(cast
<Instruction
>(U
));
1867 CS
.setCallingConv(CallingConv::Fast
);
1871 static AttributeSet
StripNest(LLVMContext
&C
, const AttributeSet
&Attrs
) {
1872 for (unsigned i
= 0, e
= Attrs
.getNumSlots(); i
!= e
; ++i
) {
1873 unsigned Index
= Attrs
.getSlotIndex(i
);
1874 if (!Attrs
.getSlotAttributes(i
).hasAttribute(Index
, Attribute::Nest
))
1877 // There can be only one.
1878 return Attrs
.removeAttribute(C
, Index
, Attribute::Nest
);
1884 static void RemoveNestAttribute(Function
*F
) {
1885 F
->setAttributes(StripNest(F
->getContext(), F
->getAttributes()));
1886 for (User
*U
: F
->users()) {
1887 if (isa
<BlockAddress
>(U
))
1889 CallSite
CS(cast
<Instruction
>(U
));
1890 CS
.setAttributes(StripNest(F
->getContext(), CS
.getAttributes()));
1894 /// Return true if this is a calling convention that we'd like to change. The
1895 /// idea here is that we don't want to mess with the convention if the user
1896 /// explicitly requested something with performance implications like coldcc,
1897 /// GHC, or anyregcc.
1898 static bool isProfitableToMakeFastCC(Function
*F
) {
1899 CallingConv::ID CC
= F
->getCallingConv();
1900 // FIXME: Is it worth transforming x86_stdcallcc and x86_fastcallcc?
1901 return CC
== CallingConv::C
|| CC
== CallingConv::X86_ThisCall
;
1904 bool GlobalOpt::OptimizeFunctions(Module
&M
) {
1905 bool Changed
= false;
1906 // Optimize functions.
1907 for (Module::iterator FI
= M
.begin(), E
= M
.end(); FI
!= E
; ) {
1909 // Functions without names cannot be referenced outside this module.
1910 if (!F
->hasName() && !F
->isDeclaration() && !F
->hasLocalLinkage())
1911 F
->setLinkage(GlobalValue::InternalLinkage
);
1913 const Comdat
*C
= F
->getComdat();
1914 bool inComdat
= C
&& NotDiscardableComdats
.count(C
);
1915 F
->removeDeadConstantUsers();
1916 if ((!inComdat
|| F
->hasLocalLinkage()) && F
->isDefTriviallyDead()) {
1917 F
->eraseFromParent();
1920 } else if (F
->hasLocalLinkage()) {
1921 if (isProfitableToMakeFastCC(F
) && !F
->isVarArg() &&
1922 !F
->hasAddressTaken()) {
1923 // If this function has a calling convention worth changing, is not a
1924 // varargs function, and is only called directly, promote it to use the
1925 // Fast calling convention.
1926 F
->setCallingConv(CallingConv::Fast
);
1927 ChangeCalleesToFastCall(F
);
1932 if (F
->getAttributes().hasAttrSomewhere(Attribute::Nest
) &&
1933 !F
->hasAddressTaken()) {
1934 // The function is not used by a trampoline intrinsic, so it is safe
1935 // to remove the 'nest' attribute.
1936 RemoveNestAttribute(F
);
1945 bool GlobalOpt::OptimizeGlobalVars(Module
&M
) {
1946 bool Changed
= false;
1948 for (Module::global_iterator GVI
= M
.global_begin(), E
= M
.global_end();
1950 GlobalVariable
*GV
= GVI
++;
1951 // Global variables without names cannot be referenced outside this module.
1952 if (!GV
->hasName() && !GV
->isDeclaration() && !GV
->hasLocalLinkage())
1953 GV
->setLinkage(GlobalValue::InternalLinkage
);
1954 // Simplify the initializer.
1955 if (GV
->hasInitializer())
1956 if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(GV
->getInitializer())) {
1957 Constant
*New
= ConstantFoldConstantExpression(CE
, DL
, TLI
);
1958 if (New
&& New
!= CE
)
1959 GV
->setInitializer(New
);
1962 if (GV
->isDiscardableIfUnused()) {
1963 if (const Comdat
*C
= GV
->getComdat())
1964 if (NotDiscardableComdats
.count(C
) && !GV
->hasLocalLinkage())
1966 Changed
|= ProcessGlobal(GV
, GVI
);
1973 isSimpleEnoughValueToCommit(Constant
*C
,
1974 SmallPtrSetImpl
<Constant
*> &SimpleConstants
,
1975 const DataLayout
*DL
);
1978 /// isSimpleEnoughValueToCommit - Return true if the specified constant can be
1979 /// handled by the code generator. We don't want to generate something like:
1980 /// void *X = &X/42;
1981 /// because the code generator doesn't have a relocation that can handle that.
1983 /// This function should be called if C was not found (but just got inserted)
1984 /// in SimpleConstants to avoid having to rescan the same constants all the
1986 static bool isSimpleEnoughValueToCommitHelper(Constant
*C
,
1987 SmallPtrSetImpl
<Constant
*> &SimpleConstants
,
1988 const DataLayout
*DL
) {
1989 // Simple global addresses are supported, do not allow dllimport or
1990 // thread-local globals.
1991 if (auto *GV
= dyn_cast
<GlobalValue
>(C
))
1992 return !GV
->hasDLLImportStorageClass() && !GV
->isThreadLocal();
1994 // Simple integer, undef, constant aggregate zero, etc are all supported.
1995 if (C
->getNumOperands() == 0 || isa
<BlockAddress
>(C
))
1998 // Aggregate values are safe if all their elements are.
1999 if (isa
<ConstantArray
>(C
) || isa
<ConstantStruct
>(C
) ||
2000 isa
<ConstantVector
>(C
)) {
2001 for (unsigned i
= 0, e
= C
->getNumOperands(); i
!= e
; ++i
) {
2002 Constant
*Op
= cast
<Constant
>(C
->getOperand(i
));
2003 if (!isSimpleEnoughValueToCommit(Op
, SimpleConstants
, DL
))
2009 // We don't know exactly what relocations are allowed in constant expressions,
2010 // so we allow &global+constantoffset, which is safe and uniformly supported
2012 ConstantExpr
*CE
= cast
<ConstantExpr
>(C
);
2013 switch (CE
->getOpcode()) {
2014 case Instruction::BitCast
:
2015 // Bitcast is fine if the casted value is fine.
2016 return isSimpleEnoughValueToCommit(CE
->getOperand(0), SimpleConstants
, DL
);
2018 case Instruction::IntToPtr
:
2019 case Instruction::PtrToInt
:
2020 // int <=> ptr is fine if the int type is the same size as the
2022 if (!DL
|| DL
->getTypeSizeInBits(CE
->getType()) !=
2023 DL
->getTypeSizeInBits(CE
->getOperand(0)->getType()))
2025 return isSimpleEnoughValueToCommit(CE
->getOperand(0), SimpleConstants
, DL
);
2027 // GEP is fine if it is simple + constant offset.
2028 case Instruction::GetElementPtr
:
2029 for (unsigned i
= 1, e
= CE
->getNumOperands(); i
!= e
; ++i
)
2030 if (!isa
<ConstantInt
>(CE
->getOperand(i
)))
2032 return isSimpleEnoughValueToCommit(CE
->getOperand(0), SimpleConstants
, DL
);
2034 case Instruction::Add
:
2035 // We allow simple+cst.
2036 if (!isa
<ConstantInt
>(CE
->getOperand(1)))
2038 return isSimpleEnoughValueToCommit(CE
->getOperand(0), SimpleConstants
, DL
);
2044 isSimpleEnoughValueToCommit(Constant
*C
,
2045 SmallPtrSetImpl
<Constant
*> &SimpleConstants
,
2046 const DataLayout
*DL
) {
2047 // If we already checked this constant, we win.
2048 if (!SimpleConstants
.insert(C
).second
)
2050 // Check the constant.
2051 return isSimpleEnoughValueToCommitHelper(C
, SimpleConstants
, DL
);
2055 /// isSimpleEnoughPointerToCommit - Return true if this constant is simple
2056 /// enough for us to understand. In particular, if it is a cast to anything
2057 /// other than from one pointer type to another pointer type, we punt.
2058 /// We basically just support direct accesses to globals and GEP's of
2059 /// globals. This should be kept up to date with CommitValueTo.
2060 static bool isSimpleEnoughPointerToCommit(Constant
*C
) {
2061 // Conservatively, avoid aggregate types. This is because we don't
2062 // want to worry about them partially overlapping other stores.
2063 if (!cast
<PointerType
>(C
->getType())->getElementType()->isSingleValueType())
2066 if (GlobalVariable
*GV
= dyn_cast
<GlobalVariable
>(C
))
2067 // Do not allow weak/*_odr/linkonce linkage or external globals.
2068 return GV
->hasUniqueInitializer();
2070 if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(C
)) {
2071 // Handle a constantexpr gep.
2072 if (CE
->getOpcode() == Instruction::GetElementPtr
&&
2073 isa
<GlobalVariable
>(CE
->getOperand(0)) &&
2074 cast
<GEPOperator
>(CE
)->isInBounds()) {
2075 GlobalVariable
*GV
= cast
<GlobalVariable
>(CE
->getOperand(0));
2076 // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
2077 // external globals.
2078 if (!GV
->hasUniqueInitializer())
2081 // The first index must be zero.
2082 ConstantInt
*CI
= dyn_cast
<ConstantInt
>(*std::next(CE
->op_begin()));
2083 if (!CI
|| !CI
->isZero()) return false;
2085 // The remaining indices must be compile-time known integers within the
2086 // notional bounds of the corresponding static array types.
2087 if (!CE
->isGEPWithNoNotionalOverIndexing())
2090 return ConstantFoldLoadThroughGEPConstantExpr(GV
->getInitializer(), CE
);
2092 // A constantexpr bitcast from a pointer to another pointer is a no-op,
2093 // and we know how to evaluate it by moving the bitcast from the pointer
2094 // operand to the value operand.
2095 } else if (CE
->getOpcode() == Instruction::BitCast
&&
2096 isa
<GlobalVariable
>(CE
->getOperand(0))) {
2097 // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
2098 // external globals.
2099 return cast
<GlobalVariable
>(CE
->getOperand(0))->hasUniqueInitializer();
2106 /// EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global
2107 /// initializer. This returns 'Init' modified to reflect 'Val' stored into it.
2108 /// At this point, the GEP operands of Addr [0, OpNo) have been stepped into.
2109 static Constant
*EvaluateStoreInto(Constant
*Init
, Constant
*Val
,
2110 ConstantExpr
*Addr
, unsigned OpNo
) {
2111 // Base case of the recursion.
2112 if (OpNo
== Addr
->getNumOperands()) {
2113 assert(Val
->getType() == Init
->getType() && "Type mismatch!");
2117 SmallVector
<Constant
*, 32> Elts
;
2118 if (StructType
*STy
= dyn_cast
<StructType
>(Init
->getType())) {
2119 // Break up the constant into its elements.
2120 for (unsigned i
= 0, e
= STy
->getNumElements(); i
!= e
; ++i
)
2121 Elts
.push_back(Init
->getAggregateElement(i
));
2123 // Replace the element that we are supposed to.
2124 ConstantInt
*CU
= cast
<ConstantInt
>(Addr
->getOperand(OpNo
));
2125 unsigned Idx
= CU
->getZExtValue();
2126 assert(Idx
< STy
->getNumElements() && "Struct index out of range!");
2127 Elts
[Idx
] = EvaluateStoreInto(Elts
[Idx
], Val
, Addr
, OpNo
+1);
2129 // Return the modified struct.
2130 return ConstantStruct::get(STy
, Elts
);
2133 ConstantInt
*CI
= cast
<ConstantInt
>(Addr
->getOperand(OpNo
));
2134 SequentialType
*InitTy
= cast
<SequentialType
>(Init
->getType());
2137 if (ArrayType
*ATy
= dyn_cast
<ArrayType
>(InitTy
))
2138 NumElts
= ATy
->getNumElements();
2140 NumElts
= InitTy
->getVectorNumElements();
2142 // Break up the array into elements.
2143 for (uint64_t i
= 0, e
= NumElts
; i
!= e
; ++i
)
2144 Elts
.push_back(Init
->getAggregateElement(i
));
2146 assert(CI
->getZExtValue() < NumElts
);
2147 Elts
[CI
->getZExtValue()] =
2148 EvaluateStoreInto(Elts
[CI
->getZExtValue()], Val
, Addr
, OpNo
+1);
2150 if (Init
->getType()->isArrayTy())
2151 return ConstantArray::get(cast
<ArrayType
>(InitTy
), Elts
);
2152 return ConstantVector::get(Elts
);
2155 /// CommitValueTo - We have decided that Addr (which satisfies the predicate
2156 /// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen.
2157 static void CommitValueTo(Constant
*Val
, Constant
*Addr
) {
2158 if (GlobalVariable
*GV
= dyn_cast
<GlobalVariable
>(Addr
)) {
2159 assert(GV
->hasInitializer());
2160 GV
->setInitializer(Val
);
2164 ConstantExpr
*CE
= cast
<ConstantExpr
>(Addr
);
2165 GlobalVariable
*GV
= cast
<GlobalVariable
>(CE
->getOperand(0));
2166 GV
->setInitializer(EvaluateStoreInto(GV
->getInitializer(), Val
, CE
, 2));
2171 /// Evaluator - This class evaluates LLVM IR, producing the Constant
2172 /// representing each SSA instruction. Changes to global variables are stored
2173 /// in a mapping that can be iterated over after the evaluation is complete.
2174 /// Once an evaluation call fails, the evaluation object should not be reused.
2177 Evaluator(const DataLayout
*DL
, const TargetLibraryInfo
*TLI
)
2178 : DL(DL
), TLI(TLI
) {
2179 ValueStack
.emplace_back();
2183 for (auto &Tmp
: AllocaTmps
)
2184 // If there are still users of the alloca, the program is doing something
2185 // silly, e.g. storing the address of the alloca somewhere and using it
2186 // later. Since this is undefined, we'll just make it be null.
2187 if (!Tmp
->use_empty())
2188 Tmp
->replaceAllUsesWith(Constant::getNullValue(Tmp
->getType()));
2191 /// EvaluateFunction - Evaluate a call to function F, returning true if
2192 /// successful, false if we can't evaluate it. ActualArgs contains the formal
2193 /// arguments for the function.
2194 bool EvaluateFunction(Function
*F
, Constant
*&RetVal
,
2195 const SmallVectorImpl
<Constant
*> &ActualArgs
);
2197 /// EvaluateBlock - Evaluate all instructions in block BB, returning true if
2198 /// successful, false if we can't evaluate it. NewBB returns the next BB that
2199 /// control flows into, or null upon return.
2200 bool EvaluateBlock(BasicBlock::iterator CurInst
, BasicBlock
*&NextBB
);
2202 Constant
*getVal(Value
*V
) {
2203 if (Constant
*CV
= dyn_cast
<Constant
>(V
)) return CV
;
2204 Constant
*R
= ValueStack
.back().lookup(V
);
2205 assert(R
&& "Reference to an uncomputed value!");
2209 void setVal(Value
*V
, Constant
*C
) {
2210 ValueStack
.back()[V
] = C
;
2213 const DenseMap
<Constant
*, Constant
*> &getMutatedMemory() const {
2214 return MutatedMemory
;
2217 const SmallPtrSetImpl
<GlobalVariable
*> &getInvariants() const {
2222 Constant
*ComputeLoadResult(Constant
*P
);
2224 /// ValueStack - As we compute SSA register values, we store their contents
2225 /// here. The back of the deque contains the current function and the stack
2226 /// contains the values in the calling frames.
2227 std::deque
<DenseMap
<Value
*, Constant
*>> ValueStack
;
2229 /// CallStack - This is used to detect recursion. In pathological situations
2230 /// we could hit exponential behavior, but at least there is nothing
2232 SmallVector
<Function
*, 4> CallStack
;
2234 /// MutatedMemory - For each store we execute, we update this map. Loads
2235 /// check this to get the most up-to-date value. If evaluation is successful,
2236 /// this state is committed to the process.
2237 DenseMap
<Constant
*, Constant
*> MutatedMemory
;
2239 /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable
2240 /// to represent its body. This vector is needed so we can delete the
2241 /// temporary globals when we are done.
2242 SmallVector
<std::unique_ptr
<GlobalVariable
>, 32> AllocaTmps
;
2244 /// Invariants - These global variables have been marked invariant by the
2245 /// static constructor.
2246 SmallPtrSet
<GlobalVariable
*, 8> Invariants
;
2248 /// SimpleConstants - These are constants we have checked and know to be
2249 /// simple enough to live in a static initializer of a global.
2250 SmallPtrSet
<Constant
*, 8> SimpleConstants
;
2252 const DataLayout
*DL
;
2253 const TargetLibraryInfo
*TLI
;
2256 } // anonymous namespace
2258 /// ComputeLoadResult - Return the value that would be computed by a load from
2259 /// P after the stores reflected by 'memory' have been performed. If we can't
2260 /// decide, return null.
2261 Constant
*Evaluator::ComputeLoadResult(Constant
*P
) {
2262 // If this memory location has been recently stored, use the stored value: it
2263 // is the most up-to-date.
2264 DenseMap
<Constant
*, Constant
*>::const_iterator I
= MutatedMemory
.find(P
);
2265 if (I
!= MutatedMemory
.end()) return I
->second
;
2268 if (GlobalVariable
*GV
= dyn_cast
<GlobalVariable
>(P
)) {
2269 if (GV
->hasDefinitiveInitializer())
2270 return GV
->getInitializer();
2274 // Handle a constantexpr getelementptr.
2275 if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(P
))
2276 if (CE
->getOpcode() == Instruction::GetElementPtr
&&
2277 isa
<GlobalVariable
>(CE
->getOperand(0))) {
2278 GlobalVariable
*GV
= cast
<GlobalVariable
>(CE
->getOperand(0));
2279 if (GV
->hasDefinitiveInitializer())
2280 return ConstantFoldLoadThroughGEPConstantExpr(GV
->getInitializer(), CE
);
2283 return nullptr; // don't know how to evaluate.
2286 /// EvaluateBlock - Evaluate all instructions in block BB, returning true if
2287 /// successful, false if we can't evaluate it. NewBB returns the next BB that
2288 /// control flows into, or null upon return.
2289 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst
,
2290 BasicBlock
*&NextBB
) {
2291 // This is the main evaluation loop.
2293 Constant
*InstResult
= nullptr;
2295 DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst
<< "\n");
2297 if (StoreInst
*SI
= dyn_cast
<StoreInst
>(CurInst
)) {
2298 if (!SI
->isSimple()) {
2299 DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
2300 return false; // no volatile/atomic accesses.
2302 Constant
*Ptr
= getVal(SI
->getOperand(1));
2303 if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(Ptr
)) {
2304 DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr
);
2305 Ptr
= ConstantFoldConstantExpression(CE
, DL
, TLI
);
2306 DEBUG(dbgs() << "; To: " << *Ptr
<< "\n");
2308 if (!isSimpleEnoughPointerToCommit(Ptr
)) {
2309 // If this is too complex for us to commit, reject it.
2310 DEBUG(dbgs() << "Pointer is too complex for us to evaluate store.");
2314 Constant
*Val
= getVal(SI
->getOperand(0));
2316 // If this might be too difficult for the backend to handle (e.g. the addr
2317 // of one global variable divided by another) then we can't commit it.
2318 if (!isSimpleEnoughValueToCommit(Val
, SimpleConstants
, DL
)) {
2319 DEBUG(dbgs() << "Store value is too complex to evaluate store. " << *Val
2324 if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(Ptr
)) {
2325 if (CE
->getOpcode() == Instruction::BitCast
) {
2326 DEBUG(dbgs() << "Attempting to resolve bitcast on constant ptr.\n");
2327 // If we're evaluating a store through a bitcast, then we need
2328 // to pull the bitcast off the pointer type and push it onto the
2330 Ptr
= CE
->getOperand(0);
2332 Type
*NewTy
= cast
<PointerType
>(Ptr
->getType())->getElementType();
2334 // In order to push the bitcast onto the stored value, a bitcast
2335 // from NewTy to Val's type must be legal. If it's not, we can try
2336 // introspecting NewTy to find a legal conversion.
2337 while (!Val
->getType()->canLosslesslyBitCastTo(NewTy
)) {
2338 // If NewTy is a struct, we can convert the pointer to the struct
2339 // into a pointer to its first member.
2340 // FIXME: This could be extended to support arrays as well.
2341 if (StructType
*STy
= dyn_cast
<StructType
>(NewTy
)) {
2342 NewTy
= STy
->getTypeAtIndex(0U);
2344 IntegerType
*IdxTy
= IntegerType::get(NewTy
->getContext(), 32);
2345 Constant
*IdxZero
= ConstantInt::get(IdxTy
, 0, false);
2346 Constant
* const IdxList
[] = {IdxZero
, IdxZero
};
2348 Ptr
= ConstantExpr::getGetElementPtr(Ptr
, IdxList
);
2349 if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(Ptr
))
2350 Ptr
= ConstantFoldConstantExpression(CE
, DL
, TLI
);
2352 // If we can't improve the situation by introspecting NewTy,
2353 // we have to give up.
2355 DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
2361 // If we found compatible types, go ahead and push the bitcast
2362 // onto the stored value.
2363 Val
= ConstantExpr::getBitCast(Val
, NewTy
);
2365 DEBUG(dbgs() << "Evaluated bitcast: " << *Val
<< "\n");
2369 MutatedMemory
[Ptr
] = Val
;
2370 } else if (BinaryOperator
*BO
= dyn_cast
<BinaryOperator
>(CurInst
)) {
2371 InstResult
= ConstantExpr::get(BO
->getOpcode(),
2372 getVal(BO
->getOperand(0)),
2373 getVal(BO
->getOperand(1)));
2374 DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: " << *InstResult
2376 } else if (CmpInst
*CI
= dyn_cast
<CmpInst
>(CurInst
)) {
2377 InstResult
= ConstantExpr::getCompare(CI
->getPredicate(),
2378 getVal(CI
->getOperand(0)),
2379 getVal(CI
->getOperand(1)));
2380 DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
2382 } else if (CastInst
*CI
= dyn_cast
<CastInst
>(CurInst
)) {
2383 InstResult
= ConstantExpr::getCast(CI
->getOpcode(),
2384 getVal(CI
->getOperand(0)),
2386 DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
2388 } else if (SelectInst
*SI
= dyn_cast
<SelectInst
>(CurInst
)) {
2389 InstResult
= ConstantExpr::getSelect(getVal(SI
->getOperand(0)),
2390 getVal(SI
->getOperand(1)),
2391 getVal(SI
->getOperand(2)));
2392 DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
2394 } else if (auto *EVI
= dyn_cast
<ExtractValueInst
>(CurInst
)) {
2395 InstResult
= ConstantExpr::getExtractValue(
2396 getVal(EVI
->getAggregateOperand()), EVI
->getIndices());
2397 DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: " << *InstResult
2399 } else if (auto *IVI
= dyn_cast
<InsertValueInst
>(CurInst
)) {
2400 InstResult
= ConstantExpr::getInsertValue(
2401 getVal(IVI
->getAggregateOperand()),
2402 getVal(IVI
->getInsertedValueOperand()), IVI
->getIndices());
2403 DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: " << *InstResult
2405 } else if (GetElementPtrInst
*GEP
= dyn_cast
<GetElementPtrInst
>(CurInst
)) {
2406 Constant
*P
= getVal(GEP
->getOperand(0));
2407 SmallVector
<Constant
*, 8> GEPOps
;
2408 for (User::op_iterator i
= GEP
->op_begin() + 1, e
= GEP
->op_end();
2410 GEPOps
.push_back(getVal(*i
));
2412 ConstantExpr::getGetElementPtr(P
, GEPOps
,
2413 cast
<GEPOperator
>(GEP
)->isInBounds());
2414 DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult
2416 } else if (LoadInst
*LI
= dyn_cast
<LoadInst
>(CurInst
)) {
2418 if (!LI
->isSimple()) {
2419 DEBUG(dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
2420 return false; // no volatile/atomic accesses.
2423 Constant
*Ptr
= getVal(LI
->getOperand(0));
2424 if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(Ptr
)) {
2425 Ptr
= ConstantFoldConstantExpression(CE
, DL
, TLI
);
2426 DEBUG(dbgs() << "Found a constant pointer expression, constant "
2427 "folding: " << *Ptr
<< "\n");
2429 InstResult
= ComputeLoadResult(Ptr
);
2431 DEBUG(dbgs() << "Failed to compute load result. Can not evaluate load."
2433 return false; // Could not evaluate load.
2436 DEBUG(dbgs() << "Evaluated load: " << *InstResult
<< "\n");
2437 } else if (AllocaInst
*AI
= dyn_cast
<AllocaInst
>(CurInst
)) {
2438 if (AI
->isArrayAllocation()) {
2439 DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
2440 return false; // Cannot handle array allocs.
2442 Type
*Ty
= AI
->getType()->getElementType();
2443 AllocaTmps
.push_back(
2444 make_unique
<GlobalVariable
>(Ty
, false, GlobalValue::InternalLinkage
,
2445 UndefValue::get(Ty
), AI
->getName()));
2446 InstResult
= AllocaTmps
.back().get();
2447 DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult
<< "\n");
2448 } else if (isa
<CallInst
>(CurInst
) || isa
<InvokeInst
>(CurInst
)) {
2449 CallSite
CS(CurInst
);
2451 // Debug info can safely be ignored here.
2452 if (isa
<DbgInfoIntrinsic
>(CS
.getInstruction())) {
2453 DEBUG(dbgs() << "Ignoring debug info.\n");
2458 // Cannot handle inline asm.
2459 if (isa
<InlineAsm
>(CS
.getCalledValue())) {
2460 DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
2464 if (IntrinsicInst
*II
= dyn_cast
<IntrinsicInst
>(CS
.getInstruction())) {
2465 if (MemSetInst
*MSI
= dyn_cast
<MemSetInst
>(II
)) {
2466 if (MSI
->isVolatile()) {
2467 DEBUG(dbgs() << "Can not optimize a volatile memset " <<
2471 Constant
*Ptr
= getVal(MSI
->getDest());
2472 Constant
*Val
= getVal(MSI
->getValue());
2473 Constant
*DestVal
= ComputeLoadResult(getVal(Ptr
));
2474 if (Val
->isNullValue() && DestVal
&& DestVal
->isNullValue()) {
2475 // This memset is a no-op.
2476 DEBUG(dbgs() << "Ignoring no-op memset.\n");
2482 if (II
->getIntrinsicID() == Intrinsic::lifetime_start
||
2483 II
->getIntrinsicID() == Intrinsic::lifetime_end
) {
2484 DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
2489 if (II
->getIntrinsicID() == Intrinsic::invariant_start
) {
2490 // We don't insert an entry into Values, as it doesn't have a
2491 // meaningful return value.
2492 if (!II
->use_empty()) {
2493 DEBUG(dbgs() << "Found unused invariant_start. Can't evaluate.\n");
2496 ConstantInt
*Size
= cast
<ConstantInt
>(II
->getArgOperand(0));
2497 Value
*PtrArg
= getVal(II
->getArgOperand(1));
2498 Value
*Ptr
= PtrArg
->stripPointerCasts();
2499 if (GlobalVariable
*GV
= dyn_cast
<GlobalVariable
>(Ptr
)) {
2500 Type
*ElemTy
= cast
<PointerType
>(GV
->getType())->getElementType();
2501 if (DL
&& !Size
->isAllOnesValue() &&
2502 Size
->getValue().getLimitedValue() >=
2503 DL
->getTypeStoreSize(ElemTy
)) {
2504 Invariants
.insert(GV
);
2505 DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV
2508 DEBUG(dbgs() << "Found a global var, but can not treat it as an "
2512 // Continue even if we do nothing.
2517 DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
2521 // Resolve function pointers.
2522 Function
*Callee
= dyn_cast
<Function
>(getVal(CS
.getCalledValue()));
2523 if (!Callee
|| Callee
->mayBeOverridden()) {
2524 DEBUG(dbgs() << "Can not resolve function pointer.\n");
2525 return false; // Cannot resolve.
2528 SmallVector
<Constant
*, 8> Formals
;
2529 for (User::op_iterator i
= CS
.arg_begin(), e
= CS
.arg_end(); i
!= e
; ++i
)
2530 Formals
.push_back(getVal(*i
));
2532 if (Callee
->isDeclaration()) {
2533 // If this is a function we can constant fold, do it.
2534 if (Constant
*C
= ConstantFoldCall(Callee
, Formals
, TLI
)) {
2536 DEBUG(dbgs() << "Constant folded function call. Result: " <<
2537 *InstResult
<< "\n");
2539 DEBUG(dbgs() << "Can not constant fold function call.\n");
2543 if (Callee
->getFunctionType()->isVarArg()) {
2544 DEBUG(dbgs() << "Can not constant fold vararg function call.\n");
2548 Constant
*RetVal
= nullptr;
2549 // Execute the call, if successful, use the return value.
2550 ValueStack
.emplace_back();
2551 if (!EvaluateFunction(Callee
, RetVal
, Formals
)) {
2552 DEBUG(dbgs() << "Failed to evaluate function.\n");
2555 ValueStack
.pop_back();
2556 InstResult
= RetVal
;
2559 DEBUG(dbgs() << "Successfully evaluated function. Result: " <<
2560 InstResult
<< "\n\n");
2562 DEBUG(dbgs() << "Successfully evaluated function. Result: 0\n\n");
2565 } else if (isa
<TerminatorInst
>(CurInst
)) {
2566 DEBUG(dbgs() << "Found a terminator instruction.\n");
2568 if (BranchInst
*BI
= dyn_cast
<BranchInst
>(CurInst
)) {
2569 if (BI
->isUnconditional()) {
2570 NextBB
= BI
->getSuccessor(0);
2573 dyn_cast
<ConstantInt
>(getVal(BI
->getCondition()));
2574 if (!Cond
) return false; // Cannot determine.
2576 NextBB
= BI
->getSuccessor(!Cond
->getZExtValue());
2578 } else if (SwitchInst
*SI
= dyn_cast
<SwitchInst
>(CurInst
)) {
2580 dyn_cast
<ConstantInt
>(getVal(SI
->getCondition()));
2581 if (!Val
) return false; // Cannot determine.
2582 NextBB
= SI
->findCaseValue(Val
).getCaseSuccessor();
2583 } else if (IndirectBrInst
*IBI
= dyn_cast
<IndirectBrInst
>(CurInst
)) {
2584 Value
*Val
= getVal(IBI
->getAddress())->stripPointerCasts();
2585 if (BlockAddress
*BA
= dyn_cast
<BlockAddress
>(Val
))
2586 NextBB
= BA
->getBasicBlock();
2588 return false; // Cannot determine.
2589 } else if (isa
<ReturnInst
>(CurInst
)) {
2592 // invoke, unwind, resume, unreachable.
2593 DEBUG(dbgs() << "Can not handle terminator.");
2594 return false; // Cannot handle this terminator.
2597 // We succeeded at evaluating this block!
2598 DEBUG(dbgs() << "Successfully evaluated block.\n");
2601 // Did not know how to evaluate this!
2602 DEBUG(dbgs() << "Failed to evaluate block due to unhandled instruction."
2607 if (!CurInst
->use_empty()) {
2608 if (ConstantExpr
*CE
= dyn_cast
<ConstantExpr
>(InstResult
))
2609 InstResult
= ConstantFoldConstantExpression(CE
, DL
, TLI
);
2611 setVal(CurInst
, InstResult
);
2614 // If we just processed an invoke, we finished evaluating the block.
2615 if (InvokeInst
*II
= dyn_cast
<InvokeInst
>(CurInst
)) {
2616 NextBB
= II
->getNormalDest();
2617 DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
2621 // Advance program counter.
2626 /// EvaluateFunction - Evaluate a call to function F, returning true if
2627 /// successful, false if we can't evaluate it. ActualArgs contains the formal
2628 /// arguments for the function.
2629 bool Evaluator::EvaluateFunction(Function
*F
, Constant
*&RetVal
,
2630 const SmallVectorImpl
<Constant
*> &ActualArgs
) {
2631 // Check to see if this function is already executing (recursion). If so,
2632 // bail out. TODO: we might want to accept limited recursion.
2633 if (std::find(CallStack
.begin(), CallStack
.end(), F
) != CallStack
.end())
2636 CallStack
.push_back(F
);
2638 // Initialize arguments to the incoming values specified.
2640 for (Function::arg_iterator AI
= F
->arg_begin(), E
= F
->arg_end(); AI
!= E
;
2642 setVal(AI
, ActualArgs
[ArgNo
]);
2644 // ExecutedBlocks - We only handle non-looping, non-recursive code. As such,
2645 // we can only evaluate any one basic block at most once. This set keeps
2646 // track of what we have executed so we can detect recursive cases etc.
2647 SmallPtrSet
<BasicBlock
*, 32> ExecutedBlocks
;
2649 // CurBB - The current basic block we're evaluating.
2650 BasicBlock
*CurBB
= F
->begin();
2652 BasicBlock::iterator CurInst
= CurBB
->begin();
2655 BasicBlock
*NextBB
= nullptr; // Initialized to avoid compiler warnings.
2656 DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB
<< "\n");
2658 if (!EvaluateBlock(CurInst
, NextBB
))
2662 // Successfully running until there's no next block means that we found
2663 // the return. Fill it the return value and pop the call stack.
2664 ReturnInst
*RI
= cast
<ReturnInst
>(CurBB
->getTerminator());
2665 if (RI
->getNumOperands())
2666 RetVal
= getVal(RI
->getOperand(0));
2667 CallStack
.pop_back();
2671 // Okay, we succeeded in evaluating this control flow. See if we have
2672 // executed the new block before. If so, we have a looping function,
2673 // which we cannot evaluate in reasonable time.
2674 if (!ExecutedBlocks
.insert(NextBB
).second
)
2675 return false; // looped!
2677 // Okay, we have never been in this block before. Check to see if there
2678 // are any PHI nodes. If so, evaluate them with information about where
2680 PHINode
*PN
= nullptr;
2681 for (CurInst
= NextBB
->begin();
2682 (PN
= dyn_cast
<PHINode
>(CurInst
)); ++CurInst
)
2683 setVal(PN
, getVal(PN
->getIncomingValueForBlock(CurBB
)));
2685 // Advance to the next block.
2690 /// EvaluateStaticConstructor - Evaluate static constructors in the function, if
2691 /// we can. Return true if we can, false otherwise.
2692 static bool EvaluateStaticConstructor(Function
*F
, const DataLayout
*DL
,
2693 const TargetLibraryInfo
*TLI
) {
2694 // Call the function.
2695 Evaluator
Eval(DL
, TLI
);
2696 Constant
*RetValDummy
;
2697 bool EvalSuccess
= Eval
.EvaluateFunction(F
, RetValDummy
,
2698 SmallVector
<Constant
*, 0>());
2701 ++NumCtorsEvaluated
;
2703 // We succeeded at evaluation: commit the result.
2704 DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
2705 << F
->getName() << "' to " << Eval
.getMutatedMemory().size()
2707 for (DenseMap
<Constant
*, Constant
*>::const_iterator I
=
2708 Eval
.getMutatedMemory().begin(), E
= Eval
.getMutatedMemory().end();
2710 CommitValueTo(I
->second
, I
->first
);
2711 for (GlobalVariable
*GV
: Eval
.getInvariants())
2712 GV
->setConstant(true);
2718 static int compareNames(Constant
*const *A
, Constant
*const *B
) {
2719 return (*A
)->getName().compare((*B
)->getName());
2722 static void setUsedInitializer(GlobalVariable
&V
,
2723 const SmallPtrSet
<GlobalValue
*, 8> &Init
) {
2725 V
.eraseFromParent();
2729 // Type of pointer to the array of pointers.
2730 PointerType
*Int8PtrTy
= Type::getInt8PtrTy(V
.getContext(), 0);
2732 SmallVector
<llvm::Constant
*, 8> UsedArray
;
2733 for (GlobalValue
*GV
: Init
) {
2735 = ConstantExpr::getPointerBitCastOrAddrSpaceCast(GV
, Int8PtrTy
);
2736 UsedArray
.push_back(Cast
);
2738 // Sort to get deterministic order.
2739 array_pod_sort(UsedArray
.begin(), UsedArray
.end(), compareNames
);
2740 ArrayType
*ATy
= ArrayType::get(Int8PtrTy
, UsedArray
.size());
2742 Module
*M
= V
.getParent();
2743 V
.removeFromParent();
2744 GlobalVariable
*NV
=
2745 new GlobalVariable(*M
, ATy
, false, llvm::GlobalValue::AppendingLinkage
,
2746 llvm::ConstantArray::get(ATy
, UsedArray
), "");
2748 NV
->setSection("llvm.metadata");
2753 /// \brief An easy to access representation of llvm.used and llvm.compiler.used.
2755 SmallPtrSet
<GlobalValue
*, 8> Used
;
2756 SmallPtrSet
<GlobalValue
*, 8> CompilerUsed
;
2757 GlobalVariable
*UsedV
;
2758 GlobalVariable
*CompilerUsedV
;
2761 LLVMUsed(Module
&M
) {
2762 UsedV
= collectUsedGlobalVariables(M
, Used
, false);
2763 CompilerUsedV
= collectUsedGlobalVariables(M
, CompilerUsed
, true);
2765 typedef SmallPtrSet
<GlobalValue
*, 8>::iterator iterator
;
2766 typedef iterator_range
<iterator
> used_iterator_range
;
2767 iterator
usedBegin() { return Used
.begin(); }
2768 iterator
usedEnd() { return Used
.end(); }
2769 used_iterator_range
used() {
2770 return used_iterator_range(usedBegin(), usedEnd());
2772 iterator
compilerUsedBegin() { return CompilerUsed
.begin(); }
2773 iterator
compilerUsedEnd() { return CompilerUsed
.end(); }
2774 used_iterator_range
compilerUsed() {
2775 return used_iterator_range(compilerUsedBegin(), compilerUsedEnd());
2777 bool usedCount(GlobalValue
*GV
) const { return Used
.count(GV
); }
2778 bool compilerUsedCount(GlobalValue
*GV
) const {
2779 return CompilerUsed
.count(GV
);
2781 bool usedErase(GlobalValue
*GV
) { return Used
.erase(GV
); }
2782 bool compilerUsedErase(GlobalValue
*GV
) { return CompilerUsed
.erase(GV
); }
2783 bool usedInsert(GlobalValue
*GV
) { return Used
.insert(GV
).second
; }
2784 bool compilerUsedInsert(GlobalValue
*GV
) {
2785 return CompilerUsed
.insert(GV
).second
;
2788 void syncVariablesAndSets() {
2790 setUsedInitializer(*UsedV
, Used
);
2792 setUsedInitializer(*CompilerUsedV
, CompilerUsed
);
2797 static bool hasUseOtherThanLLVMUsed(GlobalAlias
&GA
, const LLVMUsed
&U
) {
2798 if (GA
.use_empty()) // No use at all.
2801 assert((!U
.usedCount(&GA
) || !U
.compilerUsedCount(&GA
)) &&
2802 "We should have removed the duplicated "
2803 "element from llvm.compiler.used");
2804 if (!GA
.hasOneUse())
2805 // Strictly more than one use. So at least one is not in llvm.used and
2806 // llvm.compiler.used.
2809 // Exactly one use. Check if it is in llvm.used or llvm.compiler.used.
2810 return !U
.usedCount(&GA
) && !U
.compilerUsedCount(&GA
);
2813 static bool hasMoreThanOneUseOtherThanLLVMUsed(GlobalValue
&V
,
2814 const LLVMUsed
&U
) {
2816 assert((!U
.usedCount(&V
) || !U
.compilerUsedCount(&V
)) &&
2817 "We should have removed the duplicated "
2818 "element from llvm.compiler.used");
2819 if (U
.usedCount(&V
) || U
.compilerUsedCount(&V
))
2821 return V
.hasNUsesOrMore(N
);
2824 static bool mayHaveOtherReferences(GlobalAlias
&GA
, const LLVMUsed
&U
) {
2825 if (!GA
.hasLocalLinkage())
2828 return U
.usedCount(&GA
) || U
.compilerUsedCount(&GA
);
2831 static bool hasUsesToReplace(GlobalAlias
&GA
, const LLVMUsed
&U
,
2832 bool &RenameTarget
) {
2833 RenameTarget
= false;
2835 if (hasUseOtherThanLLVMUsed(GA
, U
))
2838 // If the alias is externally visible, we may still be able to simplify it.
2839 if (!mayHaveOtherReferences(GA
, U
))
2842 // If the aliasee has internal linkage, give it the name and linkage
2843 // of the alias, and delete the alias. This turns:
2844 // define internal ... @f(...)
2845 // @a = alias ... @f
2847 // define ... @a(...)
2848 Constant
*Aliasee
= GA
.getAliasee();
2849 GlobalValue
*Target
= cast
<GlobalValue
>(Aliasee
->stripPointerCasts());
2850 if (!Target
->hasLocalLinkage())
2853 // Do not perform the transform if multiple aliases potentially target the
2854 // aliasee. This check also ensures that it is safe to replace the section
2855 // and other attributes of the aliasee with those of the alias.
2856 if (hasMoreThanOneUseOtherThanLLVMUsed(*Target
, U
))
2859 RenameTarget
= true;
2863 bool GlobalOpt::OptimizeGlobalAliases(Module
&M
) {
2864 bool Changed
= false;
2867 for (GlobalValue
*GV
: Used
.used())
2868 Used
.compilerUsedErase(GV
);
2870 for (Module::alias_iterator I
= M
.alias_begin(), E
= M
.alias_end();
2872 Module::alias_iterator J
= I
++;
2873 // Aliases without names cannot be referenced outside this module.
2874 if (!J
->hasName() && !J
->isDeclaration() && !J
->hasLocalLinkage())
2875 J
->setLinkage(GlobalValue::InternalLinkage
);
2876 // If the aliasee may change at link time, nothing can be done - bail out.
2877 if (J
->mayBeOverridden())
2880 Constant
*Aliasee
= J
->getAliasee();
2881 GlobalValue
*Target
= dyn_cast
<GlobalValue
>(Aliasee
->stripPointerCasts());
2882 // We can't trivially replace the alias with the aliasee if the aliasee is
2883 // non-trivial in some way.
2884 // TODO: Try to handle non-zero GEPs of local aliasees.
2887 Target
->removeDeadConstantUsers();
2889 // Make all users of the alias use the aliasee instead.
2891 if (!hasUsesToReplace(*J
, Used
, RenameTarget
))
2894 J
->replaceAllUsesWith(ConstantExpr::getBitCast(Aliasee
, J
->getType()));
2895 ++NumAliasesResolved
;
2899 // Give the aliasee the name, linkage and other attributes of the alias.
2900 Target
->takeName(J
);
2901 Target
->setLinkage(J
->getLinkage());
2902 Target
->setVisibility(J
->getVisibility());
2903 Target
->setDLLStorageClass(J
->getDLLStorageClass());
2905 if (Used
.usedErase(J
))
2906 Used
.usedInsert(Target
);
2908 if (Used
.compilerUsedErase(J
))
2909 Used
.compilerUsedInsert(Target
);
2910 } else if (mayHaveOtherReferences(*J
, Used
))
2913 // Delete the alias.
2914 M
.getAliasList().erase(J
);
2915 ++NumAliasesRemoved
;
2919 Used
.syncVariablesAndSets();
2924 static Function
*FindCXAAtExit(Module
&M
, TargetLibraryInfo
*TLI
) {
2925 if (!TLI
->has(LibFunc::cxa_atexit
))
2928 Function
*Fn
= M
.getFunction(TLI
->getName(LibFunc::cxa_atexit
));
2933 FunctionType
*FTy
= Fn
->getFunctionType();
2935 // Checking that the function has the right return type, the right number of
2936 // parameters and that they all have pointer types should be enough.
2937 if (!FTy
->getReturnType()->isIntegerTy() ||
2938 FTy
->getNumParams() != 3 ||
2939 !FTy
->getParamType(0)->isPointerTy() ||
2940 !FTy
->getParamType(1)->isPointerTy() ||
2941 !FTy
->getParamType(2)->isPointerTy())
2947 /// cxxDtorIsEmpty - Returns whether the given function is an empty C++
2948 /// destructor and can therefore be eliminated.
2949 /// Note that we assume that other optimization passes have already simplified
2950 /// the code so we only look for a function with a single basic block, where
2951 /// the only allowed instructions are 'ret', 'call' to an empty C++ dtor and
2952 /// other side-effect free instructions.
2953 static bool cxxDtorIsEmpty(const Function
&Fn
,
2954 SmallPtrSet
<const Function
*, 8> &CalledFunctions
) {
2955 // FIXME: We could eliminate C++ destructors if they're readonly/readnone and
2956 // nounwind, but that doesn't seem worth doing.
2957 if (Fn
.isDeclaration())
2960 if (++Fn
.begin() != Fn
.end())
2963 const BasicBlock
&EntryBlock
= Fn
.getEntryBlock();
2964 for (BasicBlock::const_iterator I
= EntryBlock
.begin(), E
= EntryBlock
.end();
2966 if (const CallInst
*CI
= dyn_cast
<CallInst
>(I
)) {
2967 // Ignore debug intrinsics.
2968 if (isa
<DbgInfoIntrinsic
>(CI
))
2971 const Function
*CalledFn
= CI
->getCalledFunction();
2976 SmallPtrSet
<const Function
*, 8> NewCalledFunctions(CalledFunctions
);
2978 // Don't treat recursive functions as empty.
2979 if (!NewCalledFunctions
.insert(CalledFn
).second
)
2982 if (!cxxDtorIsEmpty(*CalledFn
, NewCalledFunctions
))
2984 } else if (isa
<ReturnInst
>(*I
))
2985 return true; // We're done.
2986 else if (I
->mayHaveSideEffects())
2987 return false; // Destructor with side effects, bail.
2993 bool GlobalOpt::OptimizeEmptyGlobalCXXDtors(Function
*CXAAtExitFn
) {
2994 /// Itanium C++ ABI p3.3.5:
2996 /// After constructing a global (or local static) object, that will require
2997 /// destruction on exit, a termination function is registered as follows:
2999 /// extern "C" int __cxa_atexit ( void (*f)(void *), void *p, void *d );
3001 /// This registration, e.g. __cxa_atexit(f,p,d), is intended to cause the
3002 /// call f(p) when DSO d is unloaded, before all such termination calls
3003 /// registered before this one. It returns zero if registration is
3004 /// successful, nonzero on failure.
3006 // This pass will look for calls to __cxa_atexit where the function is trivial
3008 bool Changed
= false;
3010 for (auto I
= CXAAtExitFn
->user_begin(), E
= CXAAtExitFn
->user_end();
3012 // We're only interested in calls. Theoretically, we could handle invoke
3013 // instructions as well, but neither llvm-gcc nor clang generate invokes
3015 CallInst
*CI
= dyn_cast
<CallInst
>(*I
++);
3020 dyn_cast
<Function
>(CI
->getArgOperand(0)->stripPointerCasts());
3024 SmallPtrSet
<const Function
*, 8> CalledFunctions
;
3025 if (!cxxDtorIsEmpty(*DtorFn
, CalledFunctions
))
3028 // Just remove the call.
3029 CI
->replaceAllUsesWith(Constant::getNullValue(CI
->getType()));
3030 CI
->eraseFromParent();
3032 ++NumCXXDtorsRemoved
;
3040 bool GlobalOpt::runOnModule(Module
&M
) {
3041 bool Changed
= false;
3043 DataLayoutPass
*DLP
= getAnalysisIfAvailable
<DataLayoutPass
>();
3044 DL
= DLP
? &DLP
->getDataLayout() : nullptr;
3045 TLI
= &getAnalysis
<TargetLibraryInfo
>();
3047 bool LocalChange
= true;
3048 while (LocalChange
) {
3049 LocalChange
= false;
3051 NotDiscardableComdats
.clear();
3052 for (const GlobalVariable
&GV
: M
.globals())
3053 if (const Comdat
*C
= GV
.getComdat())
3054 if (!GV
.isDiscardableIfUnused() || !GV
.use_empty())
3055 NotDiscardableComdats
.insert(C
);
3056 for (Function
&F
: M
)
3057 if (const Comdat
*C
= F
.getComdat())
3058 if (!F
.isDefTriviallyDead())
3059 NotDiscardableComdats
.insert(C
);
3060 for (GlobalAlias
&GA
: M
.aliases())
3061 if (const Comdat
*C
= GA
.getComdat())
3062 if (!GA
.isDiscardableIfUnused() || !GA
.use_empty())
3063 NotDiscardableComdats
.insert(C
);
3065 // Delete functions that are trivially dead, ccc -> fastcc
3066 LocalChange
|= OptimizeFunctions(M
);
3068 // Optimize global_ctors list.
3069 LocalChange
|= optimizeGlobalCtorsList(M
, [&](Function
*F
) {
3070 return EvaluateStaticConstructor(F
, DL
, TLI
);
3073 // Optimize non-address-taken globals.
3074 LocalChange
|= OptimizeGlobalVars(M
);
3076 // Resolve aliases, when possible.
3077 LocalChange
|= OptimizeGlobalAliases(M
);
3079 // Try to remove trivial global destructors if they are not removed
3081 Function
*CXAAtExitFn
= FindCXAAtExit(M
, TLI
);
3083 LocalChange
|= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn
);
3085 Changed
|= LocalChange
;
3088 // TODO: Move all global ctors functions to the end of the module for code