/*******************************************************************************
 * 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 "codegen/CodeGenerator.hpp"

#include <limits.h>
#include <stddef.h>
#include <stdint.h>
#include "codegen/CodeGenerator.hpp"
#include "codegen/CodeGenerator_inlines.hpp"
#include "codegen/LiveRegister.hpp"
#include "codegen/Register.hpp"
#include "codegen/RegisterPair.hpp"
#include "codegen/TreeEvaluator.hpp"
#include "compile/Compilation.hpp"
#include "compile/SymbolReferenceTable.hpp"
#include "control/Options.hpp"
#include "control/Options_inlines.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 "infra/Assert.hpp"
#include "infra/Stack.hpp"
#include "ras/Debug.hpp"

#ifdef J9_PROJECT_SPECIFIC
#ifdef TR_TARGET_S390
#include "z/codegen/S390Register.hpp"
#endif
#endif

TR::Register *OMR::CodeGenerator::evaluate(TR::Node *node)
{
    TR::Register *reg;

    TR::ILOpCodes opcode = node->getOpCodeValue();

    TR_ASSERT(!self()->comp()->getOption(TR_EnableParanoidRefCountChecks) || node->getOpCode().isTreeTop()
            || node->getReferenceCount() > 0,
        "OMR::CodeGenerator::evaluate invoked for nontreetop node [%s] with count == 0",
        node->getName(self()->comp()->getDebug()));

    if (opcode != TR::BBStart && node->getRegister()) {
        reg = node->getRegister();
    } else {
        // Evaluation of a TR IL tree can be performed by many functions:
        //
        // 1) evaluate(...)
        // 2) populateMemoryReference(...)
        // 3) populateAddTree(...)
        // ...
        //
        // However all of these functions can be categorized into two classes:
        //
        // A) functions which completely evaluate their subtree.
        // B) functions which partially evaluate their subtree.
        //
        // Because functions of class A and class B can be used interchangably to
        // perform a recursive decent of a TR IL tree, and because A or B functions
        // can perform a destructive evaluation of their subtree, a bug can occur where
        // the results of a partial evalutation are destructively overwritten before
        // being completely evalutated.
        //
        // Ex: the motivating case is the following evaluation pattern:
        //
        // node_A evaluate
        //    node_B populateMemoryReference
        //    node_C evaluate
        //
        // where
        //
        // a) there is a common node between the subtrees of node_B and node_C.
        // b) calling populateMemoryReference on node_B reduces the reference count of one
        //    of the base or index nodes to 1, creating the "opportunity" for a destructive
        //    evaluation.
        //
        // The following chain of events occurs:
        //
        // 1) evaluate is called on node_A. This evaluator can produce instructions of RX form,
        //    and chooses to do so for this node.
        //
        // 2) populateMemoryReference is called on node_B, and evaluates the subtree, returning
        //    a TR_MemoryReference to node_A's evaluator. This memory reference has not been
        //    dereferenced yet, and the base (and optionally index) nodes may have registers
        //    assigned to them.
        //
        // 3) evaluate is called on node_C, which chooses to destructively evaluate the commoned
        //    base node. The memory reference's base register now contains a garbage value.
        //
        // 4) control passes to node_A's evaluator, which emits an RX instruction using node_B's
        //    memory reference and node_C's register.
        //
        // In the past, the fix for this was to switch the order of evaluation: call evaluate
        // on node_C and then call populateMemoryReference on node_B. This fixes this scenario, but
        // the capability of another tree and evaluation pattern to create this bug still exists.
        //
        // As well, more insidious trees exist:
        //
        // ificmpeq
        //    iloadi
        //       i2l
        //          x
        //    iloadi
        //       ishl
        //          ==> i2l
        //          4
        //
        // The evaluation pattern here could be:
        //
        // evaluate
        //    populateMemoryReference
        //       evaluate
        //    populateMemoryReference
        //       evaluate
        //
        // If the commoned node's reference count is 2 coming into ificmpeq's evaluator, then
        // the second sub-evaluate call could be destructive to the first populateMemoryReference.
        //
        // Even worse, if either subtree could be destructive, then there would be no correct order to
        // perform the function calls:
        //
        // ificmpeq
        //    iloadi
        //       ishl
        //          ==> x
        //          7
        //    iloadi
        //       ishl
        //          ==> x
        //          4
        //
        // Generally, two conditions must be true for this bug to be possible:
        //
        // 1) the following two classes of recursive decent functions must exist:
        //    A) functions which completely evaluate their subtree.
        //    B) functions which partially evaluate their subtree.
        //
        // 2) destructive evaluation by either class of function must be possible.
        //
        // This code implements changes to eliminate the second condition for this bug by performing
        // the following check and fixup:
        //
        // If in a function which partially evaluates its subtree, note all non-restricted nodes that
        // have a reference count > 1. If any of those node's reference counts reach 1, then artificially
        // inflate those reference counts by 1 for the lifetime of the parent evaluation.
        //
        int32_t topOfNodeStackBeforeEvaluation = _stackOfArtificiallyInflatedNodes.topIndex();

        // Memory references are not like registers, and should not be allowed to escape their evaluator.
        // Explicitly note memory references that are not loaded into registers and automatically call
        // stopUsingMemRefRegister on all memory references that have "escaped".
        //
        // Only the s390 memory references are tracked in this way.
        //
        int32_t topOfMemRefStackBeforeEvaluation = _stackOfMemoryReferencesCreatedDuringEvaluation.topIndex();

        reg = _nodeToInstrEvaluators[opcode](node, self());

        if (self()->comp()->getOption(TR_TraceRegisterPressureDetails)) {
            traceMsg(self()->comp(), "  evaluated %s", self()->getDebug()->getName(node));
            self()->getDebug()->dumpLiveRegisters();
            traceMsg(self()->comp(), "\n");
        }

        // Pop off and decrement tracked nodes
        //
        while (_stackOfArtificiallyInflatedNodes.topIndex() > topOfNodeStackBeforeEvaluation) {
            TR::Node *artificiallyInflatedNode = _stackOfArtificiallyInflatedNodes.pop();

            if (artificiallyInflatedNode->getReferenceCount() == 1) {
                // When inflating reference counts, two cases exist:
                //
                // 1) N's ref count reaches 1 in a populate* call, which is then inc'ed to 2.
                //
                // 1a) N is never evaluated, so the ref count never goes down to 1. (node was not commoned in another
                // subtree)
                //
                //     - no tree difference should be seen in this case.
                //
                // 1b) N is evaluated, so the ref count then goes down to 1. (node was commoned in another subtree)
                //
                //     - register shuffling _could_ be seen in this case.
                //     - but a bug might have been avoided: partial and complete evaluation of a commoned node occurred.
                //
                if (self()->comp()->getOption(TR_TraceCG)) {
                    self()->comp()->getDebug()->trace(" _stackOfArtificiallyInflatedNodes.pop(): node %p part of "
                                                      "commoned case, might have avoided a bug!\n",
                        artificiallyInflatedNode);
                }
            }

            self()->decReferenceCount(artificiallyInflatedNode);

#ifdef J9_PROJECT_SPECIFIC
#if defined(TR_TARGET_S390)
            if (artificiallyInflatedNode->getOpaquePseudoRegister()) {
                TR_OpaquePseudoRegister *reg = artificiallyInflatedNode->getOpaquePseudoRegister();
                TR_StorageReference *ref = reg->getStorageReference();
                self()->processUnusedStorageRef(ref);
            }
#endif
#endif

            if (self()->comp()->getOption(TR_TraceCG)) {
                self()->comp()->getDebug()->trace(
                    " _stackOfArtificiallyInflatedNodes.pop() %p, decReferenceCount(...) called. reg=%s\n",
                    artificiallyInflatedNode,
                    artificiallyInflatedNode->getRegister()
                        ? artificiallyInflatedNode->getRegister()->getRegisterName(self()->comp())
                        : "null");
            }
        }

#if defined(TR_TARGET_S390)
        self()->StopUsingEscapedMemRefsRegisters(topOfMemRefStackBeforeEvaluation);
#endif

        bool checkRefCount = (node->getReferenceCount() <= 1 || (reg && reg == node->getRegister()));
        // for anchor mode, if node is an indirect store, it can have
        // ref count <= 2
        // but for compressedRefs, the indirect store must be an address
        if (self()->comp()->useAnchors()) {
            if (((node->getOpCode().isStoreIndirect()
                     && (self()->comp()->useCompressedPointers()
                         && (node->getSymbolReference()->getSymbol()->getDataType() == TR::Address)))
                    || opcode == TR::awrtbari)
                && node->getReferenceCount() <= 2 && !checkRefCount)
                checkRefCount = true;
        }

        TR_ASSERT(checkRefCount, "evaluate: the node's register wasn't set (node [%s])",
            node->getName(self()->comp()->getDebug()));
    }

    return reg;
}

int32_t OMR::CodeGenerator::whichNodeToEvaluate(TR::Node *first, TR::Node *second)
{
    // Use tree depth as an indicator of priority.
    //
    int32_t firstPriority = first->getEvaluationPriority(self());
    int32_t secondPriority = second->getEvaluationPriority(self());
    return (firstPriority >= secondPriority) ? 0 : 1;
}

int32_t OMR::CodeGenerator::whichChildToEvaluate(TR::Node *node)
{
    // Use tree depth as an indicator of priority.
    //
    int32_t nodePriority = 0;
    int32_t bestPriority = INT_MIN;
    int32_t bestChild = 0;

    for (int32_t childCount = 0; childCount < node->getNumChildren(); ++childCount) {
        TR::Node *child = node->getChild(childCount);
        int32_t childPriority = child->getEvaluationPriority(self());
        if (childPriority > bestPriority) {
            bestPriority = childPriority;
            nodePriority = childPriority + 1;
            bestChild = childCount;
        }
    }

    // Do not set the evaluation priority of a treetop node, since evaluation priority
    // is only meaningful for nodes yielding values, and treetops do not yield values.
    if (!node->getOpCode().isTreeTop()) {
        node->setEvaluationPriority(nodePriority);
    }

    return bestChild;
}

int32_t OMR::CodeGenerator::getEvaluationPriority(TR::Node *node)
{
    // Evaluation priority is the depth of the sub-tree.
    //
    int32_t nodePriority = 0;

    for (int32_t childCount = node->getNumChildren() - 1; childCount >= 0; childCount--) {
        TR::Node *child = node->getChild(childCount);
        int32_t childPriority;
        if (child->getRegister() != NULL)
            childPriority = 0;
        else
            childPriority = child->getEvaluationPriority(self());
        if (childPriority >= nodePriority)
            nodePriority = childPriority + 1;
    }

    return nodePriority;
}

rcount_t OMR::CodeGenerator::incReferenceCount(TR::Node *node)
{
    TR::Register *reg = node->getRegister();

#ifdef J9_PROJECT_SPECIFIC
#if defined(TR_TARGET_S390)
    if (reg && reg->getOpaquePseudoRegister()) {
        TR_OpaquePseudoRegister *pseudoReg = reg->getOpaquePseudoRegister();
        TR_StorageReference *pseudoRegStorageReference = pseudoReg->getStorageReference();

        TR_ASSERT(pseudoRegStorageReference, "the pseudoReg should have a non-null storage reference\n");

        pseudoRegStorageReference->incrementTemporaryReferenceCount();
    }
#endif
#endif

    rcount_t count = node->incReferenceCount();
    return count;
}

rcount_t OMR::CodeGenerator::decReferenceCount(TR::Node *node)
{
    TR::Register *reg = node->getRegister();

    if ((node->getReferenceCount() == 1) && reg && self()->getLiveRegisters(reg->getKind())) {
        TR_ASSERT(reg->isLive()
                || (diagnostic("\n*** Error: Register %s for node "
                               "[%s] died prematurely\n",
                        reg->getRegisterName(self()->comp()), node->getName(self()->comp()->getDebug())),
                    0),
            "Node %s register should be live", self()->getDebug()->getName(node));

        TR_LiveRegisterInfo *liveRegister = reg->getLiveRegisterInfo();
        TR::Register *pair = reg->getRegisterPair();
        if (pair) {
            pair->getHighOrder()->getLiveRegisterInfo()->decNodeCount();
            pair->getLowOrder()->getLiveRegisterInfo()->decNodeCount();
        }

        if (liveRegister && liveRegister->decNodeCount() == 0) {
            // The register is now dead
            //
            self()->getLiveRegisters(reg->getKind())->registerIsDead(reg);
        }
    }

#ifdef J9_PROJECT_SPECIFIC
#if defined(TR_TARGET_S390)
    if (reg && reg->getOpaquePseudoRegister()) {
        TR_OpaquePseudoRegister *pseudoReg = reg->getOpaquePseudoRegister();
        TR_StorageReference *storageReference = pseudoReg->getStorageReference();
        TR_ASSERT(storageReference, "the pseudoReg should have a non-null storage reference\n");
        storageReference->decrementTemporaryReferenceCount();
        if (node->getReferenceCount() == 1) {
            storageReference->decOwningRegisterCount();
            if (self()->traceBCDCodeGen())
                traceMsg(self()->comp(),
                    "\tdecrement owningRegisterCount %d->%d on ref #%d (%s) for reg %s as %s (%p) refCount == 1 (going "
                    "to 0)\n",
                    storageReference->getOwningRegisterCount() + 1, storageReference->getOwningRegisterCount(),
                    storageReference->getReferenceNumber(), self()->getDebug()->getName(storageReference->getSymbol()),
                    self()->getDebug()->getName(reg), node->getOpCode().getName(), node);
        }
    } else if (node->getOpCode().hasSymbolReference() && node->getSymbolReference()
        && node->getSymbolReference()->isTempVariableSizeSymRef()) {
        TR_ASSERT(false, "tempMemSlots should only be attached to pseudoRegisters and not node %p\n", node);
    }
#endif
#endif

    rcount_t count = node->decReferenceCount();
    return count;
}

rcount_t OMR::CodeGenerator::recursivelyDecReferenceCount(TR::Node *node)
{
    TR_ASSERT(!self()->comp()->getOption(TR_EnableParanoidRefCountChecks) || node->getOpCode().isTreeTop()
            || node->getReferenceCount() > 0,
        "OMR::CodeGenerator::recursivelyDecReferenceCount invoked for nontreetop node [%s] with count == 0",
        node->getName(self()->comp()->getDebug()));
    rcount_t count = self()->decReferenceCount(node);
    if (count == 0 && !node->getRegister())
        for (int16_t c = node->getNumChildren() - 1; c >= 0; c--)
            self()->recursivelyDecReferenceCount(node->getChild(c));
    return count;
}

void OMR::CodeGenerator::evaluateChildrenWithMultipleRefCount(TR::Node *node)
{
    for (int i = 0; i < node->getNumChildren(); i++) {
        TR::Node *child = node->getChild(i);
        if (child->getRegister() == NULL) // not already evaluated
        {
            // Note: we assume things without a symbol reference don't
            // necessarily need to be evaluated here, and can wait
            // until they are actually needed.
            //
            // vft pointers are speical - we need to evaluate the object in all cases
            // but for nopable virtual guards we can wait to load and mask the pointer
            // until we actually need to use it
            //
            if (child->getReferenceCount() > 1
                && (child->getOpCode().hasSymbolReference()
                    || (child->getOpCodeValue() == TR::l2a && child->getChild(0)->containsCompressionSequence()))) {
                TR::SymbolReference *vftPointerSymRef
                    = self()->comp()->getSymRefTab()->element(TR::SymbolReferenceTable::vftSymbol);
                if (node->isNopableInlineGuard() && self()->getSupportsVirtualGuardNOPing()
                    && child->getOpCodeValue() == TR::aloadi && child->getChild(0)->getOpCode().hasSymbolReference()
                    && child->getChild(0)->getSymbolReference() == vftPointerSymRef
                    && child->getChild(0)->getOpCodeValue() == TR::aloadi) {
                    if (!child->getChild(0)->getChild(0)->getRegister()
                        && child->getChild(0)->getChild(0)->getReferenceCount() > 1)
                        self()->evaluate(child->getChild(0)->getChild(0));
                    else
                        self()->evaluateChildrenWithMultipleRefCount(child->getChild(0)->getChild(0));
                } else {
                    self()->evaluate(child);
                }
            } else {
                self()->evaluateChildrenWithMultipleRefCount(child);
            }
        }
    }
}
