Home » forums » LtU Forum

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

By scottmcl at 2012-03-25 15:46 | LtU Forum | previous forum topic | next forum topic | other blogs | 3412 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Whoops, a little mistake

Sorry, the right hand side for the _t2 binding is wrong in the middle "traditional ANF" pseudo-code. But it doesn't affect the example or question, I don't think. It should likely read something more akin to this, depending on what simplifications the transformation logic may make.

let _t1 = a < b in
let _t2 = if _t1 then true else 
          let _t3 = big-test(a) 
          in _t3 // or maybe "if _t3 then true else false"

Anyway, the point is the need for _t2 in the "traditional ANF" pseudo-code to avoid any duplication of the "do-A(a)" and "do-B(b)" expressions - i.e., potential "code explosion".

The "extended ANF" achieves this goal by adding a construct that segregates conditional target expressions, tests and (now maybe multiple) target branches explicit - in principle also simplifying downstream analysis and transformations of the IR.

Any general wisdom or papers, source, system docs that might use any similar "ANF extension"? Thanks again for any sagacious counsel!

- Scott

By scottmcl at Mon, 2012-03-26 11:56 | login or register to post comments