llvm dev - Mar 2015 - [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?

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


-- 
Thanks a lot in advance,

Kevin Qin
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150311/294a47c1/attachment.html>

----- Original Message -----
> From: "Kevin Qin" <kevinqindev at gmail.com>
> To: "LLVM Developers Mailing List" <llvmdev at 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
> 
> If you have any better solution, don't hesitate to share.
> 
> 
> 
> --
> 
> 
> Thanks a lot in advance,
> 
> 
> Kevin Qin
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

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

2015-03-11 17:05 GMT+08:00 Hal Finkel <hfinkel at anl.gov>:
> ----- Original Message -----
> > From: "Kevin Qin" <kevinqindev at gmail.com>
> > To: "LLVM Developers Mailing List" <llvmdev at
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
>
> >
> > If you have any better solution, don't hesitate to share.
> >
> >
> >
> > --
> >
> >
> > Thanks a lot in advance,
> >
> >
> > Kevin Qin
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
>


-- 
Best Regards,

Kevin Qin
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150311/10631550/attachment.html>