Repository navigation
JIT: poor CQ for list enumeration constructs #9304
Description
From some discussion over in dotnet/csharplang#1085. Both the for and foreach cases have suboptimal CQ.
In the for case there is a redundant branch in the inner loop.
In the foreach case the enumerator's MoveNext is not inlined. If we force this and MoveNextRare inline then the jit is not able to optimize away the version check overhead in the inner loop.
Without the inlines the foreach is rougly 2.9x slower than the for; with the inlines this drops to 1.3x or so.
static int SumFor(List<int> l)
{
int result = 0;
for (int i = 0; i < l.Count; i++)
{
result += l[i];
}
return result;
}
static int SumForeach(List<int> l)
{
int result = 0;
foreach (int i in l)
{
result += i;
}
return result;
}category:cq
theme:basic-cq
skill-level:expert
cost:medium
impact:large
Activity
AndyAyersMS commentedon Nov 21, 2017
For
SumFor:IG03 is a critical block (fork/join). The join limits the jit's ability to reason about what happens in this block.
When reaching IG03 from IG02: r8d > 0, edx = 0. So edx < r8d. So the branch to IG06 is not taken.
When reaching IG03 from IG04: edx < r8d. So the branch to IG06 is not taken.
It might be simpler for the jit to reason about IG03 if it simply cloned it to push the join down to IG04.
IG03's branch makes IG04 "conditionally executed" in the loop. So the jit won't consider hoisting invariants like "mov r9, gword ptr [rcx+8]".
benaadams commentedon Nov 21, 2017
There would be more value in inlining
MoveNext; iflocalList._sizecould be compared tolocalList._items.Lengthto prove the loop would never go out of bounds (and for that check to then be hoisted)However I think the range check elimination currently only works evaluating to
.Lengthnot to a value tested to be<= .Lengthe.g._sizedotnet/coreclr#14030 (comment)AndyAyersMS commentedon Nov 21, 2017
For
SumForeach:IG08 is a also a critical block (testing the result of MoveNext):
When reached from IG07
r11dis 0 and so the jump is not taken.When reached from IG05,
r11dis 1, so the jump is always taken.By cloning this block we can streamline both branches.
The jit already realizes the compare and branch at the top of IG05 and IG06 has known outcome but doesn't act on it for some reason (perhaps because we're in SSA and don't want to mess with control flow?):
note the two operands have the same value numbers.
Fixing all that would leave us with an inner loop something like:
where we then might be able to host some of the loads off of
rdxand we'd have code that was close to theforversion.jakobbotsch commentedon Apr 17, 2024
Codegen today:
Looks much better today, but there still seems to be a redundant compare in
SumForand some quite suboptimal block layout inSumForeach(might be an interesting case to look at for block layout, cc @amanasifkhalid as well).We also seemingly don't manage to widen the IV for the foreach version. I opened #101176 for this.
amanasifkhalid commentedon May 17, 2024
With
DOTNET_JitDoReversePostOrderLayout=1,SumForis unchanged, andSumForeachis marginally better:Looking at the JIT dump, this looks like another case of the loop shape issue mentioned in #102343:
amanasifkhalid commentedon May 21, 2024
The loop rotation issue I noted above is fixed by #102343. Here's the block layout of
SumForeachusing the old layout implementation:With the new implementation, here's the initial RPO layout from above:
Then after we fix up the backward jumps, we end up with this layout:
So we're back to square one. We can't use
fgOptimizeBranchToEmptyUnconditionalto get rid ofBB06because it isn't empty. However, after setting up the RPO-based layout, there is an opportunity to compactBB06andBB03, and then move the loop head to the top of the loop as usual. This would allowBB04to fall through upon loop exit. That might seem like an odd transformation to make during layout instead of infgUpdateFlowGraph, but it does unlock some branch removal opportunities, and we have TP to spare. If I add a pass to compact blocks after getting the RPO-based layout, here's how the new final layout looks:And final codegen:
I think this warrants a follow-up to #102461.
While unrelated to this issue, we don't handle the
BBJ_CONDto emptyBBJ_ALWAYScase withfgOptimizeBranchToEmptyUnconditionaljust yet, due to the old block layout's dependence on implicit fallthrough from conditional blocks into their false targets. Once #102343 is merged, I think we should pursue that infgUpdateFlowGraph.JIT: Compact blocks in fgMoveBackwardJumpsToSuccessors (#102512)
JIT: Compact blocks in fgMoveBackwardJumpsToSuccessors (dotnet#102512)
JIT: Compact blocks in fgMoveBackwardJumpsToSuccessors (dotnet#102512)
AndyAyersMS commentedon Jul 3, 2025
@amanasifkhalid perhaps this one is worth revisiting?
amanasifkhalid commentedon Jul 3, 2025
Sure. The loop bodies are correctly rotated in the OSR variants.
SumFor:SumForeach:Notice that the loop weights were flattened at some point before layout. Looking at the JIT dump, we lose some edge likelihood fidelity during tail duplication. I'll take a closer look at this.
With tiering disabled, our block weight heuristics are good enough to keep the loops rotated correctly.
SumFor:SumForeach:In both scenarios, the block layout looks ideal. I still see the redundant compares in
SumFor:amanasifkhalid commentedon Jul 3, 2025
Before flow opts, we have this:
First, we clone the condition in
BB12intoBB15, and then compactBB12intoBB20. Then, we fold the conditions inBB12andBB20, such thatBB12jumps toBB03(which is also compacted withBB04) andBB20always exits the loop. This folding gets rid of the backedge likelihoods, leavingBB14to control the loop's iteration. So we have the following:These transformations have reduced the loop iteration likelihood from >99% to about 81%, hence why profile repair flattens the loop weights. I tried pattern-matching this case during flow opts to adjust the likelihoods as needed, but it's not easy to do this precisely without building dominators.
Since this transformation happens before loop opts, I think we can consider PGO-derived loop weights to be pretty trustworthy. I'm tempted to introduce a synthesis phase before loop opts to set loop continuation likelihoods to maintain the loop's cyclic probability. For the above case, we'd see that
BB14 -> BB15will drain the loop of its weight when profile repair runs, and increase the edge's likelihood accordingly. @AndyAyersMS how inadvisable does this sound?AndyAyersMS commentedon Jul 3, 2025
I want to make sure I understand where things go wrong.
I think the root problem here is that when we duplicate BB12 into BB15, we assume that the edge likelihood ratios remain the same, but in this case the ratios are correlated to the predecessor, and so when we simplify the original BB12 (now BB2) to always return, we arguably should go adjust the likelihoods of BB15 to be more likely to stay in the loop.
One route to a fix for this is to do limited path profiling for "critical blocks" like BB12 that have multiple predecessors and multiple successors, so we try and track the per-predecessor likelihoods. In particular the 2,2 case will arise a lot because of the lowering of
forloops and similar. The downside of this is more complex profiling, and extra burden representing and maintaining these different views of the edge likelihoods.Another is to try and remember that when we duplicate a block like these the two sets of edges are linked, and so if we simplify one set we need to adjust the other. I suspect it's unworkable in general, though perhaps if the duplication / simplification happen close together in time it might work out.
Your idea of preserving loop iteration counts also seems reasonable (at least in this case) though if there are many back edges / exit blocks it might be tricky to figure out how to fix things up.
Also note loop iteration counts themselves are not always invariants. For loop inversion it is tricky. A loop that zero-trips 99 times and iterates 100x the other time will show a roughly 50/50 likelihood in the critical block, but once inversion splits that block the loop avoidance block should have a 99/1 bias to avoid entering the loop and the in-loop block a 1/99 bias to remain in the loop.
amanasifkhalid commentedon Jul 3, 2025
When we tail-duplicate from some block
Yinto blockX, and then successfully foldX, we try to foldYas well, so tracking both sets of conditions can be done pretty locally. For the above example, are you suggesting that after we fold both condition copies to jump to different targets, we backtrack toBB14and adjust its successor likelihoods? My concern with this approach is we don't have the tools during flow opts to easily determine if the paths out ofBB14are independent.AndyAyersMS commentedon Jul 3, 2025
Ah, ok. I think what you're saying is that there is an intermediate state something like this, after the initial duplication and merging.
where the red and blue edges are the linked pairs (copies of 12's edges). Now if we are able to simplify the condition at 20+12 so that it always exits to 5, we have a contradiction, since removing the red edge out of 20+12 pushes too much profile into 5.
And the only viable repair is to reduce the profile flowing into 20+12, which means non-locally finding some dominator of 20+12 and tweaking the likelihoods there, since no matter how we adjust the paired edge on 15 there is no way to fix things to make them consistent.
What this is telling us was that the incoming profile must already have represented other executions of this code (say all this came from inlining) and once we specialize it to our context it does not hold together.
amanasifkhalid commentedon Jul 3, 2025
Right, in this case
BB14came fromSystem.Collections.Generic.List`1+Enumerator[int]:MoveNext()being inlined. This particular run came from callingSumForeachwith a List of size 10000; because of OSR, the loop looks like it never exits, so we cap and blend the loop edge likelihoods, thus giving us the initial cyclic probability of ~168. It's a shame that this eventually gets diluted down to ~5, though I suppose there isn't an easy way to cut through the noise of inlinee profiles.