This is an archive of the discontinued LLVM Phabricator instance.

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

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

Details

Summary

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
llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
1158

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

loop:
  %iv = phi i32 [%start, %entry], [%iv.next.1, %backedge]
  %cond = icmp eq i32 %iv, 0
  br i1 %cond, label %exit, label %backedge

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
  %iv.next.1 = 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
llvm/lib/Transforms/Scalar/IndVarSimplify.cpp
1158

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.

lgtm

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.

llvm/lib/Transforms/Utils/SimplifyIndVar.cpp
1552 ↗(On Diff #303343)

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

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