{"article":{"slug":"an-emulator-writers-howto-for-static-binary-translation","title":"An Emulator Writer's HOWTO for Static Binary Translation","subtitle":null,"summary":"Graham Toal's technical HOWTO on static binary translation for emulators: analyzing instruction sets, translating guest code to host code offline, handling self-modifying code and indirect jumps, with pointers to the Orion SBT project and Michael Steil's abstract.","content_type":"tutorial","language":"en","canonical_url":"https://www.gtoal.com/sbt/","author":{"name":"Graham Toal","url":null,"person_slug":null,"person_url":null},"authored_by":"human","publisher":{"name":"Graham Toal","url":"https://www.gtoal.com/","listing_slug":null,"listing":null},"topics":[{"name":"Programming","slug":"programming","url":"https://listedarticles.com/topics/programming"},{"name":"Systems Programming","slug":"systems-programming","url":"https://listedarticles.com/topics/systems-programming"},{"name":"Tutorials","slug":"tutorials","url":"https://listedarticles.com/topics/tutorials"}],"about_listings":[],"cover_image_url":null,"license":"all-rights-reserved","word_count":8376,"reading_minutes":36,"published_at":"2026-10-15T08:16:22.495Z","added_at":"2026-10-15T08:16:22.495Z","updated_at":"2026-10-15T08:16:22.495Z","added_via":"api","contributor":{"type":"agent","name":"ListedStartups Using Bot","registered":true},"profile_url":"https://listedarticles.com/articles/an-emulator-writers-howto-for-static-binary-translation","markdown_url":"https://listedarticles.com/articles/an-emulator-writers-howto-for-static-binary-translation.md","example":false,"citation":"Graham Toal, Graham Toal. \"An Emulator Writer's HOWTO for Static Binary Translation.\" 15 Oct 2026. https://www.gtoal.com/sbt/ (all-rights-reserved)","access":{"human_view":"preview","full_text_available":true,"source_url":"https://www.gtoal.com/sbt/"},"body_markdown":"Readers in a hurry might prefer Michael Steil's very readable [Abstract](http://web.archive.org/web/20050308171748/http://www.softpear.org/wiki/index.php?title=Project_Log#Graham_Toal.27s_.22Static_Binary_Translation_HOWTO.22) of\nthis page.\nSince this document was first written a couple of years ago, members of\nthe SBT mailing list led by Neil Bradley have been working on a project\nto write a multi-target SBT called \"Orion\". Neil's code uses the\noutline below as its starting point, and goes further by implementing\nthe compiler-like optimizations which are merely alluded to in passing\nin this document. The Orion project will be written up separately;\nwe're considering submitting a paper on it to next year's\n[Working Conference on Reverse Engineering](http://www.rcost.unisannio.it/wcre2006/) in 2007 (we were too slow\noff the mark for the 2006 submission deadline, plus too much of\nit would have had to be written in what one of my professors used\nto call the \"future hopeful tense\" ;-) )\nWe intend to update this document using\nexamples from Orion, plus some of the other translators for real\nmachines which have been written since this project was started.\nWe'll also add links to source\ncode for you to look at. But for now, read this (and our\nembrionic [wiki page](http://www.gtoal.com/software/StaticBinaryTranslation)) and join our\nonline chat group that discusses the subject, at\n[Yahoo Groups](http://groups.yahoo.com/group/staticrecompilers/).\n\n---\n\n## An Emulator Writer's HOWTO for Static Binary Translation\n\nThere is a lot of Computer Science literature on binary translation,\nboth of the sexy dynamic variety and the slightly duller (from the\nCS point of view) static variety. However most of what you'll find\nwhen you research the subject is rather dry and somewhat academic.\nI don't know of any accessible primers on static translation that\nsomeone from the emulation world can pick up and use in a practical\nproject.\n\nSo... the aim of this HOWTO document is to give you a very practical\nmethod that you can adapt to your own area of expertise, which should\npretty much guarantee that if you have already written or worked on a\nreasonable emulator, you will be able to write a translator which\nwill take a specific program and generate a binary from it that runs\non a different architecture, and does so faster than any emulator\nthat you're used to using.\n\nAnd that's why we're doing this: you have a favorite old video game\nthat you want to run on some system and the emulator for that system\nworks but it just isn't fast enough. Or perhaps you want to port\nan emulator which works OK on a 300MHz Pentium to a 16MHz ARM in your\nPDA. A straight port runs your favourite game at 2FPS and you don't\nthink the hardware is likely to get 25 times faster in the near\nfuture! Play your cards right and you *may* get that factor\nof 25 out of a static binary translator.\n\nThis document tries to explain things simply - perhaps too simply at\ntimes, and there are a lot of examples which differ from the previous\nexample in small details. This makes the document rather long, but\nthat's deliberate; I don't want to skip too many stages and risk\nhaving anyone lose track of the process. Apologies in advance to\nthose of you who think I'm taking it too slowly or have made this\ndocument too long.\n\n#### What are we hoping to achieve?\n\nFirst of all, let's have a quick recap of regular emulator techology.\nMost emulators work something like this:\n\n```\nfor (;;) {\n if (cycles >= eventTrigger) do_some_timed_event();\n opcode = mem[Reg_PC++];\n cycles = cycles + 1;\n switch (opcode) {\n\n case TFRregreg:\n operand = mem[Reg_PC++];\n cycles = cycles + 1;\n firstreg = operand>>4;\n secondreg = operand&15;\n *Reg[firstreg] = *Reg[secondreg];\n break;\n\n case ADDimmediate:\n operand = mem[Reg_PC++];\n cycles = cycles + 1;\n temp = Reg_A + operand + Flag_Carry;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ operand ^ (Flag_Carry<<7))>>7;\n Reg_A = temp & 0xff;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n break;\n\n case MULdirect:\n ... similar code for all the available opcodes ...\n\n }\n}\n```\n\nOK, we've all written an emulator before, and we know the code above\nis pretty inefficient, but play along with me... the actual details of\nhow an opcode is emulated aren't too important, and the enclosing loop\nin this case isn't too onerous. I could have shortened it by removing\nthe cycle count and test, but most real emulators do have something\nlike that and many have a lot more overhead, so this will do for now\nas a realistic test-bed.\n\nNow let's look at a *very* short program fragment:\n\n```\n TFR B,A\n ADDA #21\n```\n\nFirst of all we'll look at what is executed when we emulate these two\ninstructions in a traditional emulator. Let's pretend we have a symbolic\ndebugger which prints out the source of a program as it is executed; this\nis what we would see when we emulate the two lines above. We'll assume\nwe're starting from the first instruction inside the main dispatch loop.\n\n```\n if (cycles >= eventTrigger) do_some_timed_event();\n opcode = mem[Reg_PC++];\n cycles = cycles + 1;\n switch (opcode) {\n case TFRregreg:\n operand = mem[Reg_PC++];\n cycles = cycles + 1;\n firstreg = operand>>4;\n secondreg = operand&15;\n *Reg[firstreg] = *Reg[secondreg];\n break;\n }\n}\nfor (;;) {\n if (cycles >= eventTrigger) do_some_timed_event();\n opcode = mem[Reg_PC++];\n cycles = cycles + 1;\n switch (opcode) {\n\n case ADDimmediate:\n operand = mem[Reg_PC++];\n cycles = cycles + 1;\n temp = Reg_A + operand + Flag_Carry;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ operand ^ (Flag_Carry<<7))>>7;\n Reg_A = temp & 0xff;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n break;\n }\n}\n```\n\nNow, we're going to skip to the end of the book and look at the solution :-)\n \nThis is what we would *like* to be executed for the above two\ninstructions:\n\n```\n Reg_A = Reg_B;\n Reg_A = (Reg_A + 21 + Flag_Carry)&0xff;\n```\n\nDoes that look like it might be 25 times more efficient that the first\nversion? It just might be. I'll let you in on a secret: I've already\ndone this once for my favourite video game, Cinematronic's Tailgunner,\nand the translated version was just fast enough to run on the GP32\nhandheld videogame system, which is an ARM and roughly similar to the\nGameboy Advance. So the technique I'm explaining here *does*\nwork and it makes it possible to run video games at full speed on\nrelatively slow processors such as you'll find in handhelds and PDAs.\n\nOf course, we're making some pretty big assumptions in the short\nsequence above, such as we are not\ninterested in any of the flags again, we don't care if the addition causes\nan overflow, and we're not going to bother checking for our special timed\nevents at this point. What we're going to do is come up with an algorithm which\nlets us find out when those assumptions are valid, and only generate the\ncode to handle flags when we really are forced to, which in most programs\nwill not be very often. The worst case code we could hope to generate\nfor those two instructions would be this:\n\n```\n Reg_A = Reg_B;\n temp = Reg_A + 21 + Flag_Carry;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n Reg_A = temp & 0xff;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n cycles = cycles + 4; Reg_PC = Reg_PC + 4;\n if (cycles >= eventTrigger) do_some_timed_event();\n```\n\nEven this is pretty good compared to what we originally had in the\nemulator, because we no longer have to fetch the opcodes and operands,\nnor dispatch via a switch statement to decode the opcodes.\n\n#### General structure of the translator\n\nSo how do we arrange this transformation? Well, it should be pretty\nobvious that whoever wrote an emulator for the system you want to\ntranslate from has already done the heavy lifting. Basically what\nwe're going to do is write a disassembler which takes a binary and\ninstead of outputing native assembler, outputs the target code, and\nwe're going to steal most of that target code from the existing\nemulator. If we're lucky we can steal the disassembler framework\ntoo, or at the least, mangle the emulator source to turn it into a\ndisassembler.\n\nIn my examples I'm going to use C as the target code, but this method\nworks just as well if you're starting from a traditional emulator\nthat's written in the assembly language of the target machine. You\nstill will have a dispatch loop, and the equivalent of a switch jump\nto a set of labels or procedures written in the target assembly\nlanguage which decode the operands and execute instructions to\naccurately simulate the emulated machine. Our algorithm is simply\nthat the disassembler *outputs* that code for each instruction\ninstead of executing it.\n\nWe should be able to very quickly write a first naive hack at this\nwhich is still structured primarily as an emulator, but before we\ndo that, let's have a little digression:\n\nLet's go back to the days when you were a good old-fashioned emulator\nwriter. You started by working on someone else's emulator because\nyou thought it was written pretty inefficiently, and you thought you\ncould do better, right? :-) Well, you may not have done the hack below but I\nguarantee that with hindsight you'll agree you wish you had! The\nbest way to write a new emulator when you already have a working\none, even if it isn't very efficient, is to hack up a \"dual CPU\" testbed.\nBasically this is the same as a regular emulator, but it contains\ntwo completely independent CPU cores. The main dispatch loop calls\n*both* cores for every instruction, and it compares all the\nregisters after each one has emulated the instruction to see if they\ndiffer. It'll look something like this:\n\n```\nfor (;;) {\n assert(Reg_PC_1 == Reg_PC_2);\n opcode = *Reg_PC_1++; Reg_PC_2 = Reg_PC_1;\n engine1(opcode); engine2(opcode);\n assert(Reg_PC_1 == Reg_PC_2);\n assert(Reg_A_1 == Reg_A_2);\n assert(Reg_B_1 == Reg_B_2);\n assert(Flag_Carry_1 == Flag_Carry_2);\n assert(Flag_Negative_1 == Flag_Negative_2);\n assert(Flag_Zero_1 == Flag_Zero_2);\n assert(Flag_Overflow_1 == Flag_Overflow_2);\n}\n```\n\nThe astute reader will have realised that it is also wise to check\nthe RAM which has changed too, and indeed each engine does need its\nown copy of the RAM, but I'll save you a little effort and let you\nknow that in practice, unless you break some really obvious part\nof the load/save-memory code, almost all emulation errors show up\nfirst in the registers. Comparing two entire sets of memory is a\nvery expensive proposition, even in something as small as a 64K micro\nwith just 4K of RAM.\n\nOK, back on track... what we're going to do is modify one of the\nCPUs in our Dual CPU emulator so that instead of dispatching by\nopcode, it dispatches by the address of the opcode. To make this\nclear, let's look at our short example. We'll assume the code sequence\nfor the two instructions I gave is in memory at address 0xBCA7...\n\n```\nBCA7: TFR B,A\nBCA9: ADDA #21\n```\n\nOur loop (omitting the consistency checks for brevity) now becomes:\n\n```\nfor (;;) {\n opcode = mem[Reg_PC_1++];\n engine1(opcode); engine2(Reg_PC_2);\n}\n```\n\nand the 'new' emulator dispatch loop now looks like this:\n\n```\nfor (;;) {\n if (cycles >= eventTrigger) do_some_timed_event();\n\n switch (Reg_PC_2) {\n\n /* This section is automatically generated from the binary */\n\n case 0x0000:\n ... similar code for the rest of the program ...\n\n case 0xBCA7:\n cycles = cycles + 2;\n Reg_B_2 = Reg_A_2;\n Reg_PC_2 = 0xBCA9;\n break;\n\n case 0xBCA9:\n cycles = cycles + 2;\n temp = Reg_A_2 + 21 + Flag_Carry_2;\n Flag_Carry_2 = temp >> 8;\n Flag_Overflow_2 = (Reg_A_2 ^ 21 ^ (Flag_Carry_2<<7))>>7;\n Reg_A_2 = temp & 0xff;\n Flag_Negative_2 = Reg_A_2 >> 7;\n Flag_Zero_2 = (Reg_A_2 == 0 ? 1 : 0);\n Reg_PC_2 = 0xBCAB;\n break;\n\n case 0xBCAB:\n ... similar code for the rest of the program ...\n\n /* End of automatically generated section */\n }\n}\n```\n\nYou can see in the above that by switching from executing by opcode\nto executing by code address, we've already been able to make a\nfew optimisations. For instance the old emulator had to decode the\noperand byte of the TFR opcode (to determine that the operands were\nregister A and register B), and we can now see at the time we generate\nthe code above that the operand to the ADD instruction is the\nliteral value 21. We don't need to fetch that operand at emulate\ntime any more, we know what it is at translate time. Also we know\nwhat the PC will be on the next instruction so we just set it directly\ninstead of adding to it.\n\n(From now on we'll assume we're talking about the 'new' emulator and\ndrop the \"\\_2\" suffix on everything...)\n\nJust to make it absolutely clear at this point, the body of the dispatch\nloop above was generated by a program similar to a disassembler, containing\na dispatch table based on opcodes which eventually executes code something\nlike this:\n\n```\nReg_PC_translator = 0;\nfor (;;) {\n fprintf(codefile, \" case 0x%04x:\\n\", Reg_PC_translator);\n opcode = mem[Reg_PC_translator];\n Reg_PC_translator += 1;\n switch (opcode) {\n\n case TFRregreg:\n fprintf(codefile, \" cycles = cycles + 2;\\n\");\n operand = mem[Reg_PC_translator];\n firstreg = operand>>4;\n secondreg = operand&15;\n fprintf(codefile, \" Reg_%s = Reg_%s;\\n\", Regname[firstreg],\n Regname[secondreg]);\n fprintf(codefile, \" break;\\n\");\n Reg_PC_translator += 1;\n break;\n\n ... similar code for the other opcodes ...\n }\n fprintf(codefile, \"\\n\");\n}\n```\n\nSo you should be able to see now that the structure of our translator\nis pretty much falling into shape; there's only a couple of key steps\nleft. What we have above would actually work, but we still have the\noverhead of a dispatch loop. So how do we get rid of it? Well, it's\npretty easy in principle - we just remove the `break;` and\ndrop through to the next instruction:\n\n```\nfor (;;) {\n if (cycles >= eventTrigger) do_some_timed_event();\n\n switch (Reg_PC) {\n\n /* This section is automatically generated from the binary */\n\n case 0x0000:\n ... similar code for the rest of the program ...\n\n case 0xBCA7:\n cycles = cycles + 2;\n Reg_A = Reg_B;\n\n case 0xBCA9:\n cycles = cycles + 2;\n temp = Reg_A + 21 + Flag_Carry;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;;\n Reg_A = temp & 0xff;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n Reg_PC = 0xBCAE;\n break;\n\n ... similar code for the rest of the program ...\n /* End of automatically generated section */\n }\n}\n```\n\nThis is now greatly improved, because we no longer have the overhead\nof returning to the dispatch loop for the majority of instructions.\nThe only time we'll have to do that is if we execute a branch. We've\nalso been able to drop the setting of the PC and we'll do it only when\nwe need to use the PC, such as when we return to the dispatch loop,\nor when the code itself needs to use the PC (as with a JSR for example).\n\nSo let's extend our test program with \"BVS 0x2204\" (Branch if Overflow\nto the code at address 0x2204):\n\n```\n0000: ...\n...\n2204: L2204: ...\n...\nBCA7: TFR B,A\nBCA9: ADDA #21\nBCAB: BVS 0x2204\nBCAF: ...\n...\n```\n\nThe code for the BVS is pretty simple: `if (Flag_Overflow) break;`,\ni.e. stop executing in-line code, and let the dispatch loop cause a jump\nto the new address:\n\n```\nfor (;;) {\n if (cycles >= eventTrigger) do_some_timed_event();\n\n switch (Reg_PC) {\n\n /* This section is automatically generated from the binary */\n\n case 0x0000:\n ... similar code for the rest of the program ...\n\n case 0xBCA7:\n cycles = cycles + 2;\n Reg_A = Reg_B;\n\n case 0xBCA9:\n cycles = cycles + 2;\n temp = Reg_A + 21 + Flag_Carry;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n Reg_A = temp & 0xff;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n\n case 0xBCAB:\n cycles = cycles + 3;\n if (Flag_Overflow) {\n cycles = cycles + 1;\n Reg_PC = 0x2204;\n break;\n }\n\n case 0xBCAE:\n ... similar code for the rest of the program ...\n\n /* End of automatically generated section */\n }\n}\n```\n\nI hope these small incremental changes aren't too tedious, but I didn't\nwant to skip too many stages in case anyone loses the place. Here's\nanother relatively trivial change but it's an important one:\n\n```\nfor (;;) {\n if (cycles >= eventTrigger) do_some_timed_event();\n\n goto *dispatch[Reg_PC];\n\n /* This section is automatically generated from the binary */\n\n L_0000:\n ... similar code for the rest of the program ...\n\n L_BCA7:\n cycles = cycles + 2;\n Reg_A = Reg_B;\n\n L_BCA9:\n cycles = cycles + 2;\n temp = Reg_A + 21 + Flag_Carry;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n Reg_A = temp & 0xff;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n\n L_BCAB:\n cycles = cycles + 3;\n if (Flag_Overflow) {\n cycles = cycles + 1;\n Reg_PC = 0x2204;\n continue;\n }\n\n L_BCAE:\n ... similar code for the rest of the program ...\n\n /* End of automatically generated section */\n}\n```\n\nI have used GCC's non-standard extension here which allows you to\njump through an array of labels. This is how most switch jumps\nare executed anyway. (At least we hope so; a binary search table\nwould be most inefficient in a program like this). So, the case\nlabels have been replaced with simple labels, and the break out of\nthe case has been replaced with a `continue`, which\ntakes it back to the start of the enclosing dispatch loop.\nOtherwise the code is just the same.\n\nNow, let's look more closely at the BVS instruction. In this case\nwe do know at translate time where the destination is, so we could\nin fact do away with the return to the dispatch loop, and dispatch\ndirectly ourselves at the point of the BVS:\n\n```\n L_BCAB:\n cycles = cycles + 3;\n if (Flag_Overflow) {\n cycles = cycles + 1;\n Reg_PC = 0x2204;\n continue;\n }\n\n L_BCAE:\n```\n\nNow becomes ...\n\n```\n L_BCAB:\n cycles = cycles + 3;\n if (Flag_Overflow) {\n cycles = cycles + 1;\n goto L_2204;\n }\n\n L_BCAE:\n```\n\nThis is pretty good but there's one difference between this and the\noriginal code. The test for scheduled events based on the cycle count\nwill not be executed. Let's modify the code we generate a little to\nput it back in, inside the BVS code...\n\n```\n L_BCAB:\n cycles = cycles + 3;\n if (Flag_Overflow) {\n cycles = cycles + 1;\n if (cycles >= eventTrigger) do_some_timed_event();\n goto L_2204;\n }\n\n L_BCAE:\n```\n\nYou may have noticed that I'd already dropped that test in the two-opcode\nsequence when we dropped through the first instruction. The reason for\nthis is that scheduled events (eg simulated interrupts from a disk drive)\nseldom need to be cycle-perfect, so as long as we do the test relatively\nfrequently, it'll be often enough. (If this isn't true for your emulator\nthen don't do this optimisation, but for now I'll assume it's OK).\n\nWhat I'm going to suggest next is a criterion for when we need to\ninsert one of these tests: I believe that they only need to be done\nwhen you execute a branch backwards. It is almost impossible for code\nto execute in a straight line forwards for any length of time. Even\nif it does execute straight-line code, it won't take long - programs\njust are not that big, and straight-line code is *not* going\nto be megabytes long. At some point - almost certainly within a K\nat most - it will branch backwards (or somewhere non-fixed, such as in\na return from subroutine). I think those points are sufficiently frequent\nto be good places to insert the tests that would normally be in the\ndispatch loop.\nWe will soon be getting to the point where you will see why it's\nworthwhile to eliminate as many of these tests as possible...\n\nAside: the most likely event that the\nmajority of video-game emulators needs is a vsync interrupt, to allow\nflicker-free updating of the screen by the program. Let's say this\nis in fact the most frequent or time-critical interrupt that you\nwill have. It's frequency is 50Hz. Your emulated CPU is 1MHz,\nso... you'll be looking for a clock interrupt at least once every\n1,000,000/50 = 20,000 cycles. So your accuracy will not be diminished\nby more than 5% if you force out one of the event tests every 1,000\ncycles, right? Not a problem, because you're keeping a cycle count\nin the translator anyway, and all you have to do is simply add it\nup while generating code, and if it ever gets to a multiple of 1,000\nwithout you planting an event test due to something like a BVS,\nthen force one out into the code unconditionally.\n\nIncidentally, this same call can be used to adjust the real-time\nspeed of your emulation to match the real CPU. If you've followed\nthe suggestion above, you will have at least 1000 calls per emulated\nsecond, so we're dealing with quite a fine-grained timer here: all\nyou need to do is compare the cycles to real time, and wait in a\nspin-loop until real time has caught up with emulated time. (I'm\nassuming your emulator is too fast; if it's too slow, you have\nother problems!). With a 1000Hz test, any delay loops are not going\nto be noticeable, and your video game will play smoothly. (With\ntoo few tests, the response can get 'choppy').\nCycle-perfect accuracy is seldom required for the majority of old arcade games.\nThis is a *much* cheaper solution to real time accuracy than the\ntraditional one which is to handle timing on each and every\ninstruction. The danger there is that the overhead of the test\nis enough to slow you down. This isn't a problem on a fast processor,\nbut if you had a fast processor you wouldn't need to create a static\ntranslation in the first place!\n\nOK, that's the end of the simple formula to take an emulator and\nconvert it almost mechanically into a static binary translator. If we\nwant to generate smarter code than this, we now have to look at\nsomething a little more difficult. Let's look back at what we have so far:\n\n```\n L_BCA7:\n cycles = cycles + 2;\n Reg_A = Reg_B;\n\n L_BCA9:\n cycles = cycles + 2;\n temp = Reg_A + 21 + Flag_Carry;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n Reg_A = temp & 0xff;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n\n L_BCAB:\n cycles = cycles + 3;\n if (Flag_Overflow) {\n cycles = cycles + 1;\n if (cycles >= eventTrigger) do_some_timed_event();\n goto L_2204;\n }\n\n L_BCAE:\n```\n\nIf we *know* that this code above is only executed in a straight\nline, and none of the intermediate instructions are ever jumped to\ndirectly, we can rewrite the above as follows:\n\n```\n L_BCA7:\n Reg_A = Reg_B;\n temp = Reg_A + 21 + Flag_Carry;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n Reg_A = temp & 0xff;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n if (Flag_Overflow) {\n cycles = cycles + 8;\n if (cycles >= eventTrigger) do_some_timed_event();\n goto L_2204;\n }\n```\n\nNote the only time we write to cycles is when we branch elsewhere,\nbecause the cycle count for the drop-through code is being remembered\nby the translator and will be output only when it is needed. (This is\npretty much the same as how it keeps track of the PC ... and indeed\nthe PC isn't even written to on a branch because it is known implicitly\nat the destination of a fixed jump as well. We'd write to it on a\nreturn from subroutine or an indirect jump, but only then).\n\nI hear you ask *Well, that looks interesting, but how do you eliminate\nthose labels, and is the benefit really worth it? It looks like\nall you save are a few additions to the cycle count...* \nGood question, and one I'll only partially answer right now. Is the\nbenefit really worth it? No, not as given above. Our example isn't\ncomplex enough to show the big win yet. Sorry to make this even\nlonger, but all will soon become clear. Let's add a few more instructions\nto our program...\n\n```\n0000: ...\n...\n2204: L2204: ...\n...\nBCA3: LDB 0x0100\nBCA6: ASL B\nBCA7: TFR B,A\nBCA9: ADDA #21\nBCAB: ADDA B\nBCAC: BVS 0x2204\nBCAF: ...\n...\n```\n\nwhich translates to\n\n```\n L_BCA3:\n Reg_B = mem[0x0100];\n temp = Reg_B << 1;\n Reg_B = temp&0xff;\n Flag_Overflow = Flag_Carry;\n Flag_Carry = temp>>8;\n Flag_Negative = Reg_B >> 7;\n Flag_Zero = (Reg_B == 0 ? 1 : 0);\n Reg_A = Reg_B;\n temp = Reg_A + 21 + Flag_Carry;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n Reg_A = temp & 0xff;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n Reg_A = Reg_B;\n temp = Reg_A + Reg_B + Flag_Carry;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ Reg_B ^ (Flag_Carry<<7))>>7;\n Reg_A = temp & 0xff;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n if (Flag_Overflow) {\n cycles = cycles + 8;\n if (cycles >= eventTrigger) do_some_timed_event();\n goto L_2204;\n }\n```\n\nBlech. It's a lot of code for 6 original instructions. Most of it\nis coming from the setting of flags which are never used. What would\nhappen if we don't emit the statements which set flags if those flags\nare never used at all before they are written to again??? I'll tell you, this\nis what would happen:\n\n```\n L_BCA3:\n Reg_B = mem[0x0100];\n temp = Reg_B << 1;\n Reg_B = temp&0xff;\n Flag_Carry = temp >> 8;\n Reg_A = Reg_B;\n temp = Reg_A + 21 + Flag_Carry;\n Flag_Carry = temp >> 8;\n Reg_A = temp & 0xff;\n Reg_A = Reg_B;\n temp = Reg_A + Reg_B + Flag_Carry;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ Reg_B ^ (Flag_Carry<<7))>>7;\n Reg_A = temp & 0xff;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n if (Flag_Overflow) {\n cycles = cycles + 8;\n if (cycles >= eventTrigger) do_some_timed_event();\n goto L_2204;\n }\n```\n\nAs you can see, most of the flags disappear except for the few we\nactually need. If we have a longer sequence (which we'll now assume\nis the case) we can drop even more of the flag calculations, except\nwhere we need to use them. Without a particularly complex dataflow\nanalysis of the whole program, we should probably assume that we need\nto write back all the flags at any point where we jump elsewhere, or\nany time there is a necessary label which allows code elsewhere to\njump into our sequence:\n\n```\n L_BCA3:\n Reg_B = mem[0x0100];\n temp = Reg_B << 1;\n Reg_B = temp&0xff;\n Flag_Carry = temp >> 8;\n Reg_A = Reg_B;\n temp = Reg_A + 21 + Flag_Carry;\n Flag_Carry = temp >> 8;\n Reg_A = temp & 0xff;\n temp = Reg_A + Reg_B + Flag_Carry;\n Reg_A = temp & 0xff;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ Reg_B ^ (Flag_Carry<<7))>>7;\n if (Flag_Overflow) {\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n cycles = cycles + 8;\n if (cycles >= eventTrigger) do_some_timed_event();\n goto L_2204;\n }\n```\n\nYou've probably worked out by now that what we are trying to do is\nwork with what the compiler writers call 'basic blocks', i.e. the\nlongest sequence of straight-line code you can find. If we apply\nsome relatively simple compiler techniques to the improved sequence\nabove, it gets even better:\n\n```\n L_BCA3:\n temp = (mem[0x0100] << 1)&0xff;\n Reg_B = temp&0xff;\n temp = Reg_B + 21 + (temp>>8);\n temp = (temp&0xff) + Reg_B + (temp>>8);\n Reg_A = temp & 0xff;\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ Reg_B ^ (Flag_Carry<<7))>>7;\n if (Flag_Overflow) {\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n cycles = cycles + 8;\n if (cycles >= eventTrigger) do_some_timed_event();\n goto L_2204;\n }\n```\n\nThis is actually pretty damned good code now, although we did have some\nquite complex compiler-like optimisations to make and I haven't explained\nhow to do those, nor am I going to, but I will show you a neat hack to\ndo the redundant flag removal. But having shown, I hope, *why* the\nremoval of unused labels is worthwhile, I'll now give you the promised\nsecond half of the answer to the question asked some time back:\n*how do you eliminate those labels?*\n\nWell, we need to know the flow control of the program and note the\ndestinations of jumps. Those jump destinations are the only opcodes\nwhich need to be labelled. To some extent you might be able to work\nthose out statically, by having a slightly smarter disassembler framework\nwhich does a tree-walk of the source, starting at the entry point.\nI.e. whenever it hits a branch or subroutine call, it also goes off to the\ndestination and looks at the code there too. The problem with this is\nthat very few architectures are designed so that you always can determine\nthe jump destination just by looking at the code. Most architectures\nallow indirect jumps through store or registers, or let you tweak a\nreturn address on the stack so that your return from subroutine goes\nsomewhere other than where your subroutine was called from. This is\na major pain in the ass and the only practical solution is to profile\nthe execution of the code and mark the jump destinations at run time.\n\nFortunately we have just the piece of code to do this for us - the\noriginal emulator (or even our own one at this point, before we start\nmaking 'dangerous' assumptions such as removing the labels in front\nof any instructions) can be used to execute the code, and it can be\nmodified to note in an array which is the same size as memory whether\nany code address is ever jumped to.\n\nAs you can imagine, any one run through the program is not going to\nexercise every path in the code, so your profiling has to load this\narray at startup to get the results of previous runs; it then adds\nany new info it finds in this run, and writes the cumulative results\nback out to a file. I found that about a week of playtesting fully\nexercised a game. It's pretty important that you play through all\nlevels and try all problems, etc. You should execute all areas of\ncode at least once, including things like getting on the high score\ntable. Once you've done this you'll have a list of jump\ndestinations. Use this list to seed a 'smart disassembler'\nas suggested above. The two techniques together should find all\nthe executable code areas in your binary. The rest of the ROM\nyou're translating is probably\ndata. You might also run it through a 'traditional' disassembler\nand see if it finds anything that looks like code in some area\nthat you missed. (It helps in this case if your list of jump\ndestinations/tree-walking start points is held in ascii/hex. Makes\nit easier to add to by hand!)\n\nNote: if you miss any jump targets, your translation will find them\nbecause when you do a `goto *dispatch[Reg_PC];`, all the\nunlabelled statements will have an entry which takes you to a diagnostic\nroutine, and that routine will print out the value of Reg\\_PC and\ntell you to add it to the jump dest table, and rebuild your emulator.\nIf you want to get *really* fancy, you can do this quietly\nand pass control over to the other emulator core (the 'traditional'\nemulator, which should still be in your program even if it isn't\nbeing called any more) and it can interpret instructions one by one\nuntil it gets to an address which is the entry point to one of\nour statically translated sequences. That'll let you play the\ngame through, and you can automatically rebuild every time you run it,\nto incrementally improve the code.\n\nOnce you have that list of jump destinations, modify your translator\nlike this (remember our example from early on?):\n\n```\nReg_PC = 0;\nfor (;;) {\n if (jumpdest[Reg_PC]) fprintf(codefile, \"L_%04x:\\n\", Reg_PC);\n opcode = mem[Reg_PC];\n Reg_PC += 1;\n switch (opcode) {\n...\n case TFRregreg:\n cycles = cycles + 2;\n operand = mem[Reg_PC];\n firstreg = operand>>4;\n secondreg = operand&15;\n fprintf(codefile, \" Reg_%s = Reg_%s;\\n\", Regname[firstreg],\n Regname[secondreg]);\n Reg_PC += 1;\n break;\n...\n }\n fprintf(codefile, \"\\n\");\n}\n```\n\nWe're almost finished now! We just have to remove those redundant\nflag expressions and we're done. That turns out to be relatively\neasy. Here's a complete demo program; it's not actually using our\nexample code above as I wrote it some time before writing this\ndocument, but it's very obvious what's going on:\n\n```\n// A test program to eliminate redundant code; does *not* do common\n// subexpression elimination or constant folding, although in a real\n// program the CSE and dead code stuff would best be done by the same program\n\n// We might assume (perhaps wrongly) that we are translating hand-written\n// assembly code and that no obvious peephole optimisation is possible.\n\n#include \n#include \n#include \n\n#ifndef FALSE\n#define FALSE (0!=0)\n#define TRUE (0==0)\n#endif\n\n#define MAX 1024\nlong defs[MAX], uses[MAX];\nchar *codes[MAX];\nint nextfree = 0;\n\n/* Metacodes */\n#define Always 1\n#define Flush 2\n\n/* Real regs */\n#define PC 4\n#define A 8\n#define B 16\n#define CC 32\n\n/* Internal variables */\n#define TMP 64\n\n/* See http://groups.yahoo.com/group/compilers101/ for a more general\n technique to eliminate redundant code. Here we are limited to\n 30 variables */\n\nvoid flush(long regs)\n{\n int i;\n long common_regs;\n\n for (i = nextfree-1; i >= 0; --i) {\n if (common_regs = (regs & defs[i])) {\n /* if bits in 'defs' then this needs to be dumped. */\n fprintf(stdout, \"// %02d lookfor: %02x Item %d - def %02x\\n\",\n nextfree, regs, i, defs[i]);\n defs[i] |= Always; /* flag this line for printing */\n regs &= ~common_regs; /* don't need to look for these ones any more */\n }\n if (defs[i]&Always) regs |= uses[i]; /* Any unconditionals + parents */\n }\n\n for (i = 0; i < nextfree; i++) {\n fprintf(stdout, \"/* %03d [def:%02x] [use:%02x] */ \",\n i, defs[i], uses[i]);\n fprintf(stdout, \"%s %s\", (defs[i]&Always ? \" \" : \"// \"), codes[i]);\n }\n\n nextfree = 0;\n}\n\n#define dump(def, use, code) (defs[nextfree] = def, uses[nextfree] = use, \\\n codes[nextfree] = code, nextfree += 1)\n\nint main(int argc, char **argv) {\nint i;\n // Test program for a non-existent machine. Several details omitted.\n //\n // $ORG A000\n // LDB #42\n // INP A,B\n // INC B\n // INC B\n // ASR A,B\n // LDB #1\n // JMP 0xFC08 ; end of basic block ...\n\n dump(Always, Always, \" // LDB #42\\n\");\n dump(PC, 0, \"PC = 0xA000;\\n\");\n dump(B, 0, \"B = 42;\\n\");\n dump(Always, Always, \" // INP A,B\\n\");\n dump(PC, 0, \"PC = 0xA002;\\n\");\n dump(A | Always, B | Always, \"A = fninput(B);\\n\"); /* has side effects */\n dump(Always, Always, \" // INC B\\n\");\n dump(PC, 0, \"PC = 0xA003;\\n\");\n dump(TMP,B, \"tmp = B+1;\\n\");\n dump(CC, TMP, \"CC = (tmp>>8)&1;\\n\");\n dump(B, TMP, \"B = tmp&255;\\n\");\n dump(Always, Always, \" // INC B\\n\");\n dump(PC, 0, \"PC = 0xA004;\\n\");\n dump(TMP,B, \"tmp = B+1;\\n\");\n dump(CC, TMP, \"CC = (tmp>>8)&1;\\n\");\n dump(B, TMP, \"B = tmp&255;\\n\");\n dump(Always, Always, \" // ASR A,B\\n\");\n dump(PC, 0, \"PC = 0xA005;\\n\");\n dump(A, B, \"A = B>>1;\\n\");\n dump(Always, Always, \" // LDB #1\\n\");\n dump(PC, 0, \"PC = 0xA006;\\n\");\n dump(B, 0, \"B = 1;\\n\");\n dump(Always, Always, \" // JMP 0xFC08\\n\");\n dump(PC, 0, \"PC = 0xA008;\\n\");\n dump(Always, Always, \"\\n\");\n dump(PC | Always, Always, \"goto *lab[PC = 0xFC08];\\n\");\n flush(A | B | CC | PC); /* List of registers to force out (excluding TMP) */\n exit(0);\n return(0);\n}\n```\n\nWhat we're doing here is taking the printf that we're currently\nusing, and replacing it with a 'dumpf' which has two extra parameters;\none is a list of the registers or internal variables that the\nstatement *uses* as inputs, and\nthe other is a list of the registers or internal variables that the\nstatement writes to or *defines*. [Actually in that example we\nuse a simple `dump` macro, but you know how to expand that\nto a stdargs procedure that'll take printf-style extra parameters, right?]\nThe very simple def/use chain ensures that for\nany use of a variable, the immediately previous definition of it is\noutput - and so on, recursively. This particular implementation\nis a really really simple one and gets its simplicity by using\nbit flags in long ints to simplify the tables it needs to keep. If your\ntranslator needs more than 30 registers or internal variables, a more\ngeneral technique should be used. (Hint: look up Directed Acyclic\nGraphs)\n\nThe redundant expression elimination code above can also be twisted so\nthat you can generate code conditionally, such as when you want to\nreconstitute the condition code registers from the split-apart individual\nflags. If you're generating assembler rather than C and have a processor\nwhere the flag bits are compatible with your emulated system, then you\nmight not bother with separate flags and just use the hardware CC, but\nusually it's easier to calculate the flags explicitly. You can either keep the CC up\nto date, and examine the relevant bits when you need them, ... or you\ncan do it this way, and just make minimal changes only to the flags that\nyou need, and coalesce those flags into a combined CC only on the rare\noccassions when it is really needed, such as on the 6809's \"`PSHS CC`\"\ninstruction which pushes the whole CC on the stack.\nHowever the easy way to manage the CC so that you not only amalgamate the\nflags when needed, but also generate code to update the individual flag\nbits beforehand, is to use the redundant code optimiser from above.\nAny time you translate an opcode which changes one of the CC flags,\noutput this at the end of the sequence:\n\n```\ndump(CC, OV|MI|CA|ZE, \"Reg_CC = Flag_Overflow << 8 | Flag_Negative << 7 | \"\n \"Flag_Carry << 6 | Flag_Zero << 5;\");\n```\n\nIf anything uses the combined CC, it'll include that in it's *use*\nparameter, and the previous dump instruction will be generated, otherwise\nit will be dropped.\n\n```\ndump(Always | SP, SP | CC, \"mem[Reg_SP++] = Reg_CC;\");\n```\n\nSo that's about it. I didn't explain the 'compiler-like optimisations'\nbecause to do so would require a document as long as this one, and it's\ntime to cut you a break and stop here. Write the generated code carefully\nand you probably won't need that level of optimisation anyway - or if\nyou have a good compiler it'll do it for you. A second reason for\nremoving unused labels from each translated instruction is that it\nalso allows the compiler to optimise more aggressively too.\nThis is also a reason why we should eliminate most of the calls to the\ntimed event test procedure - most compilers will not be able to work out the\nside-effects of that procedure (such as writing through a pointer), and the call will automatically cause the\ncurrent basic block to end. This will severely limit the register optimisations\nthat the compiler can do for you.\nYou may find that within basic blocks, your compiler will keep each emulated\nregister in a real register and only write it back to store at the\nend of the basic block. In exceptional cases it may slave to real\nregisters throughout the whole emulator procedure or indeed the\nentire program. It doesn't hurt to declare your emulated registers\nwith the `register` keyword, such as\n\n```\n register int Reg_A, Reg_B;\n```\n\nBut be careful not to do this for variables that aren't heavily\nused. For instance we seldom mention Reg\\_PC any more and it would\nbe a bad choice to force into a register if it caused a more heavily\nreferenced variable to be spilled back to store.\n\nI believe that if you follow the procedure outlined above and are\nalready familiar with emulators, you should not find it hard to\nwrite a translator, and take one program and translate it. This\nisn't high Computer Science, it's just hacking that any competant\nprogrammer can do. So pick your favourite video game and emulator\nand go make a translation!\n\nIf you're interested in emulation for other reasons (eg you\nneed to convert some stiffware COBOL program that you've lost\nsource to, from IBM360 binary to ARM code, the techniques are\nthe very same. In fact you may find it easier because if you're\nworking from compiled code rather than hand-written assembler,\nyou're unlikely to hit any of the nasty 'gotcha's that we sometimes\ndo, such as self-modifying code... (which you can handle either\nby retaining a traditional emulator as well as the translation,\nor you can manually analyse the code and special-case it if the\ngenerated code is consistently the same)\n\nGood luck!\n\nGraham\n\n---\n\nPostscript: Read this section only *after* you've actually\ngot a translator running. If it's your first time round you can\nskip this section as it is concerned with optimisations that give\nrelatively minor incremental improvement but take some effort to\nset up. Do not try any of this until you have got your translated\nprogram working correctly.\n\n#### Constant expression folding\n\nThis is often done for you by the compiler but if you add a mechanism\nto do it yourself, you're halfway towards adding some other optimisations\nwhich need the same structure in place.\n\nA good example of constant folding can be seen in the ARM, where\nliteral constants in opcodes are only eight bits, so larger constants\nsuch as 0x12345678 are sometimes loaded in multiple operations, such as\n\n```\nMOV R0, #0x12000000\nORR R0, #0x00340000\nORR R0, #0x00005600\nORR R0, #0x00000078\n```\n\nAn alternative of course is\nto do an LDR directly from an area of store pre-initialised with the constant\nby the linker, but this sort of thing does come up. When it does we\ndon't want to emulate it the hard way, but would prefer a simple\n`R0 = 0x12345678;`\n\nTo do this, we have to remember any constant values we happen to\nsee being written to a register, and if we can fold constant operations\nat translate time then we should do so.\n\nThe ideal way to do this would be to build up full expression trees\nand handle it exactly the way an optimising compiler would. But that\nis an incredible amount of work, and we can get quite a lot of the\nbenefit from some relatively crude hacks. Firstly, we just need\na procedure to `remember(reg, value);` and then a lookup\nprocedure to get the value of `reg` if known. If it is\nknown we use the constant instead of reg, if we're doing an operation\nwith another constant, we fold them into one; if the value of reg\nis not known, we just plant code like normal.\n\nTime for some more code examples. We'll ignore the complexity of\ndecoding the LD and OR instructions to decide whether the parameters\nare immediate literal constants, direct from store locations, or\nother registers. We'll keep this short by assuming the operands\n`reg`, `reg2`, `addr`,\n`const` and `shift`\nhave already been decoded by the translator framework.\n\nThe `remember()` procedure is implementing what is\ncalled 'constant propogation'. The code below which\ncalculates `val | (const<> 8;\n Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n Reg_A = temp & 0xff;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n```\n\nSo, not to repeat all the details again, the whole set of statements\nabove should now collapse down to the rather nice:\n\n```\nReg_A = (Reg_B + 21) & 0xff;\n```\n\n(This *only* worked because the whole sequence was a basic block.\nIf the second or third instruction could be jumped to, the optimisations\nwould break the code...)\n\nBut what has this to do with the trick of remembering the values of\nregisters from running under the emulator? Well, it's because programmers\nfor small micros tend to shave every byte. They might have a label\nin front of the \"`ADDA #21`\" and that label is branched to from places\nall over the code, where the programmer already knows that the carry\nis clear. So although remembering the value of registers in straight\nline code is relatively easy, optimising over the whole of the program\nis usually rather difficult! The normal way to do this would be with\nglobal dataflow analysis. That's hard work. People write theses about\nit. What we've done here is a hack, and to be honest it could in\nprinciple sometimes give the wrong result, but it's a question of low\nprobabilities, and the longer you run the code to gather stats, the\nless likely this approximation is going to differ from reality. And\nif it does mess up once in a blue moon, it's just a video game, right?\n\nSo not only have we avoided doing global dataflow analysis, we also have\nnot built up an Abstract Syntax Tree\nnor have we written a general-purpose optimiser using tree rewriting\nrules. If you want to do that stuff, by all means do so, but you're\nlooking at the final 2 or 3% of improvement that requires 97% of effort!\n\nThere is one more optimisation I am going to mention, and I haven't done\nthis myself yet so I'm not 100% sure of the details but I think it will\nturn out to be relatively easy. In fact I cheated in the earlier\ndescription by assuming that we could do this, though by the time you\nget here you've probably tried implementing everything yourself and\nrealised that this particular tweak wasn't handled yet. We had something\nlike this:\n\n```\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ Reg_B ^ (Flag_Carry<<7))>>7;\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n if (Flag_Overflow) {\n goto L_2204;\n }\n```\n\nwhich in the next example became:\n\n```\n Flag_Carry = temp >> 8;\n Flag_Overflow = (Reg_A ^ Reg_B ^ (Flag_Carry<<7))>>7;\n if (Flag_Overflow) {\n Flag_Negative = Reg_A >> 7;\n Flag_Zero = (Reg_A == 0 ? 1 : 0);\n goto L_2204;\n }\n```\n\nThis was because `Flag_Negative` and `Flag_Zero` were not needed in the\ndrop-through code, and by moving them into the if/then clause (where\nthey *are* needed) the drop-through case will execute faster.\nI believe this optimisation can be done by slightly modifying the\n`flush()` to mark, but not remove, statements which have\nalready been conditionally output. I'll work on this some day but\nyou're all welcome to get to it first!\n\nThat really is it for me this time.\n\nGraham Toal\n\n---\n\ngtoal at gtoal dot com\n","body_html":"

Readers in a hurry might prefer Michael Steil's very readable Abstract of\nthis page.\nSince this document was first written a couple of years ago, members of\nthe SBT mailing list led by Neil Bradley have been working on a project\nto write a multi-target SBT called "Orion". Neil's code uses the\noutline below as its starting point, and goes further by implementing\nthe compiler-like optimizations which are merely alluded to in passing\nin this document. The Orion project will be written up separately;\nwe're considering submitting a paper on it to next year's\nWorking Conference on Reverse Engineering in 2007 (we were too slow\noff the mark for the 2006 submission deadline, plus too much of\nit would have had to be written in what one of my professors used\nto call the "future hopeful tense" ;-) )\nWe intend to update this document using\nexamples from Orion, plus some of the other translators for real\nmachines which have been written since this project was started.\nWe'll also add links to source\ncode for you to look at. But for now, read this (and our\nembrionic wiki page) and join our\nonline chat group that discusses the subject, at\nYahoo Groups.

\n
\n

An Emulator Writer's HOWTO for Static Binary Translation

\n

There is a lot of Computer Science literature on binary translation,\nboth of the sexy dynamic variety and the slightly duller (from the\nCS point of view) static variety. However most of what you'll find\nwhen you research the subject is rather dry and somewhat academic.\nI don't know of any accessible primers on static translation that\nsomeone from the emulation world can pick up and use in a practical\nproject.

\n

So... the aim of this HOWTO document is to give you a very practical\nmethod that you can adapt to your own area of expertise, which should\npretty much guarantee that if you have already written or worked on a\nreasonable emulator, you will be able to write a translator which\nwill take a specific program and generate a binary from it that runs\non a different architecture, and does so faster than any emulator\nthat you're used to using.

\n

And that's why we're doing this: you have a favorite old video game\nthat you want to run on some system and the emulator for that system\nworks but it just isn't fast enough. Or perhaps you want to port\nan emulator which works OK on a 300MHz Pentium to a 16MHz ARM in your\nPDA. A straight port runs your favourite game at 2FPS and you don't\nthink the hardware is likely to get 25 times faster in the near\nfuture! Play your cards right and you may get that factor\nof 25 out of a static binary translator.

\n

This document tries to explain things simply - perhaps too simply at\ntimes, and there are a lot of examples which differ from the previous\nexample in small details. This makes the document rather long, but\nthat's deliberate; I don't want to skip too many stages and risk\nhaving anyone lose track of the process. Apologies in advance to\nthose of you who think I'm taking it too slowly or have made this\ndocument too long.

\n

What are we hoping to achieve?

\n

First of all, let's have a quick recap of regular emulator techology.\nMost emulators work something like this:

\n
for (;;) {\n  if (cycles >= eventTrigger) do_some_timed_event();\n  opcode = mem[Reg_PC++];\n  cycles = cycles + 1;\n  switch (opcode) {\n\n  case TFRregreg:\n    operand = mem[Reg_PC++];\n    cycles = cycles + 1;\n    firstreg = operand>>4;\n    secondreg = operand&15;\n    *Reg[firstreg] = *Reg[secondreg];\n    break;\n\n  case ADDimmediate:\n    operand = mem[Reg_PC++];\n    cycles = cycles + 1;\n    temp = Reg_A + operand + Flag_Carry;\n    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ operand ^ (Flag_Carry<<7))>>7;\n    Reg_A = temp & 0xff;\n    Flag_Negative = Reg_A >> 7;\n    Flag_Zero = (Reg_A == 0 ? 1 : 0);\n    break;\n\n  case MULdirect:\n    ... similar code for all the available opcodes ...\n\n  }\n}
\n

