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 }