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