[LLVMdev] findNearestCommonDominator

[Tobias Grosser]

On 03/07/2010 10:33 PM, Jochen Wilhelmy wrote:
> Hi!

Hi Jochen,

> I have seen that findNearestCommonDominator has been added
> to class PostDominatorTree, maybe on my request.
>
> Now there is the following problem:
> in class DominatorTreeBase  there is an assert in findNearestCommonDominator
> that asserts if the tree is not a PostDominator tree:
>
>     assert (!this->isPostDominator()
>              &&  "This is not implemented for post dominators");
>      assert (A->getParent() == B->getParent()
>              &&  "Two blocks are not in same function");
>
>      // If either A or B is a entry block then it is nearest common
> dominator.
>      NodeT&Entry  = A->getParent()->front();
>      if (A ==&Entry || B ==&Entry)
>        return&Entry;
>
>
>
>
> When commenting out the assert it seems to work. Perhaps it has to be
> changed
> that the check for entry block (which seems to be an optimization)
> is only done for DominatorTree:
>
> if (!this->isPostDominator())
> {
>    // If either A or B is a entry block then it is nearest common dominator.
>      NodeT&Entry  = A->getParent()->front();
>      if (A ==&Entry || B ==&Entry)
>        return&Entry;
> }

Yes, you are right.

I added it, as it looked like a trivial change. I should have verified 
this better, but did not take enough time as this code path was not used 
at the moment. I will do better next time! ;-)

Your analysis seems to be correct. There is an optimization in 
findNearestCommonDominator() that does not work for PostDominatorTree.

I added a patch to not use it  for the PostDominatorTree (as proposed by 
you). Can this patch be committed to trunk and the release branch to fix 
the bug I introduced?

It passes all LLVM tests on amd64.

---------------------------------------------------------------------
findNearestCommonDominator fixed for PostDominators

Disable an optimization for the DominatorTree, to enable
findNearestCommonDominator to also work on a PostDominatorTree.
---------------------------------------------------------------------

I will investigate, if this optimization is really necessary. Maybe we 
can simplify the code by removing it completely.

Tobi
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: 0001-findNearestCommonDominator-works-for-PostDominator.patch
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20100308/0fc5db59/attachment.ksh>