Page MenuHomePhabricator

Normalize MBB's successors' probabilities in several locations.
ClosedPublic

Authored by congh on Dec 5 2015, 2:17 AM.

Details

Summary

This patch adds some missing calls to MBB::normalizeSuccProbs() in several locations where it should be called. Those places are found by checking if the sum of successors' probabilities is approximate one in MachineBlockPlacement pass with some instrumented code (not in this patch).

Diff Detail

Repository
rL LLVM

Event Timeline

congh updated this revision to Diff 41988.Dec 5 2015, 2:17 AM
congh retitled this revision from to Normalize MBB's successors' probabilities in several locations..
congh updated this object.
congh added a reviewer: davidxl.
congh added a subscriber: llvm-commits.
davidxl added inline comments.Dec 5 2015, 11:57 AM
include/llvm/CodeGen/MachineBasicBlock.h
464 ↗(On Diff #41988)

Can you add some comment about the guidelines when to use the normalize arg? For instance when the removal is the final one.

lib/CodeGen/IfConversion.cpp
1262 ↗(On Diff #41988)

Is it better to add the same 'normalize' parameter to the addSuccessor method?

A related -- for addSuccessor, what is the guideline to normalize? How can we tell if the normalization actually masks a bug in the updater?

lib/CodeGen/TailDuplication.cpp
754 ↗(On Diff #41988)

This one seems unnecessary.

862 ↗(On Diff #41988)

The normalization seems redundant -- See assertion before: assert(PredB->succ_empty()) ..

If the assertion is not true, the way prob is updated is not correct. It should do this:
OldProb = getEdgeProb(PredBB, PredBB->succ_begin());

for (.... ) {

PredBB->addSuccessor (*I, getEdgeProb(TailBB,I)*OldProb)

}

Normalization is not needed either.

congh added inline comments.Dec 5 2015, 12:39 PM
include/llvm/CodeGen/MachineBasicBlock.h
464 ↗(On Diff #41988)

I have added some comments on normalizeSuccProbs(). This is usually done when the current update on the MBB is done. There are three effects of using this interface: 1. Incorrect. 2. Necessary. 3. Redundant. We should forbid the first case and try to always do it if it is necessary.

lib/CodeGen/IfConversion.cpp
1262 ↗(On Diff #41988)

As the user already provided a probability when calling addSuccessor(), I think adding the 'normalize' parameter to it is unnecessary. Actually in most cases we don't have to do the normalization.

The time to do normalization is the update is done and no more update is coming to this MBB. It is difficult to detect if a normalization is correct, or may be expensive to do this. It is the user's responsibility to keep its usage correct.

lib/CodeGen/TailDuplication.cpp
754 ↗(On Diff #41988)

Agree. Thanks for pointing it out!.

862 ↗(On Diff #41988)

You are right. The normalization is redundant here.

congh updated this revision to Diff 41994.Dec 5 2015, 12:42 PM
congh edited edge metadata.

Update the patch according to David's comments.

davidxl edited edge metadata.Dec 8 2015, 5:15 PM

Are there any test case changes?

lib/CodeGen/IfConversion.cpp
1263 ↗(On Diff #41994)

Add a brief comment about why normalization is needed (i.e., why the input BPs do not sum up to 1)?

1719 ↗(On Diff #41994)

The comment needs to be fixed (probably in a different patch).

1753 ↗(On Diff #41994)

It is unclear why this is needed.

1754 ↗(On Diff #41994)

Will its successor edge be discarded later?

congh added a comment.Dec 10 2015, 2:18 PM

Are there any test case changes?

There is no test changes.

lib/CodeGen/IfConversion.cpp
1263 ↗(On Diff #41994)

I tried removing this normalization and there isn't new test failures. So I think this is redundant. I added a runtime check instead, which is a new interface of MBB that checks if all successors' probabilities sum up to one and produces assertion failure if not.

1719 ↗(On Diff #41994)

As this is a very small change, I think it is ok to do it in this patch. Done.

1753 ↗(On Diff #41994)

This is needed as here we have adjusted its successors's probabilities which cannot guarantee the sum is one.

1754 ↗(On Diff #41994)

I checked all uses of this function and found after each call FromBBI.BB's successors are all normalized somehow. I commented this line and didn't see any new failures in my test. So we don't have to normalize FromBBI.BB's successors.

congh added inline comments.Dec 10 2015, 2:35 PM
lib/CodeGen/IfConversion.cpp
1263 ↗(On Diff #41994)

Unfortunately the validation fails several times here, which means sum != 1 for BBI.BB's successors. However, they are going to be normalized later in RemoveExtraEdges(BBI) so it seems the normalization is still redundant.

The if converter allows many invalid temporary states which are later fixed by some clean-up functions. This makes updating and validating probabilities quite difficult.

congh updated this revision to Diff 42465.Dec 10 2015, 2:36 PM
congh edited edge metadata.

Update the patch according to David's comment.

davidxl accepted this revision.Dec 12 2015, 7:09 PM
davidxl edited edge metadata.

LGTM

This revision is now accepted and ready to land.Dec 12 2015, 7:09 PM
This revision was automatically updated to reflect the committed changes.