/*******************************************************************************
 * 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 "optimizer/Optimization.hpp"

#include <stddef.h>
#include <stdint.h>
#include "codegen/CodeGenerator.hpp"
#include "env/FrontEnd.hpp"
#include "compile/Compilation.hpp"
#include "cs2/allocator.h"
#include "env/IO.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/TreeTop.hpp"
#include "il/TreeTop_inlines.hpp"
#include "infra/Assert.hpp"
#include "infra/Cfg.hpp"
#include "infra/CfgEdge.hpp"
#include "optimizer/OptimizationManager.hpp"
#include "optimizer/Optimizations.hpp"
#include "optimizer/Optimization_inlines.hpp"
#include "optimizer/Optimizer.hpp"
#include "optimizer/Simplifier.hpp"
#include "optimizer/TransformUtil.hpp"

#define MAX_DEPTH_FOR_SMART_ANCHORING 3

// called once before perform is executed
void OMR::Optimization::prePerform() { self()->prePerformOnBlocks(); }

// called once after perform is executed
void OMR::Optimization::postPerform() { self()->postPerformOnBlocks(); }

TR::CodeGenerator *OMR::Optimization::cg() { return self()->comp()->cg(); }

TR_FrontEnd *OMR::Optimization::fe() { return self()->comp()->fe(); }

TR_Debug *OMR::Optimization::getDebug() { return self()->comp()->getDebug(); }

TR::SymbolReferenceTable *OMR::Optimization::getSymRefTab() { return self()->comp()->getSymRefTab(); }

TR_Memory *OMR::Optimization::trMemory() { return self()->comp()->trMemory(); }

TR_StackMemory OMR::Optimization::trStackMemory() { return self()->comp()->trStackMemory(); }

TR_HeapMemory OMR::Optimization::trHeapMemory() { return self()->comp()->trHeapMemory(); }

TR_PersistentMemory *OMR::Optimization::trPersistentMemory() { return self()->comp()->trPersistentMemory(); }

TR::Allocator OMR::Optimization::allocator() { return self()->comp()->allocator(); }

OMR::Optimizations OMR::Optimization::id() { return self()->manager()->id(); }

const char *OMR::Optimization::name() { return self()->manager()->name(); }

void OMR::Optimization::setTrace(bool trace) { self()->manager()->setTrace(trace); }

bool OMR::Optimization::traceAny()
{
    return (self()->trace() || self()->comp()->getOptions()->getAnyOption(TR_TraceAll));
}

bool OMR::Optimization::getLastRun() { return self()->manager()->getLastRun(); }

void OMR::Optimization::requestOpt(OMR::Optimizations optNum, bool value, TR::Block *block)
{
    TR::OptimizationManager *manager = self()->optimizer()->getOptimization(optNum);
    if (manager)
        manager->setRequested(value, block);
}

// useful utility functions for opts
void OMR::Optimization::requestDeadTreesCleanup(bool value, TR::Block *block)
{
    self()->requestOpt(OMR::deadTreesElimination, value, block);
    self()->requestOpt(OMR::trivialDeadTreeRemoval, value, block);
}

//---------------------------------------------------------------------
// Prepare to replace a node by changing its opcode.
// Use/def information and value number information must be given a
// chance to update themselves.
// The reference counts on all children must be decremented.
//
void OMR::Optimization::prepareToReplaceNode(TR::Node *node)
{
    // Value number information will be invalid after this optimization
    //
    self()->optimizer()->prepareForNodeRemoval(node);
    node->removeAllChildren();
}

void OMR::Optimization::prepareToReplaceNode(TR::Node *node, TR::ILOpCodes opcode)
{
    TR::Node::recreate(node, opcode);
    self()->prepareToReplaceNode(node);
}

/**
 * Anchor all first level children of a given node, use this if you are to replace the node
 * param node       The node whose children is to be anchored
 * param anchorTree The tree before which the anchor trees are to be inserted
 */
