<html xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:st1="urn:schemas-microsoft-com:office:smarttags" xmlns="http://www.w3.org/TR/REC-html40"
xmlns:ns13="urn:schemas-microsoft-com:office:smarttags">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 11 (filtered medium)">
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="address"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="City"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="place"/>
<!--[if !mso]>
<style>
st1\:*{behavior:url(#default#ieooui) }
</style>
<![endif]-->
<style>
<!--
/* Font Definitions */
@font-face
{font-family:"MS Mincho";
panose-1:2 2 6 9 4 2 5 8 3 4;}
@font-face
{font-family:"\@MS Mincho";
panose-1:2 2 6 9 4 2 5 8 3 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'>I’ve ran across an issue in BranchFolding.cpp where it
is incorrectly folding a branch to the wrong fallthrough location. This is in
LLVM 2.4 and seems to be in 2.5 also.<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 code in question is:<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 color=blue
face="Courier New"><span style='font-size:10.0pt;font-family:"Courier New";
color:blue'>void</span></font><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'>
BranchFolder::OptimizeBlock(MachineBasicBlock *MBB) {<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'>
MachineFunction::iterator FallThrough = MBB;<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'> ++FallThrough;<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'> <o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'> <font color=green><span
style='color:green'>// If this block is empty, make everyone use its
fall-through, not the block<o:p></o:p></span></font></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'> <font color=green><span
style='color:green'>// explicitly. Landing pads should not do this since
the landing-pad table<o:p></o:p></span></font></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'> <font color=green><span
style='color:green'>// points to this block.<o:p></o:p></span></font></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'> <font color=blue><span
style='color:blue'>if</span></font> (MBB->empty() &&
!MBB->isLandingPad()) {<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'> <font
color=green><span style='color:green'>// Dead block? Leave for cleanup
later.<o:p></o:p></span></font></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'> <font
color=blue><span style='color:blue'>if</span></font> (MBB->pred_empty()) <font
color=blue><span style='color:blue'>return</span></font>;<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'> <o:p></o:p></span></font></p>
<p class=MsoNormal style='margin-top:12.0pt;text-autospace:none'><font size=2
face="Courier New"><span style='font-size:10.0pt;font-family:"Courier New"'>
<font color=blue><span style='color:blue'>if</span></font> (FallThrough ==
MBB->getParent()->end()) {<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'>
<font color=green><span style='color:green'>// TODO: Simplify preds to not
branch here if possible!<o:p></o:p></span></font></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'> } <font
color=blue><span style='color:blue'>else</span></font> {<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><b><font size=2
face="Courier New"><span style='font-size:10.0pt;font-family:"Courier New";
font-weight:bold'> <font color=green><span
style='color:green'>// Rewrite all predecessors of the old block to go to the
fallthrough<o:p></o:p></span></font></span></font></b></p>
<p class=MsoNormal style='text-autospace:none'><b><font size=2
face="Courier New"><span style='font-size:10.0pt;font-family:"Courier New";
font-weight:bold'> <font color=green><span
style='color:green'>// instead.<o:p></o:p></span></font></span></font></b></p>
<p class=MsoNormal style='text-autospace:none'><b><font size=2
face="Courier New"><span style='font-size:10.0pt;font-family:"Courier New";
font-weight:bold'> <font color=blue><span
style='color:blue'>while</span></font> (!MBB->pred_empty()) {<o:p></o:p></span></font></b></p>
<p class=MsoNormal style='text-autospace:none'><b><font size=2
face="Courier New"><span style='font-size:10.0pt;font-family:"Courier New";
font-weight:bold'> MachineBasicBlock
*Pred = *(MBB->pred_end()-1);<o:p></o:p></span></font></b></p>
<p class=MsoNormal style='text-autospace:none'><b><font size=2
face="Courier New"><span style='font-size:10.0pt;font-family:"Courier New";
font-weight:bold'>
Pred->ReplaceUsesOfBlockWith(MBB, FallThrough);<o:p></o:p></span></font></b></p>
<p class=MsoNormal style='text-autospace:none'><b><font size=2
face="Courier New"><span style='font-size:10.0pt;font-family:"Courier New";
font-weight:bold'> }<o:p></o:p></span></font></b></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'>
<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'>
<font color=green><span style='color:green'>// If MBB was the target of a jump
table, update jump tables to go to the<o:p></o:p></span></font></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'>
<font color=green><span style='color:green'>// fallthrough instead.<o:p></o:p></span></font></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'>
MBB->getParent()->getJumpTableInfo()-><o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'>
ReplaceMBBInJumpTables(MBB, FallThrough);<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'>
MadeChange = <font color=blue><span style='color:blue'>true</span></font>;<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'> }<o:p></o:p></span></font></p>
<p class=MsoNormal style='text-autospace:none'><font size=2 face="Courier New"><span
style='font-size:10.0pt;font-family:"Courier New"'> <font
color=blue><span style='color:blue'>return</span></font>;<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face="Courier New"><span style='font-size:10.0pt;
font-family:"Courier New"'> }<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face="Courier New"><span style='font-size:10.0pt;
font-family:"Courier New"'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face="Courier New"><span style='font-size:10.0pt;
font-family:"Courier New"'>The problem with this section of code is that
FallThrough is not guaranteed to be a successor of MBB or even a descendent of
MBB.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face="Courier New"><span style='font-size:10.0pt;
font-family:"Courier New"'>The bitcode I’ve attached is a case where
there are 5 basic blocks, where the first four end with conditional branches to
an early return, as specified with initial.dot. <o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face="Courier New"><span style='font-size:10.0pt;
font-family:"Courier New"'>TailMergeBlocks in
BranchFolding::runOnMachineFunction merges the 4 early return blocks to a
single basic block and numbers renumbers them, as specified with tailmerge.dot.</span></font><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'>When it runs optimize block on the if.end14 block, it enters
the above segment of code, removing it and replacing it with FallThrough, which
is NOT its successor block and links two blocks changing the structure of the
program as shown in Optimizeblock.dot.<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'>I’ve attached a possible solution as a p4diff as I don’t
have svn setup on this machine, but let me know of any comments about the
patch.<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'>All of the files are attached in bugzilla, #3616, </span></font><a
href="http://llvm.org/bugs/show_bug.cgi?id=3616">http://llvm.org/bugs/show_bug.cgi?id=3616</a><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'>Micah Villmow<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Systems Engineer<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Advanced Technology & Performance<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>Advanced Micro Devices Inc.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><ns13:Street w:insAuthor="Micah Villmow"
w:insDate="2009-02-18T16:50:00Z" w:endInsAuthor="Micah Villmow"
w:endInsDate="2009-02-18T16:50:00Z"><ns13:address w:insAuthor="Micah Villmow"
w:insDate="2009-02-18T16:50:00Z" w:endInsAuthor="Micah Villmow"
w:endInsDate="2009-02-18T16:50:00Z">S1-609 One AMD Place</ns13:address></ns13:Street></span></font><o:p></o:p></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><ns13:place w:insAuthor="Micah Villmow"
w:insDate="2009-02-18T16:50:00Z" w:endInsAuthor="Micah Villmow"
w:endInsDate="2009-02-18T16:50:00Z"><ns13:City w:insAuthor="Micah Villmow"
w:insDate="2009-02-18T16:50:00Z" w:endInsAuthor="Micah Villmow"
w:endInsDate="2009-02-18T16:50:00Z"><st1:City w:st="on"><st1:place w:st="on">Sunnyvale</st1:place></st1:City></ns13:City></ns13:place>,
CA. 94085</span></font><o:p></o:p></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'>P: 408-749-3966</span></font><o:p></o:p></p>
<p class=MsoNormal><font size=3 face="Times New Roman"><span style='font-size:
12.0pt'> </span></font><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=3 face="Times New Roman"><span style='font-size:
12.0pt'><o:p> </o:p></span></font></p>
</div>
</body>
</html>