1 cananian 1.1 // UseDef.java, created Thu Sep 10 15:17:10 1998 by cananian
2 cananian 1.10 // Copyright (C) 1998 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.10 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1 package harpoon.Analysis;
5 cananian 1.1
6 cananian 1.10.2.3 import harpoon.ClassFile.HCode;
7 cananian 1.10.2.3 import harpoon.ClassFile.HCodeElement;
8 cananian 1.1 import harpoon.Temp.Temp;
9 cananian 1.11.2.1 import harpoon.Util.ArrayIterator;
10 cananian 1.14 import net.cscott.jutil.Default;
11 cananian 1.14 import net.cscott.jutil.IteratorEnumerator;
12 cananian 1.1 import harpoon.Util.Util;
13 cananian 1.1
14 cananian 1.1 import java.util.Enumeration;
15 cananian 1.10.2.5 import java.util.HashMap;
16 cananian 1.10.2.5 import java.util.HashSet;
17 cananian 1.10.2.5 import java.util.Iterator;
18 cananian 1.10.2.5 import java.util.Map;
19 cananian 1.10.2.5 import java.util.Set;
20 cananian 1.1 /**
21 cananian 1.5 * <code>UseDef</code> objects map <code>Temp</code>s to the
22 cananian 1.5 * <code>HCodeElement</code>s which use or define
23 cananian 1.5 * them. The <code>UseDef</code> caches its results, so you should
24 cananian 1.5 * throw away your current <code>UseDef</code> object and make
25 cananian 1.5 * another one if you make modifications to the IR.
26 cananian 1.1 *
27 cananian 1.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
28 cananian 1.15 * @version $Id: UseDef.java,v 1.15 2004/02/08 03:19:12 cananian Exp $
29 cananian 1.1 */
30 cananian 1.1
31 cananian 1.13 public class UseDef<HCE extends HCodeElement>
32 cananian 1.13 implements harpoon.Analysis.Maps.UseDefMap<HCE> {
33 cananian 1.1 /** Creates a new, empty <code>UseDef</code>. */
34 cananian 1.1 public UseDef() { }
35 cananian 1.1
36 cananian 1.13 Map<HCode<HCE>,allTempList> analyzed =
37 cananian 1.13 new HashMap<HCode<HCE>,allTempList>();
38 cananian 1.13 Map<Temp,HCE[]> useMap = new HashMap<Temp,HCE[]>();
39 cananian 1.13 Map<Temp,HCE[]> defMap = new HashMap<Temp,HCE[]>();
40 cananian 1.1
41 cananian 1.5 static class allTempList {
42 cananian 1.5 Temp[] used;
43 cananian 1.5 Temp[] defined;
44 cananian 1.9 Temp[] all;
45 cananian 1.9 allTempList(Temp[] used, Temp[] defined, Temp[] all) {
46 cananian 1.9 this.used = used; this.defined = defined; this.all = all;
47 cananian 1.5 }
48 cananian 1.5 }
49 cananian 1.5
50 cananian 1.13 void associate(HCE hce, Temp[] tl,
51 cananian 1.13 Map<Temp,Set<HCE>> map,
52 cananian 1.13 Set<Temp> allTemps1, Set<Temp> allTemps2) {
53 cananian 1.5 for (int i=0; i<tl.length; i++) {
54 cananian 1.13 Set<HCE> s = map.get(tl[i]);
55 cananian 1.13 if (s==null) { s = new HashSet<HCE>(); map.put(tl[i], s); }
56 cananian 1.10.2.5 s.add(hce);
57 cananian 1.10.2.5 allTemps1.add(tl[i]);
58 cananian 1.10.2.5 allTemps2.add(tl[i]);
59 cananian 1.5 }
60 cananian 1.5 }
61 cananian 1.5
62 cananian 1.13 Temp[] set2temps(Set<Temp> s) {
63 cananian 1.13 return s.toArray(new Temp[s.size()]);
64 cananian 1.5 }
65 cananian 1.13 HCE[] set2hces(HCode<HCE> hc, Set<HCE> s) {
66 cananian 1.13 return s.toArray(hc.elementArrayFactory().newArray(s.size()));
67 cananian 1.5 }
68 cananian 1.1
69 cananian 1.13 HCode<HCE> lastHCode = null;
70 cananian 1.13 void analyze(HCode<HCE> code) {
71 cananian 1.5 // make sure we don't analyze an HCode multiple times.
72 cananian 1.7 if (code==lastHCode) return; // we just did this one.
73 cananian 1.7 if (analyzed.containsKey(code)) return; // check the hash table.
74 cananian 1.7 lastHCode = code;
75 cananian 1.5
76 cananian 1.13 HCE[] el = code.getElements();
77 cananian 1.10.2.6 if (!(el instanceof harpoon.IR.Properties.UseDefable[]))
78 cananian 1.10.2.6 throw new Error(code.getName() + " does not implement UseDefable");
79 cananian 1.10.2.6 harpoon.IR.Properties.UseDefable[] udl =
80 cananian 1.10.2.6 (harpoon.IR.Properties.UseDefable[]) el;
81 cananian 1.5
82 cananian 1.13 Map<Temp,Set<HCE>> workUse = new HashMap<Temp,Set<HCE>>();
83 cananian 1.13 Map<Temp,Set<HCE>> workDef = new HashMap<Temp,Set<HCE>>();
84 cananian 1.13 Set<Temp> defined = new HashSet<Temp>();
85 cananian 1.13 Set<Temp> used = new HashSet<Temp>();
86 cananian 1.13 Set<Temp> all = new HashSet<Temp>();
87 cananian 1.1
88 cananian 1.5 // Scan through and associate uses and defs with their HCodeElements
89 cananian 1.5 for (int i=0; i<el.length; i++) {
90 cananian 1.9 associate(el[i], udl[i].use(), workUse, used, all);
91 cananian 1.9 associate(el[i], udl[i].def(), workDef, defined, all);
92 cananian 1.1 }
93 cananian 1.5 // replace UniqueVectors with HCodeElement arrays to save space.
94 cananian 1.15 for (Temp u : workUse.keySet()) {
95 cananian 1.13 useMap.put(u, set2hces(code, workUse.get(u)));
96 cananian 1.5 }
97 cananian 1.15 for (Temp d : workDef.keySet()) {
98 cananian 1.13 defMap.put(d, set2hces(code, workDef.get(d)));
99 cananian 1.1 }
100 cananian 1.5 // store set of all temps & mark as analyzed.
101 cananian 1.8 analyzed.put(code, new allTempList(set2temps(used),
102 cananian 1.9 set2temps(defined),
103 cananian 1.9 set2temps(all)));
104 cananian 1.5 }
105 cananian 1.2
106 cananian 1.5 /** Return the HCodeElements which define a given Temp. */
107 cananian 1.13 public HCE[] defMap(HCode<HCE> hc, Temp t) {
108 cananian 1.5 analyze(hc);
109 cananian 1.13 HCE[] r = defMap.get(t);
110 cananian 1.5 return (r == null) ?
111 cananian 1.13 hc.elementArrayFactory().newArray(0) :
112 cananian 1.13 Util.safeCopy(hc.elementArrayFactory(), r);
113 cananian 1.9 }
114 cananian 1.5 /** Return the HCodeElements which use a given Temp. */
115 cananian 1.13 public HCE[] useMap(HCode<HCE> hc, Temp t) {
116 cananian 1.5 analyze(hc);
117 cananian 1.13 HCE[] r = useMap.get(t);
118 cananian 1.5 return (r == null) ?
119 cananian 1.13 hc.elementArrayFactory().newArray(0) :
120 cananian 1.13 Util.safeCopy(hc.elementArrayFactory(), r);
121 cananian 1.9 }
122 cananian 1.5 /** Return an array of all Temps defined in a given HCode. */
123 cananian 1.13 public Temp[] allDefs(HCode<HCE> hc) {
124 cananian 1.5 analyze(hc);
125 cananian 1.13 allTempList atl = analyzed.get(hc);
126 cananian 1.13 return Util.safeCopy(Temp.arrayFactory, atl.defined);
127 cananian 1.9 }
128 cananian 1.5 /** Return an array of all Temps used in a given HCode. */
129 cananian 1.13 public Temp[] allUses(HCode<HCE> hc) {
130 cananian 1.5 analyze(hc);
131 cananian 1.13 allTempList atl = analyzed.get(hc);
132 cananian 1.13 return Util.safeCopy(Temp.arrayFactory, atl.used);
133 cananian 1.9 }
134 cananian 1.9 /** Return an array of all Temps used or defined in a given HCode. */
135 cananian 1.13 public Temp[] allTemps(HCode<HCE> hc) {
136 cananian 1.9 analyze(hc);
137 cananian 1.13 allTempList atl = analyzed.get(hc);
138 cananian 1.13 return Util.safeCopy(Temp.arrayFactory, atl.all);
139 cananian 1.1 }
140 cananian 1.1 }