unroll.c

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

*/
{
    block       *curr;
    block_edge  *edge;

    /* can't handle crap which isn't either a jump block or a conditional going to our head */
    for( edge = head->input_edges; edge != NULL; edge = edge->next_source ) {
        if( ( edge->source->class & ( JUMP | CONDITIONAL ) ) == EMPTY ) return( FALSE );
    }

    curr = head;
    while( curr != NULL ) {
        if( curr->class & LOOP_EXIT ) return( ExitEdges( head ) == 1 );
        if( curr->targets > 1 ) break;
        curr = curr->edge[ 0 ].destination;
        if( curr == head ) break;
    }
    return( FALSE );
}

extern  void    HoistCondition( block *head )
/********************************************
    We want to knock stuff off the top of a loop until the condition
    which controls exit from the loop is the first statement in the
    loop. To do this, we remove each instruction and append it to the
    prehead, while also appending a copy of the instruction to the
    loop butts. Note that this could violate the limit on instructions
    per block, but I'm not checking at the moment. You may only call
    this routine if the above function returned TRUE.
*/
{
    block_edge  *edge;
    block       *blk;
    instruction *ins, *next;

    for( edge = head->input_edges; edge != NULL; edge = edge->next_source ) {
        if( edge->source->targets > 1 ) {
            MakeNonConditional( edge->source, edge );
        }
    }

    for( blk = head; blk != NULL; blk = blk->edge[ 0 ].destination ) {
        ins = blk->ins.hd.next;
        while( ins->head.opcode != OP_BLOCK ) {
            if( _OpIsCondition( ins->head.opcode ) ) {
                RemoveIns( ins );
                SuffixIns( head->ins.hd.prev, ins );
                return;
            }
            for( edge = head->input_edges; edge != NULL; edge = edge->next_source ) {
                DupIns( edge->source->ins.hd.prev, ins, NULL, 0 );
            }
            next = ins->head.next;
            FreeIns( ins );
            ins = next;
        }
    }
    // should never reach here because we must have a conditional statement
    Zoiks( ZOIKS_113 );
}

#if 0
extern  void    HoistCondition( block **head, block *prehead )
/*************************************************************
    Munge the loop and prehead so that the condition is the first statement in
    the loop. This only works for a loop which has no conditional blocks in it
    other than the exit condition. To do this, we hoist each instruction from
    the head and make a copy appended to both the prehead and butt (my quaint
    notation for the block which jumps to the head and is not the prehead). We
    return TRUE if we were able to hoist the condition to the top, FALSE otherwise.
*/
{
    block       *butt;
    block_edge  *butt_edge;
    instruction *ins;
    instruction *next;
    instruction *butt_ins;
    instruction *prehead_ins;
    block       *blk;

    butt_edge = (*head)->input_edges;
    while( butt_edge != NULL ) {
        if( butt_edge->source != prehead ) break;
        butt_edge = butt_edge->next_source;
    }
    if( butt_edge == NULL ) return( FALSE );
    butt = MakeNonConditional( butt_edge->source, butt_edge );
    butt_ins = butt->ins.hd.prev;
    prehead_ins = prehead->ins.hd.prev;
    blk = *head;
    // it should be either a simple jump or our (1 and only) cond. exit
    if( ( blk->class & JUMP ) == EMPTY &&
        ( blk->class & CONDITIONAL ) == EMPTY ) return( FALSE );
    // the new head should have an input from prehead and one from the butt
    // any more and we have to bail out
    if( blk->inputs > 2 ) return( FALSE );
    ins = blk->ins.hd.next;
    // transfer all instructions to prehead/butt
    while( ins->head.opcode != OP_BLOCK ) {
        if( _OpIsCondition( ins->head.opcode ) ) {
            return( ( blk->class & LOOP_EXIT ) != EMPTY );
        }
        butt_ins = DupIns( butt_ins, ins, NULL, 0 );
        next = ins->head.next;
        RemoveIns( ins );
        SuffixIns( prehead_ins, ins );
        prehead_ins = ins;
        ins = next;
    }
    return( FALSE );
}
#endif

static  void    MarkLoopHeader( block *loop, block *header )
/***********************************************************
    Mark the entire loop as having header as it's loop_head.
*/
{
    while( loop != NULL ) {
        if( ( loop->class & LOOP_HEADER ) != EMPTY ) {
            loop->loop_head = PreHead->loop_head;
            if( ( PreHead->class & LOOP_HEADER ) != EMPTY ) {
                loop->loop_head = PreHead;
            }
            break;
        }
        loop->loop_head = header;
        loop = loop->u.loop;
    }
    Assert( loop != NULL );
}

