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