IntervalPartition bug?

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

IntervalPartition.diff (1.42 KB)

log (1.76 KB)

log_good (1.86 KB)

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.

To be honest, this code is really old and has never been thoroughly tested. If you want to become the "owner" of it, I'll take any patches you want against it.

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.

Hrm, when you get something that looks right, let me know and I'll apply it :slight_smile:

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.

That does seem strange. If you would like to change/refactor this code, feel free.

-Chris

Okay. I've done first round of refactoring and currently writing some code of
mine that uses IntervalPartition which should uncover any remaining issues.
When done, I'll submit a patch.

Probably I should describe the approach I taken. The problem with current
Interval class is that it contains vector<BasicBlock*> and that
Successor/Predecessor lists also point to basic block. That make it rather
inconvenient to work with 2-nd and higher-order partitions -- I'd have to
manually recover contained intervals and well as interval successors.

Storing both BasicBlock and interval would lead to a messy interface. So, I've
decided to always store Intervals in Nodes, Successors and Predecessors.
The only place where BasicBlock remain is header block.

When partioning the function, we first create trivial "zero-order" partition,
where each interval has a single basic block. First order partition is then
created from zero-order partition and so on.

As a side effect of this design, the IntervalIterator no longer has to operate
on both Function and IntervalPartition and can be made non-template.

Any objections to the above approach?

- Volodya

Sounds great to me!

-Chris