001: /* Soot - a J*va Optimization Framework
002: * Copyright (C) 1997-1999 Raja Vallee-Rai
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: /*
021: * Modified by the Sable Research Group and others 1997-1999.
022: * See the 'credits' file distributed with Soot for the complete list of
023: * contributors. (Soot is distributed at http://www.sable.mcgill.ca/soot)
024: */
025:
026: package soot.toolkits.scalar;
027:
028: import java.util.Collection;
029: import java.util.Comparator;
030: import java.util.HashMap;
031: import java.util.Iterator;
032: import java.util.List;
033: import java.util.Map;
034: import java.util.TreeSet;
035:
036: import soot.Timers;
037: import soot.options.Options;
038: import soot.toolkits.graph.DirectedGraph;
039: import soot.toolkits.graph.PseudoTopologicalOrderer;
040: import soot.toolkits.graph.interaction.FlowInfo;
041: import soot.toolkits.graph.interaction.InteractionHandler;
042:
043: /**
044: * Abstract class that provides the fixed point iteration functionality
045: * required by all BackwardFlowAnalyses.
046: *
047: */
048: public abstract class BackwardFlowAnalysis<N, A> extends
049: FlowAnalysis<N, A> {
050: /** Construct the analysis from a DirectedGraph representation of a Body. */
051: public BackwardFlowAnalysis(DirectedGraph<N> graph) {
052: super (graph);
053: }
054:
055: protected boolean isForward() {
056: return false;
057: }
058:
059: protected void doAnalysis() {
060: final Map<N, Integer> numbers = new HashMap<N, Integer>();
061: // Timers.v().orderComputation = new soot.Timer();
062: // Timers.v().orderComputation.start();
063: List<N> orderedUnits = constructOrderer().newList(graph, false);
064: // Timers.v().orderComputation.end();
065: new PseudoTopologicalOrderer().newList(graph, false);
066: int i = 1;
067: for (Iterator<N> uIt = orderedUnits.iterator(); uIt.hasNext();) {
068: final N u = uIt.next();
069: numbers.put(u, new Integer(i));
070: i++;
071: }
072:
073: Collection<N> changedUnits = constructWorklist(numbers);
074:
075: // Set initial Flows and nodes to visit.
076: {
077: Iterator<N> it = graph.iterator();
078:
079: while (it.hasNext()) {
080: N s = it.next();
081:
082: changedUnits.add(s);
083:
084: unitToBeforeFlow.put(s, newInitialFlow());
085: unitToAfterFlow.put(s, newInitialFlow());
086: }
087: }
088:
089: List<N> tails = graph.getTails();
090:
091: // Feng Qian: March 07, 2002
092: // init entry points
093: {
094: Iterator<N> it = tails.iterator();
095:
096: while (it.hasNext()) {
097: N s = it.next();
098: // this is a backward flow analysis
099: unitToAfterFlow.put(s, entryInitialFlow());
100: }
101: }
102:
103: // Perform fixed point flow analysis
104: {
105: A previousBeforeFlow = newInitialFlow();
106:
107: while (!changedUnits.isEmpty()) {
108: A beforeFlow;
109: A afterFlow;
110:
111: //get the first object
112: N s = changedUnits.iterator().next();
113: changedUnits.remove(s);
114: boolean isTail = tails.contains(s);
115:
116: copy(unitToBeforeFlow.get(s), previousBeforeFlow);
117:
118: // Compute and store afterFlow
119: {
120: List<N> succs = graph.getSuccsOf(s);
121:
122: afterFlow = unitToAfterFlow.get(s);
123:
124: if (succs.size() == 1)
125: copy(unitToBeforeFlow.get(succs.get(0)),
126: afterFlow);
127: else if (succs.size() != 0) {
128: Iterator<N> succIt = succs.iterator();
129:
130: copy(unitToBeforeFlow.get(succIt.next()),
131: afterFlow);
132:
133: while (succIt.hasNext()) {
134: A otherBranchFlow = unitToBeforeFlow
135: .get(succIt.next());
136: merge(afterFlow, otherBranchFlow);
137: }
138:
139: if (isTail && succs.size() != 0)
140: merge(afterFlow, entryInitialFlow());
141: }
142: }
143:
144: // Compute beforeFlow and store it.
145: {
146: beforeFlow = unitToBeforeFlow.get(s);
147: if (Options.v().interactive_mode()) {
148: A savedFlow = newInitialFlow();
149: if (filterUnitToAfterFlow != null) {
150: savedFlow = filterUnitToAfterFlow.get(s);
151: copy(filterUnitToAfterFlow.get(s),
152: savedFlow);
153: } else {
154: copy(afterFlow, savedFlow);
155: }
156: FlowInfo fi = new FlowInfo(savedFlow, s, false);
157: if (InteractionHandler.v().getStopUnitList() != null
158: && InteractionHandler.v()
159: .getStopUnitList().contains(s)) {
160: InteractionHandler.v()
161: .handleStopAtNodeEvent(s);
162: }
163: InteractionHandler.v()
164: .handleAfterAnalysisEvent(fi);
165: }
166: flowThrough(afterFlow, s, beforeFlow);
167: if (Options.v().interactive_mode()) {
168: A bSavedFlow = newInitialFlow();
169: if (filterUnitToBeforeFlow != null) {
170: bSavedFlow = filterUnitToBeforeFlow.get(s);
171: copy(filterUnitToBeforeFlow.get(s),
172: bSavedFlow);
173: } else {
174: copy(beforeFlow, bSavedFlow);
175: }
176: FlowInfo fi = new FlowInfo(bSavedFlow, s, true);
177: InteractionHandler.v()
178: .handleBeforeAnalysisEvent(fi);
179: }
180: }
181:
182: // Update queue appropriately
183: if (!beforeFlow.equals(previousBeforeFlow)) {
184: Iterator<N> predIt = graph.getPredsOf(s).iterator();
185:
186: while (predIt.hasNext()) {
187: N pred = predIt.next();
188:
189: changedUnits.add(pred);
190: }
191: }
192: }
193: }
194: }
195:
196: protected Collection<N> constructWorklist(
197: final Map<N, Integer> numbers) {
198: return new TreeSet<N>(new Comparator<N>() {
199: public int compare(N o1, N o2) {
200: Integer i1 = numbers.get(o1);
201: Integer i2 = numbers.get(o2);
202: return (i1.intValue() - i2.intValue());
203: }
204: });
205: }
206: }
|