cse.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 1,632 行 · 第 1/4 页

                if( next_bit == EMPTY ) break;
                _BLKBITS( blk ) = _BLKBITS( daddy ) | next_bit;
                change = TRUE;
            }
            blk = blk->u.partition;
        }
        if( next_bit == EMPTY ) break;
        if( change == FALSE ) break;
    }

    /* rip off any blocks in the partition without bits*/
    /* and propagate the bits through the instructions*/

    owner = &root->u.partition;
    for( ;; ) {
        blk = *owner;
        ins = blk->ins.hd.next;
        while( ins->head.opcode != OP_BLOCK ) {
            _INSBITS( ins ) = _BLKBITS( blk );
            ins = ins->head.next;
        }
        if( _BLKBITS( blk ) == EMPTY ) {
            *owner = blk->u.partition;
        } else {
            owner = &blk->u.partition;
        }
        if( blk == root ) break;
    }
}


extern  void    SetCSEBits( instruction *ins, instruction *new_ins )
/*******************************************************************
    set the ancestor bits of "new_ins" to be the same as "ins".
*/
{
    a_bit_set   bits;

    if( ins->head.opcode == OP_BLOCK ) {
        bits = _BLKBITS( _BLOCK( ins ) );
    } else {
        bits = _INSBITS( ins );
    }
    _INSBITS( new_ins ) = bits;
}


static  instruction *WhichIsAncestor( instruction *ins1, instruction *ins2 )
/***************************************************************************
    Return which of instructions "ins1" or "ins2" is always executed
    first, or a pointer the last instruction in a block which is a
    common ancestor to "ins1" and "ins2".
*/
{
    instruction *first;
    instruction *ins;
    a_bit_set   bits1;
    a_bit_set   bits2;
    block       *blk;

    bits1 = _INSBITS( ins1 );
    bits2 = _INSBITS( ins2 );
    if( bits1 == bits2 ) {  /* same_block*/
        first = NULL;
        if( ins1 != ins2 ) {
            ins = ins1;
            for( ;; ) {
                ins = ins->head.next;
                if( ins == ins2 ) {
                    first = ins1;
                } else if( ins->head.opcode == OP_BLOCK ) {
                    first = ins2;
                }
                if( first != NULL ) break;
            }
        }
    } else if( ( bits1 & bits2 ) == bits1 ) {
        first = ins1;
    } else if( ( bits1 & bits2 ) == bits2 ) {
        first = ins2;
    } else { /* find a hoist point*/
        bits1 &= bits2;
        ins = ins1;
        while( ins->head.opcode != OP_BLOCK ) {
            ins = ins->head.next;
        }
        blk = _BLOCK( ins );
        while( _BLKBITS( blk ) != bits1 ) {
            blk = blk->u.partition;
        }
        first = blk->ins.hd.prev;
        while( first->head.opcode == OP_NOP ) {
            if( first->flags.nop_flags & NOP_ZAP_INFO ) break;
            first = first->head.prev;
        }
        for( ;; ) { /* scan back over all the conditional branches at the end of block*/
            if( ( first->head.opcode != OP_SELECT )
                && !_OpIsCondition( first->head.opcode ) ) break;
            first = first->head.prev;
        }
    }
    return( first );
}


static  void    CleanPartition( void )
/*************************************
    Turn of all the bits we turned on in FindPartition.
*/
{
    block       *blk;

    blk = HeadBlock;
    while( blk != NULL ) {
        blk->class &= ~PARTITION_ROOT;
        blk->u.partition = NULL;
        blk = blk->next_block;
    }
}


static  bool    CanCrossBlocks( instruction *ins1,
                                instruction *ins2, name *op )
/************************************************************
    If we're generating a partial routine, we cannot cause an
    existing N_TEMP to cross blocks, due to an assumption
    in ForceTempsMemory.
*/
{
    if( !BlockByBlock ) return( TRUE );
    if( op->n.class != N_TEMP ) return( TRUE );
    if( _INSBITS( ins1 ) == _INSBITS( ins2 ) ) return( TRUE );
    if( op->t.temp_flags & CROSSES_BLOCKS ) return( TRUE );
    return( FALSE );
}


static  void    UseInOther( instruction *ins1, instruction *ins2, name *op )
/***************************************************************************
    Indicate that we have caused operand "op" to be used in both "ins1"
    and "ins2" where it was previously only used in one of those
    instructions.  This may change it's USE_IN_ANOTHER_BLOCK status.
*/
{
    if( _INSBITS( ins1 ) != _INSBITS( ins2 ) ) {
        if( op->n.class == N_MEMORY ) {
            op->v.usage |= USE_IN_ANOTHER_BLOCK;
        } else if ( op->n.class == N_TEMP ) {
            op->t.temp_flags |= CROSSES_BLOCKS;
        }
    }
}


