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