treefold.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 1,648 行 · 第 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:  Processor independent constant folding optimizations.
*
****************************************************************************/


#include "standard.h"
#include "model.h"
#include "coderep.h"
#include "cgdefs.h"
#include "addrname.h"
#include "tree.h"
#include "opcodes.h"
#include "cfloat.h"
#include "zoiks.h"
#include "i64.h"
#include "feprotos.h"
#include "types.h"

typedef union i32 {
    signed_32   s;
    unsigned_32 u;
} i32;

extern  type_def        *TypeInteger;
extern  type_def        *TypeBoolean;

#include "treefold.h"
#include "bldins.h"
extern  an              TreeGen(tn);
extern  name            *AllocIntConst(int);
extern  tn              TGCompare(cg_op,tn,tn,type_def*);
extern  unsigned_32     Mask(btn);
extern  unsigned_32     U32ModDiv(unsigned_32*,unsigned_32);
extern  tn              TGUnary(cg_op,tn,type_def*);
extern  tn              TGBinary(cg_op,tn,tn,type_def*);
extern  void            BurnTree(tn);
extern  tn              TGConst(cfloat *,type_def*);
extern  tn              TGConvert(tn,type_def*);
extern  uint            Length(char*);
extern  tn              TGTrash(tn);
extern  tn              TGNode( tn_class, cg_op, tn, tn, type_def * );
extern  bool            TGCanDuplicate( tn node );
extern  tn              TGDuplicate( tn node );

#define HasBigConst( t )       ( ( (t)->attr & TYPE_FLOAT ) || (t)->length == 8 )

static cg_op RevOpcode[] = {
    O_EQ,    /* O_EQ*/
    O_NE,    /* O_NE*/
    O_LT,    /* O_GT*/
    O_GE,    /* O_LE*/
    O_GT,    /* O_LT*/
    O_LE     /* O_GE*/
};

/* CheckCmpRange is based on code stolen from CheckMeaninglessCompare(),
 * used by the C++ front end. It is quite handy to be able to perform the
 * folding inside the cg, especially since the C++ front end doesn't do it!
 */

#define SIGN_BIT        (0x8000)
#define NumSign( a )    ((a) & SIGN_BIT)
#define NumBits( a )    ((a) & 0x7fff)

typedef enum {
    CMP_VOID    = 0,    /* comparison can't be folded */
    CMP_FALSE   = 1,
    CMP_TRUE    = 2,
} cmp_result;

typedef enum {
    REL_EQ,    // x == c
    REL_LT,    // x < c
    REL_LE,    // x <= c
    REL_SIZE
} rel_op;

//  a <= x <=  b   i.e range of x is between a and b
enum  case_range {
    CASE_LOW,         // c < a
    CASE_LOW_EQ,      // c == a
    CASE_HIGH,        // c > b
    CASE_HIGH_EQ,     // c == b
    CASE_SIZE
};

static char const CmpResult[REL_SIZE][CASE_SIZE] = {
//    c < a      c == a     c > b      c == b
    { CMP_FALSE, CMP_VOID , CMP_FALSE, CMP_VOID },  // x == c
    { CMP_FALSE, CMP_FALSE, CMP_TRUE , CMP_VOID },  // x < c
    { CMP_FALSE, CMP_VOID , CMP_TRUE , CMP_TRUE },  // x <= c
};

#define LOW_VAL         (0x80000000)
#define HIGH_VAL        (0xfffffffful)
#define MAXSIZE         32

static int CmpType( type_def *tipe )
/**********************************/
/* Convert cg type to a value used by CheckCmpRange */
{
    int     ret;

    ret =  tipe->length * 8;
    if( tipe->attr & TYPE_SIGNED )
        ret |= SIGN_BIT;
    return( ret );
}

