Implementation of nested loops in cxx_loop_proto

[emmettneyman]

Summary

Extended cxx_loop_proto to have neste for loops. Modified loop_proto_to_llvm and loop_proto_to_cxx to handle the new protos. All protos have a set of statements designated as "inner loop" statements and a set of statements designated as "outer loop" statements.

[morehouse]

Does having multiple loops one after another change any coverage in the vectorizer?

[emmettneyman]

No, it doesn't actually. I thought it would try to combine the separate loops into one block of vectorized instructions but after looking at the coverage of multiple loops vs single loop, they cover exactly the same parts of the Loop Vectorizer. Should I switch my focus to nested loops instead? I think nested loops will increase coverage.

[morehouse]

In D50670#1199556, @emmettneyman wrote:

Should I switch my focus to nested loops instead? I think nested loops will increase coverage.

Yes, I'd recommend doing that.

[morehouse]

Another option would be to allow simple control flow within the loop itself.

[emmettneyman]

Changed the multiloop protos to nested loop protos. All the protos have an inner loop and an outer loop.

[morehouse]

Does this hit new coverage in the vectorizer?

clang/tools/clang-fuzzer/proto-to-llvm/loop_proto_to_llvm.cpp

56

Please choose a better name than var.

137

This looks like a bug. inner_loop never gets set to false again. Might be a good reason to make it parameter instead.

189–193

Why do you change this to pc again?

190

I'm curious how this change affects coverage independent of the rest of this change. Also what would happen if we set %a and %b to noalias as well?

194

Looks like a pointless branch.

202

Why nuw, nsw here?

212

Can we simplify the order of blocks here? It is confusing to follow all these jumps forward and backward.

[emmettneyman]

In D50670#1200784, @morehouse wrote:

Does this hit new coverage in the vectorizer?

Yes, this does hit new coverage in the loop vectorizer code.

clang/tools/clang-fuzzer/proto-to-llvm/loop_proto_to_llvm.cpp

189–193

Sorry, it got changed back when I copy/pasted the IR.

194

I realize it's just a label with a branch instruction but I think I need it for the phi instruction. I will move the outer_loop_start label above the icmp instruction and change the branch from outer_loop_start to inner_loop_start.

202

Sorry, it got changed back when I copy/pasted the IR.

212

Yes, I think it might be cleaner to have the blocks like this:

define @foo... {

outer_loop_start

outer_loop

inner_loop_start

inner_loop

end
}

[emmettneyman]

Small changes to generated IR

[emmettneyman]

Small changes to generated IR, my last change hadn't saved

[morehouse]

clang/tools/clang-fuzzer/proto-to-llvm/loop_proto_to_llvm.cpp

137

Maybe this fixes the bug, but modifying inner_loop from different functions is still error-prone.

Please either make this a scoped variable (with a wrapper class that sets it to true in the constructor and sets it to false in the destructor), or make it a parameter.

198

I don't see any jumps to end. I think this will be an infinite loop.

201

IIUC this creates loop structure always like this:

for (int i = 0; i < s; i++) {
  for (int j = 0; j < s; j++) {
    // statements
  }
  // statements
}

Maybe not necessary for this patch, but I'm curious if adding statements before the inner loop would exercise different coverage in the vectorizer.

201

Will all loops be double-nested now?

[emmettneyman]

clang/tools/clang-fuzzer/proto-to-llvm/loop_proto_to_llvm.cpp

137

Would it be better if inner_loop was only modified in the LoopFunction operator override? For example:

