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

#ifndef INDUCTIONVAR_INCL
#define INDUCTIONVAR_INCL

#include <stddef.h>
#include <stdint.h>
#include <deque>
#include <map>
#include <utility>
#include "env/FrontEnd.hpp"
#include "compile/Compilation.hpp"
#include "control/Options.hpp"
#include "control/Options_inlines.hpp"
#include "env/TRMemory.hpp"
#include "env/jittypes.h"
#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 "infra/Assert.hpp"
#include "infra/BitVector.hpp"
#include "infra/List.hpp"
#include "optimizer/Optimization.hpp"
#include "optimizer/OptimizationManager.hpp"
#include "optimizer/LoopCanonicalizer.hpp"

class TR_BlockStructure;
class TR_Dominators;
class TR_RegionStructure;
class TR_Structure;

namespace TR {
class VPConstraint;
class VPIntRange;
class VPLongRange;
class AutomaticSymbol;
class NodeChecklist;
class Optimizer;
class SymbolReferenceTable;
class TreeTop;
} // namespace TR
template<class T> class TR_Array;

struct SymRefPair {
    union {
        TR::SymbolReference *_indexSymRef;
        int32_t _index;
    };

    bool _isConst;
    TR::SymbolReference *_derivedSymRef;
    SymRefPair *_next;
};

// 64-bit
// sign-extension elimination

class TR_NodeIndexPair {
public:
    TR_ALLOC(TR_Memory::InductionVariableAnalysis)

    TR_NodeIndexPair(TR::Node *node, int32_t index, TR_NodeIndexPair *next)
        : _node(node)
        , _index(index)
        , _next(next)
    {}

    TR::Node *_node;
    int32_t _index;
    TR_NodeIndexPair *_next;
};

class TR_StoreTreeInfo {
public:
    TR_ALLOC(TR_Memory::InductionVariableAnalysis)

    TR_StoreTreeInfo(TR::TreeTop *tt, TR::Node *load, TR_NodeIndexPair *loads, TR::TreeTop *insertionTree,
        TR::Node *loadUsedInLoopIncrement, bool b, TR::Node *constNode, bool isAddition)
        : _tt(tt)
        , _load(load)
        , _loads(loads)
        , _insertionTreeTop(insertionTree)
        , _loadUsedInLoopIncrement(loadUsedInLoopIncrement)
        , _incrementInDifferentExtendedBlock(b)
        , _constNode(constNode)
        , _isAddition(isAddition)
    {}

    TR::TreeTop *_tt;
    TR::Node *_load;
    TR_NodeIndexPair *_loads;
    TR::TreeTop *_insertionTreeTop;
    TR::Node *_loadUsedInLoopIncrement;
    bool _incrementInDifferentExtendedBlock;
    TR::Node *_constNode;
    bool _isAddition;
};

/**
 * Class TR_LoopStrider
 * ====================
 *
 * The loop strider optimization creates derived induction variables
 * (e.g. the address calculation for array accesses &a[i]) and
 * increment/decrement the derived induction variables by the appropriate
 * stride through every iteration of the loop. This can replace complex
 * array address calculations inside the loop with a load (from register
 * or memory). Note that we also create derived induction variables for
 * non-internal pointers (like 4*i or 4*i+16) in cases when it is not
 * possible to create internal pointers (e.g. a+4*i+16).
 */

class TR_LoopStrider : public TR_LoopTransformer {
public:
    TR_LoopStrider(TR::OptimizationManager *manager);

    static TR::Optimization *create(TR::OptimizationManager *manager)
    {
        return new (manager->allocator()) TR_LoopStrider(manager);
    }

    virtual int32_t perform();
    virtual const char *optDetailString() const throw();

    virtual int32_t detectCanonicalizedPredictableLoops(TR_Structure *, TR_BitVector **, int32_t);

    // bool replaceAllInductionVariableComputations(TR::Block *loopInvariantBlock, TR_Structure *, TR::SymbolReference
    // **, TR::SymbolReference *);
    virtual bool examineTreeForInductionVariableUse(TR::Block *loopInvariantBlock, TR::Node *, int32_t, TR::Node *,
        vcount_t, TR::SymbolReference **);
    virtual void updateStoreInfo(int32_t i, TR::TreeTop *tree);
    virtual void checkIfIncrementInDifferentExtendedBlock(TR::Block *block, int32_t inductionVariable);
    virtual bool isStoreInRequiredForm(int32_t symRefNum, TR_Structure *loopStructure);
    virtual TR::Node *updateLoadUsedInLoopIncrement(TR::Node *, int32_t);

