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