search

facebookarchive / BOLT

Binary Optimization and Layout Tool - A linux command-line utility used for optimizing performance of binaries
2.51k stars 176 forks source link

Remove BB with repetitions in successor #261

Closed yota9 closed 2 years ago

yota9 commented 2 years ago

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!

aaupov commented 2 years ago

Hi Vladislav! Thanks for reporting this issue with a minimal test case. I've earlier attempted to fix it with https://github.com/facebookincubator/BOLT/pull/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.

maksfb commented 2 years ago

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.

yota9 commented 2 years ago

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

yota9 commented 2 years ago

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

maksfb commented 2 years ago

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

aaupov commented 2 years ago

The root cause is addressed by 7d47004d228ab5d72b6e49000824a07415d4a10f

aaupov commented 2 years ago

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.