Page MenuHomePhabricator

[MirNamer][Canonicalizer]: Perform instruction semantic based renaming
ClosedPublic

Authored by aditya_nandakumar on Nov 13 2019, 2:35 PM.

Details

Summary

Previously:

  • Due to sensitivity of the algorithm with gaps, and extra instructions, when diffing, often we see naming being off by a few. Makes the diff unreadable even for tests with 7 and 8 instructions respectively.
  • Naming can change depending on candidates (and order of picking candidates). Suddenly if there's one extra instruction somewhere, the entire subtree would be named completely differently.
  • No consistent naming of similar instructions which occur in different functions. If we try to do something like count the frequency distribution of various differences across suite, then the above sensitivity issues are going to result in poor results.

Instead:

  • Name instruction based on semantics of the instruction (hash of the opcode and operands). Essentially for a given instruction that occurs in any module/function it'll be named similarly (ie semantic). This has some nice properties
    • Can easily look at many instructions and just check the hash and if they're named similarly, then it's the same instruction. Makes it very easy to spot the same instruction both multiple times, as well as across many functions (useful for frequency distribution).
    • Independent of traversal/candidates/depth of graph. No need to keep track of last index/gaps/skip count etc.
    • No off by few issues with diffs. I've tried the old vs new implementation in files ranging from 30 to 700 instructions. In both cases with the old algorithm, diffs are a sea of red, where as for the semantic version, in both cases, the diffs line up beautifully.
    • Simplified implementation of the main loop (simple iteration) , no keep track of what's visited and not.
  • Handle collision just by incrementing a counter. Roughly bb[N]_hash_[CollisionCount].

Additionally with the new implementation, we can probably avoid doing the hoisting of instructions to various places, as they'll likely be named the same resulting in differences only based on collision (ie regardless of whether the instruction is hoisted or not/close to use or not, it'll be named the same hash which should result in use of the instruction be identical with the only change being the collision count) which is very easy to spot visually.

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptNov 13 2019, 2:35 PM
aditya_nandakumar added a subscriber: volkan.
aditya_nandakumar removed a subscriber: volkan.

Initial comments posted. Nice work, especially on the operand/vreg-def-opcode hashing idea (which localizes lot of the difference better that before). More code comments and perhaps some ports of downstream test cases would be greatly appreciated. I think we should work together to cleanup or remove some of this stuff through a couple NFC commits so that the diff is a little easier to follow and mostly consists of what was added (with the stuff removed being removed in a separate commit).

llvm/lib/CodeGen/MIRCanonicalizerPass.cpp
441

Is there anything specifically that is needed from MIRCanonicalizerPass Given this deletion here? Can you use MIRNamerPass as your base instead and do this deletion in a later NFC commit if necessary?

llvm/lib/CodeGen/MIRVRegNamerUtils.cpp
45

Might want to consider a StringMap

71–82

Comments please.

81

I think the candidate walk code can be left alone here, and removed in an NFC if really necessary.

88

llvm_unreachable please.

106

I like this linear approach but I might like to keep the tree based approach as well as a toggle until we can add more tests. In the tree based approach I was trying to do the canonicalization based on the chain of operations that flow into a side effect, where here the side effects are renaming barriers? On second thought, I really like the hashing approach on the VReg-Def opcode and if you are confident it wont result in too may cases where a difference that should have remained is lost, I'd be fine with replacing all of this walking business.

Comments (and perhaps some brief MIR snippets) on how this renaming mechanism works would be really nice to have as well.

From what I understand, you have many test cases downstream. Can these be ported to aarch64 to bolster the testing upstream? Even the tests with 7 and 8 instructions can be useful, and I'd assume shouldn't be too difficult to port to a supported downstream target? Does this sound reasonable to you @aditya_nandakumar @bogner ??

llvm/lib/CodeGen/MIRVRegNamerUtils.h
37

Did this need to me moved from MIRVRegNamerUtils.cpp to MIRVRegNamerUtils.h? Can he be done in a NFC commit? On top of that, this appears to be a copy paste from https://reviews.llvm.org/D70029. Would you like to work with me on massaging these changes along D70029 into place here?

41

Another copy paste from D70029. CurrentBBNumber is never incremented or really used for anything of import here. Why is it included in this diff?

77–89

Comment please. It wait for D70029 to solidify and land.

plotfi requested changes to this revision.Nov 13 2019, 10:09 PM
This revision now requires changes to proceed.Nov 13 2019, 10:09 PM
plotfi added inline comments.Nov 13 2019, 10:23 PM
llvm/lib/CodeGen/MIRVRegNamerUtils.cpp
81

How do you guarantee that two different vregs don't resolve to the same "HashOperand" value? Because can't the opcode of two different def instructions happen to be the same? Is it just highly unlikely because you are also hashing the operands of the entire instruction together?

aditya_nandakumar marked 10 inline comments as done.Nov 14 2019, 6:08 PM
aditya_nandakumar added inline comments.
llvm/lib/CodeGen/MIRCanonicalizerPass.cpp
441

The change affects both. This also creates a bunch of new vreg names and changes the names with no benefit - the names have been already created with many useful properties and this undoes that.

llvm/lib/CodeGen/MIRVRegNamerUtils.cpp
45

Mostly followed the style which is using std containers in the rest of this file.

71–82

Comments in the header.

81

Consider this sequence.
On one file you have

%0 = COPY $x0
%1 = LDIMM 25
%2 = ADD %0, %1
%3 = SUB %2, 42

On the other side you have

