[BasicAA] Remove misleading overflow check

[nikic]

Summary

GEP decomposition currently checks whether the multiplication of the linear expression offset and GEP scale overflows. However, if everything else works correctly, this overflow check is both unnecessary and dangerously misleading. While it will avoid an overflow in Scale * Offset in particular, other parts of the calculation (including those on dynamic values) may still overflow. The code working on the decomposed GEPs is responsible for ensuring that it remains correct in the presence of overflow. D112611 fixes the last issue of that kind that I'm aware of (in fact, the overflow check was originally introduced to work around precisely that issue).

llvm/lib/Analysis/BasicAliasAnalysis.cpp

for (User::const_op_iterator I = GEPOp->op_begin() + 1, E = GEPOp->op_end();
       unsigned Width = Index->getType()->getIntegerBitWidth();
       unsigned SExtBits = PointerSize > Width ? PointerSize - Width : 0;
       unsigned TruncBits = PointerSize < Width ? Width - PointerSize : 0;
       LinearExpression LE = GetLinearExpression(
           CastedValue(Index, 0, SExtBits, TruncBits), DL, 0, AC, DT);
 
       // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale.
       // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale.
-
-      // It can be the case that, even through C1*V+C2 does not overflow for
-      // relevant values of V, (C2*Scale) can overflow. In that case, we cannot
-      // decompose the expression in this way.
-      //
-      // FIXME: C1*Scale and the other operations in the decomposed
-      // (C1*Scale)*V+C2*Scale can also overflow. We should check for this
-      // possibility.
-      bool Overflow;
-      APInt ScaledOffset = LE.Offset.sextOrTrunc(MaxPointerSize)
-                           .smul_ov(Scale, Overflow);
-      if (Overflow) {
-        LE = LinearExpression(CastedValue(Index, 0, SExtBits, TruncBits));
-      } else {
-        Decomposed.Offset += ScaledOffset;
-        Scale *= LE.Scale.sextOrTrunc(MaxPointerSize);
-      }
+      Decomposed.Offset += LE.Offset.sextOrTrunc(MaxPointerSize) * Scale;
 
       // If we already had an occurrence of this index variable, merge this
       // scale into it.  For example, we want to handle:
       //   A[x][x] -> x*16 + x*4 -> x*20
       // This also ensures that 'x' only appears in the index list once.
       for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) {
         if (Decomposed.VarIndices[i].Val.V == LE.Val.V &&
             Decomposed.VarIndices[i].Val.hasSameCastsAs(LE.Val)) {