1/*
2 * Copyright (c) 2011, 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.Arrays;
27import java.util.Collections;
28import java.util.List;
29
30import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
31import org.graalvm.compiler.core.common.cfg.CFGVerifier;
32import org.graalvm.compiler.core.common.cfg.Loop;
33import org.graalvm.compiler.debug.Debug;
34import org.graalvm.compiler.debug.GraalError;
35import org.graalvm.compiler.graph.Node;
36import org.graalvm.compiler.graph.NodeMap;
37import org.graalvm.compiler.nodes.AbstractBeginNode;
38import org.graalvm.compiler.nodes.AbstractEndNode;
39import org.graalvm.compiler.nodes.ControlSplitNode;
40import org.graalvm.compiler.nodes.EndNode;
41import org.graalvm.compiler.nodes.FixedNode;
42import org.graalvm.compiler.nodes.FixedWithNextNode;
43import org.graalvm.compiler.nodes.IfNode;
44import org.graalvm.compiler.nodes.LoopBeginNode;
45import org.graalvm.compiler.nodes.LoopEndNode;
46import org.graalvm.compiler.nodes.LoopExitNode;
47import org.graalvm.compiler.nodes.MergeNode;
48import org.graalvm.compiler.nodes.StructuredGraph;
49import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
50
51public final class ControlFlowGraph implements AbstractControlFlowGraph<Block> {
52    /**
53     * Don't allow probability values to be become too small or too high as this makes frequency
54     * calculations over- or underflow the range of a double. This commonly happens with infinite
55     * loops within infinite loops. The value is chosen a bit lower than half the maximum exponent
56     * supported by double. That way we can never overflow to infinity when multiplying two
57     * probability values.
58     */
59    public static final double MIN_PROBABILITY = 0x1.0p-500;
60    public static final double MAX_PROBABILITY = 1 / MIN_PROBABILITY;
61
62    public final StructuredGraph graph;
63
64    private NodeMap<Block> nodeToBlock;
65    private Block[] reversePostOrder;
66    private List<Loop<Block>> loops;
67
68    public static ControlFlowGraph compute(StructuredGraph graph, boolean connectBlocks, boolean computeLoops, boolean computeDominators, boolean computePostdominators) {
69        ControlFlowGraph cfg = new ControlFlowGraph(graph);
70        cfg.identifyBlocks();
71        cfg.computeProbabilities();
72
73        if (computeLoops) {
74            cfg.computeLoopInformation();
75        }
76        if (computeDominators) {
77            cfg.computeDominators();
78        }
79        if (computePostdominators) {
80            cfg.computePostdominators();
81        }
82        // there's not much to verify when connectBlocks == false
83        assert !(connectBlocks || computeLoops || computeDominators || computePostdominators) || CFGVerifier.verify(cfg);
84        return cfg;
85    }
86
87    private ControlFlowGraph(StructuredGraph graph) {
88        this.graph = graph;
89        this.nodeToBlock = graph.createNodeMap();
90    }
91
92    private void computeDominators() {
93        assert reversePostOrder[0].getPredecessorCount() == 0 : "start block has no predecessor and therefore no dominator";
94        Block[] blocks = reversePostOrder;
95        for (int i = 1; i < blocks.length; i++) {
96            Block block = blocks[i];
97            assert block.getPredecessorCount() > 0;
98            Block dominator = null;
99            for (Block pred : block.getPredecessors()) {
100                if (!pred.isLoopEnd()) {
101                    dominator = ((dominator == null) ? pred : commonDominatorRaw(dominator, pred));
102                }
103            }
104            // set dominator
105            block.setDominator(dominator);
106            if (dominator.getDominated().equals(Collections.emptyList())) {
107                dominator.setDominated(new ArrayList<>());
108            }
109            dominator.getDominated().add(block);
110        }
111        calcDominatorRanges(getStartBlock(), reversePostOrder.length);
112    }
113
114    private static void calcDominatorRanges(Block block, int size) {
115        Block[] stack = new Block[size];
116        stack[0] = block;
117        int tos = 0;
118        int myNumber = 0;
119
120        do {
121            Block cur = stack[tos];
122            List<Block> dominated = cur.getDominated();
123
124            if (cur.getDominatorNumber() == -1) {
125                cur.setDominatorNumber(myNumber);
126                if (dominated.size() > 0) {
127                    // Push children onto stack.
128                    for (Block b : dominated) {
129                        stack[++tos] = b;
130                    }
131                } else {
132                    cur.setMaxChildDomNumber(myNumber);
133                    --tos;
134                }
135                ++myNumber;
136            } else {
137                cur.setMaxChildDomNumber(dominated.get(0).getMaxChildDominatorNumber());
138                --tos;
139            }
140        } while (tos >= 0);
141    }
142
143    private static Block commonDominatorRaw(Block a, Block b) {
144        int aDomDepth = a.getDominatorDepth();
145        int bDomDepth = b.getDominatorDepth();
146        if (aDomDepth > bDomDepth) {
147            return commonDominatorRawSameDepth(a.getDominator(aDomDepth - bDomDepth), b);
148        } else {
149            return commonDominatorRawSameDepth(a, b.getDominator(bDomDepth - aDomDepth));
150        }
151    }
152
153    private static Block commonDominatorRawSameDepth(Block a, Block b) {
154        Block iterA = a;
155        Block iterB = b;
156        while (iterA != iterB) {
157            iterA = iterA.getDominator();
158            iterB = iterB.getDominator();
159        }
160        return iterA;
161    }
162
163    @Override
164    public Block[] getBlocks() {
165        return reversePostOrder;
166    }
167
168    @Override
169    public Block getStartBlock() {
170        return reversePostOrder[0];
171    }
172
173    public Block[] reversePostOrder() {
174        return reversePostOrder;
175    }
176
177    public NodeMap<Block> getNodeToBlock() {
178        return nodeToBlock;
179    }
180
181    public Block blockFor(Node node) {
182        return nodeToBlock.get(node);
183    }
184
185    @Override
186    public List<Loop<Block>> getLoops() {
187        return loops;
188    }
189
190    private void identifyBlock(Block block) {
191        FixedWithNextNode cur = block.getBeginNode();
192        while (true) {
193            assert !cur.isDeleted();
194            assert nodeToBlock.get(cur) == null;
195            nodeToBlock.set(cur, block);
196            FixedNode next = cur.next();
197            if (next instanceof AbstractBeginNode) {
198                block.endNode = cur;
199                return;
200            } else if (next instanceof FixedWithNextNode) {
201                cur = (FixedWithNextNode) next;
202            } else {
203                nodeToBlock.set(next, block);
204                block.endNode = next;
205                return;
206            }
207        }
208    }
209
210    /**
211     * Identify and connect blocks (including loop backward edges). Predecessors need to be in the
212     * order expected when iterating phi inputs.
213     */
214    private void identifyBlocks() {
215        // Find all block headers.
216        int numBlocks = 0;
217        for (AbstractBeginNode begin : graph.getNodes(AbstractBeginNode.TYPE)) {
218            Block block = new Block(begin);
219            identifyBlock(block);
220            numBlocks++;
221        }
222
223        // Compute reverse post order.
224        int count = 0;
225        NodeMap<Block> nodeMap = this.nodeToBlock;
226        Block[] stack = new Block[numBlocks];
227        int tos = 0;
228        Block startBlock = blockFor(graph.start());
229        stack[0] = startBlock;
230        startBlock.setPredecessors(Block.EMPTY_ARRAY);
231        do {
232            Block block = stack[tos];
233            int id = block.getId();
234            if (id == BLOCK_ID_INITIAL) {
235                // First time we see this block: push all successors.
236                FixedNode last = block.getEndNode();
237                if (last instanceof EndNode) {
238                    EndNode endNode = (EndNode) last;
239                    Block suxBlock = nodeMap.get(endNode.merge());
240                    if (suxBlock.getId() == BLOCK_ID_INITIAL) {
241                        stack[++tos] = suxBlock;
242                    }
243                    block.setSuccessors(new Block[]{suxBlock});
244                } else if (last instanceof IfNode) {
245                    IfNode ifNode = (IfNode) last;
246                    Block trueSucc = nodeMap.get(ifNode.trueSuccessor());
247                    stack[++tos] = trueSucc;
248                    Block falseSucc = nodeMap.get(ifNode.falseSuccessor());
249                    stack[++tos] = falseSucc;
250                    block.setSuccessors(new Block[]{trueSucc, falseSucc});
251                    Block[] ifPred = new Block[]{block};
252                    trueSucc.setPredecessors(ifPred);
253                    falseSucc.setPredecessors(ifPred);
254                } else if (last instanceof LoopEndNode) {
255                    LoopEndNode loopEndNode = (LoopEndNode) last;
256                    block.setSuccessors(new Block[]{nodeMap.get(loopEndNode.loopBegin())});
257                    // Nothing to do push onto the stack.
258                } else {
259                    assert !(last instanceof AbstractEndNode) : "Algorithm only supports EndNode and LoopEndNode.";
260                    int startTos = tos;
261                    Block[] ifPred = new Block[]{block};
262                    for (Node suxNode : last.successors()) {
263                        Block sux = nodeMap.get(suxNode);
264                        stack[++tos] = sux;
265                        sux.setPredecessors(ifPred);
266                    }
267                    int suxCount = tos - startTos;
268                    Block[] successors = new Block[suxCount];
269                    System.arraycopy(stack, startTos + 1, successors, 0, suxCount);
270                    block.setSuccessors(successors);
271                }
272                block.setId(BLOCK_ID_VISITED);
273                AbstractBeginNode beginNode = block.getBeginNode();
274                if (beginNode instanceof LoopBeginNode) {
275                    computeLoopPredecessors(nodeMap, block, (LoopBeginNode) beginNode);
276                } else if (beginNode instanceof MergeNode) {
277                    MergeNode mergeNode = (MergeNode) beginNode;
278                    int forwardEndCount = mergeNode.forwardEndCount();
279                    Block[] predecessors = new Block[forwardEndCount];
280                    for (int i = 0; i < forwardEndCount; ++i) {
281                        predecessors[i] = nodeMap.get(mergeNode.forwardEndAt(i));
282                    }
283                    block.setPredecessors(predecessors);
284                }
285
286            } else if (id == BLOCK_ID_VISITED) {
287                // Second time we see this block: All successors have been processed, so add block
288                // to result list. Can safely reuse the stack for this.
289                --tos;
290                count++;
291                int index = numBlocks - count;
292                stack[index] = block;
293                block.setId(index);
294            } else {
295                throw GraalError.shouldNotReachHere();
296            }
297        } while (tos >= 0);
298
299        // Compute reverse postorder and number blocks.
300        assert count == numBlocks : "all blocks must be reachable";
301        this.reversePostOrder = stack;
302    }
303
304    private static void computeLoopPredecessors(NodeMap<Block> nodeMap, Block block, LoopBeginNode loopBeginNode) {
305        int forwardEndCount = loopBeginNode.forwardEndCount();
306        LoopEndNode[] loopEnds = loopBeginNode.orderedLoopEnds();
307        Block[] predecessors = new Block[forwardEndCount + loopEnds.length];
308        for (int i = 0; i < forwardEndCount; ++i) {
309            predecessors[i] = nodeMap.get(loopBeginNode.forwardEndAt(i));
310        }
311        for (int i = 0; i < loopEnds.length; ++i) {
312            predecessors[i + forwardEndCount] = nodeMap.get(loopEnds[i]);
313        }
314        block.setPredecessors(predecessors);
315    }
316
317    private void computeProbabilities() {
318
319        for (Block block : reversePostOrder) {
320            Block[] predecessors = block.getPredecessors();
321
322            double probability;
323            if (predecessors.length == 0) {
324                probability = 1D;
325            } else if (predecessors.length == 1) {
326                Block pred = predecessors[0];
327                probability = pred.probability;
328                if (pred.getSuccessorCount() > 1) {
329                    assert pred.getEndNode() instanceof ControlSplitNode;
330                    ControlSplitNode controlSplit = (ControlSplitNode) pred.getEndNode();
331                    probability *= controlSplit.probability(block.getBeginNode());
332                }
333            } else {
334                probability = predecessors[0].probability;
335                for (int i = 1; i < predecessors.length; ++i) {
336                    probability += predecessors[i].probability;
337                }
338
339                if (block.getBeginNode() instanceof LoopBeginNode) {
340                    LoopBeginNode loopBegin = (LoopBeginNode) block.getBeginNode();
341                    probability *= loopBegin.loopFrequency();
342                }
343            }
344            if (probability < MIN_PROBABILITY) {
345                block.setProbability(MIN_PROBABILITY);
346            } else if (probability > MAX_PROBABILITY) {
347                block.setProbability(MAX_PROBABILITY);
348            } else {
349                block.setProbability(probability);
350            }
351        }
352
353    }
354
355    private void computeLoopInformation() {
356        loops = new ArrayList<>();
357        if (graph.hasLoops()) {
358            Block[] stack = new Block[this.reversePostOrder.length];
359            for (Block block : reversePostOrder) {
360                AbstractBeginNode beginNode = block.getBeginNode();
361                if (beginNode instanceof LoopBeginNode) {
362                    Loop<Block> loop = new HIRLoop(block.getLoop(), loops.size(), block);
363                    loops.add(loop);
364                    block.loop = loop;
365                    loop.getBlocks().add(block);
366
367                    LoopBeginNode loopBegin = (LoopBeginNode) beginNode;
368                    for (LoopEndNode end : loopBegin.loopEnds()) {
369                        Block endBlock = nodeToBlock.get(end);
370                        computeLoopBlocks(endBlock, loop, stack, true);
371                    }
372
373                    if (graph.getGuardsStage() != GuardsStage.AFTER_FSA) {
374                        for (LoopExitNode exit : loopBegin.loopExits()) {
375                            Block exitBlock = nodeToBlock.get(exit);
376                            assert exitBlock.getPredecessorCount() == 1;
377                            computeLoopBlocks(exitBlock.getFirstPredecessor(), loop, stack, true);
378                            loop.getExits().add(exitBlock);
379                        }
380
381                        // The following loop can add new blocks to the end of the loop's block
382                        // list.
383                        int size = loop.getBlocks().size();
384                        for (int i = 0; i < size; ++i) {
385                            Block b = loop.getBlocks().get(i);
386                            for (Block sux : b.getSuccessors()) {
387                                if (sux.loop != loop) {
388                                    AbstractBeginNode begin = sux.getBeginNode();
389                                    if (!(begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == loopBegin)) {
390                                        Debug.log(Debug.VERBOSE_LOG_LEVEL, "Unexpected loop exit with %s, including whole branch in the loop", sux);
391                                        computeLoopBlocks(sux, loop, stack, false);
392                                    }
393                                }
394                            }
395                        }
396                    }
397                }
398            }
399        }
400
401        /*
402         * Compute the loop exit blocks after FSA.
403         */
404        if (graph.getGuardsStage() == GuardsStage.AFTER_FSA) {
405            for (Block b : reversePostOrder) {
406                if (b.getLoop() != null) {
407                    for (Block succ : b.getSuccessors()) {
408                        // if the loop of the succ is a different one (or none)
409                        if (b.getLoop() != succ.getLoop()) {
410                            // and the succ loop is not a child loop of the curr one
411                            if (succ.getLoop() == null) {
412                                // we might exit multiple loops if b.loops is not a loop at depth 0
413                                Loop<Block> curr = b.getLoop();
414                                while (curr != null) {
415                                    curr.getExits().add(succ);
416                                    curr = curr.getParent();
417                                }
418                            } else {
419                                /*
420                                 * succ also has a loop, might be a child loop
421                                 *
422                                 * if it is a child loop we do not exit a loop. if it is a loop
423                                 * different than b.loop and not a child loop it must be a parent
424                                 * loop, thus we exit all loops between b.loop and succ.loop
425                                 *
426                                 * if we exit multiple loops immediately after each other the
427                                 * bytecode parser might generate loop exit nodes after another and
428                                 * the CFG will identify them as separate blocks, we just take the
429                                 * first one and exit all loops at this one
430                                 */
431                                if (succ.getLoop().getParent() != b.getLoop()) {
432                                    assert succ.getLoop().getDepth() < b.getLoop().getDepth();
433                                    // b.loop must not be a transitive parent of succ.loop
434                                    assert !Loop.transitiveParentLoop(succ.getLoop(), b.getLoop());
435                                    Loop<Block> curr = b.getLoop();
436                                    while (curr != null && curr != succ.getLoop()) {
437                                        curr.getExits().add(succ);
438                                        curr = curr.getParent();
439                                    }
440                                }
441                            }
442                        }
443                    }
444                }
445            }
446        }
447
448    }
449
450    private static void computeLoopBlocks(Block start, Loop<Block> loop, Block[] stack, boolean usePred) {
451        if (start.loop != loop) {
452            start.loop = loop;
453            stack[0] = start;
454            loop.getBlocks().add(start);
455            int tos = 0;
456            do {
457                Block block = stack[tos--];
458
459                // Add predecessors or successors to the loop.
460                for (Block b : (usePred ? block.getPredecessors() : block.getSuccessors())) {
461                    if (b.loop != loop) {
462                        stack[++tos] = b;
463                        b.loop = loop;
464                        loop.getBlocks().add(b);
465                    }
466                }
467            } while (tos >= 0);
468        }
469    }
470
471    public void computePostdominators() {
472
473        Block[] reversePostOrderTmp = this.reversePostOrder;
474
475        outer: for (int j = reversePostOrderTmp.length - 1; j >= 0; --j) {
476            Block block = reversePostOrderTmp[j];
477            if (block.isLoopEnd()) {
478                // We do not want the loop header registered as the postdominator of the loop end.
479                continue;
480            }
481            if (block.getSuccessorCount() == 0) {
482                // No successors => no postdominator.
483                continue;
484            }
485            Block firstSucc = block.getSuccessors()[0];
486            if (block.getSuccessorCount() == 1) {
487                block.postdominator = firstSucc;
488                continue;
489            }
490            Block postdominator = firstSucc;
491            for (Block sux : block.getSuccessors()) {
492                postdominator = commonPostdominator(postdominator, sux);
493                if (postdominator == null) {
494                    // There is a dead end => no postdominator available.
495                    continue outer;
496                }
497            }
498            assert !Arrays.asList(block.getSuccessors()).contains(postdominator) : "Block " + block + " has a wrong post dominator: " + postdominator;
499            block.postdominator = postdominator;
500        }
501    }
502
503    private static Block commonPostdominator(Block a, Block b) {
504        Block iterA = a;
505        Block iterB = b;
506        while (iterA != iterB) {
507            if (iterA.getId() < iterB.getId()) {
508                iterA = iterA.getPostdominator();
509                if (iterA == null) {
510                    return null;
511                }
512            } else {
513                assert iterB.getId() < iterA.getId();
514                iterB = iterB.getPostdominator();
515                if (iterB == null) {
516                    return null;
517                }
518            }
519        }
520        return iterA;
521    }
522
523    public void setNodeToBlock(NodeMap<Block> nodeMap) {
524        this.nodeToBlock = nodeMap;
525    }
526}
527