%0 = COPY $x1
%1 = LDIMM 26
%2 = ADD %0, %1
%3 = SUB %2, 42

Clearly the add is identical on both sides and is not that interesting - essentially it's an add from a LDIMM and a COPY. It's possible that those values might be different, but as far as the ADD is concerned, it's sufficient to say that for both sides ADD is doing something similar and is not the source of a diff. Add's VReg name will show identical on both cases, but sources will appear different (due to different names). However each of %0 and %1 would differ in how they are named and will show up as the diff. Sub will finally look identical. In general we want to capture the diff in the very first places they happen and not beyond that.
After renaming LHS would be,

%hash1 = COPY $x0
%hash2 = LDIMM 25
%hash3 = ADD %hash1, %hash2
%hash7 = SUB %hash3, 0

RHS would be

%hash4 = COPY $x1
%hash5 = LDIMM 26
%hash3 = ADD %hash4, %hash5
%hash7 = SUB %hash3, 0

Now when you diff those, the ADD is not the one that's different, but the first two instructions are. So they will show up nicely in the diff, but the ADD will appear identical with respect to destination and opcode, but will differ from sources. The SUB in both will be identical and will disappear from the context of the diff as it's not interesting. Now even if you have additional instruction somewhere in the instruction stream in either the LHS or the RHS side, the naming of this won't change and will point out the differences nicely.

81

I removed this as there will be no more users of this method.

88

That unfortunately won't work as we are not explicitly handling all variants of MachineOperand Kinds here. There are some challenges that can be solved (bb naming scheme) when dealing with PHIS ie how to hash them without using the name . There maybe other cases where we want to differentiate special operands. Right now we uniquely differentiate immediate and regs, but we can't really assert on any of the others.

106

In general hash collisions are resolved similarly on both sides of a diff and the hash collision renaming will also happen similarly on both sides of the diff (just incrementing numbers). This will line up really well for diffs. Additionally with the hashing method, just when you're staring at two equivalent pieces of code, just by looking at the reg name that is a hash, you can just assume that they're likely equivalent instructions and move your focus elsewhere.
In general, due to the disadvantages of the previous algorithm and the advantages of this approach, there should be no need to keep both approaches.
Regarding tests, there's sufficient coverage. The core algorithm is simple - hash instruction oeprands and rename based on the hash(which capture the semantics of the instruction). It's evident that this works correctly (look at MIR/AArch64/mirCanonIdempotent.mir included in this patch where two of the same MOV instructions are renamed correctly)

# CHECK-NEXT: %bb0_42274__1:gpr32 = MOVi32imm 408
# CHECK-NEXT: %bb0_42274__2:gpr32 = MOVi32imm 408

The only thing adding more tests would help with is we tie that up some diffing tool and make sure that the core strategy still works. Otherwise, it will be quite identical to the ones we already have here. I'll still try to come up with some screenshots of the two approaches and attach it to the review.

llvm/lib/CodeGen/MIRVRegNamerUtils.h
37

I initially used that as the base but forgot to remove them as it's not needed due to the new algorithm. As this abstraction is not really needed any more, I'll go ahead and remove this.
For the new algorithm the only thing we need is RSE_Reg and if we have just one variant, there's no need for an enum.

41

It's used for the renaming of the regs - Each instruction is named as "bb<BlockNum>_hash_<collision_counter>". The BlockNum is obtained by just saying getCurrentBlockNumber().
It's incremented in the top level renameRegs for each block that you visit.

77–89

There's not much that's taken from D70029 besides this method name and the CurrentBBNumber. Because of the differences in how instructions are named and the algorithm changes, there's no need to wait for that patch. In fact, I just realized that I can simplify this a little more by removing some of the abstractions that we don't need any more.

I missed the comment on this one. Thanks for catching it.

bogner accepted this revision.Nov 14 2019, 6:08 PM

LGTM once Puyan's feedback is addressed

llvm/lib/CodeGen/MIRVRegNamerUtils.cpp
84–88

As far as I understand this can't really be replaced with an assert as is, since things like basic block ids are being deliberately dropped here. Can you explicitly handle the cases that we really want to drop from the hash or at least update this comment to explain? I realize it might make sense to always return something, since the only effect is more collisions, but the comment reads as if you think it's an error to get here.

106

This is still doing the traversal in a sense, just a bit more implicitly while we calculate the instruction hash. The nice thing here is that the hash is stable enough that it doesn't matter where we start from, so we can just walk the instructions linearly and it ends up looking a bit simpler.

We don't really have many interestingly distinct test cases downstream - the test cases below cover the functional testing pretty well. What we do have is some experience using this on large functions that were compiled with and without GlobalISel, which have shown that this hashing approach helps quite a bit.

Addressed some feedback, removed some abstractions that are unused, added more comments.

plotfi accepted this revision.Nov 14 2019, 11:51 PM

Diff looks cleaner. Since you guys are the primary clients, LGTM.

This revision is now accepted and ready to land.Nov 14 2019, 11:51 PM
plotfi added inline comments.Nov 19 2019, 11:59 PM
llvm/lib/CodeGen/MIRNamerPass.cpp
61

Where is the BB# being set here? All the BB#s will be 0 as far as I can tell.

aditya_nandakumar marked an inline comment as done.Nov 20 2019, 12:17 AM
aditya_nandakumar added inline comments.
llvm/lib/CodeGen/MIRNamerPass.cpp
61

Yup - you're right. While trying to refactor I removed a CurrentBBNo = BBNo++ or something equivalent that I had in my tree. Good catch. Thanks.
I'll have a patch ready for this part soon.