bpred.cc

linux下基于c++的处理器仿真平台。具有处理器流水线

/*
 * bpred.cc - branch predictor routines
 *
 * This file is a part of the SimpleScalar tool suite written by
 * Todd M. Austin as a part of the Multiscalar Research Project.
 *
 * The tool suite is currently maintained by Doug Burger and Todd M. Austin.
 *
 * Copyright (C) 1994, 1995, 1996, 1997, 1998 by Todd M. Austin
 *
 * This source file is distributed "as is" in the hope that it will be
 * useful.  The tool set comes with no warranty, and no author or
 * distributor accepts any responsibility for the consequences of its
 * use.
 *
 * Everyone is granted permission to copy, modify and redistribute
 * this tool set under the following conditions:
 *
 *    This source code is distributed for non-commercial use only.
 *    Please contact the maintainer for restrictions applying to
 *    commercial use.
 *
 *    Permission is granted to anyone to make or distribute copies
 *    of this source code, either as received or modified, in any
 *    medium, provided that all copyright notices, permission and
 *    nonwarranty notices are preserved, and that the distributor
 *    grants the recipient permission for further redistribution as
 *    permitted by this document.
 *
 *    Permission is granted to distribute this file in compiled
 *    or executable form under the same conditions that apply for
 *    source code, provided that either:
 *
 *    A. it is accompanied by the corresponding machine-readable
 *       source code,
 *    B. it is accompanied by a written offer, with no time limit,
 *       to give anyone a machine-readable copy of the corresponding
 *       source code in return for reimbursement of the cost of
 *       distribution.  This written offer must permit verbatim
 *       duplication by anyone, or
 *    C. it is distributed by someone who received only the
 *       executable form, and is accompanied by a copy of the
 *       written offer of source code that they received concurrently.
 *
 * In other words, you are welcome to use, share and improve this
 * source file.  You are forbidden to forbid anyone else to use, share
 * and improve what you give them.
 *
 * INTERNET: [e-mail]
 * US Mail:  1210 W. Dayton Street, Madison, WI 53706
 *
 */

#include <cassert>
#include <cmath>
#include <string>

#include "base/cprintf.hh"
#include "base/misc.hh"
#include "base/statistics.hh"
#include "cpu/smt.hh"
#include "encumbered/cpu/full/bpred.hh"
#include "encumbered/cpu/full/cpu.hh"
#include "sim/builder.hh"
#include "sim/host.hh"
#include "sim/stats.hh"

using namespace std;

#define NBIT_MASK(n)		((1 << (n)) - 1)
#define IS_POWER_OF_TWO(n)	(((n) & ((n) - 1)) == 0)

#define BP_VERBOSE 0


/*
 * Is two-bit counter value strongly biased?
 */
#define TWOBIT_STRONG(x)	((x) == 0 || (x) == 3)

/*
 * Do  two-bit counter values agree?
 */
#define TWOBIT_AGREE(x,y)	(((x) >= 2) == ((y) >= 2))

//
// This should be stuck into the BranchPred structure, but I'm not
// quite sure what it's for... (other than something
// confidence-related)
static int conf_table[64];

