lib/Analysis/DataStructure/DataStructureOpt.cpp

   1 //===- DataStructureOpt.cpp - Data Structure Analysis Based Optimizations -===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass uses DSA to a series of simple optimizations, like marking
  11 // unwritten global variables 'constant'.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Analysis/DataStructure/DataStructure.h"
  16 #include "llvm/Analysis/DataStructure/DSGraph.h"
  17 #include "llvm/Analysis/Passes.h"
  18 #include "llvm/Module.h"
  19 #include "llvm/Constant.h"
  20 #include "llvm/Type.h"
  21 #include "llvm/ADT/Statistic.h"
  22 using namespace llvm;
  23
  24 namespace {
  25   Statistic<>
  26   NumGlobalsConstanted("ds-opt", "Number of globals marked constant");
  27   Statistic<>
  28   NumGlobalsIsolated("ds-opt", "Number of globals with references dropped");
  29
  30   class DSOpt : public ModulePass {
  31     TDDataStructures *TD;
  32   public:
  33     bool runOnModule(Module &M) {
  34       TD = &getAnalysis<TDDataStructures>();
  35       bool Changed = OptimizeGlobals(M);
  36       return Changed;
  37     }
  38
  39     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  40       AU.addRequired<TDDataStructures>();      // Uses TD Datastructures
  41       AU.addPreserved<LocalDataStructures>();  // Preserves local...
  42       AU.addPreserved<TDDataStructures>();     // Preserves bu...
  43       AU.addPreserved<BUDataStructures>();     // Preserves td...
  44     }
  45
  46   private:
  47     bool OptimizeGlobals(Module &M);
  48   };
  49
  50   RegisterOpt<DSOpt> X("ds-opt", "DSA-based simple optimizations");
  51 }
  52
  53 ModulePass *llvm::createDSOptPass() { return new DSOpt(); }
  54
  55 /// OptimizeGlobals - This method uses information taken from DSA to optimize
  56 /// global variables.
  57 ///
  58 bool DSOpt::OptimizeGlobals(Module &M) {
  59   DSGraph &GG = TD->getGlobalsGraph();
  60   const DSGraph::ScalarMapTy &SM = GG.getScalarMap();
  61   bool Changed = false;
  62
  63   for (Module::global_iterator I = M.global_begin(), E = M.global_end(); I != E; ++I)
  64     if (!I->isExternal()) { // Loop over all of the non-external globals...
  65       // Look up the node corresponding to this global, if it exists.
  66       DSNode *GNode = 0;
  67       DSGraph::ScalarMapTy::const_iterator SMI = SM.find(I);
  68       if (SMI != SM.end()) GNode = SMI->second.getNode();
  69
  70       if (GNode == 0 && I->hasInternalLinkage()) {
  71         // If there is no entry in the scalar map for this global, it was never
  72         // referenced in the program.  If it has internal linkage, that means we
  73         // can delete it.  We don't ACTUALLY want to delete the global, just
  74         // remove anything that references the global: later passes will take
  75         // care of nuking it.
  76         if (!I->use_empty()) {
  77           I->replaceAllUsesWith(Constant::getNullValue((Type*)I->getType()));
  78           ++NumGlobalsIsolated;
  79         }
  80       } else if (GNode && GNode->isComplete()) {
  81
  82         // If the node has not been read or written, and it is not externally
  83         // visible, kill any references to it so it can be DCE'd.
  84         if (!GNode->isModified() && !GNode->isRead() &&I->hasInternalLinkage()){
  85           if (!I->use_empty()) {
  86             I->replaceAllUsesWith(Constant::getNullValue((Type*)I->getType()));
  87             ++NumGlobalsIsolated;
  88           }
  89         }
  90
  91         // We expect that there will almost always be a node for this global.
  92         // If there is, and the node doesn't have the M bit set, we can set the
  93         // 'constant' bit on the global.
  94         if (!GNode->isModified() && !I->isConstant()) {
  95           I->setConstant(true);
  96           ++NumGlobalsConstanted;
  97           Changed = true;
  98         }
  99       }
 100     }
 101   return Changed;
 102 }