ms_branch.c

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

			target = st->bp_targets [branch_index];

		if (target >= 0)
			{
			newth->pc = target;
			newth->debugpc = cadr_to_addr (st, newth->pc);
#ifdef BREAKPOINT
			if (jmpbrk && (newth->pc == jmpbrk))
				ms_break (st, NULL, "JMPBRK");
#endif
				/* Put new thread on active list	*/
			right->condition = target;
			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 taken branch latency	*/
			if (TAKEN_LATENCY > 0)
				{
				newth->stall_branch = 1;
				UpdateStallFetch (newth);
				Add_to_worklist (st, TAKEN_LATENCY,
					unstall_fetch, (void *)newthread);
				}
			else
				{
				newth->stall_branch = 0;
				UpdateStallFetch (newth);
				}

				/* Remove old thread from active list	*/
			inactivate_thread (st, th);
			left->thread_st = th->thread_st;
			}

		    /* In the case where there is no predicted target,	*/
		    /* leave the fetch stalled until the branch is	*/
		    /* processed.					*/
		}

normal_exit:
		/* OK to issue the branch instruction now, so turn off	*/
		/* the IWIN_BRDLY flag.					*/
	st->iwin_flags [inum] &= ~IWIN_BRDLY;
	CheckInstAvail (st, inum);
	}



	/*
	 *  prune_branch  -  A branch has been resolved, so fix up the
	 *		branch tree accordingly.  One child is pruned,
	 *		and the other becomes identified with the parent.
	 */

void prune_branch (struct s_cpu_state *st, int branch_node)
	{
	int	trim_node, id_node;
	BrTREE	*br, *identify, *right, *left;
	THREAD	*th;

	br = &st->branch_tree [branch_node];
	if (br->lchild < 0) return;
	right = &st->branch_tree [br->rchild];
	left = &st->branch_tree [br->lchild];

	switch (br->resolution)
		{
		case PRUNE_LEFT:
			th = &st->threads [right->thread];
			trim_node = br->lchild;
			id_node = br->rchild;

			if (!br->uncond)
			    {
			    if (br->indirect)
				{
				if (br->jret)
					{
					IncStat (ST_CORRECT_JRET);
					}
				else
					{
					IncStat (ST_CORRECT_IND_BR);
					}
				}
			    else
				{
				if (right->condition < BP_BOTH)
					{
					IncStat (ST_CORRECT_FALLTHRU);
					}
				else if (right->condition < BP_TAKEN)
					{
					if (PredictTaken(right->condition,
						th->branch_likely))
						{
						IncStat (ST_CORRECT_LIKELY);
						}
					else
						{
						IncStat (ST_CORRECT_W_FALLTHRU);
						}
					}
				else if (right->condition < (BP_TAKEN+BP_BOTH))
					{
					IncStat (ST_CORRECT_W_TAKEN);
					}
				else
					{
					IncStat (ST_CORRECT_TAKEN);
					}
				}
			    }
			break;

		case PRUNE_RIGHT:
			th = &st->threads [left->thread];
			trim_node = br->rchild;
			id_node = br->lchild;

			if (!br->uncond)
			    {
			    if (br->indirect)
				{
				if (br->jret)
					{
					IncStat (ST_INCORRECT_JRET);
					}
				else
					{
					IncStat (ST_INCORRECT_IND_BR);
					}
				}
			    else
				{
				if (right->condition < BP_BOTH)
					{
					IncStat (ST_INCORRECT_FALLTHRU);
					}
				else if (right->condition < BP_TAKEN)
					{
					if (PredictTaken(right->condition,
							th->branch_likely))
					    {
					    IncStat (ST_INCORRECT_LIKELY);
					    }
					else
					    {
					    IncStat (ST_INCORRECT_W_FALLTHRU);
					    }
					}
				else if (right->condition < (BP_TAKEN+BP_BOTH))
					{
					IncStat (ST_INCORRECT_W_TAKEN);
					}
				else
					{
					IncStat (ST_INCORRECT_TAKEN);
					}
				}
			    }
			break;
		}

		/* Prune the branch starting with the losing node	*/
	recurse_prune (st, trim_node);

		/* Compress out the other node, and update thread	*/
		/* status and thread PC if an indirect branch.		*/
	identify = &st->branch_tree [id_node];
	br->thread = identify->thread;
#ifdef DEBUG_CHECKS
	if (br->thread >= THREAD_WIDTH)
		{
		fprintf (stderr,
			"Inconsistent thread structure (collapse)\r\n");
		ms_break (st, NULL, "ERR");
		}
#endif
	if (identify->thread_st & TH_ACTIVE)
		br->thread_st |= TH_ACTIVE;
	br->lchild = identify->lchild;
	br->rchild = identify->rchild;
	br->resolution = identify->resolution;
	br->indirect = identify->indirect;
	br->jret = identify->jret;
	br->call = identify->call;
	br->uncond = identify->uncond;
	br->restore |= identify->restore;
	th = &st->threads [br->thread];

		/* The status of this thread changes only if we are	*/
		/* at a leaf node.					*/
	if (th->branch_node == id_node)
		{
		th->branch_node = branch_node;
		if ((br->thread_st & TH_ACTIVE) &&
		    (!(th->thread_st & TH_ACTIVE)))
			{
			if (st->nactive >= MAX_ACT_THREADS)
				{
				fprintf (stderr,
					"Too many active threads!\r\n");
				ms_break (st, NULL, "ERR");
				}
			st->nactive++;
			th->active_thread = st->active_thread;
			st->active_thread = th;
			}
		th->thread_st = br->thread_st;
		st->branch_sp = th->branch_sp;
#ifdef PRINT_INST
	if (enable_fprint)
		printf ("--RS--Restore SP to %d\n", st->branch_sp);
#endif
		}

	speculate_reparent (st, branch_node, id_node);
	}


	/*
	 *  recurse_prune  -  Recursively prune entire branch
	 */

