1//===-- llvm/ADT/IntEqClasses.h - Equiv. Classes of Integers ----*- C++ -*-===// 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/// \file 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#ifndef LLVM_ADT_INTEQCLASSES_H 22#define LLVM_ADT_INTEQCLASSES_H 23 24#include "llvm/ADT/SmallVector.h" 25 26namespace llvm { 27 28class IntEqClasses { 29 /// EC - When uncompressed, map each integer to a smaller member of its 30 /// equivalence class. The class leader is the smallest member and maps to 31 /// itself. 32 /// 33 /// When compressed, EC[i] is the equivalence class of i. 34 SmallVector<unsigned, 8> EC; 35 36 /// NumClasses - The number of equivalence classes when compressed, or 0 when 37 /// uncompressed. 38 unsigned NumClasses = 0; 39 40public: 41 /// IntEqClasses - Create an equivalence class mapping for 0 .. N-1. 42 IntEqClasses(unsigned N = 0) { grow(N); } 43 44 /// grow - Increase capacity to hold 0 .. N-1, putting new integers in unique 45 /// equivalence classes. 46 /// This requires an uncompressed map. 47 void grow(unsigned N); 48 49 /// clear - Clear all classes so that grow() will assign a unique class to 50 /// every integer. 51 void clear() { 52 EC.clear(); 53 NumClasses = 0; 54 } 55 56 /// Join the equivalence classes of a and b. After joining classes, 57 /// findLeader(a) == findLeader(b). This requires an uncompressed map. 58 /// Returns the new leader. 59 unsigned join(unsigned a, unsigned b); 60 61 /// findLeader - Compute the leader of a's equivalence class. This is the 62 /// smallest member of the class. 63 /// This requires an uncompressed map. 64 unsigned findLeader(unsigned a) const; 65 66 /// compress - Compress equivalence classes by numbering them 0 .. M. 67 /// This makes the equivalence class map immutable. 68 void compress(); 69 70 /// getNumClasses - Return the number of equivalence classes after compress() 71 /// was called. 72 unsigned getNumClasses() const { return NumClasses; } 73 74 /// operator[] - Return a's equivalence class number, 0 .. getNumClasses()-1. 75 /// This requires a compressed map. 76 unsigned operator[](unsigned a) const { 77 assert(NumClasses && "operator[] called before compress()"); 78 return EC[a]; 79 } 80 81 /// uncompress - Change back to the uncompressed representation that allows 82 /// editing. 83 void uncompress(); 84}; 85 86} // End llvm namespace 87 88#endif 89