1 kkz 1.1.2.1 // WriteBarrierTreePass.java, created Tue Aug 21 20:20:44 2001 by kkz
2 kkz 1.1.2.1 // Copyright (C) 2000 Karen Zee <kkz@tmi.lcs.mit.edu>
3 kkz 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 kkz 1.1.2.1 package harpoon.Analysis.PreciseGC;
5 kkz 1.1.2.1
6 kkz 1.1.2.1 import harpoon.Analysis.ClassHierarchy;
7 kkz 1.1.2.1 import harpoon.Analysis.Tree.Canonicalize;
8 kkz 1.1.2.1 import harpoon.Backend.Generic.Frame;
9 kkz 1.1.2.1 import harpoon.Backend.Generic.Runtime;
10 kkz 1.1.2.1 import harpoon.Backend.Generic.Runtime.TreeBuilder;
11 kkz 1.1.2.1 import harpoon.Backend.Maps.NameMap;
12 kkz 1.1.2.1 import harpoon.ClassFile.HClass;
13 kkz 1.1.2.1 import harpoon.ClassFile.HCode;
14 kkz 1.1.2.1 import harpoon.ClassFile.HCodeElement;
15 kkz 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
16 kkz 1.1.2.1 import harpoon.ClassFile.HField;
17 kkz 1.1.2.1 import harpoon.ClassFile.HMethod;
18 kkz 1.1.2.1 import harpoon.ClassFile.Linker;
19 kkz 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
20 kkz 1.1.2.1 import harpoon.IR.Tree.BINOP;
21 kkz 1.1.2.1 import harpoon.IR.Tree.Bop;
22 kkz 1.1.2.1 import harpoon.IR.Tree.CALL;
23 kkz 1.1.2.1 import harpoon.IR.Tree.CanonicalTreeCode;
24 kkz 1.1.2.1 import harpoon.IR.Tree.CONST;
25 kkz 1.1.2.1 import harpoon.IR.Tree.DATUM;
26 kkz 1.1.2.1 import harpoon.IR.Tree.DerivationGenerator;
27 kkz 1.1.2.1 import harpoon.IR.Tree.Exp;
28 kkz 1.1.2.1 import harpoon.IR.Tree.ExpList;
29 kkz 1.1.2.1 import harpoon.IR.Tree.LABEL;
30 kkz 1.1.2.1 import harpoon.IR.Tree.METHOD;
31 kkz 1.1.2.1 import harpoon.IR.Tree.NAME;
32 kkz 1.1.2.1 import harpoon.IR.Tree.NATIVECALL;
33 kkz 1.1.2.1 import harpoon.IR.Tree.Print;
34 kkz 1.1.2.1 import harpoon.IR.Tree.SEGMENT;
35 kkz 1.1.2.1 import harpoon.IR.Tree.SEQ;
36 kkz 1.1.2.1 import harpoon.IR.Tree.Stm;
37 kkz 1.1.2.1 import harpoon.IR.Tree.Tree;
38 kkz 1.1.2.1 import harpoon.IR.Tree.TreeFactory;
39 kkz 1.1.2.1 import harpoon.IR.Tree.TEMP;
40 kkz 1.1.2.1 import harpoon.IR.Tree.Translation;
41 kkz 1.1.2.1 import harpoon.IR.Tree.Type;
42 kkz 1.1.2.1 import harpoon.Temp.Label;
43 kkz 1.1.2.1 import harpoon.Util.Util;
44 kkz 1.1.2.1
45 kkz 1.1.2.1 import java.util.Arrays;
46 kkz 1.1.2.1 import java.util.HashMap;
47 kkz 1.1.2.1 import java.util.Iterator;
48 kkz 1.1.2.1 import java.util.List;
49 kkz 1.1.2.1 import java.util.Map;
50 kkz 1.1.2.1 /**
51 kkz 1.1.2.1 * <code>WriteBarrierTreePass</code> performs some low-level
52 kkz 1.1.2.1 * transformations to the output of <code>WriteBarrierQuadPass</code>
53 kkz 1.1.2.1 * which cannot be done in the quad form on which
54 kkz 1.1.2.1 * <code>WriteBarrierQuadPass</code> operates.
55 kkz 1.1.2.1 * <code>>WriteBarrierTreePass</code> works on tree form.
56 kkz 1.1.2.1 * <p>
57 kkz 1.1.2.1 * This pass is invoked by
58 kkz 1.1.2.1 * <code>WriteBarrierQuadPass.treeCodeFactory()</code>.
59 kkz 1.1.2.1 *
60 kkz 1.1.2.1 *
61 kkz 1.1.2.1 * @author Karen Zee <kkz@tmi.lcs.mit.edu>
62 cananian 1.6 * @version $Id: WriteBarrierTreePass.java,v 1.6 2003/03/11 19:15:42 cananian Exp $
63 kkz 1.1.2.1 */
64 kkz 1.1.2.1 public abstract class WriteBarrierTreePass extends
65 kkz 1.1.2.1 harpoon.Analysis.Tree.Simplification {
66 kkz 1.1.2.1
67 kkz 1.1.2.1 // hide constructor
68 kkz 1.1.2.1 private WriteBarrierTreePass() { }
69 kkz 1.1.2.1
70 kkz 1.1.2.1 /** Code factory for applying <code>WriteBarrierTreePass</code>
71 kkz 1.1.2.1 * to a canonical tree. Clones the tree before doing
72 kkz 1.1.2.1 * transformation in-place. */
73 kkz 1.5 static public HCodeFactory codeFactory(final HCodeFactory parent,
74 kkz 1.5 final Frame f,
75 kkz 1.5 final ClassHierarchy ch,
76 kkz 1.5 final Linker linker) {
77 kkz 1.5 HClass WBC = linker.forName("harpoon.Runtime.PreciseGC.WriteBarrier");
78 kkz 1.5 HClass JLO = linker.forName("java.lang.Object");
79 kkz 1.5 HClass JLRF = linker.forName("java.lang.reflect.Field");
80 kkz 1.5 final HMethod arrayHM = WBC.getMethod("asc", new HClass[]
81 kkz 1.5 {JLO,HClass.Int,JLO,HClass.Int});
82 kkz 1.5 final HMethod fieldHM = WBC.getMethod("fsc", new HClass[]
83 kkz 1.5 {JLO,JLRF,JLO,HClass.Int});
84 cananian 1.3.2.1 assert parent.getCodeName().equals(CanonicalTreeCode.codename);
85 kkz 1.1.2.1 return Canonicalize.codeFactory(new HCodeFactory() {
86 kkz 1.1.2.1 public HCode convert(HMethod m) {
87 kkz 1.1.2.1 HCode hc = parent.convert(m);
88 kkz 1.1.2.1 if (hc!=null) {
89 kkz 1.1.2.1 harpoon.IR.Tree.Code code = (harpoon.IR.Tree.Code) hc;
90 kkz 1.1.2.1 // clone code...
91 kkz 1.1.2.1 code = (harpoon.IR.Tree.Code) code.clone(m).hcode();
92 kkz 1.1.2.1 DerivationGenerator dg = null;
93 kkz 1.1.2.1 try {
94 kkz 1.1.2.1 dg = (DerivationGenerator) code.getTreeDerivation();
95 kkz 1.1.2.1 } catch (ClassCastException ex) { /* i guess not */ }
96 kkz 1.1.2.1 // ...do analysis and modify cloned code in-place.
97 kkz 1.1.2.1 simplify((Stm)code.getRootElement(), dg,
98 kkz 1.1.2.1 HCE_RULES(f, ch, arrayHM, fieldHM));
99 kkz 1.1.2.1 hc = code;
100 kkz 1.1.2.1 }
101 kkz 1.1.2.1 return hc;
102 kkz 1.1.2.1 }
103 kkz 1.1.2.1 public String getCodeName() { return parent.getCodeName(); }
104 kkz 1.1.2.1 public void clear(HMethod m) { parent.clear(m); }
105 kkz 1.1.2.1 });
106 kkz 1.1.2.1 }
107 kkz 1.1.2.1
108 cananian 1.6 private static List<Rule> HCE_RULES(final Frame f,
109 kkz 1.1.2.1 final ClassHierarchy ch,
110 kkz 1.1.2.1 final HMethod arrayHM,
111 kkz 1.1.2.1 final HMethod fieldHM) {
112 kkz 1.1.2.1 final NameMap nm = f.getRuntime().getNameMap();
113 kkz 1.1.2.1 final Label LarrayHM = nm.label(arrayHM);
114 kkz 1.1.2.1 final Label LfieldHM = nm.label(fieldHM);
115 cananian 1.6 final Map<Label,HField> fieldMap = new HashMap<Label,HField>();
116 cananian 1.6 for(Iterator<HClass> it = ch.classes().iterator(); it.hasNext(); ) {
117 cananian 1.6 HField[] fields = it.next().getFields();
118 kkz 1.1.2.1 for(int i = 0; i < fields.length; i++) {
119 kkz 1.1.2.1 fieldMap.put(nm.label(fields[i], "obj"), fields[i]);
120 kkz 1.1.2.1 }
121 kkz 1.1.2.1 }
122 kkz 1.1.2.1 final Label cfunc =
123 kkz 1.1.2.1 new Label(nm.c_function_name("generational_write_barrier"));
124 kkz 1.1.2.1 // now make rules
125 kkz 1.1.2.1 return Arrays.asList(new Rule[] {
126 kkz 1.1.2.1 new Rule("replaceArraySC") {
127 kkz 1.1.2.1 public boolean match(Stm stm) {
128 kkz 1.1.2.1 if (!contains(_KIND(stm), _CALL)) return false;
129 kkz 1.1.2.1 CALL call = (CALL) stm;
130 kkz 1.1.2.1 if (!contains(_KIND(call.getFunc()), _NAME)) return false;
131 kkz 1.1.2.1 return ((NAME) call.getFunc()).label.equals(LarrayHM);
132 kkz 1.1.2.1 }
133 kkz 1.1.2.1 public Stm apply(TreeFactory tf, Stm stm,
134 kkz 1.1.2.1 DerivationGenerator dg) {
135 kkz 1.1.2.2 //System.out.println(Print.print(stm));
136 kkz 1.1.2.1 Runtime runtime = tf.getFrame().getRuntime();
137 kkz 1.1.2.1 TreeBuilder tb = runtime.getTreeBuilder();
138 kkz 1.1.2.1 final NAME func = new NAME(tf, stm, cfunc);
139 kkz 1.1.2.1 if (dg != null) dg.putType(func, HClass.Void);
140 kkz 1.1.2.1 // extract arguments
141 kkz 1.1.2.1 ExpList explist = ((CALL) stm).getArgs();
142 kkz 1.1.2.1 // first argument
143 kkz 1.1.2.1 TEMP objectref = (TEMP) explist.head;
144 kkz 1.1.2.1 explist = explist.tail;
145 kkz 1.1.2.2 // second argument is the array index
146 kkz 1.1.2.2 // after constant propagation, this
147 kkz 1.1.2.2 // may be either a TEMP or a CONST
148 kkz 1.1.2.2 Exp index = explist.head;
149 kkz 1.1.2.1 // ignore last 2 arguments
150 kkz 1.1.2.1 explist = explist.tail.tail;
151 kkz 1.1.2.1 // no more arguments
152 cananian 1.3.2.1 assert explist.tail == null;
153 kkz 1.1.2.1 // get array type from derivation
154 cananian 1.3.2.1 assert dg != null;
155 kkz 1.1.2.1 HClass arrayType = dg.typeMap(objectref);
156 cananian 1.3.2.1 assert arrayType != null;
157 kkz 1.1.2.1 return new NATIVECALL
158 kkz 1.1.2.1 (tf, stm, null, func, new ExpList
159 kkz 1.1.2.1 (new BINOP
160 kkz 1.1.2.1 (tf, stm, Type.POINTER, Bop.ADD,
161 kkz 1.1.2.1 tb.arrayBase
162 kkz 1.1.2.1 (tf, stm, dg, new Translation.Ex
163 kkz 1.1.2.1 (objectref)).unEx(tf),
164 kkz 1.1.2.1 tb.arrayOffset
165 kkz 1.1.2.1 (tf, stm, dg, arrayType, new Translation.Ex
166 kkz 1.1.2.1 (index)).unEx(tf)),
167 kkz 1.1.2.1 null));
168 kkz 1.1.2.1 }
169 kkz 1.1.2.1 },
170 kkz 1.1.2.1 new Rule("replaceFieldSC") {
171 kkz 1.1.2.1 public boolean match(Stm stm) {
172 kkz 1.1.2.1 if (!contains(_KIND(stm), _CALL)) return false;
173 kkz 1.1.2.1 CALL call = (CALL) stm;
174 kkz 1.1.2.1 if (!contains(_KIND(call.getFunc()), _NAME)) return false;
175 kkz 1.1.2.1 return ((NAME) call.getFunc()).label.equals(LfieldHM);
176 kkz 1.1.2.1 }
177 kkz 1.1.2.1 public Stm apply(TreeFactory tf, Stm stm,
178 kkz 1.1.2.1 DerivationGenerator dg) {
179 kkz 1.1.2.1 Runtime runtime = tf.getFrame().getRuntime();
180 kkz 1.1.2.1 TreeBuilder tb = runtime.getTreeBuilder();
181 kkz 1.1.2.1 final NAME func =
182 kkz 1.1.2.1 new NAME(tf, stm,
183 kkz 1.1.2.1 new Label(runtime.getNameMap().c_function_name
184 kkz 1.1.2.1 ("generational_write_barrier")));
185 kkz 1.1.2.1 if (dg != null) dg.putType(func, HClass.Void);
186 kkz 1.1.2.1 // extract arguments
187 kkz 1.1.2.1 ExpList explist = ((CALL) stm).getArgs();
188 kkz 1.1.2.1 // first argument
189 kkz 1.1.2.1 TEMP objectref = (TEMP) explist.head;
190 kkz 1.1.2.1 explist = explist.tail;
191 kkz 1.1.2.1 // second argument
192 kkz 1.1.2.1 NAME name = (NAME) explist.head;
193 kkz 1.1.2.1 // ignore last 2 arguments
194 kkz 1.1.2.1 explist = explist.tail.tail;
195 kkz 1.1.2.1 // no more arguments
196 cananian 1.3.2.1 assert explist.tail == null;
197 kkz 1.1.2.1 // get HField from fieldMap
198 cananian 1.6 HField field = fieldMap.get(name.label);
199 cananian 1.3.2.1 assert field != null;
200 kkz 1.1.2.1 return new NATIVECALL
201 kkz 1.1.2.1 (tf, stm, null, func, new ExpList
202 kkz 1.1.2.1 (new BINOP
203 kkz 1.1.2.1 (tf, stm, Type.POINTER, Bop.ADD, tb.fieldBase
204 kkz 1.1.2.1 (tf, stm, dg, new Translation.Ex
205 kkz 1.1.2.1 (objectref)).unEx(tf), tb.fieldOffset
206 kkz 1.1.2.1 (tf, stm, dg, field).unEx(tf)),
207 kkz 1.1.2.1 null));
208 kkz 1.1.2.1 }
209 kkz 1.1.2.1 }
210 kkz 1.1.2.1 });
211 kkz 1.1.2.1 }
212 kkz 1.1.2.1 }
213 cananian 1.2