1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
| //===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// Equivalence classes for small integers. This is a mapping of the integers
// 0 .. N-1 into M equivalence classes numbered 0 .. M-1.
//
// Initially each integer has its own equivalence class. Classes are joined by
// passing a representative member of each class to join().
//
// Once the classes are built, compress() will number them 0 .. M-1 and prevent
// further changes.
//
//===----------------------------------------------------------------------===//
#include "llvm/ADT/IntEqClasses.h"
using namespace llvm;
void IntEqClasses::grow(unsigned N) {
assert(NumClasses == 0 && "grow() called after compress().");
EC.reserve(N);
while (EC.size() < N)
EC.push_back(EC.size());
}
unsigned IntEqClasses::join(unsigned a, unsigned b) {
assert(NumClasses == 0 && "join() called after compress().");
unsigned eca = EC[a];
unsigned ecb = EC[b];
// Update pointers while searching for the leaders, compressing the paths
// incrementally. The larger leader will eventually be updated, joining the
// classes.
while (eca != ecb)
if (eca < ecb) {
EC[b] = eca;
b = ecb;
ecb = EC[b];
} else {
EC[a] = ecb;
a = eca;
eca = EC[a];
}
return eca;
}
unsigned IntEqClasses::findLeader(unsigned a) const {
assert(NumClasses == 0 && "findLeader() called after compress().");
while (a != EC[a])
a = EC[a];
return a;
}
void IntEqClasses::compress() {
if (NumClasses)
return;
for (unsigned i = 0, e = EC.size(); i != e; ++i)
EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]];
}
void IntEqClasses::uncompress() {
if (!NumClasses)
return;
SmallVector<unsigned, 8> Leader;
for (unsigned i = 0, e = EC.size(); i != e; ++i)
if (EC[i] < Leader.size())
EC[i] = Leader[EC[i]];
else
Leader.push_back(EC[i] = i);
NumClasses = 0;
}
|