Remove BB with repetitions in successor

Question

Remove BB with repetitions in successor

Closed this issue 3 years ago · 7 comments

Hello! I've found the simple example which currently breaks BOLT:

main:
    jmp 2f
1:
    je 2f
    jmp 2f
2:
    retq

Since the 1 BB is unreachable it will be removed, but it has repeated successor the 2nd BB. When we call removeAllSuccessors it will call removePredecessor in loop and remove both of the 1st block predecessors for 2nd BB on the first iteration. On the second iteration it will try to remove the same predecessor and fail. To fix this properly I would like to ask why the removeSuccessor/replaceSuccessor calls the removePredecessor with multiple=false argument? Is there any cases when we would like to remove only one successor/predecessor and don't remove the repetitions? In my mind if we call these functions we would always like to remove all of the repetitions. Or even replace vector with set.. Please tell me what do you think about it! Thank you!

Answer 1 · 2021-12-04T20:34:31.000Z

Hi Vladislav!
Thanks for reporting this issue with a minimal test case. I've earlier attempted to fix it with #201, but there has been an internal test crash (with clang binary). I'll take another look next week; chances are that this binary will be added to rafaelauler/bolt-tests repo.

Answer 2 · 2021-12-04T20:41:25.000Z

Hi @yota9, I have added a pass that normalizes CFG by removing duplicate edges and empty blocks. I added it for #231, but it also takes care of this issue.

Answer 3 · 2021-12-04T20:54:48.000Z

Hello @aaupov @maksfb ! Thank you for your answers, if this problem is known I won't fix it :) But anyway is the "multiple" argument in these functions are needed? It confuses me a bit, since I don't see the case when we don't want to remove all of the repeated entries..

Answer 4 · 2021-12-08T10:48:30.000Z

@maksfb Despite of the question above thanks to the new pass I think the issue might be closed. If you'd like I can create PR with the test above.

Answer 5 · 2021-12-09T09:55:48.000Z

@yota9, I think you raise a valid concern. Even thought the crash might be gone, we need to address the root cause.

Answer 6 · 2022-01-09T00:21:35.000Z

The root cause is addressed by 7d47004

Answer 7 · 2022-01-09T01:08:02.000Z

Regarding your question whether removing just the first occurrence of a possibly repeated block makes sense: I've looked at the places where removeSuccessor/replaceSuccessor are invoked, and some of them (e.g. in fixTailCalls) appear to operate on a single control flow edge at a time. So I think we should keep the multiple flag, at least until all the places that invoke removeSuccessor/replaceSuccessor are refactored.