/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You under the Apache License, Version 2.0
 *  (the "License"); you may not use this file except in compliance with
 *  the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */

#include "irmanager.h"
#include "Dominator.h"
#include "classic_abcd.h"
#include "classic_abcd_solver.h"
#include "opndmap.h"

#include "Stl.h"
#include "Log.h"
#include "open/types.h"
#include "Inst.h"
#include "walkers.h"
#include "PMFAction.h"
#include "constantfolder.h"

#include <assert.h>
#include <iostream>
#include <algorithm>

namespace Jitrino {

// eliminating Array Bounds Check on Demand
DEFINE_SESSION_ACTION(CLASSIC_ABCDPass, classic_abcd, "Classic ABCD: eliminating Array Bounds Check on Demand");

void
CLASSIC_ABCDPass::_run(IRManager &irm) {
    OptPass::splitCriticalEdges(irm);
    OptPass::computeDominators(irm);
    ClassicAbcd classic_abcd(this, irm, irm.getNestedMemoryManager(), 
                             *irm.getDominatorTree());
    classic_abcd.runPass();
}
//------------------------------------------------------------------------------

class IOpndProxy : public IOpnd
{
public:
    IOpndProxy(Opnd* opnd);

    IOpndProxy(I_32 c, U_32 id);

    virtual void printName(std::ostream& os) const
    {
        if ( _opnd ) {
            _opnd->print(os);
        }else{
            os << "_c" << getID() << "(const=" << getConstant() << ")";
        }
    }

    Opnd* getOrg() const { return _opnd; }

    static U_32 getProxyIdByOpnd(Opnd* opnd);
private:
    Opnd* _opnd;

    /* ids of PiOpnd, SsaOpnd, VarOpnd may alias their IDs,
     * encoding all in one ID with unaliasing
     */
    static const U_32 min_var_opnd = 0;
    static const U_32 min_ssa_opnd = MAX_UINT32 / 4;
    static const U_32 min_pi_opnd = (min_ssa_opnd) * 2;
    static const U_32 min_const_opnd = (min_ssa_opnd) * 3;
};
//------------------------------------------------------------------------------

// for debugging purposes
void printIOpnd(IOpnd* opnd)
{
    opnd->printName(std::cout);
    std::cout << std::endl;
}

bool inInt32(int64 c) {
    return (int64)(I_32)c == c;
}

bool inInt32Type(Type t) {
    return (t.tag == Type::Int8) || 
         (t.tag == Type::Int16) || 
         (t.tag == Type::Int32);
}

IOpndProxy::IOpndProxy(Opnd* opnd) : 
    IOpnd(0/* id */, 
          opnd->getInst()->isPhi() /* is_phi */, 
          ConstantFolder::isConstant(opnd) /* is_constant */),
    _opnd(opnd)
{
    setID(getProxyIdByOpnd(_opnd));
    if ( isConstant() ) {
        ConstInst* c_inst = _opnd->getInst()->asConstInst();
        assert(c_inst);
        int64 value = c_inst->getValue().i8;
        if ( inInt32Type(c_inst->getType()) ) {
            value = c_inst->getValue().i4;
        }else if ( c_inst->getType() != Type::Int64 ) {
            setUnconstrained(true);
            return;
        }
        if ( inInt32(value) ) {
            setConstant((I_32)value);
        }else{
            setUnconstrained(true);
        }
    }
}
//------------------------------------------------------------------------------

IOpndProxy::IOpndProxy(I_32 c, U_32 id) : 
    IOpnd(0, false /* is_phi */, true /* is_constant */),
    _opnd(NULL)
{
    setID(min_const_opnd + id);
    setConstant(c);
}

U_32 IOpndProxy::getProxyIdByOpnd(Opnd* opnd)
{
    U_32 id = opnd->getId();
    if ( opnd->isVarOpnd() ) {
        id += min_var_opnd;
    }else if ( opnd->isPiOpnd() ) { 
        // note: PiOpnd inherits from SsaOpnd, check PiOpnd first
        id += min_pi_opnd;
    }else if ( opnd->isSsaOpnd() ) {
        id += min_ssa_opnd;
    }else {
        assert(0);
    }
    return id;
}
//------------------------------------------------------------------------------

class BuildInequalityGraphWalker {
public:
    BuildInequalityGraphWalker(InequalityGraph* igraph) :
        _igraph(igraph), _const_id_counter(1 /*reserve 0 for solver*/),
        _map_opnd_to_pi_inst(igraph->getMemoryManager())
    {}

