[clang][Interp] Implement while and do-while loops

[tbaeder]

Summary

I was wondering whether it is somehow possible to get a loop into a expression so I can use it directly in a static_assert() (and it would be interpreted directly rather than compiled to bytecode).

[tbaeder]

Add break and continue support as well.

[aaron.ballman]

clang/test/AST/Interp/loops.cpp

94

Can you also add some tests that use nested loops with multiple levels of break and continue use?

Also, I think it might be useful to show the jump statements causing code to be an invalid constant expression, as in:

constexpr int foo() {
  int i;

  do {
    break;
    i = 12;
  } while (1);

  return i;
}

constexpr int f = foo();

[tbaeder]

clang/test/AST/Interp/loops.cpp

94

I can add a commented-out test case for that, but it is currently being rejected for the wrong reasons. I investigated that in another case already and it will simply be rejected because the variable declaration does not have an initializer. Not because we're reading an uninitialized variable.

[shafik]

clang/test/AST/Interp/loops.cpp

10

infinite loop w/o a side effect are undefined behavior and so should be ill-formed and generate a diagnostic e.g. while(1);, so we should check these cases.

[tbaeder]

clang/test/AST/Interp/loops.cpp

10

I think that's better done with a more general approach that limits the iteration count for all loops like the current interpreter does. But that would probably blow up this patch too much.

Unfortunately I can't add test case for the case you describe because the clang process with the new interpreter would never terminate :) Can add a commented-out version though.

[shafik]

clang/test/AST/Interp/loops.cpp

10

I think that is fine approach for now.

[aaron.ballman]

LGTM!

clang/lib/AST/Interp/ByteCodeStmtGen.cpp

279

clang/lib/AST/Interp/ByteCodeStmtGen.h

private:
   friend class SwitchScope<Emitter>;
 
   // Statement visitors.
   bool visitStmt(const Stmt *S);
   bool visitCompoundStmt(const CompoundStmt *S);
   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 visitBreakStmt(const BreakStmt *S);
+  bool visitContinueStmt(const ContinueStmt *S);
 
   /// Compiles a variable declaration.
   bool visitVarDecl(const VarDecl *VD);
 
 private:
   /// Type of the expression returned by the function.
   llvm::Optional<PrimType> ReturnType;
 

clang/lib/AST/Interp/ByteCodeStmtGen.cpp

bool ByteCodeStmtGen<Emitter>::visitStmt(const Stmt *S) {
   case Stmt::CompoundStmtClass:
     return visitCompoundStmt(cast<CompoundStmt>(S));
   case Stmt::DeclStmtClass:
     return visitDeclStmt(cast<DeclStmt>(S));
   case Stmt::ReturnStmtClass:
     return visitReturnStmt(cast<ReturnStmt>(S));
   case Stmt::IfStmtClass:
     return visitIfStmt(cast<IfStmt>(S));
+  case Stmt::WhileStmtClass:
+    return visitWhileStmt(cast<WhileStmt>(S));
+  case Stmt::DoStmtClass:
+    return visitDoStmt(cast<DoStmt>(S));
+  case Stmt::BreakStmtClass:
+    return visitBreakStmt(cast<BreakStmt>(S));
+  case Stmt::ContinueStmtClass:
+    return visitContinueStmt(cast<ContinueStmt>(S));
   case Stmt::NullStmtClass:
     return true;
   default: {
     if (auto *Exp = dyn_cast<Expr>(S))
       return this->discard(Exp);
     return this->bail(S);
   }
   }
if (!visitStmt(IS->getThen()))
       return false;
     this->emitLabel(LabelEnd);
   }
 
   return true;
 }
 
 template <class Emitter>