    bool isStoreInRequiredForm(TR::Node *storeNode, int32_t symRefNum, TR_Structure *loopStructure);
    TR::Node *setUsesLoadUsedInLoopIncrement(TR::Node *node, int32_t k);

    TR::Node *getNewLoopIncrement(TR_StoreTreeInfo *info, int32_t k);
    TR::Node *getNewLoopIncrement(TR::Node *oldLoad, int32_t k, int32_t symRefNum);
    void addLoad(TR_StoreTreeInfo *info, TR::Node *load, int32_t index);
    void findOrCreateStoreInfo(TR::TreeTop *tree, int32_t i);

    int32_t findNewInductionVariable(TR::Node *, TR::SymbolReference **, bool, int32_t);
    TR::Node *isExpressionLinearInInductionVariable(TR::Node *, int32_t);
    bool isExpressionLinearInSomeInductionVariable(TR::Node *);
    bool identifyExpressionLinearInInductionVariable(TR::Node *, vcount_t);
    void identifyExpressionsLinearInInductionVariables(TR_Structure *, vcount_t);
    bool foundLoad(TR::TreeTop *, TR::Node *, int32_t, vcount_t);
    bool foundLoad(TR::TreeTop *, int32_t nextInductionVariableNumber, TR::Compilation *);
    bool foundValue(TR::Node *, int32_t, vcount_t);
    bool unchangedValueNeededIn(TR::Block *, int32_t, bool &seenStore);
    void changeLoopCondition(TR_BlockStructure *loopInvariantBlock, bool usingAladd, int32_t bestCandidate,
        TR::Node *storeOfDerivedInductionVariable);
    void createParmAutoPair(TR::SymbolReference *parmSymRef, TR::SymbolReference *autoSymRef);

    TR::Node *findReplacingNode(TR::Node *node, bool usingAladd, int32_t k);
    TR::DataType findDataType(TR::Node *node, bool usingAladd, bool isInternalPointer);
    void placeStore(TR::Node *newStore, TR::Block *loopInvariantBlock);
    void setInternalPointer(TR::Symbol *symbol, TR::AutomaticSymbol *pinningArrayPointer);
    void populateLinearEquation(TR::Node *node, int32_t loopDrivingInductionVar, int32_t derivedInductionVar,
        int32_t internalPointerSymbol, TR::Node *invariantMultiplicationTerm);

    // (64-bit)
    // sign-extension elimination

    struct SignExtEntry {
        SignExtEntry()
            : extended(NULL)
            , cancelsExt(false)
            , cancelsTrunc(false)
        {}

        TR::Node *extended;
        bool cancelsExt;
        bool cancelsTrunc;
    };

    // Maps are keyed by a node's global index, because a node's address could
    // be reused after its reference count decreases to zero.
    typedef TR::typed_allocator<std::pair<ncount_t const, SignExtEntry>, TR::Allocator> SignExtMemoAllocator;
    typedef std::map<ncount_t, SignExtEntry, std::less<ncount_t>, SignExtMemoAllocator> SignExtMemo;

    void morphExpressionsLinearInInductionVariable(TR_Structure *, vcount_t);
    bool morphExpressionLinearInInductionVariable(TR::Node *, int32_t, TR::Node *, vcount_t);
    TR::Node *getInductionVariableNode(TR::Node *);
    void walkTreesAndFixUseDefs(TR_Structure *, TR::SymbolReference *, TR::NodeChecklist &);
    void replaceLoadsInStructure(TR_Structure *, int32_t, TR::Node *, TR::SymbolReference *, TR::NodeChecklist &,
        TR::NodeChecklist &);
    void replaceLoadsInSubtree(TR::Node *, int32_t, TR::Node *, TR::SymbolReference *, TR::NodeChecklist &,
        TR::NodeChecklist &);
    void widenComparison(TR::Node *, int32_t, TR::Node *, TR::NodeChecklist &);
    void eliminateSignExtensions(TR::NodeChecklist &);
    void eliminateSignExtensionsInSubtree(TR::Node *, TR::NodeChecklist &, TR::NodeChecklist &, SignExtMemo &);
    SignExtEntry signExtend(TR::Node *, TR::NodeChecklist &, SignExtMemo &);
    SignExtEntry signExtendBinOp(TR::ILOpCodes, TR::Node *, TR::NodeChecklist &, SignExtMemo &);
    void transmuteDescendantsIntoTruncations(TR::Node *, TR::Node *);
    void detectLoopsForIndVarConversion(TR_Structure *, TR::NodeChecklist &);
    void extendIVsOnLoopEntry(const TR::list<std::pair<int32_t, int32_t> > &, TR::Block *);
    void truncateIVsOnLoopExit(const TR::list<std::pair<int32_t, int32_t> > &, TR_RegionStructure *);
    void convertIV(TR::Node *, TR::TreeTop *, int32_t, int32_t, TR::ILOpCodes);
    void createConstraintsForNewInductionVariable(TR_Structure *, TR::SymbolReference *, TR::SymbolReference *);
    bool checkExpressionForInductionVariable(TR::Node *);
    bool checkStoreOfIndVar(TR::Node *);
    // end sign-extension

