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.h"
  16 #include "llvm/Analysis/DSGraph.h"
  17 #include "llvm/Module.h"
  18 #include "llvm/Constant.h"
  19 #include "Support/Statistic.h"
  20 using namespace llvm;
  21
  22 namespace {
  23   Statistic<>
  24   NumGlobalsConstanted("ds-opt", "Number of globals marked constant");
  25   Statistic<>
  26   NumGlobalsIsolated("ds-opt", "Number of globals with references dropped");
  27
  28   class DSOpt : public Pass {
  29     TDDataStructures *TD;
  30   public:
  31     bool run(Module &M) {
  32       TD = &getAnalysis<TDDataStructures>();
  33       bool Changed = OptimizeGlobals(M);
  34       return Changed;
  35     }
  36
  37     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  38       AU.addRequired<TDDataStructures>();      // Uses TD Datastructures
  39       AU.addPreserved<LocalDataStructures>();  // Preserves local...
  40       AU.addPreserved<TDDataStructures>();     // Preserves bu...
  41       AU.addPreserved<BUDataStructures>();     // Preserves td...
  42     }
  43
  44   private:
  45     bool OptimizeGlobals(Module &M);
  46   };
  47
  48   RegisterOpt<DSOpt> X("ds-opt", "DSA-based simple optimizations");
  49 }
  50
  51 /// OptimizeGlobals - This method uses information taken from DSA to optimize
  52 /// global variables.
  53 ///
  54 bool DSOpt::OptimizeGlobals(Module &M) {
  55   DSGraph &GG = TD->getGlobalsGraph();
  56   const DSGraph::ScalarMapTy &SM = GG.getScalarMap();
  57   bool Changed = false;
  58
  59   for (Module::giterator I = M.gbegin(), E = M.gend(); I != E; ++I)
  60     if (!I->isExternal()) { // Loop over all of the non-external globals...
  61       // Look up the node corresponding to this global, if it exists.
  62       DSNode *GNode = 0;
  63       DSGraph::ScalarMapTy::const_iterator SMI = SM.find(I);
  64       if (SMI != SM.end()) GNode = SMI->second.getNode();
  65
  66       if (GNode == 0 && I->hasInternalLinkage()) {
  67         // If there is no entry in the scalar map for this global, it was never
  68         // referenced in the program.  If it has internal linkage, that means we
  69         // can delete it.  We don't ACTUALLY want to delete the global, just
  70         // remove anything that references the global: later passes will take
  71         // care of nuking it.
  72         if (!I->use_empty()) {
  73           I->replaceAllUsesWith(Constant::getNullValue((Type*)I->getType()));
  74           ++NumGlobalsIsolated;
  75         }
  76       } else if (GNode && GNode->isComplete()) {
  77
  78         // If the node has not been read or written, and it is not externally
  79         // visible, kill any references to it so it can be DCE'd.
  80         if (!GNode->isModified() && !GNode->isRead() &&I->hasInternalLinkage()){
  81           if (!I->use_empty()) {
  82             I->replaceAllUsesWith(Constant::getNullValue((Type*)I->getType()));
  83             ++NumGlobalsIsolated;
  84           }
  85         }
  86
  87         // We expect that there will almost always be a node for this global.
  88         // If there is, and the node doesn't have the M bit set, we can set the
  89         // 'constant' bit on the global.
  90         if (!GNode->isModified() && !I->isConstant()) {
  91           I->setConstant(true);
  92           ++NumGlobalsConstanted;
  93           Changed = true;
  94         }
  95       }
  96     }
  97   return Changed;
  98 }