facopt.c

RISC处理器仿真分析程序。可以用于研究通用RISC处理器的指令和架构设计。在linux下编译

/************************************************************************
* Copyright (C) 1989, 1990, 1991, 1992, 1993                    	*
*                   Rabin A. Sugumar and Santosh G. Abraham		*
*									*
* This software is distributed absolutely without warranty. You are	*
* free to use and modify the software as you wish.  You are also free	*
* to distribute the software as long as it is not for commercial gain,	*
* you retain the above copyright notice, and you make clear what your	*
* modifications were.							*
*									*
* Send comments and bug reports to [e-mail]			*
*									*
************************************************************************/

/* Simulates fully associative caches of a range of sizes but of *
 * a constant line size with OPT replacement.                    */

#include <stdio.h>

/* Macros */
#define toggle(i) if(i==1)i=0;else{i=1;}
#define min(a,b) ((a<b) ? a : b)

#define ONE 1
#define MAX_PHYSICAL_MEM 2097152  /* Physical mem available on machine */
#define BYTES_PER_LINE 35  /* Storage requirement per line */

#define HASHNO 7211    /* number of slots in hash table */
#define TREE_HEIGHT 50000  /* maximum height of tree */
#define CACHE_SIZE 50000  /* no of lines in cache */
#define MAXINT 2147483647   /* 2^31-1 */

 struct tree_node {
        unsigned addr;
	int grpno;
	int prty;
        int rtwt;
        struct tree_node *lft, *rt;
 };  

 struct group_desc {
	struct tree_node *first;
	struct tree_node *last;
	int grpno;
	int wt;
	struct group_desc *nxt;
 };

 struct hash_table {
        unsigned addr;
        int grptime;
	int prty;
        struct hash_table *nxt;
   };


static struct group_desc headgrp;	/* Head of group list */
static struct tree_node *root,	/* Root of tree */
		     **p_stack;	/* Stack used in tree operations */
static struct hash_table slot[HASHNO];	/* Hash table */
static short slot_flag [HASHNO];	/* Flag for hash slots */
static unsigned *out_stack;	/* Stack depth hits array */
static int comp=0, comp_del=0, comp_ins=0, comp_lid=0,
           no_splay_steps, tot_addrs, grps_passd, grps_coalesced;
static int t_entries;		/* Count of addresses processed */
static int max_priority; /* Priority number of max priority line */
extern unsigned addr_array[],
 	        time_array[];
extern struct tree_node *Delete ();
static int ihcount;  /* To count no of time inf_handler called */
static int grp_ct=MAXINT;  /* To number groups */
static short size_exceeded=0;		/* Stack overflow flag */
static int log_tot_addrs;
static unsigned next_two_pwr;
static unsigned unknowns;

static int CLEAN_INTERVAL,
           next_clean_time;


extern int L,		/* Line size */
           T;		/* Max addresses processed */
extern unsigned MAX_CACHE_SIZE,	/* Maximum cache size of interest */
                MAX_LINES;	/* Calculated from max cache size and line size */
extern int MISS_RATIO_INTERVAL,	/* Output interval */
           SAVE_INTERVAL,      	/* Interval at which results are saved */
           P_INTERVAL;  /* Intervals at which progress output is done */

static int next_save_time;

void outpr_facopt(FILE *fd);


/**********************************************************************
Main simulation routine. Processes the addr_array and time_array obtained
from the pre-processing routine.

Input: The range in the addr_array (time_array) to be processed
Output: -1 if limit on the addresses to be processed is reached
	 0 otherwise
Side effects: The stack and group list are updated as the addresses are
	      preocessed.
**********************************************************************/

