<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jun 30, 2016 at 10:02 PM, vivek pandya <span dir="ltr"><<a href="mailto:vivekvpandya@gmail.com" target="_blank">vivekvpandya@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">One more interesting thing I have noticed is as following :<div><br></div><div>In sqlite3 code consider 3 functions namely sqlite3Update, sqlite3Select and sqlite3Where begin sqlite3WhereBegin is called by both functions sqlite3Update and sqlite3Select but according to CallGraphSCC sqlite3Update is codegen before in that case during RegMask propagation phase default regmask is used for call site of sqlite3WhereBegin and later sqlite3WhereBegin is optimized not to save callee saved registers this should obviously not happen.</div><div><br></div><div>Here is assembly code that is printed with lldb dis command on run time failure and after careful observation I have identified one bug:</div><div>...</div><div><div> 0x10002d8ff <+1855>: movl -0x74(%rbp), %r13d</div><div> 0x10002d903 <+1859>: movq -0x30(%rbp), %r12 ; this contains address of a structure</div><div> 0x10002d907 <+1863>: movq -0x38(%rbp), %r14</div><div> 0x10002d90b <+1867>: movq -0x58(%rbp), %r15</div><div> 0x10002d90f <+1871>: leaq -0x150(%rbp), %rdi</div><div> 0x10002d916 <+1878>: movq -0x50(%rbp), %rsi</div><div> 0x10002d91a <+1882>: callq 0x10001a940 ; sqlite3ExprResolveNames at sqlite3.c:47419 this function preserves callee saved regs</div><div> 0x10002d91f <+1887>: testl %eax, %eax</div><div> 0x10002d921 <+1889>: je 0x10002d92c ; <+1900> at sqlite3.c:66485</div><div> 0x10002d923 <+1891>: movq -0x70(%rbp), %rdx</div><div> 0x10002d927 <+1895>: jmp 0x10002d2b1 ; <+241> at sqlite3.c:66299</div><div> 0x10002d92c <+1900>: xorl %eax, %eax</div><div> 0x10002d92e <+1902>: movq %rax, -0xe0(%rbp)</div><div> 0x10002d935 <+1909>: xorl %ecx, %ecx</div><div> 0x10002d937 <+1911>: xorl %r8d, %r8d</div><div> 0x10002d93a <+1914>: movq %r14, %rdi</div><div> 0x10002d93d <+1917>: movq -0xd8(%rbp), %rsi</div><div> 0x10002d944 <+1924>: movq -0x50(%rbp), %rdx</div><div> 0x10002d948 <+1928>: callq 0x100030600 ; sqlite3WhereBegin at sqlite3.c:69859 this function will not save any callee saved regs and actual code uses R12</div><div> 0x10002d94d <+1933>: movq %rax, %r14</div><div> 0x10002d950 <+1936>: testq %r14, %r14</div><div> 0x10002d953 <+1939>: je 0x10002e0d3 ; <+3859> at sqlite3.c:66699</div><div> 0x10002d959 <+1945>: movq -0x48(%rbp), %rax</div><div> 0x10002d95d <+1949>: cmpb $0x0, 0x69(%rax)</div><div> 0x10002d961 <+1953>: movl $0xa, %eax</div><div> 0x10002d966 <+1958>: movl $0x26, %esi</div><div> 0x10002d96b <+1963>: cmovnel %eax, %esi</div><div> 0x10002d96e <+1966>: movq %r12, %rdi ; here value of R12 is clobbered so wrong address is passed as parameter and due to that while executing sqlite3VdbeAddOp2 bed memory access error is raised.</div><div> 0x10002d971 <+1969>: movq -0x68(%rbp), %rdx</div><div> 0x10002d975 <+1973>: movl %r13d, %ecx</div><div> 0x10002d978 <+1976>: callq 0x100019720 ; sqlite3VdbeAddOp2 at sqlite3.c:37297 </div><div>... </div><div><br></div><div>Here is lldb dis result for sqlite3VdbeAddOp3:</div><div> 0x100019500 <+0>: pushq %rbp</div><div> 0x100019501 <+1>: movq %rsp, %rbp</div><div> 0x100019504 <+4>: pushq %r15</div><div> 0x100019506 <+6>: pushq %r14</div><div> 0x100019508 <+8>: pushq %r13</div><div> 0x10001950a <+10>: pushq %r12</div><div> 0x10001950c <+12>: pushq %rbx</div><div> 0x10001950d <+13>: pushq %rax</div><div> 0x10001950e <+14>: movl %ecx, %r12d</div><div> 0x100019511 <+17>: movl %edx, %r13d</div><div> 0x100019514 <+20>: movl %esi, %r15d</div><div> 0x100019517 <+23>: movq %rdi, %rbx</div><div>-> 0x10001951a <+26>: movl 0x18(%rbx), %r14d <br></div></div><div><br></div><div>Please correct me if any thing is wrong and also please provide some help.</div></div></blockquote><div><br></div><div>The above explained bug is due to not excluding recursive functions recursive function related optimization. I have also confirm the same bug with one of other failing test case sphereflake.cpp here is explanation:</div><div><br></div><div>static node_t *create(node_t*n,const int lvl,int dist,v_t c,v_t d,double r) {</div><div><span class="" style="white-space:pre"> </span>n = 1 + new (n) node_t(sphere_t(c,2.*r),sphere_t(c,r), lvl > 1 ? dist : 1);</div><div><span class="" style="white-space:pre"> </span>if (lvl <= 1)</div><div><span class="" style="white-space:pre"> </span>return n; /*if not at the bottom, recurse a bit more*/</div><div><span class="" style="white-space:pre"> </span></div><div><span class="" style="white-space:pre"> </span>dist=std::max((dist-childs)/childs,1); const basis_t b(d); </div><div><span class="" style="white-space:pre"> </span>const double nr=r*1/3.,daL=2.*M_PI/6.,daU=2.*M_PI/3.; double a=0;</div><div><span class="" style="white-space:pre"> </span>for(int i=0;i<6;++i){ /*lower ring*/</div><div><span class="" style="white-space:pre"> </span>const v_t ndir((d*-.2+b.b1*LLVMsin(a)+b.b2*LLVMcos(a)).norm()); /*transcendentals?!*/</div><div><span class="" style="white-space:pre"> </span>n=create(n,lvl-1,dist,c+ndir*(r+nr),ndir,nr);</div><div><span class="" style="white-space:pre"> </span>a+=daL;</div><div><span class="" style="white-space:pre"> </span>}</div><div><span class="" style="white-space:pre"> </span>a-=daL/3.;/*tweak*/</div><div><span class="" style="white-space:pre"> </span>for(int i=0;i<3;++i){ /*upper ring*/</div><div><span class="" style="white-space:pre"> </span>const v_t ndir((d*+.6+b.b1*LLVMsin(a)+b.b2*LLVMcos(a)).norm());</div><div><span class="" style="white-space:pre"> </span>n=create(n,lvl-1,dist,c+ndir*(r+nr),ndir,nr); a+=daU;</div><div><span class="" style="white-space:pre"> </span>}</div><div><span class="" style="white-space:pre"> </span>return n;</div><div>}</div><div><br></div><div>the above function is recursive function but it optimized to not to save callee saved registers. Due to recursion while performing IPRA, it can't have updated regmask ( or it is not correct to have it ) so register allocators will use callee saved registers. But then it optimizes for not saving registers due to this in above case object v_t 's address has been loaded in EBX register and when recursive call returns it gets clobbered.</div><div><br></div><div>The sqlite3 failure is also due to this bug as I previously mentioned RegMask is not propagated at some call sites and still it disables saving registers.</div><div><br></div><div>To address this issue I have changed check for allowing functions to be considered for CSR optimization as follows:</div><div><br></div><div><div>bool RegUsageInfoCollector::isEligibleForTailCallOptimization(Function *F) {</div><div> if (!F->hasFnAttribute(Attribute::NoRecurse)) {</div><div> <span class="" style="white-space:pre"> </span>dbgs() << F->getName() << " Function is recursive\n";</div><div> <span class="" style="white-space:pre"> </span>return true;</div><div> }</div><div><br></div><div> const Module *M = F->getParent();</div><div> for (const Function &Fu : *M)</div><div> for (const BasicBlock &BB : Fu)</div><div> for (const Instruction &II : BB) {</div><div> if (auto CS = ImmutableCallSite(&II))</div><div> if (CS.getCalledFunction() == F && CS.isTailCall()) {</div><div> <span class="" style="white-space:pre"> </span>dbgs() << F->getName() << "Function is tailCall\n";</div><div> return true;</div><div> }</div><div> }</div><div> return false;</div><div><br></div><div>}</div></div><div><br></div><div>And now test-suite passes with zero failures. Also I have added a simple static to count number of functions which gets optimized, according to that sqlite3 application is having total 32 functions optimized, and SPASS is having 104 functions optimized.</div><div><br></div><div>If you found any thing incorrect please let me know otherwise just ping on this mail so that I can update review request.</div><div><br></div><div>Sincerely,</div><div>Vivek</div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><span class=""><font color="#888888"><div><br></div><div>-Vivek <br></div></font></span></div><div class=""><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">2016-06-30 14:21 GMT+05:30 vivek pandya <span dir="ltr"><<a href="mailto:vivekvpandya@gmail.com" target="_blank">vivekvpandya@gmail.com</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr">Hello Mentors,<div><br></div><div>I am currently finding bug in Local Function related optimization due to which runtime failures are observed in some test cases, as those test cases are containing very large function with recursion and object oriented code so I am not able to find a pattern which is causing failure. So I tried following simple case to understand expected behavior from this optimization.</div><div><br></div><div>Consider following code :</div><div><div><br></div><div>define void @bar() #0 {</div><div> call void asm sideeffect "movl<span style="white-space:pre-wrap"> </span>%ecx, %r15d", "~{r15}"() #0</div><div> call void @foo()</div><div> call void asm sideeffect "movl<span style="white-space:pre-wrap"> </span>%r15d, %ebx", "~{rbx}"() #0</div><div> ret void</div><div>}</div><div><br></div><div>define internal void @foo() #0 {</div><div> call void asm sideeffect "movl<span style="white-space:pre-wrap"> </span>%r14d, %r15d", "~{r15}"() #0</div><div> ret void</div><div>}</div></div><div><br></div><div>and its generated assembly code when IPRA enabled:</div><div><br></div><div><div><span style="white-space:pre-wrap"> </span>.section<span style="white-space:pre-wrap"> </span>__TEXT,__text,regular,pure_instructions</div><div><span style="white-space:pre-wrap"> </span>.macosx_version_min 10, 12</div><div><span style="white-space:pre-wrap"> </span>.p2align<span style="white-space:pre-wrap"> </span>4, 0x90</div><div>_foo: ## @foo</div><div><span style="white-space:pre-wrap"> </span>.cfi_startproc</div><div>## BB#0:</div><div><span style="white-space:pre-wrap"> </span>## InlineAsm Start</div><div><span style="white-space:pre-wrap"> </span>movl<span style="white-space:pre-wrap"> </span>%r14d, %r15d</div><div><span style="white-space:pre-wrap"> </span>## InlineAsm End</div><div><span style="white-space:pre-wrap"> </span>retq</div><div><span style="white-space:pre-wrap"> </span>.cfi_endproc</div><div><br></div><div><span style="white-space:pre-wrap"> </span>.globl<span style="white-space:pre-wrap"> </span>_bar</div><div><span style="white-space:pre-wrap"> </span>.p2align<span style="white-space:pre-wrap"> </span>4, 0x90</div><div>_bar: ## @bar</div><div><span style="white-space:pre-wrap"> </span>.cfi_startproc</div><div>## BB#0:</div><div><span style="white-space:pre-wrap"> </span>pushq<span style="white-space:pre-wrap"> </span>%r15</div><div>Ltmp0:</div><div><span style="white-space:pre-wrap"> </span>.cfi_def_cfa_offset 16</div><div><span style="white-space:pre-wrap"> </span>pushq<span style="white-space:pre-wrap"> </span>%rbx</div><div>Ltmp1:</div><div><span style="white-space:pre-wrap"> </span>.cfi_def_cfa_offset 24</div><div><span style="white-space:pre-wrap"> </span>pushq<span style="white-space:pre-wrap"> </span>%rax</div><div>Ltmp2:</div><div><span style="white-space:pre-wrap"> </span>.cfi_def_cfa_offset 32</div><div>Ltmp3:</div><div><span style="white-space:pre-wrap"> </span>.cfi_offset %rbx, -24</div><div>Ltmp4:</div><div><span style="white-space:pre-wrap"> </span>.cfi_offset %r15, -16</div><div><span style="white-space:pre-wrap"> </span>## InlineAsm Start</div><div><span style="white-space:pre-wrap"> </span>movl<span style="white-space:pre-wrap"> </span>%ecx, %r15d</div><div><span style="white-space:pre-wrap"> </span>## InlineAsm End</div><div><span style="white-space:pre-wrap"> </span>callq<span style="white-space:pre-wrap"> </span>_foo</div><div><span style="white-space:pre-wrap"> </span>## InlineAsm Start</div><div><span style="white-space:pre-wrap"> </span>movl<span style="white-space:pre-wrap"> </span>%r15d, %ebx</div><div><span style="white-space:pre-wrap"> </span>## InlineAsm End</div><div><span style="white-space:pre-wrap"> </span>addq<span style="white-space:pre-wrap"> </span>$8, %rsp</div><div><span style="white-space:pre-wrap"> </span>popq<span style="white-space:pre-wrap"> </span>%rbx</div><div><span style="white-space:pre-wrap"> </span>popq<span style="white-space:pre-wrap"> </span>%r15</div><div><span style="white-space:pre-wrap"> </span>retq</div><div><span style="white-space:pre-wrap"> </span>.cfi_endproc</div><div><br></div><div><br></div><div>.subsections_via_symbols</div></div><div><br></div><div>now foo clobbers R15 (which is callee saved) but as foo is local function IPRA will mark R15 as clobbered and foo will not have save/restore for R15 in prologue/epilog . Now for above function code to work correctly in call site of foo in bar save and restore of R15 is expected but I am not able to find a pass in llvm which does that in fact if I am not wrong RegMasks of call site will be used by reg allocators by LiveIntervals::checkRegMaskInterference and due to that if R15 is marked clobbered by call _foo then R15 will not be used for live-range which is spanned across call _foo. ( that it self is other concerns because it may result in virtual reg spill due to lack of available regs, as while setting callee saved regs none it will be propagated through regmaks) </div><div><br></div><div>Here are my questions related to this example:</div><div>1) Is there any pass or code in LLVM which is responsible for caller saved register for Physical Registers? By looking at InlineSpiller.cpp it is responsible for VReg spilling.</div><div>2) If such pass exists then why R15 is not saved around call __foo?</div><div>3) Why _bar is saving %rax in above code?</div><div><br></div><div>Please help!</div><div><br></div><div>Sincerely,</div><div>Vivek</div><div><br></div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div></div>