I've Been Thinking About This For Awhile Now.

[calc84maniac]

@VRAndy: I don't see a problem in PS3 emulation either

@Laurencedve: Some time ago, someone on this board explained to me why virtualisation is not an option with a DS emulator for the Pandora. Once you send the original code to directly to the CPU, it gets "out of control". It would cause huge snychonisation problems with the rest of the emulation.

Why not dynarec though? You'd think it would be easier to write a dynarec for an ARM on an ARM than a MIPS on an ARM.

Edit:
I'm not trying to get side-tracked on "extra features" here, but has anyone suggested yet to have the DS touchscreen on the Pandora screen and the top DS screen in TV-out? Or is it impossible to send two different images like that...

 

[Exophase]

Why not dynarec though? You'd think it would be easier to write a dynarec for an ARM on an ARM than a MIPS on an ARM.

Actually, I would say doing ARM on ARM is harder than doing MIPS on ARM, because ARM is just generally harder than MIPS. When performing software memory emulation and cycle counting you have to dance around the emulated flag state; MIPS doesn't have this problem since it doesn't have flags. You also have to contend with PC being a general purpose register, and predicated execution that jams up control flow. Oh, and the whole Thumb mode, which sadly DS games still use.

It's not an enormous difference, but doing a fast recompiler, or even any recompiler is still a pretty good workload. The frontend alone, ie tracking blocks, and dealing with modified code is at least somewhat non-trivial.

I've mentioned several obstacles and disadvantages to any kind of virtualization approach that I won't go over again. Having said that, recompilation (and probably virtualization in this context, for that matter) has a lot of overhead that isn't readily apparent. Doing memory emulation w/o MMU assistance is going to cost you, especially on a platform like DS with a relatively complex memory map. Using the MMU has its own tradeoffs - any trapped accesses become a lot slower. Games do at the very least occasionally bang I/O ports for reading off the gamecard, in other words they don't always use DMA even when they can. Write protection for code also becomes page-granular at best and you pay a lot for false positives. The other downside is that switching address spaces becomes much more expensive (TLB flush), and so long as you're emulating ARM7 at a low level you'll have to interleave it and ARM9 pretty tightly at times to get through some areas. High level emulation of ARM7 routines might be possible but it's pretty unproven.

So to recap, for dynarec you have to pay for:
- Scratch registers to store things, meaning spills to/from memory here and there
- Saving/restoring flags when necessary
- Cycle counting, and more expensive, cycle checking
- Higher cache pressure
- PC loads generate big constants
- Indirect branches are relatively expensive
- Stores have to be checked for self-modifying code
- Memory in general has a lot of cycles if done w/o MMU
- You won't want to keep Thumb as Thumb, worsening cache pressure (but you might be able to generate nicer code with optimizations)

Cortex-A8's performance is high, but part of it comes from code being properly scheduled and avoiding cache and BTB thrashing and poor predictability situations. Code written for earlier ARM CPUs won't necessarily fit this model very well.

Anyway, you could spend all day talking about how the CPUs can be emulated but you can't reach an answer about how DS can be emulated until you account for everything else you have to emulate, including very powerful 2D and pretty esoteric 3D and geometry engine.

 

[VRAndy]

So, obviously, I can't see any problem with a PS3 emulator.

Every time some dimwit quotes your post as proof that the Pandora can emulate the PS3, you owe me a dollar.

Maybe I'd better start a savings account. The only thing that saves me is that most of the dimwits don't use the search feature.

 

[ari64]

Why not dynarec though? You'd think it would be easier to write a dynarec for an ARM on an ARM than a MIPS on an ARM.

Actually, I would say doing ARM on ARM is harder than doing MIPS on ARM, because ARM is just generally harder than MIPS. When performing software memory emulation and cycle counting you have to dance around the emulated flag state; MIPS doesn't have this problem since it doesn't have flags. You also have to contend with PC being a general purpose register, and predicated execution that jams up control flow. Oh, and the whole Thumb mode, which sadly DS games still use.

MIPS has the SLT instructions, which are annoying in that they generally take three instructions to emulate, Sometimes it's actually easier to save flags.

Also have you seen how much code I had to write just to deal with the delay slots? Notaz is running into the same issues with SH2.

 

[Exophase]

MIPS has the SLT instructions, which are annoying in that they generally take three instructions to emulate, Sometimes it's actually easier to save flags.

