llvm dev - Sep 2020 - Mem2reg: load before single store

Hi all!

While playing with LLVM, I've found a weird behavior in mem2reg pass.

When optimizing single stores, undefined value is placed before any load
preceding the store (based on basicblock's ordering and simple dominator
analysis, if I remember correctly).

This is the line that is responsible for the behavior: (LLVM9 does the same)

https://llvm.org/doxygen/PromoteMemoryToRegister_8cpp_source.html#l00629

A problem arises, and I am not sure if it is really a problem or just weird
C-compliant behavior.

int a; // or, equally, int a=0;

int main(){
 int b;
 if (b) // (*)
   b=a;
 if (b)
   printf("This will be called");
}

The first load of variable b, before the single store (the first branching)
is replaced by undef, so the second branch will be replaced by a phi node,
if the (*) branch is taken, the value is 0, else undef.

I'm concerned that this is an LLVM bug.

Reproduction:

clang -S -emit-llvm test.c
opt -mem2reg test.ll

I'm not at the computer right now, so I cannot show the exact generated
code.

Radnai László
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200914/5a6c769f/attachment.html>

Hi again!

The initial code: (test.c)

#include <stdio.h>

int a; // or, equally, int a=0;

int main(){
 int b;
 if (b) // (*)
   b=a;
 if (b)
   puts("This will be called");
}

In LLVM IR:

define dso_local i32 @main() #0 {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
  store i32 0, i32* %1, align 4
  %3 = load i32, i32* %2, align 4
  %4 = icmp ne i32 %3, 0
  br i1 %4, label %5, label %7

5:                                                ; preds = %0
  %6 = load i32, i32* @a, align 4
  store i32 %6, i32* %2, align 4
  br label %7

7:                                                ; preds = %5, %0
  %8 = load i32, i32* %2, align 4
  %9 = icmp ne i32 %8, 0
  br i1 %9, label %10, label %12

10:                                               ; preds = %7
  %11 = call i32 @puts(i8* getelementptr inbounds ([20 x i8], [20 x i8]*
@.str, i64 0, i64 0))
  br label %12

12:                                               ; preds = %10, %7
  %13 = load i32, i32* %1, align 4
  ret i32 %13
}

After optimizing: `clang -S -emit-llvm test.c -O0 -o - | sed
's/optnone//g'
| opt asd.ll -mem2reg | llvm-dis`
(Note: optnone is removed to have mem2reg optimize the main function)

define dso_local i32 @main() #0 {
  %1 = icmp ne i32 undef, 0 ; <- undef!!
  br i1 %1, label %2, label %4

2:                                                ; preds = %0
  %3 = load i32, i32* @a, align 4
  br label %4

4:                                                ; preds = %2, %0
  %.0 = phi i32 [ %3, %2 ], [ undef, %0 ] ; <- undef!!
  %5 = icmp ne i32 %.0, 0
  br i1 %5, label %6, label %8

6:                                                ; preds = %4
  %7 = call i32 @puts(i8* getelementptr inbounds ([20 x i8], [20 x i8]*
@.str, i64 0, i64 0))
  br label %8

8:                                                ; preds = %6, %4
  ret i32 0
}

My problem is the two annotated "undef!!" comments. They are the same
undef
value, and, by decoupling these, the program changes.
I'm not really sure, because the C standard has some really weird undefined
behaviour definitions.
Also, I don't know how LLVM "undef" should work. If
"undef" is an
unspecified-like value, not an undefined-behavior-causing value, then it
could also be a bug in LLVM.

Please reach back if you need more information.

László

On Mon, Sep 14, 2020 at 9:19 AM László Radnai <radlaci97 at gmail.com>
wrote:
> Hi all!
>
> While playing with LLVM, I've found a weird behavior in mem2reg pass.
>
> When optimizing single stores, undefined value is placed before any load
> preceding the store (based on basicblock's ordering and simple
dominator
> analysis, if I remember correctly).
>
> This is the line that is responsible for the behavior: (LLVM9 does the
> same)
>
> https://llvm.org/doxygen/PromoteMemoryToRegister_8cpp_source.html#l00629
>
> A problem arises, and I am not sure if it is really a problem or just
> weird C-compliant behavior.
>
> int a; // or, equally, int a=0;
>
> int main(){
>  int b;
>  if (b) // (*)
>    b=a;
>  if (b)
>    printf("This will be called");
> }
>
> The first load of variable b, before the single store (the first
> branching) is replaced by undef, so the second branch will be replaced by a
> phi node, if the (*) branch is taken, the value is 0, else undef.
>
> I'm concerned that this is an LLVM bug.
>
> Reproduction:
>
> clang -S -emit-llvm test.c
> opt -mem2reg test.ll
>
> I'm not at the computer right now, so I cannot show the exact generated
> code.
>
> Radnai László
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200914/6aacb4e4/attachment-0001.html>

On Mon, Sep 14, 2020 at 3:19 AM László Radnai via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> A problem arises, and I am not sure if it is really a problem or just
> weird C-compliant behavior.
>
> int a; // or, equally, int a=0;
>
> int main(){
>  int b;
>  if (b) // (*)
>
At this line, you invoke undefined behavior by reading the value of
"b",
before it's been initialized. At this point, the compiler may do whatever
it likes.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20200914/dce46e8f/attachment.html>

On 9/14/20 9:30 AM, James Y Knight via llvm-dev wrote:
> On Mon, Sep 14, 2020 at 3:19 AM László Radnai via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> A problem arises, and I am not sure if it is really a problem or just
>> weird C-compliant behavior.
>>
>> int a; // or, equally, int a=0;
>>
>> int main(){
>>   int b;
>>   if (b) // (*)
>>
> At this line, you invoke undefined behavior by reading the value of
"b",
> before it's been initialized. At this point, the compiler may do
whatever
> it likes.
FTR, it is *not* UB to read the value of b, you will read undef which is 
totally fine. It is however UB to branch on undef.
At that point we can stop discussing what "happens next".

~ Johannes


>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev