[clang][Interp] Implement rem opcode

[tbaeder]

Summary

Something easier to review I hope :)

Implement an opcode to get the remainder of the divison between LHS and RHS.

[erichkeane]

clang/lib/AST/Interp/Integral.h

213

Its a touch weird we return 'bool' in all these places, rather than an Optional<Integral>, right? Perhaps a refactor idea for a future patch.

clang/lib/AST/Interp/Interp.h

171

I get that we 'know' that rem doesn't have an error case, but it seems like a mistake to not check the return value... Perhaps an even better reason to use optional.

clang/lib/AST/Interp/Opcodes.td

57

Perhaps IntegralTypeClass, unless we expect floats to be here too?

62

What does "Alu" mean here?

[tbaeder]

clang/lib/AST/Interp/Integral.h

213

The really weird part is that false here suddenly means success, but I get your point. Does using Optional introduce any sort of performance penalty if this is being called a lot?

clang/lib/AST/Interp/Opcodes.td

57

Floats don't have to be in there I guess, but so far I'd say yes, they should be, because they are usable everywhere this class is used, afaik.

62

I didn't introduce the name but I assumed it comes from "arithmetic logical unit".

[erichkeane]

clang/lib/AST/Interp/Integral.h

213

'false' as success is actually pretty common in clang, we use that all over the place. I don't believe Optional would have any negative penalty, at least compared to a pointer-param?

clang/lib/AST/Interp/Opcodes.td

57

Ok then, thanks.

62

Ah! That could be. Makes sense.

[tbaeder]

clang/lib/AST/Interp/Integral.h

213

Yeah I know it's being used elsewhere in the codebase like this, but the all the AST visitors in the interpreter code return false for failure, so this is kinda confusing to me.

I'll note the refactoring for later.

[shafik]

clang/lib/AST/Interp/Interp.h

164

You also need to catch when the result is not representable e.g INT_MIN % -1

see CheckICE(...)

[tbaeder]

clang/lib/AST/Interp/Interp.h

173

Resultis unused in here now I guess. Also RHSInt

[aaron.ballman]

clang/test/AST/Interp/literals.cpp

161

