1 cananian 1.1.2.1 // FixUnaligned.java, created Thu Mar 14 15:17:07 2002 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.Backend.RuntimeTiny;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.Tree.AlignmentAnalysis;
7 cananian 1.1.2.1 import harpoon.Analysis.Tree.Canonicalize;
8 cananian 1.1.2.1 import harpoon.Analysis.Tree.Simplification;
9 cananian 1.1.2.1 import harpoon.Backend.Maps.FieldMap;
10 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
11 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
12 cananian 1.1.2.1 import harpoon.ClassFile.HCodeAndMaps;
13 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
14 cananian 1.1.2.1 import harpoon.ClassFile.HCodeFactory;
15 cananian 1.1.2.1 import harpoon.ClassFile.HMethod;
16 cananian 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
17 cananian 1.1.2.1 import harpoon.IR.Tree.BINOP;
18 cananian 1.1.2.1 import harpoon.IR.Tree.Bop;
19 cananian 1.1.2.1 import harpoon.IR.Tree.CanonicalTreeCode;
20 cananian 1.1.2.1 import harpoon.IR.Tree.Code;
21 cananian 1.1.2.1 import harpoon.IR.Tree.CONST;
22 cananian 1.1.2.1 import harpoon.IR.Tree.DerivationGenerator;
23 cananian 1.1.2.1 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.MEM;
26 cananian 1.1.2.1 import harpoon.IR.Tree.MOVE;
27 cananian 1.1.2.1 import harpoon.IR.Tree.Stm;
28 cananian 1.1.2.1 import harpoon.IR.Tree.TEMP;
29 cananian 1.1.2.1 import harpoon.IR.Tree.Tree;
30 cananian 1.1.2.1 import harpoon.IR.Tree.TreeCode;
31 cananian 1.1.2.1 import harpoon.IR.Tree.TreeFactory;
32 cananian 1.1.2.1 import harpoon.IR.Tree.TreeKind;
33 cananian 1.1.2.1 import harpoon.IR.Tree.Type;
34 cananian 1.1.2.1 import harpoon.IR.Tree.UNOP;
35 cananian 1.1.2.1 import harpoon.IR.Tree.Uop;
36 cananian 1.1.2.1 import harpoon.Temp.Temp;
37 cananian 1.1.2.1 import harpoon.Util.Util;
38 cananian 1.1.2.1
39 cananian 1.1.2.1 import java.util.Arrays;
40 cananian 1.1.2.1 import java.util.HashMap;
41 cananian 1.1.2.1 import java.util.HashSet;
42 cananian 1.1.2.1 import java.util.Iterator;
43 cananian 1.1.2.1 import java.util.List;
44 cananian 1.1.2.1 import java.util.Map;
45 cananian 1.1.2.1 import java.util.Set;
46 cananian 1.1.2.1 /**
47 cananian 1.1.2.1 * <code>FixUnaligned</code> is a pass on <code>Tree</code> form
48 cananian 1.1.2.1 * which used alignment analysis to discover unaligned references,
49 cananian 1.1.2.1 * and then "corrects" them (using only aligned memory accesses)
50 cananian 1.1.2.1 * in the proper way for your architecture (specified via parameters
51 cananian 1.1.2.1 * to the code factory).
52 cananian 1.1.2.1 *
53 cananian 1.1.2.1 * <p><b>XXX BROKEN AND INCOMPLETE XXX</b></p>
54 cananian 1.1.2.1 *
55 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
56 cananian 1.2 * @version $Id: FixUnaligned.java,v 1.2 2002/04/10 03:03:43 cananian Exp $
57 cananian 1.1.2.1 */
58 cananian 1.1.2.1 class FixUnaligned extends Simplification {
59 cananian 1.1.2.1 // hide constructor
60 cananian 1.1.2.1 private FixUnaligned() { }
61 cananian 1.1.2.1
62 cananian 1.1.2.1 /** Code factory for applying FixUnaligned to a
63 cananian 1.1.2.1 * canonical tree. Clones the tree before doing
64 cananian 1.1.2.1 * transformation in-place. Result may not be canonicalized. */
65 cananian 1.1.2.1 public static HCodeFactory codeFactory(final HCodeFactory parent) {
66 cananian 1.1.2.1 assert parent.getCodeName().equals(CanonicalTreeCode.codename);
67 cananian 1.1.2.1 return new HCodeFactory() {
68 cananian 1.1.2.1 public HCode convert(HMethod m) {
69 cananian 1.1.2.1 HCode hc = parent.convert(m);
70 cananian 1.1.2.1 if (hc!=null) {
71 cananian 1.1.2.1 harpoon.IR.Tree.Code code = (harpoon.IR.Tree.Code) hc;
72 cananian 1.1.2.1 // clone code...
73 cananian 1.1.2.1 code = (harpoon.IR.Tree.Code) code.clone(m).hcode();
74 cananian 1.1.2.1 DerivationGenerator dg = null;
75 cananian 1.1.2.1 try {
76 cananian 1.1.2.1 dg = (DerivationGenerator) code.getTreeDerivation();
77 cananian 1.1.2.1 } catch (ClassCastException ex) { /* i guess not */ }
78 cananian 1.1.2.1 // ...do analysis and modify cloned code in-place.
79 cananian 1.1.2.1 simplify((Stm)code.getRootElement(), dg, HCE_RULES(code));
80 cananian 1.1.2.1 hc = code;
81 cananian 1.1.2.1 }
82 cananian 1.1.2.1 return hc;
83 cananian 1.1.2.1 }
84 cananian 1.1.2.1 public String getCodeName() { return TreeCode.codename; }
85 cananian 1.1.2.1 public void clear(HMethod m) { parent.clear(m); }
86 cananian 1.1.2.1 };
87 cananian 1.1.2.1 }
88 cananian 1.1.2.1
89 cananian 1.1.2.1 private static Stm findRoot(Exp e) {
90 cananian 1.1.2.1 Tree t = e.getParent();
91 cananian 1.1.2.1 if (t instanceof Exp)
92 cananian 1.1.2.1 return findRoot((Exp)t);
93 cananian 1.1.2.1 else return (Stm) t;
94 cananian 1.1.2.1 }
95 cananian 1.1.2.1 private static int sizeOf(MEM mem) {
96 cananian 1.1.2.1 if (mem.isSmall()) return (mem.bitwidth()+7)/8;
97 cananian 1.1.2.1 return Type.isDoubleWord(mem.getFactory(), mem.type()) ? 8 : 4;
98 cananian 1.1.2.1 }
99 cananian 1.1.2.1 // XXX DERIVATIONS ARE NOT CORRECT.
100 cananian 1.1.2.1 private static Exp assemble(TreeFactory tf, HCodeElement source, Temp base,
101 cananian 1.1.2.1 int offset, int size,
102 cananian 1.1.2.1 //Derivation deriv, DerivationGenerator dg,
103 cananian 1.1.2.1 int totalsize, boolean bigEndian,
104 cananian 1.1.2.1 boolean signed) {
105 cananian 1.1.2.1 int ty = (totalsize > 4) ? Type.LONG : Type.INT;
106 cananian 1.1.2.1 // big-endian or little-endian?
107 cananian 1.1.2.1 // first, pull off the largest chunk you can from the front.
108 cananian 1.1.2.1 int lowsize=1;
109 cananian 1.1.2.1 boolean signThis = bigEndian ? (offset==0):(offset+lowsize==totalsize);
110 cananian 1.1.2.1 Exp low = new MEM(tf, source, 8, signThis ? signed : false,
111 cananian 1.1.2.1 new BINOP
112 cananian 1.1.2.1 (tf, source, Type.POINTER, Bop.ADD,
113 cananian 1.1.2.1 new TEMP(tf, source, Type.POINTER, base),
114 cananian 1.1.2.1 new CONST(tf, source, offset)));
115 cananian 1.1.2.1 int bitshift=bigEndian ? ((totalsize-(offset+lowsize))*8) : (offset*8);
116 cananian 1.1.2.1
117 cananian 1.1.2.1
118 cananian 1.1.2.1 if (ty == Type.LONG)
119 cananian 1.1.2.1 low = new UNOP(tf, source, Type.INT, Uop._2L, low);
120 cananian 1.1.2.1 if (bitshift>0)
121 cananian 1.1.2.1 low = new BINOP(tf, source, ty, Bop.SHL, low,
122 cananian 1.1.2.1 new CONST(tf, source, bitshift));
123 cananian 1.1.2.1 if (size-lowsize > 0) {
124 cananian 1.1.2.1 // recursively fetch the remainder.
125 cananian 1.1.2.1 Exp high = assemble(tf, source, base, offset+lowsize, size-lowsize,
126 cananian 1.1.2.1 totalsize, bigEndian, signed);
127 cananian 1.1.2.1 // assemble the pieces.
128 cananian 1.1.2.1 low = new BINOP(tf, source, ty, Bop.OR, low, high);
129 cananian 1.1.2.1 }
130 cananian 1.1.2.1 // done!
131 cananian 1.1.2.1 return low;
132 cananian 1.1.2.1 }
133 cananian 1.1.2.1 private static Exp disassemble(MEM mem, TreeFactory tf,
134 cananian 1.1.2.1 DerivationGenerator dg) {
135 cananian 1.1.2.1 HCodeElement source = mem;
136 cananian 1.1.2.1 Temp t = new Temp(tf.tempFactory(), "fixun");
137 cananian 1.1.2.1 assert mem.getExp().type() == Type.POINTER;
138 cananian 1.1.2.1 return new ESEQ(tf, source,
139 cananian 1.1.2.1 new MOVE
140 cananian 1.1.2.1 (tf, source,
141 cananian 1.1.2.1 new TEMP(tf, source, Type.POINTER, t),
142 cananian 1.1.2.1 mem.getExp()),
143 cananian 1.1.2.1 assemble(tf, source, t, 0, sizeOf(mem), sizeOf(mem),
144 cananian 1.1.2.1 Boolean.getBoolean
145 cananian 1.1.2.1 ("harpoon.runtimetiny.big-endian"),
146 cananian 1.1.2.1 mem.isSmall() ? mem.signed() : true));
147 cananian 1.1.2.1 }
148 cananian 1.1.2.1
149 cananian 1.1.2.1 public static List<Rule> HCE_RULES(final harpoon.IR.Tree.Code code) {
150 cananian 1.1.2.1 // make an AlignmentAnalysis
151 cananian 1.1.2.1 final AlignmentAnalysis aa =
152 cananian 1.1.2.1 new AlignmentAnalysis(code, code.getGrapher(), code.getUseDefer(),
153 cananian 1.1.2.1 code.getTreeDerivation());
154 cananian 1.1.2.1 // now make rules.
155 cananian 1.1.2.1 return Arrays.asList(new Rule[] {
156 cananian 1.1.2.1 // MEM(x) -> byte-wise MEM *reads only*
157 cananian 1.1.2.1 new Rule("breakupRead") {
158 cananian 1.1.2.1 public boolean match(Exp e) {
159 cananian 1.1.2.1 // this must be a MEM.
160 cananian 1.1.2.1 if (e.kind() != TreeKind.MEM) return false;
161 cananian 1.1.2.1 // make sure this is a read.
162 cananian 1.1.2.1 if (e.getParent().kind() == TreeKind.MOVE &&
163 cananian 1.1.2.1 ((MOVE)e.getParent()).getDst() == e) return false;
164 cananian 1.1.2.1 // some other constraints.
165 cananian 1.1.2.1 if (Type.isFloatingPoint(e.type())) return false;
166 cananian 1.1.2.1 AlignmentAnalysis.Value v = aa.valueOf(((MEM)e).getExp(),
167 cananian 1.1.2.1 findRoot(e));
168 cananian 1.1.2.1 if (!v.isBaseKnown()) return false; //not well-typed.
169 cananian 1.1.2.1 // XXX here we would theoretically look at the offset
170 cananian 1.1.2.1 // and figure out if disassembly is necessary.
171 cananian 1.1.2.1 // but we're just going to assume that it is.
172 cananian 1.1.2.1 return true;
173 cananian 1.1.2.1 }
174 cananian 1.1.2.1 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg)
175 cananian 1.1.2.1 {
176 cananian 1.1.2.1 return disassemble((MEM)e, tf, dg);
177 cananian 1.1.2.1 }
178 cananian 1.1.2.1 },
179 cananian 1.1.2.1 new Rule("breakupWrite") {
180 cananian 1.1.2.1 public boolean match(Exp e) {
181 cananian 1.1.2.1 // XXX
182 cananian 1.1.2.1 return false;
183 cananian 1.1.2.1 }
184 cananian 1.1.2.1 public Exp apply(TreeFactory tf, Exp e, DerivationGenerator dg)
185 cananian 1.1.2.1 {
186 cananian 1.1.2.1 assert false;
187 cananian 1.1.2.1 return e;
188 cananian 1.1.2.1 }
189 cananian 1.1.2.1 },
190 cananian 1.1.2.1 });
191 cananian 1.1.2.1 }
192 cananian 1.2 }