From 25db58032d94e2a2899dbc8b32d38b4a59f44077 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 7 Oct 2004 04:16:33 +0000 Subject: * Rename pass to globalopt, since we do more than just constify * Instead of handling dead functions specially, just nuke them. * Be more aggressive about cleaning up after constification, in particular, handle getelementptr instructions and constantexprs. * Be a little bit more structured about how we process globals. *** Delete globals that are only stored to, and never read. These are clearly not useful, so they should go. This implements deadglobal.llx This last one triggers quite a few times. In particular, 2208 in the external tests, 1865 of which are in 252.eon. This shrinks eon from 1995094 to 1732341 bytes of bytecode. llvm-svn: 16802 --- llvm/lib/Transforms/IPO/GlobalConstifier.cpp | 147 ---------------- llvm/lib/Transforms/IPO/GlobalOpt.cpp | 250 +++++++++++++++++++++++++++ 2 files changed, 250 insertions(+), 147 deletions(-) delete mode 100644 llvm/lib/Transforms/IPO/GlobalConstifier.cpp create mode 100644 llvm/lib/Transforms/IPO/GlobalOpt.cpp (limited to 'llvm/lib') diff --git a/llvm/lib/Transforms/IPO/GlobalConstifier.cpp b/llvm/lib/Transforms/IPO/GlobalConstifier.cpp deleted file mode 100644 index 3a5a351a3a0..00000000000 --- a/llvm/lib/Transforms/IPO/GlobalConstifier.cpp +++ /dev/null @@ -1,147 +0,0 @@ -//===- GlobalConstifier.cpp - Mark read-only globals constant -------------===// -// -// The LLVM Compiler Infrastructure -// -// This file was developed by the LLVM research group and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// This pass loops over the non-constant internal global variables in the -// program. If it can prove that they are never written to, it marks them -// constant. -// -// NOTE: this should eventually use the alias analysis interfaces to do the -// transformation, but for now we just stick with a simple solution. DSA in -// particular could give a much more accurate answer to the mod/ref query, but -// it's not quite ready for this. -// -//===----------------------------------------------------------------------===// - -#include "llvm/Transforms/IPO.h" -#include "llvm/Constants.h" -#include "llvm/Instructions.h" -#include "llvm/Module.h" -#include "llvm/Pass.h" -#include "llvm/Support/Debug.h" -#include "llvm/ADT/Statistic.h" -#include -#include -using namespace llvm; - -namespace { - Statistic<> NumMarked ("constify", "Number of globals marked constant"); - Statistic<> NumDeleted("constify", "Number of globals deleted"); - - struct Constifier : public ModulePass { - bool runOnModule(Module &M); - }; - - RegisterOpt X("constify", "Global Constifier"); -} - -ModulePass *llvm::createGlobalConstifierPass() { return new Constifier(); } - -/// A lot of global constants are stored only in trivially dead setter -/// functions. Because we don't want to cycle between globaldce and this pass, -/// just do a simple check to catch the common case. -static bool ContainingFunctionIsTriviallyDead(Instruction *I) { - Function *F = I->getParent()->getParent(); - if (!F->hasInternalLinkage()) return false; - F->removeDeadConstantUsers(); - return F->use_empty(); -} - - -/// isStoredThrough - Return false if the specified pointer is provably never -/// stored through. If we can't tell, we must conservatively assume it might. -/// -static bool isStoredThrough(Value *V, std::set &PHIUsers) { - for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) - if (ConstantExpr *CE = dyn_cast(*UI)) { - if (isStoredThrough(CE, PHIUsers)) - return true; - } else if (Instruction *I = dyn_cast(*UI)) { - if (!ContainingFunctionIsTriviallyDead(I)) { - if (I->getOpcode() == Instruction::GetElementPtr || - I->getOpcode() == Instruction::Select) { - if (isStoredThrough(I, PHIUsers)) return true; - } else if (PHINode *PN = dyn_cast(I)) { - // PHI nodes we can check just like select or GEP instructions, but we - // have to be careful about infinite recursion. - if (PHIUsers.insert(PN).second) // Not already visited. - if (isStoredThrough(I, PHIUsers)) return true; - } else if (StoreInst *SI = dyn_cast(I)) { - // If this store is just storing the initializer into a global - // (i.e. not changing the value), ignore it. For now we just handle - // direct stores, no stores to fields of aggregates. - if (!isa(SI->getOperand(1))) - return true; - Constant *GVInit = - cast(SI->getOperand(1))->getInitializer(); - if (SI->getOperand(0) != GVInit) - return true; - } else if (!isa(I) && !isa(I)) { - return true; // Any other non-load instruction might store! - } - } - } else { - // Otherwise must be a global or some other user. - return true; - } - - return false; -} - -/// CleanupConstantGlobalUsers - We just marked GV constant. Loop over all -/// users of the global, cleaning up the obvious ones. This is largely just a -/// quick scan over the use list to clean up the easy and obvious cruft. -static void CleanupConstantGlobalUsers(GlobalVariable *GV) { - Constant *Init = GV->getInitializer(); - if (!Init->getType()->isFirstClassType()) - return; // We can't simplify aggregates yet! - - std::vector Users(GV->use_begin(), GV->use_end()); - - std::sort(Users.begin(), Users.end()); - Users.erase(std::unique(Users.begin(), Users.end()), Users.end()); - for (unsigned i = 0, e = Users.size(); i != e; ++i) { - if (LoadInst *LI = dyn_cast(Users[i])) { - // Replace the load with the initializer. - LI->replaceAllUsesWith(Init); - LI->getParent()->getInstList().erase(LI); - } else if (StoreInst *SI = dyn_cast(Users[i])) { - // Store must be unreachable or storing Init into the global. - SI->getParent()->getInstList().erase(SI); - } - } -} - - -bool Constifier::runOnModule(Module &M) { - bool Changed = false; - std::set PHIUsers; - for (Module::giterator GVI = M.gbegin(), E = M.gend(); GVI != E;) { - GlobalVariable *GV = GVI++; - if (!GV->isConstant() && GV->hasInternalLinkage() && GV->hasInitializer()) { - if (!isStoredThrough(GV, PHIUsers)) { - DEBUG(std::cerr << "MARKING CONSTANT: " << *GV << "\n"); - GV->setConstant(true); - - // Clean up any obviously simplifiable users now. - CleanupConstantGlobalUsers(GV); - - // If the global is dead now, just nuke it. - if (GV->use_empty()) { - M.getGlobalList().erase(GV); - ++NumDeleted; - } - - ++NumMarked; - Changed = true; - } - PHIUsers.clear(); - } - } - return Changed; -} diff --git a/llvm/lib/Transforms/IPO/GlobalOpt.cpp b/llvm/lib/Transforms/IPO/GlobalOpt.cpp new file mode 100644 index 00000000000..8e563cb07b4 --- /dev/null +++ b/llvm/lib/Transforms/IPO/GlobalOpt.cpp @@ -0,0 +1,250 @@ +//===- GlobalOpt.cpp - Optimize Global Variables --------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This pass transforms simple global variables that never have their address +// taken. If obviously true, it marks read/write globals as constant, deletes +// variables only stored to, etc. +// +//===----------------------------------------------------------------------===// + +#define DEBUG_TYPE "globalopt" +#include "llvm/Transforms/IPO.h" +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" +#include "llvm/Instructions.h" +#include "llvm/Module.h" +#include "llvm/Pass.h" +#include "llvm/Support/Debug.h" +#include "llvm/ADT/Statistic.h" +#include +#include +using namespace llvm; + +namespace { + Statistic<> NumMarked ("globalopt", "Number of globals marked constant"); + Statistic<> NumDeleted("globalopt", "Number of globals deleted"); + Statistic<> NumFnDeleted("globalopt", "Number of functions deleted"); + + struct GlobalOpt : public ModulePass { + bool runOnModule(Module &M); + }; + + RegisterOpt X("globalopt", "Global Variable Optimizer"); +} + +ModulePass *llvm::createGlobalOptimizerPass() { return new GlobalOpt(); } + +/// GlobalStatus - As we analyze each global, keep track of some information +/// about it. If we find out that the address of the global is taken, none of +/// the other info will be accurate. +struct GlobalStatus { + bool isLoaded; + enum StoredType { + NotStored, isInitializerStored, isMallocStored, isStored + } StoredType; + bool isNotSuitableForSRA; + + GlobalStatus() : isLoaded(false), StoredType(NotStored), + isNotSuitableForSRA(false) {} +}; + +/// AnalyzeGlobal - Look at all uses of the global and fill in the GlobalStatus +/// structure. If the global has its address taken, return true to indicate we +/// can't do anything with it. +/// +static bool AnalyzeGlobal(Value *V, GlobalStatus &GS, + std::set &PHIUsers) { + for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E; ++UI) + if (ConstantExpr *CE = dyn_cast(*UI)) { + if (AnalyzeGlobal(CE, GS, PHIUsers)) return true; + if (CE->getOpcode() != Instruction::GetElementPtr) + GS.isNotSuitableForSRA = true; + } else if (Instruction *I = dyn_cast(*UI)) { + if (isa(I)) { + GS.isLoaded = true; + } else if (StoreInst *SI = dyn_cast(I)) { + // If this store is just storing the initializer into a global (i.e. not + // changing the value), ignore it. For now we just handle direct + // stores, no stores to fields of aggregates. + if (GlobalVariable *GV = dyn_cast(SI->getOperand(1))) { + if (SI->getOperand(0) == GV->getInitializer() && + GS.StoredType < GlobalStatus::isInitializerStored) + GS.StoredType = GlobalStatus::isInitializerStored; + else if (isa(SI->getOperand(0)) && + GS.StoredType < GlobalStatus::isMallocStored) + GS.StoredType = GlobalStatus::isMallocStored; + else + GS.StoredType = GlobalStatus::isStored; + } else { + GS.StoredType = GlobalStatus::isStored; + } + } else if (I->getOpcode() == Instruction::GetElementPtr) { + if (AnalyzeGlobal(I, GS, PHIUsers)) return true; + if (!GS.isNotSuitableForSRA) + for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i) + if (!isa(I->getOperand(i))) { + GS.isNotSuitableForSRA = true; + break; + } + } else if (I->getOpcode() == Instruction::Select) { + if (AnalyzeGlobal(I, GS, PHIUsers)) return true; + GS.isNotSuitableForSRA = true; + } else if (PHINode *PN = dyn_cast(I)) { + // PHI nodes we can check just like select or GEP instructions, but we + // have to be careful about infinite recursion. + if (PHIUsers.insert(PN).second) // Not already visited. + if (AnalyzeGlobal(I, GS, PHIUsers)) return true; + GS.isNotSuitableForSRA = true; + } else if (isa(I)) { + GS.isNotSuitableForSRA = true; + } else { + return true; // Any other non-load instruction might take address! + } + } else { + // Otherwise must be a global or some other user. + return true; + } + + return false; +} + + + +static Constant *TraverseGEPInitializer(User *GEP, Constant *Init) { + if (GEP->getNumOperands() == 1 || + !isa(GEP->getOperand(1)) || + !cast(GEP->getOperand(1))->isNullValue()) + return 0; + + for (unsigned i = 2, e = GEP->getNumOperands(); i != e; ++i) { + ConstantInt *Idx = dyn_cast(GEP->getOperand(i)); + if (!Idx) return 0; + uint64_t IdxV = Idx->getRawValue(); + if (ConstantStruct *CS = dyn_cast(Init)) { + if (IdxV >= CS->getNumOperands()) return 0; + Init = CS->getOperand(IdxV); + } else if (ConstantArray *CA = dyn_cast(Init)) { + if (IdxV >= CA->getNumOperands()) return 0; + Init = CA->getOperand(IdxV); + } else if (ConstantPacked *CP = dyn_cast(Init)) { + if (IdxV >= CP->getNumOperands()) return 0; + Init = CP->getOperand(IdxV); + } else if (ConstantAggregateZero *CAZ = + dyn_cast(Init)) { + if (const StructType *STy = dyn_cast(Init->getType())) { + if (IdxV >= STy->getNumElements()) return 0; + Init = Constant::getNullValue(STy->getElementType(IdxV)); + } else if (const SequentialType *STy = + dyn_cast(Init->getType())) { + Init = Constant::getNullValue(STy->getElementType()); + } else { + return 0; + } + } else { + return 0; + } + } + return Init; +} + +/// CleanupConstantGlobalUsers - We just marked GV constant. Loop over all +/// users of the global, cleaning up the obvious ones. This is largely just a +/// quick scan over the use list to clean up the easy and obvious cruft. +static void CleanupConstantGlobalUsers(Value *V, Constant *Init) { + for (Value::use_iterator UI = V->use_begin(), E = V->use_end(); UI != E;) { + User *U = *UI++; + + if (LoadInst *LI = dyn_cast(U)) { + // Replace the load with the initializer. + LI->replaceAllUsesWith(Init); + LI->getParent()->getInstList().erase(LI); + } else if (StoreInst *SI = dyn_cast(U)) { + // Store must be unreachable or storing Init into the global. + SI->getParent()->getInstList().erase(SI); + } else if (ConstantExpr *CE = dyn_cast(U)) { + if (CE->getOpcode() == Instruction::GetElementPtr) { + if (Constant *SubInit = TraverseGEPInitializer(CE, Init)) + CleanupConstantGlobalUsers(CE, SubInit); + if (CE->use_empty()) CE->destroyConstant(); + } + } else if (GetElementPtrInst *GEP = dyn_cast(U)) { + if (Constant *SubInit = TraverseGEPInitializer(GEP, Init)) + CleanupConstantGlobalUsers(GEP, SubInit); + if (GEP->use_empty()) + GEP->getParent()->getInstList().erase(GEP); + } + } +} + +bool GlobalOpt::runOnModule(Module &M) { + bool Changed = false; + + // As a prepass, delete functions that are trivially dead. + bool LocalChange = true; + while (LocalChange) { + LocalChange = false; + for (Module::iterator FI = M.begin(), E = M.end(); FI != E; ) { + Function *F = FI++; + F->removeDeadConstantUsers(); + if (F->use_empty() && (F->hasInternalLinkage() || F->hasWeakLinkage())) { + M.getFunctionList().erase(F); + LocalChange = true; + ++NumFnDeleted; + } + } + Changed |= LocalChange; + } + + std::set PHIUsers; + for (Module::giterator GVI = M.gbegin(), E = M.gend(); GVI != E;) { + GlobalVariable *GV = GVI++; + if (!GV->isConstant() && GV->hasInternalLinkage() && GV->hasInitializer()) { + GlobalStatus GS; + PHIUsers.clear(); + GV->removeDeadConstantUsers(); + if (!AnalyzeGlobal(GV, GS, PHIUsers)) { + // If the global is never loaded (but may be stored to), it is dead. + // Delete it now. + if (!GS.isLoaded) { + DEBUG(std::cerr << "GLOBAL NEVER LOADED: " << *GV); + // Delete any stores we can find to the global. We may not be able to + // make it completely dead though. + CleanupConstantGlobalUsers(GV, GV->getInitializer()); + + // If the global is dead now, delete it. + if (GV->use_empty()) { + M.getGlobalList().erase(GV); + ++NumDeleted; + } + Changed = true; + + } else if (GS.StoredType <= GlobalStatus::isInitializerStored) { + DEBUG(std::cerr << "MARKING CONSTANT: " << *GV); + GV->setConstant(true); + + // Clean up any obviously simplifiable users now. + CleanupConstantGlobalUsers(GV, GV->getInitializer()); + + // If the global is dead now, just nuke it. + if (GV->use_empty()) { + M.getGlobalList().erase(GV); + ++NumDeleted; + } + + ++NumMarked; + Changed = true; + } else if (!GS.isNotSuitableForSRA && + !GV->getInitializer()->getType()->isFirstClassType()) { + //std::cerr << "COULD SRA: " << *GV; + } + } + } + } + return Changed; +} -- cgit v1.2.3