superoptimization

Usage

let run () = 
  let prog0 = [IMul("rax", "rax", 2)] in (* or other programs *)
  let regs = ["rax"] in
  let _,_, visited = run_equiv_optimizer ~iterations:10000 prog0 regs in

Constant fold

let prog0 = [Load("rax", 1); IAdd("rax", "rax", 1); IMul("rax", "rax", 2)]

Original program: li rax,1; addi rax,rax,1; muli rax,rax,2

Top 5 visited programs:

• Score 2.06250 -- result: 4 --- li rax,4
• Score 2.03125 -- result: 4 --- li rax,4; mov rax,rax
• Score 2.01562 -- result: 4 --- add rax,rax,rax; add rax,rax,rax; li rax,4
• Score 2.00781 -- result: 4 --- li rax,1; addi rax,rax,1; mov rax,rax; add rax,rax,rax
• Score 2.00391 -- result: 4 --- li rax,1; addi rax,rax,1; mov rax,rax; add rax,rax,rax; mov rax,rax

Strength reduction

let prog0 = [IMul("rax", "rax", 2)] 

Original program: muli rax,rax,2

Top 5 visited programs:

• Score 2.50000 -- result: 0 --- add rax,rax,rax
• Score 2.25000 -- result: 0 --- add rax,rax,rax; mov rax,rax
• Score 2.12500 -- result: 0 --- add rax,rax,rax; mov rax,rax; mov rax,rax
• Score 2.06250 -- result: 0 --- muli rax,rax,2
• Score 2.03125 -- result: 0 --- add rax,rax,rax; muli rax,rax,1

Dead code elimination

  let prog0 = [Load("rax", 5); Mov("rax", "rax"); IAdd("rax", "rax", 0)] in

Original program: li rax,5; mov rax,rax; addi rax,rax,0

Top 5 visited programs:

• Score 2.06250 -- result: 5 --- li rax,5
• Score 2.03125 -- result: 5 --- mov rax,rax; li rax,5
• Score 2.01562 -- result: 5 --- li rax,5; mov rax,rax; addi rax,rax,0
• Score 2.00781 -- result: 5 --- li rax,5; mov rax,rax; addi rax,rax,0; mov rax,rax
• Score 2.00391 -- result: 5 --- mul rax,rax,rax; li rax,5