Tunneling: improved elimination of conditions

Previously, the elimination of useless conditions done in the 2nd pass of the tunneling
introduced some new "nop" instructions that were not eliminated.

This commit solves this issue by anticipating the elimination of conditions in the 1st pass
of the tunneling, the 2nd pass being unchanged.

In case of cycles in the CFG, the full elimination of useless conditions may require several
iterations in the 1st pass. Moreover, in the simulation proof, the measure counting the number of
eliminated steps from each node, needs to be adapted according to the modifications on the 1st pass.
Hence, this measure results from a quite complex fixpoint computation: proving its properties
would be very difficult.

This leads us to introduce an oracle, implementing the first pass and producing the expected
measure. A certified verifier directly checks that the measure provided by the oracle
satisfies the properties expected by the simulation proof.

Introducing this oracle/verifier pair has here the following advantage:
 - the proof is simpler than the original one (e.g. having a certified union-find structure
is no more necessary for this pass).
 - the oracle is very efficient, by using imperative data-structure to compute memoized
fixpoints.

At runtime, the overhead induced by the verifier computations (and the actual computation of
the measure) seems largely compensated by the gains obtained through the imperative oracle.

1 files changed, 2 insertions, 2 deletions

diff --git a/tools/compiler_expand.ml b/tools/compiler_expand.ml
index 54946366..febb0282 100644
--- a/tools/compiler_expand.ml
+++ b/tools/compiler_expand.ml
@@ -50,8 +50,8 @@ PARTIAL, Always, Require, (Some "Unused globals"), "Unusedglob"
 
 let post_rtl_passes =
 [|
-  PARTIAL, Always, Require, (Some "Register allocation"), "Allocation", (Print "LTL");
-  TOTAL, Always, Require, (Some "Branch tunneling"), "Tunneling", Noprint;
+  PARTIAL, Always, Require, (Some "Register allocation"), "Allocation", (Print "LTL 1");
+  PARTIAL, Always, Require, (Some "Branch tunneling"), "Tunneling", (Print "LTL 2");
   PARTIAL, Always, Require, (Some "CFG linearization"), "Linearize", Noprint;
   TOTAL, Always, Require, (Some "Label cleanup"), "CleanupLabels", Noprint;
   PARTIAL, (Option "debug"), Require, (Some "Debugging info for local variables"), "Debugvar", Noprint;