LatestComputation


1   /* Soot - a J*va Optimization Framework
2    * Copyright (C) 2002 Florian Loitsch
3    *
4    * This library is free software; you can redistribute it and/or
5    * modify it under the terms of the GNU Lesser General Public
6    * License as published by the Free Software Foundation; either
7    * version 2.1 of the License, or (at your option) any later version.
8    *
9    * This library is distributed in the hope that it will be useful,
10   * but WITHOUT ANY WARRANTY; without even the implied warranty of
11   * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12   * Lesser General Public License for more details.
13   *
14   * You should have received a copy of the GNU Lesser General Public
15   * License along with this library; if not, write to the
16   * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17   * Boston, MA 02111-1307, USA.
18   */
19  
20  /*
21   * Modified by the Sable Research Group and others 1997-2002.
22   * See the 'credits' file distributed with Soot for the complete list of
23   * contributors.  (Soot is distributed at http://www.sable.mcgill.ca/soot)
24   */
25  
26  
27  package soot.jimple.toolkits.scalar.pre;
28  import soot.*;
29  import soot.toolkits.scalar.*;
30  import soot.toolkits.graph.*;
31  import soot.jimple.toolkits.scalar.*;
32  import soot.jimple.*;
33  import java.util.*;
34  import soot.util.*;
35  
36  /** 
37   * Performs a Latest-Computation on the given graph.
38   * a computation is latest, when we can't delay it anymore. This uses the
39   * Delayability-analysis.
40   * More precise: The delayability-analysis says us already until which point we
41   * can delay a computation from the earliest computation-point. We just have to
42   * search for points, where there's a computation, or, where we can't delay the
43   * computation to one of the succesors.
44   */
45  public class LatestComputation {
46    private Map unitToLatest;
47  
48  
49    /**
50     * given a DelayabilityAnalysis and the computations of each unit, calculates
51     * the latest computation-point for each expression.
52     * the <code>equivRhsMap</code> could be calculated on the fly, but it is
53     * <b>very</b> likely that it already exists (as similar maps are used for
54     * calculating Earliestness, Delayed,...
55     *
56     * @param dg a ExceptionalUnitGraph
57     * @param delayed the delayability-analysis of the same graph.
58     * @param equivRhsMap all computations of the graph
59     */
60    public LatestComputation(UnitGraph unitGraph, DelayabilityAnalysis delayed,
61                             Map equivRhsMap) {
62      this(unitGraph, delayed, equivRhsMap, new
63        ArrayPackedSet(new CollectionFlowUniverse(equivRhsMap.values())));
64    }
65  
66    /**
67     * given a DelayabilityAnalysis and the computations of each unit, calculates
68     * the latest computation-point for each expression.<br>
69     * the <code>equivRhsMap</code> could be calculated on the fly, but it is
70     * <b>very</b> likely that it already exists (as similar maps are used for
71     * calculating Earliestness, Delayed,...<br>
72     * the shared set allows more efficient set-operations, when they the
73     * computation is merged with other analyses/computations.
74     *
75     * @param dg a ExceptionalUnitGraph
76     * @param delayed the delayability-analysis of the same graph.
77     * @param equivRhsMap all computations of the graph
78     * @param set the shared flowSet
79     */
80    public LatestComputation(UnitGraph unitGraph, DelayabilityAnalysis delayed,
81                             Map equivRhsMap, BoundedFlowSet set) {
82      unitToLatest = new HashMap(unitGraph.size() + 1, 0.7f);
83  
84      Iterator unitIt = unitGraph.iterator();
85      while (unitIt.hasNext()) {
86        /* create a new Earliest-list for each unit */
87        Unit currentUnit = (Unit)unitIt.next();
88  
89        /* basically the latest-set is: 
90         * (delayed) INTERSECT (comp UNION (UNION_successors ~Delayed)) =
91         * (delayed) MINUS ((INTERSECTION_successors Delayed) MINUS comp).
92         */
93  
94        FlowSet delaySet = (FlowSet)delayed.getFlowBefore(currentUnit);
95  
96        /* Calculate (INTERSECTION_successors Delayed) */
97        FlowSet succCompSet = (FlowSet)set.topSet();
98        List succList = unitGraph.getSuccsOf(currentUnit);
99        Iterator succIt = succList.iterator();
100       while(succIt.hasNext()) {
101         Unit successor = (Unit)succIt.next();
102         succCompSet.intersection((FlowSet)delayed.getFlowBefore(successor),
103             succCompSet);
104       }
105       /* remove the computation of this set: succCompSet is then:
106        * ((INTERSECTION_successors Delayed) MINUS comp) */
107       if (equivRhsMap.get(currentUnit) != null)
108         succCompSet.remove(equivRhsMap.get(currentUnit));
109 
110       /* make the difference: */
111       FlowSet latest = (FlowSet)delaySet.emptySet();
112       delaySet.difference(succCompSet, latest);
113 
114       unitToLatest.put(currentUnit, latest);
115     }
116   }
117 
118   /**
119    * returns the set of expressions, that have their latest computation just
120    * before <code>node</code>.
121    *
122    * @param node an Object of the flow-graph (in our case always a unit).
123    * @return a FlowSet containing the expressions.
124    */
125   public Object   getFlowBefore(Object   node) {
126     return unitToLatest.get(node);
127   }
128 }
129
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags