001/*
002 * Copyright (c) 2012, 2012, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.compiler.test;
024
025import java.util.*;
026
027import com.oracle.graal.debug.*;
028
029import org.junit.*;
030
031import com.oracle.graal.nodes.*;
032import com.oracle.graal.nodes.StructuredGraph.AllowAssumptions;
033import com.oracle.graal.nodes.cfg.*;
034
035public class SimpleCFGTest extends GraalCompilerTest {
036
037    private static void dumpGraph(final StructuredGraph graph) {
038        Debug.dump(graph, "Graph");
039    }
040
041    @Test
042    public void testImplies() {
043        StructuredGraph graph = new StructuredGraph(AllowAssumptions.YES);
044
045        EndNode trueEnd = graph.add(new EndNode());
046        EndNode falseEnd = graph.add(new EndNode());
047
048        AbstractBeginNode trueBegin = graph.add(new BeginNode());
049        trueBegin.setNext(trueEnd);
050        AbstractBeginNode falseBegin = graph.add(new BeginNode());
051        falseBegin.setNext(falseEnd);
052
053        IfNode ifNode = graph.add(new IfNode(null, trueBegin, falseBegin, 0.5));
054        graph.start().setNext(ifNode);
055
056        AbstractMergeNode merge = graph.add(new MergeNode());
057        merge.addForwardEnd(trueEnd);
058        merge.addForwardEnd(falseEnd);
059        ReturnNode returnNode = graph.add(new ReturnNode(null));
060        merge.setNext(returnNode);
061
062        dumpGraph(graph);
063
064        ControlFlowGraph cfg = ControlFlowGraph.compute(graph, true, true, true, true);
065
066        List<Block> blocks = cfg.getBlocks();
067        // check number of blocks
068        assertDeepEquals(4, blocks.size());
069
070        // check block - node assignment
071        assertDeepEquals(blocks.get(0), cfg.blockFor(graph.start()));
072        assertDeepEquals(blocks.get(0), cfg.blockFor(ifNode));
073        assertDeepEquals(blocks.get(1), cfg.blockFor(trueBegin));
074        assertDeepEquals(blocks.get(1), cfg.blockFor(trueEnd));
075        assertDeepEquals(blocks.get(2), cfg.blockFor(falseBegin));
076        assertDeepEquals(blocks.get(2), cfg.blockFor(falseEnd));
077        assertDeepEquals(blocks.get(3), cfg.blockFor(merge));
078        assertDeepEquals(blocks.get(3), cfg.blockFor(returnNode));
079
080        // check postOrder
081        Iterator<Block> it = cfg.postOrder().iterator();
082        for (int i = blocks.size() - 1; i >= 0; i--) {
083            assertTrue(it.hasNext());
084            Block b = it.next();
085            assertDeepEquals(blocks.get(i), b);
086        }
087
088        // check dominators
089        assertDominator(blocks.get(0), null);
090        assertDominator(blocks.get(1), blocks.get(0));
091        assertDominator(blocks.get(2), blocks.get(0));
092        assertDominator(blocks.get(3), blocks.get(0));
093
094        // check dominated
095        assertDominatedSize(blocks.get(0), 3);
096        assertDominatedSize(blocks.get(1), 0);
097        assertDominatedSize(blocks.get(2), 0);
098        assertDominatedSize(blocks.get(3), 0);
099
100        // check postdominators
101        assertPostdominator(blocks.get(0), blocks.get(3));
102        assertPostdominator(blocks.get(1), blocks.get(3));
103        assertPostdominator(blocks.get(2), blocks.get(3));
104        assertPostdominator(blocks.get(3), null);
105    }
106
107    public static void assertDominator(Block block, Block expectedDominator) {
108        Assert.assertEquals("dominator of " + block, expectedDominator, block.getDominator());
109    }
110
111    public static void assertDominatedSize(Block block, int size) {
112        Assert.assertEquals("number of dominated blocks of " + block, size, block.getDominated().size());
113    }
114
115    public static void assertPostdominator(Block block, Block expectedPostdominator) {
116        Assert.assertEquals("postdominator of " + block, expectedPostdominator, block.getPostdominator());
117    }
118
119}