void OMR::Optimization::anchorAllChildren(TR::Node *node, TR::TreeTop *anchorTree)
{
    TR_ASSERT(anchorTree != NULL, "Can't anchor children to a NULL TR::TreeTop\n");
    if (self()->trace())
        traceMsg(self()->comp(), "%sanchoring children of node [" POINTER_PRINTF_FORMAT "]\n",
            self()->optDetailString(), node);
    for (int i = 0; i < node->getNumChildren(); i++) {
        TR::TreeTop *tt = TR::TreeTop::create(self()->comp(), TR::Node::create(TR::treetop, 1, node->getChild(i)));
        if (self()->trace())
            traceMsg(self()->comp(),
                "TreeTop [" POINTER_PRINTF_FORMAT "] is created to anchor child [" POINTER_PRINTF_FORMAT "]\n", tt,
                node->getChild(i));
        anchorTree->insertBefore(tt);
    }
}

/** anchorChildren
 *  Only anchor order dependent children
 *  \param node Root node whose children is to be anchored
 *  \param anchorTree Tree before which anchor trees will be placed
 */
void OMR::Optimization::anchorChildren(TR::Node *node, TR::TreeTop *anchorTree, uint32_t depth,
    bool hasCommonedAncestor, TR::Node *replacement)
{
    TR::Node *prevChild = NULL;

    // remaining path will be anchored to the original ancestor
    if (node == replacement)
        return;

    if (!hasCommonedAncestor) {
        hasCommonedAncestor = (node->getReferenceCount() > 1);
        if (self()->trace())
            traceMsg(self()->comp(), "set hasCommonedAncestor = %s as %s %p has refCount %d %s 1\n",
                hasCommonedAncestor ? "true" : "false", node->getOpCode().getName(), node, node->getReferenceCount(),
                hasCommonedAncestor ? ">" : "<=");
    }

    for (int j = node->getNumChildren() - 1; j >= 0; --j) {
        TR::Node *child = node->getChild(j);

        if (prevChild != child) // quite common for anchor to be called with two equal children
        {
            // For OffHeap anchoring a dataAddr load can result of its value to be live across GC points
            if (self()->nodeIsOrderDependent(child, depth, hasCommonedAncestor) && !child->isDataAddrPointer()) {
                dumpOptDetails(self()->comp(),
                    "%sanchor child %s [" POINTER_PRINTF_FORMAT "] at depth %d before %s [" POINTER_PRINTF_FORMAT "]\n",
                    self()->optDetailString(), child->getOpCode().getName(), child, depth,
                    anchorTree->getNode()->getOpCode().getName(), anchorTree->getNode());

                self()->generateAnchor(child, anchorTree);
            } else {
                self()->anchorChildren(child, anchorTree, depth + 1, hasCommonedAncestor,
                    replacement); // skipped current child, so recurse its subtree
            }
        }

        prevChild = child;
    }
}

void OMR::Optimization::generateAnchor(TR::Node *node, TR::TreeTop *anchorTree)
{
    TR_ASSERT(anchorTree != NULL, "Can't anchor children to a NULL TR::TreeTop\n");
    anchorTree->insertBefore(TR::TreeTop::create(self()->comp(), TR::Node::create(TR::treetop, 1, node)));
}

void OMR::Optimization::anchorNode(TR::Node *node, TR::TreeTop *anchorTree)
{
    if (node->getOpCode().isLoadConst() && node->anchorConstChildren()) {
        for (int32_t i = 0; i < node->getNumChildren(); i++) {
            self()->generateAnchor(node->getChild(i), anchorTree);
        }
    } else if (!node->getOpCode().isLoadConst()) {
        self()->generateAnchor(node, anchorTree);
    }
}

/**
 * Folds a given if in IL. This method does NOT update CFG
 * The callers should handle any updates to CFG or call
 * conditionalToUnconditional
 */