    void startNode(DominatorNode *domNode);
    void applyToInst(Inst* i);
    void finishNode(DominatorNode *domNode);

    void enterScope() {}
    void exitScope() {}
private:
    // returns true if an edge to const opnd is actually added
    bool addEdgeIfConstOpnd(IOpndProxy* dst, Opnd* const_src, Opnd* src, 
                            bool negate_src);

    void addAllSrcOpndsForPhi(Inst* inst);

    // returns true if the edge is actually added
    bool addDistance(IOpndProxy* dst, IOpndProxy* src, int64 constant, 
                     bool negate);

    void addDistanceSingleProblem(IOpndProxy* to, IOpndProxy* from, int64 c, 
                                  bool lower_problem);

    void addPiEdgesSingleProblem
         (IOpndProxy* dst, bool lower_problem, const PiBound& non_inf_bound);

    IOpndProxy* findProxy(Opnd* opnd);

    IOpndProxy* addOldOrCreateOpnd(Opnd* opnd);

    InequalityGraph* _igraph;
    U_32 _const_id_counter;

    // operands are mapped to their renaming Pi instructions during the walk
    // (applyToInst), and then this mapping is used to create edges between
    // operands in InequalityGraph. This allows to link newer operands with
    // constraints (edges) rather than old ones;
    //
    // Example:
    //   if ( x.1 < y.1 ) {
    //     pi( x.1 : [undef, y.1 - 1] ) -> x.2 // inst.X
    //     pi( y.1 : [x.1 + 1, undef] ) -> y.2 // inst.Y
    //   }
    //
    // we collect the mapping:
    //     x.1 -> inst.X
    //     y.1 -> inst.Y
    // to deduce edges:
    //     upper-only edge: x.2 - y.2 <= -1 // hint: 'to' - 'from'
    //     lower-only edge: 1 <= y.2 - x.2
    // instead of the straightforward:
    //     upper-only edge: x.2 - y.1 <= -1 // hint: 'to' - 'from'
    //     lower-only edge: 1 <= y.2 - x.1
    //
    // (ideally there should only be 2 elements in the map for each basic block
    //  at most (taken from "if a < b" or such), but our InsertPi sometimes adds
    //  more)
    typedef StlMap<IOpndProxy*, TauPiInst*> OpndToPiInst2ElemMap;
    OpndToPiInst2ElemMap _map_opnd_to_pi_inst;
};
//------------------------------------------------------------------------------

IOpndProxy* BuildInequalityGraphWalker::findProxy(Opnd* opnd)
{
    assert(_igraph);
    return (IOpndProxy*) _igraph->findOpnd(IOpndProxy::getProxyIdByOpnd(opnd));
}
//------------------------------------------------------------------------------

void BuildInequalityGraphWalker::addAllSrcOpndsForPhi(Inst* inst)
{
    assert(inst->getOpcode() == Op_Phi);
    for (U_32 j = 0; j < inst->getNumSrcOperands(); j++) {
        IOpndProxy* proxy_src = addOldOrCreateOpnd(inst->getSrc(j));
        addDistance(findProxy(inst->getDst()), proxy_src, 0, false /*negate*/);
    }
}
//------------------------------------------------------------------------------

void BuildInequalityGraphWalker::startNode(DominatorNode *domNode)
{
    if ( Log::isEnabled() &&
         !_map_opnd_to_pi_inst.empty() ) {
        Log::out() << "_map_opnd_to_pi_inst before clear:" << std::endl;
        OpndToPiInst2ElemMap::const_iterator 
            it = _map_opnd_to_pi_inst.begin(),
            end = _map_opnd_to_pi_inst.end();
        for (; it != end; it++ ) {
            IOpndProxy* opnd = it->first;
            TauPiInst* inst = it->second;
            Log::out() << " opnd: ";
            opnd->printName(Log::out());
            Log::out() << " -> inst: ";
            inst->print(Log::out());
            Log::out() << std::endl;
        }
    }
    _map_opnd_to_pi_inst.clear();
}
//------------------------------------------------------------------------------

bool isIntOrLong(Type* t) {
    return t->isInt4() || t->isInt8();
}
//------------------------------------------------------------------------------

void BuildInequalityGraphWalker::applyToInst(Inst* inst)
{
    assert(inst);

    Type::Tag inst_type = inst->getType();
    if ( !Type::isInteger(inst_type) && inst_type != Type::Boolean &&
         inst_type != Type::Char ) {
        // note: some operations of unsupported type can produce operands of
        // supported (int) types, for example,
        // inst-compare-two-unmanaged-pointers, we need these operands as
        // unconstrained in the graph
        Opnd* dst = inst->getDst();
        if ( dst && !dst->isNull() &&
                (dst->getType()->isInteger() ||
                 dst->getType()->isBoolean() ) ) {
            addOldOrCreateOpnd(dst)->setUnconstrained(true);
        }
        return;
    }
    if ( inst->isUnconditionalBranch() || inst->isConditionalBranch() || 
         inst->isReturn() ) {
        return;
    }
    IOpndProxy* proxy_dst;
    Opcode opc = inst->getOpcode();
    switch ( opc ) {
        case Op_Phi:
        {
            proxy_dst = addOldOrCreateOpnd(inst->getDst());
            addAllSrcOpndsForPhi(inst);
        }
            break;
        case Op_Copy:
        case Op_LdVar:
        case Op_StVar:
        {
            proxy_dst = addOldOrCreateOpnd(inst->getDst());
            addDistance(proxy_dst, findProxy(inst->getSrc(0)), 0, 
                        false /* negate */);
        }
            break;
        case Op_Conv:
        {
            // adding conversions int<->long as zero-length edges to the
            // inequality graph. This is a small enhancement to the paper's
            // algorithm, but it is safe. The proof is as follows: if we ensure
            // that a value of type 'long' is in good bounds for array access,
            // then is is proven to be not outside bounds for type 'int'
            Opnd* src = inst->getSrc(0);
            Opnd* dst = inst->getDst();
            if ( isIntOrLong(src->getType()) &&
                 isIntOrLong(dst->getType()) ) {
                proxy_dst = addOldOrCreateOpnd(inst->getDst());
                addDistance(proxy_dst, findProxy(inst->getSrc(0)), 0, 
                            false /* negate */);
            }else{
                addOldOrCreateOpnd(inst->getDst())->setUnconstrained(true);
            }
        }
            break;
        case Op_Add:
        {
            proxy_dst = addOldOrCreateOpnd(inst->getDst());
            Opnd* src0 = inst->getSrc(0);
            Opnd* src1 = inst->getSrc(1);
            addEdgeIfConstOpnd(proxy_dst, src0, src1, false /* negate */) 
            || addEdgeIfConstOpnd(proxy_dst, src1, src0, false /* negate */);
        }
            break;
        case Op_Sub:
        {
            proxy_dst = addOldOrCreateOpnd(inst->getDst());
            addEdgeIfConstOpnd(proxy_dst, inst->getSrc(1), inst->getSrc(0),
                               true /* negate */ );
        }
            break;
        case Op_TauPi:
        {
            proxy_dst = addOldOrCreateOpnd(inst->getDst());
            IOpndProxy* src0 = findProxy(inst->getSrc(0));
            addDistance(proxy_dst, src0, 0, false /* negate */);
            _map_opnd_to_pi_inst[src0] = inst->asTauPiInst();
            if ( Log::isEnabled() ) {
                Log::out() << "mapping (src->pi inst): src: ";
                src0->printName(Log::out());
                Log::out() << " inst: ";
                inst->print(Log::out());
                Log::out() << std::endl;
            }
        }
            break;
        case Op_TauArrayLen:
        case Op_LdConstant: case Op_LdStatic: case Op_TauLdInd:
        case Op_TauLdField: case Op_TauLdElem:
        case Op_DirectCall: case Op_TauVirtualCall: case Op_IndirectCall:
        case Op_IndirectMemoryCall: case Op_JitHelperCall: case Op_VMHelperCall:
        case Op_DefArg:
            // All these load instructions may potentially produce an operand
            // that would be a parameter to a newarray, hence we need it to be
            // reachable with inequality edges. Need to keep it constrained.
            addOldOrCreateOpnd(inst->getDst());
            break;
        case Op_TauStInd: case Op_TauStElem: case Op_TauStField:
        case Op_TauStRef: case Op_TauStStatic:
            break;
        default:
            addOldOrCreateOpnd(inst->getDst())->setUnconstrained(true);
            break;
    }
}
//------------------------------------------------------------------------------

void BuildInequalityGraphWalker::finishNode(DominatorNode *domNode)
{
    OpndToPiInst2ElemMap::const_iterator it = _map_opnd_to_pi_inst.begin(),
        end = _map_opnd_to_pi_inst.end();
    for (; it != end; it++ ) {
        TauPiInst* pi_inst = it->second;
        const PiCondition* condition = pi_inst->getCond();
        const PiBound& lb = condition->getLb();
        const PiBound& ub = condition->getUb();
        IOpndProxy* dst = findProxy(pi_inst->getDst());
        assert(dst);
        /*
         * pi (src0 \in [undef,A + c] -) dst
         *      dst <= A + c <-> (dst - A) <= c
         *      edge(from:A, to:dst, c)
         *
         * pi (src0 \in [A + c,undef] -) dst
         *      (A + c) <= dst <-> (A - dst) <= -c
         *      edge(from:dst, to:A, -c)
         */
        bool lb_defined = !lb.isUndefined();
        bool ub_defined = !ub.isUndefined();
        if ( lb_defined ) {
            addPiEdgesSingleProblem(dst, true /* lower_problem */, lb);
        }
        if ( ub_defined ) {
            addPiEdgesSingleProblem(dst, false /* lower_problem */, ub);
        }
    }
}

// returns true if the edge is actually added
bool BuildInequalityGraphWalker::addDistance
     (IOpndProxy* dst, IOpndProxy* src, int64 constant, bool negate)
{
    assert(dst && src);
    // This prevention to put some edges is *not* an optimization of any kind.
    // Operands can be marked unconstrained by various reasons, for example:
    // because the constant value does not fit into I_32 (which is critical for
    // array access)
    if ( !src->isUnconstrained() ) {
        if ( !inInt32(constant) ) {
            return false;
        }
        if ( negate ) {
            constant = (-1) * constant;
        }
        _igraph->addEdge(src->getID(), dst->getID(), (I_32)constant);
        return true;
    } else {
        if ( Log::isEnabled() ) {
            Log::out() << "addDistance(): skipping edge, operand is unconstrained: ";
            src->printName(Log::out());
            Log::out() << std::endl;
        }
    }
    return false;
}
//------------------------------------------------------------------------------

void BuildInequalityGraphWalker::addDistanceSingleProblem
     (IOpndProxy* to, IOpndProxy* from, int64 c, bool lower_problem)
{
    assert(to && from);
    if ( from->isUnconstrained() || !inInt32(c) ) {
        return;
    }
    _igraph->addEdgeSingleState(from->getID(), to->getID(), (I_32)c, lower_problem);
}
//------------------------------------------------------------------------------

// returns true if an edge to const opnd is actually added
bool BuildInequalityGraphWalker::addEdgeIfConstOpnd
    (IOpndProxy* dst, Opnd* const_src, Opnd* src, bool negate_src)
{
    if ( ConstantFolder::isConstant(const_src) ) {
        IOpnd* from = findProxy(const_src);
        assert(from);
        if ( !from->isUnconstrained() ) {
            return addDistance(dst, findProxy(src), from->getConstant(), 
                               negate_src);
        }
    }
    return false;
}
//------------------------------------------------------------------------------

void BuildInequalityGraphWalker::addPiEdgesSingleProblem
     (IOpndProxy* dst, bool lower_problem, const PiBound& non_inf_bound)
{
    if ( non_inf_bound.isVarPlusConst()  ) {
        Opnd* var = non_inf_bound.getVar().the_var;
        IOpndProxy* var_proxy = findProxy(var);
        assert(var_proxy);
        if ( _map_opnd_to_pi_inst.count(var_proxy) == 0 ) {
            addDistanceSingleProblem(dst /* to */,
                                  var_proxy /* from */,
                                  non_inf_bound.getConst(),
                                  lower_problem);
        }else{
            TauPiInst* pi_inst = _map_opnd_to_pi_inst[var_proxy];
            IOpndProxy* newer_var_proxy = findProxy(pi_inst->getDst());
            assert(newer_var_proxy);
            addDistanceSingleProblem(dst /* to */,
                                  newer_var_proxy /* from */,
                                  non_inf_bound.getConst(),
                                  lower_problem);
        }
    } else if ( non_inf_bound.isConst() ) {
        MemoryManager& mm = _igraph->getMemoryManager();
        IOpndProxy* c_opnd = new (mm) 
            IOpndProxy((I_32)non_inf_bound.getConst(), _const_id_counter++);
        _igraph->addOpnd(c_opnd);
        addDistanceSingleProblem(dst /* to */, c_opnd, 0, lower_problem);
    }
}
//------------------------------------------------------------------------------

IOpndProxy* BuildInequalityGraphWalker::addOldOrCreateOpnd(Opnd* opnd)
{
    IOpndProxy* proxy = findProxy(opnd);
    if ( !proxy ) {
        MemoryManager& mm = _igraph->getMemoryManager();
        proxy = new (mm) IOpndProxy(opnd);
        _igraph->addOpnd(proxy);
        if ( Log::isEnabled() ) {
            Log::out() << "added opnd: ";
            proxy->printFullName(Log::out());
            Log::out() << std::endl;
        }
    }
    return proxy;
}

class InequalityGraphPrinter : public PrintDotFile {
public:
    InequalityGraphPrinter(InequalityGraph& graph) : _graph(graph) {}
    void printDotBody()
    {
        _graph.printDotBody(*os);
    }
private:
    InequalityGraph& _graph;
};
//------------------------------------------------------------------------------

ClassicAbcd::ClassicAbcd(SessionAction* arg_source, IRManager &ir_manager,
        MemoryManager& mem_manager, DominatorTree& dom0) :
    _irManager(ir_manager), 
    _mm(mem_manager),
    _domTree(dom0),
    _redundantChecks(mem_manager),
    _zeroIOp(NULL),
    _dump_abcd_stats(ir_manager.getOptimizerFlags().dump_abcd_stats)
{
    _runTests = arg_source->getBoolArg("run_tests", false);
    _useAliases = arg_source->getBoolArg("use_aliases", true);
    _zeroIOp = new (mem_manager) IOpndProxy(0, 0 /*using reserved ID*/);
}
//------------------------------------------------------------------------------

void ClassicAbcd::updateOrInitValue
     (InstRedundancyMap& map, Inst* inst, RedundancyType type)
{
    if ( map.count(inst) == 0 ) {
        map[inst] = type;
    }else{
        I_32 new_rtype = (I_32)map[inst];
        new_rtype |= (I_32)type;
        map[inst] = (RedundancyType)new_rtype;
    }
}
//------------------------------------------------------------------------------

void ClassicAbcd::markRedundantInstructions
     (bool upper_problem, InequalityGraph& igraph, ControlFlowGraph& cfg)
{
    ClassicAbcdSolver solver(igraph, igraph.getMemoryManager());
    igraph.setState(!upper_problem /* is_lower */);

    for (Nodes::const_iterator i = cfg.getNodes().begin(); 
            i != cfg.getNodes().end(); 
            ++i) {
        Node *curr_node = *i;

        for (Inst *curr_inst = (Inst*)curr_node->getFirstInst();
             curr_inst != NULL; curr_inst = curr_inst->getNextInst()) {

            if (curr_inst->getOpcode() == Op_TauCheckBounds) {
                assert(curr_inst->getNumSrcOperands() == 2);
                if (Log::isEnabled()) {
                    Log::out() << "Trying to eliminate CheckBounds instruction ";
                    curr_inst->print(Log::out());
                    Log::out() << std::endl;
                }

                Opnd *idxOp = curr_inst->getSrc(1);
                IOpnd *idxIOp = igraph.findOpnd(IOpndProxy::getProxyIdByOpnd(idxOp));

                IOpnd *boundsIOp = _zeroIOp;
                if ( upper_problem ) {
                    Opnd *boundsOp = curr_inst->getSrc(0);
                    boundsIOp = igraph.findOpnd(IOpndProxy::getProxyIdByOpnd(boundsOp));
                }
                bool res = solver.demandProve
                           (boundsIOp, idxIOp, upper_problem ? -1 : 0, upper_problem);
                if (res) {
                    RedundancyType rt = upper_problem ? rtUPPER_MASK : rtLOWER_MASK;
                    updateOrInitValue(_redundantChecks, curr_inst, rt);
                    if (Log::isEnabled()) {
                        Log::out() << "can eliminate";
                        if ( upper_problem ) {
                            Log::out() << " upper ";
                        }else{
                            Log::out() << " lower ";
                        }
                        Log::out() << "bound check!\n";
                    }
                }else{
                    updateOrInitValue(_redundantChecks, curr_inst, rtNONE_MASK);
                }
            }
        }
    }
}
//------------------------------------------------------------------------------

void ClassicAbcd::runPass()
{
    static bool run_once = true;
    if ( run_once && _runTests ) {
        classic_abcd_test_main();
        _runTests = false;
        run_once = false;
    }

    MethodDesc& method_desc  = _irManager.getMethodDesc();
    ControlFlowGraph& cfg    = _irManager.getFlowGraph();
    TypeManager& typeManager = _irManager.getTypeManager();
    OpndManager& opndManager = _irManager.getOpndManager();
    InstFactory& instFactory = _irManager.getInstFactory();

    if ( Log::isEnabled() ) {
        FlowGraph::printDotFile(cfg, method_desc, "before_classic_abcd");
        _domTree.printDotFile(method_desc, "before_classic_abcd.dom");
        Log::out() << "ClassicAbcd pass started" << std::endl;
    }

    MemoryManager ineq_mm("ClassicAbcd::InequalityGraph");
    InsertPi insertPi(ineq_mm, _domTree, _irManager, _useAliases);
    insertPi.insertPi();
    InequalityGraph igraph(ineq_mm);
    igraph.addOpnd(_zeroIOp);
    BuildInequalityGraphWalker igraph_walker(&igraph);
    typedef ScopedDomNodeInst2DomWalker<true, BuildInequalityGraphWalker>
        IneqBuildDomWalker;
    IneqBuildDomWalker dom_walker(igraph_walker);
    DomTreeWalk<true, IneqBuildDomWalker>(_domTree, dom_walker, ineq_mm);

    if ( Log::isEnabled() ) {
        Log::out() << "added zero opnd for solving lower bound problem: ";
        _zeroIOp->printFullName(Log::out());
        Log::out() << std::endl;
        InequalityGraphPrinter printer(igraph);
        printer.printDotFile(method_desc, "inequality.graph");
    }

    _redundantChecks.clear();
    markRedundantInstructions(true /* upper_problem */, igraph, cfg);
    markRedundantInstructions(false /* upper_problem */, igraph, cfg);

    insertPi.removePi();

    U_32 checks_eliminated = 0;

    for(InstRedundancyMap::const_iterator i = _redundantChecks.begin();
        i != _redundantChecks.end(); ++i) {
        Inst *redundant_inst = i->first;
        bool fully_redundant = (i->second == rtFULL_MASK);

        if (fully_redundant) {
            // should we check if another tau has already been placed in
            // this block, and if so reuse it?  Also, should we be using
            // taupoint or tauedge?
            Opnd *tauOp = opndManager.createSsaTmpOpnd(typeManager.getTauType());
            Inst* tau_point = instFactory.makeTauPoint(tauOp);
            tau_point->insertBefore(redundant_inst);

            if (Log::isEnabled()) {
                Log::out() << "Inserted taupoint inst ";
                tau_point->print(Log::out());
                Log::out() << " before inst ";
                redundant_inst->print(Log::out());
                Log::out() << std::endl;
            }

            Opnd* dstOp = redundant_inst->getDst();
            redundant_inst->setDst(OpndManager::getNullOpnd());
            Inst* copy = instFactory.makeCopy(dstOp, tauOp);
            copy->insertBefore(redundant_inst);
            FlowGraph::eliminateCheck(cfg, redundant_inst->getNode(), redundant_inst, false);
            checks_eliminated++;

            if (Log::isEnabled()) {
                Log::out() << "Replaced bound check with inst ";
                copy->print(Log::out());
                Log::out() << std::endl;
            }
        }
    }

    size_t checks_total = _redundantChecks.size();
    if ( _dump_abcd_stats && checks_total > 0 ) {
        std::ofstream checks_log;
        checks_log.open("bounds_checks.log", std::fstream::out | std::fstream::app);
        checks_log << "removed bounds checks of: "
            << method_desc.getParentType()->getName()
            << "." << method_desc.getName()
            << method_desc.getSignatureString()
            << " total checks: " << checks_total
            << "; eliminated: " << checks_eliminated
            << "; fraction: "
            << (double) checks_eliminated / (double) checks_total
            << std::endl;
        checks_log.close();
    }

    Log::out() << "ClassicAbcd pass finished" << std::endl;
}
//------------------------------------------------------------------------------

} //namespace Jitrino