facopt.c

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

   }
}



/********************************************************************
When an unknown is referenced this routine moves it to its right position
in the stack and rearranges the other unknowns as required

Input: Address and the current time of the pre-processing routine
Output: None
Side effects: The stack is rearranged and the group list is updated
	      if required.
*********************************************************************/

void
inf_handler_fa(unsigned long addr, int cur_time)
{  struct tree_node *line_to_be_ins, /* scratch pointers */
		    *line_to_be_del,
			*prev_entry,
	      *Get_first_unknown_wobacking ();
   struct group_desc *grpptr;	/* scratch */
   int addr_grptime,		/* group time marker for unknown */
          addr_prty;
   int priority,	/* fn of cur_time */
       del_prty;	/* prty of deleted entry (during rearrangement) */
   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;


   ++ihcount;

   priority = MAXINT - cur_time; /* assumes a priority function */

   if ((headgrp.first != NULL) && (headgrp.first->addr == addr)) {
     if (headgrp.first->prty > 0)
       fprintf(stderr, "libcheetah: unknown has > 0 prty\n");
     else
       headgrp.first->prty = priority;
     return;
   }

   addr_grptime = unk_hash_del_fa (addr, &addr_prty);
   if (addr_grptime == 0)
     return;

   --unknowns;

   grpptr = headgrp.nxt; /*assumed that a unknown is not fixed
			  when it is at the top */

/*printf ("inf_handler addr: %d %d\n", addr, addr_grptime);
traverse(root);*/

   while (grpptr)
     if (grpptr->grpno < addr_grptime)
       grpptr = grpptr->nxt;
     else
       break;

/*   if (grpptr == NULL)
     printf ("Error in inf_handler: addr_grptime not found\n"); */

   while (grpptr)
     if (grpptr->last->prty > 0)
       grpptr  = grpptr->nxt;
     else
       break;

/*   if (grpptr == NULL)
     printf ("Error in inf_handler: no unknowns found\n"); */

   line_to_be_ins = del_line;
   line_to_be_ins->prty = priority;
   line_to_be_ins->addr = addr;

   del_prty = 0;
   while (grpptr) {
     line_to_be_del = Get_first_unknown_wobacking (grpptr->grpno, addr_prty, del_prty);
     if (line_to_be_del != NULL) {
       line_to_be_ins->grpno = grpptr->grpno;
       Insert (line_to_be_ins);
       if (line_to_be_ins->prty > grpptr->first->prty)
	 grpptr->first = line_to_be_ins;
       line_to_be_ins = Delete (line_to_be_del, &prev_entry);
       if (grpptr->last == line_to_be_del)
	 grpptr->last = prev_entry;
       if (line_to_be_del->prty == addr_prty)
         break;
       del_prty = line_to_be_ins->prty;
     }
     grpptr = grpptr->nxt;
   }
   del_line = line_to_be_ins;

/*   if (grpptr == NULL)
     printf ("Error in inf_handler: unknown not found\n"); */
}



/**********************************************************************
Used to add infinities to a hash table. The hash table is used by inf_handler
to get the dummy priority of the unknown and its grptime.

Input: The address, the current group number of the first group and
       the dummy prty of the address.
Output: None
Side effects: The address is added to the hash table
**************************************************************************/

unk_hash_add_fa (addr, grpno, prty)
unsigned addr;
int grpno,
    prty;

{  int loc;
   struct hash_table *ptr, *oldptr;
   struct hash_table *UHT_Get_from_free_list ();

   ++unknowns;

   loc = addr % HASHNO;
   if (slot_flag [loc] == 0){
	slot_flag [loc] = 1;
        slot[loc].addr = addr;
        slot[loc].grptime = grpno;
	slot[loc].prty = prty;
        slot[loc].nxt = NULL;
        return(0);
   }


   else{
        ptr = &slot[loc];
        while (ptr) {
            oldptr = ptr;
            if (ptr->addr == addr) {
              fprintf(stderr, "libcheetah: addr already in hash table\n"); 
fprintf(stderr, "addr: %d; t_entries: %d; prty: %d\n", addr, t_entries, ptr->prty);
fprintf(stderr, "slot addr: %d; prty: %d\n", slot[loc].addr, slot[loc].prty);
}
            ptr = ptr->nxt;
        }
	if ((oldptr->nxt = UHT_Get_from_free_list ()) == NULL)
          oldptr->nxt = (struct hash_table *) malloc(sizeof(struct hash_table));
        oldptr->nxt->addr = addr;
        oldptr->nxt->nxt = NULL;
        oldptr->nxt->grptime = grpno;
        oldptr->nxt->prty = prty;
        return(0);
    }
}




