Mercurial > hg > truffle
changeset 9245:94df73308c7a
Merge.
| author | Thomas Wuerthinger <thomas.wuerthinger@oracle.com> |
|---|---|
| date | Tue, 23 Apr 2013 11:21:05 +0200 |
| parents | 8f540423a5be (current diff) 8e7dc0023b04 (diff) |
| children | ba3dfa9e36d8 |
| files | graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityPhase.java |
| diffstat | 57 files changed, 994 insertions(+), 732 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.alloc/src/com/oracle/graal/alloc/ComputeBlockOrder.java Tue Apr 23 11:21:05 2013 +0200 @@ -26,6 +26,7 @@ import java.util.*; import com.oracle.graal.nodes.cfg.*; +import com.oracle.graal.nodes.util.*; /** * Computes an ordering of the block that can be used by the linear scan register allocator and the @@ -66,11 +67,11 @@ * * @return sorted list of blocks */ - public static List<Block> computeLinearScanOrder(int blockCount, Block startBlock) { + public static List<Block> computeLinearScanOrder(int blockCount, Block startBlock, NodesToDoubles nodeProbabilities) { List<Block> order = new ArrayList<>(); BitSet visitedBlocks = new BitSet(blockCount); - PriorityQueue<Block> worklist = initializeWorklist(startBlock, visitedBlocks); - computeLinearScanOrder(order, worklist, visitedBlocks); + PriorityQueue<Block> worklist = initializeWorklist(startBlock, visitedBlocks, nodeProbabilities); + computeLinearScanOrder(order, worklist, visitedBlocks, nodeProbabilities); assert checkOrder(order, blockCount); return order; } @@ -80,11 +81,11 @@ * * @return sorted list of blocks */ - public static List<Block> computeCodeEmittingOrder(int blockCount, Block startBlock) { + public static List<Block> computeCodeEmittingOrder(int blockCount, Block startBlock, NodesToDoubles nodeProbabilities) { List<Block> order = new ArrayList<>(); BitSet visitedBlocks = new BitSet(blockCount); - PriorityQueue<Block> worklist = initializeWorklist(startBlock, visitedBlocks); - computeCodeEmittingOrder(order, worklist, visitedBlocks); + PriorityQueue<Block> worklist = initializeWorklist(startBlock, visitedBlocks, nodeProbabilities); + computeCodeEmittingOrder(order, worklist, visitedBlocks, nodeProbabilities); assert checkOrder(order, blockCount); return order; } @@ -92,28 +93,28 @@ /** * Iteratively adds paths to the code emission block order. */ - private static void computeCodeEmittingOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + private static void computeCodeEmittingOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { while (!worklist.isEmpty()) { Block nextImportantPath = worklist.poll(); - addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks); + addPathToCodeEmittingOrder(nextImportantPath, order, worklist, visitedBlocks, nodeProbabilities); } } /** * Iteratively adds paths to the linear scan block order. */ - private static void computeLinearScanOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + private static void computeLinearScanOrder(List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { while (!worklist.isEmpty()) { Block nextImportantPath = worklist.poll(); - addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks); + addPathToLinearScanOrder(nextImportantPath, order, worklist, visitedBlocks, nodeProbabilities); } } /** * Initializes the priority queue used for the work list of blocks and adds the start block. */ - private static PriorityQueue<Block> initializeWorklist(Block startBlock, BitSet visitedBlocks) { - PriorityQueue<Block> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, blockComparator); + private static PriorityQueue<Block> initializeWorklist(Block startBlock, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { + PriorityQueue<Block> result = new PriorityQueue<>(INITIAL_WORKLIST_CAPACITY, new BlockOrderComparator(nodeProbabilities)); result.add(startBlock); visitedBlocks.set(startBlock.getId()); return result; @@ -122,10 +123,10 @@ /** * Add a linear path to the linear scan order greedily following the most likely successor. */ - private static void addPathToLinearScanOrder(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + private static void addPathToLinearScanOrder(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { block.setLinearScanNumber(order.size()); order.add(block); - Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks); + Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, nodeProbabilities); enqueueSuccessors(block, worklist, visitedBlocks); if (mostLikelySuccessor != null) { if (!mostLikelySuccessor.isLoopHeader() && mostLikelySuccessor.getPredecessorCount() > 1) { @@ -134,24 +135,24 @@ double unscheduledSum = 0.0; for (Block pred : mostLikelySuccessor.getPredecessors()) { if (pred.getLinearScanNumber() == -1) { - unscheduledSum += pred.getBeginNode().probability(); + unscheduledSum += nodeProbabilities.get(pred.getBeginNode()); } } - if (unscheduledSum > block.getProbability() / PENALTY_VERSUS_UNSCHEDULED) { + if (unscheduledSum > nodeProbabilities.get(block.getBeginNode()) / PENALTY_VERSUS_UNSCHEDULED) { // Add this merge only after at least one additional predecessor gets scheduled. visitedBlocks.clear(mostLikelySuccessor.getId()); return; } } - addPathToLinearScanOrder(mostLikelySuccessor, order, worklist, visitedBlocks); + addPathToLinearScanOrder(mostLikelySuccessor, order, worklist, visitedBlocks, nodeProbabilities); } } /** * Add a linear path to the code emission order greedily following the most likely successor. */ - private static void addPathToCodeEmittingOrder(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks) { + private static void addPathToCodeEmittingOrder(Block block, List<Block> order, PriorityQueue<Block> worklist, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { // Skip loop headers if there is only a single loop end block to make the backward jump be a // conditional jump. @@ -180,10 +181,10 @@ } } - Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks); + Block mostLikelySuccessor = findAndMarkMostLikelySuccessor(block, visitedBlocks, nodeProbabilities); enqueueSuccessors(block, worklist, visitedBlocks); if (mostLikelySuccessor != null) { - addPathToCodeEmittingOrder(mostLikelySuccessor, order, worklist, visitedBlocks); + addPathToCodeEmittingOrder(mostLikelySuccessor, order, worklist, visitedBlocks, nodeProbabilities); } } @@ -198,11 +199,12 @@ /** * Find the highest likely unvisited successor block of a given block. */ - private static Block findAndMarkMostLikelySuccessor(Block block, BitSet visitedBlocks) { + private static Block findAndMarkMostLikelySuccessor(Block block, BitSet visitedBlocks, NodesToDoubles nodeProbabilities) { Block result = null; for (Block successor : block.getSuccessors()) { - assert successor.getProbability() >= 0.0 : "Probabilities must be positive"; - if (!visitedBlocks.get(successor.getId()) && successor.getLoopDepth() >= block.getLoopDepth() && (result == null || successor.getProbability() >= result.getProbability())) { + assert nodeProbabilities.get(successor.getBeginNode()) >= 0.0 : "Probabilities must be positive"; + if (!visitedBlocks.get(successor.getId()) && successor.getLoopDepth() >= block.getLoopDepth() && + (result == null || nodeProbabilities.get(successor.getBeginNode()) >= nodeProbabilities.get(result.getBeginNode()))) { result = successor; } } @@ -243,7 +245,13 @@ /** * Comparator for sorting blocks based on loop depth and probability. */ - private static Comparator<Block> blockComparator = new Comparator<Block>() { + private static class BlockOrderComparator implements Comparator<Block> { + + private final NodesToDoubles probabilities; + + public BlockOrderComparator(NodesToDoubles probabilities) { + this.probabilities = probabilities; + } @Override public int compare(Block a, Block b) { @@ -254,11 +262,11 @@ } // Blocks with high probability before blocks with low probability. - if (a.getProbability() > b.getProbability()) { + if (probabilities.get(a.getBeginNode()) > probabilities.get(b.getBeginNode())) { return -1; } else { return 1; } } - }; + } }
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/BoxingEliminationTest.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/BoxingEliminationTest.java Tue Apr 23 11:21:05 2013 +0200 @@ -306,7 +306,6 @@ private void processMethod(final String snippet) { graph = parse(snippet); - new ComputeProbabilityPhase().apply(graph); Assumptions assumptions = new Assumptions(false); HighTierContext context = new HighTierContext(runtime(), assumptions); new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph); @@ -325,7 +324,6 @@ public void run() { graph = parse(snippet); - new ComputeProbabilityPhase().apply(graph); Assumptions assumptions = new Assumptions(false); HighTierContext context = new HighTierContext(runtime(), assumptions); new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/WriteBarrierAdditionTest.java Tue Apr 23 11:21:05 2013 +0200 @@ -0,0 +1,117 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.compiler.test; + +import org.junit.*; + +import com.oracle.graal.api.code.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.hotspot.phases.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.extended.*; +import com.oracle.graal.nodes.extended.WriteNode.WriteBarrierType; +import com.oracle.graal.phases.common.*; + +public class WriteBarrierAdditionTest extends GraalCompilerTest { + + public static class Container { + + public Container a; + public Container b; + } + + public static void test1Snippet() { + Container main = new Container(); + Container temp1 = new Container(); + Container temp2 = new Container(); + main.a = temp1; + main.b = temp2; + } + + public static void test2Snippet() { + boolean test = true; + Container main = new Container(); + Container temp1 = new Container(); + Container temp2 = new Container(); + for (int i = 0; i < 10; i++) { + if (test) { + main.a = temp1; + main.b = temp2; + test = false; + } else { + main.a = temp2; + main.b = temp1; + test = true; + } + } + } + + public static void test3Snippet() { + Container[] main = new Container[10]; + Container temp1 = new Container(); + Container temp2 = new Container(); + for (int i = 0; i < 10; i++) { + main[i].a = main[i].b = temp1; + } + + for (int i = 0; i < 10; i++) { + main[i].a = main[i].b = temp2; + } + + } + + @Test + public void test1() { + test("test1Snippet", 2); + } + + @Test + public void test2() { + test("test2Snippet", 4); + } + + @Test + public void test3() { + test("test3Snippet", 4); + } + + private void test(final String snippet, final int expectedBarriers) { + Debug.scope("WriteBarrierAditionTest", new DebugDumpScope(snippet), new Runnable() { + + public void run() { + StructuredGraph graph = parse(snippet); + new LoweringPhase(null, runtime(), replacements, new Assumptions(false)).apply(graph); + new WriteBarrierAdditionPhase().apply(graph); + Debug.dump(graph, "After Write Barrier Addition"); + final int barriers = graph.getNodes(SerialWriteBarrier.class).count(); + Assert.assertTrue(barriers == expectedBarriers); + for (WriteNode write : graph.getNodes(WriteNode.class)) { + if (write.getWriteBarrierType() != WriteBarrierType.NONE) { + Assert.assertTrue(write.successors().count() == 1); + Assert.assertTrue(write.successors().first() instanceof SerialWriteBarrier); + } + } + } + }); + } +}
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/EscapeAnalysisTest.java Tue Apr 23 11:21:05 2013 +0200 @@ -218,9 +218,6 @@ public ReturnNode call() { new GraphBuilderPhase(runtime, GraphBuilderConfiguration.getEagerDefault(), OptimisticOptimizations.ALL).apply(graph); - for (Invoke n : graph.getInvokes()) { - n.setInliningRelevance(1); - } Assumptions assumptions = new Assumptions(false); HighTierContext context = new HighTierContext(runtime(), assumptions);
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/IterativeInliningTest.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/IterativeInliningTest.java Tue Apr 23 11:21:05 2013 +0200 @@ -33,7 +33,6 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.phases.*; -import com.oracle.graal.phases.common.*; import com.oracle.graal.phases.tiers.*; import com.oracle.graal.virtual.phases.ea.*; @@ -101,7 +100,6 @@ private void processMethod(final String snippet) { graph = parse(snippet); - new ComputeProbabilityPhase().apply(graph); GraalOptions.OptEarlyReadElimination = true; HighTierContext context = new HighTierContext(runtime(), new Assumptions(false)); new IterativeInliningPhase(replacements, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL, false).apply(graph, context);
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PEAReadEliminationTest.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PEAReadEliminationTest.java Tue Apr 23 11:21:05 2013 +0200 @@ -221,7 +221,6 @@ private void processMethod(final String snippet) { graph = parse(snippet); - new ComputeProbabilityPhase().apply(graph); Assumptions assumptions = new Assumptions(false); HighTierContext context = new HighTierContext(runtime(), assumptions); new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java Tue Apr 23 11:21:05 2013 +0200 @@ -34,8 +34,10 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.java.*; +import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.graph.*; import com.oracle.graal.phases.tiers.*; import com.oracle.graal.virtual.nodes.*; import com.oracle.graal.virtual.phases.ea.*; @@ -131,10 +133,12 @@ try { Assert.assertTrue("partial escape analysis should have removed all NewInstanceNode allocations", result.getNodes(NewInstanceNode.class).isEmpty()); Assert.assertTrue("partial escape analysis should have removed all NewArrayNode allocations", result.getNodes(NewArrayNode.class).isEmpty()); + + NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(result).apply(); double probabilitySum = 0; int materializeCount = 0; for (MaterializeObjectNode materialize : result.getNodes(MaterializeObjectNode.class)) { - probabilitySum += materialize.probability(); + probabilitySum += nodeProbabilities.get(materialize); materializeCount++; } Assert.assertEquals("unexpected number of MaterializeObjectNodes", expectedCount, materializeCount); @@ -156,10 +160,7 @@ @Override public StructuredGraph call() { StructuredGraph graph = parse(snippet); - new ComputeProbabilityPhase().apply(graph); - for (Invoke n : graph.getInvokes()) { - n.asNode().setProbability(100000); - } + Assumptions assumptions = new Assumptions(false); HighTierContext context = new HighTierContext(runtime(), assumptions); new InliningPhase(runtime(), null, replacements, assumptions, null, getDefaultPhasePlan(), OptimisticOptimizations.ALL).apply(graph);
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/inlining/InliningTest.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/inlining/InliningTest.java Tue Apr 23 11:21:05 2013 +0200 @@ -158,7 +158,6 @@ StructuredGraph graph = eagerInfopointMode ? parseDebug(method) : parse(method); PhasePlan phasePlan = getDefaultPhasePlan(eagerInfopointMode); Assumptions assumptions = new Assumptions(true); - new ComputeProbabilityPhase().apply(graph); Debug.dump(graph, "Graph"); new InliningPhase(runtime(), null, replacements, assumptions, null, phasePlan, OptimisticOptimizations.ALL).apply(graph); Debug.dump(graph, "Graph");
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Tue Apr 23 11:21:05 2013 +0200 @@ -38,9 +38,11 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.PhasePlan.PhasePosition; import com.oracle.graal.phases.common.*; +import com.oracle.graal.phases.graph.*; import com.oracle.graal.phases.schedule.*; import com.oracle.graal.phases.tiers.*; import com.oracle.graal.virtual.phases.ea.*; @@ -99,8 +101,8 @@ * * @param target */ - public static LIR emitHIR(GraalCodeCacheProvider runtime, TargetDescription target, StructuredGraph graph, Replacements replacements, Assumptions assumptions, GraphCache cache, PhasePlan plan, - OptimisticOptimizations optimisticOpts, final SpeculationLog speculationLog) { + public static LIR emitHIR(GraalCodeCacheProvider runtime, TargetDescription target, final StructuredGraph graph, Replacements replacements, Assumptions assumptions, GraphCache cache, + PhasePlan plan, OptimisticOptimizations optimisticOpts, final SpeculationLog speculationLog) { if (speculationLog != null) { speculationLog.snapshot(); @@ -113,10 +115,6 @@ Debug.dump(graph, "initial state"); } - if (GraalOptions.ProbabilityAnalysis && graph.start().probability() == 0) { - new ComputeProbabilityPhase().apply(graph); - } - if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase.Instance(runtime, assumptions).apply(graph); } @@ -170,14 +168,13 @@ assert startBlock != null; assert startBlock.getPredecessorCount() == 0; - new ComputeProbabilityPhase().apply(graph); - return Debug.scope("ComputeLinearScanOrder", new Callable<LIR>() { @Override public LIR call() { - List<Block> codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blocks.length, startBlock); - List<Block> linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blocks.length, startBlock); + NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); + List<Block> codeEmittingOrder = ComputeBlockOrder.computeCodeEmittingOrder(blocks.length, startBlock, nodeProbabilities); + List<Block> linearScanOrder = ComputeBlockOrder.computeLinearScanOrder(blocks.length, startBlock, nodeProbabilities); LIR lir = new LIR(schedule.getCFG(), schedule.getBlockToNodesMap(), linearScanOrder, codeEmittingOrder, speculationLog); Debug.dump(lir, "After linear scan order");
--- a/graal/com.oracle.graal.hotspot.amd64.test/src/com/oracle/graal/hotspot/amd64/test/AMD64HotSpotFrameOmissionTest.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.hotspot.amd64.test/src/com/oracle/graal/hotspot/amd64/test/AMD64HotSpotFrameOmissionTest.java Tue Apr 23 11:21:05 2013 +0200 @@ -30,6 +30,7 @@ import org.junit.*; import com.oracle.graal.api.code.*; +import com.oracle.graal.api.code.Register.RegisterFlag; import com.oracle.graal.api.meta.*; import com.oracle.graal.api.runtime.*; import com.oracle.graal.asm.amd64.*; @@ -70,8 +71,9 @@ @Override public void generateCode(AMD64Assembler asm) { - asm.addl(rsi, 5); - asm.movl(rax, rsi); + Register arg = getArgumentRegister(0, RegisterFlag.CPU); + asm.addl(arg, 5); + asm.movl(rax, arg); asm.ret(0); } }); @@ -87,8 +89,9 @@ @Override public void generateCode(AMD64Assembler asm) { - asm.addq(rsi, 1); - asm.movq(rax, rsi); + Register arg = getArgumentRegister(0, RegisterFlag.CPU); + asm.addq(arg, 1); + asm.movq(rax, arg); asm.ret(0); } }); @@ -113,4 +116,9 @@ Assert.assertArrayEquals(expectedCode, actualCode); } + + private Register getArgumentRegister(int index, RegisterFlag flag) { + Register[] regs = runtime.lookupRegisterConfig().getCallingConventionRegisters(CallingConvention.Type.JavaCall, flag); + return regs[index]; + } }
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotVMConfig.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/HotSpotVMConfig.java Tue Apr 23 11:21:05 2013 +0200 @@ -363,6 +363,7 @@ public long logPrimitiveStub; public long logObjectStub; public long logPrintfStub; + public long stubPrintfStub; public int deoptReasonNone; public long threadIsInterruptedStub; public long identityHashCodeStub;
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotRuntime.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/meta/HotSpotRuntime.java Tue Apr 23 11:21:05 2013 +0200 @@ -262,6 +262,14 @@ /* arg2: value */ Kind.Long, /* arg3: value */ Kind.Long)); + addRuntimeCall(Stub.STUB_PRINTF, config.stubPrintfStub, + /* temps */ null, + /* ret */ ret(Kind.Void), + /* arg0: format */ javaCallingConvention(Kind.Long, + /* arg1: value */ Kind.Long, + /* arg2: value */ Kind.Long, + /* arg3: value */ Kind.Long)); + addRuntimeCall(LOG_OBJECT, config.logObjectStub, /* temps */ null, /* ret */ ret(Kind.Void),
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/nodes/CStringNode.java Tue Apr 23 11:21:05 2013 +0200 @@ -0,0 +1,61 @@ +/* + * Copyright (c) 2012, 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.hotspot.nodes; + +import static com.oracle.graal.graph.UnsafeAccess.*; + +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.calc.*; +import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.type.*; +import com.oracle.graal.word.*; + +/** + * Converts a compile-time constant Java string into a malloc'ed C string. The malloc'ed string is + * never reclaimed so this should only be used for strings in permanent code such as compiled stubs. + */ +public final class CStringNode extends FloatingNode implements Lowerable { + + private final String string; + + public CStringNode(String string) { + super(StampFactory.forWord()); + this.string = string; + } + + @Override + public void lower(LoweringTool tool) { + byte[] formatBytes = string.getBytes(); + long cstring = unsafe.allocateMemory(formatBytes.length + 1); + for (int i = 0; i < formatBytes.length; i++) { + unsafe.putByte(cstring + i, formatBytes[i]); + } + unsafe.putByte(cstring + formatBytes.length, (byte) 0); + StructuredGraph graph = (StructuredGraph) graph(); + ConstantNode replacement = ConstantNode.forLong(cstring, graph); + graph.replaceFloating(this, replacement); + } + + @NodeIntrinsic + public static native Word cstring(@ConstantNodeParameter String string); +}
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/NewInstanceStub.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/NewInstanceStub.java Tue Apr 23 11:21:05 2013 +0200 @@ -208,40 +208,4 @@ private static boolean forceSlowPath() { return Boolean.getBoolean("graal.newInstanceStub.forceSlowPath"); } - - static void log(boolean enabled, String format, long value) { - if (enabled) { - Log.printf(format, value); - } - } - - static void log(boolean enabled, String format, WordBase value) { - if (enabled) { - Log.printf(format, value.rawValue()); - } - } - - static void log(boolean enabled, String format, long v1, long v2) { - if (enabled) { - Log.printf(format, v1, v2); - } - } - - static void log(boolean enabled, String format, Word v1, long v2) { - if (enabled) { - Log.printf(format, v1.rawValue(), v2); - } - } - - static void log(boolean enabled, String format, Word v1, Word v2) { - if (enabled) { - Log.printf(format, v1.rawValue(), v2.rawValue()); - } - } - - static void log(boolean enabled, String format, long v1, long v2, long v3) { - if (enabled) { - Log.printf(format, v1, v2, v3); - } - } }
--- a/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/Stub.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.hotspot/src/com/oracle/graal/hotspot/stubs/Stub.java Tue Apr 23 11:21:05 2013 +0200 @@ -22,19 +22,25 @@ */ package com.oracle.graal.hotspot.stubs; +import static com.oracle.graal.hotspot.nodes.CStringNode.*; + import java.util.*; import java.util.concurrent.*; import com.oracle.graal.api.code.*; +import com.oracle.graal.api.code.RuntimeCallTarget.Descriptor; import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.*; import com.oracle.graal.compiler.target.*; import com.oracle.graal.debug.*; import com.oracle.graal.debug.internal.*; +import com.oracle.graal.graph.Node.ConstantNodeParameter; +import com.oracle.graal.graph.Node.NodeIntrinsic; import com.oracle.graal.hotspot.*; import com.oracle.graal.hotspot.meta.*; import com.oracle.graal.java.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.PhasePlan.PhasePosition; @@ -43,6 +49,7 @@ import com.oracle.graal.replacements.SnippetTemplate.AbstractTemplates; import com.oracle.graal.replacements.SnippetTemplate.Arguments; import com.oracle.graal.replacements.SnippetTemplate.SnippetInfo; +import com.oracle.graal.word.*; /** * Base class for implementing some low level code providing the out-of-line slow path for a @@ -156,4 +163,52 @@ } return code; } + + static void log(boolean enabled, String format, long value) { + if (enabled) { + printf(format, value); + } + } + + static void log(boolean enabled, String format, WordBase value) { + if (enabled) { + printf(format, value.rawValue()); + } + } + + static void log(boolean enabled, String format, Word v1, long v2) { + if (enabled) { + printf(format, v1.rawValue(), v2); + } + } + + static void log(boolean enabled, String format, Word v1, Word v2) { + if (enabled) { + printf(format, v1.rawValue(), v2.rawValue()); + } + } + + public static final Descriptor STUB_PRINTF = new Descriptor("stubPrintf", false, void.class, Word.class, long.class, long.class, long.class); + + @NodeIntrinsic(RuntimeCallNode.class) + private static native void printf(@ConstantNodeParameter Descriptor stubPrintf, Word format, long v1, long v2, long v3); + + /** + * Prints a formatted string to the log stream. + * + * @param format a C style printf format value that can contain at most one conversion specifier + * (i.e., a sequence of characters starting with '%'). + * @param value the value associated with the conversion specifier + */ + public static void printf(String format, long value) { + printf(STUB_PRINTF, cstring(format), value, 0L, 0L); + } + + public static void printf(String format, long v1, long v2) { + printf(STUB_PRINTF, cstring(format), v1, v2, 0L); + } + + public static void printf(String format, long v1, long v2, long v3) { + printf(STUB_PRINTF, cstring(format), v1, v2, v3); + } }
--- a/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/FrameMap.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/FrameMap.java Tue Apr 23 11:21:05 2013 +0200 @@ -96,11 +96,16 @@ /** * Size of the area occupied by outgoing overflow arguments. This value is adjusted as calling - * conventions for outgoing calls are retrieved. + * conventions for outgoing calls are retrieved. On some platforms, there is a minimum */ private int outgoingSize; /** + * Determines if this frame has values on the stack for outgoing calls. + */ + private boolean hasOutgoingStackArguments; + + /** * The list of stack areas allocated in this frame that are present in every reference map. */ private final List<StackSlot> objectStackBlocks; @@ -157,8 +162,8 @@ * {@link Architecture#getReturnAddressSize() return address slot}. */ public boolean frameNeedsAllocating() { - int unalignedFrameSize = outgoingSize + spillSize - returnAddressSize(); - return unalignedFrameSize != 0; + int unalignedFrameSize = spillSize - returnAddressSize(); + return hasOutgoingStackArguments || unalignedFrameSize != 0; } /** @@ -247,6 +252,7 @@ public void reserveOutgoing(int argsSize) { assert frameSize == -1 : "frame size must not yet be fixed"; outgoingSize = Math.max(outgoingSize, argsSize); + hasOutgoingStackArguments = hasOutgoingStackArguments || argsSize > 0; } private StackSlot getSlot(Kind kind, int additionalOffset) {
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java Tue Apr 23 11:21:05 2013 +0200 @@ -248,7 +248,6 @@ continue; } MergeNode merge = graph.add(new MergeNode()); - merge.setProbability(next.probability()); EndNode originalEnd = graph.add(new EndNode()); EndNode newEnd = graph.add(new EndNode()); merge.addForwardEnd(originalEnd);
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInside.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInside.java Tue Apr 23 11:21:05 2013 +0200 @@ -102,7 +102,6 @@ GraphUtil.killWithUnusedFloatingInputs(state); } loop.entryPoint().replaceAtPredecessor(entry); - end.setProbability(loop.entryPoint().probability()); end.setNext(loop.entryPoint()); }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Tue Apr 23 11:21:05 2013 +0200 @@ -26,6 +26,7 @@ import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.cfg.*; +import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; public abstract class LoopPolicies { @@ -35,9 +36,9 @@ } // TODO (gd) change when inversion is available - public static boolean shouldPeel(LoopEx loop) { + public static boolean shouldPeel(LoopEx loop, NodesToDoubles probabilities) { LoopBeginNode loopBegin = loop.loopBegin(); - double entryProbability = loopBegin.forwardEnd().probability(); + double entryProbability = probabilities.get(loopBegin.forwardEnd()); return entryProbability > GraalOptions.MinimumPeelProbability && loop.size() + loopBegin.graph().getNodeCount() < GraalOptions.MaximumDesiredSize; }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java Tue Apr 23 11:21:05 2013 +0200 @@ -27,7 +27,7 @@ import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; -import com.oracle.graal.loop.InductionVariable.*; +import com.oracle.graal.loop.InductionVariable.Direction; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.calc.*; import com.oracle.graal.nodes.cfg.*; @@ -39,7 +39,6 @@ private ControlFlowGraph cfg; public LoopsData(final StructuredGraph graph) { - cfg = Debug.scope("ControlFlowGraph", new Callable<ControlFlowGraph>() { @Override
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformHighPhase.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopTransformHighPhase.java Tue Apr 23 11:21:05 2013 +0200 @@ -25,7 +25,9 @@ import com.oracle.graal.debug.*; import com.oracle.graal.loop.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; +import com.oracle.graal.phases.graph.*; public class LoopTransformHighPhase extends Phase { @@ -33,9 +35,10 @@ protected void run(StructuredGraph graph) { if (graph.hasLoops()) { if (GraalOptions.LoopPeeling) { + NodesToDoubles probabilities = new ComputeProbabilityClosure(graph).apply(); LoopsData data = new LoopsData(graph); for (LoopEx loop : data.outterFirst()) { - if (LoopPolicies.shouldPeel(loop)) { + if (LoopPolicies.shouldPeel(loop, probabilities)) { Debug.log("Peeling %s", loop); LoopTransformations.peel(loop); Debug.dump(graph, "After peeling %s", loop);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FixedNode.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/FixedNode.java Tue Apr 23 11:21:05 2013 +0200 @@ -28,8 +28,6 @@ public abstract class FixedNode extends ValueNode { - private double probability; - public FixedNode(Stamp stamp) { super(stamp); } @@ -42,20 +40,6 @@ super(stamp, dependencies); } - public double probability() { - return probability; - } - - public void setProbability(double probability) { - assert probability >= 0 : String.format("Invalid argument %f, because the probability of a node must not be negative.", probability); - this.probability = probability; - assert !Double.isNaN(probability); - } - - protected void copyInto(FixedNode newNode) { - newNode.setProbability(probability); - } - @Override public boolean verify() { assertTrue(this.successors().isNotEmpty() || this.predecessor() != null, "FixedNode should not float");
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/IfNode.java Tue Apr 23 11:21:05 2013 +0200 @@ -361,13 +361,10 @@ PhiNode oldPhi = (PhiNode) oldMerge.usages().first(); PhiNode newPhi = graph().add(new PhiNode(oldPhi.stamp(), newMerge)); - double probability = 0.0; for (EndNode end : ends) { newPhi.addInput(phiValues.get(end)); newMerge.addForwardEnd(end); - probability += end.probability(); } - newMerge.setProbability(probability); FrameState stateAfter = oldMerge.stateAfter(); if (stateAfter != null) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/Invoke.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/Invoke.java Tue Apr 23 11:21:05 2013 +0200 @@ -45,14 +45,6 @@ void intrinsify(Node node); - double probability(); - - void setProbability(double value); - - double inliningRelevance(); - - void setInliningRelevance(double value); - boolean useForInlining(); void setUseForInlining(boolean value);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeNode.java Tue Apr 23 11:21:05 2013 +0200 @@ -41,7 +41,6 @@ private final int bci; private boolean polymorphic; private boolean useForInlining; - private double inliningRelevance; /** * Constructs a new Invoke instruction. @@ -55,7 +54,6 @@ this.bci = bci; this.polymorphic = false; this.useForInlining = true; - this.inliningRelevance = Double.NaN; } @Override @@ -83,16 +81,6 @@ } @Override - public double inliningRelevance() { - return inliningRelevance; - } - - @Override - public void setInliningRelevance(double value) { - inliningRelevance = value; - } - - @Override public Map<Object, Object> getDebugProperties(Map<Object, Object> map) { Map<Object, Object> debugProperties = super.getDebugProperties(map); debugProperties.put("targetMethod", callTarget.targetName());
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/InvokeWithExceptionNode.java Tue Apr 23 11:21:05 2013 +0200 @@ -42,7 +42,6 @@ private final int bci; private boolean polymorphic; private boolean useForInlining; - private double inliningRelevance; public InvokeWithExceptionNode(CallTargetNode callTarget, DispatchBeginNode exceptionEdge, int bci) { super(callTarget.returnStamp()); @@ -51,7 +50,6 @@ this.callTarget = callTarget; this.polymorphic = false; this.useForInlining = true; - this.inliningRelevance = Double.NaN; } public DispatchBeginNode exceptionEdge() { @@ -101,16 +99,6 @@ } @Override - public double inliningRelevance() { - return inliningRelevance; - } - - @Override - public void setInliningRelevance(double value) { - inliningRelevance = value; - } - - @Override public String toString(Verbosity verbosity) { if (verbosity == Verbosity.Long) { return super.toString(Verbosity.Short) + "(bci=" + bci() + ")";
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/SerialWriteBarrier.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/SerialWriteBarrier.java Tue Apr 23 11:21:05 2013 +0200 @@ -22,11 +22,12 @@ */ package com.oracle.graal.nodes; +import com.oracle.graal.graph.*; import com.oracle.graal.nodes.extended.*; import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.type.*; -public final class SerialWriteBarrier extends FixedWithNextNode implements Lowerable { +public final class SerialWriteBarrier extends FixedWithNextNode implements Lowerable, Node.IterableNodeType { @Input private ValueNode object; @Input private LocationNode location;
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/StructuredGraph.java Tue Apr 23 11:21:05 2013 +0200 @@ -236,7 +236,6 @@ public void replaceFixedWithFixed(FixedWithNextNode node, FixedWithNextNode replacement) { assert node != null && replacement != null && node.isAlive() && replacement.isAlive() : "cannot replace " + node + " with " + replacement; - replacement.setProbability(node.probability()); FixedNode next = node.next(); node.setNext(null); replacement.setNext(next); @@ -307,7 +306,6 @@ public void addAfterFixed(FixedWithNextNode node, FixedNode newNode) { assert node != null && newNode != null && node.isAlive() && newNode.isAlive() : "cannot add " + newNode + " after " + node; - newNode.setProbability(node.probability()); FixedNode next = node.next(); node.setNext(newNode); if (next != null) { @@ -322,7 +320,6 @@ assert node != null && newNode != null && node.isAlive() && newNode.isAlive() : "cannot add " + newNode + " before " + node; assert node.predecessor() != null && node.predecessor() instanceof FixedWithNextNode : "cannot add " + newNode + " before " + node; assert newNode.next() == null : newNode; - newNode.setProbability(node.probability()); FixedWithNextNode pred = (FixedWithNextNode) node.predecessor(); pred.setNext(newNode); newNode.setNext(node); @@ -334,7 +331,6 @@ reduceTrivialMerge(begin); } else { // convert to merge MergeNode merge = this.add(new MergeNode()); - merge.setProbability(begin.probability()); this.replaceFixedWithFixed(begin, merge); } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java Tue Apr 23 11:21:05 2013 +0200 @@ -29,9 +29,10 @@ public final class Block { + protected final BeginNode beginNode; + protected int id; - protected BeginNode beginNode; protected FixedNode endNode; protected Loop loop; @@ -45,8 +46,10 @@ private boolean align; private int linearScanNumber; - protected Block() { - id = ControlFlowGraph.BLOCK_ID_INITIAL; + protected Block(BeginNode node) { + this.beginNode = node; + + this.id = ControlFlowGraph.BLOCK_ID_INITIAL; this.linearScanNumber = -1; } @@ -206,10 +209,6 @@ return dominator.isDominatedBy(block); } - public double getProbability() { - return getBeginNode().probability(); - } - public int getLinearScanNumber() { return linearScanNumber; }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Tue Apr 23 11:21:05 2013 +0200 @@ -39,6 +39,7 @@ public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) { ControlFlowGraph cfg = new ControlFlowGraph(graph); cfg.identifyBlocks(); + if (connectBlocks || computeLoops || computeDominators || computePostdominators) { cfg.connectBlocks(); } @@ -111,16 +112,15 @@ public void clearNodeToBlock() { nodeToBlock.clear(); for (Block block : reversePostOrder) { - identifyBlock(block, block.beginNode); + identifyBlock(block); } } protected static final int BLOCK_ID_INITIAL = -1; protected static final int BLOCK_ID_VISITED = -2; - private void identifyBlock(Block block, BeginNode begin) { - block.beginNode = begin; - Node cur = begin; + private void identifyBlock(Block block) { + Node cur = block.getBeginNode(); Node last; do { assert !cur.isDeleted(); @@ -145,9 +145,9 @@ int numBlocks = 0; for (Node node : graph.getNodes()) { if (node instanceof BeginNode) { - Block block = new Block(); + Block block = new Block((BeginNode) node); numBlocks++; - identifyBlock(block, (BeginNode) node); + identifyBlock(block); } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/AddLocationNode.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/AddLocationNode.java Tue Apr 23 11:21:05 2013 +0200 @@ -48,11 +48,11 @@ public static AddLocationNode create(LocationNode x, LocationNode y, Graph graph) { assert x.getValueKind().equals(y.getValueKind()) && x.locationIdentity() == y.locationIdentity(); - return graph.unique(new AddLocationNode(x, y)); + return graph.unique(new AddLocationNode(x.locationIdentity(), x.getValueKind(), x, y)); } - private AddLocationNode(LocationNode x, LocationNode y) { - super(x.locationIdentity(), x.getValueKind()); + private AddLocationNode(Object identity, Kind kind, ValueNode x, ValueNode y) { + super(identity, kind); this.x = x; this.y = y; } @@ -60,7 +60,7 @@ @Override protected LocationNode addDisplacement(long displacement) { LocationNode added = getX().addDisplacement(displacement); - return graph().unique(new AddLocationNode(added, getY())); + return graph().unique(new AddLocationNode(locationIdentity(), getValueKind(), added, getY())); } @Override @@ -86,20 +86,23 @@ } @Override - public Value generateLea(LIRGeneratorTool gen, Value base) { - Value xAddr = getX().generateLea(gen, base); - return getY().generateLea(gen, xAddr); + public Value generateAddress(LIRGeneratorTool gen, Value base) { + Value xAddr = getX().generateAddress(gen, base); + return getY().generateAddress(gen, xAddr); } @Override public Value generateLoad(LIRGeneratorTool gen, Value base, DeoptimizingNode deopting) { - Value xAddr = getX().generateLea(gen, base); + Value xAddr = getX().generateAddress(gen, base); return getY().generateLoad(gen, xAddr, deopting); } @Override public void generateStore(LIRGeneratorTool gen, Value base, Value value, DeoptimizingNode deopting) { - Value xAddr = getX().generateLea(gen, base); + Value xAddr = getX().generateAddress(gen, base); getY().generateStore(gen, xAddr, value, deopting); } + + @NodeIntrinsic + public static native Location addLocation(@ConstantNodeParameter Object identity, @ConstantNodeParameter Kind kind, Location x, Location y); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/ComputeAddressNode.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/ComputeAddressNode.java Tue Apr 23 11:21:05 2013 +0200 @@ -49,7 +49,7 @@ @Override public void generate(LIRGeneratorTool gen) { - Value addr = getLocation().generateLea(gen, gen.operand(getObject())); + Value addr = getLocation().generateAddress(gen, gen.operand(getObject())); gen.setResult(this, addr); } }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/ConstantLocationNode.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/ConstantLocationNode.java Tue Apr 23 11:21:05 2013 +0200 @@ -55,7 +55,7 @@ } @Override - public Value generateLea(LIRGeneratorTool gen, Value base) { + public Value generateAddress(LIRGeneratorTool gen, Value base) { return gen.emitLea(base, displacement(), Value.ILLEGAL, 0); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/IndexedLocationNode.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/IndexedLocationNode.java Tue Apr 23 11:21:05 2013 +0200 @@ -58,10 +58,14 @@ } public static IndexedLocationNode create(Object identity, Kind kind, long displacement, ValueNode index, Graph graph, int indexScaling) { - return graph.unique(new IndexedLocationNode(identity, kind, index, displacement, indexScaling)); + return graph.unique(new IndexedLocationNode(identity, kind, displacement, index, indexScaling)); } - private IndexedLocationNode(Object identity, Kind kind, ValueNode index, long displacement, int indexScaling) { + private IndexedLocationNode(Object identity, Kind kind, ValueNode index, int indexScaling) { + this(identity, kind, 0, index, indexScaling); + } + + private IndexedLocationNode(Object identity, Kind kind, long displacement, ValueNode index, int indexScaling) { super(identity, kind); this.index = index; this.displacement = displacement; @@ -86,7 +90,7 @@ } @Override - public Value generateLea(LIRGeneratorTool gen, Value base) { + public Value generateAddress(LIRGeneratorTool gen, Value base) { return gen.emitLea(base, displacement, gen.operand(index()), indexScaling()); } @@ -99,4 +103,7 @@ public void generateStore(LIRGeneratorTool gen, Value base, Value value, DeoptimizingNode deopting) { gen.emitStore(getValueKind(), base, displacement, gen.operand(index()), indexScaling(), value, deopting); } + + @NodeIntrinsic + public static native Location indexedLocation(@ConstantNodeParameter Object identity, @ConstantNodeParameter Kind kind, int index, @ConstantNodeParameter int indexScaling); }
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/LocationNode.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/extended/LocationNode.java Tue Apr 23 11:21:05 2013 +0200 @@ -30,9 +30,9 @@ import com.oracle.graal.nodes.type.*; /** - * A location for a memory access in terms of the kind of value accessed and how to access it. - * All locations have the form [base + location], where base is a node and location is defined - * by subclasses of the {@link LocationNode}. + * A location for a memory access in terms of the kind of value accessed and how to access it. All + * locations have the form [base + location], where base is a node and location is defined by + * subclasses of the {@link LocationNode}. */ public abstract class LocationNode extends FloatingNode implements LIRLowerable, ValueNumberable { @@ -41,7 +41,7 @@ /** * Creates a new unique location identity for read and write operations. - * + * * @param name the name of the new location identity, for debugging purposes * @return the new location identity */ @@ -67,6 +67,12 @@ */ public static final Object FINAL_LOCATION = createLocation("FINAL_LOCATION"); + /** + * Marker interface for locations in snippets. + */ + public interface Location { + } + public static Object getArrayLocation(Kind elementKind) { return elementKind; } @@ -93,7 +99,7 @@ // nothing to do... } - public abstract Value generateLea(LIRGeneratorTool gen, Value base); + public abstract Value generateAddress(LIRGeneratorTool gen, Value base); public abstract Value generateLoad(LIRGeneratorTool gen, Value base, DeoptimizingNode deopting);
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/GenericStamp.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/GenericStamp.java Tue Apr 23 11:21:05 2013 +0200 @@ -33,7 +33,7 @@ private final GenericStampType type; protected GenericStamp(GenericStampType type) { - super(Kind.Void); + super(type == GenericStampType.Void ? Kind.Void : Kind.Illegal); this.type = type; }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/util/NodesToDoubles.java Tue Apr 23 11:21:05 2013 +0200 @@ -0,0 +1,46 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.nodes.util; + +import java.util.*; + +import com.oracle.graal.nodes.*; + +public class NodesToDoubles { + + private final IdentityHashMap<FixedNode, Double> nodeProbabilities; + + public NodesToDoubles(int numberOfNodes) { + this.nodeProbabilities = new IdentityHashMap<>(numberOfNodes); + } + + public void put(FixedNode n, double value) { + nodeProbabilities.put(n, value); + } + + public double get(FixedNode n) { + Double value = nodeProbabilities.get(n); + assert value != null; + return value; + } +}
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityPhase.java Tue Apr 23 11:20:53 2013 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,459 +0,0 @@ -/* - * 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.graal.phases.common; - -import java.util.*; - -import com.oracle.graal.debug.*; -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; -import com.oracle.graal.nodes.cfg.*; -import com.oracle.graal.phases.*; -import com.oracle.graal.phases.graph.*; - -/** - * Computes probabilities for nodes in a graph. - * <p> - * The computation of absolute probabilities works in three steps: - * <ol> - * <li>{@link PropagateProbability} traverses the graph in post order (merges after their ends, ...) - * and keeps track of the "probability state". Whenever it encounters a {@link ControlSplitNode} it - * uses the split's probability information to divide the probability upon the successors. Whenever - * it encounters an {@link Invoke} it assumes that the exception edge is unlikely and propagates the - * whole probability to the normal successor. Whenever it encounters a {@link MergeNode} it sums up - * the probability of all predecessors. It also maintains a set of active loops (whose - * {@link LoopBeginNode} has been visited) and builds def/use information for step 2.</li> - * <li></li> - * <li>{@link PropagateLoopFrequency} propagates the loop frequencies and multiplies each - * {@link FixedNode}'s probability with its loop frequency.</li> - * </ol> - * TODO: add exception probability information to Invokes - */ -public class ComputeProbabilityPhase extends Phase { - - private static final double EPSILON = 1d / Integer.MAX_VALUE; - - @Override - protected void run(StructuredGraph graph) { - new PropagateProbability(graph.start()).apply(); - Debug.dump(graph, "After PropagateProbability"); - computeLoopFactors(); - Debug.dump(graph, "After computeLoopFactors"); - new PropagateLoopFrequency(graph.start()).apply(); - new ComputeInliningRelevanceIterator(graph).apply(); - } - - private void computeLoopFactors() { - 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 LoopBeginNode loopBegin; - - public final NodeMap<Set<LoopInfo>> requires; - - private double loopFrequency = -1; - public boolean ended = false; - - public LoopInfo(LoopBeginNode loopBegin) { - this.loopBegin = loopBegin; - this.requires = loopBegin.graph().createNodeMap(); - } - - public double loopFrequency() { - if (loopFrequency == -1 && ended) { - double backEdgeProb = 0.0; - for (LoopEndNode le : loopBegin.loopEnds()) { - double factor = 1; - Set<LoopInfo> requireds = requires.get(le); - for (LoopInfo required : requireds) { - double t = required.loopFrequency(); - if (t == -1) { - return -1; - } - factor *= t; - } - backEdgeProb += le.probability() * factor; - } - double d = loopBegin.probability() - backEdgeProb; - if (d < EPSILON) { - d = EPSILON; - } - loopFrequency = loopBegin.probability() / d; - loopBegin.setLoopFrequency(loopFrequency); - } - return loopFrequency; - } - } - - public Set<LoopInfo> loopInfos = new HashSet<>(); - public Map<MergeNode, Set<LoopInfo>> mergeLoops = new IdentityHashMap<>(); - - 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<>(4); - if (loops != null) { - this.loops.addAll(loops); - } - } - - @Override - public Probability clone() { - return new Probability(probability, loops); - } - - @Override - public boolean merge(MergeNode merge, List<Probability> withStates) { - if (merge.forwardEndCount() > 1) { - HashSet<LoopInfo> intersection = new HashSet<>(loops); - for (Probability other : withStates) { - intersection.retainAll(other.loops); - } - for (LoopInfo info : loops) { - if (!intersection.contains(info)) { - double loopFrequency = info.loopFrequency(); - if (loopFrequency == -1) { - return false; - } - probability *= loopFrequency; - } - } - for (Probability other : withStates) { - double prob = other.probability; - for (LoopInfo info : other.loops) { - if (!intersection.contains(info)) { - double loopFrequency = info.loopFrequency(); - if (loopFrequency == -1) { - return false; - } - prob *= loopFrequency; - } - } - probability += prob; - } - loops = intersection; - mergeLoops.put(merge, new HashSet<>(intersection)); - assert isRelativeProbability(probability) : probability; - } - return true; - } - - @Override - public void loopBegin(LoopBeginNode loopBegin) { - loopInfo = new LoopInfo(loopBegin); - loopInfos.add(loopInfo); - loops.add(loopInfo); - } - - @Override - public void loopEnds(LoopBeginNode loopBegin, List<Probability> loopEndStates) { - assert loopInfo != null; - List<LoopEndNode> loopEnds = loopBegin.orderedLoopEnds(); - int i = 0; - for (Probability proba : loopEndStates) { - LoopEndNode loopEnd = loopEnds.get(i++); - Set<LoopInfo> requires = loopInfo.requires.get(loopEnd); - if (requires == null) { - requires = new HashSet<>(); - loopInfo.requires.set(loopEnd, requires); - } - for (LoopInfo innerLoop : proba.loops) { - if (innerLoop != loopInfo && !this.loops.contains(innerLoop)) { - requires.add(innerLoop); - } - } - } - loopInfo.ended = true; - } - - @Override - public void afterSplit(BeginNode node) { - assert node.predecessor() != null; - Node pred = node.predecessor(); - if (pred instanceof Invoke) { - Invoke x = (Invoke) pred; - if (x.next() != node) { - probability = 0; - } - } else { - assert pred instanceof ControlSplitNode; - ControlSplitNode x = (ControlSplitNode) pred; - probability *= x.probability(node); - } - } - } - - private class PropagateProbability extends PostOrderNodeIterator<Probability> { - - public PropagateProbability(FixedNode start) { - super(start, new Probability(1d, null)); - } - - @Override - protected void node(FixedNode 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(MergeNode merge, List<LoopCount> withStates) { - assert merge.forwardEndCount() == withStates.size() + 1; - if (merge.forwardEndCount() > 1) { - Set<LoopInfo> loops = mergeLoops.get(merge); - assert loops != null; - double countProd = 1; - for (LoopInfo loop : loops) { - countProd *= loop.loopFrequency(); - } - count = countProd; - } - return true; - } - - @Override - public void loopBegin(LoopBeginNode loopBegin) { - count *= loopBegin.loopFrequency(); - } - - @Override - public void loopEnds(LoopBeginNode loopBegin, List<LoopCount> loopEndStates) { - // nothing to do... - } - - @Override - public void afterSplit(BeginNode 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); - } - - } - - private static class ComputeInliningRelevanceIterator extends ScopedPostOrderNodeIterator { - - private final HashMap<FixedNode, Scope> scopes; - private double currentProbability; - private double parentRelevance; - - public ComputeInliningRelevanceIterator(StructuredGraph graph) { - super(graph); - this.scopes = computeLowestPathProbabilities(computeScopeInformation(graph)); - } - - @Override - protected void initializeScope() { - Scope scope = scopes.get(currentScopeStart); - parentRelevance = getParentScopeRelevance(scope); - currentProbability = scope.minPathProbability; - } - - private static double getParentScopeRelevance(Scope scope) { - if (scope.start instanceof LoopBeginNode) { - assert scope.parent != null; - double parentProbability = 0; - for (EndNode end : ((LoopBeginNode) scope.start).forwardEnds()) { - parentProbability += end.probability(); - } - return parentProbability / scope.parent.minPathProbability; - } else { - assert scope.parent == null; - return 1.0; - } - } - - @Override - protected void invoke(Invoke invoke) { - assert !Double.isNaN(invoke.probability()); - invoke.setInliningRelevance((invoke.probability() / currentProbability) * Math.min(1.0, parentRelevance)); - assert !Double.isNaN(invoke.inliningRelevance()); - } - - private static Scope[] computeScopeInformation(StructuredGraph graph) { - ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); - - Loop[] loops = cfg.getLoops(); - HashMap<Loop, Scope> processedScopes = new HashMap<>(); - Scope[] scopes = new Scope[loops.length + 1]; - Scope methodScope = new Scope(graph.start(), null); - processedScopes.put(null, methodScope); - - scopes[0] = methodScope; - for (int i = 0; i < loops.length; i++) { - scopes[i + 1] = createScope(loops[i], processedScopes); - } - - return scopes; - } - - private static Scope createScope(Loop loop, HashMap<Loop, Scope> processedLoops) { - Scope parent = processedLoops.get(loop.parent); - if (parent == null) { - parent = createScope(loop.parent, processedLoops); - } - Scope result = new Scope(loop.loopBegin(), parent); - processedLoops.put(loop, result); - return result; - } - - private static HashMap<FixedNode, Scope> computeLowestPathProbabilities(Scope[] scopes) { - HashMap<FixedNode, Scope> result = new HashMap<>(); - - for (Scope scope : scopes) { - double lowestPathProbability = computeLowestPathProbability(scope); - scope.minPathProbability = Math.max(EPSILON, lowestPathProbability); - result.put(scope.start, scope); - } - - return result; - } - - private static double computeLowestPathProbability(Scope scope) { - FixedNode scopeStart = scope.start; - ArrayList<FixedNode> pathBeginNodes = new ArrayList<>(); - pathBeginNodes.add(scopeStart); - double minPathProbability = scopeStart.probability(); - boolean isLoopScope = scopeStart instanceof LoopBeginNode; - - do { - Node current = pathBeginNodes.remove(pathBeginNodes.size() - 1); - do { - if (isLoopScope && current instanceof LoopExitNode && ((LoopBeginNode) scopeStart).loopExits().contains((LoopExitNode) current)) { - return minPathProbability; - } else if (current instanceof LoopBeginNode && current != scopeStart) { - current = getMaxProbabilityLoopExit((LoopBeginNode) current, pathBeginNodes); - minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability); - } else if (current instanceof ControlSplitNode) { - current = getMaxProbabilitySux((ControlSplitNode) current, pathBeginNodes); - minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability); - } else { - assert current.successors().count() <= 1; - current = current.successors().first(); - } - } while (current != null); - } while (!pathBeginNodes.isEmpty()); - - return minPathProbability; - } - - private static double getMinPathProbability(FixedNode current, double minPathProbability) { - if (current != null && current.probability() < minPathProbability) { - return current.probability(); - } - return minPathProbability; - } - - private static Node getMaxProbabilitySux(ControlSplitNode controlSplit, ArrayList<FixedNode> pathBeginNodes) { - Node maxSux = null; - double maxProbability = 0.0; - int pathBeginCount = pathBeginNodes.size(); - - for (Node sux : controlSplit.successors()) { - double probability = controlSplit.probability((BeginNode) sux); - if (probability > maxProbability) { - maxProbability = probability; - maxSux = sux; - truncate(pathBeginNodes, pathBeginCount); - } else if (probability == maxProbability) { - pathBeginNodes.add((FixedNode) sux); - } - } - - return maxSux; - } - - private static Node getMaxProbabilityLoopExit(LoopBeginNode loopBegin, ArrayList<FixedNode> pathBeginNodes) { - Node maxSux = null; - double maxProbability = 0.0; - int pathBeginCount = pathBeginNodes.size(); - - for (LoopExitNode sux : loopBegin.loopExits()) { - double probability = sux.probability(); - if (probability > maxProbability) { - maxProbability = probability; - maxSux = sux; - truncate(pathBeginNodes, pathBeginCount); - } else if (probability == maxProbability) { - pathBeginNodes.add(sux); - } - } - - return maxSux; - } - - public static void truncate(ArrayList<FixedNode> pathBeginNodes, int pathBeginCount) { - for (int i = pathBeginNodes.size() - pathBeginCount; i > 0; i--) { - pathBeginNodes.remove(pathBeginNodes.size() - 1); - } - } - } - - private static class Scope { - - public final FixedNode start; - public final Scope parent; - public double minPathProbability; - - public Scope(FixedNode start, Scope parent) { - this.start = start; - this.parent = parent; - } - } -}
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java Tue Apr 23 11:21:05 2013 +0200 @@ -33,12 +33,14 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.PhasePlan.PhasePosition; import com.oracle.graal.phases.common.CanonicalizerPhase.CustomCanonicalizer; import com.oracle.graal.phases.common.InliningUtil.InlineInfo; import com.oracle.graal.phases.common.InliningUtil.InliningCallback; import com.oracle.graal.phases.common.InliningUtil.InliningPolicy; +import com.oracle.graal.phases.graph.*; public class InliningPhase extends Phase implements InliningCallback { @@ -99,13 +101,15 @@ @Override protected void run(final StructuredGraph graph) { + NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); + NodesToDoubles nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).apply(); inliningPolicy.initialize(graph); while (inliningPolicy.continueInlining(graph)) { final InlineInfo candidate = inliningPolicy.next(); if (candidate != null) { - boolean isWorthInlining = inliningPolicy.isWorthInlining(candidate); + boolean isWorthInlining = inliningPolicy.isWorthInlining(candidate, nodeProbabilities, nodeRelevance); isWorthInlining &= candidate.numberOfMethods() <= maxMethodPerInlining; metricInliningConsidered.increment(); @@ -120,6 +124,10 @@ if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase.Instance(runtime, assumptions, invokeUsages, mark, customCanonicalizer).apply(graph); } + + nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); + nodeRelevance = new ComputeInliningRelevanceClosure(graph, nodeProbabilities).apply(); + inliningCount++; metricInliningPerformed.increment(); } catch (BailoutException bailout) { @@ -157,10 +165,8 @@ } assert newGraph.start().next() != null : "graph needs to be populated during PhasePosition.AFTER_PARSING"; - if (GraalOptions.ProbabilityAnalysis) { - new DeadCodeEliminationPhase().apply(newGraph); - new ComputeProbabilityPhase().apply(newGraph); - } + new DeadCodeEliminationPhase().apply(newGraph); + if (GraalOptions.OptCanonicalizer) { new CanonicalizerPhase.Instance(runtime, assumptions).apply(newGraph); } @@ -177,7 +183,7 @@ private interface InliningDecision { - boolean isWorthInlining(InlineInfo info); + boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance); } private static class GreedySizeBasedInliningDecision implements InliningDecision { @@ -193,8 +199,7 @@ } @Override - public boolean isWorthInlining(InlineInfo info) { - assert GraalOptions.ProbabilityAnalysis; + public boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance) { /* * TODO (chaeubl): invoked methods that are on important paths but not yet compiled -> * will be compiled anyways and it is likely that we are the only caller... might be @@ -220,8 +225,7 @@ int bytecodeSize = (int) (bytecodeCodeSize(info) / bonus); int complexity = (int) (compilationComplexity(info) / bonus); int compiledCodeSize = (int) (compiledCodeSize(info) / bonus); - double relevance = info.invoke().inliningRelevance(); - + double relevance = nodeRelevance.get(info.invoke().asNode()); /* * as long as the compiled code size is small enough (or the method was not yet * compiled), we can do a pretty general inlining that suits most situations @@ -240,7 +244,7 @@ * the normal inlining did not fit this invoke, so check if we have any reason why we * should still do the inlining */ - double probability = info.invoke().probability(); + double probability = nodeProbabilities.get(info.invoke().asNode()); int transferredValues = numberOfTransferredValues(info); int invokeUsages = countInvokeUsages(info); int moreSpecificArguments = countMoreSpecificArgumentInfo(info); @@ -409,8 +413,9 @@ return info; } - public boolean isWorthInlining(InlineInfo info) { - return inliningDecision.isWorthInlining(info); + @Override + public boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance) { + return inliningDecision.isWorthInlining(info, nodeProbabilities, nodeRelevance); } public void initialize(StructuredGraph graph) {
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java Tue Apr 23 11:21:05 2013 +0200 @@ -70,7 +70,7 @@ void scanInvokes(Iterable<? extends Node> newNodes); - boolean isWorthInlining(InlineInfo info); + boolean isWorthInlining(InlineInfo info, NodesToDoubles nodeProbabilities, NodesToDoubles nodeRelevance); } /** @@ -260,7 +260,6 @@ } catch (ReflectiveOperationException | IllegalArgumentException | SecurityException e) { throw new GraalInternalError(e).addContext(invoke.asNode()).addContext("macroSubstitution", macroNodeClass); } - macroNode.setProbability(invoke.asNode().probability()); CallTargetNode callTarget = invoke.callTarget(); if (invoke instanceof InvokeNode) { graph.replaceFixedWithFixed((InvokeNode) invoke, graph.add(macroNode)); @@ -466,7 +465,6 @@ ValueNode originalReceiver = ((MethodCallTargetNode) invoke.callTarget()).receiver(); // setup merge and phi nodes for results and exceptions MergeNode returnMerge = graph.add(new MergeNode()); - returnMerge.setProbability(invoke.probability()); returnMerge.setStateAfter(invoke.stateAfter().duplicate(invoke.stateAfter().bci)); PhiNode returnValuePhi = null; @@ -481,7 +479,6 @@ ExceptionObjectNode exceptionEdge = (ExceptionObjectNode) invokeWithException.exceptionEdge(); exceptionMerge = graph.add(new MergeNode()); - exceptionMerge.setProbability(exceptionEdge.probability()); FixedNode exceptionSux = exceptionEdge.next(); graph.addBeforeFixed(exceptionSux, exceptionMerge); @@ -492,20 +489,13 @@ // create one separate block for each invoked method BeginNode[] successors = new BeginNode[numberOfMethods + 1]; for (int i = 0; i < numberOfMethods; i++) { - double probability = 0; - for (int j = 0; j < typesToConcretes.length; j++) { - if (typesToConcretes[j] == i) { - probability += ptypes.get(j).getProbability(); - } - } - - successors[i] = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, invoke.probability() * probability, true); + successors[i] = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, true); } // create the successor for an unknown type FixedNode unknownTypeSux; if (shouldFallbackToInvoke()) { - unknownTypeSux = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, notRecordedTypeProbability, false); + unknownTypeSux = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, false); } else { unknownTypeSux = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated)); } @@ -612,7 +602,6 @@ assert concretes.size() == 1 && ptypes.size() > 1 && !shouldFallbackToInvoke() && notRecordedTypeProbability == 0; BeginNode calleeEntryNode = graph.add(new BeginNode()); - calleeEntryNode.setProbability(invoke.probability()); BeginNode unknownTypeSux = createUnknownTypeSuccessor(graph); BeginNode[] successors = new BeginNode[]{calleeEntryNode, unknownTypeSux}; @@ -649,15 +638,12 @@ } private static BeginNode createInvocationBlock(StructuredGraph graph, Invoke invoke, MergeNode returnMerge, PhiNode returnValuePhi, MergeNode exceptionMerge, PhiNode exceptionObjectPhi, - double probability, boolean useForInlining) { - Invoke duplicatedInvoke = duplicateInvokeForInlining(graph, invoke, exceptionMerge, exceptionObjectPhi, useForInlining, probability); + boolean useForInlining) { + Invoke duplicatedInvoke = duplicateInvokeForInlining(graph, invoke, exceptionMerge, exceptionObjectPhi, useForInlining); BeginNode calleeEntryNode = graph.add(new BeginNode()); calleeEntryNode.setNext(duplicatedInvoke.asNode()); - calleeEntryNode.setProbability(probability); EndNode endNode = graph.add(new EndNode()); - endNode.setProbability(probability); - duplicatedInvoke.setNext(endNode); returnMerge.addForwardEnd(endNode); @@ -667,13 +653,11 @@ return calleeEntryNode; } - private static Invoke duplicateInvokeForInlining(StructuredGraph graph, Invoke invoke, MergeNode exceptionMerge, PhiNode exceptionObjectPhi, boolean useForInlining, double probability) { + private static Invoke duplicateInvokeForInlining(StructuredGraph graph, Invoke invoke, MergeNode exceptionMerge, PhiNode exceptionObjectPhi, boolean useForInlining) { Invoke result = (Invoke) invoke.asNode().copyWithInputs(); Node callTarget = result.callTarget().copyWithInputs(); result.asNode().replaceFirstInput(result.callTarget(), callTarget); result.setUseForInlining(useForInlining); - result.setProbability(probability); - result.setInliningRelevance(invoke.inliningRelevance() * probability); Kind kind = invoke.asNode().kind(); if (kind != Kind.Void) { @@ -738,8 +722,6 @@ InliningUtil.receiverNullCheck(invoke); BeginNode invocationEntry = graph.add(new BeginNode()); - invocationEntry.setProbability(invoke.probability()); - BeginNode unknownTypeSux = createUnknownTypeSuccessor(graph); BeginNode[] successors = new BeginNode[]{invocationEntry, unknownTypeSux}; createDispatchOnTypeBeforeInvoke(graph, successors, true); @@ -966,6 +948,7 @@ return graph.unique(new PiNode(receiver, exact ? StampFactory.exactNonNull(commonType) : StampFactory.declaredNonNull(commonType), anchor)); } + // TODO (chaeubl): cleanup this method private static boolean checkInvokeConditions(Invoke invoke) { if (invoke.predecessor() == null || !invoke.asNode().isAlive()) { return logNotInlinedMethodAndReturnFalse(invoke, "the invoke is dead code"); @@ -974,6 +957,7 @@ } else if (((MethodCallTargetNode) invoke.callTarget()).targetMethod() == null) { return logNotInlinedMethodAndReturnFalse(invoke, "target method is null"); } else if (invoke.stateAfter() == null) { + // TODO (chaeubl): why should an invoke not have a state after? return logNotInlinedMethodAndReturnFalse(invoke, "the invoke has no after state"); } else if (!invoke.useForInlining()) { return logNotInlinedMethodAndReturnFalse(invoke, "the invoke is marked to be not used for inlining"); @@ -1127,27 +1111,8 @@ } FrameState outerFrameState = null; - double invokeProbability = invoke.asNode().probability(); int callerLockDepth = stateAfter.nestedLockDepth(); for (Node node : duplicates.values()) { - if (GraalOptions.ProbabilityAnalysis) { - if (node instanceof FixedNode) { - FixedNode fixed = (FixedNode) node; - double newProbability = fixed.probability() * invokeProbability; - if (GraalOptions.LimitInlinedProbability) { - newProbability = Math.min(newProbability, invokeProbability); - } - fixed.setProbability(newProbability); - } - if (node instanceof Invoke) { - Invoke newInvoke = (Invoke) node; - double newRelevance = newInvoke.inliningRelevance() * invoke.inliningRelevance(); - if (GraalOptions.LimitInlinedRelevance) { - newRelevance = Math.min(newRelevance, invoke.inliningRelevance()); - } - newInvoke.setInliningRelevance(newRelevance); - } - } if (node instanceof FrameState) { FrameState frameState = (FrameState) node; assert frameState.bci != FrameState.BEFORE_BCI : frameState;
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/TailDuplicationPhase.java Tue Apr 23 11:21:05 2013 +0200 @@ -35,6 +35,7 @@ import com.oracle.graal.nodes.type.*; import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; +import com.oracle.graal.phases.graph.*; /** * This class is a phase that looks for opportunities for tail duplication. The static method @@ -129,10 +130,12 @@ @Override protected void run(StructuredGraph graph) { + NodesToDoubles nodeProbabilities = new ComputeProbabilityClosure(graph).apply(); + // A snapshot is taken here, so that new MergeNode instances aren't considered for tail // duplication. for (MergeNode merge : graph.getNodes(MergeNode.class).snapshot()) { - if (!(merge instanceof LoopBeginNode) && merge.probability() >= GraalOptions.TailDuplicationProbability) { + if (!(merge instanceof LoopBeginNode) && nodeProbabilities.get(merge) >= GraalOptions.TailDuplicationProbability) { tailDuplicate(merge, DEFAULT_DECISION, null); } } @@ -219,7 +222,7 @@ * </ul> */ private void duplicate() { - Debug.log("tail duplication at merge %s in %s (prob %f)", merge, graph.method(), merge.probability()); + Debug.log("tail duplication at merge %s in %s", merge, graph.method()); ValueAnchorNode anchor = addValueAnchor(); @@ -420,9 +423,7 @@ */ private EndNode createNewMerge(FixedNode successor, FrameState stateAfterMerge) { MergeNode newBottomMerge = graph.add(new MergeNode()); - newBottomMerge.setProbability(successor.probability()); EndNode newBottomEnd = graph.add(new EndNode()); - newBottomEnd.setProbability(successor.probability()); newBottomMerge.addForwardEnd(newBottomEnd); newBottomMerge.setStateAfter(stateAfterMerge); ((FixedWithNextNode) successor.predecessor()).setNext(newBottomEnd);
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java Tue Apr 23 11:21:05 2013 +0200 @@ -47,8 +47,6 @@ static boolean InlineMegamorphicCalls = ____; public static int MaximumDesiredSize = 5000; public static int MaximumRecursiveInlining = 1; - public static boolean LimitInlinedProbability = ____; - public static boolean LimitInlinedRelevance = true; public static float BoostInliningForEscapeAnalysis = 2f; public static float RelevanceCapForInlining = 1f; public static boolean IterativeInlining = ____; @@ -75,9 +73,6 @@ public static double TailDuplicationProbability = 0.5; public static int TailDuplicationTrivialSize = 1; - // absolute probability analysis - public static boolean ProbabilityAnalysis = true; - // profiling information public static int DeoptsToDisableOptimisticOptimization = 40; public static int MatureExecutionsBranch = 1;
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/OptimisticOptimizations.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/OptimisticOptimizations.java Tue Apr 23 11:21:05 2013 +0200 @@ -53,10 +53,6 @@ if (checkDeoptimizations(method.getProfilingInfo(), deoptReason)) { enabledOpts.add(optimization); } else { - /* - * TODO (chaeubl): see GRAAL-75 (remove when we are sure that optimistic optimizations - * are not disabled unnecessarily - */ disabledOptimisticOptsMetric.increment(); } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeInliningRelevanceClosure.java Tue Apr 23 11:21:05 2013 +0200 @@ -0,0 +1,223 @@ +/* + * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ +package com.oracle.graal.phases.graph; + +import java.util.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; +import com.oracle.graal.nodes.util.*; + +public class ComputeInliningRelevanceClosure { + + private static final double EPSILON = 1d / Integer.MAX_VALUE; + + private final StructuredGraph graph; + private final NodesToDoubles nodeProbabilities; + private final NodesToDoubles nodeRelevances; + + public ComputeInliningRelevanceClosure(StructuredGraph graph, NodesToDoubles nodeProbabilities) { + this.graph = graph; + this.nodeProbabilities = nodeProbabilities; + this.nodeRelevances = new NodesToDoubles(graph.getNodeCount()); + } + + public NodesToDoubles apply() { + new ComputeInliningRelevanceIterator(graph).apply(); + return nodeRelevances; + } + + private class ComputeInliningRelevanceIterator extends ScopedPostOrderNodeIterator { + + private final HashMap<FixedNode, Scope> scopes; + private double currentProbability; + private double parentRelevance; + + public ComputeInliningRelevanceIterator(StructuredGraph graph) { + super(graph); + this.scopes = computeLowestPathProbabilities(); + } + + @Override + protected void initializeScope() { + Scope scope = scopes.get(currentScopeStart); + parentRelevance = getParentScopeRelevance(scope); + currentProbability = scope.minPathProbability; + } + + private double getParentScopeRelevance(Scope scope) { + if (scope.start instanceof LoopBeginNode) { + assert scope.parent != null; + double parentProbability = 0; + for (EndNode end : ((LoopBeginNode) scope.start).forwardEnds()) { + parentProbability += nodeProbabilities.get(end); + } + return parentProbability / scope.parent.minPathProbability; + } else { + assert scope.parent == null; + return 1.0; + } + } + + @Override + protected void invoke(Invoke invoke) { + double probability = nodeProbabilities.get(invoke.asNode()); + assert !Double.isNaN(probability); + + double relevance = (probability / currentProbability) * Math.min(1.0, parentRelevance); + nodeRelevances.put(invoke.asNode(), relevance); + assert !Double.isNaN(relevance); + } + + private HashMap<FixedNode, Scope> computeLowestPathProbabilities() { + HashMap<FixedNode, Scope> result = new HashMap<>(); + + for (Scope scope : computeScopes()) { + double lowestPathProbability = computeLowestPathProbability(scope); + scope.minPathProbability = Math.max(EPSILON, lowestPathProbability); + result.put(scope.start, scope); + } + + return result; + } + + private Scope[] computeScopes() { + ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); + + Loop[] loops = cfg.getLoops(); + HashMap<Loop, Scope> processedScopes = new HashMap<>(); + Scope[] result = new Scope[loops.length + 1]; + Scope methodScope = new Scope(graph.start(), null); + processedScopes.put(null, methodScope); + + result[0] = methodScope; + for (int i = 0; i < loops.length; i++) { + result[i + 1] = createScope(loops[i], processedScopes); + } + + return result; + } + + private Scope createScope(Loop loop, HashMap<Loop, Scope> processedLoops) { + Scope parent = processedLoops.get(loop.parent); + if (parent == null) { + parent = createScope(loop.parent, processedLoops); + } + Scope result = new Scope(loop.loopBegin(), parent); + processedLoops.put(loop, result); + return result; + } + + private double computeLowestPathProbability(Scope scope) { + FixedNode scopeStart = scope.start; + ArrayList<FixedNode> pathBeginNodes = new ArrayList<>(); + pathBeginNodes.add(scopeStart); + double minPathProbability = nodeProbabilities.get(scopeStart); + boolean isLoopScope = scopeStart instanceof LoopBeginNode; + + do { + Node current = pathBeginNodes.remove(pathBeginNodes.size() - 1); + do { + if (isLoopScope && current instanceof LoopExitNode && ((LoopBeginNode) scopeStart).loopExits().contains((LoopExitNode) current)) { + return minPathProbability; + } else if (current instanceof LoopBeginNode && current != scopeStart) { + current = getMaxProbabilityLoopExit((LoopBeginNode) current, pathBeginNodes); + minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability); + } else if (current instanceof ControlSplitNode) { + current = getMaxProbabilitySux((ControlSplitNode) current, pathBeginNodes); + minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability); + } else { + assert current.successors().count() <= 1; + current = current.successors().first(); + } + } while (current != null); + } while (!pathBeginNodes.isEmpty()); + + return minPathProbability; + } + + private double getMinPathProbability(FixedNode current, double minPathProbability) { + if (current != null && nodeProbabilities.get(current) < minPathProbability) { + return nodeProbabilities.get(current); + } + return minPathProbability; + } + + private Node getMaxProbabilitySux(ControlSplitNode controlSplit, ArrayList<FixedNode> pathBeginNodes) { + Node maxSux = null; + double maxProbability = 0.0; + int pathBeginCount = pathBeginNodes.size(); + + for (Node sux : controlSplit.successors()) { + double probability = controlSplit.probability((BeginNode) sux); + if (probability > maxProbability) { + maxProbability = probability; + maxSux = sux; + truncate(pathBeginNodes, pathBeginCount); + } else if (probability == maxProbability) { + pathBeginNodes.add((FixedNode) sux); + } + } + + return maxSux; + } + + private Node getMaxProbabilityLoopExit(LoopBeginNode loopBegin, ArrayList<FixedNode> pathBeginNodes) { + Node maxSux = null; + double maxProbability = 0.0; + int pathBeginCount = pathBeginNodes.size(); + + for (LoopExitNode sux : loopBegin.loopExits()) { + double probability = nodeProbabilities.get(sux); + if (probability > maxProbability) { + maxProbability = probability; + maxSux = sux; + truncate(pathBeginNodes, pathBeginCount); + } else if (probability == maxProbability) { + pathBeginNodes.add(sux); + } + } + + return maxSux; + } + + private void truncate(ArrayList<FixedNode> pathBeginNodes, int pathBeginCount) { + for (int i = pathBeginNodes.size() - pathBeginCount; i > 0; i--) { + pathBeginNodes.remove(pathBeginNodes.size() - 1); + } + } + } + + private static class Scope { + + public final FixedNode start; + public final Scope parent; + public double minPathProbability; + + public Scope(FixedNode start, Scope parent) { + this.start = start; + this.parent = parent; + } + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/ComputeProbabilityClosure.java Tue Apr 23 11:21:05 2013 +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.graal.phases.graph; + +import java.util.*; + +import com.oracle.graal.debug.*; +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.util.*; + +/** + * Computes probabilities for nodes in a graph. + * <p> + * The computation of absolute probabilities works in three steps: + * <ol> + * <li>{@link PropagateProbability} traverses the graph in post order (merges after their ends, ...) + * and keeps track of the "probability state". Whenever it encounters a {@link ControlSplitNode} it + * uses the split's probability information to divide the probability upon the successors. Whenever + * it encounters an {@link Invoke} it assumes that the exception edge is unlikely and propagates the + * whole probability to the normal successor. Whenever it encounters a {@link MergeNode} it sums up + * the probability of all predecessors. It also maintains a set of active loops (whose + * {@link LoopBeginNode} has been visited) and builds def/use information for step 2.</li> + * <li></li> + * <li>{@link PropagateLoopFrequency} propagates the loop frequencies and multiplies each + * {@link FixedNode}'s probability with its loop frequency.</li> + * </ol> + * TODO: add exception probability information to Invokes + */ +public class ComputeProbabilityClosure { + + private static final double EPSILON = 1d / Integer.MAX_VALUE; + + private final StructuredGraph graph; + private final NodesToDoubles nodeProbabilities; + private final Set<LoopInfo> loopInfos; + private final Map<MergeNode, Set<LoopInfo>> mergeLoops; + + public ComputeProbabilityClosure(StructuredGraph graph) { + this.graph = graph; + this.nodeProbabilities = new NodesToDoubles(graph.getNodeCount()); + this.loopInfos = new HashSet<>(); + this.mergeLoops = new IdentityHashMap<>(); + } + + public NodesToDoubles apply() { + new PropagateProbability(graph.start()).apply(); + Debug.dump(graph, "After PropagateProbability"); + computeLoopFactors(); + Debug.dump(graph, "After computeLoopFactors"); + new PropagateLoopFrequency(graph.start()).apply(); + return nodeProbabilities; + } + + private void computeLoopFactors() { + for (LoopInfo info : loopInfos) { + double frequency = info.loopFrequency(nodeProbabilities); + 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 LoopBeginNode loopBegin; + + public final NodeMap<Set<LoopInfo>> requires; + + private double loopFrequency = -1; + public boolean ended = false; + + public LoopInfo(LoopBeginNode loopBegin) { + this.loopBegin = loopBegin; + this.requires = loopBegin.graph().createNodeMap(); + } + + public double loopFrequency(NodesToDoubles nodeProbabilities) { + if (loopFrequency == -1 && ended) { + double backEdgeProb = 0.0; + for (LoopEndNode le : loopBegin.loopEnds()) { + double factor = 1; + Set<LoopInfo> requireds = requires.get(le); + for (LoopInfo required : requireds) { + double t = required.loopFrequency(nodeProbabilities); + if (t == -1) { + return -1; + } + factor *= t; + } + backEdgeProb += nodeProbabilities.get(le) * factor; + } + double d = nodeProbabilities.get(loopBegin) - backEdgeProb; + if (d < EPSILON) { + d = EPSILON; + } + loopFrequency = nodeProbabilities.get(loopBegin) / d; + loopBegin.setLoopFrequency(loopFrequency); + } + return loopFrequency; + } + } + + 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<>(4); + if (loops != null) { + this.loops.addAll(loops); + } + } + + @Override + public Probability clone() { + return new Probability(probability, loops); + } + + @Override + public boolean merge(MergeNode merge, List<Probability> withStates) { + if (merge.forwardEndCount() > 1) { + HashSet<LoopInfo> intersection = new HashSet<>(loops); + for (Probability other : withStates) { + intersection.retainAll(other.loops); + } + for (LoopInfo info : loops) { + if (!intersection.contains(info)) { + double loopFrequency = info.loopFrequency(nodeProbabilities); + if (loopFrequency == -1) { + return false; + } + probability *= loopFrequency; + } + } + for (Probability other : withStates) { + double prob = other.probability; + for (LoopInfo info : other.loops) { + if (!intersection.contains(info)) { + double loopFrequency = info.loopFrequency(nodeProbabilities); + if (loopFrequency == -1) { + return false; + } + prob *= loopFrequency; + } + } + probability += prob; + } + loops = intersection; + mergeLoops.put(merge, new HashSet<>(intersection)); + assert isRelativeProbability(probability) : probability; + } + return true; + } + + @Override + public void loopBegin(LoopBeginNode loopBegin) { + loopInfo = new LoopInfo(loopBegin); + loopInfos.add(loopInfo); + loops.add(loopInfo); + } + + @Override + public void loopEnds(LoopBeginNode loopBegin, List<Probability> loopEndStates) { + assert loopInfo != null; + List<LoopEndNode> loopEnds = loopBegin.orderedLoopEnds(); + int i = 0; + for (Probability proba : loopEndStates) { + LoopEndNode loopEnd = loopEnds.get(i++); + Set<LoopInfo> requires = loopInfo.requires.get(loopEnd); + if (requires == null) { + requires = new HashSet<>(); + loopInfo.requires.set(loopEnd, requires); + } + for (LoopInfo innerLoop : proba.loops) { + if (innerLoop != loopInfo && !this.loops.contains(innerLoop)) { + requires.add(innerLoop); + } + } + } + loopInfo.ended = true; + } + + @Override + public void afterSplit(BeginNode node) { + assert node.predecessor() != null; + Node pred = node.predecessor(); + if (pred instanceof Invoke) { + Invoke x = (Invoke) pred; + if (x.next() != node) { + probability = 0; + } + } else { + assert pred instanceof ControlSplitNode; + ControlSplitNode x = (ControlSplitNode) pred; + probability *= x.probability(node); + } + } + } + + private class PropagateProbability extends PostOrderNodeIterator<Probability> { + + public PropagateProbability(FixedNode start) { + super(start, new Probability(1d, null)); + } + + @Override + protected void node(FixedNode node) { + nodeProbabilities.put(node, 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(MergeNode merge, List<LoopCount> withStates) { + assert merge.forwardEndCount() == withStates.size() + 1; + if (merge.forwardEndCount() > 1) { + Set<LoopInfo> loops = mergeLoops.get(merge); + assert loops != null; + double countProd = 1; + for (LoopInfo loop : loops) { + countProd *= loop.loopFrequency(nodeProbabilities); + } + count = countProd; + } + return true; + } + + @Override + public void loopBegin(LoopBeginNode loopBegin) { + count *= loopBegin.loopFrequency(); + } + + @Override + public void loopEnds(LoopBeginNode loopBegin, List<LoopCount> loopEndStates) { + // nothing to do... + } + + @Override + public void afterSplit(BeginNode 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) { + nodeProbabilities.put(node, nodeProbabilities.get(node) * state.count); + } + + } +}
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/CFGPrinterObserver.java Tue Apr 23 11:21:05 2013 +0200 @@ -146,7 +146,8 @@ } else if (object instanceof StructuredGraph) { if (cfgPrinter.cfg == null) { - cfgPrinter.cfg = ControlFlowGraph.compute((StructuredGraph) object, true, true, true, false); + StructuredGraph graph = (StructuredGraph) object; + cfgPrinter.cfg = ControlFlowGraph.compute(graph, true, true, true, false); } cfgPrinter.printCFG(message, Arrays.asList(cfgPrinter.cfg.getBlocks()));
--- a/graal/com.oracle.graal.replacements.test/src/com/oracle/graal/replacements/test/MethodSubstitutionTest.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.replacements.test/src/com/oracle/graal/replacements/test/MethodSubstitutionTest.java Tue Apr 23 11:21:05 2013 +0200 @@ -50,7 +50,6 @@ StructuredGraph graph = parse(snippet); PhasePlan phasePlan = getDefaultPhasePlan(); Assumptions assumptions = new Assumptions(true); - new ComputeProbabilityPhase().apply(graph); Debug.dump(graph, "Graph"); new InliningPhase(runtime(), null, replacements, assumptions, null, phasePlan, OptimisticOptimizations.ALL).apply(graph); Debug.dump(graph, "Graph");
--- a/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsImpl.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.replacements/src/com/oracle/graal/replacements/ReplacementsImpl.java Tue Apr 23 11:21:05 2013 +0200 @@ -379,10 +379,7 @@ end.disableSafepoint(); } - if (GraalOptions.ProbabilityAnalysis) { - new DeadCodeEliminationPhase().apply(graph); - new ComputeProbabilityPhase().apply(graph); - } + new DeadCodeEliminationPhase().apply(graph); return graph; } }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/BlockState.java Tue Apr 23 11:21:05 2013 +0200 @@ -169,7 +169,6 @@ MaterializeObjectNode materialize = new MaterializeObjectNode(virtual, obj.getLockCount()); ValueNode[] values = new ValueNode[obj.getEntries().length]; - materialize.setProbability(fixed.probability()); obj.escape(materialize, state); deferred.add(virtual); for (int i = 0; i < fieldState.length; i++) {
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/GraphEffectList.java Tue Apr 23 11:21:05 2013 +0200 @@ -49,7 +49,6 @@ assert position.isAlive(); DynamicCounterNode node = graph.add(new DynamicCounterNode(name, increment, addContext)); graph.addBeforeFixed(position, node); - node.setProbability(position.probability()); } }); } @@ -70,7 +69,6 @@ assert position.isAlive(); DynamicCounterNode node = graph.add(new SurvivingCounterNode(name, increment, addContext, checkedValue)); graph.addBeforeFixed(position, node); - node.setProbability(position.probability()); } }); } @@ -94,7 +92,6 @@ public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { assert !node.isAlive() && !node.isDeleted() && position.isAlive(); graph.addBeforeFixed(position, graph.add(node)); - node.setProbability(position.probability()); } }); } @@ -140,7 +137,6 @@ public void apply(StructuredGraph graph, ArrayList<Node> obsoleteNodes) { assert !node.isAlive() && !node.isDeleted() && position.isAlive(); graph.addBeforeFixed(position, graph.add(node)); - node.setProbability(position.probability()); for (int i = 0; i < values.length; i++) { node.getValues().set(i, values[i]); }
--- a/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Tue Apr 23 11:20:53 2013 +0200 +++ b/graal/com.oracle.graal.virtual/src/com/oracle/graal/virtual/phases/ea/PartialEscapeAnalysisPhase.java Tue Apr 23 11:21:05 2013 +0200 @@ -31,6 +31,7 @@ import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.spi.*; +import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; import com.oracle.graal.phases.common.*; import com.oracle.graal.phases.common.CanonicalizerPhase.CustomCanonicalizer; @@ -200,20 +201,21 @@ } public static Map<Invoke, Double> getHints(StructuredGraph graph) { + NodesToDoubles probabilities = new ComputeProbabilityClosure(graph).apply(); Map<Invoke, Double> hints = null; for (MaterializeObjectNode materialize : graph.getNodes(MaterializeObjectNode.class)) { double sum = 0; double invokeSum = 0; for (Node usage : materialize.usages()) { if (usage instanceof FixedNode) { - sum += ((FixedNode) usage).probability(); + sum += probabilities.get((FixedNode) usage); } else { if (usage instanceof MethodCallTargetNode) { - invokeSum += ((MethodCallTargetNode) usage).invoke().probability(); + invokeSum += probabilities.get(((MethodCallTargetNode) usage).invoke().asNode()); } for (Node secondLevelUage : materialize.usages()) { if (secondLevelUage instanceof FixedNode) { - sum += ((FixedNode) secondLevelUage).probability(); + sum += probabilities.get(((FixedNode) secondLevelUage)); } } }
--- a/mx/commands.py Tue Apr 23 11:20:53 2013 +0200 +++ b/mx/commands.py Tue Apr 23 11:21:05 2013 +0200 @@ -812,6 +812,7 @@ testfile = os.environ.get('MX_TESTFILE', None) if testfile is None: (_, testfile) = tempfile.mkstemp(".testclasses", "graal") + os.close(_) def harness(projectscp, vmArgs): if not exists(javaClass) or getmtime(javaClass) < getmtime(javaSource):
--- a/src/cpu/x86/vm/graalRuntime_x86.cpp Tue Apr 23 11:20:53 2013 +0200 +++ b/src/cpu/x86/vm/graalRuntime_x86.cpp Tue Apr 23 11:21:05 2013 +0200 @@ -972,6 +972,18 @@ break; } + case stub_printf_id: { + __ enter(); + oop_maps = new OopMapSet(); + OopMap* oop_map = save_live_registers(sasm, 4); + int call_offset = __ call_RT(noreg, noreg, (address)stub_printf, j_rarg0, j_rarg1, j_rarg2, j_rarg3); + oop_maps->add_gc_map(call_offset, oop_map); + restore_live_registers(sasm); + __ leave(); + __ ret(0); + break; + } + case log_primitive_id: { __ enter(); oop_maps = new OopMapSet();
--- a/src/os/windows/vm/os_windows.cpp Tue Apr 23 11:20:53 2013 +0200 +++ b/src/os/windows/vm/os_windows.cpp Tue Apr 23 11:21:05 2013 +0200 @@ -2179,7 +2179,7 @@ ctx->Rax = (DWORD64)min_jlong; // result } else { ctx->Rip = (DWORD64)pc + 2; // idiv reg, reg is 2 bytes - ctx->Rax = (DWORD64)min_jint; // result + ctx->Rax = (DWORD64)min_jlong; // result } ctx->Rdx = (DWORD64)0; // remainder // Continue the execution
--- a/src/share/vm/graal/graalCompilerToVM.cpp Tue Apr 23 11:20:53 2013 +0200 +++ b/src/share/vm/graal/graalCompilerToVM.cpp Tue Apr 23 11:21:05 2013 +0200 @@ -773,6 +773,7 @@ set_stub("logPrimitiveStub", GraalRuntime::entry_for(GraalRuntime::log_primitive_id)); set_stub("logObjectStub", GraalRuntime::entry_for(GraalRuntime::log_object_id)); set_stub("logPrintfStub", GraalRuntime::entry_for(GraalRuntime::log_printf_id)); + set_stub("stubPrintfStub", GraalRuntime::entry_for(GraalRuntime::stub_printf_id)); set_stub("aescryptEncryptBlockStub", StubRoutines::aescrypt_encryptBlock()); set_stub("aescryptDecryptBlockStub", StubRoutines::aescrypt_decryptBlock()); set_stub("cipherBlockChainingEncryptAESCryptStub", StubRoutines::cipherBlockChaining_encryptAESCrypt());
--- a/src/share/vm/graal/graalRuntime.cpp Tue Apr 23 11:20:53 2013 +0200 +++ b/src/share/vm/graal/graalRuntime.cpp Tue Apr 23 11:21:05 2013 +0200 @@ -565,6 +565,12 @@ tty->print(buf, v1, v2, v3); JRT_END +JRT_LEAF(void, GraalRuntime::stub_printf(JavaThread* thread, jlong format, jlong v1, jlong v2, jlong v3)) + ResourceMark rm; + char *buf = (char*) (address) format; + tty->print(buf, v1, v2, v3); +JRT_END + JRT_ENTRY(void, GraalRuntime::log_primitive(JavaThread* thread, jchar typeChar, jlong value, jboolean newline)) union { jlong l;
--- a/src/share/vm/graal/graalRuntime.hpp Tue Apr 23 11:20:53 2013 +0200 +++ b/src/share/vm/graal/graalRuntime.hpp Tue Apr 23 11:21:05 2013 +0200 @@ -98,6 +98,7 @@ stub(create_out_of_bounds_exception) \ stub(log_object) \ stub(log_printf) \ + stub(stub_printf) \ stub(log_primitive) \ stub(identity_hash_code) \ stub(thread_is_interrupted) \ @@ -146,6 +147,7 @@ static void monitorexit (JavaThread* thread, oopDesc* obj, BasicLock* lock); static void vm_error(JavaThread* thread, oop where, oop format, jlong value); static void log_printf(JavaThread* thread, oop format, jlong v1, jlong v2, jlong v3); + static void stub_printf(JavaThread* thread, jlong format, jlong v1, jlong v2, jlong v3); static void log_primitive(JavaThread* thread, jchar typeChar, jlong value, jboolean newline); static void wb_pre_call(JavaThread* thread, oopDesc* obj); static void wb_post_call(JavaThread* thread, oopDesc* obj, void* card);