1 cananian 1.1.2.1 // PackedClassFieldMap.java, created Wed Jul 11 20:26:56 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.Backend.RuntimeTiny;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Backend.Maps.FieldMap;
7 cananian 1.1.2.1 import harpoon.ClassFile.HClass;
8 cananian 1.1.2.1 import harpoon.ClassFile.HField;
9 cananian 1.1.2.1 import harpoon.Util.Util;
10 cananian 1.1.2.1
11 cananian 1.1.2.1 import java.util.ArrayList;
12 cananian 1.1.2.1 import java.util.Arrays;
13 cananian 1.1.2.1 import java.util.Collections;
14 cananian 1.1.2.1 import java.util.Comparator;
15 cananian 1.1.2.1 import java.util.HashMap;
16 cananian 1.1.2.1 import java.util.Iterator;
17 cananian 1.1.2.1 import java.util.LinkedList;
18 cananian 1.1.2.1 import java.util.List;
19 cananian 1.1.2.1 import java.util.ListIterator;
20 cananian 1.1.2.1 import java.util.Map;
21 cananian 1.1.2.1 /**
22 cananian 1.1.2.1 * <code>PackedClassFieldMap</code> is a <code>FieldMap</code> for
23 cananian 1.1.2.1 * non-static fields of a class which attempts to maximally fill holes
24 cananian 1.1.2.1 * in the data structure (even if this means commingling a subclass'
25 cananian 1.1.2.1 * fields with those of its superclass) in order to minimize the
26 cananian 1.1.2.1 * space required by objects.
27 cananian 1.1.2.1 *
28 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
29 cananian 1.2 * @version $Id: TinyPackedClassFieldMap.java,v 1.2 2002/04/10 03:03:43 cananian Exp $
30 cananian 1.1.2.1 */
31 cananian 1.1.2.1 public abstract class TinyPackedClassFieldMap extends FieldMap {
32 cananian 1.1.2.1 final Runtime runtime;
33 cananian 1.1.2.1 /** Creates a <code>PackedClassFieldMap</code>. */
34 cananian 1.1.2.1 public TinyPackedClassFieldMap(Runtime runtime) {
35 cananian 1.1.2.1 this.runtime = runtime;
36 cananian 1.1.2.1 }
37 cananian 1.1.2.1
38 cananian 1.1.2.1 /** Override this function to indicate a *preferred* but not *mandatory*
39 cananian 1.1.2.1 * alignment for the given field. We will "try hard" to honor this
40 cananian 1.1.2.1 * alignment, but not if it would mean increasing the object size. */
41 cananian 1.1.2.1 public int fieldPreferredAlignment(HField hf){ return fieldAlignment(hf); }
42 cananian 1.1.2.1
43 cananian 1.1.2.1 /** Return an offset to the given field. */
44 cananian 1.1.2.1 public int fieldOffset(HField hf) {
45 cananian 1.1.2.1 assert !hf.isStatic();
46 cananian 1.1.2.1 if (!fieldcache.containsKey(hf)) do_one(hf.getDeclaringClass());
47 cananian 1.1.2.1 assert fieldcache.containsKey(hf);
48 cananian 1.1.2.1 return fieldcache.get(hf).intValue();
49 cananian 1.1.2.1 }
50 cananian 1.1.2.1 /** Return an unmodifiable List over all appropriate fields in the given
51 cananian 1.1.2.1 * class, in order from smallest to largest offset. */
52 cananian 1.1.2.1 public List<HField> fieldList(HClass hc) {
53 cananian 1.1.2.1 // get list of all fields in this class and its parents.
54 cananian 1.1.2.1 List<HField> l = new ArrayList<HField>();
55 cananian 1.1.2.1 for (HClass p = hc; p!=null; p=p.getSuperclass())
56 cananian 1.1.2.1 l.addAll(Arrays.asList(p.getDeclaredFields()));
57 cananian 1.1.2.1 // weed out static fields
58 cananian 1.1.2.1 for (Iterator<HField> it=l.iterator(); it.hasNext(); )
59 cananian 1.1.2.1 if (it.next().isStatic())
60 cananian 1.1.2.1 it.remove();
61 cananian 1.1.2.1 // now sort by fieldOffset.
62 cananian 1.1.2.1 Collections.sort(l, new Comparator<HField>() {
63 cananian 1.1.2.1 public int compare(HField hf1, HField hf2) {
64 cananian 1.1.2.1 return fieldOffset(hf1) - fieldOffset(hf2);
65 cananian 1.1.2.1 }
66 cananian 1.1.2.1 });
67 cananian 1.1.2.1 // quick verification of well-formedness
68 cananian 1.1.2.1 // (offsets must be strictly increasing)
69 cananian 1.1.2.1 int last=-100;
70 cananian 1.1.2.1 for (Iterator<HField> it=l.iterator(); it.hasNext(); ) {
71 cananian 1.1.2.1 int off=fieldOffset(it.next());
72 cananian 1.1.2.1 assert last<off : "Ill-formed field list";
73 cananian 1.1.2.1 last = off;
74 cananian 1.1.2.1 }
75 cananian 1.1.2.1 // done!
76 cananian 1.1.2.1 return l;
77 cananian 1.1.2.1 }
78 cananian 1.1.2.1
79 cananian 1.1.2.1 /** this method assigns "good" offsets to all the fields in class hc,
80 cananian 1.1.2.1 * using the assignments in hc's superclass and the list of free space
81 cananian 1.1.2.1 * in the superclass as starting points. */
82 cananian 1.1.2.1 private void do_one(HClass hc) {
83 cananian 1.1.2.1 assert hc!=null;
84 cananian 1.1.2.1 // get the 'free space' structure of the parent.
85 cananian 1.1.2.1 List<Interval> free = new LinkedList<Interval>
86 cananian 1.1.2.1 (Arrays.asList(freespace(hc.getSuperclass())));
87 cananian 1.1.2.1 // get all the fields of this class that we have to allocate.
88 cananian 1.1.2.1 List<HField> l =
89 cananian 1.1.2.1 new ArrayList<HField>(Arrays.asList(hc.getDeclaredFields()));
90 cananian 1.1.2.1 // weed out static fields
91 cananian 1.1.2.1 for (Iterator<HField> it=l.iterator(); it.hasNext(); )
92 cananian 1.1.2.1 if (it.next().isStatic())
93 cananian 1.1.2.1 it.remove();
94 cananian 1.1.2.1 // we're going to allocate fields from largest to smallest,
95 cananian 1.1.2.1 // so sort them first. (primarily sort by size, then by alignment)
96 cananian 1.1.2.1 Collections.sort(l, new Comparator<HField>() {
97 cananian 1.1.2.1 public int compare(HField hf1, HField hf2) {
98 cananian 1.1.2.1 // note reversed comparison here so that largest end up first.
99 cananian 1.1.2.1 int r = fieldSize(hf2) - fieldSize(hf1);
100 cananian 1.1.2.1 if (r==0) r = fieldPreferredAlignment(hf2)
101 cananian 1.1.2.1 - fieldPreferredAlignment(hf1);
102 cananian 1.1.2.1 if (r==0) r = fieldAlignment(hf2) - fieldAlignment(hf1);
103 cananian 1.1.2.1 return r;
104 cananian 1.1.2.1 }
105 cananian 1.1.2.1 });
106 cananian 1.1.2.1 // now allocate them one by one (largest to smallest, like we said)
107 cananian 1.1.2.1 // the alloc_one method has the side effect of adding an entry to
108 cananian 1.1.2.1 // the fieldcache.
109 cananian 1.1.2.1 nextfield:
110 cananian 1.1.2.1 while (!l.isEmpty()) {
111 cananian 1.1.2.1 // allocate largest *must-align* field
112 cananian 1.1.2.1 for (Iterator<HField> it=l.iterator(); it.hasNext(); )
113 cananian 1.1.2.1 if (alloc_one(it.next(), free, true, false)) {
114 cananian 1.1.2.1 it.remove();
115 cananian 1.1.2.1 continue nextfield;
116 cananian 1.1.2.1 }
117 cananian 1.1.2.1 // allocate largest *preferably-aligned* field
118 cananian 1.1.2.1 for (Iterator<HField> it=l.iterator(); it.hasNext(); )
119 cananian 1.1.2.1 if (alloc_one(it.next(), free, false, true)) {
120 cananian 1.1.2.1 it.remove();
121 cananian 1.1.2.1 continue nextfield;
122 cananian 1.1.2.1 }
123 cananian 1.1.2.1 // allocate smalled unaligned field.
124 cananian 1.1.2.1 if (alloc_one(l.remove(l.size()-1), free, false, false))
125 cananian 1.1.2.1 continue nextfield;
126 cananian 1.1.2.1 // should never get here!
127 cananian 1.1.2.1 assert false : "should always be able to alloc smallest field";
128 cananian 1.1.2.1 }
129 cananian 1.1.2.1 // cache away the free list for the next guy (subclasses of this)
130 cananian 1.1.2.1 freecache.put(hc, free.toArray(new Interval[free.size()]));
131 cananian 1.1.2.1 // done!
132 cananian 1.1.2.1 }
133 cananian 1.1.2.1 /** this method tries to allocate the field hf as low in the object
134 cananian 1.1.2.1 * as possible, using the current list of free spaces in the class. */
135 cananian 1.1.2.1 private boolean alloc_one(HField hf, List<Interval> free,
136 cananian 1.1.2.1 boolean mustAlign, boolean prefAlign) {
137 cananian 1.1.2.1 int size = fieldSize(hf), align = fieldAlignment(hf);
138 cananian 1.1.2.1 int palign = fieldPreferredAlignment(hf);
139 cananian 1.1.2.1 // 'mustAlign' fields have align > 1
140 cananian 1.1.2.1 if (align<=1 && mustAlign) return false;
141 cananian 1.1.2.1 // go through free list, looking for a place to put this.
142 cananian 1.1.2.1 // first, try to put it at its preferred alignment, but not at the end
143 cananian 1.1.2.1 // as a last resort, put it anywhere, ignoring the preferred alignment.
144 cananian 1.1.2.1 for (int pass=0; pass<2; pass++) {
145 cananian 1.1.2.1 for (ListIterator<Interval> li = free.listIterator(); li.hasNext();){
146 cananian 1.1.2.1 Interval i = li.next();
147 cananian 1.1.2.1 assert i.low < i.high; // validity of interval.
148 cananian 1.1.2.1 // use preferred alignment for first pass, but don't allow alloc
149 cananian 1.1.2.1 // at end (in 'infinite interval')
150 cananian 1.1.2.1 int malign = (pass==0) ? palign : align;
151 cananian 1.1.2.1 if (pass==0 && !li.hasNext()) continue;
152 cananian 1.1.2.1 // l and h will be the boundaries of the field, if we put it
153 cananian 1.1.2.1 // in this interval.
154 cananian 1.1.2.1 int l = i.low;
155 cananian 1.1.2.1 // if 'mustAlign' boot all fields which aren't perfectly aligned.
156 cananian 1.1.2.1 if (mustAlign && (!li.hasNext()) && 0!=(l%align)) continue;
157 cananian 1.1.2.1 // if 'prefAlign' boot fields which aren't preferentially aligned
158 cananian 1.1.2.1 if (prefAlign && (!li.hasNext()) && 0!=(l%palign)) continue;
159 cananian 1.1.2.1 // okay, otherwise add padding if necessary.
160 cananian 1.1.2.2 while ((l%malign)!=0) l++; // (slow, but works even w/ negative l)
161 cananian 1.1.2.1 int h = l + size;
162 cananian 1.1.2.1 if (h <= i.high) { // yay, the field fits here!
163 cananian 1.1.2.1 // update interval list.
164 cananian 1.1.2.1 Interval bot = new Interval(i.low, l);
165 cananian 1.1.2.1 Interval top = new Interval(h, i.high);
166 cananian 1.1.2.1 li.remove(); // replace the old interval with the split ones
167 cananian 1.1.2.1 if (bot.low < bot.high) li.add(bot);
168 cananian 1.1.2.1 if (top.low < top.high) li.add(top);
169 cananian 1.1.2.1 // cache field offset.
170 cananian 1.1.2.1 fieldcache.put(hf, new Integer(l));
171 cananian 1.1.2.1 // done!
172 cananian 1.1.2.1 return true; // successfully alloc'ed this field
173 cananian 1.1.2.1 }
174 cananian 1.1.2.1 }
175 cananian 1.1.2.1 }
176 cananian 1.1.2.1 return false; // unable to alloc this field, given our constraints
177 cananian 1.1.2.1 }
178 cananian 1.1.2.1 /** maps fields to already-computed offsets */
179 cananian 1.1.2.1 private final Map<HField,Integer> fieldcache =
180 cananian 1.1.2.1 new HashMap<HField,Integer>();
181 cananian 1.1.2.1
182 cananian 1.1.2.1 /** this method returns the cached 'free space' list for class hc.
183 cananian 1.1.2.1 * if the free space list for hc has not already been created and
184 cananian 1.1.2.1 * cached, invokes do_one(hc) to create and cache it. hc==null
185 cananian 1.1.2.1 * indicates the "non-existent superclass of everything", and
186 cananian 1.1.2.1 * naturally fields can be allocated anywhere in it. This is
187 cananian 1.1.2.1 * represented as the interval [0, infinity). */
188 cananian 1.1.2.1 private Interval[] freespace(HClass hc) {
189 cananian 1.1.2.1 if (hc==null)
190 cananian 1.1.2.1 if (runtime.clazBytes==4)
191 cananian 1.1.2.1 return new Interval[] { new Interval(0, Integer.MAX_VALUE) };
192 cananian 1.1.2.3 else if (runtime.hashlockShrink)
193 cananian 1.1.2.3 return new Interval[] { new Interval(-4+runtime.clazBytes,
194 cananian 1.1.2.3 Integer.MAX_VALUE) };
195 cananian 1.1.2.1 else
196 cananian 1.1.2.1 return new Interval[] { new Interval(-8+runtime.clazBytes, -4),
197 cananian 1.1.2.1 new Interval(0, Integer.MAX_VALUE) };
198 cananian 1.1.2.1 if (!freecache.containsKey(hc)) do_one(hc);
199 cananian 1.1.2.1 assert freecache.containsKey(hc);
200 cananian 1.1.2.1 return freecache.get(hc);
201 cananian 1.1.2.1 }
202 cananian 1.1.2.1 /** maps classes to 'free space' lists. */
203 cananian 1.1.2.1 private final Map<HClass,Interval[]> freecache =
204 cananian 1.1.2.1 new HashMap<HClass,Interval[]>();
205 cananian 1.1.2.1
206 cananian 1.1.2.1 /** This class represents an open interval in the class, which we
207 cananian 1.1.2.1 * may assign a field to (if it fits). */
208 cananian 1.1.2.1 private static class Interval {
209 cananian 1.1.2.1 final int low, high;
210 cananian 1.1.2.1 Interval(int low, int high) { this.low = low; this.high=high; }
211 cananian 1.1.2.1 }
212 cananian 1.2 }