Mercurial > hg > truffle
changeset 5698:764db9ada24f
rework of switch operations: unify lookup- and tableswitch, introduce switch lir instructions
line wrap: on
line diff
--- a/graal/com.oracle.graal.bytecode/src/com/oracle/graal/bytecode/BytecodeLookupSwitch.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.bytecode/src/com/oracle/graal/bytecode/BytecodeLookupSwitch.java Wed Jun 27 11:51:18 2012 +0200 @@ -41,11 +41,6 @@ } @Override - public int defaultOffset() { - return stream.readInt(alignedBci); - } - - @Override public int offsetAt(int i) { return stream.readInt(alignedBci + OFFSET_TO_FIRST_PAIR_OFFSET + PAIR_SIZE * i); }
--- a/graal/com.oracle.graal.bytecode/src/com/oracle/graal/bytecode/BytecodeSwitch.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.bytecode/src/com/oracle/graal/bytecode/BytecodeSwitch.java Wed Jun 27 11:51:18 2012 +0200 @@ -80,7 +80,9 @@ * Gets the offset from the start of the switch instruction to the default switch target. * @return the offset to the default switch target */ - public abstract int defaultOffset(); + public int defaultOffset() { + return stream.readInt(alignedBci); + } /** * Gets the key at {@code i}'th switch target index. @@ -107,4 +109,5 @@ * @return the total size in bytes of the switch instruction */ public abstract int size(); + }
--- a/graal/com.oracle.graal.bytecode/src/com/oracle/graal/bytecode/BytecodeTableSwitch.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.bytecode/src/com/oracle/graal/bytecode/BytecodeTableSwitch.java Wed Jun 27 11:51:18 2012 +0200 @@ -62,11 +62,6 @@ } @Override - public int defaultOffset() { - return stream.readInt(alignedBci); - } - - @Override public int offsetAt(int i) { return stream.readInt(alignedBci + OFFSET_TO_FIRST_JUMP_OFFSET + JUMP_OFFSET_SIZE * i); }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalOptions.java Wed Jun 27 11:51:18 2012 +0200 @@ -187,6 +187,7 @@ // Translating tableswitch instructions public static int SequentialSwitchLimit = 4; public static int RangeTestsSwitchDensity = 5; + public static double MinTableSwitchDensity = 0.5; public static boolean DetailedAsserts = ____;
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/ControlFlowOptimizer.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/alloc/ControlFlowOptimizer.java Wed Jun 27 11:51:18 2012 +0200 @@ -27,6 +27,7 @@ import com.oracle.graal.compiler.util.*; import com.oracle.graal.debug.*; import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.FallThroughOp; import com.oracle.graal.lir.cfg.*; /** @@ -178,6 +179,16 @@ } } } + // TODO(ls) enable this optimization +// lastOp = instructions.get(instructions.size() - 1); +// if (lastOp instanceof FallThroughOp) { +// FallThroughOp fallThrough = (FallThroughOp) lastOp; +// if (fallThrough.fallThroughTarget() != null && lastOp.info == null) { +// if (fallThrough.fallThroughTarget().label() == ((StandardOp.LabelOp) code.get(i + 1).lir.get(0)).getLabel()) { +// fallThrough.setFallThroughTarget(null); +// } +// } +// } } assert verify(code);
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java Wed Jun 27 11:51:18 2012 +0200 @@ -686,7 +686,6 @@ @Override public void emitIf(IfNode x) { - assert x.defaultSuccessor() == x.falseSuccessor() : "wrong destination"; emitBranch(x.compare(), getLIRBlock(x.trueSuccessor()), getLIRBlock(x.falseSuccessor()), null); } @@ -1014,128 +1013,138 @@ } } + /** + * This method tries to create a switch implementation that is optimal for the given switch. + * It will either generate a sequential if/then/else cascade, a set of range tests or a table switch. + * + * If the given switch does not contain int keys, it will always create a sequential implementation. + */ @Override - public void emitLookupSwitch(LookupSwitchNode x) { - Variable tag = load(operand(x.value())); - if (x.numberOfCases() == 0 || x.numberOfCases() < GraalOptions.SequentialSwitchLimit) { - int len = x.numberOfCases(); - for (int i = 0; i < len; i++) { - emitBranch(tag, Constant.forInt(x.keyAt(i)), Condition.EQ, false, getLIRBlock(x.blockSuccessor(i)), null); - } + public void emitSwitch(SwitchNode x) { + int keyCount = x.keyCount(); + if (keyCount == 0) { emitJump(getLIRBlock(x.defaultSuccessor()), null); } else { - visitSwitchRanges(createSwitchRanges(x, null), tag, getLIRBlock(x.defaultSuccessor())); - } - } - - @Override - public void emitTypeSwitch(TypeSwitchNode x) { - Variable tag = load(operand(x.value())); - int len = x.numberOfCases(); - for (int i = 0; i < len; i++) { - ResolvedJavaType type = x.keyAt(i); - emitBranch(tag, type.getEncoding(Representation.ObjectHub), Condition.EQ, false, getLIRBlock(x.blockSuccessor(i)), null); - } - emitJump(getLIRBlock(x.defaultSuccessor()), null); - } - - @Override - public void emitTableSwitch(TableSwitchNode x) { - Variable value = load(operand(x.value())); - // TODO: tune the defaults for the controls used to determine what kind of translation to use - if (x.numberOfCases() == 0 || x.numberOfCases() <= GraalOptions.SequentialSwitchLimit) { - int loKey = x.lowKey(); - int len = x.numberOfCases(); - for (int i = 0; i < len; i++) { - emitBranch(value, Constant.forInt(i + loKey), Condition.EQ, false, getLIRBlock(x.blockSuccessor(i)), null); - } - emitJump(getLIRBlock(x.defaultSuccessor()), null); - } else { - SwitchRange[] switchRanges = createSwitchRanges(null, x); - int rangeDensity = x.numberOfCases() / switchRanges.length; - if (rangeDensity >= GraalOptions.RangeTestsSwitchDensity) { - visitSwitchRanges(switchRanges, value, getLIRBlock(x.defaultSuccessor())); + Variable value = load(operand(x.value())); + LabelRef defaultTarget = x.defaultSuccessor() == null ? null : getLIRBlock(x.defaultSuccessor()); + if (value.kind == Kind.Object || keyCount < GraalOptions.SequentialSwitchLimit) { + // only a few entries + emitSequentialSwitch(x, value, defaultTarget); } else { - LabelRef[] targets = new LabelRef[x.numberOfCases()]; - for (int i = 0; i < x.numberOfCases(); ++i) { - targets[i] = getLIRBlock(x.blockSuccessor(i)); + long valueRange = x.keyAt(keyCount - 1).asLong() - x.keyAt(0).asLong() + 1; + int switchRangeCount = switchRangeCount(x); + int rangeDensity = keyCount / switchRangeCount; + if (rangeDensity >= GraalOptions.RangeTestsSwitchDensity) { + emitSwitchRanges(x, switchRangeCount, value, defaultTarget); + } else if (keyCount / (double) valueRange >= GraalOptions.MinTableSwitchDensity) { + 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 { + emitSequentialSwitch(x, value, defaultTarget); } - emitTableSwitch(x.lowKey(), getLIRBlock(x.defaultSuccessor()), targets, value); } } } - protected abstract void emitTableSwitch(int lowKey, LabelRef defaultTarget, LabelRef[] targets, Value index); + private void emitSequentialSwitch(final SwitchNode x, Variable key, LabelRef defaultTarget) { + int keyCount = x.keyCount(); + Integer[] 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 x.keyProbability(o1) < x.keyProbability(o2) ? 1 : x.keyProbability(o1) > x.keyProbability(o2) ? -1 : 0; + } + }); + 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]); + } + emitSequentialSwitch(keyConstants, keyTargets, defaultTarget, key); + } - // the range of values in a lookupswitch or tableswitch statement - private static final class SwitchRange { - protected final int lowKey; - protected int highKey; - protected final LabelRef sux; + 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 emitTableSwitch(int lowKey, LabelRef defaultTarget, LabelRef[] targets, Value key); - SwitchRange(int lowKey, LabelRef sux) { - this.lowKey = lowKey; - this.highKey = lowKey; - this.sux = sux; + private static int switchRangeCount(SwitchNode x) { + int keyCount = x.keyCount(); + int i = 0; + while (i < keyCount && x.keySuccessorIndex(i) == x.defaultSuccessorIndex()) { + i++; + } + if (i == keyCount) { + return 0; + } else { + int switchRangeCount = 1; + i++; + for (; i < keyCount; i++) { + if (x.keySuccessorIndex(i) != x.defaultSuccessorIndex()) { + if (x.keyAt(i).asInt() != x.keyAt(i - 1).asInt() + 1 || x.keySuccessorIndex(i) != x.keySuccessorIndex(i - 1)) { + switchRangeCount++; + } + } + } + return switchRangeCount; } } - private SwitchRange[] createSwitchRanges(LookupSwitchNode ls, TableSwitchNode ts) { - // Only one of the parameters is used, but code is shared because it is mostly the same. - SwitchNode x = ls != null ? ls : ts; - // we expect the keys to be sorted by increasing value - List<SwitchRange> res = new ArrayList<>(x.numberOfCases()); - int len = x.numberOfCases(); - if (len > 0) { - LabelRef defaultSux = getLIRBlock(x.defaultSuccessor()); - int key = ls != null ? ls.keyAt(0) : ts.lowKey(); - LabelRef sux = getLIRBlock(x.blockSuccessor(0)); - SwitchRange range = new SwitchRange(key, sux); - for (int i = 1; i < len; i++) { - int newKey = ls != null ? ls.keyAt(i) : key + 1; - LabelRef newSux = getLIRBlock(x.blockSuccessor(i)); - if (key + 1 == newKey && sux == newSux) { - // still in same range - range.highKey = newKey; - } else { - // skip tests which explicitly dispatch to the default - if (range.sux != defaultSux) { - res.add(range); + private void emitSwitchRanges(SwitchNode x, int switchRangeCount, Variable keyValue, LabelRef defaultTarget) { + 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 = 0; + int i = 0; + while (i < keyCount && x.keySuccessorIndex(i) == x.defaultSuccessorIndex()) { + i++; + } + if (i == keyCount) { + emitJump(defaultTarget, null); + } else { + int key = x.keyAt(i).asInt(); + int successor = x.keySuccessorIndex(i); + lowKeys[current] = key; + highKeys[current] = key; + targets[current] = getLIRBlock(x.blockSuccessor(successor)); + i++; + for (; i < keyCount; i++) { + int newSuccessor = x.keySuccessorIndex(i); + if (newSuccessor != defaultSuccessor) { + int newKey = x.keyAt(i).asInt(); + 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)); } - range = new SwitchRange(newKey, newSux); + key = newKey; } - key = newKey; - sux = newSux; + successor = newSuccessor; } - if (res.size() == 0 || res.get(res.size() - 1) != range) { - res.add(range); - } + assert current == switchRangeCount - 1; + emitSwitchRanges(lowKeys, highKeys, targets, defaultTarget, keyValue); } - return res.toArray(new SwitchRange[res.size()]); } - private void visitSwitchRanges(SwitchRange[] x, Variable value, LabelRef defaultSux) { - for (int i = 0; i < x.length; i++) { - SwitchRange oneRange = x[i]; - int lowKey = oneRange.lowKey; - int highKey = oneRange.highKey; - LabelRef dest = oneRange.sux; - if (lowKey == highKey) { - emitBranch(value, Constant.forInt(lowKey), Condition.EQ, false, dest, null); - } else if (highKey - lowKey == 1) { - emitBranch(value, Constant.forInt(lowKey), Condition.EQ, false, dest, null); - emitBranch(value, Constant.forInt(highKey), Condition.EQ, false, dest, null); - } else { - Label l = new Label(); - emitBranch(value, Constant.forInt(lowKey), Condition.LT, false, LabelRef.forLabel(l), null); - emitBranch(value, Constant.forInt(highKey), Condition.LE, false, dest, null); - emitLabel(l, false); - } - } - emitJump(defaultSux, null); - } - - protected XirArgument toXirArgument(Value v) { if (v == null) { return null; @@ -1332,68 +1341,6 @@ return emitMove(location); } - SwitchRange[] createLookupRanges(LookupSwitchNode x) { - // we expect the keys to be sorted by increasing value - List<SwitchRange> res = new ArrayList<>(x.numberOfCases()); - int len = x.numberOfCases(); - if (len > 0) { - LabelRef defaultSux = getLIRBlock(x.defaultSuccessor()); - int key = x.keyAt(0); - LabelRef sux = getLIRBlock(x.blockSuccessor(0)); - SwitchRange range = new SwitchRange(key, sux); - for (int i = 1; i < len; i++) { - int newKey = x.keyAt(i); - LabelRef newSux = getLIRBlock(x.blockSuccessor(i)); - if (key + 1 == newKey && sux == newSux) { - // still in same range - range.highKey = newKey; - } else { - // skip tests which explicitly dispatch to the default - if (range.sux != defaultSux) { - res.add(range); - } - range = new SwitchRange(newKey, newSux); - } - key = newKey; - sux = newSux; - } - if (res.size() == 0 || res.get(res.size() - 1) != range) { - res.add(range); - } - } - return res.toArray(new SwitchRange[res.size()]); - } - - SwitchRange[] createLookupRanges(TableSwitchNode x) { - // TODO: try to merge this with the code for LookupSwitch - List<SwitchRange> res = new ArrayList<>(x.numberOfCases()); - int len = x.numberOfCases(); - if (len > 0) { - LabelRef sux = getLIRBlock(x.blockSuccessor(0)); - int key = x.lowKey(); - LabelRef defaultSux = getLIRBlock(x.defaultSuccessor()); - SwitchRange range = new SwitchRange(key, sux); - for (int i = 0; i < len; i++, key++) { - LabelRef newSux = getLIRBlock(x.blockSuccessor(i)); - if (sux == newSux) { - // still in same range - range.highKey = key; - } else { - // skip tests which explicitly dispatch to the default - if (sux != defaultSux) { - res.add(range); - } - range = new SwitchRange(key, newSux); - } - sux = newSux; - } - if (res.size() == 0 || res.get(res.size() - 1) != range) { - res.add(range); - } - } - return res.toArray(new SwitchRange[res.size()]); - } - protected XirSupport site(ValueNode x) { return xirSupport.site(x, null); }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/target/amd64/AMD64LIRGenerator.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/target/amd64/AMD64LIRGenerator.java Wed Jun 27 11:51:18 2012 +0200 @@ -54,12 +54,7 @@ import com.oracle.graal.lir.amd64.AMD64Call.DirectCallOp; import com.oracle.graal.lir.amd64.AMD64Call.IndirectCallOp; import com.oracle.graal.lir.amd64.AMD64Compare.CompareOp; -import com.oracle.graal.lir.amd64.AMD64ControlFlow.BranchOp; -import com.oracle.graal.lir.amd64.AMD64ControlFlow.CondMoveOp; -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.TableSwitchOp; +import com.oracle.graal.lir.amd64.AMD64ControlFlow.*; import com.oracle.graal.lir.amd64.AMD64Move.CompareAndSwapOp; import com.oracle.graal.lir.amd64.AMD64Move.LeaOp; import com.oracle.graal.lir.amd64.AMD64Move.LoadOp; @@ -567,9 +562,25 @@ } @Override - protected void emitTableSwitch(int lowKey, LabelRef defaultTarget, LabelRef[] targets, Value index) { + 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 - Variable tmp = emitMove(index); + if (key.kind == Kind.Int) { + append(new SequentialSwitchOp(keyConstants, keyTargets, defaultTarget, key)); + } else { + assert key.kind == Kind.Object; + 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)); + } + + @Override + protected void emitTableSwitch(int lowKey, LabelRef defaultTarget, LabelRef[] targets, Value key) { + // Making a copy of the switch value is necessary because jump table destroys the input value + Variable tmp = emitMove(key); append(new TableSwitchOp(lowKey, defaultTarget, targets, tmp, newVariable(target.wordKind))); }
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/util/InliningUtil.java Wed Jun 27 11:51:18 2012 +0200 @@ -401,7 +401,7 @@ ResolvedJavaType[] types = new ResolvedJavaType[ptypes.length]; double[] probabilities = new double[ptypes.length + 1]; BeginNode[] successors = new BeginNode[ptypes.length + 1]; - + int[] keySuccessors = new int[ptypes.length + 1]; for (int i = 0; i < ptypes.length; i++) { types[i] = ptypes[i].type; probabilities[i] = ptypes[i].probability; @@ -412,12 +412,14 @@ entry = endNode; } successors[i] = BeginNode.begin(entry); + keySuccessors[i] = i; } assert !(unknownTypeSux instanceof MergeNode); successors[successors.length - 1] = BeginNode.begin(unknownTypeSux); probabilities[successors.length - 1] = notRecordedTypeProbability; + keySuccessors[successors.length - 1] = successors.length - 1; - TypeSwitchNode typeSwitch = graph.add(new TypeSwitchNode(objectClassNode, successors, types, probabilities)); + TypeSwitchNode typeSwitch = graph.add(new TypeSwitchNode(objectClassNode, successors, probabilities, types, probabilities, keySuccessors)); return typeSwitch; }
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/BciBlockMapping.java Wed Jun 27 11:51:18 2012 +0200 @@ -404,10 +404,15 @@ } private void addSwitchSuccessors(int predBci, BytecodeSwitch bswitch) { + // adds distinct targets to the successor list + Collection<Integer> targets = new TreeSet<>(); for (int i = 0; i < bswitch.numberOfCases(); i++) { - addSuccessor(predBci, makeBlock(bswitch.targetAt(i))); + targets.add(bswitch.targetAt(i)); } - addSuccessor(predBci, makeBlock(bswitch.defaultTarget())); + targets.add(bswitch.defaultTarget()); + for (int targetBci : targets) { + addSuccessor(predBci, makeBlock(targetBci)); + } } private void addSuccessor(int predBci, Block sux) {
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java Wed Jun 27 11:51:18 2012 +0200 @@ -1037,22 +1037,6 @@ appendGoto(createTarget(successor, frameState)); } - private void genTableswitch() { - int bci = bci(); - ValueNode value = frameState.ipop(); - BytecodeTableSwitch ts = new BytecodeTableSwitch(stream(), bci); - - int nofCases = ts.numberOfCases() + 1; // including default case - assert currentBlock.numNormalSuccessors() == nofCases; - - double[] probabilities = switchProbability(nofCases, bci); - TableSwitchNode tableSwitch = currentGraph.add(new TableSwitchNode(value, ts.lowKey(), probabilities)); - for (int i = 0; i < nofCases; ++i) { - tableSwitch.setBlockSuccessor(i, createBlockTarget(probabilities[i], currentBlock.successors.get(i), frameState)); - } - append(tableSwitch); - } - private double[] switchProbability(int numberOfCases, int bci) { double[] prob = profilingInfo.getSwitchProbabilities(bci); if (prob != null) { @@ -1077,22 +1061,35 @@ return true; } - private void genLookupswitch() { + private void genSwitch(BytecodeSwitch bs) { int bci = bci(); ValueNode value = frameState.ipop(); - BytecodeLookupSwitch ls = new BytecodeLookupSwitch(stream(), bci); + + int nofCases = bs.numberOfCases(); - int nofCases = ls.numberOfCases() + 1; // including default case - assert currentBlock.numNormalSuccessors() == nofCases; + Map<Integer, Integer> bciToSuccessorIndex = new HashMap<>(); + int successorCount = currentBlock.successors.size(); + for (int i = 0; i < successorCount; i++) { + assert !bciToSuccessorIndex.containsKey(currentBlock.successors.get(i).startBci); + if (!bciToSuccessorIndex.containsKey(currentBlock.successors.get(i).startBci)) { + bciToSuccessorIndex.put(currentBlock.successors.get(i).startBci, i); + } + } - int[] keys = new int[nofCases - 1]; - for (int i = 0; i < nofCases - 1; ++i) { - keys[i] = ls.keyAt(i); + double[] keyProbabilities = switchProbability(nofCases + 1, bci); + + int[] keys = new int[nofCases]; + int[] keySuccessors = new int[nofCases + 1]; + for (int i = 0; i < nofCases; i++) { + keys[i] = bs.keyAt(i); + keySuccessors[i] = bciToSuccessorIndex.get(bs.targetAt(i)); } - double[] probabilities = switchProbability(nofCases, bci); - LookupSwitchNode lookupSwitch = currentGraph.add(new LookupSwitchNode(value, keys, probabilities)); - for (int i = 0; i < nofCases; ++i) { - lookupSwitch.setBlockSuccessor(i, createBlockTarget(probabilities[i], currentBlock.successors.get(i), frameState)); + keySuccessors[nofCases] = bciToSuccessorIndex.get(bs.defaultTarget()); + + double[] successorProbabilities = IntegerSwitchNode.successorProbabilites(successorCount, keySuccessors, keyProbabilities); + IntegerSwitchNode lookupSwitch = currentGraph.add(new IntegerSwitchNode(value, successorCount, keys, keyProbabilities, keySuccessors)); + for (int i = 0; i < successorCount; i++) { + lookupSwitch.setBlockSuccessor(i, createBlockTarget(successorProbabilities[i], currentBlock.successors.get(i), frameState)); } append(lookupSwitch); } @@ -1691,8 +1688,8 @@ case GOTO : genGoto(); break; case JSR : genJsr(stream.readBranchDest()); break; case RET : genRet(stream.readLocalIndex()); break; - case TABLESWITCH : genTableswitch(); break; - case LOOKUPSWITCH : genLookupswitch(); break; + case TABLESWITCH : genSwitch(new BytecodeTableSwitch(stream(), bci())); break; + case LOOKUPSWITCH : genSwitch(new BytecodeLookupSwitch(stream(), bci())); break; case IRETURN : genReturn(frameState.ipop()); break; case LRETURN : genReturn(frameState.lpop()); break; case FRETURN : genReturn(frameState.fpop()); break;
--- a/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64ControlFlow.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64ControlFlow.java Wed Jun 27 11:51:18 2012 +0200 @@ -35,6 +35,7 @@ import com.oracle.graal.api.meta.*; import com.oracle.graal.graph.*; import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.FallThroughOp; import com.oracle.graal.lir.asm.*; import com.oracle.graal.nodes.calc.*; @@ -171,6 +172,155 @@ } } + public static class SequentialSwitchOp extends AMD64LIRInstruction implements FallThroughOp { + private final Constant[] keyConstants; + private final LabelRef[] keyTargets; + private LabelRef defaultTarget; + + public SequentialSwitchOp(Constant[] keyConstants, LabelRef[] keyTargets, LabelRef defaultTarget, Value key, Value... temp) { + super("SEQUENTIAL_SWITCH", LIRInstruction.NO_OPERANDS, null, LIRInstruction.NO_OPERANDS, new Value[] {key}, temp); + assert keyConstants.length == keyTargets.length; + this.keyConstants = keyConstants; + this.keyTargets = keyTargets; + this.defaultTarget = defaultTarget; + } + + @Override + public void emitCode(TargetMethodAssembler tasm, AMD64MacroAssembler masm) { + Value key = alive(0); + if (key.kind == Kind.Int) { + Register intKey = asIntReg(key); + for (int i = 0; i < keyConstants.length; i++) { + masm.cmpl(intKey, tasm.asIntConst(keyConstants[i])); + masm.jcc(ConditionFlag.equal, keyTargets[i].label()); + } + } else if (key.kind == Kind.Object) { + Register intKey = asObjectReg(key); + Register temp = asObjectReg(temp(0)); + for (int i = 0; i < keyConstants.length; i++) { + AMD64Move.move(tasm, masm, temp.asValue(Kind.Object), keyConstants[i]); + masm.cmpptr(intKey, temp); + masm.jcc(ConditionFlag.equal, keyTargets[i].label()); + } + } else { + throw new GraalInternalError("sequential switch only supported for int and object"); + } + if (defaultTarget != null) { + masm.jmp(defaultTarget.label()); + } else { + masm.hlt(); + } + } + + @Override + public String operationString() { + StringBuilder buf = new StringBuilder(super.operationString()); + buf.append("\ndefault: [").append(defaultTarget).append(']'); + for (int i = 0; i < keyConstants.length; i++) { + buf.append("\ncase ").append(keyConstants[i]).append(": [").append(keyTargets[i]).append("]"); + } + return buf.toString(); + } + + @Override + protected EnumSet<OperandFlag> flagsFor(OperandMode mode, int index) { + if (mode == OperandMode.Alive && index == 0) { + return EnumSet.of(OperandFlag.Register); + } else if (mode == OperandMode.Temp && index == 0) { + return EnumSet.of(OperandFlag.Register); + } + throw GraalInternalError.shouldNotReachHere(); + } + + @Override + public LabelRef fallThroughTarget() { + return defaultTarget; + } + + @Override + public void setFallThroughTarget(LabelRef target) { + defaultTarget = target; + } + } + + public static class SwitchRangesOp extends AMD64LIRInstruction implements FallThroughOp { + private final LabelRef[] keyTargets; + private LabelRef defaultTarget; + private final int[] lowKeys; + private final int[] highKeys; + + public SwitchRangesOp(int[] lowKeys, int[] highKeys, LabelRef[] keyTargets, LabelRef defaultTarget, Value key) { + super("SWITCH_RANGES", LIRInstruction.NO_OPERANDS, null, LIRInstruction.NO_OPERANDS, new Value[] {key}, LIRInstruction.NO_OPERANDS); + assert lowKeys.length == keyTargets.length; + assert highKeys.length == keyTargets.length; + assert key.kind == Kind.Int; + this.lowKeys = lowKeys; + this.highKeys = highKeys; + this.keyTargets = keyTargets; + this.defaultTarget = defaultTarget; + } + + @Override + public void emitCode(TargetMethodAssembler tasm, AMD64MacroAssembler masm) { + Register key = asIntReg(alive(0)); + for (int i = 0; i < lowKeys.length; i++) { + int lowKey = lowKeys[i]; + int highKey = highKeys[i]; + if (lowKey == highKey) { + masm.cmpl(key, lowKey); + masm.jcc(ConditionFlag.equal, keyTargets[i].label()); + } else if (lowKey + 1 == highKey) { + masm.cmpl(key, lowKey); + masm.jcc(ConditionFlag.equal, keyTargets[i].label()); + masm.cmpl(key, highKey); + masm.jcc(ConditionFlag.equal, keyTargets[i].label()); + } else { + Label skip = new Label(); + masm.cmpl(key, lowKey); + masm.jcc(ConditionFlag.less, skip); + masm.cmpl(key, highKey); + masm.jcc(ConditionFlag.lessEqual, keyTargets[i].label()); + masm.bind(skip); + } + } + if (defaultTarget != null) { + masm.jmp(defaultTarget.label()); + } else { + masm.hlt(); + } + } + + @Override + public String operationString() { + StringBuilder buf = new StringBuilder(super.operationString()); + buf.append("\ndefault: [").append(defaultTarget).append(']'); + for (int i = 0; i < lowKeys.length; i++) { + buf.append("\ncase ").append(lowKeys[i]).append(" - ").append(highKeys[i]).append(": [").append(keyTargets[i]).append("]"); + } + return buf.toString(); + } + + @Override + protected EnumSet<OperandFlag> flagsFor(OperandMode mode, int index) { + if (mode == OperandMode.Alive && index == 0) { + return EnumSet.of(OperandFlag.Register); + } else if (mode == OperandMode.Temp && index == 0) { + return EnumSet.of(OperandFlag.Register); + } + throw GraalInternalError.shouldNotReachHere(); + } + + @Override + public LabelRef fallThroughTarget() { + return defaultTarget; + } + + @Override + public void setFallThroughTarget(LabelRef target) { + defaultTarget = target; + } + } + public static class CondMoveOp extends AMD64LIRInstruction { private final ConditionFlag condition; @@ -237,7 +387,6 @@ } } - private static void tableswitch(TargetMethodAssembler tasm, AMD64MacroAssembler masm, int lowKey, LabelRef defaultTarget, LabelRef[] targets, Register value, Register scratch) { Buffer buf = masm.codeBuffer; // Compare index against jump table bounds @@ -251,7 +400,9 @@ } // Jump to default target if index is not within the jump table - masm.jcc(ConditionFlag.above, defaultTarget.label()); + if (defaultTarget != null) { + masm.jcc(ConditionFlag.above, defaultTarget.label()); + } // Set scratch to address of jump table int leaPos = buf.position(); @@ -284,7 +435,7 @@ } else { label.addPatchAt(buf.position()); - buf.emitByte(0); // psuedo-opcode for jump table entry + buf.emitByte(0); // pseudo-opcode for jump table entry buf.emitShort(offsetToJumpTableBase); buf.emitByte(0); // padding to make jump table entry 4 bytes wide }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/StandardOp.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/StandardOp.java Wed Jun 27 11:51:18 2012 +0200 @@ -38,6 +38,15 @@ private static Value[] EMPTY = new Value[0]; /** + * Marker interface for LIR ops that can fall through to the next operation, like a switch statement. + * setFallThroughTarget(null) can be used to make the operation fall through to the next one. + */ + public interface FallThroughOp { + LabelRef fallThroughTarget(); + void setFallThroughTarget(LabelRef target); + } + + /** * LIR operation that defines the position of a label. * The first operation of every block must implement this interface. */
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/ControlSplitNode.java Wed Jun 27 11:51:18 2012 +0200 @@ -61,14 +61,6 @@ branchProbability[successorIndex] = x; } - /** - * Gets the successor corresponding to the default (fall through) case. - * @return the default successor - */ - public FixedNode defaultSuccessor() { - return blockSuccessor(blockSuccessorCount() - 1); - } - public Iterable<BeginNode> blockSuccessors() { return new Iterable<BeginNode>() { @Override
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Wed Jun 27 11:51:18 2012 +0200 @@ -253,7 +253,7 @@ for (int i = 0; i < node.blockSuccessorCount(); i++) { BeginNode successor = node.blockSuccessor(i); node.setBlockSuccessor(i, null); - if (successor != begin && successor.isAlive()) { + if (successor != null && successor != begin && successor.isAlive()) { GraphUtil.killCFG(successor); } } @@ -261,7 +261,7 @@ node.replaceAtPredecessor(begin); node.safeDelete(); } else { - assert node.isDeleted(); + assert node.isDeleted() : node + " " + begin; } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/IntegerSwitchNode.java Wed Jun 27 11:51:18 2012 +0200 @@ -0,0 +1,168 @@ +/* + * Copyright (c) 2009, 2011, 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.nodes.extended; + +import java.util.*; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; +import com.oracle.graal.nodes.util.*; + +/** + * The {@code IntegerSwitchNode} represents a switch on integer keys, with a sorted array of key values. + * The actual implementation of the switch will be decided by the backend. + */ +public final class IntegerSwitchNode extends SwitchNode implements LIRLowerable, Simplifiable { + + private final int[] keys; + + /** + * Constructs a integer switch instruction. The keyProbabilities and keySuccessors array contain key.length + 1 + * entries, the last entry describes the default (fall through) case. + * + * @param value the instruction producing the value being switched on + * @param successors the list of successors + * @param keys the sorted list of keys + * @param keyProbabilities the probabilities of the keys + * @param keySuccessor the successor index for each key + */ + public IntegerSwitchNode(ValueNode value, BeginNode[] successors, int[] keys, double[] keyProbabilities, int[] keySuccessors) { + super(value, successors, successorProbabilites(successors.length, keySuccessors, keyProbabilities), keySuccessors, keyProbabilities); + assert keySuccessors.length == keys.length + 1; + assert keySuccessors.length == keyProbabilities.length; + this.keys = keys; + } + + /** + * Constructs a integer switch instruction. The keyProbabilities and keySuccessors array contain key.length + 1 + * entries, the last entry describes the default (fall through) case. + * + * @param value the instruction producing the value being switched on + * @param successorCount the number of successors + * @param keys the sorted list of keys + * @param keyProbabilities the probabilities of the keys + * @param keySuccessor the successor index for each key + */ + public IntegerSwitchNode(ValueNode value, int successorCount, int[] keys, double[] keyProbabilities, int[] keySuccessors) { + this(value, new BeginNode[successorCount], keys, keyProbabilities, keySuccessors); + } + + /** + * Gets the key at the specified index. + * @param i the index + * @return the key at that index + */ + @Override + public Constant keyAt(int i) { + return Constant.forInt(keys[i]); + } + + @Override + public int keyCount() { + return keys.length; + } + + @Override + public void generate(LIRGeneratorTool gen) { + gen.emitSwitch(this); + } + + @Override + public void simplify(SimplifierTool tool) { + if (value() instanceof ConstantNode) { + int constant = value().asConstant().asInt(); + + int survivingEdge = keySuccessorIndex(keyCount()); + for (int i = 0; i < keyCount(); i++) { + if (keys[i] == constant) { + survivingEdge = keySuccessorIndex(i); + } + } + for (int i = 0; i < blockSuccessorCount(); i++) { + if (i != survivingEdge) { + tool.deleteBranch(blockSuccessor(i)); + } + } + tool.addToWorkList(blockSuccessor(survivingEdge)); + ((StructuredGraph) graph()).removeSplitPropagate(this, survivingEdge); + } + if (value() != null) { + IntegerStamp stamp = value().integerStamp(); + if (!stamp.isUnrestricted()) { + int validKeys = 0; + for (int i = 0; i < keyCount(); i++) { + if (stamp.contains(keys[i])) { + validKeys++; + } + } + if (validKeys == 0) { + tool.addToWorkList(defaultSuccessor()); + ((StructuredGraph) graph()).removeSplitPropagate(this, defaultSuccessorIndex()); + } else if (validKeys != keys.length) { + ArrayList<BeginNode> newSuccessors = new ArrayList<>(blockSuccessorCount()); + int[] newKeys = new int[validKeys]; + int[] newKeySuccessors = new int [validKeys + 1]; + double[] newKeyProbabilities = new double[validKeys + 1]; + double totalProbability = 0; + int current = 0; + for (int i = 0; i < keyCount() + 1; i++) { + if (i == keyCount() || stamp.contains(keys[i])) { + int index = newSuccessors.indexOf(keySuccessor(i)); + if (index == -1) { + index = newSuccessors.size(); + newSuccessors.add(keySuccessor(i)); + } + newKeySuccessors[current] = index; + if (i < keyCount()) { + newKeys[current] = keys[i]; + } + newKeyProbabilities[current] = keyProbability(i); + totalProbability += keyProbability(i); + current++; + } + } + if (totalProbability > 0) { + for (int i = 0; i < current; i++) { + newKeyProbabilities[i] /= totalProbability; + } + } + + for (int i = 0; i < blockSuccessorCount(); i++) { + BeginNode successor = blockSuccessor(i); + if (!newSuccessors.contains(successor)) { + tool.deleteBranch(successor); + } + setBlockSuccessor(i, null); + } + + BeginNode[] successorsArray = newSuccessors.toArray(new BeginNode[newSuccessors.size()]); + IntegerSwitchNode newSwitch = graph().add(new IntegerSwitchNode(value(), successorsArray, newKeys, newKeyProbabilities, newKeySuccessors)); + ((FixedWithNextNode) predecessor()).setNext(newSwitch); + GraphUtil.killWithUnusedFloatingInputs(this); + } + } + } + } +}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/LookupSwitchNode.java Tue Jun 26 16:54:58 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,94 +0,0 @@ -/* - * Copyright (c) 2009, 2011, 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.nodes.extended; - -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.spi.*; - -/** - * The {@code LookupSwitchNode} represents a lookup switch bytecode, which has a sorted - * array of key values. - */ -public final class LookupSwitchNode extends SwitchNode implements LIRLowerable, Simplifiable { - - private final int[] keys; - - /** - * Constructs a new LookupSwitch instruction. - * @param value the instruction producing the value being switched on - * @param successors the list of successors - * @param keys the list of keys, sorted - */ - public LookupSwitchNode(ValueNode value, BeginNode[] successors, int[] keys, double[] probability) { - super(value, successors, probability); - assert successors.length == keys.length + 1; - this.keys = keys; - } - - public LookupSwitchNode(ValueNode value, int[] keys, double[] switchProbability) { - this(value, new BeginNode[switchProbability.length], keys, switchProbability); - } - - /** - * Gets the key at the specified index. - * @param i the index - * @return the key at that index - */ - public int keyAt(int i) { - return keys[i]; - } - - public int keysLength() { - return keys.length; - } - - @Override - public void generate(LIRGeneratorTool gen) { - gen.emitLookupSwitch(this); - } - - @Override - public void simplify(SimplifierTool tool) { - if (value() instanceof ConstantNode) { - ConstantNode constant = (ConstantNode) value(); - int value = constant.value.asInt(); - - int remainingSuxIndex = blockSuccessorCount() - 1; - for (int i = 0; i < keys.length; i++) { - if (value == keys[i]) { - remainingSuxIndex = i; - break; - } - } - - for (int i = 0; i < blockSuccessorCount(); i++) { - if (i != remainingSuxIndex) { - tool.deleteBranch(blockSuccessor(i)); - } - } - - tool.addToWorkList(blockSuccessor(remainingSuxIndex)); - ((StructuredGraph) graph()).removeSplit(this, remainingSuxIndex); - } - } -}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/SwitchNode.java Wed Jun 27 11:51:18 2012 +0200 @@ -22,6 +22,8 @@ */ package com.oracle.graal.nodes.extended; +import com.oracle.graal.api.meta.*; +import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.type.*; @@ -31,6 +33,8 @@ public abstract class SwitchNode extends ControlSplitNode { @Input private ValueNode value; + private final double[] keyProbabilities; + private final int[] keySuccessors; public ValueNode value() { return value; @@ -42,16 +46,72 @@ * @param successors the list of successors of this switch * @param stateAfter the state after the switch */ - public SwitchNode(ValueNode value, BeginNode[] successors, double[] probability) { - super(StampFactory.forVoid(), successors, probability); + public SwitchNode(ValueNode value, BeginNode[] successors, double[] successorProbabilities, int[] keySuccessors, double[] keyProbabilities) { + super(StampFactory.forVoid(), successors, successorProbabilities); + assert keySuccessors.length == keyProbabilities.length; this.value = value; + this.keySuccessors = keySuccessors; + this.keyProbabilities = keyProbabilities; + } + + /** + * The number of distinct keys in this switch. + */ + public abstract int keyCount(); + + /** + * The key at the specified position, encoded in a Constant. + */ + public abstract Constant keyAt(int i); + + /** + * Returns the index of the successor belonging to the key at the specified index. + */ + public int keySuccessorIndex(int i) { + return keySuccessors[i]; + } + + /** + * Returns the successor for the key at the given index. + */ + public BeginNode keySuccessor(int i) { + return blockSuccessor(keySuccessors[i]); } /** - * Gets the number of cases that this switch covers (excluding the default case). - * @return the number of cases + * Returns the probability of the key at the given index. + */ + public double keyProbability(int i) { + return keyProbabilities[i]; + } + + /** + * Returns the index of the default (fall through) successor of this switch. + */ + public int defaultSuccessorIndex() { + return keySuccessors[keySuccessors.length - 1]; + } + + /** + * Gets the successor corresponding to the default (fall through) case. + * @return the default successor */ - public int numberOfCases() { - return blockSuccessorCount() - 1; + public BeginNode defaultSuccessor() { + if (defaultSuccessorIndex() == -1) { + throw new GraalInternalError("unexpected"); + } + return defaultSuccessorIndex() == -1 ? null : blockSuccessor(defaultSuccessorIndex()); + } + + /** + * Helper function that sums up the probabilities of all keys that lead to a specific successor. + * @return an array of size successorCount with the accumulated probability for each successor. + */ + public static double[] successorProbabilites(int successorCount, int[] keySuccessors, double[] keyProbabilities) { + double[] probability = new double[successorCount]; + for (int i = 0; i < keySuccessors.length; i++) { + probability[keySuccessors[i]] += keyProbabilities[i]; + } + return probability; } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/TableSwitchNode.java Tue Jun 26 16:54:58 2012 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,94 +0,0 @@ -/* - * Copyright (c) 2009, 2011, 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.nodes.extended; - -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.spi.*; - -/** - * The {@code TableSwitchNode} represents a table switch. - */ -public final class TableSwitchNode extends SwitchNode implements LIRLowerable, Simplifiable { - - private final int lowKey; - - /** - * Constructs a new TableSwitch instruction. - * @param value the instruction producing the value being switched on - * @param successors the list of successors - * @param lowKey the lowest integer key in the table - */ - public TableSwitchNode(ValueNode value, BeginNode[] successors, int lowKey, double[] probability) { - super(value, successors, probability); - this.lowKey = lowKey; - } - - public TableSwitchNode(ValueNode value, int lowKey, double[] switchProbability) { - this(value, new BeginNode[switchProbability.length], lowKey, switchProbability); - } - - /** - * Gets the lowest key in the table switch (inclusive). - * @return the low key - */ - public int lowKey() { - return lowKey; - } - - /** - * Gets the highest key in the table switch (exclusive). - * @return the high key - */ - public int highKey() { - return lowKey + numberOfCases(); - } - - @Override - public void generate(LIRGeneratorTool gen) { - gen.emitTableSwitch(this); - } - - @Override - public void simplify(SimplifierTool tool) { - if (value() instanceof ConstantNode) { - ConstantNode constant = (ConstantNode) value(); - int value = constant.value.asInt(); - - int remainingSuxIndex; - if (value >= lowKey() && value <= highKey()) { - remainingSuxIndex = value - lowKey(); - } else { - remainingSuxIndex = blockSuccessorCount() - 1; - } - - for (int i = 0; i < blockSuccessorCount(); i++) { - if (i != remainingSuxIndex) { - tool.deleteBranch(blockSuccessor(i)); - } - } - - tool.addToWorkList(blockSuccessor(remainingSuxIndex)); - ((StructuredGraph) graph()).removeSplit(this, remainingSuxIndex); - } - } -}
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/TypeSwitchNode.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/TypeSwitchNode.java Wed Jun 27 11:51:18 2012 +0200 @@ -22,10 +22,15 @@ */ package com.oracle.graal.nodes.java; +import java.util.*; + import com.oracle.graal.api.meta.*; +import com.oracle.graal.api.meta.JavaType.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; +import com.oracle.graal.nodes.util.*; /** * The {@code TypeSwitchNode} performs a lookup based on the type of the input value. @@ -35,32 +40,116 @@ private final ResolvedJavaType[] keys; - public TypeSwitchNode(ValueNode value, BeginNode[] successors, ResolvedJavaType[] keys, double[] probability) { - super(value, successors, probability); + /** + * Constructs a type switch instruction. The keyProbabilities and keySuccessors array contain key.length + 1 + * entries, the last entry describes the default (fall through) case. + * + * @param value the instruction producing the value being switched on + * @param successors the list of successors + * @param keys the list of types + * @param keyProbabilities the probabilities of the keys + * @param keySuccessor the successor index for each key + */ + public TypeSwitchNode(ValueNode value, BeginNode[] successors, double[] successorProbabilities, ResolvedJavaType[] keys, double[] keyProbabilities, int[] keySuccessors) { + super(value, successors, successorProbabilities, keySuccessors, keyProbabilities); assert successors.length == keys.length + 1; - assert successors.length == probability.length; + assert successors.length == keyProbabilities.length; this.keys = keys; } - public TypeSwitchNode(ValueNode value, ResolvedJavaType[] keys, double[] switchProbability) { - this(value, new BeginNode[switchProbability.length], keys, switchProbability); - } - - public ResolvedJavaType keyAt(int i) { - return keys[i]; - } - - public int keysLength() { + @Override + public int keyCount() { return keys.length; } @Override + public Constant keyAt(int i) { + return keys[i].getEncoding(Representation.ObjectHub); + } + + @Override public void generate(LIRGeneratorTool gen) { - gen.emitTypeSwitch(this); + gen.emitSwitch(this); } @Override public void simplify(SimplifierTool tool) { - // TODO(ls) perform simplifications based on the type of value + if (value() instanceof ConstantNode) { + Constant constant = value().asConstant(); + + int survivingEdge = keySuccessorIndex(keyCount()); + for (int i = 0; i < keyCount(); i++) { + Constant typeHub = keyAt(i); + assert constant.kind == typeHub.kind; + if (tool.runtime().areConstantObjectsEqual(value().asConstant(), typeHub)) { + survivingEdge = keySuccessorIndex(i); + } + } + for (int i = 0; i < blockSuccessorCount(); i++) { + if (i != survivingEdge) { + tool.deleteBranch(blockSuccessor(i)); + } + } + tool.addToWorkList(blockSuccessor(survivingEdge)); + ((StructuredGraph) graph()).removeSplitPropagate(this, survivingEdge); + } + if (value() instanceof ReadHubNode) { + ObjectStamp stamp = ((ReadHubNode) value()).object().objectStamp(); + if (stamp.type() != null) { + int validKeys = 0; + for (int i = 0; i < keyCount(); i++) { + if (keys[i].isSubtypeOf(stamp.type())) { + validKeys++; + } + } + if (validKeys == 0) { + tool.addToWorkList(defaultSuccessor()); + ((StructuredGraph) graph()).removeSplitPropagate(this, defaultSuccessorIndex()); + } else if (validKeys != keys.length) { + ArrayList<BeginNode> newSuccessors = new ArrayList<>(blockSuccessorCount()); + ResolvedJavaType[] newKeys = new ResolvedJavaType[validKeys]; + int[] newKeySuccessors = new int [validKeys + 1]; + double[] newKeyProbabilities = new double[validKeys + 1]; + double totalProbability = 0; + int current = 0; + for (int i = 0; i < keyCount() + 1; i++) { + if (i == keyCount() || keys[i].isSubtypeOf(stamp.type())) { + int index = newSuccessors.indexOf(keySuccessor(i)); + if (index == -1) { + index = newSuccessors.size(); + newSuccessors.add(keySuccessor(i)); + } + newKeySuccessors[current] = index; + if (i < keyCount()) { + newKeys[current] = keys[i]; + } + newKeyProbabilities[current] = keyProbability(i); + totalProbability += keyProbability(i); + current++; + } + } + if (totalProbability > 0) { + for (int i = 0; i < current; i++) { + newKeyProbabilities[i] /= totalProbability; + } + } + + double[] newSuccessorProbabilities = successorProbabilites(newSuccessors.size(), newKeySuccessors, newKeyProbabilities); + + for (int i = 0; i < blockSuccessorCount(); i++) { + BeginNode successor = blockSuccessor(i); + if (!newSuccessors.contains(successor)) { + tool.deleteBranch(successor); + } + setBlockSuccessor(i, null); + } + + BeginNode[] successorsArray = newSuccessors.toArray(new BeginNode[newSuccessors.size()]); + TypeSwitchNode newSwitch = graph().add(new TypeSwitchNode(value(), successorsArray, newSuccessorProbabilities, newKeys, newKeyProbabilities, newKeySuccessors)); + ((FixedWithNextNode) predecessor()).setNext(newSwitch); + GraphUtil.killWithUnusedFloatingInputs(this); + } + } + } } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/LIRGeneratorTool.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/spi/LIRGeneratorTool.java Wed Jun 27 11:51:18 2012 +0200 @@ -92,9 +92,7 @@ public abstract void emitConditional(ConditionalNode i); public abstract void emitGuardCheck(BooleanNode comp, DeoptimizationReason deoptReason, DeoptimizationAction deoptAction, boolean negated, long leafGraphId); - public abstract void emitLookupSwitch(LookupSwitchNode i); - public abstract void emitTableSwitch(TableSwitchNode i); - public abstract void emitTypeSwitch(TypeSwitchNode i); + public abstract void emitSwitch(SwitchNode i); public abstract void emitInvoke(Invoke i); public abstract void emitRuntimeCall(RuntimeCallNode i);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/IntegerStamp.java Tue Jun 26 16:54:58 2012 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/IntegerStamp.java Wed Jun 27 11:51:18 2012 +0200 @@ -73,6 +73,14 @@ return mask; } + public boolean isUnrestricted() { + return lowerBound == kind().minValue() && upperBound == kind().maxValue() && mask == defaultMask(kind()); + } + + public boolean contains(long value) { + return value >= lowerBound && value <= upperBound && (value & mask) == (value & defaultMask(kind())); + } + @Override public String toString() { StringBuilder str = new StringBuilder();