PNaCl: Add ReplacePtrsWithInts pass for stripping out pointer types

PNaCl: Add ReplacePtrsWithInts pass for stripping out pointer types

ReplacePtrsWithInts converts IR to a normal form in which functions
don't reference any aggregate pointer types and pointer types only
appear inside a few instructions.

Change BlockAddress::replaceUsesOfWithOnConstant() to handle changing
a function's type by replacing a function with a bitcast ConstantExpr
of a new function.

BUG=https://code.google.com/p/nativeclient/issues/detail?id=3343
TEST=replace-ptrs-with-ints.ll + PNaCl toolchain trybots, torture tests, etc.

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

[Mark Seaborn, 2013-05-15 20:50:39]

This pass produces some nice pexe size reductions: It reduces the size of all
the Spec2k pexes.  The total sizes are:

   raw:  -6.6% size increase:  9233884 bytes (before) + -605244 = 8628640 bytes
(after)
  gzip:  -6.4% size increase:  6285665 bytes (before) + -404658 = 5881007 bytes
(after)

(I mentioned yesterday that I was seeing ~30% size increases, but that was
because I was running "-replace-ptrs-with-ints" on the stripped pexes and
forgetting to reapply "-strip" afterwards!)

I should probably upstream the BlockAddress::replaceUsesOfWithOnConstant()
change.  How much do you think that change needs a test to be upstreamed?

[eliben, 2013-05-15 22:11:21]

Some initial comments

https://codereview.chromium.org/14262011/diff/17001/lib/Transforms/NaCl/Repla...
File lib/Transforms/NaCl/ReplacePtrsWithInts.cpp (right):

https://codereview.chromium.org/14262011/diff/17001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:70: class FunctionConverter {
Comment explaining what this class does, and what its methods do, members mean,
etc... ?

https://codereview.chromium.org/14262011/diff/17001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:87: Type *ConvertType(Type *Ty);
According to the LLVM convention
(http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-...)
functions and methods are camelStartingWithLowercase

