001: // Copyright (c) 1997 Per M.A. Bothner.
002: // This is free software; for terms and warranty disclaimer see ./COPYING.
003:
004: package gnu.bytecode;
005:
006: import java.io.*;
007:
008: /**
009: * A Label represents a location in a Code attribute.
010: */
011:
012: /*
013: * Java VM control transfer instructions contain PC-relative offsets
014: * to the target (location/Label). (The offsets are relative to the
015: * start of the instruction.) A complication is that some instructions
016: * use 2-byte relative offsets, while others use 4-byte relative offsets.
017: * A few instructions exist in both "narrow" 2-byte and "wide" 4-byte forms.
018: *
019: * This library uses a very simple data structure to accumulate
020: * generated instructions - just a simple byte array of opcodes and
021: * operands, just as in the final .class file. When emitting a forward
022: * branch, we cannot emit the relative addresss of the still-unknown
023: * target. Instead, we emit the negative of the PC of the instruction,
024: * and later add the address of the target by back-patching.
025: * We keep track of which locations need back-patching in the fixups and
026: * wide_fixups arrays (for 2-byte and 4-byte offsets, respectively).
027: * This is simple, fast, and concise. However, if it turns out that
028: * the target is more than 32767 bytes away, we have problem: Once an
029: * instruction has been emitted, we cannot change its size (e.g. change
030: * a 2-byte jump offset into a 4-byte offset). (I.e. there is no
031: * "relaxation" as is done by many assemblers.)
032: *
033: * Since very few methods actually need 4-byte jump offsets, the code
034: * generator optimistically assumes that when it emits a forward branch
035: * the not-yet-defined label will later be defined within the 2-byte span
036: * of the current instruction. (Except of course for instructions like
037: * tableswitch and lookupswitch that only exist in 4-byte-offset form.)
038: *
039: * But what do we do if it turns out that the branch target is > 32767
040: * bytes away? In that case, we emit what I call a "spring" *before*
041: * we get out of range. A "spring" is a trivial basic block that
042: * contains only a single wide goto. The branches that are close to
043: * the limit are patched to point to the "spring" instead. Before
044: * every instruction CodeAttr.reserve is called. It checks if there
045: * are any pending banches that are getting close to the limit for
046: * 2-byte offsets, in which case it calls Label.emit_spring to
047: * generate the spring.
048: *
049: * Note that we may also need a spring even if the target is known,
050: * if we need a 2-byte offset, and the target is too far away.
051: *
052: * Note that while the Java bytecodes supports 32-bit relative address,
053: * there are limitations in the .class file format that limit each
054: * method to 2*16 bytes. This may change. In any case, this code has
055: * been written to support "wide jumps" - but that has not been tested!
056: */
057:
058: public class Label {
059: Label next;
060:
061: // The PC of where the label is, or -1 if not yet defined.
062: int position;
063:
064: // If >= 0, this is the location of a "spring" to this Label.
065: int spring_position;
066:
067: // Array of PC locations that reference this Label.
068: // Elements that are -1 provide room to grow.
069: // For an element fi in fixups (where fi >= 0), the 2-byte
070: // sequence code[fi]:code[fi+1] will need to be adjusted (relocated) by
071: // the position of this Label, or alternatively spring_postion.
072: // After relocation, code[fi]:code[fi+1] will be a reference to
073: // this label (usually a PC-relative reference).
074: // The lowest element fi (>= 0) is first, but fixups is otherwise unsorted.
075: // Normally, if defined(), then fixups is null.
076: // However, we may still need fixups even if defined(), if
077: // position is further away than allowed by a 16-bit offset.
078: int[] fixups;
079:
080: // Similar to fixups, but each element is a 4-byte relative jump offset.
081: int[] wide_fixups;
082:
083: public final boolean defined() {
084: return position >= 0;
085: }
086:
087: public Label(Method method) {
088: this (method.code);
089: }
090:
091: public Label(CodeAttr code) {
092: position = -1;
093: if (code.labels != null) {
094: next = code.labels.next;
095: code.labels.next = this ;
096: } else
097: code.labels = this ;
098: }
099:
100: /* Make all narrow fixups for this label point (relatively) to target. */
101: final private void relocate_fixups(CodeAttr code, int target) {
102: if (fixups == null)
103: return;
104: for (int i = fixups.length; --i >= 0;) {
105: int pos = fixups[i];
106: /* Adjust the 2-byte offset at pos in method by target. */
107: if (pos >= 0) {
108: byte[] insns = code.getCode();
109: int code_val = (insns[pos] << 8)
110: | (insns[pos + 1] & 0xFF);
111: code_val += target;
112: if (code_val < -32768 || code_val >= 32768)
113: throw new Error("overflow in label fixup");
114: insns[pos] = (byte) (code_val >> 8);
115: insns[pos + 1] = (byte) (code_val);
116: }
117: }
118: if (this != code.labels)
119: code.reorder_fixups();
120: fixups = null;
121: }
122:
123: /* Adjust the 4-byte offset at pos in method by target. */
124: static final void relocate_wide(CodeAttr code, int pos, int target) {
125: if (pos >= 0) {
126: byte[] insns = code.getCode();
127: int code_val = ((insns[pos] & 0xFF) << 24)
128: | ((insns[pos + 1] & 0xFF) << 16)
129: | ((insns[pos + 2] & 0xFF) << 8)
130: | (insns[pos + 3] & 0xFF);
131: code_val += target;
132: insns[pos] = (byte) (code_val >> 24);
133: insns[pos + 1] = (byte) (code_val >> 16);
134: insns[pos + 2] = (byte) (code_val >> 8);
135: insns[pos + 3] = (byte) code_val;
136: }
137: }
138:
139: /**
140: * Define the value of a label as having the current location.
141: * @param code the "Code" attribute of the current method
142: */
143: public void define(CodeAttr code) {
144: code.unreachable_here = false;
145: if (position >= 0)
146: throw new Error("label definition more than once");
147:
148: position = code.PC;
149:
150: /* Remove redundant goto in: goto L; L:
151: These tend to be generated when compiling IfExp's,
152: so it is worth checking for them.
153: */
154: int goto_pos = position - 3; // Position of hypothetical goto.
155: if (code.readPC <= goto_pos && fixups != null
156: && wide_fixups == null && goto_pos > 0
157: && code.getCode()[goto_pos] == (167 - 256) /* goto */) {
158: int i;
159: goto_pos++; // Skip goto opcode.
160: for (i = fixups.length; --i >= 0;) {
161: if (fixups[i] == goto_pos)
162: break;
163: }
164: if (i >= 0) {
165: position -= 3;
166: code.PC = position;
167: fixups[i] = -1;
168: }
169: }
170:
171: code.readPC = position;
172: relocate_fixups(code, position);
173:
174: if (wide_fixups != null) {
175: for (int i = wide_fixups.length; --i >= 0;)
176: relocate_wide(code, wide_fixups[i], position);
177: wide_fixups = null;
178: }
179: }
180:
181: /**
182: * Emit goto_w as target for far-away gotos in large methods.
183: * Needs to be invoked if the earliest still-pending fixup
184: * is at the limit of a 2-byte relative jump.
185: * To solve the problem, we emit a goto_w for the label,
186: * and change all pending (short) fixups to point here.
187: * We also have to jump past this goto.
188: */
189:
190: void emit_spring(CodeAttr code) {
191: code.reserve(8);
192: if (!code.unreachable_here) {
193: code.put1(167); // goto PC+6
194: code.put2(6);
195: }
196: spring_position = code.PC;
197: relocate_fixups(code, spring_position);
198: code.put1(200); // goto_w
199: emit_wide(code, spring_position);
200: code.readPC = code.PC;
201: }
202:
203: /* Save a fixup so we can later backpatch code[PC..PC+1]. */
204: private void add_fixup(CodeAttr code) {
205: int PC = code.PC;
206: int i;
207: if (fixups == null) {
208: fixups = new int[2];
209: fixups[0] = PC;
210: fixups[1] = -1;
211: } else {
212: int fixups_length = fixups.length;
213: for (i = 0; i < fixups_length && fixups[i] >= 0;)
214: i++;
215: if (i == fixups_length) {
216: int[] new_fixups = new int[2 * fixups.length];
217: System.arraycopy(fixups, 0, new_fixups, 0,
218: fixups.length);
219: i = new_fixups.length;
220: do {
221: new_fixups[--i] = -1;
222: } while (i > fixups_length);
223: fixups = new_fixups;
224: }
225: if (PC < fixups[0]) {
226: fixups[i] = fixups[0];
227: fixups[0] = PC;
228: } else
229: fixups[i] = PC;
230: }
231: if (this != code.labels
232: && (code.labels.fixups == null || PC < code.labels.fixups[0]))
233: code.reorder_fixups();
234: }
235:
236: private void add_wide_fixup(int PC) {
237: int i;
238: if (wide_fixups == null) {
239: wide_fixups = new int[2];
240: wide_fixups[0] = PC;
241: wide_fixups[1] = -1;
242: return;
243: }
244: for (i = 0; i < wide_fixups.length; i++) {
245: if (wide_fixups[i] < 0) {
246: wide_fixups[i] = PC;
247: return;
248: }
249: }
250: int[] new_fixups = new int[2 * wide_fixups.length];
251: System.arraycopy(wide_fixups, 0, new_fixups, 0,
252: wide_fixups.length);
253: new_fixups[wide_fixups.length] = PC;
254: for (i = wide_fixups.length; ++i < new_fixups.length;)
255: new_fixups[i] = -1;
256: wide_fixups = new_fixups;
257: }
258:
259: /** Return true if there are references to this Label.
260: We assume !defined(). */
261: public boolean hasFixups() {
262: return fixups != null || wide_fixups != null;
263: }
264:
265: /**
266: * Emit a reference to the current label.
267: * @param method the current method
268: * Emit the reference as a 2-byte difference relative to PC-1.
269: */
270:
271: public void emit(CodeAttr code) {
272: int PC_rel = 1 - code.PC;
273: int delta = PC_rel;
274: if (defined()) {
275: delta += position;
276: if (delta < -32768) {
277: if (spring_position >= 0
278: && spring_position + PC_rel >= -32768)
279: delta = spring_position + PC_rel;
280: else {
281: add_fixup(code);
282: delta = PC_rel;
283: }
284: }
285: } else
286: add_fixup(code);
287: code.put2(delta);
288: }
289:
290: /**
291: * Emit a wide reference to the current label.
292: * @param code the current method
293: * @param start_pc the PC at the start of this instruction
294: * Emit the reference as a 4-byte difference relative to PC-offset.
295: */
296: public void emit_wide(CodeAttr code, int start_pc) {
297: int delta = -start_pc;
298: if (defined())
299: delta += position;
300: else
301: add_wide_fixup(code.PC);
302: code.put4(delta);
303: }
304: }
|