flograph.c

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

                add = FALSE;
                for( ;; ) {
                    test = IntervalNo( edge->source, level - 1 );
                                                /* guess - internal edge*/
                    if( test != curr ) {
                                                /* guess - lower level head*/
                        test = test->parent;
                        if( test == NULL ) {
                            add = TRUE;
                            break;
                        }
                                                /* guess - no other predecessor*/
                        if( prev_int == NULL ) {
                            prev_int = test;
                        } else {
                                                /* guess - different predecessor*/
                            if( test != prev_int ) {
                                add = TRUE;
                                break;
                            }
                        }
                    }
                    edge = edge->next_source;
                    if( edge == NULL ) break;
                }
                if( add == FALSE ) {
                    curr->parent = prev_int;
                    prev_int->last_block = curr->last_block;
                    test = prev_int->sub_int;
                    while( test->next_sub_int != NULL ) {
                        test = test->next_sub_int;
                    }
                    test->next_sub_int = curr;
                } else {                        /* admit - create a new interval*/
                    NewInterval( blk, level );
                    num ++;
                }
            }
        }
        ++ level;
        if( num == prev_num || num == 1 ) break;
    }
    return( num == 1 );
}


static  void    ReorderBlocks( void )
/***********************************/
/*   Reorder blocks according to the interval ordering*/
/*   This allows each interval to be identified as a continuous range of blocks*/
{
    interval_def        *curr;
    block               *last_block;
    block               *next_block;

    last_block = HeadBlock;
    curr = HeadBlock->u.interval;
    for( ;; ) {
        for( ;; ) {
            if( curr->next_sub_int != NULL ) break;
            curr = curr->parent;
            if( curr == NULL )break;
            curr->last_block = last_block;
        }
        if( curr == NULL )break;
        curr = curr->next_sub_int;
        while( curr->level > 0 ) {
            curr = curr->sub_int;
        }
        next_block = curr->first_block;
        next_block->prev_block = last_block;
        last_block->next_block = next_block;
        next_block->id = last_block->id + 1;
        last_block = next_block;
    }
    last_block->next_block = NULL;
    BlockList = last_block;
}


static  void    EdgeLevels( void )
/********************************/
{
    block               *blk;
    block_edge          *edge;
    interval_def        *interval;
    block_num           id;

    blk = HeadBlock;
    for( ;; ) {
        edge = blk->input_edges;
        while( edge != NULL ) {
            id = edge->source->id;
            interval = blk->u.interval;
            for( ;; ) {
                if( id >= interval->first_block->id
                    && id <= interval->last_block->id ) break;
                edge->join_level = interval->level;
                interval = interval->parent;
                if( interval == NULL ) break;
            }
            edge = edge->next_source;
        }
        blk = blk->next_block;
        if( blk == NULL ) break;
    }
}


static  void    NewInterval( block *blk, int level )
/**************************************************/
{
    interval_def        *prev;
    interval_def        *new;

    prev = IntervalNo( blk, level - 1 );
    _Alloc( new, sizeof( interval_def ) );
    new->link = Intervals;
    Intervals = new;
    new->sub_int = prev;
    new->next_sub_int = NULL;
    new->level = level;
    new->parent = NULL;
    new->first_block = blk;
    new->last_block = blk;
    prev->parent = new;
}


static  void    NestingDepth( void )
/**********************************/
{
    block               *blk;
    int                 level;
    interval_def        *interval;
    block_edge          *edge;
    block               *target;
    int                 i;
    bool                change;

    interval = BlockList->u.interval->parent;
    while( interval->parent != NULL ) {
        level = interval->level - 1;
        blk = BlockList;               /* borrow 'next_block'*/
        for( ;; ) {                         /* identify all back edges at this level*/
            blk->next_block = NULL;
            i = blk->targets;
            while( --i >= 0 ) {
                edge = &blk->edge[ i ];
                target = edge->destination;
                if( target->id <= blk->id ) {     /* if back edge*/
                    if( edge->join_level == level ) {
                        blk->next_block = target;
                        if( blk->loop_head == NULL ) {
                            blk->loop_head = target;
                        }
                        blk->depth ++;
                        break;
                    }
                }
            }
            blk = blk->prev_block;
            if( blk == NULL ) break;
        }
        for( ;; ) {
            change = FALSE;
            blk = BlockList;
            for( ;; ) {
                if( blk->next_block == NULL ) {
                    i = blk->targets;
                    while( --i >= 0 ) {
                        edge = & blk->edge[ i ];
                        if( edge->join_level <= level ) {
                            target = edge->destination->next_block;
                            if( target != NULL ) {
                                blk->depth ++;
                                blk->next_block = target;  /* store head in node*/
                                if( blk->loop_head == NULL && blk != target ) {
                                    blk->loop_head = target;
                                }
                                target->class |= LOOP_HEADER;
                                change = TRUE;
                                break;
                            }
                        }
                    }
                }
                blk = blk->prev_block;
                if( blk == NULL ) break;
            }
            if( change == FALSE ) break;
        }
        interval = interval->parent;
    }

/*   Restore 'next_block'*/

    blk = BlockList;
    HeadBlock = NULL;
    for( ;; ) {
        blk->next_block = HeadBlock;
        HeadBlock = blk;
        blk = blk->prev_block;
        if( blk == NULL ) break;
    }
}

static  void    KillIntervals( void )
/***********************************/
{
    interval_def        *junk;
    block               *blk;

    while( Intervals != NULL ) {
        junk = Intervals;
        Intervals = Intervals->link;
        _Free( junk, sizeof( interval_def ) );
    }
    blk = HeadBlock;
    while( blk != NULL ) {
        blk->u.interval = NULL;
        blk = blk->next_block;
    }
}

static bool functionDegenerate;

static  bool    FlowDone( block *curr, void *parm )
/*************************************************/
{
    if( curr == (block *)parm ) {
        functionDegenerate = TRUE;
        return( FALSE );
    }
    return( TRUE );
}

static  bool    Degenerate( void )
/********************************/
{
    block       *blk;
    block_edge  *edge;

    for( blk = HeadBlock; blk != NULL; blk = blk->next_block ) {
        if( ( blk->class & LOOP_HEADER ) == EMPTY ) continue;
        for( edge = blk->input_edges; edge != NULL; edge = edge->next_source ) {
            if( ( edge->source->class & SELECT ) != EMPTY ) {
                functionDegenerate = FALSE;
                FloodForward( edge->source, FlowDone, blk );
                if( functionDegenerate ) return( TRUE );
            }
        }
    }
    return( FALSE );
}

extern  void    MakeFlowGraph( void )
/***********************************/
{
    Irreducable();
    if( CurrProc->state.attr & ROUTINE_WANTS_DEBUGGING ) {
        return;
    }
    NoBlocksToSelf();
    Intervals = NULL;
    if( HeadBlock != NULL ) {
        if( !DepthFirstSearch() ) {
            Irreducable();
            RestoreLinks();
            Renumber();
            return;
        }
        FixLinks();
        if( FindIntervals() ) {
            ReorderBlocks();
            EdgeLevels();
            NestingDepth();
            if( Degenerate() ) {
                Irreducable();
            }
       } else {
            /* irreducable flow graph. repair prev_block links*/
            Irreducable();
        }
        KillIntervals();
        ReturnsToBottom();
        Renumber();
    }
}