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

source code of llvm/include/llvm/Transforms/Utils/FunctionComparator.h