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>
Johannes Doerfert via llvm-dev
2020-Jul-01 23:12 UTC
[llvm-dev] Inner Loop extraction in LLVM
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_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/7ff9fd8a/attachment.html>
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>