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 26 namespace llvm { 27 28 class 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 40 public: 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