Hi, there have been a bit of talk on improving loops with control flow, i.e. when there is no single dominant path through the loop. To have that discussion here let me make the following proposal (based on a proposal from Armin): How about aiming for something that starts out with running the current JIT with the unrolling disabled. That will produce a graph of traces which we could partition into one subgraph per loop. When we believe all guards are either traced or never failing, we use such subgraphs as preambles. That is, we copy the full graph to producing a peeled loop graph and optimized it. We focus the optimization on removing the remaining guards as they (hopefully in most cases) are loop invariant. Then we have a guard free graph of traces that we could pass to gcc/llvm and the resulting machine code are attached after the preamble. If it turns out to be necessary, we could later add support for handing guards to better support cases where we are unable optimize them out. -- Håkan Ardö
Hi Hakan, On Thu, May 2, 2013 at 11:52 AM, Hakan Ardo <hakan@debian.org> wrote:
there have been a bit of talk on improving loops with control flow, i.e. when there is no single dominant path through the loop. To have that discussion here let me make the following proposal (based on a proposal from Armin):
I proposed nothing more or less than sending our loops to gcc/llvm. You're suggesting some refactorings of the way loops are produced, which may make sense or not, but is more than I ever claim to have proposed :-)
If it turns out to be necessary, we could later add support for handing guards to better support cases where we are unable optimize them out.
One quick word, I doubt very strongly that we can hope to remove *all* guards. Starting from that assumption looks wrong to me. In my opinion we'd be left with a large quantity of guards anyway --- mostly guards that never failed so far and probably never will, but which cannot be proven never to fail. (They would fail in some rare circumstances like suddenly starting pdb, or some integer computation overflowing; or, for most of them, you'd need some impossibly clever global "prover" to check e.g. that this list here cannot be empty or can only contain objects of this precise type.) A bientôt, Armin.
On Thu, May 2, 2013 at 3:28 PM, Armin Rigo <arigo@tunes.org> wrote:
Hi Hakan,
On Thu, May 2, 2013 at 11:52 AM, Hakan Ardo <hakan@debian.org> wrote:
there have been a bit of talk on improving loops with control flow, i.e. when there is no single dominant path through the loop. To have that discussion here let me make the following proposal (based on a proposal from Armin):
I proposed nothing more or less than sending our loops to gcc/llvm. You're suggesting some refactorings of the way loops are produced, which may make sense or not, but is more than I ever claim to have proposed :-)
Right :) Sorry for being unclear..
If it turns out to be necessary, we could later add support for handing guards to better support cases where we are unable optimize them out.
One quick word, I doubt very strongly that we can hope to remove *all* guards. Starting from that assumption looks wrong to me. In my opinion we'd be left with a large quantity of guards anyway --- mostly guards that never failed so far and probably never will, but which cannot be proven never to fail. (They would fail in some rare circumstances like suddenly starting pdb, or some integer computation overflowing; or, for most of them, you'd need some impossibly clever global "prover" to check e.g. that this list here cannot be empty or can only contain objects of this precise type.)
Your right of course. I pulled some statistics out of our benchmarks by counting the number of ops, guards and not yet traced guards for the three sections defined by the labels in our loops. That would be some setup section, the preamble and the peeled loop. This should give an indication of how good our current unrolling is at getting the never failing guards our of the loop, and it's not very good at it: http://32c60f1d49dbd76e.paste.se/ So we need to support guards from the start. -- Håkan Ardö
participants (2)
-
Armin Rigo -
Hakan Ardo