static cmp_result CheckCmpRange( opcode_defs op, int op_type, cfloat *val )
/*************************************************************************/
/* Check if comparison 'op' of operand of type 'op_type' against constant
 * 'val' can be folded, eg. '(unsigned char)x <= 255'. Integer only, can
 * be used for bitfields (op_type contains number of bits).
 */
{
    enum case_range     range;
    cmp_result          ret;
    signed_32           low;
    signed_32           high;
    signed_32           konst;
    rel_op              rel;
    bool                rev_ret = FALSE;

    /* Map cg rel ops to equivalent cases */
    switch( op ) {
    case O_NE:
        rev_ret = TRUE;
    case O_EQ:
        rel = REL_EQ;
        break;
    case O_GE:
        rev_ret = TRUE;
    case O_LT:
        rel = REL_LT;
        break;
    case O_GT:
        rev_ret = TRUE;
    case O_LE:
        rel = REL_LE;
        break;
    default:
        _Zoiks( ZOIKS_112 );
    }
    /* Determine type range */
    if( NumSign( op_type ) ) {
        low = (signed_32)(LOW_VAL) >> MAXSIZE-NumBits( op_type );
        high = ~low;
    } else {
        low = 0;
        high = HIGH_VAL >> MAXSIZE-NumBits( op_type );
    }
    /* Determine how to compare */
    konst = CFCnvF32( val );
    if( konst == low ) {
        range = CASE_LOW_EQ;
    } else if( konst == high ) {
        range = CASE_HIGH_EQ;
    } else if( NumBits( op_type ) < MAXSIZE ) { /* Can't be outside range */
        if( konst < low ) {                     /* Don't have to do unsigned compare */
            range = CASE_LOW;
        } else if( konst > high ) {
            range = CASE_HIGH;
        } else {
            range = CASE_SIZE;
        }
    } else {
        range = CASE_SIZE;
    }
    /* Figure out comparison result, if possible */
    if( range != CASE_SIZE ) {
        ret = CmpResult[rel][range];
        if( rev_ret && (ret != CMP_VOID) ) {
            /* Flip result */
            if( ret == CMP_FALSE ) {
                ret = CMP_TRUE;
            } else {
                ret = CMP_FALSE;
            }
        }
    } else {
        ret = CMP_VOID;
    }
    return( ret );
}

static signed_32 CFConvertByType( cfloat *cf, type_def *tipe )
/************************************************************/
{
    signed_32   data;

    data = CFCnvF32( cf );
    switch( tipe->length ) {
    case 1:
        if( tipe->attr & TYPE_SIGNED ) {
            data = (signed_8)data;
        } else {
            data = (unsigned_8)data;
        }
        break;
    case 2:
        if( tipe->attr & TYPE_SIGNED ) {
            data = (signed_16)data;
        } else {
            data = (unsigned_16)data;
        }
        break;
    }
    return( data );
}

static signed_64 CFGetInteger64Value( cfloat *cf )
/************************************************/
{
    signed_64   value;
    int         neg;
    cfloat      *trunc;

    trunc = CFTrunc( cf );
    neg = CFTest( trunc );
    if( neg < 0 ) CFNegate( trunc );
    value = CFCnvF64( trunc );
    if( neg < 0 ) U64Neg( &value, &value );
    CFFree( trunc );
    return( value );
}

static  cfloat  *IntToCF( signed_64 value, type_def *tipe )
/*********************************************************/
{
    signed_8    s8;
    unsigned_8  u8;
    signed_16   s16;
    unsigned_16 u16;
    signed_32   s32;
    unsigned_32 u32;

    if( tipe->attr & TYPE_SIGNED ) {
        switch( tipe->length ) {
        case 1:
            s8 = value.u._8[I64LO8];
            return( CFCnvI32F( s8 ) );
        case 2:
            s16 = value.u._16[I64LO16];
            return( CFCnvI32F( s16 ) );
        case 4:
        case 6:
            s32 = value.u._32[I64LO32];
            return( CFCnvI32F( s32 ) );
        case 8:
            return( CFCnvI64F( value.u._32[I64LO32], value.u._32[I64HI32] ) );
        default:
            _Zoiks( ZOIKS_112 );
            return( NULL );
        }
    } else {
        switch( tipe->length ) {
        case 1:
            u8 = value.u._8[I64LO8];
            return( CFCnvU32F( u8 ) );
        case 2:
            u16 = value.u._16[I64LO16];
            return( CFCnvU32F( u16 ) );
        case 4:
        case 6:
            u32 = value.u._32[I64LO32];
            return( CFCnvU32F( u32 ) );
        case 8:
            return( CFCnvU64F( value.u._32[I64LO32], value.u._32[I64HI32] ) );
        default:
            _Zoiks( ZOIKS_112 );
            return( NULL );
        }
    }
}

