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

https://reviews.llvm.org/D70210

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.

4 files changed, 48 insertions, 40 deletions

diff --git a/llvm/test/CodeGen/MIR/AArch64/mirCanonCopyCopyProp.mir b/llvm/test/CodeGen/MIR/AArch64/mirCanonCopyCopyProp.mir
index f39de6c3de7..41396b5ba7b 100644
--- a/llvm/test/CodeGen/MIR/AArch64/mirCanonCopyCopyProp.mir
+++ b/llvm/test/CodeGen/MIR/AArch64/mirCanonCopyCopyProp.mir
@@ -39,8 +39,8 @@ body: |
 
     %42:gpr32 = LDRWui %stack.0, 0 :: (dereferenceable load 8)
 
-    ;CHECK: %namedVReg1352:gpr32 = LDRWui %stack.0, 0 :: (dereferenceable load 8)
-    ;CHECK-NEXT: $w0 = COPY %namedVReg1352
+    ;CHECK: %bb0_11909__1:gpr32 = LDRWui %stack.0, 0 :: (dereferenceable load 8)
+    ;CHECK-NEXT: $w0 = COPY %bb0_11909__1
     ;CHECK-NEXT: RET_ReallyLR implicit $w0
 
     %vreg1234:gpr32 = COPY %42
diff --git a/llvm/test/CodeGen/MIR/AArch64/mirCanonIdempotent.mir b/llvm/test/CodeGen/MIR/AArch64/mirCanonIdempotent.mir
index 3a32303dc52..d393e80df98 100644
--- a/llvm/test/CodeGen/MIR/AArch64/mirCanonIdempotent.mir
+++ b/llvm/test/CodeGen/MIR/AArch64/mirCanonIdempotent.mir
@@ -1,11 +1,11 @@
 # RUN: llc -mtriple=arm64-apple-ios11.0.0 -o - -verify-machineinstrs -run-pass mir-canonicalizer %s | FileCheck %s
 # These Idempotent instructions are sorted alphabetically (based on after the '=')
-# CHECK: %namedVReg4352:gpr64 = MOVi64imm 4617315517961601024
-# CHECK-NEXT: %namedVReg4353:gpr32 = MOVi32imm 408
-# CHECK-NEXT: %namedVReg4354:gpr32 = MOVi32imm 408
-# CHECK-NEXT: %namedVReg4355:gpr64all = IMPLICIT_DEF
-# CHECK-NEXT: %namedVReg4356:fpr64 = FMOVDi 20
-# CHECK-NEXT: %namedVReg4357:fpr64 = FMOVDi 112
+# CHECK: %bb0_17169__1:gpr64 = MOVi64imm 4617315517961601024
+# CHECK-NEXT: %bb0_42274__1:gpr32 = MOVi32imm 408
+# CHECK-NEXT: %bb0_42274__2:gpr32 = MOVi32imm 408
+# CHECK-NEXT: %bb0_18275__1:gpr64all = IMPLICIT_DEF
+# CHECK-NEXT: %bb0_13880__1:fpr64 = FMOVDi 20
+# CHECK-NEXT: %bb0_21467__1:fpr64 = FMOVDi 112
 
 ...
 ---
diff --git a/llvm/test/CodeGen/MIR/AArch64/mirnamer.mir b/llvm/test/CodeGen/MIR/AArch64/mirnamer.mir
index 87b563d2091..e106e107616 100644
--- a/llvm/test/CodeGen/MIR/AArch64/mirnamer.mir
+++ b/llvm/test/CodeGen/MIR/AArch64/mirnamer.mir
@@ -5,10 +5,10 @@ name: foo
 body:             |
   bb.0:
 
-    ;CHECK: bb
-    ;CHECK-NEXT: %namedVReg1353:_(p0) = COPY $d0
-    ;CHECK-NEXT: %namedVReg1352:_(<4 x s32>) = COPY $q0
-    ;CHECK-NEXT: G_STORE %namedVReg1352(<4 x s32>), %namedVReg1353
+    ;CHECK-LABEL: bb.0
+    ;CHECK-NEXT: %bb0_12265__1:_(p0) = COPY $d0
+    ;CHECK-NEXT: %bb0_18308__1:_(<4 x s32>) = COPY $q0
+    ;CHECK-NEXT: G_STORE %bb0_18308__1(<4 x s32>), %bb0_12265__1(p0) :: (store 16)
 
     liveins: $q0, $d0
     %1:fpr(p0) = COPY $d0
