/*
 *  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 Sergey L. Ivashin
 */

#include "Ia32RegAllocCheck.h"
#include "Log.h"
#include "XTimer.h"


namespace Jitrino
{

namespace Ia32
{

using ::std::endl;
using ::std::ostream;


//========================================================================================
// utility routines
//========================================================================================


static ostream& operator << (ostream& os, const Inst& x)
{
    return os << "I#" << x.getId();
}


static ostream& operator << (ostream& os, const Opnd& x)
{
    return os << "O#" << x.getFirstId();
}


static ostream& operator << (ostream& os, RegName x)
{
    return os << getRegNameString(x);
}


//========================================================================================
// class RegAllocCheck
//========================================================================================

bool RegAllocCheck::run (bool checkloc)
{
    static CountTime regAllocCheckTimer("ia32::regAllocCheck");
    AutoTimer tm(regAllocCheckTimer);

    opandcount = irm.getOpndCount();
    errors = 0;
    headprinted = false;

    if (checkloc)
        checkLocations();

    const Nodes& nodes = irm.getFlowGraph()->getNodes();
    for (Nodes::const_iterator it = nodes.begin(), end = nodes.end(); it!=end; ++it) {
        Node* node = *it;
        if (node->isBlockNode())
        {
            bblock = node;
            checkLiveness();
            checkConstraints();
        }
    }

    if (errors != 0)
        header() << endl << "ERRORS DETECTED: " << errors << endl;   
    else if (Log::isEnabled())
        header() << endl << "No errors detected" << endl;    

    return errors == 0;
}                                                                               


const size_t MaxRegs = IRMaxRegNamesSameKind*IRMaxRegKinds;


static RegName regName (int x)
{
    U_32 k = x / IRMaxRegNamesSameKind;
    return getRegName((OpndKind)k, Constraint::getDefaultSize(k), x % IRMaxRegNamesSameKind);
}


static size_t regIdx (const Opnd* opnd)
{
    RegName rn;
    if ((rn = opnd->getRegName()) == RegName_Null)
        return MaxRegs;

    size_t x = getRegIndex(rn),
           k = getRegKind(rn); 

    assert(x < IRMaxRegNamesSameKind && k < IRMaxRegKinds); 

    return k*IRMaxRegNamesSameKind + x;
}


void RegAllocCheck::checkLiveness ()
{
    lastbb = 0;

    BitSet lives(mm, (U_32)opandcount);
    irm.getLiveAtExit(bblock, lives);

    Opnd* regdefs[MaxRegs],
        * reguses[MaxRegs],
        * regnxts[MaxRegs];

    size_t ridx;

    for (ridx = 0; ridx != MaxRegs; ++ridx)
        regdefs[ridx] = 0,
        reguses[ridx] = 0,
        regnxts[ridx] = 0;

    Opnd* opnd;
    BitSet::IterB ls(lives);
    for (int i = ls.getNext(); i != -1; i = ls.getNext())
    {
        opnd = irm.getOpnd(i);
        if ((ridx = regIdx(opnd)) < MaxRegs)
        {
            if (regnxts[ridx] == 0)
                regnxts[ridx] = opnd;
            else
                if (regnxts[ridx] != opnd)
                {
                    error() << "at end of block," << regName((int)ridx) 
                            << " assigned to " << *regnxts[ridx] << " and " << *opnd << endl;
                }
        }
    }

//  iterate over instructions towards the top of the block

    for (Inst* inst = (Inst*)bblock->getLastInst(); inst != 0; inst = inst->getPrevInst())
    {
        const U_32 props = inst->getProperties();

    //  In general, operands can be stored in arbitrary order
        Inst::Opnds opnds(inst, Inst::OpndRole_All);
        for (Inst::Opnds::iterator it = opnds.begin(); it != opnds.end(); it = opnds.next(it)){
            opnd = opnds.getOpnd(it);
            if ((ridx = regIdx(opnd)) < MaxRegs)
            {
                const U_32 roles = inst->getOpndRoles(it);

                if ((roles & Inst::OpndRole_Def) != 0)
                {
                    if (regdefs[ridx] == 0)
                        regdefs[ridx] = opnd;
                    else
                        if (regdefs[ridx] != opnd)
                        {
                            error() << "  Invalid definitions at " << *inst << " " << regName((int)ridx) 
                                    << " of " << *regdefs[ridx] << " or " << *opnd << endl;
                        }
                }

                if ((roles & Inst::OpndRole_Use) != 0)
                {
                    if (reguses[ridx] == 0)
                        reguses[ridx] = opnd;
                    else
                        if (reguses[ridx] != opnd)
                        {
                            error() << "  Invalid usages at " << *inst << " " << regName((int)ridx) 
                                    << " of " << *reguses[ridx] << " or " << *opnd << endl;
                        }
                }
            }
        }
        for (ridx = 0; ridx != MaxRegs; ++ridx)
        {
            if (regdefs[ridx] != 0)
            {
                //  conditional definitions are ignored
                if ((props & Inst::Properties_Conditional) == 0)
                {
                    if (regdefs[ridx] != regnxts[ridx]) {
                        if (regnxts[ridx] != 0)
                        {
                            error() << "  " << *inst << " " << regName((int)ridx) 
                                    << " invalid usage of " << *regnxts[ridx]
                                    << " instead of " << *regdefs[ridx] << endl;
                        }
                        else
                        {
                            //  dead def
                        }
                    }
                    regnxts[ridx] = 0;  // this register can used in the instruction
                }
            }

            else if (reguses[ridx] != 0)
            {
                if (reguses[ridx] != regnxts[ridx] && regnxts[ridx] != 0)
                {
                    error() << "  " << *inst << " " << regName((int)ridx) 
                            << " invalid usage of " << *reguses[ridx]
                            << " or " << *regnxts[ridx] << endl;
                }

                regnxts[ridx] = reguses[ridx];
            }

        // clear for next instruction to be processed
            regdefs[ridx] = 0;
            reguses[ridx] = 0;
        }
    }
}


void RegAllocCheck::checkLocations ()
{
    for (size_t i = 0; i != opandcount; ++i)
    {
        Opnd* opnd = irm.getOpnd((U_32)i);
        if (!opnd->hasAssignedPhysicalLocation())
        {
            header() << "Not assigned opand " << *opnd << endl;
            errors++;
        }
    }
}


void RegAllocCheck::checkConstraints ()
{
    lastbb = 0;
    for (const Inst* inst = (Inst*)bblock->getFirstInst(); inst != 0; inst = inst->getNextInst())
    {
        Opnd* opnd;
        Inst::Opnds opnds(inst, Inst::OpndRole_AllDefs);
        U_32 mask = 0;
        for (Inst::Opnds::iterator it = opnds.begin(); it != opnds.end(); it = opnds.next(it))
        {
            opnd = opnds.getOpnd(it);
            Constraint cloc = opnd->getConstraint(Opnd::ConstraintKind_Location);
            mask |= 1<<it;
            Constraint c = ((Inst *)inst)->getConstraint(it, mask, cloc.getSize());    
            if (!cloc.isNull())
                if (c.getSize() == cloc.getSize() && !c.contains(cloc))
                    error() << "Constraint error " << *inst << " " << *opnd << endl;
        }
    }
}


ostream& RegAllocCheck::error ()
{
    if (lastbb != bblock)
    {
        lastbb = bblock;
        header() << "BasicBlock " << bblock->getId() 
                 << "[" << ((Inst*)bblock->getFirstInst())->getId() << " .. " 
                 << ((Inst*)bblock->getLastInst())->getId() << "]" 
                 << endl ;
    }
    errors++;
    return Log::out();
}


ostream& RegAllocCheck::header ()
{
    if (!headprinted)
    {
        headprinted = true;

        MethodDesc& md=irm.getMethodDesc();
        Log::out() << endl << "RegAllocCheck for " 
                   << md.getParentType()->getName() 
                   << "." << md.getName() << "(" << md.getSignatureString() << ")"
                   << endl;  
    }
    return Log::out();
}


} //namespace Ia32
} //namespace Jitrino