// branch predictor constructor
BranchPred::BranchPred(const string &_name,
		       BPredClass _bp_class, // type of predictor
		       unsigned int _global_hist_bits,
		       unsigned int _global_pred_index_bits,
		       bool _global_xor,
		       unsigned int _num_local_hist_regs,
		       unsigned int _local_hist_bits,
		       unsigned int _local_pred_index_bits,
		       bool _local_xor,
		       unsigned int _meta_pred_index_bits,
		       bool _meta_xor,
		       unsigned int btb_sets,  // number of sets in BTB
		       unsigned int btb_assoc, // BTB associativity
		       unsigned int _ras_size,  // num entries in RAS
		       bool _conf_pred_enable,
		       unsigned int _conf_pred_index_bits,
		       unsigned int _conf_pred_ctr_bits,
		       int _conf_pred_ctr_thresh,
		       bool _conf_pred_xor,
		       ConfCounterType _conf_pred_ctr_type)
    : SimObject(_name),
      cpu(NULL),	// initialized later via setCPU()
      bp_class(_bp_class),
      global_hist_bits(_global_hist_bits),
      global_pred_table(NULL),
      global_pred_index_bits(_global_pred_index_bits),
      global_xor(_global_xor),
      num_local_hist_regs(_num_local_hist_regs),
      local_hist_bits(_local_hist_bits),
      local_pred_table(NULL),
      local_pred_index_bits(_local_pred_index_bits),
      local_xor(_local_xor),
      meta_pred_table(NULL),
      meta_pred_index_bits(_meta_pred_index_bits),
      meta_xor(_meta_xor),
      ras_size(_ras_size),
      conf_pred_enable(_conf_pred_enable),
      conf_pred_index_bits(_conf_pred_index_bits),
      conf_pred_ctr_bits(_conf_pred_ctr_bits),
      conf_pred_ctr_thresh(_conf_pred_ctr_thresh),
      conf_pred_xor(_conf_pred_xor),
      conf_pred_ctr_type(_conf_pred_ctr_type)
{
    int i;

    if (conf_pred_ctr_thresh == -1) {
	/* static confidence assignment: high confidence iff both
	 * predictors strong & agree.  conf_table is 1 for high confidence.
	 * index value is meta|local|global (2 bits each). */
	for (i = 0; i < 64; i++) {
	    int local = (i >> 2) & 3;
	    int global = i & 0x3;
	    conf_table[i] = (local == global) && TWOBIT_STRONG(local);
	}
    } else if (conf_pred_ctr_thresh == -2) {
	/* static confidence assignment: high confidence iff both
	 * predictors strong & agree OR meta strong, prediction indicated by
	 * meta is strong, other prediction agrees (maybe only weakly) */
	for (i = 0; i < 64; i++) {
	    int meta = (i >> 4) & 3;
	    int local = (i >> 2) & 3;
	    int global = i & 0x3;
	    conf_table[i] = ((local == global) &&TWOBIT_STRONG(local))
		|| (TWOBIT_STRONG(meta)
		    && ((meta >= 2) ? TWOBIT_STRONG(local) :
			TWOBIT_STRONG(global))
		    && TWOBIT_AGREE(local, global));

	}
    } else if (conf_pred_ctr_thresh >= 0) {
	/* dynamic counters determine confidence: initialize them */
	for (i = 0; i < 64; i++)
	    conf_table[i] = (1 << conf_pred_ctr_bits) - 1;
    } else
	panic("conf_pred_ctr_thresh is negative!\n");

    if (bp_class == BPredComb || bp_class == BPredGlobal) {
	/* allocate global predictor */
	unsigned pred_table_size = 1 << global_pred_index_bits;

	global_pred_table = new uint8_t[pred_table_size];

	/* initialize history regs (for repeatable results) */
	for (i = 0; i < SMT_MAX_THREADS; ++i)
	    global_hist_reg[i] = 0;

	/* initialize to weakly taken (not that it matters much) */
	for (i = 0; i < pred_table_size; ++i)
	    global_pred_table[i] = 2;

	// confidence predictor only works with COMB or GLOBAL predictor types
	if (conf_pred_enable) {
	    conf_pred_table = new uint8_t[1 << conf_pred_index_bits];

	    for (i = 0; i < (1 << conf_pred_index_bits); ++i)
		conf_pred_table[i] = 0;

	    if (conf_pred_ctr_bits > 8)
		fatal("bpred_create: confidence counter has max of 8 bits");

	    if (conf_pred_ctr_thresh >= (1 << conf_pred_ctr_bits))
		fatal("bpred_create: confidence threshold has max value of %d",
		      (1 << conf_pred_ctr_bits));
	} else
	  conf_pred_table = 0;
    } else {
	// no global predictor: config incompatible with confidence predictor
	if (conf_pred_enable)
	    fatal("confidence predictor only works with hybrid or global "
		  "branch predictor types");
    }

    if (bp_class == BPredComb || bp_class == BPredLocal) {
	/* allocate local predictor */
	unsigned pred_table_size = 1 << local_pred_index_bits;

	local_pred_table = new uint8_t[pred_table_size];

	if (!IS_POWER_OF_TWO(num_local_hist_regs))
	    fatal("number of local history regs must be a power of two");
	local_hist_regs = new unsigned int[num_local_hist_regs];

	/* initialize history registers */
	for (i = 0; i < num_local_hist_regs; ++i)
	    local_hist_regs[i] = 0;

	/* initialize to weakly taken (not that it matters much) */
	for (i = 0; i < pred_table_size; ++i)
	    local_pred_table[i] = 2;
    }
    if (bp_class == BPredComb) {
	/* allocate meta predictor */
	unsigned pred_table_size = 1 << meta_pred_index_bits;

	meta_pred_table = new uint8_t[pred_table_size];

	/* initialize to weakly favor global (not that it matters much) */
	for (i = 0; i < pred_table_size; ++i)
	    meta_pred_table[i] = 1;
    }

    /* allocate BTB */
    if (!btb_sets || !IS_POWER_OF_TWO(btb_sets))
	fatal("number of BTB sets must be non-zero and a power of two");
    if (!btb_assoc || !IS_POWER_OF_TWO(btb_assoc))
	fatal("BTB associativity must be non-zero and a power of two");

    btb.btb_data = new BTBEntry[btb_sets * btb_assoc];
    btb.sets = btb_sets;
    btb.assoc = btb_assoc;

    /* initialize BTB entries (for repeatable results) */
    for (i = 0; i < (btb.assoc * btb.sets); i++) {
	btb.btb_data[i].addr = btb.btb_data[i].target = 0;
	btb.btb_data[i].next = btb.btb_data[i].prev = 0;
    }

    /* if BTB is set-associative, initialize per-set LRU chains */
    if (btb.assoc > 1) {
	for (i = 0; i < (btb.assoc * btb.sets); i++) {
	    if (i % btb.assoc != btb.assoc - 1)
		btb.btb_data[i].next = &btb.btb_data[i + 1];
	    else
		btb.btb_data[i].next = NULL;

	    if (i % btb.assoc != btb.assoc - 1)
		btb.btb_data[i + 1].prev = &btb.btb_data[i];
	}
    }

    /* allocate return-address stack */
    if (!IS_POWER_OF_TWO(ras_size))
	fatal("Return-address-stack size must be zero or a power of two");

    if (ras_size) {
	for (i = 0; i < SMT_MAX_THREADS; i++) {
	    retAddrStack[i].stack = new Addr[ras_size];
	    // clear stack entries (for repeatable results)
	    for (int j = 0; j < ras_size; ++j)
		retAddrStack[i].stack[j] = 0;
	    retAddrStack[i].tos = ras_size - 1;
	}
    }
}

void
BranchPred::regStats( )
{
    using namespace Stats;

    lookups
	.init(cpu->number_of_threads)
	.name(name() + ".lookups")
	.desc("num BP lookups")
	.flags(total)
	;

    cond_predicted
	.init(cpu->number_of_threads)
	.name(name() + ".cond_predicted")
	.desc("num committed conditional branches")
	.flags(total)
	;

    cond_correct
	.init(cpu->number_of_threads)
	.name(name() + ".cond_correct")
	.desc("num correct dir predictions")
	.flags(total)
	;

    btb_lookups
	.init(cpu->number_of_threads)
	.name(name() + ".btb_lookups")
	.desc("Number of BTB lookups")
	.flags(total)
	;

    btb_hits
	.init(cpu->number_of_threads)
	.name(name() + ".btb_hits")
	.desc("Number of BTB hits")
	.flags(total)
	;

    used_btb
	.init(cpu->number_of_threads)
	.name(name() + ".used_btb")
	.desc("num committed branches using target from BTB")
	.flags(total)
	;

    btb_correct
	.init(cpu->number_of_threads)
	.name(name() + ".btb_correct")
	.desc("num correct BTB predictions")
	.flags(total)
	;

    used_ras
	.init(cpu->number_of_threads)
	.name(name() + ".used_ras")
	.desc("num returns predicted using RAS")
	.flags(total)
	;

    ras_correct
	.init(cpu->number_of_threads)
	.name(name() + ".ras_correct")
	.desc("num correct RAS predictions")
	.flags(total)
	;

    switch (bp_class) {
    case BPredComb:
	pred_state_table_size = 64;	/* bit patterns */
	break;

    case BPredGlobal:
    case BPredLocal:
	pred_state_table_size = 16;
	break;

    default:
	fatal("bad bpred class");
    }


    for (int i = 0; i < NUM_PRED_STATE_ENTRIES; i++)
	pred_state[i].init(pred_state_table_size);


    conf_chc.init(cpu->number_of_threads);
    conf_clc.init(cpu->number_of_threads);
    conf_ihc.init(cpu->number_of_threads);
    conf_ilc.init(cpu->number_of_threads);

    corr_conf_dist.init(/* base value */ 0,
			/* array size - 1*/
			(1 << conf_pred_ctr_bits) - 1,
			/* bucket size */ 1);

    incorr_conf_dist.init(/* base value */ 0,
			  /* array size - 1*/
			  (1 << conf_pred_ctr_bits) - 1,
			  /* bucket size */ 1);


    if (conf_pred_enable) {

	conf_chc
	    .name(name() + ".conf.cor_high")
	    .desc("num correct preds with high confidence")
	    .flags(total)
	    ;

	conf_clc
	    .name(name() + ".conf.cor_low")
	    .desc("num correct preds with low confidence")
	    .flags(total)
	    ;

	conf_ihc
	    .name(name() + ".conf.incor_high")
	    .desc("num incorrect preds with high confidence")
	    .flags(total)
	    ;

	conf_ilc
	    .name(name() + ".conf.incor_low")
	    .desc("num incorrect preds with low confidence")
	    .flags(total)
	    ;

	corr_conf_dist
	    .name(name() + ".conf.cor.dist")
	    .desc("Number of correct predictions for each confidence value")
	    .flags(pdf)
	    ;

	incorr_conf_dist
	    .name(name() + ".conf.incor.dist")
	    .desc("Number of incorrect predictions for each confidence value")
	    .flags(pdf)
	    ;
    }
}

