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 */
23package org.graalvm.compiler.core.common.cfg;
24
25import java.util.Arrays;
26import java.util.BitSet;
27import java.util.EnumMap;
28import java.util.Set;
29import 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 */
40public 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}
154