archives

Brief Question on extension to ANF IR

My goal in extending an ANF-style IR has three related parts.

  1. Segregate conditional tests from boolean expressions with results bound to variables (or temporaries). Conditional tests always have explicit test operators.
  2. Segregate conditional branch continuations from other expressions
  3. Avoid "code explosion" in expansion of short circuiting boolean test expressions.

My premise is that this extended IR is trivial to produce during normal ANF conversion and that the extended IR is more compact and easier/faster to further analyze.

The following three code snippets illustrate the "test/branch" extensions I'm exploring.


// Input source.
if a < b or big-test(a) then
  do-A(a)
else
  do-B(b)

// "Traditional" ANF-style IR 
// I hope I got the ANF rules right here.
let _t1 = a < b in
let _t2 = if not _t1 then 
            let _t3 = big-test(a) in
            if _t3 then true
            else false;
          else true
in if _t2 then
      do-A(a)
   else do-B(a)
       
// ANF-style IR extended with test/branch constructs
// %lbls are if/else branch continuations and targets for %jmp
// %ift handles some set of primitive tests in the IR
// %tr tests whether a variable warrants positive branching
%lbls _lbl1 = do-A(a);
      _lbl2 = do-B(b)
in %ift a < b then %jmp _lbl1  //  '<' is a primitive test here
   else let _t2 = big-test(a) in
        %ift %tr _t2 then %jmp _lbl1
        else %jmp _lbl2

My questions are (1) have others made similar extensions to ANF-style IR's in the past and (2) or am I just on the wrong track.

Many thanks in advance!

- Scott