LICM sinks/hoist memory accesses to dead stack objects (wrong code at -O1 on x86_64-linux-gnu)

[zhendongsu]

Bugzilla Link	52496
Version	unspecified
OS	All
CC	@fhahn,@MaskRay,@preames,@RKSimon,@rnk,@rotateright,@xiangzh1

Extended Description

It appears to be a regression from 12.*.

[758] % clangtk -v
clang version 14.0.0 (https://github.com/llvm/llvm-project.git 8ed8d370880b5c4e7bbf52b50791710a9f4f834b)
Target: x86_64-unknown-linux-gnu
Thread model: posix
InstalledDir: /local/suz-local/opfuzz/bin
Found candidate GCC installation: /usr/lib/gcc/i686-linux-gnu/8
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/6
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/6.5.0
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/7
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/7.5.0
Found candidate GCC installation: /usr/lib/gcc/x86_64-linux-gnu/8
Selected GCC installation: /usr/lib/gcc/x86_64-linux-gnu/7.5.0
Candidate multilib: .;@m64
Candidate multilib: 32;@m32
Candidate multilib: x32;@mx32
Selected multilib: .;@m64
[759] % 
[759] % clangtk -O0 -w small.c; ./a.out
[760] % 
[760] % clangtk -O1 -w small.c
[761] % ./a.out
Aborted
[762] % 
[762] % cat small.c
int printf(const char *, ...);
int a, *b;
int main() {
  int *c, *d, e;
  while (a) {
    int f[1];
    while (a)
      printf(c);
    c = f;
    b = (int *)&d;
  }
L:
  e = 1;
  if (a) {
    printf("%d", a);
    b = &e;
    (*c)++;
  }
  if (a)
    goto L;
  if (!e)
    __builtin_abort();
  return 0;
}

[rotateright]

The bug is either in or exposed by CGP. I'm attaching a slight IR reduction that shows this diff:

% llc -o - -disable-cgp=0 52496.ll | clang -x assembler - && ./a.out; echo $?
0
% llc -o - -disable-cgp=1 52496.ll | clang -x assembler - && ./a.out; echo $?
1

[rotateright]

IR test for codegenprepare

[rotateright]

I see that CGP is duplicating/sinking casts of alloca'd pointers around lifetime markers and that seems suspicious, but I'm not familiar with how that (or StackColoring?) works.

cc'ing some other contributors based on commit logs in those areas.

[fhahn]

The original C reproducer works correctly on current trunk: https://godbolt.org/z/nM3ca1hr4

The IR reproducer from @rotateright still shows a difference with and without codegenprepare, but I think this may be due to the reproducer already having accesses to locations after lifetime.end, e.g. in L.preheader.

[fhahn]

Ok, looks like the original program has an stack-use-after-scope bug and hence the program invalid (f is declared in the while() scope but escapss and is used outside that scope): https://clang.godbolt.org/z/fjEqbETnG

[zhendongsu]

Ok, looks like the original program has an stack-use-after-scope bug and hence the program invalid (f is declared in the while() scope but escapss and is used outside that scope): https://clang.godbolt.org/z/fjEqbETnG

Florian, this looks like an address sanitizer bug for 13.0.* at -O1 as the code should be valid:

• 13.0.* at -O0 okay
• 12.0.* and trunk at -O1 also okay

@fhahn

[fhahn]

You are right, the access to the out-of-scope stack entry is never executed in the original program!

The issue is that LICM hoists a load of and sinks a store to an alloca out of a loop and executes it unconditionally, even though the lifetime of the alloca has been ended. This means we now execute a load/store of a dead stack object. It's not entirely clear from LangRef what this means, but According to Alive2 this is UB: https://alive2.llvm.org/ce/z/QkhiTM (simplified version).

As a consequence, the backend will use the same stack slot for %e and %f. I don't think the load is problematic, but the store may trash a valid different stack value.

llvm::isSafeToSpeculativelyExecute may need updating to consider that the alloca is dead. CC'ing some people for additional thoughts @preames @rotateright, @alinas @nikic

IR reproducer for LICM (https://clang.godbolt.org/z/Pzn5Mf86v):

target datalayout = "e-m:o-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
define dso_local i32 @main(i32 %n) {
entry:
  %e = alloca i32, align 4
  %f = alloca i32, align 4
  store i32 0, i32* %e
  %f.cast = bitcast i32* %f to i8*
  call void @llvm.lifetime.start.p0i8(i64 4, i8* nonnull %f.cast)
  call void @llvm.lifetime.end.p0i8(i64 4, i8* nonnull %f.cast)
  br label %L

L:                                                ; preds = %if.end, %L.preheader
  %iv = phi i32 [ 0, %entry ], [ %iv.next, %if.end ]
  %tobool5.not = icmp eq i32 %iv, %n
  br i1 %tobool5.not, label %if.end, label %if.then

if.then:                                          ; preds = %L
  %i8 = load i32, i32* %f, align 4
  %inc = add nsw i32 %i8, 1
  store i32 %inc, i32* %f, align 4
  br label %if.end

if.end:                                           ; preds = %if.then, %L
  %tobool7.not = icmp eq i32 %iv, 1999
  %iv.next = add i32 %iv, 1
  br i1 %tobool7.not, label %if.end9, label %L

if.end9:                                          ; preds = %if.end
  %l = load i32, i32* %e
  ret i32 %l
}

; Function Attrs: argmemonly nofree nosync nounwind willreturn
declare void @llvm.lifetime.start.p0i8(i64 immarg, i8* nocapture) #1

; Function Attrs: argmemonly nofree nosync nounwind willreturn
declare void @llvm.lifetime.end.p0i8(i64 immarg, i8* nocapture) #1