10b57cec5SDimitry Andric //===-- llvm/ADT/IntEqClasses.h - Equiv. Classes of Integers ----*- C++ -*-===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 81fd87a68SDimitry Andric /// 91fd87a68SDimitry Andric /// \file 101fd87a68SDimitry Andric /// Equivalence classes for small integers. This is a mapping of the integers 111fd87a68SDimitry Andric /// 0 .. N-1 into M equivalence classes numbered 0 .. M-1. 121fd87a68SDimitry Andric /// 131fd87a68SDimitry Andric /// Initially each integer has its own equivalence class. Classes are joined by 141fd87a68SDimitry Andric /// passing a representative member of each class to join(). 151fd87a68SDimitry Andric /// 161fd87a68SDimitry Andric /// Once the classes are built, compress() will number them 0 .. M-1 and prevent 171fd87a68SDimitry Andric /// further changes. 181fd87a68SDimitry Andric /// 190b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 200b57cec5SDimitry Andric 210b57cec5SDimitry Andric #ifndef LLVM_ADT_INTEQCLASSES_H 220b57cec5SDimitry Andric #define LLVM_ADT_INTEQCLASSES_H 230b57cec5SDimitry Andric 240b57cec5SDimitry Andric #include "llvm/ADT/SmallVector.h" 250b57cec5SDimitry Andric 260b57cec5SDimitry Andric namespace llvm { 270b57cec5SDimitry Andric 280b57cec5SDimitry Andric class IntEqClasses { 290b57cec5SDimitry Andric /// EC - When uncompressed, map each integer to a smaller member of its 300b57cec5SDimitry Andric /// equivalence class. The class leader is the smallest member and maps to 310b57cec5SDimitry Andric /// itself. 320b57cec5SDimitry Andric /// 330b57cec5SDimitry Andric /// When compressed, EC[i] is the equivalence class of i. 340b57cec5SDimitry Andric SmallVector<unsigned, 8> EC; 350b57cec5SDimitry Andric 360b57cec5SDimitry Andric /// NumClasses - The number of equivalence classes when compressed, or 0 when 370b57cec5SDimitry Andric /// uncompressed. 38*fcaf7f86SDimitry Andric unsigned NumClasses = 0; 390b57cec5SDimitry Andric 400b57cec5SDimitry Andric public: 410b57cec5SDimitry Andric /// IntEqClasses - Create an equivalence class mapping for 0 .. N-1. 42*fcaf7f86SDimitry Andric IntEqClasses(unsigned N = 0) { grow(N); } 430b57cec5SDimitry Andric 440b57cec5SDimitry Andric /// grow - Increase capacity to hold 0 .. N-1, putting new integers in unique 450b57cec5SDimitry Andric /// equivalence classes. 460b57cec5SDimitry Andric /// This requires an uncompressed map. 470b57cec5SDimitry Andric void grow(unsigned N); 480b57cec5SDimitry Andric 490b57cec5SDimitry Andric /// clear - Clear all classes so that grow() will assign a unique class to 500b57cec5SDimitry Andric /// every integer. clear()510b57cec5SDimitry Andric void clear() { 520b57cec5SDimitry Andric EC.clear(); 530b57cec5SDimitry Andric NumClasses = 0; 540b57cec5SDimitry Andric } 550b57cec5SDimitry Andric 560b57cec5SDimitry Andric /// Join the equivalence classes of a and b. After joining classes, 570b57cec5SDimitry Andric /// findLeader(a) == findLeader(b). This requires an uncompressed map. 580b57cec5SDimitry Andric /// Returns the new leader. 590b57cec5SDimitry Andric unsigned join(unsigned a, unsigned b); 600b57cec5SDimitry Andric 610b57cec5SDimitry Andric /// findLeader - Compute the leader of a's equivalence class. This is the 620b57cec5SDimitry Andric /// smallest member of the class. 630b57cec5SDimitry Andric /// This requires an uncompressed map. 640b57cec5SDimitry Andric unsigned findLeader(unsigned a) const; 650b57cec5SDimitry Andric 660b57cec5SDimitry Andric /// compress - Compress equivalence classes by numbering them 0 .. M. 670b57cec5SDimitry Andric /// This makes the equivalence class map immutable. 680b57cec5SDimitry Andric void compress(); 690b57cec5SDimitry Andric 700b57cec5SDimitry Andric /// getNumClasses - Return the number of equivalence classes after compress() 710b57cec5SDimitry Andric /// was called. getNumClasses()720b57cec5SDimitry Andric unsigned getNumClasses() const { return NumClasses; } 730b57cec5SDimitry Andric 740b57cec5SDimitry Andric /// operator[] - Return a's equivalence class number, 0 .. getNumClasses()-1. 750b57cec5SDimitry Andric /// This requires a compressed map. 760b57cec5SDimitry Andric unsigned operator[](unsigned a) const { 770b57cec5SDimitry Andric assert(NumClasses && "operator[] called before compress()"); 780b57cec5SDimitry Andric return EC[a]; 790b57cec5SDimitry Andric } 800b57cec5SDimitry Andric 810b57cec5SDimitry Andric /// uncompress - Change back to the uncompressed representation that allows 820b57cec5SDimitry Andric /// editing. 830b57cec5SDimitry Andric void uncompress(); 840b57cec5SDimitry Andric }; 850b57cec5SDimitry Andric 860b57cec5SDimitry Andric } // End llvm namespace 870b57cec5SDimitry Andric 880b57cec5SDimitry Andric #endif 89