lib/Transforms/IPO/GlobalOpt.cpp

   1 //===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass transforms simple global variables that never have their address
  11 // taken.  If obviously true, it marks read/write globals as constant, deletes
  12 // variables only stored to, etc.
  13 //
  14 //===----------------------------------------------------------------------===//
  15
  16 #include "llvm/Transforms/IPO.h"
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/STLExtras.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/ADT/SmallSet.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/ADT/Statistic.h"
  23 #include "llvm/Analysis/ConstantFolding.h"
  24 #include "llvm/Analysis/MemoryBuiltins.h"
  25 #include "llvm/Analysis/TargetLibraryInfo.h"
  26 #include "llvm/IR/CallSite.h"
  27 #include "llvm/IR/CallingConv.h"
  28 #include "llvm/IR/Constants.h"
  29 #include "llvm/IR/DataLayout.h"
  30 #include "llvm/IR/DerivedTypes.h"
  31 #include "llvm/IR/GetElementPtrTypeIterator.h"
  32 #include "llvm/IR/Instructions.h"
  33 #include "llvm/IR/IntrinsicInst.h"
  34 #include "llvm/IR/Module.h"
  35 #include "llvm/IR/Operator.h"
  36 #include "llvm/IR/ValueHandle.h"
  37 #include "llvm/Pass.h"
  38 #include "llvm/Support/Debug.h"
  39 #include "llvm/Support/ErrorHandling.h"
  40 #include "llvm/Support/MathExtras.h"
  41 #include "llvm/Support/raw_ostream.h"
  42 #include "llvm/Transforms/Utils/CtorUtils.h"
  43 #include "llvm/Transforms/Utils/GlobalStatus.h"
  44 #include "llvm/Transforms/Utils/ModuleUtils.h"
  45 #include <algorithm>
  46 #include <deque>
  47 using namespace llvm;
  48
  49 #define DEBUG_TYPE "globalopt"
  50
  51 STATISTIC(NumMarked    , "Number of globals marked constant");
  52 STATISTIC(NumUnnamed   , "Number of globals marked unnamed_addr");
  53 STATISTIC(NumSRA       , "Number of aggregate globals broken into scalars");
  54 STATISTIC(NumHeapSRA   , "Number of heap objects SRA'd");
  55 STATISTIC(NumSubstitute,"Number of globals with initializers stored into them");
  56 STATISTIC(NumDeleted   , "Number of globals deleted");
  57 STATISTIC(NumFnDeleted , "Number of functions deleted");
  58 STATISTIC(NumGlobUses  , "Number of global uses devirtualized");
  59 STATISTIC(NumLocalized , "Number of globals localized");
  60 STATISTIC(NumShrunkToBool  , "Number of global vars shrunk to booleans");
  61 STATISTIC(NumFastCallFns   , "Number of functions converted to fastcc");
  62 STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated");
  63 STATISTIC(NumNestRemoved   , "Number of nest attributes removed");
  64 STATISTIC(NumAliasesResolved, "Number of global aliases resolved");
  65 STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated");
  66 STATISTIC(NumCXXDtorsRemoved, "Number of global C++ destructors removed");
  67
  68 namespace {
  69   struct GlobalOpt : public ModulePass {
  70     void getAnalysisUsage(AnalysisUsage &AU) const override {
  71       AU.addRequired<TargetLibraryInfoWrapperPass>();
  72     }
  73     static char ID; // Pass identification, replacement for typeid
  74     GlobalOpt() : ModulePass(ID) {
  75       initializeGlobalOptPass(*PassRegistry::getPassRegistry());
  76     }
  77
  78     bool runOnModule(Module &M) override;
  79
  80   private:
  81     bool OptimizeFunctions(Module &M);
  82     bool OptimizeGlobalVars(Module &M);
  83     bool OptimizeGlobalAliases(Module &M);
  84     bool ProcessGlobal(GlobalVariable *GV,Module::global_iterator &GVI);
  85     bool ProcessInternalGlobal(GlobalVariable *GV,Module::global_iterator &GVI,
  86                                const GlobalStatus &GS);
  87     bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn);
  88
  89     TargetLibraryInfo *TLI;
  90     SmallSet<const Comdat *, 8> NotDiscardableComdats;
  91   };
  92 }
  93
  94 char GlobalOpt::ID = 0;
  95 INITIALIZE_PASS_BEGIN(GlobalOpt, "globalopt",
  96                 "Global Variable Optimizer", false, false)
  97 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
  98 INITIALIZE_PASS_END(GlobalOpt, "globalopt",
  99                 "Global Variable Optimizer", false, false)
 100
 101 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
 102
 103 /// isLeakCheckerRoot - Is this global variable possibly used by a leak checker
 104 /// as a root?  If so, we might not really want to eliminate the stores to it.
 105 static bool isLeakCheckerRoot(GlobalVariable *GV) {
 106   // A global variable is a root if it is a pointer, or could plausibly contain
 107   // a pointer.  There are two challenges; one is that we could have a struct
 108   // the has an inner member which is a pointer.  We recurse through the type to
 109   // detect these (up to a point).  The other is that we may actually be a union
 110   // of a pointer and another type, and so our LLVM type is an integer which
 111   // gets converted into a pointer, or our type is an [i8 x #] with a pointer
 112   // potentially contained here.
 113
 114   if (GV->hasPrivateLinkage())
 115     return false;
 116
 117   SmallVector<Type *, 4> Types;
 118   Types.push_back(cast<PointerType>(GV->getType())->getElementType());
 119
 120   unsigned Limit = 20;
 121   do {
 122     Type *Ty = Types.pop_back_val();
 123     switch (Ty->getTypeID()) {
 124       default: break;
 125       case Type::PointerTyID: return true;
 126       case Type::ArrayTyID:
 127       case Type::VectorTyID: {
 128         SequentialType *STy = cast<SequentialType>(Ty);
 129         Types.push_back(STy->getElementType());
 130         break;
 131       }
 132       case Type::StructTyID: {
 133         StructType *STy = cast<StructType>(Ty);
 134         if (STy->isOpaque()) return true;
 135         for (StructType::element_iterator I = STy->element_begin(),
 136                  E = STy->element_end(); I != E; ++I) {
 137           Type *InnerTy = *I;
 138           if (isa<PointerType>(InnerTy)) return true;
 139           if (isa<CompositeType>(InnerTy))
 140             Types.push_back(InnerTy);
 141         }
 142         break;
 143       }
 144     }
 145     if (--Limit == 0) return true;
 146   } while (!Types.empty());
 147   return false;
 148 }
 149
 150 /// Given a value that is stored to a global but never read, determine whether
 151 /// it's safe to remove the store and the chain of computation that feeds the
 152 /// store.
 153 static bool IsSafeComputationToRemove(Value *V, const TargetLibraryInfo *TLI) {
 154   do {
 155     if (isa<Constant>(V))
 156       return true;
 157     if (!V->hasOneUse())
 158       return false;
 159     if (isa<LoadInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V) ||
 160         isa<GlobalValue>(V))
 161       return false;
 162     if (isAllocationFn(V, TLI))
 163       return true;
 164
 165     Instruction *I = cast<Instruction>(V);
 166     if (I->mayHaveSideEffects())
 167       return false;
 168     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
 169       if (!GEP->hasAllConstantIndices())
 170         return false;
 171     } else if (I->getNumOperands() != 1) {
 172       return false;
 173     }
 174
 175     V = I->getOperand(0);
 176   } while (1);
 177 }
 178
 179 /// CleanupPointerRootUsers - This GV is a pointer root.  Loop over all users
 180 /// of the global and clean up any that obviously don't assign the global a
 181 /// value that isn't dynamically allocated.
 182 ///
 183 static bool CleanupPointerRootUsers(GlobalVariable *GV,
 184                                     const TargetLibraryInfo *TLI) {
 185   // A brief explanation of leak checkers.  The goal is to find bugs where
 186   // pointers are forgotten, causing an accumulating growth in memory
 187   // usage over time.  The common strategy for leak checkers is to whitelist the
 188   // memory pointed to by globals at exit.  This is popular because it also
 189   // solves another problem where the main thread of a C++ program may shut down
 190   // before other threads that are still expecting to use those globals.  To
 191   // handle that case, we expect the program may create a singleton and never
 192   // destroy it.
 193
 194   bool Changed = false;
 195
 196   // If Dead[n].first is the only use of a malloc result, we can delete its
 197   // chain of computation and the store to the global in Dead[n].second.
 198   SmallVector<std::pair<Instruction *, Instruction *>, 32> Dead;
 199
 200   // Constants can't be pointers to dynamically allocated memory.
 201   for (Value::user_iterator UI = GV->user_begin(), E = GV->user_end();
 202        UI != E;) {
 203     User *U = *UI++;
 204     if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 205       Value *V = SI->getValueOperand();
 206       if (isa<Constant>(V)) {
 207         Changed = true;
 208         SI->eraseFromParent();
 209       } else if (Instruction *I = dyn_cast<Instruction>(V)) {
 210         if (I->hasOneUse())
 211           Dead.push_back(std::make_pair(I, SI));
 212       }
 213     } else if (MemSetInst *MSI = dyn_cast<MemSetInst>(U)) {
 214       if (isa<Constant>(MSI->getValue())) {
 215         Changed = true;
 216         MSI->eraseFromParent();
 217       } else if (Instruction *I = dyn_cast<Instruction>(MSI->getValue())) {
 218         if (I->hasOneUse())
 219           Dead.push_back(std::make_pair(I, MSI));
 220       }
 221     } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(U)) {
 222       GlobalVariable *MemSrc = dyn_cast<GlobalVariable>(MTI->getSource());
 223       if (MemSrc && MemSrc->isConstant()) {
 224         Changed = true;
 225         MTI->eraseFromParent();
 226       } else if (Instruction *I = dyn_cast<Instruction>(MemSrc)) {
 227         if (I->hasOneUse())
 228           Dead.push_back(std::make_pair(I, MTI));
 229       }
 230     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
 231       if (CE->use_empty()) {
 232         CE->destroyConstant();
 233         Changed = true;
 234       }
 235     } else if (Constant *C = dyn_cast<Constant>(U)) {
 236       if (isSafeToDestroyConstant(C)) {
 237         C->destroyConstant();
 238         // This could have invalidated UI, start over from scratch.
 239         Dead.clear();
 240         CleanupPointerRootUsers(GV, TLI);
 241         return true;
 242       }
 243     }
 244   }
 245
 246   for (int i = 0, e = Dead.size(); i != e; ++i) {
 247     if (IsSafeComputationToRemove(Dead[i].first, TLI)) {
 248       Dead[i].second->eraseFromParent();
 249       Instruction *I = Dead[i].first;
 250       do {
 251         if (isAllocationFn(I, TLI))
 252           break;
 253         Instruction *J = dyn_cast<Instruction>(I->getOperand(0));
 254         if (!J)
 255           break;
 256         I->eraseFromParent();
 257         I = J;
 258       } while (1);
 259       I->eraseFromParent();
 260     }
 261   }
 262
 263   return Changed;
 264 }
 265
 266 /// CleanupConstantGlobalUsers - We just marked GV constant.  Loop over all
 267 /// users of the global, cleaning up the obvious ones.  This is largely just a
 268 /// quick scan over the use list to clean up the easy and obvious cruft.  This
 269 /// returns true if it made a change.
 270 static bool CleanupConstantGlobalUsers(Value *V, Constant *Init,
 271                                        const DataLayout &DL,
 272                                        TargetLibraryInfo *TLI) {
 273   bool Changed = false;
 274   // Note that we need to use a weak value handle for the worklist items. When
 275   // we delete a constant array, we may also be holding pointer to one of its
 276   // elements (or an element of one of its elements if we're dealing with an
 277   // array of arrays) in the worklist.
 278   SmallVector<WeakVH, 8> WorkList(V->user_begin(), V->user_end());
 279   while (!WorkList.empty()) {
 280     Value *UV = WorkList.pop_back_val();
 281     if (!UV)
 282       continue;
 283
 284     User *U = cast<User>(UV);
 285
 286     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
 287       if (Init) {
 288         // Replace the load with the initializer.
 289         LI->replaceAllUsesWith(Init);
 290         LI->eraseFromParent();
 291         Changed = true;
 292       }
 293     } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
 294       // Store must be unreachable or storing Init into the global.
 295       SI->eraseFromParent();
 296       Changed = true;
 297     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
 298       if (CE->getOpcode() == Instruction::GetElementPtr) {
 299         Constant *SubInit = nullptr;
 300         if (Init)
 301           SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
 302         Changed |= CleanupConstantGlobalUsers(CE, SubInit, DL, TLI);
 303       } else if ((CE->getOpcode() == Instruction::BitCast &&
 304                   CE->getType()->isPointerTy()) ||
 305                  CE->getOpcode() == Instruction::AddrSpaceCast) {
 306         // Pointer cast, delete any stores and memsets to the global.
 307         Changed |= CleanupConstantGlobalUsers(CE, nullptr, DL, TLI);
 308       }
 309
 310       if (CE->use_empty()) {
 311         CE->destroyConstant();
 312         Changed = true;
 313       }
 314     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
 315       // Do not transform "gepinst (gep constexpr (GV))" here, because forming
 316       // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold
 317       // and will invalidate our notion of what Init is.
 318       Constant *SubInit = nullptr;
 319       if (!isa<ConstantExpr>(GEP->getOperand(0))) {
 320         ConstantExpr *CE = dyn_cast_or_null<ConstantExpr>(
 321             ConstantFoldInstruction(GEP, DL, TLI));
 322         if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr)
 323           SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
 324
 325         // If the initializer is an all-null value and we have an inbounds GEP,
 326         // we already know what the result of any load from that GEP is.
 327         // TODO: Handle splats.
 328         if (Init && isa<ConstantAggregateZero>(Init) && GEP->isInBounds())
 329           SubInit = Constant::getNullValue(GEP->getType()->getElementType());
 330       }
 331       Changed |= CleanupConstantGlobalUsers(GEP, SubInit, DL, TLI);
 332
 333       if (GEP->use_empty()) {
 334         GEP->eraseFromParent();
 335         Changed = true;
 336       }
 337     } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv
 338       if (MI->getRawDest() == V) {
 339         MI->eraseFromParent();
 340         Changed = true;
 341       }
 342
 343     } else if (Constant *C = dyn_cast<Constant>(U)) {
 344       // If we have a chain of dead constantexprs or other things dangling from
 345       // us, and if they are all dead, nuke them without remorse.
 346       if (isSafeToDestroyConstant(C)) {
 347         C->destroyConstant();
 348         CleanupConstantGlobalUsers(V, Init, DL, TLI);
 349         return true;
 350       }
 351     }
 352   }
 353   return Changed;
 354 }
 355
 356 /// isSafeSROAElementUse - Return true if the specified instruction is a safe
 357 /// user of a derived expression from a global that we want to SROA.
 358 static bool isSafeSROAElementUse(Value *V) {
 359   // We might have a dead and dangling constant hanging off of here.
 360   if (Constant *C = dyn_cast<Constant>(V))
 361     return isSafeToDestroyConstant(C);
 362
 363   Instruction *I = dyn_cast<Instruction>(V);
 364   if (!I) return false;
 365
 366   // Loads are ok.
 367   if (isa<LoadInst>(I)) return true;
 368
 369   // Stores *to* the pointer are ok.
 370   if (StoreInst *SI = dyn_cast<StoreInst>(I))
 371     return SI->getOperand(0) != V;
 372
 373   // Otherwise, it must be a GEP.
 374   GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I);
 375   if (!GEPI) return false;
 376
 377   if (GEPI->getNumOperands() < 3 || !isa<Constant>(GEPI->getOperand(1)) ||
 378       !cast<Constant>(GEPI->getOperand(1))->isNullValue())
 379     return false;
 380
 381   for (User *U : GEPI->users())
 382     if (!isSafeSROAElementUse(U))
 383       return false;
 384   return true;
 385 }
 386
 387
 388 /// IsUserOfGlobalSafeForSRA - U is a direct user of the specified global value.
 389 /// Look at it and its uses and decide whether it is safe to SROA this global.
 390 ///
 391 static bool IsUserOfGlobalSafeForSRA(User *U, GlobalValue *GV) {
 392   // The user of the global must be a GEP Inst or a ConstantExpr GEP.
 393   if (!isa<GetElementPtrInst>(U) &&
 394       (!isa<ConstantExpr>(U) ||
 395        cast<ConstantExpr>(U)->getOpcode() != Instruction::GetElementPtr))
 396     return false;
 397
 398   // Check to see if this ConstantExpr GEP is SRA'able.  In particular, we
 399   // don't like < 3 operand CE's, and we don't like non-constant integer
 400   // indices.  This enforces that all uses are 'gep GV, 0, C, ...' for some
 401   // value of C.
 402   if (U->getNumOperands() < 3 || !isa<Constant>(U->getOperand(1)) ||
 403       !cast<Constant>(U->getOperand(1))->isNullValue() ||
 404       !isa<ConstantInt>(U->getOperand(2)))
 405     return false;
 406
 407   gep_type_iterator GEPI = gep_type_begin(U), E = gep_type_end(U);
 408   ++GEPI;  // Skip over the pointer index.
 409
 410   // If this is a use of an array allocation, do a bit more checking for sanity.
 411   if (ArrayType *AT = dyn_cast<ArrayType>(*GEPI)) {
 412     uint64_t NumElements = AT->getNumElements();
 413     ConstantInt *Idx = cast<ConstantInt>(U->getOperand(2));
 414
 415     // Check to make sure that index falls within the array.  If not,
 416     // something funny is going on, so we won't do the optimization.
 417     //
 418     if (Idx->getZExtValue() >= NumElements)
 419       return false;
 420
 421     // We cannot scalar repl this level of the array unless any array
 422     // sub-indices are in-range constants.  In particular, consider:
 423     // A[0][i].  We cannot know that the user isn't doing invalid things like
 424     // allowing i to index an out-of-range subscript that accesses A[1].
 425     //
 426     // Scalar replacing *just* the outer index of the array is probably not
 427     // going to be a win anyway, so just give up.
 428     for (++GEPI; // Skip array index.
 429          GEPI != E;
 430          ++GEPI) {
 431       uint64_t NumElements;
 432       if (ArrayType *SubArrayTy = dyn_cast<ArrayType>(*GEPI))
 433         NumElements = SubArrayTy->getNumElements();
 434       else if (VectorType *SubVectorTy = dyn_cast<VectorType>(*GEPI))
 435         NumElements = SubVectorTy->getNumElements();
 436       else {
 437         assert((*GEPI)->isStructTy() &&
 438                "Indexed GEP type is not array, vector, or struct!");
 439         continue;
 440       }
 441
 442       ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand());
 443       if (!IdxVal || IdxVal->getZExtValue() >= NumElements)
 444         return false;
 445     }
 446   }
 447
 448   for (User *UU : U->users())
 449     if (!isSafeSROAElementUse(UU))
 450       return false;
 451
 452   return true;
 453 }
 454
 455 /// GlobalUsersSafeToSRA - Look at all uses of the global and decide whether it
 456 /// is safe for us to perform this transformation.
 457 ///
 458 static bool GlobalUsersSafeToSRA(GlobalValue *GV) {
 459   for (User *U : GV->users())
 460     if (!IsUserOfGlobalSafeForSRA(U, GV))
 461       return false;
 462
 463   return true;
 464 }
 465
 466
 467 /// SRAGlobal - Perform scalar replacement of aggregates on the specified global
 468 /// variable.  This opens the door for other optimizations by exposing the
 469 /// behavior of the program in a more fine-grained way.  We have determined that
 470 /// this transformation is safe already.  We return the first global variable we
 471 /// insert so that the caller can reprocess it.
 472 static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &DL) {
 473   // Make sure this global only has simple uses that we can SRA.
 474   if (!GlobalUsersSafeToSRA(GV))
 475     return nullptr;
 476
 477   assert(GV->hasLocalLinkage() && !GV->isConstant());
 478   Constant *Init = GV->getInitializer();
 479   Type *Ty = Init->getType();
 480
 481   std::vector<GlobalVariable*> NewGlobals;
 482   Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
 483
 484   // Get the alignment of the global, either explicit or target-specific.
 485   unsigned StartAlignment = GV->getAlignment();
 486   if (StartAlignment == 0)
 487     StartAlignment = DL.getABITypeAlignment(GV->getType());
 488
 489   if (StructType *STy = dyn_cast<StructType>(Ty)) {
 490     NewGlobals.reserve(STy->getNumElements());
 491     const StructLayout &Layout = *DL.getStructLayout(STy);
 492     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
 493       Constant *In = Init->getAggregateElement(i);
 494       assert(In && "Couldn't get element of initializer?");
 495       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false,
 496                                                GlobalVariable::InternalLinkage,
 497                                                In, GV->getName()+"."+Twine(i),
 498                                                GV->getThreadLocalMode(),
 499                                               GV->getType()->getAddressSpace());
 500       Globals.insert(GV->getIterator(), NGV);
 501       NewGlobals.push_back(NGV);
 502
 503       // Calculate the known alignment of the field.  If the original aggregate
 504       // had 256 byte alignment for example, something might depend on that:
 505       // propagate info to each field.
 506       uint64_t FieldOffset = Layout.getElementOffset(i);
 507       unsigned NewAlign = (unsigned)MinAlign(StartAlignment, FieldOffset);
 508       if (NewAlign > DL.getABITypeAlignment(STy->getElementType(i)))
 509         NGV->setAlignment(NewAlign);
 510     }
 511   } else if (SequentialType *STy = dyn_cast<SequentialType>(Ty)) {
 512     unsigned NumElements = 0;
 513     if (ArrayType *ATy = dyn_cast<ArrayType>(STy))
 514       NumElements = ATy->getNumElements();
 515     else
 516       NumElements = cast<VectorType>(STy)->getNumElements();
 517
 518     if (NumElements > 16 && GV->hasNUsesOrMore(16))
 519       return nullptr; // It's not worth it.
 520     NewGlobals.reserve(NumElements);
 521
 522     uint64_t EltSize = DL.getTypeAllocSize(STy->getElementType());
 523     unsigned EltAlign = DL.getABITypeAlignment(STy->getElementType());
 524     for (unsigned i = 0, e = NumElements; i != e; ++i) {
 525       Constant *In = Init->getAggregateElement(i);
 526       assert(In && "Couldn't get element of initializer?");
 527
 528       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false,
 529                                                GlobalVariable::InternalLinkage,
 530                                                In, GV->getName()+"."+Twine(i),
 531                                                GV->getThreadLocalMode(),
 532                                               GV->getType()->getAddressSpace());
 533       Globals.insert(GV->getIterator(), NGV);
 534       NewGlobals.push_back(NGV);
 535
 536       // Calculate the known alignment of the field.  If the original aggregate
 537       // had 256 byte alignment for example, something might depend on that:
 538       // propagate info to each field.
 539       unsigned NewAlign = (unsigned)MinAlign(StartAlignment, EltSize*i);
 540       if (NewAlign > EltAlign)
 541         NGV->setAlignment(NewAlign);
 542     }
 543   }
 544
 545   if (NewGlobals.empty())
 546     return nullptr;
 547
 548   DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV << "\n");
 549
 550   Constant *NullInt =Constant::getNullValue(Type::getInt32Ty(GV->getContext()));
 551
 552   // Loop over all of the uses of the global, replacing the constantexpr geps,
 553   // with smaller constantexpr geps or direct references.
 554   while (!GV->use_empty()) {
 555     User *GEP = GV->user_back();
 556     assert(((isa<ConstantExpr>(GEP) &&
 557              cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)||
 558             isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!");
 559
 560     // Ignore the 1th operand, which has to be zero or else the program is quite
 561     // broken (undefined).  Get the 2nd operand, which is the structure or array
 562     // index.
 563     unsigned Val = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
 564     if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access.
 565
 566     Value *NewPtr = NewGlobals[Val];
 567     Type *NewTy = NewGlobals[Val]->getValueType();
 568
 569     // Form a shorter GEP if needed.
 570     if (GEP->getNumOperands() > 3) {
 571       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) {
 572         SmallVector<Constant*, 8> Idxs;
 573         Idxs.push_back(NullInt);
 574         for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
 575           Idxs.push_back(CE->getOperand(i));
 576         NewPtr =
 577             ConstantExpr::getGetElementPtr(NewTy, cast<Constant>(NewPtr), Idxs);
 578       } else {
 579         GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP);
 580         SmallVector<Value*, 8> Idxs;
 581         Idxs.push_back(NullInt);
 582         for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i)
 583           Idxs.push_back(GEPI->getOperand(i));
 584         NewPtr = GetElementPtrInst::Create(
 585             NewTy, NewPtr, Idxs, GEPI->getName() + "." + Twine(Val), GEPI);
 586       }
 587     }
 588     GEP->replaceAllUsesWith(NewPtr);
 589
 590     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP))
 591       GEPI->eraseFromParent();
 592     else
 593       cast<ConstantExpr>(GEP)->destroyConstant();
 594   }
 595
 596   // Delete the old global, now that it is dead.
 597   Globals.erase(GV);
 598   ++NumSRA;
 599
 600   // Loop over the new globals array deleting any globals that are obviously
 601   // dead.  This can arise due to scalarization of a structure or an array that
 602   // has elements that are dead.
 603   unsigned FirstGlobal = 0;
 604   for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i)
 605     if (NewGlobals[i]->use_empty()) {
 606       Globals.erase(NewGlobals[i]);
 607       if (FirstGlobal == i) ++FirstGlobal;
 608     }
 609
 610   return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : nullptr;
 611 }
 612
 613 /// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified
 614 /// value will trap if the value is dynamically null.  PHIs keeps track of any
 615 /// phi nodes we've seen to avoid reprocessing them.
 616 static bool AllUsesOfValueWillTrapIfNull(const Value *V,
 617                                         SmallPtrSetImpl<const PHINode*> &PHIs) {
 618   for (const User *U : V->users())
 619     if (isa<LoadInst>(U)) {
 620       // Will trap.
 621     } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
 622       if (SI->getOperand(0) == V) {
 623         //cerr << "NONTRAPPING USE: " << *U;
 624         return false;  // Storing the value.
 625       }
 626     } else if (const CallInst *CI = dyn_cast<CallInst>(U)) {
 627       if (CI->getCalledValue() != V) {
 628         //cerr << "NONTRAPPING USE: " << *U;
 629         return false;  // Not calling the ptr
 630       }
 631     } else if (const InvokeInst *II = dyn_cast<InvokeInst>(U)) {
 632       if (II->getCalledValue() != V) {
 633         //cerr << "NONTRAPPING USE: " << *U;
 634         return false;  // Not calling the ptr
 635       }
 636     } else if (const BitCastInst *CI = dyn_cast<BitCastInst>(U)) {
 637       if (!AllUsesOfValueWillTrapIfNull(CI, PHIs)) return false;
 638     } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
 639       if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false;
 640     } else if (const PHINode *PN = dyn_cast<PHINode>(U)) {
 641       // If we've already seen this phi node, ignore it, it has already been
 642       // checked.
 643       if (PHIs.insert(PN).second && !AllUsesOfValueWillTrapIfNull(PN, PHIs))
 644         return false;
 645     } else if (isa<ICmpInst>(U) &&
 646                isa<ConstantPointerNull>(U->getOperand(1))) {
 647       // Ignore icmp X, null
 648     } else {
 649       //cerr << "NONTRAPPING USE: " << *U;
 650       return false;
 651     }
 652
 653   return true;
 654 }
 655
 656 /// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads
 657 /// from GV will trap if the loaded value is null.  Note that this also permits
 658 /// comparisons of the loaded value against null, as a special case.
 659 static bool AllUsesOfLoadedValueWillTrapIfNull(const GlobalVariable *GV) {
 660   for (const User *U : GV->users())
 661     if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
 662       SmallPtrSet<const PHINode*, 8> PHIs;
 663       if (!AllUsesOfValueWillTrapIfNull(LI, PHIs))
 664         return false;
 665     } else if (isa<StoreInst>(U)) {
 666       // Ignore stores to the global.
 667     } else {
 668       // We don't know or understand this user, bail out.
 669       //cerr << "UNKNOWN USER OF GLOBAL!: " << *U;
 670       return false;
 671     }
 672   return true;
 673 }
 674
 675 static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) {
 676   bool Changed = false;
 677   for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) {
 678     Instruction *I = cast<Instruction>(*UI++);
 679     if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
 680       LI->setOperand(0, NewV);
 681       Changed = true;
 682     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
 683       if (SI->getOperand(1) == V) {
 684         SI->setOperand(1, NewV);
 685         Changed = true;
 686       }
 687     } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
 688       CallSite CS(I);
 689       if (CS.getCalledValue() == V) {
 690         // Calling through the pointer!  Turn into a direct call, but be careful
 691         // that the pointer is not also being passed as an argument.
 692         CS.setCalledFunction(NewV);
 693         Changed = true;
 694         bool PassedAsArg = false;
 695         for (unsigned i = 0, e = CS.arg_size(); i != e; ++i)
 696           if (CS.getArgument(i) == V) {
 697             PassedAsArg = true;
 698             CS.setArgument(i, NewV);
 699           }
 700
 701         if (PassedAsArg) {
 702           // Being passed as an argument also.  Be careful to not invalidate UI!
 703           UI = V->user_begin();
 704         }
 705       }
 706     } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
 707       Changed |= OptimizeAwayTrappingUsesOfValue(CI,
 708                                 ConstantExpr::getCast(CI->getOpcode(),
 709                                                       NewV, CI->getType()));
 710       if (CI->use_empty()) {
 711         Changed = true;
 712         CI->eraseFromParent();
 713       }
 714     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
 715       // Should handle GEP here.
 716       SmallVector<Constant*, 8> Idxs;
 717       Idxs.reserve(GEPI->getNumOperands()-1);
 718       for (User::op_iterator i = GEPI->op_begin() + 1, e = GEPI->op_end();
 719            i != e; ++i)
 720         if (Constant *C = dyn_cast<Constant>(*i))
 721           Idxs.push_back(C);
 722         else
 723           break;
 724       if (Idxs.size() == GEPI->getNumOperands()-1)
 725         Changed |= OptimizeAwayTrappingUsesOfValue(
 726             GEPI, ConstantExpr::getGetElementPtr(nullptr, NewV, Idxs));
 727       if (GEPI->use_empty()) {
 728         Changed = true;
 729         GEPI->eraseFromParent();
 730       }
 731     }
 732   }
 733
 734   return Changed;
 735 }
 736
 737
 738 /// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null
 739 /// value stored into it.  If there are uses of the loaded value that would trap
 740 /// if the loaded value is dynamically null, then we know that they cannot be
 741 /// reachable with a null optimize away the load.
 742 static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV,
 743                                             const DataLayout &DL,
 744                                             TargetLibraryInfo *TLI) {
 745   bool Changed = false;
 746
 747   // Keep track of whether we are able to remove all the uses of the global
 748   // other than the store that defines it.
 749   bool AllNonStoreUsesGone = true;
 750
 751   // Replace all uses of loads with uses of uses of the stored value.
 752   for (Value::user_iterator GUI = GV->user_begin(), E = GV->user_end(); GUI != E;){
 753     User *GlobalUser = *GUI++;
 754     if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) {
 755       Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV);
 756       // If we were able to delete all uses of the loads
 757       if (LI->use_empty()) {
 758         LI->eraseFromParent();
 759         Changed = true;
 760       } else {
 761         AllNonStoreUsesGone = false;
 762       }
 763     } else if (isa<StoreInst>(GlobalUser)) {
 764       // Ignore the store that stores "LV" to the global.
 765       assert(GlobalUser->getOperand(1) == GV &&
 766              "Must be storing *to* the global");
 767     } else {
 768       AllNonStoreUsesGone = false;
 769
 770       // If we get here we could have other crazy uses that are transitively
 771       // loaded.
 772       assert((isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) ||
 773               isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) ||
 774               isa<BitCastInst>(GlobalUser) ||
 775               isa<GetElementPtrInst>(GlobalUser)) &&
 776              "Only expect load and stores!");
 777     }
 778   }
 779
 780   if (Changed) {
 781     DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV << "\n");
 782     ++NumGlobUses;
 783   }
 784
 785   // If we nuked all of the loads, then none of the stores are needed either,
 786   // nor is the global.
 787   if (AllNonStoreUsesGone) {
 788     if (isLeakCheckerRoot(GV)) {
 789       Changed |= CleanupPointerRootUsers(GV, TLI);
 790     } else {
 791       Changed = true;
 792       CleanupConstantGlobalUsers(GV, nullptr, DL, TLI);
 793     }
 794     if (GV->use_empty()) {
 795       DEBUG(dbgs() << "  *** GLOBAL NOW DEAD!\n");
 796       Changed = true;
 797       GV->eraseFromParent();
 798       ++NumDeleted;
 799     }
 800   }
 801   return Changed;
 802 }
 803
 804 /// ConstantPropUsersOf - Walk the use list of V, constant folding all of the
 805 /// instructions that are foldable.
 806 static void ConstantPropUsersOf(Value *V, const DataLayout &DL,
 807                                 TargetLibraryInfo *TLI) {
 808   for (Value::user_iterator UI = V->user_begin(), E = V->user_end(); UI != E; )
 809     if (Instruction *I = dyn_cast<Instruction>(*UI++))
 810       if (Constant *NewC = ConstantFoldInstruction(I, DL, TLI)) {
 811         I->replaceAllUsesWith(NewC);
 812
 813         // Advance UI to the next non-I use to avoid invalidating it!
 814         // Instructions could multiply use V.
 815         while (UI != E && *UI == I)
 816           ++UI;
 817         I->eraseFromParent();
 818       }
 819 }
 820
 821 /// OptimizeGlobalAddressOfMalloc - This function takes the specified global
 822 /// variable, and transforms the program as if it always contained the result of
 823 /// the specified malloc.  Because it is always the result of the specified
 824 /// malloc, there is no reason to actually DO the malloc.  Instead, turn the
 825 /// malloc into a global, and any loads of GV as uses of the new global.
 826 static GlobalVariable *
 827 OptimizeGlobalAddressOfMalloc(GlobalVariable *GV, CallInst *CI, Type *AllocTy,
 828                               ConstantInt *NElements, const DataLayout &DL,
 829                               TargetLibraryInfo *TLI) {
 830   DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << "  CALL = " << *CI << '\n');
 831
 832   Type *GlobalType;
 833   if (NElements->getZExtValue() == 1)
 834     GlobalType = AllocTy;
 835   else
 836     // If we have an array allocation, the global variable is of an array.
 837     GlobalType = ArrayType::get(AllocTy, NElements->getZExtValue());
 838
 839   // Create the new global variable.  The contents of the malloc'd memory is
 840   // undefined, so initialize with an undef value.
 841   GlobalVariable *NewGV = new GlobalVariable(*GV->getParent(),
 842                                              GlobalType, false,
 843                                              GlobalValue::InternalLinkage,
 844                                              UndefValue::get(GlobalType),
 845                                              GV->getName()+".body",
 846                                              GV,
 847                                              GV->getThreadLocalMode());
 848
 849   // If there are bitcast users of the malloc (which is typical, usually we have
 850   // a malloc + bitcast) then replace them with uses of the new global.  Update
 851   // other users to use the global as well.
 852   BitCastInst *TheBC = nullptr;
 853   while (!CI->use_empty()) {
 854     Instruction *User = cast<Instruction>(CI->user_back());
 855     if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) {
 856       if (BCI->getType() == NewGV->getType()) {
 857         BCI->replaceAllUsesWith(NewGV);
 858         BCI->eraseFromParent();
 859       } else {
 860         BCI->setOperand(0, NewGV);
 861       }
 862     } else {
 863       if (!TheBC)
 864         TheBC = new BitCastInst(NewGV, CI->getType(), "newgv", CI);
 865       User->replaceUsesOfWith(CI, TheBC);
 866     }
 867   }
 868
 869   Constant *RepValue = NewGV;
 870   if (NewGV->getType() != GV->getType()->getElementType())
 871     RepValue = ConstantExpr::getBitCast(RepValue,
 872                                         GV->getType()->getElementType());
 873
 874   // If there is a comparison against null, we will insert a global bool to
 875   // keep track of whether the global was initialized yet or not.
 876   GlobalVariable *InitBool =
 877     new GlobalVariable(Type::getInt1Ty(GV->getContext()), false,
 878                        GlobalValue::InternalLinkage,
 879                        ConstantInt::getFalse(GV->getContext()),
 880                        GV->getName()+".init", GV->getThreadLocalMode());
 881   bool InitBoolUsed = false;
 882
 883   // Loop over all uses of GV, processing them in turn.
 884   while (!GV->use_empty()) {
 885     if (StoreInst *SI = dyn_cast<StoreInst>(GV->user_back())) {
 886       // The global is initialized when the store to it occurs.
 887       new StoreInst(ConstantInt::getTrue(GV->getContext()), InitBool, false, 0,
 888                     SI->getOrdering(), SI->getSynchScope(), SI);
 889       SI->eraseFromParent();
 890       continue;
 891     }
 892
 893     LoadInst *LI = cast<LoadInst>(GV->user_back());
 894     while (!LI->use_empty()) {
 895       Use &LoadUse = *LI->use_begin();
 896       ICmpInst *ICI = dyn_cast<ICmpInst>(LoadUse.getUser());
 897       if (!ICI) {
 898         LoadUse = RepValue;
 899         continue;
 900       }
 901
 902       // Replace the cmp X, 0 with a use of the bool value.
 903       // Sink the load to where the compare was, if atomic rules allow us to.
 904       Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", false, 0,
 905                                LI->getOrdering(), LI->getSynchScope(),
 906                                LI->isUnordered() ? (Instruction*)ICI : LI);
 907       InitBoolUsed = true;
 908       switch (ICI->getPredicate()) {
 909       default: llvm_unreachable("Unknown ICmp Predicate!");
 910       case ICmpInst::ICMP_ULT:
 911       case ICmpInst::ICMP_SLT:   // X < null -> always false
 912         LV = ConstantInt::getFalse(GV->getContext());
 913         break;
 914       case ICmpInst::ICMP_ULE:
 915       case ICmpInst::ICMP_SLE:
 916       case ICmpInst::ICMP_EQ:
 917         LV = BinaryOperator::CreateNot(LV, "notinit", ICI);
 918         break;
 919       case ICmpInst::ICMP_NE:
 920       case ICmpInst::ICMP_UGE:
 921       case ICmpInst::ICMP_SGE:
 922       case ICmpInst::ICMP_UGT:
 923       case ICmpInst::ICMP_SGT:
 924         break;  // no change.
 925       }
 926       ICI->replaceAllUsesWith(LV);
 927       ICI->eraseFromParent();
 928     }
 929     LI->eraseFromParent();
 930   }
 931
 932   // If the initialization boolean was used, insert it, otherwise delete it.
 933   if (!InitBoolUsed) {
 934     while (!InitBool->use_empty())  // Delete initializations
 935       cast<StoreInst>(InitBool->user_back())->eraseFromParent();
 936     delete InitBool;
 937   } else
 938     GV->getParent()->getGlobalList().insert(GV->getIterator(), InitBool);
 939
 940   // Now the GV is dead, nuke it and the malloc..
 941   GV->eraseFromParent();
 942   CI->eraseFromParent();
 943
 944   // To further other optimizations, loop over all users of NewGV and try to
 945   // constant prop them.  This will promote GEP instructions with constant
 946   // indices into GEP constant-exprs, which will allow global-opt to hack on it.
 947   ConstantPropUsersOf(NewGV, DL, TLI);
 948   if (RepValue != NewGV)
 949     ConstantPropUsersOf(RepValue, DL, TLI);
 950
 951   return NewGV;
 952 }
 953
 954 /// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking
 955 /// to make sure that there are no complex uses of V.  We permit simple things
 956 /// like dereferencing the pointer, but not storing through the address, unless
 957 /// it is to the specified global.
 958 static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(const Instruction *V,
 959                                                       const GlobalVariable *GV,
 960                                         SmallPtrSetImpl<const PHINode*> &PHIs) {
 961   for (const User *U : V->users()) {
 962     const Instruction *Inst = cast<Instruction>(U);
 963
 964     if (isa<LoadInst>(Inst) || isa<CmpInst>(Inst)) {
 965       continue; // Fine, ignore.
 966     }
 967
 968     if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
 969       if (SI->getOperand(0) == V && SI->getOperand(1) != GV)
 970         return false;  // Storing the pointer itself... bad.
 971       continue; // Otherwise, storing through it, or storing into GV... fine.
 972     }
 973
 974     // Must index into the array and into the struct.
 975     if (isa<GetElementPtrInst>(Inst) && Inst->getNumOperands() >= 3) {
 976       if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Inst, GV, PHIs))
 977         return false;
 978       continue;
 979     }
 980
 981     if (const PHINode *PN = dyn_cast<PHINode>(Inst)) {
 982       // PHIs are ok if all uses are ok.  Don't infinitely recurse through PHI
 983       // cycles.
 984       if (PHIs.insert(PN).second)
 985         if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(PN, GV, PHIs))
 986           return false;
 987       continue;
 988     }
 989
 990     if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Inst)) {
 991       if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(BCI, GV, PHIs))
 992         return false;
 993       continue;
 994     }
 995
 996     return false;
 997   }
 998   return true;
 999 }
