Open AndyAyersMS opened 7 months ago
Tagging subscribers to this area: @JulieLeeMSFT, @jakobbotsch See info in area-owners.md if you want to be subscribed.
Author: | AndyAyersMS |
---|---|
Assignees: | - |
Labels: | `area-CodeGen-coreclr`, `needs-area-label` |
Milestone: | - |
Another example, this one has two two-def CSEs.
The jit currently does both, but just doing CSE 01 is better (per perf score).
Second number in each node is best perf score. Double box is what the jit does now.
From a recent ASP.NET collection
This leads to a bunch of ideas / suggestions:
I have implemented the useless def pruning and it has some nice (but small) wins. Similar things could be had by doing a late round of forward sub to reconnect the trees at these useless def sites (possibly more cheaply).
Sample diff
Diffs are based on 113,707 contexts (48,175 MinOpts, 65,532 FullOpts).
MISSED contexts: base: 0 (0.00%), diff: 1 (0.00%)
Diff JIT options: JitRefineCSECandidates=1
But splitting seems too messy. It is not clear how to properly handle the exception set modelling and similar aspects. It seems preferable to just build the right candidate sets up front (in which case we would not need the useless def pruning).
If we decide to revise CSE finding, we'll also have to come to grips with:
For live-across call, there's the option of splitting a multi-use CSE into parts, too. For exception set handling, splitting instead of losing the CSE may also be a good idea.
For BB_NO_CSE_IN, we could perhaps run before and after RBO, and only do the costly(?) checking in the after. RBO should not in general change the candidate set (?) so the basic locate building (building up the equivalent VN sets) built by the before phase could in principle carry over to the later phase.
For that matter, VN itself could be building these sets, or we could have a mode where they are automagically maintained whenever a tree's VN is set to something. That might be too fragile, though.... there is no general way to verify a tree has the proper VN.
Played around with this a bit more... generally not having multi-def seems to be an improvement, but not always:
One example is in TryEnterReaderLockCore, here the CSE is a TLS access helper call, and initially the code splits into two paths both of which access TLS, and below the join are more TLS accesses. Current compiler treats all this as one big CSE with 2 defs and 13 uses, new analysis as 5 separate single-def 2 use CSEs. Profitability accepts the one big one but not the 5 smaller ones (4 of which have no def or use weight):
;; current jit (one big candidate)
CSE #02, {$380, $2 } defCnt=2 useCnt=13: [def=100.000000, use=0.037279, cost= 15, call]
:: N002 ( 15, 7) CSE #02 (def)[000331] H-C-G------ * CALL help byref CORINFO_HELP_GETSHARED_GCTHREADSTATIC_BASE_NOCTOR_OPTIMIZED $380
Considering CSE #02 {$380, $2 } [def=100.000000, use=0.037279, cost= 15, call]
CSE Expression :
N002 ( 15, 7) CSE #02 (def)[000331] H-C-G------ * CALL help byref CORINFO_HELP_GETSHARED_GCTHREADSTATIC_BASE_NOCTOR_OPTIMIZED $380
N001 ( 1, 1) [000330] ----------- arg0 in rcx \--* CNS_INT int 3 $44
Aggressive CSE Promotion (200.037279 >= 200.000000)
cseRefCnt=200.037279, aggressiveRefCnt=200.000000, moderateRefCnt=100.000000
defCnt=100.000000, useCnt=0.037279, cost=15, size=7, LiveAcrossCall
def_cost=1, use_cost=1, extra_no_cost=156, extra_yes_cost=0
CSE cost savings check (156.559180 >= 100.037279) passes
compared to
;; hypothetical jit (5 small candidates)
CSE #07, {$380, $2 } defCnt=1 useCnt=2: [def=100.000000, use=0.037279, cost= 15, call]
:: N002 ( 15, 7) CSE #07 (def)[000331] H-C-G------ * CALL help byref CORINFO_HELP_GETSHARED_GCTHREADSTATIC_BASE_NOCTOR_OPTIMIZED $380
CSE #02, {$380, $2 } defCnt=1 useCnt=2: [def=0.000000, use=0.000000, cost= 15, call]
:: N002 ( 15, 7) CSE #02 (def)[000484] H-C-G------ * CALL help byref CORINFO_HELP_GETSHARED_GCTHREADSTATIC_BASE_NOCTOR_OPTIMIZED $380
CSE #13, {$380, $2 } defCnt=1 useCnt=2: [def=0.000000, use=0.000000, cost= 15, call]
:: N002 ( 15, 7) CSE #13 (def)[000644] H-C-G------ * CALL help byref CORINFO_HELP_GETSHARED_GCTHREADSTATIC_BASE_NOCTOR_OPTIMIZED $380
CSE #18, {$380, $2 } defCnt=1 useCnt=2: [def=0.000000, use=0.000000, cost= 15, call]
:: N002 ( 15, 7) CSE #18 (def)[000912] H-C-G------ * CALL help byref CORINFO_HELP_GETSHARED_GCTHREADSTATIC_BASE_NOCTOR_OPTIMIZED $380
CSE #22, {$380, $2 } defCnt=1 useCnt=2: [def=0.000000, use=0.000000, cost= 15, call]
:: N002 ( 15, 7) CSE #22 (def)[000778] H-C-G------ * CALL help byref CORINFO_HELP_GETSHARED_GCTHREADSTATIC_BASE_NOCTOR_OPTIMIZED $380
Considering CSE #07 {$380, $2 } [def=100.000000, use=0.037279, cost= 15, call]
CSE Expression :
N002 ( 15, 7) CSE #07 (def)[000331] H-C-G------ * CALL help byref CORINFO_HELP_GETSHARED_GCTHREADSTATIC_BASE_NOCTOR_OPTIMIZED $380
N001 ( 1, 1) [000330] ----------- arg0 in rcx \--* CNS_INT int 3 $44
Aggressive CSE Promotion (200.037279 >= 200.000000)
cseRefCnt=200.037279, aggressiveRefCnt=200.000000, moderateRefCnt=100.000000
defCnt=100.000000, useCnt=0.037279, cost=15, size=7, LiveAcrossCall
def_cost=1, use_cost=1, extra_no_cost=24, extra_yes_cost=0
CSE cost savings check (24.559180 >= 100.037279) fails
(note the one big case makes it solely because of extra_no_cost, which is a code size bumper).
Another thing we should consider is to boost the CSE cost for trees with calls, right now they are considered fairly cheap, but if they're pure/hoistable/cse-able then perhaps we could give them costs that better reflect their true cycle impact.
Have been looking at CSE behavior and noticed some examples where multiple-def CSEs are a bit strange.
Here's one, where the two defs are in the gray blocks and the use is in the yellow. A closer look reveals that only one of the two defs can reach the use.
This really should just be a single-def CSE.
We get to this point because CSE candidate formation (for the most part) is just keyed on the liberal VN. If two trees in the method have the same liberal VN then they belong to the same CSE candidate set. We then do a forward dataflow using these CSE trees. The only way a CSE is killed is at a join.
We then revisit the candidate member trees, and if the CSE is available at that point then the tree is marked as a use; if not, it is marked as a def. So in the example above the candidate set has 3 trees, but the BB15 tree is available at BB31 so the latter is marked as a use. The BB02 tree does not reach any uses and is also considered a def.
There are at least two issues here -- one potential and one we see in the above case:
In the case above the CSE is a class handle, and the last problem potentially leads to a lower perf score than if no CSE was done, as there is an extra callee save used (to be fair it seems plausible this would happen even without the common temp, as the path from 15->31 is live across a call).
It's not clear how often we see the case where two CSE defs reach some CSE use, and the way the algorithm is structured it's not obvious how to figure this out. Here's one half-baked idea, perhaps worth measuring sometime.
In the above case this would lead to CSE#02 being its own use-less set, so it would drop out of CSE.
category:cq theme:cse skill-level:expert cost:medium impact:medium