unroll.c

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

        if( op->i.index == orig ) {
            *pop = ScaleIndex( new, op->i.base,
                               op->i.constant,
                               op->n.name_class, op->n.size,
                               op->i.scale, op->i.index_flags );
            return( TRUE );
        } else if( op->i.base == orig ) {
            *pop = ScaleIndex( op->i.index, new, op->i.constant,
                               op->n.name_class, op->n.size,
                               op->i.scale, op->i.index_flags );
        }
        break;
    case N_TEMP:
        op = DeAlias( op );
        if( op == orig ) {
            offset = (*pop)->v.offset - op->v.offset;
            *pop = TempOffset( new, offset, (*pop)->n.name_class );
            return( TRUE );
        }
        break;
    default:
        if( op == orig ) {
            *pop = new;
            return( TRUE );
        }
    }
    return( FALSE );
}

static  void    ReplaceInductionVars( block *loop, instruction *ins_list,
                                       signed_32 scale )
/*******************************************************
    Replace all occurrences of an induction var in the loop with a new
    temp, and add an instruction to initialize that temp onto the ins_list.
    By the time we get here, everything should be either dead or a basic
    induction var. Scale should be the ordinal of the iteration we are on,
    starting at 1 and incrementing each time this is called on a copy of a
    loop.
*/
{
    induction   *ind;
    name        *temp;
    name        *var;
    instruction *ins;
    instruction *new_ins;
    block       *blk;
    int         i;
    signed_32   adjust;

    for( ind = IndVarList; ind != NULL; ind = ind->next ) {
        if( _IsV( ind, IV_DEAD ) ) continue;
        var = ind->name;
        temp = AllocTemp( var->n.name_class );
        adjust = scale * ind->plus;
        new_ins = MakeBinary( OP_ADD, var, AllocS32Const( adjust ),
                            temp, temp->n.name_class );
        for( blk = loop; blk != NULL; blk = blk->u.loop ) {
            ins = blk->ins.hd.next;
            for( ; ins->head.opcode != OP_BLOCK; ins = ins->head.next ) {
                ReplaceName( &ins->result, var, temp );
                for( i = 0; i < ins->num_operands; i++ ) {
                    ReplaceName( &ins->operands[i], var, temp );
                }
            }
        }
        /* have to add this after we run the list replacing vars */
        PrefixIns( ins_list, new_ins );
        new_ins = MakeMove( temp, var, temp->n.name_class );
        SuffixIns( loop->ins.hd.prev, new_ins );
    }
}

extern  void    DumpPtr( void * );
extern  void    DumpString( char * );
extern  void    DumpNL( void );

extern  void    DumpLoop( block *loop )
{
    block_edge  *edge;
    block_num   i;

    DumpString( "Block\t\tBlock->u.loop\tBlock->loop_head" );
    DumpNL();
    DumpNL();
    while( loop != NULL ) {
        DumpPtr( loop );
        DumpString( "\t\t" );
        DumpPtr( loop->u.loop );
        DumpString( "\t\t" );
        DumpPtr( loop->loop_head );
        DumpNL();
        DumpString( "\tInputs: " );
        for( edge = loop->input_edges; edge != NULL; edge = edge->next_source ) {
            DumpPtr( edge->source );
            DumpString( " " );
        }
        DumpNL();
        DumpString( "\tDest: " );
        for( edge = &loop->edge[ 0 ], i = 0; i < loop->targets; i++, edge++ ) {
            DumpPtr( edge->destination );
            DumpString( " " );
        }
        DumpNL();
        loop = loop->u.loop;
    }
}
#endif

static  void    LinkBlocks( block *first, block *second )
{
    first->next_block = second;
    second->prev_block = first;
}

static  void    ChainTwoLoops( loop_abstract *first, loop_abstract *last )
/*************************************************************************
    Given two detached copies of a loop, link their blocks
    together and join them via block->u.loop.
*/
{
    LinkBlocks( first->tail, last->head );
    last->head->u.loop = first->tail;
}

