<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:"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:0cm;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;
mso-fareast-language:EN-US;}
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;}
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;
mso-fareast-language:EN-US;}
@page WordSection1
{size:612.0pt 792.0pt;
margin:70.85pt 70.85pt 70.85pt 70.85pt;}
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="PL" link="#0563C1" vlink="#954F72">
<div class="WordSection1">
<p class="MsoNormal">Hello,<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span lang="EN-US">I found one case where narrowing switch instructions transformation in InstCombine produces worse code.
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Let's suppose that I have such code:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">$ cat a.c <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">void foo();<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">void bar();<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">void zoo();<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">void my_func(unsigned int a) {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> unsigned char b = a & 0xF;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> switch (b) {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> case 0: foo(); break;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> case 1: bar(); break;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> case 2: foo(); break;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> case 3: foo(); break;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> case 4: foo(); break;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> case 5: bar(); break;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> case 6: foo(); break;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> case 7: foo(); break;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> case 8: bar(); break;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> case 9: foo(); break;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> case 10: foo(); break;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> default: zoo();<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> }<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">}<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Using recent clang:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal">$ clang -O3 -S -c a.c -o a.s<o:p></o:p></p>
<p class="MsoNormal"><span lang="EN-US">I have the following assembly in the beginning of my_func:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"># bad case<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> movl %edi, %eax<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> andb $15, %al<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> cmpb $10, %al<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> ja .LBB0_9 # jump to the default case<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> andl $15, %edi<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> jmpq *.LJTI0_0(,%rdi,8) # go to jump table<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">I found that if I disable switch shrinking like shown below:
<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">$ git diff<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">diff --git a/lib/Transforms/InstCombine/InstructionCombining.cpp b/lib/Transforms/InstCombine/InstructionCombining.cpp<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">index 5d5a9b2..3682b88 100644<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">--- a/lib/Transforms/InstCombine/InstructionCombining.cpp<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">+++ b/lib/Transforms/InstCombine/InstructionCombining.cpp<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">@@ -2429,6 +2429,8 @@ Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> return &SI;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> }<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">+ return nullptr;<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">+<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> KnownBits Known = computeKnownBits(Cond, 0, &SI);<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> unsigned LeadingKnownZeros = Known.countMinLeadingZeros();<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> unsigned LeadingKnownOnes = Known.countMinLeadingOnes();<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> <o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">I get better assembly (there is no additional MOV and AND instructions):<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"># good case<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> </span>andl $15, %edi<o:p></o:p></p>
<p class="MsoNormal"> cmpl $10, %edi<o:p></o:p></p>
<p class="MsoNormal"> ja .LBB0_9<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"> <span lang="EN-US">jmpq *.LJTI0_0(,%rdi,8)<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal"><span lang="EN-US">This transformation was introduced in the commit:<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">commit 4eb03123dfda2de88a84852834845678833c8c36<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Author: Akira Hatanaka <<a href="mailto:ahatanaka@apple.com">ahatanaka@apple.com</a>><o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">Date: Thu Oct 16 06:00:46 2014 +0000<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"> Reapply r219832 - InstCombine: Narrow switch instructions using known bits.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">From IR point of view, after the ‘opt –codegenprepare’ the difference is that in good case we have simple ‘and’ operation (all calculations are made in i32). In the bad case there is 'trunc' to i4 and then ‘zext’ to i8.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">During instruction selection we expand switch into a jump table. In the bad case we use 2 copies of the value that we are switching on. First is in i8 that we use to determine whether we should jump to default case. The
second is in i64, which we use for calculating address in the jump table. In the good case they were combined.<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US">But there is still one thing that I don’t understand. What is the bad case that this transformation (narrowing switch instructions) was supposed to fix, i.e. does this transformation still make sense?<o:p></o:p></span></p>
<p class="MsoNormal"><span lang="EN-US"><o:p> </o:p></span></p>
<p class="MsoNormal"><span lang="EN-US" style="mso-fareast-language:PL">Best regards,<br>
Denis Bakhvalov.<o:p></o:p></span></p>
<p class="MsoNormal"><o:p> </o:p></p>
</div>
</body>
</html>