LLVM API Documentation

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