bool OMR::Optimization::removeOrconvertIfToGoto(TR::Node *&node, TR::Block *block, int takeBranch, TR::TreeTop *curTree,
    TR::TreeTop *&reachableTarget, TR::TreeTop *&unreachableTarget, const char *opt_details)
{
    // Either change the conditional branch to an unconditional one or remove
    // it altogether.
    // In either case the CFG must be updated to reflect the change.
    //

    node->setVirtualGuardInfo(NULL, self()->comp());

    if (takeBranch) {
        // Change the if into a goto
        //
        if (!performTransformation(self()->comp(), "%sChanging node [" POINTER_PRINTF_FORMAT "] %s into goto \n",
                opt_details, node, node->getOpCode().getName()))
            return false;
        self()->anchorChildren(node, curTree);
        self()->prepareToReplaceNode(node);
        TR::Node::recreate(node, TR::Goto);
        reachableTarget = node->getBranchDestination();
        unreachableTarget = block->getExit()->getNextTreeTop();
    } else {
        // Remove this node
        //
        if (!performTransformation(self()->comp(),
                "%sRemoving fall-through compare node [" POINTER_PRINTF_FORMAT "] %s\n", opt_details, node,
                node->getOpCode().getName()))
            return false;
        self()->anchorChildren(node, curTree);
        reachableTarget = block->getExit()->getNextTreeTop();
        unreachableTarget = node->getBranchDestination();
        // Don't call remove node as we can't suppress the removal with performTransformation any more
        self()->prepareToStopUsingNode(node, curTree);
        node->removeAllChildren();
        node = NULL;
    }

    return true;
}

/**
 * Folds a given if by updating IL, CFG and Structures.
 * If the removal of the edge caused the part of the CFG to become unreachable
 * (orphaned), it will remove the subgraph.
 *
 * The callers should be aware that the block containing the if tree might be
 * removed as well and handle such a scenario appropriately
 */
TR::CFGEdge *OMR::Optimization::changeConditionalToUnconditional(TR::Node *&node, TR::Block *block, int takeBranch,
    TR::TreeTop *curTree, const char *opt_details)
{
    TR::TreeTop *reachableTarget, *unreachableTarget;

    if (!self()->removeOrconvertIfToGoto(node, block, takeBranch, curTree, reachableTarget, unreachableTarget,
            opt_details))
        return NULL;

    // Now "unreachableTarget" contains the branch destination that is NOT being
    // taken.
    //
    TR::CFG *cfg = self()->comp()->getFlowGraph();
    TR::CFGEdge *edge = NULL;

    bool blocksWereRemoved = false;

    if (cfg) {
        if (unreachableTarget != reachableTarget) {
            TR_ASSERT(unreachableTarget->getNode()->getOpCodeValue() == TR::BBStart, "Simplifier, expected BBStart");

            TR_SuccessorIterator ei(block);
            for (edge = ei.getFirst(); edge != NULL; edge = ei.getNext())
                if (edge->getTo() == unreachableTarget->getNode()->getBlock()) {
                    blocksWereRemoved = cfg->removeEdge(edge);
                    break;
                }
        }
    } else if (takeBranch) {
        // There is no CFG so we may be dealing with extended basic blocks.
        // Remove all non-fence treetops from here to the end of the block
        //
        for (TR::TreeTop *treeTop = block->getLastRealTreeTop(), *prevTreeTop; treeTop->getNode() != node;
             treeTop = prevTreeTop) {
            prevTreeTop = treeTop->getPrevRealTreeTop();
            TR::TransformUtil::removeTree(self()->comp(), treeTop);
            blocksWereRemoved = true;
        }
    }

    return edge;
}

/**
 * Prepare to stop using a node
 */
void OMR::Optimization::prepareToStopUsingNode(TR::Node *node, TR::TreeTop *anchorTree, bool anchorChildrenNeeded)
{
    if (anchorChildrenNeeded && node->getOpCodeValue() != TR::treetop) {
        self()->anchorChildren(node, anchorTree);
    }
    if (node->getReferenceCount() <= 1) {
        self()->optimizer()->prepareForNodeRemoval(node);
    }
}

