This is an archive of the discontinued LLVM Phabricator instance.

[SimplifyCFG] Accumulate cost against budget
AbandonedPublic

Authored by samparker on Aug 21 2020, 6:07 AM.

Details

Summary

As highlighted in D82438, the speculation cost isn't accumulated in SpeculativelyExecuteBB. So now include the selects, the speculated instruction and any constant expressions against the set threshold.

Diff Detail

Event Timeline

samparker created this revision.Aug 21 2020, 6:07 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 21 2020, 6:07 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
samparker requested review of this revision.Aug 21 2020, 6:07 AM
samparker edited the summary of this revision. (Show Details)Aug 21 2020, 6:10 AM
lebedev.ri added inline comments.Aug 21 2020, 6:23 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2099–2104

Please add a new cl::opt for that.
I believe, the threshold should be the branch misprediction cost,
i.e. if it takes less cost (latency) to execute the branch
then to wrongly predict that it won't be executed,
but then rewind and execute it anyways, we should just execute it.

So i'd go with 20.

samparker added inline comments.Aug 21 2020, 6:34 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2099–2104

Most of the cost modelling framework actually tries to assume that branches are always predicated though, and I don't understand why making arbitrary decisions about machine details would be a good idea here. Plus, it's also completely irrelevant to code size... It would seem to be better to query the latency / size of the branch, but I highly doubt that would produce results that anyone would want...

lebedev.ri added inline comments.Aug 21 2020, 6:37 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2179

Ah, so this transform basically never fires then,

2183

I'm not sure what is going on here.

lebedev.ri requested changes to this revision.Aug 21 2020, 6:41 AM
lebedev.ri added inline comments.
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2099–2104

I'll rephrase: given that the cost modelling logic changed,
the remaining value of PHINodeFoldingThreshold is completely wrong.

This revision now requires changes to proceed.Aug 21 2020, 6:41 AM
samparker added inline comments.Aug 21 2020, 6:59 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2099–2104

Okay... so I guess we need to start at: What is the purpose of this code? I think it's trying to convert any number of phis and speculate, at most, a single instruction (and maybe try to figure out something with constexprs). If PHINodeFoldingThreshold is supposed to represent the cost of a cmp + sel, this doesn't feel completely broken to me but the threshold could just be PHINodeFoldingThreshold * NumPHIs?

lebedev.ri added inline comments.Aug 21 2020, 7:04 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2099–2104

I have no idea, it's you who is changing/fixing this,
you should know how it works, so you tell me :)

I'm just saying that since the entire cost-modelling logic
changed from "let's just ensure that every single instruction
is below some threshold, and ignore total cost"
to "let's count the total cost", it is pretty obvious
that using the old threshold as-is makes no sense.

samparker added inline comments.Aug 21 2020, 7:51 AM
llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2099–2104

Yeah, so I think multiplying by the number of phis should bring us back inline with what we were doing before.

samparker updated this revision to Diff 287331.Aug 24 2020, 3:31 AM

Rebased after reorganising the two parts of code that evaluate phis. The budget now allows a basic cost for each phi within the block, plus a basic cost for the one instruction that we may speculate.

lebedev.ri requested changes to this revision.Sep 10 2020, 12:46 AM

Please do address my review comments.

This revision now requires changes to proceed.Sep 10 2020, 12:46 AM
lebedev.ri resigned from this revision.Jan 12 2023, 4:46 PM

This review seems to be stuck/dead, consider abandoning if no longer relevant.

This revision now requires review to proceed.Jan 12 2023, 4:46 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 12 2023, 4:46 PM
Herald added a subscriber: StephenFan. · View Herald Transcript
samparker abandoned this revision.Jan 12 2023, 9:04 PM