/*******************************************************************************
 * 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 "control/Options.hpp"
#include "control/Options_inlines.hpp"
#include "infra/deque.hpp"
#include "env/TRMemory.hpp"
#include "il/Block.hpp"
#include "infra/Assert.hpp"
#include "infra/Flags.hpp"
#include "infra/Link.hpp"
#include "infra/Stack.hpp"
#include "optimizer/Optimizations.hpp"
#include "env/IO.hpp"

namespace TR {
class ResolvedMethodSymbol;
class TreeTop;
} // namespace TR

template<typename ByteCode, ByteCode BCunknown, class ByteCodeIterator, typename OperandStackElementType>
class TR_ByteCodeIteratorWithState : public ByteCodeIterator {
public:
    typedef TR_Stack<OperandStackElementType> ByteCodeStack;

    TR_ByteCodeIteratorWithState(TR::ResolvedMethodSymbol *methodSym, TR::Compilation *comp)
        : ByteCodeIterator(methodSym, comp)
        , _unimplementedOpcode(0)
        , _inExceptionHandler(false)
        , _stack(NULL)
        , _backwardBranches()
        , _todoQueue()
        , _stackTemps(comp->trMemory(), 20)
        , _tryCatchInfo(comp->allocator("IlGen"))
    {
        _printByteCodes = (comp->getOutFile() != NULL && comp->getOption(TR_TraceBC)
            && (comp->isOutermostMethod() || comp->getOption(TR_DebugInliner) || comp->trace(OMR::inlining)));
        _cannotAttemptOSR = comp->getOption(TR_EnableOSR) && !comp->isPeekingMethod()
            && methodSym->cannotAttemptOSRDuring(comp->getCurrentInlinedSiteIndex(), comp);
    }

    void printByteCodes()
    {
        this->printByteCodePrologue();
        for (ByteCode bc = this->first(); bc != BCunknown; bc = this->next())
            this->printByteCode();
        this->printByteCodeEpilogue();
    }

protected:
    enum ByteCodeWithStateFlags {
        inExceptionRange = 0x01,
        generated = 0x02
    };

    /// used to create a worklist of bytecode indices to traverse
    struct TodoIndex : TR_Link<TodoIndex> {
        TodoIndex(int32_t i)
            : _index(i)
        {}

        int32_t _index;
    };

    /// used to store a list of edges between bytecode indices
    struct IndexPair : TR_Link<IndexPair> {
        IndexPair(int32_t f, int32_t t)
            : _fromIndex(f)
            , _toIndex(t)
        {}

        int32_t _fromIndex, _toIndex;
    };

    void initialize()
    {
        uint32_t size = this->maxByteCodeIndex() + 5;
        _flags = (flags8_t *)this->trMemory()->allocateStackMemory(size * sizeof(flags8_t));
        _blocks = (TR::Block **)this->trMemory()->allocateStackMemory(size * sizeof(TR::Block *));
        _stacks = (ByteCodeStack **)this->trMemory()->allocateStackMemory(size * sizeof(ByteCodeStack *));
        memset(_flags, 0, size * sizeof(flags8_t));
        memset(_blocks, 0, size * sizeof(TR::Block *));
        memset(_stacks, 0, size * sizeof(ByteCodeStack *));

        findAndMarkBranchTargets();
        findAndMarkExceptionRanges();

        genBBStart(0);
        setupBBStartContext(0);
        this->setIndex(0);
    }

    /// called for each control flow edge from bytecode at fromIndex, destination bytecode is fromIndex+relativeBranch
    ///   if it's a backward branch (relativeBranch < 0) then the edge is added to the _backwardBranches list
    ///   and some flags are updated on the method symbol to indicate it may have loops or, if appropriate, nested loops
    ///   finally, genBBStart is called for the destination bytecode to register that it is the start of a basic block
    void markTarget(int32_t fromIndex, int32_t relativeBranch)
    {
        int32_t toIndex = fromIndex + relativeBranch;
        if (relativeBranch < 0) {
            this->_methodSymbol->setMayHaveLoops(true);

            IndexPair *ip, *prev = 0, *newIP = new (this->comp()->trStackMemory()) IndexPair(fromIndex, toIndex);
            for (ip = _backwardBranches.getFirst(); ip; prev = ip, ip = ip->getNext()) {
                TR_ASSERT(fromIndex >= ip->_fromIndex, "markTarget: fromIndex's aren't increasing?");
                if (ip->_toIndex < toIndex || fromIndex == ip->_fromIndex)
                    break;
                if (debug("onlyConsiderProperlyNestedBackwardBranches") && ip->_toIndex == toIndex)
                    break;
                this->_methodSymbol->setMayHaveNestedLoops(true);
            }

            newIP->setNext(ip);
            if (prev)
                prev->setNext(newIP);
            else
                _backwardBranches.setFirst(newIP);
        }
        genBBStart(toIndex);
    }

    /// called to identify the branches and their targets in the method
    ///  causes the _blocks array to be filled in with the basic blocks of the method
    void findAndMarkBranchTargets()
    {
        TR::Compilation *comp = this->comp();
        if (debug("branchTargets"))
            diagnostic("findAndMarkBranchTargets for %s\n", comp->signature());

        aboutToFindBranchTargets();

        for (ByteCode bc = this->first(); bc != BCunknown; bc = this->next()) {
            if (_printByteCodes)
                this->printByteCode();

            int32_t i = this->bcIndex();
            if (this->isBranch())
                markTarget(i, this->branchDestination(i) - i);
            markAnySpecialBranchTargets(bc);
        }
        finishedFindingBranchTargets();
    }

    /// any work that should be done before starting the search for branches and targets
    virtual void aboutToFindBranchTargets()
    {
        if (_printByteCodes)
            this->printByteCodePrologue();
    }

    /// analyze any bytecodes that don't look like branches but represent control flows and suggest basic block
    /// beginnings
    virtual void markAnySpecialBranchTargets(ByteCode bc) {}

    /// any work that should be done after all the branches and their targets have been found
    virtual void finishedFindingBranchTargets()
    {
        if (_printByteCodes)
            this->printByteCodeEpilogue();
    }

    /// update state when an exception range is identified
    ///  create all the appropriate basic blocks
    ///  initialize the summary list of try catch regions
    ///  mark bytecodes in the range as having a handler (inExceptionRange)
    void markExceptionRange(int32_t index, int32_t start, int32_t end, int32_t handler, uint32_t type)
    {
        TR::Compilation *comp = this->comp();

        if (_printByteCodes)
            trfprintf(this->comp()->getOutFile(), "ExceptionRange: start [%8x] end [%8x] handler [%8x] type [%8x] \n",
                start, end, handler, type);

        genBBStart(start);
        genBBStart(end + 1);
        genBBStart(handler);

        TR_ASSERT(_tryCatchInfo.begin() + index == _tryCatchInfo.end(), "Unexpected insertion order");
        _tryCatchInfo.insert(_tryCatchInfo.begin() + index,
            typename ByteCodeIterator::TryCatchInfo(start, end, handler, type));

        for (int32_t j = start; j <= end; ++j)
            setIsInExceptionRange(j);
    }

    /// language specifies how exception ranges are discovered
    ///  some languages (like Java) encode exception ranges as meta-data alongside the bytecodes
    ///  other languages need to discover exception ranges because they aren't specified explicitly by the bytecodes
    virtual void findAndMarkExceptionRanges() = 0;

    /// called when a bytecode index is the target of a branch so it needs to be the start of a basic block
    ///  determines to which basic block the nodes for a translated bytecode will go
    void genBBStart(int32_t index)
    {
        if (!blocks(index)) {
            blocks(index) = TR::Block::createEmptyBlock(this->comp());
            blocks(index)->setByteCodeIndex(index, this->comp());
        }
    }

    /// saveStack preserves the state of the operand stack at the end of a basic block or as needed within a block
    ///  operand stack slots are saved into locals; other blocks can then access the state of the operand stack by
    ///  loading those locals
    virtual void saveStack(int32_t) = 0;

    /// called when bytecode index "index" has been identified as the target of a branch, so needs its own basic block
    ///  if queueTarget is true, target index added to the _todoQueue to make sure it is translated
    ///  genBBStart to create the basic block structure
    ///  saveStack to make sure the state of the operand stack is accessible at the beginning of the basic block
    ///  associated with target returns the TR::TreeTop to which new treetops in the target block should be appended
    TR::TreeTop *genTarget(int32_t index, bool queueTarget = true)
    {
        if (queueTarget)
            _todoQueue.append(new (this->comp()->trStackMemory()) TodoIndex(index));
        genBBStart(index);
        saveStack(index);
        return blocks(index)->getEntry();
    }

    /// called at end of a basic block with _bcIndex set to the next target
    ///  returns with the next byte code index to translate at, which may not match the target provided
    ///    if that target block has already been generated
    int32_t genBBEndAndBBStart()
    {
        genTarget(this->_bcIndex);
        return findNextByteCodeToGen();
    }

    /// initializes the operand stack state for the given bytecode index, typically called at the beginning of a basic
    /// block
    ///   returns the bytecode index provided.
    virtual int32_t setupBBStartContext(int32_t index)
    {
        if (_stacks[index] != NULL) {
            *_stack = *_stacks[index];
            _stackTemps = *_stacks[index];
        } else {
            if (_stack)
                _stack->clear();
            _stackTemps.clear();
        }

        _block = blocks(index);
        return index;
    }

    /// grabs the next basic block start from _todoQueue that has not been generated yet
    ///   once found, setupBBStartContext is called to ensure everything is ready to start translating bytecodes at that
    ///   index
    /// if nothing left to translate, returns _maxByteCode + 8 as a number bigger than the exit test for the simulation
    /// loop
    int32_t findNextByteCodeToGen()
    {
        // find and setup the next bbStart context
        //
        TodoIndex *ti;
        while (NULL != (ti = _todoQueue.pop())) {
            if (!isGenerated(ti->_index))
                return setupBBStartContext(ti->_index);
        }

        return this->maxByteCodeIndex() + 8; // indicate that we're done
    }

    /// returns true if the bytecode index i is part of an exception range (try block)
    bool isInExceptionRange(int32_t i) { return _flags[i].testAny(inExceptionRange); }

    /// remember that the bytecode index i is part of an exception range (try block)
    void setIsInExceptionRange(int32_t i) { _flags[i].set(inExceptionRange); }

    /// returns true if the bytecode at index i has already been generated (translated to IR)
    bool isGenerated(int32_t i) { return _flags[i].testAny(generated); }

    /// remember that the bytecode at index i has already been generated (translated to IR)
    void setIsGenerated(int32_t i) { _flags[i].set(generated); }

    /// return the basic block that starts at byte code index i
    TR::Block *&blocks(int32_t i) { return _blocks[i]; }

    /// return the i'th element in the operand stack (numbered from the bottom of the operand stack, not the top)
    OperandStackElementType &node(uint32_t i) { return _stack->element(i); }

    /// return the top element on the operand stack
    OperandStackElementType &top() { return topn(0); }

    /// return the top n-th element on the operand stack
    OperandStackElementType &topn(uint32_t n) { return node(_stack->topIndex() - n); }

    /// return the top element of the operand stack and pop it off the operand stack
    OperandStackElementType pop() { return _stack->pop(); }

    /// pop n elements from the top of the stack
    void popn(uint32_t n) { _stack->setSize(_stack->size() - n); }

    /// push the element onto the operand stack
    void push(OperandStackElementType n) { _stack->push(n); }

    /// swap the top two elements of the operand stack
    void swap() { _stack->swap(); }

    /// sets the n'th element from the top to the new element e
    void setn(int32_t n, OperandStackElementType e) { topn(n) = e; }

    /// duplicate the top of the operand stack
    void dup() { dupn(1); }

    /// duplicate the top n elements of the operand stack
    void dupn(int32_t n) { shift(n, n); }

    /// generic helper routine for shifting duplicates of existing operand stack elements to the top
    ///   first grow the stack by copyCount then shift part of the operand stack (from top) up to the new top
    ///   NOTE: if copyCount > shiftCount then (copyCount - shiftCount) elements above the top of the original operand
    ///   stack will not be set
    void shift(int32_t shiftCount, int32_t copyCount)
    {
        _stack->setSize(_stack->size() + copyCount);
        for (int32_t i = 0; i < shiftCount; ++i)
            node(_stack->topIndex() - i) = node(_stack->topIndex() - i - copyCount);
    }

    /// generic helper routine for shifting and then copying elements of the operand stack
    ///   first shifts operand stack by shiftCount, then copies the shifted elements underneath the shifted operand
    ///   stack values
    void shiftAndCopy(int32_t shiftCount, int32_t copyCount)
    {
        shift(shiftCount, copyCount);
        for (int32_t i = 0; i < copyCount; ++i)
            node(_stack->topIndex() - i - shiftCount) = node(_stack->topIndex() - i);
    }

    /// rotates "countArg" elements off the top to the bottom of the operand stack
    ///    Expected: -operand stack size <= countArg <= operand stack size
    ///
    ///    \warning Make sure you know what you're doing regarding pending push
    ///             temps or you'll mess up FSD because of this rotation
    void rotate(int32_t countArg)
    {
        uint32_t count;
        if (countArg < 0)
            count = (uint32_t)(_stack->size() + countArg);
        else
            count = (uint32_t)countArg;

        // Duplicate the entries that will wrap around to the cold end of the operand stack
        uint32_t oldSize = _stack->size();
        shift(oldSize, count);

        // Move them to the cold end and then discard the duplicates
        //
        for (uint32_t i = 0; i < count; ++i)
            node(i) = node(oldSize + i);

        _stack->setSize(oldSize);
    }

    ByteCodeStack *_stack; ///< current operand stack
    ByteCodeStack _stackTemps;
    ByteCodeStack **_stacks;
    TR::Block *_block; ///< current block
    TR::Block **_blocks;
    TR_LinkHeadAndTail<TodoIndex> _todoQueue;
    TR_LinkHead<IndexPair> _backwardBranches;
    bool _inExceptionHandler;
    bool _printByteCodes;
    bool _cannotAttemptOSR;

    flags8_t *_flags;

    uint8_t _unimplementedOpcode; ///< (255 if opcode unknown)
    TR::deque<class ByteCodeIterator::TryCatchInfo> _tryCatchInfo;
};
