/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
 *
 * File:   DominatorsAnalysisProvider.cpp
 * Author: pgess  <v.melnychenko@xreate.org>
 *
 * Created on May 13, 2016, 11:39 AM
 */

/**
 *  \file DominatorsAnalysisProvider.h
 *  \brief Dominators Tree analysis
 */

#include "analysis/cfagraph.h"
#include "analysis/DominatorsAnalysisProvider.h"

#include "llvm/ADT/GraphTraits.h"
#include "llvm/Support/GenericDomTreeConstruction.h"
#include "llvm/Support/GenericDomTree.h"

#include <list>
#include <iostream>
#include <boost/format.hpp>

using namespace std;
using namespace xreate;
using namespace boost;
using namespace boost::bimaps;

namespace xreate { namespace dominators {

struct CFAGraphAdapter;

struct ScopeNode {
    ScopePacked id;
    CFAGraphAdapter* parent;
    std::list<ScopeNode*> nodesFrom;
    std::list<ScopeNode*> nodesTo;

    CFAGraphAdapter* getParent(){ return parent; }
    void printAsOperand(llvm::raw_ostream&, bool) {}
    ScopeNode(ScopePacked scope, CFAGraphAdapter* parentAdapter):
        id(scope),  parent(parentAdapter) {}
};

}
} //end of namespace xreate::dominators

namespace llvm {
using namespace xreate::dominators;

template<>
struct GraphTraits<ScopeNode*> {
    typedef ScopeNode* NodeRef;
    typedef std::list<ScopeNode*>::iterator ChildIteratorType;

    static ChildIteratorType
    child_begin(ScopeNode* node) {
        return node->nodesTo.begin();
    }

    static ChildIteratorType
    child_end(ScopeNode* node) {
        return node->nodesTo.end();
    }
};

template<>
struct GraphTraits<Inverse<ScopeNode*>>
{
    typedef ScopeNode* NodeRef;
    typedef std::list<ScopeNode*>::iterator ChildIteratorType;

    static ChildIteratorType
    child_begin(ScopeNode* node) {
        return node->nodesFrom.begin();
    }

    static ChildIteratorType
    child_end(ScopeNode* node) {
        return node->nodesFrom.end();
    }
};

template<>
struct GraphTraits<CFAGraphAdapter*> {
    typedef std::list<ScopeNode*>::iterator nodes_iterator;

    static nodes_iterator
    nodes_begin(CFAGraphAdapter* graph) {
        return graph->nodes.begin();
    }

    static nodes_iterator
    nodes_end(CFAGraphAdapter* graph) {
        return graph->nodes.end();
    }

    static ScopeNode*
    getEntryNode(CFAGraphAdapter* F) {
        return F->nodeRoot;
    }

    static unsigned int
    size(CFAGraphAdapter* graph) {
        return graph->nodes.size();
    }
};
}

namespace xreate {
namespace dominators {

class DominatorTree : public llvm::DominatorTreeBase<ScopeNode, false> {
friend class DominatorsAnalysisProvider;
public:
    DominatorTree() : llvm::DominatorTreeBase<ScopeNode, false>() {}

    void
    run(CFAGraphAdapter& program) {
        recalculate(program);
        updateDFSNumbers();

        //extract dominators info
        for(auto& entry : DomTreeNodes) {
            if(!entry.getFirst()) continue;

            dominators.emplace(entry.getFirst()->id, make_pair(entry.getSecond()->getDFSNumIn(), entry.getSecond()->getDFSNumOut()));
        }
    }

    void
    print(std::ostringstream& output, const std::string& atom) const {
        boost::format formatAtom(atom+"(%1%, range(%2%, %3%)).");

        for(auto entry : dominators) {
            output<<formatAtom%(entry.first)%(entry.second.first)%(entry.second.second)
                <<std::endl;
        }
    }

private:
    DominatorsAnalysisProvider::Dominators dominators;
};

class PostDominatorTree : public llvm::DominatorTreeBase<ScopeNode, true> {
friend class DominatorsAnalysisProvider;
public:
    PostDominatorTree() : llvm::DominatorTreeBase<ScopeNode, true>() {}

    void
    run(CFAGraphAdapter& program) {
        recalculate(program);
        updateDFSNumbers();
        //extract dominators info
        for(auto& entry : DomTreeNodes) {
            if(!entry.getFirst()) continue;

            dominators.emplace(entry.getFirst()->id, make_pair(entry.getSecond()->getDFSNumIn(), entry.getSecond()->getDFSNumOut()));
        }
    }

