001: /* -*- mode: Java; c-basic-offset: 2; -*- */
002:
003: /***
004: * InstructionCollector.java
005: *
006: * Description: Instruction buffer for the assembler
007: *
008: * Assembly consists of two passes, one to create the constant
009: * pool, and another to assemble the instructions to byte sequences.
010: * The InstructionBuffer holds instructions between these passes.
011: *
012: * The InstructionBuffer will be replaced by a FlowAnalyzer, which will
013: * perform basic-block analysis. That's the main justification for
014: * keeping this class here, instead of adding a wrapper around
015: * Assembler the way peep-hole optimization is done.
016: *
017: * During the first pass (as instructions are collected), the buffer
018: * scans the instruction sequence for string arguments to PUSH
019: * instructions. It computes an occurrence count for each string, and
020: * sorts the list of strings that occurred more than once by occurrence
021: * count. The first 64K of these are placed in the constant pool.
022: * (The sort assures that PUSH can use one-byte indices for the most
023: * frequently-referenced strings.)
024: *
025: * During the second pass, each instruction is passed to the assembler,
026: * and the resulting bytecodes are appended to an accumulated bytecode
027: * sequence.
028: */package org.openlaszlo.sc;
029:
030: import java.io.*;
031: import java.nio.*;
032: import java.util.*;
033: import org.openlaszlo.sc.Instructions.*;
034:
035: public class InstructionCollector extends ArrayList {
036: public int nextLabel;
037: public ConstantCollector constantCollector;
038: public boolean constantsGenerated;
039:
040: public InstructionCollector(boolean disableConstantPool,
041: boolean sortConstantPool) {
042: super ();
043: this .nextLabel = 0;
044: if (!disableConstantPool) {
045: this .constantCollector = sortConstantPool ? new SortedConstantCollector()
046: : new ConstantCollector();
047: } else {
048: this .constantCollector = null;
049: }
050: this .constantsGenerated = false;
051: }
052:
053: public void emit(Instruction instr) {
054: // Update the constant pool.
055: if (constantCollector != null
056: && instr instanceof PUSHInstruction) {
057: PUSHInstruction push = (PUSHInstruction) instr;
058: for (Iterator i = push.args.iterator(); i.hasNext();) {
059: Object next = i.next();
060: if (next instanceof String) {
061: constantCollector.add(next);
062: }
063: }
064: }
065: super .add(instr);
066: }
067:
068: public void push(Object value) {
069: emit(Instructions.PUSH.make(value));
070: }
071:
072: public void push(int value) {
073: push(new Integer(value));
074: }
075:
076: public void push(boolean value) {
077: push(Boolean.valueOf(value));
078: }
079:
080: public void generateConstants() {
081: // Only okay to call this once.
082: assert (!constantsGenerated);
083: ConstantCollector pool = constantCollector;
084: // TODO: [2003-07-15 ptw] (krank) turn off the constant pool
085: // for simplicity for now, but someday eliminate that
086: if (pool != null && (!pool.isEmpty())) {
087: // TODO: [2003-03-06 ptw] Make CONSTANTS its own class?
088: super .add(0, Instructions.CONSTANTS.make(pool
089: .getConstants()));
090: constantsGenerated = true;
091: }
092: }
093:
094: // Rename labels uniquely
095: private Object uniqueLabel(Map labels, Object label) {
096: Object newLabel = labels.get(label);
097: if (newLabel == null) {
098: newLabel = newLabel();
099: labels.put(label, newLabel);
100: }
101: return newLabel;
102: }
103:
104: public void appendInstructions(List instrsList) {
105: // TODO [2003-03-06 ptw] Why not relabel all instructions? (I.e.,
106: // move this to emit)
107: Map labels = new HashMap();
108: Instruction[] instrs = (Instruction[]) instrsList
109: .toArray(new Instruction[0]);
110: for (int i = 0; i < instrs.length; i++) {
111: Instruction instr = instrs[i];
112: if (instr instanceof LABELInstruction) {
113:
114: Object newLabel = uniqueLabel(labels,
115: ((LABELInstruction) instr).name);
116: instr = Instructions.LABEL.make(newLabel);
117: } else if (instr instanceof TargetInstruction) {
118: TargetInstruction target = (TargetInstruction) instr;
119: Object newLabel = uniqueLabel(labels, target
120: .getTarget());
121: instr = target.replaceTarget(newLabel);
122: }
123: emit(instr);
124: }
125: }
126:
127: public List getInstructions(boolean generateConstants) {
128: if (!constantsGenerated && generateConstants) {
129: generateConstants();
130: }
131: return this ;
132: }
133:
134: public String newLabel() {
135: return "L" + nextLabel++;
136: }
137:
138: public String newLabel(String prefix) {
139: return prefix + "$" + nextLabel++;
140: }
141:
142: public static class ConstantCollector extends ArrayList {
143: public Object[] getConstants() {
144: return toArray();
145: }
146: }
147:
148: // Long way to go for a closure
149: public static class ConstantSorter implements Comparator {
150: public int compare(Object o1, Object o2) {
151: Map.Entry me1 = (Map.Entry) o1;
152: int n1 = ((Integer) me1.getValue()).intValue();
153: Map.Entry me2 = (Map.Entry) o2;
154: int n2 = ((Integer) me2.getValue()).intValue();
155: // Sort larger to the front (higher usage)
156: // Longer string wins in a tie
157: if (n1 == n2) {
158: int l1 = ((String) me1.getKey()).length();
159: int l2 = ((String) me2.getKey()).length();
160: return l2 - l1;
161: } else {
162: return n2 - n1;
163: }
164: }
165:
166: public boolean equals(Object other) {
167: // Too specific? Do we care?
168: return this == other;
169: }
170: }
171:
172: // There is probably some idiom for singletons that I don't know
173: private static ConstantSorter sorter = new ConstantSorter();
174:
175: // This is kind of like a sorted set, but delays the sorting until
176: // you ask for values from the set, and has a special limit on the
177: // number of values that can be in the set.
178: public static class SortedConstantCollector extends
179: ConstantCollector {
180: public Map usageCount;
181: public boolean updated;
182: public boolean frozen;
183:
184: SortedConstantCollector() {
185: super ();
186: usageCount = new HashMap();
187: updated = false;
188: frozen = false;
189: }
190:
191: public void add(int index, Object value) {
192: assert (!frozen) : "Add after constant pool frozen";
193: updated = false;
194: if (usageCount.containsKey(value)) {
195: int n = ((Integer) usageCount.get(value)).intValue();
196: usageCount.put(value, new Integer(n + 1));
197: } else {
198: usageCount.put(value, new Integer(1));
199: }
200: }
201:
202: public boolean add(Object value) {
203: add(size(), value);
204: return true;
205: }
206:
207: public boolean addAll(int index, Collection c) {
208: for (Iterator i = c.iterator(); i.hasNext(); index++) {
209: add(index, i.next());
210: }
211: return true;
212: }
213:
214: public boolean addAll(Collection c) {
215: return addAll(size(), c);
216: }
217:
218: public void clear() {
219: assert (!frozen) : "Clear after constant pool frozen";
220: updated = false;
221: usageCount.clear();
222: super .clear();
223: }
224:
225: public boolean contains(Object value) {
226: // Should this return if value was ever added, or if value will
227: // be in the permitted subset?
228: return usageCount.containsKey(value);
229: }
230:
231: public int indexOf(Object value) {
232: update();
233: return super .indexOf(value);
234: }
235:
236: public boolean isEmpty() {
237: return usageCount.size() == 0;
238: }
239:
240: public int lastIndexOf(Object value) {
241: update();
242: return super .lastIndexOf(value);
243: }
244:
245: private Object removeInternal(int index) {
246: assert (!frozen) : "removeInternal after constant pool frozen";
247: updated = false;
248: Object value = super .remove(index);
249: usageCount.remove(value);
250: return value;
251: }
252:
253: public Object remove(int index) {
254: update();
255: return removeInternal(index);
256: }
257:
258: protected void removeRange(int fromIndex, int toIndex) {
259: update();
260: for (int i = fromIndex; i < toIndex; i++) {
261: removeInternal(i);
262: }
263: }
264:
265: public Object set(int index, Object value) {
266: update();
267: remove(index);
268: add(value);
269: return value;
270: }
271:
272: public Object[] toArray() {
273: update();
274: return super .toArray();
275: }
276:
277: public Object[] toArray(Object[] array) {
278: update();
279: return super .toArray(array);
280: }
281:
282: public String toString() {
283: update();
284: return super .toString();
285: }
286:
287: private void update() {
288: if (!updated) {
289: assert (!frozen) : "update after constant pool frozen";
290: super .clear();
291: ArrayList sorted = new ArrayList();
292: for (Iterator i = usageCount.entrySet().iterator(); i
293: .hasNext();) {
294: sorted.add(i.next());
295: }
296: Collections.sort(sorted, sorter);
297: // Total size of an action must be < 65535, opcode + length
298: // field is 3 bytes, also must account for encoding of strings
299: int room = 65535 - 3;
300: String encoding = "UTF-8";
301: String runtime = Instructions.getRuntime();
302: try {
303: for (Iterator i = sorted.iterator(); i.hasNext();) {
304: String symbol = (String) ((Map.Entry) i.next())
305: .getKey();
306: room -= (symbol.getBytes(encoding).length + 1);
307: if (room <= 0)
308: break;
309: super .add(symbol);
310: }
311: } catch (UnsupportedEncodingException e) {
312: assert false : "this can't happen";
313: }
314: updated = true;
315: }
316: }
317:
318: public Object[] getConstants() {
319: Object[] constants = toArray();
320: frozen = true;
321: return constants;
322: }
323: }
324: }
|