llvm dev - Apr 2008 - [LLVMdev] Comparison mismatch causes assert using VStudio STL

Hola LLVMers,

 

We saw a problem with some code in LiveIntervalAnalysis.h/.c which we've
fixed locally.  We'd like to get a patch to the mainline and want to
know how you'd like it fixed.  A couple of things come together to cause
the problem:

 

  struct Idx2MBBCompare {

    bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS) const
{

      return LHS.first < RHS.first;

    }

 

This comparator function compares the first elements of the IdxMBBPair.
This is in contrast to the default comparator for std::pairs, which
compares the second element if the first elements are equal before
making a final decision.  In this case, it makes a lot of sense given
that the second in the pair is just a pointer.

 

In LiveIntervals::runOnMachineFunction, the map is sorted with this:

 

  std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());

 

Ok so far.

 

Here is where the problem arises:

 

    std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start);

 

By omitting the explicit comparator operator, the default is used which
looks at second.  Not a huge problem in general, since you don't really
care that the pointers are sorted.

 

Visual Studio's debug STL, however, is quite the stickler.  Debug
lower_bound checks to see that the container is sorted and since
lower_bound isn't given a comparison function, it uses the default one
which isn't the one used to sort the container, and (boom!) it asserts
if the memory stars aren't aligned properly.

 

In our code we fixed this by ditching the Idx2MBBCompare operator and
just added:

 

+  inline bool operator<(const IdxMBBPair &LHS, const IdxMBBPair
&RHS) {

+    return (LHS.first < RHS.first);

+  }

 

The alternative is to make sure the Idx2MBBCompare is passed into the
appropriate places.

 

How would you like this to be fixed?  I can tool it up, but I don't want
to step on someone else's feet.

 

Thanks,

Chuck.

 

 

 

 

 

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080402/cb4b814f/attachment.html>

Hello llvm dev peeps

I would like to use an LLVMBuilder pointer as a base pointer to 
reference either an LLVMBuilder or an LLVMFoldingBuilder. As the methods 
in the Folding builder have the same names as the base class, I thought 
about submitting a patch whereby the base class methods would become 
virtual. However, the base class methods return specific types while the 
Folding builder, for good reason, return more general Value* types.

Would it be reasonable for me to submit a patch whereby the LLVMBuilder 
methods also return the general Value* type and the LLVMFoldingBuilder 
methods become virtual overrides of the base class methods?

Users (such as myself) could then decide at runtime which type of 
builder they wish to use.

Another option that was discussed in #llvm is to nuke LLVMBuilder and 
rename LLVMFoldingBuilder to LLVMBuilder. If this was the case, I'd 
argue for a flag in the Builder that could retain the old non-folding 
functionality for debugging purposes.

Your thoughts please?

On Apr 2, 2008, at 9:32 AM, Chuck Rose III wrote:
> Hola LLVMers,
>
> We saw a problem with some code in LiveIntervalAnalysis.h/.c which  
> we’ve fixed locally.  We’d like to get a patch to the mainline and  
> want to know how you’d like it fixed.  A couple of things come  
> together to cause the problem:
>
>   struct Idx2MBBCompare {
>     bool operator()(const IdxMBBPair &LHS, const IdxMBBPair &RHS)  
> const {
>       return LHS.first < RHS.first;
>     }
>
> This comparator function compares the first elements of the  
> IdxMBBPair.  This is in contrast to the default comparator for  
> std::pairs, which compares the second element if the first elements  
> are equal before making a final decision.  In this case, it makes a  
> lot of sense given that the second in the pair is just a pointer.
>
> In LiveIntervals::runOnMachineFunction, the map is sorted with this:
>
>   std::sort(Idx2MBBMap.begin(), Idx2MBBMap.end(), Idx2MBBCompare());
>
> Ok so far.
>
> Here is where the problem arises:
>
>     std::lower_bound(Idx2MBBMap.begin(), Idx2MBBMap.end(), LR.start);
>
> By omitting the explicit comparator operator, the default is used  
> which looks at second.  Not a huge problem in general, since you  
> don’t really care that the pointers are sorted.
>
> Visual Studio’s debug STL, however, is quite the stickler.  Debug  
> lower_bound checks to see that the container is sorted and since  
> lower_bound isn’t given a comparison function, it uses the default  
> one which isn’t the one used to sort the container, and (boom!) it  
> asserts if the memory stars aren’t aligned properly.
>
> In our code we fixed this by ditching the Idx2MBBCompare operator  
> and just added:
>
> +  inline bool operator<(const IdxMBBPair &LHS, const IdxMBBPair  
> &RHS) {
> +    return (LHS.first < RHS.first);
> +  }
I think this is right fix for it. Any chance you can do some sanity  
testing? Please commit after you have run it though MultiSource  
portion of llvm test suite. Thanks!

Evan
>
> The alternative is to make sure the Idx2MBBCompare is passed into  
> the appropriate places.
>
> How would you like this to be fixed?  I can tool it up, but I don’t  
> want to step on someone else’s feet.
>
> Thanks,
> Chuck.
>
>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080402/54b39fbd/attachment.html>

Hi,
> Another option that was discussed in #llvm is to nuke LLVMBuilder and 
> rename LLVMFoldingBuilder to LLVMBuilder. If this was the case, I'd 
> argue for a flag in the Builder that could retain the old non-folding 
> functionality for debugging purposes.
this plan sounds good to me.  However it's not clear to me how useful a
debug flag would really be.

Ciao,

Duncan.

On Apr 2, 2008, at 9:54 AM, Dominic Hamon wrote:
> Hello llvm dev peeps
>
> I would like to use an LLVMBuilder pointer as a base pointer to
> reference either an LLVMBuilder or an LLVMFoldingBuilder. As the  
> methods
> in the Folding builder have the same names as the base class, I  
> thought
> about submitting a patch whereby the base class methods would become
> virtual. However, the base class methods return specific types while  
> the
> Folding builder, for good reason, return more general Value* types.
>
> Would it be reasonable for me to submit a patch whereby the  
> LLVMBuilder
> methods also return the general Value* type and the LLVMFoldingBuilder
> methods become virtual overrides of the base class methods?
No, please don't do this.  The idea of llvmbuilder is that it is a  
"free" wrapper around the other existing API calls.  Making the  
methods virtual would make them much more expensive.
> Users (such as myself) could then decide at runtime which type of
> builder they wish to use.
Why do you want this?
> Another option that was discussed in #llvm is to nuke LLVMBuilder and
> rename LLVMFoldingBuilder to LLVMBuilder.
I'd strongly prefer this.  The non-folding builder is not very useful  
for anything, and anyone who wants unfolded instructions can call the  
instruction ctors directly.
> If this was the case, I'd
> argue for a flag in the Builder that could retain the old non-folding
> functionality for debugging purposes.
Why?

-Chris