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