@@ -25,20 +25,20 @@ stack:
 body:             |
   bb.0:
 
-    ;CHECK: bb
-    ;CHECK-NEXT: %namedVReg1370:gpr32 = LDRWui
-    ;CHECK-NEXT: %namedVReg1371:gpr32 = MOVi32imm 1
-    ;CHECK-NEXT: %namedVReg1372:gpr32 = LDRWui
-    ;CHECK-NEXT: %namedVReg1373:gpr32 = MOVi32imm 2
-    ;CHECK-NEXT: %namedVReg1359:gpr32 = LDRWui
-    ;CHECK-NEXT: %namedVReg1360:gpr32 = MOVi32imm 3
-    ;CHECK-NEXT: %namedVReg1365:gpr32 = nsw ADDWrr
-    ;CHECK-NEXT: %namedVReg1361:gpr32 = LDRWui
-    ;CHECK-NEXT: %namedVReg1366:gpr32 = nsw ADDWrr
-    ;CHECK-NEXT: %namedVReg1362:gpr32 = MOVi32imm 4
-    ;CHECK-NEXT: %namedVReg1355:gpr32 = nsw ADDWrr
-    ;CHECK-NEXT: %namedVReg1363:gpr32 = LDRWui
-    ;CHECK-NEXT: %namedVReg1364:gpr32 = MOVi32imm 5
+    ;CHECK-LABEL: bb.0
+    ;CHECK-NEXT: %bb0_11909__1:gpr32 = LDRWui
+    ;CHECK-NEXT: %bb0_17251__1:gpr32 = MOVi32imm 1
+    ;CHECK-NEXT: %bb0_11909__2:gpr32 = LDRWui
+    ;CHECK-NEXT: %bb0_44296__1:gpr32 = MOVi32imm 2
+    ;CHECK-NEXT: %bb0_11909__3:gpr32 = LDRWui
+    ;CHECK-NEXT: %bb0_10150__1:gpr32 = MOVi32imm 3
+    ;CHECK-NEXT: %bb0_18184__1:gpr32 = nsw ADDWrr
+    ;CHECK-NEXT: %bb0_11909__4:gpr32 = LDRWui
+    ;CHECK-NEXT: %bb0_18184__2:gpr32 = nsw ADDWrr
+    ;CHECK-NEXT: %bb0_56622__1:gpr32 = MOVi32imm 4
+    ;CHECK-NEXT: %bb0_18184__3:gpr32 = nsw ADDWrr
+    ;CHECK-NEXT: %bb0_11909__5:gpr32 = LDRWui
+    ;CHECK-NEXT: %bb0_74788__1:gpr32 = MOVi32imm 5
 
     %0:gpr32 = LDRWui %stack.0, 0 :: (dereferenceable load 8)
     %1:gpr32 = MOVi32imm 1
@@ -73,12 +73,12 @@ body:             |
   bb.0:
     liveins: $x0, $x1, $d0, $d1
 
-    ;CHECK: bb
-    ;CHECK-NEXT: %namedVReg1355:gpr32 = LDRWui
-    ;CHECK-NEXT: %namedVReg1354:gpr32 = COPY %namedVReg1355
-    ;CHECK-NEXT: %namedVReg1353:gpr32 = COPY %namedVReg1354
-    ;CHECK-NEXT: %namedVReg1352:gpr32 = COPY %namedVReg1353
-    ;CHECK-NEXT: $w0 = COPY %namedVReg1352
+    ;CHECK-LABEL: bb.0:
+    ;CHECK-NEXT: %bb0_11909__1:gpr32 = LDRWui %stack.0, 0
+    ;CHECK-NEXT: %bb0_31408__1:gpr32 = COPY %bb0_11909__1
+    ;CHECK-NEXT: %bb0_14282__1:gpr32 = COPY %bb0_31408__1
+    ;CHECK-NEXT: %bb0_14282__2:gpr32 = COPY %bb0_14282__1
+    ;CHECK-NEXT: $w0 = COPY %bb0_14282__2
 
     %0:gpr32 = LDRWui %stack.0, 0 :: (dereferenceable load 8)
     %1:gpr32 = COPY %0
