bpred.phalanx_history.c

uploading the file , the system will delete the file when time expires

/* bpred.c - branch predictor routines */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <assert.h>

#include "host.h"
#include "misc.h"
#include "machine.h"
#include "bpred.h"

// phalanx definitions
#include "phalanx.h"

// turn this on to enable dumping of preditions and resolutions (0 == on) (1==off)
#define PRINT_PREDS 1
#define PRINT_RESOL 1

/* turn this on to enable the SimpleScalar 2.0 RAS bug */
/* #define RAS_BUG_COMPATIBLE */

FILE * outfile;

// returns the number of 1's in the integer parameter
int popCount(int x) {
  int count = 0;
  int mask = 0x00000001;
  int i;
  for(i=0;i<NBITS_PHALANX_HISTORY;i++) {
    if((x&mask)!=0) count++;
    mask = mask << 1;
  }

  return count;
}

// returns the number of trailing 1's in the integer param
int trailingCount(int x) {
  int count = 0;
  int mask = 0x00000001;
  int i;
  for(i=0;i<NBITS_PHALANX_HISTORY;i++) {
    if((x&mask)!=0) {
      count++;
      mask = mask << 1;
    } else {
      return count;
    }

  }

  return count;
}

// retuns an int..the number of the predictor with best history
int selectPred(struct bpred_t * pred) {
  int predWorth[NPREDS_PHALANX];
  int i;
  int max_worth = -1;
  int max_pop = -1;
  for(i=0;i<NPREDS_PHALANX;i++) {
    predWorth[i] = trailingCount(pred->phalanx.histories[i]);
    if(max_worth<predWorth[i]) max_worth = predWorth[i];
  }

  for(i=0;i<NPREDS_PHALANX;i++) {
    if(predWorth[i]==max_worth) {
      predWorth[i] = popCount(pred->phalanx.histories[i]);
      if(max_pop<predWorth[i]) max_pop = predWorth[i];
    } else {
      predWorth[i] = -1;
    }
  }

  // now find and return a predictor with predworth = max_pop
  for(i=0;i<NPREDS_PHALANX;i++) {
    if(predWorth[i]==max_pop) return i;
    else continue;
  }

  return 0;
}

// for bpred_update, updates the history bits according to correct
void updatePhalanxMember(struct bpred_t * pred, // the top-level predictor
                         int predNumber,
                         int correct) {
  // shift the history bits
  pred->phalanx.histories[predNumber] =
    pred->phalanx.histories[predNumber] << 1;

  if(correct) {
    // or-in a 1
    pred->phalanx.histories[predNumber] =
      pred->phalanx.histories[predNumber] | 0x00000001;
  } else {
    // and-in a 0
    pred->phalanx.histories[predNumber] =
      pred->phalanx.histories[predNumber] & 0xFFFFFFFE;
  }

}

