1. [ConstantRange] makeGuaranteedNoWrapRegion(): `shl` support (details)
  2. [InstCombine] Shift amount reassociation in shifty sign bit test (details)
Commit 4b6223263a3c1fb98bc69e8eb6722d48e4eb9f49 by lebedev.ri
[ConstantRange] makeGuaranteedNoWrapRegion(): `shl` support
Summary: If all the shifts amount are already poison-producing, then we
can add more poison-producing flags ontop:
Otherwise, we should only consider the possible range of shift amts that
don't result in poison.
For unsigned range not not overflow, we must not shift out any set bits,
and the actual limit for `x` can be computed by backtransforming the
maximal value we could ever get out of the `shl` - `-1` through
`lshr`. If the `x` is any larger than that then it will overflow.
Likewise for signed range, but just in signed domain..
This is based on the general idea outlined by @nikic in
Reviewers: nikic, sanjoy
Reviewed By: nikic
Subscribers: hiraditya, llvm-commits, nikic
Tags: #llvm
Differential Revision:
llvm-svn: 375370
The file was modifiedllvm/unittests/IR/ConstantRangeTest.cpp
The file was modifiedllvm/lib/IR/ConstantRange.cpp
Commit 49483a3bc2253c9e252e5e37b709534e3b6e51cc by lebedev.ri
[InstCombine] Shift amount reassociation in shifty sign bit test
Summary: This problem consists of several parts:
* Basic sign bit extraction - `trunc? (?shr %x, (bitwidth(x)-1))`.
This is trivial, and easy to do, we have a fold for it.
* Shift amount reassociation - if we have two identical shifts,
and we can simplify-add their shift amounts together,
then we likely can just perform them as a single shift.
But this is finicky, has one-use restrictions,
and shift opcodes must be identical.
But there is a super-pattern where both of these work together. to
produce sign bit test from two shifts + comparison. We do indeed already
handle this in most cases. But since we get that fold transitively, it
has one-use restrictions. And what's worse, in this case the
right-shifts aren't required to be identical, and we can't handle that
If the total shift amount is bitwidth-1, only a sign bit will remain in
the output value. But if we look at this from the perspective of two
shifts, we can't fold - we can't possibly know what bit pattern we'd
produce via two shifts, it will be *some* kind of a mask produced from
original sign bit, but we just can't tell it's shape:
But it will *only* contain sign bit and zeros. So from the perspective
of sign bit test, we're good: Superb!
So the simplest solution is to extend
`reassociateShiftAmtsOfTwoSameDirectionShifts()` to also have a
sudo-analysis mode that will ignore extra-uses, and will only check
whether a) those are two right shifts and b) they end up with
bitwidth(x)-1 shift amount and return either the original value that we
sign-checking, or null.
This does not have any functionality change for the existing
All that being said, as disscussed in the review, this yet again
increases usage of instsimplify in instcombine as utility. Some day that
may need to be reevaluated.
Reviewers: spatel, efriedma, vsk
Reviewed By: spatel
Subscribers: xbolva00, hiraditya, llvm-commits
Tags: #llvm
Differential Revision:
llvm-svn: 375371
The file was modifiedllvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
The file was modifiedllvm/lib/Transforms/InstCombine/InstCombineInternal.h
The file was modifiedllvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
The file was modifiedllvm/test/Transforms/InstCombine/sign-bit-test-via-right-shifting-all-other-bits.ll