/*******************************************************************************
 * 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 COPYPROP_INCL
#define COPYPROP_INCL

#include <stddef.h>
#include <stdint.h>
#include "env/TRMemory.hpp"
#include "optimizer/Optimization.hpp"
#include "optimizer/OptimizationManager.hpp"
#include "optimizer/UseDefInfo.hpp"
#include "infra/Checklist.hpp"

class TR_BitVector;

namespace TR {
class SymbolReference;
class Block;
class Node;
class TreeTop;
} // namespace TR

// Copy Propagation
//
// Uses the information computed by ReachingDefinitions (stored in
// UseDefInfo) to perform the transformation. If a use node has a
// unique corresponding definition node (that is equivalent to a
// copy statement), then all occurrences of the copy in the use
// node can be replaced by the original value (the one that was copied).
// Note that after copy propagation is done, UseDefInfo might change
// because the program has been altered as a result of copy propagation.
//
// Dead Store Elimination might be a good optimization to perform
// after copy propagation is done; this could possibly eliminate
// the copy (definition) statement altogether in some cases.
//

class TR_CopyPropagation : public TR::Optimization {
public:
    // Performs copy propagation using the
    // use/def values of relevant nodes.
    //
    TR_CopyPropagation(TR::OptimizationManager *manager);

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

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

private:
    void replaceCopySymbolReferenceByOriginalIn(TR::SymbolReference *copySymRef, TR::Node *rhsOfStoreDefNode,
        TR::Node *useNode, TR::Node *defNode, TR::Node *baseAddrNode = NULL, bool baseAddrAvail = false);
    void replaceCopySymbolReferenceByOriginalRegLoadIn(TR::Node *regLoadNode, TR::Node *useNode,
        TR::SymbolReference *copySymbolReference, TR::Node *node, TR::Node *parent, int32_t childNum);
    void adjustUseDefInfo(TR::Node *, TR::Node *, TR_UseDefInfo *);
    bool isUniqueDefinitionOfUse(TR_BitVector *, TR_UseDefInfo *, int32_t);
    bool isLoadNodeSuitableForPropagation(TR::Node *useNode, TR::Node *storeNode, TR::Node *loadNode);
    TR::Node *areAllDefsInCorrectForm(TR::Node *, const TR_UseDefInfo::BitVector &, TR_UseDefInfo *, int32_t,
        TR::Node *&, int32_t &, TR::Node *&);
    bool isSafeToPropagate(TR::Node *, TR::Node *);
    TR::Node *skipTreeTopAndGetNode(TR::TreeTop *tt);
    bool isCorrectToPropagate(TR::Node *, TR::Node *, TR::list<TR::Node *> &, TR::SparseBitVector &, int32_t,
        const TR_UseDefInfo::BitVector &, TR_UseDefInfo *);
    bool isCorrectToReplace(TR::Node *, TR::Node *, const TR_UseDefInfo::BitVector &, TR_UseDefInfo *);
    bool isRedefinedBetweenStoreTreeAnd(TR::list<TR::Node *> &checkNodes, TR::SparseBitVector &, TR::Node *storeNode,
        TR::TreeTop *exitTree, int32_t regNumber, const TR_UseDefInfo::BitVector &, TR_UseDefInfo *);
    bool recursive_isRedefinedBetweenStoreTreeAnd(TR::list<TR::Node *> &checkNodes, TR::SparseBitVector &,
        TR::Node *storeNode, TR::TreeTop *exitTree, int32_t regNumber, const TR_UseDefInfo::BitVector &,
        TR_UseDefInfo *);
    bool containsNode(TR::Node *node1, TR::Node *node2, bool searchClones = true);
    TR::Node *isLoadVarWithConst(TR::Node *);
    TR::Node *isIndirectLoadFromAuto(TR::Node *);
    TR::Node *isIndirectLoadFromRegister(TR::Node *, TR::Node *&);
    TR::Node *isValidRegLoad(TR::Node *, TR::TreeTop *, int32_t &);
    TR::Node *isCheapRematerializationCandidate(TR::Node *, TR::Node *);
    bool containsLoadOfSymbol(TR::Node *node, TR::SymbolReference *symRef, TR::Node **loadNode);
    TR::Node *isBaseAddrAvailable(TR::Node *, TR::Node *, bool &);
    bool isNodeAvailableInBlock(TR::TreeTop *, TR::Node *);

    // The treetop for a use node is often required during
    // this optimization. To reduce compile time overhead, they
    // are stashed into the _useTreeTops map. This should be respected
    // by updating this map if existing uses are moved to new treetops
    //
    void collectUseTrees(TR::TreeTop *tree, TR::Node *node, TR::NodeChecklist &checklist);
    void findUseTree(TR::Node *);

    TR::TreeTop *findAnchorTree(TR::Node *, TR::Node *);
    void rematerializeIndirectLoadsFromAutos();
    void commonIndirectLoadsFromAutos();

    bool _canMaintainUseDefs;
    bool _cleanupTemps;
    TR::TreeTop *_storeTree;
    TR::TreeTop *_useTree;

    typedef TR::typed_allocator<std::pair<TR::Node * const, TR::TreeTop *>, TR::Region &> StoreTreeMapAllocator;
    typedef std::less<TR::Node *> StoreTreeMapComparator;
    typedef std::map<TR::Node *, TR::TreeTop *, StoreTreeMapComparator, StoreTreeMapAllocator> StoreTreeMap;
    StoreTreeMap _storeTreeTops;

    typedef TR::typed_allocator<std::pair<TR::Node * const, TR::TreeTop *>, TR::Region &> UseTreeMapAllocator;
    typedef std::less<TR::Node *> UseTreeMapComparator;
    typedef std::map<TR::Node *, TR::TreeTop *, UseTreeMapComparator, UseTreeMapAllocator> UseTreeMap;
    UseTreeMap _useTreeTops;

    TR::Block *_storeBlock;
    bool _lookForOriginalDefs;
    bool _propagatingWholeExpression;
};

#endif
