loopopts.c

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

/****************************************************************************
*
*                            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 optimizations.
*
****************************************************************************/


#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 "i64.h"
#include "feprotos.h"


typedef struct block_list {
        block                   *blk;
        struct block_list       *next;
} block_list;

/* target specific. Can a pointer get anywhere near the boundary pointer values?*/
/* For 8086, yes. 0000 and FFFF are quite possible as pointer values*/

#define _POINTER_GETS_NEAR_BOUNDS 1
#define BLOCK_WILL_EXECUTE      BLOCK_MARKED

extern    block                 *HeadBlock;
extern    name                  *Names[];
extern    type_class_def        Unsigned[];
extern    type_length           TypeClassSize[];

extern  name            *AllocS64Const(signed_32,signed_32);
extern  bool            ReDefinedBy(instruction*,name*);
extern  int             GetLog2(unsigned_32);
extern  instruction     *MakeBinary(opcode_defs,name*,name*,name*,type_class_def);
extern  instruction     *MakeNop(void);
extern  instruction     *MakeMove(name*,name*,type_class_def);
extern  instruction     *MakeUnary(opcode_defs,name*,name*,type_class_def);
extern  instruction     *MakeConvert(name*,name*,type_class_def,type_class_def);
extern  instruction     *MakeCondition(opcode_defs,name*,name*,int,int,type_class_def);
extern  name            *AllocTemp(type_class_def);
extern  name            *AllocConst(pointer);
extern  name            *AllocS32Const(signed_32);
extern  block           *NewBlock(label_handle,bool);
extern  label_handle    AskForNewLabel(void);
extern  bool            SameThing(name*,name*);
extern  void            RevCond(instruction*);
extern  void            PrefixIns(instruction*,instruction*);
extern  void            PrefixInsRenum(instruction*,instruction*,bool);
extern  void            SuffixIns(instruction*,instruction*);
extern  void            ReplIns(instruction*,instruction*);
extern  void            FreeIns(instruction*);
extern  bool            LoopInsDead(void);
extern  bool            TempsOverlap(name*,name*);
extern  bool            RepOp(name**,name*,name*);
extern  void            FlipCond(instruction*);
extern  name            *DeAlias(name*);
extern  void            LPBlip(void);
extern  void            RemoveInputEdge(block_edge*);
extern  block           *ReGenBlock(block*,label_handle);
extern  void            FPNotStack(name*);
extern  bool            NameIsConstant(name*);
extern  void            ConstToTemp(block*,block*,block*(*)(block*));
extern  bool            SideEffect(instruction*);
extern  name            *ScaleIndex(name*,name*,type_length,type_class_def,type_length,int,i_flags);
extern  int             CountIns(block*);
extern  instruction     *NewIns(int);
extern  byte            *Copy(void*,void*,uint);
extern  void            PropIndexes(block*);
extern  void            FixBlockIds(void);
extern  bool            UnRoll(void);
extern  void            MoveEdge(block_edge*,block*);
extern  void            PointEdge(block_edge*,block*);


static    int           NumIndVars;
static    bool          LoopProtected;
static    bool          MemChangedInLoop;
extern    byte          OptForSize;
extern    bool          BlockByBlock;

block                   *Head;
block                   *PreHead;
induction               *IndVarList;
block                   *Loop;

extern  void    InitIndVars( void )
/**********************************
    Initialize for induction variable processing
*/
{
    IndVarList = NULL;                 /* initialize */
}

static  interval_depth  MaxDepth( void )
/***************************************
    return the depth of the deepest nested loop in the procedure
*/
{
    interval_depth      depth;
    block               *blk;

    blk = HeadBlock;
    depth = 0;
    while( blk != NULL ) {
        if( blk->depth > depth ) {
            depth = blk->depth;
        }
        blk = blk->next_block;
    }
    return( depth );
}


static  void    ReplaceAllOccurences( name *of, name *with )
/***********************************************************
    Replace all occurences of "of" with "with" in the program.
*/
{
    block       *blk;
    instruction *ins;
    int         i;

    blk = HeadBlock;
    while( blk != NULL ) {
        ins = blk->ins.hd.next;
        while( ins->head.opcode != OP_BLOCK ) {
            i = ins->num_operands;
            while( --i >= 0 ) {
                RepOp( &ins->operands[ i ], of, with );
            }
            if( ins->result != NULL ) {
                RepOp( &ins->result, of, with );
            }
            ins = ins->head.next;
        }
        blk = blk->next_block;
    }
}


static  bool    InLoop( block *blk )
/***********************************
    return TRUE if blk is in the loop defined by Head.
*/
{
    if( blk == Head ) return( TRUE );
    while( blk != NULL ) {
        if( blk->loop_head == Head ) return( TRUE );
        blk = blk->loop_head;
    }
    return( FALSE );
}


extern  block   *AddPreBlock( block *postblk )
/*********************************************
    There is no preheader for this loop (loop has no initialization) so
    add a block right in front of the loop header and move any branch
    that goes from outside the loop to the header, go through the
    preheader first.
*/
{
    block_edge  *edge;
    block       *preblk;

    preblk = NewBlock( postblk->label, FALSE );
    /* set up new block to look like it was generated after postblk*/
    preblk->class = JUMP;
    preblk->id = NO_BLOCK_ID;
    preblk->gen_id = postblk->gen_id;
    preblk->ins.hd.line_num = postblk->ins.hd.line_num;
    postblk->ins.hd.line_num = 0;
    preblk->loop_head = postblk->loop_head; /**/
    preblk->depth = postblk->depth;
    if( ( postblk->class & LOOP_HEADER ) != EMPTY ) {
        // we don't always add this block before a loop header
        // for instance, in the floating point scheduling stuff
        // we use this routine to add a safe 'decache' block
        // after a loop  BBB - Oct 14, 1997
        preblk->depth -= 1;
    }
    preblk->next_block = postblk;
    preblk->prev_block = postblk->prev_block;
    postblk->prev_block = preblk;
    if( preblk->prev_block != NULL ) {
        preblk->prev_block->next_block = preblk;
    }
    preblk->input_edges = NULL;
    preblk->inputs = 0;
    /* make preblk go to postblk*/
    preblk->targets++;
    edge = &preblk->edge[ 0 ];
    edge->destination = postblk;
    edge->source = preblk;
    edge->flags = SOURCE_IS_PREHEADER | DEST_IS_BLOCK;
    edge->next_source = postblk->input_edges;
    postblk->input_edges = edge;
    postblk->inputs++;
    postblk->label = AskForNewLabel();
    FixBlockIds();
    return( preblk );
}


