/****************************************************************************
*
*                            Open Watcom Project
*
*    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
*
*  ========================================================================
*
*    This file contains Original Code and/or Modifications of Original
*    Code as defined in and that are subject to the Sybase Open Watcom
*    Public License version 1.0 (the 'License'). You may not use this file
*    except in compliance with the License. BY USING THIS FILE YOU AGREE TO
*    ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
*    provided with the Original Code and Modifications, and is also
*    available at www.sybase.com/developer/opensource.
*
*    The Original Code and all software distributed under the License are
*    distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
*    EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
*    ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
*    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
*    NON-INFRINGEMENT. Please see the License for the specific language
*    governing rights and limitations under the License.
*
*  ========================================================================
*
* Description:  Register allocator.
*
****************************************************************************/


#include "standard.h"
#include "coderep.h"
#include "opcodes.h"
#include "conflict.h"
#include "regset.h"
#include "pattern.h"
#include "procdef.h"
#include "hostsys.h"
#include "zoiks.h"
#include "model.h"

enum allocation_state {
    ALLOC_DONE,
    ALLOC_BITS,
    ALLOC_CONST_TEMP
};

extern  bool            SideEffect(instruction*);
extern  void            NowDead(name*,conflict_node*,name_set*,block*);
extern  void            PrefixIns(instruction*,instruction*);
extern  void            BurnRegTree(reg_tree*);
extern  void            IMBlip(void);
extern  conflict_node   *NameConflict(instruction*,name*);
extern  void            BuildNameTree(conflict_node*);
extern  void            AxeDeadCode(void);
extern  void            BurnNameTree(reg_tree*);
extern  bool            WorthProlog(conflict_node*,hw_reg_set);
extern  instruction     *MakeMove(name*,name*,type_class_def);
extern  void            DoNothing(instruction*);
extern  int             ExpandOps(bool);
extern  void            FindReferences(void);
extern  void            NowAlive(name*,conflict_node*,name_set*,block*);
extern  name            *DeAlias(name*);
extern  void            BuildRegTree(conflict_node*);
extern  void            FreeAConflict(conflict_node*);
extern  bool            IsIndexReg(hw_reg_set,type_class_def,bool);
extern  void            LiveInfoUpdate(void);
extern  void            MakeLiveInfo(void);
extern  void            FreeConflicts(void);
extern  reg_set_index   SegIndex(void);
extern  void            DelSegOp(instruction*,int);
extern  void            FixChoices(void);
extern  void            DelSegRes(instruction*);
extern  void            MakeConflicts(void);
extern  void            AddSegment(instruction*);
extern  void            SuffixIns(instruction*,instruction*);
extern  name            *ScaleIndex(name*,name*,type_length,type_class_def,type_length,int,i_flags);
extern  void            FixGenEntry(instruction*);
extern  int             NumOperands(instruction*);
extern  void            CalcSavings(conflict_node*);
extern  hw_reg_set      LowOffsetReg(hw_reg_set);
extern  name            *AllocRegName(hw_reg_set);
extern  bool            PropagateMoves(void);
extern  bool            PropRegsOne(void);
extern  conflict_node   *FindConflictNode(name*,block*,instruction*);
extern  hw_reg_set      HighOffsetReg(hw_reg_set);
extern  void            DeadInstructions(void);
extern  void            GRBlip(void);
extern  bool            IsSegReg(hw_reg_set);
extern  void            *SortList(void *,unsigned,bool (*)(void*,void*) );
extern  bool            MoreConflicts(void);
extern  void            DBAllocReg(name*,name*);
extern  void            MemConstTemp(conflict_node*);
extern  void            ConstSavings(void);
extern  void            RegInsDead(void);
extern  instruction     *FoldIns( instruction * );
extern  bool            IsUncacheableMemory( name * );
extern  hw_reg_set      MustSaveRegs(void);

extern  proc_def         *CurrProc;
extern  conflict_node    *ConfList;
extern  op_regs          RegList[];
extern  hw_reg_set       *RegSets[];
extern  hw_reg_set       GivenRegisters;
extern  name             *Names[];
extern  bool             BlockByBlock;
extern  bool             HaveLiveInfo;
extern  block           *HeadBlock;




static  bool    ContainedIn( name *name1, name *name2 ) {
/********************************************************
    Returns true if name1 is completely contained within the location
    occupied by name2
*/

    if( name1->n.class != name2->n.class ) return( FALSE );
    if( name1->n.class == N_TEMP ) {
        if( DeAlias( name1 ) != DeAlias( name2 ) ) return( FALSE );
    } else if( name1->n.class == N_MEMORY ) {
        if( name1 != name2 ) return( FALSE );
    } else {
        return( FALSE );
    }
    if( name1->v.offset < name2->v.offset ) return( FALSE );
    if( name1->v.offset + name1->n.size > name2->v.offset + name2->n.size )
        return( FALSE );
    return( TRUE );
}


static  hw_reg_set      SearchTree( reg_tree *tree,
                                    name *opnd, hw_reg_set reg ) {
/*****************************************************************
    Given a register "reg", and a reg_tree "tree", return the
    appropriate piece of "reg" to be associated with name "opnd".
*/

    if( tree->offset == opnd->v.offset && tree->size == opnd->n.size ) {
        return( reg );
    }
    if( opnd->v.offset < tree->offset + ( tree->size / 2 ) ) {
        return( SearchTree( tree->lo, opnd, LowOffsetReg( reg ) ) );
    } else {
        return( SearchTree( tree->hi, opnd, HighOffsetReg( reg ) ) );
    }
}


