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