This is an archive of the discontinued LLVM Phabricator instance.

[Coverage] Restore the correct count value after processing a nested region in case of combined regions.
ClosedPublic

Authored by ikudrin on Mar 30 2016, 11:25 AM.

Details

Summary

If we have several regions which cover the same code area, we should restore
the combined value for that region when return from a nested region.

This patch achieves that goal by combining regions before calling buildSegments.

Diff Detail

Event Timeline

ikudrin updated this revision to Diff 52088.Mar 30 2016, 11:25 AM
ikudrin retitled this revision from to [PGO] Restore the correct counter value after processing a nested region in case of combined regions..
ikudrin updated this object.
ikudrin added reviewers: bogner, davidxl.
ikudrin added a subscriber: llvm-commits.
vsk added a subscriber: vsk.Mar 30 2016, 12:41 PM
vsk added a comment.Mar 30 2016, 12:58 PM

Thanks for the patch.

+ 1 to Justin's comments.

llvm/trunk/lib/ProfileData/CoverageMapping.cpp
302

nit: I think we can reduce repetition here by computing the Optional<uint64_t> first, and then calling startSegment.

llvm/trunk/test/tools/llvm-cov/showTemplateInstantiations.cpp
10

Could you explain why the line containing the else is marked as having executed twice? It seems like it should only be executed once.

davidxl edited edge metadata.Mar 30 2016, 10:32 PM

I think a better fix is to change the active region stack into a stack of entry segments. The resulting code will be more readable.

llvm/trunk/lib/ProfileData/CoverageMapping.cpp
281–282

This seems like a dead function now.

llvm/trunk/test/tools/llvm-cov/showTemplateInstantiations.cpp
10

The 'else' line is not included by any region. It gets its count from the End segment of the previous region. The count of the end segment of a region is defined here to be the count of its parent region which makes sense for case like

if (...) {

// region 1

}
// non exec line

The non exec line's count is region 1's parent region's count, not region 1.

ikudrin updated this revision to Diff 52230.Mar 31 2016, 9:57 AM
ikudrin edited edge metadata.

Thanks a lot for the comments! Please review the new version of the code.

  • Added a new unit test.
  • Eliminated dead code.
  • Reworked the whole SegmentBuilder class.
  • Addressed all other comments.

Is it possible to combine identical regions (covering same area) before calling buildSegments? I think the resulting code would be a lot more readable.

ikudrin updated this revision to Diff 53561.Apr 13 2016, 8:16 AM
ikudrin retitled this revision from [PGO] Restore the correct counter value after processing a nested region in case of combined regions. to [Coverage] Restore the correct count value after processing a nested region in case of combined regions..
ikudrin updated this object.
  • Implemented David's idea of combining identical regions before calling buildSegments.
davidxl added inline comments.Apr 13 2016, 9:54 AM
llvm/trunk/lib/ProfileData/CoverageMapping.cpp
412

I think this can be simplified by calling std::unique

Followed by a scan of the duplicate entries. For each dup entry, call lower_bound to to find the matching entry and update it if it exists.

475

This probably can be moved into 'sortNestedRegions'.

ikudrin added inline comments.Apr 14 2016, 2:57 AM
llvm/trunk/lib/ProfileData/CoverageMapping.cpp
412

I'm afraid I can't fully understand your idea. std::unique just removes duplicate entries and provides no way to work with removed items. So, I can't catch, how you suppose to scan dupes. Moreover, std::lower_bound requires O(log(N)) comparisons which leads to O(N*log(N)) complexity for the whole method. At the same time, the current code requires only one scan of an array and doesn't require additional dynamic memory.
Could you provide some code to illustrate your approach?

475

As they are separate and mostly independent tasks, I don't think it's good to merge them in one function. On the other hand, we can move both sortNestedRegions and combineRegionCounts into the SegmentBuilder class and simplify callers this way.

davidxl added inline comments.Apr 14 2016, 9:20 AM
llvm/trunk/lib/ProfileData/CoverageMapping.cpp
412

unique call returns a iterator pointing to the new logical end of the vector. The dups are from logical end to the original end. You are right that lower_bound O(log(N)), but the overall complexity is O(N*log(N)) only when the # of dups is linear to the total number of regions. I doubt it is the case in real case, but your concern is legit.

413

Last --> End (which is one past last)

418

Can you just do

// Find a new region
if (Active->StartLoc() != ... ) {

Active = I;
continue;

}

426

Add a comment before this line -- "// merge duplicate region"

475

yes -- since sortNestedRegions and combineRegions are always called together side by side -- having a wrapper call will be nicer.

ikudrin added inline comments.Apr 14 2016, 9:27 AM
llvm/trunk/lib/ProfileData/CoverageMapping.cpp
412

According to http://en.cppreference.com/w/cpp/algorithm/unique:

Iterators pointing to an element between the new logical end and the physical end of the range are still dereferenceable, but the elements themselves have unspecified values.

So, you can't expect the dupes to be stored there.

davidxl added inline comments.Apr 14 2016, 9:37 AM
llvm/trunk/lib/ProfileData/CoverageMapping.cpp
412

ack.

davidxl added inline comments.Apr 14 2016, 9:53 AM
llvm/trunk/lib/ProfileData/CoverageMapping.cpp
418

Discard this comment -- your code is correct.

ikudrin updated this revision to Diff 54217.Apr 19 2016, 10:02 AM
  • Rebased to the top.
  • Moved sortNestedRegions and combineRegions into SegmentBuilder.
  • buildSegments now receives MutableArrayRef and performs sorting and combining regions internally.
  • Some ASSERT_EQ was changed to EXPECT_EQ in the added test.

looks ok to me. Check with Justin to see if he likes this cleanup.

ikudrin updated this revision to Diff 54664.Apr 22 2016, 9:29 AM
  • Reworked initialization of I according to Justin's comment.
  • Added some explanation comments for the "Merge duplicate region" code block.

Please note that I've tried to make the behavior of the new code as close to the original as possible, apart from changes required for fix the described issue. More changes are coming, which will also change this block of code, so it's anyway not the final variant. See D18831.

This revision was automatically updated to reflect the committed changes.