static  name    *FindReg( reg_tree *tree, name *opnd, name *reg ) {
/******************************************************************
    see SearchTree
*/

    return( AllocRegName( SearchTree( tree, opnd, reg->r.reg ) ) );
}


static  name    *ReplIndex( instruction *ins,
                            reg_tree *tree, name *x, name *reg ) {
/*****************************************************************
    Replace the index field of "x" with register "reg" in instruction "ins".
*/

    name        *new_x;

    ins->t.index_needs = RL_;
    reg = FindReg( tree, x->i.index, reg );
    new_x = ScaleIndex(reg, x->i.base, x->i.constant,
                        x->n.name_class, x->n.size, x->i.scale,
                        x->i.index_flags );
    return( new_x );
}


static  void    AssignMoreBits( void )
/*************************************
    Run through the list of conflicts and turn off the CONFLICT_ON_HOLD
    bit.  This is on for conflicts that needed an id bit but didn't get
    one.  MoreConflicts will assign a bit to any of these that weren't
    allocated the first time around.
*/
{
    conflict_node       *conf;

    conf = ConfList;
    while( conf != NULL ) {
        conf->state &= ~CONFLICT_ON_HOLD;
        conf = conf->next_conflict;
    }
    if( MoreConflicts() ) {
        MakeLiveInfo();
        AxeDeadCode();
    } else {
        LiveInfoUpdate();
    }
}


static  void    InitAChoice( name *temp ) {
/*****************************************/

    name        *alias;

    if( temp->n.class != N_TEMP ) return;
    if( temp->t.temp_flags & ALIAS ) return;
    alias = temp;
    do {
        alias->t.possible = RL_NUMBER_OF_SETS;
        alias = alias->t.alias;
    } while( alias != temp );
}


static  void    InitChoices( void )
/**********************************
    Set the possible register choices of all conflicts/temps to be
    RL_NUMBER_OF_SETS meaning there are no restrictions as yet.  This
    choice gets more restricted as each instruction involving the
    conflict is expanded.
*/
{
    conflict_node       *conf;
    name                *opnd;
    block               *blk;
    instruction         *ins;
    int                 i;

    conf = ConfList;
    while( conf != NULL ) {
        conf->possible = RL_NUMBER_OF_SETS;
        conf = conf->next_conflict;
    }
    if( BlockByBlock ) {
        /* this is WAY faster for BlockByBlock */
        blk = HeadBlock;
        while( blk != NULL ) {
            ins = blk->ins.hd.next;
            while( ins->head.opcode != OP_BLOCK ) {
                i = ins->num_operands;
                while( --i >= 0 ) {
                    InitAChoice( ins->operands[i] );
                }
                if( ins->result != NULL ) {
                    InitAChoice( ins->result );
                }
                ins = ins->head.next;
            }
            blk = blk->next_block;
        }
    } else {
        opnd = Names[ N_TEMP ];
        while( opnd != NULL ) {
            opnd->t.possible = RL_NUMBER_OF_SETS;
            opnd = opnd->n.next_name;
        }
    }
}


static  void    ReAlias( reg_tree *tree ) {
/******************************************
    Given a name tree, turn all temporaries into MASTER (not ALIAS)
    temporaries if their ancestor in the tree has no restrictions on
    which register it can have.  This effectively detaches the hi and lo
    part of a temporary so they may be treated separately during
    register allocation.
*/

    name        *curr;
    name        *new_ring;
    name        **owner;
    type_length endpoint;
    type_length begpoint;

    if( tree != NULL ) {
        if( tree->idx == RL_NUMBER_OF_SETS ) {
            ReAlias( tree->lo );
            ReAlias( tree->hi );
        } else {
            begpoint = tree->offset;
            endpoint = tree->size + begpoint;
            owner = &tree->temp->t.alias;
            new_ring = NULL;
            for(;;) {
                curr = *owner;
                if( curr->v.offset < begpoint
                 || curr->v.offset + curr->n.size > endpoint ) {
                    owner = &curr->t.alias;
                } else {
                    *owner = curr->t.alias;
                    if( new_ring == NULL ) {
                        new_ring = curr;
                        new_ring->t.alias = new_ring;
                    } else {
                        curr->t.alias = new_ring->t.alias;
                        new_ring->t.alias = curr;
                    }
                }
                if( curr == tree->temp ) break;
            }
            curr->t.temp_flags &= ~ALIAS;
        }
    }
}


static  bool    SplitConflicts( void )
/*************************************
    Build a name tree for each conflict, and then if the top of the tree
    has no restrictions on which registers it can have, its name mustn't
    be referenced by any instructions, so we call ReAlias to split make
    the high and low part their own "MASTER" rather than aliases of the
    temporary for the top of the tree.  See REGTREE.C for info re: name
    trees.

*/
{
    conflict_node       *conf;
    bool                change;

    change = FALSE;
    conf = ConfList;
    while( conf != NULL ) {
        BuildNameTree( conf );
        if( conf->tree != NULL
         && conf->tree->idx == RL_NUMBER_OF_SETS ) {
            change = TRUE;
            ReAlias( conf->tree );
            if( conf->tree->temp != NULL ) {
                conf->tree->temp->v.usage |= USE_MEMORY;
            }
            if( conf->tree->alt != NULL ) {
                conf->tree->alt->v.usage |= USE_MEMORY;
            }
        }
        BurnNameTree( conf->tree );
        conf->tree = NULL;
        conf = conf->next_conflict;
    }
    return( change );
}


extern  void    NullConflicts( var_usage off ) {