inssched.c

来自「开放源码的编译器open watcom 1.6.0版的源代码」· C语言 代码 · 共 1,013 行 · 第 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:  Instruction reordering for better pipeline utilization.
*
****************************************************************************/


#include <limits.h>
#include "standard.h"
#include "coderep.h"
#include "indvars.h"
#include "opcodes.h"
#include "sysmacro.h"
#include "model.h"
#include "spawn.h"
#include "memout.h"
#include "procdef.h"
#include "freelist.h"
#include "sched.h"
#include "pattern.h"
#include "vergen.h"
#include "zoiks.h"

extern  void            ProcMessage(msg_class);
extern  sym_handle      AskForLblSym(label_handle);
extern  mem_out_action  SetMemOut(mem_out_action);
extern  pointer         SafeRecurse(pointer(*)(),pointer);
extern  bool            ReDefinedBy(instruction *, name *);
extern  instruction_id  Renumber(void);
extern  hw_reg_set      StackReg(void);
extern  FU_entry        *FUEntry(instruction *);
extern  bool            FPStackIns(instruction *);
extern  int             CountIns(block*);
extern  bool            VisibleToCall(instruction *,name *, bool);
extern  bool            IsSegReg(hw_reg_set);
extern  bool            FPStackReg(name*);
extern  bool            FPInsIntroduced(instruction*);
extern  int             FPStkOver(instruction *,int);
extern  void            FPCalcStk(instruction*,int*);
extern  void            FPPreSched(block*);
extern  void            FPPostSched(block*);
extern  bool            FPFreeIns(instruction*);
extern  int             FPMaxDepth( instruction *ins );
extern  bool            DoesSomething(instruction*);
extern  name            *ScaleIndex(name*,name*,type_length,type_class_def,type_length,int,i_flags);
extern  hw_reg_set      LowReg(hw_reg_set);
extern  hw_reg_set      HighReg(hw_reg_set);
extern  int             FPStackExit( block *);
extern  void            ClearInsBits( instruction_flags );
extern  hw_reg_set      FullReg( hw_reg_set );

extern  proc_def        *CurrProc;
extern  block           *HeadBlock;
extern  byte            OptForSize;

#define DEPS_IN_BLOCK    20

typedef struct dep_list_block {
    struct dep_list_block      *next;
    unsigned                    used;
    struct dep_list_entry      entries[DEPS_IN_BLOCK];
} dep_list_block;

typedef enum {
    DEP_NONE,
    DEP_OP,
    DEP_INDEX
} dep_type;


data_dag                *DataDag;   /* global for dump routines */
static pointer          DepFrl;
static dep_list_block   *CurrDepBlock;
static block            *SBlock;


extern  bool    SchedFrlFree( void )
/***********************************
    Free the instruction schedulers dependancy link lists.
*/
{
    return( FrlFreeAll( &DepFrl, sizeof( dep_list_block ) ) );
}

static dep_list_entry *AllocDep( void )
/**************************************
    Allocate one dependancy link structure.
*/
{
    dep_list_block  *new;

    if( CurrDepBlock == NULL || CurrDepBlock->used >= DEPS_IN_BLOCK ) {
        new = AllocFrl( &DepFrl, sizeof( dep_list_block ) );
        new->next = CurrDepBlock;
        new->used = 0;
        CurrDepBlock = new;
    }
    return( &CurrDepBlock->entries[ CurrDepBlock->used++ ] );
}


static unsigned InsStallable( instruction *ins )
/***********************************************
    Determine how stallable is an instruction is. The more stallable resources
    an instruction uses, and the earlier in the instruction pipeline those
    resources are used, the more likely the instruction is going to have to
    wait due to a dependancy. This is used for breaking ties when we actually
    schedule the instructions in a block.
*/
{
    unsigned stallable;
    int i;

    stallable = 0;
    for( i = ins->num_operands - 1; i >= 0; --i ) {
        switch( ins->operands[i]->n.class ) {
        case N_INDEXED:
            stallable += 3;
            break;
        case N_REGISTER:
            stallable += 2;
            break;
        case N_MEMORY:
            stallable += 1;
            break;
        }
    }
    if( ins->result != NULL && ins->result->n.class == N_INDEXED ) {
        stallable += 3;
    }
    return( stallable );
}

static void InitDag( void )
/**************************
    Allocate the data dependancy dag list, and initialize the fields
    in it.
*/
{
    data_dag    *dag;
    data_dag    *head;
    instruction *ins;

    head = NULL;
    for( ins = SBlock->ins.hd.next; ins->head.opcode != OP_BLOCK;
         ins = ins->head.next ) {
        ins->ins_flags &= ~INS_INDEX_ADJUST;
        switch( ins->head.opcode ) {
        case OP_ADD:
        case OP_SUB:
            if( ins->operands[0] == ins->result
                && ins->operands[0]->n.class == N_REGISTER
                && ins->operands[1]->n.class == N_CONSTANT
                && ins->operands[1]->c.const_type == CONS_ABSOLUTE
                && (ins->type_class == WD || ins->type_class == SW) ) {
                /*
                    We have an instruction of the form:
                        ADD REG, CONST => REG
                    These can slide past instructions who just use REG
                    as an index register, as long as we adjust the
                    index offset by CONST. This gives the scheduler a
                    little more freedom to move things around.
                */
                ins->ins_flags |= INS_INDEX_ADJUST;
            }
            break;
        }
        _Alloc( dag, sizeof( data_dag ) );
        dag->ins = ins;
        dag->height = 0;
        dag->anc_count = 0;
        dag->deps = NULL;
        dag->visited = FALSE;
        dag->stallable = InsStallable( ins );
        dag->prev = head;
        head = dag;
    }
    DataDag = head;
}

