regalloc.c

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

    }
    return( TRUE );
}


static  bool            CheckIndecies( instruction *ins,
                                       hw_reg_set reg, hw_reg_set except,
                                       name *op ) {
/***************************************************************************
    Used by TooGreedy
*/

    HW_TurnOn( except, ins->head.live.regs );
    HW_TurnOn( except, reg );
    if( StealsIdx( ins, except, op ) ) return( MAYBE );
    if( StealsSeg( ins, reg, except, op ) ) return( MAYBE );
    return( FALSE );
}


static  bool            TooGreedy( conflict_node *conf,
                                   hw_reg_set reg, name *op ) {
/*************************************************************************
    This routine decides whether giving register "reg" to conflict
    "conf" would be too greedy.  Too greedy means that it would use the
    last index registers across an instruction that still needed one, or
    take the last segment register across an instruction still needing
    one, or take away the last register of a certain type that an
    instruction is reserving.  For example, a generate entry like
        _Un(   ANY, ANY,  NONE ), V_NO,  G_UNKNOWN,    RG_BYTE_NEED
    means that this instruction is content to sit around for a while but
    will need a byte register left over in order to be able to guarantee
    that we can generate code, since all operands may go into memory and
    a register will be needed if the machine has no addressing mode for
    memory/memory operations. Notice that all three of these requirements
    must be satisfied. An instruction could be reserving 3 registers.
*/

    block               *blk;
    instruction         *ins;
    instruction         *last;
    hw_reg_set          *ins_needs;
    bool                rc;
    reg_set_index       needs;

    blk = conf->start_block;
    ins = conf->ins_range.first;
    if( conf->name->n.class == N_TEMP
     && _Is( conf, ( INDEX_SPLIT | SEGMENT_SPLIT ) ) ) {
        ins = conf->ins_range.last;
    }
    last = conf->ins_range.last;
    rc = FALSE;
    for(;;) {
        if( ins->u.gen_table == NULL ) { /* just created instruction*/
            needs = RL_;
        } else {
            needs = ins->u.gen_table->reg_set;
        }
        ins_needs = RegSets[  RegList[  needs  ].need  ];
        if( HW_CEqual( *ins_needs, HW_EMPTY ) || _Is( conf, NEVER_TOO_GREEDY )
         || UnaryOpGetsReg( ins, reg, op ) ) {
            rc = CheckIndecies( ins, reg, HW_EMPTY, op );
        } else { /* can the instruction and indecies still get needed regs?*/
            rc = TRUE;
            for(;;) {
                if( !HW_Ovlap( *ins_needs, ins->head.live.regs )
                 && !HW_Ovlap( reg, *ins_needs ) ) {
                    rc = CheckIndecies( ins, reg, *ins_needs, op );
                    if( rc == FALSE ) break;
                }
                ++ins_needs;
                if( HW_CEqual( *ins_needs, HW_EMPTY ) ) break;
            }
        }
        if( ins == last ) break;
        ins = ins->head.next;
        while( ins->head.opcode == OP_BLOCK ) {
            blk = blk->next_block;
            ins = blk->ins.hd.next;
        }
        if( rc != FALSE ) break;
    }
    return( rc );
}


static  void    CheckIndexZap( conflict_node *conf, block *blk, instruction *ins ) {
/***********************************************************************************
    If the given instruction uses the name for conf as an index in the result,
    then mark the conflict as conflicting with anything in the instructions
    zap set, as the zap will take place before the result is written.
*/

    name        *dst;

    dst = ins->result;
    if( dst != NULL && dst->n.class == N_INDEXED ) {
        if( FindConflictNode( dst->i.index, blk, ins ) == conf ) {
            HW_TurnOn( conf->with.regs, ins->zap->reg );
        }
    }
}


