001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 2003 Jennifer Lhotak
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 2.1 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the
016: * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
017: * Boston, MA 02111-1307, USA.
018: */
019:
020: package soot.toolkits.graph;
021:
022: import soot.*;
023: import java.util.*;
024:
025: import soot.jimple.Stmt;
026: import soot.toolkits.scalar.*;
027:
028: // STEP 1: What are we computing?
029: // SETS OF Units that are post-dominators => Use ArraySparseSet.
030: //
031: // STEP 2: Precisely define what we are computing.
032: // For each statement compute the set of stmts that post-dominate it
033: //
034: // STEP 3: Decide whether it is a backwards or forwards analysis.
035: // FORWARDS
036: //
037: //
038: /**
039: * @deprecated use {@link MHGPostDominatorsFinder} instead
040: */
041: public class PostDominatorAnalysis extends BackwardFlowAnalysis {
042:
043: private UnitGraph g;
044: private FlowSet allNodes;
045:
046: public PostDominatorAnalysis(UnitGraph g) {
047: super (g);
048: this .g = g;
049:
050: initAllNodes();
051:
052: doAnalysis();
053:
054: }
055:
056: private void initAllNodes() {
057: allNodes = new ArraySparseSet();
058: Iterator it = g.iterator();
059: while (it.hasNext()) {
060: allNodes.add(it.next());
061: }
062: }
063:
064: // STEP 4: Is the merge operator union or intersection?
065: // INTERSECTION
066:
067: protected void merge(Object in1, Object in2, Object out) {
068: FlowSet inSet1 = (FlowSet) in1;
069: FlowSet inSet2 = (FlowSet) in2;
070: FlowSet outSet = (FlowSet) out;
071:
072: inSet1.intersection(inSet2, outSet);
073:
074: }
075:
076: protected void copy(Object source, Object dest) {
077:
078: FlowSet sourceIn = (FlowSet) source;
079: FlowSet destOut = (FlowSet) dest;
080:
081: sourceIn.copy(destOut);
082:
083: }
084:
085: // STEP 5: Define flow equations.
086: // dom(s) = s U ( ForAll Y in pred(s): Intersection (dom(y)))
087: // ie: dom(s) = s and whoever dominates all the predeccessors of s
088: //
089:
090: protected void flowThrough(Object inValue, Object unit,
091: Object outValue) {
092: FlowSet in = (FlowSet) inValue;
093: FlowSet out = (FlowSet) outValue;
094: Unit s = (Unit) unit;
095:
096: if (isUnitEndNode(s)) {
097: // System.out.println("s: "+s+" is end node");
098: out.clear();
099: out.add(s);
100: // System.out.println("in: "+in+" out: "+out);
101: } else {
102:
103: // System.out.println("s: "+s+" is not start node");
104: FlowSet domsOfSuccs = allNodes.clone();
105:
106: // for each pred of s
107: Iterator succsIt = g.getSuccsOf(s).iterator();
108: while (succsIt.hasNext()) {
109: Unit succ = (Unit) succsIt.next();
110: // get the unitToBeforeFlow and find the intersection
111: // System.out.println("succ: "+succ);
112: FlowSet next = (FlowSet) unitToBeforeFlow.get(succ);
113: // System.out.println("next: "+next);
114: // System.out.println("in before intersect: "+in);
115: in.intersection(next, in);
116: // System.out.println("in after intersect: "+in);
117: }
118:
119: // intersected with in
120:
121: // System.out.println("out init: "+out);
122: out.intersection(in, out);
123: out.add(s);
124: // System.out.println("out after: "+out);
125: }
126: }
127:
128: private boolean isUnitEndNode(Unit s) {
129: //System.out.println("head: "+g.getHeads().get(0));
130: if (g.getTails().contains(s))
131: return true;
132: return false;
133: }
134:
135: // STEP 6: Determine value for start/end node, and
136: // initial approximation.
137: // dom(startNode) = startNode
138: // dom(node) = allNodes
139: //
140: protected Object entryInitialFlow() {
141:
142: FlowSet fs = new ArraySparseSet();
143: List tails = g.getTails();
144: // if (tails.size() != 1) {
145: // throw new RuntimeException("Expect one end node only.");
146: // }
147: fs.add(tails.get(0));
148: return fs;
149: }
150:
151: protected Object newInitialFlow() {
152: return allNodes.clone();
153: }
154:
155: /**
156: * Returns true if s post-dominates t.
157: */
158: public boolean postDominates(Stmt s, Stmt t) {
159: return ((FlowSet) getFlowBefore(t)).contains(s);
160: }
161:
162: }
|