Differential D43951 Diff 137556 llvm/trunk/tools/llvm-mca/Dispatch.cpp

Changeset View

Standalone View

llvm/trunk/tools/llvm-mca/Dispatch.cpp

		1		//===--------------------- Dispatch.cpp -------------------------- C++ --===//
		2		//
		3		// The LLVM Compiler Infrastructure
		4		//
		5		// This file is distributed under the University of Illinois Open Source
		6		// License. See LICENSE.TXT for details.
		7		//
		8		//===----------------------------------------------------------------------===//
		9		/// \file
		10		///
		11		/// This file implements methods declared by class RegisterFile, DispatchUnit
		12		/// and RetireControlUnit.
		13		///
		14		//===----------------------------------------------------------------------===//
		15
		16		#include "Dispatch.h"
		17		#include "Backend.h"
		18		#include "Scheduler.h"
		19		#include "llvm/Support/Debug.h"
		20
		21		using namespace llvm;
		22
		23		#define DEBUG_TYPE "llvm-mca"
		24
		25		namespace mca {
		26
		27		void RegisterFile::addRegisterMapping(WriteState &WS) {
		28		unsigned RegID = WS.getRegisterID();
		29		assert(RegID && "Adding an invalid register definition?");
		30
		31		RegisterMappings[RegID] = &WS;
		32		for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I)
		33		RegisterMappings[*I] = &WS;
		34		if (MaxUsedMappings == NumUsedMappings)
		35		MaxUsedMappings++;
		36		NumUsedMappings++;
		37		TotalMappingsCreated++;
		38		// If this is a partial update, then we are done.
		39		if (!WS.fullyUpdatesSuperRegs())
		40		return;
		41
		42		for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I)
		43		RegisterMappings[*I] = &WS;
		44		}
		45
		46		void RegisterFile::invalidateRegisterMapping(const WriteState &WS) {
		47		unsigned RegID = WS.getRegisterID();
		48		bool ShouldInvalidateSuperRegs = WS.fullyUpdatesSuperRegs();
		49
		50		assert(RegID != 0 && "Invalidating an already invalid register?");
		51		assert(WS.getCyclesLeft() != -512 &&
		52		"Invalidating a write of unknown cycles!");
		53		assert(WS.getCyclesLeft() <= 0 && "Invalid cycles left for this write!");
		54		if (!RegisterMappings[RegID])
		55		return;
		56
		57		assert(NumUsedMappings);
		58		NumUsedMappings--;
		59
		60		if (RegisterMappings[RegID] == &WS)
		61		RegisterMappings[RegID] = nullptr;
		62
		63		for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I)
		64		if (RegisterMappings[*I] == &WS)
		65		RegisterMappings[*I] = nullptr;
		66
		67		if (!ShouldInvalidateSuperRegs)
		68		return;
		69
		70		for (MCSuperRegIterator I(RegID, &MRI); I.isValid(); ++I)
		71		if (RegisterMappings[*I] == &WS)
		72		RegisterMappings[*I] = nullptr;
		73		}
		74
		75		// Update the number of used mappings in the event of instruction retired.
		76		// This mehod delegates to the register file the task of invalidating
		77		// register mappings that were created for instruction IS.
		78		void DispatchUnit::invalidateRegisterMappings(const Instruction &IS) {
		79		for (const std::unique_ptr<WriteState> &WS : IS.getDefs()) {
		80		DEBUG(dbgs() << "[RAT] Invalidating mapping for: ");
		81		DEBUG(WS->dump());
		82		RAT->invalidateRegisterMapping(*WS.get());
		83		}
		84		}
		85
		86		void RegisterFile::collectWrites(SmallVectorImpl<WriteState *> &Writes,
		87		unsigned RegID) const {
		88		assert(RegID && RegID < RegisterMappings.size());
		89		WriteState *WS = RegisterMappings[RegID];
		90		if (WS) {
		91		DEBUG(dbgs() << "Found a dependent use of RegID=" << RegID << '\n');
		92		Writes.push_back(WS);
		93		}
		94
		95		// Handle potential partial register updates.
		96		for (MCSubRegIterator I(RegID, &MRI); I.isValid(); ++I) {
		97		WS = RegisterMappings[*I];
		98		if (WS && std::find(Writes.begin(), Writes.end(), WS) == Writes.end()) {
		99		DEBUG(dbgs() << "Found a dependent use of subReg " << *I << " (part of "
		100		<< RegID << ")\n");
		101		Writes.push_back(WS);
		102		}
		103		}
		104		}
		105
		106		bool RegisterFile::isAvailable(unsigned NumRegWrites) {
		107		if (!TotalMappings)
		108		return true;
		109		if (NumRegWrites > TotalMappings) {
		110		// The user specified a too small number of registers.
		111		// Artificially set the number of temporaries to NumRegWrites.
		112		errs() << "warning: not enough temporaries in the register file. "
		113		<< "The register file size has been automatically increased to "
		114		<< NumRegWrites << '\n';
		115		TotalMappings = NumRegWrites;
		116		}
		117
		118		return NumRegWrites + NumUsedMappings <= TotalMappings;
		119		}
		120
		121		#ifndef NDEBUG
		122		void RegisterFile::dump() const {
		123		for (unsigned I = 0, E = MRI.getNumRegs(); I < E; ++I)
		124		if (RegisterMappings[I]) {
		125		dbgs() << MRI.getName(I) << ", " << I << ", ";
		126		RegisterMappings[I]->dump();
		127		}
		128
		129		dbgs() << "TotalMappingsCreated: " << TotalMappingsCreated
		130		<< ", MaxUsedMappings: " << MaxUsedMappings
		131		<< ", NumUsedMappings: " << NumUsedMappings << '\n';
		132		}
		133		#endif
		134
		135		// Reserves a number of slots, and returns a new token.
		136		unsigned RetireControlUnit::reserveSlot(unsigned Index, unsigned NumMicroOps) {
		137		assert(isAvailable(NumMicroOps));
		138		unsigned NormalizedQuantity =
		139		std::min(NumMicroOps, static_cast<unsigned>(Queue.size()));
		140		// Zero latency instructions may have zero mOps. Artificially bump this
		141		// value to 1. Although zero latency instructions don't consume scheduler
		142		// resources, they still consume one slot in the retire queue.
		143		NormalizedQuantity = std::max(NormalizedQuantity, 1U);
		144		unsigned TokenID = NextAvailableSlotIdx;
		145		Queue[NextAvailableSlotIdx] = {Index, NormalizedQuantity, false};
		146		NextAvailableSlotIdx += NormalizedQuantity;
		147		NextAvailableSlotIdx %= Queue.size();
		148		AvailableSlots -= NormalizedQuantity;
		149		return TokenID;
		150		}
		151
		152		void DispatchUnit::notifyInstructionDispatched(unsigned Index) {
		153		Owner->notifyInstructionDispatched(Index);
		154		}
		155
		156		void DispatchUnit::notifyInstructionRetired(unsigned Index) {
		157		Owner->notifyInstructionRetired(Index);
		158		}
		159
		160		void RetireControlUnit::cycleEvent() {
		161		if (isEmpty())
		162		return;
		163
		164		unsigned NumRetired = 0;
		165		while (!isEmpty()) {
		166		if (MaxRetirePerCycle != 0 && NumRetired == MaxRetirePerCycle)
		167		break;
		168		RUToken &Current = Queue[CurrentInstructionSlotIdx];
		169		assert(Current.NumSlots && "Reserved zero slots?");
		170		if (!Current.Executed)
		171		break;
		172		Owner->notifyInstructionRetired(Current.Index);
		173		CurrentInstructionSlotIdx += Current.NumSlots;
		174		CurrentInstructionSlotIdx %= Queue.size();
		175		AvailableSlots += Current.NumSlots;
		176		NumRetired++;
		177		}
		178		}
		179
		180		void RetireControlUnit::onInstructionExecuted(unsigned TokenID) {
		181		assert(Queue.size() > TokenID);
		182		assert(Queue[TokenID].Executed == false && Queue[TokenID].Index != ~0U);
		183		Queue[TokenID].Executed = true;
		184		}
		185
		186		#ifndef NDEBUG
		187		void RetireControlUnit::dump() const {
		188		dbgs() << "Retire Unit: { Total Slots=" << Queue.size()
		189		<< ", Available Slots=" << AvailableSlots << " }\n";
		190		}
		191		#endif
		192
		193		bool DispatchUnit::checkRAT(const InstrDesc &Desc) {
		194		unsigned NumWrites = Desc.Writes.size();
		195		if (RAT->isAvailable(NumWrites))
		196		return true;
		197		DispatchStalls[DS_RAT_REG_UNAVAILABLE]++;
		198		return false;
		199		}
		200
		201		bool DispatchUnit::checkRCU(const InstrDesc &Desc) {
		202		unsigned NumMicroOps = Desc.NumMicroOps;
		203		if (RCU->isAvailable(NumMicroOps))
		204		return true;
		205		DispatchStalls[DS_RCU_TOKEN_UNAVAILABLE]++;
		206		return false;
		207		}
		208
		209		bool DispatchUnit::checkScheduler(const InstrDesc &Desc) {
		210		// If this is a zero-latency instruction, then it bypasses
		211		// the scheduler.
		212		switch (SC->canBeDispatched(Desc)) {
		213		case Scheduler::HWS_AVAILABLE:
		214		return true;
		215		case Scheduler::HWS_QUEUE_UNAVAILABLE:
		216		DispatchStalls[DS_SQ_TOKEN_UNAVAILABLE]++;
		217		break;
		218		case Scheduler::HWS_LD_QUEUE_UNAVAILABLE:
		219		DispatchStalls[DS_LDQ_TOKEN_UNAVAILABLE]++;
		220		break;
		221		case Scheduler::HWS_ST_QUEUE_UNAVAILABLE:
		222		DispatchStalls[DS_STQ_TOKEN_UNAVAILABLE]++;
		223		break;
		224		case Scheduler::HWS_DISPATCH_GROUP_RESTRICTION:
		225		DispatchStalls[DS_DISPATCH_GROUP_RESTRICTION]++;
		226		}
		227
		228		return false;
		229		}
		230
		231		unsigned DispatchUnit::dispatch(unsigned IID, Instruction *NewInst) {
		232		assert(!CarryOver && "Cannot dispatch another instruction!");
		233		unsigned NumMicroOps = NewInst->getDesc().NumMicroOps;
		234		if (NumMicroOps > DispatchWidth) {
		235		assert(AvailableEntries == DispatchWidth);
		236		AvailableEntries = 0;
		237		CarryOver = NumMicroOps - DispatchWidth;
		238		} else {
		239		assert(AvailableEntries >= NumMicroOps);
		240		AvailableEntries -= NumMicroOps;
		241		}
		242
		243		// Reserve slots in the RCU.
		244		unsigned RCUTokenID = RCU->reserveSlot(IID, NumMicroOps);
		245		Owner->notifyInstructionDispatched(IID);
		246
		247		SC->scheduleInstruction(IID, NewInst);
		248		return RCUTokenID;
		249		}
		250
		251		#ifndef NDEBUG
		252		void DispatchUnit::dump() const {
		253		RAT->dump();
		254		RCU->dump();
		255
		256		unsigned DSRAT = DispatchStalls[DS_RAT_REG_UNAVAILABLE];
		257		unsigned DSRCU = DispatchStalls[DS_RCU_TOKEN_UNAVAILABLE];
		258		unsigned DSSCHEDQ = DispatchStalls[DS_SQ_TOKEN_UNAVAILABLE];
		259		unsigned DSLQ = DispatchStalls[DS_LDQ_TOKEN_UNAVAILABLE];
		260		unsigned DSSQ = DispatchStalls[DS_STQ_TOKEN_UNAVAILABLE];
		261
		262		dbgs() << "STALLS --- RAT: " << DSRAT << ", RCU: " << DSRCU
		263		<< ", SCHED_QUEUE: " << DSSCHEDQ << ", LOAD_QUEUE: " << DSLQ
		264		<< ", STORE_QUEUE: " << DSSQ << '\n';
		265		}
		266		#endif
		267
		268		} // namespace mca