This is an archive of the discontinued LLVM Phabricator instance.

Make MergeBlockIntoPredecessor conformant to the precondition of calling DTU.applyUpdates
ClosedPublic

Authored by NutshellySima on Feb 20 2019, 5:55 AM.

Details

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.

Diff Detail

Event Timeline

NutshellySima created this revision.Feb 20 2019, 5:55 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 20 2019, 5:55 AM

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.

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.

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.

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.

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 accepted this revision.Feb 26 2019, 2:13 PM

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. :)

This revision is now accepted and ready to land.Feb 26 2019, 2:13 PM
This revision was automatically updated to reflect the committed changes.

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!