bpred.cc

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

{
    int ctr = *ctrp;

    if (incr && ctr < 3) {
	++(*ctrp);
	return;
    }

    if (!incr && ctr > 0) {
	--(*ctrp);
	return;
    }
}


// update the branch predictor, only useful for stateful predictors;
// updates entry for instruction type OP at address BADDR.  BTB only
// gets updated for branches which are taken.  Inst was determined to
// jump to address BTARGET and was taken if TAKEN is non-zero.
// Predictor statistics are updated with result of prediction,
// indicated by CORRECT and PRED_TAKEN, predictor state to be updated
// is indicated by *DIR_UPDATE_PTR (may be NULL for jumps, which
// shouldn't modify state bits).  Note if bpred_update is done
// speculatively, branch-prediction may get polluted.
void
BranchPred::update( int thread,	/* thread ID */
		    Addr baddr,	/* branch address */
		    Addr btarget,	/* resolved branch target */
		    int taken,		/* non-zero if branch was taken */
		    int pred_taken,	/* non-zero if branch was pred taken */
		    int correct,	/* was earlier addr prediction ok? */
		    const StaticInstBasePtr &brInst, /* static instruction */
		    BPredUpdateRec *brstate)
{				/* pred state pointer */
    BTBEntry *pbtb = NULL;
    BTBEntry *lruhead = NULL, *lruitem = NULL;
    int index, i;
    unsigned pred_state_idx;
    /* For redundant lagging threads, we can optionally turn off
     * some or all of the updates.  The following flags control
     * this.  Assume we'll update everything unless we decide otherwise. */
    bool update_local_hist = true;
    bool update_counters = true;
    bool update_btb = true;

    /* if we didn't use the predictor on this branch (for
     * leading-thread predictions) don't update */
    if (!brstate->used_predictor)
	return;

    /* don't change bpred state for non-branch instructions */
    if (!brInst->isControl())
	return;

#if BP_VERBOSE
    ccprintf(cerr, "UP: %#08X (cycle %n) ", baddr, curTick);
#endif

    if (brInst->isCondCtrl()) {
	/* conditional branch: update predictor & record statistics */
	unsigned int bindex = baddr >> BranchPredAddrShiftAmt;

#if BP_VERBOSE
	ccprintf(cerr, "COND   ");
#endif

	cond_predicted[thread]++;
	if (taken == pred_taken) {
	    cond_correct[thread]++;
#if BP_VERBOSE
	    ccprintf(cerr, "C ");
	} else {
	    ccprintf(cerr, "I ");
#endif
	}

	/*
	 *  UPDATE LOCAL PREDICTOR
	 *
	 */
	if (local_pred_table) {
	    unsigned local_bindex = bindex;

	    local_bindex &= (num_local_hist_regs - 1);

	    /* update counter used for this branch */
	    if (update_counters)
		update_ctr(&local_pred_table[brstate->local_pidx], taken);

	    /* update history shift register */
	    if (update_local_hist)
		local_hist_regs[local_bindex] =
		    (((local_hist_regs[local_bindex] << 1) | taken)
		     & NBIT_MASK(local_hist_bits));
#if BP_VERBOSE
	    ccprintf(cerr, "LH=%#08X IDX=%#08X CT=%1d ",
		     local_hist_regs[local_bindex], brstate->local_pidx,
		     local_pred_table[brstate->local_pidx]);
#endif
	}
	/*
	 *  UPDATE GLOBAL PREDICTOR
	 *
	 */
	if (global_pred_table) {
	    if (update_counters)
		update_ctr(&global_pred_table[brstate->global_pidx],
			   taken);

#if BP_VERBOSE
	    ccprintf(cerr, "GIDX=%#08X CT=%1d ", brstate->global_pidx,
		    global_pred_table[brstate->global_pidx]);
#endif
	    /* shift reg was already updated speculatively in bpred_lookup() */
	}

	/*
	 *  UPDATE META PREDICTOR
	 *
	 */
	if (meta_pred_table) {
	    bool local_pred = ((brstate->pred_state & 0x8) == 0x8);
	    bool global_pred = ((brstate->pred_state & 0x2) == 0x2);

	    /* update meta-predictor only if global & local disagreed */
	    if (local_pred != global_pred && update_counters) {
		/* increment if local predictor was correct, decrement if
		 * global was correct */
		update_ctr(&meta_pred_table[brstate->meta_pidx],
			   local_pred == taken);
#if BP_VERBOSE
		ccprintf(cerr, "MIDX=%#08X CT=%1d ", brstate->meta_pidx,
			 meta_pred_table[brstate->meta_pidx]);
	    } else {
		ccprintf(cerr, "No_Meta_Update         ");
#endif
	    }
	}

	/*
	 *
	 *  Update Confidence stuff
	 *
	 */
	if (conf_pred_enable) {
	    pred_state_idx = brstate->pred_state;

	    if (conf_pred_table) {
		uint8_t *conf_pred_ctr =
		    &(conf_pred_table[brstate->conf_pidx]);

		//  BPred was correct: Increment the counter if we
		//                     haven't maxed out
		//  BPred was wrong:   Reset the counter
		if (taken == pred_taken) {
		    corr_conf_dist.sample(brstate->conf_value);

		    // correct prediction
		    if (brstate->conf_result == CONF_HIGH)
			conf_chc[thread]++;	// high confidence
		    else
			conf_clc[thread]++;	// low confidence

		    if (*conf_pred_ctr < ((1 << conf_pred_ctr_bits) - 1))
			(*conf_pred_ctr)++;
		} else {
		    incorr_conf_dist.sample(brstate->conf_value);

		    // incorrect prediction
		    if (brstate->conf_result == CONF_HIGH)
			conf_ihc[thread]++;	// high confidence
		    else
			conf_ilc[thread]++;	// low confidence

		    switch (conf_pred_ctr_type) {
		    case CNT_RESET:
			*conf_pred_ctr = 0;
			break;
		    case CNT_SAT:
			if (*conf_pred_ctr > 0)
			    (*conf_pred_ctr)--;
			break;
		    }
		}
	    } else {
		//  Must be using small predictor...
		if (taken == pred_taken) {
		    // correct prediction
		    if (brstate->conf_result == CONF_HIGH)
			conf_chc[thread]++;	// high confidence
		    else
			conf_clc[thread]++;	// low confidence
		} else {
		    // incorrect prediction
		    if (brstate->conf_result == CONF_HIGH)
			conf_ihc[thread]++;	// high confidence
		    else
			conf_ilc[thread]++;	// low confidence
		}

		// first six bits are prediction state, last bit is
		// correct/incorrect
		if (conf_pred_ctr_thresh >= 0) {
		    // using dynamic assignment
		    if (taken == pred_taken) {
			// correct prediction
			if (conf_table[pred_state_idx] <
			    ((1 << conf_pred_ctr_bits) - 1))
			    conf_table[pred_state_idx]++;
		    } else {
			// incorrect prediction
			if (conf_pred_ctr_type == CNT_SAT)
			    if (conf_table[pred_state_idx] > 0)
				conf_table[pred_state_idx]--;
			else
			    conf_table[pred_state_idx] = 0;
		    }
		}
	    }

	    /*
	     *  Update the big predictor table for all cases
	     */
	    if (taken == pred_taken) {
		//  correct prediction
		pred_state[PS_CORRECT][pred_state_idx]++;
		if (brstate->conf_result == CONF_HIGH)
		    pred_state[PS_HC_COR][pred_state_idx]++;
		if (brstate->conf_result == CONF_LOW)
		    pred_state[PS_LC_COR][pred_state_idx]++;
	    } else {
		//  incorrect prediction
		pred_state[PS_INCORRECT][pred_state_idx]++;
		if (brstate->conf_result == CONF_HIGH)
		    pred_state[PS_HC_INCOR][pred_state_idx]++;
		if (brstate->conf_result == CONF_LOW)
		    pred_state[PS_LC_INCOR][pred_state_idx]++;
	    }

	    if (brstate->conf_result == CONF_HIGH)
		pred_state[PS_HIGH_CONF][pred_state_idx]++;
	    if (brstate->conf_result == CONF_LOW)
		pred_state[PS_LOW_CONF][pred_state_idx]++;
	}


#if BP_VERBOSE
	ccprintf(cerr, "\n");
    } else {
	ccprintf(cerr, "UNCOND \n");
#endif
    }

    if (taken) {
	if (brstate->used_ras) {
	    /* used RAS... */
	    used_ras[thread]++;

	    DPRINTF(BPredRAS, "RAS update br %#x tgt %#x %s\n", baddr, btarget,
		     correct ? "correct" : "incorrect");

	    if (correct)
		ras_correct[thread]++;

	    /* no need to update BTB */
	    return;
	}

	if (brstate->used_btb) {
	    used_btb[thread]++;
	    if (correct)
		btb_correct[thread]++;
	}

	/* update BTB */
	if (update_btb) {
	    index = (baddr >> BranchPredAddrShiftAmt) & (btb.sets - 1);

	    if (btb.assoc > 1) {
		index *= btb.assoc;

		/* Now we know the set; look for a PC match; also identify
		 * MRU and LRU items */
		for (i = index; i < (index + btb.assoc); i++) {
		    if (btb.btb_data[i].addr == baddr) {
			/* match */
			assert(!pbtb);
			pbtb = &btb.btb_data[i];
		    }
		    dassert(btb.btb_data[i].prev
			    != btb.btb_data[i].next);
		    if (btb.btb_data[i].prev == NULL) {
			/* this is the head of the lru list, ie
			 * current MRU item */
			dassert(lruhead == NULL);
			lruhead = &btb.btb_data[i];
		    }
		    if (btb.btb_data[i].next == NULL) {
			/* this is the tail of the lru list, ie the LRU item */
			dassert(lruitem == NULL);
			lruitem = &btb.btb_data[i];
		    }
		}
		dassert(lruhead && lruitem);

		if (!pbtb)
		    /* missed in BTB; choose the LRU item in this set
		     * as the victim */
		    pbtb = lruitem;
		/* else hit, and pbtb points to matching BTB entry */

		/* Update LRU state: selected item, whether selected
		 * because it matched or because it was LRU and
		 * selected as a victim, becomes MRU */
		if (pbtb != lruhead) {
		    /* this splices out the matched entry... */
		    if (pbtb->prev)
			pbtb->prev->next = pbtb->next;
		    if (pbtb->next)
			pbtb->next->prev = pbtb->prev;
		    /* ...and this puts the matched entry at the head */
		    pbtb->next = lruhead;
		    pbtb->prev = NULL;
		    lruhead->prev = pbtb;
		    dassert(pbtb->prev || pbtb->next);
		    dassert(pbtb->prev != pbtb->next);
		}
		/* else pbtb is already MRU item; do nothing */
	    } else {
		/* direct-mapped BTB */
		pbtb = &btb.btb_data[index];
	    }

	    if (pbtb) {
		/* update current information */
		if (pbtb->addr == baddr) {
		    if (!correct)
			pbtb->target = btarget;
		} else {
		    /* enter a new branch in the table */
		    pbtb->addr = baddr;
		    pbtb->target = btarget;
		}
	    }
	}
    }
}


