How to count Branches

This is a discussion on How to count Branches within the C Programming forums, part of the General Programming Boards category; Hi: In my code below, I have a verbose mode which prints results of a trace file. I need count ...

  1. #1
    sparklezilla3
    Join Date
    Mar 2010
    Posts
    41

    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);
    }

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So make a counter, and in every branch you want to count, add an instruction that adds one to the counter.

  3. #3
    sparklezilla3
    Join Date
    Mar 2010
    Posts
    41
    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.

  4. #4
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    That's why he said "make a counter, and in every branch you want to count, ...

    Don't just ALWAYS increment, only do so when you're where you need to be counting.
    Code:
    if( x )
    {
        x_branch++;
    }
    Not...
    Code:
    if( x )
    {
    }
    x_branch++;
    Quzah.
    Hope is the first step on the road to disappointment.

  5. #5
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by husslela2 View Post
    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.)

  6. #6
    sparklezilla3
    Join Date
    Mar 2010
    Posts
    41
    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?

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by husslela2 View Post
    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?

  8. #8
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,058
    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

  9. #9
    sparklezilla3
    Join Date
    Mar 2010
    Posts
    41
    ok how would i write that in C and where would i place it in this code?

  10. #10
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,058
    Quote Originally Posted by husslela2 View Post
    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.

  11. #11
    sparklezilla3
    Join Date
    Mar 2010
    Posts
    41
    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."

  12. #12
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,058
    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.

  13. #13
    sparklezilla3
    Join Date
    Mar 2010
    Posts
    41
    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.

  14. #14
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by husslela2 View Post
    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.
    The answer is "every time". (Unless that's the point, to show it's happening?) Or are you asking how many distinct places get jumped to? (I.e., if another branch to 200b38 happens later, do you want to count it, or not?)

    EDIT: Either way, you'll need to, in your BRANCH switch case, store that address; you can then, before the switch, compare current address with stored address and increment as appropriate.
    Last edited by tabstop; 04-08-2010 at 01:57 PM.

  15. #15
    sparklezilla3
    Join Date
    Mar 2010
    Posts
    41
    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.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need some guidance.
    By Kinto in forum C Programming
    Replies: 10
    Last Post: 05-31-2009, 01:02 AM
  2. bintree and count (withouth using template)?
    By cubimongoloid in forum C++ Programming
    Replies: 7
    Last Post: 05-24-2009, 07:22 AM
  3. input question
    By piyush_v in forum C Programming
    Replies: 9
    Last Post: 04-12-2007, 08:09 AM
  4. I'm missing something obvious
    By crash88 in forum C Programming
    Replies: 7
    Last Post: 07-02-2006, 01:51 AM
  5. Program Crashing
    By Pressure in forum C Programming
    Replies: 3
    Last Post: 04-18-2005, 11:28 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21