Mercurial > hg > truffle
changeset 20069:2dbfa1ed5efa
Reduce usages of fixed node probability cache.
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java Sun Mar 29 20:51:22 2015 +0200 +++ b/graal/com.oracle.graal.compiler.test/src/com/oracle/graal/compiler/test/ea/PartialEscapeAnalysisTest.java Mon Mar 30 00:54:07 2015 +0200 @@ -23,17 +23,15 @@ package com.oracle.graal.compiler.test.ea; import java.lang.ref.*; -import java.util.function.*; - import org.junit.*; import com.oracle.graal.compiler.test.*; import com.oracle.graal.graph.*; import com.oracle.graal.nodes.*; +import com.oracle.graal.nodes.cfg.*; import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.virtual.*; import com.oracle.graal.phases.common.*; -import com.oracle.graal.phases.graph.*; /** * The PartialEscapeAnalysisPhase is expected to remove all allocations and return the correct @@ -186,11 +184,11 @@ Assert.assertTrue("partial escape analysis should have removed all NewInstanceNode allocations", graph.getNodes().filter(NewInstanceNode.class).isEmpty()); Assert.assertTrue("partial escape analysis should have removed all NewArrayNode allocations", graph.getNodes().filter(NewArrayNode.class).isEmpty()); - ToDoubleFunction<FixedNode> nodeProbabilities = new FixedNodeProbabilityCache(); + ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, false, false); double probabilitySum = 0; int materializeCount = 0; for (CommitAllocationNode materialize : graph.getNodes().filter(CommitAllocationNode.class)) { - probabilitySum += nodeProbabilities.applyAsDouble(materialize) * materialize.getVirtualObjects().size(); + probabilitySum += cfg.blockFor(materialize).probability() * materialize.getVirtualObjects().size(); materializeCount += materialize.getVirtualObjects().size(); } Assert.assertEquals("unexpected number of MaterializeObjectNodes", expectedCount, materializeCount); @@ -205,5 +203,4 @@ throw e; } } - }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java Sun Mar 29 20:51:22 2015 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopEx.java Mon Mar 30 00:54:07 2015 +0200 @@ -259,7 +259,7 @@ Collection<AbstractBeginNode> blocks = new LinkedList<>(); Collection<LoopExitNode> exits = new LinkedList<>(); Queue<Block> work = new LinkedList<>(); - ControlFlowGraph cfg = loopsData().controlFlowGraph(); + ControlFlowGraph cfg = loopsData().getCFG(); work.add(cfg.blockFor(branch)); while (!work.isEmpty()) { Block b = work.remove();
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Sun Mar 29 20:51:22 2015 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java Mon Mar 30 00:54:07 2015 +0200 @@ -25,7 +25,6 @@ import static com.oracle.graal.compiler.common.GraalOptions.*; import java.util.*; -import java.util.function.*; import com.oracle.graal.debug.*; import com.oracle.graal.graph.*; @@ -49,12 +48,12 @@ } // TODO (gd) change when inversion is available - public static boolean shouldPeel(LoopEx loop, ToDoubleFunction<FixedNode> probabilities) { + public static boolean shouldPeel(LoopEx loop, ControlFlowGraph cfg) { if (loop.detectCounted()) { return false; } LoopBeginNode loopBegin = loop.loopBegin(); - double entryProbability = probabilities.applyAsDouble(loopBegin.forwardEnd()); + double entryProbability = cfg.blockFor(loopBegin.forwardEnd()).probability(); if (entryProbability > MinimumPeelProbability.getValue() && loop.size() + loopBegin.graph().getNodeCount() < MaximumDesiredSize.getValue()) { // check whether we're allowed to peel this loop for (Node node : loop.inside().nodes()) { @@ -120,7 +119,7 @@ // this may count twice because of fall-through in switches inBranchTotal += loop.nodesInLoopBranch(branch).count(); } - Block postDomBlock = loop.loopsData().controlFlowGraph().blockFor(controlSplit).getPostdominator(); + Block postDomBlock = loop.loopsData().getCFG().blockFor(controlSplit).getPostdominator(); if (postDomBlock != null) { IsolatedInitialization.UNSWITCH_SPLIT_WITH_PHIS.increment(); phis += ((MergeNode) postDomBlock.getBeginNode()).phis().count();
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java Sun Mar 29 20:51:22 2015 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopsData.java Mon Mar 30 00:54:07 2015 +0200 @@ -104,7 +104,7 @@ } } - public ControlFlowGraph controlFlowGraph() { + public ControlFlowGraph getCFG() { return cfg; }
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopPeelingPhase.java Sun Mar 29 20:51:22 2015 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopPeelingPhase.java Mon Mar 30 00:54:07 2015 +0200 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2012, 2015, 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 @@ -22,23 +22,19 @@ */ package com.oracle.graal.loop.phases; -import java.util.function.*; - import com.oracle.graal.debug.*; import com.oracle.graal.loop.*; import com.oracle.graal.nodes.*; import com.oracle.graal.phases.*; -import com.oracle.graal.phases.graph.*; public class LoopPeelingPhase extends Phase { @Override protected void run(StructuredGraph graph) { if (graph.hasLoops()) { - ToDoubleFunction<FixedNode> probabilities = new FixedNodeProbabilityCache(); LoopsData data = new LoopsData(graph); for (LoopEx loop : data.outerFirst()) { - if (LoopPolicies.shouldPeel(loop, probabilities)) { + if (LoopPolicies.shouldPeel(loop, data.getCFG())) { Debug.log("Peeling %s", loop); LoopTransformations.peel(loop); Debug.dump(graph, "After peeling %s", loop);
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopSafepointEliminationPhase.java Sun Mar 29 20:51:22 2015 +0200 +++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/phases/LoopSafepointEliminationPhase.java Mon Mar 30 00:54:07 2015 +0200 @@ -53,7 +53,7 @@ } for (LoopEx loop : loops.countedLoops()) { for (LoopEndNode loopEnd : loop.loopBegin().loopEnds()) { - Block b = loops.controlFlowGraph().blockFor(loopEnd); + Block b = loops.getCFG().blockFor(loopEnd); blocks: while (b != loop.loop().getHeader()) { assert b != null; for (FixedNode node : b.getNodes()) {
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Sun Mar 29 20:51:22 2015 +0200 +++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/ControlFlowGraph.java Mon Mar 30 00:54:07 2015 +0200 @@ -118,6 +118,10 @@ return nodeToBlock.get(node); } + public double frequencyFor(FixedNode node) { + return blockFor(node).probability(); + } + public List<Loop<Block>> getLoops() { return loops; }
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ProfileCompiledMethodsPhase.java Sun Mar 29 20:51:22 2015 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ProfileCompiledMethodsPhase.java Mon Mar 30 00:54:07 2015 +0200 @@ -23,7 +23,6 @@ package com.oracle.graal.phases.common; import java.util.*; -import java.util.function.*; import com.oracle.graal.compiler.common.cfg.*; import com.oracle.graal.graph.*; @@ -36,7 +35,6 @@ import com.oracle.graal.nodes.spi.*; import com.oracle.graal.nodes.virtual.*; import com.oracle.graal.phases.*; -import com.oracle.graal.phases.graph.*; import com.oracle.graal.phases.schedule.*; /** @@ -63,15 +61,14 @@ @Override protected void run(StructuredGraph graph) { - ToDoubleFunction<FixedNode> probabilities = new FixedNodeProbabilityCache(); SchedulePhase schedule = new SchedulePhase(); schedule.apply(graph, false); ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true); for (Loop<Block> loop : cfg.getLoops()) { - double loopProbability = probabilities.applyAsDouble(loop.getHeader().getBeginNode()); + double loopProbability = cfg.blockFor(loop.getHeader().getBeginNode()).probability(); if (loopProbability > (1D / Integer.MAX_VALUE)) { - addSectionCounters(loop.getHeader().getBeginNode(), loop.getBlocks(), loop.getChildren(), schedule, probabilities); + addSectionCounters(loop.getHeader().getBeginNode(), loop.getBlocks(), loop.getChildren(), schedule, cfg); } } // don't put the counter increase directly after the start (problems with OSR) @@ -79,7 +76,7 @@ while (current.next() instanceof FixedWithNextNode) { current = (FixedWithNextNode) current.next(); } - addSectionCounters(current, cfg.getBlocks(), cfg.getLoops(), schedule, probabilities); + addSectionCounters(current, cfg.getBlocks(), cfg.getLoops(), schedule, cfg); if (WITH_INVOKES) { for (Node node : graph.getNodes()) { @@ -92,13 +89,12 @@ } } - private static void addSectionCounters(FixedWithNextNode start, Collection<Block> sectionBlocks, Collection<Loop<Block>> childLoops, SchedulePhase schedule, - ToDoubleFunction<FixedNode> probabilities) { + private static void addSectionCounters(FixedWithNextNode start, Collection<Block> sectionBlocks, Collection<Loop<Block>> childLoops, SchedulePhase schedule, ControlFlowGraph cfg) { HashSet<Block> blocks = new HashSet<>(sectionBlocks); for (Loop<?> loop : childLoops) { blocks.removeAll(loop.getBlocks()); } - double weight = getSectionWeight(schedule, probabilities, blocks) / probabilities.applyAsDouble(start); + double weight = getSectionWeight(schedule, blocks) / cfg.blockFor(start).probability(); DynamicCounterNode.addCounterBefore(GROUP_NAME, sectionHead(start), (long) weight, true, start.next()); if (WITH_INVOKE_FREE_SECTIONS && !hasInvoke(blocks)) { DynamicCounterNode.addCounterBefore(GROUP_NAME_WITHOUT, sectionHead(start), (long) weight, true, start.next()); @@ -113,10 +109,10 @@ } } - private static double getSectionWeight(SchedulePhase schedule, ToDoubleFunction<FixedNode> probabilities, Collection<Block> blocks) { + private static double getSectionWeight(SchedulePhase schedule, Collection<Block> blocks) { double count = 0; for (Block block : blocks) { - double blockProbability = probabilities.applyAsDouble(block.getBeginNode()); + double blockProbability = block.probability(); for (Node node : schedule.getBlockToNodesMap().get(block)) { count += blockProbability * getNodeWeight(node); }
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/FixedNodeProbabilityCache.java Sun Mar 29 20:51:22 2015 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/FixedNodeProbabilityCache.java Mon Mar 30 00:54:07 2015 +0200 @@ -73,6 +73,53 @@ assert node != null; metricComputeNodeProbability.increment(); + FixedNode current = findBegin(node); + if (current == null) { + // this should only appear for dead code + return 1D; + } + + assert current instanceof AbstractBeginNode; + Double cachedValue = cache.get(current); + if (cachedValue != null) { + return cachedValue; + } + + double probability = 0.0; + if (current.predecessor() == null) { + if (current instanceof AbstractMergeNode) { + probability = handleMerge(current, probability); + } else { + assert current instanceof StartNode; + probability = 1D; + } + } else { + ControlSplitNode split = (ControlSplitNode) current.predecessor(); + probability = split.probability((AbstractBeginNode) current) * applyAsDouble(split); + } + assert !Double.isNaN(probability) && !Double.isInfinite(probability) : current + " " + probability; + cache.put(current, probability); + return probability; + } + + private double handleMerge(FixedNode current, double probability) { + double result = probability; + AbstractMergeNode currentMerge = (AbstractMergeNode) current; + NodeInputList<EndNode> currentForwardEnds = currentMerge.forwardEnds(); + /* + * Use simple iteration instead of streams, since the stream infrastructure adds many frames + * which causes the recursion to overflow the stack earlier than it would otherwise. + */ + for (AbstractEndNode endNode : currentForwardEnds) { + result += applyAsDouble(endNode); + } + if (current instanceof LoopBeginNode) { + result *= ((LoopBeginNode) current).loopFrequency(); + } + return result; + } + + private static FixedNode findBegin(FixedNode node) { FixedNode current = node; while (true) { assert current != null; @@ -85,44 +132,11 @@ break; } } else if (predecessor == null) { - // this should only appear for dead code - return 1D; + current = null; + break; } current = (FixedNode) predecessor; } - - assert current instanceof AbstractBeginNode; - Double cachedValue = cache.get(current); - if (cachedValue != null) { - return cachedValue; - } - - double probability = 0.0; - if (current.predecessor() == null) { - if (current instanceof AbstractMergeNode) { - AbstractMergeNode currentMerge = (AbstractMergeNode) current; - NodeInputList<EndNode> currentForwardEnds = currentMerge.forwardEnds(); - /* - * Use simple iteration instead of streams, since the stream infrastructure adds - * many frames which causes the recursion to overflow the stack earlier than it - * would otherwise. - */ - for (AbstractEndNode endNode : currentForwardEnds) { - probability += applyAsDouble(endNode); - } - if (current instanceof LoopBeginNode) { - probability *= ((LoopBeginNode) current).loopFrequency(); - } - } else { - assert current instanceof StartNode; - probability = 1D; - } - } else { - ControlSplitNode split = (ControlSplitNode) current.predecessor(); - probability = split.probability((AbstractBeginNode) current) * applyAsDouble(split); - } - assert !Double.isNaN(probability) && !Double.isInfinite(probability) : current + " " + probability; - cache.put(current, probability); - return probability; + return current; } }
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java Sun Mar 29 20:51:22 2015 +0200 +++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java Mon Mar 30 00:54:07 2015 +0200 @@ -30,15 +30,12 @@ import java.nio.channels.*; import java.util.*; import java.util.Map.Entry; -import java.util.function.*; - import com.oracle.graal.api.meta.*; import com.oracle.graal.compiler.common.cfg.*; 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.graph.*; import com.oracle.graal.phases.schedule.*; public class BinaryGraphPrinter implements GraphPrinter { @@ -143,7 +140,7 @@ BlockMap<List<Node>> blockToNodes = schedule == null ? null : schedule.getBlockToNodesMap(); NodeMap<Block> nodeToBlocks = schedule == null ? null : schedule.getNodeToBlockMap(); List<Block> blocks = cfg == null ? null : cfg.getBlocks(); - writeNodes(graph, nodeToBlocks); + writeNodes(graph, nodeToBlocks, cfg); writeBlocks(blocks, blockToNodes); } @@ -400,14 +397,7 @@ return node.getId(); } - private void writeNodes(Graph graph, NodeMap<Block> nodeToBlocks) throws IOException { - ToDoubleFunction<FixedNode> probabilities = null; - if (PrintGraphProbabilities.getValue()) { - try { - probabilities = new FixedNodeProbabilityCache(); - } catch (Throwable t) { - } - } + private void writeNodes(Graph graph, NodeMap<Block> nodeToBlocks, ControlFlowGraph cfg) throws IOException { Map<Object, Object> props = new HashMap<>(); writeInt(graph.getNodeCount()); @@ -415,9 +405,9 @@ for (Node node : graph.getNodes()) { NodeClass<?> nodeClass = node.getNodeClass(); node.getDebugProperties(props); - if (probabilities != null && node instanceof FixedNode) { + if (cfg != null && PrintGraphProbabilities.getValue() && node instanceof FixedNode) { try { - props.put("probability", probabilities.applyAsDouble((FixedNode) node)); + props.put("probability", cfg.blockFor(node).probability()); } catch (Throwable t) { props.put("probability", t); }