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