Depends on D29865.
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.
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)
- 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.
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.
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).
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.
This is always called without the second parameter.
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?
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).
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 :)
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?
why a forward list?
you don't need else after return.
Can you please describe the PDT bug? I'm not really familiar with it (or I call it with another name :)