void recurse_prune (struct s_cpu_state *st, int branch_node)
	{
	BrTREE	*br;
	THREAD	*th;
	int	inum, i;

	br = &st->branch_tree [branch_node];
	if (br->lchild >= 0) recurse_prune (st, br->lchild);
	if (br->rchild >= 0) recurse_prune (st, br->rchild);

#ifdef PRINT_INST
	if (enable_fprint)
		printf ("Prune: %d\r\n", branch_node);
#endif

		/* Child nodes have been flushed, flush this one too.	*/
		/* Delete all the instructions associated with this	*/
		/* node, because they are invalid (e.g. because the	*/
		/* branch went the other way).				*/
	for (inum = br->iwin_head_th; inum >= 0; inum = st->iwin_thread [inum])
		{
		st->iwin_br_node [inum] = -1;
		st->iwin_flags [inum] &= ~IWIN_SPEC;
		st->iwin_flags [inum] |= IWIN_SQUASH;

#ifdef PRECISE
				/* In the precise case, instructions	*/
				/* are kept on the thread list until	*/
				/* they graduate.  In this case they	*/
				/* might have completed already, so we	*/
				/* don't want to do anything else	*/
				/* except remove them from ldst buf.	*/
		if (st->iwin_flags [inum] & IWIN_FREED)
			{
			if (st->iwin_flags [inum] & IWIN_LDSTBUF) 
				ldst_buffer_squash (st, inum);
			}
		else
#endif /* PRECISE */

		if (st->iwin_flags [inum] & IWIN_AVAIL)
			{
			if (st->iwin_flags [inum] & IWIN_LDSTBUF) 
				{
				struct	s_ldst_buffer	*entry;
				int	will_be_freed;

				entry = st->inum2ldst[inum];
				will_be_freed =
					(entry->ls->status & LS_ST_DONE) &&
						(st->iwin[inum].r1 >= 0);
				ldst_buffer_squash(st,inum);
				if (!will_be_freed)
					free_spec_inst (st, inum);
				}

				/* If the instruction faulted, free it	*/
				/* and its target register.		*/
			else
				CheckSquash (st, &st->iwin [inum]);
			}
		else
			{		/* Not yet issued, delete it.	*/
			if (st->iwin_flags [inum] & IWIN_LDST)
				ms_ldst_dequeue (st, inum);
			ms_pri_dequeue (st, inum);
			IncStat (ST_PRUNED);
			free_spec_inst (st, inum);
			}
		}

		/* If leaf node, free up thread struct too.		*/
	th = &st->threads[br->thread];
	if ((br->lchild < 0) && (br->rchild < 0))
		{
		for (i=0; i<FPREG; i++)
			{
			ReleaseRegMap (st, th, th->regnames[i] >> 1, i);
			}
		for (i=FPREG; i<FPCTL; i++)
			{
			if ((i & 0x01) == 0)
			    {
			    ReleaseRegMap (st, th, th->regnames[i] >> 1, i);
			    }
			}
		for (i=TOT_REG; i<MAX_FP; i++)
			{
			if ((i & 0x01) == 0)
			    {
			    ReleaseRegMap (st, th, th->regnames[i] >> 1, i);
			    }
			}
		for (i=MAX_FP; i<MAX_VAR; i++)
			{
			ReleaseRegMap (st, th, th->regnames[i] >> 1, i);
			}

		if (th->thread_st & TH_ACTIVE)
			{		/* Remove thread from active list */
			st->nactive--;
			inactivate_thread (st, th);
			}
		th->thread_st = 0;
		th->pc = st->free_thread;
		st->free_thread = br->thread;
#ifdef DEBUG_CHECKS
	if (br->thread >= THREAD_WIDTH)
		{
		fprintf (stderr, "Inconsistent thread structure (free)\r\n");
		ms_break (st, NULL, "ERR");
		}
#endif
		st->nthreads--;
		}

		/* If this was a call, restore the old prediction to	*/
		/* the branch stack.					*/
	if (br->restore)
		{
		int branch_sp = th->branch_sp - 1;
		if (branch_sp < 0) branch_sp = BP_RETURN_STACK - 1;
		st->branch_stack [branch_sp] = th->old_prediction;
		st->branch_sp = branch_sp;
#ifdef PRINT_INST
	if (enable_fprint)
		printf ("--RS--Restore 0x%x at %d\n",
				th->old_prediction, branch_sp);
#endif
		}

		/* Put this node back on the free list.			*/
	br->thread = st->free_branch_node;
	st->free_branch_node = branch_node;
	}


	/*
	 *  CheckSquash  -  If an error has occurred and the instruction
	 *		    causing the error has been squashed, then
	 *		    clean up.  Remove the instruction from any
	 *		    relevant queues, and free both the instruction
	 *		    and the register.
	 */

