1 pnkfelix 1.1.2.1 // InstrGroup.java, created Fri Jan 5 11:25:20 2001 by pnkfelix
2 cananian 1.1.2.4 // Copyright (C) 2000 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.IR.Assem;
5 pnkfelix 1.1.2.1
6 pnkfelix 1.1.2.1 import harpoon.ClassFile.HCode;
7 cananian 1.3.2.2 import harpoon.ClassFile.HCodeEdge;
8 pnkfelix 1.1.2.1 import harpoon.ClassFile.HCodeElement;
9 pnkfelix 1.1.2.1 import harpoon.IR.Properties.CFGEdge;
10 pnkfelix 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
11 pnkfelix 1.1.2.1 import harpoon.IR.Properties.CFGraphable;
12 pnkfelix 1.1.2.1 import harpoon.IR.Properties.UseDefer;
13 pnkfelix 1.1.2.1 import harpoon.IR.Properties.UseDefable;
14 cananian 1.3.2.2 import harpoon.Temp.Temp;
15 cananian 1.6 import net.cscott.jutil.Default;
16 pnkfelix 1.1.2.1 import harpoon.Util.Util;
17 pnkfelix 1.1.2.1
18 cananian 1.5 import java.util.AbstractList;
19 cananian 1.3.2.2 import java.util.Arrays;
20 pnkfelix 1.1.2.1 import java.util.Collection;
21 pnkfelix 1.1.2.3 import java.util.Collections;
22 pnkfelix 1.1.2.1 import java.util.HashMap;
23 pnkfelix 1.1.2.1 import java.util.HashSet;
24 cananian 1.5 import java.util.List;
25 cananian 1.3.2.2 import java.util.Map;
26 pnkfelix 1.1.2.1 /**
27 pnkfelix 1.1.2.1 * <code>InstrGroup</code> collects a group of assembly instructions
28 pnkfelix 1.1.2.1 * together so that they can be viewed as a single atomic element of
29 pnkfelix 1.1.2.1 * the code. This allows for differing levels of abstraction as
30 pnkfelix 1.1.2.1 * required by various compiler passes. Each set of instructions
31 pnkfelix 1.1.2.1 * collected by an <code>InstrGroup</code> must collectively form a
32 pnkfelix 1.1.2.1 * single-entry single-exit region.
33 pnkfelix 1.1.2.8 *
34 cananian 1.1.2.4 * @author Felix S. Klock II <pnkfelix@mit.edu>
35 cananian 1.6 * @version $Id: InstrGroup.java,v 1.6 2004/02/08 01:55:08 cananian Exp $ */
36 pnkfelix 1.1.2.1 public class InstrGroup {
37 pnkfelix 1.1.2.1 Type type;
38 pnkfelix 1.1.2.1 Instr entry, exit;
39 pnkfelix 1.1.2.1 InstrGroup containedIn; // null ==> not contained in supergroup
40 pnkfelix 1.1.2.1
41 pnkfelix 1.1.2.1 /** Creates a <code>InstrGroup</code>. */
42 pnkfelix 1.1.2.1 public InstrGroup(Type type) {
43 pnkfelix 1.1.2.1 this.type = type;
44 pnkfelix 1.1.2.1 containedIn = null;
45 pnkfelix 1.1.2.1 }
46 pnkfelix 1.1.2.1
47 pnkfelix 1.1.2.1 /** Creates a <code>InstrGroup</code> contained in
48 pnkfelix 1.1.2.1 <code>contained</code>.
49 pnkfelix 1.1.2.1 */
50 pnkfelix 1.1.2.1 public InstrGroup(Type type, InstrGroup container) {
51 pnkfelix 1.1.2.1 this.type = type;
52 pnkfelix 1.1.2.1 containedIn = container;
53 pnkfelix 1.1.2.1 }
54 pnkfelix 1.1.2.1
55 pnkfelix 1.1.2.1 public String toString() {
56 pnkfelix 1.1.2.3 return "<group type:"+type.typeString+
57 pnkfelix 1.1.2.3 ",entry:"+((entry==null)?"null":""+entry.getID())+
58 pnkfelix 1.1.2.3 ",exit:"+((exit==null)?"null":""+exit.getID())+">";
59 pnkfelix 1.1.2.1 }
60 pnkfelix 1.1.2.1
61 pnkfelix 1.1.2.1 /** Returns true if this is contained in a super group, else
62 pnkfelix 1.1.2.1 false.
63 pnkfelix 1.1.2.1 */
64 pnkfelix 1.1.2.1 public boolean hasContainer() { return containedIn != null; }
65 pnkfelix 1.1.2.1
66 pnkfelix 1.1.2.1 /** Returns the <code>InstrGroup</code> containing
67 pnkfelix 1.1.2.1 <code>this</code>, or <code>null</code> if this is not
68 pnkfelix 1.1.2.1 contained in any super group.
69 pnkfelix 1.1.2.1 */
70 pnkfelix 1.1.2.1 public InstrGroup getContainer() { return containedIn; }
71 pnkfelix 1.1.2.1
72 pnkfelix 1.1.2.3 /** Returns true if this is (reflexively) contained in
73 pnkfelix 1.1.2.3 <code>group</code>. */
74 pnkfelix 1.1.2.3 public boolean subgroupOf(InstrGroup group) {
75 pnkfelix 1.1.2.3 return (group != null) &&
76 pnkfelix 1.1.2.3 (this == group ||
77 pnkfelix 1.1.2.3 this.containedIn == group ||
78 pnkfelix 1.1.2.3 (containedIn != null &&
79 pnkfelix 1.1.2.3 containedIn.subgroupOf( group )));
80 pnkfelix 1.1.2.3 }
81 pnkfelix 1.1.2.3
82 pnkfelix 1.1.2.1 /** Sets the entry point for a group of instructions. Should be
83 pnkfelix 1.1.2.1 called once (and only once), before setExit is called. */
84 pnkfelix 1.1.2.1 public void setEntry(Instr entry) {
85 cananian 1.3.2.1 assert this.entry == null;
86 pnkfelix 1.1.2.1 this.entry = entry;
87 pnkfelix 1.1.2.1 }
88 pnkfelix 1.1.2.1 /** Sets the exit point for this group of instructions. Should be
89 pnkfelix 1.1.2.1 called once (and only once). Note that
90 pnkfelix 1.1.2.1 for a given InstrGroup(fact, a), after setExit(b) has been
91 pnkfelix 1.1.2.1 called, it should be the case for the code associated with
92 pnkfelix 1.1.2.1 <code>fact</code>: <UL>
93 pnkfelix 1.1.2.1 <LI> a dominates b
94 pnkfelix 1.1.2.1 <LI> b postdominates a
95 pnkfelix 1.1.2.1 <LI> a and b are cycle-equivalent</UL>. */
96 pnkfelix 1.1.2.1 public void setExit(Instr exit) {
97 cananian 1.3.2.1 assert this.exit == null;
98 pnkfelix 1.1.2.1 this.exit = exit;
99 pnkfelix 1.1.2.1 }
100 pnkfelix 1.1.2.1
101 pnkfelix 1.1.2.1 /** <code>InstrGroup.GroupGrapher</code> turns an Instr -> Group map
102 pnkfelix 1.1.2.1 into a <code>CFGrapher</code>. The predecessor and successor
103 pnkfelix 1.1.2.1 relations in <code>InstrGroup.Grapher</code> use the groups to
104 pnkfelix 1.1.2.1 abstract away the control flow and layout dictated by the
105 pnkfelix 1.1.2.1 Instrs internally, returning the entry points of each group
106 pnkfelix 1.1.2.1 when needed. */
107 cananian 1.3.2.2 static class GroupGrapher extends CFGrapher<Instr> {
108 cananian 1.3.2.2 private Map<Instr,InstrGroup> i2g;
109 pnkfelix 1.1.2.1
110 cananian 1.3.2.2 GroupGrapher(Map<Instr,InstrGroup> instrToGroup) { // local to Assem package
111 pnkfelix 1.1.2.1 i2g = instrToGroup;
112 pnkfelix 1.1.2.1 }
113 pnkfelix 1.1.2.1
114 cananian 1.3.2.2 public Instr[] getLastElements(HCode<Instr> hcode) {
115 pnkfelix 1.1.2.6 // FSK: is this even necessary? It was w/o exit mapping,
116 pnkfelix 1.1.2.6 // but w/ exit mapping, I think that this loop is just an
117 pnkfelix 1.1.2.6 // identity transform. Should look into it later.
118 cananian 1.3.2.2 Instr[] hces = hcode.getLeafElements();
119 pnkfelix 1.1.2.1 if (hces != null) { // null allowed? has been so far...
120 pnkfelix 1.1.2.1 for(int i=0; i<hces.length; i++) {
121 cananian 1.3.2.2 InstrGroup ig = i2g.get(hces[i]);
122 pnkfelix 1.1.2.1 if (ig != null)
123 pnkfelix 1.1.2.5 hces[i] = ig.exit;
124 pnkfelix 1.1.2.1 }
125 pnkfelix 1.1.2.1 }
126 pnkfelix 1.1.2.1 return hces;
127 pnkfelix 1.1.2.1 }
128 cananian 1.3.2.2 public Instr getFirstElement(HCode<Instr> hcode) {
129 pnkfelix 1.1.2.1 return hcode.getRootElement();
130 pnkfelix 1.1.2.1 }
131 pnkfelix 1.1.2.1
132 cananian 1.5 public List<HCodeEdge<Instr>> predC(Instr i) {
133 cananian 1.5 if (!i2g.containsKey(i)) {
134 cananian 1.6 return Collections.<HCodeEdge<Instr>>unmodifiableList
135 cananian 1.6 (i.predC());
136 pnkfelix 1.1.2.5 } else {
137 cananian 1.3.2.2 InstrGroup ig = i2g.get(i);
138 pnkfelix 1.1.2.5 if (i == ig.exit) {
139 cananian 1.6 return Collections.<HCodeEdge<Instr>>singletonList
140 cananian 1.6 (new InstrEdge(ig.entry, ig.exit));
141 pnkfelix 1.1.2.5 } else {
142 cananian 1.3.2.1 assert i == ig.entry;
143 cananian 1.6 return Collections.<HCodeEdge<Instr>>unmodifiableList
144 cananian 1.6 (i.predC());
145 pnkfelix 1.1.2.1 }
146 pnkfelix 1.1.2.1 }
147 pnkfelix 1.1.2.1 }
148 pnkfelix 1.1.2.1
149 cananian 1.5 public List<HCodeEdge<Instr>> succC(Instr i) {
150 pnkfelix 1.1.2.1 if (!i2g.containsKey(i)) {
151 cananian 1.6 return Collections.<HCodeEdge<Instr>>unmodifiableList
152 cananian 1.6 (i.succC());
153 pnkfelix 1.1.2.1 } else {
154 cananian 1.3.2.2 InstrGroup ig = i2g.get(i);
155 pnkfelix 1.1.2.5 if (i == ig.entry) {
156 cananian 1.6 return Collections.<HCodeEdge<Instr>>singletonList
157 cananian 1.6 (new InstrEdge(ig.entry, ig.exit));
158 pnkfelix 1.1.2.5 } else {
159 cananian 1.3.2.1 assert i == ig.exit;
160 cananian 1.6 return Collections.<HCodeEdge<Instr>>unmodifiableList
161 cananian 1.6 (i.succC());
162 pnkfelix 1.1.2.1 }
163 pnkfelix 1.1.2.1 }
164 pnkfelix 1.1.2.1 }
165 pnkfelix 1.1.2.1 }
166 pnkfelix 1.1.2.1 /** <code>InstrGroup.GroupUseDefer</code> turns an Instr -> Group
167 pnkfelix 1.1.2.1 map into a <code>UseDefer</code>. It does this by performing
168 pnkfelix 1.1.2.1 a reverse data-flow analysis, accumulating definitions, along
169 pnkfelix 1.1.2.1 with uses that have definitions originating <i>outside</i> of
170 pnkfelix 1.1.2.1 the group.
171 pnkfelix 1.1.2.8 <p>
172 pnkfelix 1.1.2.8 The produced <code>UseDefer</code> then maps all of the temps
173 pnkfelix 1.1.2.8 used by the set of instrs: (group \ {entry}) as coming from
174 pnkfelix 1.1.2.8 the exit of the group, and all of the temps defined by the
175 pnkfelix 1.1.2.8 entire group as coming from the entry of the group. This is a
176 pnkfelix 1.1.2.8 conservative view; it ensures that the resulting register
177 pnkfelix 1.1.2.8 assignments will be distinct, even when they sometimes did not
178 pnkfelix 1.1.2.8 need to be.
179 pnkfelix 1.1.2.1 */
180 cananian 1.3.2.2 static class GroupUseDefer extends UseDefer<Instr> {
181 cananian 1.3.2.2 private Map<Instr,InstrGroup> i2g;
182 pnkfelix 1.1.2.1 private Type t;
183 cananian 1.3.2.2 GroupUseDefer(Map<Instr,InstrGroup> instrToGroup, Type t) { // local to Assem package
184 pnkfelix 1.1.2.1 i2g = instrToGroup;
185 pnkfelix 1.1.2.1 this.t = t;
186 pnkfelix 1.1.2.1 }
187 pnkfelix 1.1.2.3
188 pnkfelix 1.1.2.3 // **NOTE** defC and useC are ASYMMETRIC.
189 cananian 1.3.2.2 public Collection<Temp> useC(Instr i) {
190 pnkfelix 1.1.2.1 if (!i2g.containsKey(i)) {
191 cananian 1.3.2.1 assert !i.partOf(t) : ("instr:"+i+" grp type:"+t);
192 pnkfelix 1.1.2.1 return i.useC();
193 pnkfelix 1.1.2.1 } else {
194 cananian 1.3.2.2 InstrGroup ig = i2g.get(i);
195 pnkfelix 1.1.2.3 if(i == ig.entry) {
196 pnkfelix 1.1.2.3 return i.useC();
197 pnkfelix 1.1.2.3 }
198 cananian 1.3.2.1 assert i == ig.exit;
199 pnkfelix 1.1.2.3 // else work backwards, gathering up uses but killing
200 pnkfelix 1.1.2.3 // defined uses...
201 pnkfelix 1.1.2.1 Instr curr = ig.exit;
202 cananian 1.3.2.2 Collection<Temp> set = new HashSet<Temp>();
203 pnkfelix 1.1.2.1 do {
204 cananian 1.3.2.1 assert curr.getGroups().contains(ig);
205 pnkfelix 1.1.2.1 set.addAll(curr.useC());
206 cananian 1.3.2.1 assert curr.predC().size() == 1;
207 pnkfelix 1.1.2.1 curr = (Instr) curr.pred()[0].from();
208 pnkfelix 1.1.2.3 set.removeAll(curr.defC()); // order here is key
209 pnkfelix 1.1.2.1 } while(curr != ig.entry);
210 pnkfelix 1.1.2.1
211 pnkfelix 1.1.2.1 return set;
212 pnkfelix 1.1.2.1 }
213 pnkfelix 1.1.2.1 }
214 cananian 1.3.2.2 public Collection<Temp> defC(Instr i) {
215 pnkfelix 1.1.2.1 if (!i2g.containsKey(i)) {
216 cananian 1.3.2.1 assert !i.partOf(t);
217 pnkfelix 1.1.2.1 return i.defC();
218 pnkfelix 1.1.2.1 } else {
219 cananian 1.3.2.2 InstrGroup ig = i2g.get(i);
220 pnkfelix 1.1.2.3 if (i == ig.exit) {
221 pnkfelix 1.1.2.3 return Collections.EMPTY_SET;
222 pnkfelix 1.1.2.3 }
223 pnkfelix 1.1.2.3 // else gather up all defs and pass them out
224 cananian 1.3.2.1 assert i == ig.entry;
225 pnkfelix 1.1.2.1 Instr curr = ig.exit;
226 pnkfelix 1.1.2.7
227 pnkfelix 1.1.2.7 // start with defs in last instr (shifting them to the
228 pnkfelix 1.1.2.7 // start of the group)
229 cananian 1.3.2.2 Collection<Temp> set = new HashSet<Temp>( curr.defC() );
230 pnkfelix 1.1.2.1
231 pnkfelix 1.1.2.1 do {
232 cananian 1.3.2.1 assert curr.getGroups().contains(ig);
233 cananian 1.3.2.1 assert curr.predC().size() == 1;
234 pnkfelix 1.1.2.1 curr = (Instr) curr.pred()[0].from();
235 pnkfelix 1.1.2.3 set.addAll(curr.defC());
236 pnkfelix 1.1.2.1 } while(curr != ig.entry);
237 pnkfelix 1.1.2.1
238 pnkfelix 1.1.2.1 return set;
239 pnkfelix 1.1.2.1 }
240 pnkfelix 1.1.2.1 }
241 pnkfelix 1.1.2.1 }
242 pnkfelix 1.1.2.1
243 pnkfelix 1.1.2.8 /** <code>InstrGroup.Type</code> is associated with a collection
244 pnkfelix 1.1.2.8 of <code>InstrGroup</code>s for a given
245 pnkfelix 1.1.2.8 <code>Assem.Code</code>. Each <code>InstrGroup.Type</code> is
246 pnkfelix 1.1.2.8 meant to be used as a way to extract abstract <i>views</i> of
247 pnkfelix 1.1.2.8 the <code>Assem.Code</code>.
248 pnkfelix 1.1.2.8
249 pnkfelix 1.1.2.8 */
250 pnkfelix 1.1.2.1 public static class Type {
251 pnkfelix 1.1.2.1 private String typeString;
252 pnkfelix 1.1.2.3 private String details;
253 pnkfelix 1.1.2.3 private Type(String groupType, String details) {
254 pnkfelix 1.1.2.1 typeString = groupType;
255 pnkfelix 1.1.2.3 this.details = details;
256 pnkfelix 1.1.2.1 }
257 pnkfelix 1.1.2.1
258 pnkfelix 1.1.2.1 /** Creates an <code>InstrGroup</code> of the type for
259 pnkfelix 1.1.2.1 <code>this</code> representing <code>rep</code>. Note
260 pnkfelix 1.1.2.1 that <code>rep</code> should be the entry point for the
261 pnkfelix 1.1.2.1 group of instructions that will be collected by the
262 pnkfelix 1.1.2.1 returned <code>InstrGroup</code>. */
263 pnkfelix 1.1.2.1 public InstrGroup makeGroup() {
264 pnkfelix 1.1.2.1 return new InstrGroup(this);
265 pnkfelix 1.1.2.1 }
266 pnkfelix 1.1.2.1 /** Creates an <code>InstrGroup</code>, contained in
267 pnkfelix 1.1.2.1 <code>container</code> of the type for <code>this</code>
268 pnkfelix 1.1.2.1 representing <code>rep</code>. Note that <code>rep</code>
269 pnkfelix 1.1.2.1 should be the entry point for the group of instructions
270 pnkfelix 1.1.2.1 that will be collected by the returned
271 pnkfelix 1.1.2.1 <code>InstrGroup</code>. If container is null, then the
272 pnkfelix 1.1.2.1 generated InstrGroup will have no containing group. */
273 pnkfelix 1.1.2.1 public InstrGroup makeGroup(InstrGroup container) {
274 pnkfelix 1.1.2.1 return new InstrGroup(this, container);
275 pnkfelix 1.1.2.1 }
276 pnkfelix 1.1.2.1
277 pnkfelix 1.1.2.1 public String toString() {
278 pnkfelix 1.1.2.1 return "InstrGroup.Type:"+typeString;
279 pnkfelix 1.1.2.1 }
280 pnkfelix 1.1.2.1 }
281 pnkfelix 1.1.2.1
282 pnkfelix 1.1.2.1 /** groups code such as local labels (1f/1:).
283 pnkfelix 1.1.2.1 */
284 pnkfelix 1.1.2.3 public static Type NO_REORDER=new Type("ord","order sensitive dependencies");
285 pnkfelix 1.1.2.1
286 pnkfelix 1.1.2.1 /** groups code such as double word moves where we do not want to
287 pnkfelix 1.1.2.1 allow one half of the location to be assigned to hold the 2nd
288 pnkfelix 1.1.2.1 half.
289 pnkfelix 1.1.2.1 */
290 pnkfelix 1.1.2.3 public static Type AGGREGATE=new Type("agg","aggregate instructions");
291 pnkfelix 1.1.2.1
292 pnkfelix 1.1.2.1 /** groups code where we cannot insert spill code (such as
293 pnkfelix 1.1.2.1 aggregates where spill code would destroy effect of virtual
294 pnkfelix 1.1.2.1 DUMMY instructions added in). Note that it is legal to insert
295 pnkfelix 1.1.2.1 spill code BEFORE the group, just not between instructions
296 pnkfelix 1.1.2.1 contained within the group.
297 pnkfelix 1.1.2.1 */
298 pnkfelix 1.1.2.3 public static Type NO_SPILL=new Type("!sp","spill sensitive dependencies");
299 pnkfelix 1.1.2.1
300 pnkfelix 1.1.2.1 /** groups code with special delay slot instructions... (usable?)
301 pnkfelix 1.1.2.1 */
302 pnkfelix 1.1.2.3 public static Type DELAY_SLOT=new Type("del","delay slot");
303 pnkfelix 1.1.2.1
304 pnkfelix 1.1.2.1 }
305 pnkfelix 1.1.2.1
306 cananian 1.2