This is an archive of the discontinued LLVM Phabricator instance.

[IndVarSimplify] Wisely choose sext or zext when widening IV
ClosedPublic

Authored by lihuang on Sep 6 2016, 2:37 PM.

Details

Summary

[IndVarSimplify] Wisely choose sext or zext when widening IV.

This is to fix the performance regression caused by two earlier patches: D18777 and D18867. (both were reverted).

The problem was, with those patches, some IV sexts are converted to zexts. IndVarSimplify marks the IV as signed or unsigned based on its cast users which comes first. If the IV's first cast user is a zext, it will be marked as unsigned. However, marking the IV as unsigned will cause the IV to be zero-extended during widening, if the IV also has sext users (e.g. a sext of IV for GEP), the sext cannot be removed and trunc is introduced. In general, we want to remove as many s/zexts as possible during widening.

The idea of this patch is to mark the IV as singed even if its first cast user is a zext, when

  1. This IV is known to be non-negative
  2. The first cast user, zext, has a GEP user. (GEP's offsets are treated as signed values)

Diff Detail

Event Timeline

lihuang updated this revision to Diff 70468.Sep 6 2016, 2:37 PM
lihuang retitled this revision from to [IndVarSimplify] Prefer sext over zext when widening IV if it is non-negative and has a GEP user.
lihuang updated this object.
lihuang added reviewers: apilipenko, reames, sanjoy.
lihuang added a subscriber: Farhana.
lihuang updated this revision to Diff 70473.Sep 6 2016, 2:40 PM

Sorry, didn't generate a full diff.

reames edited edge metadata.Sep 6 2016, 3:39 PM

I would suggest framing this slightly differently. If we know the IV is positive, we know that a sext and an zext must produce exactly the same result. We should canonicalize on one of them in general (which I think is what your previous patches caused) and the widening code should produce the optimal result for either. In fact, it looks like there's a NeverNegative flag on NarrowIVDefUse which already tries to do this.

I think the problem here is that we're failing to use this information in getWideRecurrence?

Note that I'm not an expert in this code and would really appreciate a second opinion.

reames added a comment.Sep 6 2016, 3:45 PM

Another way of framing the possible fix is to change:

// Our raison d'etre! Eliminate sign and zero extension.
if (IsSigned ? isa<SExtInst>(DU.NarrowUse) : isa<ZExtInst>(DU.NarrowUse))

To:

if ((DU.NeverNegative && (isa<SExtInst>(DU.NarrowUse) || isa<ZExtInst>(DU.NarrowUse))) ||
   (IsSigned ? isa<SExtInst>(DU.NarrowUse) : isa<ZExtInst>(DU.NarrowUse)))

Obviously, clean up the code please. :)

This handles the sext/zext cases, but not the GEP cases. That still needs the getWideRecurrence parts.

sanjoy requested changes to this revision.Sep 6 2016, 9:37 PM
sanjoy edited edge metadata.

Please add some test cases showing what specific cases you're trying to fix. Generally I agree with Philip's reasoning above -- this fix seems somewhat ad-hoc, if we _can_ prove that the narrow iv is positive, we should be able to take opportunistically pretend it was a signed or unsigned extension on a case by case basis (and get the best of both worlds).

This revision now requires changes to proceed.Sep 6 2016, 9:37 PM
reames added a comment.Sep 7 2016, 7:33 AM

Also, as a separate patch, it would be good to add optimizations which cleanup the poor IR generated without the patch. In particular, we should be able to zext(trunc(sext(x))) and sext(trunc(zext(x)))) should be foldable when we know that x is a positive number within the range of the trunc output space. Both InstCombine (ValueTracking) and CVP (LVI) should be able to handle these cases. Same for the GEP cases.

Another way of framing the possible fix is to change:

// Our raison d'etre! Eliminate sign and zero extension.
if (IsSigned ? isa<SExtInst>(DU.NarrowUse) : isa<ZExtInst>(DU.NarrowUse))

To:

if ((DU.NeverNegative && (isa<SExtInst>(DU.NarrowUse) || isa<ZExtInst>(DU.NarrowUse))) ||
   (IsSigned ? isa<SExtInst>(DU.NarrowUse) : isa<ZExtInst>(DU.NarrowUse)))

Obviously, clean up the code please. :)

This handles the sext/zext cases, but not the GEP cases. That still needs the getWideRecurrence parts.

This is the same logic as in D18867, but this is not enough, as you said, it doesn't work for the GEP cases.

Hi Philip, Sanjoy,

Thank you for the suggestions. getWideRecurrence gives a zero-extended SCEV when IsSigned is false. We could also change it to return a sign-extended SCEV when value being extended is known non-negative.

I agree that we should canonicalize on one of the extends when the value being extended is non-negative.

InstCombine canonicalizes on zexts when the value is non-negative. I will try canonicalizing on zext and teach getWideRecurrence to return a valid AddRec when the non-negative value is zero-extended.

lihuang updated this revision to Diff 70955.Sep 10 2016, 6:45 PM
lihuang edited edge metadata.

Canonicalize on zext when IV is known non-negative. Then, for each def-use pair of IV users, choose the kind of extension based on the following strategy:

if the narrow def is non-negative, use either sext or zext which applies to the narrow user.
otherwise, use the same extension applied to narrow def for the narrow user.

I added a map in class WidenIV to track the kind of extension used for each IV user, and basically changed every query to WideIV::IsSigned to a query into this map. The reason is, each narrow user should rely on its narrow def to choose sext/zext rather than the signedness of original IV, as the IV could be either sign extended or zero extended. Should be able to integrate this map with the Widened set, but I want to make sure I am in the right direction first.

