Page MenuHomePhabricator

[PPC] Correctly adjust branch probability in PPCReduceCRLogicals
ClosedPublic

Authored by Carrot on May 24 2019, 3:19 PM.

Details

Summary

In PPCReduceCRLogicals after splitting the original MBB into 2, the 2 impacted branches still use original branch probability. This is unreasonable. Suppose we have following code, and the probability of each successor is 50%.

condc = conda || condb
br condc, label %target, label %fallthrough

It can be transformed to following,

br conda, label %target, label %newbb

newbb:

br condb, label %target, label %fallthrough

Since each branch has a probability of 50% to each successor, the total probability to %fallthrough is 25% now, and the total probability to %target is 75%. This actually changed the original profiling data. A more reasonable probability can be set to 70% to the false side for each branch instruction, so the total probability to %fallthrough is close to 50%.

This patch assumes the branch target with two incoming edges have same edge frequency and computes new probability fore each target, and keep the total probability to original targets unchanged.

Diff Detail

Repository
rL LLVM

Event Timeline

Carrot created this revision.May 24 2019, 3:19 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 24 2019, 3:19 PM
hfinkel added inline comments.May 24 2019, 3:28 PM
include/llvm/Support/BranchProbability.h
161 ↗(On Diff #201344)

This would be the first use of floating-point here, right? Can we do this any other way?

Carrot marked an inline comment as done.May 28 2019, 8:15 AM
Carrot added inline comments.
include/llvm/Support/BranchProbability.h
161 ↗(On Diff #201344)

Suppose the original branch probability to Target is P0, after splitting MBB, there are two branches to Target, the probability to it is P1 and P2. If the edge frequency to Target is same, then

F * P1 = F * P0 / 2                    ==>  P1 = P0 / 2
F * (1 - P1) * P2 = F * P1          ==>  P2 = P1 / (1 - P1)

With this distribution we can avoid square root.

Carrot updated this revision to Diff 201714.May 28 2019, 10:56 AM
Carrot edited the summary of this revision. (Show Details)

Changed the edge frequency distribution, so I can avoid floating point square root computation.

xur added inline comments.May 28 2019, 3:46 PM
lib/Target/PowerPC/PPCReduceCRLogicals.cpp
171 ↗(On Diff #201714)

NIT: (1) "need" -> "needs".
(2) Please also explain what is P0, P1, P2. A diagram would be helpful.

Carrot updated this revision to Diff 201970.May 29 2019, 10:17 AM
Carrot marked an inline comment as done.

Hi Carrot,
I agree with this change, conceptually. Have you done any performance measurements to see what the impact is?

xur accepted this revision.May 30 2019, 10:52 AM

looks good to me.

lib/Target/PowerPC/PPCReduceCRLogicals.cpp
187 ↗(On Diff #201970)

NIT: Probably use ProbFallThough?

This revision is now accepted and ready to land.May 30 2019, 10:52 AM

Hi Carrot,
I agree with this change, conceptually. Have you done any performance measurements to see what the impact is?

I didn't measure its impact, and it should not have any performance impact because currently it is disabled by default.

When I worked on code layout improvements, I got an unreasonable result for test case CodeGen/PowerPC/tail-dup-layout.ll because of this bad branch probability adjustment. So I fixed it with this patch.

Carrot marked an inline comment as done.May 30 2019, 11:38 AM
Carrot added inline comments.
lib/Target/PowerPC/PPCReduceCRLogicals.cpp
187 ↗(On Diff #201970)

I use the current expression to make it consistent with the formula in line 178.

This revision was automatically updated to reflect the committed changes.