<div dir="ltr"><div>Hi LLVMDev,</div><div>this is Jeehoon Kang, a Ph.D. student of Software Foundations Laboratory (<a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__sf.snu.ac.kr&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=hR8pGe3Q1JmYz3_mecyTZHIEnTWU6h4AP5z5veYbKKU&s=QHEI8T2mHXXoa_RYtT4MC90S-8B2k5zD674XkLa3-MQ&e=">http://sf.snu.ac.kr</a>), Dept. of Computer Science & Engineering, Seoul National University.  Our group studied the mem2reg pass, and we got a question on its algorithm.</div><div><br></div><div>As far as I understand, the mem2reg pass essentially uses the SSA construction algorithm to promote allocas into registers, but there are shortcuts for some special cases.  One of the special cases is when an alloca is "only used within a single basic block." (<a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_doxygen_html_PromoteMemoryToRegister-5F8cpp-5Fsource.html-23l00435&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=hR8pGe3Q1JmYz3_mecyTZHIEnTWU6h4AP5z5veYbKKU&s=jYPSUT11XOzlk35w1_X6cWomDQH7ZH75Wk1nlwWhngg&e=">http://llvm.org/docs/doxygen/html/PromoteMemoryToRegister_8cpp_source.html#l00435</a>)</div><div><br></div><div>But currently, I cannot understand the algorithm for this special case.  In this case, the mem2reg pass "perform[s] a single linear pass over the basic block using the Alloca."  In other words, a load is replaced by a read from a register corresponding to the nearest preceding store.  The logic I cannot understand is: "If there is no store before this load, the load takes the undef value." (<a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_doxygen_html_PromoteMemoryToRegister-5F8cpp-5Fsource.html-23l00471&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=hR8pGe3Q1JmYz3_mecyTZHIEnTWU6h4AP5z5veYbKKU&s=MPUdZbhjg5W-ns5OaDPH3y-GbMTc_HkgzgFPfw5L3hk&e=">http://llvm.org/docs/doxygen/html/PromoteMemoryToRegister_8cpp_source.html#l00471</a>).  If the block is inside a loop, just writing the undef value is unsound, I think.</div><div><br></div><div><br></div><div>Here is an example C code that I think Clang mis-compiles:</div><div>=====</div><div>void foo(unsigned char a, unsigned char b) {</div><div>  if (b != 2) printf("%d ", (int) a);</div><div>}</div><div>int main() {</div><div>  unsigned char a, b;</div><div>  for (unsigned char i = 0; i < 3; ++i) {</div><div>    a = b; // (*)</div><div>    b = 5;</div><div>    b = 2 + i;</div><div>    foo (a, b);</div><div>  }</div><div>  return 0;</div><div>}</div><div>=====</div><div>The mem2reg pass essentially promotes the variable "b" into register by the shortcut for the special case I mentioned above.  In this case, the load from "b" at (*) is replaced with the undef value, so "a = b;" is (essentially) replaced with "a = <undef>;".  However, this changes the semantics: the original program printed "2 3 ", while the transformed program prints "0 0 ".</div><div><br></div><div>The original program prints "2 3 " for the following reasons.  In the first iteration (i=0), a=<undef> and b=2, so "foo" does not print anything.  In the second and the third iteration (i=1 and i=2, respectively), (a, b) = (2, 3) and (3, 4), and "foo" prints 2 and 3, respectively.</div><div><br></div><div>On the other hand, the transformed program prints "0 0 ", since "a" always equals to <undef> in "foo".  And the Clang compiler (at least version 3.4 through the development branch 3.7) chose to print "0" for the undef value for this program.</div><div><br></div><div><br></div><div>I guess I misunderstand something here, since this case seems to be already known to LLVM developers (<a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__llvm.org_docs_doxygen_html_PromoteMemoryToRegister-5F8cpp-5Fsource.html-23l00427&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=hR8pGe3Q1JmYz3_mecyTZHIEnTWU6h4AP5z5veYbKKU&s=sG0eEmiLJqTlb2wD53wmLZgZMVXWGRuVgC5Msk6v_-I&e=">http://llvm.org/docs/doxygen/html/PromoteMemoryToRegister_8cpp_source.html#l00427</a>).  But I failed to google further information on this issue (by query "promoteSingleBlockAlloca").  So I asked here for your help.</div><div><br></div><div>Thank you,</div><div>Jeehoon</div><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__sf.snu.ac.kr_jeehoon.kang&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=hR8pGe3Q1JmYz3_mecyTZHIEnTWU6h4AP5z5veYbKKU&s=BwEoCP5LmPj1FGh18JPsRHBG-dbUYf8Rmx5UJ0oQTyQ&e=" target="_blank">Jeehoon Kang (Ph.D. student)</a><div><a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__sf.snu.ac.kr&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=hR8pGe3Q1JmYz3_mecyTZHIEnTWU6h4AP5z5veYbKKU&s=QHEI8T2mHXXoa_RYtT4MC90S-8B2k5zD674XkLa3-MQ&e=" target="_blank">Software Foundations Laboratory</a><div><a href="https://urldefense.proofpoint.com/v2/url?u=http-3A__www.snu.ac.kr&d=AwMFaQ&c=8hUWFZcy2Z-Za5rBPlktOQ&r=Mfk2qtn1LTDThVkh6-oGglNfMADXfJdty4_bhmuhMHA&m=hR8pGe3Q1JmYz3_mecyTZHIEnTWU6h4AP5z5veYbKKU&s=T7QUSLpEWabXZH93qgeBPbDs2YgIro5ZfHqzv6Vj7Fg&e=" target="_blank">Seoul National University</a></div></div></div></div>
</div>