void CheckSquash (struct s_cpu_state *st, INST *ip)
	{
	int	inum;

	inum = ip - st->iwin;
	if ((st->iwin_flags [inum] & (IWIN_SQUASH + IWIN_FAULT)) ==
					(IWIN_SQUASH + IWIN_FAULT) )
		{
		if (st->iwin_flags [inum] & IWIN_LDST)
			{
			if (PhaseA(inum))
				{
				ms_ldst_dequeue (st, inum);
				ms_pri_dequeue (st, inum);
				IncStat (ST_EXPRUNE);
				}
			else
				ldst_buffer_release (st);
			}
		free_spec_inst (st, inum);
		}
	}


	/*
	 *  speculate_reparent  -  Collapse a node out of the branch tree,
	 *			   and update the status of the instructions
	 *			   that are affected.
	 *
	 *	This routine is where instructions are despeculated.
	 */

void speculate_reparent (struct s_cpu_state *st, int branch_node, int id_node)
	{
	BrTREE	*br, *id;
	int	inum;

#ifdef PRINT_INST
	if (enable_fprint)
		printf ("Collapse %d <- %d\r\n", branch_node, id_node);
#endif

	br = &st->branch_tree [branch_node];
	id = &st->branch_tree [id_node];
	if (br->thread_st & TH_SPEC)
		{
		for (inum = id->iwin_head_th; inum >= 0;
						inum = st->iwin_thread [inum])
			st->iwin_br_node [inum] = branch_node;
		}
	else
		{
		for (inum = id->iwin_head_th; inum >= 0;
						inum = st->iwin_thread [inum])
			{
			st->iwin_br_node [inum] = branch_node;
			st->iwin_flags [inum] &= ~IWIN_SPEC;
			CheckInstAvail (st, inum);
			}
		}

		/* Then knit the two lists into one.		*/
	if (id->iwin_tail_th >= 0)
		{
		st->iwin_thread [id->iwin_tail_th] = br->iwin_head_th;
		st->iwin_bthread [br->iwin_head_th] = id->iwin_tail_th;
		br->iwin_head_th = id->iwin_head_th;
		}

		/* And delete the collapsed branch node		*/
	id->thread = st->free_branch_node;
	st->free_branch_node = id_node;
	}


	/*
	 *  inactivate_thread  -  Remove thread from active thread list
	 */

void inactivate_thread (struct s_cpu_state *st, THREAD *th)
	{
	THREAD	*prev, *active;

	for (prev = NULL, active = st->active_thread;
			(active != th);
			active = active->active_thread)
		prev = active;

	if (prev)
		prev->active_thread = th->active_thread;
	else
		st->active_thread = th->active_thread;

	th->thread_st &= ~TH_ACTIVE;
	th->active_thread = NULL;
	}