[LLVMdev] Irreducible CFG from tail duplication

[Mark Leone]

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
>