Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Support/IntEqClasses.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// Equivalence classes for small integers. This is a mapping of the integers
11
// 0 .. N-1 into M equivalence classes numbered 0 .. M-1.
12
//
13
// Initially each integer has its own equivalence class. Classes are joined by
14
// passing a representative member of each class to join().
15
//
16
// Once the classes are built, compress() will number them 0 .. M-1 and prevent
17
// further changes.
18
//
19
//===----------------------------------------------------------------------===//
20
21
#include "llvm/ADT/IntEqClasses.h"
22
23
using namespace llvm;
24
25
4.01M
void IntEqClasses::grow(unsigned N) {
26
4.01M
  assert(NumClasses == 0 && "grow() called after compress().");
27
4.01M
  EC.reserve(N);
28
15.2M
  while (EC.size() < N)
29
11.2M
    EC.push_back(EC.size());
30
4.01M
}
31
32
6.57M
unsigned IntEqClasses::join(unsigned a, unsigned b) {
33
6.57M
  assert(NumClasses == 0 && "join() called after compress().");
34
6.57M
  unsigned eca = EC[a];
35
6.57M
  unsigned ecb = EC[b];
36
6.57M
  // Update pointers while searching for the leaders, compressing the paths
37
6.57M
  // incrementally. The larger leader will eventually be updated, joining the
38
6.57M
  // classes.
39
13.1M
  while (eca != ecb)
40
6.53M
    
if (6.53M
eca < ecb6.53M
) {
41
4.18M
      EC[b] = eca;
42
4.18M
      b = ecb;
43
4.18M
      ecb = EC[b];
44
6.53M
    } else {
45
2.34M
      EC[a] = ecb;
46
2.34M
      a = eca;
47
2.34M
      eca = EC[a];
48
2.34M
    }
49
6.57M
50
6.57M
  return eca;
51
6.57M
}
52
53
491
unsigned IntEqClasses::findLeader(unsigned a) const {
54
491
  assert(NumClasses == 0 && "findLeader() called after compress().");
55
670
  while (a != EC[a])
56
179
    a = EC[a];
57
491
  return a;
58
491
}
59
60
2.25M
void IntEqClasses::compress() {
61
2.25M
  if (NumClasses)
62
0
    return;
63
13.4M
  
for (unsigned i = 0, e = EC.size(); 2.25M
i != e13.4M
;
++i11.2M
)
64
11.2M
    
EC[i] = (EC[i] == i) ? 11.2M
NumClasses++4.93M
:
EC[EC[i]]6.26M
;
65
2.25M
}
66
67
1
void IntEqClasses::uncompress() {
68
1
  if (!NumClasses)
69
0
    return;
70
1
  SmallVector<unsigned, 8> Leader;
71
11
  for (unsigned i = 0, e = EC.size(); 
i != e11
;
++i10
)
72
10
    
if (10
EC[i] < Leader.size()10
)
73
7
      EC[i] = Leader[EC[i]];
74
10
    else
75
3
      Leader.push_back(EC[i] = i);
76
1
  NumClasses = 0;
77
1
}