[LLVMdev] set_intersect and Visual C compiler

[Chris Lattner]

On Tue, 12 Oct 2004, Morten Ofstad wrote:

> This is my first post on this mailing list, so bear with me... My name
> is Morten Ofstad and I work for Hue AS (www.hue.no), a company that
> makes 3D Visualization software. We are looking into using LLVM for JIT
> compiling shader programs, to replace our own (slow) VM. A requirement

Neat!

> for this is that we can compile LLVM in VS7.1, so I contacted Paolo
> Invernizzi to find the status of his effort and to help out. I have set
> up the build environment now, with help from Paolo and have started to
> work on fixing some of the problems.

Great, I'm glad we're all working together on this! :)

> One thing that the compiler absolutely does not understand is the
> definition of set_intersect in include/llvm/ADT/SetOperations.h, and I
> am having a hard time understanding it myself.
>
> template <template<class S1ElTy> class S1Ty, class ETy, class S2Ty>
> void set_intersect(S1Ty<ETy> &S1, const S2Ty &S2) {
>    for (typename S1Ty<ETy>::iterator I = S1.begin(); I != S1.end();) {
>      const ETy &E = *I;
>      ++I;
>      if (!S2.count(E)) S1.erase(E);   // Erase element if not in S2
>    }
> }

Okay, it's pretty simple.  Given two sets (e.g. std::set), it walks
through one of them.  For each element in the set it checks to see if the
other contains the element.  if not it removes it.

It's a bit complex because of the use of template template classes, but is
otherwise fairly simple.

> it's only used in two places:
>
> lib\Transforms\Scalar\LoopSimplify.cpp
> lib\Analysis\PostDominators.cpp
>
> both of which compile correctly if I replace it with the less generic
>
> template<class STy>
> void set_intersect(STy &S1, const STy &S2)
> {
>    for(STy::iterator I = S1.begin(); I != S1.end(); ++I) {
>      if (S2.count(*I) > 0) {
>        S1.erase(*I);
>      }
>    }
> }
>
> Since I'm not very familiar with template programming, can someone
> explain to me the difference between these two implementations?

There are two problems with this.  First, this invalidates the iterator
when you erase the element.  This can be fixed by writing it like this,
which I think is fine.  If it works for you, send a patch and I'll commit
it.

template<class STy>
void set_intersect(STy &S1, const STy &S2) {
  for(STy::iterator I = S1.begin(), E = S1.end(); I != E; )
    if (S2.count(*I))
      S1.erase(*I++);
    else
      ++I;
}


> I would like to keep the implementation as general as possible while
> still compiling under VS7.1, but I'm not that familiar with C++ template
> programming so I need a little help to understand better what is going
> on here...

I don't think there is any reason to use template templates here, and LLVM
does not use them heavily at all, so if the implementation above works,
lets use it. :)

-Chris

-- 
http://llvm.org/
http://nondot.org/sabre/