object.c

开放源码的编译器open watcom 1.6.0版的源代码

            prediction = NOT_TAKEN;
        }
    }
    return( prediction );
}

static  bool    BlockContainsCall( block *blk ) {
/***********************************************/

    instruction         *ins;

    for( ins = blk->ins.hd.next; ins->head.opcode != OP_BLOCK; ins = ins->head.next ) {
        if( _OpIsCall( ins->head.opcode ) ) return( TRUE );
    }
    return( FALSE );
}

static  void    PushTargets( void *stack, block *blk ) {
/******************************************************/

    block_num   i;

    for( i = 0; i < blk->targets; i++ ) {
        EdgeStackPush( stack, &blk->edge[ i ] );
    }
}

typedef enum {
    ABORT = 0,          // Abort this particular path
    CONTINUE,           // Continue on as normal
    STOP,               // Stop the entire flood down
} flood_decision;

typedef struct flood_info {
    bool        post_dominates;
    block       *dominator;
} flood_info;

typedef flood_decision (*flood_func)( block *, flood_info * );

static  void    FloodDown( block *from, flood_func func, void *parm ) {
/*********************************************************************/

    void                *stack;
    block               *dest;
    flood_decision      decision;
    block_edge          *edge;

    ClearBlockBits( FLOODED );
    stack = EdgeStackInit();
    PushTargets( stack, from );
    from->class |= FLOODED;
    while( !EdgeStackEmpty( stack ) ) {
        edge = EdgeStackPop( stack );
        dest = edge->destination;
        if( ( dest->class & FLOODED ) != EMPTY ) continue;
        decision = func( dest, parm );
        if( decision == ABORT ) continue;
        if( decision == STOP ) break;
        dest->class |= FLOODED;
        PushTargets( stack, dest );
    }
    EdgeStackFini( stack );
}

static  flood_decision PDFloodFunc( block *blk, flood_info *info ) {
/******************************************************************/

    if( blk == info->dominator ) return( ABORT );
    if( ( blk->class & RETURN ) != EMPTY ) {
        info->post_dominates = FALSE;
        return( STOP );
    }
    return( CONTINUE );
}

static  bool    PostDominates( block *dominator, block *blk ) {
/**************************************************************
    Return TRUE if dominator post-dominates blk.
    To determine this, we just flood down aborting whenever we hit
    previously encountered blocks or the dominator. If we hit a
    RETURN block, we return FALSE.
*/

    flood_info          info;

    info.post_dominates = TRUE;
    info.dominator = dominator;
    FloodDown( blk, PDFloodFunc, (void *)&info );
    return( info.post_dominates );
}

static  bool    CallApplies( block *src, block *dst ) {
/*****************************************************/

    src = dst;
    if( BlockContainsCall( dst ) ) {
        if( !PostDominates( dst, src ) ) {
            return( TRUE );
        }
    }
    return( FALSE );
}

static  int     CallHeuristic( block *blk, instruction *cond ) {
/**************************************************************/

    int         prediction;

    prediction = DNA;
    if( CallApplies( blk, blk->edge[ 0 ].destination ) ) {
        if( !CallApplies( blk, blk->edge[ 1 ].destination ) ) {
            prediction = Want( cond, 1 );
        }
    } else {
        if( CallApplies( blk, blk->edge[ 1 ].destination ) ) {
            prediction = Want( cond, 0 );
        }
    }
    return( prediction );
}

static  bool    LoopApplies( block *blk ) {
/*****************************************/

    if( ( blk->class & LOOP_HEADER ) != EMPTY ) return( TRUE );
    if( ( blk->class & JUMP ) != EMPTY ) {
        if( ( blk->edge[ 0 ].destination->class & LOOP_HEADER ) != EMPTY ) {
            return( TRUE );
        }
    }
    return( FALSE );
}

static  int     LoopHeuristic( block *blk, instruction *cond ) {
/**************************************************************/

    int         prediction;

    prediction = DNA;
    if( LoopApplies( blk->edge[ 0 ].destination ) ) {
        if( !LoopApplies( blk->edge[ 1 ].destination ) ) {
            prediction = Want( cond, 0 );
        }
    } else {
        if( LoopApplies( blk->edge[ 1 ].destination ) ) {
            prediction = Want( cond, 1 );
        }
    }
    return( prediction );
}