OK, we've all written an emulator before, and we know the code above\nis pretty inefficient, but play along with me... the actual details of\nhow an opcode is emulated aren't too important, and the enclosing loop\nin this case isn't too onerous. I could have shortened it by removing\nthe cycle count and test, but most real emulators do have something\nlike that and many have a lot more overhead, so this will do for now\nas a realistic test-bed.

\n

Now let's look at a very short program fragment:

\n
        TFR  B,A\n        ADDA #21
\n

First of all we'll look at what is executed when we emulate these two\ninstructions in a traditional emulator. Let's pretend we have a symbolic\ndebugger which prints out the source of a program as it is executed; this\nis what we would see when we emulate the two lines above. We'll assume\nwe're starting from the first instruction inside the main dispatch loop.

\n
  if (cycles >= eventTrigger) do_some_timed_event();\n  opcode = mem[Reg_PC++];\n  cycles = cycles + 1;\n  switch (opcode) {\n  case TFRregreg:\n    operand = mem[Reg_PC++];\n    cycles = cycles + 1;\n    firstreg = operand>>4;\n    secondreg = operand&15;\n    *Reg[firstreg] = *Reg[secondreg];\n    break;\n  }\n}\nfor (;;) {\n  if (cycles >= eventTrigger) do_some_timed_event();\n  opcode = mem[Reg_PC++];\n  cycles = cycles + 1;\n  switch (opcode) {\n\n  case ADDimmediate:\n    operand = mem[Reg_PC++];\n    cycles = cycles + 1;\n    temp = Reg_A + operand + Flag_Carry;\n    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ operand ^ (Flag_Carry<<7))>>7;\n    Reg_A = temp & 0xff;\n    Flag_Negative = Reg_A >> 7;\n    Flag_Zero = (Reg_A == 0 ? 1 : 0);\n    break;\n  }\n}
