1 /* 2 * Copyright (c) 2012, 2014, 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.common.cfg; 24 25 import java.util.ArrayDeque; 26 import java.util.Arrays; 27 import java.util.Deque; 28 29 public class CFGVerifier { 30 31 public static <T extends AbstractBlockBase<T>, C extends AbstractControlFlowGraph<T>> boolean verify(C cfg) { 32 for (T block : cfg.getBlocks()) { 33 assert block.getId() >= 0; 34 assert cfg.getBlocks()[block.getId()] == block; 35 36 for (T pred : block.getPredecessors()) { 37 assert Arrays.asList(pred.getSuccessors()).contains(block); 38 assert pred.getId() < block.getId() || pred.isLoopEnd(); 39 } 40 41 for (T sux : block.getSuccessors()) { 42 assert Arrays.asList(sux.getPredecessors()).contains(block); 43 assert sux.getId() > block.getId() || sux.isLoopHeader(); 44 } 45 46 if (block.getDominator() != null) { 47 assert block.getDominator().getId() < block.getId(); 48 assert block.getDominator().getDominated().contains(block); 49 } 50 for (T dominated : block.getDominated()) { 51 assert dominated.getId() > block.getId(); 52 assert dominated.getDominator() == block; 53 } 54 55 T postDominatorBlock = block.getPostdominator(); 56 if (postDominatorBlock != null) { 57 assert block.getSuccessorCount() > 0 : "block has post-dominator block, but no successors"; 58 59 BlockMap<Boolean> visitedBlocks = new BlockMap<>(cfg); 60 visitedBlocks.put(block, true); 61 62 Deque<T> stack = new ArrayDeque<>(); 63 for (T sux : block.getSuccessors()) { 64 visitedBlocks.put(sux, true); 65 stack.push(sux); 66 } 67 68 while (stack.size() > 0) { 69 T tos = stack.pop(); 70 assert tos.getId() <= postDominatorBlock.getId(); 71 if (tos == postDominatorBlock) { 72 continue; // found a valid path 73 } 74 assert tos.getSuccessorCount() > 0 : "no path found"; 75 76 for (T sux : tos.getSuccessors()) { 77 if (visitedBlocks.get(sux) == null) { 78 visitedBlocks.put(sux, true); 79 stack.push(sux); 80 } 81 } 82 } 83 } 84 85 assert cfg.getLoops() == null || !block.isLoopHeader() || block.getLoop().getHeader() == block; 86 } 87 88 if (cfg.getLoops() != null) { 89 for (Loop<T> loop : cfg.getLoops()) { 90 assert loop.getHeader().isLoopHeader(); 91 92 for (T block : loop.getBlocks()) { 93 assert block.getId() >= loop.getHeader().getId(); 94 95 Loop<?> blockLoop = block.getLoop(); 96 while (blockLoop != loop) { 97 assert blockLoop != null; 98 blockLoop = blockLoop.getParent(); 99 } 100 101 if (!(block.isLoopHeader() && block.getLoop() == loop)) { 102 for (T pred : block.getPredecessors()) { 103 if (!loop.getBlocks().contains(pred)) { 104 assert false : "Loop " + loop + " does not contain " + pred; 105 return false; 106 } 107 } 108 } 109 } 110 111 for (T block : loop.getExits()) { 112 assert block.getId() >= loop.getHeader().getId(); 113 114 Loop<?> blockLoop = block.getLoop(); 115 while (blockLoop != null) { 116 blockLoop = blockLoop.getParent(); 117 assert blockLoop != loop; 118 } 119 } 120 } 121 } 122 123 return true; 124 } 125 }