Details
Diff Detail
- Repository
- rL LLVM
Event Timeline
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) |
lib/Transforms/Scalar/NewGVN.cpp | ||
---|---|---|
1001 ↗ | (On Diff #76658) | There's a bug (well, incompleteness) here that i just noticed 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 :) |
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. |
65 ↗ | (On Diff #76658) | You could call another ctor here like: |
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
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) | This needs to be an anchor as per http://llvm.org/docs/CodingStandards.html#provide-a-virtual-method-anchor-for-classes-in-headers |
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. |
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. |
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.
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? |
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?
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.
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? |
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. |
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.
@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. |
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: and MemoryUse (1) 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) 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 as if it was 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? |
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. |
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! |
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 |
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}. |
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. |
187 ↗ | (On Diff #81338) | const auto &OE |
241 ↗ | (On Diff #81338) | const auto &OE |