/* LSU EE 7700-1, Computer Architecture Research Methods
   Spring 2006

   Live classroom example of writing a local history branch predictor
   analyzer for Shade.

 */

#define TR_REGS
#include <stdio.h>
#include <stdlib.h>

#include <IHASH.h>
#include <ITYPES.h>
#include <trace.h>
#include <stdtr.h>
#include <trctl.h>

static void sim_init(int argc, char **argv);
static void sim_analyzer();
static void sim_results_write();

static void bp_init(int argc, char **argv);
static void bp_predict(int pc, int outcome);
static void bp_results_write();

int shade_main(int argc, char **argv)
{
  sim_init(argc, argv);
  bp_init(argc, argv);

  shade_trctl_trsize( sizeof(Trace) );    /*  Initialize. */
  shade_trctl_it(IT_ANY, 1, 0,
                 TC_TAKEN | TC_PC | TC_IH );   /*  Tell shade what to collect. */
  shade_shell(sim_analyzer);     /*  Start. (Returns after analyzer done.) */
  sim_results_write();
  bp_results_write();
  return 0;
}

struct Sim_Info_s
{
  int icount;   /* Number of instructions.   */
  int ibranch;  /* Number of integer branches. */
};

typedef struct Sim_Info_s Sim_Info;
Sim_Info sim_info;

void
sim_init(int argc, char **argv)
{
  sim_info.icount = 0;
  sim_info.ibranch = 0;
}

void
sim_analyzer()
{
  /*  /data4/koppel/shadekit/shade.v9.elf/src/include/trace.h  */
  Trace *trace_entry;

  while( ( trace_entry = shade_step() ) )
    {
      /* One iteration per (traced) instruction.  */

      int ih = trace_entry->tr_ih;  /*  Information about instruction.  */
      int prediction;
      int *elt;

      sim_info.icount++;

      if( !ih_isbicc(ih) ) continue;

      sim_info.ibranch++;

      bp_predict(trace_entry->tr_pc,trace_entry->tr_taken);
    }
}

void
sim_results_write()
{
  printf("Found %d instructions of which %d were branches.\n",
         sim_info.icount, sim_info.ibranch);
}


/* ************************************************************************ */

struct Branch_Predictor_s
{
  int bht_sizelg, bht_size, bht_mask;
  int *bht;
  char *pht;
  int pht_size,pht_mask;
  int history_len;
  int correct, wrong;
};

typedef struct Branch_Predictor_s Branch_Predictor;

Branch_Predictor bp;


void
bp_init(int argv, char **argc)
{
  int i;
  bp.wrong = bp.correct = 0;
  bp.bht_sizelg = atoi(argc[1]);
  bp.bht_size = 1 << bp.bht_sizelg;
  bp.bht_mask = bp.bht_size - 1;
  bp.bht = (int*) malloc( bp.bht_size * sizeof(bp.bht[0]) );

  bp.history_len = atoi(argc[2]);
  bp.pht_size = 1 << bp.history_len;
  bp.pht_mask = bp.pht_size -1;

  bp.pht = (char*) malloc( bp.pht_size * sizeof(bp.pht[0]) );

  /* Note: The line below does not make sense for the local history
     predictor, it did serve a purpose in the bimodal predictor which
     is what this code simulated before being modified. */
  for(i=0; i<bp.bht_size; i++) bp.bht[i] = 1;
}


void
bp_predict(int pc, int outcome)
{
  int *local_history = &bp.bht[ ( pc >> 2 ) & bp.bht_mask ];

  char *elt = &bp.pht[ *local_history ];

  int prediction = *elt > 1;

  *local_history = ( ( *local_history << 1 ) + outcome ) & bp.pht_mask;

  if( prediction == outcome ) bp.correct++; else bp.wrong++;
  if(  outcome && *elt < 3 ) elt[0]++;
  if( !outcome && *elt > 0 ) elt[0]--;
}

void
bp_results_write()
{
  printf("For table size lg %d\n",bp.bht_sizelg);
  printf("Accuracy %.3f\n", ((double)bp.correct)/(bp.correct+bp.wrong));
}