Dynamic Recompiler Author's Guide - Revision history

Aaron: /* Front-end Analysis */

2008-07-08T20:09:35Z

Front-end Analysis

← Older revision		Revision as of 22:09, 8 July 2008
Line 157:		Line 157:

	== Front-end Analysis ==		== Front-end Analysis ==

			Once it has been determined that there is no translation present for a given PC, the dynamic recompiler is responsible for examining the emulated code and generating the equivalent UML output. The tricky part, believe it or not, is the "examining the emulated code" bit. For maximal efficiency, the recompiler is going to want to translate more than just one instruction at a time; however, it doesn't want to waste a bunch of time translating instructions that aren't going to be executed.

			Because this is a common challenge for any recompiler, the universal DRC provides a generic front-end to make it easier. Before proceeding, it is important to understand a few basic terms:

			* A code '''window''' is a predefined PC-relative lower and upper bound within which the analysis will take place. An example window from the MIPS3 case has a minimum of -128 and a maximum of 512. This means that as soon as any path through the code goes more than 128 bytes before the starting PC, or more than 512 bytes beyond the starting PC, it effectively stops the analysis.
			* A code '''block''' is the collection of instructions that result from walking through the code from the starting PC until all known paths terminate (either explicitly or by branching outside of the window)
			* A code '''sequence''' is a subset of a code block where all instructions from beginning to end are guaranteed to execute sequentially, with no branches into the middle
			* An opcode '''descriptor''' is a small structure that provides information about a single emulated instruction

			To illustrate these concepts, here's some made-up MIPS assembly:

			BFBFFFFC: ...
			BFC00000: ori r2,0,$1000 ; block seq1
			BFC00004: ori r3,0,$8000 ; block seq1
			BFC00008: sw 0,0(r2) ; block seq2
			BFC0000C: addi r3,r3,-1 ; block seq2
			BFC00010: bgez r3,BFC00008 ; block seq2
			BFC00014: addi r2,r2,4 ; block seq2 seq3
			BFC00018: jr r31 ; block seq3
			BFC0001C: nop ; block
			BFC00020: ...

			Now let's say our code cache is empty and we begin executing. Immediately, we find out that PC=BFC00000 is not present in the cache, so we exit and perform a recompilation. As a first step, we call the front-end, which we initialized previously to describe our window size and a pointer to our architecture-specific opcode analyzer.

			At this point, the front-end's job is to walk through the code to identify the largest block that fits within the window, and to identify sequences within the block. To do this, it starts with the first opcode and calls the architecture-specific analyzer with an empty descriptor. The analyzer's job is to set various flags in the descriptor to describe the instruction. Upon return, the front-end has enough information to know how to proceed in its analysis. It continues doing this until it has exhausted all code paths.

			Let's have a look at the opcode descriptor:

			<insert structure here>

			<Describe fields>

			<Walk through example above>

	== Static Subroutines ==		== Static Subroutines ==

Aaron: /* Setup and Initialization */

2008-07-08T19:33:00Z

Setup and Initialization

← Older revision		Revision as of 21:33, 8 July 2008
Line 135:		Line 135:
	mips3->impstate->drcfe = drcfe_init(&feconfig, mips3);		mips3->impstate->drcfe = drcfe_init(&feconfig, mips3);

	~~Initialize~~ front-end.		The next step is to initialize the front-end. In brief, the front-end (which is described in more detail in the next section) is responsible for walking through the code, determining register dependencies and code flow, and for breaking the code up into blocks to be recompiled. The drcfe_config structure describes the parameters for the code walk and provides a callback function pointer to the architecture-specific opcode analyzer function.

	/* ~~allocate memory for cache~~-~~local~~ state ~~and initialize it~~ */		/* copy tables to the implementation-specific state */
	memcpy(mips3->impstate->fpmode, fpmode_source, sizeof(fpmode_source));		memcpy(mips3->impstate->fpmode, fpmode_source, sizeof(fpmode_source));

	~~Copy tables.~~

	/* compute the register parameters */		/* compute the register parameters */
	for (regnum = 0; regnum < 34; regnum++)		for (regnum = 0; regnum < 34; regnum++)
