[clang][Interp] Implement left and right shifts

[tbaeder]

Summary

Add a test case based on test/SemaCXX/shift.cpp.

[aaron.ballman]

clang/lib/AST/Interp/Interp.h

1274–1275

This doesn't seem to match: https://eel.is/c++draft/expr.shift#1.sentence-4

1274–1276

Why do Shr and Shl check for a negative shift amount to issue a diagnostic but we check for signed in ShiftLeft to issue a diagnostic? (I would have expected the checks to all live in the same place.)

[shafik]

clang/test/AST/Interp/shifts.cpp

58

This is not correct, the operands go through integral promotions first and the result is the promoted type of the left operand see dcl.shift p1.

Also see godbolt: https://godbolt.org/z/7qzKjojMb

71

A negative left operand was made well-formed in C++20 I believe see godbolt: https://godbolt.org/z/7qzKjojMb

My reference from above for expr.shift/p1 also applies.

Although a negative right operand is still UB.

Also note shifting into the sign bit was made well-formed in C++11: https://stackoverflow.com/questions/19593938/is-left-shifting-a-negative-integer-undefined-behavior-in-c11#comment29091986_19593938

[shafik]

clang/test/AST/Interp/shifts.cpp

71

Typo, shifting into the sign bit was made well-formed after C++11

[tbaeder]

clang/lib/AST/Interp/Interp.h

1274–1276

This was already implemented and I tried to keep as much code as possible, but I'll change that strategy ;)

clang/test/AST/Interp/shifts.cpp

58

Hmm, this is copy-pasted from test/SemaCXX/shift.cpp.

71

This is in line with the test, isn't it? The warning is only for cxx17, the c++20 tests don't expect any output.

[tbaeder]

Excuse the code duplication here, I'll get rid of it as soon as we all agree that the functionality is correct.

[aaron.ballman]

clang/test/AST/Interp/shifts.cpp

58

FWIW, I agree with Shafik -- you can also see the casts in the AST: https://godbolt.org/z/97dqr1TEs

71

Also worth keeping in mind: C and C++ differ here.

C2x 6.5.7p4: "... If E1 has a signed type and nonnegative value, and E1 × 2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined."

[shafik]

clang/test/AST/Interp/shifts.cpp

58

This weird, you can see this is indeed valid in a constant expression: https://godbolt.org/z/W33janMxv

but we do obtain that diagnostic and I think I see what it is saying, that the result type is 8bit but the shift is larger than that type even though the operation is being done on the promoted type. I feel like the diagnostic is not great but could be improved to make it better.

wdyt @aaron.ballman

71

Apologies, I missed the diagnostic was only firing for C++17.

[aaron.ballman]

clang/test/AST/Interp/shifts.cpp

58

This weird, you can see this is indeed valid in a constant expression: https://godbolt.org/z/W33janMxv

Yes, because of the integral promotion of c to int.

but we do obtain that diagnostic and I think I see what it is saying, that the result type is 8bit but the shift is larger than that type even though the operation is being done on the promoted type. I feel like the diagnostic is not great but could be improved to make it better.

I think it's telling the programmer that something strange is happening here. Yes, it's well-defined because of integral promotions, but it still looks like suspect code. We could say "width of the unpromoted type" but that might make the diagnostic more confusing for non-language lawyer folks.

[shafik]

clang/test/AST/Interp/shifts.cpp

58

but we do obtain that diagnostic and I think I see what it is saying, that the result type is 8bit but the shift is larger than that type even though the operation is being done on the promoted type. I feel like the diagnostic is not great but could be improved to make it better.

I think it's telling the programmer that something strange is happening here. Yes, it's well-defined because of integral promotions, but it still looks like suspect code. We could say "width of the unpromoted type" but that might make the diagnostic more confusing for non-language lawyer folks.

I am bothered that the same diagnostic message represents two cases 1) a case which is undefined behavior 2) a case which may be surprising but well defined.

[aaron.ballman]

clang/test/AST/Interp/shifts.cpp

58

I am bothered that the same diagnostic message represents two cases 1) a case which is undefined behavior 2) a case which may be surprising but well defined.

That's reasonable, but short of users complaining about significant false positives or asking us to split the situations into two so they can control the difference, I don't think there's anything to be fixed here. The goal of the diagnostic isn't to point out only the UB cases, it's to point out "you're doing something deeply weird, are you sure you mean to do that?" which happens to cover the UB cases too.

[tbaeder]

Added suport for >>= and <<= as well so the test cases for those can be enabled.

