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

[Hal Finkel]

----- 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