Page MenuHomePhabricator

Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline

[ADT] Fix IntEqClasses::join to return the leader in all cases.
Needs ReviewPublic

Authored by jcranmer-intel on Aug 25 2023, 12:05 PM.

Details

Reviewers
MatzeB
Summary

The method is specified to return the leader of the result of a join. If
the two members were already in an equivalence class, there is a chance
that it might fail to return the leader. For example, if the array looks
like this:

EC[0] = 0
EC[1] = 0
EC[2] = 1
EC[3] = 1

Then join(2, 3) would have returned 1, which is not the same as the
actual leader 0.

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptAug 25 2023, 12:05 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
jcranmer-intel requested review of this revision.Aug 25 2023, 12:05 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 25 2023, 12:05 PM

Nice catch!

llvm/lib/Support/IntEqClasses.cpp
36–53

Not sure how this would affect worst-case complexity given findLeader does not do any path compression. How about this instead?

jcranmer-intel added inline comments.Aug 30 2023, 7:28 AM
llvm/lib/Support/IntEqClasses.cpp
36–53

The changes I made wouldn't make the worst-case complexity any worse; it seems to me that it would work better to have findLeader do path compression instead (I further note that there appear to be no callers of IntEqClasses::findLeader in LLVM at present, so there's definitely no compile time regression here).

MatzeB added inline comments.Sep 11 2023, 12:12 PM
llvm/lib/Support/IntEqClasses.cpp
36–53

The changes I made wouldn't make the worst-case complexity any worse

They obviously won't affect the case when we only call join on members of different sets. However without the changes I proposed (or adding path compression to findLeader) it's not obvious to me that we won't cannot hit bad complexity for the cases of calling join with on members of the same set (this is only a gut feeling without proof, but you're not presenting an argument against that either).

Anyway any reason not to go with my proposed changes? Anyway adding path-compression to findLeader should also work... Either way you should upload one variant :)

Add support for path compression to IntEqClasses::findLeader.