regalloc.c

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

            HW_TurnOn( GivenRegisters, given );
        } else {
            HW_CAsgn( given, HW_EMPTY );
        }
    }
    if( HW_CEqual( given, HW_EMPTY ) && needs_one ) {
        _Zoiks( ZOIKS_040 );
    }
    return( given );
}


extern  bool    AssignARegister( conflict_node *conf, hw_reg_set reg ) {
/***********************************************************************
    Used to assign register "reg" to conflict "conf", before we've
    started the true register allocator.  (used by I87REG.C)
*/

    bool        need_live_update;

    BuildRegTree( conf );
    need_live_update = FixInstructions( conf, conf->tree, reg, FALSE );
    BitOff( conf );
    BurnRegTree( conf->tree );
    FreeAConflict( conf );
    return( need_live_update );
}


static  void    PutInMemory( conflict_node *conf ) {
/***************************************************
    Put "conf" into memory.  Also if the conflict is only used by one
    instruction, its useless, so we zap that instruction to not get
    generated.  We also turn the bit for "conf" off in the live
    information
*/

    block       *blk;
    instruction *ins;
    name        *opnd;

    IMBlip();
    opnd = conf->name;
    if( opnd->n.class == N_TEMP ) {
        if( opnd->t.temp_flags & CONST_TEMP ) {
            MemConstTemp( conf );
        } else {
            for(;;) {
                opnd->v.usage |= NEEDS_MEMORY | USE_MEMORY;
                opnd = opnd->t.alias;
                if( opnd == conf->name ) break;
            }
        }
    } else {
        opnd->v.usage |= NEEDS_MEMORY | USE_MEMORY;
    }
    blk = conf->start_block;
    ins = conf->ins_range.first;
    if( blk != NULL ) {
        for(;;) {
            if( ins->head.opcode != OP_BLOCK &&
                ins->head.state == OPERANDS_NEED_WORK ) {
                ins->head.state = INS_NEEDS_WORK;
            }
            if( ins->id == conf->ins_range.last->id ) break;
            if( ins->head.opcode == OP_BLOCK ) {
                if( blk->next_block == NULL ) {
                    Zoiks( ZOIKS_141 );
                    break;
                }
                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 );
        }
        if( conf->ins_range.first == conf->ins_range.last
         && conf->name->n.class == N_TEMP
         && ( conf->name->v.usage & USE_ADDRESS ) == 0
         && SideEffect( conf->ins_range.first ) == FALSE ) {
            DoNothing( conf->ins_range.first );
        }
    }
}


extern  conflict_node   *InMemory( conflict_node *conf ) {
/*********************************************************
    Put conflict "conf" and all other conflicts associated with the same
    name as "conf" into memory.  Sorry charlie, no register.
    Save conf as last to go so it's next_conf will be valid in case
    a bunch got freed in MemConstTemp
*/

    conflict_node       *next;
    conflict_node       *conf_list;

    conf_list = conf->name->v.conflict;
    while( conf_list != NULL ) {
        if( conf != conf_list ){
            PutInMemory( conf_list );
            next = conf_list->next_for_name;
            FreeAConflict( conf_list );
            conf_list = next;
        }else{
            conf_list = conf_list->next_for_name;
        }
    }
    PutInMemory( conf );
    next = conf->next_conflict;
    FreeAConflict( conf );
    return( next );
}


extern  conflict_node   *GiveRegister( conflict_node *conf, bool needs_one ) {
/*****************************************************************************
    Give a register to conflict "conf", if at all possible.  The
    NEEDS_INDEX and NEEDS_SEGMENT stuff is just saying that if we tried
    to give a register to a conflict that needs to be an index or
    segment register, and failed, we will set NEEDS_INDEX_SPLIT, or
    NEEDS_SEGMENT_SPLIT.  This in turn will cause ExpandOps the next
    time around to turn any reference to this variable into a temporary
    reference, for example:

        ADD     [x],y => Z
            becomes
        MOV     x => temp
        ADD     [temp],y => Z

    thus shifting the NEEDS_INDEX/NEEDS_SEGMENT requiremement onto a
    very short lived temporary, which will be guaranteed to get the
    right type of register (ensured by TooGreedy).
*/

    reg_tree            *tree;
    conflict_node       *next_valid;
    hw_reg_set          given;

    GRBlip();
    BuildRegTree( conf );
    tree = conf->tree;
    if( _Is( conf, ( INDEX_SPLIT | SEGMENT_SPLIT ) ) ) {
        needs_one = TRUE;
    }
    given = GiveBestReg( conf, tree, CurrProc->state.unalterable, needs_one );
    if( tree != NULL && ( tree->hi != NULL || tree->lo != NULL ) ) {
        LiveInfoUpdate(); /* the live info is FAR to conservative. */
    }
    if( !HW_CEqual( given, HW_EMPTY ) ) {
        next_valid = conf->next_conflict;
        BitOff( conf );
        FreeAConflict( conf );
    } else {
        if( _Is( conf, NEEDS_INDEX ) ) {
            _SetTrue( conf, NEEDS_INDEX_SPLIT );
            _SetFalse( conf, NEEDS_INDEX );
        } else if( _Is( conf, NEEDS_SEGMENT ) ) {
            _SetTrue( conf, NEEDS_SEGMENT_SPLIT );
            _SetFalse( conf, NEEDS_SEGMENT );
        }
        if( _Isnt( conf, ( NEEDS_SEGMENT_SPLIT | NEEDS_INDEX_SPLIT ) ) ) {
            next_valid = InMemory( conf );
        } else {
            next_valid = conf->next_conflict;
        }
    }
    BurnRegTree( tree );
    return( next_valid );
}


