Mercurial > hg > truffle
changeset 13294:29907e69ae8d
rework of switch generation: move code into platform independent SwitchStrategy, add boolean switch strategy
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64LIRGenerator.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.compiler.amd64/src/com/oracle/graal/compiler/amd64/AMD64LIRGenerator.java Wed Dec 11 15:59:40 2013 +0100 @@ -55,8 +55,7 @@ import com.oracle.graal.lir.amd64.AMD64ControlFlow.FloatBranchOp; import com.oracle.graal.lir.amd64.AMD64ControlFlow.FloatCondMoveOp; import com.oracle.graal.lir.amd64.AMD64ControlFlow.ReturnOp; -import com.oracle.graal.lir.amd64.AMD64ControlFlow.SequentialSwitchOp; -import com.oracle.graal.lir.amd64.AMD64ControlFlow.SwitchRangesOp; +import com.oracle.graal.lir.amd64.AMD64ControlFlow.StrategySwitchOp; import com.oracle.graal.lir.amd64.AMD64ControlFlow.TableSwitchOp; import com.oracle.graal.lir.amd64.AMD64Move.LeaOp; import com.oracle.graal.lir.amd64.AMD64Move.MembarOp; @@ -220,6 +219,7 @@ @Override public void emitJump(LabelRef label) { + assert label != null; append(new JumpOp(label)); } @@ -980,20 +980,9 @@ } @Override - protected void emitSequentialSwitch(Constant[] keyConstants, LabelRef[] keyTargets, LabelRef defaultTarget, Value key) { - // Making a copy of the switch value is necessary because jump table destroys the input - // value - if (key.getKind() == Kind.Int || key.getKind() == Kind.Long) { - append(new SequentialSwitchOp(keyConstants, keyTargets, defaultTarget, key, Value.ILLEGAL)); - } else { - assert key.getKind() == Kind.Object : key.getKind(); - append(new SequentialSwitchOp(keyConstants, keyTargets, defaultTarget, key, newVariable(Kind.Object))); - } - } - - @Override - protected void emitSwitchRanges(int[] lowKeys, int[] highKeys, LabelRef[] targets, LabelRef defaultTarget, Value key) { - append(new SwitchRangesOp(lowKeys, highKeys, targets, defaultTarget, key)); + protected void emitStrategySwitch(SwitchStrategy strategy, Variable key, LabelRef[] keyTargets, LabelRef defaultTarget) { + boolean needsTemp = key.getKind() == Kind.Object; + append(new StrategySwitchOp(strategy, keyTargets, defaultTarget, key, needsTemp ? newVariable(key.getKind()) : Value.ILLEGAL)); } @Override
--- a/graal/com.oracle.graal.compiler.hsail/src/com/oracle/graal/compiler/hsail/HSAILLIRGenerator.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.compiler.hsail/src/com/oracle/graal/compiler/hsail/HSAILLIRGenerator.java Wed Dec 11 15:59:40 2013 +0100 @@ -46,14 +46,13 @@ import com.oracle.graal.lir.hsail.HSAILControlFlow.CondMoveOp; import com.oracle.graal.lir.hsail.HSAILControlFlow.FloatCondMoveOp; import com.oracle.graal.lir.hsail.HSAILControlFlow.ReturnOp; -import com.oracle.graal.lir.hsail.HSAILControlFlow.SwitchOp; +import com.oracle.graal.lir.hsail.HSAILControlFlow.StrategySwitchOp; import com.oracle.graal.lir.hsail.HSAILMove.LeaOp; import com.oracle.graal.lir.hsail.HSAILMove.MembarOp; import com.oracle.graal.lir.hsail.HSAILMove.MoveFromRegOp; import com.oracle.graal.lir.hsail.HSAILMove.MoveToRegOp; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; -import com.oracle.graal.nodes.extended.*; import com.oracle.graal.phases.util.*; /** @@ -702,17 +701,10 @@ * * Note: Only IntegerSwitchNodes are currently supported. The IntegerSwitchNode is the node that * Graal generates for any switch construct appearing in Java bytecode. - * - * @param x the SwitchNode */ @Override - public void emitSwitch(SwitchNode x) { - // get the key of the switch. - Variable key = load(operand(x.value())); - // set the default target. - LabelRef defaultTarget = x.defaultSuccessor() == null ? null : getLIRBlock(x.defaultSuccessor()); - // emit a sequential switch for the specified key and default target. - emitSequentialSwitch(x, key, defaultTarget); + protected void emitStrategySwitch(Constant[] keyConstants, double[] keyProbabilities, LabelRef[] keyTargets, LabelRef defaultTarget, Variable value) { + emitStrategySwitch(new SwitchStrategy.SequentialStrategy(keyProbabilities, keyConstants), value, keyTargets, defaultTarget); } /** @@ -727,19 +719,19 @@ * handling operations related to method dispatch. We haven't yet added support for the * TypeSwitchNode, so for the time being we have added a check to ensure that the keys are of * type int. This also allows us to flag any test cases/execution paths that may trigger the - * creation fo a TypeSwitchNode which we don't support yet. + * creation of a TypeSwitchNode which we don't support yet. * * - * @param keyConstants array of key constants used for the case statements. + * @param strategy the strategy used for this switch. * @param keyTargets array of branch targets for each of the cases. * @param defaultTarget the branch target for the default case. * @param key the key that is compared against the key constants in the case statements. */ @Override - protected void emitSequentialSwitch(Constant[] keyConstants, LabelRef[] keyTargets, LabelRef defaultTarget, Value key) { + protected void emitStrategySwitch(SwitchStrategy strategy, Variable key, LabelRef[] keyTargets, LabelRef defaultTarget) { if (key.getKind() == Kind.Int) { // Append the LIR instruction for generating compare and branch instructions. - append(new SwitchOp(keyConstants, keyTargets, defaultTarget, key)); + append(new StrategySwitchOp(strategy, keyTargets, defaultTarget, key)); } else { // Throw an exception if the keys aren't ints. throw GraalInternalError.unimplemented("Switch statements are only supported for keys of type int"); @@ -747,11 +739,6 @@ } @Override - protected void emitSwitchRanges(int[] lowKeys, int[] highKeys, LabelRef[] targets, LabelRef defaultTarget, Value key) { - throw GraalInternalError.unimplemented(); - } - - @Override protected void emitTableSwitch(int lowKey, LabelRef defaultTarget, LabelRef[] targets, Value key) { throw GraalInternalError.unimplemented(); }
--- a/graal/com.oracle.graal.compiler.ptx/src/com/oracle/graal/compiler/ptx/PTXLIRGenerator.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.compiler.ptx/src/com/oracle/graal/compiler/ptx/PTXLIRGenerator.java Wed Dec 11 15:59:40 2013 +0100 @@ -51,7 +51,7 @@ import com.oracle.graal.lir.ptx.PTXControlFlow.FloatCondMoveOp; import com.oracle.graal.lir.ptx.PTXControlFlow.ReturnNoValOp; import com.oracle.graal.lir.ptx.PTXControlFlow.ReturnOp; -import com.oracle.graal.lir.ptx.PTXControlFlow.SequentialSwitchOp; +import com.oracle.graal.lir.ptx.PTXControlFlow.StrategySwitchOp; import com.oracle.graal.lir.ptx.PTXControlFlow.TableSwitchOp; import com.oracle.graal.lir.ptx.PTXMemOp.LoadOp; import com.oracle.graal.lir.ptx.PTXMemOp.LoadParamOp; @@ -788,20 +788,9 @@ } @Override - protected void emitSequentialSwitch(Constant[] keyConstants, LabelRef[] keyTargets, LabelRef defaultTarget, Value key) { - // Making a copy of the switch value is necessary because jump table destroys the input - // value - if (key.getKind() == Kind.Int || key.getKind() == Kind.Long) { - append(new SequentialSwitchOp(keyConstants, keyTargets, defaultTarget, key, Value.ILLEGAL, nextPredRegNum++)); - } else { - assert key.getKind() == Kind.Object : key.getKind(); - append(new SequentialSwitchOp(keyConstants, keyTargets, defaultTarget, key, newVariable(Kind.Object), nextPredRegNum++)); - } - } - - @Override - protected void emitSwitchRanges(int[] lowKeys, int[] highKeys, LabelRef[] targets, LabelRef defaultTarget, Value key) { - throw new InternalError("NYI"); + protected void emitStrategySwitch(SwitchStrategy strategy, Variable key, LabelRef[] keyTargets, LabelRef defaultTarget) { + boolean needsTemp = key.getKind() == Kind.Object; + append(new StrategySwitchOp(strategy, keyTargets, defaultTarget, key, needsTemp ? newVariable(key.getKind()) : Value.ILLEGAL, nextPredRegNum++)); } @Override
--- a/graal/com.oracle.graal.compiler.sparc/src/com/oracle/graal/compiler/sparc/SPARCLIRGenerator.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.compiler.sparc/src/com/oracle/graal/compiler/sparc/SPARCLIRGenerator.java Wed Dec 11 15:59:40 2013 +0100 @@ -50,8 +50,7 @@ import com.oracle.graal.lir.sparc.SPARCControlFlow.CondMoveOp; import com.oracle.graal.lir.sparc.SPARCControlFlow.FloatCondMoveOp; import com.oracle.graal.lir.sparc.SPARCControlFlow.ReturnOp; -import com.oracle.graal.lir.sparc.SPARCControlFlow.SequentialSwitchOp; -import com.oracle.graal.lir.sparc.SPARCControlFlow.SwitchRangesOp; +import com.oracle.graal.lir.sparc.SPARCControlFlow.StrategySwitchOp; import com.oracle.graal.lir.sparc.SPARCControlFlow.TableSwitchOp; import com.oracle.graal.lir.sparc.SPARCMove.LoadAddressOp; import com.oracle.graal.lir.sparc.SPARCMove.MembarOp; @@ -359,16 +358,9 @@ } @Override - protected void emitSequentialSwitch(Constant[] keyConstants, LabelRef[] keyTargets, LabelRef defaultTarget, Value key) { - // Making a copy of the switch value is necessary because jump table destroys the input - // value - assert key.getKind() == Kind.Int || key.getKind() == Kind.Long || key.getKind() == Kind.Object : key.getKind(); - append(new SequentialSwitchOp(keyConstants, keyTargets, defaultTarget, key, newVariable(key.getKind()))); - } - - @Override - protected void emitSwitchRanges(int[] lowKeys, int[] highKeys, LabelRef[] targets, LabelRef defaultTarget, Value key) { - append(new SwitchRangesOp(lowKeys, highKeys, targets, defaultTarget, key)); + protected void emitStrategySwitch(SwitchStrategy strategy, Variable key, LabelRef[] keyTargets, LabelRef defaultTarget) { + boolean needsTemp = key.getKind() == Kind.Long || key.getKind() == Kind.Object; + append(new StrategySwitchOp(strategy, keyTargets, defaultTarget, key, needsTemp ? newVariable(key.getKind()) : Value.ILLEGAL)); } @Override
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Wed Dec 11 15:59:40 2013 +0100 @@ -730,118 +730,66 @@ */ @Override public void emitSwitch(SwitchNode x) { + assert x.defaultSuccessor() != null; + LabelRef defaultTarget = getLIRBlock(x.defaultSuccessor()); int keyCount = x.keyCount(); if (keyCount == 0) { - emitJump(getLIRBlock(x.defaultSuccessor())); + emitJump(defaultTarget); } else { Variable value = load(operand(x.value())); - LabelRef defaultTarget = x.defaultSuccessor() == null ? null : getLIRBlock(x.defaultSuccessor()); - if (value.getKind() != Kind.Int) { - // hopefully only a few entries - emitSequentialSwitch(x, value, defaultTarget); + if (keyCount == 1) { + assert defaultTarget != null; + emitCompareBranch(load(operand(x.value())), x.keyAt(0), Condition.EQ, false, getLIRBlock(x.keySuccessor(0)), defaultTarget); } else { - assert value.getKind() == Kind.Int; - long valueRange = x.keyAt(keyCount - 1).asLong() - x.keyAt(0).asLong() + 1; - int switchRangeCount = switchRangeCount(x); - if (switchRangeCount == 0) { - emitJump(getLIRBlock(x.defaultSuccessor())); - } else if (switchRangeCount >= MinimumJumpTableSize.getValue() && keyCount / (double) valueRange >= MinTableSwitchDensity.getValue()) { - int minValue = x.keyAt(0).asInt(); - assert valueRange < Integer.MAX_VALUE; - LabelRef[] targets = new LabelRef[(int) valueRange]; - for (int i = 0; i < valueRange; i++) { - targets[i] = defaultTarget; - } - for (int i = 0; i < keyCount; i++) { - targets[x.keyAt(i).asInt() - minValue] = getLIRBlock(x.keySuccessor(i)); - } - emitTableSwitch(minValue, defaultTarget, targets, value); - } else if (keyCount / switchRangeCount >= RangeTestsSwitchDensity.getValue()) { - emitSwitchRanges(x, switchRangeCount, value, defaultTarget); + LabelRef[] keyTargets = new LabelRef[keyCount]; + Constant[] keyConstants = new Constant[keyCount]; + double[] keyProbabilities = new double[keyCount]; + for (int i = 0; i < keyCount; i++) { + keyTargets[i] = getLIRBlock(x.keySuccessor(i)); + keyConstants[i] = x.keyAt(i); + keyProbabilities[i] = x.keyProbability(i); + } + if (value.getKind() != Kind.Int || !x.isSorted()) { + // hopefully only a few entries + emitStrategySwitch(new SwitchStrategy.SequentialStrategy(keyProbabilities, keyConstants), value, keyTargets, defaultTarget); } else { - emitSequentialSwitch(x, value, defaultTarget); + emitStrategySwitch(keyConstants, keyProbabilities, keyTargets, defaultTarget, value); } } } } - protected void emitSequentialSwitch(final SwitchNode x, Variable key, LabelRef defaultTarget) { - int keyCount = x.keyCount(); - Integer[] indexes = Util.createSortedPermutation(keyCount, new Comparator<Integer>() { - - @Override - public int compare(Integer o1, Integer o2) { - return x.keyProbability(o1) < x.keyProbability(o2) ? 1 : x.keyProbability(o1) > x.keyProbability(o2) ? -1 : 0; + protected void emitStrategySwitch(Constant[] keyConstants, double[] keyProbabilities, LabelRef[] keyTargets, LabelRef defaultTarget, Variable value) { + int keyCount = keyConstants.length; + SwitchStrategy strategy = SwitchStrategy.getBestStrategy(keyProbabilities, keyConstants, keyTargets); + long valueRange = keyConstants[keyCount - 1].asLong() - keyConstants[0].asLong() + 1; + double tableSwitchDensity = keyCount / (double) valueRange; + /* + * This heuristic tries to find a compromise between the effort for the best switch strategy + * and the density of a tableswitch. If the effort for the strategy is at least 4, then a + * tableswitch is preferred if better than a certain value that starts at 0.5 and lowers + * gradually with additional effort. + */ + if (strategy.getAverageEffort() < 4 || tableSwitchDensity < (1 / Math.sqrt(strategy.getAverageEffort()))) { + emitStrategySwitch(strategy, value, keyTargets, defaultTarget); + } else { + int minValue = keyConstants[0].asInt(); + assert valueRange < Integer.MAX_VALUE; + LabelRef[] targets = new LabelRef[(int) valueRange]; + for (int i = 0; i < valueRange; i++) { + targets[i] = defaultTarget; } - }); - LabelRef[] keyTargets = new LabelRef[keyCount]; - Constant[] keyConstants = new Constant[keyCount]; - for (int i = 0; i < keyCount; i++) { - keyTargets[i] = getLIRBlock(x.keySuccessor(indexes[i])); - keyConstants[i] = x.keyAt(indexes[i]); + for (int i = 0; i < keyCount; i++) { + targets[keyConstants[i].asInt() - minValue] = keyTargets[i]; + } + emitTableSwitch(minValue, defaultTarget, targets, value); } - emitSequentialSwitch(keyConstants, keyTargets, defaultTarget, key); } - protected abstract void emitSequentialSwitch(Constant[] keyConstants, LabelRef[] keyTargets, LabelRef defaultTarget, Value key); - - protected abstract void emitSwitchRanges(int[] lowKeys, int[] highKeys, LabelRef[] targets, LabelRef defaultTarget, Value key); + protected abstract void emitStrategySwitch(SwitchStrategy strategy, Variable key, LabelRef[] keyTargets, LabelRef defaultTarget); protected abstract void emitTableSwitch(int lowKey, LabelRef defaultTarget, LabelRef[] targets, Value key); - private static int switchRangeCount(SwitchNode x) { - int keyCount = x.keyCount(); - int switchRangeCount = 0; - int defaultSux = x.defaultSuccessorIndex(); - - int key = x.keyAt(0).asInt(); - int sux = x.keySuccessorIndex(0); - for (int i = 0; i < keyCount; i++) { - int newKey = x.keyAt(i).asInt(); - int newSux = x.keySuccessorIndex(i); - if (newSux != defaultSux && (newKey != key + 1 || sux != newSux)) { - switchRangeCount++; - } - key = newKey; - sux = newSux; - } - return switchRangeCount; - } - - private void emitSwitchRanges(SwitchNode x, int switchRangeCount, Variable keyValue, LabelRef defaultTarget) { - assert switchRangeCount >= 1 : "switch ranges should not be used for emitting only the default case"; - - int[] lowKeys = new int[switchRangeCount]; - int[] highKeys = new int[switchRangeCount]; - LabelRef[] targets = new LabelRef[switchRangeCount]; - - int keyCount = x.keyCount(); - int defaultSuccessor = x.defaultSuccessorIndex(); - - int current = -1; - int key = -1; - int successor = -1; - for (int i = 0; i < keyCount; i++) { - int newSuccessor = x.keySuccessorIndex(i); - int newKey = x.keyAt(i).asInt(); - if (newSuccessor != defaultSuccessor) { - if (key + 1 == newKey && successor == newSuccessor) { - // still in same range - highKeys[current] = newKey; - } else { - current++; - lowKeys[current] = newKey; - highKeys[current] = newKey; - targets[current] = getLIRBlock(x.blockSuccessor(newSuccessor)); - } - } - key = newKey; - successor = newSuccessor; - } - assert current == switchRangeCount - 1; - emitSwitchRanges(lowKeys, highKeys, targets, defaultTarget, keyValue); - } - public FrameMap frameMap() { return frameMap; }
--- a/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64ControlFlow.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64ControlFlow.java Wed Dec 11 15:59:40 2013 +0100 @@ -36,6 +36,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.lir.*; import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.SwitchStrategy.*; import com.oracle.graal.lir.asm.*; import com.oracle.graal.nodes.calc.*; @@ -102,6 +103,61 @@ } } + public static class StrategySwitchOp extends AMD64LIRInstruction implements BlockEndOp { + @Use({CONST}) protected Constant[] keyConstants; + private final LabelRef[] keyTargets; + private LabelRef defaultTarget; + @Alive({REG}) protected Value key; + @Temp({REG, ILLEGAL}) protected Value scratch; + private final SwitchStrategy strategy; + + public StrategySwitchOp(SwitchStrategy strategy, LabelRef[] keyTargets, LabelRef defaultTarget, Value key, Value scratch) { + this.strategy = strategy; + this.keyConstants = strategy.keyConstants; + this.keyTargets = keyTargets; + this.defaultTarget = defaultTarget; + this.key = key; + this.scratch = scratch; + assert keyConstants.length == keyTargets.length; + assert keyConstants.length == strategy.keyProbabilities.length; + assert (scratch.getKind() == Kind.Illegal) == (key.getKind() == Kind.Int || key.getKind() == Kind.Long); + } + + @Override + public void emitCode(final CompilationResultBuilder crb, final AMD64MacroAssembler masm) { + final Register keyRegister = asRegister(key); + + BaseSwitchClosure closure = new BaseSwitchClosure(crb, masm, keyTargets, defaultTarget) { + @Override + protected void conditionalJump(int index, Condition condition, Label target) { + switch (key.getKind()) { + case Int: + if (crb.codeCache.needsDataPatch(keyConstants[index])) { + crb.recordDataReferenceInCode(keyConstants[index], 0, true); + } + long lc = keyConstants[index].asLong(); + assert NumUtil.isInt(lc); + masm.cmpl(keyRegister, (int) lc); + break; + case Long: + masm.cmpq(keyRegister, (AMD64Address) crb.asLongConstRef(keyConstants[index])); + break; + case Object: + assert condition == Condition.EQ || condition == Condition.NE; + Register temp = asObjectReg(scratch); + AMD64Move.move(crb, masm, temp.asValue(Kind.Object), keyConstants[index]); + masm.cmpptr(keyRegister, temp); + break; + default: + throw new GraalInternalError("switch only supported for int, long and object"); + } + masm.jcc(intCond(condition), target); + } + }; + strategy.run(closure); + } + } + public static class TableSwitchOp extends AMD64LIRInstruction implements BlockEndOp { private final int lowKey; private final LabelRef defaultTarget; @@ -119,128 +175,64 @@ @Override public void emitCode(CompilationResultBuilder crb, AMD64MacroAssembler masm) { - tableswitch(crb, masm, lowKey, defaultTarget, targets, asIntReg(index), asLongReg(scratch)); - } - } - - public static class SequentialSwitchOp extends AMD64LIRInstruction implements BlockEndOp { - @Use({CONST}) protected Constant[] keyConstants; - private final LabelRef[] keyTargets; - private LabelRef defaultTarget; - @Alive({REG}) protected Value key; - @Temp({REG, ILLEGAL}) protected Value scratch; - - public SequentialSwitchOp(Constant[] keyConstants, LabelRef[] keyTargets, LabelRef defaultTarget, Value key, Value scratch) { - assert keyConstants.length == keyTargets.length; - this.keyConstants = keyConstants; - this.keyTargets = keyTargets; - this.defaultTarget = defaultTarget; - this.key = key; - this.scratch = scratch; - } + Register value = asIntReg(index); + Register scratchReg = asLongReg(scratch); - @Override - public void emitCode(CompilationResultBuilder crb, AMD64MacroAssembler masm) { - if (key.getKind() == Kind.Int) { - Register intKey = asIntReg(key); - for (int i = 0; i < keyConstants.length; i++) { - if (crb.codeCache.needsDataPatch(keyConstants[i])) { - crb.recordDataReferenceInCode(keyConstants[i], 0, true); - } - long lc = keyConstants[i].asLong(); - assert NumUtil.isInt(lc); - masm.cmpl(intKey, (int) lc); - masm.jcc(ConditionFlag.Equal, keyTargets[i].label()); - } - } else if (key.getKind() == Kind.Long) { - Register longKey = asLongReg(key); - for (int i = 0; i < keyConstants.length; i++) { - masm.cmpq(longKey, (AMD64Address) crb.asLongConstRef(keyConstants[i])); - masm.jcc(ConditionFlag.Equal, keyTargets[i].label()); - } - } else if (key.getKind() == Kind.Object) { - Register objectKey = asObjectReg(key); - Register temp = asObjectReg(scratch); - for (int i = 0; i < keyConstants.length; i++) { - AMD64Move.move(crb, masm, temp.asValue(Kind.Object), keyConstants[i]); - masm.cmpptr(objectKey, temp); - masm.jcc(ConditionFlag.Equal, keyTargets[i].label()); - } + Buffer buf = masm.codeBuffer; + // Compare index against jump table bounds + int highKey = lowKey + targets.length - 1; + if (lowKey != 0) { + // subtract the low value from the switch value + masm.subl(value, lowKey); + masm.cmpl(value, highKey - lowKey); } else { - throw new GraalInternalError("sequential switch only supported for int, long and object"); - } - if (!defaultTarget.isCodeEmittingOrderSuccessorEdge(crb.getCurrentBlockIndex())) { - masm.jmp(defaultTarget.label()); + masm.cmpl(value, highKey); } - } - } - - public static class SwitchRangesOp extends AMD64LIRInstruction implements BlockEndOp { - private final LabelRef[] keyTargets; - private LabelRef defaultTarget; - private final int[] lowKeys; - private final int[] highKeys; - @Alive protected Value key; - - public SwitchRangesOp(int[] lowKeys, int[] highKeys, LabelRef[] keyTargets, LabelRef defaultTarget, Value key) { - this.lowKeys = lowKeys; - this.highKeys = highKeys; - this.keyTargets = keyTargets; - this.defaultTarget = defaultTarget; - this.key = key; - } - @Override - public void emitCode(CompilationResultBuilder crb, AMD64MacroAssembler masm) { - assert isSorted(lowKeys) && isSorted(highKeys); - - Label actualDefaultTarget = defaultTarget == null ? new Label() : defaultTarget.label(); - int prevHighKey = 0; - boolean skipLowCheck = false; - for (int i = 0; i < lowKeys.length; i++) { - int lowKey = lowKeys[i]; - int highKey = highKeys[i]; - if (lowKey == highKey) { - masm.cmpl(asIntReg(key), lowKey); - masm.jcc(ConditionFlag.Equal, keyTargets[i].label()); - skipLowCheck = false; - } else { - if (!skipLowCheck || (prevHighKey + 1) != lowKey) { - masm.cmpl(asIntReg(key), lowKey); - masm.jcc(ConditionFlag.Less, actualDefaultTarget); - } - masm.cmpl(asIntReg(key), highKey); - masm.jcc(ConditionFlag.LessEqual, keyTargets[i].label()); - skipLowCheck = true; - } - prevHighKey = highKey; + // Jump to default target if index is not within the jump table + if (defaultTarget != null) { + masm.jcc(ConditionFlag.Above, defaultTarget.label()); } - if (defaultTarget != null) { - if (!defaultTarget.isCodeEmittingOrderSuccessorEdge(crb.getCurrentBlockIndex())) { - masm.jmp(defaultTarget.label()); - } - } else { - masm.bind(actualDefaultTarget); - masm.hlt(); + // Set scratch to address of jump table + int leaPos = buf.position(); + masm.leaq(scratchReg, new AMD64Address(AMD64.rip, 0)); + int afterLea = buf.position(); + + // Load jump table entry into scratch and jump to it + masm.movslq(value, new AMD64Address(scratchReg, value, Scale.Times4, 0)); + masm.addq(scratchReg, value); + masm.jmp(scratchReg); + + // Inserting padding so that jump table address is 4-byte aligned + if ((buf.position() & 0x3) != 0) { + masm.nop(4 - (buf.position() & 0x3)); } - } - @Override - protected void verify() { - super.verify(); - assert lowKeys.length == keyTargets.length; - assert highKeys.length == keyTargets.length; - assert key.getKind() == Kind.Int; - } + // Patch LEA instruction above now that we know the position of the jump table + int jumpTablePos = buf.position(); + buf.setPosition(leaPos); + masm.leaq(scratchReg, new AMD64Address(AMD64.rip, jumpTablePos - afterLea)); + buf.setPosition(jumpTablePos); - private static boolean isSorted(int[] values) { - for (int i = 1; i < values.length; i++) { - if (values[i - 1] >= values[i]) { - return false; + // Emit jump table entries + for (LabelRef target : targets) { + Label label = target.label(); + int offsetToJumpTableBase = buf.position() - jumpTablePos; + if (label.isBound()) { + int imm32 = label.position() - jumpTablePos; + buf.emitInt(imm32); + } else { + label.addPatchAt(buf.position()); + + buf.emitByte(0); // pseudo-opcode for jump table entry + buf.emitShort(offsetToJumpTableBase); + buf.emitByte(0); // padding to make jump table entry 4 bytes wide } } - return true; + + JumpTable jt = new JumpTable(jumpTablePos, lowKey, highKey, 4); + crb.compilationResult.addAnnotation(jt); } } @@ -286,64 +278,6 @@ } } - private static void tableswitch(CompilationResultBuilder crb, AMD64MacroAssembler masm, int lowKey, LabelRef defaultTarget, LabelRef[] targets, Register value, Register scratch) { - Buffer buf = masm.codeBuffer; - // Compare index against jump table bounds - int highKey = lowKey + targets.length - 1; - if (lowKey != 0) { - // subtract the low value from the switch value - masm.subl(value, lowKey); - masm.cmpl(value, highKey - lowKey); - } else { - masm.cmpl(value, highKey); - } - - // Jump to default target if index is not within the jump table - if (defaultTarget != null) { - masm.jcc(ConditionFlag.Above, defaultTarget.label()); - } - - // Set scratch to address of jump table - int leaPos = buf.position(); - masm.leaq(scratch, new AMD64Address(AMD64.rip, 0)); - int afterLea = buf.position(); - - // Load jump table entry into scratch and jump to it - masm.movslq(value, new AMD64Address(scratch, value, Scale.Times4, 0)); - masm.addq(scratch, value); - masm.jmp(scratch); - - // Inserting padding so that jump table address is 4-byte aligned - if ((buf.position() & 0x3) != 0) { - masm.nop(4 - (buf.position() & 0x3)); - } - - // Patch LEA instruction above now that we know the position of the jump table - int jumpTablePos = buf.position(); - buf.setPosition(leaPos); - masm.leaq(scratch, new AMD64Address(AMD64.rip, jumpTablePos - afterLea)); - buf.setPosition(jumpTablePos); - - // Emit jump table entries - for (LabelRef target : targets) { - Label label = target.label(); - int offsetToJumpTableBase = buf.position() - jumpTablePos; - if (label.isBound()) { - int imm32 = label.position() - jumpTablePos; - buf.emitInt(imm32); - } else { - label.addPatchAt(buf.position()); - - buf.emitByte(0); // pseudo-opcode for jump table entry - buf.emitShort(offsetToJumpTableBase); - buf.emitByte(0); // padding to make jump table entry 4 bytes wide - } - } - - JumpTable jt = new JumpTable(jumpTablePos, lowKey, highKey, 4); - crb.compilationResult.addAnnotation(jt); - } - private static void floatJcc(AMD64MacroAssembler masm, ConditionFlag condition, boolean unorderedIsTrue, Label label) { Label endLabel = new Label(); if (unorderedIsTrue && !trueOnUnordered(condition)) {
--- a/graal/com.oracle.graal.lir.hsail/src/com/oracle/graal/lir/hsail/HSAILCompare.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.lir.hsail/src/com/oracle/graal/lir/hsail/HSAILCompare.java Wed Dec 11 15:59:40 2013 +0100 @@ -71,7 +71,7 @@ emitCompare(masm, condition, x, y, unorderedIsTrue); } - private static String conditionToString(Condition condition) { + public static String conditionToString(Condition condition) { switch (condition) { case EQ: return "eq";
--- a/graal/com.oracle.graal.lir.hsail/src/com/oracle/graal/lir/hsail/HSAILControlFlow.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.lir.hsail/src/com/oracle/graal/lir/hsail/HSAILControlFlow.java Wed Dec 11 15:59:40 2013 +0100 @@ -25,10 +25,12 @@ import static com.oracle.graal.lir.LIRInstruction.OperandFlag.*; import com.oracle.graal.api.meta.*; +import com.oracle.graal.asm.*; import com.oracle.graal.asm.hsail.*; import com.oracle.graal.graph.*; import com.oracle.graal.lir.*; -import com.oracle.graal.lir.StandardOp.*; +import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.SwitchStrategy.BaseSwitchClosure; import com.oracle.graal.lir.asm.*; import com.oracle.graal.nodes.calc.*; @@ -46,7 +48,7 @@ * performing HSAIL code. Thus the execution path for both the TABLESWITCH and LOOKUPSWITCH * bytecodes go through this op. */ - public static class SwitchOp extends HSAILLIRInstruction implements BlockEndOp { + public static class StrategySwitchOp extends HSAILLIRInstruction implements BlockEndOp { /** * The array of key constants used for the cases of this switch statement. */ @@ -61,20 +63,19 @@ */ @Alive({REG}) protected Value key; + private final SwitchStrategy strategy; + /** - * Constructor. Called from the HSAILLIRGenerator.emitSequentialSwitch routine. - * - * @param keyConstants - * @param keyTargets - * @param defaultTarget - * @param key + * Constructor. Called from the HSAILLIRGenerator.emitStrategySwitch routine. */ - public SwitchOp(Constant[] keyConstants, LabelRef[] keyTargets, LabelRef defaultTarget, Value key) { - assert keyConstants.length == keyTargets.length; - this.keyConstants = keyConstants; + public StrategySwitchOp(SwitchStrategy strategy, LabelRef[] keyTargets, LabelRef defaultTarget, Value key) { + this.strategy = strategy; + this.keyConstants = strategy.keyConstants; this.keyTargets = keyTargets; this.defaultTarget = defaultTarget; this.key = key; + assert keyConstants.length == keyTargets.length; + assert keyConstants.length == strategy.keyProbabilities.length; } /** @@ -89,22 +90,24 @@ * @param masm the HSAIL assembler */ @Override - public void emitCode(CompilationResultBuilder crb, HSAILAssembler masm) { - if (key.getKind() == Kind.Int) { - for (int i = 0; i < keyConstants.length; i++) { - // Generate cascading compare and branches for each case. - masm.emitCompare(key, keyConstants[i], "eq", false, false); - masm.cbr(masm.nameOf(keyTargets[i].label())); + public void emitCode(CompilationResultBuilder crb, final HSAILAssembler masm) { + BaseSwitchClosure closure = new BaseSwitchClosure(crb, masm, keyTargets, defaultTarget) { + @Override + protected void conditionalJump(int index, Condition condition, Label target) { + switch (key.getKind()) { + case Int: + // Generate cascading compare and branches for each case. + masm.emitCompare(key, keyConstants[index], HSAILCompare.conditionToString(condition), false, false); + masm.cbr(masm.nameOf(target)); + break; + case Long: + case Object: + default: + throw new GraalInternalError("switch only supported for int"); + } } - // Generate a jump for the default target if there is one. - if (defaultTarget != null && !defaultTarget.isCodeEmittingOrderSuccessorEdge(crb.getCurrentBlockIndex())) { - masm.jmp(defaultTarget.label()); - } - - } else { - // Throw an exception if the key isn't of type int. - throw new GraalInternalError("Switch statments are only supported for int keys"); - } + }; + strategy.run(closure); } }
--- a/graal/com.oracle.graal.lir.ptx/src/com/oracle/graal/lir/ptx/PTXControlFlow.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.lir.ptx/src/com/oracle/graal/lir/ptx/PTXControlFlow.java Wed Dec 11 15:59:40 2013 +0100 @@ -29,13 +29,14 @@ import com.oracle.graal.api.code.CompilationResult.JumpTable; import com.oracle.graal.api.meta.*; import com.oracle.graal.asm.*; -import com.oracle.graal.asm.ptx.*; import com.oracle.graal.asm.ptx.PTXAssembler.Global; import com.oracle.graal.asm.ptx.PTXAssembler.Setp; +import com.oracle.graal.asm.ptx.*; import com.oracle.graal.asm.ptx.PTXMacroAssembler.Mov; import com.oracle.graal.graph.*; import com.oracle.graal.lir.*; import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.SwitchStrategy.BaseSwitchClosure; import com.oracle.graal.lir.asm.*; import com.oracle.graal.nodes.calc.*; @@ -193,54 +194,55 @@ } } - public static class SequentialSwitchOp extends PTXLIRInstruction implements BlockEndOp { + public static class StrategySwitchOp extends PTXLIRInstruction implements BlockEndOp { @Use({CONST}) protected Constant[] keyConstants; private final LabelRef[] keyTargets; private LabelRef defaultTarget; @Alive({REG}) protected Value key; @Temp({REG, ILLEGAL}) protected Value scratch; + private final SwitchStrategy strategy; // Number of predicate register that would be set by this instruction. protected int predRegNum; - public SequentialSwitchOp(Constant[] keyConstants, LabelRef[] keyTargets, LabelRef defaultTarget, Value key, Value scratch, int predReg) { - assert keyConstants.length == keyTargets.length; - this.keyConstants = keyConstants; + public StrategySwitchOp(SwitchStrategy strategy, LabelRef[] keyTargets, LabelRef defaultTarget, Value key, Value scratch, int predReg) { + this.strategy = strategy; + this.keyConstants = strategy.keyConstants; this.keyTargets = keyTargets; this.defaultTarget = defaultTarget; this.key = key; this.scratch = scratch; + assert keyConstants.length == keyTargets.length; + assert keyConstants.length == strategy.keyProbabilities.length; + assert (scratch.getKind() == Kind.Illegal) == (key.getKind() == Kind.Int || key.getKind() == Kind.Long); predRegNum = predReg; } @Override - public void emitCode(CompilationResultBuilder crb, PTXMacroAssembler masm) { - Kind keyKind = key.getKind(); - - if (keyKind == Kind.Int || keyKind == Kind.Long) { - for (int i = 0; i < keyConstants.length; i++) { - if (crb.codeCache.needsDataPatch(keyConstants[i])) { - crb.recordDataReferenceInCode(keyConstants[i], 0, true); + public void emitCode(final CompilationResultBuilder crb, final PTXMacroAssembler masm) { + BaseSwitchClosure closure = new BaseSwitchClosure(crb, masm, keyTargets, defaultTarget) { + @Override + protected void conditionalJump(int index, Condition condition, Label target) { + switch (key.getKind()) { + case Int: + case Long: + if (crb.codeCache.needsDataPatch(keyConstants[index])) { + crb.recordDataReferenceInCode(keyConstants[index], 0, true); + } + new Setp(EQ, keyConstants[index], key, predRegNum).emit(masm); + break; + case Object: + assert condition == Condition.EQ || condition == Condition.NE; + PTXMove.move(crb, masm, scratch, keyConstants[index]); + new Setp(condition, scratch, key, predRegNum).emit(masm); + break; + default: + throw new GraalInternalError("switch only supported for int, long and object"); } - new Setp(EQ, keyConstants[i], key, predRegNum).emit(masm); - masm.bra(masm.nameOf(keyTargets[i].label()), predRegNum); + masm.bra(masm.nameOf(target), predRegNum); } - } else if (keyKind == Kind.Object) { - for (int i = 0; i < keyConstants.length; i++) { - PTXMove.move(crb, masm, scratch, keyConstants[i]); - new Setp(EQ, keyConstants[i], scratch, predRegNum).emit(masm); - masm.bra(keyTargets[i].label().toString(), predRegNum); - } - } else { - throw new GraalInternalError("sequential switch only supported for int, long and object"); - } - if (defaultTarget != null) { - if (!defaultTarget.isCodeEmittingOrderSuccessorEdge(crb.getCurrentBlockIndex())) { - masm.jmp(defaultTarget.label()); - } - } else { - // masm.hlt(); - } + }; + strategy.run(closure); } } @@ -265,41 +267,35 @@ @Override public void emitCode(CompilationResultBuilder crb, PTXMacroAssembler masm) { - tableswitch(crb, masm, lowKey, defaultTarget, targets, index, scratch, predRegNum); + Buffer buf = masm.codeBuffer; + + // Compare index against jump table bounds + + int highKey = lowKey + targets.length - 1; + if (lowKey != 0) { + // subtract the low value from the switch value + // new Sub(value, value, lowKey).emit(masm); + new Setp(GT, index, Constant.forInt(highKey - lowKey), predRegNum).emit(masm); + } else { + new Setp(GT, index, Constant.forInt(highKey), predRegNum).emit(masm); + } + + // Jump to default target if index is not within the jump table + if (defaultTarget != null) { + masm.bra(masm.nameOf(defaultTarget.label()), predRegNum); + } + + // address of jump table + int tablePos = buf.position(); + + JumpTable jt = new JumpTable(tablePos, lowKey, highKey, 4); + String name = "jumptable" + jt.position; + + new Global(index, name, targets).emit(masm); + + // bra(Value, name); + + crb.compilationResult.addAnnotation(jt); } } - - @SuppressWarnings("unused") - private static void tableswitch(CompilationResultBuilder crb, PTXAssembler masm, int lowKey, LabelRef defaultTarget, LabelRef[] targets, Value value, Value scratch, int predNum) { - Buffer buf = masm.codeBuffer; - - // Compare index against jump table bounds - - int highKey = lowKey + targets.length - 1; - if (lowKey != 0) { - // subtract the low value from the switch value - // new Sub(value, value, lowKey).emit(masm); - new Setp(GT, value, Constant.forInt(highKey - lowKey), predNum).emit(masm); - } else { - new Setp(GT, value, Constant.forInt(highKey), predNum).emit(masm); - } - - // Jump to default target if index is not within the jump table - if (defaultTarget != null) { - masm.bra(masm.nameOf(defaultTarget.label()), predNum); - } - - // address of jump table - int tablePos = buf.position(); - - JumpTable jt = new JumpTable(tablePos, lowKey, highKey, 4); - String name = "jumptable" + jt.position; - - new Global(value, name, targets).emit(masm); - - // bra(Value, name); - - crb.compilationResult.addAnnotation(jt); - - } }
--- a/graal/com.oracle.graal.lir.sparc/src/com/oracle/graal/lir/sparc/SPARCControlFlow.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.lir.sparc/src/com/oracle/graal/lir/sparc/SPARCControlFlow.java Wed Dec 11 15:59:40 2013 +0100 @@ -30,15 +30,31 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.asm.*; import com.oracle.graal.asm.sparc.*; -import com.oracle.graal.asm.sparc.SPARCAssembler.*; +import com.oracle.graal.asm.sparc.SPARCAssembler.Bpe; +import com.oracle.graal.asm.sparc.SPARCAssembler.Bpg; +import com.oracle.graal.asm.sparc.SPARCAssembler.Bpge; +import com.oracle.graal.asm.sparc.SPARCAssembler.Bpgu; +import com.oracle.graal.asm.sparc.SPARCAssembler.Bpl; +import com.oracle.graal.asm.sparc.SPARCAssembler.Bple; +import com.oracle.graal.asm.sparc.SPARCAssembler.Bpleu; +import com.oracle.graal.asm.sparc.SPARCAssembler.Bpne; +import com.oracle.graal.asm.sparc.SPARCAssembler.CC; +import com.oracle.graal.asm.sparc.SPARCAssembler.ConditionFlag; +import com.oracle.graal.asm.sparc.SPARCAssembler.Movcc; +import com.oracle.graal.asm.sparc.SPARCAssembler.Sub; +import com.oracle.graal.asm.sparc.SPARCMacroAssembler.Bpgeu; +import com.oracle.graal.asm.sparc.SPARCMacroAssembler.Bplu; +import com.oracle.graal.asm.sparc.SPARCMacroAssembler.Cmp; +import com.oracle.graal.asm.sparc.SPARCMacroAssembler.Jmp; +import com.oracle.graal.asm.sparc.SPARCMacroAssembler.Nop; +import com.oracle.graal.asm.sparc.SPARCMacroAssembler.Ret; import com.oracle.graal.graph.*; import com.oracle.graal.lir.*; -import com.oracle.graal.lir.StandardOp.*; +import com.oracle.graal.lir.StandardOp.BlockEndOp; +import com.oracle.graal.lir.SwitchStrategy.BaseSwitchClosure; import com.oracle.graal.lir.asm.*; import com.oracle.graal.nodes.calc.*; -import static com.oracle.graal.asm.sparc.SPARCMacroAssembler.*; - public class SPARCControlFlow { public static class BranchOp extends SPARCLIRInstruction implements StandardOp.BranchOp { @@ -72,40 +88,7 @@ } assert kind == Kind.Int || kind == Kind.Long || kind == Kind.Object; CC cc = kind == Kind.Int ? CC.Icc : CC.Xcc; - switch (actualCondition) { - case EQ: - new Bpe(cc, actualTarget).emit(masm); - break; - case NE: - new Bpne(cc, actualTarget).emit(masm); - break; - case BT: - new Bplu(cc, actualTarget).emit(masm); - break; - case LT: - new Bpl(cc, actualTarget).emit(masm); - break; - case BE: - new Bpleu(cc, actualTarget).emit(masm); - break; - case LE: - new Bple(cc, actualTarget).emit(masm); - break; - case GE: - new Bpge(cc, actualTarget).emit(masm); - break; - case AE: - new Bpgeu(cc, actualTarget).emit(masm); - break; - case GT: - new Bpg(cc, actualTarget).emit(masm); - break; - case AT: - new Bpgu(cc, actualTarget).emit(masm); - break; - default: - throw GraalInternalError.shouldNotReachHere(); - } + emitCompare(masm, actualTarget, actualCondition, cc); new Nop().emit(masm); // delay slot if (needJump) { masm.jmp(falseDestination.label()); @@ -113,6 +96,43 @@ } } + private static void emitCompare(SPARCMacroAssembler masm, Label target, Condition actualCondition, CC cc) { + switch (actualCondition) { + case EQ: + new Bpe(cc, target).emit(masm); + break; + case NE: + new Bpne(cc, target).emit(masm); + break; + case BT: + new Bplu(cc, target).emit(masm); + break; + case LT: + new Bpl(cc, target).emit(masm); + break; + case BE: + new Bpleu(cc, target).emit(masm); + break; + case LE: + new Bple(cc, target).emit(masm); + break; + case GE: + new Bpge(cc, target).emit(masm); + break; + case AE: + new Bpgeu(cc, target).emit(masm); + break; + case GT: + new Bpg(cc, target).emit(masm); + break; + case AT: + new Bpgu(cc, target).emit(masm); + break; + default: + throw GraalInternalError.shouldNotReachHere(); + } + } + @Opcode("CMOVE") public static class CondMoveOp extends SPARCLIRInstruction { @@ -264,136 +284,64 @@ } } - public static class SequentialSwitchOp extends SPARCLIRInstruction implements BlockEndOp { - + public static class StrategySwitchOp extends SPARCLIRInstruction implements BlockEndOp { @Use({CONST}) protected Constant[] keyConstants; private final LabelRef[] keyTargets; private LabelRef defaultTarget; @Alive({REG}) protected Value key; @Temp({REG, ILLEGAL}) protected Value scratch; + private final SwitchStrategy strategy; - public SequentialSwitchOp(Constant[] keyConstants, LabelRef[] keyTargets, LabelRef defaultTarget, Value key, Value scratch) { - assert keyConstants.length == keyTargets.length; - this.keyConstants = keyConstants; + public StrategySwitchOp(SwitchStrategy strategy, LabelRef[] keyTargets, LabelRef defaultTarget, Value key, Value scratch) { + this.strategy = strategy; + this.keyConstants = strategy.keyConstants; this.keyTargets = keyTargets; this.defaultTarget = defaultTarget; this.key = key; this.scratch = scratch; + assert keyConstants.length == keyTargets.length; + assert keyConstants.length == strategy.keyProbabilities.length; + assert (scratch.getKind() == Kind.Illegal) == (key.getKind() == Kind.Int); } @Override - public void emitCode(CompilationResultBuilder crb, SPARCMacroAssembler masm) { - if (key.getKind() == Kind.Int) { - Register intKey = asIntReg(key); - for (int i = 0; i < keyConstants.length; i++) { - if (crb.codeCache.needsDataPatch(keyConstants[i])) { - crb.recordDataReferenceInCode(keyConstants[i], 0, true); + public void emitCode(final CompilationResultBuilder crb, final SPARCMacroAssembler masm) { + final Register keyRegister = asRegister(key); + + BaseSwitchClosure closure = new BaseSwitchClosure(crb, masm, keyTargets, defaultTarget) { + @Override + protected void conditionalJump(int index, Condition condition, Label target) { + switch (key.getKind()) { + case Int: + if (crb.codeCache.needsDataPatch(keyConstants[index])) { + crb.recordDataReferenceInCode(keyConstants[index], 0, true); + } + long lc = keyConstants[index].asLong(); + assert NumUtil.isInt(lc); + new Cmp(keyRegister, (int) lc).emit(masm); + emitCompare(masm, target, condition, CC.Icc); + break; + case Long: { + Register temp = asLongReg(scratch); + SPARCMove.move(crb, masm, temp.asValue(Kind.Long), keyConstants[index]); + new Cmp(keyRegister, temp).emit(masm); + emitCompare(masm, target, condition, CC.Xcc); + break; + } + case Object: { + Register temp = asObjectReg(scratch); + SPARCMove.move(crb, masm, temp.asValue(Kind.Object), keyConstants[index]); + new Cmp(keyRegister, temp).emit(masm); + emitCompare(masm, target, condition, CC.Ptrcc); + break; + } + default: + throw new GraalInternalError("switch only supported for int, long and object"); } - long lc = keyConstants[i].asLong(); - assert NumUtil.isInt(lc); - new Cmp(intKey, (int) lc).emit(masm); - new Bpe(CC.Icc, keyTargets[i].label()).emit(masm); - new Nop().emit(masm); // delay slot - } - } else if (key.getKind() == Kind.Long) { - Register longKey = asLongReg(key); - Register temp = asLongReg(scratch); - for (int i = 0; i < keyConstants.length; i++) { - SPARCMove.move(crb, masm, temp.asValue(Kind.Long), keyConstants[i]); - new Cmp(longKey, temp).emit(masm); - new Bpe(CC.Xcc, keyTargets[i].label()).emit(masm); - new Nop().emit(masm); // delay slot - } - } else if (key.getKind() == Kind.Object) { - Register objectKey = asObjectReg(key); - Register temp = asObjectReg(scratch); - for (int i = 0; i < keyConstants.length; i++) { - SPARCMove.move(crb, masm, temp.asValue(Kind.Object), keyConstants[i]); - new Cmp(objectKey, temp).emit(masm); - new Bpe(CC.Ptrcc, keyTargets[i].label()).emit(masm); new Nop().emit(masm); // delay slot } - } else { - throw new GraalInternalError("sequential switch only supported for int, long and object"); - } - if (defaultTarget != null) { - if (!defaultTarget.isCodeEmittingOrderSuccessorEdge(crb.getCurrentBlockIndex())) { - masm.jmp(defaultTarget.label()); - } - } else { - new Illtrap(0).emit(masm); - } - } - } - - public static class SwitchRangesOp extends SPARCLIRInstruction implements BlockEndOp { - - private final LabelRef[] keyTargets; - private LabelRef defaultTarget; - private final int[] lowKeys; - private final int[] highKeys; - @Alive protected Value key; - - public SwitchRangesOp(int[] lowKeys, int[] highKeys, LabelRef[] keyTargets, LabelRef defaultTarget, Value key) { - this.lowKeys = lowKeys; - this.highKeys = highKeys; - this.keyTargets = keyTargets; - this.defaultTarget = defaultTarget; - this.key = key; - } - - @Override - public void emitCode(CompilationResultBuilder crb, SPARCMacroAssembler masm) { - assert isSorted(lowKeys) && isSorted(highKeys); - - Label actualDefaultTarget = defaultTarget == null ? new Label() : defaultTarget.label(); - int prevHighKey = 0; - boolean skipLowCheck = false; - for (int i = 0; i < lowKeys.length; i++) { - int lowKey = lowKeys[i]; - int highKey = highKeys[i]; - if (lowKey == highKey) { - // masm.cmpl(asIntReg(key), lowKey); - // masm.jcc(ConditionFlag.Equal, keyTargets[i].label()); - skipLowCheck = false; - } else { - if (!skipLowCheck || (prevHighKey + 1) != lowKey) { - // masm.cmpl(asIntReg(key), lowKey); - // masm.jcc(ConditionFlag.Less, actualDefaultTarget); - } - // masm.cmpl(asIntReg(key), highKey); - // masm.jcc(ConditionFlag.LessEqual, keyTargets[i].label()); - skipLowCheck = true; - } - prevHighKey = highKey; - } - - if (defaultTarget != null) { - if (!defaultTarget.isCodeEmittingOrderSuccessorEdge(crb.getCurrentBlockIndex())) { - new Bpa(defaultTarget.label()).emit(masm); - } - } else { - masm.bind(actualDefaultTarget); - new Illtrap(0).emit(masm); - } - throw GraalInternalError.unimplemented(); - } - - @Override - protected void verify() { - super.verify(); - assert lowKeys.length == keyTargets.length; - assert highKeys.length == keyTargets.length; - assert key.getKind() == Kind.Int; - } - - private static boolean isSorted(int[] values) { - for (int i = 1; i < values.length; i++) { - if (values[i - 1] >= values[i]) { - return false; - } - } - return true; + }; + strategy.run(closure); } } @@ -415,41 +363,40 @@ @Override public void emitCode(CompilationResultBuilder crb, SPARCMacroAssembler masm) { - tableswitch(crb, masm, lowKey, defaultTarget, targets, asIntReg(index), asLongReg(scratch)); + Register value = asIntReg(index); + Register scratchReg = asLongReg(scratch); + + Buffer buf = masm.codeBuffer; + // Compare index against jump table bounds + int highKey = lowKey + targets.length - 1; + if (lowKey != 0) { + // subtract the low value from the switch value + new Sub(value, lowKey, value).emit(masm); + // masm.setp_gt_s32(value, highKey - lowKey); + } else { + // masm.setp_gt_s32(value, highKey); + } + + // Jump to default target if index is not within the jump table + if (defaultTarget != null) { + new Bpgu(CC.Icc, defaultTarget.label()).emit(masm); + new Nop().emit(masm); // delay slot + } + + // Load jump table entry into scratch and jump to it + // masm.movslq(value, new AMD64Address(scratch, value, Scale.Times4, 0)); + // masm.addq(scratch, value); + new Jmp(new SPARCAddress(scratchReg, 0)).emit(masm); + new Nop().emit(masm); // delay slot + + // address of jump table + int tablePos = buf.position(); + + JumpTable jt = new JumpTable(tablePos, lowKey, highKey, 4); + crb.compilationResult.addAnnotation(jt); + + // SPARC: unimp: tableswitch extract + throw GraalInternalError.unimplemented(); } } - - private static void tableswitch(CompilationResultBuilder crb, SPARCAssembler masm, int lowKey, LabelRef defaultTarget, LabelRef[] targets, Register value, Register scratch) { - Buffer buf = masm.codeBuffer; - // Compare index against jump table bounds - int highKey = lowKey + targets.length - 1; - if (lowKey != 0) { - // subtract the low value from the switch value - new Sub(value, lowKey, value).emit(masm); - // masm.setp_gt_s32(value, highKey - lowKey); - } else { - // masm.setp_gt_s32(value, highKey); - } - - // Jump to default target if index is not within the jump table - if (defaultTarget != null) { - new Bpgu(CC.Icc, defaultTarget.label()).emit(masm); - new Nop().emit(masm); // delay slot - } - - // Load jump table entry into scratch and jump to it - // masm.movslq(value, new AMD64Address(scratch, value, Scale.Times4, 0)); - // masm.addq(scratch, value); - new Jmp(new SPARCAddress(scratch, 0)).emit(masm); - new Nop().emit(masm); // delay slot - - // address of jump table - int tablePos = buf.position(); - - JumpTable jt = new JumpTable(tablePos, lowKey, highKey, 4); - crb.compilationResult.addAnnotation(jt); - - // SPARC: unimp: tableswitch extract - throw GraalInternalError.unimplemented(); - } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/SwitchStrategy.java Wed Dec 11 15:59:40 2013 +0100 @@ -0,0 +1,448 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.lir; + +import java.util.*; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.asm.*; +import com.oracle.graal.lir.asm.*; +import com.oracle.graal.nodes.calc.*; + +public abstract class SwitchStrategy { + + private interface SwitchClosure { + /** + * Generates a conditional or unconditional jump. The jump will be unconditional if + * condition is null. If defaultTarget is true, then the jump will go the the default. + * + * @param index Index of the value and the jump target (only used if defaultTarget == false) + * @param condition The condition on which to jump (can be null) + * @param defaultTarget true if the jump should go to the default target, false if index + * should be used. + */ + void conditionalJump(int index, Condition condition, boolean defaultTarget); + + /** + * Generates a conditional jump to the target with the specified index. The fall through + * should go to the default target. + * + * @param index Index of the value and the jump target + * @param condition The condition on which to jump + * @param canFallThrough true if this is the last instruction in the switch statement, to + * allow for fall-through optimizations. + */ + void conditionalJumpOrDefault(int index, Condition condition, boolean canFallThrough); + + /** + * Create a new label and generate a conditional jump to it. + * + * @param index Index of the value and the jump target + * @param condition The condition on which to jump + * @return a new Label + */ + Label conditionalJump(int index, Condition condition); + + /** + * Binds a label returned by {@link #conditionalJump(int, Condition)}. + */ + void bind(Label label); + + /** + * Return true iff the target of both indexes is the same. + */ + boolean isSameTarget(int index1, int index2); + } + + /** + * Backends can subclass this abstract class to generate code for switch strategies. + */ + public abstract static class BaseSwitchClosure implements SwitchClosure { + + private final CompilationResultBuilder crb; + private final AbstractAssembler masm; + private final LabelRef[] keyTargets; + private final LabelRef defaultTarget; + + public BaseSwitchClosure(CompilationResultBuilder crb, AbstractAssembler masm, LabelRef[] keyTargets, LabelRef defaultTarget) { + this.crb = crb; + this.masm = masm; + this.keyTargets = keyTargets; + this.defaultTarget = defaultTarget; + } + + /** + * This method generates code for a comparison between the actual value and the constant at + * the given index and a condition jump to target. + */ + protected abstract void conditionalJump(int index, Condition condition, Label target); + + public void conditionalJump(int index, Condition condition, boolean targetDefault) { + Label target = targetDefault ? defaultTarget.label() : keyTargets[index].label(); + if (condition == null) { + masm.jmp(target); + } else { + conditionalJump(index, condition, target); + } + } + + public void conditionalJumpOrDefault(int index, Condition condition, boolean canFallThrough) { + if (canFallThrough && defaultTarget.isCodeEmittingOrderSuccessorEdge(crb.getCurrentBlockIndex())) { + conditionalJump(index, condition, keyTargets[index].label()); + } else if (canFallThrough && keyTargets[index].isCodeEmittingOrderSuccessorEdge(crb.getCurrentBlockIndex())) { + conditionalJump(index, condition.negate(), defaultTarget.label()); + } else { + conditionalJump(index, condition, keyTargets[index].label()); + masm.jmp(defaultTarget.label()); + } + } + + public Label conditionalJump(int index, Condition condition) { + Label label = new Label(); + conditionalJump(index, condition, label); + return label; + } + + public void bind(Label label) { + masm.bind(label); + } + + public boolean isSameTarget(int index1, int index2) { + return keyTargets[index1] == keyTargets[index2]; + } + + } + + private class EffortClosure implements SwitchClosure { + + private int defaultEffort; + private int defaultCount; + private final int[] keyEfforts = new int[keyConstants.length]; + private final int[] keyCounts = new int[keyConstants.length]; + private final LabelRef[] keyTargets; + + public EffortClosure(LabelRef[] keyTargets) { + this.keyTargets = keyTargets; + } + + public void conditionalJump(int index, Condition condition, boolean defaultTarget) { + // nothing to do + } + + public void conditionalJumpOrDefault(int index, Condition condition, boolean canFallThrough) { + // nothing to do + } + + public Label conditionalJump(int index, Condition condition) { + // nothing to do + return null; + } + + public void bind(Label label) { + // nothing to do + } + + public boolean isSameTarget(int index1, int index2) { + return keyTargets[index1] == keyTargets[index2]; + } + + public double getAverageEffort() { + double defaultProbability = 1; + double effort = 0; + for (int i = 0; i < keyConstants.length; i++) { + effort += keyEfforts[i] * keyProbabilities[i] / keyCounts[i]; + defaultProbability -= keyProbabilities[i]; + } + return effort + defaultEffort * defaultProbability / defaultCount; + } + } + + public final double[] keyProbabilities; + public final Constant[] keyConstants; + private double averageEffort = -1; + private EffortClosure effortClosure; + + public SwitchStrategy(double[] keyProbabilities, Constant[] keyConstants) { + assert keyConstants.length == keyProbabilities.length && keyConstants.length >= 2; + this.keyProbabilities = keyProbabilities; + this.keyConstants = keyConstants; + } + + public double getAverageEffort() { + assert averageEffort >= 0; + return averageEffort; + } + + /* + * Looks for the end of a stretch of key constants that are successive numbers and have the same + * target. + */ + protected int getSliceEnd(SwitchClosure closure, int pos) { + int slice = pos; + while (slice < (keyConstants.length - 1) && keyConstants[slice + 1].asLong() == keyConstants[slice].asLong() + 1 && closure.isSameTarget(slice, slice + 1)) { + slice++; + } + return slice; + } + + protected void registerEffort(int rangeStart, int rangeEnd, int depth) { + if (effortClosure != null) { + for (int i = rangeStart; i <= rangeEnd; i++) { + effortClosure.keyEfforts[i] += depth; + effortClosure.keyCounts[i]++; + } + } + } + + protected void registerDefaultEffort(int depth) { + if (effortClosure != null) { + effortClosure.defaultEffort += depth; + effortClosure.defaultCount++; + } + } + + @Override + public String toString() { + return getClass().getSimpleName() + "[avgEffort=" + averageEffort + "]"; + } + + public static class SequentialStrategy extends SwitchStrategy { + private final Integer[] indexes; + + public SequentialStrategy(final double[] keyProbabilities, Constant[] keyConstants) { + super(keyProbabilities, keyConstants); + + int keyCount = keyConstants.length; + indexes = new Integer[keyCount]; + for (int i = 0; i < keyCount; i++) { + indexes[i] = i; + } + Arrays.sort(indexes, new Comparator<Integer>() { + @Override + public int compare(Integer o1, Integer o2) { + return keyProbabilities[o1] < keyProbabilities[o2] ? 1 : keyProbabilities[o1] > keyProbabilities[o2] ? -1 : 0; + } + }); + } + + @Override + public void run(SwitchClosure closure) { + for (int i = 0; i < keyConstants.length - 1; i++) { + closure.conditionalJump(indexes[i], Condition.EQ, false); + registerEffort(indexes[i], indexes[i], i + 1); + } + closure.conditionalJumpOrDefault(indexes[keyConstants.length - 1], Condition.EQ, true); + registerEffort(indexes[keyConstants.length - 1], indexes[keyConstants.length - 1], keyConstants.length); + registerDefaultEffort(keyConstants.length); + } + } + + public static class RangesStrategy extends SwitchStrategy { + private final Integer[] indexes; + + public RangesStrategy(final double[] keyProbabilities, Constant[] keyConstants) { + super(keyProbabilities, keyConstants); + + int keyCount = keyConstants.length; + indexes = new Integer[keyCount]; + for (int i = 0; i < keyCount; i++) { + indexes[i] = i; + } + Arrays.sort(indexes, new Comparator<Integer>() { + @Override + public int compare(Integer o1, Integer o2) { + return keyProbabilities[o1] < keyProbabilities[o2] ? 1 : keyProbabilities[o1] > keyProbabilities[o2] ? -1 : 0; + } + }); + } + + @Override + public void run(SwitchClosure closure) { + int depth = 0; + closure.conditionalJump(0, Condition.LT, true); + registerDefaultEffort(++depth); + int rangeStart = 0; + int rangeEnd = getSliceEnd(closure, rangeStart); + while (rangeEnd != keyConstants.length - 1) { + if (rangeStart == rangeEnd) { + closure.conditionalJump(rangeStart, Condition.EQ, false); + registerEffort(rangeStart, rangeEnd, ++depth); + } else { + if (rangeStart == 0 || keyConstants[rangeStart - 1].asLong() + 1 != keyConstants[rangeStart].asLong()) { + closure.conditionalJump(rangeStart, Condition.LT, true); + registerDefaultEffort(++depth); + } + closure.conditionalJump(rangeEnd, Condition.LE, false); + registerEffort(rangeStart, rangeEnd, ++depth); + } + rangeStart = rangeEnd + 1; + rangeEnd = getSliceEnd(closure, rangeStart); + } + if (rangeStart == rangeEnd) { + closure.conditionalJumpOrDefault(rangeStart, Condition.EQ, true); + registerEffort(rangeStart, rangeEnd, ++depth); + registerDefaultEffort(depth); + } else { + if (rangeStart == 0 || keyConstants[rangeStart - 1].asLong() + 1 != keyConstants[rangeStart].asLong()) { + closure.conditionalJump(rangeStart, Condition.LT, true); + registerDefaultEffort(++depth); + } + closure.conditionalJumpOrDefault(rangeEnd, Condition.LE, true); + registerEffort(rangeStart, rangeEnd, ++depth); + registerDefaultEffort(depth); + } + } + } + + public static class BooleanStrategy extends SwitchStrategy { + + private static final double MIN_PROBABILITY = 0.00001; + + private final double[] probabilitySums; + + public BooleanStrategy(double[] keyProbabilities, Constant[] keyConstants) { + super(keyProbabilities, keyConstants); + probabilitySums = new double[keyProbabilities.length + 1]; + double sum = 0; + for (int i = 0; i < keyConstants.length; i++) { + sum += Math.max(keyProbabilities[i], MIN_PROBABILITY); + probabilitySums[i + 1] = sum; + } + } + + @Override + public void run(SwitchClosure closure) { + recurseBooleanSwitch(closure, 0, keyConstants.length - 1, 0); + } + + /** + * Recursively generate a list of comparisons that always subdivides the key list in the + * middle (in terms of probability, not index). + */ + private void recurseBooleanSwitch(SwitchClosure closure, int left, int right, int startDepth) { + assert startDepth < keyConstants.length * 3 : "runaway recursion in boolean switch"; + int depth = startDepth; + boolean leftBorder = left == 0; + boolean rightBorder = right == keyConstants.length - 1; + + if (left + 1 == right) { + // only two possible values + if (leftBorder || rightBorder || keyConstants[right].asLong() + 1 != keyConstants[right + 1].asLong() || keyConstants[left].asLong() + 1 != keyConstants[right].asLong()) { + closure.conditionalJump(left, Condition.EQ, false); + registerEffort(left, left, ++depth); + closure.conditionalJumpOrDefault(right, Condition.EQ, rightBorder); + registerEffort(right, right, ++depth); + registerDefaultEffort(depth); + } else { + closure.conditionalJump(left, Condition.EQ, false); + registerEffort(left, left, ++depth); + closure.conditionalJump(right, null, false); + registerEffort(right, right, depth); + } + return; + } + double probabilityStart = probabilitySums[left]; + double probabilityMiddle = (probabilityStart + probabilitySums[right + 1]) / 2; + assert probabilityStart >= probabilityStart; + int middle = left; + while (getSliceEnd(closure, middle + 1) < right && probabilitySums[getSliceEnd(closure, middle + 1)] < probabilityMiddle) { + middle = getSliceEnd(closure, middle + 1); + } + middle = getSliceEnd(closure, middle); + assert middle < keyConstants.length - 1; + + if (getSliceEnd(closure, left) == middle) { + if (left == 0) { + closure.conditionalJump(0, Condition.LT, true); + registerDefaultEffort(++depth); + } + closure.conditionalJump(middle, Condition.LE, false); + registerEffort(left, middle, ++depth); + + if (middle + 1 == right) { + closure.conditionalJumpOrDefault(right, Condition.EQ, rightBorder); + registerEffort(right, right, ++depth); + registerDefaultEffort(depth); + } else { + if (keyConstants[middle].asLong() + 1 != keyConstants[middle + 1].asLong()) { + closure.conditionalJump(middle + 1, Condition.LT, true); + registerDefaultEffort(++depth); + } + if (getSliceEnd(closure, middle + 1) == right) { + if (right == keyConstants.length - 1 || keyConstants[right].asLong() + 1 != keyConstants[right + 1].asLong()) { + closure.conditionalJumpOrDefault(right, Condition.LE, rightBorder); + registerEffort(middle + 1, right, ++depth); + registerDefaultEffort(depth); + } else { + closure.conditionalJump(middle + 1, null, false); + registerEffort(middle + 1, right, depth); + } + } else { + recurseBooleanSwitch(closure, middle + 1, right, depth); + } + } + } else if (getSliceEnd(closure, middle + 1) == right) { + if (rightBorder || keyConstants[right].asLong() + 1 != keyConstants[right + 1].asLong()) { + closure.conditionalJump(right, Condition.GT, true); + registerDefaultEffort(++depth); + } + closure.conditionalJump(middle + 1, Condition.GE, false); + registerEffort(middle + 1, right, ++depth); + recurseBooleanSwitch(closure, left, middle, depth); + } else { + Label label = closure.conditionalJump(middle + 1, Condition.GE); + depth++; + recurseBooleanSwitch(closure, left, middle, depth); + closure.bind(label); + recurseBooleanSwitch(closure, middle + 1, right, depth); + } + } + } + + public abstract void run(SwitchClosure closure); + + private static SwitchStrategy[] getStrategies(double[] keyProbabilities, Constant[] keyConstants, LabelRef[] keyTargets) { + SwitchStrategy[] strategies = new SwitchStrategy[]{new SequentialStrategy(keyProbabilities, keyConstants), new RangesStrategy(keyProbabilities, keyConstants), + new BooleanStrategy(keyProbabilities, keyConstants)}; + for (SwitchStrategy strategy : strategies) { + strategy.effortClosure = strategy.new EffortClosure(keyTargets); + strategy.run(strategy.effortClosure); + strategy.averageEffort = strategy.effortClosure.getAverageEffort(); + strategy.effortClosure = null; + } + return strategies; + } + + public static SwitchStrategy getBestStrategy(double[] keyProbabilities, Constant[] keyConstants, LabelRef[] keyTargets) { + SwitchStrategy[] strategies = getStrategies(keyProbabilities, keyConstants, keyTargets); + double bestEffort = Integer.MAX_VALUE; + SwitchStrategy bestStrategy = null; + for (SwitchStrategy strategy : strategies) { + if (strategy.getAverageEffort() < bestEffort) { + bestEffort = strategy.getAverageEffort(); + bestStrategy = strategy; + } + } + return bestStrategy; + } +}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/IntegerSwitchNode.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/IntegerSwitchNode.java Wed Dec 11 15:59:40 2013 +0100 @@ -54,6 +54,15 @@ assert keySuccessors.length == keys.length + 1; assert keySuccessors.length == keyProbabilities.length; this.keys = keys; + assert assertValues(); + assert assertSorted(); + } + + private boolean assertSorted() { + for (int i = 1; i < keys.length; i++) { + assert keys[i - 1] < keys[i]; + } + return true; } /** @@ -70,6 +79,11 @@ this(value, new AbstractBeginNode[successorCount], keys, keyProbabilities, keySuccessors); } + @Override + public boolean isSorted() { + return true; + } + /** * Gets the key at the specified index. *
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Wed Dec 11 15:59:40 2013 +0100 @@ -47,6 +47,7 @@ */ public SwitchNode(ValueNode value, AbstractBeginNode[] successors, int[] keySuccessors, double[] keyProbabilities) { super(StampFactory.forVoid()); + assert value.kind() == Kind.Int || value.kind() == Kind.Long || value.kind() == Kind.Object; assert keySuccessors.length == keyProbabilities.length; this.successors = new NodeSuccessorList<>(this, successors); this.value = value; @@ -65,6 +66,15 @@ return true; } + protected boolean assertValues() { + Kind kind = value.kind(); + for (int i = 0; i < keyCount(); i++) { + Constant key = keyAt(i); + assert key.getKind() == kind; + } + return true; + } + @Override public double probability(AbstractBeginNode successor) { double sum = 0; @@ -107,6 +117,8 @@ return value; } + public abstract boolean isSorted(); + /** * The number of distinct keys in this switch. */
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/TypeSwitchNode.java Wed Dec 11 15:15:35 2013 +0100 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/TypeSwitchNode.java Wed Dec 11 15:59:40 2013 +0100 @@ -56,6 +56,25 @@ assert successors.length <= keys.length + 1; assert keySuccessors.length == keyProbabilities.length; this.keys = keys; + assert assertValues(); + } + + @Override + public boolean isSorted() { + Kind kind = value().kind(); + if (kind.isNumericInteger()) { + Constant lastKey = null; + for (int i = 0; i < keyCount(); i++) { + Constant key = keyAt(i); + if (lastKey != null && key.asLong() <= lastKey.asLong()) { + return false; + } + lastKey = key; + } + return true; + } else { + return false; + } } @Override