\n

Now, we're going to skip to the end of the book and look at the solution :-)

\n

This is what we would like to be executed for the above two\ninstructions:

\n
    Reg_A = Reg_B;\n    Reg_A = (Reg_A + 21 + Flag_Carry)&0xff;
\n

Does that look like it might be 25 times more efficient that the first\nversion? It just might be. I'll let you in on a secret: I've already\ndone this once for my favourite video game, Cinematronic's Tailgunner,\nand the translated version was just fast enough to run on the GP32\nhandheld videogame system, which is an ARM and roughly similar to the\nGameboy Advance. So the technique I'm explaining here does\nwork and it makes it possible to run video games at full speed on\nrelatively slow processors such as you'll find in handhelds and PDAs.

\n

Of course, we're making some pretty big assumptions in the short\nsequence above, such as we are not\ninterested in any of the flags again, we don't care if the addition causes\nan overflow, and we're not going to bother checking for our special timed\nevents at this point. What we're going to do is come up with an algorithm which\nlets us find out when those assumptions are valid, and only generate the\ncode to handle flags when we really are forced to, which in most programs\nwill not be very often. The worst case code we could hope to generate\nfor those two instructions would be this:

\n
  Reg_A = Reg_B;\n  temp = Reg_A + 21 + Flag_Carry;\n  Flag_Carry = temp >> 8;\n  Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n  Reg_A = temp & 0xff;\n  Flag_Negative = Reg_A >> 7;\n  Flag_Zero = (Reg_A == 0 ? 1 : 0);\n  cycles = cycles + 4; Reg_PC = Reg_PC + 4;\n  if (cycles >= eventTrigger) do_some_timed_event();
