| /* |
| * Copyright (c) 2014, 2014, 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 org.graalvm.compiler.lir.constopt; |
| |
| import java.util.ArrayDeque; |
| import java.util.ArrayList; |
| import java.util.BitSet; |
| import java.util.Deque; |
| import java.util.HashSet; |
| import java.util.List; |
| |
| import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; |
| import org.graalvm.compiler.debug.Debug; |
| import org.graalvm.compiler.debug.Debug.Scope; |
| import org.graalvm.compiler.debug.Indent; |
| import org.graalvm.compiler.lir.constopt.ConstantTree.Flags; |
| import org.graalvm.compiler.lir.constopt.ConstantTree.NodeCost; |
| |
| /** |
| * Analyzes a {@link ConstantTree} and marks potential materialization positions. |
| */ |
| public final class ConstantTreeAnalyzer { |
| private final ConstantTree tree; |
| private final BitSet visited; |
| |
| @SuppressWarnings("try") |
| public static NodeCost analyze(ConstantTree tree, AbstractBlockBase<?> startBlock) { |
| try (Scope s = Debug.scope("ConstantTreeAnalyzer")) { |
| ConstantTreeAnalyzer analyzer = new ConstantTreeAnalyzer(tree); |
| analyzer.analyzeBlocks(startBlock); |
| return tree.getCost(startBlock); |
| } catch (Throwable e) { |
| throw Debug.handle(e); |
| } |
| } |
| |
| private ConstantTreeAnalyzer(ConstantTree tree) { |
| this.tree = tree; |
| this.visited = new BitSet(tree.size()); |
| } |
| |
| /** |
| * Queues all relevant blocks for {@linkplain #process processing}. |
| * |
| * This is a worklist-style algorithm because a (more elegant) recursive implementation may |
| * cause {@linkplain StackOverflowError stack overflows} on larger graphs. |
| * |
| * @param startBlock The start block of the dominator subtree. |
| */ |
| @SuppressWarnings("try") |
| private void analyzeBlocks(AbstractBlockBase<?> startBlock) { |
| Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(); |
| worklist.offerLast(startBlock); |
| while (!worklist.isEmpty()) { |
| AbstractBlockBase<?> block = worklist.pollLast(); |
| try (Indent i = Debug.logAndIndent(Debug.VERBOSE_LOG_LEVEL, "analyze: %s", block)) { |
| assert block != null : "worklist is empty!"; |
| assert isMarked(block) : "Block not part of the dominator tree: " + block; |
| |
| if (isLeafBlock(block)) { |
| Debug.log(Debug.VERBOSE_LOG_LEVEL, "leaf block"); |
| leafCost(block); |
| continue; |
| } |
| |
| if (!visited.get(block.getId())) { |
| // if not yet visited (and not a leaf block) process all children first! |
| Debug.log(Debug.VERBOSE_LOG_LEVEL, "not marked"); |
| worklist.offerLast(block); |
| List<? extends AbstractBlockBase<?>> children = block.getDominated(); |
| children.forEach(child -> filteredPush(worklist, child)); |
| visited.set(block.getId()); |
| } else { |
| Debug.log(Debug.VERBOSE_LOG_LEVEL, "marked"); |
| // otherwise, process block |
| process(block); |
| } |
| } |
| } |
| } |
| |
| /** |
| * Calculates the cost of a {@code block}. It is assumed that all {@code children} have already |
| * been {@linkplain #process processed} |
| * |
| * @param block The block to be processed. |
| */ |
| private void process(AbstractBlockBase<?> block) { |
| List<UseEntry> usages = new ArrayList<>(); |
| double bestCost = 0; |
| int numMat = 0; |
| List<? extends AbstractBlockBase<?>> children = block.getDominated(); |
| assert children.stream().anyMatch(this::isMarked) : "no children? should have called leafCost(): " + block; |
| |
| // collect children costs |
| for (AbstractBlockBase<?> child : children) { |
| if (isMarked(child)) { |
| NodeCost childCost = tree.getCost(child); |
| assert childCost != null : "Child with null cost? block: " + child; |
| usages.addAll(childCost.getUsages()); |
| numMat += childCost.getNumMaterializations(); |
| bestCost += childCost.getBestCost(); |
| } |
| } |
| assert numMat > 0 : "No materialization? " + numMat; |
| |
| // choose block |
| List<UseEntry> usagesBlock = tree.getUsages(block); |
| double probabilityBlock = block.probability(); |
| |
| if (!usagesBlock.isEmpty() || shouldMaterializerInCurrentBlock(probabilityBlock, bestCost, numMat)) { |
| // mark current block as potential materialization position |
| usages.addAll(usagesBlock); |
| bestCost = probabilityBlock; |
| numMat = 1; |
| tree.set(Flags.CANDIDATE, block); |
| } else { |
| // stick with the current solution |
| } |
| |
| assert (new HashSet<>(usages)).size() == usages.size() : "doulbe entries? " + usages; |
| NodeCost nodeCost = new NodeCost(bestCost, usages, numMat); |
| tree.setCost(block, nodeCost); |
| } |
| |
| /** |
| * This is the cost function that decides whether a materialization should be inserted in the |
| * current block. |
| * <p> |
| * Note that this function does not take into account if a materialization is required despite |
| * the probabilities (e.g. there are usages in the current block). |
| * |
| * @param probabilityBlock Probability of the current block. |
| * @param probabilityChildren Accumulated probability of the children. |
| * @param numMat Number of materializations along the subtrees. We use {@code numMat - 1} to |
| * insert materializations as late as possible if the probabilities are the same. |
| */ |
| private static boolean shouldMaterializerInCurrentBlock(double probabilityBlock, double probabilityChildren, int numMat) { |
| return probabilityBlock * Math.pow(0.9, numMat - 1) < probabilityChildren; |
| } |
| |
| private void filteredPush(Deque<AbstractBlockBase<?>> worklist, AbstractBlockBase<?> block) { |
| if (isMarked(block)) { |
| Debug.log(Debug.VERBOSE_LOG_LEVEL, "adding %s to the worklist", block); |
| worklist.offerLast(block); |
| } |
| } |
| |
| private void leafCost(AbstractBlockBase<?> block) { |
| tree.set(Flags.CANDIDATE, block); |
| tree.getOrInitCost(block); |
| } |
| |
| private boolean isMarked(AbstractBlockBase<?> block) { |
| return tree.isMarked(block); |
| } |
| |
| private boolean isLeafBlock(AbstractBlockBase<?> block) { |
| return tree.isLeafBlock(block); |
| } |
| |
| } |