static  bool    IsPreHeader( block *test ) {
/*******************************************
    return TRUE if block "test" will serve as a preheader for "Loop".  A
    preheader must branch directly to the loop head, and no other block
    that is not in the loop may branch into the loop.
*/

    int         i;
    block       *other;

    /* check that test only goes to the loop head*/
    if( test->targets != 1 ) return( FALSE );
    if( test->edge[ 0 ].destination != Head ) return( FALSE );
    if( ( test->class & IN_LOOP ) != EMPTY ) return( FALSE );
    /* check that no other block outside the loop branches into the loop*/
    other = HeadBlock;
    while( other != NULL ) {
        if( other != test && ( other->class & IN_LOOP ) == EMPTY ) {
            i = other->targets;
            while( --i >= 0 ) {
                if( other->edge[ i ].destination->class & IN_LOOP )
                    return( FALSE );
            }
        }
        other = other->next_block;
    }
    test->edge[ 0 ].flags |= SOURCE_IS_PREHEADER;
    return( TRUE );
}


static  block   *FindPreHeader( void )
/*************************************
    See if there is a basic block that will suffice as a pre-header for
    "Loop".
*/
{
    block       *preheader;
    block_edge  *edge;

    edge = Head->input_edges;
    for( ;; ) {
        if( edge == NULL ) { /* maybe there is a 'user defined' preheader*/
            preheader = HeadBlock;
            while( preheader != NULL ) {
                if( IsPreHeader( preheader ) ) return( preheader );
                preheader = preheader->next_block;
            }
            return( NULL );
        }
        if( edge->flags & SOURCE_IS_PREHEADER ) break;
        edge = edge->next_source;
    }
    return( edge->source );
}


static  void    PreHeader( void )
/********************************
    Make sure that "Loop" has a preheader "PreHead"
*/
{
    block_edge  *edge;
    block_edge  *next;

    PreHead = FindPreHeader();
    if( PreHead == NULL ) {
        PreHead = AddPreBlock( Head );
        edge = Head->input_edges;
        while( edge != NULL ) {
            next = edge->next_source;
            if( edge->source != PreHead &&
                ( edge->source->class & IN_LOOP ) == EMPTY ) {
                MoveEdge( edge, PreHead );
            }
            edge = next;
        }
    }
}


extern  void    MarkLoop( void )
/*******************************
    Mark the current loop (defined by Head) as IN_LOOP.  Also mark any
    blocks in the loop containing a branch out of the loop as LOOP_EXIT.
*/
{
    block       *other_blk;
    int         targets;
    block_edge  *edge;

    Loop = NULL;
    other_blk = HeadBlock;
    while( other_blk != NULL ) {
        if( InLoop( other_blk ) ) {
            other_blk->class |= IN_LOOP;
            other_blk->u.loop = Loop;
            Loop = other_blk;
        }
        other_blk = other_blk->next_block;
    }
    other_blk = Loop;
    while( other_blk != NULL ) {
        targets = other_blk->targets;
        edge = &other_blk->edge[ 0 ];
        while( --targets >= 0 ) {
            if( ( edge->destination->class & IN_LOOP ) == EMPTY ) {
                other_blk->class |= LOOP_EXIT;
            }
            ++edge;
        }
        other_blk = other_blk->u.loop;
    }
    PreHeader();
}


extern  void    UnMarkLoop( void )
/*********************************
    Turn off the loop marking bits for the current loop.
*/
{
    block       *blk;

    blk = HeadBlock;
    while( blk != NULL ) {
        blk->class &= ~( IN_LOOP | LOOP_EXIT );
        blk->u.loop = NULL;
        blk = blk->next_block;
    }
}

extern  block   *NextInLoop( block *blk )
/***************************************/
{
    return( blk->u.loop );
}


extern  block   *NextInProg( block *blk )
/***************************************/
{
    return( blk->next_block );
}


extern  void            MakeJumpBlock( block *cond_blk, block_edge *exit_edge )
/******************************************************************************
    Turn the loop condition exit block into one that just transfers out
    of the loop.
*/
{
    block_edge  *edge;

    RemoveInputEdge( &cond_blk->edge[ 0 ] );
    RemoveInputEdge( &cond_blk->edge[ 1 ] );
    cond_blk->class &= ~CONDITIONAL;
    cond_blk->class |= JUMP;
    cond_blk->targets = 1;
    edge = &cond_blk->edge[0];
    edge->flags = exit_edge->flags;
    edge->source = cond_blk;
    edge->destination = exit_edge->destination;
    edge->next_source = exit_edge->destination->input_edges;
    exit_edge->destination->input_edges = edge;
    exit_edge->destination->inputs++;
}


static  bool    KillOneTrippers( void )
/**************************************
    Nuke the loops that are only going to go around one time.
*/
{
    block       *blk;
    block       *curr;
    block       *loop_head;
    instruction *ins;
    instruction *next;