/**
 * In the special case of replacing a node with its child then anchoring is not
 * needed for the replacing child (as it and any children of its own will
 * remain anchored)
 *
 * So if all of the node's other children are constants then no anchoring at
 * all is required when replacing.
 */
TR::Node *OMR::Optimization::replaceNodeWithChild(TR::Node *node, TR::Node *child, TR::TreeTop *anchorTree,
    TR::Block *block, bool correctBCDPrecision)
{
#ifdef J9_PROJECT_SPECIFIC
    if (correctBCDPrecision && node->getType().isBCD() && child->getType().isBCD()
        && node->getDecimalPrecision() != child->getDecimalPrecision()) {
        // The extra work for BCD (packed,zoned etc) nodes on a replace node is ensuring
        // that the precision of the replacing node (child) matches the precision of the replaced
        // node (node).
        // If 'child' has a different precision than 'node' then the parent of 'node', if it is call
        // for example, will pass too many or too few digits to its callee (even digits known to be zero
        // are significant to calls to ensure the callee can demarshal the arguments correctly).
        // If the 'child' truncates then there is the danger that this truncating side-effect will be lost unless
        // a bcd modPrecOp is inserted.
        // If correctBCDPrecision=false then the caller has guaranteed that there is no danger of a child truncation
        // or widening causing any problems.
        //
        // This transformation is required for correctness so do not provide a performTransformation

        int32_t childIndex = -1;
        for (int32_t i = 0; i < node->getNumChildren(); i++) {
            if (node->getChild(i) == child) {
                childIndex = i;
            } else if (node->getChild(i)->getOpCode().isLoadConst() && node->getChild(i)->anchorConstChildren()) {
                for (int32_t j = 0; j < node->getChild(i)->getNumChildren(); j++) {
                    self()->anchorNode(node->getChild(i)->getChild(j), anchorTree);
                }
            } else if (!node->getChild(i)->getOpCode().isLoadConst()
                && node->getChild(i)->getOpCodeValue() != TR::loadaddr) {
                self()->anchorNode(node->getChild(i), anchorTree);
            }
        }
        if (childIndex == -1) {
            TR_ASSERT(false, "could not find child under node in replaceBCDNodeWithChild\n");
            return node;
        }
        if (node->getReferenceCount() > 1) {
            TR::Node *newNode = TR::Node::create(TR::ILOpCode::modifyPrecisionOpCode(child->getDataType()), 1, child);
            newNode->setDecimalPrecision(node->getDecimalPrecision());
            dumpOptDetails(self()->comp(),
                "%sPrecision mismatch when replacing parent %s [" POINTER_PRINTF_FORMAT
                "] with child %s [" POINTER_PRINTF_FORMAT "] so create new parent %s [" POINTER_PRINTF_FORMAT "]\n",
                self()->optDetailString(), node->getOpCode().getName(), node, child->getOpCode().getName(), child,
                newNode->getOpCode().getName(), newNode);
            return self()->replaceNode(node, newNode, anchorTree, false); // needAnchor=false
        } else {
            dumpOptDetails(self()->comp(),
                "%sPrecision mismatch when replacing parent %s [" POINTER_PRINTF_FORMAT
                "] with child %s [" POINTER_PRINTF_FORMAT "] so change parent op to ",
                self()->optDetailString(), node->getOpCode().getName(), node, child->getOpCode().getName(), child);
            TR_ASSERT(node->getReferenceCount() == 1, "node %p refCount should be 1 and not %d\n", node,
                node->getReferenceCount());
            child->incReferenceCount();
            // zd2pd    <- node - change to zdModifyPrecision (must use child type as modPrec is being applied to the
            // child)
            //    zdX   <- child
            //
            self()->prepareToReplaceNode(node, TR::ILOpCode::modifyPrecisionOpCode(child->getDataType()));
            node->setNumChildren(1);
            node->setChild(0, child);
            dumpOptDetails(self()->comp(), "%s\n", node->getOpCode().getName());
            if (self()->id() == OMR::treeSimplification)
                return ((TR::Simplifier *)self())->simplify(node, block);
            else
                return node;
        }
    } else
#endif
    {
        TR_ASSERT(node->hasChild(child), "node %p is not a child of node %p\n", child, node);
        bool needAnchor = false;
        for (int32_t i = 0; i < node->getNumChildren(); i++) {
            // skip anchoring for 1) the input 'child' 2) constants with no children 3) loadaddrs
            if (node->getChild(i) != child
                && (!node->getChild(i)->getOpCode().isLoadConst() || node->getChild(i)->anchorConstChildren())
                && node->getChild(i)->getOpCodeValue() != TR::loadaddr) {
                needAnchor = true;
                break;
            }
        }
        return self()->replaceNode(node, child, anchorTree, needAnchor);
    }
}

