block.h

// This file if part of the llir-opt project.
// Licensing information can be found in the LICENSE file.
// (C) 2018 Nandor Licker. All rights reserved.
 
#pragma once
 
#include <string>
#include <string_view>
#include <vector>
 
#include <llvm/ADT/ilist.h>
#include <llvm/ADT/ilist_node.h>
#include <llvm/ADT/iterator_range.h>
#include <llvm/IR/CFG.h>
#include <llvm/Support/raw_ostream.h>
 
#include "core/inst.h"
#include "core/global.h"
#include "core/symbol_table.h"
 
class Func;
class PhiInst;
 
 
 
class Block final : public llvm::ilist_node_with_parent<Block, Func>, public Global {
public:
  static constexpr Global::Kind kGlobalKind = Global::Kind::BLOCK;
 
public:
  // Type of the instruction list.
  using InstListType = llvm::ilist<Inst>;
 
  // Iterator types over instructions.
  using iterator = InstListType::iterator;
  using reverse_iterator = InstListType::reverse_iterator;
  using const_iterator = InstListType::const_iterator;
  using const_reverse_iterator = InstListType::const_reverse_iterator;
 
  // Iterator wrapper.
  template<typename T>
  using iter_fwd = std::iterator<std::forward_iterator_tag, T, ptrdiff_t, T *, T *>;
 
  template <class BlockT, class UseIterator>
  class PredIterator : public iter_fwd<BlockT> {
  private:
    using Self = PredIterator<BlockT, UseIterator>;
    UseIterator use_;
 
  public:
    using pointer = typename iter_fwd<BlockT>::pointer;
    using reference = typename iter_fwd<BlockT>::reference;
 
    PredIterator() = default;
 
    inline PredIterator(UseIterator it) : use_(it) { SkipToTerminator(); }
 
    inline bool operator==(const PredIterator& x) const { return use_ == x.use_; }
    inline bool operator!=(const PredIterator& x) const { return !operator==(x); }
 
    inline reference operator*() const
    {
      return static_cast<const TerminatorInst *>(*use_)->getParent();
    }
 
    inline pointer *operator->() const
    {
      return &operator*();
    }
 
    inline PredIterator& operator++()
    {
      ++use_;
      SkipToTerminator();
      return *this;
    }
 
    inline PredIterator operator++(int) {
      PredIterator tmp = *this;
      ++*this;
      return tmp;
    }
 
  private:
    inline void SkipToTerminator()
    {
      while (!use_.atEnd()) {
        if (!*use_ || !(*use_)->Is(Value::Kind::INST)) {
          ++use_;
          continue;
        }
 
        if (!static_cast<const Inst *>(*use_)->IsTerminator()) {
          ++use_;
          continue;
        }
 
        break;
      }
    }
  };
 
  // Iterator over connected basic blocks.
  using succ_iterator = llvm::SuccIterator<TerminatorInst, Block>;
  using const_succ_iterator = llvm::SuccIterator<const TerminatorInst, const Block>;
  using pred_iterator = PredIterator<Block, Value::user_iterator>;
  using const_pred_iterator = PredIterator<const Block, Value::const_user_iterator>;
 
  // Forward iterator wrapper.
  template<typename It, typename T>
  using facade_fwd = llvm::iterator_facade_base<It, std::forward_iterator_tag, T>;
 
  template<typename PhiT, typename IterT>
  class PhiIterator : public facade_fwd<PhiIterator<PhiT, IterT>, PhiT> {
  public:
    template <typename PhiU, typename IterU>
    PhiIterator(const PhiIterator<PhiU, IterU> &rhs)
      : phi_(rhs.phi_)
    {
    }
 
    bool operator == (const PhiIterator &rhs) const { return phi_ == rhs.phi_; }
 
    PhiT &operator * () const { return *phi_; }
 
    PhiIterator &operator ++ ()
    {
      auto end = phi_->getParent()->end();
      auto it = std::next(IterT(phi_));
      if (it != end && it->Is(Inst::Kind::PHI)) {
        phi_ = static_cast<PhiT *>(&*it);
      } else {
        phi_ = nullptr;
      }
      return *this;
    }
 
    PhiIterator &operator ++ (int)
    {
      PhiIterator it = *this;
      *this++;
      return it;
    }
 
