[IR] Add an iterator and range accessor for the PHI nodes of a basic block.

[chandlerc]

Summary

This allows writing much more natural and readable range based for loops
directly over the PHI nodes. It also takes advantage of the same tricks
for terminating the sequence as the hand coded versions.

I've replaced one example of this mostly to showcase the difference and
I've added a unit test to make sure the facilities really work the way
they're intended. I want to use this inside of SimpleLoopUnswitch but it
seems generally nice.

[dblaikie]

include/llvm/IR/BasicBlock.h

286

Generally prefer to use non-member op overloads where possible (but maybe the iterator_facade isn't compatible with this? Not sure). That way LHS and RHS conversions happen equally - relevant for, say, const+non-const_iterator comparisons.

293

Seems weird to build an iterator in every increment, though I imagine it's cheap - any reason to do this rather than to keep the iterator as a member (rather than the pointer as a member)?

304–306

Usually I expect to see this done the other way around - having the non-const version delegate to the const version. Otherwise the const version is technically UB when invoked on a const object (since it casts away constness, calls a function, etc). Though I realize that means needing an explicit conversion from const iterator to non-const iterator - maybe easier to have two implementations then, given it's short/simple.

unittests/IR/BasicBlockTest.cpp

67

const_casts /to/ const kind of weird me out (because they're rare & so I'm only really used to seeing const_casts removing const - takes a bit to read when they're adding it). Should we have an llvm::implicit_cast?

Should it be "const auto &" on the LHS, if this is a const iterator?

[chandlerc]

include/llvm/IR/BasicBlock.h

286

I have no idea, but all the uses of iterator_facade_base follow this pattern. I'd somewhat rather not try to fix this in this patch....

293

It avoids the dyn_cast on every dereference (or having more state).

304–306

Why is it UB to cast away const even on a const object? I don't think anything makes that UB.

The UB thing is to *modify* a const object. But the non-const function here doesn't do that, so it seems fine?

I can have two implementations, but then I have to put them both out-of-line because the implementation of this method cannot be written in this header (requires the definition of the PHINode type which requires the definition of the BasicBlock type...)

unittests/IR/BasicBlockTest.cpp

67

To the first point: what would you suggest I write? I don't really care, this seemed to work.

To the second point: why? auto will deduce const just fine... adding const myself won't really surface any bugs. I guess I always prefer to write less when there is no reason to write more...

[dblaikie]

include/llvm/IR/BasicBlock.h

286

Rightio

293

Presumably only a cast, not a dyn_cast, right? (isa on increment, cast on deref?)

but sure

304–306

Fair - can't find anything that says it's UB to call a non-const function on a const object, but weirds me out a bit because it'd make it pretty easy to leak a non-const pointer/mutate state by accident, so I'd tend to prefer the inverse phrasing, but I realize it's a bit awkward. Up to you.

unittests/IR/BasicBlockTest.cpp

67

I'd love an implicit_cast - if you want to add one while you're at it, but I understand that's a whole nother thing with test cases, etc.

I figure const, &, and * are short enough that the relative cost/benefit is worthwhile to include them. The LLVM style guide does at least call for '*' when auto is deducing to a pointer (/when that matters - if it's some opaque typedef that the code doesn't care about pointerness, I suppose '*' wouldn't be used) & I've always assumed (incorrectly, now that I look) that the style guide said the same about const. At least that's my habit.

Up to you.

[chandlerc]

Thanks for all the comments Dave! I'm gonna land this with the fix below, but do let me know if you want any further work here.

include/llvm/IR/BasicBlock.h

304–306

Digging around, we do this ... pretty frequently. And I dunno that having an explicit conversion from a const_iterator to non-const iterator is any less weird. In both cases, we're stripping off const and doing something with it.

Anyways, I'm gonna leave this as-is for now as it doesn't seem uncommon. Happy to revisit this if you and/or others come the consensus that we really want to shift away from this.

unittests/IR/BasicBlockTest.cpp

67

Adding const here.

Happy for this to switch to an implicit cast if/when one shows up, but I'm gonna resist shaving that yak today. ;]

include/llvm/IR/BasicBlock.h

 
 namespace llvm {
 
 class CallInst;
 class Function;
 class LandingPadInst;
 class LLVMContext;
 class Module;
+class PHINode;
 class TerminatorInst;
 class ValueSymbolTable;
 
 /// \brief LLVM Basic Block Representation
 ///
 /// This represents a single basic block in LLVM. A basic block is simply a
 /// container of instructions that execute sequentially. Basic blocks are Values
 /// because they are referenced by instructions such as branches and switch
public:
 
   inline size_t                   size() const { return InstList.size();  }
   inline bool                    empty() const { return InstList.empty(); }
   inline const Instruction      &front() const { return InstList.front(); }
   inline       Instruction      &front()       { return InstList.front(); }
   inline const Instruction       &back() const { return InstList.back();  }
   inline       Instruction       &back()       { return InstList.back();  }
 
+  /// Iterator to walk just the phi nodes in the basic block.
+  template <typename PHINodeT = PHINode, typename BBIteratorT = iterator>
+  class phi_iterator_impl
+      : public iterator_facade_base<phi_iterator_impl<PHINodeT, BBIteratorT>,
+                                    std::forward_iterator_tag, PHINodeT> {
+    friend BasicBlock;
+
+    PHINodeT *PN;
+
+    phi_iterator_impl(PHINodeT *PN) : PN(PN) {}
+
+  public:
+    // Allow default construction to build variables, but this doesn't build
+    // a useful iterator.
+    phi_iterator_impl() = default;
+
+    // Allow conversion between instantiations where valid.
+    template <typename PHINodeU, typename BBIteratorU>
+    phi_iterator_impl(const phi_iterator_impl<PHINodeU, BBIteratorU> &Arg)
+        : PN(Arg.PN) {}
+
+    bool operator==(const phi_iterator_impl &Arg) const { return PN == Arg.PN; }
+
+    PHINodeT &operator*() const { return *PN; }
+
+    using phi_iterator_impl::iterator_facade_base::operator++;
+    phi_iterator_impl &operator++() {
+      assert(PN && "Cannot increment the end iterator!");
+      PN = dyn_cast<PHINodeT>(std::next(BBIteratorT(PN)));
+      return *this;
+    }
+  };
+  typedef phi_iterator_impl<> phi_iterator;
+  typedef phi_iterator_impl<const PHINode, BasicBlock::const_iterator>
+      const_phi_iterator;
+
+  /// Returns a range that iterates over the phis in the basic block.
+  ///
+  /// Note that this cannot be used with basic blocks that have no terminator.
+  iterator_range<const_phi_iterator> phis() const {
+    return const_cast<BasicBlock *>(this)->phis();
+  }
+  iterator_range<phi_iterator> phis();
+
   /// \brief Return the underlying instruction list container.
   ///
   /// Currently you need to access the underlying instruction list container
   /// directly if you want to modify it.
   const InstListType &getInstList() const { return InstList; }
         InstListType &getInstList()       { return InstList; }
 
   /// \brief Returns a pointer to a member of the instruction list.

lib/IR/BasicBlock.cpp

for (;SI != E; ++SI) {
     if (*SI != SuccBB)
       return nullptr;
     // The same successor appears multiple times in the successor list.
     // This is OK.
   }
   return SuccBB;
 }
 
+iterator_range<BasicBlock::phi_iterator> BasicBlock::phis() {
+  return make_range<phi_iterator>(dyn_cast<PHINode>(&front()), nullptr);
+}
+
 /// This method is used to notify a BasicBlock that the
 /// specified Predecessor of the block is no longer able to reach it.  This is
 /// actually not used to update the Predecessor list, but is actually used to
 /// update the PHI nodes that reside in the block.  Note that this should be
 /// called while the predecessor still refers to this block.
 ///
 void BasicBlock::removePredecessor(BasicBlock *Pred,
                                    bool DontDeleteUselessPHIs) {
BasicBlock *BasicBlock::splitBasicBlock(iterator I, const Twine &BBName) {
   // _were_ the successors of the 'this' block), and update any PHI nodes in
   // successors.  If there were PHI nodes in the successors, then they need to
   // know that incoming branches will be from New, not from Old.
   //
   for (succ_iterator I = succ_begin(New), E = succ_end(New); I != E; ++I) {
     // Loop over any phi nodes in the basic block, updating the BB field of
     // incoming values...
     BasicBlock *Successor = *I;
-    PHINode *PN;
-    for (BasicBlock::iterator II = Successor->begin();
-         (PN = dyn_cast<PHINode>(II)); ++II) {
-      int IDX = PN->getBasicBlockIndex(this);
-      while (IDX != -1) {
-        PN->setIncomingBlock((unsigned)IDX, New);
-        IDX = PN->getBasicBlockIndex(this);
+    for (auto &PN : Successor->phis()) {
+      int Idx = PN.getBasicBlockIndex(this);
+      while (Idx != -1) {
+        PN.setIncomingBlock((unsigned)Idx, New);
+        Idx = PN.getBasicBlockIndex(this);
       }
     }
   }
   return New;
 }
 
 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
   TerminatorInst *TI = getTerminator();

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/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/Module.h"
+#include "llvm/IR/NoFolder.h"
+#include "gmock/gmock-matchers.h"
+#include "gtest/gtest.h"
+#include <memory>
+
+namespace llvm {
+namespace {
+
+TEST(BasicBlockTest, PhiRange) {
+  LLVMContext Context;
+
+  // Create the main block.
+  std::unique_ptr<BasicBlock> BB(BasicBlock::Create(Context));
+
+  // Create some predecessors of it.
+  std::unique_ptr<BasicBlock> BB1(BasicBlock::Create(Context));
+  BranchInst::Create(BB.get(), BB1.get());
+  std::unique_ptr<BasicBlock> BB2(BasicBlock::Create(Context));
+  BranchInst::Create(BB.get(), BB2.get());
+
+  // Make it a cycle.
+  auto *BI = BranchInst::Create(BB.get(), BB.get());
+
+  // Now insert some PHI nodes.
+  auto *Int32Ty = Type::getInt32Ty(Context);
+  auto *P1 = PHINode::Create(Int32Ty, /*NumReservedValues*/ 3, "phi.1", BI);
+  auto *P2 = PHINode::Create(Int32Ty, /*NumReservedValues*/ 3, "phi.2", BI);
+  auto *P3 = PHINode::Create(Int32Ty, /*NumReservedValues*/ 3, "phi.3", BI);
+
+  // Some non-PHI nodes.
+  auto *Sum = BinaryOperator::CreateAdd(P1, P2, "sum", BI);
+
+  // Now wire up the incoming values that are interesting.
+  P1->addIncoming(P2, BB.get());
+  P2->addIncoming(P1, BB.get());
+  P3->addIncoming(Sum, BB.get());
+
+  // Finally, let's iterate them, which is the thing we're trying to test.
+  // We'll use this to wire up the rest of the incoming values.
+  for (auto &PN : BB->phis()) {
+    PN.addIncoming(UndefValue::get(Int32Ty), BB1.get());
+    PN.addIncoming(UndefValue::get(Int32Ty), BB2.get());
+  }
+
+  // Test that we can use const iterators and generally that the iterators
+  // behave like iterators.
+  BasicBlock::const_phi_iterator CI;
+  CI = CI = BB->phis().begin();
+  EXPECT_NE(CI, BB->phis().end());
+
+  // And iterate a const range.
+  for (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));
+  }
+}
+
+} // End anonymous namespace.
+} // End llvm namespace.

unittests/IR/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Analysis
   AsmParser
   Core
   Support
   )
 
 set(IRSources
   AsmWriterTest.cpp
   AttributesTest.cpp
+  BasicBlockTest.cpp
   ConstantRangeTest.cpp
   ConstantsTest.cpp
   DebugInfoTest.cpp
   DebugTypeODRUniquingTest.cpp
   DominatorTreeTest.cpp
   FunctionTest.cpp
   IRBuilderTest.cpp
   InstructionsTest.cpp