This is an archive of the discontinued LLVM Phabricator instance.

Fix PR25339: ARM Constant Island
ClosedPublic

Authored by weimingz on Feb 4 2016, 10:29 AM.

Details

Summary

Currently, the ARM Constant Island may not converge (or not converge quickly).
This patch let it move to the closest water after the user if it doesn't converge after 15 iterations.

This address https://llvm.org/bugs/show_bug.cgi?id=25339

Diff Detail

Repository
rL LLVM

Event Timeline

weimingz updated this revision to Diff 46926.Feb 4 2016, 10:29 AM
weimingz retitled this revision from to Fix PR25339: ARM Constant Island.
weimingz updated this object.
weimingz set the repository for this revision to rL LLVM.
weimingz added a subscriber: llvm-commits.
weimingz added a reviewer: srhines.

Hi Weiming,

I'd like to know how you got to the magic number of 15. So, showing a small program that doesn't converge, then showing that this change makes it at least stop and produce whatever result is acceptable.

Constant islands are a major pain to get right because some relocations are only handled later and merging two islands can grow the distance of a third beyond the range of some load far away. In the same way, *not* merging could cause the same effects.

Would be good to see the results of compiling large pieces of code (say, LNT, Chromium, Firefox) which have plenty of opportunities to get this wrong. Without tests, it's hard to see what kind of problem you're trying to avoid, here.

cheers,
--renato

lib/Target/ARM/ARMConstantIslandPass.cpp
463–464

Shouldn't this 15 be in a constant somewhere? Maybe a hidden command line options, which defaults to 15, but can be changed?

1336

s/lowerest/lowest/

1351

Update the comment to reflect the new flag

Hi Renato,

I'll post the test case shortly. Since it's based on proprietary code,
it needs to complete some internal review process.
So far, I can only give a brief description of the problematic code.
Please see https://llvm.org/bugs/show_bug.cgi?id=25339

The number 15 is half of the max threshold of 30.
I did a measurement of building SPEC and the highest iteration number I
see is 3.

Thanks,
Weiming

I'll post the test case shortly. Since it's based on proprietary code,
it needs to complete some internal review process.

I completely understand. No worries.

So far, I can only give a brief description of the problematic code.
Please see https://llvm.org/bugs/show_bug.cgi?id=25339

Ah, excellent! That bug was on my radar, and I'm glad someone is looking at it. When you submit a review based on a bug, it's good to put the bug number like "Addresses bug #NNNN", so we can grab the rest of the context.

The number 15 is half of the max threshold of 30.

Right. If the max is hard-coded, then maybe say max/2 in there?

It's also not clear to me why 15 is better than 30. If the algorithm fails to converge on both, than clearly either hard-coded numbers would be ok as long as the safe option is implemented. This patch seems to be doing both: forcing a convergence, even if a bad one (which would also work with 30 iterations, I think), and reducing the threshold to 15 (which doesn't make much sense per se).

I did a measurement of building SPEC and the highest iteration number I
see is 3.

This means that the application itself is problematic in that respect, so any number beyond 5 would be a good bet, with higher numbers better because they would only hit the worse cases.

What's the impact if you keep the original threshold?

cheers,
--renato

Hi Renato,

I uploaded the test case to bugzilla.
https://llvm.org/bugs/show_bug.cgi?id=25339

This patch doesn't reduce the threshold to 15. It tries to accelerate
the converge after 15th iteration by ignoring the "best growth".

Thanks,
Weiming

This patch doesn't reduce the threshold to 15. It tries to accelerate
the converge after 15th iteration by ignoring the "best growth".

Ok, so then we need the number 15 to be on the same place as the number 30. If both are magic constants, we need to make them into some kind of static const global or a hidden compiler flag.

cheers,
--renato

weimingz updated this revision to Diff 48731.Feb 22 2016, 2:22 PM
weimingz updated this object.

I uploaded another test case to https://llvm.org/bugs/show_bug.cgi?id=25339.
That test case exposes different issues with CP. In that case, we want to split BB to accelerate converge.

rengolin accepted this revision.Feb 23 2016, 6:05 AM
rengolin added a reviewer: rengolin.

Looks much better, thanks!

There's only the typo on the comment "lowerest" -> "lowest", but LGTM with that fix.

This revision is now accepted and ready to land.Feb 23 2016, 6:05 AM
weimingz updated this revision to Diff 48833.Feb 23 2016, 10:41 AM
weimingz edited edge metadata.
weimingz marked an inline comment as done.

fixed the typo and updated comments

Looks much better, thanks!

There's only the typo on the comment "lowerest" -> "lowest", but LGTM with that fix.

Hi Renato,

Thanks for reviewing. I will fix the comment and merge it.

weimingz closed this revision.Feb 23 2016, 10:43 AM
srhines edited edge metadata.Feb 23 2016, 11:18 AM

To be perfectly clear, this was submitted as r261665.

This comment was removed by weimingz.