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.ArrayList;
26 import java.util.Collections;
27 import java.util.List;
28 import java.util.function.BiConsumer;
29 import java.util.function.Predicate;
30
31 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
32 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
33 import org.graalvm.compiler.core.common.cfg.BlockMap;
34 import org.graalvm.compiler.core.common.cfg.PrintableDominatorOptimizationProblem;
35 import org.graalvm.compiler.core.common.cfg.PropertyConsumable;
36
37 /**
38 * Represents a dominator (sub-)tree for a constant definition.
39 */
40 public class ConstantTree extends PrintableDominatorOptimizationProblem<ConstantTree.Flags, ConstantTree.NodeCost> {
41
42 public enum Flags {
43 SUBTREE,
44 USAGE,
45 MATERIALIZE,
46 CANDIDATE,
47 }
48
49 /**
50 * Costs associated with a block.
51 */
52 public static class NodeCost implements PropertyConsumable {
53 private List<UseEntry> usages;
54 private double bestCost;
55 private int numMat;
56
57 public NodeCost(double bestCost, List<UseEntry> usages, int numMat) {
58 this.bestCost = bestCost;
59 this.usages = usages;
60 this.numMat = numMat;
61 }
62
63 @Override
64 public void forEachProperty(BiConsumer<String, String> action) {
65 action.accept("bestCost", Double.toString(getBestCost()));
66 action.accept("numMat", Integer.toString(getNumMaterializations()));
67 action.accept("numUsages", Integer.toString(usages.size()));
68 }
69
70 public void addUsage(UseEntry usage) {
71 if (usages == null) {
72 usages = new ArrayList<>();
73 }
74 usages.add(usage);
75 }
76
77 public List<UseEntry> getUsages() {
78 if (usages == null) {
79 Collections.emptyList();
80 }
81 return usages;
82 }
83
84 public double getBestCost() {
85 return bestCost;
86 }
87
88 public int getNumMaterializations() {
89 return numMat;
90 }
91
92 public void setBestCost(double cost) {
93 bestCost = cost;
94 }
95
96 @Override
97 public String toString() {
98 return "NodeCost [bestCost=" + bestCost + ", numUsages=" + usages.size() + ", numMat=" + numMat + "]";
99 }
100 }
101
102 private final BlockMap<List<UseEntry>> blockMap;
103
104 public ConstantTree(AbstractControlFlowGraph<?> cfg, DefUseTree tree) {
105 super(Flags.class, cfg);
106 this.blockMap = new BlockMap<>(cfg);
107 tree.forEach(u -> getOrInitList(u.getBlock()).add(u));
108 }
109
110 private List<UseEntry> getOrInitList(AbstractBlockBase<?> block) {
111 List<UseEntry> list = blockMap.get(block);
112 if (list == null) {
113 list = new ArrayList<>();
114 blockMap.put(block, list);
115 }
116 return list;
117 }
118
119 public List<UseEntry> getUsages(AbstractBlockBase<?> block) {
120 List<UseEntry> list = blockMap.get(block);
121 if (list == null) {
122 return Collections.emptyList();
123 }
124 return Collections.unmodifiableList(list);
125 }
126
127 /**
128 * Returns the cost object associated with {@code block}. If there is none, a new cost object is
129 * created.
130 */
131 NodeCost getOrInitCost(AbstractBlockBase<?> block) {
132 NodeCost cost = getCost(block);
133 if (cost == null) {
134 cost = new NodeCost(block.probability(), blockMap.get(block), 1);
135 setCost(block, cost);
136 }
137 return cost;
138 }
139
140 @Override
141 public String getName(Flags type) {
142 switch (type) {
143 case USAGE:
144 return "hasUsage";
145 case SUBTREE:
146 return "inSubtree";
147 case MATERIALIZE:
148 return "materialize";
149 case CANDIDATE:
150 return "candidate";
151 }
152 return super.getName(type);
153 }
154
155 @Override
156 public void forEachPropertyPair(AbstractBlockBase<?> block, BiConsumer<String, String> action) {
157 if (get(Flags.SUBTREE, block) && (block.getDominator() == null || !get(Flags.SUBTREE, block.getDominator()))) {
158 action.accept("hasDefinition", "true");
159 }
160 super.forEachPropertyPair(block, action);
161 }
162
163 public long subTreeSize() {
164 return stream(Flags.SUBTREE).count();
165 }
166
167 public AbstractBlockBase<?> getStartBlock() {
168 return stream(Flags.SUBTREE).findFirst().get();
169 }
170
171 public void markBlocks() {
172 for (AbstractBlockBase<?> block : getBlocks()) {
173 if (get(Flags.USAGE, block)) {
174 setDominatorPath(Flags.SUBTREE, block);
175 }
176 }
177 }
178
179 public boolean isMarked(AbstractBlockBase<?> block) {
180 return get(Flags.SUBTREE, block);
181 }
182
183 public boolean isLeafBlock(AbstractBlockBase<?> block) {
184 AbstractBlockBase<?> dom = block.getFirstDominated();
185 while (dom != null) {
186 if (isMarked(dom)) {
187 return false;
188 }
189 dom = dom.getDominatedSibling();
190 }
191 return true;
192 }
193
194 public void setSolution(AbstractBlockBase<?> block) {
195 set(Flags.MATERIALIZE, block);
196 }
197
198 public int size() {
199 return getBlocks().length;
200 }
201
202 public void traverseTreeWhileTrue(AbstractBlockBase<?> block, Predicate<AbstractBlockBase<?>> action) {
203 assert block != null : "block must not be null!";
204 if (action.test(block)) {
205 AbstractBlockBase<?> dom = block.getFirstDominated();
206 while (dom != null) {
207 if (this.isMarked(dom)) {
208 traverseTreeWhileTrue(dom, action);
209 }
210 dom = dom.getDominatedSibling();
211 }
212 }
213 }
214
215 }