/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Support/IntEqClasses.cpp
Line | Count | Source (jump to first uncovered line) |
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 | 4.01M | void IntEqClasses::grow(unsigned N) { |
26 | 4.01M | assert(NumClasses == 0 && "grow() called after compress()."); |
27 | 4.01M | EC.reserve(N); |
28 | 15.2M | while (EC.size() < N) |
29 | 11.2M | EC.push_back(EC.size()); |
30 | 4.01M | } |
31 | | |
32 | 6.57M | unsigned IntEqClasses::join(unsigned a, unsigned b) { |
33 | 6.57M | assert(NumClasses == 0 && "join() called after compress()."); |
34 | 6.57M | unsigned eca = EC[a]; |
35 | 6.57M | unsigned ecb = EC[b]; |
36 | 6.57M | // Update pointers while searching for the leaders, compressing the paths |
37 | 6.57M | // incrementally. The larger leader will eventually be updated, joining the |
38 | 6.57M | // classes. |
39 | 13.1M | while (eca != ecb) |
40 | 6.53M | if (6.53M eca < ecb6.53M ) { |
41 | 4.18M | EC[b] = eca; |
42 | 4.18M | b = ecb; |
43 | 4.18M | ecb = EC[b]; |
44 | 6.53M | } else { |
45 | 2.34M | EC[a] = ecb; |
46 | 2.34M | a = eca; |
47 | 2.34M | eca = EC[a]; |
48 | 2.34M | } |
49 | 6.57M | |
50 | 6.57M | return eca; |
51 | 6.57M | } |
52 | | |
53 | 491 | unsigned IntEqClasses::findLeader(unsigned a) const { |
54 | 491 | assert(NumClasses == 0 && "findLeader() called after compress()."); |
55 | 670 | while (a != EC[a]) |
56 | 179 | a = EC[a]; |
57 | 491 | return a; |
58 | 491 | } |
59 | | |
60 | 2.25M | void IntEqClasses::compress() { |
61 | 2.25M | if (NumClasses) |
62 | 0 | return; |
63 | 13.4M | for (unsigned i = 0, e = EC.size(); 2.25M i != e13.4M ; ++i11.2M ) |
64 | 11.2M | EC[i] = (EC[i] == i) ? 11.2M NumClasses++4.93M : EC[EC[i]]6.26M ; |
65 | 2.25M | } |
66 | | |
67 | 1 | void IntEqClasses::uncompress() { |
68 | 1 | if (!NumClasses) |
69 | 0 | return; |
70 | 1 | SmallVector<unsigned, 8> Leader; |
71 | 11 | for (unsigned i = 0, e = EC.size(); i != e11 ; ++i10 ) |
72 | 10 | if (10 EC[i] < Leader.size()10 ) |
73 | 7 | EC[i] = Leader[EC[i]]; |
74 | 10 | else |
75 | 3 | Leader.push_back(EC[i] = i); |
76 | 1 | NumClasses = 0; |
77 | 1 | } |