Mercurial > hg > graal-jvmci-8
changeset 16951:57da9b26a327
Introduce DominatorOptimizationProblem.
author | Josef Eisl <josef.eisl@jku.at> |
---|---|
date | Mon, 25 Aug 2014 17:18:36 +0200 |
parents | 559ab93c1ad6 |
children | 2451521ed26f |
files | graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/DominatorOptimizationProblem.java graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PrintableCFG.java graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PrintableDominatorOptimizationProblem.java graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/PropertyConsumable.java |
diffstat | 4 files changed, 270 insertions(+), 0 deletions(-) [+] |
line wrap: on
line diff
--- /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); +}