Possible MemCpyOpt bug?

Hi all,

I think I’ve managed to trick the legacy MemCpyOpt (MCO) into an incorrect
transform, but I would like to confirm the validity of my counterexample before
working on the fix. Suppose the following IR:

%T = type { i32, i32 }

define void @f(%T* %a, %T* %b, %T* %c, %T* %d) {
%val = load %T, %T* %a, !alias.scope !{!10}

; store1
; Aliases the load
store %T { i32 22, i32 22 }, %T* %b, !alias.scope !{!11}

; store2
; Aliases the store below and the load. No-alias with above store
store %T { i32 44, i32 44 }, %T* %c, !alias.scope !{!12},
!noalias !{!11}

; store3
; MCO wants to combine this store with the load into a memcpy
store %T %val, %T* %d, !alias.scope !{!13}, !noalias !{!10, !11}
ret void
}

!0 = !{!0}
!1 = !{!1}
!2 = !{!2}
!3 = !{!3}

!10 = !{ !10, !0 }
!11 = !{ !11, !1 }
!12 = !{ !12, !2 }
!13 = !{ !13, !3 }

Have I used the metadata nodes correctly? The goal is to make:

  • load may-alias store1
  • load may-alias store2
  • store2 may-alias store3

-print-may-aliases seems confirm this:

opt -disable-output -basicaa -scoped-noalias -aa-eval -evaluate-aa-metadata -print-may-aliases ohgod.ll
Function: f: 4 pointers, 0 call sites
MayAlias: %T* %a, %T* %b
MayAlias: %T* %a, %T* %c
MayAlias: %T* %b, %T* %c
MayAlias: %T* %a, %T* %d
MayAlias: %T* %b, %T* %d
MayAlias: %T* %c, %T* %d
MayAlias: %val = load %T, %T* %a, !alias.scope !0 <-> store %T { i32 23, i32 23 }, %T* %b, !alias.scope !3
MayAlias: %val = load %T, %T* %a, !alias.scope !0 <-> store %T { i32 44, i32 44 }, %T* %c, !alias.scope !6, !noalias !3
MayAlias: store %T %val, %T* %d, !alias.scope !9, !noalias !12 <-> store %T { i32 44, i32 44 }, %T* %c, !alias.scope !6, !noalias !3

The problem is that MCO happily moves store2 + store3 above store1 (this is
fine) and then the load below store2 (this is not fine) in order to combine
load + store3 into a memcpy:

opt -S -basicaa -scoped-noalias -aa-eval -evaluate-aa-metadata -memcpyopt

%T = type { i32, i32 }

define void @f(%T* %a, %T* %b, %T* %c, %T* %d) {
; store2
store %T { i32 44, i32 44 }, %T* %c, !alias.scope !0, !noalias !3

; combined from load + store3
call void @llvm.memcpy.p0i8.p0i8.i64(i8* (bitcast %T* %d to i8*),
i8* (bitcast %T* %a to i8*),
i64 8, i32 4, i1 false)

; store1
store %T { i32 23, i32 23 }, %T* %b, !alias.scope !3
ret void
}

From: "Bryant Wong via llvm-dev" <llvm-dev@lists.llvm.org>
To: llvm-dev@lists.llvm.org
Sent: Thursday, November 17, 2016 1:00:06 PM
Subject: [llvm-dev] Possible MemCpyOpt bug?

Hi all,

I think I've managed to trick the legacy MemCpyOpt (MCO) into an
incorrect
transform, but I would like to confirm the validity of my
counterexample before
working on the fix.

Looks like you posted a fix for review: https://reviews.llvm.org/D26811

Suppose the following IR:

%T = type { i32, i32 }

define void @f(%T* %a, %T* %b, %T* %c, %T* %d) {
%val = load %T, %T* %a, !alias.scope !{!10}

; store1
; Aliases the load
store %T { i32 22, i32 22 }, %T* %b, !alias.scope !{!11}

; store2
; Aliases the store below and the load. No-alias with above store
store %T { i32 44, i32 44 }, %T* %c, !alias.scope !{!12},
!noalias !{!11}

; store3
; MCO wants to combine this store with the load into a memcpy
store %T %val, %T* %d, !alias.scope !{!13}, !noalias !{!10, !11}
ret void
}

!0 = !{!0}
!1 = !{!1}
!2 = !{!2}
!3 = !{!3}

!10 = !{ !10, !0 }
!11 = !{ !11, !1 }
!12 = !{ !12, !2 }
!13 = !{ !13, !3 }

Have I used the metadata nodes correctly? The goal is to make:

- load may-alias store1
- load may-alias store2
- store2 may-alias store3

Looks right.

-Hal

+1
The only question i have on correctness is whether it only moves past single loads at a time (otherwise, you really have to check every load it passes)