IRSimilarityIdentifier.h

//===- IRSimilarityIdentifier.h - Find similarity in a module --------------==//
//
// 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
// Interface file for the IRSimilarityIdentifier for identifying similarities in
// IR including the IRInstructionMapper, which maps an Instruction to unsigned
// integers.
//
// Two sequences of instructions are called "similar" if they perform the same
// series of operations for all inputs.
//
// \code
// %1 = add i32 %a, 10
// %2 = add i32 %a, %1
// %3 = icmp slt icmp %1, %2
// \endcode
//
// and
//
// \code
// %1 = add i32 11, %a
// %2 = sub i32 %a, %1
// %3 = icmp sgt icmp %2, %1
// \endcode
//
// ultimately have the same result, even if the inputs, and structure are
// slightly different.
//
// For instructions, we do not worry about operands that do not have fixed
// semantic meaning to the program.  We consider the opcode that the instruction
// has, the types, parameters, and extra information such as the function name,
// or comparison predicate.  These are used to create a hash to map instructions
// to integers to be used in similarity matching in sequences of instructions
//
// Terminology:
// An IRSimilarityCandidate is a region of IRInstructionData (wrapped
// Instructions), usually used to denote a region of similarity has been found.
//
// A SimilarityGroup is a set of IRSimilarityCandidates that are structurally
// similar to one another.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H
#define LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H

#include "llvm/IR/InstVisitor.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/PassManager.h"
#include "llvm/Pass.h"
#include "llvm/Support/Allocator.h"

