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