1 //===- VPlanValue.h - Represent Values in Vectorizer Plan -----------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// This file contains the declarations of the entities induced by Vectorization
11 /// Plans, e.g. the instructions the VPlan intends to generate if executed.
12 /// VPlan models the following entities:
13 /// VPValue
14 ///  |-- VPUser
15 ///  |    |-- VPInstruction
16 /// These are documented in docs/VectorizationPlan.rst.
17 ///
18 //===----------------------------------------------------------------------===//
19 
20 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
21 #define LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
22 
23 #include "llvm/ADT/DenseMap.h"
24 #include "llvm/ADT/SmallVector.h"
25 #include "llvm/IR/Value.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/raw_ostream.h"
28 
29 namespace llvm {
30 
31 // Forward declarations.
32 class VPUser;
33 
34 // This is the base class of the VPlan Def/Use graph, used for modeling the data
35 // flow into, within and out of the VPlan. VPValues can stand for live-ins
36 // coming from the input IR, instructions which VPlan will generate if executed
37 // and live-outs which the VPlan will need to fix accordingly.
38 class VPValue {
39   friend class VPBuilder;
40   friend class VPlanTransforms;
41   friend class VPBasicBlock;
42   friend class VPInterleavedAccessInfo;
43 
44 private:
45   const unsigned char SubclassID; ///< Subclass identifier (for isa/dyn_cast).
46 
47   SmallVector<VPUser *, 1> Users;
48 
49 protected:
50   // Hold the underlying Value, if any, attached to this VPValue.
51   Value *UnderlyingVal;
52 
53   VPValue(const unsigned char SC, Value *UV = nullptr)
54       : SubclassID(SC), UnderlyingVal(UV) {}
55 
56   // DESIGN PRINCIPLE: Access to the underlying IR must be strictly limited to
57   // the front-end and back-end of VPlan so that the middle-end is as
58   // independent as possible of the underlying IR. We grant access to the
59   // underlying IR using friendship. In that way, we should be able to use VPlan
60   // for multiple underlying IRs (Polly?) by providing a new VPlan front-end,
61   // back-end and analysis information for the new IR.
62 
63   /// Return the underlying Value attached to this VPValue.
64   Value *getUnderlyingValue() { return UnderlyingVal; }
65 
66   // Set \p Val as the underlying Value of this VPValue.
67   void setUnderlyingValue(Value *Val) {
68     assert(!UnderlyingVal && "Underlying Value is already set.");
69     UnderlyingVal = Val;
70   }
71 
72 public:
73   /// An enumeration for keeping track of the concrete subclass of VPValue that
74   /// are actually instantiated. Values of this enumeration are kept in the
75   /// SubclassID field of the VPValue objects. They are used for concrete
76   /// type identification.
77   enum { VPValueSC, VPUserSC, VPInstructionSC };
78 
79   VPValue(Value *UV = nullptr) : VPValue(VPValueSC, UV) {}
80   VPValue(const VPValue &) = delete;
81   VPValue &operator=(const VPValue &) = delete;
82 
83   /// \return an ID for the concrete type of this object.
84   /// This is used to implement the classof checks. This should not be used
85   /// for any other purpose, as the values may change as LLVM evolves.
86   unsigned getVPValueID() const { return SubclassID; }
87 
88   void printAsOperand(raw_ostream &OS) const {
89     OS << "%vp" << (unsigned short)(unsigned long long)this;
90   }
91 
92   unsigned getNumUsers() const { return Users.size(); }
93   void addUser(VPUser &User) { Users.push_back(&User); }
94 
95   typedef SmallVectorImpl<VPUser *>::iterator user_iterator;
96   typedef SmallVectorImpl<VPUser *>::const_iterator const_user_iterator;
97   typedef iterator_range<user_iterator> user_range;
98   typedef iterator_range<const_user_iterator> const_user_range;
99 
100   user_iterator user_begin() { return Users.begin(); }
101   const_user_iterator user_begin() const { return Users.begin(); }
102   user_iterator user_end() { return Users.end(); }
103   const_user_iterator user_end() const { return Users.end(); }
104   user_range users() { return user_range(user_begin(), user_end()); }
105   const_user_range users() const {
106     return const_user_range(user_begin(), user_end());
107   }
108 
109   /// Returns true if the value has more than one unique user.
110   bool hasMoreThanOneUniqueUser() {
111     if (getNumUsers() == 0)
112       return false;
113 
114     // Check if all users match the first user.
115     auto Current = std::next(user_begin());
116     while (Current != user_end() && *user_begin() == *Current)
117       Current++;
118     return Current != user_end();
119   }
120 
121   void replaceAllUsesWith(VPValue *New);
122 };
123 
124 typedef DenseMap<Value *, VPValue *> Value2VPValueTy;
125 typedef DenseMap<VPValue *, Value *> VPValue2ValueTy;
126 
127 raw_ostream &operator<<(raw_ostream &OS, const VPValue &V);
128 
129 /// This class augments VPValue with operands which provide the inverse def-use
130 /// edges from VPValue's users to their defs.
131 class VPUser : public VPValue {
132 private:
133   SmallVector<VPValue *, 2> Operands;
134 
135 protected:
136   VPUser(const unsigned char SC) : VPValue(SC) {}
137   VPUser(const unsigned char SC, ArrayRef<VPValue *> Operands) : VPValue(SC) {
138     for (VPValue *Operand : Operands)
139       addOperand(Operand);
140   }
141 
142 public:
143   VPUser() : VPValue(VPValue::VPUserSC) {}
144   VPUser(ArrayRef<VPValue *> Operands) : VPUser(VPValue::VPUserSC, Operands) {}
145   VPUser(std::initializer_list<VPValue *> Operands)
146       : VPUser(ArrayRef<VPValue *>(Operands)) {}
147   VPUser(const VPUser &) = delete;
148   VPUser &operator=(const VPUser &) = delete;
149 
150   /// Method to support type inquiry through isa, cast, and dyn_cast.
151   static inline bool classof(const VPValue *V) {
152     return V->getVPValueID() >= VPUserSC &&
153            V->getVPValueID() <= VPInstructionSC;
154   }
155 
156   void addOperand(VPValue *Operand) {
157     Operands.push_back(Operand);
158     Operand->addUser(*this);
159   }
160 
161   unsigned getNumOperands() const { return Operands.size(); }
162   inline VPValue *getOperand(unsigned N) const {
163     assert(N < Operands.size() && "Operand index out of bounds");
164     return Operands[N];
165   }
166 
167   void setOperand(unsigned I, VPValue *New) { Operands[I] = New; }
168 
169   typedef SmallVectorImpl<VPValue *>::iterator operand_iterator;
170   typedef SmallVectorImpl<VPValue *>::const_iterator const_operand_iterator;
171   typedef iterator_range<operand_iterator> operand_range;
172   typedef iterator_range<const_operand_iterator> const_operand_range;
173 
174   operand_iterator op_begin() { return Operands.begin(); }
175   const_operand_iterator op_begin() const { return Operands.begin(); }
176   operand_iterator op_end() { return Operands.end(); }
177   const_operand_iterator op_end() const { return Operands.end(); }
178   operand_range operands() { return operand_range(op_begin(), op_end()); }
179   const_operand_range operands() const {
180     return const_operand_range(op_begin(), op_end());
181   }
182 };
183 
184 } // namespace llvm
185 
186 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_VALUE_H
187