namespace llvm {
class Module;

namespace IRSimilarity {

struct IRInstructionDataList;

/// This represents what is and is not supported when finding similarity in
/// Instructions.
///
/// Legal Instructions are considered when looking at similarity between
/// Instructions.
///
/// Illegal Instructions cannot be considered when looking for similarity
/// between Instructions. They act as boundaries between similarity regions.
///
/// Invisible Instructions are skipped over during analysis.
// TODO: Shared with MachineOutliner
enum InstrType { Legal, Illegal, Invisible };

/// This provides the utilities for hashing an Instruction to an unsigned
/// integer. Two IRInstructionDatas produce the same hash value when their
/// underlying Instructions perform the same operation (even if they don't have
/// the same input operands.)
/// As a more concrete example, consider the following:
///
/// \code
/// %add1 = add i32 %a, %b
/// %add2 = add i32 %c, %d
/// %add3 = add i64 %e, %f
/// \endcode
///
// Then the IRInstructionData wrappers for these Instructions may be hashed like
/// so:
///
/// \code
/// ; These two adds have the same types and operand types, so they hash to the
/// ; same number.
/// %add1 = add i32 %a, %b ; Hash: 1
/// %add2 = add i32 %c, %d ; Hash: 1
/// ; This add produces an i64. This differentiates it from %add1 and %add2. So,
/// ; it hashes to a different number.
/// %add3 = add i64 %e, %f; Hash: 2
/// \endcode
///
///
/// This hashing scheme will be used to represent the program as a very long
/// string. This string can then be placed in a data structure which can be used
/// for similarity queries.
///
/// TODO: Handle types of Instructions which can be equal even with different
/// operands. (E.g. comparisons with swapped predicates.)
/// TODO: Handle CallInsts, which are only checked for function type
/// by \ref isSameOperationAs.
/// TODO: Handle GetElementPtrInsts, as some of the operands have to be the
/// exact same, and some do not.
struct IRInstructionData
    : ilist_node<IRInstructionData, ilist_sentinel_tracking<true>> {

  /// The source Instruction that is being wrapped.
  Instruction *Inst = nullptr;
  /// The values of the operands in the Instruction.
  SmallVector<Value *, 4> OperVals;
  /// The legality of the wrapped instruction. This is informed by InstrType,
  /// and is used when checking when two instructions are considered similar.
  /// If either instruction is not legal, the instructions are automatically not
  /// considered similar.
  bool Legal = false;

  /// This is only relevant if we are wrapping a CmpInst where we needed to
  /// change the predicate of a compare instruction from a greater than form
  /// to a less than form.  It is None otherwise.
  Optional<CmpInst::Predicate> RevisedPredicate;

  /// This is only relevant if we are wrapping a CallInst. If we are requiring
  /// that the function calls have matching names as well as types, and the
  /// call is not an indirect call, this will hold the name of the function.  If
  /// it is an indirect string, it will be the empty string.  However, if this
  /// requirement is not in place it will be the empty string regardless of the
  /// function call type.  The value held here is used to create the hash of the
  /// instruction, and check to make sure two instructions are close to one
  /// another.
  Optional<std::string> CalleeName;

  /// This structure holds the distances of how far "ahead of" or "behind" the
  /// target blocks of a branch, or the incoming blocks of a phi nodes are.
  /// If the value is negative, it means that the block was registered before
  /// the block of this instruction in terms of blocks in the function.
  /// Code Example:
  /// \code
  /// block_1:
  ///   br i1 %0, label %block_2, label %block_3
  /// block_2:
  ///   br i1 %1, label %block_1, label %block_2
  /// block_3:
  ///   br i1 %2, label %block_2, label %block_1
  /// ; Replacing the labels with relative values, this becomes:
  /// block_1:
  ///   br i1 %0, distance 1, distance 2
  /// block_2:
  ///   br i1 %1, distance -1, distance 0
  /// block_3:
  ///   br i1 %2, distance -1, distance -2
  /// \endcode
  /// Taking block_2 as our example, block_1 is "behind" block_2, and block_2 is
  /// "ahead" of block_2.
  SmallVector<int, 4> RelativeBlockLocations;

  /// Gather the information that is difficult to gather for an Instruction, or
  /// is changed. i.e. the operands of an Instruction and the Types of those
  /// operands. This extra information allows for similarity matching to make
  /// assertions that allow for more flexibility when checking for whether an
  /// Instruction performs the same operation.
  IRInstructionData(Instruction &I, bool Legality, IRInstructionDataList &IDL);
  IRInstructionData(IRInstructionDataList &IDL);

  /// Fills data stuctures for IRInstructionData when it is constructed from a
  // reference or a pointer.
  void initializeInstruction();

  /// Get the predicate that the compare instruction is using for hashing the
  /// instruction. the IRInstructionData must be wrapping a CmpInst.
  CmpInst::Predicate getPredicate() const;

  /// Get the callee name that the call instruction is using for hashing the
  /// instruction. The IRInstructionData must be wrapping a CallInst.
  StringRef getCalleeName() const;

  /// A function that swaps the predicates to their less than form if they are
  /// in a greater than form. Otherwise, the predicate is unchanged.
  ///
  /// \param CI - The comparison operation to find a consistent preidcate for.
  /// \return the consistent comparison predicate. 
  static CmpInst::Predicate predicateForConsistency(CmpInst *CI);

  /// For an IRInstructionData containing a branch, finds the
  /// relative distances from the source basic block to the target by taking
  /// the difference of the number assigned to the current basic block and the
  /// target basic block of the branch.
  ///
  /// \param BasicBlockToInteger - The mapping of basic blocks to their location
  /// in the module.
  void
  setBranchSuccessors(DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger);

  /// For an IRInstructionData containing a CallInst, set the function name
  /// appropriately.  This will be an empty string if it is an indirect call,
  /// or we are not matching by name of the called function.  It will be the
  /// name of the function if \p MatchByName is true and it is not an indirect
  /// call.  We may decide not to match by name in order to expand the
  /// size of the regions we can match.  If a function name has the same type
  /// signature, but the different name, the region of code is still almost the
  /// same.  Since function names can be treated as constants, the name itself
  /// could be extrapolated away.  However, matching by name provides a
  /// specificity and more "identical" code than not matching by name.
  ///
  /// \param MatchByName - A flag to mark whether we are using the called
  /// function name as a differentiating parameter.
  void setCalleeName(bool MatchByName = true);

  /// For an IRInstructionData containing a PHINode, finds the
  /// relative distances from the incoming basic block to the current block by
  /// taking the difference of the number assigned to the current basic block
  /// and the incoming basic block of the branch.
  ///
  /// \param BasicBlockToInteger - The mapping of basic blocks to their location
  /// in the module.
  void
  setPHIPredecessors(DenseMap<BasicBlock *, unsigned> &BasicBlockToInteger);

  /// Hashes \p Value based on its opcode, types, and operand types.
  /// Two IRInstructionData instances produce the same hash when they perform
  /// the same operation.
  ///
  /// As a simple example, consider the following instructions.
  ///
  /// \code
  /// %add1 = add i32 %x1, %y1
  /// %add2 = add i32 %x2, %y2
  ///
  /// %sub = sub i32 %x1, %y1
  ///
  /// %add_i64 = add i64 %x2, %y2
  /// \endcode
  ///
  /// Because the first two adds operate the same types, and are performing the
  /// same action, they will be hashed to the same value.
  ///
  /// However, the subtraction instruction is not the same as an addition, and
  /// will be hashed to a different value.
  ///
  /// Finally, the last add has a different type compared to the first two add
  /// instructions, so it will also be hashed to a different value that any of
  /// the previous instructions.
  ///
  /// \param [in] ID - The IRInstructionData instance to be hashed.
  /// \returns A hash_value of the IRInstructionData.
  friend hash_code hash_value(const IRInstructionData &ID) {
    SmallVector<Type *, 4> OperTypes;
    for (Value *V : ID.OperVals)
      OperTypes.push_back(V->getType());

    if (isa<CmpInst>(ID.Inst))
      return llvm::hash_combine(
          llvm::hash_value(ID.Inst->getOpcode()),
          llvm::hash_value(ID.Inst->getType()),
          llvm::hash_value(ID.getPredicate()),
          llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));

    if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(ID.Inst)) {
      // To hash intrinsics, we use the opcode, and types like the other
      // instructions, but also, the Intrinsic ID, and the Name of the
      // intrinsic.
      Intrinsic::ID IntrinsicID = II->getIntrinsicID();
      return llvm::hash_combine(
          llvm::hash_value(ID.Inst->getOpcode()),
          llvm::hash_value(ID.Inst->getType()), llvm::hash_value(IntrinsicID),
          llvm::hash_value(*ID.CalleeName),
          llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
    }

    if (isa<CallInst>(ID.Inst)) {
      std::string FunctionName = *ID.CalleeName;
      return llvm::hash_combine(
          llvm::hash_value(ID.Inst->getOpcode()),
          llvm::hash_value(ID.Inst->getType()),
          llvm::hash_value(ID.Inst->getType()), llvm::hash_value(FunctionName),
          llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
    }

    return llvm::hash_combine(
        llvm::hash_value(ID.Inst->getOpcode()),
        llvm::hash_value(ID.Inst->getType()),
        llvm::hash_combine_range(OperTypes.begin(), OperTypes.end()));
  }

  IRInstructionDataList *IDL = nullptr;
};

struct IRInstructionDataList
    : simple_ilist<IRInstructionData, ilist_sentinel_tracking<true>> {};

/// Compare one IRInstructionData class to another IRInstructionData class for
/// whether they are performing a the same operation, and can mapped to the
/// same value. For regular instructions if the hash value is the same, then
/// they will also be close.
///
/// \param A - The first IRInstructionData class to compare
/// \param B - The second IRInstructionData class to compare
/// \returns true if \p A and \p B are similar enough to be mapped to the same
/// value.
bool isClose(const IRInstructionData &A, const IRInstructionData &B);

struct IRInstructionDataTraits : DenseMapInfo<IRInstructionData *> {
  static inline IRInstructionData *getEmptyKey() { return nullptr; }
  static inline IRInstructionData *getTombstoneKey() {
    return reinterpret_cast<IRInstructionData *>(-1);
  }

