ms_branch.c

一个用在mips体系结构中的操作系统

/*
 * Copyright (C) 1996-1998 by the Board of Trustees
 *    of Leland Stanford Junior University.
 * 
 * This file is part of the SimOS distribution. 
 * See LICENSE file for terms of the license. 
 *
 */


	/*
	 *  ms_branch.c  -  Handle branch processing for the MXS simulator
	 *
	 *	Branches are handled by spawning threads to follow along
	 *	all predicted paths.  If no threads are available, then
	 *	no speculative execution occurs.
	 *
	 *	If a branch is conditional, the branch prediction logic
	 *	is consulted.  A thread is spawned to follow the predicted
	 *	path, while the original thread holds the state prior to
	 *	the branch.  If multiple active threads are allowed, then
	 *	both threads may proceed.
	 *
	 *	The branch_tree structure holds the set of unresolved
	 *	branches, which form a binary tree.
	 *
	 *	Jim Bennett
	 *	1994, 1995
	 */

#include <stdlib.h>
#include "ms.h"

void recurse_prune (struct s_cpu_state *st, int branch_node);
void speculate_reparent (struct s_cpu_state *st, int branch_node, int id_node);
void inactivate_thread (struct s_cpu_state *st, THREAD *th);



	/*
	 *  ms_branch  -  Process a branch
	 */

