set_intersect and Visual C compiler

Morten_Ofstad · October 12, 2004, 5:59pm

Hello,

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

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
   }
}

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? 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...

m.

clattner · October 12, 2004, 7:01pm

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

Jeff_Cohen · October 12, 2004, 6:47pm

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

Jeff_Cohen · October 12, 2004, 6:50pm

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

The compiler probably wants a typename before S1Ty::key_type...

Alkis_Evlogimenos · October 12, 2004, 6:53pm

This is a N log(M) algorithm. Why don't we use the set_intersection algorithm
which runs in N+M time?

clattner · October 12, 2004, 7:08pm

That seems fine as well. I don't have strong feelings about it either
way, so we'll use whatever works.

-Chris

clattner · October 12, 2004, 7:12pm

I would have no problem with that

-Chris

Patrick_Meredith · October 13, 2004, 7:53am

Here is my code, (GV is a GlobalVariable*):

GV = new GlobalVariable(AI->getType(), false, GlobalValue::InternalLinkage,
0, "temp_glob", &M);

I tell it to make it with internal linkage, but when I run the pass it makes
them external:

%temp_glob = external global [10 x int]* ; <[10 x int]**>
[#uses=2]
%temp_glob = external global [10 x float]* ; <[10 x float]**>
[#uses=2]

and of course I get the broken module error because they aren't external:
Global is external, but doesn't have external linkage!
[10 x int]** %temp_glob
Global is external, but doesn't have external linkage!
[10 x float]** %temp_glob

Anyone know what I am doing wrong?

Patrick_Meredith · October 13, 2004, 8:00am

Ahh, you have to initialize it to be Internal. Sorry for the pointless
post.

Paolo_Invernizzi · October 13, 2004, 8:12am

Both are working well on VC. Just tested.

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;
}

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
   }
}

Patrick_Meredith · October 13, 2004, 8:44am

Both are working well on VC. Just tested.

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;
}

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
   }
}

---
Paolo Invernizzi

But like Alkis said we should probably just use the stl set_intersection, it
runs in linear time instead of n*lg(n).

Vikram_Adve · October 13, 2004, 2:28pm

Either use it directly if possible, or otherwise use the better algorithm. It may not be possible because the code above works for STL containers other than sets.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.cs.uiuc.edu/

clattner · October 13, 2004, 3:22pm

It's not just a matter of dropping it in. Patches accepted to switch us
over though.

-Chris

clattner · October 13, 2004, 3:31pm

I applied this one, and also the SetVector patch:

http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20041011/019258.html
http://mail.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20041011/019259.html

Thanks guys!

-Chris