[clang][Interp] Implement switch statements

[tbaeder]

Summary

This creates a temporary local variable for the condition variable, then emits all the comparisons for the case statements, followed by the sub statements of the case statements.

[tbaeder]

Ping

[aaron.ballman]

clang/lib/AST/Interp/ByteCodeStmtGen.cpp

423

How well does this handle large switch statements? Generated code sometimes winds up with thousands of cases, so I'm wondering if we need to have a jump table implementation for numerous cases and use the simple comparison implementation when there's only a small number of labels (and we can test to see what constitutes a good value for "small number of labels").

Also, one thing to be aware of (that hopefully won't matter TOO much in this case): the switch case list does not have a stable iteration order IIRC.

clang/test/AST/Interp/switch.cpp

16–18

lol, you should probably fix this so it's not so confusing to casual readers.

46

I think it would be good to add a non-trivial init and show that it fails when appropriate. e.g.,

struct Weirdo {
  consteval Weirdo(int);
  Weirdo(double);

  int Val = 1;
};

constexpr int whatever() {
  switch (Weirdo W(12); W.Val) {
  case 1: return 12;
  default: return 100;
  }
}

constexpr int whatever_else() {
  switch (Weirdo W(1.2); W.Val) { // Should get an error because of the init not being constexpr
  case 1: return 12;
  default: return 100;
  }
}

static_assert(whatever() == 12, "");
static_assert(whatever_else() == 12, ""); // Shouldn't compile because the function isn't constexpr

68

I'd like a test where the case value is itself a constant expression that is either valid or invalid:

constexpr int good() { return 1; }
constexpr int test(int val) {
  switch (val) {
  case good(): return 100;
  default: return -1;
  }
  return 0;
}
static_assert(test(1) == 100, "");

constexpr int bad(int val) { return val / 0; }
constexpr int another_test(int val) {
  switch (val) {
  case bad(val): return 100; // Should not compile
  default: return -1;
  }
  return 0;
}
static_assert(another_test(1) == 100, ""); // Should not compile

[tbaeder]

clang/lib/AST/Interp/ByteCodeStmtGen.cpp

423

With 10'000 case labels, it seems to be slightly slower if all case labels need to be iterated through and slightly faster if the first iteration already hits. I'm not too concerned about the performance here tbh.

clang/test/AST/Interp/switch.cpp

16–18

What exactly is the confusing part? :D That the case labels are out of order?

[aaron.ballman]

clang/lib/AST/Interp/ByteCodeStmtGen.cpp

423

Okay, we can address performance concerns later, if they arise. Thanks!

clang/test/AST/Interp/switch.cpp

16–18

The function is called isEven and 11, 13, 15 all return true due to fallthrough.

[tbaeder]

clang/test/AST/Interp/switch.cpp

46

This is unfortunately hard do test with the new constant interpreter right now. It never emits the "never produces a constant expression" diagnostic because I removed the Run() call from isPotentialConstantExpression(). I need to revert that and instead fix the interpreter to correctly takes this mode into account.

And for the non-constexpr constructor, we will reject the call in the static_assert(), but not diagnose anything useful because we're not checking the constructor for constexpr-ness (this is part of https://reviews.llvm.org/D137563 I believe).

[aaron.ballman]

clang/test/AST/Interp/switch.cpp

46

I'd be fine if the tests were added with FIXME comments (or commented out if they're too disruptive).

[shafik]

clang/lib/AST/Interp/ByteCodeStmtGen.cpp

405

The condition could be a class type w/ a conversion operator, this does not seem like it will handle this case. Maybe b/c you don't handle conversion operators yet but might be worth a FIXME or TODO.

clang/lib/AST/Interp/ByteCodeStmtGen.h

private:
   bool visitDeclStmt(const DeclStmt *DS);
   bool visitReturnStmt(const ReturnStmt *RS);
   bool visitIfStmt(const IfStmt *IS);
   bool visitWhileStmt(const WhileStmt *S);
   bool visitDoStmt(const DoStmt *S);
   bool visitForStmt(const ForStmt *S);
   bool visitBreakStmt(const BreakStmt *S);
   bool visitContinueStmt(const ContinueStmt *S);
+  bool visitSwitchStmt(const SwitchStmt *S);
+  bool visitCaseStmt(const CaseStmt *S);
+  bool visitDefaultStmt(const DefaultStmt *S);
 
   /// Compiles a variable declaration.
 
 private:
   /// Type of the expression returned by the function.
   llvm::Optional<PrimType> ReturnType;
 
   /// Switch case mapping.

clang/lib/AST/Interp/ByteCodeStmtGen.cpp

