<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:m="http://schemas.microsoft.com/office/2004/12/omml" 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 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:SimSun;
panose-1:2 1 6 0 3 1 1 1 1 1;}
@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;}
@font-face
{font-family:"\@SimSun";
panose-1:2 1 6 0 3 1 1 1 1 1;}
/* 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:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p
{mso-style-priority:99;
margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@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="#0563C1" vlink="#954F72"><div class=WordSection1><p class=MsoNormal>Hi all,<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>I have a simple test case like this<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>class H<o:p></o:p></p><p class=MsoNormal>{<o:p></o:p></p><p class=MsoNormal>public:<o:p></o:p></p><p class=MsoNormal> int a; <o:p></o:p></p><p class=MsoNormal> int b; <o:p></o:p></p><p class=MsoNormal> int c; <o:p></o:p></p><p class=MsoNormal>};<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>inline int operator < (H& A, H& B)<o:p></o:p></p><p class=MsoNormal>{<o:p></o:p></p><p class=MsoNormal> return (A.a < B.a) ? 1 :<o:p></o:p></p><p class=MsoNormal> (A.a > B.a) ? 0 :<o:p></o:p></p><p class=MsoNormal> (A.b < B.b) ? 1 :<o:p></o:p></p><p class=MsoNormal> (A.b > B.b) ? 0 :<o:p></o:p></p><p class=MsoNormal> A.c < B.c;<o:p></o:p></p><p class=MsoNormal>}<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>int s(H *h, int j)<o:p></o:p></p><p class=MsoNormal>{<o:p></o:p></p><p class=MsoNormal> if (h[j] < h[j+1]) <o:p></o:p></p><p class=MsoNormal> j+=2;<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> return j;<o:p></o:p></p><p class=MsoNormal>}<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>The generated assembly in AArch64 is like below. X86 assembly has similar problem.<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal><span style='color:#1F497D'>If(h0.a < h1.a) goto bb0<o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>if (h0.a > h1.a) goto bb1</span><span style='color:#212121'><o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>If(h0.b < h1.b) goto bb2</span><span style='color:#212121'><o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>if (h0.b > h1.b) goto bb3</span><span style='color:#212121'><o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>flag = (h0.c < h1.c)</span><span style='color:#212121'><o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>goto if_end </span><span style='color:#212121'><o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>bb0: Flag = 1; Goto if_end</span><span style='color:#212121'><o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>bb1: Flag = 0; Goto if_end</span><span style='color:#212121'><o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>bb2: Flag = 1; Goto if_end</span><span style='color:#212121'><o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>bb3: Flag = 0; Goto if_end</span><span style='color:#212121'><o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'>if_end: j = select flag, j+2, j</span><span style='color:#212121'><o:p></o:p></span></p><p class=MsoNormal><span style='color:#1F497D'><o:p> </o:p></span></p><p class=MsoNormal>The trivial basic blocks bb0 – bb3 can cause huge performance penalty if the comparison (h[j] < h[j+1]) is in a hot loop. The IR code of if_end is like this<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal> %cond = phi i1 [ false, … ], [ true, … ], [ false, … ], [ true, … ], [%flag, …]<o:p></o:p></p><p class=MsoNormal> %add = add i32 %j, 2<o:p></o:p></p><p class=MsoNormal> %j.add = select i1 %cond.i, i32 %j, i32 %add<o:p></o:p></p><p class=MsoNormal><o:p> </o:p></p><p class=MsoNormal>Every bool constant in the phi becomes a trivial basic block in the assembly. select is generated by <span style='color:black'>SpeculativelyExecuteBB() of simplifyCFG before function inlining and prevents jump-threading to further optimize the CFG. If I run the passes in the order of<o:p></o:p></span></p><p class=MsoNormal><span style='color:black'><o:p> </o:p></span></p><p><span style='font-family:"Calibri",sans-serif;color:black'>-inline -instcombine -jump-threading -simplifycfg<o:p></o:p></span></p><p class=MsoNormal><span style='color:black'><o:p> </o:p></span></p><p class=MsoNormal><span style='color:black'>then the problem is gone. instcombine can clean the code after inlining so that jump-threading can optimize the CFG.<o:p></o:p></span></p><p class=MsoNormal><span style='color:black'><o:p> </o:p></span></p><p class=MsoNormal><span style='color:black'>Please let me know if you have any advice to solve this problem.<o:p></o:p></span></p><p class=MsoNormal><span style='color:black'><o:p> </o:p></span></p><p class=MsoNormal><span style='color:black'>Thank you,<o:p></o:p></span></p><p class=MsoNormal><span style='color:black'><o:p> </o:p></span></p><p class=MsoNormal><span style='color:black'>Haicheng<o:p></o:p></span></p><p class=MsoNormal><o:p> </o:p></p></div></body></html>