/**
 * Pop top element off of return address stack.  Used to fix up RAS
 * after a SkipFuncEvent (see pc_event.cc).
 */
void
BranchPred::popRAS(int thread)
{
    ReturnAddrStack *ras = &retAddrStack[thread];
#if TRACING_ON
    int old_tos = ras->tos;
#endif

    ras->tos--;
    if (ras->tos < 0)
	ras->tos = ras_size - 1;

    DPRINTF(BPredRAS, "RAS pop %d -> %d\n", old_tos, ras->tos);
}


BEGIN_DECLARE_SIM_OBJECT_PARAMS(BranchPred)

    SimpleEnumParam<BPredClass> pred_class;
    Param<unsigned> global_hist_bits;
    Param<unsigned> global_index_bits;
    Param<bool> global_xor;
    Param<unsigned> local_hist_regs;
    Param<unsigned> local_hist_bits;
    Param<unsigned> local_index_bits;
    Param<bool> local_xor;
    Param<unsigned> choice_index_bits;
    Param<bool> choice_xor;
    Param<unsigned> btb_size;
    Param<unsigned> btb_assoc;
    Param<unsigned> ras_size;
    Param<bool> conf_pred_enable;
    Param<unsigned> conf_pred_index_bits;
    Param<unsigned> conf_pred_ctr_bits;
    Param<int> conf_pred_ctr_thresh;
    Param<bool> conf_pred_xor;
    SimpleEnumParam<ConfCounterType> conf_pred_ctr_type;

