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.nodes.cfg;
26
27 import java.util.ArrayList;
28 import java.util.Arrays;
29 import java.util.BitSet;
30 import java.util.List;
31
32 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
33 import org.graalvm.compiler.core.common.cfg.CFGVerifier;
34 import org.graalvm.compiler.core.common.cfg.Loop;
35 import org.graalvm.compiler.debug.DebugContext;
36 import org.graalvm.compiler.debug.GraalError;
37 import org.graalvm.compiler.graph.Node;
38 import org.graalvm.compiler.graph.NodeMap;
39 import org.graalvm.compiler.nodes.AbstractBeginNode;
40 import org.graalvm.compiler.nodes.AbstractEndNode;
41 import org.graalvm.compiler.nodes.ControlSinkNode;
42 import org.graalvm.compiler.nodes.ControlSplitNode;
43 import org.graalvm.compiler.nodes.EndNode;
44 import org.graalvm.compiler.nodes.FixedNode;
45 import org.graalvm.compiler.nodes.FixedWithNextNode;
46 import org.graalvm.compiler.nodes.IfNode;
47 import org.graalvm.compiler.nodes.LoopBeginNode;
48 import org.graalvm.compiler.nodes.LoopEndNode;
49 import org.graalvm.compiler.nodes.LoopExitNode;
50 import org.graalvm.compiler.nodes.MergeNode;
51 import org.graalvm.compiler.nodes.StructuredGraph;
52 import org.graalvm.compiler.nodes.StructuredGraph.GuardsStage;
53
54 public final class ControlFlowGraph implements AbstractControlFlowGraph<Block> {
55 /**
56 * Don't allow relative frequency values to be become too small or too high as this makes
57 * frequency calculations over- or underflow the range of a double. This commonly happens with
58 * infinite loops within infinite loops. The value is chosen a bit lower than half the maximum
59 * exponent supported by double. That way we can never overflow to infinity when multiplying two
60 * relative frequency values.
61 */
62 public static final double MIN_RELATIVE_FREQUENCY = 0x1.0p-500;
63 public static final double MAX_RELATIVE_FREQUENCY = 1 / MIN_RELATIVE_FREQUENCY;
64
65 public final StructuredGraph graph;
66
67 private NodeMap<Block> nodeToBlock;
68 private Block[] reversePostOrder;
69 private List<Loop<Block>> loops;
70 private int maxDominatorDepth;
71
72 public interface RecursiveVisitor<V> {
597 if (graph.hasLoops()) {
598 Block[] stack = new Block[this.reversePostOrder.length];
599 for (Block block : reversePostOrder) {
600 AbstractBeginNode beginNode = block.getBeginNode();
601 if (beginNode instanceof LoopBeginNode) {
602 Loop<Block> parent = block.getLoop();
603 Loop<Block> loop = new HIRLoop(parent, loops.size(), block);
604 if (parent != null) {
605 parent.getChildren().add(loop);
606 }
607 loops.add(loop);
608 block.setLoop(loop);
609 loop.getBlocks().add(block);
610
611 LoopBeginNode loopBegin = (LoopBeginNode) beginNode;
612 for (LoopEndNode end : loopBegin.loopEnds()) {
613 Block endBlock = nodeToBlock.get(end);
614 computeLoopBlocks(endBlock, loop, stack, true);
615 }
616
617 if (graph.getGuardsStage() != GuardsStage.AFTER_FSA) {
618 for (LoopExitNode exit : loopBegin.loopExits()) {
619 Block exitBlock = nodeToBlock.get(exit);
620 assert exitBlock.getPredecessorCount() == 1;
621 computeLoopBlocks(exitBlock.getFirstPredecessor(), loop, stack, true);
622 loop.addExit(exitBlock);
623 }
624
625 // The following loop can add new blocks to the end of the loop's block
626 // list.
627 int size = loop.getBlocks().size();
628 for (int i = 0; i < size; ++i) {
629 Block b = loop.getBlocks().get(i);
630 for (Block sux : b.getSuccessors()) {
631 if (sux.getLoop() != loop) {
632 AbstractBeginNode begin = sux.getBeginNode();
633 if (!(begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == loopBegin)) {
634 graph.getDebug().log(DebugContext.VERBOSE_LEVEL, "Unexpected loop exit with %s, including whole branch in the loop", sux);
635 computeLoopBlocks(sux, loop, stack, false);
636 }
637 }
638 }
639 }
640 }
641 }
642 }
643 }
644
645 /*
646 * Compute the loop exit blocks after FSA.
647 */
648 if (graph.getGuardsStage() == GuardsStage.AFTER_FSA) {
649 for (Block b : reversePostOrder) {
650 if (b.getLoop() != null) {
651 for (Block succ : b.getSuccessors()) {
652 // if the loop of the succ is a different one (or none)
653 if (b.getLoop() != succ.getLoop()) {
654 // and the succ loop is not a child loop of the curr one
655 if (succ.getLoop() == null) {
656 // we might exit multiple loops if b.loops is not a loop at depth 0
657 Loop<Block> curr = b.getLoop();
658 while (curr != null) {
659 curr.addExit(succ);
660 curr = curr.getParent();
661 }
662 } else {
663 /*
664 * succ also has a loop, might be a child loop
665 *
666 * if it is a child loop we do not exit a loop. if it is a loop
667 * different than b.loop and not a child loop it must be a parent
668 * loop, thus we exit all loops between b.loop and succ.loop
669 *
670 * if we exit multiple loops immediately after each other the
671 * bytecode parser might generate loop exit nodes after another and
672 * the CFG will identify them as separate blocks, we just take the
673 * first one and exit all loops at this one
674 */
675 if (succ.getLoop().getParent() != b.getLoop()) {
676 assert succ.getLoop().getDepth() < b.getLoop().getDepth();
677 // b.loop must not be a transitive parent of succ.loop
678 assert !Loop.transitiveParentLoop(succ.getLoop(), b.getLoop());
679 Loop<Block> curr = b.getLoop();
680 while (curr != null && curr != succ.getLoop()) {
681 curr.addExit(succ);
682 curr = curr.getParent();
683 }
684 }
685 }
686 }
687 }
688 }
689 }
690 }
691
692 }
693
694 private static void computeLoopBlocks(Block start, Loop<Block> loop, Block[] stack, boolean usePred) {
695 if (start.getLoop() != loop) {
696 start.setLoop(loop);
697 stack[0] = start;
698 loop.getBlocks().add(start);
699 int tos = 0;
700 do {
701 Block block = stack[tos--];
702
703 // Add predecessors or successors to the loop.
704 for (Block b : (usePred ? block.getPredecessors() : block.getSuccessors())) {
705 if (b.getLoop() != loop) {
706 stack[++tos] = b;
707 b.setLoop(loop);
708 loop.getBlocks().add(b);
709 }
710 }
711 } while (tos >= 0);
|
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.nodes.cfg;
26
27 import static org.graalvm.compiler.core.common.cfg.AbstractBlockBase.BLOCK_ID_COMPARATOR;
28
29 import java.util.ArrayList;
30 import java.util.Arrays;
31 import java.util.BitSet;
32 import java.util.List;
33
34 import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
35 import org.graalvm.compiler.core.common.cfg.CFGVerifier;
36 import org.graalvm.compiler.core.common.cfg.Loop;
37 import org.graalvm.compiler.debug.DebugContext;
38 import org.graalvm.compiler.debug.GraalError;
39 import org.graalvm.compiler.graph.Node;
40 import org.graalvm.compiler.graph.NodeMap;
41 import org.graalvm.compiler.nodes.AbstractBeginNode;
42 import org.graalvm.compiler.nodes.AbstractEndNode;
43 import org.graalvm.compiler.nodes.ControlSinkNode;
44 import org.graalvm.compiler.nodes.ControlSplitNode;
45 import org.graalvm.compiler.nodes.EndNode;
46 import org.graalvm.compiler.nodes.FixedNode;
47 import org.graalvm.compiler.nodes.FixedWithNextNode;
48 import org.graalvm.compiler.nodes.IfNode;
49 import org.graalvm.compiler.nodes.LoopBeginNode;
50 import org.graalvm.compiler.nodes.LoopEndNode;
51 import org.graalvm.compiler.nodes.LoopExitNode;
52 import org.graalvm.compiler.nodes.MergeNode;
53 import org.graalvm.compiler.nodes.StructuredGraph;
54
55 public final class ControlFlowGraph implements AbstractControlFlowGraph<Block> {
56 /**
57 * Don't allow relative frequency values to be become too small or too high as this makes
58 * frequency calculations over- or underflow the range of a double. This commonly happens with
59 * infinite loops within infinite loops. The value is chosen a bit lower than half the maximum
60 * exponent supported by double. That way we can never overflow to infinity when multiplying two
61 * relative frequency values.
62 */
63 public static final double MIN_RELATIVE_FREQUENCY = 0x1.0p-500;
64 public static final double MAX_RELATIVE_FREQUENCY = 1 / MIN_RELATIVE_FREQUENCY;
65
66 public final StructuredGraph graph;
67
68 private NodeMap<Block> nodeToBlock;
69 private Block[] reversePostOrder;
70 private List<Loop<Block>> loops;
71 private int maxDominatorDepth;
72
73 public interface RecursiveVisitor<V> {
598 if (graph.hasLoops()) {
599 Block[] stack = new Block[this.reversePostOrder.length];
600 for (Block block : reversePostOrder) {
601 AbstractBeginNode beginNode = block.getBeginNode();
602 if (beginNode instanceof LoopBeginNode) {
603 Loop<Block> parent = block.getLoop();
604 Loop<Block> loop = new HIRLoop(parent, loops.size(), block);
605 if (parent != null) {
606 parent.getChildren().add(loop);
607 }
608 loops.add(loop);
609 block.setLoop(loop);
610 loop.getBlocks().add(block);
611
612 LoopBeginNode loopBegin = (LoopBeginNode) beginNode;
613 for (LoopEndNode end : loopBegin.loopEnds()) {
614 Block endBlock = nodeToBlock.get(end);
615 computeLoopBlocks(endBlock, loop, stack, true);
616 }
617
618 // Note that at this point, due to traversal order, child loops of `loop` have
619 // not been discovered yet.
620 for (Block b : loop.getBlocks()) {
621 for (Block sux : b.getSuccessors()) {
622 if (sux.getLoop() != loop) {
623 assert sux.getLoopDepth() < loop.getDepth();
624 loop.getNaturalExits().add(sux);
625 }
626 }
627 }
628 loop.getNaturalExits().sort(BLOCK_ID_COMPARATOR);
629
630 if (!graph.getGuardsStage().areFrameStatesAtDeopts()) {
631 for (LoopExitNode exit : loopBegin.loopExits()) {
632 Block exitBlock = nodeToBlock.get(exit);
633 assert exitBlock.getPredecessorCount() == 1;
634 computeLoopBlocks(exitBlock.getFirstPredecessor(), loop, stack, true);
635 loop.getLoopExits().add(exitBlock);
636 }
637 loop.getLoopExits().sort(BLOCK_ID_COMPARATOR);
638
639 // The following loop can add new blocks to the end of the loop's block
640 // list.
641 int size = loop.getBlocks().size();
642 for (int i = 0; i < size; ++i) {
643 Block b = loop.getBlocks().get(i);
644 for (Block sux : b.getSuccessors()) {
645 if (sux.getLoop() != loop) {
646 AbstractBeginNode begin = sux.getBeginNode();
647 if (!loopBegin.isLoopExit(begin)) {
648 assert !(begin instanceof LoopBeginNode);
649 assert sux.getLoopDepth() < loop.getDepth();
650 graph.getDebug().log(DebugContext.VERBOSE_LEVEL, "Unexpected loop exit with %s, including whole branch in the loop", sux);
651 computeLoopBlocks(sux, loop, stack, false);
652 }
653 }
654 }
655 }
656 } else {
657 loop.getLoopExits().addAll(loop.getNaturalExits());
658 }
659 }
660 }
661 }
662 }
663
664 private static void computeLoopBlocks(Block start, Loop<Block> loop, Block[] stack, boolean usePred) {
665 if (start.getLoop() != loop) {
666 start.setLoop(loop);
667 stack[0] = start;
668 loop.getBlocks().add(start);
669 int tos = 0;
670 do {
671 Block block = stack[tos--];
672
673 // Add predecessors or successors to the loop.
674 for (Block b : (usePred ? block.getPredecessors() : block.getSuccessors())) {
675 if (b.getLoop() != loop) {
676 stack[++tos] = b;
677 b.setLoop(loop);
678 loop.getBlocks().add(b);
679 }
680 }
681 } while (tos >= 0);
|