  private:
    PhiIterator(PhiT *phi_) : phi_(phi_) {}
 
  private:
    friend Block;
    PhiT *phi_;
  };
 
  using phi_iterator = PhiIterator<PhiInst, iterator>;
  using const_phi_iterator = PhiIterator<const PhiInst, const_iterator>;
 
public:
  Block(
      const std::string_view name,
      Visibility visibility = Visibility::LOCAL
  );
 
  ~Block();
 
  void removeFromParent() override;
  void eraseFromParent() override;
 
  void AddInst(Inst *inst, Inst *before = nullptr);
 
  void AddPhi(PhiInst *phi);
 
  Func *getParent() const { return parent_; }
 
  TerminatorInst *GetTerminator();
  const TerminatorInst *GetTerminator() const;
 
  std::optional<llvm::Align> GetAlignment() const override
  {
    return llvm::Align(1u);
  }
 
  bool HasAddressTaken() const;
  bool IsLandingPad() const;
  bool IsTrap() const;
 
  void insert(Inst *inst, iterator it);
  void insertAfter(Inst *inst, iterator it);
 
  void remove(iterator it);
  void erase(iterator it);
  void erase(iterator first, iterator last);
 
  void clear();
 
  // Iterator over the instructions.
  bool empty() const { return insts_.empty(); }
  iterator begin() { return insts_.begin(); }
  iterator end() { return insts_.end(); }
  const_iterator begin() const { return insts_.begin(); }
  const_iterator end() const { return insts_.end(); }
  reverse_iterator rbegin() { return insts_.rbegin(); }
  reverse_iterator rend() { return insts_.rend(); }
  const_reverse_iterator rbegin() const { return insts_.rbegin(); }
  const_reverse_iterator rend() const { return insts_.rend(); }
 
  size_t size() const { return insts_.size(); }
 
  // Iterator over the successors.
  succ_iterator succ_begin();
  succ_iterator succ_end();
  inline llvm::iterator_range<succ_iterator> successors()
  {
    return llvm::make_range(succ_begin(), succ_end());
  }
 
  const_succ_iterator succ_begin() const;
  const_succ_iterator succ_end() const;
  inline llvm::iterator_range<const_succ_iterator> successors() const
  {
    return llvm::make_range(succ_begin(), succ_end());
  }
 
  inline unsigned succ_size() const
  {
    return std::distance(succ_begin(), succ_end());
  }
 
  inline bool succ_empty() const { return succ_begin() == succ_end(); }
 
  // Iterator over the predecessors.
  inline bool pred_empty() const { return pred_begin() == pred_end(); }
  inline unsigned pred_size() const
  {
    return std::distance(pred_begin(), pred_end());
  }
  pred_iterator pred_begin() { return pred_iterator(user_begin()); }
  pred_iterator pred_end() { return pred_iterator(user_end()); }
  const_pred_iterator pred_begin() const { return const_pred_iterator(user_begin()); }
  const_pred_iterator pred_end() const { return const_pred_iterator(user_end()); }
  inline llvm::iterator_range<pred_iterator> predecessors()
  {
    return llvm::make_range(pred_begin(), pred_end());
  }
  inline llvm::iterator_range<const_pred_iterator> predecessors() const
  {
    return llvm::make_range(pred_begin(), pred_end());
  }
 
  // Checks whether the block lacks phi nodes.
  bool phi_empty() const { return !begin()->Is(Inst::Kind::PHI); }
  // Iterator over PHI nodes.
  llvm::iterator_range<const_phi_iterator> phis() const {
    return const_cast<Block *>(this)->phis();
  }
  llvm::iterator_range<phi_iterator> phis();
 
  iterator first_non_phi();
 
  Block *splitBlock(iterator I);
 
  // LLVM: Debug printing.
  void printAsOperand(llvm::raw_ostream &O, bool PrintType = true) const;
 
  Prog *getProg() override;
 
  void dump(llvm::raw_ostream &os = llvm::errs()) const;
 
private:
  friend struct llvm::ilist_traits<Inst>;
  friend struct SymbolTableListTraits<Block>;
  void setParent(Func *parent) { parent_ = parent; }
 
private:
  Func *parent_;
  InstListType insts_;
};
 
inline llvm::raw_ostream &operator<<(llvm::raw_ostream &os, const Block &block)
{
  block.dump(os);
  return os;
}