/*******************************************************************************
 * 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 <stddef.h>
#include <stdint.h>
#include "compile/Compilation.hpp"
#include "compile/SymbolReferenceTable.hpp"
#include "control/Options.hpp"
#include "control/Options_inlines.hpp"
#include "cs2/allocator.h"
#include "env/TRMemory.hpp"
#include "il/AliasSetInterface.hpp"
#include "il/AutomaticSymbol.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/ParameterSymbol.hpp"
#include "il/RegisterMappedSymbol.hpp"
#include "il/ResolvedMethodSymbol.hpp"
#include "il/Symbol.hpp"
#include "il/SymbolReference.hpp"
#include "il/TreeTop.hpp"
#include "il/TreeTop_inlines.hpp"
#include "infra/Assert.hpp"
#include "infra/BitVector.hpp"
#include "infra/Cfg.hpp"
#include "infra/List.hpp"
#include "infra/CfgNode.hpp"
#include "optimizer/DataFlowAnalysis.hpp"
#include "ras/Debug.hpp"

class TR_Structure;

namespace TR {
class Optimizer;
}

TR_LiveVariableInformation::TR_LiveVariableInformation(TR::Compilation *c, TR::Optimizer *optimizer,
    TR_Structure *rootStructure, bool splitLongs, bool includeParms, bool ignoreOSRUses)
    : _compilation(c)
    , _trMemory(c->trMemory())
    , _ignoreOSRUses(ignoreOSRUses)
{
    _traceLiveVariableInfo = comp()->getOption(TR_TraceLiveness);

    // Find the number of locals and assign an index to each
    //
    _numLocals = 0;
    _includeParms = includeParms;
    _splitLongs = splitLongs;

    _localObjects = NULL;
    _cachedRegularGenSetInfo = NULL;
    _cachedRegularKillSetInfo = NULL;
    _cachedExceptionGenSetInfo = NULL;
    _cachedExceptionKillSetInfo = NULL;

    _haveCachedGenAndKillSets = false;
    _liveCommonedLoads = NULL;
    _seenCommonedNodeForLoadOfLocal = NULL;
    _distinctCommonedLoads = NULL;
}

void TR_LiveVariableInformation::collectLiveVariableInformation()
{
    if (traceLiveVarInfo())
        traceMsg(comp(), "Collecting live variable information\n");
    if (_includeParms) {
        TR::ParameterSymbol *p;
        ListIterator<TR::ParameterSymbol> parms(&comp()->getMethodSymbol()->getParameterList());
        for (p = parms.getFirst(); p != NULL; p = parms.getNext()) {
            if (traceLiveVarInfo())
                traceMsg(comp(), "#%2d : is a parm symbol at %p\n", _numLocals, p);

            if (p->getType().isInt64() && _splitLongs) {
                p->setLiveLocalIndex(_numLocals, comp()->fe());
                _numLocals += 2;
            } else
                p->setLiveLocalIndex(_numLocals++, comp()->fe());
        }
    }

    TR::AutomaticSymbol *p;
    ListIterator<TR::AutomaticSymbol> locals(&comp()->getMethodSymbol()->getAutomaticList());
    for (p = locals.getFirst(); p != NULL; p = locals.getNext()) {
        if (traceLiveVarInfo())
            traceMsg(comp(), "Local #%2d is symbol at %p\n", _numLocals, p);

        if (p->getType().isInt64() && _splitLongs) {
            p->setLiveLocalIndex(_numLocals, comp()->fe());
            _numLocals += 2;
        } else
            p->setLiveLocalIndex(_numLocals++, comp()->fe());
    }

    if (traceLiveVarInfo())
        traceMsg(comp(), "Finished collecting live variable information: %d locals found\n", _numLocals);

    _localObjects = NULL;
    _cachedRegularGenSetInfo = NULL;
    _cachedRegularKillSetInfo = NULL;
    _cachedExceptionGenSetInfo = NULL;
    _cachedExceptionKillSetInfo = NULL;

    _haveCachedGenAndKillSets = false;
    _liveCommonedLoads = NULL;
}

void TR_LiveVariableInformation::createGenAndKillSetCaches()
{
    _numNodes = comp()->getFlowGraph()->getNextNodeNumber();
    int32_t arraySize = _numNodes * sizeof(TR_BitVector *);
    _cachedRegularGenSetInfo = (TR_BitVector **)trMemory()->allocateStackMemory(arraySize);
    _cachedRegularKillSetInfo = (TR_BitVector **)trMemory()->allocateStackMemory(arraySize);
    _cachedExceptionGenSetInfo = (TR_BitVector **)trMemory()->allocateStackMemory(arraySize);
    _cachedExceptionKillSetInfo = (TR_BitVector **)trMemory()->allocateStackMemory(arraySize);

    // need to allocate each block's sets here or else they may be allocated above an inner stack mark
    // and then be de-allocated before they get re-used
    for (int32_t b = 0; b < _numNodes; b++) {
        _cachedRegularGenSetInfo[b] = new (trStackMemory()) TR_BitVector(_numLocals, trMemory());
        _cachedRegularKillSetInfo[b] = new (trStackMemory()) TR_BitVector(_numLocals, trMemory());
        _cachedExceptionGenSetInfo[b] = new (trStackMemory()) TR_BitVector(_numLocals, trMemory());
        _cachedExceptionKillSetInfo[b] = new (trStackMemory()) TR_BitVector(_numLocals, trMemory());
    }

    _haveCachedGenAndKillSets = false;
}

void TR_LiveVariableInformation::initializeGenAndKillSetInfo(TR_BitVector **regularGenSetInfo,
    TR_BitVector **regularKillSetInfo, TR_BitVector **exceptionGenSetInfo, TR_BitVector **exceptionKillSetInfo)
{
    if (_haveCachedGenAndKillSets) {
        TR_ASSERT(comp()->getFlowGraph()->getNextNodeNumber() == _numNodes,
            "flow graph has changed since gen and kill sets were initialized");
        // copy our cached sets into the arrays being passed to us
        for (int32_t nodeNumber = 0; nodeNumber < _numNodes; nodeNumber++) {
            if (_cachedRegularGenSetInfo[nodeNumber] != NULL) {
                regularGenSetInfo[nodeNumber] = new (trStackMemory()) TR_BitVector(_numLocals, trMemory(), stackAlloc);
                *(regularGenSetInfo[nodeNumber]) = *(_cachedRegularGenSetInfo[nodeNumber]);
            }

            if (_cachedRegularKillSetInfo[nodeNumber] != NULL) {
                regularKillSetInfo[nodeNumber] = new (trStackMemory()) TR_BitVector(_numLocals, trMemory(), stackAlloc);
                *(regularKillSetInfo[nodeNumber]) = *(_cachedRegularKillSetInfo[nodeNumber]);
            }

            if (_cachedExceptionGenSetInfo[nodeNumber] != NULL) {
                exceptionGenSetInfo[nodeNumber]
                    = new (trStackMemory()) TR_BitVector(_numLocals, trMemory(), stackAlloc);
                *(exceptionGenSetInfo[nodeNumber]) = *(_cachedExceptionGenSetInfo[nodeNumber]);
            }

            if (_cachedExceptionKillSetInfo[nodeNumber] != NULL) {
                exceptionKillSetInfo[nodeNumber]
                    = new (trStackMemory()) TR_BitVector(_numLocals, trMemory(), stackAlloc);
                *(exceptionKillSetInfo[nodeNumber]) = *(_cachedExceptionKillSetInfo[nodeNumber]);
            }
        }
        return;
    }

    // allocate bit vector to store local objects as they are found by findUseOfLocal
    _localObjects = new (trStackMemory()) TR_BitVector(_numLocals, trMemory());

    // For each block in the CFG build the gen and kill set for this analysis.
    // Go in treetop order, which guarantees that we see the correct (i.e. first)
    // evaluation point for each node.
    //
    vcount_t visitCount = comp()->incVisitCount();
    TR::Block *block;
    int32_t blockNum = 0;
    bool seenException = false;

    bool ignoreBlock = false;
    for (TR::TreeTop *treeTop = comp()->getStartTree(); treeTop; treeTop = treeTop->getNextTreeTop()) {
        TR::Node *node = treeTop->getNode();
        if (node->getOpCodeValue() == TR::BBEnd && ignoreBlock) {
            ignoreBlock = false;
            continue;
        }
        if (ignoreBlock)
            continue;

        if (node->getOpCodeValue() == TR::BBStart) {
            block = node->getBlock();
            blockNum = block->getNumber();
            seenException = false;
            if (_ignoreOSRUses && (block->isOSRCodeBlock() || block->isOSRCatchBlock())) {
                ignoreBlock = true;
                continue;
            }
            if (traceLiveVarInfo())
                traceMsg(comp(), "\nNow generating liveness information for block_%d\n", blockNum);
        }

        // Find uses of locals in this tree.
        //
        findUseOfLocal(node, blockNum, regularGenSetInfo, regularKillSetInfo, NULL, true, visitCount);
        if (_cachedRegularGenSetInfo && regularGenSetInfo[blockNum] != NULL) {
            *(_cachedRegularGenSetInfo[blockNum]) = *(regularGenSetInfo[blockNum]);
            if (!seenException) {
                if (exceptionGenSetInfo[blockNum] == NULL)
                    exceptionGenSetInfo[blockNum]
                        = new (trStackMemory()) TR_BitVector(_numLocals, trMemory(), stackAlloc);
                *(exceptionGenSetInfo[blockNum]) = *(regularGenSetInfo[blockNum]);
                if (_cachedExceptionGenSetInfo != NULL)
                    *(_cachedExceptionGenSetInfo[blockNum]) = *(regularGenSetInfo[blockNum]);
            }
        }

        if (node->getOpCodeValue() == TR::treetop)
            node = node->getFirstChild();

        if (node->getOpCode().isStoreDirect()) {
            TR::RegisterMappedSymbol *local = node->getSymbolReference()->getSymbol()->getAutoSymbol();
            if (!local && _includeParms)
                local = node->getSymbolReference()->getSymbol()->getParmSymbol();

            if (local) {
                uint16_t localIndex = local->getLiveLocalIndex();

                if (localIndex != INVALID_LIVENESS_INDEX) {
                    if (traceLiveVarInfo())
                        traceMsg(comp(), "\n Killing symbol with local index %d in block_%d\n", localIndex, blockNum);

                    if (regularKillSetInfo[blockNum] == NULL)
                        regularKillSetInfo[blockNum]
                            = new (trStackMemory()) TR_BitVector(_numLocals, trMemory(), stackAlloc);
                    regularKillSetInfo[blockNum]->set(localIndex);
                    if (_cachedRegularKillSetInfo)
                        _cachedRegularKillSetInfo[blockNum]->set(localIndex);

                    if (_splitLongs && local->getType().isInt64()) {
                        regularKillSetInfo[blockNum]->set(localIndex + 1);
                        if (_cachedRegularKillSetInfo)
                            _cachedRegularKillSetInfo[blockNum]->set(localIndex + 1);
                    }

                    if (!seenException) {
                        if (exceptionKillSetInfo[blockNum] == NULL)
                            exceptionKillSetInfo[blockNum]
                                = new (trStackMemory()) TR_BitVector(_numLocals, trMemory(), stackAlloc);
                        exceptionKillSetInfo[blockNum]->set(localIndex);
                        if (_cachedExceptionKillSetInfo)
                            _cachedExceptionKillSetInfo[blockNum]->set(localIndex);

                        if (_splitLongs && local->getType().isInt64()) {
                            exceptionKillSetInfo[blockNum]->set(localIndex + 1);
                            if (_cachedExceptionKillSetInfo)
                                _cachedExceptionKillSetInfo[blockNum]->set(localIndex + 1);
                        }
                    }
                }
            }
        }

        if (!seenException && node->exceptionsRaised() != 0)
            seenException = true;
    }

    // if any local objects were found, mark them as gen'd in all blocks
    if (!_localObjects->isEmpty()) {
        for (TR::CFGNode *cfgNode = _compilation->getFlowGraph()->getFirstNode(); cfgNode;
             cfgNode = cfgNode->getNext()) {
            TR::Block *b = cfgNode->asBlock();
            if (b) {
                int32_t blockNum = b->getNumber();

                if (traceLiveVarInfo())
                    traceMsg(comp(), "            Adding local objects to gen set for block_%d\n", blockNum);

                if (regularGenSetInfo[blockNum] == NULL)
                    regularGenSetInfo[blockNum]
                        = new (trStackMemory()) TR_BitVector(_numLocals, trMemory(), stackAlloc);
                *regularGenSetInfo[blockNum] |= *_localObjects;
                if (_cachedRegularGenSetInfo)

                    *_cachedRegularGenSetInfo[blockNum] |= *_localObjects;

                if (exceptionGenSetInfo[blockNum] == NULL)
                    exceptionGenSetInfo[blockNum]
                        = new (trStackMemory()) TR_BitVector(_numLocals, trMemory(), stackAlloc);
                *exceptionGenSetInfo[blockNum] |= *_localObjects;
                if (_cachedExceptionGenSetInfo)
                    *_cachedExceptionGenSetInfo[blockNum] |= *_localObjects;
            }
        }
    }
    _localObjects = NULL;

    if (_cachedRegularGenSetInfo) {
        // clear out empty sets in the cached versions
        for (int32_t b = 0; b < _numNodes; b++) {
            if (regularGenSetInfo[b] == NULL)
                _cachedRegularGenSetInfo[b] = NULL;
            if (regularKillSetInfo[b] == NULL)
                _cachedRegularKillSetInfo[b] = NULL;
            if (exceptionGenSetInfo[b] == NULL)
                _cachedExceptionGenSetInfo[b] = NULL;
            if (exceptionKillSetInfo[b] == NULL)
                _cachedExceptionKillSetInfo[b] = NULL;
        }

        _haveCachedGenAndKillSets = true;
    }
}

// call this method to force findUseOfLocal to track uses of live commoned loads
// i.e. if a tree contains a commoned reference to a load of a local, then
void TR_LiveVariableInformation::trackLiveCommonedLoads()
{
    _liveCommonedLoads = new (trStackMemory()) TR_BitVector(_numLocals, trMemory());
}

void TR_LiveVariableInformation::findCommonedLoads(TR::Node *node, TR_BitVector *commonedLoads,
    bool movingForwardThroughTrees, vcount_t visitCount)
{
    TR_ASSERT(commonedLoads, "asked to collect commoned loads, but no bit vector passed in");
    visitTreeForLocals(node, NULL, NULL, movingForwardThroughTrees, true, visitCount, commonedLoads, false);
}

void TR_LiveVariableInformation::findAllUseOfLocal(TR::Node *node, int32_t blockNum, TR_BitVector *genSetInfo,
    TR_BitVector *killSetInfo, TR_BitVector *commonedLoads, bool movingForwardThroughTrees, vcount_t visitCount)
{
    visitTreeForLocals(node, &genSetInfo, killSetInfo, movingForwardThroughTrees, true, visitCount, commonedLoads,
        false);
}

void TR_LiveVariableInformation::findLocalUsesInBackwardsTreeWalk(TR::Node *node, int32_t blockNum,
    TR_BitVector *genSetInfo, TR_BitVector *killSetInfo, TR_BitVector *commonedLoads, vcount_t visitCount)
{
    TR_ASSERT(commonedLoads != NULL, "can't do a backward tree walk properly unless recording commoned loads for tree");
    visitTreeForLocals(node, &genSetInfo, killSetInfo, false, true, visitCount, commonedLoads, false);
}

void TR_LiveVariableInformation::findUseOfLocal(TR::Node *node, int32_t blockNum, TR_BitVector **genSetInfo,
    TR_BitVector **killSetInfo, TR_BitVector *commonedLoads, bool movingForwardThroughTrees, vcount_t visitCount)
{
    visitTreeForLocals(node, genSetInfo + blockNum, killSetInfo[blockNum], movingForwardThroughTrees, false, visitCount,
        commonedLoads, false);
}

// movingForwardThroughTrees describes how the client is walking treetops
// for walking trees forwards, use visit count to determine when nodes have been visited
// for walking trees backwards, use future use counts to determine the last reference and only look at those
//    last uses (because they're actually the first references in the block)
// if visitEntireTree is true, then the backward traversal will continue under commoned nodes but belowCommonedNode will
// be set
//    NOTE: forward traversals cannot rely on visitEntireTree
// belowCommonedNode is used to track when we're traversing a commoned part of a node's tree or not (on first call, pass
// in false) if commonedLoads is non-null, then any symbols loaded while belowCommonedNode is set are marked in that bit
// vector if visitCount is >= 0, then it will be used to avoid visiting nodes multiple times
//    NOTE: if a node has its visit count set to visitCount, it will not be visited unless visitEntireTree is set
//    NOTE: for backward traversals a new visit count is needed for each treetop in an EBB to visit correctly and
//    efficiently
void TR_LiveVariableInformation::visitTreeForLocals(TR::Node *node, TR_BitVector **blockGenSetInfo,
    TR_BitVector *blockKillSetInfo, bool movingForwardThroughTrees, bool visitEntireTree, vcount_t visitCount,
    TR_BitVector *commonedLoads, bool belowCommonedNode)
{
    if (movingForwardThroughTrees) {
        TR_ASSERT(!visitEntireTree, "can't walk trees forwards and visit entire tree");
        TR_ASSERT(visitCount >= 0, "can't walk trees forwards without a visitCount");
    }

    if (traceLiveVarInfo()) {
        if (movingForwardThroughTrees)
            traceMsg(comp(),
                "         Looking forward for uses in node %p has visitCount = %d and comp() visitCount = %d\n", node,
                node->getVisitCount(), visitCount);
        else
            traceMsg(comp(),
                "         Looking backward for uses in node %p has future use count = %d and reference count = %d\n",
                node, node->getFutureUseCount(), node->getReferenceCount());
    }

    uint16_t localIndex = INVALID_LIVENESS_INDEX;
    TR::RegisterMappedSymbol *local = NULL;

    // TR::SymbolReference *symRef = node->getSymbolReference();
    if (node->getOpCode().isLoadVarDirect() || node->getOpCodeValue() == TR::loadaddr) {
        local = node->getSymbolReference()->getSymbol()->getAutoSymbol();
        if (!local && _includeParms)
            local = node->getSymbolReference()->getSymbol()->getParmSymbol();
        if (local) {
            localIndex = local->getLiveLocalIndex();
            if (localIndex == INVALID_LIVENESS_INDEX)
                local = NULL; // don't analyze this local if localIndex == INVALID_LIVENESS_INDEX
        }
    }
    // if local != NULL at this point, then we have a load of a local with index in localIndex

    // figure out if we should be visiting this node
    if (movingForwardThroughTrees) {
        // if we're below a commoned node, then we must be visiting the entire tree so just keep going
        if (!belowCommonedNode) {
            // maybe we should end traversal here?
            if (node->getVisitCount() == visitCount) {
                if (visitEntireTree)
                    belowCommonedNode = true;
                else
                    // this node has already been visited and we're not supposed to visit the entire tree
                    return;
            } else
                node->setVisitCount(visitCount);
        }
    } else {
        // if we're below a commoned node, then we must be visiting the entire tree so just keep going
        if (!belowCommonedNode) {
            if (node->getFutureUseCount() > 0)
                node->decFutureUseCount();
            if (node->getFutureUseCount() > 0) {
                if (traceLiveVarInfo())
                    traceMsg(comp(), "            not first reference\n");

                if (_liveCommonedLoads != NULL && local != NULL) {
                    if (_seenCommonedNodeForLoadOfLocal == NULL) {
                        _seenCommonedNodeForLoadOfLocal = new (trStackMemory()) TR::NodeChecklist(comp());
                        _distinctCommonedLoads
                            = (int32_t *)comp()->trMemory()->allocateStackMemory(_numLocals * sizeof(int32_t));
                        memset(_distinctCommonedLoads, 0x0, _numLocals * sizeof(int32_t));
                    }

                    // Has this load of a local variable been encountered before in this backwards
                    // tree walk?  If not, add the node to the checklist and bump the number of distinct
                    // commoned loads of the local variable.
                    //
                    if (!_seenCommonedNodeForLoadOfLocal->contains(node)) {
                        _seenCommonedNodeForLoadOfLocal->add(node);
                        _distinctCommonedLoads[localIndex] = _distinctCommonedLoads[localIndex] + 1;
                    }
                }

                // traversal should either end here (for regular traversal) or track that we're below a commoned node
                if (visitEntireTree)
                    belowCommonedNode = true;
                else
                    return;
            } else {
                bool otherReferencesStillLive = false;

                // if this is a load, and there are no other live commoned loads of the local,
                // clear it in liveCommonedLoads if we've been asked to track them
                if (_liveCommonedLoads != NULL && local != NULL) {
                    if (_seenCommonedNodeForLoadOfLocal != NULL) {
                        // If we've encountered a commoned reference to this node, decrease
                        // the number of distinct commoned references of the local that are
                        // are still live.  If there are no more live commoned references to
                        // the local, remove it from _liveCommonedLoads
                        //
                        if (_seenCommonedNodeForLoadOfLocal->contains(node)) {
                            int32_t numDistinctCommonedLoads = _distinctCommonedLoads[localIndex];
                            _distinctCommonedLoads[localIndex] = numDistinctCommonedLoads - 1;

                            _seenCommonedNodeForLoadOfLocal->remove(node);

                            if (numDistinctCommonedLoads == 1) {
                                _liveCommonedLoads->reset(localIndex);
                            } else {
                                otherReferencesStillLive = true;
                            }
                        }
                    } else {
                        _liveCommonedLoads->reset(localIndex);
                    }
                }

                if (traceLiveVarInfo()) {
                    if (otherReferencesStillLive) {
                        traceMsg(comp(),
                            "            First reference to this node, but other commoned references to this local sym "
                            "are still live\n");
                    } else {
                        if (local != NULL) {
                            traceMsg(comp(),
                                "            First reference to this node, and either this is the first of all "
                                "commoned references to this sym or this it is not a commoned reference\n");
                        } else {
                            traceMsg(comp(), "            First reference to this node\n");
                        }
                    }
                }
            }
        }

        // visit count used to detect commoned nodes WITHIN each tree: visit count must be different for each tree in an
        // EBB for this to work properly ...IF the visit count isn't different for each tree, this DOES NOT WORK
        // PROPERLY
        if (node->getVisitCount() == visitCount && node->getFutureUseCount() > 0)
            return;
        node->setVisitCount(visitCount);
    }

    // if we get here, then we should visit this node

    // go look for symbols in node's children
    for (int32_t i = 0; i < node->getNumChildren(); ++i)
        visitTreeForLocals(node->getChild(i), blockGenSetInfo, blockKillSetInfo, movingForwardThroughTrees,
            visitEntireTree, visitCount, commonedLoads, belowCommonedNode);

    // if we reference a local symbol, then record it
    if (local) {
        if (traceLiveVarInfo() && local)
            traceMsg(comp(), "            Node [%p] local [%p] idx %d\n", node, local, localIndex);

        if (belowCommonedNode) {
            if (commonedLoads != NULL && local) {
                if (traceLiveVarInfo())
                    traceMsg(comp(), "              Marking as commoned load\n");
                commonedLoads->set(localIndex);
            } else {
                if (traceLiveVarInfo())
                    traceMsg(comp(), "              Commoned load, but not asked to remember it\n");
            }
            if (_liveCommonedLoads != NULL) {
                if (traceLiveVarInfo())
                    traceMsg(comp(), "              Marking %d as live commoned load\n", localIndex);
                _liveCommonedLoads->set(localIndex);

                if (!movingForwardThroughTrees && _seenCommonedNodeForLoadOfLocal != NULL) {
                    // Has this load of a local variable been encountered before in this backwards
                    // tree walk?  If not, add the node to the checklist and bump the number of distinct
                    // commoned loads of the local variable.
                    //
                    if (!_seenCommonedNodeForLoadOfLocal->contains(node)) {
                        _distinctCommonedLoads[localIndex] = _distinctCommonedLoads[localIndex] + 1;
                        _seenCommonedNodeForLoadOfLocal->add(node);
                    }
                }
            }
        }
        if (_localObjects != NULL && local && local->isLocalObject()) {
            // First use of a local object.
            // This local object will be live throughout the method,
            // so mark it as generated in the exit block.
            //
            TR_ASSERT(node->getOpCodeValue() == TR::loadaddr, "assertion failure");
            _localObjects->set(localIndex);
            if (traceLiveVarInfo())
                traceMsg(comp(), "            Marking local object\n");
        } else if (!belowCommonedNode && blockGenSetInfo)

        {
            // This local is in the gen set if we haven't already seen a kill
            // for it
            //
            if (!movingForwardThroughTrees || blockKillSetInfo == NULL || (local && !blockKillSetInfo->get(localIndex)))
            //! blockKillSetInfo->get(localIndex))
            {
                if (traceLiveVarInfo() && local)
                    traceMsg(comp(), "            Gening symbol with local index %d\n", localIndex);

                if (*blockGenSetInfo == NULL)
                    *blockGenSetInfo = new (trStackMemory()) TR_BitVector(_numLocals, trMemory(), stackAlloc);

                if (local)
                    (*blockGenSetInfo)->set(localIndex);

                if (_splitLongs && local && local->getType().isInt64()) {
                    (*blockGenSetInfo)->set(localIndex + 1);
                }
            }
        }
    }
    return;
}

/*
 * Solve gen set for a given node. If the node is an OSR point, consider the symbols that are alive if the
 * program is interpreted. Add those symbols to the basic gen set.
 */
void TR_OSRLiveVariableInformation::findUseOfLocal(TR::Node *node, int32_t blockNum, TR_BitVector **genSetInfo,
    TR_BitVector **killSetInfo, TR_BitVector *commonedLoads, bool movingForwardThroughTrees, vcount_t visitCount)
{
    TR_LiveVariableInformation::findUseOfLocal(node, blockNum, genSetInfo, killSetInfo, commonedLoads,
        movingForwardThroughTrees, visitCount);
    if (comp()->isPotentialOSRPoint(node)) {
        TR_BitVector *liveSymbols = getLiveSymbolsInInterpreter(node->getByteCodeInfo());
        if (killSetInfo[blockNum])
            *liveSymbols -= *killSetInfo[blockNum];
        TR_BitVector **blockGenSetInfo = genSetInfo + blockNum;
        if (comp()->getOption(TR_TraceOSR)) {
            traceMsg(comp(), "liveSymbols introduced by real uses at OSRPoint node n%dn:", node->getGlobalIndex());
            liveSymbols->print(comp());
            traceMsg(comp(), "\n");
        }

        if (!liveSymbols->isEmpty()) {
            if (*blockGenSetInfo == NULL)
                *blockGenSetInfo = new (trStackMemory()) TR_BitVector(numLocals(), trMemory(), stackAlloc);

            *(*blockGenSetInfo) |= *liveSymbols;
        }
    }
}