  static unsigned getHashValue(const IRInstructionData *E) {
    using llvm::hash_value;
    assert(E && "IRInstructionData is a nullptr?");
    return hash_value(*E);
  }

  static bool isEqual(const IRInstructionData *LHS,
                      const IRInstructionData *RHS) {
    if (RHS == getEmptyKey() || RHS == getTombstoneKey() ||
        LHS == getEmptyKey() || LHS == getTombstoneKey())
      return LHS == RHS;

    assert(LHS && RHS && "nullptr should have been caught by getEmptyKey?");
    return isClose(*LHS, *RHS);
  }
};

/// Helper struct for converting the Instructions in a Module into a vector of
/// unsigned integers. This vector of unsigned integers can be thought of as a
/// "numeric string". This numeric string can then be queried by, for example,
/// data structures that find repeated substrings.
///
/// This hashing is done per BasicBlock in the module. To hash Instructions
/// based off of their operations, each Instruction is wrapped in an
/// IRInstructionData struct. The unsigned integer for an IRInstructionData
/// depends on:
/// - The hash provided by the IRInstructionData.
/// - Which member of InstrType the IRInstructionData is classified as.
// See InstrType for more details on the possible classifications, and how they
// manifest in the numeric string.
///
/// The numeric string for an individual BasicBlock is terminated by an unique
/// unsigned integer. This prevents data structures which rely on repetition
/// from matching across BasicBlocks. (For example, the SuffixTree.)
/// As a concrete example, if we have the following two BasicBlocks:
/// \code
/// bb0:
/// %add1 = add i32 %a, %b
/// %add2 = add i32 %c, %d
/// %add3 = add i64 %e, %f
/// bb1:
/// %sub = sub i32 %c, %d
/// \endcode
/// We may hash the Instructions like this (via IRInstructionData):
/// \code
/// bb0:
/// %add1 = add i32 %a, %b ; Hash: 1
/// %add2 = add i32 %c, %d; Hash: 1
/// %add3 = add i64 %e, %f; Hash: 2
/// bb1:
/// %sub = sub i32 %c, %d; Hash: 3
/// %add4 = add i32 %c, %d ; Hash: 1
/// \endcode
/// And produce a "numeric string representation" like so:
/// 1, 1, 2, unique_integer_1, 3, 1, unique_integer_2
///
/// TODO: This is very similar to the MachineOutliner, and should be
/// consolidated into the same interface.
struct IRInstructionMapper {
  /// The starting illegal instruction number to map to.
  ///
  /// Set to -3 for compatibility with DenseMapInfo<unsigned>.
  unsigned IllegalInstrNumber = static_cast<unsigned>(-3);

  /// The next available integer to assign to a legal Instruction to.
  unsigned LegalInstrNumber = 0;

  /// Correspondence from IRInstructionData to unsigned integers.
  DenseMap<IRInstructionData *, unsigned, IRInstructionDataTraits>
      InstructionIntegerMap;

  /// A mapping for a basic block in a module to its assigned number/location
  /// in the module.
  DenseMap<BasicBlock *, unsigned> BasicBlockToInteger;

  /// Set if we added an illegal number in the previous step.
  /// Since each illegal number is unique, we only need one of them between
  /// each range of legal numbers. This lets us make sure we don't add more
  /// than one illegal number per range.
  bool AddedIllegalLastTime = false;

  /// Marks whether we found a illegal instruction in the previous step.
  bool CanCombineWithPrevInstr = false;

  /// Marks whether we have found a set of instructions that is long enough
  /// to be considered for similarity.
  bool HaveLegalRange = false;

  /// Marks whether we should use exact function names, as well as types to
  /// find similarity between calls.
  bool EnableMatchCallsByName = false;

  /// This allocator pointer is in charge of holding on to the IRInstructionData
  /// so it is not deallocated until whatever external tool is using it is done
  /// with the information.
  SpecificBumpPtrAllocator<IRInstructionData> *InstDataAllocator = nullptr;

  /// This allocator pointer is in charge of creating the IRInstructionDataList
  /// so it is not deallocated until whatever external tool is using it is done
  /// with the information.
  SpecificBumpPtrAllocator<IRInstructionDataList> *IDLAllocator = nullptr;

  /// Get an allocated IRInstructionData struct using the InstDataAllocator.
  ///
  /// \param I - The Instruction to wrap with IRInstructionData.
  /// \param Legality - A boolean value that is true if the instruction is to
  /// be considered for similarity, and false if not.
  /// \param IDL - The InstructionDataList that the IRInstructionData is
  /// inserted into.
  /// \returns An allocated IRInstructionData struct.
  IRInstructionData *allocateIRInstructionData(Instruction &I, bool Legality,
                                               IRInstructionDataList &IDL);

  /// Get an empty allocated IRInstructionData struct using the
  /// InstDataAllocator.
  ///
  /// \param IDL - The InstructionDataList that the IRInstructionData is
  /// inserted into.
  /// \returns An allocated IRInstructionData struct.
  IRInstructionData *allocateIRInstructionData(IRInstructionDataList &IDL);

  /// Get an allocated IRInstructionDataList object using the IDLAllocator.
  ///
  /// \returns An allocated IRInstructionDataList object.
  IRInstructionDataList *allocateIRInstructionDataList();

  IRInstructionDataList *IDL = nullptr;

  /// Assigns values to all the basic blocks in function \p F starting from
  /// integer \p BBNumber.
  ///
  /// \param F - The function containing the basic blocks to assign numbers to.
  /// \param BBNumber - The number to start from.
  void initializeForBBs(Function &F, unsigned &BBNumber) {
    for (BasicBlock &BB : F)
      BasicBlockToInteger.insert(std::make_pair(&BB, BBNumber++));
  }

