facopt.c

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

/*********************************************************************
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
*Lookup_prev(entry)
struct tree_node *entry;


{  struct tree_node *ptr,
	    *lstlft_node;
   int grpno,
	prty;

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

	if ((ptr == NULL) || (ptr->rt == NULL)) 
	  return (lstlft_node);
	else {
	  ptr = ptr->rt;
	  while (ptr->lft != NULL)
	    ptr = ptr->lft;
	  return (ptr);
	}
}        




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

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

struct tree_node
*Lookup_next(entry)
struct tree_node *entry;


{  struct tree_node *ptr,
	     *lstrt_node;
   int grpno,
	prty;

	grpno = entry->grpno;
	prty = entry->prty;
        ptr = root;
        while (ptr){
           ++comp;
           if ((ptr->grpno < grpno) ||
			((ptr->grpno == grpno) && (ptr->prty > prty))) {
                ptr = ptr->lft;
           }
           else{
                if ((ptr->grpno == grpno) && (ptr->prty == prty)) {
		  break;
                }
		lstrt_node = ptr;
		ptr = ptr->rt;
	   }
        }                                                            

	if ((ptr == NULL) || (ptr->lft == NULL))
	  return (lstrt_node);
	else {
	  ptr = ptr->lft;
	  while (ptr->rt != NULL)
	    ptr = ptr->rt;
	  return (ptr);
	}
}        



/******************************************************************
Routine to decide whether to call Insert_no_Balance() or
Insert_and_Balance(). Currently calls the routines alternately.

Input: Node to be inserted
Output: None
Side effects: Calls an insertion rutine which inserts ins_node
and balances stack if required.
******************************************************************/

Insert (ins_node)
struct tree_node *ins_node;

{ static short insert_flag=0;

  if (insert_flag)
    Insert_and_Balance (ins_node);
  else
    Insert_no_Balance (ins_node);
  toggle (insert_flag);
}



/**************************************************************
Inserts node in the tree

Input: Node to be inserted
Output: None
Side effects: The node is inserted in its proper position
**************************************************************/

Insert_no_Balance (ins_node)
struct tree_node *ins_node;

{  struct tree_node *ptr,	    /* Scratch pointers */
		 *oldptr;
   register int grpno,		    /* Group no. to be searched */
		 prty;		    /* Priority of entry to be searched */
   int lstlft;                      /* Flag for type of last branch */

   ins_node->lft = ins_node->rt = NULL;
   if (root == NULL)
     root = ins_node;
   else {
     grpno = ins_node->grpno;
     prty = ins_node->prty;
     ptr = root;
     while (ptr){
       oldptr = ptr;
       ++comp_ins;
       if (ptr->grpno < grpno) {
         ptr = ptr->lft;
	 lstlft = 1;
       }
       else
         if (ptr->grpno == grpno)
	   if (ptr->prty > prty) {
             ptr = ptr->lft;
	     lstlft = 1;
           }
	   else if (ptr->prty < prty) {
         	ptr = ptr->rt;
	 	lstlft = 0;
       	   }
	   else {
	     fprintf(stderr, "libcheetah: error in insert\n");
             break;
	   }
       else { 
         ptr = ptr->rt;
	 lstlft = 0;
       }
     }
     if (lstlft)
       oldptr->lft = ins_node;
     else
       oldptr->rt = ins_node;
   }
}



/********************************************************************
Same as above but the inserted node is splayed to the top

Input: Node to be inserted
Output: None
Side effects: The node is added to the tree and splayed to the top
********************************************************************/

Insert_and_Balance (ins_node)
struct tree_node *ins_node;

{  struct tree_node *ptr,	    /* Scratch pointers */
		 *oldptr;
   int lstlft,                      /* Flag for type of last branch */
        grpno,			    /* Group no. to be searched */
	 prty,			    /* Priority of entry to be searched */
	  top,
	   at;

   ins_node->lft = ins_node->rt = NULL;
   if (root == NULL)
     root = ins_node;
   else
     if (root->lft == NULL)
       root->lft = ins_node;
     else {
       grpno = ins_node->grpno;
       prty = ins_node->prty;
       ptr = root->lft;
       top = 0;
       while (ptr){
	 ++top;
	 p_stack [top] = ptr;
         oldptr = ptr;
         ++comp_ins;
         if ((ptr->grpno < grpno) ||
		  ((ptr->grpno == grpno) && (ptr->prty > prty))) {
           ptr = ptr->lft;
	   lstlft = 1;
         }
         else{
           if ((ptr->grpno == grpno) && (ptr->prty == prty)) {
	     fprintf(stderr, "libcheetah: error in Insert\n");
             break;
           }
           ptr = ptr->rt;
	   lstlft = 0;
         }
       }
       ++top;
       p_stack [top] = ins_node;
       if (lstlft)
         oldptr->lft = ins_node;
       else
         oldptr->rt = ins_node;

	/* Splay only if path > log(tot_addrs) */
       if (top > log_tot_addrs) {
         at = top;
         while (at > 1){
	   ++no_splay_steps;   /* Counts the number of basic operations */
           splay(at, p_stack);
           at = at - 2;
         }
         root->lft = p_stack[1];
       }
     }
}



