This is an archive of the discontinued LLVM Phabricator instance.

[MIRVRegNamer] MachineInstr StableHashing.
ClosedPublic

Authored by plotfi on Sep 1 2020, 8:34 AM.

Details

Summary

Introducing Stable Hashing, based on Fowler–Noll–Vo hash function.
This hashing scheme has been useful out of tree, and I want to start experimenting with it.
Specifically I want to experiment on the MIRVRegNamer, MIRCanononicalizer, and eventually the MachineOutliner.

This diff is a first step, that optionally brings stable hashing to the MIRVRegNamer (and as a result, the MIRCanonicalizer).
We've tested this hashing scheme on a lot of MachineOperand types that llvm::hash_value can not handle in a stable manner.

Diff Detail

Event Timeline

plotfi created this revision.Sep 1 2020, 8:34 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 1 2020, 8:34 AM
plotfi requested review of this revision.Sep 1 2020, 8:34 AM
plotfi updated this revision to Diff 289233.Sep 1 2020, 11:30 AM
plotfi updated this revision to Diff 289252.Sep 1 2020, 12:37 PM
lanza added a comment.Sep 2 2020, 10:44 AM

Other than the one comment LGTM.

llvm/lib/CodeGen/MachineStableHash.cpp
151

That seems kinda error prone. VRegRenamer::getInstructionOpcodeHash would just propagate forward a failure blindly.

plotfi updated this revision to Diff 289746.Sep 3 2020, 9:22 AM
plotfi marked an inline comment as done.
plotfi added inline comments.
llvm/lib/CodeGen/MachineStableHash.cpp
151

The namer is resigned to handle collisions, but yeah I agree. If a hash comes out as 0 it should hit an assert.

arsenm added a subscriber: arsenm.Sep 3 2020, 9:27 AM
arsenm added inline comments.
llvm/include/llvm/CodeGen/MachineStableHash.h
2

Extra blank line

llvm/lib/CodeGen/MIRVRegNamerUtils.cpp
66

Why substr?

plotfi marked an inline comment as done.Sep 3 2020, 9:37 AM
plotfi added inline comments.
llvm/lib/CodeGen/MIRVRegNamerUtils.cpp
66

Mostly because the existing hash (see end of the function) is a 5 char substring. Thanks for reviewing this @arsenm You think this should be a 7 char hash?

plotfi updated this revision to Diff 289748.Sep 3 2020, 9:38 AM
plotfi marked an inline comment as done.

Is there any way to test the hash itself on certain instructions?

e.g. verify that two instructions with different address spaces get a different hash?

llvm/lib/CodeGen/MIRVRegNamerUtils.cpp
62

Style nit: usually I've seen things like this formatted like below in the LLVM codebase:

/* HashVRegs = */ true, ...
llvm/lib/CodeGen/MachineStableHash.cpp
67

nit: somewhat shorter

183

static_cast for greppability?

Is there any way to test the hash itself on certain instructions?

e.g. verify that two instructions with different address spaces get a different hash?

I think most of the tests where I added the -mir-vreg-namer-use-stable-hash line are checking for that. For instance the ; CHECK-NEXT: %bb0_{{[0-9]+}}__1: lines pretty much ensure that the __1 is there, which means there was not more than one collision.

paquette accepted this revision.Sep 3 2020, 10:09 AM

Oh wait the tests already test what I was concerned about. LGTM with minor nits.

(although decoupling the tests from mir-canon would be nice, since this is supposed to be standalone)

This revision is now accepted and ready to land.Sep 3 2020, 10:09 AM

Oh wait the tests already test what I was concerned about. LGTM with minor nits.

(although decoupling the tests from mir-canon would be nice, since this is supposed to be standalone)

Cool. I am planning to write some tests for the MO types the MIRCanon tests aren't already covering.

plotfi updated this revision to Diff 289763.Sep 3 2020, 10:48 AM
plotfi marked 4 inline comments as done.
This revision was landed with ongoing or failed builds.Sep 3 2020, 1:13 PM
This revision was automatically updated to reflect the committed changes.