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.List; 30 31 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 32 import org.graalvm.compiler.debug.Debug; 33 import org.graalvm.compiler.debug.Debug.Scope; 34 import org.graalvm.compiler.debug.Indent; 35 import org.graalvm.compiler.lir.constopt.ConstantTree.Flags; 36 import org.graalvm.compiler.lir.constopt.ConstantTree.NodeCost; 37 38 /** 39 * Analyzes a {@link ConstantTree} and marks potential materialization positions. 40 */ 41 public final class ConstantTreeAnalyzer { 42 private final ConstantTree tree; 43 private final BitSet visited; 44 45 @SuppressWarnings("try") 46 public static NodeCost analyze(ConstantTree tree, AbstractBlockBase<?> startBlock) { 47 try (Scope s = Debug.scope("ConstantTreeAnalyzer")) { 48 ConstantTreeAnalyzer analyzer = new ConstantTreeAnalyzer(tree); 49 analyzer.analyzeBlocks(startBlock); 50 return tree.getCost(startBlock); 51 } catch (Throwable e) { 52 throw Debug.handle(e); 53 } 54 } 55 56 private ConstantTreeAnalyzer(ConstantTree tree) { 57 this.tree = tree; 58 this.visited = new BitSet(tree.size()); 59 } 60 61 /** 62 * Queues all relevant blocks for {@linkplain #process processing}. 63 * 64 * This is a worklist-style algorithm because a (more elegant) recursive implementation may 65 * cause {@linkplain StackOverflowError stack overflows} on larger graphs. 66 * 67 * @param startBlock The start block of the dominator subtree. 68 */ 69 @SuppressWarnings("try") 70 private void analyzeBlocks(AbstractBlockBase<?> startBlock) { 71 Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(); 72 worklist.offerLast(startBlock); 73 while (!worklist.isEmpty()) { 74 AbstractBlockBase<?> block = worklist.pollLast(); 75 try (Indent i = Debug.logAndIndent(Debug.VERBOSE_LEVEL, "analyze: %s", block)) { 76 assert block != null : "worklist is empty!"; 77 assert isMarked(block) : "Block not part of the dominator tree: " + block; 78 79 if (isLeafBlock(block)) { 80 Debug.log(Debug.VERBOSE_LEVEL, "leaf block"); 81 leafCost(block); 82 continue; 83 } 84 85 if (!visited.get(block.getId())) { 86 // if not yet visited (and not a leaf block) process all children first! 87 Debug.log(Debug.VERBOSE_LEVEL, "not marked"); 88 worklist.offerLast(block); 89 AbstractBlockBase<?> dominated = block.getFirstDominated(); 90 while (dominated != null) { 91 filteredPush(worklist, dominated); 92 dominated = dominated.getDominatedSibling(); 93 } 94 visited.set(block.getId()); 95 } else { 96 Debug.log(Debug.VERBOSE_LEVEL, "marked"); 97 // otherwise, process block 98 process(block); 99 } 100 } 101 } 102 } 103 104 /** 105 * Calculates the cost of a {@code block}. It is assumed that all {@code children} have already 106 * been {@linkplain #process processed} 107 * 108 * @param block The block to be processed. 109 */ 110 private void process(AbstractBlockBase<?> block) { 111 List<UseEntry> usages = new ArrayList<>(); 112 double bestCost = 0; 113 int numMat = 0; 114 115 // collect children costs 116 AbstractBlockBase<?> child = block.getFirstDominated(); 117 while (child != null) { 118 if (isMarked(child)) { 119 NodeCost childCost = tree.getCost(child); 120 assert childCost != null : "Child with null cost? block: " + child; 121 usages.addAll(childCost.getUsages()); 122 numMat += childCost.getNumMaterializations(); 123 bestCost += childCost.getBestCost(); 124 } 125 child = child.getDominatedSibling(); 126 } 127 assert numMat > 0 : "No materialization? " + numMat; 128 129 // choose block 130 List<UseEntry> usagesBlock = tree.getUsages(block); 131 double probabilityBlock = block.probability(); 132 133 if (!usagesBlock.isEmpty() || shouldMaterializerInCurrentBlock(probabilityBlock, bestCost, numMat)) { 134 // mark current block as potential materialization position 135 usages.addAll(usagesBlock); 136 bestCost = probabilityBlock; 137 numMat = 1; 138 tree.set(Flags.CANDIDATE, block); 139 } else { 140 // stick with the current solution 141 } 142 143 NodeCost nodeCost = new NodeCost(bestCost, usages, numMat); 144 tree.setCost(block, nodeCost); 145 } 146 147 /** 148 * This is the cost function that decides whether a materialization should be inserted in the 149 * current block. 150 * <p> 151 * Note that this function does not take into account if a materialization is required despite 152 * the probabilities (e.g. there are usages in the current block). 153 * 154 * @param probabilityBlock Probability of the current block. 155 * @param probabilityChildren Accumulated probability of the children. 156 * @param numMat Number of materializations along the subtrees. We use {@code numMat - 1} to 157 * insert materializations as late as possible if the probabilities are the same. 158 */ 159 private static boolean shouldMaterializerInCurrentBlock(double probabilityBlock, double probabilityChildren, int numMat) { 160 return probabilityBlock * Math.pow(0.9, numMat - 1) < probabilityChildren; 161 } 162 163 private void filteredPush(Deque<AbstractBlockBase<?>> worklist, AbstractBlockBase<?> block) { 164 if (isMarked(block)) { 165 Debug.log(Debug.VERBOSE_LEVEL, "adding %s to the worklist", block); 166 worklist.offerLast(block); 167 } 168 } 169 170 private void leafCost(AbstractBlockBase<?> block) { 171 tree.set(Flags.CANDIDATE, block); 172 tree.getOrInitCost(block); 173 } 174 175 private boolean isMarked(AbstractBlockBase<?> block) { 176 return tree.isMarked(block); 177 } 178 179 private boolean isLeafBlock(AbstractBlockBase<?> block) { 180 return tree.isLeafBlock(block); 181 } 182 183 }