--- 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();

--- /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<Boolean> 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<DefUseTree> map;
+    private BitSet phiConstants;
+    private BitSet defined;
+    private BlockMap<List<UseEntry>> blockMap;
+    private BlockMap<LIRInsertionBuffer> 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<UseEntry> 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<UseEntry> getUsages(AbstractBlock<?> block, Variable variable) {
+        List<UseEntry> 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<AbstractBlock<?>> 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<LIRInstruction> 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<UseEntry> 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<LIRInstruction> instructions = lir.getLIRforBlock(block);
+            insertionBuffer.init(instructions);
+        }
+        return insertionBuffer;
+    }
+}

--- /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<ConstantTree.Flags, ConstantTree.NodeCost> {
+
+    public enum Flags {
+        SUBTREE,
+        USAGE,
+        MATERIALIZE,
+        CANDIDATE,
+    }
+
+    /**
+     * Costs associated with a block.
+     */
+    public static class NodeCost implements PropertyConsumable {
+        private List<UseEntry> usages;
+        private double bestCost;
+        private int numMat;
+
+        public NodeCost(double bestCost, List<UseEntry> usages, int numMat) {
+            this.bestCost = bestCost;
+            this.usages = usages;
+            this.numMat = numMat;
+        }
+
+        public void forEachProperty(BiConsumer<String, String> 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<UseEntry> 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<List<UseEntry>> 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<UseEntry> getOrInitList(AbstractBlock<?> block) {
+        List<UseEntry> list = blockMap.get(block);
+        if (list == null) {
+            list = new ArrayList<>();
+            blockMap.put(block, list);
+        }
+        return list;
+    }
+
+    public List<UseEntry> getUsages(AbstractBlock<?> block) {
+        List<UseEntry> 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<String, String> 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<AbstractBlock<?>> action) {
+        assert block != null : "block must not be null!";
+        if (action.test(block)) {
+            block.getDominated().stream().filter(this::isMarked).forEach(dominated -> traverseTreeWhileTrue(dominated, action));
+        }
+    }
+
+}

--- /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<AbstractBlock<?>> 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<? extends AbstractBlock<?>> 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<UseEntry> usages = new ArrayList<>();
+        double bestCost = 0;
+        int numMat = 0;
+        List<? extends AbstractBlock<?>> 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<UseEntry> 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.
+     * <p>
+     * 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<AbstractBlock<?>> 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);
+    }
+
+}

--- /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<UseEntry> 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<? super UseEntry> action) {
+        uses.forEach(action);
+    }
+
+}
\ No newline at end of file

--- /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

--- /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<T> {
+
+    private final ArrayList<T> 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<T> action) {
+        for (T e : content) {
+            if (e != null) {
+                action.accept(e);
+            }
+        }
+    }
+
+    /**
+     * Keeps only keys which match the given predicate.
+     */
+    public void filter(Predicate<T> 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

--- 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