LLVM  15.0.0git
FunctionComparator.cpp
Go to the documentation of this file.
1 //===- FunctionComparator.h - Function Comparator -------------------------===//
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 implements the FunctionComparator and GlobalNumberState classes
10 // which are used by the MergeFunctions pass for comparing functions.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/APFloat.h"
16 #include "llvm/ADT/APInt.h"
17 #include "llvm/ADT/ArrayRef.h"
18 #include "llvm/ADT/Hashing.h"
19 #include "llvm/ADT/SmallPtrSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/IR/Attributes.h"
22 #include "llvm/IR/BasicBlock.h"
23 #include "llvm/IR/Constant.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/DataLayout.h"
26 #include "llvm/IR/DerivedTypes.h"
27 #include "llvm/IR/Function.h"
28 #include "llvm/IR/GlobalValue.h"
29 #include "llvm/IR/InlineAsm.h"
30 #include "llvm/IR/InstrTypes.h"
31 #include "llvm/IR/Instruction.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/LLVMContext.h"
34 #include "llvm/IR/Metadata.h"
35 #include "llvm/IR/Module.h"
36 #include "llvm/IR/Operator.h"
37 #include "llvm/IR/Type.h"
38 #include "llvm/IR/Value.h"
39 #include "llvm/Support/Casting.h"
40 #include "llvm/Support/Compiler.h"
41 #include "llvm/Support/Debug.h"
44 #include <cassert>
45 #include <cstddef>
46 #include <cstdint>
47 #include <utility>
48 
49 using namespace llvm;
50 
51 #define DEBUG_TYPE "functioncomparator"
52 
54  if (L < R)
55  return -1;
56  if (L > R)
57  return 1;
58  return 0;
59 }
60 
62  if (L.value() < R.value())
63  return -1;
64  if (L.value() > R.value())
65  return 1;
66  return 0;
67 }
68 
69 int FunctionComparator::cmpOrderings(AtomicOrdering L, AtomicOrdering R) const {
70  if ((int)L < (int)R)
71  return -1;
72  if ((int)L > (int)R)
73  return 1;
74  return 0;
75 }
76 
77 int FunctionComparator::cmpAPInts(const APInt &L, const APInt &R) const {
78  if (int Res = cmpNumbers(L.getBitWidth(), R.getBitWidth()))
79  return Res;
80  if (L.ugt(R))
81  return 1;
82  if (R.ugt(L))
83  return -1;
84  return 0;
85 }
86 
87 int FunctionComparator::cmpAPFloats(const APFloat &L, const APFloat &R) const {
88  // Floats are ordered first by semantics (i.e. float, double, half, etc.),
89  // then by value interpreted as a bitstring (aka APInt).
90  const fltSemantics &SL = L.getSemantics(), &SR = R.getSemantics();
91  if (int Res = cmpNumbers(APFloat::semanticsPrecision(SL),
93  return Res;
94  if (int Res = cmpNumbers(APFloat::semanticsMaxExponent(SL),
96  return Res;
97  if (int Res = cmpNumbers(APFloat::semanticsMinExponent(SL),
99  return Res;
100  if (int Res = cmpNumbers(APFloat::semanticsSizeInBits(SL),
102  return Res;
103  return cmpAPInts(L.bitcastToAPInt(), R.bitcastToAPInt());
104 }
105 
107  // Prevent heavy comparison, compare sizes first.
108  if (int Res = cmpNumbers(L.size(), R.size()))
109  return Res;
110 
111  // Compare strings lexicographically only when it is necessary: only when
112  // strings are equal in size.
113  return L.compare(R);
114 }
115 
116 int FunctionComparator::cmpAttrs(const AttributeList L,
117  const AttributeList R) const {
118  if (int Res = cmpNumbers(L.getNumAttrSets(), R.getNumAttrSets()))
119  return Res;
120 
121  for (unsigned i : L.indexes()) {
122  AttributeSet LAS = L.getAttributes(i);
123  AttributeSet RAS = R.getAttributes(i);
124  AttributeSet::iterator LI = LAS.begin(), LE = LAS.end();
125  AttributeSet::iterator RI = RAS.begin(), RE = RAS.end();
126  for (; LI != LE && RI != RE; ++LI, ++RI) {
127  Attribute LA = *LI;
128  Attribute RA = *RI;
129  if (LA.isTypeAttribute() && RA.isTypeAttribute()) {
130  if (LA.getKindAsEnum() != RA.getKindAsEnum())
131  return cmpNumbers(LA.getKindAsEnum(), RA.getKindAsEnum());
132 
133  Type *TyL = LA.getValueAsType();
134  Type *TyR = RA.getValueAsType();
135  if (TyL && TyR) {
136  if (int Res = cmpTypes(TyL, TyR))
137  return Res;
138  continue;
139  }
140 
141  // Two pointers, at least one null, so the comparison result is
142  // independent of the value of a real pointer.
143  if (int Res = cmpNumbers((uint64_t)TyL, (uint64_t)TyR))
144  return Res;
145  continue;
146  }
147  if (LA < RA)
148  return -1;
149  if (RA < LA)
150  return 1;
151  }
152  if (LI != LE)
153  return 1;
154  if (RI != RE)
155  return -1;
156  }
157  return 0;
158 }
159 
160 int FunctionComparator::cmpRangeMetadata(const MDNode *L,
161  const MDNode *R) const {
162  if (L == R)
163  return 0;
164  if (!L)
165  return -1;
166  if (!R)
167  return 1;
168  // Range metadata is a sequence of numbers. Make sure they are the same
169  // sequence.
170  // TODO: Note that as this is metadata, it is possible to drop and/or merge
171  // this data when considering functions to merge. Thus this comparison would
172  // return 0 (i.e. equivalent), but merging would become more complicated
173  // because the ranges would need to be unioned. It is not likely that
174  // functions differ ONLY in this metadata if they are actually the same
175  // function semantically.
176  if (int Res = cmpNumbers(L->getNumOperands(), R->getNumOperands()))
177  return Res;
178  for (size_t I = 0; I < L->getNumOperands(); ++I) {
179  ConstantInt *LLow = mdconst::extract<ConstantInt>(L->getOperand(I));
180  ConstantInt *RLow = mdconst::extract<ConstantInt>(R->getOperand(I));
181  if (int Res = cmpAPInts(LLow->getValue(), RLow->getValue()))
182  return Res;
183  }
184  return 0;
185 }
186 
187 int FunctionComparator::cmpOperandBundlesSchema(const CallBase &LCS,
188  const CallBase &RCS) const {
189  assert(LCS.getOpcode() == RCS.getOpcode() && "Can't compare otherwise!");
190 
191  if (int Res =
193  return Res;
194 
195  for (unsigned I = 0, E = LCS.getNumOperandBundles(); I != E; ++I) {
196  auto OBL = LCS.getOperandBundleAt(I);
197  auto OBR = RCS.getOperandBundleAt(I);
198 
199  if (int Res = OBL.getTagName().compare(OBR.getTagName()))
200  return Res;
201 
202  if (int Res = cmpNumbers(OBL.Inputs.size(), OBR.Inputs.size()))
203  return Res;
204  }
205 
206  return 0;
207 }
208 
209 /// Constants comparison:
210 /// 1. Check whether type of L constant could be losslessly bitcasted to R
211 /// type.
212 /// 2. Compare constant contents.
213 /// For more details see declaration comments.
215  const Constant *R) const {
216  Type *TyL = L->getType();
217  Type *TyR = R->getType();
218 
219  // Check whether types are bitcastable. This part is just re-factored
220  // Type::canLosslesslyBitCastTo method, but instead of returning true/false,
221  // we also pack into result which type is "less" for us.
222  int TypesRes = cmpTypes(TyL, TyR);
223  if (TypesRes != 0) {
224  // Types are different, but check whether we can bitcast them.
225  if (!TyL->isFirstClassType()) {
226  if (TyR->isFirstClassType())
227  return -1;
228  // Neither TyL nor TyR are values of first class type. Return the result
229  // of comparing the types
230  return TypesRes;
231  }
232  if (!TyR->isFirstClassType()) {
233  if (TyL->isFirstClassType())
234  return 1;
235  return TypesRes;
236  }
237 
238  // Vector -> Vector conversions are always lossless if the two vector types
239  // have the same size, otherwise not.
240  unsigned TyLWidth = 0;
241  unsigned TyRWidth = 0;
242 
243  if (auto *VecTyL = dyn_cast<VectorType>(TyL))
244  TyLWidth = VecTyL->getPrimitiveSizeInBits().getFixedSize();
245  if (auto *VecTyR = dyn_cast<VectorType>(TyR))
246  TyRWidth = VecTyR->getPrimitiveSizeInBits().getFixedSize();
247 
248  if (TyLWidth != TyRWidth)
249  return cmpNumbers(TyLWidth, TyRWidth);
250 
251  // Zero bit-width means neither TyL nor TyR are vectors.
252  if (!TyLWidth) {
253  PointerType *PTyL = dyn_cast<PointerType>(TyL);
254  PointerType *PTyR = dyn_cast<PointerType>(TyR);
255  if (PTyL && PTyR) {
256  unsigned AddrSpaceL = PTyL->getAddressSpace();
257  unsigned AddrSpaceR = PTyR->getAddressSpace();
258  if (int Res = cmpNumbers(AddrSpaceL, AddrSpaceR))
259  return Res;
260  }
261  if (PTyL)
262  return 1;
263  if (PTyR)
264  return -1;
265 
266  // TyL and TyR aren't vectors, nor pointers. We don't know how to
267  // bitcast them.
268  return TypesRes;
269  }
270  }
271 
272  // OK, types are bitcastable, now check constant contents.
273 
274  if (L->isNullValue() && R->isNullValue())
275  return TypesRes;
276  if (L->isNullValue() && !R->isNullValue())
277  return 1;
278  if (!L->isNullValue() && R->isNullValue())
279  return -1;
280 
281  auto GlobalValueL = const_cast<GlobalValue *>(dyn_cast<GlobalValue>(L));
282  auto GlobalValueR = const_cast<GlobalValue *>(dyn_cast<GlobalValue>(R));
283  if (GlobalValueL && GlobalValueR) {
284  return cmpGlobalValues(GlobalValueL, GlobalValueR);
285  }
286 
287  if (int Res = cmpNumbers(L->getValueID(), R->getValueID()))
288  return Res;
289 
290  if (const auto *SeqL = dyn_cast<ConstantDataSequential>(L)) {
291  const auto *SeqR = cast<ConstantDataSequential>(R);
292  // This handles ConstantDataArray and ConstantDataVector. Note that we
293  // compare the two raw data arrays, which might differ depending on the host
294  // endianness. This isn't a problem though, because the endiness of a module
295  // will affect the order of the constants, but this order is the same
296  // for a given input module and host platform.
297  return cmpMem(SeqL->getRawDataValues(), SeqR->getRawDataValues());
298  }
299 
300  switch (L->getValueID()) {
301  case Value::UndefValueVal:
302  case Value::PoisonValueVal:
303  case Value::ConstantTokenNoneVal:
304  return TypesRes;
305  case Value::ConstantIntVal: {
306  const APInt &LInt = cast<ConstantInt>(L)->getValue();
307  const APInt &RInt = cast<ConstantInt>(R)->getValue();
308  return cmpAPInts(LInt, RInt);
309  }
310  case Value::ConstantFPVal: {
311  const APFloat &LAPF = cast<ConstantFP>(L)->getValueAPF();
312  const APFloat &RAPF = cast<ConstantFP>(R)->getValueAPF();
313  return cmpAPFloats(LAPF, RAPF);
314  }
315  case Value::ConstantArrayVal: {
316  const ConstantArray *LA = cast<ConstantArray>(L);
317  const ConstantArray *RA = cast<ConstantArray>(R);
318  uint64_t NumElementsL = cast<ArrayType>(TyL)->getNumElements();
319  uint64_t NumElementsR = cast<ArrayType>(TyR)->getNumElements();
320  if (int Res = cmpNumbers(NumElementsL, NumElementsR))
321  return Res;
322  for (uint64_t i = 0; i < NumElementsL; ++i) {
323  if (int Res = cmpConstants(cast<Constant>(LA->getOperand(i)),
324  cast<Constant>(RA->getOperand(i))))
325  return Res;
326  }
327  return 0;
328  }
329  case Value::ConstantStructVal: {
330  const ConstantStruct *LS = cast<ConstantStruct>(L);
331  const ConstantStruct *RS = cast<ConstantStruct>(R);
332  unsigned NumElementsL = cast<StructType>(TyL)->getNumElements();
333  unsigned NumElementsR = cast<StructType>(TyR)->getNumElements();
334  if (int Res = cmpNumbers(NumElementsL, NumElementsR))
335  return Res;
336  for (unsigned i = 0; i != NumElementsL; ++i) {
337  if (int Res = cmpConstants(cast<Constant>(LS->getOperand(i)),
338  cast<Constant>(RS->getOperand(i))))
339  return Res;
340  }
341  return 0;
342  }
343  case Value::ConstantVectorVal: {
344  const ConstantVector *LV = cast<ConstantVector>(L);
345  const ConstantVector *RV = cast<ConstantVector>(R);
346  unsigned NumElementsL = cast<FixedVectorType>(TyL)->getNumElements();
347  unsigned NumElementsR = cast<FixedVectorType>(TyR)->getNumElements();
348  if (int Res = cmpNumbers(NumElementsL, NumElementsR))
349  return Res;
350  for (uint64_t i = 0; i < NumElementsL; ++i) {
351  if (int Res = cmpConstants(cast<Constant>(LV->getOperand(i)),
352  cast<Constant>(RV->getOperand(i))))
353  return Res;
354  }
355  return 0;
356  }
357  case Value::ConstantExprVal: {
358  const ConstantExpr *LE = cast<ConstantExpr>(L);
359  const ConstantExpr *RE = cast<ConstantExpr>(R);
360  unsigned NumOperandsL = LE->getNumOperands();
361  unsigned NumOperandsR = RE->getNumOperands();
362  if (int Res = cmpNumbers(NumOperandsL, NumOperandsR))
363  return Res;
364  for (unsigned i = 0; i < NumOperandsL; ++i) {
365  if (int Res = cmpConstants(cast<Constant>(LE->getOperand(i)),
366  cast<Constant>(RE->getOperand(i))))
367  return Res;
368  }
369  return 0;
370  }
371  case Value::BlockAddressVal: {
372  const BlockAddress *LBA = cast<BlockAddress>(L);
373  const BlockAddress *RBA = cast<BlockAddress>(R);
374  if (int Res = cmpValues(LBA->getFunction(), RBA->getFunction()))
375  return Res;
376  if (LBA->getFunction() == RBA->getFunction()) {
377  // They are BBs in the same function. Order by which comes first in the
378  // BB order of the function. This order is deterministic.
379  Function *F = LBA->getFunction();
380  BasicBlock *LBB = LBA->getBasicBlock();
381  BasicBlock *RBB = RBA->getBasicBlock();
382  if (LBB == RBB)
383  return 0;
384  for (BasicBlock &BB : F->getBasicBlockList()) {
385  if (&BB == LBB) {
386  assert(&BB != RBB);
387  return -1;
388  }
389  if (&BB == RBB)
390  return 1;
391  }
392  llvm_unreachable("Basic Block Address does not point to a basic block in "
393  "its function.");
394  return -1;
395  } else {
396  // cmpValues said the functions are the same. So because they aren't
397  // literally the same pointer, they must respectively be the left and
398  // right functions.
399  assert(LBA->getFunction() == FnL && RBA->getFunction() == FnR);
400  // cmpValues will tell us if these are equivalent BasicBlocks, in the
401  // context of their respective functions.
402  return cmpValues(LBA->getBasicBlock(), RBA->getBasicBlock());
403  }
404  }
405  default: // Unknown constant, abort.
406  LLVM_DEBUG(dbgs() << "Looking at valueID " << L->getValueID() << "\n");
407  llvm_unreachable("Constant ValueID not recognized.");
408  return -1;
409  }
410 }
411 
413  uint64_t LNumber = GlobalNumbers->getNumber(L);
414  uint64_t RNumber = GlobalNumbers->getNumber(R);
415  return cmpNumbers(LNumber, RNumber);
416 }
417 
418 /// cmpType - compares two types,
419 /// defines total ordering among the types set.
420 /// See method declaration comments for more details.
421 int FunctionComparator::cmpTypes(Type *TyL, Type *TyR) const {
422  PointerType *PTyL = dyn_cast<PointerType>(TyL);
423  PointerType *PTyR = dyn_cast<PointerType>(TyR);
424 
425  const DataLayout &DL = FnL->getParent()->getDataLayout();
426  if (PTyL && PTyL->getAddressSpace() == 0)
427  TyL = DL.getIntPtrType(TyL);
428  if (PTyR && PTyR->getAddressSpace() == 0)
429  TyR = DL.getIntPtrType(TyR);
430 
431  if (TyL == TyR)
432  return 0;
433 
434  if (int Res = cmpNumbers(TyL->getTypeID(), TyR->getTypeID()))
435  return Res;
436 
437  switch (TyL->getTypeID()) {
438  default:
439  llvm_unreachable("Unknown type!");
440  case Type::IntegerTyID:
441  return cmpNumbers(cast<IntegerType>(TyL)->getBitWidth(),
442  cast<IntegerType>(TyR)->getBitWidth());
443  // TyL == TyR would have returned true earlier, because types are uniqued.
444  case Type::VoidTyID:
445  case Type::FloatTyID:
446  case Type::DoubleTyID:
447  case Type::X86_FP80TyID:
448  case Type::FP128TyID:
449  case Type::PPC_FP128TyID:
450  case Type::LabelTyID:
451  case Type::MetadataTyID:
452  case Type::TokenTyID:
453  return 0;
454 
455  case Type::PointerTyID:
456  assert(PTyL && PTyR && "Both types must be pointers here.");
457  return cmpNumbers(PTyL->getAddressSpace(), PTyR->getAddressSpace());
458 
459  case Type::StructTyID: {
460  StructType *STyL = cast<StructType>(TyL);
461  StructType *STyR = cast<StructType>(TyR);
462  if (STyL->getNumElements() != STyR->getNumElements())
463  return cmpNumbers(STyL->getNumElements(), STyR->getNumElements());
464 
465  if (STyL->isPacked() != STyR->isPacked())
466  return cmpNumbers(STyL->isPacked(), STyR->isPacked());
467 
468  for (unsigned i = 0, e = STyL->getNumElements(); i != e; ++i) {
469  if (int Res = cmpTypes(STyL->getElementType(i), STyR->getElementType(i)))
470  return Res;
471  }
472  return 0;
473  }
474 
475  case Type::FunctionTyID: {
476  FunctionType *FTyL = cast<FunctionType>(TyL);
477  FunctionType *FTyR = cast<FunctionType>(TyR);
478  if (FTyL->getNumParams() != FTyR->getNumParams())
479  return cmpNumbers(FTyL->getNumParams(), FTyR->getNumParams());
480 
481  if (FTyL->isVarArg() != FTyR->isVarArg())
482  return cmpNumbers(FTyL->isVarArg(), FTyR->isVarArg());
483 
484  if (int Res = cmpTypes(FTyL->getReturnType(), FTyR->getReturnType()))
485  return Res;
486 
487  for (unsigned i = 0, e = FTyL->getNumParams(); i != e; ++i) {
488  if (int Res = cmpTypes(FTyL->getParamType(i), FTyR->getParamType(i)))
489  return Res;
490  }
491  return 0;
492  }
493 
494  case Type::ArrayTyID: {
495  auto *STyL = cast<ArrayType>(TyL);
496  auto *STyR = cast<ArrayType>(TyR);
497  if (STyL->getNumElements() != STyR->getNumElements())
498  return cmpNumbers(STyL->getNumElements(), STyR->getNumElements());
499  return cmpTypes(STyL->getElementType(), STyR->getElementType());
500  }
503  auto *STyL = cast<VectorType>(TyL);
504  auto *STyR = cast<VectorType>(TyR);
505  if (STyL->getElementCount().isScalable() !=
506  STyR->getElementCount().isScalable())
507  return cmpNumbers(STyL->getElementCount().isScalable(),
508  STyR->getElementCount().isScalable());
509  if (STyL->getElementCount() != STyR->getElementCount())
510  return cmpNumbers(STyL->getElementCount().getKnownMinValue(),
511  STyR->getElementCount().getKnownMinValue());
512  return cmpTypes(STyL->getElementType(), STyR->getElementType());
513  }
514  }
515 }
516 
517 // Determine whether the two operations are the same except that pointer-to-A
518 // and pointer-to-B are equivalent. This should be kept in sync with
519 // Instruction::isSameOperationAs.
520 // Read method declaration comments for more details.
522  const Instruction *R,
523  bool &needToCmpOperands) const {
524  needToCmpOperands = true;
525  if (int Res = cmpValues(L, R))
526  return Res;
527 
528  // Differences from Instruction::isSameOperationAs:
529  // * replace type comparison with calls to cmpTypes.
530  // * we test for I->getRawSubclassOptionalData (nuw/nsw/tail) at the top.
531  // * because of the above, we don't test for the tail bit on calls later on.
532  if (int Res = cmpNumbers(L->getOpcode(), R->getOpcode()))
533  return Res;
534 
535  if (const GetElementPtrInst *GEPL = dyn_cast<GetElementPtrInst>(L)) {
536  needToCmpOperands = false;
537  const GetElementPtrInst *GEPR = cast<GetElementPtrInst>(R);
538  if (int Res =
539  cmpValues(GEPL->getPointerOperand(), GEPR->getPointerOperand()))
540  return Res;
541  return cmpGEPs(GEPL, GEPR);
542  }
543 
544  if (int Res = cmpNumbers(L->getNumOperands(), R->getNumOperands()))
545  return Res;
546 
547  if (int Res = cmpTypes(L->getType(), R->getType()))
548  return Res;
549 
550  if (int Res = cmpNumbers(L->getRawSubclassOptionalData(),
551  R->getRawSubclassOptionalData()))
552  return Res;
553 
554  // We have two instructions of identical opcode and #operands. Check to see
555  // if all operands are the same type
556  for (unsigned i = 0, e = L->getNumOperands(); i != e; ++i) {
557  if (int Res =
558  cmpTypes(L->getOperand(i)->getType(), R->getOperand(i)->getType()))
559  return Res;
560  }
561 
562  // Check special state that is a part of some instructions.
563  if (const AllocaInst *AI = dyn_cast<AllocaInst>(L)) {
564  if (int Res = cmpTypes(AI->getAllocatedType(),
565  cast<AllocaInst>(R)->getAllocatedType()))
566  return Res;
567  return cmpAligns(AI->getAlign(), cast<AllocaInst>(R)->getAlign());
568  }
569  if (const LoadInst *LI = dyn_cast<LoadInst>(L)) {
570  if (int Res = cmpNumbers(LI->isVolatile(), cast<LoadInst>(R)->isVolatile()))
571  return Res;
572  if (int Res = cmpAligns(LI->getAlign(), cast<LoadInst>(R)->getAlign()))
573  return Res;
574  if (int Res =
575  cmpOrderings(LI->getOrdering(), cast<LoadInst>(R)->getOrdering()))
576  return Res;
577  if (int Res = cmpNumbers(LI->getSyncScopeID(),
578  cast<LoadInst>(R)->getSyncScopeID()))
579  return Res;
580  return cmpRangeMetadata(
581  LI->getMetadata(LLVMContext::MD_range),
582  cast<LoadInst>(R)->getMetadata(LLVMContext::MD_range));
583  }
584  if (const StoreInst *SI = dyn_cast<StoreInst>(L)) {
585  if (int Res =
586  cmpNumbers(SI->isVolatile(), cast<StoreInst>(R)->isVolatile()))
587  return Res;
588  if (int Res = cmpAligns(SI->getAlign(), cast<StoreInst>(R)->getAlign()))
589  return Res;
590  if (int Res =
591  cmpOrderings(SI->getOrdering(), cast<StoreInst>(R)->getOrdering()))
592  return Res;
593  return cmpNumbers(SI->getSyncScopeID(),
594  cast<StoreInst>(R)->getSyncScopeID());
595  }
596  if (const CmpInst *CI = dyn_cast<CmpInst>(L))
597  return cmpNumbers(CI->getPredicate(), cast<CmpInst>(R)->getPredicate());
598  if (auto *CBL = dyn_cast<CallBase>(L)) {
599  auto *CBR = cast<CallBase>(R);
600  if (int Res = cmpNumbers(CBL->getCallingConv(), CBR->getCallingConv()))
601  return Res;
602  if (int Res = cmpAttrs(CBL->getAttributes(), CBR->getAttributes()))
603  return Res;
604  if (int Res = cmpOperandBundlesSchema(*CBL, *CBR))
605  return Res;
606  if (const CallInst *CI = dyn_cast<CallInst>(L))
607  if (int Res = cmpNumbers(CI->getTailCallKind(),
608  cast<CallInst>(R)->getTailCallKind()))
609  return Res;
610  return cmpRangeMetadata(L->getMetadata(LLVMContext::MD_range),
611  R->getMetadata(LLVMContext::MD_range));
612  }
613  if (const InsertValueInst *IVI = dyn_cast<InsertValueInst>(L)) {
614  ArrayRef<unsigned> LIndices = IVI->getIndices();
615  ArrayRef<unsigned> RIndices = cast<InsertValueInst>(R)->getIndices();
616  if (int Res = cmpNumbers(LIndices.size(), RIndices.size()))
617  return Res;
618  for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
619  if (int Res = cmpNumbers(LIndices[i], RIndices[i]))
620  return Res;
621  }
622  return 0;
623  }
624  if (const ExtractValueInst *EVI = dyn_cast<ExtractValueInst>(L)) {
625  ArrayRef<unsigned> LIndices = EVI->getIndices();
626  ArrayRef<unsigned> RIndices = cast<ExtractValueInst>(R)->getIndices();
627  if (int Res = cmpNumbers(LIndices.size(), RIndices.size()))
628  return Res;
629  for (size_t i = 0, e = LIndices.size(); i != e; ++i) {
630  if (int Res = cmpNumbers(LIndices[i], RIndices[i]))
631  return Res;
632  }
633  }
634  if (const FenceInst *FI = dyn_cast<FenceInst>(L)) {
635  if (int Res =
636  cmpOrderings(FI->getOrdering(), cast<FenceInst>(R)->getOrdering()))
637  return Res;
638  return cmpNumbers(FI->getSyncScopeID(),
639  cast<FenceInst>(R)->getSyncScopeID());
640  }
641  if (const AtomicCmpXchgInst *CXI = dyn_cast<AtomicCmpXchgInst>(L)) {
642  if (int Res = cmpNumbers(CXI->isVolatile(),
643  cast<AtomicCmpXchgInst>(R)->isVolatile()))
644  return Res;
645  if (int Res =
646  cmpNumbers(CXI->isWeak(), cast<AtomicCmpXchgInst>(R)->isWeak()))
647  return Res;
648  if (int Res =
649  cmpOrderings(CXI->getSuccessOrdering(),
650  cast<AtomicCmpXchgInst>(R)->getSuccessOrdering()))
651  return Res;
652  if (int Res =
653  cmpOrderings(CXI->getFailureOrdering(),
654  cast<AtomicCmpXchgInst>(R)->getFailureOrdering()))
655  return Res;
656  return cmpNumbers(CXI->getSyncScopeID(),
657  cast<AtomicCmpXchgInst>(R)->getSyncScopeID());
658  }
659  if (const AtomicRMWInst *RMWI = dyn_cast<AtomicRMWInst>(L)) {
660  if (int Res = cmpNumbers(RMWI->getOperation(),
661  cast<AtomicRMWInst>(R)->getOperation()))
662  return Res;
663  if (int Res = cmpNumbers(RMWI->isVolatile(),
664  cast<AtomicRMWInst>(R)->isVolatile()))
665  return Res;
666  if (int Res = cmpOrderings(RMWI->getOrdering(),
667  cast<AtomicRMWInst>(R)->getOrdering()))
668  return Res;
669  return cmpNumbers(RMWI->getSyncScopeID(),
670  cast<AtomicRMWInst>(R)->getSyncScopeID());
671  }
672  if (const ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(L)) {
673  ArrayRef<int> LMask = SVI->getShuffleMask();
674  ArrayRef<int> RMask = cast<ShuffleVectorInst>(R)->getShuffleMask();
675  if (int Res = cmpNumbers(LMask.size(), RMask.size()))
676  return Res;
677  for (size_t i = 0, e = LMask.size(); i != e; ++i) {
678  if (int Res = cmpNumbers(LMask[i], RMask[i]))
679  return Res;
680  }
681  }
682  if (const PHINode *PNL = dyn_cast<PHINode>(L)) {
683  const PHINode *PNR = cast<PHINode>(R);
684  // Ensure that in addition to the incoming values being identical
685  // (checked by the caller of this function), the incoming blocks
686  // are also identical.
687  for (unsigned i = 0, e = PNL->getNumIncomingValues(); i != e; ++i) {
688  if (int Res =
689  cmpValues(PNL->getIncomingBlock(i), PNR->getIncomingBlock(i)))
690  return Res;
691  }
692  }
693  return 0;
694 }
695 
696 // Determine whether two GEP operations perform the same underlying arithmetic.
697 // Read method declaration comments for more details.
698 int FunctionComparator::cmpGEPs(const GEPOperator *GEPL,
699  const GEPOperator *GEPR) const {
700  unsigned int ASL = GEPL->getPointerAddressSpace();
701  unsigned int ASR = GEPR->getPointerAddressSpace();
702 
703  if (int Res = cmpNumbers(ASL, ASR))
704  return Res;
705 
706  // When we have target data, we can reduce the GEP down to the value in bytes
707  // added to the address.
708  const DataLayout &DL = FnL->getParent()->getDataLayout();
709  unsigned BitWidth = DL.getPointerSizeInBits(ASL);
710  APInt OffsetL(BitWidth, 0), OffsetR(BitWidth, 0);
711  if (GEPL->accumulateConstantOffset(DL, OffsetL) &&
712  GEPR->accumulateConstantOffset(DL, OffsetR))
713  return cmpAPInts(OffsetL, OffsetR);
714  if (int Res =
716  return Res;
717 
718  if (int Res = cmpNumbers(GEPL->getNumOperands(), GEPR->getNumOperands()))
719  return Res;
720 
721  for (unsigned i = 0, e = GEPL->getNumOperands(); i != e; ++i) {
722  if (int Res = cmpValues(GEPL->getOperand(i), GEPR->getOperand(i)))
723  return Res;
724  }
725 
726  return 0;
727 }
728 
729 int FunctionComparator::cmpInlineAsm(const InlineAsm *L,
730  const InlineAsm *R) const {
731  // InlineAsm's are uniqued. If they are the same pointer, obviously they are
732  // the same, otherwise compare the fields.
733  if (L == R)
734  return 0;
735  if (int Res = cmpTypes(L->getFunctionType(), R->getFunctionType()))
736  return Res;
737  if (int Res = cmpMem(L->getAsmString(), R->getAsmString()))
738  return Res;
739  if (int Res = cmpMem(L->getConstraintString(), R->getConstraintString()))
740  return Res;
741  if (int Res = cmpNumbers(L->hasSideEffects(), R->hasSideEffects()))
742  return Res;
743  if (int Res = cmpNumbers(L->isAlignStack(), R->isAlignStack()))
744  return Res;
745  if (int Res = cmpNumbers(L->getDialect(), R->getDialect()))
746  return Res;
747  assert(L->getFunctionType() != R->getFunctionType());
748  return 0;
749 }
750 
751 /// Compare two values used by the two functions under pair-wise comparison. If
752 /// this is the first time the values are seen, they're added to the mapping so
753 /// that we will detect mismatches on next use.
754 /// See comments in declaration for more details.
755 int FunctionComparator::cmpValues(const Value *L, const Value *R) const {
756  // Catch self-reference case.
757  if (L == FnL) {
758  if (R == FnR)
759  return 0;
760  return -1;
761  }
762  if (R == FnR) {
763  if (L == FnL)
764  return 0;
765  return 1;
766  }
767 
768  const Constant *ConstL = dyn_cast<Constant>(L);
769  const Constant *ConstR = dyn_cast<Constant>(R);
770  if (ConstL && ConstR) {
771  if (L == R)
772  return 0;
773  return cmpConstants(ConstL, ConstR);
774  }
775 
776  if (ConstL)
777  return 1;
778  if (ConstR)
779  return -1;
780 
781  const InlineAsm *InlineAsmL = dyn_cast<InlineAsm>(L);
782  const InlineAsm *InlineAsmR = dyn_cast<InlineAsm>(R);
783 
784  if (InlineAsmL && InlineAsmR)
785  return cmpInlineAsm(InlineAsmL, InlineAsmR);
786  if (InlineAsmL)
787  return 1;
788  if (InlineAsmR)
789  return -1;
790 
791  auto LeftSN = sn_mapL.insert(std::make_pair(L, sn_mapL.size())),
792  RightSN = sn_mapR.insert(std::make_pair(R, sn_mapR.size()));
793 
794  return cmpNumbers(LeftSN.first->second, RightSN.first->second);
795 }
796 
797 // Test whether two basic blocks have equivalent behaviour.
799  const BasicBlock *BBR) const {
800  BasicBlock::const_iterator InstL = BBL->begin(), InstLE = BBL->end();
801  BasicBlock::const_iterator InstR = BBR->begin(), InstRE = BBR->end();
802 
803  do {
804  bool needToCmpOperands = true;
805  if (int Res = cmpOperations(&*InstL, &*InstR, needToCmpOperands))
806  return Res;
807  if (needToCmpOperands) {
808  assert(InstL->getNumOperands() == InstR->getNumOperands());
809 
810  for (unsigned i = 0, e = InstL->getNumOperands(); i != e; ++i) {
811  Value *OpL = InstL->getOperand(i);
812  Value *OpR = InstR->getOperand(i);
813  if (int Res = cmpValues(OpL, OpR))
814  return Res;
815  // cmpValues should ensure this is true.
816  assert(cmpTypes(OpL->getType(), OpR->getType()) == 0);
817  }
818  }
819 
820  ++InstL;
821  ++InstR;
822  } while (InstL != InstLE && InstR != InstRE);
823 
824  if (InstL != InstLE && InstR == InstRE)
825  return 1;
826  if (InstL == InstLE && InstR != InstRE)
827  return -1;
828  return 0;
829 }
830 
832  if (int Res = cmpAttrs(FnL->getAttributes(), FnR->getAttributes()))
833  return Res;
834 
835  if (int Res = cmpNumbers(FnL->hasGC(), FnR->hasGC()))
836  return Res;
837 
838  if (FnL->hasGC()) {
839  if (int Res = cmpMem(FnL->getGC(), FnR->getGC()))
840  return Res;
841  }
842 
843  if (int Res = cmpNumbers(FnL->hasSection(), FnR->hasSection()))
844  return Res;
845 
846  if (FnL->hasSection()) {
847  if (int Res = cmpMem(FnL->getSection(), FnR->getSection()))
848  return Res;
849  }
850 
851  if (int Res = cmpNumbers(FnL->isVarArg(), FnR->isVarArg()))
852  return Res;
853 
854  // TODO: if it's internal and only used in direct calls, we could handle this
855  // case too.
856  if (int Res = cmpNumbers(FnL->getCallingConv(), FnR->getCallingConv()))
857  return Res;
858 
859  if (int Res = cmpTypes(FnL->getFunctionType(), FnR->getFunctionType()))
860  return Res;
861 
862  assert(FnL->arg_size() == FnR->arg_size() &&
863  "Identically typed functions have different numbers of args!");
864 
865  // Visit the arguments so that they get enumerated in the order they're
866  // passed in.
868  ArgRI = FnR->arg_begin(),
869  ArgLE = FnL->arg_end();
870  ArgLI != ArgLE; ++ArgLI, ++ArgRI) {
871  if (cmpValues(&*ArgLI, &*ArgRI) != 0)
872  llvm_unreachable("Arguments repeat!");
873  }
874  return 0;
875 }
876 
877 // Test whether the two functions have equivalent behaviour.
879  beginCompare();
880 
881  if (int Res = compareSignature())
882  return Res;
883 
884  // We do a CFG-ordered walk since the actual ordering of the blocks in the
885  // linked list is immaterial. Our walk starts at the entry block for both
886  // functions, then takes each block from each terminator in order. As an
887  // artifact, this also means that unreachable blocks are ignored.
888  SmallVector<const BasicBlock *, 8> FnLBBs, FnRBBs;
889  SmallPtrSet<const BasicBlock *, 32> VisitedBBs; // in terms of F1.
890 
891  FnLBBs.push_back(&FnL->getEntryBlock());
892  FnRBBs.push_back(&FnR->getEntryBlock());
893 
894  VisitedBBs.insert(FnLBBs[0]);
895  while (!FnLBBs.empty()) {
896  const BasicBlock *BBL = FnLBBs.pop_back_val();
897  const BasicBlock *BBR = FnRBBs.pop_back_val();
898 
899  if (int Res = cmpValues(BBL, BBR))
900  return Res;
901 
902  if (int Res = cmpBasicBlocks(BBL, BBR))
903  return Res;
904 
905  const Instruction *TermL = BBL->getTerminator();
906  const Instruction *TermR = BBR->getTerminator();
907 
908  assert(TermL->getNumSuccessors() == TermR->getNumSuccessors());
909  for (unsigned i = 0, e = TermL->getNumSuccessors(); i != e; ++i) {
910  if (!VisitedBBs.insert(TermL->getSuccessor(i)).second)
911  continue;
912 
913  FnLBBs.push_back(TermL->getSuccessor(i));
914  FnRBBs.push_back(TermR->getSuccessor(i));
915  }
916  }
917  return 0;
918 }
919 
920 namespace {
921 
922 // Accumulate the hash of a sequence of 64-bit integers. This is similar to a
923 // hash of a sequence of 64bit ints, but the entire input does not need to be
924 // available at once. This interface is necessary for functionHash because it
925 // needs to accumulate the hash as the structure of the function is traversed
926 // without saving these values to an intermediate buffer. This form of hashing
927 // is not often needed, as usually the object to hash is just read from a
928 // buffer.
929 class HashAccumulator64 {
930  uint64_t Hash;
931 
932 public:
933  // Initialize to random constant, so the state isn't zero.
934  HashAccumulator64() { Hash = 0x6acaa36bef8325c5ULL; }
935 
936  void add(uint64_t V) { Hash = hashing::detail::hash_16_bytes(Hash, V); }
937 
938  // No finishing is required, because the entire hash value is used.
939  uint64_t getHash() { return Hash; }
940 };
941 
942 } // end anonymous namespace
943 
944 // A function hash is calculated by considering only the number of arguments and
945 // whether a function is varargs, the order of basic blocks (given by the
946 // successors of each basic block in depth first order), and the order of
947 // opcodes of each instruction within each of these basic blocks. This mirrors
948 // the strategy compare() uses to compare functions by walking the BBs in depth
949 // first order and comparing each instruction in sequence. Because this hash
950 // does not look at the operands, it is insensitive to things such as the
951 // target of calls and the constants used in the function, which makes it useful
952 // when possibly merging functions which are the same modulo constants and call
953 // targets.
955  HashAccumulator64 H;
956  H.add(F.isVarArg());
957  H.add(F.arg_size());
958 
961 
962  // Walk the blocks in the same order as FunctionComparator::cmpBasicBlocks(),
963  // accumulating the hash of the function "structure." (BB and opcode sequence)
964  BBs.push_back(&F.getEntryBlock());
965  VisitedBBs.insert(BBs[0]);
966  while (!BBs.empty()) {
967  const BasicBlock *BB = BBs.pop_back_val();
968  // This random value acts as a block header, as otherwise the partition of
969  // opcodes into BBs wouldn't affect the hash, only the order of the opcodes
970  H.add(45798);
971  for (auto &Inst : *BB) {
972  H.add(Inst.getOpcode());
973  }
974  const Instruction *Term = BB->getTerminator();
975  for (unsigned i = 0, e = Term->getNumSuccessors(); i != e; ++i) {
976  if (!VisitedBBs.insert(Term->getSuccessor(i)).second)
977  continue;
978  BBs.push_back(Term->getSuccessor(i));
979  }
980  }
981  return H.getHash();
982 }
i
i
Definition: README.txt:29
llvm::CallBase::getNumOperandBundles
unsigned getNumOperandBundles() const
Return the number of operand bundles associated with this User.
Definition: InstrTypes.h:1940
llvm::Type::ArrayTyID
@ ArrayTyID
Arrays.
Definition: Type.h:75
llvm::Argument
This class represents an incoming formal argument to a Function.
Definition: Argument.h:28
llvm::BasicBlock::end
iterator end()
Definition: BasicBlock.h:299
llvm::Type::FloatTyID
@ FloatTyID
32-bit floating point type
Definition: Type.h:58
llvm::APFloatBase::semanticsSizeInBits
static unsigned int semanticsSizeInBits(const fltSemantics &)
Definition: APFloat.cpp:222
llvm::Type::DoubleTyID
@ DoubleTyID
64-bit floating point type
Definition: Type.h:59
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::FunctionComparator::cmpValues
int cmpValues(const Value *L, const Value *R) const
Assign or look up previously assigned numbers for the two values, and return whether the numbers are ...
Definition: FunctionComparator.cpp:755
llvm::DataLayout
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:113
Metadata.h
llvm::FunctionComparator::cmpBasicBlocks
int cmpBasicBlocks(const BasicBlock *BBL, const BasicBlock *BBR) const
Test whether two basic blocks have equivalent behaviour.
Definition: FunctionComparator.cpp:798
llvm::InlineAsm::getAsmString
const std::string & getAsmString() const
Definition: InlineAsm.h:83
llvm::Function
Definition: Function.h:60
llvm::Attribute
Definition: Attributes.h:52
llvm::Type::VoidTyID
@ VoidTyID
type with no size
Definition: Type.h:63
llvm::InlineAsm::isAlignStack
bool isAlignStack() const
Definition: InlineAsm.h:69
llvm::GlobalObject::getSection
StringRef getSection() const
Get the custom section of this global if it has one.
Definition: GlobalObject.h:111
llvm::Attribute::isTypeAttribute
bool isTypeAttribute() const
Return true if the attribute is a type attribute.
Definition: Attributes.cpp:273
llvm::ConstantInt::getValue
const APInt & getValue() const
Return the constant as an APInt value reference.
Definition: Constants.h:133
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
InlineAsm.h
llvm::FunctionComparator::compareSignature
int compareSignature() const
Compares the signature and other general attributes of the two functions.
Definition: FunctionComparator.cpp:831
ErrorHandling.h
llvm::Function::getEntryBlock
const BasicBlock & getEntryBlock() const
Definition: Function.h:709
llvm::PointerType::getAddressSpace
unsigned getAddressSpace() const
Return the address space of the Pointer type.
Definition: DerivedTypes.h:682
llvm::BlockAddress::getBasicBlock
BasicBlock * getBasicBlock() const
Definition: Constants.h:877
llvm::Type::getTypeID
TypeID getTypeID() const
Return the type id for the type.
Definition: Type.h:136
FunctionComparator.h
APInt.h
llvm::Function::arg_size
size_t arg_size() const
Definition: Function.h:773
llvm::Type
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
llvm::APInt::getBitWidth
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1423
Module.h
llvm::AttributeList
Definition: Attributes.h:408
llvm::FunctionComparator::beginCompare
void beginCompare()
Start the comparison.
Definition: FunctionComparator.h:109
llvm::APInt::ugt
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition: APInt.h:1132
llvm::FenceInst
An instruction for ordering other memory operations.
Definition: Instructions.h:445
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
llvm::InlineAsm::getFunctionType
FunctionType * getFunctionType() const
getFunctionType - InlineAsm's are always pointers to functions.
Definition: InlineAsm.cpp:56
Operator.h
Hashing.h
getBitWidth
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
Definition: ValueTracking.cpp:98
llvm::FunctionType::getNumParams
unsigned getNumParams() const
Return the number of fixed parameters this function type requires.
Definition: DerivedTypes.h:139
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:654
llvm::FunctionComparator::FnR
const Function * FnR
Definition: FunctionComparator.h:329
llvm::APFloat::getSemantics
const fltSemantics & getSemantics() const
Definition: APFloat.h:1222
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::RISCVFenceField::R
@ R
Definition: RISCVBaseInfo.h:240
llvm::FunctionComparator::cmpConstants
int cmpConstants(const Constant *L, const Constant *R) const
Constants comparison.
Definition: FunctionComparator.cpp:214
llvm::FunctionType::isVarArg
bool isVarArg() const
Definition: DerivedTypes.h:123
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
llvm::MDNode::getNumOperands
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1199
llvm::FunctionComparator::functionHash
static FunctionHash functionHash(Function &)
Definition: FunctionComparator.cpp:954
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
Instruction.h
llvm::ConstantInt
This is the shared class of boolean and integer constants.
Definition: Constants.h:79
llvm::Instruction::getNumSuccessors
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Definition: Instruction.cpp:777
llvm::Instruction::getOpcode
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:157
llvm::Type::MetadataTyID
@ MetadataTyID
Metadata.
Definition: Type.h:65
GlobalValue.h
llvm::Type::FunctionTyID
@ FunctionTyID
Functions.
Definition: Type.h:72
Constants.h
llvm::Constant::isNullValue
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
Definition: Constants.cpp:76
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::FunctionComparator::cmpMem
int cmpMem(StringRef L, StringRef R) const
Definition: FunctionComparator.cpp:106
llvm::InlineAsm::hasSideEffects
bool hasSideEffects() const
Definition: InlineAsm.h:68
llvm::StructType::isPacked
bool isPacked() const
Definition: DerivedTypes.h:273
InstrTypes.h
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
llvm::Function::arg_end
arg_iterator arg_end()
Definition: Function.h:749
llvm::Value::getValueID
unsigned getValueID() const
Return an ID for the concrete type of this object.
Definition: Value.h:532
llvm::ConstantArray
ConstantArray - Constant Array Declarations.
Definition: Constants.h:409
llvm::Instruction
Definition: Instruction.h:42
llvm::AttributeList::getAttributes
AttributeSet getAttributes(unsigned Index) const
The attributes for the specified index are returned.
Definition: Attributes.cpp:1470
APFloat.h
llvm::AArch64CC::LE
@ LE
Definition: AArch64BaseInfo.h:268
llvm::FunctionComparator::cmpAPInts
int cmpAPInts(const APInt &L, const APInt &R) const
Definition: FunctionComparator.cpp:77
llvm::FunctionComparator::FnL
const Function * FnL
Definition: FunctionComparator.h:329
SmallPtrSet.h
llvm::Instruction::getSuccessor
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
Definition: Instruction.cpp:789
llvm::Type::PointerTyID
@ PointerTyID
Pointers.
Definition: Type.h:73
llvm::hashing::detail::hash_16_bytes
uint64_t hash_16_bytes(uint64_t low, uint64_t high)
Definition: Hashing.h:183
llvm::APFloat::bitcastToAPInt
APInt bitcastToAPInt() const
Definition: APFloat.h:1129
llvm::InlineAsm::getDialect
AsmDialect getDialect() const
Definition: InlineAsm.h:70
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
Type.h
llvm::Instruction::getMetadata
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
Definition: Instruction.h:279
llvm::Function::getAttributes
AttributeList getAttributes() const
Return the attribute list for this Function.
Definition: Function.h:314
llvm::CmpInst
This class is the base class for the comparison instructions.
Definition: InstrTypes.h:709
llvm::Function::getGC
const std::string & getGC() const
Definition: Function.cpp:686
llvm::AttributeSet::end
iterator end() const
Definition: Attributes.cpp:754
llvm::MDNode::getOperand
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1193
llvm::InlineAsm
Definition: InlineAsm.h:31
llvm::AtomicOrdering
AtomicOrdering
Atomic ordering for LLVM's memory model.
Definition: AtomicOrdering.h:56
BasicBlock.h
llvm::GlobalObject::hasSection
bool hasSection() const
Check if this global has a custom object file section.
Definition: GlobalObject.h:103
llvm::APFloat
Definition: APFloat.h:700
llvm::FunctionComparator::compare
int compare()
Test whether the two functions have equivalent behaviour.
Definition: FunctionComparator.cpp:878
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:305
llvm::GlobalValue
Definition: GlobalValue.h:44
llvm::Constant
This is an important base class in LLVM.
Definition: Constant.h:41
uint64_t
llvm::Function::getCallingConv
CallingConv::ID getCallingConv() const
getCallingConv()/setCallingConv(CC) - These method get and set the calling convention of this functio...
Definition: Function.h:238
llvm::GlobalValue::getParent
Module * getParent()
Get the module that this global value is contained inside of...
Definition: GlobalValue.h:577
llvm::Function::hasGC
bool hasGC() const
hasGC/getGC/setGC/clearGC - The name of the garbage collection algorithm to use during code generatio...
Definition: Function.h:306
llvm::ARM_AM::add
@ add
Definition: ARMAddressingModes.h:39
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::Attribute::getKindAsEnum
Attribute::AttrKind getKindAsEnum() const
Return the attribute's kind as an enum (Attribute::AttrKind).
Definition: Attributes.cpp:277
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::FunctionComparator::cmpAligns
int cmpAligns(Align L, Align R) const
Definition: FunctionComparator.cpp:61
llvm::FunctionType::getParamType
Type * getParamType(unsigned i) const
Parameter type accessors.
Definition: DerivedTypes.h:135
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:929
llvm::PointerType
Class to represent pointers.
Definition: DerivedTypes.h:632
ArrayRef.h
llvm::ConstantVector
Constant Vector Declarations.
Definition: Constants.h:493
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::FunctionComparator::cmpAPFloats
int cmpAPFloats(const APFloat &L, const APFloat &R) const
Definition: FunctionComparator.cpp:87
llvm::MDNode
Metadata node.
Definition: Metadata.h:926
RA
SI optimize exec mask operations pre RA
Definition: SIOptimizeExecMaskingPreRA.cpp:71
llvm::GEPOperator
Definition: Operator.h:375
llvm::ConstantStruct
Definition: Constants.h:441
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::Type::FP128TyID
@ FP128TyID
128-bit floating point type (112-bit significand)
Definition: Type.h:61
llvm::InlineAsm::getConstraintString
const std::string & getConstraintString() const
Definition: InlineAsm.h:84
llvm::GlobalNumberState::getNumber
uint64_t getNumber(GlobalValue *Global)
Definition: FunctionComparator.h:71
llvm::BlockAddress
The address of a basic block.
Definition: Constants.h:848
llvm::ArrayRef< unsigned >
DataLayout.h
llvm::StructType
Class to represent struct types.
Definition: DerivedTypes.h:213
llvm::Type::PPC_FP128TyID
@ PPC_FP128TyID
128-bit floating point type (two 64-bits, PowerPC)
Definition: Type.h:62
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::CallBase::getOperandBundleAt
OperandBundleUse getOperandBundleAt(unsigned Index) const
Return the operand bundle at a specific index.
Definition: InstrTypes.h:1996
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
Compiler.h
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::FunctionComparator::cmpOperations
int cmpOperations(const Instruction *L, const Instruction *R, bool &needToCmpOperands) const
Compare two Instructions for equivalence, similar to Instruction::isSameOperationAs.
Definition: FunctionComparator.cpp:521
llvm::Value::getRawSubclassOptionalData
unsigned getRawSubclassOptionalData() const
Return the raw optional flags value contained in this value.
Definition: Value.h:539
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:176
llvm::StructType::getNumElements
unsigned getNumElements() const
Random access to the elements.
Definition: DerivedTypes.h:327
llvm::AtomicRMWInst
an instruction that atomically reads a memory location, combines it with another value,...
Definition: Instructions.h:727
llvm::Type::IntegerTyID
@ IntegerTyID
Arbitrary bit width integers.
Definition: Type.h:71
llvm::GEPOperator::getPointerAddressSpace
unsigned getPointerAddressSpace() const
Method to return the address space of the pointer operand.
Definition: Operator.h:435
Attributes.h
llvm::StringRef::size
constexpr LLVM_NODISCARD size_t size() const
size - Get the string size.
Definition: StringRef.h:157
llvm::AArch64_AM::ASR
@ ASR
Definition: AArch64AddressingModes.h:37
llvm::BlockAddress::getFunction
Function * getFunction() const
Definition: Constants.h:876
Constant.h
llvm::ConstantExpr
A constant value that is initialized with an expression using other constant values.
Definition: Constants.h:971
H
#define H(x, y, z)
Definition: MD5.cpp:57
llvm::M68kBeads::Term
@ Term
Definition: M68kBaseInfo.h:71
llvm::FunctionComparator::cmpTypes
int cmpTypes(Type *TyL, Type *TyR) const
cmpType - compares two types, defines total ordering among the types set.
Definition: FunctionComparator.cpp:421
llvm::Align::value
uint64_t value() const
This is a hole in the type system and should not be abused.
Definition: Alignment.h:85
llvm::Type::FixedVectorTyID
@ FixedVectorTyID
Fixed width SIMD vector type.
Definition: Type.h:76
llvm::ExtractValueInst
This instruction extracts a struct member or array element value from an aggregate value.
Definition: Instructions.h:2411
llvm::GEPOperator::accumulateConstantOffset
bool accumulateConstantOffset(const DataLayout &DL, APInt &Offset, function_ref< bool(Value &, APInt &)> ExternalAnalysis=nullptr) const
Accumulate the constant address offset of this GEP if possible.
Definition: Operator.cpp:86
llvm::AArch64CC::LS
@ LS
Definition: AArch64BaseInfo.h:264
Casting.h
llvm::Attribute::getValueAsType
Type * getValueAsType() const
Return the attribute's value as a Type.
Definition: Attributes.cpp:312
llvm::fltSemantics
Definition: APFloat.cpp:54
Function.h
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::Type::TokenTyID
@ TokenTyID
Tokens.
Definition: Type.h:68
llvm::AttributeList::getNumAttrSets
unsigned getNumAttrSets() const
Definition: Attributes.cpp:1497
llvm::AttributeSet::begin
iterator begin() const
Definition: Attributes.cpp:750
llvm::Function::getFunctionType
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:175
llvm::Function::arg_begin
arg_iterator arg_begin()
Definition: Function.h:740
llvm::Type::LabelTyID
@ LabelTyID
Labels.
Definition: Type.h:64
llvm::Function::isVarArg
bool isVarArg() const
isVarArg - Return true if this function takes a variable number of arguments.
Definition: Function.h:188
llvm::Type::StructTyID
@ StructTyID
Structures.
Definition: Type.h:74
llvm::ShuffleVectorInst
This instruction constructs a fixed permutation of two input vectors.
Definition: Instructions.h:2008
Instructions.h
llvm::GEPOperator::getSourceElementType
Type * getSourceElementType() const
Definition: Operator.cpp:47
llvm::User::getNumOperands
unsigned getNumOperands() const
Definition: User.h:191
llvm::AttributeSet
Definition: Attributes.h:274
llvm::FunctionComparator::cmpNumbers
int cmpNumbers(uint64_t L, uint64_t R) const
Definition: FunctionComparator.cpp:53
SmallVector.h
llvm::APFloatBase::semanticsPrecision
static unsigned int semanticsPrecision(const fltSemantics &)
Definition: APFloat.cpp:211
llvm::PHINode::getIncomingBlock
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Definition: Instructions.h:2780
llvm::ArrayRef::size
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:164
llvm::AttributeList::indexes
index_iterator indexes() const
Use this to iterate over the valid attribute indexes.
Definition: Attributes.h:895
llvm::PHINode
Definition: Instructions.h:2664
llvm::BasicBlock::getTerminator
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:119
llvm::StructType::getElementType
Type * getElementType(unsigned N) const
Definition: DerivedTypes.h:328
llvm::CallBase
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
Definition: InstrTypes.h:1174
llvm::Type::ScalableVectorTyID
@ ScalableVectorTyID
Scalable SIMD vector type.
Definition: Type.h:77
llvm::Module::getDataLayout
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
DerivedTypes.h
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1474
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
LLVMContext.h
llvm::AllocaInst
an instruction to allocate memory on the stack
Definition: Instructions.h:58
llvm::User::getOperand
Value * getOperand(unsigned i) const
Definition: User.h:169
raw_ostream.h
llvm::InsertValueInst
This instruction inserts a struct field of array element value into an aggregate value.
Definition: Instructions.h:2522
Value.h
llvm::GetElementPtrInst::getPointerOperand
Value * getPointerOperand()
Definition: Instructions.h:1052
llvm::FunctionType::getReturnType
Type * getReturnType() const
Definition: DerivedTypes.h:124
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::AtomicCmpXchgInst
An instruction that atomically checks whether a specified value is in a memory location,...
Definition: Instructions.h:522
llvm::FunctionComparator::cmpGlobalValues
int cmpGlobalValues(GlobalValue *L, GlobalValue *R) const
Compares two global values by number.
Definition: FunctionComparator.cpp:412
llvm::StringRef::compare
LLVM_NODISCARD int compare(StringRef RHS) const
compare - Compare two strings; the result is -1, 0, or 1 if this string is lexicographically less tha...
Definition: StringRef.h:201
Debug.h
llvm::Type::X86_FP80TyID
@ X86_FP80TyID
80-bit floating point type (X87)
Definition: Type.h:60
llvm::APFloatBase::semanticsMaxExponent
static ExponentType semanticsMaxExponent(const fltSemantics &)
Definition: APFloat.cpp:215
llvm::BasicBlock::const_iterator
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:88
llvm::Type::isFirstClassType
bool isFirstClassType() const
Return true if the type is "first class", meaning it is a valid type for a Value.
Definition: Type.h:243
llvm::FunctionType
Class to represent function types.
Definition: DerivedTypes.h:103
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365
llvm::APFloatBase::semanticsMinExponent
static ExponentType semanticsMinExponent(const fltSemantics &)
Definition: APFloat.cpp:219