static  bool    UnOpsLiveFrom( instruction *first, instruction *last )
/*********************************************************************
    Do the operand and result of "first" live until instruction "last"?
*/
{
    instruction *ins;

    ins = last->head.prev;
    for( ;; ) {
        while( ins->head.opcode == OP_BLOCK ) {
            ins = _BLOCK( ins )->input_edges->source->ins.hd.prev;
        }
        if( ins == first ) break;
        if( ReDefinedBy( ins, first->operands[ 0 ] ) ) return( FALSE );
        if( ReDefinedBy( ins, first->result ) ) return( FALSE );
        ins = ins->head.prev;
    }
    return( TRUE );
}


static  who_dies BinOpsLiveFrom( instruction *first,
                                instruction *last,
                                name *op1, name *op2, name *result )
/*******************************************************************
    Determine which of "op1", "op2", and "result" live from instruction
    "first" to instruction "last".
*/
{
    instruction *ins;
    bool        result_dies;

    ins = last->head.prev;
    if( result == NULL ) {
        for( ;; ) {
            while( ins->head.opcode == OP_BLOCK ) {
                ins = _BLOCK( ins )->input_edges->source->ins.hd.prev;
            }
            if( ins == first ) break;
            if( ReDefinedBy( ins, op1 ) ) return( OP_DIES );
            if( ReDefinedBy( ins, op2 ) ) return( OP_DIES );
            ins = ins->head.prev;
        }
        return( ALL_LIVE );
    } else {
        result_dies = FALSE;
        for( ;; ) {
            while( ins->head.opcode == OP_BLOCK ) { /* 89-09-05 */
                ins = _BLOCK( ins )->input_edges->source->ins.hd.prev;
            }
            if( ins == first ) break;
            if( ReDefinedBy( ins, op1 ) ) return( OP_DIES );
            if( ReDefinedBy( ins, op2 ) ) return( OP_DIES );
            if( ReDefinedBy( ins, result ) ) {
                result_dies = TRUE;
            }
            ins = ins->head.prev;
        }
        if( result_dies ) return( RESULT_DIES );
        return( ALL_LIVE );
    }
}

static  bool            HoistLooksGood( instruction *target, instruction *orig )
/*******************************************************************************
    Does it look like a good idea to hoist a busy expression from the original
    instruction to the hoist point. Currently, this is not a good idea if we
    are not overly concerned about code size and we would be hoisting the expr
    out of a switch statement.
*/
{
    instruction         *ins;
    block               *target_blk;
    block               *blk;

    if( OptForSize > 50 ) return( TRUE );
    for( ins = target; ins->head.opcode != OP_BLOCK; ins = ins->head.next );
    target_blk = _BLOCK( ins );
    for( ins = orig; ins->head.opcode != OP_BLOCK; ins = ins->head.next );
    blk = _BLOCK( ins );
    if( blk == target_blk ) return( TRUE );
    while( blk != NULL ) {
        if( blk->inputs != 1 ) _Zoiks( ZOIKS_103 ); // because we're in a partition
        blk = blk->input_edges->source;
        if( ( blk->class & SELECT ) != EMPTY ) return( FALSE );
        if( blk == target_blk ) return( TRUE );
    }
    _Zoiks( ZOIKS_104 );
    return( TRUE );
}


#define i1( ins )      _OpIsBinary( ins->head.opcode ) /* unary=0, binary=1 */


static  instruction     *ProcessExpr( instruction *ins1,
                                      instruction *ins2, bool signed_matters )
