<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:x="urn:schemas-microsoft-com:office:excel" xmlns:p="urn:schemas-microsoft-com:office:powerpoint" xmlns:a="urn:schemas-microsoft-com:office:access" xmlns:dt="uuid:C2F41010-65B3-11d1-A29F-00AA00C14882" xmlns:s="uuid:BDC6E3F0-6DA3-11d1-A2A3-00AA00C14882" xmlns:rs="urn:schemas-microsoft-com:rowset" xmlns:z="#RowsetSchema" xmlns:b="urn:schemas-microsoft-com:office:publisher" xmlns:ss="urn:schemas-microsoft-com:office:spreadsheet" xmlns:c="urn:schemas-microsoft-com:office:component:spreadsheet" xmlns:odc="urn:schemas-microsoft-com:office:odc" xmlns:oa="urn:schemas-microsoft-com:office:activation" xmlns:html="http://www.w3.org/TR/REC-html40" xmlns:q="http://schemas.xmlsoap.org/soap/envelope/" xmlns:rtc="http://microsoft.com/officenet/conferencing" xmlns:D="DAV:" xmlns:Repl="http://schemas.microsoft.com/repl/" xmlns:mt="http://schemas.microsoft.com/sharepoint/soap/meetings/" xmlns:x2="http://schemas.microsoft.com/office/excel/2003/xml" xmlns:ppda="http://www.passport.com/NameSpace.xsd" xmlns:ois="http://schemas.microsoft.com/sharepoint/soap/ois/" xmlns:dir="http://schemas.microsoft.com/sharepoint/soap/directory/" xmlns:ds="http://www.w3.org/2000/09/xmldsig#" xmlns:dsp="http://schemas.microsoft.com/sharepoint/dsp" xmlns:udc="http://schemas.microsoft.com/data/udc" xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:sub="http://schemas.microsoft.com/sharepoint/soap/2002/1/alerts/" xmlns:ec="http://www.w3.org/2001/04/xmlenc#" xmlns:sp="http://schemas.microsoft.com/sharepoint/" xmlns:sps="http://schemas.microsoft.com/sharepoint/soap/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:udcs="http://schemas.microsoft.com/data/udc/soap" xmlns:udcxf="http://schemas.microsoft.com/data/udc/xmlfile" xmlns:udcp2p="http://schemas.microsoft.com/data/udc/parttopart" xmlns:wf="http://schemas.microsoft.com/sharepoint/soap/workflow/" xmlns:dsss="http://schemas.microsoft.com/office/2006/digsig-setup" xmlns:dssi="http://schemas.microsoft.com/office/2006/digsig" xmlns:mdssi="http://schemas.openxmlformats.org/package/2006/digital-signature" xmlns:mver="http://schemas.openxmlformats.org/markup-compatibility/2006" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns:mrels="http://schemas.openxmlformats.org/package/2006/relationships" xmlns:spwp="http://microsoft.com/sharepoint/webpartpages" xmlns:ex12t="http://schemas.microsoft.com/exchange/services/2006/types" xmlns:ex12m="http://schemas.microsoft.com/exchange/services/2006/messages" xmlns:pptsl="http://schemas.microsoft.com/sharepoint/soap/SlideLibrary/" xmlns:spsl="http://microsoft.com/webservices/SharePointPortalServer/PublishedLinksService" xmlns:Z="urn:schemas-microsoft-com:" xmlns:st="" 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 12 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri","sans-serif";}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri","sans-serif";
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link=blue vlink=purple><div class=WordSection1><p class=MsoNormal>I have ran across a case where the function isIdenticalTo is return true for instructions that are not equivalent. The instructions in question are load/store instructions, and is causing a problem with MachineBranchFolding. The problem is this, I have two branches of a switch statement that are identical, except for the size of the store. Here is some cut-down LLVM-IR to showcase the issue:<o:p></o:p></p><p class=MsoNormal>switch.case: ; preds = %if.end<o:p></o:p></p><p class=MsoNormal> %tmp53 = extractelement <4 x i32> %format, i32 1 ; <i32> [#uses=1]<o:p></o:p></p><p class=MsoNormal> switch i32 %tmp53, label %if.then [<o:p></o:p></p><p class=MsoNormal> i32 1, label %switch.case55<o:p></o:p></p><p class=MsoNormal> i32 2, label %switch.case61<o:p></o:p></p><p class=MsoNormal> ]<o:p></o:p></p><p class=MsoNormal>switch.case55: ; preds = %switch.case<o:p></o:p></p><p class=MsoNormal> %arrayidx = getelementptr i8 addrspace(1)* %conv3, i32 %tmp22 ; <i8 addrspace(1)*> [#uses=1]<o:p></o:p></p><p class=MsoNormal> %tmp59 = extractelement <4 x i32> %9, i32 0 ; <i32> [#uses=1]<o:p></o:p></p><p class=MsoNormal> %conv60 = trunc i32 %tmp59 to i8 ; <i8> [#uses=1]<o:p></o:p></p><p class=MsoNormal> store i8 %conv60, i8 addrspace(1)* %arrayidx<o:p></o:p></p><p class=MsoNormal> ret void<o:p></o:p></p><p class=MsoNormal>switch.case61: ; preds = %switch.case<o:p></o:p></p><p class=MsoNormal> %arrayidx64 = getelementptr i16 addrspace(1)* %conv, i32 %tmp22 ; <i16 addrspace(1)*> [#uses=1]<o:p></o:p></p><p class=MsoNormal> %tmp66 = extractelement <4 x i32> %9, i32 0 ; <i32> [#uses=1]<o:p></o:p></p><p class=MsoNormal> %conv67 = trunc i32 %tmp66 to i16 ; <i16> [#uses=1]<o:p></o:p></p><p class=MsoNormal> store i16 %conv67, i16 addrspace(1)* %arrayidx64<o:p></o:p></p><p class=MsoNormal> ret void<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Notice how except for the sizes of the pointer, the sequence is the same. This translates into the following for my backend at the MI level.<o:p></o:p></p><p class=MsoNormal><span style='font-size:8.0pt'>BB#9: derived from LLVM BB %switch.case55<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> Live Ins: %R258 %R260 %R259<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> Predecessors according to CFG: BB#8<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> %R257<def> = CUSTOM_ADD_i32 %R260<kill>, %R258<kill><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> %R258<def> = VEXTRACT_v4i32 %R259<kill>, 1<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> GLOBALTRUNCSTORE_i32 %R258<kill>, %R257<kill>, 8; mem:ST1[%arrayidx]<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> RETURN<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'>BB#10: derived from LLVM BB %switch.case61<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> Live Ins: %R258 %R260 %R259<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> Predecessors according to CFG: BB#7<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> %R257<def> = LOADCONST_i32 1<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> %R257<def> = SHL_i32 %R258<kill>, %R257<kill><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> %R257<def> = CUSTOM_ADD_i32 %R260<kill>, %R257<kill><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> %R258<def> = VEXTRACT_v4i32 %R259<kill>, 1<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> GLOBALTRUNCSTORE_i32 %R258<kill>, %R257<kill>, 8; mem:ST2[%arrayidx64]<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'> RETURN<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:8.0pt'><o:p> </o:p></span></p><p class=MsoNormal>Notice how except for the memory operand size on the truncating store, the last three instructions in BB#7 is the same as BB#8. <o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Now looking at isIdenticalTo, I don't see any checks on the memory size. Since I don't encode this information in the instruction, because it is encoded in the memory object, two different instructions can be considered identical for different memory sizes. I believe this is incorrect.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Here is my proposed patch for the issue:<o:p></o:p></p><p class=MsoNormal>Index: MachineInstr.cpp<o:p></o:p></p><p class=MsoNormal>===================================================================<o:p></o:p></p><p class=MsoNormal>--- MachineInstr.cpp (revision 122820)<o:p></o:p></p><p class=MsoNormal>+++ MachineInstr.cpp (working copy)<o:p></o:p></p><p class=MsoNormal>@@ -761,9 +761,23 @@<o:p></o:p></p><p class=MsoNormal> // If opcodes or number of operands are not the same then the two<o:p></o:p></p><p class=MsoNormal> // instructions are obviously not identical.<o:p></o:p></p><p class=MsoNormal> if (Other->getOpcode() != getOpcode() ||<o:p></o:p></p><p class=MsoNormal>- Other->getNumOperands() != getNumOperands())<o:p></o:p></p><p class=MsoNormal>+ Other->getNumOperands() != getNumOperands() ||<o:p></o:p></p><p class=MsoNormal>+ Other->memoperands_empty() != memoperands_empty())<o:p></o:p></p><p class=MsoNormal> return false;<o:p></o:p></p><p class=MsoNormal> <o:p></o:p></p><p class=MsoNormal>+ if (!memoperands_empty()) {<o:p></o:p></p><p class=MsoNormal>+ // If we have mem operands, make sure that the sizes of the memoperands for each<o:p></o:p></p><p class=MsoNormal>+ // MI are the same. The values can be different, so lets only check the sizes.<o:p></o:p></p><p class=MsoNormal>+ // If the sizes between one of the memoperands differ, then the instructions are<o:p></o:p></p><p class=MsoNormal>+ // not identical.<o:p></o:p></p><p class=MsoNormal>+ for (MachineInstr::mmo_iterator mb1 = memoperands_begin(), mb2 = Other->memoperands_begin()<o:p></o:p></p><p class=MsoNormal>+ me = memoperands_end(); mb1 != me; ++mb1, ++mb2) {<o:p></o:p></p><p class=MsoNormal>+ if (mb1->getSize() != mb2->getSize() || <o:p></o:p></p><p class=MsoNormal>+ mb1->getFlags() != mb2->getFlags() ||<o:p></o:p></p><p class=MsoNormal>+ mb1->getOffset() != mb2->getOffset()) {<o:p></o:p></p><p class=MsoNormal>+ return false;<o:p></o:p></p><p class=MsoNormal>+ }<o:p></o:p></p><p class=MsoNormal>+ }<o:p></o:p></p><p class=MsoNormal>+ }<o:p></o:p></p><p class=MsoNormal>+<o:p></o:p></p><p class=MsoNormal> // Check operands to make sure they match.<o:p></o:p></p><p class=MsoNormal> for (unsigned i = 0, e = getNumOperands(); i != e; ++i) {<o:p></o:p></p><p class=MsoNormal> const MachineOperand &MO = getOperand(i);<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>So, my question is, should isIdenticalTo take the memoperands into account? Is my patch correct? I almost feel like isIdenticalTo needs to be added to MachineMemOperand class.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Thoughts?<o:p></o:p></p><p class=MsoNormal>Micah<o:p></o:p></p></div></body></html>