[mycpp/dataflow] add stack roots solver

[melvinw]

This patch adds a stack roots solver written in souffle. It uses the facts and control flow graph emitted by control_flow_pass to compute a minimal (approximately) set of stack roots required for safe execution of the source program. The relations and rules for this program, AKA our rooting policy, are derived from the examples enumerated in the translation example added in #2030.

If mycpp is run with the --minimize-stack-roots flag, it will execute the stack roots solver and feed its output into cppgen_pass where it will be queried to determine if a StackRoot should be emitted for a local variable. When --minimize-stack-roots is set, cppgen_pass will also omit stack roots for loop index variables. Without --minimize-stack-roots there are no changes to the generated code produced by cppgen_pass.

Running mycpp with --minimize-stack-roots reduces the number of stack roots in _gen/bin/oils_for_unix.mycpp.cc by ~78%!

Before

$ grep StackRoot _gen/bin/oils_for_unix.mycpp.cc | wc -l
4744

After

$ grep StackRoot _gen/bin/oils_for_unix.mycpp.cc | wc -l
1001

[melvinw]

OK. Plugged this into cppgen_pass. I also removed the roots for loop index variables like we talked about on the call the other day @andychu. Here's the diff of the generated code for the new example:

diff --git a/home/melvin/gc_stack_roots.mycpp.cc b/_gen/mycpp/examples/gc_stack_roots.mycpp.cc
index 4002d4d40..cc46fafa0 100644
--- a/home/melvin/gc_stack_roots.mycpp.cc
+++ b/_gen/mycpp/examples/gc_stack_roots.mycpp.cc
@@ -64,11 +64,8 @@ namespace gc_stack_roots {  // define

 void print_list(List<BigStr*>* l) {
-  StackRoot _root0(&l);
-
   for (ListIter<BigStr*> it(l); !it.Done(); it.Next()) {
     BigStr* s = it.Value();
-    StackRoot _for(&s  );
     print(s);
   }
 }
@@ -109,8 +106,6 @@ ctx_Stasher::~ctx_Stasher() {

 void no_collect() {
   List<BigStr*>* l = nullptr;
-  StackRoot _root0(&l);
-
   l = NewList<BigStr*>(std::initializer_list<BigStr*>{str0, str1});
   print_list(l);
 }
@@ -119,7 +114,6 @@ void simple_collect() {
   List<BigStr*>* l1 = nullptr;
   List<BigStr*>* l2 = nullptr;
   StackRoot _root0(&l1);
-  StackRoot _root1(&l2);

   l1 = NewList<BigStr*>(std::initializer_list<BigStr*>{str2, str3});
   l2 = NewList<BigStr*>(std::initializer_list<BigStr*>{str4, str5});
@@ -142,8 +136,7 @@ void indirect_collect() {
 void arg_roots() {
   List<BigStr*>* l1 = nullptr;
   List<BigStr*>* l2 = nullptr;
-  StackRoot _root0(&l1);
-  StackRoot _root1(&l2);
+  StackRoot _root0(&l2);

   l1 = NewList<BigStr*>(std::initializer_list<BigStr*>{str8});
   ignore_and_collect(l1);
@@ -155,8 +148,7 @@ void arg_roots() {
 void alias() {
   List<BigStr*>* l1 = nullptr;
   List<BigStr*>* l2 = nullptr;
-  StackRoot _root0(&l1);
-  StackRoot _root1(&l2);
+  StackRoot _root0(&l2);

   l1 = NewList<BigStr*>(std::initializer_list<BigStr*>{str11, str12});
   l2 = l1;
@@ -175,7 +167,6 @@ void collect_scoped_resource() {
 void collect_in_loop() {
   for (ListIter<BigStr*> it(NewList<BigStr*>(std::initializer_list<BigStr*>{str15, str16})); !it.Done(); it.Next()) {
     BigStr* s = it.Value();
-    StackRoot _for(&s  );
     mylib::MaybeCollect();
     print(s);
   }
@@ -192,7 +183,6 @@ void collect_in_comprehension() {
   }
   for (ListIter<BigStr*> it(l); !it.Done(); it.Next()) {
     BigStr* s = it.Value();
-    StackRoot _for(&s  );
     print(s);
   }
 }

[melvinw]

We should do a diff on _gen/mycpp/examples/gc_stack_roots.mycpp.cc too

[andychu]

OK cool

It might be possible to add a build variant even, like _gen/bin/oils_for_unix.mycpp_souffle.cc

And maybe only an ASAN build of that one

then we can diff them in the tree even

[melvinw]

Oh yeah, that would be good. I'll tweak this so it's off by default unless some build flag is set

[melvinw]

OK this is opt-in now. You can run mycpp with --minimize-stack-roots from the new variant

[andychu]

Oh is this ready to review? Not draft anymore?

[melvinw]

Oh, whoops! I totally forgot to change the status. I think it's ready for a look.

[andychu]

Also it would be helpful to write a full commit description with the details, since there is a bunch of stuff going on

Including a summary of what changed

Is everything hidden behind a flag, or are there some changes to generated code?

[melvinw]

Oh yes, definitely. Just updated the PR description with some details. Let me know if anything needs to be clarified further

[andychu]

OK great thanks, merged!

If we decided we don't need _for roots at all, we could turn that off first as a separate change

It will make it easier to bisect later in case we need to