[LLVMbugs] [Bug 24248] New: Scalarizer generates incorrect code

[bugzilla-daemon at llvm.org]

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

            Bug ID: 24248
           Summary: Scalarizer generates incorrect code
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Scalar Optimizations
          Assignee: unassignedbugs at nondot.org
          Reporter: fraser at codeplay.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

I think it's best to explain this with an example program.

C-like pseudo code:

void foo(int x) {
  int2 pos = { 0, x };
  pos.y++;
  for (int i = 0; i < 1; ++i) {
    pos.y++;
  }
}

LLVM IR:

define void @foo(i32 %x) {
entry:
  %vecinit = insertelement <2 x i32> <i32 0, i32 0>, i32 %x, i32 1
  %inc = add i32 %x, 1
  %0 = insertelement <2 x i32> %vecinit, i32 %inc, i32 1
  br label %loop

loop:                                        ; preds = %loop, %entry
  %pos = phi <2 x i32> [ %0, %entry ], [ %new.pos.y, %loop ]
  %i = phi i32 [ 0, %entry ], [ %new.i, %loop ]
  %pos.y = extractelement <2 x i32> %pos, i32 1
  %inc.pos.y = add i32 %pos.y, 1
  %new.pos.y = insertelement <2 x i32> %pos, i32 %inc.pos.y, i32 1
  %new.i = add i32 %i, 1
  %cmp2 = icmp slt i32 %new.i, 1
  br i1 %cmp2, label %loop, label %exit

exit:                                        ; preds = %loop
  ret void
}

Note that the vector %pos is (0, %inc) when it enters the loop. Now, if we run
the scalarizer on this program:

opt -scalarizer -S -o - test.ll

define void @foo(i32 %x) {
entry:
  %vecinit = insertelement <2 x i32> zeroinitializer, i32 %x, i32 1
  %inc = add i32 %x, 1
  %0 = insertelement <2 x i32> %vecinit, i32 %inc, i32 1
  br label %loop

loop:                                             ; preds = %loop, %entry
  %pos.i0 = phi i32 [ 0, %entry ], [ %pos.i01, %loop ]
  %pos.i1 = phi i32 [ %x, %entry ], [ %inc.pos.y, %loop ]
  %i = phi i32 [ 0, %entry ], [ %new.i, %loop ]
  %pos.upto0 = insertelement <2 x i32> undef, i32 %pos.i0, i32 0
  %pos = insertelement <2 x i32> %pos.upto0, i32 %pos.i1, i32 1
  %pos.y = extractelement <2 x i32> %pos, i32 1
  %inc.pos.y = add i32 %pos.y, 1
  %new.pos.y = insertelement <2 x i32> %pos, i32 %inc.pos.y, i32 1
  %pos.i01 = extractelement <2 x i32> %pos, i32 0
  %new.i = add i32 %i, 1
  %cmp2 = icmp slt i32 %new.i, 1
  br i1 %cmp2, label %loop, label %exit

exit:                                             ; preds = %loop
  ret void
}

The scalarizer has scalarized %pos to be (0, %x) when it enters the loop,
instead of (0, %inc). The first operand to the second PHI should be %inc, not
%x.

>From what I've observed while debugging, the bug is in Scatterer::operator[].

What happens is that when scalarizing the PHI, it first deals with element 0.
For this, it walks up the chain of insertelement instructions to find the value
to substitute.

The first insertelement instruction it finds, %0, inserts %inc to element 1. It
caches %inc in CV[1]. Since it hasn't found element 0 yet, it walks up to
%vecinit. This again inserts into element 1, this time %x. It then caches %x in
CV[1], overwriting %inc. Since it still hasn't found element 0, it walks up to
the initializer and returns zero.

Then it scalarizes element 1. It checks its cache and finds CV[1], which is %x.
It uses that in the new PHI instruction. This is the problem. The cache is
overwritten when walking a series of insertelement instructions that don't deal
with the element it's actually searching for.

Perhaps it should only cache elements it's not searching for if they're not
already cached? This would mean the latest insertelement instruction is always
used.

-- 
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/20150724/f53c7cfe/attachment.html>