# HG changeset patch # User Josef Eisl # Date 1408979916 -7200 # Node ID 57da9b26a32766ea94240f7a5c8cc483a6829e8c # Parent 559ab93c1ad6fddc1ea3a52f26896a2a6b7db749 Introduce DominatorOptimizationProblem. diff -r 559ab93c1ad6 -r 57da9b26a327 graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/DominatorOptimizationProblem.java --- /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 An enum that describes the flags that can be associated with a block. + * @param 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, C> { + + private List> blocks; + private EnumMap flags; + private BlockMap costs; + + protected DominatorOptimizationProblem(Class flagType, AbstractControlFlowGraph cfg) { + this.blocks = cfg.getBlocks(); + flags = new EnumMap<>(flagType); + costs = new BlockMap<>(cfg); + assert verify(blocks); + } + + private static boolean verify(List> 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> 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> 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 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 getFlags() { + return flags.keySet(); + } + + /** + * Returns the name of a flag. + */ + public String getName(E flag) { + return flag.toString(); + } +} \ No newline at end of file diff -r 559ab93c1ad6 -r 57da9b26a327 graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PrintableCFG.java --- /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> 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 action) { + // no extra properties per default + } +} diff -r 559ab93c1ad6 -r 57da9b26a327 graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PrintableDominatorOptimizationProblem.java --- /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, C extends PropertyConsumable> extends DominatorOptimizationProblem implements PrintableCFG { + + protected PrintableDominatorOptimizationProblem(Class keyType, AbstractControlFlowGraph cfg) { + super(keyType, cfg); + } + + public void forEachPropertyPair(AbstractBlock block, BiConsumer action) { + // for each flag + getFlags().forEach(flag -> ((BiConsumer) (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 diff -r 559ab93c1ad6 -r 57da9b26a327 graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PropertyConsumable.java --- /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 action); +}