001: /*
002:
003: Derby - Class org.apache.derby.impl.services.bytecode.Conditional
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.services.bytecode;
023:
024: import org.apache.derby.iapi.services.classfile.VMOpcode;
025: import org.apache.derby.iapi.services.sanity.SanityManager;
026:
027: /**
028: A Conditional represents an if/then/else block.
029: When this is created the code will already have
030: the conditional check code. The code is optimized for branch
031: offsets that fit in 2 bytes, though will handle 4 byte offsets.
032: <code>
033: if condition
034: then code
035: else code
036: </code>
037: what actually gets built is
038: <code>
039: if !condition branch to eb:
040: then code
041: goto end: // skip else
042: eb:
043: else code
044: end:
045: </code>
046:
047: If no else condition was provided then the code is:
048:
049: <code>
050: if !condition branch to end:
051: then code
052: end:
053: </code>
054:
055: Note all branches here are using relative offsets, not absolute program counters.
056:
057: If the then code leads to the conditional branch offset being too big (>32k)
058: because the then code is larger than 32767 bytes then this is built:
059: <code>
060: // when else code is present
061: if condition branch to tb: (relative offset +8)
062: goto_w eb: // indirect for else block (5 bytes)
063: tb:
064: then code (> 32767 bytes)
065: goto end:
066: eb:
067: else code
068: end:
069: </code>
070:
071: <code>
072: // when only then code is present
073: if condition branch to tb: (relative offset +8)
074: goto_w end: // indirect for else block (5 bytes)
075: tb:
076: then code (> 32767 bytes)
077: end:
078: </code>
079:
080: If there is an else branch and only it is larger than 32767 bytes then
081: the code is:
082:
083: <code>
084: if !condition branch to eb: (offset increased by two over previous value)
085: then code
086: goto_w end: // skip else
087: eb:
088: else code (> 32767 bytes)
089: end:
090: </code>
091:
092: This has one special case where the size of conditional branch to eb:
093: now must change from a 16bit value to a 32 bit value. The generated code
094: for this is the same as when both the then code and the else code require
095: 32bit offsets for the branches. This code is:
096:
097: <code>
098: if condition branch to tb: (relative offset +8)
099: goto_w eb: // indirect for else block (5 bytes)
100: tb:
101: then code (> 32767 bytes)
102: goto_w end:
103: eb:
104: else code (> 32767 bytes)
105: end:
106: </code>
107:
108: In theory, at the moment this should not happen as this would mean a total
109: code size that exceeds the limit on the code size for a method (64k). This
110: code handles this case as it does occur if the limit for a branch is lowered
111: for testing purposes, to ensure the complete set of branch re-write code works.
112: This lowering of the limit can be done by changing the constant BRANCH16LIMIT.
113:
114: */
115: class Conditional {
116:
117: /**
118: * Limit of a 16 bit branch.
119: * <P>
120: * If broad testing of the switch from 16bit to 32bit
121: * offsets is required then this constant can be reduced
122: * to a lower value, say 50 and run complete tests. This
123: * will cover all the combinations. This works because the
124: * GOTO_W instruction works with any offset value.
125: */
126: private static final int BRANCH16LIMIT = 32767;
127:
128: private final Conditional parent;
129: /**
130: * pc of the 'if' opcode.
131: */
132: private final int if_pc;
133:
134: private Type[] stack;
135:
136: /**
137: * pc of the GOTO added at the end of the then block
138: * to transfer control to the end of this conditional.
139: * That is at the end of the else block.
140: */
141: private int thenGoto_pc;
142:
143: /**
144: * Start a conditional block.
145: * @param parent Current conditional block, null if no nesting is going on.
146: * @param chunk CodeChunk this conditional lives in
147: * @param ifOpcode Opcode for the if check.
148: * @param entryStack Type stack on entering the conditional then block.
149: */
150: Conditional(Conditional parent, CodeChunk chunk, short ifOpcode,
151: Type[] entryStack) {
152: this .parent = parent;
153: if_pc = chunk.getPC();
154: this .stack = entryStack;
155:
156: // reserve the space for the branch, will overwrite later
157: // with the correct branch offset.
158: chunk.addInstrU2(ifOpcode, 0);
159: }
160:
161: /**
162: * Complete the 'then' block and start the 'else' block for this conditional
163: * @param chunk CodeChunk this conditional lives in
164: * @param thenStack Type stack on completing the conditional then block.
165: * @return the type stack on entering the then block
166: */
167: Type[] startElse(BCMethod mb, CodeChunk chunk, Type[] thenStack) {
168:
169: // reserve space for the goto end we will be adding
170: chunk.addInstrU2(VMOpcode.GOTO, 0);
171:
172: // fill in the branch opcode to branch to
173: // the code after the goto, which is the current pc.
174: fillIn(mb, chunk, if_pc, chunk.getPC());
175:
176: // Cannot use the pc before adding the GOTO above
177: // as the fillIn may insert bytes that move the GOTO,
178: // thus calculate at the end, and subtract the number of
179: // instructions in a goto to get its pc.
180: thenGoto_pc = chunk.getPC() - 3;
181:
182: Type[] entryStack = stack;
183: stack = thenStack;
184:
185: return entryStack;
186: }
187:
188: /**
189: * Complete the conditional and patch up any jump instructions.
190: * @param chunk CodeChunk this conditional lives in
191: * @param elseStack Current stack, which is the stack at the end of the else
192: * @param stackNumber Current number of valid elements in elseStack
193: * @return The conditional this conditional was nested in, if any.
194: */
195: Conditional end(BCMethod mb, CodeChunk chunk, Type[] elseStack,
196: int stackNumber) {
197: int branch_pc;
198: if (thenGoto_pc == 0) {
199: // no else condition, make the conditional branch to the end
200: branch_pc = if_pc;
201: } else {
202: // otherwise make the goto branch to the end
203: branch_pc = thenGoto_pc;
204: }
205:
206: fillIn(mb, chunk, branch_pc, chunk.getPC());
207:
208: if (SanityManager.DEBUG) {
209: if (stackNumber != stack.length)
210: SanityManager
211: .THROWASSERT("ByteCode Conditional then/else stack depths differ then:"
212: + stack.length
213: + " else: "
214: + stackNumber);
215:
216: for (int i = 0; i < stackNumber; i++) {
217: if (!stack[i].vmName().equals(elseStack[i].vmName()))
218: SanityManager
219: .THROWASSERT("ByteCode Conditional then/else stack mismatch: then: "
220: + stack[i].vmName()
221: + " else: "
222: + elseStack[i].vmName());
223: }
224: }
225:
226: return parent;
227: }
228:
229: /**
230: * Fill in the offsets for a conditional or goto instruction that
231: * were dummied up as zero during code generation. Handles modifying
232: * branch logic when the offset for the branch is greater than can
233: * fit in 16 bits. In this case a GOTO_W with a 32 bit offset will
234: * be used, see details within the method for how this is acheived
235: * in all situations. This method might insert instructions in the
236: * already generated byte code, thus increasing the program counter.
237: *
238: * @param mb Method this conditional is for
239: * @param chunk Our code chunk
240: * @param branch_pc pc of the branch or goto opcode in the code stream
241: * @param target_pc pc where we want to jump to.
242: */
243: private void fillIn(BCMethod mb, CodeChunk chunk, int branch_pc,
244: int target_pc) {
245:
246: int offset = target_pc - branch_pc;
247:
248: // Following code assumes that this class only
249: // generates forward jumps. Jump of zero is
250: // wrong as well, would be infinite loop or stack problems.
251: if (SanityManager.DEBUG) {
252: if (offset <= 0)
253: SanityManager
254: .THROWASSERT("Conditional branch zero or negative "
255: + offset);
256: }
257:
258: // Original opcode written.
259: short branchOpcode = chunk.getOpcode(branch_pc);
260:
261: // Handle 16bit offsets, two byte.
262: if (offset <= BRANCH16LIMIT) {
263: // Code was already setup for two byte offsets,
264: // branch or goto instruction was written with
265: // offset zero, ready to be overwritten by this code.
266: CodeChunk mod = chunk.insertCodeSpace(branch_pc, 0);
267: mod.addInstrU2(branchOpcode, offset);
268: return;
269: }
270:
271: if (branchOpcode == VMOpcode.GOTO) {
272:
273: // The goto could be beyond the code length
274: // supported by the virtual machine: VMOpcode.MAX_CODE_LENGTH
275: // We allow this because later splits may bring the goto
276: // offset to within the required limits. If the goto
277: // still points outside the limits of the JVM then
278: // building the class will fail anyway since the code
279: // size will be too large. So no need to flag an error here.
280:
281: // Change the GOTO to a GOTO_W, which means
282: // inserting 2 bytes into the stream.
283: CodeChunk mod = chunk.insertCodeSpace(branch_pc, 2);
284:
285: // Offset we are jumping to is now two bytes futher away
286: offset += 2;
287:
288: // replace the original GOTO with a GOTO_W
289: mod.addInstrU4(VMOpcode.GOTO_W, offset);
290:
291: // Now need to patch up the original conditional
292: // as the else code it was branching to is now
293: // another two bytes away.
294: // There are three cases, given the original branch_offset:
295: //
296: // 1) branch_offset 16bit, branch_offset+2 16 bit
297: // 2) branch_offset 16bit, branch_offset+2 32 bit
298: // 3) branch_offset 32bit, branch_offset+2 32 bit
299: //
300: int startElse_pc = mod.getPC();
301:
302: int branchOffset = startElse_pc - if_pc;
303:
304: if (branchOffset <= BRANCH16LIMIT + 2) {
305: // case 1) branch_offset 16bit, branch_offset+2 16 bit
306: // case 2) branch_offset 16bit, branch_offset+2 32 bit
307: //
308: // Branch to the else code is on the original conditional
309:
310: // both handled by the standard fillIn method.
311: fillIn(mb, chunk, if_pc, mod.getPC());
312: return;
313:
314: }
315:
316: // branch to the else code was changed from the conditional
317: // to a GOTO_W as the branch was out of the range of the
318: // conditional.
319:
320: // Overwrite the offset of the existing GOTO_W, the instruction
321: // after the conditional instruction, which is three bytes long
322: mod = chunk.insertCodeSpace(if_pc + 3, 0);
323:
324: // Above branchOffset was calculated from the conditional
325: // but we need to branch from the GOTO_W that was inserted
326: // which is three bytes after the conditional.
327: branchOffset -= 3;
328:
329: mod.addInstrU4(VMOpcode.GOTO_W, branchOffset);
330: return;
331:
332: } else {
333: // Ensure the pc we are jumping to (the current pc)
334: // is within bounds of a valid method *after*
335: // we have added the extra bytes.
336: if ((target_pc + 5) >= VMOpcode.MAX_CODE_LENGTH) {
337: mb.cb.addLimitExceeded(mb, "branch_target",
338: VMOpcode.MAX_CODE_LENGTH, target_pc + 5);
339: // even if we fail continue to generate the correct code
340: // so that the assumptions in the patch up code are not broken.
341: }
342:
343: // Conditional branch
344: // branch on the conditional, need to add
345: // indirection. Basically changing
346: // (actual conditional might be different)
347: // Note branch inverting.
348: //
349: // IFNONNULL branch offset (to else code)
350: // <then code>
351: // GOTO end:
352: // <else code>
353: // end:
354: // to
355: //
356: // IFNULL branch +8 (to then code, 3 bytes in stream)
357: // GOTO_W offset* (to else code, 5 new bytes in stream)
358: // <then code>
359: // GOTO end:
360: // <else code>
361:
362: // Invert branch.
363: switch (branchOpcode) {
364: case VMOpcode.IFNONNULL:
365: branchOpcode = VMOpcode.IFNULL;
366: break;
367: case VMOpcode.IFEQ:
368: branchOpcode = VMOpcode.IFNE;
369: break;
370: default:
371: if (SanityManager.DEBUG)
372: SanityManager
373: .THROWASSERT("Conditional does not handle opcode "
374: + branchOpcode);
375:
376: }
377:
378: // Thus we need to insert 5 bytes
379: //
380: CodeChunk mod = chunk.insertCodeSpace(branch_pc, 5);
381:
382: // mod is positioned at the current branch.
383: mod.addInstrU2(branchOpcode, 8);
384:
385: // Indirect goto for the conditional else block or end.
386: // Offset was from the comparision instruction to the
387: // start of the real code. Now the branch location
388: // is an additional two bytes away, because this
389: // GOTO_W instruction occupies 5 bytes, and the original
390: // branch 3.
391: offset += 2;
392:
393: mod.addInstrU4(VMOpcode.GOTO_W, offset);
394:
395: return;
396: }
397: }
398:
399: }
|