[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

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.