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