PNaCl: Add ExpandConstantExpr pass for converting ConstantExprs to Instructions

PNaCl: Add ExpandConstantExpr pass for converting ConstantExprs to Instructions

Once this pass is enabled, it will simplify the language to reduce the
set of constructs that a PNaCl translator needs to handle as part of a
stable wire format for PNaCl.

BUG=https://code.google.com/p/nativeclient/issues/detail?id=3337
TEST=test/Transforms/NaCl/expand-constantexpr.ll

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-llvm.git;a=commit;h=bd7c1e1

[Derek Schuff, 2013-03-14 21:23:50]

On 2013/03/14 20:10:08, Mark Seaborn wrote:

Would it make sense to just make this a ModulePass so (in a future CL) we could
also hand constexprs in global initializers? (also presumably we could re-use
part of it for the TLS expansion pass)

https://codereview.chromium.org/12792011/diff/1/lib/Transforms/NaCl/ExpandCon...
File lib/Transforms/NaCl/ExpandConstantExpr.cpp (right):

https://codereview.chromium.org/12792011/diff/1/lib/Transforms/NaCl/ExpandCon...
lib/Transforms/NaCl/ExpandConstantExpr.cpp:43:
INITIALIZE_PASS(ExpandConstantExpr, "expand-constant-expr",
if you use a static RegisterPass<ExpandConstantExprPass> Foo(...) in the pass's
cpp file, you don't need to have this, or to manually call
initializeExpandConstantExprPass() in the constructor or in opt.cpp

[Mark Seaborn, 2013-03-14 21:44:18]

> Would it make sense to just make this a ModulePass so (in a future
> CL) we could also hand constexprs in global initializers?

We can't convert constexprs global initializers to instructions because
instructions aren't allowed in that context.

For global initializers (which I'm treating as a separate issue,
https://code.google.com/p/nativeclient/issues/detail?id=3113), I intend to
flatten the constexprs.  This is quite different, so I think it should be a
separate pass, so that it can be enabled and tested separately, etc.

> (also presumably we could re-use part of it for the TLS expansion
> pass)

I'm keeping ExpandTlsConstantExpr separate for now because it's a less invasive
transformation -- it only converts what's needed by ExpandTls, and it searches
for uses rather than visiting all instructions.

https://codereview.chromium.org/12792011/diff/1/lib/Transforms/NaCl/ExpandCon...
File lib/Transforms/NaCl/ExpandConstantExpr.cpp (right):

https://codereview.chromium.org/12792011/diff/1/lib/Transforms/NaCl/ExpandCon...
lib/Transforms/NaCl/ExpandConstantExpr.cpp:43:
INITIALIZE_PASS(ExpandConstantExpr, "expand-constant-expr",
On 2013/03/14 21:23:50, Derek Schuff wrote:
> if you use a static RegisterPass<ExpandConstantExprPass> Foo(...) in the
pass's
> cpp file, you don't need to have this, or to manually call
> initializeExpandConstantExprPass() in the constructor or in opt.cpp

But then what causes ExpandConstantExpr.cpp to get linked into 'opt'?  You would
need icky linker tricks such as --whole-archive to do that.

Basically RegisterPass isn't used in the LLVM codebase for registering passes. 
All the passes are registered via the INITIALIZE_PASS pattern instead (including
those I added before in lib/Transforms/NaCl).  Grep the codebase to see
examples.

RegisterPass is basically only used for lib/Transforms/Hello/Hello.cpp.  It's
recommended by the doc http://llvm.org/docs/WritingAnLLVMPass.html for building
a pass into a .so library, but it doesn't work well for other linking use cases.

[Mark Seaborn, 2013-03-15 15:12:12]

I've fixed two corner cases:
 * Phi nodes with multiple incoming edges from the same basic block
 * Landingpad instructions

The PNaCl toolchain trybots now pass with this LLVM pass enabled.

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

some driveby comments

https://codereview.chromium.org/12792011/diff/5001/test/Transforms/NaCl/expan...
File test/Transforms/NaCl/expand-constantexpr.ll (right):

https://codereview.chromium.org/12792011/diff/5001/test/Transforms/NaCl/expan...
test/Transforms/NaCl/expand-constantexpr.ll:20: ; CHECK: %expanded1 = ptrtoint
i32* @global_var1 to i32
How about testing something with further nesting, to test the recursion in the
implementation?

https://codereview.chromium.org/12792011/diff/5001/test/Transforms/NaCl/expan...
test/Transforms/NaCl/expand-constantexpr.ll:68: %result = phi i32 [ ptrtoint
(i32* @global_var1 to i32), %entry ],
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]

https://codereview.chromium.org/12792011/diff/5001/test/Transforms/NaCl/expan...
File test/Transforms/NaCl/expand-constantexpr.ll (right):

https://codereview.chromium.org/12792011/diff/5001/test/Transforms/NaCl/expan...
test/Transforms/NaCl/expand-constantexpr.ll:68: %result = phi i32 [ ptrtoint
(i32* @global_var1 to i32), %entry ],
On 2013/03/15 17:56:01, jvoung (cr) wrote:
> 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?

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]

https://codereview.chromium.org/12792011/diff/5001/test/Transforms/NaCl/expan...
File test/Transforms/NaCl/expand-constantexpr.ll (right):

https://codereview.chromium.org/12792011/diff/5001/test/Transforms/NaCl/expan...
test/Transforms/NaCl/expand-constantexpr.ll:20: ; CHECK: %expanded1 = ptrtoint
i32* @global_var1 to i32
On 2013/03/15 17:56:01, jvoung (cr) wrote:
> How about testing something with further nesting, to test the recursion
> in the implementation?

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

https://codereview.chromium.org/12792011/diff/5001/test/Transforms/NaCl/expan...
test/Transforms/NaCl/expand-constantexpr.ll:68: %result = phi i32 [ ptrtoint
(i32* @global_var1 to i32), %entry ],
On 2013/03/15 17:56:01, jvoung (cr) wrote:
> 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?

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.

[Derek Schuff, 2013-03-15 19:28:48]

lgtm