  /// Assigns values to all the basic blocks in Module \p M.
  /// \param M - The module containing the basic blocks to assign numbers to.
  void initializeForBBs(Module &M) {
    unsigned BBNumber = 0;
    for (Function &F : M)
      initializeForBBs(F, BBNumber);
  }

  /// Maps the Instructions in a BasicBlock \p BB to legal or illegal integers
  /// determined by \p InstrType. Two Instructions are mapped to the same value
  /// if they are close as defined by the InstructionData class above.
  ///
  /// \param [in] BB - The BasicBlock to be mapped to integers.
  /// \param [in,out] InstrList - Vector of IRInstructionData to append to.
  /// \param [in,out] IntegerMapping - Vector of unsigned integers to append to.
  void convertToUnsignedVec(BasicBlock &BB,
                            std::vector<IRInstructionData *> &InstrList,
                            std::vector<unsigned> &IntegerMapping);

  /// Maps an Instruction to a legal integer.
  ///
  /// \param [in] It - The Instruction to be mapped to an integer.
  /// \param [in,out] IntegerMappingForBB - Vector of unsigned integers to
  /// append to.
  /// \param [in,out] InstrListForBB - Vector of InstructionData to append to.
  /// \returns The integer \p It was mapped to.
  unsigned mapToLegalUnsigned(BasicBlock::iterator &It,
                              std::vector<unsigned> &IntegerMappingForBB,
                              std::vector<IRInstructionData *> &InstrListForBB);

  /// Maps an Instruction to an illegal integer.
  ///
  /// \param [in] It - The \p Instruction to be mapped to an integer.
  /// \param [in,out] IntegerMappingForBB - Vector of unsigned integers to
  /// append to.
  /// \param [in,out] InstrListForBB - Vector of IRInstructionData to append to.
  /// \param End - true if creating a dummy IRInstructionData at the end of a
  /// basic block.
  /// \returns The integer \p It was mapped to.
  unsigned mapToIllegalUnsigned(
      BasicBlock::iterator &It, std::vector<unsigned> &IntegerMappingForBB,
      std::vector<IRInstructionData *> &InstrListForBB, bool End = false);

  IRInstructionMapper(SpecificBumpPtrAllocator<IRInstructionData> *IDA,
                      SpecificBumpPtrAllocator<IRInstructionDataList> *IDLA)
      : InstDataAllocator(IDA), IDLAllocator(IDLA) {
    // Make sure that the implementation of DenseMapInfo<unsigned> hasn't
    // changed.
    assert(DenseMapInfo<unsigned>::getEmptyKey() == static_cast<unsigned>(-1) &&
           "DenseMapInfo<unsigned>'s empty key isn't -1!");
    assert(DenseMapInfo<unsigned>::getTombstoneKey() ==
               static_cast<unsigned>(-2) &&
           "DenseMapInfo<unsigned>'s tombstone key isn't -2!");

    IDL = new (IDLAllocator->Allocate())
        IRInstructionDataList();
  }

  /// Custom InstVisitor to classify different instructions for whether it can
  /// be analyzed for similarity.
  struct InstructionClassification
      : public InstVisitor<InstructionClassification, InstrType> {
    InstructionClassification() = default;

    // TODO: Determine a scheme to resolve when the label is similar enough.
    InstrType visitBranchInst(BranchInst &BI) {
      if (EnableBranches)
        return Legal;
      return Illegal;
    }
    InstrType visitPHINode(PHINode &PN) { 
      if (EnableBranches)
        return Legal;
      return Illegal;
    }
    // TODO: Handle allocas.
    InstrType visitAllocaInst(AllocaInst &AI) { return Illegal; }
    // We exclude variable argument instructions since variable arguments
    // requires extra checking of the argument list.
    InstrType visitVAArgInst(VAArgInst &VI) { return Illegal; }
    // We exclude all exception handling cases since they are so context
    // dependent.
    InstrType visitLandingPadInst(LandingPadInst &LPI) { return Illegal; }
    InstrType visitFuncletPadInst(FuncletPadInst &FPI) { return Illegal; }
    // DebugInfo should be included in the regions, but should not be
    // analyzed for similarity as it has no bearing on the outcome of the
    // program.
    InstrType visitDbgInfoIntrinsic(DbgInfoIntrinsic &DII) { return Invisible; }
    InstrType visitIntrinsicInst(IntrinsicInst &II) {
      // These are disabled due to complications in the CodeExtractor when
      // outlining these instructions.  For instance, It is unclear what we
      // should do when moving only the start or end lifetime instruction into
      // an outlined function. Also, assume-like intrinsics could be removed
      // from the region, removing arguments, causing discrepencies in the
      // number of inputs between different regions.
      if (II.isAssumeLikeIntrinsic())
        return Illegal;
      return EnableIntrinsics ? Legal : Illegal;
    }
    // We only allow call instructions where the function has a name and
    // is not an indirect call.
    InstrType visitCallInst(CallInst &CI) {
      Function *F = CI.getCalledFunction();
      bool IsIndirectCall = CI.isIndirectCall();
      if (IsIndirectCall && !EnableIndirectCalls)
        return Illegal;
      if (!F && !IsIndirectCall)
        return Illegal;
      // Functions marked with the swifttailcc and tailcc calling conventions
      // require special handling when outlining musttail functions.  The
      // calling convention must be passed down to the outlined function as
      // well. Further, there is special handling for musttail calls as well,
      // requiring a return call directly after.  For now, the outliner does not
      // support this, so we do not handle matching this case either.
      if ((CI.getCallingConv() == CallingConv::SwiftTail ||
           CI.getCallingConv() == CallingConv::Tail) &&
          !EnableMustTailCalls)
        return Illegal;
      if (CI.isMustTailCall() && !EnableMustTailCalls)
        return Illegal;
      return Legal;
    }
    // TODO: We do not current handle similarity that changes the control flow.
    InstrType visitInvokeInst(InvokeInst &II) { return Illegal; }
    // TODO: We do not current handle similarity that changes the control flow.
    InstrType visitCallBrInst(CallBrInst &CBI) { return Illegal; }
    // TODO: Handle interblock similarity.
    InstrType visitTerminator(Instruction &I) { return Illegal; }
    InstrType visitInstruction(Instruction &I) { return Legal; }

    // The flag variable that lets the classifier know whether we should
    // allow branches to be checked for similarity.
    bool EnableBranches = false;

    // The flag variable that lets the classifier know whether we should
    // allow indirect calls to be considered legal instructions.
    bool EnableIndirectCalls = false;

    // Flag that lets the classifier know whether we should allow intrinsics to
    // be checked for similarity.
    bool EnableIntrinsics = false;
  
    // Flag that lets the classifier know whether we should allow tail calls to
    // be checked for similarity.
    bool EnableMustTailCalls = false;
  };

