Mercurial > hg > Members > tobaru > cbc > CbC_llvm
diff lib/Transforms/IPO/GlobalOpt.cpp @ 80:67baa08a3894
update to LLVM 3.6
| author | Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 25 Sep 2014 16:56:18 +0900 |
| parents | 54457678186b |
| children | 60c9769439b8 |
line wrap: on
line diff
--- a/lib/Transforms/IPO/GlobalOpt.cpp Mon May 05 03:18:03 2014 +0900 +++ b/lib/Transforms/IPO/GlobalOpt.cpp Thu Sep 25 16:56:18 2014 +0900 @@ -13,36 +13,41 @@ // //===----------------------------------------------------------------------===// -#define DEBUG_TYPE "globalopt" #include "llvm/Transforms/IPO.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/Analysis/ConstantFolding.h" #include "llvm/Analysis/MemoryBuiltins.h" +#include "llvm/IR/CallSite.h" #include "llvm/IR/CallingConv.h" #include "llvm/IR/Constants.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/DerivedTypes.h" +#include "llvm/IR/GetElementPtrTypeIterator.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Module.h" #include "llvm/IR/Operator.h" +#include "llvm/IR/ValueHandle.h" #include "llvm/Pass.h" -#include "llvm/Support/CallSite.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" -#include "llvm/Support/GetElementPtrTypeIterator.h" #include "llvm/Support/MathExtras.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Target/TargetLibraryInfo.h" +#include "llvm/Transforms/Utils/CtorUtils.h" #include "llvm/Transforms/Utils/GlobalStatus.h" #include "llvm/Transforms/Utils/ModuleUtils.h" #include <algorithm> +#include <deque> using namespace llvm; +#define DEBUG_TYPE "globalopt" + STATISTIC(NumMarked , "Number of globals marked constant"); STATISTIC(NumUnnamed , "Number of globals marked unnamed_addr"); STATISTIC(NumSRA , "Number of aggregate globals broken into scalars"); @@ -62,7 +67,7 @@ namespace { struct GlobalOpt : public ModulePass { - virtual void getAnalysisUsage(AnalysisUsage &AU) const { + void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired<TargetLibraryInfo>(); } static char ID; // Pass identification, replacement for typeid @@ -70,20 +75,18 @@ initializeGlobalOptPass(*PassRegistry::getPassRegistry()); } - bool runOnModule(Module &M); + bool runOnModule(Module &M) override; private: - GlobalVariable *FindGlobalCtors(Module &M); bool OptimizeFunctions(Module &M); bool OptimizeGlobalVars(Module &M); bool OptimizeGlobalAliases(Module &M); - bool OptimizeGlobalCtorsList(GlobalVariable *&GCL); bool ProcessGlobal(GlobalVariable *GV,Module::global_iterator &GVI); bool ProcessInternalGlobal(GlobalVariable *GV,Module::global_iterator &GVI, const GlobalStatus &GS); bool OptimizeEmptyGlobalCXXDtors(Function *CXAAtExitFn); - DataLayout *TD; + const DataLayout *DL; TargetLibraryInfo *TLI; }; } @@ -195,7 +198,7 @@ SmallVector<std::pair<Instruction *, Instruction *>, 32> Dead; // Constants can't be pointers to dynamically allocated memory. - for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); + for (Value::user_iterator UI = GV->user_begin(), E = GV->user_end(); UI != E;) { User *U = *UI++; if (StoreInst *SI = dyn_cast<StoreInst>(U)) { @@ -265,11 +268,20 @@ /// quick scan over the use list to clean up the easy and obvious cruft. This /// returns true if it made a change. static bool CleanupConstantGlobalUsers(Value *V, Constant *Init, - DataLayout *TD, TargetLibraryInfo *TLI) { + const DataLayout *DL, + TargetLibraryInfo *TLI) { bool Changed = false; - SmallVector<User*, 8> WorkList(V->use_begin(), V->use_end()); + // Note that we need to use a weak value handle for the worklist items. When + // we delete a constant array, we may also be holding pointer to one of its + // elements (or an element of one of its elements if we're dealing with an + // array of arrays) in the worklist. + SmallVector<WeakVH, 8> WorkList(V->user_begin(), V->user_end()); while (!WorkList.empty()) { - User *U = WorkList.pop_back_val(); + Value *UV = WorkList.pop_back_val(); + if (!UV) + continue; + + User *U = cast<User>(UV); if (LoadInst *LI = dyn_cast<LoadInst>(U)) { if (Init) { @@ -284,14 +296,15 @@ Changed = true; } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(U)) { if (CE->getOpcode() == Instruction::GetElementPtr) { - Constant *SubInit = 0; + Constant *SubInit = nullptr; if (Init) SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE); - Changed |= CleanupConstantGlobalUsers(CE, SubInit, TD, TLI); - } else if (CE->getOpcode() == Instruction::BitCast && - CE->getType()->isPointerTy()) { + Changed |= CleanupConstantGlobalUsers(CE, SubInit, DL, TLI); + } else if ((CE->getOpcode() == Instruction::BitCast && + CE->getType()->isPointerTy()) || + CE->getOpcode() == Instruction::AddrSpaceCast) { // Pointer cast, delete any stores and memsets to the global. - Changed |= CleanupConstantGlobalUsers(CE, 0, TD, TLI); + Changed |= CleanupConstantGlobalUsers(CE, nullptr, DL, TLI); } if (CE->use_empty()) { @@ -302,10 +315,10 @@ // Do not transform "gepinst (gep constexpr (GV))" here, because forming // "gepconstexpr (gep constexpr (GV))" will cause the two gep's to fold // and will invalidate our notion of what Init is. - Constant *SubInit = 0; + Constant *SubInit = nullptr; if (!isa<ConstantExpr>(GEP->getOperand(0))) { ConstantExpr *CE = - dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP, TD, TLI)); + dyn_cast_or_null<ConstantExpr>(ConstantFoldInstruction(GEP, DL, TLI)); if (Init && CE && CE->getOpcode() == Instruction::GetElementPtr) SubInit = ConstantFoldLoadThroughGEPConstantExpr(Init, CE); @@ -315,7 +328,7 @@ if (Init && isa<ConstantAggregateZero>(Init) && GEP->isInBounds()) SubInit = Constant::getNullValue(GEP->getType()->getElementType()); } - Changed |= CleanupConstantGlobalUsers(GEP, SubInit, TD, TLI); + Changed |= CleanupConstantGlobalUsers(GEP, SubInit, DL, TLI); if (GEP->use_empty()) { GEP->eraseFromParent(); @@ -332,7 +345,7 @@ // us, and if they are all dead, nuke them without remorse. if (isSafeToDestroyConstant(C)) { C->destroyConstant(); - CleanupConstantGlobalUsers(V, Init, TD, TLI); + CleanupConstantGlobalUsers(V, Init, DL, TLI); return true; } } @@ -359,15 +372,14 @@ // Otherwise, it must be a GEP. GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(I); - if (GEPI == 0) return false; + if (!GEPI) return false; if (GEPI->getNumOperands() < 3 || !isa<Constant>(GEPI->getOperand(1)) || !cast<Constant>(GEPI->getOperand(1))->isNullValue()) return false; - for (Value::use_iterator I = GEPI->use_begin(), E = GEPI->use_end(); - I != E; ++I) - if (!isSafeSROAElementUse(*I)) + for (User *U : GEPI->users()) + if (!isSafeSROAElementUse(U)) return false; return true; } @@ -433,9 +445,10 @@ } } - for (Value::use_iterator I = U->use_begin(), E = U->use_end(); I != E; ++I) - if (!isSafeSROAElementUse(*I)) + for (User *UU : U->users()) + if (!isSafeSROAElementUse(UU)) return false; + return true; } @@ -443,11 +456,10 @@ /// is safe for us to perform this transformation. /// static bool GlobalUsersSafeToSRA(GlobalValue *GV) { - for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); - UI != E; ++UI) { - if (!IsUserOfGlobalSafeForSRA(*UI, GV)) + for (User *U : GV->users()) + if (!IsUserOfGlobalSafeForSRA(U, GV)) return false; - } + return true; } @@ -457,10 +469,10 @@ /// behavior of the program in a more fine-grained way. We have determined that /// this transformation is safe already. We return the first global variable we /// insert so that the caller can reprocess it. -static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &TD) { +static GlobalVariable *SRAGlobal(GlobalVariable *GV, const DataLayout &DL) { // Make sure this global only has simple uses that we can SRA. if (!GlobalUsersSafeToSRA(GV)) - return 0; + return nullptr; assert(GV->hasLocalLinkage() && !GV->isConstant()); Constant *Init = GV->getInitializer(); @@ -472,11 +484,11 @@ // Get the alignment of the global, either explicit or target-specific. unsigned StartAlignment = GV->getAlignment(); if (StartAlignment == 0) - StartAlignment = TD.getABITypeAlignment(GV->getType()); + StartAlignment = DL.getABITypeAlignment(GV->getType()); if (StructType *STy = dyn_cast<StructType>(Ty)) { NewGlobals.reserve(STy->getNumElements()); - const StructLayout &Layout = *TD.getStructLayout(STy); + const StructLayout &Layout = *DL.getStructLayout(STy); for (unsigned i = 0, e = STy->getNumElements(); i != e; ++i) { Constant *In = Init->getAggregateElement(i); assert(In && "Couldn't get element of initializer?"); @@ -493,7 +505,7 @@ // propagate info to each field. uint64_t FieldOffset = Layout.getElementOffset(i); unsigned NewAlign = (unsigned)MinAlign(StartAlignment, FieldOffset); - if (NewAlign > TD.getABITypeAlignment(STy->getElementType(i))) + if (NewAlign > DL.getABITypeAlignment(STy->getElementType(i))) NGV->setAlignment(NewAlign); } } else if (SequentialType *STy = dyn_cast<SequentialType>(Ty)) { @@ -504,11 +516,11 @@ NumElements = cast<VectorType>(STy)->getNumElements(); if (NumElements > 16 && GV->hasNUsesOrMore(16)) - return 0; // It's not worth it. + return nullptr; // It's not worth it. NewGlobals.reserve(NumElements); - uint64_t EltSize = TD.getTypeAllocSize(STy->getElementType()); - unsigned EltAlign = TD.getABITypeAlignment(STy->getElementType()); + uint64_t EltSize = DL.getTypeAllocSize(STy->getElementType()); + unsigned EltAlign = DL.getABITypeAlignment(STy->getElementType()); for (unsigned i = 0, e = NumElements; i != e; ++i) { Constant *In = Init->getAggregateElement(i); assert(In && "Couldn't get element of initializer?"); @@ -531,7 +543,7 @@ } if (NewGlobals.empty()) - return 0; + return nullptr; DEBUG(dbgs() << "PERFORMING GLOBAL SRA ON: " << *GV); @@ -540,7 +552,7 @@ // Loop over all of the uses of the global, replacing the constantexpr geps, // with smaller constantexpr geps or direct references. while (!GV->use_empty()) { - User *GEP = GV->use_back(); + User *GEP = GV->user_back(); assert(((isa<ConstantExpr>(GEP) && cast<ConstantExpr>(GEP)->getOpcode()==Instruction::GetElementPtr)|| isa<GetElementPtrInst>(GEP)) && "NonGEP CE's are not SRAable!"); @@ -593,18 +605,15 @@ if (FirstGlobal == i) ++FirstGlobal; } - return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : 0; + return FirstGlobal != NewGlobals.size() ? NewGlobals[FirstGlobal] : nullptr; } /// AllUsesOfValueWillTrapIfNull - Return true if all users of the specified /// value will trap if the value is dynamically null. PHIs keeps track of any /// phi nodes we've seen to avoid reprocessing them. static bool AllUsesOfValueWillTrapIfNull(const Value *V, - SmallPtrSet<const PHINode*, 8> &PHIs) { - for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; - ++UI) { - const User *U = *UI; - + SmallPtrSetImpl<const PHINode*> &PHIs) { + for (const User *U : V->users()) if (isa<LoadInst>(U)) { // Will trap. } else if (const StoreInst *SI = dyn_cast<StoreInst>(U)) { @@ -632,13 +641,13 @@ if (PHIs.insert(PN) && !AllUsesOfValueWillTrapIfNull(PN, PHIs)) return false; } else if (isa<ICmpInst>(U) && - isa<ConstantPointerNull>(UI->getOperand(1))) { + isa<ConstantPointerNull>(U->getOperand(1))) { // Ignore icmp X, null } else { //cerr << "NONTRAPPING USE: " << *U; return false; } - } + return true; } @@ -646,10 +655,7 @@ /// from GV will trap if the loaded value is null. Note that this also permits /// comparisons of the loaded value against null, as a special case. static bool AllUsesOfLoadedValueWillTrapIfNull(const GlobalVariable *GV) { - for (Value::const_use_iterator UI = GV->use_begin(), E = GV->use_end(); - UI != E; ++UI) { - const User *U = *UI; - + for (const User *U : GV->users()) if (const LoadInst *LI = dyn_cast<LoadInst>(U)) { SmallPtrSet<const PHINode*, 8> PHIs; if (!AllUsesOfValueWillTrapIfNull(LI, PHIs)) @@ -661,13 +667,12 @@ //cerr << "UNKNOWN USER OF GLOBAL!: " << *U; return false; } - } return true; } static bool OptimizeAwayTrappingUsesOfValue(Value *V, Constant *NewV) { bool Changed = false; - for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) { + for (auto UI = V->user_begin(), E = V->user_end(); UI != E; ) { Instruction *I = cast<Instruction>(*UI++); if (LoadInst *LI = dyn_cast<LoadInst>(I)) { LI->setOperand(0, NewV); @@ -693,7 +698,7 @@ if (PassedAsArg) { // Being passed as an argument also. Be careful to not invalidate UI! - UI = V->use_begin(); + UI = V->user_begin(); } } } else if (CastInst *CI = dyn_cast<CastInst>(I)) { @@ -733,7 +738,7 @@ /// if the loaded value is dynamically null, then we know that they cannot be /// reachable with a null optimize away the load. static bool OptimizeAwayTrappingUsesOfLoads(GlobalVariable *GV, Constant *LV, - DataLayout *TD, + const DataLayout *DL, TargetLibraryInfo *TLI) { bool Changed = false; @@ -742,7 +747,7 @@ bool AllNonStoreUsesGone = true; // Replace all uses of loads with uses of uses of the stored value. - for (Value::use_iterator GUI = GV->use_begin(), E = GV->use_end(); GUI != E;){ + for (Value::user_iterator GUI = GV->user_begin(), E = GV->user_end(); GUI != E;){ User *GlobalUser = *GUI++; if (LoadInst *LI = dyn_cast<LoadInst>(GlobalUser)) { Changed |= OptimizeAwayTrappingUsesOfValue(LI, LV); @@ -782,7 +787,7 @@ Changed |= CleanupPointerRootUsers(GV, TLI); } else { Changed = true; - CleanupConstantGlobalUsers(GV, 0, TD, TLI); + CleanupConstantGlobalUsers(GV, nullptr, DL, TLI); } if (GV->use_empty()) { DEBUG(dbgs() << " *** GLOBAL NOW DEAD!\n"); @@ -796,11 +801,11 @@ /// ConstantPropUsersOf - Walk the use list of V, constant folding all of the /// instructions that are foldable. -static void ConstantPropUsersOf(Value *V, - DataLayout *TD, TargetLibraryInfo *TLI) { - for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ) +static void ConstantPropUsersOf(Value *V, const DataLayout *DL, + TargetLibraryInfo *TLI) { + for (Value::user_iterator UI = V->user_begin(), E = V->user_end(); UI != E; ) if (Instruction *I = dyn_cast<Instruction>(*UI++)) - if (Constant *NewC = ConstantFoldInstruction(I, TD, TLI)) { + if (Constant *NewC = ConstantFoldInstruction(I, DL, TLI)) { I->replaceAllUsesWith(NewC); // Advance UI to the next non-I use to avoid invalidating it! @@ -820,7 +825,7 @@ CallInst *CI, Type *AllocTy, ConstantInt *NElements, - DataLayout *TD, + const DataLayout *DL, TargetLibraryInfo *TLI) { DEBUG(errs() << "PROMOTING GLOBAL: " << *GV << " CALL = " << *CI << '\n'); @@ -844,9 +849,9 @@ // If there are bitcast users of the malloc (which is typical, usually we have // a malloc + bitcast) then replace them with uses of the new global. Update // other users to use the global as well. - BitCastInst *TheBC = 0; + BitCastInst *TheBC = nullptr; while (!CI->use_empty()) { - Instruction *User = cast<Instruction>(CI->use_back()); + Instruction *User = cast<Instruction>(CI->user_back()); if (BitCastInst *BCI = dyn_cast<BitCastInst>(User)) { if (BCI->getType() == NewGV->getType()) { BCI->replaceAllUsesWith(NewGV); @@ -855,7 +860,7 @@ BCI->setOperand(0, NewGV); } } else { - if (TheBC == 0) + if (!TheBC) TheBC = new BitCastInst(NewGV, CI->getType(), "newgv", CI); User->replaceUsesOfWith(CI, TheBC); } @@ -877,7 +882,7 @@ // Loop over all uses of GV, processing them in turn. while (!GV->use_empty()) { - if (StoreInst *SI = dyn_cast<StoreInst>(GV->use_back())) { + if (StoreInst *SI = dyn_cast<StoreInst>(GV->user_back())) { // The global is initialized when the store to it occurs. new StoreInst(ConstantInt::getTrue(GV->getContext()), InitBool, false, 0, SI->getOrdering(), SI->getSynchScope(), SI); @@ -885,15 +890,15 @@ continue; } - LoadInst *LI = cast<LoadInst>(GV->use_back()); + LoadInst *LI = cast<LoadInst>(GV->user_back()); while (!LI->use_empty()) { - Use &LoadUse = LI->use_begin().getUse(); - if (!isa<ICmpInst>(LoadUse.getUser())) { + Use &LoadUse = *LI->use_begin(); + ICmpInst *ICI = dyn_cast<ICmpInst>(LoadUse.getUser()); + if (!ICI) { LoadUse = RepValue; continue; } - ICmpInst *ICI = cast<ICmpInst>(LoadUse.getUser()); // Replace the cmp X, 0 with a use of the bool value. // Sink the load to where the compare was, if atomic rules allow us to. Value *LV = new LoadInst(InitBool, InitBool->getName()+".val", false, 0, @@ -927,7 +932,7 @@ // If the initialization boolean was used, insert it, otherwise delete it. if (!InitBoolUsed) { while (!InitBool->use_empty()) // Delete initializations - cast<StoreInst>(InitBool->use_back())->eraseFromParent(); + cast<StoreInst>(InitBool->user_back())->eraseFromParent(); delete InitBool; } else GV->getParent()->getGlobalList().insert(GV, InitBool); @@ -939,9 +944,9 @@ // To further other optimizations, loop over all users of NewGV and try to // constant prop them. This will promote GEP instructions with constant // indices into GEP constant-exprs, which will allow global-opt to hack on it. - ConstantPropUsersOf(NewGV, TD, TLI); + ConstantPropUsersOf(NewGV, DL, TLI); if (RepValue != NewGV) - ConstantPropUsersOf(RepValue, TD, TLI); + ConstantPropUsersOf(RepValue, DL, TLI); return NewGV; } @@ -952,10 +957,9 @@ /// it is to the specified global. static bool ValueIsOnlyUsedLocallyOrStoredToOneGlobal(const Instruction *V, const GlobalVariable *GV, - SmallPtrSet<const PHINode*, 8> &PHIs) { - for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); - UI != E; ++UI) { - const Instruction *Inst = cast<Instruction>(*UI); + SmallPtrSetImpl<const PHINode*> &PHIs) { + for (const User *U : V->users()) { + const Instruction *Inst = cast<Instruction>(U); if (isa<LoadInst>(Inst) || isa<CmpInst>(Inst)) { continue; // Fine, ignore. @@ -1002,7 +1006,7 @@ static void ReplaceUsesOfMallocWithGlobal(Instruction *Alloc, GlobalVariable *GV) { while (!Alloc->use_empty()) { - Instruction *U = cast<Instruction>(*Alloc->use_begin()); + Instruction *U = cast<Instruction>(*Alloc->user_begin()); Instruction *InsertPt = U; if (StoreInst *SI = dyn_cast<StoreInst>(U)) { // If this is the store of the allocation into the global, remove it. @@ -1013,7 +1017,7 @@ } else if (PHINode *PN = dyn_cast<PHINode>(U)) { // Insert the load in the corresponding predecessor, not right before the // PHI. - InsertPt = PN->getIncomingBlock(Alloc->use_begin())->getTerminator(); + InsertPt = PN->getIncomingBlock(*Alloc->use_begin())->getTerminator(); } else if (isa<BitCastInst>(U)) { // Must be bitcast between the malloc and store to initialize the global. ReplaceUsesOfMallocWithGlobal(U, GV); @@ -1023,7 +1027,7 @@ // If this is a "GEP bitcast" and the user is a store to the global, then // just process it as a bitcast. if (GEPI->hasAllZeroIndices() && GEPI->hasOneUse()) - if (StoreInst *SI = dyn_cast<StoreInst>(GEPI->use_back())) + if (StoreInst *SI = dyn_cast<StoreInst>(GEPI->user_back())) if (SI->getOperand(1) == GV) { // Must be bitcast GEP between the malloc and store to initialize // the global. @@ -1043,23 +1047,22 @@ /// of a load) are simple enough to perform heap SRA on. This permits GEP's /// that index through the array and struct field, icmps of null, and PHIs. static bool LoadUsesSimpleEnoughForHeapSRA(const Value *V, - SmallPtrSet<const PHINode*, 32> &LoadUsingPHIs, - SmallPtrSet<const PHINode*, 32> &LoadUsingPHIsPerLoad) { + SmallPtrSetImpl<const PHINode*> &LoadUsingPHIs, + SmallPtrSetImpl<const PHINode*> &LoadUsingPHIsPerLoad) { // We permit two users of the load: setcc comparing against the null // pointer, and a getelementptr of a specific form. - for (Value::const_use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; - ++UI) { - const Instruction *User = cast<Instruction>(*UI); + for (const User *U : V->users()) { + const Instruction *UI = cast<Instruction>(U); // Comparison against null is ok. - if (const ICmpInst *ICI = dyn_cast<ICmpInst>(User)) { + if (const ICmpInst *ICI = dyn_cast<ICmpInst>(UI)) { if (!isa<ConstantPointerNull>(ICI->getOperand(1))) return false; continue; } // getelementptr is also ok, but only a simple form. - if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(User)) { + if (const GetElementPtrInst *GEPI = dyn_cast<GetElementPtrInst>(UI)) { // Must index into the array and into the struct. if (GEPI->getNumOperands() < 3) return false; @@ -1068,7 +1071,7 @@ continue; } - if (const PHINode *PN = dyn_cast<PHINode>(User)) { + if (const PHINode *PN = dyn_cast<PHINode>(UI)) { if (!LoadUsingPHIsPerLoad.insert(PN)) // This means some phi nodes are dependent on each other. // Avoid infinite looping! @@ -1099,9 +1102,8 @@ Instruction *StoredVal) { SmallPtrSet<const PHINode*, 32> LoadUsingPHIs; SmallPtrSet<const PHINode*, 32> LoadUsingPHIsPerLoad; - for (Value::const_use_iterator UI = GV->use_begin(), E = GV->use_end(); - UI != E; ++UI) - if (const LoadInst *LI = dyn_cast<LoadInst>(*UI)) { + for (const User *U : GV->users()) + if (const LoadInst *LI = dyn_cast<LoadInst>(U)) { if (!LoadUsesSimpleEnoughForHeapSRA(LI, LoadUsingPHIs, LoadUsingPHIsPerLoad)) return false; @@ -1113,9 +1115,7 @@ // that all inputs the to the PHI nodes are in the same equivalence sets. // Check to verify that all operands of the PHIs are either PHIS that can be // transformed, loads from GV, or MI itself. - for (SmallPtrSet<const PHINode*, 32>::const_iterator I = LoadUsingPHIs.begin() - , E = LoadUsingPHIs.end(); I != E; ++I) { - const PHINode *PN = *I; + for (const PHINode *PN : LoadUsingPHIs) { for (unsigned op = 0, e = PN->getNumIncomingValues(); op != e; ++op) { Value *InVal = PN->getIncomingValue(op); @@ -1169,10 +1169,13 @@ } else if (PHINode *PN = dyn_cast<PHINode>(V)) { // PN's type is pointer to struct. Make a new PHI of pointer to struct // field. - StructType *ST = cast<StructType>(PN->getType()->getPointerElementType()); - + + PointerType *PTy = cast<PointerType>(PN->getType()); + StructType *ST = cast<StructType>(PTy->getElementType()); + + unsigned AS = PTy->getAddressSpace(); PHINode *NewPN = - PHINode::Create(PointerType::getUnqual(ST->getElementType(FieldNo)), + PHINode::Create(PointerType::get(ST->getElementType(FieldNo), AS), PN->getNumIncomingValues(), PN->getName()+".f"+Twine(FieldNo), PN); Result = NewPN; @@ -1240,7 +1243,7 @@ // If this is the first time we've seen this PHI, recursively process all // users. - for (Value::use_iterator UI = PN->use_begin(), E = PN->use_end(); UI != E; ) { + for (auto UI = PN->user_begin(), E = PN->user_end(); UI != E;) { Instruction *User = cast<Instruction>(*UI++); RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite); } @@ -1253,8 +1256,7 @@ static void RewriteUsesOfLoadForHeapSRoA(LoadInst *Load, DenseMap<Value*, std::vector<Value*> > &InsertedScalarizedValues, std::vector<std::pair<PHINode*, unsigned> > &PHIsToRewrite) { - for (Value::use_iterator UI = Load->use_begin(), E = Load->use_end(); - UI != E; ) { + for (auto UI = Load->user_begin(), E = Load->user_end(); UI != E;) { Instruction *User = cast<Instruction>(*UI++); RewriteHeapSROALoadUser(User, InsertedScalarizedValues, PHIsToRewrite); } @@ -1268,7 +1270,7 @@ /// PerformHeapAllocSRoA - CI is an allocation of an array of structures. Break /// it up into multiple allocations of arrays of the fields. static GlobalVariable *PerformHeapAllocSRoA(GlobalVariable *GV, CallInst *CI, - Value *NElems, DataLayout *TD, + Value *NElems, const DataLayout *DL, const TargetLibraryInfo *TLI) { DEBUG(dbgs() << "SROA HEAP ALLOC: " << *GV << " MALLOC = " << *CI << '\n'); Type *MAT = getMallocAllocatedType(CI, TLI); @@ -1285,9 +1287,10 @@ std::vector<Value*> FieldGlobals; std::vector<Value*> FieldMallocs; + unsigned AS = GV->getType()->getPointerAddressSpace(); for (unsigned FieldNo = 0, e = STy->getNumElements(); FieldNo != e;++FieldNo){ Type *FieldTy = STy->getElementType(FieldNo); - PointerType *PFieldTy = PointerType::getUnqual(FieldTy); + PointerType *PFieldTy = PointerType::get(FieldTy, AS); GlobalVariable *NGV = new GlobalVariable(*GV->getParent(), @@ -1297,13 +1300,13 @@ GV->getThreadLocalMode()); FieldGlobals.push_back(NGV); - unsigned TypeSize = TD->getTypeAllocSize(FieldTy); + unsigned TypeSize = DL->getTypeAllocSize(FieldTy); if (StructType *ST = dyn_cast<StructType>(FieldTy)) - TypeSize = TD->getStructLayout(ST)->getSizeInBytes(); - Type *IntPtrTy = TD->getIntPtrType(CI->getType()); + TypeSize = DL->getStructLayout(ST)->getSizeInBytes(); + Type *IntPtrTy = DL->getIntPtrType(CI->getType()); Value *NMI = CallInst::CreateMalloc(CI, IntPtrTy, FieldTy, ConstantInt::get(IntPtrTy, TypeSize), - NElems, 0, + NElems, nullptr, CI->getName() + ".f" + Twine(FieldNo)); FieldMallocs.push_back(NMI); new StoreInst(NMI, NGV, CI); @@ -1385,7 +1388,7 @@ // Okay, the malloc site is completely handled. All of the uses of GV are now // loads, and all uses of those loads are simple. Rewrite them to use loads // of the per-field globals instead. - for (Value::use_iterator UI = GV->use_begin(), E = GV->use_end(); UI != E;) { + for (auto UI = GV->user_begin(), E = GV->user_end(); UI != E;) { Instruction *User = cast<Instruction>(*UI++); if (LoadInst *LI = dyn_cast<LoadInst>(User)) { @@ -1460,9 +1463,9 @@ Type *AllocTy, AtomicOrdering Ordering, Module::global_iterator &GVI, - DataLayout *TD, + const DataLayout *DL, TargetLibraryInfo *TLI) { - if (!TD) + if (!DL) return false; // If this is a malloc of an abstract type, don't touch it. @@ -1492,7 +1495,7 @@ // This eliminates dynamic allocation, avoids an indirection accessing the // data, and exposes the resultant global to further GlobalOpt. // We cannot optimize the malloc if we cannot determine malloc array size. - Value *NElems = getMallocArraySize(CI, TD, TLI, true); + Value *NElems = getMallocArraySize(CI, DL, TLI, true); if (!NElems) return false; @@ -1500,8 +1503,8 @@ // Restrict this transformation to only working on small allocations // (2048 bytes currently), as we don't want to introduce a 16M global or // something. - if (NElements->getZExtValue() * TD->getTypeAllocSize(AllocTy) < 2048) { - GVI = OptimizeGlobalAddressOfMalloc(GV, CI, AllocTy, NElements, TD, TLI); + if (NElements->getZExtValue() * DL->getTypeAllocSize(AllocTy) < 2048) { + GVI = OptimizeGlobalAddressOfMalloc(GV, CI, AllocTy, NElements, DL, TLI); return true; } @@ -1530,13 +1533,13 @@ // If this is a fixed size array, transform the Malloc to be an alloc of // structs. malloc [100 x struct],1 -> malloc struct, 100 if (ArrayType *AT = dyn_cast<ArrayType>(getMallocAllocatedType(CI, TLI))) { - Type *IntPtrTy = TD->getIntPtrType(CI->getType()); - unsigned TypeSize = TD->getStructLayout(AllocSTy)->getSizeInBytes(); + Type *IntPtrTy = DL->getIntPtrType(CI->getType()); + unsigned TypeSize = DL->getStructLayout(AllocSTy)->getSizeInBytes(); Value *AllocSize = ConstantInt::get(IntPtrTy, TypeSize); Value *NumElements = ConstantInt::get(IntPtrTy, AT->getNumElements()); Instruction *Malloc = CallInst::CreateMalloc(CI, IntPtrTy, AllocSTy, AllocSize, NumElements, - 0, CI->getName()); + nullptr, CI->getName()); Instruction *Cast = new BitCastInst(Malloc, CI->getType(), "tmp", CI); CI->replaceAllUsesWith(Cast); CI->eraseFromParent(); @@ -1546,8 +1549,8 @@ CI = cast<CallInst>(Malloc); } - GVI = PerformHeapAllocSRoA(GV, CI, getMallocArraySize(CI, TD, TLI, true), - TD, TLI); + GVI = PerformHeapAllocSRoA(GV, CI, getMallocArraySize(CI, DL, TLI, true), + DL, TLI); return true; } @@ -1559,7 +1562,8 @@ static bool OptimizeOnceStoredGlobal(GlobalVariable *GV, Value *StoredOnceVal, AtomicOrdering Ordering, Module::global_iterator &GVI, - DataLayout *TD, TargetLibraryInfo *TLI) { + const DataLayout *DL, + TargetLibraryInfo *TLI) { // Ignore no-op GEPs and bitcasts. StoredOnceVal = StoredOnceVal->stripPointerCasts(); @@ -1574,13 +1578,13 @@ SOVC = ConstantExpr::getBitCast(SOVC, GV->getInitializer()->getType()); // Optimize away any trapping uses of the loaded value. - if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, TD, TLI)) + if (OptimizeAwayTrappingUsesOfLoads(GV, SOVC, DL, TLI)) return true; } else if (CallInst *CI = extractMallocCall(StoredOnceVal, TLI)) { Type *MallocType = getMallocAllocatedType(CI, TLI); if (MallocType && TryToOptimizeStoreOfMallocToGlobal(GV, CI, MallocType, Ordering, GVI, - TD, TLI)) + DL, TLI)) return true; } } @@ -1607,11 +1611,9 @@ // Walk the use list of the global seeing if all the uses are load or store. // If there is anything else, bail out. - for (Value::use_iterator I = GV->use_begin(), E = GV->use_end(); I != E; ++I){ - User *U = *I; + for (User *U : GV->users()) if (!isa<LoadInst>(U) && !isa<StoreInst>(U)) return false; - } DEBUG(dbgs() << " *** SHRINKING TO BOOL: " << *GV); @@ -1636,7 +1638,7 @@ IsOneZero = InitVal->isNullValue() && CI->isOne(); while (!GV->use_empty()) { - Instruction *UI = cast<Instruction>(GV->use_back()); + Instruction *UI = cast<Instruction>(GV->user_back()); if (StoreInst *SI = dyn_cast<StoreInst>(UI)) { // Change the store into a boolean store. bool StoringOther = SI->getOperand(0) == OtherVal; @@ -1696,9 +1698,6 @@ /// possible. If we make a change, return true. bool GlobalOpt::ProcessGlobal(GlobalVariable *GV, Module::global_iterator &GVI) { - if (!GV->isDiscardableIfUnused()) - return false; - // Do more involved optimizations if the global is internal. GV->removeDeadConstantUsers(); @@ -1752,7 +1751,8 @@ ->getEntryBlock().begin()); Type *ElemTy = GV->getType()->getElementType(); // FIXME: Pass Global's alignment when globals have alignment - AllocaInst *Alloca = new AllocaInst(ElemTy, NULL, GV->getName(), &FirstI); + AllocaInst *Alloca = new AllocaInst(ElemTy, nullptr, + GV->getName(), &FirstI); if (!isa<UndefValue>(GV->getInitializer())) new StoreInst(GV->getInitializer(), Alloca, &FirstI); @@ -1774,7 +1774,7 @@ } else { // Delete any stores we can find to the global. We may not be able to // make it completely dead though. - Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer(), TD, TLI); + Changed = CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI); } // If the global is dead now, delete it. @@ -1790,7 +1790,7 @@ GV->setConstant(true); // Clean up any obviously simplifiable users now. - CleanupConstantGlobalUsers(GV, GV->getInitializer(), TD, TLI); + CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI); // If the global is dead now, just nuke it. if (GV->use_empty()) { @@ -1803,11 +1803,13 @@ ++NumMarked; return true; } else if (!GV->getInitializer()->getType()->isSingleValueType()) { - if (DataLayout *TD = getAnalysisIfAvailable<DataLayout>()) - if (GlobalVariable *FirstNewGV = SRAGlobal(GV, *TD)) { + if (DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>()) { + const DataLayout &DL = DLP->getDataLayout(); + if (GlobalVariable *FirstNewGV = SRAGlobal(GV, DL)) { GVI = FirstNewGV; // Don't skip the newly produced globals! return true; } + } } else if (GS.StoredType == GlobalStatus::StoredOnce) { // If the initial value for the global was an undef value, and if only // one other value was stored into it, we can just change the @@ -1819,7 +1821,7 @@ GV->setInitializer(SOVConstant); // Clean up any obviously simplifiable users now. - CleanupConstantGlobalUsers(GV, GV->getInitializer(), TD, TLI); + CleanupConstantGlobalUsers(GV, GV->getInitializer(), DL, TLI); if (GV->use_empty()) { DEBUG(dbgs() << " *** Substituting initializer allowed us to " @@ -1836,7 +1838,7 @@ // Try to optimize globals based on the knowledge that only one value // (besides its initializer) is ever stored to the global. if (OptimizeOnceStoredGlobal(GV, GS.StoredOnceValue, GS.Ordering, GVI, - TD, TLI)) + DL, TLI)) return true; // Otherwise, if the global was not a boolean, we can shrink it to be a @@ -1857,11 +1859,11 @@ /// ChangeCalleesToFastCall - Walk all of the direct calls of the specified /// function, changing them to FastCC. static void ChangeCalleesToFastCall(Function *F) { - for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){ - if (isa<BlockAddress>(*UI)) + for (User *U : F->users()) { + if (isa<BlockAddress>(U)) continue; - CallSite User(cast<Instruction>(*UI)); - User.setCallingConv(CallingConv::Fast); + CallSite CS(cast<Instruction>(U)); + CS.setCallingConv(CallingConv::Fast); } } @@ -1880,21 +1882,31 @@ static void RemoveNestAttribute(Function *F) { F->setAttributes(StripNest(F->getContext(), F->getAttributes())); - for (Value::use_iterator UI = F->use_begin(), E = F->use_end(); UI != E;++UI){ - if (isa<BlockAddress>(*UI)) + for (User *U : F->users()) { + if (isa<BlockAddress>(U)) continue; - CallSite User(cast<Instruction>(*UI)); - User.setAttributes(StripNest(F->getContext(), User.getAttributes())); + CallSite CS(cast<Instruction>(U)); + CS.setAttributes(StripNest(F->getContext(), CS.getAttributes())); } } +/// Return true if this is a calling convention that we'd like to change. The +/// idea here is that we don't want to mess with the convention if the user +/// explicitly requested something with performance implications like coldcc, +/// GHC, or anyregcc. +static bool isProfitableToMakeFastCC(Function *F) { + CallingConv::ID CC = F->getCallingConv(); + // FIXME: Is it worth transforming x86_stdcallcc and x86_fastcallcc? + return CC == CallingConv::C || CC == CallingConv::X86_ThisCall; +} + bool GlobalOpt::OptimizeFunctions(Module &M) { bool Changed = false; // Optimize functions. for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) { Function *F = FI++; // Functions without names cannot be referenced outside this module. - if (!F->hasName() && !F->isDeclaration()) + if (!F->hasName() && !F->isDeclaration() && !F->hasLocalLinkage()) F->setLinkage(GlobalValue::InternalLinkage); F->removeDeadConstantUsers(); if (F->isDefTriviallyDead()) { @@ -1902,11 +1914,11 @@ Changed = true; ++NumFnDeleted; } else if (F->hasLocalLinkage()) { - if (F->getCallingConv() == CallingConv::C && !F->isVarArg() && + if (isProfitableToMakeFastCC(F) && !F->isVarArg() && !F->hasAddressTaken()) { - // If this function has C calling conventions, is not a varargs - // function, and is only called directly, promote it to use the Fast - // calling convention. + // If this function has a calling convention worth changing, is not a + // varargs function, and is only called directly, promote it to use the + // Fast calling convention. F->setCallingConv(CallingConv::Fast); ChangeCalleesToFastCall(F); ++NumFastCallFns; @@ -1928,139 +1940,41 @@ bool GlobalOpt::OptimizeGlobalVars(Module &M) { bool Changed = false; + + SmallSet<const Comdat *, 8> NotDiscardableComdats; + for (const GlobalVariable &GV : M.globals()) + if (const Comdat *C = GV.getComdat()) + if (!GV.isDiscardableIfUnused()) + NotDiscardableComdats.insert(C); + for (Module::global_iterator GVI = M.global_begin(), E = M.global_end(); GVI != E; ) { GlobalVariable *GV = GVI++; // Global variables without names cannot be referenced outside this module. - if (!GV->hasName() && !GV->isDeclaration()) + if (!GV->hasName() && !GV->isDeclaration() && !GV->hasLocalLinkage()) GV->setLinkage(GlobalValue::InternalLinkage); // Simplify the initializer. if (GV->hasInitializer()) if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GV->getInitializer())) { - Constant *New = ConstantFoldConstantExpression(CE, TD, TLI); + Constant *New = ConstantFoldConstantExpression(CE, DL, TLI); if (New && New != CE) GV->setInitializer(New); } - Changed |= ProcessGlobal(GV, GVI); + if (GV->isDiscardableIfUnused()) { + if (const Comdat *C = GV->getComdat()) + if (NotDiscardableComdats.count(C)) + continue; + Changed |= ProcessGlobal(GV, GVI); + } } return Changed; } -/// FindGlobalCtors - Find the llvm.global_ctors list, verifying that all -/// initializers have an init priority of 65535. -GlobalVariable *GlobalOpt::FindGlobalCtors(Module &M) { - GlobalVariable *GV = M.getGlobalVariable("llvm.global_ctors"); - if (GV == 0) return 0; - - // Verify that the initializer is simple enough for us to handle. We are - // only allowed to optimize the initializer if it is unique. - if (!GV->hasUniqueInitializer()) return 0; - - if (isa<ConstantAggregateZero>(GV->getInitializer())) - return GV; - ConstantArray *CA = cast<ConstantArray>(GV->getInitializer()); - - for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) { - if (isa<ConstantAggregateZero>(*i)) - continue; - ConstantStruct *CS = cast<ConstantStruct>(*i); - if (isa<ConstantPointerNull>(CS->getOperand(1))) - continue; - - // Must have a function or null ptr. - if (!isa<Function>(CS->getOperand(1))) - return 0; - - // Init priority must be standard. - ConstantInt *CI = cast<ConstantInt>(CS->getOperand(0)); - if (CI->getZExtValue() != 65535) - return 0; - } - - return GV; -} - -/// ParseGlobalCtors - Given a llvm.global_ctors list that we can understand, -/// return a list of the functions and null terminator as a vector. -static std::vector<Function*> ParseGlobalCtors(GlobalVariable *GV) { - if (GV->getInitializer()->isNullValue()) - return std::vector<Function*>(); - ConstantArray *CA = cast<ConstantArray>(GV->getInitializer()); - std::vector<Function*> Result; - Result.reserve(CA->getNumOperands()); - for (User::op_iterator i = CA->op_begin(), e = CA->op_end(); i != e; ++i) { - ConstantStruct *CS = cast<ConstantStruct>(*i); - Result.push_back(dyn_cast<Function>(CS->getOperand(1))); - } - return Result; -} - -/// InstallGlobalCtors - Given a specified llvm.global_ctors list, install the -/// specified array, returning the new global to use. -static GlobalVariable *InstallGlobalCtors(GlobalVariable *GCL, - const std::vector<Function*> &Ctors) { - // If we made a change, reassemble the initializer list. - Constant *CSVals[2]; - CSVals[0] = ConstantInt::get(Type::getInt32Ty(GCL->getContext()), 65535); - CSVals[1] = 0; - - StructType *StructTy = - cast<StructType>(GCL->getType()->getElementType()->getArrayElementType()); - - // Create the new init list. - std::vector<Constant*> CAList; - for (unsigned i = 0, e = Ctors.size(); i != e; ++i) { - if (Ctors[i]) { - CSVals[1] = Ctors[i]; - } else { - Type *FTy = FunctionType::get(Type::getVoidTy(GCL->getContext()), - false); - PointerType *PFTy = PointerType::getUnqual(FTy); - CSVals[1] = Constant::getNullValue(PFTy); - CSVals[0] = ConstantInt::get(Type::getInt32Ty(GCL->getContext()), - 0x7fffffff); - } - CAList.push_back(ConstantStruct::get(StructTy, CSVals)); - } - - // Create the array initializer. - Constant *CA = ConstantArray::get(ArrayType::get(StructTy, - CAList.size()), CAList); - - // If we didn't change the number of elements, don't create a new GV. - if (CA->getType() == GCL->getInitializer()->getType()) { - GCL->setInitializer(CA); - return GCL; - } - - // Create the new global and insert it next to the existing list. - GlobalVariable *NGV = new GlobalVariable(CA->getType(), GCL->isConstant(), - GCL->getLinkage(), CA, "", - GCL->getThreadLocalMode()); - GCL->getParent()->getGlobalList().insert(GCL, NGV); - NGV->takeName(GCL); - - // Nuke the old list, replacing any uses with the new one. - if (!GCL->use_empty()) { - Constant *V = NGV; - if (V->getType() != GCL->getType()) - V = ConstantExpr::getBitCast(V, GCL->getType()); - GCL->replaceAllUsesWith(V); - } - GCL->eraseFromParent(); - - if (Ctors.size()) - return NGV; - else - return 0; -} - - static inline bool isSimpleEnoughValueToCommit(Constant *C, - SmallPtrSet<Constant*, 8> &SimpleConstants, - const DataLayout *TD); + SmallPtrSetImpl<Constant*> &SimpleConstants, + const DataLayout *DL); /// isSimpleEnoughValueToCommit - Return true if the specified constant can be @@ -2072,12 +1986,15 @@ /// in SimpleConstants to avoid having to rescan the same constants all the /// time. static bool isSimpleEnoughValueToCommitHelper(Constant *C, - SmallPtrSet<Constant*, 8> &SimpleConstants, - const DataLayout *TD) { - // Simple integer, undef, constant aggregate zero, global addresses, etc are - // all supported. - if (C->getNumOperands() == 0 || isa<BlockAddress>(C) || - isa<GlobalValue>(C)) + SmallPtrSetImpl<Constant*> &SimpleConstants, + const DataLayout *DL) { + // Simple global addresses are supported, do not allow dllimport or + // thread-local globals. + if (auto *GV = dyn_cast<GlobalValue>(C)) + return !GV->hasDLLImportStorageClass() && !GV->isThreadLocal(); + + // Simple integer, undef, constant aggregate zero, etc are all supported. + if (C->getNumOperands() == 0 || isa<BlockAddress>(C)) return true; // Aggregate values are safe if all their elements are. @@ -2085,7 +2002,7 @@ isa<ConstantVector>(C)) { for (unsigned i = 0, e = C->getNumOperands(); i != e; ++i) { Constant *Op = cast<Constant>(C->getOperand(i)); - if (!isSimpleEnoughValueToCommit(Op, SimpleConstants, TD)) + if (!isSimpleEnoughValueToCommit(Op, SimpleConstants, DL)) return false; } return true; @@ -2098,41 +2015,41 @@ switch (CE->getOpcode()) { case Instruction::BitCast: // Bitcast is fine if the casted value is fine. - return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, TD); + return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); case Instruction::IntToPtr: case Instruction::PtrToInt: // int <=> ptr is fine if the int type is the same size as the // pointer type. - if (!TD || TD->getTypeSizeInBits(CE->getType()) != - TD->getTypeSizeInBits(CE->getOperand(0)->getType())) + if (!DL || DL->getTypeSizeInBits(CE->getType()) != + DL->getTypeSizeInBits(CE->getOperand(0)->getType())) return false; - return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, TD); + return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); // GEP is fine if it is simple + constant offset. case Instruction::GetElementPtr: for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i) if (!isa<ConstantInt>(CE->getOperand(i))) return false; - return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, TD); + return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); case Instruction::Add: // We allow simple+cst. if (!isa<ConstantInt>(CE->getOperand(1))) return false; - return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, TD); + return isSimpleEnoughValueToCommit(CE->getOperand(0), SimpleConstants, DL); } return false; } static inline bool isSimpleEnoughValueToCommit(Constant *C, - SmallPtrSet<Constant*, 8> &SimpleConstants, - const DataLayout *TD) { + SmallPtrSetImpl<Constant*> &SimpleConstants, + const DataLayout *DL) { // If we already checked this constant, we win. if (!SimpleConstants.insert(C)) return true; // Check the constant. - return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, TD); + return isSimpleEnoughValueToCommitHelper(C, SimpleConstants, DL); } @@ -2148,8 +2065,7 @@ return false; if (GlobalVariable *GV = dyn_cast<GlobalVariable>(C)) - // Do not allow weak/*_odr/linkonce/dllimport/dllexport linkage or - // external globals. + // Do not allow weak/*_odr/linkonce linkage or external globals. return GV->hasUniqueInitializer(); if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { @@ -2164,7 +2080,7 @@ return false; // The first index must be zero. - ConstantInt *CI = dyn_cast<ConstantInt>(*llvm::next(CE->op_begin())); + ConstantInt *CI = dyn_cast<ConstantInt>(*std::next(CE->op_begin())); if (!CI || !CI->isZero()) return false; // The remaining indices must be compile-time known integers within the @@ -2259,24 +2175,18 @@ /// Once an evaluation call fails, the evaluation object should not be reused. class Evaluator { public: - Evaluator(const DataLayout *TD, const TargetLibraryInfo *TLI) - : TD(TD), TLI(TLI) { - ValueStack.push_back(new DenseMap<Value*, Constant*>); + Evaluator(const DataLayout *DL, const TargetLibraryInfo *TLI) + : DL(DL), TLI(TLI) { + ValueStack.emplace_back(); } ~Evaluator() { - DeleteContainerPointers(ValueStack); - while (!AllocaTmps.empty()) { - GlobalVariable *Tmp = AllocaTmps.back(); - AllocaTmps.pop_back(); - + for (auto &Tmp : AllocaTmps) // If there are still users of the alloca, the program is doing something // silly, e.g. storing the address of the alloca somewhere and using it // later. Since this is undefined, we'll just make it be null. if (!Tmp->use_empty()) Tmp->replaceAllUsesWith(Constant::getNullValue(Tmp->getType())); - delete Tmp; - } } /// EvaluateFunction - Evaluate a call to function F, returning true if @@ -2292,20 +2202,20 @@ Constant *getVal(Value *V) { if (Constant *CV = dyn_cast<Constant>(V)) return CV; - Constant *R = ValueStack.back()->lookup(V); + Constant *R = ValueStack.back().lookup(V); assert(R && "Reference to an uncomputed value!"); return R; } void setVal(Value *V, Constant *C) { - ValueStack.back()->operator[](V) = C; + ValueStack.back()[V] = C; } const DenseMap<Constant*, Constant*> &getMutatedMemory() const { return MutatedMemory; } - const SmallPtrSet<GlobalVariable*, 8> &getInvariants() const { + const SmallPtrSetImpl<GlobalVariable*> &getInvariants() const { return Invariants; } @@ -2313,9 +2223,9 @@ Constant *ComputeLoadResult(Constant *P); /// ValueStack - As we compute SSA register values, we store their contents - /// here. The back of the vector contains the current function and the stack + /// here. The back of the deque contains the current function and the stack /// contains the values in the calling frames. - SmallVector<DenseMap<Value*, Constant*>*, 4> ValueStack; + std::deque<DenseMap<Value*, Constant*>> ValueStack; /// CallStack - This is used to detect recursion. In pathological situations /// we could hit exponential behavior, but at least there is nothing @@ -2330,7 +2240,7 @@ /// AllocaTmps - To 'execute' an alloca, we create a temporary global variable /// to represent its body. This vector is needed so we can delete the /// temporary globals when we are done. - SmallVector<GlobalVariable*, 32> AllocaTmps; + SmallVector<std::unique_ptr<GlobalVariable>, 32> AllocaTmps; /// Invariants - These global variables have been marked invariant by the /// static constructor. @@ -2340,7 +2250,7 @@ /// simple enough to live in a static initializer of a global. SmallPtrSet<Constant*, 8> SimpleConstants; - const DataLayout *TD; + const DataLayout *DL; const TargetLibraryInfo *TLI; }; @@ -2359,7 +2269,7 @@ if (GlobalVariable *GV = dyn_cast<GlobalVariable>(P)) { if (GV->hasDefinitiveInitializer()) return GV->getInitializer(); - return 0; + return nullptr; } // Handle a constantexpr getelementptr. @@ -2371,7 +2281,7 @@ return ConstantFoldLoadThroughGEPConstantExpr(GV->getInitializer(), CE); } - return 0; // don't know how to evaluate. + return nullptr; // don't know how to evaluate. } /// EvaluateBlock - Evaluate all instructions in block BB, returning true if @@ -2381,7 +2291,7 @@ BasicBlock *&NextBB) { // This is the main evaluation loop. while (1) { - Constant *InstResult = 0; + Constant *InstResult = nullptr; DEBUG(dbgs() << "Evaluating Instruction: " << *CurInst << "\n"); @@ -2393,7 +2303,7 @@ Constant *Ptr = getVal(SI->getOperand(1)); if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) { DEBUG(dbgs() << "Folding constant ptr expression: " << *Ptr); - Ptr = ConstantFoldConstantExpression(CE, TD, TLI); + Ptr = ConstantFoldConstantExpression(CE, DL, TLI); DEBUG(dbgs() << "; To: " << *Ptr << "\n"); } if (!isSimpleEnoughPointerToCommit(Ptr)) { @@ -2406,7 +2316,7 @@ // If this might be too difficult for the backend to handle (e.g. the addr // of one global variable divided by another) then we can't commit it. - if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, TD)) { + if (!isSimpleEnoughValueToCommit(Val, SimpleConstants, DL)) { DEBUG(dbgs() << "Store value is too complex to evaluate store. " << *Val << "\n"); return false; @@ -2438,7 +2348,7 @@ Ptr = ConstantExpr::getGetElementPtr(Ptr, IdxList); if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) - Ptr = ConstantFoldConstantExpression(CE, TD, TLI); + Ptr = ConstantFoldConstantExpression(CE, DL, TLI); // If we can't improve the situation by introspecting NewTy, // we have to give up. @@ -2482,6 +2392,17 @@ getVal(SI->getOperand(2))); DEBUG(dbgs() << "Found a Select! Simplifying: " << *InstResult << "\n"); + } else if (auto *EVI = dyn_cast<ExtractValueInst>(CurInst)) { + InstResult = ConstantExpr::getExtractValue( + getVal(EVI->getAggregateOperand()), EVI->getIndices()); + DEBUG(dbgs() << "Found an ExtractValueInst! Simplifying: " << *InstResult + << "\n"); + } else if (auto *IVI = dyn_cast<InsertValueInst>(CurInst)) { + InstResult = ConstantExpr::getInsertValue( + getVal(IVI->getAggregateOperand()), + getVal(IVI->getInsertedValueOperand()), IVI->getIndices()); + DEBUG(dbgs() << "Found an InsertValueInst! Simplifying: " << *InstResult + << "\n"); } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(CurInst)) { Constant *P = getVal(GEP->getOperand(0)); SmallVector<Constant*, 8> GEPOps; @@ -2502,12 +2423,12 @@ Constant *Ptr = getVal(LI->getOperand(0)); if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Ptr)) { - Ptr = ConstantFoldConstantExpression(CE, TD, TLI); + Ptr = ConstantFoldConstantExpression(CE, DL, TLI); DEBUG(dbgs() << "Found a constant pointer expression, constant " "folding: " << *Ptr << "\n"); } InstResult = ComputeLoadResult(Ptr); - if (InstResult == 0) { + if (!InstResult) { DEBUG(dbgs() << "Failed to compute load result. Can not evaluate load." "\n"); return false; // Could not evaluate load. @@ -2520,11 +2441,10 @@ return false; // Cannot handle array allocs. } Type *Ty = AI->getType()->getElementType(); - AllocaTmps.push_back(new GlobalVariable(Ty, false, - GlobalValue::InternalLinkage, - UndefValue::get(Ty), - AI->getName())); - InstResult = AllocaTmps.back(); + AllocaTmps.push_back( + make_unique<GlobalVariable>(Ty, false, GlobalValue::InternalLinkage, + UndefValue::get(Ty), AI->getName())); + InstResult = AllocaTmps.back().get(); DEBUG(dbgs() << "Found an alloca. Result: " << *InstResult << "\n"); } else if (isa<CallInst>(CurInst) || isa<InvokeInst>(CurInst)) { CallSite CS(CurInst); @@ -2579,9 +2499,9 @@ Value *Ptr = PtrArg->stripPointerCasts(); if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Ptr)) { Type *ElemTy = cast<PointerType>(GV->getType())->getElementType(); - if (TD && !Size->isAllOnesValue() && + if (DL && !Size->isAllOnesValue() && Size->getValue().getLimitedValue() >= - TD->getTypeStoreSize(ElemTy)) { + DL->getTypeStoreSize(ElemTy)) { Invariants.insert(GV); DEBUG(dbgs() << "Found a global var that is an invariant: " << *GV << "\n"); @@ -2626,17 +2546,17 @@ return false; } - Constant *RetVal = 0; + Constant *RetVal = nullptr; // Execute the call, if successful, use the return value. - ValueStack.push_back(new DenseMap<Value*, Constant*>); + ValueStack.emplace_back(); if (!EvaluateFunction(Callee, RetVal, Formals)) { DEBUG(dbgs() << "Failed to evaluate function.\n"); return false; } - delete ValueStack.pop_back_val(); + ValueStack.pop_back(); InstResult = RetVal; - if (InstResult != NULL) { + if (InstResult) { DEBUG(dbgs() << "Successfully evaluated function. Result: " << InstResult << "\n\n"); } else { @@ -2668,7 +2588,7 @@ else return false; // Cannot determine. } else if (isa<ReturnInst>(CurInst)) { - NextBB = 0; + NextBB = nullptr; } else { // invoke, unwind, resume, unreachable. DEBUG(dbgs() << "Can not handle terminator."); @@ -2687,7 +2607,7 @@ if (!CurInst->use_empty()) { if (ConstantExpr *CE = dyn_cast<ConstantExpr>(InstResult)) - InstResult = ConstantFoldConstantExpression(CE, TD, TLI); + InstResult = ConstantFoldConstantExpression(CE, DL, TLI); setVal(CurInst, InstResult); } @@ -2733,13 +2653,13 @@ BasicBlock::iterator CurInst = CurBB->begin(); while (1) { - BasicBlock *NextBB = 0; // Initialized to avoid compiler warnings. + BasicBlock *NextBB = nullptr; // Initialized to avoid compiler warnings. DEBUG(dbgs() << "Trying to evaluate BB: " << *CurBB << "\n"); if (!EvaluateBlock(CurInst, NextBB)) return false; - if (NextBB == 0) { + if (!NextBB) { // Successfully running until there's no next block means that we found // the return. Fill it the return value and pop the call stack. ReturnInst *RI = cast<ReturnInst>(CurBB->getTerminator()); @@ -2758,7 +2678,7 @@ // Okay, we have never been in this block before. Check to see if there // are any PHI nodes. If so, evaluate them with information about where // we came from. - PHINode *PN = 0; + PHINode *PN = nullptr; for (CurInst = NextBB->begin(); (PN = dyn_cast<PHINode>(CurInst)); ++CurInst) setVal(PN, getVal(PN->getIncomingValueForBlock(CurBB))); @@ -2770,15 +2690,17 @@ /// EvaluateStaticConstructor - Evaluate static constructors in the function, if /// we can. Return true if we can, false otherwise. -static bool EvaluateStaticConstructor(Function *F, const DataLayout *TD, +static bool EvaluateStaticConstructor(Function *F, const DataLayout *DL, const TargetLibraryInfo *TLI) { // Call the function. - Evaluator Eval(TD, TLI); + Evaluator Eval(DL, TLI); Constant *RetValDummy; bool EvalSuccess = Eval.EvaluateFunction(F, RetValDummy, SmallVector<Constant*, 0>()); if (EvalSuccess) { + ++NumCtorsEvaluated; + // We succeeded at evaluation: commit the result. DEBUG(dbgs() << "FULLY EVALUATED GLOBAL CTOR FUNCTION '" << F->getName() << "' to " << Eval.getMutatedMemory().size() @@ -2787,72 +2709,31 @@ Eval.getMutatedMemory().begin(), E = Eval.getMutatedMemory().end(); I != E; ++I) CommitValueTo(I->second, I->first); - for (SmallPtrSet<GlobalVariable*, 8>::const_iterator I = - Eval.getInvariants().begin(), E = Eval.getInvariants().end(); - I != E; ++I) - (*I)->setConstant(true); + for (GlobalVariable *GV : Eval.getInvariants()) + GV->setConstant(true); } return EvalSuccess; } -/// OptimizeGlobalCtorsList - Simplify and evaluation global ctors if possible. -/// Return true if anything changed. -bool GlobalOpt::OptimizeGlobalCtorsList(GlobalVariable *&GCL) { - std::vector<Function*> Ctors = ParseGlobalCtors(GCL); - bool MadeChange = false; - if (Ctors.empty()) return false; - - // Loop over global ctors, optimizing them when we can. - for (unsigned i = 0; i != Ctors.size(); ++i) { - Function *F = Ctors[i]; - // Found a null terminator in the middle of the list, prune off the rest of - // the list. - if (F == 0) { - if (i != Ctors.size()-1) { - Ctors.resize(i+1); - MadeChange = true; - } - break; - } - DEBUG(dbgs() << "Optimizing Global Constructor: " << *F << "\n"); - - // We cannot simplify external ctor functions. - if (F->empty()) continue; - - // If we can evaluate the ctor at compile time, do. - if (EvaluateStaticConstructor(F, TD, TLI)) { - Ctors.erase(Ctors.begin()+i); - MadeChange = true; - --i; - ++NumCtorsEvaluated; - continue; - } - } - - if (!MadeChange) return false; - - GCL = InstallGlobalCtors(GCL, Ctors); - return true; -} - static int compareNames(Constant *const *A, Constant *const *B) { return (*A)->getName().compare((*B)->getName()); } static void setUsedInitializer(GlobalVariable &V, - SmallPtrSet<GlobalValue *, 8> Init) { + const SmallPtrSet<GlobalValue *, 8> &Init) { if (Init.empty()) { V.eraseFromParent(); return; } + // Type of pointer to the array of pointers. + PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext(), 0); + SmallVector<llvm::Constant *, 8> UsedArray; - PointerType *Int8PtrTy = Type::getInt8PtrTy(V.getContext()); - - for (SmallPtrSet<GlobalValue *, 8>::iterator I = Init.begin(), E = Init.end(); - I != E; ++I) { - Constant *Cast = llvm::ConstantExpr::getBitCast(*I, Int8PtrTy); + for (GlobalValue *GV : Init) { + Constant *Cast + = ConstantExpr::getPointerBitCastOrAddrSpaceCast(GV, Int8PtrTy); UsedArray.push_back(Cast); } // Sort to get deterministic order. @@ -2883,10 +2764,17 @@ CompilerUsedV = collectUsedGlobalVariables(M, CompilerUsed, true); } typedef SmallPtrSet<GlobalValue *, 8>::iterator iterator; + typedef iterator_range<iterator> used_iterator_range; iterator usedBegin() { return Used.begin(); } iterator usedEnd() { return Used.end(); } + used_iterator_range used() { + return used_iterator_range(usedBegin(), usedEnd()); + } iterator compilerUsedBegin() { return CompilerUsed.begin(); } iterator compilerUsedEnd() { return CompilerUsed.end(); } + used_iterator_range compilerUsed() { + return used_iterator_range(compilerUsedBegin(), compilerUsedEnd()); + } bool usedCount(GlobalValue *GV) const { return Used.count(GV); } bool compilerUsedCount(GlobalValue *GV) const { return CompilerUsed.count(GV); @@ -2939,7 +2827,8 @@ return U.usedCount(&GA) || U.compilerUsedCount(&GA); } -static bool hasUsesToReplace(GlobalAlias &GA, LLVMUsed &U, bool &RenameTarget) { +static bool hasUsesToReplace(GlobalAlias &GA, const LLVMUsed &U, + bool &RenameTarget) { RenameTarget = false; bool Ret = false; if (hasUseOtherThanLLVMUsed(GA, U)) @@ -2974,23 +2863,26 @@ bool Changed = false; LLVMUsed Used(M); - for (SmallPtrSet<GlobalValue *, 8>::iterator I = Used.usedBegin(), - E = Used.usedEnd(); - I != E; ++I) - Used.compilerUsedErase(*I); + for (GlobalValue *GV : Used.used()) + Used.compilerUsedErase(GV); for (Module::alias_iterator I = M.alias_begin(), E = M.alias_end(); I != E;) { Module::alias_iterator J = I++; // Aliases without names cannot be referenced outside this module. - if (!J->hasName() && !J->isDeclaration()) + if (!J->hasName() && !J->isDeclaration() && !J->hasLocalLinkage()) J->setLinkage(GlobalValue::InternalLinkage); // If the aliasee may change at link time, nothing can be done - bail out. if (J->mayBeOverridden()) continue; Constant *Aliasee = J->getAliasee(); - GlobalValue *Target = cast<GlobalValue>(Aliasee->stripPointerCasts()); + GlobalValue *Target = dyn_cast<GlobalValue>(Aliasee->stripPointerCasts()); + // We can't trivially replace the alias with the aliasee if the aliasee is + // non-trivial in some way. + // TODO: Try to handle non-zero GEPs of local aliasees. + if (!Target) + continue; Target->removeDeadConstantUsers(); // Make all users of the alias use the aliasee instead. @@ -2998,7 +2890,7 @@ if (!hasUsesToReplace(*J, Used, RenameTarget)) continue; - J->replaceAllUsesWith(Aliasee); + J->replaceAllUsesWith(ConstantExpr::getBitCast(Aliasee, J->getType())); ++NumAliasesResolved; Changed = true; @@ -3006,7 +2898,8 @@ // Give the aliasee the name, linkage and other attributes of the alias. Target->takeName(J); Target->setLinkage(J->getLinkage()); - Target->GlobalValue::copyAttributesFrom(J); + Target->setVisibility(J->getVisibility()); + Target->setDLLStorageClass(J->getDLLStorageClass()); if (Used.usedErase(J)) Used.usedInsert(Target); @@ -3029,12 +2922,12 @@ static Function *FindCXAAtExit(Module &M, TargetLibraryInfo *TLI) { if (!TLI->has(LibFunc::cxa_atexit)) - return 0; + return nullptr; Function *Fn = M.getFunction(TLI->getName(LibFunc::cxa_atexit)); if (!Fn) - return 0; + return nullptr; FunctionType *FTy = Fn->getFunctionType(); @@ -3045,7 +2938,7 @@ !FTy->getParamType(0)->isPointerTy() || !FTy->getParamType(1)->isPointerTy() || !FTy->getParamType(2)->isPointerTy()) - return 0; + return nullptr; return Fn; } @@ -3113,8 +3006,8 @@ // and remove them. bool Changed = false; - for (Function::use_iterator I = CXAAtExitFn->use_begin(), - E = CXAAtExitFn->use_end(); I != E;) { + for (auto I = CXAAtExitFn->user_begin(), E = CXAAtExitFn->user_end(); + I != E;) { // We're only interested in calls. Theoretically, we could handle invoke // instructions as well, but neither llvm-gcc nor clang generate invokes // to __cxa_atexit. @@ -3146,12 +3039,10 @@ bool GlobalOpt::runOnModule(Module &M) { bool Changed = false; - TD = getAnalysisIfAvailable<DataLayout>(); + DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); + DL = DLP ? &DLP->getDataLayout() : nullptr; TLI = &getAnalysis<TargetLibraryInfo>(); - // Try to find the llvm.globalctors list. - GlobalVariable *GlobalCtors = FindGlobalCtors(M); - bool LocalChange = true; while (LocalChange) { LocalChange = false; @@ -3160,8 +3051,9 @@ LocalChange |= OptimizeFunctions(M); // Optimize global_ctors list. - if (GlobalCtors) - LocalChange |= OptimizeGlobalCtorsList(GlobalCtors); + LocalChange |= optimizeGlobalCtorsList(M, [&](Function *F) { + return EvaluateStaticConstructor(F, DL, TLI); + }); // Optimize non-address-taken globals. LocalChange |= OptimizeGlobalVars(M);