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();
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 }
|
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();
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 }
|