static  block   *DoUnroll( block *tail, signed_32 reps, bool replace_vars )
/**************************************************************************
    Unroll the given loop (this is the tail block, and loop is connected
    through blk->u.loop to the head, in which blk->u.loop == NULL) reps
    times (there will be reps + 1 copies of the loop body) and replace induction
    vars with new temps if replace_vars == TRUE
    All of the copies made will be connected through blk->u.loop, and a
    pointer to the tail of the new super-loop will be returned.
*/
{
    loop_abstract       *new_loops;
    loop_abstract       *curr;
    loop_abstract       *next;
    loop_abstract       *first;
    loop_abstract       *last;
    block               *next_block;
    signed_32           i;
    signed_32           size;

    replace_vars = replace_vars;
    size = sizeof( loop_abstract ) * reps;

    // allocate an array of these abstract loop thingies
    _Alloc( new_loops, size );
    first = &new_loops[ 0 ];
    last = &new_loops[ reps - 1 ];

    // create the actual copies - they will be independant of each other
    for( i = 0; i < reps; i++ ) {
        curr = &new_loops[ i ];
        DupLoop( tail, curr );
    }

    // want last copy to jump to original loop - we do it here because
    // the last copy is going to get linked (via blk->u.loop) into the
    // entire loop after the next pass over the array of copies
    RedirectHeaderEdges( last->tail, Head );

    // also, we make the original loop jump to the first of the duplicates
    RedirectHeaderEdges( tail, first->head );

    // now we need to make each of the loops chain to the next chap in line
    // we also take this opportunity to link the various copies together via
    // blk->next_block and blk->u.loop
    for( i = 1; i < reps; i++ ) {
        curr = &new_loops[ i - 1 ];
        next = &new_loops[   i   ];
        RedirectHeaderEdges( curr->tail, next->head );
        ChainTwoLoops( curr, next );
    }

    // now we just have to ram the entire thing into the block list
    // for this function and link them to the original via blk->u.loop
    next_block = tail->next_block;
    LinkBlocks( tail, first->head );
    LinkBlocks( last->tail, next_block );
    first->head->u.loop = tail;

    next_block = last->tail;
    _Free( new_loops, size );

    // and return the tail of the new super-loop
    return( next_block );
}

static  bool    TractableCond( loop_condition *cond )
/****************************************************
    To be a nice conditional exit (one we can munge) we need a comparison
    between an induction variable and a loop-invariant expression. If these
    conditions are present, we fill in the fields and return TRUE. If we
    return FALSE, the values of cond are guaranteed to be irrelevant junk.
*/
{
    bool        ok;
    induction   *tmp;
    signed_32   plus;
    bool        exit_true;
    byte        opcode;
    name        *n;
    instruction *ins;
    block       *blk;


    ins = cond->compare_ins;
    blk = cond->compare_block;
    ok = FALSE;
    exit_true = FALSE;
    MarkInvariants();
    if( !InvariantOp( ins->operands[ 1 ] ) ) {
        n = ins->operands[ 0 ];
        ins->operands[ 0 ] = ins->operands[ 1 ];
        ins->operands[ 1 ] = n;
        RevCond( ins );
    }
    if( InvariantOp( ins->operands[ 1 ] ) ) {
        tmp = FindIndVar( ins->operands[ 0 ] );
        if( tmp != NULL ) {
            cond->induction = tmp;
            cond->invariant = ins->operands[ 1 ];
            ok = TRUE;
        }
    }
    UnMarkInvariants();
    if( !ok ) return( FALSE );
    if( _IsV( cond->induction, IV_DEAD ) ) return( FALSE );
    if( ( blk->edge[ 0 ].destination->class & IN_LOOP ) != EMPTY ) {
        cond->exit_edge = blk->edge[ 1 ].destination;
        cond->loop_edge = blk->edge[ 0 ].destination;
        if( _TrueIndex( ins ) == 1 ) {
            // want loop to continue executing if condition TRUE
            FlipCond( ins );
            _SetBlockIndex( ins, 0, 1 );
        }
    } else {
        cond->exit_edge = blk->edge[ 0 ].destination;
        cond->loop_edge = blk->edge[ 1 ].destination;
        if( _TrueIndex( ins ) == 0 ) {
            // want loop to continue executing if condition TRUE
            FlipCond( ins );
            _SetBlockIndex( ins, 1, 0 );
        }
    }
    plus = cond->induction->plus;
    opcode = ins->head.opcode;
    switch( opcode ) {
    case OP_CMP_NOT_EQUAL:
        if( plus < 0 ) {
            cond->opcode = OP_CMP_GREATER;
        } else {
            cond->opcode = OP_CMP_LESS;
        }
        break;
    case OP_CMP_GREATER:
    case OP_CMP_GREATER_EQUAL:
        cond->opcode = opcode;
        if( plus >= 0 ) ok = FALSE;
        break;
    case OP_CMP_LESS:
    case OP_CMP_LESS_EQUAL:
        cond->opcode = opcode;
        if( plus <= 0 ) ok = FALSE;
        break;
    case OP_CMP_EQUAL:
    case OP_BIT_TEST_TRUE:
    case OP_BIT_TEST_FALSE:
        ok = FALSE;
        break;
    default:
        Zoiks( ZOIKS_113 );
    }
    return( ok );
}