int
stack_proc_fa(int start,		/* index of starting array location */
	      int end)			/* index of ending array location */
{
   int i, l;
   unsigned addr;
   int priority,
      new_addrs;
   struct tree_node *nnode;

   if (t_entries == 0) {
     root = (struct tree_node *) malloc(sizeof(struct tree_node));
     root->rt = root->lft = NULL;
     root->prty = Priority_fa (0);
     root->addr = addr_array [0];
     root->grpno = 0;

     l = 0;
     while ((addr_array [l] == addr_array [0]) && (l < end))
       ++l;
     nnode = (struct tree_node *) malloc(sizeof(struct tree_node));
     nnode->rt = nnode->lft = NULL;
     priority = Priority_fa (l-1);
     nnode->prty = priority;
     nnode->addr = root->addr;
     if (nnode->prty < 0)
       unk_hash_add_fa (addr_array[l-1], MAXINT, priority);
     nnode->grpno = MAXINT;
     priority = Priority_fa (l);
     root->prty = priority;
     root->addr = addr_array [l];
     root->lft = nnode;
     headgrp.first = headgrp.last = root;
     headgrp.grpno = 0;
     headgrp.nxt = (struct group_desc *) malloc (sizeof (struct group_desc));
     headgrp.nxt->first = nnode;
     headgrp.nxt->last = nnode;
     headgrp.nxt->grpno = MAXINT;
     headgrp.nxt->wt = 1;
     headgrp.nxt->nxt = NULL;

     out_stack [1] += l-1;
     tot_addrs = 2;
     log_tot_addrs = 1;
     next_two_pwr = 4;
     for (i=0; i<=l; i++) {
       addr_array [i] = 0;
       time_array [i] = 0;
     }
     start = l+1;
     t_entries = l+1;
   }


   for (l=start; l<end; l++) {
	++t_entries;
	addr = addr_array [l];
	if (t_entries > next_save_time) {
	  outpr_facopt(stderr);
	  next_save_time += SAVE_INTERVAL;
	}
	if (t_entries > next_clean_time) {
	  if (size_exceeded)
	    hash_clean_fa ();
	  next_clean_time += CLEAN_INTERVAL;
	}

	if ((t_entries % P_INTERVAL) == 0)
          fprintf(stderr, "libcheetah: addresses processed  %d\n", t_entries);

	priority = Priority_fa (l);

        if ((new_addrs = process_groups (addr, priority)) == 1) {
	  ++tot_addrs;
	  if (tot_addrs > next_two_pwr) {
	    ++log_tot_addrs;
	    next_two_pwr *= 2;
	  }
	  if (size_exceeded == 0)
	    if (tot_addrs > MAX_LINES) {
	      toggle(size_exceeded);
              fprintf(stderr,
		      "libcheetah: tot_addrs limit exceeded, t_entries=%d\n",
		      t_entries);
	    }
        }
	addr_array [l] = 0;
	time_array [l] = 0;
        if (t_entries > T) {
	  return(1);
	}
   } /* for */
   return (0);
}


/*********************************************************************
Initialization routine. Creates a root for the splay tree
and allocates space for the arrays.

Input: None
Output: None
Side effects: Creates a root for the tree. Adds the address to the splay tree.
*********************************************************************/

init_facopt ()

{

      CLEAN_INTERVAL = 10000000;
      next_save_time = SAVE_INTERVAL;

      out_stack = (unsigned *) calloc (MAX_LINES, sizeof (unsigned));
                        /* Stack is not cut off precisely at MAX_LINES */
      p_stack = (struct tree_node **) calloc ((MAX_LINES+1000), sizeof (struct tree_node *));

      if ((out_stack == NULL) || (p_stack == NULL))
        goto error;

      next_clean_time = CLEAN_INTERVAL;

      return;
error:
      fprintf(stderr, "libcheetah: problem allocating space (in init)\n");
      exit (1);
}





/**********************************************************
  Does the stack processing for each address in the trace for
  OPT replacement.

  The stack is maintained as a tree. A list of groups constituting
  the stack is maintained. This list is traversed by the procedure.
  It calls special tree handling routines to perform some stack operations
  and to maintain the group list.

  Input: address referenced and its priority(a fn of its time of next refn)
  Output: none
  Side effects: Updates the stack depth hit array
		Updates the group list and the tree.
**********************************************************/

process_groups (addr, priority)
unsigned addr;	/* Address referenced */
int priority;	/* New priority of address */

