[SROA] some wrong when dealing with undef variable

LLVM Project
1

when dealing with the case below:

extern int foo2(int a, int b,int c);
void foo(int *a, int len){
 for(int i=0;i<len;i++) {
 int tmp;
 tmp = foo2(tmp, a[i], 0);
 tmp = foo2(tmp, a[i], 1);
 a[i] = tmp;
 }
}

there will be an redundant phi node %9 after SORA pass:

define dso_local void @foo(i32* nocapture, i32) local_unnamed_addr #0 {
  %3 = icmp sgt i32 %1, 0
  br i1 %3, label %4, label %6

; <label>:4:                                      ; preds = %2
  %5 = zext i32 %1 to i64
  br label %7

; <label>:6:                                      ; preds = %7, %2
  ret void

; <label>:7:                                      ; preds = %7, %4
  %8 = phi i64 [ 0, %4 ], [ %15, %7 ]
  %9 = phi i32 [ undef, %4 ], [ %14, %7 ]
  %10 = getelementptr inbounds i32, i32* %0, i64 %8
  %11 = load i32, i32* %10, align 4, !tbaa !2
  %12 = tail call i32 @foo2(i32 %9, i32 %11, i32 0) #2
  %13 = load i32, i32* %10, align 4, !tbaa !2
  %14 = tail call i32 @foo2(i32 %12, i32 %13, i32 1) #2
  store i32 %14, i32* %10, align 4, !tbaa !2
  %15 = add nuw nsw i64 %8, 1
  %16 = icmp eq i64 %15, %5
  br i1 %16, label %6, label %7
}

when the result we expect is:

; <label>:7:                                      ; preds = %7, %4
  %8 = phi i64 [ 0, %4 ], [ %15, %7 ]
  %10 = getelementptr inbounds i32, i32* %0, i64 %8
  %11 = load i32, i32* %10, align 4, !tbaa !2
  %12 = tail call i32 @foo2(i32 undef, i32 %11, i32 0) #2
  %13 = load i32, i32* %10, align 4, !tbaa !2
  %14 = tail call i32 @foo2(i32 %12, i32 %13, i32 1) #2
  store i32 %14, i32* %10, align 4, !tbaa !2
  %15 = add nuw nsw i64 %8, 1
  %16 = icmp eq i64 %15, %5
  br i1 %16, label %6, label %7
}

and I found this problem is caused by the function ComputeLiveInBlocks, it will work though all predecessors if this value is load before store, ignoring the lifetime_start intrinsic which was deleted before in function removeIntrinsicUsers.

2

I wouldn’t describe %9 as being redundant here, as the behaviour of the IR program in your expected result is different from the behaviour that SROA produces. Specifically: SROA’s output only makes %9 undef on the first iteration of the loop, the value is well defined in every subsequent iteration. Wheras in your expected output, the (effective) value of %9 is undef on every iteration of the loop.

As I recall, a redundant PHI has a formal definition of having the same incoming value from every incoming block.

Which one of the overall compiler behaviours you’ve posted is correct is a different question, I think it’s up to subsequent optimisation passes to fold the value of undef into places rather than SROA’s responsibility.

3

I believe the original program contains UB in this line: tmp = foo2(tmp, a[i], 0); (passing indeterminate value by value as a function parameter).
Not that SROA takes advantage of this fact (but this function would likely be turned into nop in the full pipeline) but the transformation itself seems valid.

4

No, SROA refined the behavior in a way that needs to be preserved. We lost the lifetime information on tmp, as @ttllllll6 describes. This is a performance bug.

That sounds like the underlying problem. Can you file a bug, please.

That is correct, but irrelevant. Once on IR level, and w/o noundef on the argument, this code doesn’t exhibit this UB and SROA should not “loose” information.

5

The OP didn’t provide an IR that they used, and the example C code does generate declarations with noundef attribute. There could be some potential missed optimizations hiding in there but the patch fixing this should have better motivating example/IR included.

6

Right. Given the C and IR examples, I assume the OP used clang < v14.0:

But again, the IR could come from something else, we should simply utilize the lifetime markers better in SROA.

7

Thanks for replying, and sorry for the later reply of me.
I found this problem in a custom clang base on version 15.0, and I tried to test in the newist llvm, but our service miss some requirement so I can’t build one.
It seems very useful the website you put here, thanks again.
and I’m sorry that I don’t know some terms you mentioned, OP and UB, can anyone tell me, or is there any website that I can search the terms?

8

OP - Original Poster (that’s you ;P).
UB - Undefined Behavior: Undefined behavior - Wikipedia