Same question here as with div in regards to testing float behavior. (If you don't intend to support floats yet, make sure the commit message makes that clear.)

[tbaeder]

clang/test/AST/Interp/literals.cpp

161

Ultimately sure, but as of right now, floats aren't supported at all, so nope.

[aaron.ballman]

clang/test/AST/Interp/literals.cpp

161

Okay, fine by me.

In terms of the request by @shafik for INT_MIN % -1, keep in mind there are arbitrary width integer types like _BitInt, so you should add test coverage for code like:

constexpr _BitInt(7) Val = -64;
static_assert(Val % (_BitInt(7)-1, "");

and similar for division.

[tbaeder]

clang/test/AST/Interp/literals.cpp

161

I just checked, _BitInt doesn't work at all; it bails out when creating the Descriptor for the variable.

I already added the suggested note for the INT_MIN case in this patch, but I wasn't sure how to test is properly. Should I just use a fixed-width integer type and copy its _MIN value in the test?

[aaron.ballman]

clang/test/AST/Interp/literals.cpp

161

Ah, well that's something we should fix! :-D

I already added the suggested note for the INT_MIN case in this patch, but I wasn't sure how to test is properly. Should I just use a fixed-width integer type and copy its _MIN value in the test?

You should be able to use:

#define INT_MIN (~__INT_MAX__)

(and similar for the other MIN macros) which relies on the predefined macro instead of something from a header.

[tbaeder]

clang/test/AST/Interp/literals.cpp

161

Done, thanks. But I guess this now depends on https://reviews.llvm.org/D134804 since it uses ~ haha

[tbaeder]

clang/lib/AST/Interp/Interp.h

164

I added the check here some lines below; Is that alright? If so I'd add the same code to the div() implementation.

[aaron.ballman]

clang/lib/AST/Interp/Interp.h

164

Looks correct to me.

170

I really like how clear and generalized this predicate is!

[shafik]

LGTM

clang/lib/AST/Interp/ByteCodeExprGen.cpp

if (Optional<PrimType> T = classify(BO->getType())) {
     case BO_GE:
       return Discard(this->emitGE(*LT, BO));
     case BO_Sub:
       return Discard(this->emitSub(*T, BO));
     case BO_Add:
       return Discard(this->emitAdd(*T, BO));
     case BO_Mul:
       return Discard(this->emitMul(*T, BO));
+    case BO_Rem:
+      return Discard(this->emitRem(*T, BO));
     case BO_Assign:
       if (!this->emitStore(*T, BO))
         return false;
       return DiscardResult ? this->emitPopPtr(BO) : true;
     default:
       return this->bail(BO);
     }
   }

clang/lib/AST/Interp/Integral.h

public:
   static bool sub(Integral A, Integral B, unsigned OpBits, Integral *R) {
     return CheckSubUB(A.V, B.V, R->V);
   }
 
   static bool mul(Integral A, Integral B, unsigned OpBits, Integral *R) {
     return CheckMulUB(A.V, B.V, R->V);
   }
 
+  static bool rem(Integral A, Integral B, unsigned OpBits, Integral *R) {
+    *R = Integral(A.V % B.V);
+    return false;
+  }
+
   static bool neg(Integral A, Integral *R) {
     *R = -A;
     return false;
   }
 
 private:
   template <typename T> static bool CheckAddUB(T A, T B, T &R) {
     if constexpr (std::is_signed_v<T>) {

clang/lib/AST/Interp/Interp.h

 template <PrimType Name, class T = typename PrimConv<Name>::T>
 bool Mul(InterpState &S, CodePtr OpPC) {
   const T &RHS = S.Stk.pop<T>();
   const T &LHS = S.Stk.pop<T>();
   const unsigned Bits = RHS.bitWidth() * 2;
   return AddSubMulHelper<T, T::mul, std::multiplies>(S, OpPC, Bits, LHS, RHS);
 }
 
+/// 1) Pops the RHS from the stack.
+/// 2) Pops the LHS from the stack.
+/// 3) Pushes 'LHS % RHS' on the stack (the remainder of dividing LHS by RHS).
+template <PrimType Name, class T = typename PrimConv<Name>::T>
+bool Rem(InterpState &S, CodePtr OpPC) {
+  const T &RHS = S.Stk.pop<T>();
+  const T &LHS = S.Stk.pop<T>();
+
+  if (RHS.isZero()) {
+    const SourceInfo &Loc = S.Current->getSource(OpPC);
+    S.FFDiag(Loc, diag::note_expr_divide_by_zero);
+    return false;
+  }
+
+  if (LHS.isSigned() && LHS.isMin() && RHS.isNegative() && RHS.isMinusOne()) {
+    APSInt LHSInt = LHS.toAPSInt();
+    SmallString<32> Trunc;
+    (-LHSInt.extend(LHSInt.getBitWidth() + 1)).toString(Trunc, 10);
+    const SourceInfo &Loc = S.Current->getSource(OpPC);
+    const Expr *E = S.Current->getExpr(OpPC);
+    S.CCEDiag(Loc, diag::note_constexpr_overflow) << Trunc << E->getType();
+    return false;
+  }
+
+  const unsigned Bits = RHS.bitWidth() * 2;
+  T Result;
+  if (!T::rem(LHS, RHS, Bits, &Result)) {
+    S.Stk.push<T>(Result);
+    return true;
+  }
+  return false;
+}
+
 //===----------------------------------------------------------------------===//
 // Inv
 //===----------------------------------------------------------------------===//
 
 template <PrimType Name, class T = typename PrimConv<Name>::T>
 bool Inv(InterpState &S, CodePtr OpPC) {
   using BoolT = PrimConv<PT_Bool>::T;
   const T &Val = S.Stk.pop<T>();

clang/lib/AST/Interp/Opcodes.td

 //===----------------------------------------------------------------------===//
 // Classes of types instructions operate on.
 //===----------------------------------------------------------------------===//
 
 class TypeClass {
   list<Type> Types;
 }
 
-def AluTypeClass : TypeClass {
+def NumberTypeClass : TypeClass {
   let Types = [Sint8, Uint8, Sint16, Uint16, Sint32,
-               Uint32, Sint64, Uint64, Bool];
+               Uint32, Sint64, Uint64];
+}
+
+def AluTypeClass : TypeClass {
+  let Types = !listconcat(NumberTypeClass.Types, [Bool]);
 }
 
 def PtrTypeClass : TypeClass {
   let Types = [Ptr];
 }
 
 def BoolTypeClass : TypeClass {
   let Types = [Bool];

 //===----------------------------------------------------------------------===//
 // Binary operators.
 //===----------------------------------------------------------------------===//
 
 // [Real, Real] -> [Real]
 def Sub : AluOpcode;
 def Add : AluOpcode;
 def Mul : AluOpcode;
+def Rem : Opcode {
+  let Types = [NumberTypeClass];
+  let HasGroup = 1;
+}
 
 
 //===----------------------------------------------------------------------===//
 // Unary operators.
 //===----------------------------------------------------------------------===//
 
 // [Real] -> [Real]
 def Inv: Opcode {

clang/test/AST/Interp/literals.cpp

constinit int var = foo(5); // ref-error {{not a constant expression}} \
                               // ref-note {{required by 'constinit' specifier}} \
                               // expected-error  {{is not a constant expression}} \
                               // expected-note {{in call to}} \
                               // expected-error {{does not have a constant initializer}} \
                               // expected-note {{required by 'constinit' specifier}} \
 
 #endif
 };
+
+#define INT_MIN (~__INT_MAX__)
+
+namespace rem {
+  static_assert(2 % 2 == 0, "");
+  static_assert(2 % 1 == 0, "");
+  static_assert(-3 % 4 == -3, "");
+  static_assert(4 % -2 == 0, "");
+  static_assert(-3 % -4 == -3, "");
+
+  constexpr int zero() { return 0; }
+  static_assert(10 % zero() == 20, ""); // ref-error {{not an integral constant expression}} \
+                                        // ref-note {{division by zero}} \
+                                        // expected-error {{not an integral constant expression}} \
+                                        // expected-note {{division by zero}}
+
+
+  static_assert(true % true == 0, "");
+  static_assert(false % true == 0, "");
+  static_assert(true % false == 10, ""); // ref-error {{not an integral constant expression}} \
+                                         // ref-note {{division by zero}} \
+                                         // expected-error {{not an integral constant expression}} \
+                                         // expected-note {{division by zero}}
+  constexpr int x = INT_MIN % - 1; // ref-error {{must be initialized by a constant expression}} \
+                                   // ref-note {{value 2147483648 is outside the range}} \
+                                   // expected-error {{must be initialized by a constant expression}} \
+                                   // expected-note {{value 2147483648 is outside the range}} \
+
+};