  /// Maps an Instruction to a member of InstrType.
  InstructionClassification InstClassifier;
};

/// This is a class that wraps a range of IRInstructionData from one point to
/// another in the vector of IRInstructionData, which is a region of the
/// program.  It is also responsible for defining the structure within this
/// region of instructions.
///
/// The structure of a region is defined through a value numbering system
/// assigned to each unique value in a region at the creation of the
/// IRSimilarityCandidate.
///
/// For example, for each Instruction we add a mapping for each new
/// value seen in that Instruction.
/// IR:                    Mapping Added:
/// %add1 = add i32 %a, c1    %add1 -> 3, %a -> 1, c1 -> 2
/// %add2 = add i32 %a, %1    %add2 -> 4
/// %add3 = add i32 c2, c1    %add3 -> 6, c2 -> 5
///
/// We can compare IRSimilarityCandidates against one another.
/// The \ref isSimilar function compares each IRInstructionData against one
/// another and if we have the same sequences of IRInstructionData that would
/// create the same hash, we have similar IRSimilarityCandidates.
///
/// We can also compare the structure of IRSimilarityCandidates. If we can
/// create a mapping of registers in the region contained by one
/// IRSimilarityCandidate to the region contained by different
/// IRSimilarityCandidate, they can be considered structurally similar.
///
/// IRSimilarityCandidate1:   IRSimilarityCandidate2:
/// %add1 = add i32 %a, %b    %add1 = add i32 %d, %e
/// %add2 = add i32 %a, %c    %add2 = add i32 %d, %f
/// %add3 = add i32 c1, c2    %add3 = add i32 c3, c4
///
/// Can have the following mapping from candidate to candidate of:
/// %a -> %d, %b -> %e, %c -> %f, c1 -> c3, c2 -> c4
/// and can be considered similar.
///
/// IRSimilarityCandidate1:   IRSimilarityCandidate2:
/// %add1 = add i32 %a, %b    %add1 = add i32 %d, c4
/// %add2 = add i32 %a, %c    %add2 = add i32 %d, %f
/// %add3 = add i32 c1, c2    %add3 = add i32 c3, c4
///
/// We cannot create the same mapping since the use of c4 is not used in the
/// same way as %b or c2.
class IRSimilarityCandidate {
private:
  /// The start index of this IRSimilarityCandidate in the instruction list.
  unsigned StartIdx = 0;

  /// The number of instructions in this IRSimilarityCandidate.
  unsigned Len = 0;

  /// The first instruction in this IRSimilarityCandidate.
  IRInstructionData *FirstInst = nullptr;

  /// The last instruction in this IRSimilarityCandidate.
  IRInstructionData *LastInst = nullptr;

  /// Global Value Numbering structures
  /// @{
  /// Stores the mapping of the value to the number assigned to it in the
  /// IRSimilarityCandidate.
  DenseMap<Value *, unsigned> ValueToNumber;
  /// Stores the mapping of the number to the value assigned this number.
  DenseMap<unsigned, Value *> NumberToValue;
  /// Stores the mapping of a value's number to canonical numbering in the
  /// candidate's respective similarity group.
  DenseMap<unsigned, unsigned> NumberToCanonNum;
  /// Stores the mapping of canonical number in the candidate's respective
  /// similarity group to a value number.
  DenseMap<unsigned, unsigned> CanonNumToNumber;
  /// @}

public:
  /// \param StartIdx - The starting location of the region.
  /// \param Len - The length of the region.
  /// \param FirstInstIt - The starting IRInstructionData of the region.
  /// \param LastInstIt - The ending IRInstructionData of the region.
  IRSimilarityCandidate(unsigned StartIdx, unsigned Len,
                        IRInstructionData *FirstInstIt,
                        IRInstructionData *LastInstIt);

  /// \param A - The first IRInstructionCandidate to compare.
  /// \param B - The second IRInstructionCandidate to compare.
  /// \returns True when every IRInstructionData in \p A is similar to every
  /// IRInstructionData in \p B.
  static bool isSimilar(const IRSimilarityCandidate &A,
                        const IRSimilarityCandidate &B);

  /// \param [in] A - The first IRInstructionCandidate to compare.
  /// \param [in] B - The second IRInstructionCandidate to compare.
  /// \returns True when every IRInstructionData in \p A is structurally similar
  /// to \p B.
  static bool compareStructure(const IRSimilarityCandidate &A,
                               const IRSimilarityCandidate &B);

  /// \param [in] A - The first IRInstructionCandidate to compare.
  /// \param [in] B - The second IRInstructionCandidate to compare.
  /// \param [in,out] ValueNumberMappingA - A mapping of value numbers from
  /// candidate \p A to candidate \B.
  /// \param [in,out] ValueNumberMappingB - A mapping of value numbers from
  /// candidate \p B to candidate \A.
  /// \returns True when every IRInstructionData in \p A is structurally similar
  /// to \p B.
  static bool
  compareStructure(const IRSimilarityCandidate &A,
                   const IRSimilarityCandidate &B,
                   DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingA,
                   DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMappingB);

