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
}
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
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
}
Ah... yeah, tailduplicate does some messy stuff. Although, I don't
think you'd normally call a CFG like that irreducible?
-Eli
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