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