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 "if_conversion.h"
18
19 #include "optimizer/ir/basicblock.h"
20 #include "optimizer/analysis/alias_analysis.h"
21 #include "optimizer/analysis/bounds_analysis.h"
22 #include "optimizer/analysis/loop_analyzer.h"
23
24 namespace ark::compiler {
RunImpl()25 bool IfConversion::RunImpl()
26 {
27 COMPILER_LOG(DEBUG, IFCONVERSION) << "Run " << GetPassName();
28 bool result = false;
29 // Post order (without reverse)
30 for (auto it = GetGraph()->GetBlocksRPO().rbegin(); it != GetGraph()->GetBlocksRPO().rend(); it++) {
31 auto block = *it;
32 if (block->GetSuccsBlocks().size() == MAX_SUCCS_NUM) {
33 result |= TryTriangle(block) || TryDiamond(block);
34 }
35 }
36 COMPILER_LOG(DEBUG, IFCONVERSION) << GetPassName() << " complete";
37 return result;
38 }
39
40 /*
41 The methods handles the recognition of the following pattern that have two variations:
42 BB -- basic block the recognition starts from
43 TBB -- TrueSuccessor of BB
44 FBB -- FalseSuccessor of BB
45
46 P0 P1
47 [BB] [BB]
48 | \ | \
49 | [TBB] | [FBB]
50 | / | /
51 [FBB] [TBB]
52 */
TryTriangle(BasicBlock * bb)53 bool IfConversion::TryTriangle(BasicBlock *bb)
54 {
55 ASSERT(bb->GetSuccsBlocks().size() == MAX_SUCCS_NUM);
56 BasicBlock *tbb;
57 BasicBlock *fbb;
58 bool swapped = false;
59 // interpret P1 variation as P0
60 if (bb->GetTrueSuccessor()->GetPredsBlocks().size() == 1) {
61 tbb = bb->GetTrueSuccessor();
62 fbb = bb->GetFalseSuccessor();
63 } else if (bb->GetFalseSuccessor()->GetPredsBlocks().size() == 1) {
64 tbb = bb->GetFalseSuccessor();
65 fbb = bb->GetTrueSuccessor();
66 swapped = true;
67 } else {
68 return false;
69 }
70
71 if (tbb->GetSuccsBlocks().size() > 1 || fbb->GetPredsBlocks().size() <= 1 || tbb->GetSuccessor(0) != fbb) {
72 return false;
73 }
74
75 if (LoopInvariantPreventConversion(bb)) {
76 return false;
77 }
78
79 uint32_t instCount = 0;
80 uint32_t phiCount = 0;
81 auto limit = GetIfcLimit(bb);
82 if (IsConvertable(tbb, &instCount) && IsPhisAllowed(fbb, tbb, bb, &phiCount)) {
83 COMPILER_LOG(DEBUG, IFCONVERSION)
84 << "Triangle pattern was found in Block #" << bb->GetId() << " with " << instCount
85 << " convertible instruction(s) and " << phiCount << " Phi(s) to process";
86 if (instCount <= limit && phiCount <= limit) {
87 // Joining tbb into bb
88 bb->JoinBlocksUsingSelect(tbb, nullptr, swapped);
89
90 if (fbb->GetPredsBlocks().size() == 1 && bb->IsTry() == fbb->IsTry()) {
91 bb->JoinSuccessorBlock(); // join fbb
92 COMPILER_LOG(DEBUG, IFCONVERSION) << "Merged blocks " << tbb->GetId() << " and " << fbb->GetId()
93 << " into " << bb->GetId() << " using Select";
94 GetGraph()->GetEventWriter().EventIfConversion(bb->GetId(), bb->GetGuestPc(), "Triangle", tbb->GetId(),
95 fbb->GetId(), -1);
96 } else {
97 COMPILER_LOG(DEBUG, IFCONVERSION)
98 << "Merged block " << tbb->GetId() << " into " << bb->GetId() << " using Select";
99 GetGraph()->GetEventWriter().EventIfConversion(bb->GetId(), bb->GetGuestPc(), "Triangle_Phi",
100 tbb->GetId(), -1, -1);
101 }
102 return true;
103 }
104 }
105
106 return false;
107 }
108
GetIfcLimit(BasicBlock * bb)109 uint32_t IfConversion::GetIfcLimit(BasicBlock *bb)
110 {
111 ASSERT(bb->GetSuccsBlocks().size() == MAX_SUCCS_NUM);
112 auto trueCounter = GetGraph()->GetBranchCounter(bb, true);
113 auto falseCounter = GetGraph()->GetBranchCounter(bb, false);
114 if (trueCounter == 0 && falseCounter == 0) {
115 return limit_;
116 }
117 auto minCounter = std::min(trueCounter, falseCounter);
118 // NOLINTNEXTLINE(readability-magic-numbers)
119 auto percent = (minCounter * 100) / (trueCounter + falseCounter);
120 if (percent < g_options.GetCompilerIfConversionIncraseLimitThreshold()) {
121 return limit_;
122 }
123 // The limit is increased by 4 times for branch with a large number of mispredicts
124 return limit_ << 2U;
125 }
126
127 /*
128 The methods handles the recognition of the following pattern:
129 BB -- basic block the recognition starts from
130 TBB -- TrueSuccessor of BB
131 FBB -- FalseSuccessor of BB
132 JBB -- Joint basic block of branches
133
134 [BB]
135 / \
136 [TBB] [FBB]
137 \ /
138 [JBB]
139 */
TryDiamond(BasicBlock * bb)140 bool IfConversion::TryDiamond(BasicBlock *bb)
141 {
142 ASSERT(bb->GetSuccsBlocks().size() == MAX_SUCCS_NUM);
143 BasicBlock *tbb = bb->GetTrueSuccessor();
144 if (tbb->GetPredsBlocks().size() != 1 || tbb->GetSuccsBlocks().size() != 1) {
145 return false;
146 }
147
148 BasicBlock *fbb = bb->GetFalseSuccessor();
149 if (fbb->GetPredsBlocks().size() != 1 || fbb->GetSuccsBlocks().size() != 1) {
150 return false;
151 }
152
153 BasicBlock *jbb = tbb->GetSuccessor(0);
154 if (jbb->GetPredsBlocks().size() <= 1 || fbb->GetSuccessor(0) != jbb) {
155 return false;
156 }
157
158 if (LoopInvariantPreventConversion(bb)) {
159 return false;
160 }
161
162 uint32_t tbbInst = 0;
163 uint32_t fbbInst = 0;
164 uint32_t phiCount = 0;
165 auto limit = GetIfcLimit(bb);
166 if (IsConvertable(tbb, &tbbInst) && IsConvertable(fbb, &fbbInst) && IsPhisAllowed(jbb, tbb, fbb, &phiCount)) {
167 COMPILER_LOG(DEBUG, IFCONVERSION)
168 << "Diamond pattern was found in Block #" << bb->GetId() << " with " << (tbbInst + fbbInst)
169 << " convertible instruction(s) and " << phiCount << " Phi(s) to process";
170 if (tbbInst + fbbInst <= limit && phiCount <= limit) {
171 // Joining tbb into bb
172 bb->JoinBlocksUsingSelect(tbb, fbb, false);
173
174 bb->JoinSuccessorBlock(); // joining fbb
175
176 if (jbb->GetPredsBlocks().size() == 1 && bb->IsTry() == jbb->IsTry()) {
177 bb->JoinSuccessorBlock(); // joining jbb
178 COMPILER_LOG(DEBUG, IFCONVERSION) << "Merged blocks " << tbb->GetId() << ", " << fbb->GetId() << " and "
179 << jbb->GetId() << " into " << bb->GetId() << " using Select";
180 GetGraph()->GetEventWriter().EventIfConversion(bb->GetId(), bb->GetGuestPc(), "Diamond", tbb->GetId(),
181 fbb->GetId(), jbb->GetId());
182 } else {
183 COMPILER_LOG(DEBUG, IFCONVERSION) << "Merged blocks " << tbb->GetId() << " and " << fbb->GetId()
184 << " into " << bb->GetId() << " using Select";
185 GetGraph()->GetEventWriter().EventIfConversion(bb->GetId(), bb->GetGuestPc(), "Diamond_Phi",
186 tbb->GetId(), fbb->GetId(), -1);
187 }
188 return true;
189 }
190 }
191 return false;
192 }
193
LoopInvariantPreventConversion(BasicBlock * bb)194 bool IfConversion::LoopInvariantPreventConversion(BasicBlock *bb)
195 {
196 if (!g_options.IsCompilerLicmConditions()) {
197 // Need to investigate may be it is always better to avoid IfConv for loop invariant condition
198 return false;
199 }
200 if (!bb->IsLoopValid()) {
201 return false;
202 }
203 auto loop = bb->GetLoop();
204 if (loop->IsRoot()) {
205 return false;
206 }
207 auto lastInst = bb->GetLastInst();
208 for (auto &input : lastInst->GetInputs()) {
209 if (input.GetInst()->GetBasicBlock()->GetLoop() == loop) {
210 return false;
211 }
212 }
213 return true;
214 }
215
IsConvertable(BasicBlock * bb,uint32_t * instCount)216 bool IfConversion::IsConvertable(BasicBlock *bb, uint32_t *instCount)
217 {
218 uint32_t total = 0;
219 for (auto inst : bb->AllInsts()) {
220 ASSERT(inst->GetOpcode() != Opcode::Phi);
221 if (!inst->IsIfConvertable()) {
222 return false;
223 }
224 total += static_cast<uint32_t>(inst->HasUsers());
225 }
226 *instCount = total;
227 return true;
228 }
229
IsPhisAllowed(BasicBlock * bb,BasicBlock * pred1,BasicBlock * pred2,uint32_t * phiCount)230 bool IfConversion::IsPhisAllowed(BasicBlock *bb, BasicBlock *pred1, BasicBlock *pred2, uint32_t *phiCount)
231 {
232 uint32_t total = 0;
233
234 for (auto phi : bb->PhiInsts()) {
235 size_t index1 = phi->CastToPhi()->GetPredBlockIndex(pred1);
236 size_t index2 = phi->CastToPhi()->GetPredBlockIndex(pred2);
237 ASSERT(index1 != index2);
238
239 auto inst1 = phi->GetInput(index1).GetInst();
240 auto inst2 = phi->GetInput(index2).GetInst();
241 if (inst1 == inst2) {
242 // Otherwise DCE should remove Phi
243 [[maybe_unused]] constexpr auto IMM_2 = 2;
244 ASSERT(bb->GetPredsBlocks().size() > IMM_2);
245 // No select needed
246 continue;
247 }
248
249 // Select can be supported for float operands on the specific architectures (arm64 now)
250 if (DataType::IsFloatType(phi->GetType()) && !canEncodeFloatSelect_) {
251 return false;
252 }
253
254 // NOTE: LICM conditions pass moves condition chain invariants outside the loop
255 // and consider branch probability. IfConversion can replaces it with SelectInst
256 // but their If inst users lose branch probability information. This code prevents
257 // such conversion until IfConversion can estimate branch probability.
258 if (IsConditionChainPhi(phi)) {
259 return false;
260 }
261
262 // One more Select
263 total++;
264 }
265 *phiCount = total;
266 return true;
267 }
268
IsConditionChainPhi(Inst * phi)269 bool IfConversion::IsConditionChainPhi(Inst *phi)
270 {
271 if (!g_options.IsCompilerLicmConditions()) {
272 return false;
273 }
274
275 auto loop = phi->GetBasicBlock()->GetLoop();
276 for (auto &user : phi->GetUsers()) {
277 auto userBb = user.GetInst()->GetBasicBlock();
278 if (!userBb->GetLoop()->IsInside(loop)) {
279 return false;
280 }
281 }
282 return true;
283 }
284
InvalidateAnalyses()285 void IfConversion::InvalidateAnalyses()
286 {
287 GetGraph()->InvalidateAnalysis<AliasAnalysis>();
288 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
289 }
290 } // namespace ark::compiler
291