llvm dev - Jul 2020 - Inner Loop extraction in LLVM

Hello everyone,

Quick question about loop extraction in llvm. I've been using the
LoopExtractor pass in llvm/lib/Transforms/IPO/LoopExtractor.cpp to extract top
level loops from programs.

I'm wondering if extracting inner-most loops is any more complex than using
the BlockExtractor pass in llvm/lib/Transforms/IPO/BlockExtractor.cpp and making
sure that the basic blocks in the extracted region are single entry-single exit.
Would there be any fundamental differences wrt what LoopExtractor is doing for
top-level loops?

Thanks,
Iulian

Hi Iulian,


On first thought I would think that extracting top-level loops is only 
minimally easier than extracting any other loop level,

if you consider arbitrary input, e.g,. potential irreducible 
"outer-outer-most" loops. For inner ones you might want to split

some blocks and edges to make sure they are not shared with the outer 
loop but other than that, I imagine it to be pretty similar.

(This assumes you do not want to preserve things like LoopInfo, 
ScalarEvolution, ...).

Extracting a single basic block is probably easier still. Again, 
assuming you do not want to update analyses.


If you want more details or think I haven't grasped the essence of your 
questions, feel free to say so :)


~ Johannes



On 7/1/20 4:23 PM, iulian brumar via llvm-dev wrote:
> Hello everyone,
>
> Quick question about loop extraction in llvm. I've been using the
LoopExtractor pass in llvm/lib/Transforms/IPO/LoopExtractor.cpp to extract top
level loops from programs.
>
> I'm wondering if extracting inner-most loops is any more complex than
using the BlockExtractor pass in llvm/lib/Transforms/IPO/BlockExtractor.cpp and
making sure that the basic blocks in the extracted region are single
entry-single exit. Would there be any fundamental differences wrt what
LoopExtractor is doing for top-level loops?
>
> Thanks,
> Iulian
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200701/fcf28b53/attachment.html>

Hi Johannes,

This is very helpful and thank you for the quick response.

I imagine that the usual nested loop structure is something like:

loop1_header_bb
bbs_between_loop1_header_and_loop2_header
loop2_header_bb
loop_body_bbs
br loop2_header_bb
instructions_before_loop1_end_and_after_loop2_end
br loop1_header_bb

In this case you mean that loop2_header_bb might need to be split before
extracting loop 2 into its own function? I'm not sure yet about how to use
bb splitting to enable inner-loop extraction and what splitting edges means.

Sincerely, 
Iulian
     On Wednesday, July 1, 2020, 06:06:01 PM EDT, Johannes Doerfert
<johannesdoerfert at gmail.com> wrote:
 
  
Hi Iulian,
 

 
 
On first thought I would think that extracting top-level loops is only minimally
easier than extracting any other loop level,
 
if you consider arbitrary input, e.g,. potential irreducible
"outer-outer-most" loops. For inner ones you might want to split
 
 some blocks and edges to make sure they are not shared with the outer loop but
other than that, I imagine it to be pretty similar.
 
 (This assumes you do not want to preserve things like LoopInfo,
ScalarEvolution, ...).
 
 
Extracting a single basic block is probably easier still. Again, assuming you do
not want to update analyses.
 

 
 
If you want more details or think I haven't grasped the essence of your
questions, feel free to say so :)
 
 

 
 
~ Johannes
 

 
 

 
 On 7/1/20 4:23 PM, iulian brumar via llvm-dev wrote:
  
 Hello everyone,Quick question about loop extraction in llvm. I've been
using the LoopExtractor pass in llvm/lib/Transforms/IPO/LoopExtractor.cpp to
extract top level loops from programs.I'm wondering if extracting inner-most
loops is any more complex than using the BlockExtractor pass in
llvm/lib/Transforms/IPO/BlockExtractor.cpp and making sure that the basic blocks
in the extracted region are single entry-single exit. Would there be any
fundamental differences wrt what LoopExtractor is doing for top-level
loops?Thanks,Iulian_______________________________________________LLVM
Developers mailing listllvm-dev at
lists.llvm.orghttps://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
   
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200701/7822811c/attachment.html>