[LSR] Check for signed overflow in NarrowSearchSpaceByDetectingSupersets.

[fhahn]

Summary

We are adding a sign extended IR value to an int64_t, which can cause
signed overflows, as in the attached test case, where we have a formula
with BaseOffset = -1 and a constant with numeric_limits<int64_t>::min().

If the addition would overflow, skip the simplification for this
formula. Note that the target triple is required to trigger the failure.

[fhahn]

Looks like at other places we cast one operand to uint64_t and then assign the result to int64_t. Given that the operations reflect formulas based on IR types, I guess that's valid? The LangRef does not explicitly mention the behavior of signed overflow for add & co, but given that it is using 2's complement, it should be defined, right?

[efriedma]

It looks like LSR doesn't deal with this sort of issue consistently... some places we try to overflow-check arithmetic on the offset, and others we use wrapping arithmetic.

What should happen, really, is that each formula includes a bitwidth, and all arithmetic involving that formula use arithmetic that wraps at that bitwidth (like an APInt). Otherwise it's not really clear what the computation actually means.

[fhahn]

In D59211#1424945, @efriedma wrote:

It looks like LSR doesn't deal with this sort of issue consistently... some places we try to overflow-check arithmetic on the offset, and others we use wrapping arithmetic.

What should happen, really, is that each formula includes a bitwidth, and all arithmetic involving that formula use arithmetic that wraps at that bitwidth (like an APInt). Otherwise it's not really clear what the computation actually means.

Right, that makes sense! I guess that would consistently address the signed overflows and potentially codegen errors by wrong wrapping/truncating. I'm happy to look into that. Unfortunately we are this UBSan failure internally, do you think it would be OK to get this in (either as is or with wrapping arithmetic) until the issue is addressed consistently?

[efriedma]

It's probably okay to preserve the current behavior here with an explicit uint64_t cast, for now, maybe with a FIXME.

[fhahn]

use wrapping arithmetic

[efriedma]

LGTM

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp

 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/ScalarEvolutionNormalization.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/OperandTraits.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Use.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Casting.h"
+#include "llvm/Support/CheckedArithmetic.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <cstdlib>
 #include <iterator>
 #include <limits>
-#include <numeric>
 #include <map>
+#include <numeric>
 #include <utility>
 
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-reduce"
 
 /// MaxIVUsers is an arbitrary threshold that provides an early opportunity for
 /// bail out. This threshold is far beyond the number of users that LSR can
for (size_t LUIdx = 0, NumUses = Uses.size(); LUIdx != NumUses; ++LUIdx) {
         Formula &F = LU.Formulae[i];
         // Look for a formula with a constant or GV in a register. If the use
         // also has a formula with that same value in an immediate field,
         // delete the one that uses a register.
         for (SmallVectorImpl<const SCEV *>::const_iterator
              I = F.BaseRegs.begin(), E = F.BaseRegs.end(); I != E; ++I) {
           if (const SCEVConstant *C = dyn_cast<SCEVConstant>(*I)) {
             Formula NewF = F;
-            NewF.BaseOffset += C->getValue()->getSExtValue();
+
+            Optional<int64_t> MaybeResult =
+                checkedAdd(NewF.BaseOffset, C->getValue()->getSExtValue());
+            // Skip simplification if addition overflows.
+            if (!MaybeResult)
+              continue;
+
+            NewF.BaseOffset = *MaybeResult;
             NewF.BaseRegs.erase(NewF.BaseRegs.begin() +
                                 (I - F.BaseRegs.begin()));
             if (LU.HasFormulaWithSameRegs(NewF)) {
               LLVM_DEBUG(dbgs() << "  Deleting "; F.print(dbgs());
                          dbgs() << '\n');
               LU.DeleteFormula(F);
               --i;
               --e;

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

+; RUN: opt -lsr-complexity-limit=50 -loop-reduce -S %s | FileCheck %s
+
+target triple = "x86_64-apple-macosx10.14.0"
+target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
+
+; CHECK: overflow1
+define void @overflow1(i64 %a) {
+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
+}