/****************************************************************************
*
*                            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 code detection and optimization.
*
****************************************************************************/


#include "optwif.h"

typedef struct common_info {
        ins_entry   *start_com;
        ins_entry   *start_del;
        uint        save;
} common_info;

extern    byte  OptForSize;

extern  bool            Equal( pointer, pointer, uint );
extern  ins_entry       *IsolatedCode( ins_entry * );
extern  void            AddNewJump( ins_entry *, code_lbl * );
extern  void            InsertQueue( ins_entry *, ins_entry * );
extern  void            DeleteQueue( ins_entry * );
extern  oc_class        PrevClass( ins_entry * );
extern  ins_entry       *Untangle( ins_entry * );
extern  ins_entry       *NextIns( ins_entry * );
extern  void            ChgLblRef( ins_entry *, code_lbl * );
extern  code_lbl        *AddNewLabel( ins_entry *, int );
extern  ins_entry       *DelInstr( ins_entry * );
extern  ins_entry       *PrevIns( ins_entry * );
extern  int             OptInsSize( oc_class, oc_dest_attr );
extern  bool            FindShort( ins_entry *, ins_entry * );



static  bool    JustMoveLabel( common_info *max, ins_entry *ins )
/***************************************************************/
{
    oc_class            cl;
    ins_entry           *lbl;
    ins_entry           *add;
    ins_entry           *next;

  optbegin
    if( PrevClass( max->start_del ) != OC_LABEL )
        optreturn( FALSE );
    lbl = PrevIns( max->start_del );
    if( _Attr( lbl ) & ATTR_SHORT )
        optreturn( FALSE );
    cl = PrevClass( lbl );
    if( !_TransferClass( cl ) )
        optreturn( FALSE );
    DeleteQueue( lbl );
    InsertQueue( lbl, PrevIns( max->start_com ) );
    add = PrevIns( max->start_del );
    for( ;; ) {
        next = NextIns( add );
        DelInstr( next );
        if( next == ins ) {
            break;
        }
    }
    Untangle( lbl );
    optreturn( TRUE );
}


static  void    TransformJumps( ins_entry *ins, ins_entry *first )
/****************************************************************/
{
    ins_entry           *add;
    ins_entry           *next;
    ins_entry           *lbl;
    oc_class            cl;

  optbegin
    if( _Class( ins ) == OC_RET )
        optreturnvoid;
    lbl = _Label( ins )->ins;
    if( lbl == NULL )
        optreturnvoid;
    add = lbl;
    for( ;; ) {
        if( add == NULL )
            optreturnvoid;
        cl = _Class( add );
        if( _TransferClass( cl ) )
            break;
        if( cl == OC_LABEL ) {
            if( _Attr( add ) & ATTR_SHORT )
                optreturnvoid;
            _ClrStatus( _Label( add ), SHORTREACH );
        }
        add = NextIns( add );
    }
    if( add == first || add == ins )
        optreturnvoid;
    if( FindShort( first, lbl ) )
        optreturnvoid;
    for( ;; ) {
        next = PrevIns( add );
        DeleteQueue( add );
        InsertQueue( add, first );
        if( add == lbl )
            break;
        add = next;
    }
    DeleteQueue( first );
    InsertQueue( first, next );
    Untangle( NextIns( first ) );
  optend
}



static  bool    CommonInstr( ins_entry *old, ins_entry *add )
/***********************************************************/
{
    oc_entry    *oc_add;
    oc_entry    *oc_old;

  optbegin
    if( _IsModel( NO_OPTIMIZATION ) )
        optreturn( FALSE );
    oc_add = &add->oc.oc_entry;
    oc_old = &old->oc.oc_entry;
    if( oc_add->class != oc_old->class )
        optreturn( FALSE );
    if( oc_add->reclen != oc_old->reclen )
        optreturn( FALSE );
    switch( _Class( old ) ) {
    case OC_BDATA:
        /* User may be doing stupid stuff like stringing together a bunch
         * of '__asm _emit x' or '__asm db x' statements which aren't complete
         * instructions. If we try to optimize and split them, things are
         * going to go boom. So let's just not touch those - it's extremely
         * unlikely that we'd be missing any real optimization opportunities.
         */
        /* fall through */
    case OC_DEAD:
        optreturn( FALSE );
    case OC_JMP:
    case OC_CALL:
    case OC_LABEL:
    case OC_LREF:
        if( _Label( old ) != _Label( add ) )
            optreturn( FALSE );
        break;
    case OC_JCOND:
        if( _JmpCond( old ) != _JmpCond( add ) )
            optreturn( FALSE );
        if( _Label( old ) != _Label( add ) )
            optreturn( FALSE );
#if _TARGET & _TARG_RISC
        if( old->oc.oc_jcond.index != add->oc.oc_jcond.index )
            return( FALSE );
#endif
        break;
    case OC_RET:
        if( _RetPop( old ) != _RetPop( add ) )
            optreturn( FALSE );
        break;
    default:
        if( Equal( oc_add, oc_old, oc_add->reclen ) == FALSE )
            optreturn( FALSE );
        break;
    }
    optreturn( TRUE );
}


