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.DebugContext; 33 import org.graalvm.compiler.debug.Indent; 34 import org.graalvm.compiler.lir.constopt.ConstantTree.Flags; 35 import org.graalvm.compiler.lir.constopt.ConstantTree.NodeCost; 36 37 /** 38 * Analyzes a {@link ConstantTree} and marks potential materialization positions. 39 */ 40 public final class ConstantTreeAnalyzer { 41 private final ConstantTree tree; 42 private final BitSet visited; 43 44 @SuppressWarnings("try") 45 public static NodeCost analyze(DebugContext debug, ConstantTree tree, AbstractBlockBase<?> startBlock) { 46 try (DebugContext.Scope s = debug.scope("ConstantTreeAnalyzer")) { 47 ConstantTreeAnalyzer analyzer = new ConstantTreeAnalyzer(tree); 48 analyzer.analyzeBlocks(debug, startBlock); 49 return tree.getCost(startBlock); 50 } catch (Throwable e) { 51 throw debug.handle(e); 52 } 53 } 54 55 private ConstantTreeAnalyzer(ConstantTree tree) { 56 this.tree = tree; 57 this.visited = new BitSet(tree.size()); 58 } 59 60 /** 61 * Queues all relevant blocks for {@linkplain #process processing}. 62 * 63 * This is a worklist-style algorithm because a (more elegant) recursive implementation may 64 * cause {@linkplain StackOverflowError stack overflows} on larger graphs. 65 * 66 * @param startBlock The start block of the dominator subtree. 67 */ 68 @SuppressWarnings("try") 69 private void analyzeBlocks(DebugContext debug, AbstractBlockBase<?> startBlock) { 70 Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(); 71 worklist.offerLast(startBlock); 72 while (!worklist.isEmpty()) { 73 AbstractBlockBase<?> block = worklist.pollLast(); 74 try (Indent i = debug.logAndIndent(DebugContext.VERBOSE_LEVEL, "analyze: %s", block)) { 75 assert block != null : "worklist is empty!"; 76 assert isMarked(block) : "Block not part of the dominator tree: " + block; 77 78 if (isLeafBlock(block)) { 79 debug.log(DebugContext.VERBOSE_LEVEL, "leaf block"); 80 leafCost(block); 81 continue; 82 } 83 84 if (!visited.get(block.getId())) { 85 // if not yet visited (and not a leaf block) process all children first! 86 debug.log(DebugContext.VERBOSE_LEVEL, "not marked"); 87 worklist.offerLast(block); 88 AbstractBlockBase<?> dominated = block.getFirstDominated(); 89 while (dominated != null) { 90 filteredPush(debug, worklist, dominated); 91 dominated = dominated.getDominatedSibling(); 92 } 93 visited.set(block.getId()); 94 } else { 95 debug.log(DebugContext.VERBOSE_LEVEL, "marked"); 96 // otherwise, process block 97 process(block); 98 } 99 } 100 } 101 } 102 103 /** 104 * Calculates the cost of a {@code block}. It is assumed that all {@code children} have already 105 * been {@linkplain #process processed} 106 * 107 * @param block The block to be processed. 108 */ 109 private void process(AbstractBlockBase<?> block) { 110 List<UseEntry> usages = new ArrayList<>(); 111 double bestCost = 0; 112 int numMat = 0; 113 114 // collect children costs 115 AbstractBlockBase<?> child = block.getFirstDominated(); 116 while (child != null) { 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 child = child.getDominatedSibling(); 125 } 126 assert numMat > 0 : "No materialization? " + numMat; 127 128 // choose block 129 List<UseEntry> usagesBlock = tree.getUsages(block); 130 double probabilityBlock = block.probability(); 131 132 if (!usagesBlock.isEmpty() || shouldMaterializerInCurrentBlock(probabilityBlock, bestCost, numMat)) { 133 // mark current block as potential materialization position 134 usages.addAll(usagesBlock); 135 bestCost = probabilityBlock; 136 numMat = 1; 137 tree.set(Flags.CANDIDATE, block); 138 } else { 139 // stick with the current solution 140 } 141 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(DebugContext debug, Deque<AbstractBlockBase<?>> worklist, AbstractBlockBase<?> block) { 163 if (isMarked(block)) { 164 debug.log(DebugContext.VERBOSE_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 }