+bool ByteCodeStmtGen<Emitter>::visitWhileStmt(const WhileStmt *S) {
+  const Expr *Cond = S->getCond();
+  const Stmt *Body = S->getBody();
+
+  LabelTy CondLabel = this->getLabel(); // Label before the condition.
+  LabelTy EndLabel = this->getLabel();  // Label after the loop.
+  LoopScope<Emitter> LS(this, EndLabel, CondLabel);
+
+  this->emitLabel(CondLabel);
+  if (!this->visitBool(Cond))
+    return false;
+  if (!this->jumpFalse(EndLabel))
+    return false;
+
+  if (!this->visitStmt(Body))
+    return false;
+  if (!this->jump(CondLabel))
+    return false;
+
+  this->emitLabel(EndLabel);
+
+  return true;
+}
+
+template <class Emitter>
+bool ByteCodeStmtGen<Emitter>::visitDoStmt(const DoStmt *S) {
+  const Expr *Cond = S->getCond();
+  const Stmt *Body = S->getBody();
+
+  LabelTy StartLabel = this->getLabel();
+  LabelTy EndLabel = this->getLabel();
+  LabelTy CondLabel = this->getLabel();
+  LoopScope<Emitter> LS(this, EndLabel, CondLabel);
+
+  this->emitLabel(StartLabel);
+  if (!this->visitStmt(Body))
+    return false;
+  this->emitLabel(CondLabel);
+  if (!this->visitBool(Cond))
+    return false;
+  if (!this->jumpTrue(StartLabel))
+    return false;
+  this->emitLabel(EndLabel);
+  return true;
+}
+
+template <class Emitter>
+bool ByteCodeStmtGen<Emitter>::visitBreakStmt(const BreakStmt *S) {
+  if (!BreakLabel)
+    return false;
+
+  return this->jump(*BreakLabel);
+}
+
+template <class Emitter>
+bool ByteCodeStmtGen<Emitter>::visitContinueStmt(const ContinueStmt *S) {
+  if (!ContinueLabel)
+    return false;
+
+  return this->jump(*ContinueLabel);
+}
+
+template <class Emitter>
 bool ByteCodeStmtGen<Emitter>::visitVarDecl(const VarDecl *VD) {
   if (!VD->hasLocalStorage()) {
     // No code generation required.
     return true;
   }
 
   // Integers, pointers, primitives.
   if (Optional<PrimType> T = this->classify(VD->getType())) {

clang/test/AST/Interp/loops.cpp

+// RUN: %clang_cc1 -fexperimental-new-constant-interpreter -std=c++14 -verify %s
+// RUN: %clang_cc1 -std=c++14 -verify=ref %s
+// RUN: %clang_cc1 -fexperimental-new-constant-interpreter -std=c++20 -verify=expected-cpp20 %s
+// RUN: %clang_cc1 -std=c++20 -verify=ref %s
+
+// ref-no-diagnostics
+// expected-no-diagnostics
+
+namespace WhileLoop {
+  constexpr int f() {
+    int i = 0;
+    while(false) {
+      i = i + 1;
+    }
+    return i;
+  }
+  static_assert(f() == 0, "");
+
+
+  constexpr int f2() {
+    int i = 0;
+    while(i != 5) {
+      i = i + 1;
+    }
+    return i;
+  }
+  static_assert(f2() == 5, "");
+
+  constexpr int f3() {
+    int i = 0;
+    while(true) {
+      i = i + 1;
+
+      if (i == 5)
+        break;
+    }
+    return i;
+  }
+  static_assert(f3() == 5, "");
+
+  constexpr int f4() {
+    int i = 0;
+    while(i != 5) {
+
+      i = i + 1;
+      continue;
+      i = i - 1;
+    }
+    return i;
+  }
+  static_assert(f4() == 5, "");
+
+
+  constexpr int f5(bool b) {
+    int i = 0;
+
+    while(true) {
+      if (!b) {
+        if (i == 5)
+          break;
+      }
+
+      if (b) {
+        while (i != 10) {
+          i = i + 1;
+          if (i == 8)
+            break;
+
+          continue;
+        }
+      }
+
+      if (b)
+        break;
+
+      i = i + 1;
+      continue;
+    }
+
+    return i;
+  }
+  static_assert(f5(true) == 8, "");
+  static_assert(f5(false) == 5, "");
+
+#if 0
+  /// FIXME: This is an infinite loop, which should
+  ///   be rejected.
+  constexpr int f6() {
+    while(true);
+  }
+#endif
+};
+
+namespace DoWhileLoop {
+
+  constexpr int f() {
+    int i = 0;
+    do {
+      i = i + 1;
+    } while(false);
+    return i;
+  }
+  static_assert(f() == 1, "");
+
+  constexpr int f2() {
+    int i = 0;
+    do {
+      i = i + 1;
+    } while(i != 5);
+    return i;
+  }
+  static_assert(f2() == 5, "");
+
+
+  constexpr int f3() {
+    int i = 0;
+    do {
+      i = i + 1;
+      if (i == 5)
+        break;
+    } while(true);
+    return i;
+  }
+  static_assert(f3() == 5, "");
+
+  constexpr int f4() {
+    int i = 0;
+    do {
+      i = i + 1;
+      continue;
+      i = i - 1;
+    } while(i != 5);
+    return i;
+  }
+  static_assert(f4() == 5, "");
+
+  constexpr int f5(bool b) {
+    int i = 0;
+
+    do {
+      if (!b) {
+        if (i == 5)
+          break;
+      }
+
+      if (b) {
+        do {
+          i = i + 1;
+          if (i == 8)
+            break;
+
+          continue;
+        } while (i != 10);
+      }
+
+      if (b)
+        break;
+
+      i = i + 1;
+      continue;
+    } while(true);
+
+    return i;
+  }
+  static_assert(f5(true) == 8, "");
+  static_assert(f5(false) == 5, "");
+
+  /// FIXME: This should be accepted in C++20 but is currently being rejected
+  ///   because the variable declaration doesn't have an initializier.
+#if __cplusplus >= 202002L
+  constexpr int f6() {
+    int i;
+    do {
+      i = 5;
+      break;
+    } while (true);
+    return i;
+  }
+  static_assert(f6() == 5, ""); // expected-cpp20-error {{not an integral constant}}
+#endif
+
+#if 0
+  /// FIXME: This is an infinite loop, which should
+  ///   be rejected.
+  constexpr int f7() {
+    while(true);
+  }
+#endif
+};