PIN Branch Predictor for ARM + correlation with JSC vPC

brpredict.cpp

#include "pin.H"

#include <map>
#include <iostream>

const int *vPC_address = NULL;

KNOB<ADDRINT> KnobVPCAddress(KNOB_MODE_WRITEONCE, "pintool", "address", "0", "");

struct Branch
{
	int vPC;
	void *pc;
	bool taken;
	void *target;
	void *fallthrough;

	Branch(void *_pc, bool _taken, void *_target, void *_fallthrough)
		: vPC(*vPC_address)
		, pc(_pc)
		, taken(_taken)
		, target(_target)
		, fallthrough(_fallthrough)
	{
	}
};

class BTB
{
public:
	struct Entry
	{
		void *target;
		void *pc_tag;
		int vPC_tag;
	};

private:
	bool correlate_vPC;
	Entry entries[256][2];

	Entry *e(const Branch &br)
	{
		if (correlate_vPC)
		{
			return entries[(reinterpret_cast<uintptr_t>(br.pc) ^ br.vPC) & 0xFF];
		}
		else
		{
			return entries[reinterpret_cast<uintptr_t>(br.pc) & 0xFF];
		}
	}

	bool match(const Branch &br, const Entry &entry)
	{
		return br.pc == entry.pc_tag && (!correlate_vPC || br.vPC == entry.vPC_tag);
	}

public:
	BTB(bool _correlate_vPC)
		: correlate_vPC(_correlate_vPC)
	{
	}

	Entry *target(const Branch &br)
	{
		Entry *entry = e(br);

		if (match(br, entry[0]))
		{
			return &entry[0];
		}
		else if (match(br, entry[1]))
		{
			return &entry[1];
		}
		else
		{
			return NULL;
		}
	}

	void update(const Branch &br)
	{
		Entry *entry = e(br);

		if (match(br, entry[0]))
		{
			entry[1] = entry[0];
		}

		entry[0].target = br.target;
		entry[0].pc_tag = br.pc;
		entry[0].vPC_tag = br.vPC;
	}
};

class GHB
{
	int buffer[256][16];
	uint16_t history;
	bool correlate_vPC;

	int &count(const Branch &br)
	{
		uint8_t hi = history >> 2;
		uint8_t lo = (history & 3);
		lo += lo << 2;
		lo ^= reinterpret_cast<uintptr_t>(br.pc) & 0xF;

		if (correlate_vPC) lo ^= br.vPC & 0xF;

		return buffer[hi][lo];
	}

public:

	GHB(bool _correlate_vPC)
		: correlate_vPC(_correlate_vPC)
	{
		std::fill(&buffer[0][0], &buffer[255][15], 0);
	}

	bool predict(const Branch &br)
	{
		return count(br) >= 2;
	}

	void update(const Branch &br)
	{
		int &c = count(br);

		if (br.taken)
			c = std::min(c + 1, 3);
		else
			c = std::max(c - 1, 0);

		history = ((history << 1) | br.taken) & 0x3FF;
	}
};

struct Statistics {
	size_t executed;
	size_t predicted;
	size_t correct;

	Statistics()
		: executed(0)
		, predicted(0)
		, correct(0)
	{
	}
};

#define NumPredictors 4

class Predict
{
	GHB ghb;
	BTB btb;

	static Predict predictors[NumPredictors];
	static std::map<void*, Statistics*> branch_stats;

	Predict(bool correlate_GHB_vPC, bool correlate_BTB_vPC)
		: ghb(correlate_GHB_vPC)
		, btb(correlate_BTB_vPC)
	{
	}

public:

	static
	void predict(void *ins, bool taken, void *target, void *fallthrough)
	{

		Branch br(ins, taken, target, fallthrough);

		for (size_t i = 0; i < NumPredictors; ++i)
		{
			BTB::Entry *entry = predictors[i].btb.target(br);
			Statistics *&stats_entry = branch_stats[br.pc];

			if (!stats_entry)
			{
				stats_entry = new Statistics[NumPredictors];
			}

			Statistics &stats = stats_entry[i];

			++stats.executed;

			if (entry)
			{
				++stats.predicted;

				void *prediction = entry->target;
				void *next = br.target;

				if (br.fallthrough)
				{
					prediction = predictors[i].ghb.predict(br) ? prediction : br.fallthrough;
					next = br.taken ? next : br.fallthrough;
				}

				if (prediction == next)
					++stats.correct;

				predictors[i].ghb.update(br);
			}

			predictors[i].btb.update(br);
		}

	}

