[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: "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