swiftshader / SwiftShader / refs/heads/llvm10-clean / . / third_party / llvm-10.0 / llvm / include / llvm / Transforms / Utils / FunctionComparator.h

//===- 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/Attributes.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 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 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 Instruction *L, const Instruction *R) 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 |