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