<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns="http://www.w3.org/TR/REC-html40">

<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 11 (filtered medium)">
<style>
<!--
 /* Font Definitions */
 @font-face
        {font-family:Consolas;
        panose-1:2 11 6 9 2 2 4 3 2 4;}
 /* Style Definitions */
 p.MsoNormal, li.MsoNormal, div.MsoNormal
        {margin:0in;
        margin-bottom:.0001pt;
        font-size:12.0pt;
        font-family:"Times New Roman";}
a:link, span.MsoHyperlink
        {color:blue;
        text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
        {color:purple;
        text-decoration:underline;}
span.EmailStyle17
        {mso-style-type:personal-compose;
        font-family:Arial;
        color:windowtext;}
@page Section1
        {size:8.5in 11.0in;
        margin:1.0in 1.25in 1.0in 1.25in;}
div.Section1
        {page:Section1;}
-->
</style>

</head>

<body lang=EN-US link=blue vlink=purple>

<div class=Section1>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Hola LLVMers,<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>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:<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal style='text-autospace:none'><font size=2 face=Consolas><span
style='font-size:10.0pt;font-family:Consolas'>  <font color=blue><span
style='color:blue'>struct</span></font> Idx2MBBCompare {<o:p></o:p></span></font></p>

<p class=MsoNormal style='text-autospace:none'><font size=2 face=Consolas><span
style='font-size:10.0pt;font-family:Consolas'>    <font
color=blue><span style='color:blue'>bool</span></font> <font color=blue><span
style='color:blue'>operator</span></font>()(<font color=blue><span
style='color:blue'>const</span></font> IdxMBBPair &LHS, <font color=blue><span
style='color:blue'>const</span></font> IdxMBBPair &RHS) <font color=blue><span
style='color:blue'>const</span></font> {<o:p></o:p></span></font></p>

<p class=MsoNormal style='text-autospace:none'><font size=2 face=Consolas><span
style='font-size:10.0pt;font-family:Consolas'>      <font
color=blue><span style='color:blue'>return</span></font> LHS.first <
RHS.first;<o:p></o:p></span></font></p>

<p class=MsoNormal style='text-autospace:none'><font size=2 face=Consolas><span
style='font-size:10.0pt;font-family:Consolas'>    }<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>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.<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>In LiveIntervals::runOnMachineFunction, the map is sorted
with this:<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal style='text-autospace:none'><font size=2 face=Consolas><span
style='font-size:10.0pt;font-family:Consolas'>  <font color=blue><span
style='color:blue'>std</span></font>::sort(Idx2MBBMap.begin(), Idx2MBBMap.<font
color=blue><span style='color:blue'>end</span></font>(), Idx2MBBCompare());<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Ok so far.<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Here is where the problem arises:<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal style='text-autospace:none'><font size=2 face=Consolas><span
style='font-size:10.0pt;font-family:Consolas'>    <font
color=blue><span style='color:blue'>std</span></font>::lower_bound(Idx2MBBMap.begin(),
Idx2MBBMap.<font color=blue><span style='color:blue'>end</span></font>(),
LR.start);<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>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.<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>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.<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>In our code we fixed this by ditching the Idx2MBBCompare
operator and just added:<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>+  inline bool operator<(const IdxMBBPair &LHS,
const IdxMBBPair &RHS) {<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>+    return (LHS.first < RHS.first);<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>+  }<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>The alternative is to make sure the Idx2MBBCompare is passed
into the appropriate places.<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>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.<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Thanks,<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Chuck.<o:p></o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>

</div>

</body>

</html>