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

/**
 * @author Intel, Pavel A. Ozhdikhin
 *
 */

#include <assert.h>
#include <iostream>
#include <algorithm>
#include "Stl.h"
#include "Log.h"
#include "open/types.h"
#include "Inst.h"
#include "irmanager.h"
#include "Dominator.h"
#include "Loop.h"
#include "globalcodemotion.h"
#include "CSEHash.h"
#include "Opcode.h"
#include "constantfolder.h"
#include "walkers.h"
#include "optimizer.h"
#include "hashvaluenumberer.h"
#include "aliasanalyzer.h"
#include "memoryopt.h"
#include "FlowGraph.h"
#include "optpass.h"

namespace Jitrino {

    static void printLabel(std::ostream& os, DominatorNode* dNode) {
        FlowGraph::printLabel(os, dNode->getNode());
    }

DEFINE_SESSION_ACTION(GlobalCodeMotionPass, gcm, "Global Code Motion")

void GlobalCodeMotionPass::_run(IRManager& irm) {
    OptPass::splitCriticalEdges(irm);
    OptPass::computeDominatorsAndLoops(irm);
    MemoryManager& memoryManager = irm.getNestedMemoryManager();
    DominatorTree* dominatorTree = irm.getDominatorTree();
    LoopTree* loopTree = irm.getLoopTree();
    assert(dominatorTree->isValid() && loopTree->isValid());
    GlobalCodeMotion gcm(irm, memoryManager, *dominatorTree, loopTree);
    gcm.runPass();
}

DEFINE_SESSION_ACTION(GlobalValueNumberingPass, gvn, "Global Value Numbering")

void GlobalValueNumberingPass::_run(IRManager& irm) {
    OptPass::computeDominatorsAndLoops(irm);
    DominatorTree* dominatorTree = irm.getDominatorTree();
    assert(dominatorTree && dominatorTree->isValid());
    LoopTree* loopTree = irm.getLoopTree();
    assert(loopTree && loopTree->isValid());
    MemoryManager& memoryManager = irm.getNestedMemoryManager();
    ControlFlowGraph& flowGraph = irm.getFlowGraph();

    DomFrontier frontier(memoryManager,*dominatorTree,&flowGraph);
    TypeAliasAnalyzer aliasAnalyzer;
    MemoryOpt mopt(irm, memoryManager, *dominatorTree,
        frontier, loopTree, &aliasAnalyzer);
    mopt.runPass();
    HashValueNumberer valueNumberer(irm, *dominatorTree);
    valueNumberer.doGlobalValueNumbering(&mopt);
}


GlobalCodeMotion::GlobalCodeMotion(IRManager &irManager0, 
                                   MemoryManager& memManager,
                                   DominatorTree& dom0,
                                   LoopTree *loopTree0)
    : irManager(irManager0), 
      fg(irManager0.getFlowGraph()),
      methodDesc(irManager0.getMethodDesc()),
      mm(memManager),
      dominators(dom0),
      loopTree(loopTree0),
      flags(*irManager.getOptimizerFlags().gcmFlags),
      earliest(memManager),
      latest(memManager),
      visited(memManager),
      uses(memManager)
{
}

GlobalCodeMotion::~GlobalCodeMotion()
{
}

void 
GlobalCodeMotion::readFlags(Action* argSource, GcmFlags* flags) {
    IAction::HPipeline p = NULL; //default pipeline for argSource
    flags->dry_run = argSource->getBoolArg(p, "gcm.dry_run", false);
    flags->sink_stvars = argSource->getBoolArg(p, "gcm.sink_stvars", false);
    flags->min_cut = argSource->getBoolArg(p, "gcm.min_cut", false);
    flags->sink_constants = argSource->getBoolArg(p, "gcm.sink_constants", false);
}

void GlobalCodeMotion::showFlags(std::ostream& os) {
    os << "  global code motion flags:"<<std::endl;
    os << "    gcm.dry_run[={on|OFF}]        - don't really move anything" << std::endl;
    os << "    gcm.sink_stvars[={on|OFF}]    - raise ldvar, sink stvar to Phi nodes"  << std::endl;
    os << "    gcm.min_cut[={on|OFF}]        - duplicate placement on mincut between def and uses" << std::endl;
    os << "    gcm.sink_constants[={ON|off}] - sink constants after placement" << std::endl;
}

void GlobalCodeMotion::runPass() {
    if (flags.dry_run && !flags.sink_constants) return;

    if (Log::isEnabled()) {
        Log::out() << "IR before GCM pass" << std::endl;
        FlowGraph::printHIR(Log::out(), irManager.getFlowGraph(), methodDesc);
        FlowGraph::printDotFile(irManager.getFlowGraph(), methodDesc, "beforegcm");
        dominators.printDotFile(methodDesc, "beforegcm.dom");
        dominators.printIndentedTree(Log::out(), "beforegcm.dom");
        loopTree->printDotFile(methodDesc, "beforegcm.loop");
    }

    if (!flags.dry_run) {
        // schedule instructions early
        scheduleAllEarly();
        // now earliest[i] = domNode for earliest placement.

        clearVisited();

        scheduleAllLate();
    }

    // sink loads of constants, since IPF back-end doesn't re-materialize
    if (flags.sink_constants)
        sinkAllConstants();
    // patch up SSA form in case live ranges overlap now
    // for now, we don't move Phis, Ldvars, or Stvars, so Ssa form is unaffected
    // fixSsaForm();

    if (Log::isEnabled() ) {
        Log::out() << "IR after GCM pass" << std::endl;
        FlowGraph::printHIR(Log::out(),irManager.getFlowGraph(), methodDesc);
        FlowGraph::printDotFile( irManager.getFlowGraph(), methodDesc, "aftergcm");
        dominators.printDotFile(methodDesc, "aftergcm.dom");
    }
}

// EARLY SCHEDULING

// a DomNodeInstWalker, forwards/preorder
class GcmScheduleEarlyWalker {
    GlobalCodeMotion *thePass;
    Node *block;
    DominatorNode *domNode;
public:
    void startNode(DominatorNode *domNode0) { 
        domNode = domNode0;
        block = domNode->getNode();
        if (Log::isEnabled() ) {
            Log::out() << "Begin early scheduling of block ";
            FlowGraph::print(Log::out(), block);
            Log::out() << std::endl;
        }    
    };
    void applyToInst(Inst *i) { thePass->scheduleEarly(domNode, i);  };
    void finishNode(DominatorNode *domNode) { 
        Node *block1 = domNode->getNode();
        if( !(block == block1) ) assert(0);
        if (Log::isEnabled() ) {
            Log::out() << "Done early scheduling of block ";
            FlowGraph::print(Log::out(), block);
            Log::out() << std::endl;
        }    
    };
    
