JIT: fgReorderBlocks does nonsensical things

[AndyAyersMS]

I added some diagnostic output to fgReorderBlocks to try and better understand the logic.

One odd thing I noticed is that it will often rearrange zero-weight blocks, eg:

-----------------------------------------------------------------------------------------------------------------------------------------
BBnum BBid ref try hnd preds           weight   IBC  lp [IL range]     [jump]      [EH region]         [flags]
-----------------------------------------------------------------------------------------------------------------------------------------
BB01 [0000]  1                             1    100    [000..013)-> BB06 ( cond )                     i hascall gcsafe IBC 
BB03 [0004]  1       BB01                  1.00 100    [000..001)-> BB04 ( cond )                     i IBC 
BB05 [0006]  1       BB03                  0.70  70    [000..001)-> BB13 ( cond )                     i IBC 
BB15 [0015]  1       BB05                  0.70  70    [???..???)-> BB12 (always)                     internal IBC 
BB06 [0007]  1       BB01                  0.00   0    [000..001)-> BB08 ( cond )                     i IBC 
BB07 [0008]  1       BB06                  0.00   0    [000..001)-> BB13 ( cond )                     i IBC 
BB16 [0016]  1       BB07                  0.00   0    [???..???)-> BB12 (always)                     internal IBC 
BB08 [0009]  1       BB06                  0      0    [000..001)-> BB10 ( cond )                     i rare IBC 
BB09 [0010]  1       BB08                  0      0    [000..001)-> BB11 (always)                     i rare hascall gcsafe IBC 
BB10 [0011]  1       BB08                  0      0    [000..001)                                     i rare IBC 
BB11 [0012]  2       BB09,BB10             0      0    [???..???)-> BB13 ( cond )                     internal rare IBC 
BB12 [0001]  4       BB11,BB14,BB15,BB16   1           [013..024)        (return)                     i jmp hascall gcsafe 
BB04 [0005]  1       BB03                  0.30  30    [000..001)-> BB13 ( cond )                     i IBC 
BB14 [0014]  1       BB04                  0.30  30    [???..???)-> BB12 (always)                     internal IBC 
BB13 [0002]  4       BB04,BB05,BB07,BB11   1           [024..026)        (return)                     i 
-----------------------------------------------------------------------------------------------------------------------------------------

--- BB15 ...
prev BB05 jumps to BB13;  -- trying fgOptimizeBranch
--- BB06 ...
prev BB15 jumps to BB12;  -- trying fgOptimizeBranch
--- BB07 ...
prev BB06 jumps to BB08; fwd-jmp; prev-cond; [hotWeight 0.5]  -- trying to rearrange
 considering option #1 -- relocate BB07 ... BB? later
 reached dest
 option 1: would move BB07 through BB16 and connect dest
Decided to reverse conditional branch at block BB06 branch to BB08 because of IBC profile data
fgFindInsertPoint(regionIndex=0, putInTryRegion=true, startBlk=BB01, endBlk=BB00, nearBlk=BB11, jumpBlk=BB16, runRarely=false)
Relocated uncommon blocks (BB07 .. BB16) by reversing conditional jump at BB06
Relocated blocks [BB07..BB16] inserted after BB12

The proximate cause for this is that it is adding/subtracting absolute values to block weights, which is nonsensical; for instance the decision above comes from this bit of code, which takes a zero weight block and deduces a hotWeight of 0.5:

runtime/src/coreclr/jit/fgopt.cpp

Lines 4499 to 4505 in f2f4f50

	BasicBlock::weight_t weightDest =
	bDest->isMaxBBWeight() ? bDest->bbWeight : (bDest->bbWeight + 1) / 2;
	BasicBlock::weight_t weightPrev =
	bPrev->isMaxBBWeight() ? bPrev->bbWeight : (bPrev->bbWeight + 2) / 3;
	// select the lower of weightDest and weightPrev
	profHotWeight = (weightDest < weightPrev) ? weightDest : weightPrev;

There are several other examples of this sort of logic in this method.

After all is done we can still see cases where the hot blocks in the method are not compact, eg in the example above we end up with:

*************** Finishing PHASE Optimize layout
Trees after Optimize layout

-----------------------------------------------------------------------------------------------------------------------------------------
BBnum BBid ref try hnd preds           weight   IBC  lp [IL range]     [jump]      [EH region]         [flags]
-----------------------------------------------------------------------------------------------------------------------------------------
BB01 [0000]  1                             1    100    [000..013)-> BB06 ( cond )                     i hascall gcsafe IBC 
BB03 [0004]  1       BB01                  1.00 100    [000..001)-> BB04 ( cond )                     i IBC 
BB05 [0006]  1       BB03                  0.70  70    [000..001)-> BB13 ( cond )                     i IBC 
BB15 [0015]  1       BB05                  0.70  70    [???..???)-> BB12 (always)                     internal IBC 
BB06 [0007]  1       BB01                  0.00   0    [000..001)-> BB07 ( cond )                     i IBC 
BB08 [0009]  1       BB06                  0      0    [000..001)-> BB10 ( cond )                     i rare IBC 
BB09 [0010]  1       BB08                  0      0    [000..001)-> BB11 (always)                     i rare hascall gcsafe IBC 
BB10 [0011]  1       BB08                  0      0    [000..001)                                     i rare IBC 
BB11 [0012]  2       BB09,BB10             0      0    [???..???)-> BB13 ( cond )                     internal rare IBC 
BB12 [0001]  4       BB04,BB11,BB15,BB16   1           [013..024)        (return)                     i jmp hascall gcsafe 
BB07 [0008]  1       BB06                  0.00   0    [000..001)-> BB13 ( cond )                     i IBC 
BB16 [0016]  1       BB07                  0.00   0    [???..???)-> BB12 (always)                     internal IBC 
BB04 [0005]  1       BB03                  0.30  30    [000..001)-> BB12 ( cond )                     i IBC 
BB13 [0002]  4       BB04,BB05,BB07,BB11   1           [024..026)        (return)                     i 
-----------------------------------------------------------------------------------------------------------------------------------------

I would suggest this entire method be rewritten not to try and solve block ordering as an incremental problem, but instead consider starting with a decent global layout (likely based on a profile-greedy reverse post order) and then trying to incrementally improve.

category:cq
theme:block-layout

[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.