static  tn      IntToType( signed_32 value, type_def *tipe )
/**********************************************************/
{
    signed_64   temp;

    I32ToI64( value, &temp );
    return( TGConst( IntToCF( temp, tipe ), tipe ) );
}


static  tn      Int64ToType( signed_64 value, type_def *tipe )
/************************************************************/
{
    return( TGConst( IntToCF( value, tipe ), tipe ) );
}


static  tn      CFToType( cfloat *cf, type_def *tipe )
/****************************************************/
{
    tn          result;

    if( ( tipe->attr & TYPE_FLOAT ) == EMPTY ) {
        result = TGConst( IntToCF( CFGetInteger64Value( cf ), tipe ), tipe );
        CFFree( cf );
    } else {
        result = TGConst( cf, tipe );
    }
    return( result );
}



extern  int     GetLog2( unsigned_32 value )
/******************************************/
{
    unsigned_32     count;
    int             log;

    if( _IsPowerOfTwo( value ) && value != 0 ) {
        log = 0;
        count = 1;
        for( ;; ) {
            if( count == value ) return( log );
            count += count;
            ++log;
        }
    }
    return( -1 );
}


extern  tn      FoldTimes( tn left, tn rite, type_def *tipe )
/***********************************************************/
{
    tn          temp;
    tn          fold;
    int         test;
    int         log;
    cfloat      *lv;
    cfloat      *rv;
    unsigned_32 li;
    unsigned_32 ri;

    if( left->class == TN_CONS ) {
        temp = left;
        left = rite;
        rite = temp;
    }
    if( rite->class != TN_CONS ) return( NULL );
    if( left->class == TN_BINARY && left->op == O_TIMES &&
        tipe == left->tipe && !HasBigConst( tipe ) ) {
        if( left->u.left->class == TN_CONS ) {
            left->u.left = FoldTimes( left->u.left, rite, tipe );
            return( left );
        }
        if( left->rite->class == TN_CONS ) {
            left->rite = FoldTimes( left->rite, rite, tipe );
            return( left );
        }
    }
    if( left->class==TN_BINARY && left->op==O_LSHIFT && tipe==left->tipe ) {
        if( !HasBigConst( tipe ) && left->rite->class == TN_CONS ) {
            log = left->rite->u.name->c.int_value;
            li = 1;
            while( --log >= 0 ) {
                li <<= 1;
            }
            BurnTree( left->rite );
            left->rite = CFToType( CFCnvU32F( li ), tipe );
            left->op = O_TIMES;
            left->rite = FoldTimes( left->rite, rite, tipe );
            return( left );
        }
    }
    rv = rite->u.name->c.value;
    if( left->class == TN_CONS ) {
        lv = left->u.name->c.value;
        if( !HasBigConst( tipe ) && CFIs32( lv ) && CFIs32( rv ) ) {
            li = CFConvertByType( lv, tipe );
            ri = CFConvertByType( rv, tipe );
            ri = li * ri;
            fold = IntToType( ri, tipe );
        } else {
            fold = CFToType( CFMul( left->u.name->c.value, rv ), tipe );
        }
        BurnTree( left );
        BurnTree( rite );
        return( fold );
    }