regalloc.c

开放源码的编译器open watcom 1.6.0版的源代码

/***********************************************
    Turn off the usage attributes for each temporary, and null the
    conflict field.  This is called in preparation for calling
    MakeConflicts.  "off" is an extra bit will get turned off.  Generate
    will call NullConflicts( USE_IN_ANOTHER_BLOCK ) since it will call
    SearchDefUse to calculate this bit accurately.  USE_IN_ANOTHER_BLOCK
    bit is initially turned on for all front end symbols since we don't
    know how it is going to be used.
*/

    name        *temp;

    temp = Names[ N_TEMP ];
    while( temp != NULL ) {
        temp->v.conflict = NULL;
        temp->v.usage &=(USE_IN_ANOTHER_BLOCK+USE_MEMORY+USE_ADDRESS
                        +VAR_VOLATILE+NEEDS_MEMORY+HAS_MEMORY);
        if( ( temp->v.usage & (USE_MEMORY+USE_ADDRESS+VAR_VOLATILE+NEEDS_MEMORY) )
            == EMPTY ) {
            temp->v.usage &= ~off;
        }
        temp->v.block_usage = EMPTY;
        temp = temp->n.next_name;
    }
}


static  bool  FixInstructions( conflict_node *conf, reg_tree *tree,
                               hw_reg_set reg, bool need_live_update ) {
/***********************************************************************
    Run the the instruction list assigning register "reg" to conflict
    "conf" whose tree is "tree".  "need_live_info_update" will be set to
    false if the caller of this function is going to update the live
    information itself.
*/

    name                *reg_name;
#include "savcache.h"

    reg_name = AllocRegName( reg );
    if( ( conf->name->v.usage & USE_IN_ANOTHER_BLOCK )
     && ( conf->name->v.usage & ( NEEDS_MEMORY | USE_ADDRESS ) ) ) {
        conf->name->v.usage |= USE_MEMORY;
    }
    opnd = tree->temp;
    if( _IsModel( DBG_LOCALS ) ) {
        DBAllocReg( reg_name, opnd );
    }

#define _InRegAssgn
#include "savcode.h"

    if( _LBitEmpty( conf->id.within_block )
     && _GBitEmpty( conf->id.out_of_block ) ) {
        /* update live info since the conflict had no id.*/
        if( need_live_update ) {
            LiveInfoUpdate();
            return( FALSE );
        } else {
            return( TRUE );
        }
    }
    return( FALSE );
}


static  bool    Idx( name *op ) {
/********************************
    Return TRUE if "op" is a name that has been used as the index field
    of an N_INDEXED (eg: 5[t1])
*/

    if( op == NULL ) return( FALSE );
    if( op->n.class != N_TEMP ) return( FALSE );
    if( ( op->t.temp_flags & INDEXED ) == EMPTY ) return( FALSE );
    return( TRUE );
}


static  void    BitOff( conflict_node *conf ) {
/**********************************************
    Run through the instruction turning the bits for conflict "conf" off
    in the live information.  (Done after it's been given a register or
    stuffed in memory).
*/


    block       *blk;
    instruction *ins;

    blk = conf->start_block;
    ins = conf->ins_range.first;
    if( blk != NULL ) {
        for(;;) {
            if( ins == conf->ins_range.last ) break;
            if( ins->head.opcode == OP_BLOCK ) {
                blk = blk->next_block;
                ins = (instruction *)&blk->ins;
            }
            ins = ins->head.next;
            _GBitTurnOff( ins->head.live.out_of_block, conf->id.out_of_block );
            _LBitTurnOff( ins->head.live.within_block, conf->id.within_block );
        }
    }
}