static  bool    GuardApplies( block *blk, block *dst, name *reg ) {
/*****************************************************************/

    instruction *ins;
    int         i;

    for( ins = dst->ins.hd.next; ins->head.opcode != OP_BLOCK; ins = ins->head.next ) {
        for( i = 0; i < ins->num_operands; i++ ) {
            // this could be beefed up to take into account aggragates
            if( ins->operands[ i ] == reg ) {
                return( !PostDominates( dst, blk ) );
            }
            if( ReDefinedBy( ins, reg ) ) {
                return( FALSE );
            }
        }
    }
    return( FALSE );
}

static  int     TryGuard( block *blk, instruction *cond, name *reg ) {
/********************************************************************/

    int         prediction;

    prediction = DNA;
    if( GuardApplies( blk, blk->edge[ 0 ].destination, reg ) ) {
        if( !GuardApplies( blk, blk->edge[ 1 ].destination, reg ) ) {
            prediction = Want( cond, 0 );
        }
    } else {
        if( GuardApplies( blk, blk->edge[ 1 ].destination, reg ) ) {
            prediction = Want( cond, 1 );
        }
    }
    return( prediction );
}

static  int     GuardHeuristic( block *blk, instruction *cond ) {
/***************************************************************/

    name        *op1;
    name        *op2;
    int         prediction;

    op1 = cond->operands[ 0 ];
    op2 = cond->operands[ 1 ];
    prediction = DNA;
    if( op1->n.class == N_REGISTER ) {
        prediction = TryGuard( blk, cond, op1 );
    }
    if( prediction == DNA ) {
        if( op2->n.class == N_REGISTER ) {
            prediction = TryGuard( blk, cond, op2 );
        }
    }
    return( DNA );
}

static  bool    StoreApplies( block *blk, block *next ) {
/*******************************************************/

    instruction *ins;

    if( PostDominates( next, blk ) ) return( FALSE );
    for( ins = next->ins.hd.next; ins->head.opcode != OP_BLOCK; ins = ins->head.next ) {
        if( ins->result == NULL ) continue;
        switch( ins->result->n.class ) {
        case N_MEMORY:
        case N_INDEXED:
        // case N_TEMP:
            return( TRUE );
        }
    }
    return( FALSE );
}

static  int     StoreHeuristic( block *blk, instruction *cond ) {
/***************************************************************/

    int         prediction;

    prediction = DNA;
    if( StoreApplies( blk, blk->edge[ 0 ].destination ) ) {
        if( !StoreApplies( blk, blk->edge[ 1 ].destination ) ) {
            prediction = Want( cond, 1 );
        }
    } else {
        if( StoreApplies( blk, blk->edge[ 1 ].destination ) ) {
            prediction = Want( cond, 0 );
        }
    }
    return( prediction );
}

static  bool    ReturnApplies( block *blk ) {
/*******************************************/

    if( ( blk->class & RETURN ) != EMPTY ) return( TRUE );
    if( ( blk->class & JUMP ) != EMPTY ) {
        if( ( blk->edge[ 0 ].destination->class & RETURN ) != EMPTY ) {
            return( TRUE );
        }
    }
    return( FALSE );
}

static  int     ReturnHeuristic( block *blk, instruction *cond ) {
/****************************************************************/

    int         prediction;

    prediction = DNA;
    if( ReturnApplies( blk->edge[ 0 ].destination ) ) {
        if( !ReturnApplies( blk->edge[ 1 ].destination ) ) {
            prediction = Want( cond, 1 );
        }
    } else {
        if( ReturnApplies( blk->edge[ 1 ].destination ) ) {
            prediction = Want( cond, 0 );
        }
    }
    return( prediction );
}

typedef int (*bp_heuristic)( block *, instruction * );

static bp_heuristic     Heuristics[] = {
    PointerHeuristic,
    CallHeuristic,
    OpcodeHeuristic,
    ReturnHeuristic,
    StoreHeuristic,
    LoopHeuristic,
    GuardHeuristic,
};

