llvm dev - Nov 2009 - [LLVMdev] DeadStoreElimination: do better without TargetData

On Nov 4, 2009, at 7:21 AM, Hans Wennborg wrote:
> Re-posting with better-looking code.
Thanks, do you have a testcase showing what this does?

-Chris
>
> Hans Wennborg wrote:
>> 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
>>
------------------------------------------------------------------------
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> Index: lib/Transforms/Scalar/DeadStoreElimination.cpp
> ==================================================================> ---
lib/Transforms/Scalar/DeadStoreElimination.cpp	(revision 86023)
> +++ lib/Transforms/Scalar/DeadStoreElimination.cpp	(working copy)
> @@ -117,10 +117,12 @@
>
>     // If this is a store-store dependence, then the previous store  
> is dead so
>     // long as this store is at least as big as it.
> -    if (StoreInst *DepStore =
dyn_cast<StoreInst>(InstDep.getInst()))
> -      if (TD &&
> -         
TD->getTypeStoreSize(DepStore->getOperand(0)->getType()) <> -    
TD->getTypeStoreSize(SI->getOperand(0)->getType())) {
> +    if (StoreInst *DepStore = dyn_cast<StoreInst>(InstDep.getInst 
> ())) {
> +      const Type *DepType = DepStore->getOperand(0)->getType();
> +      const Type *SIType = SI->getOperand(0)->getType();
> +      if (DepType == SIType ||
> +          (TD &&
> +          TD->getTypeStoreSize(DepType) <= TD->getTypeStoreSize 
> (SIType))) {
>         // Delete the store and now-dead instructions that feed it.
>         DeleteDeadInstruction(DepStore);
>         NumFastStores++;
> @@ -133,6 +135,7 @@
>           --BBI;
>         continue;
>       }
> +    }
>
>     // If we're storing the same value back to a pointer that we just
>     // loaded from, then the store can be removed.
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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:
> 
> On Nov 4, 2009, at 7:21 AM, Hans Wennborg wrote:
> 
>> Re-posting with better-looking code.
> 
> Thanks, do you have a testcase showing what this does?
> 
> -Chris
> 
>>
>> Hans Wennborg wrote:
>>> 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
>>>
------------------------------------------------------------------------
>>> _______________________________________________
>>> LLVM Developers mailing list
>>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>> Index: lib/Transforms/Scalar/DeadStoreElimination.cpp
>>
==================================================================>> ---
lib/Transforms/Scalar/DeadStoreElimination.cpp    (revision 86023)
>> +++ lib/Transforms/Scalar/DeadStoreElimination.cpp    (working copy)
>> @@ -117,10 +117,12 @@
>>
>>     // If this is a store-store dependence, then the previous store is 
>> dead so
>>     // long as this store is at least as big as it.
>> -    if (StoreInst *DepStore =
dyn_cast<StoreInst>(InstDep.getInst()))
>> -      if (TD &&
>> -         
TD->getTypeStoreSize(DepStore->getOperand(0)->getType()) <>> -
TD->getTypeStoreSize(SI->getOperand(0)->getType())) {
>> +    if (StoreInst *DepStore =
dyn_cast<StoreInst>(InstDep.getInst())) {
>> +      const Type *DepType = DepStore->getOperand(0)->getType();
>> +      const Type *SIType = SI->getOperand(0)->getType();
>> +      if (DepType == SIType ||
>> +          (TD &&
>> +          TD->getTypeStoreSize(DepType) <= 
>> TD->getTypeStoreSize(SIType))) {
>>         // Delete the store and now-dead instructions that feed it.
>>         DeleteDeadInstruction(DepStore);
>>         NumFastStores++;
>> @@ -133,6 +135,7 @@
>>           --BBI;
>>         continue;
>>       }
>> +    }
>>
>>     // If we're storing the same value back to a pointer that we
just
>>     // loaded from, then the store can be removed.
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>

On Wed, Nov 4, 2009 at 12:13 PM, Hans Wennborg <hans at hanshq.net>
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.

On Nov 4, 2009, at 10:13 AM, 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
> }
>
> 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.
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

On Nov 5, 2009, at 1:59 PM, Hans Wennborg wrote:
> 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