/* create a branch predictor */
struct bpred_t *			/* branch predictory instance */
bpred_create(enum bpred_class class,	/* type of predictor to create */
	     unsigned int bimod_size,	/* bimod table size */
	     unsigned int l1size,	/* 2lev l1 table size */
	     unsigned int l2size,	/* 2lev l2 table size */
	     unsigned int meta_size,	/* meta table size */
	     unsigned int shift_width,	/* history register width */
	     unsigned int xor,  	/* history xor address flag */
	     unsigned int btb_sets,	/* number of sets in BTB */ 
	     unsigned int btb_assoc,	/* BTB associativity */
	     unsigned int retstack_size) /* num entries in ret-addr stack */
{
  // this is what will eventually be returned
  struct bpred_t *pred;

  // allocate space for the predictor structure
  if (!(pred = calloc(1, sizeof(struct bpred_t))))
    fatal("out of virtual memory");

  if(PRINT_PREDS==0||PRINT_RESOL==0) {
    outfile = fopen("predtrace","w");
  }

  // assign the type of predictor (from params)
  pred->class = class;

  // call sub-constructtors for stateful predictors
  switch (class) {
  case BPredPhalanx:
    // call sub-constructors if enabled for gag,pag,pap,gshare,bimod
    if(GAG_ENABLE)
    pred->phalanx.gag =
      bpred_create(BPred2Level,0,1,1<<shift_width,0,shift_width,0,btb_sets,
                   btb_assoc,retstack_size);

    if(PAG_ENABLE)
    pred->phalanx.pag =
      bpred_create(BPred2Level,0,l1size,1<<shift_width,0,shift_width,0,
                   btb_sets,btb_assoc,retstack_size);

    if(PAP_ENABLE)
    pred->phalanx.pap =
      bpred_create(BPred2Level,0,l1size,1<<(shift_width+l1size),0,shift_width,0,
                   btb_sets,btb_assoc,retstack_size);

    if(GSHARE_ENABLE)
    pred->phalanx.gshare =
      bpred_create(BPred2Level,0,1,1<<shift_width,0,shift_width,1, // XOR = yes
                   btb_sets,btb_assoc,retstack_size);

    if(BIMOD_ENABLE)
    pred->phalanx.bimod =
      bpred_create(BPred2bit,bimod_size,0,0,0,0,0,btb_sets,btb_assoc,retstack_size);

    // allocate space for the history bits for each predictor
    // note: calloc automatically zeroes the bits
    pred->phalanx.histories = calloc(NPREDS_PHALANX,sizeof(int));
     
    break;
  case BPredComb:
    /* bimodal component */
    pred->dirpred.bimod = 
      bpred_dir_create(BPred2bit, bimod_size, 0, 0, 0);

    /* 2-level component */
    pred->dirpred.twolev = 
      bpred_dir_create(BPred2Level, l1size, l2size, shift_width, xor);

    /* metapredictor component */
    pred->dirpred.meta = 
      bpred_dir_create(BPred2bit, meta_size, 0, 0, 0);

    break;

  case BPred2Level:
    pred->dirpred.twolev = 
      bpred_dir_create(class, l1size, l2size, shift_width, xor);

    break;

  case BPred2bit:
    pred->dirpred.bimod = 
      bpred_dir_create(class, bimod_size, 0, 0, 0);

  /* Non-stateful predictors go here */
  case BPredTaken:
  case BPredNotTaken:
    /* no other state */
    break;

  default:
    panic("bogus predictor class");
  }

  /* allocate ret-addr stack and branch table buffer */
  switch (class) {
  case BPredComb:
  case BPredPhalanx: // do normal allocations for Phalanx
  case BPred2Level:
  case BPred2bit:
    {
      int i;

      /* allocate branch table buffer */
      
      // parameter checking
      if (!btb_sets || (btb_sets & (btb_sets-1)) != 0)
	fatal("number of BTB sets must be non-zero and a power of two");
      if (!btb_assoc || (btb_assoc & (btb_assoc-1)) != 0)
	fatal("BTB associativity must be non-zero and a power of two");

      // allocate the space required
      if (!(pred->btb.btb_data = calloc(btb_sets * btb_assoc,
					sizeof(struct bpred_btb_ent_t))))
	fatal("cannot allocate BTB");

      // set attributes according to parameters
      pred->btb.sets = btb_sets;
      pred->btb.assoc = btb_assoc;

      // if the associativity is greater than 1, the LRU Linked list
      // chain must be set up
      if (pred->btb.assoc > 1)
	for (i=0; i < (pred->btb.assoc*pred->btb.sets); i++)
	  {
	    if (i % pred->btb.assoc != pred->btb.assoc - 1)
	      pred->btb.btb_data[i].next = &pred->btb.btb_data[i+1];
	    else
	      pred->btb.btb_data[i].next = NULL;
	    
	    if (i % pred->btb.assoc != pred->btb.assoc - 1)
	      pred->btb.btb_data[i+1].prev = &pred->btb.btb_data[i];
	  }

      /* allocate retstack */
      if ((retstack_size & (retstack_size-1)) != 0)
	fatal("Return-address-stack size must be zero or a power of two");
      
      pred->retstack.size = retstack_size;
      if (retstack_size)
	if (!(pred->retstack.stack = calloc(retstack_size, 
					    sizeof(struct bpred_btb_ent_t))))
	  fatal("cannot allocate return-address-stack");
      pred->retstack.tos = retstack_size - 1;
      
      break;
    }

  case BPredTaken:
  case BPredNotTaken:
    /* no other state */
    break;

  default:
    panic("bogus predictor class");
  }

  // all done with the constructor, return the predictor
  return pred;
}

