Thread: How to count Branches

Hi:

In my code below, I have a verbose mode which prints results of a trace file.
I need count the branches that are taken.
Which would be if the branch instruction on the line before is used in the instruction on the next line, then the branch is taken.

How do i create a counter that will count if the line before's address is used...
then count it...

Code:

#include <stdio.h>
// You can include the trace item structure and type by including a header file
#include "mytrace.h"
#define TRACE_BUFSIZE 1024*1024
#include <stdint.h>
#include <stdlib.h>
static FILE *trace_fd;
static int trace_buf_ptr;
static int trace_buf_end;
static struct trace_item *trace_buf;

void trace_init()
{
  trace_buf = (trace_item*)malloc(sizeof(struct trace_item) * TRACE_BUFSIZE);

  if (!trace_buf) {
    fprintf(stdout, "** trace_buf not allocated\n");
    exit(-1);
  }

  trace_buf_ptr = 0;
  trace_buf_end = 0;
}

void trace_uninit()
{
  free(trace_buf);
  fclose(trace_fd);
}

int trace_get_item(struct trace_item **item)
{
  int n_items;

  if (trace_buf_ptr == trace_buf_end) {
    // get new data
    n_items = fread(trace_buf, sizeof(struct trace_item), TRACE_BUFSIZE, trace_fd);
    if (!n_items) return 0;

    trace_buf_ptr = 0;
    trace_buf_end = n_items;
  }

  *item = &trace_buf[trace_buf_ptr];
  trace_buf_ptr++;

  return 1;
}

