MergeFunc: Avoid invalid merge of functions using different range metadata

[dotdash]

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.

[dyatkovskiy]

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.

[dotdash]

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 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.

[dyatkovskiy]

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!

[dotdash]

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 ;-)

[dyatkovskiy]

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]

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]

LGTM! Thanks!

[dyatkovskiy]

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

[dotdash]

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

[dyatkovskiy]

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]

Committed as r211391.
Thanks!

lib/Transforms/IPO/MergeFunctions.cpp

private:
   /// just convert it to integers and call cmpNumbers.
   /// 5. Compare in operation operand types with cmpType in
   /// most significant operand first order.
   /// 6. Last stage. Check operations for some specific attributes.
   /// For example, for Load it would be:
   /// 6.1.Load: volatile (as boolean flag)
   /// 6.2.Load: alignment (as integer numbers)
   /// 6.3.Load: synch-scope (as integer numbers)
+  /// 6.4.Load: range metadata (as integer numbers)
   /// On this stage its better to see the code, since its not more than 10-15
   /// strings for particular instruction, and could change sometimes.
   int cmpOperation(const Instruction *L, const Instruction *R) const;
 
   bool isEquivalentOperation(const Instruction *I1,
                              const Instruction *I2) const {
     return cmpOperation(I1, I2) == 0;
   }
if (const LoadInst *LI = dyn_cast<LoadInst>(L)) {
     if (int Res = cmpNumbers(LI->isVolatile(), cast<LoadInst>(R)->isVolatile()))
       return Res;
     if (int Res =
             cmpNumbers(LI->getAlignment(), cast<LoadInst>(R)->getAlignment()))
       return Res;
     if (int Res =
             cmpNumbers(LI->getOrdering(), cast<LoadInst>(R)->getOrdering()))
       return Res;
-    return cmpNumbers(LI->getSynchScope(), cast<LoadInst>(R)->getSynchScope());
+    if (int Res =
+            cmpNumbers(LI->getSynchScope(), cast<LoadInst>(R)->getSynchScope()))
+      return Res;
+    return cmpNumbers((uint64_t)LI->getMetadata(LLVMContext::MD_range),
+                      (uint64_t)cast<LoadInst>(R)->getMetadata(LLVMContext::MD_range));
   }
   if (const StoreInst *SI = dyn_cast<StoreInst>(L)) {
     if (int Res =
             cmpNumbers(SI->isVolatile(), cast<StoreInst>(R)->isVolatile()))
       return Res;
     if (int Res =
             cmpNumbers(SI->getAlignment(), cast<StoreInst>(R)->getAlignment()))
       return Res;

test/Transforms/MergeFunc/ranges.ll

+; RUN: opt -mergefunc -S < %s | FileCheck %s
+define i1 @cmp_with_range(i8*, i8*) {
+  %v1 = load i8* %0, !range !0
+  %v2 = load i8* %1, !range !0
+  %out = icmp eq i8 %v1, %v2
+  ret i1 %out
+}
+
+define i1 @cmp_no_range(i8*, i8*) {
+; CHECK-LABEL: @cmp_no_range
+; CHECK-NEXT  %v1 = load i8* %0
+; CHECK-NEXT  %v2 = load i8* %1
+; CHECK-NEXT  %out = icmp eq i8 %v1, %v2
+; CHECK-NEXT  ret i1 %out
+  %v1 = load i8* %0
+  %v2 = load i8* %1
+  %out = icmp eq i8 %v1, %v2
+  ret i1 %out
+}
+
+define i1 @cmp_different_range(i8*, i8*) {
+; CHECK-LABEL: @cmp_different_range
+; CHECK-NEXT:  %v1 = load i8* %0, !range !1
+; CHECK-NEXT:  %v2 = load i8* %1, !range !1
+; CHECK-NEXT:  %out = icmp eq i8 %v1, %v2
+; CHECK-NEXT:  ret i1 %out
+  %v1 = load i8* %0, !range !1
+  %v2 = load i8* %1, !range !1
+  %out = icmp eq i8 %v1, %v2
+  ret i1 %out
+}
+
+define i1 @cmp_with_same_range(i8*, i8*) {
+; CHECK-LABEL: @cmp_with_same_range
+; CHECK: tail call i1 @cmp_with_range
+  %v1 = load i8* %0, !range !0
+  %v2 = load i8* %1, !range !0
+  %out = icmp eq i8 %v1, %v2
+  ret i1 %out
+}
+
+!0 = metadata !{i8 0, i8 2}
+!1 = metadata !{i8 5, i8 7}