LLVM API Documentation

GlobalOpt.cpp
Go to the documentation of this file.
00001 //===- GlobalOpt.cpp - Optimize Global Variables --------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass transforms simple global variables that never have their address
00011 // taken.  If obviously true, it marks read/write globals as constant, deletes
00012 // variables only stored to, etc.
00013 //
00014 //===----------------------------------------------------------------------===//
00015 
00016 #include "llvm/Transforms/IPO.h"
00017 #include "llvm/ADT/DenseMap.h"
00018 #include "llvm/ADT/STLExtras.h"
00019 #include "llvm/ADT/SmallPtrSet.h"
00020 #include "llvm/ADT/SmallSet.h"
00021 #include "llvm/ADT/SmallVector.h"
00022 #include "llvm/ADT/Statistic.h"
00023 #include "llvm/Analysis/ConstantFolding.h"
00024 #include "llvm/Analysis/MemoryBuiltins.h"
00025 #include "llvm/IR/CallSite.h"
00026 #include "llvm/IR/CallingConv.h"
00027 #include "llvm/IR/Constants.h"
00028 #include "llvm/IR/DataLayout.h"
00029 #include "llvm/IR/DerivedTypes.h"
00030 #include "llvm/IR/GetElementPtrTypeIterator.h"
00031 #include "llvm/IR/Instructions.h"
00032 #include "llvm/IR/IntrinsicInst.h"
00033 #include "llvm/IR/Module.h"
00034 #include "llvm/IR/Operator.h"
00035 #include "llvm/IR/ValueHandle.h"
00036 #include "llvm/Pass.h"
00037 #include "llvm/Support/Debug.h"
00038 #include "llvm/Support/ErrorHandling.h"
00039 #include "llvm/Support/MathExtras.h"
00040 #include "llvm/Support/raw_ostream.h"
00041 #include "llvm/Target/TargetLibraryInfo.h"
00042 #include "llvm/Transforms/Utils/CtorUtils.h"
00043 #include "llvm/Transforms/Utils/GlobalStatus.h"
00044 #include "llvm/Transforms/Utils/ModuleUtils.h"
00045 #include <algorithm>
00046 #include <deque>
00047 using namespace llvm;
00048 
00049 #define DEBUG_TYPE "globalopt"
00050 
00051 STATISTIC(NumMarked    , "Number of globals marked constant");
00052 STATISTIC(NumUnnamed   , "Number of globals marked unnamed_addr");
00053 STATISTIC(NumSRA       , "Number of aggregate globals broken into scalars");
00054 STATISTIC(NumHeapSRA   , "Number of heap objects SRA'd");
00055 STATISTIC(NumSubstitute,"Number of globals with initializers stored into them");
00056 STATISTIC(NumDeleted   , "Number of globals deleted");
00057 STATISTIC(NumFnDeleted , "Number of functions deleted");
00058 STATISTIC(NumGlobUses  , "Number of global uses devirtualized");
00059 STATISTIC(NumLocalized , "Number of globals localized");
00060 STATISTIC(NumShrunkToBool  , "Number of global vars shrunk to booleans");
00061 STATISTIC(NumFastCallFns   , "Number of functions converted to fastcc");
00062 STATISTIC(NumCtorsEvaluated, "Number of static ctors evaluated");
00063 STATISTIC(NumNestRemoved   , "Number of nest attributes removed");
00064 STATISTIC(NumAliasesResolved, "Number of global aliases resolved");
00065 STATISTIC(NumAliasesRemoved, "Number of global aliases eliminated");
00066 STATISTIC(NumCXXDtorsRemoved, "Number of global C++ destructors removed");
00067 
00068 namespace {
00069   struct GlobalOpt : public ModulePass {
00070     void getAnalysisUsage(AnalysisUsage &AU) const override {
00071       AU.addRequired<TargetLibraryInfo>();
00072     }
00073     static char ID; // Pass identification, replacement for typeid
00074     GlobalOpt() : ModulePass(ID) {
00075       initializeGlobalOptPass(*PassRegistry::getPassRegistry());
00076     }
00077 
00078     bool runOnModule(Module &M) override;
00079 
00080   private:
00081     bool OptimizeFunctions(Module &M);
00082     bool OptimizeGlobalVars(Module &M);
00083     bool OptimizeGlobalAliases(Module &M);
00084     bool ProcessGlobal(GlobalVariable *GV,Module::global_iterator &GVI);
00085     bool ProcessInternalGlobal(GlobalVariable *GV,Module::global_iterator &GVI,
00086                                const GlobalStatus &GS);
00087     bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn);
00088 
00089     const DataLayout *DL;
00090     TargetLibraryInfo *TLI;
00091   };
00092 }
00093 
00094 char GlobalOpt::ID = 0;
00095 INITIALIZE_PASS_BEGIN(GlobalOpt, "globalopt",
00096                 "Global Variable Optimizer", false, false)
00097 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
00098 INITIALIZE_PASS_END(GlobalOpt, "globalopt",
00099                 "Global Variable Optimizer", false, false)
00100 
00101 ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); }
00102 
00103 /// isLeakCheckerRoot - Is this global variable possibly used by a leak checker
00104 /// as a root?  If so, we might not really want to eliminate the stores to it.
00105 static bool isLeakCheckerRoot(GlobalVariable *GV) {
00106   // A global variable is a root if it is a pointer, or could plausibly contain
00107   // a pointer.  There are two challenges; one is that we could have a struct
00108   // the has an inner member which is a pointer.  We recurse through the type to
00109   // detect these (up to a point).  The other is that we may actually be a union
00110   // of a pointer and another type, and so our LLVM type is an integer which
00111   // gets converted into a pointer, or our type is an [i8 x #] with a pointer
00112   // potentially contained here.
00113 
00114   if (GV->hasPrivateLinkage())
00115     return false;
00116 
00117   SmallVector<Type *, 4> Types;
00118   Types.push_back(cast<PointerType>(GV->getType())->getElementType());
00119 
00120   unsigned Limit = 20;
00121   do {
00122     Type *Ty = Types.pop_back_val();
00123     switch (Ty->getTypeID()) {
00124       default: break;
00125       case Type::PointerTyID: return true;
00126       case Type::ArrayTyID:
00127       case Type::VectorTyID: {
00128         SequentialType *STy = cast<SequentialType>(Ty);
00129         Types.push_back(STy->getElementType());
00130         break;
00131       }
00132       case Type::StructTyID: {
00133         StructType *STy = cast<StructType>(Ty);
00134         if (STy->isOpaque()) return true;
00135         for (StructType::element_iterator I = STy->element_begin(),
00136                  E = STy->element_end(); I != E; ++I) {
00137           Type *InnerTy = *I;
00138           if (isa<PointerType>(InnerTy)) return true;
00139           if (isa<CompositeType>(InnerTy))
00140             Types.push_back(InnerTy);
00141         }
00142         break;
00143       }
00144     }
00145     if (--Limit == 0) return true;
00146   } while (!Types.empty());
00147   return false;
00148 }
00149 
00150 /// Given a value that is stored to a global but never read, determine whether
00151 /// it's safe to remove the store and the chain of computation that feeds the
00152 /// store.
00153 static bool IsSafeComputationToRemove(Value *V, const TargetLibraryInfo *TLI) {
00154   do {
00155     if (isa<Constant>(V))
00156       return true;
00157     if (!V->hasOneUse())
00158       return false;
00159     if (isa<LoadInst>(V) || isa<InvokeInst>(V) || isa<Argument>(V) ||
00160         isa<GlobalValue>(V))
00161       return false;
00162     if (isAllocationFn(V, TLI))
00163       return true;
00164 
00165     Instruction *I = cast<Instruction>(V);
00166     if (I->mayHaveSideEffects())
00167       return false;
00168     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I)) {
00169       if (!GEP->hasAllConstantIndices())
00170         return false;
00171     } else if (I->getNumOperands() != 1) {
00172       return false;
00173     }
00174 
00175     V = I->getOperand(0);
00176   } while (1);
00177 }
00178 
00179 /// CleanupPointerRootUsers - This GV is a pointer root.  Loop over all users
00180 /// of the global and clean up any that obviously don't assign the global a
00181 /// value that isn't dynamically allocated.
00182 ///
00183 static bool CleanupPointerRootUsers(GlobalVariable *GV,
00184                                     const TargetLibraryInfo *TLI) {
00185   // A brief explanation of leak checkers.  The goal is to find bugs where
00186   // pointers are forgotten, causing an accumulating growth in memory
00187   // usage over time.  The common strategy for leak checkers is to whitelist the
00188   // memory pointed to by globals at exit.  This is popular because it also
00189   // solves another problem where the main thread of a C++ program may shut down
00190   // before other threads that are still expecting to use those globals.  To
00191   // handle that case, we expect the program may create a singleton and never
00192   // destroy it.
00193 
00194   bool Changed = false;
00195 
00196   // If Dead[n].first is the only use of a malloc result, we can delete its
00197   // chain of computation and the store to the global in Dead[n].second.
00198   SmallVector<std::pair<Instruction *, Instruction *>, 32> Dead;
00199 
00200   // Constants can't be pointers to dynamically allocated memory.
00201   for (Value::user_iterator UI = GV->user_begin(), E = GV->user_end();
00202        UI != E;) {
00203     User *U = *UI++;
00204     if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
00205       Value *V = SI->getValueOperand();
00206       if (isa<Constant>(V)) {
00207         Changed = true;
00208         SI->eraseFromParent();
00209       } else if (Instruction *I = dyn_cast<Instruction>(V)) {
00210         if (I->hasOneUse())
00211           Dead.push_back(std::make_pair(I, SI));
00212       }
00213     } else if (MemSetInst *MSI = dyn_cast<MemSetInst>(U)) {
00214       if (isa<Constant>(MSI->getValue())) {
00215         Changed = true;
00216         MSI->eraseFromParent();
00217       } else if (Instruction *I = dyn_cast<Instruction>(MSI->getValue())) {
00218         if (I->hasOneUse())
00219           Dead.push_back(std::make_pair(I, MSI));
00220       }
00221     } else if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(U)) {
00222       GlobalVariable *MemSrc = dyn_cast<GlobalVariable>(MTI->getSource());
00223       if (MemSrc && MemSrc->isConstant()) {
00224         Changed = true;
00225         MTI->eraseFromParent();
00226       } else if (Instruction *I = dyn_cast<Instruction>(MemSrc)) {
00227         if (I->hasOneUse())
00228           Dead.push_back(std::make_pair(I, MTI));
00229       }
00230     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
00231       if (CE->use_empty()) {
00232         CE->destroyConstant();
00233         Changed = true;
00234       }
00235     } else if (Constant *C = dyn_cast<Constant>(U)) {
00236       if (isSafeToDestroyConstant(C)) {
00237         C->destroyConstant();
00238         // This could have invalidated UI, start over from scratch.
00239         Dead.clear();
00240         CleanupPointerRootUsers(GV, TLI);
00241         return true;
00242       }
00243     }
00244   }
00245 
00246   for (int i = 0, e = Dead.size(); i != e; ++i) {
00247     if (IsSafeComputationToRemove(Dead[i].first, TLI)) {
00248       Dead[i].second->eraseFromParent();
00249       Instruction *I = Dead[i].first;
00250       do {
00251         if (isAllocationFn(I, TLI))
00252           break;
00253         Instruction *J = dyn_cast<Instruction>(I->getOperand(0));
00254         if (!J)
00255           break;
00256         I->eraseFromParent();
00257         I = J;
00258       } while (1);
00259       I->eraseFromParent();
00260     }
00261   }
00262 
00263   return Changed;
00264 }
00265 
00266 /// CleanupConstantGlobalUsers - We just marked GV constant.  Loop over all
00267 /// users of the global, cleaning up the obvious ones.  This is largely just a
00268 /// quick scan over the use list to clean up the easy and obvious cruft.  This
00269 /// returns true if it made a change.
00270 static bool CleanupConstantGlobalUsers(Value *V, Constant *Init,
00271                                        const DataLayout *DL,
00272                                        TargetLibraryInfo *TLI) {
00273   bool Changed = false;
00274   // Note that we need to use a weak value handle for the worklist items. When
00275   // we delete a constant array, we may also be holding pointer to one of its
00276   // elements (or an element of one of its elements if we're dealing with an
00277   // array of arrays) in the worklist.
00278   SmallVector<WeakVH, 8> WorkList(V->user_begin(), V->user_end());
00279   while (!WorkList.empty()) {
00280     Value *UV = WorkList.pop_back_val();
00281     if (!UV)
00282       continue;
00283 
00284     User *U = cast<User>(UV);
00285 
00286     if (LoadInst *LI = dyn_cast<LoadInst>(U)) {
00287       if (Init) {
00288         // Replace the load with the initializer.
00289         LI->replaceAllUsesWith(Init);
00290         LI->eraseFromParent();
00291         Changed = true;
00292       }
00293     } else if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
00294       // Store must be unreachable or storing Init into the global.
00295       SI->eraseFromParent();
00296       Changed = true;
00297     } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) {
00298       if (CE->getOpcode() == Instruction::GetElementPtr) {
00299         Constant *SubInit = nullptr;
00300         if (Init)
00301           SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
00302         Changed |= CleanupConstantGlobalUsers(CE, SubInit, DL, TLI);
00303       } else if ((CE->getOpcode() == Instruction::BitCast &&
00304                   CE->getType()->isPointerTy()) ||
00305                  CE->getOpcode() == Instruction::AddrSpaceCast) {
00306         // Pointer cast, delete any stores and memsets to the global.
00307         Changed |= CleanupConstantGlobalUsers(CE, nullptr, DL, TLI);
00308       }
00309 
00310       if (CE->use_empty()) {
00311         CE->destroyConstant();
00312         Changed = true;
00313       }
00314     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(U)) {
00315       // Do not transform "gepinst (gep constexpr (GV))" here, because forming
00316       // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold
00317       // and will invalidate our notion of what Init is.
00318       Constant *SubInit = nullptr;
00319       if (!isa<ConstantExpr>(GEP->getOperand(0))) {
00320         ConstantExpr *CE =
00321           dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP, DL, TLI));
00322         if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr)
00323           SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE);
00324 
00325         // If the initializer is an all-null value and we have an inbounds GEP,
00326         // we already know what the result of any load from that GEP is.
00327         // TODO: Handle splats.
00328         if (Init && isa<ConstantAggregateZero>(Init) && GEP->isInBounds())
00329           SubInit = Constant::getNullValue(GEP->getType()->getElementType());
00330       }
00331       Changed |= CleanupConstantGlobalUsers(GEP, SubInit, DL, TLI);
00332 
00333       if (GEP->use_empty()) {
00334         GEP->eraseFromParent();
00335         Changed = true;
00336       }
00337     } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(U)) { // memset/cpy/mv
00338       if (MI->getRawDest() == V) {
00339         MI->eraseFromParent();
00340         Changed = true;
00341       }
00342 
00343     } else if (Constant *C = dyn_cast<Constant>(U)) {
00344       // If we have a chain of dead constantexprs or other things dangling from
00345       // us, and if they are all dead, nuke them without remorse.
00346       if (isSafeToDestroyConstant(C)) {
00347         C->destroyConstant();
00348         CleanupConstantGlobalUsers(V, Init, DL, TLI);
00349         return true;
00350       }
00351     }
00352   }
00353   return Changed;
00354 }
00355 
00356 /// isSafeSROAElementUse - Return true if the specified instruction is a safe
00357 /// user of a derived expression from a global that we want to SROA.
00358 static bool isSafeSROAElementUse(Value *V) {
00359   // We might have a dead and dangling constant hanging off of here.
00360   if (Constant *C = dyn_cast<Constant>(V))
00361     return isSafeToDestroyConstant(C);
00362 
00363   Instruction *I = dyn_cast<Instruction>(V);
00364   if (!I) return false;
00365 
00366   // Loads are ok.
00367   if (isa<LoadInst>(I)) return true;
00368 
00369   // Stores *to* the pointer are ok.
00370   if (StoreInst *SI = dyn_cast<StoreInst>(I))
00371     return SI->getOperand(0) != V;
00372 
00373   // Otherwise, it must be a GEP.
00374   GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I);
00375   if (!GEPI) return false;
00376 
00377   if (GEPI->getNumOperands() < 3 || !isa<Constant>(GEPI->getOperand(1)) ||
00378       !cast<Constant>(GEPI->getOperand(1))->isNullValue())
00379     return false;
00380 
00381   for (User *U : GEPI->users())
00382     if (!isSafeSROAElementUse(U))
00383       return false;
00384   return true;
00385 }
00386 
00387 
00388 /// IsUserOfGlobalSafeForSRA - U is a direct user of the specified global value.
00389 /// Look at it and its uses and decide whether it is safe to SROA this global.
00390 ///
00391 static bool IsUserOfGlobalSafeForSRA(User *U, GlobalValue *GV) {
00392   // The user of the global must be a GEP Inst or a ConstantExpr GEP.
00393   if (!isa<GetElementPtrInst>(U) &&
00394       (!isa<ConstantExpr>(U) ||
00395        cast<ConstantExpr>(U)->getOpcode() != Instruction::GetElementPtr))
00396     return false;
00397 
00398   // Check to see if this ConstantExpr GEP is SRA'able.  In particular, we
00399   // don't like < 3 operand CE's, and we don't like non-constant integer
00400   // indices.  This enforces that all uses are 'gep GV, 0, C, ...' for some
00401   // value of C.
00402   if (U->getNumOperands() < 3 || !isa<Constant>(U->getOperand(1)) ||
00403       !cast<Constant>(U->getOperand(1))->isNullValue() ||
00404       !isa<ConstantInt>(U->getOperand(2)))
00405     return false;
00406 
00407   gep_type_iterator GEPI = gep_type_begin(U), E = gep_type_end(U);
00408   ++GEPI;  // Skip over the pointer index.
00409 
00410   // If this is a use of an array allocation, do a bit more checking for sanity.
00411   if (ArrayType *AT = dyn_cast<ArrayType>(*GEPI)) {
00412     uint64_t NumElements = AT->getNumElements();
00413     ConstantInt *Idx = cast<ConstantInt>(U->getOperand(2));
00414 
00415     // Check to make sure that index falls within the array.  If not,
00416     // something funny is going on, so we won't do the optimization.
00417     //
00418     if (Idx->getZExtValue() >= NumElements)
00419       return false;
00420 
00421     // We cannot scalar repl this level of the array unless any array
00422     // sub-indices are in-range constants.  In particular, consider:
00423     // A[0][i].  We cannot know that the user isn't doing invalid things like
00424     // allowing i to index an out-of-range subscript that accesses A[1].
00425     //
00426     // Scalar replacing *just* the outer index of the array is probably not
00427     // going to be a win anyway, so just give up.
00428     for (++GEPI; // Skip array index.
00429          GEPI != E;
00430          ++GEPI) {
00431       uint64_t NumElements;
00432       if (ArrayType *SubArrayTy = dyn_cast<ArrayType>(*GEPI))
00433         NumElements = SubArrayTy->getNumElements();
00434       else if (VectorType *SubVectorTy = dyn_cast<VectorType>(*GEPI))
00435         NumElements = SubVectorTy->getNumElements();
00436       else {
00437         assert((*GEPI)->isStructTy() &&
00438                "Indexed GEP type is not array, vector, or struct!");
00439         continue;
00440       }
00441 
00442       ConstantInt *IdxVal = dyn_cast<ConstantInt>(GEPI.getOperand());
00443       if (!IdxVal || IdxVal->getZExtValue() >= NumElements)
00444         return false;
00445     }
00446   }
00447 
00448   for (User *UU : U->users())
00449     if (!isSafeSROAElementUse(UU))
00450       return false;
00451 
00452   return true;
00453 }
00454 
00455 /// GlobalUsersSafeToSRA - Look at all uses of the global and decide whether it
00456 /// is safe for us to perform this transformation.
00457 ///
00458 static bool GlobalUsersSafeToSRA(GlobalValue *GV) {
00459   for (User *U : GV->users())
00460     if (!IsUserOfGlobalSafeForSRA(U, GV))
00461       return false;
00462 
00463   return true;
00464 }
00465 
00466 
00467 /// SRAGlobal - Perform scalar replacement of aggregates on the specified global
00468 /// variable.  This opens the door for other optimizations by exposing the
00469 /// behavior of the program in a more fine-grained way.  We have determined that
00470 /// this transformation is safe already.  We return the first global variable we
00471 /// insert so that the caller can reprocess it.
00472 static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &DL) {
00473   // Make sure this global only has simple uses that we can SRA.
00474   if (!GlobalUsersSafeToSRA(GV))
00475     return nullptr;
00476 
00477   assert(GV->hasLocalLinkage() && !GV->isConstant());
00478   Constant *Init = GV->getInitializer();
00479   Type *Ty = Init->getType();
00480 
00481   std::vector<GlobalVariable*> NewGlobals;
00482   Module::GlobalListType &Globals = GV->getParent()->getGlobalList();
00483 
00484   // Get the alignment of the global, either explicit or target-specific.
00485   unsigned StartAlignment = GV->getAlignment();
00486   if (StartAlignment == 0)
00487     StartAlignment = DL.getABITypeAlignment(GV->getType());
00488 
00489   if (StructType *STy = dyn_cast<StructType>(Ty)) {
00490     NewGlobals.reserve(STy->getNumElements());
00491     const StructLayout &Layout = *DL.getStructLayout(STy);
00492     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) {
00493       Constant *In = Init->getAggregateElement(i);
00494       assert(In && "Couldn't get element of initializer?");
00495       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(i), false,
00496                                                GlobalVariable::InternalLinkage,
00497                                                In, GV->getName()+"."+Twine(i),
00498                                                GV->getThreadLocalMode(),
00499                                               GV->getType()->getAddressSpace());
00500       Globals.insert(GV, NGV);
00501       NewGlobals.push_back(NGV);
00502 
00503       // Calculate the known alignment of the field.  If the original aggregate
00504       // had 256 byte alignment for example, something might depend on that:
00505       // propagate info to each field.
00506       uint64_t FieldOffset = Layout.getElementOffset(i);
00507       unsigned NewAlign = (unsigned)MinAlign(StartAlignment, FieldOffset);
00508       if (NewAlign > DL.getABITypeAlignment(STy->getElementType(i)))
00509         NGV->setAlignment(NewAlign);
00510     }
00511   } else if (SequentialType *STy = dyn_cast<SequentialType>(Ty)) {
00512     unsigned NumElements = 0;
00513     if (ArrayType *ATy = dyn_cast<ArrayType>(STy))
00514       NumElements = ATy->getNumElements();
00515     else
00516       NumElements = cast<VectorType>(STy)->getNumElements();
00517 
00518     if (NumElements > 16 && GV->hasNUsesOrMore(16))
00519       return nullptr; // It's not worth it.
00520     NewGlobals.reserve(NumElements);
00521 
00522     uint64_t EltSize = DL.getTypeAllocSize(STy->getElementType());
00523     unsigned EltAlign = DL.getABITypeAlignment(STy->getElementType());
00524     for (unsigned i = 0, e = NumElements; i != e; ++i) {
00525       Constant *In = Init->getAggregateElement(i);
00526       assert(In && "Couldn't get element of initializer?");
00527 
00528       GlobalVariable *NGV = new GlobalVariable(STy->getElementType(), false,
00529                                                GlobalVariable::InternalLinkage,
00530                                                In, GV->getName()+"."+Twine(i),
00531                                                GV->getThreadLocalMode(),
00532                                               GV->getType()->getAddressSpace());
00533       Globals.insert(GV, NGV);
00534       NewGlobals.push_back(NGV);
00535 
00536       // Calculate the known alignment of the field.  If the original aggregate
00537       // had 256 byte alignment for example, something might depend on that:
00538       // propagate info to each field.
00539       unsigned NewAlign = (unsigned)MinAlign(StartAlignment, EltSize*i);
00540       if (NewAlign > EltAlign)
00541         NGV->setAlignment(NewAlign);
00542     }
00543   }
00544 
00545   if (NewGlobals.empty())
00546     return nullptr;
00547 
00548   DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV);
00549 
00550   Constant *NullInt =Constant::getNullValue(Type::getInt32Ty(GV->getContext()));
00551 
00552   // Loop over all of the uses of the global, replacing the constantexpr geps,
00553   // with smaller constantexpr geps or direct references.
00554   while (!GV->use_empty()) {
00555     User *GEP = GV->user_back();
00556     assert(((isa<ConstantExpr>(GEP) &&
00557              cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)||
00558             isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!");
00559 
00560     // Ignore the 1th operand, which has to be zero or else the program is quite
00561     // broken (undefined).  Get the 2nd operand, which is the structure or array
00562     // index.
00563     unsigned Val = cast<ConstantInt>(GEP->getOperand(2))->getZExtValue();
00564     if (Val >= NewGlobals.size()) Val = 0; // Out of bound array access.
00565 
00566     Value *NewPtr = NewGlobals[Val];
00567 
00568     // Form a shorter GEP if needed.
00569     if (GEP->getNumOperands() > 3) {
00570       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP)) {
00571         SmallVector<Constant*, 8> Idxs;
00572         Idxs.push_back(NullInt);
00573         for (unsigned i = 3, e = CE->getNumOperands(); i != e; ++i)
00574           Idxs.push_back(CE->getOperand(i));
00575         NewPtr = ConstantExpr::getGetElementPtr(cast<Constant>(NewPtr), Idxs);
00576       } else {
00577         GetElementPtrInst *GEPI = cast<GetElementPtrInst>(GEP);
00578         SmallVector<Value*, 8> Idxs;
00579         Idxs.push_back(NullInt);
00580         for (unsigned i = 3, e = GEPI->getNumOperands(); i != e; ++i)
00581           Idxs.push_back(GEPI->getOperand(i));
00582         NewPtr = GetElementPtrInst::Create(NewPtr, Idxs,
00583                                            GEPI->getName()+"."+Twine(Val),GEPI);
00584       }
00585     }
00586     GEP->replaceAllUsesWith(NewPtr);
00587 
00588     if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(GEP))
00589       GEPI->eraseFromParent();
00590     else
00591       cast<ConstantExpr>(GEP)->destroyConstant();
00592   }
00593 
00594   // Delete the old global, now that it is dead.
00595   Globals.erase(GV);
00596   ++NumSRA;
00597 
00598   // Loop over the new globals array deleting any globals that are obviously
00599   // dead.  This can arise due to scalarization of a structure or an array that
00600   // has elements that are dead.
00601   unsigned FirstGlobal = 0;
00602   for (unsigned i = 0, e = NewGlobals.size(); i != e; ++i)
00603     if (NewGlobals[i]->use_empty()) {
00604       Globals.erase(NewGlobals[i]);
00605       if (FirstGlobal == i) ++FirstGlobal;
00606     }
00607 
00608   return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : nullptr;
00609 }
00610 
00611 /// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified
00612 /// value will trap if the value is dynamically null.  PHIs keeps track of any
00613 /// phi nodes we've seen to avoid reprocessing them.
00614 static bool AllUsesOfValueWillTrapIfNull(const Value *V,
00615                                          SmallPtrSet<const PHINode*, 8> &PHIs) {
00616   for (const User *U : V->users())
00617     if (isa<LoadInst>(U)) {
00618       // Will trap.
00619     } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) {
00620       if (SI->getOperand(0) == V) {
00621         //cerr << "NONTRAPPING USE: " << *U;
00622         return false;  // Storing the value.
00623       }
00624     } else if (const CallInst *CI = dyn_cast<CallInst>(U)) {
00625       if (CI->getCalledValue() != V) {
00626         //cerr << "NONTRAPPING USE: " << *U;
00627         return false;  // Not calling the ptr
00628       }
00629     } else if (const InvokeInst *II = dyn_cast<InvokeInst>(U)) {
00630       if (II->getCalledValue() != V) {
00631         //cerr << "NONTRAPPING USE: " << *U;
00632         return false;  // Not calling the ptr
00633       }
00634     } else if (const BitCastInst *CI = dyn_cast<BitCastInst>(U)) {
00635       if (!AllUsesOfValueWillTrapIfNull(CI, PHIs)) return false;
00636     } else if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
00637       if (!AllUsesOfValueWillTrapIfNull(GEPI, PHIs)) return false;
00638     } else if (const PHINode *PN = dyn_cast<PHINode>(U)) {
00639       // If we've already seen this phi node, ignore it, it has already been
00640       // checked.
00641       if (PHIs.insert(PN) && !AllUsesOfValueWillTrapIfNull(PN, PHIs))
00642         return false;
00643     } else if (isa<ICmpInst>(U) &&
00644                isa<ConstantPointerNull>(U->getOperand(1))) {
00645       // Ignore icmp X, null
00646     } else {
00647       //cerr << "NONTRAPPING USE: " << *U;
00648       return false;
00649     }
00650 
00651   return true;
00652 }
00653 
00654 /// AllUsesOfLoadedValueWillTrapIfNull - Return true if all uses of any loads
00655 /// from GV will trap if the loaded value is null.  Note that this also permits
00656 /// comparisons of the loaded value against null, as a special case.
00657 static bool AllUsesOfLoadedValueWillTrapIfNull(const GlobalVariable *GV) {
00658   for (const User *U : GV->users())
00659     if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
00660       SmallPtrSet<const PHINode*, 8> PHIs;
00661       if (!AllUsesOfValueWillTrapIfNull(LI, PHIs))
00662         return false;
00663     } else if (isa<StoreInst>(U)) {
00664       // Ignore stores to the global.
00665     } else {
00666       // We don't know or understand this user, bail out.
00667       //cerr << "UNKNOWN USER OF GLOBAL!: " << *U;
00668       return false;
00669     }
00670   return true;
00671 }
00672 
00673 static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) {
00674   bool Changed = false;
00675   for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) {
00676     Instruction *I = cast<Instruction>(*UI++);
00677     if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
00678       LI->setOperand(0, NewV);
00679       Changed = true;
00680     } else if (StoreInst *SI = dyn_cast<StoreInst>(I)) {
00681       if (SI->getOperand(1) == V) {
00682         SI->setOperand(1, NewV);
00683         Changed = true;
00684       }
00685     } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
00686       CallSite CS(I);
00687       if (CS.getCalledValue() == V) {
00688         // Calling through the pointer!  Turn into a direct call, but be careful
00689         // that the pointer is not also being passed as an argument.
00690         CS.setCalledFunction(NewV);
00691         Changed = true;
00692         bool PassedAsArg = false;
00693         for (unsigned i = 0, e = CS.arg_size(); i != e; ++i)
00694           if (CS.getArgument(i) == V) {
00695             PassedAsArg = true;
00696             CS.setArgument(i, NewV);
00697           }
00698 
00699         if (PassedAsArg) {
00700           // Being passed as an argument also.  Be careful to not invalidate UI!
00701           UI = V->user_begin();
00702         }
00703       }
00704     } else if (CastInst *CI = dyn_cast<CastInst>(I)) {
00705       Changed |= OptimizeAwayTrappingUsesOfValue(CI,
00706                                 ConstantExpr::getCast(CI->getOpcode(),
00707                                                       NewV, CI->getType()));
00708       if (CI->use_empty()) {
00709         Changed = true;
00710         CI->eraseFromParent();
00711       }
00712     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I)) {
00713       // Should handle GEP here.
00714       SmallVector<Constant*, 8> Idxs;
00715       Idxs.reserve(GEPI->getNumOperands()-1);
00716       for (User::op_iterator i = GEPI->op_begin() + 1, e = GEPI->op_end();
00717            i != e; ++i)
00718         if (Constant *C = dyn_cast<Constant>(*i))
00719           Idxs.push_back(C);
00720         else
00721           break;
00722       if (Idxs.size() == GEPI->getNumOperands()-1)
00723         Changed |= OptimizeAwayTrappingUsesOfValue(GEPI,
00724                           ConstantExpr::getGetElementPtr(NewV, Idxs));
00725       if (GEPI->use_empty()) {
00726         Changed = true;
00727         GEPI->eraseFromParent();
00728       }
00729     }
00730   }
00731 
00732   return Changed;
00733 }
00734 
00735 
00736 /// OptimizeAwayTrappingUsesOfLoads - The specified global has only one non-null
00737 /// value stored into it.  If there are uses of the loaded value that would trap
00738 /// if the loaded value is dynamically null, then we know that they cannot be
00739 /// reachable with a null optimize away the load.
00740 static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV,
00741                                             const DataLayout *DL,
00742                                             TargetLibraryInfo *TLI) {
00743   bool Changed = false;
00744 
00745   // Keep track of whether we are able to remove all the uses of the global
00746   // other than the store that defines it.
00747   bool AllNonStoreUsesGone = true;
00748 
00749   // Replace all uses of loads with uses of uses of the stored value.
00750   for (Value::user_iterator GUI = GV->user_begin(), E = GV->user_end(); GUI != E;){
00751     User *GlobalUser = *GUI++;
00752     if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) {
00753       Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV);
00754       // If we were able to delete all uses of the loads
00755       if (LI->use_empty()) {
00756         LI->eraseFromParent();
00757         Changed = true;
00758       } else {
00759         AllNonStoreUsesGone = false;
00760       }
00761     } else if (isa<StoreInst>(GlobalUser)) {
00762       // Ignore the store that stores "LV" to the global.
00763       assert(GlobalUser->getOperand(1) == GV &&
00764              "Must be storing *to* the global");
00765     } else {
00766       AllNonStoreUsesGone = false;
00767 
00768       // If we get here we could have other crazy uses that are transitively
00769       // loaded.
00770       assert((isa<PHINode>(GlobalUser) || isa<SelectInst>(GlobalUser) ||
00771               isa<ConstantExpr>(GlobalUser) || isa<CmpInst>(GlobalUser) ||
00772               isa<BitCastInst>(GlobalUser) ||
00773               isa<GetElementPtrInst>(GlobalUser)) &&
00774              "Only expect load and stores!");
00775     }
00776   }
00777 
00778   if (Changed) {
00779     DEBUG(dbgs() << "OPTIMIZED LOADS FROM STORED ONCE POINTER: " << *GV);
00780     ++NumGlobUses;
00781   }
00782 
00783   // If we nuked all of the loads, then none of the stores are needed either,
00784   // nor is the global.
00785   if (AllNonStoreUsesGone) {
00786     if (isLeakCheckerRoot(GV)) {
00787       Changed |= CleanupPointerRootUsers(GV, TLI);
00788     } else {
00789       Changed = true;
00790       CleanupConstantGlobalUsers(GV, nullptr, DL, TLI);
00791     }
00792     if (GV->use_empty()) {
00793       DEBUG(dbgs() << "  *** GLOBAL NOW DEAD!\n");
00794       Changed = true;
00795       GV->eraseFromParent();
00796       ++NumDeleted;
00797     }
00798   }
00799   return Changed;
00800 }
00801 
00802 /// ConstantPropUsersOf - Walk the use list of V, constant folding all of the
00803 /// instructions that are foldable.
00804 static void ConstantPropUsersOf(Value *V, const DataLayout *DL,
00805                                 TargetLibraryInfo *TLI) {
00806   for (Value::user_iterator UI = V->user_begin(), E = V->user_end(); UI != E; )
00807     if (Instruction *I = dyn_cast<Instruction>(*UI++))
00808       if (Constant *NewC = ConstantFoldInstruction(I, DL, TLI)) {
00809         I->replaceAllUsesWith(NewC);
00810 
00811         // Advance UI to the next non-I use to avoid invalidating it!
00812         // Instructions could multiply use V.
00813         while (UI != E && *UI == I)
00814           ++UI;
00815         I->eraseFromParent();
00816       }
00817 }
00818 
00819 /// OptimizeGlobalAddressOfMalloc - This function takes the specified global
00820 /// variable, and transforms the program as if it always contained the result of
00821 /// the specified malloc.  Because it is always the result of the specified
00822 /// malloc, there is no reason to actually DO the malloc.  Instead, turn the
00823 /// malloc into a global, and any loads of GV as uses of the new global.
00824 static GlobalVariable *OptimizeGlobalAddressOfMalloc(GlobalVariable *GV,
00825                                                      CallInst *CI,
00826                                                      Type *AllocTy,
00827                                                      ConstantInt *NElements,
00828                                                      const DataLayout *DL,
00829                                                      TargetLibraryInfo *TLI) {
00830   DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << "  CALL = " << *CI << '\n');
00831 
00832   Type *GlobalType;
00833   if (NElements->getZExtValue() == 1)
00834     GlobalType = AllocTy;
00835   else
00836     // If we have an array allocation, the global variable is of an array.
00837     GlobalType = ArrayType::get(AllocTy, NElements->getZExtValue());
00838 
00839   // Create the new global variable.  The contents of the malloc'd memory is
00840   // undefined, so initialize with an undef value.
00841   GlobalVariable *NewGV = new GlobalVariable(*GV->getParent(),
00842                                              GlobalType, false,
00843                                              GlobalValue::InternalLinkage,
00844                                              UndefValue::get(GlobalType),
00845                                              GV->getName()+".body",
00846                                              GV,
00847                                              GV->getThreadLocalMode());
00848 
00849   // If there are bitcast users of the malloc (which is typical, usually we have
00850   // a malloc + bitcast) then replace them with uses of the new global.  Update
00851   // other users to use the global as well.
00852   BitCastInst *TheBC = nullptr;
00853   while (!CI->use_empty()) {
00854     Instruction *User = cast<Instruction>(CI->user_back());
00855     if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) {
00856       if (BCI->getType() == NewGV->getType()) {
00857         BCI->replaceAllUsesWith(NewGV);
00858         BCI->eraseFromParent();
00859       } else {
00860         BCI->setOperand(0, NewGV);
00861       }
00862     } else {
00863       if (!TheBC)
00864         TheBC = new BitCastInst(NewGV, CI->getType(), "newgv", CI);
00865       User->replaceUsesOfWith(CI, TheBC);
00866     }
00867   }
00868 
00869   Constant *RepValue = NewGV;
00870   if (NewGV->getType() != GV->getType()->getElementType())
00871     RepValue = ConstantExpr::getBitCast(RepValue,
00872                                         GV->getType()->getElementType());
00873 
00874   // If there is a comparison against null, we will insert a global bool to
00875   // keep track of whether the global was initialized yet or not.
00876   GlobalVariable *InitBool =
00877     new GlobalVariable(Type::getInt1Ty(GV->getContext()), false,
00878                        GlobalValue::InternalLinkage,
00879                        ConstantInt::getFalse(GV->getContext()),
00880                        GV->getName()+".init", GV->getThreadLocalMode());
00881   bool InitBoolUsed = false;
00882 
00883   // Loop over all uses of GV, processing them in turn.
00884   while (!GV->use_empty()) {
00885     if (StoreInst *SI = dyn_cast<StoreInst>(GV->user_back())) {
00886       // The global is initialized when the store to it occurs.
00887       new StoreInst(ConstantInt::getTrue(GV->getContext()), InitBool, false, 0,
00888                     SI->getOrdering(), SI->getSynchScope(), SI);
00889       SI->eraseFromParent();
00890       continue;
00891     }
00892 
00893     LoadInst *LI = cast<LoadInst>(GV->user_back());
00894     while (!LI->use_empty()) {
00895       Use &LoadUse = *LI->use_begin();
00896       ICmpInst *ICI = dyn_cast<ICmpInst>(LoadUse.getUser());
00897       if (!ICI) {
00898         LoadUse = RepValue;
00899         continue;
00900       }
00901 
00902       // Replace the cmp X, 0 with a use of the bool value.
00903       // Sink the load to where the compare was, if atomic rules allow us to.
00904       Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", false, 0,
00905                                LI->getOrdering(), LI->getSynchScope(),
00906                                LI->isUnordered() ? (Instruction*)ICI : LI);
00907       InitBoolUsed = true;
00908       switch (ICI->getPredicate()) {
00909       default: llvm_unreachable("Unknown ICmp Predicate!");
00910       case ICmpInst::ICMP_ULT:
00911       case ICmpInst::ICMP_SLT:   // X < null -> always false
00912         LV = ConstantInt::getFalse(GV->getContext());
00913         break;
00914       case ICmpInst::ICMP_ULE:
00915       case ICmpInst::ICMP_SLE:
00916       case ICmpInst::ICMP_EQ:
00917         LV = BinaryOperator::CreateNot(LV, "notinit", ICI);
00918         break;
00919       case ICmpInst::ICMP_NE:
00920       case ICmpInst::ICMP_UGE:
00921       case ICmpInst::ICMP_SGE:
00922       case ICmpInst::ICMP_UGT:
00923       case ICmpInst::ICMP_SGT:
00924         break;  // no change.
00925       }
00926       ICI->replaceAllUsesWith(LV);
00927       ICI->eraseFromParent();
00928     }
00929     LI->eraseFromParent();
00930   }
00931 
00932   // If the initialization boolean was used, insert it, otherwise delete it.
00933   if (!InitBoolUsed) {
00934     while (!InitBool->use_empty())  // Delete initializations
00935       cast<StoreInst>(InitBool->user_back())->eraseFromParent();
00936     delete InitBool;
00937   } else
00938     GV->getParent()->getGlobalList().insert(GV, InitBool);
00939 
00940   // Now the GV is dead, nuke it and the malloc..
00941   GV->eraseFromParent();
00942   CI->eraseFromParent();
00943 
00944   // To further other optimizations, loop over all users of NewGV and try to
00945   // constant prop them.  This will promote GEP instructions with constant
00946   // indices into GEP constant-exprs, which will allow global-opt to hack on it.
00947   ConstantPropUsersOf(NewGV, DL, TLI);
00948   if (RepValue != NewGV)
00949     ConstantPropUsersOf(RepValue, DL, TLI);
00950 
00951   return NewGV;
00952 }
00953 
00954 /// ValueIsOnlyUsedLocallyOrStoredToOneGlobal - Scan the use-list of V checking
00955 /// to make sure that there are no complex uses of V.  We permit simple things
00956 /// like dereferencing the pointer, but not storing through the address, unless
00957 /// it is to the specified global.
00958 static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(const Instruction *V,
00959                                                       const GlobalVariable *GV,
00960                                          SmallPtrSet<const PHINode*, 8> &PHIs) {
00961   for (const User *U : V->users()) {
00962     const Instruction *Inst = cast<Instruction>(U);
00963 
00964     if (isa<LoadInst>(Inst) || isa<CmpInst>(Inst)) {
00965       continue; // Fine, ignore.
00966     }
00967 
00968     if (const StoreInst *SI = dyn_cast<StoreInst>(Inst)) {
00969       if (SI->getOperand(0) == V && SI->getOperand(1) != GV)
00970         return false;  // Storing the pointer itself... bad.
00971       continue; // Otherwise, storing through it, or storing into GV... fine.
00972     }
00973 
00974     // Must index into the array and into the struct.
00975     if (isa<GetElementPtrInst>(Inst) && Inst->getNumOperands() >= 3) {
00976       if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(Inst, GV, PHIs))
00977         return false;
00978       continue;
00979     }
00980 
00981     if (const PHINode *PN = dyn_cast<PHINode>(Inst)) {
00982       // PHIs are ok if all uses are ok.  Don't infinitely recurse through PHI
00983       // cycles.
00984       if (PHIs.insert(PN))
00985         if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(PN, GV, PHIs))
00986           return false;
00987       continue;
00988     }
00989 
00990     if (const BitCastInst *BCI = dyn_cast<BitCastInst>(Inst)) {
00991       if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(BCI, GV, PHIs))
00992         return false;
00993       continue;
00994     }
00995 
00996     return false;
00997   }
00998   return true;
00999 }
01000 
01001 /// ReplaceUsesOfMallocWithGlobal - The Alloc pointer is stored into GV
01002 /// somewhere.  Transform all uses of the allocation into loads from the
01003 /// global and uses of the resultant pointer.  Further, delete the store into
01004 /// GV.  This assumes that these value pass the
01005 /// 'ValueIsOnlyUsedLocallyOrStoredToOneGlobal' predicate.
01006 static void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc,
01007                                           GlobalVariable *GV) {
01008   while (!Alloc->use_empty()) {
01009     Instruction *U = cast<Instruction>(*Alloc->user_begin());
01010     Instruction *InsertPt = U;
01011     if (StoreInst *SI = dyn_cast<StoreInst>(U)) {
01012       // If this is the store of the allocation into the global, remove it.
01013       if (SI->getOperand(1) == GV) {
01014         SI->eraseFromParent();
01015         continue;
01016       }
01017     } else if (PHINode *PN = dyn_cast<PHINode>(U)) {
01018       // Insert the load in the corresponding predecessor, not right before the
01019       // PHI.
01020       InsertPt = PN->getIncomingBlock(*Alloc->use_begin())->getTerminator();
01021     } else if (isa<BitCastInst>(U)) {
01022       // Must be bitcast between the malloc and store to initialize the global.
01023       ReplaceUsesOfMallocWithGlobal(U, GV);
01024       U->eraseFromParent();
01025       continue;
01026     } else if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(U)) {
01027       // If this is a "GEP bitcast" and the user is a store to the global, then
01028       // just process it as a bitcast.
01029       if (GEPI->hasAllZeroIndices() && GEPI->hasOneUse())
01030         if (StoreInst *SI = dyn_cast<StoreInst>(GEPI->user_back()))
01031           if (SI->getOperand(1) == GV) {
01032             // Must be bitcast GEP between the malloc and store to initialize
01033             // the global.
01034             ReplaceUsesOfMallocWithGlobal(GEPI, GV);
01035             GEPI->eraseFromParent();
01036             continue;
01037           }
01038     }
01039 
01040     // Insert a load from the global, and use it instead of the malloc.
01041     Value *NL = new LoadInst(GV, GV->getName()+".val", InsertPt);
01042     U->replaceUsesOfWith(Alloc, NL);
01043   }
01044 }
01045 
01046 /// LoadUsesSimpleEnoughForHeapSRA - Verify that all uses of V (a load, or a phi
01047 /// of a load) are simple enough to perform heap SRA on.  This permits GEP's
01048 /// that index through the array and struct field, icmps of null, and PHIs.
01049 static bool LoadUsesSimpleEnoughForHeapSRA(const Value *V,
01050                         SmallPtrSet<const PHINode*, 32> &LoadUsingPHIs,
01051                         SmallPtrSet<const PHINode*, 32> &LoadUsingPHIsPerLoad) {
01052   // We permit two users of the load: setcc comparing against the null
01053   // pointer, and a getelementptr of a specific form.
01054   for (const User *U : V->users()) {
01055     const Instruction *UI = cast<Instruction>(U);
01056 
01057     // Comparison against null is ok.
01058     if (const ICmpInst *ICI = dyn_cast<ICmpInst>(UI)) {
01059       if (!isa<ConstantPointerNull>(ICI->getOperand(1)))
01060         return false;
01061       continue;
01062     }
01063 
01064     // getelementptr is also ok, but only a simple form.
01065     if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(UI)) {
01066       // Must index into the array and into the struct.
01067       if (GEPI->getNumOperands() < 3)
01068         return false;
01069 
01070       // Otherwise the GEP is ok.
01071       continue;
01072     }
01073 
01074     if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
01075       if (!LoadUsingPHIsPerLoad.insert(PN))
01076         // This means some phi nodes are dependent on each other.
01077         // Avoid infinite looping!
01078         return false;
01079       if (!LoadUsingPHIs.insert(PN))
01080         // If we have already analyzed this PHI, then it is safe.
01081         continue;
01082 
01083       // Make sure all uses of the PHI are simple enough to transform.
01084       if (!LoadUsesSimpleEnoughForHeapSRA(PN,
01085                                           LoadUsingPHIs, LoadUsingPHIsPerLoad))
01086         return false;
01087 
01088       continue;
01089     }
01090 
01091     // Otherwise we don't know what this is, not ok.
01092     return false;
01093   }
01094 
01095   return true;
01096 }
01097 
01098 
01099 /// AllGlobalLoadUsesSimpleEnoughForHeapSRA - If all users of values loaded from
01100 /// GV are simple enough to perform HeapSRA, return true.
01101 static bool AllGlobalLoadUsesSimpleEnoughForHeapSRA(const GlobalVariable *GV,
01102                                                     Instruction *StoredVal) {
01103   SmallPtrSet<const PHINode*, 32> LoadUsingPHIs;
01104   SmallPtrSet<const PHINode*, 32> LoadUsingPHIsPerLoad;
01105   for (const User *U : GV->users())
01106     if (const LoadInst *LI = dyn_cast<LoadInst>(U)) {
01107       if (!LoadUsesSimpleEnoughForHeapSRA(LI, LoadUsingPHIs,
01108                                           LoadUsingPHIsPerLoad))
01109         return false;
01110       LoadUsingPHIsPerLoad.clear();
01111     }
01112 
01113   // If we reach here, we know that all uses of the loads and transitive uses
01114   // (through PHI nodes) are simple enough to transform.  However, we don't know
01115   // that all inputs the to the PHI nodes are in the same equivalence sets.
01116   // Check to verify that all operands of the PHIs are either PHIS that can be
01117   // transformed, loads from GV, or MI itself.
01118   for (SmallPtrSet<const PHINode*, 32>::const_iterator I = LoadUsingPHIs.begin()
01119        , E = LoadUsingPHIs.end(); I != E; ++I) {
01120     const PHINode *PN = *I;
01121     for (unsigned op = 0, e = PN->getNumIncomingValues(); op != e; ++op) {
01122       Value *InVal = PN->getIncomingValue(op);
01123 
01124       // PHI of the stored value itself is ok.
01125       if (InVal == StoredVal) continue;
01126 
01127       if (const PHINode *InPN = dyn_cast<PHINode>(InVal)) {
01128         // One of the PHIs in our set is (optimistically) ok.
01129         if (LoadUsingPHIs.count(InPN))
01130           continue;
01131         return false;
01132       }
01133 
01134       // Load from GV is ok.
01135       if (const LoadInst *LI = dyn_cast<LoadInst>(InVal))
01136         if (LI->getOperand(0) == GV)
01137           continue;
01138 
01139       // UNDEF? NULL?
01140 
01141       // Anything else is rejected.
01142       return false;
01143     }
01144   }
01145 
01146   return true;
01147 }
01148 
01149 static Value *GetHeapSROAValue(Value *V, unsigned FieldNo,
01150                DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues,
01151                    std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) {
01152   std::vector<Value*> &FieldVals = InsertedScalarizedValues[V];
01153 
01154   if (FieldNo >= FieldVals.size())
01155     FieldVals.resize(FieldNo+1);
01156 
01157   // If we already have this value, just reuse the previously scalarized
01158   // version.
01159   if (Value *FieldVal = FieldVals[FieldNo])
01160     return FieldVal;
01161 
01162   // Depending on what instruction this is, we have several cases.
01163   Value *Result;
01164   if (LoadInst *LI = dyn_cast<LoadInst>(V)) {
01165     // This is a scalarized version of the load from the global.  Just create
01166     // a new Load of the scalarized global.
01167     Result = new LoadInst(GetHeapSROAValue(LI->getOperand(0), FieldNo,
01168                                            InsertedScalarizedValues,
01169                                            PHIsToRewrite),
01170                           LI->getName()+".f"+Twine(FieldNo), LI);
01171   } else if (PHINode *PN = dyn_cast<PHINode>(V)) {
01172     // PN's type is pointer to struct.  Make a new PHI of pointer to struct
01173     // field.
01174 
01175     PointerType *PTy = cast<PointerType>(PN->getType());
01176     StructType *ST = cast<StructType>(PTy->getElementType());
01177 
01178     unsigned AS = PTy->getAddressSpace();
01179     PHINode *NewPN =
01180       PHINode::Create(PointerType::get(ST->getElementType(FieldNo), AS),
01181                      PN->getNumIncomingValues(),
01182                      PN->getName()+".f"+Twine(FieldNo), PN);
01183     Result = NewPN;
01184     PHIsToRewrite.push_back(std::make_pair(PN, FieldNo));
01185   } else {
01186     llvm_unreachable("Unknown usable value");
01187   }
01188 
01189   return FieldVals[FieldNo] = Result;
01190 }
01191 
01192 /// RewriteHeapSROALoadUser - Given a load instruction and a value derived from
01193 /// the load, rewrite the derived value to use the HeapSRoA'd load.
01194 static void RewriteHeapSROALoadUser(Instruction *LoadUser,
01195              DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues,
01196                    std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) {
01197   // If this is a comparison against null, handle it.
01198   if (ICmpInst *SCI = dyn_cast<ICmpInst>(LoadUser)) {
01199     assert(isa<ConstantPointerNull>(SCI->getOperand(1)));
01200     // If we have a setcc of the loaded pointer, we can use a setcc of any
01201     // field.
01202     Value *NPtr = GetHeapSROAValue(SCI->getOperand(0), 0,
01203                                    InsertedScalarizedValues, PHIsToRewrite);
01204 
01205     Value *New = new ICmpInst(SCI, SCI->getPredicate(), NPtr,
01206                               Constant::getNullValue(NPtr->getType()),
01207                               SCI->getName());
01208     SCI->replaceAllUsesWith(New);
01209     SCI->eraseFromParent();
01210     return;
01211   }
01212 
01213   // Handle 'getelementptr Ptr, Idx, i32 FieldNo ...'
01214   if (GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(LoadUser)) {
01215     assert(GEPI->getNumOperands() >= 3 && isa<ConstantInt>(GEPI->getOperand(2))
01216            && "Unexpected GEPI!");
01217 
01218     // Load the pointer for this field.
01219     unsigned FieldNo = cast<ConstantInt>(GEPI->getOperand(2))->getZExtValue();
01220     Value *NewPtr = GetHeapSROAValue(GEPI->getOperand(0), FieldNo,
01221                                      InsertedScalarizedValues, PHIsToRewrite);
01222 
01223     // Create the new GEP idx vector.
01224     SmallVector<Value*, 8> GEPIdx;
01225     GEPIdx.push_back(GEPI->getOperand(1));
01226     GEPIdx.append(GEPI->op_begin()+3, GEPI->op_end());
01227 
01228     Value *NGEPI = GetElementPtrInst::Create(NewPtr, GEPIdx,
01229                                              GEPI->getName(), GEPI);
01230     GEPI->replaceAllUsesWith(NGEPI);
01231     GEPI->eraseFromParent();
01232     return;
01233   }
01234 
01235   // Recursively transform the users of PHI nodes.  This will lazily create the
01236   // PHIs that are needed for individual elements.  Keep track of what PHIs we
01237   // see in InsertedScalarizedValues so that we don't get infinite loops (very
01238   // antisocial).  If the PHI is already in InsertedScalarizedValues, it has
01239   // already been seen first by another load, so its uses have already been
01240   // processed.
01241   PHINode *PN = cast<PHINode>(LoadUser);
01242   if (!InsertedScalarizedValues.insert(std::make_pair(PN,
01243                                               std::vector<Value*>())).second)
01244     return;
01245 
01246   // If this is the first time we've seen this PHI, recursively process all
01247   // users.
01248   for (auto UI = PN->user_begin(), E = PN->user_end(); UI != E;) {
01249     Instruction *User = cast<Instruction>(*UI++);
01250     RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite);
01251   }
01252 }
01253 
01254 /// RewriteUsesOfLoadForHeapSRoA - We are performing Heap SRoA on a global.  Ptr
01255 /// is a value loaded from the global.  Eliminate all uses of Ptr, making them
01256 /// use FieldGlobals instead.  All uses of loaded values satisfy
01257 /// AllGlobalLoadUsesSimpleEnoughForHeapSRA.
01258 static void RewriteUsesOfLoadForHeapSRoA(LoadInst *Load,
01259                DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues,
01260                    std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) {
01261   for (auto UI = Load->user_begin(), E = Load->user_end(); UI != E;) {
01262     Instruction *User = cast<Instruction>(*UI++);
01263     RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite);
01264   }
01265 
01266   if (Load->use_empty()) {
01267     Load->eraseFromParent();
01268     InsertedScalarizedValues.erase(Load);
01269   }
01270 }
01271 
01272 /// PerformHeapAllocSRoA - CI is an allocation of an array of structures.  Break
01273 /// it up into multiple allocations of arrays of the fields.
01274 static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, CallInst *CI,
01275                                             Value *NElems, const DataLayout *DL,
01276                                             const TargetLibraryInfo *TLI) {
01277   DEBUG(dbgs() << "SROA HEAP ALLOC: " << *GV << "  MALLOC = " << *CI << '\n');
01278   Type *MAT = getMallocAllocatedType(CI, TLI);
01279   StructType *STy = cast<StructType>(MAT);
01280 
01281   // There is guaranteed to be at least one use of the malloc (storing
01282   // it into GV).  If there are other uses, change them to be uses of
01283   // the global to simplify later code.  This also deletes the store
01284   // into GV.
01285   ReplaceUsesOfMallocWithGlobal(CI, GV);
01286 
01287   // Okay, at this point, there are no users of the malloc.  Insert N
01288   // new mallocs at the same place as CI, and N globals.
01289   std::vector<Value*> FieldGlobals;
01290   std::vector<Value*> FieldMallocs;
01291 
01292   unsigned AS = GV->getType()->getPointerAddressSpace();
01293   for (unsigned FieldNo = 0, e = STy->getNumElements(); FieldNo != e;++FieldNo){
01294     Type *FieldTy = STy->getElementType(FieldNo);
01295     PointerType *PFieldTy = PointerType::get(FieldTy, AS);
01296 
01297     GlobalVariable *NGV =
01298       new GlobalVariable(*GV->getParent(),
01299                          PFieldTy, false, GlobalValue::InternalLinkage,
01300                          Constant::getNullValue(PFieldTy),
01301                          GV->getName() + ".f" + Twine(FieldNo), GV,
01302                          GV->getThreadLocalMode());
01303     FieldGlobals.push_back(NGV);
01304 
01305     unsigned TypeSize = DL->getTypeAllocSize(FieldTy);
01306     if (StructType *ST = dyn_cast<StructType>(FieldTy))
01307       TypeSize = DL->getStructLayout(ST)->getSizeInBytes();
01308     Type *IntPtrTy = DL->getIntPtrType(CI->getType());
01309     Value *NMI = CallInst::CreateMalloc(CI, IntPtrTy, FieldTy,
01310                                         ConstantInt::get(IntPtrTy, TypeSize),
01311                                         NElems, nullptr,
01312                                         CI->getName() + ".f" + Twine(FieldNo));
01313     FieldMallocs.push_back(NMI);
01314     new StoreInst(NMI, NGV, CI);
01315   }
01316 
01317   // The tricky aspect of this transformation is handling the case when malloc
01318   // fails.  In the original code, malloc failing would set the result pointer
01319   // of malloc to null.  In this case, some mallocs could succeed and others
01320   // could fail.  As such, we emit code that looks like this:
01321   //    F0 = malloc(field0)
01322   //    F1 = malloc(field1)
01323   //    F2 = malloc(field2)
01324   //    if (F0 == 0 || F1 == 0 || F2 == 0) {
01325   //      if (F0) { free(F0); F0 = 0; }
01326   //      if (F1) { free(F1); F1 = 0; }
01327   //      if (F2) { free(F2); F2 = 0; }
01328   //    }
01329   // The malloc can also fail if its argument is too large.
01330   Constant *ConstantZero = ConstantInt::get(CI->getArgOperand(0)->getType(), 0);
01331   Value *RunningOr = new ICmpInst(CI, ICmpInst::ICMP_SLT, CI->getArgOperand(0),
01332                                   ConstantZero, "isneg");
01333   for (unsigned i = 0, e = FieldMallocs.size(); i != e; ++i) {
01334     Value *Cond = new ICmpInst(CI, ICmpInst::ICMP_EQ, FieldMallocs[i],
01335                              Constant::getNullValue(FieldMallocs[i]->getType()),
01336                                "isnull");
01337     RunningOr = BinaryOperator::CreateOr(RunningOr, Cond, "tmp", CI);
01338   }
01339 
01340   // Split the basic block at the old malloc.
01341   BasicBlock *OrigBB = CI->getParent();
01342   BasicBlock *ContBB = OrigBB->splitBasicBlock(CI, "malloc_cont");
01343 
01344   // Create the block to check the first condition.  Put all these blocks at the
01345   // end of the function as they are unlikely to be executed.
01346   BasicBlock *NullPtrBlock = BasicBlock::Create(OrigBB->getContext(),
01347                                                 "malloc_ret_null",
01348                                                 OrigBB->getParent());
01349 
01350   // Remove the uncond branch from OrigBB to ContBB, turning it into a cond
01351   // branch on RunningOr.
01352   OrigBB->getTerminator()->eraseFromParent();
01353   BranchInst::Create(NullPtrBlock, ContBB, RunningOr, OrigBB);
01354 
01355   // Within the NullPtrBlock, we need to emit a comparison and branch for each
01356   // pointer, because some may be null while others are not.
01357   for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) {
01358     Value *GVVal = new LoadInst(FieldGlobals[i], "tmp", NullPtrBlock);
01359     Value *Cmp = new ICmpInst(*NullPtrBlock, ICmpInst::ICMP_NE, GVVal,
01360                               Constant::getNullValue(GVVal->getType()));
01361     BasicBlock *FreeBlock = BasicBlock::Create(Cmp->getContext(), "free_it",
01362                                                OrigBB->getParent());
01363     BasicBlock *NextBlock = BasicBlock::Create(Cmp->getContext(), "next",
01364                                                OrigBB->getParent());
01365     Instruction *BI = BranchInst::Create(FreeBlock, NextBlock,
01366                                          Cmp, NullPtrBlock);
01367 
01368     // Fill in FreeBlock.
01369     CallInst::CreateFree(GVVal, BI);
01370     new StoreInst(Constant::getNullValue(GVVal->getType()), FieldGlobals[i],
01371                   FreeBlock);
01372     BranchInst::Create(NextBlock, FreeBlock);
01373 
01374     NullPtrBlock = NextBlock;
01375   }
01376 
01377   BranchInst::Create(ContBB, NullPtrBlock);
01378 
01379   // CI is no longer needed, remove it.
01380   CI->eraseFromParent();
01381 
01382   /// InsertedScalarizedLoads - As we process loads, if we can't immediately
01383   /// update all uses of the load, keep track of what scalarized loads are
01384   /// inserted for a given load.
01385   DenseMap<Value*, std::vector<Value*> > InsertedScalarizedValues;
01386   InsertedScalarizedValues[GV] = FieldGlobals;
01387 
01388   std::vector<std::pair<PHINode*, unsigned> > PHIsToRewrite;
01389 
01390   // Okay, the malloc site is completely handled.  All of the uses of GV are now
01391   // loads, and all uses of those loads are simple.  Rewrite them to use loads
01392   // of the per-field globals instead.
01393   for (auto UI = GV->user_begin(), E = GV->user_end(); UI != E;) {
01394     Instruction *User = cast<Instruction>(*UI++);
01395 
01396     if (LoadInst *LI = dyn_cast<LoadInst>(User)) {
01397       RewriteUsesOfLoadForHeapSRoA(LI, InsertedScalarizedValues, PHIsToRewrite);
01398       continue;
01399     }
01400 
01401     // Must be a store of null.
01402     StoreInst *SI = cast<StoreInst>(User);
01403     assert(isa<ConstantPointerNull>(SI->getOperand(0)) &&
01404            "Unexpected heap-sra user!");
01405 
01406     // Insert a store of null into each global.
01407     for (unsigned i = 0, e = FieldGlobals.size(); i != e; ++i) {
01408       PointerType *PT = cast<PointerType>(FieldGlobals[i]->getType());
01409       Constant *Null = Constant::getNullValue(PT->getElementType());
01410       new StoreInst(Null, FieldGlobals[i], SI);
01411     }
01412     // Erase the original store.
01413     SI->eraseFromParent();
01414   }
01415 
01416   // While we have PHIs that are interesting to rewrite, do it.
01417   while (!PHIsToRewrite.empty()) {
01418     PHINode *PN = PHIsToRewrite.back().first;
01419     unsigned FieldNo = PHIsToRewrite.back().second;
01420     PHIsToRewrite.pop_back();
01421     PHINode *FieldPN = cast<PHINode>(InsertedScalarizedValues[PN][FieldNo]);
01422     assert(FieldPN->getNumIncomingValues() == 0 &&"Already processed this phi");
01423 
01424     // Add all the incoming values.  This can materialize more phis.
01425     for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
01426       Value *InVal = PN->getIncomingValue(i);
01427       InVal = GetHeapSROAValue(InVal, FieldNo, InsertedScalarizedValues,
01428                                PHIsToRewrite);
01429       FieldPN->addIncoming(InVal, PN->getIncomingBlock(i));
01430     }
01431   }
01432 
01433   // Drop all inter-phi links and any loads that made it this far.
01434   for (DenseMap<Value*, std::vector<Value*> >::iterator
01435        I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end();
01436        I != E; ++I) {
01437     if (PHINode *PN = dyn_cast<PHINode>(I->first))
01438       PN->dropAllReferences();
01439     else if (LoadInst *LI = dyn_cast<LoadInst>(I->first))
01440       LI->dropAllReferences();
01441   }
01442 
01443   // Delete all the phis and loads now that inter-references are dead.
01444   for (DenseMap<Value*, std::vector<Value*> >::iterator
01445        I = InsertedScalarizedValues.begin(), E = InsertedScalarizedValues.end();
01446        I != E; ++I) {
01447     if (PHINode *PN = dyn_cast<PHINode>(I->first))
01448       PN->eraseFromParent();
01449     else if (LoadInst *LI = dyn_cast<LoadInst>(I->first))
01450       LI->eraseFromParent();
01451   }
01452 
01453   // The old global is now dead, remove it.
01454   GV->eraseFromParent();
01455 
01456   ++NumHeapSRA;
01457   return cast<GlobalVariable>(FieldGlobals[0]);
01458 }
01459 
01460 /// TryToOptimizeStoreOfMallocToGlobal - This function is called when we see a
01461 /// pointer global variable with a single value stored it that is a malloc or
01462 /// cast of malloc.
01463 static bool TryToOptimizeStoreOfMallocToGlobal(GlobalVariable *GV,
01464                                                CallInst *CI,
01465                                                Type *AllocTy,
01466                                                AtomicOrdering Ordering,
01467                                                Module::global_iterator &GVI,
01468                                                const DataLayout *DL,
01469                                                TargetLibraryInfo *TLI) {
01470   if (!DL)
01471     return false;
01472 
01473   // If this is a malloc of an abstract type, don't touch it.
01474   if (!AllocTy->isSized())
01475     return false;
01476 
01477   // We can't optimize this global unless all uses of it are *known* to be
01478   // of the malloc value, not of the null initializer value (consider a use
01479   // that compares the global's value against zero to see if the malloc has
01480   // been reached).  To do this, we check to see if all uses of the global
01481   // would trap if the global were null: this proves that they must all
01482   // happen after the malloc.
01483   if (!AllUsesOfLoadedValueWillTrapIfNull(GV))
01484     return false;
01485 
01486   // We can't optimize this if the malloc itself is used in a complex way,
01487   // for example, being stored into multiple globals.  This allows the
01488   // malloc to be stored into the specified global, loaded icmp'd, and
01489   // GEP'd.  These are all things we could transform to using the global
01490   // for.
01491   SmallPtrSet<const PHINode*, 8> PHIs;
01492   if (!ValueIsOnlyUsedLocallyOrStoredToOneGlobal(CI, GV, PHIs))
01493     return false;
01494 
01495   // If we have a global that is only initialized with a fixed size malloc,
01496   // transform the program to use global memory instead of malloc'd memory.
01497   // This eliminates dynamic allocation, avoids an indirection accessing the
01498   // data, and exposes the resultant global to further GlobalOpt.
01499   // We cannot optimize the malloc if we cannot determine malloc array size.
01500   Value *NElems = getMallocArraySize(CI, DL, TLI, true);
01501   if (!NElems)
01502     return false;
01503 
01504   if (ConstantInt *NElements = dyn_cast<ConstantInt>(NElems))
01505     // Restrict this transformation to only working on small allocations
01506     // (2048 bytes currently), as we don't want to introduce a 16M global or
01507     // something.
01508     if (NElements->getZExtValue() * DL->getTypeAllocSize(AllocTy) < 2048) {
01509       GVI = OptimizeGlobalAddressOfMalloc(GV, CI, AllocTy, NElements, DL, TLI);
01510       return true;
01511     }
01512 
01513   // If the allocation is an array of structures, consider transforming this
01514   // into multiple malloc'd arrays, one for each field.  This is basically
01515   // SRoA for malloc'd memory.
01516 
01517   if (Ordering != NotAtomic)
01518     return false;
01519 
01520   // If this is an allocation of a fixed size array of structs, analyze as a
01521   // variable size array.  malloc [100 x struct],1 -> malloc struct, 100
01522   if (NElems == ConstantInt::get(CI->getArgOperand(0)->getType(), 1))
01523     if (ArrayType *AT = dyn_cast<ArrayType>(AllocTy))
01524       AllocTy = AT->getElementType();
01525 
01526   StructType *AllocSTy = dyn_cast<StructType>(AllocTy);
01527   if (!AllocSTy)
01528     return false;
01529 
01530   // This the structure has an unreasonable number of fields, leave it
01531   // alone.
01532   if (AllocSTy->getNumElements() <= 16 && AllocSTy->getNumElements() != 0 &&
01533       AllGlobalLoadUsesSimpleEnoughForHeapSRA(GV, CI)) {
01534 
01535     // If this is a fixed size array, transform the Malloc to be an alloc of
01536     // structs.  malloc [100 x struct],1 -> malloc struct, 100
01537     if (ArrayType *AT = dyn_cast<ArrayType>(getMallocAllocatedType(CI, TLI))) {
01538       Type *IntPtrTy = DL->getIntPtrType(CI->getType());
01539       unsigned TypeSize = DL->getStructLayout(AllocSTy)->getSizeInBytes();
01540       Value *AllocSize = ConstantInt::get(IntPtrTy, TypeSize);
01541       Value *NumElements = ConstantInt::get(IntPtrTy, AT->getNumElements());
01542       Instruction *Malloc = CallInst::CreateMalloc(CI, IntPtrTy, AllocSTy,
01543                                                    AllocSize, NumElements,
01544                                                    nullptr, CI->getName());
01545       Instruction *Cast = new BitCastInst(Malloc, CI->getType(), "tmp", CI);
01546       CI->replaceAllUsesWith(Cast);
01547       CI->eraseFromParent();
01548       if (BitCastInst *BCI = dyn_cast<BitCastInst>(Malloc))
01549         CI = cast<CallInst>(BCI->getOperand(0));
01550       else
01551         CI = cast<CallInst>(Malloc);
01552     }
01553 
01554     GVI = PerformHeapAllocSRoA(GV, CI, getMallocArraySize(CI, DL, TLI, true),
01555                                DL, TLI);
01556     return true;
01557   }
01558 
01559   return false;
01560 }
01561 
01562 // OptimizeOnceStoredGlobal - Try to optimize globals based on the knowledge
01563 // that only one value (besides its initializer) is ever stored to the global.
01564 static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal,
01565                                      AtomicOrdering Ordering,
01566                                      Module::global_iterator &GVI,
01567                                      const DataLayout *DL,
01568                                      TargetLibraryInfo *TLI) {
01569   // Ignore no-op GEPs and bitcasts.
01570   StoredOnceVal = StoredOnceVal->stripPointerCasts();
01571 
01572   // If we are dealing with a pointer global that is initialized to null and
01573   // only has one (non-null) value stored into it, then we can optimize any
01574   // users of the loaded value (often calls and loads) that would trap if the
01575   // value was null.
01576   if (GV->getInitializer()->getType()->isPointerTy() &&
01577       GV->getInitializer()->isNullValue()) {
01578     if (Constant *SOVC = dyn_cast<Constant>(StoredOnceVal)) {
01579       if (GV->getInitializer()->getType() != SOVC->getType())
01580         SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType());
01581 
01582       // Optimize away any trapping uses of the loaded value.
01583       if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, DL, TLI))
01584         return true;
01585     } else if (CallInst *CI = extractMallocCall(StoredOnceVal, TLI)) {
01586       Type *MallocType = getMallocAllocatedType(CI, TLI);
01587       if (MallocType &&
01588           TryToOptimizeStoreOfMallocToGlobal(GV, CI, MallocType, Ordering, GVI,
01589                                              DL, TLI))
01590         return true;
01591     }
01592   }
01593 
01594   return false;
01595 }
01596 
01597 /// TryToShrinkGlobalToBoolean - At this point, we have learned that the only
01598 /// two values ever stored into GV are its initializer and OtherVal.  See if we
01599 /// can shrink the global into a boolean and select between the two values
01600 /// whenever it is used.  This exposes the values to other scalar optimizations.
01601 static bool TryToShrinkGlobalToBoolean(GlobalVariable *GV, Constant *OtherVal) {
01602   Type *GVElType = GV->getType()->getElementType();
01603 
01604   // If GVElType is already i1, it is already shrunk.  If the type of the GV is
01605   // an FP value, pointer or vector, don't do this optimization because a select
01606   // between them is very expensive and unlikely to lead to later
01607   // simplification.  In these cases, we typically end up with "cond ? v1 : v2"
01608   // where v1 and v2 both require constant pool loads, a big loss.
01609   if (GVElType == Type::getInt1Ty(GV->getContext()) ||
01610       GVElType->isFloatingPointTy() ||
01611       GVElType->isPointerTy() || GVElType->isVectorTy())
01612     return false;
01613 
01614   // Walk the use list of the global seeing if all the uses are load or store.
01615   // If there is anything else, bail out.
01616   for (User *U : GV->users())
01617     if (!isa<LoadInst>(U) && !isa<StoreInst>(U))
01618       return false;
01619 
01620   DEBUG(dbgs() << "   *** SHRINKING TO BOOL: " << *GV);
01621 
01622   // Create the new global, initializing it to false.
01623   GlobalVariable *NewGV = new GlobalVariable(Type::getInt1Ty(GV->getContext()),
01624                                              false,
01625                                              GlobalValue::InternalLinkage,
01626                                         ConstantInt::getFalse(GV->getContext()),
01627                                              GV->getName()+".b",
01628                                              GV->getThreadLocalMode(),
01629                                              GV->getType()->getAddressSpace());
01630   GV->getParent()->getGlobalList().insert(GV, NewGV);
01631 
01632   Constant *InitVal = GV->getInitializer();
01633   assert(InitVal->getType() != Type::getInt1Ty(GV->getContext()) &&
01634          "No reason to shrink to bool!");
01635 
01636   // If initialized to zero and storing one into the global, we can use a cast
01637   // instead of a select to synthesize the desired value.
01638   bool IsOneZero = false;
01639   if (ConstantInt *CI = dyn_cast<ConstantInt>(OtherVal))
01640     IsOneZero = InitVal->isNullValue() && CI->isOne();
01641 
01642   while (!GV->use_empty()) {
01643     Instruction *UI = cast<Instruction>(GV->user_back());
01644     if (StoreInst *SI = dyn_cast<StoreInst>(UI)) {
01645       // Change the store into a boolean store.
01646       bool StoringOther = SI->getOperand(0) == OtherVal;
01647       // Only do this if we weren't storing a loaded value.
01648       Value *StoreVal;
01649       if (StoringOther || SI->getOperand(0) == InitVal) {
01650         StoreVal = ConstantInt::get(Type::getInt1Ty(GV->getContext()),
01651                                     StoringOther);
01652       } else {
01653         // Otherwise, we are storing a previously loaded copy.  To do this,
01654         // change the copy from copying the original value to just copying the
01655         // bool.
01656         Instruction *StoredVal = cast<Instruction>(SI->getOperand(0));
01657 
01658         // If we've already replaced the input, StoredVal will be a cast or
01659         // select instruction.  If not, it will be a load of the original
01660         // global.
01661         if (LoadInst *LI = dyn_cast<LoadInst>(StoredVal)) {
01662           assert(LI->getOperand(0) == GV && "Not a copy!");
01663           // Insert a new load, to preserve the saved value.
01664           StoreVal = new LoadInst(NewGV, LI->getName()+".b", false, 0,
01665                                   LI->getOrdering(), LI->getSynchScope(), LI);
01666         } else {
01667           assert((isa<CastInst>(StoredVal) || isa<SelectInst>(StoredVal)) &&
01668                  "This is not a form that we understand!");
01669           StoreVal = StoredVal->getOperand(0);
01670           assert(isa<LoadInst>(StoreVal) && "Not a load of NewGV!");
01671         }
01672       }
01673       new StoreInst(StoreVal, NewGV, false, 0,
01674                     SI->getOrdering(), SI->getSynchScope(), SI);
01675     } else {
01676       // Change the load into a load of bool then a select.
01677       LoadInst *LI = cast<LoadInst>(UI);
01678       LoadInst *NLI = new LoadInst(NewGV, LI->getName()+".b", false, 0,
01679                                    LI->getOrdering(), LI->getSynchScope(), LI);
01680       Value *NSI;
01681       if (IsOneZero)
01682         NSI = new ZExtInst(NLI, LI->getType(), "", LI);
01683       else
01684         NSI = SelectInst::Create(NLI, OtherVal, InitVal, "", LI);
01685       NSI->takeName(LI);
01686       LI->replaceAllUsesWith(NSI);
01687     }
01688     UI->eraseFromParent();
01689   }
01690 
01691   // Retain the name of the old global variable. People who are debugging their
01692   // programs may expect these variables to be named the same.
01693   NewGV->takeName(GV);
01694   GV->eraseFromParent();
01695   return true;
01696 }
01697 
01698 
01699 /// ProcessGlobal - Analyze the specified global variable and optimize it if
01700 /// possible.  If we make a change, return true.
01701 bool GlobalOpt::ProcessGlobal(GlobalVariable *GV,
01702                               Module::global_iterator &GVI) {
01703   // Do more involved optimizations if the global is internal.
01704   GV->removeDeadConstantUsers();
01705 
01706   if (GV->use_empty()) {
01707     DEBUG(dbgs() << "GLOBAL DEAD: " << *GV);
01708     GV->eraseFromParent();
01709     ++NumDeleted;
01710     return true;
01711   }
01712 
01713   if (!GV->hasLocalLinkage())
01714     return false;
01715 
01716   GlobalStatus GS;
01717 
01718   if (GlobalStatus::analyzeGlobal(GV, GS))
01719     return false;
01720 
01721   if (!GS.IsCompared && !GV->hasUnnamedAddr()) {
01722     GV->setUnnamedAddr(true);
01723     NumUnnamed++;
01724   }
01725 
01726   if (GV->isConstant() || !GV->hasInitializer())
01727     return false;
01728 
01729   return ProcessInternalGlobal(GV, GVI, GS);
01730 }
01731 
01732 /// ProcessInternalGlobal - Analyze the specified global variable and optimize
01733 /// it if possible.  If we make a change, return true.
01734 bool GlobalOpt::ProcessInternalGlobal(GlobalVariable *GV,
01735                                       Module::global_iterator &GVI,
01736                                       const GlobalStatus &GS) {
01737   // If this is a first class global and has only one accessing function
01738   // and this function is main (which we know is not recursive), we replace
01739   // the global with a local alloca in this function.
01740   //
01741   // NOTE: It doesn't make sense to promote non-single-value types since we
01742   // are just replacing static memory to stack memory.
01743   //
01744   // If the global is in different address space, don't bring it to stack.
01745   if (!GS.HasMultipleAccessingFunctions &&
01746       GS.AccessingFunction && !GS.HasNonInstructionUser &&
01747       GV->getType()->getElementType()->isSingleValueType() &&
01748       GS.AccessingFunction->getName() == "main" &&
01749       GS.AccessingFunction->hasExternalLinkage() &&
01750       GV->getType()->getAddressSpace() == 0) {
01751     DEBUG(dbgs() << "LOCALIZING GLOBAL: " << *GV);
01752     Instruction &FirstI = const_cast<Instruction&>(*GS.AccessingFunction
01753                                                    ->getEntryBlock().begin());
01754     Type *ElemTy = GV->getType()->getElementType();
01755     // FIXME: Pass Global's alignment when globals have alignment
01756     AllocaInst *Alloca = new AllocaInst(ElemTy, nullptr,
01757                                         GV->getName(), &FirstI);
01758     if (!isa<UndefValue>(GV->getInitializer()))
01759       new StoreInst(GV->getInitializer(), Alloca, &FirstI);
01760 
01761     GV->replaceAllUsesWith(Alloca);
01762     GV->eraseFromParent();
01763     ++NumLocalized;
01764     return true;
01765   }
01766 
01767   // If the global is never loaded (but may be stored to), it is dead.
01768   // Delete it now.
01769   if (!GS.IsLoaded) {
01770     DEBUG(dbgs() << "GLOBAL NEVER LOADED: " << *GV);
01771 
01772     bool Changed;
01773     if (isLeakCheckerRoot(GV)) {
01774       // Delete any constant stores to the global.
01775       Changed = CleanupPointerRootUsers(GV, TLI);
01776     } else {
01777       // Delete any stores we can find to the global.  We may not be able to
01778       // make it completely dead though.
01779       Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
01780     }
01781 
01782     // If the global is dead now, delete it.
01783     if (GV->use_empty()) {
01784       GV->eraseFromParent();
01785       ++NumDeleted;
01786       Changed = true;
01787     }
01788     return Changed;
01789 
01790   } else if (GS.StoredType <= GlobalStatus::InitializerStored) {
01791     DEBUG(dbgs() << "MARKING CONSTANT: " << *GV << "\n");
01792     GV->setConstant(true);
01793 
01794     // Clean up any obviously simplifiable users now.
01795     CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
01796 
01797     // If the global is dead now, just nuke it.
01798     if (GV->use_empty()) {
01799       DEBUG(dbgs() << "   *** Marking constant allowed us to simplify "
01800             << "all users and delete global!\n");
01801       GV->eraseFromParent();
01802       ++NumDeleted;
01803     }
01804 
01805     ++NumMarked;
01806     return true;
01807   } else if (!GV->getInitializer()->getType()->isSingleValueType()) {
01808     if (DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>()) {
01809       const DataLayout &DL = DLP->getDataLayout();
01810       if (GlobalVariable *FirstNewGV = SRAGlobal(GV, DL)) {
01811         GVI = FirstNewGV;  // Don't skip the newly produced globals!
01812         return true;
01813       }
01814     }
01815   } else if (GS.StoredType == GlobalStatus::StoredOnce) {
01816     // If the initial value for the global was an undef value, and if only
01817     // one other value was stored into it, we can just change the
01818     // initializer to be the stored value, then delete all stores to the
01819     // global.  This allows us to mark it constant.
01820     if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue))
01821       if (isa<UndefValue>(GV->getInitializer())) {
01822         // Change the initial value here.
01823         GV->setInitializer(SOVConstant);
01824 
01825         // Clean up any obviously simplifiable users now.
01826         CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI);
01827 
01828         if (GV->use_empty()) {
01829           DEBUG(dbgs() << "   *** Substituting initializer allowed us to "
01830                        << "simplify all users and delete global!\n");
01831           GV->eraseFromParent();
01832           ++NumDeleted;
01833         } else {
01834           GVI = GV;
01835         }
01836         ++NumSubstitute;
01837         return true;
01838       }
01839 
01840     // Try to optimize globals based on the knowledge that only one value
01841     // (besides its initializer) is ever stored to the global.
01842     if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, GVI,
01843                                  DL, TLI))
01844       return true;
01845 
01846     // Otherwise, if the global was not a boolean, we can shrink it to be a
01847     // boolean.
01848     if (Constant *SOVConstant = dyn_cast<Constant>(GS.StoredOnceValue)) {
01849       if (GS.Ordering == NotAtomic) {
01850         if (TryToShrinkGlobalToBoolean(GV, SOVConstant)) {
01851           ++NumShrunkToBool;
01852           return true;
01853         }
01854       }
01855     }
01856   }
01857 
01858   return false;
01859 }
01860 
01861 /// ChangeCalleesToFastCall - Walk all of the direct calls of the specified
01862 /// function, changing them to FastCC.
01863 static void ChangeCalleesToFastCall(Function *F) {
01864   for (User *U : F->users()) {
01865     if (isa<BlockAddress>(U))
01866       continue;
01867     CallSite CS(cast<Instruction>(U));
01868     CS.setCallingConv(CallingConv::Fast);
01869   }
01870 }
01871 
01872 static AttributeSet StripNest(LLVMContext &C, const AttributeSet &Attrs) {
01873   for (unsigned i = 0, e = Attrs.getNumSlots(); i != e; ++i) {
01874     unsigned Index = Attrs.getSlotIndex(i);
01875     if (!Attrs.getSlotAttributes(i).hasAttribute(Index, Attribute::Nest))
01876       continue;
01877 
01878     // There can be only one.
01879     return Attrs.removeAttribute(C, Index, Attribute::Nest);
01880   }
01881 
01882   return Attrs;
01883 }
01884 
01885 static void RemoveNestAttribute(Function *F) {
01886   F->setAttributes(StripNest(F->getContext(), F->getAttributes()));
01887   for (User *U : F->users()) {
01888     if (isa<BlockAddress>(U))
01889       continue;
01890     CallSite CS(cast<Instruction>(U));
01891     CS.setAttributes(StripNest(F->getContext(), CS.getAttributes()));
01892   }
01893 }
01894 
01895 /// Return true if this is a calling convention that we'd like to change.  The
01896 /// idea here is that we don't want to mess with the convention if the user
01897 /// explicitly requested something with performance implications like coldcc,
01898 /// GHC, or anyregcc.
01899 static bool isProfitableToMakeFastCC(Function *F) {
01900   CallingConv::ID CC = F->getCallingConv();
01901   // FIXME: Is it worth transforming x86_stdcallcc and x86_fastcallcc?
01902   return CC == CallingConv::C || CC == CallingConv::X86_ThisCall;
01903 }
01904 
01905 bool GlobalOpt::OptimizeFunctions(Module &M) {
01906   bool Changed = false;
01907   // Optimize functions.
01908   for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) {
01909     Function *F = FI++;
01910     // Functions without names cannot be referenced outside this module.
01911     if (!F->hasName() && !F->isDeclaration() && !F->hasLocalLinkage())
01912       F->setLinkage(GlobalValue::InternalLinkage);
01913     F->removeDeadConstantUsers();
01914     if (F->isDefTriviallyDead()) {
01915       F->eraseFromParent();
01916       Changed = true;
01917       ++NumFnDeleted;
01918     } else if (F->hasLocalLinkage()) {
01919       if (isProfitableToMakeFastCC(F) && !F->isVarArg() &&
01920           !F->hasAddressTaken()) {
01921         // If this function has a calling convention worth changing, is not a
01922         // varargs function, and is only called directly, promote it to use the
01923         // Fast calling convention.
01924         F->setCallingConv(CallingConv::Fast);
01925         ChangeCalleesToFastCall(F);
01926         ++NumFastCallFns;
01927         Changed = true;
01928       }
01929 
01930       if (F->getAttributes().hasAttrSomewhere(Attribute::Nest) &&
01931           !F->hasAddressTaken()) {
01932         // The function is not used by a trampoline intrinsic, so it is safe
01933         // to remove the 'nest' attribute.
01934         RemoveNestAttribute(F);
01935         ++NumNestRemoved;
01936         Changed = true;
01937       }
01938     }
01939   }
01940   return Changed;
01941 }
01942 
01943 bool GlobalOpt::OptimizeGlobalVars(Module &M) {
01944   bool Changed = false;
01945 
01946   SmallSet<const Comdat *, 8> NotDiscardableComdats;
01947   for (const GlobalVariable &GV : M.globals())
01948     if (const Comdat *C = GV.getComdat())
01949       if (!GV.isDiscardableIfUnused())
01950         NotDiscardableComdats.insert(C);
01951 
01952   for (Module::global_iterator GVI = M.global_begin(), E = M.global_end();
01953        GVI != E; ) {
01954     GlobalVariable *GV = GVI++;
01955     // Global variables without names cannot be referenced outside this module.
01956     if (!GV->hasName() && !GV->isDeclaration() && !GV->hasLocalLinkage())
01957       GV->setLinkage(GlobalValue::InternalLinkage);
01958     // Simplify the initializer.
01959     if (GV->hasInitializer())
01960       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GV->getInitializer())) {
01961         Constant *New = ConstantFoldConstantExpression(CE, DL, TLI);
01962         if (New && New != CE)
01963           GV->setInitializer(New);
01964       }
01965 
01966     if (GV->isDiscardableIfUnused()) {
01967       if (const Comdat *C = GV->getComdat())
01968         if (NotDiscardableComdats.count(C))
01969           continue;
01970       Changed |= ProcessGlobal(GV, GVI);
01971     }
01972   }
01973   return Changed;
01974 }
01975 
01976 static inline bool
01977 isSimpleEnoughValueToCommit(Constant *C,
01978                             SmallPtrSet<Constant*, 8> &SimpleConstants,
01979                             const DataLayout *DL);
01980 
01981 
01982 /// isSimpleEnoughValueToCommit - Return true if the specified constant can be
01983 /// handled by the code generator.  We don't want to generate something like:
01984 ///   void *X = &X/42;
01985 /// because the code generator doesn't have a relocation that can handle that.
01986 ///
01987 /// This function should be called if C was not found (but just got inserted)
01988 /// in SimpleConstants to avoid having to rescan the same constants all the
01989 /// time.
01990 static bool isSimpleEnoughValueToCommitHelper(Constant *C,
01991                                    SmallPtrSet<Constant*, 8> &SimpleConstants,
01992                                    const DataLayout *DL) {
01993   // Simple global addresses are supported, do not allow dllimport or
01994   // thread-local globals.
01995   if (auto *GV = dyn_cast<GlobalValue>(C))
01996     return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal();
01997 
01998   // Simple integer, undef, constant aggregate zero, etc are all supported.
01999   if (C->getNumOperands() == 0 || isa<BlockAddress>(C))
02000     return true;
02001 
02002   // Aggregate values are safe if all their elements are.
02003   if (isa<ConstantArray>(C) || isa<ConstantStruct>(C) ||
02004       isa<ConstantVector>(C)) {
02005     for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) {
02006       Constant *Op = cast<Constant>(C->getOperand(i));
02007       if (!isSimpleEnoughValueToCommit(Op, SimpleConstants, DL))
02008         return false;
02009     }
02010     return true;
02011   }
02012 
02013   // We don't know exactly what relocations are allowed in constant expressions,
02014   // so we allow &global+constantoffset, which is safe and uniformly supported
02015   // across targets.
02016   ConstantExpr *CE = cast<ConstantExpr>(C);
02017   switch (CE->getOpcode()) {
02018   case Instruction::BitCast:
02019     // Bitcast is fine if the casted value is fine.
02020     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
02021 
02022   case Instruction::IntToPtr:
02023   case Instruction::PtrToInt:
02024     // int <=> ptr is fine if the int type is the same size as the
02025     // pointer type.
02026     if (!DL || DL->getTypeSizeInBits(CE->getType()) !=
02027                DL->getTypeSizeInBits(CE->getOperand(0)->getType()))
02028       return false;
02029     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
02030 
02031   // GEP is fine if it is simple + constant offset.
02032   case Instruction::GetElementPtr:
02033     for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
02034       if (!isa<ConstantInt>(CE->getOperand(i)))
02035         return false;
02036     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
02037 
02038   case Instruction::Add:
02039     // We allow simple+cst.
02040     if (!isa<ConstantInt>(CE->getOperand(1)))
02041       return false;
02042     return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL);
02043   }
02044   return false;
02045 }
02046 
02047 static inline bool
02048 isSimpleEnoughValueToCommit(Constant *C,
02049                             SmallPtrSet<Constant*, 8> &SimpleConstants,
02050                             const DataLayout *DL) {
02051   // If we already checked this constant, we win.
02052   if (!SimpleConstants.insert(C)) return true;
02053   // Check the constant.
02054   return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL);
02055 }
02056 
02057 
02058 /// isSimpleEnoughPointerToCommit - Return true if this constant is simple
02059 /// enough for us to understand.  In particular, if it is a cast to anything
02060 /// other than from one pointer type to another pointer type, we punt.
02061 /// We basically just support direct accesses to globals and GEP's of
02062 /// globals.  This should be kept up to date with CommitValueTo.
02063 static bool isSimpleEnoughPointerToCommit(Constant *C) {
02064   // Conservatively, avoid aggregate types. This is because we don't
02065   // want to worry about them partially overlapping other stores.
02066   if (!cast<PointerType>(C->getType())->getElementType()->isSingleValueType())
02067     return false;
02068 
02069   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C))
02070     // Do not allow weak/*_odr/linkonce linkage or external globals.
02071     return GV->hasUniqueInitializer();
02072 
02073   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) {
02074     // Handle a constantexpr gep.
02075     if (CE->getOpcode() == Instruction::GetElementPtr &&
02076         isa<GlobalVariable>(CE->getOperand(0)) &&
02077         cast<GEPOperator>(CE)->isInBounds()) {
02078       GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
02079       // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
02080       // external globals.
02081       if (!GV->hasUniqueInitializer())
02082         return false;
02083 
02084       // The first index must be zero.
02085       ConstantInt *CI = dyn_cast<ConstantInt>(*std::next(CE->op_begin()));
02086       if (!CI || !CI->isZero()) return false;
02087 
02088       // The remaining indices must be compile-time known integers within the
02089       // notional bounds of the corresponding static array types.
02090       if (!CE->isGEPWithNoNotionalOverIndexing())
02091         return false;
02092 
02093       return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
02094 
02095     // A constantexpr bitcast from a pointer to another pointer is a no-op,
02096     // and we know how to evaluate it by moving the bitcast from the pointer
02097     // operand to the value operand.
02098     } else if (CE->getOpcode() == Instruction::BitCast &&
02099                isa<GlobalVariable>(CE->getOperand(0))) {
02100       // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or
02101       // external globals.
02102       return cast<GlobalVariable>(CE->getOperand(0))->hasUniqueInitializer();
02103     }
02104   }
02105 
02106   return false;
02107 }
02108 
02109 /// EvaluateStoreInto - Evaluate a piece of a constantexpr store into a global
02110 /// initializer.  This returns 'Init' modified to reflect 'Val' stored into it.
02111 /// At this point, the GEP operands of Addr [0, OpNo) have been stepped into.
02112 static Constant *EvaluateStoreInto(Constant *Init, Constant *Val,
02113                                    ConstantExpr *Addr, unsigned OpNo) {
02114   // Base case of the recursion.
02115   if (OpNo == Addr->getNumOperands()) {
02116     assert(Val->getType() == Init->getType() && "Type mismatch!");
02117     return Val;
02118   }
02119 
02120   SmallVector<Constant*, 32> Elts;
02121   if (StructType *STy = dyn_cast<StructType>(Init->getType())) {
02122     // Break up the constant into its elements.
02123     for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i)
02124       Elts.push_back(Init->getAggregateElement(i));
02125 
02126     // Replace the element that we are supposed to.
02127     ConstantInt *CU = cast<ConstantInt>(Addr->getOperand(OpNo));
02128     unsigned Idx = CU->getZExtValue();
02129     assert(Idx < STy->getNumElements() && "Struct index out of range!");
02130     Elts[Idx] = EvaluateStoreInto(Elts[Idx], Val, Addr, OpNo+1);
02131 
02132     // Return the modified struct.
02133     return ConstantStruct::get(STy, Elts);
02134   }
02135 
02136   ConstantInt *CI = cast<ConstantInt>(Addr->getOperand(OpNo));
02137   SequentialType *InitTy = cast<SequentialType>(Init->getType());
02138 
02139   uint64_t NumElts;
02140   if (ArrayType *ATy = dyn_cast<ArrayType>(InitTy))
02141     NumElts = ATy->getNumElements();
02142   else
02143     NumElts = InitTy->getVectorNumElements();
02144 
02145   // Break up the array into elements.
02146   for (uint64_t i = 0, e = NumElts; i != e; ++i)
02147     Elts.push_back(Init->getAggregateElement(i));
02148 
02149   assert(CI->getZExtValue() < NumElts);
02150   Elts[CI->getZExtValue()] =
02151     EvaluateStoreInto(Elts[CI->getZExtValue()], Val, Addr, OpNo+1);
02152 
02153   if (Init->getType()->isArrayTy())
02154     return ConstantArray::get(cast<ArrayType>(InitTy), Elts);
02155   return ConstantVector::get(Elts);
02156 }
02157 
02158 /// CommitValueTo - We have decided that Addr (which satisfies the predicate
02159 /// isSimpleEnoughPointerToCommit) should get Val as its value.  Make it happen.
02160 static void CommitValueTo(Constant *Val, Constant *Addr) {
02161   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Addr)) {
02162     assert(GV->hasInitializer());
02163     GV->setInitializer(Val);
02164     return;
02165   }
02166 
02167   ConstantExpr *CE = cast<ConstantExpr>(Addr);
02168   GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
02169   GV->setInitializer(EvaluateStoreInto(GV->getInitializer(), Val, CE, 2));
02170 }
02171 
02172 namespace {
02173 
02174 /// Evaluator - This class evaluates LLVM IR, producing the Constant
02175 /// representing each SSA instruction.  Changes to global variables are stored
02176 /// in a mapping that can be iterated over after the evaluation is complete.
02177 /// Once an evaluation call fails, the evaluation object should not be reused.
02178 class Evaluator {
02179 public:
02180   Evaluator(const DataLayout *DL, const TargetLibraryInfo *TLI)
02181     : DL(DL), TLI(TLI) {
02182     ValueStack.emplace_back();
02183   }
02184 
02185   ~Evaluator() {
02186     for (auto &Tmp : AllocaTmps)
02187       // If there are still users of the alloca, the program is doing something
02188       // silly, e.g. storing the address of the alloca somewhere and using it
02189       // later.  Since this is undefined, we'll just make it be null.
02190       if (!Tmp->use_empty())
02191         Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType()));
02192   }
02193 
02194   /// EvaluateFunction - Evaluate a call to function F, returning true if
02195   /// successful, false if we can't evaluate it.  ActualArgs contains the formal
02196   /// arguments for the function.
02197   bool EvaluateFunction(Function *F, Constant *&RetVal,
02198                         const SmallVectorImpl<Constant*> &ActualArgs);
02199 
02200   /// EvaluateBlock - Evaluate all instructions in block BB, returning true if
02201   /// successful, false if we can't evaluate it.  NewBB returns the next BB that
02202   /// control flows into, or null upon return.
02203   bool EvaluateBlock(BasicBlock::iterator CurInst, BasicBlock *&NextBB);
02204 
02205   Constant *getVal(Value *V) {
02206     if (Constant *CV = dyn_cast<Constant>(V)) return CV;
02207     Constant *R = ValueStack.back().lookup(V);
02208     assert(R && "Reference to an uncomputed value!");
02209     return R;
02210   }
02211 
02212   void setVal(Value *V, Constant *C) {
02213     ValueStack.back()[V] = C;
02214   }
02215 
02216   const DenseMap<Constant*, Constant*> &getMutatedMemory() const {
02217     return MutatedMemory;
02218   }
02219 
02220   const SmallPtrSet<GlobalVariable*, 8> &getInvariants() const {
02221     return Invariants;
02222   }
02223 
02224 private:
02225   Constant *ComputeLoadResult(Constant *P);
02226 
02227   /// ValueStack - As we compute SSA register values, we store their contents
02228   /// here. The back of the deque contains the current function and the stack
02229   /// contains the values in the calling frames.
02230   std::deque<DenseMap<Value*, Constant*>> ValueStack;
02231 
02232   /// CallStack - This is used to detect recursion.  In pathological situations
02233   /// we could hit exponential behavior, but at least there is nothing
02234   /// unbounded.
02235   SmallVector<Function*, 4> CallStack;
02236 
02237   /// MutatedMemory - For each store we execute, we update this map.  Loads
02238   /// check this to get the most up-to-date value.  If evaluation is successful,
02239   /// this state is committed to the process.
02240   DenseMap<Constant*, Constant*> MutatedMemory;
02241 
02242   /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable
02243   /// to represent its body.  This vector is needed so we can delete the
02244   /// temporary globals when we are done.
02245   SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps;
02246 
02247   /// Invariants - These global variables have been marked invariant by the
02248   /// static constructor.
02249   SmallPtrSet<GlobalVariable*, 8> Invariants;
02250 
02251   /// SimpleConstants - These are constants we have checked and know to be
02252   /// simple enough to live in a static initializer of a global.
02253   SmallPtrSet<Constant*, 8> SimpleConstants;
02254 
02255   const DataLayout *DL;
02256   const TargetLibraryInfo *TLI;
02257 };
02258 
02259 }  // anonymous namespace
02260 
02261 /// ComputeLoadResult - Return the value that would be computed by a load from
02262 /// P after the stores reflected by 'memory' have been performed.  If we can't
02263 /// decide, return null.
02264 Constant *Evaluator::ComputeLoadResult(Constant *P) {
02265   // If this memory location has been recently stored, use the stored value: it
02266   // is the most up-to-date.
02267   DenseMap<Constant*, Constant*>::const_iterator I = MutatedMemory.find(P);
02268   if (I != MutatedMemory.end()) return I->second;
02269 
02270   // Access it.
02271   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) {
02272     if (GV->hasDefinitiveInitializer())
02273       return GV->getInitializer();
02274     return nullptr;
02275   }
02276 
02277   // Handle a constantexpr getelementptr.
02278   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(P))
02279     if (CE->getOpcode() == Instruction::GetElementPtr &&
02280         isa<GlobalVariable>(CE->getOperand(0))) {
02281       GlobalVariable *GV = cast<GlobalVariable>(CE->getOperand(0));
02282       if (GV->hasDefinitiveInitializer())
02283         return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE);
02284     }
02285 
02286   return nullptr;  // don't know how to evaluate.
02287 }
02288 
02289 /// EvaluateBlock - Evaluate all instructions in block BB, returning true if
02290 /// successful, false if we can't evaluate it.  NewBB returns the next BB that
02291 /// control flows into, or null upon return.
02292 bool Evaluator::EvaluateBlock(BasicBlock::iterator CurInst,
02293                               BasicBlock *&NextBB) {
02294   // This is the main evaluation loop.
02295   while (1) {
02296     Constant *InstResult = nullptr;
02297 
02298     DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n");
02299 
02300     if (StoreInst *SI = dyn_cast<StoreInst>(CurInst)) {
02301       if (!SI->isSimple()) {
02302         DEBUG(dbgs() << "Store is not simple! Can not evaluate.\n");
02303         return false;  // no volatile/atomic accesses.
02304       }
02305       Constant *Ptr = getVal(SI->getOperand(1));
02306       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
02307         DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr);
02308         Ptr = ConstantFoldConstantExpression(CE, DL, TLI);
02309         DEBUG(dbgs() << "; To: " << *Ptr << "\n");
02310       }
02311       if (!isSimpleEnoughPointerToCommit(Ptr)) {
02312         // If this is too complex for us to commit, reject it.
02313         DEBUG(dbgs() << "Pointer is too complex for us to evaluate store.");
02314         return false;
02315       }
02316 
02317       Constant *Val = getVal(SI->getOperand(0));
02318 
02319       // If this might be too difficult for the backend to handle (e.g. the addr
02320       // of one global variable divided by another) then we can't commit it.
02321       if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) {
02322         DEBUG(dbgs() << "Store value is too complex to evaluate store. " << *Val
02323               << "\n");
02324         return false;
02325       }
02326 
02327       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
02328         if (CE->getOpcode() == Instruction::BitCast) {
02329           DEBUG(dbgs() << "Attempting to resolve bitcast on constant ptr.\n");
02330           // If we're evaluating a store through a bitcast, then we need
02331           // to pull the bitcast off the pointer type and push it onto the
02332           // stored value.
02333           Ptr = CE->getOperand(0);
02334 
02335           Type *NewTy = cast<PointerType>(Ptr->getType())->getElementType();
02336 
02337           // In order to push the bitcast onto the stored value, a bitcast
02338           // from NewTy to Val's type must be legal.  If it's not, we can try
02339           // introspecting NewTy to find a legal conversion.
02340           while (!Val->getType()->canLosslesslyBitCastTo(NewTy)) {
02341             // If NewTy is a struct, we can convert the pointer to the struct
02342             // into a pointer to its first member.
02343             // FIXME: This could be extended to support arrays as well.
02344             if (StructType *STy = dyn_cast<StructType>(NewTy)) {
02345               NewTy = STy->getTypeAtIndex(0U);
02346 
02347               IntegerType *IdxTy = IntegerType::get(NewTy->getContext(), 32);
02348               Constant *IdxZero = ConstantInt::get(IdxTy, 0, false);
02349               Constant * const IdxList[] = {IdxZero, IdxZero};
02350 
02351               Ptr = ConstantExpr::getGetElementPtr(Ptr, IdxList);
02352               if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr))
02353                 Ptr = ConstantFoldConstantExpression(CE, DL, TLI);
02354 
02355             // If we can't improve the situation by introspecting NewTy,
02356             // we have to give up.
02357             } else {
02358               DEBUG(dbgs() << "Failed to bitcast constant ptr, can not "
02359                     "evaluate.\n");
02360               return false;
02361             }
02362           }
02363 
02364           // If we found compatible types, go ahead and push the bitcast
02365           // onto the stored value.
02366           Val = ConstantExpr::getBitCast(Val, NewTy);
02367 
02368           DEBUG(dbgs() << "Evaluated bitcast: " << *Val << "\n");
02369         }
02370       }
02371 
02372       MutatedMemory[Ptr] = Val;
02373     } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(CurInst)) {
02374       InstResult = ConstantExpr::get(BO->getOpcode(),
02375                                      getVal(BO->getOperand(0)),
02376                                      getVal(BO->getOperand(1)));
02377       DEBUG(dbgs() << "Found a BinaryOperator! Simplifying: " << *InstResult
02378             << "\n");
02379     } else if (CmpInst *CI = dyn_cast<CmpInst>(CurInst)) {
02380       InstResult = ConstantExpr::getCompare(CI->getPredicate(),
02381                                             getVal(CI->getOperand(0)),
02382                                             getVal(CI->getOperand(1)));
02383       DEBUG(dbgs() << "Found a CmpInst! Simplifying: " << *InstResult
02384             << "\n");
02385     } else if (CastInst *CI = dyn_cast<CastInst>(CurInst)) {
02386       InstResult = ConstantExpr::getCast(CI->getOpcode(),
02387                                          getVal(CI->getOperand(0)),
02388                                          CI->getType());
02389       DEBUG(dbgs() << "Found a Cast! Simplifying: " << *InstResult
02390             << "\n");
02391     } else if (SelectInst *SI = dyn_cast<SelectInst>(CurInst)) {
02392       InstResult = ConstantExpr::getSelect(getVal(SI->getOperand(0)),
02393                                            getVal(SI->getOperand(1)),
02394                                            getVal(SI->getOperand(2)));
02395       DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult
02396             << "\n");
02397     } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) {
02398       Constant *P = getVal(GEP->getOperand(0));
02399       SmallVector<Constant*, 8> GEPOps;
02400       for (User::op_iterator i = GEP->op_begin() + 1, e = GEP->op_end();
02401            i != e; ++i)
02402         GEPOps.push_back(getVal(*i));
02403       InstResult =
02404         ConstantExpr::getGetElementPtr(P, GEPOps,
02405                                        cast<GEPOperator>(GEP)->isInBounds());
02406       DEBUG(dbgs() << "Found a GEP! Simplifying: " << *InstResult
02407             << "\n");
02408     } else if (LoadInst *LI = dyn_cast<LoadInst>(CurInst)) {
02409 
02410       if (!LI->isSimple()) {
02411         DEBUG(dbgs() << "Found a Load! Not a simple load, can not evaluate.\n");
02412         return false;  // no volatile/atomic accesses.
02413       }
02414 
02415       Constant *Ptr = getVal(LI->getOperand(0));
02416       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) {
02417         Ptr = ConstantFoldConstantExpression(CE, DL, TLI);
02418         DEBUG(dbgs() << "Found a constant pointer expression, constant "
02419               "folding: " << *Ptr << "\n");
02420       }
02421       InstResult = ComputeLoadResult(Ptr);
02422       if (!InstResult) {
02423         DEBUG(dbgs() << "Failed to compute load result. Can not evaluate load."
02424               "\n");
02425         return false; // Could not evaluate load.
02426       }
02427 
02428       DEBUG(dbgs() << "Evaluated load: " << *InstResult << "\n");
02429     } else if (AllocaInst *AI = dyn_cast<AllocaInst>(CurInst)) {
02430       if (AI->isArrayAllocation()) {
02431         DEBUG(dbgs() << "Found an array alloca. Can not evaluate.\n");
02432         return false;  // Cannot handle array allocs.
02433       }
02434       Type *Ty = AI->getType()->getElementType();
02435       AllocaTmps.push_back(
02436           make_unique<GlobalVariable>(Ty, false, GlobalValue::InternalLinkage,
02437                                       UndefValue::get(Ty), AI->getName()));
02438       InstResult = AllocaTmps.back().get();
02439       DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n");
02440     } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) {
02441       CallSite CS(CurInst);
02442 
02443       // Debug info can safely be ignored here.
02444       if (isa<DbgInfoIntrinsic>(CS.getInstruction())) {
02445         DEBUG(dbgs() << "Ignoring debug info.\n");
02446         ++CurInst;
02447         continue;
02448       }
02449 
02450       // Cannot handle inline asm.
02451       if (isa<InlineAsm>(CS.getCalledValue())) {
02452         DEBUG(dbgs() << "Found inline asm, can not evaluate.\n");
02453         return false;
02454       }
02455 
02456       if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) {
02457         if (MemSetInst *MSI = dyn_cast<MemSetInst>(II)) {
02458           if (MSI->isVolatile()) {
02459             DEBUG(dbgs() << "Can not optimize a volatile memset " <<
02460                   "intrinsic.\n");
02461             return false;
02462           }
02463           Constant *Ptr = getVal(MSI->getDest());
02464           Constant *Val = getVal(MSI->getValue());
02465           Constant *DestVal = ComputeLoadResult(getVal(Ptr));
02466           if (Val->isNullValue() && DestVal && DestVal->isNullValue()) {
02467             // This memset is a no-op.
02468             DEBUG(dbgs() << "Ignoring no-op memset.\n");
02469             ++CurInst;
02470             continue;
02471           }
02472         }
02473 
02474         if (II->getIntrinsicID() == Intrinsic::lifetime_start ||
02475             II->getIntrinsicID() == Intrinsic::lifetime_end) {
02476           DEBUG(dbgs() << "Ignoring lifetime intrinsic.\n");
02477           ++CurInst;
02478           continue;
02479         }
02480 
02481         if (II->getIntrinsicID() == Intrinsic::invariant_start) {
02482           // We don't insert an entry into Values, as it doesn't have a
02483           // meaningful return value.
02484           if (!II->use_empty()) {
02485             DEBUG(dbgs() << "Found unused invariant_start. Can't evaluate.\n");
02486             return false;
02487           }
02488           ConstantInt *Size = cast<ConstantInt>(II->getArgOperand(0));
02489           Value *PtrArg = getVal(II->getArgOperand(1));
02490           Value *Ptr = PtrArg->stripPointerCasts();
02491           if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) {
02492             Type *ElemTy = cast<PointerType>(GV->getType())->getElementType();
02493             if (DL && !Size->isAllOnesValue() &&
02494                 Size->getValue().getLimitedValue() >=
02495                 DL->getTypeStoreSize(ElemTy)) {
02496               Invariants.insert(GV);
02497               DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV
02498                     << "\n");
02499             } else {
02500               DEBUG(dbgs() << "Found a global var, but can not treat it as an "
02501                     "invariant.\n");
02502             }
02503           }
02504           // Continue even if we do nothing.
02505           ++CurInst;
02506           continue;
02507         }
02508 
02509         DEBUG(dbgs() << "Unknown intrinsic. Can not evaluate.\n");
02510         return false;
02511       }
02512 
02513       // Resolve function pointers.
02514       Function *Callee = dyn_cast<Function>(getVal(CS.getCalledValue()));
02515       if (!Callee || Callee->mayBeOverridden()) {
02516         DEBUG(dbgs() << "Can not resolve function pointer.\n");
02517         return false;  // Cannot resolve.
02518       }
02519 
02520       SmallVector<Constant*, 8> Formals;
02521       for (User::op_iterator i = CS.arg_begin(), e = CS.arg_end(); i != e; ++i)
02522         Formals.push_back(getVal(*i));
02523 
02524       if (Callee->isDeclaration()) {
02525         // If this is a function we can constant fold, do it.
02526         if (Constant *C = ConstantFoldCall(Callee, Formals, TLI)) {
02527           InstResult = C;
02528           DEBUG(dbgs() << "Constant folded function call. Result: " <<
02529                 *InstResult << "\n");
02530         } else {
02531           DEBUG(dbgs() << "Can not constant fold function call.\n");
02532           return false;
02533         }
02534       } else {
02535         if (Callee->getFunctionType()->isVarArg()) {
02536           DEBUG(dbgs() << "Can not constant fold vararg function call.\n");
02537           return false;
02538         }
02539 
02540         Constant *RetVal = nullptr;
02541         // Execute the call, if successful, use the return value.
02542         ValueStack.emplace_back();
02543         if (!EvaluateFunction(Callee, RetVal, Formals)) {
02544           DEBUG(dbgs() << "Failed to evaluate function.\n");
02545           return false;
02546         }
02547         ValueStack.pop_back();
02548         InstResult = RetVal;
02549 
02550         if (InstResult) {
02551           DEBUG(dbgs() << "Successfully evaluated function. Result: " <<
02552                 InstResult << "\n\n");
02553         } else {
02554           DEBUG(dbgs() << "Successfully evaluated function. Result: 0\n\n");
02555         }
02556       }
02557     } else if (isa<TerminatorInst>(CurInst)) {
02558       DEBUG(dbgs() << "Found a terminator instruction.\n");
02559 
02560       if (BranchInst *BI = dyn_cast<BranchInst>(CurInst)) {
02561         if (BI->isUnconditional()) {
02562           NextBB = BI->getSuccessor(0);
02563         } else {
02564           ConstantInt *Cond =
02565             dyn_cast<ConstantInt>(getVal(BI->getCondition()));
02566           if (!Cond) return false;  // Cannot determine.
02567 
02568           NextBB = BI->getSuccessor(!Cond->getZExtValue());
02569         }
02570       } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurInst)) {
02571         ConstantInt *Val =
02572           dyn_cast<ConstantInt>(getVal(SI->getCondition()));
02573         if (!Val) return false;  // Cannot determine.
02574         NextBB = SI->findCaseValue(Val).getCaseSuccessor();
02575       } else if (IndirectBrInst *IBI = dyn_cast<IndirectBrInst>(CurInst)) {
02576         Value *Val = getVal(IBI->getAddress())->stripPointerCasts();
02577         if (BlockAddress *BA = dyn_cast<BlockAddress>(Val))
02578           NextBB = BA->getBasicBlock();
02579         else
02580           return false;  // Cannot determine.
02581       } else if (isa<ReturnInst>(CurInst)) {
02582         NextBB = nullptr;
02583       } else {
02584         // invoke, unwind, resume, unreachable.
02585         DEBUG(dbgs() << "Can not handle terminator.");
02586         return false;  // Cannot handle this terminator.
02587       }
02588 
02589       // We succeeded at evaluating this block!
02590       DEBUG(dbgs() << "Successfully evaluated block.\n");
02591       return true;
02592     } else {
02593       // Did not know how to evaluate this!
02594       DEBUG(dbgs() << "Failed to evaluate block due to unhandled instruction."
02595             "\n");
02596       return false;
02597     }
02598 
02599     if (!CurInst->use_empty()) {
02600       if (ConstantExpr *CE = dyn_cast<ConstantExpr>(InstResult))
02601         InstResult = ConstantFoldConstantExpression(CE, DL, TLI);
02602 
02603       setVal(CurInst, InstResult);
02604     }
02605 
02606     // If we just processed an invoke, we finished evaluating the block.
02607     if (InvokeInst *II = dyn_cast<InvokeInst>(CurInst)) {
02608       NextBB = II->getNormalDest();
02609       DEBUG(dbgs() << "Found an invoke instruction. Finished Block.\n\n");
02610       return true;
02611     }
02612 
02613     // Advance program counter.
02614     ++CurInst;
02615   }
02616 }
02617 
02618 /// EvaluateFunction - Evaluate a call to function F, returning true if
02619 /// successful, false if we can't evaluate it.  ActualArgs contains the formal
02620 /// arguments for the function.
02621 bool Evaluator::EvaluateFunction(Function *F, Constant *&RetVal,
02622                                  const SmallVectorImpl<Constant*> &ActualArgs) {
02623   // Check to see if this function is already executing (recursion).  If so,
02624   // bail out.  TODO: we might want to accept limited recursion.
02625   if (std::find(CallStack.begin(), CallStack.end(), F) != CallStack.end())
02626     return false;
02627 
02628   CallStack.push_back(F);
02629 
02630   // Initialize arguments to the incoming values specified.
02631   unsigned ArgNo = 0;
02632   for (Function::arg_iterator AI = F->arg_begin(), E = F->arg_end(); AI != E;
02633        ++AI, ++ArgNo)
02634     setVal(AI, ActualArgs[ArgNo]);
02635 
02636   // ExecutedBlocks - We only handle non-looping, non-recursive code.  As such,
02637   // we can only evaluate any one basic block at most once.  This set keeps
02638   // track of what we have executed so we can detect recursive cases etc.
02639   SmallPtrSet<BasicBlock*, 32> ExecutedBlocks;
02640 
02641   // CurBB - The current basic block we're evaluating.
02642   BasicBlock *CurBB = F->begin();
02643 
02644   BasicBlock::iterator CurInst = CurBB->begin();
02645 
02646   while (1) {
02647     BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings.
02648     DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n");
02649 
02650     if (!EvaluateBlock(CurInst, NextBB))
02651       return false;
02652 
02653     if (!NextBB) {
02654       // Successfully running until there's no next block means that we found
02655       // the return.  Fill it the return value and pop the call stack.
02656       ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator());
02657       if (RI->getNumOperands())
02658         RetVal = getVal(RI->getOperand(0));
02659       CallStack.pop_back();
02660       return true;
02661     }
02662 
02663     // Okay, we succeeded in evaluating this control flow.  See if we have
02664     // executed the new block before.  If so, we have a looping function,
02665     // which we cannot evaluate in reasonable time.
02666     if (!ExecutedBlocks.insert(NextBB))
02667       return false;  // looped!
02668 
02669     // Okay, we have never been in this block before.  Check to see if there
02670     // are any PHI nodes.  If so, evaluate them with information about where
02671     // we came from.
02672     PHINode *PN = nullptr;
02673     for (CurInst = NextBB->begin();
02674          (PN = dyn_cast<PHINode>(CurInst)); ++CurInst)
02675       setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB)));
02676 
02677     // Advance to the next block.
02678     CurBB = NextBB;
02679   }
02680 }
02681 
02682 /// EvaluateStaticConstructor - Evaluate static constructors in the function, if
02683 /// we can.  Return true if we can, false otherwise.
02684 static bool EvaluateStaticConstructor(Function *F, const DataLayout *DL,
02685                                       const TargetLibraryInfo *TLI) {
02686   // Call the function.
02687   Evaluator Eval(DL, TLI);
02688   Constant *RetValDummy;
02689   bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy,
02690                                            SmallVector<Constant*, 0>());
02691 
02692   if (EvalSuccess) {
02693     ++NumCtorsEvaluated;
02694 
02695     // We succeeded at evaluation: commit the result.
02696     DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '"
02697           << F->getName() << "' to " << Eval.getMutatedMemory().size()
02698           << " stores.\n");
02699     for (DenseMap<Constant*, Constant*>::const_iterator I =
02700            Eval.getMutatedMemory().begin(), E = Eval.getMutatedMemory().end();
02701          I != E; ++I)
02702       CommitValueTo(I->second, I->first);
02703     for (SmallPtrSet<GlobalVariable*, 8>::const_iterator I =
02704            Eval.getInvariants().begin(), E = Eval.getInvariants().end();
02705          I != E; ++I)
02706       (*I)->setConstant(true);
02707   }
02708 
02709   return EvalSuccess;
02710 }
02711 
02712 static int compareNames(Constant *const *A, Constant *const *B) {
02713   return (*A)->getName().compare((*B)->getName());
02714 }
02715 
02716 static void setUsedInitializer(GlobalVariable &V,
02717                                SmallPtrSet<GlobalValue *, 8> Init) {
02718   if (Init.empty()) {
02719     V.eraseFromParent();
02720     return;
02721   }
02722 
02723   // Type of pointer to the array of pointers.
02724   PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext(), 0);
02725 
02726   SmallVector<llvm::Constant *, 8> UsedArray;
02727   for (SmallPtrSet<GlobalValue *, 8>::iterator I = Init.begin(), E = Init.end();
02728        I != E; ++I) {
02729     Constant *Cast
02730       = ConstantExpr::getPointerBitCastOrAddrSpaceCast(*I, Int8PtrTy);
02731     UsedArray.push_back(Cast);
02732   }
02733   // Sort to get deterministic order.
02734   array_pod_sort(UsedArray.begin(), UsedArray.end(), compareNames);
02735   ArrayType *ATy = ArrayType::get(Int8PtrTy, UsedArray.size());
02736 
02737   Module *M = V.getParent();
02738   V.removeFromParent();
02739   GlobalVariable *NV =
02740       new GlobalVariable(*M, ATy, false, llvm::GlobalValue::AppendingLinkage,
02741                          llvm::ConstantArray::get(ATy, UsedArray), "");
02742   NV->takeName(&V);
02743   NV->setSection("llvm.metadata");
02744   delete &V;
02745 }
02746 
02747 namespace {
02748 /// \brief An easy to access representation of llvm.used and llvm.compiler.used.
02749 class LLVMUsed {
02750   SmallPtrSet<GlobalValue *, 8> Used;
02751   SmallPtrSet<GlobalValue *, 8> CompilerUsed;
02752   GlobalVariable *UsedV;
02753   GlobalVariable *CompilerUsedV;
02754 
02755 public:
02756   LLVMUsed(Module &M) {
02757     UsedV = collectUsedGlobalVariables(M, Used, false);
02758     CompilerUsedV = collectUsedGlobalVariables(M, CompilerUsed, true);
02759   }
02760   typedef SmallPtrSet<GlobalValue *, 8>::iterator iterator;
02761   iterator usedBegin() { return Used.begin(); }
02762   iterator usedEnd() { return Used.end(); }
02763   iterator compilerUsedBegin() { return CompilerUsed.begin(); }
02764   iterator compilerUsedEnd() { return CompilerUsed.end(); }
02765   bool usedCount(GlobalValue *GV) const { return Used.count(GV); }
02766   bool compilerUsedCount(GlobalValue *GV) const {
02767     return CompilerUsed.count(GV);
02768   }
02769   bool usedErase(GlobalValue *GV) { return Used.erase(GV); }
02770   bool compilerUsedErase(GlobalValue *GV) { return CompilerUsed.erase(GV); }
02771   bool usedInsert(GlobalValue *GV) { return Used.insert(GV); }
02772   bool compilerUsedInsert(GlobalValue *GV) { return CompilerUsed.insert(GV); }
02773 
02774   void syncVariablesAndSets() {
02775     if (UsedV)
02776       setUsedInitializer(*UsedV, Used);
02777     if (CompilerUsedV)
02778       setUsedInitializer(*CompilerUsedV, CompilerUsed);
02779   }
02780 };
02781 }
02782 
02783 static bool hasUseOtherThanLLVMUsed(GlobalAlias &GA, const LLVMUsed &U) {
02784   if (GA.use_empty()) // No use at all.
02785     return false;
02786 
02787   assert((!U.usedCount(&GA) || !U.compilerUsedCount(&GA)) &&
02788          "We should have removed the duplicated "
02789          "element from llvm.compiler.used");
02790   if (!GA.hasOneUse())
02791     // Strictly more than one use. So at least one is not in llvm.used and
02792     // llvm.compiler.used.
02793     return true;
02794 
02795   // Exactly one use. Check if it is in llvm.used or llvm.compiler.used.
02796   return !U.usedCount(&GA) && !U.compilerUsedCount(&GA);
02797 }
02798 
02799 static bool hasMoreThanOneUseOtherThanLLVMUsed(GlobalValue &V,
02800                                                const LLVMUsed &U) {
02801   unsigned N = 2;
02802   assert((!U.usedCount(&V) || !U.compilerUsedCount(&V)) &&
02803          "We should have removed the duplicated "
02804          "element from llvm.compiler.used");
02805   if (U.usedCount(&V) || U.compilerUsedCount(&V))
02806     ++N;
02807   return V.hasNUsesOrMore(N);
02808 }
02809 
02810 static bool mayHaveOtherReferences(GlobalAlias &GA, const LLVMUsed &U) {
02811   if (!GA.hasLocalLinkage())
02812     return true;
02813 
02814   return U.usedCount(&GA) || U.compilerUsedCount(&GA);
02815 }
02816 
02817 static bool hasUsesToReplace(GlobalAlias &GA, LLVMUsed &U, bool &RenameTarget) {
02818   RenameTarget = false;
02819   bool Ret = false;
02820   if (hasUseOtherThanLLVMUsed(GA, U))
02821     Ret = true;
02822 
02823   // If the alias is externally visible, we may still be able to simplify it.
02824   if (!mayHaveOtherReferences(GA, U))
02825     return Ret;
02826 
02827   // If the aliasee has internal linkage, give it the name and linkage
02828   // of the alias, and delete the alias.  This turns:
02829   //   define internal ... @f(...)
02830   //   @a = alias ... @f
02831   // into:
02832   //   define ... @a(...)
02833   Constant *Aliasee = GA.getAliasee();
02834   GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts());
02835   if (!Target->hasLocalLinkage())
02836     return Ret;
02837 
02838   // Do not perform the transform if multiple aliases potentially target the
02839   // aliasee. This check also ensures that it is safe to replace the section
02840   // and other attributes of the aliasee with those of the alias.
02841   if (hasMoreThanOneUseOtherThanLLVMUsed(*Target, U))
02842     return Ret;
02843 
02844   RenameTarget = true;
02845   return true;
02846 }
02847 
02848 bool GlobalOpt::OptimizeGlobalAliases(Module &M) {
02849   bool Changed = false;
02850   LLVMUsed Used(M);
02851 
02852   for (SmallPtrSet<GlobalValue *, 8>::iterator I = Used.usedBegin(),
02853                                                E = Used.usedEnd();
02854        I != E; ++I)
02855     Used.compilerUsedErase(*I);
02856 
02857   for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end();
02858        I != E;) {
02859     Module::alias_iterator J = I++;
02860     // Aliases without names cannot be referenced outside this module.
02861     if (!J->hasName() && !J->isDeclaration() && !J->hasLocalLinkage())
02862       J->setLinkage(GlobalValue::InternalLinkage);
02863     // If the aliasee may change at link time, nothing can be done - bail out.
02864     if (J->mayBeOverridden())
02865       continue;
02866 
02867     Constant *Aliasee = J->getAliasee();
02868     GlobalValue *Target = dyn_cast<GlobalValue>(Aliasee->stripPointerCasts());
02869     // We can't trivially replace the alias with the aliasee if the aliasee is
02870     // non-trivial in some way.
02871     // TODO: Try to handle non-zero GEPs of local aliasees.
02872     if (!Target)
02873       continue;
02874     Target->removeDeadConstantUsers();
02875 
02876     // Make all users of the alias use the aliasee instead.
02877     bool RenameTarget;
02878     if (!hasUsesToReplace(*J, Used, RenameTarget))
02879       continue;
02880 
02881     J->replaceAllUsesWith(ConstantExpr::getBitCast(Aliasee, J->getType()));
02882     ++NumAliasesResolved;
02883     Changed = true;
02884 
02885     if (RenameTarget) {
02886       // Give the aliasee the name, linkage and other attributes of the alias.
02887       Target->takeName(J);
02888       Target->setLinkage(J->getLinkage());
02889       Target->setVisibility(J->getVisibility());
02890       Target->setDLLStorageClass(J->getDLLStorageClass());
02891 
02892       if (Used.usedErase(J))
02893         Used.usedInsert(Target);
02894 
02895       if (Used.compilerUsedErase(J))
02896         Used.compilerUsedInsert(Target);
02897     } else if (mayHaveOtherReferences(*J, Used))
02898       continue;
02899 
02900     // Delete the alias.
02901     M.getAliasList().erase(J);
02902     ++NumAliasesRemoved;
02903     Changed = true;
02904   }
02905 
02906   Used.syncVariablesAndSets();
02907 
02908   return Changed;
02909 }
02910 
02911 static Function *FindCXAAtExit(Module &M, TargetLibraryInfo *TLI) {
02912   if (!TLI->has(LibFunc::cxa_atexit))
02913     return nullptr;
02914 
02915   Function *Fn = M.getFunction(TLI->getName(LibFunc::cxa_atexit));
02916 
02917   if (!Fn)
02918     return nullptr;
02919 
02920   FunctionType *FTy = Fn->getFunctionType();
02921 
02922   // Checking that the function has the right return type, the right number of
02923   // parameters and that they all have pointer types should be enough.
02924   if (!FTy->getReturnType()->isIntegerTy() ||
02925       FTy->getNumParams() != 3 ||
02926       !FTy->getParamType(0)->isPointerTy() ||
02927       !FTy->getParamType(1)->isPointerTy() ||
02928       !FTy->getParamType(2)->isPointerTy())
02929     return nullptr;
02930 
02931   return Fn;
02932 }
02933 
02934 /// cxxDtorIsEmpty - Returns whether the given function is an empty C++
02935 /// destructor and can therefore be eliminated.
02936 /// Note that we assume that other optimization passes have already simplified
02937 /// the code so we only look for a function with a single basic block, where
02938 /// the only allowed instructions are 'ret', 'call' to an empty C++ dtor and
02939 /// other side-effect free instructions.
02940 static bool cxxDtorIsEmpty(const Function &Fn,
02941                            SmallPtrSet<const Function *, 8> &CalledFunctions) {
02942   // FIXME: We could eliminate C++ destructors if they're readonly/readnone and
02943   // nounwind, but that doesn't seem worth doing.
02944   if (Fn.isDeclaration())
02945     return false;
02946 
02947   if (++Fn.begin() != Fn.end())
02948     return false;
02949 
02950   const BasicBlock &EntryBlock = Fn.getEntryBlock();
02951   for (BasicBlock::const_iterator I = EntryBlock.begin(), E = EntryBlock.end();
02952        I != E; ++I) {
02953     if (const CallInst *CI = dyn_cast<CallInst>(I)) {
02954       // Ignore debug intrinsics.
02955       if (isa<DbgInfoIntrinsic>(CI))
02956         continue;
02957 
02958       const Function *CalledFn = CI->getCalledFunction();
02959 
02960       if (!CalledFn)
02961         return false;
02962 
02963       SmallPtrSet<const Function *, 8> NewCalledFunctions(CalledFunctions);
02964 
02965       // Don't treat recursive functions as empty.
02966       if (!NewCalledFunctions.insert(CalledFn))
02967         return false;
02968 
02969       if (!cxxDtorIsEmpty(*CalledFn, NewCalledFunctions))
02970         return false;
02971     } else if (isa<ReturnInst>(*I))
02972       return true; // We're done.
02973     else if (I->mayHaveSideEffects())
02974       return false; // Destructor with side effects, bail.
02975   }
02976 
02977   return false;
02978 }
02979 
02980 bool GlobalOpt::OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn) {
02981   /// Itanium C++ ABI p3.3.5:
02982   ///
02983   ///   After constructing a global (or local static) object, that will require
02984   ///   destruction on exit, a termination function is registered as follows:
02985   ///
02986   ///   extern "C" int __cxa_atexit ( void (*f)(void *), void *p, void *d );
02987   ///
02988   ///   This registration, e.g. __cxa_atexit(f,p,d), is intended to cause the
02989   ///   call f(p) when DSO d is unloaded, before all such termination calls
02990   ///   registered before this one. It returns zero if registration is
02991   ///   successful, nonzero on failure.
02992 
02993   // This pass will look for calls to __cxa_atexit where the function is trivial
02994   // and remove them.
02995   bool Changed = false;
02996 
02997   for (auto I = CXAAtExitFn->user_begin(), E = CXAAtExitFn->user_end();
02998        I != E;) {
02999     // We're only interested in calls. Theoretically, we could handle invoke
03000     // instructions as well, but neither llvm-gcc nor clang generate invokes
03001     // to __cxa_atexit.
03002     CallInst *CI = dyn_cast<CallInst>(*I++);
03003     if (!CI)
03004       continue;
03005 
03006     Function *DtorFn =
03007       dyn_cast<Function>(CI->getArgOperand(0)->stripPointerCasts());
03008     if (!DtorFn)
03009       continue;
03010 
03011     SmallPtrSet<const Function *, 8> CalledFunctions;
03012     if (!cxxDtorIsEmpty(*DtorFn, CalledFunctions))
03013       continue;
03014 
03015     // Just remove the call.
03016     CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
03017     CI->eraseFromParent();
03018 
03019     ++NumCXXDtorsRemoved;
03020 
03021     Changed |= true;
03022   }
03023 
03024   return Changed;
03025 }
03026 
03027 bool GlobalOpt::runOnModule(Module &M) {
03028   bool Changed = false;
03029 
03030   DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
03031   DL = DLP ? &DLP->getDataLayout() : nullptr;
03032   TLI = &getAnalysis<TargetLibraryInfo>();
03033 
03034   bool LocalChange = true;
03035   while (LocalChange) {
03036     LocalChange = false;
03037 
03038     // Delete functions that are trivially dead, ccc -> fastcc
03039     LocalChange |= OptimizeFunctions(M);
03040 
03041     // Optimize global_ctors list.
03042     LocalChange |= optimizeGlobalCtorsList(M, [&](Function *F) {
03043       return EvaluateStaticConstructor(F, DL, TLI);
03044     });
03045 
03046     // Optimize non-address-taken globals.
03047     LocalChange |= OptimizeGlobalVars(M);
03048 
03049     // Resolve aliases, when possible.
03050     LocalChange |= OptimizeGlobalAliases(M);
03051 
03052     // Try to remove trivial global destructors if they are not removed
03053     // already.
03054     Function *CXAAtExitFn = FindCXAAtExit(M, TLI);
03055     if (CXAAtExitFn)
03056       LocalChange |= OptimizeEmptyGlobalCXXDtors(CXAAtExitFn);
03057 
03058     Changed |= LocalChange;
03059   }
03060 
03061   // TODO: Move all global ctors functions to the end of the module for code
03062   // layout.
03063 
03064   return Changed;
03065 }