[IR] Begin removal of TerminatorInst by removing successor manipulation.

[chandlerc]

Summary

The core get and set routines move to the Instruction class. These
routines are only valid to call on instructions which are terminators.

The iterator and *generic* range based access move to CFG.h where all
the other generic successor and predecessor access lives. While moving
the iterator here, simplify it using the iterator utilities LLVM
provides and updates coding style as much as reasonable. The APIs remain
pointer-heavy when they could better use references, and retain the odd
behavior of operator* and operator-> that is common in LLVM
iterators. Adjusting this API, if desired, should be a follow-up step.

Non-generic range iteration is added for the two instructions where
there is an especially easy mechanism and where there was code
attempting to use the range accessor from a specific subclass:
indirectbr and br. In both cases, the successors are contiguous
operands and can be easily iterated via the operand list.

This is the first major patch in removing the TerminatorInst type from
the IR's instruction type hierarchy. The steps that I have planned out
(although there are likely to be some minor ones) look like the
following:

• Remove the few remaining APIs of TerminatorInst, replacing them with existing predicates in Instruction or adding new ones if needed.
• Replacing isa<TerminatorInst> and dyn_cast<TerminatorInst> with appropriate uses of isTerminator.
• Replacing TerminatorInst in parameter APIs with just Instruction and potentially an assert on isTerminator.
• Replacing TerminatorInst in the return of the remaining APIs (not updated above) with Instruction. Most notably, the getTerminator method.
• Removing TerminotarInst type completely.
• Making InvokeInst and CallInst derive from a common base class w/ most of the logic currently in CallInst.
• Replacing uses of CallSite everywhere with the common base class.

These are likely to be quite mechanical, and I suspect are probably best done
with post-commit review. Please lete me know if there are specific
patches in this series you'd like to do pre-commit review on and I'll
happily break them out. Naturally, if any end up with significant
questions in them, I'll post a review for that.

[dberris]

llvm/include/llvm/IR/CFG.h

193 ↗

