[clang][Interp] Implement for loops

[tbaeder]

Ping

[aaron.ballman]

LGTM aside from some minor points.

clang/lib/AST/Interp/ByteCodeStmtGen.cpp

361

What does the call to discard() do? Evaluate the expression and discard the results? (If so, the API might want for a better name at some point, as it can also read like "do nothing with this expression".)

clang/test/AST/Interp/loops.cpp

217–227

I'd love to see a stress test for the compile time performance of:

int func() {
  int i = 0;
  for (;;) {
    if (i == __INT_MAX__)
      break;
    ++i;
  }
  return i;
}
static_assert(func() == __INT_MAX__);

I don't think there's value to testing specifically how long it takes for this to execute, but we should probably start thinking about how to validate performance characteristics pretty soon. Perhaps relative performance compared to the existing constant expression evaluator would be interesting though?

272

Another test to add here: for (;;); is just as infinite.

[tbaeder]

clang/lib/AST/Interp/ByteCodeStmtGen.cpp

361

Yes, it's the same problem that https://reviews.llvm.org/D136013 tries to solve. If Inc evaluates to a value, it will leave that on the stack and something needs to remove it from there, which is what discard() does.

clang/test/AST/Interp/loops.cpp

217–227

Perhaps relative performance compared to the existing constant expression evaluator would be interesting though?

Definitely. My plan was basically to get some base functionality going and then always keep an eye on performance. Your test doesn't work because the current interpreter has a step limit, but for a simple loop up until 100'000, the current interpreter takes 42s here and the new one takes 2s.

[tbaeder]

clang/test/AST/Interp/loops.cpp

272

Heh, that's what this was supposed to be :) I already have the while(true) one above.

clang/lib/AST/Interp/ByteCodeStmtGen.h

private:
   // 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 visitForStmt(const ForStmt *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.

clang/lib/AST/Interp/ByteCodeStmtGen.cpp

bool ByteCodeStmtGen<Emitter>::visitStmt(const Stmt *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::ForStmtClass:
+    return visitForStmt(cast<ForStmt>(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))
if (!this->visitBool(Cond))
     return false;
   if (!this->jumpTrue(StartLabel))
     return false;
   this->emitLabel(EndLabel);
   return true;
 }
 
 template <class Emitter>
+bool ByteCodeStmtGen<Emitter>::visitForStmt(const ForStmt *S) {
+  // for (Init; Cond; Inc) { Body }
+  const Stmt *Init = S->getInit();
+  const Expr *Cond = S->getCond();
+  const Expr *Inc = S->getInc();
+  const Stmt *Body = S->getBody();
+
+  LabelTy EndLabel = this->getLabel();
+  LabelTy CondLabel = this->getLabel();
+  LabelTy IncLabel = this->getLabel();
+  LoopScope<Emitter> LS(this, EndLabel, IncLabel);
+
+  if (Init && !this->visitStmt(Init))
+    return false;
+  this->emitLabel(CondLabel);
+  if (Cond) {
+    if (!this->visitBool(Cond))
+      return false;
+    if (!this->jumpFalse(EndLabel))
+      return false;
+  }
+  if (Body && !this->visitStmt(Body))
+    return false;
+  this->emitLabel(IncLabel);
+  if (Inc && !this->discard(Inc))
+    return false;
+  if (!this->jump(CondLabel))
+    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>

clang/test/AST/Interp/loops.cpp

 #if 0
   /// FIXME: This is an infinite loop, which should
   ///   be rejected.
   constexpr int f7() {
     while(true);
   }
 #endif
 };
+
+namespace ForLoop {
+  constexpr int f() {
+    int i = 0;
+    for (;false;) {
+      i = i + 1;
+    }
+    return i;
+  }
+  static_assert(f() == 0, "");
+
+  constexpr int f2() {
+    int m = 0;
+    for (int i = 0; i < 10; i = i + 1){
+      m = i;
+    }
+    return m;
+  }
+  static_assert(f2() == 9, "");
+
+  constexpr int f3() {
+    int i = 0;
+    for (; i != 5; i = i + 1);
+    return i;
+  }
+  static_assert(f3() == 5, "");
+
+  constexpr int f4() {
+    int i = 0;
+    for (;;) {
+      i = i + 1;
+
+      if (i == 5)
+        break;
+    }
+    return i;
+  }
+  static_assert(f4() == 5, "");
+
+  constexpr int f5() {
+    int i = 0;
+    for (;i != 5;) {
+      i = i + 1;
+      continue;
+      i = i - 1;
+    }
+    return i;
+  }
+  static_assert(f5() == 5, "");
+
+  constexpr int f6(bool b) {
+    int i = 0;
+
+    for (;true;) {
+      if (!b) {
+        if (i == 5)
+          break;
+      }
+
+      if (b) {
+        for (; i != 10; i = i + 1) {
+          if (i == 8)
+            break;
+          continue;
+        }
+      }
+
+      if (b)
+        break;
+
+      i = i + 1;
+      continue;
+    }
+
+    return i;
+  }
+  static_assert(f6(true) == 8, "");
+  static_assert(f6(false) == 5, "");
+
+#if 0
+  /// FIXME: This is an infinite loop, which should
+  ///   be rejected.
+  constexpr int f6() {
+    for(;;);
+  }
+#endif
+
+};