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.
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. :) > > -ChrisI 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...
On Tuesday 12 October 2004 14:01, Chris Lattner wrote:> 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.This is a N log(M) algorithm. Why don't we use the set_intersection algorithm which runs in N+M time? -- Alkis
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 requirementNeat!> 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/