[IR] Add SturcturalHash printer pass

[aidengrossman]

Summary

This patch adds in a StructuralHash printer pass that prints out the
hexadeicmal representation of the hash of a module and all of the
functions within it.

[aeubanks]

llvm/include/llvm/Analysis/StructuralHash.h

2

10

this comment doesn't seem very useful, I'd remove it

llvm/lib/Analysis/StructuralHash.cpp

21

this should be a textual pass parameter, see FUNCTION_PASS_WITH_PARAMS. typically parseSinglePassOption expects foo<bar>, and this pass name is print<foo<bar>>, so you'll need to strip off the print<> before passing the name to parseSinglePassOption

llvm/test/Analysis/StructuralHash/structural-hash-printer.ll

15

this and DETAILED-HASH are the same CHECK lines. did you mean to check that DETAILED-HASH gives two different hashes?

[aidengrossman]

Address reviewer feedback

• Fix top comment typo
• Remove mostly useless header comment
• Switch to using pass options fron the cl::opt in printer pass
• Update test

[aidengrossman]

llvm/lib/Analysis/StructuralHash.cpp

21

Updated. I ended up doing it similar to how it's done for print<memoryssa> where the syntax is print<pass-name><option> which seems to already have support within parseSinglePassOptions and is at least somewhat canonical.

llvm/test/Analysis/StructuralHash/structural-hash-printer.ll

15

The original intention here was just to make sure that they were printing anything at all rather than be flaky in response to a specific hash, but that's a good point. I've adjusted it to specific hashes as that should be rather consistent (other than in response to changes in StructuralHash).

[nikic]

llvm/test/Analysis/StructuralHash/structural-hash-printer.ll

20

Isn't this going to fail on 32-bit, at least when combined with your other patch?

[aidengrossman]

Address reviewer feedback

• Update test hashes based on most recent revision of earlier patch in stack
• Make test require 64 bit architecture to prevent failures on 32 bit arches.

[aidengrossman]

Split lit test

[aidengrossman]

llvm/test/Analysis/StructuralHash/structural-hash-printer.ll

20

Yes. I meant to fix this but hadn't gotten around to it yet. I've split the test into two files, one marked as REQUIRE; llvm-64-bits. I check both hashes on both platforms (but regex for the detailed hash on the non-64-bit-only test) and check for an exact hash on the 64 bit platform. I think that should provide a decent amount of test coverage.

[aidengrossman]

Update test that I forgot to save before committing.

[nikic]

llvm/lib/Passes/PassBuilder.cpp

1098

For pass options, just detailed would be a more typical name.

[nikic]

It would probably make sense to move your existing unit test coverage over to the printer pass.

[aidengrossman]

In D158317#4611131, @nikic wrote:

It would probably make sense to move your existing unit test coverage over to the printer pass.

I think it would be difficult to express a lot of the StructuralHash test cases as lit style tests. A lot of the functionality that is tested is whether or not hashes are different for two slightly different functions rather than their exact values which is very feasible to do in a unit test and possible to do in a lit test but a little bit less elegant (more test churn if the StructuralHash implementation changes, dealing with 32/64-bit differences) I would think. Maybe I'm missing something though?

[nikic]

In D158317#4611182, @aidengrossman wrote:

In D158317#4611131, @nikic wrote:

It would probably make sense to move your existing unit test coverage over to the printer pass.

I think it would be difficult to express a lot of the StructuralHash test cases as lit style tests. A lot of the functionality that is tested is whether or not hashes are different for two slightly different functions rather than their exact values which is very feasible to do in a unit test and possible to do in a lit test but a little bit less elegant (more test churn if the StructuralHash implementation changes, dealing with 32/64-bit differences) I would think. Maybe I'm missing something though?

That's a good point, but ... what's the point of this pass if we can't use it for testing?

[aidengrossman]

Address reviewer feedback

• Switch pass option name to detailed rather than the much more verbose enable-detailed-structural-hash

[aidengrossman]

In D158317#4611235, @aidengrossman wrote:

Address reviewer feedback

• Switch pass option name to detailed rather than the much more verbose enable-detailed-structural-hash

I'm interested in having a consistent textual interface to expose IR hashes for some downstream analysis and figured upstreaming it would add in a little bit of test coverage (although not be the bulk of it) and might be useful if someone else wants similar data.

