1 // Copyright (c) 2018 Google LLC. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef SOURCE_OPT_SCALAR_ANALYSIS_H_ 16 #define SOURCE_OPT_SCALAR_ANALYSIS_H_ 17 18 #include <algorithm> 19 #include <cstdint> 20 #include <map> 21 #include <memory> 22 #include <unordered_set> 23 #include <utility> 24 #include <vector> 25 26 #include "source/opt/basic_block.h" 27 #include "source/opt/instruction.h" 28 #include "source/opt/scalar_analysis_nodes.h" 29 30 namespace spvtools { 31 namespace opt { 32 33 class IRContext; 34 class Loop; 35 36 // Manager for the Scalar Evolution analysis. Creates and maintains a DAG of 37 // scalar operations generated from analysing the use def graph from incoming 38 // instructions. Each node is hashed as it is added so like node (for instance, 39 // two induction variables i=0,i++ and j=0,j++) become the same node. After 40 // creating a DAG with AnalyzeInstruction it can the be simplified into a more 41 // usable form with SimplifyExpression. 42 class ScalarEvolutionAnalysis { 43 public: 44 explicit ScalarEvolutionAnalysis(IRContext* context); 45 46 // Create a unary negative node on |operand|. 47 SENode* CreateNegation(SENode* operand); 48 49 // Creates a subtraction between the two operands by adding |operand_1| to the 50 // negation of |operand_2|. 51 SENode* CreateSubtraction(SENode* operand_1, SENode* operand_2); 52 53 // Create an addition node between two operands. The |simplify| when set will 54 // allow the function to return an SEConstant instead of an addition if the 55 // two input operands are also constant. 56 SENode* CreateAddNode(SENode* operand_1, SENode* operand_2); 57 58 // Create a multiply node between two operands. 59 SENode* CreateMultiplyNode(SENode* operand_1, SENode* operand_2); 60 61 // Create a node representing a constant integer. 62 SENode* CreateConstant(int64_t integer); 63 64 // Create a value unknown node, such as a load. 65 SENode* CreateValueUnknownNode(const Instruction* inst); 66 67 // Create a CantComputeNode. Used to exit out of analysis. 68 SENode* CreateCantComputeNode(); 69 70 // Create a new recurrent node with |offset| and |coefficient|, with respect 71 // to |loop|. 72 SENode* CreateRecurrentExpression(const Loop* loop, SENode* offset, 73 SENode* coefficient); 74 75 // Construct the DAG by traversing use def chain of |inst|. 76 SENode* AnalyzeInstruction(const Instruction* inst); 77 78 // Simplify the |node| by grouping like terms or if contains a recurrent 79 // expression, rewrite the graph so the whole DAG (from |node| down) is in 80 // terms of that recurrent expression. 81 // 82 // For example. 83 // Induction variable i=0, i++ would produce Rec(0,1) so i+1 could be 84 // transformed into Rec(1,1). 85 // 86 // X+X*2+Y-Y+34-17 would be transformed into 3*X + 17, where X and Y are 87 // ValueUnknown nodes (such as a load instruction). 88 SENode* SimplifyExpression(SENode* node); 89 90 // Add |prospective_node| into the cache and return a raw pointer to it. If 91 // |prospective_node| is already in the cache just return the raw pointer. 92 SENode* GetCachedOrAdd(std::unique_ptr<SENode> prospective_node); 93 94 // Checks that the graph starting from |node| is invariant to the |loop|. 95 bool IsLoopInvariant(const Loop* loop, const SENode* node) const; 96 97 // Sets |is_gt_zero| to true if |node| represent a value always strictly 98 // greater than 0. The result of |is_gt_zero| is valid only if the function 99 // returns true. 100 bool IsAlwaysGreaterThanZero(SENode* node, bool* is_gt_zero) const; 101 102 // Sets |is_ge_zero| to true if |node| represent a value greater or equals to 103 // 0. The result of |is_ge_zero| is valid only if the function returns true. 104 bool IsAlwaysGreaterOrEqualToZero(SENode* node, bool* is_ge_zero) const; 105 106 // Find the recurrent term belonging to |loop| in the graph starting from 107 // |node| and return the coefficient of that recurrent term. Constant zero 108 // will be returned if no recurrent could be found. |node| should be in 109 // simplest form. 110 SENode* GetCoefficientFromRecurrentTerm(SENode* node, const Loop* loop); 111 112 // Return a rebuilt graph starting from |node| with the recurrent expression 113 // belonging to |loop| being zeroed out. Returned node will be simplified. 114 SENode* BuildGraphWithoutRecurrentTerm(SENode* node, const Loop* loop); 115 116 // Return the recurrent term belonging to |loop| if it appears in the graph 117 // starting at |node| or null if it doesn't. 118 SERecurrentNode* GetRecurrentTerm(SENode* node, const Loop* loop); 119 120 SENode* UpdateChildNode(SENode* parent, SENode* child, SENode* new_child); 121 122 // The loops in |loop_pair| will be considered the same when constructing 123 // SERecurrentNode objects. This enables analysing dependencies that will be 124 // created during loop fusion. AddLoopsToPretendAreTheSame(const std::pair<const Loop *,const Loop * > & loop_pair)125 void AddLoopsToPretendAreTheSame( 126 const std::pair<const Loop*, const Loop*>& loop_pair) { 127 pretend_equal_[std::get<1>(loop_pair)] = std::get<0>(loop_pair); 128 } 129 130 private: 131 SENode* AnalyzeConstant(const Instruction* inst); 132 133 // Handles both addition and subtraction. If the |instruction| is OpISub 134 // then the resulting node will be op1+(-op2) otherwise if it is OpIAdd then 135 // the result will be op1+op2. |instruction| must be OpIAdd or OpISub. 136 SENode* AnalyzeAddOp(const Instruction* instruction); 137 138 SENode* AnalyzeMultiplyOp(const Instruction* multiply); 139 140 SENode* AnalyzePhiInstruction(const Instruction* phi); 141 142 IRContext* context_; 143 144 // A map of instructions to SENodes. This is used to track recurrent 145 // expressions as they are added when analyzing instructions. Recurrent 146 // expressions come from phi nodes which by nature can include recursion so we 147 // check if nodes have already been built when analyzing instructions. 148 std::map<const Instruction*, SENode*> recurrent_node_map_; 149 150 // On creation we create and cache the CantCompute node so we not need to 151 // perform a needless create step. 152 SENode* cached_cant_compute_; 153 154 // Helper functor to allow two unique_ptr to nodes to be compare. Only 155 // needed 156 // for the unordered_set implementation. 157 struct NodePointersEquality { operatorNodePointersEquality158 bool operator()(const std::unique_ptr<SENode>& lhs, 159 const std::unique_ptr<SENode>& rhs) const { 160 return *lhs == *rhs; 161 } 162 }; 163 164 // Cache of nodes. All pointers to the nodes are references to the memory 165 // managed by they set. 166 std::unordered_set<std::unique_ptr<SENode>, SENodeHash, NodePointersEquality> 167 node_cache_; 168 169 // Loops that should be considered the same for performing analysis for loop 170 // fusion. 171 std::map<const Loop*, const Loop*> pretend_equal_; 172 }; 173 174 // Wrapping class to manipulate SENode pointer using + - * / operators. 175 class SExpression { 176 public: 177 // Implicit on purpose ! SExpression(SENode * node)178 SExpression(SENode* node) 179 : node_(node->GetParentAnalysis()->SimplifyExpression(node)), 180 scev_(node->GetParentAnalysis()) {} 181 182 inline operator SENode*() const { return node_; } 183 inline SENode* operator->() const { return node_; } 184 const SENode& operator*() const { return *node_; } 185 GetScalarEvolutionAnalysis()186 inline ScalarEvolutionAnalysis* GetScalarEvolutionAnalysis() const { 187 return scev_; 188 } 189 190 inline SExpression operator+(SENode* rhs) const; 191 template <typename T, 192 typename std::enable_if<std::is_integral<T>::value, int>::type = 0> 193 inline SExpression operator+(T integer) const; 194 inline SExpression operator+(SExpression rhs) const; 195 196 inline SExpression operator-() const; 197 inline SExpression operator-(SENode* rhs) const; 198 template <typename T, 199 typename std::enable_if<std::is_integral<T>::value, int>::type = 0> 200 inline SExpression operator-(T integer) const; 201 inline SExpression operator-(SExpression rhs) const; 202 203 inline SExpression operator*(SENode* rhs) const; 204 template <typename T, 205 typename std::enable_if<std::is_integral<T>::value, int>::type = 0> 206 inline SExpression operator*(T integer) const; 207 inline SExpression operator*(SExpression rhs) const; 208 209 template <typename T, 210 typename std::enable_if<std::is_integral<T>::value, int>::type = 0> 211 inline std::pair<SExpression, int64_t> operator/(T integer) const; 212 // Try to perform a division. Returns the pair <this.node_ / rhs, division 213 // remainder>. If it fails to simplify it, the function returns a 214 // CanNotCompute node. 215 std::pair<SExpression, int64_t> operator/(SExpression rhs) const; 216 217 private: 218 SENode* node_; 219 ScalarEvolutionAnalysis* scev_; 220 }; 221 222 inline SExpression SExpression::operator+(SENode* rhs) const { 223 return scev_->CreateAddNode(node_, rhs); 224 } 225 226 template <typename T, 227 typename std::enable_if<std::is_integral<T>::value, int>::type> 228 inline SExpression SExpression::operator+(T integer) const { 229 return *this + scev_->CreateConstant(integer); 230 } 231 232 inline SExpression SExpression::operator+(SExpression rhs) const { 233 return *this + rhs.node_; 234 } 235 236 inline SExpression SExpression::operator-() const { 237 return scev_->CreateNegation(node_); 238 } 239 240 inline SExpression SExpression::operator-(SENode* rhs) const { 241 return *this + scev_->CreateNegation(rhs); 242 } 243 244 template <typename T, 245 typename std::enable_if<std::is_integral<T>::value, int>::type> 246 inline SExpression SExpression::operator-(T integer) const { 247 return *this - scev_->CreateConstant(integer); 248 } 249 250 inline SExpression SExpression::operator-(SExpression rhs) const { 251 return *this - rhs.node_; 252 } 253 254 inline SExpression SExpression::operator*(SENode* rhs) const { 255 return scev_->CreateMultiplyNode(node_, rhs); 256 } 257 258 template <typename T, 259 typename std::enable_if<std::is_integral<T>::value, int>::type> 260 inline SExpression SExpression::operator*(T integer) const { 261 return *this * scev_->CreateConstant(integer); 262 } 263 264 inline SExpression SExpression::operator*(SExpression rhs) const { 265 return *this * rhs.node_; 266 } 267 268 template <typename T, 269 typename std::enable_if<std::is_integral<T>::value, int>::type> 270 inline std::pair<SExpression, int64_t> SExpression::operator/(T integer) const { 271 return *this / scev_->CreateConstant(integer); 272 } 273 274 template <typename T, 275 typename std::enable_if<std::is_integral<T>::value, int>::type> 276 inline SExpression operator+(T lhs, SExpression rhs) { 277 return rhs + lhs; 278 } 279 inline SExpression operator+(SENode* lhs, SExpression rhs) { return rhs + lhs; } 280 281 template <typename T, 282 typename std::enable_if<std::is_integral<T>::value, int>::type> 283 inline SExpression operator-(T lhs, SExpression rhs) { 284 // NOLINTNEXTLINE(whitespace/braces) 285 return SExpression{rhs.GetScalarEvolutionAnalysis()->CreateConstant(lhs)} - 286 rhs; 287 } 288 inline SExpression operator-(SENode* lhs, SExpression rhs) { 289 // NOLINTNEXTLINE(whitespace/braces) 290 return SExpression{lhs} - rhs; 291 } 292 293 template <typename T, 294 typename std::enable_if<std::is_integral<T>::value, int>::type> 295 inline SExpression operator*(T lhs, SExpression rhs) { 296 return rhs * lhs; 297 } 298 inline SExpression operator*(SENode* lhs, SExpression rhs) { return rhs * lhs; } 299 300 template <typename T, 301 typename std::enable_if<std::is_integral<T>::value, int>::type> 302 inline std::pair<SExpression, int64_t> operator/(T lhs, SExpression rhs) { 303 // NOLINTNEXTLINE(whitespace/braces) 304 return SExpression{rhs.GetScalarEvolutionAnalysis()->CreateConstant(lhs)} / 305 rhs; 306 } 307 inline std::pair<SExpression, int64_t> operator/(SENode* lhs, SExpression rhs) { 308 // NOLINTNEXTLINE(whitespace/braces) 309 return SExpression{lhs} / rhs; 310 } 311 312 } // namespace opt 313 } // namespace spvtools 314 #endif // SOURCE_OPT_SCALAR_ANALYSIS_H_ 315