| 1 | /* |
| 2 | |
| 3 | Derby - Class org.apache.derby.impl.services.bytecode.Conditional |
| 4 | |
| 5 | Copyright 2000, 2006 The Apache Software Foundation or its licensors, as applicable. |
| 6 | |
| 7 | Licensed under the Apache License, Version 2.0 (the "License"); |
| 8 | you may not use this file except in compliance with the License. |
| 9 | You may obtain a copy of the License at |
| 10 | |
| 11 | http://www.apache.org/licenses/LICENSE-2.0 |
| 12 | |
| 13 | Unless required by applicable law or agreed to in writing, software |
| 14 | distributed under the License is distributed on an "AS IS" BASIS, |
| 15 | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 16 | See the License for the specific language governing permissions and |
| 17 | limitations under the License. |
| 18 | |
| 19 | */ |
| 20 | |
| 21 | package org.apache.derby.impl.services.bytecode; |
| 22 | import org.apache.derby.iapi.services.classfile.VMOpcode; |
| 23 | import org.apache.derby.iapi.services.sanity.SanityManager; |
| 24 | |
| 25 | /** |
| 26 | A Conditional represents an if/then/else block. |
| 27 | When this is created the code will already have |
| 28 | the conditional check code. The code is optimized for branch |
| 29 | offsets that fit in 2 bytes, though will handle 4 byte offsets. |
| 30 | <code> |
| 31 | if condition |
| 32 | then code |
| 33 | else code |
| 34 | </code> |
| 35 | what actually gets built is |
| 36 | <code> |
| 37 | if !condition branch to eb: |
| 38 | then code |
| 39 | goto end: // skip else |
| 40 | eb: |
| 41 | else code |
| 42 | end: |
| 43 | </code> |
| 44 | |
| 45 | If no else condition was provided then the code is: |
| 46 | |
| 47 | <code> |
| 48 | if !condition branch to end: |
| 49 | then code |
| 50 | end: |
| 51 | </code> |
| 52 | |
| 53 | Note all branches here are using relative offsets, not absolute program counters. |
| 54 | |
| 55 | If the then code leads to the conditional branch offset being too big (>32k) |
| 56 | because the then code is larger than 32767 bytes then this is built: |
| 57 | <code> |
| 58 | // when else code is present |
| 59 | if condition branch to tb: (relative offset +8) |
| 60 | goto_w eb: // indirect for else block (5 bytes) |
| 61 | tb: |
| 62 | then code (> 32767 bytes) |
| 63 | goto end: |
| 64 | eb: |
| 65 | else code |
| 66 | end: |
| 67 | </code> |
| 68 | |
| 69 | <code> |
| 70 | // when only then code is present |
| 71 | if condition branch to tb: (relative offset +8) |
| 72 | goto_w end: // indirect for else block (5 bytes) |
| 73 | tb: |
| 74 | then code (> 32767 bytes) |
| 75 | end: |
| 76 | </code> |
| 77 | |
| 78 | If there is an else branch and only it is larger than 32767 bytes then |
| 79 | the code is: |
| 80 | |
| 81 | <code> |
| 82 | if !condition branch to eb: (offset increased by two over previous value) |
| 83 | then code |
| 84 | goto_w end: // skip else |
| 85 | eb: |
| 86 | else code (> 32767 bytes) |
| 87 | end: |
| 88 | </code> |
| 89 | |
| 90 | This has one special case where the size of conditional branch to eb: |
| 91 | now must change from a 16bit value to a 32 bit value. The generated code |
| 92 | for this is the same as when both the then code and the else code require |
| 93 | 32bit offsets for the branches. This code is: |
| 94 | |
| 95 | <code> |
| 96 | if condition branch to tb: (relative offset +8) |
| 97 | goto_w eb: // indirect for else block (5 bytes) |
| 98 | tb: |
| 99 | then code (> 32767 bytes) |
| 100 | goto_w end: |
| 101 | eb: |
| 102 | else code (> 32767 bytes) |
| 103 | end: |
| 104 | </code> |
| 105 | |
| 106 | In theory, at the moment this should not happen as this would mean a total |
| 107 | code size that exceeds the limit on the code size for a method (64k). This |
| 108 | code handles this case as it does occur if the limit for a branch is lowered |
| 109 | for testing purposes, to ensure the complete set of branch re-write code works. |
| 110 | This lowering of the limit can be done by changing the constant BRANCH16LIMIT. |
| 111 | |
| 112 | */ |
| 113 | class Conditional { |
| 114 | |
| 115 | /** |
| 116 | * Limit of a 16 bit branch. |
| 117 | * <P> |
| 118 | * If broad testing of the switch from 16bit to 32bit |
| 119 | * offsets is required then this constant can be reduced |
| 120 | * to a lower value, say 50 and run complete tests. This |
| 121 | * will cover all the combinations. This works because the |
| 122 | * GOTO_W instruction works with any offset value. |
| 123 | */ |
| 124 | private static final int BRANCH16LIMIT = 32767; |
| 125 | |
| 126 | |
| 127 | private final Conditional parent; |
| 128 | /** |
| 129 | * pc of the 'if' opcode. |
| 130 | */ |
| 131 | private final int if_pc; |
| 132 | |
| 133 | private Type[] stack; |
| 134 | |
| 135 | /** |
| 136 | * pc of the GOTO added at the end of the then block |
| 137 | * to transfer control to the end of this conditional. |
| 138 | * That is at the end of the else block. |
| 139 | */ |
| 140 | private int thenGoto_pc; |
| 141 | |
| 142 | /** |
| 143 | * Start a conditional block. |
| 144 | * @param parent Current conditional block, null if no nesting is going on. |
| 145 | * @param chunk CodeChunk this conditional lives in |
| 146 | * @param ifOpcode Opcode for the if check. |
| 147 | * @param entryStack Type stack on entering the conditional then block. |
| 148 | */ |
| 149 | Conditional(Conditional parent, CodeChunk chunk, short ifOpcode, Type[] entryStack) { |
| 150 | this.parent = parent; |
| 151 | if_pc = chunk.getPC(); |
| 152 | this.stack = entryStack; |
| 153 | |
| 154 | // reserve the space for the branch, will overwrite later |
| 155 | // with the correct branch offset. |
| 156 | chunk.addInstrU2(ifOpcode, 0); |
| 157 | } |
| 158 | |
| 159 | /** |
| 160 | * Complete the 'then' block and start the 'else' block for this conditional |
| 161 | * @param chunk CodeChunk this conditional lives in |
| 162 | * @param thenStack Type stack on completing the conditional then block. |
| 163 | * @return the type stack on entering the then block |
| 164 | */ |
| 165 | Type[] startElse(BCMethod mb, CodeChunk chunk, Type[] thenStack) { |
| 166 | |
| 167 | // reserve space for the goto end we will be adding |
| 168 | chunk.addInstrU2(VMOpcode.GOTO, 0); |
| 169 | |
| 170 | // fill in the branch opcode to branch to |
| 171 | // the code after the goto, which is the current pc. |
| 172 | fillIn(mb, chunk, if_pc, chunk.getPC()); |
| 173 | |
| 174 | // Cannot use the pc before adding the GOTO above |
| 175 | // as the fillIn may insert bytes that move the GOTO, |
| 176 | // thus calculate at the end, and subtract the number of |
| 177 | // instructions in a goto to get its pc. |
| 178 | thenGoto_pc = chunk.getPC() - 3; |
| 179 | |
| 180 | Type[] entryStack = stack; |
| 181 | stack = thenStack; |
| 182 | |
| 183 | return entryStack; |
| 184 | } |
| 185 | |
| 186 | |
| 187 | /** |
| 188 | * Complete the conditional and patch up any jump instructions. |
| 189 | * @param chunk CodeChunk this conditional lives in |
| 190 | * @param elseStack Current stack, which is the stack at the end of the else |
| 191 | * @param stackNumber Current number of valid elements in elseStack |
| 192 | * @return The conditional this conditional was nested in, if any. |
| 193 | */ |
| 194 | Conditional end(BCMethod mb, CodeChunk chunk, Type[] elseStack, int stackNumber) { |
| 195 | int branch_pc; |
| 196 | if (thenGoto_pc == 0) { |
| 197 | // no else condition, make the conditional branch to the end |
| 198 | branch_pc = if_pc; |
| 199 | } else { |
| 200 | // otherwise make the goto branch to the end |
| 201 | branch_pc = thenGoto_pc; |
| 202 | } |
| 203 | |
| 204 | fillIn(mb, chunk, branch_pc, chunk.getPC()); |
| 205 | |
| 206 | if (SanityManager.DEBUG) |
| 207 | { |
| 208 | if (stackNumber != stack.length) |
| 209 | SanityManager.THROWASSERT("ByteCode Conditional then/else stack depths differ then:" |
| 210 | + stack.length + " else: " + stackNumber); |
| 211 | |
| 212 | for (int i = 0; i < stackNumber; i++) |
| 213 | { |
| 214 | if (!stack[i].vmName().equals(elseStack[i].vmName())) |
| 215 | SanityManager.THROWASSERT("ByteCode Conditional then/else stack mismatch: then: " |
| 216 | + stack[i].vmName() + |
| 217 | " else: " + elseStack[i].vmName()); |
| 218 | } |
| 219 | } |
| 220 | |
| 221 | return parent; |
| 222 | } |
| 223 | |
| 224 | /** |
| 225 | * Fill in the offsets for a conditional or goto instruction that |
| 226 | * were dummied up as zero during code generation. Handles modifying |
| 227 | * branch logic when the offset for the branch is greater than can |
| 228 | * fit in 16 bits. In this case a GOTO_W with a 32 bit offset will |
| 229 | * be used, see details within the method for how this is acheived |
| 230 | * in all situations. This method might insert instructions in the |
| 231 | * already generated byte code, thus increasing the program counter. |
| 232 | * |
| 233 | * @param mb Method this conditional is for |
| 234 | * @param chunk Our code chunk |
| 235 | * @param branch_pc pc of the branch or goto opcode in the code stream |
| 236 | * @param target_pc pc where we want to jump to. |
| 237 | */ |
| 238 | private void fillIn(BCMethod mb, CodeChunk chunk, |
| 239 | int branch_pc, int target_pc) { |
| 240 | |
| 241 | int offset = target_pc - branch_pc; |
| 242 | |
| 243 | // Following code assumes that this class only |
| 244 | // generates forward jumps. Jump of zero is |
| 245 | // wrong as well, would be infinite loop or stack problems. |
| 246 | if (SanityManager.DEBUG) |
| 247 | { |
| 248 | if (offset <= 0) |
| 249 | SanityManager.THROWASSERT("Conditional branch zero or negative " + offset); |
| 250 | } |
| 251 | |
| 252 | // Original opcode written. |
| 253 | short branchOpcode = chunk.getOpcode(branch_pc); |
| 254 | |
| 255 | // Handle 16bit offsets, two byte. |
| 256 | if (offset <= BRANCH16LIMIT) |
| 257 | { |
| 258 | // Code was already setup for two byte offsets, |
| 259 | // branch or goto instruction was written with |
| 260 | // offset zero, ready to be overwritten by this code. |
| 261 | CodeChunk mod = chunk.insertCodeSpace(branch_pc, 0); |
| 262 | mod.addInstrU2(branchOpcode, offset); |
| 263 | return; |
| 264 | } |
| 265 | |
| 266 | if (branchOpcode == VMOpcode.GOTO) |
| 267 | { |
| 268 | |
| 269 | // The goto could be beyond the code length |
| 270 | // supported by the virtual machine: VMOpcode.MAX_CODE_LENGTH |
| 271 | // We allow this because later splits may bring the goto |
| 272 | // offset to within the required limits. If the goto |
| 273 | // still points outside the limits of the JVM then |
| 274 | // building the class will fail anyway since the code |
| 275 | // size will be too large. So no need to flag an error here. |
| 276 | |
| 277 | // Change the GOTO to a GOTO_W, which means |
| 278 | // inserting 2 bytes into the stream. |
| 279 | CodeChunk mod = chunk.insertCodeSpace(branch_pc, 2); |
| 280 | |
| 281 | // Offset we are jumping to is now two bytes futher away |
| 282 | offset += 2; |
| 283 | |
| 284 | // replace the original GOTO with a GOTO_W |
| 285 | mod.addInstrU4(VMOpcode.GOTO_W, offset); |
| 286 | |
| 287 | // Now need to patch up the original conditional |
| 288 | // as the else code it was branching to is now |
| 289 | // another two bytes away. |
| 290 | // There are three cases, given the original branch_offset: |
| 291 | // |
| 292 | // 1) branch_offset 16bit, branch_offset+2 16 bit |
| 293 | // 2) branch_offset 16bit, branch_offset+2 32 bit |
| 294 | // 3) branch_offset 32bit, branch_offset+2 32 bit |
| 295 | // |
| 296 | int startElse_pc = mod.getPC(); |
| 297 | |
| 298 | int branchOffset = startElse_pc - if_pc; |
| 299 | |
| 300 | if (branchOffset <= BRANCH16LIMIT + 2) |
| 301 | { |
| 302 | // case 1) branch_offset 16bit, branch_offset+2 16 bit |
| 303 | // case 2) branch_offset 16bit, branch_offset+2 32 bit |
| 304 | // |
| 305 | // Branch to the else code is on the original conditional |
| 306 | |
| 307 | // both handled by the standard fillIn method. |
| 308 | fillIn(mb, chunk, if_pc, mod.getPC()); |
| 309 | return; |
| 310 | |
| 311 | } |
| 312 | |
| 313 | // branch to the else code was changed from the conditional |
| 314 | // to a GOTO_W as the branch was out of the range of the |
| 315 | // conditional. |
| 316 | |
| 317 | // Overwrite the offset of the existing GOTO_W, the instruction |
| 318 | // after the conditional instruction, which is three bytes long |
| 319 | mod = chunk.insertCodeSpace(if_pc + 3, 0); |
| 320 | |
| 321 | // Above branchOffset was calculated from the conditional |
| 322 | // but we need to branch from the GOTO_W that was inserted |
| 323 | // which is three bytes after the conditional. |
| 324 | branchOffset -= 3; |
| 325 | |
| 326 | mod.addInstrU4(VMOpcode.GOTO_W, branchOffset); |
| 327 | return; |
| 328 | |
| 329 | } |
| 330 | else |
| 331 | { |
| 332 | // Ensure the pc we are jumping to (the current pc) |
| 333 | // is within bounds of a valid method *after* |
| 334 | // we have added the extra bytes. |
| 335 | if ((target_pc + 5) >= VMOpcode.MAX_CODE_LENGTH) |
| 336 | { |
| 337 | mb.cb.addLimitExceeded(mb, |
| 338 | "branch_target", 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 | { |
| 365 | case VMOpcode.IFNONNULL: |
| 366 | branchOpcode = VMOpcode.IFNULL; |
| 367 | break; |
| 368 | case VMOpcode.IFEQ: |
| 369 | branchOpcode = VMOpcode.IFNE; |
| 370 | break; |
| 371 | default: |
| 372 | if (SanityManager.DEBUG) |
| 373 | SanityManager.THROWASSERT("Conditional does not handle opcode " + branchOpcode); |
| 374 | |
| 375 | } |
| 376 | |
| 377 | // Thus we need to insert 5 bytes |
| 378 | // |
| 379 | CodeChunk mod = chunk.insertCodeSpace(branch_pc, 5); |
| 380 | |
| 381 | // mod is positioned at the current branch. |
| 382 | mod.addInstrU2(branchOpcode, 8); |
| 383 | |
| 384 | // Indirect goto for the conditional else block or end. |
| 385 | // Offset was from the comparision instruction to the |
| 386 | // start of the real code. Now the branch location |
| 387 | // is an additional two bytes away, because this |
| 388 | // GOTO_W instruction occupies 5 bytes, and the original |
| 389 | // branch 3. |
| 390 | offset += 2; |
| 391 | |
| 392 | mod.addInstrU4(VMOpcode.GOTO_W, offset); |
| 393 | |
| 394 | return; |
| 395 | } |
| 396 | } |
| 397 | |
| 398 | |
| 399 | } |