diff --git a/llvm/include/llvm/IR/BasicBlock.h b/llvm/include/llvm/IR/BasicBlock.h --- a/llvm/include/llvm/IR/BasicBlock.h +++ b/llvm/include/llvm/IR/BasicBlock.h @@ -20,6 +20,7 @@ #include "llvm/ADT/iterator.h" #include "llvm/ADT/iterator_range.h" #include "llvm/IR/Instruction.h" +#include "llvm/IR/IteratorsHelper.h" #include "llvm/IR/SymbolTableListTraits.h" #include "llvm/IR/Value.h" #include "llvm/Support/CBindingWrapping.h" @@ -91,6 +92,44 @@ using reverse_iterator = InstListType::reverse_iterator; using const_reverse_iterator = InstListType::const_reverse_iterator; + /// Successor and predecessor iterators. + using succ_iterator = SuccIterator; + using const_succ_iterator = SuccIterator; + using succ_range = iterator_range; + using const_succ_range = iterator_range; + using pred_iterator = PredIterator; + using const_pred_iterator = + PredIterator; + using pred_range = iterator_range; + using const_pred_range = iterator_range; + + succ_iterator succ_begin() { return succ_iterator(getTerminator()); } + const_succ_iterator succ_begin() const { + return const_succ_iterator(getTerminator()); + } + succ_iterator succ_end() { return succ_iterator(getTerminator(), true); } + const_succ_iterator succ_end() const { + return const_succ_iterator(getTerminator(), true); + } + bool succ_empty() const { return succ_begin() == succ_end(); } + unsigned succ_size() const { return std::distance(succ_begin(), succ_end()); } + succ_range successors() { return succ_range(succ_begin(), succ_end()); } + const_succ_range successors() const { + return const_succ_range(succ_begin(), succ_end()); + } + pred_iterator pred_begin() { return pred_iterator(this); } + const_pred_iterator pred_begin() const { return const_pred_iterator(this); } + pred_iterator pred_end() { return pred_iterator(this, true); } + const_pred_iterator pred_end() const { + return const_pred_iterator(this, true); + } + bool pred_empty() const { return pred_begin() == pred_end(); } + unsigned pred_size() const { return std::distance(pred_begin(), pred_end()); } + pred_range predecessors() { return pred_range(pred_begin(), pred_end()); } + const_pred_range predecessors() const { + return const_pred_range(pred_begin(), pred_end()); + } + /// Creates a new BasicBlock. /// /// If the Parent parameter is specified, the basic block is automatically diff --git a/llvm/include/llvm/IR/CFG.h b/llvm/include/llvm/IR/CFG.h --- a/llvm/include/llvm/IR/CFG.h +++ b/llvm/include/llvm/IR/CFG.h @@ -34,84 +34,18 @@ namespace llvm { -//===----------------------------------------------------------------------===// -// BasicBlock pred_iterator definition -//===----------------------------------------------------------------------===// - -template // Predecessor Iterator -class PredIterator : public std::iterator { - using super = - std::iterator; - using Self = PredIterator; - USE_iterator It; - - inline void advancePastNonTerminators() { - // Loop to ignore non-terminator uses (for example BlockAddresses). - while (!It.atEnd()) { - if (auto *Inst = dyn_cast(*It)) - if (Inst->isTerminator()) - break; - - ++It; - } - } - -public: - using pointer = typename super::pointer; - using reference = typename super::reference; - - PredIterator() = default; - explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) { - advancePastNonTerminators(); - } - inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {} - - inline bool operator==(const Self& x) const { return It == x.It; } - inline bool operator!=(const Self& x) const { return !operator==(x); } - - inline reference operator*() const { - assert(!It.atEnd() && "pred_iterator out of range!"); - return cast(*It)->getParent(); - } - inline pointer *operator->() const { return &operator*(); } - - inline Self& operator++() { // Preincrement - assert(!It.atEnd() && "pred_iterator out of range!"); - ++It; advancePastNonTerminators(); - return *this; - } - - inline Self operator++(int) { // Postincrement - Self tmp = *this; ++*this; return tmp; - } - - /// getOperandNo - Return the operand number in the predecessor's - /// terminator of the successor. - unsigned getOperandNo() const { - return It.getOperandNo(); - } - - /// getUse - Return the operand Use in the predecessor's terminator - /// of the successor. - Use &getUse() const { - return It.getUse(); - } -}; - -using pred_iterator = PredIterator; -using const_pred_iterator = - PredIterator; +using pred_iterator = BasicBlock::pred_iterator; +using const_pred_iterator = BasicBlock::const_pred_iterator; using pred_range = iterator_range; using const_pred_range = iterator_range; -inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); } +inline pred_iterator pred_begin(BasicBlock *BB) { return BB->pred_begin(); } inline const_pred_iterator pred_begin(const BasicBlock *BB) { - return const_pred_iterator(BB); + return BB->pred_begin(); } -inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);} +inline pred_iterator pred_end(BasicBlock *BB) { return BB->pred_end(); } inline const_pred_iterator pred_end(const BasicBlock *BB) { - return const_pred_iterator(BB, true); + return BB->pred_end(); } inline bool pred_empty(const BasicBlock *BB) { return pred_begin(BB) == pred_end(BB); @@ -128,127 +62,18 @@ return const_pred_range(pred_begin(BB), pred_end(BB)); } -//===----------------------------------------------------------------------===// -// Instruction and BasicBlock succ_iterator helpers -//===----------------------------------------------------------------------===// - -template -class SuccIterator - : public iterator_facade_base, - 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; - - 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(); - } -}; - -using succ_iterator = SuccIterator; -using const_succ_iterator = SuccIterator; +using succ_iterator = BasicBlock::succ_iterator; +using const_succ_iterator = BasicBlock::const_succ_iterator; using succ_range = iterator_range; using const_succ_range = iterator_range; -inline succ_iterator succ_begin(Instruction *I) { return succ_iterator(I); } +inline succ_iterator succ_begin(Instruction *I) { return I->succ_begin(); } inline const_succ_iterator succ_begin(const Instruction *I) { - return const_succ_iterator(I); + return I->succ_begin(); } -inline succ_iterator succ_end(Instruction *I) { return succ_iterator(I, true); } +inline succ_iterator succ_end(Instruction *I) { return I->succ_end(); } inline const_succ_iterator succ_end(const Instruction *I) { - return const_succ_iterator(I, true); + return I->succ_end(); } inline bool succ_empty(const Instruction *I) { return succ_begin(I) == succ_end(I); @@ -263,17 +88,13 @@ return const_succ_range(succ_begin(I), succ_end(I)); } -inline succ_iterator succ_begin(BasicBlock *BB) { - return succ_iterator(BB->getTerminator()); -} +inline succ_iterator succ_begin(BasicBlock *BB) { return BB->succ_begin(); } inline const_succ_iterator succ_begin(const BasicBlock *BB) { - return const_succ_iterator(BB->getTerminator()); -} -inline succ_iterator succ_end(BasicBlock *BB) { - return succ_iterator(BB->getTerminator(), true); + return BB->succ_begin(); } +inline succ_iterator succ_end(BasicBlock *BB) { return BB->succ_end(); } inline const_succ_iterator succ_end(const BasicBlock *BB) { - return const_succ_iterator(BB->getTerminator(), true); + return BB->succ_end(); } inline bool succ_empty(const BasicBlock *BB) { return succ_begin(BB) == succ_end(BB); diff --git a/llvm/include/llvm/IR/Instruction.h b/llvm/include/llvm/IR/Instruction.h --- a/llvm/include/llvm/IR/Instruction.h +++ b/llvm/include/llvm/IR/Instruction.h @@ -19,6 +19,7 @@ #include "llvm/ADT/StringRef.h" #include "llvm/ADT/ilist_node.h" #include "llvm/IR/DebugLoc.h" +#include "llvm/IR/IteratorsHelper.h" #include "llvm/IR/SymbolTableListTraits.h" #include "llvm/IR/User.h" #include "llvm/IR/Value.h" @@ -62,6 +63,25 @@ Instruction(const Instruction &) = delete; Instruction &operator=(const Instruction &) = delete; + /// Successor iterators. + using succ_iterator = SuccIterator; + using const_succ_iterator = SuccIterator; + using succ_range = iterator_range; + using const_succ_range = iterator_range; + + succ_iterator succ_begin() { return succ_iterator(this); } + const_succ_iterator succ_begin() const { return const_succ_iterator(this); } + succ_iterator succ_end() { return succ_iterator(this, true); } + const_succ_iterator succ_end() const { + return const_succ_iterator(this, true); + } + bool succ_empty() const { return succ_begin() == succ_end(); } + unsigned succ_size() const { return std::distance(succ_begin(), succ_end()); } + succ_range successors() { return succ_range(succ_begin(), succ_end()); } + const_succ_range successors() const { + return const_succ_range(succ_begin(), succ_end()); + } + /// Specialize the methods defined in Value, as we know that an instruction /// can only be used by other instructions. Instruction *user_back() { return cast(*user_begin());} diff --git a/llvm/include/llvm/IR/IteratorsHelper.h b/llvm/include/llvm/IR/IteratorsHelper.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/IR/IteratorsHelper.h @@ -0,0 +1,203 @@ +//===- IteratorsHelper.h ---------------------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +/// \file +/// +/// This file provides generic facilities for iterating successors and +/// predecessors of basic blocks, the successors of specific terminator +/// instructions, etc. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_IR_ITERATORSHELPER_H +#define LLVM_IR_ITERATORSHELPER_H + +#include "llvm/ADT/iterator.h" +#include "llvm/ADT/iterator_range.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/type_traits.h" +#include +#include +#include + +namespace llvm { + +//===----------------------------------------------------------------------===// +// BasicBlock pred_iterator definition +//===----------------------------------------------------------------------===// + +template // Predecessor Iterator +class PredIterator : public std::iterator { + using super = + std::iterator; + using Self = PredIterator; + USE_iterator It; + + inline void advancePastNonTerminators() { + // Loop to ignore non-terminator uses (for example BlockAddresses). + while (!It.atEnd()) { + if (auto *Inst = dyn_cast(*It)) + if (Inst->isTerminator()) + break; + + ++It; + } + } + +public: + using pointer = typename super::pointer; + using reference = typename super::reference; + + PredIterator() = default; + explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) { + advancePastNonTerminators(); + } + inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {} + + inline bool operator==(const Self &x) const { return It == x.It; } + inline bool operator!=(const Self &x) const { return !operator==(x); } + + inline reference operator*() const { + assert(!It.atEnd() && "pred_iterator out of range!"); + return cast(*It)->getParent(); + } + inline pointer *operator->() const { return &operator*(); } + + inline Self &operator++() { // Preincrement + assert(!It.atEnd() && "pred_iterator out of range!"); + ++It; + advancePastNonTerminators(); + return *this; + } + + inline Self operator++(int) { // Postincrement + Self tmp = *this; + ++*this; + return tmp; + } + + /// getOperandNo - Return the operand number in the predecessor's + /// terminator of the successor. + unsigned getOperandNo() const { return It.getOperandNo(); } + + /// getUse - Return the operand Use in the predecessor's terminator + /// of the successor. + Use &getUse() const { return It.getUse(); } +}; + +//===----------------------------------------------------------------------===// +// Instruction and BasicBlock succ_iterator helpers +//===----------------------------------------------------------------------===// + +template +class SuccIterator + : public iterator_facade_base, + 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; + + 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(); + } +}; +} // end namespace llvm + +#endif // LLVM_IR_ITERATORSHELPER_H diff --git a/llvm/lib/IR/BasicBlock.cpp b/llvm/lib/IR/BasicBlock.cpp --- a/llvm/lib/IR/BasicBlock.cpp +++ b/llvm/lib/IR/BasicBlock.cpp @@ -256,7 +256,7 @@ /// If this basic block has a single predecessor block, /// return the block, otherwise return a null pointer. const BasicBlock *BasicBlock::getSinglePredecessor() const { - const_pred_iterator PI = pred_begin(this), E = pred_end(this); + const_pred_iterator PI = pred_begin(), E = pred_end(); if (PI == E) return nullptr; // No preds. const BasicBlock *ThePred = *PI; ++PI; @@ -269,7 +269,7 @@ /// multiple edges from the unique predecessor to this block (for example /// a switch statement with multiple cases having the same destination). const BasicBlock *BasicBlock::getUniquePredecessor() const { - const_pred_iterator PI = pred_begin(this), E = pred_end(this); + const_pred_iterator PI = pred_begin(), E = pred_end(); if (PI == E) return nullptr; // No preds. const BasicBlock *PredBB = *PI; ++PI; @@ -283,15 +283,15 @@ } bool BasicBlock::hasNPredecessors(unsigned N) const { - return hasNItems(pred_begin(this), pred_end(this), N); + return hasNItems(pred_begin(), pred_end(), N); } bool BasicBlock::hasNPredecessorsOrMore(unsigned N) const { - return hasNItemsOrMore(pred_begin(this), pred_end(this), N); + return hasNItemsOrMore(pred_begin(), pred_end(), N); } const BasicBlock *BasicBlock::getSingleSuccessor() const { - const_succ_iterator SI = succ_begin(this), E = succ_end(this); + const_succ_iterator SI = succ_begin(), E = succ_end(); if (SI == E) return nullptr; // no successors const BasicBlock *TheSucc = *SI; ++SI; @@ -299,7 +299,7 @@ } const BasicBlock *BasicBlock::getUniqueSuccessor() const { - const_succ_iterator SI = succ_begin(this), E = succ_end(this); + const_succ_iterator SI = succ_begin(), E = succ_end(); if (SI == E) return nullptr; // No successors const BasicBlock *SuccBB = *SI; ++SI; @@ -325,9 +325,10 @@ /// void BasicBlock::removePredecessor(BasicBlock *Pred, bool KeepOneInputPHIs) { - assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs. - find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) && - "removePredecessor: BB is not a predecessor!"); + assert( + (hasNUsesOrMore(16) || // Reduce cost of this assertion for complex CFGs. + find(pred_begin(), pred_end(), Pred) != pred_end()) && + "removePredecessor: BB is not a predecessor!"); if (InstList.empty()) return; PHINode *APN = dyn_cast(&front()); @@ -474,7 +475,7 @@ // Cope with being called on a BasicBlock that doesn't have a terminator // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this. return; - llvm::for_each(successors(TI), [Old, New](BasicBlock *Succ) { + llvm::for_each(TI->successors(), [Old, New](BasicBlock *Succ) { Succ->replacePhiUsesWith(Old, New); }); }