001: /* -*- mode: Java; c-basic-offset: 2; -*- */
002:
003: /***
004: * Assembler.java
005: *
006: * Description: The assembler translates an assembly instruction into
007: * a sequence of bytes.
008: */package org.openlaszlo.sc;
009:
010: import java.io.*;
011: import java.nio.*;
012: import java.util.*;
013: import org.openlaszlo.sc.Instructions.*;
014: import org.openlaszlo.sc.Emitter;
015:
016: // Assembly is relatively straightforward except for the PUSH
017: // instruction, and label resolution.
018: //
019: // During the assembly of PUSH, strings in the constant pool are
020: // replaced by constant-pool references.
021: //
022: // Note that the assembler, not the code generator, is responsible for
023: // recognizing which string arguments to a PUSH instruction can refer
024: // to the constant pool.
025: //
026: // Label targets are are entered in a table mapping label names to
027: // offsets. Instructions that contain label sources are processed as
028: // follows: a backwards reference is replaced by a byte offset, while a
029: // forward-reference is entered in a table mapping a label name to a
030: // list of offsets whence the label is referenced. When a label is
031: // encountered, the forward-reference table is used to backpatch
032: // forward references.
033:
034: public class Assembler implements Emitter {
035: Hashtable labels;
036: ByteBuffer bytes;
037: private static byte[] backingStore;
038: Hashtable constants;
039:
040: // relative indicates a normal relative reference if relative is
041: // false, this reference is part of label arithmetic, that is, a
042: // difference of two labels:
043: // (label2 - label1)
044: // this produces two references, one with positive=true and one
045: // with positive=false.
046: public static class LabelReference {
047: int patchloc;
048: boolean relative;
049: boolean positive;
050: }
051:
052: public static class Label {
053: Object name;
054: int location;
055: List references;
056:
057: // Java sucks
058: protected int MIN_OFFSET() {
059: return -1 << 15;
060: };
061:
062: protected int MAX_OFFSET() {
063: return (1 << 15) - 1;
064: };
065:
066: public Label(Object name) {
067: this .name = name;
068: this .location = -1;
069: this .references = new ArrayList();
070: }
071:
072: public boolean isResolved() {
073: return location != -1;
074: }
075:
076: public void setLocation(ByteBuffer bytes) {
077: assert (!isResolved()) : "Label.setLocation() called on resolved label";
078: assert bytes.order() == ByteOrder.LITTLE_ENDIAN;
079: location = bytes.position();
080: // Backpatch forward jumps
081: for (Iterator i = references.iterator(); i.hasNext();) {
082: LabelReference lr = (LabelReference) i.next();
083: int patchloc = lr.patchloc;
084: int offset = location - (patchloc + 2);
085: if (!lr.relative) {
086: // If we are doing label arithmetic, we store the relative
087: // offset of the first label we encounter, when the second
088: // label is encountered it will subtract its offset. When
089: // the instruction is first written, it will write 0 offsets
090: // at the patchloc. So, the test for curval == 0 is saying
091: // "is this the first label we have encountered for this
092: // location?" And if so, it will not do any arithmetic, it
093: // will simply write the offset of that label into the
094: // patchloc.
095: // FIXME [2007-12-14 ptw] (LPP-5262) This will fail if the
096: // blocks in the try are maximal
097: // Fetch unsigned:
098: int curval = bytes.getShort(patchloc)
099: & MAX_OFFSET();
100: if (curval == 0) {
101: ;
102: } else if (lr.positive) {
103: offset = offset - curval;
104: } else {
105: offset = curval - offset;
106: }
107: }
108:
109: if (offset < MIN_OFFSET() || offset > MAX_OFFSET()) {
110: throw new CompilerException(
111: (this instanceof Block ? "Block" : "Label")
112: + " " + name + ": jump offset "
113: + offset + " too large");
114: }
115: bytes.putShort(patchloc, (short) offset);
116: }
117: references = null;
118: }
119:
120: public short computeOffset(ByteBuffer bytes) {
121: assert (isResolved()) : "Label.computeOffset() called on unresolved label";
122: assert bytes.order() == ByteOrder.LITTLE_ENDIAN;
123: int offset = location - bytes.position();
124: if (offset < MIN_OFFSET() || offset > MAX_OFFSET()) {
125: throw new CompilerException(
126: (this instanceof Block ? "Block" : "Label")
127: + " " + name + ": jump offset "
128: + offset + " too large");
129: }
130: return (short) offset;
131: }
132:
133: public void addReference(int patchloc) {
134: addReference(patchloc, true, true);
135: }
136:
137: public void addReference(int patchloc, boolean relative,
138: boolean positive) {
139: assert (!isResolved()) : "adding reference to resolved label";
140: LabelReference lr = new LabelReference();
141: lr.patchloc = patchloc;
142: lr.relative = relative;
143: lr.positive = positive;
144: references.add(lr);
145: }
146:
147: public String toString() {
148: return name.toString();
149: }
150: }
151:
152: public static class Block extends Label {
153: protected int MIN_OFFSET() {
154: return 0;
155: };
156:
157: protected int MAX_OFFSET() {
158: return (1 << 16) - 1;
159: };
160:
161: public Block(Object name) {
162: super (name);
163: }
164: }
165:
166: private synchronized byte[] getBacking() {
167: byte[] b = backingStore;
168: backingStore = null;
169: return b;
170: }
171:
172: private synchronized void setBacking(byte[] b) {
173: backingStore = b;
174: }
175:
176: public Assembler() {
177: this .labels = new Hashtable(); // {String -> Label}
178: // Try to reuse the backing buffer
179: byte[] bs = getBacking();
180: if (bs != null) {
181: this .bytes = ByteBuffer.wrap(bs);
182: bytes.order(ByteOrder.LITTLE_ENDIAN);
183: } else {
184: // Room to not grow immediately. See emit.
185: this .bytes = ByteBuffer.allocate((1 << 14) + (1 << 16));
186: bytes.order(ByteOrder.LITTLE_ENDIAN);
187: }
188: this .constants = new Hashtable(); // {String -> int}
189: }
190:
191: public byte[] assemble(List instrs) {
192: for (Iterator i = instrs.iterator(); i.hasNext();) {
193: emit((Instruction) i.next());
194: }
195: List unresolvedLabels = new ArrayList();
196: // One wonders why this couldn't be an Iterator
197: for (Enumeration i = labels.elements(); i.hasMoreElements();) {
198: Label label = (Label) i.nextElement();
199: if (!label.isResolved()) {
200: unresolvedLabels.add(label);
201: }
202: }
203: //System.out.println("assembled: " + bytes.toString());
204: assert (unresolvedLabels.size() == 0) : "unresolved labels: "
205: + unresolvedLabels;
206: // TODO [2004-03-04 ptw] be more efficient than this!
207: byte[] result = new byte[bytes.position()];
208: bytes.flip();
209: bytes.get(result);
210: // Save the backing buffer
211: setBacking(bytes.array());
212: return result;
213: }
214:
215: public Label getLabel(Object name, boolean signed) {
216: if (!labels.containsKey(name)) {
217: if (signed) {
218: labels.put(name, new Label(name));
219: } else {
220: labels.put(name, new Block(name));
221: }
222: }
223: return (Label) labels.get(name);
224: }
225:
226: public void resolveTarget(TargetInstruction target, Label[] labels) {
227: if (labels.length > 1) {
228:
229: // Multiple labels indicate that we are doing label arithmetic,
230: // each pair is a difference of values, used to compute the
231: // size of a code block. This is needed for the try instruction.
232: // At the moment, we only implement this for forward references,
233: // which solves the only case we care about with the try instruction.
234:
235: assert labels.length % 2 == 0 : "multiple target labels must be in pairs";
236:
237: // Emit the instruction and then get the list of addresses
238: // to backpatch.
239:
240: int origloc = bytes.position();
241: target.writeBytes(bytes, constants);
242:
243: for (int i = 0; i < labels.length; i += 2) {
244: Label labelpos = labels[i];
245: Label labelneg = labels[i + 1];
246:
247: assert (labelpos.location == -1 && labelneg.location == -1) : "target arithmetic using backward refs not implemented";
248:
249: int targetoff = target.targetOffset(i / 2);
250: int patchloc = (targetoff < 0 ? bytes.position()
251: : origloc)
252: + targetoff;
253:
254: labelpos.addReference(patchloc, false, true); // add absolute pos value
255: labelneg.addReference(patchloc, false, false); // add absolute neg value
256: }
257: } else if (labels[0].location == -1) {
258: // Target location isn't yet available. Use a null
259: // offset, and add the address to be patched to this
260: // label's list of backpatch locations.
261: int origloc = bytes.position();
262: target.writeBytes(bytes, constants);
263:
264: int targetoff = target.targetOffset(0);
265: int patchloc = (targetoff < 0 ? bytes.position() : origloc)
266: + targetoff;
267: labels[0].addReference(patchloc);
268: } else {
269: // Target computation requires that we write the instruction first!
270: target.targetOffset = 0;
271: target.writeBytes(bytes, constants);
272: short offset = labels[0].computeOffset(bytes);
273: assert bytes.order() == ByteOrder.LITTLE_ENDIAN;
274: bytes.putShort(bytes.position() - 2, offset);
275: }
276: }
277:
278: public void emit(Instruction instr) {
279: // Verify there is room for a maximal instruction (1<<16)
280: if (!(bytes.remaining() > 1 << 16)) {
281: // TODO [2004-03-11 ptw] Spool to file above a certain size
282: ByteBuffer newBytes = ByteBuffer
283: .allocate(bytes.capacity() * 2);
284: newBytes.order(ByteOrder.LITTLE_ENDIAN);
285: ByteBuffer oldBytes = bytes;
286: bytes.flip();
287: newBytes.put(bytes);
288: bytes = newBytes;
289: //System.out.println("Grow buffer: " + oldBytes + " => " + newBytes);
290: }
291: if (instr instanceof ConcreteInstruction
292: && ((ConcreteInstruction) instr).op == Actions.CONSTANTS) {
293: // Initialize the constant map
294: this .constants = new Hashtable();
295: for (ListIterator i = ((ConcreteInstruction) instr).args
296: .listIterator(); i.hasNext();) {
297: int index = i.nextIndex();
298: constants.put(i.next(), new Integer(index));
299: }
300: // Fall through to the general case
301: }
302: if (instr instanceof LABELInstruction) {
303: Object name = ((LABELInstruction) instr).name;
304: Label label = getLabel(name, true);
305: assert (!label.isResolved()) : "duplicate label" + label;
306: // Get the current location, and save it for backjumps
307: label.setLocation(bytes);
308: } else if (instr instanceof TargetInstruction) {
309: TargetInstruction target = (TargetInstruction) instr;
310: Object targetval = target.getTarget();
311: Label[] labels;
312: if (targetval instanceof Object[]) {
313: Object[] vals = (Object[]) targetval;
314: labels = new Label[vals.length];
315: for (int i = 0; i < vals.length; i++)
316: labels[i] = getLabel(vals[i],
317: instr instanceof BranchInstruction);
318: } else {
319: labels = new Label[1];
320: labels[0] = getLabel(targetval,
321: instr instanceof BranchInstruction);
322: }
323: resolveTarget(target, labels);
324: } else {
325: instr.writeBytes(bytes, constants);
326: }
327: }
328: }
|