    void
    print(std::ostringstream& output, const std::string& atom) const {
        boost::format formatAtom(atom+"(%1%, range(%2%, %3%)).");

        for(auto entry : dominators) {
            output<<formatAtom%(entry.first)%(entry.second.first)%(entry.second.second)
                <<std::endl;
        }
    }

private:
    DominatorsAnalysisProvider::Dominators dominators;
};

ScopeNode*
CFAGraphAdapter::registerScope(ScopePacked scope){
    ScopeNode elemNew(scope, this);
    auto fnComp = [](const ScopeNode* a, const ScopeNode* b){return a->id < b->id;};
    auto posLowerBound = std::lower_bound(nodes.begin(), nodes.end(), &elemNew, fnComp);

    if(posLowerBound==nodes.end()|| (*posLowerBound)->id > scope){
        ScopeNode* elemNewP = new ScopeNode(elemNew);
        *elemNewP = elemNew;
        return *nodes.insert(posLowerBound, elemNewP);
    }

    return *posLowerBound;
}

CFAGraphAdapter*
CFAGraphAdapter::build(const cfa::CFAGraph* graph) {
    return build(graph->__dependencyRelations);
}

CFAGraphAdapter*
CFAGraphAdapter::build(const std::multimap<ScopePacked, ScopePacked>& dataScopesOrder){
    CFAGraphAdapter* tree=new CFAGraphAdapter();

    enum NODE_MARK{NO_ROOT, POSSIBLE_ROOT};
    std::unordered_map<unsigned int, NODE_MARK> nodeMarks;
    for (const auto& edge: dataScopesOrder){

        ScopeNode* nodeTo = tree->registerScope(edge.first);
        ScopeNode* nodeFrom = tree->registerScope(edge.second);
        nodeTo->nodesFrom.push_back(nodeFrom);
        nodeFrom->nodesTo.push_back(nodeTo);

        nodeMarks.emplace(edge.second, POSSIBLE_ROOT); //weak optional insert
        auto result = nodeMarks.emplace(edge.first, NO_ROOT); //strong insert or update
        if(!result.second){
            result.first->second = NO_ROOT;
        }
    }

    std::list<ScopePacked> nodeRoots;
    for(auto nodeMark: nodeMarks){
        if(nodeMark.second == POSSIBLE_ROOT) nodeRoots.push_back(nodeMark.first);
    }

    if(nodeRoots.size()>1){
        ScopeNode* nodeGlobalRoot = tree->registerScope(SCOPE_ABSTRACT_GLOBAL);
        for(auto rootLocal: nodeRoots){
            ScopeNode* nodeLocalRoot = tree->registerScope(rootLocal);
            nodeLocalRoot->nodesFrom.push_back(nodeGlobalRoot);
            nodeGlobalRoot->nodesTo.push_back(nodeLocalRoot);
        }

        tree->nodeRoot = nodeGlobalRoot;

    } else if (nodeRoots.size()==1){
        tree->nodeRoot = tree->registerScope(nodeRoots.front());

    } else {
        ScopeNode* nodeGlobalRoot = tree->registerScope(SCOPE_ABSTRACT_GLOBAL);
        tree->nodeRoot = nodeGlobalRoot;
    }

    return tree;
}

void
DominatorsAnalysisProvider::run(CFAGraphAdapter* program) {
    treeForwardDominators.reset(new DominatorTree());
    treePostDominators.reset(new PostDominatorTree());

    treeForwardDominators->run(*program);
    treePostDominators->run(*program);
}

void
DominatorsAnalysisProvider::print(std::ostringstream& output) const {
    treeForwardDominators->print(output, "cfa_forwdom");
    treePostDominators->print(output, "cfa_postdom");
}

const DominatorsAnalysisProvider::Dominators&
DominatorsAnalysisProvider::getForwardDominators() const {
    return treeForwardDominators->dominators;
}

const DominatorsAnalysisProvider::Dominators&
DominatorsAnalysisProvider::getPostDominators() const {
    return treePostDominators->dominators;
}

DominatorsAnalysisProvider::DominatorsAnalysisProvider() {}
DominatorsAnalysisProvider::~DominatorsAnalysisProvider() { }


}} //end of namespace xreate::dominators