[LLVMdev] IntervalPartition bug?

[Vladimir Prus]

Hi,
it looks like the IntervalPartition does not work as expected when constructed 
from another interval partition.

Say, I have built an interval partition from function, and the first interval 
has two basic blocks. When I create second order partition and print all 
intervals, the second basic block of the function is not seen anywhere.

Here's what's going on in IntervalIterator.h:

  bool ProcessInterval(NodeTy *Node) {
    BasicBlock *Header = getNodeHeader(Node);
    if (Visited.count(Header)) return false;

    Interval *Int = new Interval(Header);
    Visited.insert(Header);   // The header has now been visited!

Here's NodeTy is a first order interval and can contain several basic blocks, 
but we add only the first one.

I attach the patch which tries to fixes that. Also, for convenience, there's 
output of 2-order interval on some test case. 'log' is before the change and 
'log_good' is after the change.

I must admit the change does not look 100% right to me yet.

On a related note, I'm a bit surprised that 2-nd order partition consists of 
basic blocks. I'd more expect that it consisted of Interval's. As it stands, 
it's not easy to tell which 1-st order invervals are contained in a given 
2-nd order interval.

- Volodya


-------------- next part --------------
A non-text attachment was scrubbed...
Name: IntervalPartition.diff
Type: text/x-diff
Size: 1456 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20050429/39646682/attachment.diff>
-------------- next part --------------
2-order partition
-------------------------------------------------------------
Interval Contents:

entry:
	load int* %i		; <int>:0 [#uses=1]
	load int* %j		; <int>:1 [#uses=1]
	%tmp.24 = setgt int %k, 0		; <bool> [#uses=1]
	%tmp.35 = load int* %i		; <int> [#uses=2]
	br bool %tmp.24, label %no_exit.preheader, label %loopexit


no_exit:		; preds = %no_exit, %no_exit.preheader
	%indvar = phi uint [ 0, %no_exit.preheader ], [ %indvar.next, %no_exit ]		; <uint> [#uses=2]
	%j.tmp.1 = phi int [ %j.promoted, %no_exit.preheader ], [ %tmp.8, %no_exit ]		; <int> [#uses=1]
	%tmp.3.0 = phi int [ %tmp.5, %no_exit ], [ %tmp.35, %no_exit.preheader ]		; <int> [#uses=1]
	%c.0.0 = cast uint %indvar to int		; <int> [#uses=1]
	%tmp.5 = add int %tmp.3.0, %k		; <int> [#uses=3]
	%tmp.10 = shl int %j.tmp.1, ubyte 1		; <int> [#uses=1]
	%tmp.8 = add int %tmp.10, %k		; <int> [#uses=2]
	%inc = add int %c.0.0, 1		; <int> [#uses=1]
	%tmp.2 = setlt int %inc, %k		; <bool> [#uses=1]
	%indvar.next = add uint %indvar, 1		; <uint> [#uses=1]
	br bool %tmp.2, label %no_exit, label %loopexit.loopexit


loopexit.loopexit:		; preds = %no_exit
	store int %tmp.5, int* %i
	load int* %i		; <int>:2 [#uses=1]
	store int %tmp.8, int* %j
	load int* %j		; <int>:3 [#uses=1]
	br label %loopexit


loopexit:		; preds = %loopexit.loopexit, %entry
	%j__local.0 = phi int [ %3, %loopexit.loopexit ], [ %1, %entry ]		; <int> [#uses=1]
	%i__local.0 = phi int [ %2, %loopexit.loopexit ], [ %0, %entry ]		; <int> [#uses=1]
	%tmp.3.1 = phi int [ %tmp.35, %entry ], [ %tmp.5, %loopexit.loopexit ]		; <int> [#uses=1]
	store int %j__local.0, int* %j
	store int %i__local.0, int* %i
	%tmp.13 = load int* %j		; <int> [#uses=1]
	%tmp.14 = add int %tmp.3.1, %tmp.13		; <int> [#uses=1]
	ret int %tmp.14

Interval Predecessors:
Interval Successors:
-------------- next part --------------
2-order partition
-------------------------------------------------------------
Interval Contents:

entry:
	load int* %i		; <int>:0 [#uses=1]
	load int* %j		; <int>:1 [#uses=1]
	%tmp.24 = setgt int %k, 0		; <bool> [#uses=1]
	%tmp.35 = load int* %i		; <int> [#uses=2]
	br bool %tmp.24, label %no_exit.preheader, label %loopexit


no_exit.preheader:		; preds = %entry
	%j.promoted = load int* %j		; <int> [#uses=1]
	br label %no_exit


no_exit:		; preds = %no_exit, %no_exit.preheader
	%indvar = phi uint [ 0, %no_exit.preheader ], [ %indvar.next, %no_exit ]		; <uint> [#uses=2]
	%j.tmp.1 = phi int [ %j.promoted, %no_exit.preheader ], [ %tmp.8, %no_exit ]		; <int> [#uses=1]
	%tmp.3.0 = phi int [ %tmp.5, %no_exit ], [ %tmp.35, %no_exit.preheader ]		; <int> [#uses=1]
	%c.0.0 = cast uint %indvar to int		; <int> [#uses=1]
	%tmp.5 = add int %tmp.3.0, %k		; <int> [#uses=3]
	%tmp.10 = shl int %j.tmp.1, ubyte 1		; <int> [#uses=1]
	%tmp.8 = add int %tmp.10, %k		; <int> [#uses=2]
	%inc = add int %c.0.0, 1		; <int> [#uses=1]
	%tmp.2 = setlt int %inc, %k		; <bool> [#uses=1]
	%indvar.next = add uint %indvar, 1		; <uint> [#uses=1]
	br bool %tmp.2, label %no_exit, label %loopexit.loopexit


loopexit.loopexit:		; preds = %no_exit
	store int %tmp.5, int* %i
	load int* %i		; <int>:2 [#uses=1]
	store int %tmp.8, int* %j
	load int* %j		; <int>:3 [#uses=1]
	br label %loopexit


loopexit:		; preds = %loopexit.loopexit, %entry
	%j__local.0 = phi int [ %3, %loopexit.loopexit ], [ %1, %entry ]		; <int> [#uses=1]
	%i__local.0 = phi int [ %2, %loopexit.loopexit ], [ %0, %entry ]		; <int> [#uses=1]
	%tmp.3.1 = phi int [ %tmp.35, %entry ], [ %tmp.5, %loopexit.loopexit ]		; <int> [#uses=1]
	store int %j__local.0, int* %j
	store int %i__local.0, int* %i
	%tmp.13 = load int* %j		; <int> [#uses=1]
	%tmp.14 = add int %tmp.3.1, %tmp.13		; <int> [#uses=1]
	ret int %tmp.14

Interval Predecessors:
Interval Successors: