[LLVMdev] Cross-Block Dead Store Elimination

[Daniel Berlin]

On Wed Nov 05 2014 at 4:49:47 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.)
>

To do it "right", you'd have to build SSU and do PRE in the reverse
direction, which GVN doesn't do.  The patch posted actually does this
"right" (building SSU and using it), though i haven't looked through it to
see if it just does SSU building and usage, or actually does PRE.  Either
way, it's a good enough start :)

For normal cross-block cases, GVN does not value number loads *or* stores,
so it will never discover this, unless it can do so through the load's
 direct dependency.

IMHO, cleaning up the SSU based patch and getting it in would be the right
way to go. It may require some post-dominance speedups and cleanups to get
it fast enough and right enough (I know everyone hates the post-dominator
tree, but there is no other way to do proper store sinking)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20141106/65f66b4d/attachment.html>