/**
 * Common routine to replace the node by another
 *
 * This routine replaces one use of this node by adjusting reference counts and
 * returning the replacing node. It is assumed that the caller will replace the
 * reference to the original node with the replacing node. The visit count on
 * the original node is reset so that it is visited again on the next reference.
 */
TR::Node *OMR::Optimization::replaceNode(TR::Node *node, TR::Node *other, TR::TreeTop *anchorTree, bool anchorChildren)
{
    if (!performTransformation(self()->comp(),
            "%sReplace node [" POINTER_PRINTF_FORMAT "] %s by [" POINTER_PRINTF_FORMAT "] %s\n",
            self()->optDetailString(), node, node->getOpCode().getName(), other, other->getOpCode().getName())) {
        if (other->getReferenceCount() == 0) {
            // Because the replacement node will not be used and it does not currently exist in the compilation unit,
            // it should be destroyed.
            other->removeAllChildren();
        }
        return node;
    }

    // Increment the reference count on the replacing node, since it will be
    // getting a new reference.
    //
    other->incReferenceCount();

    // This must be done AFTER
    // incrementing the count on the replacing node in case the replacing node is
    // a child of the original node. Otherwise we can end up deleting
    // use/def info from the child (in prepareForNodeRemoval)
    // Adjust usedef and value number information if this node is not going to
    // be used any more.
    //
    self()->prepareToStopUsingNode(node, anchorTree, anchorChildren);

    // Decrement the reference count on the original node. This must be done AFTER
    // incrementing the count on the replacing node in case the replacing node is
    // a child of the original node. In this case we don't want the count on the
    // replacing node to go to zero.
    //
    node->recursivelyDecReferenceCount();

    // If the original node still has other uses make sure it is re-visited
    // so the other references to it can be fixed up too.
    //
    if (node->getReferenceCount() > 0)
        node->setVisitCount(0);

    return other;
}

/**
 * Common routine to remove the node from the tree
 */
void OMR::Optimization::removeNode(TR::Node *node, TR::TreeTop *anchorTree)
{
    // Reduce the reference counts of all children.
    //
    if (performTransformation(self()->comp(), "%sRemoving redundant node [" POINTER_PRINTF_FORMAT "] %s\n",
            self()->optDetailString(), node, node->getOpCode().getName())) {
        self()->prepareToStopUsingNode(node, anchorTree);
        node->removeAllChildren();
    }
}

bool OMR::Optimization::nodeIsOrderDependent(TR::Node *node, uint32_t depth, bool hasCommonedAncestor)
{
    // While it may be tempting to use futureUseCount here, futureUseCount isn't well maintained in simplifier
    // and so shouldn't be used for functional items such as to anchor or not anchor a node. FutureUseCount
    // should only be used as a heuristic for optimizations.
    bool constNeedsAnchor = node->getOpCode().isLoadConst() && node->anchorConstChildren();
    return ((node->getOpCode().isLoad() && node->getOpCode().hasSymbolReference()
                && ((node->getReferenceCount() > 1) || hasCommonedAncestor))
        || ((!node->getOpCode().isLoadConst() || constNeedsAnchor) && depth >= MAX_DEPTH_FOR_SMART_ANCHORING));
}