/*************************************************************************
Deletes unknowns from the hash table. Returns the grptime and the dummy
priority of the address.

Input: Address
Outpur: The grptime and the dummy priority
Side effects: The entry is deleted from the hash table
*************************************************************************/

unk_hash_del_fa (addr, prty_ptr)
int addr;
int *prty_ptr;

{  int loc,
     grpno;
   struct hash_table *ptr, *oldptr;


   loc = addr % HASHNO;
   if (slot_flag[loc] == 0){
     return (0);
   }
   else if (slot[loc].addr == addr) {
     if (slot[loc].nxt == NULL) {
       slot_flag[loc] = 0;
       *prty_ptr = slot[loc].prty;
       return (slot[loc].grptime);
     }
     else {
       grpno = slot[loc].grptime;
       *prty_ptr = slot[loc].prty;
       slot[loc].addr = slot[loc].nxt->addr;
       slot[loc].grptime = slot[loc].nxt->grptime;
       slot[loc].prty = slot[loc].nxt->prty;
       ptr = slot[loc].nxt;
       slot[loc].nxt = slot[loc].nxt->nxt;
       UHT_Add_to_free_list (ptr);
       return (grpno);
     }
   }
   else{
        ptr = &slot[loc];
        while (ptr) {
          if (ptr->addr == addr)
            break;
          oldptr = ptr;
          ptr = ptr->nxt;
        }
        if (ptr){
          grpno = ptr->grptime;
	  *prty_ptr = ptr->prty;
	  oldptr->nxt = ptr->nxt;
	  UHT_Add_to_free_list (ptr);
	  return (grpno);
        }
        else {
     	  return (0);
        }
    }
}


/*********************************************************************
Inorder traversal using a stack.
Adapted from Harry Smith (page 214)

Starts at the bottom most entry of a group and searches upward for
the first node such that
1. It is that of the referenced address
2. It has a priority less than the del_prty but greater than search_prty.
   search_prty is the -ve old prty of the referenced address and the second
   second condition ensures that only entries that have interacted with
   the referenced address are rearranged.
   del_prty is the priority of the address deleted from
   the previous group and the first condition ensures that it displaces
   only entries of lower priority. For the first group del_prty is set
   to 0 which ensures that the entry deleted is of negative priority.

Input: last entry of group, dummy priority of refned unknown and
       dummy priority of deleted unknown
Output: Returns pointer to node matching the above condition
Side effects: None
************************************************************************/

struct tree_node
*Get_first_unknown (entry, search_prty, del_prty)
struct tree_node *entry;
int search_prty,
       del_prty;

{  int grpno,
        prty,
         top;
   struct tree_node *ptr,
	         *oldptr;

   grpno = entry->grpno;
   prty = entry->prty;
   ptr = root;
   top = 0;
   while (ptr){
     if ((ptr->grpno < grpno) ||
		((ptr->grpno == grpno) && (ptr->prty > prty))) {
        ++top;
        p_stack [top] = ptr;
        ptr = ptr->lft;
     }
     else {
       if ((ptr->grpno == grpno) && (ptr->prty == prty)) {
          ++top;
          p_stack [top] = ptr;
	  break;
       }
       ptr = ptr->rt;
     }
   }

   while (top > 0) {
     ptr = p_stack[top];
     --top;
     /* visit node */
/*printf("%d  %d   %d\n", ptr->addr, ptr->grpno, ptr->prty);*/
     if ((ptr->prty > 0) || (ptr->grpno != grpno))
       return (NULL);
     else if ((ptr->prty == search_prty) ||
	((ptr->prty < del_prty) && (ptr->prty > search_prty)))
       return(ptr);

       ptr = ptr->rt;
       while (ptr) {
	 ++top;
	 p_stack[top] = ptr;
	 ptr = ptr->lft;
       }
   }
}                                                            



/*********************************************************************
Given an entry in the stack returns the previous entry

Input: Pointer to entry
Output: Pointer to previous entry
Side effects: None
*********************************************************************/