Line 151:		Line 149:
	}		}

	~~/* if~~ we have registers ~~to spare~~, ~~assign r2, r3, r4~~ to ~~leftovers */~~		Now we're in the home stretch. If there is any required static initialization of the implementation-specific state, it can be done now. In this case, we have a table that we copy so that it is always accessible from the near cache. And then we build up a table of pointers to each of the registers, which we will use during code generation to quickly determine the parameter type and value given a MIPS register number. Note that because MIPS register 0 is always hard-coded to 0, we specify the type to be DRCUML_PTYPE_IMMEDIATE instead of DRCUML_PTYPE_MEMORY. This is one of the reasons why we store both a type and value for each parameter.
	~~if (!DISABLE_FAST_REGISTERS)~~
	{
	~~drcuml_get_backend_info(mips3->impstate->drcuml, &beinfo);~~
	~~if (beinfo.direct_iregs > 4)~~
	{
	~~mips3->impstate->regmap[2].type = mips3->impstate->regmaplo[2].~~type ~~= DRCUML_PTYPE_INT_REGISTER;~~
	~~mips3->impstate->regmap[2].value = mips3->impstate->regmaplo[2].~~value ~~= DRCUML_REG_I4;~~
	}
	~~if (beinfo~~.~~direct_iregs > 5)~~
	{
	~~mips3~~-~~>impstate->regmap[3].~~type ~~= mips3->impstate->regmaplo[3]~~.type ~~= DRCUML_PTYPE_INT_REGISTER;~~
	~~mips3->impstate->regmap[3].value = mips3->impstate->regmaplo[3].~~value ~~= DRCUML_REG_I5;~~
	}
	~~if (beinfo.direct_iregs > 6)~~
	{
	~~mips3->impstate->regmap[4].type = mips3->impstate->regmaplo[4].type = DRCUML_PTYPE_INT_REGISTER;~~
	~~mips3->impstate->regmap[4].value = mips3->impstate->regmaplo[4].value = DRCUML_REG_I6;~~
	}
	}

	~~Configure registers~~.

	/* mark the cache dirty so it is updated on next execute */		/* mark the cache dirty so it is updated on next execute */
	mips3->impstate->cache_dirty = TRUE;		mips3->impstate->cache_dirty = TRUE;

	~~Mark~~ cache dirty.		Finally, we mark cache dirty, which will force it to be flushed on the next (first) call to the CPU's execute function.

	== Front-end Analysis ==		== Front-end Analysis ==

Georg: /* Logic Flow */ typo

2008-07-02T05:41:43Z

Logic Flow: typo

← Older revision		Revision as of 07:41, 2 July 2008
Line 40:		Line 40:
	This may seem kind of odd at first, but let's step through the high-level flow to understand what is happening.		This may seem kind of odd at first, but let's step through the high-level flow to understand what is happening.

	The first thing we do is stash the number of cycles to execute somewhere where it will be accessible to the generated code. In this case we, store it in the CPU state. Then we begin our execution loop.		The first thing we do is stash the number of cycles to execute somewhere where it will be accessible to the generated code. In this case, we store it in the CPU state. Then we begin our execution loop.

	Now, in an ideal world, all the code we would ever want to execute has already been translated to the target architecture, and so to execute it, we simply jump into the translated code and begin execution. If this is in fact the case, then the generated code will execute for the number of cycles we stashed in the CPU state. When it is finished, it will return to the caller with a return code of EXIT_OUT_OF_CYCLES, indicating that all the cycles have been exhausted.		Now, in an ideal world, all the code we would ever want to execute has already been translated to the target architecture, and so to execute it, we simply jump into the translated code and begin execution. If this is in fact the case, then the generated code will execute for the number of cycles we stashed in the CPU state. When it is finished, it will return to the caller with a return code of EXIT_OUT_OF_CYCLES, indicating that all the cycles have been exhausted.

Aaron: /* Setup and Initialization */

2008-07-01T20:04:00Z

Setup and Initialization

Show changes

Aaron at 20:10, 24 June 2008

2008-06-24T20:10:37Z

