Very nice. Thanks for the explanation. It sounds analogous to a pipeline like this:

[FetchOpcode] —> [FetchOperand (stall)] —> [FetchData] —> [Execute] —> [???] —> [WriteBack]

... where the next instruction is fetched when the current one is at the FetchData stage (i.e. FetchOperand is a “stall” state). But I’m not sure if all instructions go through all stages in your design.

_________________
C74-6502 Website: https://c74project.com

While getting Fig FORTH up and running, I've been pondering how best to manage self-modifying code in the pipeline. There are two key issues:

1) Detection: Data is written to memory in the WriteBack stage. A series of comparators can check whether we are writing to an address already in the pipeline. To that end, each pipeline register can have a "source" field which stores the memory address of the instruction held there. In the brute force method, each stage would have as many source-address fields as bytes in the instruction, and every write would be compared against every byte address in every pipeline stage. With seven stages and up to three bytes per insrtruction, you end up with an additional 21 comparators -- plus additional ICs beyond that to make the pipeline registers wide enough to store the addresses. That's probably not practical. One alternative to reduce the required hardware is to use only word-addresses (32-bit) in the comparisons, which has some drawbacks. Perhaps there are others solutions as well.

2) Action: The accepted practice is to flush the modified instructions from the pipeline whenever self-modifying code (SMC) is detected (see here for a good discussion of SMC handling on x86). In essence, the pipeline writes NOPs to the modified stage and all downstream stages, and then starts fetching from the source address of the modified stage to reload the instructions. Ironically this makes self-modifying code slower than otherwise, which is precisely the reverse effect from what the programmer would have inteded. Indeed, it's likely that the offending code will be an often-executed critical snippet, and the additional NOPs will significantly punish CPI. Once again, there may be alternatives worth exploring.

I thought for now I would simply share the general contours of the issue. I'll be working on the final fix for this down the road a bit, and as always I can use all the help I can get.

Cheers for now,
Drass

P.S. Here's a bit of fun trivia. The x86 discussion mentioned above contains a reference to US Patent 6237088 "System and method for tracking in-flight instructions in a pipeline", The patent appears to cover a detection mechanism for self-modifying code similar to the one described above (except that addresses are kept in a separate "Line Address Buffer" rather than in the pipeline itself). The patent was granted to Intel in May 2001 and appears to have expired in June of 2018. National Semiconductor filed a similar patent in 1997 (both patents were granted, so I assume these were deemed sufficiently different by the patent office) -- US Patent 5835949A "Method of identifying and self-modifying code". This patent seems to have expired in 2014. It’s described as follows:

"A system and method of readily identifying and handling self-modifying variable length instructions in a pipelined processor is disclosed employing index tags associated with each stage of the execution pipeline wherein the index tags identify the cache line numbers in the instruction cache from which the instructions originate."

It's comforting to know that both these patents are now expired. Looks like we can safely proceed with this project after all ... Phew!

_________________
C74-6502 Website: https://c74project.com

Drass:

It seems like a bunch of work on your part to support self-modifying code. You seem to be considering self-modifying code as a necessity. In the case of figFORTH, it does modify the dispatch address in page zero (if I remember correctly), but I'm pretty sure that the number of cycles, i.e. number of instructions, that dispatch initiates is far more than the depth of the pipeline as you've described. It is perfectly valid to support self-modifying code with a stipulation that the modified code cannot be executed within the depth of the pipeline; put the onus on the programmer to ensure that the modifications that he's making to the instruction stream will be valid before the processor cycles back to execute the modified instruction.

In other words, take a pointer from one of the reference / fundamental RISC architectures of the last century: Microprocessor without Interlocked Pipeline Stages (MIPS).

The cache coherency and program security issues associated with self-modifying code will be problem enough for your architecture to tackle without also taking into account modifications to the instruction stream less than the depth of your processor's pipeline.

_________________
Michael A.

Thanks for the perspective Michael. Your point is well taken.

It's relatively easy to expertiment with the simulation, so there is little downside to exploring options. Then, even if left out of the hardware implementation, support for self-modifyng code in the simulation may be a helpful diagnostic tool to identify the issue in existing software (it might display some diagnostics to identify the problem areas, for example, and perhaps even "patch" the code as needed -- as an side, there are other areas worth exploring where the simulation may become a companion "optimizer").

The fact that both BASIC (GETCHR) and figFORTH (EXEC) use tight self-modifying code is a motivating factor. It would be nice to run these 6502 staples without modification. Alas, I agree that may prove impractical in the end. If so, then a tool which creates a pipeline-compatible binary, or at least provides some help in doing so, will be desirable.

