116 lines · cpp
1//===- llvm/CodeGen/MachineBlockHashInfo.cpp---------------------*- 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-exception6//7//===----------------------------------------------------------------------===//8//9// Compute the hashes of basic blocks.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/CodeGen/MachineBlockHashInfo.h"14#include "llvm/CodeGen/Passes.h"15#include "llvm/InitializePasses.h"16#include "llvm/Target/TargetMachine.h"17 18using namespace llvm;19 20uint64_t hashBlock(const MachineBasicBlock &MBB, bool HashOperands) {21 uint64_t Hash = 0;22 for (const MachineInstr &MI : MBB) {23 if (MI.isMetaInstruction() || MI.isTerminator())24 continue;25 Hash = hashing::detail::hash_16_bytes(Hash, MI.getOpcode());26 if (HashOperands) {27 for (unsigned i = 0; i < MI.getNumOperands(); i++) {28 Hash =29 hashing::detail::hash_16_bytes(Hash, hash_value(MI.getOperand(i)));30 }31 }32 }33 return Hash;34}35 36/// Fold a 64-bit integer to a 16-bit one.37uint16_t fold_64_to_16(const uint64_t Value) {38 uint16_t Res = static_cast<uint16_t>(Value);39 Res ^= static_cast<uint16_t>(Value >> 16);40 Res ^= static_cast<uint16_t>(Value >> 32);41 Res ^= static_cast<uint16_t>(Value >> 48);42 return Res;43}44 45INITIALIZE_PASS(MachineBlockHashInfo, "machine-block-hash",46 "Machine Block Hash Analysis", true, true)47 48char MachineBlockHashInfo::ID = 0;49 50MachineBlockHashInfo::MachineBlockHashInfo() : MachineFunctionPass(ID) {51 initializeMachineBlockHashInfoPass(*PassRegistry::getPassRegistry());52}53 54void MachineBlockHashInfo::getAnalysisUsage(AnalysisUsage &AU) const {55 AU.setPreservesAll();56 MachineFunctionPass::getAnalysisUsage(AU);57}58 59struct CollectHashInfo {60 uint64_t Offset;61 uint64_t OpcodeHash;62 uint64_t InstrHash;63 uint64_t NeighborHash;64};65 66bool MachineBlockHashInfo::runOnMachineFunction(MachineFunction &F) {67 DenseMap<const MachineBasicBlock *, CollectHashInfo> HashInfos;68 uint16_t Offset = 0;69 // Initialize hash components70 for (const MachineBasicBlock &MBB : F) {71 // offset of the machine basic block72 HashInfos[&MBB].Offset = Offset;73 Offset += MBB.size();74 // Hashing opcodes75 HashInfos[&MBB].OpcodeHash = hashBlock(MBB, /*HashOperands=*/false);76 // Hash complete instructions77 HashInfos[&MBB].InstrHash = hashBlock(MBB, /*HashOperands=*/true);78 }79 80 // Initialize neighbor hash81 for (const MachineBasicBlock &MBB : F) {82 uint64_t Hash = HashInfos[&MBB].OpcodeHash;83 // Append hashes of successors84 for (const MachineBasicBlock *SuccMBB : MBB.successors()) {85 uint64_t SuccHash = HashInfos[SuccMBB].OpcodeHash;86 Hash = hashing::detail::hash_16_bytes(Hash, SuccHash);87 }88 // Append hashes of predecessors89 for (const MachineBasicBlock *PredMBB : MBB.predecessors()) {90 uint64_t PredHash = HashInfos[PredMBB].OpcodeHash;91 Hash = hashing::detail::hash_16_bytes(Hash, PredHash);92 }93 HashInfos[&MBB].NeighborHash = Hash;94 }95 96 // Assign hashes97 for (const MachineBasicBlock &MBB : F) {98 const auto &HashInfo = HashInfos[&MBB];99 BlendedBlockHash BlendedHash(fold_64_to_16(HashInfo.Offset),100 fold_64_to_16(HashInfo.OpcodeHash),101 fold_64_to_16(HashInfo.InstrHash),102 fold_64_to_16(HashInfo.NeighborHash));103 MBBHashInfo[&MBB] = BlendedHash.combine();104 }105 106 return false;107}108 109uint64_t MachineBlockHashInfo::getMBBHash(const MachineBasicBlock &MBB) {110 return MBBHashInfo[&MBB];111}112 113MachineFunctionPass *llvm::createMachineBlockHashInfoPass() {114 return new MachineBlockHashInfo();115}116