LCOV - code coverage report
Current view: top level - lib/Support - IntEqClasses.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 29 30 96.7 %
Date: 2018-02-18 16:14:26 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     3299782 : void IntEqClasses::grow(unsigned N) {
      26             :   assert(NumClasses == 0 && "grow() called after compress().");
      27     3299782 :   EC.reserve(N);
      28     9737768 :   while (EC.size() < N)
      29     3218993 :     EC.push_back(EC.size());
      30     3299782 : }
      31             : 
      32     1034592 : unsigned IntEqClasses::join(unsigned a, unsigned b) {
      33             :   assert(NumClasses == 0 && "join() called after compress().");
      34     2069184 :   unsigned eca = EC[a];
      35     2069184 :   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     2025772 :   while (eca != ecb)
      40      991180 :     if (eca < ecb) {
      41      965456 :       EC[b] = eca;
      42             :       b = ecb;
      43      965456 :       ecb = EC[b];
      44             :     } else {
      45     1016904 :       EC[a] = ecb;
      46             :       a = eca;
      47     1016904 :       eca = EC[a];
      48             :     }
      49             : 
      50     1034592 :   return eca;
      51             : }
      52             : 
      53         481 : unsigned IntEqClasses::findLeader(unsigned a) const {
      54             :   assert(NumClasses == 0 && "findLeader() called after compress().");
      55        1284 :   while (a != EC[a])
      56             :     a = EC[a];
      57         481 :   return a;
      58             : }
      59             : 
      60     1762658 : void IntEqClasses::compress() {
      61     1762658 :   if (NumClasses)
      62             :     return;
      63     4981651 :   for (unsigned i = 0, e = EC.size(); i != e; ++i)
      64     7412101 :     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          30 :     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             : }

Generated by: LCOV version 1.13