LCOV - code coverage report
Current view: top level - lib/Support - IntEqClasses.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 32 33 97.0 %
Date: 2017-09-14 15:23:50 Functions: 5 5 100.0 %
Legend: Lines: hit not hit

          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     2931548 : void IntEqClasses::grow(unsigned N) {
      26             :   assert(NumClasses == 0 && "grow() called after compress().");
      27     2931548 :   EC.reserve(N);
      28    14237641 :   while (EC.size() < N)
      29     5583030 :     EC.push_back(EC.size());
      30     2931548 : }
      31             : 
      32      934339 : unsigned IntEqClasses::join(unsigned a, unsigned b) {
      33             :   assert(NumClasses == 0 && "join() called after compress().");
      34     1868678 :   unsigned eca = EC[a];
      35     1868678 :   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     1825697 :   while (eca != ecb)
      40      891358 :     if (eca < ecb) {
      41      839056 :       EC[b] = eca;
      42      419528 :       b = ecb;
      43      839056 :       ecb = EC[b];
      44             :     } else {
      45      943660 :       EC[a] = ecb;
      46      471830 :       a = eca;
      47      943660 :       eca = EC[a];
      48             :     }
      49             : 
      50      934339 :   return eca;
      51             : }
      52             : 
      53         484 : unsigned IntEqClasses::findLeader(unsigned a) const {
      54             :   assert(NumClasses == 0 && "findLeader() called after compress().");
      55        1314 :   while (a != EC[a])
      56             :     a = EC[a];
      57         484 :   return a;
      58             : }
      59             : 
      60     1544013 : void IntEqClasses::compress() {
      61     1544013 :   if (NumClasses)
      62             :     return;
      63     5879541 :   for (unsigned i = 0, e = EC.size(); i != e; ++i)
      64    10124197 :     EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]];
      65             : }
      66             : 
      67           1 : void IntEqClasses::uncompress() {
      68           1 :   if (!NumClasses)
      69           0 :     return;
      70           2 :   SmallVector<unsigned, 8> Leader;
      71          12 :   for (unsigned i = 0, e = EC.size(); i != e; ++i)
      72          30 :     if (EC[i] < Leader.size())
      73          28 :       EC[i] = Leader[EC[i]];
      74             :     else
      75           6 :       Leader.push_back(EC[i] = i);
      76           1 :   NumClasses = 0;
      77             : }

Generated by: LCOV version 1.13