[clang][dataflow] Change PruneTriviallyFalseEdges for building CFG

[kinu]

Summary

Keeping this false could end up with extra iterations on a lot of loops
that aren't real ones (e.g. they could be a do-while-false for macros),
and makes the analyses very slow.

This patch changes the default for
CFG::BuildOptions.PruneTriviallyFalseEdges to true to avoid it.

[gribozavr2]

Is it testable? For example, can we show that we don't compute the program state for the program point "p" here:

void f() {
  while (true) {
  }
  /*p*/
}

[kinu]

Add a while-true test

[kinu]

In D149640#4311889, @gribozavr2 wrote:

Is it testable? For example, can we show that we don't compute the program state for the program point "p" here:

I added a simple test, how does it look?

[mboehme]

In D149640#4311963, @kinu wrote:

In D149640#4311889, @gribozavr2 wrote:

Is it testable? For example, can we show that we don't compute the program state for the program point "p" here:

I added a simple test, how does it look?

Do we even need to add a new test for this?

This change breaks the existing test TransferTest.VarDeclInDoWhile, which tests essentially the same scenario, so it's probably sufficient to just update that test?

[ymandel]

Thank you!

[kinu]

Changing the existing test to reflect the flag change

[gribozavr2]

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

2642

Could you update the test name to reflect what the test is checking now? (the comment that you added below)

[mboehme]

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

2674

It's unfortuante that all of these checks have gone away. I think the test was actually trying to test something.

I'd suggest checking the environment at two different places:

void target(int *Foo) {
  do {
    int Bar = *Foo;
    // [[in_loop]]
  } while (true);
  (void)0;
  // [[after_loop]]
}

You can keep the existing checks for the in_loop environment and verify that Results doesn't actually contain an environment for after_loop.

[kinu]

(comment only)

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

2674

Wdyt if we change this to exercise do { } while (false) instead (with the checks that we already have), and add a simple while (true) {}?

[kinu]

Updated changes further not to lose the existing checks with the do-while test.

Also restored the simplest test that exercises the while-true one.

[ymandel]

LGTM

[mboehme]

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

2674

Thanks, good idea!

2691

This comment looks stale?

[kinu]

Updated the stale comment.

[kinu]

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

2691

Good catch, updated!

clang/lib/Analysis/FlowSensitive/ControlFlowContext.cpp

static llvm::BitVector findReachableBlocks(const CFG &Cfg) {
   }
 
   return BlockReachable;
 }
 
 llvm::Expected<ControlFlowContext>
 ControlFlowContext::build(const Decl *D, Stmt &S, ASTContext &C) {
   CFG::BuildOptions Options;
-  Options.PruneTriviallyFalseEdges = false;
+  Options.PruneTriviallyFalseEdges = true;
   Options.AddImplicitDtors = true;
   Options.AddTemporaryDtors = true;
   Options.AddInitializers = true;
   Options.AddCXXDefaultInitExprInCtors = true;
 
   // Ensure that all sub-expressions in basic blocks are evaluated.
   Options.setAllAlwaysAdd();
 

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(
             dyn_cast<StructValue>(Env.getValue(*BazDecl, SkipPast::None));
         ASSERT_THAT(BazVal, NotNull());
 
         EXPECT_NE(BazVal, FooVal);
         EXPECT_NE(BazVal, BarVal);
       });
 }
 
 TEST(TransferTest, VarDeclInDoWhile) {
   std::string Code = R"(
     void target(int *Foo) {
       do {
         int Bar = *Foo;
-      } while (true);
+      } while (false);
       (void)0;
       /*[[p]]*/
     }
   )";
   runDataflow(
       Code,
       [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
          ASTContext &ASTCtx) {
runDataflow(
             cast<PointerValue>(Env.getValue(*FooDecl, SkipPast::None));
         const auto *FooPointeeVal =
             cast<IntegerValue>(Env.getValue(FooVal->getPointeeLoc()));
 
         const auto *BarVal = dyn_cast_or_null<IntegerValue>(
             Env.getValue(*BarDecl, SkipPast::None));
         ASSERT_THAT(BarVal, NotNull());
 
         EXPECT_EQ(BarVal, FooPointeeVal);
       });
 }
 
+TEST(TransferTest, UnreachableAfterWhileTrue) {
+  std::string Code = R"(
+    void target() {
+      while (true) {}
+      (void)0;
+      /*[[p]]*/
+    }
+  )";
+  runDataflow(
+      Code,
+      [](const llvm::StringMap<DataflowAnalysisState<NoopLattice>> &Results,
+         ASTContext &ASTCtx) {
+        // The node after the while-true is pruned because it is trivially
+        // known to be unreachable.
+        ASSERT_TRUE(Results.empty());
+      });
+}
+
 TEST(TransferTest, AggregateInitialization) {
   std::string BracesCode = R"(
     struct A {
       int Foo;
     };
 
     struct B {
       int Bar;