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