This is an archive of the discontinued LLVM Phabricator instance.

MergeFunc: Avoid invalid merge of functions using different range metadata
ClosedPublic

Authored by dotdash on Jun 8 2014, 10:37 AM.

Details

Reviewers
dyatkovskiy
Summary

Different range metadata can lead to different optimizations in later
passes, possibly breaking the semantics of the merged function. So range
metadata must be taken into consideration when comparing Load
instructions.

Diff Detail

Event Timeline

dotdash updated this revision to Diff 10218.Jun 8 2014, 10:37 AM
dotdash retitled this revision from to MergeFunc: Avoid invalid merge of functions using different range metadata.
dotdash updated this object.
dotdash edited the test plan for this revision. (Show Details)
dotdash added a reviewer: dyatkovskiy.
dotdash added a subscriber: Unknown Object (MLST).
dyatkovskiy edited edge metadata.Jun 9 2014, 3:05 PM

Hi Bjorn,
You have found really interesting point :-)
For this changes set, please, read inline comments.

In general. We can merge such cases (and it's good to merge them), but we also have to merge metadata.
Two loads:
1.: %0 = load i8* %check_place, !range !0
2.: %0 = load i8* %check_place, !range !1
With metadata:
!0 = metadata !{i8 0, i8 2}
!1 = metadata !{i8 5, i8 7}

Could be merged into:
%0 = load i8* %check_place, !range !0

With metadata:
!0 = metadata !{i8 0, i8 2, i8 5, i8 7}

I think you could do this check "MergeFunctions::insert": if destination or source function contains load with "range" - extend 'range' metadata with new values.

Could you provide such patch after this one?

test/Transforms/MergeFunc/ranges.ll
13

This is valid check, but IMHO it's a bit fragile.
Could you check full function contents here. It has only 5 lines :-)

23

The same. I'd prefer to see that whole function remains unchanged.

I wasn't sure about expanding the range to be more generic, since I thought that that might defeat some optimizations in other passes. I'll update the patch later today.

dotdash updated this revision to Diff 10280.Jun 10 2014, 8:41 AM
dotdash edited edge metadata.

Updated the patch to merge the range metadata for the loads instead of not
merging such functions at all. I found mergeTwoFunctions() to be a better place
than insert() to call the new method that handles the merge of the range
metadata. I hope this is what you had in mind.

Hi Bjorn (sorry I don't have o-umlaut on my keyboard :-) ),

Yes. This is proper way.
Only critical thing is: we have to avoid extra function body scanning. So in this context, try to introduce the way of noticing such loads on cmpOperation stage. So we could avoid rescan whole function again while merging. It possible by associating structure for each function, that would keep usefull information we collect while scanning. You can do that by introducing new field in ComparableFunction, and store anything suspicious you find about 'load' insts :-)
Then on merging stage you won't scan functions again, but just check ComparableFunction fields.
But...
I hope, we will replace ComparableFunction soon with similar structure ( during O(N*log(N) optimization). So that's why I'd propose to commit it just as fix for now (so you had to fix your tests only in first patch version).
And then it would be really good, if you proceed to work on this subject, so we could create good optimization for 'ranges' metadata.

Thanks for working on it!

Hi Stepan,

my bad, I just always forget that the hashmap contains ComparableFunctions, not just Functions, so I didn't see where to put the list of load instructions.

Just to make sure that I didn't misunderstand you and implement the wrong thing, you want me to go back to the initial patch that removes the merge of such function and fix the tests to ensure that the whole body is retained. And then later once you reworked ComparableFunction, I could go and implement the merge of ranges in a proper way, right?

Thanks!
Björn

PS: No worries about the o-umlaut, I'm used to losing that on the internet ;-)

Yes. Exactly ) For now, I propose to come back to initial patch; make sure tests has been fixed as I asked you in inline comments and, I think we apply it (Nick didn't object about it yesterday).
Then, after we replace ComparableFunction with new structure, you could introduce 'range' metadata merging.
Thanks for working on it!

dotdash updated this revision to Diff 10327.Jun 11 2014, 10:39 AM

Reverted back to the patch the avoids the merge in case of different range
metadata and adjusted the tests to check for the whole function body remaining
unchanged.

dyatkovskiy accepted this revision.Jun 11 2014, 11:12 AM
dyatkovskiy edited edge metadata.

LGTM! Thanks!

This revision is now accepted and ready to land.Jun 11 2014, 11:12 AM
dyatkovskiy added a comment.EditedJun 12 2014, 4:13 PM

Hi Bjorn,
Do you need us to commit your patch? I could do it, if Nick won't object.

Hi Stepan,
yes, I need someone to commit this for me.

Hi Nick,
Can I commit it for Björn?
Thanks!
-Stepan

Björn Steinbrink wrote:

Hi Stepan,
yes, I need someone to commit this for me.

http://reviews.llvm.org/D4062

dyatkovskiy closed this revision.Jun 20 2014, 2:05 PM

Committed as r211391.
Thanks!