Changed how LLVM IR was generated to increase vectorization

[emmettneyman]

Summary

Changed the structure of the generated IR to make it easier to vectorize

[morehouse]

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

134

What does pc mean in this triple? I'm used to seeing x86_64-unknown-linux-gnu.

135

Does removing the variable names really make this easier to vectorize?

138

Does removing branch names really make this easier to vectorize?

[emmettneyman]

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

134

It's probably generating pc since I'm using my desktop. I'll change it to unknown so it's not platform-specific.

135

It doesn't, I just thought it was cleaner and produced slightly smaller IR. It also more closely mimics the behavior of the -emit-llvm flag.

138

Same answer as above. Should I change these back?

[emmettneyman]

Changed pc to unknown

[morehouse]

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

138

I think the previous labels were more human-readable.

[emmettneyman]

Added back more descriptive variable and loop names

[morehouse]

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

127

Should %s be signed? Do we want unsigned compare here?

134

Seems like the endloop label is unnecessary. Does this help vectorize? If not, lets get rid of unconditional jumps to the next line.

136–138

This will make overflow undefined... Isn't that the opposite of what we want? That will permit LLVM to assume overflow never happens and modify the code in new ways based on that assumption.

[emmettneyman]

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

127

I don't think it matters since %s will always be positive (it will always be equal to
kArraySize from input_arrays.h).

134

I initially had it this way since that's how -emit-llvm generated the code. But it doesn't seem like it's necessary for loops to be vectorized upon further inspection.

136–138

That's a good point. It probably won't matter since this addition will never overflow (we're just starting at zero and incrementing by one). This is what was generated by -emit-llvm. I'll remove it to reduce confusion.

[emmettneyman]

Some small fixes to improve simplicity of generated IR

[emmettneyman]

Rebased and ready to land

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

std::string VarRefToString(std::ostream &os, const VarRef &x) {
   case VarRef::ARR_B:
     arr = "%b";
     break;
   case VarRef::ARR_C:
     arr = "%c";
     break;
   }
   std::string ptr_var = get_var();
-  os << ptr_var << " = getelementptr i32, i32* " << arr << ", i64 %ct\n";
+  os << ptr_var << " = getelementptr inbounds i32, i32* " << arr << ", i64 %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 StatementSeq &x) {
   for (auto &st : x.statements()) {
     os << st;
   }
   return os;
 }
 std::ostream &operator<<(std::ostream &os, const LoopFunction &x) {
-  return os << "define void @foo(i32* %a, i32* %b, i32* noalias %c, i64 %s) {\n"
-            << "%i = alloca i64\n"
-            << "store i64 0, i64* %i\n"
-            << "br label %loop\n\n"
+  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 = load i64, i64* %i\n"
-            << "%comp = icmp eq i64 %ct, %s\n"
-            << "br i1 %comp, label %endloop, label %body\n\n"
-            << "body:\n"
+            << " %ct   = phi i64 [ %ctnew, %loop ], [ 0, %start ]\n"
             << x.statements()
-            << "%z = add i64 1, %ct\n"
-            << "store i64 %z, i64* %i\n"
-            << "br label %loop\n\n"
-            << "endloop:\n"
-            << "ret void\n}\n";
+            << "%ctnew = add i64 %ct, 1\n"
+            << "%j = icmp eq i64 %ctnew, %s\n"
+            << "br i1 %j, label %end, label %loop\n}\n";
 }
 
 // ---------------------------------
 
 std::string LoopFunctionToLLVMString(const LoopFunction &input) {
   std::ostringstream os;
   os << input;
   return os.str();