[IR] BasicBlock updatePHIs function for updating predecessors

[Marandil]

Summary

[IR] Add a function to update all PHI nodes within the block to change incoming values from IncomingOld to IncomingNew if IncomingOld is no longer a valid predecessor, or add new incoming edges in PHI nodes with IncomingNew otherwise.

The rationale behind this function is the amount of PHI node updates in my IR-based implementation of Jump Maps.

I've added a few unit tests for the function.

[• dberlin]

lib/IR/BasicBlock.cpp

449

I'm not sure this loop is necessary.
If this funciton is how to update phi edges, you should guarantee an input state.
IE either pred edges removed or not removed.

457

This should be an assert

466

Can you explain why?
This seems like a bug?

[• dberlin]

lib/IR/BasicBlock.cpp

464

It should be an assert that the old predecessor existed in the phi

468

This will put the phi arguments out of order with the predecessors, which is smoethign we would like to avoid.

470

I looked at the code for this function, and i don't see why it would fail.
Can you explain?

[Marandil]

lib/IR/BasicBlock.cpp

466

Consider this:

switch (a) {
  default: BB0;
  case 0: BB0;
  case 1: BB1;
  case 2: BB2;
  case 19: BB0;
  case 20: BB1;
  case 21: BB2;
}

changed into:

if (0 <= a <=2) {
  switch (a) {
    default: unreachable;
    case 0: BB0;
    case 1: BB1;
    case 2: BB2;
  }
} else {
  switch (a-19) {
    default: BB0;
    case 0: BB0;
    case 1: BB1;
    case 2: BB2;
  }
}

For BB0 a single predecessor changed into 2 different possible predecessors, that should share the same incoming value.

[• dberlin]

That just m

lib/IR/BasicBlock.cpp

466

That just makes me believe the API specification for this function is confusing.
Either your goal is to update all phis from one block to another, or it isn't.
In the above, you aren't.

[Marandil]

lib/IR/BasicBlock.cpp

466

The specification says:

/// \brief Replace (or add) occurrences of IncomingOld in PHIs with IncomingNew,
/// depending on whether or not IncomingOld is still a valid predecessor.

Consider a shorter example:

BB0:
  br i1 %0, label %BB2, label %BB2
BB1:
  br label %BB2
BB2:
  %1 = phi i32 [0, %BB0], [1, %BB1]
  ret i32 %1

Now, I modify the second edge of the br in BB0 (oblivious on the dest of the first one)

BB0:
  br i1 %0, label %BB2, label %BB3
BB1:
  br label %BB2
BB2:
  %1 = phi i32 [0, %BB0], [1, %BB1]
  ret i32 %1
BB3:
  br label %BB0

Obviously, the PHI node in BB2 is now invalid, as BB3->BB2 is another valid edge; so we need to update it:

BB0:
  br i1 %0, label %BB2, label %BB3
BB1:
  br label %BB2
BB2:
  %1 = phi i32 [0, %BB0], [1, %BB1], [0, %BB3]
  ret i32 %1
BB3:
  br label %BB0

The function is supposed to detect whether or not a new value in PHI should be added and it is inclined in the description.

[• dberlin]

lib/IR/BasicBlock.cpp

466

I understand you have documented what it does.
I'm saying
A. "what it does" seems very specific to your use case
B. What it does in a specific case is not easy to understand just from looking at the call.
C. It is not what i would expect from a function named "updatephis" , I would expect such a thing to do *either* addition *or* replacement, not "add/replac depending on a bunch of variables and factors"
etc

IE This function seems incredibly specific to your case of updating.

I can say for certain in all the phi updating i've encountered, it would not be usable or useful.
A one to one replacement function would be useful (IE replace old with new)
An "add new edge to every phi" would be useful.
A function that tries to combine them and do something depending on other state that isn't passed - not so much.

But i'm going to leave it to others to see if they think this functionality is useful.
I can only request if they do, you don't call it "updatephis" because that is a very generic name for something that is quite specific.

[Marandil]

lib/IR/BasicBlock.cpp

466

