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 }