[LLVMdev] IntervalPartition bug?

[Vladimir Prus]

On Saturday 30 April 2005 07:30, Chris Lattner wrote:

> > 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 :)
>
> > 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.

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