LLVM  14.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 
20 #include "llvm/ADT/IntEqClasses.h"
21 #include <cassert>
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 }
i
i
Definition: README.txt:29
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::SmallVector< unsigned, 8 >
IntEqClasses.h
llvm::IntEqClasses::join
unsigned join(unsigned a, unsigned b)
Join the equivalence classes of a and b.
Definition: IntEqClasses.cpp:32
llvm::IntEqClasses::findLeader
unsigned findLeader(unsigned a) const
findLeader - Compute the leader of a's equivalence class.
Definition: IntEqClasses.cpp:53
a
=0.0 ? 0.0 :(a > 0.0 ? 1.0 :-1.0) a
Definition: README.txt:489
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
llvm::IntEqClasses::compress
void compress()
compress - Compress equivalence classes by numbering them 0 .
Definition: IntEqClasses.cpp:60
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::IntEqClasses::grow
void grow(unsigned N)
grow - Increase capacity to hold 0 .
Definition: IntEqClasses.cpp:25
N
#define N
llvm::IntEqClasses::uncompress
void uncompress()
uncompress - Change back to the uncompressed representation that allows editing.
Definition: IntEqClasses.cpp:67
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624