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.Arrays; 26 import java.util.BitSet; 27 import java.util.EnumMap; 28 import java.util.Set; 29 import java.util.stream.Stream; 30 31 /** 32 * This class represents a dominator tree problem, i.e. a problem which can be solved by traversing 33 * the dominator (sub-)tree. 34 * 35 * @param <E> An enum that describes the flags that can be associated with a block. 36 * @param <C> An arbitrary cost type that is associated with a block. It is intended to carry 37 * information needed to calculate the solution. Note that {@code C} should not contain 38 * boolean flags. Use an enum entry in {@code E} instead. 39 */ 40 public abstract class DominatorOptimizationProblem<E extends Enum<E>, C> { 41 42 private AbstractBlockBase<?>[] blocks; 43 private EnumMap<E, BitSet> flags; 44 private BlockMap<C> costs; 45 46 protected DominatorOptimizationProblem(Class<E> flagType, AbstractControlFlowGraph<?> cfg) { 47 this.blocks = cfg.getBlocks(); 48 flags = new EnumMap<>(flagType); 49 costs = new BlockMap<>(cfg); 50 assert verify(blocks); 51 } 52 53 private static boolean verify(AbstractBlockBase<?>[] blocks) { 54 for (int i = 0; i < blocks.length; i++) { 55 AbstractBlockBase<?> block = blocks[i]; 56 if (i != block.getId()) { 57 assert false : String.format("Id index mismatch @ %d vs. %s.getId()==%d", i, block, block.getId()); 58 return false; 59 } 60 } 61 return true; 62 } 63 64 public final AbstractBlockBase<?>[] getBlocks() { 65 return blocks; 66 } 67 68 public final AbstractBlockBase<?> getBlockForId(int id) { 69 AbstractBlockBase<?> block = blocks[id]; 70 assert block.getId() == id : "wrong block-to-id mapping"; 71 return block; 72 } 73 74 /** 75 * Sets a flag for a block. 76 */ 77 public final void set(E flag, AbstractBlockBase<?> block) { 78 BitSet bitSet = flags.get(flag); 79 if (bitSet == null) { 80 bitSet = new BitSet(blocks.length); 81 flags.put(flag, bitSet); 82 } 83 bitSet.set(block.getId()); 84 } 85 86 /** 87 * Checks whether a flag is set for a block. 88 */ 89 public final boolean get(E flag, AbstractBlockBase<?> block) { 90 BitSet bitSet = flags.get(flag); 91 return bitSet == null ? false : bitSet.get(block.getId()); 92 } 93 94 /** 95 * Returns a {@linkplain Stream} of blocks for which {@code flag} is set. 96 */ 97 public final Stream<? extends AbstractBlockBase<?>> stream(E flag) { 98 return Arrays.asList(getBlocks()).stream().filter(block -> get(flag, block)); 99 } 100 101 /** 102 * Returns the cost object associated with {@code block}. Might return {@code null} if not set. 103 */ 104 public final C getCost(AbstractBlockBase<?> block) { 105 C cost = costs.get(block); 106 return cost; 107 } 108 109 /** 110 * Sets the cost for a {@code block}. 111 */ 112 public final void setCost(AbstractBlockBase<?> block, C cost) { 113 costs.put(block, cost); 114 } 115 116 /** 117 * Sets {@code flag} for all blocks along the dominator path from {@code block} to the root 118 * until a block it finds a block where {@code flag} is already set. 119 */ 120 public final void setDominatorPath(E flag, AbstractBlockBase<?> block) { 121 BitSet bitSet = flags.get(flag); 122 if (bitSet == null) { 123 bitSet = new BitSet(blocks.length); 124 flags.put(flag, bitSet); 125 } 126 for (AbstractBlockBase<?> b = block; b != null && !bitSet.get(b.getId()); b = b.getDominator()) { 127 // mark block 128 bitSet.set(b.getId()); 129 } 130 } 131 132 /** 133 * Returns a {@link Stream} of flags associated with {@code block}. 134 */ 135 public final Stream<E> getFlagsForBlock(AbstractBlockBase<?> block) { 136 return getFlags().stream().filter(flag -> get(flag, block)); 137 } 138 139 /** 140 * Returns the {@link Set} of flags that can be set for this 141 * {@linkplain DominatorOptimizationProblem problem}. 142 */ 143 public final Set<E> getFlags() { 144 return flags.keySet(); 145 } 146 147 /** 148 * Returns the name of a flag. 149 */ 150 public String getName(E flag) { 151 return flag.toString(); 152 } 153 }