For the attached test case, unchecked addition of immediate starts and

ends overflows, as they can be arbitrary i64 constants.

# Details

# Diff Detail

- Repository
- rL LLVM

### Event Timeline

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp | ||
---|---|---|

4152 ↗ | (On Diff #190143) | This code is trying to compute (x+y)/2. Mathematically, this can't overflow, so this shouldn't require a bitwidth to produce a meaningful result. |

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp | ||
---|---|---|

4152 ↗ | (On Diff #190143) | Unless I am missing something, the cast addresses a potential overflow for the x + y part of the expression. Running the attached test with opt+ubsan crashes here. |

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp | ||
---|---|---|

4152 ↗ | (On Diff #190143) | Sorry, I guess I wasn't clear. By "mathematically, this can't overflow", I meant that if x and y are in the range [INT_MIN, INT_MAX], (x+y)/2 is also in the range [INT_MIN, INT_MAX]. If you try to compute the result by just writing "(x+y)/2" in C, sure, it'll overflow, but you can rewrite the formula some other way. (Not sure what the most efficient way to write that in C is, off the top of my head.) |

Thanks Eli, I did not realize that there are quite efficient ways to compute the

expressions other than splitting it up and dealing with the even/uneven cases

with modulo.

I did some digging online and updated the patch with an approach that should be

quite efficient.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp | ||
---|---|---|

4142 ↗ | (On Diff #192202) | Are you sure this formula is right? Alive says it doesn't work correctly for signed values: https://rise4fun.com/Alive/E3V. |

Modeling round-to-zero behavior correctly for all inputs is a bit tricky. I'll revisit it when I have more time

Fix calculation: use signed right shift to divide by 2 with round to -inf and

add 1 for negative results where one value is odd and the other even to get

round to 0 behavior. Proof: https://rise4fun.com/Alive/Plqc