polly/Support/VirtualInstruction.h

//===------ VirtualInstruction.cpp ------------------------------*- 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
//
//===----------------------------------------------------------------------===//
//
// Tools for determining which instructions are within a statement and the
// nature of their operands.
//
//===----------------------------------------------------------------------===//

#ifndef POLLY_SUPPORT_VIRTUALINSTRUCTION_H
#define POLLY_SUPPORT_VIRTUALINSTRUCTION_H

#include "polly/ScopInfo.h"

namespace polly {
using llvm::User;

/// Determine the nature of a value's use within a statement.
///
/// These are not always representable by llvm::Use. For instance, scalar write
/// MemoryAccesses do use a value, but are not associated with an instruction's
/// argument.
///
/// Despite its name it is not tied to virtual instructions (although it works
/// fine with them), but to promote consistent handling of values used in
/// statements.
class VirtualUse {
public:
  /// The different types of uses. Handling usually differentiates a lot between
  /// these; one can use a switch to handle each case (and get warned by the
  /// compiler if one is not handled).
  enum UseKind {
    // An llvm::Constant.
    Constant,

    // An llvm::BasicBlock.
    Block,

    // A value that can be generated using ScopExpander.
    Synthesizable,

    // A load that always reads the same value throughout the SCoP (address and
    // the value located there a SCoP-invariant) and has been hoisted in front
    // of the SCoP.
    Hoisted,

    // Definition before the SCoP and not synthesizable. Can be an instruction
    // outside the SCoP, a function argument or a global value. Whether there is
    // a scalar MemoryAccess in this statement for reading it depends on the
    // -polly-analyze-read-only-scalars switch.
    ReadOnly,

    // A definition within the same statement. No MemoryAccess between
    // definition and use are necessary.
    Intra,

    // Definition in another statement. There is a scalar MemoryAccess that
    // makes it available in this statement.
    Inter
  };

private:
  /// The statement where a value is used.
  ScopStmt *User;

  /// The value that is used.
  Value *Val;

  /// The type of value use.
  UseKind Kind;

  /// The value represented as llvm::SCEV expression.
  const SCEV *ScevExpr;

  /// If this is an inter-statement (or read-only) use, contains the
  /// MemoryAccess that makes the value available in this statement. In case of
  /// intra-statement uses, can contain a MemoryKind::Array access. In all other
  /// cases, it is a nullptr.
  MemoryAccess *InputMA;

  VirtualUse(ScopStmt *User, Value *Val, UseKind Kind, const SCEV *ScevExpr,
             MemoryAccess *InputMA)
      : User(User), Val(Val), Kind(Kind), ScevExpr(ScevExpr), InputMA(InputMA) {
  }

public:
  /// Get a VirtualUse for an llvm::Use.
  ///
  /// @param S       The Scop object.
  /// @param U       The llvm::Use the get information for.
  /// @param LI      The LoopInfo analysis. Needed to determine whether the
  ///                value is synthesizable.
  /// @param Virtual Whether to ignore existing MemoryAcccess.
  ///
  /// @return The VirtualUse representing the same use as @p U.
  static VirtualUse create(Scop *S, const Use &U, LoopInfo *LI, bool Virtual);

  /// Get a VirtualUse for uses within statements.
  ///
  /// It is assumed that the user is not a PHINode. Such uses are always
  /// VirtualUse::Inter unless in a regions statement.
  ///
  /// @param S         The Scop object.
  /// @param UserStmt  The statement in which @p Val is used. Can be nullptr, in
  ///                  which case it assumed that the statement has been
  ///                  removed, which is only possible if no instruction in it
  ///                  had side-effects or computes a value used by another
  ///                  statement.
  /// @param UserScope Loop scope in which the value is used. Needed to
  ///                  determine whether the value is synthesizable.
  /// @param Val       The value being used.
  /// @param Virtual   Whether to use (and prioritize over instruction location)
  ///                  information about MemoryAccesses.
  ///
  /// @return A VirtualUse object that gives information about @p Val's use in
  ///         @p UserStmt.
  static VirtualUse create(Scop *S, ScopStmt *UserStmt, Loop *UserScope,
                           Value *Val, bool Virtual);

