Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Support/IntEqClasses.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===//
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
// Equivalence classes for small integers. This is a mapping of the integers
10
// 0 .. N-1 into M equivalence classes numbered 0 .. M-1.
11
//
12
// Initially each integer has its own equivalence class. Classes are joined by
13
// passing a representative member of each class to join().
14
//
15
// Once the classes are built, compress() will number them 0 .. M-1 and prevent
16
// further changes.
17
//
18
//===----------------------------------------------------------------------===//
19
20
#include "llvm/ADT/IntEqClasses.h"
21
22
using namespace llvm;
23
24
6.95M
void IntEqClasses::grow(unsigned N) {
25
6.95M
  assert(NumClasses == 0 && "grow() called after compress().");
26
6.95M
  EC.reserve(N);
27
17.8M
  while (EC.size() < N)
28
10.8M
    EC.push_back(EC.size());
29
6.95M
}
30
31
5.49M
unsigned IntEqClasses::join(unsigned a, unsigned b) {
32
5.49M
  assert(NumClasses == 0 && "join() called after compress().");
33
5.49M
  unsigned eca = EC[a];
34
5.49M
  unsigned ecb = EC[b];
35
5.49M
  // Update pointers while searching for the leaders, compressing the paths
36
5.49M
  // incrementally. The larger leader will eventually be updated, joining the
37
5.49M
  // classes.
38
10.9M
  while (eca != ecb)
39
5.44M
    if (eca < ecb) {
40
3.37M
      EC[b] = eca;
41
3.37M
      b = ecb;
42
3.37M
      ecb = EC[b];
43
3.37M
    } else {
44
2.07M
      EC[a] = ecb;
45
2.07M
      a = eca;
46
2.07M
      eca = EC[a];
47
2.07M
    }
48
5.49M
49
5.49M
  return eca;
50
5.49M
}
51
52
672
unsigned IntEqClasses::findLeader(unsigned a) const {
53
672
  assert(NumClasses == 0 && "findLeader() called after compress().");
54
918
  while (a != EC[a])
55
246
    a = EC[a];
56
672
  return a;
57
672
}
58
59
3.67M
void IntEqClasses::compress() {
60
3.67M
  if (NumClasses)
61
0
    return;
62
14.5M
  
for (unsigned i = 0, e = EC.size(); 3.67M
i != e;
++i10.8M
)
63
10.8M
    EC[i] = (EC[i] == i) ? 
NumClasses++5.70M
:
EC[EC[i]]5.18M
;
64
3.67M
}
65
66
1
void IntEqClasses::uncompress() {
67
1
  if (!NumClasses)
68
0
    return;
69
1
  SmallVector<unsigned, 8> Leader;
70
11
  for (unsigned i = 0, e = EC.size(); i != e; 
++i10
)
71
10
    if (EC[i] < Leader.size())
72
7
      EC[i] = Leader[EC[i]];
73
3
    else
74
3
      Leader.push_back(EC[i] = i);
75
1
  NumClasses = 0;
76
1
}