[llvm-dev] Inner Loop extraction in LLVM

[iulian brumar via llvm-dev]

 Thanks a lot Johannes,

I'm looking into it!
     On Wednesday, July 1, 2020, 07:13:33 PM EDT, Johannes Doerfert <johannesdoerfert at gmail.com> wrote:  
 
  
In the case below you probably don't need to split much.
 
It might be more complicated if the two loops share edges, i.a.,
 

 
 
```
 
 
for (...) {
 
 
  for (...) {
 
 
    if (...)
 
      return;
 
  }
 
}
 
```
 

 
 
I guess the trick is to isolate the inner loop properly so that extraction becomes trivial.
 
If you for example make sure there is a single "entering" edge (from outside the loop to the header),
 
 and a single "exiting" edge (from the loop to a block not in the loop), outlining can be done with
 
the code extractor for blocks we already have. (Unclear about updating analyses though).
 

 
 

 
 

 
 

 
 On 7/1/20 5:36 PM, iulian brumar wrote:
  
  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_bbbbs_between_loop1_header_and_loop2_headerloop2_header_bbloop_body_bbsbr loop2_header_bbinstructions_before_loop1_end_and_after_loop2_endbr loop1_header_bbIn 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/20200702/0beb1ea6/attachment.html>