<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><br><div><html>On Apr 2, 2008, at 9:32 AM, Chuck Rose III wrote:</html><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div lang="EN-US" link="blue" vlink="purple"><div class="Section1"><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; ">Hola LLVMers,<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; 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></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Consolas"><span style="font-size: 10pt; font-family: Consolas; "> <span class="Apple-converted-space"> </span><font color="blue"><span style="color: blue; ">struct</span></font><span class="Apple-converted-space"> </span>Idx2MBBCompare {<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Consolas"><span style="font-size: 10pt; font-family: Consolas; "> <span class="Apple-converted-space"> </span><font color="blue"><span style="color: blue; ">bool</span></font><span class="Apple-converted-space"> </span><font color="blue"><span style="color: blue; ">operator</span></font>()(<font color="blue"><span style="color: blue; ">const</span></font><span class="Apple-converted-space"> </span>IdxMBBPair &LHS,<span class="Apple-converted-space"> </span><font color="blue"><span style="color: blue; ">const</span></font><span class="Apple-converted-space"> </span>IdxMBBPair &RHS)<span class="Apple-converted-space"> </span><font color="blue"><span style="color: blue; ">const</span></font><span class="Apple-converted-space"> </span>{<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Consolas"><span style="font-size: 10pt; font-family: Consolas; "> <span class="Apple-converted-space"> </span><font color="blue"><span style="color: blue; ">return</span></font><span class="Apple-converted-space"> </span>LHS.first < RHS.first;<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Consolas"><span style="font-size: 10pt; font-family: Consolas; "> }<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; 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></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; ">In LiveIntervals::runOnMachineFunction, the map is sorted with this:<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Consolas"><span style="font-size: 10pt; font-family: Consolas; "> <span class="Apple-converted-space"> </span><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></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; ">Ok so far.<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; ">Here is where the problem arises:<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Consolas"><span style="font-size: 10pt; font-family: Consolas; "> <span class="Apple-converted-space"> </span><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></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; 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></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; 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></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; ">In our code we fixed this by ditching the Idx2MBBCompare operator and just added:<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; ">+ inline bool operator<(const IdxMBBPair &LHS, const IdxMBBPair &RHS) {<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; ">+ return (LHS.first < RHS.first);<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; ">+ }</span></font></div></div></div></span></blockquote><div><br></div>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!</div><div><br></div><div>Evan</div><div><br><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><div lang="EN-US" link="blue" vlink="purple"><div class="Section1"><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; ">The alternative is to make sure the Idx2MBBCompare is passed into the appropriate places.<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; 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></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; ">Thanks,<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; ">Chuck.<o:p></o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div><div style="margin-top: 0in; margin-right: 0in; margin-left: 0in; margin-bottom: 0.0001pt; font-size: 12pt; font-family: 'Times New Roman'; "><font size="2" face="Arial"><span style="font-size: 10pt; font-family: Arial; "><o:p> </o:p></span></font></div></div>_______________________________________________<br>LLVM Developers mailing list<br><a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a href="http://llvm.cs.uiuc.edu" style="color: blue; text-decoration: underline; ">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" style="color: blue; text-decoration: underline; ">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></div></span></blockquote></div><br></body></html>