nullprop.c

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

    redefinition of the given operand.
*/
{
    instruction         *curr;

    blk = blk;
    curr = ins;
    while( curr->head.opcode != OP_BLOCK ) {
        // if we are going forward, the dereferences take precedence over the
        // redefinitions, the reverse is true when backpeddling
        if( forward ) {
            if( DereferencedBy( curr, op ) ) return( BLOCK_DEREFS );
            if( ReDefinedBy( curr, op ) ) return( BLOCK_REDEFS );
        #if 0
            if( curr->head.opcode == OP_MOV &&
                curr->operands[ 0 ] == op &&
                curr->result != op ) {
                // we see mov t1 -> t2, and are trying to see if t1 has dominating
                // derefs from this path on - this is true if t2 has dominating
                // derefs from this path on - so we recurse (Yikes!)
                parms.blk = blk;
                parms.ins = curr;
                parms.op = curr->result;
                parms.forward = TRUE;
                if( SafeRecurse( DominatingDeref, &parms ) != (void *)FALSE ) {
                    return( BLOCK_DEREFS );
                }
            }
        #endif
        } else {
            if( ReDefinedBy( curr, op ) ) return( BLOCK_REDEFS );
            if( DereferencedBy( curr, op ) ) return( BLOCK_DEREFS );
        }
        curr = NextIns( curr, forward );
    }
    return( BLOCK_NOTHING );
}

static  void            *DominatingDeref( parm_struct *parms )
/************************************************************
    Return TRUE if the given instruction is dominated by a dereference of op. This is not a true
    dominator in the sense of the dragon book, but a dominator in the sense that every path from
    the instruction given to the return encounters a dereference of op (if forward) or every
    path from the first instruction in the function to the instruction given encounters a deref
    of op (if backwards or forwards = FALSE ).
*/
{
    block_edge          *edge;
    edge_stack          *stk;
    int                 result;
    bool                dominated;
    block               *blk;


    // check instructions from ins to end of block
    // also check that op is USE_IN_ANOTHER_BLOCK
    result = BlockSearch( parms->blk, NextIns( parms->ins, parms->forward ), parms->op, parms->forward );
    switch( result ) {
    case BLOCK_DEREFS:
        return( (void *)TRUE );
    case BLOCK_REDEFS:
        return( (void *)FALSE );
    }
    if( LastBlock( parms->blk, parms->forward ) ||
        ( parms->op->v.usage & USE_IN_ANOTHER_BLOCK ) == EMPTY ) return( (void *)FALSE );
    stk = InitStack();
    PushTargets( stk, parms->blk, parms->forward );
    dominated = TRUE;
    while( dominated ) {
        if( Empty( stk ) ) break;
        edge = Pop( stk );
        blk = EdgeBlock( edge, parms->forward );
        if( blk->class & BLOCK_VISITED ) continue;
        result = BlockSearch( blk, FirstIns( blk, parms->forward ), parms->op, parms->forward );
        switch( result ) {
        case BLOCK_DEREFS:
            // continue on with the next block in the old depth-first search
            // this path is ok and we do not need to push any targets
            break;
        case BLOCK_REDEFS:
            // one path encountered a redefinition before it got a deref, so
            // the compare is not dominated by a dereference
            dominated = FALSE;
            break;
        default:
            PushTargets( stk, blk, parms->forward );
            if( LastBlock( blk, parms->forward ) ) {
                // we have hit either the return or head of the function without
                // finding a deref along this particular path, so the compare is
                // not dominated by a dereference.
                dominated = FALSE;
            }
        }
        blk->class |= BLOCK_VISITED;
    }
    FiniStack( stk );
    return( dominated ? (void *)TRUE : (void *)FALSE );
}

extern  void            FloodDown( block *blk, block_class bits )
/***************************************************************/
{
    edge_stack          *stk;
    block_edge          *edge;

    stk = InitStack();
    for(;;) {
        if( ( blk->class & bits ) != EMPTY ) {
            blk->class |= bits;
            PushTargets( stk, blk, TRUE );
        }
        if( Empty( stk ) ) break;
        edge = Pop( stk );
        blk = edge->destination;
    }
    FiniStack( stk );
}

