Conditional


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