← Older revision		Revision as of 22:10, 24 June 2008
Line 1:		Line 1:
	This is intended to be an introduction to how to write a dynamic recompiler using the universal architecture in MAME. I suspect it will eventually need to be broken into multiple separate pieces, but we'll keep it all together to start with.		This is intended to be an introduction to how to write a dynamic recompiler using the universal architecture in MAME. It is important to note that the description of how to write a dynamic recompiler below is not the only way to do so. In fact, the universal architecture is sufficiently flexible that it is possible to do something substantially different than what is described here and still make it work.

			The decription below essentially describes how the first two recompilers (MIPS3 and PowerPC) operate, and provides in general a well-tested framework for future recompilers.

			I suspect this article will eventually need to be broken into multiple separate pieces, but we'll keep it all together to start with.

	== Logic Flow ==		== Logic Flow ==

Aaron: /* Logic Flow */

2008-06-24T20:05:29Z

Logic Flow

← Older revision		Revision as of 22:05, 24 June 2008
Line 35:		Line 35:

	This may seem kind of odd at first, but let's step through the high-level flow to understand what is happening.		This may seem kind of odd at first, but let's step through the high-level flow to understand what is happening.

			The first thing we do is stash the number of cycles to execute somewhere where it will be accessible to the generated code. In this case we, store it in the CPU state. Then we begin our execution loop.

			Now, in an ideal world, all the code we would ever want to execute has already been translated to the target architecture, and so to execute it, we simply jump into the translated code and begin execution. If this is in fact the case, then the generated code will execute for the number of cycles we stashed in the CPU state. When it is finished, it will return to the caller with a return code of EXIT_OUT_OF_CYCLES, indicating that all the cycles have been exhausted.

			Of course, this is a ''dynamic'' recompiler. The word dynamic here refers to the fact that we do not translate all the code up front, but rather perform translation on the fly, as new code is encountered. This means that we will sometimes attempt to execute code that hasn't been translated yet. When this occurs, the translated code will return to the caller with a special return code of EXIT_MISSING_CODE, meaning that there is no valid translated code for the current PC. In response to receiving this return code, the recompiler must translate the new code into the code cache, and then call back again to the translated code to allow it to continue processing.

			It is also possible that during execution, a substantial change is made to the CPU's state, such that all previously translated code is immediately invalidated. In this situation, the translated code returns EXIT_FLUSH_CACHE, in response to which the recompiler will flush the cache. When finished, we loop back around and attempt to execute the translated code again. Of course, since we just flushed the cache, the expectation is that we will immediately return with an EXIT_MISSING_CODE so that we are forced to translate from scratch the code that was previously executing.

	== Setup and Initialization ==		== Setup and Initialization ==

Aaron: New page: This is intended to be an introduction to how to write a dynamic recompiler using the universal architecture in MAME. I suspect it will eventually need to be broken into multiple separate ...

2008-06-17T20:02:37Z

New page: This is intended to be an introduction to how to write a dynamic recompiler using the universal architecture in MAME. I suspect it will eventually need to be broken into multiple separate ...

New page

This is intended to be an introduction to how to write a dynamic recompiler using the universal architecture in MAME. I suspect it will eventually need to be broken into multiple separate pieces, but we'll keep it all together to start with.

== Logic Flow ==

The logic flow of an interpreter is pretty easy to understand, because it works like a CPU does:

mycpu_execute_interpreted(numcycles)
{
do
{
opcode = fetch_opcode();
execute_opcode(opcode);
numcycles -= opcode_num_cycles;
}
while (numcycles >= 0);
}

Essentially, the core execution of the interpreter consists of sitting in a loop, fetching a single opcode at a time, executing it, and counting up cycles until it is time to move on to something else in the emulation. The bulk of the code in an interpreter consists of the implementations of the individual opcodes, and must be relatively well-tuned because it is executed quite frequently.

In contrast, the logic flow of a dynamic recompiler is considerably less analagous to a CPU:

mycpu_execute_recompiled(numcycles)
{
cpustate.numcycles = numcycles;
do
{
return_code = (*recompiler_entry_point)();
if (return_code == EXIT_MISSING_CODE)
recompile_code_at_current_pc();
else if (return_code == EXIT_FLUSH_CACHE)
code_cache_flush();
}
while (return_code != EXIT_OUT_OF_CYCLES);
}

This may seem kind of odd at first, but let's step through the high-level flow to understand what is happening.

== Setup and Initialization ==

Compile-time versus run-time

== Front-end Analysis ==

== Static Subroutines ==

== Common Generation Functions ==

== General Opcode Behaviors ==

== Specific Opcode Behaviors ==