This is an archive of the discontinued LLVM Phabricator instance.

Differential D12302

Comparing operands should not require the same ValueID
ClosedPublic

Authored by • jrkoenig on Aug 24 2015, 4:41 PM.

Details

Reviewers
dschuff
nlewycky
jfb
Commits
rG9dc042a0b62c: Comparing operands should not require the same ValueID
rL246001: Comparing operands should not require the same ValueID
Summary

When comparing basic blocks, there is an additional check that two
Value*'s should have the same ID, which interferes with merging equivalent
constants of different kinds (such as a ConstantInt and a ConstantPointerNull
in the included testcase). The cmpValues function already ensures that the
two values in each function are the same, so removing this check should not
cause incorrect merging.

Also, the type comparison is redundant, based on reviewing the code and
testing on the test suite and several large LTO bitcodes.

Diff Detail

Repository
rL LLVM

Event Timeline

• jrkoenig updated this revision to Diff 33022.Aug 24 2015, 4:41 PM
• jrkoenig retitled this revision from to Comparing operands should not require the same ValueID.
• jrkoenig updated this object.
• jrkoenig added reviewers: jfb, dschuff, nlewycky.
jfb added inline comments.Aug 25 2015, 11:20 AM
test/Transforms/MergeFunc/merge-const-ptr-and-int.ll
2 ↗(On Diff #33022)

Could you add:

  • An equivalent negative test, where i32 and i32* are returned with the same p:64 datalayout. Those shouldn't be merged.
  • A test where ret i64 1 isn't merged with ret i64* null.
  • Test where other equivalent types are merged (vector, array, structure).
  • A test where undef of different types is merged.
  • A test where endianness would be relevant.
4 ↗(On Diff #33022)

"differ"

• jrkoenig updated this revision to Diff 33110.Aug 25 2015, 1:11 PM

Added more positive/negative tests.

jfb added inline comments.Aug 25 2015, 1:20 PM
test/Transforms/MergeFunc/merge-const-ptr-and-int.ll
3 ↗(On Diff #33110)

Missing undef and endian.

27 ↗(On Diff #33110)

Here you test A and B funcs by calling them, whereas below you check whether functions are still defined. You should be consistent!

• jrkoenig added inline comments.Aug 25 2015, 1:32 PM
test/Transforms/MergeFunc/merge-const-ptr-and-int.ll
3 ↗(On Diff #33110)

Added 1,2, and 3. For 3, only vectors are considered bitcast-able, and thus the mergable.

For 4, this is not possible. In fact, two constants with the same type, one undef and the other not, will not be merged, because they cannot compare equal.

Consider f() { return -1; }, g() { return undef; } and h() { return 1;}. If undef was the same as any constant, the ordering would not be a total order because f == g and g == h, but f < h. In order to handle this, the undef would need to be turned into one of the constants -1 or 1, but it can't be both at once. This would have to be an in-place mutation in the comparison, which is quite ugly.

For 5, I don't think such a thing is possible. The only way endianness can be exposed is by converting a <2x i32> into a < 8 x i8 >, or some other equivalent conversion. This is allowed by cmpConstants. But any extraction from that vector/operation on it will have a different type, and thus compare differently, so practically I doubt you can construct a program which depends on endianess.

• jrkoenig added a subscriber: llvm-commits.Aug 25 2015, 1:32 PM
jfb added inline comments.Aug 25 2015, 1:38 PM
test/Transforms/MergeFunc/merge-const-ptr-and-int.ll
3 ↗(On Diff #33110)

For undef you can at least merge two functions of different types, but where both are undef?

27 ↗(On Diff #33110)

Missing this :)

• jrkoenig updated this revision to Diff 33114.Aug 25 2015, 1:44 PM

Added undef tests; use consistent merge-checking method

• jrkoenig updated this revision to Diff 33116.Aug 25 2015, 1:47 PM

Formatting fixups.

jfb edited edge metadata.Aug 25 2015, 1:59 PM

Ugh... sorry for more comments... I think you should separate each test into its own .ll file: as is they check that merging occurred, but the tests doesn't validate *what* got merged! Having them in separate files would make that obvious and potentially catch tricky bugs.

I'm good after that!

test/Transforms/MergeFunc/merge-const-ptr-and-int.ll
2 ↗(On Diff #33116)

Bikeshed: CHECKNOT-NOT is a bit weird. MERGED-NOT would be nicer.

• jrkoenig updated this revision to Diff 33121.Aug 25 2015, 2:18 PM
• jrkoenig edited edge metadata.

Split tests into different files.

jfb accepted this revision.Aug 25 2015, 2:21 PM
jfb edited edge metadata.

lgtm

This revision is now accepted and ready to land.Aug 25 2015, 2:21 PM
dschuff accepted this revision.Aug 25 2015, 3:23 PM
dschuff edited edge metadata.
Closed by commit rL246001: Comparing operands should not require the same ValueID (authored by jfb). · Explain WhyAug 25 2015, 8:03 PM
This revision was automatically updated to reflect the committed changes.

Revision Contents

PathSize
llvm/
trunk/
lib/
Transforms/
IPO/
7 lines
test/
Transforms/
MergeFunc/
20 lines
18 lines
24 lines
23 lines
21 lines

Diff 33173

llvm/trunk/lib/Transforms/IPO/MergeFunctions.cpp

Show First 20 Lines • Show All 1,076 Lines • ▼ Show 20 Lines if (GEPL && GEPR) {
return Res; return Res;
assert(InstL->getNumOperands() == InstR->getNumOperands()); assert(InstL->getNumOperands() == InstR->getNumOperands());
for (unsigned i = 0, e = InstL->getNumOperands(); i != e; ++i) { for (unsigned i = 0, e = InstL->getNumOperands(); i != e; ++i) {
Value *OpL = InstL->getOperand(i); Value *OpL = InstL->getOperand(i);
Value *OpR = InstR->getOperand(i); Value *OpR = InstR->getOperand(i);
if (int Res = cmpValues(OpL, OpR)) if (int Res = cmpValues(OpL, OpR))
return Res; return Res;
if (int Res = cmpNumbers(OpL->getValueID(), OpR->getValueID())) // cmpValues should ensure this is true.
return Res; assert(cmpTypes(OpL->getType(), OpR->getType()) == 0);
// TODO: Already checked in cmpOperation
if (int Res = cmpTypes(OpL->getType(), OpR->getType()))
return Res;
} }
} }
++InstL, ++InstR; ++InstL, ++InstR;
} while (InstL != InstLE && InstR != InstRE); } while (InstL != InstLE && InstR != InstRE);
if (InstL != InstLE && InstR == InstRE) if (InstL != InstLE && InstR == InstRE)
return 1; return 1;
▲ Show 20 Lines • Show All 673 Lines • Show Last 20 Lines

llvm/trunk/test/Transforms/MergeFunc/merge-const-ptr-and-int.ll

; RUN: opt -mergefunc -S < %s | FileCheck %s
; RUN: opt -mergefunc -S < %s | FileCheck -check-prefix=MERGE %s
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
; Afunc and Bfunc differ only in that one returns i64, the other a pointer.
; These should be merged.
define internal i64 @Afunc(i32* %P, i32* %Q) {
; CHECK-LABEL: define internal i64 @Afunc
store i32 4, i32* %P
store i32 6, i32* %Q
ret i64 0
}
define internal i64* @Bfunc(i32* %P, i32* %Q) {
; MERGE-NOT: @Bfunc
store i32 4, i32* %P
store i32 6, i32* %Q
ret i64* null
}

llvm/trunk/test/Transforms/MergeFunc/merge-different-vector-types.ll

; RUN: opt -mergefunc -S < %s | FileCheck %s
; RUN: opt -mergefunc -S < %s | FileCheck -check-prefix=MERGE %s
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
; Merging should still work even if the values are wrapped in a vector.
define internal <2 x i64> @Mfunc(i32* %P, i32* %Q) {
; CHECK-LABEL: define internal <2 x i64> @Mfunc
store i32 1, i32* %P
store i32 1, i32* %Q
ret <2 x i64> <i64 0, i64 0>
}
define internal <2 x i64*> @Nfunc(i32* %P, i32* %Q) {
; MERGE-NOT: @Nfunc
store i32 1, i32* %P
store i32 1, i32* %Q
ret <2 x i64*> <i64* null, i64* null>
}

llvm/trunk/test/Transforms/MergeFunc/no-merge-ptr-different-sizes.ll

; RUN: opt -mergefunc -S < %s | FileCheck %s
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
; These should not be merged, as the datalayout says a pointer is 64 bits. No
; sext/zext is specified, so these functions could lower differently.
define internal i32 @Ffunc(i32* %P, i32* %Q) {
; CHECK-LABEL: define internal i32 @Ffunc
; CHECK-NEXT: store
; CHECK-NEXT: store
; CHECK-NEXT: ret
store i32 1, i32* %P
store i32 3, i32* %Q
ret i32 0
}
define internal i64* @Gfunc(i32* %P, i32* %Q) {
; CHECK-LABEL: define internal i64* @Gfunc
; CHECK-NEXT: store
; CHECK-NEXT: store
; CHECK-NEXT: ret
store i32 1, i32* %P
store i32 3, i32* %Q
ret i64* null
}

llvm/trunk/test/Transforms/MergeFunc/no-merge-ptr-int-different-values.ll

; RUN: opt -mergefunc -S < %s | FileCheck %s
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
; These should not be merged, as 1 != 0.
define internal i64 @Ifunc(i32* %P, i32* %Q) {
; CHECK-LABEL: define internal i64 @Ifunc
; CHECK-NEXT: store
; CHECK-NEXT: store
; CHECK-NEXT: ret
store i32 10, i32* %P
store i32 10, i32* %Q
ret i64 1
}
define internal i64* @Jfunc(i32* %P, i32* %Q) {
; CHECK-LABEL: define internal i64* @Jfunc
; CHECK-NEXT: store
; CHECK-NEXT: store
; CHECK-NEXT: ret
store i32 10, i32* %P
store i32 10, i32* %Q
ret i64* null
}

llvm/trunk/test/Transforms/MergeFunc/undef-different-types.ll

; RUN: opt -mergefunc -S < %s | FileCheck %s
; RUN: opt -mergefunc -S < %s | FileCheck -check-prefix=MERGE %s
target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
; Cfunc and Dfunc differ only in that one returns i64, the other a pointer, and
; both return undef. They should be merged. Note undef cannot be merged with
; anything else, because this implies the ordering will be inconsistent (i.e.
; -1 == undef and undef == 1, but -1 < 1, so we must have undef != <any int>).
define internal i64 @Cfunc(i32* %P, i32* %Q) {
; CHECK-LABEL: define internal i64 @Cfunc
store i32 4, i32* %P
store i32 6, i32* %Q
ret i64 undef
}
define internal i64* @Dfunc(i32* %P, i32* %Q) {
; MERGE-NOT: @Dfunc
store i32 4, i32* %P
store i32 6, i32* %Q
ret i64* undef
}