//===- 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();
/// Hash a function. Equivalent functions will have the same hash, and unequal
/// functions will have different hashes with high probability.
using FunctionHash = uint64_t;
static FunctionHash functionHash(Function &);
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 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 cmpRangeMetadata(const MDNode *L, const MDNode *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