[llvm-bugs] [Bug 25387] New: SCEV update problem

[via llvm-bugs]

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

            Bug ID: 25387
           Summary: SCEV update problem
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Global Analyses
          Assignee: unassignedbugs at nondot.org
          Reporter: wmi at google.com
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

For the following testcase 1.c:
long a[1000], M, N;

void foo() {
  long i, j;
  for (i = 0; i < N; i++)
    for (j = 0; j < M; j++)
      a[i + j] = i + j;
}

Build command:
~/llvm-r243664/build/bin/clang -O2 -S 1.c

The IR before loop vectorization is:
***********************************************
for.cond.1.preheader:                             ; preds =
%for.cond.1.preheader.lr.ph, %for.inc.5
  %i.018 = phi i64 [ 0, %for.cond.1.preheader.lr.ph ], [ %inc6, %for.inc.5 ]
  br i1 %cmp2.15, label %for.body.3.preheader, label %for.inc.5

for.body.3.preheader:                             ; preds =
%for.cond.1.preheader
  br label %for.body.3

for.body.3:                                       ; preds =
%for.body.3.preheader, %for.body.3
  %j.016 = phi i64 [ %inc, %for.body.3 ], [ 0, %for.body.3.preheader ]
  %add = add nuw nsw i64 %j.016, %i.018
  ...
  %inc = add nuw nsw i64 %j.016, 1
  %exitcond = icmp eq i64 %inc, %1
  br i1 %exitcond, label %for.inc.5.loopexit, label %for.body.3

for.inc.5.loopexit:                               ; preds = %for.body.3
  br label %for.inc.5

for.inc.5:                                        ; preds =
%for.inc.5.loopexit, %for.cond.1.preheader
  %inc6 = add nuw nsw i64 %i.018, 1
  %cmp = icmp slt i64 %inc6, %0
  br i1 %cmp, label %for.cond.1.preheader, label %for.end.7.loopexit
***********************************************

For value %j.016 in loop for.body.3,
  %j.016 = phi i64 [ %inc, %for.body.3 ], [ 0, %for.body.3.preheader ],
call SE->getSCEV(%j.016)->dump() in gdb, the SCEV is:
  {0,+,1}<nuw><nsw><%for.body.3>
The SCEV is correct.

After loop vectorization, %j.016 is changed. The SCEV of %j.016 should be
updated and reflect the change.
***********************************************
for.cond.1.preheader:                             ; preds =
%for.cond.1.preheader.lr.ph, %for.inc.5
  %i.018 = phi i64 [ 0, %for.cond.1.preheader.lr.ph ], [ %inc6, %for.inc.5 ]
  ......
vector.body:                                      ; preds = %vector.body,
%vector.ph
  ...
  br i1 %3, label %middle.block, label %vector.body, !llvm.loop !5

middle.block:                                     ; preds = %vector.body,
%overflow.checked
  %resume.val = phi i64 [ 0, %overflow.checked ], [ %end.idx.rnd.down,
%vector.body ]
  %trunc.resume.val = phi i64 [ 0, %overflow.checked ], [ %end.idx.rnd.down,
%vector.body ]
  %cmp.n = icmp eq i64 %end.idx, %resume.val
  br i1 %cmp.n, label %for.inc.5.loopexit, label %scalar.ph

scalar.ph:                                        ; preds = %middle.block,
%for.body.3.preheader
  %bc.resume.val = phi i64 [ %resume.val, %middle.block ], [ 0,
%for.body.3.preheader ]
  %bc.trunc.resume.val = phi i64 [ %trunc.resume.val, %middle.block ], [ 0,
%for.body.3.preheader ]
  br label %for.body.3

for.body.3:                                       ; preds = %scalar.ph,
%for.body.3
  %j.016 = phi i64 [ %inc, %for.body.3 ], [ %bc.trunc.resume.val, %scalar.ph ]
  %add = add nuw nsw i64 %j.016, %i.018
  %arrayidx = getelementptr inbounds [1000 x i64], [1000 x i64]* @a, i64 0, i64
%add
  store i64 %add, i64* %arrayidx, align 8, !tbaa !1
  %inc = add nuw nsw i64 %j.016, 1
  %exitcond = icmp eq i64 %inc, %1
  br i1 %exitcond, label %for.inc.5.loopexit, label %for.body.3

for.inc.5:                                        ; preds =
%for.inc.5.loopexit, %for.cond.1.preheader
  %inc6 = add nuw nsw i64 %i.018, 1
  %cmp = icmp slt i64 %inc6, %0
  br i1 %cmp, label %for.cond.1.preheader, label %for.end.7.loopexit
***********************************************

For value %j.016 in loop for.body.3,
  %j.016 = phi i64 [ %inc, %for.body.3 ], [ %bc.trunc.resume.val, %scalar.ph ]
call SE->getSCEV(%j.016)->dump() in gdb, the SCEV is:
  {0,+,1}<nuw><nsw><%for.body.3>
The SCEV is probably wrong since it has no change during vectorization.

The problem is probably caused by an outdated ValueExprMap in ScalarEvolution.
If we call SE->ValueExprMap.clear() to clean the SCEV cache, and then call
SE->getSCEV(%j.016)->dump() in gdb again, the SCEV is:
{%bc.trunc.resume.val,+,1}<nuw><nsw><%for.body.3>. This is the correct SCEV.

-- 
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/20151102/65579d0e/attachment.html>