# HG changeset patch # User Josef Eisl # Date 1408980194 -7200 # Node ID 2451521ed26fc7b9d1b610071e78d7ae9b0aed3b # Parent 57da9b26a32766ea94240f7a5c8cc483a6829e8c Add ConstantLoadOptimization. diff -r 57da9b26a327 -r 2451521ed26f graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java --- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon Aug 25 17:18:36 2014 +0200 +++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java Mon Aug 25 17:23:14 2014 +0200 @@ -41,6 +41,7 @@ import com.oracle.graal.debug.internal.*; import com.oracle.graal.lir.*; import com.oracle.graal.lir.asm.*; +import com.oracle.graal.lir.constopt.*; import com.oracle.graal.lir.gen.*; import com.oracle.graal.nodes.*; import com.oracle.graal.nodes.cfg.*; @@ -256,6 +257,15 @@ throw Debug.handle(e); } + if (ConstantLoadOptimization.Options.ConstantLoadOptimization.getValue()) { + try (Scope s = Debug.scope("ConstantLoadOptimization", lir)) { + ConstantLoadOptimization.optimize(lirGenRes.getLIR(), lirGen); + Debug.dump(lir, "After constant load optimization"); + } catch (Throwable e) { + throw Debug.handle(e); + } + } + try (Scope s = Debug.scope("Allocator", nodeLirGen)) { if (backend.shouldAllocateRegisters()) { new LinearScan(target, lir, frameMap).allocate(); diff -r 57da9b26a327 -r 2451521ed26f graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/ConstantLoadOptimization.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/ConstantLoadOptimization.java Mon Aug 25 17:23:14 2014 +0200 @@ -0,0 +1,330 @@ +/* + * 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.lir.constopt; + +import static com.oracle.graal.api.code.ValueUtil.*; +import static com.oracle.graal.lir.LIRValueUtil.*; + +import java.util.*; +import java.util.stream.*; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.MoveOp; +import com.oracle.graal.lir.constopt.ConstantTree.Flags; +import com.oracle.graal.lir.constopt.ConstantTree.NodeCost; +import com.oracle.graal.lir.gen.*; +import com.oracle.graal.options.*; + +/** + * This optimization tries to improve the handling of constants by replacing a single definition of + * a constant, which is potentially scheduled into a block with high probability, with one or more + * definitions in blocks with a lower probability. + */ +public class ConstantLoadOptimization { + + public static class Options { + // @formatter:off + @Option(help = "Enable constant load optimization.") + public static final OptionValue ConstantLoadOptimization = new OptionValue<>(true); + // @formatter:on + } + + public static void optimize(LIR lir, LIRGeneratorTool lirGen) { + new ConstantLoadOptimization(lir, lirGen).apply(); + } + + private LIR lir; + private LIRGeneratorTool lirGen; + private VariableMap map; + private BitSet phiConstants; + private BitSet defined; + private BlockMap> blockMap; + private BlockMap insertionBuffers; + + private static DebugMetric constantsTotal = Debug.metric("ConstantLoadOptimization[total]"); + private static DebugMetric phiConstantsSkipped = Debug.metric("ConstantLoadOptimization[PhisSkipped]"); + private static DebugMetric singleUsageConstantsSkipped = Debug.metric("ConstantLoadOptimization[SingleUsageSkipped]"); + private static DebugMetric usageAtDefinitionSkipped = Debug.metric("ConstantLoadOptimization[UsageAtDefinitionSkipped]"); + private static DebugMetric materializeAtDefinitionSkipped = Debug.metric("ConstantLoadOptimization[MaterializeAtDefinitionSkipped]"); + private static DebugMetric constantsOptimized = Debug.metric("ConstantLoadOptimization[optimized]"); + + private ConstantLoadOptimization(LIR lir, LIRGeneratorTool lirGen) { + this.lir = lir; + this.lirGen = lirGen; + this.map = new VariableMap<>(); + this.phiConstants = new BitSet(); + this.defined = new BitSet(); + this.insertionBuffers = new BlockMap<>(lir.getControlFlowGraph()); + this.blockMap = new BlockMap<>(lir.getControlFlowGraph()); + } + + private void apply() { + try (Indent indent = Debug.logAndIndent("ConstantLoadOptimization")) { + try (Scope s = Debug.scope("BuildDefUseTree")) { + // build DefUseTree + lir.getControlFlowGraph().getBlocks().forEach(this::processBlock); + // remove all with only one use + map.filter(t -> { + if (t.usageCount() > 1) { + return true; + } else { + singleUsageConstantsSkipped.increment(); + return false; + } + }); + // collect block map + map.forEach(tree -> tree.forEach(this::addUsageToBlockMap)); + } catch (Throwable e) { + throw Debug.handle(e); + } + + try (Scope s = Debug.scope("BuildConstantTree")) { + // create ConstantTree + map.forEach(this::createConstantTree); + + // insert moves, delete null instructions and reset instruction ids + lir.getControlFlowGraph().getBlocks().forEach(this::rewriteBlock); + } catch (Throwable e) { + throw Debug.handle(e); + } + } + } + + public void print() { + map.forEach(t -> Debug.log(1, "%s", t)); + } + + private static boolean isConstantLoad(LIRInstruction inst) { + if (!(inst instanceof MoveOp)) { + return false; + } + MoveOp move = (MoveOp) inst; + return isConstant(move.getInput()) && isVariable(move.getResult()); + } + + private void addUsageToBlockMap(UseEntry entry) { + AbstractBlock block = entry.getBlock(); + List list = blockMap.get(block); + if (list == null) { + list = new ArrayList<>(); + blockMap.put(block, list); + } + list.add(entry); + } + + private void processBlock(AbstractBlock block) { + try (Indent indent = Debug.logAndIndent("Block: %s", block)) { + + InstructionValueConsumer loadConsumer = new InstructionValueConsumer() { + @Override + public void visitValue(LIRInstruction instruction, Value value) { + if (isVariable(value)) { + Variable var = (Variable) value; + + if (!phiConstants.get(var.index)) { + if (!defined.get(var.index)) { + defined.set(var.index); + if (isConstantLoad(instruction)) { + Debug.log("constant load: %s", instruction); + map.put(var, new DefUseTree(instruction, block)); + constantsTotal.increment(); + } + } else { + // Variable is redefined, this only happens for constant loads + // introduced by phi resolution -> ignore. + DefUseTree removed = map.remove(var); + if (removed != null) { + phiConstantsSkipped.increment(); + } + phiConstants.set(var.index); + Debug.log(3, "Removing phi variable: %s", var); + } + } else { + assert defined.get(var.index) : "phi but not defined? " + var; + } + + } + } + + }; + + ValuePositionProcedure useProcedure = new ValuePositionProcedure() { + @Override + public void doValue(LIRInstruction instruction, ValuePosition position) { + Value value = position.get(instruction); + if (isVariable(value)) { + Variable var = (Variable) value; + if (!phiConstants.get(var.index)) { + DefUseTree tree = map.get(var); + if (tree != null) { + tree.addUsage(block, instruction, position); + Debug.log("usage of %s : %s", var, instruction); + } + } + } + } + + }; + + int opId = 0; + for (LIRInstruction inst : lir.getLIRforBlock(block)) { + // set instruction id to the index in the lir instruction list + inst.setId(opId++); + inst.visitEachOutput(loadConsumer); + inst.forEachInput(useProcedure); + inst.forEachAlive(useProcedure); + + } + } + } + + public List getUsages(AbstractBlock block, Variable variable) { + List list = blockMap.get(block); + return list == null ? Collections.emptyList() : list.stream().filter(u -> u.getValue().equals(variable)).collect(Collectors.toList()); + } + + private void createConstantTree(DefUseTree tree) { + ConstantTree constTree = new ConstantTree(lir.getControlFlowGraph(), tree); + constTree.set(Flags.SUBTREE, tree.getBlock()); + tree.forEach(u -> constTree.set(Flags.USAGE, u.getBlock())); + + if (constTree.get(Flags.USAGE, tree.getBlock())) { + // usage in the definition block -> no optimization + usageAtDefinitionSkipped.increment(); + return; + } + + constTree.markBlocks(); + + NodeCost cost = ConstantTreeAnalyzer.analyze(constTree, tree.getBlock()); + int usageCount = cost.getUsages().size(); + assert usageCount == tree.usageCount() : "Usage count differs: " + usageCount + " vs. " + tree.usageCount(); + + if (Debug.isLogEnabled(1)) { + try (Indent i = Debug.logAndIndent(1, "Variable: %s, Block: %s, prob.: %f", tree.getVariable(), tree.getBlock(), tree.getBlock().probability())) { + Debug.log(1, "Usages result: %s", cost); + } + + } + + if (cost.getNumMaterializations() > 1 || cost.getBestCost() < tree.getBlock().probability()) { + try (Scope s = Debug.scope("CLOmodify", constTree); Indent i = Debug.logAndIndent("Replacing %s = %s", tree.getVariable(), tree.getConstant().toValueString())) { + // mark original load for removal + deleteInstruction(tree); + constantsOptimized.increment(); + + // collect result + createLoads(tree, constTree, tree.getBlock()); + + } catch (Throwable e) { + throw Debug.handle(e); + } + } else { + // no better solution found + materializeAtDefinitionSkipped.increment(); + } + Debug.dump(constTree, "ConstantTree for " + tree.getVariable()); + } + + private void createLoads(DefUseTree tree, ConstantTree constTree, AbstractBlock startBlock) { + Deque> worklist = new ArrayDeque<>(); + worklist.add(startBlock); + while (!worklist.isEmpty()) { + AbstractBlock block = worklist.pollLast(); + if (constTree.get(Flags.CANDIDATE, block)) { + constTree.set(Flags.MATERIALIZE, block); + // create and insert load + insertLoad(tree.getConstant(), tree.getVariable().getLIRKind(), block, constTree.getCost(block).getUsages()); + } else { + for (AbstractBlock dominated : block.getDominated()) { + if (constTree.isMarked(dominated)) { + worklist.addLast(dominated); + } + } + } + } + } + + private void rewriteBlock(AbstractBlock block) { + // insert moves + LIRInsertionBuffer buffer = insertionBuffers.get(block); + if (buffer != null) { + assert buffer.initialized() : "not initialized?"; + buffer.finish(); + } + + // delete instructions + List instructions = lir.getLIRforBlock(block); + boolean hasDead = false; + for (LIRInstruction inst : instructions) { + if (inst == null) { + hasDead = true; + } else { + inst.setId(-1); + } + } + if (hasDead) { + // Remove null values from the list. + instructions.removeAll(Collections.singleton(null)); + } + } + + private void deleteInstruction(DefUseTree tree) { + AbstractBlock block = tree.getBlock(); + LIRInstruction instruction = tree.getInstruction(); + Debug.log("deleting instruction %s from block %s", instruction, block); + lir.getLIRforBlock(block).set(instruction.id(), null); + } + + private void insertLoad(Constant constant, LIRKind kind, AbstractBlock block, List usages) { + assert usages != null && usages.size() > 0 : String.format("No usages %s %s %s", constant, block, usages); + // create variable + Variable variable = lirGen.newVariable(kind); + // create move + LIRInstruction move = lir.getSpillMoveFactory().createMove(variable, constant); + // insert instruction + getInsertionBuffer(block).append(1, move); + Debug.log("new move (%s) and inserted in block %s", move, block); + // update usages + for (UseEntry u : usages) { + u.getPosition().set(u.getInstruction(), variable); + Debug.log("patched instruction %s", u.getInstruction()); + } + } + + private LIRInsertionBuffer getInsertionBuffer(AbstractBlock block) { + LIRInsertionBuffer insertionBuffer = insertionBuffers.get(block); + if (insertionBuffer == null) { + insertionBuffer = new LIRInsertionBuffer(); + insertionBuffers.put(block, insertionBuffer); + assert !insertionBuffer.initialized() : "already initialized?"; + List instructions = lir.getLIRforBlock(block); + insertionBuffer.init(instructions); + } + return insertionBuffer; + } +} diff -r 57da9b26a327 -r 2451521ed26f graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/ConstantTree.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/ConstantTree.java Mon Aug 25 17:23:14 2014 +0200 @@ -0,0 +1,190 @@ +/* + * 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.lir.constopt; + +import java.util.*; +import java.util.function.*; + +import com.oracle.graal.compiler.common.cfg.*; + +/** + * Represents a dominator (sub-)tree for a constant definition. + */ +public class ConstantTree extends PrintableDominatorOptimizationProblem { + + public enum Flags { + SUBTREE, + USAGE, + MATERIALIZE, + CANDIDATE, + } + + /** + * Costs associated with a block. + */ + public static class NodeCost implements PropertyConsumable { + private List usages; + private double bestCost; + private int numMat; + + public NodeCost(double bestCost, List usages, int numMat) { + this.bestCost = bestCost; + this.usages = usages; + this.numMat = numMat; + } + + public void forEachProperty(BiConsumer action) { + action.accept("bestCost", Double.toString(getBestCost())); + action.accept("numMat", Integer.toString(getNumMaterializations())); + action.accept("numUsages", Integer.toString(usages.size())); + } + + public void addUsage(UseEntry usage) { + if (usages == null) { + usages = new ArrayList<>(); + } + usages.add(usage); + } + + public List getUsages() { + if (usages == null) { + Collections.emptyList(); + } + return usages; + } + + public double getBestCost() { + return bestCost; + } + + public int getNumMaterializations() { + return numMat; + } + + public void setBestCost(double cost) { + bestCost = cost; + } + + @Override + public String toString() { + return "NodeCost [bestCost=" + bestCost + ", numUsages=" + usages.size() + ", numMat=" + numMat + "]"; + } + } + + private final BlockMap> blockMap; + + public ConstantTree(AbstractControlFlowGraph cfg, DefUseTree tree) { + super(Flags.class, cfg); + this.blockMap = new BlockMap<>(cfg); + tree.forEach(u -> getOrInitList(u.getBlock()).add(u)); + } + + private List getOrInitList(AbstractBlock block) { + List list = blockMap.get(block); + if (list == null) { + list = new ArrayList<>(); + blockMap.put(block, list); + } + return list; + } + + public List getUsages(AbstractBlock block) { + List list = blockMap.get(block); + if (list == null) { + return Collections.emptyList(); + } + return Collections.unmodifiableList(list); + } + + /** + * Returns the cost object associated with {@code block}. If there is none, a new cost object is + * created. + */ + NodeCost getOrInitCost(AbstractBlock block) { + NodeCost cost = getCost(block); + if (cost == null) { + cost = new NodeCost(block.probability(), blockMap.get(block), 1); + setCost(block, cost); + } + return cost; + } + + @Override + public String getName(Flags type) { + switch (type) { + case USAGE: + return "hasUsage"; + case SUBTREE: + return "inSubtree"; + case MATERIALIZE: + return "materialize"; + case CANDIDATE: + return "candidate"; + } + return super.getName(type); + } + + @Override + public void forEachPropertyPair(AbstractBlock block, BiConsumer action) { + if (get(Flags.SUBTREE, block) && (block.getDominator() == null || !get(Flags.SUBTREE, block.getDominator()))) { + action.accept("hasDefinition", "true"); + } + super.forEachPropertyPair(block, action); + } + + public long subTreeSize() { + return stream(Flags.SUBTREE).count(); + } + + public AbstractBlock getStartBlock() { + return stream(Flags.SUBTREE).findFirst().get(); + } + + public void markBlocks() { + stream(Flags.USAGE).forEach(block -> setDominatorPath(Flags.SUBTREE, block)); + } + + public boolean isMarked(AbstractBlock block) { + return get(Flags.SUBTREE, block); + } + + public boolean isLeafBlock(AbstractBlock block) { + return block.getDominated().stream().noneMatch(this::isMarked); + } + + public void setSolution(AbstractBlock block) { + set(Flags.MATERIALIZE, block); + } + + public int size() { + return getBlocks().size(); + } + + public void traverseTreeWhileTrue(AbstractBlock block, Predicate> action) { + assert block != null : "block must not be null!"; + if (action.test(block)) { + block.getDominated().stream().filter(this::isMarked).forEach(dominated -> traverseTreeWhileTrue(dominated, action)); + } + } + +} diff -r 57da9b26a327 -r 2451521ed26f graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/ConstantTreeAnalyzer.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/ConstantTreeAnalyzer.java Mon Aug 25 17:23:14 2014 +0200 @@ -0,0 +1,174 @@ +/* + * 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.lir.constopt; + +import java.util.*; + +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.debug.*; +import com.oracle.graal.debug.Debug.Scope; +import com.oracle.graal.lir.constopt.ConstantTree.Flags; +import com.oracle.graal.lir.constopt.ConstantTree.NodeCost; + +/** + * Analyzes a {@link ConstantTree} and marks potential materialization positions. + */ +public class ConstantTreeAnalyzer { + private final ConstantTree tree; + private final BitSet visited; + + public static NodeCost analyze(ConstantTree tree, AbstractBlock startBlock) { + try (Scope s = Debug.scope("ConstantTreeAnalyzer")) { + ConstantTreeAnalyzer analyzer = new ConstantTreeAnalyzer(tree); + analyzer.analyzeBlocks(startBlock); + return tree.getCost(startBlock); + } catch (Throwable e) { + throw Debug.handle(e); + } + } + + private ConstantTreeAnalyzer(ConstantTree tree) { + this.tree = tree; + this.visited = new BitSet(tree.size()); + } + + /** + * Queues all relevant blocks for {@linkplain #process processing}. + * + * This is a worklist-style algorithm because a (more elegant) recursive implementation may + * cause {@linkplain StackOverflowError stack overflows} on larger graphs. + * + * @param startBlock The start block of the dominator subtree. + */ + private void analyzeBlocks(AbstractBlock startBlock) { + Deque> worklist = new ArrayDeque<>(); + worklist.offerLast(startBlock); + while (!worklist.isEmpty()) { + AbstractBlock block = worklist.pollLast(); + try (Indent i = Debug.logAndIndent(3, "analyze: %s", block)) { + assert block != null : "worklist is empty!"; + assert isMarked(block) : "Block not part of the dominator tree: " + block; + + if (isLeafBlock(block)) { + Debug.log(3, "leaf block"); + leafCost(block); + continue; + } + + if (!visited.get(block.getId())) { + // if not yet visited (and not a leaf block) process all children first! + Debug.log(3, "not marked"); + worklist.offerLast(block); + List> children = block.getDominated(); + children.forEach(child -> filteredPush(worklist, child)); + visited.set(block.getId()); + } else { + Debug.log(3, "marked"); + // otherwise, process block + process(block); + } + } + } + } + + /** + * Calculates the cost of a {@code block}. It is assumed that all {@code children} have already + * been {@linkplain #process processed} + * + * @param block The block to be processed. + */ + private void process(AbstractBlock block) { + List usages = new ArrayList<>(); + double bestCost = 0; + int numMat = 0; + List> children = block.getDominated(); + assert children.stream().anyMatch(this::isMarked) : "no children? should have called leafCost(): " + block; + + // collect children costs + for (AbstractBlock child : children) { + if (isMarked(child)) { + NodeCost childCost = tree.getCost(child); + assert childCost != null : "Child with null cost? block: " + child; + usages.addAll(childCost.getUsages()); + numMat += childCost.getNumMaterializations(); + bestCost += childCost.getBestCost(); + } + } + assert numMat > 0 : "No materialization? " + numMat; + + // choose block + List usagesBlock = tree.getUsages(block); + double probabilityBlock = block.probability(); + + if (!usagesBlock.isEmpty() || shouldMaterializerInCurrentBlock(probabilityBlock, bestCost, numMat)) { + // mark current block as potential materialization position + usages.addAll(usagesBlock); + bestCost = probabilityBlock; + numMat = 1; + tree.set(Flags.CANDIDATE, block); + } else { + // stick with the current solution + } + + assert (new HashSet<>(usages)).size() == usages.size() : "doulbe entries? " + usages; + NodeCost nodeCost = new NodeCost(bestCost, usages, numMat); + tree.setCost(block, nodeCost); + } + + /** + * This is the cost function that decides whether a materialization should be inserted in the + * current block. + *

