DeadStoreElimination: do better without TargetData

The attached patch makes DeadStoreElimination able to remove stores in store-store dependencies when the operand types are equal, even if there is no TargetData available.

/ Hans

DeadStoreElimination.patch (812 Bytes)

Re-posting with better-looking code.

Hans Wennborg wrote:

DeadStoreElimination2.patch (1.27 KB)

Re-posting with better-looking code.

Thanks, do you have a testcase showing what this does?

-Chris

Sorry, I admit my e-mail was a bit unclear.
Here is an example:

declare void @foo()

define void @f(i32* noalias %p) {
         store i32 1, i32* %p; <-- This is dead
         call void @foo()
         store i32 2, i32 *%p
         ret void
}

When run through ./llvm-as test.ll -o - | ./opt -O3 -S
the dead store is not removed by the DSE pass.
(The call to @foo is there to prevent InstCombine from folding the store instructions into one.)

This is because DSE relies on TargetData to find out about pointer sizes. Apparently, there was some default value for this before, but when running with top of the tree today, it turned out that TD=NULL in the DSE code.

We discussed this in the IRC channel, and someone pointed out that the more the pass can do without having info about the target, the better -- hence the patch.

With the patch, DSE will at least see if the data types are equal, even though it doesn't have information about their sizes. This is enough for handling the example above, and probably many others as well.

/ Hans

Chris Lattner wrote:

Sorry, I admit my e-mail was a bit unclear.
Here is an example:

declare void @foo()

define void @f(i32* noalias %p) {
store i32 1, i32* %p; <-- This is dead
call void @foo()
store i32 2, i32 *%p
ret void
}

When run through ./llvm-as test.ll -o - | ./opt -O3 -S
the dead store is not removed by the DSE pass.
(The call to @foo is there to prevent InstCombine from folding the store
instructions into one.)

This is because DSE relies on TargetData to find out about pointer
sizes. Apparently, there was some default value for this before, but
when running with top of the tree today, it turned out that TD=NULL in
the DSE code.

Yes, there was a default value before - a single default value for all
targets. On most targets, it was wrong, and led to the optimizer
breaking code unless the module had the host's target data string
packaged up inside of it.

We discussed this in the IRC channel, and someone pointed out that the
more the pass can do without having info about the target, the better --
hence the patch.

My feeling exactly.

With the patch, DSE will at least see if the data types are equal, even
though it doesn't have information about their sizes. This is enough for
handling the example above, and probably many others as well.

Thanks.

Thanks, applied here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20091102/090396.html

I'd appreciate it if you could resend your other patches in patch format like this, attached to the email with the testcase using filecheck. This commit should be a good example. Thanks for helping improve this area!

-Chris

Hans Wennborg wrote:

Sorry, I admit my e-mail was a bit unclear.
Here is an example:

declare void @foo()

define void @f(i32* noalias %p) {
         store i32 1, i32* %p; <-- This is dead
         call void @foo()
         store i32 2, i32 *%p
         ret void
}

Hold up. Is this correct?

"noalias: This indicates that the pointer does not alias any global or any other parameter. The caller is responsible for ensuring that this is the case." - LangRef

I've been interpreting this to mean that an arbitrary function may modify %p in this example, so long as it isn't *directly* held by a global or another argument. However, the global could contain a pointer to an object, indirectly pointing to %p.

This would allow us to get more 'noalias' results from within @foo itself, but we not this optimization around it. I believe it's compatible with the definition of 'restrict' in C which noalias is modelled on.

According to my interpretation, if the TD was the only issue blocking this transform then DSE was already buggy.

Chris, could you please confirm your intention here?

Nick

I haven't thought about this, but this patch doesn't regress prior functionality it only makes it work when no TD is available.

-Chris

My apologies for not replying sooner; I've been away from keyboard all
day today.

Thanks, applied here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20091102/090396.html

I'd appreciate it if you could resend your other patches in patch format
like this, attached to the email with the testcase using filecheck.
This commit should be a good example. Thanks for helping improve this
area!

I'm not sure I follow you completely here. You want me to resend to
llvmdev, right -- not llvm-commits?

Sure, either way works.

What is the difference between the patch format i used and the one you
refer to, except for the testcase?
Is this filecheck thing documented somwhere?

Specifically, please send it as an attachment instead of inline:
http://llvm.org/docs/DeveloperPolicy.html#patches

This makes it easier to apply. FileCheck is documented here:
http://llvm.org/docs/TestingGuide.html#FileCheck

Thanks!

-Chris