    TR::Node *placeInitializationTreeInLoopInvariantBlock(TR_BlockStructure *, TR::SymbolReference *,
        TR::SymbolReference *, int32_t, TR::SymbolReferenceTable *);
    TR::Node *placeNewInductionVariableIncrementTree(TR_BlockStructure *, TR::SymbolReference *, TR::SymbolReference *,
        int32_t, TR::SymbolReferenceTable *, TR::Node *, int32_t);
    TR::Node *placeNewInductionVariableIncrementTree(TR_BlockStructure *loopInvariantBlock,
        TR::SymbolReference *inductionVarSymRef, TR::SymbolReference *newSymbolReference, int32_t k,
        TR::SymbolReferenceTable *symRefTab, TR::Node *placeHolderNode, TR::Node *newLoad,
        TR::TreeTop *insertionTreeTop, TR::Node *constNode, bool isAddition);

    bool reassociateAndHoistComputations(TR::Block *, TR_Structure *);
    bool reassociateAndHoistComputations(TR::Block *, TR::Node *, int32_t, TR::Node *, vcount_t);

    bool reassociateAndHoistNonPacked();

    bool checkInvariance(TR::Node *, int32_t, TR::Node *, int32_t);

    int32_t maxInternalPointers()
    {
        // was int32_t reservedForLoops=comp()->getOption(TR_ProcessHugeMethods)?6:2;
        // increased to 8 since we did see the limit being reached and believe 2 would
        // be too little as a buffer for the internal pointer spills. 8 is a hypothetical
        // estimate and may be changed later if more observation is found.
        int32_t reservedForLoops = 8;

        int32_t maxNumber = comp()->maxInternalPointers();

        if (maxNumber >= reservedForLoops)
            return maxNumber - reservedForLoops;
        else
            return reservedForLoops;
    }

    int32_t maxInternalPointersAtPointTooLateToBackOff()
    {
        int32_t reservedForLoops = comp()->getOption(TR_ProcessHugeMethods) ? 4 : 0;

        int32_t maxNumber = comp()->maxInternalPointers();

        if (maxNumber >= reservedForLoops)
            return maxNumber - reservedForLoops;
        else
            return reservedForLoops;
    }

    void setAdditiveTermNode(TR::Node *node, int32_t k)
    {
        TR_ASSERT(k < _numberOfLinearExprs, "index k %d exceeds _numberOfLinearExprs %d!\n", k, _numberOfLinearExprs);
        _linearEquations[k][3] = (intptr_t)node;
    }

    TR::Node *getAdditiveTermNode(int32_t k)
    {
        TR_ASSERT(k < _numberOfLinearExprs, "index k %d exceeds _numberOfLinearExprs %d!\n", k, _numberOfLinearExprs);
        return (TR::Node *)(intptr_t)_linearEquations[k][3];
    }

    TR::Node *duplicateAdditiveTermNode(int32_t k, TR::Node *node, TR::DataType type)
    {
        TR_ASSERT(k < _numberOfLinearExprs, "index k %d exceeds _numberOfLinearExprs %d!\n", k, _numberOfLinearExprs);
        TR::Node *new_node = ((TR::Node *)(intptr_t)_linearEquations[k][3])->duplicateTree();
        new_node->setByteCodeIndex(node->getByteCodeIndex());
        new_node->setInlinedSiteIndex(node->getInlinedSiteIndex());

        if (new_node->getDataType() != type)
            new_node = TR::Node::create(
                TR::ILOpCode::getProperConversion(new_node->getDataType(), type, false /* !wantZeroExtension */), 1,
                new_node);
        return new_node;
    }

