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