int main(int argc, char **argv)
{
  struct trace_item *tr_entry;
  size_t size;
  char *trace_file_name;
  int trace_view_on = 0;

  unsigned char t_type = 0;
  unsigned char t_sReg_a= 0;
  unsigned char t_sReg_b= 0;
  unsigned char t_dReg= 0;
  unsigned int t_PC = 0;
  unsigned int t_Addr = 0;

  unsigned int n_items = 0;
  unsigned int n_nop = 0;
  unsigned int n_rtype = 0;
  unsigned int n_itype = 0;
  unsigned int n_load = 0;
  unsigned int n_store = 0;
  unsigned int n_branch = 0;
  unsigned int n_jtype = 0;
  unsigned int n_jrtype = 0;
  unsigned int n_special = 0;
  unsigned int n_unknown = 0;
  unsigned int n_mem_inst = 0;
  unsigned int n_cont_inst = 0;

  if (argc == 1) {
    fprintf(stdout, "\nUSAGE: tv <trace_file> <switch - any character>\n");
    fprintf(stdout, "\n(switch) to turn on or off individual item view.\n\n");
    exit(0);
  }

  trace_file_name = argv[1];
  trace_view_on = (argc == 3);

  fprintf(stdout, "\n ** opening file %s\n", trace_file_name);

  trace_fd = fopen(trace_file_name, "rb");

  if (!trace_fd) {
    fprintf(stdout, "\ntrace file %s not opened.\n\n", trace_file_name);
    exit(0);
  }

  trace_init();

  while(1) {
    size = trace_get_item(&tr_entry);

    if (!size) {
      printf("+ total # items : %u\n", n_items);
      printf("+ # nop: %u\n", n_nop);
      printf("+ # rtype: %u\n", n_rtype);
      printf("+ # itype: %u\n", n_itype);
      printf("+ # load: %u\n", n_load);
      printf("+ # store: %u\n", n_store);
      printf("+ # branch: %u\n", n_branch);
      printf("+ # jtype: %u\n", n_jtype);
      printf("+ # jrtype: %u\n", n_jrtype);
      printf("+ # special: %u\n", n_special);
      printf("+ # unknown: %u\n", n_unknown);
      printf("+ # Avg mem instr: %4.2f\n", (double)n_mem_inst/(double)n_items);
      printf("+ # Avg control instr: %4.2f\n", (double)n_cont_inst/(double)n_items);
      break;
    }
    else{
      n_items++;
      t_type = tr_entry->type;
      t_sReg_a = tr_entry->sReg_a;
      t_sReg_b = tr_entry->sReg_b;
      t_dReg = tr_entry->dReg;
      t_PC = tr_entry->PC;
      t_Addr = tr_entry->Addr;
    }

    switch(tr_entry->type) {

      case ti_NOP:
        if (trace_view_on){
          printf("[item %d] [entry NOP:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_nop++;
        break;

      case ti_RTYPE:
        if (trace_view_on){
          printf("[item %d] [entry RTYPE:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_rtype++;
        break;

     case ti_ITYPE:
        if (trace_view_on){
          printf("[item %d] [entry ITYPE:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_itype++;
        break;

     case ti_LOAD:
        if (trace_view_on){
          printf("[item %d] [entry LOAD:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items,  tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_load++; n_mem_inst++;
        break;

     case ti_STORE:
        if (trace_view_on){
          printf("[item %d] [entry STORE:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_store++; n_mem_inst++;
        break;

     case ti_BRANCH:
        if (trace_view_on){
          printf("[item %d] [entry BRANCH:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }
        n_branch++; n_cont_inst++;
        break;

     case ti_JTYPE:
        if (trace_view_on){
          printf("[item %d] [entry JTYPE:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_jtype++; n_cont_inst++;
        break;

     case ti_SPECIAL:
        if (trace_view_on){
          printf("[item %d] [entry SPECIAL:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_special++; n_cont_inst++;
        break;

     case ti_JRTYPE:
        if (trace_view_on){
          printf("[item %d] [entry JRTYPE:] [(PC: %x)] [(sReg_a: %d)] [(sReg_b: %d)] [(dReg: %d)] [(addr: %x)]\n", n_items, tr_entry->PC, tr_entry->sReg_a, tr_entry->sReg_b, tr_entry->dReg, tr_entry->Addr);
        }

        n_jrtype++; n_cont_inst++;
        break;

      default:
	n_unknown++;
	break;
    }
  }

  trace_uninit();

  exit(0);
}

So make a counter, and in every branch you want to count, add an instruction that adds one to the counter.

but the branch is not always "taken"
if it's taken the branch target address is used in the next called instruction in the trace file.
That is the branch instructions that I need to count.

Originally Posted by husslela2

but the branch is not always "taken"
if it's taken the branch target address is used in the next called instruction in the trace file.
That is the branch instructions that I need to count.

So, if you're allowed to change the source just put a counter in the branches you want to count. If for whatever reason you can't modify the program at all and need to parse the trace file to see the counts, then I guess you need to read lines of the trace file looking for your numbers. (Although the last seems rather odd to me.)

So basically I want to say
if %x for a branch equals %x.next of whatever line item it is whether it could be a load instruction or RTYPE, ITYPE, if the target address equals the branch address
then count that...

how would i do that?

Originally Posted by husslela2

So basically I want to say
if %x for a branch equals %x.next of whatever line item it is whether it could be a load instruction or RTYPE, ITYPE, if the target address equals the branch address
then count that...

how would i do that?

Here's the thing. As far as any of us can tell, your variable n_branch already does everything you're asking for. Or are you modeling a system that is somehow allowed to ignore a branch statement? Or are one of these other statements a "jump if", so that you need to check whether execution continued normally or the jump was taken?

If the branch is "taken" then the target address of the branch is loaded into the PC, otherwise PC gets the address of the instruction immediately after the branch instruction. Use this fact to increment a counter

Code:

if (<addr in PC> equals <target addr of branch>)
    increment counter

ok how would i write that in C and where would i place it in this code?

Originally Posted by husslela2

ok how would i write that in C and where would i place it in this code?

First of all the details in your posts are very sketchy and confusing, so
State requirements clearly, explain the code, and provide concrete examples of what you expect to see.
From your posts it isn't clear what you're trying to do.

This code inputs a trace file, and either will print a count of the different instruction types that are called; either an RType, JType, IType, Branch, PC, etc..
If the "print view" is "on" it prints each line item out from the trace file.
What I WANT to do is to have a "Branches Taken" variable that ONLY counts a branch instruction in the trace file, when the "target address" produced for a Branch item instruction is loaded into the Program Counter.
However, I still want to leave the Branch instruction counter because i need to know how many branch instructions there are, but I also need to be able to calculate when the branch is actually "taken."

Alright so you increment a counter when you see a branch instr. and another when the "branch is actually taken"?
So can you post a small snippet of the trace file - one with a BRANCH instruction in it.

sure:
here is a sample of the verbose mode that prints out the trace items.

Code:

[item 1] entry ITYPE: (PC: 200cd8) (sReg_a: 2) (sReg_b: 255) (dReg: 2) (addr: 106)

[item 2] entry BRANCH: (PC: 200cdc) (sReg_a: 2) (sReg_b: 0) (dReg: 255) (addr: 200ce8)

[item 3] entry LOAD: (PC: 200ce8) (sReg_a: 28) (sReg_b: 255) (dReg: 2) (addr: 1000c000)

[item 4] entry BRANCH: (PC: 200cec) (sReg_a: 2) (sReg_b: 0) (dReg: 255) (addr: 200b38)

[item 5] entry LOAD: (PC: 200b38) (sReg_a: 28) (sReg_b: 255) (dReg: 4) (addr: 1001bd04)

[item 6] entry LOAD: (PC: 200b3c) (sReg_a: 28) (sReg_b: 255) (dReg: 2) (addr: 1000c2fc)

[item 7] entry RTYPE: (PC: 200b40) (sReg_a: 4) (sReg_b: 17) (dReg: 3) (addr: 0)

[item 8] entry LOAD: (PC: 200b44) (sReg_a: 3) (sReg_b: 255) (dReg: 3) (addr: 200aa6ec)

[item 9] entry ITYPE: (PC: 200b48) (sReg_a: 255) (sReg_b: 2) (dReg: 2) (addr: 5)

[item 10] entry RTYPE: (PC: 200b4c) (sReg_a: 2) (sReg_b: 3) (dReg: 2) (addr: 0)

Now, for instance as you can see in item #2 calls a branch and then the PC trace item in #3, takes that target address from the previous branch instruction.
I want to count how many times it does that.

Yes, everytime the branch is accepted by the PC counter on the next instruction, then I want to count that. So if the PC: is different the branch address given in the instruction before, then DO NOT count it.