PHINode: introduce setIncomingValueForBlock() function, and use it.

[Whitney]

Summary

There is PHINode::getBasicBlockIndex() and PHINode::setIncomingValue() but no function to replace incoming value for a specified BasicBlock* predecessor.
Clearly, there are a lot of places that could use that functionality.

[fhahn]

llvm/include/llvm/IR/Instructions.h

2729 ↗

(On Diff #204779)

can this just be

int Idx = getBasicBlockIndex(BB);
assert(Idx >= 0 && "Invalid basic block argument!");
return setIncomingValue(Idx, V);

similar to getIncomingValueForBlock above?

[Whitney]

llvm/include/llvm/IR/Instructions.h

2729 ↗

(On Diff #204779)

I thought of doing that, but sometimes a phi node may have multiple operands of the same incoming block (not sure why). I am using a similar code pattern as in replaceIncomingBlockWith().

[fhahn]

llvm/include/llvm/IR/Instructions.h

2729 ↗

(On Diff #204779)

Ah right. I think it is worth mentioning in the doc comment that it will replace all values coming from BB?

For the places that use getbasicBlockIndex, this is not a NFC I think, as they would only replace the incoming value of the first occurrence.

[Whitney]

llvm/include/llvm/IR/Instructions.h

2729 ↗

(On Diff #204779)

Removed [NFC] from the title. And updated the comment.

[Meinersbur]

LGTM, please wait for @fhahn's ok as well.

llvm/include/llvm/IR/Instructions.h

2677 ↗

(On Diff #204801)

[nit] unrelated

2733 ↗

(On Diff #204801)

[suggestion] assert when no matching block was found?

2729 ↗

(On Diff #204779)

It's not forbidden and sometimes cannot even be simplified by fusing edges, e.g. a switch with multiple values branching to the same block.

Unfortunately for the PHI it is indistinguishable which of the switch cases was taken. That means, all of the incoming values from the same block should be the same. This patch may actually fix some bugs where only one of the incoming values was changed.

[fhahn]

LGTM, thanks for updating. I think it would be good to add an assertion as Micheal suggested, as we have similar ones in related functions.

[Whitney]

Added the assert. Thanks for the reviews.

llvm/trunk/include/llvm/IR/Instructions.h

public:
   }
 
   void setIncomingBlock(unsigned i, BasicBlock *BB) {
     assert(BB && "PHI node got a null basic block!");
     block_begin()[i] = BB;
   }
 
   /// Replace every incoming basic block \p Old to basic block \p New.
-  void replaceIncomingBlockWith(BasicBlock *Old, BasicBlock *New) {
+  void replaceIncomingBlockWith(const BasicBlock *Old, BasicBlock *New) {
     assert(New && Old && "PHI node got a null basic block!");
     for (unsigned Op = 0, NumOps = getNumOperands(); Op != NumOps; ++Op)
       if (getIncomingBlock(Op) == Old)
         setIncomingBlock(Op, New);
   }
 
   /// Add an incoming value to the end of the PHI list
   ///
public:
   }
 
   Value *getIncomingValueForBlock(const BasicBlock *BB) const {
     int Idx = getBasicBlockIndex(BB);
     assert(Idx >= 0 && "Invalid basic block argument!");
     return getIncomingValue(Idx);
   }
 
+  /// Set every incoming value(s) for block \p BB to \p V.
+  void setIncomingValueForBlock(const BasicBlock *BB, Value *V) {
+    assert(BB && "PHI node got a null basic block!");
+    bool Found = false;
+    for (unsigned Op = 0, NumOps = getNumOperands(); Op != NumOps; ++Op)
+      if (getIncomingBlock(Op) == BB) {
+        Found = true;
+        setIncomingValue(Op, V);
+      }
+    assert(Found && "Invalid basic block argument to set!");
+  }
+
   /// If the specified PHI node always merges together the
   /// same value, return the value, otherwise return null.
   Value *hasConstantValue() const;
 
   /// Whether the specified PHI node always merges
   /// together the same value, assuming undefs are equal to a unique
   /// non-undef value.
   bool hasConstantOrUndefValue() const;

llvm/trunk/lib/CodeGen/SafeStack.cpp

while (!AI->use_empty()) {
       else
         InsertBefore = User;
 
       IRBuilder<> IRBUser(InsertBefore);
       Value *Off = IRBUser.CreateGEP(Int8Ty, BasePointer, // BasePointer is i8*
                                      ConstantInt::get(Int32Ty, -Offset));
       Value *Replacement = IRBUser.CreateBitCast(Off, AI->getType(), Name);
 
-      if (auto *PHI = dyn_cast<PHINode>(User)) {
+      if (auto *PHI = dyn_cast<PHINode>(User))
         // PHI nodes may have multiple incoming edges from the same BB (why??),
         // all must be updated at once with the same incoming value.
-        auto *BB = PHI->getIncomingBlock(U);
-        for (unsigned I = 0; I < PHI->getNumIncomingValues(); ++I)
-          if (PHI->getIncomingBlock(I) == BB)
-            PHI->setIncomingValue(I, Replacement);
-      } else {
+        PHI->setIncomingValueForBlock(PHI->getIncomingBlock(U), Replacement);
+      else
         U.set(Replacement);
-      }
-    }
 
     AI->eraseFromParent();
   }
 
   // Re-align BasePointer so that our callees would see it aligned as
   // expected.
   // FIXME: no need to update BasePointer in leaf functions.
   unsigned FrameSize = alignTo(SSL.getFrameSize(), StackAlignment);

llvm/trunk/lib/Transforms/Scalar/GVN.cpp

for (BasicBlock *P : Preds) {
 
       if (isCriticalEdge(P->getTerminator(), GetSuccessorNumber(P, B))) {
         if (BasicBlock *S = splitCriticalEdges(P, B))
           DeadBlocks.insert(P = S);
       }
 
       for (BasicBlock::iterator II = B->begin(); isa<PHINode>(II); ++II) {
         PHINode &Phi = cast<PHINode>(*II);
-        Phi.setIncomingValue(Phi.getBasicBlockIndex(P),
-                             UndefValue::get(Phi.getType()));
+        Phi.setIncomingValueForBlock(P, UndefValue::get(Phi.getType()));
         if (MD)
           MD->invalidateCachedPointerInfo(&Phi);
       }
     }
   }
 }
 
 // If the given branch is recognized as a foldable branch (i.e. conditional

llvm/trunk/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

LoopConstrainer::RewrittenRangeInfo LoopConstrainer::changeIterationSpaceEnd(
   return RRI;
 }
 
 void LoopConstrainer::rewriteIncomingValuesForPHIs(
     LoopStructure &LS, BasicBlock *ContinuationBlock,
     const LoopConstrainer::RewrittenRangeInfo &RRI) const {
   unsigned PHIIndex = 0;
   for (PHINode &PN : LS.Header->phis())
-    for (unsigned i = 0, e = PN.getNumIncomingValues(); i < e; ++i)
-      if (PN.getIncomingBlock(i) == ContinuationBlock)
-        PN.setIncomingValue(i, RRI.PHIValuesAtPseudoExit[PHIIndex++]);
+    PN.setIncomingValueForBlock(ContinuationBlock,
+                                RRI.PHIValuesAtPseudoExit[PHIIndex++]);
 
   LS.IndVarStart = RRI.IndVarEnd;
 }
 
 BasicBlock *LoopConstrainer::createPreheader(const LoopStructure &LS,
                                              BasicBlock *OldPreheader,
                                              const char *Tag) const {
   BasicBlock *Preheader = BasicBlock::Create(Ctx, Tag, &F, LS.Header);

llvm/trunk/lib/Transforms/Scalar/LoopUnswitch.cpp

for (User *U : LIC->users()) {
     new UnreachableInst(Context, Abort);
     // Force the new case destination to branch to the "unreachable"
     // block while maintaining a (dead) CFG edge to the old block.
     NewSISucc->getTerminator()->eraseFromParent();
     BranchInst::Create(Abort, OldSISucc,
                        ConstantInt::getTrue(Context), NewSISucc);
     // Release the PHI operands for this edge.
     for (PHINode &PN : NewSISucc->phis())
-      PN.setIncomingValue(PN.getBasicBlockIndex(Switch),
-                          UndefValue::get(PN.getType()));
+      PN.setIncomingValueForBlock(Switch, UndefValue::get(PN.getType()));
     // Tell the domtree about the new block. We don't fully update the
     // domtree here -- instead we force it to do a full recomputation
     // after the pass is complete -- but we do need to inform it of
     // new blocks.
     DT->addNewBlock(Abort, NewSISucc);
   }
 
   SimplifyCode(Worklist, L);

llvm/trunk/lib/Transforms/Scalar/StructurizeCFG.cpp

for (const auto &PI : Map) {
       for (const auto &VI : PI.second) {
         Updater.AddAvailableValue(VI.first, VI.second);
         Dominator.addAndRememberBlock(VI.first);
       }
 
       if (!Dominator.resultIsRememberedBlock())
         Updater.AddAvailableValue(Dominator.result(), Undef);
 
-      for (BasicBlock *FI : From) {
-        int Idx = Phi->getBasicBlockIndex(FI);
-        assert(Idx != -1);
-        Phi->setIncomingValue(Idx, Updater.GetValueAtEndOfBlock(FI));
-      }
+      for (BasicBlock *FI : From)
+        Phi->setIncomingValueForBlock(FI, Updater.GetValueAtEndOfBlock(FI));
     }
 
     DeletedPhis.erase(To);
   }
   assert(DeletedPhis.empty());
 
   // Simplify any phis inserted by the SSAUpdater if possible
   bool Changed;

llvm/trunk/lib/Transforms/Utils/LoopUnrollPeel.cpp

#endif
   // from the last peeled-off iteration instead of the preheader.
   for (BasicBlock::iterator I = Header->begin(); isa<PHINode>(I); ++I) {
     PHINode *PHI = cast<PHINode>(I);
     Value *NewVal = PHI->getIncomingValueForBlock(Latch);
     Instruction *LatchInst = dyn_cast<Instruction>(NewVal);
     if (LatchInst && L->contains(LatchInst))
       NewVal = LVMap[LatchInst];
 
-    PHI->setIncomingValue(PHI->getBasicBlockIndex(NewPreHeader), NewVal);
+    PHI->setIncomingValueForBlock(NewPreHeader, NewVal);
   }
 
   // Adjust the branch weights on the loop exit.
   if (ExitWeight) {
     // The backedge count is the difference of current header weight and
     // current loop exit weight. If the current header weight is smaller than
     // the current loop exit weight, we mark the loop backedge weight as 1.
     uint64_t BackEdgeWeight = 0;

llvm/trunk/lib/Transforms/Utils/LoopUnrollRuntime.cpp

for (PHINode &PN : Succ->phis()) {
       }
       // Adding a value to the new PHI node from the last prolog block
       // that was created.
       NewPN->addIncoming(V, PrologLatch);
 
       // Update the existing PHI node operand with the value from the
       // new PHI node.  How this is done depends on if the existing
       // PHI node is in the original loop block, or the exit block.
-      if (L->contains(&PN)) {
-        PN.setIncomingValue(PN.getBasicBlockIndex(NewPreHeader), NewPN);
-      } else {
+      if (L->contains(&PN))
+        PN.setIncomingValueForBlock(NewPreHeader, NewPN);
+      else
         PN.addIncoming(NewPN, PrologExit);
-      }
-    }
-  }
 
   // Make sure that created prolog loop is in simplified form
   SmallVector<BasicBlock *, 4> PrologExitPreds;
   Loop *PrologLoop = LI->getLoopFor(PrologLatch);
   if (PrologLoop) {
     for (BasicBlock *PredBB : predecessors(PrologExit))
       if (PrologLoop->contains(PredBB))
         PrologExitPreds.push_back(PredBB);
for (PHINode &PN : Succ->phis()) {
       // Adding a value to the new PHI node from the unrolling loop preheader.
       NewPN->addIncoming(PN.getIncomingValueForBlock(NewPreHeader), PreHeader);
       // Adding a value to the new PHI node from the unrolling loop latch.
       NewPN->addIncoming(PN.getIncomingValueForBlock(Latch), Latch);
 
       // Update the existing PHI node operand with the value from the new PHI
       // node.  Corresponding instruction in epilog loop should be PHI.
       PHINode *VPN = cast<PHINode>(VMap[&PN]);
-      VPN->setIncomingValue(VPN->getBasicBlockIndex(EpilogPreHeader), NewPN);
+      VPN->setIncomingValueForBlock(EpilogPreHeader, NewPN);
     }
   }
 
   Instruction *InsertPt = NewExit->getTerminator();
   IRBuilder<> B(InsertPt);
   Value *BrLoopExit = B.CreateIsNotNull(ModVal, "lcmp.mod");
   assert(Exit && "Loop must have a single exit block only");
   // Split the epilogue exit to maintain loop canonicalization guarantees

llvm/trunk/lib/Transforms/Utils/SimplifyCFG.cpp

if (BI->isConditional()) {
           if (PBI_C->isOne()) {
             Instruction *NotCond = cast<Instruction>(
                 Builder.CreateNot(PBI->getCondition(), "not.cond"));
             MergedCond = cast<Instruction>(Builder.CreateBinOp(
                 Instruction::Or, NotCond, MergedCond, "or.cond"));
           }
         }
         // Update PHI Node.
-        PHIs[i]->setIncomingValue(PHIs[i]->getBasicBlockIndex(PBI->getParent()),
-                                  MergedCond);
+  PHIs[i]->setIncomingValueForBlock(PBI->getParent(), MergedCond);
       }
 
       // PBI is changed to branch to TrueDest below. Remove itself from
       // potential phis from all other successors.
       if (MSSAU)
         MSSAU->changeCondBranchToUnconditionalTo(PBI, TrueDest);
 
       // Change PBI from Conditional to Unconditional.

llvm/trunk/lib/Transforms/Vectorize/LoopVectorize.cpp

if (OrigPhi == OldInduction) {
       EndValue->setName("ind.end");
     }
 
     // The new PHI merges the original incoming value, in case of a bypass,
     // or the value at the end of the vectorized loop.
     BCResumeVal->addIncoming(EndValue, MiddleBlock);
 
     // Fix the scalar body counter (PHI node).
-    unsigned BlockIdx = OrigPhi->getBasicBlockIndex(ScalarPH);
-
     // The old induction's phi node in the scalar body needs the truncated
     // value.
     for (BasicBlock *BB : LoopBypassBlocks)
       BCResumeVal->addIncoming(II.getStartValue(), BB);
-    OrigPhi->setIncomingValue(BlockIdx, BCResumeVal);
+    OrigPhi->setIncomingValueForBlock(ScalarPH, BCResumeVal);
   }
 
   // We need the OrigLoop (scalar loop part) latch terminator to help
   // produce correct debug info for the middle block BB instructions.
   // The legality check stage guarantees that the loop will have a single
   // latch.
   assert(isa<BranchInst>(OrigLoop->getLoopLatch()->getTerminator()) &&
          "Scalar loop latch terminator isn't a branch");
void InnerLoopVectorizer::fixFirstOrderRecurrence(PHINode *Phi) {
   // Fix the initial value of the original recurrence in the scalar loop.
   Builder.SetInsertPoint(&*LoopScalarPreHeader->begin());
   auto *Start = Builder.CreatePHI(Phi->getType(), 2, "scalar.recur.init");
   for (auto *BB : predecessors(LoopScalarPreHeader)) {
     auto *Incoming = BB == LoopMiddleBlock ? ExtractForScalar : ScalarInit;
     Start->addIncoming(Incoming, BB);
   }
 
-  Phi->setIncomingValue(Phi->getBasicBlockIndex(LoopScalarPreHeader), Start);
+  Phi->setIncomingValueForBlock(LoopScalarPreHeader, Start);
   Phi->setName("scalar.recur");
 
   // Finally, fix users of the recurrence outside the loop. The users will need
   // either the last value of the scalar recurrence or the last value of the
   // vector recurrence we extracted in the middle block. Since the loop is in
   // LCSSA form, we just need to find all the phi nodes for the original scalar
   // recurrence in the exit block, and then add an edge for the middle block.
   for (PHINode &LCSSAPhi : LoopExitBlock->phis()) {