LLVM 20.0.0git
IntEqClasses.cpp
Go to the documentation of this file.
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
21#include <cassert>
22
23using namespace llvm;
24
25void IntEqClasses::grow(unsigned N) {
26 assert(NumClasses == 0 && "grow() called after compress().");
27 EC.reserve(N);
28 while (EC.size() < N)
29 EC.push_back(EC.size());
30}
31
32unsigned IntEqClasses::join(unsigned a, unsigned b) {
33 assert(NumClasses == 0 && "join() called after compress().");
34 unsigned eca = EC[a];
35 unsigned ecb = EC[b];
36 // Update pointers while searching for the leaders, compressing the paths
37 // incrementally. The larger leader will eventually be updated, joining the
38 // classes.
39 while (eca != ecb)
40 if (eca < ecb) {
41 EC[b] = eca;
42 b = ecb;
43 ecb = EC[b];
44 } else {
45 EC[a] = ecb;
46 a = eca;
47 eca = EC[a];
48 }
49
50 return eca;
51}
52
53unsigned IntEqClasses::findLeader(unsigned a) const {
54 assert(NumClasses == 0 && "findLeader() called after compress().");
55 while (a != EC[a])
56 a = EC[a];
57 return a;
58}
59
61 if (NumClasses)
62 return;
63 for (unsigned i = 0, e = EC.size(); i != e; ++i)
64 EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]];
65}
66
68 if (!NumClasses)
69 return;
71 for (unsigned i = 0, e = EC.size(); i != e; ++i)
72 if (EC[i] < Leader.size())
73 EC[i] = Leader[EC[i]];
74 else
75 Leader.push_back(EC[i] = i);
76 NumClasses = 0;
77}
Equivalence classes for small integers.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned findLeader(unsigned a) const
findLeader - Compute the leader of a's equivalence class.
void compress()
compress - Compress equivalence classes by numbering them 0 .
void uncompress()
uncompress - Change back to the uncompressed representation that allows editing.
unsigned join(unsigned a, unsigned b)
Join the equivalence classes of a and b.
void grow(unsigned N)
grow - Increase capacity to hold 0 .
size_t size() const
Definition: SmallVector.h:92
void reserve(size_type N)
Definition: SmallVector.h:677
void push_back(const T &Elt)
Definition: SmallVector.h:427
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
#define N