[LSR] Fix signed overflow in GenerateCrossUseConstantOffsets.

[fhahn]

Summary

For the attached test case, unchecked addition of immediate starts and
ends overflows, as they can be arbitrary i64 constants.

[fhahn]

Use wrapping arithmetic

[fhahn]

Another case similar to D59211

[fhahn]

Ping. This applies the same solution as D59211 to a different case.

[efriedma]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

4146

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.

[fhahn]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

4146

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.

[efriedma]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

4146

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.)

[fhahn]

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.

[efriedma]

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

4148

Are you sure this formula is right? Alive says it doesn't work correctly for signed values: https://rise4fun.com/Alive/E3V.

[fhahn]

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

[fhahn]

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

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

for (ImmMapTy::const_iterator J = Imms.begin(), JE = Imms.end();
           UsedByIndicesMap[Reg].count() == 1) {
         LLVM_DEBUG(dbgs() << "Skipping cross-use reuse for " << *OrigReg
                           << '\n');
         continue;
       }
 
       // Conservatively examine offsets between this orig reg a few selected
       // other orig regs.
+      int64_t First = Imms.begin()->first;
+      int64_t Last = std::prev(Imms.end())->first;
+      // Compute (First + Last)  / 2 without overflow using the fact that
+      // First + Last = 2 * (First + Last) + (First ^ Last).
+      int64_t Avg = (First & Last) + ((First ^ Last) >> 1);
+      // If the result is negative and First is odd and Last even (or vice versa),
+      // we rounded towards -inf. Add 1 in that case, to round towards 0.
+      Avg = Avg + ((First ^ Last) & ((uint64_t)Avg >> 63));
       ImmMapTy::const_iterator OtherImms[] = {
           Imms.begin(), std::prev(Imms.end()),
-        Imms.lower_bound((Imms.begin()->first + std::prev(Imms.end())->first) /
-                         2)
-      };
+         Imms.lower_bound(Avg)};
       for (size_t i = 0, e = array_lengthof(OtherImms); i != e; ++i) {
         ImmMapTy::const_iterator M = OtherImms[i];
         if (M == J || M == JE) continue;
 
         // Compute the difference between the two.
         int64_t Imm = (uint64_t)JImm - M->first;
         for (unsigned LUIdx : UsedByIndices.set_bits())
           // Make a memo of this use, offset, and register tuple.
           if (UniqueItems.insert(std::make_pair(LUIdx, Imm)).second)
             WorkItems.push_back(WorkItem(LUIdx, Imm, OrigReg));

llvm/test/Transforms/LoopStrengthReduce/lsr-overflow.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -lsr-complexity-limit=50 -loop-reduce -S %s | FileCheck %s
+
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @overflow1(i64 %a) {
+; CHECK-LABEL: @overflow1(
+; CHECK-NEXT:  bb:
+; CHECK-NEXT:    [[TMP0:%.*]] = add i64 [[A:%.*]], -1
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[A]], -9223372036854775808
+; CHECK-NEXT:    br label [[BB1:%.*]]
+; CHECK:       bb1:
+; CHECK-NEXT:    [[LSR_IV1:%.*]] = phi i64 [ [[LSR_IV_NEXT2:%.*]], [[BB1]] ], [ [[TMP1]], [[BB:%.*]] ]
+; CHECK-NEXT:    [[LSR_IV:%.*]] = phi i64 [ [[LSR_IV_NEXT:%.*]], [[BB1]] ], [ [[TMP0]], [[BB]] ]
+; CHECK-NEXT:    [[TMP4:%.*]] = icmp ne i64 [[LSR_IV1]], 0
+; CHECK-NEXT:    [[TMP5:%.*]] = and i1 [[TMP4]], true
+; CHECK-NEXT:    [[LSR_IV_NEXT]] = add i64 [[LSR_IV]], 1
+; CHECK-NEXT:    [[LSR_IV_NEXT2]] = add i64 [[LSR_IV1]], 1
+; CHECK-NEXT:    br i1 [[TMP5]], label [[BB1]], label [[BB7:%.*]]
+; CHECK:       bb7:
+; CHECK-NEXT:    [[TMP9:%.*]] = and i64 [[LSR_IV_NEXT]], 1
+; CHECK-NEXT:    [[TMP10:%.*]] = icmp eq i64 [[TMP9]], 0
+; CHECK-NEXT:    unreachable
+;
+bb:
+  br label %bb1
+
+bb1:                                              ; preds = %bb1, %bb
+  %tmp = phi i64 [ %a, %bb ], [ %tmp6, %bb1 ]
+  %tmp4 = icmp ne i64 %tmp, -9223372036854775808
+  %tmp5 = and i1 %tmp4, 1
+  %tmp6 = add i64 %tmp, 1
+  br i1 %tmp5, label %bb1, label %bb7
+
+bb7:                                              ; preds = %bb1
+  %tmp9 = and i64 %tmp, 1
+  %tmp10 = icmp eq i64 %tmp9, 0
+  unreachable
+}