Coverage Report

Created: 2019-07-24 05:18

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