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 */ 42 T[] getBlocks(); 43 44 Collection<Loop<T>> getLoops(); 45 46 T getStartBlock(); 47 48 /** 49 * True if block {@code a} is dominated by block {@code b}. 50 */ 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 */ 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 */ 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 */ 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 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") 120 static <T extends AbstractBlockBase<T>> T commonDominatorTyped(T a, T b) { 121 return (T) commonDominator(a, b); 122 } 123 }