_________________
C74-6502 Website: https://c74project.com

Alright, fig-FORTH is up and running on the pipeline!

Dr Jefyll was kind enough to supply a version of fig-FORTH that runs in the Kowalski simulator (many thanks Jeff). I used our good friend the Sieve of Eratosthenes as a test once again. This time it was a version from rosettacode which Dr Jefyll adapted to run on fig-FORTH. Here it is:

Fig-FORTH uses self-modifying code in the NEXT routine, which as Michael suspected, works just fine in the pipeline. Unfortunately, fig also uses self-modifying code in the EXEC routine, and this did require that three NOPs be inserted into the code stream. Once that was done, the prime sieve ran happily to 100, as follows:

Performance is quite good at 1.22 CPI and 2.7x NMOS — not bad at all actually. Tournament prediction does quite well at 93% accuracy. Indeed, with 93% of branches taken on this run, 2-bit prediction does equally well. I know we had wondered how the pipeline might deal with data-oriented branches in this code, but evidently branching is in fact quite regular. Thus far only the BASIC interpreter has needed the more sophisticated predictor.

I noted a few other performance-related items on this run:

• Data Stalls are unusually high at 9%. This is largely due to the common practice of modifying an index register just prior to using it in an indexed operation. Interestingly, this is often arbitrary and could be avoided by re-ordering instructions slightly. The condition is realtively easy to detect, so I'm pondering whether some optimizations may be appropriate here.
• Delay Slots are high also at 7%. This is largely due to the indirect jump in the often-executed NEXT routine. I suspect the other FORTH variants (that Garth listed here) will perform differently in this regard. (I would be curious to test some of these. Can anyone provide some pointers to them? Ideally, I would need source code which will run in the Kowalski simulator so I can more easilty deal woth self-modifying code).
• It's interesting to note that there are a lot of JMP <abs> instructions in this code -- 7% of executed instructions are JMPs (not shown in the Run Stats). I mention this because it may be possible to optimize these jumps out with “zero-cycle” jumps. More on that later.

Ok, so that’s a whole lot of fun. All in all I'm very happy with this result. We’ll have to see whether any additional optimizations make sense for FigFORTH. More to come ...

Chees for now,
Drass

EDIT: Best to correct typo in the FORTH code that Dr Jefyll points out below. Thanks Jeff!

_________________
C74-6502 Website: https://c74project.com

Nice result! And it's very good to see in-the-wild natural use of self-modifying code - instead of worrying about it as an abstract possibility, we see actual examples. And we see how to calm it down to run on a machine that won't run it as-is.

In case anyone's wondering, EXEC is a label in the assembly source. The corresponding Forth word is EXECUTE .

Also, this 2dup definition which I hacked together contains a typo which we later corrected. Forth afficianados will realize there's supposed to be a space after the ( .

It's nice to see the high accuracy rates. But most primitives are fairly short, which means FIG Forth spends a lot of its time executing NEXT. And, the only conditional branch in NEXT is embarrassingly predictable! (After the ADC that adds 2 to IP-low, there's a BCC that detects those rare occasions when a carry results and IP-high needs to be incremented.) So, as always, we need to remain aware of what the stats don't tell us.

ETA: Hm, a lot of time spent in NEXT doesn't necessarily mean most of the conditional branches encountered are in NEXT. Hmmm!

-- Jeff

_________________
In 1988 my 65C02 got six new registers and 44 new full-speed instructions!
https://laughtonelectronics.com/Arcana/ ... mmary.html

Thanks for catching that Jeff. I edited the post above to correct the typo.

A quick test shows that just about 50% of branches are in fact executions of the BCC in the NEXT routine. That certainly contributes to the very high number of taken branches in this run, and makes over all prediction easier.

But even so, 93%-taken seems high, and shows a significant bias even outside NEXT. My speculation is that it’s all about 16-bit integer arithmetic in this case. As you suggest, adjusting the high-byte of 16-bit quantities is an example of a forward branch that is almost always taken. (In fact, this is probably an example of a common 6502 idiom which MichaelM has suggested might aid prediction). There is likely a lot of that going on here given the program under test.

Forward branches are often presented in various articles as likely not-taken. But those folks may not be thinking about 16-bit integer arithmetic on an 8-bit processor.

_________________
C74-6502 Website: https://c74project.com

Maybe short-distance forward branches are usually taken?

