[LLVMdev] EquivalenceClasses

[Anton Vayvod]

On 5/9/07, David Greene <greened at obbligato.org> wrote:
>
> Can someone explain the terminology used in the Doxygen
> comments for EquivalenceClasses?  Specifically, what is
> a "Leader" as opposed to other members of an equivalence
> class?


As far as I understand, leader is the first element of the class within the
std::set container where all element of all classes are stored altogether.
Leader contains a pointer to the last element of the class. The idea is
similar to storing multiple linked lists in an array or in a vector. Leader
elements allow iterating through class elements only via
EquivalenceClasses::member_begin, member_end methods. Except of that there
is no difference between the leader and the rest members of an equivalence
class here.

These leaders doesn't relate to coset leaders or something, AFAIK. It's not
a mathematical notion there.

Say, for example, I want to create a set of equivalence
> classes to specify subset relationships.  Imagine B is
> a subset of A, C is a subset of B, E is a subset of D
> and D has no relation to any other set.  I'd like to
> group things into equivalence classes representing
> "immediate" subsets:
>
> Class 1: A, B
> Class 2: B, C
> Class 3: D, E


I don't understand how A and B, for example, are equivalent. B is a subset
of A but not vice versa. Thus your relation is not symmetric.

Would A, B and D be the "Leaders" of the equivalence classes?
> Note that I don't want {A, B, C} as an equivalence class
> because it breaks the "immediate subset" relationship.
>
> With a relationship like equality, there is no problem because
> no member of the equivalence class has any different information
> about it than any other.  But a relation like "subset" implies
> that members of the equivalence class are not all equal.


Equivalence classes are defined via equivalence relation. Subset is not one
so this data structure just won't work correctly. I think that your relation
should be represented by another structure. E.g. undirected graph can be
used to represent any binary relation (if you chose binary matrix
representation I'd recommend using BitSetVector data structure found in
include/llvm/ADT directory).

FYI, in linear scan register allocator EquivalenceClasses object is used to
divide register classes via "alias" relation. See ComputeRelatedRegClasses
method in RegAllocLinearScan.cpp.

Anton.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20070510/e6b9af86/attachment.html>