How to exclude the basic blocks ending with unreachable instructions when calculating the post dominator tree?

Beginners
1

My algorithm has to assume that all basic blocks are post-dominated by the return block. However, I found that the blocks ending with unreachable instructions will break my assumption so I have to exclude them in the post dominator tree.

I’ve tried calling removeUnreachableBlocks() before calculating the function, but nothing seemed to change. Also, I tried the recalculate() function with updates that remove the edges between the unreachable blocks and their predecessors but it had no difference from calculating without these updates.

Therefore, is there any method to solve this problem? Could the only method be removing these basic blocks from the function and restoring them after calculating the post-dominator tree?

2

Did you check if the blocks that you expect to get removed actually get removed?

3

Nope. I think the reason is that removeUnreachableBlocks() means deleting blocks that are unreachable from the entry, which differs from the blocks ending with an unreachable instruction.

4

Oh right, if they can’t be removed it will be trickier. Is there no way to lift the restriction? You could also have multiple blocks with returns, right?

5

I’m running my pass on C codes and I didn’t see multiple blocks with returns so I think these blocks ending with unreachable instructions are the only problems.

6

May I give an example to your question, see the following code:
int x = 3;
if(x == 3) {
x *= 2;
} else {
x++;
}
return x;

the cfg be like:
bb1
bb2 bb3
bb4

bb1 is dominate bb4, because every path to bb4 will pass bb1. but bb4 is not post-dom bb3, because the bb3 is not always on the line from bb4 to bb1. I don’t know if this is your example. And in this code, if you don’t detected unreachable code, you can not get the conclusion that bb2 or bb3 is dominated and post-dom too. I’m confused about this question. and may be you want to remove the unreachable instruction, you should do useless code elimination first.

7

I’ve got the solution. Just call removeFromParent() for all basic blocks ending with an unreachable instruction, then calculate the post-dominator tree. After that, I can add all the removed basic blocks back to the function. This will change the text of codes but the function’s CFG will keep the same.

1 Like