static  block   *Predictor( block *blk ) {
/*****************************************
    Given a conditional block, return the most likely
    successor of this block.
*/
    block_edge          *edge;
    bp_heuristic        ptr;
    int                 i;
    int                 prediction;
    instruction         *cond;

    edge = FindLoopBackEdge( blk );
    if( edge == NULL ) {
        cond = FindCondition( blk );
        for( i = 0; i < sizeof(Heuristics) / sizeof(Heuristics[0]); i++ ) {
            ptr = Heuristics[ i ];
            prediction = ptr( blk, cond );
            switch( prediction ) {
            case TAKEN:
                return( blk->edge[ _TrueIndex( cond ) ].destination );
            case NOT_TAKEN:
                return( blk->edge[ _FalseIndex( cond ) ].destination );
            }
        }
    }
    /* what the hell, pick one at random */
    return( blk->edge[ 0 ].destination );
}

#define _Placed( x )    (((x)->class&BLOCK_VISITED)!=EMPTY)
#define _MarkPlaced( x )((x)->class|=BLOCK_VISITED)

static  block   *BestFollower( block_queue *unplaced, block *blk ) {
/******************************************************************/

    block       *best;
    block       *curr;
    block_num   i;

    best = NULL;
    switch( ( blk->class & (RETURN|JUMP|CONDITIONAL|SELECT|CALL_LABEL) ) ) {
    case RETURN:
    case JUMP:
    case SELECT:
        for( i = 0; i < blk->targets; i++ ) {
            best = blk->edge[ i ].destination;
            if( !_Placed( best ) ) return( best );
        }
        best = NULL;
        break;
    case CONDITIONAL:
        /*
         * If exactly one of the followers has already been placed,
         * then the other one is obviously the best candidate. Otherwise,
         * we run branch prediction if neither is placed, or return NULL
         * if both have been placed.
         */
        #define _Munge( a, b )  ( ( (a) << 8 ) + (b) )
        switch( _Munge( _Placed( blk->edge[ 0 ].destination ),
                        _Placed( blk->edge[ 1 ].destination ) ) ) {
        case _Munge( 0, 0 ):
            /* get some branch prediction going here */
            best = Predictor( blk );
            break;
        case _Munge( 1, 0 ):
            best = blk->edge[ 1 ].destination;
            break;
        case _Munge( 0, 1 ):
            best = blk->edge[ 0 ].destination;
            break;
        case _Munge( 1, 1 ):
            best = NULL;
            break;
        }
        break;
    case CALL_LABEL:
        for( curr = BQFirst( unplaced ); curr != NULL; curr = BQNext( unplaced, curr ) ) {
            if( curr->gen_id == ( blk->gen_id + 1 ) ) {
                best = curr;
                break;
            }
        }
        assert( best != NULL );
        assert( ( best->class & RETURNED_TO ) != EMPTY );
        break;
    }
    return( best );
}

extern  void    SortBlocks( void )
/********************************/
{
    block_queue unplaced;
    block_queue placed;
    block       *curr;
    block       *next;
    block       *ret_block;

    ClearBlockBits( BLOCK_VISITED );
    BlocksSortedBy( GenId );
    if( _IsModel( NO_OPTIMIZATION ) ) return;
    if( _IsntModel( BRANCH_PREDICTION ) ) return;
    if( OptForSize > 50 ) return;
    // we can't screw about with the placement of the return
    // block when we are outputting records which mark the start
    // of the epilog etc...
    if( _IsModel( DBG_LOCALS ) ) return;
    BQInit( &unplaced );
    BQInit( &placed );
    for( curr = HeadBlock; curr != NULL; curr = next ) {
        next = curr->next_block;
        BQAdd( &unplaced, curr );
        if( ( curr->class & RETURNED_TO ) != EMPTY ) {
            // blocks which are returned to by a call_label routine
            // should not be placed because they are special cased in
            // BestFollower to come out directly after the CALL_LABEL
            // block
            _MarkPlaced( curr );
        }
        ret_block = curr;
    }
    while( !BQEmpty( &unplaced ) ) {
        curr = BQRemove( &unplaced, NULL );
        if( _Placed( curr ) ) continue;
        while( 1 ) {
            BQAdd( &placed, curr );
            _MarkPlaced( curr );
            curr = BestFollower( &unplaced, curr );
            if( curr == NULL ) break;
            BQRemove( &unplaced, curr );
        }
    }
    HeadBlock = placed.first;
    ClearBlockBits( BLOCK_VISITED );
}