/*
 * \brief Calculate live symbols for a BCI for a method based on OSRLiveRangeInfo
 *
 * @param osrMethodData
 * @param byteCodeIndex BCI of the OSRPoint
 * @param liveLocals The bit vector keeping liveness info
 *
 * OSRLiveRangeInfo keeps all the dead symbol reference numbers for a bci in a given caller. This function use the total
 * autos or pend
 */
void TR_OSRLiveVariableInformation::buildLiveSymbolsBitVector(TR_OSRMethodData *osrMethodData, int32_t byteCodeIndex,
    TR_BitVector *liveLocals)
{
    if (osrMethodData == NULL || osrMethodData->getSymRefs() == NULL)
        return;
    TR_BitVector *deadSymRefs = osrMethodData->getLiveRangeInfo(byteCodeIndex);
    TR_BitVector *liveSymRefs = new (comp()->trStackMemory()) TR_BitVector(0, trMemory(), stackAlloc);

    *liveSymRefs |= *osrMethodData->getSymRefs();
    if (deadSymRefs != NULL)
        *liveSymRefs -= *deadSymRefs;
    DefiningMap *definingMap = osrMethodData->getDefiningMap();

    TR_BitVectorIterator liveSymRefIt(*liveSymRefs);
    while (liveSymRefIt.hasMoreElements()) {
        int32_t symRefNumber = liveSymRefIt.getNextElement();
        // if the symbol can't be found in definigMap don't need to set any gen set bit
        // because it must be defined by a constant
        if (definingMap->find(symRefNumber) == definingMap->end())
            continue;
        TR_BitVector *definingSymbols = (*definingMap)[symRefNumber];
        if (comp()->getOption(TR_TraceOSR)) {
            traceMsg(comp(), "definingMap for symRef #%d\n", symRefNumber);
            definingSymbols->print(comp());
            traceMsg(comp(), "\n");
        }
        TR_BitVectorIterator it(*definingSymbols);
        while (it.hasMoreElements()) {
            int32_t definingSymRefNumber = it.getNextElement();
            int32_t liveLocalIndex = INVALID_LIVENESS_INDEX;
            TR::Symbol *symbol = comp()->getSymRefTab()->getSymRef(definingSymRefNumber)->getSymbol();
            TR::RegisterMappedSymbol *local = NULL;
            local = symbol->getAutoSymbol();
            if (!local && includeParms())
                local = symbol->getParmSymbol();
            if (local)
                liveLocalIndex = local->getLiveLocalIndex();
            if (local && liveLocalIndex != INVALID_LIVENESS_INDEX) {
                if (comp()->getOption(TR_TraceOSR))
                    traceMsg(comp(), "set liveLocalIndex %d for definingSymbol %p definingSymRefNumber %d\n",
                        local->getLiveLocalIndex(), symbol, definingSymRefNumber);
                liveLocals->set(liveLocalIndex);
            }
        }
    }
}