END_DECLARE_SIM_OBJECT_PARAMS(BranchPred)

// parameter strings for enum BPredClass
const char *bpred_class_strings[] =
{
    "hybrid", "global", "local"
};

// parameter strings for enum ConfCounterType
const char *conf_counter_type_strings[] =
{
    "resetting", "saturating"
};

BEGIN_INIT_SIM_OBJECT_PARAMS(BranchPred)

    INIT_ENUM_PARAM(pred_class, "predictor class",
		    bpred_class_strings),
    INIT_PARAM(global_hist_bits, "global predictor history reg bits"),
    INIT_PARAM(global_index_bits, "global predictor index bits"),
    INIT_PARAM(global_xor, "XOR global hist w/PC (false: concatenate)"),
    INIT_PARAM(local_hist_regs, "num. local predictor history regs"),
    INIT_PARAM(local_hist_bits, "local predictor history reg bits"),
    INIT_PARAM(local_index_bits, "local predictor index bits"),
    INIT_PARAM(local_xor, "XOR local hist w/PC (false: concatenate)"),
    INIT_PARAM(choice_index_bits, "choice predictor index bits"),
    INIT_PARAM(choice_xor, "XOR choice hist w/PC (false: concatenate)"),
    INIT_PARAM(btb_size, "number of entries in BTB"),
    INIT_PARAM(btb_assoc, "BTB associativity"),
    INIT_PARAM(ras_size, "return address stack size"),
    INIT_PARAM_DFLT(conf_pred_enable, "enable confidence predictor", false),
    INIT_PARAM(conf_pred_index_bits, "confidence predictor index bits"),
    INIT_PARAM(conf_pred_ctr_bits, "confidence predictor counter bits"),
    INIT_PARAM(conf_pred_ctr_thresh, "confidence predictor threshold"),
    INIT_PARAM(conf_pred_xor, "XOR confidence predictor bits"),
    INIT_ENUM_PARAM(conf_pred_ctr_type, "confidence predictor type",
		    conf_counter_type_strings)

