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