unroll.c

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

/****************************************************************************
*
*                            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:  Loop unrolling optimizations. Contains lots of obsolete
*               and/or nonfunctional code. Currently doesn't work at all
*               because other optimizations munge loops into a form this
*               module doesn't expect.
*
****************************************************************************/


#include <assert.h>
#include "standard.h"
#include "coderep.h"
#include "indvars.h"
#include "opcodes.h"
#include "sysmacro.h"
#include "cfloat.h"
#include "model.h"
#include "stackok.h"
#include "zoiks.h"
#include "cgaux.h"

extern  block           *MakeBlock(label_handle,block_num);
extern  instruction     *DupInstrs(instruction*,instruction*,instruction*,induction*,signed_32);
extern  label_handle    AskForNewLabel( void );
extern  void            MoveEdge(block_edge*,block*);
extern  void            PointEdge(block_edge*,block*);
extern  bool            AnalyseLoop(induction*,bool*,instruction**,block**);
extern  name            *DeAlias(name*);
extern  name            *TempOffset(name *,type_length ,type_class_def );
extern  name            *AllocTemp(type_class_def );
extern  name            *SAllocIndex(name *,name *,type_length ,type_class_def ,type_length );
extern  instruction     *MakeBinary(opcode_defs ,name *,name *,name *,type_class_def );
extern  instruction     *MakeCondition(opcode_defs ,name *,name *,int,int,type_class_def );
extern  name            *AllocS32Const(signed_32 );
extern  void            SuffixIns(instruction *,instruction *);
extern  name            *ScaleIndex(name *,name *,type_length ,type_class_def ,type_length ,int ,i_flags );
extern  void            PrefixIns(instruction *,instruction *);
extern  bool            InvariantOp(name *);
extern  induction       *FindIndVar( name *);
extern  void            RemoveInputEdge( block_edge * );
extern  void            SuffixPreHeader( instruction * );
extern  block           *NewBlock( label_handle, bool );
extern  void            MarkLoop( void );
extern  void            UnMarkLoop( void );
extern  void            MarkInvariants( void );
extern  void            UnMarkInvariants( void );
extern  instruction     *MakeMove( name *, name *, type_class_def );
extern  instruction     *DupIns( instruction *, instruction *, name *, signed_32 );
extern  void            RemoveBlock( block * );
extern  void            FlipCond( instruction * );
extern  void            RevCond( instruction * );
extern  int             CountIns( block *);
extern  void            MoveDownLoop( block * );
extern  block           *ReGenBlock( block *, label_handle );
extern  void            MakeJumpBlock( block *, block_edge * );
extern  void            FreeIns( instruction * );
extern  void            URBlip( void );

extern type_class_def   Signed[];
extern block            *HeadBlock;
extern block            *PreHead;
extern block            *Head;
extern name             *Names[];
extern byte             OptForSize;
extern induction        *IndVarList;
extern block            *Loop;
extern type_length      TypeClassSize[];

#define Assert( x )     { if( !(x) ) Zoiks( ZOIKS_113 ); }

typedef struct loop_condition {
    byte        opcode;
    induction   *induction;
    name        *invariant;
    block       *exit_edge;
    block       *loop_edge;
    instruction *compare_ins;
    block       *compare_block;
    bool        clean;                  // do we need something to clean up after us?
    bool        complete;               // did we unroll the loop completely
} loop_condition;


extern  void    FixBlockIds( void )
/**********************************
    Fix up the block_id field of temps.
*/
{
    block_num   id;
    block       *blk;
    name        *temp;

    id = 0;
    for( temp = Names[ N_TEMP ]; temp != NULL; temp = temp->n.next_name ) {
        if( temp->t.u.block_id == NO_BLOCK_ID ) {
            temp->t.temp_flags |= VISITED;
        } else {
            temp->t.temp_flags &= ~VISITED;
        }
    }
    blk = HeadBlock;
    while( blk != NULL ) {
        ++id;
        for( temp = Names[ N_TEMP ]; temp != NULL; temp = temp->n.next_name ) {
            if( temp->t.temp_flags & VISITED ) continue;
            if( temp->t.u.block_id != blk->id ) continue;
            temp->t.temp_flags |= VISITED;
            temp->t.u.block_id = id;
        }
        blk->id = id;
        blk = blk->next_block;
    }
    for( temp = Names[ N_TEMP ]; temp != NULL; temp = temp->n.next_name ) {
        temp->t.temp_flags &= ~VISITED;
    }
}

extern  block   *DupBlock( block *blk )
/**************************************
    Create a copy of the given block and all the instructions in it.
    This copy is not linked in anywhere. It has room for as many edges
    as blk has targets, but the number of targets is set to 0. There
    are no inputs to this block. The block class is the same as blk.
*/
{
    block       *copy;

    copy = MakeBlock( AskForNewLabel(), blk->targets );
    copy->class = ( blk->class & ~( LOOP_HEADER | ITERATIONS_KNOWN ) );
    copy->id = NO_BLOCK_ID;
    copy->depth = blk->depth;
    copy->gen_id = blk->gen_id;
    copy->ins.hd.line_num = 0;
    copy->next_block = NULL;
    copy->prev_block = NULL;
    DupInstrs( (instruction *)&copy->ins,
                blk->ins.hd.next, blk->ins.hd.prev, NULL, 0 );
    return( copy );
}

#define COPY_PTR( x )   (x)->v.alter_ego

static  void    ClearCopyPtrs( block *tail )
/******************************************/
{
    block       *blk;

    blk = tail;
    while( blk != NULL ) {
        COPY_PTR( blk ) = NULL;
        blk = blk->u.loop;
    }
}