https://codereview.chromium.org/14262011/diff/17001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:100: static Instruction
*CopyDebug(Instruction *NewInst, Instruction *Original) {
Hmm, this is being used in ExpandVarArgs too, so maybe it's worth separating it
as a utility function somewhere in lib/Transforms/NaCl?

https://codereview.chromium.org/14262011/diff/17001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:500: // the conversion in three
passes.
Explain what the three passes are/do?

https://codereview.chromium.org/14262011/diff/17001/test/Transforms/NaCl/repl...
File test/Transforms/NaCl/replace-ptrs-with-ints.ll (right):

https://codereview.chromium.org/14262011/diff/17001/test/Transforms/NaCl/repl...
test/Transforms/NaCl/replace-ptrs-with-ints.ll:27: define void @return_void() {
What is this for?

https://codereview.chromium.org/14262011/diff/17001/test/Transforms/NaCl/repl...
test/Transforms/NaCl/replace-ptrs-with-ints.ll:411: define i8*
@getelementptr(i8* %ptr) {
What is this for?

https://codereview.chromium.org/14262011/diff/17001/test/Transforms/NaCl/repl...
test/Transforms/NaCl/replace-ptrs-with-ints.ll:416: define i32* @va_arg(i8*
%valist) {
Ditto

[Mark Seaborn, 2013-05-16 02:08:40]

https://codereview.chromium.org/14262011/diff/17001/lib/Transforms/NaCl/Repla...
File lib/Transforms/NaCl/ReplacePtrsWithInts.cpp (right):

https://codereview.chromium.org/14262011/diff/17001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:70: class FunctionConverter {
On 2013/05/15 22:11:21, eliben wrote:
> Comment explaining what this class does, and what its methods do, members
mean,
> etc... ?

Comments added.

https://codereview.chromium.org/14262011/diff/17001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:87: Type *ConvertType(Type *Ty);
On 2013/05/15 22:11:21, eliben wrote:
> According to the LLVM convention
>
(http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-...)
> functions and methods are camelStartingWithLowercase

Oops, yes.  Fixed the methods.

https://codereview.chromium.org/14262011/diff/17001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:100: static Instruction
*CopyDebug(Instruction *NewInst, Instruction *Original) {
On 2013/05/15 22:11:21, eliben wrote:
> Hmm, this is being used in ExpandVarArgs too, so maybe it's worth separating
it
> as a utility function somewhere in lib/Transforms/NaCl?

OK, done.

https://codereview.chromium.org/14262011/diff/17001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:500: // the conversion in three
passes.
On 2013/05/15 22:11:21, eliben wrote:
> Explain what the three passes are/do?

In the course of adding comments, I realised that this doesn't need three passes
any more.

I've refactored it to remove FunctionMap now.

https://codereview.chromium.org/14262011/diff/17001/test/Transforms/NaCl/repl...
File test/Transforms/NaCl/replace-ptrs-with-ints.ll (right):

https://codereview.chromium.org/14262011/diff/17001/test/Transforms/NaCl/repl...
test/Transforms/NaCl/replace-ptrs-with-ints.ll:27: define void @return_void() {
On 2013/05/15 22:11:21, eliben wrote:
> What is this for?

This was just checking that the pass doesn't barf on "ret void".  Removed now,
since other tests contain "ret void".

https://codereview.chromium.org/14262011/diff/17001/test/Transforms/NaCl/repl...
test/Transforms/NaCl/replace-ptrs-with-ints.ll:411: define i8*
@getelementptr(i8* %ptr) {
On 2013/05/15 22:11:21, eliben wrote:
> What is this for?

This just checks that the pass doesn't barf on getelementptr, so that the pass
doesn't unnecessarily depend on other expansion passes having been run.  Comment
added.

https://codereview.chromium.org/14262011/diff/17001/test/Transforms/NaCl/repl...
test/Transforms/NaCl/replace-ptrs-with-ints.ll:416: define i32* @va_arg(i8*
%valist) {
On 2013/05/15 22:11:21, eliben wrote:
> Ditto

Ditto.

[Derek Schuff, 2013-05-17 23:16:05]

https://codereview.chromium.org/14262011/diff/22002/lib/IR/Constants.cpp
File lib/IR/Constants.cpp (right):

https://codereview.chromium.org/14262011/diff/22002/lib/IR/Constants.cpp#newc...
lib/IR/Constants.cpp:1374: NewF = cast<Function>(To->stripPointerCasts());
LOCALMOD with comment?

https://codereview.chromium.org/14262011/diff/22002/lib/Transforms/NaCl/Repla...
File lib/Transforms/NaCl/ReplacePtrsWithInts.cpp (right):

https://codereview.chromium.org/14262011/diff/22002/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:173:
convertType(Val->getType()->getPointerElementType())->getPointerTo();
is this sequence just to convert e.g. from array type to pointer?

https://codereview.chromium.org/14262011/diff/22002/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:223: for (SmallVector<Instruction *,
10>::iterator I = ToErase.begin(),
the standard idiom in LLVM in this kind of situation is to iterate over a
SmallVectorImpl so you don't have to duplicate the baked-in size, in case it
gets changed (same goes for function args)

https://codereview.chromium.org/14262011/diff/22002/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:322: if (ArgSize == ResultSize) {
You could probably just make an IRBuilder and use CreateZExtOrTrunc here instead
of all this logic.

https://codereview.chromium.org/14262011/diff/22002/test/Transforms/NaCl/repl...
File test/Transforms/NaCl/replace-ptrs-with-ints.ll (right):

https://codereview.chromium.org/14262011/diff/22002/test/Transforms/NaCl/repl...
test/Transforms/NaCl/replace-ptrs-with-ints.ll:259: %struct = type { i32, i32 }
can you move this decl to the top since there are references to it there?

[Mark Seaborn, 2013-05-20 15:08:12]

I've fixed alloca to preserve alignment when the alignment is implicit.

https://codereview.chromium.org/14262011/diff/22002/lib/IR/Constants.cpp
File lib/IR/Constants.cpp (right):

https://codereview.chromium.org/14262011/diff/22002/lib/IR/Constants.cpp#newc...
lib/IR/Constants.cpp:1374: NewF = cast<Function>(To->stripPointerCasts());
On 2013/05/17 23:16:05, Derek Schuff wrote:
> LOCALMOD with comment?

Done: LOCALMOD comment added.

https://codereview.chromium.org/14262011/diff/22002/lib/Transforms/NaCl/Repla...
File lib/Transforms/NaCl/ReplacePtrsWithInts.cpp (right):

https://codereview.chromium.org/14262011/diff/22002/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:173:
convertType(Val->getType()->getPointerElementType())->getPointerTo();
On 2013/05/17 23:16:05, Derek Schuff wrote:
> is this sequence just to convert e.g. from array type to pointer?

No, arrays aren't involved.  This line converts a pointer to a non-normalized
type to a pointer to a normalized type.

e.g. i16** is converted to i32* (because i32 is the normalized version of i16*).
 i8* is left as i8*.

https://codereview.chromium.org/14262011/diff/22002/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:223: for (SmallVector<Instruction *,
10>::iterator I = ToErase.begin(),
On 2013/05/17 23:16:05, Derek Schuff wrote:
> the standard idiom in LLVM in this kind of situation is to iterate over a
> SmallVectorImpl so you don't have to duplicate the baked-in size, in case it
> gets changed (same goes for function args)

Done.

https://codereview.chromium.org/14262011/diff/22002/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:322: if (ArgSize == ResultSize) {
On 2013/05/17 23:16:05, Derek Schuff wrote:
> You could probably just make an IRBuilder and use CreateZExtOrTrunc here
instead
> of all this logic.

Done.

https://codereview.chromium.org/14262011/diff/22002/test/Transforms/NaCl/repl...
File test/Transforms/NaCl/replace-ptrs-with-ints.ll (right):

https://codereview.chromium.org/14262011/diff/22002/test/Transforms/NaCl/repl...
test/Transforms/NaCl/replace-ptrs-with-ints.ll:259: %struct = type { i32, i32 }
On 2013/05/17 23:16:05, Derek Schuff wrote:
> can you move this decl to the top since there are references to it there?

Done.

[Derek Schuff, 2013-05-20 16:05:45]

lgtm

[eliben, 2013-05-20 22:18:49]

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Expan...
File lib/Transforms/NaCl/ExpandUtils.cpp (right):

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Expan...
lib/Transforms/NaCl/ExpandUtils.cpp:42: Instruction *llvm::CopyDebug(Instruction
*NewInst, Instruction *Original) {
Somewhere a comment should say what this does and how to use it. Preferably next
to the declaration?

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
File lib/Transforms/NaCl/ReplacePtrsWithInts.cpp (right):

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:106: // Returns the NormalizedPtr
form of the given pointer value.
It also inserts the conversion instruction, not just returns the new value

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:135: if
(!From->getType()->isPointerTy()) {
It's kind of unclear (definietely from the method name and comment) that this is
done. Also it would be nice to document the logic for placeholders

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:191: if (isa<InlineAsm>(V))
Under what circumstances can we have inline asm?

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:227: (*I)->dropAllReferences();
Document why this is needed. Why would reference remain if you RAUW-ed it
before?

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:254: static AttributeSet
RemoveAttrs(LLVMContext &Context, AttributeSet Attrs) {
Document what kinds of attrs this removes

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:297: Ret->eraseFromParent();
Can you clarify why you use recordConvertedAndErase for some instructions, but
not for others?

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:444: FunctionPass *Pass =
createExpandConstantExprPass();
Wait, you planned to run the ConstExpr pass last precisely because other passes
may introduce ConstExprs. Has this changed?

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:491:
OldFunc->getParent()->getFunctionList().insert(OldFunc, NewFunc);
Can you use M instead of OldFunc->getParent() ?

[Mark Seaborn, 2013-05-21 23:12:07]

I've updated this to strip out lifetime markers, because of the problem with PHI
nodes I found in https://code.google.com/p/nativeclient/issues/detail?id=3443. 
Please take a look.

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Expan...
File lib/Transforms/NaCl/ExpandUtils.cpp (right):

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Expan...
lib/Transforms/NaCl/ExpandUtils.cpp:42: Instruction *llvm::CopyDebug(Instruction
*NewInst, Instruction *Original) {
On 2013/05/20 22:18:49, eliben wrote:
> Somewhere a comment should say what this does and how to use it. Preferably
next
> to the declaration?

Added comment in header.

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
File lib/Transforms/NaCl/ReplacePtrsWithInts.cpp (right):

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:106: // Returns the NormalizedPtr
form of the given pointer value.
On 2013/05/20 22:18:49, eliben wrote:
> It also inserts the conversion instruction, not just returns the new value

Comment added.

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:135: if
(!From->getType()->isPointerTy()) {
On 2013/05/20 22:18:49, eliben wrote:
> It's kind of unclear (definietely from the method name and comment) that this
is
> done. Also it would be nice to document the logic for placeholders

Added comment.

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:191: if (isa<InlineAsm>(V))
On 2013/05/20 22:18:49, eliben wrote:
> Under what circumstances can we have inline asm?

PNaCl doesn't allow it, obviously.  However, I have generally been taking the
approach of making these passes as general-purpose as possible.

We have inline asm when running the GCC torture tests.  Jan recently changed
these to pass "--pnacl-disable-abi-check" for asm-using tests rather than just
disabling the tests.  Handling inline asm gracefully here is a simple enough way
of dealing with that.

Maybe we should just disable all ABI simplification passes for GCC torture tests
covering features not supported by PNaCl.  I've been looking into this, since it
would simplify things.

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:227: (*I)->dropAllReferences();
On 2013/05/20 22:18:49, eliben wrote:
> Document why this is needed.

Comment added.

> Why would reference remain if you RAUW-ed it before?

We *haven't* RAUW'd the instructions in the ToErase list.  ToErase contains
instructions we are replacing with instructions of different types, and we can't
use RAUW in that case.

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:254: static AttributeSet
RemoveAttrs(LLVMContext &Context, AttributeSet Attrs) {
On 2013/05/20 22:18:49, eliben wrote:
> Document what kinds of attrs this removes

Added more commentary in the function.

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:297: Ret->eraseFromParent();
On 2013/05/20 22:18:49, eliben wrote:
> Can you clarify why you use recordConvertedAndErase for some instructions, but
> not for others?

We don't erase:
 * Arguments -- because you can't erase them; they are tied to the function, and
erased when the function is erased
 * instructions converted in-place -- because we want to leave the original
instruction in place

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:444: FunctionPass *Pass =
createExpandConstantExprPass();
On 2013/05/20 22:18:49, eliben wrote:
> Wait, you planned to run the ConstExpr pass last precisely because other
passes
> may introduce ConstExprs. Has this changed?

ReplacePtrsWithInts needs to run after ExpandConstantExpr.

ReplacePtrsWithInts can't handle arbitrary ConstantExprs in its input.

The ordering we need is:
  -flatten-globals  # introduces some bitcast ConstantExprs of globals
  -expand-constant-expr
  -expand-getelementptr    # assumes ConstantExprs are gone
  -replace-ptrs-with-ints  # assumes ConstantExprs are gone

https://codereview.chromium.org/14262011/diff/30001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:491:
OldFunc->getParent()->getFunctionList().insert(OldFunc, NewFunc);
On 2013/05/20 22:18:49, eliben wrote:
> Can you use M instead of OldFunc->getParent() ?

Yes, done.

[eliben, 2013-05-22 16:08:02]

LGTM with minor nits

https://codereview.chromium.org/14262011/diff/41001/include/llvm/Transforms/N...
File include/llvm/Transforms/NaCl.h (right):

https://codereview.chromium.org/14262011/diff/41001/include/llvm/Transforms/N...
include/llvm/Transforms/NaCl.h:41: // Copy debug information from Original to
NewInst.
Maybe "Return NewInst with debug information copied from Original" would be
clearer?

https://codereview.chromium.org/14262011/diff/41001/lib/Transforms/NaCl/Repla...
File lib/Transforms/NaCl/ReplacePtrsWithInts.cpp (right):

https://codereview.chromium.org/14262011/diff/41001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:261: static AttributeSet
RemoveAttrs(LLVMContext &Context, AttributeSet Attrs) {
Comment this function. Also, a more descriptive name would be helpful (the
current one almost suggests that all attributes are removed)

[Derek Schuff, 2013-05-22 16:24:08]

lgtm with one nit

https://codereview.chromium.org/14262011/diff/41001/lib/Transforms/NaCl/Repla...
File lib/Transforms/NaCl/ReplacePtrsWithInts.cpp (right):

https://codereview.chromium.org/14262011/diff/41001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:367: // Remove alloca lifetime
markers for now.  This is because
It's probably worth having this comment or some subset of it up at the top of
this file with the general description.

[Mark Seaborn, 2013-05-22 18:29:14]

https://codereview.chromium.org/14262011/diff/41001/include/llvm/Transforms/N...
File include/llvm/Transforms/NaCl.h (right):

https://codereview.chromium.org/14262011/diff/41001/include/llvm/Transforms/N...
include/llvm/Transforms/NaCl.h:41: // Copy debug information from Original to
NewInst.
On 2013/05/22 16:08:02, eliben wrote:
> Maybe "Return NewInst with debug information copied from Original" would be
> clearer?

"Return NewInst with" sounds a little bit like it makes a copy of NewInst.

As a compromise, I've put "Copy debug information from Original to NewInst, and
return NewInst."

https://codereview.chromium.org/14262011/diff/41001/lib/Transforms/NaCl/Repla...
File lib/Transforms/NaCl/ReplacePtrsWithInts.cpp (right):

https://codereview.chromium.org/14262011/diff/41001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:261: static AttributeSet
RemoveAttrs(LLVMContext &Context, AttributeSet Attrs) {
On 2013/05/22 16:08:02, eliben wrote:
> Comment this function.

Done.

> Also, a more descriptive name would be helpful (the
> current one almost suggests that all attributes are removed)

Changed to RemovePointerAttrs().

https://codereview.chromium.org/14262011/diff/41001/lib/Transforms/NaCl/Repla...
lib/Transforms/NaCl/ReplacePtrsWithInts.cpp:367: // Remove alloca lifetime
markers for now.  This is because
On 2013/05/22 16:24:08, Derek Schuff wrote:
> It's probably worth having this comment or some subset of it up at the top of
> this file with the general description.

OK, added a small comment at the top.

[Mark Seaborn, 2013-05-22 18:34:48]

Committed patchset #13 manually as r9f0ec13 (presubmit successful).