Page MenuHomePhabricator

LoopRotation: remove iterative calls to rotateLoops
AbandonedPublic

Authored by sebpop on Jun 10 2016, 12:36 PM.

Details

Summary

Loops should be rotated only once. Passes regression test and llvm test-suite.

Patch wrote by Aditya Kumar and Sebastian Pop.

Diff Detail

Event Timeline

sebpop updated this revision to Diff 60387.Jun 10 2016, 12:36 PM
sebpop retitled this revision from to LoopRotation: remove iterative calls to rotateLoops.
sebpop updated this object.
sebpop added reviewers: dberlin, atrick, hfinkel.
sebpop added subscribers: llvm-commits, hiraditya.
dberlin edited edge metadata.Jun 10 2016, 12:37 PM
dberlin added a subscriber: dberlin.

What's the reasoning/justification for the original vs the change?

sanjoy added a subscriber: sanjoy.Jun 10 2016, 12:49 PM

I thought @mzolotukhin had done this already?

What's the reasoning/justification for the original vs the change?

As the code is written, the function rotateLoop only execute once.

// Rotate if either the loop latch does *not* exit the loop, or if the loop
// latch was just simplified.
if (L->isLoopExiting(OrigLatch) && !SimplifiedLatch)
  return false;

Furthermore a testcase that contains more than 1 loop exit does not get rotated correctly: only the first condition gets rotated.

void foo (int *p, int a, int b) {

while (a % b && b / a) {
  *p = a++;
  p++;
}

}

We are working on fixing the rotation of this loop in a separate patch.

@sanjoy: yeah, that's my patch D20181. I missed your LGTM, so I haven't committed it though.

@sebpop: it's interesting, I'm working on that too actually. How do you plan to handle that and how far have you progressed with it? I hope to get something working soonish.

@dberlin: it's kind of a cleanup. We don't call it more than once anyway, so this is just unnecessary complication in the code.

@mzolotukhin, yeah, i was added as a reviewer, but had no context, so just
trying to figure out what's up :)

Thanks for your patch: it looks similar, so you have one more LGTM ;-)
Could you please commit?

@sebpop: it's interesting, I'm working on that too actually. How do you plan to handle that and how far have you progressed with it? I hope to get something working soonish.

We haven't got very far: we just have seen this oddity today.
We were also thinking to remove the corner cases of code hoisting from loop rotation (it is not the place to do these cleanups.)
And then we would simplify the code copying with a plain BB->copy().
We need to keep copying BBs as far as we have not reached the loop latch and still under some budget in terms of number of copied instructions.

sebpop abandoned this revision.Jun 10 2016, 2:22 PM

Duplicate of D20181.

I committed D20181 in r272439.

We were also thinking to remove the corner cases of code hoisting from loop rotation (it is not the place to do these cleanups.)

Yeah, these clean-ups are always getting in the way. I really think we should improve LoopSimplifyCFG and introduce LoopInstSimplify that would take care of that (I have that on my todo list, but I'm not sure if I can make it in a near future).

And then we would simplify the code copying with a plain BB->copy().
We need to keep copying BBs as far as we have not reached the loop latch and still under some budget in terms of number of copied instructions.

Right, my idea was to make loop-rotation more generic, thus enabling it on more complicated loops. It has some interesting corner cases though: for instance you can end up with several nested loops after rotating a single loop, but that's details, which we'll figure out in the process:)

Right, my idea was to make loop-rotation more generic, thus enabling it on more complicated loops. It has some interesting corner cases though: for instance you can end up with several nested loops after rotating a single loop, but that's details, which we'll figure out in the process:)

I discussed about this with Aditya, and we think that a better idea is
to make jump-threading handle the loop rotation: there is no reason to
have rotation as a separate pass when jump-threading is already
(supposed to) do the same transform.


llvm-commits mailing list
llvm-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-commits

Can you please elaborate how jump-threading can handle loop-rotation? Are you talking about some particular case, or in general?

Michael

In general, loop rotation is just "split the header block into two versions", which is precisely the sort of transform jump threading does. Actually, the only reason JumpThreading doesn't rotate loops at the moment is that it's explicitly suppressed for loop headers.

atrick edited edge metadata.Jun 13 2016, 5:31 PM

Of course loop rotation and jump threading are both forms of tail-duplication. So what! That doesn't mean they should be the same pass. These things are done for different reasons. Loop rotation's job is to put loops into a canonical form for the sake of all other downstream loop passes.

When two passes share common transformations, they should share a utility. They should not be combined into one pass unless they
(a) are driven be the same analysis
(b) have the same pass ordering dependencies

It is very likely that LLVM clients who care about compile time will run -loop-rotate, and not -jump-threading.
(They will also likely want a light-weight "tail duplication" which we unfortunately don't provide)

When two passes share common transformations, they should share a utility. They should not be combined into one pass unless they
(a) are driven be the same analysis
(b) have the same pass ordering dependencies

I stand corrected: loop-rotation and jump-thread should remain in separate passes.

Maybe we can improve the current code by using the same code generation functionality:
I see that currently there is no function to duplicate a single entry multiple exits (SEME) path
needed for both loop-rotation and jump-threading.