This is an archive of the discontinued LLVM Phabricator instance.

[SCEV] Compute affine range in another way to avoid bitwidth extending.
ClosedPublic

Authored by mzolotukhin on Feb 28 2017, 3:14 PM.

Details

Summary

This approach has two major advantages over the existing one:

  1. We don't need to extend bitwidth in our computations. Extending

bitwidth is a big issue for compile time as we often end up working with
APInts wider than 64bit, which is a slow case for APInt.

  1. When we zero extend a wrapped range, we lose some information (we

replace the range with [0, 1 << src bit width)). Thus, avoiding such
extensions better preserves information.

Correctness testing:
I ran 'ninja check' with assertions that the new implementation of
getRangeForAffineAR gives the same results as the old one (this
functionality is not present in this patch). There were several failures -
I inspected them manually and found out that they all are caused by
the fact that we're returning more accurate results now (see bullet (2)
above).
Without such assertions 'ninja check' works just fine, as well as
SPEC2006.

Compile time testing:
CTMark/Os:

  • mafft/pairlocalalign -16.98%
  • tramp3d-v4/tramp3d-v4 -12.72%
  • lencod/lencod -11.51%
  • Bullet/bullet -4.36%
  • ClamAV/clamscan -3.66%
  • 7zip/7zip-benchmark -3.19%
  • sqlite3/sqlite3 -2.95%
  • SPASS/SPASS -2.74%
  • Average -5.81%

Performance testing:
The changes are expected to be neutral for runtime performance. That
said, I plan to run some tests overnight to verify that.

Event Timeline

mzolotukhin created this revision.Feb 28 2017, 3:14 PM
mzolotukhin edited the summary of this revision. (Show Details)Feb 28 2017, 3:16 PM
atrick edited edge metadata.Feb 28 2017, 5:02 PM

I haven't fully reviewed the code, but I'm really glad you were able to express the range without extending its width. Thanks for doing this.

lib/Analysis/ScalarEvolution.cpp
4770

This is probably fine:

CheckBackDirection = StepSMin.isNegative();

As expected, runtime performance didn't change for SPECINT2006 (I tried -O3), but compile time improved across all the tests:

  • 464.h264ref -11.13%
  • 456.hmmer -7.72%
  • 401.bzip2 -7.47%
  • 445.gobmk -5.89%
  • 473.astar -4.50%
  • 462.libquantum -4.29%
  • 429.mcf -4.24%
  • 458.sjeng -3.38%
  • 400.perlbench -3.28%
  • 403.gcc -3.26%
sanjoy requested changes to this revision.Mar 3 2017, 7:18 PM

It was not clear to me that this is safe around certain kinds of overflow -- if the questions I raised inline are invalid, please add comments / asserts making them obviously invalid. :)

lib/Analysis/ScalarEvolution.cpp
4683

tripleUCompare is not too descriptive -- what is it actually doing? Rather, what property of A, B, C is it testing for?

4716

Is it okay for this to overflow?

4762

Do you need to pass in BackDirection here? Can't you get the same information by checking the sign of Step?

4765

Same question here about the multiplication overflowing.

4779

I'd s/CheckBackDirection/CheckBwdDirection/ for consistency.

4781

Is this correct if StepSMin (and thus also StepSMin.abs()) is INT_SMIN?

This revision now requires changes to proceed.Mar 3 2017, 7:18 PM
mzolotukhin edited edge metadata.
  • Address review remarks.
mzolotukhin marked 7 inline comments as done.Mar 6 2017, 11:36 PM

Hi,

Thanks for the initial review, please find the patch updated.

Michael

lib/Analysis/ScalarEvolution.cpp
4683

I'm using ConstantRange::contains instead. I'd really appreciate more eyes here to check if I'm not missing anything.

4716

Fixed.

4762

Fixed.

mzolotukhin updated this revision to Diff 90979.Mar 7 2017, 7:24 PM
mzolotukhin marked 3 inline comments as done.
  • Merge two similar functions together.
sanjoy requested changes to this revision.Mar 10 2017, 6:16 PM

Mostly minor stuff. Requesting another iteration mostly because I too want to look at it again with fresh eyes to see if I missed anything.

lib/Analysis/ScalarEvolution.cpp
4691

How about just folding all of these together and changing the comment to match?

If either Step or MaxBECount is 0 or the start range is maximally conservative to begin with ..

4696

I'd s/BackDirection/Descending/

Also, please add a justification on why this abs does the right thing of Step is INT_SMIN (or bail out in that case).

4702

Can we get the APInt::getMaxValue(StartRange.getBitWidth()) == MaxBECount * Step check here by changing ult to ule?

4715

I'd suggest not calling these *Min or *Max since they're not the minimum or maximum (signed or unsigned).

4717

Very minor stylistic thing (and I'll understand if you don't want to change it): I'd have written this as BackDirection ? (StartMin - Offset) : (StartMax + Offset)

4725

Again, these should not be called *Min or *Max.

This revision now requires changes to proceed.Mar 10 2017, 6:16 PM
mzolotukhin edited edge metadata.
  • Address review remarks.
mzolotukhin marked an inline comment as done.
  • Add a comment about INT_SMIN.
mzolotukhin marked 3 inline comments as done.Mar 11 2017, 8:40 PM

Requesting another iteration mostly because I too want to look at it again with fresh eyes to see if I missed anything.

Absolutely.

I updated the patch, please take a look when you are ready :)

Thanks,
Michael

lib/Analysis/ScalarEvolution.cpp
4691

I prefer to keep them separate for the following reason. In the first case we check if the start range doesn't change at all. I.e. we know for sure that final value is the same as the original one because either step is 0, or MaxBECount is 0. In the second case, in contrast, the value is changed, but we cannot predict a new range, because the original range is too conservative. I.e. the final range is also full range, in some sense it's a different full range compared to the start range. I hope this explanation makes sense :)

4696

I'd s/BackDirection/Descending/

I like Descending better too, thanks!

Also, please add a justification on why this abs does the right thing of Step is INT_SMIN

I tried to add a comment about it, but I'm not sure it's clear enough. But I'm pretty sure we're doing correct thing here due to wrap-around of APInt.

4702

I rechecked the formulas and I think the second one is not need at all.

If MaxBECount*Step == UINT_MAX, then we don't overflow. E.g. we can go from 0 to 255 with step=1 and MaxBECount=255 without a wrap.

4715

Thanks, fixed.

4717

Fixed.

sanjoy accepted this revision.Mar 16 2017, 1:48 PM

lgtm

Do you mind adding some targeted test cases for this, especially around cases where you think our behavior may have changed?

That's fine to do later in a later commit though.

This revision is now accepted and ready to land.Mar 16 2017, 1:48 PM
This revision was automatically updated to reflect the committed changes.
mzolotukhin marked 3 inline comments as done.