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 1 : 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 51 : GlobalNumberState() = default;
71 :
72 26 : uint64_t getNumber(GlobalValue* Global) {
73 : ValueNumberMap::iterator MapIter;
74 : bool Inserted;
75 52 : 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 2 : : 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 209 : sn_mapL.clear();
112 209 : 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
|
