[LLVMdev] set_intersect and Visual C compiler

[Jeff Cohen]

On Tue, 12 Oct 2004 14:01:21 -0500 (CDT)
Chris Lattner <sabre at nondot.org> wrote:

> 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

I think a better version is:

template <class S1Ty, class S2Ty>
void set_intersect(S1Ty &S1, const S2Ty &S2) {
   for (typename S1Ty::iterator I = S1.begin(); I != S1.end();) {
     const S1Ty::key_type &E = *I;
     ++I;
     if (!S2.count(E)) S1.erase(E);   // Erase element if not in S2
   }
}

This eliminates the use of a template templates while keeping the same
flexibility.  Not that I actually to compile this...