/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
/**
 * @author Intel, Mikhail Y. Fursov
 */

#include "Ia32CodeLayoutBottomUp.h"
#include "Ia32IRManager.h"
#include "Log.h"
namespace Jitrino
{
namespace Ia32 {
/**
* Class to perform bottom-up block layout. 
* The layout algorithm is similar to the one described in the paper
* "Profile Guided Code Positioning" by Hansen & Pettis. 
*/

BottomUpLayout::BottomUpLayout(IRManager* irm) : 
Linearizer(irm), 
mm("Ia32::bottomUpLayout"), 
firstInChain(mm, irm->getFlowGraph()->getNodeCount(), false),
lastInChain(mm, irm->getFlowGraph()->getNodeCount(), false),
prevInLayoutBySuccessorId(mm, irm->getFlowGraph()->getNodeCount(), NULL)
{
}


struct edge_comparator {
    bool operator() (const Edge* e1, const Edge* e2) const { //true -> e1 is first
        double v1 = getEdgeExecCount(e1);
        double v2 = getEdgeExecCount(e2);
        return   v1 > v2;
    }
    static double getEdgeExecCount(const Edge* e) { 
        return e->getSourceNode()->getExecCount() * e->getEdgeProb();
    }

};

void BottomUpLayout::linearizeCfgImpl() {
    assert(irManager->getFlowGraph()->isEdgeProfileConsistent());
    StlVector<Edge*> sortedEdges(mm);
    const Nodes& nodes = irManager->getFlowGraph()->getNodes();
    sortedEdges.reserve(nodes.size() * 3);
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it)  {
        Node* node = *it;
        const Edges& edges = node->getOutEdges();
        sortedEdges.insert(sortedEdges.end(), edges.begin(), edges.end());
    }
    //GCC 3.4 passes NULLs to comparator if usual std::sort is used here..
    std::stable_sort(sortedEdges.begin(), sortedEdges.end(), edge_comparator());
    for(StlVector<Edge*>::const_iterator it = sortedEdges.begin(), itEnd = sortedEdges.end(); it!=itEnd; it++) {
        Edge* edge  = *it;
        layoutEdge(edge);
    }
    //create one-block-chains from blocks that was not laid out
    //these blocks are dispatch successors or are blocks connected by in/out edges to already laid out chains
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it)  {
        Node* node = *it;
        if (node->isBlockNode()) {
            BasicBlock* block = (BasicBlock*)node;
            if (block->getLayoutSucc() == NULL && !lastInChain[block->getDfNum()]) {
                firstInChain[block->getDfNum()] = true;
                lastInChain[block->getDfNum()] = true;
            }
        }
    }
    combineChains();
}

void  BottomUpLayout::layoutEdge(Edge *edge) {
    Node* tailNode = edge->getSourceNode();
    Node* headNode = edge->getTargetNode();
    if (!headNode->isBlockNode() || !tailNode->isBlockNode()) {
        return;
    }
    if (headNode == irManager->getFlowGraph()->getEntryNode()) { //prolog node should be first in layout
        return;
    }
    if (tailNode == headNode) {
        return; //backedge to self
    }
    BasicBlock* tailBlock = (BasicBlock*)tailNode;
    if (tailBlock->getLayoutSucc()!=NULL) {
        return;  //tailBlock is layout predecessor for another successor
    }
    BasicBlock* headBlock = (BasicBlock*)headNode;
    if (prevInLayoutBySuccessorId[headBlock->getDfNum()]!=NULL) {
        return; // head was already laid out (in other chain)
    }
    if (lastInChain[tailBlock->getDfNum()] && firstInChain[headBlock->getDfNum()]) {
        BasicBlock* tailOfHeadChain = headBlock;
        while (tailOfHeadChain->getLayoutSucc()!=NULL) {
            tailOfHeadChain = tailOfHeadChain->getLayoutSucc();
        }   
        if (tailOfHeadChain == tailBlock) {
            return; // layout must be acyclic
        }
    }

    tailBlock->setLayoutSucc(headBlock);
    prevInLayoutBySuccessorId[headBlock->getDfNum()] = tailBlock;

    BasicBlock* tailPred = prevInLayoutBySuccessorId[tailBlock->getDfNum()];
    if (tailPred) {
        assert(lastInChain[tailBlock->getDfNum()]);
        lastInChain[tailBlock->getDfNum()] = false;
    } else {
        firstInChain[tailBlock->getDfNum()] = true;
    }// here we have valid first
    firstInChain[headBlock->getDfNum()] = false;

    BasicBlock* newLast = headBlock;
    while (newLast->getLayoutSucc()!=NULL) {
        newLast = newLast->getLayoutSucc();
    }
    lastInChain[newLast->getDfNum()] = true;
}


