Page MenuHomePhabricator

[SLP] Fixed non-determenistic behavior in Loop Vectorizer.
ClosedPublic

Authored by aaboud on Mar 6 2017, 3:36 AM.

Details

Summary

We should not iterate on Set container.
Added a SmallVector "CheckDepsList", which is used to keep the order when iterating over "CheckDeps" Set.

Diff Detail

Repository
rL LLVM

Event Timeline

aaboud created this revision.Mar 6 2017, 3:37 AM
mkuper edited edge metadata.Mar 6 2017, 11:56 AM

Is there a reason not to make MemAccessInfoSet a SmallSetVector instead?

aaboud added a comment.Mar 7 2017, 1:12 AM

Is there a reason not to make MemAccessInfoSet a SmallSetVector instead?

You are right, I needed to change "erase" to "remove" in order to work with SetVector, which I missed in my first try.
Notice that we will still need to iterate on the ordered set with a "while(!empty())" because we are removing entries from the Set while iterating on it.

aaboud updated this revision to Diff 90814.Mar 7 2017, 1:13 AM

Notice that we will still need to iterate on the ordered set with a "while(!empty())" because we are removing entries from the Set while iterating on it.

Oy. That's not good. Removal from SetVector (except with pop_back) is linear-time... :-\

I'm not a fan of the original patch either, though - both because it keeps the same data twice, in two different members. The best idea I can think off of the top of my head, is having the member be an ordered container, then making a copy into a regular set in areDepsSafe(), and then iterating over the ordered container, but working with the set, like your patch does.
But that's also pretty ugly. Better ideas are welcome.

aaboud updated this revision to Diff 90907.Mar 7 2017, 12:02 PM

One more try.

mkuper added inline comments.Mar 7 2017, 12:43 PM
include/llvm/Analysis/LoopAccessAnalysis.h
97 ↗(On Diff #90907)

I don't think there's a reason to keep the Set typedef here if the only use is for a local variable.

lib/Analysis/LoopAccessAnalysis.cpp
825 ↗(On Diff #90907)

We never have duplicates here anyway, right? So it doesn't matter if it's a set or a list.

1611 ↗(On Diff #90907)

Is this necessary?
I mean, it used to happen as a side-effect of the way the loop was structured, but is CheckDeps every actually used after this?

aaboud marked an inline comment as done.Mar 7 2017, 12:55 PM

Thanks, Michael for the comments.
Unfortunately, I do not have answers for all!

include/llvm/Analysis/LoopAccessAnalysis.h
97 ↗(On Diff #90907)

Agree, will fix.

lib/Analysis/LoopAccessAnalysis.cpp
825 ↗(On Diff #90907)

I do not know this code Michael, but even if we end up having duplication, we are going to process them once due to the "Visited" set.

1611 ↗(On Diff #90907)

Again, I am not familiar with the code, from my check, this is why I preferred to keep same behavior as before.

I do not mind removing this line.

mkuper accepted this revision.Mar 7 2017, 1:08 PM

LGTM, modulo the minor issues inline.

lib/Analysis/LoopAccessAnalysis.cpp
825 ↗(On Diff #90907)

Yes, but if there's a lot of duplication, then the loop now has many more iterations. I think this is fine, though, since a pointer can't be in more than one AliasSet.

1611 ↗(On Diff #90907)

I don't know this code well enough either to positively say whether it's safe to remove. That's why I'm asking you to check. :-)

This revision is now accepted and ready to land.Mar 7 2017, 1:08 PM
aaboud updated this revision to Diff 90922.Mar 7 2017, 1:20 PM
aaboud marked an inline comment as done.

Updated patch as agreed.
I doubled check and it seems that it is safe not to clear the CheckDeps at areDepsSafe, if need to be reused the code clear it, otherwise it will be deleted when deleting the LoopAccessInfo instance.

This revision was automatically updated to reflect the committed changes.