std::ostream &operator<<(std::ostream &os, const LoopFunction &x) {
  inner_loop = false;
  os << "target triple = \"x86_64-unknown-linux-gnu\"\n"
     ....
     << << "outer_loop:\n"
     << x.outer_statements();
  inner_loop = true;
  os << "%o_ct_new = add i64 %outer_ct, 1\n"
     ....
     << "!2 = !{!\"llvm.loop.vectorize.width\", i32 " << kArraySize << "}\n";
  return os;

And removed inner_loop = true; from the above function?

190

%c was always supposed to be noalias. It got changed accidentally in the last patch. I'm not sure what would change in the coverage if %a and %b also got set to be noalias.

@kcc and I had originally planned for foo (int *a, int *b, int *__restrict__ c, size_t s) to be just the first function signature we tried for this fuzz target and to change it up and try different signatures.

198

There are two jumps to end, one before entering the outer_loop and one at the end of outer_loop.

201

Yes, that's correct. It's also worth noting that all the statements in the inner loop will only use j to index into the arrays, never i. It shouldn't be hard to add outer loop statements before the inner loop. A third StatementSeq could be added to the LoopFunction proto: one for outer loop statements before the inner loop, one for inner loop statements, and one for outer loop statements after the inner loop.

201

Yes, all loops will be double-nested. It shouldn't be difficult to make the inner loop optional though. In cxx_loop_proto, the first Statement_Seq, inner_statements, can be made optional and then a different IR structures can be generated depending on whether or not inner_statements exists.

[morehouse]

clang/tools/clang-fuzzer/proto-to-llvm/loop_proto_to_llvm.cpp

137

That would be better.

198

Right, sorry not sure what I missed there.

201

Can we do that in this patch? I think it makes sense to be able to generate either single loops or nested loops.

[emmettneyman]

Made the inner loop optional and moved all modifications of inner_loop to one function.

[morehouse]

clang/tools/clang-fuzzer/proto-to-cxx/loop_proto_to_cxx.cpp

133

Why do we need to set inner_loop from different functions?

Again, using the global like this is just too easy to screw up. I'd like to see it default to false and then have a scoped wrapper that sets it to true only for the duration necessary.

clang/tools/clang-fuzzer/proto-to-llvm/loop_proto_to_llvm.cpp

148

Same comment as above. I'm getting confused trying to understand what inner_loop is set to at any given point.

[emmettneyman]

Changed modifying global var to scoped class

[emmettneyman]

Updated comments, rebased, and ready to land

clang/tools/clang-fuzzer/cxx_loop_proto.proto

message Statement {
   required AssignmentStatement assignment = 1;
 }
 
 message StatementSeq {
   repeated Statement statements = 1;
 }
 
 message LoopFunction {
-  required StatementSeq statements = 1;
+  optional StatementSeq inner_statements = 1;
+  required StatementSeq outer_statements = 2;
 }
 
 package clang_fuzzer;

clang/tools/clang-fuzzer/proto-to-cxx/loop_proto_to_cxx.cpp

 // The following is needed to convert protos in human-readable form
 #include <google/protobuf/text_format.h>
 
 #include <ostream>
 #include <sstream>
 
 namespace clang_fuzzer {
 
+static bool inner_loop = false;
+class InnerLoop {
+  public:
+  InnerLoop() {
+    inner_loop = true;
+  }
+  ~InnerLoop() {
+    inner_loop = false;
+  }
+};
+
 // Forward decls.
 std::ostream &operator<<(std::ostream &os, const BinaryOp &x);
 std::ostream &operator<<(std::ostream &os, const StatementSeq &x);
 
 // Proto to C++.
 std::ostream &operator<<(std::ostream &os, const Const &x) {
   return os << "(" << x.val() << ")";
 }
 std::ostream &operator<<(std::ostream &os, const VarRef &x) {
+  std::string which_loop = inner_loop ? "j" : "i";
   switch (x.arr()) {
     case VarRef::ARR_A:
-      return os << "a[i]";
+      return os << "a[" << which_loop << "]";
     case VarRef::ARR_B:
-      return os << "b[i]";
+      return os << "b[" << which_loop << "]";
     case VarRef::ARR_C:
-      return os << "c[i]";
+      return os << "c[" << which_loop << "]";
   }
 }
 std::ostream &operator<<(std::ostream &os, const Rvalue &x) {
   if (x.has_cons())
     return os << x.cons();
   if (x.has_binop())
     return os << x.binop();
   if (x.has_varref())

 std::ostream &operator<<(std::ostream &os, const Statement &x) {
   return os << x.assignment();
 }
 std::ostream &operator<<(std::ostream &os, const StatementSeq &x) {
   for (auto &st : x.statements())
     os << st;
   return os;
 }
-std::ostream &operator<<(std::ostream &os, const LoopFunction &x) {
-  return os << "void foo(int *a, int *b, int *__restrict__ c, size_t s) {\n"
-            << "for (int i=0; i<s; i++){\n"
-            << x.statements() << "}\n}\n";
+void NestedLoopToString(std::ostream &os, const LoopFunction &x) {
+  os << "void foo(int *a, int *b, int *__restrict__ c, size_t s) {\n"
+     << "for (int i=0; i<s; i++){\n"
+     << "for (int j=0; j<s; j++){\n";
+  {
+    InnerLoop IL;
+    os << x.inner_statements() << "}\n";
+  }
+  os << x.outer_statements() << "}\n}\n";
+}
+void SingleLoopToString(std::ostream &os, const LoopFunction &x) {
+  os << "void foo(int *a, int *b, int *__restrict__ c, size_t s) {\n"
+     << x.outer_statements() << "}\n}\n";
+}
+std::ostream &operator<<(std::ostream &os, const LoopFunction &x) {
+  if (x.has_inner_statements())
+    NestedLoopToString(os, x);
+  else
+    SingleLoopToString(os, x);
+  return os;
 }
 
 // ---------------------------------
 
 std::string LoopFunctionToString(const LoopFunction &input) {
   std::ostringstream os;
   os << input;
   return os.str();

clang/tools/clang-fuzzer/proto-to-llvm/loop_proto_to_llvm.cpp

 
 namespace clang_fuzzer {
 
 // Forward decls
 std::string BinopToString(std::ostream &os, const BinaryOp &x);
 std::string StateSeqToString(std::ostream &os, const StatementSeq &x);
 
 // Counter variable to generate new LLVM IR variable names and wrapper function
-std::string get_var() {
+static std::string get_var() {
   static int ctr = 0;
   return "%var" + std::to_string(ctr++);
 }
 
+static bool inner_loop = false;
+class InnerLoop {
+  public:
+  InnerLoop() {
+    inner_loop = true;
+  }
+  ~InnerLoop() {
+    inner_loop = false;
+  }
+};
+
+
 // Proto to LLVM.
 
 std::string ConstToString(const Const &x) {
   return std::to_string(x.val());
 }
 std::string VarRefToString(std::ostream &os, const VarRef &x) {
+  std::string which_loop = inner_loop ? "inner" : "outer";
   std::string arr;
   switch(x.arr()) {
   case VarRef::ARR_A:
     arr = "%a";
     break;
   case VarRef::ARR_B:
     arr = "%b";
     break;
   case VarRef::ARR_C:
     arr = "%c";
     break;
   }
   std::string ptr_var = get_var();
-  os << ptr_var << " = getelementptr inbounds i32, i32* " << arr << ", i64 %ct\n";
+  os << ptr_var << " = getelementptr inbounds i32, i32* " << arr
+     << ", i64 %" << which_loop << "_ct\n";
   return ptr_var;
 }
 std::string RvalueToString(std::ostream &os, const Rvalue &x) {
   if(x.has_cons())
     return ConstToString(x.cons());
   if(x.has_binop())
     return BinopToString(os, x.binop());
   if(x.has_varref()) {

 }
 std::ostream &operator<<(std::ostream &os, const Statement &x) {
   return os << x.assignment();
 }
 std::ostream &operator<<(std::ostream &os, const StatementSeq &x) {
   for (auto &st : x.statements()) {
     os << st;
   }
   return os;
 }
-std::ostream &operator<<(std::ostream &os, const LoopFunction &x) {
-  return os << "target triple = \"x86_64-unknown-linux-gnu\"\n"
-            << "define void @foo(i32* %a, i32* %b, i32* %c, i64 %s) {\n"
-            << "%1 = icmp sgt i64 %s, 0\n"
-            << "br i1 %1, label %start, label %end\n"
-            << "start:\n"
-            << "br label %loop\n"
-            << "end:\n"
-            << "ret void\n"
-            << "loop:\n"
-            << " %ct   = phi i64 [ %ctnew, %loop ], [ 0, %start ]\n"
-            << x.statements()
-            << "%ctnew = add i64 %ct, 1\n"
-            << "%j = icmp eq i64 %ctnew, %s\n"
-            << "br i1 %j, label %end, label %loop, !llvm.loop !0\n}\n"
-            << "!0 = distinct !{!0, !1, !2}\n"
-            << "!1 = !{!\"llvm.loop.vectorize.enable\", i1 true}\n"
-            << "!2 = !{!\"llvm.loop.vectorize.width\", i32 " << kArraySize
-            << "}\n";
+void NestedLoopToString(std::ostream &os, const LoopFunction &x) {
+  os << "target triple = \"x86_64-unknown-linux-gnu\"\n"
+     << "define void @foo(i32* %a, i32* %b, i32* noalias %c, i64 %s) {\n"
+     << "outer_loop_start:\n"
+     << "%cmp = icmp sgt i64 %s, 0\n"
+     << "br i1 %cmp, label %inner_loop_start, label %end\n"
+     << "outer_loop:\n"
+     << x.outer_statements()
+     << "%o_ct_new = add i64 %outer_ct, 1\n"
+     << "%jmp_outer = icmp eq i64 %o_ct_new, %s\n"
+     << "br i1 %jmp_outer, label %end, label %inner_loop_start\n"
+     << "inner_loop_start:\n"
+     << "%outer_ct = phi i64 [%o_ct_new, %outer_loop], [0, %outer_loop_start]\n"
+     << "br label %inner_loop\n"
+     << "inner_loop:\n"
+     << "%inner_ct = phi i64 [0, %inner_loop_start], [%i_ct_new, %inner_loop]\n";
+  {
+    InnerLoop IL;
+    os << x.inner_statements();
+  }
+  os << "%i_ct_new = add i64 %inner_ct, 1\n"
+     << "%jmp_inner = icmp eq i64 %i_ct_new, %s\n"
+     << "br i1 %jmp_inner, label %outer_loop, label %inner_loop, !llvm.loop !0\n"
+     << "end:\n"
+     << "ret void\n"
+     << "}\n"
+     << "!0 = distinct !{!0, !1, !2}\n"
+     << "!1 = !{!\"llvm.loop.vectorize.enable\", i1 true}\n"
+     << "!2 = !{!\"llvm.loop.vectorize.width\", i32 " << kArraySize << "}\n";
+}
+void SingleLoopToString(std::ostream &os, const LoopFunction &x) {
+  os << "target triple = \"x86_64-unknown-linux-gnu\"\n"
+     << "define void @foo(i32* %a, i32* %b, i32* noalias %c, i64 %s) {\n"
+     << "%cmp = icmp sgt i64 %s, 0\n"
+     << "br i1 %cmp, label %start, label %end\n"
+     << "%outer_ct = phi i64 [ %ctnew, %loop ], [ 0, %start ]\n"
+     << x.outer_statements()
+     << "%ctnew = add i64 %outer_ct, 1\n"
+     << "!2 = !{!\"llvm.loop.vectorize.width\", i32 " << kArraySize << "}\n";
+}
+std::ostream &operator<<(std::ostream &os, const LoopFunction &x) {
+  if (x.has_inner_statements())
+    NestedLoopToString(os, x);
+  else
+    SingleLoopToString(os, x);
+  return os;
 }
 
 // ---------------------------------
 
 std::string LoopFunctionToLLVMString(const LoopFunction &input) {
   std::ostringstream os;
   os << input;
   return os.str();
 }
 std::string LoopProtoToLLVM(const uint8_t *data, size_t size) {
   LoopFunction message;
   if (!message.ParsePartialFromArray(data, size))
     return "#error invalid proto\n";
   return LoopFunctionToLLVMString(message);
 }
 
 } // namespace clang_fuzzer