LLVM  9.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  StoreInst *NSI =
1714  new StoreInst(StoreVal, NewGV, false, 0, SI->getOrdering(),
1715  SI->getSyncScopeID(), SI);
1716  NSI->setDebugLoc(SI->getDebugLoc());
1717  } else {
1718  // Change the load into a load of bool then a select.
1719  LoadInst *LI = cast<LoadInst>(UI);
1720  LoadInst *NLI = new LoadInst(NewGV, LI->getName()+".b", false, 0,
1721  LI->getOrdering(), LI->getSyncScopeID(), LI);
1722  Instruction *NSI;
1723  if (IsOneZero)
1724  NSI = new ZExtInst(NLI, LI->getType(), "", LI);
1725  else
1726  NSI = SelectInst::Create(NLI, OtherVal, InitVal, "", LI);
1727  NSI->takeName(LI);
1728  // Since LI is split into two instructions, NLI and NSI both inherit the
1729  // same DebugLoc
1730  NLI->setDebugLoc(LI->getDebugLoc());
1731  NSI->setDebugLoc(LI->getDebugLoc());
1732  LI->replaceAllUsesWith(NSI);
1733  }
1734  UI->eraseFromParent();
1735  }
1736 
1737  // Retain the name of the old global variable. People who are debugging their
1738  // programs may expect these variables to be named the same.
1739  NewGV->takeName(GV);
1740  GV->eraseFromParent();
1741  return true;
1742 }
1743 
1744 static bool deleteIfDead(
1745  GlobalValue &GV, SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
1747 
1748  if (!GV.isDiscardableIfUnused() && !GV.isDeclaration())
1749  return false;
1750 
1751  if (const Comdat *C = GV.getComdat())
1752  if (!GV.hasLocalLinkage() && NotDiscardableComdats.count(C))
1753  return false;
1754 
1755  bool Dead;
1756  if (auto *F = dyn_cast<Function>(&GV))
1757  Dead = (F->isDeclaration() && F->use_empty()) || F->isDefTriviallyDead();
1758  else
1759  Dead = GV.use_empty();
1760  if (!Dead)
1761  return false;
1762 
1763  LLVM_DEBUG(dbgs() << "GLOBAL DEAD: " << GV << "\n");
1764  GV.eraseFromParent();
1765  ++NumDeleted;
1766  return true;
1767 }
1768 
1770  const Function *F, GlobalValue *GV,
1771  function_ref<DominatorTree &(Function &)> LookupDomTree) {
1772  // Find all uses of GV. We expect them all to be in F, and if we can't
1773  // identify any of the uses we bail out.
1774  //
1775  // On each of these uses, identify if the memory that GV points to is
1776  // used/required/live at the start of the function. If it is not, for example
1777  // if the first thing the function does is store to the GV, the GV can
1778  // possibly be demoted.
1779  //
1780  // We don't do an exhaustive search for memory operations - simply look
1781  // through bitcasts as they're quite common and benign.
1782  const DataLayout &DL = GV->getParent()->getDataLayout();
1785  for (auto *U : GV->users()) {
1786  if (Operator::getOpcode(U) == Instruction::BitCast) {
1787  for (auto *UU : U->users()) {
1788  if (auto *LI = dyn_cast<LoadInst>(UU))
1789  Loads.push_back(LI);
1790  else if (auto *SI = dyn_cast<StoreInst>(UU))
1791  Stores.push_back(SI);
1792  else
1793  return false;
1794  }
1795  continue;
1796  }
1797 
1799  if (!I)
1800  return false;
1801  assert(I->getParent()->getParent() == F);
1802 
1803  if (auto *LI = dyn_cast<LoadInst>(I))
1804  Loads.push_back(LI);
1805  else if (auto *SI = dyn_cast<StoreInst>(I))
1806  Stores.push_back(SI);
1807  else
1808  return false;
1809  }
1810 
1811  // We have identified all uses of GV into loads and stores. Now check if all
1812  // of them are known not to depend on the value of the global at the function
1813  // entry point. We do this by ensuring that every load is dominated by at
1814  // least one store.
1815  auto &DT = LookupDomTree(*const_cast<Function *>(F));
1816 
1817  // The below check is quadratic. Check we're not going to do too many tests.
1818  // FIXME: Even though this will always have worst-case quadratic time, we
1819  // could put effort into minimizing the average time by putting stores that
1820  // have been shown to dominate at least one load at the beginning of the
1821  // Stores array, making subsequent dominance checks more likely to succeed
1822  // early.
1823  //
1824  // The threshold here is fairly large because global->local demotion is a
1825  // very powerful optimization should it fire.
1826  const unsigned Threshold = 100;
1827  if (Loads.size() * Stores.size() > Threshold)
1828  return false;
1829 
1830  for (auto *L : Loads) {
1831  auto *LTy = L->getType();
1832  if (none_of(Stores, [&](const StoreInst *S) {
1833  auto *STy = S->getValueOperand()->getType();
1834  // The load is only dominated by the store if DomTree says so
1835  // and the number of bits loaded in L is less than or equal to
1836  // the number of bits stored in S.
1837  return DT.dominates(S, L) &&
1838  DL.getTypeStoreSize(LTy) <= DL.getTypeStoreSize(STy);
1839  }))
1840  return false;
1841  }
1842  // All loads have known dependences inside F, so the global can be localized.
1843  return true;
1844 }
1845 
1846 /// C may have non-instruction users. Can all of those users be turned into
1847 /// instructions?
1849  // We don't do this exhaustively. The most common pattern that we really need
1850  // to care about is a constant GEP or constant bitcast - so just looking
1851  // through one single ConstantExpr.
1852  //
1853  // The set of constants that this function returns true for must be able to be
1854  // handled by makeAllConstantUsesInstructions.
1855  for (auto *U : C->users()) {
1856  if (isa<Instruction>(U))
1857  continue;
1858  if (!isa<ConstantExpr>(U))
1859  // Non instruction, non-constantexpr user; cannot convert this.
1860  return false;
1861  for (auto *UU : U->users())
1862  if (!isa<Instruction>(UU))
1863  // A constantexpr used by another constant. We don't try and recurse any
1864  // further but just bail out at this point.
1865  return false;
1866  }
1867 
1868  return true;
1869 }
1870 
1871 /// C may have non-instruction users, and
1872 /// allNonInstructionUsersCanBeMadeInstructions has returned true. Convert the
1873 /// non-instruction users to instructions.
1876  for (auto *U : C->users()) {
1877  if (isa<ConstantExpr>(U))
1878  Users.push_back(cast<ConstantExpr>(U));
1879  else
1880  // We should never get here; allNonInstructionUsersCanBeMadeInstructions
1881  // should not have returned true for C.
1882  assert(
1883  isa<Instruction>(U) &&
1884  "Can't transform non-constantexpr non-instruction to instruction!");
1885  }
1886 
1887  SmallVector<Value*,4> UUsers;
1888  for (auto *U : Users) {
1889  UUsers.clear();
1890  for (auto *UU : U->users())
1891  UUsers.push_back(UU);
1892  for (auto *UU : UUsers) {
1893  Instruction *UI = cast<Instruction>(UU);
1894  Instruction *NewU = U->getAsInstruction();
1895  NewU->insertBefore(UI);
1896  UI->replaceUsesOfWith(U, NewU);
1897  }
1898  // We've replaced all the uses, so destroy the constant. (destroyConstant
1899  // will update value handles and metadata.)
1900  U->destroyConstant();
1901  }
1902 }
1903 
1904 /// Analyze the specified global variable and optimize
1905 /// it if possible. If we make a change, return true.
1907  GlobalVariable *GV, const GlobalStatus &GS, TargetLibraryInfo *TLI,
1908  function_ref<DominatorTree &(Function &)> LookupDomTree) {
1909  auto &DL = GV->getParent()->getDataLayout();
1910  // If this is a first class global and has only one accessing function and
1911  // this function is non-recursive, we replace the global with a local alloca
1912  // in this function.
1913  //
1914  // NOTE: It doesn't make sense to promote non-single-value types since we
1915  // are just replacing static memory to stack memory.
1916  //
1917  // If the global is in different address space, don't bring it to stack.
1919  GS.AccessingFunction &&
1920  GV->getValueType()->isSingleValueType() &&
1921  GV->getType()->getAddressSpace() == 0 &&
1922  !GV->isExternallyInitialized() &&
1926  LookupDomTree)) {
1927  const DataLayout &DL = GV->getParent()->getDataLayout();
1928 
1929  LLVM_DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV << "\n");
1930  Instruction &FirstI = const_cast<Instruction&>(*GS.AccessingFunction
1931  ->getEntryBlock().begin());
1932  Type *ElemTy = GV->getValueType();
1933  // FIXME: Pass Global's alignment when globals have alignment
1934  AllocaInst *Alloca = new AllocaInst(ElemTy, DL.getAllocaAddrSpace(), nullptr,
1935  GV->getName(), &FirstI);
1936  if (!isa<UndefValue>(GV->getInitializer()))
1937  new StoreInst(GV->getInitializer(), Alloca, &FirstI);
1938 
1940 
1941  GV->replaceAllUsesWith(Alloca);
1942  GV->eraseFromParent();
1943  ++NumLocalized;
1944  return true;
1945  }
1946 
1947  // If the global is never loaded (but may be stored to), it is dead.
1948  // Delete it now.
1949  if (!GS.IsLoaded) {
1950  LLVM_DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV << "\n");
1951 
1952  bool Changed;
1953  if (isLeakCheckerRoot(GV)) {
1954  // Delete any constant stores to the global.
1955  Changed = CleanupPointerRootUsers(GV, TLI);
1956  } else {
1957  // Delete any stores we can find to the global. We may not be able to
1958  // make it completely dead though.
1959  Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
1960  }
1961 
1962  // If the global is dead now, delete it.
1963  if (GV->use_empty()) {
1964  GV->eraseFromParent();
1965  ++NumDeleted;
1966  Changed = true;
1967  }
1968  return Changed;
1969 
1970  }
1972  LLVM_DEBUG(dbgs() << "MARKING CONSTANT: " << *GV << "\n");
1973  GV->setConstant(true);
1974 
1975  // Clean up any obviously simplifiable users now.
1976  CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
1977 
1978  // If the global is dead now, just nuke it.
1979  if (GV->use_empty()) {
1980  LLVM_DEBUG(dbgs() << " *** Marking constant allowed us to simplify "
1981  << "all users and delete global!\n");
1982  GV->eraseFromParent();
1983  ++NumDeleted;
1984  return true;
1985  }
1986 
1987  // Fall through to the next check; see if we can optimize further.
1988  ++NumMarked;
1989  }
1990  if (!GV->getInitializer()->getType()->isSingleValueType()) {
1991  const DataLayout &DL = GV->getParent()->getDataLayout();
1992  if (SRAGlobal(GV, DL))
1993  return true;
1994  }
1996  // If the initial value for the global was an undef value, and if only
1997  // one other value was stored into it, we can just change the
1998  // initializer to be the stored value, then delete all stores to the
1999  // global. This allows us to mark it constant.
2000  if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue))
2001  if (isa<UndefValue>(GV->getInitializer())) {
2002  // Change the initial value here.
2003  GV->setInitializer(SOVConstant);
2004 
2005  // Clean up any obviously simplifiable users now.
2006  CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
2007 
2008  if (GV->use_empty()) {
2009  LLVM_DEBUG(dbgs() << " *** Substituting initializer allowed us to "
2010  << "simplify all users and delete global!\n");
2011  GV->eraseFromParent();
2012  ++NumDeleted;
2013  }
2014  ++NumSubstitute;
2015  return true;
2016  }
2017 
2018  // Try to optimize globals based on the knowledge that only one value
2019  // (besides its initializer) is ever stored to the global.
2020  if (optimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, DL, TLI))
2021  return true;
2022 
2023  // Otherwise, if the global was not a boolean, we can shrink it to be a
2024  // boolean.
2025  if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) {
2026  if (GS.Ordering == AtomicOrdering::NotAtomic) {
2027  if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) {
2028  ++NumShrunkToBool;
2029  return true;
2030  }
2031  }
2032  }
2033  }
2034 
2035  return false;
2036 }
2037 
2038 /// Analyze the specified global variable and optimize it if possible. If we
2039 /// make a change, return true.
2040 static bool
2042  function_ref<DominatorTree &(Function &)> LookupDomTree) {
2043  if (GV.getName().startswith("llvm."))
2044  return false;
2045 
2046  GlobalStatus GS;
2047 
2048  if (GlobalStatus::analyzeGlobal(&GV, GS))
2049  return false;
2050 
2051  bool Changed = false;
2052  if (!GS.IsCompared && !GV.hasGlobalUnnamedAddr()) {
2053  auto NewUnnamedAddr = GV.hasLocalLinkage() ? GlobalValue::UnnamedAddr::Global
2055  if (NewUnnamedAddr != GV.getUnnamedAddr()) {
2056  GV.setUnnamedAddr(NewUnnamedAddr);
2057  NumUnnamed++;
2058  Changed = true;
2059  }
2060  }
2061 
2062  // Do more involved optimizations if the global is internal.
2063  if (!GV.hasLocalLinkage())
2064  return Changed;
2065 
2066  auto *GVar = dyn_cast<GlobalVariable>(&GV);
2067  if (!GVar)
2068  return Changed;
2069 
2070  if (GVar->isConstant() || !GVar->hasInitializer())
2071  return Changed;
2072 
2073  return processInternalGlobal(GVar, GS, TLI, LookupDomTree) || Changed;
2074 }
2075 
2076 /// Walk all of the direct calls of the specified function, changing them to
2077 /// FastCC.
2079  for (User *U : F->users()) {
2080  if (isa<BlockAddress>(U))
2081  continue;
2082  CallSite CS(cast<Instruction>(U));
2084  }
2085 }
2086 
2088  // There can be at most one attribute set with a nest attribute.
2089  unsigned NestIndex;
2090  if (Attrs.hasAttrSomewhere(Attribute::Nest, &NestIndex))
2091  return Attrs.removeAttribute(C, NestIndex, Attribute::Nest);
2092  return Attrs;
2093 }
2094 
2097  for (User *U : F->users()) {
2098  if (isa<BlockAddress>(U))
2099  continue;
2100  CallSite CS(cast<Instruction>(U));
2102  }
2103 }
2104 
2105 /// Return true if this is a calling convention that we'd like to change. The
2106 /// idea here is that we don't want to mess with the convention if the user
2107 /// explicitly requested something with performance implications like coldcc,
2108 /// GHC, or anyregcc.
2109 static bool hasChangeableCC(Function *F) {
2110  CallingConv::ID CC = F->getCallingConv();
2111 
2112  // FIXME: Is it worth transforming x86_stdcallcc and x86_fastcallcc?
2113  if (CC != CallingConv::C && CC != CallingConv::X86_ThisCall)
2114  return false;
2115 
2116  // Don't break the invariant that the inalloca parameter is the only parameter
2117  // passed in memory.
2118  // FIXME: GlobalOpt should remove inalloca when possible and hoist the dynamic
2119  // alloca it uses to the entry block if possible.
2120  if (F->getAttributes().hasAttrSomewhere(Attribute::InAlloca))
2121  return false;
2122 
2123  // FIXME: Change CC for the whole chain of musttail calls when possible.
2124  //
2125  // Can't change CC of the function that either has musttail calls, or is a
2126  // musttail callee itself
2127  for (User *U : F->users()) {
2128  if (isa<BlockAddress>(U))
2129  continue;
2130  CallInst* CI = dyn_cast<CallInst>(U);
2131  if (!CI)
2132  continue;
2133 
2134  if (CI->isMustTailCall())
2135  return false;
2136  }
2137 
2138  for (BasicBlock &BB : *F)
2139  if (BB.getTerminatingMustTailCall())
2140  return false;
2141 
2142  return true;
2143 }
2144 
2145 /// Return true if the block containing the call site has a BlockFrequency of
2146 /// less than ColdCCRelFreq% of the entry block.
2147 static bool isColdCallSite(CallSite CS, BlockFrequencyInfo &CallerBFI) {
2148  const BranchProbability ColdProb(ColdCCRelFreq, 100);
2149  auto CallSiteBB = CS.getInstruction()->getParent();
2150  auto CallSiteFreq = CallerBFI.getBlockFreq(CallSiteBB);
2151  auto CallerEntryFreq =
2152  CallerBFI.getBlockFreq(&(CS.getCaller()->getEntryBlock()));
2153  return CallSiteFreq < CallerEntryFreq * ColdProb;
2154 }
2155 
2156 // This function checks if the input function F is cold at all call sites. It
2157 // also looks each call site's containing function, returning false if the
2158 // caller function contains other non cold calls. The input vector AllCallsCold
2159 // contains a list of functions that only have call sites in cold blocks.
2160 static bool
2163  const std::vector<Function *> &AllCallsCold) {
2164 
2165  if (F.user_empty())
2166  return false;
2167 
2168  for (User *U : F.users()) {
2169  if (isa<BlockAddress>(U))
2170  continue;
2171 
2172  CallSite CS(cast<Instruction>(U));
2173  Function *CallerFunc = CS.getInstruction()->getParent()->getParent();
2174  BlockFrequencyInfo &CallerBFI = GetBFI(*CallerFunc);
2175  if (!isColdCallSite(CS, CallerBFI))
2176  return false;
2177  auto It = std::find(AllCallsCold.begin(), AllCallsCold.end(), CallerFunc);
2178  if (It == AllCallsCold.end())
2179  return false;
2180  }
2181  return true;
2182 }
2183 
2185  for (User *U : F->users()) {
2186  if (isa<BlockAddress>(U))
2187  continue;
2188  CallSite CS(cast<Instruction>(U));
2190  }
2191 }
2192 
2193 // This function iterates over all the call instructions in the input Function
2194 // and checks that all call sites are in cold blocks and are allowed to use the
2195 // coldcc calling convention.
2196 static bool
2198  function_ref<BlockFrequencyInfo &(Function &)> GetBFI) {
2199  for (BasicBlock &BB : F) {
2200  for (Instruction &I : BB) {
2201  if (CallInst *CI = dyn_cast<CallInst>(&I)) {
2202  CallSite CS(cast<Instruction>(CI));
2203  // Skip over isline asm instructions since they aren't function calls.
2204  if (CI->isInlineAsm())
2205  continue;
2206  Function *CalledFn = CI->getCalledFunction();
2207  if (!CalledFn)
2208  return false;
2209  if (!CalledFn->hasLocalLinkage())
2210  return false;
2211  // Skip over instrinsics since they won't remain as function calls.
2212  if (CalledFn->getIntrinsicID() != Intrinsic::not_intrinsic)
2213  continue;
2214  // Check if it's valid to use coldcc calling convention.
2215  if (!hasChangeableCC(CalledFn) || CalledFn->isVarArg() ||
2216  CalledFn->hasAddressTaken())
2217  return false;
2218  BlockFrequencyInfo &CallerBFI = GetBFI(F);
2219  if (!isColdCallSite(CS, CallerBFI))
2220  return false;
2221  }
2222  }
2223  }
2224  return true;
2225 }
2226 
2227 static bool
2231  function_ref<DominatorTree &(Function &)> LookupDomTree,
2232  SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
2233 
2234  bool Changed = false;
2235 
2236  std::vector<Function *> AllCallsCold;
2237  for (Module::iterator FI = M.begin(), E = M.end(); FI != E;) {
2238  Function *F = &*FI++;
2239  if (hasOnlyColdCalls(*F, GetBFI))
2240  AllCallsCold.push_back(F);
2241  }
2242 
2243  // Optimize functions.
2244  for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
2245  Function *F = &*FI++;
2246 
2247  // Don't perform global opt pass on naked functions; we don't want fast
2248  // calling conventions for naked functions.
2249  if (F->hasFnAttribute(Attribute::Naked))
2250  continue;
2251 
2252  // Functions without names cannot be referenced outside this module.
2253  if (!F->hasName() && !F->isDeclaration() && !F->hasLocalLinkage())
2255 
2256  if (deleteIfDead(*F, NotDiscardableComdats)) {
2257  Changed = true;
2258  continue;
2259  }
2260 
2261  // LLVM's definition of dominance allows instructions that are cyclic
2262  // in unreachable blocks, e.g.:
2263  // %pat = select i1 %condition, @global, i16* %pat
2264  // because any instruction dominates an instruction in a block that's
2265  // not reachable from entry.
2266  // So, remove unreachable blocks from the function, because a) there's
2267  // no point in analyzing them and b) GlobalOpt should otherwise grow
2268  // some more complicated logic to break these cycles.
2269  // Removing unreachable blocks might invalidate the dominator so we
2270  // recalculate it.
2271  if (!F->isDeclaration()) {
2272  if (removeUnreachableBlocks(*F)) {
2273  auto &DT = LookupDomTree(*F);
2274  DT.recalculate(*F);
2275  Changed = true;
2276  }
2277  }
2278 
2279  Changed |= processGlobal(*F, TLI, LookupDomTree);
2280 
2281  if (!F->hasLocalLinkage())
2282  continue;
2283 
2284  if (hasChangeableCC(F) && !F->isVarArg() && !F->hasAddressTaken()) {
2285  NumInternalFunc++;
2286  TargetTransformInfo &TTI = GetTTI(*F);
2287  // Change the calling convention to coldcc if either stress testing is
2288  // enabled or the target would like to use coldcc on functions which are
2289  // cold at all call sites and the callers contain no other non coldcc
2290  // calls.
2291  if (EnableColdCCStressTest ||
2292  (isValidCandidateForColdCC(*F, GetBFI, AllCallsCold) &&
2293  TTI.useColdCCForColdCall(*F))) {
2296  Changed = true;
2297  NumColdCC++;
2298  }
2299  }
2300 
2301  if (hasChangeableCC(F) && !F->isVarArg() &&
2302  !F->hasAddressTaken()) {
2303  // If this function has a calling convention worth changing, is not a
2304  // varargs function, and is only called directly, promote it to use the
2305  // Fast calling convention.
2308  ++NumFastCallFns;
2309  Changed = true;
2310  }
2311 
2312  if (F->getAttributes().hasAttrSomewhere(Attribute::Nest) &&
2313  !F->hasAddressTaken()) {
2314  // The function is not used by a trampoline intrinsic, so it is safe
2315  // to remove the 'nest' attribute.
2317  ++NumNestRemoved;
2318  Changed = true;
2319  }
2320  }
2321  return Changed;
2322 }
2323 
2324 static bool
2326  function_ref<DominatorTree &(Function &)> LookupDomTree,
2327  SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
2328  bool Changed = false;
2329 
2330  for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
2331  GVI != E; ) {
2332  GlobalVariable *GV = &*GVI++;
2333  // Global variables without names cannot be referenced outside this module.
2334  if (!GV->hasName() && !GV->isDeclaration() && !GV->hasLocalLinkage())
2336  // Simplify the initializer.
2337  if (GV->hasInitializer())
2338  if (auto *C = dyn_cast<Constant>(GV->getInitializer())) {
2339  auto &DL = M.getDataLayout();
2340  Constant *New = ConstantFoldConstant(C, DL, TLI);
2341  if (New && New != C)
2342  GV->setInitializer(New);
2343  }
2344 
2345  if (deleteIfDead(*GV, NotDiscardableComdats)) {
2346  Changed = true;
2347  continue;
2348  }
2349 
2350  Changed |= processGlobal(*GV, TLI, LookupDomTree);
2351  }
2352  return Changed;
2353 }
2354 
2355 /// Evaluate a piece of a constantexpr store into a global initializer. This
2356 /// returns 'Init' modified to reflect 'Val' stored into it. At this point, the
2357 /// GEP operands of Addr [0, OpNo) have been stepped into.
2359  ConstantExpr *Addr, unsigned OpNo) {
2360  // Base case of the recursion.
2361  if (OpNo == Addr->getNumOperands()) {
2362  assert(Val->getType() == Init->getType() && "Type mismatch!");
2363  return Val;
2364  }
2365 
2367  if (StructType *STy = dyn_cast<StructType>(Init->getType())) {
2368  // Break up the constant into its elements.
2369  for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
2370  Elts.push_back(Init->getAggregateElement(i));
2371 
2372  // Replace the element that we are supposed to.
2373  ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo));
2374  unsigned Idx = CU->getZExtValue();
2375  assert(Idx < STy->getNumElements() && "Struct index out of range!");
2376  Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1);
2377 
2378  // Return the modified struct.
2379  return ConstantStruct::get(STy, Elts);
2380  }
2381 
2382  ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo));
2383  SequentialType *InitTy = cast<SequentialType>(Init->getType());
2384  uint64_t NumElts = InitTy->getNumElements();
2385 
2386  // Break up the array into elements.
2387  for (uint64_t i = 0, e = NumElts; i != e; ++i)
2388  Elts.push_back(Init->getAggregateElement(i));
2389 
2390  assert(CI->getZExtValue() < NumElts);
2391  Elts[CI->getZExtValue()] =
2392  EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1);
2393 
2394  if (Init->getType()->isArrayTy())
2395  return ConstantArray::get(cast<ArrayType>(InitTy), Elts);
2396  return ConstantVector::get(Elts);
2397 }
2398 
2399 /// We have decided that Addr (which satisfies the predicate
2400 /// isSimpleEnoughPointerToCommit) should get Val as its value. Make it happen.
2401 static void CommitValueTo(Constant *Val, Constant *Addr) {
2402  if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
2403  assert(GV->hasInitializer());
2404  GV->setInitializer(Val);
2405  return;
2406  }
2407 
2408  ConstantExpr *CE = cast<ConstantExpr>(Addr);
2409  GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
2410  GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2));
2411 }
2412 
2413 /// Given a map of address -> value, where addresses are expected to be some form
2414 /// of either a global or a constant GEP, set the initializer for the address to
2415 /// be the value. This performs mostly the same function as CommitValueTo()
2416 /// and EvaluateStoreInto() but is optimized to be more efficient for the common
2417 /// case where the set of addresses are GEPs sharing the same underlying global,
2418 /// processing the GEPs in batches rather than individually.
2419 ///
2420 /// To give an example, consider the following C++ code adapted from the clang
2421 /// regression tests:
2422 /// struct S {
2423 /// int n = 10;
2424 /// int m = 2 * n;
2425 /// S(int a) : n(a) {}
2426 /// };
2427 ///
2428 /// template<typename T>
2429 /// struct U {
2430 /// T *r = &q;
2431 /// T q = 42;
2432 /// U *p = this;
2433 /// };
2434 ///
2435 /// U<S> e;
2436 ///
2437 /// The global static constructor for 'e' will need to initialize 'r' and 'p' of
2438 /// the outer struct, while also initializing the inner 'q' structs 'n' and 'm'
2439 /// members. This batch algorithm will simply use general CommitValueTo() method
2440 /// to handle the complex nested S struct initialization of 'q', before
2441 /// processing the outermost members in a single batch. Using CommitValueTo() to
2442 /// handle member in the outer struct is inefficient when the struct/array is
2443 /// very large as we end up creating and destroy constant arrays for each
2444 /// initialization.
2445 /// For the above case, we expect the following IR to be generated:
2446 ///
2447 /// %struct.U = type { %struct.S*, %struct.S, %struct.U* }
2448 /// %struct.S = type { i32, i32 }
2449 /// @e = global %struct.U { %struct.S* gep inbounds (%struct.U, %struct.U* @e,
2450 /// i64 0, i32 1),
2451 /// %struct.S { i32 42, i32 84 }, %struct.U* @e }
2452 /// The %struct.S { i32 42, i32 84 } inner initializer is treated as a complex
2453 /// constant expression, while the other two elements of @e are "simple".
2458  SimpleCEs.reserve(Mem.size());
2459 
2460  for (const auto &I : Mem) {
2461  if (auto *GV = dyn_cast<GlobalVariable>(I.first)) {
2462  GVs.push_back(std::make_pair(GV, I.second));
2463  } else {
2464  ConstantExpr *GEP = cast<ConstantExpr>(I.first);
2465  // We don't handle the deeply recursive case using the batch method.
2466  if (GEP->getNumOperands() > 3)
2467  ComplexCEs.push_back(std::make_pair(GEP, I.second));
2468  else
2469  SimpleCEs.push_back(std::make_pair(GEP, I.second));
2470  }
2471  }
2472 
2473  // The algorithm below doesn't handle cases like nested structs, so use the
2474  // slower fully general method if we have to.
2475  for (auto ComplexCE : ComplexCEs)
2476  CommitValueTo(ComplexCE.second, ComplexCE.first);
2477 
2478  for (auto GVPair : GVs) {
2479  assert(GVPair.first->hasInitializer());
2480  GVPair.first->setInitializer(GVPair.second);
2481  }
2482 
2483  if (SimpleCEs.empty())
2484  return;
2485 
2486  // We cache a single global's initializer elements in the case where the
2487  // subsequent address/val pair uses the same one. This avoids throwing away and
2488  // rebuilding the constant struct/vector/array just because one element is
2489  // modified at a time.
2491  Elts.reserve(SimpleCEs.size());
2492  GlobalVariable *CurrentGV = nullptr;
2493 
2494  auto commitAndSetupCache = [&](GlobalVariable *GV, bool Update) {
2495  Constant *Init = GV->getInitializer();
2496  Type *Ty = Init->getType();
2497  if (Update) {
2498  if (CurrentGV) {
2499  assert(CurrentGV && "Expected a GV to commit to!");
2500  Type *CurrentInitTy = CurrentGV->getInitializer()->getType();
2501  // We have a valid cache that needs to be committed.
2502  if (StructType *STy = dyn_cast<StructType>(CurrentInitTy))
2503  CurrentGV->setInitializer(ConstantStruct::get(STy, Elts));
2504  else if (ArrayType *ArrTy = dyn_cast<ArrayType>(CurrentInitTy))
2505  CurrentGV->setInitializer(ConstantArray::get(ArrTy, Elts));
2506  else
2507  CurrentGV->setInitializer(ConstantVector::get(Elts));
2508  }
2509  if (CurrentGV == GV)
2510  return;
2511  // Need to clear and set up cache for new initializer.
2512  CurrentGV = GV;
2513  Elts.clear();
2514  unsigned NumElts;
2515  if (auto *STy = dyn_cast<StructType>(Ty))
2516  NumElts = STy->getNumElements();
2517  else
2518  NumElts = cast<SequentialType>(Ty)->getNumElements();
2519  for (unsigned i = 0, e = NumElts; i != e; ++i)
2520  Elts.push_back(Init->getAggregateElement(i));
2521  }
2522  };
2523 
2524  for (auto CEPair : SimpleCEs) {
2525  ConstantExpr *GEP = CEPair.first;
2526  Constant *Val = CEPair.second;
2527 
2528  GlobalVariable *GV = cast<GlobalVariable>(GEP->getOperand(0));
2529  commitAndSetupCache(GV, GV != CurrentGV);
2530  ConstantInt *CI = cast<ConstantInt>(GEP->getOperand(2));
2531  Elts[CI->getZExtValue()] = Val;
2532  }
2533  // The last initializer in the list needs to be committed, others
2534  // will be committed on a new initializer being processed.
2535  commitAndSetupCache(CurrentGV, true);
2536 }
2537 
2538 /// Evaluate static constructors in the function, if we can. Return true if we
2539 /// can, false otherwise.
2541  TargetLibraryInfo *TLI) {
2542  // Call the function.
2543  Evaluator Eval(DL, TLI);
2544  Constant *RetValDummy;
2545  bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy,
2547 
2548  if (EvalSuccess) {
2549  ++NumCtorsEvaluated;
2550 
2551  // We succeeded at evaluation: commit the result.
2552  LLVM_DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
2553  << F->getName() << "' to "
2554  << Eval.getMutatedMemory().size() << " stores.\n");
2556  for (GlobalVariable *GV : Eval.getInvariants())
2557  GV->setConstant(true);
2558  }
2559 
2560  return EvalSuccess;
2561 }
2562 
2563 static int compareNames(Constant *const *A, Constant *const *B) {
2564  Value *AStripped = (*A)->stripPointerCastsNoFollowAliases();
2565  Value *BStripped = (*B)->stripPointerCastsNoFollowAliases();
2566  return AStripped->getName().compare(BStripped->getName());
2567 }
2568 
2571  if (Init.empty()) {
2572  V.eraseFromParent();
2573  return;
2574  }
2575 
2576  // Type of pointer to the array of pointers.
2577  PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext(), 0);
2578 
2579  SmallVector<Constant *, 8> UsedArray;
2580  for (GlobalValue *GV : Init) {
2581  Constant *Cast
2583  UsedArray.push_back(Cast);
2584  }
2585  // Sort to get deterministic order.
2586  array_pod_sort(UsedArray.begin(), UsedArray.end(), compareNames);
2587  ArrayType *ATy = ArrayType::get(Int8PtrTy, UsedArray.size());
2588 
2589  Module *M = V.getParent();
2590  V.removeFromParent();
2591  GlobalVariable *NV =
2592  new GlobalVariable(*M, ATy, false, GlobalValue::AppendingLinkage,
2593  ConstantArray::get(ATy, UsedArray), "");
2594  NV->takeName(&V);
2595  NV->setSection("llvm.metadata");
2596  delete &V;
2597 }
2598 
2599 namespace {
2600 
2601 /// An easy to access representation of llvm.used and llvm.compiler.used.
2602 class LLVMUsed {
2604  SmallPtrSet<GlobalValue *, 8> CompilerUsed;
2605  GlobalVariable *UsedV;
2606  GlobalVariable *CompilerUsedV;
2607 
2608 public:
2609  LLVMUsed(Module &M) {
2610  UsedV = collectUsedGlobalVariables(M, Used, false);
2611  CompilerUsedV = collectUsedGlobalVariables(M, CompilerUsed, true);
2612  }
2613 
2614  using iterator = SmallPtrSet<GlobalValue *, 8>::iterator;
2615  using used_iterator_range = iterator_range<iterator>;
2616 
2617  iterator usedBegin() { return Used.begin(); }
2618  iterator usedEnd() { return Used.end(); }
2619 
2620  used_iterator_range used() {
2621  return used_iterator_range(usedBegin(), usedEnd());
2622  }
2623 
2624  iterator compilerUsedBegin() { return CompilerUsed.begin(); }
2625  iterator compilerUsedEnd() { return CompilerUsed.end(); }
2626 
2627  used_iterator_range compilerUsed() {
2628  return used_iterator_range(compilerUsedBegin(), compilerUsedEnd());
2629  }
2630 
2631  bool usedCount(GlobalValue *GV) const { return Used.count(GV); }
2632 
2633  bool compilerUsedCount(GlobalValue *GV) const {
2634  return CompilerUsed.count(GV);
2635  }
2636 
2637  bool usedErase(GlobalValue *GV) { return Used.erase(GV); }
2638  bool compilerUsedErase(GlobalValue *GV) { return CompilerUsed.erase(GV); }
2639  bool usedInsert(GlobalValue *GV) { return Used.insert(GV).second; }
2640 
2641  bool compilerUsedInsert(GlobalValue *GV) {
2642  return CompilerUsed.insert(GV).second;
2643  }
2644 
2645  void syncVariablesAndSets() {
2646  if (UsedV)
2647  setUsedInitializer(*UsedV, Used);
2648  if (CompilerUsedV)
2649  setUsedInitializer(*CompilerUsedV, CompilerUsed);
2650  }
2651 };
2652 
2653 } // end anonymous namespace
2654 
2655 static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U) {
2656  if (GA.use_empty()) // No use at all.
2657  return false;
2658 
2659  assert((!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) &&
2660  "We should have removed the duplicated "
2661  "element from llvm.compiler.used");
2662  if (!GA.hasOneUse())
2663  // Strictly more than one use. So at least one is not in llvm.used and
2664  // llvm.compiler.used.
2665  return true;
2666 
2667  // Exactly one use. Check if it is in llvm.used or llvm.compiler.used.
2668  return !U.usedCount(&GA) && !U.compilerUsedCount(&GA);
2669 }
2670 
2672  const LLVMUsed &U) {
2673  unsigned N = 2;
2674  assert((!U.usedCount(&V) || !U.compilerUsedCount(&V)) &&
2675  "We should have removed the duplicated "
2676  "element from llvm.compiler.used");
2677  if (U.usedCount(&V) || U.compilerUsedCount(&V))
2678  ++N;
2679  return V.hasNUsesOrMore(N);
2680 }
2681 
2682 static bool mayHaveOtherReferences(GlobalAlias &GA, const LLVMUsed &U) {
2683  if (!GA.hasLocalLinkage())
2684  return true;
2685 
2686  return U.usedCount(&GA) || U.compilerUsedCount(&GA);
2687 }
2688 
2689 static bool hasUsesToReplace(GlobalAlias &GA, const LLVMUsed &U,
2690  bool &RenameTarget) {
2691  RenameTarget = false;
2692  bool Ret = false;
2693  if (hasUseOtherThanLLVMUsed(GA, U))
2694  Ret = true;
2695 
2696  // If the alias is externally visible, we may still be able to simplify it.
2697  if (!mayHaveOtherReferences(GA, U))
2698  return Ret;
2699 
2700  // If the aliasee has internal linkage, give it the name and linkage
2701  // of the alias, and delete the alias. This turns:
2702  // define internal ... @f(...)
2703  // @a = alias ... @f
2704  // into:
2705  // define ... @a(...)
2706  Constant *Aliasee = GA.getAliasee();
2707  GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts());
2708  if (!Target->hasLocalLinkage())
2709  return Ret;
2710 
2711  // Do not perform the transform if multiple aliases potentially target the
2712  // aliasee. This check also ensures that it is safe to replace the section
2713  // and other attributes of the aliasee with those of the alias.
2714  if (hasMoreThanOneUseOtherThanLLVMUsed(*Target, U))
2715  return Ret;
2716 
2717  RenameTarget = true;
2718  return true;
2719 }
2720 
2721 static bool
2723  SmallPtrSetImpl<const Comdat *> &NotDiscardableComdats) {
2724  bool Changed = false;
2725  LLVMUsed Used(M);
2726 
2727  for (GlobalValue *GV : Used.used())
2728  Used.compilerUsedErase(GV);
2729 
2730  for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end();
2731  I != E;) {
2732  GlobalAlias *J = &*I++;
2733 
2734  // Aliases without names cannot be referenced outside this module.
2735  if (!J->hasName() && !J->isDeclaration() && !J->hasLocalLinkage())
2737 
2738  if (deleteIfDead(*J, NotDiscardableComdats)) {
2739  Changed = true;
2740  continue;
2741  }
2742 
2743  // If the alias can change at link time, nothing can be done - bail out.
2744  if (J->isInterposable())
2745  continue;
2746 
2747  Constant *Aliasee = J->getAliasee();
2749  // We can't trivially replace the alias with the aliasee if the aliasee is
2750  // non-trivial in some way.
2751  // TODO: Try to handle non-zero GEPs of local aliasees.
2752  if (!Target)
2753  continue;
2754  Target->removeDeadConstantUsers();
2755 
2756  // Make all users of the alias use the aliasee instead.
2757  bool RenameTarget;
2758  if (!hasUsesToReplace(*J, Used, RenameTarget))
2759  continue;
2760 
2762  ++NumAliasesResolved;
2763  Changed = true;
2764 
2765  if (RenameTarget) {
2766  // Give the aliasee the name, linkage and other attributes of the alias.
2767  Target->takeName(&*J);
2768  Target->setLinkage(J->getLinkage());
2769  Target->setDSOLocal(J->isDSOLocal());
2770  Target->setVisibility(J->getVisibility());
2771  Target->setDLLStorageClass(J->getDLLStorageClass());
2772 
2773  if (Used.usedErase(&*J))
2774  Used.usedInsert(Target);
2775 
2776  if (Used.compilerUsedErase(&*J))
2777  Used.compilerUsedInsert(Target);
2778  } else if (mayHaveOtherReferences(*J, Used))
2779  continue;
2780 
2781  // Delete the alias.
2782  M.getAliasList().erase(J);
2783  ++NumAliasesRemoved;
2784  Changed = true;
2785  }
2786 
2787  Used.syncVariablesAndSets();
2788 
2789  return Changed;
2790 }
2791 
2793  LibFunc F = LibFunc_cxa_atexit;
2794  if (!TLI->has(F))
2795  return nullptr;
2796 
2797  Function *Fn = M.getFunction(TLI->getName(F));
2798  if (!Fn)
2799  return nullptr;
2800 
2801  // Make sure that the function has the correct prototype.
2802  if (!TLI->getLibFunc(*Fn, F) || F != LibFunc_cxa_atexit)
2803  return nullptr;
2804 
2805  return Fn;
2806 }
2807 
2808 /// Returns whether the given function is an empty C++ destructor and can
2809 /// therefore be eliminated.
2810 /// Note that we assume that other optimization passes have already simplified
2811 /// the code so we only look for a function with a single basic block, where
2812 /// the only allowed instructions are 'ret', 'call' to an empty C++ dtor and
2813 /// other side-effect free instructions.
2814 static bool cxxDtorIsEmpty(const Function &Fn,
2815  SmallPtrSet<const Function *, 8> &CalledFunctions) {
2816  // FIXME: We could eliminate C++ destructors if they're readonly/readnone and
2817  // nounwind, but that doesn't seem worth doing.
2818  if (Fn.isDeclaration())
2819  return false;
2820 
2821  if (++Fn.begin() != Fn.end())
2822  return false;
2823 
2824  const BasicBlock &EntryBlock = Fn.getEntryBlock();
2825  for (BasicBlock::const_iterator I = EntryBlock.begin(), E = EntryBlock.end();
2826  I != E; ++I) {
2827  if (const CallInst *CI = dyn_cast<CallInst>(I)) {
2828  // Ignore debug intrinsics.
2829  if (isa<DbgInfoIntrinsic>(CI))
2830  continue;
2831 
2832  const Function *CalledFn = CI->getCalledFunction();
2833 
2834  if (!CalledFn)
2835  return false;
2836 
2837  SmallPtrSet<const Function *, 8> NewCalledFunctions(CalledFunctions);
2838 
2839  // Don't treat recursive functions as empty.
2840  if (!NewCalledFunctions.insert(CalledFn).second)
2841  return false;
2842 
2843  if (!cxxDtorIsEmpty(*CalledFn, NewCalledFunctions))
2844  return false;
2845  } else if (isa<ReturnInst>(*I))
2846  return true; // We're done.
2847  else if (I->mayHaveSideEffects())
2848  return false; // Destructor with side effects, bail.
2849  }
2850 
2851  return false;
2852 }
2853 
2854 static bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) {
2855  /// Itanium C++ ABI p3.3.5:
2856  ///
2857  /// After constructing a global (or local static) object, that will require
2858  /// destruction on exit, a termination function is registered as follows:
2859  ///
2860  /// extern "C" int __cxa_atexit ( void (*f)(void *), void *p, void *d );
2861  ///
2862  /// This registration, e.g. __cxa_atexit(f,p,d), is intended to cause the
2863  /// call f(p) when DSO d is unloaded, before all such termination calls
2864  /// registered before this one. It returns zero if registration is
2865  /// successful, nonzero on failure.
2866 
2867  // This pass will look for calls to __cxa_atexit where the function is trivial
2868  // and remove them.
2869  bool Changed = false;
2870 
2871  for (auto I = CXAAtExitFn->user_begin(), E = CXAAtExitFn->user_end();
2872  I != E;) {
2873  // We're only interested in calls. Theoretically, we could handle invoke
2874  // instructions as well, but neither llvm-gcc nor clang generate invokes
2875  // to __cxa_atexit.
2876  CallInst *CI = dyn_cast<CallInst>(*I++);
2877  if (!CI)
2878  continue;
2879 
2880  Function *DtorFn =
2882  if (!DtorFn)
2883  continue;
2884 
2885  SmallPtrSet<const Function *, 8> CalledFunctions;
2886  if (!cxxDtorIsEmpty(*DtorFn, CalledFunctions))
2887  continue;
2888 
2889  // Just remove the call.
2891  CI->eraseFromParent();
2892 
2893  ++NumCXXDtorsRemoved;
2894 
2895  Changed |= true;
2896  }
2897 
2898  return Changed;
2899 }
2900 
2902  Module &M, const DataLayout &DL, TargetLibraryInfo *TLI,
2905  function_ref<DominatorTree &(Function &)> LookupDomTree) {
2906  SmallPtrSet<const Comdat *, 8> NotDiscardableComdats;
2907  bool Changed = false;
2908  bool LocalChange = true;
2909  while (LocalChange) {
2910  LocalChange = false;
2911 
2912  NotDiscardableComdats.clear();
2913  for (const GlobalVariable &GV : M.globals())
2914  if (const Comdat *C = GV.getComdat())
2915  if (!GV.isDiscardableIfUnused() || !GV.use_empty())
2916  NotDiscardableComdats.insert(C);
2917  for (Function &F : M)
2918  if (const Comdat *C = F.getComdat())
2919  if (!F.isDefTriviallyDead())
2920  NotDiscardableComdats.insert(C);
2921  for (GlobalAlias &GA : M.aliases())
2922  if (const Comdat *C = GA.getComdat())
2923  if (!GA.isDiscardableIfUnused() || !GA.use_empty())
2924  NotDiscardableComdats.insert(C);
2925 
2926  // Delete functions that are trivially dead, ccc -> fastcc
2927  LocalChange |= OptimizeFunctions(M, TLI, GetTTI, GetBFI, LookupDomTree,
2928  NotDiscardableComdats);
2929 
2930  // Optimize global_ctors list.
2931  LocalChange |= optimizeGlobalCtorsList(M, [&](Function *F) {
2932  return EvaluateStaticConstructor(F, DL, TLI);
2933  });
2934 
2935  // Optimize non-address-taken globals.
2936  LocalChange |= OptimizeGlobalVars(M, TLI, LookupDomTree,
2937  NotDiscardableComdats);
2938 
2939  // Resolve aliases, when possible.
2940  LocalChange |= OptimizeGlobalAliases(M, NotDiscardableComdats);
2941 
2942  // Try to remove trivial global destructors if they are not removed
2943  // already.
2944  Function *CXAAtExitFn = FindCXAAtExit(M, TLI);
2945  if (CXAAtExitFn)
2946  LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn);
2947 
2948  Changed |= LocalChange;
2949  }
2950 
2951  // TODO: Move all global ctors functions to the end of the module for code
2952  // layout.
2953 
2954  return Changed;
2955 }
2956 
2958  auto &DL = M.getDataLayout();
2959  auto &TLI = AM.getResult<TargetLibraryAnalysis>(M);
2960  auto &FAM =
2961  AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
2962  auto LookupDomTree = [&FAM](Function &F) -> DominatorTree &{
2963  return FAM.getResult<DominatorTreeAnalysis>(F);
2964  };
2965  auto GetTTI = [&FAM](Function &F) -> TargetTransformInfo & {
2966  return FAM.getResult<TargetIRAnalysis>(F);
2967  };
2968 
2969  auto GetBFI = [&FAM](Function &F) -> BlockFrequencyInfo & {
2970  return FAM.getResult<BlockFrequencyAnalysis>(F);
2971  };
2972 
2973  if (!optimizeGlobalsInModule(M, DL, &TLI, GetTTI, GetBFI, LookupDomTree))
2974  return PreservedAnalyses::all();
2975  return PreservedAnalyses::none();
2976 }
2977 
2978 namespace {
2979 
2980 struct GlobalOptLegacyPass : public ModulePass {
2981  static char ID; // Pass identification, replacement for typeid
2982 
2983  GlobalOptLegacyPass() : ModulePass(ID) {
2985  }
2986 
2987  bool runOnModule(Module &M) override {
2988  if (skipModule(M))
2989  return false;
2990 
2991  auto &DL = M.getDataLayout();
2992  auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
2993  auto LookupDomTree = [this](Function &F) -> DominatorTree & {
2994  return this->getAnalysis<DominatorTreeWrapperPass>(F).getDomTree();
2995  };
2996  auto GetTTI = [this](Function &F) -> TargetTransformInfo & {
2997  return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
2998  };
2999 
3000  auto GetBFI = [this](Function &F) -> BlockFrequencyInfo & {
3001  return this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
3002  };
3003 
3004  return optimizeGlobalsInModule(M, DL, TLI, GetTTI, GetBFI, LookupDomTree);
3005  }
3006 
3007  void getAnalysisUsage(AnalysisUsage &AU) const override {
3012  }
3013 };
3014 
3015 } // end anonymous namespace
3016 
3017 char GlobalOptLegacyPass::ID = 0;
3018 
3019 INITIALIZE_PASS_BEGIN(GlobalOptLegacyPass, "globalopt",
3020  "Global Variable Optimizer", false, false)
3025 INITIALIZE_PASS_END(GlobalOptLegacyPass, "globalopt",
3026  "Global Variable Optimizer", false, false)
3027 
3029  return new GlobalOptLegacyPass();
3030 }
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:410
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:585
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
C - The default llvm calling convention, compatible with C.
Definition: CallingConv.h:35
unsigned getOpcode() const
Return the opcode at the root of this constant expression.
Definition: Constants.h:1210
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:1602
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.
This class represents lattice values for constants.
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:65
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:1154
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:2201
static GetElementPtrInst * Create(Type *PointeeType, Value *Ptr, ArrayRef< Value *> IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Definition: Instructions.h:880
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:1744
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:630
gep_type_iterator gep_type_end(const User *GEP)
unsigned less or equal
Definition: InstrTypes.h:672
unsigned less than
Definition: InstrTypes.h:671
static bool OptimizeGlobalVars(Module &M, TargetLibraryInfo *TLI, function_ref< DominatorTree &(Function &)> LookupDomTree, SmallPtrSetImpl< const Comdat *> &NotDiscardableComdats)
Definition: GlobalOpt.cpp:2325
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:117
static bool hasChangeableCC(Function *F)
Return true if this is a calling convention that we&#39;d like to change.
Definition: GlobalOpt.cpp:2109
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:2358
StringRef getName(LibFunc F) const
Analysis pass providing the TargetTransformInfo.
static bool hasOnlyColdCalls(Function &F, function_ref< BlockFrequencyInfo &(Function &)> GetBFI)
Definition: GlobalOpt.cpp:2197
AtomicOrdering getOrdering() const
Returns the ordering constraint of this load instruction.
Definition: Instructions.h:248
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:705
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.
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:1186
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:521
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:645
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:1906
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:983
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:2563
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:265
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:269
const AliasListType & getAliasList() const
Get the Module&#39;s list of aliases (constant).
Definition: Module.h:538
Value * getArgOperand(unsigned i) const
Definition: InstrTypes.h:1135
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:529
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
static bool hasUsesToReplace(GlobalAlias &GA, const LLVMUsed &U, bool &RenameTarget)
Definition: GlobalOpt.cpp:2689
static void makeAllConstantUsesInstructions(Constant *C)
C may have non-instruction users, and allNonInstructionUsersCanBeMadeInstructions has returned true...
Definition: GlobalOpt.cpp:1874
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Definition: GlobalOpt.cpp:2957
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:2147
const DataLayout & getDataLayout() const
Get the data layout for the module&#39;s target platform.
Definition: Module.cpp:371
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:353
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:2184
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:556
bool isConstant() const
If the value is a global constant, its value is immutable throughout the runtime execution of the pro...
static Optional< unsigned > getOpcode(ArrayRef< VPValue *> Values)
Returns the opcode of Values or ~0 if they do not all agree.
Definition: VPlanSLP.cpp:197
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:2901
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:1200
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:2682
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:2228
static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal)
At this point, we have learned that the only two values ever stored into GV are its initializer and O...
Definition: GlobalOpt.cpp:1599
static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U)
Definition: GlobalOpt.cpp:2655
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:578
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"))
Fast - This calling convention attempts to make calls as fast as possible (e.g.
Definition: CallingConv.h:43
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:889
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:2078
static Function * FindCXAAtExit(Module &M, TargetLibraryInfo *TLI)
Definition: GlobalOpt.cpp:2792
static void setUsedInitializer(GlobalVariable &V, const SmallPtrSetImpl< GlobalValue *> &Init)
Definition: GlobalOpt.cpp:2569
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:321
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:429
constexpr char Attrs[]
Key for Kernel::Metadata::mAttrs.
void takeName(Value *V)
Transfer the name from V to this value.
Definition: Value.cpp:291
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:537
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:335
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:1773
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:854
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:750
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:423
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N users or more.
Definition: Value.cpp:135
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:1083
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
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
Definition: Instruction.h:308
DLLStorageClassTypes getDLLStorageClass() const
Definition: GlobalValue.h:259
VisibilityTypes getVisibility() const
Definition: GlobalValue.h:233
alias_iterator alias_end()
Definition: Module.h:619
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:3025
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:562
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:2095
A pair of DIGlobalVariable and DIExpression.
bool isUnordered() const
Definition: Instructions.h:279
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:2814
static Constant * get(StructType *T, ArrayRef< Constant *> V)
Definition: Constants.cpp:1044
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:3028
static bool isValidCandidateForColdCC(Function &F, function_ref< BlockFrequencyInfo &(Function &)> GetBFI, const std::vector< Function *> &AllCallsCold)
Definition: GlobalOpt.cpp:2161
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:2671
LLVMContext & getContext() const
getContext - Return a reference to the LLVMContext associated with this function. ...
Definition: Function.cpp:193
static UndefValue * get(Type *T)
Static factory methods - Return an &#39;undef&#39; object of the specified type.
Definition: Constants.cpp:1415
const Constant * stripPointerCasts() const
Definition: Constant.h:174
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs, and aliases.
Definition: Value.cpp:529
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:1207
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:673
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:580
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:2087
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:596
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:3025
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:2401
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:271
X86_ThisCall - Similar to X86_StdCall.
Definition: CallingConv.h:111
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:730
signed less than
Definition: InstrTypes.h:675
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:381
uint64_t getSizeInBytes() const
Definition: DataLayout.h:537
alias_iterator alias_begin()
Definition: Module.h:617
void getOperandBundlesAsDefs(SmallVectorImpl< OperandBundleDef > &Defs) const
Return the list of operand bundles attached to this instruction as a vector of OperandBundleDefs.
Definition: InstrTypes.h:1715
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:622
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:578
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:1437
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:176
static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL, TargetLibraryInfo *TLI)
Evaluate static constructors in the function, if we can.
Definition: GlobalOpt.cpp:2540
signed less or equal
Definition: InstrTypes.h:676
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:1848
static cl::opt< unsigned > Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), cl::init(100), cl::Hidden)
static Constant * getCast(unsigned ops, Constant *C, Type *Ty, bool OnlyIfReduced=false)
Convenience function for getting a Cast operation.
Definition: Constants.cpp:1530
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:2454
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:436
use_iterator use_begin()
Definition: Value.h:339
Predicate getPredicate() const
Return the predicate for this instruction.
Definition: InstrTypes.h:721
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
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
Definition: Instruction.h:311
iterator end()
Definition: Module.h:597
void setUnnamedAddr(UnnamedAddr Val)
Definition: GlobalValue.h:216
iterator begin() const
Definition: SmallPtrSet.h:397
uint64_t getElementOffset(unsigned Idx) const
Definition: DataLayout.h:551
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:670
static bool OptimizeGlobalAliases(Module &M, SmallPtrSetImpl< const Comdat *> &NotDiscardableComdats)
Definition: GlobalOpt.cpp:2722
const Value * stripPointerCastsNoFollowAliases() const
Strip off pointer casts and all-zero GEPs.
Definition: Value.cpp:533
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:214
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.
LLVM_NODISCARD 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:260
#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:595
static bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn)
Definition: GlobalOpt.cpp:2854
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:581
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:408
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
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
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:1254
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
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:2041
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:349
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:419
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:446
Type * getElementType() const
Definition: DerivedTypes.h:360
iterator_range< global_iterator > globals()
Definition: Module.h:584
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:669
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:1769
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:117
#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:1274
static Constant * get(ArrayRef< Constant *> V)
Definition: Constants.cpp:1079
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:674
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