/tmp/buildd/llvm-toolchain-snapshot-3.7~svn236708/lib/Transforms/IPO/GlobalOpt.cpp

Bug Summary

File:	lib/Transforms/IPO/GlobalOpt.cpp
Location:	line 578, column 9
Description:	Value stored to 'NewTy' is never read

Annotated Source Code

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