Revisit code that updates loops before block removal

[kunalspathak]

While working on #68803 to fix #68756, we encountered several issues about how we track and update loop tables around block that we will remove. We should revisit the logic in optUpdateLoopsBeforeRemoveBlock().

1. After we renumber blocks, we add new blocks on the way (specifically during loop hoisting, we add preheaders). The lpContains() method relies on bbNum to determine if something is present in loop or not. Below is the code that is used to determine if a block is present in loop or not, but newer added blocks might have higher bbNum and can falsely claim that the block is not in the loop.
   

   runtime/src/coreclr/jit/optimizer.cpp

   Lines 515 to 518 in 4cd4cff

   	if (loop.lpContains(auxBlock))
   	{
   	continue;
   	}

2. If there was a preheader which had invariants hoisted, but later those invariants were eliminated by assertion prop or some other optimization, we would be left with empty preheader which want to eliminate. We invoke optUpdateLoopsBeforeRemoveBlock() and decide if the loop should also be removed or not.
   

   runtime/src/coreclr/jit/optimizer.cpp

   Lines 466 to 467 in 4cd4cff

   	// If `block` flows to the loop entry then the whole loop will become unreachable if it is the
   	// only non-loop predecessor.

Later, we also iterate through all the blocks, one of them being the preheader that we want to eliminate. We think that it is not part of a loop (because of reason mentioned above) but then see that auxBlock->bbJumpDest == loop.lpEntry and reset the flag saying we do not have to remove the loop. Here, we assume that there was a predecessor outside the loop, but never verify if auxBlock == block.

runtime/src/coreclr/jit/optimizer.cpp

Lines 509 to 512 in 4cd4cff

	// Check if the entry has other predecessors outside the loop.
	// TODO: Replace this when predecessors are available.
	for (BasicBlock* const auxBlock : Blocks())

3. If we decide to remove the loop or not, we fail to check for certain scenarios if loop.lpHead == block and if yes, we should update the loop.lpHead to point to the predecessor of block we are trying to remove.
4. Today, we do update loopHead in certain cases, but bbPrev might not be the right block we should set, but should be a predecesssor if possible. If we just add assert(block->bbPrev->KindIs(BBJ_NONE, BBJ_ALWAYS)), we would see that BBJ_THROW or BBJ_RETURN blocks are getting set as lpHead of a loop. This portion needs to be revisited as well.
   

   runtime/src/coreclr/jit/optimizer.cpp

   Lines 565 to 570 in 4cd4cff

   	else if (loop.lpHead == block)
   	{
   	reportBefore();
   	/* The loop has a new head - Just update the loop table */
   	loop.lpHead = block->bbPrev;
   	}

category:implementation
theme:loop-opt
skill-level:expert
cost:medium
impact:medium

[dotnet-issue-labeler]

I couldn't figure out the best area label to add to this issue. If you have write-permissions please help me learn by adding exactly one area label.

[kunalspathak]

@dotnet/jit-contrib , @BruceForstall

[ghost]

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

Issue Details

---

While working on #68803 to fix #68756, we encountered several issues about how we track and update loop tables around block that we will remove. We should revisit the logic in optUpdateLoopsBeforeRemoveBlock().

1. After we renumber blocks, we add new blocks on the way (specifically during loop hoisting, we add preheaders). The lpContains() method relies on bbNum to determine if something is present in loop or not. Below is the code that is used to determine if a block is present in loop or not, but newer added blocks might have higher bbNum and can falsely claim that the block is not in the loop.
   

   runtime/src/coreclr/jit/optimizer.cpp

   Lines 515 to 518 in 4cd4cff

   	if (loop.lpContains(auxBlock))
   	{
   	continue;
   	}

2. If there was a preheader which had invariants hoisted, but later those invariants were eliminated by assertion prop or some other optimization, we would be left with empty preheader which want to eliminate. We invoke optUpdateLoopsBeforeRemoveBlock() and decide if the loop should also be removed or not.
   

   runtime/src/coreclr/jit/optimizer.cpp

   Lines 466 to 467 in 4cd4cff

   	// If `block` flows to the loop entry then the whole loop will become unreachable if it is the
   	// only non-loop predecessor.

Later, we also iterate through all the blocks, one of them being the preheader that we want to eliminate. We think that it is not part of a loop (because of reason mentioned above) but then see that auxBlock->bbJumpDest == loop.lpEntry and reset the flag saying we do not have to remove the loop. Here, we assume that there was a predecessor outside the loop, but never verify if auxBlock == block.

runtime/src/coreclr/jit/optimizer.cpp

Lines 509 to 512 in 4cd4cff

	// Check if the entry has other predecessors outside the loop.
	// TODO: Replace this when predecessors are available.
	for (BasicBlock* const auxBlock : Blocks())

3. If we decide to remove the loop or not, we fail to check for certain scenarios if loop.lpHead == block and if yes, we should update the loop.lpHead to point to the predecessor of block we are trying to remove.
4. Today, we do update loopHead in certain cases, but bbPrev might not be the right block we should set, but should be a predecesssor if possible. If we just add assert(block->bbPrev->KindIs(BBJ_NONE, BBJ_ALWAYS)), we would see that BBJ_THROW or BBJ_RETURN blocks are getting set as lpHead of a loop. This portion needs to be revisited as well.
   

   runtime/src/coreclr/jit/optimizer.cpp

   Lines 565 to 570 in 4cd4cff

   	else if (loop.lpHead == block)
   	{
   	reportBefore();
   	/* The loop has a new head - Just update the loop table */
   	loop.lpHead = block->bbPrev;
   	}

Author:	kunalspathak
Assignees:	-
Labels:	area-CodeGen-coreclr, untriaged
Milestone:	-

[BruceForstall]

I think we should enable the code that always creates loop pre-headers when doing loop recognition (you could consider it part of loop canonicalization), and prevents removing empty pre-headers through optimization, finally letting them be removed late in compilation if they are empty. This would mean there's no need to on-demand create them, which invalidates bbNum sequential ordering and thus dominators.

[kunalspathak]

Thanks @BruceForstall. Whenever you get a chance, can you publish a draft PR of whatever changes you have so far for "always create loop pre-headers"? I can iterate on top of it to solve this problem.

[jakobbotsch]

This code no longer exists