/*******************************************************************************
 * 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
 *******************************************************************************/

#include <stdint.h>
#include <string.h>
#include "env/FrontEnd.hpp"
#include "compile/Compilation.hpp"
#include "compile/ResolvedMethod.hpp"
#include "env/StackMemoryRegion.hpp"
#include "env/TRMemory.hpp"
#include "il/Block.hpp"
#include "il/DataTypes.hpp"
#include "il/ILOpCodes.hpp"
#include "il/ILOps.hpp"
#include "il/Node.hpp"
#include "il/Node_inlines.hpp"
#include "il/Symbol.hpp"
#include "il/SymbolReference.hpp"
#include "il/TreeTop.hpp"
#include "il/TreeTop_inlines.hpp"
#include "infra/BitVector.hpp"
#include "infra/Cfg.hpp"
#include "infra/List.hpp"
#include "infra/CfgEdge.hpp"
#include "optimizer/Structure.hpp"
#include "optimizer/DataFlowAnalysis.hpp"
#include "optimizer/LocalAnalysis.hpp"

class TR_OpaqueClassBlock;

namespace TR {
class Optimizer;
}

// #define MAX_BLOCKS_FOR_STACK_ALLOCATION 16

// This file contains an implementation of Global Anticipatability which
// is the first global bit vector analyses used by PRE. Global anticipatability
// attempts to discover points in the program that are possibilities for
// being optimal. If an expression is not globally anticipatable at some
// program point, then that point cannot be an optimal placement point
// for the expression.
//
//
TR_DataFlowAnalysis::Kind TR_GlobalAnticipatability::getKind() { return GlobalAnticipatability; }

TR_GlobalAnticipatability *TR_GlobalAnticipatability::asGlobalAnticipatability() { return this; }

int32_t TR_GlobalAnticipatability::getNumberOfBits() { return _localTransparency.getNumNodes(); }

void TR_GlobalAnticipatability::analyzeNode(TR::Node *, vcount_t, TR_BlockStructure *, TR_BitVector *) {}

TR_GlobalAnticipatability::TR_GlobalAnticipatability(TR::Compilation *comp, TR::Optimizer *optimizer,
    TR_Structure *rootStructure, bool trace)
    : TR_BackwardIntersectionBitVectorAnalysis(comp, comp->getFlowGraph(), optimizer, trace)
    , _localAnalysisInfo(comp, trace)
    , _localTransparency(_localAnalysisInfo, trace)
    , _localAnticipatability(_localAnalysisInfo, &_localTransparency, trace)
{
    if (trace)
        traceMsg(comp, "Starting GlobalAnticipatability\n");

    _supportedNodesAsArray = _localAnalysisInfo._supportedNodesAsArray;

    initializeBlockInfo();

    {
        TR::StackMemoryRegion stackMemoryRegion(*trMemory());

        performAnalysis(rootStructure, false);

        int32_t j;
        for (j = 0; j < _numberOfNodes; j++)
            *_blockAnalysisInfo[j] |= *(_localAnticipatability.getDownwardExposedAnalysisInfo(j));

        if (trace) {
            int32_t i;
            for (i = 0; i < _numberOfNodes; i++) {
                traceMsg(comp, "Block number : %d has solution : ", i);
                _blockAnalysisInfo[i]->print(comp);
                traceMsg(comp, "\n");
            }

            traceMsg(comp, "Ending GlobalAnticipatability\n");
        }

    } // scope of the stack memory region

    // Null out info not used by callers
    _outSetInfo = NULL;
}

bool TR_GlobalAnticipatability::postInitializationProcessing()
{
    // In this case, i.e. global anticipatability _outSetInfo is required
    // as a field. So it is specifically allocated here and not as part
    // of the other more general bit vectors allocated by any backward
    // bit vector analysis.
    //
    _outSetInfo = (ContainerType **)trMemory()->allocateStackMemory(_numberOfNodes * sizeof(ContainerType *));

    int32_t i;
    for (i = 0; i < _numberOfNodes; i++)
        allocateContainer(_outSetInfo + i);

    allocateContainer(&_scratch);
    allocateContainer(&_scratch2);
    allocateContainer(&_scratch3);

    // this array will store _checkExpressions info per block
    // (some expressions can be exceptional in some blocks but not others)
    _checkExpressionsInBlock
        = (ContainerType **)trMemory()->allocateStackMemory(_numberOfNodes * sizeof(ContainerType *));
    memset(_checkExpressionsInBlock, 0, _numberOfNodes * sizeof(ContainerType *));
    return true;
}

