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

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>

----- Original Message -----
> From: "Kevin Qin" <kevinqindev at gmail.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "LLVM Developers Mailing List" <llvmdev at
cs.uiuc.edu>, "chandlerc" <chandlerc at gmail.com>,
"James Molloy"
> <james at 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
> 
> 
> 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
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

Hi Hal,

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

Cheers,
Kevin

2015-03-11 20:37 GMT+08:00 Hal Finkel <hfinkel at anl.gov>:
> ----- Original Message -----
> > From: "Kevin Qin" <kevinqindev at gmail.com>
> > To: "Hal Finkel" <hfinkel at anl.gov>
> > Cc: "LLVM Developers Mailing List" <llvmdev at
cs.uiuc.edu>, "chandlerc" <
> chandlerc at gmail.com>, "James Molloy"
> > <james at 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
>
> >
> >
> > 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
>
> --
> 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/20150312/642fd037/attachment.html>