Incorrect post-dominators with multiple returns

[sunfishcode]

Bugzilla Link	1098
Resolution	FIXED
Resolved on	May 04, 2008 17:55
Version	trunk
OS	All
CC	@asl,@nlewycky

Extended Description

In some test cases with multiple return statements, the post-dominator passes
return incorrect information.

For this test case:

define void %foo(bool %x) {
entry:
br bool %x, label %bb1, label %bb0
bb0:
ret void
bb1:
br label %bb2
bb2:
ret void
}

The `entry' block's immediate post-dominator should be the exit node, but the
immediate post-dominator pass's print() output is

Immediate Dominator For Basic Block: %entry is: %bb0
Immediate Dominator For Basic Block: %bb0 is: <>
Immediate Dominator For Basic Block: %bb1 is: %bb2
Immediate Dominator For Basic Block: %bb2 is: <>

The post-dominator tree and post-dominator set passes exhibit similar
behavior.

[lattner]

Interesting. This is probably related to Bug 1069, but is a much nicer testcase.

Devang, can you see if Nate's patch (r1.55 to postdominators.cpp) to rewrite post-dom introduced this? If
so we can choose to either revert that (ugly) or figure out how to fix it. Are you very familiar with the
Lengauer and Tarjan dominators algorithm?

-Chris

[lattner]

*** Bug #1441 has been marked as a duplicate of this bug. ***

[llvmbot]

I am testing this patch.
I am testing this patch.

[llvmbot]

This fixes the test case. And it does not cause any disruption in MultiSource/Benchmarks test run.
However there is better fix that I will try today.

[llvmbot]

2nd approach
This patch does its job but causes failure in ADCE. When postdominator is not
found for a node, ADCE tries to convert its termnator to a return.

See ADCE.cpp:399

While optimizing hexxagon, assertion fails inside RemoveSuccessor() because
terminator is switch stmt.

[lattner]

owen is looking at merging dom and pdom, maybe this will magically be resolved :)

[lattner]

Owen, is this the issue you found in postdom?

[llvmbot]

Yes, this looks like exactly the same issue I was running into. Unfortunately, merging the two didn't help at all.

[lattner]

Here is an upgraded testcase:
define void @​foo(i1 %x) {
entry:
br i1 %x, label %bb1, label %bb0
bb0: ; preds = %entry
ret void
bb1: ; preds = %entry
br label %bb2
bb2: ; preds = %bb1
ret void
}

Owen, when I try to verify this, I get:

$ llvm-as | opt -postdomtree -analyze
...
Pass::print not implemented for pass: 'Post-Dominator Tree Construction'!

Please fix :)

[llvmbot]

Test case results after commit 49768:
Printing analysis 'Post-Dominator Tree Construction' for function 'foo':
=============================--------------------------------
Inorder PostDominator Tree:
[1] <> {4294967295,4294967295}
[2] %bb0 {4294967295,4294967295}
[2] %bb2 {4294967295,4294967295}
[3] %bb1 {4294967295,4294967295}

Unfortunately %entry has now disappeared completely, leading to the following postdomfrontier results:
Printing analysis 'Post-Dominance Frontier Construction' for function 'foo':
DomFrontier for BB <> is:
DomFrontier for BB %bb0 is:
DomFrontier for BB %bb1 is:
DomFrontier for BB %bb2 is:

[llvmbot]

Fixed in r50628.