\n

Even this is pretty good compared to what we originally had in the\nemulator, because we no longer have to fetch the opcodes and operands,\nnor dispatch via a switch statement to decode the opcodes.

\n

General structure of the translator

\n

So how do we arrange this transformation? Well, it should be pretty\nobvious that whoever wrote an emulator for the system you want to\ntranslate from has already done the heavy lifting. Basically what\nwe're going to do is write a disassembler which takes a binary and\ninstead of outputing native assembler, outputs the target code, and\nwe're going to steal most of that target code from the existing\nemulator. If we're lucky we can steal the disassembler framework\ntoo, or at the least, mangle the emulator source to turn it into a\ndisassembler.

\n

In my examples I'm going to use C as the target code, but this method\nworks just as well if you're starting from a traditional emulator\nthat's written in the assembly language of the target machine. You\nstill will have a dispatch loop, and the equivalent of a switch jump\nto a set of labels or procedures written in the target assembly\nlanguage which decode the operands and execute instructions to\naccurately simulate the emulated machine. Our algorithm is simply\nthat the disassembler outputs that code for each instruction\ninstead of executing it.

\n

We should be able to very quickly write a first naive hack at this\nwhich is still structured primarily as an emulator, but before we\ndo that, let's have a little digression:

\n

Let's go back to the days when you were a good old-fashioned emulator\nwriter. You started by working on someone else's emulator because\nyou thought it was written pretty inefficiently, and you thought you\ncould do better, right? :-) Well, you may not have done the hack below but I\nguarantee that with hindsight you'll agree you wish you had! The\nbest way to write a new emulator when you already have a working\none, even if it isn't very efficient, is to hack up a "dual CPU" testbed.\nBasically this is the same as a regular emulator, but it contains\ntwo completely independent CPU cores. The main dispatch loop calls\nboth cores for every instruction, and it compares all the\nregisters after each one has emulated the instruction to see if they\ndiffer. It'll look something like this:

