Thread safety analysis: Unwrap __builtin_expect in getTrylockCallExpr

[aaronpuchert]

Summary

When people are really sure they'll get the lock they sometimes use
__builtin_expect. It's also used by some assertion implementations.
Asserting that try-lock succeeded is basically the same as asserting
that the lock is not held by anyone else (and acquiring it).

[aaron.ballman]

LGTM, but you should give @delesley a chance to weigh in before you commit.

[aaronpuchert]

No problem. Thanks for reviewing! I'm terribly sorry to be bombarding the two of you with so many review requests lately, and I hope it'll soon be over.

[aaron.ballman]

In D52398#1244074, @aaronpuchert wrote:

No problem. Thanks for reviewing! I'm terribly sorry to be bombarding the two of you with so many review requests lately, and I hope it'll soon be over.

No apologies necessary -- I love and appreciate the work you've been doing on thread safety analysis!

[aaronpuchert]

@delesley Any objections to this?

It's certainly useful for our code base, because our assert-like macros use __builtin_expect, but I'm not sure if that applies to the general public.

[aaron.ballman]

In D52398#1251894, @aaronpuchert wrote:

@delesley Any objections to this?

It's certainly useful for our code base, because our assert-like macros use __builtin_expect, but I'm not sure if that applies to the general public.

I think you're fine to commit -- this seems like an intuitive extension to the functionality; if there are issues, we can revert post-commit.

[hokein]

Hi, @aaronpuchert, the patch has caused many new warnings in our internal codebase, below is a reduced one. Do you mind reverting the patch?

// if the condition is not true, CHECK will terminate the program.
#define CHECK(condition) (__builtin_expect((condition), true)) ? 1 : 0

void foo() {
    CHECK(mu.TryLock()); 
    mu.Unlock();
}

[aaronpuchert]

In D52398#1255148, @hokein wrote:

Hi, @aaronpuchert, the patch has caused many new warnings in our internal codebase, below is a reduced one. Do you mind reverting the patch?

// if the condition is not true, CHECK will terminate the program.
#define CHECK(condition) (__builtin_expect((condition), true)) ? 1 : 0

void foo() {
    CHECK(mu.TryLock()); 
    mu.Unlock();
}

Even before there was another warning in this code: "releasing mutex 'mu' that was not held" on mu.Unlock(). Is there an example that didn't show any warnings before?

And can you confirm that the warning also appeared before if you replace __builtin_expect(x, *) by x? Both are functionally equivalent.

I will have a closer look, but my first feeling is that the problem is not that we unwrap __builtin_expect, but instead that we don't consider the ternary operator ?: in getTrylockCallExpr. I'll see if I can fix that.

[hokein]

In D52398#1255218, @aaronpuchert wrote:

In D52398#1255148, @hokein wrote:

Hi, @aaronpuchert, the patch has caused many new warnings in our internal codebase, below is a reduced one. Do you mind reverting the patch?

// if the condition is not true, CHECK will terminate the program.
#define CHECK(condition) (__builtin_expect((condition), true)) ? 1 : 0

void foo() {
    CHECK(mu.TryLock()); 
    mu.Unlock();
}

Thanks for looking into it!

Even before there was another warning in this code: "releasing mutex 'mu' that was not held" on mu.Unlock(). Is there an example that didn't show any warnings before?

I think the warning of Unlock is not critical here, what matters is the warning on CHECK(mu.TryLock()); . The above example I provided may be not totally correct, I reduced it from a relatively complicated source. I'm confirm that the warning doesn't appear before the patch.

And can you confirm that the warning also appeared before if you replace __builtin_expect(x, *) by x? Both are functionally equivalent.
I will have a closer look, but my first feeling is that the problem is not that we unwrap __builtin_expect, but instead that we don't consider the ternary operator ?: in getTrylockCallExpr. I'll see if I can fix that.

Yeah, your feeling is right. The warning does appear if we replace __builtin_expect by x even before the patch. It seems that getTrylockCallExpr doesn't consider ?:.

You patch is not the root cause of the issue, but our internal integration blocked by the warning, do you mind reverting this patch temporarily until we also fix the getTrylockCallExpr? Thanks very much for the understanding!

[aaronpuchert]

@hokein Please have a look at D52888, maybe you can try it out already. The problem was that ?: expressions are considered a branch point and when merging both branches the warning was emitted. Before this change, we couldn't look into __builtin_expect and so we didn't see that the result of TryLock is used to branch. Take this source:

void foo() {
    if (mu.TryLock() ? 1 : 0)
      mu.Unlock();
}

The CFG is:

void foo()
 [B6 (ENTRY)]
   Succs (1): B5

 [B1]
   1: mu
   2: [B1.1].Unlock
   3: [B1.2]()
   Preds (1): B2
   Succs (1): B0

 [B2]
   1: [B5.3] ? [B3.1] : [B4.1]
   2: [B2.1] (ImplicitCastExpr, IntegralToBoolean, _Bool)
   T: if [B2.2]
   Preds (2): B3 B4
   Succs (2): B1 B0

 [B3]
   1: 1
   Preds (1): B5
   Succs (1): B2

 [B4]
   1: 0
   Preds (1): B5
   Succs (1): B2

 [B5]
   1: mu
   2: [B5.1].TryLock
   3: [B5.2]()
   T: [B5.3] ? ... : ...
   Preds (1): B6
   Succs (2): B3 B4

 [B0 (EXIT)]
   Preds (2): B1 B2