static bool isFieldAccess(TR::Node *nextNode)
{
    if (nextNode->getOpCode().isIndirect() && nextNode->getOpCode().isLoadVar()
        && nextNode->getOpCode().hasSymbolReference() && !nextNode->getSymbolReference()->isUnresolved()
        && nextNode->getSymbolReference()->getSymbol()->isShadow() && !nextNode->isInternalPointer()
        && (!nextNode->getOpCode().isArrayLength())) {
        TR::Node *firstChild = nextNode->getFirstChild();
        if ((firstChild->getOpCodeValue() == TR::aload)
            && firstChild->getSymbolReference()->getSymbol()->isAutoOrParm())
            return true;
    }

    return false;
}

static bool nodeCanSurvive(TR::Node *nextNode, TR::Node *lastNodeFirstChild, TR::Node *lastNodeSecondChild,
    TR::Compilation *comp, bool trace)
{
    if (isFieldAccess(nextNode)) {
        intptr_t similarOffset = -1;
        bool seenSimilarAccess = false;
        TR::Node *firstChild = nextNode->getFirstChild();
        if (lastNodeFirstChild) {
            if (lastNodeFirstChild->getFirstChild()->getLocalIndex() == firstChild->getLocalIndex()) {
                similarOffset = lastNodeFirstChild->getSymbolReference()->getOffset();
                seenSimilarAccess = true;
            }
        }

        if (lastNodeSecondChild) {
            if (lastNodeSecondChild->getFirstChild()->getLocalIndex() == firstChild->getLocalIndex()) {
                if (similarOffset < lastNodeSecondChild->getSymbolReference()->getOffset())
                    similarOffset = lastNodeSecondChild->getSymbolReference()->getOffset();

                seenSimilarAccess = true;
            }
        }

        if (trace)
            traceMsg(comp, "seen similar access %d\n", seenSimilarAccess);

        if (seenSimilarAccess) {
            if (similarOffset >= nextNode->getSymbolReference()->getOffset())
                return true;

            TR::SymbolReference *symRef = firstChild->getSymbolReference();
            int32_t len;
            const char *sig = symRef->getTypeSignature(len);

            TR::SymbolReference *otherSymRef = nextNode->getSymbolReference();

            TR_OpaqueClassBlock *cl = NULL;
            if (sig && (len > 0))
                cl = comp->fe()->getClassFromSignature(sig, len, otherSymRef->getOwningMethod(comp));

            TR_OpaqueClassBlock *otherClassObject = NULL;
            int32_t otherLen;
            const char *otherSig
                = otherSymRef->getOwningMethod(comp)->classNameOfFieldOrStatic(otherSymRef->getCPIndex(), otherLen);
            if (otherSig) {
                otherSig = TR::Compiler->cls.classNameToSignature(otherSig, otherLen, comp);
                otherClassObject
                    = comp->fe()->getClassFromSignature(otherSig, otherLen, otherSymRef->getOwningMethod(comp));
            }

            if (trace)
                traceMsg(comp, "cl %p other cl %p\n", cl, otherClassObject);

            if (cl && otherClassObject && (comp->fe()->isInstanceOf(cl, otherClassObject, true) == TR_yes))
                return true;
        }
    }

    return false;
}

extern bool isExceptional(TR::Compilation *, TR::Node *); // in LocalAnalysis.cpp

bool TR_GlobalAnticipatability::isExceptionalInBlock(TR::Node *node, int32_t blockNumber, ContainerType *alreadyInBlock,
    vcount_t visitCount)
{
    if (node->getVisitCount() == visitCount)
        return false;

    node->setVisitCount(visitCount);

    int32_t i;
    for (i = 0; i < node->getNumChildren(); i++) {
        TR::Node *child = node->getChild(i);
        if (isExceptionalInBlock(child, blockNumber, alreadyInBlock, visitCount)) {
            node->setVisitCount(visitCount - 1); // so that node gets visited again for another expression in this block
            return true;
        }
    }

    if (node->getLocalIndex() != -1 && alreadyInBlock->get(node->getLocalIndex()))
        return false;

    if (isExceptional(comp(), node)) {
        node->setVisitCount(visitCount - 1);
        return true;
    } else {
        return false;
    }
}

