You are viewing a plain text version of this content. The canonical link for it is here.
Posted to derby-commits@db.apache.org by km...@apache.org on 2007/11/02 01:18:33 UTC
svn commit: r591172 - in
/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/services/bytecode:
BCMethod.java CodeChunk.java
Author: kmarsden
Date: Thu Nov 1 17:18:32 2007
New Revision: 591172
URL: http://svn.apache.org/viewvc?rev=591172&view=rev
Log:
merges from trunk
DERBY-766 (partial) Move code in CodeChunk into a sub-method so that it can be shared (in a future commit) between the two ways of splitting a large method into sub-methods.
merge 430306 to 10.1 from trunk
DERBY-766 (partial) Clean up the existing split methods to avoid confusion over a code length passed in. Now length of the method's code is determined inside the methods rather than being passed around.
merge 430522 to 10.1 from trunk
DERBY-766 (partial) Almost working code in CodeChunk that splits expressions out from a method into a sub-method for generated code. Increased the number of unions supported in the largeCodeGen test from ~800 to ~1300. Code not yet enabled as some unexpected errors exist at 1400 unions, leading to a ClassCastException. Committing as a checkpoint, the actual split call from BCMethod is commented
out to avoid any problems running it.
merge 431474 to 10.1 from trunk
Modified:
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/services/bytecode/BCMethod.java
db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/services/bytecode/CodeChunk.java
Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/services/bytecode/BCMethod.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/services/bytecode/BCMethod.java?rev=591172&r1=591171&r2=591172&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/services/bytecode/BCMethod.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/services/bytecode/BCMethod.java Thu Nov 1 17:18:32 2007
@@ -76,7 +76,7 @@
final BCClass cb;
protected final ClassHolder modClass; // the class it is in (modifiable fmt)
- private final String myReturnType;
+ final String myReturnType;
/**
* The original name of the method, this
@@ -259,6 +259,7 @@
private void splitMethod() {
int split_pc = 0;
+ boolean splittingZeroStack = true;
for (int codeLength = myCode.getPC();
(cb.limitMsg == null) &&
(codeLength > CODE_SPLIT_LENGTH);
@@ -279,19 +280,36 @@
if (optimalMinLength > lengthToCheck)
optimalMinLength = lengthToCheck;
- split_pc = myCode.splitZeroStack(this, modClass, split_pc,
- lengthToCheck, optimalMinLength);
+ if (splittingZeroStack)
+ {
+ split_pc = myCode.splitZeroStack(this, modClass, split_pc,
+ optimalMinLength);
+ }
+ else
+ {
+ //TODO: re-start split at point left off
+ //split_pc = myCode.splitExpressionOut(this, modClass,
+ // optimalMinLength, maxStack);
+
+ // DERBY-766 temp - don't call the split method yet.
+ split_pc = -1;
+ }
// Negative split point returned means that no split
// was possible. Give up on this approach and goto
- // the next approach (none-yet).
+ // the next approach.
if (split_pc < 0) {
- break;
+ if (!splittingZeroStack)
+ break;
+ splittingZeroStack = false;
+ split_pc = 0;
}
// success, continue on splitting after the call to the
// sub-method if the method still execeeds the maximum length.
}
+
+
}
/*
Modified: db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/services/bytecode/CodeChunk.java
URL: http://svn.apache.org/viewvc/db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/services/bytecode/CodeChunk.java?rev=591172&r1=591171&r2=591172&view=diff
==============================================================================
--- db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/services/bytecode/CodeChunk.java (original)
+++ db/derby/code/branches/10.1/java/engine/org/apache/derby/impl/services/bytecode/CodeChunk.java Thu Nov 1 17:18:32 2007
@@ -830,7 +830,7 @@
byte[] codeBytes = cout.getData();
int u2p = CODE_OFFSET + pc + 1;
-
+
return ((codeBytes[u2p] & 0xff) << 8) | (codeBytes[u2p+1] & 0xff);
}
@@ -939,7 +939,7 @@
*/
private int findMaxStack(ClassHolder ch, int pc, int codeLength) {
- int endPc = pc + codeLength;
+ final int endPc = pc + codeLength;
int stack = 0;
int maxStack = 0;
@@ -955,7 +955,7 @@
maxStack = stack;
int[] cond_pcs = findConditionalPCs(pc, opcode);
- if (cond_pcs != null) {
+ if (cond_pcs != null) {
// an else block exists.
if (cond_pcs[3] != -1) {
int blockMaxStack = findMaxStack(ch, cond_pcs[1],
@@ -1278,11 +1278,10 @@
*
* @param mb Method for this chunk.
* @param ch Class definition
- * @param codeLength codeLength to check
* @param optimalMinLength minimum length required for split
*/
final int splitZeroStack(BCMethod mb, ClassHolder ch, final int split_pc,
- final int codeLength, final int optimalMinLength) {
+ final int optimalMinLength) {
int stack = 0;
// maximum possible split seen that is less than
@@ -1294,7 +1293,7 @@
// a conditional.
int outerConditionalEnd_pc = -1;
- int end_pc = split_pc + codeLength;
+ int end_pc = getPC(); // pc will be positioned at the end.
for (int pc = split_pc; pc < end_pc;) {
short opcode = getOpcode(pc);
@@ -1389,28 +1388,8 @@
BCMethod subMethod = startSubMethod(mb, "void", split_pc,
splitLength);
- CodeChunk subChunk = subMethod.myCode;
-
- byte[] codeBytes = cout.getData();
-
- // the code to be moved into the sub method
- // as a block. This will correctly increase the
- // program counter.
- try {
- subChunk.cout.write(codeBytes, CODE_OFFSET + split_pc,
- splitLength);
- } catch (IOException ioe) {
- limitHit(ioe);
- }
-
- // Just cause the sub-method to return,
- // fix up its maxStack and then complete it.
- subChunk.addInstr(VMOpcode.RETURN);
- subMethod.maxStack = subChunk.findMaxStack(ch, 0, subChunk.getPC());
- subMethod.complete();
-
- return removePushedCode(mb, ch, subMethod, split_pc, splitLength,
- codeLength);
+ return splitCodeIntoSubMethod(mb, ch, subMethod,
+ split_pc, splitLength);
}
return -1;
}
@@ -1424,9 +1403,9 @@
* uses parameters.
*/
private BCMethod startSubMethod(BCMethod mb, String returnType,
- int split_pc, int codeLength) {
+ int split_pc, int blockLength) {
- boolean needParameters = usesParameters(mb, split_pc, codeLength);
+ boolean needParameters = usesParameters(mb, split_pc, blockLength);
return mb.getNewSubMethod(returnType, needParameters);
}
@@ -1497,10 +1476,9 @@
}
return false;
}
-
/**
- * Remove a block of code from this method that was
- * pushed into a sub-method and call the sub-method.
+ * Split a block of code from this method into a sub-method
+ * and call it.
*
* Returns the pc of this method just after the call
* to the sub-method.
@@ -1510,19 +1488,74 @@
* @param subMethod Sub-method code was pushed into
* @param split_pc Program counter the split started at
* @param splitLength Length of code split
- * @param codeLength Length of code before split
+ */
+ private int splitCodeIntoSubMethod(BCMethod mb, ClassHolder ch,
+ BCMethod subMethod, final int split_pc, final int splitLength) {
+ CodeChunk subChunk = subMethod.myCode;
+
+ byte[] codeBytes = cout.getData();
+
+ // the code to be moved into the sub method
+ // as a block. This will correctly increase the
+ // program counter.
+ try {
+ subChunk.cout.write(codeBytes, CODE_OFFSET + split_pc, splitLength);
+ } catch (IOException ioe) {
+ limitHit(ioe);
+ }
+
+ // Just cause the sub-method to return,
+ // fix up its maxStack and then complete it.
+ if (subMethod.myReturnType.equals("void"))
+ subChunk.addInstr(VMOpcode.RETURN);
+ else
+ subChunk.addInstr(VMOpcode.ARETURN);
+
+ // Finding the max stack requires the class format to
+ // still be valid. If we have blown the number of constant
+ // pool entries then we can no longer guarantee that indexes
+ // into the constant pool in the code stream are valid.
+ if (cb.limitMsg != null)
+ return -1;
+
+ subMethod.maxStack = subChunk.findMaxStack(ch, 0, subChunk.getPC());
+ subMethod.complete();
+
+ return removePushedCode(mb, ch, subMethod, split_pc, splitLength);
+ }
+
+ /**
+ * Remove a block of code from this method that was pushed into a sub-method
+ * and call the sub-method.
+ *
+ * Returns the pc of this method just after the call to the sub-method.
+ *
+ * @param mb
+ * My method
+ * @param ch
+ * My class
+ * @param subMethod
+ * Sub-method code was pushed into
+ * @param split_pc
+ * Program counter the split started at
+ * @param splitLength
+ * Length of code split
*/
private int removePushedCode(BCMethod mb, ClassHolder ch,
- BCMethod subMethod, int split_pc, int splitLength, int codeLength) {
+ BCMethod subMethod, final int split_pc, final int splitLength) {
// now need to fix up this method, create
// a new CodeChunk just to be clearer than
// trying to modify this chunk directly.
+
+ // total length of the code for this method before split
+ final int codeLength = getPC();
+
CodeChunk replaceChunk = new CodeChunk(mb.cb);
mb.myCode = replaceChunk;
mb.maxStack = 0;
byte[] codeBytes = cout.getData();
-
+
// write any existing code before the split point
// into the replacement chunk.
if (split_pc != 0) {
@@ -1540,10 +1573,12 @@
// Write the code remaining in this method into the replacement chunk
- int remainingCodeLength = codeLength - splitLength;
- try {
- replaceChunk.cout.write(codeBytes, CODE_OFFSET + split_pc
- + splitLength, remainingCodeLength);
+ int remainingCodePC = split_pc + splitLength;
+ int remainingCodeLength = codeLength - splitLength - split_pc;
+
+ try {
+ replaceChunk.cout.write(codeBytes, CODE_OFFSET + remainingCodePC,
+ remainingCodeLength);
} catch (IOException ioe) {
limitHit(ioe);
}
@@ -1554,7 +1589,7 @@
// into the constant pool in the code stream are valid.
if (cb.limitMsg != null)
return -1;
-
+
mb.maxStack = replaceChunk.findMaxStack(ch, 0, replaceChunk.getPC());
return postSplit_pc;
@@ -1616,8 +1651,8 @@
* <LI> N + 1 - method returning a single word
* <LI> N + 2 - method returning a double word (java long or double)
* </UL>
- * This code will handle the N+1 and N+2 cases, the typical
- * ones for generated code.
+ * This code will handle the N+1 where the word is a reference,
+ * the typical case for generated code.
* <BR>
* The code is self contained because in general the byte code
* for the arguments will push and pop values but never drop
@@ -1640,39 +1675,28 @@
* push3 this swap invoke
* </code>
* In this case the byte code for arg1 (swap) is not self-contained
- * and relies on earlier stack values. The set of instructions
- * that break the self-containment are limited and thus can be
- * checked for easily.
+ * and relies on earlier stack values.
* <P>
* How to identify "self-contained blocks of code".
* <BR>
* We walk through the byte code and maintain a history of
- * the program counter when the stack changed. If a word
- * was pushed by an opcode that does not depend on previous
- * stack values the current program counter is recorded
- * otherwise -1 is set to indicate stack value may depend
- * on previous stack values.
- * <code>
- * pcDepth[N] = 45
- * pcDepth[N+1] = -1
- * pcDepth[N+2] = 52
- * </code>
- * <BR>
- * The pcDepth represents a program counter that caused
- * the stack to reach that depth and is independent of
- * previous stack entries. Initially a very limited
- * number of opcodes are supported as independent.
+ * the program counter that indicates the start of the
+ * independent sequence each stack word depends on.
+ * Thus for a ALOAD_0 instruction which pushes 'this' the
+ * dependent pc is that of the this. If a DUP instruction followed
+ * then the top-word is now dependent on the previous word (this)
+ * and thus the dependence of it is equal to the dependence of
+ * the previous word. This information is kept in earliestIndepPC
+ * array as we process the instruction stream.
* <BR>
- * If the instruction that caused the stack decrease
- * is an invoke byte code that matches what we are looking for
- * then a determination begins as to if its calling sequence
- * is self-contained and should it be split out into a sub-method.
- * The information with the instruction allows us to find
- * the stack-depth corresponding to the instance for the call.
- * The depth, from the pcDepth array allows us to find the
- * pc and instruction that pushed the instance. It can then be
- * determined the code to generate the instance is this
- * or this.getter().
+ * When a INVOKE instruction is seen for an instance method
+ * that returns a single or double word, the dependence of
+ * the returned value is the dependence of the word in the
+ * stack that is the objectref for the call. This complete
+ * sequence from the pc the objectref depended on to the
+ * INVOKE instruction is then a self contained sequence
+ * and can be split into a sub-method.
+
* <BR>
* If the block is self-contained then it can be split, following
* similar logic to splitZeroStack().
@@ -1680,23 +1704,54 @@
* <P>
* WORK IN PROGRESS - Incremental development
* <BR>
- * Currently just walks the method maintaining the
- * pcByDepth array and identifies potential blocks
- * to splt. Does not perform any split.
- * Not called by submitted code. Tested with local
- * changes from calls in BCMethod.
+ * Currently walks the method maintaining the
+ * earliestIndepPC array and identifies potential blocks
+ * to splt, performs splits as required.
+ * Called by BCMethod but commented out in submitted code.
+ * Tested with local changes from calls in BCMethod.
+ * Splits generally work, though largeCodeGen shows
+ * a problem that will be fixed before the code in
+ * enabled for real.
*
*/
+
final int splitExpressionOut(BCMethod mb, ClassHolder ch,
- final int codeLength, final int optimalMinLength,
+ final int optimalMinLength,
int maxStack)
{
- // program counter for the instruction that
- // made the stack reach the given stack depth.
- int[] pcByDepth = new int[maxStack+1];
- Arrays.fill(pcByDepth, -1);
- pcByDepth[0] = 0;
+ // Save the best block we have seen for splitting out.
+ int bestSplitPC = -1;
+ int bestSplitBlockLength = -1;
+ String bestSplitRT = null;
+ // Program counter of the earliest instruction
+ // that the word in the current active stack
+ // at the given depth depends on.
+ //
+ // Some examples, N is the stack depth *after*
+ // the instruction.
+ // E.g.
+ // ALOAD_0 - pushes this, is an instruction that
+ // pushes an independent value, so the current
+ // stack word depends on the pc of current instruction.
+ // earliestIndepPC[N] = pc (that pushed the value).
+ //
+ // DUP - duplicates the top word, so the duplicated
+ // top word will depend on the same pc as the word
+ // it was duplicated from.
+ // I.e. earliestIndepPC[N]
+ // = earliestIndepPC[N-1];
+ //
+ // instance method call returning single word value.
+ // The top word will depend on the same pc as the
+ // objectref for the method call, which was at the
+ // same depth in this case.
+ // earliestIndepPC[N] unchanged
+ //
+ // at any time earliestIndepPC is only valid
+ // from 1 to N where N is the depth of the stack.
+ int[] earliestIndepPC = new int[maxStack+1];
+
int stack = 0;
//TODO: this conditional handling is copied from
@@ -1707,11 +1762,12 @@
// a conditional.
int outerConditionalEnd_pc = -1;
- int end_pc = 0 + codeLength;
+ int end_pc = getPC();
+
for (int pc = 0; pc < end_pc;) {
short opcode = getOpcode(pc);
-
+
int stackDelta = stackWordDelta(ch, pc, opcode);
stack += stackDelta;
@@ -1753,37 +1809,94 @@
}
continue;
}
-
- // Set up independent points.
- //
- // Code in this switch either
- // 1) 'break's out not changing anything
- // to indicate the instruction left the
- // stack in such that its independence
- // at the current stack level is left unchanged.
- //
- // 2) Marks the opcode_pc as the independent
- // start point for the current stack depth.
- //
- // 3) marks the current stack depth as not
- // having an independent start point. In some cases
- // that may be a false assertion as it's a fail safe
- // system. Only a small defined set of instructions
- // are handled as valid starting points. More development
- // and thought can be put into handling more cases as required.
- // The 'this' ALOAD_0 instruction will cover most cases.
int opcode_pc = pc - instructionLength(opcode);
switch (opcode)
{
- // Independent instructions that do not modify the stack
- case VMOpcode.NOP:
+ // Any instruction we don't have any information
+ // on, we simply clear all evidence of independent
+ // starting points, and start again.
+ default:
+ Arrays.fill(earliestIndepPC,
+ 0, stack + 1, -1);
+ break;
+
+ // Independent instructions do not change the stack depth
+ // and the independence of the top word picks up
+ // the independence of the previous word at the same
+ // position. Ie. no change!
+ case VMOpcode.ARRAYLENGTH:
+ case VMOpcode.NOP:
+ case VMOpcode.CHECKCAST:
+ case VMOpcode.D2L:
+ case VMOpcode.DNEG:
+ case VMOpcode.F2I:
break;
- // Independent instructions that push one value
- case VMOpcode.ALOAD_0: // push 'this'
- pcByDepth[stack] = opcode_pc;
+ // Independent instructions that push one word
+ case VMOpcode.ALOAD_0:
+ case VMOpcode.ALOAD_1:
+ case VMOpcode.ALOAD_2:
+ case VMOpcode.ALOAD_3:
+ case VMOpcode.ALOAD:
+ case VMOpcode.ACONST_NULL:
+ case VMOpcode.BIPUSH:
+ case VMOpcode.FCONST_0:
+ case VMOpcode.FCONST_1:
+ case VMOpcode.FCONST_2:
+ case VMOpcode.FLOAD:
+ case VMOpcode.ICONST_0:
+ case VMOpcode.ICONST_1:
+ case VMOpcode.ICONST_2:
+ case VMOpcode.ICONST_3:
+ case VMOpcode.ICONST_4:
+ case VMOpcode.ICONST_5:
+ case VMOpcode.ICONST_M1:
+ case VMOpcode.LDC:
+ case VMOpcode.LDC_W:
+ case VMOpcode.SIPUSH:
+ earliestIndepPC[stack] = opcode_pc;
break;
+
+ // Independent instructions that push two words
+ case VMOpcode.DCONST_0:
+ case VMOpcode.DCONST_1:
+ case VMOpcode.LCONST_0:
+ case VMOpcode.LCONST_1:
+ case VMOpcode.LDC2_W:
+ case VMOpcode.LLOAD:
+ case VMOpcode.LLOAD_0:
+ case VMOpcode.LLOAD_1:
+ case VMOpcode.LLOAD_2:
+ case VMOpcode.LLOAD_3:
+ earliestIndepPC[stack - 1] =
+ earliestIndepPC[stack] = opcode_pc;
+ break;
+
+ // nothing to do for pop, obviously no
+ // code will be dependent on the popped words.
+ case VMOpcode.POP:
+ case VMOpcode.POP2:
+ break;
+
+ case VMOpcode.SWAP:
+ earliestIndepPC[stack] = earliestIndepPC[stack -1];
+ break;
+
+ // push a value that depends on the previous value
+ case VMOpcode.I2L:
+ earliestIndepPC[stack] = earliestIndepPC[stack -1];
+ break;
+
+ case VMOpcode.GETFIELD:
+ {
+ String vmDescriptor = getTypeDescriptor(ch, opcode_pc);
+ int width = CodeChunk.getDescriptorWordCount(vmDescriptor);
+ if (width == 2)
+ earliestIndepPC[stack] = earliestIndepPC[stack -1];
+
+ break;
+ }
case VMOpcode.INVOKEINTERFACE:
case VMOpcode.INVOKEVIRTUAL:
@@ -1797,85 +1910,89 @@
// Width of the value returned by the method call.
String vmDescriptor = getTypeDescriptor(ch, opcode_pc);
int width = CodeChunk.getDescriptorWordCount(vmDescriptor);
-
- // Need to determine the pc of the
- // instruction that pushed the objectref
- // for the method call. Three cases depending
- // on the return type:
- // 1) void method
- // pcDepth[stack + 1]
- // 2) returns single word
- // pcDepth[stack]
- // 3) returns double word
- // pcDepth[stack - 1]
- // Special case of zero arguments
- // and returning an single word value.
- // In this case most likely the code
- // block to the objectref is not
- // worth splitting, but it also
- // does not affect the independence
- // of the current stack depth.
- // If the objectref was independent
- // then the current stack value will
- // be. This is looking
- // for the case of this.getXXXFactory().
- //
- //
- // objectref is popped and single word
- // value pushed by method call, so
- // stackDelta must be zero.
- if (stackDelta == 0 && width == 1)
+ // Independence of this block is the independence
+ // of the objectref that invokved the method.
+ int selfContainedBlockStart;
+ if (width == 0)
{
- break;
+ // objectref was at one more than the current depth
+ selfContainedBlockStart =
+ earliestIndepPC[stack + 1];
}
+ else if (width == 1)
+ {
+ // stack is unchanged, objectref was at
+ // the current stack depth
+ selfContainedBlockStart = earliestIndepPC[stack];
+ }
+ else
+ {
+ // width == 2, objectref was one below the
+ // current stack depth.
+ selfContainedBlockStart = earliestIndepPC[stack] =
+ earliestIndepPC[stack - 1];
+ }
- int stackDepthForObjectref = stack + (1 - width);
-
- // Look for an starting point that is independent
- // starting at the objectref and working backwards
- // in the code by looking for program counters
- // that pushed an independent value.
- int selfContainedBlockStart = -1;
- for (int sd = stackDepthForObjectref; sd >= 0; sd--)
+ if (selfContainedBlockStart != -1)
{
- int pcStart = pcByDepth[sd];
-
- // not a independent value
- if (pcStart == -1)
- continue;
-
- // found a suitable block if
- if ((pc - pcStart) >= optimalMinLength)
- {
- selfContainedBlockStart = pcStart;
- break;
- }
+ int blockLength = pc - selfContainedBlockStart;
+
+ // Only split for a method that returns
+ // an class reference.
+ int me = vmDescriptor.lastIndexOf(')');
+
+ if (vmDescriptor.charAt(me+1) == 'L')
+ {
+ String rt = vmDescriptor.substring(me + 2,
+ vmDescriptor.length() - 1);
+
+ if (blockLength > (VMOpcode.MAX_CODE_LENGTH - 1))
+ {
+ // too big to split into a single method
+ // (one for the return opcode)
+ }
+ else if (blockLength >= optimalMinLength)
+ {
+ // Split now!
+ System.out.println("NOW " + blockLength
+ + " @ " + selfContainedBlockStart);
+ BCMethod subMethod = startSubMethod(mb,
+ rt, selfContainedBlockStart,
+ blockLength);
+
+ return splitCodeIntoSubMethod(mb, ch, subMethod,
+ selfContainedBlockStart, blockLength);
+ }
+ else if (blockLength > bestSplitBlockLength)
+ {
+ // Save it, may split at this point
+ // if nothing better seen.
+ bestSplitPC = selfContainedBlockStart;
+ bestSplitBlockLength = blockLength;
+ bestSplitRT = rt;
+ }
+ }
}
-
- // Did we find an independent starting pc
- if (selfContainedBlockStart != -1)
- {
- // TODO: actual extract & split
- return -1;
- }
- pcByDepth[stack] = -1;
- if (width == 2)
- pcByDepth[stack - 1] = -1;
break;
}
- //TODO: work on splits.
- default:
- // assume the instruction is not independent
- // (fail-safe)
- pcByDepth[stack] = -1;
- // account for opcodes pushing longs/doubles.
- if (stackDelta == 2)
- pcByDepth[stack - 1] = -1;
- break;
- }
+ }
+
}
+
+ if (bestSplitBlockLength > 100)
+ {
+ System.out.println("BEST " + bestSplitBlockLength
+ + " @ " + bestSplitPC);
+ BCMethod subMethod = startSubMethod(mb,
+ bestSplitRT, bestSplitPC,
+ bestSplitBlockLength);
+
+ return splitCodeIntoSubMethod(mb, ch, subMethod,
+ bestSplitBlockLength, bestSplitBlockLength);
+ }
+
return -1;
}