PNaCl: Add ExpandConstantExpr pass for converting ConstantExprs to Instructions

test/Transforms/NaCl/expand-constantexpr.ll

+; RUN: opt < %s -expand-constant-expr -S | FileCheck %s
+
+@global_var1 = global i32 123
+@global_var2 = global i32 123
+
+
+define i8* @constantexpr_bitcast() {
+  ret i8* bitcast (i32* @global_var1 to i8*)
+}
+; CHECK: @constantexpr_bitcast
+; CHECK: %expanded = bitcast i32* @global_var1 to i8*
+; CHECK: ret i8* %expanded
+
+
+define i32 @constantexpr_nested() {
+  ret i32 add (i32 ptrtoint (i32* @global_var1 to i32),
+               i32 ptrtoint (i32* @global_var2 to i32))
+}
+; CHECK: @constantexpr_nested
+; CHECK: %expanded1 = ptrtoint i32* @global_var1 to i32

[jvoung (off chromium), 2013/03/15 17:56:01]

How about testing something with further nesting, to test the recursion in the
implementation?

[Mark Seaborn, 2013/03/15 19:28:44]

We're already testing some nesting, but OK, let's test deeper nesting.

+; CHECK: %expanded2 = ptrtoint i32* @global_var2 to i32
+; CHECK: %expanded = add i32 %expanded1, %expanded2
+; CHECK: ret i32 %expanded
+
+
+define i32 @constantexpr_phi() {
+entry:
+  br label %label
+label:
+  %result = phi i32 [ ptrtoint (i32* @global_var1 to i32), %entry ]
+  ret i32 %result
+}
+; CHECK: @constantexpr_phi
+; CHECK: entry:
+; CHECK: %expanded = ptrtoint i32* @global_var1 to i32
+; CHECK: br label %label
+; CHECK: label:
+; CHECK: %result = phi i32 [ %expanded, %entry ]
+
+
+; This tests that ExpandConstantExpr correctly handles a PHI node that
+; contains the same ConstantExpr twice.
+; Using replaceAllUsesWith() is not correct on a PHI node when the
+; new instruction has to be added to an incoming block.
+define i32 @constantexpr_phi_twice(i1 %arg) {
+  br i1 %arg, label %iftrue, label %iffalse
+iftrue:
+  br label %exit
+iffalse:
+  br label %exit
+exit:
+  %result = phi i32 [ ptrtoint (i32* @global_var1 to i32), %iftrue ],
+                    [ ptrtoint (i32* @global_var1 to i32), %iffalse ]
+  ret i32 %result
+}
+; CHECK: @constantexpr_phi_twice
+; CHECK: iftrue:
+; CHECK: %expanded = ptrtoint i32* @global_var1 to i32
+; CHECK: iffalse:
+; CHECK: %expanded1 = ptrtoint i32* @global_var1 to i32
+; CHECK: exit:
+
+
+define i32 @constantexpr_phi_multiple_entry(i1 %arg) {
+entry:
+  br i1 %arg, label %done, label %done
+done:
+  %result = phi i32 [ ptrtoint (i32* @global_var1 to i32), %entry ],

[jvoung (off chromium), 2013/03/15 17:56:01]

Just curious: for an example which uses "br i1, ..., ...", won't a simple code
generator still have the property you described in the bug:

" A simple code generator will produce code that inefficiently evaluates
<constantexpr> even if the iftrue branch is not taken, e.g.:

     <evaluate <constantexpr> and store in %x>
     <test %cmp>
     b<cond> iftrue
     b iffalse

"

Since the const expr pushed back?

[jvoung (off chromium), 2013/03/15 19:17:26]

Err, n/m it only looks that way for this example but for normal if-else + phis,
the then-else branches are distinct from the actual if.

[Mark Seaborn, 2013/03/15 19:28:44]

This pass does generate the same evaluation ordering that a naive code generator
would produce as above, yes.

But the difference is that an offline IR-to-IR pass can improve the code that
ExpandConstantExpr produces by reordering instructions -- and it has all the
time in the world to do so, unlike the PNaCl translator.

For example, consider the input:

foo:
  ...
  br i1 %cond, label %loop, label %done
loop:
  %x = phi i8* [ some_constexpr (@global), %foo ] [ ... ]


ExpandConstantExpr will expand this to the naive code:

foo:
  ...
  %expanded = some_constexpr (@global)  ; Might be computed unnecessarily
  br i1 %cond, label %loop, label %done
loop:
  %x = phi i8* [ %expanded, %foo ] [ ... ]


But this could be optimised by splitting the edge:

foo:
  ...
  br i1 %cond, label %loop, label %done
loop.from_foo:
  %expanded = some_constexpr (@global)
  br %loop
loop:
  %x = phi i8* [ %expanded, %loop.from_foo ] [ ... ]

There's probably an LLVM pass somewhere that will do this.  I'm not going to try
to optimise this at the moment -- ABI stability is the priority.

+                    [ ptrtoint (i32* @global_var1 to i32), %entry ]
+  ret i32 %result
+}
+; CHECK: @constantexpr_phi_multiple_entry
+; CHECK: entry:
+; CHECK: %expanded = ptrtoint i32* @global_var1 to i32
+; CHECK: br i1 %arg, label %done, label %done
+; CHECK: done:
+; CHECK: %result = phi i32 [ %expanded, %entry ], [ %expanded, %entry ]
+
+
+
+declare void @external_func()
+declare void @personality_func()
+
+define void @test_landingpad() {
+  invoke void @external_func() to label %ok unwind label %onerror
+ok:
+  ret void
+onerror:
+  %lp = landingpad i32
+      personality i8* bitcast (void ()* @personality_func to i8*)
+      catch i32* null
+  ret void
+}
+; landingpad can only accept a ConstantExpr, so this should remain
+; unmodified.
+; CHECK: @test_landingpad
+; CHECK: personality i8* bitcast (void ()* @personality_func to i8*)