Strong post-dominance in LLVM?

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

Hi Bjarke,

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

Cheers,

James

Hi James, Bjarke,

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

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?

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

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 https://llvm.org/bugs/show_bug.cgi?id=24078 :slight_smile: CC'ed you

-- Sanjoy