It seems that tail duplication can make a reducible CFG irreducible
(example below). Is that intentional? Are there other optimizations
that have that property?
Is irreducibility a problem for existing LLVM passes? It looks like
there was once an open project for a pass to make irreducible graphs
reducible. Was that ever implemented?
- Mark
; "opt -inline -tailduplicate" makes an irreducible CFG from this code
@x = weak global float 0.0
define internal fastcc void @foo(float %f) {
entry:
%b = fcmp ogt float %f, 0.0
br i1 %b, label %then, label %continue
then:
store float 0.0, float* @x
br label %continue
continue:
ret void
}
define void @test() {
entry:
%x = load float* @x
call fastcc void @foo( float %x )
%neg = sub float 0.0, %x
call fastcc void @foo( float %neg )
ret void
}
On Thu, Jul 24, 2008 at 2:00 PM, Mark Leone <markleone at gmail.com> wrote:> Is irreducibility a problem for existing LLVM passes?There aren't any LLVM passes that expect a reducible CFG at the moment; of course, some passes are more effective with reducible CFGs.> It looks like > there was once an open project for a pass to make irreducible graphs > reducible. Was that ever implemented?There isn't any such pass in trunk LLVM. One could potentially be added, but it would have to be a high-quality implementation, and we'd have to measure the costs and benefits carefully.> ; "opt -inline -tailduplicate" makes an irreducible CFG from this codeI can't reproduce the issue, and I can't see how tailduplicate could possibly make your function irreducible, since it shouldn't be able to introduce a loop into a function without any loops. Can you include the output you're getting, and point out the issue? I guess it's worth pointing out that in trunk LLVM, the tailduplicate pass has been removed from the standard set of passes run by llvm-gcc and opt -std-compile-opts. -Eli
Thanks Eli. It's not introducing loops, just unstructured
conditionals (e.g. X's in the control-flow graph, rather than
diamonds). You can see it using "opt -view-cfg" on the code below.
Sounds like it's not a bug. Thanks for the info.
- Mark
; Tail duplication yielded this code, which has non-structured control flow.
; Note that "then.i2" and "continue.i3" both have
predecessors
; "then.i" and "foo.exit", making an irreducible
"X" in the control-flow graph.
@x = weak global float 0.000000e+00
define void @test() {
entry:
%x = load float* @x
%b.i = fcmp ogt float %x, 0.000000e+00
%neg = sub float 0.000000e+00, %x
%b.i1 = fcmp ogt float %neg, 0.000000e+00
br i1 %b.i, label %then.i, label %continue.i
then.i: ; preds = %entry
store float 0.000000e+00, float* @x
br i1 %b.i1, label %then.i2, label %continue.i3
continue.i: ; preds = %entry
br label %foo.exit
foo.exit: ; preds = %continue.i
br i1 %b.i1, label %then.i2, label %continue.i3
then.i2: ; preds = %foo.exit, %then.i
store float 0.000000e+00, float* @x
ret void
continue.i3: ; preds = %foo.exit, %then.i
br label %foo.exit4
foo.exit4: ; preds = %continue.i3
ret void
}
On Thu, Jul 24, 2008 at 3:38 PM, Eli Friedman <eli.friedman at gmail.com>
wrote:> On Thu, Jul 24, 2008 at 2:00 PM, Mark Leone <markleone at gmail.com>
wrote:
>> Is irreducibility a problem for existing LLVM passes?
>
> There aren't any LLVM passes that expect a reducible CFG at the
> moment; of course, some passes are more effective with reducible CFGs.
>
>> It looks like
>> there was once an open project for a pass to make irreducible graphs
>> reducible. Was that ever implemented?
>
> There isn't any such pass in trunk LLVM. One could potentially be
> added, but it would have to be a high-quality implementation, and we'd
> have to measure the costs and benefits carefully.
>
>> ; "opt -inline -tailduplicate" makes an irreducible CFG from
this code
>
> I can't reproduce the issue, and I can't see how tailduplicate
could
> possibly make your function irreducible, since it shouldn't be able to
> introduce a loop into a function without any loops. Can you include
> the output you're getting, and point out the issue?
>
> I guess it's worth pointing out that in trunk LLVM, the tailduplicate
> pass has been removed from the standard set of passes run by llvm-gcc
> and opt -std-compile-opts.
>
> -Eli
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
hi mark,> It seems that tail duplication can make a reducible CFG irreducible > (example below). Is that intentional? Are there other optimizations > that have that property?there has been a discussion on this problem some weeks ago: http://lists.cs.uiuc.edu/pipermail/llvmdev/2008-June/015247.html the message includes a patch for taildup, that disables the duplication of loop headers. there are some remarks on the patch in follow-up messages, most notably it causes some compiltime overhead (~1%-2% on spec benchmarks). note that, taildup has been completely removed on trunk. florian -- Brandner Florian CD Laboratory - Compilation Techniques for Embedded Processors Institut für Computersprachen E185/1 Technische Universität Wien Argentinierstraße 8 / 185 A-1040 Wien, Austria Tel.: (+431) 58801-58521 E-Mail: brandner at complang.tuwien.ac.at