This is an archive of the discontinued LLVM Phabricator instance.

[SLP] Avoid signed integer overflow
ClosedPublic

Authored by mssimpso on Aug 19 2016, 12:02 PM.

Details

Summary

The test case included with r279125 exposed an existing signed integer overflow. Since getTreeCost can return INT_MAX, we have to be careful to avoid undefined behavior when summing it with other costs, such as getReductionCost.

This patch removes the possibility of assigning a cost INT_MAX. Since we were previously using INT_MAX as an indicator for "should not vectorize", we now explicitly check this condition with "canVectorizeTree" before computing a cost.

This patch adds a run-line to the test case used for r279125 that ensures we don't vectorize it. Previously, this line would vectorize the test case because of an undefined cost.

Diff Detail

Event Timeline

mssimpso updated this revision to Diff 68718.Aug 19 2016, 12:02 PM
mssimpso retitled this revision from to [SLP] Avoid signed integer overflow.
mssimpso updated this object.
mssimpso added a reviewer: mkuper.
mssimpso added subscribers: hans, llvm-commits, kcc.
mkuper edited edge metadata.Aug 19 2016, 3:25 PM

Using SaturatingAdd here seems right, but:

a) I'd prefer it if the test did check something beyond "don't crash".
b) It would be better it if one of the language lawyers looked at the SaturatingAdd implementation. In particular, I'm not sure casting an out-of-range unsigned to signed is well-defined.

Using SaturatingAdd here seems right, but:

a) I'd prefer it if the test did check something beyond "don't crash".

Yeah, I agree. The difficulty now is that the total cost will be computed as INT_MAX (correctly), which will prevent vectorization in the first place. This really obfuscates the original problem. INT_MAX is set because of the depth < 3 check. The best thing to do might be to add a new command line option specifying the depth at which we declare the tree completely unprofitable to vectorize (instead of hard-coding it to 3). We can then raise the threshold in one run-line to avoid INT_MAX and re-enable vectorization. Another run-line can use the default threshold and ensure the cost doesn't wrap.

b) It would be better it if one of the language lawyers looked at the SaturatingAdd implementation. In particular, I'm not sure casting an out-of-range unsigned to signed is well-defined.

Sure, I'll add more folks to the review.

Daniel,

Would you mind taking a look at the signed version of SaturatingAdd I added when you have a chance. I think you added the existing unsigned version. Thanks!

mssimpso updated this revision to Diff 68913.Aug 22 2016, 2:37 PM
mssimpso updated this object.
mssimpso added a subscriber: gberry.

Hi Michael,

According to @gberry, the signed SaturatingAdd implementation I added isn't well-defined as you guessed. I started rewriting it, but I think a better solution might be to avoid INT_MAX all together. We're using INT_MAX to essentially indicate "do not vectorize". I think it makes better sense to put the INT_MAX logic in a function that returns a bool.

I've updated the patch to do this. I've also kept the existing test case intact, and added a new run-line checking for no vectorization. The test was being vectorized by chance due to the undefined behavior.

mkuper accepted this revision.Aug 22 2016, 3:59 PM
mkuper edited edge metadata.

This LGTM except for the name. :-)

I think the name shouldVectorizeTree() implies that if true, we will vectorize - while in fact, we still need to pass the cost check.
I'd say either (a) rename it to something more explicit (something that references the fact we're checking whether the tree is tiny), or (b) have a single function to perform both the "tininess" check and the cost check.

This revision is now accepted and ready to land.Aug 22 2016, 3:59 PM

Thanks, Michael! I'll rewrite the function as isTreeTinyAndNotFullyVectorizable.

This revision was automatically updated to reflect the committed changes.