{  int depth;		/* Stack depth counter */
   struct group_desc *grpptr,		/* Scratch pointer */
		  *oldgrpptr,
		  *newgrpptr;
   struct tree_node *Lookup_next (),		/* Tree handling functions */
		    *Lookup_prev (),
	   *Lookup_Delete_Insert (),
		         *Delete (),
			*prev_entry,
		         *grpsecond;
   static struct tree_node dummy_for_del_line;
	/* One extra node is allocated for del_line which changes */
   static struct tree_node *del_line = &dummy_for_del_line;

    /* Hit at top */
  if (headgrp.first->addr == addr) {
    ++ out_stack [1];
    headgrp.first->prty = priority;
    headgrp.first->addr = addr;
  }
  else {
     /* Depth two hit */
    grpptr = headgrp.nxt;
    ++grps_passd;

	/* For inf_handler */
    if (headgrp.first->prty < 0) {
	/* A kludge to set grptime correctly on a depth two hit */
      if (headgrp.nxt->first->addr == addr)
        unk_hash_add_fa (headgrp.first->addr, (headgrp.nxt->grpno-1), headgrp.first->prty);
      else
        unk_hash_add_fa (headgrp.first->addr, headgrp.nxt->grpno, headgrp.first->prty);
    }

    if (grpptr->first->addr == addr) {
      ++out_stack [2];

      if (grpptr->wt == 1) {
	/* One entry in first group */
        grpptr->first->addr = headgrp.first->addr;
	grpptr->first->prty = headgrp.first->prty;
      }
      else {
	grpsecond = Lookup_next (grpptr->first);
	if (grpsecond->grpno != grpptr->grpno)
	  fprintf(stderr, "libcheetah: inconsistent next entry\n");
	if (grpsecond->prty < headgrp.first->prty) {
	/* Coalescing. new group not needed */
          grpptr->first->addr = headgrp.first->addr;
          grpptr->first->prty = headgrp.first->prty;
	}
	else {

	  --grp_ct;

       /* A new group is created */
	  newgrpptr = (struct group_desc *) malloc (sizeof (struct group_desc)) ;
	  newgrpptr->first = grpptr->first;
	  newgrpptr->last = grpptr->first;
	  newgrpptr->grpno = grp_ct;
	  newgrpptr->wt = 1;
	  newgrpptr->first->addr = headgrp.first->addr;
	  newgrpptr->first->prty = headgrp.first->prty;
	  newgrpptr->first->grpno = grp_ct;
	  newgrpptr->nxt = grpptr;
	  headgrp.nxt = newgrpptr;

	/* adjust next group */
          grpptr->first = grpsecond;
	  grpptr->wt -= 1;
        }
      }
      headgrp.first->addr = addr;
      headgrp.first->prty = priority;
    }
    else {
	/* Hit at second or higher group */
      del_line->prty = headgrp.first->prty;
      del_line->addr = headgrp.first->addr;
      headgrp.first->addr = addr;
      headgrp.first->prty = priority;

      if (del_line->prty > grpptr->last->prty) {
	/* del_line enters group. last entry bcomes del_line */
	del_line->grpno = grpptr->grpno;
	Insert (del_line);
	if (del_line->prty > grpptr->first->prty)
	  grpptr->first = del_line;
	del_line = Delete (grpptr->last, &prev_entry);
	grpptr->last = prev_entry;
	if (grpptr->last->grpno != grpptr->grpno)
	  fprintf(stderr, "libcheetah: inconsistent prev entry\n");
      }

      oldgrpptr = grpptr;
      depth = grpptr->wt + 1;
      grpptr = grpptr->nxt;
   
      while (grpptr != NULL) {
	++grps_passd;
        if (grpptr->first->addr == addr) { /* Hit */
	  if ((depth+1) <= MAX_LINES)
	    ++out_stack[depth+1];

	  del_line->grpno = oldgrpptr->grpno;
	  oldgrpptr->last = Lookup_Delete_Insert (grpptr->first, del_line);
	  oldgrpptr->wt += 1;

          if (grpptr->first == grpptr->last) {
	/* delete group if it had only the refned entry */
	    oldgrpptr->nxt = grpptr->nxt;
            free (grpptr);
	    grpptr = oldgrpptr; /* grpptr should not be NULL */
	  }
          else {
	/* else set group-first to next entry */
            grpptr->first  = Lookup_next(grpptr->first);
	    grpptr->wt -= 1;
	    if (grpptr->first->grpno != grpptr->grpno)
	      fprintf(stderr, "libcheetah: inconsistent next entry\n");
	  }
	  break;
  
        }
	else if (del_line->prty > grpptr->last->prty) {
	/* del_line enters group. last entry bcomes del_line */
	  del_line->grpno = grpptr->grpno;
	  Insert (del_line);
	  if (del_line->prty > grpptr->first->prty)
	    grpptr->first = del_line;
	  del_line = Delete (grpptr->last, &prev_entry);

	  grpptr->last = prev_entry;
	  if (grpptr->last->grpno != grpptr->grpno)
	    fprintf(stderr, "libcheetah: inconsistent prev entry\n");
	}
	oldgrpptr = grpptr;
	depth += grpptr->wt;
	grpptr = grpptr->nxt;
      } /* while */
     } /* else */

     if (grpptr == NULL) {
	/* refned address is new (compulsory miss)  */
	/* If stack has overflowed, del_line is not added to the end
	   of the stack. Also, if del_line is an unknown, it is deleted
	   from the ft_hash_table as well. Unknowns are deleted from
	   the unknown hash table only during the cleaning step */
       if (size_exceeded) {
	 if (del_line->prty < 0) {
	   ft_hash_del (del_line->addr);
	 }
       }
       else {
         del_line->grpno = oldgrpptr->grpno;
         Insert (del_line);
         oldgrpptr->last = del_line;
         oldgrpptr->wt += 1;
         del_line = (struct tree_node *) malloc(sizeof(struct tree_node));
       }
       return (1);
     }
   } /* else */
   return (0);
} /*fn*/



/********************************************************************
Given the index of the address in the address array it determines the
priority of the address using the time_array.

Input: Index of current address in the addr_array.
Output: The priority of the current address
Side effects: None
********************************************************************/

Priority_fa (i)
int i;

{  static int inf_count=0;

   if (time_array [i] > 0)
     return (MAXINT - time_array [i]); /* inf_handler assumes this fn.
			 inf_handler has to be changed if this is changed */
   else if (time_array [i] == 0)
     return (--inf_count);
   else {
     fprintf(stderr, "libcheetah: error in Priority function\n");
     return (0);