[SCCP] Add support for insertelement instructions

[davide]

Summary

The support was already there, but it was commented out, and didn't get some cases right, e.g. the one where either idx or elt being undef.

[davide]

Also, added test cases for all these cases (at least the one I thought of)

[eli.friedman]

I think you're misunderstanding what "isUndefined" means... it means "we haven't computed the value of this instruction yet", not "this value is an UndefValue". See https://www.cs.rice.edu/~keith/512/2011/Lectures/L19-SCCP-1up.pdf and http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.4146&rep=rep1&type=pdf .

[davide]

In D22186#479403, @eli.friedman wrote:

I think you're misunderstanding what "isUndefined" means... it means "we haven't computed the value of this instruction yet", not "this value is an UndefValue". See https://www.cs.rice.edu/~keith/512/2011/Lectures/L19-SCCP-1up.pdf and http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.4146&rep=rep1&type=pdf .

Yes, I was confused.. the code actually in some places uses isUndefined() as synonim to undef which now I see why it's completely wrong... I'd like to rename isUndefined() to isUnknown(), which is what Keith Cooper uses in the slides, what do you think?

[eli.friedman]

Sure, that's fine (in a separate commit, of course).

[davide]

In D22186#479404, @davide wrote:

In D22186#479403, @eli.friedman wrote:

I think you're misunderstanding what "isUndefined" means... it means "we haven't computed the value of this instruction yet", not "this value is an UndefValue". See https://www.cs.rice.edu/~keith/512/2011/Lectures/L19-SCCP-1up.pdf and http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.105.4146&rep=rep1&type=pdf .

Yes, I was confused.. the code actually in some places uses isUndefined() as synonim to undef which now I see why it's completely wrong... I'd like to rename isUndefined() to isUnknown(), which is what Keith Cooper uses in the slides, what do you think?

In D22186#479414, @eli.friedman wrote:

Sure, that's fine (in a separate commit, of course).

I also went forward and removed all the dead vector code b38095fbc8454f96e9d4ff88db28769cba741f71 which used isUndefined() wrongly

lib/Transforms/Scalar/SCCP.cpp

     markOverdefined(&I);
   else if(ValState.isConstant() && IdxState.isConstant())
     markConstant(&I, ConstantExpr::getExtractElement(ValState.getConstant(),
                                                      IdxState.getConstant()));
 #endif
 }
 
 void SCCPSolver::visitInsertElementInst(InsertElementInst &I) {
-  // TODO : SCCP does not handle vectors properly.
-  return markOverdefined(&I);
-#if 0
   LatticeVal &ValState = getValueState(I.getOperand(0));
   LatticeVal &EltState = getValueState(I.getOperand(1));
   LatticeVal &IdxState = getValueState(I.getOperand(2));
 
   if (ValState.isOverdefined() || EltState.isOverdefined() ||
       IdxState.isOverdefined())
-    markOverdefined(&I);
-  else if(ValState.isConstant() && EltState.isConstant() &&
-          IdxState.isConstant())
-    markConstant(&I, ConstantExpr::getInsertElement(ValState.getConstant(),
-                                                    EltState.getConstant(),
-                                                    IdxState.getConstant()));
-  else if (ValState.isUndefined() && EltState.isConstant() &&
-           IdxState.isConstant())
-    markConstant(&I,ConstantExpr::getInsertElement(UndefValue::get(I.getType()),
-                                                   EltState.getConstant(),
-                                                   IdxState.getConstant()));
-#endif
+    return markOverdefined(&I);
+
+  // Creating a new vector.
+  // Example: insertelement <1 x i64> undef, i64 27, i32 0
+  //  -> <1 x i64> <i64 27>
+  if (ValState.isUndefined())
+    return markConstant(
+        &I,
+        ConstantExpr::getInsertElement(
+            UndefValue::get(I.getType()),
+            EltState.isUndefined() ? UndefValue::get(I.getOperand(1)->getType())
+                                   : EltState.getConstant(),
+            IdxState.isUndefined() ? UndefValue::get(I.getOperand(2)->getType())
+                                   : IdxState.getConstant()));
+  // Inserting into an existing vector.
+  // Example: %vec = <2 x i64> <i64 1, i64 undef>
+  // insertelement <2 x i64> %vec, i64 42, i32 1 ->
+  //   <2 x i64> <i64 1, i64 42>
+  if (ValState.isConstant())
+    return markConstant(
+        &I,
+        ConstantExpr::getInsertElement(
+            ValState.getConstant(),
+            EltState.isUndefined() ? UndefValue::get(I.getOperand(1)->getType())
+                                   : EltState.getConstant(),
+            IdxState.isUndefined() ? UndefValue::get(I.getOperand(2)->getType())
+                                   : IdxState.getConstant()));
+  markOverdefined(&I);
 }
 
 void SCCPSolver::visitShuffleVectorInst(ShuffleVectorInst &I) {
   // TODO : SCCP does not handle vectors properly.
   return markOverdefined(&I);
 #if 0
   LatticeVal &V1State   = getValueState(I.getOperand(0));
   LatticeVal &V2State   = getValueState(I.getOperand(1));

test/Transforms/SCCP/insertelement.ll

+; RUN: opt < %s -sccp -S | FileCheck %s
+
+; CHECK-LABEL: @insertelement
+define <4 x i64> @insertelement() {
+  %vec1 = insertelement <4 x i64> undef, i64 -1, i32 0
+  %vec2 = insertelement <4 x i64> %vec1, i64 -2, i32 1
+  %vec3 = insertelement <4 x i64> %vec2, i64 -3, i32 2
+  %vec4 = insertelement <4 x i64> %vec3, i64 -4, i32 3
+  ; CHECK: ret <4 x i64> <i64 -1, i64 -2, i64 -3, i64 -4>
+  ret <4 x i64> %vec4
+}
+
+; CHECK-LABEL: @insertelement_undef
+define <4 x i64> @insertelement_undef() {
+  %vec1 = insertelement <4 x i64> undef, i64 -1, i32 0
+  %vec2 = insertelement <4 x i64> %vec1, i64 -2, i32 1
+  %vec3 = insertelement <4 x i64> %vec2, i64 -3, i32 2
+  %vec4 = insertelement <4 x i64> %vec3, i64 -4, i32 3
+  %vec5 = insertelement <4 x i64> %vec3, i64 -5, i32 4
+  ; CHECK: ret <4 x i64> undef
+  ret <4 x i64> %vec5
+}
+
+define <1 x i64> @insertelement_undef_idx1() {
+  ; Out-of-bounds index -> fold to undef
+  %vec1 = insertelement <1 x i64> undef, i64 42, i32 27
+  ret <1 x i64> %vec1
+  ; CHECK: ret <1 x i64> undef
+}
+
+define <2 x i64> @insertelement_undef_idx2() {
+  ; Undef index -> fold to undef
+  %vec1 = insertelement <2 x i64> undef, i64 42, i32 undef
+  %vec2 = insertelement <2 x i64> %vec1, i64 666, i32 undef
+  ret <2 x i64> %vec2
+  ; CHECK: ret <2 x i64> undef
+}
+
+define <2 x i64> @insertelement_undef_elem() {
+  ; Undef elem -> fold to undef
+  %vec1 = insertelement <2 x i64> undef, i64 undef, i32 0
+  %vec2 = insertelement <2 x i64> %vec1, i64 undef, i32 1
+  ret <2 x i64> %vec2
+  ; CHECK: ret <2 x i64> undef
+}