diff --git a/llvm/test/CodeGen/MIR/AMDGPU/mir-canon-multi.mir b/llvm/test/CodeGen/MIR/AMDGPU/mir-canon-multi.mir
index 67bf92b6081..36d8425e7eb 100644
--- a/llvm/test/CodeGen/MIR/AMDGPU/mir-canon-multi.mir
+++ b/llvm/test/CodeGen/MIR/AMDGPU/mir-canon-multi.mir
@@ -1,18 +1,26 @@
-# RUN: llc -o -  -march=amdgcn  -run-pass mir-canonicalizer  -x mir %s | FileCheck %s
+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -o -  -march=amdgcn  -run-pass mir-canonicalizer  %s | FileCheck %s
 
-# CHECK: %namedVReg4354:vgpr_32 = COPY $vgpr0
-# CHECK: %namedVReg1352:vgpr_32 = COPY %namedVReg4353
-# CHECK-NEXT: %namedVReg1358:vgpr_32 = COPY %namedVReg1361
-# CHECK-NEXT: %namedVReg1359:vgpr_32 = COPY %namedVReg1362
-# CHECK-NEXT: %namedVReg1353:vreg_64 = REG_SEQUENCE %namedVReg4354, %subreg.sub0, %namedVReg1352, %subreg.sub1
-# CHECK-NEXT: %namedVReg1354:sgpr_128 = REG_SEQUENCE %namedVReg4354, %subreg.sub0, %namedVReg1352, %subreg.sub1, %namedVReg1358, %subreg.sub2, %namedVReg1359, %subreg.sub3
 # This tests for the itereator invalidation fix (reviews.llvm.org/D62713)
-# CHECK-NEXT: BUFFER_STORE_DWORD_ADDR64 %namedVReg1352, %namedVReg1353, %namedVReg1354, 0, 0, 0, 0, 0, 0, 0, implicit $exec
 ...
 ---
 name: foo
 body:             |
   bb.0:
+    ; CHECK-LABEL: name: foo
+    ; CHECK: %bb0_43693__1:sreg_32_xm0 = S_MOV_B32 61440
+    ; CHECK: %bb0_13829__1:sreg_32_xm0 = S_MOV_B32 0
+    ; CHECK: %bb0_14481__1:vgpr_32 = COPY $vgpr0
+    ; CHECK: %bb0_18142__1:sgpr_64 = COPY $sgpr0_sgpr1
+    ; CHECK: %bb0_16462__1:sreg_64_xexec = S_LOAD_DWORDX2_IMM %bb0_18142__1, 9, 0, 0
+    ; CHECK: %bb0_89962__1:sreg_64_xexec = S_LOAD_DWORDX2_IMM %bb0_18142__1, 11, 0, 0
+    ; CHECK: %bb0_10035__1:vgpr_32 = COPY %bb0_13829__1
+    ; CHECK: %bb0_18361__1:vgpr_32 = COPY %bb0_16462__1
+    ; CHECK: %bb0_18361__2:vgpr_32 = COPY %bb0_89962__1
+    ; CHECK: %bb0_16181__1:vreg_64 = REG_SEQUENCE %bb0_14481__1, %subreg.sub0, %bb0_10035__1, %subreg.sub1
+    ; CHECK: %bb0_71315__1:sgpr_128 = REG_SEQUENCE %bb0_14481__1, %subreg.sub0, %bb0_10035__1, %subreg.sub1, %bb0_18361__1, %subreg.sub2, %bb0_18361__2, %subreg.sub3
+    ; CHECK: BUFFER_STORE_DWORD_ADDR64 %bb0_10035__1, %bb0_16181__1, %bb0_71315__1, 0, 0, 0, 0, 0, 0, 0, implicit $exec
+    ; CHECK: S_ENDPGM 0
     %10:sreg_32_xm0 = S_MOV_B32 61440
     %11:sreg_32_xm0 = S_MOV_B32 0
     %3:vgpr_32 = COPY $vgpr0