/*
 * Copyright (c) 2011, 2011, 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.max.graal.compiler.schedule;

import java.util.*;

import com.oracle.max.cri.ci.*;
import com.oracle.max.criutils.*;
import com.oracle.max.graal.compiler.*;
import com.oracle.max.graal.compiler.phases.*;
import com.oracle.max.graal.compiler.util.*;
import com.oracle.max.graal.graph.*;
import com.oracle.max.graal.graph.Node.Verbosity;
import com.oracle.max.graal.nodes.*;
import com.oracle.max.graal.nodes.extended.*;
import com.oracle.max.graal.nodes.virtual.*;


public class IdentifyBlocksPhase extends Phase {

    public static class BlockFactory {
        public Block createBlock(int blockID) {
            return new Block(blockID);
        }
    }

    private final BlockFactory blockFactory;
    private final List<Block> blocks = new ArrayList<>();
    private NodeMap<Block> nodeToBlock;
    private NodeMap<Block> earliestCache;
    private Block startBlock;
    private boolean scheduleAllNodes;
    private int loopCount;

    public IdentifyBlocksPhase(boolean scheduleAllNodes) {
        this(scheduleAllNodes, new BlockFactory());
    }

    public IdentifyBlocksPhase(boolean scheduleAllNodes, BlockFactory blockFactory) {
        super(scheduleAllNodes ? "FullSchedule" : "PartSchedule", false);
        this.blockFactory = blockFactory;
        this.scheduleAllNodes = scheduleAllNodes;
    }

    public void calculateAlwaysReachedBlock() {
        for (Block b : blocks) {
            calculateAlwaysReachedBlock(b);
        }
    }


    private void calculateAlwaysReachedBlock(Block b) {
        if (b.getSuccessors().size() == 1) {
            b.setAlwaysReachedBlock(b.getSuccessors().get(0));
        } else if (b.getSuccessors().size() > 1) {
            BitMap blockBitMap = new BitMap(blocks.size());
            List<Block> visitedBlocks = new ArrayList<>();

            // Do a fill starting at the dominated blocks and going upwards over predecessors.
            for (Block dominated : b.getDominated()) {
                for (Block pred : dominated.getPredecessors()) {
                    blockFill(blockBitMap, pred, b, visitedBlocks);
                }
            }

            boolean ok = true;

            // Find out if there is exactly 1 dominated block that is left unmarked (this is the potential merge block that is always reached).
            Block unmarkedDominated = null;
            for (Block dominated : b.getDominated()) {
                if (!blockBitMap.get(dominated.blockID())) {
                    if (unmarkedDominated != null) {
                        ok = false;
                        break;
                    }
                    unmarkedDominated = dominated;
                }
            }

            if (ok) {
                // Check that there is no exit possible except for exception edges.
                for (Block visitedBlock : visitedBlocks) {
                    assert blockBitMap.get(visitedBlock.blockID());
                    for (Block succ : visitedBlock.getSuccessors()) {
                        if (succ != unmarkedDominated && !succ.isExceptionBlock() && !blockBitMap.get(succ.blockID())) {
                            ok = false;
                            break;
                        }
                    }

                    if (!ok) {
                        break;
                    }
                }
            }

            if (ok) {
                assert unmarkedDominated != null;
                b.setAlwaysReachedBlock(unmarkedDominated);
            }
        }
    }

    private void blockFill(BitMap blockBitMap, Block cur, Block stop, List<Block> visitedBlocks) {
        if (blockBitMap.get(cur.blockID())) {
            return;
        }

        blockBitMap.set(cur.blockID());
        visitedBlocks.add(cur);

        if (cur != stop) {
            for (Block pred : cur.getPredecessors()) {
                blockFill(blockBitMap, pred, stop, visitedBlocks);
            }
        }
    }

    @Override
    protected void run(StructuredGraph graph) {
        nodeToBlock = graph.createNodeMap();
        earliestCache = graph.createNodeMap();
        identifyBlocks(graph);
    }

    public Block getStartBlock() {
        return startBlock;
    }

    public List<Block> getBlocks() {
        return Collections.unmodifiableList(blocks);
    }

    public NodeMap<Block> getNodeToBlock() {
        return nodeToBlock;
    }

    private Block createBlock() {
        Block b = blockFactory.createBlock(blocks.size());
        blocks.add(b);
        return b;
    }

    public int loopCount() {
        return loopCount;
    }

    private Block assignBlockNew(Node n, Block block, StructuredGraph graph) {
        Block b = block;
        if (b == null) {
            b = createBlock();
        }

        assert nodeToBlock.get(n) == null;
        nodeToBlock.set(n, b);

        if (n == graph.start()) {
            startBlock = b;
        }

        if (n instanceof MergeNode) {
            for (PhiNode phi : ((MergeNode) n).phis()) {
                nodeToBlock.set(phi, b);
            }
        }
        if (n instanceof EndNode) {
            assert b.end() == null || n == b.end();
            b.setEnd((EndNode) n);
        }
        if (b.lastNode() == null) {
            b.setFirstNode(n);
            b.setLastNode(n);
            b.getInstructions().add(n);
        } else {
            b.getInstructions().add(0, n);
            b.setFirstNode(n);
        }

        return b;
    }

    public static boolean isBlockEnd(Node n) {
        return trueSuccessorCount(n) > 1 || n instanceof ReturnNode || n instanceof UnwindNode || n instanceof DeoptimizeNode;
    }

    private void identifyBlocks(StructuredGraph graph) {

        // Identify blocks.
        for (Node n : graph.getNodes()) {
            if (n instanceof EndNode || n instanceof ReturnNode || n instanceof UnwindNode || n instanceof LoopEndNode || n instanceof DeoptimizeNode) {
                Block block = null;
                Node currentNode = n;
                Node prev = null;
                while (nodeToBlock.get(currentNode) == null) {
                    block = assignBlockNew(currentNode, block, graph);
                    if (currentNode instanceof FixedNode) {
                        block.setProbability(((FixedNode) currentNode).probability());
                    }
                    if (currentNode.predecessor() == null) {
                        // At a merge node => stop iteration.
                        assert currentNode instanceof MergeNode || currentNode == ((StructuredGraph) currentNode.graph()).start() : currentNode;
                        break;
                    }
                    if (block != null && currentNode instanceof BeginNode) {
                        // We are at a split node => start a new block.
                        block = null;
                    }
                    prev = currentNode;
                    currentNode = currentNode.predecessor();
                    // FIX(ls) what's the meaning of this assert?
//                    assert !(currentNode instanceof AccessNode && ((AccessNode) currentNode).next() != prev) : currentNode;
                    assert !currentNode.isDeleted() : prev + " " + currentNode;
                }
            }
        }

        // Connect blocks.
        for (Block block : blocks) {
            Node n = block.firstNode();
            if (n instanceof MergeNode) {
                MergeNode m = (MergeNode) n;
                for (Node pred : m.cfgPredecessors()) {
                    Block predBlock = nodeToBlock.get(pred);
                    predBlock.addSuccessor(block);
                }
            } else {
                if (n.predecessor() != null) {
                    if (Util.isFixed(n.predecessor())) {
                        Block predBlock = nodeToBlock.get(n.predecessor());
                        predBlock.addSuccessor(block);
                    }
                }
            }
        }

        computeDominators(graph);

        if (scheduleAllNodes) {
            computeLoopInformation(); // Will make the graph cyclic.
            assignBlockToNodes(graph);
            sortNodesWithinBlocks(graph);
        }
    }

    private void computeLoopInformation() {
        // Add successors of loop end nodes. Makes the graph cyclic.
        for (Block block : blocks) {
            Node n = block.lastNode();
            if (n instanceof LoopEndNode) {
                LoopEndNode loopEnd = (LoopEndNode) n;
                assert loopEnd.loopBegin() != null;
                Block loopBeginBlock = nodeToBlock.get(loopEnd.loopBegin());
                block.addSuccessor(loopBeginBlock);
                BitMap map = new BitMap(blocks.size());
                loopBeginBlock.loopBlocks = new ArrayList<>();
                markBlocks(block, loopBeginBlock, map, loopCount++, block.loopDepth());
                assert loopBeginBlock.loopDepth() == block.loopDepth() && loopBeginBlock.loopIndex() == block.loopIndex();
            }
        }
    }

    private void markBlocks(Block block, Block loopBeginBlock, BitMap map, int loopIndex, int initialDepth) {
        if (map.get(block.blockID())) {
            return;
        }

        map.set(block.blockID());
        loopBeginBlock.loopBlocks.add(block);
        if (block.loopDepth() <= initialDepth) {
            assert block.loopDepth() == initialDepth;
            block.setLoopIndex(loopIndex);
        }
        block.setLoopDepth(block.loopDepth() + 1);

        if (block == loopBeginBlock) {
            return;
        }

        for (Block pred : block.getPredecessors()) {
            markBlocks(pred, loopBeginBlock, map, loopIndex, initialDepth);
        }

        if (block.isLoopHeader()) {
            markBlocks(nodeToBlock.get(((LoopBeginNode) block.firstNode()).loopEnd()), loopBeginBlock, map, loopIndex, initialDepth);
        }
    }

    private void assignBlockToNodes(StructuredGraph graph) {
        for (Node n : graph.getNodes()) {
            assignBlockToNode(n);
        }
    }

    public void assignBlockToNode(Node n) {
        if (n == null) {
            return;
        }

        assert !n.isDeleted();

        Block prevBlock = nodeToBlock.get(n);
        if (prevBlock != null) {
            return;
        }
        assert !(n instanceof PhiNode) : n;
        // if in CFG, schedule at the latest position possible in the outermost loop possible
        Block latestBlock = latestBlock(n);
        Block block;
        if (latestBlock == null) {
            block = earliestBlock(n);
        } else if (GraalOptions.ScheduleOutOfLoops && !(n instanceof VirtualObjectFieldNode) && !(n instanceof VirtualObjectNode)) {
            Block earliestBlock = earliestBlock(n);
            block = scheduleOutOfLoops(n, latestBlock, earliestBlock);
        } else {
            block = latestBlock;
        }
        assert !(n instanceof MergeNode);
        nodeToBlock.set(n, block);
        block.getInstructions().add(n);
    }

    private Block latestBlock(Node n) {
        Block block = null;
        for (Node succ : n.successors()) {
            if (succ == null) {
                continue;
            }
            assignBlockToNode(succ);
            block = getCommonDominator(block, nodeToBlock.get(succ));
        }
        ensureScheduledUsages(n);
        CommonDominatorBlockClosure cdbc = new CommonDominatorBlockClosure(block);
        for (Node usage : n.usages()) {
            blocksForUsage(n, usage, cdbc);
        }
        return cdbc.block;
    }

    private class CommonDominatorBlockClosure implements BlockClosure {
        public Block block;
        public CommonDominatorBlockClosure(Block block) {
            this.block = block;
        }
        @Override
        public void apply(Block newBlock) {
            this.block = getCommonDominator(this.block, newBlock);
        }
    }

    private Block earliestBlock(Node n) {
        Block earliest = nodeToBlock.get(n);
        if (earliest != null) {
            return earliest;
        }
        earliest = earliestCache.get(n);
        if (earliest != null) {
            return earliest;
        }
        BitMap bits = new BitMap(blocks.size());
        ArrayList<Node> before = new ArrayList<>();
        if (n.predecessor() != null) {
            before.add(n.predecessor());
        }
        for (Node input : n.inputs()) {
            before.add(input);
        }
        for (Node pred : before) {
            if (pred == null) {
                continue;
            }
            Block b = earliestBlock(pred);
            if (!bits.get(b.blockID())) {
                earliest = b;
                do {
                    bits.set(b.blockID());
                    b = b.dominator();
                } while(b != null && !bits.get(b.blockID()));
            }
        }
        if (earliest == null) {
            Block start = nodeToBlock.get(((StructuredGraph) n.graph()).start());
            assert start != null;
            return start;
        }
        earliestCache.set(n, earliest);
        return earliest;
    }


    private static Block scheduleOutOfLoops(Node n, Block latestBlock, Block earliest) {
        assert latestBlock != null : "no latest : " + n;
        Block cur = latestBlock;
        Block result = latestBlock;
        while (cur.loopDepth() != 0 && cur != earliest && cur.dominator() != null) {
            Block dom = cur.dominator();
            if (dom.loopDepth() < result.loopDepth()) {
                result = dom;
            }
            cur = dom;
        }
        return result;
    }

    private void blocksForUsage(Node node, Node usage, BlockClosure closure) {
        if (usage instanceof PhiNode) {
            PhiNode phi = (PhiNode) usage;
            MergeNode merge = phi.merge();
            Block mergeBlock = nodeToBlock.get(merge);
            assert mergeBlock != null : "no block for merge " + merge.toString(Verbosity.Id);
            for (int i = 0; i < phi.valueCount(); ++i) {
                if (phi.valueAt(i) == node) {
                    if (mergeBlock.getPredecessors().size() <= i) {
                        TTY.println(merge.toString());
                        TTY.println(phi.toString());
                        TTY.println(merge.cfgPredecessors().toString());
                        TTY.println(phi.inputs().toString());
                        TTY.println("value count: " + phi.valueCount());
                    }
                closure.apply(mergeBlock.getPredecessors().get(i));
                }
            }
        } else if (usage instanceof FrameState && ((FrameState) usage).block() != null) {
            MergeNode merge = ((FrameState) usage).block();
            Block block = null;
            for (Node pred : merge.cfgPredecessors()) {
                block = getCommonDominator(block, nodeToBlock.get(pred));
            }
            closure.apply(block);
        } else {
            assignBlockToNode(usage);
            closure.apply(nodeToBlock.get(usage));
        }
    }

    private void ensureScheduledUsages(Node node) {
        for (Node usage : node.usages().snapshot()) {
            assignBlockToNode(usage);
        }
        // now true usages are ready
    }

    private Block getCommonDominator(Block a, Block b) {
        if (a == null) {
            return b;
        }
        if (b == null) {
            return a;
        }
        return commonDominator(a, b);
    }

    private void sortNodesWithinBlocks(StructuredGraph graph) {
        NodeBitMap map = graph.createNodeBitMap();
        for (Block b : blocks) {
            sortNodesWithinBlocks(b, map);
        }
    }

    private void sortNodesWithinBlocks(Block b, NodeBitMap map) {
        List<Node> instructions = b.getInstructions();
        List<Node> sortedInstructions = new ArrayList<>(instructions.size() + 2);

        assert !map.isMarked(b.firstNode()) && nodeToBlock.get(b.firstNode()) == b;
        assert !map.isMarked(b.lastNode()) && nodeToBlock.get(b.lastNode()) == b;

        for (Node i : instructions) {
            addToSorting(b, i, sortedInstructions, map);
        }

        // Make sure that last node gets really last (i.e. when a frame state successor hangs off it).
        Node lastSorted = sortedInstructions.get(sortedInstructions.size() - 1);
        if (lastSorted != b.lastNode()) {
            int idx = sortedInstructions.indexOf(b.lastNode());
            boolean canNotMove = false;
            for (int i = idx + 1; i < sortedInstructions.size(); i++) {
                if (sortedInstructions.get(i).inputs().contains(b.lastNode())) {
                    canNotMove = true;
                    break;
                }
            }
            if (canNotMove) {
                // (cwi) this was the assertion commented out below.  However, it is failing frequently when the
                // scheduler is used for debug printing in early compiler phases. This was annoying during debugging
                // when an excpetion breakpoint is set for assertion errors, so I changed it to a bailout.
                if (b.lastNode() instanceof ControlSplitNode) {
                    throw new CiBailout("");
                }
                //assert !(b.lastNode() instanceof ControlSplitNode);

                //b.setLastNode(lastSorted);
            } else {
                sortedInstructions.remove(b.lastNode());
                sortedInstructions.add(b.lastNode());
            }
        }
        b.setInstructions(sortedInstructions);
    }

    private void addToSorting(Block b, Node i, List<Node> sortedInstructions, NodeBitMap map) {
        if (i == null || map.isMarked(i) || nodeToBlock.get(i) != b || i instanceof PhiNode || i instanceof LocalNode) {
            return;
        }

        if (i instanceof WriteNode) {
            // TODO(tw): Make sure every ReadNode that is connected to the same memory state is executed before every write node.
            // WriteNode wn = (WriteNode) i;
        }

        FrameState state = null;
        WriteNode writeNode = null;
        for (Node input : i.inputs()) {
            if (input instanceof WriteNode && !map.isMarked(input) && nodeToBlock.get(input) == b) {
                writeNode = (WriteNode) input;
            } else if (input instanceof FrameState) {
                state = (FrameState) input;
            } else {
                addToSorting(b, input, sortedInstructions, map);
            }
        }

        if (i.predecessor() != null) {
            addToSorting(b, i.predecessor(), sortedInstructions, map);
        }

        map.mark(i);

        addToSorting(b, state, sortedInstructions, map);
        assert writeNode == null || !map.isMarked(writeNode);
        addToSorting(b, writeNode, sortedInstructions, map);

        // Now predecessors and inputs are scheduled => we can add this node.
        sortedInstructions.add(i);
    }

    private void computeDominators(StructuredGraph graph) {
        Block dominatorRoot = nodeToBlock.get(graph.start());
        assert dominatorRoot != null;
        assert dominatorRoot.getPredecessors().size() == 0;
        BitMap visited = new BitMap(blocks.size());
        visited.set(dominatorRoot.blockID());
        LinkedList<Block> workList = new LinkedList<>();
        workList.add(dominatorRoot);

        int cnt = 0;
        while (!workList.isEmpty()) {
            if (cnt++ > blocks.size() * 20) {
                throw new RuntimeException("(ls) endless loop in computeDominators?");
            }
            Block b = workList.remove();

            List<Block> predecessors = b.getPredecessors();
            if (predecessors.size() == 1) {
                b.setDominator(predecessors.get(0));
            } else if (predecessors.size() > 1) {
                boolean delay = false;
                for (Block pred : predecessors) {
                    if (pred != dominatorRoot && pred.dominator() == null) {
                        delay = true;
                        break;
                    }
                }

                if (delay) {
                    workList.add(b);
                    continue;
                }

                Block dominator = null;
                for (Block pred : predecessors) {
                    if (dominator == null) {
                        dominator = pred;
                    } else {
                        dominator = commonDominator(dominator, pred);
                    }
                }
                b.setDominator(dominator);
            }

            for (Block succ : b.getSuccessors()) {
                if (!visited.get(succ.blockID())) {
                    visited.set(succ.blockID());
                    workList.add(succ);
                }
            }
        }
    }

    public Block commonDominator(Block a, Block b) {
        BitMap bitMap = new BitMap(blocks.size());
        Block cur = a;
        while (cur != null) {
            bitMap.set(cur.blockID());
            cur = cur.dominator();
        }

        cur = b;
        while (cur != null) {
            if (bitMap.get(cur.blockID())) {
                return cur;
            }
            cur = cur.dominator();
        }

        throw new IllegalStateException("no common dominator between " + a + " and " + b);
    }

    public static int trueSuccessorCount(Node n) {
        if (n == null) {
            return 0;
        }
        int i = 0;
        for (Node s : n.successors()) {
            if (Util.isFixed(s)) {
                i++;
            }
        }
        return i;
    }
}