static  bool            ConfBefore( void *c1, void *c2 ) {
/*********************************************************
    used by SortConflicts
*/

    return( ((conflict_node *)c1)->savings > ((conflict_node *)c2)->savings );
}


static  void    SortConflicts( void )
/************************************
    Sort the conflicts in order of descending savings.
*/
{
    ConfList = SortList( ConfList, offsetof( conflict_node, next_conflict ),
                         ConfBefore );
}


static  enum allocation_state    AssignConflicts( void )
/*******************************************************
    Run through the conflict list and calculate the savings associated
    with giving a register to each one.  Sort the list in order of
    descending savings and then give a register (or memory location) to
    each conflict in the list that is not ON_HOLD.
*/
{
    conflict_node               *conf;
    conflict_node               *next;
    enum allocation_state       state;
    name                        *opnd;
    bool                        only_const_temps;

    conf = ConfList;
    while( conf != NULL ) {
        next = conf->next_conflict;
        if( conf->start_block == NULL ) {
            FreeAConflict( conf );
        } else {
            if( _Isnt( conf, SAVINGS_CALCULATED ) ) {
                conf->available = 1; /* FOR NOW for CalcSavings' benifit */
                CalcSavings( conf );
                if( _Isnt( conf, CONFLICT_ON_HOLD ) ) {
                    _SetTrue( conf, SAVINGS_CALCULATED );
                    _SetTrue( conf, SAVINGS_JUST_CALCULATED );
                }
            }
            _SetFalse( conf, NEEDS_INDEX_SPLIT | NEEDS_SEGMENT_SPLIT );
        }
        conf = next;
    }
    ConstSavings();

    SortConflicts();
    state = ALLOC_BITS;
    conf = ConfList;
    if( conf == NULL ) return( state );
    opnd = conf->name;
    if( opnd->n.class == N_TEMP && (opnd->t.temp_flags & CONST_TEMP) ) {
        only_const_temps = TRUE;
    } else {
        only_const_temps = FALSE;
    }
    for( ;;  ) {
        if( conf == NULL ) break;
        opnd = conf->name;
        next = conf->next_conflict;
        if( _Isnt( conf, CONFLICT_ON_HOLD ) ) {
            /*
                We stop register allocating on the first CONST_TEMP we see
                so that any CONST_TEMP's that aren't needed can get cleaned
                up and their live information regenerated.
            */
            if( !only_const_temps && opnd->n.class == N_TEMP
                && (opnd->t.temp_flags & CONST_TEMP) ) return( ALLOC_CONST_TEMP );
            if( conf->savings == 0 || IsUncacheableMemory( conf->name ) ) {
                next = InMemory( conf );
            } else {
                next = GiveRegister( conf, FALSE );
            }
            if( opnd->v.conflict == conf ) { /* if it didn't get processed */
                state = ALLOC_DONE;
            }
        }
        conf = next;
    }
    return( state );
}


extern  void    ReConstFold( void )
/**********************************
    Call FoldIns on each instruction in case we propagated a constant
    into an instruction leaving something which looks like C op C -> T,
    which none of the regalloc tables can handle. Can't just call
    ConstFold because it works on a stupid partition.
*/
{
    instruction                 *ins;
    instruction                 *next;
    block                       *blk;

    for( blk = HeadBlock; blk != NULL; blk = blk->next_block ) {
        for( ins = blk->ins.hd.next; ins->head.opcode != OP_BLOCK; ins = next ) {
            next = ins->head.next;
            FoldIns( ins );
        }
    }
}


extern  bool    RegAlloc( bool keep_on_truckin ) {
/*************************************************
    Allocate registers to variables while expanding instructions.
    Instructions are expanded until they correspond 1 to 1 with machine
    instructions.  The first part of this routine is for the 8086.  We
    expand all instructions and then see if any variables get split up
    (Far pointers for example rarely get referenced as a whole.) If any
    variables get split so that only their parts are referenced, we
    throw away the conflict graph and start again.  This causes a
    segment and an offset to be treated as separate variables on the
    8086.  The second part of this routine just expands instructions,
    and gives out registers in turn until no more instructions or
    operands need work.
*/

    int unknowns;
    enum allocation_state       last;

    HW_CAsgn( GivenRegisters, HW_EMPTY );
    if( BlockByBlock == FALSE ) {
        InitChoices();
        unknowns = ExpandOps( keep_on_truckin );
        if( unknowns <= 0 ) return( unknowns == 0 );
        if( SplitConflicts() ) {
            FreeConflicts();
            NullConflicts( EMPTY );
            HaveLiveInfo = FALSE;
            if( _IsntModel( NO_OPTIMIZATION ) ) {
                DeadInstructions();
                FindReferences();
                PropagateMoves();
                PropRegsOne();
                ReConstFold();
            }
            FindReferences();
            MakeConflicts();
            MakeLiveInfo();
            HaveLiveInfo = TRUE;
            AxeDeadCode();
        }
    }
    last = ALLOC_DONE;
    for(;;) {
        InitChoices();
        unknowns = ExpandOps( keep_on_truckin );
        if( unknowns <= 0 ) break;
        FixChoices();
        if( last == ALLOC_CONST_TEMP ) {
            /* Ran into the first CONST_TEMP conflict.
               need to do a RegInsDead again in case some of the
               temps aren't used anymore */
            RegInsDead();
        }
        last = AssignConflicts();
        if( last == ALLOC_BITS ) {
            /* ran out of bits */
            AssignMoreBits();
        }
    }
    return( unknowns == 0 );
}