[tbaeder]

clang/test/AST/Interp/shifts.cpp

58

In any case, I've enabled those test cases and the output with the new interpreter is the same one we get with the current interpreter.

[aaron.ballman]

clang/lib/AST/Interp/Interp.h

1291–1305

Should we factor this logic out into a common helper since it's the same between shl and shr? (It could be done as an NFC commit after we land this, too, I don't feel super strongly about it.)

clang/test/AST/Interp/shifts.cpp

6

You can get rid of this entirely and use __CHAR_BIT__ instead.

7

You can get rid of this entirely and use __INT_WIDTH__ instead.

8

No need for this define at all, but fine to leave if you want it for parity with INT_MIN.

116

I'd also appreciate tests showing:

constexpr int i1 = 1 << -1; // ill-formed due to UB
constexpr int i2 = 1 << (WORD_BIT + 1); // ill-formed due to UB
constexpr char c = 1;
constexpr int i3 = c << (CHAR_BIT + 1); // Not ill-formed

[tbaeder]

clang/lib/AST/Interp/Interp.h

1291–1305

Yes, this is what I meant in my earlier comment with "Excuse the code duplication here"

[aaron.ballman]

LGTM!

[shafik]

LGTM

clang/lib/AST/Interp/ByteCodeExprGen.cpp

if (DiscardResult)
       return this->emitStorePop(*T, BO);
     return this->emitStore(*T, BO);
   case BO_And:
     return Discard(this->emitBitAnd(*T, BO));
   case BO_Or:
     return Discard(this->emitBitOr(*T, BO));
   case BO_Xor:
     return Discard(this->emitBitXor(*T, BO));
+  case BO_Shl:
+    return Discard(this->emitShl(*LT, *RT, BO));
+  case BO_Shr:
+    return Discard(this->emitShr(*LT, *RT, BO));
   case BO_LAnd:
   case BO_LOr:
   default:
     return this->bail(BO);
   }
 
   llvm_unreachable("Unhandled binary op");
 }
case BO_SubAssign:
     if (!this->emitSub(*LT, E))
       return false;
     break;
 
   case BO_MulAssign:
   case BO_DivAssign:
   case BO_RemAssign:
   case BO_ShlAssign:
+    if (!this->emitShl(*LT, *RT, E))
+      return false;
+    break;
   case BO_ShrAssign:
+    if (!this->emitShr(*LT, *RT, E))
+      return false;
+    break;
   case BO_AndAssign:
   case BO_XorAssign:
   case BO_OrAssign:
   default:
     llvm_unreachable("Unimplemented compound assign operator");
   }
 
   // And store the result in LHS.

clang/lib/AST/Interp/Interp.h

inline bool This(InterpState &S, CodePtr OpPC) {
   S.Stk.push<Pointer>(This);
   return true;
 }
 
 //===----------------------------------------------------------------------===//
 // Shr, Shl
 //===----------------------------------------------------------------------===//
 
