This is an archive of the discontinued LLVM Phabricator instance.

[LV] Fix incorrect detection of type-promoted Phis
AbandonedPublic

Authored by mkazantsev on Jan 11 2018, 1:55 AM.

Details

Summary

Loop vectorizer may recognize the following pattern

%iv = phi i32 ...
%x = add i32 %iv, %mask

where %mask is 2^N - 1 as Phi node of type iN which was type-promoted
during canonicalizing transforms. In this case we can vectorize the loop using
its original type and fit more elements into one vector.

The logic that is responsible for this is broken. It only demands that a Phi is
masked, but does not check that after all calculations the result is actually
truncated to type iN. As result, it may falsely detect the following code as
being somehow connected to type-promoted Phis:

char foo(char c) {
    for (int i = 1; i < 193; i++) {
          c &= (char) 1;
          c += (char) 3;
    }
    return c;
}

Vectorizer tries to calculate the result of this loop in vector of i1, what lead
to incorrect calculations (answer is always 0 or 1 instead of 3 or `4).

This patch strengthens the detecor of this situation. If we have shrinked the
type due to masking, we should later check that the result of all calculations
is either dead or is properly truncated to this type.

Diff Detail

Event Timeline

mkazantsev created this revision.Jan 11 2018, 1:55 AM

Added a comment, fixed some typos.

anna added inline comments.Jan 22 2018, 2:01 PM
lib/Transforms/Utils/LoopUtils.cpp
372

I don't think you can assert since you can have uses of ExitInstruction in unreachable blocks and unreachable blocks by definition are outside a loop.

388

getNumUses is linear in the number of uses. This is better: LCSSAPhi->hasNUsesOrMore(2)

mkazantsev marked 2 inline comments as done.
mkazantsev added inline comments.
lib/Transforms/Utils/LoopUtils.cpp
372

Good point, thanks!

anna accepted this revision.Feb 1 2018, 5:38 AM
anna added a subscriber: mssimpso.

LGTM. I think there maybe performance degradations in vectorization, but this is needed for a correctness fix.
Pls wait for @mssimpso if he has any comments.

This revision is now accepted and ready to land.Feb 1 2018, 5:38 AM
anna added a comment.Feb 2 2018, 2:12 PM

I just saw on another review thread that Matt's away for a few weeks.
Max, feel free to land this change.

I cannot merge this because of https://reviews.llvm.org/D42309 which has been merged yesterday and removed the piece of code which I touched. It was addressing the bug PR35734 which actually looks pretty similar to what I was trying to fix here. I don't know this code good enough to understand whether it actually has fixed the problem or just hid it, though. However it helps the test. I think I will just end up merging the tests as NFC and abandoning this one since this logic is no more.

mkazantsev abandoned this revision.Feb 6 2018, 1:21 AM

Abandoning due to underlying code massive rework done in https://reviews.llvm.org/rL324195. The bug was fixed with this patch. The tests merged separately as NFC.

Max/Anna,

Sorry for not responding sooner - I was away from work for a few weeks. Yes, this looks like the same issue that was fixed over in rL324195. Thanks for adding the new tests, and sorry for the duplicated effort! Let me know if you run into any problems with the new code.