extern  block   *AddBlocks( block *insertion_point, block *block_list )
/**********************************************************************
    Insert the list of blocks after the given insertion point.
*/
{
    block       *last;

    last = block_list;
    while( last->next_block != NULL ) last = last->next_block;
    last->next_block = insertion_point->next_block;
    if( last->next_block != NULL ) {
        last->next_block->prev_block = last;
    }
    block_list->prev_block = insertion_point;
    insertion_point->next_block = block_list;
    return( last );
}

extern  void    RemoveIns( instruction *ins )
/********************************************
    Remove the ins from the instruction ring. Does not take
    into account live info or anything else like that.
*/
{
    instruction *next;
    instruction *prev;

    next = ins->head.next;
    prev = ins->head.prev;
    next->head.prev = prev;
    prev->head.next = next;
    ins->head.next = NULL;
    ins->head.prev = NULL;
}

static  block   *MakeNonConditional( block *butt, block_edge *edge )
/*******************************************************************
    If butt is conditional, create a new block which is
    in between the conditional block and the head of the
    current loop. We need a nonconditional block so that
    we can append instructions to it when hoisting the
    condition to the top of the loop.
*/
{
    block       *blk;

    if( ( butt->class & CONDITIONAL ) != EMPTY ) {
        blk = MakeBlock( AskForNewLabel(), 1 );
        blk->class = JUMP | IN_LOOP;
        blk->id = NO_BLOCK_ID;
        blk->gen_id = butt->gen_id;
        blk->ins.hd.line_num = 0;
        blk->next_block = butt->next_block;
        if( blk->next_block != NULL ) {
            blk->next_block->prev_block = blk;
        }
        blk->prev_block = butt;
        butt->next_block = blk;
        blk->loop_head = Head;
        PointEdge( &blk->edge[ 0 ], edge->destination );
        MoveEdge( edge, blk );
        UnMarkLoop();
        MarkLoop();
        return( blk );
    }
    return( butt );
}

static  int     ExitEdges( block *head )
/***************************************
    Return the number of edges in the loop with the given head which
    exit the loop.
*/
{
    int         count;
    block       *blk;

    count = 0;
    for( blk = HeadBlock; blk != NULL; blk = blk->next_block ) {
        if( blk->loop_head == head || blk == head ) {
            if( blk->class & LOOP_EXIT ) count++;
        }
    }
    return( count );
}

extern  bool    CanHoist( block *head )
/**************************************
    Figure out if we can hoist the condition of a loop to the top of
    the loop. Basically, we can do this as long as there are no
    if's between the head and the comparison instruction.