/*
 *  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 "globalopndanalyzer.h"
#include "irmanager.h"
#include "Dominator.h"
#include "Inst.h"
#include "Loop.h"
#include "BitSet.h"
#include "Log.h"
#include "optpass.h"

namespace Jitrino {

DEFINE_SESSION_ACTION(GlobalOperandAnalysisPass, markglobals, "Basic Block based Global Operand Analysis")

void
GlobalOperandAnalysisPass::_run(IRManager& irm) {
    OptPass::computeDominators(irm);
    OptPass::computeLoops(irm);
    AdvancedGlobalOpndAnalyzer globalOpndAnalyzer(irm, *irm.getLoopTree());
    globalOpndAnalyzer.doAnalysis();
}

//
//  Reset global bits 
//
void
GlobalOpndAnalyzer::resetGlobalBits() {
    Nodes::iterator niter;
    for (niter = nodes.begin(); niter != nodes.end(); ++niter) {
        Node* node = *niter;
        Inst *headInst = (Inst*)node->getFirstInst();
        for (Inst* inst = headInst->getNextInst();inst!=NULL;inst=inst->getNextInst()) {
            //
            // SsaVarOpnds and VarOpnds are always global; we care only about
            // SsaTmpOpnds.
            //
            Opnd* dst = inst->getDst();
            if (dst->isSsaVarOpnd() || dst->isVarOpnd()) {
                dst->setIsGlobal(true);
                continue;
            }
            dst->setIsGlobal(false);
        }
    }
}

//
//  Mark temporaries whose live range spans basic block boundary as globals
//
void 
GlobalOpndAnalyzer::markGlobals() {
    //
    // Now walk instructions in postorder, marking sources that have not been
    // visited as global.
    //
    U_32 numInsts = irManager.getInstFactory().getNumInsts();
    MemoryManager memManager("GlobalOpndAnalyzer::doAnalysis()");
    BitSet markedInstSet(memManager,numInsts);
    Nodes::iterator niter;
    for (niter = nodes.begin(); niter != nodes.end(); ++niter) {
        Node* node = *niter;
        Inst* headInst = (Inst*)node->getFirstInst();
        for (Inst* inst = headInst->getNextInst();inst!=NULL;inst=inst->getNextInst()) {
            // mark as visited
            markedInstSet.setBit(inst->getId(),true);
            // check sources to see if any span globally
            for (U_32 i=0; i<inst->getNumSrcOperands(); i++) {
                Opnd* src = inst->getSrc(i);
                //
                // we care only about srcs that are temporary
                //
                if (src->isSsaTmpOpnd() == false)
                    continue;
                //
                // if the instruction defining this source has not been marked,
                // then the opnd must be global because of the post order walk
                //
                if (markedInstSet.getBit(src->getInst()->getId()) == false) {
                    src->setIsGlobal(true);
                    if(Log::isEnabled())  {
                        Log::out() << "XXX - GlobalOpnd:";src->getInst()->print(Log::out()); Log::out() << ::std::endl;
                    }
                }
            }
        }
    }
}

void
GlobalOpndAnalyzer::doAnalysis() {
    nodes.reserve(flowGraph.getNodeCount());
    flowGraph.getNodesPostOrder(nodes);
    resetGlobalBits();
    // mark temporaries whose live spans basic block boundary as globals
    markGlobals();   
}


//
//  Information about a global operand
//
struct AdvancedGlobalOpndAnalyzer::OpndInfo {
    OpndInfo(U_32 h, U_32 ts) : header(h), timeStamp(ts), isGlobal(false) {
    }
    U_32    header;       // dfNum of a header where node is used.
    U_32    timeStamp;
    bool      isGlobal;
};

//
//  Hash table with the global operand information
//
class AdvancedGlobalOpndAnalyzer::OpndTable : public HashTable<Opnd,OpndInfo> {
public:
    OpndTable(MemoryManager& mm, U_32 size) : 
        HashTable<Opnd,OpndInfo>(mm,size), memManager(mm), lastHeaderTimeStamp(0) {
    }
    void clear() {
        lastHeaderTimeStamp = 0;
        removeAll();
    }
    void recordUse(Opnd * use, U_32 loopHeader, U_32 timeStamp) {
        OpndInfo * info = lookup(use);
        if (info == NULL)
            insertOpnd(use, loopHeader, timeStamp);
        else {
            //
            //  If previous use had different loop header, temp is global
            //
            if (info->header != loopHeader)
                info->isGlobal = true;
        }
    }
    void recordDef(Opnd * def, U_32 loopHeader, U_32 timeStamp) {
        OpndInfo * info = lookup(def);
        //
        //  Operand may be not in the table if it's definition is inside
        //  the loop and use is outside the loop, or if it's dead. 
        //  Insert it into a table
        //
        if (info == NULL) 
            insertOpnd(def,loopHeader,timeStamp);
        else {
            //
            //  If loop header of the definition is not equal loop header of
            //  the use, operand is global
            //
            if (info->header != loopHeader)
                info->isGlobal = true;
            //
            //  If we saw a loop header between use and definition operand 
            //  may be global.
            //
            else if (info->timeStamp < lastHeaderTimeStamp)
                info->isGlobal = true;
        }
    }
    void recordLoopHeader(U_32 timeStamp) {
        lastHeaderTimeStamp = timeStamp;
    }
private:
    virtual bool keyEquals(Opnd* key1,Opnd* key2) const {
        return key1 == key2;
    }
    virtual U_32 getKeyHashCode(Opnd* key) const {
        return key->getId();
    }
    void insertOpnd(Opnd * opnd, U_32  header, U_32 timeStamp) {
        insert(opnd, new(memManager) OpndInfo(header,timeStamp));
    }
    MemoryManager& memManager;
    U_32  lastHeaderTimeStamp;
};
    
void
AdvancedGlobalOpndAnalyzer::markManagedPointerBases() {
    //
    //  Walk nodes in postorder
    //
    Nodes::iterator niter;
    for (niter = nodes.begin(); niter != nodes.end(); ++niter) {
        Node* node = *niter;
        //
        //  Walk instructions in reverse order
        //
        for (Inst* inst = (Inst*)node->getLastInst(); inst!=NULL; inst=inst->getPrevInst()) {       
            Opcode opcode = inst->getOpcode();
            // If the managed pointer generated by an instruction is global, its source 
            // should also be marked as global.  (Though, technically only if the managed
            // pointer is live across a GC safe point.  We don't make this further
            // distinction.)
            switch(opcode) {
            case Op_LdVarAddr:
                break;
            case Op_LdLockAddr:
            case Op_LdFieldAddr: 
            case Op_LdElemAddr:
            case Op_LdArrayBaseAddr:
            case Op_AddScaledIndex:
        {
                Opnd* src = inst->getSrc(0);
                Opnd* dst = inst->getDst();
                if(!src->isGlobal() && dst->isGlobal()) {
                    if (dst->getType()->isManagedPtr()) {
                        src->setIsGlobal(true);
                    } else {
                        assert(dst->getType()->isUnmanagedPtr());
                    }

                }
        };
                break;
        default:
        break;
            }
        }
    }
}
    
void
AdvancedGlobalOpndAnalyzer::unmarkFalseGlobals() {
    MemoryManager localMemManager("RefinedGlobalOpndAnalyzer::doAnalysis.localMemManager");
    opndTable = new (localMemManager) OpndTable(localMemManager, 16);
    U_32 timeStamp = 0;
    //
    //  Walk nodes in postorder
    //
    Nodes::iterator niter;
    for (niter = nodes.begin(); niter != nodes.end(); ++niter) {
        Node* node = *niter;
        timeStamp++;    
        //
        //  Figure out the current loop header
        //
        Node* header = loopInfo.getLoopHeader(node, false);
        U_32 currHeader = header != NULL ? header->getDfNum() : (U_32)-1;
        
        //
        //  Walk instructions in reverse order
        //
        for (Inst* inst = (Inst*)node->getLastInst(); inst!=NULL; inst=inst->getPrevInst()) {
            //
            // Analyze sources 
            //
            for (U_32 i=0; i<inst->getNumSrcOperands(); i++) {
                Opnd* src = inst->getSrc(i);
                //
                // We care only about global tmps
                //
                if (src->isSsaTmpOpnd() == true && src->isGlobal() == true)
                    opndTable->recordUse(src, currHeader,timeStamp);
            }
            //
            //  Analyze destination
            //
            Opnd * dst = inst->getDst();
            //
            //  We care only about global temps
            //
            if (dst->isSsaTmpOpnd() == true && dst->isGlobal() == true) 
                opndTable->recordDef(dst,currHeader, timeStamp);

        }
        //
        //  If this node is a loop header record it in operand table
        //
        if (loopInfo.isLoopHeader(node))
            opndTable->recordLoopHeader(timeStamp);
    }
    //
    //  Mark global operands that we found to be actually local as local
    //
    HashTableIter<Opnd, OpndInfo> tableIter(opndTable);
    Opnd *     opnd;
    OpndInfo * info;
    while (tableIter.getNextElem(opnd,info)) {
        if (info->isGlobal == false) {
            opnd->setIsGlobal(false);
            if(Log::isEnabled())  {
                Log::out() << "XXX - Not a Global Opnd:";
                opnd->print(Log::out()); 
                Log::out() << ::std::endl;
            }
        }
    }
}


void
AdvancedGlobalOpndAnalyzer::markGlobals() {
    //
    //  If CFG does not contain any loops there are no global temporaries
    //
    if (!flowGraph.getLoopTree()->hasLoops())
        return;
    //
    //  Mark temporaries whose live spans basic block as globals
    //
    GlobalOpndAnalyzer::markGlobals();
    //
    //  Unmark global temporaries whose live range does not span loop boundary
    //
    unmarkFalseGlobals();

    //
    //  Mark references that generate global managed pointers as global also. 
    //
    markManagedPointerBases();
}



} //namespace Jitrino