LLVM  8.0.0svn
GlobalOpt.cpp
Go to the documentation of this file.
1 //===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This pass transforms simple global variables that never have their address
11 // taken. If obviously true, it marks read/write globals as constant, deletes
12 // variables only stored to, etc.
13 //
14 //===----------------------------------------------------------------------===//
15 
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.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/CallSite.h"
34 #include "llvm/IR/CallingConv.h"
35 #include "llvm/IR/Constant.h"
36 #include "llvm/IR/Constants.h"
37 #include "llvm/IR/DataLayout.h"
39 #include "llvm/IR/DerivedTypes.h"
40 #include "llvm/IR/Dominators.h"
41 #include "llvm/IR/Function.h"
43 #include "llvm/IR/GlobalAlias.h"
44 #include "llvm/IR/GlobalValue.h"
45 #include "llvm/IR/GlobalVariable.h"
46 #include "llvm/IR/InstrTypes.h"
47 #include "llvm/IR/Instruction.h"
48 #include "llvm/IR/Instructions.h"
49 #include "llvm/IR/IntrinsicInst.h"
50 #include "llvm/IR/Module.h"
51 #include "llvm/IR/Operator.h"
52 #include "llvm/IR/Type.h"
53 #include "llvm/IR/Use.h"
54 #include "llvm/IR/User.h"
55 #include "llvm/IR/Value.h"
56 #include "llvm/IR/ValueHandle.h"
57 #include "llvm/Pass.h"
59 #include "llvm/Support/Casting.h"
61 #include "llvm/Support/Debug.h"
65 #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(NumHeapSRA , "Number of heap objects SRA'd");
82 STATISTIC(NumSubstitute,"Number of globals with initializers stored into them");
83 STATISTIC(NumDeleted , "Number of globals deleted");
84 STATISTIC(NumGlobUses , "Number of global uses devirtualized");
85 STATISTIC(NumLocalized , "Number of globals localized");
86 STATISTIC(NumShrunkToBool , "Number of global vars shrunk to booleans");
87 STATISTIC(NumFastCallFns , "Number of functions converted to fastcc");
88 STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated");
89 STATISTIC(NumNestRemoved , "Number of nest attributes removed");
90 STATISTIC(NumAliasesResolved, "Number of global aliases resolved");
91 STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated");
92 STATISTIC(NumCXXDtorsRemoved, "Number of global C++ destructors removed");
93 STATISTIC(NumInternalFunc, "Number of internal functions");
94 STATISTIC(NumColdCC, "Number of functions marked coldcc");
95 
96 static cl::opt<bool>
97  EnableColdCCStressTest("enable-coldcc-stress-test",
98  cl::desc("Enable stress test of coldcc by adding "
99  "calling conv to all internal functions."),
100  cl::init(false), cl::Hidden);
101 
103  "coldcc-rel-freq", cl::Hidden, cl::init(2), cl::ZeroOrMore,
104  cl::desc(
105  "Maximum block frequency, expressed as a percentage of caller's "
106  "entry frequency, for a call site to be considered cold for enabling"
107  "coldcc"));
108 
109 /// Is this global variable possibly used by a leak checker as a root? If so,
110 /// we might not really want to eliminate the stores to it.
112  // A global variable is a root if it is a pointer, or could plausibly contain
113  // a pointer. There are two challenges; one is that we could have a struct
114  // the has an inner member which is a pointer. We recurse through the type to
115  // detect these (up to a point). The other is that we may actually be a union
116  // of a pointer and another type, and so our LLVM type is an integer which
117  // gets converted into a pointer, or our type is an [i8 x #] with a pointer
118  // potentially contained here.
119 
120  if (GV->hasPrivateLinkage())
121  return false;
122 
124  Types.push_back(GV->getValueType());
125 
126  unsigned Limit = 20;
127  do {
128  Type *Ty = Types.pop_back_val();
129  switch (Ty->getTypeID()) {
130  default: break;
131  case Type::PointerTyID: return true;
132  case Type::ArrayTyID:
133  case Type::VectorTyID: {
134  SequentialType *STy = cast<SequentialType>(Ty);
135  Types.push_back(STy->getElementType());
136  break;
137  }
138  case Type::StructTyID: {
139  StructType *STy = cast<StructType>(Ty);
140  if (STy->isOpaque()) return true;
142  E = STy->element_end(); I != E; ++I) {
143  Type *InnerTy = *I;
144  if (isa<PointerType>(InnerTy)) return true;
145  if (isa<CompositeType>(InnerTy))
146  Types.push_back(InnerTy);
147  }
148  break;
149  }
150  }
151  if (--Limit == 0) return true;
152  } while (!Types.empty());
153  return false;
154 }
155 
156 /// Given a value that is stored to a global but never read, determine whether
157 /// it's safe to remove the store and the chain of computation that feeds the
158 /// store.
159 static bool IsSafeComputationToRemove(Value *V, const TargetLibraryInfo *TLI) {
160  do {
161  if (isa<Constant>(V))
162  return true;
163  if (!V->hasOneUse())
164  return false;
165  if (isa<LoadInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V) ||
166  isa<GlobalValue>(V))
167  return false;
168  if (isAllocationFn(V, TLI))
169  return true;
170 
171  Instruction *I = cast<Instruction>(V);
172  if (I->mayHaveSideEffects())
173  return false;
174  if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
175  if (!GEP->hasAllConstantIndices())
176  return false;
177  } else if (I->getNumOperands() != 1) {
178  return false;
179  }
180 
181  V = I->getOperand(0);
182  } while (true);
183 }
184 
185 /// This GV is a pointer root. Loop over all users of the global and clean up
186 /// any that obviously don't assign the global a value that isn't dynamically
187 /// allocated.
189  const TargetLibraryInfo *TLI) {
190  // A brief explanation of leak checkers. The goal is to find bugs where
191  // pointers are forgotten, causing an accumulating growth in memory
192  // usage over time. The common strategy for leak checkers is to whitelist the
193  // memory pointed to by globals at exit. This is popular because it also
194  // solves another problem where the main thread of a C++ program may shut down
195  // before other threads that are still expecting to use those globals. To
196  // handle that case, we expect the program may create a singleton and never
197  // destroy it.
198 
199  bool Changed = false;
200 
201  // If Dead[n].first is the only use of a malloc result, we can delete its
202  // chain of computation and the store to the global in Dead[n].second.
204 
205  // Constants can't be pointers to dynamically allocated memory.
206  for (Value::user_iterator UI = GV->user_begin(), E = GV->user_end();
207  UI != E;) {
208  User *U = *UI++;
209  if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
210  Value *V = SI->getValueOperand();
211  if (isa<Constant>(V)) {
212  Changed = true;
213  SI->eraseFromParent();
214  } else if (Instruction *I = dyn_cast<Instruction>(V)) {
215  if (I->hasOneUse())
216  Dead.push_back(std::make_pair(I, SI));
217  }
218  } else if (MemSetInst *MSI = dyn_cast<MemSetInst>(U)) {
219  if (isa<Constant>(MSI->getValue())) {
220  Changed = true;
221  MSI->eraseFromParent();
222  } else if (Instruction *I = dyn_cast<Instruction>(MSI->getValue())) {
223  if (I->hasOneUse())
224  Dead.push_back(std::make_pair(I, MSI));
225  }
226  } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(U)) {
227  GlobalVariable *MemSrc = dyn_cast<GlobalVariable>(MTI->getSource());
228  if (MemSrc && MemSrc->isConstant()) {
229  Changed = true;
230  MTI->eraseFromParent();
231  } else if (Instruction *I = dyn_cast<Instruction>(MemSrc)) {
232  if (I->hasOneUse())
233  Dead.push_back(std::make_pair(I, MTI));
234  }
235  } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
236  if (CE->use_empty()) {
237  CE->destroyConstant();
238  Changed = true;
239  }
240  } else if (Constant *C = dyn_cast<Constant>(U)) {
241  if (isSafeToDestroyConstant(C)) {
242  C->destroyConstant();
243  // This could have invalidated UI, start over from scratch.
244  Dead.clear();
245  CleanupPointerRootUsers(GV, TLI);
246  return true;
247  }
248  }
249  }
250 
251  for (int i = 0, e = Dead.size(); i != e; ++i) {
252  if (IsSafeComputationToRemove(Dead[i].first, TLI)) {
253  Dead[i].second->eraseFromParent();
254  Instruction *I = Dead[i].first;
255  do {
256  if (isAllocationFn(I, TLI))
257  break;
259  if (!J)
260  break;
261  I->eraseFromParent();
262  I = J;
263  } while (true);
264  I->eraseFromParent();
265  }
266  }
267 
268  return Changed;
269 }
270 
271 /// We just marked GV constant. Loop over all users of the global, cleaning up
272 /// the obvious ones. This is largely just a quick scan over the use list to
273 /// clean up the easy and obvious cruft. This returns true if it made a change.
275  const DataLayout &DL,
276  TargetLibraryInfo *TLI) {
277  bool Changed = false;
278  // Note that we need to use a weak value handle for the worklist items. When
279  // we delete a constant array, we may also be holding pointer to one of its
280  // elements (or an element of one of its elements if we're dealing with an
281  // array of arrays) in the worklist.
283  while (!WorkList.empty()) {
284  Value *UV = WorkList.pop_back_val();
285  if (!UV)
286  continue;
287 
288  User *U = cast<User>(UV);
289 
290  if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
291  if (Init) {
292  // Replace the load with the initializer.
293  LI->replaceAllUsesWith(Init);
294  LI->eraseFromParent();
295  Changed = true;
296  }
297  } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
298  // Store must be unreachable or storing Init into the global.
299  SI->eraseFromParent();
300  Changed = true;
301  } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
302  if (CE->getOpcode() == Instruction::GetElementPtr) {
303  Constant *SubInit = nullptr;
304  if (Init)
305  SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
306  Changed |= CleanupConstantGlobalUsers(CE, SubInit, DL, TLI);
307  } else if ((CE->getOpcode() == Instruction::BitCast &&
308  CE->getType()->isPointerTy()) ||
309  CE->getOpcode() == Instruction::AddrSpaceCast) {
310  // Pointer cast, delete any stores and memsets to the global.
311  Changed |= CleanupConstantGlobalUsers(CE, nullptr, DL, TLI);
312  }
313 
314  if (CE->use_empty()) {
315  CE->destroyConstant();
316  Changed = true;
317  }
318  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
319  // Do not transform "gepinst (gep constexpr (GV))" here, because forming
320  // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold
321  // and will invalidate our notion of what Init is.
322  Constant *SubInit = nullptr;
323  if (!isa<ConstantExpr>(GEP->getOperand(0))) {
324  ConstantExpr *CE = dyn_cast_or_null<ConstantExpr>(
325  ConstantFoldInstruction(GEP, DL, TLI));
326  if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr)
327  SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
328 
329  // If the initializer is an all-null value and we have an inbounds GEP,
330  // we already know what the result of any load from that GEP is.
331  // TODO: Handle splats.
332  if (Init && isa<ConstantAggregateZero>(Init) && GEP->isInBounds())
333  SubInit = Constant::getNullValue(GEP->getResultElementType());
334  }
335  Changed |= CleanupConstantGlobalUsers(GEP, SubInit, DL, TLI);
336 
337  if (GEP->use_empty()) {
338  GEP->eraseFromParent();
339  Changed = true;
340  }
341  } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv
342  if (MI->getRawDest() == V) {
343  MI->eraseFromParent();
344  Changed = true;
345  }
346 
347  } else if (Constant *C = dyn_cast<Constant>(U)) {
348  // If we have a chain of dead constantexprs or other things dangling from
349  // us, and if they are all dead, nuke them without remorse.
350  if (isSafeToDestroyConstant(C)) {
351  C->destroyConstant();
352  CleanupConstantGlobalUsers(V, Init, DL, TLI);
353  return true;
354  }
355  }
356  }
357  return Changed;
358 }
359 
360 static bool isSafeSROAElementUse(Value *V);
361 
362 /// Return true if the specified GEP is a safe user of a derived
363 /// expression from a global that we want to SROA.
364 static bool isSafeSROAGEP(User *U) {
365  // Check to see if this ConstantExpr GEP is SRA'able. In particular, we
366  // don't like < 3 operand CE's, and we don't like non-constant integer
367  // indices. This enforces that all uses are 'gep GV, 0, C, ...' for some
368  // value of C.
369  if (U->getNumOperands() < 3 || !isa<Constant>(U->getOperand(1)) ||
370  !cast<Constant>(U->getOperand(1))->isNullValue())
371  return false;
372 
374  ++GEPI; // Skip over the pointer index.
375 
376  // For all other level we require that the indices are constant and inrange.
377  // In particular, consider: A[0][i]. We cannot know that the user isn't doing
378  // invalid things like allowing i to index an out-of-range subscript that
379  // accesses A[1]. This can also happen between different members of a struct
380  // in llvm IR.
381  for (; GEPI != E; ++GEPI) {
382  if (GEPI.isStruct())
383  continue;
384 
385  ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand());
386  if (!IdxVal || (GEPI.isBoundedSequential() &&
387  IdxVal->getZExtValue() >= GEPI.getSequentialNumElements()))
388  return false;
389  }
390 
391  return llvm::all_of(U->users(),
392  [](User *UU) { return isSafeSROAElementUse(UU); });
393 }
394 
395 /// Return true if the specified instruction is a safe user of a derived
396 /// expression from a global that we want to SROA.
397 static bool isSafeSROAElementUse(Value *V) {
398  // We might have a dead and dangling constant hanging off of here.
399  if (Constant *C = dyn_cast<Constant>(V))
400  return isSafeToDestroyConstant(C);
401 
403  if (!I) return false;
404 
405  // Loads are ok.
406  if (isa<LoadInst>(I)) return true;
407 
408  // Stores *to* the pointer are ok.
409  if (StoreInst *SI = dyn_cast<StoreInst>(I))
410  return SI->getOperand(0) != V;
411 
412  // Otherwise, it must be a GEP. Check it and its users are safe to SRA.
413  return isa<GetElementPtrInst>(I) && isSafeSROAGEP(I);
414 }
415 
416 /// Look at all uses of the global and decide whether it is safe for us to
417 /// perform this transformation.
419  for (User *U : GV->users()) {
420  // The user of the global must be a GEP Inst or a ConstantExpr GEP.
421  if (!isa<GetElementPtrInst>(U) &&
422  (!isa<ConstantExpr>(U) ||
423  cast<ConstantExpr>(U)->getOpcode() != Instruction::GetElementPtr))
424  return false;
425 
426  // Check the gep and it's users are safe to SRA
427  if (!isSafeSROAGEP(U))
428  return false;
429  }
430 
431  return true;
432 }
433 
434 /// Copy over the debug info for a variable to its SRA replacements.
436  uint64_t FragmentOffsetInBits,
437  uint64_t FragmentSizeInBits,
438  unsigned NumElements) {
440  GV->getDebugInfo(GVs);
441  for (auto *GVE : GVs) {
442  DIVariable *Var = GVE->getVariable();
443  DIExpression *Expr = GVE->getExpression();
444  if (NumElements > 1) {
446  Expr, FragmentOffsetInBits, FragmentSizeInBits))
447  Expr = *E;
448  else
449  return;
450  }
451  auto *NGVE = DIGlobalVariableExpression::get(GVE->getContext(), Var, Expr);
452  NGV->addDebugInfo(NGVE);
453  }
454 }
455 
456 /// Perform scalar replacement of aggregates on the specified global variable.
457 /// This opens the door for other optimizations by exposing the behavior of the
458 /// program in a more fine-grained way. We have determined that this
459 /// transformation is safe already. We return the first global variable we
460 /// insert so that the caller can reprocess it.
462  // Make sure this global only has simple uses that we can SRA.
463  if (!GlobalUsersSafeToSRA(GV))
464  return nullptr;
465 
466  assert(GV->hasLocalLinkage());
467  Constant *Init = GV->getInitializer();
468  Type *Ty = Init->getType();
469 
470  std::vector<GlobalVariable *> NewGlobals;
471  Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
472 
473  // Get the alignment of the global, either explicit or target-specific.
474  unsigned StartAlignment = GV->getAlignment();
475  if (StartAlignment == 0)
476  StartAlignment = DL.getABITypeAlignment(GV->getType());
477 
478  if (StructType *STy = dyn_cast<StructType>(Ty)) {
479  unsigned NumElements = STy->getNumElements();
480  NewGlobals.reserve(NumElements);
481  const StructLayout &Layout = *DL.getStructLayout(STy);
482  for (unsigned i = 0, e = NumElements; i != e; ++i) {
483  Constant *In = Init->getAggregateElement(i);
484  assert(In && "Couldn't get element of initializer?");
485  GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false,
487  In, GV->getName()+"."+Twine(i),
488  GV->getThreadLocalMode(),
489  GV->getType()->getAddressSpace());
491  NGV->copyAttributesFrom(GV);
492  Globals.push_back(NGV);
493  NewGlobals.push_back(NGV);
494 
495  // Calculate the known alignment of the field. If the original aggregate
496  // had 256 byte alignment for example, something might depend on that:
497  // propagate info to each field.
498  uint64_t FieldOffset = Layout.getElementOffset(i);
499  unsigned NewAlign = (unsigned)MinAlign(StartAlignment, FieldOffset);
500  if (NewAlign > DL.getABITypeAlignment(STy->getElementType(i)))
501  NGV->setAlignment(NewAlign);
502 
503  // Copy over the debug info for the variable.
504  uint64_t Size = DL.getTypeAllocSizeInBits(NGV->getValueType());
505  uint64_t FragmentOffsetInBits = Layout.getElementOffsetInBits(i);
506  transferSRADebugInfo(GV, NGV, FragmentOffsetInBits, Size, NumElements);
507  }
508  } else if (SequentialType *STy = dyn_cast<SequentialType>(Ty)) {
509  unsigned NumElements = STy->getNumElements();
510  if (NumElements > 16 && GV->hasNUsesOrMore(16))
511  return nullptr; // It's not worth it.
512  NewGlobals.reserve(NumElements);
513  auto ElTy = STy->getElementType();
514  uint64_t EltSize = DL.getTypeAllocSize(ElTy);
515  unsigned EltAlign = DL.getABITypeAlignment(ElTy);
516  uint64_t FragmentSizeInBits = DL.getTypeAllocSizeInBits(ElTy);
517  for (unsigned i = 0, e = NumElements; i != e; ++i) {
518  Constant *In = Init->getAggregateElement(i);
519  assert(In && "Couldn't get element of initializer?");
520 
521  GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false,
523  In, GV->getName()+"."+Twine(i),
524  GV->getThreadLocalMode(),
525  GV->getType()->getAddressSpace());
527  NGV->copyAttributesFrom(GV);
528  Globals.push_back(NGV);
529  NewGlobals.push_back(NGV);
530 
531  // Calculate the known alignment of the field. If the original aggregate
532  // had 256 byte alignment for example, something might depend on that:
533  // propagate info to each field.
534  unsigned NewAlign = (unsigned)MinAlign(StartAlignment, EltSize*i);
535  if (NewAlign > EltAlign)
536  NGV->setAlignment(NewAlign);
537  transferSRADebugInfo(GV, NGV, FragmentSizeInBits * i, FragmentSizeInBits,
538  NumElements);
539  }
540  }
541 
542  if (NewGlobals.empty())
543  return nullptr;
544 
545  LLVM_DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV << "\n");
546 
548 
549  // Loop over all of the uses of the global, replacing the constantexpr geps,
550  // with smaller constantexpr geps or direct references.
551  while (!GV->use_empty()) {
552  User *GEP = GV->user_back();
553  assert(((isa<ConstantExpr>(GEP) &&
554  cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)||
555  isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!");
556 
557  // Ignore the 1th operand, which has to be zero or else the program is quite
558  // broken (undefined). Get the 2nd operand, which is the structure or array
559  // index.
560  unsigned Val = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
561  if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access.
562 
563  Value *NewPtr = NewGlobals[Val];
564  Type *NewTy = NewGlobals[Val]->getValueType();
565 
566  // Form a shorter GEP if needed.
567  if (GEP->getNumOperands() > 3) {
568  if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) {
570  Idxs.push_back(NullInt);
571  for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
572  Idxs.push_back(CE->getOperand(i));
573  NewPtr =
574  ConstantExpr::getGetElementPtr(NewTy, cast<Constant>(NewPtr), Idxs);
575  } else {
576  GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP);
578  Idxs.push_back(NullInt);
579  for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i)
580  Idxs.push_back(GEPI->getOperand(i));
581  NewPtr = GetElementPtrInst::Create(
582  NewTy, NewPtr, Idxs, GEPI->getName() + "." + Twine(Val), GEPI);
583  }
584  }
585  GEP->replaceAllUsesWith(NewPtr);
586 
587  if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP))
588  GEPI->eraseFromParent();
589  else
590  cast<ConstantExpr>(GEP)->destroyConstant();
591  }
592 
593  // Delete the old global, now that it is dead.
594  Globals.erase(GV);
595  ++NumSRA;
596 
597  // Loop over the new globals array deleting any globals that are obviously
598  // dead. This can arise due to scalarization of a structure or an array that
599  // has elements that are dead.
600  unsigned FirstGlobal = 0;
601  for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i)
602  if (NewGlobals[i]->use_empty()) {
603  Globals.erase(NewGlobals[i]);
604  if (FirstGlobal == i) ++FirstGlobal;
605  }
606 
607  return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : nullptr;
608 }
609 
610 /// Return true if all users of the specified value will trap if the value is
611 /// dynamically null. PHIs keeps track of any phi nodes we've seen to avoid
612 /// reprocessing them.
613 static bool AllUsesOfValueWillTrapIfNull(const Value *V,
615  for (const User *U : V->users()) {
616  if (const Instruction *I = dyn_cast<Instruction>(U)) {
617  // If null pointer is considered valid, then all uses are non-trapping.
618  // Non address-space 0 globals have already been pruned by the caller.
619  if (NullPointerIsDefined(I->getFunction()))
620  return false;
621  }
622  if (isa<LoadInst>(U)) {
623  // Will trap.
624  } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
625  if (SI->getOperand(0) == V) {
626  //cerr << "NONTRAPPING USE: " << *U;
627  return false; // Storing the value.
628  }
629  } else if (const CallInst *CI = dyn_cast<CallInst>(U)) {
630  if (CI->getCalledValue() != V) {
631  //cerr << "NONTRAPPING USE: " << *U;
632  return false; // Not calling the ptr
633  }
634  } else if (const InvokeInst *II = dyn_cast<InvokeInst>(U)) {
635  if (II->getCalledValue() != V) {
636  //cerr << "NONTRAPPING USE: " << *U;
637  return false; // Not calling the ptr
638  }
639  } else if (const BitCastInst *CI = dyn_cast<BitCastInst>(U)) {
640  if (!AllUsesOfValueWillTrapIfNull(CI, PHIs)) return false;
641  } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
642  if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false;
643  } else if (const PHINode *PN = dyn_cast<PHINode>(U)) {
644  // If we've already seen this phi node, ignore it, it has already been
645  // checked.
646  if (PHIs.insert(PN).second && !AllUsesOfValueWillTrapIfNull(PN, PHIs))
647  return false;
648  } else if (isa<ICmpInst>(U) &&
649  isa<ConstantPointerNull>(U->getOperand(1))) {
650  // Ignore icmp X, null
651  } else {
652  //cerr << "NONTRAPPING USE: " << *U;
653  return false;
654  }
655  }
656  return true;
657 }
658 
659 /// Return true if all uses of any loads from GV will trap if the loaded value
660 /// is null. Note that this also permits comparisons of the loaded value
661 /// against null, as a special case.
663  for (const User *U : GV->users())
664  if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
666  if (!AllUsesOfValueWillTrapIfNull(LI, PHIs))
667  return false;
668  } else if (isa<StoreInst>(U)) {
669  // Ignore stores to the global.
670  } else {
671  // We don't know or understand this user, bail out.
672  //cerr << "UNKNOWN USER OF GLOBAL!: " << *U;
673  return false;
674  }
675  return true;
676 }
677 
679  bool Changed = false;
680  for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) {
681  Instruction *I = cast<Instruction>(*UI++);
682  // Uses are non-trapping if null pointer is considered valid.
683  // Non address-space 0 globals are already pruned by the caller.
685  return false;
686  if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
687  LI->setOperand(0, NewV);
688  Changed = true;
689  } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
690  if (SI->getOperand(1) == V) {
691  SI->setOperand(1, NewV);
692  Changed = true;
693  }
694  } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
695  CallSite CS(I);
696  if (CS.getCalledValue() == V) {
697  // Calling through the pointer! Turn into a direct call, but be careful
698  // that the pointer is not also being passed as an argument.
699  CS.setCalledFunction(NewV);
700  Changed = true;
701  bool PassedAsArg = false;
702  for (unsigned i = 0, e = CS.arg_size(); i != e; ++i)
703  if (CS.getArgument(i) == V) {
704  PassedAsArg = true;
705  CS.setArgument(i, NewV);
706  }
707 
708  if (PassedAsArg) {
709  // Being passed as an argument also. Be careful to not invalidate UI!
710  UI = V->user_begin();
711  }
712  }
713  } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
714  Changed |= OptimizeAwayTrappingUsesOfValue(CI,
715  ConstantExpr::getCast(CI->getOpcode(),
716  NewV, CI->getType()));
717  if (CI->use_empty()) {
718  Changed = true;
719  CI->eraseFromParent();
720  }
721  } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
722  // Should handle GEP here.
724  Idxs.reserve(GEPI->getNumOperands()-1);
725  for (User::op_iterator i = GEPI->op_begin() + 1, e = GEPI->op_end();
726  i != e; ++i)
727  if (Constant *C = dyn_cast<Constant>(*i))
728  Idxs.push_back(C);
729  else
730  break;
731  if (Idxs.size() == GEPI->getNumOperands()-1)
733  GEPI, ConstantExpr::getGetElementPtr(nullptr, NewV, Idxs));
734  if (GEPI->use_empty()) {
735  Changed = true;
736  GEPI->eraseFromParent();
737  }
738  }
739  }
740 
741  return Changed;
742 }
743 
744 /// The specified global has only one non-null value stored into it. If there
745 /// are uses of the loaded value that would trap if the loaded value is
746 /// dynamically null, then we know that they cannot be reachable with a null
747 /// optimize away the load.
749  const DataLayout &DL,
750  TargetLibraryInfo *TLI) {
751  bool Changed = false;
752 
753  // Keep track of whether we are able to remove all the uses of the global
754  // other than the store that defines it.
755  bool AllNonStoreUsesGone = true;
756 
757  // Replace all uses of loads with uses of uses of the stored value.
758  for (Value::user_iterator GUI = GV->user_begin(), E = GV->user_end(); GUI != E;){
759  User *GlobalUser = *GUI++;
760  if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) {
761  Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV);
762  // If we were able to delete all uses of the loads
763  if (LI->use_empty()) {
764  LI->eraseFromParent();
765  Changed = true;
766  } else {
767  AllNonStoreUsesGone = false;
768  }
769  } else if (isa<StoreInst>(GlobalUser)) {
770  // Ignore the store that stores "LV" to the global.
771  assert(GlobalUser->getOperand(1) == GV &&
772  "Must be storing *to* the global");
773  } else {
774  AllNonStoreUsesGone = false;
775 
776  // If we get here we could have other crazy uses that are transitively
777  // loaded.
778  assert((isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) ||
779  isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) ||
780  isa<BitCastInst>(GlobalUser) ||
781  isa<GetElementPtrInst>(GlobalUser)) &&
782  "Only expect load and stores!");
783  }
784  }
785 
786  if (Changed) {
787  LLVM_DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV
788  << "\n");
789  ++NumGlobUses;
790  }
791 
792  // If we nuked all of the loads, then none of the stores are needed either,
793  // nor is the global.
794  if (AllNonStoreUsesGone) {
795  if (isLeakCheckerRoot(GV)) {
796  Changed |= CleanupPointerRootUsers(GV, TLI);
797  } else {
798  Changed = true;
799  CleanupConstantGlobalUsers(GV, nullptr, DL, TLI);
800  }
801  if (GV->use_empty()) {
802  LLVM_DEBUG(dbgs() << " *** GLOBAL NOW DEAD!\n");
803  Changed = true;
804  GV->eraseFromParent();
805  ++NumDeleted;
806  }
807  }
808  return Changed;
809 }
810 
811 /// Walk the use list of V, constant folding all of the instructions that are
812 /// foldable.
813 static void ConstantPropUsersOf(Value *V, const DataLayout &DL,
814  TargetLibraryInfo *TLI) {
815  for (Value::user_iterator UI = V->user_begin(), E = V->user_end(); UI != E; )
816  if (Instruction *I = dyn_cast<Instruction>(*UI++))
817  if (Constant *NewC = ConstantFoldInstruction(I, DL, TLI)) {
818  I->replaceAllUsesWith(NewC);
819 
820  // Advance UI to the next non-I use to avoid invalidating it!
821  // Instructions could multiply use V.
822  while (UI != E && *UI == I)
823  ++UI;
824  if (isInstructionTriviallyDead(I, TLI))
825  I->eraseFromParent();
826  }
827 }
828 
829 /// This function takes the specified global variable, and transforms the
830 /// program as if it always contained the result of the specified malloc.
831 /// Because it is always the result of the specified malloc, there is no reason
832 /// to actually DO the malloc. Instead, turn the malloc into a global, and any
833 /// loads of GV as uses of the new global.
834 static GlobalVariable *
836  ConstantInt *NElements, const DataLayout &DL,
837  TargetLibraryInfo *TLI) {
838  LLVM_DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << " CALL = " << *CI
839  << '\n');
840 
841  Type *GlobalType;
842  if (NElements->getZExtValue() == 1)
843  GlobalType = AllocTy;
844  else
845  // If we have an array allocation, the global variable is of an array.
846  GlobalType = ArrayType::get(AllocTy, NElements->getZExtValue());
847 
848  // Create the new global variable. The contents of the malloc'd memory is
849  // undefined, so initialize with an undef value.
850  GlobalVariable *NewGV = new GlobalVariable(
851  *GV->getParent(), GlobalType, false, GlobalValue::InternalLinkage,
852  UndefValue::get(GlobalType), GV->getName() + ".body", nullptr,
853  GV->getThreadLocalMode());
854 
855  // If there are bitcast users of the malloc (which is typical, usually we have
856  // a malloc + bitcast) then replace them with uses of the new global. Update
857  // other users to use the global as well.
858  BitCastInst *TheBC = nullptr;
859  while (!CI->use_empty()) {
860  Instruction *User = cast<Instruction>(CI->user_back());
861  if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) {
862  if (BCI->getType() == NewGV->getType()) {
863  BCI->replaceAllUsesWith(NewGV);
864  BCI->eraseFromParent();
865  } else {
866  BCI->setOperand(0, NewGV);
867  }
868  } else {
869  if (!TheBC)
870  TheBC = new BitCastInst(NewGV, CI->getType(), "newgv", CI);
871  User->replaceUsesOfWith(CI, TheBC);
872  }
873  }
874 
875  Constant *RepValue = NewGV;
876  if (NewGV->getType() != GV->getValueType())
877  RepValue = ConstantExpr::getBitCast(RepValue, GV->getValueType());
878 
879  // If there is a comparison against null, we will insert a global bool to
880  // keep track of whether the global was initialized yet or not.
881  GlobalVariable *InitBool =
882  new GlobalVariable(Type::getInt1Ty(GV->getContext()), false,
883  GlobalValue::InternalLinkage,
885  GV->getName()+".init", GV->getThreadLocalMode());
886  bool InitBoolUsed = false;
887 
888  // Loop over all uses of GV, processing them in turn.
889  while (!GV->use_empty()) {
890  if (StoreInst *SI = dyn_cast<StoreInst>(GV->user_back())) {
891  // The global is initialized when the store to it occurs.
892  new StoreInst(ConstantInt::getTrue(GV->getContext()), InitBool, false, 0,
893  SI->getOrdering(), SI->getSyncScopeID(), SI);
894  SI->eraseFromParent();
895  continue;
896  }
897 
898  LoadInst *LI = cast<LoadInst>(GV->user_back());
899  while (!LI->use_empty()) {
900  Use &LoadUse = *LI->use_begin();
901  ICmpInst *ICI = dyn_cast<ICmpInst>(LoadUse.getUser());
902  if (!ICI) {
903  LoadUse = RepValue;
904  continue;
905  }
906 
907  // Replace the cmp X, 0 with a use of the bool value.
908  // Sink the load to where the compare was, if atomic rules allow us to.
909  Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", false, 0,
910  LI->getOrdering(), LI->getSyncScopeID(),
911  LI->isUnordered() ? (Instruction*)ICI : LI);
912  InitBoolUsed = true;
913  switch (ICI->getPredicate()) {
914  default: llvm_unreachable("Unknown ICmp Predicate!");
915  case ICmpInst::ICMP_ULT:
916  case ICmpInst::ICMP_SLT: // X < null -> always false
917  LV = ConstantInt::getFalse(GV->getContext());
918  break;
919  case ICmpInst::ICMP_ULE:
920  case ICmpInst::ICMP_SLE:
921  case ICmpInst::ICMP_EQ:
922  LV = BinaryOperator::CreateNot(LV, "notinit", ICI);
923  break;
924  case ICmpInst::ICMP_NE:
925  case ICmpInst::ICMP_UGE:
926  case ICmpInst::ICMP_SGE:
927  case ICmpInst::ICMP_UGT:
928  case ICmpInst::ICMP_SGT:
929  break; // no change.
930  }
931  ICI->replaceAllUsesWith(LV);
932  ICI->eraseFromParent();
933  }
934  LI->eraseFromParent();
935  }
936 
937  // If the initialization boolean was used, insert it, otherwise delete it.
938  if (!InitBoolUsed) {
939  while (!InitBool->use_empty()) // Delete initializations
940  cast<StoreInst>(InitBool->user_back())->eraseFromParent();
941  delete InitBool;
942  } else
943  GV->getParent()->getGlobalList().insert(GV->getIterator(), InitBool);
944 
945  // Now the GV is dead, nuke it and the malloc..
946  GV->eraseFromParent();
947  CI->eraseFromParent();
948 
949  // To further other optimizations, loop over all users of NewGV and try to
950  // constant prop them. This will promote GEP instructions with constant
951  // indices into GEP constant-exprs, which will allow global-opt to hack on it.
952  ConstantPropUsersOf(NewGV, DL, TLI);
953  if (RepValue != NewGV)
954  ConstantPropUsersOf(RepValue, DL, TLI);
955 
956  return NewGV;
957 }
958 
959 /// Scan the use-list of V checking to make sure that there are no complex uses
960 /// of V. We permit simple things like dereferencing the pointer, but not
961 /// storing through the address, unless it is to the specified global.
963  const GlobalVariable *GV,
965  for (const User *U : V->users()) {
966  const Instruction *Inst = cast<Instruction>(U);
967 
968  if (isa<LoadInst>(Inst) || isa<CmpInst>(Inst)) {
969  continue; // Fine, ignore.
970  }
971 
972  if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
973  if (SI->getOperand(0) == V && SI->getOperand(1) != GV)
974  return false; // Storing the pointer itself... bad.
975  continue; // Otherwise, storing through it, or storing into GV... fine.
976  }
977 
978  // Must index into the array and into the struct.
979  if (isa<GetElementPtrInst>(Inst) && Inst->getNumOperands() >= 3) {
980  if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Inst, GV, PHIs))
981  return false;
982  continue;
983  }
984 
985  if (const PHINode *PN = dyn_cast<PHINode>(Inst)) {
986  // PHIs are ok if all uses are ok. Don't infinitely recurse through PHI
987  // cycles.
988  if (PHIs.insert(PN).second)
990  return false;
991  continue;
992  }
993 
994  if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Inst)) {
995  if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(BCI, GV, PHIs))
996  return false;
997  continue;
998  }
999 
1000  return false;
1001  }
1002  return true;
1003 }
1004 
1005 /// The Alloc pointer is stored into GV somewhere. Transform all uses of the
1006 /// allocation into loads from the global and uses of the resultant pointer.
1007 /// Further, delete the store into GV. This assumes that these value pass the
1008 /// 'ValueIsOnlyUsedLocallyOrStoredToOneGlobal' predicate.
1010  GlobalVariable *GV) {
1011  while (!Alloc->use_empty()) {
1012  Instruction *U = cast<Instruction>(*Alloc->user_begin());
1013  Instruction *InsertPt = U;
1014  if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1015  // If this is the store of the allocation into the global, remove it.
1016  if (SI->getOperand(1) == GV) {
1017  SI->eraseFromParent();
1018  continue;
1019  }
1020  } else if (PHINode *PN = dyn_cast<PHINode>(U)) {
1021  // Insert the load in the corresponding predecessor, not right before the
1022  // PHI.
1023  InsertPt = PN->getIncomingBlock(*Alloc->use_begin())->getTerminator();
1024  } else if (isa<BitCastInst>(U)) {
1025  // Must be bitcast between the malloc and store to initialize the global.
1027  U->eraseFromParent();
1028  continue;
1029  } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
1030  // If this is a "GEP bitcast" and the user is a store to the global, then
1031  // just process it as a bitcast.
1032  if (GEPI->hasAllZeroIndices() && GEPI->hasOneUse())
1033  if (StoreInst *SI = dyn_cast<StoreInst>(GEPI->user_back()))
1034  if (SI->getOperand(1) == GV) {
1035  // Must be bitcast GEP between the malloc and store to initialize
1036  // the global.
1038  GEPI->eraseFromParent();
1039  continue;
1040  }
1041  }
1042 
1043  // Insert a load from the global, and use it instead of the malloc.
1044  Value *NL = new LoadInst(GV, GV->getName()+".val", InsertPt);
1045  U->replaceUsesOfWith(Alloc, NL);
1046  }
1047 }
1048 
1049 /// Verify that all uses of V (a load, or a phi of a load) are simple enough to
1050 /// perform heap SRA on. This permits GEP's that index through the array and
1051 /// struct field, icmps of null, and PHIs.
1053  SmallPtrSetImpl<const PHINode*> &LoadUsingPHIs,
1054  SmallPtrSetImpl<const PHINode*> &LoadUsingPHIsPerLoad) {
1055  // We permit two users of the load: setcc comparing against the null
1056  // pointer, and a getelementptr of a specific form.
1057  for (const User *U : V->users()) {
1058  const Instruction *UI = cast<Instruction>(U);
1059 
1060  // Comparison against null is ok.
1061  if (const ICmpInst *ICI = dyn_cast<ICmpInst>(UI)) {
1062  if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
1063  return false;
1064  continue;
1065  }
1066 
1067  // getelementptr is also ok, but only a simple form.
1068  if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(UI)) {
1069  // Must index into the array and into the struct.
1070  if (GEPI->getNumOperands() < 3)
1071  return false;
1072 
1073  // Otherwise the GEP is ok.
1074  continue;
1075  }
1076 
1077  if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
1078  if (!LoadUsingPHIsPerLoad.insert(PN).second)
1079  // This means some phi nodes are dependent on each other.
1080  // Avoid infinite looping!
1081  return false;
1082  if (!LoadUsingPHIs.insert(PN).second)
1083  // If we have already analyzed this PHI, then it is safe.
1084  continue;
1085 
1086  // Make sure all uses of the PHI are simple enough to transform.
1088  LoadUsingPHIs, LoadUsingPHIsPerLoad))
1089  return false;
1090 
1091  continue;
1092  }
1093 
1094  // Otherwise we don't know what this is, not ok.
1095  return false;
1096  }
1097 
1098  return true;
1099 }
1100 
1101 /// If all users of values loaded from GV are simple enough to perform HeapSRA,
1102 /// return true.
1104  Instruction *StoredVal) {
1105  SmallPtrSet<const PHINode*, 32> LoadUsingPHIs;
1106  SmallPtrSet<const PHINode*, 32> LoadUsingPHIsPerLoad;
1107  for (const User *U : GV->users())
1108  if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
1109  if (!LoadUsesSimpleEnoughForHeapSRA(LI, LoadUsingPHIs,
1110  LoadUsingPHIsPerLoad))
1111  return false;
1112  LoadUsingPHIsPerLoad.clear();
1113  }
1114 
1115  // If we reach here, we know that all uses of the loads and transitive uses
1116  // (through PHI nodes) are simple enough to transform. However, we don't know
1117  // that all inputs the to the PHI nodes are in the same equivalence sets.
1118  // Check to verify that all operands of the PHIs are either PHIS that can be
1119  // transformed, loads from GV, or MI itself.
1120  for (const PHINode *PN : LoadUsingPHIs) {
1121  for (unsigned op = 0, e = PN->getNumIncomingValues(); op != e; ++op) {
1122  Value *InVal = PN->getIncomingValue(op);
1123 
1124  // PHI of the stored value itself is ok.
1125  if (InVal == StoredVal) continue;
1126 
1127  if (const PHINode *InPN = dyn_cast<PHINode>(InVal)) {
1128  // One of the PHIs in our set is (optimistically) ok.
1129  if (LoadUsingPHIs.count(InPN))
1130  continue;
1131  return false;
1132  }
1133 
1134  // Load from GV is ok.
1135  if (const LoadInst *LI = dyn_cast<LoadInst>(InVal))
1136  if (LI->getOperand(0) == GV)
1137  continue;
1138 
1139  // UNDEF? NULL?
1140 
1141  // Anything else is rejected.
1142  return false;
1143  }
1144  }
1145 
1146  return true;
1147 }
1148 
1149 static Value *GetHeapSROAValue(Value *V, unsigned FieldNo,
1150  DenseMap<Value *, std::vector<Value *>> &InsertedScalarizedValues,
1151  std::vector<std::pair<PHINode *, unsigned>> &PHIsToRewrite) {
1152  std::vector<Value *> &FieldVals = InsertedScalarizedValues[V];
1153 
1154  if (FieldNo >= FieldVals.size())
1155  FieldVals.resize(FieldNo+1);
1156 
1157  // If we already have this value, just reuse the previously scalarized
1158  // version.
1159  if (Value *FieldVal = FieldVals[FieldNo])
1160  return FieldVal;
1161 
1162  // Depending on what instruction this is, we have several cases.
1163  Value *Result;
1164  if (LoadInst *LI = dyn_cast<LoadInst>(V)) {
1165  // This is a scalarized version of the load from the global. Just create
1166  // a new Load of the scalarized global.
1167  Result = new LoadInst(GetHeapSROAValue(LI->getOperand(0), FieldNo,
1168  InsertedScalarizedValues,
1169  PHIsToRewrite),
1170  LI->getName()+".f"+Twine(FieldNo), LI);
1171  } else {
1172  PHINode *PN = cast<PHINode>(V);
1173  // PN's type is pointer to struct. Make a new PHI of pointer to struct
1174  // field.
1175 
1176  PointerType *PTy = cast<PointerType>(PN->getType());
1177  StructType *ST = cast<StructType>(PTy->getElementType());
1178 
1179  unsigned AS = PTy->getAddressSpace();
1180  PHINode *NewPN =
1181  PHINode::Create(PointerType::get(ST->getElementType(FieldNo), AS),
1182  PN->getNumIncomingValues(),
1183  PN->getName()+".f"+Twine(FieldNo), PN);
1184  Result = NewPN;
1185  PHIsToRewrite.push_back(std::make_pair(PN, FieldNo));
1186  }
1187 
1188  return FieldVals[FieldNo] = Result;
1189 }
1190 
1191 /// Given a load instruction and a value derived from the load, rewrite the
1192 /// derived value to use the HeapSRoA'd load.
1193 static void RewriteHeapSROALoadUser(Instruction *LoadUser,
1194  DenseMap<Value *, std::vector<Value *>> &InsertedScalarizedValues,
1195  std::vector<std::pair<PHINode *, unsigned>> &PHIsToRewrite) {
1196  // If this is a comparison against null, handle it.
1197  if (ICmpInst *SCI = dyn_cast<ICmpInst>(LoadUser)) {
1198  assert(isa<ConstantPointerNull>(SCI->getOperand(1)));
1199  // If we have a setcc of the loaded pointer, we can use a setcc of any
1200  // field.
1201  Value *NPtr = GetHeapSROAValue(SCI->getOperand(0), 0,
1202  InsertedScalarizedValues, PHIsToRewrite);
1203 
1204  Value *New = new ICmpInst(SCI, SCI->getPredicate(), NPtr,
1206  SCI->getName());
1207  SCI->replaceAllUsesWith(New);
1208  SCI->eraseFromParent();
1209  return;
1210  }
1211 
1212  // Handle 'getelementptr Ptr, Idx, i32 FieldNo ...'
1213  if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(LoadUser)) {
1214  assert(GEPI->getNumOperands() >= 3 && isa<ConstantInt>(GEPI->getOperand(2))
1215  && "Unexpected GEPI!");
1216 
1217  // Load the pointer for this field.
1218  unsigned FieldNo = cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue();
1219  Value *NewPtr = GetHeapSROAValue(GEPI->getOperand(0), FieldNo,
1220  InsertedScalarizedValues, PHIsToRewrite);
1221 
1222  // Create the new GEP idx vector.
1223  SmallVector<Value*, 8> GEPIdx;
1224  GEPIdx.push_back(GEPI->getOperand(1));
1225  GEPIdx.append(GEPI->op_begin()+3, GEPI->op_end());
1226 
1227  Value *NGEPI = GetElementPtrInst::Create(GEPI->getResultElementType(), NewPtr, GEPIdx,
1228  GEPI->getName(), GEPI);
1229  GEPI->replaceAllUsesWith(NGEPI);
1230  GEPI->eraseFromParent();
1231  return;
1232  }
1233 
1234  // Recursively transform the users of PHI nodes. This will lazily create the
1235  // PHIs that are needed for individual elements. Keep track of what PHIs we
1236  // see in InsertedScalarizedValues so that we don't get infinite loops (very
1237  // antisocial). If the PHI is already in InsertedScalarizedValues, it has
1238  // already been seen first by another load, so its uses have already been
1239  // processed.
1240  PHINode *PN = cast<PHINode>(LoadUser);
1241  if (!InsertedScalarizedValues.insert(std::make_pair(PN,
1242  std::vector<Value *>())).second)
1243  return;
1244 
1245  // If this is the first time we've seen this PHI, recursively process all
1246  // users.
1247  for (auto UI = PN->user_begin(), E = PN->user_end(); UI != E;) {
1248  Instruction *User = cast<Instruction>(*UI++);
1249  RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite);
1250  }
1251 }
1252 
1253 /// We are performing Heap SRoA on a global. Ptr is a value loaded from the
1254 /// global. Eliminate all uses of Ptr, making them use FieldGlobals instead.
1255 /// All uses of loaded values satisfy AllGlobalLoadUsesSimpleEnoughForHeapSRA.
1257  DenseMap<Value *, std::vector<Value *>> &InsertedScalarizedValues,
1258  std::vector<std::pair<PHINode *, unsigned> > &PHIsToRewrite) {
1259  for (auto UI = Load->user_begin(), E = Load->user_end(); UI != E;) {
1260  Instruction *User = cast<Instruction>(*UI++);
1261  RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite);
1262  }
1263 
1264  if (Load->use_empty()) {
1265  Load->eraseFromParent();
1266  InsertedScalarizedValues.erase(Load);
1267  }
1268 }
1269 
1270 /// CI is an allocation of an array of structures. Break it up into multiple
1271 /// allocations of arrays of the fields.
1273  Value *NElems, const DataLayout &DL,
1274  const TargetLibraryInfo *TLI) {
1275  LLVM_DEBUG(dbgs() << "SROA HEAP ALLOC: " << *GV << " MALLOC = " << *CI
1276  << '\n');
1277  Type *MAT = getMallocAllocatedType(CI, TLI);
1278  StructType *STy = cast<StructType>(MAT);
1279 
1280  // There is guaranteed to be at least one use of the malloc (storing
1281  // it into GV). If there are other uses, change them to be uses of
1282  // the global to simplify later code. This also deletes the store
1283  // into GV.
1285 
1286  // Okay, at this point, there are no users of the malloc. Insert N
1287  // new mallocs at the same place as CI, and N globals.
1288  std::vector<Value *> FieldGlobals;
1289  std::vector<Value *> FieldMallocs;
1290 
1292  CI->getOperandBundlesAsDefs(OpBundles);
1293 
1294  unsigned AS = GV->getType()->getPointerAddressSpace();
1295  for (unsigned FieldNo = 0, e = STy->getNumElements(); FieldNo != e;++FieldNo){
1296  Type *FieldTy = STy->getElementType(FieldNo);
1297  PointerType *PFieldTy = PointerType::get(FieldTy, AS);
1298 
1299  GlobalVariable *NGV = new GlobalVariable(
1300  *GV->getParent(), PFieldTy, false, GlobalValue::InternalLinkage,
1301  Constant::getNullValue(PFieldTy), GV->getName() + ".f" + Twine(FieldNo),
1302  nullptr, GV->getThreadLocalMode());
1303  NGV->copyAttributesFrom(GV);
1304  FieldGlobals.push_back(NGV);
1305 
1306  unsigned TypeSize = DL.getTypeAllocSize(FieldTy);
1307  if (StructType *ST = dyn_cast<StructType>(FieldTy))
1308  TypeSize = DL.getStructLayout(ST)->getSizeInBytes();
1309  Type *IntPtrTy = DL.getIntPtrType(CI->getType());
1310  Value *NMI = CallInst::CreateMalloc(CI, IntPtrTy, FieldTy,
1311  ConstantInt::get(IntPtrTy, TypeSize),
1312  NElems, OpBundles, nullptr,
1313  CI->getName() + ".f" + Twine(FieldNo));
1314  FieldMallocs.push_back(NMI);
1315  new StoreInst(NMI, NGV, CI);
1316  }
1317 
1318  // The tricky aspect of this transformation is handling the case when malloc
1319  // fails. In the original code, malloc failing would set the result pointer
1320  // of malloc to null. In this case, some mallocs could succeed and others
1321  // could fail. As such, we emit code that looks like this:
1322  // F0 = malloc(field0)
1323  // F1 = malloc(field1)
1324  // F2 = malloc(field2)
1325  // if (F0 == 0 || F1 == 0 || F2 == 0) {
1326  // if (F0) { free(F0); F0 = 0; }
1327  // if (F1) { free(F1); F1 = 0; }
1328  // if (F2) { free(F2); F2 = 0; }
1329  // }
1330  // The malloc can also fail if its argument is too large.
1331  Constant *ConstantZero = ConstantInt::get(CI->getArgOperand(0)->getType(), 0);
1332  Value *RunningOr = new ICmpInst(CI, ICmpInst::ICMP_SLT, CI->getArgOperand(0),
1333  ConstantZero, "isneg");
1334  for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) {
1335  Value *Cond = new ICmpInst(CI, ICmpInst::ICMP_EQ, FieldMallocs[i],
1336  Constant::getNullValue(FieldMallocs[i]->getType()),
1337  "isnull");
1338  RunningOr = BinaryOperator::CreateOr(RunningOr, Cond, "tmp", CI);
1339  }
1340 
1341  // Split the basic block at the old malloc.
1342  BasicBlock *OrigBB = CI->getParent();
1343  BasicBlock *ContBB =
1344  OrigBB->splitBasicBlock(CI->getIterator(), "malloc_cont");
1345 
1346  // Create the block to check the first condition. Put all these blocks at the
1347  // end of the function as they are unlikely to be executed.
1348  BasicBlock *NullPtrBlock = BasicBlock::Create(OrigBB->getContext(),
1349  "malloc_ret_null",
1350  OrigBB->getParent());
1351 
1352  // Remove the uncond branch from OrigBB to ContBB, turning it into a cond
1353  // branch on RunningOr.
1354  OrigBB->getTerminator()->eraseFromParent();
1355  BranchInst::Create(NullPtrBlock, ContBB, RunningOr, OrigBB);
1356 
1357  // Within the NullPtrBlock, we need to emit a comparison and branch for each
1358  // pointer, because some may be null while others are not.
1359  for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) {
1360  Value *GVVal = new LoadInst(FieldGlobals[i], "tmp", NullPtrBlock);
1361  Value *Cmp = new ICmpInst(*NullPtrBlock, ICmpInst::ICMP_NE, GVVal,
1362  Constant::getNullValue(GVVal->getType()));
1363  BasicBlock *FreeBlock = BasicBlock::Create(Cmp->getContext(), "free_it",
1364  OrigBB->getParent());
1365  BasicBlock *NextBlock = BasicBlock::Create(Cmp->getContext(), "next",
1366  OrigBB->getParent());
1367  Instruction *BI = BranchInst::Create(FreeBlock, NextBlock,
1368  Cmp, NullPtrBlock);
1369 
1370  // Fill in FreeBlock.
1371  CallInst::CreateFree(GVVal, OpBundles, BI);
1372  new StoreInst(Constant::getNullValue(GVVal->getType()), FieldGlobals[i],
1373  FreeBlock);
1374  BranchInst::Create(NextBlock, FreeBlock);
1375 
1376  NullPtrBlock = NextBlock;
1377  }
1378 
1379  BranchInst::Create(ContBB, NullPtrBlock);
1380 
1381  // CI is no longer needed, remove it.
1382  CI->eraseFromParent();
1383 
1384  /// As we process loads, if we can't immediately update all uses of the load,
1385  /// keep track of what scalarized loads are inserted for a given load.
1386  DenseMap<Value *, std::vector<Value *>> InsertedScalarizedValues;
1387  InsertedScalarizedValues[GV] = FieldGlobals;
1388 
1389  std::vector<std::pair<PHINode *, unsigned>> PHIsToRewrite;
1390 
1391  // Okay, the malloc site is completely handled. All of the uses of GV are now
1392  // loads, and all uses of those loads are simple. Rewrite them to use loads
1393  // of the per-field globals instead.
1394  for (auto UI = GV->user_begin(), E = GV->user_end(); UI != E;) {
1395  Instruction *User = cast<Instruction>(*UI++);
1396 
1397  if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
1398  RewriteUsesOfLoadForHeapSRoA(LI, InsertedScalarizedValues, PHIsToRewrite);
1399  continue;
1400  }
1401 
1402  // Must be a store of null.
1403  StoreInst *SI = cast<StoreInst>(User);
1404  assert(isa<ConstantPointerNull>(SI->getOperand(0)) &&
1405  "Unexpected heap-sra user!");
1406 
1407  // Insert a store of null into each global.
1408  for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) {
1409  Type *ValTy = cast<GlobalValue>(FieldGlobals[i])->getValueType();
1410  Constant *Null = Constant::getNullValue(ValTy);
1411  new StoreInst(Null, FieldGlobals[i], SI);
1412  }
1413  // Erase the original store.
1414  SI->eraseFromParent();
1415  }
1416 
1417  // While we have PHIs that are interesting to rewrite, do it.
1418  while (!PHIsToRewrite.empty()) {
1419  PHINode *PN = PHIsToRewrite.back().first;
1420  unsigned FieldNo = PHIsToRewrite.back().second;
1421  PHIsToRewrite.pop_back();
1422  PHINode *FieldPN = cast<PHINode>(InsertedScalarizedValues[PN][FieldNo]);
1423  assert(FieldPN->getNumIncomingValues() == 0 &&"Already processed this phi");
1424 
1425  // Add all the incoming values. This can materialize more phis.
1426  for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1427  Value *InVal = PN->getIncomingValue(i);
1428  InVal = GetHeapSROAValue(InVal, FieldNo, InsertedScalarizedValues,
1429  PHIsToRewrite);
1430  FieldPN->addIncoming(InVal, PN->getIncomingBlock(i));
1431  }
1432  }
1433 
1434  // Drop all inter-phi links and any loads that made it this far.
1435  for (DenseMap<Value *, std::vector<Value *>>::iterator
1436  I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end();
1437  I != E; ++I) {
1438  if (PHINode *PN = dyn_cast<PHINode>(I->first))
1439  PN->dropAllReferences();
1440  else if (LoadInst *LI = dyn_cast<LoadInst>(I->first))
1441  LI->dropAllReferences();
1442  }
1443 
1444  // Delete all the phis and loads now that inter-references are dead.
1445  for (DenseMap<Value *, std::vector<Value *>>::iterator
1446  I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end();
1447  I != E; ++I) {
1448  if (PHINode *PN = dyn_cast<PHINode>(I->first))
1449  PN->eraseFromParent();
1450  else if (LoadInst *LI = dyn_cast<LoadInst>(I->first))
1451  LI->eraseFromParent();
1452  }
1453 
1454  // The old global is now dead, remove it.
1455  GV->eraseFromParent();
1456 
1457  ++NumHeapSRA;
1458  return cast<GlobalVariable>(FieldGlobals[0]);
1459 }
1460 
1461 /// This function is called when we see a pointer global variable with a single
1462 /// value stored it that is a malloc or cast of malloc.
1464  Type *AllocTy,
1465  AtomicOrdering Ordering,
1466  const DataLayout &DL,
1467  TargetLibraryInfo *TLI) {
1468  // If this is a malloc of an abstract type, don't touch it.
1469  if (!AllocTy->isSized())
1470  return false;
1471 
1472  // We can't optimize this global unless all uses of it are *known* to be
1473  // of the malloc value, not of the null initializer value (consider a use
1474  // that compares the global's value against zero to see if the malloc has
1475  // been reached). To do this, we check to see if all uses of the global
1476  // would trap if the global were null: this proves that they must all
1477  // happen after the malloc.
1479  return false;
1480 
1481  // We can't optimize this if the malloc itself is used in a complex way,
1482  // for example, being stored into multiple globals. This allows the
1483  // malloc to be stored into the specified global, loaded icmp'd, and
1484  // GEP'd. These are all things we could transform to using the global
1485  // for.
1487  if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(CI, GV, PHIs))
1488  return false;
1489 
1490  // If we have a global that is only initialized with a fixed size malloc,
1491  // transform the program to use global memory instead of malloc'd memory.
1492  // This eliminates dynamic allocation, avoids an indirection accessing the
1493  // data, and exposes the resultant global to further GlobalOpt.
1494  // We cannot optimize the malloc if we cannot determine malloc array size.
1495  Value *NElems = getMallocArraySize(CI, DL, TLI, true);
1496  if (!NElems)
1497  return false;
1498 
1499  if (ConstantInt *NElements = dyn_cast<ConstantInt>(NElems))
1500  // Restrict this transformation to only working on small allocations
1501  // (2048 bytes currently), as we don't want to introduce a 16M global or
1502  // something.
1503  if (NElements->getZExtValue() * DL.getTypeAllocSize(AllocTy) < 2048) {
1504  OptimizeGlobalAddressOfMalloc(GV, CI, AllocTy, NElements, DL, TLI);
1505  return true;
1506  }
1507 
1508  // If the allocation is an array of structures, consider transforming this
1509  // into multiple malloc'd arrays, one for each field. This is basically
1510  // SRoA for malloc'd memory.
1511 
1512  if (Ordering != AtomicOrdering::NotAtomic)
1513  return false;
1514 
1515  // If this is an allocation of a fixed size array of structs, analyze as a
1516  // variable size array. malloc [100 x struct],1 -> malloc struct, 100
1517  if (NElems == ConstantInt::get(CI->getArgOperand(0)->getType(), 1))
1518  if (ArrayType *AT = dyn_cast<ArrayType>(AllocTy))
1519  AllocTy = AT->getElementType();
1520 
1521  StructType *AllocSTy = dyn_cast<StructType>(AllocTy);
1522  if (!AllocSTy)
1523  return false;
1524 
1525  // This the structure has an unreasonable number of fields, leave it
1526  // alone.
1527  if (AllocSTy->getNumElements() <= 16 && AllocSTy->getNumElements() != 0 &&
1529 
1530  // If this is a fixed size array, transform the Malloc to be an alloc of
1531  // structs. malloc [100 x struct],1 -> malloc struct, 100
1532  if (ArrayType *AT = dyn_cast<ArrayType>(getMallocAllocatedType(CI, TLI))) {
1533  Type *IntPtrTy = DL.getIntPtrType(CI->getType());
1534  unsigned TypeSize = DL.getStructLayout(AllocSTy)->getSizeInBytes();
1535  Value *AllocSize = ConstantInt::get(IntPtrTy, TypeSize);
1536  Value *NumElements = ConstantInt::get(IntPtrTy, AT->getNumElements());
1538  CI->getOperandBundlesAsDefs(OpBundles);
1539  Instruction *Malloc =
1540  CallInst::CreateMalloc(CI, IntPtrTy, AllocSTy, AllocSize, NumElements,
1541  OpBundles, nullptr, CI->getName());
1542  Instruction *Cast = new BitCastInst(Malloc, CI->getType(), "tmp", CI);
1543  CI->replaceAllUsesWith(Cast);
1544  CI->eraseFromParent();
1545  if (BitCastInst *BCI = dyn_cast<BitCastInst>(Malloc))
1546  CI = cast<CallInst>(BCI->getOperand(0));
1547  else
1548  CI = cast<CallInst>(Malloc);
1549  }
1550 
1551  PerformHeapAllocSRoA(GV, CI, getMallocArraySize(CI, DL, TLI, true), DL,
1552  TLI);
1553  return true;
1554  }
1555 
1556  return false;
1557 }
1558 
1559 // Try to optimize globals based on the knowledge that only one value (besides
1560 // its initializer) is ever stored to the global.
1561 static bool optimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal,
1562  AtomicOrdering Ordering,
1563  const DataLayout &DL,
1564  TargetLibraryInfo *TLI) {
1565  // Ignore no-op GEPs and bitcasts.
1566  StoredOnceVal = StoredOnceVal->stripPointerCasts();
1567 
1568  // If we are dealing with a pointer global that is initialized to null and
1569  // only has one (non-null) value stored into it, then we can optimize any
1570  // users of the loaded value (often calls and loads) that would trap if the
1571  // value was null.
1572  if (GV->getInitializer()->getType()->isPointerTy() &&
1573  GV->getInitializer()->isNullValue() &&
1575  nullptr /* F */,
1577  if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
1578  if (GV->getInitializer()->getType() != SOVC->getType())
1579  SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
1580 
1581  // Optimize away any trapping uses of the loaded value.
1582  if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, DL, TLI))
1583  return true;
1584  } else if (CallInst *CI = extractMallocCall(StoredOnceVal, TLI)) {
1585  Type *MallocType = getMallocAllocatedType(CI, TLI);
1586  if (MallocType && tryToOptimizeStoreOfMallocToGlobal(GV, CI, MallocType,
1587  Ordering, DL, TLI))
1588  return true;
1589  }
1590  }
1591 
1592  return false;
1593 }
1594 
1595 /// At this point, we have learned that the only two values ever stored into GV
1596 /// are its initializer and OtherVal. See if we can shrink the global into a
1597 /// boolean and select between the two values whenever it is used. This exposes
1598 /// the values to other scalar optimizations.
1600  Type *GVElType = GV->getValueType();
1601 
1602  // If GVElType is already i1, it is already shrunk. If the type of the GV is
1603  // an FP value, pointer or vector, don't do this optimization because a select
1604  // between them is very expensive and unlikely to lead to later
1605  // simplification. In these cases, we typically end up with "cond ? v1 : v2"
1606  // where v1 and v2 both require constant pool loads, a big loss.
1607  if (GVElType == Type::getInt1Ty(GV->getContext()) ||
1608  GVElType->isFloatingPointTy() ||
1609  GVElType->isPointerTy() || GVElType->isVectorTy())
1610  return false;
1611 
1612  // Walk the use list of the global seeing if all the uses are load or store.
1613  // If there is anything else, bail out.
1614  for (User *U : GV->users())
1615  if (!isa<LoadInst>(U) && !isa<StoreInst>(U))
1616  return false;
1617 
1618  LLVM_DEBUG(dbgs() << " *** SHRINKING TO BOOL: " << *GV << "\n");
1619 
1620  // Create the new global, initializing it to false.
1622  false,
1625  GV->getName()+".b",
1626  GV->getThreadLocalMode(),
1627  GV->getType()->getAddressSpace());
1628  NewGV->copyAttributesFrom(GV);
1629  GV->getParent()->getGlobalList().insert(GV->getIterator(), NewGV);
1630 
1631  Constant *InitVal = GV->getInitializer();
1632  assert(InitVal->getType() != Type::getInt1Ty(GV->getContext()) &&
1633  "No reason to shrink to bool!");
1634 
1636  GV->getDebugInfo(GVs);
1637 
1638  // If initialized to zero and storing one into the global, we can use a cast
1639  // instead of a select to synthesize the desired value.
1640  bool IsOneZero = false;
1641  bool EmitOneOrZero = true;
1642  if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal)){
1643  IsOneZero = InitVal->isNullValue() && CI->isOne();
1644 
1645  if (ConstantInt *CIInit = dyn_cast<ConstantInt>(GV->getInitializer())){
1646  uint64_t ValInit = CIInit->getZExtValue();
1647  uint64_t ValOther = CI->getZExtValue();
1648  uint64_t ValMinus = ValOther - ValInit;
1649 
1650  for(auto *GVe : GVs){
1651  DIGlobalVariable *DGV = GVe->getVariable();
1652  DIExpression *E = GVe->getExpression();
1653 
1654  // It is expected that the address of global optimized variable is on
1655  // top of the stack. After optimization, value of that variable will
1656  // be ether 0 for initial value or 1 for other value. The following
1657  // expression should return constant integer value depending on the
1658  // value at global object address:
1659  // val * (ValOther - ValInit) + ValInit:
1660  // DW_OP_deref DW_OP_constu <ValMinus>
1661  // DW_OP_mul DW_OP_constu <ValInit> DW_OP_plus DW_OP_stack_value
1663  dwarf::DW_OP_deref, dwarf::DW_OP_constu, ValMinus,
1664  dwarf::DW_OP_mul, dwarf::DW_OP_constu, ValInit,
1665  dwarf::DW_OP_plus};
1669  NewGV->addDebugInfo(DGVE);
1670  }
1671  EmitOneOrZero = false;
1672  }
1673  }
1674 
1675  if (EmitOneOrZero) {
1676  // FIXME: This will only emit address for debugger on which will
1677  // be written only 0 or 1.
1678  for(auto *GV : GVs)
1679  NewGV->addDebugInfo(GV);
1680  }
1681 
1682  while (!GV->use_empty()) {
1683  Instruction *UI = cast<Instruction>(GV->user_back());
1684  if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
1685  // Change the store into a boolean store.
1686  bool StoringOther = SI->getOperand(0) == OtherVal;
1687  // Only do this if we weren't storing a loaded value.
1688  Value *StoreVal;
1689  if (StoringOther || SI->getOperand(0) == InitVal) {
1690  StoreVal = ConstantInt::get(Type::getInt1Ty(GV->getContext()),
1691  StoringOther);
1692  } else {
1693  // Otherwise, we are storing a previously loaded copy. To do this,
1694  // change the copy from copying the original value to just copying the
1695  // bool.
1696  Instruction *StoredVal = cast<Instruction>(SI->getOperand(0));
1697 
1698  // If we've already replaced the input, StoredVal will be a cast or
1699  // select instruction. If not, it will be a load of the original
1700  // global.
1701  if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
1702  assert(LI->getOperand(0) == GV && "Not a copy!");
1703  // Insert a new load, to preserve the saved value.
1704  StoreVal = new LoadInst(NewGV, LI->getName()+".b", false, 0,
1705  LI->getOrdering(), LI->getSyncScopeID(), LI);
1706  } else {
1707  assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) &&
1708  "This is not a form that we understand!");
1709  StoreVal = StoredVal->getOperand(0);
1710  assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!");
1711  }
1712  }
1713  new StoreInst(StoreVal, NewGV, false, 0,
1714  SI->getOrdering(), SI->getSyncScopeID(), SI);
1715  } else {
1716  // Change the load into a load of bool then a select.
1717  LoadInst *LI = cast<LoadInst>(UI);
1718  LoadInst *NLI = new LoadInst(NewGV, LI->getName()+".b", false, 0,
1719  LI->getOrdering(), LI->getSyncScopeID(), LI);
1720  Value *NSI;
1721  if (IsOneZero)
1722  NSI = new ZExtInst(NLI, LI->getType(), "", LI);
1723  else
1724  NSI = SelectInst::Create(NLI, OtherVal, InitVal, "", LI);
1725  NSI->takeName(LI);
1726  LI->replaceAllUsesWith(NSI);
1727  }
1728  UI->eraseFromParent();
1729  }
1730 
1731  // Retain the name of the old global variable. People who are debugging their
1732  // programs may expect these variables to be named the same.
1733  NewGV->takeName(GV);
1734  GV->eraseFromParent();
1735  return true;
1736 }
1737 
1738 static bool deleteIfDead(
1739  GlobalValue &GV, SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
1741 
1742  if (!GV.isDiscardableIfUnused() && !GV.isDeclaration())
1743  return false;
1744 
1745  if (const Comdat *C = GV.getComdat())
1746  if (!GV.hasLocalLinkage() && NotDiscardableComdats.count(C))
1747  return false;
1748 
1749  bool Dead;
1750  if (auto *F = dyn_cast<Function>(&GV))
1751  Dead = (F->isDeclaration() && F->use_empty()) || F->isDefTriviallyDead();
1752  else
1753  Dead = GV.use_empty();
1754  if (!Dead)
1755  return false;
1756 
1757  LLVM_DEBUG(dbgs() << "GLOBAL DEAD: " << GV << "\n");
1758  GV.eraseFromParent();
1759  ++NumDeleted;
1760  return true;
1761 }
1762 
1764  const Function *F, GlobalValue *GV,
1765  function_ref<DominatorTree &(Function &)> LookupDomTree) {
1766  // Find all uses of GV. We expect them all to be in F, and if we can't
1767  // identify any of the uses we bail out.
1768  //
1769  // On each of these uses, identify if the memory that GV points to is
1770  // used/required/live at the start of the function. If it is not, for example
1771  // if the first thing the function does is store to the GV, the GV can
1772  // possibly be demoted.
1773  //
1774  // We don't do an exhaustive search for memory operations - simply look
1775  // through bitcasts as they're quite common and benign.
1776  const DataLayout &DL = GV->getParent()->getDataLayout();
1779  for (auto *U : GV->users()) {
1780  if (Operator::getOpcode(U) == Instruction::BitCast) {
1781  for (auto *UU : U->users()) {
1782  if (auto *LI = dyn_cast<LoadInst>(UU))
1783  Loads.push_back(LI);
1784  else if (auto *SI = dyn_cast<StoreInst>(UU))
1785  Stores.push_back(SI);
1786  else
1787  return false;
1788  }
1789  continue;
1790  }
1791 
1793  if (!I)
1794  return false;
1795  assert(I->getParent()->getParent() == F);
1796 
1797  if (auto *LI = dyn_cast<LoadInst>(I))
1798  Loads.push_back(LI);
1799  else if (auto *SI = dyn_cast<StoreInst>(I))
1800  Stores.push_back(SI);
1801  else
1802  return false;
1803  }
1804 
1805  // We have identified all uses of GV into loads and stores. Now check if all
1806  // of them are known not to depend on the value of the global at the function
1807  // entry point. We do this by ensuring that every load is dominated by at
1808  // least one store.
1809  auto &DT = LookupDomTree(*const_cast<Function *>(F));
1810 
1811  // The below check is quadratic. Check we're not going to do too many tests.
1812  // FIXME: Even though this will always have worst-case quadratic time, we
1813  // could put effort into minimizing the average time by putting stores that
1814  // have been shown to dominate at least one load at the beginning of the
1815  // Stores array, making subsequent dominance checks more likely to succeed
1816  // early.
1817  //
1818  // The threshold here is fairly large because global->local demotion is a
1819  // very powerful optimization should it fire.
1820  const unsigned Threshold = 100;
1821  if (Loads.size() * Stores.size() > Threshold)
1822  return false;
1823 
1824  for (auto *L : Loads) {
1825  auto *LTy = L->getType();
1826  if (none_of(Stores, [&](const StoreInst *S) {
1827  auto *STy = S->getValueOperand()->getType();
1828  // The load is only dominated by the store if DomTree says so
1829  // and the number of bits loaded in L is less than or equal to
1830  // the number of bits stored in S.
1831  return DT.dominates(S, L) &&
1832  DL.getTypeStoreSize(LTy) <= DL.getTypeStoreSize(STy);
1833  }))
1834  return false;
1835  }
1836  // All loads have known dependences inside F, so the global can be localized.
1837  return true;
1838 }
1839 
1840 /// C may have non-instruction users. Can all of those users be turned into
1841 /// instructions?
1843  // We don't do this exhaustively. The most common pattern that we really need
1844  // to care about is a constant GEP or constant bitcast - so just looking
1845  // through one single ConstantExpr.
1846  //
1847  // The set of constants that this function returns true for must be able to be
1848  // handled by makeAllConstantUsesInstructions.
1849  for (auto *U : C->users()) {
1850  if (isa<Instruction>(U))
1851  continue;
1852  if (!isa<ConstantExpr>(U))
1853  // Non instruction, non-constantexpr user; cannot convert this.
1854  return false;
1855  for (auto *UU : U->users())
1856  if (!isa<Instruction>(UU))
1857  // A constantexpr used by another constant. We don't try and recurse any
1858  // further but just bail out at this point.
1859  return false;
1860  }
1861 
1862  return true;
1863 }
1864 
1865 /// C may have non-instruction users, and
1866 /// allNonInstructionUsersCanBeMadeInstructions has returned true. Convert the
1867 /// non-instruction users to instructions.
1870  for (auto *U : C->users()) {
1871  if (isa<ConstantExpr>(U))
1872  Users.push_back(cast<ConstantExpr>(U));
1873  else
1874  // We should never get here; allNonInstructionUsersCanBeMadeInstructions
1875  // should not have returned true for C.
1876  assert(
1877  isa<Instruction>(U) &&
1878  "Can't transform non-constantexpr non-instruction to instruction!");
1879  }
1880 
1881  SmallVector<Value*,4> UUsers;
1882  for (auto *U : Users) {
1883  UUsers.clear();
1884  for (auto *UU : U->users())
1885  UUsers.push_back(UU);
1886  for (auto *UU : UUsers) {
1887  Instruction *UI = cast<Instruction>(UU);
1888  Instruction *NewU = U->getAsInstruction();
1889  NewU->insertBefore(UI);
1890  UI->replaceUsesOfWith(U, NewU);
1891  }
1892  // We've replaced all the uses, so destroy the constant. (destroyConstant
1893  // will update value handles and metadata.)
1894  U->destroyConstant();
1895  }
1896 }
1897 
1898 /// Analyze the specified global variable and optimize
1899 /// it if possible. If we make a change, return true.
1901  GlobalVariable *GV, const GlobalStatus &GS, TargetLibraryInfo *TLI,
1902  function_ref<DominatorTree &(Function &)> LookupDomTree) {
1903  auto &DL = GV->getParent()->getDataLayout();
1904  // If this is a first class global and has only one accessing function and
1905  // this function is non-recursive, we replace the global with a local alloca
1906  // in this function.
1907  //
1908  // NOTE: It doesn't make sense to promote non-single-value types since we
1909  // are just replacing static memory to stack memory.
1910  //
1911  // If the global is in different address space, don't bring it to stack.
1913  GS.AccessingFunction &&
1914  GV->getValueType()->isSingleValueType() &&
1915  GV->getType()->getAddressSpace() == 0 &&
1916  !GV->isExternallyInitialized() &&
1920  LookupDomTree)) {
1921  const DataLayout &DL = GV->getParent()->getDataLayout();
1922 
1923  LLVM_DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV << "\n");
1924  Instruction &FirstI = const_cast<Instruction&>(*GS.AccessingFunction
1925  ->getEntryBlock().begin());
1926  Type *ElemTy = GV->getValueType();
1927  // FIXME: Pass Global's alignment when globals have alignment
1928  AllocaInst *Alloca = new AllocaInst(ElemTy, DL.getAllocaAddrSpace(), nullptr,
1929  GV->getName(), &FirstI);
1930  if (!isa<UndefValue>(GV->getInitializer()))
1931  new StoreInst(GV->getInitializer(), Alloca, &FirstI);
1932 
1934 
1935  GV->replaceAllUsesWith(Alloca);
1936  GV->eraseFromParent();
1937  ++NumLocalized;
1938  return true;
1939  }
1940 
1941  // If the global is never loaded (but may be stored to), it is dead.
1942  // Delete it now.
1943  if (!GS.IsLoaded) {
1944  LLVM_DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV << "\n");
1945 
1946  bool Changed;
1947  if (isLeakCheckerRoot(GV)) {
1948  // Delete any constant stores to the global.
1949  Changed = CleanupPointerRootUsers(GV, TLI);
1950  } else {
1951  // Delete any stores we can find to the global. We may not be able to
1952  // make it completely dead though.
1953  Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
1954  }
1955 
1956  // If the global is dead now, delete it.
1957  if (GV->use_empty()) {
1958  GV->eraseFromParent();
1959  ++NumDeleted;
1960  Changed = true;
1961  }
1962  return Changed;
1963 
1964  }
1966  LLVM_DEBUG(dbgs() << "MARKING CONSTANT: " << *GV << "\n");
1967  GV->setConstant(true);
1968 
1969  // Clean up any obviously simplifiable users now.
1970  CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
1971 
1972  // If the global is dead now, just nuke it.
1973  if (GV->use_empty()) {
1974  LLVM_DEBUG(dbgs() << " *** Marking constant allowed us to simplify "
1975  << "all users and delete global!\n");
1976  GV->eraseFromParent();
1977  ++NumDeleted;
1978  return true;
1979  }
1980 
1981  // Fall through to the next check; see if we can optimize further.
1982  ++NumMarked;
1983  }
1984  if (!GV->getInitializer()->getType()->isSingleValueType()) {
1985  const DataLayout &DL = GV->getParent()->getDataLayout();
1986  if (SRAGlobal(GV, DL))
1987  return true;
1988  }
1990  // If the initial value for the global was an undef value, and if only
1991  // one other value was stored into it, we can just change the
1992  // initializer to be the stored value, then delete all stores to the
1993  // global. This allows us to mark it constant.
1994  if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue))
1995  if (isa<UndefValue>(GV->getInitializer())) {
1996  // Change the initial value here.
1997  GV->setInitializer(SOVConstant);
1998 
1999  // Clean up any obviously simplifiable users now.
2000  CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
2001 
2002  if (GV->use_empty()) {
2003  LLVM_DEBUG(dbgs() << " *** Substituting initializer allowed us to "
2004  << "simplify all users and delete global!\n");
2005  GV->eraseFromParent();
2006  ++NumDeleted;
2007  }
2008  ++NumSubstitute;
2009  return true;
2010  }
2011 
2012  // Try to optimize globals based on the knowledge that only one value
2013  // (besides its initializer) is ever stored to the global.
2014  if (optimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, DL, TLI))
2015  return true;
2016 
2017  // Otherwise, if the global was not a boolean, we can shrink it to be a
2018  // boolean.
2019  if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) {
2020  if (GS.Ordering == AtomicOrdering::NotAtomic) {
2021  if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) {
2022  ++NumShrunkToBool;
2023  return true;
2024  }
2025  }
2026  }
2027  }
2028 
2029  return false;
2030 }
2031 
2032 /// Analyze the specified global variable and optimize it if possible. If we
2033 /// make a change, return true.
2034 static bool
2036  function_ref<DominatorTree &(Function &)> LookupDomTree) {
2037  if (GV.getName().startswith("llvm."))
2038  return false;
2039 
2040  GlobalStatus GS;
2041 
2042  if (GlobalStatus::analyzeGlobal(&GV, GS))
2043  return false;
2044 
2045  bool Changed = false;
2046  if (!GS.IsCompared && !GV.hasGlobalUnnamedAddr()) {
2047  auto NewUnnamedAddr = GV.hasLocalLinkage() ? GlobalValue::UnnamedAddr::Global
2049  if (NewUnnamedAddr != GV.getUnnamedAddr()) {
2050  GV.setUnnamedAddr(NewUnnamedAddr);
2051  NumUnnamed++;
2052  Changed = true;
2053  }
2054  }
2055 
2056  // Do more involved optimizations if the global is internal.
2057  if (!GV.hasLocalLinkage())
2058  return Changed;
2059 
2060  auto *GVar = dyn_cast<GlobalVariable>(&GV);
2061  if (!GVar)
2062  return Changed;
2063 
2064  if (GVar->isConstant() || !GVar->hasInitializer())
2065  return Changed;
2066 
2067  return processInternalGlobal(GVar, GS, TLI, LookupDomTree) || Changed;
2068 }
2069 
2070 /// Walk all of the direct calls of the specified function, changing them to
2071 /// FastCC.
2073  for (User *U : F->users()) {
2074  if (isa<BlockAddress>(U))
2075  continue;
2076  CallSite CS(cast<Instruction>(U));
2078  }
2079 }
2080 
2082  // There can be at most one attribute set with a nest attribute.
2083  unsigned NestIndex;
2084  if (Attrs.hasAttrSomewhere(Attribute::Nest, &NestIndex))
2085  return Attrs.removeAttribute(C, NestIndex, Attribute::Nest);
2086  return Attrs;
2087 }
2088 
2091  for (User *U : F->users()) {
2092  if (isa<BlockAddress>(U))
2093  continue;
2094  CallSite CS(cast<Instruction>(U));
2096  }
2097 }
2098 
2099 /// Return true if this is a calling convention that we'd like to change. The
2100 /// idea here is that we don't want to mess with the convention if the user
2101 /// explicitly requested something with performance implications like coldcc,
2102 /// GHC, or anyregcc.
2103 static bool hasChangeableCC(Function *F) {
2104  CallingConv::ID CC = F->getCallingConv();
2105 
2106  // FIXME: Is it worth transforming x86_stdcallcc and x86_fastcallcc?
2107  if (CC != CallingConv::C && CC != CallingConv::X86_ThisCall)
2108  return false;
2109 
2110  // Don't break the invariant that the inalloca parameter is the only parameter
2111  // passed in memory.
2112  // FIXME: GlobalOpt should remove inalloca when possible and hoist the dynamic
2113  // alloca it uses to the entry block if possible.
2114  if (F->getAttributes().hasAttrSomewhere(Attribute::InAlloca))
2115  return false;
2116 
2117  // FIXME: Change CC for the whole chain of musttail calls when possible.
2118  //
2119  // Can't change CC of the function that either has musttail calls, or is a
2120  // musttail callee itself
2121  for (User *U : F->users()) {
2122  if (isa<BlockAddress>(U))
2123  continue;
2124  CallInst* CI = dyn_cast<CallInst>(U);
2125  if (!CI)
2126  continue;
2127 
2128  if (CI->isMustTailCall())
2129  return false;
2130  }
2131 
2132  for (BasicBlock &BB : *F)
2133  if (BB.getTerminatingMustTailCall())
2134  return false;
2135 
2136  return true;
2137 }
2138 
2139 /// Return true if the block containing the call site has a BlockFrequency of
2140 /// less than ColdCCRelFreq% of the entry block.
2141 static bool isColdCallSite(CallSite CS, BlockFrequencyInfo &CallerBFI) {
2142  const BranchProbability ColdProb(ColdCCRelFreq, 100);
2143  auto CallSiteBB = CS.getInstruction()->getParent();
2144  auto CallSiteFreq = CallerBFI.getBlockFreq(CallSiteBB);
2145  auto CallerEntryFreq =
2146  CallerBFI.getBlockFreq(&(CS.getCaller()->getEntryBlock()));
2147  return CallSiteFreq < CallerEntryFreq * ColdProb;
2148 }
2149 
2150 // This function checks if the input function F is cold at all call sites. It
2151 // also looks each call site's containing function, returning false if the
2152 // caller function contains other non cold calls. The input vector AllCallsCold
2153 // contains a list of functions that only have call sites in cold blocks.
2154 static bool
2157  const std::vector<Function *> &AllCallsCold) {
2158 
2159  if (F.user_empty())
2160  return false;
2161 
2162  for (User *U : F.users()) {
2163  if (isa<BlockAddress>(U))
2164  continue;
2165 
2166  CallSite CS(cast<Instruction>(U));
2167  Function *CallerFunc = CS.getInstruction()->getParent()->getParent();
2168  BlockFrequencyInfo &CallerBFI = GetBFI(*CallerFunc);
2169  if (!isColdCallSite(CS, CallerBFI))
2170  return false;
2171  auto It = std::find(AllCallsCold.begin(), AllCallsCold.end(), CallerFunc);
2172  if (It == AllCallsCold.end())
2173  return false;
2174  }
2175  return true;
2176 }
2177 
2179  for (User *U : F->users()) {
2180  if (isa<BlockAddress>(U))
2181  continue;
2182  CallSite CS(cast<Instruction>(U));
2184  }
2185 }
2186 
2187 // This function iterates over all the call instructions in the input Function
2188 // and checks that all call sites are in cold blocks and are allowed to use the
2189 // coldcc calling convention.
2190 static bool
2192  function_ref<BlockFrequencyInfo &(Function &)> GetBFI) {
2193  for (BasicBlock &BB : F) {
2194  for (Instruction &I : BB) {
2195  if (CallInst *CI = dyn_cast<CallInst>(&I)) {
2196  CallSite CS(cast<Instruction>(CI));
2197  // Skip over isline asm instructions since they aren't function calls.
2198  if (CI->isInlineAsm())
2199  continue;
2200  Function *CalledFn = CI->getCalledFunction();
2201  if (!CalledFn)
2202  return false;
2203  if (!CalledFn->hasLocalLinkage())
2204  return false;
2205  // Skip over instrinsics since they won't remain as function calls.
2206  if (CalledFn->getIntrinsicID() != Intrinsic::not_intrinsic)
2207  continue;
2208  // Check if it's valid to use coldcc calling convention.
2209  if (!hasChangeableCC(CalledFn) || CalledFn->isVarArg() ||
2210  CalledFn->hasAddressTaken())
2211  return false;
2212  BlockFrequencyInfo &CallerBFI = GetBFI(F);
2213  if (!isColdCallSite(CS, CallerBFI))
2214  return false;
2215  }
2216  }
2217  }
2218  return true;
2219 }
2220 
2221 static bool
2225  function_ref<DominatorTree &(Function &)> LookupDomTree,
2226  SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
2227 
2228  bool Changed = false;
2229 
2230  std::vector<Function *> AllCallsCold;
2231  for (Module::iterator FI = M.begin(), E = M.end(); FI != E;) {
2232  Function *F = &*FI++;
2233  if (hasOnlyColdCalls(*F, GetBFI))
2234  AllCallsCold.push_back(F);
2235  }
2236 
2237  // Optimize functions.
2238  for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
2239  Function *F = &*FI++;
2240 
2241  // Don't perform global opt pass on naked functions; we don't want fast
2242  // calling conventions for naked functions.
2243  if (F->hasFnAttribute(Attribute::Naked))
2244  continue;
2245 
2246  // Functions without names cannot be referenced outside this module.
2247  if (!F->hasName() && !F->isDeclaration() && !F->hasLocalLinkage())
2249 
2250  if (deleteIfDead(*F, NotDiscardableComdats)) {
2251  Changed = true;
2252  continue;
2253  }
2254 
2255  // LLVM's definition of dominance allows instructions that are cyclic
2256  // in unreachable blocks, e.g.:
2257  // %pat = select i1 %condition, @global, i16* %pat
2258  // because any instruction dominates an instruction in a block that's
2259  // not reachable from entry.
2260  // So, remove unreachable blocks from the function, because a) there's
2261  // no point in analyzing them and b) GlobalOpt should otherwise grow
2262  // some more complicated logic to break these cycles.
2263  // Removing unreachable blocks might invalidate the dominator so we
2264  // recalculate it.
2265  if (!F->isDeclaration()) {
2266  if (removeUnreachableBlocks(*F)) {
2267  auto &DT = LookupDomTree(*F);
2268  DT.recalculate(*F);
2269  Changed = true;
2270  }
2271  }
2272 
2273  Changed |= processGlobal(*F, TLI, LookupDomTree);
2274 
2275  if (!F->hasLocalLinkage())
2276  continue;
2277 
2278  if (hasChangeableCC(F) && !F->isVarArg() && !F->hasAddressTaken()) {
2279  NumInternalFunc++;
2280  TargetTransformInfo &TTI = GetTTI(*F);
2281  // Change the calling convention to coldcc if either stress testing is
2282  // enabled or the target would like to use coldcc on functions which are
2283  // cold at all call sites and the callers contain no other non coldcc
2284  // calls.
2285  if (EnableColdCCStressTest ||
2286  (isValidCandidateForColdCC(*F, GetBFI, AllCallsCold) &&
2287  TTI.useColdCCForColdCall(*F))) {
2290  Changed = true;
2291  NumColdCC++;
2292  }
2293  }
2294 
2295  if (hasChangeableCC(F) && !F->isVarArg() &&
2296  !F->hasAddressTaken()) {
2297  // If this function has a calling convention worth changing, is not a
2298  // varargs function, and is only called directly, promote it to use the
2299  // Fast calling convention.
2302  ++NumFastCallFns;
2303  Changed = true;
2304  }
2305 
2306  if (F->getAttributes().hasAttrSomewhere(Attribute::Nest) &&
2307  !F->hasAddressTaken()) {
2308  // The function is not used by a trampoline intrinsic, so it is safe
2309  // to remove the 'nest' attribute.
2311  ++NumNestRemoved;
2312  Changed = true;
2313  }
2314  }
2315  return Changed;
2316 }
2317 
2318 static bool
2320  function_ref<DominatorTree &(Function &)> LookupDomTree,
2321  SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
2322  bool Changed = false;
2323 
2324  for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
2325  GVI != E; ) {
2326  GlobalVariable *GV = &*GVI++;
2327  // Global variables without names cannot be referenced outside this module.
2328  if (!GV->hasName() && !GV->isDeclaration() && !GV->hasLocalLinkage())
2330  // Simplify the initializer.
2331  if (GV->hasInitializer())
2332  if (auto *C = dyn_cast<Constant>(GV->getInitializer())) {
2333  auto &DL = M.getDataLayout();
2334  Constant *New = ConstantFoldConstant(C, DL, TLI);
2335  if (New && New != C)
2336  GV->setInitializer(New);
2337  }
2338 
2339  if (deleteIfDead(*GV, NotDiscardableComdats)) {
2340  Changed = true;
2341  continue;
2342  }
2343 
2344  Changed |= processGlobal(*GV, TLI, LookupDomTree);
2345  }
2346  return Changed;
2347 }
2348 
2349 /// Evaluate a piece of a constantexpr store into a global initializer. This
2350 /// returns 'Init' modified to reflect 'Val' stored into it. At this point, the
2351 /// GEP operands of Addr [0, OpNo) have been stepped into.
2353  ConstantExpr *Addr, unsigned OpNo) {
2354  // Base case of the recursion.
2355  if (OpNo == Addr->getNumOperands()) {
2356  assert(Val->getType() == Init->getType() && "Type mismatch!");
2357  return Val;
2358  }
2359 
2361  if (StructType *STy = dyn_cast<StructType>(Init->getType())) {
2362  // Break up the constant into its elements.
2363  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
2364  Elts.push_back(Init->getAggregateElement(i));
2365 
2366  // Replace the element that we are supposed to.
2367  ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo));
2368  unsigned Idx = CU->getZExtValue();
2369  assert(Idx < STy->getNumElements() && "Struct index out of range!");
2370  Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1);
2371 
2372  // Return the modified struct.
2373  return ConstantStruct::get(STy, Elts);
2374  }
2375 
2376  ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo));
2377  SequentialType *InitTy = cast<SequentialType>(Init->getType());
2378  uint64_t NumElts = InitTy->getNumElements();
2379 
2380  // Break up the array into elements.
2381  for (uint64_t i = 0, e = NumElts; i != e; ++i)
2382  Elts.push_back(Init->getAggregateElement(i));
2383 
2384  assert(CI->getZExtValue() < NumElts);
2385  Elts[CI->getZExtValue()] =
2386  EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1);
2387 
2388  if (Init->getType()->isArrayTy())
2389  return ConstantArray::get(cast<ArrayType>(InitTy), Elts);
2390  return ConstantVector::get(Elts);
2391 }
2392 
2393 /// We have decided that Addr (which satisfies the predicate
2394 /// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen.
2395 static void CommitValueTo(Constant *Val, Constant *Addr) {
2396  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
2397  assert(GV->hasInitializer());
2398  GV->setInitializer(Val);
2399  return;
2400  }
2401 
2402  ConstantExpr *CE = cast<ConstantExpr>(Addr);
2403  GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
2404  GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2));
2405 }
2406 
2407 /// Given a map of address -> value, where addresses are expected to be some form
2408 /// of either a global or a constant GEP, set the initializer for the address to
2409 /// be the value. This performs mostly the same function as CommitValueTo()
2410 /// and EvaluateStoreInto() but is optimized to be more efficient for the common
2411 /// case where the set of addresses are GEPs sharing the same underlying global,
2412 /// processing the GEPs in batches rather than individually.
2413 ///
2414 /// To give an example, consider the following C++ code adapted from the clang
2415 /// regression tests:
2416 /// struct S {
2417 /// int n = 10;
2418 /// int m = 2 * n;
2419 /// S(int a) : n(a) {}
2420 /// };
2421 ///
2422 /// template<typename T>
2423 /// struct U {
2424 /// T *r = &q;
2425 /// T q = 42;
2426 /// U *p = this;
2427 /// };
2428 ///
2429 /// U<S> e;
2430 ///
2431 /// The global static constructor for 'e' will need to initialize 'r' and 'p' of
2432 /// the outer struct, while also initializing the inner 'q' structs 'n' and 'm'
2433 /// members. This batch algorithm will simply use general CommitValueTo() method
2434 /// to handle the complex nested S struct initialization of 'q', before
2435 /// processing the outermost members in a single batch. Using CommitValueTo() to
2436 /// handle member in the outer struct is inefficient when the struct/array is
2437 /// very large as we end up creating and destroy constant arrays for each
2438 /// initialization.
2439 /// For the above case, we expect the following IR to be generated:
2440 ///
2441 /// %struct.U = type { %struct.S*, %struct.S, %struct.U* }
2442 /// %struct.S = type { i32, i32 }
2443 /// @e = global %struct.U { %struct.S* gep inbounds (%struct.U, %struct.U* @e,
2444 /// i64 0, i32 1),
2445 /// %struct.S { i32 42, i32 84 }, %struct.U* @e }
2446 /// The %struct.S { i32 42, i32 84 } inner initializer is treated as a complex
2447 /// constant expression, while the other two elements of @e are "simple".
2452  SimpleCEs.reserve(Mem.size());
2453 
2454  for (const auto &I : Mem) {
2455  if (auto *GV = dyn_cast<GlobalVariable>(I.first)) {
2456  GVs.push_back(std::make_pair(GV, I.second));
2457  } else {
2458  ConstantExpr *GEP = cast<ConstantExpr>(I.first);
2459  // We don't handle the deeply recursive case using the batch method.
2460  if (GEP->getNumOperands() > 3)
2461  ComplexCEs.push_back(std::make_pair(GEP, I.second));
2462  else
2463  SimpleCEs.push_back(std::make_pair(GEP, I.second));
2464  }
2465  }
2466 
2467  // The algorithm below doesn't handle cases like nested structs, so use the
2468  // slower fully general method if we have to.
2469  for (auto ComplexCE : ComplexCEs)
2470  CommitValueTo(ComplexCE.second, ComplexCE.first);
2471 
2472  for (auto GVPair : GVs) {
2473  assert(GVPair.first->hasInitializer());
2474  GVPair.first->setInitializer(GVPair.second);
2475  }
2476 
2477  if (SimpleCEs.empty())
2478  return;
2479 
2480  // We cache a single global's initializer elements in the case where the
2481  // subsequent address/val pair uses the same one. This avoids throwing away and
2482  // rebuilding the constant struct/vector/array just because one element is
2483  // modified at a time.
2485  Elts.reserve(SimpleCEs.size());
2486  GlobalVariable *CurrentGV = nullptr;
2487 
2488  auto commitAndSetupCache = [&](GlobalVariable *GV, bool Update) {
2489  Constant *Init = GV->getInitializer();
2490  Type *Ty = Init->getType();
2491  if (Update) {
2492  if (CurrentGV) {
2493  assert(CurrentGV && "Expected a GV to commit to!");
2494  Type *CurrentInitTy = CurrentGV->getInitializer()->getType();
2495  // We have a valid cache that needs to be committed.
2496  if (StructType *STy = dyn_cast<StructType>(CurrentInitTy))
2497  CurrentGV->setInitializer(ConstantStruct::get(STy, Elts));
2498  else if (ArrayType *ArrTy = dyn_cast<ArrayType>(CurrentInitTy))
2499  CurrentGV->setInitializer(ConstantArray::get(ArrTy, Elts));
2500  else
2501  CurrentGV->setInitializer(ConstantVector::get(Elts));
2502  }
2503  if (CurrentGV == GV)
2504  return;
2505  // Need to clear and set up cache for new initializer.
2506  CurrentGV = GV;
2507  Elts.clear();
2508  unsigned NumElts;
2509  if (auto *STy = dyn_cast<StructType>(Ty))
2510  NumElts = STy->getNumElements();
2511  else
2512  NumElts = cast<SequentialType>(Ty)->getNumElements();
2513  for (unsigned i = 0, e = NumElts; i != e; ++i)
2514  Elts.push_back(Init->getAggregateElement(i));
2515  }
2516  };
2517 
2518  for (auto CEPair : SimpleCEs) {
2519  ConstantExpr *GEP = CEPair.first;
2520  Constant *Val = CEPair.second;
2521 
2522  GlobalVariable *GV = cast<GlobalVariable>(GEP->getOperand(0));
2523  commitAndSetupCache(GV, GV != CurrentGV);
2524  ConstantInt *CI = cast<ConstantInt>(GEP->getOperand(2));
2525  Elts[CI->getZExtValue()] = Val;
2526  }
2527  // The last initializer in the list needs to be committed, others
2528  // will be committed on a new initializer being processed.
2529  commitAndSetupCache(CurrentGV, true);
2530 }
2531 
2532 /// Evaluate static constructors in the function, if we can. Return true if we
2533 /// can, false otherwise.
2535  TargetLibraryInfo *TLI) {
2536  // Call the function.
2537  Evaluator Eval(DL, TLI);
2538  Constant *RetValDummy;
2539  bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy,
2541 
2542  if (EvalSuccess) {
2543  ++NumCtorsEvaluated;
2544 
2545  // We succeeded at evaluation: commit the result.
2546  LLVM_DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
2547  << F->getName() << "' to "
2548  << Eval.getMutatedMemory().size() << " stores.\n");
2550  for (GlobalVariable *GV : Eval.getInvariants())
2551  GV->setConstant(true);
2552  }
2553 
2554  return EvalSuccess;
2555 }
2556 
2557 static int compareNames(Constant *const *A, Constant *const *B) {
2558  Value *AStripped = (*A)->stripPointerCastsNoFollowAliases();
2559  Value *BStripped = (*B)->stripPointerCastsNoFollowAliases();
2560  return AStripped->getName().compare(BStripped->getName());
2561 }
2562 
2565  if (Init.empty()) {
2566  V.eraseFromParent();
2567  return;
2568  }
2569 
2570  // Type of pointer to the array of pointers.
2571  PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext(), 0);
2572 
2573  SmallVector<Constant *, 8> UsedArray;
2574  for (GlobalValue *GV : Init) {
2575  Constant *Cast
2577  UsedArray.push_back(Cast);
2578  }
2579  // Sort to get deterministic order.
2580  array_pod_sort(UsedArray.begin(), UsedArray.end(), compareNames);
2581  ArrayType *ATy = ArrayType::get(Int8PtrTy, UsedArray.size());
2582 
2583  Module *M = V.getParent();
2584  V.removeFromParent();
2585  GlobalVariable *NV =
2586  new GlobalVariable(*M, ATy, false, GlobalValue::AppendingLinkage,
2587  ConstantArray::get(ATy, UsedArray), "");
2588  NV->takeName(&V);
2589  NV->setSection("llvm.metadata");
2590  delete &V;
2591 }
2592 
2593 namespace {
2594 
2595 /// An easy to access representation of llvm.used and llvm.compiler.used.
2596 class LLVMUsed {
2598  SmallPtrSet<GlobalValue *, 8> CompilerUsed;
2599  GlobalVariable *UsedV;
2600  GlobalVariable *CompilerUsedV;
2601 
2602 public:
2603  LLVMUsed(Module &M) {
2604  UsedV = collectUsedGlobalVariables(M, Used, false);
2605  CompilerUsedV = collectUsedGlobalVariables(M, CompilerUsed, true);
2606  }
2607 
2608  using iterator = SmallPtrSet<GlobalValue *, 8>::iterator;
2609  using used_iterator_range = iterator_range<iterator>;
2610 
2611  iterator usedBegin() { return Used.begin(); }
2612  iterator usedEnd() { return Used.end(); }
2613 
2614  used_iterator_range used() {
2615  return used_iterator_range(usedBegin(), usedEnd());
2616  }
2617 
2618  iterator compilerUsedBegin() { return CompilerUsed.begin(); }
2619  iterator compilerUsedEnd() { return CompilerUsed.end(); }
2620 
2621  used_iterator_range compilerUsed() {
2622  return used_iterator_range(compilerUsedBegin(), compilerUsedEnd());
2623  }
2624 
2625  bool usedCount(GlobalValue *GV) const { return Used.count(GV); }
2626 
2627  bool compilerUsedCount(GlobalValue *GV) const {
2628  return CompilerUsed.count(GV);
2629  }
2630 
2631  bool usedErase(GlobalValue *GV) { return Used.erase(GV); }
2632  bool compilerUsedErase(GlobalValue *GV) { return CompilerUsed.erase(GV); }
2633  bool usedInsert(GlobalValue *GV) { return Used.insert(GV).second; }
2634 
2635  bool compilerUsedInsert(GlobalValue *GV) {
2636  return CompilerUsed.insert(GV).second;
2637  }
2638 
2639  void syncVariablesAndSets() {
2640  if (UsedV)
2641  setUsedInitializer(*UsedV, Used);
2642  if (CompilerUsedV)
2643  setUsedInitializer(*CompilerUsedV, CompilerUsed);
2644  }
2645 };
2646 
2647 } // end anonymous namespace
2648 
2649 static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U) {
2650  if (GA.use_empty()) // No use at all.
2651  return false;
2652 
2653  assert((!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) &&
2654  "We should have removed the duplicated "
2655  "element from llvm.compiler.used");
2656  if (!GA.hasOneUse())
2657  // Strictly more than one use. So at least one is not in llvm.used and
2658  // llvm.compiler.used.
2659  return true;
2660 
2661  // Exactly one use. Check if it is in llvm.used or llvm.compiler.used.
2662  return !U.usedCount(&GA) && !U.compilerUsedCount(&GA);
2663 }
2664 
2666  const LLVMUsed &U) {
2667  unsigned N = 2;
2668  assert((!U.usedCount(&V) || !U.compilerUsedCount(&V)) &&
2669  "We should have removed the duplicated "
2670  "element from llvm.compiler.used");
2671  if (U.usedCount(&V) || U.compilerUsedCount(&V))
2672  ++N;
2673  return V.hasNUsesOrMore(N);
2674 }
2675 
2676 static bool mayHaveOtherReferences(GlobalAlias &GA, const LLVMUsed &U) {
2677  if (!GA.hasLocalLinkage())
2678  return true;
2679 
2680  return U.usedCount(&GA) || U.compilerUsedCount(&GA);
2681 }
2682 
2683 static bool hasUsesToReplace(GlobalAlias &GA, const LLVMUsed &U,
2684  bool &RenameTarget) {
2685  RenameTarget = false;
2686  bool Ret = false;
2687  if (hasUseOtherThanLLVMUsed(GA, U))
2688  Ret = true;
2689 
2690  // If the alias is externally visible, we may still be able to simplify it.
2691  if (!mayHaveOtherReferences(GA, U))
2692  return Ret;
2693 
2694  // If the aliasee has internal linkage, give it the name and linkage
2695  // of the alias, and delete the alias. This turns:
2696  // define internal ... @f(...)
2697  // @a = alias ... @f
2698  // into:
2699  // define ... @a(...)
2700  Constant *Aliasee = GA.getAliasee();
2701  GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts());
2702  if (!Target->hasLocalLinkage())
2703  return Ret;
2704 
2705  // Do not perform the transform if multiple aliases potentially target the
2706  // aliasee. This check also ensures that it is safe to replace the section
2707  // and other attributes of the aliasee with those of the alias.
2708  if (hasMoreThanOneUseOtherThanLLVMUsed(*Target, U))
2709  return Ret;
2710 
2711  RenameTarget = true;
2712  return true;
2713 }
2714 
2715 static bool
2717  SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
2718  bool Changed = false;
2719  LLVMUsed Used(M);
2720 
2721  for (GlobalValue *GV : Used.used())
2722  Used.compilerUsedErase(GV);
2723 
2724  for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end();
2725  I != E;) {
2726  GlobalAlias *J = &*I++;
2727 
2728  // Aliases without names cannot be referenced outside this module.
2729  if (!J->hasName() && !J->isDeclaration() && !J->hasLocalLinkage())
2731 
2732  if (deleteIfDead(*J, NotDiscardableComdats)) {
2733  Changed = true;
2734  continue;
2735  }
2736 
2737  // If the alias can change at link time, nothing can be done - bail out.
2738  if (J->isInterposable())
2739  continue;
2740 
2741  Constant *Aliasee = J->getAliasee();
2743  // We can't trivially replace the alias with the aliasee if the aliasee is
2744  // non-trivial in some way.
2745  // TODO: Try to handle non-zero GEPs of local aliasees.
2746  if (!Target)
2747  continue;
2748  Target->removeDeadConstantUsers();
2749 
2750  // Make all users of the alias use the aliasee instead.
2751  bool RenameTarget;
2752  if (!hasUsesToReplace(*J, Used, RenameTarget))
2753  continue;
2754 
2756  ++NumAliasesResolved;
2757  Changed = true;
2758 
2759  if (RenameTarget) {
2760  // Give the aliasee the name, linkage and other attributes of the alias.
2761  Target->takeName(&*J);
2762  Target->setLinkage(J->getLinkage());
2763  Target->setDSOLocal(J->isDSOLocal());
2764  Target->setVisibility(J->getVisibility());
2765  Target->setDLLStorageClass(J->getDLLStorageClass());
2766 
2767  if (Used.usedErase(&*J))
2768  Used.usedInsert(Target);
2769 
2770  if (Used.compilerUsedErase(&*J))
2771  Used.compilerUsedInsert(Target);
2772  } else if (mayHaveOtherReferences(*J, Used))
2773  continue;
2774 
2775  // Delete the alias.
2776  M.getAliasList().erase(J);
2777  ++NumAliasesRemoved;
2778  Changed = true;
2779  }
2780 
2781  Used.syncVariablesAndSets();
2782 
2783  return Changed;
2784 }
2785 
2787  LibFunc F = LibFunc_cxa_atexit;
2788  if (!TLI->has(F))
2789  return nullptr;
2790 
2791  Function *Fn = M.getFunction(TLI->getName(F));
2792  if (!Fn)
2793  return nullptr;
2794 
2795  // Make sure that the function has the correct prototype.
2796  if (!TLI->getLibFunc(*Fn, F) || F != LibFunc_cxa_atexit)
2797  return nullptr;
2798 
2799  return Fn;
2800 }
2801 
2802 /// Returns whether the given function is an empty C++ destructor and can
2803 /// therefore be eliminated.
2804 /// Note that we assume that other optimization passes have already simplified
2805 /// the code so we only look for a function with a single basic block, where
2806 /// the only allowed instructions are 'ret', 'call' to an empty C++ dtor and
2807 /// other side-effect free instructions.
2808 static bool cxxDtorIsEmpty(const Function &Fn,
2809  SmallPtrSet<const Function *, 8> &CalledFunctions) {
2810  // FIXME: We could eliminate C++ destructors if they're readonly/readnone and
2811  // nounwind, but that doesn't seem worth doing.
2812  if (Fn.isDeclaration())
2813  return false;
2814 
2815  if (++Fn.begin() != Fn.end())
2816  return false;
2817 
2818  const BasicBlock &EntryBlock = Fn.getEntryBlock();
2819  for (BasicBlock::const_iterator I = EntryBlock.begin(), E = EntryBlock.end();
2820  I != E; ++I) {
2821  if (const CallInst *CI = dyn_cast<CallInst>(I)) {
2822  // Ignore debug intrinsics.
2823  if (isa<DbgInfoIntrinsic>(CI))
2824  continue;
2825 
2826  const Function *CalledFn = CI->getCalledFunction();
2827 
2828  if (!CalledFn)
2829  return false;
2830 
2831  SmallPtrSet<const Function *, 8> NewCalledFunctions(CalledFunctions);
2832 
2833  // Don't treat recursive functions as empty.
2834  if (!NewCalledFunctions.insert(CalledFn).second)
2835  return false;
2836 
2837  if (!cxxDtorIsEmpty(*CalledFn, NewCalledFunctions))
2838  return false;
2839  } else if (isa<ReturnInst>(*I))
2840  return true; // We're done.
2841  else if (I->mayHaveSideEffects())
2842  return false; // Destructor with side effects, bail.
2843  }
2844 
2845  return false;
2846 }
2847 
2848 static bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) {
2849  /// Itanium C++ ABI p3.3.5:
2850  ///
2851  /// After constructing a global (or local static) object, that will require
2852  /// destruction on exit, a termination function is registered as follows:
2853  ///
2854  /// extern "C" int __cxa_atexit ( void (*f)(void *), void *p, void *d );
2855  ///
2856  /// This registration, e.g. __cxa_atexit(f,p,d), is intended to cause the
2857  /// call f(p) when DSO d is unloaded, before all such termination calls
2858  /// registered before this one. It returns zero if registration is
2859  /// successful, nonzero on failure.
2860 
2861  // This pass will look for calls to __cxa_atexit where the function is trivial
2862  // and remove them.
2863  bool Changed = false;
2864 
2865  for (auto I = CXAAtExitFn->user_begin(), E = CXAAtExitFn->user_end();
2866  I != E;) {
2867  // We're only interested in calls. Theoretically, we could handle invoke
2868  // instructions as well, but neither llvm-gcc nor clang generate invokes
2869  // to __cxa_atexit.
2870  CallInst *CI = dyn_cast<CallInst>(*I++);
2871  if (!CI)
2872  continue;
2873 
2874  Function *DtorFn =
2876  if (!DtorFn)
2877  continue;
2878 
2879  SmallPtrSet<const Function *, 8> CalledFunctions;
2880  if (!cxxDtorIsEmpty(*DtorFn, CalledFunctions))
2881  continue;
2882 
2883  // Just remove the call.
2885  CI->eraseFromParent();
2886 
2887  ++NumCXXDtorsRemoved;
2888 
2889  Changed |= true;
2890  }
2891 
2892  return Changed;
2893 }
2894 
2896  Module &M, const DataLayout &DL, TargetLibraryInfo *TLI,
2899  function_ref<DominatorTree &(Function &)> LookupDomTree) {
2900  SmallPtrSet<const Comdat *, 8> NotDiscardableComdats;
2901  bool Changed = false;
2902  bool LocalChange = true;
2903  while (LocalChange) {
2904  LocalChange = false;
2905 
2906  NotDiscardableComdats.clear();
2907  for (const GlobalVariable &GV : M.globals())
2908  if (const Comdat *C = GV.getComdat())
2909  if (!GV.isDiscardableIfUnused() || !GV.use_empty())
2910  NotDiscardableComdats.insert(C);
2911  for (Function &F : M)
2912  if (const Comdat *C = F.getComdat())
2913  if (!F.isDefTriviallyDead())
2914  NotDiscardableComdats.insert(C);
2915  for (GlobalAlias &GA : M.aliases())
2916  if (const Comdat *C = GA.getComdat())
2917  if (!GA.isDiscardableIfUnused() || !GA.use_empty())
2918  NotDiscardableComdats.insert(C);
2919 
2920  // Delete functions that are trivially dead, ccc -> fastcc
2921  LocalChange |= OptimizeFunctions(M, TLI, GetTTI, GetBFI, LookupDomTree,
2922  NotDiscardableComdats);
2923 
2924  // Optimize global_ctors list.
2925  LocalChange |= optimizeGlobalCtorsList(M, [&](Function *F) {
2926  return EvaluateStaticConstructor(F, DL, TLI);
2927  });
2928 
2929  // Optimize non-address-taken globals.
2930  LocalChange |= OptimizeGlobalVars(M, TLI, LookupDomTree,
2931  NotDiscardableComdats);
2932 
2933  // Resolve aliases, when possible.
2934  LocalChange |= OptimizeGlobalAliases(M, NotDiscardableComdats);
2935 
2936  // Try to remove trivial global destructors if they are not removed
2937  // already.
2938  Function *CXAAtExitFn = FindCXAAtExit(M, TLI);
2939  if (CXAAtExitFn)
2940  LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn);
2941 
2942  Changed |= LocalChange;
2943  }
2944 
2945  // TODO: Move all global ctors functions to the end of the module for code
2946  // layout.
2947 
2948  return Changed;
2949 }
2950 
2952  auto &DL = M.getDataLayout();
2953  auto &TLI = AM.getResult<TargetLibraryAnalysis>(M);
2954  auto &FAM =
2955  AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
2956  auto LookupDomTree = [&FAM](Function &F) -> DominatorTree &{
2957  return FAM.getResult<DominatorTreeAnalysis>(F);
2958  };
2959  auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {
2960  return FAM.getResult<TargetIRAnalysis>(F);
2961  };
2962 
2963  auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & {
2964  return FAM.getResult<BlockFrequencyAnalysis>(F);
2965  };
2966 
2967  if (!optimizeGlobalsInModule(M, DL, &TLI, GetTTI, GetBFI, LookupDomTree))
2968  return PreservedAnalyses::all();
2969  return PreservedAnalyses::none();
2970 }
2971 
2972 namespace {
2973 
2974 struct GlobalOptLegacyPass : public ModulePass {
2975  static char ID; // Pass identification, replacement for typeid
2976 
2977  GlobalOptLegacyPass() : ModulePass(ID) {
2979  }
2980 
2981  bool runOnModule(Module &M) override {
2982  if (skipModule(M))
2983  return false;
2984 
2985  auto &DL = M.getDataLayout();
2986  auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
2987  auto LookupDomTree = [this](Function &F) -> DominatorTree & {
2988  return this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
2989  };
2990  auto GetTTI = [this](Function &F) -> TargetTransformInfo & {
2991  return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
2992  };
2993 
2994  auto GetBFI = [this](Function &F) -> BlockFrequencyInfo & {
2995  return this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
2996  };
2997 
2998  return optimizeGlobalsInModule(M, DL, TLI, GetTTI, GetBFI, LookupDomTree);
2999  }
3000 
3001  void getAnalysisUsage(AnalysisUsage &AU) const override {
3006  }
3007 };
3008 
3009 } // end anonymous namespace
3010 
3011 char GlobalOptLegacyPass::ID = 0;
3012 
3013 INITIALIZE_PASS_BEGIN(GlobalOptLegacyPass, "globalopt",
3014  "Global Variable Optimizer", false, false)
3019 INITIALIZE_PASS_END(GlobalOptLegacyPass, "globalopt",
3020  "Global Variable Optimizer", false, false)
3021 
3023  return new GlobalOptLegacyPass();
3024 }
void setVisibility(VisibilityTypes V)
Definition: GlobalValue.h:239
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:177
uint64_t CallInst * C
Value * getValueOperand()
Definition: Instructions.h:399
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks &#39;this&#39; from the containing basic block and deletes it.
Definition: Instruction.cpp:68
unsigned getAlignment() const
Definition: GlobalObject.h:59
bool isAllocationFn(const Value *V, const TargetLibraryInfo *TLI, bool LookThroughBitCast=false)
Tests if a value is a call or invoke to a library function that allocates or reallocates memory (eith...
A parsed version of the target data layout string in and methods for querying it. ...
Definition: DataLayout.h:111
static ConstantInt * getFalse(LLVMContext &Context)
Definition: Constants.cpp:584
ThreadLocalMode getThreadLocalMode() const
Definition: GlobalValue.h:255
static bool CleanupConstantGlobalUsers(Value *V, Constant *Init, const DataLayout &DL, TargetLibraryInfo *TLI)
We just marked GV constant.
Definition: GlobalOpt.cpp:274
void initializeGlobalOptLegacyPassPass(PassRegistry &)
bool IsLoaded
True if the global is ever loaded.
Definition: GlobalStatus.h:36
static bool isLeakCheckerRoot(GlobalVariable *GV)
Is this global variable possibly used by a leak checker as a root? If so, we might not really want to...
Definition: GlobalOpt.cpp:111
static IntegerType * getInt1Ty(LLVMContext &C)
Definition: Type.cpp:173
raw_ostream & errs()
This returns a reference to a raw_ostream for standard error.
bool hasLocalLinkage() const
Definition: GlobalValue.h:436
unsigned getOpcode() const
Return the opcode at the root of this constant expression.
Definition: Constants.h:1199
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
Special purpose, only applies to global arrays.
Definition: GlobalValue.h:55
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Value * StoredOnceValue
If only one value (besides the initializer constant) is ever stored to this global, keep track of what value it is.
Definition: GlobalStatus.h:60
const Function * AccessingFunction
These start out null/false.
Definition: GlobalStatus.h:65
static Constant * getPointerBitCastOrAddrSpaceCast(Constant *C, Type *Ty)
Create a BitCast or AddrSpaceCast for a pointer type depending on the address space.
Definition: Constants.cpp:1579
DiagnosticInfoOptimizationBase::Argument NV
static BinaryOperator * CreateNot(Value *Op, const Twine &Name="", Instruction *InsertBefore=nullptr)
unsigned arg_size() const
Definition: CallSite.h:219
Atomic ordering constants.
bool hasPrivateLinkage() const
Definition: GlobalValue.h:435
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:770
iterator erase(iterator where)
Definition: ilist.h:267
const Constant * getInitializer() const
getInitializer - Return the initializer for this global variable.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
static bool IsSafeComputationToRemove(Value *V, const TargetLibraryInfo *TLI)
Given a value that is stored to a global but never read, determine whether it&#39;s safe to remove the st...
Definition: GlobalOpt.cpp:159
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:314
Constant * ConstantFoldLoadThroughGEPConstantExpr(Constant *C, ConstantExpr *CE)
ConstantFoldLoadThroughGEPConstantExpr - Given a constant and a getelementptr constantexpr, return the constant value being addressed by the constant expression, or null if something is funny and we can&#39;t decide.
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:64
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:1143
bool isSized(SmallPtrSetImpl< Type *> *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:265
bool user_empty() const
Definition: Value.h:364
iterator end()
Definition: Function.h:658
static Value * GetHeapSROAValue(Value *V, unsigned FieldNo, DenseMap< Value *, std::vector< Value *>> &InsertedScalarizedValues, std::vector< std::pair< PHINode *, unsigned >> &PHIsToRewrite)
Definition: GlobalOpt.cpp:1149
static void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc, GlobalVariable *GV)
The Alloc pointer is stored into GV somewhere.
Definition: GlobalOpt.cpp:1009
This class represents zero extension of integer types.
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:313
const StructLayout * getStructLayout(StructType *Ty) const
Returns a StructLayout object, indicating the alignment of the struct, its size, and the offsets of i...
Definition: DataLayout.cpp:588
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
bool useColdCCForColdCall(Function &F) const
Return true if the input function which is cold at all call sites, should use coldcc calling conventi...
bool removeUnreachableBlocks(Function &F, LazyValueInfo *LVI=nullptr, DomTreeUpdater *DTU=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Remove all blocks that can not be reached from the function&#39;s entry.
Definition: Local.cpp:2218
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:869
static bool isSafeSROAElementUse(Value *V)
Return true if the specified instruction is a safe user of a derived expression from a global that we...
Definition: GlobalOpt.cpp:397
static bool deleteIfDead(GlobalValue &GV, SmallPtrSetImpl< const Comdat *> &NotDiscardableComdats)
Definition: GlobalOpt.cpp:1738
This class represents a function call, abstracting a target machine&#39;s calling convention.
static PointerType * get(Type *ElementType, unsigned AddressSpace)
This constructs a pointer to an object of the specified type in a numbered address space...
Definition: Type.cpp:617
gep_type_iterator gep_type_end(const User *GEP)
unsigned less or equal
Definition: InstrTypes.h:683
unsigned less than
Definition: InstrTypes.h:682
static bool OptimizeGlobalVars(Module &M, TargetLibraryInfo *TLI, function_ref< DominatorTree &(Function &)> LookupDomTree, SmallPtrSetImpl< const Comdat *> &NotDiscardableComdats)
Definition: GlobalOpt.cpp:2319
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:107
static bool hasChangeableCC(Function *F)
Return true if this is a calling convention that we&#39;d like to change.
Definition: GlobalOpt.cpp:2103
static Constant * EvaluateStoreInto(Constant *Init, Constant *Val, ConstantExpr *Addr, unsigned OpNo)
Evaluate a piece of a constantexpr store into a global initializer.
Definition: GlobalOpt.cpp:2352
StringRef getName(LibFunc F) const
Analysis pass providing the TargetTransformInfo.
static bool hasOnlyColdCalls(Function &F, function_ref< BlockFrequencyInfo &(Function &)> GetBFI)
Definition: GlobalOpt.cpp:2191
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
Definition: Instructions.h:237
static GlobalVariable * OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, CallInst *CI, Type *AllocTy, ConstantInt *NElements, const DataLayout &DL, TargetLibraryInfo *TLI)
This function takes the specified global variable, and transforms the program as if it always contain...
Definition: GlobalOpt.cpp:835
static bool isSafeSROAGEP(User *U)
Return true if the specified GEP is a safe user of a derived expression from a global that we want to...
Definition: GlobalOpt.cpp:364
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", Instruction *InsertBefore=nullptr, Instruction *MDFrom=nullptr)
bool HasMultipleAccessingFunctions
Definition: GlobalStatus.h:66
LLVMContext & getContext() const
All values hold a context through their type.
Definition: Value.cpp:714
bool isInterposable() const
Return true if this global&#39;s definition can be substituted with an arbitrary definition at link time...
Definition: GlobalValue.h:420
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Definition: Function.h:321
This class wraps the llvm.memset intrinsic.
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:43
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1042
13: Structures
Definition: Type.h:73
STATISTIC(NumFunctions, "Total number of functions")
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)
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:231
F(f)
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Definition: DerivedTypes.h:503
An instruction for reading from memory.
Definition: Instructions.h:168
const GlobalListType & getGlobalList() const
Get the Module&#39;s list of global variables (constant).
Definition: Module.h:511
bool isOpaque() const
Return true if this is a type with an identity that has no body specified yet.
Definition: DerivedTypes.h:269
Hexagon Common GEP
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.cpp:138
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:230
static Instruction * CreateFree(Value *Source, Instruction *InsertBefore)
Generate the IR for a call to the builtin free function.
iv Induction Variable Users
Definition: IVUsers.cpp:52
static GlobalVariable * PerformHeapAllocSRoA(GlobalVariable *GV, CallInst *CI, Value *NElems, const DataLayout &DL, const TargetLibraryInfo *TLI)
CI is an allocation of an array of structures.
Definition: GlobalOpt.cpp:1272
#define op(i)
15: Pointers
Definition: Type.h:75
This defines the Use class.
void reserve(size_type N)
Definition: SmallVector.h:376
bool isMustTailCall() const
bool EvaluateFunction(Function *F, Constant *&RetVal, const SmallVectorImpl< Constant *> &ActualArgs)
Evaluate a call to function F, returning true if successful, false if we can&#39;t evaluate it...
Definition: Evaluator.cpp:646
void setAlignment(unsigned Align)
Definition: Globals.cpp:116
static bool processInternalGlobal(GlobalVariable *GV, const GlobalStatus &GS, TargetLibraryInfo *TLI, function_ref< DominatorTree &(Function &)> LookupDomTree)
Analyze the specified global variable and optimize it if possible.
Definition: GlobalOpt.cpp:1900
LLVMContext & getContext() const
Get the context in which this basic block lives.
Definition: BasicBlock.cpp:33
static bool LoadUsesSimpleEnoughForHeapSRA(const Value *V, SmallPtrSetImpl< const PHINode *> &LoadUsingPHIs, SmallPtrSetImpl< const PHINode *> &LoadUsingPHIsPerLoad)
Verify that all uses of V (a load, or a phi of a load) are simple enough to perform heap SRA on...
Definition: GlobalOpt.cpp:1052
static Constant * get(ArrayType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:960
This global is stored to, but the only thing stored is the constant it was initialized with...
Definition: GlobalStatus.h:45
static int compareNames(Constant *const *A, Constant *const *B)
Definition: GlobalOpt.cpp:2557
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:268
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:263
const AliasListType & getAliasList() const
Get the Module&#39;s list of aliases (constant).
Definition: Module.h:528
static DIExpression * prependOpcodes(const DIExpression *Expr, SmallVectorImpl< uint64_t > &Ops, bool StackValue=false)
Prepend DIExpr with the given opcodes and optionally turn it into a stack value.
unsigned getAllocaAddrSpace() const
Definition: DataLayout.h:258
AnalysisUsage & addRequired()
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
Definition: DataLayout.h:521
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
static bool hasUsesToReplace(GlobalAlias &GA, const LLVMUsed &U, bool &RenameTarget)
Definition: GlobalOpt.cpp:2683
static void makeAllConstantUsesInstructions(Constant *C)
C may have non-instruction users, and allNonInstructionUsersCanBeMadeInstructions has returned true...
Definition: GlobalOpt.cpp:1868
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: GlobalOpt.cpp:2951
static bool isColdCallSite(CallSite CS, BlockFrequencyInfo &CallerBFI)
Return true if the block containing the call site has a BlockFrequency of less than ColdCCRelFreq% of...
Definition: GlobalOpt.cpp:2141
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:364
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:662
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:364
TypeID getTypeID() const
Return the type id for the type.
Definition: Type.h:138
bool isFloatingPointTy() const
Return true if this is one of the six floating-point types.
Definition: Type.h:162
void setInitializer(Constant *InitVal)
setInitializer - Sets the initializer for this global variable, removing any existing initializer if ...
Definition: Globals.cpp:363
bool isDSOLocal() const
Definition: GlobalValue.h:280
static void changeCallSitesToColdCC(Function *F)
Definition: GlobalOpt.cpp:2178
Class to represent struct types.
Definition: DerivedTypes.h:201
A Use represents the edge between a Value definition and its users.
Definition: Use.h:56
uint64_t getElementOffsetInBits(unsigned Idx) const
Definition: DataLayout.h:548
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
static bool optimizeGlobalsInModule(Module &M, const DataLayout &DL, TargetLibraryInfo *TLI, function_ref< TargetTransformInfo &(Function &)> GetTTI, function_ref< BlockFrequencyInfo &(Function &)> GetBFI, function_ref< DominatorTree &(Function &)> LookupDomTree)
Definition: GlobalOpt.cpp:2895
UnnamedAddr getUnnamedAddr() const
Definition: GlobalValue.h:213
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:1056
This file contains the simple types necessary to represent the attributes associated with functions a...
Legacy analysis pass which computes BlockFrequencyInfo.
StoredType
Keep track of what stores to the global look like.
Definition: GlobalStatus.h:39
InstrTy * getInstruction() const
Definition: CallSite.h:92
static bool mayHaveOtherReferences(GlobalAlias &GA, const LLVMUsed &U)
Definition: GlobalOpt.cpp:2676
uint64_t getNumElements() const
Definition: DerivedTypes.h:359
void setDLLStorageClass(DLLStorageClassTypes C)
Definition: GlobalValue.h:268
void setArgument(unsigned ArgNo, Value *newVal)
Definition: CallSite.h:191
static bool OptimizeFunctions(Module &M, TargetLibraryInfo *TLI, function_ref< TargetTransformInfo &(Function &)> GetTTI, function_ref< BlockFrequencyInfo &(Function &)> GetBFI, function_ref< DominatorTree &(Function &)> LookupDomTree, SmallPtrSetImpl< const Comdat *> &NotDiscardableComdats)
Definition: GlobalOpt.cpp:2222
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:1599
static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U)
Definition: GlobalOpt.cpp:2649
AtomicOrdering
Atomic ordering for LLVM&#39;s memory model.
INITIALIZE_PASS_BEGIN(GlobalOptLegacyPass, "globalopt", "Global Variable Optimizer", false, false) INITIALIZE_PASS_END(GlobalOptLegacyPass
global_iterator global_begin()
Definition: Module.h:568
ValTy * getCalledValue() const
Return the pointer to function that is being called.
Definition: CallSite.h:100
Constant * ConstantFoldConstant(const Constant *C, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldConstant - Attempt to fold the constant using the specified DataLayout.
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:267
static cl::opt< int > ColdCCRelFreq("coldcc-rel-freq", cl::Hidden, cl::init(2), cl::ZeroOrMore, 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"))
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:85
User * getUser() const LLVM_READONLY
Returns the User that contains this Use.
Definition: Use.cpp:41
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:885
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:245
static bool optimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, AtomicOrdering Ordering, const DataLayout &DL, TargetLibraryInfo *TLI)
Definition: GlobalOpt.cpp:1561
static void ChangeCalleesToFastCall(Function *F)
Walk all of the direct calls of the specified function, changing them to FastCC.
Definition: GlobalOpt.cpp:2072
static Function * FindCXAAtExit(Module &M, TargetLibraryInfo *TLI)
Definition: GlobalOpt.cpp:2786
static void setUsedInitializer(GlobalVariable &V, const SmallPtrSetImpl< GlobalValue *> &Init)
Definition: GlobalOpt.cpp:2563
Class to represent array types.
Definition: DerivedTypes.h:369
bool has(LibFunc F) const
Tests whether a library function is available.
static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(const Instruction *V, const GlobalVariable *GV, SmallPtrSetImpl< const PHINode *> &PHIs)
Scan the use-list of V checking to make sure that there are no complex uses of V. ...
Definition: GlobalOpt.cpp:962
This class represents a no-op cast from one type to another.
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:224
An instruction for storing to memory.
Definition: Instructions.h:310
LinkageTypes getLinkage() const
Definition: GlobalValue.h:451
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
Definition: Value.cpp:439
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:301
iterator begin()
Definition: Function.h:656
Type::subtype_iterator element_iterator
Definition: DerivedTypes.h:301
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree...
Definition: Dominators.h:145
Value * getOperand(unsigned i) const
Definition: User.h:170
void removeDeadConstantUsers() const
If there are any dead constant users dangling off of this constant, remove them.
Definition: Constants.cpp:536
Class to represent pointers.
Definition: DerivedTypes.h:467
This global is stored to, but only its initializer and one other value is ever stored to it...
Definition: GlobalStatus.h:51
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:157
void replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Definition: User.cpp:21
Constant * getAggregateElement(unsigned Elt) const
For aggregates (struct/array/vector) return the constant that corresponds to the specified element if...
Definition: Constants.cpp:338
Value * getMallocArraySize(CallInst *CI, const DataLayout &DL, const TargetLibraryInfo *TLI, bool LookThroughSExt=false)
getMallocArraySize - Returns the array size of a malloc call.
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
Definition: Constants.cpp:1750
const BasicBlock & getEntryBlock() const
Definition: Function.h:640
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:610
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:843
IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space...
Definition: DataLayout.cpp:742
bool hasAttrSomewhere(Attribute::AttrKind Kind, unsigned *Index=nullptr) const
Return true if the specified attribute is set for at least one parameter or for the return value...
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata *> MDs)
Definition: Metadata.h:1166
void setAttributes(AttributeList PAL)
Set the parameter attributes of the call.
Definition: CallSite.h:333
void setCallingConv(CallingConv::ID CC)
Definition: Function.h:217
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:410
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N users or more.
Definition: Value.cpp:140
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:939
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
Definition: Constants.h:149
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
As we analyze each global, keep track of some information about it.
Definition: GlobalStatus.h:30
Wrapper pass for TargetTransformInfo.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:154
DLLStorageClassTypes getDLLStorageClass() const
Definition: GlobalValue.h:259
VisibilityTypes getVisibility() const
Definition: GlobalValue.h:233
alias_iterator alias_end()
Definition: Module.h:609
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction...
Definition: Instruction.cpp:74
bool hasName() const
Definition: Value.h:251
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
globalopt
Definition: GlobalOpt.cpp:3019
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important class for using LLVM in a threaded context.
Definition: LLVMContext.h:69
const CallInst * extractMallocCall(const Value *I, const TargetLibraryInfo *TLI)
extractMallocCall - Returns the corresponding CallInst if the instruction is a malloc call...
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This is an important base class in LLVM.
Definition: Constant.h:42
LLVM_NODISCARD bool empty() const
Definition: SmallPtrSet.h:92
This file contains the declarations for the subclasses of Constant, which represent the different fla...
bool isPointerTy() const
True if this is an instance of PointerType.
Definition: Type.h:224
void setExternallyInitialized(bool Val)
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:371
bool mayHaveSideEffects() const
Return true if the instruction may have side effects.
Definition: Instruction.h:558
void getDebugInfo(SmallVectorImpl< DIGlobalVariableExpression *> &GVs) const
Fill the vector with all debug info attachements.
Definition: Metadata.cpp:1525
Constant * ConstantFoldInstruction(Instruction *I, const DataLayout &DL, const TargetLibraryInfo *TLI=nullptr)
ConstantFoldInstruction - Try to constant fold the specified instruction.
void eraseFromParent()
eraseFromParent - This method unlinks &#39;this&#39; from the containing module and deletes it...
Definition: Globals.cpp:359
element_iterator element_end() const
Definition: DerivedTypes.h:304
static void RemoveNestAttribute(Function *F)
Definition: GlobalOpt.cpp:2089
A pair of DIGlobalVariable and DIExpression.
bool isUnordered() const
Definition: Instructions.h:268
Represent the analysis usage information of a pass.
This instruction compares its operands according to the predicate given to the constructor.
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:361
void setCallingConv(CallingConv::ID CC)
Set the calling convention of the call.
Definition: CallSite.h:316
static bool cxxDtorIsEmpty(const Function &Fn, SmallPtrSet< const Function *, 8 > &CalledFunctions)
Returns whether the given function is an empty C++ destructor and can therefore be eliminated...
Definition: GlobalOpt.cpp:2808
static Constant * get(StructType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:1021
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:495
Base class for variables.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
Definition: BasicBlock.h:100
LLVM_NODISCARD LLVM_ATTRIBUTE_ALWAYS_INLINE 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:184
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
self_iterator getIterator()
Definition: ilist_node.h:82
ModulePass * createGlobalOptimizerPass()
createGlobalOptimizerPass - This function returns a new pass that optimizes non-address taken interna...
Definition: GlobalOpt.cpp:3022
static bool isValidCandidateForColdCC(Function &F, function_ref< BlockFrequencyInfo &(Function &)> GetBFI, const std::vector< Function *> &AllCallsCold)
Definition: GlobalOpt.cpp:2155
static bool analyzeGlobal(const Value *V, GlobalStatus &GS)
Look at all uses of the global and fill in the GlobalStatus structure.
const Function * getFunction() const
Return the function this instruction belongs to.
Definition: Instruction.cpp:60
void setConstant(bool Val)
static bool hasMoreThanOneUseOtherThanLLVMUsed(GlobalValue &V, const LLVMUsed &U)
Definition: GlobalOpt.cpp:2665
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:194
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1392
const Constant * stripPointerCasts() const
Definition: Constant.h:173
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, and aliases.
Definition: Value.cpp:539
bool isSafeToDestroyConstant(const Constant *C)
It is safe to destroy a constant iff it is only used by constants itself.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:160
size_t size() const
Definition: SmallVector.h:53
static wasm::ValType getType(const TargetRegisterClass *RC)
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1063
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
Definition: Type.cpp:220
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:813
static void RewriteHeapSROALoadUser(Instruction *LoadUser, DenseMap< Value *, std::vector< Value *>> &InsertedScalarizedValues, std::vector< std::pair< PHINode *, unsigned >> &PHIsToRewrite)
Given a load instruction and a value derived from the load, rewrite the derived value to use the Heap...
Definition: GlobalOpt.cpp:1193
void removeFromParent()
removeFromParent - This method unlinks &#39;this&#39; from the containing module, but does not delete it...
Definition: Globals.cpp:355
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
signed greater than
Definition: InstrTypes.h:684
unsigned first
bool doesNotRecurse() const
Determine if the function is known not to recurse, directly or indirectly.
Definition: Function.h:556
This class evaluates LLVM IR, producing the Constant representing each SSA instruction.
Definition: Evaluator.h:39
global_iterator global_end()
Definition: Module.h:570
14: Arrays
Definition: Type.h:74
This is the superclass of the array and vector type classes.
Definition: DerivedTypes.h:343
static AttributeList StripNest(LLVMContext &C, AttributeList Attrs)
Definition: GlobalOpt.cpp:2081
GlobalVariable * collectUsedGlobalVariables(const Module &M, SmallPtrSetImpl< GlobalValue *> &Set, bool CompilerUsed)
Given "llvm.used" or "llvm.compiler.used" as a global name, collect the initializer elements of that ...
Definition: Module.cpp:550
Analysis pass which computes BlockFrequencyInfo.
This is the common base class for memset/memcpy/memmove.
Iterator for intrusive lists based on ilist_node.
unsigned getNumOperands() const
Definition: User.h:192
Global Variable Optimizer
Definition: GlobalOpt.cpp:3019
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
static void CommitValueTo(Constant *Val, Constant *Addr)
We have decided that Addr (which satisfies the predicate isSimpleEnoughPointerToCommit) should get Va...
Definition: GlobalOpt.cpp:2395
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false...
Definition: SmallPtrSet.h:378
ValTy * getArgument(unsigned ArgNo) const
Definition: CallSite.h:186
16: SIMD &#39;packed&#39; format, or other vector type
Definition: Type.h:76
iterator end()
Definition: BasicBlock.h:265
CallingConv::ID getCallingConv() const
getCallingConv()/setCallingConv(CC) - These method get and set the calling convention of this functio...
Definition: Function.h:213
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
Module.h This file contains the declarations for the Module class.
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:64
Provides information about what library functions are available for the current target.
unsigned getABITypeAlignment(Type *Ty) const
Returns the minimum ABI-required alignment for the specified type.
Definition: DataLayout.cpp:722
signed less than
Definition: InstrTypes.h:686
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
uint64_t getSizeInBytes() const
Definition: DataLayout.h:529
alias_iterator alias_begin()
Definition: Module.h:607
C - The default llvm calling convention, compatible with C.
Definition: CallingConv.h:35
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:621
static BranchInst * Create(BasicBlock *IfTrue, Instruction *InsertBefore=nullptr)
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
bool hasGlobalUnnamedAddr() const
Definition: GlobalValue.h:200
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:577
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:1440
void setAttributes(AttributeList Attrs)
Set the attribute list for this Function.
Definition: Function.h:227
DWARF expression.
Intrinsic::ID getIntrinsicID() const LLVM_READONLY
getIntrinsicID - This method returns the ID number of the specified function, or Intrinsic::not_intri...
Definition: Function.h:194
void setLinkage(LinkageTypes LT)
Definition: GlobalValue.h:445
BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:133
Function * getFunction(StringRef Name) const
Look up the specified function in the module symbol table.
Definition: Module.cpp:175
static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL, TargetLibraryInfo *TLI)
Evaluate static constructors in the function, if we can.
Definition: GlobalOpt.cpp:2534
signed less or equal
Definition: InstrTypes.h:687
A range adaptor for a pair of iterators.
This file contains constants used for implementing Dwarf debug support.
const Comdat * getComdat() const
Definition: Globals.cpp:171
Target - Wrapper for Target specific information.
void push_back(pointer val)
Definition: ilist.h:313
Type * getMallocAllocatedType(const CallInst *CI, const TargetLibraryInfo *TLI)
getMallocAllocatedType - Returns the Type allocated by malloc call.
iterator_range< user_iterator > users()
Definition: Value.h:400
static bool allNonInstructionUsersCanBeMadeInstructions(Constant *C)
C may have non-instruction users.
Definition: GlobalOpt.cpp:1842
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
Definition: Constants.cpp:1507
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
element_iterator element_begin() const
Definition: DerivedTypes.h:303
static Instruction * CreateMalloc(Instruction *InsertBefore, Type *IntPtrTy, Type *AllocTy, Value *AllocSize, Value *ArraySize=nullptr, Function *MallocF=nullptr, const Twine &Name="")
Generate the IR for a call to malloc:
const SmallPtrSetImpl< GlobalVariable * > & getInvariants() const
Definition: Evaluator.h:93
static void BatchCommitValueTo(const DenseMap< Constant *, Constant *> &Mem)
Given a map of address -> value, where addresses are expected to be some form of either a global or a...
Definition: GlobalOpt.cpp:2448
const Comdat * getComdat() const
Definition: GlobalObject.h:101
uint64_t getTypeAllocSize(Type *Ty) const
Returns the offset in bytes between successive objects of the specified type, including alignment pad...
Definition: DataLayout.h:428
use_iterator use_begin()
Definition: Value.h:339
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:731
static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(const GlobalVariable *GV, Instruction *StoredVal)
If all users of values loaded from GV are simple enough to perform HeapSRA, return true...
Definition: GlobalOpt.cpp:1103
This class wraps the llvm.memcpy/memmove intrinsics.
void eraseFromParent()
This method unlinks &#39;this&#39; from the containing module and deletes it.
Definition: Globals.cpp:85
FunTy * getCaller() const
Return the caller function for this call site.
Definition: CallSite.h:267
static bool GlobalUsersSafeToSRA(GlobalValue *GV)
Look at all uses of the global and decide whether it is safe for us to perform this transformation...
Definition: GlobalOpt.cpp:418
iterator insert(iterator where, pointer New)
Definition: ilist.h:228
iterator end()
Definition: Module.h:587
void setUnnamedAddr(UnnamedAddr Val)
Definition: GlobalValue.h:216
iterator begin() const
Definition: SmallPtrSet.h:397
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:543
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
bool IsCompared
True if the global&#39;s address is used in a comparison.
Definition: GlobalStatus.h:32
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:56
AtomicOrdering Ordering
Set to the strongest atomic ordering requirement.
Definition: GlobalStatus.h:73
unsigned greater or equal
Definition: InstrTypes.h:681
static bool OptimizeGlobalAliases(Module &M, SmallPtrSetImpl< const Comdat *> &NotDiscardableComdats)
Definition: GlobalOpt.cpp:2716
const Value * stripPointerCastsNoFollowAliases() const
Strip off pointer casts and all-zero GEPs.
Definition: Value.cpp:543
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:224
void copyAttributesFrom(const GlobalVariable *Src)
copyAttributesFrom - copy all additional attributes (those not needed to create a GlobalVariable) fro...
Definition: Globals.cpp:386
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
AttributeList removeAttribute(LLVMContext &C, unsigned Index, Attribute::AttrKind Kind) const
Remove the specified attribute at the specified index from this attribute list.
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:107
SyncScope::ID getSyncScopeID() const
Returns the synchronization scope ID of this load instruction.
Definition: Instructions.h:249
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
user_iterator_impl< User > user_iterator
Definition: Value.h:369
ModulePass class - This class is used to implement unstructured interprocedural optimizations and ana...
Definition: Pass.h:225
iterator begin()
Definition: Module.h:585
static bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn)
Definition: GlobalOpt.cpp:2848
X86_ThisCall - Similar to X86_StdCall.
Definition: CallingConv.h:111
static GlobalVariable * SRAGlobal(GlobalVariable *GV, const DataLayout &DL)
Perform scalar replacement of aggregates on the specified global variable.
Definition: GlobalOpt.cpp:461
static ArrayType * get(Type *ElementType, uint64_t NumElements)
This static method is the primary way to construct an ArrayType.
Definition: Type.cpp:568
const DenseMap< Constant *, Constant * > & getMutatedMemory() const
Definition: Evaluator.h:89
LLVM_NODISCARD std::enable_if<!is_simple_type< Y >::value, typename cast_retty< X, const Y >::ret_type >::type dyn_cast(const Y &Val)
Definition: Casting.h:323
Type * getValueType() const
Definition: GlobalValue.h:276
uint32_t Size
Definition: Profile.cpp:47
Rename collisions when linking (static functions).
Definition: GlobalValue.h:56
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="")
Split the basic block into two basic blocks at the specified instruction.
Definition: BasicBlock.cpp:402
static bool tryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, CallInst *CI, Type *AllocTy, AtomicOrdering Ordering, const DataLayout &DL, TargetLibraryInfo *TLI)
This function is called when we see a pointer global variable with a single value stored it that is a...
Definition: GlobalOpt.cpp:1463
iterator end() const
Definition: SmallPtrSet.h:402
void getOperandBundlesAsDefs(SmallVectorImpl< OperandBundleDef > &Defs) const
Return the list of operand bundles attached to this instruction as a vector of OperandBundleDefs.
Definition: InstrTypes.h:1230
bool isDeclaration() const
Return true if the primary definition of this global value is outside of the current translation unit...
Definition: Globals.cpp:206
Analysis pass providing the TargetLibraryInfo.
static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV, const DataLayout &DL, TargetLibraryInfo *TLI)
The specified global has only one non-null value stored into it.
Definition: GlobalOpt.cpp:748
static int const Threshold
TODO: Write a new FunctionPass AliasAnalysis so that it can keep a cache.
bool hasAddressTaken(const User **=nullptr) const
hasAddressTaken - returns true if there are any uses of this function other than direct calls or invo...
Definition: Function.cpp:1255
static void transferSRADebugInfo(GlobalVariable *GV, GlobalVariable *NGV, uint64_t FragmentOffsetInBits, uint64_t FragmentSizeInBits, unsigned NumElements)
Copy over the debug info for a variable to its SRA replacements.
Definition: GlobalOpt.cpp:435
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
user_iterator user_begin()
Definition: Value.h:376
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
bool isSingleValueType() const
Return true if the type is a valid type for a register in codegen.
Definition: Type.h:250
static bool processGlobal(GlobalValue &GV, TargetLibraryInfo *TLI, function_ref< DominatorTree &(Function &)> LookupDomTree)
Analyze the specified global variable and optimize it if possible.
Definition: GlobalOpt.cpp:2035
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:566
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction has no side ef...
Definition: Local.cpp:348
LLVM Value Representation.
Definition: Value.h:73
uint64_t getTypeStoreSize(Type *Ty) const
Returns the maximum number of bytes that may be overwritten by storing the specified type...
Definition: DataLayout.h:411
static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV)
Definition: GlobalOpt.cpp:678
bool hasInitializer() const
Definitions have initializers, declarations don&#39;t.
unsigned getOpcode() const
Return the opcode for this Instruction or ConstantExpr.
Definition: Operator.h:41
Invoke instruction.
void addDebugInfo(DIGlobalVariableExpression *GV)
Attach a DIGlobalVariableExpression.
Definition: Metadata.cpp:1521
uint64_t getTypeAllocSizeInBits(Type *Ty) const
Returns the offset in bits between successive objects of the specified type, including alignment padd...
Definition: DataLayout.h:438
Type * getElementType() const
Definition: DerivedTypes.h:360
iterator_range< global_iterator > globals()
Definition: Module.h:574
IRTranslator LLVM IR MI
bool hasOneUse() const
Return true if there is exactly one user of this value.
Definition: Value.h:413
unsigned greater than
Definition: InstrTypes.h:680
A container for analyses that lazily runs them and caches their results.
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:260
AttributeList getAttributes() const
Get the parameter attributes of the call.
Definition: CallSite.h:329
This pass exposes codegen information to IR-level passes.
static bool CleanupPointerRootUsers(GlobalVariable *GV, const TargetLibraryInfo *TLI)
This GV is a pointer root.
Definition: GlobalOpt.cpp:188
static bool isPointerValueDeadOnEntryToFunction(const Function *F, GlobalValue *GV, function_ref< DominatorTree &(Function &)> LookupDomTree)
Definition: GlobalOpt.cpp:1763
bool optimizeGlobalCtorsList(Module &M, function_ref< bool(Function *)> ShouldRemove)
Call "ShouldRemove" for every entry in M&#39;s global_ctor list and remove the entries for which it retur...
Definition: CtorUtils.cpp:119
#define LLVM_DEBUG(X)
Definition: Debug.h:123
static void RewriteUsesOfLoadForHeapSRoA(LoadInst *Load, DenseMap< Value *, std::vector< Value *>> &InsertedScalarizedValues, std::vector< std::pair< PHINode *, unsigned > > &PHIsToRewrite)
We are performing Heap SRoA on a global.
Definition: GlobalOpt.cpp:1256
bool isExternallyInitialized() const
void setSection(StringRef S)
Change the section for this global.
Definition: Globals.cpp:189
void setCalledFunction(Value *V)
Set the callee to the specified value.
Definition: CallSite.h:126
bool use_empty() const
Definition: Value.h:323
bool isDefTriviallyDead() const
isDefTriviallyDead - Return true if it is trivially safe to remove this function definition from the ...
Definition: Function.cpp:1275
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1056
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:613
void setDSOLocal(bool Local)
Definition: GlobalValue.h:278
PointerType * getType() const
Global values are always pointers.
Definition: GlobalValue.h:274
signed greater or equal
Definition: InstrTypes.h:685
User * user_back()
Definition: Value.h:386
bool isArrayTy() const
True if this is an instance of ArrayType.
Definition: Type.h:221
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...
const BasicBlock * getParent() const
Definition: Instruction.h:67
an instruction to allocate memory on the stack
Definition: Instructions.h:60
gep_type_iterator gep_type_begin(const User *GEP)
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1038
user_iterator user_end()
Definition: Value.h:384
const Constant * getAliasee() const
Definition: GlobalAlias.h:78