This is an archive of the discontinued LLVM Phabricator instance.

[SLSR] consider &B[S << i] as &B[(1 << i) * S]
ClosedPublic

Authored by jingyue on Apr 5 2015, 10:54 PM.

Details

Summary

This reduces handling &B[(1 << i) * s] to handling &B[i * S].

Diff Detail

Event Timeline

jingyue updated this revision to Diff 23263.Apr 5 2015, 10:54 PM
jingyue retitled this revision from to [SLSR] consider &B[S << i] as &B[(1 << i) * S].
jingyue updated this object.
jingyue edited the test plan for this revision. (Show Details)
jingyue added a reviewer: meheff.
jingyue added a subscriber: Unknown Object (MLST).
sanjoy added a subscriber: sanjoy.Apr 5 2015, 11:37 PM

Super-pedantic nit on the comment message: I think it should be "This reduces handling &B[(i << 1) * s] to handling &B[i * S]."

lib/Transforms/Scalar/StraightLineStrengthReduce.cpp
372

A << B is nsw does not imply A * (1 << B) is nsw. For i8 a counterexample is A = -1 and B = 7 -- -1 << 7 does not sign-overflow but -1 * -128 sign-overflows. In general, for iN I think the only counterexample has B = N-1; if that can be proved (I haven't tried) then it should be sufficient to guard for just that.

Please disregard my last comment on the nsw bit. I checked, the langref defines nsw in terms of the multiplication that would be equivalent to the shift, and your code is correct as it is.

In case you're curious, I was going by the following definition of sign-overflow -- A OP B sign-overflows if "sext(A) OP sext(B) != sext(A OP B)". That definition does not really make sense in the context of left shifts.

jingyue updated this revision to Diff 23277.Apr 6 2015, 9:24 AM

A minor fix to the commit message. Thanks, Sanjoy!

meheff edited edge metadata.Apr 6 2015, 9:57 AM

LGTM. Thanks!

This revision was automatically updated to reflect the committed changes.