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 
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 
verify(C cfg)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.getExits()) {
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 }
139