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 }