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

54

Please choose a better name than var.

134

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

155–179

Why do you change this to pc again?

156

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?

160

Looks like a pointless branch.

168

Why nuw, nsw here?

178

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

155–179

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

160

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.

168

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

178

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

134

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.

164

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

167

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.

167

Will all loops be double-nested now?

[emmettneyman]

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

134

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?

156

%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.

164

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

167

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.

167

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

134

That would be better.

164

Right, sorry not sure what I missed there.

167

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

121

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

145

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 {
+message Loop {
   required StatementSeq statements = 1;
 }
 
+message LoopFunction {
+  repeated Loop loops = 1;
+}
+
 package clang_fuzzer;

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

 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 Loop &x){
+  return os << "for (int i=0; i<s; i++){\n"
+            << x.statements() << "}\n";
+}
 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";
+  os << "void foo(int *a, int *b, int *__restrict__ c, size_t s) {\n";
+  for (auto &lp : x.loops())
+    os << lp;
+  return os << "}\n";
 }
 
 // ---------------------------------
 
 std::string LoopFunctionToString(const LoopFunction &input) {
   std::ostringstream os;
   os << input;
   return os.str();
 }
 std::string LoopProtoToCxx(const uint8_t *data, size_t size) {
   LoopFunction message;
   if (!message.ParsePartialFromArray(data, size))
     return "#error invalid proto\n";
   return LoopFunctionToString(message);
 }
 
 } // namespace clang_fuzzer

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 int loop_ctr = 0;
+
+static std::string get_loop_num() {
+  return std::to_string(loop_ctr);
+}
+
+static void new_loop() {
+  loop_ctr++;
+}
+
 // 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 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 %ct_" << get_loop_num() << "\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 Loop &x) {
+  new_loop();
+  std::string lnum = get_loop_num();
+  std::string next_lnum = std::to_string(stoi(lnum) + 1);
+  if (!lnum.compare("1")) {
+    os << "%cmp_" << lnum << " = icmp sgt i64 %s, 0\n"
+       << "br i1 %cmp_" << lnum << ", label %loop_start_" << lnum 
+       << ", label %end\n";
+  }
+  return os << "loop_start_" << lnum << ":\n"
+            << "br label %loop_" << lnum << "\n"
+            << "loop_end_" << lnum << ":\n"
+            << "%cmp_" << next_lnum << " = icmp sgt i64 %s, 0\n"
+            << "br i1 %cmp_" << next_lnum << ", label %loop_start_" << next_lnum
+            << ", label %end\n"
+            << "loop_" << lnum << ":\n"
+            << " %ct_" << lnum << "   = phi i64 [ %ctnew_" << lnum
+            << ", %loop_" << lnum << " ], [ 0, %loop_start_" << lnum << " ]\n"
+            << x.statements()
+            << "%ctnew_" << lnum << " = add i64 %ct_" << lnum << ", 1\n"
+            << "%j_" << lnum << " = icmp eq i64 %ctnew_" << lnum << ", %s\n"
+            << "br i1 %j_" << lnum << ", label %loop_end_" << lnum
+            << ", label %loop_" << lnum << ", !llvm.loop !0\n";
+
+}
 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";
+  os << "target triple = \"x86_64-unknown-linux-gnu\"\n"
+     << "define void @foo(i32* %a, i32* %b, i32* %c, i64 %s) {\n";
+  for (auto &lp : x.loops()) {
+    os << lp;
+    // No matter how many loops the protobuf has, only translate 10 of them
+    if (!get_loop_num().compare("10"))
+      break;
+  }
+  new_loop();
+  std::string lnum = get_loop_num();
+  os << "loop_start_" << lnum << ":\n"
+     << "br label %end\n"
+     << "ret void\n}\n"
+     << "!2 = !{!\"llvm.loop.vectorize.width\", i32 " << kArraySize << "}\n";
+  return os;
 }
 
 // ---------------------------------
 
 std::string LoopFunctionToLLVMString(const LoopFunction &input) {
   std::ostringstream os;
   os << input;
   return os.str();