static bool StackOp( instruction *ins )
/**************************************
    Does this instruction explicitly or implicitly use the machine's stack
    pointer.
*/
{
    int     i;
    hw_reg_set  sp;
    name        *op;

    switch( ins->head.opcode ) {
    case OP_CALL:
    case OP_CALL_INDIRECT:
    case OP_PUSH:
    case OP_POP:
        return( TRUE );
    }
    sp = StackReg();
    for( i = ins->num_operands-1; i >= 0; --i ) {
        op = ins->operands[i];
        if( op->n.class == N_INDEXED ) op = op->i.index;
        if(op->n.class == N_REGISTER && HW_Ovlap(sp,op->r.reg)) return( TRUE );
    }
    op = ins->result;
    if( op == NULL ) return( FALSE );
    if( op->n.class == N_INDEXED ) op = op->i.index;
    if( op->n.class == N_REGISTER && HW_Ovlap(sp,op->r.reg) ) return( TRUE );
    return( FALSE );
}


static  bool    ReallyDefinedBy( instruction *ins_i, instruction *ins_j,
                                 name *op, bool ins_linked )
/**********************************************************************/
{
    bool        redefd;
    instruction *ins;

    redefd = ReDefinedBy( ins_i, op );
    if( redefd != MAYBE || !ins_linked ) return( redefd );
    _INS_NOT_BLOCK( ins_i );
    _INS_NOT_BLOCK( ins_j );
    if( ins_i->id > ins_j->id ) {
        ins = ins_i;
        ins_i = ins_j;
        ins_j = ins;
    }
    while( ins_i != ins_j ) {
        if( ReDefinedBy( ins_i, op->i.index ) ) return( TRUE );
        ins_i = ins_i->head.next;
    }
    return( FALSE );
}

static bool OkToSlide( instruction *ins, name *op )
/**************************************************
    Is it OK to slide an INDEX_ADJUST instruction past an index name?
*/
{
    #if  _TARGET & (_TARG_80386 | _TARG_IAPX86 )
        int             i;
    #endif

    ins = ins;
    if( op->i.base != NULL ) return( TRUE );
    if( op->i.constant != 0 ) return( TRUE );
    if( OptForSize >= 50 ) return( FALSE );
    #if  _TARGET & (_TARG_80386 | _TARG_IAPX86 )
        /* bad news to add a displacement on an instruction that also
           has a constant operand (takes an extra clock) */
        for( i = ins->num_operands-1; i >= 0; --i ) {
            if( ins->operands[i]->n.class == N_CONSTANT ) return( FALSE );
        }
    #endif
    return( TRUE );
}

static bool HiddenDependancy( instruction *ins, name *op )
/*********************************************************
    Look out for cheesy hidden dependencies. These can come
    about, for instance, when two instructions modify
    AL and AH - these cause a stall.
*/
{
    int         i;
    hw_reg_set  full;

    if( FPStackIns( ins ) ) return( FALSE );
    if( op->n.class != N_REGISTER ) return( FALSE );
    full = FullReg( op->r.reg );
    op = ins->result;
    for( i = 0; i < ins->num_operands; i++ ) {
        if( op == NULL ) continue;
        if( op->n.class != N_REGISTER ) continue;
        if( HW_Ovlap( full, op->r.reg ) ) return( TRUE );
        op = ins->operands[ i ];
    }
    return( FALSE );
}

static dep_type CheckOneOp( instruction *ins_i, instruction *ins_j,
                        name *op, bool ins_linked )
/******************************************************************
    Check one op for redefinition
*/
{
    if( op->n.class == N_INDEXED && op->i.index != NULL ) {
        if( ins_linked
            && (ins_i->ins_flags & INS_INDEX_ADJUST)
            && HW_Ovlap( ins_i->result->r.reg, op->i.index->r.reg )
            && OkToSlide( ins_j, op ) ) {
            return(DEP_NONE);
        }
        if( ReDefinedBy( ins_i, op->i.index ) ) {
            return( DEP_INDEX );
        }
    }
    if( ReallyDefinedBy( ins_i, ins_j, op, ins_linked ) ) {
        if( !FPStackReg( op ) ) return( DEP_OP );
        if( ins_i->sequence == ins_j->sequence ) return( DEP_OP );
    }
    if( HiddenDependancy( ins_i, op ) ) {
        return( DEP_OP );
    }
    return( DEP_NONE );
}


static dep_type DataDependant( instruction *ins_i,
                               instruction *ins_j, bool ins_linked )
/************************************************************************
    Does instruction i redefine any of the operands or result of
    instruction j? And if so, how?
*/