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