001/*
002 * Copyright (c) 2014, 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.compiler.common.cfg;
024
025import java.util.*;
026import java.util.stream.*;
027
028/**
029 * This class represents a dominator tree problem, i.e. a problem which can be solved by traversing
030 * the dominator (sub-)tree.
031 *
032 * @param <E> An enum that describes the flags that can be associated with a block.
033 * @param <C> An arbitrary cost type that is associated with a block. It is intended to carry
034 *            information needed to calculate the solution. Note that {@code C} should not contain
035 *            boolean flags. Use an enum entry in {@code E} instead.
036 */
037public abstract class DominatorOptimizationProblem<E extends Enum<E>, C> {
038
039    private List<? extends AbstractBlockBase<?>> blocks;
040    private EnumMap<E, BitSet> flags;
041    private BlockMap<C> costs;
042
043    protected DominatorOptimizationProblem(Class<E> flagType, AbstractControlFlowGraph<?> cfg) {
044        this.blocks = cfg.getBlocks();
045        flags = new EnumMap<>(flagType);
046        costs = new BlockMap<>(cfg);
047        assert verify(blocks);
048    }
049
050    private static boolean verify(List<? extends AbstractBlockBase<?>> blocks) {
051        for (int i = 0; i < blocks.size(); i++) {
052            AbstractBlockBase<?> block = blocks.get(i);
053            if (i != block.getId()) {
054                assert false : String.format("Id index mismatch @ %d vs. %s.getId()==%d", i, block, block.getId());
055                return false;
056            }
057        }
058        return true;
059    }
060
061    public final List<? extends AbstractBlockBase<?>> getBlocks() {
062        return blocks;
063    }
064
065    public final AbstractBlockBase<?> getBlockForId(int id) {
066        AbstractBlockBase<?> block = blocks.get(id);
067        assert block.getId() == id : "wrong block-to-id mapping";
068        return block;
069    }
070
071    /**
072     * Sets a flag for a block.
073     */
074    public final void set(E flag, AbstractBlockBase<?> block) {
075        BitSet bitSet = flags.get(flag);
076        if (bitSet == null) {
077            bitSet = new BitSet(blocks.size());
078            flags.put(flag, bitSet);
079        }
080        bitSet.set(block.getId());
081    }
082
083    /**
084     * Checks whether a flag is set for a block.
085     */
086    public final boolean get(E flag, AbstractBlockBase<?> block) {
087        BitSet bitSet = flags.get(flag);
088        return bitSet == null ? false : bitSet.get(block.getId());
089    }
090
091    /**
092     * Returns a {@linkplain Stream} of blocks for which {@code flag} is set.
093     */
094    public final Stream<? extends AbstractBlockBase<?>> stream(E flag) {
095        return getBlocks().stream().filter(block -> get(flag, block));
096    }
097
098    /**
099     * Returns the cost object associated with {@code block}. Might return {@code null} if not set.
100     */
101    public final C getCost(AbstractBlockBase<?> block) {
102        C cost = costs.get(block);
103        return cost;
104    }
105
106    /**
107     * Sets the cost for a {@code block}.
108     */
109    public final void setCost(AbstractBlockBase<?> block, C cost) {
110        costs.put(block, cost);
111    }
112
113    /**
114     * Sets {@code flag} for all blocks along the dominator path from {@code block} to the root
115     * until a block it finds a block where {@code flag} is already set.
116     */
117    public final void setDominatorPath(E flag, AbstractBlockBase<?> block) {
118        BitSet bitSet = flags.get(flag);
119        if (bitSet == null) {
120            bitSet = new BitSet(blocks.size());
121            flags.put(flag, bitSet);
122        }
123        for (AbstractBlockBase<?> b = block; b != null && !bitSet.get(b.getId()); b = b.getDominator()) {
124            // mark block
125            bitSet.set(b.getId());
126        }
127    }
128
129    /**
130     * Returns a {@link Stream} of flags associated with {@code block}.
131     */
132    public final Stream<E> getFlagsForBlock(AbstractBlockBase<?> block) {
133        return getFlags().stream().filter(flag -> get(flag, block));
134    }
135
136    /**
137     * Returns the {@link Set} of flags that can be set for this
138     * {@linkplain DominatorOptimizationProblem problem}.
139     */
140    public final Set<E> getFlags() {
141        return flags.keySet();
142    }
143
144    /**
145     * Returns the name of a flag.
146     */
147    public String getName(E flag) {
148        return flag.toString();
149    }
150}