This is an archive of the discontinued LLVM Phabricator instance.

Mark BB as annotated if its weight is > 0
ClosedPublic

Authored by danielcdh on Sep 28 2015, 10:14 AM.

Details

Reviewers
dnovillo
davidxl
Summary

Mark BB as annotated if its weight is > 0, otherwise the propagation algorithm will not be able to propagate edge weights.

Diff Detail

Event Timeline

danielcdh updated this revision to Diff 35885.Sep 28 2015, 10:14 AM
danielcdh retitled this revision from to Mark BB as annotated if its weight is > 0.
danielcdh updated this object.
danielcdh added a reviewer: dnovillo.
dnovillo edited edge metadata.Sep 28 2015, 10:39 AM

LGTM with a test case.

Thanks.

danielcdh updated this revision to Diff 35892.Sep 28 2015, 10:53 AM
danielcdh edited edge metadata.

Update reviewer

danielcdh updated this revision to Diff 35894.Sep 28 2015, 10:55 AM

Add reviewers.

danielcdh added a subscriber: llvm-commits.
danielcdh updated this revision to Diff 35931.Sep 28 2015, 6:19 PM

Add unittest to fix propagation. This equivalence class based method is still incorrect. I will have a separate patch to fix equivalence class bug.

davidxl added inline comments.Sep 28 2015, 8:51 PM
lib/Transforms/IPO/SampleProfile.cpp
242

I think it is clearer to rename this method 'setBlockWeight' -- what it does is to read from the samples and set the cached weight for BB and mark it as annotated.

485

Should use annotated EC's weight.

579

There seems to be a missing step to propagate weights from annotated BBs to their equivalence classes -- the later should be used in Edge propagation

danielcdh added inline comments.Sep 28 2015, 9:20 PM
lib/Transforms/IPO/SampleProfile.cpp
242

In another patch http://reviews.llvm.org/D13231, I changed getBlockWeight as a const member function and removed the caching (because there is no reuse), and move the setting of BlockWeights outside this function.

485

That's correct. I'll have a separate patch to fix the EC's propagation.

Let me back up a little bit. If getBlockWeight() marks the block visited all the time, then how can propagation work? getBlockWeight is only used when computing the *initial* weight of the blocks (I agree with David, it should be renamed to setBlockWeight()).

But, in looking at the code again, it doesn't seem correct to mark the block visited there. We mark them visited when we are assigning equivalence classes.

I think I'm missing something here.

computeBlockWeights assigns weights to basic blocks that has profile data and mark them as annotated. But after this step, there will still be basic blocks that are not annotated. So the propagation step works on 3 things:

  • set edge weights and mark it as annotated
  • set basic block weights for those unannotated basic blocks and mark them as annotated
  • adjust basic block weights for those annotated basic blocks which has apparently incorrect weights

Equivalence class is not the place to set the annotated flag, it just sets the equivalence class for each basic block. In later propagation algorithm, instead of checking "IsAnnotated(BB)", we should check "IsAnnotated(BB->equivalence_class)".

Dehao

dnovillo added inline comments.Sep 29 2015, 8:11 AM
lib/Transforms/IPO/SampleProfile.cpp
309

clang-format this? I think it will now fit on the same line.

danielcdh updated this revision to Diff 35995.Sep 29 2015, 10:20 AM

clang-format

danielcdh marked an inline comment as done.Sep 29 2015, 10:22 AM

rerun clang-format.

dnovillo accepted this revision.Sep 29 2015, 10:50 AM
dnovillo edited edge metadata.

LGTM

This revision is now accepted and ready to land.Sep 29 2015, 10:50 AM
danielcdh updated this revision to Diff 36060.Sep 29 2015, 6:44 PM
danielcdh edited edge metadata.

This change exposed many errors in the original test input. Thus I integrated the EC related change into this patch so that I only need to update the test input once.

Diego and David, please help take another look at the patch. With this patch, the propagation should be very robust now.

Patch looks fine. Just a couple of final questions.

include/llvm/ProfileData/SampleProf.h
221 ↗(On Diff #36060)

Sadly, I don't think there is a test case for this check I had added. With your new changes, we can now distinguish 0 from missing sample all the time, right?

lib/Transforms/IPO/SampleProfile.cpp
375

Not sure why we don't process blocks post-dominated by BB1 anymore?

danielcdh added inline comments.Sep 30 2015, 7:44 AM
include/llvm/ProfileData/SampleProf.h
221 ↗(On Diff #36060)

Yes, now GetBlockCount will return std::error_code if there is no profile.

lib/Transforms/IPO/SampleProfile.cpp
375

Processing dominators should be able to cover all ECs, this is because if BB1 dominates BB2, and BB1 and BB2 are in the same EC, then BB2 also post-dominates BB1.

danielcdh closed this revision.Oct 2 2015, 10:06 AM

submitted