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