While this is useful in its own right, it is really intended to support

a subsequent change.

# Details

- Reviewers
reames majnemer atrick nlewycky hfinkel - Commits
- rG96709c485431: [SCEV] Reapply 'Exploit A < B => (A+K) < (B+K) when possible'

rGfdec9deb1333: [SCEV] Exploit A < B => (A+K) < (B+K) when possible

rL248637: [SCEV] Reapply 'Exploit A < B => (A+K) < (B+K) when possible'

rL248606: [SCEV] Exploit A < B => (A+K) < (B+K) when possible

# Diff Detail

- Repository
- rL LLVM

### Event Timeline

lib/Analysis/ScalarEvolution.cpp | ||
---|---|---|

7369–7372 ↗ | (On Diff #35055) | Let's say I have the following: A = 0x7FFFFFFF B = 0x7FFFBC80 In this case, However, this results in the following: A+1 = 0x80000000 B+1 = 0x7FFFBC81 Thus the claim is made false, However, the claim is valid if we can prove that I'm no SCEV expert but it seems to me that the code is doing the right thing, is it only the comment that needs adjustment? |

Hi Sanjoy,

I'm no scev expert, so I'm most probably missing something here: why limit ourselves to "A < B => (A+1) < (B+1)" when "A < B => (A+Cst) < (B+Cst)" also holds --- assuming there are no overflows ?

Thanks,

Arnaud

I'm no scev expert, so I'm most probably missing something here: why

limit ourselves to "A < B => (A+1) < (B+1)" when "A < B => (A+Cst) <

(B+Cst)" also holds --- assuming there are no overflows ?

You're right, on no overflow, "A < B => (A+Cst) < (B+Cst)" (with the caveat that Cst

be positive if the comparison is signed).

I was initially working with "(A+1) < (B+1)" because that's the case

that had shown up, and hence that was the case I cared about. But

you're right -- given handing arbitrary constants is not much more

work, we should be handling those. I've updated the patch to do the

same (uploading shortly).

Thanks,

Arnaud

lib/Analysis/ScalarEvolution.cpp | ||
---|---|---|

7369–7372 ↗ | (On Diff #35055) | As discussed on IRC, the |

- Address Hal's review.
- Generalize the transform a little bit -- A s< B => A + C s< B + C if B s< INT_MIN - C even if C is negative. Add a test case for the same.

lib/Analysis/ScalarEvolution.cpp | ||
---|---|---|

7367 ↗ | (On Diff #35576) | There is actually a simpler proof for the signed case (I'll update the The proof hinges on We'll also assume the unsigned variant of the implication, ( A s< B s< INT_MIN - C <=> (A + INT_MIN) u< (B + INT_MIN) u< -C [ using (1) ] <=> (A + INT_MIN + C) u< (B + INT_MIN + C) [ using (2) ] <=> (A + INT_MIN + C + INT_MIN) s< (B + INT_MIN + C + INT_MIN) [ using (1) ] <=> A + C s< B + C |

- Clarify comments a bit more and fix typos in comments. Only comments changed in this update.