[llvm-bugs] [Bug 39814] New: SCCP generates wrong code for ssa_copy

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=39814

            Bug ID: 39814
           Summary: SCCP generates wrong code for ssa_copy
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: carrot at google.com
                CC: llvm-bugs at lists.llvm.org

Compile following code with 

opt test.ll -S -ipsccp

define void @foo(i64*, i64) {
entry:
  %address = getelementptr inbounds i64, i64* %0, i64 2
  %cond3 = icmp eq i64 %1, 10
  br i1 %cond3, label %loop_header, label %exit

loop_header:
  %v23 = phi i64 [ %ivar, %loop_last ], [ 0, %entry ]
  %v25 = getelementptr inbounds i64, i64* %0, i64 %v23
  %v26 = load i64, i64* %v25, align 4
  %v27 = and i64 %v26, 1879048192
  %cond2 = icmp eq i64 %v27, 1610612736
  br i1 %cond2, label %loop_2, label %exit

loop_2:
  %ivar = add nuw nsw i64 %v23, 1
  %cond1 = icmp eq i64 %v26, %ivar
  br i1 %cond1, label %dont_delete, label %exit

dont_delete:
  br label %loop_last

loop_last:
  %loop_cond = icmp ult i64 %ivar, 10
  br i1 %loop_cond, label %loop_header, label %loop_exit

loop_exit:
  store i64 %v27, i64* %address, align 8
  br label %exit

exit:
  ret void
}

I got:

define void @foo(i64*, i64) {
entry:
  %address = getelementptr inbounds i64, i64* %0, i64 2
  %cond3 = icmp eq i64 %1, 10
  br i1 %cond3, label %loop_header, label %exit

loop_header:                                      ; preds = %loop_last, %entry
  %v23 = phi i64 [ 1, %loop_last ], [ 0, %entry ]        // WRONG!
  %v25 = getelementptr inbounds i64, i64* %0, i64 %v23
  %v26 = load i64, i64* %v25, align 4
  %v27 = and i64 %v26, 1879048192
  %cond2 = icmp eq i64 %v27, 1610612736
  br i1 %cond2, label %loop_2, label %exit

loop_2:                                           ; preds = %loop_header
  %ivar = add nuw nsw i64 %v23, 1
  %cond1 = icmp eq i64 %v26, %ivar
  br i1 %cond1, label %dont_delete, label %exit

dont_delete:                                      ; preds = %loop_2
  br label %loop_last

loop_last:                                        ; preds = %dont_delete
  %loop_cond = icmp ult i64 %ivar, 10
  br i1 %loop_cond, label %loop_header, label %loop_exit

loop_exit:                                        ; preds = %loop_last
  store i64 1610612736, i64* %address, align 8
  br label %exit

exit:                                             ; preds = %loop_exit,
%loop_2, %loop_header, %entry
  ret void
}

Note that

   %v23 = phi i64 [ 1, %loop_last ], [ 0, %entry ]

the value comes from BB %loop_last should not be constant 1.


The problem is, when ssa_copy is inserted, we have

%ivar = add nuw nsw i64 %v23, 1
  ...
%ivar.0 = call i64 @llvm.ssa.copy.93825120544720(i64 %ivar)
  ...
%ivar.0.1 = call i64 @llvm.ssa.copy.93825120544720(i64 %ivar.0)

When llvm is processing the last instruction in function
SCCPSolver::visitCallSite, it uses constant information from the first
instruction.

return (void)mergeInValue(IV, I, getValueState(PBranch->OriginalOp));

At this time we have:

(gdb) p I->dump()
  %ivar.0.1 = call i64 @llvm.ssa.copy.93825120544720(i64 %ivar.0)
$6 = void
(gdb) p CopyOf->dump()
  %ivar.0 = call i64 @llvm.ssa.copy.93825120544720(i64 %ivar)
(gdb) p PBranch->OriginalOp->dump()
  %ivar = add nuw nsw i64 %v23, 1

Basically the last instruction is a copy of %ivar.0, which is a copy of %ivar,
so which instruction is used to get constant information doesn't matter too
much, so current implementation uses the first instruction. But the problem is
the last instruction is not a direct user of the first instruction, so when the
constant information of %ivar is updated, the last instruction isn't updated
accordingly. So the correct fix should tell SCCP that I is a user of
PBranch->OriginalOp:
    addAdditionalUser(PBranch->OriginalOp, I);

On the other hand, when computing the constant information of the second
instruction, it combines guarded condition information, so in theory it may
have more precise information than first instruction. So I think a better fix
is:
   return (void)mergeInValue(IV, I, OriginalVal);

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20181127/0da2bf55/attachment.html>