[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

2734

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

2734

Ok,thanks for reviewing. A new patch updated.

[guopeilin]

Pinging reviewers ...

[efriedma]

llvm/lib/Bitcode/Reader/BitcodeReader.cpp

2358

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

llvm/lib/Bitcode/Reader/ValueList.cpp

155–156

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

2358

fixed

llvm/lib/Bitcode/Reader/ValueList.cpp

155–156

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;
+    Type *SelectorTy;
+    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::Error:
       return error("Malformed block");
-    case BitstreamEntry::EndBlock:
+    case BitstreamEntry::EndBlock: {
       // Once all the constants have been read, go through and resolve forward
       // references.
       //
       // We have to treat shuffles specially because they don't have three
       // operands anymore.  We need to convert the shuffle mask into an array,
       // and we can't convert a forward reference.
       for (auto &DelayedShuffle : DelayedShuffles) {
         VectorType *OpTy = DelayedShuffle.OpTy;
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);
       }
+      std::vector<int> DelayedSelectorsSet(DelayedSelectors.size(), 1);
+      while (true) {
+        for (size_t i = 0; i < DelayedSelectors.size(); ++i) {
+          auto &DelayedSelector = DelayedSelectors[i];
+          Type *OpTy = DelayedSelector.OpTy;
+          Type *SelectorTy = DelayedSelector.SelectorTy;
+          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))
+            if (Value *V = ValueList[Op0Idx]) {
+              DelayedSelectorsSet[i] = 0;
+              if (SelectorTy != V->getType())
+                SelectorTy =
+                    VectorType::get(SelectorTy, VTy->getElementCount());
+            } else {
+              continue;
+            }
+          Constant *Op0 = ValueList.getConstantFwdRef(Op0Idx, SelectorTy);
+          Value *V = ConstantExpr::getSelect(Op0, Op1, Op2);
+          ValueList.assignValue(V, CstNo);
+        }
+        if (all_of(DelayedSelectorsSet.begin(), DelayedSelectorsSet.end(),
+                   [](int i) { return i == 0; })) {
+          break;
+        }
+      }
 
       if (NextCstNo != ValueList.size())
         return error("Invalid constant reference");
 
       ValueList.resolveConstantForwardRefs();
       return Error::success();
+    }
     case BitstreamEntry::Record:
       // The interesting case.
       break;
     }
 
     // Read a record.
     Record.clear();
     Type *VoidType = Type::getVoidTy(Context);
case bitc::CST_CODE_CE_GEP_WITH_INRANGE_INDEX: { // [ty, flags, n x
                                          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, SelectorTy, Record[0], Record[1],
+                                  Record[2], NextCstNo});
+      ++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/lib/Bitcode/Reader/ValueList.cpp

void BitcodeReaderValueList::resolveConstantForwardRefs() {
   llvm::sort(ResolveConstants);
 
   SmallVector<Constant *, 64> NewOps;
 
   while (!ResolveConstants.empty()) {
     Value *RealVal = operator[](ResolveConstants.back().second);
     Constant *Placeholder = ResolveConstants.back().first;
     ResolveConstants.pop_back();
-
+    if (Placeholder == RealVal)
+      continue;
     // Loop over all users of the placeholder, updating them to reference the
     // new value.  If they reference more than one placeholder, update them all
     // at once.
     while (!Placeholder->use_empty()) {
       auto UI = Placeholder->user_begin();
       User *U = *UI;
 
       // If the using object isn't uniqued, just update the operands.  This

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
+}