END_INIT_SIM_OBJECT_PARAMS(BranchPred)


CREATE_SIM_OBJECT(BranchPred)
{
    // These flags are used to avoid evaluating parameters that have
    // no meaning in a given context (like global predictor parameters
    // when the selected predictor type is local).  It would be neater
    // to have different subclasses for the different predictor types,
    // but (1) it would be too big a rewrite of this old code, (2) we
    // never really use anything but the hybrid predictor anyway, and
    // (3) the performance hit from virtualizing all the BPred calls
    // might be noticeable.
    bool need_local  = pred_class == BPredComb || pred_class == BPredLocal;
    bool need_global = pred_class == BPredComb || pred_class == BPredGlobal;
    bool need_meta = pred_class == BPredComb;
    bool need_conf = conf_pred_enable;

    return new BranchPred(getInstanceName(),
			  pred_class,
			  need_global ? global_hist_bits : 0,
			  need_global ? global_index_bits : 0,
			  need_global ? global_xor : false,
			  need_local ? local_hist_regs : 0,
			  need_local ? local_hist_bits : 0,
			  need_local ? local_index_bits : 0,
			  need_local ? local_xor : false,
			  need_meta ? choice_index_bits : 0,
			  need_meta ? choice_xor : false,
			  btb_size / btb_assoc, btb_assoc,
			  ras_size,
			  conf_pred_enable,
			  need_conf ? conf_pred_index_bits : 0,
			  need_conf ? conf_pred_ctr_bits : 0,
			  need_conf ? conf_pred_ctr_thresh : 0,
			  need_conf ? conf_pred_xor : false,
			  need_conf ? conf_pred_ctr_type : CNT_RESET);
}

REGISTER_SIM_OBJECT("BranchPred", BranchPred)