3 ms·

" I'm confident termination here can be very directly mapped to solving the halting problem." Why? Iterative dataflow problems, in particular, capturing secon

" I'm confident termination here can be very directly mapped to solving the halting problem." Why? Iterative dataflow problems, in particular, capturing second order effects, etc, are very well known things and often do not require solving the halting problem or anything like it. Just propagating analysis facts around (IE "i can thread this jump"). In fact, i'm fairly confident standard jump threading (which this isn't quite) can be split into an analysis and optimization path. This is because you already know what the CFG will look like if you perform a particular jump threading. This is similar to PRE and other situations where you know what the end result of a given expression being PRE'd will be, and thus, you can figure out whether what the full end state of the transform will be, regardless of whether you do it. In fact, if you couldn't do this, you couldn't do LCM as two unidirectional dataflow problems. Jump threading seems much the same. Completely decomposable, regardless of whether you perform a given path of optimizations or not. The only question is the expense of doing so.

MatzeBraun 11y ago
I am not convinced it's that simple if 1 application of jump threading creates a new opportunity. The endlessly unreliable loop example in the post suggests that is is a halting problem to find out whether we should stop jump threading because we are unrolling an endless loop or not.
- perlgeek 11y ago
  Though there's a very pragmatic solution for the compiler: Stop after a fixed number of iterations. Since it's an optimization, and not required for correct operation of the compiler, one can simply give up instead of risking an infinite loop.
- DannyBee 11y ago
  First, that example is not jump threading, since its cloning code and CFG blocks. https://en.wikipedia.org/wiki/Jump_threading https://en.wikipedia.org/wiki/Jump_threading is a better description of jump threading. In what the author describes as jump threading, you have the same problem as loop peeling or any other loop optimization that may get applied to an infinite loop and want to duplicate per-iteration code from that loop. Yet somehow, as you'll see, we can prove things about the end states of those optimizations. ;-)

MatzeBraun 11y ago

I am not convinced it's that simple if 1 application of jump threading creates a new opportunity. The endlessly unreliable loop example in the post suggests that is is a halting problem to find out whether we should stop jump threading because we are unrolling an endless loop or not.

perlgeek 11y ago
Though there's a very pragmatic solution for the compiler: Stop after a fixed number of iterations. Since it's an optimization, and not required for correct operation of the compiler, one can simply give up instead of risking an infinite loop.
DannyBee 11y ago
First, that example is not jump threading, since its cloning code and CFG blocks. https://en.wikipedia.org/wiki/Jump_threading https://en.wikipedia.org/wiki/Jump_threading is a better description of jump threading. In what the author describes as jump threading, you have the same problem as loop peeling or any other loop optimization that may get applied to an infinite loop and want to duplicate per-iteration code from that loop. Yet somehow, as you'll see, we can prove things about the end states of those optimizations. ;-)