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

~ Johannes

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

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

~ Johannes

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

Thanks a lot Johannes,

I’m looking into it!

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