void
BranchPred::regFormulas()
{
    using namespace Stats;

    lookup_rate
	.name(name() + ".lookup_rate")
	.desc("Rate of bpred lookups")
	.flags(total)
	;
    lookup_rate = lookups / cpu->numCycles;

    dir_accuracy
	.name(name() + ".dir_accuracy")
	.desc("fraction of predictions correct")
	.flags(total)
	;
    dir_accuracy = cond_correct / cond_predicted;

    btb_hit_rate
	.name(name() + ".btb_hit_rate")
	.desc("BTB hit ratio")
	.flags(total)
	;
    btb_hit_rate = btb_hits / btb_lookups;

    btb_accuracy
	.name(name() + ".btb_accuracy")
	.desc("fraction of BTB targets correct")
	.flags(total)
	;
    btb_accuracy = btb_correct / used_btb;

    ras_accuracy
	.name(name() + ".ras_accuracy")
	.desc("fraction of RAS targets correct")
	.flags(total)
	;
    ras_accuracy = ras_correct / used_ras;

    if (conf_pred_enable) {
	conf_sens
	    .name(name() + ".conf.sens")
	    .desc("Sens: \% correct preds that were HC")
	    .precision(4)
	    ;
	conf_sens = conf_chc / (conf_chc + conf_clc);

	conf_pvp
	    .name(name() + ".conf.pvp")