/*******************************************************************************
 * Copyright IBM Corp. and others 2000
 *
 * This program and the accompanying materials are made available under
 * the terms of the Eclipse Public License 2.0 which accompanies this
 * distribution and is available at https://www.eclipse.org/legal/epl-2.0/
 * or the Apache License, Version 2.0 which accompanies this distribution
 * and is available at https://www.apache.org/licenses/LICENSE-2.0.
 *
 * This Source Code may also be made available under the following Secondary
 * Licenses when the conditions for such availability set forth in the
 * Eclipse Public License, v. 2.0 are satisfied: GNU General Public License,
 * version 2 with the GNU Classpath Exception [1] and GNU General Public
 * License, version 2 with the OpenJDK Assembly Exception [2].
 *
 * [1] https://www.gnu.org/software/classpath/license.html
 * [2] https://openjdk.org/legal/assembly-exception.html
 *
 * SPDX-License-Identifier: EPL-2.0 OR Apache-2.0 OR GPL-2.0-only WITH Classpath-exception-2.0 OR GPL-2.0-only WITH OpenJDK-assembly-exception-1.0
 *******************************************************************************/

#if DEBUG

#include "optimizer/DominatorsChk.hpp"

#include <stdint.h>
#include <string.h>
#include "compile/Compilation.hpp"
#include "env/TRMemory.hpp"
#include "il/Block.hpp"
#include "infra/Array.hpp"
#include "infra/BitVector.hpp"
#include "infra/Cfg.hpp"
#include "infra/List.hpp"
#include "infra/CfgEdge.hpp"

TR_DominatorsChk::TR_DominatorsChk(TR::Compilation *c)
    : _compilation(c)
{
    int32_t i, j;
    _topDfNum = 0;
    _visitCount = comp()->incOrResetVisitCount();

    TR::CFG *cfg = comp()->getFlowGraph();
    _numBlocks = cfg->getNumberOfNodes() + 1;

    if (debug("traceDOM"))
        dumpOptDetails(comp(), "   Number of blocks is %d\n", _numBlocks - 1);

    // Info will persist until the caller releases the stack
    //
    _info = (BBInfoChk *)trMemory()->allocateStackMemory(_numBlocks * sizeof(BBInfoChk));

    memset(_info, 0, _numBlocks * sizeof(BBInfoChk));

    int32_t nextNodeNumber = cfg->getNextNodeNumber();
    _dfNumbers = (int32_t *)trMemory()->allocateStackMemory(nextNodeNumber * sizeof(int32_t));
    memset(_dfNumbers, 0, nextNodeNumber * sizeof(int32_t));

    findDominators(toBlock(cfg->getStart()));
    findImmediateDominators();

    for (i = 2; i < _topDfNum + 1; i++) {
        TR_BitVector *bucket = _info[i]._bucket;
        TR_BitVector *tmpbucket = _info[i]._tmpbucket;
        TR::Block *dominator;

        for (j = 0; j < _numBlocks - 1; j++) {
            if (tmpbucket->get(j)) {
                dominator = _info[j + 1]._block;
                _info[i]._idom = &_info[j + 1];
            }
        }

        TR::Block *dominated = _info[i]._block;

        if (((dominator == NULL) && (dominated == NULL))) {
        }

        // These two lines to be uncommented if this is the only Dominator
        // algorithm in use in the program. They set the Dominator info to
        // be used by other modules. The Dominator info is currently being
        // set by the efficient Dominator algorithm.
        //
        //      dominated->setDominator(dominator);
        //      dominator->addDominatedBlock(dominated);

        for (j = 0; j < _numBlocks - 1; j++) {
            if (bucket->get(j)) {
                if (debug("traceDOM")) {
                    dumpOptDetails(comp(), "   Dominator of [%d] is [%d] \n", _info[i]._block->getNumber(),
                        _info[j + 1]._block->getNumber());
                    dumpOptDetails(comp(), "   Immediate Dominator of [%d] is [%d] \n", _info[i]._block->getNumber(),
                        dominator->getNumber());
                }
            }
        }
    }
}

// Part 1 of the simple O(n^2) algorithm in Muchnick. Performs initialization
// and computes dominators for each node.
//
void TR_DominatorsChk::findDominators(TR::Block *start)
{
    int32_t i, j;
    BBInfoChk *w;
    bool change = true;
    TR_BitVector *intersection = new (trStackMemory()) TR_BitVector(_numBlocks, trMemory(), stackAlloc);

    initialize(start, NULL);

    while (change) {
        change = false;
        for (i = 2; i < _topDfNum + 1; i++) {
            w = _info + i;

            for (j = 0; j < _numBlocks - 1; j++)
                intersection->set(j);

            TR::CFGEdge *pred;
            BBInfoChk *predinfo;
            for (auto pred = w->_block->getPredecessors().begin(); pred != w->_block->getPredecessors().end(); ++pred) {
                predinfo = _info + (_dfNumbers[toBlock((*pred)->getFrom())->getNumber()] + 1);
                (*intersection) &= (*(predinfo->_bucket));
            }
            for (auto pred = w->_block->getExceptionPredecessors().begin();
                 pred != w->_block->getExceptionPredecessors().end(); ++pred) {
                predinfo = _info + (_dfNumbers[toBlock((*pred)->getFrom())->getNumber()] + 1);
                (*intersection) &= (*(predinfo->_bucket));
            }

            intersection->set(i - 1);

            if (!((*(w->_bucket)) == *intersection)) {
                change = true;

                // Copy intersection into bucket, except for the last bit.
                // Is this what was intended?
                int32_t lastBit = w->_bucket->get(_numBlocks - 1);
                *w->_bucket = *intersection;
                if (lastBit)
                    w->_bucket->set(_numBlocks - 1);
                else
                    w->_bucket->reset(_numBlocks - 1);
            }
        }
    }
}

