1 //===- DataStructureOpt.cpp - Data Structure Analysis Based Optimizations -===//
3 // The LLVM Compiler Infrastructure
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.
8 //===----------------------------------------------------------------------===//
10 // This pass uses DSA to a series of simple optimizations, like marking
11 // unwritten global variables 'constant'.
13 //===----------------------------------------------------------------------===//
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"
26 NumGlobalsConstanted("ds-opt", "Number of globals marked constant");
28 NumGlobalsIsolated("ds-opt", "Number of globals with references dropped");
30 class DSOpt : public ModulePass {
33 bool runOnModule(Module &M) {
34 TD = &getAnalysis<TDDataStructures>();
35 bool Changed = OptimizeGlobals(M);
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...
47 bool OptimizeGlobals(Module &M);
50 RegisterOpt<DSOpt> X("ds-opt", "DSA-based simple optimizations");
53 ModulePass *llvm::createDSOptPass() { return new DSOpt(); }
55 /// OptimizeGlobals - This method uses information taken from DSA to optimize
58 bool DSOpt::OptimizeGlobals(Module &M) {
59 DSGraph &GG = TD->getGlobalsGraph();
60 const DSGraph::ScalarMapTy &SM = GG.getScalarMap();
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.
67 DSGraph::ScalarMapTy::const_iterator SMI = SM.find(I);
68 if (SMI != SM.end()) GNode = SMI->second.getNode();
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
76 if (!I->use_empty()) {
77 I->replaceAllUsesWith(Constant::getNullValue((Type*)I->getType()));
80 } else if (GNode && GNode->isComplete()) {
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()));
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()) {
96 ++NumGlobalsConstanted;