From b19ec1eb3d0cbb3017e1bc7111efac5643cf4fdd Mon Sep 17 00:00:00 2001
From: Taewook Oh <twoh@fb.com>
Date: Wed, 27 Nov 2019 10:18:01 -0800
Subject: [BPI] Improve unreachable/ColdCall heurstics to handle loops.

Summary:
While updatePostDominatedByUnreachable attemps to find basic blocks that are post-domianted by unreachable blocks, it currently cannot handle loops precisely, because it doesn't use the actual post dominator tree analysis but relies on heuristics of visiting basic blocks in post-order. More precisely, when the entire loop is post-dominated by the unreachable block, current algorithm fails to detect the entire loop as post-dominated by the unreachable because when the algorithm reaches to the loop latch it fails to tell all its successors (including the loop header) will "eventually" be post-domianted by the unreachable block, because the algorithm hasn't visited the loop header yet. This makes BPI for the loop latch to assume that loop backedges are taken with 100% of probability. And because of this, block frequency info sometimes marks virtually dead loops (which are post dominated by unreachable blocks) super hot, because 100% backedge-taken probability makes the loop iteration count the max value. updatePostDominatedByColdCall has the exact same problem as well.

To address this problem, this patch makes PostDominatedByUnreachable/PostDominatedByColdCall to be computed with the actual post-dominator tree.

Reviewers: skatkov, chandlerc, manmanren

Reviewed By: skatkov

Subscribers: manmanren, vsk, apilipenko, Carrot, qcolombet, hiraditya, llvm-commits

Tags: #llvm

Differential Revision: https://reviews.llvm.org/D70104
---
 llvm/test/Analysis/BranchProbabilityInfo/basic.ll  | 18 +++++++++++++++
 .../Analysis/BranchProbabilityInfo/noreturn.ll     | 26 ++++++++++++++++++++++
 2 files changed, 44 insertions(+)

(limited to 'llvm/test/Analysis')

diff --git a/llvm/test/Analysis/BranchProbabilityInfo/basic.ll b/llvm/test/Analysis/BranchProbabilityInfo/basic.ll
index 64e0a82456f..8212cc47690 100644
--- a/llvm/test/Analysis/BranchProbabilityInfo/basic.ll
+++ b/llvm/test/Analysis/BranchProbabilityInfo/basic.ll
@@ -141,6 +141,24 @@ exit:
   ret i32 %result
 }
 
+define i32 @test_cold_loop(i32 %a, i32 %b) {
+entry:
+  %cond1 = icmp eq i32 %a, 42
+  br i1 %cond1, label %header, label %exit
+
+header:
+  br label %body
+
+body:
+  %cond2 = icmp eq i32 %b, 42
+  br i1 %cond2, label %header, label %exit
+; CHECK: edge body -> header probability is 0x40000000 / 0x80000000 = 50.00%
+
+exit:
+  call void @coldfunc()
+  ret i32 %b
+}
+
 declare i32 @regular_function(i32 %i)
 
 define i32 @test_cold_call_sites_with_prof(i32 %a, i32 %b, i1 %flag, i1 %flag2) {
diff --git a/llvm/test/Analysis/BranchProbabilityInfo/noreturn.ll b/llvm/test/Analysis/BranchProbabilityInfo/noreturn.ll
index 0566ca16c2f..6e01afd2cfc 100644
--- a/llvm/test/Analysis/BranchProbabilityInfo/noreturn.ll
+++ b/llvm/test/Analysis/BranchProbabilityInfo/noreturn.ll
@@ -79,6 +79,32 @@ exit:
   ret i32 %b
 }
 
+define i32 @test4(i32 %a, i32 %b) {
+; CHECK: Printing analysis {{.*}} for function 'test4'
+; Make sure we handle loops post-dominated by unreachables.
+entry:
+  %cond1 = icmp eq i32 %a, 42
+  br i1 %cond1, label %header, label %exit
+; CHECK: edge entry -> header probability is 0x00000001 / 0x80000000 = 0.00%
+; CHECK: edge entry -> exit probability is 0x7fffffff / 0x80000000 = 100.00% [HOT edge]
+
+header:
+  br label %body
+
+body:
+  %cond2 = icmp eq i32 %a, 42
+  br i1 %cond2, label %header, label %abort
+; CHECK: edge body -> header probability is 0x40000000 / 0x80000000 = 50.00%
+; CHECK: edge body -> abort probability is 0x40000000 / 0x80000000 = 50.00%
+
+abort:
+  call void @abort() noreturn
+  unreachable
+
+exit:
+  ret i32 %b
+}
+
 @_ZTIi = external global i8*
 
 ; CHECK-LABEL: throwSmallException
-- 
cgit v1.2.3