\n
for (;;) {\n  assert(Reg_PC_1 == Reg_PC_2);\n  opcode = *Reg_PC_1++; Reg_PC_2 = Reg_PC_1;\n  engine1(opcode); engine2(opcode);\n  assert(Reg_PC_1 == Reg_PC_2);\n  assert(Reg_A_1 == Reg_A_2);\n  assert(Reg_B_1 == Reg_B_2);\n  assert(Flag_Carry_1 == Flag_Carry_2);\n  assert(Flag_Negative_1 == Flag_Negative_2);\n  assert(Flag_Zero_1 == Flag_Zero_2);\n  assert(Flag_Overflow_1 == Flag_Overflow_2);\n}
\n

The astute reader will have realised that it is also wise to check\nthe RAM which has changed too, and indeed each engine does need its\nown copy of the RAM, but I'll save you a little effort and let you\nknow that in practice, unless you break some really obvious part\nof the load/save-memory code, almost all emulation errors show up\nfirst in the registers. Comparing two entire sets of memory is a\nvery expensive proposition, even in something as small as a 64K micro\nwith just 4K of RAM.

\n

OK, back on track... what we're going to do is modify one of the\nCPUs in our Dual CPU emulator so that instead of dispatching by\nopcode, it dispatches by the address of the opcode. To make this\nclear, let's look at our short example. We'll assume the code sequence\nfor the two instructions I gave is in memory at address 0xBCA7...

\n
BCA7:        TFR  B,A\nBCA9:        ADDA #21
\n

Our loop (omitting the consistency checks for brevity) now becomes:

\n
for (;;) {\n  opcode = mem[Reg_PC_1++];\n  engine1(opcode); engine2(Reg_PC_2);\n}
\n

and the 'new' emulator dispatch loop now looks like this:

\n
for (;;) {\n  if (cycles >= eventTrigger) do_some_timed_event();\n\n  switch (Reg_PC_2) {\n\n  /* This section is automatically generated from the binary */\n\n  case 0x0000:\n    ... similar code for the rest of the program ...\n\n  case 0xBCA7:\n    cycles = cycles + 2;\n    Reg_B_2 = Reg_A_2;\n    Reg_PC_2 = 0xBCA9;\n    break;\n\n  case 0xBCA9:\n    cycles = cycles + 2;\n    temp = Reg_A_2 + 21 + Flag_Carry_2;\n    Flag_Carry_2 = temp >> 8;\n    Flag_Overflow_2 = (Reg_A_2 ^ 21 ^ (Flag_Carry_2<<7))>>7;\n    Reg_A_2 = temp & 0xff;\n    Flag_Negative_2 = Reg_A_2 >> 7;\n    Flag_Zero_2 = (Reg_A_2 == 0 ? 1 : 0);\n    Reg_PC_2 = 0xBCAB;\n    break;\n\n  case 0xBCAB:\n    ... similar code for the rest of the program ...\n\n  /* End of automatically generated section */\n  }\n}
\n

You can see in the above that by switching from executing by opcode\nto executing by code address, we've already been able to make a\nfew optimisations. For instance the old emulator had to decode the\noperand byte of the TFR opcode (to determine that the operands were\nregister A and register B), and we can now see at the time we generate\nthe code above that the operand to the ADD instruction is the\nliteral value 21. We don't need to fetch that operand at emulate\ntime any more, we know what it is at translate time. Also we know\nwhat the PC will be on the next instruction so we just set it directly\ninstead of adding to it.

\n

(From now on we'll assume we're talking about the 'new' emulator and\ndrop the "_2" suffix on everything...)

\n

Just to make it absolutely clear at this point, the body of the dispatch\nloop above was generated by a program similar to a disassembler, containing\na dispatch table based on opcodes which eventually executes code something\nlike this:

\n
Reg_PC_translator = 0;\nfor (;;) {\n  fprintf(codefile, "  case 0x%04x:\\n", Reg_PC_translator);\n  opcode = mem[Reg_PC_translator];\n  Reg_PC_translator += 1;\n  switch (opcode) {\n\n  case TFRregreg:\n    fprintf(codefile, "    cycles = cycles + 2;\\n");\n    operand = mem[Reg_PC_translator];\n    firstreg = operand>>4;\n    secondreg = operand&15;\n    fprintf(codefile, "    Reg_%s = Reg_%s;\\n", Regname[firstreg],\n                                                Regname[secondreg]);\n    fprintf(codefile, "    break;\\n");\n    Reg_PC_translator += 1;\n    break;\n\n    ... similar code for the other opcodes ...\n  }\n  fprintf(codefile, "\\n");\n}
\n

So you should be able to see now that the structure of our translator\nis pretty much falling into shape; there's only a couple of key steps\nleft. What we have above would actually work, but we still have the\noverhead of a dispatch loop. So how do we get rid of it? Well, it's\npretty easy in principle - we just remove the break; and\ndrop through to the next instruction:

\n
for (;;) {\n  if (cycles >= eventTrigger) do_some_timed_event();\n\n  switch (Reg_PC) {\n\n  /* This section is automatically generated from the binary */\n\n  case 0x0000:\n    ... similar code for the rest of the program ...\n\n  case 0xBCA7:\n    cycles = cycles + 2;\n    Reg_A = Reg_B;\n\n  case 0xBCA9:\n    cycles = cycles + 2;\n    temp = Reg_A + 21 + Flag_Carry;\n    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;;\n    Reg_A = temp & 0xff;\n    Flag_Negative = Reg_A >> 7;\n    Flag_Zero = (Reg_A == 0 ? 1 : 0);\n    Reg_PC = 0xBCAE;\n    break;\n\n    ... similar code for the rest of the program ...\n  /* End of automatically generated section */\n  }\n}
\n

