[BPI] Adjust the probability for floating point unordered comparison

[Carrot]

Summary

Since NaN is very rare in normal programs, so the probability for floating point unordered comparison should be extremely small. Current probability is 3/8, it is too large, this patch changes it to a tiny number.

[ebrevnov]

I've never looked to this piece of code before. For that reason I would like some one more familiar with this part to make a review.

[scanon]

lib/Analysis/BranchProbabilityInfo.cpp

122

How was this weight selected? Why 2**20 - 1 in particular? If it's just to match IH_TAKEN_WEIGHT, let's use that value instead of repeating it here.

The comment could probable use a little work, too. I broadly agree with the *effect* of this change, but I don't think that unordered is that rare--rather, NaN is often an indication that something has gone wrong, and it makes sense to move that off the hot path.

[Carrot]

Comment change.

lib/Analysis/BranchProbabilityInfo.cpp

122

It has no semantic relation with IH_TAKEN_WEIGHT, I looked for an appropriate weight to represent the extremely likely probability, and IH_TAKEN_WEIGHT has the similar effect on control flow, so I used the same number.

Do you still think it's better to use IH_TAKEN_WEIGHT here, or what probability is more appropriate here?

[xbolva00]

What about

if(isnan(x)) ?

LLVM IR has __isnan call.

[Carrot]

isnan() is lowered to fcmp uno, in this case the taken probability may be higher, but still much smaller than ordered result, and the usage of isnan() is already very rare, most of uno comparisons are generated from different math library functions.
On the other side I guess most of the taken uno comparisons in a correct program comes from explicitly isnan() call.

[Carrot]

ping

[scanon]

It's not that NaN is rare in normal programs, or that it indicates a bug in the code. It's that testing for NaN is usually an indication that you're testing for an exceptional case, and it makes sense to move those off the hot path (i.e. NaN is actually pretty common, but the likelihood of handling it on the normal-value path through code is small).

test/CodeGen/SystemZ/call-05.ll

456

I know nothing about Z architecture; is this codegen change actually an improvement? What architectural considerations are at work here?

[Carrot]

test/CodeGen/SystemZ/call-05.ll

456

In this case, the machine code if conversion only considers branch and a target with non trivial probability, the original probability is 3/8, large enough to enable this if conversion. After reducing the probability, if conversion thinks it is too small, not worth the effort to optimize it.

[kpn]

What will this do to software that does frequently use NaNs and doesn't treat them as exceptional?

[davidxl]

static prediction is intended to help common use cases, so for corner cases when NaNs are used frequently, user will need to resort to source annotation (such as builtin_expect).

[Carrot]

ping

[xbolva00]

I think this change makes sense for plain static mode.

[davidxl]

some benchmark numbers?

[xbolva00]

I think this patch was motivated by the perf of some (micro)benchmarks attached in @Carrot’s previous patch and patch fixes the perf issue.

But I agree, more benchmark results would be useful.

[Carrot]

In D65303#1661329, @davidxl wrote:

some benchmark numbers?

It brings back 35% regression of Evgeniy's micro benchmark.

SPEC 2006 is running.

[Carrot]

spec 2006 int result is 39.2 vs 39.3, so no change.

lib/Analysis/BranchProbabilityInfo.cpp

 static const uint32_t PH_NONTAKEN_WEIGHT = 12;
 
 static const uint32_t ZH_TAKEN_WEIGHT = 20;
 static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
 
 static const uint32_t FPH_TAKEN_WEIGHT = 20;
 static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
 
+/// This is the probability for an ordered floating point comparison.
+static const uint32_t FPH_ORD_WEIGHT = 1024 * 1024 - 1;
+/// This is the probability for an unordered floating point comparison, it means
+/// one or two of the operands are NaN, it should be extremely rare.
+static const uint32_t FPH_UNO_WEIGHT = 1;
+
 /// Invoke-terminating normal branch taken weight
 ///
 /// This is the weight for branching to the normal destination of an invoke
 /// instruction. We expect this to happen most of the time. Set the weight to an
 /// absurdly high value so that nested loops subsume it.
 static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
 
 /// Invoke-terminating normal branch not-taken weight.
bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
   if (!BI || !BI->isConditional())
     return false;
 
   Value *Cond = BI->getCondition();
   FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
   if (!FCmp)
     return false;
 
+  uint32_t TakenWeight = FPH_TAKEN_WEIGHT;
+  uint32_t NontakenWeight = FPH_NONTAKEN_WEIGHT;
   bool isProb;
   if (FCmp->isEquality()) {
     // f1 == f2 -> Unlikely
     // f1 != f2 -> Likely
     isProb = !FCmp->isTrueWhenEqual();
   } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
     // !isnan -> Likely
     isProb = true;
+    TakenWeight = FPH_ORD_WEIGHT;
+    NontakenWeight = FPH_UNO_WEIGHT;
   } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
     // isnan -> Unlikely
     isProb = false;
+    TakenWeight = FPH_ORD_WEIGHT;
+    NontakenWeight = FPH_UNO_WEIGHT;
   } else {
     return false;
   }
 
   unsigned TakenIdx = 0, NonTakenIdx = 1;
 
   if (!isProb)
     std::swap(TakenIdx, NonTakenIdx);
 
-  BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
-                              FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
+  BranchProbability TakenProb(TakenWeight, TakenWeight + NontakenWeight);
   setEdgeProbability(BB, TakenIdx, TakenProb);
   setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
   return true;
 }
 
 bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
   const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
   if (!II)

test/Analysis/BranchProbabilityInfo/fcmp.ll

+; RUN: opt < %s -analyze -branch-prob | FileCheck %s
+
+; This function tests the floating point unorder comparison. The probability
+; of NaN should be extremely small.
+; CHECK: Printing analysis 'Branch Probability Analysis' for function 'uno'
+; CHECK:  edge  -> a probability is 0x00000800 / 0x80000000 = 0.00%
+; CHECK:  edge  -> b probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
+
+define void @uno(float %val1, float %val2) {
+  %cond = fcmp uno float %val1, %val2
+  br i1 %cond, label %a, label %b
+
+a:
+  call void @fa()
+  ret void
+
+b:
+  call void @fb()
+  ret void
+}
+
+; This function tests the floating point order comparison.
+; CHECK: Printing analysis 'Branch Probability Analysis' for function 'ord'
+; CHECK:  edge  -> a probability is 0x7ffff800 / 0x80000000 = 100.00% [HOT edge]
+; CHECK:  edge  -> b probability is 0x00000800 / 0x80000000 = 0.00%
+
+define void @ord(float %val1, float %val2) {
+  %cond = fcmp ord float %val1, %val2
+  br i1 %cond, label %a, label %b
+
+a:
+  call void @fa()
+  ret void
+
+b:
+  call void @fb()
+  ret void
+}
+
+declare void @fa()
+declare void @fb()

test/CodeGen/SystemZ/call-05.ll

b:
   store i32 1, i32 *@var;
   ret void
 }
 
 ; Check a conditional sibling call - float uno compare.
 define void @f25(float %val1, float %val2) {
 ; CHECK-LABEL: f25:
 ; CHECK: cebr %f0, %f2
-; CHECK: bor %r1
+; CHECK: jo
 ; CHECK: br %r14
+; CHECK: br %r1
   %fun_a = load volatile void() *, void()** @fun_a;
   %cond = fcmp uno float %val1, %val2;
   br i1 %cond, label %a, label %b;
 
 a:
   tail call void %fun_a()
   ret void
 
 b:
   store i32 1, i32 *@var;
   ret void
 }