LLVM  8.0.0svn
IntEqClasses.cpp
Go to the documentation of this file.
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 void 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 
32 unsigned 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 
53 unsigned 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 }
unsigned findLeader(unsigned a) const
findLeader - Compute the leader of a&#39;s equivalence class.
void push_back(const T &Elt)
Definition: SmallVector.h:218
void grow(unsigned N)
grow - Increase capacity to hold 0 .
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
void compress()
compress - Compress equivalence classes by numbering them 0 .
void reserve(size_type N)
Definition: SmallVector.h:376
void uncompress()
uncompress - Change back to the uncompressed representation that allows editing.
size_t size() const
Definition: SmallVector.h:53
unsigned join(unsigned a, unsigned b)
Join the equivalence classes of a and b.
#define N
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())