LLVM  6.0.0svn
FunctionComparator.h
Go to the documentation of this file.
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"
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.
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).
64  ValueNumberMap GlobalNumbers;
65 
66  // The next unused serial number to assign to a global.
67  uint64_t NextNumber = 0;
68 
69 public:
70  GlobalNumberState() = default;
71 
72  uint64_t getNumber(GlobalValue* Global) {
74  bool Inserted;
75  std::tie(MapIter, Inserted) = GlobalNumbers.insert({Global, NextNumber});
76  if (Inserted)
77  NextNumber++;
78  return MapIter->second;
79  }
80 
81  void erase(GlobalValue *Global) {
82  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).
95 public:
96  FunctionComparator(const Function *F1, const Function *F2,
98  : 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  sn_mapL.clear();
112  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  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
void clear()
Definition: ValueMap.h:148
Atomic ordering constants.
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: ValueMap.h:175
Various leaf nodes.
Definition: ISDOpcodes.h:60
This class defines the default behavior for configurable aspects of ValueMap<>.
Definition: ValueMap.h:58
Metadata node.
Definition: Metadata.h:862
uint64_t FunctionHash
Hash a function.
FunctionComparator(const Function *F1, const Function *F2, GlobalNumberState *GN)
This file contains the simple types necessary to represent the attributes associated with functions a...
AtomicOrdering
Atomic ordering for LLVM&#39;s memory model.
void beginCompare()
Start the comparison.
uint64_t getNumber(GlobalValue *Global)
void erase(GlobalValue *Global)
an instruction for type-safe pointer arithmetic to access elements of arrays and structs ...
Definition: Instructions.h:837
FunctionComparator - Compares two functions to determine whether or not they will generate machine co...
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
The instances of the Type class are immutable: once they are created, they are never changed...
Definition: Type.h:46
This is an important base class in LLVM.
Definition: Constant.h:42
GlobalNumberState assigns an integer to each global value in the program, which is used by the compar...
Class for arbitrary precision integers.
Definition: APInt.h:69
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
Definition: ScaledNumber.h:252
LLVM Value Representation.
Definition: Value.h:73
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:49
bool erase(const KeyT &Val)
Definition: ValueMap.h:193