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 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 60void IntEqClasses::compress() { 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 67void IntEqClasses::uncompress() { 68 if (!NumClasses) 69 return; 70 SmallVector<unsigned, 8> Leader; 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} 78