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.Analysis;
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.4 * @version $Id: PackedClassFieldMap.java,v 1.4 2002/04/10 03:02:22 cananian Exp $
30 cananian 1.1.2.1 */
31 cananian 1.1.2.1 public abstract class PackedClassFieldMap extends FieldMap {
32 cananian 1.1.2.1 /** Creates a <code>PackedClassFieldMap</code>. */
33 cananian 1.1.2.1 public PackedClassFieldMap() { /* no special initialization */ }
34 cananian 1.1.2.1
35 cananian 1.1.2.1 /** Return an offset to the given field. */
36 cananian 1.1.2.1 public int fieldOffset(HField hf) {
37 cananian 1.3.2.1 assert !hf.isStatic();
38 cananian 1.1.2.1 if (!fieldcache.containsKey(hf)) do_one(hf.getDeclaringClass());
39 cananian 1.3.2.1 assert fieldcache.containsKey(hf);
40 cananian 1.3.2.2 return fieldcache.get(hf).intValue();
41 cananian 1.1.2.1 }
42 cananian 1.1.2.1 /** Return an unmodifiable List over all appropriate fields in the given
43 cananian 1.1.2.1 * class, in order from smallest to largest offset. */
44 cananian 1.3.2.2 public List<HField> fieldList(HClass hc) {
45 cananian 1.1.2.1 // get list of all fields in this class and its parents.
46 cananian 1.3.2.2 List<HField> l = new ArrayList<HField>();
47 cananian 1.1.2.1 for (HClass p = hc; p!=null; p=p.getSuperclass())
48 cananian 1.1.2.1 l.addAll(Arrays.asList(p.getDeclaredFields()));
49 cananian 1.1.2.1 // weed out static fields
50 cananian 1.3.2.2 for (Iterator<HField> it=l.iterator(); it.hasNext(); )
51 cananian 1.3.2.2 if (it.next().isStatic())
52 cananian 1.1.2.1 it.remove();
53 cananian 1.1.2.1 // now sort by fieldOffset.
54 cananian 1.3.2.2 Collections.sort(l, new Comparator<HField>() {
55 cananian 1.3.2.2 public int compare(HField hf1, HField hf2) {
56 cananian 1.1.2.1 return fieldOffset(hf1) - fieldOffset(hf2);
57 cananian 1.1.2.1 }
58 cananian 1.1.2.1 });
59 cananian 1.1.2.2 // quick verification of well-formedness
60 cananian 1.1.2.2 // (offsets must be strictly increasing)
61 cananian 1.1.2.2 int last=-1;
62 cananian 1.3.2.2 for (Iterator<HField> it=l.iterator(); it.hasNext(); ) {
63 cananian 1.3.2.2 int off=fieldOffset(it.next());
64 cananian 1.3.2.1 assert last<off : "Ill-formed field list";
65 cananian 1.1.2.2 last = off;
66 cananian 1.1.2.2 }
67 cananian 1.1.2.1 // done!
68 cananian 1.1.2.1 return l;
69 cananian 1.1.2.1 }
70 cananian 1.1.2.1
71 cananian 1.1.2.1 /** this method assigns "good" offsets to all the fields in class hc,
72 cananian 1.1.2.1 * using the assignments in hc's superclass and the list of free space
73 cananian 1.1.2.1 * in the superclass as starting points. */
74 cananian 1.1.2.1 private void do_one(HClass hc) {
75 cananian 1.3.2.1 assert hc!=null;
76 cananian 1.1.2.1 // get the 'free space' structure of the parent.
77 cananian 1.3.2.2 List<Interval> free = new LinkedList<Interval>
78 cananian 1.3.2.2 (Arrays.asList(freespace(hc.getSuperclass())));
79 cananian 1.1.2.1 // get all the fields of this class that we have to allocate.
80 cananian 1.3.2.2 List<HField> l =
81 cananian 1.3.2.2 new ArrayList<HField>(Arrays.asList(hc.getDeclaredFields()));
82 cananian 1.1.2.1 // weed out static fields
83 cananian 1.3.2.2 for (Iterator<HField> it=l.iterator(); it.hasNext(); )
84 cananian 1.3.2.2 if (it.next().isStatic())
85 cananian 1.1.2.1 it.remove();
86 cananian 1.1.2.1 // we're going to allocate fields from largest to smallest,
87 cananian 1.1.2.1 // so sort them first. (primarily sort by size, then by alignment)
88 cananian 1.3.2.2 Collections.sort(l, new Comparator<HField>() {
89 cananian 1.3.2.2 public int compare(HField hf1, HField hf2) {
90 cananian 1.1.2.1 // note reversed comparison here so that largest end up first.
91 cananian 1.1.2.1 int r = fieldSize(hf2) - fieldSize(hf1);
92 cananian 1.1.2.1 if (r==0) r = fieldAlignment(hf2) - fieldAlignment(hf1);
93 cananian 1.1.2.1 return r;
94 cananian 1.1.2.1 }
95 cananian 1.1.2.1 });
96 cananian 1.1.2.1 // now allocate them one by one (largest to smallest, like we said)
97 cananian 1.1.2.1 // the alloc_one method has the side effect of adding an entry to
98 cananian 1.1.2.1 // the fieldcache.
99 cananian 1.3.2.2 for (Iterator<HField> it=l.iterator(); it.hasNext(); )
100 cananian 1.3.2.2 alloc_one(it.next(), free);
101 cananian 1.1.2.1 // cache away the free list for the next guy (subclasses of this)
102 cananian 1.3.2.2 freecache.put(hc, free.toArray(new Interval[free.size()]));
103 cananian 1.1.2.1 // done!
104 cananian 1.1.2.1 }
105 cananian 1.1.2.1 /** this method tries to allocate the field hf as low in the object
106 cananian 1.1.2.1 * as possible, using the current list of free spaces in the class. */
107 cananian 1.3.2.2 private void alloc_one(HField hf, List<Interval> free) {
108 cananian 1.1.2.1 int size = fieldSize(hf), align = fieldAlignment(hf);
109 cananian 1.1.2.1 // go through free list, looking for a place to put this.
110 cananian 1.3.2.2 for (ListIterator<Interval> li = free.listIterator(); li.hasNext(); ) {
111 cananian 1.3.2.2 Interval i = li.next();
112 cananian 1.3.2.1 assert i.low < i.high; // validity of interval.
113 cananian 1.1.2.1 // l and h will be the boundaries of the field, if we put it
114 cananian 1.1.2.1 // in this interval.
115 cananian 1.1.2.1 int l = i.low;
116 cananian 1.1.2.1 if ((l%align)!=0) l+= align - (l % align);
117 cananian 1.1.2.1 int h = l + size;
118 cananian 1.1.2.1 if (h <= i.high) { // yay, the field fits here!
119 cananian 1.1.2.1 // update interval list.
120 cananian 1.1.2.1 Interval bot = new Interval(i.low, l);
121 cananian 1.1.2.1 Interval top = new Interval(h, i.high);
122 cananian 1.1.2.1 li.remove(); // replace the old interval with the split ones
123 cananian 1.1.2.1 if (bot.low < bot.high) li.add(bot);
124 cananian 1.1.2.1 if (top.low < top.high) li.add(top);
125 cananian 1.1.2.1 // cache field offset.
126 cananian 1.1.2.1 fieldcache.put(hf, new Integer(l));
127 cananian 1.1.2.1 // done!
128 cananian 1.1.2.1 return;
129 cananian 1.1.2.1 }
130 cananian 1.1.2.1 }
131 cananian 1.1.2.1 // the last interval goes to infinity; we should always be able to
132 cananian 1.1.2.1 // allocate at the end of the object (ie never get to this point)
133 cananian 1.1.2.1 throw new Error("Should never get here!");
134 cananian 1.1.2.1 }
135 cananian 1.1.2.1 /** maps fields to already-computed offsets */
136 cananian 1.3.2.2 private final Map<HField,Integer> fieldcache =
137 cananian 1.3.2.2 new HashMap<HField,Integer>();
138 cananian 1.1.2.1
139 cananian 1.1.2.1 /** this method returns the cached 'free space' list for class hc.
140 cananian 1.1.2.1 * if the free space list for hc has not already been created and
141 cananian 1.1.2.1 * cached, invokes do_one(hc) to create and cache it. hc==null
142 cananian 1.1.2.1 * indicates the "non-existent superclass of everything", and
143 cananian 1.1.2.1 * naturally fields can be allocated anywhere in it. This is
144 cananian 1.1.2.1 * represented as the interval [0, infinity). */
145 cananian 1.1.2.1 private Interval[] freespace(HClass hc) {
146 cananian 1.1.2.1 if (hc==null)
147 cananian 1.1.2.1 return new Interval[] { new Interval(0, Integer.MAX_VALUE) };
148 cananian 1.1.2.1 if (!freecache.containsKey(hc)) do_one(hc);
149 cananian 1.3.2.1 assert freecache.containsKey(hc);
150 cananian 1.3.2.2 return freecache.get(hc);
151 cananian 1.1.2.1 }
152 cananian 1.1.2.1 /** maps classes to 'free space' lists. */
153 cananian 1.3.2.2 private final Map<HClass,Interval[]> freecache =
154 cananian 1.3.2.2 new HashMap<HClass,Interval[]>();
155 cananian 1.1.2.1
156 cananian 1.1.2.1 /** This class represents an open interval in the class, which we
157 cananian 1.1.2.1 * may assign a field to (if it fits). */
158 cananian 1.1.2.1 private static class Interval {
159 cananian 1.1.2.1 final int low, high;
160 cananian 1.1.2.1 Interval(int low, int high) { this.low = low; this.high=high; }
161 cananian 1.1.2.1 }
162 cananian 1.2 }