static  void    FindCommon( common_info *c, ins_entry *p1, ins_entry *p2 )
/************************************************************************/
{
  optbegin
    c->save = 0;
    for( ;; ) {
        if( CommonInstr( p1, p2 ) == FALSE )
            break;
        c->start_com = p1;
        c->start_del = p2;
        c->save += _ObjLen( p1 );
        for( ;; ) {
            p1 = PrevIns( p1 );
            if( p1 == NULL )
                optreturnvoid;
            if( _Class( p1 ) != OC_LABEL ) {
                break;
            }
        }
        p2 = PrevIns( p2 );
        if( p2 == NULL ) {
            break;
        }
    }
  optend
}

extern  bool    ComTail( ins_entry *list, ins_entry *ins )
/********************************************************/
{
    ins_entry           *try;
    ins_entry           *add;
    ins_entry           *next;
    ins_entry           *lbl;
    ins_entry           *first;
    common_info         common;
    common_info         max;
    int                 align;

  optbegin
    align = (_Class( list ) == OC_LABEL) ? _ObjLen( list ) : 0;
    try = list;
    max.save = 0;
    for( ;; ) {
        if( try != ins ) {
            FindCommon( &common, try, ins );
            if( common.save > max.save ) {
                max = common;
                first = try;
            }
        }
        try = _LblRef( try );
        if( try == NULL ) {
            break;
        }
    }
    if( max.save == 0 )
        optreturn( FALSE );
    if( JustMoveLabel( &max, ins ) )
        optreturn( TRUE );
    if( OptForSize < 25 )
        optreturn( FALSE );
    if( max.save <= OptInsSize( OC_JMP, OC_DEST_NEAR ) )
        optreturn( FALSE );
    TransformJumps( ins, first );
    add = PrevIns( max.start_del );
    try = PrevIns( max.start_com );
    if( FindShort( try, NULL ) )
        align = 0;
    AddNewJump( add, AddNewLabel( PrevIns( max.start_com ), align ) );
    lbl = PrevIns( max.start_com );
    add = NextIns( add );
    for( ;; ) {
        next = NextIns( add );
        DelInstr( next );
        if( next == ins ) {
            break;
        }
    }
    Untangle( lbl );
    IsolatedCode( add );
    optreturn( TRUE );
}


extern  bool    ComCode( ins_entry *jmp )
/***************************************/
{
    ins_entry   *new;
    ins_entry   *com;
    int         align;
    bool        common;

  optbegin
    common = FALSE;
    new = _Label( jmp )->ins;
    if( new != NULL ) {
        align = _ObjLen( new );
        for( ;; ) {
            for( ;; ) {
                new = PrevIns( new );
                if( new == NULL )
                    break;
                if( new == jmp )
                    break;
                if( _Class( new ) != OC_LABEL ) {
                    break;
                }
            }
            if( new == NULL )
                break;
            if( new == jmp )
                break;
            com = PrevIns( jmp );
            if( com == NULL )
                break;
            if( CommonInstr( new, com ) == FALSE )
                break;
            com = PrevIns( DelInstr( com ) );
            common = TRUE;
            if( _Class( jmp ) == OC_DEAD ) {
                optreturn( common );
            }
        }
        if( common ) {
            if( FindShort( new, NULL ) )
                align = 0;
            ChgLblRef( jmp, AddNewLabel( new, align ) );
            Untangle( NextIns( new ) );
            Untangle( NextIns( jmp ) );
            Untangle( com );
        }
    }
    if( _Class( jmp ) == OC_DEAD )
        optreturn( common );
    common |= ComTail( _Label( jmp )->refs, jmp );
    optreturn( common );
}


extern  void    TraceCommon( ins_entry *lbl_ins )
/***********************************************/
{
    ins_entry   *ref;
    ins_entry   *ins;

  optbegin
    for( ;; ) {
        ref = _Label( lbl_ins )->refs;
        for( ;; ) {
            for( ;; ) {
                if( ref == NULL )
                    optreturnvoid;
                ins = ref;
                ref = _LblRef( ref );
                if( _Class( ins ) == OC_JMP ) {
                    break;
                }
            }
            if( ComCode( ins ) ) {
                break;
            }
        }
        if( ref == NULL ) {
            break;
        }
    }
    optreturnvoid;
}
