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 */
23package org.graalvm.compiler.nodes.cfg;
24
25import java.util.ArrayList;
26import java.util.Iterator;
27
28import org.graalvm.compiler.core.common.LocationIdentity;
29import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
30import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
31import org.graalvm.compiler.core.common.cfg.Loop;
32import org.graalvm.compiler.graph.Node;
33import org.graalvm.compiler.nodes.AbstractBeginNode;
34import org.graalvm.compiler.nodes.FixedNode;
35import org.graalvm.compiler.nodes.FixedWithNextNode;
36import org.graalvm.compiler.nodes.InvokeWithExceptionNode;
37import org.graalvm.compiler.nodes.LoopBeginNode;
38import org.graalvm.compiler.nodes.LoopEndNode;
39import org.graalvm.compiler.nodes.memory.MemoryCheckpoint;
40
41public 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}
327