LLVM API Documentation
00001 //===- DataStructureOpt.cpp - Data Structure Analysis Based Optimizations -===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This pass uses DSA to a series of simple optimizations, like marking 00011 // unwritten global variables 'constant'. 00012 // 00013 //===----------------------------------------------------------------------===// 00014 00015 #include "llvm/Analysis/DataStructure/DataStructure.h" 00016 #include "llvm/Analysis/DataStructure/DSGraph.h" 00017 #include "llvm/Analysis/Passes.h" 00018 #include "llvm/Module.h" 00019 #include "llvm/Constant.h" 00020 #include "llvm/Type.h" 00021 #include "llvm/ADT/Statistic.h" 00022 using namespace llvm; 00023 00024 namespace { 00025 Statistic<> 00026 NumGlobalsConstanted("ds-opt", "Number of globals marked constant"); 00027 Statistic<> 00028 NumGlobalsIsolated("ds-opt", "Number of globals with references dropped"); 00029 00030 class DSOpt : public ModulePass { 00031 TDDataStructures *TD; 00032 public: 00033 bool runOnModule(Module &M) { 00034 TD = &getAnalysis<TDDataStructures>(); 00035 bool Changed = OptimizeGlobals(M); 00036 return Changed; 00037 } 00038 00039 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00040 AU.addRequired<TDDataStructures>(); // Uses TD Datastructures 00041 AU.addPreserved<LocalDataStructures>(); // Preserves local... 00042 AU.addPreserved<TDDataStructures>(); // Preserves bu... 00043 AU.addPreserved<BUDataStructures>(); // Preserves td... 00044 } 00045 00046 private: 00047 bool OptimizeGlobals(Module &M); 00048 }; 00049 00050 RegisterOpt<DSOpt> X("ds-opt", "DSA-based simple optimizations"); 00051 } 00052 00053 ModulePass *llvm::createDSOptPass() { return new DSOpt(); } 00054 00055 /// OptimizeGlobals - This method uses information taken from DSA to optimize 00056 /// global variables. 00057 /// 00058 bool DSOpt::OptimizeGlobals(Module &M) { 00059 DSGraph &GG = TD->getGlobalsGraph(); 00060 const DSGraph::ScalarMapTy &SM = GG.getScalarMap(); 00061 bool Changed = false; 00062 00063 for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I) 00064 if (!I->isExternal()) { // Loop over all of the non-external globals... 00065 // Look up the node corresponding to this global, if it exists. 00066 DSNode *GNode = 0; 00067 DSGraph::ScalarMapTy::const_iterator SMI = SM.find(I); 00068 if (SMI != SM.end()) GNode = SMI->second.getNode(); 00069 00070 if (GNode == 0 && I->hasInternalLinkage()) { 00071 // If there is no entry in the scalar map for this global, it was never 00072 // referenced in the program. If it has internal linkage, that means we 00073 // can delete it. We don't ACTUALLY want to delete the global, just 00074 // remove anything that references the global: later passes will take 00075 // care of nuking it. 00076 if (!I->use_empty()) { 00077 I->replaceAllUsesWith(Constant::getNullValue((Type*)I->getType())); 00078 ++NumGlobalsIsolated; 00079 } 00080 } else if (GNode && GNode->isComplete()) { 00081 00082 // If the node has not been read or written, and it is not externally 00083 // visible, kill any references to it so it can be DCE'd. 00084 if (!GNode->isModified() && !GNode->isRead() &&I->hasInternalLinkage()){ 00085 if (!I->use_empty()) { 00086 I->replaceAllUsesWith(Constant::getNullValue((Type*)I->getType())); 00087 ++NumGlobalsIsolated; 00088 } 00089 } 00090 00091 // We expect that there will almost always be a node for this global. 00092 // If there is, and the node doesn't have the M bit set, we can set the 00093 // 'constant' bit on the global. 00094 if (!GNode->isModified() && !I->isConstant()) { 00095 I->setConstant(true); 00096 ++NumGlobalsConstanted; 00097 Changed = true; 00098 } 00099 } 00100 } 00101 return Changed; 00102 }