trecurse.c

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

/****************************************************************************
*
*                            Open Watcom Project
*
*    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
*
*  ========================================================================
*
*    This file contains Original Code and/or Modifications of Original
*    Code as defined in and that are subject to the Sybase Open Watcom
*    Public License version 1.0 (the 'License'). You may not use this file
*    except in compliance with the License. BY USING THIS FILE YOU AGREE TO
*    ALL TERMS AND CONDITIONS OF THE LICENSE. A copy of the License is
*    provided with the Original Code and Modifications, and is also
*    available at www.sybase.com/developer/opensource.
*
*    The Original Code and all software distributed under the License are
*    distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
*    EXPRESS OR IMPLIED, AND SYBASE AND ALL CONTRIBUTORS HEREBY DISCLAIM
*    ALL SUCH WARRANTIES, INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF
*    MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR
*    NON-INFRINGEMENT. Please see the License for the specific language
*    governing rights and limitations under the License.
*
*  ========================================================================
*
* Description:  Tail recursion elimination.
*
****************************************************************************/


#include "standard.h"
#include "model.h"
#include "coderep.h"
#include "opcodes.h"
#include "typedef.h"
#include "procdef.h"
#include "dump.h"

extern proc_def         *CurrProc;
extern block            *HeadBlock;
extern bool             BlockByBlock;

extern  sym_handle      AskForLblSym(label_handle);
extern  bool            SideEffect(instruction*);
extern  pointer         SafeRecurse(pointer(*)(),pointer);
extern  name            *AllocTemp(type_class_def );
extern  label_handle    AskForNewLabel( void );
extern  void            PrefixIns(instruction*,instruction*);
extern  void            SuffixIns(instruction *,instruction *);
extern  void            ReplIns(instruction *,instruction *);
extern  void            FreeIns(instruction *);
extern  instruction     *MakeMove(name *,name *,type_class_def );
extern  instruction     *MakeConvert(name *,name *,type_class_def,type_class_def );
extern  void            RemoveInputEdge( block_edge * );
extern  void            PointEdge( block_edge *, block * );

static  name            *ReturnValue;

#define _TR_LINK( x )   x->u2.parm_list
#define _PROC_LINK( x ) x->parms_list


static instruction *FindPreviousIns( instruction *curr )
/*******************************************************
    Return the instruction which would be executed immediately prior
    to the given instruction, ignoring block boundaries and other
    such trivia. Uses the MARKED flag to determine which, of all
    possible input sources, to select.
*/
{
    instruction *prev;
    block       *blk;
    block_edge  *edge;

    prev = curr->head.prev;
    if( prev->head.opcode == OP_BLOCK ) {
        blk = _BLOCK( prev );
        edge = blk->input_edges;
        while( edge != NULL ) {
            if( edge->source->class & BLOCK_MARKED ) break;
            edge = edge->next_source;
        }
        prev = edge->source->ins.hd.prev;
    }
    // note - prev->head.opcode guaranteed not to be OP_BLOCK
    // because of silly OP_NOP appended to every instruction ring
    return( prev );
}


static bool SafeOp( name *op, bool write )
/*****************************************
    Return TRUE if the given operand is not something which
    would indicate an instruction with a possibly useful effect.
    Basically, we are allowed to ignore instructions which simply
    shuffle temporaries and constants around, as well as stuff
    which reads registers. Writing a register is bad news though.
*/
{
    if( op == NULL ) return( TRUE );
    switch( op->n.class ) {
    case N_TEMP:
    case N_CONSTANT:
        return( TRUE );
    case N_REGISTER:
        return( !write );
    default:
        return( FALSE );
    }
}

static bool CheckReturn( instruction *ins )
/******************************************
    Check to see if the given instruction, which writes to
    ReturnValue, receives it's value, unmodified, from the
    return value of the recursive call. To do this, backtrack
    through the blocks (always choosing the MARKED one from
    the list of input sources) keeping track of the source of the
    value we are writing into the return register. If, when
    we reach the call (as we must), this value is the return
    value itself, we can declare this instruction safe.
*/
{
    name        *value;

    // since we have already descended past all these instructions on
    // the way down we know the first call we will hit will be the one
    // we are thinking of eliminating
    value = ReturnValue;
    while( ins->head.opcode != OP_CALL ) {
        if( ins->result == value ) {
            if( ins->head.opcode != OP_MOV ) return( FALSE );
            value = ins->operands[ 0 ];
        }
        // following will slide by block boundaries with greatest of ease
        ins = FindPreviousIns( ins );
    }
    return( value == ReturnValue );
}


static void DoOneParm( instruction *parm_ins, instruction *decl_ins, instruction *callins )
/********************************************************************
    Replace the parm_ins with a convert and a move designed to set up
    the parms into the appropriate temps so we can simply jump to the
    start of our function.
*/
{
    instruction         *first;
    instruction         *second;
    name                *tmp;
    name                *src;
    type_class_def      src_class;
    type_class_def      dst_class;

    src = parm_ins->operands[ 0 ];
    src_class = src->n.name_class;
    dst_class = decl_ins->result->n.name_class;
    tmp = AllocTemp( dst_class );
    first = MakeConvert( src, tmp, dst_class, src_class );
    second = MakeMove( tmp, decl_ins->result, dst_class );
    ReplIns( parm_ins, first );
    PrefixIns( callins, second );
}

static void DoTrans( block *blk, instruction *call_ins )
/*******************************************************
    Transform a recursive call into a jump to the
    start of our function.
*/
{
    instruction *ins;
    instruction *next;
    instruction *decl_ins;
    block       *target;
    int         i;
    block_edge  *edge;

    decl_ins = _PROC_LINK( CurrProc );
    for( ins = _TR_LINK( call_ins ); ins != NULL; ins = next ) {
        next = _TR_LINK( ins );
        DoOneParm( ins, decl_ins, call_ins );
        decl_ins = _TR_LINK( decl_ins );
    }

    // delete all instructions in this block from call instruction on
    for( ins = call_ins; ins->head.opcode != OP_BLOCK; ins = next ) {
        next = ins->head.next;
        FreeIns( ins );
    }

    // make blk jump to the block after the prologue
    target = HeadBlock->edge[ 0 ].destination;
    blk->class = ( blk->class | JUMP ) & ~( CONDITIONAL | RETURN | SELECT );

    // remove blk from the input lists of any blocks which it might have
    // previously gone to
    for( i = 0; i < blk->targets; i++ ) {
        edge = &blk->edge[ i ];
        RemoveInputEdge( edge );
    }

    blk->targets = 0;
    PointEdge( &blk->edge[ 0 ], target );
}

static bool SafePath( instruction *ins )
/***************************************
    Return TRUE if the path from the given ins (not OP_BLOCK)
    to the end of the block is safe to ignore for purposes of
    eliminating a call higher up the tree.
*/
{
    int         i;

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