lir/constopt/ConstantTree.java

/*
 * 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 org.graalvm.compiler.lir.constopt;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.function.BiConsumer;
import java.util.function.Predicate;

import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
import org.graalvm.compiler.core.common.cfg.AbstractControlFlowGraph;
import org.graalvm.compiler.core.common.cfg.BlockMap;
import org.graalvm.compiler.core.common.cfg.PrintableDominatorOptimizationProblem;
import org.graalvm.compiler.core.common.cfg.PropertyConsumable;

/**
 * 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;
        }

        @Override
        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(AbstractBlockBase<?> block) {
        List<UseEntry> list = blockMap.get(block);
        if (list == null) {
            list = new ArrayList<>();
            blockMap.put(block, list);
        }
        return list;
    }

    public List<UseEntry> getUsages(AbstractBlockBase<?> 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(AbstractBlockBase<?> 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(AbstractBlockBase<?> 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 AbstractBlockBase<?> getStartBlock() {
        return stream(Flags.SUBTREE).findFirst().get();
    }

    public void markBlocks() {
        for (AbstractBlockBase<?> block : getBlocks()) {
            if (get(Flags.USAGE, block)) {
                setDominatorPath(Flags.SUBTREE, block);
            }
        }
    }

    public boolean isMarked(AbstractBlockBase<?> block) {
        return get(Flags.SUBTREE, block);
    }

    public boolean isLeafBlock(AbstractBlockBase<?> block) {
        for (AbstractBlockBase<?> dom : block.getDominated()) {
            if (isMarked(dom)) {
                return false;
            }
        }
        return true;
    }

    public void setSolution(AbstractBlockBase<?> block) {
        set(Flags.MATERIALIZE, block);
    }

    public int size() {
        return getBlocks().length;
    }

    public void traverseTreeWhileTrue(AbstractBlockBase<?> block, Predicate<AbstractBlockBase<?>> action) {
        assert block != null : "block must not be null!";
        if (action.test(block)) {
            block.getDominated().stream().filter(this::isMarked).forEach(dominated -> traverseTreeWhileTrue(dominated, action));
        }
    }

}