static  void    NeighboursUse( conflict_node *conf ) {
/*****************************************************
    Calculate which conflicts "conf" could not share the same register
    with by running through the live range of the conflict and checking
    what other conflicts are live and what registers are live or
    modified at a point where "conf" is also live.
*/

    block               *blk;
    instruction         *ins;
    name                *dst;
    name                *definition;
    name_set            no_conflict;
    hw_reg_set          tmp;
    instruction         *last;
    global_bit_set      gbit;
    local_bit_set       lbit;

    blk = conf->start_block;
    ins = conf->ins_range.first;
    last = conf->ins_range.last;
    if( ins->head.opcode == OP_MOV && ins->result == conf->name ) {
        definition = ins->operands[0];
    } else {
        definition = NULL;
    }
    HW_CAsgn( conf->with.regs, HW_EMPTY );
    _GBitInit( conf->with.out_of_block, EMPTY );
    _LBitInit( conf->with.within_block, EMPTY );
    _INS_NOT_BLOCK ( last );
    if( ins != last ) {
        _NameSetInit( no_conflict );
        for(;;) {
            ins = ins->head.next;
            if( ins->head.opcode != OP_BLOCK ) {

                /*   The no_conflict set indicates names which do not conflict*/
                /*   with conf->name due to OP_MOV instructions*/

                dst = ins->result;
                if( dst != NULL ) {
                    NowDead( dst, FindConflictNode( dst, blk, ins ),
                                &no_conflict, blk );
                }
                if( ins->head.opcode != OP_MOV ) {
                    if( dst == conf->name ) {
                        _NameSetInit( no_conflict );
                    }
                } else if( ins->operands[ 0 ] == conf->name ) {
                    NowAlive( dst, FindConflictNode( dst, blk, ins ),
                                    &no_conflict, blk );
                } else if( dst == conf->name ) {
                    _NameSetInit( no_conflict );
                    definition = ins->operands[ 0 ];
                    NowAlive( definition,
                              FindConflictNode( definition, blk, ins ),
                              &no_conflict, blk );
                }
                /* it only conflicts if temp is live across result/zap*/
                if( ins != last ) {
                    if( ( conf->name->v.usage & ( NEEDS_MEMORY | USE_ADDRESS ) )
                     || ( _LBitEmpty( conf->id.within_block )
                       && _GBitEmpty( conf->id.out_of_block ) )
                     || ( _LBitOverlap( conf->id.within_block,
                          ins->head.next->head.live.within_block ) )
                     || ( _GBitOverlap( conf->id.out_of_block,
                          ins->head.next->head.live.out_of_block ) ) ) {
                        HW_TurnOn( conf->with.regs, ins->zap->reg );
                        if( dst != NULL && dst->n.class == N_REGISTER ) {
                            HW_TurnOn( conf->with.regs, dst->r.reg );
                        }
                    } else {
                        // know that conf is not live after this instruction
                        // if it was live before, must mark it as conflicting
                        // with anything in the zap set         BBB - Nov, 1994
                        if( ( _LBitOverlap( conf->id.within_block,
                                ins->head.live.within_block ) )
                         || ( _GBitOverlap( conf->id.out_of_block,
                                ins->head.live.out_of_block ) ) ) {
                            CheckIndexZap( conf, blk, ins );
                        }
                    }
                } else {
                    CheckIndexZap( conf, blk, ins );
                }
            }
            if( _GBitOverlap( ins->head.live.out_of_block,
                              conf->id.out_of_block )
             || _LBitOverlap( ins->head.live.within_block,
                              conf->id.within_block )
             || ( _LBitEmpty( conf->id.within_block )
               && _GBitEmpty( conf->id.out_of_block ) ) ) {
                tmp = ins->head.live.regs;
                HW_TurnOff( tmp, no_conflict.regs );
                HW_TurnOn( conf->with.regs, tmp );
                _GBitAssign( gbit, ins->head.live.out_of_block );
                _GBitTurnOff( gbit, no_conflict.out_of_block );
                _GBitTurnOn( conf->with.out_of_block, gbit );
                _LBitAssign( lbit, ins->head.live.within_block );
                _LBitTurnOff( lbit, no_conflict.within_block );
                _LBitTurnOn( conf->with.within_block, lbit );
            }
            if( ins->head.opcode == OP_CALL
                        || ins->head.opcode == OP_CALL_INDIRECT ) {
                _NameSetInit( no_conflict );
            } else if( ins->head.opcode == OP_BLOCK ) {
                _LBitInit( conf->with.within_block, EMPTY );
                if( blk->next_block == NULL ) {
                    Zoiks( ZOIKS_141 );
                    break;
                }
                blk = blk->next_block;
                ins = (instruction *)&blk->ins;
                _NameSetInit( no_conflict );
            }
            if( ins->id == last->id ) break;
        }
    }
    /*
        Here's the deal with the following: we are assuming that a register
        being used to initialize a const temp must be the allocated register
        of another const temp - ie we cannot allow reductions which will turn
        something like "mov K -> t1" into "mov K -> R1, mov R1 -> t1" - any
        constant loading reduction which can generate a move from a register
        into a const temp must wait until the const temp has been allocated a
        register or dissolved back into a constant before happening.

        The reason we need to do this is because const temps percolating down
        from parent-loops will be marked as being live all throughout the loop,
        which means they would conflict with this const temp and so could not
        normally share a register.

        BBB - July 22, 1995
     */
    if( _ConstTemp( conf->name ) ) {
        if( definition != NULL && definition->n.class == N_REGISTER ) {
            HW_TurnOff( conf->with.regs, definition->r.reg );
            conf->savings = MAX_SAVE;
        }
    }
}


