//===------ 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 final {
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 MemoryAccess.
///
/// @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 final {
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 final {
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 */