LLVM  9.0.0svn
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 
20 #include "llvm/ADT/IntEqClasses.h"
21 
22 using namespace llvm;
23 
24 void IntEqClasses::grow(unsigned N) {
25  assert(NumClasses == 0 && "grow() called after compress().");
26  EC.reserve(N);
27  while (EC.size() < N)
28  EC.push_back(EC.size());
29 }
30 
31 unsigned IntEqClasses::join(unsigned a, unsigned b) {
32  assert(NumClasses == 0 && "join() called after compress().");
33  unsigned eca = EC[a];
34  unsigned ecb = EC[b];
35  // Update pointers while searching for the leaders, compressing the paths
36  // incrementally. The larger leader will eventually be updated, joining the
37  // classes.
38  while (eca != ecb)
39  if (eca < ecb) {
40  EC[b] = eca;
41  b = ecb;
42  ecb = EC[b];
43  } else {
44  EC[a] = ecb;
45  a = eca;
46  eca = EC[a];
47  }
48 
49  return eca;
50 }
51 
52 unsigned IntEqClasses::findLeader(unsigned a) const {
53  assert(NumClasses == 0 && "findLeader() called after compress().");
54  while (a != EC[a])
55  a = EC[a];
56  return a;
57 }
58 
60  if (NumClasses)
61  return;
62  for (unsigned i = 0, e = EC.size(); i != e; ++i)
63  EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]];
64 }
65 
67  if (!NumClasses)
68  return;
70  for (unsigned i = 0, e = EC.size(); i != e; ++i)
71  if (EC[i] < Leader.size())
72  EC[i] = Leader[EC[i]];
73  else
74  Leader.push_back(EC[i] = i);
75  NumClasses = 0;
76 }
unsigned findLeader(unsigned a) const
findLeader - Compute the leader of a&#39;s equivalence class.
void grow(unsigned N)
grow - Increase capacity to hold 0 .
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void push_back(const T &Elt)
Definition: SmallVector.h:211
void compress()
compress - Compress equivalence classes by numbering them 0 .
void reserve(size_type N)
Definition: SmallVector.h:369
void uncompress()
uncompress - Change back to the uncompressed representation that allows editing.
size_t size() const
Definition: SmallVector.h:52
unsigned join(unsigned a, unsigned b)
Join the equivalence classes of a and b.
#define N
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())