static  hw_reg_set      GiveBestReg( conflict_node *conf, reg_tree *tree,
                                     hw_reg_set except, bool needs_one ) {
/*************************************************************************
    Give the best possible register to conflict "conf", (whose tree is
    "tree"), excluding registers in the set "except".  The best register
    is one that would create the most register register moves of the
    form "MOV Rn => Rn", or operations of the form  "OP Rn,x => Rn"
    but is not too greedy (See TooGreedy).  needs_one is TRUE when the
    conflict really really really needs to be assigned a register.  If
    this routine fails, but needs_one is TRUE, something truly bad has
    happened.
*/

    hw_reg_set  reg;
    hw_reg_set  best;
    int         best_saves;
    int         saves;
    hw_reg_set  *possible;
    hw_reg_set  given;
    hw_reg_set  gave_hi;
    hw_reg_set  gave_lo;
    bool        greed;
    bool        all_TRUE;
    bool        failed;

    NeighboursUse( conf );
    if( tree == NULL ) {
        HW_CAsgn( given, HW_EMPTY );
    } else if( tree->regs == NULL ) {
        /*
         * there are no restraints on the whole temporary (not referenced)
         * so give registers to its high and low parts seperately
         */
        failed = FALSE;
        HW_CAsgn( gave_hi, HW_EMPTY );
        HW_CAsgn( gave_lo, HW_EMPTY );
        if( tree->hi != NULL ) {
            gave_hi = GiveBestReg( conf, tree->hi, except, needs_one );
            if( HW_CEqual( gave_hi, HW_EMPTY ) ) {
                failed = TRUE;
            }
        }
        if( tree->lo != NULL ) {
            given = except;
            HW_TurnOn( given, gave_hi );
            gave_lo = GiveBestReg( conf, tree->lo, given, needs_one );
            if( HW_CEqual( gave_lo, HW_EMPTY ) ) {
                failed = TRUE;
            }
        }
        if( failed ) {
            HW_CAsgn( given, HW_EMPTY );
        } else {
            given = gave_hi;
            HW_TurnOn( given, gave_lo );
        }
        HW_TurnOn( GivenRegisters, gave_hi );
        HW_TurnOn( GivenRegisters, gave_lo );
    } else {
        best = HW_EMPTY;
        best_saves = -1;
        all_TRUE = TRUE;
        possible = tree->regs;
        for(;;) {
            reg = *possible;
            if( HW_CEqual( reg, HW_EMPTY ) ) break;
            if( !HW_Ovlap( reg, conf->with.regs )
             && !HW_Ovlap( reg, except ) ) {
                greed = TooGreedy( conf, reg, tree->temp );
                if( greed == FALSE ) {
                    saves = CountRegMoves( conf, reg, conf->tree, 3 );
                    if( ( saves > best_saves )
                     || ( saves == best_saves
                       && HW_Subset( GivenRegisters, reg )
                       && !HW_Subset( GivenRegisters, best ) ) ) {
                        best = reg;
                        best_saves = saves;
                    }
                }
                if( greed != TRUE ) {
                    all_TRUE = FALSE;
                }
            }
            ++ possible;
        }
        if( all_TRUE ) {
            HW_CAsgn( given, HW_EMPTY );
        } else if( HW_CEqual( best, HW_EMPTY ) ) {
            if( _Is( conf, NEEDS_INDEX ) ) {
                _SetTrue( conf, NEEDS_INDEX_SPLIT );
                _SetFalse( conf, NEEDS_INDEX );
            }
            if( _Is( conf, NEEDS_SEGMENT ) ) {
                _SetTrue( conf, NEEDS_SEGMENT_SPLIT );
                _SetFalse( conf, NEEDS_SEGMENT );
            }
            HW_CAsgn( given, HW_EMPTY );
        } else if( needs_one || WorthProlog( conf, best ) ) {
            FixInstructions( conf, tree, best, TRUE );
            given = best;