This is an archive of the discontinued LLVM Phabricator instance.

NewGVN
ClosedPublic

Authored by davide on Nov 1 2016, 5:03 PM.

Diff Detail

Repository
rL LLVM

Event Timeline

davide updated this revision to Diff 76658.Nov 1 2016, 5:03 PM
davide retitled this revision from to [WIP] Initial NewGVN.
davide updated this object.
davide removed subscribers: mgorny, modocache.
filcab added a subscriber: filcab.Nov 2 2016, 2:56 PM
davide retitled this revision from [WIP] Initial NewGVN to NewGVN.Nov 15 2016, 10:50 PM
davide added reviewers: dberlin, majnemer.
davide added a subscriber: llvm-commits.
majnemer added inline comments.Nov 15 2016, 11:04 PM
include/llvm/Transforms/Scalar/GVNExpression.h
14–15 ↗(On Diff #76658)

I'd insert a newline here.

16–17 ↗(On Diff #76658)

I'd insert a newline here.

76 ↗(On Diff #76658)

Comments should end with a period.

85 ↗(On Diff #76658)

other should follow the naming convention.

118–119 ↗(On Diff #76658)

unsigned int -> unsigned, there are other places where this not followed, please correct them.

128–161 ↗(On Diff #76658)

Inline keyword is superfluous, we are in the class definition. Please correct this elsewhere as well.

556 ↗(On Diff #76658)

Please use const auto * when assigning w/ a dyn_cast, the type should be clear.

Great to see this finally come upstream! Thanks for driving this :)

(Just two quick comments inline while I'm here)

include/llvm/Transforms/Scalar/GVNExpression.h
221 ↗(On Diff #76658)

final does not seem applied equally everywhere, for instance why isn't LoadExpression marked final as well?

241 ↗(On Diff #76658)

= default; (check the others)

dberlin added inline comments.Nov 15 2016, 11:44 PM
lib/Transforms/Scalar/NewGVN.cpp
1001 ↗(On Diff #76658)

There's a bug (well, incompleteness) here that i just noticed
For memory, we also need to mark the uses of the MemoryDef/MemoryUse for the instruction as touched.
(and handle MemoryPhi's).
While most of the time, they are already touched, otherwise, will not iterate when we have discovered something about memory for, say, store over store.

MemoryPhi's will need value numbering when I fix the store over store problem, but for now, i'd just skip them.

So i'd add something like

if (MemoryAccess *MA = MSSA->getMemoryAccess(V)) 
  markMemoryUsersTouched(MA);

where markMemoryUsersTouched just walks the users of MA and mark MA->getInst() touched iff it's a MemoryUseOrDef.

This will ensure memory instructions change when we discover new things about them.

Sorry, in GCC, they are part of the IR, so there aren't two use lists :)

Prazek added a subscriber: Prazek.Nov 17 2016, 2:25 PM
Prazek added inline comments.
include/llvm/Transforms/Scalar/GVNExpression.h
37 ↗(On Diff #76658)

I am not really sure what does it mean, where other enums seems to be self descriptive.
Does it mean "inside basic block, but not BB start nor end?"

65 ↗(On Diff #76658)

You could call another ctor here like:
Expression(unsigned int o = ..) : Expression(ExpressionTypeBase), o) {}

davide updated this revision to Diff 78441.Nov 17 2016, 5:25 PM
davide marked 7 inline comments as done.

Addressed the first round of comments + random cleanups I found by inspection.

davide updated this revision to Diff 78442.Nov 17 2016, 5:25 PM
davide edited reviewers, added: Bigcheese; removed: deadalnix.
davide added inline comments.Nov 17 2016, 6:54 PM
include/llvm/Transforms/Scalar/GVNExpression.h
221 ↗(On Diff #76658)

Just an oversight. Fixed (also in other places).

241 ↗(On Diff #76658)

I converted all of them, please let me know if I missed something

Can you also post on Phabricator a mockup of a patch to enable the newgvn pass by default in the trunk clang compiler in order to simplify end-user testing? I noticed that the current clang compiler doesn't seem to enable the current gvn pass by default.

davide added a comment.EditedNov 19 2016, 12:40 PM

Can you also post on Phabricator a mockup of a patch to enable the newgvn pass by default in the trunk clang compiler in order to simplify end-user testing? I noticed that the current clang compiler doesn't seem to enable the current gvn pass by default.

Sure, I'll make one. I'm not sure what you mean when you say that the current clang compiler doesn't call the current GVN. In EmitAssemblyHelper::CreatePasses, we call inside LLVM, PMBuilder.populateModulePassManager() which creates a pass pipeline containing GVN (see Transforms/IPO/PassManagerBuilder.cpp).

Hi Davide,

A high level comment for an issue I've just run into when rebasing GVNSink on top of NewGVN - you've defined LoadExpression::equals and StoreExpression::equals in the header, which gives multiple definition errors (for ::equals and the vtables) if any other file tries to #include <GVNExpression.h>.

Cheers,

James

davide updated this revision to Diff 78751.Nov 21 2016, 12:12 PM
davide edited edge metadata.

Move LoadExpression::equals/StoreExpression::equals to NewGVN.cpp

Bigcheese requested changes to this revision.Nov 27 2016, 5:59 PM
Bigcheese edited edge metadata.
Bigcheese added inline comments.
include/llvm/Transforms/Scalar/GVNExpression.h
49 ↗(On Diff #78751)

These don't need to be private.

54 ↗(On Diff #78751)

This can be private.

55 ↗(On Diff #78751)

Since you've got getOptcode() and setOpcode() this doesn't need to be protected. Either make this public and get rid of the accessors, or make it private.

64 ↗(On Diff #78751)

I think this can be removed.

69 ↗(On Diff #78751)
71–83 ↗(On Diff #78751)

The behavior of this operator is quite nonintuitive. It's actually isTrivallyCongruent(), not is equal. However if this is the natural equality definition for this type, then it would be fine with a comment explaining that.

87–89 ↗(On Diff #78751)

This can return a different hash_code for Expressions which compare equal.

111–113 ↗(On Diff #78751)

Don't need to be private.

165 ↗(On Diff #78751)

Not needed.

189 ↗(On Diff #78751)

Anchor.

include/llvm/Transforms/Scalar/NewGVN.h
10–12 ↗(On Diff #78751)

This looks like the comment from the old GVN pass.

lib/Transforms/Scalar/NewGVN.cpp
1 ↗(On Diff #78751)

NewGVN.cpp

10–14 ↗(On Diff #78751)

Old comment. Missing \file

127 ↗(On Diff #78751)

Prefer ~0u

132 ↗(On Diff #78751)

Prefer ~1u

145 ↗(On Diff #78751)

This seems like the wrong equality operator for the above hash. It will return true for things that don't hash to the same value.

210 ↗(On Diff #78751)

This doesn't need to be explicit.

1226 ↗(On Diff #78751)

Do we have a proper type anywhere to use for a range instead of pair? first and last.

This revision now requires changes to proceed.Nov 27 2016, 5:59 PM
davide updated this revision to Diff 79876.Nov 30 2016, 11:53 PM
davide edited edge metadata.
davide marked 10 inline comments as done and an inline comment as not done.Nov 30 2016, 11:53 PM

Addressed Michael's comments.

Sorry for the delay. I'm on the road this week with limited access to internet.
I encourage other people to comment so that we can get the first revision in tree and iterate from there.

include/llvm/Transforms/Scalar/GVNExpression.h
87–89 ↗(On Diff #78751)

See Danny's reply (in the next mail).

lib/Transforms/Scalar/NewGVN.cpp
1226 ↗(On Diff #78751)

No, I personally don't mind std::pair, but I can change it if you feel strong.

davide added a comment.Dec 5 2016, 6:57 AM

Monday morning ping.
I would like to get the first cut in-tree soon (let's say, this week or the next) so we can iterate in-tree.

RKSimon edited edge metadata.Dec 6 2016, 10:59 AM

Mainly a code style review and a few random things I managed to spot. I don't know enough about GVN to go in depth.

What I did notice was that this really needs commenting more thoroughly, describing each Expression class type etc. and there needs to be more consistency with the ordering of class variables / method types.

include/llvm/Transforms/Scalar/GVNExpression.h
34 ↗(On Diff #79876)

Use a short prefix not the whole enum type name: ET_Base, ..... ET_Store, ET_BasicEnd

47 ↗(On Diff #79876)

Should this be called ExpressionBase or something?

62 ↗(On Diff #79876)

Keep the constructors / destructors at the top of the public block? At least not mixed in with the other methods.

67 ↗(On Diff #79876)

Magic numbers - replace with enum?

83 ↗(On Diff #79876)

Split the print/debug methods into their own section headed with (similar to MachineInstr.h):

//
// Debugging support
//
83 ↗(On Diff #79876)

Debug print out code can be quite bulky - worth moving these to a cpp file instead of inline?

116 ↗(On Diff #79876)

Consistently put these next to the ops_begin() methods?

155 ↗(On Diff #79876)

Put these consistently in the same place in each class.

205 ↗(On Diff #79876)

Add override? Probably in a few other places too.

444 ↗(On Diff #79876)

Put class variables consistently at the top or the bottom.

lib/Transforms/Scalar/NewGVN.cpp
136 ↗(On Diff #79876)

static_cast<uintptr_t>(-1) ?

173 ↗(On Diff #79876)

Is it a good idea to leave an initializer here?

245 ↗(On Diff #79876)

Don't leave this amongst the creators

375 ↗(On Diff #79876)

newline

436 ↗(On Diff #79876)

Did you mean to compare pointer values?

442 ↗(On Diff #79876)

Tidyup?

E->ops_push_back(lookupOperandLeader(Arg1, nullptr, B));
E->ops_push_back(lookupOperandLeader(Arg2, nullptr, B));
459 ↗(On Diff #79876)
return nullptr;
552 ↗(On Diff #79876)

wasted newline

590 ↗(On Diff #79876)

Remove braces:

if (Value *V = ConstantFoldInstOperands(I, C, *DL, TLI))
676 ↗(On Diff #79876)

E->ops_push_back(lookupOperandLeader(PointerOp, LI, B))

809 ↗(On Diff #79876)
if (II && EI->getNumIndices() == 1 && *EI->idx_begin() == 0) {
978 ↗(On Diff #79876)
if (E == nullptr) {
1270 ↗(On Diff #79876)

Same named variables is asking for trouble

1433 ↗(On Diff #79876)

newline

1572 ↗(On Diff #79876)

Why is this increment not done in the for block?

1680 ↗(On Diff #79876)

Use for-range loop?

for (CongruenceClass *CC : CongruenceClasses])
1827 ↗(On Diff #79876)

Why isn't this increment done in the for block?

silvas added a subscriber: silvas.Dec 8 2016, 11:30 PM

Simon has done a pretty good job with the style review. Once his comments are cleaned up it will be easier to provide further comments.

A couple other stylistic comments and a doc request. I still need to do a walk-through of the code and stuff to provide more in-depth comments.

include/llvm/Transforms/Scalar/GVNExpression.h
241 ↗(On Diff #79876)

PrintEType here and elsewhere.

lib/Transforms/Scalar/NewGVN.cpp
10 ↗(On Diff #79876)

This file comment needs to be signficantly expanded. Remember, lots of people looking at this class might be e.g. people taking a compiler class that want to look at a "real" GVN implementation. Let's make sure come away impressed so that they will want to join LLVM!

At the very least, some citations for the relevant paper and stuff, along with summary of which exact variant of the algorithm are implemented would be good. Also, I think the high-level idea of GVN is simple enough that a high-level from-scratch description would be appropriate. I can help with writing this if you want.

In theory, we can expand this later, but when have you seen a commit improving a file-level comment? The only one I remember was in response to post-commit review asking for an improved file-level comment. So getting it right the first time is actually pretty important.

474 ↗(On Diff #79876)

Are the ifdef's necessary when all that is inside is a DEBUG?

Also, uhm, this needs tests. Maybe you can get away with just adding some more RUN lines to some LegacyGVN tests?

Also, uhm, this needs tests. Maybe you can get away with just adding some more RUN lines to some LegacyGVN tests?

Yes, this is my intention. In the non-upstream branch all the tests have another run line which looks like
RUN: opt -newgvn %s | FileCheck %s. They're not included here just to make the diff smaller.

kariddi added a subscriber: kariddi.Dec 9 2016, 6:54 PM
kariddi added inline comments.
lib/Transforms/Scalar/NewGVN.cpp
1219 ↗(On Diff #79876)

This gets cleared, but the CongruenceClasses seem to be created through "new" and stored in the vector.

Where do they get destroyed?

kariddi added inline comments.Dec 9 2016, 7:17 PM
lib/Transforms/Scalar/NewGVN.cpp
1330 ↗(On Diff #79876)

You are hiding the already defined variable of the same name above. This is slightly confusing while reading the code.

Consider changing this to CurrInstRange or the one above in TotalInstRange or something like that.

Also, uhm, this needs tests. Maybe you can get away with just adding some more RUN lines to some LegacyGVN tests?

Yes, this is my intention. In the non-upstream branch all the tests have another run line which looks like
RUN: opt -newgvn %s | FileCheck %s. They're not included here just to make the diff smaller.

Might it be possible to create a new phab patch now - dependent on this one that includes the NewGVN activation and test changes? Doesn't affect this initial patch but helps everyone see the upcoming effects on tests.

davide updated this revision to Diff 81137.Dec 12 2016, 2:10 PM
davide edited edge metadata.
davide marked 23 inline comments as done.

Thank you all for the comments! New revision attached.

davide added a subscriber: hfinkel.Dec 12 2016, 2:17 PM

Thank you all for the comments! New revision attached.

@hfinkel : Hal, do you plan to review this?

include/llvm/Transforms/Scalar/GVNExpression.h
34 ↗(On Diff #79876)

Done.

47 ↗(On Diff #79876)

To be honest, I prefer Expression. I can change it if you feel strong about it.

62 ↗(On Diff #79876)

Fixed.

83 ↗(On Diff #79876)

Not sure, this doesn't seem to have a terrible compile-time impact. We can move later, if needed.

83 ↗(On Diff #79876)

yeah.

155 ↗(On Diff #79876)

Done.

205 ↗(On Diff #79876)

Done, I think.

444 ↗(On Diff #79876)

Consistently put variables at the top of the class.

lib/Transforms/Scalar/NewGVN.cpp
10 ↗(On Diff #79876)

I agree. Tried to expand it a bit.

136 ↗(On Diff #79876)

Michael preferred ~0U, but from what I see -1 is used everywhere else, so I'm switching back.

459 ↗(On Diff #79876)

Changed, here and everywhere else in the file.

474 ↗(On Diff #79876)

Probably not, removing.

1270 ↗(On Diff #79876)

well, very spread in the new PM port, but I agree with you. I put an underscore at the beginning so that we can distinguish.

1572 ↗(On Diff #79876)

Many other passes do the same, seems like common style.

1680 ↗(On Diff #79876)

Nice catch!

1827 ↗(On Diff #79876)

See comment above.

dberlin added inline comments.Dec 12 2016, 5:52 PM
lib/Transforms/Scalar/NewGVN.cpp
10 ↗(On Diff #79876)

I'm happy to describe the sparse predicated algorithm a bit if you want to add it. I'll touch on the predication/etc bits when we add them.

Traditional GVN algorithms fall into two categories: Congruence partitioning and Hash based.

Hash based GVN's hash the operation performed by an instruction in some fashion, and look it up in a hash table. Anything that hashes the same and is otherwise "congruent" is considered equal. A hash based value numbering is optimistic if it is assumes that everything not in the table is congruent to everything else, and pessimistic if it is assumes everything not in the table is not congruent to everything else.

Congruence partitioning based GVN's start with every value in a single partition, and split the partition as they discover values that are not equal.

Optimistic hash based GVN and congruence partitioning GVN will discover the same set of congruences.

Most compilers nowadays use optimistic hash based approaches. The downside to optimistic hash based value numbering is that it requires reprocessing the entire routine again and again until the hashtables stops changing. This is because value dependences are not tracked well enough to know what must be reprocessed, and values can be involved in cycles (meaning there is no perfect order in which you can process the function to get a correct result). This makes these algorithms non-sparse. There are refinements to these algorithms, such as SCC based value numbering, which only requires iterating SCC's of the SSA graph, but most compilers use the hash table approach.

By contrast, the algorithm is more like the sparse conditional constant propagation algorithm, and uses a worklist of instructions to process. Dependencies between values and instructions are tracked finely enough (through the CongruenceClass structure) that when the value an operation has changes, we add the possibly dependent instructions to the worklist and keep going.

Memory locations s also value numbered by this algorithm. For memory, the goal of the algorithm is to discover the values stored at various memory locations (instead of just what loads are equivalent). Because of this loads and stores are value numbered together (while they are different expression classes, the hash ensures this occurs). MemorySSA is used to value number memory state.

To give a concrete example, given:
1 = MemoryDef(0)
store %a, %ptr

and

MemoryUse (1)
load %ptr

These will be value numbered into the same congruence class, as the memory is the same location with the same value.

This also enables the algorithm to discover equivalences that alias analysis cannot easily do.

A trivial example:

1= MemoryDef(0)
store %a, %ptr
MemoryUse(1)
load %ptr
2 = MemoryDef(1)
store %a, %ptr
MemoryUse(2)
load %ptr

These loads are equivalent, but a simple value numbering will not discover this.

The algorithm we use will discover that the stores store the same value, and thus will say that 1 and 2 are equivalent memory states.

It will then value number
MemoryUse(2)
load %ptr

as if it was
MemoryUse(1)
load %ptr

This enables the algorithm to discover fairly advanced (and even cyclic) equivalences between memory locations, much as it will do for scalars.

The algorithm used also performs unreachable code elimination/etc, similar to how sparse conditional constant propagation works. It optimistically assumes edges are unreachable until proven otherwise, and ignores unreachable values when value numbering phi nodes to create a maximal answer to value equivalence.

In addition to the above this algorithm supports forward propagation, global reassociation, and predication.

A couple more small comments as take another pass looking at the patch.

lib/Transforms/Scalar/NewGVN.cpp
842 ↗(On Diff #81137)

"Don’t duplicate function or class name at the beginning of the comment."

http://llvm.org/docs/CodingStandards.html#doxygen-use-in-documentation-comments

1455 ↗(On Diff #81137)

This is just implementing a lexicographical comparison, right?

If so, I would do:

return std::tie(DFSIn, DFSOut, ...) < std::tie(other.DFSIn, other.DFSOut, ...);
1464 ↗(On Diff #81137)

This seems super sketchy, comparing < on pointers. What's up with that? Won't that make the result nondeterministic?

hfinkel added inline comments.Dec 13 2016, 4:00 PM
include/llvm/Transforms/Scalar/GVNExpression.h
65 ↗(On Diff #81137)

Please explain in this comment why you're not comparing the expression types for loads and stores. This is also somewhat confusing because we've already compared the opcodes.

183 ↗(On Diff #81137)

This looks a bit odd. Shouldn't you check the opcode equality first and then cast to BasicExpression?

lib/Transforms/Scalar/NewGVN.cpp
215 ↗(On Diff #81137)

Do we want to guard this with #ifdef NDEBUG?

460 ↗(On Diff #81137)

Add period after expression.

647 ↗(On Diff #81137)

We also need to add operand bundles too for calls.

davide updated this revision to Diff 81338.Dec 13 2016, 6:12 PM

Another round of comments.

davide added inline comments.Dec 13 2016, 6:14 PM
lib/Transforms/Scalar/NewGVN.cpp
647 ↗(On Diff #81137)

Addressed all your other comments, Hal. I put a FIXME here and I'll review it later (sorry I'm not super familiar with operator bundles and I want to add a test as well).

842 ↗(On Diff #81137)

Done, did a pass over NewGVN.cpp

1455 ↗(On Diff #81137)

Done, it's now much easier to understand, thanks!

hfinkel edited edge metadata.Dec 13 2016, 7:27 PM

A few more comments on the comments, otherwise, I'm fine with committing this and working on it in-tree. Thanks for your work on this!

include/llvm/Transforms/Scalar/GVNExpression.h
66 ↗(On Diff #81338)

What does load coercion mean in this context? Also, for loads and stores we set the opcode to 0 and that should be noted somewhere here.

lib/Transforms/Scalar/NewGVN.cpp
648 ↗(On Diff #81338)

bundle operators -> operand bundles

vsk added a subscriber: vsk.Dec 13 2016, 7:33 PM
vsk added inline comments.
include/llvm/Transforms/Scalar/GVNExpression.h
63 ↗(On Diff #81338)

Could you add a brief comment explaining the significance of the ~0U, ~1U, and ~2U opcodes before using them? In particular, it would be nice to explain why we don't look at 'Other' when Opcode is in {~0,~1}.

Prazek added inline comments.Dec 14 2016, 3:06 AM
include/llvm/Transforms/Scalar/GVNExpression.h
111–114 ↗(On Diff #81338)

It would be better to provide defautl values here

125–126 ↗(On Diff #81338)

and remove it from here.
Also, it seems suspicious that NumOperands argument is not NumOperands, it is actually MaxOperands.

187 ↗(On Diff #81338)

const auto &OE

241 ↗(On Diff #81338)

const auto &OE

This revision was automatically updated to reflect the committed changes.