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