LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Utils - FunctionComparator.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 12 12 100.0 %
Date: 2018-02-23 15:42:53 Functions: 1 1 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- FunctionComparator.h - Function Comparator ---------------*- C++ -*-===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file defines the FunctionComparator and GlobalNumberState classes which
      11             : // are used by the MergeFunctions pass for comparing functions.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #ifndef LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H
      16             : #define LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H
      17             : 
      18             : #include "llvm/ADT/DenseMap.h"
      19             : #include "llvm/ADT/StringRef.h"
      20             : #include "llvm/IR/Attributes.h"
      21             : #include "llvm/IR/Instructions.h" 
      22             : #include "llvm/IR/Operator.h"
      23             : #include "llvm/IR/ValueMap.h"
      24             : #include "llvm/Support/AtomicOrdering.h"
      25             : #include "llvm/Support/Casting.h"
      26             : #include <cstdint>
      27             : #include <tuple>
      28             : 
      29             : namespace llvm {
      30             : 
      31             : class APFloat;
      32             : class APInt;
      33             : class BasicBlock;
      34             : class Constant;
      35             : class Function;
      36             : class GlobalValue;
      37             : class InlineAsm;
      38             : class Instruction;
      39             : class MDNode;
      40             : class Type;
      41             : class Value;
      42             : 
      43             : /// GlobalNumberState assigns an integer to each global value in the program,
      44             : /// which is used by the comparison routine to order references to globals. This
      45             : /// state must be preserved throughout the pass, because Functions and other
      46             : /// globals need to maintain their relative order. Globals are assigned a number
      47             : /// when they are first visited. This order is deterministic, and so the
      48             : /// assigned numbers are as well. When two functions are merged, neither number
      49             : /// is updated. If the symbols are weak, this would be incorrect. If they are
      50             : /// strong, then one will be replaced at all references to the other, and so
      51             : /// direct callsites will now see one or the other symbol, and no update is
      52             : /// necessary. Note that if we were guaranteed unique names, we could just
      53             : /// compare those, but this would not work for stripped bitcodes or for those
      54             : /// few symbols without a name.
      55          49 : class GlobalNumberState {
      56             :   struct Config : ValueMapConfig<GlobalValue *> {
      57             :     enum { FollowRAUW = false };
      58             :   };
      59             : 
      60             :   // Each GlobalValue is mapped to an identifier. The Config ensures when RAUW
      61             :   // occurs, the mapping does not change. Tracking changes is unnecessary, and
      62             :   // also problematic for weak symbols (which may be overwritten).
      63             :   using ValueNumberMap = ValueMap<GlobalValue *, uint64_t, Config>;
      64             :   ValueNumberMap GlobalNumbers;
      65             : 
      66             :   // The next unused serial number to assign to a global.
      67             :   uint64_t NextNumber = 0;
      68             : 
      69             : public:
      70          49 :   GlobalNumberState() = default;
      71             : 
      72          26 :   uint64_t getNumber(GlobalValue* Global) {
      73             :     ValueNumberMap::iterator MapIter;
      74             :     bool Inserted;
      75          78 :     std::tie(MapIter, Inserted) = GlobalNumbers.insert({Global, NextNumber});
      76          26 :     if (Inserted)
      77          11 :       NextNumber++;
      78          26 :     return MapIter->second;
      79             :   }
      80             : 
      81             :   void erase(GlobalValue *Global) {
      82           4 :     GlobalNumbers.erase(Global);
      83             :   }
      84             : 
      85             :   void clear() {
      86             :     GlobalNumbers.clear();
      87             :   }
      88             : };
      89             : 
      90             : /// FunctionComparator - Compares two functions to determine whether or not
      91             : /// they will generate machine code with the same behaviour. DataLayout is
      92             : /// used if available. The comparator always fails conservatively (erring on the
      93             : /// side of claiming that two functions are different).
      94             : class FunctionComparator {
      95             : public:
      96             :   FunctionComparator(const Function *F1, const Function *F2,
      97             :                      GlobalNumberState* GN)
      98         384 :       : FnL(F1), FnR(F2), GlobalNumbers(GN) {}
      99             : 
     100             :   /// Test whether the two functions have equivalent behaviour.
     101             :   int compare();
     102             : 
     103             :   /// Hash a function. Equivalent functions will have the same hash, and unequal
     104             :   /// functions will have different hashes with high probability.
     105             :   using FunctionHash = uint64_t;
     106             :   static FunctionHash functionHash(Function &);
     107             : 
     108             : protected:
     109             :   /// Start the comparison.
     110             :   void beginCompare() {
     111         200 :     sn_mapL.clear();
     112         200 :     sn_mapR.clear();
     113             :   }
     114             : 
     115             :   /// Compares the signature and other general attributes of the two functions.
     116             :   int compareSignature() const;
     117             : 
     118             :   /// Test whether two basic blocks have equivalent behaviour.
     119             :   int cmpBasicBlocks(const BasicBlock *BBL, const BasicBlock *BBR) const;
     120             : 
     121             :   /// Constants comparison.
     122             :   /// Its analog to lexicographical comparison between hypothetical numbers
     123             :   /// of next format:
     124             :   /// <bitcastability-trait><raw-bit-contents>
     125             :   ///
     126             :   /// 1. Bitcastability.
     127             :   /// Check whether L's type could be losslessly bitcasted to R's type.
     128             :   /// On this stage method, in case when lossless bitcast is not possible
     129             :   /// method returns -1 or 1, thus also defining which type is greater in
     130             :   /// context of bitcastability.
     131             :   /// Stage 0: If types are equal in terms of cmpTypes, then we can go straight
     132             :   ///          to the contents comparison.
     133             :   ///          If types differ, remember types comparison result and check
     134             :   ///          whether we still can bitcast types.
     135             :   /// Stage 1: Types that satisfies isFirstClassType conditions are always
     136             :   ///          greater then others.
     137             :   /// Stage 2: Vector is greater then non-vector.
     138             :   ///          If both types are vectors, then vector with greater bitwidth is
     139             :   ///          greater.
     140             :   ///          If both types are vectors with the same bitwidth, then types
     141             :   ///          are bitcastable, and we can skip other stages, and go to contents
     142             :   ///          comparison.
     143             :   /// Stage 3: Pointer types are greater than non-pointers. If both types are
     144             :   ///          pointers of the same address space - go to contents comparison.
     145             :   ///          Different address spaces: pointer with greater address space is
     146             :   ///          greater.
     147             :   /// Stage 4: Types are neither vectors, nor pointers. And they differ.
     148             :   ///          We don't know how to bitcast them. So, we better don't do it,
     149             :   ///          and return types comparison result (so it determines the
     150             :   ///          relationship among constants we don't know how to bitcast).
     151             :   ///
     152             :   /// Just for clearance, let's see how the set of constants could look
     153             :   /// on single dimension axis:
     154             :   ///
     155             :   /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors]
     156             :   /// Where: NFCT - Not a FirstClassType
     157             :   ///        FCT - FirstClassTyp:
     158             :   ///
     159             :   /// 2. Compare raw contents.
     160             :   /// It ignores types on this stage and only compares bits from L and R.
     161             :   /// Returns 0, if L and R has equivalent contents.
     162             :   /// -1 or 1 if values are different.
     163             :   /// Pretty trivial:
     164             :   /// 2.1. If contents are numbers, compare numbers.
     165             :   ///    Ints with greater bitwidth are greater. Ints with same bitwidths
     166             :   ///    compared by their contents.
     167             :   /// 2.2. "And so on". Just to avoid discrepancies with comments
     168             :   /// perhaps it would be better to read the implementation itself.
     169             :   /// 3. And again about overall picture. Let's look back at how the ordered set
     170             :   /// of constants will look like:
     171             :   /// [NFCT], [FCT, "others"], [FCT, pointers], [FCT, vectors]
     172             :   ///
     173             :   /// Now look, what could be inside [FCT, "others"], for example:
     174             :   /// [FCT, "others"] =
     175             :   /// [
     176             :   ///   [double 0.1], [double 1.23],
     177             :   ///   [i32 1], [i32 2],
     178             :   ///   { double 1.0 },       ; StructTyID, NumElements = 1
     179             :   ///   { i32 1 },            ; StructTyID, NumElements = 1
     180             :   ///   { double 1, i32 1 },  ; StructTyID, NumElements = 2
     181             :   ///   { i32 1, double 1 }   ; StructTyID, NumElements = 2
     182             :   /// ]
     183             :   ///
     184             :   /// Let's explain the order. Float numbers will be less than integers, just
     185             :   /// because of cmpType terms: FloatTyID < IntegerTyID.
     186             :   /// Floats (with same fltSemantics) are sorted according to their value.
     187             :   /// Then you can see integers, and they are, like a floats,
     188             :   /// could be easy sorted among each others.
     189             :   /// The structures. Structures are grouped at the tail, again because of their
     190             :   /// TypeID: StructTyID > IntegerTyID > FloatTyID.
     191             :   /// Structures with greater number of elements are greater. Structures with
     192             :   /// greater elements going first are greater.
     193             :   /// The same logic with vectors, arrays and other possible complex types.
     194             :   ///
     195             :   /// Bitcastable constants.
     196             :   /// Let's assume, that some constant, belongs to some group of
     197             :   /// "so-called-equal" values with different types, and at the same time
     198             :   /// belongs to another group of constants with equal types
     199             :   /// and "really" equal values.
     200             :   ///
     201             :   /// Now, prove that this is impossible:
     202             :   ///
     203             :   /// If constant A with type TyA is bitcastable to B with type TyB, then:
     204             :   /// 1. All constants with equal types to TyA, are bitcastable to B. Since
     205             :   ///    those should be vectors (if TyA is vector), pointers
     206             :   ///    (if TyA is pointer), or else (if TyA equal to TyB), those types should
     207             :   ///    be equal to TyB.
     208             :   /// 2. All constants with non-equal, but bitcastable types to TyA, are
     209             :   ///    bitcastable to B.
     210             :   ///    Once again, just because we allow it to vectors and pointers only.
     211             :   ///    This statement could be expanded as below:
     212             :   /// 2.1. All vectors with equal bitwidth to vector A, has equal bitwidth to
     213             :   ///      vector B, and thus bitcastable to B as well.
     214             :   /// 2.2. All pointers of the same address space, no matter what they point to,
     215             :   ///      bitcastable. So if C is pointer, it could be bitcasted to A and to B.
     216             :   /// So any constant equal or bitcastable to A is equal or bitcastable to B.
     217             :   /// QED.
     218             :   ///
     219             :   /// In another words, for pointers and vectors, we ignore top-level type and
     220             :   /// look at their particular properties (bit-width for vectors, and
     221             :   /// address space for pointers).
     222             :   /// If these properties are equal - compare their contents.
     223             :   int cmpConstants(const Constant *L, const Constant *R) const;
     224             : 
     225             :   /// Compares two global values by number. Uses the GlobalNumbersState to
     226             :   /// identify the same gobals across function calls.
     227             :   int cmpGlobalValues(GlobalValue *L, GlobalValue *R) const;
     228             : 
     229             :   /// Assign or look up previously assigned numbers for the two values, and
     230             :   /// return whether the numbers are equal. Numbers are assigned in the order
     231             :   /// visited.
     232             :   /// Comparison order:
     233             :   /// Stage 0: Value that is function itself is always greater then others.
     234             :   ///          If left and right values are references to their functions, then
     235             :   ///          they are equal.
     236             :   /// Stage 1: Constants are greater than non-constants.
     237             :   ///          If both left and right are constants, then the result of
     238             :   ///          cmpConstants is used as cmpValues result.
     239             :   /// Stage 2: InlineAsm instances are greater than others. If both left and
     240             :   ///          right are InlineAsm instances, InlineAsm* pointers casted to
     241             :   ///          integers and compared as numbers.
     242             :   /// Stage 3: For all other cases we compare order we meet these values in
     243             :   ///          their functions. If right value was met first during scanning,
     244             :   ///          then left value is greater.
     245             :   ///          In another words, we compare serial numbers, for more details
     246             :   ///          see comments for sn_mapL and sn_mapR.
     247             :   int cmpValues(const Value *L, const Value *R) const;
     248             : 
     249             :   /// Compare two Instructions for equivalence, similar to
     250             :   /// Instruction::isSameOperationAs.
     251             :   ///
     252             :   /// Stages are listed in "most significant stage first" order:
     253             :   /// On each stage below, we do comparison between some left and right
     254             :   /// operation parts. If parts are non-equal, we assign parts comparison
     255             :   /// result to the operation comparison result and exit from method.
     256             :   /// Otherwise we proceed to the next stage.
     257             :   /// Stages:
     258             :   /// 1. Operations opcodes. Compared as numbers.
     259             :   /// 2. Number of operands.
     260             :   /// 3. Operation types. Compared with cmpType method.
     261             :   /// 4. Compare operation subclass optional data as stream of bytes:
     262             :   /// just convert it to integers and call cmpNumbers.
     263             :   /// 5. Compare in operation operand types with cmpType in
     264             :   /// most significant operand first order.
     265             :   /// 6. Last stage. Check operations for some specific attributes.
     266             :   /// For example, for Load it would be:
     267             :   /// 6.1.Load: volatile (as boolean flag)
     268             :   /// 6.2.Load: alignment (as integer numbers)
     269             :   /// 6.3.Load: ordering (as underlying enum class value)
     270             :   /// 6.4.Load: synch-scope (as integer numbers)
     271             :   /// 6.5.Load: range metadata (as integer ranges)
     272             :   /// On this stage its better to see the code, since its not more than 10-15
     273             :   /// strings for particular instruction, and could change sometimes.
     274             :   ///
     275             :   /// Sets \p needToCmpOperands to true if the operands of the instructions
     276             :   /// still must be compared afterwards. In this case it's already guaranteed
     277             :   /// that both instructions have the same number of operands.
     278             :   int cmpOperations(const Instruction *L, const Instruction *R,
     279             :                     bool &needToCmpOperands) const;
     280             : 
     281             :   /// cmpType - compares two types,
     282             :   /// defines total ordering among the types set.
     283             :   ///
     284             :   /// Return values:
     285             :   /// 0 if types are equal,
     286             :   /// -1 if Left is less than Right,
     287             :   /// +1 if Left is greater than Right.
     288             :   ///
     289             :   /// Description:
     290             :   /// Comparison is broken onto stages. Like in lexicographical comparison
     291             :   /// stage coming first has higher priority.
     292             :   /// On each explanation stage keep in mind total ordering properties.
     293             :   ///
     294             :   /// 0. Before comparison we coerce pointer types of 0 address space to
     295             :   /// integer.
     296             :   /// We also don't bother with same type at left and right, so
     297             :   /// just return 0 in this case.
     298             :   ///
     299             :   /// 1. If types are of different kind (different type IDs).
     300             :   ///    Return result of type IDs comparison, treating them as numbers.
     301             :   /// 2. If types are integers, check that they have the same width. If they
     302             :   /// are vectors, check that they have the same count and subtype.
     303             :   /// 3. Types have the same ID, so check whether they are one of:
     304             :   /// * Void
     305             :   /// * Float
     306             :   /// * Double
     307             :   /// * X86_FP80
     308             :   /// * FP128
     309             :   /// * PPC_FP128
     310             :   /// * Label
     311             :   /// * Metadata
     312             :   /// We can treat these types as equal whenever their IDs are same.
     313             :   /// 4. If Left and Right are pointers, return result of address space
     314             :   /// comparison (numbers comparison). We can treat pointer types of same
     315             :   /// address space as equal.
     316             :   /// 5. If types are complex.
     317             :   /// Then both Left and Right are to be expanded and their element types will
     318             :   /// be checked with the same way. If we get Res != 0 on some stage, return it.
     319             :   /// Otherwise return 0.
     320             :   /// 6. For all other cases put llvm_unreachable.
     321             :   int cmpTypes(Type *TyL, Type *TyR) const;
     322             : 
     323             :   int cmpNumbers(uint64_t L, uint64_t R) const;
     324             :   int cmpAPInts(const APInt &L, const APInt &R) const;
     325             :   int cmpAPFloats(const APFloat &L, const APFloat &R) const;
     326             :   int cmpMem(StringRef L, StringRef R) const;
     327             : 
     328             :   // The two functions undergoing comparison.
     329             :   const Function *FnL, *FnR;
     330             : 
     331             : private:
     332             :   int cmpOrderings(AtomicOrdering L, AtomicOrdering R) const;
     333             :   int cmpInlineAsm(const InlineAsm *L, const InlineAsm *R) const;
     334             :   int cmpAttrs(const AttributeList L, const AttributeList R) const;
     335             :   int cmpRangeMetadata(const MDNode *L, const MDNode *R) const;
     336             :   int cmpOperandBundlesSchema(const Instruction *L, const Instruction *R) const;
     337             : 
     338             :   /// Compare two GEPs for equivalent pointer arithmetic.
     339             :   /// Parts to be compared for each comparison stage,
     340             :   /// most significant stage first:
     341             :   /// 1. Address space. As numbers.
     342             :   /// 2. Constant offset, (using GEPOperator::accumulateConstantOffset method).
     343             :   /// 3. Pointer operand type (using cmpType method).
     344             :   /// 4. Number of operands.
     345             :   /// 5. Compare operands, using cmpValues method.
     346             :   int cmpGEPs(const GEPOperator *GEPL, const GEPOperator *GEPR) const;
     347             :   int cmpGEPs(const GetElementPtrInst *GEPL,
     348             :               const GetElementPtrInst *GEPR) const {
     349          35 :     return cmpGEPs(cast<GEPOperator>(GEPL), cast<GEPOperator>(GEPR));
     350             :   }
     351             : 
     352             :   /// Assign serial numbers to values from left function, and values from
     353             :   /// right function.
     354             :   /// Explanation:
     355             :   /// Being comparing functions we need to compare values we meet at left and
     356             :   /// right sides.
     357             :   /// Its easy to sort things out for external values. It just should be
     358             :   /// the same value at left and right.
     359             :   /// But for local values (those were introduced inside function body)
     360             :   /// we have to ensure they were introduced at exactly the same place,
     361             :   /// and plays the same role.
     362             :   /// Let's assign serial number to each value when we meet it first time.
     363             :   /// Values that were met at same place will be with same serial numbers.
     364             :   /// In this case it would be good to explain few points about values assigned
     365             :   /// to BBs and other ways of implementation (see below).
     366             :   ///
     367             :   /// 1. Safety of BB reordering.
     368             :   /// It's safe to change the order of BasicBlocks in function.
     369             :   /// Relationship with other functions and serial numbering will not be
     370             :   /// changed in this case.
     371             :   /// As follows from FunctionComparator::compare(), we do CFG walk: we start
     372             :   /// from the entry, and then take each terminator. So it doesn't matter how in
     373             :   /// fact BBs are ordered in function. And since cmpValues are called during
     374             :   /// this walk, the numbering depends only on how BBs located inside the CFG.
     375             :   /// So the answer is - yes. We will get the same numbering.
     376             :   ///
     377             :   /// 2. Impossibility to use dominance properties of values.
     378             :   /// If we compare two instruction operands: first is usage of local
     379             :   /// variable AL from function FL, and second is usage of local variable AR
     380             :   /// from FR, we could compare their origins and check whether they are
     381             :   /// defined at the same place.
     382             :   /// But, we are still not able to compare operands of PHI nodes, since those
     383             :   /// could be operands from further BBs we didn't scan yet.
     384             :   /// So it's impossible to use dominance properties in general.
     385             :   mutable DenseMap<const Value*, int> sn_mapL, sn_mapR;
     386             : 
     387             :   // The global state we will use
     388             :   GlobalNumberState* GlobalNumbers;
     389             : };
     390             : 
     391             : } // end namespace llvm
     392             : 
     393             : #endif // LLVM_TRANSFORMS_UTILS_FUNCTIONCOMPARATOR_H

Generated by: LCOV version 1.13