trecurse.c

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

        for( i = 0; i < ins->num_operands; i++ ) {
            if( !SafeOp( ins->operands[ i ], FALSE ) ) return( FALSE );
        }
        if( ins->result == ReturnValue ) {
            // check to see if this value we are writing into the
            // return register is the value returned from the
            // recursive call we are eliminating - if so continue
            if( CheckReturn( ins ) ) continue;
        }
        if( !SafeOp( ins->result, TRUE ) ) return( FALSE );
    }
    return( TRUE );
}

static pointer SafeBlock( block *blk )
/*********************************************************
    Return blk if the given block, and all reachable blocks,
    are safe to ignore for purposes of eliminating tail recursion,
    We abuse a pointer as a boolean variable because that is
    what SafeRecurse wants.
*/
{
    int         i;
    block       *dest;
    block       *safe;

    if( blk->class & BLOCK_MARKED ) return( NULL );
    blk->class |= BLOCK_MARKED;
    safe = NULL;
    if( SafePath( blk->ins.hd.next ) ) {
        safe = blk;
        for( i = 0; i < blk->targets; i++ ) {
            dest = blk->edge[ i ].destination;
            if( SafeRecurse( SafeBlock, dest ) == NULL ) {
                safe = NULL;
                break;
            }
        }
    }
    blk->class &= ~BLOCK_MARKED;
    return( safe );
}

static bool ScaryOperand( name *var )
/************************************
    return TRUE if the operand given has any properties which
    might make elimination of tail recursion impossible
*/
{
    if( var != NULL ) {
        // if anything has had its address taken we chicken out
        if( var->n.class == N_TEMP ) {
            return( var->v.usage & USE_ADDRESS );
        }
    }
    return( FALSE );
}

static bool ScaryConditions( void )
/**********************************
    Traverse the current function and return
    TRUE if there are any conditions present which
    would scare us out of doing tail recursion
    elimination, such as vars which have had
    their addresses taken...
*/
{
    block       *blk;
    instruction *ins;
    int         i;

    blk = HeadBlock;
    while( blk != NULL ) {
        ins = blk->ins.hd.next;
        while( ins->head.opcode != OP_BLOCK ) {
            for( i = 0; i < ins->num_operands; i++ ) {
                if( ScaryOperand( ins->operands[ i ] ) ) return( TRUE );
            }
            if( ScaryOperand( ins->result ) ) return( TRUE );
            ins = ins->head.next;
        }
        blk = blk->next_block;
    }
    return( FALSE );
}

static bool     OkayToTransCall( block *blk, instruction *call_ins )
/*******************************************************************
    Check to see if it is okay to turn this call instruction
    into a jump to eliminate tail recursion.  To see if this
    is safe, we have to follow all paths of execution to the
    return block and make sure that nothing important happens
    along these.
*/
{
    sym_handle  label;
    block       *dest;
    int         i;
    instruction *parm;
    instruction *ins;
    bool        ok;

    label = AskForLblSym( CurrProc->label );
    if( call_ins->operands[ CALL_OP_ADDR ]->v.symbol != label ) {
        return( FALSE );
    }

    // check to make sure length of parm lists are the same
    parm = _TR_LINK( call_ins );
    for( ins = _PROC_LINK( CurrProc ); ins != NULL; ins = _TR_LINK( ins ) ) {
        if( parm == NULL ) return( FALSE );
        parm = _TR_LINK( parm );
    }
    if( parm != NULL ) return( FALSE );

    // check to see if all paths are hazard-free from the
    //  call ins to the return block
    ok = FALSE;
    ReturnValue = call_ins->result;
    blk->class |= BLOCK_MARKED;
    // if the call is in the return block, then there are no
    // paths out of this routine which do not go through it
    // (except perhaps stuff calling aborts routines) so don't
    // bother - better running out of stack than an infinite loop
    // (besides - certain codegen stuff needs a RET block)
    if( ( ( blk->class & RETURN ) == EMPTY ) &&
            SafePath( call_ins->head.next ) ) {
        ok = TRUE;
        for( i = 0; i < blk->targets; i++ ) {
            dest = blk->edge[ i ].destination;
            if( SafeBlock( dest ) == NULL ) {
                ok = FALSE;
                break;
            }
        }
    }
    blk->class &= ~BLOCK_MARKED;
    return( ok );
}

extern void     TRAddParm( instruction *call_ins, instruction *parm_ins )
/************************************************************************
    Add another instruction to the list of parameters for the given call
    instruction.
*/
{
    // if either is NULL we've had an error and should refrain from GP faulting
    if( call_ins == NULL || parm_ins == NULL ) return;
    _TR_LINK( parm_ins ) = (void *)_TR_LINK( call_ins );
    _TR_LINK( call_ins ) = (void *)parm_ins;
}

extern void     TRDeclareParm( instruction *parm_ins )
/*****************************************************
    Declare another parm for the current procedure. This parm
    is added to a linked list hanging off of CurrProc.
*/
{
    if( parm_ins == NULL ) return;
    _TR_LINK( parm_ins ) = (void *)_PROC_LINK( CurrProc );
    _PROC_LINK( CurrProc ) = (void *)parm_ins;
}

extern bool     TailRecursion( void )
/************************************
    Eliminate any tail recursion. We assume that, for any call in
    the function, we have a linked list of the parameters to that
    call which was built up while creating the call instruction from
    the tree, through the use of TRAddParm.
    To do the deed, we scramble through the instructions backwards
    following all possible paths of execution. If, on any path, we
    encounter an instruction which might make tail recursion impossible
    to eliminate, we give up. If we encounter a call to ourselves
    before we encounter a useful instruction, we replace the call with
    some code which moves the parameters into the appropriate spots
    and jumps to the block just after the prologue.
*/
{
    block       *blk;
    instruction *ins;
    instruction *next;
    bool        changed;

    changed = FALSE;
    if( _IsntModel( NO_OPTIMIZATION ) &&
        !ScaryConditions() && !BlockByBlock ) {
        blk = HeadBlock;
        while( blk != NULL ) {
            ins = blk->ins.hd.next;
            while( ins->head.opcode != OP_BLOCK ) {
                if( ins->head.opcode == OP_CALL ) {
                    if( OkayToTransCall( blk, ins ) ) {
                        DoTrans( blk, ins );
                        changed = TRUE;
                        break;
                    }
                }
                ins = ins->head.next;
            }
            blk = blk->next_block;
        }
    }
    // now reset our links and flags
    blk = HeadBlock;
    while( blk != NULL ) {
        ins = blk->ins.hd.next;
        while( ins->head.opcode != OP_BLOCK ) {
            _TR_LINK( ins ) = NULL;
            ins = ins->head.next;
        }
        blk = blk->next_block;
    }
    for( ins = _PROC_LINK( CurrProc ); ins != NULL; ins = next ) {
        next = _TR_LINK( ins );
        _TR_LINK( ins ) = NULL;
    }
    return( changed );
}