Triton: Preserving Expected Block Order

[mariari]

as seen in #16, there is no easy way to jump to a label without affecting the call stack. This demands that abstractions like loop or if after their termination, will have to have their exit code labels be placed after the label they were called from.

(def nonsense-example
  (tagbody 
   :nonesense-entry-point
     (dup 0)
     (if (begin (push 2) add)
         (begin (push 3) add))
   ;; In real code, this is generated by if, not written in code explicitly
   :after-if 
     (push 4)
     (loop swap (push 3) add swap)
   ;; In real code, this is generated by loop, not written in code explicitly
   :after-loop
     (dup 0)
     (push 100)
     lt skiz recurse return))

This should generate code to look something like

nonsense-entry-point:
  dup0
  skiz
  call if-wraper
after-if:
  push 4
  call loop
after-loop:
  dup0
  push 100
  lt skiz recurse return

if-wraper: ...
loop: ....

where loop and if-wrapper: are filled in with their proper code. However note where after-if: and after-loop: come. Their ordering was set to be after whatever the current block at the time was!

This behavior is not trivial to implement, as we can not rely on all gotos's to get the ordering naturally like a SSA style control flow graph.

In fact, due to how ordering works, we have to make sure we move down the any labels that were created before the continues-at point to the end, as the if/loop return label may have labels that already implicitly follow it!

We therefore have to carefully remember this ordering ourselves. Thankfully I propose the following solutions:

Solution 1: Flip the Chessboard, Anything that Branches, is now an adhoc procedure!

This solution is simpler than the second solution and is more elegant, however it needs some build up.

When we say something like (loop swap (push 3) add swap), how we think of the control graph, is that it calls into some loop boiler plate with the user logic inside, then it returns back to the caller.

Thus instead of thinking of concepts like loop and if as primitives or like a normal instruction, we can think of it like a higher order procedure!

Namely, an invocation of loop or if creates a brand new procedure, with the code the user specified being inside the generated procedure.

Since these blocks always call and return they are safe to move anywhere. This completely removes any need for reordering logic.

All that needs to happen from the code standpoint is:

1. Extend labels with a notion of created procedures that we accumulate.
2. When making an abstraction which takes user code and has any branches, remember to mark it as a procedure!
   • This puts a burden upon the abstraction writer, however hopefully it should be obvious when this happens
     • Maybe if I have enough examples I can nicely abstract it away from the author...

Solution 2: Extending Tlabels with Ordering and Hashtables

We change tlabels from being just a a list of blocks, to being a record containing the following fields.

1. A current ordering
2. A hashtable mapping the keyword label of a block to the block itself.
3. A current block that we are adding instructions onto.
4. A list of the current explicit follows.
5. An enum of :front, :end, or nil. For current blocks without labels, telling them where they go in the ordering

What the 4. point does, is when we finalize the block, we will move all nodes between the current node and what follows to the end.

Thus if we have

:a :b :c :d :e

and we say :d follows :a, then the ordering list will now look like

:a :d :e :b :c

This method is slow and is O(n^2) in the number of explicit follows. However if this is found to slow down the speed of compilation, then I can implement a O(n) method by some sort of numbering.

A note about merging tlabels

An important means of combination for tlables is appending an instruction or a set of instructions to the front.

This will serve as the modified version of my existing triton:cons-instructions-to-labels

• Consing an opcode (push, call, etc.):
  1. if there is a label for the current block:
     1. Finish the block, updating/adding it to the hashtable at its label
     2. Create a new block, with the enum field set to :front
  2. If there is no label for the current block
     1. Just cons onto the current block!
• Consing a label:
  1. If there is a label for the current block
     • Finish the block, updating/adding it to the hashtable at its label
     • Create a new block, and place it's ordering to the front of the list, and set the enum to nil
  2. If there is no label for the current block
     - Add the label to the current block
     - Add the new label to the ordering, at the front or end depening on what the value of the enum is.
• Consing a block:
  1. If there is no current block
     • Then set the current block to the given block
  2. If there is no label for the current block
     • Merge the two blocks. Note if the block we are consing has a label, then simply call the logic for consing a label
  3. If there is a label for the current block
     1. Finish the block, updating/adding it to the hashtable at its label
     2. Add block, and call logic for consing a label
• Consing a tlabels:
  1. Merge the hashtables.
  2. If there is no name for the current block and the consed tlabels is not empty:
     • gensym an unique label for the current block.
  3. Finalize the current block
  4. Take the tlabels's current block as our own, along with its enum value