struct tree_node
*Get_first_unknown_wobacking (grpno, search_prty, del_prty)
int grpno,
    search_prty,
    del_prty;

{  struct tree_node *ptr,
	    *lstlft_node;

        ptr = root;
        while (ptr){
           ++comp;
           if ((ptr->grpno < grpno) ||
			((ptr->grpno == grpno) && (ptr->prty > search_prty))) {
		lstlft_node = ptr;
                ptr = ptr->lft;
           }
           else{
                if ((ptr->grpno == grpno) && (ptr->prty == search_prty)) {
		  return (ptr);
                }
		ptr = ptr->rt;
	   }
        }                                                            

	if ((lstlft_node->grpno == grpno) && (lstlft_node->prty < del_prty))
	  return (lstlft_node);
	else
	  return (NULL);
}        



/********************************************************************
Output routine.

Input: None
Output: None
Side effects: None
********************************************************************/

void
outpr_facopt(FILE *fd)
{  int sum=0,
       i;
   int stack_end;

   fprintf(fd, "Addresses processed : %d\n", t_entries);
   fprintf(fd, "Line size : %d bytes \n", (ONE << L));
   fprintf(fd, "Number of distinct addresses  %d\n", tot_addrs);
#ifdef PERF
   fprintf(fd, "Total Number of groups passed\t%d\n\n", grps_passd);
   fprintf(fd, "Total Number of splay steps\t%d\n\n", no_splay_steps);
   fprintf(fd, "Number of insert comparisons\t%d\n", comp_ins);
   fprintf(fd, "Number of delete comparisons\t%d\n", comp_del);
   fprintf(fd, "Number of times inf_handler called\t%d\n", ihcount);
#endif

   fprintf(fd, "Cache size (bytes)\tMiss Ratio\n");
   stack_end = min (tot_addrs, MAX_LINES);
   
   for (i = 1; i <= stack_end; i++) {
     sum += out_stack[i];
     if ((i % MISS_RATIO_INTERVAL) == 0)
       fprintf(fd, "%d\t\t\t%1.6lf\n", (i * (ONE << L)),
	       (1.0 - ((double)sum/(double)t_entries)));
   }
   if (stack_end == tot_addrs)
     fprintf(fd, "Miss ratio is %lf for all bigger caches\n",
	     (1.0 - ((double)sum/(double)t_entries)));
   fprintf(fd, "\n\n\n");
 }


/**********************************************************************
Locates the referenced address, deletes it and inserts the address deleted
from the previous group in its place.

Input: Referenced address and address deleted from earlier group
Output: Pointer to node at which insertion occurred.
Side effects.: The deletion and insertion are done and the inserted
node is splayed to the root of the tree.
***********************************************************************/

struct tree_node
*Lookup_Delete_Insert (del_entry, ins_entry)
struct tree_node *del_entry,		/* Entry to be deleted. Refned entry */
		 *ins_entry;		/* Deleted line. To be inserted. */


{  struct tree_node *ptr,
	  *inserted_node;
   int top, pos, at;
   int grpno,
        prty;


   grpno = del_entry->grpno;
   prty = del_entry->prty;
   if (root->grpno == grpno){
       fprintf(stderr, "libcheetah: hit at root\n");
       return (0);
   }
   else{
        top = 0;
        ptr = root->lft;	/* Starts at root->lft to avoid involving
				   root in balance operations */
        while (ptr){
           ++comp;
           ++top;
           p_stack[top] = ptr;
           if ((ptr->grpno < grpno) ||
			((ptr->grpno == grpno) && (ptr->prty > prty))) {
                ptr = ptr->lft;
           }
           else{
	     if ((ptr->grpno == grpno) && (ptr->prty == prty)) {
                     pos = top;
		     break;
             }
             ptr = ptr->rt;
	   }
        }                                                            

        p_stack[pos]->grpno = ins_entry->grpno;
	p_stack[pos]->prty  = ins_entry->prty;
	p_stack[pos]->addr = ins_entry->addr;
	inserted_node = p_stack[pos];

        at = pos;
        while (at > 1){
            ++no_splay_steps;   /* Counts the number of basic operations */
            splay(at, p_stack);
            at = at - 2;
        }
        root->lft = p_stack[1];
        return (inserted_node);
   } /* else */
} /* fn */