(On Diff #148871)

Maybe this should be a non-member friend, and works with const and non-const versions of compatible type?

friend inline bool operator==(const Self& L, const Self& R) {
  return L.Idx == R.Idx;
}

[chandlerc]

llvm/include/llvm/IR/CFG.h

193 ↗

(On Diff #148871)

It has to be a member for the underlying iterator helper to work (due to how that underlying helper is implemented).

Is there really a problem to solve here though? Not sure what the benefit is of this in the absence of a type hierarchy... We don't do it very consistently in LLVM anywhere.

[rnk]

llvm/include/llvm/IR/Instructions.h

3263 ↗

(On Diff #148871)

What are these used for? It doesn't seem like they are called in any way in this code. Do these keep existing calls to Br->successors() compiling?

[dberris]

llvm/include/llvm/IR/CFG.h

193 ↗

(On Diff #148871)

Ah, that's fair -- didn't know that the facade requires equality to be defined as a member.

The only problems the friend declaration solves are the overload resolution issue (if you want to have type deduction of the RHS to support slightly different types) and forces ADL when defined inline -- i.e. the only way to find the operator is through ADL.

Consider:

template <class T>
class C {
  template <class U> friend bool operator==(const C& L, const C<U>& R) {
    return ...;
  }
  ...
};

This allows C<int> and C<const int> types to be comparable, without having to make any special considerations. It also only allows for the equality comparison to be found with ADL, and no other way (AFAICT).

Whether that needs to be more widely adopted in LLVM/Clang is a separate issue, probably not worth spending a lot more time on.

[chandlerc]

llvm/include/llvm/IR/CFG.h

193 ↗

(On Diff #148871)

Yeah, I think this is going to be fine for our somewhat limited needs for now. Thanks for the feedback though!

llvm/include/llvm/IR/Instructions.h

3263 ↗

(On Diff #148871)

Correct. THere were a few places that were calling it directly on a BranchInst and it seemed easy enough to implement that in a more obvious fashion than going through the (quite high cost) generic successors logic.

[chandlerc]

Adding James as a reviewer since I know he's interested in this stuff...

[hfinkel]

LGTM

These are likely to be quite mechanical, and I suspect are probably best done with post-commit review.

I agree. The others sound sufficiently mechanical for post-commit review.

llvm/include/llvm/IR/CFG.h

195 ↗

(On Diff #148871)

Should BasicBlock here be BlockT?

198 ↗

(On Diff #148871)

Same here?

[chandlerc]

Any last comments here? Hal has given LGTM, and so I'm planning to move forward with this tomorrow.

(I've rebased it and addressed the two minor comments from Hal...)

[aivchenk]

Hi Chandler, are you still planning to work on that?

Thanks, Alexander

[chandlerc]

In D47467#1207174, @aivchenk wrote:

Hi Chandler, are you still planning to work on that?

Thanks, Alexander

Yes, really sorry for the delay here.

This has been held up by finishing off security related work, but should be moving again once the next patch there is finished.

[chandlerc]

In D47467#1207191, @chandlerc wrote:

In D47467#1207174, @aivchenk wrote:

Hi Chandler, are you still planning to work on that?

Thanks, Alexander

Yes, really sorry for the delay here.

This has been held up by finishing off security related work, but should be moving again once the next patch there is finished.

FYI, I've rebased and will be landing this and subsequent patches now.

llvm/trunk/include/llvm/IR/CFG.h

-//===- CFG.h - Process LLVM structures as graphs ----------------*- C++ -*-===//
+//===- CFG.h ----------------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
-//
-// This file defines specializations of GraphTraits that allow Function and
-// BasicBlock graphs to be treated as proper graphs for generic algorithms.
-//
+/// \file
+///
+/// This file provides various utilities for inspecting and working with the
+/// control flow graph in LLVM IR. This includes generic facilities for
+/// iterating successors and predecessors of basic blocks, the successors of
+/// specific terminator instructions, etc. It also defines specializations of
+/// GraphTraits that allow Function and BasicBlock graphs to be treated as
+/// proper graphs for generic algorithms.
+///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_CFG_H
 #define LLVM_IR_CFG_H
 
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/iterator.h"
 #include "llvm/ADT/iterator_range.h"

 inline pred_range predecessors(BasicBlock *BB) {
   return pred_range(pred_begin(BB), pred_end(BB));
 }
 inline pred_const_range predecessors(const BasicBlock *BB) {
   return pred_const_range(pred_begin(BB), pred_end(BB));
 }
 
 //===----------------------------------------------------------------------===//
-// BasicBlock succ_iterator helpers
+// Instruction and BasicBlock succ_iterator helpers
 //===----------------------------------------------------------------------===//
 
-using succ_iterator =
-    TerminatorInst::SuccIterator<TerminatorInst *, BasicBlock>;
-using succ_const_iterator =
-    TerminatorInst::SuccIterator<const TerminatorInst *, const BasicBlock>;
+template <class InstructionT, class BlockT>
+class SuccIterator
+    : public iterator_facade_base<SuccIterator<InstructionT, BlockT>,
+                                  std::random_access_iterator_tag, BlockT, int,
+                                  BlockT *, BlockT *> {
+public:
+  using difference_type = int;
+  using pointer = BlockT *;
+  using reference = BlockT *;
+
+private:
+  InstructionT *Inst;
+  int Idx;
+  using Self = SuccIterator<InstructionT, BlockT>;
+
+  inline bool index_is_valid(int Idx) {
+    // Note that we specially support the index of zero being valid even in the
+    // face of a null instruction.
+    return Idx >= 0 && (Idx == 0 || Idx <= (int)Inst->getNumSuccessors());
+  }
+
+  /// Proxy object to allow write access in operator[]
+  class SuccessorProxy {
+    Self It;
+
+  public:
+    explicit SuccessorProxy(const Self &It) : It(It) {}
+
+    SuccessorProxy(const SuccessorProxy &) = default;
+
+    SuccessorProxy &operator=(SuccessorProxy RHS) {
+      *this = reference(RHS);
+      return *this;
+    }
+
+    SuccessorProxy &operator=(reference RHS) {
+      It.Inst->setSuccessor(It.Idx, RHS);
+      return *this;
+    }
+
+    operator reference() const { return *It; }
+  };
+
+public:
+  // begin iterator
+  explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
+  // end iterator
+  inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
+    if (Inst)
+      Idx = Inst->getNumSuccessors();
+    else
+      // Inst == NULL happens, if a basic block is not fully constructed and
+      // consequently getTerminator() returns NULL. In this case we construct
+      // a SuccIterator which describes a basic block that has zero
+      // successors.
+      // Defining SuccIterator for incomplete and malformed CFGs is especially
+      // useful for debugging.
+      Idx = 0;
+  }
+
+  /// This is used to interface between code that wants to
+  /// operate on terminator instructions directly.
+  int getSuccessorIndex() const { return Idx; }
+
+  inline bool operator==(const Self &x) const { return Idx == x.Idx; }
+
+  inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
+
+  // We use the basic block pointer directly for operator->.
+  inline BlockT *operator->() const { return operator*(); }
+
+  inline bool operator<(const Self &RHS) const {
+    assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
+    return Idx < RHS.Idx;
+  }
+
+  int operator-(const Self &RHS) const {
+    assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
+    return Idx - RHS.Idx;
+  }
+
+  inline Self &operator+=(int RHS) {
+    int NewIdx = Idx + RHS;
+    assert(index_is_valid(NewIdx) && "Iterator index out of bound");
+    Idx = NewIdx;
+    return *this;
+  }
+
+  inline Self &operator-=(int RHS) { return operator+=(-RHS); }
+
+  // Specially implement the [] operation using a proxy object to support
+  // assignment.
+  inline SuccessorProxy operator[](int Offset) {
+    Self TmpIt = *this;
+    TmpIt += Offset;
+    return SuccessorProxy(TmpIt);
+  }
+
+  /// Get the source BlockT of this iterator.
+  inline BlockT *getSource() {
+    assert(Inst && "Source not available, if basic block was malformed");
+    return Inst->getParent();
+  }
+};
+
+template <typename T, typename U> struct isPodLike<SuccIterator<T, U>> {
+  static const bool value = isPodLike<T>::value;
+};
+
+using succ_iterator = SuccIterator<Instruction, BasicBlock>;
+using succ_const_iterator = SuccIterator<const Instruction, const BasicBlock>;
 using succ_range = iterator_range<succ_iterator>;
 using succ_const_range = iterator_range<succ_const_iterator>;
 
+inline succ_iterator succ_begin(Instruction *I) { return succ_iterator(I); }
+inline succ_const_iterator succ_begin(const Instruction *I) {
+  return succ_const_iterator(I);
+}
+inline succ_iterator succ_end(Instruction *I) { return succ_iterator(I, true); }
+inline succ_const_iterator succ_end(const Instruction *I) {
+  return succ_const_iterator(I, true);
+}
+inline bool succ_empty(const Instruction *I) {
+  return succ_begin(I) == succ_end(I);
+}
+inline unsigned succ_size(const Instruction *I) {
+  return std::distance(succ_begin(I), succ_end(I));
+}
+inline succ_range successors(Instruction *I) {
+  return succ_range(succ_begin(I), succ_end(I));
+}
+inline succ_const_range successors(const Instruction *I) {
+  return succ_const_range(succ_begin(I), succ_end(I));
+}
+
 inline succ_iterator succ_begin(BasicBlock *BB) {
   return succ_iterator(BB->getTerminator());
 }
 inline succ_const_iterator succ_begin(const BasicBlock *BB) {
   return succ_const_iterator(BB->getTerminator());
 }
 inline succ_iterator succ_end(BasicBlock *BB) {
   return succ_iterator(BB->getTerminator(), true);

 }
 inline succ_range successors(BasicBlock *BB) {
   return succ_range(succ_begin(BB), succ_end(BB));
 }
 inline succ_const_range successors(const BasicBlock *BB) {
   return succ_const_range(succ_begin(BB), succ_end(BB));
 }
 
-template <typename T, typename U>
-struct isPodLike<TerminatorInst::SuccIterator<T, U>> {
-  static const bool value = isPodLike<T>::value;
-};
-
 //===--------------------------------------------------------------------===//
 // GraphTraits specializations for basic block graphs (CFGs)
 //===--------------------------------------------------------------------===//
 
 // Provide specializations of GraphTraits to be able to treat a function as a
 // graph of basic blocks...
 
 template <> struct GraphTraits<BasicBlock*> {

llvm/trunk/include/llvm/IR/InstrTypes.h

TerminatorInst(Type *Ty, Instruction::TermOps iType,
                  Instruction *InsertBefore = nullptr)
     : Instruction(Ty, iType, Ops, NumOps, InsertBefore) {}
 
   TerminatorInst(Type *Ty, Instruction::TermOps iType,
                  Use *Ops, unsigned NumOps, BasicBlock *InsertAtEnd)
     : Instruction(Ty, iType, Ops, NumOps, InsertAtEnd) {}
 
 public:
-  /// Return the number of successors that this terminator has.
-  unsigned getNumSuccessors() const;
-
-  /// Return the specified successor.
-  BasicBlock *getSuccessor(unsigned idx) const;
-
-  /// Update the specified successor to point at the provided block.
-  void setSuccessor(unsigned idx, BasicBlock *B);
-
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const Instruction *I) {
     return I->isTerminator();
   }
   static bool classof(const Value *V) {
     return isa<Instruction>(V) && classof(cast<Instruction>(V));
   }
 
   // Returns true if this terminator relates to exception handling.
   bool isExceptional() const {
     switch (getOpcode()) {
     case Instruction::CatchSwitch:
     case Instruction::CatchRet:
     case Instruction::CleanupRet:
     case Instruction::Invoke:
     case Instruction::Resume:
       return true;
     default:
       return false;
     }
   }
-
-  //===--------------------------------------------------------------------===//
-  // succ_iterator definition
-  //===--------------------------------------------------------------------===//
-
-  template <class Term, class BB> // Successor Iterator
-  class SuccIterator : public std::iterator<std::random_access_iterator_tag, BB,
-                                            int, BB *, BB *> {
-    using super =
-        std::iterator<std::random_access_iterator_tag, BB, int, BB *, BB *>;
-
-  public:
-    using pointer = typename super::pointer;
-    using reference = typename super::reference;
-
-  private:
-    Term TermInst;
-    unsigned idx;
-    using Self = SuccIterator<Term, BB>;
-
-    inline bool index_is_valid(unsigned idx) {
-      return idx < TermInst->getNumSuccessors();
-    }
-
-    /// Proxy object to allow write access in operator[]
-    class SuccessorProxy {
-      Self it;
-
-    public:
-      explicit SuccessorProxy(const Self &it) : it(it) {}
-
-      SuccessorProxy(const SuccessorProxy &) = default;
-
-      SuccessorProxy &operator=(SuccessorProxy r) {
-        *this = reference(r);
-        return *this;
-      }
-
-      SuccessorProxy &operator=(reference r) {
-        it.TermInst->setSuccessor(it.idx, r);
-        return *this;
-      }
-
-      operator reference() const { return *it; }
-    };
-
-  public:
-    // begin iterator
-    explicit inline SuccIterator(Term T) : TermInst(T), idx(0) {}
-    // end iterator
-    inline SuccIterator(Term T, bool) : TermInst(T) {
-      if (TermInst)
-        idx = TermInst->getNumSuccessors();
-      else
-        // Term == NULL happens, if a basic block is not fully constructed and
-        // consequently getTerminator() returns NULL. In this case we construct
-        // a SuccIterator which describes a basic block that has zero
-        // successors.
-        // Defining SuccIterator for incomplete and malformed CFGs is especially
-        // useful for debugging.
-        idx = 0;
-    }
-
-    /// This is used to interface between code that wants to
-    /// operate on terminator instructions directly.
-    unsigned getSuccessorIndex() const { return idx; }
-
-    inline bool operator==(const Self &x) const { return idx == x.idx; }
-    inline bool operator!=(const Self &x) const { return !operator==(x); }
-
-    inline reference operator*() const { return TermInst->getSuccessor(idx); }
-    inline pointer operator->() const { return operator*(); }
-
-    inline Self &operator++() {
-      ++idx;
-      return *this;
-    } // Preincrement
-
-    inline Self operator++(int) { // Postincrement
-      Self tmp = *this;
-      ++*this;
-      return tmp;
-    }
-
-    inline Self &operator--() {
-      --idx;
-      return *this;
-    }                             // Predecrement
-    inline Self operator--(int) { // Postdecrement
-      Self tmp = *this;
-      --*this;
-      return tmp;
-    }
-
-    inline bool operator<(const Self &x) const {
-      assert(TermInst == x.TermInst &&
-             "Cannot compare iterators of different blocks!");
-      return idx < x.idx;
-    }
-
-    inline bool operator<=(const Self &x) const {
-      assert(TermInst == x.TermInst &&
-             "Cannot compare iterators of different blocks!");
-      return idx <= x.idx;
-    }
-    inline bool operator>=(const Self &x) const {
-      assert(TermInst == x.TermInst &&
-             "Cannot compare iterators of different blocks!");
-      return idx >= x.idx;
-    }
-
-    inline bool operator>(const Self &x) const {
-      assert(TermInst == x.TermInst &&
-             "Cannot compare iterators of different blocks!");
-      return idx > x.idx;
-    }
-
-    inline Self &operator+=(int Right) {
-      unsigned new_idx = idx + Right;
-      assert(index_is_valid(new_idx) && "Iterator index out of bound");
-      idx = new_idx;
-      return *this;
-    }
-
-    inline Self operator+(int Right) const {
-      Self tmp = *this;
-      tmp += Right;
-      return tmp;
-    }
-
-    inline Self &operator-=(int Right) { return operator+=(-Right); }
-
-    inline Self operator-(int Right) const { return operator+(-Right); }
-
-    inline int operator-(const Self &x) const {
-      assert(TermInst == x.TermInst &&
-             "Cannot work on iterators of different blocks!");
-      int distance = idx - x.idx;
-      return distance;
-    }
-
-    inline SuccessorProxy operator[](int offset) {
-      Self tmp = *this;
-      tmp += offset;
-      return SuccessorProxy(tmp);
-    }
-
-    /// Get the source BB of this iterator.
-    inline BB *getSource() {
-      assert(TermInst && "Source not available, if basic block was malformed");
-      return TermInst->getParent();
-    }
-  };
-
-  using succ_iterator = SuccIterator<TerminatorInst *, BasicBlock>;
-  using succ_const_iterator =
-      SuccIterator<const TerminatorInst *, const BasicBlock>;
-  using succ_range = iterator_range<succ_iterator>;
-  using succ_const_range = iterator_range<succ_const_iterator>;
-
-private:
-  inline succ_iterator succ_begin() { return succ_iterator(this); }
-  inline succ_const_iterator succ_begin() const {
-    return succ_const_iterator(this);
-  }
-  inline succ_iterator succ_end() { return succ_iterator(this, true); }
-  inline succ_const_iterator succ_end() const {
-    return succ_const_iterator(this, true);
-  }
-
-public:
-  inline succ_range successors() {
-    return succ_range(succ_begin(), succ_end());
-  }
-  inline succ_const_range successors() const {
-    return succ_const_range(succ_begin(), succ_end());
-  }
 };
 
 //===----------------------------------------------------------------------===//
 //                          UnaryInstruction Class
 //===----------------------------------------------------------------------===//
 
 class UnaryInstruction : public Instruction {
 protected:

llvm/trunk/include/llvm/IR/Instruction.h

public:
   /// Determine if one instruction is the same operation as another.
   bool isSameOperationAs(const Instruction *I, unsigned flags = 0) const;
 
   /// Return true if there are any uses of this instruction in blocks other than
   /// the specified block. Note that PHI nodes are considered to evaluate their
   /// operands in the corresponding predecessor block.
   bool isUsedOutsideOfBlock(const BasicBlock *BB) const;
 
+  /// Return the number of successors that this instruction has. The instruction
+  /// must be a terminator.
+  unsigned getNumSuccessors() const;
+
+  /// Return the specified successor. This instruction must be a terminator.
+  BasicBlock *getSuccessor(unsigned Idx) const;
+
+  /// Update the specified successor to point at the provided block. This
+  /// instruction must be a terminator.
+  void setSuccessor(unsigned Idx, BasicBlock *BB);
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const Value *V) {
     return V->getValueID() >= Value::InstructionVal;
   }
 
   //----------------------------------------------------------------------
   // Exported enumerations.

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

 
 protected:
   // Note: Instruction needs to be a friend here to call cloneImpl.
   friend class Instruction;
 
   BranchInst *cloneImpl() const;
 
 public:
+  /// Iterator type that casts an operand to a basic block.
+  ///
+  /// This only makes sense because the successors are stored as adjacent
+  /// operands for branch instructions.
+  struct succ_op_iterator
+      : iterator_adaptor_base<succ_op_iterator, value_op_iterator,
+                              std::random_access_iterator_tag, BasicBlock *,
+                              ptrdiff_t, BasicBlock *, BasicBlock *> {
+    explicit succ_op_iterator(value_op_iterator I) : iterator_adaptor_base(I) {}
+
+    BasicBlock *operator*() const { return cast<BasicBlock>(*I); }
+    BasicBlock *operator->() const { return operator*(); }
+  };
+
+  /// The const version of `succ_op_iterator`.
+  struct const_succ_op_iterator
+      : iterator_adaptor_base<const_succ_op_iterator, const_value_op_iterator,
+                              std::random_access_iterator_tag,
+                              const BasicBlock *, ptrdiff_t, const BasicBlock *,
+                              const BasicBlock *> {
+    explicit const_succ_op_iterator(const_value_op_iterator I)
+        : iterator_adaptor_base(I) {}
+
+    const BasicBlock *operator*() const { return cast<BasicBlock>(*I); }
+    const BasicBlock *operator->() const { return operator*(); }
+  };
+
   static BranchInst *Create(BasicBlock *IfTrue,
                             Instruction *InsertBefore = nullptr) {
     return new(1) BranchInst(IfTrue, InsertBefore);
   }
 
   static BranchInst *Create(BasicBlock *IfTrue, BasicBlock *IfFalse,
                             Value *Cond, Instruction *InsertBefore = nullptr) {
     return new(3) BranchInst(IfTrue, IfFalse, Cond, InsertBefore);
public:
 
   /// Swap the successors of this branch instruction.
   ///
   /// Swaps the successors of the branch instruction. This also swaps any
   /// branch weight metadata associated with the instruction so that it
   /// continues to map correctly to each operand.
   void swapSuccessors();
 
+  iterator_range<succ_op_iterator> successors() {
+    return make_range(
+        succ_op_iterator(std::next(value_op_begin(), isConditional() ? 1 : 0)),
+        succ_op_iterator(value_op_end()));
+  }
+
+  iterator_range<const_succ_op_iterator> successors() const {
+    return make_range(const_succ_op_iterator(
+                          std::next(value_op_begin(), isConditional() ? 1 : 0)),
+                      const_succ_op_iterator(value_op_end()));
+  }
+
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const Instruction *I) {
     return (I->getOpcode() == Instruction::Br);
   }
   static bool classof(const Value *V) {
     return isa<Instruction>(V) && classof(cast<Instruction>(V));
   }
 };

 
 protected:
   // Note: Instruction needs to be a friend here to call cloneImpl.
   friend class Instruction;
 
   IndirectBrInst *cloneImpl() const;
 
 public:
+  /// Iterator type that casts an operand to a basic block.
+  ///
+  /// This only makes sense because the successors are stored as adjacent
+  /// operands for indirectbr instructions.
+  struct succ_op_iterator
+      : iterator_adaptor_base<succ_op_iterator, value_op_iterator,
+                              std::random_access_iterator_tag, BasicBlock *,
+                              ptrdiff_t, BasicBlock *, BasicBlock *> {
+    explicit succ_op_iterator(value_op_iterator I) : iterator_adaptor_base(I) {}
+
+    BasicBlock *operator*() const { return cast<BasicBlock>(*I); }
+    BasicBlock *operator->() const { return operator*(); }
+  };
+
+  /// The const version of `succ_op_iterator`.
+  struct const_succ_op_iterator
+      : iterator_adaptor_base<const_succ_op_iterator, const_value_op_iterator,
+                              std::random_access_iterator_tag,
+                              const BasicBlock *, ptrdiff_t, const BasicBlock *,
+                              const BasicBlock *> {
+    explicit const_succ_op_iterator(const_value_op_iterator I)
+        : iterator_adaptor_base(I) {}
+
+    const BasicBlock *operator*() const { return cast<BasicBlock>(*I); }
+    const BasicBlock *operator->() const { return operator*(); }
+  };
+
   static IndirectBrInst *Create(Value *Address, unsigned NumDests,
                                 Instruction *InsertBefore = nullptr) {
     return new IndirectBrInst(Address, NumDests, InsertBefore);
   }
 
   static IndirectBrInst *Create(Value *Address, unsigned NumDests,
                                 BasicBlock *InsertAtEnd) {
     return new IndirectBrInst(Address, NumDests, InsertAtEnd);
public:
   unsigned getNumSuccessors() const { return getNumOperands()-1; }
   BasicBlock *getSuccessor(unsigned i) const {
     return cast<BasicBlock>(getOperand(i+1));
   }
   void setSuccessor(unsigned i, BasicBlock *NewSucc) {
     setOperand(i + 1, NewSucc);
   }
 
+  iterator_range<succ_op_iterator> successors() {
+    return make_range(succ_op_iterator(std::next(value_op_begin())),
+                      succ_op_iterator(value_op_end()));
+  }
+
+  iterator_range<const_succ_op_iterator> successors() const {
+    return make_range(const_succ_op_iterator(std::next(value_op_begin())),
+                      const_succ_op_iterator(value_op_end()));
+  }
+
   // Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const Instruction *I) {
     return I->getOpcode() == Instruction::IndirectBr;
   }
   static bool classof(const Value *V) {
     return isa<Instruction>(V) && classof(cast<Instruction>(V));
   }
 };

llvm/trunk/lib/Analysis/LoopInfo.cpp

if (BasicBlock *Latch = getLoopLatch()) {
     // Go through each predecessor of the loop header and check the
     // terminator for the metadata.
     BasicBlock *H = getHeader();
     for (BasicBlock *BB : this->blocks()) {
       TerminatorInst *TI = BB->getTerminator();
       MDNode *MD = nullptr;
 
       // Check if this terminator branches to the loop header.
-      for (BasicBlock *Successor : TI->successors()) {
+      for (BasicBlock *Successor : successors(TI)) {
         if (Successor == H) {
           MD = TI->getMetadata(LLVMContext::MD_loop);
           break;
         }
       }
       if (!MD)
         return nullptr;
 
if (BasicBlock *Latch = getLoopLatch()) {
     return;
   }
 
   assert(!getLoopLatch() &&
          "The loop should have no single latch at this point");
   BasicBlock *H = getHeader();
   for (BasicBlock *BB : this->blocks()) {
     TerminatorInst *TI = BB->getTerminator();
-    for (BasicBlock *Successor : TI->successors()) {
+    for (BasicBlock *Successor : successors(TI)) {
       if (Successor == H)
         TI->setMetadata(LLVMContext::MD_loop, LoopID);
     }
   }
 }
 
 void Loop::setLoopAlreadyUnrolled() {
   MDNode *LoopID = getLoopID();

llvm/trunk/lib/Analysis/MemorySSAUpdater.cpp

 }
 
 void MemorySSAUpdater::removeBlocks(
     const SmallPtrSetImpl<BasicBlock *> &DeadBlocks) {
   // First delete all uses of BB in MemoryPhis.
   for (BasicBlock *BB : DeadBlocks) {
     TerminatorInst *TI = BB->getTerminator();
     assert(TI && "Basic block expected to have a terminator instruction");
-    for (BasicBlock *Succ : TI->successors())
+    for (BasicBlock *Succ : successors(TI))
       if (!DeadBlocks.count(Succ))
         if (MemoryPhi *MP = MSSA->getMemoryAccess(Succ)) {
           MP->unorderedDeleteIncomingBlock(BB);
           if (MP->getNumIncomingValues() == 1)
             removeMemoryAccess(MP);
         }
     // Drop all references of all accesses in BB
     if (MemorySSA::AccessList *Acc = MSSA->getWritableBlockAccesses(BB))

llvm/trunk/lib/CodeGen/GlobalISel/IRTranslator.cpp

bool IRTranslator::translateBr(const User &U, MachineIRBuilder &MIRBuilder) {
   MachineBasicBlock &TgtBB = getMBB(BrTgt);
   MachineBasicBlock &CurBB = MIRBuilder.getMBB();
 
   // If the unconditional target is the layout successor, fallthrough.
   if (!CurBB.isLayoutSuccessor(&TgtBB))
     MIRBuilder.buildBr(TgtBB);
 
   // Link successors.
-  for (const BasicBlock *Succ : BrInst.successors())
+  for (const BasicBlock *Succ : successors(&BrInst))
     CurBB.addSuccessor(&getMBB(*Succ));
   return true;
 }
 
 bool IRTranslator::translateSwitch(const User &U,
                                    MachineIRBuilder &MIRBuilder) {
   // For now, just translate as a chain of conditional branches.
   // FIXME: could we share most of the logic/code in
bool IRTranslator::translateIndirectBr(const User &U,
                                        MachineIRBuilder &MIRBuilder) {
   const IndirectBrInst &BrInst = cast<IndirectBrInst>(U);
 
   const unsigned Tgt = getOrCreateVReg(*BrInst.getAddress());
   MIRBuilder.buildBrIndirect(Tgt);
 
   // Link successors.
   MachineBasicBlock &CurBB = MIRBuilder.getMBB();
-  for (const BasicBlock *Succ : BrInst.successors())
+  for (const BasicBlock *Succ : successors(&BrInst))
     CurBB.addSuccessor(&getMBB(*Succ));
 
   return true;
 }
 
 bool IRTranslator::translateLoad(const User &U, MachineIRBuilder &MIRBuilder) {
   const LoadInst &LI = cast<LoadInst>(U);
 

llvm/trunk/lib/IR/BasicBlock.cpp

 }
 
 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
   TerminatorInst *TI = getTerminator();
   if (!TI)
     // Cope with being called on a BasicBlock that doesn't have a terminator
     // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
     return;
-  for (BasicBlock *Succ : TI->successors()) {
+  for (BasicBlock *Succ : successors(TI)) {
     // N.B. Succ might not be a complete BasicBlock, so don't assume
     // that it ends with a non-phi instruction.
     for (iterator II = Succ->begin(), IE = Succ->end(); II != IE; ++II) {
       PHINode *PN = dyn_cast<PHINode>(II);
       if (!PN)
         break;
       int i;
       while ((i = PN->getBasicBlockIndex(this)) >= 0)

llvm/trunk/lib/IR/Instruction.cpp

bool Instruction::isAssociative() const {
   case FAdd:
     return cast<FPMathOperator>(this)->hasAllowReassoc() &&
            cast<FPMathOperator>(this)->hasNoSignedZeros();
   default:
     return false;
   }
 }
 
+unsigned Instruction::getNumSuccessors() const {
+  switch (getOpcode()) {
+#define HANDLE_TERM_INST(N, OPC, CLASS)                                        \
+  case Instruction::OPC:                                                       \
+    return static_cast<const CLASS *>(this)->getNumSuccessors();
+#include "llvm/IR/Instruction.def"
+  default:
+    break;
+  }
+  llvm_unreachable("not a terminator");
+}
+
+BasicBlock *Instruction::getSuccessor(unsigned idx) const {
+  switch (getOpcode()) {
+#define HANDLE_TERM_INST(N, OPC, CLASS)                                        \
+  case Instruction::OPC:                                                       \
+    return static_cast<const CLASS *>(this)->getSuccessor(idx);
+#include "llvm/IR/Instruction.def"
+  default:
+    break;
+  }
+  llvm_unreachable("not a terminator");
+}
+
+void Instruction::setSuccessor(unsigned idx, BasicBlock *B) {
+  switch (getOpcode()) {
+#define HANDLE_TERM_INST(N, OPC, CLASS)                                        \
+  case Instruction::OPC:                                                       \
+    return static_cast<CLASS *>(this)->setSuccessor(idx, B);
+#include "llvm/IR/Instruction.def"
+  default:
+    break;
+  }
+  llvm_unreachable("not a terminator");
+}
+
 Instruction *Instruction::cloneImpl() const {
   llvm_unreachable("Subclass of Instruction failed to implement cloneImpl");
 }
 
 void Instruction::swapProfMetadata() {
   MDNode *ProfileData = getMetadata(LLVMContext::MD_prof);
   if (!ProfileData || ProfileData->getNumOperands() != 3 ||
       !isa<MDString>(ProfileData->getOperand(0)))

llvm/trunk/lib/IR/Instructions.cpp

 User::op_iterator CallSite::getCallee() const {
   Instruction *II(getInstruction());
   return isCall()
     ? cast<CallInst>(II)->op_end() - 1 // Skip Callee
     : cast<InvokeInst>(II)->op_end() - 3; // Skip BB, BB, Callee
 }
 
 //===----------------------------------------------------------------------===//
-//                            TerminatorInst Class
-//===----------------------------------------------------------------------===//
-
-unsigned TerminatorInst::getNumSuccessors() const {
-  switch (getOpcode()) {
-#define HANDLE_TERM_INST(N, OPC, CLASS)                                        \
-  case Instruction::OPC:                                                       \
-    return static_cast<const CLASS *>(this)->getNumSuccessors();
-#include "llvm/IR/Instruction.def"
-  default:
-    break;
-  }
-  llvm_unreachable("not a terminator");
-}
-
-BasicBlock *TerminatorInst::getSuccessor(unsigned idx) const {
-  switch (getOpcode()) {
-#define HANDLE_TERM_INST(N, OPC, CLASS)                                        \
-  case Instruction::OPC:                                                       \
-    return static_cast<const CLASS *>(this)->getSuccessor(idx);
-#include "llvm/IR/Instruction.def"
-  default:
-    break;
-  }
-  llvm_unreachable("not a terminator");
-}
-
-void TerminatorInst::setSuccessor(unsigned idx, BasicBlock *B) {
-  switch (getOpcode()) {
-#define HANDLE_TERM_INST(N, OPC, CLASS)                                        \
-  case Instruction::OPC:                                                       \
-    return static_cast<CLASS *>(this)->setSuccessor(idx, B);
-#include "llvm/IR/Instruction.def"
-  default:
-    break;
-  }
-  llvm_unreachable("not a terminator");
-}
-
-//===----------------------------------------------------------------------===//
 //                              SelectInst Class
 //===----------------------------------------------------------------------===//
 
 /// areInvalidOperands - Return a string if the specified operands are invalid
 /// for a select operation, otherwise return null.
 const char *SelectInst::areInvalidOperands(Value *Op0, Value *Op1, Value *Op2) {
   if (Op1->getType() != Op2->getType())
     return "both values to select must have same type";

llvm/trunk/lib/Transforms/InstCombine/InstructionCombining.cpp

if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       }
     } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) {
       if (ConstantInt *Cond = dyn_cast<ConstantInt>(SI->getCondition())) {
         Worklist.push_back(SI->findCaseValue(Cond)->getCaseSuccessor());
         continue;
       }
     }
 
-    for (BasicBlock *SuccBB : TI->successors())
+    for (BasicBlock *SuccBB : successors(TI))
       Worklist.push_back(SuccBB);
   } while (!Worklist.empty());
 
   // Once we've found all of the instructions to add to instcombine's worklist,
   // add them in reverse order.  This way instcombine will visit from the top
   // of the function down.  This jives well with the way that it adds all uses
   // of instructions to the worklist after doing a transformation, thus avoiding
   // some N^2 behavior in pathological cases.

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

bool hasEH(const BasicBlock *BB) {
     }
 
     BBSideEffects[BB] = false;
     return false;
   }
 
   // Return true when a successor of BB dominates A.
   bool successorDominate(const BasicBlock *BB, const BasicBlock *A) {
-    for (const BasicBlock *Succ : BB->getTerminator()->successors())
+    for (const BasicBlock *Succ : successors(BB))
       if (DT->dominates(Succ, A))
         return true;
 
     return false;
   }
 
   // Return true when I1 appears before I2 in the instructions of BB.
   bool firstInBB(const Instruction *I1, const Instruction *I2) {
private:
   // Returns true when the values are flowing out to each edge.
   bool valueAnticipable(CHIArgs C, TerminatorInst *TI) const {
     if (TI->getNumSuccessors() > (unsigned)size(C))
       return false; // Not enough args in this CHI.
 
     for (auto CHI : C) {
       BasicBlock *Dest = CHI.Dest;
       // Find if all the edges have values flowing out of BB.
-      bool Found = llvm::any_of(TI->successors(), [Dest](const BasicBlock *BB) {
-          return BB == Dest; });
+      bool Found = llvm::any_of(
+          successors(TI), [Dest](const BasicBlock *BB) { return BB == Dest; });
       if (!Found)
         return false;
     }
     return true;
   }
 
   // Check if it is safe to hoist values tracked by CHI in the range
   // [Begin, End) and accumulate them in Safe.

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

bool LoopInterchangeLegality::tightlyNested(Loop *OuterLoop, Loop *InnerLoop) {
   // A perfectly nested loop will not have any branch in between the outer and
   // inner block i.e. outer header will branch to either inner preheader and
   // outerloop latch.
   BranchInst *OuterLoopHeaderBI =
       dyn_cast<BranchInst>(OuterLoopHeader->getTerminator());
   if (!OuterLoopHeaderBI)
     return false;
 
-  for (BasicBlock *Succ : OuterLoopHeaderBI->successors())
+  for (BasicBlock *Succ : successors(OuterLoopHeaderBI))
     if (Succ != InnerLoopPreHeader && Succ != OuterLoopLatch)
       return false;
 
   LLVM_DEBUG(dbgs() << "Checking instructions in Loop header and Loop latch\n");
   // We do not have any basic block in between now make sure the outer header
   // and outer loop latch doesn't contain any unsafe instructions.
   if (containsUnsafeInstructionsInHeader(OuterLoopHeader) ||
       containsUnsafeInstructionsInLatch(OuterLoopLatch))
void LoopInterchangeTransform::updateIncomingBlock(BasicBlock *CurrBlock,
   }
 }
 
 /// Update BI to jump to NewBB instead of OldBB. Records updates to
 /// the dominator tree in DTUpdates, if DT should be preserved.
 static void updateSuccessor(BranchInst *BI, BasicBlock *OldBB,
                             BasicBlock *NewBB,
                             std::vector<DominatorTree::UpdateType> &DTUpdates) {
-  assert(llvm::count_if(BI->successors(),
+  assert(llvm::count_if(successors(BI),
                         [OldBB](BasicBlock *BB) { return BB == OldBB; }) < 2 &&
          "BI must jump to OldBB at most once.");
   for (unsigned i = 0, e = BI->getNumSuccessors(); i < e; ++i) {
     if (BI->getSuccessor(i) == OldBB) {
       BI->setSuccessor(i, NewBB);
 
       DTUpdates.push_back(
           {DominatorTree::UpdateKind::Insert, BI->getParent(), NewBB});

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

assert((pred_begin(BB) == pred_end(BB) ||
          BB->getSinglePredecessor() == BB) && "Block is not dead!");
   TerminatorInst *BBTerm = BB->getTerminator();
   std::vector<DominatorTree::UpdateType> Updates;
 
   // Loop through all of our successors and make sure they know that one
   // of their predecessors is going away.
   if (DTU)
     Updates.reserve(BBTerm->getNumSuccessors());
-  for (BasicBlock *Succ : BBTerm->successors()) {
+  for (BasicBlock *Succ : successors(BBTerm)) {
     Succ->removePredecessor(BB);
     if (DTU)
       Updates.push_back({DominatorTree::Delete, BB, Succ});
   }
 
   // Zap all the instructions in the block.
   while (!BB->empty()) {
     Instruction &I = BB->back();

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

if (!TerminatorDone) {
 
     if (CodeInfo)
       if (auto CS = ImmutableCallSite(OldTI))
         if (CS.hasOperandBundles())
           CodeInfo->OperandBundleCallSites.push_back(NewInst);
 
     // Recursively clone any reachable successor blocks.
     const TerminatorInst *TI = BB->getTerminator();
-    for (const BasicBlock *Succ : TI->successors())
+    for (const BasicBlock *Succ : successors(TI))
       ToClone.push_back(Succ);
   }
 
   if (CodeInfo) {
     CodeInfo->ContainsCalls          |= hasCalls;
     CodeInfo->ContainsDynamicAllocas |= hasDynamicAllocas;
     CodeInfo->ContainsDynamicAllocas |= hasStaticAllocas &&
       BB != &BB->getParent()->front();

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

if (TheOnlyDest) {
       // Insert the new branch.
       Builder.CreateBr(TheOnlyDest);
       BasicBlock *BB = SI->getParent();
       std::vector <DominatorTree::UpdateType> Updates;
       if (DTU)
         Updates.reserve(SI->getNumSuccessors() - 1);
 
       // Remove entries from PHI nodes which we no longer branch to...
-      for (BasicBlock *Succ : SI->successors()) {
+      for (BasicBlock *Succ : successors(SI)) {
         // Found case matching a constant operand?
         if (Succ == TheOnlyDest) {
           TheOnlyDest = nullptr; // Don't modify the first branch to TheOnlyDest
         } else {
           Succ->removePredecessor(BB);
           if (DTU)
             Updates.push_back({DominatorTree::Delete, BB, Succ});
         }

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

if (C) {
         if (II->getIntrinsicID() == Intrinsic::assume)
           AC->registerAssumption(II);
     }
   }
 
   // Along with all the other instructions, we just cloned OrigHeader's
   // terminator into OrigPreHeader. Fix up the PHI nodes in each of OrigHeader's
   // successors by duplicating their incoming values for OrigHeader.
-  TerminatorInst *TI = OrigHeader->getTerminator();
-  for (BasicBlock *SuccBB : TI->successors())
+  for (BasicBlock *SuccBB : successors(OrigHeader))
     for (BasicBlock::iterator BI = SuccBB->begin();
          PHINode *PN = dyn_cast<PHINode>(BI); ++BI)
       PN->addIncoming(PN->getIncomingValueForBlock(OrigHeader), OrigPreheader);
 
   // Now that OrigPreHeader has a clone of OrigHeader's terminator, remove
   // OrigPreHeader's old terminator (the original branch into the loop), and
   // remove the corresponding incoming values from the PHI nodes in OrigHeader.
   LoopEntryBranch->eraseFromParent();

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

static bool SimplifyTerminatorOnSelect(TerminatorInst *OldTerm, Value *Cond,
   // Remove any superfluous successor edges from the CFG.
   // First, figure out which successors to preserve.
   // If TrueBB and FalseBB are equal, only try to preserve one copy of that
   // successor.
   BasicBlock *KeepEdge1 = TrueBB;
   BasicBlock *KeepEdge2 = TrueBB != FalseBB ? FalseBB : nullptr;
 
   // Then remove the rest.
-  for (BasicBlock *Succ : OldTerm->successors()) {
+  for (BasicBlock *Succ : successors(OldTerm)) {
     // Make sure only to keep exactly one copy of each edge.
     if (Succ == KeepEdge1)
       KeepEdge1 = nullptr;
     else if (Succ == KeepEdge2)
       KeepEdge2 = nullptr;
     else
       Succ->removePredecessor(OldTerm->getParent(),
                               /*DontDeleteUselessPHIs=*/true);