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