[aidengrossman]

Bump on this patch when reviewers have a chance. Thanks!

[aidengrossman]

Skip printing hashes of function declarations.

[aeubanks]

llvm/test/Analysis/StructuralHash/structural-hash-printer.ll

18

seems unfortunate to hardcode specific hashes, can we instead do something like

CHECK-NEXT: Function f1 Hash: [[H:([a-z0-9]{16})]]
CHECK-NEXT: Function f2 Hash: [[H:([a-z0-9]{16})]]

DETAILED-NEXT: Function f1 Hash: [[H:([a-z0-9]{16})]]
DETAILED-NOT: Function f2 Hash: [[H]]
DETAILED-NEXT: Function f2 Hash: {{([a-z0-9]{16})}}

[aidengrossman]

Address reviewer feedback

• Switch main test to use regular expressions and lit variables for

verification that hashes are correct.

llvm/test/Analysis/StructuralHash/structural-hash-printer.ll

18

That is definitely an elegant way of doing that. I hadn't seen substitution blocks before. Thanks for pointing them out! I've left the exact detailed hash values in the other test file as I still think it's important to test that the values are stable across runs/machines matching the criteria to avoid accidentally hashing a pointer. If a different from of testing for that is desired, I can change it up though.

[aeubanks]

lg with one comment

if the test does turn out to be annoying to constantly update we can revisit

llvm/test/Analysis/StructuralHash/structural-hash-detailed.ll

11 ↗

(On Diff #554039)

add a comment about expecting the number to be stable across runs

[aeubanks]

llvm/test/Analysis/StructuralHash/structural-hash-detailed.ll

11 ↗

(On Diff #554039)

actually I just had the idea that you can run it twice and diff the outputs to make sure they're the same, that's way more resistant to random changes

[aidengrossman]

llvm/test/Analysis/StructuralHash/structural-hash-detailed.ll

11 ↗

(On Diff #554039)

That's definitely a better way of doing it. Thanks for the suggestion! I'll push a commit up with that change. It won't show up locally on some of the machines I work on because they have ASLR disabled, but all (or at least most) of the buildbots should have that enabled which is what matters more for coverage.

llvm/include/llvm/Analysis/StructuralHash.h

+//=- StructuralHash.h - Structural Hash Printing --*- C++ -*-----------------=//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_STRUCTURALHASH_H
+#define LLVM_ANALYSIS_STRUCTURALHASH_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+/// Printer pass for  StructuralHashes
+class StructuralHashPrinterPass
+    : public PassInfoMixin<StructuralHashPrinterPass> {
+  raw_ostream &OS;
+  bool EnableDetailedStructuralHash;
+
+public:
+  explicit StructuralHashPrinterPass(raw_ostream &OS, bool Detailed)
+      : OS(OS), EnableDetailedStructuralHash(Detailed) {}
+
+  PreservedAnalyses run(Module &M, ModuleAnalysisManager &MAM);
+};
+
+} // namespace llvm
+
+#endif // LLVM_ANALYSIS_STRUCTURALHASH_H

llvm/lib/Analysis/CMakeLists.txt

add_llvm_component_library(LLVMAnalysis
   RegionPrinter.cpp
   ReplayInlineAdvisor.cpp
   ScalarEvolution.cpp
   ScalarEvolutionAliasAnalysis.cpp
   ScalarEvolutionDivision.cpp
   ScalarEvolutionNormalization.cpp
   StackLifetime.cpp
   StackSafetyAnalysis.cpp
+  StructuralHash.cpp
   SyntheticCountsUtils.cpp
   TFLiteUtils.cpp
   TargetLibraryInfo.cpp
   TargetTransformInfo.cpp
   TensorSpec.cpp
   Trace.cpp
   TrainingLogger.cpp
   TypeBasedAliasAnalysis.cpp

llvm/lib/Analysis/StructuralHash.cpp

+//===- StructuralHash.cpp - Function Hash Printing ------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines the StructuralHashPrinterPass which is used to show
+// the structural hash of all functions in a module and the module itself.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/StructuralHash.h"
+#include "llvm/IR/StructuralHash.h"
+#include "llvm/Support/CommandLine.h"
+
+using namespace llvm;
+
+PreservedAnalyses StructuralHashPrinterPass::run(Module &M,
+                                                 ModuleAnalysisManager &MAM) {
+  OS << "Module Hash: "
+     << Twine::utohexstr(StructuralHash(M, EnableDetailedStructuralHash))
+     << "\n";
+  for (Function &F : M) {
+    OS << "Function " << F.getName() << " Hash: "
+       << Twine::utohexstr(StructuralHash(F, EnableDetailedStructuralHash))
+       << "\n";
+  }
+  return PreservedAnalyses::all();
+}

llvm/lib/Passes/PassBuilder.cpp

 //===- Parsing and selection of pass pipelines ----------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 /// \file

 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ProfileSummaryInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScopedNoAliasAA.h"
 #include "llvm/Analysis/StackLifetime.h"
 #include "llvm/Analysis/StackSafetyAnalysis.h"
+#include "llvm/Analysis/StructuralHash.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/TypeBasedAliasAnalysis.h"
 #include "llvm/Analysis/UniformityAnalysis.h"
 #include "llvm/CodeGen/HardwareLoops.h"
 #include "llvm/CodeGen/TypePromotion.h"
 #include "llvm/IR/DebugInfo.h"
 #include "llvm/IR/Dominators.h"
if (ParamName.consume_front("profile-filename=")) {
       return make_error<StringError>(
           formatv("invalid MemProfUse pass parameter '{0}' ", ParamName).str(),
           inconvertibleErrorCode());
     }
   }
   return Result;
 }
 
+Expected<bool> parseStructuralHashPrinterPassOptions(StringRef Params) {
+  return parseSinglePassOption(Params, "enable-detailed-structural-hash",
+                               "StructuralHashPrinterPass");
+}
+
 } // namespace
 
 /// Tests whether a pass name starts with a valid prefix for a default pipeline
 /// alias.
 static bool startsWithDefaultPipelineAliasPrefix(StringRef Name) {
   return Name.startswith("default") || Name.startswith("thinlto") ||
          Name.startswith("lto");
 }