    bool isAdditiveTermConst(int32_t k)
    {
        TR_ASSERT(k < _numberOfLinearExprs, "index k %d exceeds _numberOfLinearExprs %d!\n", k, _numberOfLinearExprs);
        return (((TR::Node *)(intptr_t)_linearEquations[k][3]) == NULL
            || ((TR::Node *)(intptr_t)_linearEquations[k][3])->getOpCode().isLoadConst());
    }

    int64_t getAdditiveTermConst(int32_t k);
    bool isAdditiveTermEquivalentTo(int32_t k, TR::Node *node);

    void setMulTermNode(TR::Node *node, int32_t k)
    {
        TR_ASSERT(k < _numberOfLinearExprs, "index k %d exceeds _numberOfLinearExprs %d!\n", k, _numberOfLinearExprs);
        _linearEquations[k][2] = (intptr_t)node;
    }

    TR::Node *getMulTermNode(int32_t k)
    {
        TR_ASSERT(k < _numberOfLinearExprs, "index k %d exceeds _numberOfLinearExprs %d!\n", k, _numberOfLinearExprs);
        return (TR::Node *)(intptr_t)_linearEquations[k][2];
    }

    TR::Node *duplicateMulTermNode(int32_t k, TR::Node *node, TR::DataType type);

    bool isMulTermConst(int32_t k)
    {
        TR_ASSERT(k < _numberOfLinearExprs, "index k %d exceeds _numberOfLinearExprs %d!\n", k, _numberOfLinearExprs);
        return ((TR::Node *)(intptr_t)_linearEquations[k][2])->getOpCode().isLoadConst();
    }

    int64_t getMulTermConst(int32_t k);
    bool isMulTermEquivalentTo(int32_t k, TR::Node *node);

    bool isExprLoopInvariant(TR::Node *node)
    {
        if (node->getOpCode().isLoadConst()
            || (node->getOpCode().isLoadVarDirect() && node->getSymbol()->isAutoOrParm()
                && _neverWritten->get(node->getSymbolReference()->getReferenceNumber())))
            return true;

        if (TR::ILOpCode::isOpCodeAnImplicitNoOp(node->getOpCode()) && node->getNumChildren() == 1)
            return isExprLoopInvariant(node->getChild(0));
        return false;
    }

    int64_t **_linearEquations;
    TR::Node **_loadUsedInNewLoopIncrement;

    typedef TR::typed_allocator<std::pair<uint32_t const, TR::SymbolReference *>, TR::Region &> SymRefMapAllocator;
    typedef std::less<uint32_t> SymRefMapComparator;
    typedef std::map<uint32_t, TR::SymbolReference *, SymRefMapComparator, SymRefMapAllocator> SymRefMap;
    SymRefMap *_reassociatedAutos;

    List<TR::Node> _reassociatedNodes;

    typedef TR::typed_allocator<std::pair<uint32_t const, List<TR_StoreTreeInfo> *>, TR::Region &>
        StoreTreeMapAllocator;
    typedef std::less<uint32_t> StoreTreeMapComparator;
    typedef std::map<uint32_t, List<TR_StoreTreeInfo> *, StoreTreeMapComparator, StoreTreeMapAllocator> StoreTreeMap;
    StoreTreeMap _storeTreesSingleton;
    StoreTreeMap *_storeTreesList;
    // List<TR::Node> **_loadUsedInNewLoopIncrementList;

    int32_t _numSymRefs;

    typedef TR::typed_allocator<std::pair<uint32_t const, SymRefPair *>, TR::Region &> SymRefPairMapAllocator;
    typedef std::less<uint32_t> SymRefPairMapComparator;
    typedef std::map<uint32_t, SymRefPair *, SymRefPairMapComparator, SymRefPairMapAllocator> SymRefPairMap;
    SymRefPairMap *_hoistedAutos;

    SymRefPair *_parmAutoPairs;
    int32_t _count;
    int32_t _numberOfLinearExprs, _numInternalPointers;
    int32_t _numInternalPointerOrPinningArrayTempsInitialized;
    bool _usesLoadUsedInLoopIncrement;
    TR_StoreTreeInfo *_storeTreeInfoForLoopIncrement;
    bool _registersScarce;
    bool _newTempsCreated;
    bool _newNonAddressTempsCreated;
    bool _arrayShadowParent;

