cse.c

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

/****************************************************************************
*
*                            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:  Common Subexpression Elimination (aka CommonSex).
*
****************************************************************************/


#include "standard.h"
#include "coderep.h"
#include "opcodes.h"
#include "zoiks.h"
#include "typedef.h"
#include "hostsys.h"
#include "model.h"
#include "cgdefs.h"
#include "tree.h"
#include "cfloat.h"
#include "feprotos.h"

typedef enum {
        ALL_LIVE,
        OP_DIES,
        RESULT_DIES
} who_dies;

extern block            *HeadBlock;
extern name             *Names[];
extern type_class_def   Unsigned[];
extern bool             BlockByBlock;
extern  byte            OptForSize;

static instruction      *ExprHeads[LAST_CSE_OP+1];
static  bool            LeaveIndVars;

extern  name            *ScaleIndex(name *,name *,type_length ,type_class_def ,type_length ,int ,i_flags );
extern name             *AllocTemp(type_class_def);
extern void             FPNotStack(name*);
extern bool             FPStackOp(name*);
extern bool             FPSideEffect(instruction*);
extern bool             FPStackIns(instruction*);
extern void             FreeIns(instruction*);
extern void             PrefixIns(instruction*,instruction*);
extern void             SuffixIns(instruction*,instruction*);
extern instruction      *MakeMove(name*,name*,type_class_def);
extern instruction      *MakeBinary(opcode_defs,name*,name*,name*,type_class_def);
extern bool             FPIsConvert(instruction*);
extern name             *AllocConst(pointer);
extern pointer          CnvCFToType(pointer,type_def*);
extern type_def         *ClassType(type_class_def);
extern int              NumOperands(instruction*);
extern bool             InsDead(void);
extern bool             LoadAToMove(instruction*);
extern bool             Hoistable(instruction*,block*);
extern void             SXBlip(void);
extern instruction      *MakeUnary(opcode_defs,name*,name*,type_class_def);
extern  name            *STempOffset(name*,type_length,type_class_def,type_length);
extern  name            *SAllocMemory(pointer,type_length,cg_class,type_class_def,type_length);
extern  name            *AllocAddrConst(name*,int,constant_class,type_class_def);
extern  name            *AllocIntConst(int);
extern  bool            DeadBlocks(void);
extern  void            RemoveInputEdge(block_edge*);
extern  byte            *Copy(void*,void*,uint);
extern  instruction     *NewIns(int);
extern  bool            DivIsADog(type_class_def);
extern  bool            IsVolatile(name*);
extern  bool            ReDefinedBy(instruction*,name*);
extern  bool            Inducable(block*,instruction*);
extern  void            MoveHead(block*,block*);
extern  void            MakeFlowGraph(void);
extern  bool            BlockTrim(void);
extern  bool            PeepOpt(block*,block *(*)(block *,block *),block *,bool);
extern  instruction     *FoldIns(instruction*);
extern  bool            ConstFold(block*);
extern  int             GetLog2(unsigned_32);
extern  bool            IsSegReg(hw_reg_set);
extern  void            FindReferences(void);
extern  bool            IsTrickyPointerConv( instruction * );

/* forward declarations */
static  void            TreeBits( block *root );
static  void            DeleteFromList( instruction **owner,
                                        instruction *ins, instruction *new );
static  void            CleanTableEntries( block *root );

/* Borrow a few fields and bits to label trees with bits and link stuff */

#define _INSBITS( ins )   _LBitScalar((ins)->head.live.within_block)
#define _BLKBITS( blk )   _LBitScalar((blk)->available_bit)
#define _INSLINK( ins )   (*(instruction **)&(ins)->u2.cse_link)
#define _NAMELINK( op )   (*(instruction **)&(op)->v.conflict)
#define PARTITION_ROOT    BLOCK_VISITED
#define INS_DEFINES_OWN_OPERAND INS_MARKED




static  void    ReCalcAddrTaken( void )
/**************************************
*/
{
    name        *temp;

    for( temp = Names[ N_TEMP ]; temp != NULL; temp = temp->n.next_name ) {
        if( temp->v.usage & VAR_VOLATILE ) continue;
        if( temp->v.symbol != NULL &&
            ( FEAttr( temp->v.symbol ) & FE_ADDR_TAKEN ) ) continue;
        temp->v.usage &= ~USE_ADDRESS;
    }
    FindReferences();
}


