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
28namespace spvtools {
29namespace opt {
30
31class LoopFusion {
32 public:
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