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