[BitcodeReader] Delay select until all constants resolved

[guopeilin]

Summary

Like the shuffle, we should treat the select delayed so that all constants can be resolved.

[efriedma]

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

2722

Maybe it would simplify the algorithm if you ValueList.getConstantFwdRef(NextCstNo, CurTy); here? That way, indexing into ValueList later would never fail.

[guopeilin]

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

2722

Ok,thanks for reviewing. A new patch updated.

[guopeilin]

Pinging reviewers ...

[efriedma]

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

2360

SelectorTy is always i1; no need to store it here.

llvm/lib/Bitcode/Reader/ValueList.cpp

155 ↗

(On Diff #370867)

Why is this change necessary? If we're sticking a value into ResolveConstants that isn't a placeholder, something has gone wrong, I think.

[guopeilin]

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

2360

fixed

llvm/lib/Bitcode/Reader/ValueList.cpp

155 ↗

(On Diff #370867)

In the previous patch, which we parse select repeatedly, will generate some cases that placeholder become the exact RealVal.
However, in the new patch, this is not need any more.

[efriedma]

LGTM

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

struct DelayedShufTy {
     VectorType *OpTy;
     VectorType *RTy;
     uint64_t Op0Idx;
     uint64_t Op1Idx;
     uint64_t Op2Idx;
     unsigned CstNo;
   };
   std::vector<DelayedShufTy> DelayedShuffles;
+  struct DelayedSelTy {
+    Type *OpTy;
+    uint64_t Op0Idx;
+    uint64_t Op1Idx;
+    uint64_t Op2Idx;
+    unsigned CstNo;
+  };
+  std::vector<DelayedSelTy> DelayedSelectors;
+
   while (true) {
     Expected<BitstreamEntry> MaybeEntry = Stream.advanceSkippingSubblocks();
     if (!MaybeEntry)
       return MaybeEntry.takeError();
     BitstreamEntry Entry = MaybeEntry.get();
 
     switch (Entry.Kind) {
     case BitstreamEntry::SubBlock: // Handled for us already.
case BitstreamEntry::EndBlock:
         Constant *Op2 = ValueList.getConstantFwdRef(Op2Idx, ShufTy);
         if (!ShuffleVectorInst::isValidOperands(Op0, Op1, Op2))
           return error("Invalid shufflevector operands");
         SmallVector<int, 16> Mask;
         ShuffleVectorInst::getShuffleMask(Op2, Mask);
         Value *V = ConstantExpr::getShuffleVector(Op0, Op1, Mask);
         ValueList.assignValue(V, CstNo);
       }
+      for (auto &DelayedSelector : DelayedSelectors) {
+        Type *OpTy = DelayedSelector.OpTy;
+        Type *SelectorTy = Type::getInt1Ty(Context);
+        uint64_t Op0Idx = DelayedSelector.Op0Idx;
+        uint64_t Op1Idx = DelayedSelector.Op1Idx;
+        uint64_t Op2Idx = DelayedSelector.Op2Idx;
+        uint64_t CstNo = DelayedSelector.CstNo;
+        Constant *Op1 = ValueList.getConstantFwdRef(Op1Idx, OpTy);
+        Constant *Op2 = ValueList.getConstantFwdRef(Op2Idx, OpTy);
+        // The selector might be an i1 or an <n x i1>
+        // Get the type from the ValueList before getting a forward ref.
+        if (VectorType *VTy = dyn_cast<VectorType>(OpTy)) {
+          Value *V = ValueList[Op0Idx];
+          assert(V);
+          if (SelectorTy != V->getType())
+            SelectorTy = VectorType::get(SelectorTy, VTy->getElementCount());
+        }
+        Constant *Op0 = ValueList.getConstantFwdRef(Op0Idx, SelectorTy);
+        Value *V = ConstantExpr::getSelect(Op0, Op1, Op2);
+        ValueList.assignValue(V, CstNo);
+      }
 
       if (NextCstNo != ValueList.size())
         return error("Invalid constant reference");
 
       ValueList.resolveConstantForwardRefs();
       return Error::success();
     case BitstreamEntry::Record:
       // The interesting case.
case bitc::CST_CODE_CE_GEP_WITH_INRANGE_INDEX: { // [ty, flags, n x
       V = ConstantExpr::getGetElementPtr(PointeeType, Elts[0], Indices,
                                          InBounds, InRangeIndex);
       break;
     }
     case bitc::CST_CODE_CE_SELECT: {  // CE_SELECT: [opval#, opval#, opval#]
       if (Record.size() < 3)
         return error("Invalid record");
 
-      Type *SelectorTy = Type::getInt1Ty(Context);
-
-      // The selector might be an i1, an <n x i1>, or a <vscale x n x i1>
-      // Get the type from the ValueList before getting a forward ref.
-      if (VectorType *VTy = dyn_cast<VectorType>(CurTy))
-        if (Value *V = ValueList[Record[0]])
-          if (SelectorTy != V->getType())
-            SelectorTy = VectorType::get(SelectorTy,
-                                         VTy->getElementCount());
-
-      V = ConstantExpr::getSelect(ValueList.getConstantFwdRef(Record[0],
-                                                              SelectorTy),
-                                  ValueList.getConstantFwdRef(Record[1],CurTy),
-                                  ValueList.getConstantFwdRef(Record[2],CurTy));
-      break;
+      DelayedSelectors.push_back(
+          {CurTy, Record[0], Record[1], Record[2], NextCstNo});
+      (void)ValueList.getConstantFwdRef(NextCstNo, CurTy);
+      ++NextCstNo;
+      continue;
     }
     case bitc::CST_CODE_CE_EXTRACTELT
         : { // CE_EXTRACTELT: [opty, opval, opty, opval]
       if (Record.size() < 3)
         return error("Invalid record");
       VectorType *OpTy =
         dyn_cast_or_null<VectorType>(getTypeByID(Record[0]));
       if (!OpTy)

llvm/test/Bitcode/bitcode-parseconstant-delay-select.ll

+; RUN: llvm-as < %s -preserve-bc-uselistorder=false | llvm-dis -disable-output
+@a = external dso_local global i32, align 4
+@c = external dso_local global [3 x i32], align 4
+@b = external dso_local local_unnamed_addr global i32, align 4
+
+define dso_local i32 @main() local_unnamed_addr {
+middle.block:
+  br label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %middle.block
+  store i32 extractelement (<4 x i32> select (<4 x i1> select (<4 x i1> <i1 icmp sle (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 0), i1 icmp sle (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 0), i1 icmp sle (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 0), i1 icmp sle (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 0)>, <4 x i1> <i1 icmp sge (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 0), i1 icmp sge (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 0), i1 icmp sge (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 0), i1 icmp sge (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 0)>, <4 x i1> zeroinitializer), <4 x i32> zeroinitializer, <4 x i32> select (<4 x i1> select (<4 x i1> <i1 icmp sgt (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 0), i1 icmp sgt (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 0), i1 icmp sgt (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 0), i1 icmp sgt (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 0)>, <4 x i1> <i1 icmp eq (i32 sdiv (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 3), i32 0), i1 icmp eq (i32 sdiv (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 3), i32 0), i1 icmp eq (i32 sdiv (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 3), i32 0), i1 icmp eq (i32 sdiv (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 3), i32 0)>, <4 x i1> zeroinitializer), <4 x i32> <i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32)>, <4 x i32> <i32 lshr (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 31), i32 lshr (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 31), i32 lshr (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 31), i32 lshr (i32 zext (i1 icmp eq (i32* getelementptr inbounds ([3 x i32], [3 x i32]* @c, i64 0, i64 2), i32* @a) to i32), i32 31)>)), i32 3), i32* @b, align 4
+  ret i32 undef
+}