1 /* 2 * Copyright (c) 2012, 2012, 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.core.test; 24 25 import org.junit.Assert; 26 import org.junit.Test; 27 28 import org.graalvm.compiler.debug.Debug; 29 import org.graalvm.compiler.nodes.AbstractBeginNode; 30 import org.graalvm.compiler.nodes.AbstractMergeNode; 31 import org.graalvm.compiler.nodes.BeginNode; 32 import org.graalvm.compiler.nodes.EndNode; 33 import org.graalvm.compiler.nodes.IfNode; 34 import org.graalvm.compiler.nodes.MergeNode; 35 import org.graalvm.compiler.nodes.ReturnNode; 36 import org.graalvm.compiler.nodes.StructuredGraph; 37 import org.graalvm.compiler.nodes.StructuredGraph.AllowAssumptions; 38 import org.graalvm.compiler.nodes.cfg.Block; 39 import org.graalvm.compiler.nodes.cfg.ControlFlowGraph; 40 41 public class SimpleCFGTest extends GraalCompilerTest { 42 43 private static void dumpGraph(final StructuredGraph graph) { 44 Debug.dump(Debug.BASIC_LOG_LEVEL, graph, "Graph"); 45 } 46 47 @Test 48 public void testImplies() { 49 StructuredGraph graph = new StructuredGraph.Builder(getInitialOptions(), AllowAssumptions.YES).build(); 50 51 EndNode trueEnd = graph.add(new EndNode()); 52 EndNode falseEnd = graph.add(new EndNode()); 53 54 AbstractBeginNode trueBegin = graph.add(new BeginNode()); 55 trueBegin.setNext(trueEnd); 56 AbstractBeginNode falseBegin = graph.add(new BeginNode()); 57 falseBegin.setNext(falseEnd); 58 59 IfNode ifNode = graph.add(new IfNode(null, trueBegin, falseBegin, 0.5)); 60 graph.start().setNext(ifNode); 61 62 AbstractMergeNode merge = graph.add(new MergeNode()); 63 merge.addForwardEnd(trueEnd); 64 merge.addForwardEnd(falseEnd); 65 ReturnNode returnNode = graph.add(new ReturnNode(null)); 66 merge.setNext(returnNode); 67 68 dumpGraph(graph); 69 70 ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true); 71 72 Block[] blocks = cfg.getBlocks(); 73 // check number of blocks 74 assertDeepEquals(4, blocks.length); 75 76 // check block - node assignment 77 assertDeepEquals(blocks[0], cfg.blockFor(graph.start())); 78 assertDeepEquals(blocks[0], cfg.blockFor(ifNode)); 79 assertDeepEquals(blocks[1], cfg.blockFor(trueBegin)); 80 assertDeepEquals(blocks[1], cfg.blockFor(trueEnd)); 81 assertDeepEquals(blocks[2], cfg.blockFor(falseBegin)); 82 assertDeepEquals(blocks[2], cfg.blockFor(falseEnd)); 83 assertDeepEquals(blocks[3], cfg.blockFor(merge)); 84 assertDeepEquals(blocks[3], cfg.blockFor(returnNode)); 85 86 // check dominators 87 assertDominator(blocks[0], null); 88 assertDominator(blocks[1], blocks[0]); 89 assertDominator(blocks[2], blocks[0]); 90 assertDominator(blocks[3], blocks[0]); 91 92 // check dominated 93 assertDominatedSize(blocks[0], 3); 94 assertDominatedSize(blocks[1], 0); 95 assertDominatedSize(blocks[2], 0); 96 assertDominatedSize(blocks[3], 0); 97 98 // check postdominators 99 assertPostdominator(blocks[0], blocks[3]); 100 assertPostdominator(blocks[1], blocks[3]); 101 assertPostdominator(blocks[2], blocks[3]); 102 assertPostdominator(blocks[3], null); 103 } 104 105 public static void assertDominator(Block block, Block expectedDominator) { 106 Assert.assertEquals("dominator of " + block, expectedDominator, block.getDominator()); 107 } 108 109 public static void assertDominatedSize(Block block, int size) { 110 int count = 0; 111 Block domChild = block.getFirstDominated(); 112 while (domChild != null) { 113 count++; 114 domChild = domChild.getDominatedSibling(); 115 } 116 Assert.assertEquals("number of dominated blocks of " + block, size, count); 117 } 118 119 public static void assertPostdominator(Block block, Block expectedPostdominator) { 120 Assert.assertEquals("postdominator of " + block, expectedPostdominator, block.getPostdominator()); 121 } 122 123 }