static  bool    LoadAddr( void )
/*******************************
    Propagate load address instructions by replacing them with moves of
    "relocatable constants". For example:
       LA  x => t    is replaced by    MOV address(x) => t
    Then PropagateMoves will move the ADDRESS(x) constants down and the
    MOV adresss(x) instruction might go away.
*/
{
    block       *blk;
    instruction *ins;
    bool        change;

    change = FALSE;
    blk = HeadBlock;
    while( blk != NULL ) {
        ins = blk->ins.hd.next;
        while( ins->head.opcode != OP_BLOCK ) {
            change |= LoadAToMove( ins );
            ins = ins->head.next;
        }
        blk = blk->next_block;
    }
    return( change );
}


static  bool    FindDefnBlocks( block *blk, instruction *cond, int i )
/********************************************************************/
{
    block_edge  *edge;
    block_edge  *other_input;
    block_edge  *next_source;
    block       *input;
    instruction *prev;
    name        *op;
    instruction *new_cond;
    instruction *new_ins;
    block_edge  *jump_edge;
    block       *new_dest_blk;
    bool        change;

    change = FALSE;
    op = cond->operands[ i ];
    for( edge = blk->input_edges; edge != NULL; edge = next_source ) {
        next_source = edge->next_source;
        input = edge->source;
        if( !( input->class & JUMP ) ) continue;
        for( prev = input->ins.hd.prev;
             prev->head.opcode != OP_BLOCK; prev = prev->head.prev ) {
            if( !ReDefinedBy( prev, op ) ) continue;
            if( prev->head.opcode != OP_MOV ) break;
            if( prev->result != op ) break;
            if( input->depth < blk->depth ) { // don't make 2 entries into loop
                other_input = blk->input_edges;
                while( other_input != NULL ) {
                    if( other_input->source->depth < blk->depth &&
                        other_input->source != input ) break;
                    other_input = other_input->next_source;
                }
                if( other_input != NULL ) break;
            }
            new_cond = NewIns( 2 );
            Copy( cond, new_cond,
                  sizeof(instruction)+(MAX_OPS_PER_INS-1)*sizeof(name*) );
            new_cond->head.prev = new_cond;
            new_cond->head.next = new_cond;
            new_cond->operands[ i ] = prev->operands[ 0 ];
            new_ins = FoldIns( new_cond );
            if( new_ins == NULL ) {
                new_ins = new_cond;
            }
            if( _OpIsCondition( new_ins->head.opcode ) ) {
                if( _TrueIndex( new_ins ) == _FalseIndex( new_ins ) ) {
                    new_dest_blk = blk->edge[ _TrueIndex( new_ins ) ].destination;
                    if( new_dest_blk != blk ) {
                        jump_edge = &input->edge[ 0 ];
                        RemoveInputEdge( jump_edge );
                        new_dest_blk->inputs++;
                        jump_edge->next_source = new_dest_blk->input_edges;
                        new_dest_blk->input_edges = jump_edge;
                        jump_edge->destination = new_dest_blk;
                        if( input->depth < blk->depth ) {
                            MoveHead( blk, new_dest_blk );
                        }
                        change = TRUE;
                    }
                }
            }
            FreeIns( new_ins );
            break;
        }
    }
    return( change );
}


static  bool    StretchABlock( block *blk )
/******************************************
    see StretchEdges
*/
{
    instruction         *ins;
    name                *op;
    int                 i;

    if( blk->ins.hd.prev != blk->ins.hd.next ) return( FALSE );
    ins = blk->ins.hd.next;
    if( !_OpIsCondition( ins->head.opcode ) ) return( FALSE );
    op = ins->operands[ 0 ];
    i = 1;
    if( op->n.class != N_CONSTANT ) {
        op = ins->operands[ 1 ];
        i = 0;
    }
    if( op->n.class != N_CONSTANT ) return( FALSE );
    if( IsVolatile( ins->operands[ i ] ) ) return( FALSE );
    return( FindDefnBlocks( blk, ins, i ) );
}