Yeeeeeah.. no. I'm going to have to go with worrying about flags due to memory and cycle checking being worse than having to do two additional instructions on ARM. There's no way your problem costs you more instructions, but really it's just easier to deal with. How about dead flag elimination on MIPS? Not much to eliminate with no flags..

Also have you seen how much code I had to write just to deal with the delay slots? Notaz is running into the same issues with SH2.

I've heard, and while I take your word for it I'm not sure I grasp the challenge. If I gave you that you give me this: have you ever seen code on ARM which is executed as ARM code once then Thumb code later, without any modification to the code? I have.

 

[skeezix]

Exo -- isn't that what Roy says in Blade Runner?

But really.. you mean the same opcodes used in different ways, and it works? I'd never even thought of that. Its almost diabolical genius (Or do you mean it doesn't work, but was done? Or doesn't work, but with a desirable outcome?)

jeff

edit: watching a show in background, frakking started typgin what I was hearing

 

[Exophase]

It works. And it's horrible. I really hate the developers. They did so many awful things.

 

[calc84maniac]

Also have you seen how much code I had to write just to deal with the delay slots? Notaz is running into the same issues with SH2.

I've heard, and while I take your word for it I'm not sure I grasp the challenge. If I gave you that you give me this: have you ever seen code on ARM which is executed as ARM code once then Thumb code later, without any modification to the code? I have.

Well obviously you would use different translation pools for ARM code and Thumb code

 

[DasFool]

Exo -- isn't that what Roy says in Blade Runner?

I've seen things you people wouldn't believe. Attack ships on fire off the shoulder of Orion. I watched C-beams glitter in the darkness at Tannhäuser Gate. All those moments will be lost in time like tears in rain.

The jig is up Exophase, we know you're a skin job.

 

[ari64]

MIPS has the SLT instructions, which are annoying in that they generally take three instructions to emulate, Sometimes it's actually easier to save flags.

Yeeeeeah.. no. I'm going to have to go with worrying about flags due to memory and cycle checking being worse than having to do two additional instructions on ARM. There's no way your problem costs you more instructions, but really it's just easier to deal with. How about dead flag elimination on MIPS? Not much to eliminate with no flags..

Oh, there is a lot to eliminate on MIPS. Guess what the unneeded_registers function does? Exactly the same thing as the dead flag elimination you refer to, except it throws away registers. Without this, about 10% of the CPU time was spent storing dead values.

Also have you seen how much code I had to write just to deal with the delay slots? Notaz is running into the same issues with SH2.

I've heard, and while I take your word for it I'm not sure I grasp the challenge. If I gave you that you give me this: have you ever seen code on ARM which is executed as ARM code once then Thumb code later, without any modification to the code? I have.

When you generate code for the delay slot, you're going to put a branch after that instruction. Now think about what happens when another branch jumps to the instruction in the delay slot. Also the exception handler has to set a special flag when the instruction in the delay slot faults. And it makes the data flow analysis messy.

I've seen some nasty stuff but I think that wins. What did this code actually do?

 

[fusion_power]

Hmmm, so there is not a real benefit from the fact, that Pandora and DS using booth ARM processor Architecture?

 

[lulzfish]

Hmmm, so there is not a real benefit from the fact, that Pandora and DS using booth ARM processor Architecture?

No, I guess ARM doesn't have all the backwards-compatibilities and virtualization features like x86 has.

 

[Exophase]

Oh, there is a lot to eliminate on MIPS. Guess what the unneeded_registers function does? Exactly the same thing as the dead flag elimination you refer to, except it throws away registers. Without this, about 10% of the CPU time was spent storing dead values.

MIPS is not the only platform that has registers, nor is it the only scenario where you're emulating something that has more than what you're emulating on. I'm saying that platforms with flags have an additional challenge. Obviously if possible you don't want to emulate them completely in software. But they're accessed more indirectly than registers and have their own unique properties and problems. For what it's worth, I've been tracking register liveness in ARM based things too, although not just for allocation purposes.

When you generate code for the delay slot, you're going to put a branch after that instruction. Now think about what happens when another branch jumps to the instruction in the delay slot. Also the exception handler has to set a special flag when the instruction in the delay slot faults. And it makes the data flow analysis messy.

Exceptions as side-effects are always a pain in the ass to deal with in recompilers - I'll certainly grant you the extra irritation of tracking those in delay slots. But what you're describing for branches to delay slots seems sensitive to other design details. If you're linking branches internally inside blocks then it's a problem, but only in so much that you have to note where it happens and just not internally link to them. To handle internal branches you need a first pass that scans the block anyway, and you need to mark exit points. Marking the instruction after as a delay slot isn't much of a big deal.