/*
    Here's my candidate for weeny comment of the year - BBB Jan '94

    To unroll a nice loop which looks like:

        while( i < n ) {
            LoopBody();
            i += constant;
        }

    ( reps - 1 ) times ( so we get reps total repetitions of
    LoopBody inside our unrolled loop) we produce code which looks
    like the following:

    +---------------------------+
    |                           |
    |         PreHeader         |       Has "add n, -reps -> new_temp"
    |                           |       instruction added to it
    +---------------------------+
                  |
                 \|/
    +---------------------------+
    |                           |       If comparison is unsigned,
    |         SignCheck         |--+    we check to make sure that n and
    |                           |  |    ( n - reps ) have the same sign.
    +---------------------------+  |    ( If not - goto the normal loop below )
                  |                |
                 \|/               |
    +---------------------------+  |
    |                           |  |    This is something which looks like:
    |         BigCond           |--+     if ( i COMPARISON new_temp ) then
    |                           |  |            goto unrolled body
    +---------------------------+  |     else
                  |                |            goto littleCond below
                 \|/               |
    +---------------------------+  |
  \ |                           |  |    This is just reps copies of the
 +-+|         Unrolled Body     |  |    loop body with the conditional
 |/ |                           |  |    statement deleted of course.
 |  +---------------------------+  |
 |                |                |
 |               \|/               |
 |  +---------------------------+  |
 |  |                           |  |    A replication of the bigcond above -
 +--|         BigCond           |  |    as long as we are throwing code size
    |                           |  |    to the wind, might as well have fun
    +---------------------------+  |
                  |                |
                 \|/               |
    +---------------------------+/ |
    |                           |--+
    |         LittleCond        |\      What follows is just a guarded copy
    |                           |--+    of the original loop, to take care of
    +---------------------------+  |    any slop left over (n % reps iterations)
                  |                |
                 \|/               |
    +---------------------------+  |
  \ |                           |  |    The LittleCond blocks look like
 +-+|         LoopBody          |  |
 |/ |                           |  |            if i COMPARISON n then
 |  +---------------------------+  |                    goto LoopBody
 |                |                |            else
 |               \|/               |                    goto exit block
 |  +---------------------------+  |
 |  |                           |  |
 +--|         LittleCond        |  |
    |                           |  |
    +---------------------------+  |
                  |                |
                 \|/               |
    +---------------------------+  |
    |                           |/ |    We only unroll in this fun manner if
    |         Exit Block        |--+    we only had one conditional exit from the
    |                           |\      loop, so this guy is well-defined
    +---------------------------+
*/