1000
1001 /// ReplaceUsesOfMallocWithGlobal - The Alloc pointer is stored into GV
1002 /// somewhere.  Transform all uses of the allocation into loads from the
1003 /// global and uses of the resultant pointer.  Further, delete the store into
1004 /// GV.  This assumes that these value pass the
1005 /// 'ValueIsOnlyUsedLocallyOrStoredToOneGlobal' predicate.
1006 static void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc,
1007                                           GlobalVariable *GV) {
1008   while (!Alloc->use_empty()) {
1009     Instruction *U = cast<Instruction>(*Alloc->user_begin());
1010     Instruction *InsertPt = U;
1011     if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
1012       // If this is the store of the allocation into the global, remove it.
1013       if (SI->getOperand(1) == GV) {
1014         SI->eraseFromParent();
1015         continue;
1016       }
1017     } else if (PHINode *PN = dyn_cast<PHINode>(U)) {
1018       // Insert the load in the corresponding predecessor, not right before the
1019       // PHI.
1020       InsertPt = PN->getIncomingBlock(*Alloc->use_begin())->getTerminator();
1021     } else if (isa<BitCastInst>(U)) {
1022       // Must be bitcast between the malloc and store to initialize the global.
1023       ReplaceUsesOfMallocWithGlobal(U, GV);
1024       U->eraseFromParent();
1025       continue;
1026     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
1027       // If this is a "GEP bitcast" and the user is a store to the global, then
1028       // just process it as a bitcast.
1029       if (GEPI->hasAllZeroIndices() && GEPI->hasOneUse())
1030         if (StoreInst *SI = dyn_cast<StoreInst>(GEPI->user_back()))
1031           if (SI->getOperand(1) == GV) {
1032             // Must be bitcast GEP between the malloc and store to initialize
1033             // the global.
1034             ReplaceUsesOfMallocWithGlobal(GEPI, GV);
1035             GEPI->eraseFromParent();
1036             continue;
1037           }
1038     }
1039
1040     // Insert a load from the global, and use it instead of the malloc.
1041     Value *NL = new LoadInst(GV, GV->getName()+".val", InsertPt);
1042     U->replaceUsesOfWith(Alloc, NL);
1043   }
1044 }
1045
1046 /// LoadUsesSimpleEnoughForHeapSRA - Verify that all uses of V (a load, or a phi
1047 /// of a load) are simple enough to perform heap SRA on.  This permits GEP's
1048 /// that index through the array and struct field, icmps of null, and PHIs.
1049 static bool LoadUsesSimpleEnoughForHeapSRA(const Value *V,
1050                         SmallPtrSetImpl<const PHINode*> &LoadUsingPHIs,
1051                         SmallPtrSetImpl<const PHINode*> &LoadUsingPHIsPerLoad) {
1052   // We permit two users of the load: setcc comparing against the null
1053   // pointer, and a getelementptr of a specific form.
1054   for (const User *U : V->users()) {
1055     const Instruction *UI = cast<Instruction>(U);
1056
1057     // Comparison against null is ok.
1058     if (const ICmpInst *ICI = dyn_cast<ICmpInst>(UI)) {
1059       if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
1060         return false;
1061       continue;
1062     }
1063
1064     // getelementptr is also ok, but only a simple form.
1065     if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(UI)) {
1066       // Must index into the array and into the struct.
1067       if (GEPI->getNumOperands() < 3)
1068         return false;
1069
1070       // Otherwise the GEP is ok.
1071       continue;
1072     }
1073
1074     if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
1075       if (!LoadUsingPHIsPerLoad.insert(PN).second)
1076         // This means some phi nodes are dependent on each other.
1077         // Avoid infinite looping!
1078         return false;
1079       if (!LoadUsingPHIs.insert(PN).second)
1080         // If we have already analyzed this PHI, then it is safe.
1081         continue;
1082
1083       // Make sure all uses of the PHI are simple enough to transform.
1084       if (!LoadUsesSimpleEnoughForHeapSRA(PN,
1085                                           LoadUsingPHIs, LoadUsingPHIsPerLoad))
1086         return false;
1087
1088       continue;
1089     }
1090
1091     // Otherwise we don't know what this is, not ok.
1092     return false;
1093   }
1094
1095   return true;
1096 }
1097
1098
1099 /// AllGlobalLoadUsesSimpleEnoughForHeapSRA - If all users of values loaded from
1100 /// GV are simple enough to perform HeapSRA, return true.
1101 static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(const GlobalVariable *GV,
1102                                                     Instruction *StoredVal) {
1103   SmallPtrSet<const PHINode*, 32> LoadUsingPHIs;
1104   SmallPtrSet<const PHINode*, 32> LoadUsingPHIsPerLoad;
1105   for (const User *U : GV->users())
1106     if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
1107       if (!LoadUsesSimpleEnoughForHeapSRA(LI, LoadUsingPHIs,
1108                                           LoadUsingPHIsPerLoad))
1109         return false;
1110       LoadUsingPHIsPerLoad.clear();
1111     }
1112
1113   // If we reach here, we know that all uses of the loads and transitive uses
1114   // (through PHI nodes) are simple enough to transform.  However, we don't know
1115   // that all inputs the to the PHI nodes are in the same equivalence sets.
1116   // Check to verify that all operands of the PHIs are either PHIS that can be
1117   // transformed, loads from GV, or MI itself.
1118   for (const PHINode *PN : LoadUsingPHIs) {
1119     for (unsigned op = 0, e = PN->getNumIncomingValues(); op != e; ++op) {
1120       Value *InVal = PN->getIncomingValue(op);
1121
1122       // PHI of the stored value itself is ok.
1123       if (InVal == StoredVal) continue;
1124
1125       if (const PHINode *InPN = dyn_cast<PHINode>(InVal)) {
1126         // One of the PHIs in our set is (optimistically) ok.
1127         if (LoadUsingPHIs.count(InPN))
1128           continue;
1129         return false;
1130       }
1131
1132       // Load from GV is ok.
1133       if (const LoadInst *LI = dyn_cast<LoadInst>(InVal))
1134         if (LI->getOperand(0) == GV)
1135           continue;
1136
1137       // UNDEF? NULL?
1138
1139       // Anything else is rejected.
1140       return false;
1141     }
1142   }
1143
1144   return true;
1145 }
1146
1147 static Value *GetHeapSROAValue(Value *V, unsigned FieldNo,
1148                DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues,
1149                    std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) {
1150   std::vector<Value*> &FieldVals = InsertedScalarizedValues[V];
1151
1152   if (FieldNo >= FieldVals.size())
1153     FieldVals.resize(FieldNo+1);
1154
1155   // If we already have this value, just reuse the previously scalarized
1156   // version.
1157   if (Value *FieldVal = FieldVals[FieldNo])
1158     return FieldVal;
1159
1160   // Depending on what instruction this is, we have several cases.
1161   Value *Result;
1162   if (LoadInst *LI = dyn_cast<LoadInst>(V)) {
1163     // This is a scalarized version of the load from the global.  Just create
1164     // a new Load of the scalarized global.
1165     Result = new LoadInst(GetHeapSROAValue(LI->getOperand(0), FieldNo,
1166                                            InsertedScalarizedValues,
1167                                            PHIsToRewrite),
1168                           LI->getName()+".f"+Twine(FieldNo), LI);
1169   } else {
1170     PHINode *PN = cast<PHINode>(V);
1171     // PN's type is pointer to struct.  Make a new PHI of pointer to struct
1172     // field.
1173
1174     PointerType *PTy = cast<PointerType>(PN->getType());
1175     StructType *ST = cast<StructType>(PTy->getElementType());
1176
1177     unsigned AS = PTy->getAddressSpace();
1178     PHINode *NewPN =
1179       PHINode::Create(PointerType::get(ST->getElementType(FieldNo), AS),
1180                      PN->getNumIncomingValues(),
1181                      PN->getName()+".f"+Twine(FieldNo), PN);
1182     Result = NewPN;
1183     PHIsToRewrite.push_back(std::make_pair(PN, FieldNo));
1184   }
1185
1186   return FieldVals[FieldNo] = Result;
1187 }
1188
1189 /// RewriteHeapSROALoadUser - Given a load instruction and a value derived from
1190 /// the load, rewrite the derived value to use the HeapSRoA'd load.
1191 static void RewriteHeapSROALoadUser(Instruction *LoadUser,
1192              DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues,
1193                    std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) {
1194   // If this is a comparison against null, handle it.
1195   if (ICmpInst *SCI = dyn_cast<ICmpInst>(LoadUser)) {
1196     assert(isa<ConstantPointerNull>(SCI->getOperand(1)));
1197     // If we have a setcc of the loaded pointer, we can use a setcc of any
1198     // field.
1199     Value *NPtr = GetHeapSROAValue(SCI->getOperand(0), 0,
1200                                    InsertedScalarizedValues, PHIsToRewrite);
1201
1202     Value *New = new ICmpInst(SCI, SCI->getPredicate(), NPtr,
1203                               Constant::getNullValue(NPtr->getType()),
1204                               SCI->getName());
1205     SCI->replaceAllUsesWith(New);
1206     SCI->eraseFromParent();
1207     return;
1208   }
1209
1210   // Handle 'getelementptr Ptr, Idx, i32 FieldNo ...'
1211   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(LoadUser)) {
1212     assert(GEPI->getNumOperands() >= 3 && isa<ConstantInt>(GEPI->getOperand(2))
1213            && "Unexpected GEPI!");
1214
1215     // Load the pointer for this field.
1216     unsigned FieldNo = cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue();
1217     Value *NewPtr = GetHeapSROAValue(GEPI->getOperand(0), FieldNo,
1218                                      InsertedScalarizedValues, PHIsToRewrite);
1219
1220     // Create the new GEP idx vector.
1221     SmallVector<Value*, 8> GEPIdx;
1222     GEPIdx.push_back(GEPI->getOperand(1));
1223     GEPIdx.append(GEPI->op_begin()+3, GEPI->op_end());
1224
1225     Value *NGEPI = GetElementPtrInst::Create(GEPI->getResultElementType(), NewPtr, GEPIdx,
1226                                              GEPI->getName(), GEPI);
1227     GEPI->replaceAllUsesWith(NGEPI);
1228     GEPI->eraseFromParent();
1229     return;
1230   }
1231
1232   // Recursively transform the users of PHI nodes.  This will lazily create the
1233   // PHIs that are needed for individual elements.  Keep track of what PHIs we
1234   // see in InsertedScalarizedValues so that we don't get infinite loops (very
1235   // antisocial).  If the PHI is already in InsertedScalarizedValues, it has
1236   // already been seen first by another load, so its uses have already been
1237   // processed.
1238   PHINode *PN = cast<PHINode>(LoadUser);
1239   if (!InsertedScalarizedValues.insert(std::make_pair(PN,
1240                                               std::vector<Value*>())).second)
1241     return;
1242
1243   // If this is the first time we've seen this PHI, recursively process all
1244   // users.
1245   for (auto UI = PN->user_begin(), E = PN->user_end(); UI != E;) {
1246     Instruction *User = cast<Instruction>(*UI++);
1247     RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite);
1248   }
1249 }
1250
1251 /// RewriteUsesOfLoadForHeapSRoA - We are performing Heap SRoA on a global.  Ptr
1252 /// is a value loaded from the global.  Eliminate all uses of Ptr, making them
1253 /// use FieldGlobals instead.  All uses of loaded values satisfy
1254 /// AllGlobalLoadUsesSimpleEnoughForHeapSRA.
1255 static void RewriteUsesOfLoadForHeapSRoA(LoadInst *Load,
1256                DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues,
1257                    std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) {
1258   for (auto UI = Load->user_begin(), E = Load->user_end(); UI != E;) {
1259     Instruction *User = cast<Instruction>(*UI++);
1260     RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite);
1261   }
1262
1263   if (Load->use_empty()) {
1264     Load->eraseFromParent();
1265     InsertedScalarizedValues.erase(Load);
1266   }
1267 }
1268
1269 /// PerformHeapAllocSRoA - CI is an allocation of an array of structures.  Break
1270 /// it up into multiple allocations of arrays of the fields.
1271 static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, CallInst *CI,
1272                                             Value *NElems, const DataLayout &DL,
1273                                             const TargetLibraryInfo *TLI) {
1274   DEBUG(dbgs() << "SROA HEAP ALLOC: " << *GV << "  MALLOC = " << *CI << '\n');
1275   Type *MAT = getMallocAllocatedType(CI, TLI);
1276   StructType *STy = cast<StructType>(MAT);
1277
1278   // There is guaranteed to be at least one use of the malloc (storing
1279   // it into GV).  If there are other uses, change them to be uses of
1280   // the global to simplify later code.  This also deletes the store
1281   // into GV.
1282   ReplaceUsesOfMallocWithGlobal(CI, GV);
1283
1284   // Okay, at this point, there are no users of the malloc.  Insert N
1285   // new mallocs at the same place as CI, and N globals.
1286   std::vector<Value*> FieldGlobals;
1287   std::vector<Value*> FieldMallocs;
1288
1289   unsigned AS = GV->getType()->getPointerAddressSpace();
1290   for (unsigned FieldNo = 0, e = STy->getNumElements(); FieldNo != e;++FieldNo){
1291     Type *FieldTy = STy->getElementType(FieldNo);
1292     PointerType *PFieldTy = PointerType::get(FieldTy, AS);
1293
1294     GlobalVariable *NGV =
1295       new GlobalVariable(*GV->getParent(),
1296                          PFieldTy, false, GlobalValue::InternalLinkage,
1297                          Constant::getNullValue(PFieldTy),
1298                          GV->getName() + ".f" + Twine(FieldNo), GV,
1299                          GV->getThreadLocalMode());
1300     FieldGlobals.push_back(NGV);
1301
1302     unsigned TypeSize = DL.getTypeAllocSize(FieldTy);
1303     if (StructType *ST = dyn_cast<StructType>(FieldTy))
1304       TypeSize = DL.getStructLayout(ST)->getSizeInBytes();
1305     Type *IntPtrTy = DL.getIntPtrType(CI->getType());
1306     Value *NMI = CallInst::CreateMalloc(CI, IntPtrTy, FieldTy,
1307                                         ConstantInt::get(IntPtrTy, TypeSize),
1308                                         NElems, nullptr,
1309                                         CI->getName() + ".f" + Twine(FieldNo));
1310     FieldMallocs.push_back(NMI);
1311     new StoreInst(NMI, NGV, CI);
1312   }
1313
1314   // The tricky aspect of this transformation is handling the case when malloc
1315   // fails.  In the original code, malloc failing would set the result pointer
1316   // of malloc to null.  In this case, some mallocs could succeed and others
1317   // could fail.  As such, we emit code that looks like this:
1318   //    F0 = malloc(field0)
1319   //    F1 = malloc(field1)
1320   //    F2 = malloc(field2)
1321   //    if (F0 == 0 || F1 == 0 || F2 == 0) {
1322   //      if (F0) { free(F0); F0 = 0; }
1323   //      if (F1) { free(F1); F1 = 0; }
1324   //      if (F2) { free(F2); F2 = 0; }
1325   //    }
1326   // The malloc can also fail if its argument is too large.
1327   Constant *ConstantZero = ConstantInt::get(CI->getArgOperand(0)->getType(), 0);
1328   Value *RunningOr = new ICmpInst(CI, ICmpInst::ICMP_SLT, CI->getArgOperand(0),
1329                                   ConstantZero, "isneg");
1330   for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) {
1331     Value *Cond = new ICmpInst(CI, ICmpInst::ICMP_EQ, FieldMallocs[i],
1332                              Constant::getNullValue(FieldMallocs[i]->getType()),
1333                                "isnull");
1334     RunningOr = BinaryOperator::CreateOr(RunningOr, Cond, "tmp", CI);
1335   }
1336
1337   // Split the basic block at the old malloc.
1338   BasicBlock *OrigBB = CI->getParent();
1339   BasicBlock *ContBB =
1340       OrigBB->splitBasicBlock(CI->getIterator(), "malloc_cont");
1341
1342   // Create the block to check the first condition.  Put all these blocks at the
1343   // end of the function as they are unlikely to be executed.
1344   BasicBlock *NullPtrBlock = BasicBlock::Create(OrigBB->getContext(),
1345                                                 "malloc_ret_null",
1346                                                 OrigBB->getParent());
1347
1348   // Remove the uncond branch from OrigBB to ContBB, turning it into a cond
1349   // branch on RunningOr.
1350   OrigBB->getTerminator()->eraseFromParent();
1351   BranchInst::Create(NullPtrBlock, ContBB, RunningOr, OrigBB);
1352
1353   // Within the NullPtrBlock, we need to emit a comparison and branch for each
1354   // pointer, because some may be null while others are not.
1355   for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) {
1356     Value *GVVal = new LoadInst(FieldGlobals[i], "tmp", NullPtrBlock);
1357     Value *Cmp = new ICmpInst(*NullPtrBlock, ICmpInst::ICMP_NE, GVVal,
1358                               Constant::getNullValue(GVVal->getType()));
1359     BasicBlock *FreeBlock = BasicBlock::Create(Cmp->getContext(), "free_it",
1360                                                OrigBB->getParent());
1361     BasicBlock *NextBlock = BasicBlock::Create(Cmp->getContext(), "next",
1362                                                OrigBB->getParent());
1363     Instruction *BI = BranchInst::Create(FreeBlock, NextBlock,
1364                                          Cmp, NullPtrBlock);
1365
1366     // Fill in FreeBlock.
1367     CallInst::CreateFree(GVVal, BI);
1368     new StoreInst(Constant::getNullValue(GVVal->getType()), FieldGlobals[i],
1369                   FreeBlock);
1370     BranchInst::Create(NextBlock, FreeBlock);
1371
1372     NullPtrBlock = NextBlock;
1373   }
1374
1375   BranchInst::Create(ContBB, NullPtrBlock);
1376
1377   // CI is no longer needed, remove it.
1378   CI->eraseFromParent();
1379
1380   /// InsertedScalarizedLoads - As we process loads, if we can't immediately
1381   /// update all uses of the load, keep track of what scalarized loads are
1382   /// inserted for a given load.
1383   DenseMap<Value*, std::vector<Value*> > InsertedScalarizedValues;
1384   InsertedScalarizedValues[GV] = FieldGlobals;
1385
1386   std::vector<std::pair<PHINode*, unsigned> > PHIsToRewrite;
1387
1388   // Okay, the malloc site is completely handled.  All of the uses of GV are now
1389   // loads, and all uses of those loads are simple.  Rewrite them to use loads
1390   // of the per-field globals instead.
1391   for (auto UI = GV->user_begin(), E = GV->user_end(); UI != E;) {
1392     Instruction *User = cast<Instruction>(*UI++);
1393
1394     if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
1395       RewriteUsesOfLoadForHeapSRoA(LI, InsertedScalarizedValues, PHIsToRewrite);
1396       continue;
1397     }
1398
1399     // Must be a store of null.
1400     StoreInst *SI = cast<StoreInst>(User);
1401     assert(isa<ConstantPointerNull>(SI->getOperand(0)) &&
1402            "Unexpected heap-sra user!");
1403
1404     // Insert a store of null into each global.
1405     for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) {
1406       PointerType *PT = cast<PointerType>(FieldGlobals[i]->getType());
1407       Constant *Null = Constant::getNullValue(PT->getElementType());
1408       new StoreInst(Null, FieldGlobals[i], SI);
1409     }
1410     // Erase the original store.
1411     SI->eraseFromParent();
1412   }
1413
1414   // While we have PHIs that are interesting to rewrite, do it.
1415   while (!PHIsToRewrite.empty()) {
1416     PHINode *PN = PHIsToRewrite.back().first;
1417     unsigned FieldNo = PHIsToRewrite.back().second;
1418     PHIsToRewrite.pop_back();
1419     PHINode *FieldPN = cast<PHINode>(InsertedScalarizedValues[PN][FieldNo]);
1420     assert(FieldPN->getNumIncomingValues() == 0 &&"Already processed this phi");
1421
1422     // Add all the incoming values.  This can materialize more phis.
1423     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
1424       Value *InVal = PN->getIncomingValue(i);
1425       InVal = GetHeapSROAValue(InVal, FieldNo, InsertedScalarizedValues,
1426                                PHIsToRewrite);
1427       FieldPN->addIncoming(InVal, PN->getIncomingBlock(i));
1428     }
1429   }
1430
1431   // Drop all inter-phi links and any loads that made it this far.
1432   for (DenseMap<Value*, std::vector<Value*> >::iterator
1433        I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end();
1434        I != E; ++I) {
1435     if (PHINode *PN = dyn_cast<PHINode>(I->first))
1436       PN->dropAllReferences();
1437     else if (LoadInst *LI = dyn_cast<LoadInst>(I->first))
1438       LI->dropAllReferences();
1439   }
1440
1441   // Delete all the phis and loads now that inter-references are dead.
1442   for (DenseMap<Value*, std::vector<Value*> >::iterator
1443        I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end();
1444        I != E; ++I) {
1445     if (PHINode *PN = dyn_cast<PHINode>(I->first))
1446       PN->eraseFromParent();
1447     else if (LoadInst *LI = dyn_cast<LoadInst>(I->first))
1448       LI->eraseFromParent();
1449   }
1450
1451   // The old global is now dead, remove it.
1452   GV->eraseFromParent();
1453
1454   ++NumHeapSRA;
1455   return cast<GlobalVariable>(FieldGlobals[0]);
1456 }
1457
1458 /// TryToOptimizeStoreOfMallocToGlobal - This function is called when we see a
1459 /// pointer global variable with a single value stored it that is a malloc or
1460 /// cast of malloc.
1461 static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV, CallInst *CI,
1462                                                Type *AllocTy,
1463                                                AtomicOrdering Ordering,
1464                                                Module::global_iterator &GVI,
1465                                                const DataLayout &DL,
1466                                                TargetLibraryInfo *TLI) {
1467   // If this is a malloc of an abstract type, don't touch it.
1468   if (!AllocTy->isSized())
1469     return false;
1470
1471   // We can't optimize this global unless all uses of it are *known* to be
1472   // of the malloc value, not of the null initializer value (consider a use
1473   // that compares the global's value against zero to see if the malloc has
1474   // been reached).  To do this, we check to see if all uses of the global
1475   // would trap if the global were null: this proves that they must all
1476   // happen after the malloc.
1477   if (!AllUsesOfLoadedValueWillTrapIfNull(GV))
1478     return false;
1479
1480   // We can't optimize this if the malloc itself is used in a complex way,
1481   // for example, being stored into multiple globals.  This allows the
1482   // malloc to be stored into the specified global, loaded icmp'd, and
1483   // GEP'd.  These are all things we could transform to using the global
1484   // for.
1485   SmallPtrSet<const PHINode*, 8> PHIs;
1486   if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(CI, GV, PHIs))
1487     return false;
1488
1489   // If we have a global that is only initialized with a fixed size malloc,
1490   // transform the program to use global memory instead of malloc'd memory.
1491   // This eliminates dynamic allocation, avoids an indirection accessing the
1492   // data, and exposes the resultant global to further GlobalOpt.
1493   // We cannot optimize the malloc if we cannot determine malloc array size.
1494   Value *NElems = getMallocArraySize(CI, DL, TLI, true);
1495   if (!NElems)
1496     return false;
1497
1498   if (ConstantInt *NElements = dyn_cast<ConstantInt>(NElems))
1499     // Restrict this transformation to only working on small allocations
1500     // (2048 bytes currently), as we don't want to introduce a 16M global or
1501     // something.
1502     if (NElements->getZExtValue() * DL.getTypeAllocSize(AllocTy) < 2048) {
1503       GVI = OptimizeGlobalAddressOfMalloc(GV, CI, AllocTy, NElements, DL, TLI)
1504                 ->getIterator();
1505       return true;
1506     }
1507
1508   // If the allocation is an array of structures, consider transforming this
1509   // into multiple malloc'd arrays, one for each field.  This is basically
1510   // SRoA for malloc'd memory.
1511
1512   if (Ordering != NotAtomic)
1513     return false;
1514
1515   // If this is an allocation of a fixed size array of structs, analyze as a
1516   // variable size array.  malloc [100 x struct],1 -> malloc struct, 100
1517   if (NElems == ConstantInt::get(CI->getArgOperand(0)->getType(), 1))
1518     if (ArrayType *AT = dyn_cast<ArrayType>(AllocTy))
1519       AllocTy = AT->getElementType();
1520
1521   StructType *AllocSTy = dyn_cast<StructType>(AllocTy);
1522   if (!AllocSTy)
1523     return false;
1524
1525   // This the structure has an unreasonable number of fields, leave it
1526   // alone.
1527   if (AllocSTy->getNumElements() <= 16 && AllocSTy->getNumElements() != 0 &&
1528       AllGlobalLoadUsesSimpleEnoughForHeapSRA(GV, CI)) {
1529
1530     // If this is a fixed size array, transform the Malloc to be an alloc of
1531     // structs.  malloc [100 x struct],1 -> malloc struct, 100
1532     if (ArrayType *AT = dyn_cast<ArrayType>(getMallocAllocatedType(CI, TLI))) {
1533       Type *IntPtrTy = DL.getIntPtrType(CI->getType());
1534       unsigned TypeSize = DL.getStructLayout(AllocSTy)->getSizeInBytes();
1535       Value *AllocSize = ConstantInt::get(IntPtrTy, TypeSize);
1536       Value *NumElements = ConstantInt::get(IntPtrTy, AT->getNumElements());
1537       Instruction *Malloc = CallInst::CreateMalloc(CI, IntPtrTy, AllocSTy,
1538                                                    AllocSize, NumElements,
1539                                                    nullptr, CI->getName());
1540       Instruction *Cast = new BitCastInst(Malloc, CI->getType(), "tmp", CI);
1541       CI->replaceAllUsesWith(Cast);
1542       CI->eraseFromParent();
1543       if (BitCastInst *BCI = dyn_cast<BitCastInst>(Malloc))
1544         CI = cast<CallInst>(BCI->getOperand(0));
1545       else
1546         CI = cast<CallInst>(Malloc);
1547     }
1548
1549     GVI = PerformHeapAllocSRoA(GV, CI, getMallocArraySize(CI, DL, TLI, true),
1550                                DL, TLI)
1551               ->getIterator();
1552     return true;
1553   }
1554
1555   return false;
1556 }
1557
1558 // OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge
1559 // that only one value (besides its initializer) is ever stored to the global.
1560 static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal,
1561                                      AtomicOrdering Ordering,
1562                                      Module::global_iterator &GVI,
1563                                      const DataLayout &DL,
1564                                      TargetLibraryInfo *TLI) {
1565   // Ignore no-op GEPs and bitcasts.
1566   StoredOnceVal = StoredOnceVal->stripPointerCasts();
1567
1568   // If we are dealing with a pointer global that is initialized to null and
1569   // only has one (non-null) value stored into it, then we can optimize any
1570   // users of the loaded value (often calls and loads) that would trap if the
1571   // value was null.
1572   if (GV->getInitializer()->getType()->isPointerTy() &&
1573       GV->getInitializer()->isNullValue()) {
1574     if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
1575       if (GV->getInitializer()->getType() != SOVC->getType())
1576         SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
1577
1578       // Optimize away any trapping uses of the loaded value.
1579       if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, DL, TLI))
1580         return true;
1581     } else if (CallInst *CI = extractMallocCall(StoredOnceVal, TLI)) {
1582       Type *MallocType = getMallocAllocatedType(CI, TLI);
1583       if (MallocType &&
1584           TryToOptimizeStoreOfMallocToGlobal(GV, CI, MallocType, Ordering, GVI,
1585                                              DL, TLI))
1586         return true;
1587     }
1588   }
1589
1590   return false;
1591 }
1592
1593 /// TryToShrinkGlobalToBoolean - At this point, we have learned that the only
1594 /// two values ever stored into GV are its initializer and OtherVal.  See if we
1595 /// can shrink the global into a boolean and select between the two values
1596 /// whenever it is used.  This exposes the values to other scalar optimizations.
1597 static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) {
1598   Type *GVElType = GV->getType()->getElementType();
1599
1600   // If GVElType is already i1, it is already shrunk.  If the type of the GV is
1601   // an FP value, pointer or vector, don't do this optimization because a select
1602   // between them is very expensive and unlikely to lead to later
1603   // simplification.  In these cases, we typically end up with "cond ? v1 : v2"
1604   // where v1 and v2 both require constant pool loads, a big loss.
1605   if (GVElType == Type::getInt1Ty(GV->getContext()) ||
1606       GVElType->isFloatingPointTy() ||
1607       GVElType->isPointerTy() || GVElType->isVectorTy())
1608     return false;
1609
1610   // Walk the use list of the global seeing if all the uses are load or store.
1611   // If there is anything else, bail out.
1612   for (User *U : GV->users())
1613     if (!isa<LoadInst>(U) && !isa<StoreInst>(U))
1614       return false;
1615
1616   DEBUG(dbgs() << "   *** SHRINKING TO BOOL: " << *GV << "\n");
1617
1618   // Create the new global, initializing it to false.
1619   GlobalVariable *NewGV = new GlobalVariable(Type::getInt1Ty(GV->getContext()),
1620                                              false,
1621                                              GlobalValue::InternalLinkage,
1622                                         ConstantInt::getFalse(GV->getContext()),
1623                                              GV->getName()+".b",
1624                                              GV->getThreadLocalMode(),
1625                                              GV->getType()->getAddressSpace());
1626   GV->getParent()->getGlobalList().insert(GV->getIterator(), NewGV);
1627
1628   Constant *InitVal = GV->getInitializer();
1629   assert(InitVal->getType() != Type::getInt1Ty(GV->getContext()) &&
1630          "No reason to shrink to bool!");
1631
1632   // If initialized to zero and storing one into the global, we can use a cast
1633   // instead of a select to synthesize the desired value.
1634   bool IsOneZero = false;
1635   if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal))
1636     IsOneZero = InitVal->isNullValue() && CI->isOne();
1637
1638   while (!GV->use_empty()) {
1639     Instruction *UI = cast<Instruction>(GV->user_back());
1640     if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
1641       // Change the store into a boolean store.
1642       bool StoringOther = SI->getOperand(0) == OtherVal;
1643       // Only do this if we weren't storing a loaded value.
1644       Value *StoreVal;
1645       if (StoringOther || SI->getOperand(0) == InitVal) {
1646         StoreVal = ConstantInt::get(Type::getInt1Ty(GV->getContext()),
1647                                     StoringOther);
1648       } else {
1649         // Otherwise, we are storing a previously loaded copy.  To do this,
1650         // change the copy from copying the original value to just copying the
1651         // bool.
1652         Instruction *StoredVal = cast<Instruction>(SI->getOperand(0));
1653
1654         // If we've already replaced the input, StoredVal will be a cast or
1655         // select instruction.  If not, it will be a load of the original
1656         // global.
1657         if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
1658           assert(LI->getOperand(0) == GV && "Not a copy!");
1659           // Insert a new load, to preserve the saved value.
1660           StoreVal = new LoadInst(NewGV, LI->getName()+".b", false, 0,
1661                                   LI->getOrdering(), LI->getSynchScope(), LI);
1662         } else {
1663           assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) &&
1664                  "This is not a form that we understand!");
1665           StoreVal = StoredVal->getOperand(0);
1666           assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!");
1667         }
1668       }
1669       new StoreInst(StoreVal, NewGV, false, 0,
1670                     SI->getOrdering(), SI->getSynchScope(), SI);
1671     } else {
1672       // Change the load into a load of bool then a select.
1673       LoadInst *LI = cast<LoadInst>(UI);
1674       LoadInst *NLI = new LoadInst(NewGV, LI->getName()+".b", false, 0,
1675                                    LI->getOrdering(), LI->getSynchScope(), LI);
1676       Value *NSI;
1677       if (IsOneZero)
1678         NSI = new ZExtInst(NLI, LI->getType(), "", LI);
1679       else
1680         NSI = SelectInst::Create(NLI, OtherVal, InitVal, "", LI);
1681       NSI->takeName(LI);
1682       LI->replaceAllUsesWith(NSI);
1683     }
1684     UI->eraseFromParent();
1685   }
1686
1687   // Retain the name of the old global variable. People who are debugging their
1688   // programs may expect these variables to be named the same.
1689   NewGV->takeName(GV);
1690   GV->eraseFromParent();
1691   return true;
1692 }
1693
1694
1695 /// ProcessGlobal - Analyze the specified global variable and optimize it if
1696 /// possible.  If we make a change, return true.
1697 bool GlobalOpt::ProcessGlobal(GlobalVariable *GV,
1698                               Module::global_iterator &GVI) {
1699   // Do more involved optimizations if the global is internal.
1700   GV->removeDeadConstantUsers();
1701
1702   if (GV->use_empty()) {
1703     DEBUG(dbgs() << "GLOBAL DEAD: " << *GV << "\n");
1704     GV->eraseFromParent();
1705     ++NumDeleted;
1706     return true;
1707   }
1708
1709   if (!GV->hasLocalLinkage())
1710     return false;
1711
1712   GlobalStatus GS;
1713
1714   if (GlobalStatus::analyzeGlobal(GV, GS))
1715     return false;
1716
1717   if (!GS.IsCompared && !GV->hasUnnamedAddr()) {
1718     GV->setUnnamedAddr(true);
1719     NumUnnamed++;
1720   }
1721
1722   if (GV->isConstant() || !GV->hasInitializer())
1723     return false;
1724
1725   return ProcessInternalGlobal(GV, GVI, GS);
1726 }
1727
1728 /// ProcessInternalGlobal - Analyze the specified global variable and optimize
1729 /// it if possible.  If we make a change, return true.
1730 bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV,
1731                                       Module::global_iterator &GVI,
1732                                       const GlobalStatus &GS) {
1733   auto &DL = GV->getParent()->getDataLayout();
1734   // If this is a first class global and has only one accessing function
1735   // and this function is main (which we know is not recursive), we replace
1736   // the global with a local alloca in this function.
1737   //
1738   // NOTE: It doesn't make sense to promote non-single-value types since we
1739   // are just replacing static memory to stack memory.
1740   //
1741   // If the global is in different address space, don't bring it to stack.
1742   if (!GS.HasMultipleAccessingFunctions &&
1743       GS.AccessingFunction && !GS.HasNonInstructionUser &&
1744       GV->getType()->getElementType()->isSingleValueType() &&
1745       GS.AccessingFunction->getName() == "main" &&
1746       GS.AccessingFunction->hasExternalLinkage() &&
1747       GV->getType()->getAddressSpace() == 0) {
1748     DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV);
1749     Instruction &FirstI = const_cast<Instruction&>(*GS.AccessingFunction
1750                                                    ->getEntryBlock().begin());
1751     Type *ElemTy = GV->getType()->getElementType();
1752     // FIXME: Pass Global's alignment when globals have alignment
1753     AllocaInst *Alloca = new AllocaInst(ElemTy, nullptr,
1754                                         GV->getName(), &FirstI);
1755     if (!isa<UndefValue>(GV->getInitializer()))
1756       new StoreInst(GV->getInitializer(), Alloca, &FirstI);
1757
1758     GV->replaceAllUsesWith(Alloca);
1759     GV->eraseFromParent();
1760     ++NumLocalized;
1761     return true;
1762   }
1763
1764   // If the global is never loaded (but may be stored to), it is dead.
1765   // Delete it now.
1766   if (!GS.IsLoaded) {
1767     DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV);
1768
1769     bool Changed;
1770     if (isLeakCheckerRoot(GV)) {
1771       // Delete any constant stores to the global.
1772       Changed = CleanupPointerRootUsers(GV, TLI);
1773     } else {
1774       // Delete any stores we can find to the global.  We may not be able to
1775       // make it completely dead though.
1776       Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
1777     }
1778
1779     // If the global is dead now, delete it.
1780     if (GV->use_empty()) {
1781       GV->eraseFromParent();
1782       ++NumDeleted;
1783       Changed = true;
1784     }
1785     return Changed;
1786
1787   } else if (GS.StoredType <= GlobalStatus::InitializerStored) {
1788     DEBUG(dbgs() << "MARKING CONSTANT: " << *GV << "\n");
1789     GV->setConstant(true);
1790
1791     // Clean up any obviously simplifiable users now.
1792     CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
1793
1794     // If the global is dead now, just nuke it.
1795     if (GV->use_empty()) {
1796       DEBUG(dbgs() << "   *** Marking constant allowed us to simplify "
1797             << "all users and delete global!\n");
1798       GV->eraseFromParent();
1799       ++NumDeleted;
1800     }
1801
1802     ++NumMarked;
1803     return true;
1804   } else if (!GV->getInitializer()->getType()->isSingleValueType()) {
1805     const DataLayout &DL = GV->getParent()->getDataLayout();
1806     if (GlobalVariable *FirstNewGV = SRAGlobal(GV, DL)) {
1807       GVI = FirstNewGV->getIterator(); // Don't skip the newly produced globals!
1808       return true;
1809     }
1810   } else if (GS.StoredType == GlobalStatus::StoredOnce && GS.StoredOnceValue) {
1811     // If the initial value for the global was an undef value, and if only
1812     // one other value was stored into it, we can just change the
1813     // initializer to be the stored value, then delete all stores to the
1814     // global.  This allows us to mark it constant.
1815     if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue))
1816       if (isa<UndefValue>(GV->getInitializer())) {
1817         // Change the initial value here.
1818         GV->setInitializer(SOVConstant);
1819
1820         // Clean up any obviously simplifiable users now.
1821         CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
1822
1823         if (GV->use_empty()) {
1824           DEBUG(dbgs() << "   *** Substituting initializer allowed us to "
1825                        << "simplify all users and delete global!\n");
1826           GV->eraseFromParent();
1827           ++NumDeleted;
1828         } else {
1829           GVI = GV->getIterator();
1830         }
1831         ++NumSubstitute;
1832         return true;
1833       }
1834
1835     // Try to optimize globals based on the knowledge that only one value
1836     // (besides its initializer) is ever stored to the global.
1837     if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, GVI,
1838                                  DL, TLI))
1839       return true;
1840
1841     // Otherwise, if the global was not a boolean, we can shrink it to be a
1842     // boolean.
1843     if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) {
1844       if (GS.Ordering == NotAtomic) {
1845         if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) {
1846           ++NumShrunkToBool;
1847           return true;
1848         }
1849       }
1850     }
1851   }
1852
1853   return false;
1854 }
1855
1856 /// ChangeCalleesToFastCall - Walk all of the direct calls of the specified
1857 /// function, changing them to FastCC.
1858 static void ChangeCalleesToFastCall(Function *F) {
1859   for (User *U : F->users()) {
1860     if (isa<BlockAddress>(U))
1861       continue;
1862     CallSite CS(cast<Instruction>(U));
1863     CS.setCallingConv(CallingConv::Fast);
1864   }
1865 }
1866
1867 static AttributeSet StripNest(LLVMContext &C, const AttributeSet &Attrs) {
1868   for (unsigned i = 0, e = Attrs.getNumSlots(); i != e; ++i) {
1869     unsigned Index = Attrs.getSlotIndex(i);
1870     if (!Attrs.getSlotAttributes(i).hasAttribute(Index, Attribute::Nest))
1871       continue;
1872
1873     // There can be only one.
1874     return Attrs.removeAttribute(C, Index, Attribute::Nest);
1875   }
1876
1877   return Attrs;
1878 }
1879
1880 static void RemoveNestAttribute(Function *F) {
1881   F->setAttributes(StripNest(F->getContext(), F->getAttributes()));
1882   for (User *U : F->users()) {
1883     if (isa<BlockAddress>(U))
1884       continue;
1885     CallSite CS(cast<Instruction>(U));
1886     CS.setAttributes(StripNest(F->getContext(), CS.getAttributes()));
1887   }
1888 }
1889
1890 /// Return true if this is a calling convention that we'd like to change.  The
1891 /// idea here is that we don't want to mess with the convention if the user
1892 /// explicitly requested something with performance implications like coldcc,
1893 /// GHC, or anyregcc.
1894 static bool isProfitableToMakeFastCC(Function *F) {
1895   CallingConv::ID CC = F->getCallingConv();
1896   // FIXME: Is it worth transforming x86_stdcallcc and x86_fastcallcc?
1897   return CC == CallingConv::C || CC == CallingConv::X86_ThisCall;
1898 }
1899
1900 bool GlobalOpt::OptimizeFunctions(Module &M) {
1901   bool Changed = false;
1902   // Optimize functions.
1903   for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
1904     Function *F = &*FI++;
1905     // Functions without names cannot be referenced outside this module.
1906     if (!F->hasName() && !F->isDeclaration() && !F->hasLocalLinkage())
1907       F->setLinkage(GlobalValue::InternalLinkage);
1908
1909     const Comdat *C = F->getComdat();
1910     bool inComdat = C && NotDiscardableComdats.count(C);
1911     F->removeDeadConstantUsers();
1912     if ((!inComdat || F->hasLocalLinkage()) && F->isDefTriviallyDead()) {
1913       F->eraseFromParent();
1914       Changed = true;
1915       ++NumFnDeleted;
1916     } else if (F->hasLocalLinkage()) {
1917       if (isProfitableToMakeFastCC(F) && !F->isVarArg() &&
1918           !F->hasAddressTaken()) {
1919         // If this function has a calling convention worth changing, is not a
1920         // varargs function, and is only called directly, promote it to use the
1921         // Fast calling convention.
1922         F->setCallingConv(CallingConv::Fast);
1923         ChangeCalleesToFastCall(F);
1924         ++NumFastCallFns;
1925         Changed = true;
1926       }
1927
1928       if (F->getAttributes().hasAttrSomewhere(Attribute::Nest) &&
1929           !F->hasAddressTaken()) {
1930         // The function is not used by a trampoline intrinsic, so it is safe
1931         // to remove the 'nest' attribute.
1932         RemoveNestAttribute(F);
1933         ++NumNestRemoved;
1934         Changed = true;
1935       }
1936     }
1937   }
1938   return Changed;
1939 }
1940
1941 bool GlobalOpt::OptimizeGlobalVars(Module &M) {
1942   bool Changed = false;
1943
1944   for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
1945        GVI != E; ) {
1946     GlobalVariable *GV = &*GVI++;
1947     // Global variables without names cannot be referenced outside this module.
1948     if (!GV->hasName() && !GV->isDeclaration() && !GV->hasLocalLinkage())
1949       GV->setLinkage(GlobalValue::InternalLinkage);
1950     // Simplify the initializer.
1951     if (GV->hasInitializer())
1952       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GV->getInitializer())) {
1953         auto &DL = M.getDataLayout();
1954         Constant *New = ConstantFoldConstantExpression(CE, DL, TLI);
1955         if (New && New != CE)
1956           GV->setInitializer(New);
1957       }
1958
1959     if (GV->isDiscardableIfUnused()) {
1960       if (const Comdat *C = GV->getComdat())
1961         if (NotDiscardableComdats.count(C) && !GV->hasLocalLinkage())
1962           continue;
1963       Changed |= ProcessGlobal(GV, GVI);
1964     }
1965   }
1966   return Changed;
1967 }
1968
1969 static inline bool
1970 isSimpleEnoughValueToCommit(Constant *C,
1971                             SmallPtrSetImpl<Constant *> &SimpleConstants,
1972                             const DataLayout &DL);
1973
1974 /// isSimpleEnoughValueToCommit - Return true if the specified constant can be
1975 /// handled by the code generator.  We don't want to generate something like:
1976 ///   void *X = &X/42;
1977 /// because the code generator doesn't have a relocation that can handle that.
1978 ///
1979 /// This function should be called if C was not found (but just got inserted)
1980 /// in SimpleConstants to avoid having to rescan the same constants all the
1981 /// time.
1982 static bool
1983 isSimpleEnoughValueToCommitHelper(Constant *C,
1984                                   SmallPtrSetImpl<Constant *> &SimpleConstants,
1985                                   const DataLayout &DL) {
1986   // Simple global addresses are supported, do not allow dllimport or
1987   // thread-local globals.
1988   if (auto *GV = dyn_cast<GlobalValue>(C))
1989     return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal();
1990
1991   // Simple integer, undef, constant aggregate zero, etc are all supported.
1992   if (C->getNumOperands() == 0 || isa<BlockAddress>(C))
1993     return true;
1994
1995   // Aggregate values are safe if all their elements are.
1996   if (isa<ConstantArray>(C) || isa<ConstantStruct>(C) ||
1997       isa<ConstantVector>(C)) {
1998     for (Value *Op : C->operands())
1999       if (!isSimpleEnoughValueToCommit(cast<Constant>(Op), SimpleConstants, DL))
2000         return false;
2001     return true;
2002   }
2003
2004   // We don't know exactly what relocations are allowed in constant expressions,
2005   // so we allow &global+constantoffset, which is safe and uniformly supported
2006   // across targets.
2007   ConstantExpr *CE = cast<ConstantExpr>(C);
2008   switch (CE->getOpcode()) {
2009   case Instruction::BitCast:
2010     // Bitcast is fine if the casted value is fine.
2011     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
2012
2013   case Instruction::IntToPtr:
2014   case Instruction::PtrToInt:
2015     // int <=> ptr is fine if the int type is the same size as the
2016     // pointer type.
2017     if (DL.getTypeSizeInBits(CE->getType()) !=
2018         DL.getTypeSizeInBits(CE->getOperand(0)->getType()))
2019       return false;
2020     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
2021
2022   // GEP is fine if it is simple + constant offset.
2023   case Instruction::GetElementPtr:
2024     for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
2025       if (!isa<ConstantInt>(CE->getOperand(i)))
2026         return false;
2027     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
2028
2029   case Instruction::Add:
2030     // We allow simple+cst.
2031     if (!isa<ConstantInt>(CE->getOperand(1)))
2032       return false;
2033     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
2034   }
2035   return false;
2036 }
2037
2038 static inline bool
2039 isSimpleEnoughValueToCommit(Constant *C,
2040                             SmallPtrSetImpl<Constant *> &SimpleConstants,
2041                             const DataLayout &DL) {
2042   // If we already checked this constant, we win.
2043   if (!SimpleConstants.insert(C).second)
2044     return true;
2045   // Check the constant.
2046   return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);
2047 }
2048
2049
2050 /// isSimpleEnoughPointerToCommit - Return true if this constant is simple
2051 /// enough for us to understand.  In particular, if it is a cast to anything
2052 /// other than from one pointer type to another pointer type, we punt.
2053 /// We basically just support direct accesses to globals and GEP's of
2054 /// globals.  This should be kept up to date with CommitValueTo.
2055 static bool isSimpleEnoughPointerToCommit(Constant *C) {
2056   // Conservatively, avoid aggregate types. This is because we don't
2057   // want to worry about them partially overlapping other stores.
2058   if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType())
2059     return false;
2060
2061   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
2062     // Do not allow weak/*_odr/linkonce linkage or external globals.
2063     return GV->hasUniqueInitializer();
2064
2065   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
2066     // Handle a constantexpr gep.
2067     if (CE->getOpcode() == Instruction::GetElementPtr &&
2068         isa<GlobalVariable>(CE->getOperand(0)) &&
2069         cast<GEPOperator>(CE)->isInBounds()) {
2070       GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
2071       // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
2072       // external globals.
2073       if (!GV->hasUniqueInitializer())
2074         return false;
2075
2076       // The first index must be zero.
2077       ConstantInt *CI = dyn_cast<ConstantInt>(*std::next(CE->op_begin()));
2078       if (!CI || !CI->isZero()) return false;
2079
2080       // The remaining indices must be compile-time known integers within the
2081       // notional bounds of the corresponding static array types.
2082       if (!CE->isGEPWithNoNotionalOverIndexing())
2083         return false;
2084
2085       return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
2086
2087     // A constantexpr bitcast from a pointer to another pointer is a no-op,
2088     // and we know how to evaluate it by moving the bitcast from the pointer
2089     // operand to the value operand.
2090     } else if (CE->getOpcode() == Instruction::BitCast &&
2091                isa<GlobalVariable>(CE->getOperand(0))) {
2092       // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
2093       // external globals.
2094       return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer();
2095     }
2096   }
2097
2098   return false;
2099 }
2100
2101 /// EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global
2102 /// initializer.  This returns 'Init' modified to reflect 'Val' stored into it.
2103 /// At this point, the GEP operands of Addr [0, OpNo) have been stepped into.
2104 static Constant *EvaluateStoreInto(Constant *Init, Constant *Val,
2105                                    ConstantExpr *Addr, unsigned OpNo) {
2106   // Base case of the recursion.
2107   if (OpNo == Addr->getNumOperands()) {
2108     assert(Val->getType() == Init->getType() && "Type mismatch!");
2109     return Val;
2110   }
2111
2112   SmallVector<Constant*, 32> Elts;
2113   if (StructType *STy = dyn_cast<StructType>(Init->getType())) {
2114     // Break up the constant into its elements.
2115     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
2116       Elts.push_back(Init->getAggregateElement(i));
2117
2118     // Replace the element that we are supposed to.
2119     ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo));
2120     unsigned Idx = CU->getZExtValue();
2121     assert(Idx < STy->getNumElements() && "Struct index out of range!");
2122     Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1);
2123
2124     // Return the modified struct.
2125     return ConstantStruct::get(STy, Elts);
2126   }
2127
2128   ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo));
2129   SequentialType *InitTy = cast<SequentialType>(Init->getType());
2130
2131   uint64_t NumElts;
2132   if (ArrayType *ATy = dyn_cast<ArrayType>(InitTy))
2133     NumElts = ATy->getNumElements();
2134   else
2135     NumElts = InitTy->getVectorNumElements();
2136
2137   // Break up the array into elements.
2138   for (uint64_t i = 0, e = NumElts; i != e; ++i)
2139     Elts.push_back(Init->getAggregateElement(i));
2140
2141   assert(CI->getZExtValue() < NumElts);
2142   Elts[CI->getZExtValue()] =
2143     EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1);
2144
2145   if (Init->getType()->isArrayTy())
2146     return ConstantArray::get(cast<ArrayType>(InitTy), Elts);
2147   return ConstantVector::get(Elts);
2148 }
2149
2150 /// CommitValueTo - We have decided that Addr (which satisfies the predicate
2151 /// isSimpleEnoughPointerToCommit) should get Val as its value.  Make it happen.
2152 static void CommitValueTo(Constant *Val, Constant *Addr) {
2153   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
2154     assert(GV->hasInitializer());
2155     GV->setInitializer(Val);
2156     return;
2157   }
2158
2159   ConstantExpr *CE = cast<ConstantExpr>(Addr);
2160   GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
2161   GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2));
2162 }
2163
2164 namespace {
2165
2166 /// Evaluator - This class evaluates LLVM IR, producing the Constant
2167 /// representing each SSA instruction.  Changes to global variables are stored
2168 /// in a mapping that can be iterated over after the evaluation is complete.
2169 /// Once an evaluation call fails, the evaluation object should not be reused.
2170 class Evaluator {
2171 public:
2172   Evaluator(const DataLayout &DL, const TargetLibraryInfo *TLI)
2173       : DL(DL), TLI(TLI) {
2174     ValueStack.emplace_back();
2175   }
2176
2177   ~Evaluator() {
2178     for (auto &Tmp : AllocaTmps)
2179       // If there are still users of the alloca, the program is doing something
2180       // silly, e.g. storing the address of the alloca somewhere and using it
2181       // later.  Since this is undefined, we'll just make it be null.
2182       if (!Tmp->use_empty())
2183         Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
2184   }
2185
2186   /// EvaluateFunction - Evaluate a call to function F, returning true if
2187   /// successful, false if we can't evaluate it.  ActualArgs contains the formal
2188   /// arguments for the function.
2189   bool EvaluateFunction(Function *F, Constant *&RetVal,
2190                         const SmallVectorImpl<Constant*> &ActualArgs);
2191
2192   /// EvaluateBlock - Evaluate all instructions in block BB, returning true if
2193   /// successful, false if we can't evaluate it.  NewBB returns the next BB that
2194   /// control flows into, or null upon return.
2195   bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB);
2196
2197   Constant *getVal(Value *V) {
2198     if (Constant *CV = dyn_cast<Constant>(V)) return CV;
2199     Constant *R = ValueStack.back().lookup(V);
2200     assert(R && "Reference to an uncomputed value!");
2201     return R;
2202   }
2203
2204   void setVal(Value *V, Constant *C) {
2205     ValueStack.back()[V] = C;
2206   }
2207
2208   const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
2209     return MutatedMemory;
2210   }
2211
2212   const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const {
2213     return Invariants;
2214   }
2215
2216 private:
2217   Constant *ComputeLoadResult(Constant *P);
2218
2219   /// ValueStack - As we compute SSA register values, we store their contents
2220   /// here. The back of the deque contains the current function and the stack
2221   /// contains the values in the calling frames.
2222   std::deque<DenseMap<Value*, Constant*>> ValueStack;
2223
2224   /// CallStack - This is used to detect recursion.  In pathological situations
2225   /// we could hit exponential behavior, but at least there is nothing
2226   /// unbounded.
2227   SmallVector<Function*, 4> CallStack;
2228
2229   /// MutatedMemory - For each store we execute, we update this map.  Loads
2230   /// check this to get the most up-to-date value.  If evaluation is successful,
2231   /// this state is committed to the process.
2232   DenseMap<Constant*, Constant*> MutatedMemory;
2233
2234   /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable
2235   /// to represent its body.  This vector is needed so we can delete the
2236   /// temporary globals when we are done.
2237   SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
2238
2239   /// Invariants - These global variables have been marked invariant by the
2240   /// static constructor.
2241   SmallPtrSet<GlobalVariable*, 8> Invariants;
2242
2243   /// SimpleConstants - These are constants we have checked and know to be
2244   /// simple enough to live in a static initializer of a global.
2245   SmallPtrSet<Constant*, 8> SimpleConstants;
2246
2247   const DataLayout &DL;
2248   const TargetLibraryInfo *TLI;
2249 };
2250
2251 }  // anonymous namespace
2252
2253 /// ComputeLoadResult - Return the value that would be computed by a load from
2254 /// P after the stores reflected by 'memory' have been performed.  If we can't
2255 /// decide, return null.
2256 Constant *Evaluator::ComputeLoadResult(Constant *P) {
2257   // If this memory location has been recently stored, use the stored value: it
2258   // is the most up-to-date.
2259   DenseMap<Constant*, Constant*>::const_iterator I = MutatedMemory.find(P);
2260   if (I != MutatedMemory.end()) return I->second;
2261
2262   // Access it.
2263   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
2264     if (GV->hasDefinitiveInitializer())
2265       return GV->getInitializer();
2266     return nullptr;
2267   }
2268
2269   // Handle a constantexpr getelementptr.
2270   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P))
2271     if (CE->getOpcode() == Instruction::GetElementPtr &&
2272         isa<GlobalVariable>(CE->getOperand(0))) {
2273       GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
2274       if (GV->hasDefinitiveInitializer())
2275         return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
2276     }
2277
2278   return nullptr;  // don't know how to evaluate.
2279 }
2280
2281 /// EvaluateBlock - Evaluate all instructions in block BB, returning true if
2282 /// successful, false if we can't evaluate it.  NewBB returns the next BB that
2283 /// control flows into, or null upon return.
2284 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst,
2285                               BasicBlock *&NextBB) {
2286   // This is the main evaluation loop.
2287   while (1) {
2288     Constant *InstResult = nullptr;
2289
2290     DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
2291
2292     if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
2293       if (!SI->isSimple()) {
2294         DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
2295         return false;  // no volatile/atomic accesses.
2296       }
2297       Constant *Ptr = getVal(SI->getOperand(1));
2298       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
2299         DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
2300         Ptr = ConstantFoldConstantExpression(CE, DL, TLI);
2301         DEBUG(dbgs() << "; To: " << *Ptr << "\n");
2302       }
2303       if (!isSimpleEnoughPointerToCommit(Ptr)) {
2304         // If this is too complex for us to commit, reject it.
2305         DEBUG(dbgs() << "Pointer is too complex for us to evaluate store.");
2306         return false;
2307       }
2308
2309       Constant *Val = getVal(SI->getOperand(0));
2310
2311       // If this might be too difficult for the backend to handle (e.g. the addr
2312       // of one global variable divided by another) then we can't commit it.
2313       if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
2314         DEBUG(dbgs() << "Store value is too complex to evaluate store. " << *Val
2315               << "\n");
2316         return false;
2317       }
2318
2319       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
2320         if (CE->getOpcode() == Instruction::BitCast) {
2321           DEBUG(dbgs() << "Attempting to resolve bitcast on constant ptr.\n");
2322           // If we're evaluating a store through a bitcast, then we need
2323           // to pull the bitcast off the pointer type and push it onto the
2324           // stored value.
2325           Ptr = CE->getOperand(0);
2326
2327           Type *NewTy = cast<PointerType>(Ptr->getType())->getElementType();
2328
2329           // In order to push the bitcast onto the stored value, a bitcast
2330           // from NewTy to Val's type must be legal.  If it's not, we can try
2331           // introspecting NewTy to find a legal conversion.
2332           while (!Val->getType()->canLosslesslyBitCastTo(NewTy)) {
2333             // If NewTy is a struct, we can convert the pointer to the struct
2334             // into a pointer to its first member.
2335             // FIXME: This could be extended to support arrays as well.
2336             if (StructType *STy = dyn_cast<StructType>(NewTy)) {
2337               NewTy = STy->getTypeAtIndex(0U);
2338
2339               IntegerType *IdxTy = IntegerType::get(NewTy->getContext(), 32);
2340               Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);
2341               Constant * const IdxList[] = {IdxZero, IdxZero};
2342
2343               Ptr = ConstantExpr::getGetElementPtr(nullptr, Ptr, IdxList);
2344               if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
2345                 Ptr = ConstantFoldConstantExpression(CE, DL, TLI);
2346
2347             // If we can't improve the situation by introspecting NewTy,
2348             // we have to give up.
2349             } else {
2350               DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
2351                     "evaluate.\n");
2352               return false;
2353             }
2354           }
2355
2356           // If we found compatible types, go ahead and push the bitcast
2357           // onto the stored value.
2358           Val = ConstantExpr::getBitCast(Val, NewTy);
2359
2360           DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
2361         }
2362       }
2363
2364       MutatedMemory[Ptr] = Val;
2365     } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
2366       InstResult = ConstantExpr::get(BO->getOpcode(),
2367                                      getVal(BO->getOperand(0)),
2368                                      getVal(BO->getOperand(1)));
2369       DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: " << *InstResult
2370             << "\n");
2371     } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
2372       InstResult = ConstantExpr::getCompare(CI->getPredicate(),
2373                                             getVal(CI->getOperand(0)),
2374                                             getVal(CI->getOperand(1)));
2375       DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
2376             << "\n");
2377     } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
2378       InstResult = ConstantExpr::getCast(CI->getOpcode(),
2379                                          getVal(CI->getOperand(0)),
2380                                          CI->getType());
2381       DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
2382             << "\n");
2383     } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
2384       InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
2385                                            getVal(SI->getOperand(1)),
2386                                            getVal(SI->getOperand(2)));
2387       DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
2388             << "\n");
2389     } else if (auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) {
2390       InstResult = ConstantExpr::getExtractValue(
2391           getVal(EVI->getAggregateOperand()), EVI->getIndices());
2392       DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: " << *InstResult
2393                    << "\n");
2394     } else if (auto *IVI = dyn_cast<InsertValueInst>(CurInst)) {
2395       InstResult = ConstantExpr::getInsertValue(
2396           getVal(IVI->getAggregateOperand()),
2397           getVal(IVI->getInsertedValueOperand()), IVI->getIndices());
2398       DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: " << *InstResult
2399                    << "\n");
2400     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
2401       Constant *P = getVal(GEP->getOperand(0));
2402       SmallVector<Constant*, 8> GEPOps;
2403       for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end();
2404            i != e; ++i)
2405         GEPOps.push_back(getVal(*i));
2406       InstResult =
2407           ConstantExpr::getGetElementPtr(GEP->getSourceElementType(), P, GEPOps,
2408                                          cast<GEPOperator>(GEP)->isInBounds());
2409       DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult
2410             << "\n");
2411     } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
2412
2413       if (!LI->isSimple()) {
2414         DEBUG(dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
2415         return false;  // no volatile/atomic accesses.
2416       }
2417
2418       Constant *Ptr = getVal(LI->getOperand(0));
2419       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
2420         Ptr = ConstantFoldConstantExpression(CE, DL, TLI);
2421         DEBUG(dbgs() << "Found a constant pointer expression, constant "
2422               "folding: " << *Ptr << "\n");
2423       }
2424       InstResult = ComputeLoadResult(Ptr);
2425       if (!InstResult) {
2426         DEBUG(dbgs() << "Failed to compute load result. Can not evaluate load."
2427               "\n");
2428         return false; // Could not evaluate load.
2429       }
2430
2431       DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
2432     } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
2433       if (AI->isArrayAllocation()) {
2434         DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
2435         return false;  // Cannot handle array allocs.
2436       }
2437       Type *Ty = AI->getType()->getElementType();
2438       AllocaTmps.push_back(
2439           make_unique<GlobalVariable>(Ty, false, GlobalValue::InternalLinkage,
2440                                       UndefValue::get(Ty), AI->getName()));
2441       InstResult = AllocaTmps.back().get();
2442       DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
2443     } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
2444       CallSite CS(&*CurInst);
2445
2446       // Debug info can safely be ignored here.
2447       if (isa<DbgInfoIntrinsic>(CS.getInstruction())) {
2448         DEBUG(dbgs() << "Ignoring debug info.\n");
2449         ++CurInst;
2450         continue;
2451       }
2452
2453       // Cannot handle inline asm.
2454       if (isa<InlineAsm>(CS.getCalledValue())) {
2455         DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
2456         return false;
2457       }
2458
2459       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
2460         if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
2461           if (MSI->isVolatile()) {
2462             DEBUG(dbgs() << "Can not optimize a volatile memset " <<
2463                   "intrinsic.\n");
2464             return false;
2465           }
2466           Constant *Ptr = getVal(MSI->getDest());
2467           Constant *Val = getVal(MSI->getValue());
2468           Constant *DestVal = ComputeLoadResult(getVal(Ptr));
2469           if (Val->isNullValue() && DestVal && DestVal->isNullValue()) {
2470             // This memset is a no-op.
2471             DEBUG(dbgs() << "Ignoring no-op memset.\n");
2472             ++CurInst;
2473             continue;
2474           }
2475         }
2476
2477         if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
2478             II->getIntrinsicID() == Intrinsic::lifetime_end) {
2479           DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
2480           ++CurInst;
2481           continue;
2482         }
2483
2484         if (II->getIntrinsicID() == Intrinsic::invariant_start) {
2485           // We don't insert an entry into Values, as it doesn't have a
2486           // meaningful return value.
2487           if (!II->use_empty()) {
2488             DEBUG(dbgs() << "Found unused invariant_start. Can't evaluate.\n");
2489             return false;
2490           }
2491           ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
2492           Value *PtrArg = getVal(II->getArgOperand(1));
2493           Value *Ptr = PtrArg->stripPointerCasts();
2494           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
2495             Type *ElemTy = cast<PointerType>(GV->getType())->getElementType();
2496             if (!Size->isAllOnesValue() &&
2497                 Size->getValue().getLimitedValue() >=
2498                     DL.getTypeStoreSize(ElemTy)) {
2499               Invariants.insert(GV);
2500               DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV
2501                     << "\n");
2502             } else {
2503               DEBUG(dbgs() << "Found a global var, but can not treat it as an "
2504                     "invariant.\n");
2505             }
2506           }
2507           // Continue even if we do nothing.
2508           ++CurInst;
2509           continue;
2510         } else if (II->getIntrinsicID() == Intrinsic::assume) {
2511           DEBUG(dbgs() << "Skipping assume intrinsic.\n");
2512           ++CurInst;
2513           continue;
2514         }
2515
2516         DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
2517         return false;
2518       }
2519
2520       // Resolve function pointers.
2521       Function *Callee = dyn_cast<Function>(getVal(CS.getCalledValue()));
2522       if (!Callee || Callee->mayBeOverridden()) {
2523         DEBUG(dbgs() << "Can not resolve function pointer.\n");
2524         return false;  // Cannot resolve.
2525       }
2526
2527       SmallVector<Constant*, 8> Formals;
2528       for (User::op_iterator i = CS.arg_begin(), e = CS.arg_end(); i != e; ++i)
2529         Formals.push_back(getVal(*i));
2530
2531       if (Callee->isDeclaration()) {
2532         // If this is a function we can constant fold, do it.
2533         if (Constant *C = ConstantFoldCall(Callee, Formals, TLI)) {
2534           InstResult = C;
2535           DEBUG(dbgs() << "Constant folded function call. Result: " <<
2536                 *InstResult << "\n");
2537         } else {
2538           DEBUG(dbgs() << "Can not constant fold function call.\n");
2539           return false;
2540         }
2541       } else {
2542         if (Callee->getFunctionType()->isVarArg()) {
2543           DEBUG(dbgs() << "Can not constant fold vararg function call.\n");
2544           return false;
2545         }
2546
2547         Constant *RetVal = nullptr;
2548         // Execute the call, if successful, use the return value.
2549         ValueStack.emplace_back();
2550         if (!EvaluateFunction(Callee, RetVal, Formals)) {
2551           DEBUG(dbgs() << "Failed to evaluate function.\n");
2552           return false;
2553         }
2554         ValueStack.pop_back();
2555         InstResult = RetVal;
2556
2557         if (InstResult) {
2558           DEBUG(dbgs() << "Successfully evaluated function. Result: " <<
2559                 InstResult << "\n\n");
2560         } else {
2561           DEBUG(dbgs() << "Successfully evaluated function. Result: 0\n\n");
2562         }
2563       }
2564     } else if (isa<TerminatorInst>(CurInst)) {
2565       DEBUG(dbgs() << "Found a terminator instruction.\n");
2566
2567       if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
2568         if (BI->isUnconditional()) {
2569           NextBB = BI->getSuccessor(0);
2570         } else {
2571           ConstantInt *Cond =
2572             dyn_cast<ConstantInt>(getVal(BI->getCondition()));
2573           if (!Cond) return false;  // Cannot determine.
2574
2575           NextBB = BI->getSuccessor(!Cond->getZExtValue());
2576         }
2577       } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
2578         ConstantInt *Val =
2579           dyn_cast<ConstantInt>(getVal(SI->getCondition()));
2580         if (!Val) return false;  // Cannot determine.
2581         NextBB = SI->findCaseValue(Val).getCaseSuccessor();
2582       } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
2583         Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
2584         if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
2585           NextBB = BA->getBasicBlock();
2586         else
2587           return false;  // Cannot determine.
2588       } else if (isa<ReturnInst>(CurInst)) {
2589         NextBB = nullptr;
2590       } else {
2591         // invoke, unwind, resume, unreachable.
2592         DEBUG(dbgs() << "Can not handle terminator.");
2593         return false;  // Cannot handle this terminator.
2594       }
2595
2596       // We succeeded at evaluating this block!
2597       DEBUG(dbgs() << "Successfully evaluated block.\n");
2598       return true;
2599     } else {
2600       // Did not know how to evaluate this!
2601       DEBUG(dbgs() << "Failed to evaluate block due to unhandled instruction."
2602             "\n");
2603       return false;
2604     }
2605
2606     if (!CurInst->use_empty()) {
2607       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(InstResult))
2608         InstResult = ConstantFoldConstantExpression(CE, DL, TLI);
2609
2610       setVal(&*CurInst, InstResult);
2611     }
2612
2613     // If we just processed an invoke, we finished evaluating the block.
2614     if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
2615       NextBB = II->getNormalDest();
2616       DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
2617       return true;
2618     }
2619
2620     // Advance program counter.
2621     ++CurInst;
2622   }
2623 }
2624
2625 /// EvaluateFunction - Evaluate a call to function F, returning true if
2626 /// successful, false if we can't evaluate it.  ActualArgs contains the formal
2627 /// arguments for the function.
2628 bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
2629                                  const SmallVectorImpl<Constant*> &ActualArgs) {
2630   // Check to see if this function is already executing (recursion).  If so,
2631   // bail out.  TODO: we might want to accept limited recursion.
2632   if (std::find(CallStack.begin(), CallStack.end(), F) != CallStack.end())
2633     return false;
2634
2635   CallStack.push_back(F);
2636
2637   // Initialize arguments to the incoming values specified.
2638   unsigned ArgNo = 0;
2639   for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
2640        ++AI, ++ArgNo)
2641     setVal(&*AI, ActualArgs[ArgNo]);
2642
2643   // ExecutedBlocks - We only handle non-looping, non-recursive code.  As such,
2644   // we can only evaluate any one basic block at most once.  This set keeps
2645   // track of what we have executed so we can detect recursive cases etc.
2646   SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
2647
2648   // CurBB - The current basic block we're evaluating.
2649   BasicBlock *CurBB = &F->front();
2650
2651   BasicBlock::iterator CurInst = CurBB->begin();
2652
2653   while (1) {
2654     BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
2655     DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
2656
2657     if (!EvaluateBlock(CurInst, NextBB))
2658       return false;
2659
2660     if (!NextBB) {
2661       // Successfully running until there's no next block means that we found
2662       // the return.  Fill it the return value and pop the call stack.
2663       ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
2664       if (RI->getNumOperands())
2665         RetVal = getVal(RI->getOperand(0));
2666       CallStack.pop_back();
2667       return true;
2668     }
2669
2670     // Okay, we succeeded in evaluating this control flow.  See if we have
2671     // executed the new block before.  If so, we have a looping function,
2672     // which we cannot evaluate in reasonable time.
2673     if (!ExecutedBlocks.insert(NextBB).second)
2674       return false;  // looped!
2675
2676     // Okay, we have never been in this block before.  Check to see if there
2677     // are any PHI nodes.  If so, evaluate them with information about where
2678     // we came from.
2679     PHINode *PN = nullptr;
2680     for (CurInst = NextBB->begin();
2681          (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
2682       setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
2683
2684     // Advance to the next block.
2685     CurBB = NextBB;
2686   }
2687 }
2688
2689 /// EvaluateStaticConstructor - Evaluate static constructors in the function, if
2690 /// we can.  Return true if we can, false otherwise.
2691 static bool EvaluateStaticConstructor(Function *F, const DataLayout &DL,
2692                                       const TargetLibraryInfo *TLI) {
2693   // Call the function.
2694   Evaluator Eval(DL, TLI);
2695   Constant *RetValDummy;
2696   bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy,
2697                                            SmallVector<Constant*, 0>());
2698
2699   if (EvalSuccess) {
2700     ++NumCtorsEvaluated;
2701
2702     // We succeeded at evaluation: commit the result.
2703     DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
2704           << F->getName() << "' to " << Eval.getMutatedMemory().size()
2705           << " stores.\n");
2706     for (DenseMap<Constant*, Constant*>::const_iterator I =
2707            Eval.getMutatedMemory().begin(), E = Eval.getMutatedMemory().end();
2708          I != E; ++I)
2709       CommitValueTo(I->second, I->first);
2710     for (GlobalVariable *GV : Eval.getInvariants())
2711       GV->setConstant(true);
2712   }
2713
2714   return EvalSuccess;
2715 }
2716
2717 static int compareNames(Constant *const *A, Constant *const *B) {
2718   return (*A)->stripPointerCasts()->getName().compare(
2719       (*B)->stripPointerCasts()->getName());
2720 }
2721
2722 static void setUsedInitializer(GlobalVariable &V,
2723                                const SmallPtrSet<GlobalValue *, 8> &Init) {
2724   if (Init.empty()) {
2725     V.eraseFromParent();
2726     return;
2727   }
2728
2729   // Type of pointer to the array of pointers.
2730   PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext(), 0);
2731
2732   SmallVector<llvm::Constant *, 8> UsedArray;
2733   for (GlobalValue *GV : Init) {
2734     Constant *Cast
2735       = ConstantExpr::getPointerBitCastOrAddrSpaceCast(GV, Int8PtrTy);
2736     UsedArray.push_back(Cast);
2737   }
2738   // Sort to get deterministic order.
2739   array_pod_sort(UsedArray.begin(), UsedArray.end(), compareNames);
2740   ArrayType *ATy = ArrayType::get(Int8PtrTy, UsedArray.size());
2741
2742   Module *M = V.getParent();
2743   V.removeFromParent();
2744   GlobalVariable *NV =
2745       new GlobalVariable(*M, ATy, false, llvm::GlobalValue::AppendingLinkage,
2746                          llvm::ConstantArray::get(ATy, UsedArray), "");
2747   NV->takeName(&V);
2748   NV->setSection("llvm.metadata");
2749   delete &V;
2750 }
2751
2752 namespace {
2753 /// \brief An easy to access representation of llvm.used and llvm.compiler.used.
2754 class LLVMUsed {
2755   SmallPtrSet<GlobalValue *, 8> Used;
2756   SmallPtrSet<GlobalValue *, 8> CompilerUsed;
2757   GlobalVariable *UsedV;
2758   GlobalVariable *CompilerUsedV;
2759
2760 public:
2761   LLVMUsed(Module &M) {
2762     UsedV = collectUsedGlobalVariables(M, Used, false);
2763     CompilerUsedV = collectUsedGlobalVariables(M, CompilerUsed, true);
2764   }
2765   typedef SmallPtrSet<GlobalValue *, 8>::iterator iterator;
2766   typedef iterator_range<iterator> used_iterator_range;
2767   iterator usedBegin() { return Used.begin(); }
2768   iterator usedEnd() { return Used.end(); }
2769   used_iterator_range used() {
2770     return used_iterator_range(usedBegin(), usedEnd());
2771   }
2772   iterator compilerUsedBegin() { return CompilerUsed.begin(); }
2773   iterator compilerUsedEnd() { return CompilerUsed.end(); }
2774   used_iterator_range compilerUsed() {
2775     return used_iterator_range(compilerUsedBegin(), compilerUsedEnd());
2776   }
2777   bool usedCount(GlobalValue *GV) const { return Used.count(GV); }
2778   bool compilerUsedCount(GlobalValue *GV) const {
2779     return CompilerUsed.count(GV);
2780   }
2781   bool usedErase(GlobalValue *GV) { return Used.erase(GV); }
2782   bool compilerUsedErase(GlobalValue *GV) { return CompilerUsed.erase(GV); }
2783   bool usedInsert(GlobalValue *GV) { return Used.insert(GV).second; }
2784   bool compilerUsedInsert(GlobalValue *GV) {
2785     return CompilerUsed.insert(GV).second;
2786   }
2787
2788   void syncVariablesAndSets() {
2789     if (UsedV)
2790       setUsedInitializer(*UsedV, Used);
2791     if (CompilerUsedV)
2792       setUsedInitializer(*CompilerUsedV, CompilerUsed);
2793   }
2794 };
2795 }
2796
2797 static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U) {
2798   if (GA.use_empty()) // No use at all.
2799     return false;
2800
2801   assert((!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) &&
2802          "We should have removed the duplicated "
2803          "element from llvm.compiler.used");
2804   if (!GA.hasOneUse())
2805     // Strictly more than one use. So at least one is not in llvm.used and
2806     // llvm.compiler.used.
2807     return true;
2808
2809   // Exactly one use. Check if it is in llvm.used or llvm.compiler.used.
2810   return !U.usedCount(&GA) && !U.compilerUsedCount(&GA);
2811 }
2812
2813 static bool hasMoreThanOneUseOtherThanLLVMUsed(GlobalValue &V,
2814                                                const LLVMUsed &U) {
2815   unsigned N = 2;
2816   assert((!U.usedCount(&V) || !U.compilerUsedCount(&V)) &&
2817          "We should have removed the duplicated "
2818          "element from llvm.compiler.used");
2819   if (U.usedCount(&V) || U.compilerUsedCount(&V))
2820     ++N;
2821   return V.hasNUsesOrMore(N);
2822 }
2823
2824 static bool mayHaveOtherReferences(GlobalAlias &GA, const LLVMUsed &U) {
2825   if (!GA.hasLocalLinkage())
2826     return true;
2827
2828   return U.usedCount(&GA) || U.compilerUsedCount(&GA);
2829 }
2830
2831 static bool hasUsesToReplace(GlobalAlias &GA, const LLVMUsed &U,
2832                              bool &RenameTarget) {
2833   RenameTarget = false;
2834   bool Ret = false;
2835   if (hasUseOtherThanLLVMUsed(GA, U))
2836     Ret = true;
2837
2838   // If the alias is externally visible, we may still be able to simplify it.
2839   if (!mayHaveOtherReferences(GA, U))
2840     return Ret;
2841
2842   // If the aliasee has internal linkage, give it the name and linkage
2843   // of the alias, and delete the alias.  This turns:
2844   //   define internal ... @f(...)
2845   //   @a = alias ... @f
2846   // into:
2847   //   define ... @a(...)
2848   Constant *Aliasee = GA.getAliasee();
2849   GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts());
2850   if (!Target->hasLocalLinkage())
2851     return Ret;
2852
2853   // Do not perform the transform if multiple aliases potentially target the
2854   // aliasee. This check also ensures that it is safe to replace the section
2855   // and other attributes of the aliasee with those of the alias.
2856   if (hasMoreThanOneUseOtherThanLLVMUsed(*Target, U))
2857     return Ret;
2858
2859   RenameTarget = true;
2860   return true;
2861 }
2862
2863 bool GlobalOpt::OptimizeGlobalAliases(Module &M) {
2864   bool Changed = false;
2865   LLVMUsed Used(M);
2866
2867   for (GlobalValue *GV : Used.used())
2868     Used.compilerUsedErase(GV);
2869
2870   for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end();
2871        I != E;) {
2872     Module::alias_iterator J = I++;
2873     // Aliases without names cannot be referenced outside this module.
2874     if (!J->hasName() && !J->isDeclaration() && !J->hasLocalLinkage())
2875       J->setLinkage(GlobalValue::InternalLinkage);
2876     // If the aliasee may change at link time, nothing can be done - bail out.
2877     if (J->mayBeOverridden())
2878       continue;
2879
2880     Constant *Aliasee = J->getAliasee();
2881     GlobalValue *Target = dyn_cast<GlobalValue>(Aliasee->stripPointerCasts());
2882     // We can't trivially replace the alias with the aliasee if the aliasee is
2883     // non-trivial in some way.
2884     // TODO: Try to handle non-zero GEPs of local aliasees.
2885     if (!Target)
2886       continue;
2887     Target->removeDeadConstantUsers();
2888
2889     // Make all users of the alias use the aliasee instead.
2890     bool RenameTarget;
2891     if (!hasUsesToReplace(*J, Used, RenameTarget))
2892       continue;
2893
2894     J->replaceAllUsesWith(ConstantExpr::getBitCast(Aliasee, J->getType()));
2895     ++NumAliasesResolved;
2896     Changed = true;
2897
2898     if (RenameTarget) {
2899       // Give the aliasee the name, linkage and other attributes of the alias.
2900       Target->takeName(&*J);
2901       Target->setLinkage(J->getLinkage());
2902       Target->setVisibility(J->getVisibility());
2903       Target->setDLLStorageClass(J->getDLLStorageClass());
2904
2905       if (Used.usedErase(&*J))
2906         Used.usedInsert(Target);
2907
2908       if (Used.compilerUsedErase(&*J))
2909         Used.compilerUsedInsert(Target);
2910     } else if (mayHaveOtherReferences(*J, Used))
2911       continue;
2912
2913     // Delete the alias.
2914     M.getAliasList().erase(J);
2915     ++NumAliasesRemoved;
2916     Changed = true;
2917   }
2918
2919   Used.syncVariablesAndSets();
2920
2921   return Changed;
2922 }
2923
2924 static Function *FindCXAAtExit(Module &M, TargetLibraryInfo *TLI) {
2925   if (!TLI->has(LibFunc::cxa_atexit))
2926     return nullptr;
2927
2928   Function *Fn = M.getFunction(TLI->getName(LibFunc::cxa_atexit));
2929
2930   if (!Fn)
2931     return nullptr;
2932
2933   FunctionType *FTy = Fn->getFunctionType();
2934
2935   // Checking that the function has the right return type, the right number of
2936   // parameters and that they all have pointer types should be enough.
2937   if (!FTy->getReturnType()->isIntegerTy() ||
2938       FTy->getNumParams() != 3 ||
2939       !FTy->getParamType(0)->isPointerTy() ||
2940       !FTy->getParamType(1)->isPointerTy() ||
2941       !FTy->getParamType(2)->isPointerTy())
2942     return nullptr;
2943
2944   return Fn;
2945 }
2946
2947 /// cxxDtorIsEmpty - Returns whether the given function is an empty C++
2948 /// destructor and can therefore be eliminated.
2949 /// Note that we assume that other optimization passes have already simplified
2950 /// the code so we only look for a function with a single basic block, where
2951 /// the only allowed instructions are 'ret', 'call' to an empty C++ dtor and
2952 /// other side-effect free instructions.
2953 static bool cxxDtorIsEmpty(const Function &Fn,
2954                            SmallPtrSet<const Function *, 8> &CalledFunctions) {
2955   // FIXME: We could eliminate C++ destructors if they're readonly/readnone and
2956   // nounwind, but that doesn't seem worth doing.
2957   if (Fn.isDeclaration())
2958     return false;
2959
2960   if (++Fn.begin() != Fn.end())
2961     return false;
2962
2963   const BasicBlock &EntryBlock = Fn.getEntryBlock();
2964   for (BasicBlock::const_iterator I = EntryBlock.begin(), E = EntryBlock.end();
2965        I != E; ++I) {
2966     if (const CallInst *CI = dyn_cast<CallInst>(I)) {
2967       // Ignore debug intrinsics.
2968       if (isa<DbgInfoIntrinsic>(CI))
2969         continue;
2970
2971       const Function *CalledFn = CI->getCalledFunction();
2972
2973       if (!CalledFn)
2974         return false;
2975
2976       SmallPtrSet<const Function *, 8> NewCalledFunctions(CalledFunctions);
2977
2978       // Don't treat recursive functions as empty.
2979       if (!NewCalledFunctions.insert(CalledFn).second)
2980         return false;
2981
2982       if (!cxxDtorIsEmpty(*CalledFn, NewCalledFunctions))
2983         return false;
2984     } else if (isa<ReturnInst>(*I))
2985       return true; // We're done.
2986     else if (I->mayHaveSideEffects())
2987       return false; // Destructor with side effects, bail.
2988   }
2989
2990   return false;
2991 }
2992
2993 bool GlobalOpt::OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) {
2994   /// Itanium C++ ABI p3.3.5:
2995   ///
2996   ///   After constructing a global (or local static) object, that will require
2997   ///   destruction on exit, a termination function is registered as follows:
2998   ///
2999   ///   extern "C" int __cxa_atexit ( void (*f)(void *), void *p, void *d );
3000   ///
3001   ///   This registration, e.g. __cxa_atexit(f,p,d), is intended to cause the
3002   ///   call f(p) when DSO d is unloaded, before all such termination calls
3003   ///   registered before this one. It returns zero if registration is
3004   ///   successful, nonzero on failure.
3005
3006   // This pass will look for calls to __cxa_atexit where the function is trivial
3007   // and remove them.
3008   bool Changed = false;
3009
3010   for (auto I = CXAAtExitFn->user_begin(), E = CXAAtExitFn->user_end();
3011        I != E;) {
3012     // We're only interested in calls. Theoretically, we could handle invoke
3013     // instructions as well, but neither llvm-gcc nor clang generate invokes
3014     // to __cxa_atexit.
3015     CallInst *CI = dyn_cast<CallInst>(*I++);
3016     if (!CI)
3017       continue;
3018
3019     Function *DtorFn =
3020       dyn_cast<Function>(CI->getArgOperand(0)->stripPointerCasts());
3021     if (!DtorFn)
3022       continue;
3023
3024     SmallPtrSet<const Function *, 8> CalledFunctions;
3025     if (!cxxDtorIsEmpty(*DtorFn, CalledFunctions))
3026       continue;
3027
3028     // Just remove the call.
3029     CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
3030     CI->eraseFromParent();
3031
3032     ++NumCXXDtorsRemoved;
3033
3034     Changed |= true;
3035   }
3036
3037   return Changed;
3038 }
3039
3040 bool GlobalOpt::runOnModule(Module &M) {
3041   bool Changed = false;
3042
3043   auto &DL = M.getDataLayout();
3044   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
3045
3046   bool LocalChange = true;
3047   while (LocalChange) {
3048     LocalChange = false;
3049
3050     NotDiscardableComdats.clear();
3051     for (const GlobalVariable &GV : M.globals())
3052       if (const Comdat *C = GV.getComdat())
3053         if (!GV.isDiscardableIfUnused() || !GV.use_empty())
3054           NotDiscardableComdats.insert(C);
3055     for (Function &F : M)
3056       if (const Comdat *C = F.getComdat())
3057         if (!F.isDefTriviallyDead())
3058           NotDiscardableComdats.insert(C);
3059     for (GlobalAlias &GA : M.aliases())
3060       if (const Comdat *C = GA.getComdat())
3061         if (!GA.isDiscardableIfUnused() || !GA.use_empty())
3062           NotDiscardableComdats.insert(C);
3063
3064     // Delete functions that are trivially dead, ccc -> fastcc
3065     LocalChange |= OptimizeFunctions(M);
3066
3067     // Optimize global_ctors list.
3068     LocalChange |= optimizeGlobalCtorsList(M, [&](Function *F) {
3069       return EvaluateStaticConstructor(F, DL, TLI);
3070     });
3071
3072     // Optimize non-address-taken globals.
3073     LocalChange |= OptimizeGlobalVars(M);
3074
3075     // Resolve aliases, when possible.
3076     LocalChange |= OptimizeGlobalAliases(M);
3077
3078     // Try to remove trivial global destructors if they are not removed
3079     // already.
3080     Function *CXAAtExitFn = FindCXAAtExit(M, TLI);
3081     if (CXAAtExitFn)
3082       LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn);
3083
3084     Changed |= LocalChange;
3085   }
3086
3087   // TODO: Move all global ctors functions to the end of the module for code
3088   // layout.
3089
3090   return Changed;
3091 }
3092