/*
 * 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
			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;
	}