+ * Note that this function does not take into account if a materialization is required despite + * the probabilities (e.g. there are usages in the current block). + * + * @param probabilityBlock Probability of the current block. + * @param probabilityChildren Accumulated probability of the children. + * @param numMat Number of materializations along the subtrees. We use {@code numMat - 1} to + * insert materializations as late as possible if the probabilities are the same. + */ + private static boolean shouldMaterializerInCurrentBlock(double probabilityBlock, double probabilityChildren, int numMat) { + return probabilityBlock * Math.pow(0.9, numMat - 1) < probabilityChildren; + } + + private void filteredPush(Deque> worklist, AbstractBlock block) { + if (isMarked(block)) { + Debug.log(3, "adding %s to the worklist", block); + worklist.offerLast(block); + } + } + + private void leafCost(AbstractBlock block) { + tree.set(Flags.CANDIDATE, block); + tree.getOrInitCost(block); + } + + private boolean isMarked(AbstractBlock block) { + return tree.isMarked(block); + } + + private boolean isLeafBlock(AbstractBlock block) { + return tree.isLeafBlock(block); + } + +} diff -r 57da9b26a327 -r 2451521ed26f graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/DefUseTree.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/DefUseTree.java Mon Aug 25 17:23:14 2014 +0200 @@ -0,0 +1,81 @@ +/* + * 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.lir.constopt; + +import java.util.*; +import java.util.function.*; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.*; +import com.oracle.graal.lir.StandardOp.MoveOp; + +/** + * Represents def-use tree of a constant. + */ +class DefUseTree { + private final LIRInstruction instruction; + private final AbstractBlock block; + private final List uses; + + public DefUseTree(LIRInstruction instruction, AbstractBlock block) { + assert instruction instanceof MoveOp : "Not a MoveOp: " + instruction; + this.instruction = instruction; + this.block = block; + this.uses = new ArrayList<>(); + } + + public Variable getVariable() { + return (Variable) ((MoveOp) instruction).getResult(); + } + + public Constant getConstant() { + return (Constant) ((MoveOp) instruction).getInput(); + } + + public LIRInstruction getInstruction() { + return instruction; + } + + public AbstractBlock getBlock() { + return block; + } + + @Override + public String toString() { + return "DefUseTree [" + instruction + "|" + block + "," + uses + "]"; + } + + public void addUsage(AbstractBlock b, LIRInstruction inst, ValuePosition position) { + uses.add(new UseEntry(b, inst, position)); + } + + public int usageCount() { + return uses.size(); + } + + public void forEach(Consumer action) { + uses.forEach(action); + } + +} \ No newline at end of file diff -r 57da9b26a327 -r 2451521ed26f graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/UseEntry.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/UseEntry.java Mon Aug 25 17:23:14 2014 +0200 @@ -0,0 +1,64 @@ +/* + * 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.lir.constopt; + +import com.oracle.graal.api.meta.*; +import com.oracle.graal.compiler.common.cfg.*; +import com.oracle.graal.lir.*; + +/** + * Represents a usage of a constant. + */ +class UseEntry { + + private final AbstractBlock block; + private final LIRInstruction instruction; + private final ValuePosition position; + + public UseEntry(AbstractBlock block, LIRInstruction instruction, ValuePosition position) { + this.block = block; + this.instruction = instruction; + this.position = position; + } + + public LIRInstruction getInstruction() { + return instruction; + } + + public AbstractBlock getBlock() { + return block; + } + + public ValuePosition getPosition() { + return position; + } + + public Value getValue() { + return position.get(instruction); + } + + @Override + public String toString() { + return "Use[" + getValue() + ":" + instruction + ":" + block + "]"; + } +} \ No newline at end of file diff -r 57da9b26a327 -r 2451521ed26f graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/VariableMap.java --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.lir/src/com/oracle/graal/lir/constopt/VariableMap.java Mon Aug 25 17:23:14 2014 +0200 @@ -0,0 +1,87 @@ +/* + * 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.lir.constopt; + +import java.util.*; +import java.util.function.*; + +import com.oracle.graal.lir.*; + +/** + * Maps variables to a generic type. + * + * TODO (je) evaluate data structure + */ +class VariableMap { + + private final ArrayList content; + + public VariableMap() { + content = new ArrayList<>(); + } + + public T get(Variable key) { + if (key == null || key.index >= content.size()) { + return null; + } + return content.get(key.index); + } + + public T put(Variable key, T value) { + assert key != null : "Key cannot be null"; + assert value != null : "Value cannot be null"; + while (key.index >= content.size()) { + content.add(null); + } + return content.set(key.index, value); + } + + public T remove(Variable key) { + assert key != null : "Key cannot be null"; + if (key.index >= content.size()) { + return null; + } + return content.set(key.index, null); + } + + public void forEach(Consumer action) { + for (T e : content) { + if (e != null) { + action.accept(e); + } + } + } + + /** + * Keeps only keys which match the given predicate. + */ + public void filter(Predicate predicate) { + for (int i = 0; i < content.size(); i++) { + T e = content.get(i); + if (e != null && !predicate.test(e)) { + content.set(i, null); + } + } + } + +} \ No newline at end of file diff -r 57da9b26a327 -r 2451521ed26f mx/projects --- a/mx/projects Mon Aug 25 17:18:36 2014 +0200 +++ b/mx/projects Mon Aug 25 17:23:14 2014 +0200 @@ -390,7 +390,7 @@ # graal.lir project@com.oracle.graal.lir@subDir=graal project@com.oracle.graal.lir@sourceDirs=src -project@com.oracle.graal.lir@dependencies=com.oracle.graal.debug,com.oracle.graal.compiler.common,com.oracle.graal.asm +project@com.oracle.graal.lir@dependencies=com.oracle.graal.compiler.common,com.oracle.graal.asm,com.oracle.graal.debug project@com.oracle.graal.lir@checkstyle=com.oracle.graal.graph project@com.oracle.graal.lir@javaCompliance=1.8 project@com.oracle.graal.lir@workingSets=Graal,LIR