Mercurial > hg > truffle
changeset 3211:76507b87dd25
global absolute probability analysis:
* added switch probability, changed branch probability from int to double
* absolute probability on each FixedNode computed by new ComputeProbabilityPhase
* loopFrequency estimation on LoopBegin nodes
* added GraalOptions.ProbabilityAnalysis flag: builds probability information and let inlining and escape analysis use it
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java Tue Jul 12 17:00:25 2011 +0200 @@ -57,10 +57,13 @@ // escape analysis settings public static boolean EscapeAnalysis = ____; - public static int ForcedInlineEscapeWeight = 0; + public static int ForcedInlineEscapeWeight = 100; public static int MaximumEscapeAnalysisArrayLength = 32; public static boolean PrintEscapeAnalysis = ____; + // absolute probability analysis + public static boolean ProbabilityAnalysis = true; + // debugging settings public static boolean VerifyPointerMaps = ____; public static int MethodEndBreakpointGuards = 0; @@ -114,6 +117,7 @@ public static boolean TraceEscapeAnalysis = ____; public static boolean TraceCanonicalizer = ____; public static boolean TraceMemoryMaps = ____; + public static boolean TraceProbability = ____; public static boolean TraceReadElimination = ____; public static boolean TraceGVN = ____; public static int TraceBytecodeParserLevel = 0;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/BlockMap.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/BlockMap.java Tue Jul 12 17:00:25 2011 +0200 @@ -279,10 +279,10 @@ case IFNONNULL: { current = null; - int probability = GraalOptions.UseBranchPrediction ? method.branchProbability(bci) : -1; + double probability = GraalOptions.UseBranchPrediction ? method.branchProbability(bci) : -1; - Block b1 = probability == 100 ? makeBranchOverrideBlock(bci, bci + 3, false) : makeBlock(bci + 3); - Block b2 = probability == 0 ? makeBranchOverrideBlock(bci, bci + Bytes.beS2(code, bci + 1), true) : makeBlock(bci + Bytes.beS2(code, bci + 1)); + Block b1 = probability == 1.0 ? makeBranchOverrideBlock(bci, bci + 3, false) : makeBlock(bci + 3); + Block b2 = probability == 0.0 ? makeBranchOverrideBlock(bci, bci + Bytes.beS2(code, bci + 1), true) : makeBlock(bci + Bytes.beS2(code, bci + 1)); setSuccessors(bci, b1, b2); assert lengthOf(code, bci) == 3;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java Tue Jul 12 17:00:25 2011 +0200 @@ -85,13 +85,16 @@ new GraphBuilderPhase(compilation, compilation.method, false).apply(compilation.graph); // } - if (GraalOptions.TestGraphDuplication) { new DuplicationPhase().apply(compilation.graph); } new DeadCodeEliminationPhase().apply(compilation.graph); + if (GraalOptions.ProbabilityAnalysis) { + new ComputeProbabilityPhase().apply(compilation.graph); + } + if (GraalOptions.Inline) { new InliningPhase(compilation, this, null).apply(compilation.graph); }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Anchor.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Anchor.java Tue Jul 12 17:00:25 2011 +0200 @@ -96,6 +96,8 @@ @Override public Node copy(Graph into) { - return new Anchor(into); + Anchor x = new Anchor(into); + super.copyInto(x); + return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ControlSplit.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ControlSplit.java Tue Jul 12 17:00:25 2011 +0200 @@ -62,21 +62,33 @@ return blockSuccessorCount; } + protected final double[] branchProbability; + /** * Constructs a new block end with the specified value type. * @param kind the type of the value produced by this instruction * @param successors the list of successor blocks. If {@code null}, a new one will be created. */ - public ControlSplit(CiKind kind, List<? extends FixedNode> blockSuccessors, int inputCount, int successorCount, Graph graph) { - this(kind, blockSuccessors.size(), inputCount, successorCount, graph); + public ControlSplit(CiKind kind, List<? extends FixedNode> blockSuccessors, double[] branchProbability, int inputCount, int successorCount, Graph graph) { + this(kind, blockSuccessors.size(), branchProbability, inputCount, successorCount, graph); for (int i = 0; i < blockSuccessors.size(); i++) { setBlockSuccessor(i, blockSuccessors.get(i)); } } - public ControlSplit(CiKind kind, int blockSuccessorCount, int inputCount, int successorCount, Graph graph) { + public ControlSplit(CiKind kind, int blockSuccessorCount, double[] branchProbability, int inputCount, int successorCount, Graph graph) { super(kind, inputCount + INPUT_COUNT, successorCount + blockSuccessorCount + SUCCESSOR_COUNT, graph); this.blockSuccessorCount = blockSuccessorCount; + assert branchProbability.length == blockSuccessorCount; + this.branchProbability = branchProbability; + } + + public double probability(int successorIndex) { + return branchProbability[successorIndex]; + } + + public void setProbability(int successorIndex, double x) { + branchProbability[successorIndex] = x; } /** @@ -110,4 +122,15 @@ } }; } + + @Override + public Map<Object, Object> getDebugProperties() { + Map<Object, Object> properties = super.getDebugProperties(); + StringBuilder str = new StringBuilder(); + for (int i = 0; i < branchProbability.length; i++) { + str.append(i == 0 ? "" : ", ").append(String.format("%7.5f", branchProbability[i])); + } + properties.put("branchProbability", str.toString()); + return properties; + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/CreateVectorNode.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/CreateVectorNode.java Tue Jul 12 17:00:25 2011 +0200 @@ -87,7 +87,9 @@ @Override public Node copy(Graph into) { - return new CreateVectorNode(reversed, null, into); + CreateVectorNode x = new CreateVectorNode(reversed, null, into); + super.copyInto(x); + return x; } @Override @@ -120,7 +122,11 @@ } else { condition = new Compare(loopVariable, Condition.LT, length(), graph()); } - If ifNode = new If(condition, graph()); + int expectedLength = 100; // TODO: it may be possible to get a more accurate estimate...? + if (length().isConstant()) { + expectedLength = length().asConstant().asInt(); + } + If ifNode = new If(condition, 1.0 / expectedLength, graph()); loopBegin.setNext(ifNode); ifNode.setTrueSuccessor(loopEnd); this.replaceAtPredecessors(end);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Deoptimize.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Deoptimize.java Tue Jul 12 17:00:25 2011 +0200 @@ -88,6 +88,7 @@ public Node copy(Graph into) { Deoptimize x = new Deoptimize(action, into); x.setMessage(message); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/EndNode.java Tue Jul 12 17:00:25 2011 +0200 @@ -49,7 +49,9 @@ @Override public Node copy(Graph into) { - return new EndNode(into); + EndNode x = new EndNode(into); + super.copyInto(x); + return x; } public Merge merge() {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ExceptionObject.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ExceptionObject.java Tue Jul 12 17:00:25 2011 +0200 @@ -56,6 +56,7 @@ @Override public Node copy(Graph into) { ExceptionObject x = new ExceptionObject(into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FixedGuard.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FixedGuard.java Tue Jul 12 17:00:25 2011 +0200 @@ -61,7 +61,9 @@ @Override public Node copy(Graph into) { - return new FixedGuard(into); + FixedGuard x = new FixedGuard(into); + super.copyInto(x); + return x; } @SuppressWarnings("unchecked")
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FixedNode.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/FixedNode.java Tue Jul 12 17:00:25 2011 +0200 @@ -22,14 +22,36 @@ */ package com.oracle.max.graal.compiler.ir; +import java.util.*; + import com.oracle.max.graal.graph.*; import com.sun.cri.ci.*; +public abstract class FixedNode extends Value { -public abstract class FixedNode extends Value { + private double probability; public FixedNode(CiKind kind, int inputCount, int successorCount, Graph graph) { super(kind, inputCount, successorCount, graph); } + public double probability() { + return probability; + } + + public void setProbability(double probability) { + this.probability = probability; + } + + protected void copyInto(FixedNode newNode) { + newNode.setProbability(probability); + } + + @Override + public Map<Object, Object> getDebugProperties() { + Map<Object, Object> properties = super.getDebugProperties(); + properties.put("probability", String.format("%7.5f", probability)); + return properties; + } + }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/If.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/If.java Tue Jul 12 17:00:25 2011 +0200 @@ -60,8 +60,8 @@ inputs().set(super.inputCount() + INPUT_COMPARE, n); } - public If(BooleanNode condition, Graph graph) { - super(CiKind.Illegal, 2, INPUT_COUNT, SUCCESSOR_COUNT, graph); + public If(BooleanNode condition, double probability, Graph graph) { + super(CiKind.Illegal, 2, new double[] {probability, 1 - probability}, INPUT_COUNT, SUCCESSOR_COUNT, graph); setCompare(condition); } @@ -130,7 +130,9 @@ @Override public Node copy(Graph into) { - return new If(null, into); + If x = new If(null, probability(0), into); + super.copyInto(x); + return x; } @SuppressWarnings("unchecked")
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerAddVectorNode.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/IntegerAddVectorNode.java Tue Jul 12 17:00:25 2011 +0200 @@ -57,7 +57,9 @@ @Override public Node copy(Graph into) { - return new IntegerAddVectorNode(null, null, into); + IntegerAddVectorNode x = new IntegerAddVectorNode(null, null, into); + super.copyInto(x); + return x; } @Override
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Invoke.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Invoke.java Tue Jul 12 17:00:25 2011 +0200 @@ -215,6 +215,7 @@ public Node copy(Graph into) { Invoke x = new Invoke(bci, opcode, kind, new Value[argumentCount], target, returnType, into); x.setCanInline(canInline); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoadField.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoadField.java Tue Jul 12 17:00:25 2011 +0200 @@ -109,7 +109,9 @@ @Override public Node copy(Graph into) { - return new LoadField(null, field, into); + LoadField x = new LoadField(null, field, into); + super.copyInto(x); + return x; } @SuppressWarnings("unchecked")
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoadIndexed.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoadIndexed.java Tue Jul 12 17:00:25 2011 +0200 @@ -100,6 +100,7 @@ @Override public Node copy(Graph into) { LoadIndexed x = new LoadIndexed(null, null, null, elementKind(), into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LookupSwitch.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LookupSwitch.java Tue Jul 12 17:00:25 2011 +0200 @@ -48,8 +48,8 @@ * @param stateAfter the state after the switch * @param graph */ - public LookupSwitch(Value value, List<? extends FixedNode> successors, int[] keys, Graph graph) { - super(value, successors, INPUT_COUNT, SUCCESSOR_COUNT, graph); + public LookupSwitch(Value value, List<? extends FixedNode> successors, int[] keys, double[] probability, Graph graph) { + super(value, successors, probability, INPUT_COUNT, SUCCESSOR_COUNT, graph); this.keys = keys; } @@ -86,7 +86,8 @@ @Override public Node copy(Graph into) { - LookupSwitch x = new LookupSwitch(null, Arrays.asList(new FixedNodeWithNext[numberOfCases() + 1]), keys.clone(), into); + LookupSwitch x = new LookupSwitch(null, Arrays.asList(new FixedNodeWithNext[numberOfCases() + 1]), keys.clone(), branchProbability.clone(), into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopBegin.java Tue Jul 12 17:00:25 2011 +0200 @@ -29,8 +29,20 @@ import com.oracle.max.graal.graph.*; public class LoopBegin extends Merge { + + private double loopFrequency; + public LoopBegin(Graph graph) { super(graph); + loopFrequency = 1; + } + + public double loopFrequency() { + return loopFrequency; + } + + public void setLoopFrequency(double loopFrequency) { + this.loopFrequency = loopFrequency; } public LoopEnd loopEnd() { @@ -62,7 +74,10 @@ @Override public Node copy(Graph into) { - return new LoopBegin(into); + LoopBegin x = new LoopBegin(into); + x.setLoopFrequency(loopFrequency); + super.copyInto(x); + return x; } @Override @@ -131,4 +146,11 @@ } }; } + + @Override + public Map<Object, Object> getDebugProperties() { + Map<Object, Object> properties = super.getDebugProperties(); + properties.put("loopFrequency", String.format("%7.1f", loopFrequency)); + return properties; + } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopEnd.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/LoopEnd.java Tue Jul 12 17:00:25 2011 +0200 @@ -79,6 +79,7 @@ @Override public Node copy(Graph into) { LoopEnd x = new LoopEnd(into); + super.copyInto(x); return x; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Merge.java Tue Jul 12 17:00:25 2011 +0200 @@ -306,7 +306,9 @@ @Override public Node copy(Graph into) { assert getClass() == Merge.class : "copy of " + getClass(); - return new Merge(into); + Merge x = new Merge(into); + super.copyInto(x); + return x; } public void removeEnd(EndNode pred) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MonitorEnter.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MonitorEnter.java Tue Jul 12 17:00:25 2011 +0200 @@ -64,6 +64,7 @@ @Override public Node copy(Graph into) { MonitorEnter x = new MonitorEnter(null, null, lockNumber, into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MonitorExit.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MonitorExit.java Tue Jul 12 17:00:25 2011 +0200 @@ -58,6 +58,7 @@ @Override public Node copy(Graph into) { MonitorExit x = new MonitorExit(null, null, lockNumber, into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewInstance.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewInstance.java Tue Jul 12 17:00:25 2011 +0200 @@ -95,6 +95,7 @@ @Override public Node copy(Graph into) { NewInstance x = new NewInstance(instanceClass, cpi, constantPool, into); + super.copyInto(x); return x; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewMultiArray.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewMultiArray.java Tue Jul 12 17:00:25 2011 +0200 @@ -136,6 +136,7 @@ @Override public Node copy(Graph into) { NewMultiArray x = new NewMultiArray(elementType, new Value[dimensionCount], cpi, constantPool, into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewObjectArray.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewObjectArray.java Tue Jul 12 17:00:25 2011 +0200 @@ -84,6 +84,7 @@ @Override public Node copy(Graph into) { NewObjectArray x = new NewObjectArray(elementClass, null, into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewTypeArray.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewTypeArray.java Tue Jul 12 17:00:25 2011 +0200 @@ -70,6 +70,7 @@ @Override public Node copy(Graph into) { NewTypeArray x = new NewTypeArray(null, elementType, into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Placeholder.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Placeholder.java Tue Jul 12 17:00:25 2011 +0200 @@ -65,6 +65,7 @@ @Override public Node copy(Graph into) { Placeholder x = new Placeholder(into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ReadNode.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ReadNode.java Tue Jul 12 17:00:25 2011 +0200 @@ -53,6 +53,8 @@ @Override public Node copy(Graph into) { - return new ReadNode(super.kind, null, null, into); + ReadNode x = new ReadNode(super.kind, null, null, into); + super.copyInto(x); + return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ReadVectorNode.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ReadVectorNode.java Tue Jul 12 17:00:25 2011 +0200 @@ -47,7 +47,9 @@ @Override public Node copy(Graph into) { - return new ReadVectorNode(null, null, null, into); + ReadVectorNode x = new ReadVectorNode(null, null, null, into); + super.copyInto(x); + return x; }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/RegisterFinalizer.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/RegisterFinalizer.java Tue Jul 12 17:00:25 2011 +0200 @@ -128,6 +128,8 @@ @Override public Node copy(Graph into) { - return new RegisterFinalizer(null, into); + RegisterFinalizer x = new RegisterFinalizer(null, into); + super.copyInto(x); + return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Return.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Return.java Tue Jul 12 17:00:25 2011 +0200 @@ -91,6 +91,7 @@ @Override public Node copy(Graph into) { Return x = new Return(kind, into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/StoreField.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/StoreField.java Tue Jul 12 17:00:25 2011 +0200 @@ -100,6 +100,8 @@ @Override public Node copy(Graph into) { - return new StoreField(null, field, null, into); + StoreField x = new StoreField(null, field, null, into); + super.copyInto(x); + return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/StoreIndexed.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/StoreIndexed.java Tue Jul 12 17:00:25 2011 +0200 @@ -96,6 +96,7 @@ @Override public Node copy(Graph into) { StoreIndexed x = new StoreIndexed(null, null, null, elementKind(), null, into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Switch.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Switch.java Tue Jul 12 17:00:25 2011 +0200 @@ -65,8 +65,8 @@ * @param stateAfter the state after the switch * @param graph */ - public Switch(Value value, List<? extends FixedNode> successors, int inputCount, int successorCount, Graph graph) { - super(CiKind.Illegal, successors, inputCount + INPUT_COUNT, successorCount + SUCCESSOR_COUNT, graph); + public Switch(Value value, List<? extends FixedNode> successors, double[] probability, int inputCount, int successorCount, Graph graph) { + super(CiKind.Illegal, successors, probability, inputCount + INPUT_COUNT, successorCount + SUCCESSOR_COUNT, graph); setValue(value); }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/TableSwitch.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/TableSwitch.java Tue Jul 12 17:00:25 2011 +0200 @@ -47,8 +47,8 @@ * @param stateAfter the state after the switch * @param graph */ - public TableSwitch(Value value, List<? extends FixedNode> successors, int lowKey, Graph graph) { - super(value, successors, INPUT_COUNT, SUCCESSOR_COUNT, graph); + public TableSwitch(Value value, List<? extends FixedNode> successors, int lowKey, double[] probability, Graph graph) { + super(value, successors, probability, INPUT_COUNT, SUCCESSOR_COUNT, graph); this.lowKey = lowKey; } @@ -88,7 +88,8 @@ @Override public Node copy(Graph into) { - TableSwitch x = new TableSwitch(null, Arrays.asList(new FixedNodeWithNext[numberOfCases() + 1]), lowKey, into); + TableSwitch x = new TableSwitch(null, Arrays.asList(new FixedNodeWithNext[numberOfCases() + 1]), lowKey, branchProbability, into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Unwind.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Unwind.java Tue Jul 12 17:00:25 2011 +0200 @@ -76,6 +76,7 @@ @Override public Node copy(Graph into) { Unwind x = new Unwind(null, into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ValueAnchor.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/ValueAnchor.java Tue Jul 12 17:00:25 2011 +0200 @@ -80,6 +80,7 @@ @Override public Node copy(Graph into) { ValueAnchor x = new ValueAnchor(null, into); + super.copyInto(x); return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/WriteMemoryCheckpointNode.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/WriteMemoryCheckpointNode.java Tue Jul 12 17:00:25 2011 +0200 @@ -50,6 +50,8 @@ @Override public Node copy(Graph into) { - return new WriteMemoryCheckpointNode(into); + WriteMemoryCheckpointNode x = new WriteMemoryCheckpointNode(into); + super.copyInto(x); + return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/WriteNode.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/WriteNode.java Tue Jul 12 17:00:25 2011 +0200 @@ -62,6 +62,8 @@ @Override public Node copy(Graph into) { - return new WriteNode(super.kind, null, null, null, into); + WriteNode x = new WriteNode(super.kind, null, null, null, into); + super.copyInto(x); + return x; } }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/WriteVectorNode.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/WriteVectorNode.java Tue Jul 12 17:00:25 2011 +0200 @@ -63,7 +63,9 @@ @Override public Node copy(Graph into) { - return new WriteVectorNode(null, null, null, null, into); + WriteVectorNode x = new WriteVectorNode(null, null, null, null, into); + super.copyInto(x); + return x; }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/ComputeProbabilityPhase.java Tue Jul 12 17:00:25 2011 +0200 @@ -0,0 +1,295 @@ +/* + * Copyright (c) 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.max.graal.compiler.phases; + +import java.util.*; + +import com.oracle.max.graal.compiler.*; +import com.oracle.max.graal.compiler.debug.*; +import com.oracle.max.graal.compiler.ir.*; +import com.oracle.max.graal.compiler.observer.*; +import com.oracle.max.graal.compiler.phases.EscapeAnalysisPhase.MergeableState; +import com.oracle.max.graal.compiler.phases.EscapeAnalysisPhase.PostOrderNodeIterator; +import com.oracle.max.graal.graph.*; + +public class ComputeProbabilityPhase extends Phase { + private static final double EPSILON = 1d / Integer.MAX_VALUE; + + /* + * The computation of absolute probabilities works in three steps: + * + * - The first step, "PropagateProbability", traverses the graph in post order (merges after their ends, ...) and keeps track of the "probability state". + * Whenever it encounters a ControlSplit it uses the splits probability information to divide the probability upon the successors. + * Whenever it encounters an Invoke it assumes that the exception edge is unlikely and propagates the whole probability to the normal successor. + * Whenever it encounters a Merge it sums up the probability of all predecessors. + * It also maintains a set of active loops (whose LoopBegin has been visited) and builds def/use information for the second step. + * + * - The third step propagates the loop frequencies and multiplies each FixedNode's probability with its loop frequency. + * + * TODO: add exception probability information to Invokes + */ + + @Override + protected void run(Graph graph) { + new PropagateProbability((FixedNode) graph.start().next()).apply(); + GraalCompilation compilation = GraalCompilation.compilation(); + if (compilation.compiler.isObserved() && GraalOptions.TraceProbability) { + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After PropagateProbability", graph, true, false)); + } + computeLoopFactors(); + if (compilation.compiler.isObserved() && GraalOptions.TraceProbability) { + compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After computeLoopFactors", graph, true, false)); + } + new PropagateLoopFrequency((FixedNode) graph.start().next()).apply(); + } + + private void computeLoopFactors() { + if (GraalOptions.TraceProbability) { + for (LoopInfo info : loopInfos) { + TTY.println("\nLoop " + info.loopBegin); + TTY.print(" requires: "); + for (LoopInfo r : info.requires) { + TTY.print(r.loopBegin + " "); + } + TTY.println(); + } + } + for (LoopInfo info : loopInfos) { + double frequency = info.loopFrequency(); + assert frequency != -1; + } + } + + private static boolean isRelativeProbability(double prob) { + // 1.01 to allow for some rounding errors + return prob >= 0 && prob <= 1.01; + } + + public static class LoopInfo { + public final LoopBegin loopBegin; + + public final Set<LoopInfo> requires = new HashSet<LoopInfo>(4); + + private double loopFrequency = -1; + public boolean ended = false; + + public LoopInfo(LoopBegin loopBegin) { + this.loopBegin = loopBegin; + } + + public double loopFrequency() { + if (loopFrequency == -1 && ended) { + double factor = 1; + for (LoopInfo required : requires) { + double t = required.loopFrequency(); + if (t == -1) { + return -1; + } + factor *= t; + } + double d = loopBegin.loopEnd().probability() * factor; + if (d < EPSILON) { + d = EPSILON; + } else if (d > loopBegin.probability() - EPSILON) { + d = loopBegin.probability() - EPSILON; + } + loopFrequency = loopBegin.probability() / (loopBegin.probability() - d); + loopBegin.setLoopFrequency(loopFrequency); +// TTY.println("computed loop Frequency %f for %s", loopFrequency, loopBegin); + } + return loopFrequency; + } + } + + public Set<LoopInfo> loopInfos = new HashSet<LoopInfo>(); + public Map<Merge, Set<LoopInfo>> mergeLoops = new HashMap<Merge, Set<LoopInfo>>(); + + private class Probability implements MergeableState<Probability> { + public double probability; + public HashSet<LoopInfo> loops; + public LoopInfo loopInfo; + + public Probability(double probability, HashSet<LoopInfo> loops) { + this.probability = probability; + this.loops = new HashSet<LoopInfo>(4); + if (loops != null) { + this.loops.addAll(loops); + } + } + + @Override + public Probability clone() { + return new Probability(probability, loops); + } + + @Override + public boolean merge(Merge merge, Collection<Probability> withStates) { + if (merge.endCount() > 1) { + HashSet<LoopInfo> intersection = new HashSet<LoopInfo>(loops); + for (Probability other : withStates) { + intersection.retainAll(other.loops); + } + for (LoopInfo info : loops) { + if (!intersection.contains(info)) { + // TTY.println("probability for %s at %s", info.loopBegin, merge); + double loopFrequency = info.loopFrequency(); + if (loopFrequency == -1) { + // TTY.println("re-queued " + merge); + return false; + } + probability *= loopFrequency; + } + } + for (Probability other : withStates) { + double prob = other.probability; + for (LoopInfo info : other.loops) { + if (!intersection.contains(info)) { + // TTY.println("probability for %s at %s", info.loopBegin, merge); + double loopFrequency = info.loopFrequency(); + if (loopFrequency == -1) { + // TTY.println("re-queued " + merge); + return false; + } + prob *= loopFrequency; + } + } + probability += prob; + } + loops = intersection; + // TTY.println("merged " + merge); + mergeLoops.put(merge, new HashSet<LoopInfo>(intersection)); + assert isRelativeProbability(probability) : probability; + } + return true; + } + + @Override + public void loopBegin(LoopBegin loopBegin) { + loopInfo = new LoopInfo(loopBegin); + loopInfos.add(loopInfo); + loops.add(loopInfo); + } + + @Override + public void loopEnd(LoopEnd loopEnd, Probability loopEndState) { + assert loopInfo != null; + for (LoopInfo innerLoop : loopEndState.loops) { + if (innerLoop != loopInfo && !loops.contains(innerLoop)) { + loopInfo.requires.add(innerLoop); + } + } + loopInfo.ended = true; + } + + @Override + public void afterSplit(FixedNode node) { + assert node.predecessors().size() == 1; + Node pred = node.predecessors().get(0); + if (pred instanceof Invoke) { + Invoke x = (Invoke) pred; + if (x.next() != node) { + probability = 0; + } + } else { + assert pred instanceof ControlSplit; + ControlSplit x = (ControlSplit) pred; + double sum = 0; + for (int i = 0; i < x.blockSuccessorCount(); i++) { + if (x.blockSuccessor(i) == node) { + sum += x.probability(i); + } + } + probability *= sum; + } + } + } + + private class PropagateProbability extends PostOrderNodeIterator<Probability> { + + public PropagateProbability(FixedNode start) { + super(start, new Probability(1d, null)); + } + + @Override + protected void node(FixedNode node) { +// TTY.println(" -- %7.5f %s", state.probability, node); + node.setProbability(state.probability); + } + } + + private class LoopCount implements MergeableState<LoopCount> { + public double count; + + public LoopCount(double count) { + this.count = count; + } + + @Override + public LoopCount clone() { + return new LoopCount(count); + } + + @Override + public boolean merge(Merge merge, Collection<LoopCount> withStates) { + assert merge.endCount() == withStates.size() + 1; + if (merge.endCount() > 1) { + Set<LoopInfo> loops = mergeLoops.get(merge); +// TTY.println("merging count for %s: %d ends, %d loops", merge, merge.endCount(), loops.size()); + assert loops != null; + double countProd = 1; + for (LoopInfo loop : loops) { + countProd *= loop.loopFrequency(); + } + count = countProd; + } + return true; + } + + @Override + public void loopBegin(LoopBegin loopBegin) { + count *= loopBegin.loopFrequency(); + } + + @Override + public void loopEnd(LoopEnd loopEnd, LoopCount loopEndState) { + // nothing to do... + } + + @Override + public void afterSplit(FixedNode node) { + // nothing to do... + } + } + + private class PropagateLoopFrequency extends PostOrderNodeIterator<LoopCount> { + + public PropagateLoopFrequency(FixedNode start) { + super(start, new LoopCount(1d)); + } + + @Override + protected void node(FixedNode node) { + node.setProbability(node.probability() * state.count); + } + } +}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java Tue Jul 12 17:00:25 2011 +0200 @@ -41,9 +41,10 @@ public interface MergeableState <T> { T clone(); - void merge(Merge merge, Collection<T> withStates); + boolean merge(Merge merge, Collection<T> withStates); void loopBegin(LoopBegin loopBegin); void loopEnd(LoopEnd loopEnd, T loopEndState); + void afterSplit(FixedNode node); } public abstract static class PostOrderNodeIterator<T extends MergeableState<T>> { @@ -73,7 +74,8 @@ current = nextQueuedNode(); } else if (current instanceof LoopBegin) { state.loopBegin((LoopBegin) current); - nodeStates.put(current, state.clone()); + nodeStates.put(current, state); + state = state.clone(); loopBegin((LoopBegin) current); current = ((LoopBegin) current).next(); assert current != null; @@ -138,11 +140,16 @@ assert other != null; states.add(other); } - state.merge(merge, states); - return merge; + boolean ready = state.merge(merge, states); + if (ready) { + return merge; + } else { + nodeQueue.addLast(merge); + } } else { assert node.predecessors().size() == 1; state = nodeStates.get(node.predecessors().get(0)).clone(); + state.afterSplit(node); return node; } } @@ -237,7 +244,7 @@ } @Override - public void merge(Merge merge, Collection<BlockExitState> withStates) { + public boolean merge(Merge merge, Collection<BlockExitState> withStates) { Phi vobjPhi = null; Phi[] valuePhis = new Phi[fieldState.length]; for (BlockExitState other : withStates) { @@ -271,6 +278,7 @@ assert valuePhis[i2].valueCount() == withStates.size() + 1; } } + return true; } @Override @@ -299,6 +307,11 @@ assert ((Phi) fieldState[i2]).valueCount() == 2; } } + + @Override + public void afterSplit(FixedNode node) { + // nothing to do... + } } @@ -382,10 +395,9 @@ Set<Invoke> invokes = new HashSet<Invoke>(); int iterations = 0; - int weight; int minimumWeight = GraalOptions.ForcedInlineEscapeWeight; do { - weight = analyze(op, node, exits, invokes); + double weight = analyze(op, node, exits, invokes); if (exits.size() != 0) { if (GraalOptions.TraceEscapeAnalysis || GraalOptions.PrintEscapeAnalysis) { TTY.println("%n####### escaping object: %d %s (%s) in %s", node.id(), node.shortName(), ((Value) node).exactType(), compilation.method); @@ -444,8 +456,8 @@ } } - private int analyze(EscapeOp op, Node node, Collection<Node> exits, Collection<Invoke> invokes) { - int weight = 0; + private double analyze(EscapeOp op, Node node, Collection<Node> exits, Collection<Invoke> invokes) { + double weight = 0; for (Node usage : node.usages()) { boolean escapes = op.escape(node, usage); if (escapes) { @@ -460,7 +472,11 @@ } } } else { - weight++; + if (GraalOptions.ProbabilityAnalysis && usage instanceof FixedNode) { + weight += ((FixedNode) usage).probability(); + } else { + weight++; + } } } return weight;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java Tue Jul 12 17:00:25 2011 +0200 @@ -676,7 +676,15 @@ private void ifNode(Value x, Condition cond, Value y) { assert !x.isDeleted() && !y.isDeleted(); - If ifNode = new If(new Compare(x, cond, y, graph), graph); + double probability = method.branchProbability(bci()); + if (probability < 0) { + if (GraalOptions.TraceProbability) { + TTY.println("missing probability in " + method + " at bci " + bci()); + } + probability = 0.5; + } + + If ifNode = new If(new Compare(x, cond, y, graph), probability, graph); append(ifNode); BlockMap.BranchOverride override = branchOverride.get(bci()); FixedNode tsucc; @@ -1053,13 +1061,29 @@ int offset = ts.defaultOffset(); list.add(null); offsetList.add(offset); - TableSwitch tableSwitch = new TableSwitch(value, list, ts.lowKey(), graph); + TableSwitch tableSwitch = new TableSwitch(value, list, ts.lowKey(), switchProbability(list.size(), bci), graph); for (int i = 0; i < offsetList.size(); ++i) { tableSwitch.setBlockSuccessor(i, createTargetAt(bci + offsetList.get(i), frameState)); } append(tableSwitch); } + private double[] switchProbability(int numberOfCases, int bci) { + double[] prob = method.switchProbability(bci); + if (prob != null) { + assert prob.length == numberOfCases; + } else { + if (GraalOptions.TraceProbability) { + TTY.println("Missing probability (switch) in " + method + " at bci " + bci); + } + prob = new double[numberOfCases]; + for (int i = 0; i < numberOfCases; i++) { + prob[i] = 1.0d / numberOfCases; + } + } + return prob; + } + private void genLookupswitch() { int bci = bci(); Value value = frameState.ipop(); @@ -1078,7 +1102,7 @@ int offset = ls.defaultOffset(); list.add(null); offsetList.add(offset); - LookupSwitch lookupSwitch = new LookupSwitch(value, list, keys, graph); + LookupSwitch lookupSwitch = new LookupSwitch(value, list, keys, switchProbability(list.size(), bci), graph); for (int i = 0; i < offsetList.size(); ++i) { lookupSwitch.setBlockSuccessor(i, createTargetAt(bci + offsetList.get(i), frameState)); } @@ -1337,7 +1361,7 @@ FixedNode catchSuccessor = createTarget(blockFromBci[block.handler.handlerBCI()], frameState); FixedNode nextDispatch = createTarget(nextBlock, frameState); Value exception = frameState.stackAt(0); - If ifNode = new If(new InstanceOf(typeInstruction, exception, false, graph), graph); + If ifNode = new If(new InstanceOf(typeInstruction, exception, false, graph), 0.5, graph); append(ifNode); ifNode.setTrueSuccessor(catchSuccessor); ifNode.setFalseSuccessor(nextDispatch);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java Tue Jul 12 17:00:25 2011 +0200 @@ -39,6 +39,10 @@ public class InliningPhase extends Phase { + /* + * - Detect method which only call another method with some parameters set to constants: void foo(a) -> void foo(a, b) -> void foo(a, b, c) ... + * These should not be taken into account when determining inlining depth. + */ public static final HashMap<RiMethod, Integer> methodCount = new HashMap<RiMethod, Integer>(); @@ -299,13 +303,17 @@ private boolean checkSizeConditions(RiMethod caller, int iterations, RiMethod method, Invoke invoke, RiTypeProfile profile, float adjustedRatio) { int maximumSize = GraalOptions.MaximumTrivialSize; - float ratio = 0; + double ratio = 0; if (profile != null && profile.count > 0) { RiMethod parent = invoke.stateAfter().method(); - ratio = profile.count / (float) parent.invocationCount(); + if (GraalOptions.ProbabilityAnalysis) { + ratio = invoke.probability(); + } else { + ratio = profile.count / (float) parent.invocationCount(); + } if (ratio >= GraalOptions.FreqInlineRatio) { maximumSize = GraalOptions.MaximumFreqInlineSize; - } else if (ratio >= (1 - adjustedRatio)) { + } else if (ratio >= 1 * (1 - adjustedRatio)) { maximumSize = GraalOptions.MaximumInlineSize; } } @@ -439,6 +447,10 @@ } graph = new CompilerGraph(null); new GraphBuilderPhase(compilation, method, true).apply(graph); + if (GraalOptions.ProbabilityAnalysis) { + new DeadCodeEliminationPhase().apply(graph); + new ComputeProbabilityPhase().apply(graph); + } } invoke.inputs().clearAll(); @@ -484,7 +496,14 @@ Map<Node, Node> duplicates = compilation.graph.addDuplicate(nodes, replacements); FrameState stateBefore = null; + double invokeProbability = invoke.probability(); for (Node node : duplicates.values()) { + if (GraalOptions.ProbabilityAnalysis) { + if (node instanceof FixedNode) { + FixedNode fixed = (FixedNode) node; + fixed.setProbability(fixed.probability() * invokeProbability); + } + } if (node instanceof Invoke && ((Invoke) node).canInline()) { newInvokes.add((Invoke) node); } else if (node instanceof FrameState) {
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotMethodResolved.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotMethodResolved.java Tue Jul 12 17:00:25 2011 +0200 @@ -28,4 +28,5 @@ public interface HotSpotMethodResolved extends RiMethod, Remote { RiMethod uniqueConcreteMethod(); + void dumpProfile(); }
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotMethodResolvedImpl.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotMethodResolvedImpl.java Tue Jul 12 17:00:25 2011 +0200 @@ -202,24 +202,28 @@ return compiler.getVMEntries().RiMethod_typeProfile(this, bci); } - public int branchProbability(int bci) { + public double branchProbability(int bci) { return compiler.getVMEntries().RiMethod_branchProbability(this, bci); } + public double[] switchProbability(int bci) { + return compiler.getVMEntries().RiMethod_switchProbability(this, bci); + } + public void dumpProfile() { TTY.println("profile info for %s", this); TTY.println("canBeStaticallyBound: " + canBeStaticallyBound()); TTY.println("invocationCount: " + invocationCount()); for (int i = 0; i < codeSize(); i++) { - if (exceptionProbability(i) != -1) { - TTY.println("exceptionProbability@%d: %d", i, exceptionProbability(i)); + if (exceptionProbability(i) > 0) { + TTY.println(" exceptionProbability@%d: %d", i, exceptionProbability(i)); } if (branchProbability(i) != -1) { - TTY.println("branchProbability@%d: %d", i, branchProbability(i)); + TTY.println(" branchProbability@%d: %f", i, branchProbability(i)); } RiTypeProfile profile = typeProfile(i); if (profile != null && profile.count > 0) { - TTY.println("profile@%d: count: %d, morphism: %d", i, profile.count, profile.morphism); + TTY.println(" profile@%d: count: %d, morphism: %d", i, profile.count, profile.morphism); } } }
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotMethodUnresolved.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotMethodUnresolved.java Tue Jul 12 17:00:25 2011 +0200 @@ -174,7 +174,11 @@ return null; } - public int branchProbability(int bci) { + public double branchProbability(int bci) { return -1; } + + public double[] switchProbability(int bci) { + return null; + } }
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotRuntime.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/HotSpotRuntime.java Tue Jul 12 17:00:25 2011 +0200 @@ -428,10 +428,10 @@ new WriteVectorNode(new IntegerAddVectorNode(reverseVector, destPos, graph), dest, location, reverseValues, graph); reverseVector.setStateAfter(stateAfter); - If ifNode = new If(new Compare(src, Condition.EQ, dest, graph), graph); + If ifNode = new If(new Compare(src, Condition.EQ, dest, graph), 0.5, graph); guard.setNext(ifNode); - If secondIf = new If(new Compare(srcPos, Condition.LT, destPos, graph), graph); + If secondIf = new If(new Compare(srcPos, Condition.LT, destPos, graph), 0.5, graph); ifNode.setTrueSuccessor(secondIf); secondIf.setTrueSuccessor(reverseVector); @@ -446,7 +446,7 @@ if (componentType == CiKind.Object) { Value srcClass = readHub(graph, src); Value destClass = readHub(graph, dest); - If elementClassIf = new If(new Compare(srcClass, Condition.EQ, destClass, graph), graph); + If elementClassIf = new If(new Compare(srcClass, Condition.EQ, destClass, graph), 0.5, graph); ifNode.setFalseSuccessor(elementClassIf); newInvoke = new Invoke(bci, Bytecodes.INVOKESTATIC, CiKind.Void, new Value[]{src, srcPos, dest, destPos, length}, method, method.signature().returnType(method.holder()), graph); newInvoke.setCanInline(false);
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/VMEntries.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/VMEntries.java Tue Jul 12 17:00:25 2011 +0200 @@ -49,7 +49,9 @@ RiTypeProfile RiMethod_typeProfile(HotSpotMethodResolved method, int bci); - int RiMethod_branchProbability(HotSpotMethodResolved method, int bci); + double RiMethod_branchProbability(HotSpotMethodResolved method, int bci); + + double[] RiMethod_switchProbability(HotSpotMethodResolved method, int bci); RiType RiSignature_lookupType(String returnType, HotSpotTypeResolved accessingClass);
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/VMEntriesNative.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/VMEntriesNative.java Tue Jul 12 17:00:25 2011 +0200 @@ -60,7 +60,10 @@ public native RiTypeProfile RiMethod_typeProfile(HotSpotMethodResolved method, int bci); @Override - public native int RiMethod_branchProbability(HotSpotMethodResolved method, int bci); + public native double RiMethod_branchProbability(HotSpotMethodResolved method, int bci); + + @Override + public native double[] RiMethod_switchProbability(HotSpotMethodResolved method, int bci); @Override public native RiType RiSignature_lookupType(String returnType, HotSpotTypeResolved accessingClass);
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/nodes/ArrayWriteBarrier.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/nodes/ArrayWriteBarrier.java Tue Jul 12 17:00:25 2011 +0200 @@ -94,6 +94,8 @@ @Override public Node copy(Graph into) { - return new ArrayWriteBarrier(null, null, into); + ArrayWriteBarrier x = new ArrayWriteBarrier(null, null, into); + super.copyInto(x); + return x; } }
--- a/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/nodes/FieldWriteBarrier.java Tue Jul 12 13:10:33 2011 +0200 +++ b/graal/com.oracle.max.graal.runtime/src/com/oracle/max/graal/runtime/nodes/FieldWriteBarrier.java Tue Jul 12 17:00:25 2011 +0200 @@ -81,6 +81,8 @@ @Override public Node copy(Graph into) { - return new FieldWriteBarrier(null, into); + FieldWriteBarrier x = new FieldWriteBarrier(null, into); + super.copyInto(x); + return x; } }
--- a/src/share/vm/graal/graalVMEntries.cpp Tue Jul 12 13:10:33 2011 +0200 +++ b/src/share/vm/graal/graalVMEntries.cpp Tue Jul 12 17:00:25 2011 +0200 @@ -251,8 +251,7 @@ return JNIHandles::make_local(obj()); } -// public native RiTypeProfile RiMethod_branchProfile(long vmId, int bci); -JNIEXPORT jint JNICALL Java_com_oracle_graal_runtime_VMEntries_RiMethod_2branchProbability(JNIEnv *, jobject, jobject hotspot_method, jint bci) { +JNIEXPORT jdouble JNICALL Java_com_oracle_graal_runtime_VMEntries_RiMethod_2branchProbability(JNIEnv *, jobject, jobject hotspot_method, jint bci) { TRACE_graal_3("VMEntries::RiMethod_typeProfile"); ciMethodData* method_data; ciMethod* cimethod; @@ -277,10 +276,6 @@ not_taken = data->as_BranchData()->not_taken(); } - // scale the counts to be commensurate with invocation counts: - taken = cimethod->scale_count(taken); - not_taken = cimethod->scale_count(not_taken); - // Give up if too few (or too many, in which case the sum will overflow) counts to be meaningful. // We also check that individual counters are positive first, otherwise the sum can become positive. if (taken < 0 || not_taken < 0 || taken + not_taken < 40) return -1; @@ -289,10 +284,56 @@ if (taken == 0) return 0; else if (not_taken == 0) - return 100; + return 1; else { // Compute probability of true path - int probability = (int)(taken * 100.0 / (taken + not_taken)); - return MIN2(99, MAX2(1, probability)); + return (jdouble)(taken) / (taken + not_taken); + } +} + +JNIEXPORT jobject JNICALL Java_com_oracle_graal_runtime_VMEntries_RiMethod_2switchProbability(JNIEnv *, jobject, jobject hotspot_method, jint bci) { + TRACE_graal_3("VMEntries::RiMethod_typeProfile"); + ciMethodData* method_data; + ciMethod* cimethod; + { + VM_ENTRY_MARK; + methodOop method = getMethodFromHotSpotMethod(hotspot_method); + cimethod = (ciMethod*)CURRENT_ENV->get_object(method); + } + method_data = cimethod->method_data(); + + jfloat probability = -1; + + if (method_data == NULL || !method_data->is_mature()) return NULL; + + ciProfileData* data = method_data->bci_to_data(bci); + if (data == NULL || !data->is_MultiBranchData()) return NULL; + + MultiBranchData* branch_data = data->as_MultiBranchData(); + + long sum = 0; + int cases = branch_data->number_of_cases(); + GrowableArray<uint>* counts = new GrowableArray<uint>(cases + 1); + + for (int i = 0; i < cases; i++) { + uint value = branch_data->count_at(i); + sum += value; + counts->append(value); + } + uint value = branch_data->default_count(); + sum += value; + counts->append(value); + + // Give up if too few (or too many, in which case the sum will overflow) counts to be meaningful. + // We also check that individual counters are positive first, otherwise the sum can become positive. + if (sum < 10 * (cases + 3)) return NULL; + + { + VM_ENTRY_MARK; + typeArrayOop probability = oopFactory::new_typeArray(T_DOUBLE, cases + 1, CHECK_NULL); + for (int i = 0; i < cases + 1; i++) { + probability->double_at_put(i, counts->at(i) / (double) sum); + } + return JNIHandles::make_local(probability); } } @@ -856,7 +897,8 @@ {CC"RiMethod_hasBalancedMonitors", CC"("RESOLVED_METHOD")Z", FN_PTR(Java_com_oracle_graal_runtime_VMEntries_RiMethod_1hasBalancedMonitors)}, {CC"RiMethod_uniqueConcreteMethod", CC"("RESOLVED_METHOD")"METHOD, FN_PTR(Java_com_oracle_graal_runtime_VMEntries_RiMethod_1uniqueConcreteMethod)}, {CC"RiMethod_typeProfile", CC"("RESOLVED_METHOD"I)"TYPE_PROFILE, FN_PTR(Java_com_oracle_graal_runtime_VMEntries_RiMethod_2typeProfile)}, - {CC"RiMethod_branchProbability", CC"("RESOLVED_METHOD"I)I", FN_PTR(Java_com_oracle_graal_runtime_VMEntries_RiMethod_2branchProbability)}, + {CC"RiMethod_branchProbability", CC"("RESOLVED_METHOD"I)D", FN_PTR(Java_com_oracle_graal_runtime_VMEntries_RiMethod_2branchProbability)}, + {CC"RiMethod_switchProbability", CC"("RESOLVED_METHOD"I)[D", FN_PTR(Java_com_oracle_graal_runtime_VMEntries_RiMethod_2switchProbability)}, {CC"RiMethod_invocationCount", CC"("RESOLVED_METHOD")I", FN_PTR(Java_com_oracle_graal_runtime_VMEntries_RiMethod_1invocationCount)}, {CC"RiMethod_exceptionProbability", CC"("RESOLVED_METHOD"I)I", FN_PTR(Java_com_oracle_graal_runtime_VMEntries_RiMethod_2exceptionProbability)}, {CC"RiSignature_lookupType", CC"("STRING RESOLVED_TYPE")"TYPE, FN_PTR(Java_com_oracle_graal_runtime_VMEntries_RiSignature_1lookupType)},