ConstantRange in PR1255

Hi Duncan. I have strange problems with you mailbox, my posts are lost sometimes on this way.
I just want to duplicate answer on your question in this thread:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120305/138785.html

ConstantRange has a little bit another purposes. It is not a classical range. Yes it has Lower and Upper, but "sub" and "add" operations are differs from "difference" and "union" set operations. But it is still possible to replace Range class with the ConstantRange, though we need to implement classical set operations to do it.

-Stepan.

Hi Stepan,

Hi Duncan. I have strange problems with you mailbox, my posts are lost sometimes on this way.

OK, sorry about that. Do you have any details?

I just want to duplicate answer on your question in this thread:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20120305/138785.html

ConstantRange has a little bit another purposes. It is not a classical range.

How do you mean? It looks like a classical range to me!

  Yes it has Lower and Upper, but "sub" and "add" operations are differs from "difference" and "union" set operations.

It has intersectWith and unionWith, so I'm not sure what you mean here.
There is also "inverse" for forming the complement.

  But it is still possible to replace Range class with the ConstantRange, though we need to implement classical set operations to do it.

The basic set operations are already implemented as I mentioned above, though
you might want to add some convenience methods like symmetric difference.

Ciao, Duncan.

Hi, Duncan.

unionWith result is differs from set union, since it produces single set always while set operations may produce two sets.

E.g.:
For ranges
[1, 5) and [10,15)
unionWith produces [1,15), while set union should just keep these sets without changing, probably with indication that sets are not intersected. Implementation of set union is simple though.

The "symmetric difference" implementation is little bit more complex.
For two sets
[1,15) and [7,12)
symmetric difference is pair of ranges:
[1,7) and [12,15)

I propose to implement these methods in ConstantRange (I can do it).

-Stepan.

Hi Stepan,

unionWith result is differs from set union, since it produces single set always
while set operations may produce two sets.

this is true, but that's inevitable if the result is to be a single
ConstantRange. You can of course define methods that returns a pair
of ConstantRanges and does what you want. But why do you need these
methods anyway? A "switch" is just going to be a (probably ordered)
list of disjoint ranges. Where do set operations come in?

Ciao, Duncan.

Well... each case is represented as pair<BB, vector<Range> >. Right?
We need "union" for optimal case building. And we need support "difference" if we decided that some ranges or numbers in case will never used (in some optimization passes it happens sometimes).

-Stepan

Hi Stepan,

Well... each case is represented as pair<BB, vector<Range> >. Right?

well, you could also use vector<pair<BB, Range>>.

We need "union" for optimal case building.

In such cases you only need union when the union will be an interval, rather
than two intervals, right? In which case unionWith suffices.

  And we need support "difference" if we decided that some ranges or numbers in case will never used (in some optimization passes it happens sometimes).

OK.

Ciao, Duncan.

Hi Stepan,

Well... each case is represented as pair<BB, vector<Range> >. Right?

after thinking about this some more I think you are right to not use
ConstantRange, and instead to build your own set abstraction.

Ciao, Duncan.

Hmmm... why?
Duncan Sands wrote:

Hi Stepan,

Hmmm... why?

because you basically want pairs (set, destination) where set could be a
arbitrary set of integers. As in practice these sets are a union of a
small number of intervals, the set abstraction should efficiently represent
unions of intervals, but that's more of an optimization than anything else.
Probably for the needs of switch lowering you will need to expose the
underlying intervals, but the basic abstraction is a set. You could build it
on top of ConstantRange if you like, but as most of ConstantRange is not very
relevant, you could also quite reasonably build it some other way. In fact I
was assuming that that's what you had in mind...

Ciao, Duncan.

Hi Duncan,

Yes. ConstantRange has a little bit different purposes instead.
OK. I'll build another Range class then.

-Stepan.
Duncan Sands wrote: