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