/*
 * Calculate live symbols at a given bci in the current call chain
 */
TR_BitVector *TR_OSRLiveVariableInformation::getLiveSymbolsInInterpreter(TR_ByteCodeInfo &byteCodeInfo)
{
    int32_t callerIndex = byteCodeInfo.getCallerIndex();
    int32_t byteCodeIndex = byteCodeInfo.getByteCodeIndex();
    TR_BCLiveSymbolsMap *bcLiveSymbolMap = NULL;
    TR_BitVector *liveSymbols = NULL;
    if (bcLiveSymbolMaps[callerIndex + 1] == NULL) {
        bcLiveSymbolMap
            = new TR_BCLiveSymbolsMap(TR_BCLiveSymbolsMapComparator(), TR_BCLiveSymbolsMapAllocator(comp()->region()));
        bcLiveSymbolMaps[callerIndex + 1] = bcLiveSymbolMap;
    } else {
        bcLiveSymbolMap = bcLiveSymbolMaps[callerIndex + 1];
        if (bcLiveSymbolMap->find(byteCodeIndex) != bcLiveSymbolMap->end())
            return (*bcLiveSymbolMap)[byteCodeIndex];
    }

    OMR::ResolvedMethodSymbol *methodSymbol
        = (callerIndex == -1) ? comp()->getMethodSymbol() : comp()->getInlinedResolvedMethodSymbol(callerIndex);
    TR_OSRMethodData *osrMethodData = comp()->getOSRCompilationData()->getOSRMethodDataArray()[callerIndex + 1];
    TR_BitVector *liveLocals = new (comp()->trStackMemory()) TR_BitVector(0, comp()->trMemory(), stackAlloc);
    buildLiveSymbolsBitVector(osrMethodData, byteCodeIndex, liveLocals);
    (*bcLiveSymbolMap)[byteCodeIndex] = liveLocals;

    // recursively traverse the call chain until reaching the top method caller
    if (callerIndex == -1)
        return liveLocals;
    TR_InlinedCallSite &callSite = comp()->getInlinedCallSite(callerIndex);
    *liveLocals |= *getLiveSymbolsInInterpreter(callSite._byteCodeInfo);
    return liveLocals;
}

TR_OSRLiveVariableInformation::TR_OSRLiveVariableInformation(TR::Compilation *c, TR::Optimizer *optimizer,
    TR_Structure *rootStructure, bool splitLongs, bool includeParms, bool ignoreOSRUses)
    : TR_LiveVariableInformation(c, optimizer, rootStructure, splitLongs, includeParms, ignoreOSRUses)
{
    int32_t numOfMethods = comp()->getNumInlinedCallSites() + 1;
    bcLiveSymbolMaps
        = (TR_BCLiveSymbolsMap **)comp()->trMemory()->allocateHeapMemory(numOfMethods * sizeof(TR_BCLiveSymbolsMap *));
    memset(bcLiveSymbolMaps, 0x00, numOfMethods * sizeof(TR_BCLiveSymbolsMap *));
}

