Pipeline.cpp

// Copyright 2014 Dolphin Emulator Project
// Licensed under GPLv2
// Refer to the license.txt file included.

#include <algorithm>
#include <deque>

#include "Core/PowerPC/Pipeline.h"
#include "Core/PowerPC/PPCTables.h"


namespace PPCPipeline {

struct queuedInst
{
	UGeckoInstruction inst;
	GekkoOPInfo *info;
	u32 pc;

	queuedInst(UGeckoInstruction _inst, u32 _pc)
	{
		pc = _pc;
		inst = _inst;
		info = GetOpInfo(_inst);
	}
};

struct dispatchedInst;

static std::deque<queuedInst *> dispatchQueue;
static std::deque<dispatchedInst*> completionQueue;

struct dispatchedInst
{
	UGeckoInstruction inst;
	GekkoOPInfo *info;
	u32 pc;
	int cycles;
	bool complete;

	dispatchedInst() {
		inst = dispatchQueue[0]->inst;
		info = dispatchQueue[0]->info;
		pc = dispatchQueue[0]->pc;
		cycles = info->numCycles;
		complete = false;
		completionQueue.push_back(this);
		delete dispatchQueue[0];
		dispatchQueue.pop_front();
	}

	bool retireable() {
		// TODO: Exceptions? Unresloved Predicted branch
		return complete;
	}
};

// The execution units (and their Reservation Stations)
// Each execution unit has one Reservation Station, where a dispatched instruction can sit
// while the first slot is busy.
// LSU - Load Store Unit
dispatchedInst* LSU1, *LSU2, *LSU_rs1, *LSU_rs2;
// FPU - Floating Point Unit
dispatchedInst* FPU1, *FPU2, *FPU3, *FPU_rs;
// IU1 - Interger Unit 1 (complex)
dispatchedInst* IU1, *IU1_rs;
// IU2 - Interger Unit 2
dispatchedInst* IU2, *IU2_rs;
// SRU - System Register Unit
dispatchedInst* SRU, *SRU_rs;

static u32 fetch_pc;

static int num_fetches;

bool dispatch() {
	// Check we actually have an instruction and a place in the completion queue to put it.
	if(dispatchQueue.size() == 0 || completionQueue.size() >= 6)
		return false;

	// TODO: check we actually have the rename registers needed.

	switch(dispatchQueue[0]->info->flags & FL_EX_MASK)
	{
	case FL_EX_FPU:
		if(!FPU1)
		{
			FPU1 = new dispatchedInst();
			return true;
		}
		else if (!FPU_rs)
		{
			FPU_rs = new dispatchedInst();
			return true;
		}
		return false;
	case FL_EX_IUx:
		if(!IU2) // Try for IU2 first
		{
			IU2 = new dispatchedInst();
			return true;
		}
		else if (!IU1)
		{
			IU1 = new dispatchedInst();
			return true;
		}
		else if (!IU2_rs)
		{
			IU2_rs = new dispatchedInst();
			return true;
		}
		else if (!IU1_rs)
		{
			IU1_rs = new dispatchedInst();
			return true;
		}
		return false;
	case FL_EX_IU1:
		if (!IU1)
		{
			IU1 = new dispatchedInst();
			return true;
		}
		else if (!IU1_rs)
		{
			IU1_rs = new dispatchedInst();
			return true;
		}
		return false;
	case FL_EX_LSU:
		if (!LSU1)
		{
			LSU1 = new dispatchedInst();
			return true;
		}
		else if (!LSU_rs1)
		{
			LSU_rs1 = new dispatchedInst();
			return true;
		}
		else if (!LSU_rs2)
		{
			LSU_rs2 = new dispatchedInst();
			return true;
		}
		return false;
	case FL_EX_SRU:
		if (!SRU)
		{
			SRU = new dispatchedInst();
			return true;
		}
		else if (!SRU_rs)
		{
			SRU_rs = new dispatchedInst();
			return true;
		}
		return false;
	default:
		return false;
	}

}

void cycle(std::function<void (UGeckoInstruction, u32)> retire)
{
	// Do one tick of the cpu pipeline.
	// Because each stage of the pipeline flows into the next,
	// we start at the end and do this in reverse order.

	// Retire instructions from the completion queue.
	// CQ[0] can be retired if execution is finished and there are no pending branches or exceptions
	if (completionQueue.size() > 0 && completionQueue[0]->retireable())
	{
		retire(completionQueue[0]->inst, completionQueue[0]->pc);
		delete completionQueue[0];

		// CQ[1] can be retired if CQ[0] was retired and exection is finished etc.
		// FIXME: make sure we don't exceed register retirement limits.
		if (completionQueue.size() > 1 && completionQueue[1]->retireable())
		{
			retire(completionQueue[1]->inst, completionQueue[0]->pc);
			delete completionQueue[1];
			completionQueue.pop_front();
		}
		completionQueue.pop_front();
	}

	// Advance all instructions through their slots.
	if (SRU && --SRU->cycles == 0)
	{
		SRU->complete = true;
		SRU = nullptr;
	}
	if (IU2 && --IU2->cycles == 0)
	{
		IU2->complete = true;
		IU2 = nullptr;
	}
	if (IU1 && --IU1->cycles == 0)
	{
		IU1->complete = true;
		IU1 = nullptr;
	}
	if (FPU3 && --FPU3->cycles == 0)
	{
		FPU3->complete = true;
		FPU3 = nullptr;
	}
	if (FPU2 && --FPU2->cycles == 0)
	{
		FPU2->cycles = 1;
		FPU3 = FPU2;
		FPU2 = nullptr;
	}
	if (FPU1 && --FPU1->cycles == 0)
	{
		FPU1->cycles = 1;
		FPU2 = FPU1;
		FPU1 = nullptr;
	}
	if (LSU2 && --LSU2->cycles == 0)
	{
		LSU2->complete = true;
		LSU2 = nullptr;
	}
	if (LSU1 && --LSU1->cycles == 0)
	{
		LSU1->cycles = 1;
		LSU1 = FPU2;
		LSU1 = nullptr;
	}

	// Try to move instrutions out of reservation stations
	if (SRU_rs && SRU == nullptr)
	{
		SRU = SRU_rs;
		SRU_rs = nullptr;
	}
	if (IU2_rs && IU2 == nullptr)
	{
		IU2 = IU2_rs;
		IU2_rs = nullptr;
	}
	if (IU1_rs && IU1 == nullptr)
	{
		IU1 = IU1_rs;
		IU1_rs = nullptr;
	}
	if (FPU_rs && FPU1 == nullptr)
	{
		FPU1 = FPU_rs;
		FPU_rs = nullptr;
	}
	if (LSU_rs1 && LSU1 == nullptr)
	{
		LSU1 = LSU_rs1;
		LSU_rs1 = LSU_rs2; // Chain the two reservation stations together
		LSU_rs2 = nullptr;
	}

	// TODO: Fold branches here.

	// Try to dispatch the bottom two instructions from the instruction queue.
	if(dispatch())
	{
		// First dispatch was sucessful, try another
		dispatch();
	}

	// Load new instructions into queue.
	for(int i = 0; i < num_fetches; i++) {
		UGeckoInstruction inst;
		inst.hex = Memory::ReadUnchecked_U32(fetch_pc);
		dispatchQueue.push_back(new queuedInst(inst, fetch_pc));
		fetch_pc += 4;
	}

	num_fetches = std::min<int>(4, 6 - dispatchQueue.size());
}

void init() {
	for (auto entry : dispatchQueue)
		delete entry;
	dispatchQueue.empty();

	for (auto entry : completionQueue)
		delete entry;
	completionQueue.empty();

	FPU1 = FPU2 = FPU3 = FPU_rs = nullptr;
	LSU1 = LSU2 = LSU_rs1 = LSU_rs2 = nullptr;
	IU1 = IU2 = IU1_rs = IU2_rs = nullptr;
	SRU = SRU_rs = nullptr;

	fetch_pc = PowerPC::ppcState.pc;
}

}