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

Kevin Qin kevinqindev at gmail.com
Wed Mar 11 22:41:23 PDT 2015


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>


More information about the llvm-dev mailing list