How about splitting the current function into two, one for each case + one helper that detects the case and uses the appropriate version?
I have actually encountered this behavior several times with switch instructions (IR-level range splitting, etc) so I don't want to "keep it for myself".
Regarding the name: what name(s) would you propose? I have originally called this function fixPHIs, but later decided to rename it to updatePHIs. Maybe you have better suggestions.

[Marandil]

I have changed checks to asserts as requested.

[Marandil]

Follow up in https://reviews.llvm.org/D34283.

include/llvm/IR/BasicBlock.h

public:
 
   /// \brief Return the landingpad instruction associated with the landing pad.
   const LandingPadInst *getLandingPadInst() const;
   LandingPadInst *getLandingPadInst() {
     return const_cast<LandingPadInst *>(
                     static_cast<const BasicBlock *>(this)->getLandingPadInst());
   }
 
+  /// \brief Replace (or add) occurrences of IncomingOld in PHIs with IncomingNew,
+  /// depending on whether or not IncomingOld is still a valid predecessor.
+  void updatePHIs(BasicBlock* IncomingOld,
+                  BasicBlock* IncomingNew);
+
 private:
   /// \brief Increment the internal refcount of the number of BlockAddresses
   /// referencing this BasicBlock by \p Amt.
   ///
   /// This is almost always 0, sometimes one possibly, but almost never 2, and
   /// inconceivably 3 or more.
   void AdjustBlockAddressRefCount(int Amt) {
     setValueSubclassData(getSubclassDataFromValue()+Amt);

lib/IR/BasicBlock.cpp

 #include "SymbolTableListTraitsImpl.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/IntrinsicInst.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Type.h"
+#include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 
 using namespace llvm;
 
 ValueSymbolTable *BasicBlock::getValueSymbolTable() {
   if (Function *F = getParent())
     return F->getValueSymbolTable();
   return nullptr;

 bool BasicBlock::isLandingPad() const {
   return isa<LandingPadInst>(getFirstNonPHI());
 }
 
 /// Return the landingpad instruction associated with the landing pad.
 const LandingPadInst *BasicBlock::getLandingPadInst() const {
   return dyn_cast<LandingPadInst>(getFirstNonPHI());
 }
+
+
+/// Find all PHI nodes and depending on whether OldIncoming is a valid
+/// predecessor, add NewIncoming with the same value as OldIncoming, or change
+/// the incoming links on them.
+void BasicBlock::updatePHIs(BasicBlock* IncomingOld,
+                            BasicBlock* IncomingNew) {
+  // Iterate over predecessors of BB; mark if any of them is IncomingOld or
+  // IncomingNew.
+  bool oldPredecessor = false;
+  bool newPredecessor = false;
+  for (BasicBlock *Pred : predecessors(this)) {
+    if (Pred == IncomingOld)
+      oldPredecessor = true;
+    if (Pred == IncomingNew)
+      newPredecessor = true;
+  }
+  // If new is not a predecessor, issue warning and return.
+  if (!newPredecessor) {
+    errs() << "WARNING: attempting to update PHI predecessor for block with no "
+              "such predecessor\n";
+    return;
+  }
+
+  for (auto &PHI : this->phis()) {
+    int incoming = PHI.getBasicBlockIndex(IncomingOld);
+    if (incoming >= 0) {
+      if (oldPredecessor) {
+        // Cannot just change the incoming when IncomingOld is still valid,
+        // need to insert another value with the same incoming value.
+        PHI.addIncoming(PHI.getIncomingValue(incoming), IncomingNew);
+      } else {
+        PHI.setIncomingBlock(incoming, IncomingNew);
+      }
+    }
+  }
+}

unittests/IR/BasicBlockTest.cpp

 //===- llvm/unittest/IR/BasicBlockTest.cpp - BasicBlock unit tests --------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/NoFolder.h"
+#include "llvm/Support/SourceMgr.h"
 #include "gmock/gmock-matchers.h"
 #include "gtest/gtest.h"
 #include <memory>
 
 namespace llvm {
 namespace {
 
 TEST(BasicBlockTest, PhiRange) {
TEST(BasicBlockTest, PhiRange) {
   // And iterate a const range.
   for (const auto &PN : const_cast<const BasicBlock *>(BB.get())->phis()) {
     EXPECT_EQ(BB.get(), PN.getIncomingBlock(0));
     EXPECT_EQ(BB1.get(), PN.getIncomingBlock(1));
     EXPECT_EQ(BB2.get(), PN.getIncomingBlock(2));
   }
 }
 
+class BasicBlockPhiTest : public ::testing::Test
+{
+protected:
+  LLVMContext C;
+
+  // Create a somewhat complex function with a couple of basic blocks and a
+  // single phi node.
+  const char *ModuleString = "define i32 @f(i32 %x) {\n"
+                             "bb0:\n"
+                             "  switch i32 %x, label %bb1 [\n"
+                             "         i32 2,  label %bb2\n"
+                             "         i32 3,  label %bb3\n"
+                             "         i32 4,  label %bb4]\n"
+                             "bb1:\n"
+                             "  br label %bb5\n"
+                             "bb2:\n"
+                             "  br label %bb5\n"
+                             "bb3:\n"
+                             "  br label %bb5\n"
+                             "bb4:\n"
+                             "  br label %bb5\n"
+                             "bb5:\n"
+                             "  %r = phi i32 [ 0, %bb1 ],\n"
+                             "               [ 1, %bb2 ],\n"
+                             "               [ 2, %bb3 ],\n"
+                             "               [ 3, %bb4 ]\n"
+                             "  ret i32 %r\n"
+                             "}\n";
+
+  std::unique_ptr<Module> M;
+  Function *F;
+
+  BasicBlock* BB0;
+  BasicBlock* BB1;
+  BasicBlock* BB2;
+  BasicBlock* BB3;
+  BasicBlock* BB4;
+  BasicBlock* BB5;
+
+  virtual void SetUp()
+  {
+    SMDiagnostic Err;
+
+    M = parseAssemblyString(ModuleString, Err, C);
+    F = M->getFunction("f");
+
+    auto It = F->begin();
+
+    BB0 = &*It++;
+    BB1 = &*It++;
+    BB2 = &*It++;
+    BB3 = &*It++;
+    BB4 = &*It++;
+    BB5 = &*It++;
+
+    EXPECT_TRUE(It == F->end());
+  }
+};
+
+TEST_F(BasicBlockPhiTest, SwitchReplaceFixPHI) {
+
+  SwitchInst* SI = dyn_cast<SwitchInst>(&BB0->front());
+  PHINode*    PN = dyn_cast<PHINode>(&BB5->front());
+
+  EXPECT_TRUE(SI != nullptr);
+  EXPECT_TRUE(PN != nullptr);
+
+  // Insert new label bb6.
+  IRBuilder<> Builder(C);
+  BasicBlock* BB6 = BasicBlock::Create(C, "bb6", F);
+
+  // Make bb1 jump to bb5.
+  BranchInst* BB1_Br = dyn_cast<BranchInst>(&BB1->front());
+  BB1_Br->setSuccessor(0, BB6);
+
+  // Add immediate branch to bb1.
+  Builder.SetInsertPoint(BB6);
+  Builder.CreateBr(BB5);
+
+  BB5->updatePHIs(BB1, BB6);
+
+  outs() << *PN << "\n";
+  EXPECT_TRUE(PN->getIncomingBlock(0) == BB6);
+}
+
+TEST_F(BasicBlockPhiTest, SwitchDefaultFixPHI) {
+
+  SwitchInst* SI = dyn_cast<SwitchInst>(&BB0->front());
+  PHINode*    PN = dyn_cast<PHINode>(&BB5->front());
+
+  EXPECT_TRUE(SI != nullptr);
+  EXPECT_TRUE(PN != nullptr);
+
+  // Make the switch directly branch to BB5 on default.
+  SI->setDefaultDest(BB5);
+  BB1->eraseFromParent();
+
+  BB5->updatePHIs(BB1, BB0);
+
+  outs() << *PN << "\n";
+  EXPECT_TRUE(PN->getIncomingBlock(0) == BB0);
+}
+
 } // End anonymous namespace.
 } // End llvm namespace.