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