  struct OperandMapping {
    /// The IRSimilarityCandidate that holds the instruction the OperVals were
    /// pulled from.
    const IRSimilarityCandidate &IRSC;

    /// The operand values to be analyzed.
    ArrayRef<Value *> &OperVals;

    /// The current mapping of global value numbers from one IRSimilarityCandidate
    /// to another IRSimilarityCandidate.
    DenseMap<unsigned, DenseSet<unsigned>> &ValueNumberMapping;
  };

  /// A helper struct to hold the candidate, for a branch instruction, the
  /// relative location of a label, and the label itself.  This is mostly to
  /// group the values together before passing them as a bundle to a function.
  struct RelativeLocMapping {
    /// The IRSimilarityCandidate that holds the instruction the relative
    /// location was pulled from.
    const IRSimilarityCandidate &IRSC;

    /// The relative location to be analyzed.
    int RelativeLocation;

    /// The corresponding value.
    Value *OperVal;
  };

  /// Compare the operands in \p A and \p B and check that the current mapping
  /// of global value numbers from \p A to \p B and \p B to \A is consistent.
  ///
  /// \param A - The first IRInstructionCandidate, operand values, and current
  /// operand mappings to compare.
  /// \param B - The second IRInstructionCandidate, operand values, and current
  /// operand mappings to compare.
  /// \returns true if the IRSimilarityCandidates operands are compatible.
  static bool compareNonCommutativeOperandMapping(OperandMapping A,
                                                  OperandMapping B);

  /// Compare the operands in \p A and \p B and check that the current mapping
  /// of global value numbers from \p A to \p B and \p B to \A is consistent
  /// given that the operands are commutative.
  ///
  /// \param A - The first IRInstructionCandidate, operand values, and current
  /// operand mappings to compare.
  /// \param B - The second IRInstructionCandidate, operand values, and current
  /// operand mappings to compare.
  /// \returns true if the IRSimilarityCandidates operands are compatible.
  static bool compareCommutativeOperandMapping(OperandMapping A,
                                               OperandMapping B);

  /// Compare the relative locations in \p A and \p B and check that the
  /// distances match if both locations are contained in the region, and that
  /// the branches both point outside the region if they do not.
  /// Example Region:
  /// \code
  /// entry:
  ///   br i1 %0, label %block_1, label %block_3
  /// block_0:
  ///   br i1 %0, label %block_1, label %block_2
  /// block_1:
  ///   br i1 %0, label %block_2, label %block_3
  /// block_2:
  ///   br i1 %1, label %block_1, label %block_4
  /// block_3:
  ///   br i1 %2, label %block_2, label %block_5
  /// \endcode
  /// If we compare the branches in block_0 and block_1 the relative values are
  /// 1 and 2 for both, so we consider this a match.
  ///
  /// If we compare the branches in entry and block_0 the relative values are
  /// 2 and 3, and 1 and 2 respectively.  Since these are not the same we do not
  /// consider them a match.
  ///
  /// If we compare the branches in block_1 and block_2 the relative values are
  /// 1 and 2, and -1 and None respectively.  As a result we do not consider
  /// these to be the same
  ///
  /// If we compare the branches in block_2 and block_3 the relative values are
  /// -1 and None for both.  We do consider these to be a match.
  ///
  /// \param A - The first IRInstructionCandidate, relative location value,
  /// and incoming block.
  /// \param B - The second IRInstructionCandidate, relative location value,
  /// and incoming block.
  /// \returns true if the relative locations match.
  static bool checkRelativeLocations(RelativeLocMapping A,
                                     RelativeLocMapping B);

  /// Create a mapping from the value numbering to a different separate set of
  /// numbers. This will serve as a guide for relating one candidate to another.
  /// The canonical number gives use the ability identify which global value
  /// number in one candidate relates to the global value number in the other.
  ///
  /// \param [in, out] CurrCand - The IRSimilarityCandidate to create a
  /// canonical numbering for.
  static void createCanonicalMappingFor(IRSimilarityCandidate &CurrCand);

  /// Create a mapping for the value numbering of the calling
  /// IRSimilarityCandidate, to a different separate set of numbers, based on
  /// the canonical ordering in \p SourceCand. These are defined based on the
  /// found mappings in \p ToSourceMapping and \p FromSourceMapping.  Both of
  /// these relationships should have the same information, just in opposite
  /// directions.
  ///
  /// \param [in, out] SourceCand - The IRSimilarityCandidate to create a
  /// canonical numbering from.
  /// \param ToSourceMapping - The mapping of value numbers from this candidate
  /// to \p SourceCand.
  /// \param FromSourceMapping - The mapping of value numbers from \p SoureCand
  /// to this candidate.
  void createCanonicalRelationFrom(
      IRSimilarityCandidate &SourceCand,
      DenseMap<unsigned, DenseSet<unsigned>> &ToSourceMapping,
      DenseMap<unsigned, DenseSet<unsigned>> &FromSourceMapping);

  /// \param [in,out] BBSet - The set to track the basic blocks.
  void getBasicBlocks(DenseSet<BasicBlock *> &BBSet) const {
    for (IRInstructionData &ID : *this) {
      BasicBlock *BB = ID.Inst->getParent();
      BBSet.insert(BB);
    }
  }

  /// \param [in,out] BBSet - The set to track the basic blocks.
  /// \param [in,out] BBList - A list in order of use to track the basic blocks.
  void getBasicBlocks(DenseSet<BasicBlock *> &BBSet,
                      SmallVector<BasicBlock *> &BBList) const {
    for (IRInstructionData &ID : *this) {
      BasicBlock *BB = ID.Inst->getParent();
      if (BBSet.insert(BB).second)
        BBList.push_back(BB);
    }
  }