This is now greatly improved, because we no longer have the overhead\nof returning to the dispatch loop for the majority of instructions.\nThe only time we'll have to do that is if we execute a branch. We've\nalso been able to drop the setting of the PC and we'll do it only when\nwe need to use the PC, such as when we return to the dispatch loop,\nor when the code itself needs to use the PC (as with a JSR for example).

\n

So let's extend our test program with "BVS 0x2204" (Branch if Overflow\nto the code at address 0x2204):

\n
0000: ...\n...\n2204: L2204: ...\n...\nBCA7:        TFR  B,A\nBCA9:        ADDA #21\nBCAB:        BVS  0x2204\nBCAF: ...\n...
\n

The code for the BVS is pretty simple: if (Flag_Overflow) break;,\ni.e. stop executing in-line code, and let the dispatch loop cause a jump\nto the new address:

\n
for (;;) {\n  if (cycles >= eventTrigger) do_some_timed_event();\n\n  switch (Reg_PC) {\n\n  /* This section is automatically generated from the binary */\n\n  case 0x0000:\n    ... similar code for the rest of the program ...\n\n  case 0xBCA7:\n    cycles = cycles + 2;\n    Reg_A = Reg_B;\n\n  case 0xBCA9:\n    cycles = cycles + 2;\n    temp = Reg_A + 21 + Flag_Carry;\n    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n    Reg_A = temp & 0xff;\n    Flag_Negative = Reg_A >> 7;\n    Flag_Zero = (Reg_A == 0 ? 1 : 0);\n\n  case 0xBCAB:\n    cycles = cycles + 3;\n    if (Flag_Overflow) {\n      cycles = cycles + 1;\n      Reg_PC = 0x2204;\n      break;\n    }\n\n  case 0xBCAE:\n    ... similar code for the rest of the program ...\n\n  /* End of automatically generated section */\n  }\n}
\n

I hope these small incremental changes aren't too tedious, but I didn't\nwant to skip too many stages in case anyone loses the place. Here's\nanother relatively trivial change but it's an important one:

\n
for (;;) {\n  if (cycles >= eventTrigger) do_some_timed_event();\n\n  goto *dispatch[Reg_PC];\n\n  /* This section is automatically generated from the binary */\n\n  L_0000:\n    ... similar code for the rest of the program ...\n\n  L_BCA7:\n    cycles = cycles + 2;\n    Reg_A = Reg_B;\n\n  L_BCA9:\n    cycles = cycles + 2;\n    temp = Reg_A + 21 + Flag_Carry;\n    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n    Reg_A = temp & 0xff;\n    Flag_Negative = Reg_A >> 7;\n    Flag_Zero = (Reg_A == 0 ? 1 : 0);\n\n  L_BCAB:\n    cycles = cycles + 3;\n    if (Flag_Overflow) {\n      cycles = cycles + 1;\n      Reg_PC = 0x2204;\n      continue;\n    }\n\n  L_BCAE:\n    ... similar code for the rest of the program ...\n\n  /* End of automatically generated section */\n}
\n

I have used GCC's non-standard extension here which allows you to\njump through an array of labels. This is how most switch jumps\nare executed anyway. (At least we hope so; a binary search table\nwould be most inefficient in a program like this). So, the case\nlabels have been replaced with simple labels, and the break out of\nthe case has been replaced with a continue, which\ntakes it back to the start of the enclosing dispatch loop.\nOtherwise the code is just the same.

\n

Now, let's look more closely at the BVS instruction. In this case\nwe do know at translate time where the destination is, so we could\nin fact do away with the return to the dispatch loop, and dispatch\ndirectly ourselves at the point of the BVS:

\n
  L_BCAB:\n    cycles = cycles + 3;\n    if (Flag_Overflow) {\n      cycles = cycles + 1;\n      Reg_PC = 0x2204;\n      continue;\n    }\n\n  L_BCAE:
\n

Now becomes ...

\n
  L_BCAB:\n    cycles = cycles + 3;\n    if (Flag_Overflow) {\n      cycles = cycles + 1;\n      goto L_2204;\n    }\n\n  L_BCAE:
\n

This is pretty good but there's one difference between this and the\noriginal code. The test for scheduled events based on the cycle count\nwill not be executed. Let's modify the code we generate a little to\nput it back in, inside the BVS code...

\n
  L_BCAB:\n    cycles = cycles + 3;\n    if (Flag_Overflow) {\n      cycles = cycles + 1;\n      if (cycles >= eventTrigger) do_some_timed_event();\n      goto L_2204;\n    }\n\n  L_BCAE:
\n

You may have noticed that I'd already dropped that test in the two-opcode\nsequence when we dropped through the first instruction. The reason for\nthis is that scheduled events (eg simulated interrupts from a disk drive)\nseldom need to be cycle-perfect, so as long as we do the test relatively\nfrequently, it'll be often enough. (If this isn't true for your emulator\nthen don't do this optimisation, but for now I'll assume it's OK).

\n

What I'm going to suggest next is a criterion for when we need to\ninsert one of these tests: I believe that they only need to be done\nwhen you execute a branch backwards. It is almost impossible for code\nto execute in a straight line forwards for any length of time. Even\nif it does execute straight-line code, it won't take long - programs\njust are not that big, and straight-line code is not going\nto be megabytes long. At some point - almost certainly within a K\nat most - it will branch backwards (or somewhere non-fixed, such as in\na return from subroutine). I think those points are sufficiently frequent\nto be good places to insert the tests that would normally be in the\ndispatch loop.\nWe will soon be getting to the point where you will see why it's\nworthwhile to eliminate as many of these tests as possible...

\n

Aside: the most likely event that the\nmajority of video-game emulators needs is a vsync interrupt, to allow\nflicker-free updating of the screen by the program. Let's say this\nis in fact the most frequent or time-critical interrupt that you\nwill have. It's frequency is 50Hz. Your emulated CPU is 1MHz,\nso... you'll be looking for a clock interrupt at least once every\n1,000,000/50 = 20,000 cycles. So your accuracy will not be diminished\nby more than 5% if you force out one of the event tests every 1,000\ncycles, right? Not a problem, because you're keeping a cycle count\nin the translator anyway, and all you have to do is simply add it\nup while generating code, and if it ever gets to a multiple of 1,000\nwithout you planting an event test due to something like a BVS,\nthen force one out into the code unconditionally.

\n

Incidentally, this same call can be used to adjust the real-time\nspeed of your emulation to match the real CPU. If you've followed\nthe suggestion above, you will have at least 1000 calls per emulated\nsecond, so we're dealing with quite a fine-grained timer here: all\nyou need to do is compare the cycles to real time, and wait in a\nspin-loop until real time has caught up with emulated time. (I'm\nassuming your emulator is too fast; if it's too slow, you have\nother problems!). With a 1000Hz test, any delay loops are not going\nto be noticeable, and your video game will play smoothly. (With\ntoo few tests, the response can get 'choppy').\nCycle-perfect accuracy is seldom required for the majority of old arcade games.\nThis is a much cheaper solution to real time accuracy than the\ntraditional one which is to handle timing on each and every\ninstruction. The danger there is that the overhead of the test\nis enough to slow you down. This isn't a problem on a fast processor,\nbut if you had a fast processor you wouldn't need to create a static\ntranslation in the first place!

\n

OK, that's the end of the simple formula to take an emulator and\nconvert it almost mechanically into a static binary translator. If we\nwant to generate smarter code than this, we now have to look at\nsomething a little more difficult. Let's look back at what we have so far:

\n
  L_BCA7:\n    cycles = cycles + 2;\n    Reg_A = Reg_B;\n\n  L_BCA9:\n    cycles = cycles + 2;\n    temp = Reg_A + 21 + Flag_Carry;\n    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n    Reg_A = temp & 0xff;\n    Flag_Negative = Reg_A >> 7;\n    Flag_Zero = (Reg_A == 0 ? 1 : 0);\n\n  L_BCAB:\n    cycles = cycles + 3;\n    if (Flag_Overflow) {\n      cycles = cycles + 1;\n      if (cycles >= eventTrigger) do_some_timed_event();\n      goto L_2204;\n    }\n\n  L_BCAE:
\n

If we know that this code above is only executed in a straight\nline, and none of the intermediate instructions are ever jumped to\ndirectly, we can rewrite the above as follows:

\n
  L_BCA7:\n    Reg_A = Reg_B;\n    temp = Reg_A + 21 + Flag_Carry;\n    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n    Reg_A = temp & 0xff;\n    Flag_Negative = Reg_A >> 7;\n    Flag_Zero = (Reg_A == 0 ? 1 : 0);\n    if (Flag_Overflow) {\n      cycles = cycles + 8;\n      if (cycles >= eventTrigger) do_some_timed_event();\n      goto L_2204;\n    }
\n

Note the only time we write to cycles is when we branch elsewhere,\nbecause the cycle count for the drop-through code is being remembered\nby the translator and will be output only when it is needed. (This is\npretty much the same as how it keeps track of the PC ... and indeed\nthe PC isn't even written to on a branch because it is known implicitly\nat the destination of a fixed jump as well. We'd write to it on a\nreturn from subroutine or an indirect jump, but only then).

\n

I hear you ask *Well, that looks interesting, but how do you eliminate\nthose labels, and is the benefit really worth it? It looks like\nall you save are a few additions to the cycle count...*
\nGood question, and one I'll only partially answer right now. Is the\nbenefit really worth it? No, not as given above. Our example isn't\ncomplex enough to show the big win yet. Sorry to make this even\nlonger, but all will soon become clear. Let's add a few more instructions\nto our program...

\n
0000: ...\n...\n2204: L2204: ...\n...\nBCA3:        LDB  0x0100\nBCA6:        ASL  B\nBCA7:        TFR  B,A\nBCA9:        ADDA #21\nBCAB:        ADDA B\nBCAC:        BVS  0x2204\nBCAF: ...\n...
\n

which translates to

\n
  L_BCA3:\n    Reg_B = mem[0x0100];\n    temp = Reg_B << 1;\n    Reg_B = temp&0xff;\n    Flag_Overflow = Flag_Carry;\n    Flag_Carry = temp>>8;\n    Flag_Negative = Reg_B >> 7;\n    Flag_Zero = (Reg_B == 0 ? 1 : 0);\n    Reg_A = Reg_B;\n    temp = Reg_A + 21 + Flag_Carry;\n    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n    Reg_A = temp & 0xff;\n    Flag_Negative = Reg_A >> 7;\n    Flag_Zero = (Reg_A == 0 ? 1 : 0);\n    Reg_A = Reg_B;\n    temp = Reg_A + Reg_B + Flag_Carry;\n    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ Reg_B ^ (Flag_Carry<<7))>>7;\n    Reg_A = temp & 0xff;\n    Flag_Negative = Reg_A >> 7;\n    Flag_Zero = (Reg_A == 0 ? 1 : 0);\n    if (Flag_Overflow) {\n      cycles = cycles + 8;\n      if (cycles >= eventTrigger) do_some_timed_event();\n      goto L_2204;\n    }
\n

Blech. It's a lot of code for 6 original instructions. Most of it\nis coming from the setting of flags which are never used. What would\nhappen if we don't emit the statements which set flags if those flags\nare never used at all before they are written to again??? I'll tell you, this\nis what would happen:

\n
  L_BCA3:\n    Reg_B = mem[0x0100];\n    temp = Reg_B << 1;\n    Reg_B = temp&0xff;\n    Flag_Carry = temp >> 8;\n    Reg_A = Reg_B;\n    temp = Reg_A + 21 + Flag_Carry;\n    Flag_Carry = temp >> 8;\n    Reg_A = temp & 0xff;\n    Reg_A = Reg_B;\n    temp = Reg_A + Reg_B + Flag_Carry;\n    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ Reg_B ^ (Flag_Carry<<7))>>7;\n    Reg_A = temp & 0xff;\n    Flag_Negative = Reg_A >> 7;\n    Flag_Zero = (Reg_A == 0 ? 1 : 0);\n    if (Flag_Overflow) {\n      cycles = cycles + 8;\n      if (cycles >= eventTrigger) do_some_timed_event();\n      goto L_2204;\n    }
\n

As you can see, most of the flags disappear except for the few we\nactually need. If we have a longer sequence (which we'll now assume\nis the case) we can drop even more of the flag calculations, except\nwhere we need to use them. Without a particularly complex dataflow\nanalysis of the whole program, we should probably assume that we need\nto write back all the flags at any point where we jump elsewhere, or\nany time there is a necessary label which allows code elsewhere to\njump into our sequence:

\n
  L_BCA3:\n    Reg_B = mem[0x0100];\n    temp = Reg_B << 1;\n    Reg_B = temp&0xff;\n    Flag_Carry = temp >> 8;\n    Reg_A = Reg_B;\n    temp = Reg_A + 21 + Flag_Carry;\n    Flag_Carry = temp >> 8;\n    Reg_A = temp & 0xff;\n    temp = Reg_A + Reg_B + Flag_Carry;\n    Reg_A = temp & 0xff;\n    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ Reg_B ^ (Flag_Carry<<7))>>7;\n    if (Flag_Overflow) {\n      Flag_Negative = Reg_A >> 7;\n      Flag_Zero = (Reg_A == 0 ? 1 : 0);\n      cycles = cycles + 8;\n      if (cycles >= eventTrigger) do_some_timed_event();\n      goto L_2204;\n    }
\n

You've probably worked out by now that what we are trying to do is\nwork with what the compiler writers call 'basic blocks', i.e. the\nlongest sequence of straight-line code you can find. If we apply\nsome relatively simple compiler techniques to the improved sequence\nabove, it gets even better:

\n
  L_BCA3:\n    temp = (mem[0x0100] << 1)&0xff;\n    Reg_B = temp&0xff;\n    temp = Reg_B + 21 + (temp>>8);\n    temp = (temp&0xff) + Reg_B + (temp>>8);\n    Reg_A = temp & 0xff;\n    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ Reg_B ^ (Flag_Carry<<7))>>7;\n    if (Flag_Overflow) {\n      Flag_Negative = Reg_A >> 7;\n      Flag_Zero = (Reg_A == 0 ? 1 : 0);\n      cycles = cycles + 8;\n      if (cycles >= eventTrigger) do_some_timed_event();\n      goto L_2204;\n    }
\n

This is actually pretty damned good code now, although we did have some\nquite complex compiler-like optimisations to make and I haven't explained\nhow to do those, nor am I going to, but I will show you a neat hack to\ndo the redundant flag removal. But having shown, I hope, why the\nremoval of unused labels is worthwhile, I'll now give you the promised\nsecond half of the answer to the question asked some time back:\nhow do you eliminate those labels?

\n

Well, we need to know the flow control of the program and note the\ndestinations of jumps. Those jump destinations are the only opcodes\nwhich need to be labelled. To some extent you might be able to work\nthose out statically, by having a slightly smarter disassembler framework\nwhich does a tree-walk of the source, starting at the entry point.\nI.e. whenever it hits a branch or subroutine call, it also goes off to the\ndestination and looks at the code there too. The problem with this is\nthat very few architectures are designed so that you always can determine\nthe jump destination just by looking at the code. Most architectures\nallow indirect jumps through store or registers, or let you tweak a\nreturn address on the stack so that your return from subroutine goes\nsomewhere other than where your subroutine was called from. This is\na major pain in the ass and the only practical solution is to profile\nthe execution of the code and mark the jump destinations at run time.

\n

Fortunately we have just the piece of code to do this for us - the\noriginal emulator (or even our own one at this point, before we start\nmaking 'dangerous' assumptions such as removing the labels in front\nof any instructions) can be used to execute the code, and it can be\nmodified to note in an array which is the same size as memory whether\nany code address is ever jumped to.

\n

As you can imagine, any one run through the program is not going to\nexercise every path in the code, so your profiling has to load this\narray at startup to get the results of previous runs; it then adds\nany new info it finds in this run, and writes the cumulative results\nback out to a file. I found that about a week of playtesting fully\nexercised a game. It's pretty important that you play through all\nlevels and try all problems, etc. You should execute all areas of\ncode at least once, including things like getting on the high score\ntable. Once you've done this you'll have a list of jump\ndestinations. Use this list to seed a 'smart disassembler'\nas suggested above. The two techniques together should find all\nthe executable code areas in your binary. The rest of the ROM\nyou're translating is probably\ndata. You might also run it through a 'traditional' disassembler\nand see if it finds anything that looks like code in some area\nthat you missed. (It helps in this case if your list of jump\ndestinations/tree-walking start points is held in ascii/hex. Makes\nit easier to add to by hand!)

\n

Note: if you miss any jump targets, your translation will find them\nbecause when you do a goto *dispatch[Reg_PC];, all the\nunlabelled statements will have an entry which takes you to a diagnostic\nroutine, and that routine will print out the value of Reg_PC and\ntell you to add it to the jump dest table, and rebuild your emulator.\nIf you want to get really fancy, you can do this quietly\nand pass control over to the other emulator core (the 'traditional'\nemulator, which should still be in your program even if it isn't\nbeing called any more) and it can interpret instructions one by one\nuntil it gets to an address which is the entry point to one of\nour statically translated sequences. That'll let you play the\ngame through, and you can automatically rebuild every time you run it,\nto incrementally improve the code.

\n

Once you have that list of jump destinations, modify your translator\nlike this (remember our example from early on?):

\n
Reg_PC = 0;\nfor (;;) {\n  if (jumpdest[Reg_PC]) fprintf(codefile, "L_%04x:\\n", Reg_PC);\n  opcode = mem[Reg_PC];\n  Reg_PC += 1;\n  switch (opcode) {\n...\n  case TFRregreg:\n    cycles = cycles + 2;\n    operand = mem[Reg_PC];\n    firstreg = operand>>4;\n    secondreg = operand&15;\n    fprintf(codefile, "    Reg_%s = Reg_%s;\\n", Regname[firstreg],\n                                                Regname[secondreg]);\n    Reg_PC += 1;\n    break;\n...\n  }\n  fprintf(codefile, "\\n");\n}
\n

We're almost finished now! We just have to remove those redundant\nflag expressions and we're done. That turns out to be relatively\neasy. Here's a complete demo program; it's not actually using our\nexample code above as I wrote it some time before writing this\ndocument, but it's very obvious what's going on:

\n
// A test program to eliminate redundant code; does *not* do common\n// subexpression elimination or constant folding, although in a real\n// program the CSE and dead code stuff would best be done by the same program\n\n// We might assume (perhaps wrongly) that we are translating hand-written\n// assembly code and that no obvious peephole optimisation is possible.\n\n#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n\n#ifndef FALSE\n#define FALSE (0!=0)\n#define TRUE  (0==0)\n#endif\n\n#define MAX 1024\nlong defs[MAX], uses[MAX];\nchar *codes[MAX];\nint nextfree = 0;\n\n/* Metacodes */\n#define Always 1\n#define Flush 2\n\n/* Real regs */\n#define PC  4\n#define A   8\n#define B   16\n#define CC  32\n\n/* Internal variables */\n#define TMP 64\n\n/* See http://groups.yahoo.com/group/compilers101/ for a more general\n   technique to eliminate redundant code.  Here we are limited to\n   30 variables */\n\nvoid flush(long regs)\n{\n  int i;\n  long common_regs;\n\n  for (i = nextfree-1; i >= 0; --i) {\n    if (common_regs = (regs & defs[i])) {\n      /* if bits in 'defs' then this needs to be dumped. */\n      fprintf(stdout, "// %02d lookfor: %02x  Item %d - def %02x\\n",\n        nextfree, regs, i, defs[i]);\n      defs[i] |= Always;  /* flag this line for printing */\n      regs &= ~common_regs; /* don't need to look for these ones any more */\n    }\n    if (defs[i]&Always) regs |= uses[i]; /* Any unconditionals + parents */\n  }\n\n  for (i = 0; i < nextfree; i++) {\n      fprintf(stdout, "/* %03d [def:%02x] [use:%02x] */  ",\n        i, defs[i], uses[i]);\n      fprintf(stdout, "%s %s", (defs[i]&Always ? "   " : "// "), codes[i]);\n  }\n\n  nextfree = 0;\n}\n\n#define dump(def, use, code) (defs[nextfree] = def, uses[nextfree] = use, \\\n                              codes[nextfree] = code, nextfree += 1)\n\nint main(int argc, char **argv) {\nint i;\n  //  Test program for a non-existent machine.  Several details omitted.\n  //\n  //  $ORG A000\n  //  LDB #42\n  //  INP A,B\n  //  INC B\n  //  INC B\n  //  ASR A,B\n  //  LDB #1\n  //  JMP 0xFC08    ; end of basic block ...\n\n  dump(Always,  Always, "           //  LDB #42\\n");\n  dump(PC, 0, "PC = 0xA000;\\n");\n  dump(B,  0, "B = 42;\\n");\n  dump(Always,  Always, "           //  INP A,B\\n");\n  dump(PC, 0, "PC = 0xA002;\\n");\n  dump(A | Always,  B | Always, "A = fninput(B);\\n"); /* has side effects */\n  dump(Always, Always, "           //  INC B\\n");\n  dump(PC, 0, "PC = 0xA003;\\n");\n  dump(TMP,B, "tmp = B+1;\\n");\n  dump(CC, TMP, "CC = (tmp>>8)&1;\\n");\n  dump(B,  TMP, "B = tmp&255;\\n");\n  dump(Always, Always, "           //  INC B\\n");\n  dump(PC, 0, "PC = 0xA004;\\n");\n  dump(TMP,B, "tmp = B+1;\\n");\n  dump(CC, TMP, "CC = (tmp>>8)&1;\\n");\n  dump(B,  TMP, "B = tmp&255;\\n");\n  dump(Always, Always, "           //  ASR A,B\\n");\n  dump(PC, 0, "PC = 0xA005;\\n");\n  dump(A,  B, "A = B>>1;\\n");\n  dump(Always, Always, "           //  LDB #1\\n");\n  dump(PC, 0, "PC = 0xA006;\\n");\n  dump(B,  0, "B = 1;\\n");\n  dump(Always, Always, "           //  JMP 0xFC08\\n");\n  dump(PC, 0, "PC = 0xA008;\\n");\n  dump(Always, Always, "\\n");\n  dump(PC | Always, Always, "goto *lab[PC = 0xFC08];\\n");\n  flush(A | B | CC | PC); /* List of registers to force out (excluding TMP) */\n  exit(0);\n  return(0);\n}
\n

What we're doing here is taking the printf that we're currently\nusing, and replacing it with a 'dumpf' which has two extra parameters;\none is a list of the registers or internal variables that the\nstatement uses as inputs, and\nthe other is a list of the registers or internal variables that the\nstatement writes to or defines. [Actually in that example we\nuse a simple dump macro, but you know how to expand that\nto a stdargs procedure that'll take printf-style extra parameters, right?]\nThe very simple def/use chain ensures that for\nany use of a variable, the immediately previous definition of it is\noutput - and so on, recursively. This particular implementation\nis a really really simple one and gets its simplicity by using\nbit flags in long ints to simplify the tables it needs to keep. If your\ntranslator needs more than 30 registers or internal variables, a more\ngeneral technique should be used. (Hint: look up Directed Acyclic\nGraphs)

\n

The redundant expression elimination code above can also be twisted so\nthat you can generate code conditionally, such as when you want to\nreconstitute the condition code registers from the split-apart individual\nflags. If you're generating assembler rather than C and have a processor\nwhere the flag bits are compatible with your emulated system, then you\nmight not bother with separate flags and just use the hardware CC, but\nusually it's easier to calculate the flags explicitly. You can either keep the CC up\nto date, and examine the relevant bits when you need them, ... or you\ncan do it this way, and just make minimal changes only to the flags that\nyou need, and coalesce those flags into a combined CC only on the rare\noccassions when it is really needed, such as on the 6809's "PSHS CC"\ninstruction which pushes the whole CC on the stack.\nHowever the easy way to manage the CC so that you not only amalgamate the\nflags when needed, but also generate code to update the individual flag\nbits beforehand, is to use the redundant code optimiser from above.\nAny time you translate an opcode which changes one of the CC flags,\noutput this at the end of the sequence:

\n
dump(CC, OV|MI|CA|ZE, "Reg_CC = Flag_Overflow << 8 | Flag_Negative << 7 | "\n                               "Flag_Carry << 6 | Flag_Zero << 5;");
\n

If anything uses the combined CC, it'll include that in it's use\nparameter, and the previous dump instruction will be generated, otherwise\nit will be dropped.

\n
dump(Always | SP, SP | CC, "mem[Reg_SP++] = Reg_CC;");
\n

So that's about it. I didn't explain the 'compiler-like optimisations'\nbecause to do so would require a document as long as this one, and it's\ntime to cut you a break and stop here. Write the generated code carefully\nand you probably won't need that level of optimisation anyway - or if\nyou have a good compiler it'll do it for you. A second reason for\nremoving unused labels from each translated instruction is that it\nalso allows the compiler to optimise more aggressively too.\nThis is also a reason why we should eliminate most of the calls to the\ntimed event test procedure - most compilers will not be able to work out the\nside-effects of that procedure (such as writing through a pointer), and the call will automatically cause the\ncurrent basic block to end. This will severely limit the register optimisations\nthat the compiler can do for you.\nYou may find that within basic blocks, your compiler will keep each emulated\nregister in a real register and only write it back to store at the\nend of the basic block. In exceptional cases it may slave to real\nregisters throughout the whole emulator procedure or indeed the\nentire program. It doesn't hurt to declare your emulated registers\nwith the register keyword, such as

\n
  register int Reg_A, Reg_B;
\n

But be careful not to do this for variables that aren't heavily\nused. For instance we seldom mention Reg_PC any more and it would\nbe a bad choice to force into a register if it caused a more heavily\nreferenced variable to be spilled back to store.

\n

I believe that if you follow the procedure outlined above and are\nalready familiar with emulators, you should not find it hard to\nwrite a translator, and take one program and translate it. This\nisn't high Computer Science, it's just hacking that any competant\nprogrammer can do. So pick your favourite video game and emulator\nand go make a translation!

\n

If you're interested in emulation for other reasons (eg you\nneed to convert some stiffware COBOL program that you've lost\nsource to, from IBM360 binary to ARM code, the techniques are\nthe very same. In fact you may find it easier because if you're\nworking from compiled code rather than hand-written assembler,\nyou're unlikely to hit any of the nasty 'gotcha's that we sometimes\ndo, such as self-modifying code... (which you can handle either\nby retaining a traditional emulator as well as the translation,\nor you can manually analyse the code and special-case it if the\ngenerated code is consistently the same)

\n

Good luck!

\n

Graham

\n
\n

Postscript: Read this section only after you've actually\ngot a translator running. If it's your first time round you can\nskip this section as it is concerned with optimisations that give\nrelatively minor incremental improvement but take some effort to\nset up. Do not try any of this until you have got your translated\nprogram working correctly.

\n

Constant expression folding

\n

This is often done for you by the compiler but if you add a mechanism\nto do it yourself, you're halfway towards adding some other optimisations\nwhich need the same structure in place.

\n

A good example of constant folding can be seen in the ARM, where\nliteral constants in opcodes are only eight bits, so larger constants\nsuch as 0x12345678 are sometimes loaded in multiple operations, such as

\n
MOV R0, #0x12000000\nORR R0, #0x00340000\nORR R0, #0x00005600\nORR R0, #0x00000078
\n

An alternative of course is\nto do an LDR directly from an area of store pre-initialised with the constant\nby the linker, but this sort of thing does come up. When it does we\ndon't want to emulate it the hard way, but would prefer a simple\nR0 = 0x12345678;

\n

To do this, we have to remember any constant values we happen to\nsee being written to a register, and if we can fold constant operations\nat translate time then we should do so.

\n

The ideal way to do this would be to build up full expression trees\nand handle it exactly the way an optimising compiler would. But that\nis an incredible amount of work, and we can get quite a lot of the\nbenefit from some relatively crude hacks. Firstly, we just need\na procedure to remember(reg, value); and then a lookup\nprocedure to get the value of reg if known. If it is\nknown we use the constant instead of reg, if we're doing an operation\nwith another constant, we fold them into one; if the value of reg\nis not known, we just plant code like normal.

\n

Time for some more code examples. We'll ignore the complexity of\ndecoding the LD and OR instructions to decide whether the parameters\nare immediate literal constants, direct from store locations, or\nother registers. We'll keep this short by assuming the operands\nreg, reg2, addr,\nconst and shift\nhave already been decoded by the translator framework.

\n

The remember() procedure is implementing what is\ncalled 'constant propogation'. The code below which\ncalculates val | (const<<shift) is doing\n'constant expression folding'.

\n
  case LDimmediate:  /* LD reg, byte-const, shift */\n    remember(reg, const<<shift);\n    dumpf(reg, 0, "R%d = %d", reg, const<<shift));\n    break;\n\n  case LDreg:        /* LD reg, reg2, shift */\n    if (known(reg2, &val2)) {\n      remember(reg, val2<<shift);\n      dumpf(reg, 0, "R%d = %d", reg, val2<<shift));\n    } else {\n      forget(reg);\n      dumpf(reg, reg2, "R%d = R%d<<%d", reg, reg2, shift));\n    }\n    break;\n\n  case LDdirect:     /* LD reg, storeaddr, shift */\n    forget(reg);\n    dumpf(reg, 0, "R%d = mem[%d]<<%d", reg, addr, shift));\n    break;\n\n  case ORimmediate:  /* OR reg, byte-const, shift */\n    if (known(reg, &val)) {\n      remember(reg, val | (const<<shift));\n      dumpf(reg, 0, "R%d = %d", reg, val | (const<<shift));\n    } else {\n      forget(reg);\n      dumpf(reg, reg, "R%d = R%d | %d", reg, reg, const<<shift));\n    }\n    break;\n\n  case ORreg:        /* OR reg, reg2, shift */\n    if (known(reg, &val)) {\n      if (known(reg2, &val2)) {\n        remember(reg, val | (val2<<shift));\n        dumpf(reg, 0, "R%d = %d", reg, val | (val2<<shift));\n      } else {\n        forget(reg);\n        dumpf(reg, reg2, "R%d = %d | (R%d<<%d)", reg, val, reg2, shift);\n      }\n    } else if (known(reg2, &val2)) {\n        forget(reg);\n        dumpf(reg, reg, "R%d = R%d | %d", reg, reg, (val2<<shift));\n    } else {\n      forget(reg);\n      dumpf(reg, reg|reg2, "R%d = R%d | (R%d<<%d)", reg, reg, reg2, const<<shift));\n    }\n    break;\n\n  case ORdirect:     /* OR reg, storeaddr, shift */\n    if (known(reg, &val)) {\n      dumpf(reg, 0, "R%d = %d | (mem[%d]<<%d)", reg, val, addr, shift));\n    } else {\n      forget(reg);\n      dumpf(reg, reg, "R%d = R%d | (mem[%d]<<%d)", reg, reg, addr, shift));\n    }\n    break;
