This is an archive of the discontinued LLVM Phabricator instance.

[LSR] Drop LSR solution if it is less profitable than baseline
ClosedPublic

Authored by eopXD on May 19 2022, 11:34 PM.

Details

Summary

The LSR may suggest less profitable transformation to the loop. This
patch adds check to prevent LSR from generating worse code than what
we already have.

Since LSR affects nearly all targets, the patch is guarded by the
option 'lsr-drop-solution' and default as disable for now.

The next step should be extending an TTI interface to allow target(s)
to enable this enhancememnt.

Debug log is added to remind user of such choice to skip the LSR
solution.

Diff Detail

Event Timeline

eopXD created this revision.May 19 2022, 11:34 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 19 2022, 11:34 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
eopXD requested review of this revision.May 19 2022, 11:34 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 19 2022, 11:34 PM
eopXD added a reviewer: Restricted Project.May 19 2022, 11:35 PM

Is it feasible to add a test case?

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
3393

How can the baseline immediately become the loser?

3394

Since SCEV subexpressions can be reused by multiple instructions, doesn't this mean that this is overestimating the baseline cost?

5182

Instead of the const cast, would it be possible to make Cost::isLess accept a const object?

5183

Starting with newline?

eopXD added inline comments.May 24 2022, 7:43 PM
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
3393

I have encounter cases that the BaselineCost is updated to loser when compiling spec2k6 benchmarks. This if-statement is used for us to prevent assertion errors as RateFormula assumes the cost to not be a loser when called.

I have a patch (D125670) that is pretty simple to free us from using this if-statement? I think its pretty simple and we can land it first?

eopXD added a comment.May 24 2022, 8:08 PM

@Meinersbur Thank you for the review. I'll update when pre-commit patches (D125670 and D126350) land.

llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
3394

Yes you are right, we should prevent repeating RateFormula hen multiple IVStrideUse matches the same LU. Let me update my code.

5182

Created D126350.

eopXD marked an inline comment as not done.May 24 2022, 8:09 PM
eopXD updated this revision to Diff 463625.Sep 28 2022, 11:02 AM

Rebase to latest main.

Don't include baseline cost when SCEV is not used inside the loop. (isUseFullyOutsideLoop(L) == false)

eopXD updated this revision to Diff 463636.Sep 28 2022, 11:37 AM
eopXD marked 4 inline comments as done.

Address review comments.

eopXD added inline comments.Sep 28 2022, 11:37 AM
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
3393

D125670 landed. Marking this thread as complete.

3394

Created DenseSet<int> VisitedLSRUse to take account for SCEV that is already calculated.

5182

D126350 landed, marking this thread as complete.

5183

Removed leading newline.

eopXD updated this revision to Diff 463651.Sep 28 2022, 12:36 PM

Add test case.

eopXD updated this revision to Diff 463801.Sep 29 2022, 2:06 AM

Update test case for debug log.

eopXD updated this revision to Diff 463880.Sep 29 2022, 6:53 AM

Change:

  • Drop solution when baseline solution is better
  • Remove check for isLoser before calling RateFormula
  • Minor adjustment to debug log
eopXD updated this revision to Diff 463913.Sep 29 2022, 8:14 AM

Rebase to latest main.

eopXD updated this revision to Diff 463918.Sep 29 2022, 8:39 AM

Use option to block this addition for now.

eopXD added a comment.Oct 6 2022, 1:16 AM

Gentle ping, thank you :)

craig.topper added inline comments.Oct 25 2022, 9:17 PM
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
195

spell "solution" here.

craig.topper added inline comments.Oct 25 2022, 9:18 PM
llvm/lib/Transforms/Scalar/LoopStrengthReduce.cpp
3304

LUIdx is declared as size_t. Does this need to be DenseSet<size_t>?

eopXD updated this revision to Diff 470705.Oct 25 2022, 9:48 PM

Address comments.

eopXD added a comment.Oct 25 2022, 9:50 PM

Also separated debug message test case from the code gen test case.

eopXD marked 2 inline comments as done.Oct 25 2022, 9:51 PM
eopXD updated this revision to Diff 470709.Oct 25 2022, 10:21 PM

Add missing end-line in debug message.

Meinersbur accepted this revision.Oct 26 2022, 8:38 AM

LGTM, and sorry for the delay.

Could you add a description to the commit message?

This revision is now accepted and ready to land.Oct 26 2022, 8:38 AM
eopXD updated this revision to Diff 471082.Oct 27 2022, 2:11 AM

Rebase to latest main.

eopXD edited the summary of this revision. (Show Details)Oct 27 2022, 2:18 AM