1 /*
2 * Copyright (c) 2009, 2016, 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.nodes.cfg;
24
25 import java.util.ArrayList;
26 import java.util.Iterator;
27
28 import org.graalvm.compiler.core.common.LocationIdentity;
29 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
30 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
31 import org.graalvm.compiler.core.common.cfg.Loop;
32 import org.graalvm.compiler.graph.Node;
33 import org.graalvm.compiler.nodes.AbstractBeginNode;
34 import org.graalvm.compiler.nodes.FixedNode;
35 import org.graalvm.compiler.nodes.FixedWithNextNode;
36 import org.graalvm.compiler.nodes.InvokeWithExceptionNode;
37 import org.graalvm.compiler.nodes.LoopBeginNode;
38 import org.graalvm.compiler.nodes.LoopEndNode;
39 import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
40
41 public final class Block extends AbstractBlockBase<Block> {
42
43 public static final Block[] EMPTY_ARRAY = new Block[0];
44
45 protected final AbstractBeginNode beginNode;
46
47 protected FixedNode endNode;
48
49 protected double probability;
50 protected Loop<Block> loop;
51
52 protected Block postdominator;
53 protected Block distancedDominatorCache;
54 private LocationSet killLocations;
55 private LocationSet killLocationsBetweenThisAndDominator;
56
57 protected Block(AbstractBeginNode node) {
58 this.beginNode = node;
59 }
60
61 public AbstractBeginNode getBeginNode() {
62 return beginNode;
63 }
64
65 public FixedNode getEndNode() {
66 return endNode;
67 }
68
69 @Override
70 public Loop<Block> getLoop() {
71 return loop;
72 }
73
74 public void setLoop(Loop<Block> loop) {
75 this.loop = loop;
76 }
77
78 @Override
79 public int getLoopDepth() {
80 return loop == null ? 0 : loop.getDepth();
81 }
82
83 @Override
84 public boolean isLoopHeader() {
85 return getBeginNode() instanceof LoopBeginNode;
86 }
87
88 @Override
89 public boolean isLoopEnd() {
90 return getEndNode() instanceof LoopEndNode;
91 }
92
93 @Override
94 public boolean isExceptionEntry() {
95 Node predecessor = getBeginNode().predecessor();
96 return predecessor != null && predecessor instanceof InvokeWithExceptionNode && getBeginNode() == ((InvokeWithExceptionNode) predecessor).exceptionEdge();
97 }
98
99 public Block getFirstPredecessor() {
100 return getPredecessors()[0];
101 }
102
103 public Block getFirstSuccessor() {
104 return getSuccessors()[0];
105 }
106
107 public Block getEarliestPostDominated() {
108 Block b = this;
109 while (true) {
110 Block dom = b.getDominator();
111 if (dom != null && dom.getPostdominator() == b) {
112 b = dom;
113 } else {
114 break;
115 }
116 }
117 return b;
118 }
119
120 @Override
121 public Block getPostdominator() {
122 return postdominator;
123 }
124
125 private class NodeIterator implements Iterator<FixedNode> {
126
127 private FixedNode cur;
128
129 NodeIterator() {
130 cur = getBeginNode();
131 }
132
133 @Override
134 public boolean hasNext() {
135 return cur != null;
136 }
137
138 @Override
139 public FixedNode next() {
140 FixedNode result = cur;
141 if (result instanceof FixedWithNextNode) {
142 FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) result;
143 FixedNode next = fixedWithNextNode.next();
144 if (next instanceof AbstractBeginNode) {
145 next = null;
146 }
147 cur = next;
148 } else {
149 cur = null;
150 }
151 assert !(cur instanceof AbstractBeginNode);
152 return result;
153 }
154
155 @Override
156 public void remove() {
157 throw new UnsupportedOperationException();
158 }
159 }
160
161 public Iterable<FixedNode> getNodes() {
162 return new Iterable<FixedNode>() {
163
164 @Override
165 public Iterator<FixedNode> iterator() {
166 return new NodeIterator();
167 }
168
169 @Override
170 public String toString() {
171 StringBuilder str = new StringBuilder().append('[');
172 for (FixedNode node : this) {
173 str.append(node).append(", ");
174 }
175 if (str.length() > 1) {
176 str.setLength(str.length() - 2);
177 }
178 return str.append(']').toString();
179 }
180 };
181 }
182
183 @Override
184 public String toString() {
185 return "B" + id;
186 }
187
188 @Override
189 public double probability() {
190 return probability;
191 }
192
193 public void setProbability(double probability) {
194 assert probability >= 0 && Double.isFinite(probability);
195 this.probability = probability;
196 }
197
198 @Override
199 public Block getDominator(int distance) {
200 Block result = this;
201 for (int i = 0; i < distance; ++i) {
202 result = result.getDominator();
203 }
204 return result;
205 }
206
207 public boolean canKill(LocationIdentity location) {
208 if (location.isImmutable()) {
209 return false;
210 }
211 return getKillLocations().contains(location);
212 }
213
214 public LocationSet getKillLocations() {
215 if (killLocations == null) {
216 killLocations = calcKillLocations();
217 }
218 return killLocations;
219 }
220
221 private LocationSet calcKillLocations() {
222 LocationSet result = new LocationSet();
223 for (FixedNode node : this.getNodes()) {
224 if (node instanceof MemoryCheckpoint.Single) {
225 LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
226 result.add(identity);
227 } else if (node instanceof MemoryCheckpoint.Multi) {
228 for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
229 result.add(identity);
230 }
231 }
232 if (result.isAny()) {
233 break;
234 }
235 }
236 return result;
237 }
238
239 public boolean canKillBetweenThisAndDominator(LocationIdentity location) {
240 if (location.isImmutable()) {
241 return false;
242 }
243 return this.getKillLocationsBetweenThisAndDominator().contains(location);
244 }
245
246 private LocationSet getKillLocationsBetweenThisAndDominator() {
247 if (this.killLocationsBetweenThisAndDominator == null) {
248 LocationSet dominatorResult = new LocationSet();
249 Block stopBlock = getDominator();
250 if (this.isLoopHeader()) {
251 assert stopBlock.getLoopDepth() < this.getLoopDepth();
252 dominatorResult.addAll(((HIRLoop) this.getLoop()).getKillLocations());
253 } else {
254 for (Block b : this.getPredecessors()) {
255 assert !this.isLoopHeader();
256 if (b != stopBlock) {
257 dominatorResult.addAll(b.getKillLocations());
258 if (dominatorResult.isAny()) {
259 break;
260 }
261 b.calcKillLocationsBetweenThisAndTarget(dominatorResult, stopBlock);
262 if (dominatorResult.isAny()) {
263 break;
264 }
265 }
266 }
267 }
268 this.killLocationsBetweenThisAndDominator = dominatorResult;
269 }
270 return this.killLocationsBetweenThisAndDominator;
271 }
272
273 private void calcKillLocationsBetweenThisAndTarget(LocationSet result, Block stopBlock) {
274 assert AbstractControlFlowGraph.dominates(stopBlock, this);
275 if (stopBlock == this || result.isAny()) {
276 // We reached the stop block => nothing to do.
277 return;
278 } else {
279 if (stopBlock == this.getDominator()) {
280 result.addAll(this.getKillLocationsBetweenThisAndDominator());
281 } else {
282 // Divide and conquer: Aggregate kill locations from this to the dominator and then
283 // from the dominator onwards.
284 calcKillLocationsBetweenThisAndTarget(result, this.getDominator());
285 result.addAll(this.getDominator().getKillLocations());
286 if (result.isAny()) {
287 return;
288 }
289 this.getDominator().calcKillLocationsBetweenThisAndTarget(result, stopBlock);
290 }
291 }
292 }
293
294 @Override
295 public void delete() {
296
297 // adjust successor and predecessor lists
298 Block next = getSuccessors()[0];
299 for (Block pred : getPredecessors()) {
300 Block[] predSuccs = pred.successors;
301 Block[] newPredSuccs = new Block[predSuccs.length];
302 for (int i = 0; i < predSuccs.length; ++i) {
303 if (predSuccs[i] == this) {
304 newPredSuccs[i] = next;
305 } else {
306 newPredSuccs[i] = predSuccs[i];
307 }
308 }
309 pred.setSuccessors(newPredSuccs);
310 }
311
312 ArrayList<Block> newPreds = new ArrayList<>();
313 for (int i = 0; i < next.getPredecessorCount(); i++) {
314 Block curPred = next.getPredecessors()[i];
315 if (curPred == this) {
316 for (Block b : getPredecessors()) {
317 newPreds.add(b);
318 }
319 } else {
320 newPreds.add(curPred);
321 }
322 }
323
324 next.setPredecessors(newPreds.toArray(new Block[0]));
325 }
326 }