llvm/lib/IR/StructuralHash.cpp

   1 //===-- StructuralHash.cpp - IR Hash for expensive checks -------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9
  10 #ifdef EXPENSIVE_CHECKS
  11
  12 #include "llvm/IR/StructuralHash.h"
  13 #include "llvm/IR/Function.h"
  14 #include "llvm/IR/Module.h"
  15
  16 using namespace llvm;
  17
  18 namespace {
  19 namespace details {
  20
  21 // Basic hashing mechanism to detect structural change to the IR, used to verify
  22 // pass return status consistency with actual change. Loosely copied from
  23 // llvm/lib/Transforms/Utils/FunctionComparator.cpp
  24
  25 class StructuralHash {
  26   uint64_t Hash = 0x6acaa36bef8325c5ULL;
  27
  28   void update(uint64_t V) { Hash = hashing::detail::hash_16_bytes(Hash, V); }
  29
  30 public:
  31   StructuralHash() = default;
  32
  33   void update(const Function &F) {
  34     if (F.empty())
  35       return;
  36
  37     update(F.isVarArg());
  38     update(F.arg_size());
  39
  40     SmallVector<const BasicBlock *, 8> BBs;
  41     SmallPtrSet<const BasicBlock *, 16> VisitedBBs;
  42
  43     BBs.push_back(&F.getEntryBlock());
  44     VisitedBBs.insert(BBs[0]);
  45     while (!BBs.empty()) {
  46       const BasicBlock *BB = BBs.pop_back_val();
  47       update(45798); // Block header
  48       for (auto &Inst : *BB)
  49         update(Inst.getOpcode());
  50
  51       const Instruction *Term = BB->getTerminator();
  52       for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
  53         if (!VisitedBBs.insert(Term->getSuccessor(i)).second)
  54           continue;
  55         BBs.push_back(Term->getSuccessor(i));
  56       }
  57     }
  58   }
  59
  60   void update(const Module &M) {
  61     for (const Function &F : M)
  62       update(F);
  63   }
  64
  65   uint64_t getHash() const { return Hash; }
  66 };
  67
  68 } // namespace details
  69
  70 } // namespace
  71
  72 uint64_t llvm::StructuralHash(const Function &F) {
  73   details::StructuralHash H;
  74   H.update(F);
  75   return H.getHash();
  76 }
  77
  78 uint64_t llvm::StructuralHash(const Module &M) {
  79   details::StructuralHash H;
  80   H.update(M);
  81   return H.getHash();
  82 }
  83
  84 #endif