[LLVMdev] Strong post-dominance in LLVM? (original) (raw)

Bjarke Roune broune at google.com
Thu Jul 9 10:42:31 PDT 2015

On Thu, Jul 9, 2015 at 12:42 AM, James Molloy <james at jamesmolloy.co.uk> wrote:

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

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

On Thu, Jul 9, 2015 at 12:42 AM, James Molloy <james at jamesmolloy.co.uk> wrote:

Hi Bjarke,

Forgive my naivety, but wouldn't that involve solving the halting problem? Cheers, James On Thu, 9 Jul 2015 at 02:21 Bjarke Roune <broune at google.com> wrote:

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

LLVM Developers mailing list LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150709/a393170c/attachment.html>

More information about the llvm-dev mailing list