1 /* 2 * Copyright (c) 2014, 2014, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 package org.graalvm.compiler.lir.constopt; 24 25 import java.util.ArrayDeque; 26 import java.util.ArrayList; 27 import java.util.BitSet; 28 import java.util.Deque; 29 import java.util.HashSet; 30 import java.util.List; 31 32 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 33 import org.graalvm.compiler.debug.Debug; 34 import org.graalvm.compiler.debug.Debug.Scope; 35 import org.graalvm.compiler.debug.Indent; 36 import org.graalvm.compiler.lir.constopt.ConstantTree.Flags; 37 import org.graalvm.compiler.lir.constopt.ConstantTree.NodeCost; 38 39 /** 40 * Analyzes a {@link ConstantTree} and marks potential materialization positions. 41 */ 42 public final class ConstantTreeAnalyzer { 43 private final ConstantTree tree; 44 private final BitSet visited; 45 46 @SuppressWarnings("try") 47 public static NodeCost analyze(ConstantTree tree, AbstractBlockBase<?> startBlock) { 48 try (Scope s = Debug.scope("ConstantTreeAnalyzer")) { 49 ConstantTreeAnalyzer analyzer = new ConstantTreeAnalyzer(tree); 50 analyzer.analyzeBlocks(startBlock); 51 return tree.getCost(startBlock); 52 } catch (Throwable e) { 53 throw Debug.handle(e); 54 } 55 } 56 57 private ConstantTreeAnalyzer(ConstantTree tree) { 58 this.tree = tree; 59 this.visited = new BitSet(tree.size()); 60 } 61 62 /** 63 * Queues all relevant blocks for {@linkplain #process processing}. 64 * 65 * This is a worklist-style algorithm because a (more elegant) recursive implementation may 66 * cause {@linkplain StackOverflowError stack overflows} on larger graphs. 67 * 68 * @param startBlock The start block of the dominator subtree. 69 */ 70 @SuppressWarnings("try") 71 private void analyzeBlocks(AbstractBlockBase<?> startBlock) { 72 Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(); 73 worklist.offerLast(startBlock); 74 while (!worklist.isEmpty()) { 75 AbstractBlockBase<?> block = worklist.pollLast(); 76 try (Indent i = Debug.logAndIndent(Debug.VERBOSE_LOG_LEVEL, "analyze: %s", block)) { 77 assert block != null : "worklist is empty!"; 78 assert isMarked(block) : "Block not part of the dominator tree: " + block; 79 80 if (isLeafBlock(block)) { 81 Debug.log(Debug.VERBOSE_LOG_LEVEL, "leaf block"); 82 leafCost(block); 83 continue; 84 } 85 86 if (!visited.get(block.getId())) { 87 // if not yet visited (and not a leaf block) process all children first! 88 Debug.log(Debug.VERBOSE_LOG_LEVEL, "not marked"); 89 worklist.offerLast(block); 90 List<? extends AbstractBlockBase<?>> children = block.getDominated(); 91 children.forEach(child -> filteredPush(worklist, child)); 92 visited.set(block.getId()); 93 } else { 94 Debug.log(Debug.VERBOSE_LOG_LEVEL, "marked"); 95 // otherwise, process block 96 process(block); 97 } 98 } 99 } 100 } 101 102 /** 103 * Calculates the cost of a {@code block}. It is assumed that all {@code children} have already 104 * been {@linkplain #process processed} 105 * 106 * @param block The block to be processed. 107 */ 108 private void process(AbstractBlockBase<?> block) { 109 List<UseEntry> usages = new ArrayList<>(); 110 double bestCost = 0; 111 int numMat = 0; 112 List<? extends AbstractBlockBase<?>> children = block.getDominated(); 113 assert children.stream().anyMatch(this::isMarked) : "no children? should have called leafCost(): " + block; 114 115 // collect children costs 116 for (AbstractBlockBase<?> child : children) { 117 if (isMarked(child)) { 118 NodeCost childCost = tree.getCost(child); 119 assert childCost != null : "Child with null cost? block: " + child; 120 usages.addAll(childCost.getUsages()); 121 numMat += childCost.getNumMaterializations(); 122 bestCost += childCost.getBestCost(); 123 } 124 } 125 assert numMat > 0 : "No materialization? " + numMat; 126 127 // choose block 128 List<UseEntry> usagesBlock = tree.getUsages(block); 129 double probabilityBlock = block.probability(); 130 131 if (!usagesBlock.isEmpty() || shouldMaterializerInCurrentBlock(probabilityBlock, bestCost, numMat)) { 132 // mark current block as potential materialization position 133 usages.addAll(usagesBlock); 134 bestCost = probabilityBlock; 135 numMat = 1; 136 tree.set(Flags.CANDIDATE, block); 137 } else { 138 // stick with the current solution 139 } 140 141 assert (new HashSet<>(usages)).size() == usages.size() : "doulbe entries? " + usages; 142 NodeCost nodeCost = new NodeCost(bestCost, usages, numMat); 143 tree.setCost(block, nodeCost); 144 } 145 146 /** 147 * This is the cost function that decides whether a materialization should be inserted in the 148 * current block. 149 * <p> 150 * Note that this function does not take into account if a materialization is required despite 151 * the probabilities (e.g. there are usages in the current block). 152 * 153 * @param probabilityBlock Probability of the current block. 154 * @param probabilityChildren Accumulated probability of the children. 155 * @param numMat Number of materializations along the subtrees. We use {@code numMat - 1} to 156 * insert materializations as late as possible if the probabilities are the same. 157 */ 158 private static boolean shouldMaterializerInCurrentBlock(double probabilityBlock, double probabilityChildren, int numMat) { 159 return probabilityBlock * Math.pow(0.9, numMat - 1) < probabilityChildren; 160 } 161 162 private void filteredPush(Deque<AbstractBlockBase<?>> worklist, AbstractBlockBase<?> block) { 163 if (isMarked(block)) { 164 Debug.log(Debug.VERBOSE_LOG_LEVEL, "adding %s to the worklist", block); 165 worklist.offerLast(block); 166 } 167 } 168 169 private void leafCost(AbstractBlockBase<?> block) { 170 tree.set(Flags.CANDIDATE, block); 171 tree.getOrInitCost(block); 172 } 173 174 private boolean isMarked(AbstractBlockBase<?> block) { 175 return tree.isMarked(block); 176 } 177 178 private boolean isLeafBlock(AbstractBlockBase<?> block) { 179 return tree.isLeafBlock(block); 180 } 181 182 }