1 cananian 1.1.2.1 // CacheEquivalence.java, created Wed Jun 6 15:06:02 2001 by cananian
2 cananian 1.1.2.1 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Tree;
5 cananian 1.1.2.1
6 cananian 1.1.2.17 import harpoon.Analysis.ClassHierarchy;
7 cananian 1.1.2.1 import harpoon.Analysis.DomTree;
8 cananian 1.1.2.4 import harpoon.Analysis.ReachingDefs;
9 cananian 1.1.2.4 import harpoon.Analysis.ReachingDefsAltImpl;
10 cananian 1.1.2.1 import harpoon.Analysis.Maps.Derivation.DList;
11 cananian 1.1.2.5 import harpoon.Backend.Generic.Runtime.TreeBuilder;
12 cananian 1.1.2.4 import harpoon.ClassFile.HClass;
13 cananian 1.3.2.2 import harpoon.ClassFile.HCode;
14 cananian 1.1.2.4 import harpoon.ClassFile.HCode.PrintCallback;
15 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
16 cananian 1.1.2.4 import harpoon.IR.Properties.CFGrapher;
17 cananian 1.1.2.4 import harpoon.IR.Properties.UseDefer;
18 cananian 1.1.2.4 import harpoon.IR.Tree.BINOP;
19 cananian 1.1.2.4 import harpoon.IR.Tree.Bop;
20 cananian 1.1.2.4 import harpoon.IR.Tree.CALL;
21 cananian 1.1.2.4 import harpoon.IR.Tree.CONST;
22 cananian 1.1.2.1 import harpoon.IR.Tree.Code;
23 cananian 1.1.2.4 import harpoon.IR.Tree.ESEQ;
24 cananian 1.1.2.1 import harpoon.IR.Tree.Exp;
25 cananian 1.1.2.1 import harpoon.IR.Tree.ExpList;
26 cananian 1.1.2.4 import harpoon.IR.Tree.INVOCATION;
27 cananian 1.1.2.1 import harpoon.IR.Tree.MEM;
28 cananian 1.1.2.4 import harpoon.IR.Tree.METHOD;
29 cananian 1.1.2.1 import harpoon.IR.Tree.MOVE;
30 cananian 1.1.2.4 import harpoon.IR.Tree.NAME;
31 cananian 1.1.2.4 import harpoon.IR.Tree.Print;
32 cananian 1.1.2.1 import harpoon.IR.Tree.Stm;
33 cananian 1.1.2.1 import harpoon.IR.Tree.TEMP;
34 cananian 1.1.2.1 import harpoon.IR.Tree.Tree;
35 cananian 1.1.2.1 import harpoon.IR.Tree.TreeDerivation;
36 cananian 1.1.2.1 import harpoon.IR.Tree.TreeKind;
37 cananian 1.1.2.4 import harpoon.IR.Tree.TreeVisitor;
38 cananian 1.1.2.4 import harpoon.IR.Tree.Type;
39 cananian 1.1.2.4 import harpoon.IR.Tree.UNOP;
40 cananian 1.1.2.4 import harpoon.IR.Tree.Uop;
41 cananian 1.1.2.4 import harpoon.Temp.Label;
42 cananian 1.1.2.1 import harpoon.Temp.Temp;
43 cananian 1.5 import net.cscott.jutil.GenericMultiMap;
44 cananian 1.5 import net.cscott.jutil.MultiMap;
45 cananian 1.5 import net.cscott.jutil.Default;
46 cananian 1.5 import net.cscott.jutil.Environment;
47 cananian 1.5 import net.cscott.jutil.HashEnvironment;
48 cananian 1.1.2.4 import harpoon.Util.Util;
49 cananian 1.5 import net.cscott.jutil.WorkSet;
50 cananian 1.1.2.1
51 cananian 1.1.2.14 import java.util.Arrays;
52 cananian 1.1.2.4 import java.util.Collection;
53 cananian 1.1.2.2 import java.util.Collections;
54 cananian 1.1.2.1 import java.util.HashMap;
55 cananian 1.1.2.1 import java.util.HashSet;
56 cananian 1.1.2.4 import java.util.Iterator;
57 cananian 1.1.2.4 import java.util.List;
58 cananian 1.1.2.1 import java.util.Map;
59 cananian 1.1.2.1 import java.util.Set;
60 cananian 1.1.2.1 /**
61 cananian 1.1.2.1 * <code>CacheEquivalence</code> creates tag-check equivalence classes
62 cananian 1.1.2.1 * for MEM operations in a Tree.
63 cananian 1.1.2.1 *
64 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
65 cananian 1.5 * @version $Id: CacheEquivalence.java,v 1.5 2004/02/08 01:54:28 cananian Exp $
66 cananian 1.1.2.1 */
67 cananian 1.1.2.1 public class CacheEquivalence {
68 cananian 1.1.2.4 private static final boolean DEBUG=false;
69 cananian 1.1.2.5 private static final int CACHE_LINE_SIZE = 32; /* bytes */
70 cananian 1.1.2.4
71 cananian 1.1.2.1 /** Creates a <code>CacheEquivalence</code>. */
72 cananian 1.1.2.17 public CacheEquivalence(harpoon.IR.Tree.Code code, ClassHierarchy ch) {
73 cananian 1.3.2.2 CFGrapher<Tree> cfg = code.getGrapher();
74 cananian 1.3.2.2 UseDefer<Tree> udr = code.getUseDefer();
75 cananian 1.1.2.1 TreeDerivation td = code.getTreeDerivation();
76 cananian 1.1.2.4 /* new analysis */
77 cananian 1.3.2.3 final AlignmentAnalysis df = new AlignmentAnalysis(code, cfg, udr, td);
78 cananian 1.1.2.16 /*- construct cache eq -*/
79 cananian 1.1.2.17 new TagDominate(code, cfg, td, ch, df);
80 cananian 1.1.2.16 /* debugging information dump */
81 cananian 1.1.2.4 if (DEBUG) {
82 cananian 1.1.2.4 harpoon.IR.Tree.Print.print(new java.io.PrintWriter(System.out),
83 cananian 1.1.2.4 code, new PrintCallback() {
84 cananian 1.1.2.4 public void printAfter(java.io.PrintWriter pw,
85 cananian 1.1.2.4 HCodeElement hce) {
86 cananian 1.1.2.4 if (hce instanceof Exp) {
87 cananian 1.1.2.4 Exp e = (Exp) hce;
88 cananian 1.1.2.4 Tree t = e;
89 cananian 1.1.2.4 while (!(t instanceof Stm))
90 cananian 1.1.2.4 t = t.getParent();
91 cananian 1.1.2.4 pw.print(" [VAL: "+df.valueOf(e, (Stm)t)+"]");
92 cananian 1.1.2.4 }
93 cananian 1.1.2.16 if (hce instanceof MEM) {
94 cananian 1.1.2.16 pw.print(" [CQ: "+cache_equiv.get(hce)+"]");
95 cananian 1.1.2.16 }
96 cananian 1.1.2.4 }
97 cananian 1.1.2.4 });
98 cananian 1.1.2.4 }
99 cananian 1.1.2.1 }
100 cananian 1.1.2.5 /* -------- cache equivalence pass ------- */
101 cananian 1.1.2.5 private class TagDominate {
102 cananian 1.1.2.17 final ClassHierarchy ch;
103 cananian 1.1.2.5 final TreeDerivation td;
104 cananian 1.3.2.3 final AlignmentAnalysis df;
105 cananian 1.1.2.5 final DomTree dt;
106 cananian 1.1.2.5 final TreeBuilder tb;
107 cananian 1.1.2.17 TagDominate(Code c, CFGrapher cfg, TreeDerivation td,
108 cananian 1.3.2.3 ClassHierarchy ch, AlignmentAnalysis df) {
109 cananian 1.1.2.17 this.ch = ch;
110 cananian 1.1.2.5 this.td = td;
111 cananian 1.1.2.5 this.df = df;
112 cananian 1.1.2.18 this.tb = c.getFrame().getRuntime().getTreeBuilder();
113 cananian 1.1.2.5 this.dt = new DomTree(c, cfg, false);
114 cananian 1.1.2.1
115 cananian 1.1.2.5 final Environment e = new HashEnvironment();
116 cananian 1.1.2.5 HCodeElement[] roots = dt.roots();
117 cananian 1.1.2.5 for (int i=0; i<roots.length; i++)
118 cananian 1.1.2.5 traverseDT((Stm) roots[i], e);
119 cananian 1.1.2.5 }
120 cananian 1.1.2.5 /* analyze stms travelling down the dominator tree */
121 cananian 1.1.2.5 void traverseDT(Stm stm, Environment e) {
122 cananian 1.1.2.5 /* save environment */
123 cananian 1.1.2.5 Environment.Mark mark = e.getMark();
124 cananian 1.1.2.5 /* do analysis */
125 cananian 1.1.2.5 analyze(stm, e);
126 cananian 1.1.2.5 /* recurse */
127 cananian 1.1.2.5 HCodeElement[] child = dt.children(stm);
128 cananian 1.1.2.5 for (int i=0; i<child.length; i++)
129 cananian 1.1.2.5 traverseDT((Stm)child[i], e);
130 cananian 1.1.2.5 /* restore environment */
131 cananian 1.1.2.5 e.undoToMark(mark);
132 cananian 1.1.2.5 /* done! */
133 cananian 1.1.2.5 return;
134 cananian 1.1.2.5 }
135 cananian 1.1.2.5 /* analyze one statement in the environment defined by map m */
136 cananian 1.1.2.5 void analyze(Stm stm, Map pre) {
137 cananian 1.1.2.5 Map post = new HashMap();
138 cananian 1.1.2.5 /* first look for all *reads* */
139 cananian 1.1.2.5 /* There is NO ORDER defined for any of these. */
140 cananian 1.1.2.5 for (ExpList el=stm.kids(); el!=null; el=el.tail) {
141 cananian 1.1.2.5 add(stm, el.head, pre, post, true);
142 cananian 1.1.2.5 }
143 cananian 1.1.2.5 /* now all post mappings get added to pre */
144 cananian 1.1.2.5 pre.putAll(post); post.clear();
145 cananian 1.1.2.5 /* now look for writes (which must happen after reads) */
146 cananian 1.1.2.5 if (stm.kind()==TreeKind.MOVE)
147 cananian 1.1.2.5 add(stm, ((MOVE)stm).getDst(), pre, post, false);
148 cananian 1.1.2.5 pre.putAll(post); post.clear();
149 cananian 1.1.2.5 }
150 cananian 1.1.2.5 void add(Stm root, Exp e, Map pre, Map post, boolean recurse) {
151 cananian 1.1.2.5 if (e.kind()==TreeKind.MEM) {
152 cananian 1.1.2.5 MEM mem = (MEM) e; Exp memexp = mem.getExp();
153 cananian 1.3.2.3 AlignmentAnalysis.Value v = df.valueOf(memexp, root);
154 cananian 1.1.2.5 // cases:
155 cananian 1.1.2.14 // 1a) known base & known offset.
156 cananian 1.1.2.14 // 1b) known base & offset mod N, in a kgroup.
157 cananian 1.1.2.14 // (N mod CACHE_LINE_SIZE must be zero)
158 cananian 1.1.2.14 // 1c) known base & offset mod N, in a kgroup.
159 cananian 1.1.2.14 // (where CACHE_LINE_SIZE mod N must be zero)
160 cananian 1.1.2.5 // 2) known base & unknown offset, but object is smaller
161 cananian 1.1.2.5 // than cache line size.
162 cananian 1.1.2.5 // 3) all others.
163 cananian 1.3.2.3 AlignmentAnalysis.DefPoint dp = null;
164 cananian 1.3.2.3 AlignmentAnalysis.KGroup kgroup = null;
165 cananian 1.1.2.14 long line=0; long modulus=0;
166 cananian 1.1.2.14 if (v.isBaseKnown() &&
167 cananian 1.3.2.3 ((AlignmentAnalysis.BaseAndOffset)v).def.isWellTyped()) {
168 cananian 1.3.2.3 AlignmentAnalysis.BaseAndOffset bao = (AlignmentAnalysis.BaseAndOffset) v;
169 cananian 1.1.2.17 if (maxObjSize(bao.def.type()) <= CACHE_LINE_SIZE
170 cananian 1.1.2.14 // arrays can't count as small because
171 cananian 1.1.2.14 // length is not statically known.
172 cananian 1.1.2.14 && !bao.def.type().isArray()) {
173 cananian 1.1.2.14 /* case 2 */
174 cananian 1.3.2.3 assert (bao.offset instanceof AlignmentAnalysis.Constant ?
175 cananian 1.3.2.3 ((AlignmentAnalysis.Constant)bao.offset)
176 cananian 1.1.2.17 .number < CACHE_LINE_SIZE : true);
177 cananian 1.1.2.14 dp = bao.def; line = 0; // case 2
178 cananian 1.3.2.3 } else if (bao.offset instanceof AlignmentAnalysis.Constant) {
179 cananian 1.1.2.14 /* case 1a */
180 cananian 1.3.2.3 AlignmentAnalysis.Constant c = (AlignmentAnalysis.Constant) bao.offset;
181 cananian 1.1.2.14 dp = bao.def; line = c.number/CACHE_LINE_SIZE;
182 cananian 1.3.2.3 } else if (bao.offset instanceof AlignmentAnalysis.ConstantModuloN){
183 cananian 1.3.2.3 AlignmentAnalysis.ConstantModuloN cmn =
184 cananian 1.3.2.3 (AlignmentAnalysis.ConstantModuloN) bao.offset;
185 cananian 1.1.2.14 if (cmn.kgroup!=null) {
186 cananian 1.1.2.14 if (0==(cmn.modulus % CACHE_LINE_SIZE)) {
187 cananian 1.1.2.14 /* case 1b */
188 cananian 1.1.2.14 dp = bao.def; kgroup=cmn.kgroup;
189 cananian 1.1.2.14 line = cmn.number / CACHE_LINE_SIZE;
190 cananian 1.1.2.14 modulus = cmn.modulus;
191 cananian 1.1.2.14 } else if (0==(CACHE_LINE_SIZE % cmn.modulus)) {
192 cananian 1.1.2.14 /* case 1c */
193 cananian 1.1.2.14 dp = bao.def; kgroup=cmn.kgroup;
194 cananian 1.1.2.14 // note that we can't guarantee that
195 cananian 1.1.2.14 // k*modulus is on a cache line boundary.
196 cananian 1.1.2.14 line = cmn.number / cmn.modulus;
197 cananian 1.1.2.14 modulus = cmn.modulus;
198 cananian 1.1.2.14 }
199 cananian 1.1.2.5 }
200 cananian 1.1.2.5 }
201 cananian 1.1.2.5 }
202 cananian 1.1.2.14 if (dp!=null) { // cases 1abc and 2
203 cananian 1.1.2.14 List key = Arrays.asList(new Object[] {
204 cananian 1.1.2.14 dp, new Long(line), new Long(modulus), kgroup
205 cananian 1.1.2.14 });
206 cananian 1.1.2.14 CacheEquivSet ces = (CacheEquivSet) pre.get(key);
207 cananian 1.1.2.5 if (ces==null) ces = new CacheEquivSet(mem);
208 cananian 1.1.2.5 else ces.others.add(mem);
209 cananian 1.1.2.5 cache_equiv.put(mem, ces);
210 cananian 1.1.2.14 post.put(key, ces);
211 cananian 1.1.2.5 } else { // case 3
212 cananian 1.1.2.5 cache_equiv.put(mem, new CacheEquivSet(mem));
213 cananian 1.1.2.5 }
214 cananian 1.1.2.5 }
215 cananian 1.1.2.5 if (recurse)
216 cananian 1.1.2.5 for (Tree tp=e.getFirstChild(); tp!=null; tp=tp.getSibling())
217 cananian 1.1.2.5 add(root, (Exp)tp, pre, post, recurse);
218 cananian 1.1.2.5 }
219 cananian 1.1.2.17 // returns the size of an object of the specified class.
220 cananian 1.1.2.5 int objSize(HClass hc) { return tb.headerSize(hc)+tb.objectSize(hc); }
221 cananian 1.1.2.17 // returns the maximum size of an object of the specified type.
222 cananian 1.1.2.17 // this must account for any subclasses of the type, which likely
223 cananian 1.1.2.17 // are larger than it is.
224 cananian 1.1.2.17 int maxObjSize(HClass hc) {
225 cananian 1.1.2.17 if (!sizeCache.containsKey(hc)) {
226 cananian 1.1.2.17 // compute maximum object size recursively.
227 cananian 1.1.2.17 int size = objSize(hc);
228 cananian 1.3.2.3 for (Iterator<HClass> it=ch.children(hc).iterator();
229 cananian 1.3.2.3 it.hasNext(); )
230 cananian 1.3.2.3 size = Math.max(size, maxObjSize(it.next()));
231 cananian 1.1.2.17 sizeCache.put(hc, new Integer(size));
232 cananian 1.1.2.17 }
233 cananian 1.3.2.3 return sizeCache.get(hc).intValue();
234 cananian 1.1.2.17 }
235 cananian 1.1.2.17 // keep an object size cache for speed.
236 cananian 1.3.2.3 private final Map<HClass,Integer> sizeCache =
237 cananian 1.3.2.3 new HashMap<HClass,Integer>();
238 cananian 1.1.2.5 }
239 cananian 1.1.2.4
240 cananian 1.1.2.4 /*----------------------------------------------------------------*/
241 cananian 1.1.2.4
242 cananian 1.1.2.4 /** defines the properties of cache-equivalence sets */
243 cananian 1.1.2.1 static class CacheEquivSet {
244 cananian 1.1.2.1 public final MEM first;
245 cananian 1.1.2.1 public final Set others = new HashSet();
246 cananian 1.1.2.1 public CacheEquivSet(MEM mem) { this.first = mem; }
247 cananian 1.1.2.16 public String toString() {
248 cananian 1.1.2.16 return "<TAG DEF:"+first+"; USE:"+others+">";
249 cananian 1.1.2.16 }
250 cananian 1.1.2.1 }
251 cananian 1.1.2.1 final Map cache_equiv = new HashMap();
252 cananian 1.1.2.1
253 cananian 1.1.2.1 /** Returns the number of memory operations which share the same
254 cananian 1.1.2.1 * tag as this memory operation. 1 indicates no sharing possible. */
255 cananian 1.1.2.2 public int num_using_this_tag(MEM mem) {
256 cananian 1.1.2.1 return ((CacheEquivSet) cache_equiv.get(mem)).others.size() + 1;
257 cananian 1.1.2.1 }
258 cananian 1.1.2.1 /** Returns 'true' if this operation requires a tag check. If
259 cananian 1.1.2.1 * ops_using_this_tag(mem) is also true, then you should store the
260 cananian 1.1.2.1 * result of the tag check some where for further use. */
261 cananian 1.1.2.1 public boolean needs_tag_check(MEM mem) {
262 cananian 1.1.2.1 return whose_tag_check(mem) == mem;
263 cananian 1.1.2.1 }
264 cananian 1.1.2.1 /** Returns the MEM operation which should have stored the
265 cananian 1.1.2.1 * necessary tag information for this MEM operation. */
266 cananian 1.1.2.1 public MEM whose_tag_check(MEM mem) {
267 cananian 1.1.2.1 return ((CacheEquivSet) cache_equiv.get(mem)).first;
268 cananian 1.1.2.2 }
269 cananian 1.1.2.2 /** Returns all the MEM operations which use the tag defined
270 cananian 1.1.2.2 * by whose_tag_check(mem) */
271 cananian 1.1.2.2 public Set ops_using_this_tag(MEM mem) {
272 cananian 1.1.2.2 return Collections.unmodifiableSet
273 cananian 1.1.2.2 (((CacheEquivSet) cache_equiv.get(mem)).others);
274 cananian 1.1.2.1 }
275 cananian 1.2 }