EIC code displayed by LXR master/​include/​polly/​Support/​VirtualInstruction.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:48:20

 //===------ 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 */

This page was automatically generated by the 2.3.7 LXR engine. The LXR team