--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/DominatorOptimizationProblem.java	Mon Aug 25 17:18:36 2014 +0200
@@ -0,0 +1,150 @@
+/*
+ * Copyright (c) 2014, 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.compiler.common.cfg;
+
+import java.util.*;
+import java.util.stream.*;
+
+/**
+ * This class represents a dominator tree problem, i.e. a problem which can be solved by traversing
+ * the dominator (sub-)tree.
+ *
+ * @param <E> An enum that describes the flags that can be associated with a block.
+ * @param <C> An arbitrary cost type that is associated with a block. It is intended to carry
+ *            information needed to calculate the solution. Note that {@code C} should not contain
+ *            boolean flags. Use an enum entry in {@code E} instead.
+ */
+public abstract class DominatorOptimizationProblem<E extends Enum<E>, C> {
+
+    private List<? extends AbstractBlock<?>> blocks;
+    private EnumMap<E, BitSet> flags;
+    private BlockMap<C> costs;
+
+    protected DominatorOptimizationProblem(Class<E> flagType, AbstractControlFlowGraph<?> cfg) {
+        this.blocks = cfg.getBlocks();
+        flags = new EnumMap<>(flagType);
+        costs = new BlockMap<>(cfg);
+        assert verify(blocks);
+    }
+
+    private static boolean verify(List<? extends AbstractBlock<?>> blocks) {
+        for (int i = 0; i < blocks.size(); i++) {
+            AbstractBlock<?> block = blocks.get(i);
+            if (i != block.getId()) {
+                assert false : String.format("Id index mismatch @ %d vs. %s.getId()==%d", i, block, block.getId());
+                return false;
+            }
+        }
+        return true;
+    }
+
+    public final List<? extends AbstractBlock<?>> getBlocks() {
+        return blocks;
+    }
+
+    public final AbstractBlock<?> getBlockForId(int id) {
+        AbstractBlock<?> block = blocks.get(id);
+        assert block.getId() == id : "wrong block-to-id mapping";
+        return block;
+    }
+
+    /**
+     * Sets a flag for a block.
+     */
+    public final void set(E flag, AbstractBlock<?> block) {
+        BitSet bitSet = flags.get(flag);
+        if (bitSet == null) {
+            bitSet = new BitSet(blocks.size());
+            flags.put(flag, bitSet);
+        }
+        bitSet.set(block.getId());
+    }
+
+    /**
+     * Checks whether a flag is set for a block.
+     */
+    public final boolean get(E flag, AbstractBlock<?> block) {
+        BitSet bitSet = flags.get(flag);
+        return bitSet == null ? false : bitSet.get(block.getId());
+    }
+
+    /**
+     * Returns a {@linkplain Stream} of blocks for which {@code flag} is set.
+     */
+    public final Stream<? extends AbstractBlock<?>> stream(E flag) {
+        return getBlocks().stream().filter(block -> get(flag, block));
+    }
+
+    /**
+     * Returns the cost object associated with {@code block}. Might return {@code null} if not set.
+     */
+    public final C getCost(AbstractBlock<?> block) {
+        C cost = costs.get(block);
+        return cost;
+    }
+
+    /**
+     * Sets the cost for a {@code block}.
+     */
+    public final void setCost(AbstractBlock<?> block, C cost) {
+        costs.put(block, cost);
+    }
+
+    /**
+     * Sets {@code flag} for all blocks along the dominator path from {@code block} to the root
+     * until a block it finds a block where {@code flag} is already set.
+     */
+    public final void setDominatorPath(E flag, AbstractBlock<?> block) {
+        BitSet bitSet = flags.get(flag);
+        if (bitSet == null) {
+            bitSet = new BitSet(blocks.size());
+            flags.put(flag, bitSet);
+        }
+        for (AbstractBlock<?> b = block; b != null && !bitSet.get(b.getId()); b = b.getDominator()) {
+            // mark block
+            bitSet.set(b.getId());
+        }
+    }
+
+    /**
+     * Returns a {@link Stream} of flags associated with {@code block}.
+     */
+    public final Stream<E> getFlagsForBlock(AbstractBlock<?> block) {
+        return getFlags().stream().filter(flag -> get(flag, block));
+    }
+
+    /**
+     * Returns the {@link Set} of flags that can be set for this
+     * {@linkplain DominatorOptimizationProblem problem}.
+     */
+    public final Set<E> getFlags() {
+        return flags.keySet();
+    }
+
+    /**
+     * Returns the name of a flag.
+     */
+    public String getName(E flag) {
+        return flag.toString();
+    }
+}
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PrintableCFG.java	Mon Aug 25 17:18:36 2014 +0200
@@ -0,0 +1,45 @@
+/*
+ * Copyright (c) 2014, 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.compiler.common.cfg;
+
+import java.util.*;
+import java.util.function.*;
+
+/**
+ * Represents a control-flow graph where each node can be annotated with arbitrary property pairs of
+ * the form ({@linkplain String name}, {@linkplain String value}).
+ */
+public interface PrintableCFG {
+
+    List<? extends AbstractBlock<?>> getBlocks();
+
+    /**
+     * Applies {@code action} to all extra property pairs (name, value) of {@code block}.
+     *
+     * @param block a block from {@link #getBlocks()}.
+     * @param action a {@link BiConsumer consumer}.
+     */
+    default void forEachPropertyPair(AbstractBlock<?> block, BiConsumer<String, String> action) {
+        // no extra properties per default
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PrintableDominatorOptimizationProblem.java	Mon Aug 25 17:18:36 2014 +0200
@@ -0,0 +1,45 @@
+/*
+ * Copyright (c) 2014, 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.compiler.common.cfg;
+
+import java.util.function.*;
+
+/**
+ * A {@linkplain PrintableCFG printable} {@link DominatorOptimizationProblem}.
+ */
+public abstract class PrintableDominatorOptimizationProblem<E extends Enum<E>, C extends PropertyConsumable> extends DominatorOptimizationProblem<E, C> implements PrintableCFG {
+
+    protected PrintableDominatorOptimizationProblem(Class<E> keyType, AbstractControlFlowGraph<?> cfg) {
+        super(keyType, cfg);
+    }
+
+    public void forEachPropertyPair(AbstractBlock<?> block, BiConsumer<String, String> action) {
+        // for each flag
+        getFlags().forEach(flag -> ((BiConsumer<String, Boolean>) (name, value) -> action.accept(name, value ? "true" : "false")).accept(getName(flag), get(flag, block)));
+        // for each property
+        C cost = getCost(block);
+        if (cost != null) {
+            cost.forEachProperty((name, value) -> action.accept(name, value));
+        }
+    }
+}
\ No newline at end of file

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PropertyConsumable.java	Mon Aug 25 17:18:36 2014 +0200
@@ -0,0 +1,30 @@
+/*
+ * Copyright (c) 2014, 2014, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.compiler.common.cfg;
+
+import java.util.function.*;
+
+public interface PropertyConsumable {
+
+    void forEachProperty(BiConsumer<String, String> action);
+}