[clang] add __builtin_unpredictable and convert to metadata

[spatel]

Summary

This patch depends on D12341 ('unpredictable' metadata type for LLVM).

For now, I am ignoring the horrible thought that this builtin might take an extra parameter to distinguish different hardware. :)

The goal is to make LLVM generate different code for these functions for a target that has cheap branches (see PR23827 for more details):

int foo();
int normal(int x, int y, int z) {
   if (x != 0 && y != 0) return foo();
   return 1;
}

int crazy(int x, int y) {
   if (__builtin_unpredictable(x != 0 && y != 0)) return foo();
   return 1;
}

[kparzysz]

lib/CodeGen/CodeGenFunction.cpp

1238

Is the definition of CreateCondBr actually updated somewhere? I didn't see it in any other patch.

[spatel]

lib/CodeGen/CodeGenFunction.cpp

1238

Yes - please see the 2nd hunk in IRBuilder.h in D12341.

[spatel]

lib/CodeGen/CodeGenFunction.cpp

1238

[the previous reply didn't make it to the commits list...trying again]
Yes - please see the 2nd hunk in IRBuilder.h in D12341.

[kparzysz]

LGTM

lib/CodeGen/CodeGenFunction.cpp

1238

You're right. I see it.

docs/LanguageExtensions.rst

 
 The ``__builtin_unreachable()`` builtin has completely undefined behavior.
 Since it has undefined behavior, it is a statement that it is never reached and
 the optimizer can take advantage of this to produce better code.  This builtin
 takes no arguments and produces a void result.
 
 Query for this feature with ``__has_builtin(__builtin_unreachable)``.
 
+``__builtin_unpredictable``
+-------------------------
+
+``__builtin_unpredictable`` is used to indicate that a branch condition is
+unpredictable by hardware mechanisms such as branch prediction logic.
+
+**Syntax**:
+
+.. code-block:: c++
+
+    __builtin_unpredictable(long long)
+
+**Example of use**:
+
+.. code-block:: c++
+
+  if (__builtin_unpredictable(x > 0)) {
+     foo();
+  }
+
+**Description**:
+
+The ``__builtin_unpredictable()`` builtin is expected to be used with control
+flow conditions such as in ``if`` and ``switch`` statements.
+
+Query for this feature with ``__has_builtin(__builtin_unpredictable)``.
+
 ``__sync_swap``
 ---------------
 
 ``__sync_swap`` is used to atomically swap integers or pointers in memory.
 
 **Syntax**:
 
 .. code-block:: c++

include/clang/Basic/Builtins.def

 BUILTIN(__builtin___sprintf_chk, "ic*izcC*.", "Fp:3:")
 BUILTIN(__builtin___vsnprintf_chk, "ic*zizcC*a", "FP:4:")
 BUILTIN(__builtin___vsprintf_chk, "ic*izcC*a", "FP:3:")
 BUILTIN(__builtin___fprintf_chk, "iP*icC*.", "Fp:2:")
 BUILTIN(__builtin___printf_chk, "iicC*.", "Fp:1:")
 BUILTIN(__builtin___vfprintf_chk, "iP*icC*a", "FP:2:")
 BUILTIN(__builtin___vprintf_chk, "iicC*a", "FP:1:")
 
+BUILTIN(__builtin_unpredictable, "LiLi"   , "nc")
 BUILTIN(__builtin_expect, "LiLiLi"   , "nc")
 BUILTIN(__builtin_prefetch, "vvC*.", "nc")
 BUILTIN(__builtin_readcyclecounter, "ULLi", "n")
 BUILTIN(__builtin_trap, "v", "nr")
 BUILTIN(__builtin_debugtrap, "v", "n")
 BUILTIN(__builtin_unreachable, "v", "nr")
 BUILTIN(__builtin_shufflevector, "v."   , "nc")
 BUILTIN(__builtin_convertvector, "v."   , "nct")

lib/CodeGen/CGBuiltin.cpp

case Builtin::BI__builtin_popcountll: {
 
     llvm::Type *ResultType = ConvertType(E->getType());
     Value *Result = Builder.CreateCall(F, ArgValue);
     if (Result->getType() != ResultType)
       Result = Builder.CreateIntCast(Result, ResultType, /*isSigned*/true,
                                      "cast");
     return RValue::get(Result);
   }
+  case Builtin::BI__builtin_unpredictable: {
+    // Always return the argument of __builtin_unpredictable. LLVM does not
+    // handle this builtin. Metadata for this builtin should be added directly
+    // to instructions such as branches or switches that use it.
+    return RValue::get(EmitScalarExpr(E->getArg(0)));
+  }
   case Builtin::BI__builtin_expect: {
     Value *ArgValue = EmitScalarExpr(E->getArg(0));
     llvm::Type *ArgType = ArgValue->getType();
 
     Value *ExpectedValue = EmitScalarExpr(E->getArg(1));
     // Don't generate llvm.expect on -O0 as the backend won't use it for
     // anything.
     // Note, we still IRGen ExpectedValue because it could have side-effects.

lib/CodeGen/CodeGenFunction.cpp

 #include "CGOpenMPRuntime.h"
 #include "CodeGenModule.h"
 #include "CodeGenPGO.h"
 #include "TargetInfo.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/StmtCXX.h"
+#include "clang/Basic/Builtins.h"
 #include "clang/Basic/TargetInfo.h"
 #include "clang/CodeGen/CGFunctionInfo.h"
 #include "clang/Frontend/CodeGenOptions.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Operator.h"
 using namespace clang;
if (const CXXThrowExpr *Throw = dyn_cast<CXXThrowExpr>(Cond)) {
     // condition for a case like:
     //   br(c ? throw x : y, t, f) -> br(c, br(throw x, t, f), br(y, t, f)
     // Fold this to:
     //   br(c, throw x, br(y, t, f))
     EmitCXXThrowExpr(Throw, /*KeepInsertionPoint*/false);
     return;
   }
 
+  // If the branch has a condition wrapped by __builtin_unpredictable,
+  // create metadata that specifies that the branch is unpredictable.
+  // Don't bother if not optimizing because that metadata would not be used.
+  llvm::MDNode *Unpredictable = nullptr;
+  if (CGM.getCodeGenOpts().OptimizationLevel != 0) {
+    if (const CallExpr *Call = dyn_cast<CallExpr>(Cond)) {
+      const Decl *TargetDecl = Call->getCalleeDecl();
+      if (const FunctionDecl *FD = dyn_cast_or_null<FunctionDecl>(TargetDecl)) {
+        if (FD->getBuiltinID() == Builtin::BI__builtin_unpredictable) {
+          // Unpredictable metadata is a percentage from 0 (completely
+          // predictable) to 100 (completely unpredictable). If the program has
+          // this hint, we assume the branch is completely unpredictable.
+          llvm::MDBuilder MDHelper(getLLVMContext());
+          Unpredictable = MDHelper.createUnpredictable(100);
+        }
+      }
+    }
+  }
+
   // Create branch weights based on the number of times we get here and the
   // number of times the condition should be true.
   uint64_t CurrentCount = std::max(getCurrentProfileCount(), TrueCount);
   llvm::MDNode *Weights =
       createProfileWeights(TrueCount, CurrentCount - TrueCount);
 
   // Emit the code with the fully general case.
   llvm::Value *CondV;
   {
     ApplyDebugLocation DL(*this, Cond);
     CondV = EvaluateExprAsBool(Cond);
   }
-  Builder.CreateCondBr(CondV, TrueBlock, FalseBlock, Weights);
+  Builder.CreateCondBr(CondV, TrueBlock, FalseBlock, Weights, Unpredictable);
 }
 
 /// ErrorUnsupported - Print out an error that codegen doesn't support the
 /// specified stmt yet.
 void CodeGenFunction::ErrorUnsupported(const Stmt *S, const char *Type) {
   CGM.ErrorUnsupported(S, Type);
 }
 

lib/StaticAnalyzer/Checkers/BuiltinFunctionChecker.cpp

bool BuiltinFunctionChecker::evalCall(const CallExpr *CE,
   const LocationContext *LCtx = C.getLocationContext();
   if (!FD)
     return false;
 
   switch (FD->getBuiltinID()) {
   default:
     return false;
 
+  case Builtin::BI__builtin_unpredictable:
   case Builtin::BI__builtin_expect:
   case Builtin::BI__builtin_assume_aligned:
   case Builtin::BI__builtin_addressof: {
-    // For __builtin_expect and __builtin_assume_aligned, just return the value
-    // of the subexpression.
+    // For __builtin_unpredictable, __builtin_expect, and
+    // __builtin_assume_aligned, just return the value of the subexpression.
     // __builtin_addressof is going from a reference to a pointer, but those
     // are represented the same way in the analyzer.
     assert (CE->arg_begin() != CE->arg_end());
     SVal X = state->getSVal(*(CE->arg_begin()), LCtx);
     C.addTransition(state->BindExpr(CE, LCtx, X));
     return true;
   }
 

test/CodeGen/builtin-unpredictable.c

+// RUN: %clang_cc1 -triple x86_64-unknown-unknown -emit-llvm -o - %s -O1 | FileCheck %s
+// RUN: %clang_cc1 -triple x86_64-unknown-unknown -emit-llvm -o - %s -O0 | FileCheck %s --check-prefix=CHECK_O0
+
+// When optimizing, the builtin should be converted to metadata.
+// When not optimizing, there should be no metadata created for the builtin.
+// In both cases, the builtin should be removed from the code.
+
+void foo();
+void branch(int x) {
+// CHECK-LABEL: define void @branch(
+
+// CHECK-NOT: builtin_unpredictable
+// CHECK: !unpredictable [[METADATA:.+]]
+// CHECK: [[METADATA]] = !{i8 100}
+
+// CHECK_O0-NOT: builtin_unpredictable
+// CHECK_O0-NOT: !unpredictable 
+
+  if (__builtin_unpredictable(x > 0))
+    foo ();
+}
+
+// TODO: Add metadata for unpredictable switches.
+int unpredictable_switch(int x) {
+  switch(__builtin_unpredictable(x)) {
+  default:
+    return 0;
+  case 0:
+  case 1:
+  case 2:
+    return 1;
+  case 5:
+    return 5;
+  };
+
+  return 0;
+}