Encourage loop cloning #21
Conversation
A small constant loop iteration count is easy for the JIT to detect, and leads to the JIT unrolling the loop, if other profitability conditions occur. It never leads to loop cloning. Sometimes choosing larger loop bounds does lead to cloning, though in the cases I tried, less than 0.5% of generated programs ended up with cloned loops.
|
@jakobbotsch PTAL |
| { | ||
| // An iteration count of 2 leads to JIT loop unrolling (if size contraints apply). An iteration count of 40 is larger | ||
| // than the JIT allowed constant loop iteration unroll count, and leads to loop cloning. | ||
| T iterationCount = random.FlipCoin(random.Options.SmallLoopIterationCountProb) ? T.CreateChecked(2) : T.CreateChecked(40); |
There was a problem hiding this comment.
With the high probability of generating 40 iterations I would be worried about generating many nested loops of with 40 iterations. This probably should have some kind of budget inside GenLoop.
The nesting level is controlled by this hill equation: https://www.desmos.com/calculator/oiftyfbfrh
It makes the nesting of a bunch of for loops rare, but since the curve is O(40^n) it grows very rapidly.
There was a problem hiding this comment.
I was thinking an alternative would be to keep the iteration count low, but put the iteration end in a global static variable, so maybe the JIT wouldn't be able to "inline" the value.
There was a problem hiding this comment.
Maybe something like that is the way to go. It also has to be compatible reduction, however.
I wonder if we should add some CheckBudget method to IRuntime and then generate a dynamic if (!s_rt.CheckBudget()) break; in all the loops we are worried about. We would also have to teach the reducer to never remove that.
It does pollute all generated loops with an early exit, making the lower bound on the trip count unknowable, which excludes a whole class of possible loop transformations.
There was a problem hiding this comment.
It does pollute all generated loops with an early exit, making the lower bound on the trip count unknowable, which excludes a whole class of possible loop transformations.
I think that makes this option a non-starter.
There was a problem hiding this comment.
I think all RyuJITs loop transformations handle multiple exits (in practice, due to exceptions, almost all loops come with unknowable lower bounds on the trip count). So I think this budget based approach would be much better for coverage than putting the iteration end in a static variable, where none of the JIT's IV opts would be able to reason about it.
A small constant loop iteration count is easy for the JIT to detect, and
leads to the JIT unrolling the loop, if other profitability conditions
occur. It never leads to loop cloning.
Sometimes choosing larger loop bounds does lead to cloning, though in
the cases I tried, less than 0.5% of generated programs ended up with
cloned loops.