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