Granted, I don't mean to make light of something that you've solved first hand and I haven't, I'm just giving my initial reaction to what I think I'd do. Is this something that comes up a lot?

I've seen some nasty stuff but I think that wins. What did this code actually do?

I wish I could tell you. I just remember it was one instruction or so and fell through into a bx or something that got it into ARM - it looked more like it was a "Thumb tolerant" header than anything else. My memory might be a little off though. Incidentally, this was a game that did several other things that made my life difficult: very heavy self modifying code (including modifications of the block currently executing), used the top half of a Thumb bl instruction independently, got the PC unaligned (I bet anything it was misuse of bl that caused this predicament), uses idle loops even though its predecessor didn't, has 64KHz audio output generated in software for some bizarre reason.. There are probably other things I'm forgetting. I had to fix obscure issue after issue to even get in to boot.

 

[ari64]

Oh, there is a lot to eliminate on MIPS. Guess what the unneeded_registers function does? Exactly the same thing as the dead flag elimination you refer to, except it throws away registers. Without this, about 10% of the CPU time was spent storing dead values.

MIPS is not the only platform that has registers, nor is it the only scenario where you're emulating something that has more than what you're emulating on. I'm saying that platforms with flags have an additional challenge. Obviously if possible you don't want to emulate them completely in software. But they're accessed more indirectly than registers and have their own unique properties and problems. For what it's worth, I've been tracking register liveness in ARM based things too, although not just for allocation purposes.

Liveness analysis for flags is essentially the same algorithm as for registers, so I assume you would do them at the same time. I also track the special registers (HI, LO) in the same function.

When you generate code for the delay slot, you're going to put a branch after that instruction. Now think about what happens when another branch jumps to the instruction in the delay slot. Also the exception handler has to set a special flag when the instruction in the delay slot faults. And it makes the data flow analysis messy.

Exceptions as side-effects are always a pain in the ass to deal with in recompilers - I'll certainly grant you the extra irritation of tracking those in delay slots. But what you're describing for branches to delay slots seems sensitive to other design details. If you're linking branches internally inside blocks then it's a problem, but only in so much that you have to note where it happens and just not internally link to them. To handle internal branches you need a first pass that scans the block anyway, and you need to mark exit points. Marking the instruction after as a delay slot isn't much of a big deal.

That's basically what I did. If the target is in a delay slot then it will not internally link to it. The challenge is to come up with a solution that doesn't involve compiling the block twice.

Granted, I don't mean to make light of something that you've solved first hand and I haven't, I'm just giving my initial reaction to what I think I'd do. Is this something that comes up a lot?

Well, I haven't developed any great solutions. If I did, it would probably involve recompiling that one instruction and then jumping to the next instruction after the delay slot.

Some games never do this and others do. I suspect that Nintendo used different compilers throughout the N64's lifetime. Different compilers tend to leave distinctive signatures. Besides the handling of delay slots, there are other things like how it does moves. In some games it's always OR r2, r1, r0 and in others it's DADD r2, r1, r0.

I wish I could tell you. I just remember it was one instruction or so and fell through into a bx or something that got it into ARM - it looked more like it was a "Thumb tolerant" header than anything else. My memory might be a little off though. Incidentally, this was a game that did several other things that made my life difficult: very heavy self modifying code (including modifications of the block currently executing), used the top half of a Thumb bl instruction independently, got the PC unaligned (I bet anything it was misuse of bl that caused this predicament), uses idle loops even though its predecessor didn't, has 64KHz audio output generated in software for some bizarre reason.. There are probably other things I'm forgetting. I had to fix obscure issue after issue to even get in to boot.

What happens when you get the PC unaligned? Doesn't it just ignore the lower two bits?

 

[calc84maniac]

I wish I could tell you. I just remember it was one instruction or so and fell through into a bx or something that got it into ARM - it looked more like it was a "Thumb tolerant" header than anything else. My memory might be a little off though. Incidentally, this was a game that did several other things that made my life difficult: very heavy self modifying code (including modifications of the block currently executing), used the top half of a Thumb bl instruction independently, got the PC unaligned (I bet anything it was misuse of bl that caused this predicament), uses idle loops even though its predecessor didn't, has 64KHz audio output generated in software for some bizarre reason.. There are probably other things I'm forgetting. I had to fix obscure issue after issue to even get in to boot.

What happens when you get the PC unaligned? Doesn't it just ignore the lower two bits?

I think I remember when reading ARM docs a while back that what happens is "UNPREDICTABLE".

 

