DirectXShaderCompiler/lib/Support/IntEqClasses.cpp at main · microsoft/DirectXShaderCompiler · GitHub

History

70 lines (63 loc) · 2.08 KB

Raw

//===-- llvm/ADT/IntEqClasses.cpp - Equivalence Classes of Integers -------===//

// The LLVM Compiler Infrastructure

// This file is distributed under the University of Illinois Open Source

// License. See LICENSE.TXT for details.

//===----------------------------------------------------------------------===//

// Equivalence classes for small integers. This is a mapping of the integers

// 0 .. N-1 into M equivalence classes numbered 0 .. M-1.

// Initially each integer has its own equivalence class. Classes are joined by

// passing a representative member of each class to join().

// Once the classes are built, compress() will number them 0 .. M-1 and prevent

// further changes.

//===----------------------------------------------------------------------===//

#include "llvm/ADT/IntEqClasses.h"

using namespace llvm;

void IntEqClasses::grow(unsigned N) {

assert(NumClasses == 0 && "grow() called after compress().");

EC.reserve(N);

while (EC.size() < N)

EC.push_back(EC.size());

}

void IntEqClasses::join(unsigned a, unsigned b) {

assert(NumClasses == 0 && "join() called after compress().");

unsigned eca = EC[a];

unsigned ecb = EC[b];

// Update pointers while searching for the leaders, compressing the paths

// incrementally. The larger leader will eventually be updated, joining the

// classes.

while (eca != ecb)

if (eca < ecb)

EC[b] = eca, b = ecb, ecb = EC[b];

else

EC[a] = ecb, a = eca, eca = EC[a];

}

unsigned IntEqClasses::findLeader(unsigned a) const {

assert(NumClasses == 0 && "findLeader() called after compress().");

while (a != EC[a])

a = EC[a];

return a;

}

void IntEqClasses::compress() {

if (NumClasses)

return;

for (unsigned i = 0, e = EC.size(); i != e; ++i)

EC[i] = (EC[i] == i) ? NumClasses++ : EC[EC[i]];

}

void IntEqClasses::uncompress() {

if (!NumClasses)

return;

SmallVector<unsigned, 8> Leader;

for (unsigned i = 0, e = EC.size(); i != e; ++i)

if (EC[i] < Leader.size())

EC[i] = Leader[EC[i]];

else

Leader.push_back(EC[i] = i);

NumClasses = 0;

}

DirectXShaderCompiler/lib/Support/IntEqClasses.cpp at main · microsoft/DirectXShaderCompiler · GitHub

Uh oh!

Expand file tree

Breadcrumbs

IntEqClasses.cpp

Latest commit

History

Breadcrumbs

IntEqClasses.cpp

File metadata and controls