This change includes the logic in D18867, so added those 2 test cases here. The 3rd test case comes from TSVC/174 (regression caused by D18777). All sext/zext to IV users in these 3 tests should be removed.

Ping :),

Do you think this is the right direction?

Thanks,
-Li

Hi Li,

Sorry, I've been a bit busier than usual. I'll take a look at this this weekend.

  • Sanjoy

Hi Sanjoy,

No problem, take your time.

sanjoy requested changes to this revision.Sep 18 2016, 11:51 PM
sanjoy edited edge metadata.

Some comments inline.

lib/Transforms/Scalar/IndVarSimplify.cpp
916

Please name the name so that the intent of the bool is obvious (perhaps WasSignExtended?). Or (even better) use something other than a bool as the domain (perhaps an enum?). Also, clang-format.

946

I'm not a big fan of returning via params like these -- it is too easy to forget to update the return value along one path. Have you considered returning an std::pair or even a hand-rolled struct instead?

954

Document these please.

1163

Common these three ExtendKindMap[DU.NarrowDef] lookups into one with a descriptive name.

Actually, these should not look up the DenseMap directly like these -- if DU.NarrowDef is not in ExtendKindMap then we'll get a bogus false result here. You should add an accessor that will trip an assert if DU.NarrowDef is not present in ExtendKindMap.

1197

Here and elsewhere please document the new WidenBySext paramenter.

1220

clang-format please

1391

I'd spell it as canWidenBySExt (same below).

1470

Does ExtendKindMap subsume the IsSigned field? If so, that field should be removed.

This revision now requires changes to proceed.Sep 18 2016, 11:51 PM
lihuang updated this revision to Diff 72371.Sep 23 2016, 3:25 PM
lihuang retitled this revision from [IndVarSimplify] Prefer sext over zext when widening IV if it is non-negative and has a GEP user to [IndVarSimplify] Wisely choose sext or zext when widening IV.
lihuang updated this object.
lihuang edited edge metadata.

Address Sanjoy's comments.

lihuang marked 8 inline comments as done.Sep 23 2016, 3:44 PM

Add another test case where zext should not be removed.

lib/Transforms/Scalar/IndVarSimplify.cpp
916

Sorry for the late reply, I was working on other stuff.

Added an enum type ExtendKind.

946

thanks for the suggestion, I changed the return type to a std::pair of AddRec* and ExtendKind.

1163–1164

Actually DU.NarrowDef should be already in this map when we come to visit NarrowUse, because we visit NarrowDef before pushing NarrowUse to the queue when doing BFS.

I added an assert in WidenIVUse to ensure this.

1194–1198

Removed this parameter.

1470

Yes it does, removed the IsSigned field from WidenIV.

sanjoy requested changes to this revision.Sep 24 2016, 12:24 AM
sanjoy edited edge metadata.

Hi Li,

This is looking fairly close to ready. I mostly have some nitpicky comments inline.

lib/Transforms/Scalar/IndVarSimplify.cpp
919

Make the domain of this map an AssertingVH to guard against use-after-free bugs.

1163–1164

Actually DU.NarrowDef should be already in this map when we come to visit NarrowUse, because we visit NarrowDef before pushing NarrowUse to the queue when doing BFS.

Yes, but I'd rather have the assert automatically trigger anything you access ExtendKindMap.

1202

s/SignExtended/Unknown/

Not compulsory to change: you can use {A, B} instead of std::make_pair(A, B).

1306

Have you considered putting canWidenBySExt and canWidenByZExt as lambdas here? That will make things more readable I think.

1347

Add an assert((WideAddRec.first == nullptr) == (.second == Unknown)).

This revision now requires changes to proceed.Sep 24 2016, 12:24 AM
lihuang updated this revision to Diff 72548.Sep 26 2016, 1:05 PM
lihuang edited edge metadata.
lihuang marked 10 inline comments as done.
lihuang marked an inline comment as done.
lihuang added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
1306–1307

Good suggestion :) I changed them to lambdas

sanjoy requested changes to this revision.Sep 26 2016, 1:12 PM
sanjoy edited edge metadata.

Only one thing left. :)

lib/Transforms/Scalar/IndVarSimplify.cpp
1163–1164

This was not done.

To be clear: I was suggesting adding a method:

ExtendKind getExtendKind(Instruction *I) {
  auto It = ExtendKindMap.find(I);
  assert(It != ExtendKindMap.end() && "Not found!");
  return It->second;
}

to the WidenIV class, and using that instead of ExtendKindMap[DU.NarrowDef] here and below.

This revision now requires changes to proceed.Sep 26 2016, 1:12 PM
lihuang marked an inline comment as done.Sep 26 2016, 1:27 PM
lihuang added inline comments.
lib/Transforms/Scalar/IndVarSimplify.cpp
1163–1164

I see...

I think DenseMap should have an "at" like std::map::at, but it doesn't. Okay, I will add a method like you are suggesting here.

lihuang updated this revision to Diff 72569.Sep 26 2016, 2:28 PM
lihuang edited edge metadata.
lihuang marked an inline comment as done.
sanjoy accepted this revision.Sep 26 2016, 2:40 PM
sanjoy edited edge metadata.

Lgtm

This revision is now accepted and ready to land.Sep 26 2016, 2:40 PM

Committed.
Revision 282650

lihuang closed this revision.Sep 28 2016, 5:38 PM