[Exophase]

Liveness analysis for flags is essentially the same algorithm as for registers, so I assume you would do them at the same time. I also track the special registers (HI, LO) in the same function.

Yes. The analysis itself isn't an additional challenge. It's resolving it (in a useful way) with native flag generation. Flags are generally trickier than ordinary registers because of their tighter coupling to each other. In other words, it's more the "elimination" part and the role it plays in interacting with what you still do have to generate that matters.

When you generate code for the delay slot, you're going to put a branch after that instruction. Now think about what happens when another branch jumps to the instruction in the delay slot. Also the exception handler has to set a special flag when the instruction in the delay slot faults. And it makes the data flow analysis messy.

That's basically what I did. If the target is in a delay slot then it will not internally link to it. The challenge is to come up with a solution that doesn't involve compiling the block twice.

Some games never do this and others do. I suspect that Nintendo used different compilers throughout the N64's lifetime. Different compilers tend to leave distinctive signatures. Besides the handling of delay slots, there are other things like how it does moves. In some games it's always OR r2, r1, r0 and in others it's DADD r2, r1, r0.

I don't think duplicating that part of the block is a big deal unless those branches are being used constantly (I doubt it). You'll never eliminate complete redundancy in a recompiler while still having a very good design.

What happens when you get the PC unaligned? Doesn't it just ignore the lower two bits?

On GBA, yes. Like the ARM vs Thumb problem and branches to delay slots I'd say the bigger issue isn't so much how to actually take care of it - that was easy, just force alignment of PC. It's more that you never really think that you'll have to take care of it in the first place.

I think I remember when reading ARM docs a while back that what happens is "UNPREDICTABLE".

Unfortunately, those kinds of documents are written for people using the hardware or as requirements for people licensing it. An actual hardware implementation will rarely be sufficiently unpredictable so as to negate needing proper emulation - if software relies on it. Of course, usually software doesn't.

 

[notaz]

How do you guys handle interrupts caused by i/o writes (i.e. unmasking)? I don't like the idea of doing checks and ending blocks after every write.

 

[ari64]

How do you guys handle interrupts caused by i/o writes (i.e. unmasking)? I don't like the idea of doing checks and ending blocks after every write.

I do checks, but don't end the block. The N64 RAM is mapped from 80000000 to 807FFFFF, so I do

cmp r0,#0x800000
bvc exception_handler
str r1,[r0]

At the end of the block, I generate the exception handler and fill in the branch target. When doing constant propagation, the check isn't necessary.

After that, there's a second check for self-modifying code.

 

[Exophase]

How do you guys handle interrupts caused by i/o writes (i.e. unmasking)? I don't like the idea of doing checks and ending blocks after every write.

For gpSP I didn't have dynamic register allocation in any of the recompiler backends, so the problem wasn't quit as severe, ie flag and register mappings were in a known state before stores. In this situation, you will need to know the PC at the store so it can be passed to the interrupt handler. There are a few ways to do this. In the MIPS version I stored it in a register and had a register track the base PC of a block. In the ARM version I stored it as a constant after the function call (all loads/stores called functions) and loaded the value pointed to by lr (and returned to lr + 4). With a little more work you could store it in a separate table. I'm thinking of having native to emulated PC mappings for stores stored in a block header that comes before blocks and searching backwards for that header. You can also have a totally unrelated hash map or sorted list; since you add to the translation buffer sequentially the relations stay sorted.

Once you have the PC you can have the function that the store called return to whereever interrupts go instead of the normal return location. When the interrupt handler returns to that PC it'll end up recompiling a new block at that location. If a lot of instructions conditionally cause exceptions then you'll end up duplicating parts of a lot of blocks, but this shouldn't happen if there's no MMU.

If you have dynamic register/flag mapping then you have to do something else to recover the registers. Laurent's idea is to retranslate the block to find what the mapping is at that point. If you can spend the space you can store it along with the PC wherever you store that, largely depending on how expensive your mappings are - for SH2 I would guess something like 4 bits per 12 or so registers, so 6 bytes.

 

[ari64]

If you have dynamic register/flag mapping then you have to do something else to recover the registers. Laurent's idea is to retranslate the block to find what the mapping is at that point. If you can spend the space you can store it along with the PC wherever you store that, largely depending on how expensive your mappings are - for SH2 I would guess something like 4 bits per 12 or so registers, so 6 bytes.

My epilogue code sets the PC and saves whatever registers need to be saved. I don't store the mapping anywhere else.