bool ByteCodeStmtGen<Emitter>::visitStmt(const Stmt *S) {
   case Stmt::DoStmtClass:
     return visitDoStmt(cast<DoStmt>(S));
   case Stmt::ForStmtClass:
     return visitForStmt(cast<ForStmt>(S));
   case Stmt::BreakStmtClass:
     return visitBreakStmt(cast<BreakStmt>(S));
   case Stmt::ContinueStmtClass:
     return visitContinueStmt(cast<ContinueStmt>(S));
+  case Stmt::SwitchStmtClass:
+    return visitSwitchStmt(cast<SwitchStmt>(S));
+  case Stmt::CaseStmtClass:
+    return visitCaseStmt(cast<CaseStmt>(S));
+  case Stmt::DefaultStmtClass:
+    return visitDefaultStmt(cast<DefaultStmt>(S));
   case Stmt::NullStmtClass:
     return true;
   default: {
     if (auto *Exp = dyn_cast<Expr>(S))
       return this->discard(Exp);
     return this->bail(S);
   }
   }

 bool ByteCodeStmtGen<Emitter>::visitContinueStmt(const ContinueStmt *S) {
   if (!ContinueLabel)
     return false;
 
   this->emitCleanup();
   return this->jump(*ContinueLabel);
 }
 
+template <class Emitter>
+bool ByteCodeStmtGen<Emitter>::visitSwitchStmt(const SwitchStmt *S) {
+  const Expr *Cond = S->getCond();
+  PrimType CondT = this->classifyPrim(Cond->getType());
+
+  LabelTy EndLabel = this->getLabel();
+  OptLabelTy DefaultLabel = None;
+  unsigned CondVar = this->allocateLocalPrimitive(Cond, CondT, true, false);
+
+  if (const auto *CondInit = S->getInit())
+    if (!visitStmt(CondInit))
+      return false;
+
+  // Initialize condition variable.
+  if (!this->visit(Cond))
+    return false;
+  if (!this->emitSetLocal(CondT, CondVar, S))
+    return false;
+
+  CaseMap CaseLabels;
+  // Create labels and comparison ops for all case statements.
+  for (const SwitchCase *SC = S->getSwitchCaseList(); SC;
+       SC = SC->getNextSwitchCase()) {
+    if (const auto *CS = dyn_cast<CaseStmt>(SC)) {
+      // FIXME: Implement ranges.
+      if (CS->caseStmtIsGNURange())
+        return false;
+      CaseLabels[SC] = this->getLabel();
+
+      const Expr *Value = CS->getLHS();
+      PrimType ValueT = this->classifyPrim(Value->getType());
+
+      // Compare the case statment's value to the switch condition.
+      if (!this->emitGetLocal(CondT, CondVar, CS))
+        return false;
+      if (!this->visit(Value))
+        return false;
+
+      // Compare and jump to the case label.
+      if (!this->emitEQ(ValueT, S))
+        return false;
+      if (!this->jumpTrue(CaseLabels[CS]))
+        return false;
+    } else {
+      assert(!DefaultLabel);
+      DefaultLabel = this->getLabel();
+    }
+  }
+
+  // If none of the conditions above were true, fall through to the default
+  // statement or jump after the switch statement.
+  if (DefaultLabel) {
+    if (!this->jump(*DefaultLabel))
+      return false;
+  } else {
+    if (!this->jump(EndLabel))
+      return false;
+  }
+
+  SwitchScope<Emitter> SS(this, std::move(CaseLabels), EndLabel, DefaultLabel);
+  if (!this->visitStmt(S->getBody()))
+    return false;
+  this->emitLabel(EndLabel);
+  return true;
+}
+
+template <class Emitter>
+bool ByteCodeStmtGen<Emitter>::visitCaseStmt(const CaseStmt *S) {
+  this->emitLabel(CaseLabels[S]);
+  return this->visitStmt(S->getSubStmt());
+}
+
+template <class Emitter>
+bool ByteCodeStmtGen<Emitter>::visitDefaultStmt(const DefaultStmt *S) {
+  this->emitLabel(*DefaultLabel);
+  return this->visitStmt(S->getSubStmt());
+}
+
 namespace clang {
 namespace interp {
 
 template class ByteCodeStmtGen<ByteCodeEmitter>;
 
 } // namespace interp
 } // namespace clang

clang/test/AST/Interp/switch.cpp

+// RUN: %clang_cc1 -fexperimental-new-constant-interpreter -verify %s
+// RUN: %clang_cc1 -verify=ref %s
+
+// ref-no-diagnostics
+// expected-no-diagnostics
+
+constexpr bool isEven(int a) {
+  bool v = false;
+  switch(a) {
+  case 2: return true;
+  case 4: return true;
+  case 6: return true;
+
+  case 8:
+  case 10:
+  case 11:
+  case 13:
+  case 15:
+  case 12:
+    return true;
+  case 14:
+    v = true;
+    break;
+
+  default:
+  switch(a) {
+  case 1:
+    break;
+  case 3:
+    return false;
+  default:
+    break;
+  }
+  }
+
+  return v;
+}
+static_assert(isEven(2), "");
+static_assert(isEven(8), "");
+static_assert(isEven(10), "");
+static_assert(isEven(14), "");
+static_assert(!isEven(1), "");
+
+
+constexpr int withInit() {
+  switch(int a = 2; a) {
+    case 1: return -1;
+    case 2: return 2;
+  }
+  return -1;
+}
+static_assert(withInit() == 2, "");
+
+constexpr int FT(int a) {
+  int m = 0;
+  switch(a) {
+  case 4: m++;
+  case 3: m++;
+  case 2: m++;
+  case 1: m++;
+    return m;
+  }
+
+  return -1;
+}
+static_assert(FT(1) == 1, "");
+static_assert(FT(4) == 4, "");
+static_assert(FT(5) == -1, "");