// Initialization step for part 1 of the algorithm. Initializes the
// bucket structure and traverses the flow graph in Depth First Order
// to perform numbering.
//
void TR_DominatorsChk::initialize(TR::Block *start, TR::Block *nullParent)
{
    TR_Array<StackInfo> *stack
        = new (trStackMemory()) TR_Array<StackInfo>(trMemory(), _numBlocks / 2, false, stackAlloc);
    // Set up to start at the start block
    //
    TR::CFGEdge dummyEdge;
    TR::CFGEdgeList dummyList(comp()->region());
    dummyList.push_front(&dummyEdge);
    (*stack)[0].curIterator = dummyList.begin();
    (*stack)[0].list = &dummyList;
    TR::Block *block;
    int32_t index = 1;
    while ((--index) >= 0) {
        auto next = (*stack)[index].curIterator;
        auto list = (*stack)[index].list;
        if ((*next)->getTo())
            block = toBlock((*next)->getTo());
        else
            block = start;

        TR::Block *nextBlock;
        if (block->getVisitCount() == _visitCount) {
            // This block has already been processed. Just set up the next block
            // at this level.
            //
            ++next;
            if (next != list->end()) {
                if (debug("traceDOM"))
                    dumpOptDetails(comp(), "Insert block_%d at level %d\n", toBlock((*next)->getTo())->getNumber(),
                        index);
                (*stack)[index++].curIterator = next;
            }
            continue;
        }

        if (debug("traceDOM"))
            dumpOptDetails(comp(), "At level %d block_%d becomes block_%d\n", index, block->getNumber(), _topDfNum);

        // Note: the BBInfoChk index is one more than the block's DF number.
        //
        block->setVisitCount(_visitCount);
        // block->setNumber(_topDfNum++);
        _dfNumbers[block->getNumber()] = _topDfNum++;
        BBInfoChk *binfo = _info + _topDfNum;
        binfo->_block = block;
        binfo->_bucket = new (trStackMemory()) TR_BitVector(_numBlocks, trMemory(), stackAlloc);

        if (block != start)
            binfo->_bucket->setAll(_numBlocks - 1);
        else
            binfo->_bucket->set(_topDfNum - 1);

        // Set up the next block at this level
        //
        ++next;
        if (next != list->end()) {
            if (debug("traceDOM"))
                dumpOptDetails(comp(), "Insert block_%d at level %d\n", toBlock((*next)->getTo())->getNumber(), index);
            (*stack)[index++].curIterator = next;
        }

        // Set up the successors to be processed
        //
        list = &(block->getExceptionSuccessors());
        next = list->begin();
        if (next != list->end()) {
            if (debug("traceDOM"))
                dumpOptDetails(comp(), "Insert block_%d at level %d\n", toBlock((*next)->getTo())->getNumber(), index);
            (*stack)[index].list = list;
            (*stack)[index++].curIterator = next;
        }
        list = &(block->getSuccessors());
        next = list->begin();
        if (next != list->end()) {
            if (debug("traceDOM"))
                dumpOptDetails(comp(), "Insert block_%d at level %d\n", toBlock((*next)->getTo())->getNumber(), index);
            (*stack)[index].list = list;
            (*stack)[index++].curIterator = next;
        }
    }
}

// Part 2 of the simple O(n^2) algorithm in Muchnick. Performs initialization
// and computes immediate dominators for each node. Note that this uses the
// dominators info computed in Part 1.
//
void TR_DominatorsChk::findImmediateDominators()
{
    int32_t i, j, k;
    BBInfoChk *w, *x;

    initialize();

    for (i = 2; i < _topDfNum + 1; i++) {
        w = _info + i;

        for (j = 1; j < _topDfNum + 1; j++) {
            x = _info + j;

            if (w->_tmpbucket->get(j - 1)) {
                for (k = 0; k < _numBlocks - 1; k++) {
                    if (!((j - 1) == k)) {
                        if (x->_tmpbucket->get(k))
                            w->_tmpbucket->reset(k);
                    }
                }
            }
        }
    }
}

// Initialization step for part 2 of the algorithm. Initializes the
// tmpbucket structure.
//
void TR_DominatorsChk::initialize()
{
    int i;
    BBInfoChk *w;

    for (i = 1; i < _topDfNum + 1; i++) {
        w = _info + i;
        w->_tmpbucket = new (trStackMemory()) TR_BitVector(*w->_bucket);
        w->_tmpbucket->reset(i - 1);
    }
}

#endif
