How to run two loop passes non-interleaved if they are registered one by one?

Hi LLVM developers,

I want to add LICM pass after loop unrolling pass in current optimization pipeline. Because both of them are loop passes, so if I registered them one by one, they will interleaved go through all loops in bottom up way within same loop pass manager. Loop unroling pass may create new inner loops from partial unrolling, and those newly created loops can be visited only if the rest of loop passes are finished on current loop. The problem is, this visit order may be not in bottom up way, but that is order is required by LICM.

For example, the input has 2 nested loops(L1 and L2).

for () { //L1
for() { }//L2
}

We registered LICM pass after loop unrolling pass, so these 2 passes will share the same loop pass manager. The initialized work queue will be (L1, L2). Loop pass manager always pops out the last object, so loop unrolling pass will visit L2 first, and then LICM pass. When L2 is visited by all passes, it will be removed from queue. At this stage, everything is fine.

Next, L1 is on process, and it’s partial unrolled from loop unrolling pass, and finally L3 is created.

for () { //L1
for() { }//L2
for() { }//L3

}

Here’s the problem. As LICM shared same loop pass manager will loop unrolling pass, then L1 will be visited by LICM. But LICM extremely requires a bottle up visit order, and at this moment, L1 is visited earlier than L3, this will cause assertion failure.

The best solution for this is spiting two passes into different pass manager, and let them run non-interleaved. But I don’t know how to implement this within legacy pass manager. Does anyone know how to do that?

If you have any better solution, don’t hesitate to share.

From: "Kevin Qin" <kevinqindev@gmail.com>
To: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>
Sent: Wednesday, March 11, 2015 3:47:35 AM
Subject: [LLVMdev] How to run two loop passes non-interleaved if they are registered one by one?

Hi LLVM developers,

I want to add LICM pass after loop unrolling pass in current
optimization pipeline. Because both of them are loop passes, so if I
registered them one by one, they will interleaved go through all
loops in bottom up way within same loop pass manager. Loop unroling
pass may create new inner loops from partial unrolling, and those
newly created loops can be visited only if the rest of loop passes
are finished on current loop. The problem is, this visit order may
be not in bottom up way, but that is order is required by LICM.

For example, the input has 2 nested loops(L1 and L2).

for () { //L1
for() { }//L2
}

We registered LICM pass after loop unrolling pass, so these 2 passes
will share the same loop pass manager. The initialized work queue
will be (L1, L2). Loop pass manager always pops out the last object,
so loop unrolling pass will visit L2 first, and then LICM pass. When
L2 is visited by all passes, it will be removed from queue. At this
stage, everything is fine.

Next, L1 is on process, and it's partial unrolled from loop unrolling
pass, and finally L3 is created.

for () { //L1
for() { }//L2
for() { }//L3

}

Here's the problem. As LICM shared same loop pass manager will loop
unrolling pass, then L1 will be visited by LICM. But LICM extremely
requires a bottle up visit order, and at this moment, L1 is visited
earlier than L3, this will cause assertion failure.

The best solution for this is spiting two passes into different pass
manager, and let them run non-interleaved. But I don't know how to
implement this within legacy pass manager. Does anyone know how to
do that?

I believe that, generically, we've needed 'barrier' passes for this purpose. Creating a 'noop' function pass is an option. In this case, inserting a run of instcombine (or, if that's too expensive for some reason, instsimplify) could be reasonable. I can imagine unrolling creating things that turn out to be loop invariant only after simplification (especially considering that we rely on simplification to clean up the repeated induction variable increments, etc. after unrolling).

-Hal

Hi Hal,

James told me that in PassManagerBuilder.cpp, BarrierNoopPass is already used for this kind of purpose(though there’s also a fixme saying it’s hacking). I think it’s a good idea to use this pass here.

Thanks,
Kevin

From: "Kevin Qin" <kevinqindev@gmail.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "LLVM Developers Mailing List" <llvmdev@cs.uiuc.edu>, "chandlerc" <chandlerc@gmail.com>, "James Molloy"
<james@jamesmolloy.co.uk>
Sent: Wednesday, March 11, 2015 5:04:49 AM
Subject: Re: [LLVMdev] How to run two loop passes non-interleaved if they are registered one by one?

Hi Hal,

James told me that in PassManagerBuilder.cpp, BarrierNoopPass is
already used for this kind of purpose(though there's also a fixme
saying it's hacking). I think it's a good idea to use this pass
here.

Yes and no. BarrierNoopPass is a module level pass (we use it to break out of the CGSCC pass manager), and so is overkill here. You just need a function level pass. If you're adding this near the end, it might not matter that much, however.

-Hal

Hi Hal,

Thanks for your reminding. Finally I inserted InstructionSimplifier pass as barrier and committed it at r232011.

Cheers,
Kevin