Should repetitive basic blocks be removed in the results of LoopBase::getExitBlocks()?

Hi, all. I’m using void LoopBase::getExitBlocks (SmallVectorImpl< BlockT * > &ExitBlocks) const to get all
exit blocks for a loop. The problem I find with this API is that it returns repetitive basic blocks in certain
situations. Should repetitive basic blocks be removed?

I have an example to show the problem. Following is the source code and the CFG is enclosed.

int main()
{
int i = rand()%10;

while ( i < 20 )
{
i++;
if ( i == 5)
return 21;
if ( i == 9)
continue;
else if ( i == 10)
break;
}
return i;
}

If you use getExitBlocks() to get the exit basic blocks for the loop, the block “10” will show up twice in the
results.

Xiaoming

test_cfg.pdf (3.92 KB)

Users generally expect a unique set of exit blocks, but don’t make any strong assumption. The worst that can happen is missed optimization or redundant analysis. In most cases, the loop is in LoopSimplifyForm, so it’s probably not a problem in practice.

-Andy

Another thing I should mention. The iteration order of ExitBlocks is important. In llvm, generating unique sets is a pain because values are not numbered and iteration order needs to be reproducible. We would need to keep a SmallPtrSet for membership checking while populating the result vector.

-Andy

hi,

Users generally expect a unique set of exit blocks, but don't make any
strong assumption. The worst that can happen is missed optimization or
redundant analysis. In most cases, the loop is in LoopSimplifyForm, so it's
probably not a problem in practice.

Another thing I should mention. The iteration order of ExitBlocks is
important. In llvm, generating unique sets is a pain because values are not
numbered and iteration order needs to be reproducible. We would need to keep
a SmallPtrSet for membership checking while populating the result vector.

What about use the SetVector[1] as container? As its comment say:

This adapter class provides a way to keep a set of things that also
has the property of a deterministic iteration order. The order of
iteration is the order of insertion.

best regards
ether
[1]http://www.llvm.org/doxygen/classllvm_1_1SetVector.html

Sure, you can wrap the SmallPtrSet within the SetVector. You need to change the API then.
-Andy