Suspicious behavior of mem2reg (promoteSingleBlockAlloca)

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:

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

Bug filed at https://llvm.org/bugs/show_bug.cgi?id=24179