\n

Beware when you start this kind of code though - you have to be sure to\ncall forget(reg) every time you write to a register with something that\nisn't a constant. So... in our short example above, we would generate calls\nto dump the following code:

\n
R0 = 0x12000000;\nR0 = 0x12340000;\nR0 = 0x12345600;\nR0 = 0x12345678;
\n

This isn't nearly as bad as it looks because the redundant code elimination\nalgorithm will only print out the last value of R0. None of the earlier\nones have any dependents, so they will be dropped.

\n

Now, why are we going to such lengths? Well, do you remember the code\nyou added to record jump destinations, in order to determine the starts\nand finishes of basic blocks? We're going to modify that code a little\nso that we record for every instruction the values of all the\nregisters at the point of that instruction! [Aside: in fact you can get\naway with recording the register values only at the entry points to\nevery basic block. This speeds it up considerably for no loss of information\nand allows you to playtest in real time...] We do this by having several\nparallel arrays which are each the same size as the code memory, and\nnoting in each element the first value of the register that we see at\nthat address. If we ever see a different value for the register at that\naddress, we tag the memory as 'deadbeef'. After many many runs of the\ncode under the emulator, we soon converge on a set of register contents\nwhich are invariant.

\n

We do this so that when we get to code translation time, we can treat a\nregister as if it were a constant, if its value is invariant. This lets\nthe constant-folding code above have even more data to play with. A perfect\nexample of this is our original (imaginary) code sequence,

\n
        TFR  B,A\n        ADDA #21
\n

I didn't make a big thing of it, but the ADD instruction as coded\nwas actually an "add with carry", and we never knew the status of the\ncarry flag at that point. However in real code (and this does happen\non some real machines) the programmer would clear the carry first:

\n
        CLC\n        TFR  B,A\n        ADDA #21
\n

In that case, the code we could generate - in our original\nscheme, before we added all the fancy stuff - would have been:

\n
  Flag_Carry = 0;\n  Reg_A = Reg_B;\n  temp = Reg_A + 21 + Flag_Carry;\n  Flag_Carry = temp >> 8;\n  Flag_Overflow = (Reg_A ^ 21 ^ (Flag_Carry<<7))>>7;\n  Reg_A = temp & 0xff;\n  Flag_Negative = Reg_A >> 7;\n  Flag_Zero = (Reg_A == 0 ? 1 : 0);
\n

So, not to repeat all the details again, the whole set of statements\nabove should now collapse down to the rather nice:

\n
Reg_A = (Reg_B + 21) & 0xff;
\n

(This only worked because the whole sequence was a basic block.\nIf the second or third instruction could be jumped to, the optimisations\nwould break the code...)

\n

But what has this to do with the trick of remembering the values of\nregisters from running under the emulator? Well, it's because programmers\nfor small micros tend to shave every byte. They might have a label\nin front of the "ADDA #21" and that label is branched to from places\nall over the code, where the programmer already knows that the carry\nis clear. So although remembering the value of registers in straight\nline code is relatively easy, optimising over the whole of the program\nis usually rather difficult! The normal way to do this would be with\nglobal dataflow analysis. That's hard work. People write theses about\nit. What we've done here is a hack, and to be honest it could in\nprinciple sometimes give the wrong result, but it's a question of low\nprobabilities, and the longer you run the code to gather stats, the\nless likely this approximation is going to differ from reality. And\nif it does mess up once in a blue moon, it's just a video game, right?

\n

So not only have we avoided doing global dataflow analysis, we also have\nnot built up an Abstract Syntax Tree\nnor have we written a general-purpose optimiser using tree rewriting\nrules. If you want to do that stuff, by all means do so, but you're\nlooking at the final 2 or 3% of improvement that requires 97% of effort!

\n

There is one more optimisation I am going to mention, and I haven't done\nthis myself yet so I'm not 100% sure of the details but I think it will\nturn out to be relatively easy. In fact I cheated in the earlier\ndescription by assuming that we could do this, though by the time you\nget here you've probably tried implementing everything yourself and\nrealised that this particular tweak wasn't handled yet. We had something\nlike this:

\n
    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ Reg_B ^ (Flag_Carry<<7))>>7;\n    Flag_Negative = Reg_A >> 7;\n    Flag_Zero = (Reg_A == 0 ? 1 : 0);\n    if (Flag_Overflow) {\n      goto L_2204;\n    }
\n

which in the next example became:

\n
    Flag_Carry = temp >> 8;\n    Flag_Overflow = (Reg_A ^ Reg_B ^ (Flag_Carry<<7))>>7;\n    if (Flag_Overflow) {\n      Flag_Negative = Reg_A >> 7;\n      Flag_Zero = (Reg_A == 0 ? 1 : 0);\n      goto L_2204;\n    }
\n

This was because Flag_Negative and Flag_Zero were not needed in the\ndrop-through code, and by moving them into the if/then clause (where\nthey are needed) the drop-through case will execute faster.\nI believe this optimisation can be done by slightly modifying the\nflush() to mark, but not remove, statements which have\nalready been conditionally output. I'll work on this some day but\nyou're all welcome to get to it first!

\n

That really is it for me this time.

\n

Graham Toal

\n
\n

gtoal at gtoal dot com

","headings":[{"level":2,"text":"An Emulator Writer's HOWTO for Static Binary Translation","id":"an-emulator-writer-s-howto-for-static-binary-translation"}]}}