1 /*
   2  * Copyright (c) 2012, 2018, 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 }