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

46 ↗

(On Diff #160740)

Please choose a better name than var.

127 ↗

(On Diff #160740)

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

131 ↗

(On Diff #160740)

Why do you change this to pc again?

132 ↗

(On Diff #160740)

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?

136 ↗

(On Diff #160740)

Looks like a pointless branch.

144 ↗

(On Diff #160740)

Why nuw, nsw here?

154 ↗

(On Diff #160740)

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

131 ↗

(On Diff #160740)

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

136 ↗

(On Diff #160740)

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.

144 ↗

(On Diff #160740)

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

154 ↗

(On Diff #160740)

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

127 ↗

(On Diff #160866)

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.

140 ↗

(On Diff #160866)

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

143 ↗

(On Diff #160866)

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.

143 ↗

(On Diff #160866)

Will all loops be double-nested now?

[emmettneyman]

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

127 ↗

(On Diff #160866)

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?

140 ↗

(On Diff #160866)

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

143 ↗

(On Diff #160866)

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.

143 ↗

(On Diff #160866)

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.

132 ↗

(On Diff #160740)

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

[morehouse]

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

127 ↗

(On Diff #160866)

That would be better.

140 ↗

(On Diff #160866)

Right, sorry not sure what I missed there.

143 ↗

(On Diff #160866)

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

124 ↗

(On Diff #160920)

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

137 ↗

(On Diff #160920)

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

tools/clang-fuzzer/cxx_loop_proto.proto

 //===-- cxx_loop_proto.proto - Protobuf description of C++ with for loops -===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 ///  This file describes a subset of C++ as a protobuf. It is used to
-///  more easily find interesting inputs for fuzzing Clang. This subset
-///  differs from the one defined in cxx_proto.proto by eliminating while
-///  loops and conditionals. The goal is that the C++ code generated will be
-///  more likely to stress the LLVM loop vectorizer.
+///  more easily find interesting inputs for fuzzing LLVM's vectorizer.
+///  This subset differs from the one defined in cxx_proto.proto by eliminating
+///  while loops and conditionals. The goal is that the C++ code generated will
+///  be more likely to stress the LLVM loop vectorizer. The code generated will
+///  contain either a single loop or two nested loops.
 ///
 //===----------------------------------------------------------------------===//
 
 syntax = "proto2";
 
 message Const {
   required int32 val = 1;
 }
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;

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

 //==-- loop_proto_to_cxx.cpp - Protobuf-C++ conversion ---------------------==//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Implements functions for converting between protobufs and C++. Differs from
-// proto_to_cxx.cpp by wrapping all the generated C++ code in a single for
-// loop. Also coutputs a different function signature that includes a
-// size_t parameter for the loop to use. The C++ code generated is meant to
-// stress the LLVM loop vectorizer.
+// proto_to_cxx.cpp by wrapping all the generated C++ code in either a single
+// for loop or two nested loops. Also outputs a different function signature
+// that includes a size_t parameter for the loop to use. The C++ code generated
+// is meant to stress the LLVM loop vectorizer.
 //
 // Still a work in progress.
 //
 //===----------------------------------------------------------------------===//
 
 #include "cxx_loop_proto.pb.h"
 #include "proto_to_cxx.h"
 
 // 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();

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();