[llvm-dev] A code layout related side-effect introduced by rL318299
Wei Mi via llvm-dev
llvm-dev at lists.llvm.org
Mon Dec 18 16:14:50 PST 2017
Hi,
Recently 10% performance regression on an important benchmark showed up
after we integrated https://reviews.llvm.org/rL318299. The analysis showed
that rL318299 triggered loop rotation on an multi exits loop, and the loop
rotation introduced code layout issue. The performance regression is a
side-effect of rL318299. I got two testcases a.ll and b.ll attached to
illustrate the problem. a.ll was generated by rL318298 and b.ll was
generated by rL318299.
-------------------------- a.ll ----------------------------
declare void @_Z1fv() local_unnamed_addr #2
@i = global i8 0, align 1
define i8* @_Z1gPcS_S_(i8* nocapture readonly %d, i8* %h, i8* readnone
returned %p3) local_unnamed_addr #3 {
entry:
br label %while.cond
while.cond: ; preds = %while.body,
%entry
%h.addr.0 = phi i8* [ %h, %entry ], [ %add.ptr4, %while.body ]
%d.addr.0 = phi i8* [ %d, %entry ], [ %add.ptr3, %while.body ]
%cmp = icmp ugt i8* %h.addr.0, @i
br i1 %cmp, label %while.end, label %while.body
while.body: ; preds = %while.cond
%0 = bitcast i8* %d.addr.0 to i64*
%1 = load i64, i64* %0, align 1
%2 = bitcast i8* %h.addr.0 to i64*
store i64 %1, i64* %2, align 1
%add.ptr = getelementptr inbounds i8, i8* %d.addr.0, i64 8
%3 = bitcast i8* %add.ptr to i64*
%4 = load i64, i64* %3, align 1
store i64 %4, i64* %2, align 1
%add.ptr3 = getelementptr inbounds i8, i8* %d.addr.0, i64 6
%add.ptr4 = getelementptr inbounds i8, i8* %h.addr.0, i64 6
%cmp5 = icmp ult i8* %add.ptr4, %p3
br i1 %cmp5, label %while.cond, label %return
while.end: ; preds = %while.cond
tail call void @_Z1fv()
unreachable
return: ; preds = %while.body
ret i8* %p3
}
-------------------------- b.ll ----------------------------
declare void @_Z1fv() local_unnamed_addr #2
@i = global i8 0, align 1
define i8* @_Z1gPcS_S_(i8* nocapture readonly %d, i8* %h, i8* readnone
returned %p3) local_unnamed_addr #3 {
entry:
br label %while.cond
while.cond: ; preds = %cleanup.cont,
%entry
%h.addr.0 = phi i8* [ %h, %entry ], [ %add.ptr4, %cleanup.cont ]
%d.addr.0 = phi i8* [ %d, %entry ], [ %add.ptr3, %cleanup.cont ]
%cmp = icmp ugt i8* %h.addr.0, @i
br i1 %cmp, label %while.end, label %while.body
while.body: ; preds = %while.cond
%0 = bitcast i8* %d.addr.0 to i64*
%1 = load i64, i64* %0, align 1
%2 = bitcast i8* %h.addr.0 to i64*
store i64 %1, i64* %2, align 1
%add.ptr = getelementptr inbounds i8, i8* %d.addr.0, i64 8
%3 = bitcast i8* %add.ptr to i64*
%4 = load i64, i64* %3, align 1
store i64 %4, i64* %2, align 1
%add.ptr4 = getelementptr inbounds i8, i8* %h.addr.0, i64 6
%cmp5 = icmp ult i8* %add.ptr4, %p3
br i1 %cmp5, label %cleanup.cont, label %return
cleanup.cont: ; preds = %while.body
%add.ptr3 = getelementptr inbounds i8, i8* %d.addr.0, i64 6
br label %while.cond
while.end: ; preds = %while.cond
tail call void @_Z1fv()
unreachable
return: ; preds = %while.body
ret i8* %p3
}
The only difference between a.ll and b.ll is the basicblock cleanup.cont.
-------------------------- a.ll after loop rotate, same as a.ll before loop
rotate ----------------------------
~/workarea/llvm-r318298/dbuild/bin/opt -loop-rotate -S < a.ll
; ModuleID = '<stdin>'
source_filename = "<stdin>"
@i = global i8 0, align 1
declare void @_Z1fv() local_unnamed_addr
define i8* @_Z1gPcS_S_(i8* nocapture readonly %d, i8* %h, i8* readnone
returned %p3) local_unnamed_addr {
entry:
br label %while.cond
while.cond: ; preds = %while.body,
%entry
%h.addr.0 = phi i8* [ %h, %entry ], [ %add.ptr4, %while.body ]
%d.addr.0 = phi i8* [ %d, %entry ], [ %add.ptr3, %while.body ]
%cmp = icmp ugt i8* %h.addr.0, @i
br i1 %cmp, label %while.end, label %while.body
while.body: ; preds = %while.cond
%0 = bitcast i8* %d.addr.0 to i64*
%1 = load i64, i64* %0, align 1
%2 = bitcast i8* %h.addr.0 to i64*
store i64 %1, i64* %2, align 1
%add.ptr = getelementptr inbounds i8, i8* %d.addr.0, i64 8
%3 = bitcast i8* %add.ptr to i64*
%4 = load i64, i64* %3, align 1
store i64 %4, i64* %2, align 1
%add.ptr3 = getelementptr inbounds i8, i8* %d.addr.0, i64 6
%add.ptr4 = getelementptr inbounds i8, i8* %h.addr.0, i64 6
%cmp5 = icmp ult i8* %add.ptr4, %p3
br i1 %cmp5, label %while.cond, label %return
while.end: ; preds = %while.cond
tail call void @_Z1fv()
unreachable
return: ; preds = %while.body
ret i8* %p3
}
-------------------------- b.ll after loop rotate
----------------------------
~/workarea/llvm-r318298/dbuild/bin/opt -loop-rotate -S < b.ll
@i = global i8 0, align 1
declare void @_Z1fv() local_unnamed_addr
define i8* @_Z1gPcS_S_(i8* nocapture readonly %d, i8* %h, i8* readnone
returned %p3) local_unnamed_addr {
entry:
%cmp1 = icmp ugt i8* %h, @i
br i1 %cmp1, label %while.end, label %while.body.lr.ph
while.body.lr.ph: ; preds = %entry
br label %while.body
while.cond: ; preds = %while.body
%h.addr.0 = phi i8* [ %add.ptr4, %while.body ]
%d.addr.0 = phi i8* [ %add.ptr3, %while.body ]
%cmp = icmp ugt i8* %h.addr.0, @i
br i1 %cmp, label %while.cond.while.end_crit_edge, label %while.body
while.body: ; preds = %
while.body.lr.ph, %while.cond
%d.addr.03 = phi i8* [ %d, %while.body.lr.ph ], [ %d.addr.0, %while.cond ]
%h.addr.02 = phi i8* [ %h, %while.body.lr.ph ], [ %h.addr.0, %while.cond ]
%0 = bitcast i8* %d.addr.03 to i64*
%1 = load i64, i64* %0, align 1
%2 = bitcast i8* %h.addr.02 to i64*
store i64 %1, i64* %2, align 1
%add.ptr = getelementptr inbounds i8, i8* %d.addr.03, i64 8
%3 = bitcast i8* %add.ptr to i64*
%4 = load i64, i64* %3, align 1
store i64 %4, i64* %2, align 1
%add.ptr4 = getelementptr inbounds i8, i8* %h.addr.02, i64 6
%cmp5 = icmp ult i8* %add.ptr4, %p3
%add.ptr3 = getelementptr inbounds i8, i8* %d.addr.03, i64 6
br i1 %cmp5, label %while.cond, label %return
while.cond.while.end_crit_edge: ; preds = %while.cond
br label %while.end
while.end: ; preds =
%while.cond.while.end_crit_edge, %entry
tail call void @_Z1fv()
unreachable
return: ; preds = %while.body
ret i8* %p3
}
a.ll and b.ll have different results after loop rotation because of
http://llvm.org/viewvc/llvm-project?view=revision&revision=181230
<https://www.google.com/url?q=http://llvm.org/viewvc/llvm-project?view%3Drevision%26revision%3D181230&sa=D&usg=AFQjCNHIQDnlfGByPF-pvV991MH72_ExNg>
-------------------------- a.s generated from a.ll
----------------------------
~/workarea/llvm-r318298/dbuild/bin/opt -loop-rotate -S < a.ll
|~/workarea/llvm-r318298/dbuild/bin/llc
.cfi_startproc
# BB#0: # %entry
pushq %rax
.cfi_def_cfa_offset 16
movl $i, %eax
.p2align 4, 0x90
.LBB0_1: # %while.cond
# =>This Inner Loop Header: Depth=1
cmpq %rax, %rsi
ja .LBB0_4
# BB#2: # %while.body
# in Loop: Header=BB0_1 Depth=1
movq (%rdi), %rcx
movq %rcx, (%rsi)
movq 8(%rdi), %rcx
movq %rcx, (%rsi)
addq $6, %rdi
addq $6, %rsi
cmpq %rdx, %rsi
jb .LBB0_1
# BB#3: # %return
movq %rdx, %rax
popq %rcx
retq
.LBB0_4: # %while.end
callq _Z1fv
.Lfunc_end0:
.size _Z1gPcS_S_, .Lfunc_end0-_Z1gPcS_S_
.cfi_endproc
call _Z1fv is unreachable. Suppose loop LBB0_1 has few iterations, a.s will
contain mostly fall through branches.
-------------------------- b.s generated from b.ll
----------------------------
~/workarea/llvm-r318298/dbuild/bin/opt -loop-rotate -S < b.ll
|~/workarea/llvm-r318298/dbuild/bin/llc
.cfi_startproc
# BB#0: # %entry
pushq %rax
.cfi_def_cfa_offset 16
movl $i, %eax
cmpq %rax, %rsi
ja .LBB0_5
# BB#1:
movl $i, %eax
.p2align 4, 0x90
.LBB0_3: # %while.body
# =>This Inner Loop Header: Depth=1
movq (%rdi), %rcx
movq %rcx, (%rsi)
movq 8(%rdi), %rcx
movq %rcx, (%rsi)
addq $6, %rsi
cmpq %rdx, %rsi
jae .LBB0_4
# BB#2: # %while.cond
# in Loop: Header=BB0_3 Depth=1
addq $6, %rdi
cmpq %rax, %rsi
jbe .LBB0_3
.LBB0_5: # %while.end
callq _Z1fv
.LBB0_4: # %return
movq %rdx, %rax
popq %rcx
retq
.Lfunc_end0:
.size _Z1gPcS_S_, .Lfunc_end0-_Z1gPcS_S_
.cfi_endproc
call _Z1fv is unreachable. Here we have "jae .LBB0_4" which will not fall
through when exiting the loop. The non-fall-through branch increases branch
misses significantly and regresses the benchmark by 10%.
Now a possible way to fix it is to duplicate basicblock .LBB0_3, just like
what tail duplication does, but basicblock .LBB0_3 contains 7 instructions
and it will introduce some cost of code size increase.
Any suggestion to fix the issue are welcomed!
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20171218/0fe56494/attachment.html>
More information about the llvm-dev
mailing list