Page MenuHomePhabricator

Optimize memcmp(x,y,n)==0 for small n and suitably aligned x/y.
ClosedPublic

Authored by Eelis on Jan 13 2015, 11:20 AM.

Diff Detail

Event Timeline

Eelis updated this revision to Diff 18100.Jan 13 2015, 11:20 AM
Eelis retitled this revision from to Optimize memcmp(x,y,n)==0 for small n and suitably aligned x/y..
Eelis updated this object.
Eelis edited the test plan for this revision. (Show Details)
Eelis added a subscriber: Unknown Object (MLST).
joerg added a subscriber: joerg.Jan 13 2015, 11:50 PM

For platforms with suppport for unaligned access, this is always a win, isn't it? I.e. independent of the correct alignment of the pointers.

Thanks Joerg, that's a great point!

I don't really know how to do that though. I see that the memcmp code in SelectionDAGBuilder.cpp uses allowsMisalignedMemoryAccesses(), but that function takes an EVT, a type which is not known in Transforms/Utils/SimplifyLibCalls.cpp.

majnemer added inline comments.
lib/Transforms/Utils/SimplifyLibCalls.cpp
955

Isn't the RHS just isPowerOf2_64?

Also, '8' sounds awfully target specific. I doubt this is the correct number for the MSP430 target.

956–958

This seems strangely formatted, consider running clang-format over these lines.

960

There is no need to manually strength-reduce multiplication by eight. Also, this can never fail.

962–965

Perhaps:

Type *LHSPtrTy =
    IntType->getPointerTo(LHS->getType()->getPointerAddressSpace());
Type *RHSPtrTy =
    IntType->getPointerTo(RHS->getType()->getPointerAddressSpace());
Eelis added a comment.Jan 14 2015, 6:58 AM

Thanks David! I'll attach an updated patch, but I don't know how to get rid of the "8" constant.

lib/Transforms/Utils/SimplifyLibCalls.cpp
955

Oh, I just took this from InstCombiner::SimplifyMemTransfer, which does:

if (Size > 8 || (Size&(Size-1)))
  return nullptr;  // If not 1/2/4/8 bytes, exit.

I'll use isPowerOf2_64 instead, but I'm not sure what I should I use instead of 8.

956–958

I like the &&s aligned on the left so I easily see it's a repeated conjunction, but I see that clang-format wants them on the right, so I'll do that.

960

Oh, I just took the "Len << 3" from InstCombiner::SimplifyMemTransfer. Will fix. :)

962–965

This too I just took from InstCombiner::SimplifyMemTransfer. I will use what you suggest instead.

Eelis updated this revision to Diff 18151.Jan 14 2015, 7:11 AM

Addressed all review comments except the "Len <= 8" check, because I don't know what should be used instead.

Eelis added a comment.Jan 14 2015, 7:12 AM

Oh crap, left out the tests this time. Reuploading.

Eelis updated this revision to Diff 18152.Jan 14 2015, 7:13 AM

Now once more with tests. :)

mcrosier added inline comments.
test/Transforms/InstCombine/memcmp-1.ll
77

; CHECK-LABEL:

94

; CHECK-LABEL:

111

; CHECK-LABEL:

Eelis added a comment.Jan 14 2015, 7:57 AM

Thanks mcrosier, will fix!

(I'm curious: how come this wasn't caught when I ran the tests? Are these names case-insensitive?)

Eelis updated this revision to Diff 18153.Jan 14 2015, 8:01 AM

CHECK-label -> CHECK-LABEL

In D6952#108619, @Eelis wrote:

(I'm curious: how come this wasn't caught when I ran the tests? Are these names case-insensitive?)

The tests will pass with or without the CHECK-LABEL directives. I believe the FileCheck directives are case-sensitive, but I would have to look at the FileCheck implementation to verify. Regardless, CHECK-LABEL is the preferred style.

Chad

majnemer accepted this revision.Jan 21 2015, 2:55 AM
majnemer added a reviewer: majnemer.

LGTM

This revision is now accepted and ready to land.Jan 21 2015, 2:55 AM

Eelis,
Do you have commit rights? If not, I'd be happy to commit the patch on your behalf.

Chad

Eelis added a comment.Jan 22 2015, 4:41 PM

I don't think this code should be committed yet, because it does not yet check whether the integer types are available. I tried doing it with:

if (DL && DL->isLegalInteger(Len * 8) && ...

.. but that doesn't work (and the tests fail) because DL is nullptr.

Eelis updated this revision to Diff 18738.Jan 25 2015, 9:17 PM
Eelis edited edge metadata.

Ah, it wasn't that DL was null, but rather that there were no native integer types specified in the target datalayout for the test. I've added those, and I've also refined the alignment check to take the integer type's preferred alignment into account.

I think it's okay to commit now. Chad: I don't have commit rights, so yes please! Thanks :)

mcrosier requested changes to this revision.Aug 28 2015, 10:33 AM
mcrosier added a reviewer: mcrosier.

@majnemer: David, would you mind giving this a once over before I commit? This has been sitting for many months..

This revision now requires changes to proceed.Aug 28 2015, 10:33 AM
majnemer accepted this revision.Aug 28 2015, 10:35 AM
majnemer edited edge metadata.

LGTM

mcrosier accepted this revision.Aug 28 2015, 11:31 AM
mcrosier edited edge metadata.

Committed r246313.

This revision is now accepted and ready to land.Aug 28 2015, 11:31 AM
mcrosier closed this revision.Aug 28 2015, 11:31 AM