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