llvm/IR/CFG.h

0001 //===- CFG.h ----------------------------------------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 /// \file
0009 ///
0010 /// This file provides various utilities for inspecting and working with the
0011 /// control flow graph in LLVM IR. This includes generic facilities for
0012 /// iterating successors and predecessors of basic blocks, the successors of
0013 /// specific terminator instructions, etc. It also defines specializations of
0014 /// GraphTraits that allow Function and BasicBlock graphs to be treated as
0015 /// proper graphs for generic algorithms.
0016 ///
0017 //===----------------------------------------------------------------------===//
0018
0019 #ifndef LLVM_IR_CFG_H
0020 #define LLVM_IR_CFG_H
0021
0022 #include "llvm/ADT/GraphTraits.h"
0023 #include "llvm/ADT/iterator.h"
0024 #include "llvm/ADT/iterator_range.h"
0025 #include "llvm/IR/BasicBlock.h"
0026 #include "llvm/IR/Function.h"
0027 #include "llvm/IR/Value.h"
0028 #include <cassert>
0029 #include <cstddef>
0030 #include <iterator>
0031
0032 namespace llvm {
0033
0034 class Instruction;
0035 class Use;
0036
0037 //===----------------------------------------------------------------------===//
0038 // BasicBlock pred_iterator definition
0039 //===----------------------------------------------------------------------===//
0040
0041 template <class Ptr, class USE_iterator> // Predecessor Iterator
0042 class PredIterator {
0043 public:
0044   using iterator_category = std::forward_iterator_tag;
0045   using value_type = Ptr;
0046   using difference_type = std::ptrdiff_t;
0047   using pointer = Ptr *;
0048   using reference = Ptr *;
0049
0050 protected:
0051   using Self = PredIterator<Ptr, USE_iterator>;
0052   USE_iterator It;
0053
0054   inline void advancePastNonTerminators() {
0055     // Loop to ignore non-terminator uses (for example BlockAddresses).
0056     while (!It.atEnd()) {
0057       if (auto *Inst = dyn_cast<Instruction>(*It))
0058         if (Inst->isTerminator())
0059           break;
0060
0061       ++It;
0062     }
0063   }
0064
0065 public:
0066   PredIterator() = default;
0067   explicit inline PredIterator(Ptr *bb) : It(bb->user_begin()) {
0068     advancePastNonTerminators();
0069   }
0070   inline PredIterator(Ptr *bb, bool) : It(bb->user_end()) {}
0071
0072   inline bool operator==(const Self& x) const { return It == x.It; }
0073   inline bool operator!=(const Self& x) const { return !operator==(x); }
0074
0075   inline reference operator*() const {
0076     assert(!It.atEnd() && "pred_iterator out of range!");
0077     return cast<Instruction>(*It)->getParent();
0078   }
0079   inline pointer *operator->() const { return &operator*(); }
0080
0081   inline Self& operator++() {   // Preincrement
0082     assert(!It.atEnd() && "pred_iterator out of range!");
0083     ++It; advancePastNonTerminators();
0084     return *this;
0085   }
0086
0087   inline Self operator++(int) { // Postincrement
0088     Self tmp = *this; ++*this; return tmp;
0089   }
0090
0091   /// getOperandNo - Return the operand number in the predecessor's
0092   /// terminator of the successor.
0093   unsigned getOperandNo() const {
0094     return It.getOperandNo();
0095   }
0096
0097   /// getUse - Return the operand Use in the predecessor's terminator
0098   /// of the successor.
0099   Use &getUse() const {
0100     return It.getUse();
0101   }
0102 };
0103
0104 using pred_iterator = PredIterator<BasicBlock, Value::user_iterator>;
0105 using const_pred_iterator =
0106     PredIterator<const BasicBlock, Value::const_user_iterator>;
0107 using pred_range = iterator_range<pred_iterator>;
0108 using const_pred_range = iterator_range<const_pred_iterator>;
0109
0110 inline pred_iterator pred_begin(BasicBlock *BB) { return pred_iterator(BB); }
0111 inline const_pred_iterator pred_begin(const BasicBlock *BB) {
0112   return const_pred_iterator(BB);
0113 }
0114 inline pred_iterator pred_end(BasicBlock *BB) { return pred_iterator(BB, true);}
0115 inline const_pred_iterator pred_end(const BasicBlock *BB) {
0116   return const_pred_iterator(BB, true);
0117 }
0118 inline bool pred_empty(const BasicBlock *BB) {
0119   return pred_begin(BB) == pred_end(BB);
0120 }
0121 /// Get the number of predecessors of \p BB. This is a linear time operation.
0122 /// Use \ref BasicBlock::hasNPredecessors() or hasNPredecessorsOrMore if able.
0123 inline unsigned pred_size(const BasicBlock *BB) {
0124   return std::distance(pred_begin(BB), pred_end(BB));
0125 }
0126 inline pred_range predecessors(BasicBlock *BB) {
0127   return pred_range(pred_begin(BB), pred_end(BB));
0128 }
0129 inline const_pred_range predecessors(const BasicBlock *BB) {
0130   return const_pred_range(pred_begin(BB), pred_end(BB));
0131 }
0132
0133 //===----------------------------------------------------------------------===//
0134 // Instruction and BasicBlock succ_iterator helpers
0135 //===----------------------------------------------------------------------===//
0136
0137 template <class InstructionT, class BlockT>
0138 class SuccIterator
0139     : public iterator_facade_base<SuccIterator<InstructionT, BlockT>,
0140                                   std::random_access_iterator_tag, BlockT, int,
0141                                   BlockT *, BlockT *> {
0142 public:
0143   using difference_type = int;
0144   using pointer = BlockT *;
0145   using reference = BlockT *;
0146
0147 private:
0148   InstructionT *Inst;
0149   int Idx;
0150   using Self = SuccIterator<InstructionT, BlockT>;
0151
0152   inline bool index_is_valid(int Idx) {
0153     // Note that we specially support the index of zero being valid even in the
0154     // face of a null instruction.
0155     return Idx >= 0 && (Idx == 0 || Idx <= (int)Inst->getNumSuccessors());
0156   }
0157
0158   /// Proxy object to allow write access in operator[]
0159   class SuccessorProxy {
0160     Self It;
0161
0162   public:
0163     explicit SuccessorProxy(const Self &It) : It(It) {}
0164
0165     SuccessorProxy(const SuccessorProxy &) = default;
0166
0167     SuccessorProxy &operator=(SuccessorProxy RHS) {
0168       *this = reference(RHS);
0169       return *this;
0170     }
0171
0172     SuccessorProxy &operator=(reference RHS) {
0173       It.Inst->setSuccessor(It.Idx, RHS);
0174       return *this;
0175     }
0176
0177     operator reference() const { return *It; }
0178   };
0179
0180 public:
0181   // begin iterator
0182   explicit inline SuccIterator(InstructionT *Inst) : Inst(Inst), Idx(0) {}
0183   // end iterator
0184   inline SuccIterator(InstructionT *Inst, bool) : Inst(Inst) {
0185     if (Inst)
0186       Idx = Inst->getNumSuccessors();
0187     else
0188       // Inst == NULL happens, if a basic block is not fully constructed and
0189       // consequently getTerminator() returns NULL. In this case we construct
0190       // a SuccIterator which describes a basic block that has zero
0191       // successors.
0192       // Defining SuccIterator for incomplete and malformed CFGs is especially
0193       // useful for debugging.
0194       Idx = 0;
0195   }
0196
0197   /// This is used to interface between code that wants to
0198   /// operate on terminator instructions directly.
0199   int getSuccessorIndex() const { return Idx; }
0200
0201   inline bool operator==(const Self &x) const { return Idx == x.Idx; }
0202
0203   inline BlockT *operator*() const { return Inst->getSuccessor(Idx); }
0204
0205   // We use the basic block pointer directly for operator->.
0206   inline BlockT *operator->() const { return operator*(); }
0207
0208   inline bool operator<(const Self &RHS) const {
0209     assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
0210     return Idx < RHS.Idx;
0211   }
0212
0213   int operator-(const Self &RHS) const {
0214     assert(Inst == RHS.Inst && "Cannot compare iterators of different blocks!");
0215     return Idx - RHS.Idx;
0216   }
0217
0218   inline Self &operator+=(int RHS) {
0219     int NewIdx = Idx + RHS;
0220     assert(index_is_valid(NewIdx) && "Iterator index out of bound");
0221     Idx = NewIdx;
0222     return *this;
0223   }
0224
0225   inline Self &operator-=(int RHS) { return operator+=(-RHS); }
0226
0227   // Specially implement the [] operation using a proxy object to support
0228   // assignment.
0229   inline SuccessorProxy operator[](int Offset) {
0230     Self TmpIt = *this;
0231     TmpIt += Offset;
0232     return SuccessorProxy(TmpIt);
0233   }
0234
0235   /// Get the source BlockT of this iterator.
0236   inline BlockT *getSource() {
0237     assert(Inst && "Source not available, if basic block was malformed");
0238     return Inst->getParent();
0239   }
0240 };
0241
0242 using succ_iterator = SuccIterator<Instruction, BasicBlock>;
0243 using const_succ_iterator = SuccIterator<const Instruction, const BasicBlock>;
0244 using succ_range = iterator_range<succ_iterator>;
0245 using const_succ_range = iterator_range<const_succ_iterator>;
0246
0247 inline succ_iterator succ_begin(Instruction *I) { return succ_iterator(I); }
0248 inline const_succ_iterator succ_begin(const Instruction *I) {
0249   return const_succ_iterator(I);
0250 }
0251 inline succ_iterator succ_end(Instruction *I) { return succ_iterator(I, true); }
0252 inline const_succ_iterator succ_end(const Instruction *I) {
0253   return const_succ_iterator(I, true);
0254 }
0255 inline bool succ_empty(const Instruction *I) {
0256   return succ_begin(I) == succ_end(I);
0257 }
0258 inline unsigned succ_size(const Instruction *I) {
0259   return std::distance(succ_begin(I), succ_end(I));
0260 }
0261 inline succ_range successors(Instruction *I) {
0262   return succ_range(succ_begin(I), succ_end(I));
0263 }
0264 inline const_succ_range successors(const Instruction *I) {
0265   return const_succ_range(succ_begin(I), succ_end(I));
0266 }
0267
0268 inline succ_iterator succ_begin(BasicBlock *BB) {
0269   return succ_iterator(BB->getTerminator());
0270 }
0271 inline const_succ_iterator succ_begin(const BasicBlock *BB) {
0272   return const_succ_iterator(BB->getTerminator());
0273 }
0274 inline succ_iterator succ_end(BasicBlock *BB) {
0275   return succ_iterator(BB->getTerminator(), true);
0276 }
0277 inline const_succ_iterator succ_end(const BasicBlock *BB) {
0278   return const_succ_iterator(BB->getTerminator(), true);
0279 }
0280 inline bool succ_empty(const BasicBlock *BB) {
0281   return succ_begin(BB) == succ_end(BB);
0282 }
0283 inline unsigned succ_size(const BasicBlock *BB) {
0284   return std::distance(succ_begin(BB), succ_end(BB));
0285 }
0286 inline succ_range successors(BasicBlock *BB) {
0287   return succ_range(succ_begin(BB), succ_end(BB));
0288 }
0289 inline const_succ_range successors(const BasicBlock *BB) {
0290   return const_succ_range(succ_begin(BB), succ_end(BB));
0291 }
0292
0293 //===--------------------------------------------------------------------===//
0294 // GraphTraits specializations for basic block graphs (CFGs)
0295 //===--------------------------------------------------------------------===//
0296
0297 // Provide specializations of GraphTraits to be able to treat a function as a
0298 // graph of basic blocks...
0299
0300 template <> struct GraphTraits<BasicBlock*> {
0301   using NodeRef = BasicBlock *;
0302   using ChildIteratorType = succ_iterator;
0303
0304   static NodeRef getEntryNode(BasicBlock *BB) { return BB; }
0305   static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
0306   static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
0307
0308   static unsigned getNumber(const BasicBlock *BB) { return BB->getNumber(); }
0309 };
0310
0311 static_assert(GraphHasNodeNumbers<BasicBlock *>,
0312               "GraphTraits getNumber() not detected");
0313
0314 template <> struct GraphTraits<const BasicBlock*> {
0315   using NodeRef = const BasicBlock *;
0316   using ChildIteratorType = const_succ_iterator;
0317
0318   static NodeRef getEntryNode(const BasicBlock *BB) { return BB; }
0319
0320   static ChildIteratorType child_begin(NodeRef N) { return succ_begin(N); }
0321   static ChildIteratorType child_end(NodeRef N) { return succ_end(N); }
0322
0323   static unsigned getNumber(const BasicBlock *BB) { return BB->getNumber(); }
0324 };
0325
0326 static_assert(GraphHasNodeNumbers<const BasicBlock *>,
0327               "GraphTraits getNumber() not detected");
0328
0329 // Provide specializations of GraphTraits to be able to treat a function as a
0330 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
0331 // a function is considered to be when traversing the predecessor edges of a BB
0332 // instead of the successor edges.
0333 //
0334 template <> struct GraphTraits<Inverse<BasicBlock*>> {
0335   using NodeRef = BasicBlock *;
0336   using ChildIteratorType = pred_iterator;
0337
0338   static NodeRef getEntryNode(Inverse<BasicBlock *> G) { return G.Graph; }
0339   static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
0340   static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
0341
0342   static unsigned getNumber(const BasicBlock *BB) { return BB->getNumber(); }
0343 };
0344
0345 static_assert(GraphHasNodeNumbers<Inverse<BasicBlock *>>,
0346               "GraphTraits getNumber() not detected");
0347
0348 template <> struct GraphTraits<Inverse<const BasicBlock*>> {
0349   using NodeRef = const BasicBlock *;
0350   using ChildIteratorType = const_pred_iterator;
0351
0352   static NodeRef getEntryNode(Inverse<const BasicBlock *> G) { return G.Graph; }
0353   static ChildIteratorType child_begin(NodeRef N) { return pred_begin(N); }
0354   static ChildIteratorType child_end(NodeRef N) { return pred_end(N); }
0355
0356   static unsigned getNumber(const BasicBlock *BB) { return BB->getNumber(); }
0357 };
0358
0359 static_assert(GraphHasNodeNumbers<Inverse<const BasicBlock *>>,
0360               "GraphTraits getNumber() not detected");
0361
0362 //===--------------------------------------------------------------------===//
0363 // GraphTraits specializations for function basic block graphs (CFGs)
0364 //===--------------------------------------------------------------------===//
0365
0366 // Provide specializations of GraphTraits to be able to treat a function as a
0367 // graph of basic blocks... these are the same as the basic block iterators,
0368 // except that the root node is implicitly the first node of the function.
0369 //
0370 template <> struct GraphTraits<Function*> : public GraphTraits<BasicBlock*> {
0371   static NodeRef getEntryNode(Function *F) { return &F->getEntryBlock(); }
0372
0373   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
0374   using nodes_iterator = pointer_iterator<Function::iterator>;
0375
0376   static nodes_iterator nodes_begin(Function *F) {
0377     return nodes_iterator(F->begin());
0378   }
0379
0380   static nodes_iterator nodes_end(Function *F) {
0381     return nodes_iterator(F->end());
0382   }
0383
0384   static size_t size(Function *F) { return F->size(); }
0385
0386   static unsigned getMaxNumber(const Function *F) {
0387     return F->getMaxBlockNumber();
0388   }
0389   static unsigned getNumberEpoch(const Function *F) {
0390     return F->getBlockNumberEpoch();
0391   }
0392 };
0393 template <> struct GraphTraits<const Function*> :
0394   public GraphTraits<const BasicBlock*> {
0395   static NodeRef getEntryNode(const Function *F) { return &F->getEntryBlock(); }
0396
0397   // nodes_iterator/begin/end - Allow iteration over all nodes in the graph
0398   using nodes_iterator = pointer_iterator<Function::const_iterator>;
0399
0400   static nodes_iterator nodes_begin(const Function *F) {
0401     return nodes_iterator(F->begin());
0402   }
0403
0404   static nodes_iterator nodes_end(const Function *F) {
0405     return nodes_iterator(F->end());
0406   }
0407
0408   static size_t size(const Function *F) { return F->size(); }
0409
0410   static unsigned getMaxNumber(const Function *F) {
0411     return F->getMaxBlockNumber();
0412   }
0413   static unsigned getNumberEpoch(const Function *F) {
0414     return F->getBlockNumberEpoch();
0415   }
0416 };
0417
0418 // Provide specializations of GraphTraits to be able to treat a function as a
0419 // graph of basic blocks... and to walk it in inverse order.  Inverse order for
0420 // a function is considered to be when traversing the predecessor edges of a BB
0421 // instead of the successor edges.
0422 //
0423 template <> struct GraphTraits<Inverse<Function*>> :
0424   public GraphTraits<Inverse<BasicBlock*>> {
0425   static NodeRef getEntryNode(Inverse<Function *> G) {
0426     return &G.Graph->getEntryBlock();
0427   }
0428
0429   static unsigned getMaxNumber(const Function *F) {
0430     return F->getMaxBlockNumber();
0431   }
0432   static unsigned getNumberEpoch(const Function *F) {
0433     return F->getBlockNumberEpoch();
0434   }
0435 };
0436 template <> struct GraphTraits<Inverse<const Function*>> :
0437   public GraphTraits<Inverse<const BasicBlock*>> {
0438   static NodeRef getEntryNode(Inverse<const Function *> G) {
0439     return &G.Graph->getEntryBlock();
0440   }
0441
0442   static unsigned getMaxNumber(const Function *F) {
0443     return F->getMaxBlockNumber();
0444   }
0445   static unsigned getNumberEpoch(const Function *F) {
0446     return F->getBlockNumberEpoch();
0447   }
0448 };
0449
0450 } // end namespace llvm
0451
0452 #endif // LLVM_IR_CFG_H