1 /*
2  * Copyright (c) 2014, 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.Collection;
28 
29 public interface AbstractControlFlowGraph<T extends AbstractBlockBase<T>> {
30 
31     int BLOCK_ID_INITIAL = -1;
32     int BLOCK_ID_VISITED = -2;
33 
34     /**
35      * Returns the list blocks contained in this control flow graph.
36      *
37      * It is {@linkplain CFGVerifier guaranteed} that the blocks are numbered and ordered according
38      * to a reverse post order traversal of the control flow graph.
39      *
40      * @see CFGVerifier
41      */
getBlocks()42     T[] getBlocks();
43 
getLoops()44     Collection<Loop<T>> getLoops();
45 
getStartBlock()46     T getStartBlock();
47 
48     /**
49      * True if block {@code a} is dominated by block {@code b}.
50      */
isDominatedBy(AbstractBlockBase<?> a, AbstractBlockBase<?> b)51     static boolean isDominatedBy(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
52         int domNumberA = a.getDominatorNumber();
53         int domNumberB = b.getDominatorNumber();
54         return domNumberA >= domNumberB && domNumberA <= b.getMaxChildDominatorNumber();
55     }
56 
57     /**
58      * True if block {@code a} dominates block {@code b} and {@code a} is not identical block to
59      * {@code b}.
60      */
strictlyDominates(AbstractBlockBase<?> a, AbstractBlockBase<?> b)61     static boolean strictlyDominates(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
62         return a != b && dominates(a, b);
63     }
64 
65     /**
66      * True if block {@code a} dominates block {@code b}.
67      */
dominates(AbstractBlockBase<?> a, AbstractBlockBase<?> b)68     static boolean dominates(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
69         assert a != null && b != null;
70         return isDominatedBy(b, a);
71     }
72 
73     /**
74      * Calculates the common dominator of two blocks.
75      *
76      * Note that this algorithm makes use of special properties regarding the numbering of blocks.
77      *
78      * @see #getBlocks()
79      * @see CFGVerifier
80      */
commonDominator(AbstractBlockBase<?> a, AbstractBlockBase<?> b)81     static AbstractBlockBase<?> commonDominator(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
82         if (a == null) {
83             return b;
84         } else if (b == null) {
85             return a;
86         } else if (a == b) {
87             return a;
88         } else {
89             int aDomDepth = a.getDominatorDepth();
90             int bDomDepth = b.getDominatorDepth();
91             AbstractBlockBase<?> aTemp;
92             AbstractBlockBase<?> bTemp;
93             if (aDomDepth > bDomDepth) {
94                 aTemp = a;
95                 bTemp = b;
96             } else {
97                 aTemp = b;
98                 bTemp = a;
99             }
100             return commonDominatorHelper(aTemp, bTemp);
101         }
102     }
103 
commonDominatorHelper(AbstractBlockBase<?> a, AbstractBlockBase<?> b)104     static AbstractBlockBase<?> commonDominatorHelper(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
105         int domNumberA = a.getDominatorNumber();
106         AbstractBlockBase<?> result = b;
107         while (domNumberA < result.getDominatorNumber()) {
108             result = result.getDominator();
109         }
110         while (domNumberA > result.getMaxChildDominatorNumber()) {
111             result = result.getDominator();
112         }
113         return result;
114     }
115 
116     /**
117      * @see AbstractControlFlowGraph#commonDominator(AbstractBlockBase, AbstractBlockBase)
118      */
119     @SuppressWarnings("unchecked")
commonDominatorTyped(T a, T b)120     static <T extends AbstractBlockBase<T>> T commonDominatorTyped(T a, T b) {
121         return (T) commonDominator(a, b);
122     }
123 }
124