static  void    MakeWorldGoAround( block *loop, loop_abstract *cleanup_copy, loop_condition *cond, signed_32 reps )
/******************************************************************************************************************
    This functions lays out the code as given above, creating and linking in condition
    blocks as needed. It then sorts the blocks into the given order, to make sure that nothing
    screws up our lovely flow of control.
*/
{
    name                *temp;
    instruction         *add;
    name                *modifier;
    type_class_def      comp_type;
    block               *new;
    instruction         *ins;
    unsigned_32         high_bit;

    comp_type = cond->compare_ins->type_class;
    temp = AllocTemp( comp_type );
    modifier = AllocS32Const( -1 * reps * cond->induction->plus );
    add = MakeBinary( OP_ADD, cond->invariant, modifier, temp, comp_type );
    SuffixPreHeader( add );

    // add a piece of code to check and make sure n and ( n - reps ) have the same sign
    if( cond->complete == FALSE && Signed[ comp_type ] != comp_type ) {
        new = MakeBlock( AskForNewLabel(), 2 );
        new->class = CONDITIONAL;
        new->loop_head = PreHead->loop_head;
        new->next_block = NULL;
        new->prev_block = NULL;
        new->input_edges = NULL;
        new->id = NO_BLOCK_ID;
        new->gen_id = PreHead->gen_id;
        new->ins.hd.line_num = 0;
        temp = AllocTemp( comp_type );
        ins = MakeBinary( OP_XOR, add->result, cond->invariant, temp, comp_type );
        SuffixIns( new->ins.hd.prev, ins );
        high_bit = 1 << ( ( 8 * TypeClassSize[ comp_type ] ) - 1 );
        ins = MakeCondition( OP_BIT_TEST_TRUE, temp, AllocS32Const( high_bit ), 0, 1, comp_type );
        SuffixIns( new->ins.hd.prev, ins );
        PointEdge( &new->edge[ 0 ], cleanup_copy->head );
        PointEdge( &new->edge[ 1 ], loop->loop_head );
        MoveEdge( &PreHead->edge[ 0 ], new );
        AddBlocks( PreHead, new );
    }

    // now munge Head so that it looks more like we want it to, and make a copy which we can
    // then attach to our butt
    ins = Head->ins.hd.prev;
    ins->head.opcode = cond->opcode;
    ins->operands[ 0 ] = cond->induction->name;
    ins->operands[ 1 ] = add->result;
    _SetBlockIndex( ins, 0, 1 );
    if( cond->complete ) {
        block_edge      *edge;

        // we have completely unrolled the loop - so behead it
        MarkHeaderEdges( loop, Head );
        RedirectHeaderEdges( loop, cond->exit_edge );
        edge = &Head->edge[ 0 ];
        if( ( edge->destination->class & IN_LOOP ) == EMPTY ) {
            edge = &Head->edge[ 1 ];
        }
        FreeIns( ins );
        MakeJumpBlock( Head, edge );
        MarkLoopHeader( loop, Head->loop_head );
        Head->class &= ~(LOOP_HEADER | ITERATIONS_KNOWN);
    } else {
        MoveEdge( &Head->edge[ 0 ], cond->loop_edge );
        if( cond->clean ) {
            MoveEdge( &Head->edge[ 1 ], cond->exit_edge );
        } else {
            MoveEdge( &Head->edge[ 1 ], cleanup_copy->head );
        }
        if( ( loop->class & JUMP ) != EMPTY ) {
            if( loop->edge[ 0 ].destination == Head ) {
                block   *blk;

                Head->class &= ~LOOP_HEADER;
                blk = DupBlock( Head );
                AddBlocks( loop, blk );
                MoveEdge( &loop->edge[ 0 ], blk );
                PointEdge( &blk->edge[ 0 ], Head->edge[ 0 ].destination );
                PointEdge( &blk->edge[ 1 ], Head->edge[ 1 ].destination );
                blk->u.loop = loop;
                while( 1 ) {
                    if( loop->u.loop == Head ) {
                        loop->u.loop = NULL;
                        loop->class |= LOOP_HEADER;
                        loop->loop_head = Head->loop_head;
                        MarkLoopHeader( blk, loop );
                        Head = loop;
                        break;
                    }
                    loop = loop->u.loop;
                }
            }
        }
    }
    // won't make copy now until I have this all worked out
    // the cleanup stuff should all be pointing in the right place by now
}

extern  bool    Hoisted( block *head, instruction *compare )
{
#if 0
    if( CanHoist( head ) ) {
        HoistCondition( head );
        return( TRUE );
    }
#else
    if( head->class & CONDITIONAL ) {
        if( _OpIsCondition( head->ins.hd.next->head.opcode ) &&
                compare == head->ins.hd.next ) return( TRUE );
    }
#endif
    return( FALSE );
}

extern  bool    UnRoll()
/***********************
    Unroll the given loop n times.
*/
{
    loop_condition      cond;
    block               *last;
    signed_32           unroll_count;
    bool                one_cond;
    loop_abstract       cleanup_copy;

    if( Head->class & DONT_UNROLL ) return( FALSE );
    unroll_count = UnrollCount( Loop, &cond.clean, &cond.complete );
    if( unroll_count <= 0 ) return( FALSE );
    AnalyseLoop( NULL, &one_cond, &cond.compare_ins, &cond.compare_block );
    if( one_cond &&
        Hoisted( Head, cond.compare_ins ) &&
        TractableCond( &cond ) ) {
        MarkHeaderEdges( Loop, Head );
        DupLoop( Loop, &cleanup_copy );
        RedirectHeaderEdges( cleanup_copy.tail, cleanup_copy.head );
        cleanup_copy.head->class |= LOOP_HEADER | DONT_UNROLL;
        MarkLoopHeader( cleanup_copy.tail, cleanup_copy.head );
        Head->class |= IGNORE;
        last = DoUnroll( Loop, unroll_count, FALSE );
        Head->class &= ~IGNORE;
        MarkLoopHeader( last, Head );
        MakeWorldGoAround( last, &cleanup_copy, &cond, unroll_count );
        cleanup_copy.head->loop_head = Head->loop_head;
        AddBlocks( last, cleanup_copy.head );
        UnMarkHeaderEdges( last );
        // MoveDownLoop( cond_blk );
    } else if( Head->unroll_count > 0 ) {
        last = DoUnroll( Loop, Head->unroll_count, FALSE );
        MarkLoopHeader( last, Head );
    }
    Head->class |= DONT_UNROLL;
    FixBlockIds();
    ClearCopyPtrs( Loop );
    return( TRUE );
}