[rs4gc] Simplify code by cloning existing instructions when inserting base chain [NFC]

[reames]

Summary

This is nfc, but just complicated I wanted a separate set of eyes. The motivation is a) cleaner code, and b) reducing some spurious test changes in D98315.

Previously we created a new node, then filled in the pieces. Now, we clone the existing node, then change the respective fields. The only change in handling is with phis since we have to handle multiple incoming edges from the same block a bit differently.

[skatkov]

As I see the difference between old and new behavior is as follows:
Before we created new instruction which are not constructed yet (PHI node and verifier will complain if we missed anything) or are initialized with undefs.
Now we just create a new instructions containing the same values as derived pointer.

In both cases, later we fill the new instructions with detected bases. If there is not bugs the result should be the same.
In case we missed anything in the old case we get undef and with this patch we get old value.

If we take into account the patch https://reviews.llvm.org/D98315 which may skip setting second operand for ShuffleVector, with this patch
we can get the second operand equal to the old value instead of undef. I do not see how bad it can be but it is a difference.
So the main difference I see is related to ShuffleVector but not phi.

Not sure but original way seems a bit more protective than new one,
What kind of "some spurious test changes" do you observe?

Generally I do not have strong preference what is better, so I'm ok with this patch.

[reames]

In D98316#2627960, @skatkov wrote:

< ...

So the main difference I see is related to ShuffleVector but not phi.

Not sure but original way seems a bit more protective than new one,
What kind of "some spurious test changes" do you observe?

For the phi case, the new pattern is actually safer. Consider the case where we miss an operand. With the old code, we'd have a syntactically valid phi node with the wrong input. With the new code, the verifier would reject the phi as it would be missing an operand.

You're right that (combined with the later change) the primary effect is reusing the second operand of the shuffle. It turns out I'd screwed up the diffs I'd posted. I'd posted that change *without* being rebased on this one. The diffs I'd been concerned about was the use of undef operands (as opposed to the original operand). What is very unclear to my now, is why I thought that was a bad thing. :)

I ended up landing this with a change to explicitly use undef for the second operand of a broadcast. That's entirely NFC, and frankly, looks cleaner to me now. Now sure what I was thinking when I first posted this.

[skatkov]

For the phi case, the new pattern is actually safer. Consider the case where we miss an operand. With the old code, we'd have a syntactically valid phi node with the wrong input. With the new code, the verifier would reject the phi as it would be missing an operand.

May be I'm missing something but to me it looks opposite :)
In case some operand is missed, old code will produce incorrect phi node while new one will contain wrong input...

[reames]

In D98316#2630701, @skatkov wrote:

For the phi case, the new pattern is actually safer. Consider the case where we miss an operand. With the old code, we'd have a syntactically valid phi node with the wrong input. With the new code, the verifier would reject the phi as it would be missing an operand.

May be I'm missing something but to me it looks opposite :)
In case some operand is missed, old code will produce incorrect phi node while new one will contain wrong input...

The key difference is between setIncomingValue and addIncomingValue. If incorrect, the new code will fail to add an incoming edge. That will produce a PHI which immediately fails verification.

llvm/lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