static  signed_32     CountRegMoves( conflict_node *conf,
                               hw_reg_set reg, reg_tree *tree,
                               int levels ) {
/********************************************
    For a conflict "conf", whose tree is "tree", count the number of
    instructions of the form (1) "MOV Rn => Rn" or (2) "OP Rn,x => Rn"
    that assigning register "reg" to the conflict would create.  These
    are good things to create since the go away (1) or are easy to
    generate in one machine instruction (2).
*/

    block               *blk;
    instruction         *ins;
    signed_32           count;
    int                 half;
    name                *reg_name;
    name                *op1;
#if _TARGET & (_TARG_80386|_TARG_IAPX86|_TARG_370)
    name                *op2;
#endif
    name                *res;
    bool                idx;
    conflict_node       *other_conf;
    name                *other_opnd;

    levels = levels;
    if( tree == NULL ) return( 0 );
    reg_name = AllocRegName( reg );
    count = 0;
    blk = conf->start_block;
    ins = conf->ins_range.first;
    if( tree->temp != NULL ) {
        idx = IsIndexReg( reg, tree->temp->n.name_class, FALSE );
    } else {
        idx = FALSE;
    }
    half = tree->size / 2;
    for(;;) {
        if( ins->head.opcode == OP_BLOCK ) {
            blk = blk->next_block;
            ins = blk->ins.hd.next;
        } else {
            if( ins->head.opcode != OP_MOV ) {
/* 88-Dec-23*/
            #if _TARGET & (_TARG_80386|_TARG_IAPX86|_TARG_370)
                op1 = NULL;
                op2 = NULL;
                if( ins->num_operands != 0 ) {
                    op1 = ins->operands[ 0 ];
                    switch( ins->head.opcode ) {
                    case OP_ADD:
                    case OP_EXT_ADD:
                    case OP_MUL:
                    case OP_AND:
                    case OP_OR:
                    case OP_XOR:
                        op2 = ins->operands[ 1 ];
                        break;
                    }
                }
                res = ins->result;
                if( res == reg_name ) {
                    if( op1 == tree->temp || op1 == tree->alt
                      || op2 == tree->temp || op2 == tree->alt ) {
                        count += half;
                    }
                } else if( res == tree->temp || res == tree->alt ) {
                   if( op1 == reg_name || op2 == reg_name ) {
                        count += half;
                   }
                }
/* 88-Dec-23*/
            #endif
            } else {
                op1 = ins->operands[ 0 ];
                res = ins->result;
                if( ( ( op1 == tree->temp || op1 == tree->alt )
                     && ( res == reg_name || ( idx && Idx( res ) ) ) )
                 || ( ( res == tree->temp || res == tree->alt )
                     && ( op1 == reg_name || ( idx && Idx( op1 ) ) ) ) ) {
                    count += tree->size;
                } else if( ( res->n.class == N_REGISTER )
                        && HW_Ovlap( reg, res->r.reg ) ) {
                    /*
                       if we're moving into an overlapping register, give
                       it half a move waiting. E.g.:
                         MOV U2 [DI] ==> t1
                         MOV U1 t1   ==> CL
                    */
                    count += half;
                }
            }
            if( ins == conf->ins_range.last ) break;
            ins = ins->head.next;
        }
    }
#if ( _TARGET & _TARG_370 )
    if( 1 ) {
#else
    if( _IsModel( SUPER_OPTIMAL ) ) {
#endif
        count += CountRegMoves( conf, HighOffsetReg( reg ), tree->hi, levels );
        count += CountRegMoves( conf, LowOffsetReg( reg ), tree->lo, levels );
    }
    if( _IsModel( SUPER_OPTIMAL ) ) {
        /*
         * This is really expensive, compile time-wise, but what it does is
         * checks to see if we have an intervening temp or two that may turn
         * into register register moves, as in
         * MOV Rn => T1
         * MOV T1 => T2
         * MOV T2 => Rn
         * which will save us something in the case that T1 or T2 get assigned
         * to Rn
         */

        hw_reg_set      saved_regs;

        saved_regs = MustSaveRegs();
        if( !HW_Ovlap( saved_regs, reg ) ) count += 2;
        count <<= levels;
        if( count != 0 || levels == 0 ) return( count );
        blk = HeadBlock;
        while( blk != NULL ) {
            ins = blk->ins.hd.next;
            for( ins = blk->ins.hd.next; ins->head.opcode != OP_BLOCK; ins = ins->head.next ) {
                if( ins->head.opcode == OP_MOV ) {
                    other_opnd = NULL;
                    if( ins->result == conf->name ) {
                        other_opnd = ins->operands[ 0 ];
                    } else if( ins->operands[ 0 ] == conf->name ) {
                        other_opnd = ins->result;
                    }
                    if( other_opnd == NULL ) continue;
                    switch( other_opnd->n.class ) {
                    case N_MEMORY:
                    case N_INDEXED:
                    case N_CONSTANT:
                        break;
                    default:
                        other_conf = FindConflictNode( other_opnd, blk, ins );
                        if( other_conf != NULL ) {
                            reg_name = tree->temp;
                            tree->temp = other_conf->name;
                            count = CountRegMoves( other_conf, reg, tree, levels-1 );
                            tree->temp = reg_name;
                            return( count );
                        }
                    }
                }
            }
            blk = blk->next_block;
        }
        return( 0 );
    }
    return( count );
}


static  bool    UnaryOpGetsReg( instruction *ins, hw_reg_set reg,
                                name *op ) {
/******************************************************************************
    return true if this is a unary operator and we can generate code
    given that the result or operand gets a register (a little machine specific
    but I don't know of any machines for which this isn't true).
*/
     return( NumOperands( ins ) == 1 && ins->result != NULL &&
            !IsSegReg( reg ) && ins->head.opcode != OP_CONVERT &&
            ( ins->operands[0] == op || ins->result == op ) );
}


static  bool    StealsSeg( instruction *ins,
                           hw_reg_set reg, hw_reg_set except,
                           name *actual_op ) {
/***************************************************************
    Does giving "reg" to "conf" steal the last segment away from "ins"?
*/

    hw_reg_set          *index_needs;
    name                *op;
    conflict_node       *new_conf;
    int                 i;

    i = ins->num_operands;
    --i;
    if( i < NumOperands( ins ) ) return( FALSE );
    op = ins->operands[ i ];
    new_conf = NameConflict( ins, op );
    if( new_conf == NULL ) return( FALSE );
    if( ( op == actual_op ) && IsSegReg( reg ) ) return( FALSE );
    index_needs = RegSets[  SegIndex()  ];
    if( HW_CEqual( *index_needs, HW_EMPTY ) ) return( FALSE );
    for(;;) {
        if( !HW_Ovlap( *index_needs, except ) ) return( FALSE );
        ++index_needs;
        if( HW_CEqual( *index_needs, HW_EMPTY ) ) break;
    }
    return( TRUE );
}


static  bool    StealsIdx( instruction *ins,
                           hw_reg_set except, name *actual_op ) {
/****************************************************************
    Does precluding the set of regiseters "except" from operands of
    "ins" make it impossible to generate an indexed addressing mode?
*/

    hw_reg_set          *index_needs;
    name                *op;
    conflict_node       *new_conf;
    int                 i;
    bool                is_result;

    i = ins->num_operands;
    is_result = FALSE;
    while( --i >= 0 ) {
        op = ins->operands[ i ];
        if( op->n.class == N_INDEXED ) {
            new_conf = NameConflict( ins, op->i.index ); // oops
            if( new_conf == NULL || actual_op == op->i.index ) return( FALSE );
        }
    }
    if( ins->result != NULL ) {
        op = ins->result;
        if( op->n.class == N_INDEXED ) {
            new_conf = NameConflict( ins, op->i.index ); // oops
            if( new_conf == NULL || actual_op == op->i.index ) return( FALSE );
            is_result = TRUE;
        }
    }
    index_needs = RegSets[  ins->t.index_needs  ];
    if( HW_CEqual( *index_needs, HW_EMPTY ) ) return( FALSE );
    for(;;) {
        if( !HW_Ovlap( *index_needs, except ) ) {
            if( !is_result ) return( FALSE );
            if( !HW_Ovlap( *index_needs, ins->zap->reg ) ) return( FALSE );
        }
        ++index_needs;
        if( HW_CEqual( *index_needs, HW_EMPTY ) ) break;