This is an archive of the discontinued LLVM Phabricator instance.

[SLSR] handle candidate form (B + i * S)
ClosedPublic

Authored by jingyue on Apr 10 2015, 2:27 PM.

Details

Summary

With this patch, SLSR may rewrite

S1: X = B + i * S
S2: Y = B + i' * S

to

S2: Y = X + (i' - i) * S

A secondary improvement: if (i' - i) is a power of 2, emit Y as X + (S << log(i' - i)). (S << log(i' -i)) is in a canonical form and thus more likely GVN'ed than (i' - i) * S.

Diff Detail

Event Timeline

jingyue updated this revision to Diff 23625.Apr 10 2015, 2:27 PM
jingyue retitled this revision from to [SLSR] handle candidate form (B + i * S).
jingyue updated this object.
jingyue edited the test plan for this revision. (Show Details)
jingyue added reviewers: broune, eliben, hfinkel, meheff, sanjoy.
jingyue added a subscriber: Unknown Object (MLST).
jingyue updated this revision to Diff 23626.Apr 10 2015, 2:46 PM

Do not SLSR if (B + i * S) can be folded to an addressing mode.

meheff edited edge metadata.Apr 14 2015, 10:35 AM

LGTM.

Thanks.
Mark

jingyue updated this object.Apr 14 2015, 11:20 AM
jingyue edited edge metadata.
broune edited edge metadata.Apr 14 2015, 1:08 PM

I added some comments not directly related to the patch, since you're the author of the whole pass, but feel free to ignore those parts for this patch.

Would it make sense to avoid transformations like this one?

X = B + 8 * S
Y = B + S

to

X = B + 8 * S
Y = X - 7 * S
lib/Transforms/Scalar/StraightLineStrengthReduce.cpp
29

Might be good to explain here why this is an improvement and where the strength is reduced. The rewritten expression still has the form B + i * S, just with a different B and i. Right? Perhaps we're hoping that (i' - i) * S will be easier to optimize, e.g. if it appears more than once or if i' - i is now -1, 0, 1 or a power of 2?

37

Same comment as above.

39–42

extend -> extent

46

I think this is a definition of what an immediate basis is, though it reads to me as a statement that we either use the closest basis or the immediate basis, which suggests that they are not necessarily the same. Perhaps: with respect to the immediate basis, which is the basis that is the closest ancestor in the dominator tree." Is that what "closest" means here?

54–57

Would it make sense to add a TODO for the case where i - i' is constant but i and i' are not?

79–80

Should there be another case added above for Add, or perhaps just refer to the comments on the entries in Kind instead of duplicating it here?

97–98

This is ambiguous as "may not" can mean "must not" or "might not". I'd do "may not" -> "might not" or rewrite as "does not necessarily have". (I know you didn't change this in this patch, but you're the author of the pass, right?)

105

can corresponds -> can correspond

158

The function name says singular candidate and the comment says plural candidates. So one of them is not right.

205

We also keep track of unlinked instructions by their parent being null, and therefore never insert the same element twice nor query whether an element is in UnlinkedInstructions. So might this better be a lower-overhead type like a vector?

269–270

to -> in

274

Maybe add: in case this expression is later used as an address in a way that is foldable as an addressing mode.

Or am I misunderstanding this? The significant difference seems to me to be that above, we know it's an address and thus will be folded if possible as it's included directly in a GEP and here this expression may or may not feed directly into a GEP later on.

325–326

running forever -> taking too much time. It would terminate.

354

Could add: so that it can be the basis of other candidates.

431

Would it make sense to assert that I has exactly 2 operands?

455–456

is *s a typo?

565

would it make sense to catch the negative of a power of 2?

583–586

Would it make sense to assert that Basis.Ins->getParent() != nullptr ?

jingyue updated this revision to Diff 23750.Apr 14 2015, 9:49 PM
jingyue updated this object.
jingyue edited edge metadata.

Broune's comments

That's a very good point. I think isSimplestForm in the updated patch handles that case. I also added a test. PTAL

Thanks for the detailed review! These comments improved the patch a lot.

lib/Transforms/Scalar/StraightLineStrengthReduce.cpp
29

Done.

37

Done.

39–42

Done.

46

Done.

54–57

Done. I don't think it's a common case, unless you encountered that already? Anyway, it doesn't hurt adding a TODO.

79–80

Done.

97–98

Done.

105

Done.

158

Done.

205

Done.

269–270

Done.

274

Even if an add instruction is not used as an address by a load/store, it can be likely computed in one machine instruction (e.g., leal in x86). I agree this heuristic is inaccurate, but I don't have a better way of characterizing it. Any better idea?

325–326

Done.

354

Done.

431

Done.

455–456

Fixed. I mean ArrayIdx = ArrayIdx *nsw 1.

565

Done. Also added a test on that.

583–586

Done.

eliben accepted this revision.Apr 15 2015, 7:57 AM
eliben edited edge metadata.

LGTM

This revision is now accepted and ready to land.Apr 15 2015, 7:57 AM
jingyue updated this revision to Diff 23781.Apr 15 2015, 9:41 AM
jingyue edited edge metadata.

Minor changes in comments

jingyue closed this revision.Apr 15 2015, 9:49 AM