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: