This is an archive of the discontinued LLVM Phabricator instance.

[NFC][InlineCost] Factor cost modeling out of CallAnalyzer traversal.
ClosedPublic

Authored by mtrofin on Dec 19 2019, 4:26 PM.

Details

Summary

The goal is to simplify experimentation on the cost model. Today,
CallAnalyzer decides 2 things: legality, and benefit. The refactoring
keeps legality assessment in CallAnalyzer, and factors benefit
evaluation out, as an extension.

Event Timeline

mtrofin created this revision.Dec 19 2019, 4:26 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 19 2019, 4:26 PM
davidxl added inline comments.Dec 19 2019, 6:41 PM
llvm/lib/Analysis/InlineCost.cpp
161

Can you document each handler in source?

Also does it make more sense to provide a dummy empty body so that users are not forced to implement all of them?

640

InlineCostCallAnalyzer?

mtrofin updated this revision to Diff 234824.Dec 19 2019, 8:42 PM

virtuals have implementation; renamed derived class; made OnJumpTable return bool, like OnCaseCluster does.

The SROA handling code should also be abstracted away and let the derived class handling cost accumulation. In particular, the common code pattern like:

if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {

  if (I.isSimple()) {
    accumulateSROACost(CostIt, InlineConstants::InstrCost);
    return true;
  }

  disableSROA(CostIt);
}

Can be abtracted with interface CallAnalyzer::handleSROA(..), and the derived class implements this pattern.

mtrofin updated this revision to Diff 234990.Dec 20 2019, 4:46 PM
  • renamed to camelCase
  • factored the sroa costing out

The SROA handling code should also be abstracted away and let the derived class handling cost accumulation. In particular, the common code pattern like:

if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) {

  if (I.isSimple()) {
    accumulateSROACost(CostIt, InlineConstants::InstrCost);
    return true;
  }

  disableSROA(CostIt);
}

Can be abtracted with interface CallAnalyzer::handleSROA(..), and the derived class implements this pattern.

Done - that also pulls out the sroa-related costing stuff out, which I've missed originally.

davidxl added inline comments.Dec 20 2019, 8:11 PM
llvm/lib/Analysis/InlineCost.cpp
179

Document -- similarly for other APIs overrider may need to define.

180

document.

186

Should it be named 'onInitializeSROAArg' or something?

187

Document semantics of the API. Also should it be renamed 'onAggregateSROAUse'?

mtrofin updated this revision to Diff 235158.Dec 23 2019, 9:42 AM
mtrofin marked 4 inline comments as done.

Comments, some renames, and more clarity around the SROA APIs' arguments.

mtrofin marked 2 inline comments as done.Dec 23 2019, 9:43 AM
davidxl added inline comments.Dec 23 2019, 10:34 AM
llvm/lib/Analysis/InlineCost.cpp
164

Document what to return.

171

Called before the analysis of the callee body (with callsite contexts propagate) starts. It checks callsites specific information.

ALso document what to return.

173

Called when the analysis engine decides that SROA can not be done.

175

Called by the analysis when load elimination can not happen.

182

Make a note that 'Call' is a callsite in the callee body -- not to be confused with the callsite being analyzed.

197

onFinalizeSwitch

206

analyzeIndirectCall

mtrofin updated this revision to Diff 235173.Dec 23 2019, 11:56 AM

incorporated feedback

mtrofin marked 7 inline comments as done.Jan 6 2020, 8:36 AM

this looks good to me. Easwaran, do you have any comments on the refactoring?

The intention is to make the base CallAnalysis becomes a symbolic execution engine (virtual optimizations) what can be reused. The cost tracking is extracted into the derived class.

Thanks for refactoring LGTM.

eraman added inline comments.Jan 7 2020, 1:15 PM
llvm/lib/Analysis/InlineCost.cpp
129–131

This should go to InlineCostCallAnalyzer as it is not needed for legality check or symbolic evaluation.

136

Please leave an empty line before the doc comment to make this more readable (here and other places below)

676

Let's say you are using a different flavor of InlineCostCallAnalyzer (one which has different implemnetation of the virtual onXYZ methods), you should be instantiating an instance of that class here and call analyze here.

1519

Comment should go to callee (please check all places where you call onXYZ methods if the comment belong in the caller or callee)

1545

Why not move the entire block into a single function?

1673–1674

Comments should go into the callee. Also, it's better to merge onCaseCluster and onFinalizeSwitch into one function and just do

onFinalizeSwitch();
return false;

(Revisiting this - I think even onJumpTable should be folded into onFinalizeSwitch. From simplification/legality perspective, there is notthing left to do here after checking if the condition folds into a constant)

1767

onCommonInstructionSimplification is more meaningful.

1967–1968

The comments are not in-sync with the code. shouldStop could potentially use other ways to check if the analysis should stop - not just cost exceeds the threshold

2038–2039

Shouldn't this entire block be moved to InlineCostCallAnalyzer as this isn't performing symbolic evaluation or legality check?

mtrofin updated this revision to Diff 236714.Jan 7 2020, 4:09 PM
mtrofin marked 13 inline comments as done.

Incorporated feedback.

mtrofin added inline comments.Jan 7 2020, 4:09 PM
llvm/lib/Analysis/InlineCost.cpp
676

Maybe, but I'd prefer addressing that problem when the scenario arises, and avoid the added complexity meanwhile, wdyt?

1967–1968

True, and in this case, the code is kind of self-evident. I moved the comment to the shouldStop implementation.

2038–2039

Possibly, but all that prep work - getting a DominatorTree, LoopInfo, going over loops, making sure we ignore those that aren't executed - would be necessary if we want to account the number of loops somehow.

eraman added inline comments.Jan 8 2020, 1:41 PM
llvm/lib/Analysis/InlineCost.cpp
676

I still think this is better handled now, but if you think otherwise, please add a comment.

2038–2039

Well, all this prep work is for cost computation right? Again, since the goal is to keep only symbolic analysis + legality check here, why keep these here?

davidxl added inline comments.Jan 8 2020, 2:18 PM
llvm/lib/Analysis/InlineCost.cpp
2038–2039

This looks like cost computation specific and should probably be moved to the derived class. It can query the base class about deadblocks.

mtrofin updated this revision to Diff 236919.Jan 8 2020, 3:24 PM

Removed 'onLoops'

eraman added a comment.Jan 8 2020, 3:59 PM

LGTM

llvm/lib/Analysis/InlineCost.cpp
457

Please add a FIXME here saying we should be using the same derived class instance

mtrofin updated this revision to Diff 236936.Jan 8 2020, 5:07 PM
mtrofin marked 2 inline comments as done.

added fixmes

mtrofin marked 3 inline comments as done.Jan 8 2020, 5:09 PM
mtrofin added inline comments.
llvm/lib/Analysis/InlineCost.cpp
457

done, also marked InlineCostCallAnalyzer as final and referenced this fixme there, it'll be more visible should deriving InlineCostCallAnalyzer happen.

This revision was not accepted when it landed; it landed in state Needs Review.Jan 8 2020, 5:19 PM
This revision was automatically updated to reflect the committed changes.
mtrofin marked an inline comment as done.
mtrofin reopened this revision.Jan 9 2020, 11:21 PM
mtrofin updated this revision to Diff 237247.Jan 9 2020, 11:21 PM

fixed bugs

mtrofin updated this revision to Diff 237444.Jan 10 2020, 3:19 PM

fixes. Validated building a few binaries are identical before/after this change

davidxl accepted this revision.Jan 10 2020, 3:21 PM

lgtm

This revision is now accepted and ready to land.Jan 10 2020, 3:21 PM
This revision was automatically updated to reflect the committed changes.

LGTM

llvm/lib/Analysis/InlineCost.cpp
241

nit on naming: Perhaps use EnabledSROAAllocas ? Also, I feel the comment lines starting from We don't delete... is not required.

2226–2228

Looks like unintended change.

mtrofin marked an inline comment as done.Jan 10 2020, 4:30 PM
mtrofin added inline comments.
llvm/lib/Analysis/InlineCost.cpp
2226–2228

It's unrelated, but intended: clang-format kept indenting the original comments. I looked closer at what was happening, and it looks like the comments characterize the 'case' they used to be above, but clang-format wants to indent them as a case statement body. So I moved them as shown, to avoid future churn with clang-format.

mtrofin marked an inline comment as done.Jan 10 2020, 4:32 PM
mtrofin added inline comments.
llvm/lib/Analysis/InlineCost.cpp
241

Agreed, I'll send a followup to rename.