From 779046e433004f8b21e672ea7585aa6cb98a3f8d Mon Sep 17 00:00:00 2001
From: Fraser Cormack <fraser@codeplay.com>
Date: Mon, 10 Aug 2015 14:48:47 +0000
Subject: [PATCH] Prevent the scalarizer from caching incorrect entries

The scalarizer can cache incorrect entries when walking up a chain of
insertelement instructions. This occurs when it encounters more than one
instruction that it is not actively searching for, as it unconditionally caches
every element it finds. The fix is to only cache the first element that it
isn't searching for so we don't overwrite correct entries.

Reviewers: hfinkel

Differential Revision: http://reviews.llvm.org/D11559


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@244448 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/Scalar/Scalarizer.cpp    | 10 +++++++--
 test/Transforms/Scalarizer/cache-bug.ll | 30 +++++++++++++++++++++++++
 2 files changed, 38 insertions(+), 2 deletions(-)
 create mode 100644 test/Transforms/Scalarizer/cache-bug.ll

diff --git a/lib/Transforms/Scalar/Scalarizer.cpp b/lib/Transforms/Scalar/Scalarizer.cpp
index 3b8307c4316..c99f13be6a9 100644
--- a/lib/Transforms/Scalar/Scalarizer.cpp
+++ b/lib/Transforms/Scalar/Scalarizer.cpp
@@ -227,10 +227,16 @@ Value *Scatterer::operator[](unsigned I) {
       if (!Idx)
         break;
       unsigned J = Idx->getZExtValue();
-      CV[J] = Insert->getOperand(1);
       V = Insert->getOperand(0);
-      if (I == J)
+      if (I == J) {
+        CV[J] = Insert->getOperand(1);
         return CV[J];
+      } else if (!CV[J]) {
+        // Only cache the first entry we find for each index we're not actively
+        // searching for. This prevents us from going too far up the chain and
+        // caching incorrect entries.
+        CV[J] = Insert->getOperand(1);
+      }
     }
     CV[I] = Builder.CreateExtractElement(V, Builder.getInt32(I),
                                          V->getName() + ".i" + Twine(I));
diff --git a/test/Transforms/Scalarizer/cache-bug.ll b/test/Transforms/Scalarizer/cache-bug.ll
new file mode 100644
index 00000000000..f8c2d100d59
--- /dev/null
+++ b/test/Transforms/Scalarizer/cache-bug.ll
@@ -0,0 +1,30 @@
+; RUN: opt -scalarizer -S < %s | FileCheck %s
+target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
+
+
+; Check that vector element 1 is scalarized correctly from a chain of
+; insertelement instructions
+define void @func(i32 %x) {
+; CHECK-LABEL: @func(
+; CHECK-NOT: phi i32 [ %x, %entry ], [ %inc.pos.y, %loop ]
+; CHECK:     phi i32 [ %inc, %entry ], [ %inc.pos.y, %loop ]
+; CHECK:   ret void
+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:
+  %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:
+  ret void
+}
-- 
2.34.1