/* create a branch direction predictor */
struct bpred_dir_t *		/* branch direction predictor instance */
bpred_dir_create (
  enum bpred_class class,	/* type of predictor to create */
  unsigned int l1size,	 	/* level-1 table size */
  unsigned int l2size,	 	/* level-2 table size (if relevant) */
  unsigned int shift_width,	/* history register width */
  unsigned int xor)	    	/* history xor address flag */
{
  // this is what will eventually be returned
  struct bpred_dir_t *pred_dir;

  // used for initialization--no need to modify these
  unsigned int cnt;
  int flipflop;

  // allocate space for the predictor itself
  if (!(pred_dir = calloc(1, sizeof(struct bpred_dir_t))))
    fatal("out of virtual memory");

  // set the class as per the paremeter
  pred_dir->class = class;

  cnt = -1;

  // here we will create and initialize our additional state
  switch (class) {
  case BPred2Level:
    {
      // parameter checking
      if (!l1size || (l1size & (l1size-1)) != 0)
	fatal("level-1 size, `%d', must be non-zero and a power of two", 
	      l1size);
      pred_dir->config.two.l1size = l1size;
      
      if (!l2size || (l2size & (l2size-1)) != 0)
	fatal("level-2 size, `%d', must be non-zero and a power of two", 
	      l2size);
      pred_dir->config.two.l2size = l2size;
      
      if (!shift_width || shift_width > 30)
	fatal("shift register width, `%d', must be non-zero and positive",
	      shift_width);
      pred_dir->config.two.shift_width = shift_width;
      
      pred_dir->config.two.xor = xor;
      pred_dir->config.two.shiftregs = calloc(l1size, sizeof(int));
      if (!pred_dir->config.two.shiftregs)
	fatal("cannot allocate shift register table");
      
      pred_dir->config.two.l2table = calloc(l2size, sizeof(unsigned char));
      if (!pred_dir->config.two.l2table)
	fatal("cannot allocate second level table");

      /* initialize counters to weakly this-or-that */
      flipflop = 1;
      for (cnt = 0; cnt < l2size; cnt++)
	{
	  pred_dir->config.two.l2table[cnt] = flipflop;
	  flipflop = 3 - flipflop;
	}

      break;
    }

  case BPred2bit:
    // more parameter checking here
    if (!l1size || (l1size & (l1size-1)) != 0)
      fatal("2bit table size, `%d', must be non-zero and a power of two", 
	    l1size);
    pred_dir->config.bimod.size = l1size;

    // actual allocation occurs here
    if (!(pred_dir->config.bimod.table =
	  calloc(l1size, sizeof(unsigned char))))
      fatal("cannot allocate 2bit storage");
    /* initialize counters to weakly this-or-that */
    flipflop = 1;
    for (cnt = 0; cnt < l1size; cnt++)
      {
	pred_dir->config.bimod.table[cnt] = flipflop;
	flipflop = 3 - flipflop;
      }

    break;

  case BPredTaken:
  case BPredNotTaken:
    /* no other state */
    break;

  default:
    panic("bogus branch direction predictor class");
  }

  // done, return the direction predictor
  return pred_dir;
}

/* print branch direction predictor configuration */
void
bpred_dir_config(
  struct bpred_dir_t *pred_dir,	/* branch direction predictor instance */
  char name[],			/* predictor name */
  FILE *stream)			/* output stream */
{
  // print direction prediction configuration, depending on the type of direction predictor
  switch (pred_dir->class) {
  case BPred2Level:
    fprintf(stream,
      "pred_dir: %s: 2-lvl: %d l1-sz, %d bits/ent, %s xor, %d l2-sz, direct-mapped\n",
      name, pred_dir->config.two.l1size, pred_dir->config.two.shift_width,
      pred_dir->config.two.xor ? "" : "no", pred_dir->config.two.l2size);
    break;

  case BPred2bit:
    fprintf(stream, "pred_dir: %s: 2-bit: %d entries, direct-mapped\n",
      name, pred_dir->config.bimod.size);
    break;

  case BPredTaken:
    fprintf(stream, "pred_dir: %s: predict taken\n", name);
    break;

  case BPredNotTaken:
    fprintf(stream, "pred_dir: %s: predict not taken\n", name);
    break;

  case BPredPhalanx:
    fprintf(stream, "Phalanx selected\n");
    break;

  default:
    panic("bogus branch direction predictor class");
  }
}

/* print branch predictor configuration */
void
bpred_config(struct bpred_t *pred,	/* branch predictor instance */
	     FILE *stream)		/* output stream */
{
  // print the branch predictor configuration, depending on the type of predictor
  switch (pred->class) {
  case BPredPhalanx:
    fprintf(stream,"Phalanx configuration:\n");
    fprintf(stream,"GAG:\n");
    if(GAG_ENABLE) bpred_config(pred->phalanx.gag,stream);
    fprintf(stream,"PAG:\n");
    if(PAG_ENABLE) bpred_config(pred->phalanx.pag,stream);
    fprintf(stream,"PAP:\n");
    if(PAP_ENABLE) bpred_config(pred->phalanx.pap,stream);
    fprintf(stream,"GHARE:\n");
    if(GSHARE_ENABLE) bpred_config(pred->phalanx.gshare,stream);
    fprintf(stream,"BIMOD:\n");
    if(BIMOD_ENABLE) bpred_config(pred->phalanx.bimod,stream);
    break;
  case BPredComb:
    bpred_dir_config (pred->dirpred.bimod, "bimod", stream);
    bpred_dir_config (pred->dirpred.twolev, "2lev", stream);
    bpred_dir_config (pred->dirpred.meta, "meta", stream);
    fprintf(stream, "btb: %d sets x %d associativity", 
	    pred->btb.sets, pred->btb.assoc);
    fprintf(stream, "ret_stack: %d entries", pred->retstack.size);
    break;

  case BPred2Level:
    bpred_dir_config (pred->dirpred.twolev, "2lev", stream);
    fprintf(stream, "btb: %d sets x %d associativity",