Make MergeBlockIntoPredecessor conformant to the precondition of calling DTU.applyUpdates

[NutshellySima]

Summary

It is mentioned in the document of DTU that "It is illegal to submit any update that has already been submitted, i.e., you are supposed not to insert an existent edge or delete a nonexistent edge." It is dangerous to violet this rule because DomTree and PostDomTree occasionally crash on this scenario.

This patch fixes MergeBlockIntoPredecessor, making it conformant to this precondition.

[brzycki]

Thank you for looking into this. I was working on applying MergeBLockIntoPredecessor replacement in JumpThreading.cpp (via D48202) and ran into check failures that I haven't had time to properly debug. I suspect at least one of these is related to the change you made above.

[NutshellySima]

In D58444#1404242, @brzycki wrote:

Thank you for looking into this. I was working on applying MergeBLockIntoPredecessor replacement in JumpThreading.cpp (via D48202) and ran into check failures that I haven't had time to properly debug. I suspect at least one of these is related to the change you made above.

Thanks for your comment! I am worried about the difficulty in discovering and debugging bugs involving incremental DT updating. I think it is indeed easy to violet the preconditions of applyUpdates() and I believe if it is a concern, a strict validation should be added to check if preconditions are fulfilled in DEBUG mode later.

[brzycki]

In D58444#1404380, @NutshellySima wrote:

In D58444#1404242, @brzycki wrote:

Thank you for looking into this. I was working on applying MergeBLockIntoPredecessor replacement in JumpThreading.cpp (via D48202) and ran into check failures that I haven't had time to properly debug. I suspect at least one of these is related to the change you made above.

Thanks for your comment! I am worried about the difficulty in discovering and debugging bugs involving incremental DT updating. I think it is indeed easy to violet the preconditions of applyUpdates() and I believe if it is a concern, a strict validation should be added to check if preconditions are fulfilled in DEBUG mode later.

@NutshellySima I've spent some time this week working to use the replacement MergeBLockIntoPredecessor in JumpThreading.cpp along with this patch. I'm still dealing with correctness issues due to slight differences in the API interface assumptions as well as the change of BB being hoisted (new) versus SinglePred being sunk (old). There are impacts to other analysis like LVI and LoopHeaders along with changes in the IR due to blocks getting different names.

I'll keep you informed if I pass all correctness tests with my changes.

[NutshellySima]

In D58444#1407194, @brzycki wrote:

In D58444#1404380, @NutshellySima wrote:

In D58444#1404242, @brzycki wrote:

Thank you for looking into this. I was working on applying MergeBLockIntoPredecessor replacement in JumpThreading.cpp (via D48202) and ran into check failures that I haven't had time to properly debug. I suspect at least one of these is related to the change you made above.

Thanks for your comment! I am worried about the difficulty in discovering and debugging bugs involving incremental DT updating. I think it is indeed easy to violet the preconditions of applyUpdates() and I believe if it is a concern, a strict validation should be added to check if preconditions are fulfilled in DEBUG mode later.

@NutshellySima I've spent some time this week working to use the replacement MergeBLockIntoPredecessor in JumpThreading.cpp along with this patch. I'm still dealing with correctness issues due to slight differences in the API interface assumptions as well as the change of BB being hoisted (new) versus SinglePred being sunk (old). There are impacts to other analysis like LVI and LoopHeaders along with changes in the IR due to blocks getting different names.

I'll keep you informed if I pass all correctness tests with my changes.

Thanks! Sounds like it will be possible to avoid DomTree recalculations then. :) I’m glad to help if there is anything involving DTU to the best of my knowledge.

[brzycki]

Thanks! Sounds like it will be possible to avoid DomTree recalculations then. :) I’m glad to help if there is anything involving DTU to the best of my knowledge.

I appreciate it. So far the issues I've had to deal with are all related to test cases, LVI, or the ABI change that MErgeBlockIntoPredecessor can return false and not merge blocks. I'm running test-suite today to double-check my changes. If that goes well I'll probably give you a "LGTM" on this change.

[brzycki]

I finished performing functional testing using MergeBlockIntoPredecessor in JumpThreading.cpp. With this change I was able to pass make-check and test-suite. I saw no crashes and believe this to be the correct updates for DTU.

Thank you @NutshellySima for proactively fixing this. :)

[NutshellySima]

In D58444#1411301, @brzycki wrote:

I finished performing functional testing using MergeBlockIntoPredecessor in JumpThreading.cpp. With this change I was able to pass make-check and test-suite. I saw no crashes and believe this to be the correct updates for DTU.

Thank you @NutshellySima for proactively fixing this. :)

Thanks!

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

bool llvm::MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU,
   // DTU update: Collect all the edges that exit BB.
   // These dominator edges will be redirected from Pred.
   std::vector<DominatorTree::UpdateType> Updates;
   if (DTU) {
     Updates.reserve(1 + (2 * succ_size(BB)));
     Updates.push_back({DominatorTree::Delete, PredBB, BB});
     for (auto I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
       Updates.push_back({DominatorTree::Delete, BB, *I});
+      // This successor of BB may already have PredBB as a predecessor.
+      if (llvm::find(successors(PredBB), *I) == succ_end(PredBB))
         Updates.push_back({DominatorTree::Insert, PredBB, *I});
     }
   }
 
   if (MSSAU)
     MSSAU->moveAllAfterMergeBlocks(BB, PredBB, &*(BB->begin()));
 
   // Delete the unconditional branch from the predecessor...
   PredBB->getInstList().pop_back();