TR_GlobalAnticipatability::ContainerType *TR_GlobalAnticipatability::getCheckExpressionsInBlock(int32_t blockNumber)
{
    return _localTransparency.getCheckExpressions();
}

bool isRareEdge(TR::Compilation *comp, TR::CFGEdge *edge)
{
    return false; // has to be performance tested with Java
    /*

    #if 0
       traceMsg (comp, "Edge from %d to %d has freq %d\n", toBlock(edge->getFrom())->getNumber(),
                                                         toBlock(edge->getTo())->getNumber(),
                                                         edge->getFrequency());
    #endif
       return (edge->getFrequency() == 1);*/
}

void TR_GlobalAnticipatability::killBasedOnSuccTransparency(TR::Block *block)
{
    TR::Block *nextSucc;
    for (auto succEdge = block->getSuccessors().begin(); succEdge != block->getSuccessors().end(); ++succEdge) {
        nextSucc = toBlock((*succEdge)->getTo());
        *_scratch = *(_localTransparency.getAnalysisInfo(nextSucc->getNumber()));
        *_scratch |= *(_localAnticipatability.getAnalysisInfo(nextSucc->getNumber()));
        *_regularInfo &= *_scratch;
    }
}

// Overrides the implementation in the superclass as this analysis
// is slightly different from conventional bit vector analyses.
// It uses the results from local analyses instead of examining
// each tree top for effects on the input bit vector at that tree top.
// This analysis has a trivial analyzeNode(...) method as a result.
//
//
void TR_GlobalAnticipatability::analyzeTreeTopsInBlockStructure(TR_BlockStructure *blockStructure)
{
    TR::Block *block = blockStructure->getBlock();
    TR::TreeTop *currentTree = block->getExit();
    TR::TreeTop *entryTree = block->getEntry();
    bool notSeenTreeWithChecks = true;

    killBasedOnSuccTransparency(block);
    copyFromInto(_regularInfo, _outSetInfo[blockStructure->getNumber()]);

    _containsExceptionTreeTop = false;
    while (!(currentTree == entryTree)) {
        if (notSeenTreeWithChecks) {
            bool currentTreeHasChecks = treeHasChecks(currentTree);
            if (currentTreeHasChecks) {
                notSeenTreeWithChecks = false;
                _containsExceptionTreeTop = true;
                compose(_regularInfo, _exceptionInfo);
                compose(_outSetInfo[blockStructure->getNumber()], _exceptionInfo);
            }
        } else
            break;

        if (!(currentTree == entryTree))
            currentTree = currentTree->getPrevTreeTop();
    }

    if (block != comp()->getFlowGraph()->getEnd()) {
        // Ignore the effect of cold blocks on anticipatability
        //
        TR::Block *next;
        bool hasNonColdSuccessor = false;
        bool analyzedSucc = true;
        for (auto edge = block->getSuccessors().begin(); edge != block->getSuccessors().end(); ++edge) {
            next = toBlock((*edge)->getTo());
            int32_t blockWeight = 1;
            if (!next->isCold())
                next->getStructureOf()->calculateFrequencyOfExecution(&blockWeight);

            bool rare = isRareEdge(comp(), *edge);

            if (!rare && blockWeight > 1 && next->getStructureOf()->hasBeenAnalyzedBefore()) {
                hasNonColdSuccessor = true;
            }

            if (!next->getStructureOf()->hasBeenAnalyzedBefore()) {
                analyzedSucc = false;
            }

            if (hasNonColdSuccessor && !analyzedSucc)
                break;
        }

        if (analyzedSucc) {
            _regularInfo->setAll(_numberOfBits);
            killBasedOnSuccTransparency(block);

            TR::Node *lastNodeFirstChild = NULL;
            TR::Node *lastNodeSecondChild = NULL;

            TR::TreeTop *lastTree = block->getLastRealTreeTop();
            if (lastTree) {
                TR::Node *lastNode = lastTree->getNode();
                if (lastNode->getOpCode().isIf()) {
                    lastNodeFirstChild = lastNode->getFirstChild();
                    if (!isFieldAccess(lastNodeFirstChild))
                        lastNodeFirstChild = NULL;

                    lastNodeSecondChild = lastNode->getSecondChild();
                    if (!isFieldAccess(lastNodeSecondChild))
                        lastNodeSecondChild = NULL;
                }
            }

            for (auto edge = block->getSuccessors().begin(); edge != block->getSuccessors().end(); ++edge) {
                next = toBlock((*edge)->getTo());
                ExtraAnalysisInfo *analysisInfo = getAnalysisInfo(next->getStructureOf());

                int32_t blockWeight = 1;
                bool rare = isRareEdge(comp(), *edge);

                if (!next->isCold())
                    next->getStructureOf()->calculateFrequencyOfExecution(&blockWeight);

                if ((!rare && !next->isCold() && blockWeight > 1) || !hasNonColdSuccessor) {
                    *_regularInfo &= *(analysisInfo->_inSetInfo);
                } else {
                    _scratch->setAll(_numberOfBits);

                    *_scratch2 = *_scratch;
                    *_scratch2 &= *_localTransparency.getCheckExpressions();
                    //*_scratch2 &= *(_localAnticipatability.getAnalysisInfo(next->getNumber()));
                    _scratch3->empty();

                    if (trace()) {
                        // traceMsg(comp(), "_scratch2 : ");
                        //_scratch2->print(comp());
                        // traceMsg(comp(), "\n");
                    }
                    if ((lastNodeFirstChild || lastNodeSecondChild) && !_scratch2->isEmpty()) {
                        ContainerType::Cursor bvi(*_scratch2);
                        for (bvi.SetToFirstOne(); bvi.Valid(); bvi.SetToNextOne()) {
                            int32_t nextExpression = bvi;
                            TR::Node *nextNode = _supportedNodesAsArray[nextExpression];
                            if (trace())
                                traceMsg(comp(), "next expression %d\n", nextExpression);
                            if (nodeCanSurvive(nextNode, lastNodeFirstChild, lastNodeSecondChild, comp(), trace())) {
                                _scratch3->set(nextExpression);
                            }
                        }
                    }

                    *_scratch -= *_localTransparency.getCheckExpressions();
                    *_scratch |= *_scratch3;
                    *_scratch |= *(analysisInfo->_inSetInfo);
                    *_regularInfo &= *_scratch;
                }
            }

            // make expressions available on both sides of 'if' if it post-dominates loop entry
            int32_t blockWeight = 1;
            blockStructure->calculateFrequencyOfExecution(&blockWeight);
            if (blockWeight > 1 && block->getFrequency() == blockStructure->getParent()->getEntryBlock()->getFrequency()
                && block->getFrequency() == (MAX_BLOCK_COUNT + MAX_COLD_BLOCK_COUNT)
                && block->isPRECandidate()) // set in loop versioner
            {
                _scratch->empty();
                for (auto edge = block->getSuccessors().begin(); edge != block->getSuccessors().end(); ++edge) {
                    next = toBlock((*edge)->getTo());
                    ExtraAnalysisInfo *analysisInfo = getAnalysisInfo(next->getStructureOf());
                    bool rare = isRareEdge(comp(), *edge);

                    int32_t blockWeight = 1;
                    if (!next->isCold())
                        next->getStructureOf()->calculateFrequencyOfExecution(&blockWeight);

                    if (!rare && blockWeight > 1) {
                        dumpOptDetails(comp(),
                            "Ignoring ifcmp within loop in block_%d and adding available expressions from block_%d\n",
                            block->getNumber(), next->getNumber());
                        *_scratch |= *(analysisInfo->_inSetInfo);
                    }
                }

                if (!_scratch->isEmpty()) {
#if 0
               *_scratch -= _localTransparency.getCheckExpressions();
#else
                    *_scratch -= *getCheckExpressionsInBlock(block->getNumber());
#endif
                    *_regularInfo |= *_scratch;
                }
            }
        }

        *_regularInfo &= *(_localTransparency.getAnalysisInfo(blockStructure->getBlock()->getNumber()));
        *_regularInfo
            |= *(_localAnticipatability.getDownwardExposedAnalysisInfo(blockStructure->getBlock()->getNumber()));
    }

    if (trace()) {
        traceMsg(comp(), "\nLocal Anticipatability of Block : %d\n", blockStructure->getBlock()->getNumber());
        _localAnticipatability.getDownwardExposedAnalysisInfo(blockStructure->getBlock()->getNumber())->print(comp());

        traceMsg(comp(), "\nIn Set of Block : %d\n", blockStructure->getNumber());
        _regularInfo->print(comp());
    }
}
