This is an archive of the discontinued LLVM Phabricator instance.

Implementation of nested loops in cxx_loop_proto
ClosedPublic

Authored by emmettneyman on Aug 13 2018, 3:37 PM.

Details

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.

Diff Detail

Repository
rC Clang

Event Timeline

emmettneyman created this revision.Aug 13 2018, 3:37 PM

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

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.

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

Yes, I'd recommend doing that.

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

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

emmettneyman retitled this revision from Implementation of multiple loops in cxx_loop_proto to Implementation of nested loops in cxx_loop_proto.Aug 14 2018, 6:12 PM
emmettneyman edited the summary of this revision. (Show Details)

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.

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 edited the summary of this revision. (Show Details)

Small changes to generated IR

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

morehouse added inline comments.Aug 15 2018, 11:35 AM
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 added inline comments.Aug 15 2018, 1:15 PM
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 added inline comments.Aug 15 2018, 1:40 PM
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 updated this revision to Diff 160920.EditedAug 15 2018, 2:37 PM

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

morehouse added inline comments.Aug 15 2018, 3:15 PM
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.

Changed modifying global var to scoped class

morehouse accepted this revision.Aug 15 2018, 3:56 PM
This revision is now accepted and ready to land.Aug 15 2018, 3:56 PM

Updated comments, rebased, and ready to land

This revision was automatically updated to reflect the committed changes.