  /// Compare the start and end indices of the two IRSimilarityCandidates for
  /// whether they overlap. If the start instruction of one
  /// IRSimilarityCandidate is less than the end instruction of the other, and
  /// the start instruction of one is greater than the start instruction of the
  /// other, they overlap.
  ///
  /// \returns true if the IRSimilarityCandidates do not have overlapping
  /// instructions.
  static bool overlap(const IRSimilarityCandidate &A,
                      const IRSimilarityCandidate &B);

  /// \returns the number of instructions in this Candidate.
  unsigned getLength() const { return Len; }

  /// \returns the start index of this IRSimilarityCandidate.
  unsigned getStartIdx() const { return StartIdx; }

  /// \returns the end index of this IRSimilarityCandidate.
  unsigned getEndIdx() const { return StartIdx + Len - 1; }

  /// \returns The first IRInstructionData.
  IRInstructionData *front() const { return FirstInst; }
  /// \returns The last IRInstructionData.
  IRInstructionData *back() const { return LastInst; }

  /// \returns The first Instruction.
  Instruction *frontInstruction() { return FirstInst->Inst; }
  /// \returns The last Instruction
  Instruction *backInstruction() { return LastInst->Inst; }

  /// \returns The BasicBlock the IRSimilarityCandidate starts in.
  BasicBlock *getStartBB() { return FirstInst->Inst->getParent(); }
  /// \returns The BasicBlock the IRSimilarityCandidate ends in.
  BasicBlock *getEndBB() { return LastInst->Inst->getParent(); }

  /// \returns The Function that the IRSimilarityCandidate is located in.
  Function *getFunction() { return getStartBB()->getParent(); }

  /// Finds the positive number associated with \p V if it has been mapped.
  /// \param [in] V - the Value to find.
  /// \returns The positive number corresponding to the value.
  /// \returns None if not present.
  Optional<unsigned> getGVN(Value *V) {
    assert(V != nullptr && "Value is a nullptr?");
    DenseMap<Value *, unsigned>::iterator VNIt = ValueToNumber.find(V);
    if (VNIt == ValueToNumber.end())
      return None;
    return VNIt->second;
  }

  /// Finds the Value associate with \p Num if it exists.
  /// \param [in] Num - the number to find.
  /// \returns The Value associated with the number.
  /// \returns None if not present.
  Optional<Value *> fromGVN(unsigned Num) {
    DenseMap<unsigned, Value *>::iterator VNIt = NumberToValue.find(Num);
    if (VNIt == NumberToValue.end())
      return None;
    assert(VNIt->second != nullptr && "Found value is a nullptr!");
    return VNIt->second;
  }

  /// Find the canonical number from the global value number \p N stored in the
  /// candidate.
  ///
  /// \param N - The global value number to find the canonical number for.
  /// \returns An optional containing the value, and None if it could not be
  /// found.
  Optional<unsigned> getCanonicalNum(unsigned N) {
    DenseMap<unsigned, unsigned>::iterator NCIt = NumberToCanonNum.find(N);
    if (NCIt == NumberToCanonNum.end())
      return None;
    return NCIt->second;
  }

  /// Find the global value number from the canonical number \p N stored in the
  /// candidate.
  ///
  /// \param N - The canonical number to find the global vlaue number for.
  /// \returns An optional containing the value, and None if it could not be
  /// found.
  Optional<unsigned> fromCanonicalNum(unsigned N) {
    DenseMap<unsigned, unsigned>::iterator CNIt = CanonNumToNumber.find(N);
    if (CNIt == CanonNumToNumber.end())
      return None;
    return CNIt->second;
  }

  /// \param RHS -The IRSimilarityCandidate to compare against
  /// \returns true if the IRSimilarityCandidate is occurs after the
  /// IRSimilarityCandidate in the program.
  bool operator<(const IRSimilarityCandidate &RHS) const {
    return getStartIdx() > RHS.getStartIdx();
  }

  using iterator = IRInstructionDataList::iterator;
  iterator begin() const { return iterator(front()); }
  iterator end() const { return std::next(iterator(back())); }
};

typedef DenseMap<IRSimilarityCandidate *,
                 DenseMap<unsigned, DenseSet<unsigned>>>
    CandidateGVNMapping;
typedef std::vector<IRSimilarityCandidate> SimilarityGroup;
typedef std::vector<SimilarityGroup> SimilarityGroupList;

/// This class puts all the pieces of the IRInstructionData,
/// IRInstructionMapper, IRSimilarityCandidate together.
///
/// It first feeds the Module or vector of Modules into the IRInstructionMapper,
/// and puts all the mapped instructions into a single long list of
/// IRInstructionData.
///
/// The list of unsigned integers is given to the Suffix Tree or similar data
/// structure to find repeated subsequences.  We construct an
/// IRSimilarityCandidate for each instance of the subsequence.  We compare them
/// against one another since  These repeated subsequences can have different
/// structure.  For each different kind of structure found, we create a
/// similarity group.
///
/// If we had four IRSimilarityCandidates A, B, C, and D where A, B and D are
/// structurally similar to one another, while C is different we would have two
/// SimilarityGroups:
///
/// SimilarityGroup 1:  SimilarityGroup 2
/// A, B, D             C
///
/// A list of the different similarity groups is then returned after
/// analyzing the module.
class IRSimilarityIdentifier {
public:
  IRSimilarityIdentifier(bool MatchBranches = true,
                         bool MatchIndirectCalls = true,
                         bool MatchCallsWithName = false,
                         bool MatchIntrinsics = true,
                         bool MatchMustTailCalls = true)
      : Mapper(&InstDataAllocator, &InstDataListAllocator),
        EnableBranches(MatchBranches), EnableIndirectCalls(MatchIndirectCalls),
        EnableMatchingCallsByName(MatchCallsWithName),
        EnableIntrinsics(MatchIntrinsics),
        EnableMustTailCalls(MatchMustTailCalls) {}

private:
  /// Map the instructions in the module to unsigned integers, using mapping
  /// already present in the Mapper if possible.
  ///
  /// \param [in] M Module - To map to integers.
  /// \param [in,out] InstrList - The vector to append IRInstructionData to.
  /// \param [in,out] IntegerMapping - The vector to append integers to.
  void populateMapper(Module &M, std::vector<IRInstructionData *> &InstrList,
                      std::vector<unsigned> &IntegerMapping);