llvm/lib/Passes/PassRegistry.def

MODULE_PASS_WITH_PARAMS("embed-bitcode",
                         "thinlto;emit-summary")
 MODULE_PASS_WITH_PARAMS("memprof-use",
                          "MemProfUsePass",
                         [](std::string Opts) {
                           return MemProfUsePass(Opts);
                         },
                         parseMemProfUsePassOptions,
                         "profile-filename=S")
+MODULE_PASS_WITH_PARAMS("print<structural-hash>",
+                        "StructuralHashPrinterPass",
+                        [](bool EnableDetailedStructuralHash) {
+                          return StructuralHashPrinterPass(
+                              dbgs(),
+                              EnableDetailedStructuralHash);
+                        },
+                        parseStructuralHashPrinterPassOptions,
+                        "enable-detailed-structural-hash")
 #undef MODULE_PASS_WITH_PARAMS
 
 #ifndef CGSCC_ANALYSIS
 #define CGSCC_ANALYSIS(NAME, CREATE_PASS)
 #endif
 CGSCC_ANALYSIS("no-op-cgscc", NoOpCGSCCAnalysis())
 CGSCC_ANALYSIS("fam-proxy", FunctionAnalysisManagerCGSCCProxy())
 CGSCC_ANALYSIS("pass-instrumentation", PassInstrumentationAnalysis(PIC))

llvm/test/Analysis/StructuralHash/structural-hash-printer.ll

+; RUN: opt -passes='print<structural-hash>' -disable-output %s 2>&1 | FileCheck %s
+; RUN: opt -passes='print<structural-hash><enable-detailed-structural-hash>' -disable-output %s 2>&1 | FileCheck %s -check-prefix=DETAILED-HASH
+
+define i64 @f1(i64 %a) {
+  %b = add i64 %a, 1
+  ret i64 %b
+}
+
+define i32 @f2(i32 %a) {
+  %b = add i32 %a, 2
+  ret i32 %b
+}
+
+; CHECK: Module Hash: 39c8037f62da229
+; CHECK: Function f1 Hash: b677567fe628d557
+; CHECK: Function f2 Hash: b677567fe628d557
+
+; DETAILED-HASH: Module Hash: 4319a994e79f670f
+; DETAILED-HASH: Function f1 Hash: 7c3de1848de089eb
+; DETAILED-HASH: Function f2 Hash: e8f145a33b501984
+