    // (64-bit)
    // sign-extension elimination data-structures
    bool _isInductionVariableMorphed;
    // end sign-extension

private:
    TR::Node *genLoad(TR::Node *node, TR::SymbolReference *symRef, bool isInternalPointer);
    void examineOpCodesForInductionVariableUse(TR::Node *node, TR::Node *parent, int32_t &childNum, int32_t &index,
        TR::Node *originalNode, TR::Node *replacingNode, TR::Node *linearTerm, TR::Node *mulTerm,
        TR::SymbolReference **newSymbolReference, TR::Block *loopInvariantBlock,
        TR::AutomaticSymbol *pinningArrayPointer, int64_t differenceInAdditiveConstants, bool &isInternalPointer,
        bool &downcastNode, bool &usingAladd);
    void changeBranchFromIntToLong(TR::Node *branch);
    TR::VPLongRange *genVPLongRange(TR::VPConstraint *cons, int64_t coeff, int64_t additive);
    TR::VPIntRange *genVPIntRange(TR::VPConstraint *cons, int64_t coeff, int64_t additive);
};

enum TR_ProgressionKind {
    Identity = 0,
    Arithmetic,
    Geometric
};

class TR_BasicInductionVariable {
public:
    TR_ALLOC(TR_Memory::InductionVariableAnalysis);

    TR_BasicInductionVariable(TR::Compilation *c, TR_RegionStructure *loop, TR::SymbolReference *symRef)
        : _comp(c)
        , _loop(loop)
        , _symRef(symRef)
        , _entryValue(0)
        , _deltaOnBackEdge(0)
        , _deltaOnExitEdge(0)
        , _increment(0)
        , _onlyIncrementValid(false)
    {}

    TR_BasicInductionVariable(TR::Compilation *c, TR_BasicInductionVariable *biv)
        : _comp(c)
        , _loop(biv->_loop)
        , _symRef(biv->_symRef)
        , _entryValue(biv->_entryValue)
        , _deltaOnBackEdge(biv->_deltaOnBackEdge)
        , _deltaOnExitEdge(biv->_deltaOnExitEdge)
        , _increment(biv->_increment)
    {
        _onlyIncrementValid = false;
    }

    TR::Compilation *comp() { return _comp; }

    TR::SymbolReference *getSymRef() { return _symRef; }

    TR::Node *getEntryValue() { return _entryValue; }

    bool isLongInt() { return _symRef->getSymbol()->getDataType() == TR::Int64; }

    void setEntryValue(TR::Node *node) { _entryValue = node->duplicateTree(); }

    int32_t getDeltaOnBackEdge() { return _deltaOnBackEdge; }

    void setDeltaOnBackEdge(int32_t d) { _deltaOnBackEdge = d; }

    int32_t getDeltaOnExitEdge() { return _deltaOnExitEdge; }

    void setDeltaOnExitEdge(int32_t d) { _deltaOnExitEdge = d; }

    int32_t getIncrement() { return _increment; }

    void setIncrement(int32_t incr) { _increment = incr; }

    virtual TR::Node *getExitValue() { return 0; } // FIXME: ask the loop?

    // the following returns the iteration count of the loop,
    // note that this is not necessarily the same as the number of times
    // that this induction variable will be incremented
    //
    // iteration count is defined as the number of times the loop exit test
    // will fail (ie. the number of times the backedge will be taken)
    //
    virtual int32_t getIterationCount() { return -1; } // FIXME: ask the loop?

    bool isOnlyIncrementValid() { return _onlyIncrementValid; }

    void setOnlyIncrementValid(bool v) { _onlyIncrementValid = v; }

private:
    TR::Compilation *_comp;
    TR_RegionStructure *_loop;
    TR::SymbolReference *_symRef;
    TR::Node *_entryValue;
    int32_t _deltaOnBackEdge;
    int32_t _deltaOnExitEdge;
    int32_t _increment;
    bool _onlyIncrementValid;
};

class TR_PrimaryInductionVariable : public TR_BasicInductionVariable {
public:
    TR_ALLOC(TR_Memory::InductionVariableAnalysis);

    TR_PrimaryInductionVariable(TR_BasicInductionVariable *biv, TR::Block *branchBlock, TR::Node *exitBound,
        TR::ILOpCodes exitOp, TR::Compilation *comp, TR::Optimizer *opt, bool usesUnchangedValueInLoopTest, bool trace);

