Page MenuHomePhabricator

[SimpligyCFG] NFC, remove GCD that was only used for powers of two
ClosedPublic

Authored by shawnl on Apr 25 2019, 1:58 PM.

Details

Summary

This is patch 2 is a series beginning with D61150

and replace with an equilivent countTrailingZeros.

GCD is much more expensive than this, with repeated division.

And actually using the full GCD would require multiplication in the generated code.

This depends on D60823

Diff Detail

Event Timeline

shawnl created this revision.Apr 25 2019, 1:58 PM
shawnl edited the summary of this revision. (Show Details)
shawnl added a reviewer: jmolloy.
shawnl set the repository for this revision to rL LLVM.
Herald added a project: Restricted Project. · View Herald TranscriptApr 25 2019, 1:58 PM
shawnl edited the summary of this revision. (Show Details)Apr 25 2019, 4:18 PM
jmolloy requested changes to this revision.Apr 26 2019, 12:46 AM

Thanks for splitting these up! They're really much easier to read.

Some comments, but none of them fatal.

Cheers!

lib/Transforms/Utils/SimplifyCFG.cpp
5543

It feels to me like this comment still has value - perhaps it should be kept?

5550

I personally would rewrite this whole thing as:

unsigned Shift = 64;
for (auto &V : Values)
  Shift = std::min(Shift, countTrailingZeros((uint64_t)V);

I don't see the need for the zero bailout.

5551

This comment could be clearer. I've tried to understand it a couple of times and only vaguely do. Could you please rewrite it so that it clearly states *which* edge condition you're referring to (I presume ctz(0)?)

5561

Shift is an integer, not a pointer or boolean, so please use if (Shift != 0).

5563

Nit: I'd use:

V >>= Shift;

Just to make it ultra-clear that we're updating V in-place (updating a mutable reference iterator is fine in this case, but it's something readers normally expect so it'd be good to make this very clear).

This revision now requires changes to proceed.Apr 26 2019, 12:46 AM
nikic added a subscriber: nikic.Apr 26 2019, 12:49 AM
nikic added inline comments.Apr 26 2019, 10:27 AM
lib/Transforms/Utils/SimplifyCFG.cpp
5563

It's rather hidden due to overzealous auto use, but this is going to perform an arithmetic shift. This doesn't seem correct to me, as the used rotate operation degenerates to a logical shift for valid values (with low bits unset).

shawnl marked an inline comment as done.Apr 27 2019, 7:31 PM
shawnl added inline comments.
lib/Transforms/Utils/SimplifyCFG.cpp
5563

Yeah, that happened when I split the patches up. (and the style issue because I just simplified the old code, but I was using unsigned then)

jmolloy added inline comments.Apr 29 2019, 1:05 AM
lib/Transforms/Utils/SimplifyCFG.cpp
5553

I completely misinterpreted this comment and this code. I thought your comment referred to *runtime behaviour* of generated cttz instructions. Actually it's just referring to the return value of llvm::countTrailingZeros().

I'd recommend making this comment less scary. My suggestion would be:

countTrailingZeros(0) returns 64. As Values is guaranteed to have more than one element and LLVM disallows duplicate cases, Shift is guaranteed to be less than 64.

... and then add an assert(Shift < 64) afterwards to prove it.

5563

I'd recommend just switching to using APInt. That's what it's for after all - making things like this self-explaining.

jmolloy requested changes to this revision.Apr 30 2019, 4:32 AM
This revision now requires changes to proceed.Apr 30 2019, 4:32 AM
shawnl marked an inline comment as done.Apr 30 2019, 7:00 AM
shawnl added inline comments.
lib/Transforms/Utils/SimplifyCFG.cpp
5563

I remove your signed interpretation in a later patch.

shawnl updated this revision to Diff 197333.Apr 30 2019, 8:02 AM
jmolloy accepted this revision.May 1 2019, 12:40 AM

LGTM.

This revision is now accepted and ready to land.May 1 2019, 12:40 AM
shawnl closed this revision.May 26 2019, 7:45 AM

applied 361726