This is an archive of the discontinued LLVM Phabricator instance.

Needs RevisionPublic

Authored by bryant on Feb 11 2017, 10:31 AM.



Depends on D29865.

Diff Detail


Event Timeline

bryant created this revision.Feb 11 2017, 10:31 AM
davide requested changes to this revision.Feb 12 2017, 12:53 PM

See comments on the other review

This revision now requires changes to proceed.Feb 12 2017, 12:53 PM
bryant updated this revision to Diff 89346.Feb 22 2017, 4:06 AM
bryant edited edge metadata.
bryant retitled this revision from [PDSE] Add pretty printer for factored redundancy graph. to [PDSE] Add PDSE..
  • PDSE actually PDSEs now.
  • Added a test file.
dberlin added inline comments.Feb 22 2017, 3:24 PM

DenseMap<const BasicBlock *, iplist<RealOcc>> will work.

Just derive RealOcc from ilist_node<RealOcc>

bryant updated this revision to Diff 91132.Mar 8 2017, 10:46 PM

It runs faster than before.

  • Reduced number of whole function traversals. All occurrence classes are now DSE-ed and renamed in a single post-dom pre-order traversal.
  • Only call getModRefInfo when absolutely necessary, which is when a potential aliasing load is encountered.
  • Cache between-class aliasing info.
bryant updated this revision to Diff 91139.Mar 8 2017, 11:52 PM

Added test cases and fix-me cases.

dberlin edited edge metadata.Mar 29 2017, 1:43 PM
dberlin added a subscriber: grosser.

I'm going to start looking at this in detail today or tomorrow.
Adding Tobias since i believe he asked what we have that will depend on a postdom tree.

This optimization depends on a complete and correct postdom tree
(also, recursively, because it depends on IDFCalculator, which also depends on the path properties of the postdom tree. ADCE attempts to hack around that fact, it's much harder to do here)

bryant updated this revision to Diff 93443.Mar 29 2017, 8:44 PM
  • Partition each redundancy class of must-aliasing, same-sized stores into same-opcode, same-pointer-type subclasses. For instance, memmove(i8* %a, i8*, i32 1), store i8, i8* %a, and store i1, i1* (bitcast i8* %a to i1*) belong to the same redundancy class, but distinct subclasses. This is needed for PRE insertion to work.
  • Use SSAUpdater to generate the PRE-inserted occurrence's pointer operand (and whichever phi nodes are needed).
  • Extend computeCanBeAnt to account for unsplittable critical edges, e.g., lambda blocks that terminated by indirectbr.
  • Add more tests from bugpoint.
mehdi_amini added inline comments.Mar 29 2017, 9:38 PM

Is "PDSE" supposed to be a well known acronym? I feel that the description could be more friendly with --help readers.

It also sounds strange to me that "Partial DSE" is "stronger" than "DSE" alone.

davide added inline comments.Mar 29 2017, 10:07 PM

It doesn't to me, at all. See, for example, PRE (partial redundancy elimination) which is stronger than full redundancy elimination (once we agree on the meaning of stronger).

filcab added a subscriber: filcab.Apr 3 2017, 7:30 AM

Will need to read up a bit more before I can usefully comment on the algorithm, but I've added a few minor comments.

Please document the tests a bit better. Some of them have a good explanation of what they're testing, others don't. For example, in the first two, add a high-level explanation of what they're testing. It makes it much easier to figure out what happened when someone else changes some code which changes the output on those tests.


I think it helps if you look at it as (PDS)E, and not as P(DSE) :-)


isReal/isLambda sound like they return booleans. Code like X->isReal()->isLambda() looks weird.
In my opinion, asReal/asLambda (or similar) would be easier to read (exact same behavior: If they're the type that we're asking for, return the pointer. Otherwise return nullptr).


This is always called without the second parameter.
It seems code would be simpler if you just took a pointer as an argument.


Why isReal()->isLambda()? Won't the isLambda() always return nullptr? (Type can't be both OccTy::Real and OccTy::Lambda)


We usually comment above the variable.


Did you do any measurements/reasoning for these sizes, btw?
(Just asking. No need to worry too much for now)


Nit: We can do without the else in these.


Should we assert?


Please remove editor-related markup.


I'd rather have an ASCII diagram instead of relying on an external image service (also hard to look at when reading tests).

This revision now requires changes to proceed.May 1 2017, 11:19 AM

Hey Bryant,
Is this the latest code?

Wanted to review it, but looks like there are unaddressed comments.
I know you put a tremendous amount of good work into this, but i also know it can be frustrating, so if you are done with it, and want someone to take it over, let me know :)

I'd like to take a look at this too. Realistically, as this is a big chunk, it won't be before next weekend when I can actually sit down without being interrupted.

Thanks for this very good piece of work, Bryant.
In general this pass needs more comments (i.e. the phases of the algorithm need to be described, for example renamePass()).
Some comments to begin with.


We generally put the comment above the field and not below, can you change those?


you don't need else after return.


why a forward list?


Can you please describe the PDT bug? I'm not really familiar with it (or I call it with another name :)

aqjune added a subscriber: aqjune.Oct 14 2018, 9:54 PM

Hello all,

I found that this patch (+ D29865) can be successfully rebased on the recent LLVM commit with minor fix.

If @bryant doesn't mind, I can be of help in updating the patches.

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