    TR::Block *getBranchBlock() { return _branchBlock; }

    TR::Node *getExitBound() { return _exitBound; }

    bool isUnsigned() { return ((TR::ILOpCode *)&_exitOp)->isUnsignedCompare(); }

    virtual TR::Node *getExitValue();

    virtual int32_t getIterationCount() { return _iterCount; }

    int32_t getNumLoopExits() { return _numLoopExits; }

    void setNumLoopExits(int32_t v) { _numLoopExits = v; }

    bool usesUnchangedValueInLoopTest() { return _usesUnchangedValueInLoopTest; }

    void setUsesUnchangedValueInLoopTest(bool v) { _usesUnchangedValueInLoopTest = v; }

private:
    TR::Node *_exitBound;
    TR::ILOpCodes _exitOp;
    int32_t _iterCount;
    TR::Block *_branchBlock;
    int32_t _numLoopExits;
    bool _usesUnchangedValueInLoopTest;
};

class TR_DerivedInductionVariable : public TR_BasicInductionVariable {
public:
    TR_ALLOC(TR_Memory::InductionVariableAnalysis);

    TR_DerivedInductionVariable(TR::Compilation *c, TR_BasicInductionVariable *biv, TR_PrimaryInductionVariable *piv)
        : TR_BasicInductionVariable(c, biv)
        , _piv(piv)
    {}

    virtual TR::Node *getExitValue();

    virtual int32_t getIterationCount() { return _piv->getIterationCount(); }

private:
    TR_BasicInductionVariable *_piv;
};

class TR_InductionVariableAnalysis : public TR::Optimization {
public:
    TR_InductionVariableAnalysis(TR::OptimizationManager *manager);

    static TR::Optimization *create(TR::OptimizationManager *manager)
    {
        return new (manager->allocator()) TR_InductionVariableAnalysis(manager);
    }

    virtual int32_t perform();
    virtual const char *optDetailString() const throw();

    TR_Array<TR_BasicInductionVariable *> *getInductionVariables() { return _ivs; }

private:
    typedef TR::typed_allocator<TR::CFGEdge *, TR::Allocator> WorkQueueAllocator;
    typedef std::deque<TR::CFGEdge *, WorkQueueAllocator> WorkQueue;

    class DeltaInfo {
    public:
        TR_ALLOC(TR_Memory::InductionVariableAnalysis);

        DeltaInfo(int32_t delta)
            : _delta(delta)
            , _unknown(false)
            , _kind(Identity)
        {}

        DeltaInfo(DeltaInfo *other)
            : _delta(other->_delta)
            , _unknown(other->_unknown)
            , _kind(other->_kind)
        {}

        void setUnknownValue() { _unknown = true; }

        bool isUnknownValue() { return _unknown; }

        TR_ProgressionKind getKind() { return _kind; }

        int32_t getDelta() { return _delta; }

        void arithmeticDelta(int32_t incr);
        void geometricDelta(int32_t incr);
        void merge(DeltaInfo *other);

    private:
        int32_t _delta;
        TR_ProgressionKind _kind;
        bool _unknown;
    };

    struct AnalysisInfo {
    public:
        TR_ALLOC(TR_Memory::InductionVariableAnalysis);

        AnalysisInfo(TR_BitVector *loopLocalDefs, TR_BitVector *allDefs)
            : _loopLocalDefs(loopLocalDefs)
            , _allDefs(allDefs)
        {}

        TR_BitVector *getLoopLocalDefs() { return _loopLocalDefs; }

        TR_BitVector *getAllDefs() { return _allDefs; }

    private:
        TR_BitVector *_loopLocalDefs;
        TR_BitVector *_allDefs;
    };

    static void appendPredecessors(WorkQueue &workList, TR::Block *block);

    void removeStaleIVs(TR_RegionStructure *region);
    void gatherCandidates(TR_Structure *s, TR_BitVector *b, TR_BitVector *);

    void perform(TR_RegionStructure *str);

    void analyzeNaturalLoop(TR_RegionStructure *loop);
    void analyzeAcyclicRegion(TR_RegionStructure *region, TR_RegionStructure *loop);
    void analyzeCyclicRegion(TR_RegionStructure *region, TR_RegionStructure *loop);
    void analyzeBlock(TR_BlockStructure *block, TR_RegionStructure *loop);
    void analyzeLoopExpressions(TR_RegionStructure *loop, DeltaInfo **loopSet);

