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