1 salcianu 1.1.2.1 // PAThreadMap.java, created Sun Jan 9 15:49:32 2000 by salcianu
2 cananian 1.1.2.3 // Copyright (C) 2000 Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
3 salcianu 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 salcianu 1.1.2.1 package harpoon.Analysis.PointerAnalysis;
5 salcianu 1.1.2.1
6 salcianu 1.1.2.1 import java.lang.System;
7 salcianu 1.1.2.1 import java.util.Hashtable;
8 salcianu 1.1.2.1 import java.util.Enumeration;
9 salcianu 1.1.2.1 import java.util.Map;
10 salcianu 1.1.2.1 import java.util.Iterator;
11 salcianu 1.1.2.2 import java.util.Set;
12 salcianu 1.1.2.1
13 salcianu 1.1.2.8 import java.util.Arrays;
14 salcianu 1.1.2.8
15 salcianu 1.1.2.7 import harpoon.Util.Util;
16 salcianu 1.1.2.7
17 salcianu 1.1.2.14 import harpoon.Util.DataStructs.Relation;
18 salcianu 1.1.2.14
19 salcianu 1.1.2.1 /**
20 salcianu 1.1.2.1 * <code>PAThreadMap</code> implements the parallel thread map
21 salcianu 1.1.2.1 * (i.e. the "tau" function from the algorithm). For each thread node
22 salcianu 1.1.2.1 * n, tau(n) is a conservative approximation of the number of instances
23 salcianu 1.1.2.1 * of nT that could run in parallel with the current thread.
24 salcianu 1.1.2.1 * tau(n) is a number from the set {0,1,2} where 0 stands for no instance,
25 salcianu 1.1.2.1 * 1 for at most one instance and 2 for possibly multiple instances.
26 salcianu 1.1.2.1 *
27 salcianu 1.1.2.1 * <code>PAThreadMap</code> is more or less a <code>Hashtable</code> with
28 salcianu 1.1.2.1 * some access functions to enforce the new rules for addition and
29 salcianu 1.1.2.1 * substraction.
30 salcianu 1.1.2.1 *
31 salcianu 1.1.2.1 * @author Alexandru SALCIANU <salcianu@retezat.lcs.mit.edu>
32 cananian 1.5 * @version $Id: PAThreadMap.java,v 1.5 2004/02/08 03:20:03 cananian Exp $
33 salcianu 1.1.2.1 */
34 salcianu 1.1.2.15 public class PAThreadMap implements java.io.Serializable {
35 salcianu 1.1.2.1
36 salcianu 1.1.2.1 static private final Integer ONE = new Integer(1);
37 salcianu 1.1.2.1 static private final Integer TWO = new Integer(2);
38 salcianu 1.1.2.1
39 salcianu 1.1.2.1 private Hashtable hash;
40 salcianu 1.1.2.1
41 salcianu 1.1.2.1 /** Creates a <code>PAThreadMap</code>. */
42 salcianu 1.1.2.1 public PAThreadMap() {
43 salcianu 1.1.2.1 hash = new Hashtable();
44 salcianu 1.1.2.1 }
45 salcianu 1.1.2.1
46 salcianu 1.1.2.1 // Look at the value attached to the thread node n
47 salcianu 1.1.2.1 // (i.e. tau(n)
48 salcianu 1.1.2.1 public int getValue(PANode n){
49 salcianu 1.1.2.1 Integer v = (Integer)hash.get(n);
50 salcianu 1.1.2.1
51 salcianu 1.1.2.1 if(v != null){
52 salcianu 1.1.2.1 return ((Integer) hash.get(n)).intValue();
53 salcianu 1.1.2.1 }
54 salcianu 1.1.2.1 else return 0;
55 salcianu 1.1.2.1 }
56 salcianu 1.1.2.1
57 salcianu 1.1.2.2 /** Increments the value attached to <code>n</code> */
58 salcianu 1.1.2.1 public void inc(PANode n){
59 salcianu 1.1.2.1 Integer v = (Integer)hash.get(n);
60 salcianu 1.1.2.1
61 salcianu 1.1.2.1 if(v == null) hash.put(n,ONE);
62 salcianu 1.1.2.1 if(v == ONE) hash.put(n,TWO);
63 salcianu 1.1.2.1 }
64 salcianu 1.1.2.5
65 salcianu 1.1.2.5
66 salcianu 1.1.2.5 /** Convenient function that calls <code>inc</code> for all the
67 salcianu 1.1.2.5 nodes from <code>set</code> */
68 salcianu 1.1.2.5 public void incAll(Set nodes){
69 cananian 1.5 for (Object nodeO : nodes){
70 cananian 1.5 PANode node = (PANode) nodeO;
71 salcianu 1.1.2.5 inc(node);
72 salcianu 1.1.2.5 }
73 salcianu 1.1.2.5 }
74 salcianu 1.1.2.1
75 salcianu 1.1.2.2 /** Decrements the value attached to <code>n</code> */
76 salcianu 1.1.2.1 public void dec(PANode n){
77 salcianu 1.1.2.1 Integer v = (Integer)hash.get(n);
78 salcianu 1.1.2.1
79 salcianu 1.1.2.1 if(v==null){
80 salcianu 1.1.2.1 System.err.println("Error in PAThreadMap: cannot do 0--\n");
81 salcianu 1.1.2.1 System.exit(1);
82 salcianu 1.1.2.1 }
83 salcianu 1.1.2.1
84 salcianu 1.1.2.1 // another alternative would be to attach to n a special object
85 salcianu 1.1.2.1 // ZERO. However, I decided to remove the mapping for n - in this
86 salcianu 1.1.2.1 // way, we don't create two values for expressing tau(n)=0 (null
87 salcianu 1.1.2.1 // and ZERO) and decrease the number of keys from the map.
88 salcianu 1.1.2.1 if(v==ONE) hash.remove(n);
89 salcianu 1.1.2.1 if(v==TWO) hash.put(n,TWO);
90 salcianu 1.1.2.12 }
91 salcianu 1.1.2.12
92 salcianu 1.1.2.12 /** Checks whether the thread "nt" is started or not. */
93 salcianu 1.1.2.12 public boolean isStarted(PANode nt){
94 salcianu 1.1.2.12 return hash.containsKey(nt);
95 salcianu 1.1.2.1 }
96 salcianu 1.1.2.7
97 salcianu 1.1.2.7 /** Add a positive <code>delta</code> to the value attached to a node. */
98 salcianu 1.1.2.7 public void add(PANode n, int delta){
99 cananian 1.3.2.1 assert delta>0 : ("PAThreadMap.add: delta should be > 0");
100 salcianu 1.1.2.7 int new_tau = getValue(n) + delta;
101 salcianu 1.1.2.7 if( new_tau > 1 )
102 salcianu 1.1.2.7 hash.put(n,TWO);
103 salcianu 1.1.2.7 else
104 salcianu 1.1.2.7 hash.put(n,ONE);
105 salcianu 1.1.2.7 }
106 salcianu 1.1.2.7
107 salcianu 1.1.2.1
108 salcianu 1.1.2.5 /** Set to zero the value attached to the node <code>n</code>. */
109 salcianu 1.1.2.5 public void setToZero(PANode n){
110 salcianu 1.1.2.5 hash.remove(n);
111 salcianu 1.1.2.5 }
112 salcianu 1.1.2.5
113 salcianu 1.1.2.4 /** Returns all the thread nodes <code>nT</code> that have assigned
114 salcianu 1.1.2.4 * a non-zero count (i.e. tau(nT) > 0 in the algorithm) */
115 salcianu 1.1.2.1 public Enumeration activeThreads(){
116 salcianu 1.1.2.1 return hash.keys();
117 salcianu 1.1.2.1 }
118 salcianu 1.1.2.1
119 salcianu 1.1.2.4 /** Returns all the thread nodes <code>nT</code> that have assigned
120 salcianu 1.1.2.4 * a non-zero count (i.e. tau(nT) > 0 in the algorithm) */
121 salcianu 1.1.2.4 public Set activeThreadSet(){
122 salcianu 1.1.2.4 return hash.keySet();
123 salcianu 1.1.2.4 }
124 salcianu 1.1.2.11
125 salcianu 1.1.2.11
126 salcianu 1.1.2.11 /** Remove all the <code>PANode</code>s that appear in <code>set</code>
127 salcianu 1.1.2.11 from <code>this</code> thread map. */
128 salcianu 1.1.2.11 public void remove(Set set){
129 cananian 1.5 for (Object nodeO : set){
130 cananian 1.5 PANode node = (PANode) nodeO;
131 salcianu 1.1.2.11 hash.remove(node);
132 salcianu 1.1.2.11 }
133 salcianu 1.1.2.11 }
134 salcianu 1.1.2.11
135 salcianu 1.1.2.4
136 salcianu 1.1.2.1 /** <code>join</code> combines two <code>PAThreadMap</code>s in
137 salcianu 1.1.2.1 * a control-flow join poin */
138 salcianu 1.1.2.1 public void join(PAThreadMap tau2){
139 salcianu 1.1.2.1 Enumeration e = tau2.activeThreads();
140 salcianu 1.1.2.1 while(e.hasMoreElements()){
141 salcianu 1.1.2.1 PANode n = (PANode) e.nextElement();
142 salcianu 1.1.2.9 int count1 = getValue(n);
143 salcianu 1.1.2.9 int count2 = tau2.getValue(n);
144 salcianu 1.1.2.9 if(count2 > count1)
145 salcianu 1.1.2.9 switch(count2){
146 salcianu 1.1.2.9 case 1:
147 salcianu 1.1.2.9 hash.put(n,ONE);
148 salcianu 1.1.2.9 break;
149 salcianu 1.1.2.9 case 2:
150 salcianu 1.1.2.9 hash.put(n,TWO);
151 salcianu 1.1.2.9 break;
152 salcianu 1.1.2.9 default:
153 salcianu 1.1.2.9 System.err.println("PAThreadMap.join: Strange value!");
154 salcianu 1.1.2.9 }
155 salcianu 1.1.2.10 }
156 salcianu 1.1.2.10 }
157 salcianu 1.1.2.10
158 salcianu 1.1.2.10 /** Inserts the image of <code>tau2</code> through the <code>mu</code>
159 salcianu 1.1.2.10 mapping into <code>this</code> object.
160 salcianu 1.1.2.10 Forall <code>node</code> in <code>tau2.activeThreads</code>,
161 salcianu 1.1.2.10 forall <code>node2</code> in <code>mu(node)</code>,
162 salcianu 1.1.2.10 <code>tau(node2) += tau2(node)</code>. */
163 salcianu 1.1.2.10 public void insert(PAThreadMap tau2, Relation mu){
164 salcianu 1.1.2.10 Enumeration e = tau2.activeThreads();
165 salcianu 1.1.2.10 while(e.hasMoreElements()){
166 salcianu 1.1.2.10 PANode node = (PANode) e.nextElement();
167 salcianu 1.1.2.10 int tau_node = tau2.getValue(node);
168 cananian 1.5 for (Object new_nodeO : mu.getValues(node)){
169 cananian 1.5 PANode new_node = (PANode) new_nodeO;
170 salcianu 1.1.2.10 add(new_node,tau_node);
171 salcianu 1.1.2.10 }
172 salcianu 1.1.2.1 }
173 salcianu 1.1.2.13 }
174 salcianu 1.1.2.13
175 salcianu 1.1.2.13 /* Specializes <code>this</code> <code>PAThreadMap</code> according to
176 salcianu 1.1.2.13 <code>map</code>, a mapping from <code>PANode<code> to
177 salcianu 1.1.2.13 <code>PANode</code>. Each node which is not explicitly mapped is
178 salcianu 1.1.2.13 considered to be mapped to itself. */
179 salcianu 1.1.2.13 public PAThreadMap specialize(final Map map){
180 salcianu 1.1.2.13 final PAThreadMap tau2 = new PAThreadMap();
181 salcianu 1.1.2.13
182 cananian 1.5 for(Object entryO : hash.entrySet()){
183 cananian 1.5 Map.Entry entry = (Map.Entry) entryO;
184 salcianu 1.1.2.13 PANode node2 = PANode.translate((PANode) entry.getKey(), map);
185 salcianu 1.1.2.13
186 salcianu 1.1.2.13 tau2.hash.put(node2, (Integer) entry.getValue());
187 salcianu 1.1.2.13 }
188 salcianu 1.1.2.13
189 salcianu 1.1.2.13 return tau2;
190 salcianu 1.1.2.1 }
191 salcianu 1.1.2.1
192 salcianu 1.1.2.2 /** Private constructor used by <code>clone</code> and
193 salcianu 1.1.2.2 * <code>keepTheEssential</code> */
194 salcianu 1.1.2.1 private PAThreadMap(Hashtable _hash){
195 salcianu 1.1.2.1 hash = _hash;
196 salcianu 1.1.2.1 }
197 salcianu 1.1.2.1
198 salcianu 1.1.2.1 /** <code>clone</code> creates a copy of <code>this</code> thread map;
199 salcianu 1.1.2.2 * by doing a simple shallow copy of the <code>hash<code> field.
200 salcianu 1.1.2.1 */
201 salcianu 1.1.2.1 public Object clone(){
202 salcianu 1.1.2.1 return new PAThreadMap((Hashtable)hash.clone());
203 salcianu 1.1.2.1 }
204 salcianu 1.1.2.1
205 salcianu 1.1.2.2 /** Produces a new <code>PAThreadMap</code> containing only the thread
206 salcianu 1.1.2.8 * nodes that appear in <code>essential_nodes</code>. */
207 salcianu 1.1.2.2 public PAThreadMap keepTheEssential(Set essential_nodes){
208 salcianu 1.1.2.2 Hashtable _hash = new Hashtable();
209 cananian 1.5 for (Object entryO : hash.entrySet()){
210 cananian 1.5 Map.Entry entry = (Map.Entry) entryO;
211 salcianu 1.1.2.2 PANode node = (PANode)entry.getKey();
212 salcianu 1.1.2.2 if(essential_nodes.contains(node))
213 salcianu 1.1.2.2 _hash.put(node,entry.getValue());
214 salcianu 1.1.2.2 }
215 salcianu 1.1.2.2 return new PAThreadMap(_hash);
216 salcianu 1.1.2.4 }
217 salcianu 1.1.2.4
218 salcianu 1.1.2.4 /** Checks the equality of two <code>PAThreadMap</code>s */
219 salcianu 1.1.2.4 public boolean equals(Object o){
220 salcianu 1.1.2.4 if(o==null) return false;
221 salcianu 1.1.2.4 PAThreadMap tau2 = (PAThreadMap) o;
222 salcianu 1.1.2.4 Set set1 = activeThreadSet();
223 salcianu 1.1.2.4 Set set2 = tau2.activeThreadSet();
224 salcianu 1.1.2.4 // two PAThreadMap's are equal if they contain the same keys
225 salcianu 1.1.2.4 if(!set1.equals(set2)){
226 salcianu 1.1.2.5 ///System.out.println("PAThreadMap.equals(): different keySet's");
227 salcianu 1.1.2.5 ///System.out.print("Old " + tau2);
228 salcianu 1.1.2.5 ///System.out.print("New " + this);
229 salcianu 1.1.2.4 return false;
230 salcianu 1.1.2.4 }
231 cananian 1.5 for (Object nodeO : set1){
232 cananian 1.5 PANode node = (PANode) nodeO;
233 salcianu 1.1.2.4 // and assign the same values to them
234 salcianu 1.1.2.4 if(getValue(node)!=tau2.getValue(node)){
235 salcianu 1.1.2.5 ///System.out.println("PAThreadMap.equals(): " +
236 salcianu 1.1.2.5 /// "different values assigned to " + node +
237 salcianu 1.1.2.5 /// " v1=" + tau2.getValue(node) +
238 salcianu 1.1.2.5 /// " v2=" + getValue(node));
239 salcianu 1.1.2.4 return false;
240 salcianu 1.1.2.4 }
241 salcianu 1.1.2.4 }
242 salcianu 1.1.2.4 return true;
243 salcianu 1.1.2.2 }
244 salcianu 1.1.2.2
245 salcianu 1.1.2.8 /** Pretty print function for debug purposes.
246 salcianu 1.1.2.8 <code>tau1.equals(tau2) <==> tau1.toString().equals(tau2.toString()).</code> */
247 salcianu 1.1.2.1 public String toString(){
248 salcianu 1.1.2.1 StringBuffer buffer = new StringBuffer("Parallel Thread Map:\n");
249 salcianu 1.1.2.8
250 salcianu 1.1.2.8 Object[] active_threads = Debug.sortedSet(hash.keySet());
251 salcianu 1.1.2.8
252 salcianu 1.1.2.8 for(int i = 0 ; i < active_threads.length ; i++){
253 salcianu 1.1.2.8 Object thread = active_threads[i];
254 salcianu 1.1.2.8 Object value = hash.get(thread);
255 salcianu 1.1.2.8 buffer.append(" " + thread + " -> " + value + "\n");
256 salcianu 1.1.2.1 }
257 salcianu 1.1.2.8
258 salcianu 1.1.2.8 return buffer.toString();
259 salcianu 1.1.2.1 }
260 salcianu 1.1.2.1
261 salcianu 1.1.2.1 }
262 cananian 1.2