/*****************************************************************************
    Given two instruction "ins1" and "ins2" in the same partition, first
    find out if they have the same operands, and if they do, determine
    "WhichIsAncestor", which gives us the common ancestor of "ins1" and
    "ins2".  If this is one of ins1 or ins2, we have a common
    subexpressions as long as the operands of the ancestor aren't
    redefined between the two (BinOpsLiveFrom).  If we have a hoist
    point, (different common ancestor) we have a very busy expression as
    long as the operands of ins1 and ins2 aren't redefined between the
    hoist point and either of ins1 and ins2 (BinOpsLiveFrom).
*/
{
    instruction         *first;
    instruction         *new_ins;
    instruction         *dead_or_new_ins;
    name                *temp;
    type_class_def      class;
    who_dies            killed;
    int                 i;

    dead_or_new_ins = NULL;
    i = i1( ins1 );
    if( ins1->head.opcode == OP_CONVERT ) {
        if( ins1->base_type_class != ins2->base_type_class ) {
            return( FALSE );
        }
    }
    if( signed_matters ) {
        if( ins1->type_class != ins2->type_class ) {
            return( NULL );
        }
    } else {
        if( Unsigned[ ins1->type_class ] != Unsigned[ ins2->type_class ] ) {
            return( NULL );
        }
    }
    if( ins1->operands[ 0 ] != ins2->operands[ 0 ] ||
        ins1->operands[ i ] != ins2->operands[ i ] ) {
          if( !_OpCommutes( ins1->head.opcode ) ) return( NULL );
          if( ins1->operands[ 0 ] != ins2->operands[ i ] ||
              ins1->operands[ i ] != ins2->operands[ 0 ] ) return( NULL );
    }
    first = WhichIsAncestor( ins1, ins2 );
    if( first == ins2 ) {
        ins2 = ins1;
        ins1 = first;
    }
    if( first == ins1 ) { /* or used to be ins2*/
        if( ( ins1->ins_flags & INS_DEFINES_OWN_OPERAND ) == EMPTY ) {
            killed = BinOpsLiveFrom( ins1, ins2, ins1->operands[ 0 ],
                                      ins1->operands[ i ], ins1->result );
            if( killed != OP_DIES ) {
                class = ins1->result->n.name_class;
                if( killed == RESULT_DIES
                 || !CanCrossBlocks( ins1, ins2, ins1->result ) ) {
                    temp = AllocTemp( class );
                    new_ins = MakeMove( temp, ins1->result, class );
                    ins1->result = temp;
                    SuffixIns( ins1, new_ins );
                    SetCSEBits( ins1, new_ins );
                    FPNotStack( temp );
                }
                new_ins = MakeMove( ins1->result, ins2->result, class );
                UseInOther( ins1, ins2, ins1->result );
                dead_or_new_ins = ins2;
                SetCSEBits( ins2, new_ins );
                SuffixIns( ins2, new_ins );
                FPNotStack( ins1->result );
            }
        }
    } else if( first != NULL ) { /* we calculated a hoist point*/
        if( ins1->operands[ 0 ]->n.class != N_INDEXED
         && ins1->operands[ i ]->n.class != N_INDEXED
         && Hoistable( ins1, NULL )
         && BinOpsLiveFrom( first->head.next, ins1, ins1->operands[ 0 ],
                            ins1->operands[ i ], NULL ) == ALL_LIVE
         && BinOpsLiveFrom( first->head.next, ins2, ins2->operands[ 0 ],
                            ins2->operands[ i ], NULL ) == ALL_LIVE
         && HoistLooksGood( first, ins1 )
         && HoistLooksGood( first, ins2 ) ) {
            class = ins1->type_class;
            temp = AllocTemp( class );
            temp->t.temp_flags |= CROSSES_BLOCKS;
            if( _OpIsBinary( ins1->head.opcode ) ) {
                new_ins = MakeBinary( ins1->head.opcode,
                                       ins1->operands[ 0 ],
                                       ins1->operands[ 1 ],
                                       temp, class );
            } else {
                new_ins = MakeUnary( ins1->head.opcode,
                                       ins1->operands[ 0 ],
                                       temp, class );
            }
            new_ins->base_type_class = ins1->base_type_class;
            dead_or_new_ins = new_ins;
            SetCSEBits( first, new_ins );
            SuffixIns( first, new_ins );
            new_ins = MakeMove( temp, ins1->result, class );
            SetCSEBits( ins1, new_ins );
            SuffixIns( ins1, new_ins );
            new_ins = MakeMove( temp, ins2->result, class );
            SetCSEBits( ins2, new_ins );
            SuffixIns( ins2, new_ins );
        }
    }
    return( dead_or_new_ins );
}


static  bool    OkToInvert( name *div )
/**************************************
   Is it OK to compute the reciprical of 'div'? Either it must
   be exactly representable (a integer power of two) or the user
   must have said that it was OK.
*/
{
    if( _IsModel( FP_UNSTABLE_OPTIMIZATION ) ) return( TRUE );
    if( (div->n.class == N_TEMP) && (div->t.temp_flags & CONST_TEMP) ) {
        div = div->v.symbol;
    }
    if( div->n.class != N_CONSTANT ) return( FALSE );
    if( div->c.const_type != CONS_ABSOLUTE ) return( FALSE );
    if( !CFIs32( div->c.value ) ) return( FALSE );
    if( GetLog2( div->c.int_value ) == -1 ) return( FALSE );
    return( TRUE );
}


static  bool    ProcessDivide( instruction *ins1, instruction *ins2 )
/********************************************************************
    Given two instruction "ins1" and "ins2" in the same partition, first
    find out if they have the same divisor, and if they do, determine
    "WhichIsAncestor", which gives us the common ancestor of "ins1" and
    "ins2".  If this is one of ins1 or ins2, we have a common
    subexpressions as long as the divisor of the ancestor aren't
    redefined between the two (BinOpsLiveFrom).
*/
{
    instruction         *first;
    instruction         *new_ins;
    name                *temp;
    who_dies            killed;
    name                *divisor;

    if( ins1->type_class != ins2->type_class ) return( FALSE );
    if( !DivIsADog( ins1->type_class ) ) return( FALSE );
    if( ins1->operands[ 1 ] != ins2->operands[ 1 ] ) return( FALSE );
    first = WhichIsAncestor( ins1, ins2 );
    if( first == ins2 ) {
        ins2 = ins1;
        ins1 = first;
    }
    if( first == ins1 ) {
        divisor = ins1->operands[ 1 ];
        if( !OkToInvert( divisor ) ) return( FALSE );
        if( !ReDefinedBy( ins1, divisor ) ) {
            killed = BinOpsLiveFrom( ins1, ins2, divisor, divisor, NULL );