[LLVMdev] Cross-Block Dead Store Elimination

[Artem Dinaburg]

Hi Philip,

I've attached two simplified examples: does_optimize.ll and does_not_optimize.ll.

In both examples, the load/store of %STACK_BASEVAL and %STACK_LIMITVAL should be removed, since the values are never used. The difference is that in does_optimize.ll, the store is in the same block as the load, and in does_not_optimize.dll, the store is in a different block. 

When optimizing does_optimize.ll, the DeadStoreElimination pass removes the store as as "Remove Store of Load from same pointer" (http://llvm.org/docs/doxygen/html/DeadStoreElimination_8cpp_source.html#l00510). 

When optimizing does_not_optimize.ll, the store is not removed, because the corresponding load is in a different block. 

In both cases, we load a value and then store in back into the same location, so both load and store should be optimized out.

Thanks,
Artem Dinaburg

On Nov 5, 2014, at 7:48 PM, Philip Reames <listmail at philipreames.com> wrote:

> 
> On 10/24/2014 01:17 PM, Artem Dinaburg wrote:
>> Hi,
>> 
>> It looks like the DeadStoreElimination optimization doesn't work across BasicBlock boundaries. The project I'm working on (https://github.com/trailofbits/mcsema), would tremendously benefit from even simple cross-block DSE. 
> If you have specific small examples which aren't getting caught, I'd be interested in seeing test cases (as bugs.)
>> 
>> There was a patch to do non-local DSE few years ago (http://lists.cs.uiuc.edu/pipermail/llvmdev/2010-January/028751.html), but seems that the patch was never merged.
>> 
>> Is there an existing way to do cross-block DSE?
> EarlyCSE handles limited cases here.  GVN probably could, but doesn't seem to.  (Which surprises me.)
>> Was there something wrong with the original non-local DSE patch that it wasn't merged?
> I suspect it got lost in review.  It looks like there were some quality issues with the original implementation and the cycle never got closed.
>> 
>> Thanks,
>> Artem
>> 
>> 
>> _______________________________________________
>> LLVM Developers mailing list
>> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141106/e359275c/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: does_not_optimize.ll
Type: application/octet-stream
Size: 2039 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141106/e359275c/attachment.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141106/e359275c/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: does_optimize.ll
Type: application/octet-stream
Size: 2041 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141106/e359275c/attachment-0001.obj>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141106/e359275c/attachment-0002.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3869 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141106/e359275c/attachment.bin>