/* * 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: dburger@cs.wisc.edu * 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 constructorBranchPred::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;	}    }}voidBranchPred::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)	    ;    }}voidBranchPred::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")