• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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