So we start in B5, then call TryLock and branch on ?: into B3 or B4. We find that in B3 the lock is held and in B4 it isn't, so when both merge into B2 we complain that we don't know if the lock is held or not.

I think the proper solution is to not branch on conditionals, and rather introspect them when a "real" branch happens. There is a slight possibility that this might break other use cases, but I hope not.

[rupprecht]

In D52398#1255290, @aaronpuchert wrote:

@hokein Please have a look at D52888, maybe you can try it out already. The problem was that ?: expressions are considered a branch point and when merging both branches the warning was emitted. Before this change, we couldn't look into __builtin_expect and so we didn't see that the result of TryLock is used to branch.

I patched the proposed fix-forward and it seems to have things building again. Is there an ETA on landing that? If it's going to take a bit, is there any chance we could revert this patch until then?

[aaronpuchert]

In D52398#1257092, @rupprecht wrote:

I patched the proposed fix-forward and it seems to have things building again. Is there an ETA on landing that? If it's going to take a bit, is there any chance we could revert this patch until then?

The fix was just committed (rC343902). Generally I'm for reverting if there are functional deficiencies, but here it's more that an unrelated issue was accidentally uncovered by this patch.

[rupprecht]

In D52398#1257133, @aaronpuchert wrote:

In D52398#1257092, @rupprecht wrote:

I patched the proposed fix-forward and it seems to have things building again. Is there an ETA on landing that? If it's going to take a bit, is there any chance we could revert this patch until then?

The fix was just committed (rC343902). Generally I'm for reverting if there are functional deficiencies, but here it's more that an unrelated issue was accidentally uncovered by this patch.

Ah, I thought it was an issue with this patch. Clearly I shouldn't pretend to understand thread analysis :)
Thanks for the fix!

cfe/trunk/lib/Analysis/ThreadSafety.cpp

 #include "clang/AST/Type.h"
 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
 #include "clang/Analysis/Analyses/ThreadSafetyCommon.h"
 #include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
 #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h"
 #include "clang/Analysis/Analyses/ThreadSafetyUtil.h"
 #include "clang/Analysis/AnalysisDeclContext.h"
 #include "clang/Analysis/CFG.h"
+#include "clang/Basic/Builtins.h"
 #include "clang/Basic/LLVM.h"
 #include "clang/Basic/OperatorKinds.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/Specifiers.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/ImmutableMap.h"
 #include "llvm/ADT/Optional.h"

 // The negate variable should be called with false, and will be set to true
 // if the function call is negated, e.g. if (!mu.tryLock(...))
 const CallExpr* ThreadSafetyAnalyzer::getTrylockCallExpr(const Stmt *Cond,
                                                          LocalVarContext C,
                                                          bool &Negate) {
   if (!Cond)
     return nullptr;
 
-  if (const auto *CallExp = dyn_cast<CallExpr>(Cond))
+  if (const auto *CallExp = dyn_cast<CallExpr>(Cond)) {
+    if (CallExp->getBuiltinCallee() == Builtin::BI__builtin_expect)
+      return getTrylockCallExpr(CallExp->getArg(0), C, Negate);
     return CallExp;
+  }
   else if (const auto *PE = dyn_cast<ParenExpr>(Cond))
     return getTrylockCallExpr(PE->getSubExpr(), C, Negate);
   else if (const auto *CE = dyn_cast<ImplicitCastExpr>(Cond))
     return getTrylockCallExpr(CE->getSubExpr(), C, Negate);
   else if (const auto *EWC = dyn_cast<ExprWithCleanups>(Cond))
     return getTrylockCallExpr(EWC->getSubExpr(), C, Negate);
   else if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) {
     const Expr *E = LocalVarMap.lookupExpr(DRE->getDecl(), C);

cfe/trunk/test/SemaCXX/warn-thread-safety-analysis.cpp

struct TestTryLock {
   }
 
   void foo2() {
     if (!mu.TryLock()) return;
     a = 2;
     mu.Unlock();
   }
 
+  void foo2_builtin_expect() {
+    if (__builtin_expect(!mu.TryLock(), false))
+      return;
+    a = 2;
+    mu.Unlock();
+  }
+
   void foo3() {
     bool b = mu.TryLock();
     if (b) {
       a = 3;
       mu.Unlock();
     }
   }
 
+  void foo3_builtin_expect() {
+    bool b = mu.TryLock();
+    if (__builtin_expect(b, true)) {
+      a = 3;
+      mu.Unlock();
+    }
+  }
+
   void foo4() {
     bool b = mu.TryLock();
     if (!b) return;
     a = 4;
     mu.Unlock();
   }
 
   void foo5() {