	static
	VOID summary(INT32, VOID*)
	{
		Statistics total;

		std::map<void*, Statistics*>::iterator i;
		for (i = branch_stats.begin(); i != branch_stats.end(); ++i)
		{
			Statistics *stats = i->second;

			size_t max_index = 0;

			std::cout << i->first << "\t" << stats[0].executed;
			std::cout << "\t" << stats[0].correct << "\t" << stats[0].predicted;

			for (size_t i = 1; i < NumPredictors; ++i)
			{
				if (stats[i].correct > stats[max_index].correct)
				{
					max_index = i;
				}

				std::cout << "\t" << stats[i].correct << "\t" << stats[i].predicted;

			}

			std::cout << "\t" << max_index << std::endl;

			total.predicted += stats[max_index].predicted;
			total.correct   += stats[max_index].correct;
			total.executed  += stats[max_index].executed;
		}

		std::cout << std::endl;
		std::cout << std::endl;
		std::cout << " Executed: " <<  total.executed << std::endl;
		std::cout << "Predicted: " << total.predicted << std::endl;
		std::cout << "  Correct: " <<   total.correct << std::endl;
	}
};

Predict Predict::predictors[NumPredictors] = { Predict(false, false), Predict(false, true), Predict(true, false), Predict(true, true) };
std::map<void*, Statistics*> Predict::branch_stats;

VOID BranchInstruction(INS ins, void *vPC)
{
	if (INS_IsBranch(ins))
	{
		IMG img = IMG_FindByAddress(INS_Address(ins));
		if (IMG_Valid(img) && IMG_IsMainExecutable(img))
		{
			INS_InsertCall(ins, IPOINT_BEFORE, (AFUNPTR) Predict::predict,
					IARG_INST_PTR,
					IARG_BRANCH_TAKEN,
					IARG_BRANCH_TARGET_ADDR,
					IARG_FALLTHROUGH_ADDR,
					IARG_END);
		}
	}
}

int main(int argc, char *argv[])
{
	if (PIN_Init(argc, argv))
	{
		return -1;
	}

	vPC_address = reinterpret_cast<int*>(KnobVPCAddress.Value());

	PIN_InitSymbols();

	INS_AddInstrumentFunction(BranchInstruction, NULL);
	PIN_AddFiniFunction(Predict::summary, NULL);

	PIN_StartProgram();

	return 0;
}

run.sh

# From within the PerformanceTests/SunSpider directory
$PIN/pin -t $PIN/source/tools/SimpleExamples/obj-intel64/brtrace.so -address 0x9279f8 > predicted.out -- $WEBKIT/Release/Programs/jsc -f sunspider-0.9.1-results/sunspider-test-prefix.js -f resources/sunspider-standalone-driver.js

WebKit.diff

Index: Source/JavaScriptCore/interpreter/Interpreter.cpp
===================================================================
--- Source/JavaScriptCore/interpreter/Interpreter.cpp	(revision 80598)
+++ Source/JavaScriptCore/interpreter/Interpreter.cpp	(working copy)
@@ -75,6 +75,8 @@
 
 namespace JSC {
 
+Instruction* globalVPC;
+
 // Returns the depth of the scope chain within a given call frame.
 static int depth(CodeBlock* codeBlock, ScopeChainNode* sc)
 {
@@ -1489,7 +1491,7 @@
 #if ENABLE(OPCODE_SAMPLING)
     #define SAMPLE(codeBlock, vPC) m_sampler->sample(codeBlock, vPC)
 #else
-    #define SAMPLE(codeBlock, vPC)
+    #define SAMPLE(codeBlock, vPC) do { globalVPC = vPC; } while(false)
 #endif
 
 #if ENABLE(COMPUTED_GOTO_INTERPRETER)
Index: configure.ac
===================================================================
--- configure.ac	(revision 80598)
+++ configure.ac	(working copy)
@@ -865,12 +865,9 @@
 AC_MSG_RESULT([$with_font_backend])
 
 # Add '-g' flag to gcc if it's debug build
-if test "$enable_debug" = "yes"; then
    CXXFLAGS="$CXXFLAGS -g"
    CFLAGS="$CFLAGS -g"
-else
    AC_DEFINE([NDEBUG], [1], [Define to disable debugging features])
-fi
 
 # Add the appropriate 'O' level for optimized builds
 if test "$enable_optimizations" = "yes"; then
delete this gist
Comments are parsed with GitHub Flavored Markdown