Add missing edge in block splitter #7680

a7ehuo · 2025-03-06T13:56:43Z

There is a case where before block splitter, the merge block is the original fall-through block of the split block and it is also the split block's branch destination. In this case, there is only one edge from the split block to the merge block.

--- Before block splitter ---
BBStart <block_1>  (splitPred)
   ificmpeq ------> block_2

BBStart <block_2>  (mergeNode)

As part of the block splitter transformation, it removes the edge from the split block to its original branch destination. It reverses the split block's branch destination to its original fall-through block. In this case the new branch destination is the same as the original branch destination, but the edge between them is now missing.

We need to create the edge if it doesn't exist.

--- After block splitter  ---
BBStart <block_1>  (splitPred)
   ificmpne -----> block_2     // branch reversed

BBStart <block_3> (cloneStart)

BBStart <block_4> (cloneEnd)

BBStart <block_2> (mergeNode)
-----------------------------

Fixes: eclipse-openj9/openj9#21030

a7ehuo · 2025-03-06T14:02:04Z

@vijaysun-omr May I ask you to review this change? Thank you!

A more detailed description on this block splitter problem can be found in eclipse-openj9/openj9#21030 (comment).

@hzongaro fyi

vijaysun-omr · 2025-03-06T14:35:45Z

Just so I understand this better, if splitPred (block 1) in your example has nothing in between it and block 2 before block splitter was run, is it correct to have blocks 3 and 4 appear in between blocks 1 and 2 if we take the fall through path out of block 1 after block splitter has run ?

a7ehuo · 2025-03-06T15:28:13Z

Here is what happens inside TR_BlockSplitter::splitBlock including how the cloned blocks, block_3 and block_4, are inserted.
block_1: pred or splitPred
block_2: candidate
block_3: cloneStart
block_4: cloneEnd

(1)
After block_3 and block_4 are cloned, the edge block_1-->block_3 (pred-->cloneStart) is added in CFG, and the branch destination edge block_1-->block_2 (pred-->candidate) is removed in CFG, but the block_1's exit tree top is still linked to block_2's entry tree top.

omr/compiler/optimizer/LocalOpts.cpp

Lines 6610 to 6611 in 2799857

    
           cfg->addEdge(pred, cloneStart); 
        
           cfg->removeEdge(pred, candidate);

BBStart <block_1>  (pred or splitPred)
   ificmpeq ------> block_2
      ...
BBEnd </block_1> =====

BBStart <block_2>  (mergeNode)
BBEnd </block_2> =====

(2)
block_4 (cloneEnd) is inserted before block_2. At 6630, pred->getExit()->getNextTreeTop() is the entry of block_2. At 6631, block_3 (cloneStart) is inserted after block_1.

omr/compiler/optimizer/LocalOpts.cpp

Lines 6630 to 6631 in 2799857

    
           cloneEnd->getExit()->join(pred->getExit()->getNextTreeTop()); 
        
           pred->getExit()->join(cloneStart->getEntry());

BBStart <block_1>  (pred or splitPred)
   ificmpeq ------> block_2
      ...
BBEnd </block_1> =====

BBStart <block_3>  (cloneStart)
BBEnd </block_3> =====

BBStart <block_4>  (cloneEnd)
BBEnd </block_4> =====

BBStart <block_2>  (mergeNode)
BBEnd </block_2> =====

(3)
Check and reverse the branch inside block_1. cloneEnd is block_4 and cloneEnd->getExit()->getNextTreeTop() is now the entry of block_2 which is the original fall-through block for block_1. At this point in CFG, there is no longer an edge from block_1 to block_2. Because in (1), it removes the branch destination edge block_1-->block_2, which is the same edge for the fall-through path between block_1 and block_2. This is the special case this PR is handling.

omr/compiler/optimizer/LocalOpts.cpp