    bool analyzeExitEdges(TR_RegionStructure *loop, TR_BitVector *candidates,
        TR_Array<TR_BasicInductionVariable *> &basicIVs);

    bool findEntryValues(TR_RegionStructure *loop, TR_Array<TR_BasicInductionVariable *> &basicIVs);
    TR::Node *findEntryValueForSymRef(TR_RegionStructure *loop, TR::SymbolReference *symRef);
    TR::Node *getEntryValue(TR::Block *block, TR::SymbolReference *symRef, TR_BitVector *nodesDone,
        TR_Array<TR::Node *> &cachedVales, int32_t depth = 0);

    bool isProgressionalStore(TR::Node *node, TR_ProgressionKind *kind, int64_t *incr);
    bool getProgression(TR::Node *expr, TR::SymbolReference *storeRef, TR::SymbolReference **ref,
        TR_ProgressionKind *prog, int64_t *incr);
    bool isGotoBlock(TR::Block *block);

    bool branchContainsInductionVariable(TR_RegionStructure *loop, TR::Node *branchNode,
        TR_Array<TR_BasicInductionVariable *> &basicIVs);
    bool branchContainsInductionVariable(TR::Node *branchNode, TR::SymbolReference *ivSymRef, int32_t *nodeBudget);
    bool isIVUnchangedInLoop(TR_RegionStructure *loop, TR::Block *loopTestBlock, TR::Node *ivNode);

    void initializeBlockInfoArray(TR_RegionStructure *region);

    DeltaInfo **setBlockInfo(TR::Block *b, DeltaInfo **info) { return _blockInfo[b->getNumber()] = info; }

    DeltaInfo **newBlockInfo(TR_RegionStructure *loop);

    DeltaInfo **getBlockInfo(TR::Block *block) { return _blockInfo[block->getNumber()]; }

    void mergeWithBlock(TR::Block *block, DeltaInfo **info, TR_RegionStructure *loop);
    void mergeWithSet(DeltaInfo **, DeltaInfo **, TR_RegionStructure *loop);

    void printDeltaInfo(DeltaInfo *info);

    DeltaInfo ***_blockInfo;
    TR_Array<TR_BasicInductionVariable *> *_ivs;
    TR_Dominators *_dominators;

    // BitVectors to memoize a check in analyzeExitEdges
    TR_BitVector _seenInnerRegionExit;
    TR_BitVector _isOSRInduceBlock;
};

/*
 * This pass attempts to transforms loops with single back-edge testing address nodes into
 * ones with integer node tests. The main motivation is that IVA does not recognize address type node.
 * Since a lot of loop-based optimizations and analysis are written for loops with integral IV,
 * this is a simple solution to catch many address incrementing loops. The other, full-fledged solution is
 * to recognize address IV in IVA and everywhere else, but that may entail much more work.
 *
 * Address IV is also a fairly common coding pattern in C (pointer manip) and C++ with iterators
 * of contiguous memory.
 * This pass is analogous to loop strider in that it undo's the pointer incr which strides by size of underlying
 * type.
 */
class TR_IVTypeTransformer : public TR_LoopTransformer {
public:
    TR_IVTypeTransformer(TR::OptimizationManager *manager)
        : TR_LoopTransformer(manager)
        , _addrSymRef(NULL)
        , _baseSymRef(NULL)
        , _intIdxSymRef(NULL)
    {}

    static TR::Optimization *create(TR::OptimizationManager *manager)
    {
        return new (manager->allocator()) TR_IVTypeTransformer(manager);
    }

    virtual int32_t perform();
    virtual const char *optDetailString() const throw();

private:
    void changeIVTypeFromAddrToInt(TR_RegionStructure *natLoop);
    bool isInAddrIncrementForm(TR::Node *node, int32_t &increment);
    void replaceAloadWithBaseIndexInSubtree(TR::Node *node);
    TR::ILOpCodes getIntegralIfOpCode(TR::ILOpCodes ifacmp, bool is64bit);
    TR::SymbolReference *findComparandSymRef(TR::Node *node);
    TR::SymbolReference *_addrSymRef;
    TR::SymbolReference *_baseSymRef;
    TR::SymbolReference *_intIdxSymRef;
};

#endif
