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 }