EIC code displayed by LXR master/​include/​llvm/​Transforms/​Utils/​FunctionComparator.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:44:43

 //===- FunctionComparator.h - Function Comparator ---------------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines the FunctionComparator and GlobalNumberState classes which
 // are used by the MergeFunctions pass for comparing functions.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H
 #define LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/ValueMap.h"
 #include "llvm/Support/AtomicOrdering.h"
 #include "llvm/Support/Casting.h"
 #include <cstdint>
 #include <tuple>
 
 namespace llvm {
 
 class APFloat;
 class AttributeList;
 class APInt;
 class BasicBlock;
 class Constant;
 class Function;
 class GlobalValue;
 class InlineAsm;
 class Instruction;
 class MDNode;
 class Type;
 class Value;
 
 /// GlobalNumberState assigns an integer to each global value in the program,
 /// which is used by the comparison routine to order references to globals. This
 /// state must be preserved throughout the pass, because Functions and other
 /// globals need to maintain their relative order. Globals are assigned a number
 /// when they are first visited. This order is deterministic, and so the
 /// assigned numbers are as well. When two functions are merged, neither number
 /// is updated. If the symbols are weak, this would be incorrect. If they are
 /// strong, then one will be replaced at all references to the other, and so
 /// direct callsites will now see one or the other symbol, and no update is
 /// necessary. Note that if we were guaranteed unique names, we could just
 /// compare those, but this would not work for stripped bitcodes or for those
 /// few symbols without a name.
 class GlobalNumberState {
   struct Config : ValueMapConfig<GlobalValue *> {
     enum { FollowRAUW = false };
   };
 
   // Each GlobalValue is mapped to an identifier. The Config ensures when RAUW
   // occurs, the mapping does not change. Tracking changes is unnecessary, and
   // also problematic for weak symbols (which may be overwritten).
   using ValueNumberMap = ValueMap<GlobalValue *, uint64_t, Config>;
   ValueNumberMap GlobalNumbers;
 
   // The next unused serial number to assign to a global.
   uint64_t NextNumber = 0;
 
 public:
   GlobalNumberState() = default;
 
   uint64_t getNumber(GlobalValue* Global) {
     ValueNumberMap::iterator MapIter;
     bool Inserted;
     std::tie(MapIter, Inserted) = GlobalNumbers.insert({Global, NextNumber});
     if (Inserted)
       NextNumber++;
     return MapIter->second;
   }
 
   void erase(GlobalValue *Global) {
     GlobalNumbers.erase(Global);
   }
 
   void clear() {
     GlobalNumbers.clear();
   }
 };
 
 /// FunctionComparator - Compares two functions to determine whether or not
 /// they will generate machine code with the same behaviour. DataLayout is
 /// used if available. The comparator always fails conservatively (erring on the
 /// side of claiming that two functions are different).
 class FunctionComparator {
 public:
   FunctionComparator(const Function *F1, const Function *F2,
                      GlobalNumberState* GN)
       : FnL(F1), FnR(F2), GlobalNumbers(GN) {}
 
   /// Test whether the two functions have equivalent behaviour.
   int compare();
 
 protected:
   /// Start the comparison.
   void beginCompare() {
     sn_mapL.clear();
     sn_mapR.clear();
   }
 
   /// Compares the signature and other general attributes of the two functions.
   int compareSignature() const;
 
   /// Test whether two basic blocks have equivalent behaviour.
   int cmpBasicBlocks(const BasicBlock *BBL, const BasicBlock *BBR) const;
 
   /// Constants comparison.
   /// Its analog to lexicographical comparison between hypothetical numbers
   /// of next format:
   /// <bitcastability-trait><raw-bit-contents>
   ///
   /// 1. Bitcastability.
   /// Check whether L's type could be losslessly bitcasted to R's type.
   /// On this stage method, in case when lossless bitcast is not possible
   /// method returns -1 or 1, thus also defining which type is greater in
   /// context of bitcastability.
   /// Stage 0: If types are equal in terms of cmpTypes, then we can go straight
   ///          to the contents comparison.
   ///          If types differ, remember types comparison result and check
   ///          whether we still can bitcast types.
   /// Stage 1: Types that satisfies isFirstClassType conditions are always
   ///          greater then others.
   /// Stage 2: Vector is greater then non-vector.
   ///          If both types are vectors, then vector with greater bitwidth is
   ///          greater.
   ///          If both types are vectors with the same bitwidth, then types
   ///          are bitcastable, and we can skip other stages, and go to contents
   ///          comparison.
   /// Stage 3: Pointer types are greater than non-pointers. If both types are
   ///          pointers of the same address space - go to contents comparison.
   ///          Different address spaces: pointer with greater address space is
   ///          greater.
   /// Stage 4: Types are neither vectors, nor pointers. And they differ.
   ///          We don't know how to bitcast them. So, we better don't do it,
   ///          and return types comparison result (so it determines the
   ///          relationship among constants we don't know how to bitcast).
   ///
   /// Just for clearance, let's see how the set of constants could look
   /// on single dimension axis:
   ///
   /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors]
   /// Where: NFCT - Not a FirstClassType
   ///        FCT - FirstClassTyp:
   ///
   /// 2. Compare raw contents.
   /// It ignores types on this stage and only compares bits from L and R.
   /// Returns 0, if L and R has equivalent contents.
   /// -1 or 1 if values are different.
   /// Pretty trivial:
   /// 2.1. If contents are numbers, compare numbers.
   ///    Ints with greater bitwidth are greater. Ints with same bitwidths
   ///    compared by their contents.
   /// 2.2. "And so on". Just to avoid discrepancies with comments
   /// perhaps it would be better to read the implementation itself.
   /// 3. And again about overall picture. Let's look back at how the ordered set
   /// of constants will look like:
   /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors]
   ///
   /// Now look, what could be inside [FCT, "others"], for example:
   /// [FCT, "others"] =
   /// [
   ///   [double 0.1], [double 1.23],
   ///   [i32 1], [i32 2],
   ///   { double 1.0 },       ; StructTyID, NumElements = 1
   ///   { i32 1 },            ; StructTyID, NumElements = 1
   ///   { double 1, i32 1 },  ; StructTyID, NumElements = 2
   ///   { i32 1, double 1 }   ; StructTyID, NumElements = 2
   /// ]
   ///
   /// Let's explain the order. Float numbers will be less than integers, just
   /// because of cmpType terms: FloatTyID < IntegerTyID.
   /// Floats (with same fltSemantics) are sorted according to their value.
   /// Then you can see integers, and they are, like a floats,
   /// could be easy sorted among each others.
   /// The structures. Structures are grouped at the tail, again because of their
   /// TypeID: StructTyID > IntegerTyID > FloatTyID.
   /// Structures with greater number of elements are greater. Structures with
   /// greater elements going first are greater.
   /// The same logic with vectors, arrays and other possible complex types.
   ///
   /// Bitcastable constants.
   /// Let's assume, that some constant, belongs to some group of
   /// "so-called-equal" values with different types, and at the same time
   /// belongs to another group of constants with equal types
   /// and "really" equal values.
   ///
   /// Now, prove that this is impossible:
   ///
   /// If constant A with type TyA is bitcastable to B with type TyB, then:
   /// 1. All constants with equal types to TyA, are bitcastable to B. Since
   ///    those should be vectors (if TyA is vector), pointers
   ///    (if TyA is pointer), or else (if TyA equal to TyB), those types should
   ///    be equal to TyB.
   /// 2. All constants with non-equal, but bitcastable types to TyA, are
   ///    bitcastable to B.
   ///    Once again, just because we allow it to vectors and pointers only.
   ///    This statement could be expanded as below:
   /// 2.1. All vectors with equal bitwidth to vector A, has equal bitwidth to
   ///      vector B, and thus bitcastable to B as well.
   /// 2.2. All pointers of the same address space, no matter what they point to,
   ///      bitcastable. So if C is pointer, it could be bitcasted to A and to B.
   /// So any constant equal or bitcastable to A is equal or bitcastable to B.
   /// QED.
   ///
   /// In another words, for pointers and vectors, we ignore top-level type and
   /// look at their particular properties (bit-width for vectors, and
   /// address space for pointers).
   /// If these properties are equal - compare their contents.
   int cmpConstants(const Constant *L, const Constant *R) const;
 
   /// Compares two global values by number. Uses the GlobalNumbersState to
   /// identify the same gobals across function calls.
   int cmpGlobalValues(GlobalValue *L, GlobalValue *R) const;
 
   /// Assign or look up previously assigned numbers for the two values, and
   /// return whether the numbers are equal. Numbers are assigned in the order
   /// visited.
   /// Comparison order:
   /// Stage 0: Value that is function itself is always greater then others.
   ///          If left and right values are references to their functions, then
   ///          they are equal.
   /// Stage 1: Constants are greater than non-constants.
   ///          If both left and right are constants, then the result of
   ///          cmpConstants is used as cmpValues result.
   /// Stage 2: InlineAsm instances are greater than others. If both left and
   ///          right are InlineAsm instances, InlineAsm* pointers casted to
   ///          integers and compared as numbers.
   /// Stage 3: For all other cases we compare order we meet these values in
   ///          their functions. If right value was met first during scanning,
   ///          then left value is greater.
   ///          In another words, we compare serial numbers, for more details
   ///          see comments for sn_mapL and sn_mapR.
   int cmpValues(const Value *L, const Value *R) const;
 
   /// Compare two Instructions for equivalence, similar to
   /// Instruction::isSameOperationAs.
   ///
   /// Stages are listed in "most significant stage first" order:
   /// On each stage below, we do comparison between some left and right
   /// operation parts. If parts are non-equal, we assign parts comparison
   /// result to the operation comparison result and exit from method.
   /// Otherwise we proceed to the next stage.
   /// Stages:
   /// 1. Operations opcodes. Compared as numbers.
   /// 2. Number of operands.
   /// 3. Operation types. Compared with cmpType method.
   /// 4. Compare operation subclass optional data as stream of bytes:
   /// just convert it to integers and call cmpNumbers.
   /// 5. Compare in operation operand types with cmpType in
   /// most significant operand first order.
   /// 6. Last stage. Check operations for some specific attributes.
   /// For example, for Load it would be:
   /// 6.1.Load: volatile (as boolean flag)
   /// 6.2.Load: alignment (as integer numbers)
   /// 6.3.Load: ordering (as underlying enum class value)
   /// 6.4.Load: synch-scope (as integer numbers)
   /// 6.5.Load: range metadata (as integer ranges)
   /// On this stage its better to see the code, since its not more than 10-15
   /// strings for particular instruction, and could change sometimes.
   ///
   /// Sets \p needToCmpOperands to true if the operands of the instructions
   /// still must be compared afterwards. In this case it's already guaranteed
   /// that both instructions have the same number of operands.
   int cmpOperations(const Instruction *L, const Instruction *R,
                     bool &needToCmpOperands) const;
 
   /// cmpType - compares two types,
   /// defines total ordering among the types set.
   ///
   /// Return values:
   /// 0 if types are equal,
   /// -1 if Left is less than Right,
   /// +1 if Left is greater than Right.
   ///
   /// Description:
   /// Comparison is broken onto stages. Like in lexicographical comparison
   /// stage coming first has higher priority.
   /// On each explanation stage keep in mind total ordering properties.
   ///
   /// 0. Before comparison we coerce pointer types of 0 address space to
   /// integer.
   /// We also don't bother with same type at left and right, so
   /// just return 0 in this case.
   ///
   /// 1. If types are of different kind (different type IDs).
   ///    Return result of type IDs comparison, treating them as numbers.
   /// 2. If types are integers, check that they have the same width. If they
   /// are vectors, check that they have the same count and subtype.
   /// 3. Types have the same ID, so check whether they are one of:
   /// * Void
   /// * Float
   /// * Double
   /// * X86_FP80
   /// * FP128
   /// * PPC_FP128
   /// * Label
   /// * Metadata
   /// We can treat these types as equal whenever their IDs are same.
   /// 4. If Left and Right are pointers, return result of address space
   /// comparison (numbers comparison). We can treat pointer types of same
   /// address space as equal.
   /// 5. If types are complex.
   /// Then both Left and Right are to be expanded and their element types will
   /// be checked with the same way. If we get Res != 0 on some stage, return it.
   /// Otherwise return 0.
   /// 6. For all other cases put llvm_unreachable.
   int cmpTypes(Type *TyL, Type *TyR) const;
 
   int cmpNumbers(uint64_t L, uint64_t R) const;
   int cmpAligns(Align L, Align R) const;
   int cmpAPInts(const APInt &L, const APInt &R) const;
   int cmpConstantRanges(const ConstantRange &L, const ConstantRange &R) const;
   int cmpAPFloats(const APFloat &L, const APFloat &R) const;
   int cmpMem(StringRef L, StringRef R) const;
 
   // The two functions undergoing comparison.
   const Function *FnL, *FnR;
 
 private:
   int cmpOrderings(AtomicOrdering L, AtomicOrdering R) const;
   int cmpInlineAsm(const InlineAsm *L, const InlineAsm *R) const;
   int cmpAttrs(const AttributeList L, const AttributeList R) const;
   int cmpMDNode(const MDNode *L, const MDNode *R) const;
   int cmpMetadata(const Metadata *L, const Metadata *R) const;
   int cmpInstMetadata(Instruction const *L, Instruction const *R) const;
   int cmpOperandBundlesSchema(const CallBase &LCS, const CallBase &RCS) const;
 
   /// Compare two GEPs for equivalent pointer arithmetic.
   /// Parts to be compared for each comparison stage,
   /// most significant stage first:
   /// 1. Address space. As numbers.
   /// 2. Constant offset, (using GEPOperator::accumulateConstantOffset method).
   /// 3. Pointer operand type (using cmpType method).
   /// 4. Number of operands.
   /// 5. Compare operands, using cmpValues method.
   int cmpGEPs(const GEPOperator *GEPL, const GEPOperator *GEPR) const;
   int cmpGEPs(const GetElementPtrInst *GEPL,
               const GetElementPtrInst *GEPR) const {
     return cmpGEPs(cast<GEPOperator>(GEPL), cast<GEPOperator>(GEPR));
   }
 
   /// Assign serial numbers to values from left function, and values from
   /// right function.
   /// Explanation:
   /// Being comparing functions we need to compare values we meet at left and
   /// right sides.
   /// Its easy to sort things out for external values. It just should be
   /// the same value at left and right.
   /// But for local values (those were introduced inside function body)
   /// we have to ensure they were introduced at exactly the same place,
   /// and plays the same role.
   /// Let's assign serial number to each value when we meet it first time.
   /// Values that were met at same place will be with same serial numbers.
   /// In this case it would be good to explain few points about values assigned
   /// to BBs and other ways of implementation (see below).
   ///
   /// 1. Safety of BB reordering.
   /// It's safe to change the order of BasicBlocks in function.
   /// Relationship with other functions and serial numbering will not be
   /// changed in this case.
   /// As follows from FunctionComparator::compare(), we do CFG walk: we start
   /// from the entry, and then take each terminator. So it doesn't matter how in
   /// fact BBs are ordered in function. And since cmpValues are called during
   /// this walk, the numbering depends only on how BBs located inside the CFG.
   /// So the answer is - yes. We will get the same numbering.
   ///
   /// 2. Impossibility to use dominance properties of values.
   /// If we compare two instruction operands: first is usage of local
   /// variable AL from function FL, and second is usage of local variable AR
   /// from FR, we could compare their origins and check whether they are
   /// defined at the same place.
   /// But, we are still not able to compare operands of PHI nodes, since those
   /// could be operands from further BBs we didn't scan yet.
   /// So it's impossible to use dominance properties in general.
   mutable DenseMap<const Value*, int> sn_mapL, sn_mapR;
 
   // The global state we will use
   GlobalNumberState* GlobalNumbers;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H

This page was automatically generated by the 2.3.7 LXR engine. The LXR team