LLVM 18.0.0git
GlobalOpt.cpp
Go to the documentation of this file.
1//===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This pass transforms simple global variables that never have their address
10// taken. If obviously true, it marks read/write globals as constant, deletes
11// variables only stored to, etc.
12//
13//===----------------------------------------------------------------------===//
14
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/STLExtras.h"
20#include "llvm/ADT/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 (Ty->isScalableTy())
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 AddrSpaceCastInst *CI = dyn_cast<AddrSpaceCastInst>(U)) {
667 if (!AllUsesOfValueWillTrapIfNull(CI, PHIs))
668 return false;
669 } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
670 if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false;
671 } else if (const PHINode *PN = dyn_cast<PHINode>(U)) {
672 // If we've already seen this phi node, ignore it, it has already been
673 // checked.
674 if (PHIs.insert(PN).second && !AllUsesOfValueWillTrapIfNull(PN, PHIs))
675 return false;
676 } else if (isa<ICmpInst>(U) &&
677 !ICmpInst::isSigned(cast<ICmpInst>(U)->getPredicate()) &&
678 isa<LoadInst>(U->getOperand(0)) &&
679 isa<ConstantPointerNull>(U->getOperand(1))) {
680 assert(isa<GlobalValue>(cast<LoadInst>(U->getOperand(0))
681 ->getPointerOperand()
682 ->stripPointerCasts()) &&
683 "Should be GlobalVariable");
684 // This and only this kind of non-signed ICmpInst is to be replaced with
685 // the comparing of the value of the created global init bool later in
686 // optimizeGlobalAddressOfAllocation for the global variable.
687 } else {
688 return false;
689 }
690 }
691 return true;
692}
693
694/// Return true if all uses of any loads from GV will trap if the loaded value
695/// is null. Note that this also permits comparisons of the loaded value
696/// against null, as a special case.
699 Worklist.push_back(GV);
700 while (!Worklist.empty()) {
701 const Value *P = Worklist.pop_back_val();
702 for (const auto *U : P->users()) {
703 if (auto *LI = dyn_cast<LoadInst>(U)) {
705 if (!AllUsesOfValueWillTrapIfNull(LI, PHIs))
706 return false;
707 } else if (auto *SI = dyn_cast<StoreInst>(U)) {
708 // Ignore stores to the global.
709 if (SI->getPointerOperand() != P)
710 return false;
711 } else if (auto *CE = dyn_cast<ConstantExpr>(U)) {
712 if (CE->stripPointerCasts() != GV)
713 return false;
714 // Check further the ConstantExpr.
715 Worklist.push_back(CE);
716 } else {
717 // We don't know or understand this user, bail out.
718 return false;
719 }
720 }
721 }
722
723 return true;
724}
725
726/// Get all the loads/store uses for global variable \p GV.
730 Worklist.push_back(GV);
731 while (!Worklist.empty()) {
732 auto *P = Worklist.pop_back_val();
733 for (auto *U : P->users()) {
734 if (auto *CE = dyn_cast<ConstantExpr>(U)) {
735 Worklist.push_back(CE);
736 continue;
737 }
738
739 assert((isa<LoadInst>(U) || isa<StoreInst>(U)) &&
740 "Expect only load or store instructions");
741 Uses.push_back(U);
742 }
743 }
744}
745
747 bool Changed = false;
748 for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) {
749 Instruction *I = cast<Instruction>(*UI++);
750 // Uses are non-trapping if null pointer is considered valid.
751 // Non address-space 0 globals are already pruned by the caller.
752 if (NullPointerIsDefined(I->getFunction()))
753 return false;
754 if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
755 LI->setOperand(0, NewV);
756 Changed = true;
757 } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
758 if (SI->getOperand(1) == V) {
759 SI->setOperand(1, NewV);
760 Changed = true;
761 }
762 } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
763 CallBase *CB = cast<CallBase>(I);
764 if (CB->getCalledOperand() == V) {
765 // Calling through the pointer! Turn into a direct call, but be careful
766 // that the pointer is not also being passed as an argument.
767 CB->setCalledOperand(NewV);
768 Changed = true;
769 bool PassedAsArg = false;
770 for (unsigned i = 0, e = CB->arg_size(); i != e; ++i)
771 if (CB->getArgOperand(i) == V) {
772 PassedAsArg = true;
773 CB->setArgOperand(i, NewV);
774 }
775
776 if (PassedAsArg) {
777 // Being passed as an argument also. Be careful to not invalidate UI!
778 UI = V->user_begin();
779 }
780 }
781 } else if (AddrSpaceCastInst *CI = dyn_cast<AddrSpaceCastInst>(I)) {
783 CI, ConstantExpr::getAddrSpaceCast(NewV, CI->getType()));
784 if (CI->use_empty()) {
785 Changed = true;
786 CI->eraseFromParent();
787 }
788 } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
789 // Should handle GEP here.
791 Idxs.reserve(GEPI->getNumOperands()-1);
792 for (User::op_iterator i = GEPI->op_begin() + 1, e = GEPI->op_end();
793 i != e; ++i)
794 if (Constant *C = dyn_cast<Constant>(*i))
795 Idxs.push_back(C);
796 else
797 break;
798 if (Idxs.size() == GEPI->getNumOperands()-1)
800 GEPI, ConstantExpr::getGetElementPtr(GEPI->getSourceElementType(),
801 NewV, Idxs));
802 if (GEPI->use_empty()) {
803 Changed = true;
804 GEPI->eraseFromParent();
805 }
806 }
807 }
808
809 return Changed;
810}
811
812/// The specified global has only one non-null value stored into it. If there
813/// are uses of the loaded value that would trap if the loaded value is
814/// dynamically null, then we know that they cannot be reachable with a null
815/// optimize away the load.
817 GlobalVariable *GV, Constant *LV, const DataLayout &DL,
819 bool Changed = false;
820
821 // Keep track of whether we are able to remove all the uses of the global
822 // other than the store that defines it.
823 bool AllNonStoreUsesGone = true;
824
825 // Replace all uses of loads with uses of uses of the stored value.
826 for (User *GlobalUser : llvm::make_early_inc_range(GV->users())) {
827 if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) {
828 Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV);
829 // If we were able to delete all uses of the loads
830 if (LI->use_empty()) {
831 LI->eraseFromParent();
832 Changed = true;
833 } else {
834 AllNonStoreUsesGone = false;
835 }
836 } else if (isa<StoreInst>(GlobalUser)) {
837 // Ignore the store that stores "LV" to the global.
838 assert(GlobalUser->getOperand(1) == GV &&
839 "Must be storing *to* the global");
840 } else {
841 AllNonStoreUsesGone = false;
842
843 // If we get here we could have other crazy uses that are transitively
844 // loaded.
845 assert((isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) ||
846 isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) ||
847 isa<BitCastInst>(GlobalUser) ||
848 isa<GetElementPtrInst>(GlobalUser) ||
849 isa<AddrSpaceCastInst>(GlobalUser)) &&
850 "Only expect load and stores!");
851 }
852 }
853
854 if (Changed) {
855 LLVM_DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV
856 << "\n");
857 ++NumGlobUses;
858 }
859
860 // If we nuked all of the loads, then none of the stores are needed either,
861 // nor is the global.
862 if (AllNonStoreUsesGone) {
863 if (isLeakCheckerRoot(GV)) {
864 Changed |= CleanupPointerRootUsers(GV, GetTLI);
865 } else {
866 Changed = true;
868 }
869 if (GV->use_empty()) {
870 LLVM_DEBUG(dbgs() << " *** GLOBAL NOW DEAD!\n");
871 Changed = true;
872 GV->eraseFromParent();
873 ++NumDeleted;
874 }
875 }
876 return Changed;
877}
878
879/// Walk the use list of V, constant folding all of the instructions that are
880/// foldable.
881static void ConstantPropUsersOf(Value *V, const DataLayout &DL,
882 TargetLibraryInfo *TLI) {
883 for (Value::user_iterator UI = V->user_begin(), E = V->user_end(); UI != E; )
884 if (Instruction *I = dyn_cast<Instruction>(*UI++))
885 if (Constant *NewC = ConstantFoldInstruction(I, DL, TLI)) {
886 I->replaceAllUsesWith(NewC);
887
888 // Advance UI to the next non-I use to avoid invalidating it!
889 // Instructions could multiply use V.
890 while (UI != E && *UI == I)
891 ++UI;
893 I->eraseFromParent();
894 }
895}
896
897/// This function takes the specified global variable, and transforms the
898/// program as if it always contained the result of the specified malloc.
899/// Because it is always the result of the specified malloc, there is no reason
900/// to actually DO the malloc. Instead, turn the malloc into a global, and any
901/// loads of GV as uses of the new global.
902static GlobalVariable *
904 uint64_t AllocSize, Constant *InitVal,
905 const DataLayout &DL,
906 TargetLibraryInfo *TLI) {
907 LLVM_DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << " CALL = " << *CI
908 << '\n');
909
910 // Create global of type [AllocSize x i8].
911 Type *GlobalType = ArrayType::get(Type::getInt8Ty(GV->getContext()),
912 AllocSize);
913
914 // Create the new global variable. The contents of the allocated memory is
915 // undefined initially, so initialize with an undef value.
916 GlobalVariable *NewGV = new GlobalVariable(
917 *GV->getParent(), GlobalType, false, GlobalValue::InternalLinkage,
918 UndefValue::get(GlobalType), GV->getName() + ".body", nullptr,
919 GV->getThreadLocalMode());
920
921 // Initialize the global at the point of the original call. Note that this
922 // is a different point from the initialization referred to below for the
923 // nullability handling. Sublety: We have not proven the original global was
924 // only initialized once. As such, we can not fold this into the initializer
925 // of the new global as may need to re-init the storage multiple times.
926 if (!isa<UndefValue>(InitVal)) {
928 // TODO: Use alignment above if align!=1
929 Builder.CreateMemSet(NewGV, InitVal, AllocSize, std::nullopt);
930 }
931
932 // Update users of the allocation to use the new global instead.
933 CI->replaceAllUsesWith(NewGV);
934
935 // If there is a comparison against null, we will insert a global bool to
936 // keep track of whether the global was initialized yet or not.
937 GlobalVariable *InitBool =
938 new GlobalVariable(Type::getInt1Ty(GV->getContext()), false,
941 GV->getName()+".init", GV->getThreadLocalMode());
942 bool InitBoolUsed = false;
943
944 // Loop over all instruction uses of GV, processing them in turn.
946 allUsesOfLoadAndStores(GV, Guses);
947 for (auto *U : Guses) {
948 if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
949 // The global is initialized when the store to it occurs. If the stored
950 // value is null value, the global bool is set to false, otherwise true.
952 GV->getContext(),
953 !isa<ConstantPointerNull>(SI->getValueOperand())),
954 InitBool, false, Align(1), SI->getOrdering(),
955 SI->getSyncScopeID(), SI);
956 SI->eraseFromParent();
957 continue;
958 }
959
960 LoadInst *LI = cast<LoadInst>(U);
961 while (!LI->use_empty()) {
962 Use &LoadUse = *LI->use_begin();
963 ICmpInst *ICI = dyn_cast<ICmpInst>(LoadUse.getUser());
964 if (!ICI) {
965 LoadUse.set(NewGV);
966 continue;
967 }
968
969 // Replace the cmp X, 0 with a use of the bool value.
970 Value *LV = new LoadInst(InitBool->getValueType(), InitBool,
971 InitBool->getName() + ".val", false, Align(1),
972 LI->getOrdering(), LI->getSyncScopeID(), LI);
973 InitBoolUsed = true;
974 switch (ICI->getPredicate()) {
975 default: llvm_unreachable("Unknown ICmp Predicate!");
976 case ICmpInst::ICMP_ULT: // X < null -> always false
978 break;
979 case ICmpInst::ICMP_UGE: // X >= null -> always true
981 break;
982 case ICmpInst::ICMP_ULE:
983 case ICmpInst::ICMP_EQ:
984 LV = BinaryOperator::CreateNot(LV, "notinit", ICI);
985 break;
986 case ICmpInst::ICMP_NE:
987 case ICmpInst::ICMP_UGT:
988 break; // no change.
989 }
990 ICI->replaceAllUsesWith(LV);
991 ICI->eraseFromParent();
992 }
993 LI->eraseFromParent();
994 }
995
996 // If the initialization boolean was used, insert it, otherwise delete it.
997 if (!InitBoolUsed) {
998 while (!InitBool->use_empty()) // Delete initializations
999 cast<StoreInst>(InitBool->user_back())->eraseFromParent();
1000 delete InitBool;
1001 } else
1002 GV->getParent()->insertGlobalVariable(GV->getIterator(), InitBool);
1003
1004 // Now the GV is dead, nuke it and the allocation..
1005 GV->eraseFromParent();
1006 CI->eraseFromParent();
1007
1008 // To further other optimizations, loop over all users of NewGV and try to
1009 // constant prop them. This will promote GEP instructions with constant
1010 // indices into GEP constant-exprs, which will allow global-opt to hack on it.
1011 ConstantPropUsersOf(NewGV, DL, TLI);
1012
1013 return NewGV;
1014}
1015
1016/// Scan the use-list of GV checking to make sure that there are no complex uses
1017/// of GV. We permit simple things like dereferencing the pointer, but not
1018/// storing through the address, unless it is to the specified global.
1019static bool
1021 const GlobalVariable *GV) {
1024 Worklist.push_back(CI);
1025
1026 while (!Worklist.empty()) {
1027 const Value *V = Worklist.pop_back_val();
1028 if (!Visited.insert(V).second)
1029 continue;
1030
1031 for (const Use &VUse : V->uses()) {
1032 const User *U = VUse.getUser();
1033 if (isa<LoadInst>(U) || isa<CmpInst>(U))
1034 continue; // Fine, ignore.
1035
1036 if (auto *SI = dyn_cast<StoreInst>(U)) {
1037 if (SI->getValueOperand() == V &&
1038 SI->getPointerOperand()->stripPointerCasts() != GV)
1039 return false; // Storing the pointer not into GV... bad.
1040 continue; // Otherwise, storing through it, or storing into GV... fine.
1041 }
1042
1043 if (auto *BCI = dyn_cast<BitCastInst>(U)) {
1044 Worklist.push_back(BCI);
1045 continue;
1046 }
1047
1048 if (auto *GEPI = dyn_cast<GetElementPtrInst>(U)) {
1049 Worklist.push_back(GEPI);
1050 continue;
1051 }
1052
1053 return false;
1054 }
1055 }
1056
1057 return true;
1058}
1059
1060/// If we have a global that is only initialized with a fixed size allocation
1061/// try to transform the program to use global memory instead of heap
1062/// allocated memory. This eliminates dynamic allocation, avoids an indirection
1063/// accessing the data, and exposes the resultant global to further GlobalOpt.
1065 CallInst *CI,
1066 const DataLayout &DL,
1067 TargetLibraryInfo *TLI) {
1068 if (!isRemovableAlloc(CI, TLI))
1069 // Must be able to remove the call when we get done..
1070 return false;
1071
1072 Type *Int8Ty = Type::getInt8Ty(CI->getFunction()->getContext());
1073 Constant *InitVal = getInitialValueOfAllocation(CI, TLI, Int8Ty);
1074 if (!InitVal)
1075 // Must be able to emit a memset for initialization
1076 return false;
1077
1078 uint64_t AllocSize;
1079 if (!getObjectSize(CI, AllocSize, DL, TLI, ObjectSizeOpts()))
1080 return false;
1081
1082 // Restrict this transformation to only working on small allocations
1083 // (2048 bytes currently), as we don't want to introduce a 16M global or
1084 // something.
1085 if (AllocSize >= 2048)
1086 return false;
1087
1088 // We can't optimize this global unless all uses of it are *known* to be
1089 // of the malloc value, not of the null initializer value (consider a use
1090 // that compares the global's value against zero to see if the malloc has
1091 // been reached). To do this, we check to see if all uses of the global
1092 // would trap if the global were null: this proves that they must all
1093 // happen after the malloc.
1095 return false;
1096
1097 // We can't optimize this if the malloc itself is used in a complex way,
1098 // for example, being stored into multiple globals. This allows the
1099 // malloc to be stored into the specified global, loaded, gep, icmp'd.
1100 // These are all things we could transform to using the global for.
1102 return false;
1103
1104 OptimizeGlobalAddressOfAllocation(GV, CI, AllocSize, InitVal, DL, TLI);
1105 return true;
1106}
1107
1108// Try to optimize globals based on the knowledge that only one value (besides
1109// its initializer) is ever stored to the global.
1110static bool
1112 const DataLayout &DL,
1114 // Ignore no-op GEPs and bitcasts.
1115 StoredOnceVal = StoredOnceVal->stripPointerCasts();
1116
1117 // If we are dealing with a pointer global that is initialized to null and
1118 // only has one (non-null) value stored into it, then we can optimize any
1119 // users of the loaded value (often calls and loads) that would trap if the
1120 // value was null.
1121 if (GV->getInitializer()->getType()->isPointerTy() &&
1122 GV->getInitializer()->isNullValue() &&
1123 StoredOnceVal->getType()->isPointerTy() &&
1125 nullptr /* F */,
1127 if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
1128 // Optimize away any trapping uses of the loaded value.
1129 if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, DL, GetTLI))
1130 return true;
1131 } else if (isAllocationFn(StoredOnceVal, GetTLI)) {
1132 if (auto *CI = dyn_cast<CallInst>(StoredOnceVal)) {
1133 auto *TLI = &GetTLI(*CI->getFunction());
1135 return true;
1136 }
1137 }
1138 }
1139
1140 return false;
1141}
1142
1143/// At this point, we have learned that the only two values ever stored into GV
1144/// are its initializer and OtherVal. See if we can shrink the global into a
1145/// boolean and select between the two values whenever it is used. This exposes
1146/// the values to other scalar optimizations.
1148 Type *GVElType = GV->getValueType();
1149
1150 // If GVElType is already i1, it is already shrunk. If the type of the GV is
1151 // an FP value, pointer or vector, don't do this optimization because a select
1152 // between them is very expensive and unlikely to lead to later
1153 // simplification. In these cases, we typically end up with "cond ? v1 : v2"
1154 // where v1 and v2 both require constant pool loads, a big loss.
1155 if (GVElType == Type::getInt1Ty(GV->getContext()) ||
1156 GVElType->isFloatingPointTy() ||
1157 GVElType->isPointerTy() || GVElType->isVectorTy())
1158 return false;
1159
1160 // Walk the use list of the global seeing if all the uses are load or store.
1161 // If there is anything else, bail out.
1162 for (User *U : GV->users()) {
1163 if (!isa<LoadInst>(U) && !isa<StoreInst>(U))
1164 return false;
1165 if (getLoadStoreType(U) != GVElType)
1166 return false;
1167 }
1168
1169 LLVM_DEBUG(dbgs() << " *** SHRINKING TO BOOL: " << *GV << "\n");
1170
1171 // Create the new global, initializing it to false.
1173 false,
1176 GV->getName()+".b",
1177 GV->getThreadLocalMode(),
1178 GV->getType()->getAddressSpace());
1179 NewGV->copyAttributesFrom(GV);
1180 GV->getParent()->insertGlobalVariable(GV->getIterator(), NewGV);
1181
1182 Constant *InitVal = GV->getInitializer();
1183 assert(InitVal->getType() != Type::getInt1Ty(GV->getContext()) &&
1184 "No reason to shrink to bool!");
1185
1187 GV->getDebugInfo(GVs);
1188
1189 // If initialized to zero and storing one into the global, we can use a cast
1190 // instead of a select to synthesize the desired value.
1191 bool IsOneZero = false;
1192 bool EmitOneOrZero = true;
1193 auto *CI = dyn_cast<ConstantInt>(OtherVal);
1194 if (CI && CI->getValue().getActiveBits() <= 64) {
1195 IsOneZero = InitVal->isNullValue() && CI->isOne();
1196
1197 auto *CIInit = dyn_cast<ConstantInt>(GV->getInitializer());
1198 if (CIInit && CIInit->getValue().getActiveBits() <= 64) {
1199 uint64_t ValInit = CIInit->getZExtValue();
1200 uint64_t ValOther = CI->getZExtValue();
1201 uint64_t ValMinus = ValOther - ValInit;
1202
1203 for(auto *GVe : GVs){
1204 DIGlobalVariable *DGV = GVe->getVariable();
1205 DIExpression *E = GVe->getExpression();
1206 const DataLayout &DL = GV->getParent()->getDataLayout();
1207 unsigned SizeInOctets =
1208 DL.getTypeAllocSizeInBits(NewGV->getValueType()) / 8;
1209
1210 // It is expected that the address of global optimized variable is on
1211 // top of the stack. After optimization, value of that variable will
1212 // be ether 0 for initial value or 1 for other value. The following
1213 // expression should return constant integer value depending on the
1214 // value at global object address:
1215 // val * (ValOther - ValInit) + ValInit:
1216 // DW_OP_deref DW_OP_constu <ValMinus>
1217 // DW_OP_mul DW_OP_constu <ValInit> DW_OP_plus DW_OP_stack_value
1219 dwarf::DW_OP_deref_size, SizeInOctets,
1220 dwarf::DW_OP_constu, ValMinus,
1221 dwarf::DW_OP_mul, dwarf::DW_OP_constu, ValInit,
1222 dwarf::DW_OP_plus};
1223 bool WithStackValue = true;
1224 E = DIExpression::prependOpcodes(E, Ops, WithStackValue);
1226 DIGlobalVariableExpression::get(NewGV->getContext(), DGV, E);
1227 NewGV->addDebugInfo(DGVE);
1228 }
1229 EmitOneOrZero = false;
1230 }
1231 }
1232
1233 if (EmitOneOrZero) {
1234 // FIXME: This will only emit address for debugger on which will
1235 // be written only 0 or 1.
1236 for(auto *GV : GVs)
1237 NewGV->addDebugInfo(GV);
1238 }
1239
1240 while (!GV->use_empty()) {
1241 Instruction *UI = cast<Instruction>(GV->user_back());
1242 if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
1243 // Change the store into a boolean store.
1244 bool StoringOther = SI->getOperand(0) == OtherVal;
1245 // Only do this if we weren't storing a loaded value.
1246 Value *StoreVal;
1247 if (StoringOther || SI->getOperand(0) == InitVal) {
1249 StoringOther);
1250 } else {
1251 // Otherwise, we are storing a previously loaded copy. To do this,
1252 // change the copy from copying the original value to just copying the
1253 // bool.
1254 Instruction *StoredVal = cast<Instruction>(SI->getOperand(0));
1255
1256 // If we've already replaced the input, StoredVal will be a cast or
1257 // select instruction. If not, it will be a load of the original
1258 // global.
1259 if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
1260 assert(LI->getOperand(0) == GV && "Not a copy!");
1261 // Insert a new load, to preserve the saved value.
1262 StoreVal = new LoadInst(NewGV->getValueType(), NewGV,
1263 LI->getName() + ".b", false, Align(1),
1264 LI->getOrdering(), LI->getSyncScopeID(), LI);
1265 } else {
1266 assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) &&
1267 "This is not a form that we understand!");
1268 StoreVal = StoredVal->getOperand(0);
1269 assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!");
1270 }
1271 }
1272 StoreInst *NSI =
1273 new StoreInst(StoreVal, NewGV, false, Align(1), SI->getOrdering(),
1274 SI->getSyncScopeID(), SI);
1275 NSI->setDebugLoc(SI->getDebugLoc());
1276 } else {
1277 // Change the load into a load of bool then a select.
1278 LoadInst *LI = cast<LoadInst>(UI);
1279 LoadInst *NLI = new LoadInst(NewGV->getValueType(), NewGV,
1280 LI->getName() + ".b", false, Align(1),
1281 LI->getOrdering(), LI->getSyncScopeID(), LI);
1282 Instruction *NSI;
1283 if (IsOneZero)
1284 NSI = new ZExtInst(NLI, LI->getType(), "", LI);
1285 else
1286 NSI = SelectInst::Create(NLI, OtherVal, InitVal, "", LI);
1287 NSI->takeName(LI);
1288 // Since LI is split into two instructions, NLI and NSI both inherit the
1289 // same DebugLoc
1290 NLI->setDebugLoc(LI->getDebugLoc());
1291 NSI->setDebugLoc(LI->getDebugLoc());
1292 LI->replaceAllUsesWith(NSI);
1293 }
1294 UI->eraseFromParent();
1295 }
1296
1297 // Retain the name of the old global variable. People who are debugging their
1298 // programs may expect these variables to be named the same.
1299 NewGV->takeName(GV);
1300 GV->eraseFromParent();
1301 return true;
1302}
1303
1304static bool
1306 SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats,
1307 function_ref<void(Function &)> DeleteFnCallback = nullptr) {
1309
1310 if (!GV.isDiscardableIfUnused() && !GV.isDeclaration())
1311 return false;
1312
1313 if (const Comdat *C = GV.getComdat())
1314 if (!GV.hasLocalLinkage() && NotDiscardableComdats.count(C))
1315 return false;
1316
1317 bool Dead;
1318 if (auto *F = dyn_cast<Function>(&GV))
1319 Dead = (F->isDeclaration() && F->use_empty()) || F->isDefTriviallyDead();
1320 else
1321 Dead = GV.use_empty();
1322 if (!Dead)
1323 return false;
1324
1325 LLVM_DEBUG(dbgs() << "GLOBAL DEAD: " << GV << "\n");
1326 if (auto *F = dyn_cast<Function>(&GV)) {
1327 if (DeleteFnCallback)
1328 DeleteFnCallback(*F);
1329 }
1330 GV.eraseFromParent();
1331 ++NumDeleted;
1332 return true;
1333}
1334
1336 const Function *F, GlobalValue *GV,
1337 function_ref<DominatorTree &(Function &)> LookupDomTree) {
1338 // Find all uses of GV. We expect them all to be in F, and if we can't
1339 // identify any of the uses we bail out.
1340 //
1341 // On each of these uses, identify if the memory that GV points to is
1342 // used/required/live at the start of the function. If it is not, for example
1343 // if the first thing the function does is store to the GV, the GV can
1344 // possibly be demoted.
1345 //
1346 // We don't do an exhaustive search for memory operations - simply look
1347 // through bitcasts as they're quite common and benign.
1348 const DataLayout &DL = GV->getParent()->getDataLayout();
1351 for (auto *U : GV->users()) {
1352 Instruction *I = dyn_cast<Instruction>(U);
1353 if (!I)
1354 return false;
1355 assert(I->getParent()->getParent() == F);
1356
1357 if (auto *LI = dyn_cast<LoadInst>(I))
1358 Loads.push_back(LI);
1359 else if (auto *SI = dyn_cast<StoreInst>(I))
1360 Stores.push_back(SI);
1361 else
1362 return false;
1363 }
1364
1365 // We have identified all uses of GV into loads and stores. Now check if all
1366 // of them are known not to depend on the value of the global at the function
1367 // entry point. We do this by ensuring that every load is dominated by at
1368 // least one store.
1369 auto &DT = LookupDomTree(*const_cast<Function *>(F));
1370
1371 // The below check is quadratic. Check we're not going to do too many tests.
1372 // FIXME: Even though this will always have worst-case quadratic time, we
1373 // could put effort into minimizing the average time by putting stores that
1374 // have been shown to dominate at least one load at the beginning of the
1375 // Stores array, making subsequent dominance checks more likely to succeed
1376 // early.
1377 //
1378 // The threshold here is fairly large because global->local demotion is a
1379 // very powerful optimization should it fire.
1380 const unsigned Threshold = 100;
1381 if (Loads.size() * Stores.size() > Threshold)
1382 return false;
1383
1384 for (auto *L : Loads) {
1385 auto *LTy = L->getType();
1386 if (none_of(Stores, [&](const StoreInst *S) {
1387 auto *STy = S->getValueOperand()->getType();
1388 // The load is only dominated by the store if DomTree says so
1389 // and the number of bits loaded in L is less than or equal to
1390 // the number of bits stored in S.
1391 return DT.dominates(S, L) &&
1392 DL.getTypeStoreSize(LTy).getFixedValue() <=
1393 DL.getTypeStoreSize(STy).getFixedValue();
1394 }))
1395 return false;
1396 }
1397 // All loads have known dependences inside F, so the global can be localized.
1398 return true;
1399}
1400
1401// For a global variable with one store, if the store dominates any loads,
1402// those loads will always load the stored value (as opposed to the
1403// initializer), even in the presence of recursion.
1405 GlobalVariable *GV, const StoreInst *StoredOnceStore,
1406 function_ref<DominatorTree &(Function &)> LookupDomTree) {
1407 const Value *StoredOnceValue = StoredOnceStore->getValueOperand();
1408 // We can do this optimization for non-constants in nosync + norecurse
1409 // functions, but globals used in exactly one norecurse functions are already
1410 // promoted to an alloca.
1411 if (!isa<Constant>(StoredOnceValue))
1412 return false;
1413 const Function *F = StoredOnceStore->getFunction();
1415 for (User *U : GV->users()) {
1416 if (auto *LI = dyn_cast<LoadInst>(U)) {
1417 if (LI->getFunction() == F &&
1418 LI->getType() == StoredOnceValue->getType() && LI->isSimple())
1419 Loads.push_back(LI);
1420 }
1421 }
1422 // Only compute DT if we have any loads to examine.
1423 bool MadeChange = false;
1424 if (!Loads.empty()) {
1425 auto &DT = LookupDomTree(*const_cast<Function *>(F));
1426 for (auto *LI : Loads) {
1427 if (DT.dominates(StoredOnceStore, LI)) {
1428 LI->replaceAllUsesWith(const_cast<Value *>(StoredOnceValue));
1429 LI->eraseFromParent();
1430 MadeChange = true;
1431 }
1432 }
1433 }
1434 return MadeChange;
1435}
1436
1437/// Analyze the specified global variable and optimize
1438/// it if possible. If we make a change, return true.
1439static bool
1443 function_ref<DominatorTree &(Function &)> LookupDomTree) {
1444 auto &DL = GV->getParent()->getDataLayout();
1445 // If this is a first class global and has only one accessing function and
1446 // this function is non-recursive, we replace the global with a local alloca
1447 // in this function.
1448 //
1449 // NOTE: It doesn't make sense to promote non-single-value types since we
1450 // are just replacing static memory to stack memory.
1451 //
1452 // If the global is in different address space, don't bring it to stack.
1453 if (!GS.HasMultipleAccessingFunctions &&
1454 GS.AccessingFunction &&
1456 GV->getType()->getAddressSpace() == DL.getAllocaAddrSpace() &&
1457 !GV->isExternallyInitialized() &&
1458 GS.AccessingFunction->doesNotRecurse() &&
1459 isPointerValueDeadOnEntryToFunction(GS.AccessingFunction, GV,
1460 LookupDomTree)) {
1461 const DataLayout &DL = GV->getParent()->getDataLayout();
1462
1463 LLVM_DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV << "\n");
1464 Instruction &FirstI = const_cast<Instruction&>(*GS.AccessingFunction
1465 ->getEntryBlock().begin());
1466 Type *ElemTy = GV->getValueType();
1467 // FIXME: Pass Global's alignment when globals have alignment
1468 AllocaInst *Alloca = new AllocaInst(ElemTy, DL.getAllocaAddrSpace(), nullptr,
1469 GV->getName(), &FirstI);
1470 if (!isa<UndefValue>(GV->getInitializer()))
1471 new StoreInst(GV->getInitializer(), Alloca, &FirstI);
1472
1473 GV->replaceAllUsesWith(Alloca);
1474 GV->eraseFromParent();
1475 ++NumLocalized;
1476 return true;
1477 }
1478
1479 bool Changed = false;
1480
1481 // If the global is never loaded (but may be stored to), it is dead.
1482 // Delete it now.
1483 if (!GS.IsLoaded) {
1484 LLVM_DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV << "\n");
1485
1486 if (isLeakCheckerRoot(GV)) {
1487 // Delete any constant stores to the global.
1488 Changed = CleanupPointerRootUsers(GV, GetTLI);
1489 } else {
1490 // Delete any stores we can find to the global. We may not be able to
1491 // make it completely dead though.
1492 Changed = CleanupConstantGlobalUsers(GV, DL);
1493 }
1494
1495 // If the global is dead now, delete it.
1496 if (GV->use_empty()) {
1497 GV->eraseFromParent();
1498 ++NumDeleted;
1499 Changed = true;
1500 }
1501 return Changed;
1502
1503 }
1504 if (GS.StoredType <= GlobalStatus::InitializerStored) {
1505 LLVM_DEBUG(dbgs() << "MARKING CONSTANT: " << *GV << "\n");
1506
1507 // Don't actually mark a global constant if it's atomic because atomic loads
1508 // are implemented by a trivial cmpxchg in some edge-cases and that usually
1509 // requires write access to the variable even if it's not actually changed.
1510 if (GS.Ordering == AtomicOrdering::NotAtomic) {
1511 assert(!GV->isConstant() && "Expected a non-constant global");
1512 GV->setConstant(true);
1513 Changed = true;
1514 }
1515
1516 // Clean up any obviously simplifiable users now.
1517 Changed |= CleanupConstantGlobalUsers(GV, DL);
1518
1519 // If the global is dead now, just nuke it.
1520 if (GV->use_empty()) {
1521 LLVM_DEBUG(dbgs() << " *** Marking constant allowed us to simplify "
1522 << "all users and delete global!\n");
1523 GV->eraseFromParent();
1524 ++NumDeleted;
1525 return true;
1526 }
1527
1528 // Fall through to the next check; see if we can optimize further.
1529 ++NumMarked;
1530 }
1531 if (!GV->getInitializer()->getType()->isSingleValueType()) {
1532 const DataLayout &DL = GV->getParent()->getDataLayout();
1533 if (SRAGlobal(GV, DL))
1534 return true;
1535 }
1536 Value *StoredOnceValue = GS.getStoredOnceValue();
1537 if (GS.StoredType == GlobalStatus::StoredOnce && StoredOnceValue) {
1538 Function &StoreFn =
1539 const_cast<Function &>(*GS.StoredOnceStore->getFunction());
1540 bool CanHaveNonUndefGlobalInitializer =
1541 GetTTI(StoreFn).canHaveNonUndefGlobalInitializerInAddressSpace(
1542 GV->getType()->getAddressSpace());
1543 // If the initial value for the global was an undef value, and if only
1544 // one other value was stored into it, we can just change the
1545 // initializer to be the stored value, then delete all stores to the
1546 // global. This allows us to mark it constant.
1547 // This is restricted to address spaces that allow globals to have
1548 // initializers. NVPTX, for example, does not support initializers for
1549 // shared memory (AS 3).
1550 auto *SOVConstant = dyn_cast<Constant>(StoredOnceValue);
1551 if (SOVConstant && isa<UndefValue>(GV->getInitializer()) &&
1552 DL.getTypeAllocSize(SOVConstant->getType()) ==
1553 DL.getTypeAllocSize(GV->getValueType()) &&
1554 CanHaveNonUndefGlobalInitializer) {
1555 if (SOVConstant->getType() == GV->getValueType()) {
1556 // Change the initializer in place.
1557 GV->setInitializer(SOVConstant);
1558 } else {
1559 // Create a new global with adjusted type.
1560 auto *NGV = new GlobalVariable(
1561 *GV->getParent(), SOVConstant->getType(), GV->isConstant(),
1562 GV->getLinkage(), SOVConstant, "", GV, GV->getThreadLocalMode(),
1563 GV->getAddressSpace());
1564 NGV->takeName(GV);
1565 NGV->copyAttributesFrom(GV);
1566 GV->replaceAllUsesWith(NGV);
1567 GV->eraseFromParent();
1568 GV = NGV;
1569 }
1570
1571 // Clean up any obviously simplifiable users now.
1573
1574 if (GV->use_empty()) {
1575 LLVM_DEBUG(dbgs() << " *** Substituting initializer allowed us to "
1576 << "simplify all users and delete global!\n");
1577 GV->eraseFromParent();
1578 ++NumDeleted;
1579 }
1580 ++NumSubstitute;
1581 return true;
1582 }
1583
1584 // Try to optimize globals based on the knowledge that only one value
1585 // (besides its initializer) is ever stored to the global.
1586 if (optimizeOnceStoredGlobal(GV, StoredOnceValue, DL, GetTLI))
1587 return true;
1588
1589 // Try to forward the store to any loads. If we have more than one store, we
1590 // may have a store of the initializer between StoredOnceStore and a load.
1591 if (GS.NumStores == 1)
1592 if (forwardStoredOnceStore(GV, GS.StoredOnceStore, LookupDomTree))
1593 return true;
1594
1595 // Otherwise, if the global was not a boolean, we can shrink it to be a
1596 // boolean. Skip this optimization for AS that doesn't allow an initializer.
1597 if (SOVConstant && GS.Ordering == AtomicOrdering::NotAtomic &&
1598 (!isa<UndefValue>(GV->getInitializer()) ||
1599 CanHaveNonUndefGlobalInitializer)) {
1600 if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) {
1601 ++NumShrunkToBool;
1602 return true;
1603 }
1604 }
1605 }
1606
1607 return Changed;
1608}
1609
1610/// Analyze the specified global variable and optimize it if possible. If we
1611/// make a change, return true.
1612static bool
1616 function_ref<DominatorTree &(Function &)> LookupDomTree) {
1617 if (GV.getName().startswith("llvm."))
1618 return false;
1619
1620 GlobalStatus GS;
1621
1622 if (GlobalStatus::analyzeGlobal(&GV, GS))
1623 return false;
1624
1625 bool Changed = false;
1626 if (!GS.IsCompared && !GV.hasGlobalUnnamedAddr()) {
1627 auto NewUnnamedAddr = GV.hasLocalLinkage() ? GlobalValue::UnnamedAddr::Global
1628 : GlobalValue::UnnamedAddr::Local;
1629 if (NewUnnamedAddr != GV.getUnnamedAddr()) {
1630 GV.setUnnamedAddr(NewUnnamedAddr);
1631 NumUnnamed++;
1632 Changed = true;
1633 }
1634 }
1635
1636 // Do more involved optimizations if the global is internal.
1637 if (!GV.hasLocalLinkage())
1638 return Changed;
1639
1640 auto *GVar = dyn_cast<GlobalVariable>(&GV);
1641 if (!GVar)
1642 return Changed;
1643
1644 if (GVar->isConstant() || !GVar->hasInitializer())
1645 return Changed;
1646
1647 return processInternalGlobal(GVar, GS, GetTTI, GetTLI, LookupDomTree) ||
1648 Changed;
1649}
1650
1651/// Walk all of the direct calls of the specified function, changing them to
1652/// FastCC.
1654 for (User *U : F->users()) {
1655 if (isa<BlockAddress>(U))
1656 continue;
1657 cast<CallBase>(U)->setCallingConv(CallingConv::Fast);
1658 }
1659}
1660
1663 unsigned AttrIndex;
1664 if (Attrs.hasAttrSomewhere(A, &AttrIndex))
1665 return Attrs.removeAttributeAtIndex(C, AttrIndex, A);
1666 return Attrs;
1667}
1668
1670 F->setAttributes(StripAttr(F->getContext(), F->getAttributes(), A));
1671 for (User *U : F->users()) {
1672 if (isa<BlockAddress>(U))
1673 continue;
1674 CallBase *CB = cast<CallBase>(U);
1675 CB->setAttributes(StripAttr(F->getContext(), CB->getAttributes(), A));
1676 }
1677}
1678
1679/// Return true if this is a calling convention that we'd like to change. The
1680/// idea here is that we don't want to mess with the convention if the user
1681/// explicitly requested something with performance implications like coldcc,
1682/// GHC, or anyregcc.
1684 CallingConv::ID CC = F->getCallingConv();
1685
1686 // FIXME: Is it worth transforming x86_stdcallcc and x86_fastcallcc?
1688 return false;
1689
1690 // FIXME: Change CC for the whole chain of musttail calls when possible.
1691 //
1692 // Can't change CC of the function that either has musttail calls, or is a
1693 // musttail callee itself
1694 for (User *U : F->users()) {
1695 if (isa<BlockAddress>(U))
1696 continue;
1697 CallInst* CI = dyn_cast<CallInst>(U);
1698 if (!CI)
1699 continue;
1700
1701 if (CI->isMustTailCall())
1702 return false;
1703 }
1704
1705 for (BasicBlock &BB : *F)
1706 if (BB.getTerminatingMustTailCall())
1707 return false;
1708
1709 return true;
1710}
1711
1712/// Return true if the block containing the call site has a BlockFrequency of
1713/// less than ColdCCRelFreq% of the entry block.
1714static bool isColdCallSite(CallBase &CB, BlockFrequencyInfo &CallerBFI) {
1715 const BranchProbability ColdProb(ColdCCRelFreq, 100);
1716 auto *CallSiteBB = CB.getParent();
1717 auto CallSiteFreq = CallerBFI.getBlockFreq(CallSiteBB);
1718 auto CallerEntryFreq =
1719 CallerBFI.getBlockFreq(&(CB.getCaller()->getEntryBlock()));
1720 return CallSiteFreq < CallerEntryFreq * ColdProb;
1721}
1722
1723// This function checks if the input function F is cold at all call sites. It
1724// also looks each call site's containing function, returning false if the
1725// caller function contains other non cold calls. The input vector AllCallsCold
1726// contains a list of functions that only have call sites in cold blocks.
1727static bool
1730 const std::vector<Function *> &AllCallsCold) {
1731
1732 if (F.user_empty())
1733 return false;
1734
1735 for (User *U : F.users()) {
1736 if (isa<BlockAddress>(U))
1737 continue;
1738
1739 CallBase &CB = cast<CallBase>(*U);
1740 Function *CallerFunc = CB.getParent()->getParent();
1741 BlockFrequencyInfo &CallerBFI = GetBFI(*CallerFunc);
1742 if (!isColdCallSite(CB, CallerBFI))
1743 return false;
1744 if (!llvm::is_contained(AllCallsCold, CallerFunc))
1745 return false;
1746 }
1747 return true;
1748}
1749
1751 for (User *U : F->users()) {
1752 if (isa<BlockAddress>(U))
1753 continue;
1754 cast<CallBase>(U)->setCallingConv(CallingConv::Cold);
1755 }
1756}
1757
1758// This function iterates over all the call instructions in the input Function
1759// and checks that all call sites are in cold blocks and are allowed to use the
1760// coldcc calling convention.
1761static bool
1764 for (BasicBlock &BB : F) {
1765 for (Instruction &I : BB) {
1766 if (CallInst *CI = dyn_cast<CallInst>(&I)) {
1767 // Skip over isline asm instructions since they aren't function calls.
1768 if (CI->isInlineAsm())
1769 continue;
1770 Function *CalledFn = CI->getCalledFunction();
1771 if (!CalledFn)
1772 return false;
1773 // Skip over intrinsics since they won't remain as function calls.
1774 // Important to do this check before the linkage check below so we
1775 // won't bail out on debug intrinsics, possibly making the generated
1776 // code dependent on the presence of debug info.
1777 if (CalledFn->getIntrinsicID() != Intrinsic::not_intrinsic)
1778 continue;
1779 if (!CalledFn->hasLocalLinkage())
1780 return false;
1781 // Check if it's valid to use coldcc calling convention.
1782 if (!hasChangeableCC(CalledFn) || CalledFn->isVarArg() ||
1783 CalledFn->hasAddressTaken())
1784 return false;
1785 BlockFrequencyInfo &CallerBFI = GetBFI(F);
1786 if (!isColdCallSite(*CI, CallerBFI))
1787 return false;
1788 }
1789 }
1790 }
1791 return true;
1792}
1793
1795 for (User *U : F->users()) {
1796 CallBase *CB = dyn_cast<CallBase>(U);
1797 if (!CB) {
1798 assert(isa<BlockAddress>(U) &&
1799 "Expected either CallBase or BlockAddress");
1800 continue;
1801 }
1802 if (CB->isMustTailCall())
1803 return true;
1804 }
1805 return false;
1806}
1807
1809 for (User *U : F->users())
1810 if (isa<InvokeInst>(U))
1811 return true;
1812 return false;
1813}
1814
1816 RemoveAttribute(F, Attribute::Preallocated);
1817
1818 auto *M = F->getParent();
1819
1820 IRBuilder<> Builder(M->getContext());
1821
1822 // Cannot modify users() while iterating over it, so make a copy.
1823 SmallVector<User *, 4> PreallocatedCalls(F->users());
1824 for (User *U : PreallocatedCalls) {
1825 CallBase *CB = dyn_cast<CallBase>(U);
1826 if (!CB)
1827 continue;
1828
1829 assert(
1830 !CB->isMustTailCall() &&
1831 "Shouldn't call RemotePreallocated() on a musttail preallocated call");
1832 // Create copy of call without "preallocated" operand bundle.
1834 CB->getOperandBundlesAsDefs(OpBundles);
1835 CallBase *PreallocatedSetup = nullptr;
1836 for (auto *It = OpBundles.begin(); It != OpBundles.end(); ++It) {
1837 if (It->getTag() == "preallocated") {
1838 PreallocatedSetup = cast<CallBase>(*It->input_begin());
1839 OpBundles.erase(It);
1840 break;
1841 }
1842 }
1843 assert(PreallocatedSetup && "Did not find preallocated bundle");
1844 uint64_t ArgCount =
1845 cast<ConstantInt>(PreallocatedSetup->getArgOperand(0))->getZExtValue();
1846
1847 assert((isa<CallInst>(CB) || isa<InvokeInst>(CB)) &&
1848 "Unknown indirect call type");
1849 CallBase *NewCB = CallBase::Create(CB, OpBundles, CB);
1850 CB->replaceAllUsesWith(NewCB);
1851 NewCB->takeName(CB);
1852 CB->eraseFromParent();
1853
1854 Builder.SetInsertPoint(PreallocatedSetup);
1855 auto *StackSave = Builder.CreateStackSave();
1856 Builder.SetInsertPoint(NewCB->getNextNonDebugInstruction());
1857 Builder.CreateStackRestore(StackSave);
1858
1859 // Replace @llvm.call.preallocated.arg() with alloca.
1860 // Cannot modify users() while iterating over it, so make a copy.
1861 // @llvm.call.preallocated.arg() can be called with the same index multiple
1862 // times. So for each @llvm.call.preallocated.arg(), we see if we have
1863 // already created a Value* for the index, and if not, create an alloca and
1864 // bitcast right after the @llvm.call.preallocated.setup() so that it
1865 // dominates all uses.
1866 SmallVector<Value *, 2> ArgAllocas(ArgCount);
1867 SmallVector<User *, 2> PreallocatedArgs(PreallocatedSetup->users());
1868 for (auto *User : PreallocatedArgs) {
1869 auto *UseCall = cast<CallBase>(User);
1870 assert(UseCall->getCalledFunction()->getIntrinsicID() ==
1871 Intrinsic::call_preallocated_arg &&
1872 "preallocated token use was not a llvm.call.preallocated.arg");
1873 uint64_t AllocArgIndex =
1874 cast<ConstantInt>(UseCall->getArgOperand(1))->getZExtValue();
1875 Value *AllocaReplacement = ArgAllocas[AllocArgIndex];
1876 if (!AllocaReplacement) {
1877 auto AddressSpace = UseCall->getType()->getPointerAddressSpace();
1878 auto *ArgType =
1879 UseCall->getFnAttr(Attribute::Preallocated).getValueAsType();
1880 auto *InsertBefore = PreallocatedSetup->getNextNonDebugInstruction();
1881 Builder.SetInsertPoint(InsertBefore);
1882 auto *Alloca =
1883 Builder.CreateAlloca(ArgType, AddressSpace, nullptr, "paarg");
1884 ArgAllocas[AllocArgIndex] = Alloca;
1885 AllocaReplacement = Alloca;
1886 }
1887
1888 UseCall->replaceAllUsesWith(AllocaReplacement);
1889 UseCall->eraseFromParent();
1890 }
1891 // Remove @llvm.call.preallocated.setup().
1892 cast<Instruction>(PreallocatedSetup)->eraseFromParent();
1893 }
1894}
1895
1896static bool
1901 function_ref<DominatorTree &(Function &)> LookupDomTree,
1902 SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats,
1903 function_ref<void(Function &F)> ChangedCFGCallback,
1904 function_ref<void(Function &F)> DeleteFnCallback) {
1905
1906 bool Changed = false;
1907
1908 std::vector<Function *> AllCallsCold;
1910 if (hasOnlyColdCalls(F, GetBFI))
1911 AllCallsCold.push_back(&F);
1912
1913 // Optimize functions.
1915 // Don't perform global opt pass on naked functions; we don't want fast
1916 // calling conventions for naked functions.
1917 if (F.hasFnAttribute(Attribute::Naked))
1918 continue;
1919
1920 // Functions without names cannot be referenced outside this module.
1921 if (!F.hasName() && !F.isDeclaration() && !F.hasLocalLinkage())
1922 F.setLinkage(GlobalValue::InternalLinkage);
1923
1924 if (deleteIfDead(F, NotDiscardableComdats, DeleteFnCallback)) {
1925 Changed = true;
1926 continue;
1927 }
1928
1929 // LLVM's definition of dominance allows instructions that are cyclic
1930 // in unreachable blocks, e.g.:
1931 // %pat = select i1 %condition, @global, i16* %pat
1932 // because any instruction dominates an instruction in a block that's
1933 // not reachable from entry.
1934 // So, remove unreachable blocks from the function, because a) there's
1935 // no point in analyzing them and b) GlobalOpt should otherwise grow
1936 // some more complicated logic to break these cycles.
1937 // Notify the analysis manager that we've modified the function's CFG.
1938 if (!F.isDeclaration()) {
1940 Changed = true;
1941 ChangedCFGCallback(F);
1942 }
1943 }
1944
1945 Changed |= processGlobal(F, GetTTI, GetTLI, LookupDomTree);
1946
1947 if (!F.hasLocalLinkage())
1948 continue;
1949
1950 // If we have an inalloca parameter that we can safely remove the
1951 // inalloca attribute from, do so. This unlocks optimizations that
1952 // wouldn't be safe in the presence of inalloca.
1953 // FIXME: We should also hoist alloca affected by this to the entry
1954 // block if possible.
1955 if (F.getAttributes().hasAttrSomewhere(Attribute::InAlloca) &&
1956 !F.hasAddressTaken() && !hasMustTailCallers(&F) && !F.isVarArg()) {
1957 RemoveAttribute(&F, Attribute::InAlloca);
1958 Changed = true;
1959 }
1960
1961 // FIXME: handle invokes
1962 // FIXME: handle musttail
1963 if (F.getAttributes().hasAttrSomewhere(Attribute::Preallocated)) {
1964 if (!F.hasAddressTaken() && !hasMustTailCallers(&F) &&
1965 !hasInvokeCallers(&F)) {
1967 Changed = true;
1968 }
1969 continue;
1970 }
1971
1972 if (hasChangeableCC(&F) && !F.isVarArg() && !F.hasAddressTaken()) {
1973 NumInternalFunc++;
1974 TargetTransformInfo &TTI = GetTTI(F);
1975 // Change the calling convention to coldcc if either stress testing is
1976 // enabled or the target would like to use coldcc on functions which are
1977 // cold at all call sites and the callers contain no other non coldcc
1978 // calls.
1981 isValidCandidateForColdCC(F, GetBFI, AllCallsCold))) {
1982 F.setCallingConv(CallingConv::Cold);
1984 Changed = true;
1985 NumColdCC++;
1986 }
1987 }
1988
1989 if (hasChangeableCC(&F) && !F.isVarArg() && !F.hasAddressTaken()) {
1990 // If this function has a calling convention worth changing, is not a
1991 // varargs function, and is only called directly, promote it to use the
1992 // Fast calling convention.
1993 F.setCallingConv(CallingConv::Fast);
1995 ++NumFastCallFns;
1996 Changed = true;
1997 }
1998
1999 if (F.getAttributes().hasAttrSomewhere(Attribute::Nest) &&
2000 !F.hasAddressTaken()) {
2001 // The function is not used by a trampoline intrinsic, so it is safe
2002 // to remove the 'nest' attribute.
2003 RemoveAttribute(&F, Attribute::Nest);
2004 ++NumNestRemoved;
2005 Changed = true;
2006 }
2007 }
2008 return Changed;
2009}
2010
2011static bool
2015 function_ref<DominatorTree &(Function &)> LookupDomTree,
2016 SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
2017 bool Changed = false;
2018
2019 for (GlobalVariable &GV : llvm::make_early_inc_range(M.globals())) {
2020 // Global variables without names cannot be referenced outside this module.
2021 if (!GV.hasName() && !GV.isDeclaration() && !GV.hasLocalLinkage())
2023 // Simplify the initializer.
2024 if (GV.hasInitializer())
2025 if (auto *C = dyn_cast<Constant>(GV.getInitializer())) {
2026 auto &DL = M.getDataLayout();
2027 // TLI is not used in the case of a Constant, so use default nullptr
2028 // for that optional parameter, since we don't have a Function to
2029 // provide GetTLI anyway.
2030 Constant *New = ConstantFoldConstant(C, DL, /*TLI*/ nullptr);
2031 if (New != C)
2032 GV.setInitializer(New);
2033 }
2034
2035 if (deleteIfDead(GV, NotDiscardableComdats)) {
2036 Changed = true;
2037 continue;
2038 }
2039
2040 Changed |= processGlobal(GV, GetTTI, GetTLI, LookupDomTree);
2041 }
2042 return Changed;
2043}
2044
2045/// Evaluate static constructors in the function, if we can. Return true if we
2046/// can, false otherwise.
2048 TargetLibraryInfo *TLI) {
2049 // Skip external functions.
2050 if (F->isDeclaration())
2051 return false;
2052 // Call the function.
2053 Evaluator Eval(DL, TLI);
2054 Constant *RetValDummy;
2055 bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy,
2057
2058 if (EvalSuccess) {
2059 ++NumCtorsEvaluated;
2060
2061 // We succeeded at evaluation: commit the result.
2062 auto NewInitializers = Eval.getMutatedInitializers();
2063 LLVM_DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
2064 << F->getName() << "' to " << NewInitializers.size()
2065 << " stores.\n");
2066 for (const auto &Pair : NewInitializers)
2067 Pair.first->setInitializer(Pair.second);
2068 for (GlobalVariable *GV : Eval.getInvariants())
2069 GV->setConstant(true);
2070 }
2071
2072 return EvalSuccess;
2073}
2074
2075static int compareNames(Constant *const *A, Constant *const *B) {
2076 Value *AStripped = (*A)->stripPointerCasts();
2077 Value *BStripped = (*B)->stripPointerCasts();
2078 return AStripped->getName().compare(BStripped->getName());
2079}
2080
2083 if (Init.empty()) {
2084 V.eraseFromParent();
2085 return;
2086 }
2087
2088 // Get address space of pointers in the array of pointers.
2089 const Type *UsedArrayType = V.getValueType();
2090 const auto *VAT = cast<ArrayType>(UsedArrayType);
2091 const auto *VEPT = cast<PointerType>(VAT->getArrayElementType());
2092
2093 // Type of pointer to the array of pointers.
2094 PointerType *PtrTy =
2095 PointerType::get(V.getContext(), VEPT->getAddressSpace());
2096
2098 for (GlobalValue *GV : Init) {
2100 UsedArray.push_back(Cast);
2101 }
2102
2103 // Sort to get deterministic order.
2104 array_pod_sort(UsedArray.begin(), UsedArray.end(), compareNames);
2105 ArrayType *ATy = ArrayType::get(PtrTy, UsedArray.size());
2106
2107 Module *M = V.getParent();
2108 V.removeFromParent();
2109 GlobalVariable *NV =
2111 ConstantArray::get(ATy, UsedArray), "");
2112 NV->takeName(&V);
2113 NV->setSection("llvm.metadata");
2114 delete &V;
2115}
2116
2117namespace {
2118
2119/// An easy to access representation of llvm.used and llvm.compiler.used.
2120class LLVMUsed {
2122 SmallPtrSet<GlobalValue *, 4> CompilerUsed;
2123 GlobalVariable *UsedV;
2124 GlobalVariable *CompilerUsedV;
2125
2126public:
2127 LLVMUsed(Module &M) {
2129 UsedV = collectUsedGlobalVariables(M, Vec, false);
2130 Used = {Vec.begin(), Vec.end()};
2131 Vec.clear();
2132 CompilerUsedV = collectUsedGlobalVariables(M, Vec, true);
2133 CompilerUsed = {Vec.begin(), Vec.end()};
2134 }
2135
2137 using used_iterator_range = iterator_range<iterator>;
2138
2139 iterator usedBegin() { return Used.begin(); }
2140 iterator usedEnd() { return Used.end(); }
2141
2142 used_iterator_range used() {
2143 return used_iterator_range(usedBegin(), usedEnd());
2144 }
2145
2146 iterator compilerUsedBegin() { return CompilerUsed.begin(); }
2147 iterator compilerUsedEnd() { return CompilerUsed.end(); }
2148
2149 used_iterator_range compilerUsed() {
2150 return used_iterator_range(compilerUsedBegin(), compilerUsedEnd());
2151 }
2152
2153 bool usedCount(GlobalValue *GV) const { return Used.count(GV); }
2154
2155 bool compilerUsedCount(GlobalValue *GV) const {
2156 return CompilerUsed.count(GV);
2157 }
2158
2159 bool usedErase(GlobalValue *GV) { return Used.erase(GV); }
2160 bool compilerUsedErase(GlobalValue *GV) { return CompilerUsed.erase(GV); }
2161 bool usedInsert(GlobalValue *GV) { return Used.insert(GV).second; }
2162
2163 bool compilerUsedInsert(GlobalValue *GV) {
2164 return CompilerUsed.insert(GV).second;
2165 }
2166
2167 void syncVariablesAndSets() {
2168 if (UsedV)
2169 setUsedInitializer(*UsedV, Used);
2170 if (CompilerUsedV)
2171 setUsedInitializer(*CompilerUsedV, CompilerUsed);
2172 }
2173};
2174
2175} // end anonymous namespace
2176
2177static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U) {
2178 if (GA.use_empty()) // No use at all.
2179 return false;
2180
2181 assert((!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) &&
2182 "We should have removed the duplicated "
2183 "element from llvm.compiler.used");
2184 if (!GA.hasOneUse())
2185 // Strictly more than one use. So at least one is not in llvm.used and
2186 // llvm.compiler.used.
2187 return true;
2188
2189 // Exactly one use. Check if it is in llvm.used or llvm.compiler.used.
2190 return !U.usedCount(&GA) && !U.compilerUsedCount(&GA);
2191}
2192
2193static bool mayHaveOtherReferences(GlobalValue &GV, const LLVMUsed &U) {
2194 if (!GV.hasLocalLinkage())
2195 return true;
2196
2197 return U.usedCount(&GV) || U.compilerUsedCount(&GV);
2198}
2199
2200static bool hasUsesToReplace(GlobalAlias &GA, const LLVMUsed &U,
2201 bool &RenameTarget) {
2202 RenameTarget = false;
2203 bool Ret = false;
2204 if (hasUseOtherThanLLVMUsed(GA, U))
2205 Ret = true;
2206
2207 // If the alias is externally visible, we may still be able to simplify it.
2208 if (!mayHaveOtherReferences(GA, U))
2209 return Ret;
2210
2211 // If the aliasee has internal linkage and no other references (e.g.,
2212 // @llvm.used, @llvm.compiler.used), give it the name and linkage of the
2213 // alias, and delete the alias. This turns:
2214 // define internal ... @f(...)
2215 // @a = alias ... @f
2216 // into:
2217 // define ... @a(...)
2218 Constant *Aliasee = GA.getAliasee();
2219 GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts());
2221 return Ret;
2222
2223 RenameTarget = true;
2224 return true;
2225}
2226
2227static bool
2229 SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
2230 bool Changed = false;
2231 LLVMUsed Used(M);
2232
2233 for (GlobalValue *GV : Used.used())
2234 Used.compilerUsedErase(GV);
2235
2236 // Return whether GV is explicitly or implicitly dso_local and not replaceable
2237 // by another definition in the current linkage unit.
2238 auto IsModuleLocal = [](GlobalValue &GV) {
2240 (GV.isDSOLocal() || GV.isImplicitDSOLocal());
2241 };
2242
2243 for (GlobalAlias &J : llvm::make_early_inc_range(M.aliases())) {
2244 // Aliases without names cannot be referenced outside this module.
2245 if (!J.hasName() && !J.isDeclaration() && !J.hasLocalLinkage())
2246 J.setLinkage(GlobalValue::InternalLinkage);
2247
2248 if (deleteIfDead(J, NotDiscardableComdats)) {
2249 Changed = true;
2250 continue;
2251 }
2252
2253 // If the alias can change at link time, nothing can be done - bail out.
2254 if (!IsModuleLocal(J))
2255 continue;
2256
2257 Constant *Aliasee = J.getAliasee();
2258 GlobalValue *Target = dyn_cast<GlobalValue>(Aliasee->stripPointerCasts());
2259 // We can't trivially replace the alias with the aliasee if the aliasee is
2260 // non-trivial in some way. We also can't replace the alias with the aliasee
2261 // if the aliasee may be preemptible at runtime. On ELF, a non-preemptible
2262 // alias can be used to access the definition as if preemption did not
2263 // happen.
2264 // TODO: Try to handle non-zero GEPs of local aliasees.
2265 if (!Target || !IsModuleLocal(*Target))
2266 continue;
2267
2268 Target->removeDeadConstantUsers();
2269
2270 // Make all users of the alias use the aliasee instead.
2271 bool RenameTarget;
2272 if (!hasUsesToReplace(J, Used, RenameTarget))
2273 continue;
2274
2275 J.replaceAllUsesWith(Aliasee);
2276 ++NumAliasesResolved;
2277 Changed = true;
2278
2279 if (RenameTarget) {
2280 // Give the aliasee the name, linkage and other attributes of the alias.
2281 Target->takeName(&J);
2282 Target->setLinkage(J.getLinkage());
2283 Target->setDSOLocal(J.isDSOLocal());
2284 Target->setVisibility(J.getVisibility());
2285 Target->setDLLStorageClass(J.getDLLStorageClass());
2286
2287 if (Used.usedErase(&J))
2288 Used.usedInsert(Target);
2289
2290 if (Used.compilerUsedErase(&J))
2291 Used.compilerUsedInsert(Target);
2292 } else if (mayHaveOtherReferences(J, Used))
2293 continue;
2294
2295 // Delete the alias.
2296 M.eraseAlias(&J);
2297 ++NumAliasesRemoved;
2298 Changed = true;
2299 }
2300
2301 Used.syncVariablesAndSets();
2302
2303 return Changed;
2304}
2305
2306static Function *
2308 // Hack to get a default TLI before we have actual Function.
2309 auto FuncIter = M.begin();
2310 if (FuncIter == M.end())
2311 return nullptr;
2312 auto *TLI = &GetTLI(*FuncIter);
2313
2314 LibFunc F = LibFunc_cxa_atexit;
2315 if (!TLI->has(F))
2316 return nullptr;
2317
2318 Function *Fn = M.getFunction(TLI->getName(F));
2319 if (!Fn)
2320 return nullptr;
2321
2322 // Now get the actual TLI for Fn.
2323 TLI = &GetTLI(*Fn);
2324
2325 // Make sure that the function has the correct prototype.
2326 if (!TLI->getLibFunc(*Fn, F) || F != LibFunc_cxa_atexit)
2327 return nullptr;
2328
2329 return Fn;
2330}
2331
2332/// Returns whether the given function is an empty C++ destructor and can
2333/// therefore be eliminated.
2334/// Note that we assume that other optimization passes have already simplified
2335/// the code so we simply check for 'ret'.
2336static bool cxxDtorIsEmpty(const Function &Fn) {
2337 // FIXME: We could eliminate C++ destructors if they're readonly/readnone and
2338 // nounwind, but that doesn't seem worth doing.
2339 if (Fn.isDeclaration())
2340 return false;
2341
2342 for (const auto &I : Fn.getEntryBlock()) {
2343 if (I.isDebugOrPseudoInst())
2344 continue;
2345 if (isa<ReturnInst>(I))
2346 return true;
2347 break;
2348 }
2349 return false;
2350}
2351
2352static bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) {
2353 /// Itanium C++ ABI p3.3.5:
2354 ///
2355 /// After constructing a global (or local static) object, that will require
2356 /// destruction on exit, a termination function is registered as follows:
2357 ///
2358 /// extern "C" int __cxa_atexit ( void (*f)(void *), void *p, void *d );
2359 ///
2360 /// This registration, e.g. __cxa_atexit(f,p,d), is intended to cause the
2361 /// call f(p) when DSO d is unloaded, before all such termination calls
2362 /// registered before this one. It returns zero if registration is
2363 /// successful, nonzero on failure.
2364
2365 // This pass will look for calls to __cxa_atexit where the function is trivial
2366 // and remove them.
2367 bool Changed = false;
2368
2369 for (User *U : llvm::make_early_inc_range(CXAAtExitFn->users())) {
2370 // We're only interested in calls. Theoretically, we could handle invoke
2371 // instructions as well, but neither llvm-gcc nor clang generate invokes
2372 // to __cxa_atexit.
2373 CallInst *CI = dyn_cast<CallInst>(U);
2374 if (!CI)
2375 continue;
2376
2377 Function *DtorFn =
2378 dyn_cast<Function>(CI->getArgOperand(0)->stripPointerCasts());
2379 if (!DtorFn || !cxxDtorIsEmpty(*DtorFn))
2380 continue;
2381
2382 // Just remove the call.
2384 CI->eraseFromParent();
2385
2386 ++NumCXXDtorsRemoved;
2387
2388 Changed |= true;
2389 }
2390
2391 return Changed;
2392}
2393
2394static bool
2399 function_ref<DominatorTree &(Function &)> LookupDomTree,
2400 function_ref<void(Function &F)> ChangedCFGCallback,
2401 function_ref<void(Function &F)> DeleteFnCallback) {
2402 SmallPtrSet<const Comdat *, 8> NotDiscardableComdats;
2403 bool Changed = false;
2404 bool LocalChange = true;
2405 std::optional<uint32_t> FirstNotFullyEvaluatedPriority;
2406
2407 while (LocalChange) {
2408 LocalChange = false;
2409
2410 NotDiscardableComdats.clear();
2411 for (const GlobalVariable &GV : M.globals())
2412 if (const Comdat *C = GV.getComdat())
2413 if (!GV.isDiscardableIfUnused() || !GV.use_empty())
2414 NotDiscardableComdats.insert(C);
2415 for (Function &F : M)
2416 if (const Comdat *C = F.getComdat())
2417 if (!F.isDefTriviallyDead())
2418 NotDiscardableComdats.insert(C);
2419 for (GlobalAlias &GA : M.aliases())
2420 if (const Comdat *C = GA.getComdat())
2421 if (!GA.isDiscardableIfUnused() || !GA.use_empty())
2422 NotDiscardableComdats.insert(C);
2423
2424 // Delete functions that are trivially dead, ccc -> fastcc
2425 LocalChange |= OptimizeFunctions(M, GetTLI, GetTTI, GetBFI, LookupDomTree,
2426 NotDiscardableComdats, ChangedCFGCallback,
2427 DeleteFnCallback);
2428
2429 // Optimize global_ctors list.
2430 LocalChange |=
2431 optimizeGlobalCtorsList(M, [&](uint32_t Priority, Function *F) {
2432 if (FirstNotFullyEvaluatedPriority &&
2433 *FirstNotFullyEvaluatedPriority != Priority)
2434 return false;
2435 bool Evaluated = EvaluateStaticConstructor(F, DL, &GetTLI(*F));
2436 if (!Evaluated)
2437 FirstNotFullyEvaluatedPriority = Priority;
2438 return Evaluated;
2439 });
2440
2441 // Optimize non-address-taken globals.
2442 LocalChange |= OptimizeGlobalVars(M, GetTTI, GetTLI, LookupDomTree,
2443 NotDiscardableComdats);
2444
2445 // Resolve aliases, when possible.
2446 LocalChange |= OptimizeGlobalAliases(M, NotDiscardableComdats);
2447
2448 // Try to remove trivial global destructors if they are not removed
2449 // already.
2450 Function *CXAAtExitFn = FindCXAAtExit(M, GetTLI);
2451 if (CXAAtExitFn)
2452 LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn);
2453
2454 Changed |= LocalChange;
2455 }
2456
2457 // TODO: Move all global ctors functions to the end of the module for code
2458 // layout.
2459
2460 return Changed;
2461}
2462
2464 auto &DL = M.getDataLayout();
2465 auto &FAM =
2467 auto LookupDomTree = [&FAM](Function &F) -> DominatorTree &{
2469 };
2470 auto GetTLI = [&FAM](Function &F) -> TargetLibraryInfo & {
2472 };
2473 auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {
2475 };
2476
2477 auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & {
2479 };
2480 auto ChangedCFGCallback = [&FAM](Function &F) {
2482 };
2483 auto DeleteFnCallback = [&FAM](Function &F) { FAM.clear(F, F.getName()); };
2484
2485 if (!optimizeGlobalsInModule(M, DL, GetTLI, GetTTI, GetBFI, LookupDomTree,
2486 ChangedCFGCallback, DeleteFnCallback))
2487 return PreservedAnalyses::all();
2488
2490 // We made sure to clear analyses for deleted functions.
2492 // The only place we modify the CFG is when calling
2493 // removeUnreachableBlocks(), but there we make sure to invalidate analyses
2494 // for modified functions.
2496 return PA;
2497}
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:2307
static bool optimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, const DataLayout &DL, function_ref< TargetLibraryInfo &(Function &)> GetTLI)
Definition: GlobalOpt.cpp:1111
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:1064
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:881
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:697
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:2336
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:903
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:1020
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:1897
static void RemoveAttribute(Function *F, Attribute::AttrKind A)
Definition: GlobalOpt.cpp:1669
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:1305
static void RemovePreallocated(Function *F)
Definition: GlobalOpt.cpp:1815
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:1613
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:1714
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:2228
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:1147
static void ChangeCalleesToFastCall(Function *F)
Walk all of the direct calls of the specified function, changing them to FastCC.
Definition: GlobalOpt.cpp:1653
static bool hasMustTailCallers(Function *F)
Definition: GlobalOpt.cpp:1794
static bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn)
Definition: GlobalOpt.cpp:2352
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:2012
static void allUsesOfLoadAndStores(GlobalVariable *GV, SmallVector< Value *, 4 > &Uses)
Get all the loads/store uses for global variable GV.
Definition: GlobalOpt.cpp:727
static bool mayHaveOtherReferences(GlobalValue &GV, const LLVMUsed &U)
Definition: GlobalOpt.cpp:2193
static bool hasChangeableCC(Function *F)
Return true if this is a calling convention that we'd like to change.
Definition: GlobalOpt.cpp:1683
static void changeCallSitesToColdCC(Function *F)
Definition: GlobalOpt.cpp:1750
static AttributeList StripAttr(LLVMContext &C, AttributeList Attrs, Attribute::AttrKind A)
Definition: GlobalOpt.cpp:1661
static bool hasInvokeCallers(Function *F)
Definition: GlobalOpt.cpp:1808
static void setUsedInitializer(GlobalVariable &V, const SmallPtrSetImpl< GlobalValue * > &Init)
Definition: GlobalOpt.cpp:2081
static bool hasOnlyColdCalls(Function &F, function_ref< BlockFrequencyInfo &(Function &)> GetBFI)
Definition: GlobalOpt.cpp:1762
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:816
static bool isValidCandidateForColdCC(Function &F, function_ref< BlockFrequencyInfo &(Function &)> GetBFI, const std::vector< Function * > &AllCallsCold)
Definition: GlobalOpt.cpp:1728
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:2395
static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL, TargetLibraryInfo *TLI)
Evaluate static constructors in the function, if we can.
Definition: GlobalOpt.cpp:2047
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:1404
static int compareNames(Constant *const *A, Constant *const *B)
Definition: GlobalOpt.cpp:2075
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:1335
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:1440
static bool hasUsesToReplace(GlobalAlias &GA, const LLVMUsed &U, bool &RenameTarget)
Definition: GlobalOpt.cpp:2200
static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV)
Definition: GlobalOpt.cpp:746
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:2177
Hexagon Common GEP
#define _
IRTranslator LLVM IR MI
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
#define P(N)
FunctionAnalysisManager FAM
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file 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:76
This class represents a conversion between pointers from one address space to another.
an instruction to allocate memory on the stack
Definition: Instructions.h:58
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h: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:84
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)
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:1493
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:1489
Function * getCaller()
Helper to get the caller (the parent function).
This class represents a function call, abstracting a target machine's calling convention.
bool isMustTailCall() const
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h: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 * 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:1225
static Constant * getAddrSpaceCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:2225
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:840
static ConstantInt * getBool(LLVMContext &Context, bool V)
Definition: Constants.cpp:847
This is an important base class in LLVM.
Definition: Constant.h:41
const Constant * stripPointerCasts() const
Definition: Constant.h:213
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:708
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:356
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:76
DWARF expression.
bool extractIfOffset(int64_t &Offset) const
If this is a constant offset, extract it.
static std::optional< DIExpression * > createFragmentExpression(const DIExpression *Expr, unsigned OffsetInBits, unsigned SizeInBits)
Create a DIExpression to describe one part of an aggregate variable that is fragmented across multipl...
static DIExpression * prependOpcodes(const DIExpression *Expr, SmallVectorImpl< uint64_t > &Ops, bool StackValue=false, bool EntryValue=false)
Prepend DIExpr with the given opcodes and optionally turn it into a stack value.
A pair of DIGlobalVariable and DIExpression.
uint64_t getSizeInBits() const
Base class for variables.
DIType * getType() const
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
Definition: DenseMap.h:235
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:747
bool hasAddressTaken(const User **=nullptr, bool IgnoreCallbackUses=false, bool IgnoreAssumeLikeCalls=true, bool IngoreLLVMUsed=false, bool IgnoreARCAttachedCall=false, bool IgnoreCastedDirectCall=false) const
hasAddressTaken - returns true if there are any uses of this function other than direct calls or invo...
Definition: Function.cpp:1752
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:206
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function.
Definition: Function.cpp:320
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:189
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:2463
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:1744
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:1740
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:2628
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:392
const BasicBlock * getParent() const
Definition: Instruction.h:90
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:75
const Instruction * getNextNonDebugInstruction(bool SkipPseudoOp=false) const
Return a pointer to the next non-debug instruction in the same basic block as 'this',...
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Definition: Instruction.cpp:83
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:389
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
void insertGlobalVariable(GlobalVariable *GV)
Insert global variable GV at the end of the global variable list and take ownership.
Definition: Module.h:551
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:254
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:690
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)
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
Definition: SmallPtrSet.h:345
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
Definition: SmallPtrSet.h:380
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:384
iterator end() const
Definition: SmallPtrSet.h:409
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:366
iterator begin() const
Definition: SmallPtrSet.h:404
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:451
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void reserve(size_type N)
Definition: SmallVector.h:667
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
Value * getValueOperand()
Definition: Instructions.h: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:255
static IntegerType * getInt1Ty(LLVMContext &C)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
@ ArrayTyID
Arrays.
Definition: Type.h:75
@ ScalableVectorTyID
Scalable SIMD vector type.
Definition: Type.h:77
@ StructTyID
Structures.
Definition: Type.h:74
@ FixedVectorTyID
Fixed width SIMD vector type.
Definition: Type.h:76
@ PointerTyID
Pointers.
Definition: Type.h:73
bool isSingleValueType() const
Return true if the type is a valid type for a register in codegen.
Definition: Type.h:287
static IntegerType * getInt8Ty(LLVMContext &C)
bool isFloatingPointTy() const
Return true if this is one of the floating-point types.
Definition: Type.h:185
bool isScalableTy() const
Return true if this is a type whose size is a known multiple of vscale.
TypeID getTypeID() const
Return the type id for the type.
Definition: Type.h:137
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1724
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
void set(Value *Val)
Definition: Value.h:870
User * getUser() const
Returns the User that contains this Use.
Definition: Use.h:72
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
const Value * stripAndAccumulateConstantOffsets(const DataLayout &DL, APInt &Offset, bool AllowNonInbounds, bool AllowInvariantGroup=false, function_ref< bool(Value &Value, APInt &Offset)> ExternalAnalysis=nullptr) const
Accumulate the constant offset this value has compared to a base pointer.
bool hasOneUse() const
Return true if there is exactly one use of this value.
Definition: Value.h:434
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp: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
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:440
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:2037
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:666
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:1529
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:1652
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:1985
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:1741
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:1926
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:1884
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:1612
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:2760
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:834
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:1455