  /// Map the instructions in the modules vector to unsigned integers, using
  /// mapping already present in the mapper if possible.
  ///
  /// \param [in] Modules - The list of modules to use to populate the mapper
  /// \param [in,out] InstrList - The vector to append IRInstructionData to.
  /// \param [in,out] IntegerMapping - The vector to append integers to.
  void populateMapper(ArrayRef<std::unique_ptr<Module>> &Modules,
                      std::vector<IRInstructionData *> &InstrList,
                      std::vector<unsigned> &IntegerMapping);

  /// Find the similarity candidates in \p InstrList and corresponding
  /// \p UnsignedVec
  ///
  /// \param [in,out] InstrList - The vector to append IRInstructionData to.
  /// \param [in,out] IntegerMapping - The vector to append integers to.
  /// candidates found in the program.
  void findCandidates(std::vector<IRInstructionData *> &InstrList,
                      std::vector<unsigned> &IntegerMapping);

public:
  // Find the IRSimilarityCandidates in the \p Modules and group by structural
  // similarity in a SimilarityGroup, each group is returned in a
  // SimilarityGroupList.
  //
  // \param [in] Modules - the modules to analyze.
  // \returns The groups of similarity ranges found in the modules.
  SimilarityGroupList &
  findSimilarity(ArrayRef<std::unique_ptr<Module>> Modules);

  // Find the IRSimilarityCandidates in the given Module grouped by structural
  // similarity in a SimilarityGroup, contained inside a SimilarityGroupList.
  //
  // \param [in] M - the module to analyze.
  // \returns The groups of similarity ranges found in the module.
  SimilarityGroupList &findSimilarity(Module &M);

  // Clears \ref SimilarityCandidates if it is already filled by a previous run.
  void resetSimilarityCandidates() {
    // If we've already analyzed a Module or set of Modules, so we must clear
    // the SimilarityCandidates to make sure we do not have only old values
    // hanging around.
    if (SimilarityCandidates)
      SimilarityCandidates->clear();
    else
      SimilarityCandidates = SimilarityGroupList();
  }

  // \returns The groups of similarity ranges found in the most recently passed
  // set of modules.
  Optional<SimilarityGroupList> &getSimilarity() {
    return SimilarityCandidates;
  }

private:
  /// The allocator for IRInstructionData.
  SpecificBumpPtrAllocator<IRInstructionData> InstDataAllocator;

  /// The allocator for IRInstructionDataLists.
  SpecificBumpPtrAllocator<IRInstructionDataList> InstDataListAllocator;

  /// Map Instructions to unsigned integers and wraps the Instruction in an
  /// instance of IRInstructionData.
  IRInstructionMapper Mapper;

  /// The flag variable that marks whether we should check branches for
  /// similarity, or only look within basic blocks.
  bool EnableBranches = true;

  /// The flag variable that marks whether we allow indirect calls to be checked
  /// for similarity, or exclude them as a legal instruction.
  bool EnableIndirectCalls = true;

  /// The flag variable that marks whether we allow calls to be marked as
  /// similar if they do not have the same name, only the same calling
  /// convention, attributes and type signature.
  bool EnableMatchingCallsByName = true;

  /// The flag variable that marks whether we should check intrinsics for
  /// similarity.
  bool EnableIntrinsics = true;

  // The flag variable that marks whether we should allow tailcalls
  // to be checked for similarity.
  bool EnableMustTailCalls = false;

  /// The SimilarityGroups found with the most recent run of \ref
  /// findSimilarity. None if there is no recent run.
  Optional<SimilarityGroupList> SimilarityCandidates;
};

} // end namespace IRSimilarity

/// An analysis pass based on legacy pass manager that runs and returns
/// IRSimilarityIdentifier run on the Module.
class IRSimilarityIdentifierWrapperPass : public ModulePass {
  std::unique_ptr<IRSimilarity::IRSimilarityIdentifier> IRSI;

public:
  static char ID;
  IRSimilarityIdentifierWrapperPass();

  IRSimilarity::IRSimilarityIdentifier &getIRSI() { return *IRSI; }
  const IRSimilarity::IRSimilarityIdentifier &getIRSI() const { return *IRSI; }

  bool doInitialization(Module &M) override;
  bool doFinalization(Module &M) override;
  bool runOnModule(Module &M) override;
  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.setPreservesAll();
  }
};

/// An analysis pass that runs and returns the IRSimilarityIdentifier run on the
/// Module.
class IRSimilarityAnalysis : public AnalysisInfoMixin<IRSimilarityAnalysis> {
public:
  typedef IRSimilarity::IRSimilarityIdentifier Result;

  Result run(Module &M, ModuleAnalysisManager &);

private:
  friend AnalysisInfoMixin<IRSimilarityAnalysis>;
  static AnalysisKey Key;
};

/// Printer pass that uses \c IRSimilarityAnalysis.
class IRSimilarityAnalysisPrinterPass
    : public PassInfoMixin<IRSimilarityAnalysisPrinterPass> {
  raw_ostream &OS;

public:
  explicit IRSimilarityAnalysisPrinterPass(raw_ostream &OS) : OS(OS) {}
  PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
};

} // end namespace llvm

#endif // LLVM_ANALYSIS_IRSIMILARITYIDENTIFIER_H