Page MenuHomePhabricator

[IndVars] Recognize 'sub nuw' expressed as 'add' for widening

Authored by mkazantsev on Oct 16 2020, 6:34 AM.



InstCombine canonicalizes 'sub nuw' instructions to 'add' without the
nuw flag. The typical case where we see it is decrementing induction
variables. For them, IndVars fails to prove that it's legal to widen them,
and inserts unprofitable zext's.

This patch adds recognition of such pattern using SCEV.

Diff Detail

Event Timeline

mkazantsev created this revision.Oct 16 2020, 6:34 AM
fhahn added inline comments.Nov 2 2020, 11:31 AM
1158 ↗(On Diff #301209)

This seems independent of the add x, -y -> sub nuw? Can this be split off into a separate patch? IIUC the test case for the detection without this change would be something like

  %iv = phi i32 [%start, %entry], [, %backedge]
  %cond = icmp eq i32 %iv, 0
  br i1 %cond, label %exit, label %backedge

  %foo = add i32 %iv, -1
  %index = zext i32 %foo to i64
  %store.addr = getelementptr i32, i32* %p, i64 %index
  store i32 1, i32* %store.addr
  %load.addr = getelementptr i32, i32* %q, i64 %index
  %stop = load i32, i32* %q
  %loop.cond = icmp eq i32 %stop, 0 = add i32 %iv, -1
  br i1 %loop.cond, label %loop, label %failure
mkazantsev planned changes to this revision.Nov 5 2020, 10:44 PM
mkazantsev added inline comments.Nov 5 2020, 11:52 PM
1158 ↗(On Diff #301209)

Good point, thanks for catching! I'll split it out.

Split out widen increment logic into separate change.

skatkov accepted this revision.Nov 11 2020, 2:28 AM
skatkov added a subscriber: skatkov.


This revision is now accepted and ready to land.Nov 11 2020, 2:28 AM
fhahn accepted this revision.Nov 11 2020, 4:17 AM

Thanks for the update! LGTM as well.


tiny nit: perhaps move just before use? Or inline.

mkazantsev marked an inline comment as done.Nov 11 2020, 8:50 PM