12a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen//===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===// 22a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// 32a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// The LLVM Compiler Infrastructure 42a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// 52a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// This file is distributed under the University of Illinois Open Source 62a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// License. See LICENSE.TXT for details. 72a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// 82a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 92a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// 102a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// Equivalence classes for small integers. This is a mapping of the integers 112a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// 0 .. N-1 into M equivalence classes numbered 0 .. M-1. 122a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// 132a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// Initially each integer has its own equivalence class. Classes are joined by 142a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// passing a representative member of each class to join(). 152a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// 162a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// Once the classes are built, compress() will number them 0 .. M-1 and prevent 172a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// further changes. 182a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen// 192a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen//===----------------------------------------------------------------------===// 202a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen 212a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen#include "llvm/ADT/IntEqClasses.h" 222a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen 232a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesenusing namespace llvm; 242a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen 252a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesenvoid IntEqClasses::grow(unsigned N) { 262a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen assert(NumClasses == 0 && "grow() called after compress()."); 27b907e8a2d40dc546f21ff7e122a80b121653851aJakob Stoklund Olesen EC.reserve(N); 282a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen while (EC.size() < N) 292a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen EC.push_back(EC.size()); 302a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen} 312a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen 322a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesenvoid IntEqClasses::join(unsigned a, unsigned b) { 332a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen assert(NumClasses == 0 && "join() called after compress()."); 342a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen unsigned eca = EC[a]; 352a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen unsigned ecb = EC[b]; 362a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen // Update pointers while searching for the leaders, compressing the paths 372a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen // incrementally. The larger leader will eventually be updated, joining the 382a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen // classes. 392a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen while (eca != ecb) 402a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen if (eca < ecb) 412a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen EC[b] = eca, b = ecb, ecb = EC[b]; 422a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen else 432a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen EC[a] = ecb, a = eca, eca = EC[a]; 442a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen} 452a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen 462a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesenunsigned IntEqClasses::findLeader(unsigned a) const { 472a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen assert(NumClasses == 0 && "findLeader() called after compress()."); 482a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen while (a != EC[a]) 492a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen a = EC[a]; 502a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen return a; 512a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen} 522a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen 532a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesenvoid IntEqClasses::compress() { 542a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen if (NumClasses) 552a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen return; 562a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen for (unsigned i = 0, e = EC.size(); i != e; ++i) 572a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]]; 582a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen} 592a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen 602a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesenvoid IntEqClasses::uncompress() { 612a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen if (!NumClasses) 622a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen return; 632a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen SmallVector<unsigned, 8> Leader; 642a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen for (unsigned i = 0, e = EC.size(); i != e; ++i) 652a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen if (EC[i] < Leader.size()) 662a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen EC[i] = Leader[EC[i]]; 672a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen else 682a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen Leader.push_back(EC[i] = i); 692a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen NumClasses = 0; 702a6899c5391a9aada02686dee29f9b56218ed1d3Jakob Stoklund Olesen} 71