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