Page MenuHomePhabricator

[DSE] Basic MemorySSA-backed global DSE
Needs ReviewPublic

Authored by bryant on Feb 7 2017, 2:18 AM.



Previously posted to .

This will do everything that the current DSE does (except partial overwrite
tracking), but globally and sparsely (thanks to MemorySSA). Its main limitation
is that it requires every the later store of a DSE pair to post-dom the earlier.
In other words, it can't transform this:

store _ -> %x
if undef:
    store _ -> %x
    // do nothing.


if undef:
    store _ -> %x
    store _ -> %x

because the store inside the if-block doesn't post-dom the first one. Properly
handling this case would require a PRE approach (thanks Dan) that I'm also
currently cooking up.

So the purpose of posting this is posterity, and also to act as a back-up in
case the PRE attempt fails.

Diff Detail


Event Timeline

bryant created this revision.Feb 7 2017, 2:18 AM

Very nice code.


This is the old way to call TLI; see, for example, r294028.


I think we need some sort of iteration limit here to avoid quadratic compile-time for large basic blocks with lots of mayalias stores.

dberlin added inline comments.Feb 7 2017, 6:56 PM

FWIW, we don't optimize stores, because actually making that part of the def-use chain disconnects parts of the MemorySSA graph without multiple phis.

But .. there is nothing that stops the batch optimizer from *storing the info* in another field that isn't "DefiningAccess".

Then we could just reverse link (IE put a list in the def that goes to the uses) them to have a "clobberinguses" field just as easily.

that would make these walks as fast as they can be, because you would never have to go to "next def".
the set of clobbering uses would be complete and correct.

Now, whether it's worth it yet to do this, no idea.
But it's honestly simple enough.

The use/store optimizer already computes the answer to "what is the thing that clobbers this" in optimal time.



Maybe use PtrUseVisitor to build NonEscapes instead of densely stomping on all instructions. Also for Returns.

Prazek added inline comments.Feb 26 2017, 2:06 AM

Why are the comments after the code?

davide edited edge metadata.Apr 9 2017, 3:14 PM

Is this superseded by your new PDSE pass?

Yes. This was my first foray into sparse, non-local DSE and exists as a back-up if for some reason PDSE doesn't make it in (the biggest concern now is speed).

do you mind to abandon this revision then?

dberlin edited edge metadata.Apr 10 2017, 11:27 AM

So, two options::

  1. we make partial overwrite tracking work, commit this, and continue on PDSE until it's read
  2. We abandon this, work on PDSE, and come back to this if we can't make PDSE subsume it.

(which we should be able to)

jfb added a subscriber: jfb.Jan 30 2019, 1:53 PM