1 /*
2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd.
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
16 #include "compiler_logger.h"
17 #include "optimizer/ir/basicblock.h"
18 #include "optimizer/ir/inst.h"
19 #include "optimizer/analysis/alias_analysis.h"
20 #include "optimizer/analysis/bounds_analysis.h"
21 #include "optimizer/analysis/dominators_tree.h"
22 #include "optimizer/analysis/rpo.h"
23 #include "optimizer/analysis/loop_analyzer.h"
24 #include "optimizer/optimizations/code_sink.h"
25
26 namespace ark::compiler {
27 /**
28 * Code sinking optimization attempts to sink operations that is needed only in
29 * a particular execution path but are performed on paths that do not need
30 * them.
31 *
32 * [BB 0] ---------\
33 * | v3 = v1 + v2 \
34 * | \
35 * [BB 1] [BB 2]
36 * return v1 return v3
37 *
38 * Transforms into
39 *
40 * [BB 0] ------\
41 * | \
42 * [BB 1] [BB 2]
43 * return v1 v3 = v1 + v2
44 * return v3
45 *
46 * Generally we can move only instructions with no side-effects.
47 * We can't move:
48 * - Allocations
49 * - Control flow instructions
50 * - Instructions that can throw an exception
51 * - Function calls (they may have side effects and/or throw exceptions as well)
52 * - Monitors
53 * - Store instructions
54 *
55 * We do not move:
56 * - Loads that may be aliased by following stores in a basic block
57 * - Loads if there is any presence of monitors in a function
58 * - Instructions into inner loops
59 */
RunImpl()60 bool CodeSink::RunImpl()
61 {
62 isApplied_ = false;
63 GetGraph()->RunPass<LoopAnalyzer>();
64 // Iteratively sink instructions. On each iteration an instruction can be
65 // sunk to it's basic block dominatee. Iterate sinking until no changes
66 // happens.
67 bool changed = true;
68 for (int i = 0; changed; ++i) {
69 changed = false;
70 COMPILER_LOG(DEBUG, CODE_SINK) << "Sinking iteration " << i;
71 for (auto block : GetGraph()->GetBlocksRPO()) {
72 changed |= ProcessBlock(block);
73 }
74 isApplied_ |= changed;
75 }
76
77 COMPILER_LOG(DEBUG, CODE_SINK) << "Code Sink complete";
78 return isApplied_;
79 }
80
InvalidateAnalyses()81 void CodeSink::InvalidateAnalyses()
82 {
83 if (isApplied_) {
84 // Bounds analysis works with instructions in a particular basic block
85 // reordering breaks it
86 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
87 }
88 }
89
90 /**
91 * Iterate instructions in reverse order to decrease the number of iterations.
92 * If instruction can be sunk, it is erased from it's basic block and inserted
93 * into appropriate successor.
94 */
ProcessBlock(BasicBlock * block)95 bool CodeSink::ProcessBlock(BasicBlock *block)
96 {
97 if (block->IsStartBlock() || block->IsEndBlock()) {
98 return false;
99 }
100 bool madeChange = false;
101 bool memBarrier = false;
102 InstVector stores(GetGraph()->GetLocalAllocator()->Adapter());
103 for (auto inst : block->InstsSafeReverse()) {
104 if (inst->IsCatchPhi() || !inst->HasUsers()) {
105 continue;
106 }
107 if (inst->GetOpcode() == Opcode::Monitor || (inst->IsStore() && IsVolatileMemInst(inst)) ||
108 inst->GetFlag(compiler::inst_flags::HEAP_INV)) {
109 // Ensures that we do not move in or out monitored section
110 // Also ensures we do not sink over volatile store
111 memBarrier = true;
112 continue;
113 }
114 BasicBlock *candidate = SinkInstruction(inst, &stores, memBarrier);
115 if (candidate != nullptr) {
116 COMPILER_LOG(DEBUG, CODE_SINK) << "Sunk v" << inst->GetId() << " to BB " << candidate->GetId();
117 GetGraph()->GetEventWriter().EventCodeSink(inst->GetId(), inst->GetPc(), block->GetId(),
118 candidate->GetId());
119 block->EraseInst(inst, true);
120 // Insertion in the beginning of the block guaranties we do not
121 // enter or exit monitor in candidate block
122 candidate->PrependInst(inst);
123 madeChange = true;
124 }
125 }
126 return madeChange;
127 }
128
InstHasRefInput(Inst * inst)129 static bool InstHasRefInput(Inst *inst)
130 {
131 for (size_t i = 0; i < inst->GetInputsCount(); ++i) {
132 if (!DataType::IsTypeNumeric(inst->GetInputType(i))) {
133 return true;
134 }
135 }
136 return false;
137 }
138
139 /**
140 * Check that an instruction can be sunk. Then check that dominated blocks are acceptable for sinking.
141 * Finally, return the candidate.
142 */
SinkInstruction(Inst * inst,InstVector * stores,bool barriered)143 BasicBlock *CodeSink::SinkInstruction(Inst *inst, InstVector *stores, bool barriered)
144 {
145 ASSERT(inst->GetOpcode() != Opcode::Phi && inst->GetOpcode() != Opcode::CatchPhi);
146 // Save stores to be sure we do not sink a load instruction that may be
147 // overwritten by later store instruction
148 if (inst->IsStore()) {
149 stores->push_back(inst);
150 return nullptr;
151 }
152 // Check that instruction can be sunk
153 // Volatile memory operations are barriers
154 // We can't move instruction with REFERENCE input throw SaveState(GC can moved or delete the object)
155 // For Bytecode Optimizer, it is not allowed to mix LoadStatic and class initialization (for another LoadStatic),
156 // so LoadStatic cannot be sunk
157 if (inst->IsAllocation() || inst->IsControlFlow() || inst->CanThrow() || inst->IsBarrier() || inst->IsSaveState() ||
158 (!GetGraph()->IsBytecodeOptimizer() && InstHasRefInput(inst)) ||
159 (GetGraph()->IsBytecodeOptimizer() && (inst->GetOpcode() == Opcode::LoadStatic))) {
160 return nullptr;
161 }
162 if (inst->IsLoad()) {
163 // Do not sink over monitors or volatile stores
164 if (barriered) {
165 return nullptr;
166 }
167 for (auto store : *stores) {
168 if (GetGraph()->CheckInstAlias(inst, store) != AliasType::NO_ALIAS) {
169 return nullptr;
170 }
171 }
172 }
173
174 BasicBlock *block = inst->GetBasicBlock();
175 auto dominated = block->GetDominatedBlocks();
176 for (auto cand : dominated) {
177 if (IsAcceptableTarget(inst, cand)) {
178 return cand;
179 }
180 }
181
182 return nullptr;
183 }
184
185 /// Check that candidate dominates all users of inst.
IsAcceptableTarget(Inst * inst,BasicBlock * candidate)186 bool CodeSink::IsAcceptableTarget(Inst *inst, BasicBlock *candidate)
187 {
188 ASSERT(inst != nullptr);
189 ASSERT(candidate != nullptr);
190 ASSERT(inst->GetBasicBlock() != candidate);
191 ASSERT(inst->GetBasicBlock()->IsDominate(candidate));
192
193 if (candidate->IsEndBlock() || candidate->IsTryBegin() || candidate->IsTryEnd()) {
194 return false;
195 }
196
197 Loop *candLoop = candidate->GetLoop();
198 // Do not sink into irreducible loops
199 if (candLoop->IsIrreducible()) {
200 return false;
201 }
202
203 BasicBlock *block = inst->GetBasicBlock();
204 Loop *loop = block->GetLoop();
205 if (candidate->GetPredsBlocks().size() > 1) {
206 // Do not sink loads across a critical edge there may be stores in
207 // other code paths.
208 if (inst->IsLoad()) {
209 return false;
210 }
211 if (loop != candLoop) {
212 return false;
213 }
214 }
215 ASSERT_PRINT(loop == candLoop || loop->IsInside(candLoop), "Can sink only into outer loop");
216
217 // Check that all uses are dominated by the candidate
218 for (auto &user : inst->GetUsers()) {
219 Inst *uinst = user.GetInst();
220 auto ublock = uinst->GetBasicBlock();
221 // We can't insert instruction before Phi, therefore do not sink into blocks where one of users is a Phi
222 if (!candidate->IsDominate(ublock) || (uinst->IsPhi() && ublock == candidate)) {
223 return false;
224 }
225 }
226 return true;
227 }
228 } // namespace ark::compiler
229