Line data    Source code

       1             : //===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      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             : #include "llvm/ADT/IntEqClasses.h"
      22             : 
      23             : using namespace llvm;
      24             : 
      25     4330313 : void IntEqClasses::grow(unsigned N) {
      26             :   assert(NumClasses == 0 && "grow() called after compress().");
      27     4330313 :   EC.reserve(N);
      28    14148373 :   while (EC.size() < N)
      29     9818060 :     EC.push_back(EC.size());
      30     4330313 : }
      31             : 
      32     4819689 : unsigned IntEqClasses::join(unsigned a, unsigned b) {
      33             :   assert(NumClasses == 0 && "join() called after compress().");
      34     4819689 :   unsigned eca = EC[a];
      35     9639378 :   unsigned ecb = EC[b];
      36             :   // Update pointers while searching for the leaders, compressing the paths
      37             :   // incrementally. The larger leader will eventually be updated, joining the
      38             :   // classes.
      39     9610503 :   while (eca != ecb)
      40     4790814 :     if (eca < ecb) {
      41     3265997 :       EC[b] = eca;
      42             :       b = ecb;
      43     6531994 :       ecb = EC[b];
      44             :     } else {
      45     1524817 :       EC[a] = ecb;
      46             :       a = eca;
      47     3049634 :       eca = EC[a];
      48             :     }
      49             : 
      50     4819689 :   return eca;
      51             : }
      52             : 
      53         577 : unsigned IntEqClasses::findLeader(unsigned a) const {
      54             :   assert(NumClasses == 0 && "findLeader() called after compress().");
      55        1558 :   while (a != EC[a])
      56             :     a = EC[a];
      57         577 :   return a;
      58             : }
      59             : 
      60     2388690 : void IntEqClasses::compress() {
      61     2388690 :   if (NumClasses)
      62             :     return;
      63    12206750 :   for (unsigned i = 0, e = EC.size(); i != e; ++i)
      64    19636120 :     EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]];
      65             : }
      66             : 
      67           1 : void IntEqClasses::uncompress() {
      68           1 :   if (!NumClasses)
      69           0 :     return;
      70             :   SmallVector<unsigned, 8> Leader;
      71          11 :   for (unsigned i = 0, e = EC.size(); i != e; ++i)
      72          20 :     if (EC[i] < Leader.size())
      73           7 :       EC[i] = Leader[EC[i]];
      74             :     else
      75           3 :       Leader.push_back(EC[i] = i);
      76           1 :   NumClasses = 0;
      77             : }