  static VirtualUse create(ScopStmt *UserStmt, Loop *UserScope, Value *Val,
                           bool Virtual) {
    return create(UserStmt->getParent(), UserStmt, UserScope, Val, Virtual);
  }

  bool isConstant() const { return Kind == Constant; }
  bool isBlock() const { return Kind == Block; }
  bool isSynthesizable() const { return Kind == Synthesizable; }
  bool isHoisted() const { return Kind == Hoisted; }
  bool isReadOnly() const { return Kind == ReadOnly; }
  bool isIntra() const { return Kind == Intra; }
  bool isInter() const { return Kind == Inter; }

  /// Return user statement.
  ScopStmt *getUser() const { return User; }

  /// Return the used value.
  llvm::Value *getValue() const { return Val; }

  /// Return the type of use.
  UseKind getKind() const { return Kind; }

  /// Return the ScalarEvolution representation of @p Val.
  const SCEV *getScevExpr() const { return ScevExpr; }

  /// Return the MemoryAccess that makes the value available in this statement,
  /// if any.
  MemoryAccess *getMemoryAccess() const { return InputMA; }

  /// Print a description of this object.
  ///
  /// @param OS           Stream to print to.
  /// @param Reproducible If true, ensures that the output is stable between
  ///                     runs and is suitable to check in regression tests.
  ///                     This excludes printing e.g. pointer values. If false,
  ///                     the output should not be used for regression tests,
  ///                     but may contain more information useful in debugger
  ///                     sessions.
  void print(raw_ostream &OS, bool Reproducible = true) const;

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  void dump() const;
#endif
};

/// An iterator for virtual operands.
class VirtualOperandIterator {
  friend class VirtualInstruction;
  friend class VirtualUse;

  using Self = VirtualOperandIterator;

  ScopStmt *User;
  User::op_iterator U;

  VirtualOperandIterator(ScopStmt *User, User::op_iterator U)
      : User(User), U(U) {}

public:
  using iterator_category = std::forward_iterator_tag;
  using value_type = VirtualUse;
  using difference_type = std::ptrdiff_t;
  using pointer = value_type *;
  using reference = value_type &;

  inline bool operator==(const Self &that) const {
    assert(this->User == that.User);
    return this->U == that.U;
  }

  inline bool operator!=(const Self &that) const {
    assert(this->User == that.User);
    return this->U != that.U;
  }

  VirtualUse operator*() const {
    return VirtualUse::create(User, User->getSurroundingLoop(), U->get(), true);
  }

  Use *operator->() const { return U; }

  Self &operator++() {
    U++;
    return *this;
  }

  Self operator++(int) {
    Self tmp = *this;
    ++*this;
    return tmp;
  }
};

/// This class represents a "virtual instruction", an instruction in a ScopStmt,
/// effectively a ScopStmt/Instruction-pair.
///
/// An instructions can be moved between statements (e.g. to avoid a scalar
/// dependency) and even can be contained in multiple statements (for instance,
/// to recompute a value instead of transferring it), hence 'virtual'. This
/// class is required to represent such instructions that are not in their
/// 'physical' location anymore.
///
/// A statement can currently not contain the same instructions multiple times
/// (that is, from different loop iterations). Therefore, a
/// ScopStmt/Instruction-pair uniquely identifies a virtual instructions.
/// ScopStmt::getInstruction() can contain the same instruction multiple times,
/// but they necessarily compute the same value.
class VirtualInstruction {
  friend class VirtualOperandIterator;
  friend struct llvm::DenseMapInfo<VirtualInstruction>;

private:
  /// The statement this virtual instruction is in.
  ScopStmt *Stmt = nullptr;

  /// The instruction of a statement.
  Instruction *Inst = nullptr;

public:
  VirtualInstruction() {}

