Please use GitHub pull requests for new patches. Avoid migrating existing patches. Phabricator shutdown timeline

Paths

Table of Contentst

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

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

Details

Reviewers

broune
eliben
sanjoy
meheff
hfinkel

Commits

rG43885ebb3ab3: [SLSR] handle candidate form (B + i * S)
rL235019: [SLSR] handle candidate form (B + i * S)

Summary

With this patch, SLSR may rewrite

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

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

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

LGTM.

Thanks.
Mark

jingyue updated this object.Apr 14 2015, 11:20 AM

jingyue edited edge metadata.

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

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 ?

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.