Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- 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