/*
 *  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 "insertpi.h"
#include "walkers.h"
#include "abcdbounds.h"
#include "constantfolder.h"

namespace Jitrino {

static ComparisonModifier
negateComparison(ComparisonModifier mod)
{
    switch (mod) {
    case Cmp_GT: return Cmp_GTE;
    case Cmp_GT_Un: return Cmp_GTE_Un;
    case Cmp_GTE: return Cmp_GT;
    case Cmp_GTE_Un: return Cmp_GT_Un;
    case Cmp_EQ: return Cmp_EQ;
    case Cmp_NE_Un: return Cmp_NE_Un;
    default:
        assert(0); return mod;
    }
}

static const char *
printableComparison(ComparisonModifier mod)
{
    switch (mod) {
    case Cmp_GT: return "Cmp_GT";
    case Cmp_GT_Un: return "Cmp_GT_Un";
    case Cmp_GTE: return "Cmp_GTE";
    case Cmp_GTE_Un: return "Cmp_GTE_Un";
    case Cmp_EQ: return "Cmp_EQ";
    case Cmp_NE_Un: return "Cmp_NE_Un";
    default:
        assert(0); return "";
    }
}

static Type::Tag
unsignType(Type::Tag typetag)
{
    switch (typetag) {
    case Type::IntPtr: return Type::UIntPtr;
    case Type::Int8: return Type::UInt8;
    case Type::Int16: return Type::UInt16;
    case Type::Int32: return Type::UInt32;
    case Type::Int64: return Type::UInt64;
    default:
        assert(0); return typetag;
    }
}

// a DomWalker, to be applied in pre-order
class InsertPiWalker {
public:
    InsertPiWalker(InsertPi* insert_pi) : _insertPi(insert_pi) {};

    void applyToDominatorNode(DominatorNode *domNode) 
    { 
        _insertPi->insertPiToNode(domNode->getNode()); 
    }

    // is called before a node and its children are processed
    void enterScope() {};

    // is called after node and children are processed
    void exitScope() {};

private:
    InsertPi* _insertPi;
};
//------------------------------------------------------------------------------

// Add a Pi node in the node if it is after each test 
// which tells something about a variable
//
// WARNING: Pi var live ranges may overlap the original var live ranges
// since we don't bother to add Phi nodes and rename subsequent uses of var.
void InsertPi::insertPi()
{
    InsertPiWalker insert_pi_walker(this);

    // dom-pre-order traversal
    DomTreeWalk<true, InsertPiWalker>(_domTree, insert_pi_walker, _mm);
    renamePiVariables();

    if (Log::isEnabled()) {
        Log::out() << "IR after Pi insertion" << std::endl;
        FlowGraph::printHIR(Log::out(), _irManager.getFlowGraph(), 
                            _irManager.getMethodDesc());
        FlowGraph::printDotFile(_irManager.getFlowGraph(), 
                                _irManager.getMethodDesc(), "withpi");
    }
}
//------------------------------------------------------------------------------

// add Pi in the node iff after a test which tells something about the var
void InsertPi::insertPiToNode(Node* block)
{
    Edge *dom_edge = 0;

    // see if there is a predecessor block idom such that 
    //  (1) idom dominates this one
    //  (2) this block dominates all other predecessors
    //  (3) idom has multiple out-edges
    //  (4) idom has only 1 edge to this node

    // (1a) if a predecessor dominates it must be idom
    Node *idom = _domTree.getIdom(block);

    // (3) must exist and have multiple out-edges
    if ((idom == NULL) || (idom->hasOnlyOneSuccEdge())) {
        return;
    }

    if (Log::isEnabled()) {
        Log::out() << "Checking block " << (int)block->getId() << " with idom "
                   << (int) idom->getId() << std::endl;
    }

    if (block->hasOnlyOnePredEdge()) {
        // must be from idom -- (1b)
        // satisfies (2) trivially
        dom_edge = *(block->getInEdges().begin());
    } else { 
        // check (1b) and (2)
        const Edges &inedges = block->getInEdges();
        typedef Edges::const_iterator EdgeIter;
        EdgeIter e_last = inedges.end();
        for (EdgeIter e_iter = inedges.begin(); e_iter != e_last; e_iter++) {
            Edge *in_edge = *e_iter;
            Node *pred_block = in_edge->getSourceNode();
            if (pred_block == idom) {
                // (1b) found idom
                if (dom_edge) {
                    // failed (4): idom found on more than one incoming edge
                    return;
                }
                dom_edge = in_edge;
            } else if (! _domTree.dominates(block, pred_block)) {
                // failed (2)
                return;
            }
        }
    }

    if (dom_edge) { 
        Edge *in_edge = dom_edge;
        Node *pred_block = idom;
        if (Log::isEnabled()) {
            Log::out() << "Checking branch for " << (int)block->getId() 
                       << " with idom "
                       << (int) idom->getId() << std::endl;
        }
        if (!pred_block->hasOnlyOneSuccEdge()) {
            Edge::Kind kind = in_edge->getKind();
            switch (kind) {
            case Edge::Kind_True:
            case Edge::Kind_False:
                {
                    Inst* branchi1 = (Inst*)pred_block->getLastInst();
                    assert(branchi1 != NULL);
                    BranchInst* branchi = branchi1->asBranchInst();
                    if (branchi && branchi->isConditionalBranch()) {
                        insertPiForBranch(block, branchi, kind);
                    } else {
                        return;
                    }
                }
                break;

            case Edge::Kind_Dispatch: 
                return;

            case Edge::Kind_Unconditional:
                // Previous block must have a PEI
                // since it had multiple out-edges.
                // This is the unexceptional condition.
                { 
                    Inst* lasti = (Inst*)pred_block->getLastInst();
                    assert(lasti != NULL);
                    insertPiForUnexceptionalPEI(block, lasti);
                }
                // We could look for a bounds check in predecessor.

                // But: since now all useful PEIs have explicit results,
                // they imply a Pi-like action.
                break;
            case Edge::Kind_Catch:
                break;
            default:
            break;
            }
        }
    }
}
//------------------------------------------------------------------------------

void InsertPi::insertPiForUnexceptionalPEI(Node *block, Inst *lasti)
{
    switch (lasti->getOpcode()) {
    case Op_TauCheckBounds:
        {
            // the number of newarray elements must be >= 0.
            assert(lasti->getNumSrcOperands() == 2);
            Opnd *idxOp = lasti->getSrc(1);
            Opnd *boundsOp = lasti->getSrc(0);

            if (Log::isEnabled()) {
                Log::out() << "Adding info about CheckBounds instruction ";
                lasti->print(Log::out());
                Log::out() << std::endl;
            }
            Type::Tag typetag = idxOp->getType()->tag;
            PiBound lb(typetag, int64(0));
            PiBound ub(typetag, 1, VarBound(boundsOp),int64(-1));
            PiCondition bounds0(lb, ub);
            Opnd *tauOpnd = lasti->getDst(); // use the checkbounds tau
            insertPiForOpndAndAliases(block, idxOp, bounds0, tauOpnd);

            PiBound idxBound(typetag, 1, VarBound(idxOp), int64(1));
            PiCondition bounds1(idxBound, PiBound(typetag, false));
            insertPiForOpndAndAliases(block, boundsOp, bounds1, tauOpnd);
        }
        break;
    case Op_NewArray:
        {
            // the number of newarray elements must be in [0, MAXINT32]
            assert(lasti->getNumSrcOperands() == 1);
            Opnd *numElemOpnd = lasti->getSrc(0);
            if (Log::isEnabled()) {
                Log::out() << "Adding info about NewArray instruction ";
                lasti->print(Log::out());
                Log::out() << std::endl;
            }
            Opnd *tauOpnd = getBlockTauEdge(block); // need to use a TauEdge
            PiCondition bounds0(PiBound(numElemOpnd->getType()->tag, 
                                        int64(0)),
                                PiBound(numElemOpnd->getType()->tag, 
                                        int64(0x7fffffff)));
            insertPiForOpndAndAliases(block, numElemOpnd, bounds0, tauOpnd);
        }
        break;
    case Op_NewMultiArray:
        {
            // the number of newarray dimensions must be >= 1.
            U_32 numOpnds = lasti->getNumSrcOperands();
            assert(numOpnds >= 1);
            StlSet<Opnd *> done(_mm);
            if (Log::isEnabled()) {
                Log::out() << "Adding info about NewMultiArray instruction ";
                lasti->print(Log::out());
                Log::out() << std::endl;
            }
            Opnd *tauOpnd = 0;
            // the number of newarray elements must be in [0, MAXINT32]
            for (U_32 opndNum = 0; opndNum < numOpnds; opndNum++) {
                Opnd *thisOpnd = lasti->getSrc(opndNum);
                if (!done.has(thisOpnd)) {
                    done.insert(thisOpnd);
                    PiCondition bounds0(PiBound(thisOpnd->getType()->tag, 
                                                int64(0)),
                                        PiBound(thisOpnd->getType()->tag, 
                                                int64(0x7fffffff)));
                    if ( !tauOpnd ) {
                        tauOpnd = getBlockTauEdge(block); // must use a tauEdge
                    }
                    insertPiForOpndAndAliases(block, thisOpnd, bounds0, tauOpnd);
                }
            }
        }
        break;
    default:
        break;
    }    
}
//------------------------------------------------------------------------------

SsaTmpOpnd* InsertPi::getBlockTauEdge(Node *block) {
    if ((_lastTauEdgeBlock == block) && _blockTauEdge) return _blockTauEdge;
    Inst *firstInst = (Inst*)block->getFirstInst();
    Inst *inst = firstInst->getNextInst();
    for (; inst != NULL; inst = inst->getNextInst()) {
        if (inst->getOpcode() == Op_TauEdge) {
            _blockTauEdge = inst->getDst()->asSsaTmpOpnd();
            assert(_blockTauEdge);
            _lastTauEdgeBlock = block;
            return _blockTauEdge;
        }
    }
    for (inst = firstInst->getNextInst(); inst != NULL; inst = inst->getNextInst()) {
        if ((inst->getOpcode() != Op_Phi) && (inst->getOpcode() != Op_TauPoint)) {
            break; // insert before inst.
        }
    }
    // no non-phis, insert before inst;
    TypeManager &tm = _irManager.getTypeManager();
    SsaTmpOpnd *tauOpnd = _irManager.getOpndManager().createSsaTmpOpnd(tm.getTauType());
    Inst* tauEdge = _irManager.getInstFactory().makeTauEdge(tauOpnd);
    if(Log::isEnabled()) {
        Log::out() << "Inserting tauEdge inst ";
        tauEdge->print(Log::out());
        if (inst!=NULL) {
            Log::out() << " before inst ";
            inst->print(Log::out()); 
        }
        Log::out() << std::endl;
    }
    if (inst != NULL) {
        tauEdge->insertBefore(inst);
    }  else {
        block->appendInst(tauEdge);
    }
    _blockTauEdge = tauOpnd;
    _lastTauEdgeBlock = block;
    return tauOpnd;
}
//------------------------------------------------------------------------------

// Insert Pi Nodes for any variables occurring in the branch test
//
// Since we're examining the test anyway, let's figure out the conditions
// here, too, so we don't have to duplicate any code.  Note that this 
// condition may already be in terms of Pi variables from the predecessor 
// block, since 
//   -- predecessor dominates this block
//   -- we are traversing blocks in a dominator-tree preorder
// so we must have already visited the predecessor.
//
// We also must add the new Pi variable to our map.
// 
void InsertPi::insertPiForBranch(Node* block, 
                                 BranchInst* branchi, 
                                 Edge::Kind kind) // True or False only
{
    Type::Tag instTypeTag = branchi->getType();
    if (!Type::isInteger(instTypeTag))
        return; 
    ComparisonModifier mod = branchi->getComparisonModifier();
    if (branchi->getNumSrcOperands() == 1) {
        Opnd *op0 = branchi->getSrc(0);
        PiCondition zeroBounds(PiBound(instTypeTag, (int64)0), 
                               PiBound(instTypeTag, (int64)0));
        switch (mod) {
        case Cmp_Zero:
            insertPiForComparison(block,
                                       Cmp_EQ,
                                       zeroBounds,
                                       op0,
                                       false,
                                       // negate if false edge
                                       (kind == Edge::Kind_False)); 
            break;
        case Cmp_NonZero:
            insertPiForComparison(block,
                                       Cmp_EQ, // use EQ
                                       zeroBounds,
                                       op0,
                                       false, 
                                       // but negate if true edge
                                       (kind == Edge::Kind_True));
            break;
    default:
        break;
        }
    } else {
        Opnd *op0 = branchi->getSrc(0);
        Opnd *op1 = branchi->getSrc(1);
        assert(branchi->getNumSrcOperands() == 2);
        PiCondition bounds0(op0->getType()->tag, op0);
        PiCondition bounds1(op1->getType()->tag, op1);
        if (!bounds0.isUnknown()) {
            insertPiForComparison(block,
                                       mod,
                                       bounds0,
                                       op1,
                                       false,
                                       // negate for false edge
                                       (kind == Edge::Kind_False));
        }
        if (!bounds1.isUnknown()) {
            insertPiForComparison(block,
                                       mod,
                                       bounds1,
                                       op0,
                                       true,
                                       // negate for false edge
                                       (kind == Edge::Kind_False));
        }
    }
}
//------------------------------------------------------------------------------

void InsertPi::insertPiForComparison(Node* block,
                                     ComparisonModifier mod,
                                     const PiCondition &bounds,
                                     Opnd* op,
                                     bool swap_operands,
                                     bool negate_comparison)
{
    if (Log::isEnabled()) {
        Log::out() << "insertPiForComparison(..., ";
        Log::out() << printableComparison(mod);
        Log::out() << ", ";
        bounds.print(Log::out());
        Log::out() << ", ";
        op->print(Log::out());
        Log::out() << ", ";
        Log::out() << (swap_operands ? "true" : "false");
        Log::out() << ", ";
        Log::out() << (negate_comparison ? "true" : "false");
        Log::out() << ")" << std::endl;

        // Print last inst from all prev blocks.
        Edges::const_iterator it = block->getInEdges().begin(),
            end = block->getInEdges().end();
        for(; it != end; ++it) {
            Edge* edge = (*it);
            Log::out() << "pred inst---> ";
            ((Inst*)edge->getSourceNode()->getLastInst())->print(Log::out());
            Log::out() << std::endl;
        }
    }

    PiCondition bounds0 = bounds;
    // add a Pi node for immediate value.
    if (negate_comparison) {
        mod = negateComparison(mod);
        swap_operands = !swap_operands;
        if (Log::isEnabled()) {
            Log::out() << "insertPiForComparison: negating comparison to " ;
            Log::out() << printableComparison(mod);
            Log::out() << std::endl;
        }
    }
    switch (mod) {
    case Cmp_EQ:
        if (!negate_comparison)
            insertPiForOpndAndAliases(block, op, bounds0, NULL);
        else {
            if (Log::isEnabled()) {
                Log::out() << "insertPiForComparison: cannot represent ! Cmp_EQ" << std::endl;
            }
        }
        // we can't represent the other case
        break;
    case Cmp_NE_Un:
        if (negate_comparison)
            insertPiForOpndAndAliases(block, op, bounds0, NULL);
        else {
            if (Log::isEnabled()) {
                Log::out() << "insertPiForComparison: cannot represent Cmp_NE_Un" << std::endl;
            }
        }
        // we can't represent the other case
        break;
    case Cmp_GT_Un:
        if (swap_operands) { // op > bounds, only a lower bound on op
            Type::Tag optag = op->getType()->tag;
            if (!Type::isUnsignedInteger(optag)) {
                // 1 is a lower bound on int op
                PiCondition oneBounds(PiBound(optag, (int64)1), 
                                      PiBound(optag, (int64)1));
                PiCondition oneLowerBound(oneBounds.only_lower_bound());
                insertPiForOpndAndAliases(block, op, oneLowerBound, NULL);
            } else {
                // we can be more precise for an unsigned op
                bounds0 = bounds0.cast(unsignType(bounds0.getType()));
                PiCondition bounds1a(bounds0.only_lower_bound());
                PiCondition bounds1(bounds1a.add((int64)1));
                if (! bounds1.getLb().isUnknown())
                    insertPiForOpndAndAliases(block, op, bounds1, NULL);
                else {
                    if (Log::isEnabled()) {
                        Log::out() << "insertPiForComparison(1): bounds1 LB is Unknown;\n\tbounds is ";
                        bounds.print(Log::out());
                        Log::out() << "\n\tbounds0 is ";
                        bounds0.print(Log::out());
                        Log::out() << "\n\tbounds1a is ";
                        bounds1a.print(Log::out());
                        Log::out() << "\n\tbounds1 is ";
                        bounds1.print(Log::out());
                        Log::out() << std::endl;
                    }
                }
            }
        } else { // bounds > op, only an upper bound on op
            Type::Tag optag = op->getType()->tag;
            if (Type::isUnsignedInteger(optag)) {
                // for an unsigned upper bound, we're ok
                bounds0 = bounds0.cast(unsignType(bounds0.getType()));
                PiCondition bounds1(bounds0.only_upper_bound().add((int64)-1));
                if (! bounds1.getUb().isUnknown())
                    insertPiForOpndAndAliases(block, op, bounds1, NULL);
                else {
                    if (Log::isEnabled()) {
                        Log::out() << "insertPiForComparison(2): bounds1 LB is Unknown;\n\tbounds is ";
                        bounds.print(Log::out());
                        Log::out() << "\n\tbounds0 is ";
                        bounds0.print(Log::out());
                        Log::out() << "\n\tbounds1 is ";
                        bounds1.print(Log::out());
                        Log::out() << std::endl;
                    }
                }
            } else {
                // otherwise, we know nothing unless bound is a small constant
                PiCondition bounds1(bounds0.only_upper_bound().add((int64)-1));
                if (bounds0.getUb().isConstant()) {
                    int64 ubConst = bounds1.getUb().getConst();
                    if (((optag == Type::Int32) &&
                         ((ubConst&0xffffffff) <= 0x7ffffff) && 
                         ((ubConst&0xffffffff) >= 0)) ||
                        ((optag == Type::Int64) &&
                         ((ubConst <= 0x7ffffff) && 
                          (ubConst >= 0)))) {
                        insertPiForOpndAndAliases(block, op, bounds1, NULL);
                    } else {
                        if (Log::isEnabled()) {
                            Log::out() << "insertPiForComparison(2): bounds1 LB is Unknown;\n\tbounds is ";
                            bounds.print(Log::out());
                            Log::out() << "\n\tbounds0 is ";
                            bounds0.print(Log::out());
                            Log::out() << "\n\tbounds1 is ";
                            bounds1.print(Log::out());
                            Log::out() << std::endl;
                        }
                    }
                }
            }
        }
        break;
    case Cmp_GT:
        if (swap_operands) { // op > bounds, only a lower bound on op
            PiCondition bounds1a(bounds0.only_lower_bound());
            PiCondition bounds1(bounds1a.add((int64)1));
            if (! bounds1.getLb().isUnknown())
                insertPiForOpndAndAliases(block, op, bounds1, NULL);
            else {
                if (Log::isEnabled()) {
                    Log::out() << "insertPiForComparison(1): bounds1 LB is Unknown;\n\tbounds is ";
                    bounds.print(Log::out());
                    Log::out() << "\n\tbounds0 is ";
                    bounds0.print(Log::out());
                    Log::out() << "\n\tbounds1a is ";
                    bounds1a.print(Log::out());
                    Log::out() << "\n\tbounds1 is ";
                    bounds1.print(Log::out());
                    Log::out() << std::endl;
                }
            }
        } else { // bounds > op, only an upper bound on op
            PiCondition bounds1(bounds0.only_upper_bound().add((int64)-1));
            if (! bounds1.getUb().isUnknown())
                insertPiForOpndAndAliases(block, op, bounds1, NULL);
            else {
                if (Log::isEnabled()) {
                    Log::out() << "insertPiForComparison(2): bounds1 LB is Unknown;\n\tbounds is ";
                    bounds.print(Log::out());
                    Log::out() << "\n\tbounds0 is ";
                    bounds0.print(Log::out());
                    Log::out() << "\n\tbounds1 is ";
                    bounds1.print(Log::out());
                    Log::out() << std::endl;
                }
            }
        }
        break;
    case Cmp_GTE_Un:
        if (swap_operands) { // op >= bounds, only lower bound on op
            Type::Tag optag = op->getType()->tag;
            if (!Type::isUnsignedInteger(optag)) {
                // 0 is a lower bound on an int op
                PiCondition zeroBounds(PiBound(optag, (int64)0), 
                                       PiBound(optag, (int64)0));
                PiCondition zeroLowerBound(zeroBounds.only_lower_bound());
                insertPiForOpndAndAliases(block, op, zeroLowerBound, NULL);
            } else {
                // we can be more precise for an unsigned op lb
                bounds0 = bounds0.cast(unsignType(bounds0.getType()));
                if (! bounds0.getLb().isUnknown()) {
                    insertPiForOpndAndAliases(block, op, 
                                                  bounds0.only_lower_bound(), NULL);
                } else {
                    if (Log::isEnabled()) {
                        Log::out() << "insertPiForComparison(3): bounds0 LB is Unknown;\n\tbounds is ";
                        bounds.print(Log::out());
                        Log::out() << "\n\tbounds0 is ";
                        bounds0.print(Log::out());
                        Log::out() << std::endl;
                    }
                }
            }
        } else { // bounds >= op, only upper bound on op
            Type::Tag optag = op->getType()->tag;
            if (Type::isUnsignedInteger(optag)) {
                // unsigned ub on unsigned op 
                bounds0 = bounds0.cast(unsignType(bounds0.getType()));
                if (! bounds0.getUb().isUnknown())
                    insertPiForOpndAndAliases(block, op, 
                                                  bounds0.only_upper_bound(), NULL);
                else {
                    if (Log::isEnabled()) {
                        Log::out() << "insertPiForComparison(4): bounds0 UB is Unknown;\n\tbounds is ";
                        bounds.print(Log::out());
                        Log::out() << "\n\tbounds0 is ";
                        bounds0.print(Log::out());
                        Log::out() << std::endl;
                    }
                }
            } else {
                // otherwise, we know nothing unless bound is a small constant
                if (bounds0.getUb().isConstant()) {
                    int64 ubConst = bounds0.getUb().getConst();
                    if (((optag == Type::Int32) &&
                         ((ubConst&0xffffffff) <= 0x7ffffff) && 
                         ((ubConst&0xffffffff) >= 0)) ||
                        ((optag == Type::Int64) &&
                         ((ubConst <= 0x7ffffff) && 
                          (ubConst >= 0)))) {
                        insertPiForOpndAndAliases(block, op, bounds0, NULL);
                    } else {
                        if (Log::isEnabled()) {
                            Log::out() << "insertPiForComparison(2): bounds0 LB is Unknown;\n\tbounds is ";
                            bounds.print(Log::out());
                            Log::out() << "\n\tbounds0 is ";
                            bounds0.print(Log::out());
                            Log::out() << std::endl;
                        }
                    }
                }
            }
        }
        break;
    case Cmp_GTE:
        if (swap_operands) { // op >= bounds, only lower bound on op
            if (! bounds0.getLb().isUnknown()) {
                insertPiForOpndAndAliases(block, op, 
                                              bounds0.only_lower_bound(), NULL);
            } else {
                if (Log::isEnabled()) {
                    Log::out() << "insertPiForComparison(3): bounds0 LB is Unknown;\n\tbounds is ";
                    bounds.print(Log::out());
                    Log::out() << "\n\tbounds0 is ";
                    bounds0.print(Log::out());
                    Log::out() << std::endl;
                }
            }
        } else { // bounds >= op, only upper bound on op
            if (! bounds0.getUb().isUnknown())
                insertPiForOpndAndAliases(block, op, 
                                              bounds0.only_upper_bound(), NULL);
            else {
                if (Log::isEnabled()) {
                    Log::out() << "insertPiForComparison(4): bounds0 UB is Unknown;\n\tbounds is ";
                    bounds.print(Log::out());
                    Log::out() << "\n\tbounds0 is ";
                    bounds0.print(Log::out());
                    Log::out() << std::endl;
                }
            }
        }
        break;
    case Cmp_Zero:
    case Cmp_NonZero:
    case Cmp_Mask:
        assert(0);
        break;
    default:
    assert(false);
    break;
    }
}
//------------------------------------------------------------------------------

void InsertPi::insertPiForOpnd(Node *block, 
                               Opnd *org, 
                               const PiCondition &cond,
                               Opnd *tauOpnd)
{
    if (ConstantFolder::isConstant(org)) {
        if (Log::isEnabled()) {
            Log::out() << "Skipping Pi Node for opnd ";
            org->print(Log::out());
            Log::out() << " under condition ";
            cond.print(Log::out());
            Log::out() << " since it is constant" << std::endl;
        }
    } else {
        PiOpnd *piOpnd = _irManager.getOpndManager().createPiOpnd(org);
        Inst *headInst = (Inst*)block->getFirstInst();
        PiCondition *condPtr = new (_irManager.getMemoryManager()) PiCondition(cond);
        if (tauOpnd == 0)
            tauOpnd = getBlockTauEdge(block);
        Inst *newInst = _irManager.getInstFactory().makeTauPi(piOpnd, org, tauOpnd, condPtr);
        Inst *place = headInst->getNextInst();
        while (place != NULL) {
            Opcode opc = place->getOpcode();
            if ((opc != Op_Phi) && (opc != Op_TauPoint) && (opc != Op_TauEdge))
                break;
            place = place->getNextInst();
        }
        if (Log::isEnabled()) {
            Log::out() << "Inserting Pi Node for opnd ";
            org->print(Log::out());
            Log::out() << " under condition ";
            cond.print(Log::out());
            if (place!=NULL) {
                Log::out() << " just before inst ";
                place->print(Log::out());
            }
            Log::out() << std::endl;
        }
        if (place != NULL) {
            newInst->insertBefore(place);
        } else {
            block->appendInst(newInst);
        }
    }
}
//------------------------------------------------------------------------------

// dereferencing through Pis, 0 if not constant.
Opnd* InsertPi::getConstantOpnd(Opnd *opnd)
{
    return ConstantFolder::isConstant(opnd) ? opnd : NULL;
}
//------------------------------------------------------------------------------

bool InsertPi::getAliases(Opnd *opnd, AbcdAliases *aliases, int64 addend)
{
    Inst *inst = opnd->getInst();
    switch (inst->getOpcode()) {
    case Op_TauPi:
        return getAliases(inst->getSrc(0), aliases, addend);

    case Op_Add:
        {
            Opnd *op0 = inst->getSrc(0);
            Opnd *op1 = inst->getSrc(1);
            Opnd *constOpnd0 = getConstantOpnd(op0);
            Opnd *constOpnd1 = getConstantOpnd(op1);
            if ((constOpnd0 || constOpnd1) &&
                (inst->getType() == Type::Int32)) {
                // I assume we've done folding first
                assert(!(constOpnd0 && constOpnd1));
                if (constOpnd1) {
                    // swap the operands;
                    constOpnd0 = constOpnd1;
                    op1 = op0;
                }
                // now constOpnd0 should be constant
                // op1 is the non-constant operand

                Inst *inst0 = constOpnd0->getInst();
                assert(inst0);
                ConstInst *cinst0 = inst0->asConstInst();
                assert(cinst0);
                ConstInst::ConstValue cv = cinst0->getValue();
                I_32 c = cv.i4;
                int64 sumc = c + addend;
                if (add_overflowed<int64>(sumc, c, addend)) {
                    return false;
                } else {
                    VarBound vb(op1);
                    aliases->theSet.insert(PiBound(inst->getType(), 1, vb, sumc));
                    getAliases(op1, aliases, sumc);
                    return true;
                }
            }
        }
        break;
    case Op_Sub:
        {
            Opnd *constOpnd = getConstantOpnd(inst->getSrc(1));
            if (constOpnd && (inst->getType() == Type::Int32)) {
                Opnd *op1 = constOpnd;
                Inst *inst1 = op1->getInst();
                assert(inst1);
                ConstInst *cinst1 = inst1->asConstInst();
                assert(cinst1);
                ConstInst::ConstValue cv = cinst1->getValue();
                int64 c = cv.i4;
                int64 negc = -c;
                int64 subres = addend + negc;
                if (neg_overflowed<int64>(negc, c) ||
                    add_overflowed<int64>(subres, addend, negc)) {
                    return false;
                } else {
                    VarBound vb(op1);
                    aliases->theSet.insert(PiBound(inst->getType(), 1, vb, subres));
                    getAliases(op1, aliases, subres);
                    return true;
                }
            }
        }
        break;
    case Op_Copy:
        assert(0); // do copy propagation first
        break;
    case Op_TauCheckZero:
        return false;
    default:
        break;
    }
    return false;
}
//------------------------------------------------------------------------------

// checks for aliases of opnd, inserts them.
void InsertPi::insertPiForOpndAndAliases(Node *block, 
                                         Opnd *org, 
                                         const PiCondition &cond,
                                         Opnd *tauOpnd)
{
    const PiBound &lb = cond.getLb();
    const PiBound &ub = cond.getUb();

    if (_useAliases) {
        if (Log::isEnabled()) {
            Log::out() << "Inserting Pi Node for opnd ";
            org->print(Log::out());
            Log::out() << " and its aliases";
            Log::out() << " under condition ";
            cond.print(Log::out());
            Log::out() << std::endl;
        }
        AbcdAliases aliases(_mm);
        // check for aliases
        insertPiForOpnd(block, org, cond, tauOpnd);
        if (getAliases(org, &aliases, 0)) {
            if (Log::isEnabled()) {
                Log::out() << "Has aliases ";
                AbcdAliasesSet::iterator iter = aliases.theSet.begin();
                AbcdAliasesSet::iterator end = aliases.theSet.end();
                for ( ; iter != end; iter++) {
                    PiBound alias = *iter;
                    alias.print(Log::out());
                    Log::out() << " ";
                }
                Log::out() << std::endl;
            }
            AbcdAliasesSet::iterator iter = aliases.theSet.begin();
            AbcdAliasesSet::iterator end = aliases.theSet.end();
            for ( ; iter != end; iter++) {
                PiBound alias = *iter; 
                PiBound inverted = alias.invert(org); // org - c
                // plug-in lb and ub into inverted, yields bounds:
                //   [ lb - c, ub - c ]
                PiCondition renamedCondition(PiBound(inverted, org, lb),
                                             PiBound(inverted, org, ub));
                insertPiForOpnd(block, alias.getVar().the_var, 
                                    renamedCondition, tauOpnd);
            }
        }
    } else {
        insertPiForOpnd(block, org, cond, tauOpnd);
    }
}
//------------------------------------------------------------------------------

// a DomWalker, to be applied forwards/preorder
class RenamePiWalker {
public:

    RenamePiWalker(InsertPi *insert_pi,
                   MemoryManager &localMM,
                   SparseOpndMap* &piMap0,
                   int sizeEstimate0) : 
        _insertPi(insert_pi), 
        localMemManager(localMM), 
        _piMap(piMap0),
        sizeEstimate(sizeEstimate0)
    {}

    void applyToDominatorNode(DominatorNode *domNode) 
    { 
        _insertPi->renamePiVariablesInNode(domNode->getNode()); 
    }

    void enterScope() 
    {
        if (!_piMap) _piMap = 
            new (localMemManager) SparseOpndMap(sizeEstimate,
                                                localMemManager, 1, 4, 7);
        _piMap->enter_scope(); 
    }

    void exitScope() 
    { 
        _piMap->exit_scope(); 
    }
private:
    InsertPi* _insertPi;
    MemoryManager &localMemManager;
    SparseOpndMap* &_piMap;
    int sizeEstimate;
};
//------------------------------------------------------------------------------

void InsertPi::renamePiVariables()
{
    MethodDesc &methodDesc= _irManager.getMethodDesc();
    U_32 byteCodeSize = methodDesc.getByteCodeSize();
    MemoryManager localMemManager("Abcd::renamePiNodes");

    RenamePiWalker theWalker(this, localMemManager, _piMap, byteCodeSize);
    DomTreeWalk<true, RenamePiWalker>(_domTree, theWalker, localMemManager);
}
//------------------------------------------------------------------------------

void InsertPi::renamePiVariablesInNode(Node *block)
{
    // For each variable use in the block, check for a Pi version in
    // the piTable.  Since we are visiting in preorder over dominator
    // tree dominator order, any found version will dominate this node.

    // Phase 0: remap just Pi inst source operands.
    Inst* headInst = (Inst*)block->getFirstInst();
    for (Inst* inst = headInst->getNextInst(); inst != NULL; inst = inst->getNextInst()) {
        if (inst->getOpcode() == Op_TauPi) {
            // Replace Pi source operands with renames from the map.
            Opnd *dstOpnd = inst->getDst();
            assert(dstOpnd->isPiOpnd());
            Opnd *srcOpnd = inst->getSrc(0);
            if (_useAliases) {
                if (srcOpnd->isSsaVarOpnd()) {
                    srcOpnd = srcOpnd->asSsaVarOpnd()->getVar();
                }
            }
            // Find the end of the operand replace chain.
            // The most constrained operand is being used, the more
            // opportunities we have for optimization.
            Opnd *replaceOpnd = _piMap->lookupTillEnd(srcOpnd);
            if (replaceOpnd) {
                // Disallow remapping source operand of Pi Nodes to their
                // destination operands.
                if (Log::isEnabled()) {
                    Log::out() << "remapping src in Pi: ";
                    inst->print(Log::out());
                    Log::out() << ", replaceOpnd: ";
                    replaceOpnd->print(Log::out());
                }
                if (dstOpnd->getId() != replaceOpnd->getId()) {
                    inst->setSrc(0, replaceOpnd);
                    srcOpnd = replaceOpnd;
                    if (Log::isEnabled()) {
                        Log::out() << "... done" << std::endl;
                    }
                } else {
                    if (Log::isEnabled()) {
                        Log::out() << "... defines this opnd, cannot remap" << std::endl;
                    }
                }
            }

            // We now replaced the source. Add any Pi node destination to the map.
            _piMap->insert(srcOpnd, dstOpnd);
            if (Log::isEnabled()) {
                Log::out() << "adding remap for Pi of ";
                srcOpnd->print(Log::out());
                Log::out() << " to ";
                inst->getDst()->print(Log::out());
                Log::out() << std::endl;
            }
        }
    }

    // Phase 1: add Pi remappings, remap source operands of other instructions
    // and pi conditions.
    for (Inst* inst = headInst->getNextInst(); inst != NULL; inst = inst->getNextInst()) {

        // Remap source operands if they match a Pi definition.
        U_32 numOpnds = inst->getNumSrcOperands();
        for (U_32 i=0; i<numOpnds; i++) {
            Opnd *opnd = inst->getSrc(i);
            while (opnd->isPiOpnd()) {
                opnd = opnd->asPiOpnd()->getOrg();
            }
            // Transitively look up for deepest Pi renamings of this operand.
            // The most constrained operand is being used, the more
            // opportunities we have for optimization.
            Opnd *foundOpnd = _piMap->lookupTillEnd(opnd);
            if (foundOpnd) {
                // Remap the source operand except for Pi instruction and for
                // array argument for chkbounds instruction. The latter is
                // because (a) we do not need any facts provided by pi renaming
                // for this operand, (b) we should limit array operand renaming
                // to be able to search the proof path by exact array operand
                // id.
                if (inst->getOpcode() != Op_TauPi &&
                    (inst->getOpcode() != Op_TauCheckBounds || i != 0)) {
                    inst->setSrc(i, foundOpnd);
                }
            }
        }

        // Remap variables appearing in the condition of the Pi node.
        if (inst->getOpcode() == Op_TauPi) {
            TauPiInst *thePiInst = inst->asTauPiInst();
            assert(thePiInst);

            if (Log::isEnabled()) {
                Log::out() << "remapping condition in ";
                inst->print(Log::out());
                Log::out() << std::endl;
            }
            PiCondition *cond = thePiInst->cond;
            if (Log::isEnabled()) {
                Log::out() << "  original condition is ";
                cond->print(Log::out());
                Log::out() << std::endl;
            }
            Opnd *lbRemap = cond->getLb().getVar().the_var;
            if (lbRemap) {
                if (Log::isEnabled()) {
                    Log::out() << "  has lbRemap=";
                    lbRemap->print(Log::out());
                    Log::out() << std::endl;
                }
                if (lbRemap->isPiOpnd())
                    lbRemap = lbRemap->asPiOpnd()->getOrg();
                Opnd *lbRemapTo = _piMap->lookupTillEnd(lbRemap);
                if (lbRemapTo) {
                    if (Log::isEnabled()) {
                        Log::out() << "adding remap of lbRemap=";
                        lbRemap->print(Log::out());
                        Log::out() << " to lbRemapTo=";
                        lbRemapTo->print(Log::out());
                        Log::out() << " to condition ";
                        cond->print(Log::out());
                    }
                    PiCondition remapped(*cond, lbRemap, lbRemapTo);
                    if (Log::isEnabled()) {
                        Log::out() << " YIELDS1 ";
                        remapped.print(Log::out());
                    }
                    *cond = remapped;
                    if (Log::isEnabled()) {
                        Log::out() << " YIELDS ";
                        cond->print(Log::out());
                        Log::out() << std::endl;
                    }
                }
            }
            Opnd *ubRemap = cond->getUb().getVar().the_var;
            if (ubRemap && (lbRemap != ubRemap)) {
                if (Log::isEnabled()) {
                    Log::out() << "  has ubRemap=";
                    ubRemap->print(Log::out());
                    Log::out() << std::endl;
                }
                if (ubRemap->isPiOpnd())
                    ubRemap = ubRemap->asPiOpnd()->getOrg();
                Opnd *ubRemapTo = _piMap->lookupTillEnd(ubRemap);
                if (ubRemapTo) {
                    if (Log::isEnabled()) {
                        Log::out() << "adding remap of ubRemap=";
                        ubRemap->print(Log::out());
                        Log::out() << " to ubRemapTo=";
                        ubRemapTo->print(Log::out());
                        Log::out() << " to condition ";
                        cond->print(Log::out());
                    }
                    PiCondition remapped(*cond, ubRemap, ubRemapTo);
                    if (Log::isEnabled()) {
                        Log::out() << " YIELDS1 ";
                        remapped.print(Log::out());
                    }
                    *cond = remapped;
                    if (Log::isEnabled()) {
                        Log::out() << " YIELDS ";
                        cond->print(Log::out());
                        Log::out() << std::endl;
                    }
                }
            }
        }
    }
}
//------------------------------------------------------------------------------

// a ScopedDomNodeInstWalker, forward/preorder
class RemovePiWalker {
public:
    RemovePiWalker(InsertPi* ins) : _insertPi(ins), block(0) // forward
    {}

    void startNode(DominatorNode *domNode) { block = domNode->getNode(); };
    void applyToInst(Inst *i) { _insertPi->removePiOnInst(block, i); }
    void finishNode(DominatorNode *domNode) {}

    void enterScope() {}
    void exitScope() {}
private:
    InsertPi* _insertPi;
    Node* block;
};
//------------------------------------------------------------------------------

void InsertPi::removePi()
{
    RemovePiWalker removePiWalker(this);
    typedef ScopedDomNodeInst2DomWalker<true, RemovePiWalker> 
        RemovePiDomWalker;
    RemovePiDomWalker removePiDomWalker(removePiWalker);
    DomTreeWalk<true, RemovePiDomWalker>(_domTree, removePiDomWalker, _mm);
}
//------------------------------------------------------------------------------

void InsertPi::removePiOnInst(Node* block, Inst *inst)
{
    if ( inst->getOpcode() == Op_TauPi ) {
        inst->unlink();
    }else{
        // replace Pi operands with original ones
        U_32 num_opnds = inst->getNumSrcOperands();
        for (U_32 i = 0; i < num_opnds; i++) {
            Opnd* pi_opnd = inst->getSrc(i);
            while ( pi_opnd->isPiOpnd() ) {
                pi_opnd = pi_opnd->asPiOpnd()->getOrg();
            }
            inst->setSrc(i, pi_opnd);
        }
    }
}
//------------------------------------------------------------------------------

} //namespace Jitrino