  /// Create a new virtual instruction of an instruction @p Inst in @p Stmt.
  VirtualInstruction(ScopStmt *Stmt, Instruction *Inst)
      : Stmt(Stmt), Inst(Inst) {
    assert(Stmt && Inst);
  }

  VirtualOperandIterator operand_begin() const {
    return VirtualOperandIterator(Stmt, Inst->op_begin());
  }

  VirtualOperandIterator operand_end() const {
    return VirtualOperandIterator(Stmt, Inst->op_end());
  }

  /// Returns a list of virtual operands.
  ///
  /// Virtual operands, like virtual instructions, need to encode the ScopStmt
  /// they are in.
  llvm::iterator_range<VirtualOperandIterator> operands() const {
    return {operand_begin(), operand_end()};
  }

  /// Return the SCoP everything is contained in.
  Scop *getScop() const { return Stmt->getParent(); }

  /// Return the ScopStmt this virtual instruction is in.
  ScopStmt *getStmt() const { return Stmt; }

  /// Return the instruction in the statement.
  Instruction *getInstruction() const { return Inst; }

  /// Print a description of this object.
  ///
  /// @param OS           Stream to print to.
  /// @param Reproducible If true, ensures that the output is stable between
  ///                     runs and is suitable for checks in regression tests.
  ///                     This excludes printing e.g., pointer values. If false,
  ///                     the output should not be used for regression tests,
  ///                     but may contain more information useful in debugger
  ///                     sessions.
  void print(raw_ostream &OS, bool Reproducible = true) const;

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  void dump() const;
#endif
};

static inline bool operator==(VirtualInstruction LHS, VirtualInstruction RHS) {
  return LHS.getStmt() == RHS.getStmt() &&
         LHS.getInstruction() == RHS.getInstruction();
}

/// Find all reachable instructions and accesses.
///
/// @param S              The SCoP to find everything reachable in.
/// @param LI             LoopInfo required for analysis.
/// @param UsedInsts[out] Receives all reachable instructions.
/// @param UsedAccs[out]  Receives all reachable accesses.
/// @param OnlyLocal      If non-nullptr, activates local mode: The SCoP is
///                       assumed to consist only of this statement and is
///                       conservatively correct. Does not require walking the
///                       whole SCoP.
void markReachable(Scop *S, LoopInfo *LI,
                   DenseSet<VirtualInstruction> &UsedInsts,
                   DenseSet<MemoryAccess *> &UsedAccs,
                   ScopStmt *OnlyLocal = nullptr);
} // namespace polly

namespace llvm {
/// Support VirtualInstructions in llvm::DenseMaps.
template <> struct DenseMapInfo<polly::VirtualInstruction> {
public:
  static bool isEqual(polly::VirtualInstruction LHS,
                      polly::VirtualInstruction RHS) {
    return DenseMapInfo<polly::ScopStmt *>::isEqual(LHS.getStmt(),
                                                    RHS.getStmt()) &&
           DenseMapInfo<Instruction *>::isEqual(LHS.getInstruction(),
                                                RHS.getInstruction());
  }

  static polly::VirtualInstruction getTombstoneKey() {
    polly::VirtualInstruction TombstoneKey;
    TombstoneKey.Stmt = DenseMapInfo<polly::ScopStmt *>::getTombstoneKey();
    TombstoneKey.Inst = DenseMapInfo<Instruction *>::getTombstoneKey();
    return TombstoneKey;
  }

  static polly::VirtualInstruction getEmptyKey() {
    polly::VirtualInstruction EmptyKey;
    EmptyKey.Stmt = DenseMapInfo<polly::ScopStmt *>::getEmptyKey();
    EmptyKey.Inst = DenseMapInfo<Instruction *>::getEmptyKey();
    return EmptyKey;
  }

  static unsigned getHashValue(polly::VirtualInstruction Val) {
    return DenseMapInfo<std::pair<polly::ScopStmt *, Instruction *>>::
        getHashValue(std::make_pair(Val.getStmt(), Val.getInstruction()));
  }
};
} // namespace llvm

#endif /* POLLY_SUPPORT_VIRTUALINSTRUCTION_H */