for (auto Pair : States) {
     // Since we're joining a vector and scalar base, they can never be the
     // same.  As a result, we should always see insert element having reached
     // the conflict state.
     assert(!isa<InsertElementInst>(I) || State.isConflict());
 
     if (!State.isConflict())
       continue;
 
-    /// Create and insert a new instruction which will represent the base of
-    /// the given instruction 'I'.
-    auto MakeBaseInstPlaceholder = [](Instruction *I) -> Instruction* {
+    auto getMangledName = [](Instruction *I) -> std::string {
       if (isa<PHINode>(I)) {
-        BasicBlock *BB = I->getParent();
-        int NumPreds = pred_size(BB);
-        assert(NumPreds > 0 && "how did we reach here");
-        std::string Name = suffixed_name_or(I, ".base", "base_phi");
-        return PHINode::Create(I->getType(), NumPreds, Name, I);
-      } else if (SelectInst *SI = dyn_cast<SelectInst>(I)) {
-        // The undef will be replaced later
-        UndefValue *Undef = UndefValue::get(SI->getType());
-        std::string Name = suffixed_name_or(I, ".base", "base_select");
-        return SelectInst::Create(SI->getCondition(), Undef, Undef, Name, SI);
-      } else if (auto *EE = dyn_cast<ExtractElementInst>(I)) {
-        UndefValue *Undef = UndefValue::get(EE->getVectorOperand()->getType());
-        std::string Name = suffixed_name_or(I, ".base", "base_ee");
-        return ExtractElementInst::Create(Undef, EE->getIndexOperand(), Name,
-                                          EE);
-      } else if (auto *IE = dyn_cast<InsertElementInst>(I)) {
-        UndefValue *VecUndef = UndefValue::get(IE->getOperand(0)->getType());
-        UndefValue *ScalarUndef = UndefValue::get(IE->getOperand(1)->getType());
-        std::string Name = suffixed_name_or(I, ".base", "base_ie");
-        return InsertElementInst::Create(VecUndef, ScalarUndef,
-                                         IE->getOperand(2), Name, IE);
+        return suffixed_name_or(I, ".base", "base_phi");
+      } else if (isa<SelectInst>(I)) {
+        return suffixed_name_or(I, ".base", "base_select");
+      } else if (isa<ExtractElementInst>(I)) {
+        return suffixed_name_or(I, ".base", "base_ee");
+      } else if (isa<InsertElementInst>(I)) {
+        return suffixed_name_or(I, ".base", "base_ie");
       } else {
-        auto *SV = cast<ShuffleVectorInst>(I);
-        UndefValue *VecUndef = UndefValue::get(SV->getOperand(0)->getType());
-        std::string Name = suffixed_name_or(I, ".base", "base_sv");
-        return new ShuffleVectorInst(VecUndef, VecUndef, SV->getShuffleMask(),
-                                     Name, SV);
+        return suffixed_name_or(I, ".base", "base_sv");
       }
     };
-    Instruction *BaseInst = MakeBaseInstPlaceholder(I);
+
+    Instruction *BaseInst = I->clone();
+    BaseInst->insertBefore(I);
+    BaseInst->setName(getMangledName(I));
     // Add metadata marking this as a base value
     BaseInst->setMetadata("is_base_value", MDNode::get(I->getContext(), {}));
     States[I] = BDVState(I, BDVState::Conflict, BaseInst);
   }
 
 #ifndef NDEBUG
   VerifyStates();
 #endif
assert((!isKnownBaseResult(BDV) ||
             !areBothVectorOrScalar(BDV, State.getBaseValue())) &&
            "why did it get added?");
     assert(!State.isUnknown() && "Optimistic algorithm didn't complete!");
     if (!State.isConflict())
       continue;
 
     if (PHINode *BasePHI = dyn_cast<PHINode>(State.getBaseValue())) {
       PHINode *PN = cast<PHINode>(BDV);
-      unsigned NumPHIValues = PN->getNumIncomingValues();
+      const unsigned NumPHIValues = PN->getNumIncomingValues();
+
+      // The IR verifier requires phi nodes with multiple entries from the
+      // same basic block to have the same incoming value for each of those
+      // entries.  Since we're inserting bitcasts in the loop, make sure we
+      // do so at least once per incoming block.
+      DenseMap<BasicBlock *, Value*> BlockToValue;
       for (unsigned i = 0; i < NumPHIValues; i++) {
         Value *InVal = PN->getIncomingValue(i);
         BasicBlock *InBB = PN->getIncomingBlock(i);
-
-        // If we've already seen InBB, add the same incoming value
-        // we added for it earlier.  The IR verifier requires phi
-        // nodes with multiple entries from the same basic block
-        // to have the same incoming value for each of those
-        // entries.  If we don't do this check here and basephi
-        // has a different type than base, we'll end up adding two
-        // bitcasts (and hence two distinct values) as incoming
-        // values for the same basic block.
-
-        int BlockIndex = BasePHI->getBasicBlockIndex(InBB);
-        if (BlockIndex != -1) {
-          Value *OldBase = BasePHI->getIncomingValue(BlockIndex);
-          BasePHI->addIncoming(OldBase, InBB);
-
+        if (!BlockToValue.count(InBB))
+          BlockToValue[InBB] = getBaseForInput(InVal, InBB->getTerminator());
+        else {
 #ifndef NDEBUG
+          Value *OldBase = BlockToValue[InBB];
           Value *Base = getBaseForInput(InVal, nullptr);
           // In essence this assert states: the only way two values
           // incoming from the same basic block may be different is by
           // being different bitcasts of the same value.  A cleanup
           // that remains TODO is changing findBaseOrBDV to return an
           // llvm::Value of the correct type (and still remain pure).
           // This will remove the need to add bitcasts.
           assert(Base->stripPointerCasts() == OldBase->stripPointerCasts() &&
                  "Sanity -- findBaseOrBDV should be pure!");
 #endif
-          continue;
         }
-
-        // Find the instruction which produces the base for each input.  We may
-        // need to insert a bitcast in the incoming block.
-        // TODO: Need to split critical edges if insertion is needed
-        Value *Base = getBaseForInput(InVal, InBB->getTerminator());
-        BasePHI->addIncoming(Base, InBB);
+        Value *Base = BlockToValue[InBB];
+        BasePHI->setIncomingValue(i, Base);
       }
-      assert(BasePHI->getNumIncomingValues() == NumPHIValues);
     } else if (SelectInst *BaseSI =
                    dyn_cast<SelectInst>(State.getBaseValue())) {
       SelectInst *SI = cast<SelectInst>(BDV);
 
       // Find the instruction which produces the base for each input.
       // We may need to insert a bitcast.
       BaseSI->setTrueValue(getBaseForInput(SI->getTrueValue(), BaseSI));
       BaseSI->setFalseValue(getBaseForInput(SI->getFalseValue(), BaseSI));
#endif
       auto UpdateOperand = [&](int OperandIdx) {
         Value *InVal = BdvSV->getOperand(OperandIdx);
         Value *Base = getBaseForInput(InVal, BaseSV);
         BaseSV->setOperand(OperandIdx, Base);
       };
       UpdateOperand(0); // vector operand
       if (!BdvSV->isZeroEltSplat())
         UpdateOperand(1); // vector operand
+      else {
+        // Never read, so just use undef
+        Value *InVal = BdvSV->getOperand(1);
+        BaseSV->setOperand(1, UndefValue::get(InVal->getType()));
+      }
     }
   }
 
 #ifndef NDEBUG
   VerifyStates();
 #endif
 
   // Cache all of our results so we can cheaply reuse them