/********************************************************************
Deletes node and returns a pointer to the previous node in the stack

Input: Entry to be deleted
Output: Pointer to entry deleted and
        pointer to prev entry (returned using prev_entry
Side effects: An entry is deleted from the stack
********************************************************************/

struct tree_node
*Delete (entry, prev_entry)
struct tree_node *entry,
	   **prev_entry;

{  register int grpno,
	         prty;
   struct tree_node *ptr,     /* Scratch pointers */
	      *oldptr_dn,
	      *oldptr_mn,
	        *dn=NULL,     /* Node deleted */
		     *mn,	/* Node moved */
	    *lstlft_node;
   int lstlft_dn,		/* Flags indicating type of last branch */
       lstlft_mn;

	grpno = entry->grpno;
	prty = entry->prty;
        ptr = root;
        while (ptr){
           ++comp_del;
           if ((ptr->grpno < grpno) ||
			((ptr->grpno == grpno ) && (ptr->prty > prty))){
		oldptr_dn = ptr;
		lstlft_node = ptr;
                ptr = ptr->lft;
		lstlft_dn = 1;
           }
           else{
                if ((ptr->grpno == grpno) && (ptr->prty == prty)) {
		  dn = ptr;
		  break;
                }
	   	oldptr_dn = ptr;
                ptr = ptr->rt;
		lstlft_dn = 0;
           }
        } /* while */
        if (dn == NULL) {
	  fprintf(stderr, "libcheetah: error in delete\n");
	  return (0);
	}

        else {
	  if (ptr->rt == NULL) {
	    if (ptr == root) root = ptr->lft;
	    else if (lstlft_dn) oldptr_dn->lft = ptr->lft;
	    else             oldptr_dn->rt = ptr->lft;
	    *prev_entry = lstlft_node;
	  }
	  else if (ptr->lft == NULL) {
	    if (ptr == root) root = ptr->rt;
	    else if (lstlft_dn) oldptr_dn->lft = ptr->rt;
	    else             oldptr_dn->rt = ptr->rt;
	    ptr = ptr->rt;
	    while (ptr->lft != NULL)
	      ptr = ptr->lft;
	    *prev_entry = ptr;
	  }
	  else {
	    oldptr_mn = ptr;
	    ptr = ptr->rt;
	    lstlft_mn = 0;
            while (ptr->lft != NULL) {
	      oldptr_mn = ptr;
	      ptr = ptr->lft;
	      lstlft_mn = 1;
	    }
	    mn = ptr;
	    *prev_entry = mn;
	    if (lstlft_mn) oldptr_mn->lft = mn->rt;
	    else	   oldptr_mn->rt = mn->rt;
	    mn->lft = dn->lft;
	    mn->rt = dn->rt;
	    if (dn == root) root = mn;
	    else if (lstlft_dn) oldptr_dn->lft = mn;
	    else 		oldptr_dn->rt = mn;
	  }
	  return (dn);
	}
}




/***********************************************************************
Cleans the unknown hash table. Get the maximum unknown priority in the
stack by calling the routine Get_max_prty_unknown

Input: None
Output: None
Side effects: Removes inessential unknowns from the hash table
***********************************************************************/

hash_clean_fa ()

{  int loc,		/* Scratch */
       max_prty;	/* Max unknown priority in stack */
   struct hash_table *ptr, *oldptr; 	/* Scratch */


   max_prty = Get_max_prty_unknown ();
   if (max_prty >= 0)
     fprintf(stderr, "libcheetah: max unknown priority non-negative\n");

   for (loc=0; loc<HASHNO; loc++) {
     while ((slot_flag[loc] != 0) && (slot[loc].prty > max_prty)) {
         --unknowns;
         if (slot[loc].nxt == NULL) {
           slot_flag[loc] = 0;
	   continue;
         }
         else {
           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);
         }
     } /*while*/
     if (slot_flag[loc] != 0) {
          ptr = &slot[loc];
          while (ptr) {
            if (ptr->prty > max_prty) {
	      --unknowns;
	      oldptr->nxt = ptr->nxt;
	      UHT_Add_to_free_list  (ptr);
	      ptr = oldptr;
            }
            oldptr = ptr;
            ptr = ptr->nxt;
          }
      }
   } /* for */
}



/******************************************************************
Determines the maximum priority of an unknown in the stack by doing an
inorder traversal of the tree.
Adapted from Harry Smith "Data structures: Form and Function"

Input: None
Output: Maximum unknown priority in stack
Side effects: None
******************************************************************/

Get_max_prty_unknown ()

{  int top;
   struct tree_node *ptr;
   int max_prty=(5-MAXINT);

   ptr = root;
   top = 0;
   while (ptr != NULL) {
     ++top;
     p_stack[top] = ptr;
     ptr = ptr->lft;
   }
   while (top > 0) {
     ptr = p_stack[top];
     --top;
     if ((ptr->prty < 0) && (ptr->prty > max_prty))
       max_prty = ptr->prty;
     if (ptr->rt != NULL) {
       ptr = ptr->rt;
       while (ptr != NULL) {
         ++top;
         p_stack[top] = ptr;
         ptr = ptr->lft;
       }
     }
   }
   return (max_prty);
}