LLVM API Documentation

DataStructureOpt.cpp

Go to the documentation of this file.
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 }