[clang][dataflow] Add support for clang's `__builtin_expect`.

[ymandel]

Summary

This patch adds basic modeling of __builtin_expect, just to propagate the
(first) argument, making the call transparent.

Driveby: adds tests for proper handling of some other builtins.

[xazax.hun]

Nice!

Speaking of builtins, it might be great to add tests for __builtin_unreachable, __builtin_trap, __builtin_debugtrap. The CFG might already have the right shape so we might not need to add any code to support them. But it would be nice to know :) Maybe we could even add a comment to VisitCallExpr why those wouldn't need explicit support.

[ymandel]

add tests for other builtins.

[ymandel]

comment

clang/lib/Analysis/FlowSensitive/Transfer.cpp

 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/Expr.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/OperationKinds.h"
 #include "clang/AST/Stmt.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/Analysis/FlowSensitive/DataflowEnvironment.h"
 #include "clang/Analysis/FlowSensitive/Value.h"
+#include "clang/Basic/Builtins.h"
 #include "clang/Basic/OperatorKinds.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Casting.h"
 #include <cassert>
 #include <memory>
 #include <tuple>
 
 namespace clang {
public:
   void VisitCXXTemporaryObjectExpr(const CXXTemporaryObjectExpr *S) {
     auto &Loc = Env.createStorageLocation(*S);
     Env.setStorageLocation(*S, Loc);
     if (Value *Val = Env.createValue(S->getType()))
       Env.setValue(Loc, *Val);
   }
 
   void VisitCallExpr(const CallExpr *S) {
+    // Of clang's builtins, only `__builtin_expect` is handled explicitly, since
+    // others (like trap, debugtrap, and unreachable) are handled by CFG
+    // construction.
     if (S->isCallToStdMove()) {
       assert(S->getNumArgs() == 1);
 
       const Expr *Arg = S->getArg(0);
       assert(Arg != nullptr);
 
       auto *ArgLoc = Env.getStorageLocation(*Arg, SkipPast::None);
       if (ArgLoc == nullptr)
         return;
 
       Env.setStorageLocation(*S, *ArgLoc);
+    } else if (S->getDirectCallee() != nullptr &&
+               S->getDirectCallee()->getBuiltinID() ==
+                   Builtin::BI__builtin_expect) {
+      assert(S->getNumArgs() > 0);
+      assert(S->getArg(0) != nullptr);
+      // `__builtin_expect` returns by-value, so strip away any potential
+      // references in the argument.
+      auto *ArgLoc = Env.getStorageLocation(
+          *S->getArg(0)->IgnoreParenImpCasts(), SkipPast::Reference);
+      if (ArgLoc == nullptr)
+        return;
+      Env.setStorageLocation(*S, *ArgLoc);
     }
   }
 
   void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *S) {
     const Expr *SubExpr = S->getSubExpr();
     assert(SubExpr != nullptr);
 
     auto *SubExprLoc = Env.getStorageLocation(*SubExpr, SkipPast::None);

clang/unittests/Analysis/FlowSensitive/TransferTest.cpp

runDataflow(Code,
                 const auto *BarVal = dyn_cast_or_null<NegationValue>(
                     Env.getValue(*BarDecl, SkipPast::None));
                 ASSERT_THAT(BarVal, NotNull());
 
                 EXPECT_EQ(&BarVal->getSubVal(), FooVal);
               });
 }
 
+TEST_F(TransferTest, BuiltinExpect) {
+  std::string Code = R"(
+    void target(long Foo) {
+      long Bar = __builtin_expect(Foo, true);
+      /*[[p]]*/
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const auto &Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                EXPECT_EQ(Env.getValue(*FooDecl, SkipPast::None),
+                          Env.getValue(*BarDecl, SkipPast::None));
+              });
+}
+
+TEST_F(TransferTest, BuiltinUnreachable) {
+  std::string Code = R"(
+    void target(bool Foo) {
+      bool Bar = false;
+      if (Foo)
+        Bar = Foo;
+      else
+        __builtin_unreachable();
+      (void)0;
+      /*[[p]]*/
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const auto &Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                // `__builtin_unreachable` promises that the code is
+                // unreachable, so the compiler treats the "then" branch as the
+                // only possible predecessor of this statement.
+                EXPECT_EQ(Env.getValue(*FooDecl, SkipPast::None),
+                          Env.getValue(*BarDecl, SkipPast::None));
+              });
+}
+
+TEST_F(TransferTest, BuiltinTrap) {
+  std::string Code = R"(
+    void target(bool Foo) {
+      bool Bar = false;
+      if (Foo)
+        Bar = Foo;
+      else
+        __builtin_trap();
+      (void)0;
+      /*[[p]]*/
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const auto &Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                // `__builtin_trap` ensures program termination, so only the
+                // "then" branch is a predecessor of this statement.
+                EXPECT_EQ(Env.getValue(*FooDecl, SkipPast::None),
+                          Env.getValue(*BarDecl, SkipPast::None));
+              });
+}
+
+TEST_F(TransferTest, BuiltinDebugTrap) {
+  std::string Code = R"(
+    void target(bool Foo) {
+      bool Bar = false;
+      if (Foo)
+        Bar = Foo;
+      else
+        __builtin_debugtrap();
+      (void)0;
+      /*[[p]]*/
+    }
+  )";
+  runDataflow(Code,
+              [](llvm::ArrayRef<
+                     std::pair<std::string, DataflowAnalysisState<NoopLattice>>>
+                     Results,
+                 ASTContext &ASTCtx) {
+                ASSERT_THAT(Results, ElementsAre(Pair("p", _)));
+                const auto &Env = Results[0].second.Env;
+
+                const ValueDecl *FooDecl = findValueDecl(ASTCtx, "Foo");
+                ASSERT_THAT(FooDecl, NotNull());
+
+                const ValueDecl *BarDecl = findValueDecl(ASTCtx, "Bar");
+                ASSERT_THAT(BarDecl, NotNull());
+
+                // `__builtin_debugtrap` doesn't ensure program termination.
+                EXPECT_NE(Env.getValue(*FooDecl, SkipPast::None),
+                          Env.getValue(*BarDecl, SkipPast::None));
+              });
+}
+
 TEST_F(TransferTest, StaticIntSingleVarDecl) {
   std::string Code = R"(
     void target() {
       static int Foo;
       // [[p]]
     }
   )";
   runDataflow(Code,