Good insight BigEd! I did some testing and indeed short-range forward branches (of 5 bytes or less) are taken about 96% of the time in the Basic and Forth tests. I think this confirms your intuition quite decisively.

[EDIT: Thinking through this ... ]

_________________
C74-6502 Website: https://c74project.com

Alright, I did a little more digging with the Forth Prime Sieve test ...

48% of all executed branches in this test are short-range branches, and of those 98% are taken. We might expect, therefore, that telling the predictor to assume that short-range branches are taken should improve accuracy significantly. Unfortunately, that’s not the case. Changing the initial assumption has no measurable effect on accuracy rate. The reason is that the 2-bit predictor is a quick learner, particularly when presented with such a regular stream of branches.

To see it in action, I ran some traces which show the 2-bit predictor working over time. It takes about 300,000 cycles for the Forth Prime Sieve to run to completion. Below are traces showing the number and percentage of mispredictions over the first 30,000 cycles. The first run is performed with the usual BTFNT assumption, and the second with a “Backward and Short-Forward taken, Long-Forward not-taken” assumption.

Here is the standard BTFNT run:

And now the modified run:
As we can see, the modified predictor does much better to start, but the advantage is reduced to just 1% after 30,000 cycles. In fact, we can see that in the last 1,000 cycles of the trace, both runs report exactly the same number of mispredictions (20). After 300,000 cycles of largely equivalent performance, the initial advantage is vanishingly small and both assumptions are equivalent for all practical purposes.

This is all to say that although this modified assumption is in fact better, it is only so over a very short run. Still, it’s an improvement and one which I am glad we have identified. We’ll have to see whether other tests show it be valuable enough to justify the additional complexity (i.e. having to test the the size of the branch offset before deciding whether a branch should be taken or not). For the time being, we’ll just add it to our bag of tricks and move on.

Many thanks to BigEd for identifying it!

Cheers for now,
Drass

_________________
C74-6502 Website: https://c74project.com

Interesting! I wonder, if there's a not-too-helpful distorting effect in running a short benchmark for a long time. If, for example, we ran a Basic interpreter running a reasonably diverse but not especially loopy program, might we get different answers?

I would be very interested to try more substantial Basic or Forth programs. Can you suggest some? Realistically, programs with substantial running times are going to include loops, but your point is well taken. We could do better than these very tight looping benchmarks.

_________________
C74-6502 Website: https://c74project.com

On another note, I mentioned earlier that it may be possible to optimize JMP <abs> instructions out of the pipeline using zero-cycle jumps. This a relatively straight-forward change whereby the btb entry for a JMP is applied to the instruction preceding it, rather than to the JMP itself. The CPU will then skip the JMP in future encounters and jump from the preceding instruction directly to the target address of the JMP. (Recall that the Branch Target Buffer stores the address of the Next PC for the Fetch stage). The JMP instruction itself is not executed, so the jump complets in zero cycles.

There is one caveat to this mechanism. An unconditional JMP btb entry cannot be applied to the preceding instruction if that instruction requires a btb entry of its own (i.e., the instruction is a branch, RTS or indirect jump). It turns out that about half of the executed JMP instructions in the figFORTH code originate from a single JMP -- the one in the NEXT routine. As (bad) luck would have it, this JMP is preceded by a conditional branch (the BCC that Dr Jefyll refers to above). This JMP will therefore only be optimized out about once every 128 iterations, when the preceding branch is not taken.

Even so, the change will reliably optimize the other half of the JMPs, which is beneficial. Let's look at the impact on the Prime Sieve run:
As we can see, just about half of the JMP instructions have been successfuly "Skipped" in this run. These skipped JMPs have legitimately completed though, so this number is added to the total count of completed instructions when calculating CPI. As a result, CPI drops from 1.22 in the pervious run to 1.18 in this run -- a meaningful improvement.

Interestingly, we see also that Data Stalls have increased slightly from 9% to 10%. This is due to the fact that certain eliminated jumps sat between instructions that share a mutual dependency. With jumps gone, these instructions now execute one after the other in the code stream, and trigger a stall as a result. In effect, the JMP is being immediately replaced by a Data Stall in these instances. Thankfully this happens only rarely.

For a bit of fun, it's pretty magical to see the skipped JMPs dissapear from the pipeline. Note the jmp $0244 in the cycle below (between inx and ldy #1 instructions):
And now, we run the same test with zero-cycle-jumps enabled, and ... Shazzam!
... the jmp is gone (note inx is followed immediately by ldy #1). Neat.

Cheers for now,
Drass

_________________
C74-6502 Website: https://c74project.com