struct chains_comparator{
    const StlVector<BasicBlock*>& prevInLayoutBySuccessorId;
    const BasicBlock* prolog;
    chains_comparator(const StlVector<BasicBlock*>& _prevInLayoutBySuccessorId, BasicBlock* _prolog) 
        : prevInLayoutBySuccessorId(_prevInLayoutBySuccessorId), prolog(_prolog) 
    {};
    
    
    bool operator() (const BasicBlock* c1, const BasicBlock* c2) const { 
        if (c1 == prolog) {
            return true;
        }
        if (c2 == prolog) {
            return false;
        }
        double fromC1ToC2 = calcEdgesWeight(c1, c2);
        double fromC2ToC1 = calcEdgesWeight(c2, c1);
        if (fromC1ToC2 > fromC2ToC1) {
            return true; //c1 is first in topological order
        } else if (fromC1ToC2 < fromC2ToC1) {
            return false; //c2 is first in topological order
        }
        return c1 > c2; //any stable order..
    }

    double calcEdgesWeight(const BasicBlock* c1, const BasicBlock* c2) const {
        double d = 0.0;
        //distance is sum of exec count of c1 blocks out edges c1 to c2;
        for (const BasicBlock* b = c1; b!=NULL; b = b->getLayoutSucc()) {
            const Edges& outEdges = b->getOutEdges();
            for (Edges::const_iterator ite = outEdges.begin(), ende = outEdges.end(); ite!=ende; ++ite) {
                Edge* e= *ite;
                Node* node = e->getTargetNode();
                if (node != b->getLayoutSucc() && node->isBlockNode()) {
                    const BasicBlock* targetBlock = (BasicBlock*)node;
                    //look if node is in c2 chain
                    const BasicBlock* targetChain = findChain(targetBlock);
                    if (targetChain == c2) {
                        double dd = b->getExecCount() * e->getEdgeProb();
                        d+=dd;
                    }
                }
            }
        }
        return d;
    }

    const BasicBlock* findChain(const BasicBlock* bb) const  {
        const BasicBlock* prev  = bb;
        while ((prev = prevInLayoutBySuccessorId[bb->getDfNum()])!=NULL) {
            bb = prev;
        }
        return bb;
    }
};


void BottomUpLayout::combineChains() {
    StlVector<BasicBlock*> chains(mm);
    const Nodes& nodes = irManager->getFlowGraph()->getNodes();
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it)  {
        Node* node = *it;
        if (firstInChain[node->getDfNum()]) {
            assert(node->isBlockNode());
            chains.push_back((BasicBlock*)node);
        }
    }
    std::sort(chains.begin(), chains.end(), 
        chains_comparator(prevInLayoutBySuccessorId, (BasicBlock*)irManager->getFlowGraph()->getEntryNode()));
    assert(*chains.begin() ==irManager->getFlowGraph()->getEntryNode());

    assert(*chains.begin() == irManager->getFlowGraph()->getEntryNode());
    for (U_32 i = 0, n = (U_32)chains.size()-1; i<n;i++) {
        BasicBlock* firstChain = chains[i];
        BasicBlock* secondChain= chains[i+1];
        BasicBlock* lastInFirst = firstChain;
        while (lastInFirst->getLayoutSucc()!=NULL) {
            lastInFirst = lastInFirst->getLayoutSucc();
        }
        lastInFirst->setLayoutSucc(secondChain);
    }
}

}} //namespace