Optimize code layout

When detecting a superblock that spans a loop, lay out the code in such
a way that not looping can be handled via fall-through, thus saving an
extra instruction on the suspected hot-path.

1 files changed, 14 insertions, 5 deletions

diff --git a/backend/Linearizeaux.ml b/backend/Linearizeaux.ml
index 5914f6a3..e89db024 100644
--- a/backend/Linearizeaux.ml
+++ b/backend/Linearizeaux.ml
@@ -113,7 +113,7 @@ let flatten_blocks blks =
   let cmp_minpc (mpc1, _) (mpc2, _) =
     if mpc1 = mpc2 then 0 else if mpc1 > mpc2 then -1 else 1
   in
-    List.flatten (List.map snd (List.sort cmp_minpc blks))
+    List.flatten (List.map snd (List.stable_sort cmp_minpc (List.rev blks)))
 
 (* Build the enumeration *)
 
@@ -139,11 +139,16 @@ let super_blocks f joins =
        pc is the function entry point
           or a join point
           or the successor of a conditional test *)
-  let rec start_block pc =
+  let rec start_block ?minpc pc =
+    let minpc =
+      match minpc with
+      | None -> pc
+      | Some minpc -> minpc
+    in
     let npc = P.to_int pc in
     if not (IntSet.mem npc !visited) then begin
       visited := IntSet.add npc !visited;
-      in_block [] npc pc
+      in_block [] (P.to_int minpc) pc
     end
   (* in_block: add pc to block and check successors *)
   and in_block blk minpc pc =
@@ -159,10 +164,14 @@ let super_blocks f joins =
             match pred with
             | None -> (end_block blk minpc; start_block ifso; start_block ifnot)
             | Some true -> (next_in_block blk minpc ifso; start_block ifnot)
-            | Some false -> (next_in_block blk minpc ifnot; start_block ifso)
+            | Some false ->
+              if List.mem ifnot blk then
+                (next_in_block blk minpc ifnot; start_block ~minpc:ifnot ifso)
+              else
+                (next_in_block blk minpc ifnot; start_block ifso)
           end
        | Ljumptable(arg, tbl) :: _ ->
-             end_block blk minpc; List.iter start_block tbl
+             end_block blk minpc; List.iter (start_block ?minpc:None) tbl
        | Lreturn :: _ -> end_block blk minpc
        | instr :: b' -> do_instr_list b' in
        do_instr_list b