static  bool            BlockSideEffect( block *blk )
/***************************************************/
{
    instruction         *ins;

    for( ins = blk->ins.hd.next; ins->head.opcode != OP_BLOCK; ins = ins->head.next ) {
        if( _OpIsCall( ins->head.opcode ) ) return( TRUE );
        if( SideEffect( ins ) ) return( TRUE );
    }
    return( FALSE );
}

static  bool            EdgeHasSideEffect( block *blk, instruction *cmp, bool cmp_result )
/****************************************************************************************/
{
    edge_stack          *stk;
    block               *elim;
    block               *taken;
    bool                side_effect;
    block_edge          *edge;

    if( cmp_result == TRUE ) {
        taken = blk->edge[ _TrueIndex( cmp ) ].destination;
        elim = blk->edge[ _FalseIndex( cmp ) ].destination;
    } else {
        taken = blk->edge[ _FalseIndex( cmp ) ].destination;
        elim = blk->edge[ _TrueIndex( cmp ) ].destination;
    }
    ClearBlockBits( BLOCK_VISITED );
    FloodDown( taken, BLOCK_VISITED );
    stk = InitStack();
    side_effect = FALSE;

    /*
     * Flood fill forward looking for a path which has a side effect on it.
     * Paths are killed when we hit a block already seen or which is in
     * the other edge of the graph (the edge which is taken).
     */
    while( !side_effect ) {
        if( ( elim->class & BLOCK_VISITED ) == EMPTY ) {
            if( BlockSideEffect( elim ) ) {
                side_effect = TRUE;
                break;
            }
            // should add something here which cuts out if we see a
            // deref of the temp we are searching for - a call to
            // BlockSearch with the appropriate parms should do
            elim->class |= BLOCK_VISITED;
            PushTargets( stk, elim, TRUE );
        }
        if( Empty( stk ) ) break;
        edge = Pop( stk );
        elim = edge->destination;
    }
    FiniStack( stk );
    ClearBlockBits( BLOCK_VISITED );
    return( side_effect );
}

static  bool            NullProp( block *blk )
/********************************************/
{
    instruction         *cmp;
    name                **ptr;
    parm_struct         parms;
    int                 dest_index;

    cmp = CompareIns( blk );
    if( cmp == NULL ) return( FALSE );
    switch( cmp->head.opcode ) {
    case OP_CMP_EQUAL:
        dest_index = _FalseIndex( cmp );
        break;
    case OP_CMP_NOT_EQUAL:
        dest_index = _TrueIndex( cmp );
        break;
    default:
        return( FALSE );
    }
    if( IsZero( cmp->operands[ 0 ] ) ) {
        ptr = &cmp->operands[ 1 ];
    } else if( IsZero( cmp->operands[ 1 ] ) ) {
        ptr = &cmp->operands[ 0 ];
    } else {
        return( FALSE );
    }
    parms.blk = blk;
    parms.ins = cmp;
    parms.op = *ptr;
    parms.forward = TRUE;
    ClearBlockBits( BLOCK_VISITED );
    if( DominatingDeref( &parms ) ) {
        if( !EdgeHasSideEffect( blk, cmp, cmp->head.opcode == OP_CMP_NOT_EQUAL ) ) {
            // only nuke the edge if the code we are removing
            // does not have a side effect or if the dominators are before the compare
            KillCondBlk( blk, cmp, dest_index );
            return( TRUE );
        }
    }
    parms.forward = FALSE;
    ClearBlockBits( BLOCK_VISITED );
    if( DominatingDeref( &parms ) ) {
        KillCondBlk( blk, cmp, dest_index );
        return( TRUE );
    }
    return( FALSE );
}

extern  void            PropNullInfo( void )
/*******************************************
    Use pointer dereferences as information to enable folding of
    pointer comparisons versus NULL.
*/
{
    block               *blk;
    bool                change;

    if( _IsModel( NO_OPTIMIZATION ) ) return;
    if( _IsModel( NULL_DEREF_OK ) ) return;
    change = FALSE;
    blk = HeadBlock;
    while( blk != NULL ) {
        change |= NullProp( blk );
        blk = blk->next_block;
    }
    ClearBlockBits( BLOCK_VISITED );
    if( change ){
        BlockTrim();
    }
}