[LLVMdev] Suspicious behavior of mem2reg (promoteSingleBlockAlloca)

[Sanjoy Das]

You're right, this seems wrong.  The smallest reproducer I can find
is:

'''
declare i1 @use(i32)

define void @f() {
 entry:
  %t = alloca i32
  br label %loop

 loop:
  %v = load i32, i32* %t
  %c = call i1 @use(i32 %v)
  store i32 46, i32* %t
  store i32 42, i32* %t
  br i1 %c, label %loop, label %exit

 exit:
  ret void
}
'''

(The irrelevant store of 46 is to prevent another heuristic in mem2reg
from kicking in.)

Running this through -mem2reg gives me

'''
declare i1 @use(i32)

define void @f() {
entry:
  br label %loop

loop:                                             ; preds = %loop, %entry
  %c = tail call i1 @use(i32 undef)
  br i1 %c, label %loop, label %exit

exit:                                             ; preds = %loop
  ret void
}
'''

when %v should really be a phi that is undef on the entry -> loop edge
and 42 on the loop -> loop backedge.

-- Sanjoy


On Fri, Jul 17, 2015 at 12:16 AM, Jeehoon Kang
<jeehoon.kang at sf.snu.ac.kr> wrote:
> Hi LLVMDev,
> this is Jeehoon Kang, a Ph.D. student of Software Foundations Laboratory
> (http://sf.snu.ac.kr), Dept. of Computer Science & Engineering, Seoul
> National University.  Our group studied the mem2reg pass, and we got a
> question on its algorithm.
>
> 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."
> (http://llvm.org/docs/doxygen/html/PromoteMemoryToRegister_8cpp_source.html#l00435)
>
> 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."
> (http://llvm.org/docs/doxygen/html/PromoteMemoryToRegister_8cpp_source.html#l00471).
> If the block is inside a loop, just writing the undef value is unsound, I
> think.
>
>
> Here is an example C code that I think Clang mis-compiles:
> =====
> void foo(unsigned char a, unsigned char b) {
>   if (b != 2) printf("%d ", (int) a);
> }
> int main() {
>   unsigned char a, b;
>   for (unsigned char i = 0; i < 3; ++i) {
>     a = b; // (*)
>     b = 5;
>     b = 2 + i;
>     foo (a, b);
>   }
>   return 0;
> }
> =====
> 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 ".
>
> 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.
>
> 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.
>
>
> I guess I misunderstand something here, since this case seems to be already
> known to LLVM developers
> (http://llvm.org/docs/doxygen/html/PromoteMemoryToRegister_8cpp_source.html#l00427).
> But I failed to google further information on this issue (by query
> "promoteSingleBlockAlloca").  So I asked here for your help.
>
> Thank you,
> Jeehoon
>
> --
> Jeehoon Kang (Ph.D. student)
> Software Foundations Laboratory
> Seoul National University
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>