typedef struct  loop_abstract {
    block       *head;
    block       *tail;
} loop_abstract;

static  block   *DupLoop( block *tail, loop_abstract *loop )
/***********************************************************
    Make a copy of the given loop and return a pointer to its head.
    The blocks in the new loop will be linked together via blk->next_block,
    but they will not be linked into the function blocks. Edges going to
    blocks not in the loop will go to the same edges, others will go to the
    corresponding edge in the new loop.
*/
{
    block       *blk;
    block       *copy;
    block       *prev;
    block       *dest;
    block_num   i;
    block_edge  *edge;
    block       *old_header;

    URBlip();

    prev = copy = NULL;
    ClearCopyPtrs( tail );

    // make a copy of each of the blocks in the original loop
    for( blk = tail; blk != NULL; blk = blk->u.loop ) {
        if( ( blk->class & IGNORE ) != EMPTY ) continue;
        copy = DupBlock( blk );
        COPY_PTR( blk ) = copy;
        COPY_PTR( copy ) = blk;
        if( prev != NULL ) { // link this copy into the list of copied blocks
            prev->u.loop = copy;
            copy->next_block = prev;
            prev->prev_block = copy;
        } else {
            loop->tail = copy;
        }
        prev = copy;
    }
    loop->head = copy;
    if( copy != NULL ) {
        copy->u.loop = NULL; // terminate the list held in blk->u.loop
    }

    // now link the blocks together - for each edge, we point the
    // edge in the corresponding block to the same block if it is in the
    // loop, otherwise we use the copy of the block.
    old_header = Head;
    for( blk = tail; blk != NULL; blk = blk->u.loop ) {
        if( ( blk->class & IGNORE ) != EMPTY ) continue;
        copy = COPY_PTR( blk );
        for( i = 0; i < blk->targets; i++ ) {
            dest = blk->edge[ i ].destination;
            if( ( dest->class & IN_LOOP ) != EMPTY ) {
                if( dest != old_header ) {
                    dest = COPY_PTR( dest );
                }
            }
            edge = &copy->edge[ i ];
            PointEdge( edge, dest );
            edge->flags &= ~ONE_ITER_EXIT;
            if( dest == old_header ) {
                edge->flags |= DEST_IS_HEADER;
            }
        }
    }
    return( COPY_PTR( tail ) );
}

static  void    MarkHeaderEdges( block *loop, block *head )
/**********************************************************
    Mark every edge in the loop which points to the given
    header as DEST_IS_HEADER.
*/
{
    block       *blk;
    block_num   i;
    block_edge  *edge;

    for( blk = loop; blk != NULL; blk = blk->u.loop ) {
        for( i = 0; i < blk->targets; i++ ) {
            edge = &blk->edge[ i ];
            if( edge->destination == head ) {
                edge->flags |= DEST_IS_HEADER;
            }
        }
    }
}

static  void    RedirectHeaderEdges( block *loop, block *new_head )
/******************************************************************
    Run through the given loop replacing edges which point to the
    loop head with edges which point to new_head.
*/
{
    block       *blk;
    block_num   i;
    block_edge  *edge;

    for( blk = loop; blk != NULL; blk = blk->u.loop ) {
        for( i = 0; i < blk->targets; i++ ) {
            edge = &blk->edge[ i ];
            if( edge->flags & DEST_IS_HEADER ) {
                MoveEdge( edge, new_head );
                edge->source = blk;
            }
        }
    }
}

static  void    UnMarkHeaderEdges( block *loop )
/**********************************************/
{
    block       *blk;
    block_num   i;
    block_edge  *edge;

    for( blk = loop; blk != NULL; blk = blk->u.loop ) {
        for( i = 0; i < blk->targets; i++ ) {
            edge = &blk->edge[ i ];
            edge->flags &= ~DEST_IS_HEADER;
        }
    }
}


#define MAX_CODE_SIZE   0x20
#define UNROLL_MAX      0x20

static  signed_32       UnrollCount( block *loop_tail, bool *clean, bool *complete )
/***********************************************************************************
    Figure out how many times we want to unroll the given loop.
*/
{
    signed_32   num_ins;
    signed_32   unroll_count;
    block       *blk;

    // check out this awesome heuristic...
    *complete = FALSE;
    *clean = FALSE;
    unroll_count = Head->unroll_count;
    if( unroll_count == 0 ) {
        if( _IsntModel( LOOP_UNROLLING ) ) return( 0 );
        if( OptForSize != 0 ) return( FALSE );
        num_ins = 0;
        blk = loop_tail;
        while( blk != NULL ) {
            if( blk->class & SELECT ) return( 0 );
            num_ins += CountIns( blk );
            blk = blk->u.loop;
        }
        if( Head->class & ITERATIONS_KNOWN ) {
            unroll_count = MAX_CODE_SIZE / num_ins;
            while( unroll_count ) {
                if( Head->iterations % ( unroll_count + 1 ) == 0 ) {
                    break;
                }
                unroll_count -= 1;
            }
            if( unroll_count >= ( Head->iterations - 1 ) ) {
                unroll_count = Head->iterations - 1;
                *complete = TRUE;
            }
        } else {
            // don't bother
            // unroll_count = MAX_CODE_SIZE / num_ins;
            // if( unroll_count > UNROLL_MAX ) unroll_count = UNROLL_MAX;
        }
    }
    return( unroll_count );
}

#if 0
static  bool    ReplaceName( name **pop, name *orig, name *new )
/***************************************************************
    Replace all occurrences of orig in *pop with new and return the new name.
*/
{
    name        *op;
    type_length offset;

    op = *pop;
    if( op == NULL ) return( FALSE );
    switch( op->n.class ) {
    case N_INDEXED: