Use fixed-point representation for BranchProbability.
BranchProbability now is represented by its numerator and denominator in uint32_t type. This patch changes this representation into a fixed point that is represented by the numerator in uint32_t type and a constant denominator 1<<31. This is quite similar to the representation of BlockMass in BlockFrequencyInfoImpl.h. There are several pros and cons of this change:
Pros:
1. It uses only a half space of the current one.
2. Some operations are much faster like plus, subtraction, comparison, and scaling by an integer.
Cons:
1. Constructing a probability using arbitrary numerator and denominator needs additional calculations.
2. It is a little less precise than before as we use a fixed denominator. For example, 1 - 1/3 may not be exactly identical to 1 / 3 (this will lead to many BranchProbability unit test failures). This should not matter when we only use it for branch probability. If we use it like a rational value for some precise calculations we may need another construct like ValueRatio.
One important reason for this change is that we propose to store branch probabilities instead of edge weights in MachineBasicBlock. We also want clients to use probability instead of weight when adding successors to a MBB. The current BranchProbability has more space which may be a concern.
Differential revision: http://reviews.llvm.org/D12603
llvm-svn: 248633
diff --git a/llvm/test/Transforms/SampleProfile/branch.ll b/llvm/test/Transforms/SampleProfile/branch.ll
index 051a738..d367a84 100644
--- a/llvm/test/Transforms/SampleProfile/branch.ll
+++ b/llvm/test/Transforms/SampleProfile/branch.ll
@@ -36,8 +36,8 @@
tail call void @llvm.dbg.value(metadata i8** %argv, i64 0, metadata !14, metadata !DIExpression()), !dbg !27
%cmp = icmp slt i32 %argc, 2, !dbg !28
br i1 %cmp, label %return, label %if.end, !dbg !28
-; CHECK: edge entry -> return probability is 0 / 1 = 0%
-; CHECK: edge entry -> if.end probability is 1 / 1 = 100%
+; CHECK: edge entry -> return probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge entry -> if.end probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
if.end: ; preds = %entry
%arrayidx = getelementptr inbounds i8*, i8** %argv, i64 1, !dbg !30
@@ -46,8 +46,8 @@
tail call void @llvm.dbg.value(metadata i32 %call, i64 0, metadata !17, metadata !DIExpression()), !dbg !30
%cmp1 = icmp sgt i32 %call, 100, !dbg !35
br i1 %cmp1, label %for.body, label %if.end6, !dbg !35
-; CHECK: edge if.end -> for.body probability is 0 / 1 = 0%
-; CHECK: edge if.end -> if.end6 probability is 1 / 1 = 100%
+; CHECK: edge if.end -> for.body probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge if.end -> if.end6 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
for.body: ; preds = %if.end, %for.body
%u.016 = phi i32 [ %inc, %for.body ], [ 0, %if.end ]
@@ -65,14 +65,14 @@
tail call void @llvm.dbg.value(metadata i32 %inc, i64 0, metadata !21, metadata !DIExpression()), !dbg !38
%exitcond = icmp eq i32 %inc, %call, !dbg !38
br i1 %exitcond, label %if.end6, label %for.body, !dbg !38
-; CHECK: edge for.body -> if.end6 probability is 0 / 10226 = 0%
-; CHECK: edge for.body -> for.body probability is 10226 / 10226 = 100% [HOT edge]
+; CHECK: edge for.body -> if.end6 probability is 0x00000000 / 0x80000000 = 0.00%
+; CHECK: edge for.body -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
if.end6: ; preds = %for.body, %if.end
%result.0 = phi double [ 0.000000e+00, %if.end ], [ %sub, %for.body ]
%call7 = tail call i32 (i8*, ...) @printf(i8* getelementptr inbounds ([15 x i8], [15 x i8]* @.str, i64 0, i64 0), double %result.0), !dbg !39
br label %return, !dbg !40
-; CHECK: edge if.end6 -> return probability is 16 / 16 = 100% [HOT edge]
+; CHECK: edge if.end6 -> return probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
return: ; preds = %entry, %if.end6
%retval.0 = phi i32 [ 0, %if.end6 ], [ 1, %entry ]
diff --git a/llvm/test/Transforms/SampleProfile/calls.ll b/llvm/test/Transforms/SampleProfile/calls.ll
index 9db4f5d..aa17643 100644
--- a/llvm/test/Transforms/SampleProfile/calls.ll
+++ b/llvm/test/Transforms/SampleProfile/calls.ll
@@ -52,8 +52,8 @@
store i32 %inc, i32* %i, align 4, !dbg !14
%cmp = icmp slt i32 %0, 400000000, !dbg !14
br i1 %cmp, label %while.body, label %while.end, !dbg !14
-; CHECK: edge while.cond -> while.body probability is 5391 / 5391 = 100% [HOT edge]
-; CHECK: edge while.cond -> while.end probability is 0 / 5391 = 0%
+; CHECK: edge while.cond -> while.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge while.cond -> while.end probability is 0x00000000 / 0x80000000 = 0.00%
while.body: ; preds = %while.cond
%1 = load i32, i32* %i, align 4, !dbg !16
@@ -63,8 +63,8 @@
; both branches out of while.body had the same weight. In reality,
; the edge while.body->if.then is taken most of the time.
;
-; CHECK: edge while.body -> if.then probability is 5752 / 5752 = 100% [HOT edge]
-; CHECK: edge while.body -> if.else probability is 0 / 5752 = 0%
+; CHECK: edge while.body -> if.then probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge while.body -> if.else probability is 0x00000000 / 0x80000000 = 0.00%
if.then: ; preds = %while.body
diff --git a/llvm/test/Transforms/SampleProfile/discriminator.ll b/llvm/test/Transforms/SampleProfile/discriminator.ll
index bffeaca..ffc474b 100644
--- a/llvm/test/Transforms/SampleProfile/discriminator.ll
+++ b/llvm/test/Transforms/SampleProfile/discriminator.ll
@@ -34,15 +34,15 @@
%0 = load i32, i32* %i.addr, align 4, !dbg !12
%cmp = icmp slt i32 %0, 100, !dbg !12
br i1 %cmp, label %while.body, label %while.end, !dbg !12
-; CHECK: edge while.cond -> while.body probability is 100 / 101 = 99.0099% [HOT edge]
-; CHECK: edge while.cond -> while.end probability is 1 / 101 = 0.990099%
+; CHECK: edge while.cond -> while.body probability is 0x7ebb907a / 0x80000000 = 99.01% [HOT edge]
+; CHECK: edge while.cond -> while.end probability is 0x01446f86 / 0x80000000 = 0.99%
while.body: ; preds = %while.cond
%1 = load i32, i32* %i.addr, align 4, !dbg !14
%cmp1 = icmp slt i32 %1, 50, !dbg !14
br i1 %cmp1, label %if.then, label %if.end, !dbg !14
-; CHECK: edge while.body -> if.then probability is 5 / 100 = 5%
-; CHECK: edge while.body -> if.end probability is 95 / 100 = 95% [HOT edge]
+; CHECK: edge while.body -> if.then probability is 0x06666666 / 0x80000000 = 5.00%
+; CHECK: edge while.body -> if.end probability is 0x7999999a / 0x80000000 = 95.00% [HOT edge]
if.then: ; preds = %while.body
%2 = load i32, i32* %x, align 4, !dbg !17
diff --git a/llvm/test/Transforms/SampleProfile/fnptr.ll b/llvm/test/Transforms/SampleProfile/fnptr.ll
index 3064ad8..f95bf97 100644
--- a/llvm/test/Transforms/SampleProfile/fnptr.ll
+++ b/llvm/test/Transforms/SampleProfile/fnptr.ll
@@ -5,12 +5,12 @@
; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/fnptr.prof | opt -analyze -branch-prob | FileCheck %s
; RUN: opt < %s -sample-profile -sample-profile-file=%S/Inputs/fnptr.binprof | opt -analyze -branch-prob | FileCheck %s
-; CHECK: edge for.body3 -> if.then probability is 534 / 2598 = 20.5543%
-; CHECK: edge for.body3 -> if.else probability is 2064 / 2598 = 79.4457%
-; CHECK: edge for.inc -> for.inc12 probability is 1052 / 2598 = 40.4927%
-; CHECK: edge for.inc -> for.body3 probability is 1546 / 2598 = 59.5073%
-; CHECK: edge for.inc12 -> for.end14 probability is 518 / 1052 = 49.2395%
-; CHECK: edge for.inc12 -> for.cond1.preheader probability is 534 / 1052 = 50.7605%
+; CHECK: edge for.body3 -> if.then probability is 0x1a4f3959 / 0x80000000 = 20.55%
+; CHECK: edge for.body3 -> if.else probability is 0x65b0c6a7 / 0x80000000 = 79.45%
+; CHECK: edge for.inc -> for.inc12 probability is 0x33d4a4c1 / 0x80000000 = 40.49%
+; CHECK: edge for.inc -> for.body3 probability is 0x4c2b5b3f / 0x80000000 = 59.51%
+; CHECK: edge for.inc12 -> for.end14 probability is 0x3f06d04e / 0x80000000 = 49.24%
+; CHECK: edge for.inc12 -> for.cond1.preheader probability is 0x40f92fb2 / 0x80000000 = 50.76%
; Original C++ test case.
;
diff --git a/llvm/test/Transforms/SampleProfile/propagate.ll b/llvm/test/Transforms/SampleProfile/propagate.ll
index 7d5ce73..ca58d17 100644
--- a/llvm/test/Transforms/SampleProfile/propagate.ll
+++ b/llvm/test/Transforms/SampleProfile/propagate.ll
@@ -73,8 +73,8 @@
%5 = load i64, i64* %N.addr, align 8, !dbg !15
%cmp1 = icmp slt i64 %4, %5, !dbg !15
br i1 %cmp1, label %for.body, label %for.end18, !dbg !15
-; CHECK: edge for.cond -> for.body probability is 10 / 10 = 100% [HOT edge]
-; CHECK: edge for.cond -> for.end18 probability is 0 / 10 = 0%
+; CHECK: edge for.cond -> for.body probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge for.cond -> for.end18 probability is 0x00000000 / 0x80000000 = 0.00%
for.body: ; preds = %for.cond
%6 = load i64, i64* %i, align 8, !dbg !18
@@ -82,8 +82,8 @@
%div = sdiv i64 %7, 3, !dbg !18
%cmp2 = icmp sgt i64 %6, %div, !dbg !18
br i1 %cmp2, label %if.then3, label %if.end, !dbg !18
-; CHECK: edge for.body -> if.then3 probability is 1 / 5 = 20%
-; CHECK: edge for.body -> if.end probability is 4 / 5 = 80%
+; CHECK: edge for.body -> if.then3 probability is 0x1999999a / 0x80000000 = 20.00%
+; CHECK: edge for.body -> if.end probability is 0x66666666 / 0x80000000 = 80.00%
if.then3: ; preds = %for.body
%8 = load i32, i32* %x.addr, align 4, !dbg !21
@@ -97,8 +97,8 @@
%div4 = sdiv i64 %10, 4, !dbg !22
%cmp5 = icmp sgt i64 %9, %div4, !dbg !22
br i1 %cmp5, label %if.then6, label %if.else7, !dbg !22
-; CHECK: edge if.end -> if.then6 probability is 3 / 6342 = 0.0473037%
-; CHECK: edge if.end -> if.else7 probability is 6339 / 6342 = 99.9527% [HOT edge]
+; CHECK: edge if.end -> if.then6 probability is 0x000f801f / 0x80000000 = 0.05%
+; CHECK: edge if.end -> if.else7 probability is 0x7ff07fe1 / 0x80000000 = 99.95% [HOT edge]
if.then6: ; preds = %if.end
%11 = load i32, i32* %y.addr, align 4, !dbg !24
@@ -119,8 +119,8 @@
%14 = load i64, i64* %i, align 8, !dbg !28
%cmp10 = icmp slt i64 %conv9, %14, !dbg !28
br i1 %cmp10, label %for.body11, label %for.end, !dbg !28
-; CHECK: edge for.cond8 -> for.body11 probability is 16191 / 16191 = 100% [HOT edge]
-; CHECK: edge for.cond8 -> for.end probability is 0 / 16191 = 0%
+; CHECK: edge for.cond8 -> for.body11 probability is 0x80000000 / 0x80000000 = 100.00% [HOT edge]
+; CHECK: edge for.cond8 -> for.end probability is 0x00000000 / 0x80000000 = 0.00%
for.body11: ; preds = %for.cond8
%15 = load i32, i32* %j, align 4, !dbg !31