001/*
002 * Copyright (c) 2009, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.nodes.cfg;
024
025import java.util.*;
026
027import jdk.internal.jvmci.meta.*;
028
029import com.oracle.graal.compiler.common.cfg.*;
030import com.oracle.graal.graph.*;
031import com.oracle.graal.nodes.*;
032import com.oracle.graal.nodes.memory.*;
033
034public final class Block extends AbstractBlockBase<Block> {
035
036    protected final AbstractBeginNode beginNode;
037
038    protected FixedNode endNode;
039
040    protected double probability;
041    protected Loop<Block> loop;
042
043    protected Block postdominator;
044    protected Block distancedDominatorCache;
045    private LocationSet killLocations;
046    private LocationSet killLocationsBetweenThisAndDominator;
047
048    protected Block(AbstractBeginNode node) {
049        this.beginNode = node;
050    }
051
052    public AbstractBeginNode getBeginNode() {
053        return beginNode;
054    }
055
056    public FixedNode getEndNode() {
057        return endNode;
058    }
059
060    @Override
061    public Loop<Block> getLoop() {
062        return loop;
063    }
064
065    public void setLoop(Loop<Block> loop) {
066        this.loop = loop;
067    }
068
069    @Override
070    public int getLoopDepth() {
071        return loop == null ? 0 : loop.getDepth();
072    }
073
074    @Override
075    public boolean isLoopHeader() {
076        return getBeginNode() instanceof LoopBeginNode;
077    }
078
079    @Override
080    public boolean isLoopEnd() {
081        return getEndNode() instanceof LoopEndNode;
082    }
083
084    @Override
085    public boolean isExceptionEntry() {
086        Node predecessor = getBeginNode().predecessor();
087        return predecessor != null && predecessor instanceof InvokeWithExceptionNode && getBeginNode() == ((InvokeWithExceptionNode) predecessor).exceptionEdge();
088    }
089
090    public Block getFirstPredecessor() {
091        return getPredecessors().get(0);
092    }
093
094    public Block getFirstSuccessor() {
095        return getSuccessors().get(0);
096    }
097
098    public Block getEarliestPostDominated() {
099        Block b = this;
100        while (true) {
101            Block dom = b.getDominator();
102            if (dom != null && dom.getPostdominator() == b) {
103                b = dom;
104            } else {
105                break;
106            }
107        }
108        return b;
109    }
110
111    @Override
112    public Block getPostdominator() {
113        return postdominator;
114    }
115
116    private class NodeIterator implements Iterator<FixedNode> {
117
118        private FixedNode cur;
119
120        public NodeIterator() {
121            cur = getBeginNode();
122        }
123
124        @Override
125        public boolean hasNext() {
126            return cur != null;
127        }
128
129        @Override
130        public FixedNode next() {
131            FixedNode result = cur;
132            if (result instanceof FixedWithNextNode) {
133                FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) result;
134                FixedNode next = fixedWithNextNode.next();
135                if (next instanceof AbstractBeginNode) {
136                    next = null;
137                }
138                cur = next;
139            } else {
140                cur = null;
141            }
142            assert !(cur instanceof AbstractBeginNode);
143            return result;
144        }
145
146        @Override
147        public void remove() {
148            throw new UnsupportedOperationException();
149        }
150    }
151
152    public Iterable<FixedNode> getNodes() {
153        return new Iterable<FixedNode>() {
154
155            @Override
156            public Iterator<FixedNode> iterator() {
157                return new NodeIterator();
158            }
159
160            @Override
161            public String toString() {
162                StringBuilder str = new StringBuilder().append('[');
163                for (FixedNode node : this) {
164                    str.append(node).append(", ");
165                }
166                if (str.length() > 1) {
167                    str.setLength(str.length() - 2);
168                }
169                return str.append(']').toString();
170            }
171        };
172    }
173
174    @Override
175    public String toString() {
176        return "B" + id;
177    }
178
179    @Override
180    public double probability() {
181        return probability;
182    }
183
184    public void setProbability(double probability) {
185        assert probability >= 0 && Double.isFinite(probability);
186        this.probability = probability;
187    }
188
189    @Override
190    public Block getDominator(int distance) {
191        Block result = this;
192        for (int i = 0; i < distance; ++i) {
193            result = result.getDominator();
194        }
195        return result;
196    }
197
198    public boolean canKill(LocationIdentity location) {
199        if (location.isImmutable()) {
200            return false;
201        }
202        return getKillLocations().contains(location);
203    }
204
205    public LocationSet getKillLocations() {
206        if (killLocations == null) {
207            killLocations = calcKillLocations();
208        }
209        return killLocations;
210    }
211
212    private LocationSet calcKillLocations() {
213        LocationSet result = new LocationSet();
214        for (FixedNode node : this.getNodes()) {
215            if (node instanceof MemoryCheckpoint.Single) {
216                LocationIdentity identity = ((MemoryCheckpoint.Single) node).getLocationIdentity();
217                result.add(identity);
218            } else if (node instanceof MemoryCheckpoint.Multi) {
219                for (LocationIdentity identity : ((MemoryCheckpoint.Multi) node).getLocationIdentities()) {
220                    result.add(identity);
221                }
222            }
223            if (result.isAny()) {
224                break;
225            }
226        }
227        return result;
228    }
229
230    public boolean canKillBetweenThisAndDominator(LocationIdentity location) {
231        if (location.isImmutable()) {
232            return false;
233        }
234        return this.getKillLocationsBetweenThisAndDominator().contains(location);
235    }
236
237    private LocationSet getKillLocationsBetweenThisAndDominator() {
238        if (this.killLocationsBetweenThisAndDominator == null) {
239            LocationSet dominatorResult = new LocationSet();
240            Block stopBlock = getDominator();
241            if (this.isLoopHeader()) {
242                assert stopBlock.getLoopDepth() < this.getLoopDepth();
243                dominatorResult.addAll(((HIRLoop) this.getLoop()).getKillLocations());
244            } else {
245                for (Block b : this.getPredecessors()) {
246                    assert !this.isLoopHeader();
247                    if (b != stopBlock) {
248                        dominatorResult.addAll(b.getKillLocations());
249                        if (dominatorResult.isAny()) {
250                            break;
251                        }
252                        b.calcKillLocationsBetweenThisAndTarget(dominatorResult, stopBlock);
253                        if (dominatorResult.isAny()) {
254                            break;
255                        }
256                    }
257                }
258            }
259            this.killLocationsBetweenThisAndDominator = dominatorResult;
260        }
261        return this.killLocationsBetweenThisAndDominator;
262    }
263
264    private void calcKillLocationsBetweenThisAndTarget(LocationSet result, Block stopBlock) {
265        assert AbstractControlFlowGraph.dominates(stopBlock, this);
266        if (stopBlock == this || result.isAny()) {
267            // We reached the stop block => nothing to do.
268            return;
269        } else {
270            if (stopBlock == this.getDominator()) {
271                result.addAll(this.getKillLocationsBetweenThisAndDominator());
272            } else {
273                // Divide and conquer: Aggregate kill locations from this to the dominator and then
274                // from the dominator onwards.
275                calcKillLocationsBetweenThisAndTarget(result, this.getDominator());
276                result.addAll(this.getDominator().getKillLocations());
277                if (result.isAny()) {
278                    return;
279                }
280                this.getDominator().calcKillLocationsBetweenThisAndTarget(result, stopBlock);
281            }
282        }
283    }
284}