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_LOOP_FUSION_H_ 16 #define SOURCE_OPT_LOOP_FUSION_H_ 17 18 #include <map> 19 #include <set> 20 #include <utility> 21 #include <vector> 22 23 #include "source/opt/ir_context.h" 24 #include "source/opt/loop_descriptor.h" 25 #include "source/opt/loop_utils.h" 26 #include "source/opt/scalar_analysis.h" 27 28 namespace spvtools { 29 namespace opt { 30 31 class LoopFusion { 32 public: LoopFusion(IRContext * context,Loop * loop_0,Loop * loop_1)33 LoopFusion(IRContext* context, Loop* loop_0, Loop* loop_1) 34 : context_(context), 35 loop_0_(loop_0), 36 loop_1_(loop_1), 37 containing_function_(loop_0->GetHeaderBlock()->GetParent()) {} 38 39 // Checks if the |loop_0| and |loop_1| are compatible for fusion. 40 // That means: 41 // * they both have one induction variable 42 // * they have the same upper and lower bounds 43 // - same inital value 44 // - same condition 45 // * they have the same update step 46 // * they are adjacent, with |loop_0| appearing before |loop_1| 47 // * there are no break/continue in either of them 48 // * they both have pre-header blocks (required for ScalarEvolutionAnalysis 49 // and dependence checking). 50 bool AreCompatible(); 51 52 // Checks if compatible |loop_0| and |loop_1| are legal to fuse. 53 // * fused loops do not have any dependencies with dependence distance greater 54 // than 0 that did not exist in the original loops. 55 // * there are no function calls in the loops (could have side-effects) 56 bool IsLegal(); 57 58 // Perform the actual fusion of |loop_0_| and |loop_1_|. The loops have to be 59 // compatible and the fusion has to be legal. 60 void Fuse(); 61 62 private: 63 // Check that the initial values are the same. 64 bool CheckInit(); 65 66 // Check that the conditions are the same. 67 bool CheckCondition(); 68 69 // Check that the steps are the same. 70 bool CheckStep(); 71 72 // Returns |true| if |instruction| is used in the continue or condition block 73 // of |loop|. 74 bool UsedInContinueOrConditionBlock(Instruction* instruction, Loop* loop); 75 76 // Remove entries in |instructions| that are not used in the continue or 77 // condition block of |loop|. 78 void RemoveIfNotUsedContinueOrConditionBlock( 79 std::vector<Instruction*>* instructions, Loop* loop); 80 81 // Returns |true| if |instruction| is used in |loop|. 82 bool IsUsedInLoop(Instruction* instruction, Loop* loop); 83 84 // Returns |true| if |loop| has at least one barrier or function call. 85 bool ContainsBarriersOrFunctionCalls(Loop* loop); 86 87 // Get all instructions in the |loop| (except in the latch block) that have 88 // the opcode |opcode|. 89 std::pair<std::vector<Instruction*>, std::vector<Instruction*>> 90 GetLoadsAndStoresInLoop(Loop* loop); 91 92 // Given a vector of memory operations (OpLoad/OpStore), constructs a map from 93 // variables to the loads/stores that those variables. 94 std::map<Instruction*, std::vector<Instruction*>> LocationToMemOps( 95 const std::vector<Instruction*>& mem_ops); 96 97 IRContext* context_; 98 99 // The original loops to be fused. 100 Loop* loop_0_; 101 Loop* loop_1_; 102 103 // The function that contains |loop_0_| and |loop_1_|. 104 Function* containing_function_ = nullptr; 105 106 // The induction variables for |loop_0_| and |loop_1_|. 107 Instruction* induction_0_ = nullptr; 108 Instruction* induction_1_ = nullptr; 109 }; 110 111 } // namespace opt 112 } // namespace spvtools 113 114 #endif // SOURCE_OPT_LOOP_FUSION_H_ 115