001/*
002 * Copyright (c) 2012, 2014, 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.common.cfg;
024
025import java.util.*;
026
027public class CFGVerifier {
028
029    public static <T extends AbstractBlockBase<T>, C extends AbstractControlFlowGraph<T>> boolean verify(C cfg) {
030        for (T block : cfg.getBlocks()) {
031            assert block.getId() >= 0;
032            assert cfg.getBlocks().get(block.getId()) == block;
033
034            for (T pred : block.getPredecessors()) {
035                assert pred.getSuccessors().contains(block);
036                assert pred.getId() < block.getId() || pred.isLoopEnd();
037            }
038
039            for (T sux : block.getSuccessors()) {
040                assert sux.getPredecessors().contains(block);
041                assert sux.getId() > block.getId() || sux.isLoopHeader();
042            }
043
044            if (block.getDominator() != null) {
045                assert block.getDominator().getId() < block.getId();
046                assert block.getDominator().getDominated().contains(block);
047            }
048            for (T dominated : block.getDominated()) {
049                assert dominated.getId() > block.getId();
050                assert dominated.getDominator() == block;
051            }
052
053            T postDominatorBlock = block.getPostdominator();
054            if (postDominatorBlock != null) {
055                assert block.getSuccessorCount() > 0 : "block has post-dominator block, but no successors";
056
057                BlockMap<Boolean> visitedBlocks = new BlockMap<>(cfg);
058                visitedBlocks.put(block, true);
059
060                Deque<T> stack = new ArrayDeque<>();
061                for (T sux : block.getSuccessors()) {
062                    visitedBlocks.put(sux, true);
063                    stack.push(sux);
064                }
065
066                while (stack.size() > 0) {
067                    T tos = stack.pop();
068                    assert tos.getId() <= postDominatorBlock.getId();
069                    if (tos == postDominatorBlock) {
070                        continue; // found a valid path
071                    }
072                    assert tos.getSuccessorCount() > 0 : "no path found";
073
074                    for (T sux : tos.getSuccessors()) {
075                        if (visitedBlocks.get(sux) == null) {
076                            visitedBlocks.put(sux, true);
077                            stack.push(sux);
078                        }
079                    }
080                }
081            }
082
083            assert cfg.getLoops() == null || !block.isLoopHeader() || block.getLoop().getHeader() == block;
084        }
085
086        if (cfg.getLoops() != null) {
087            for (Loop<T> loop : cfg.getLoops()) {
088                assert loop.getHeader().isLoopHeader();
089
090                for (T block : loop.getBlocks()) {
091                    assert block.getId() >= loop.getHeader().getId();
092
093                    Loop<?> blockLoop = block.getLoop();
094                    while (blockLoop != loop) {
095                        assert blockLoop != null;
096                        blockLoop = blockLoop.getParent();
097                    }
098
099                    if (!(block.isLoopHeader() && block.getLoop() == loop)) {
100                        for (T pred : block.getPredecessors()) {
101                            if (!loop.getBlocks().contains(pred)) {
102                                assert false : "Loop " + loop + " does not contain " + pred;
103                                return false;
104                            }
105                        }
106                    }
107                }
108
109                for (T block : loop.getExits()) {
110                    assert block.getId() >= loop.getHeader().getId();
111
112                    Loop<?> blockLoop = block.getLoop();
113                    while (blockLoop != null) {
114                        blockLoop = blockLoop.getParent();
115                        assert blockLoop != loop;
116                    }
117                }
118            }
119        }
120
121        return true;
122    }
123}