void ms_branch (struct s_cpu_state *st, THREAD *th, int likely)
	{
	int	i, inum, thread;
	INST	*ip;
	THREAD	*newth;
	int	reg_ix;
	int	newthread;
	BrTREE	*br, *left, *right;
	int	branch_index, pbits, target;
	int	fall_thru;
	WorkDecls;

	inum = th->branch_inum;
	ip = &st->iwin[inum];
	br = &st->branch_tree [th->branch_node];
	thread = br->thread;
	br->indirect = is_indirect_branch (ip->op);
	br->jret = (ip->op == OPJRET);
	br->call = is_call (ip->op);
	br->uncond = immediate_unconditional (ip);

		/* On an unconditional branch with an immediate		*/
		/* address, just do the branch.  Takes effect after	*/
		/* TAKEN_LATENCY cycles.				*/
	if (br->uncond && (!br->call))
		{
		st->iwin_flags [inum] |= IWIN_AVAIL;
		ms_pri_dequeue (st, inum);	/* Issue the instr.	*/
		IncStat (ST_EXBRANCH);

		th->pc = ip->imm;		/* Execute the instr.	*/
		st->iwin_branch_pc[inum] = th->pc;
		th->debugpc = cadr_to_addr (st, th->pc);
#ifdef BREAKPOINT
		if (jmpbrk && (th->pc == jmpbrk))
			ms_break (st, NULL, "JMPBRK");
#endif
		if (TAKEN_LATENCY > 0)
			{
			Add_to_worklist (st, TAKEN_LATENCY,
					finish_branch, (void *)ip);
			}
		else
			finish_branch ((void *)st, (void *)ip);
		return;
		}

		/* In all other cases we need to acquire another thread	*/
		/* to hold the context.  If there are no more free	*/
		/* threads, then stall until the branch is resolved	*/
		/* (normal processing).					*/

	th->stall_thread = 1;
	if (st->nthreads >= THREAD_WIDTH) goto normal_exit;

	th->stall_thread = 0;
	if (st->free_thread < 0) 
		{
		fprintf (stderr, "Consistency error in thread management\r\n");
		ms_break (st, NULL, "ERR");
		}
	st->nthreads++;
	newthread = st->free_thread;
	newth = &st->threads[newthread];
	st->free_thread = newth->pc;

		/* Got a free thread, so instantiate it.  This is a	*/
		/* fork operation; just copy the state of the original	*/
		/* thread.						*/
	for (i=0; i<MAX_VAR/2; i++)
		newth->half_def[i] = th->half_def[i];
	for (i=0; i<FPREG; i++)
		{
		newth->regnames[i] = th->regnames[i];
		reg_ix = newth->regnames[i] >> 1;
		AcquireRegMap (&st->reg_rstat[reg_ix], newth, i);
		}
	for (i=FPREG; i<MAX_FP; i++)
		{
		newth->regnames[i] = th->regnames[i];
		if ((i & 0x01) == 0)
		    {
		    reg_ix = newth->regnames[i] >> 1;
		    AcquireRegMap (&st->reg_rstat[reg_ix], newth, i);
		    }
		}
	for (i=MAX_FP; i<MAX_VAR; i++)
		{
		newth->regnames[i] = th->regnames[i];
		reg_ix = newth->regnames[i] >> 1;
		AcquireRegMap (&st->reg_rstat[reg_ix], newth, i);
		}

	newth->pc = th->pc;
        newth->thread_st = 0;
	newth->stall_branch = th->stall_branch;
	newth->stall_thread = 0;
	newth->stall_fpc = th->stall_fpc;   /* This can non-zero if we have
                                             * a special inst in the branch
                                             * delay slot. */
	newth->stall_icache = 0;
	newth->stall_except = 0;
	newth->stall_itlbmiss = 0;
	newth->stall_sys = th->stall_sys;
	newth->stall_sc = th->stall_sc;
	newth->stall_cp0 = th->stall_cp0;
	UpdateStallFetch (newth);
	newth->branch_sp = th->branch_sp;
	newth->branch_dly = th->branch_dly;
	newth->branch_likely = th->branch_likely;
	newth->active_thread = NULL;

		/* Grab two free nodes for the branch tree (guaranteed	*/
		/* to succeed, since a tree always has fewer internal	*/
		/* nodes than leaves) and add them to the tree.		*/

	br->lchild = st->free_branch_node;
	left = &st->branch_tree [st->free_branch_node];
	st->free_branch_node = left->thread;

	left->thread = thread;
#ifdef DEBUG_CHECKS
	if (thread >= THREAD_WIDTH)
		{
		fprintf (stderr, "Inconsistent thread structure (left)\r\n");
		ms_break (st, NULL, "ERR");
		}
#endif
	left->lchild = -1;
	left->rchild = -1;
	left->condition = 0;
	left->resolution = 0;
	left->indirect = 0;
	left->jret = 0;
	left->call = 0;
	left->uncond = 0;
	left->restore = 0;
	left->iwin_head_th = -1;
	left->iwin_tail_th = -1;

	br->rchild = st->free_branch_node;
	right = &st->branch_tree [st->free_branch_node];
	st->free_branch_node = right->thread;

	right->thread = newthread;
#ifdef DEBUG_CHECKS
	if (newthread >= THREAD_WIDTH)
		{
		fprintf (stderr, "Inconsistent thread structure (right)\r\n");
		ms_break (st, NULL, "ERR");
		}
#endif
	right->lchild = -1;
	right->rchild = -1;
	right->condition = 0;
	right->resolution = 0;
	right->indirect = 0;
	right->jret = 0;
	right->call = 0;
	right->uncond = 0;
	right->restore = 0;
	right->iwin_head_th = -1;
	right->iwin_tail_th = -1;

#ifdef PRINT_INST
	if (enable_fprint)
		printf ("Branch: %d -> %d, %d\r\n",
			th->branch_node, br->lchild, br->rchild);
#endif

	th->branch_node = br->lchild;
	newth->branch_node = br->rchild;

	branch_index = bp_pc_to_index(st->iwin_pc [inum]);

		/* Handle an unconditional immediate call.  No		*/
		/* prediction is needed.				*/
	if (br->uncond && br->call)
		{
		IncStat (ST_UNCOND_BR);
		right->condition = BP_MAX_VAL;
		left->condition = 0;
		newth->pc = ip->imm;
		th->branch_dly = 0;
		th->branch_likely = 0;
		newth->debugpc = cadr_to_addr (st, newth->pc);
#ifdef BREAKPOINT
		if (jmpbrk && (newth->pc == jmpbrk))
			ms_break (st, NULL, "JMPBRK");
#endif
			/* Put the new thread on the active list	*/
		newth->thread_st = TH_ACTIVE + TH_SPEC;
		newth->active_thread = st->active_thread;
		st->active_thread = newth;
		right->thread_st = newth->thread_st;

			/* Account for branch latency			*/
		newth->stall_branch = 0;
		UpdateStallFetch (newth);
		if (TAKEN_LATENCY > 0)
			{
			newth->stall_branch = 1;
			UpdateStallFetch (newth);
			Add_to_worklist (st, TAKEN_LATENCY,
				unstall_fetch, (void *)newthread);
			}

			/* Update branch predictor's return stack	*/
		newth->old_prediction = st->branch_stack[st->branch_sp];
#ifdef PRINT_INST
	if (enable_fprint)
		printf ("--RS--Push 0x%x at %d\n", th->pc, st->branch_sp);
#endif
		st->branch_stack[st->branch_sp]= th->pc;
		st->branch_sp++;
		if (st->branch_sp >= BP_RETURN_STACK)
			st->branch_sp = 0;
		newth->branch_sp = st->branch_sp;
		right->restore = 1;
				/* Remove old thread from active list	*/
                inactivate_thread (st, th);
		}
		/* If the branch is conditional, do branch prediction	*/
	else if (is_conditional (ip->op))
		{
		IncStat (ST_COND_BR);
		pbits = st->bp_bits [branch_index];
		right->condition = pbits;
		left->condition = BP_MAX_VAL - pbits;
		if (PredictTaken (pbits, likely))
			{
			fall_thru = 0;
			if (likely)
				{
				newth->branch_likely_pc = ip->imm;
				newth->branch_likely = 1;
                                newth->branch_dly--;  /* branch inst processed */
                                                      /* here. */
				}
			else
				newth->pc = ip->imm;

			th->branch_dly = 0;
			th->branch_likely = 0;
			if (likely) th->pc += BRANCH_SLOTS*PC_INC;
			newth->debugpc = cadr_to_addr (st, newth->pc);
#ifdef BREAKPOINT
			if (jmpbrk && (newth->pc == jmpbrk))
				ms_break (st, NULL, "JMPBRK");
#endif
			}
		else
			{
			fall_thru = 1;
			if (likely)
				{
				th->branch_likely_pc = ip->imm;
				th->branch_likely = 1;
				}
			else
				th->pc = ip->imm;

			newth->branch_dly = 0;
			newth->branch_likely = 0;
			if (likely) newth->pc += BRANCH_SLOTS*PC_INC;

			newth->debugpc = cadr_to_addr (st, newth->pc);
			th->debugpc = cadr_to_addr (st, th->pc);
#ifdef BREAKPOINT
			if (jmpbrk && (newth->pc == jmpbrk))
				ms_break (st, NULL, "JMPBRK");
			if (jmpbrk && (th->pc == jmpbrk))
				ms_break (st, NULL, "JMPBRK");
#endif
			}

			/* Put the new thread on the active list	*/
		newth->thread_st = TH_ACTIVE + TH_SPEC;
		newth->active_thread = st->active_thread;
		st->active_thread = newth;
		right->thread_st = newth->thread_st;

			/* Account for branch latency			*/
		newth->stall_branch = 0;
		UpdateStallFetch (newth);
		if (fall_thru)
			{
			if (FALLTHRU_LATENCY > 0)
				{
				newth->stall_branch = 1;
				UpdateStallFetch (newth);
				Add_to_worklist (st, FALLTHRU_LATENCY,
					unstall_fetch, (void *)newthread);
				}
			}
		else
			{
			if (TAKEN_LATENCY > 0)
				{
				newth->stall_branch = 1;
				UpdateStallFetch (newth);
				Add_to_worklist (st, TAKEN_LATENCY,
					unstall_fetch, (void *)newthread);
				}
			}

			/* Update branch predictor's return stack */
		if ((!fall_thru) && br->call)
			{
			newth->old_prediction = st->branch_stack[st->branch_sp];
#ifdef PRINT_INST
	if (enable_fprint)
		printf ("--RS--Push 0x%x at %d\n", th->pc, st->branch_sp);
#endif
			st->branch_stack[st->branch_sp]= th->pc;
			st->branch_sp++;
			if (st->branch_sp >= BP_RETURN_STACK)
				st->branch_sp = 0;
			newth->branch_sp = st->branch_sp;
			right->restore = 1;
			}

			/* Decide whether to follow both paths based	*/
			/* on the strength of the prediction		*/
		if ((pbits < BP_BOTH) || (pbits >= (BP_TAKEN+BP_BOTH)) ||
		    (st->nactive >= MAX_ACT_THREADS))
			{
				/* Remove old thread from the active	*/
				/* list if the prediction is strong, or	*/
				/* if there aren't any more active	*/
				/* threads available.			*/
			inactivate_thread (st, th);
			}
		else
			{
				/* Otherwise both threads should be active */
			if (!(th->thread_st & TH_ACTIVE))
				{
				th->active_thread = st->active_thread;
				st->active_thread = th;
				}
			st->nactive++;
			th->thread_st |= TH_ACTIVE | TH_SPEC;
			th->stall_branch = 0;
			UpdateStallFetch (th);

				/* Handle branch latency.  Notice that	*/
				/* fall_thru for this case is the	*/
				/* complement of fall_thru for the	*/
				/* predicted path, above.		*/
			if (!fall_thru)
				{
				if (FALLTHRU_LATENCY > 0)
					{
					th->stall_branch = 1;
					UpdateStallFetch (th);
					Add_to_worklist (st, FALLTHRU_LATENCY,
						unstall_fetch, (void *)thread);
					}
				}
			else
				{
				if (TAKEN_LATENCY > 0)
					{
					th->stall_branch = 1;
					UpdateStallFetch (th);
					Add_to_worklist (st, TAKEN_LATENCY,
						unstall_fetch, (void *)thread);
					}
				}

				/* Update branch predictor's return stack */
			if (fall_thru && br->call)
				{
				th->old_prediction =
					st->branch_stack[st->branch_sp];
#ifdef PRINT_INST
	if (enable_fprint)
		printf ("--RS--Push 0x%x at %d\n", newth->pc, st->branch_sp);
#endif
				st->branch_stack[st->branch_sp]= newth->pc;
				st->branch_sp++;
				if (st->branch_sp >= BP_RETURN_STACK)
					st->branch_sp = 0;
				th->branch_sp = st->branch_sp;
				left->restore = 1;
				}

			}
		left->thread_st = th->thread_st;
		}

		/* If the branch is to a register, do target prediction	*/
	else if (br->indirect)
		{
		IncStat (ST_IND_BR);

			/* Update branch predictor's return stack */
		if (br->call)
			{
			newth->old_prediction =
					st->branch_stack[st->branch_sp];
#ifdef PRINT_INST
	if (enable_fprint)
		printf ("--RS--Push 0x%x at %d\n", th->pc, st->branch_sp);
#endif
			st->branch_stack[st->branch_sp]= th->pc;
			st->branch_sp++;
			if (st->branch_sp >= BP_RETURN_STACK)
				st->branch_sp = 0;
			newth->branch_sp = st->branch_sp;
			right->restore = 1;
			}

		if (br->jret)
			{
			st->branch_sp--;
			if (st->branch_sp < 0)
				st->branch_sp = BP_RETURN_STACK - 1;
			newth->branch_sp = st->branch_sp;
			target = st->branch_stack [st->branch_sp];
#ifdef PRINT_INST
	if (enable_fprint)
		printf ("--RS--Pop 0x%x at %d\n", target, st->branch_sp);
#endif
			}
		else