btb.cpp

Go to the documentation of this file.

/*
        Copyright (C) 1997 CFU Corporation

        File: btb.cpp
        Description: branch target buffer
        Author: Chao-yinig Fu
        Date: Oct. 27, 2000

        ^..^
        (00)

         $__$
        <~00~>
         (oo)
          ||

        ```````
        C ^|^ D
         \ O /
*/

#include "btb.h"

//
// Input: 
//      ip:     the ip of this mop
//      slot:   the predicted slot
// Return
//      find_btb: true (yes), false (no)
//      target: the predicted address
//
void BTB::predict(int ip,int slot,bool &find_btb,int &target)
{
        //if(ip!=5692)return;

        int index=ip>>_b;
        index=index&_index_mask;

        int start_index=index*_num_of_entry_per_set;

        //fprintf(stderr,"ip=%d index=%d\n",ip,index);

        int this_index;
        int i;
        for(i=0;i<_num_of_entry_per_set;i++)
        {
                this_index=start_index+i;

                // Check Tag
                if(_tag[this_index]==ip && _slot[this_index]==slot)
                {
                        break;
                }
        }

        if(i==_num_of_entry_per_set)    // We didn't find the tag match
        {
                find_btb=false;

                //fprintf(stderr,"We didn't find_btb for ip=%d slot=%d\n",ip,slot);
                return; 
        }
        else
        {
                find_btb=true;
                target=_target[this_index];

                //fprintf(stderr,"We find_btb for ip=%d slot=%d target=%d\n",ip,slot,target);
                return;
        }
}

//
// Parameter
//      ip: ip of this mop
//      slot: the actual taken slot
//      target: the taken address
//      global_cycle: the current global cycle
//
void BTB::update(int ip,int slot,int target,int global_cycle)
{
        //if(ip!=5692)return;

        int index=ip>>_b;
        index=index&_index_mask;

        int start_index=index*_num_of_entry_per_set;

        //HZ: add initialization of this_index, not sure it is the right thing
        // to do
        //int this_index;
        int this_index = 0;
        int i;
        int oldest_time=_time[start_index]; //_time[this_index];
        int oldest_entry=start_index;
        int empty_entry=-1;

        for(i=0;i<_num_of_entry_per_set;i++)
        {
                this_index=start_index+i;

                int this_tag=_tag[this_index];
                int this_slot=_slot[this_index];
                // Check Tag
                if(this_tag==ip && this_slot==slot)
                {
                        break;
                }

                // find the first empty entry
                if(empty_entry==-1 && this_tag==-1)
                {
                        empty_entry=this_index;
                }

                // find LRU entry
                int this_time=_time[this_index];
                if(this_time<oldest_time)
                {
                        oldest_time=this_time;
                        oldest_entry=this_index;
                }
        }

        if(i==_num_of_entry_per_set)    // We didn't find the tag match
        {
                // Replace oldest_entry
                // update its time
                if(empty_entry==-1)     // put to oldest entry
                {
                        _time[oldest_entry]=global_cycle;
                        _tag[oldest_entry]=ip;
                        _slot[oldest_entry]=slot;
                        _target[oldest_entry]=target;

                        //fprintf(stderr,"BTB MISS UPDATE ip=%d slot=%d target=%d saveto (index=%d oldest_entry=%d)\n",ip,slot,target,index,oldest_entry%start_index);
                }
                else    // put to empty_entry
                {
                        _time[empty_entry]=global_cycle;
                        _tag[empty_entry]=ip;
                        _slot[empty_entry]=slot;
                        _target[empty_entry]=target;

                        //fprintf(stderr,"BTB MISS UPDATE ip=%d slot=%d target=%d saveto (index=%d empty_entry=%d)\n",ip,slot,target,index,empty_entry%start_index);
                }
        }
        else    // we find the tag match
        {
                // update its time
                _time[this_index]=global_cycle;

                if(_target[this_index]!=target)
                {
                        //fprintf(stderr,"BTB HIT UPDATE ip=%d slot=%d old_target=%d new_target=%d\n",ip,slot,_target[this_index],target);
                        _target[this_index]=target;
                }
        }
}

---