Strong post-dominance in LLVM?

Project Infrastructure LLVM Dev List Archives
1

There is PostDominatorTree for determining post-dominance. Even if A post-dominates B and B is executed, that doesn’t guarantee that A will be executed. For example, there could be an infinite loop in-between. Strong post-dominance makes the stronger guarantee that there will be no infinite loop from B to A. Do we have anything in LLVM for determining strong post-dominance and in general for guaranteeing that if B is executed, then A will also be executed?

Bjarke

2

Hi Bjarke,

Forgive my naivety, but wouldn’t that involve solving the halting problem?

Cheers,

James

3

Hi James, Bjarke,

4

If I had to have the exact right answer for every input, then yes. If you allow a return value of “I don’t know” for some inputs, then you can solve the halting problem trivially by always returning “I don’t know”. Better solutions return “I don’t know” on a smaller subset of the inputs. That the halting problem is undecidable then just means that all correct solutions must return “I don’t know” for some inputs.

Bjarke

5

There is PostDominatorTree for determining post-dominance. Even if A
post-dominates B and B is executed, that doesn't guarantee that A will be
executed. For example, there could be an infinite loop in-between. Strong
post-dominance makes the stronger guarantee that there will be no infinite
loop from B to A. Do we have anything in LLVM for determining strong
post-dominance and in general for guaranteeing that if B is executed, then A
will also be executed?

The closest thing to this I can think of is `isGuaranteedToExecute` in
LICM.cpp. Perhaps that mechanism can be generalized?

6

nested infinite loops, yet it uses this function to hoist trapping
instructions. I also don't think that it works correctly if the loop itself
iterates infinitely but does have exit blocks in the CFG. I think this
function is based on the assumption that all loops terminate, but I don't
see where LICM checks that. I'm about to file a bug for that and see if I
can trigger it in an example, but feel free to save me the effort if you
know some reason that what it's doing is OK?

Bjarke

7

Thanks. I took a look at it. It does not appear to take into account nested
infinite loops, yet it uses this function to hoist trapping instructions. I
also don't think that it works correctly if the loop itself iterates
infinitely but does have exit blocks in the CFG. I think this function is
based on the assumption that all loops terminate, but I don't see where LICM
checks that. I'm about to file a bug for that and see if I can trigger it in
an example, but feel free to save me the effort if you know some reason that
what it's doing is OK?

Hah, I *just* filed 24078 – LICM incorrectly hoists load :slight_smile: CC'ed you

-- Sanjoy