[libraries-pgo] Assertion failed '(h->bbJumpKind == BBJ_COND) && (h->bbNext == loop.lpEntry)' during 'Clone loops'

[jakobbotsch]

Seen in recent testing on #68703 (but presumably not related to the changes there).

Pipeline run: https://dev.azure.com/dnceng/public/_build/results?buildId=1815405&view=results
Helix job name: net7.0-windows-Release-x64-CoreCLR_checked-fullpgo_random_edge-Windows.10.Amd64.Open
Work item: System.Linq.Parallel.Tests
Console log: https://helixre107v0xdeko0k025g8.blob.core.windows.net/dotnet-runtime-refs-pull-68703-merge-8b8ab2065a214c7bb1/System.Linq.Parallel.Tests/1/console.26995272.log?helixlogtype=result

cc @AndyAyersMS

[ghost]

Tagging subscribers to this area: @JulieLeeMSFT, @jakobbotsch
See info in area-owners.md if you want to be subscribed.

Issue Details

---

Seen in recent testing on #68703 (but presumably not related to the changes there).

Pipeline run: https://dev.azure.com/dnceng/public/_build/results?buildId=1815405&view=results
Helix job name: net7.0-windows-Release-x64-CoreCLR_checked-fullpgo_random_edge-Windows.10.Amd64.Open
Work item: System.Linq.Parallel.Tests
Console log: https://helixre107v0xdeko0k025g8.blob.core.windows.net/dotnet-runtime-refs-pull-68703-merge-8b8ab2065a214c7bb1/System.Linq.Parallel.Tests/1/console.26995272.log?helixlogtype=result

cc @AndyAyersMS

Author:	jakobbotsch
Assignees:	-
Labels:	area-CodeGen-coreclr
Milestone:	-

[jakobbotsch]

There's a whole bunch more of test failures in that run that I haven't had time to go through and file issues for yet.

[AndyAyersMS]

We have the following flow graph. The blocks in orange are recognized as an inner loop (despite BB03 having another back edge from BB09).

We clone this loop for the invariant type test in BB03, then rebuild dominators and renumber, ending up with

where the fast path loop now stretches from BB05 to BB10 with entry BB04. We find hoistable stuff in BB05 and go to create a preheader, but BB04 does not dominate BB05 (there is a path from BB03 -> BB12 -> BB19 -> BB05 that avoids BB04). Hence the assert.

Not sure what the right fix is just yet.

[AndyAyersMS]

Actually, the type test is not invariant.

The call in BB09 redefines the local V02 used in BB03 as the base of the indir. So, we need to address the fact that we're not seeing the entire loop body and this is leading us astray.

[AndyAyersMS]

Method source:

runtime/src/libraries/System.Linq.Expressions/src/System/Linq/Expressions/Compiler/LambdaCompiler.ControlFlow.cs

Lines 246 to 284 in 57bfe47

	private void AddReturnLabel(LambdaExpression lambda)
	{
	Expression expression = lambda.Body;
	while (true)
	{
	switch (expression.NodeType)
	{
	default:
	// Didn't find return label
	return;
	case ExpressionType.Label:
	// Found the label. We can directly return from this place
	// only if the label type is reference assignable to the lambda return type.
	LabelTarget label = ((LabelExpression)expression).Target;
	_labelInfo.Add(label, new LabelInfo(_ilg, label, TypeUtils.AreReferenceAssignable(lambda.ReturnType, label.Type)));
	return;
	case ExpressionType.Block:
	// Look in the last significant expression of a block
	var body = (BlockExpression)expression;
	// omit empty and debuginfo at the end of the block since they
	// are not going to emit any IL
	if (body.ExpressionCount == 0)
	{
	return;
	}
	for (int i = body.ExpressionCount - 1; i >= 0; i--)
	{
	expression = body.GetExpression(i);
	if (Significant(expression))
	{
	break;
	}
	}
	continue;
	}
	}
	}
	}

Most of this method is cold...

After GDV there is a type test in the loop, but the loop never iterates. Seems like we shouldn't bother cloning in such cases.

[jakobbotsch]

I also see a lot of assertion failures that look like

Assert failure(PID 14476 [0x0000388c], Thread: 16528 [0x4090]): Assertion failed 'fgDominate(head, entry)' in 'System.Text.Encoding:GetByteCount(System.String,int,int):int:this' during 'Hoist loop code' (IL size 109; hash 0x10278d31; Tier1)

    File: D:\a\_work\1\s\src\coreclr\jit\optimizer.cpp Line: 7451
    Image: D:\h\w\B4940A2B\p\dotnet.exe

in recent runs. Do you think it could be the same issue or should I open another one?

[AndyAyersMS]

What I'm describing above is actually the fgDominates assert. Maybe we should repurpose this issue for that and open a new one for the original.

[AndyAyersMS]

I think the issue is that optCanonicalizeLoop does not split out non-loop backedges from loop backedges. Before finding loops we have the following flow:

We find two loops:

• L00 from BB02 to BB14
• L01 from BB02 to BB11

Since the two share a top block, we canonicalize by creating a new top for L00, and we redirect the BB14 edge there. That leaves two back edges into L01/BB02, one of which comes from BB12 which is not part of L01. We need to do a second split here and redirect that edge into a new block as well, so that L01 only has the backedge from BB11.

[AndyAyersMS]

What I'm describing above is actually the fgDominates assert. Maybe we should repurpose this issue for that and open a new one for the original.

Opened a new issue for the fgDominates assert: #70802

[AndyAyersMS]

Ok, finally looking at the right repro. We have a pair of back to back loops:

and we decide both of them have invariant type tests and should be cloned:

Considering loop L00 to clone for optimizations.
Checking loop L00 for optimization candidates (type tests)
...TT considering [000193]
... right form, V02
Loop L00 has invariant type test [000193] on V02 ...  but loop does not iterate often enough.
...TT considering [001626]
...TT considering [001632]
...TT considering [000125]
...TT considering [000227]
... right form, V02
Loop L00 has invariant type test [000227] on V02 ...  but loop does not iterate often enough.
...TT considering [001661]
...TT considering [001667]
...TT considering [000155]
...TT considering [000159]
...TT considering [001832]
...TT considering [000095]
------------------------------------------------------------
Considering loop L01 to clone for optimizations.
Checking loop L01 for optimization candidates (type tests)
...TT considering [000193]
... right form, V02
Loop L01 has invariant type test [000193] on V02 ...  passed profile screening
...TT considering [001626]
...TT considering [001632]
...TT considering [000125]
------------------------------------------------------------
Considering loop L02 to clone for optimizations.
Checking loop L02 for optimization candidates (type tests)
...TT considering [000227]
... right form, V02
Loop L02 has invariant type test [000227] on V02 ...  passed profile screening
...TT considering [001661]
...TT considering [001667]
...TT considering [000155]
------------------------------------------------------------

Note we really should clone L00 instead, but somehow the profile data (which is random here) is inconsistent and we don't think the loop iterates).

At any rate, cloning both L01 and L02 should be legal, if not optimal.

We clone L01 and then blow up trying to clone L02.

[AndyAyersMS]

Here's the flow graph after cloning L01. BB129-BB130 are the cloning conditions (null check and class check, respectively), BB91 the top of the fast loop, BB119 the top of the slow loop.

The key thing here is that L02 with top BB100 still thinks BB99 is its head block. This is no longer the case.

[EgorBo]

Failed in #70941 as well