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