{"id":621786,"date":"2023-03-25T09:48:52","date_gmt":"2023-03-25T14:48:52","guid":{"rendered":"https:\/\/news.sellorbuyhomefast.com\/index.php\/2023\/03\/25\/explaining-my-fast-6502-code-generator\/"},"modified":"2023-03-25T09:48:52","modified_gmt":"2023-03-25T14:48:52","slug":"explaining-my-fast-6502-code-generator","status":"publish","type":"post","link":"https:\/\/newsycanuse.com\/index.php\/2023\/03\/25\/explaining-my-fast-6502-code-generator\/","title":{"rendered":"Explaining my fast 6502 code generator"},"content":{"rendered":"
\n

\n To learn how optimizing compilers are made, I built one<\/a> targeting the 6502 architecture<\/a>.
\n In a bizarre twist, my compiler generates faster code than GCC, LLVM, and every other compiler I compared it to.\n <\/p>\n

<\/p>\n

I reckon my compiler isn’t doing more when it comes to high-level optimizations,
\n so the gains must be from the code generation<\/a> side.
\n This makes sense, as most compilers are multi-target, with backends
\n designed for modern RISC-like systems, not the ancient 6502.
\n It doesn’t matter how good GCC or LLVM’s high-level optimizations are
\n if they falter at the last leg of the race.\n <\/p>\n

Still, my compiler also beats those designed for retro and embedded systems, like VBCC, SDCC, and KickC.
\n For this reason, it seemed like a good idea to write about my technique.<\/p>\n

Cheating Disclaimer<\/h2>\n

Before I get into it, I want to cover three areas my compiler has an advantage, which aren’t tied to algorithmic design.
\n I call these my “cheats”, as other compilers could<\/i> do these things, but there are trade-offs involved.<\/p>\n

\n First, my compiler generates what are know as
\n “illegal” instructions<\/a>.
\n An illegal instruction is one which isn’t officially documented by the manufacturer,
\n but still exists in the hardware.
\n On most 6502 chips, a few illegal instructions exist which combine the behavior of two “legal” instructions.
\n Their use can save a few cycles, but not every backend generates them.\n <\/p>\n

Second, some of my compiler’s gains can be explained by its computational effort.
\n My compiler spends the majority of its CPU budget (a few milliseconds) doing instruction selection,
\n but not all compilers do.
\n Typically, the more time spent searching for a solution, the better the results.\n <\/p>\n

\n Lastly, there is loop unrolling and other optimizations that trade space efficiency for speed,
\n which is hard to compare fairly when benchmarking different compilers.
\n I tried to pick tests which weren’t affected by this,
\n but obviously I can’t be perfect.\n <\/p>\n

With my conscience clear, onto the algorithm!<\/p>\n

A Quick, Vague Overview<\/h2>\n

\n I’ve been calling my own attempt “outsider art<\/a>“,
\n as I didn’t know much about code generation when writing it.
\n In fact, the technique didn’t even originate in my compiler;
\n I based it on an old animation system I wrote years prior.
\n My algorithm is interesting because it combines instruction selection
\n with register allocation, but also because it’s written using continuations<\/a>.
\n In all my years of programming, it’s the only practical use I’ve found for such black magic.\n <\/p>\n

\n To briefly explain how it works, I’ll say that each basic block in my
\n IR<\/a> is represented as a
\n DAG<\/a> in
\n SSA form<\/a>.
\n The first step of code generation is to break both of these properties,
\n converting basic blocks to totally-ordered<\/a> lists that do not contain phi nodes.\n <\/p>\n

\n The ordered basic blocks are then processed from beginning to end,
\n generating multiple assembly code combinations per operation.
\n The list of combinations will grow at an exponential rate,
\n but most can be pruned using ideas from dynamic programming<\/a>
\n and branch-and-bound<\/a>.\n <\/p>\n

\n To improve the generated code, output states of each basic block are fed into their successor blocks as inputs.
\n This process repeats until a fixed point is reached.
\n A cooling schedule a-la simulated annealing<\/a>
\n is applied to find results faster.\n <\/p>\n

\n After this, each basic block will have multiple code sequences to choose from.
\n The most expensive ones can be heuristically pruned,
\n then a good selection can be made by solving a partitioned boolean quadratic problem<\/a> (PBQP).\n <\/p>\n

\n Finally, additional instructions are inserted as transitions between the basic blocks,
\n and a few optimization passes are run on the resulting assembly code for good measure.\n <\/p>\n

\n

A More Detailed Explanation<\/h2>\n

Basic Block IR<\/h3>\n

As stated, the
\n IR<\/a>
\n of each basic block is a
\n DAG<\/a> in
\n in SSA form<\/a>,
\n which sounds complicated until you see a picture of it.\n <\/p>\n

Given the code below:<\/p>\n

\nfoo = fn() ^ 5\nreturn foo - (foo & 3)<\/pre>\n
The IR DAG would look like this:<\/p>\n
        <\/p>\n
Each node in the graph represents a value, with edges denoting the flow of data.
\n        To compute a value, the nodes pointing to it must be computed first \u2014
\n        e.g. to compute the node labeled (&)<\/code>, the nodes (^)<\/code> and (3)<\/code> must be computed first.
\n        It’s a dependency graph<\/a>.\n        <\/p>\n
Ordering<\/h3>\n
The first step of code generation is to take the IR and create a
\n        total order<\/a>
\n        out of its nodes, positioning each node to occur after its dependencies.
\n        This is akin to putting each node on a number line such that every edge points in the same direction (downwards in the diagram).<\/p>\n
        <\/p>\n
The generated assembly code will follow this order.<\/p>\n
How does one find this order?<\/h4>\n
It’s easy to do using a topological sort<\/a>,
\n        but there’s a problem: DAGs can have multiple valid orderings, and some will generate better code than others.<\/p>\n
To find a good ordering (one which generates efficient code),
\n        the topological sorting algorithm is still used, but it can be modified using a few heuristics.
\n        First, “fake” edges can be added to the graph to constrain nodes to occur after other nodes.
\n        Second, a greedy algorithm can be used to influence the traversal order of the topological sort.
\n        In my compiler, I prioritize nodes which form the
\n        longest path<\/a> through the graph,
\n        which produces an ordering that has small
\n        live ranges<\/a>,
\n        resulting in less register pressure and stores.\n        <\/p>\n
        
\n        
Here’s an actual DAG from my compiler.<\/sup><\/p>\n
\n
Basic Block Instruction Selection – Part 1: Animation<\/h3>\n
With the IR prepared, now it’s time to generate some assembly code.
\n        I mentioned earlier that my algorithm was based on an animation system,
\n        and although that sounds weird and unrelated, it will be easier for me
\n        to explain the animation system first and then extend it to work like my compiler.<\/p>\n
The animation I’m talking about was for a NES game.
\n        On that system, animation can be done by loading a new tileset into video memory each frame,
\n        overwriting the previous frame’s tileset.\n        <\/p>\n
        <\/p>\n
Most games accomplish this using special hardware on the cartridge called a mapper,
\n        which lets the system page a tileset into video memory quickly.
\n        But in my case, I was making a game that wasn’t going to use that piece of hardware.
\n        Instead, I had to copy the bytes using the CPU as a middle-man.\n        <\/p>\n
The obvious way to copy bytes is with a loop (think “memcpy” from C),
\n        but this turned out to be too slow.
\n        For each iteration, too much time was being spent incrementing, then comparing,
\n        then branching back to the loop.<\/p>\n
The only way I could see it working was if I unrolled the loop \u2014 not once \u2014 but fully.
\n        For example, if I wanted to copy the byte sequence (10, 20, 30) to video memory, I could write assembly code like this:<\/p>\n
\nlda #20      ; Load constant: 20\nsta PPUDATA  ; Upload to video RAM\n\nlda #30      ; Load constant: 30\nsta PPUDATA  ; Upload to video RAM\n\nlda #40      ; Load constant: 40\nsta PPUDATA  ; Upload to video RAM<\/pre>\n
In other words, I was writing code like a noob who quit programming class before learning what a for-loop was.
\n        But it was fast, and that’s what mattered.<\/p>\n
Rather than writing these sequences by hand, it was clear I should automate it.
\n        A naive approach would be to write a script which generates one load and one store per uploaded byte,
\n        but it’s possible to do better.
\n        As registers preserve their values, a sequence like (1, 8, 1, 8, 1, 8) requires only two loads:<\/p>\n
\nldx #1      ; Load register X\nlda #8      ; Load register A\nstx PPUDATA ; Upload register X to video RAM\nsta PPUDATA ; Upload register A to video RAM\nstx PPUDATA\nsta PPUDATA\nstx PPUDATA\nsta PPUDATA<\/pre>\n
How does one determine these loads optimally?<\/b><\/p>\n
To keep things simple, I’ll first explain how to solve this for a CPU with one register,
\n        then expand to a CPU with three.<\/p>\n
For a CPU with one register, the algorithm boils down to finding redundant loads and eliding them.
\n        By redundant load, I mean a load which has no effect, like the second load below:<\/p>\n
\nlda #10\nsta PPUDATA\nlda #10       \/\/ redundant\nsta PPUDATA<\/pre>\n
Finding and eliding redundant loads is easy to do; just keep track of the previously loaded value.
\n        The pseudocode below does just that, optimally:<\/p>\n
\nprev = -1\n\nfor each byte to upload:\n    if prev != byte:\n        emit_load(byte)\n        prev = byte\n\n    emit_store()<\/pre>\n
This idea can almost<\/i> be extended to use three registers
\n        by using three “prev” variables instead of one.
\n        You might approach it using a struct or record type to keep things clean:<\/p>\n
\nstruct cpu_state\n{\n    int a\n    int x\n    int y\n}<\/pre>\n
Unfortunately, there’s a problem.
\n        Although we can keep track of each register this and elide stores,
\n        it’s not clear how we should handle loads.
\n        Given a value not found in any register, which register should load it?\n        <\/p>\n
We can make these decisions optimally by generating assembly code for every possible combination of loads (brute force)
\n        and only keeping the best one, but this quickly becomes infeasible.
\n        For each byte that needs loading, there are three choices possible.
\n        The number of combinations will grow at an exponential rate.<\/p>\n
        
\n        
Diagram of the brute-force search tree.<\/sup><\/p>\n
Luckily, this brute-force approach is still usable if a trick is used.
\n        It’s possible to prune most combinations, shrinking the size of the search space.<\/b><\/p>\n
If two pieces of assembly code have been generated, and both have the same observable side effect,
\n        the higher costing one can be pruned.
\n        By side effects, I mean that both upload the same byte sequence
\n        and finish with identical register states.
\n        For example, these two pieces of code are equivalent:\n        <\/p>\n
\nlda #1\nsta PPUDATA\nldx #2\nstx PPUDATA\nldy #3\nsty PPUDATA\nsta PPUDATA\n<\/pre>\n
\nldy #1\nsty PPUDATA\nldx #2\nstx PPUDATA\nldy #3\nsty PPUDATA\nlda #1\nsta PPUDATA\n<\/pre>\n
Both upload the sequence (1, 2, 3, 1), and both leave the registers at (A = 1, X = 2, Y = 3).
\nThe second one requires an extra load though, so it can be pruned.<\/p>\n
Keep in mind that this works for partial snippets of code too.
\nInstead generating entire code sequences and comparing them,
\nit’s possible to generate the code instruction-by-instruction and compare at each step.<\/p>\n
To implement this, the algorithm will handle the combinations in a breadth-first fashion.
\nIt will first generate all the combinations for the first byte and prune some,
\nthen it will generate all the combinations for the second byte and prune some, and so on.
\nThe pruning is done by storing the results in a hash table, indexed by each combination’s “cpu_state”
\n(the struct introduced earlier).<\/p>\n
For better performance, an additional method of pruning will be used.
\nIf we keep track of the current best combination at each iteration step,
\nwe can prune other combinations that are slower by three or more loads.
\nThis preserves optimality of the final result, as three loads is enough to convert from any “cpu_state” to another.\n<\/p>\n
Putting all this together, the algorithm to elide loads in a 3-register CPU becomes:<\/p>\n
\nprev_hash_map.clear()\n\nfor each byte to upload:\n    next_lowest_cost = INFINITY\n    next_hash_map.clear()\n\n    for each combination in prev_hash_map:\n        if combination.cost >= prev_lowest_cost + 3:   \/\/ Second method of pruning\n            continue\n\n        for each register (A, X, Y):\n            new_combination = combination\n            if new_combination.cpu_state.register != byte:\n                new_combination.code.append_load()\n                new_combination.cost += 1\n                new_combination.cpu_state.register = byte\n\n            if combination.cost < next_lowest_cost:\n                next_lowest_cost = combination.cost\n\n            next_hash_map.insert(new_combination)\n            if next_hash_map already had this cpu_state:  \/\/ First method of pruning\n                Keep the lowest-costing one\n\n    swap(next_hash_map, prev_hash_map)\n    prev_lowest_cost = next_lowest_cost<\/pre>\n
(If you want to see actual code, I've put a C++ implementation
\nhere<\/a>
\nand here<\/a>.)<\/p>\n
        
\n        
I converted the Cowboy Bebop intro to a NES ROM using this animation process.
\n        The GIF runs at a lower framerate.<\/sup><\/p>\n
\n
Basic Block Instruction Selection - Part 2: The Compiler<\/h3>\n
Alright, alright. . .  we can generate code for animations \u2014 So what?
\n        This is an article about compilers, right?<\/p>\n
\n        Well, consider this: Instead of processing a sequence of bytes with this algorithm,
\n            let's process the sequence of IR operations created earlier.<\/b><\/p>\n
Here's the ordered sequence of IR operations, from earlier.
\n        I've added variable names (Q, R, S, T) as placeholders for each node:<\/p>\n
\nQ = call fn\nR = Q ^ 5\nS = R & 3\nT = R - S\nreturn T<\/pre>\n
Like we did for the sequence of bytes, we can generate combinations per operation and prune the worst ones,
\n        but there are two big differences:<\/p>\n
    \n
  1. Different IR operations generate different assembly instructions (not just loads).<\/li>\n
  2. The \"cpu_state\" struct will also track variable names.<\/li>\n<\/ol>\n
    Putting this into practice, I'll show how the algorithm handles the ordered IR.
    \n        The algorithm starts by generating combinations for the first operation: \"call fn\"<\/b>,
    \n        which there is only one:<\/p>\n
    \n; call fn:\njsr fn   ; Call the function\nsta Q    ; Store the result into variable Q\n         ; cpu_state is now (A = Q, X = ?, Y = ?)<\/pre>\n
    After that, it will generate the combinations for the XOR operation (^)<\/b>.
    \n        There's a single assembly instruction which does this: \"EOR\",
    \n        but since XOR is commutative, two code combinations exist:\n        <\/p>\n
    ; call fn:\njsr fn   ; Call the function\nsta Q    ; Store the result into variable Q\n         ; cpu_state is now (A = Q, X = ?, Y = ?)\n; xor:\nlda #5 ; Load 5 into register A\neor Q  ; XOR register A with variable Q\nsta R  ; Store the result into variable R\n       ; cpu_state is (A = R, X = ?, Y = ?)<\/pre>\n
    ; call fn:\njsr fn   ; Call the function\nsta Q    ; Store the result into variable Q\n         ; cpu_state is now (A = Q, X = ?, Y = ?)\n; xor:\neor #5 ; XOR register A with variable 5\nsta R  ; Store the result into variable R\n       ; cpu_state is (A = R, X = ?, Y = ?)<\/pre>\n
    The second combination does not need a load instruction for the Q variable, as it's already loaded in the register.
    \n        Since both of these code sequences have the same side effect, the first combination will be pruned.<\/p>\n
    Now, for the AND operation (&)<\/b>.
    \n        While there is an AND instruction, there's also an illegal instruction called SAX,
    \n        which perform a bitwise AND of register A with register X and stores the result.
    \n        This results in four combinations, so I'll only show the two that won't get pruned:\n        <\/p>\n
    ; call fn:\njsr fn   ; Call the function\nsta Q    ; Store the result into variable Q\n         ; cpu_state is now (A = Q, X = ?, Y = ?)\n; xor:\neor #5 ; XOR register A with variable 5\nsta R  ; Store the result into variable R\n       ; cpu_state is (A = R, X = ?, Y = ?)\n; and:\nand #3   ; AND register A with 5\nsta S    ; Store the result into variable S\n         ; cpu_state is (A = S, X = ?, Y = ?)<\/pre>\n
    ; call fn:\njsr fn   ; Call the function\nsta Q    ; Store the result into variable Q\n         ; cpu_state is now (A = Q, X = ?, Y = ?)\n; xor:\neor #5 ; XOR register A with variable 5\nsta R  ; Store the result into variable R\n       ; cpu_state is (A = R, X = ?, Y = ?)\n; and:\nldx #3   ; Load 3 into register X\nsax S    ; Store the AND of registers A and X into variable S\n         ; cpu_state is (A = R, X = 3, Y = ?)<\/pre>\n
    For the subtraction operation (-)<\/b>, the SBC instruction will be used following a SEC instruction to set the carry flag.
    \n        As subtraction isn't commutative, there's only one way to do this, but since the previous operation generated two combinations,
    \n        this operation will result in two combinations too.\n        <\/p>\n
    ; call fn:\njsr fn   ; Call the function\nsta Q    ; Store the result into variable Q\n         ; cpu_state is now (A = Q, X = ?, Y = ?)\n; xor:\neor #5 ; XOR register A with variable 5\nsta R  ; Store the result into variable R\n       ; cpu_state is (A = R, X = ?, Y = ?)\n; and:\nand #3   ; AND register A with 5\nsta S    ; Store the result into variable S\n         ; cpu_state is (A = S, X = ?, Y = ?)\n; subtract:\nlda R    ; Load R into register A\nsec\nsbc S    ; Subtract S from register A\nsta T    ; Store the result into variable T\n         ; cpu_state is (A = T, X = ?, Y = ?)<\/pre>\n
    ; call fn:\njsr fn   ; Call the function\nsta Q    ; Store the result into variable Q\n         ; cpu_state is now (A = Q, X = ?, Y = ?)\n; xor:\neor #5 ; XOR register A with variable 5\nsta R  ; Store the result into variable R\n       ; cpu_state is (A = R, X = ?, Y = ?)\n; and:\nldx #3   ; Load 3 into register X\nsax S    ; Store the AND of registers A and X into variable S\n         ; cpu_state is (A = R, X = 3, Y = ?)\n; subtract:\nsec\nsbc S    ; Subtract S from register A\nsta T    ; Store the result into variable T\n         ; cpu_state is (A = T, X = 3, Y = ?)<\/pre>\n
    Lastly, the return operation<\/b>, which is implemented with a single RTS instruction.
    \n        This one is so simple, I'm not going to illustrate it with a code example.
    \n        Simply imagine a \"RTS\" appended onto the end of the previous two combinations.\n        <\/p>\n
    Finishing up<\/h4>\n
    Once the combinations have been run, the algorithm selects the lowest-costing one.
    \n        In this case, it's the one that uses a SAX instruction instead of AND,
    \n        as it requires one less instruction.<\/p>\n
    The resulting selection looks like this, but we're not done yet:<\/p>\n
    \njsr fn\nsta Q\neor #5\nsta R\nldx #3\nsax S\nsec\nsbc S\nsta T\nrts<\/pre>\n
    The issue is, most of these store instructions are unecessary, as nothing will ever load them.
    \n        To fix this, an extra pass is run which identifies stores that are never loaded.
    \n        This results in the final code:<\/p>\n
    \njsr fn\neor #5\nldx #3\nsax S\nsec\nsbc S\nrts<\/pre>\n
    In the actual compiler, the code generator is a bit smarter about stores,
    \n        and can usually estimate if they're needed or not while generating the combinations.
    \n        This is important, as the presence of a store influences a combination's cost.\n        <\/p>\n
    Basic Block Instruction Selection - Part 3: Continuations<\/h3>\n
    As shown, compiling an IR operation boils down to generating a bunch of combinations.
    \n        However, if you were write code to translate IR operations into assembly combinations,
    \n        you'd find it to be a repetive, menial coding task.\n        <\/p>\n
    The issue relates to the number of combinations.
    \n        For each IR operation, there will be a few valid instructions that can implement it,
    \n        and each of those instructions will have its own variants, resulting in more combinations.
    \n        Multiply these together (and double it for communicative operations),
    \n        and you'll end up with a lot of combinations per IR operation.<\/p>\n
            
    \n        
    Our combinations have combinations!<\/sub><\/p>\n
    It would be nice to abstract these details away and create building blocks for
    \n        implementing operations. Luckily, I found a solution by using continuations.<\/p>\n
    Each step (or \"building block\") will be implemented as a function written in
    \n        continuation-passing style<\/a>.
    \n        Instead of returning, these functions will call their continuations with each instruction they want to generate a combination for.
    \n        For example, to generate three combinations, the continuation will be called three times with three different instructions.\n        <\/p>\n
    Here's how a function for loading a value in register A might look, in pseudocode:<\/p>\n
    \nload_A(desired_value, cpu_state, continuation)\n    if cpu_state.A == desired_value\n        continuation(cpu_state, NOP)\n    else if cpu_state.X == desired_value\n        continuation(cpu_state, TXA)\n    else if cpu_state.Y == desired_value\n        continuation(cpu_state, TYA)\n    else\n        continuation(cpu_state, LDA)\n        continuation(cpu_state, LAX)<\/pre>\n
    \n        If the value is already present in one of the registers: either nothing happens (NOP), or a transfer between registers occurs (TXA, TYA).
    \n        Otherwise, two combinations will occur: one using the LDA instruction,
    \n        and another using the LAX instruction.\n        <\/p>\n
    The point of writing functions like this is that they can be composed.
    \n        With a bit of plumbing, it's possible to end up with a
    \n            domain-specific language<\/a> that resembles:<\/p>\n
    \ncompose(load_A(L), load_X(R), instruction(SAX))<\/pre>\n
    A single line like this can cover 50 different assembly sequences, all handling different combinations of instructions and addressing modes.
    \n        It's much easier to write than trying to enumerate all the possibilities by hand.<\/p>\n
    Control Flow - Part 1: Basics<\/h3>\n
    Although the algorithm I've described is tied to basic blocks, it can handle control flow (branches, loops, etc) too.
    \n        Branch operations are not special \u2014 they generate assembly combinations like any other.\n        <\/p>\n
    For example, take a look at this control flow graph (the rectangles are basic blocks):<\/p>\n
            <\/p>\n
    Each basic block in this graph will be assigned a unique label name (L1, L2, L3, etc).<\/p>\n
    Now we'll generate the code for each basic block separately<\/i>, implementing control flow as instructions involving these labels.
    \n        Once every basic block has its code generated, we can concatenate the results:<\/p>\n
    \nL1:\n    ; (More code would go here)\n    beq L1 ; Branch instruction\n    bne L2\nL2:\n    ; (More code would go here)\n    jmp L4 ; Jump instruction\nL3:\n    ; (More code would go here)\n    beq L1\n    bne L4\nL4:\n    ; (More code would go here)\n    rts<\/pre>\n
    With this implemented, the compiler now works.
    \n        It can generate executables!<\/p>\n
    Control Flow - Part 2: Optimizations<\/h3>\n
    The process above works, but does not produce good code across basic block boundaries.
    \n        The issue stems from compiling basic blocks separately without sharing knowledge of the register states between them.
    \n        If one basic block needs a value from a previous block, it will emit a load instruction
    \n        even if it's redundant.<\/p>\n
    For example, this is how a loop would look:<\/p>\n
    \nL0:\n    ldx #0 ; Load register X with 0\n    stx I  ; Store variable I\nL1:\n    ldx I  ; Load variable I\n    inx    ; Increment register X\n    stx I  ; Store variable I\n    bne L1 ; Branch if register X is not zero<\/pre>\n
    But this is how a loop should<\/i> look:<\/p>\n
    \n    ldx #0 ; Load register X with 0\nL1:\n    inx    ; Increment register X\n    bne L1 ; Branch if register X is not zero<\/pre>\n
    The second loop lacks redundant loads.<\/p>\n
    To solve this, the final \"cpu_state\" from basic blocks need to be shared.
    \n        This can be done by passing each basic block's result into its successors as input.\n        <\/p>\n
            
    \n        
    Old method: Generate code for each basic block individually.<\/sup><\/p>\n
            
    \n        
    New method: Use the output states from generating a basic block as the input states to the next.<\/sup><\/p>\n
    This is an iterative process where each node can be processed multiple times.
    \n        When a node is processed, it will trigger its successors to be processed next passing outputs as inputs. This will repeat until a fixed point is reached.\n        <\/p>\n
    Going back to the loop example, initial iterations will produce inefficient code,
    \n        but later iterations will propagate the register states through the loop from (L3) to (L1).
    \n        Once variable \"I\" appears pre-loaded in register X, optimal code will follow.<\/p>\n
    To expedite this process, it's beneficial to only pass the lowest-costing results along
    \n        and get stricter each iteration.
    \n        This resembles     simulated annealing<\/a>.\n        <\/p>\n
    Control Flow - Part 3: Some Loads Required<\/h3>\n
    Although the method above generates improved code,
    \n        it's no longer possible to get a working program by concatenating the lowest-costing combinations.
    \n        The issue is, each code combination now expects some specific register values as inputs,
    \n        but the output of one combination may not correspond to the input of another.
    \n        You could get nonsensical results like initializing a loop variable using the Y register,
    \n        but incrementing using the X register:<\/p>\n
    \n; This code is incorrectly compiled!\nL0:\n    ldy #0   ; Output Y as the iteration count\n             ; NOTE: A sty instruction was removed by the \"remove unused stores\" pass.\nL1:\n             ; Input X as the iteration count\n    inx\n    bne L1<\/pre>\n
    To fix this, the input states of each basic block must match the output states of their predecessors.
    \n        If there is a discrepency, a load can be inserted to correct it.<\/p>\n
    By inserting loads, the code becomes:<\/p>\n
    \nL0:\n    ldy #0\n    sty I   ; This store is no longer removed.\nL1_entry:\n    ldx I   ; Inserted load\nL1:\n    inx\n    bne L1<\/pre>\n
    Which works, but isn't ideal.<\/p>\n
    Control Flow - Part 4: PBQP<\/h3>\n
    The woes above are caused by selecting only the lowest-costing combinations per basic block,
    \n        without taking into consideration the compatability between input\/output states.
    \n        Ideally, we'd factor in the cost of inserted loads.<\/p>\n
    Doing so is an optimization problem, and one which closely maps to the
    \n            Partitioned Boolean Quadratic Problem<\/a> (PBQP).
    \n        If we can solve a PBQP problem, we can select optimal combinations for our basic blocks.<\/p>\n
    Unfortunately, not much has been written on PBQP, and what does exist is hard to read for most:<\/p>\n
            
    \n        
    Image Source<\/a><\/sup><\/p>\n
    My advice is that instead of struggling over equations, it's easier to learn PBQP by thinking visually, in terms of graphs.\n        <\/p>\n
    Imagine a graph where each node has a finite list of choices,
    \n        and each of those choices has a cost.
    \n        The goal PBQP is to pick one choice for each node, minimizing the total cost.
    \n        The catch is, an additional cost is incurred for every edge in the graph
    \n        based on the choices made at the edge's vertices.\n        <\/p>\n
    The picture below illustrates such a graph.
    \n        Each node has a choice of two colors, and those colors have a cost next to them.
    \n        When selecting two colors, the cost of the edge must be paid as well.
    \n        This is done by looking up the cost in a table unique to each edge, using the two selected colors as keys.\n        <\/p>\n
            <\/p>\n
    Below, I've made some choices, and have crossed out everything I didn't choose.
    \n        The total cost is the sum of the visible numbers, which is 3 + 1 + 7 + 3 + 6 + 7 = 27.
    \n        The goal of PBQP is to find choices which minimizes this sum.<\/p>\n
            <\/p>\n
    A fast algorithm<\/a>
    \n        exists to solve PBQP problems near-optimally.
    \n        The algorithm works on the graph, reducing and combining nodes until none remain.
    \n        At the end, the algorithm works backwards, using the steps it took to decide which choices to make.<\/p>\n
    Going back to the compiler, the problem I was describing fits perfectly into this visualization:<\/p>\n