(original) (raw)

On Apr 6, 2020, at 16:53, Stefanos Baziotis <stefanos.baziotis@gmail.com> wrote:

Hi,

> But the value can't be \[0,7\] due to the earlier branch. When I said it was guaranteed to wrap, I only meant for the range of values that were possible after the first branch.
Indeed, for some reason I remembered that the left check is >= 0 when I wrote this.

Thanks a lot for the breakdown in CorrelatedValuePropagation. I had no idea about this pass.

> It was able to see that the input to add was in the range \[8,14) in the call to LVI->getConstantRange in processBinOp.

I could not reproduce that. I get:
BinOp: %4 = add nsw i32 %2, -8
LRange: \[0,-2147483648)
RRange: \[-8,-7)

> processCmp skips calling LVI for the select's icmp because the input isn't in the same basic block and isn't a phi.
Do you maybe mean: \_is\_ in the same BB (and isn't a PHI).

By the way, I don't get the reasoning in the comment above:
// As a policy choice, we choose not to waste compile time on anything where
// the comparison is testing local values.

> I think this is because the code executed for getConstant doesn't handle icmp even when it can prove the input is in a constant range.

Maybe we ended up on the same thing. I'm not sure I followed that correctly but getValueFromICmpCondition() should have been able to handle that.

Best,
Stefanos

Στις Δευ, 6 Απρ 2020 στις 5:22 π.μ., ο/η Craig Topper <craig.topper@gmail.com> έγραψε:

On Sun, Apr 5, 2020 at 6:34 PM Stefanos Baziotis <stefanos.baziotis@gmail.com> wrote:

Hi Craig,

> Adding a nuw to the add -8 is incorrect.
Yeah, I didn't mean to say it was correct. It was just an observation that with nuw the optimization was happened and I asked if someone thought it was somehow connected.

> From the perspective of the unsigned math, -8 is treated a very large positive number. The input to the add is \[8,13) and adding a large positive number to it wraps around past 0\. So that is guaranteed unsigned wrap
I understand yes, but I don't think it is guaranteed. Unless I miss something, for values in \[0, 7\] it won't wrap. But past that and up to (and including in the original source code) 13, it will wrap yes.

But the value can't be \[0,7\] due to the earlier branch. When I said it was guaranteed to wrap, I only meant for the range of values that were possible after the first branch.

In theory, the CorrelatedValuePropagation pass should have been able to optimize the select. It was able to see that the input to add was in the range \[8,14) in the call to LVI->getConstantRange in processBinOp. processCmp skips calling LVI for the select's icmp because the input isn't in the same basic block and isn't a phi. And the call to LVI->getConstant for the select in processSelect didn't return a constant. I think this is because the code executed for getConstant doesn't handle icmp even when it can prove the input is in a constant range. I tried removing the local value check in processCmp so that getPredicateAt would called, but that didn't help either.

Best,
- Stefanos

Στις Δευ, 6 Απρ 2020 στις 3:10 π.μ., ο/η Craig Topper <craig.topper@gmail.com> έγραψε:

Adding a nuw to the add -8 is incorrect. From the perspective of the unsigned math, -8 is treated a very large positive number. The input to the add is \[8,13) and adding a large positive number to it wraps around past 0\. So that is guaranteed unsigned wrap. On the other hand, a sub nuw 8 would be correct.

\~Craig

On Sun, Apr 5, 2020 at 3:27 PM Stefanos Baziotis via llvm-dev <llvm-dev@lists.llvm.org> wrote:

Thanks, I didn't know that! Indeed, it's instruction combine that does the job.

- Stefanos

Στις Δευ, 6 Απρ 2020 στις 12:38 π.μ., ο/η Florian Hahn <florian\_hahn@apple.com> έγραψε:

\> On Apr 5, 2020, at 22:20, Stefanos Baziotis <stefanos.baziotis@gmail.com> wrote:
\>
\> > Any idea about how the compiler could remove the lshr and use a add -16?
\> Actually, I just figured that doing this test is like solving this:
\>
\> 8 <= x/2 <= 13
\> 16 <= x <= 26
\> 0 <= x - 16 <= 10 => 0 <= x < 11
\> The left part is know since it's unsigned
\> The right part could be done x <= 11 => x < 12 because it's actually an integer division.
\> Wow... I would be really happy to know what pass does that.

I’d guess a combination of instcombine rules together with some other transforms. You could probably use \`-print-after-all\` (\`clang -mllvm -print-after-all\` if you are using clang) to track down the relevant passes/steps.

\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_\_
LLVM Developers mailing list
llvm-dev@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev