1221339Sdim//===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===// 2221339Sdim// 3221339Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4221339Sdim// See https://llvm.org/LICENSE.txt for license information. 5221339Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6221339Sdim// 7221339Sdim//===----------------------------------------------------------------------===// 8221339Sdim// 9221339Sdim// Equivalence classes for small integers. This is a mapping of the integers 10221339Sdim// 0 .. N-1 into M equivalence classes numbered 0 .. M-1. 11221339Sdim// 12221339Sdim// Initially each integer has its own equivalence class. Classes are joined by 13221339Sdim// passing a representative member of each class to join(). 14221339Sdim// 15221339Sdim// Once the classes are built, compress() will number them 0 .. M-1 and prevent 16221339Sdim// further changes. 17221339Sdim// 18221339Sdim//===----------------------------------------------------------------------===// 19221339Sdim 20221339Sdim#include "llvm/ADT/IntEqClasses.h" 21221339Sdim 22221339Sdimusing namespace llvm; 23221339Sdim 24221339Sdimvoid IntEqClasses::grow(unsigned N) { 25221339Sdim assert(NumClasses == 0 && "grow() called after compress()."); 26221339Sdim EC.reserve(N); 27221339Sdim while (EC.size() < N) 28221339Sdim EC.push_back(EC.size()); 29221339Sdim} 30221339Sdim 31221339Sdimunsigned IntEqClasses::join(unsigned a, unsigned b) { 32221339Sdim assert(NumClasses == 0 && "join() called after compress()."); 33221339Sdim unsigned eca = EC[a]; 34221339Sdim unsigned ecb = EC[b]; 35221339Sdim // Update pointers while searching for the leaders, compressing the paths 36221339Sdim // incrementally. The larger leader will eventually be updated, joining the 37221339Sdim // classes. 38221339Sdim while (eca != ecb) 39221339Sdim if (eca < ecb) { 40221339Sdim EC[b] = eca; 41221339Sdim b = ecb; 42221339Sdim ecb = EC[b]; 43221339Sdim } else { 44221339Sdim EC[a] = ecb; 45221339Sdim a = eca; 46221339Sdim eca = EC[a]; 47221339Sdim } 48221339Sdim 49221339Sdim return eca; 50221339Sdim} 51221339Sdim 52221339Sdimunsigned IntEqClasses::findLeader(unsigned a) const { 53221339Sdim assert(NumClasses == 0 && "findLeader() called after compress()."); 54221339Sdim while (a != EC[a]) 55221339Sdim a = EC[a]; 56221339Sdim return a; 57221339Sdim} 58221339Sdim 59221339Sdimvoid IntEqClasses::compress() { 60221339Sdim if (NumClasses) 61221339Sdim return; 62221339Sdim for (unsigned i = 0, e = EC.size(); i != e; ++i) 63221339Sdim EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]]; 64221339Sdim} 65221339Sdim 66221339Sdimvoid IntEqClasses::uncompress() { 67221339Sdim if (!NumClasses) 68221339Sdim return; 69221339Sdim SmallVector<unsigned, 8> Leader; 70221339Sdim for (unsigned i = 0, e = EC.size(); i != e; ++i) 71221339Sdim if (EC[i] < Leader.size()) 72221339Sdim EC[i] = Leader[EC[i]]; 73221339Sdim else 74221339Sdim Leader.push_back(EC[i] = i); 75221339Sdim NumClasses = 0; 76221339Sdim} 77221339Sdim