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

source code of llvm/lib/Transforms/IPO/GlobalOpt.cpp