# HG changeset patch # User Miguel Garcia # Date 1400163138 -7200 # Node ID ce1444862ec2f224420e35d111bcec7984342480 # Parent 26cedd987c836c6e693010cbc741b14f98580f71 [inlining] moved ComputeInliningRelevance closer to its single user diff -r 26cedd987c83 -r ce1444862ec2 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/ComputeInliningRelevance.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/ComputeInliningRelevance.java Thu May 15 15:45:29 2014 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,324 +0,0 @@ -/* - * 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.common.inlining; - -import static com.oracle.graal.graph.util.CollectionsAccess.*; - -import java.util.*; -import java.util.function.*; - -import com.oracle.graal.graph.*; -import com.oracle.graal.nodes.*; - -import edu.umd.cs.findbugs.annotations.*; - -public class ComputeInliningRelevance { - - private static final double EPSILON = 1d / Integer.MAX_VALUE; - private static final double UNINITIALIZED = -1D; - - private static final int EXPECTED_MIN_INVOKE_COUNT = 3; - private static final int EXPECTED_INVOKE_RATIO = 20; - private static final int EXPECTED_LOOP_COUNT = 3; - - private final StructuredGraph graph; - private final ToDoubleFunction nodeProbabilities; - - /** - * Node relevances are pre-computed for all invokes if the graph contains loops. If there are no - * loops, the computation happens lazily based on {@link #rootScope}. - */ - private Map nodeRelevances; - /** - * This scope is non-null if (and only if) there are no loops in the graph. In this case, the - * root scope is used to compute invoke relevances on the fly. - */ - private Scope rootScope; - - public ComputeInliningRelevance(StructuredGraph graph, ToDoubleFunction nodeProbabilities) { - this.graph = graph; - this.nodeProbabilities = nodeProbabilities; - } - - /** - * Initializes or updates the relevance computation. If there are no loops within the graph, - * most computation happens lazily. - */ - public void compute() { - rootScope = null; - if (!graph.hasLoops()) { - // fast path for the frequent case of no loops - rootScope = new Scope(graph.start(), null); - } else { - if (nodeRelevances == null) { - nodeRelevances = newNodeIdentityMap(EXPECTED_MIN_INVOKE_COUNT + graph.getNodeCount() / EXPECTED_INVOKE_RATIO); - } - NodeWorkList workList = graph.createNodeWorkList(); - Map loops = newNodeIdentityMap(EXPECTED_LOOP_COUNT); - - loops.put(null, new Scope(graph.start(), null)); - for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.class)) { - createLoopScope(loopBegin, loops); - } - - for (Scope scope : loops.values()) { - scope.process(workList); - } - } - } - - public double getRelevance(Invoke invoke) { - if (rootScope != null) { - return rootScope.computeInvokeRelevance(invoke); - } - assert nodeRelevances != null : "uninitialized relevance"; - return nodeRelevances.get(invoke); - } - - /** - * Determines the parent of the given loop and creates a {@link Scope} object for each one. This - * method will call itself recursively if no {@link Scope} for the parent loop exists. - */ - private Scope createLoopScope(LoopBeginNode loopBegin, Map loops) { - Scope scope = loops.get(loopBegin); - if (scope == null) { - final Scope parent; - // look for the parent scope - FixedNode current = loopBegin.forwardEnd(); - while (true) { - if (current.predecessor() == null) { - if (current instanceof LoopBeginNode) { - // if we reach a LoopBeginNode then we're within this loop - parent = createLoopScope((LoopBeginNode) current, loops); - break; - } else if (current instanceof StartNode) { - // we're within the outermost scope - parent = loops.get(null); - break; - } else { - assert current.getClass() == MergeNode.class : current; - // follow any path upwards - it doesn't matter which one - current = ((MergeNode) current).forwardEndAt(0); - } - } else if (current instanceof LoopExitNode) { - // if we reach a loop exit then we follow this loop and have the same parent - parent = createLoopScope(((LoopExitNode) current).loopBegin(), loops).parent; - break; - } else { - current = (FixedNode) current.predecessor(); - } - } - scope = new Scope(loopBegin, parent); - loops.put(loopBegin, scope); - } - return scope; - } - - /** - * A scope holds information for the contents of one loop or of the root of the method. It does - * not include child loops, i.e., the iteration in {@link #process(NodeWorkList)} explicitly - * excludes the nodes of child loops. - */ - private class Scope { - public final FixedNode start; - public final Scope parent; // can be null for the outermost scope - - /** - * The minimum probability along the most probable path in this scope. Computed lazily. - */ - private double fastPathMinProbability = UNINITIALIZED; - /** - * A measure of how important this scope is within its parent scope. Computed lazily. - */ - private double scopeRelevanceWithinParent = UNINITIALIZED; - - public Scope(FixedNode start, Scope parent) { - this.start = start; - this.parent = parent; - } - - @SuppressFBWarnings("FE_FLOATING_POINT_EQUALITY") - public double getFastPathMinProbability() { - if (fastPathMinProbability == UNINITIALIZED) { - fastPathMinProbability = Math.max(EPSILON, computeFastPathMinProbability(start)); - } - return fastPathMinProbability; - } - - /** - * Computes the ratio between the probabilities of the current scope's entry point and the - * parent scope's fastPathMinProbability. - */ - @SuppressFBWarnings("FE_FLOATING_POINT_EQUALITY") - public double getScopeRelevanceWithinParent() { - if (scopeRelevanceWithinParent == UNINITIALIZED) { - if (start instanceof LoopBeginNode) { - assert parent != null; - double scopeEntryProbability = nodeProbabilities.applyAsDouble(((LoopBeginNode) start).forwardEnd()); - - scopeRelevanceWithinParent = scopeEntryProbability / parent.getFastPathMinProbability(); - } else { - scopeRelevanceWithinParent = 1D; - } - } - return scopeRelevanceWithinParent; - } - - /** - * Processes all invokes in this scope by starting at the scope's start node and iterating - * all fixed nodes. Child loops are skipped by going from loop entries directly to the loop - * exits. Processing stops at loop exits of the current loop. - */ - public void process(NodeWorkList workList) { - assert !(start instanceof Invoke); - workList.addAll(start.successors()); - - for (Node current : workList) { - assert current.isAlive(); - - if (current instanceof Invoke) { - // process the invoke and queue its successors - nodeRelevances.put((FixedNode) current, computeInvokeRelevance((Invoke) current)); - workList.addAll(current.successors()); - } else if (current instanceof LoopBeginNode) { - // skip child loops by advancing over the loop exits - ((LoopBeginNode) current).loopExits().forEach(exit -> workList.add(exit.next())); - } else if (current instanceof LoopEndNode) { - // nothing to do - } else if (current instanceof LoopExitNode) { - // nothing to do - } else if (current instanceof FixedWithNextNode) { - workList.add(((FixedWithNextNode) current).next()); - } else if (current instanceof EndNode) { - workList.add(((EndNode) current).merge()); - } else if (current instanceof ControlSinkNode) { - // nothing to do - } else if (current instanceof ControlSplitNode) { - workList.addAll(current.successors()); - } else { - assert false : current; - } - } - } - - /** - * The relevance of an invoke is the ratio between the invoke's probability and the current - * scope's fastPathMinProbability, adjusted by scopeRelevanceWithinParent. - */ - public double computeInvokeRelevance(Invoke invoke) { - double invokeProbability = nodeProbabilities.applyAsDouble(invoke.asNode()); - assert !Double.isNaN(invokeProbability); - - double relevance = (invokeProbability / getFastPathMinProbability()) * Math.min(1.0, getScopeRelevanceWithinParent()); - assert !Double.isNaN(relevance) : invoke + ": " + relevance + " / " + invokeProbability + " / " + getFastPathMinProbability() + " / " + getScopeRelevanceWithinParent(); - return relevance; - } - } - - /** - * Computes the minimum probability along the most probable path within the scope. During - * iteration, the method returns immediately once a loop exit is discovered. - */ - private double computeFastPathMinProbability(FixedNode scopeStart) { - ArrayList pathBeginNodes = new ArrayList<>(); - pathBeginNodes.add(scopeStart); - double minPathProbability = nodeProbabilities.applyAsDouble(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) { - return current == null ? minPathProbability : Math.min(minPathProbability, nodeProbabilities.applyAsDouble(current)); - } - - /** - * Returns the most probable successor. If multiple successors share the maximum probability, - * one is returned and the others are enqueued in pathBeginNodes. - */ - private static Node getMaxProbabilitySux(ControlSplitNode controlSplit, ArrayList 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; - } - - /** - * Returns the most probable loop exit. If multiple successors share the maximum probability, - * one is returned and the others are enqueued in pathBeginNodes. - */ - private Node getMaxProbabilityLoopExit(LoopBeginNode loopBegin, ArrayList pathBeginNodes) { - Node maxSux = null; - double maxProbability = 0.0; - int pathBeginCount = pathBeginNodes.size(); - - for (LoopExitNode sux : loopBegin.loopExits()) { - double probability = nodeProbabilities.applyAsDouble(sux); - if (probability > maxProbability) { - maxProbability = probability; - maxSux = sux; - truncate(pathBeginNodes, pathBeginCount); - } else if (probability == maxProbability) { - pathBeginNodes.add(sux); - } - } - - return maxSux; - } - - private static void truncate(ArrayList pathBeginNodes, int pathBeginCount) { - for (int i = pathBeginNodes.size() - pathBeginCount; i > 0; i--) { - pathBeginNodes.remove(pathBeginNodes.size() - 1); - } - } -} diff -r 26cedd987c83 -r ce1444862ec2 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/CallsiteHolder.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/CallsiteHolder.java Thu May 15 15:45:29 2014 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/CallsiteHolder.java Thu May 15 16:12:18 2014 +0200 @@ -27,8 +27,6 @@ import com.oracle.graal.nodes.FixedNode; import com.oracle.graal.nodes.Invoke; import com.oracle.graal.nodes.StructuredGraph; -import com.oracle.graal.phases.common.inlining.ComputeInliningRelevance; -import com.oracle.graal.phases.common.inlining.walker.InliningIterator; import com.oracle.graal.phases.graph.FixedNodeProbabilityCache; import java.util.Iterator; diff -r 26cedd987c83 -r ce1444862ec2 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/ComputeInliningRelevance.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/ComputeInliningRelevance.java Thu May 15 16:12:18 2014 +0200 @@ -0,0 +1,324 @@ +/* + * 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.common.inlining.walker; + +import static com.oracle.graal.graph.util.CollectionsAccess.*; + +import java.util.*; +import java.util.function.*; + +import com.oracle.graal.graph.*; +import com.oracle.graal.nodes.*; + +import edu.umd.cs.findbugs.annotations.*; + +public class ComputeInliningRelevance { + + private static final double EPSILON = 1d / Integer.MAX_VALUE; + private static final double UNINITIALIZED = -1D; + + private static final int EXPECTED_MIN_INVOKE_COUNT = 3; + private static final int EXPECTED_INVOKE_RATIO = 20; + private static final int EXPECTED_LOOP_COUNT = 3; + + private final StructuredGraph graph; + private final ToDoubleFunction nodeProbabilities; + + /** + * Node relevances are pre-computed for all invokes if the graph contains loops. If there are no + * loops, the computation happens lazily based on {@link #rootScope}. + */ + private Map nodeRelevances; + /** + * This scope is non-null if (and only if) there are no loops in the graph. In this case, the + * root scope is used to compute invoke relevances on the fly. + */ + private Scope rootScope; + + public ComputeInliningRelevance(StructuredGraph graph, ToDoubleFunction nodeProbabilities) { + this.graph = graph; + this.nodeProbabilities = nodeProbabilities; + } + + /** + * Initializes or updates the relevance computation. If there are no loops within the graph, + * most computation happens lazily. + */ + public void compute() { + rootScope = null; + if (!graph.hasLoops()) { + // fast path for the frequent case of no loops + rootScope = new Scope(graph.start(), null); + } else { + if (nodeRelevances == null) { + nodeRelevances = newNodeIdentityMap(EXPECTED_MIN_INVOKE_COUNT + graph.getNodeCount() / EXPECTED_INVOKE_RATIO); + } + NodeWorkList workList = graph.createNodeWorkList(); + Map loops = newNodeIdentityMap(EXPECTED_LOOP_COUNT); + + loops.put(null, new Scope(graph.start(), null)); + for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.class)) { + createLoopScope(loopBegin, loops); + } + + for (Scope scope : loops.values()) { + scope.process(workList); + } + } + } + + public double getRelevance(Invoke invoke) { + if (rootScope != null) { + return rootScope.computeInvokeRelevance(invoke); + } + assert nodeRelevances != null : "uninitialized relevance"; + return nodeRelevances.get(invoke); + } + + /** + * Determines the parent of the given loop and creates a {@link Scope} object for each one. This + * method will call itself recursively if no {@link Scope} for the parent loop exists. + */ + private Scope createLoopScope(LoopBeginNode loopBegin, Map loops) { + Scope scope = loops.get(loopBegin); + if (scope == null) { + final Scope parent; + // look for the parent scope + FixedNode current = loopBegin.forwardEnd(); + while (true) { + if (current.predecessor() == null) { + if (current instanceof LoopBeginNode) { + // if we reach a LoopBeginNode then we're within this loop + parent = createLoopScope((LoopBeginNode) current, loops); + break; + } else if (current instanceof StartNode) { + // we're within the outermost scope + parent = loops.get(null); + break; + } else { + assert current.getClass() == MergeNode.class : current; + // follow any path upwards - it doesn't matter which one + current = ((MergeNode) current).forwardEndAt(0); + } + } else if (current instanceof LoopExitNode) { + // if we reach a loop exit then we follow this loop and have the same parent + parent = createLoopScope(((LoopExitNode) current).loopBegin(), loops).parent; + break; + } else { + current = (FixedNode) current.predecessor(); + } + } + scope = new Scope(loopBegin, parent); + loops.put(loopBegin, scope); + } + return scope; + } + + /** + * A scope holds information for the contents of one loop or of the root of the method. It does + * not include child loops, i.e., the iteration in {@link #process(NodeWorkList)} explicitly + * excludes the nodes of child loops. + */ + private class Scope { + public final FixedNode start; + public final Scope parent; // can be null for the outermost scope + + /** + * The minimum probability along the most probable path in this scope. Computed lazily. + */ + private double fastPathMinProbability = UNINITIALIZED; + /** + * A measure of how important this scope is within its parent scope. Computed lazily. + */ + private double scopeRelevanceWithinParent = UNINITIALIZED; + + public Scope(FixedNode start, Scope parent) { + this.start = start; + this.parent = parent; + } + + @SuppressFBWarnings("FE_FLOATING_POINT_EQUALITY") + public double getFastPathMinProbability() { + if (fastPathMinProbability == UNINITIALIZED) { + fastPathMinProbability = Math.max(EPSILON, computeFastPathMinProbability(start)); + } + return fastPathMinProbability; + } + + /** + * Computes the ratio between the probabilities of the current scope's entry point and the + * parent scope's fastPathMinProbability. + */ + @SuppressFBWarnings("FE_FLOATING_POINT_EQUALITY") + public double getScopeRelevanceWithinParent() { + if (scopeRelevanceWithinParent == UNINITIALIZED) { + if (start instanceof LoopBeginNode) { + assert parent != null; + double scopeEntryProbability = nodeProbabilities.applyAsDouble(((LoopBeginNode) start).forwardEnd()); + + scopeRelevanceWithinParent = scopeEntryProbability / parent.getFastPathMinProbability(); + } else { + scopeRelevanceWithinParent = 1D; + } + } + return scopeRelevanceWithinParent; + } + + /** + * Processes all invokes in this scope by starting at the scope's start node and iterating + * all fixed nodes. Child loops are skipped by going from loop entries directly to the loop + * exits. Processing stops at loop exits of the current loop. + */ + public void process(NodeWorkList workList) { + assert !(start instanceof Invoke); + workList.addAll(start.successors()); + + for (Node current : workList) { + assert current.isAlive(); + + if (current instanceof Invoke) { + // process the invoke and queue its successors + nodeRelevances.put((FixedNode) current, computeInvokeRelevance((Invoke) current)); + workList.addAll(current.successors()); + } else if (current instanceof LoopBeginNode) { + // skip child loops by advancing over the loop exits + ((LoopBeginNode) current).loopExits().forEach(exit -> workList.add(exit.next())); + } else if (current instanceof LoopEndNode) { + // nothing to do + } else if (current instanceof LoopExitNode) { + // nothing to do + } else if (current instanceof FixedWithNextNode) { + workList.add(((FixedWithNextNode) current).next()); + } else if (current instanceof EndNode) { + workList.add(((EndNode) current).merge()); + } else if (current instanceof ControlSinkNode) { + // nothing to do + } else if (current instanceof ControlSplitNode) { + workList.addAll(current.successors()); + } else { + assert false : current; + } + } + } + + /** + * The relevance of an invoke is the ratio between the invoke's probability and the current + * scope's fastPathMinProbability, adjusted by scopeRelevanceWithinParent. + */ + public double computeInvokeRelevance(Invoke invoke) { + double invokeProbability = nodeProbabilities.applyAsDouble(invoke.asNode()); + assert !Double.isNaN(invokeProbability); + + double relevance = (invokeProbability / getFastPathMinProbability()) * Math.min(1.0, getScopeRelevanceWithinParent()); + assert !Double.isNaN(relevance) : invoke + ": " + relevance + " / " + invokeProbability + " / " + getFastPathMinProbability() + " / " + getScopeRelevanceWithinParent(); + return relevance; + } + } + + /** + * Computes the minimum probability along the most probable path within the scope. During + * iteration, the method returns immediately once a loop exit is discovered. + */ + private double computeFastPathMinProbability(FixedNode scopeStart) { + ArrayList pathBeginNodes = new ArrayList<>(); + pathBeginNodes.add(scopeStart); + double minPathProbability = nodeProbabilities.applyAsDouble(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) { + return current == null ? minPathProbability : Math.min(minPathProbability, nodeProbabilities.applyAsDouble(current)); + } + + /** + * Returns the most probable successor. If multiple successors share the maximum probability, + * one is returned and the others are enqueued in pathBeginNodes. + */ + private static Node getMaxProbabilitySux(ControlSplitNode controlSplit, ArrayList 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; + } + + /** + * Returns the most probable loop exit. If multiple successors share the maximum probability, + * one is returned and the others are enqueued in pathBeginNodes. + */ + private Node getMaxProbabilityLoopExit(LoopBeginNode loopBegin, ArrayList pathBeginNodes) { + Node maxSux = null; + double maxProbability = 0.0; + int pathBeginCount = pathBeginNodes.size(); + + for (LoopExitNode sux : loopBegin.loopExits()) { + double probability = nodeProbabilities.applyAsDouble(sux); + if (probability > maxProbability) { + maxProbability = probability; + maxSux = sux; + truncate(pathBeginNodes, pathBeginCount); + } else if (probability == maxProbability) { + pathBeginNodes.add(sux); + } + } + + return maxSux; + } + + private static void truncate(ArrayList pathBeginNodes, int pathBeginCount) { + for (int i = pathBeginNodes.size() - pathBeginCount; i > 0; i--) { + pathBeginNodes.remove(pathBeginNodes.size() - 1); + } + } +}