Refactor the sway-core/src/asm_generation directory.

[otrho]

When switching from AST -> ASM to AST -> IR -> ASM all the new IR -> ASM code went in from_ir.rs to keep it simple and contained.

But the old AST -> ASM code has been removed now and from_ir.rs is ~2500 lines and should be broken up and refactored. All the tests called from there and hosted in sway-core/tests/ir_to_asm still need to be moved over to sway/test/src/ir_generation or somewhere similar, and switched to use FileCheck.

Treating this as a bit of a parent issue, here's some sub-issues:

• Split asm_builder up further.
• Far jumps and the data section:
  • Investigate issue with data section addressing limits. #3161
  • Relocate code to avoid far jumps in ASMgen. #3347
  • Remove addresses from the data section. #3346

[otrho]

I took a birds eye view of what's in asm_generation and the pipeline from IR to ASM and took some notes. Might be useful in a refactor. Of note is the duplication of opcodes between VirtualOp and AllocatedOp which is nice for type safety but does involve a lot of duplication.

* ir -> asm:
  * from_ir.rs:
    * compile_ir_to_asm():
      * compile_module_to_asm()         sway_ir::Context -> AbstractInstructionSet
      * remove_unnecessary_jumps()      AbstractInstructionSet -> JumpOptimizedAsmSet
      * allocate_registers()            JumpOptimizedAsmSet -> RegisterAllocatedAsmSet
        * realize_labels()              AbstractInstructionSet -> RealizedAbstractInstructionSet
        * allocate_registers()          RealizedAbstractInstructionSet -> InstructionSet via register allocator
      * optimize()                      InstructionSet -> FinalizedAsm

* JumpOptimizedAsmSet                   - wrapper around AbstractInstructionSet
* RegisterAllocatedAsmSet               - wrapper around InstructionSet
* FinalizedAsm                          - wrapper around InstructionSet

* AbstractInstructionSet                - collection of Op
* RealizedAbstractInstructionSet        - collection of RealizedOp
* InstructionSet                        - collection of AllocatedOp

* Op                                    - Either<VirtualOp, OrganizationalOp>
  * VirtualOp                           - giant list of opcodes
  * OrganizationalOp                    - tiny list of opcodes (label, jumps, data section placeholder)
* AllocatedOp                           - giant list of opcodes
* RealizedOp                            - VirtualOp

* VirtualOp:
  * Opcodes with VirtualRegisters and VirtualImmediates
* AllocatedOp:
  * Opcodes with AllocatedRegisters and AllocatedImmediates

[otrho]

This has changed a bit with #2843 but is still desperately needed.

[otrho]

Here are some personal notes I took down at some point which might as well go here. They apply to #2906 too.

• Stages in pipeline:

  • IR to virtual ops:
    • Virtual ops should be like SSA. Prevent ability to change a destination register.
    • Inlining ASM blocks correctly.
  • Optimisations on Virtual:
    • Proper data flow analysis:
      • Redundant moves. (a -> b, b -> c == a -> c)
      • Redundant copy back. (a -> b, b -> a)
      • DCE. (a -> b, b never used)
      • Incremental adds. (a * 2 + 1 -> b, a * 2 + 2 -> c == a * 2 + 1 ->b, b + 1 -> c)
    • Other DCE. (NOOPs?)
    • Control flow optimisation:
      • Reducing multiple jumps by negating conditions.
      • Eliminate jumps to jumps. Just jump to second destination.
    • CSE. Maybe some ops are repeated in different CFG arms. Then jump to jumps are made more
      likely too.
    • Redundant arith - add x 0, mul x 1.
    • Inefficient arith - mul x 2 == add x x -- ^need gas costs^. Shifts for mul x 2, etc.
    • Other peephole?
    • Must be ware of control flow for these! Should pretty much be restricted to within basic
      blocks.
  • Virtual to Allocated:
    • Register allocator with spills.
    • PUSHA/POPA replacement.
  • Optimisations on Allocated:
    • Undoing redundancies of setting up call-frame.
    • Remove redundancies of PUSHA/POPA for sequential calls - no need to pop after first call to
      just push again for second call. This would require them to be performed by the caller, which
      should be possible -- need to ask the function which regs it uses to save them.
  • Lay out data section(s) - Part I:
    • Optimise for small values. Remove zero, one, vals which fit in MOVI.
    • Make sure no redundant vals.
  • Allocated to Realised:
    • Gathering label offsets.
    • Rewriting control flow:
      • Inject labels into data section. They must go in the first data section.
  • Lay out data section(s) - Part II:
    • Split into multiple sections.
  • Realised to Finalised:
    • Replace LW data and LW label with mulitple data sections.
    • MCPI etc?
  • Finalised to Bytecode.

• Registers are:

  • Virtual (infinite, SSA)
  • Allocated (finite, VM)
  • Should share a trait, minimise redundancy.

• Ops are:

  • Virtual:
    • VM.
    • Control flow.
    • Load data/label.
    • Pusha/popa.
  • Allocated:
    • VM.
    • Control flow.
    • Load data/label.
  • Realised:
    • VM.
    • Load data/label.
  • Finalized:
    • VM.
  • Should share a trait, minimise redundancy. Every op is an enum. Each variant (Regular,
    ControlFlow, etc) implements traits. So VirtualOp, AllocatedOp, etc. should be able to
    derive the trait, each variant provides it, so it works..?