Lines 6638 to 6640 in 2799857

    
           if (lastRealNode->getBranchDestination()->getNode()->getBlock()->getNumber() == candidate->getNumber()) 
        
              { 
        
              lastRealNode->reverseBranch(cloneEnd->getExit()->getNextTreeTop());

BBStart <block_1>  (pred or splitPred)
   ificmpne ------> block_2 // branch reversed. The new branch destination is the same as the old branch destination because block_2 was originally block_1's fall-through block and its old branch destination. 
      ...
BBEnd </block_1> =====

BBStart <block_3>  (cloneStart)
BBEnd </block_3> =====

BBStart <block_4>  (cloneEnd)
BBEnd </block_4> =====

BBStart <block_2>  (mergeNode)
BBEnd </block_2> =====

vijaysun-omr · 2025-03-06T17:22:19Z

Thanks for the detailed explanation, it will come in handy when I review the code later today.

My question was less about the mechanics of how the trees were changed step by step, and more about the logical control flow in the program, i.e. if you look at your prior comment, it was unclear what the original position was for block 3 and block 4 with respect to block 1 and block 2 that were shown in the "before block splitter" snippet.

While your last comment clarified that block 3 and block 4 were located after block 2 in the trees, is the transformation you are showing only applicable if block 2 did not have any code apart from BBStart/BBEnd ? The reason that I ask is otherwise it does not look like the "after block splitter" picture shown


BBStart <block_1>  (pred or splitPred)
   ificmpne ------> block_2 // branch reversed. The new branch destination is the same as the old branch destination because block_2 was originally block_1's fall-through block and its old branch destination. 
      ...
BBEnd </block_1> =====

BBStart <block_3>  (cloneStart)
BBEnd </block_3> =====

BBStart <block_4>  (cloneEnd)
BBEnd </block_4> =====

BBStart <block_2>  (mergeNode)
BBEnd </block_2> =====

is functionally equivalent to the "before block splitter" picture shown

block_1: pred or splitPred
block_2: candidate
block_3: cloneStart
block_4: cloneEnd

a7ehuo · 2025-03-06T19:01:52Z

is the transformation you are showing only applicable if block 2 did not have any code apart from BBStart/BBEnd ? The reason that I ask is otherwise it does not look like the “after block splitter” picture shown

None of the blocks are empty. I showed only BBStart and BBEnd to simplify things.

it was unclear what the original position was for block 3 and block 4 with respect to block 1 and block 2 that were shown in the “before block splitter” snippet.

In this particular case, block_3 is a clone of block_2, and block_4 is a clone of block_2's fall-through block.

Before TR_BlockSplitter::splitBlock
-------------------------------------
block_1: pred or splitPred. The last real tree top is ificmpeq and its branch destination is block_2
block_2: candidate

   cfg 1->2

After TR_BlockSplitter::splitBlock
-------------------------------------

block_1: pred or splitPred. The last real tree top is reversed from ificmpeq into ificmpne. The new branch destination for ificmpne is still block_2 because block_2 was the original fall-through block for block_1
block_3: cloneStart     // clone of block_2
block_4: cloneEnd       // clone of block_2's fall-through block
block_2: candidate

   cfg: 1->3, 3->4      // missing 1->2

compiler/optimizer/LocalOpts.cpp

vijaysun-omr · 2025-03-07T00:18:31Z

Jenkins build all

vijaysun-omr · 2025-03-07T00:19:06Z

The only suggestion is to add a comment. So I am starting testing anyway.

There is a case where before block splitter, the merge block is the original fall-through block of the split block and it is also the split block's branch destination. In this case, there is only one edge from the split block to the merge block. --- Before block splitter --- BBStart <block_1> (splitPred) ificmpeq ------> block_2 BBStart <block_2> (mergeNode) As part of the block splitter transformation, it removes the edge from the split block to its original branch destination. It reverses the split block's branch destination to its original fall-through block. In this case the new branch destination is the same as the original branch destination, but the edge between them is now missing. We need to create the edge if it doesn't exist. --- After block splitter --- BBStart <block_1> (splitPred) ificmpne -----> block_2 // branch reversed BBStart <block_3> (cloneStart) BBStart <block_4> (cloneEnd) BBStart <block_2> (mergeNode) ----------------------------- Fixes: eclipse-openj9/openj9#21030 Signed-off-by: Annabelle Huo <Annabelle.Huo@ibm.com>

a7ehuo · 2025-03-07T01:05:57Z

Jenkins build all

vijaysun-omr · 2025-03-07T14:08:32Z

Jenkins build amac,riscv

a7ehuo · 2025-03-07T15:05:20Z

Both failures fail in PR #7679 test too.

linux_riscv64 failed with the following error, which also failed in PR #7679 test too. Both PR tests run on: riscv-build1

09:09:21  [WS-CLEANUP] Deleting project workspace...
09:09:21  [WS-CLEANUP] Deferred wipeout is used...
09:09:21  ERROR: Cannot delete workspace :Remote call on riscv-build1 failed

osx_aarch64 failed with porttest, which also failed in PR #7679 test too. Both PR tests run on mac15-aarch64-1

[2025-03-07T14:17:51.280Z] 15: [  FAILED  ] PortSysinfoTest.sysinfo_test_sysinfo_set_limit_ADDRESS_SPACE (0 ms)
...
09:21:46  The following tests FAILED:
09:21:46  	 15 - porttest (Failed)

a7ehuo requested a review from vijaysun-omr as a code owner March 6, 2025 13:56

a7ehuo added the comp:compiler label Mar 6, 2025

vijaysun-omr self-assigned this Mar 6, 2025

vijaysun-omr reviewed Mar 6, 2025

View reviewed changes

compiler/optimizer/LocalOpts.cpp Show resolved Hide resolved

a7ehuo force-pushed the fix-block-splitter-missing-edge branch from f30e683 to 6cb52ac Compare March 7, 2025 01:04

vijaysun-omr approved these changes Mar 7, 2025

View reviewed changes

vijaysun-omr merged commit 23100e7 into eclipse-omr:master Mar 7, 2025
11 of 13 checks passed

a7ehuo mentioned this pull request Mar 7, 2025

(0.51) Add missing edge in block splitter eclipse-openj9/openj9-omr#222

Merged

mpirvu mentioned this pull request Mar 13, 2025

Increase a couple of inliner thresholds #7688

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Add missing edge in block splitter #7680

Add missing edge in block splitter #7680

Uh oh!

a7ehuo commented Mar 6, 2025

Uh oh!

a7ehuo commented Mar 6, 2025

Uh oh!

vijaysun-omr commented Mar 6, 2025 •

edited

Loading

Uh oh!

a7ehuo commented Mar 6, 2025 •

edited

Loading

Uh oh!

vijaysun-omr commented Mar 6, 2025

Uh oh!

a7ehuo commented Mar 6, 2025

Uh oh!

Uh oh!

vijaysun-omr commented Mar 7, 2025

Uh oh!

vijaysun-omr commented Mar 7, 2025

Uh oh!

a7ehuo commented Mar 7, 2025

Uh oh!

vijaysun-omr commented Mar 7, 2025

Uh oh!

a7ehuo commented Mar 7, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Add missing edge in block splitter #7680

Add missing edge in block splitter #7680

Uh oh!

Conversation

a7ehuo commented Mar 6, 2025

Uh oh!

a7ehuo commented Mar 6, 2025

Uh oh!

vijaysun-omr commented Mar 6, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

a7ehuo commented Mar 6, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

vijaysun-omr commented Mar 6, 2025

Uh oh!

a7ehuo commented Mar 6, 2025

Uh oh!

Uh oh!

vijaysun-omr commented Mar 7, 2025

Uh oh!

vijaysun-omr commented Mar 7, 2025

Uh oh!

a7ehuo commented Mar 7, 2025

Uh oh!

vijaysun-omr commented Mar 7, 2025

Uh oh!

a7ehuo commented Mar 7, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

vijaysun-omr commented Mar 6, 2025 •

edited

Loading

a7ehuo commented Mar 6, 2025 •

edited

Loading