    GcmScheduleEarlyWalker(GlobalCodeMotion *thePass0)
        : thePass(thePass0), block(0), domNode(0)
    {
    };
};

void GlobalCodeMotion::scheduleAllEarly()
{
    GcmScheduleEarlyWalker scheduleEarlyWalker(this);

    // adapt the DomNodeInstWalker to a forwards DomWalker
    typedef DomNodeInst2DomWalker<true, GcmScheduleEarlyWalker> EarlyDomInstWalker;
    EarlyDomInstWalker domInstWalker(scheduleEarlyWalker);
    
    // do the walk, pre-order
    DomTreeWalk<true, EarlyDomInstWalker>(dominators, domInstWalker, mm);
}

// since it will usually visit in the right order, we used dominator tree order
// BUT: since GVN may leave instructions out of place, we can't count on
// operands having been visited before the instruction.
// THOUGH: we guarantee the head of each cycle (when placed legally) will
// be a Phi function, and thus pinned.  This means that for non-Phi instrs,
// we can just place all operands first, then this instruction.
// For Phi instructions, we must just leave them in place (pinned) and leave
// the operands for later visiting.

// domNode should be 0 or i's DominatorNode, if we happen to know it.
void GlobalCodeMotion::scheduleEarly(DominatorNode *domNode, Inst *i)
{
    if (i->isLabel()) return;
    if (alreadyVisited(i)) {
        /* if (Log::isEnabled() ) {
        Log::out() << "= Inst is already scheduled early: "; i->print(Log::out());
        Log::out() << std::endl;
        }
        */
        return;
    }

    Node *cfgNode = i->getNode();
    if (domNode==NULL) {
        domNode = dominators.getDominatorNode(cfgNode);
    }
    bool pinned = isPinned(i);
    markAsVisited(i);

    if (Log::isEnabled() ) {
        Log::out() << "< Beginning early scheduling of " << (pinned?"":"not");
        Log::out() << " pinned inst ";  i->print(Log::out());
        Log::out() << std::endl;
    }

    if (pinned) {       // leave it here
        // We place operands before placing instruction, to get ordering right
        // in the block; in normal code, operands should appear first and 
        // have been already placed, but after GVN we don't have that guarantee.
        if (i->getOpcode() != Op_Phi) { // phi operands must also be pinned, skip them.
            if (Log::isEnabled() ) {
                Log::out() << " Inst is not a Phi, processing operands" << std::endl;
            }
            // for others, record uses in this instruction
            U_32 numSrcs = i->getNumSrcOperands();
            for (U_32 srcNum=0; srcNum < numSrcs; ++srcNum) {
                Opnd *srcOpnd = i->getSrc(srcNum);
                Inst *srcInst = srcOpnd->getInst();
                scheduleEarly(0, srcInst);
                if (Log::isEnabled() ) {
                    Log::out() << " Recording that "; srcInst->print(Log::out());
                    Log::out() << " is used by "; i->print(Log::out());
                    Log::out() << std::endl;
                }
                UsesMap::iterator it = uses.find(srcInst);
                UsesSet* theSet = NULL; 
                if (it == uses.end()) {
                    theSet = new (mm) UsesSet(mm);
                    it = uses.insert(::std::make_pair(srcInst, theSet)).first;
                }
                theSet = it->second;
                theSet->insert(i);
            }
        }

        // now place instruction
        earliest[i] = domNode;

        if (i->getOperation().canThrow()) {
            // as a special case, mark it as being in the normal successor node;
            // this will cause dependent instructions to be placed correctly.
            Node *peiNode = earliest[i]->getNode();

            const Edges &outedges = peiNode->getOutEdges();
            typedef Edges::const_iterator EdgeIter;
            EdgeIter eLast = outedges.end();
            DominatorNode *newDom = 0;
            for (EdgeIter eIter = outedges.begin(); eIter != eLast; eIter++) {
                Edge *outEdge = *eIter;
                Edge::Kind kind = outEdge->getKind();
                if (kind != Edge::Kind_Dispatch) {
                    Node *succBlock = outEdge->getTargetNode();
                    newDom = dominators.getDominatorNode(succBlock);
                    break;
                }
            }        
            if (newDom) {
                earliest[i] = newDom;
            }
        }

    } else {
        // not pinned, figure out earliest placement
        DominatorNode *currentEarliest = dominators.getDominatorRoot();
        DominatorNode *srcInstEarliest = NULL;
        U_32 numSrcs = i->getNumSrcOperands();
        for (U_32 srcNum=0; srcNum < numSrcs; ++srcNum) {
            Opnd *srcOpnd = i->getSrc(srcNum);
            Inst *srcInst = srcOpnd->getInst();
            scheduleEarly(0, srcInst);
            srcInstEarliest = earliest[srcInst];
            // Note that both currentEarliest and srcInstEarliest dominate this instruction.
            // Thus one of them must dominate the other.
            // The dominated one is the earliest place we can put this.
            if (currentEarliest->isAncestorOf(srcInstEarliest)) {
                // must move currentEarliest down to have srcOpnd available
                currentEarliest = srcInstEarliest;
            }
            if (Log::isEnabled() ) {
                Log::out() << " Inst uses ";    srcInst->print(Log::out());
                Log::out() << ", which has early placement in "; FlowGraph::printLabel(Log::out(), srcInstEarliest);
                Log::out() << std::endl;
            }
            // record the use while we're iterating.
            UsesMap::iterator it = uses.find(srcInst);
            UsesSet* theSet = NULL; 
            if (it == uses.end()) {
                theSet = new (mm) UsesSet(mm);
                it = uses.insert(::std::make_pair(srcInst, theSet)).first;
            }
            theSet = it->second;
            theSet->insert(i);
        }
        srcInstEarliest = currentEarliest;  // now is the latest placement of src insts
        // moving above catch inst may cause problems in code emitter
        // check that we do not cross catch boundaries
        // find earliest intermediate basic block,  starting from the block containing i
        DominatorNode *instEarliest = domNode;
        for (currentEarliest = domNode; ; currentEarliest = currentEarliest->getParent()) {
            if(currentEarliest==0){
	    	break;
	    }
	
	    Node *candidateNode = currentEarliest->getNode();
	    
	    if (Log::isEnabled() ) {
                Log::out() << "  trying node "; FlowGraph::printLabel(Log::out(), candidateNode);
            }
            // intermediate basic blocks with catch labels are
            // inappropriate to place instructions in  
            if (candidateNode->isDispatchNode()) {
                if (Log::isEnabled() ) {
                    Log::out() << "  ...  isDispatchNode";      Log::out() << std::endl;
                }
                break;
            }
            LabelInst *first = (LabelInst*)(candidateNode->getFirstInst());
            Inst* next=first->getNextInst();
            if ((next !=NULL) && (next->getOpcode() == Op_Catch)) {
                if (Log::isEnabled() ) {
                    Log::out() << "  ...  getOpcode() == Op_Catch";     Log::out() << std::endl;
                }
                instEarliest=currentEarliest;
                break;
            }
            if (first->isCatchLabel()) {
                if (Log::isEnabled() ) {
                    Log::out() << "  ...  isCatchLabel";        Log::out() << std::endl;
                }
                break;
            }
            if (Log::isEnabled() ) {
                Log::out() << "  ...  OK";      Log::out() << std::endl;
            }
            instEarliest=currentEarliest;
            if (currentEarliest==srcInstEarliest) {
                break;
            }
        } // end for
        earliest[i] = instEarliest;
    }

    if (Log::isEnabled() ) {
        Log::out() << "> Done earliest placement of "; i->print(Log::out());
        Log::out() << " is in block ";  FlowGraph::printLabel(Log::out(), earliest[i]);            
        Log::out() << std::endl;
    }
}

// LATE SCHEDULING

// a domNodeInstWalker, backwards/postorder
class GcmScheduleLateWalker {
    GlobalCodeMotion *thePass;
    Node *block;
    DominatorNode *domNode;
public:
    void startNode(DominatorNode *domNode0) { 
        domNode = domNode0;
        block = domNode->getNode();
        if (Log::isEnabled() ) {
            Log::out() << "Begin late scheduling of block ";
            FlowGraph::print(Log::out(), block);
            Log::out() << std::endl;
        }    
    };
    void applyToInst(Inst *i) { thePass->scheduleLate(domNode, 0, i); };
    void finishNode(DominatorNode *domNode) { 
        Node *block1 = domNode->getNode();
        if( !(block == block1) ) assert(0);;
        if (Log::isEnabled() ) {
            Log::out() << "Done late scheduling of block ";
            FlowGraph::print(Log::out(), block);
            Log::out() << std::endl;
        }    
    };
    GcmScheduleLateWalker(GlobalCodeMotion *thePass0)
        : thePass(thePass0), block(0), domNode(0)
    {
    };
};

void GlobalCodeMotion::scheduleAllLate()
{
    GcmScheduleLateWalker scheduleLateWalker(this);

    // adapt the DomNodeInstWalker to a forwards DomWalker
    typedef DomNodeInst2DomWalker<false, GcmScheduleLateWalker> LateDomInstWalker;
    LateDomInstWalker domInstWalker(scheduleLateWalker);

    DomTreeWalk<false, LateDomInstWalker>(dominators, domInstWalker, mm);
}

// Note that we are visiting instructions in a block in reverse order.
// It is safe to modify anything below the current instruction.
// as long as no using* instruction precedes this instruction in the same block, we
// are safe in recursively placing use.

// basei, if non-0, is the instruction where we are current iterating, and domNode is
// its node.  If i is where we are iterating, then domNode is its node and basei is 0.
void GlobalCodeMotion::scheduleLate(DominatorNode *domNode, Inst *basei, Inst *i)
{
    if (i->isLabel()) return;
    if (alreadyVisited(i)) return;

    if (domNode==NULL) {
        domNode = dominators.getDominatorNode(i->getNode());
    }

    markAsVisited(i);

    if (Log::isEnabled() ) {
        Log::out() << "< Beginning late scheduling of inst ";
        i->print(Log::out());
        Log::out() << std::endl;
    }

    bool pinned = isPinned(i);
    // figure out where to put it, first scheduling users along the way

    // schedule users
    DominatorNode *lca = 0;
    UsesMap::iterator it = uses.find(i);
    UsesSet* users = NULL;

    if (it == uses.end()) {
        users = new (mm) UsesSet(mm);
        it = uses.insert(::std::make_pair(i, users)).first;
    }

    users = it->second;
    UsesSet::iterator uiter = users->begin();
    UsesSet::iterator uend = users->end();

    for ( ; uiter != uend; ++uiter) {
        Inst *useri = *uiter;

        // schedule use
        scheduleLate(domNode, basei, useri);

        if (Log::isEnabled() ) {
            Log::out() << "Inst ";  i->print(Log::out());
            Log::out() << " is used by inst ";  useri->print(Log::out());
            Log::out() << " which is in "; FlowGraph::printLabel(Log::out(), latest[useri]);
            Log::out() << std::endl;
        }

        if (pinned) continue;
        DominatorNode *usingBlock = latest[useri];
        lca = leastCommonAncestor(lca, usingBlock);
        while (lca->getNode()->isDispatchNode()) {
            lca = lca->getParent(); // code can't be placed in dispatch nodes
        }
    }

    if (pinned) {
        // if following instruction is not already scheduled,
        // then we are scheduling this pinned instruction as a use of some
        // other instruction.  Before scheduling it, we must schedule any
        // following pinned instruction.
        Inst *nextInst = i->getNextInst();
        while ((nextInst!=NULL) && !alreadyVisited(nextInst)) {
            if (isPinned(nextInst)) {
                if (Log::isEnabled() ) {
                    Log::out() << "Pinned Inst "; i->print(Log::out());
                    Log::out() << " is followed by unscheduled pinned inst ";
                    nextInst->print(Log::out());
                    Log::out() << std::endl;
                }
                scheduleLate(domNode, basei, nextInst);
                // scheduling nextInst should result in scheduling
                // any following pinned inst, so break out of loop.
                break; 
            } else {
                if (Log::isEnabled() ) {
                    Log::out() << "Pinned Inst "; i->print(Log::out());
                    Log::out() << " is followed by unscheduled unpinned inst ";
                    nextInst->print(Log::out());
                    Log::out() << std::endl;
                }
                nextInst = nextInst->getNextInst();
            }
        }
        if (Log::isEnabled() ) {
            Log::out() << "Inst is pinned, left in place: "; i->print(Log::out());
            Log::out() << std::endl;
        }
        latest[i] = dominators.getDominatorNode(i->getNode()); // leave it here.
    } else if (lca == 0) {
        // if LCA==0, then there are no uses; i is dead.
        if (Log::isEnabled() ) {
            Log::out() << "Inst has no uses, left in place: "; i->print(Log::out());
            Log::out() << std::endl;
        }
        latest[i] = dominators.getDominatorNode(i->getNode()); // leave it here.
    } else {
        // now LCA is leastCommonAncestor of all uses
        if (i->isLdVar()) {
            // moving ldVar late is dangerous: can jump over stVar for the same var
            if (domNode->isAncestorOf(lca)) {
                lca=domNode;
            }
        }
        Node* lcaNode = lca->getNode();
        DominatorNode *best = lca;
        Node* bestNode = best->getNode();
        DominatorNode *earliestBlock = earliest[i];
        // code can't be placed in dispatch nodes:
        assert(!earliestBlock->getNode()->isDispatchNode());
        if (Log::isEnabled() ) {
            Log::out() << " LCA is "; FlowGraph::printLabel(Log::out(), lca);
            Log::out() << ", best is "; printLabel(Log::out(), best);
            Log::out() << " earliestBlock is "; printLabel(Log::out(), earliestBlock);
            Log::out() << std::endl;
        }

        while (lca != earliestBlock) {
            lca = lca->getParent(); // go up dom tree
            lcaNode = lca->getNode();
            assert(lca && lcaNode);
            if (lcaNode->isDispatchNode()) {
                continue; // code can't be placed in dispatch nodes
            }
            if (Log::isEnabled() ) {
                Log::out() << " LCA is "; printLabel(Log::out(), lca);                          Log::out() << " with depth " << (int)loopTree->getLoopDepth(lcaNode);
                Log::out() << ", best is ";     printLabel(Log::out(), best);
                Log::out() << " with depth " << (int)loopTree->getLoopDepth(bestNode);
                Log::out() << std::endl;
            }

            if (loopTree->getLoopDepth(lcaNode) < loopTree->getLoopDepth(bestNode)) {
                // find deepest block at shallowest nest
                best = lca;
                bestNode = lcaNode;
                if (Log::isEnabled() ) {
                    Log::out() << " LCA replaces best" << std::endl;
                }
            }
        };

        if (Log::isEnabled() ) {
            Log::out() << " Finally, best is "; printLabel(Log::out(), best);
            Log::out() << std::endl;
        }
        latest[i] = best;
    }

    if (Log::isEnabled() ) {
        Log::out() << " Placing inst "; i->print(Log::out());
        Log::out() << " in block ";     printLabel(Log::out(), latest[i]);            
        Log::out() << std::endl;
    }

    // now, to actually move the instruction:

    // we always move instructions at the start of the block.
    // this looks confusing if we are inserting into the same block
    // we are iterating over: we may see the instruction again, but
    // this is safe since the instruction is already marked as placed.

    // we do this even for pinned instructions; they will be visited in
    // reverse order, so they will be replaced in the block starting at
    // the top, so we are ok.

    Node *node = latest[i]->getNode();
    Inst* headInst = (Inst*)node->getFirstInst();
    assert(headInst->isLabel());

    i->unlink();
    if (i->getOperation().mustEndBlock()) {
        // but an instruction which must be at the end must stay there.
        // this includes branches.
        if (Log::isEnabled()) {
            Log::out() << "> Placing inst before headinst ";
            headInst->print(Log::out());
            Log::out() << std::endl;
        }
        node->appendInst(i);
    } else {
        if (Log::isEnabled()) {
            Log::out() << "> Placing inst after headinst ";
            headInst->print(Log::out());
            Log::out() << std::endl;
        }
        node->prependInst(i);
    }
}

DominatorNode *GlobalCodeMotion::leastCommonAncestor(DominatorNode *a, DominatorNode *b)
{
    if (a == 0) return b;
    assert(b != 0);
    while (a != b) {
        if (dominators.isAncestor(a, b)) {
            b = a;
        } else if (dominators.isAncestor(b, a)) {
            a = b;
        } else {
            a = a->getParent();
            b = b->getParent();
        }
    }
    return a;
}

// a NodeInstWalker, forwards/preorder
class GcmSinkConstantsWalker {
    GlobalCodeMotion *thePass;
    Node *block;
public:
    void startNode(Node *cfgNode0) { 
        block = cfgNode0;
        if (Log::isEnabled()) {
            Log::out() << "Begin sinking constants in block";
            FlowGraph::print(Log::out(), block);
            Log::out() << std::endl;
        }    
    };
    void applyToInst(Inst *i) { thePass->sinkConstants(i); };
    void finishNode(Node *cfgNode0) { 
        if (Log::isEnabled() ) {
            Log::out() << "Done sinking constants in block";
            FlowGraph::print(Log::out(), block);
            Log::out() << std::endl;
        }    
    };
    
