Page MenuHomePhabricator

[ValueTracking] An improvement to IR ValueTracking on Non-negative Integers
ClosedPublic

Authored by lihuang on Apr 4 2016, 5:20 PM.

Details

Summary

An improvement to IR ValueTracking on Non-negative Integers.

Current IR ValueTracking does not recognize the cases below, thus hiding optimization opportunities.

  1. Induction variable starting from a non-negative integer and incrementing in each iteration is known to be non-negative.
  2. Result of left shifting a non-negative integer with nsw flag is known to be non-negative.

This change is a small improvement to computeKnownBits on PHI node and Shift.

Patch by Ruben Perez.

Diff Detail

Repository
rL LLVM

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
lihuang updated this revision to Diff 52635.Apr 4 2016, 5:20 PM
lihuang added reviewers: mbodart, reames, sanjoy.
lihuang added a subscriber: llvm-commits.
sanjoy requested changes to this revision.Apr 5 2016, 12:19 AM
sanjoy edited edge metadata.
sanjoy added inline comments.
lib/Analysis/ValueTracking.cpp
805 ↗(On Diff #52635)

Can this rule be split out into a separate change of its own (with its own tests etc.)?

lib/Transforms/Scalar/IndVarSimplify.cpp
1309 ↗(On Diff #52635)

Usually we refrain from changing multiple passes at once. Can you please move these IndVarSimplify changes to their own patch, with their own tests?

test/Analysis/ValueTracking/shift-nsw.ll
11 ↗(On Diff #52635)
  • The filename is misleading -- there is a lot going on here other than the "nsw shift" optimization.
  • Please break these into small bits of IR functions each of which show one transform.
  • Use CHECK-LABEL
This revision now requires changes to proceed.Apr 5 2016, 12:19 AM

I will separate the change in IndVarSimplify into another patch and create a new diff.

lib/Analysis/ValueTracking.cpp
805 ↗(On Diff #52635)

Yes it could, I will make a separate patch for this with its own tests.

lib/Transforms/Scalar/IndVarSimplify.cpp
1309 ↗(On Diff #52635)

Sure, I will make a separate patch for this change and its tests.

test/Analysis/ValueTracking/shift-nsw.ll
11 ↗(On Diff #52635)

Thanks! I will update this test.

lihuang updated this revision to Diff 52738.Apr 5 2016, 3:12 PM
lihuang edited edge metadata.

Make a separate patch for changes in ValueTracking.cpp. Updated the tests. Changes in IndVarSimplify.cpp will go to another diff.

This change fails a front-end test (Frontend/optimization-remark-options.c), but the change in IndVarSimplify.cpp will fix this test.

lihuang updated this revision to Diff 52740.Apr 5 2016, 3:36 PM
lihuang edited edge metadata.

Sorry I didn't generate a full diff, updated.

Ping :), any suggestions/comments on this change?

mbodart added inline comments.Apr 15 2016, 4:20 PM
lib/Analysis/ValueTracking.cpp
817 ↗(On Diff #52740)

This could be an "else if", as the sign bit cannot be both known 0 and known 1.

1301 ↗(On Diff #52740)

For the Sub case we have to be more careful about which value is the LHS and which is the RHS.
The way the code is currently structured, if (LL == I) then R is the LHS and L is the RHS,
otherwise vice versa. So we have to take (LL == I) into account to know whether to
check (KnownZero3, KnownOne2) or (KnownZero2, KnownOne3).

And while I don't know how valuable it would be to catch additional cases, we could set a KnownOne sign bit result for the Sub case if it's (negative -= non-negative), and for the Add case if it's (negative += negative).

test/Analysis/ValueTracking/known-non-negative.ll
6 ↗(On Diff #52740)

Please add additional test cases for mul and sub.

reames requested changes to this revision.Apr 18 2016, 5:08 PM
reames edited edge metadata.
This revision now requires changes to proceed.Apr 18 2016, 5:08 PM
lihuang updated this revision to Diff 54519.Apr 21 2016, 9:58 AM
lihuang edited edge metadata.

Address Mitch's comments.

For the sub case, I added the check (LL == I), this is the case when IV is LHS. I didn't add the case when IV is RHS because it's hard to infer anything meaningful.

mbodart added inline comments.Apr 21 2016, 1:51 PM
lib/Analysis/ValueTracking.cpp
1292 ↗(On Diff #54519)

This "if", and the one below for Mul, should be "else if".

Otherwise LGTM!

lihuang updated this revision to Diff 54592.Apr 21 2016, 4:14 PM
lihuang edited edge metadata.
lihuang updated this revision to Diff 62032.Jun 27 2016, 4:19 PM

Rebase the same patch on the latest source.

This ValueTracking change breaks a FE test (clang/test/Frontend/optimization-remark-options.c), but now the test could be fixed by D18777 and D21773.

Rebase the same patch on the latest source.

This ValueTracking change breaks a FE test (clang/test/Frontend/optimization-remark-options.c), but now the test could be fixed by D18777 and D21773.

Sorry, my mistake, the test could be fixed by D18867 and D21773.

lihuang updated this revision to Diff 65843.Jul 27 2016, 5:15 PM

Rebase this change on latest source. The test in D21773 should be fixed by D18867.

Another Ping for this patch :).

Sanjoy, this patch and D18867 depends on each other so they need to go in at the same time, otherwise it will break tests.

sanjoy requested changes to this revision.Aug 5 2016, 6:12 PM
sanjoy edited edge metadata.
sanjoy added inline comments.
lib/Analysis/ValueTracking.cpp
788 ↗(On Diff #65843)

I'd s/KnownZero2/KnownZeroOp (same for KnownOne2), and s/KnownZero/KnownZeroResult/. Also, pass in KnownZeroOp by const ref.

796 ↗(On Diff #65843)

Why can't this be folded into the KZF and KOF for the Instruction::Shl case?

1271 ↗(On Diff #65843)

Use auto *.

1288 ↗(On Diff #65843)

What does this bit have to do with the changes to how we handle shifts? If they're not related, they should definitely be reviewed/tested/committed separately.

This revision now requires changes to proceed.Aug 5 2016, 6:12 PM
lihuang added inline comments.Aug 8 2016, 12:22 PM
lib/Analysis/ValueTracking.cpp
796 ↗(On Diff #65843)

Thank you for suggesting this, will fold this logic to KZF and KOF

1288 ↗(On Diff #65843)

Will separate out the shift part

lihuang updated this revision to Diff 67236.Aug 8 2016, 3:46 PM
lihuang edited edge metadata.

Separate the non-negative shift changes to another patch. Address Sanjoy's comments.

sanjoy requested changes to this revision.Aug 8 2016, 11:08 PM
sanjoy edited edge metadata.

Mostly looks okay, I just have a few minor nits.

lib/Analysis/ValueTracking.cpp
1248 ↗(On Diff #67236)

s/Initial/initial/

1255 ↗(On Diff #67236)

Nit: I'd use setBit instead of |= with a new APInt. For BitWidth larger than 64, what you have currently will allocate unnecessarily, and I think setBit will look just as obvious (if not more).

1275 ↗(On Diff #67236)

Indent looks off -- please use clang-format.

This revision now requires changes to proceed.Aug 8 2016, 11:08 PM
lihuang updated this revision to Diff 67399.Aug 9 2016, 12:57 PM
lihuang edited edge metadata.

Use APInt::setBit, fix the indentation

lihuang added inline comments.Aug 9 2016, 12:58 PM
lib/Analysis/ValueTracking.cpp
1255 ↗(On Diff #67399)

Agree, changed to use setBit

sanjoy accepted this revision.Aug 9 2016, 10:23 PM
sanjoy edited edge metadata.

lgtm

sanjoy accepted this revision.Aug 9 2016, 10:24 PM

lgtm

This revision was automatically updated to reflect the committed changes.
rogfer01 added a subscriber: rogfer01.EditedAug 12 2016, 4:29 AM

This change caused a noticeable regression in benchmark MultiSource/Benchmarks/TSVC/Symbolics-flt/Symbolics-flt from LNT.

You can check this in the daily LNT results from 11th August (scroll down until MultiSource/Benchmarks/TSVC/Symbolics-flt/Symbolics-flt)

http://llvm.org/perf/db_default/v4/nts/daily_report/2016/8/11?day_start=16

MultiSource/Benchmarks/TSVC/Symbolics-dbl/Symbolics-dbl is also affected.

Can you take a look at it?

Thank you!

This change caused a noticeable regression in benchmark MultiSource/Benchmarks/TSVC/Symbolics-flt/Symbolics-flt from LNT.

This also caused a number of major regressions on our internal benchmarking framework. I would like to see the change reverted while the public regression mentioned above is investigated. We can provide some analysis of what went wrong in our internal environment, but I'd prefer to avoid investing that effort if we can diagnose from public benchmarks.

I will look into the regressions on public benchmarks.

If you'd prefer reverting this change then you need also revert D18867 since that change relies on this.

The problem is in indvarsimplify, this patch results in redundant trunc/sext that should be eliminated by indvarsimplify but not, causing the loop in TSVC/s174 not vectorizable. I will submit a fix for review.

lihuang edited edge metadata.Aug 24 2016, 1:04 PM
lihuang added a subscriber: Farhana.
lihuang updated this revision to Diff 73080.Sep 30 2016, 10:06 AM
lihuang edited reviewers, added: apilipenko; removed: mbodart.
lihuang removed rL LLVM as the repository for this revision.

Rebase this patch to latest source.

As the performance problem has been fixed by r282650 (D24280), we can re-commit this patch.

lihuang reopened this revision.Sep 30 2016, 10:07 AM

Hi Sanjoy and Artur,

This patch is the same as before, can we re-commit it?

reames added a comment.Oct 1 2016, 4:13 PM

Recommit LGTM

This revision was automatically updated to reflect the committed changes.