static  bool    StretchEdges( void )
/***********************************

    Try to detect code like:
        found = 1;
        goto somewhere;

    somewhere:;
        if( found ) goto elsewhere;

*/
{
    block       *blk;
    bool        change;

    change = FALSE;
    for( blk = HeadBlock; blk != NULL; blk = blk->next_block ) {
        if( StretchABlock( blk ) ) change = TRUE;
    }
    return( change );
}


extern  bool    PropRegsOne( void )
/*********************************/
/*
 * We can't propagate registers very far, but one instruction is safe.
 * This is specially for the case when we have a(b(x)). We'll generate
 * call    B => reg
 * mov     reg => temp
 * mov     temp => ??? (or push temp)
 * call    A
 */
{
#if 0
    block       *blk;
    instruction *ins;
    instruction *next;
    name        *reg;
    name        **opp;
    bool        change;

    change = FALSE;
    for( blk = HeadBlock; blk != NULL; blk = blk->next_block ) {
        for( ins = blk->ins.hd.next; ins->head.opcode != OP_BLOCK;
                                     ins = ins->head.next ) {
            if( ins->head.opcode != OP_MOV ) continue;
            reg = ins->operands[ 0 ];
            if( FPSideEffect( ins ) ) continue;
            if( reg->n.class != N_REGISTER ) continue;
            next = ins->head.next;
            if( next->head.opcode == OP_BLOCK ) break;
            if( FPStackIns( next ) ) continue;
            if( next->head.opcode == OP_LA ) continue;
            if( next->head.opcode == OP_CAREFUL_LA ) continue;
            if( next->num_operands != 1 ) {
                if( next->num_operands <= NumOperands( next ) ) continue;
                if( !IsSegReg( reg->r.reg ) ) continue;
                opp = &next->operands[ next->num_operands-1 ];
            } else {
                if( _IsConvert( next ) ) continue;
                opp = &next->operands[ 0 ];
            }
            if( *opp != ins->result ) continue;
            *opp = reg;
            change = TRUE;
        }
    }
    return( change );
#else
    return( FALSE );
#endif
}


static  void    FindPartition( void )
/************************************
    Partition the flow graph into trees, with root indicated by
    PARTITION_ROOT.  Nodes of the tree (except root) may have only one
    input edge.  These are the partitions in which dataflow is easy to
    deal with since there is no merging of information.
*/
{
    block       *blk;
    block       *oth;
    block       *temp;
    block_edge  *edge;
    int         i;

    blk = HeadBlock;
    while( blk != NULL ) {
        if( ( blk->class & BIG_LABEL ) != 0 || blk->inputs != 1 ) {
            blk->class |= PARTITION_ROOT;
        }
        blk->u.partition = blk;
        _BLKBITS( blk ) = EMPTY;
        blk = blk->next_block;
    }
    blk = HeadBlock;
    while( blk != NULL ) {
        i = blk->targets;
        edge = &blk->edge[ 0 ];
        while( --i >= 0 ) {
            if( edge->flags & DEST_IS_BLOCK ) {
                oth = edge->destination;
                if( !( oth->class & PARTITION_ROOT ) && oth->inputs == 1 ) {
                    temp = oth->u.partition;
                    oth->u.partition = blk->u.partition;
                    blk->u.partition = temp;
                }
            }
            ++edge;
        }
        blk = blk->next_block;
    }
    blk = HeadBlock;
    while( blk != NULL ) {
        if( blk->class & PARTITION_ROOT ) {
            TreeBits( blk );
        }
        blk = blk->next_block;
    }
}


static  void    TreeBits( block *root )
/**************************************
    Label the partition (tree) with bits such that block A is the
    ancestor of block B IFF _BLKBITS(A) & _BLKBITS(B) == _BLKBITS(A).
    Simply speaking, we add a new bit for every node in the tree.  A
    child node gets its parents bit set plus one new one for itself.
    This allows for simple ancestor, sibling, first common ancestor
    checking.
*/
{
    block       *daddy;
    a_bit_set   next_bit;
    bool        change;
    block       *blk;
    instruction *ins;
    block       **owner;

    next_bit = 1;
    _BLKBITS( root ) = next_bit;
    for( ;; ) {
        change = FALSE;
        blk = root->u.partition;
        while( blk != root ) {
            daddy = blk->input_edges->source;
            if( _BLKBITS( blk ) == EMPTY && _BLKBITS( daddy ) != EMPTY ) {
                next_bit <<= 1;