    GcmSinkConstantsWalker(GlobalCodeMotion *thePass0)
        : thePass(thePass0), block(0)
    {
    };
};


void GlobalCodeMotion::sinkAllConstants()
{
    GcmSinkConstantsWalker gcmSinkConstantsWalker(this);

    // adapt the NodeInstWalker to a NodeWalker

    typedef NodeInst2NodeWalker<true, GcmSinkConstantsWalker> 
        SinkConstantsNodeWalker;
    SinkConstantsNodeWalker sinkConstantsNodeWalker(gcmSinkConstantsWalker);
    
    // do the walk, postorder
    NodeWalk<SinkConstantsNodeWalker>(fg, sinkConstantsNodeWalker);
}

void GlobalCodeMotion::sinkConstants(Inst *inst)
{
    for (U_32 i = 0; i < inst->getNumSrcOperands(); i++) {
        Opnd *opnd = inst->getSrc(i);
        Inst *opndInst = opnd->getInst();
        if (opndInst->isConst()) {
            ConstInst* cinst = opndInst->asConstInst();
            ConstInst::ConstValue cv = cinst->getValue();
            InstFactory &ifactory = irManager.getInstFactory();
            OpndManager &opndManager = irManager.getOpndManager();
            Opnd *newOp = opndManager.createSsaTmpOpnd(opnd->getType());
            Inst *newInst = ifactory.makeLdConst(newOp, cv);
            newInst->insertBefore(inst);
        }
    }
}

// MISC STUFF

bool GlobalCodeMotion::isPinned(Inst *i)
{
    Opcode opcode = i->getOpcode();
    // be explicit about SSA ops
//  if ((opcode == Op_LdVar) || (opcode == Op_StVar) || (opcode == Op_Phi))
    if ((opcode == Op_StVar) || (opcode == Op_Phi))
        return true;
    if (i->getOperation().isMovable()) {
        return false;
    }
    const OptimizerFlags& optimizerFlags = irManager.getOptimizerFlags(); 
    if (0 && optimizerFlags.cse_final) {
        switch (i->getOpcode()) {
        case Op_TauLdInd: 
            {
                Inst *srcInst = i->getSrc(0)->getInst();
                if ((srcInst->getOpcode() == Op_LdFieldAddr) ||
                    (srcInst->getOpcode() == Op_LdStaticAddr)) {
                    FieldAccessInst *faInst = srcInst->asFieldAccessInst();
                    FieldDesc *fd = faInst->getFieldDesc();
                    if (fd->isInitOnly()) {
                        return false;
                    }
                }
            } 
            break;
        case Op_LdStatic:
            {
                FieldAccessInst *inst = i->asFieldAccessInst();
                assert(inst);
                FieldDesc* fd = inst->getFieldDesc();
                if (fd->isInitOnly())
                    return false;
            }
            break;
        case Op_TauLdField:
            {
                FieldAccessInst *inst = i->asFieldAccessInst();
                assert(inst);
                FieldDesc* fd = inst->getFieldDesc();
                if (fd->isInitOnly())
                    return false;
            }
            break;
        default:
            break;
        };
    }
    return true;
}

void GlobalCodeMotion::markAsVisited(Inst *i)
{
    visited.insert(i);
}

bool GlobalCodeMotion::alreadyVisited(Inst *i)
{
    VisitedSet::const_iterator it = visited.find(i);
    return (it != visited.end());
}

void GlobalCodeMotion::clearVisited()
{
    visited.clear();
}

} //namespace Jitrino