KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > soot > jimple > toolkits > scalar > pre > EarliestnessComputation


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  * Computes the earliest points for the given expressions.<br>
38  * This basicly finds the highest point in the flow-graph where we can put each
39  * computation, without introducing new computations on any path.<br>
40  * More technically: A computation is earliest, if at the current point the
41  * computation is down-safe, and if either:
42  * <ul>
43  * <li> any of the predecessors is not transparent, or
44  * <li> if any predecessors is not "safe" (ie. the insertion of
45  * this computation would insert it on a path, where it was not before).
46  * </ul><br>
47  * Intuitively: If the one predecessor is not transparent, we can't push the
48  * computation further up. If one of the predecessor is not safe, we would
49  * introduce a new computation on its path. Hence we can't push further up.<p>
50  * Note that this computation is linear in the number of units, as we don't need
51  * to find any fixed-point.
52  *
53  * @see UpSafetyAnalysis
54  * @see DownSafetyAnalysis
55  */
56 public class EarliestnessComputation {
57   private Map unitToEarliest;
58   private SideEffectTester sideEffect;
59
60   /**
61    * given an UpSafetyAnalysis and a DownSafetyAnalysis, performs the
62    * earliest-computation.<br>
63    *
64    * @param unitGraph the Unitgraph we'll work on.
65    * @param upSafe a UpSafetyAnalysis of <code>unitGraph</code>
66    * @param downSafe a DownSafetyAnalysis of <code>unitGraph</code>
67    * @param sideEffect the SideEffectTester that will tell if a node is
68    * transparent or not.
69    */
70   public EarliestnessComputation(UnitGraph unitGraph, UpSafetyAnalysis upSafe,
71       DownSafetyAnalysis downSafe, SideEffectTester sideEffect) {
72     this(unitGraph, upSafe, downSafe, sideEffect, new ArraySparseSet());
73   }
74
75   /**
76    * given an UpSafetyAnalysis and a DownSafetyAnalysis, performs the
77    * earliest-computation.<br>
78    * allows to share sets over multiple analyses (set-operations are usually
79    * more efficient, if the sets come from the same source).
80    *
81    * @param unitGraph the Unitgraph we'll work on.
82    * @param upSafe a UpSafetyAnalysis of <code>unitGraph</code>
83    * @param downSafe a DownSafetyAnalysis of <code>unitGraph</code>
84    * @param sideEffect the SideEffectTester that will tell if a node is
85    * transparent or not.
86    * @param set the shared set.
87    */
88   public EarliestnessComputation(UnitGraph unitGraph, UpSafetyAnalysis upSafe,
89       DownSafetyAnalysis downSafe, SideEffectTester sideEffect, FlowSet set) {
90     this.sideEffect = sideEffect;
91
92     unitToEarliest = new HashMap(unitGraph.size() + 1, 0.7f);
93
94     Iterator unitIt = unitGraph.iterator();
95     while (unitIt.hasNext()) {
96       /* create a new Earliest-list for each unit */
97       Unit currentUnit = (Unit)unitIt.next();
98       FlowSet earliest = (FlowSet)set.emptySet();
99       unitToEarliest.put(currentUnit, earliest);
100
101       /* get a copy of the downSafe-set at the current unit */
102       FlowSet downSafeSet =
103         (FlowSet)((FlowSet)downSafe.getFlowBefore(currentUnit)).clone();
104
105       List predList = unitGraph.getPredsOf(currentUnit);
106       if (predList.size() == 0) { //no predecessor
107 /* we are obviously at the earliest position for any downsafe
108          * computation */
109         earliest.union(downSafeSet);
110       } else {
111         Iterator predIt = predList.iterator();
112         while(predIt.hasNext()) {
113           Unit predecessor = (Unit)predIt.next();
114
115           { /* if a predecessor is not transparent for a certain computation,
116              * that is downsafe here, we can't push the computation further up,
117              * and the earliest computation is before the current point.*/
118
119             /* for each element in the downSafe-set, look if it passes through
120              * the predecessor */
121             Iterator downSafeIt = downSafeSet.iterator();
122             while (downSafeIt.hasNext()) {
123               EquivalentValue equiVal = (EquivalentValue)downSafeIt.next();
124               Value avail = equiVal.getValue();
125               if (avail instanceof FieldRef) {
126                 if (sideEffect.unitCanWriteTo(predecessor, avail)) {
127                   earliest.add(equiVal);
128                   downSafeIt.remove();
129                 }
130               } else {
131                 Iterator usesIt = avail.getUseBoxes().iterator();
132
133                 // iterate over uses in each avail.
134 while (usesIt.hasNext()) {
135                   Value use = ((ValueBox)usesIt.next()).getValue();
136
137                   if (sideEffect.unitCanWriteTo(predecessor, use)) {
138                     earliest.add(equiVal);
139                     downSafeIt.remove();
140                     break;
141                   }
142                 }
143               }
144             }
145           }
146
147           { /* look if one of the expressions is not upsafe and not downsafe in
148              * one of the predecessors */
149             Iterator downSafeIt = downSafeSet.iterator();
150             while (downSafeIt.hasNext()) {
151               EquivalentValue equiVal = (EquivalentValue)downSafeIt.next();
152               Value avail = equiVal.getValue();
153               FlowSet preDown = (FlowSet)downSafe.getFlowBefore(predecessor);
154               FlowSet preUp = (FlowSet)upSafe.getFlowBefore(predecessor);
155               if (!preDown.contains(equiVal) && !preUp.contains(equiVal)) {
156                 earliest.add(equiVal);
157                 downSafeIt.remove();
158               }
159             }
160           }
161         }
162       }
163     }
164   }
165
166   /**
167    * returns the FlowSet of expressions, that have their earliest computation just
168    * before <code>node</code>.
169    *
170    * @param node a Object of the flow-graph (in our case always a unit).
171    * @return a FlowSet containing the expressions.
172    */
173   public Object JavaDoc getFlowBefore(Object JavaDoc node) {
174     return unitToEarliest.get(node);
175   }
176 }
177
Popular Tags