/*
 *  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, Pavel A. Ozhdikhin
 *
 */

#include "Dominator.h"
#include <string.h>

namespace Jitrino {

// BOTTOM : no idom.  idom[entry] = BOTTOM
#define NONE MAX_UINT32
// TOP : no information computed yet
#define UNDEFINED 0 

// Cooper / Harvey / Kennedy variation on simple iterative dominator algorithm.
// They claim that this is faster than Lengauer / Tarjan in practice.  
DominatorTree*
DominatorBuilder::computeDominators(MemoryManager& mm, ControlFlowGraph* flowgraph, bool isPost, bool ignoreUnreach) {
    // Temp memory manager
    MemoryManager tmm("DominatorBuilder::computeDominators");
    Nodes nodes(tmm);

    // Get the nodes of the flowgraph in postorder.
    flowgraph->getNodesPostOrder(nodes, !isPost);
    U_32 numNodes = (U_32) nodes.size();
#ifdef _DEBUG
    // Start (entry/exit) node should be last.
    Node* start = nodes.back();
    assert((start == (isPost ? flowgraph->getExitNode() : flowgraph->getEntryNode()) 
            && start->getPostNum() == numNodes-1));
#endif         
    // Initialize the idom array to UNDEFINED.  Idiom maps the postorder
    // number of a node to the postorder number of its idom.
    StlVector<U_32> idom(tmm);
    idom.insert(idom.end(), (unsigned int) numNodes-1, UNDEFINED);
    // Initialize idom[entry] = NONE.
    idom.insert(idom.end(), NONE);

    // Find maximal fixed point
    bool changed = true;
    while(changed) {
        changed = false;
        // Process all nodes except entry in reverse postorder.
        Nodes::reverse_iterator i;
        for(i = nodes.rbegin()+1; i != nodes.rend(); ++i) {
            Node* node = *i;
            U_32 nodeNum = node->getPostNum();

            // Compute updated idom from predecessors
            U_32 newIdom = UNDEFINED;
            Edges::const_iterator j;
            for(j = node->getEdges(isPost).begin(); j != node->getEdges(isPost).end(); ++j) {
                Node* pred = (*j)->getNode(isPost);
                // Assert that pred is reachable.
                if (!ignoreUnreach)
                    assert(pred->getTraversalNum() == flowgraph->getTraversalNum());
                if (!ignoreUnreach || (ignoreUnreach && (pred->getTraversalNum() == flowgraph->getTraversalNum()))) {
                    U_32 predNum = pred->getPostNum();
                    // Skip unprocessed preds (only happens on first iteration).
                    if(idom[predNum] != UNDEFINED)
                        // Intersect dominator sets.
                        newIdom = (newIdom == UNDEFINED) ? predNum : intersect(idom, newIdom, predNum);
                } 
            }
            assert(newIdom != UNDEFINED);

            // Update if changed
            if(newIdom != idom[nodeNum]) {
                // Assert that we are converging.
                assert(newIdom > idom[nodeNum]);
                idom[nodeNum] = newIdom;
                changed = true;
            }
        }
    }

    // Build dominator tree and return.
    return new (mm) DominatorTree(mm, flowgraph, nodes, idom, isPost);
}

U_32 
DominatorBuilder::intersect(StlVector<U_32>& idom, U_32 finger1, U_32 finger2) {
    // Intersect the dominator sets represented by finger1 and finger2.
    while(finger1 != finger2) {
        while(finger1 < finger2)
            finger1 = idom[finger1];
        while(finger2 < finger1)
            finger2 = idom[finger2];
    }
    // Set should at least contain root/entry.
    assert(finger1 != NONE);
    return finger1;
}

DominatorTree::DominatorTree(MemoryManager& mm,
                             ControlFlowGraph* fg,
                             Nodes& nodes,
                             StlVector<U_32>& idom,
                             bool isPostDominator)     
                             : flowgraph(fg), traversalNum(fg->getTraversalNum()), 
                               numNodes(fg->getMaxNodeId()), 
                               _isPostDominator(isPostDominator), tree(mm, numNodes, NULL) {
    // Create the dominator tree nodes..
    U_32 postNum, id=MAX_UINT32;
    for(postNum = 0; postNum < nodes.size(); ++postNum) {
        Node* node = nodes[postNum];
        id = node->getId();
        tree[id] = new (mm) DominatorNode(node);
    }

    // Create tree itself.  Note that the children of each
    // dominator parent node will be in sorted in
    // reverse postorder.  It's assumed that nodes is 
    // in postorder.
    for(postNum = 0; postNum < nodes.size(); ++postNum) {
        Node* node = nodes[postNum];
        id = node->getId();
        // Assert post-ordering of nodes.
        assert((U_32) postNum == node->getPostNum());
        if(idom[postNum] != NONE) {
            // Assert that idoms are acyclic.
            assert(idom[postNum] > postNum);
            Node* parent = nodes[idom[postNum]];
            U_32 parentId = parent->getId();
            assert(tree[parentId] != NULL);
            // Assert that new child (added to beginning) has highest postorder number.
            assert(tree[parentId]->getChild() == NULL || tree[parentId]->getChild()->getNode()->getPostNum() < postNum);
            tree[parentId]->addChild(tree[id]);
        }
    }

    // Last node is root.
    root = tree[id];
    computeOrder();
}

bool DominatorTree::dominates(Node* a, Node* b) {
    assert(a != NULL && b != NULL);
    assert(a->getId() < numNodes && b->getId() < numNodes);
    DominatorNode* na = tree[a->getId()];
    DominatorNode* nb = tree[b->getId()];
    if (na == NULL || nb == NULL) {
        return false;
    }
    return a==b || isAncestor(na, nb);
}


DomFrontier::DomFrontier(MemoryManager& mm, 
                         DominatorTree& d,
                         ControlFlowGraph*     fg) 
: memManager(mm), dom(d), isPostDominator(d.isPostDominator()) {
    // To Do: may want to keep number of nodes in flow graph instead of recomputing every time
    numNodes = (U_32) fg->getNodeCount();

    // if flow graph has been modified since dominator was computed, then
    // dominator information needs to be recomputed
    if (!dom.isValid()) {
        DominatorBuilder db;
        dom = *db.computeDominators(memManager,fg);
    }

    beenComputed = new (memManager) BitSet(memManager, numNodes);
    DF = (List<Node>**) memManager.alloc(sizeof(List<Node>*)*numNodes);
    memset(DF, 0, numNodes*sizeof(List<Node>*));  // initialized with NULL
}

void DomFrontier::addDF(U_32 entry, Node* n) {
    assert(entry < numNodes);
    // make sure no duplicate entry
    for (List<Node>* l = DF[entry]; l != NULL; l = l->getNext())
        if (l->getElem() == n)  
            return;
    DF[entry] = new (memManager) List<Node>(n,DF[entry]);
}

void DomFrontier::computeDomFrontier(Node* node) {
    U_32 dfnum = node->getDfNum();
    // if dom frontiers are not computed yet
    if (beenComputed->getBit(dfnum))
        return;
    beenComputed->setBit(dfnum,true);

    // If this is a post-dominance frontier, use the reverse graph.
    bool forward = !isPostDominator;

    // compute DF local: the successors of node that are not strictly
    // dominated by node
    const Edges& edges = node->getEdges(forward);
    Edges::const_iterator eiter;
    for(eiter = edges.begin(); eiter != edges.end(); ++eiter) {
        Edge* e = *eiter;
        Node *succ =  e->getNode(forward);
        if (dom.getIdom(succ) != node) {
            addDF(dfnum,succ);
        }
    }

    // compute DF up: Nodes in the dom frontier of node that are dominated
    // by node's immediate dominator
    for (DominatorNode* c = dom.getDominatorNode(node)->getChild(); c != NULL; c = c->getSiblings()) {
        Node* child = c->getNode();
        computeDomFrontier(child);
        
        // go over each frontier of child
        for (List<Node>* f = DF[child->getDfNum()];f != NULL; f = f->getNext()) {
            Node *elem = f->getElem();
            // if node does not strictly dominates elem
            if (elem == node || !dom.dominates(node,elem)) {
                addDF(dfnum,elem);
            }
        }
    }
}


} //namespace Jitrino