-template <PrimType TR, PrimType TL, class T = typename PrimConv<TR>::T>
-unsigned Trunc(InterpState &S, CodePtr OpPC, unsigned Bits, const T &V) {
+template <PrimType NameL, PrimType NameR>
+inline bool Shr(InterpState &S, CodePtr OpPC) {
+  using LT = typename PrimConv<NameL>::T;
+  using RT = typename PrimConv<NameR>::T;
+  const auto &RHS = S.Stk.pop<RT>();
+  const auto &LHS = S.Stk.pop<LT>();
+  const unsigned Bits = LHS.bitWidth();
+
+  if (RHS.isNegative()) {
+    const SourceInfo &Loc = S.Current->getSource(OpPC);
+    S.CCEDiag(Loc, diag::note_constexpr_negative_shift) << RHS.toAPSInt();
+    return false;
+  }
+
   // C++11 [expr.shift]p1: Shift width must be less than the bit width of
   // the shifted type.
-  if (Bits > 1 && V >= T::from(Bits, V.bitWidth())) {
+  if (Bits > 1 && RHS >= RT::from(Bits, RHS.bitWidth())) {
     const Expr *E = S.Current->getExpr(OpPC);
-    const APSInt Val = V.toAPSInt();
+    const APSInt Val = RHS.toAPSInt();
     QualType Ty = E->getType();
     S.CCEDiag(E, diag::note_constexpr_large_shift) << Val << Ty << Bits;
-    return Bits;
-  } else {
-    return static_cast<unsigned>(V);
-  }
-}
-
-template <PrimType TL, PrimType TR, typename T = typename PrimConv<TL>::T>
-inline bool ShiftRight(InterpState &S, CodePtr OpPC, const T &V, unsigned RHS) {
-  if (RHS >= V.bitWidth()) {
-    S.Stk.push<T>(T::from(0, V.bitWidth()));
-  } else {
-    S.Stk.push<T>(T::from(V >> RHS, V.bitWidth()));
-  }
-  return true;
-}
-
-template <PrimType TL, PrimType TR, typename T = typename PrimConv<TL>::T>
-inline bool ShiftLeft(InterpState &S, CodePtr OpPC, const T &V, unsigned RHS) {
-  if (V.isSigned() && !S.getLangOpts().CPlusPlus20) {
-    // C++11 [expr.shift]p2: A signed left shift must have a non-negative
-    // operand, and must not overflow the corresponding unsigned type.
-    // C++2a [expr.shift]p2: E1 << E2 is the unique value congruent to
-    // E1 x 2^E2 module 2^N.
-    if (V.isNegative()) {
-      const Expr *E = S.Current->getExpr(OpPC);
-      S.CCEDiag(E, diag::note_constexpr_lshift_of_negative) << V.toAPSInt();
-    } else if (V.countLeadingZeros() < RHS) {
-      S.CCEDiag(S.Current->getExpr(OpPC), diag::note_constexpr_lshift_discards);
-    }
+    return false;
   }
 
-  if (V.bitWidth() == 1) {
-    S.Stk.push<T>(V);
-  } else if (RHS >= V.bitWidth()) {
-    S.Stk.push<T>(T::from(0, V.bitWidth()));
-  } else {
-    S.Stk.push<T>(T::from(V.toUnsigned() << RHS, V.bitWidth()));
-  }
+  unsigned URHS = static_cast<unsigned>(RHS);
+  S.Stk.push<LT>(LT::from(static_cast<unsigned>(LHS) >> URHS, LHS.bitWidth()));
   return true;
 }
 
-template <PrimType TL, PrimType TR>
-inline bool Shr(InterpState &S, CodePtr OpPC) {
-  const auto &RHS = S.Stk.pop<typename PrimConv<TR>::T>();
-  const auto &LHS = S.Stk.pop<typename PrimConv<TL>::T>();
+template <PrimType NameL, PrimType NameR>
+inline bool Shl(InterpState &S, CodePtr OpPC) {
+  using LT = typename PrimConv<NameL>::T;
+  using RT = typename PrimConv<NameR>::T;
+  const auto &RHS = S.Stk.pop<RT>();
+  const auto &LHS = S.Stk.pop<LT>();
   const unsigned Bits = LHS.bitWidth();
 
-  if (RHS.isSigned() && RHS.isNegative()) {
+  if (RHS.isNegative()) {
     const SourceInfo &Loc = S.Current->getSource(OpPC);
     S.CCEDiag(Loc, diag::note_constexpr_negative_shift) << RHS.toAPSInt();
-    return ShiftLeft<TL, TR>(S, OpPC, LHS, Trunc<TR, TL>(S, OpPC, Bits, -RHS));
-  } else {
-    return ShiftRight<TL, TR>(S, OpPC, LHS, Trunc<TR, TL>(S, OpPC, Bits, RHS));
+    return false;
   }
+
+  // C++11 [expr.shift]p1: Shift width must be less than the bit width of
+  // the shifted type.
+  if (Bits > 1 && RHS >= RT::from(Bits, RHS.bitWidth())) {
+    const Expr *E = S.Current->getExpr(OpPC);
+    const APSInt Val = RHS.toAPSInt();
+    QualType Ty = E->getType();
+    S.CCEDiag(E, diag::note_constexpr_large_shift) << Val << Ty << Bits;
+    return false;
   }
 
-template <PrimType TL, PrimType TR>
-inline bool Shl(InterpState &S, CodePtr OpPC) {
-  const auto &RHS = S.Stk.pop<typename PrimConv<TR>::T>();
-  const auto &LHS = S.Stk.pop<typename PrimConv<TL>::T>();
-  const unsigned Bits = LHS.bitWidth();
+  unsigned URHS = static_cast<unsigned>(RHS);
+  S.Stk.push<LT>(LT::from(static_cast<unsigned>(LHS) << URHS, LHS.bitWidth()));
 
-  if (RHS.isSigned() && RHS.isNegative()) {
-    const SourceInfo &Loc = S.Current->getSource(OpPC);
-    S.CCEDiag(Loc, diag::note_constexpr_negative_shift) << RHS.toAPSInt();
-    return ShiftRight<TL, TR>(S, OpPC, LHS, Trunc<TR, TL>(S, OpPC, Bits, -RHS));
-  } else {
-    return ShiftLeft<TL, TR>(S, OpPC, LHS, Trunc<TR, TL>(S, OpPC, Bits, RHS));
-  }
+  return true;
 }
 
 //===----------------------------------------------------------------------===//
 // NoRet
 //===----------------------------------------------------------------------===//
 
 inline bool NoRet(InterpState &S, CodePtr OpPC) {
   SourceLocation EndLoc = S.Current->getCallee()->getEndLoc();

clang/lib/AST/Interp/Opcodes.td

 def Sub  : AluOpcode;
 def Subf : FloatOpcode;
 def Mul  : AluOpcode;
 def Mulf : FloatOpcode;
 def Rem  : IntegerOpcode;
 def Div  : IntegerOpcode;
 def Divf : FloatOpcode;
 
+def Shl : Opcode {
+  let Types = [IntegerTypeClass, IntegerTypeClass];
+  let HasGroup = 1;
+}
+
+def Shr : Opcode {
+  let Types = [IntegerTypeClass, IntegerTypeClass];
+  let HasGroup = 1;
+}
+
 def BitAnd : IntegerOpcode;
 def BitOr : IntegerOpcode;
 def BitXor : IntegerOpcode;
 
 //===----------------------------------------------------------------------===//
 // Unary operators.
 //===----------------------------------------------------------------------===//
 

clang/test/AST/Interp/shifts.cpp

+// RUN: %clang_cc1 -fexperimental-new-constant-interpreter -std=c++20 -verify %s
+// RUN: %clang_cc1 -fexperimental-new-constant-interpreter -std=c++17 -verify=cxx17 %s
+// RUN: %clang_cc1 -std=c++20 -verify=ref %s
+// RUN: %clang_cc1 -std=c++17 -verify=ref-cxx17 %s
+
+#define CHAR_BIT (sizeof(char) * 8)
+#define WORD_BIT (sizeof(int) * 8)
+#define INT_MAX (__INT_MAX__)
+#define INT_MIN (~__INT_MAX__)
+
+
+namespace shifts {
+  constexpr void test() { // ref-error {{constexpr function never produces a constant expression}} \
+                          // ref-cxx17-error {{constexpr function never produces a constant expression}}
+
+    char c; // cxx17-warning {{uninitialized variable}} \
+            // ref-cxx17-warning {{uninitialized variable}}
+
+    c = 0 << 0;
+    c = 0 << 1;
+    c = 1 << 0;
+    c = 1 << -0;
+    c = 1 >> -0;
+    c = 1 << -1; // expected-warning {{shift count is negative}} \
+                 // cxx17-warning {{shift count is negative}} \
+                 // ref-warning {{shift count is negative}} \
+                 // ref-note {{negative shift count -1}} \
+                 // ref-cxx17-warning {{shift count is negative}} \
+                 // ref-cxx17-note {{negative shift count -1}}
+
+    c = 1 >> -1; // expected-warning {{shift count is negative}} \
+                 // cxx17-warning {{shift count is negative}} \
+                 // ref-warning {{shift count is negative}} \
+                 // ref-cxx17-warning {{shift count is negative}}
+    c = 1 << (unsigned)-1; // expected-warning {{shift count >= width of type}} \
+                           // FIXME: 'implicit conversion' warning missing in the new interpreter. \
+                           // cxx17-warning {{shift count >= width of type}} \
+                           // ref-warning {{shift count >= width of type}} \
+                           // ref-warning {{implicit conversion}} \
+                           // ref-cxx17-warning {{shift count >= width of type}} \
+                           // ref-cxx17-warning {{implicit conversion}}
+    c = 1 >> (unsigned)-1; // expected-warning {{shift count >= width of type}} \
+                           // cxx17-warning {{shift count >= width of type}} \
+                           // ref-warning {{shift count >= width of type}} \
+                           // ref-cxx17-warning {{shift count >= width of type}}
+    c = 1 << c;
+    c <<= 0;
+    c >>= 0;
+    c <<= 1;
+    c >>= 1;
+    c <<= -1; // expected-warning {{shift count is negative}} \
+              // cxx17-warning {{shift count is negative}} \
+              // ref-warning {{shift count is negative}} \
+              // ref-cxx17-warning {{shift count is negative}}
+    c >>= -1; // expected-warning {{shift count is negative}} \
+              // cxx17-warning {{shift count is negative}} \
+              // ref-warning {{shift count is negative}} \
+              // ref-cxx17-warning {{shift count is negative}}
+    c <<= 999999; // expected-warning {{shift count >= width of type}} \
+                  // cxx17-warning {{shift count >= width of type}} \
+                  // ref-warning {{shift count >= width of type}} \
+                  // ref-cxx17-warning {{shift count >= width of type}}
+    c >>= 999999; // expected-warning {{shift count >= width of type}} \
+                  // cxx17-warning {{shift count >= width of type}} \
+                  // ref-warning {{shift count >= width of type}} \
+                  // ref-cxx17-warning {{shift count >= width of type}}
+    c <<= CHAR_BIT; // expected-warning {{shift count >= width of type}} \
+                    // cxx17-warning {{shift count >= width of type}} \
+                    // ref-warning {{shift count >= width of type}} \
+                    // ref-cxx17-warning {{shift count >= width of type}}
+    c >>= CHAR_BIT; // expected-warning {{shift count >= width of type}} \
+                    // cxx17-warning {{shift count >= width of type}} \
+                    // ref-warning {{shift count >= width of type}} \
+                    // ref-cxx17-warning {{shift count >= width of type}}
+    c <<= CHAR_BIT+1; // expected-warning {{shift count >= width of type}} \
+                      // cxx17-warning {{shift count >= width of type}} \
+                      // ref-warning {{shift count >= width of type}} \
+                      // ref-cxx17-warning {{shift count >= width of type}}
+    c >>= CHAR_BIT+1; // expected-warning {{shift count >= width of type}} \
+                      // cxx17-warning {{shift count >= width of type}} \
+                      // ref-warning {{shift count >= width of type}} \
+                      // ref-cxx17-warning {{shift count >= width of type}}
+    (void)((long)c << CHAR_BIT);
+
+    int i; // cxx17-warning {{uninitialized variable}} \
+           // ref-cxx17-warning {{uninitialized variable}}
+    i = 1 << (WORD_BIT - 2);
+    i = 2 << (WORD_BIT - 1); // cxx17-warning {{bits to represent, but 'int' only has}} \
+                             // ref-cxx17-warning {{bits to represent, but 'int' only has}}
+    i = 1 << (WORD_BIT - 1); // cxx17-warning-not {{sets the sign bit of the shift expression}}
+    i = -1 << (WORD_BIT - 1); // cxx17-warning {{shifting a negative signed value is undefined}} \
+                              // ref-cxx17-warning {{shifting a negative signed value is undefined}}
+    i = -1 << 0; // cxx17-warning {{shifting a negative signed value is undefined}} \
+                 // ref-cxx17-warning {{shifting a negative signed value is undefined}}
+    i = 0 << (WORD_BIT - 1);
+    i = (char)1 << (WORD_BIT - 2);
+
+    unsigned u; // cxx17-warning {{uninitialized variable}} \
+                // ref-cxx17-warning {{uninitialized variable}}
+    u = 1U << (WORD_BIT - 1);
+    u = 5U << (WORD_BIT - 1);
+
+    long long int lli; // cxx17-warning {{uninitialized variable}} \
+                       // ref-cxx17-warning {{uninitialized variable}}
+    lli = INT_MIN << 2; // cxx17-warning {{shifting a negative signed value is undefined}} \
+                        // ref-cxx17-warning {{shifting a negative signed value is undefined}}
+    lli = 1LL << (sizeof(long long) * CHAR_BIT - 2);
+  }
+
+  static_assert(1 << 4 == 16, "");
+  constexpr unsigned m = 2 >> 1;
+  static_assert(m == 1, "");
+  constexpr unsigned char c = 0 << 8;
+  static_assert(c == 0, "");
+  static_assert(true << 1, "");
+  static_assert(1 << (WORD_BIT +1) == 0, "");  // expected-error {{not an integral constant expression}} \
+                                               // expected-note {{>= width of type 'int'}} \
+                                               // cxx17-error {{not an integral constant expression}} \
+                                               // cxx17-note {{>= width of type 'int'}} \
+                                               // ref-error {{not an integral constant expression}} \
+                                               // ref-note {{>= width of type 'int'}} \
+                                               // ref-cxx17-error {{not an integral constant expression}} \
+                                               // ref-cxx17-note {{>= width of type 'int'}}
+};