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 "optimizer/analysis/countable_loop_parser.h"
17 #include "optimizer/analysis/bounds_analysis.h"
18 #include "optimizer/analysis/loop_analyzer.h"
19 #include "optimizer/ir/basicblock.h"
20 #include "optimizer/ir/graph.h"
21
22 namespace ark::compiler {
23 /**
24 * Check if loop is countable
25 *
26 * [Loop]
27 * Phi(init, update)
28 * ...
29 * update(phi, 1)
30 * Compare(Add/Sub, test)
31 *
32 * where `update` is Add or Sub instruction
33 */
Parse()34 std::optional<CountableLoopInfo> CountableLoopParser::Parse()
35 {
36 if (loop_.IsIrreducible() || loop_.IsOsrLoop() || loop_.IsTryCatchLoop() || loop_.GetBackEdges().size() != 1 ||
37 loop_.IsRoot() || loop_.IsInfinite()) {
38 return std::nullopt;
39 }
40
41 if (!ParseLoopExit()) {
42 return std::nullopt;
43 }
44
45 if (!SetUpdateAndTestInputs()) {
46 return std::nullopt;
47 }
48
49 if (!IsInstIncOrDec(loopInfo_.update)) {
50 return std::nullopt;
51 }
52 SetIndexAndConstStep();
53 if (loopInfo_.index->GetBasicBlock() != loop_.GetHeader()) {
54 return std::nullopt;
55 }
56
57 if (!TryProcessBackEdge()) {
58 return std::nullopt;
59 }
60 return loopInfo_;
61 }
62
ParseLoopExit()63 bool CountableLoopParser::ParseLoopExit()
64 {
65 auto loopExit = FindLoopExitBlock();
66 if (loopExit->IsEmpty() || (loopExit != loop_.GetHeader() && loopExit != loop_.GetBackEdges()[0])) {
67 return false;
68 }
69 isHeadLoopExit_ = (loopExit == loop_.GetHeader() && loopExit != loop_.GetBackEdges()[0]);
70 loopInfo_.ifImm = loopExit->GetLastInst();
71 if (loopInfo_.ifImm->GetOpcode() != Opcode::IfImm && loopInfo_.ifImm->GetOpcode() != Opcode::If) {
72 return false;
73 }
74 auto loopExitCmp = loopInfo_.ifImm->GetInput(0).GetInst();
75 if (loopExitCmp->GetOpcode() != Opcode::Compare) {
76 return false;
77 }
78 if (isHeadLoopExit_ && !loopExitCmp->GetInput(0).GetInst()->IsPhi() &&
79 !loopExitCmp->GetInput(1).GetInst()->IsPhi()) {
80 return false;
81 }
82 auto cmpType = loopExitCmp->CastToCompare()->GetOperandsType();
83 return DataType::GetCommonType(cmpType) == DataType::INT64;
84 }
85
TryProcessBackEdge()86 bool CountableLoopParser::TryProcessBackEdge()
87 {
88 ASSERT(loopInfo_.index->IsPhi());
89 auto backEdge {loop_.GetBackEdges()[0]};
90 auto backEdgeIdx {loopInfo_.index->CastToPhi()->GetPredBlockIndex(backEdge)};
91 if (loopInfo_.index->GetInput(backEdgeIdx).GetInst() != loopInfo_.update) {
92 return false;
93 }
94 ASSERT(loopInfo_.index->GetInputsCount() == MAX_SUCCS_NUM);
95 loopInfo_.init = loopInfo_.index->GetInput(1 - backEdgeIdx).GetInst();
96 SetNormalizedConditionCode();
97 return IsConditionCodeAcceptable();
98 }
99
HasPreHeaderCompare(Loop * loop,const CountableLoopInfo & loopInfo)100 bool CountableLoopParser::HasPreHeaderCompare(Loop *loop, const CountableLoopInfo &loopInfo)
101 {
102 auto preHeader = loop->GetPreHeader();
103 auto backEdge = loop->GetBackEdges()[0];
104 if (loopInfo.ifImm->GetBasicBlock() != backEdge || preHeader->IsEmpty() ||
105 preHeader->GetLastInst()->GetOpcode() != Opcode::IfImm) {
106 return false;
107 }
108 auto preHeaderIfImm = preHeader->GetLastInst();
109 ASSERT(preHeaderIfImm->GetOpcode() == Opcode::IfImm);
110 auto preHeaderCmp = preHeaderIfImm->GetInput(0).GetInst();
111 if (preHeaderCmp->GetOpcode() != Opcode::Compare) {
112 return false;
113 }
114 auto backEdgeCmp = loopInfo.ifImm->GetInput(0).GetInst();
115 ASSERT(backEdgeCmp->GetOpcode() == Opcode::Compare);
116
117 // Compare condition codes
118 if (preHeaderCmp->CastToCompare()->GetCc() != backEdgeCmp->CastToCompare()->GetCc()) {
119 return false;
120 }
121
122 if (loopInfo.ifImm->CastToIfImm()->GetCc() != preHeaderIfImm->CastToIfImm()->GetCc() ||
123 loopInfo.ifImm->CastToIfImm()->GetImm() != preHeaderIfImm->CastToIfImm()->GetImm()) {
124 return false;
125 }
126
127 // Compare control-flow
128 if (preHeader->GetTrueSuccessor() != backEdge->GetTrueSuccessor() ||
129 preHeader->GetFalseSuccessor() != backEdge->GetFalseSuccessor()) {
130 return false;
131 }
132
133 // Compare test inputs
134 auto testInputIdx = 1;
135 if (backEdgeCmp->GetInput(0) == loopInfo.test) {
136 testInputIdx = 0;
137 } else {
138 ASSERT(backEdgeCmp->GetInput(1) == loopInfo.test);
139 }
140
141 return preHeaderCmp->GetInput(testInputIdx).GetInst() == loopInfo.test &&
142 preHeaderCmp->GetInput(1 - testInputIdx).GetInst() == loopInfo.init;
143 }
144
145 // Returns exact number of iterations for loop with constant boundaries
146 // if its index does not overflow
GetLoopIterations(const CountableLoopInfo & loopInfo)147 std::optional<uint64_t> CountableLoopParser::GetLoopIterations(const CountableLoopInfo &loopInfo)
148 {
149 if (!loopInfo.init->IsConst() || !loopInfo.test->IsConst() || loopInfo.constStep == 0) {
150 return std::nullopt;
151 }
152 uint64_t initValue = loopInfo.init->CastToConstant()->GetInt64Value();
153 uint64_t testValue = loopInfo.test->CastToConstant()->GetInt64Value();
154 auto type = loopInfo.index->GetType();
155
156 if (loopInfo.isInc) {
157 int64_t maxTest = BoundsRange::GetMax(type) - static_cast<int64_t>(loopInfo.constStep);
158 if (loopInfo.normalizedCc == CC_LE) {
159 maxTest--;
160 }
161 if (static_cast<int64_t>(testValue) > maxTest) {
162 // index may overflow
163 return std::nullopt;
164 }
165 } else {
166 int64_t minTest = BoundsRange::GetMin(type) + static_cast<int64_t>(loopInfo.constStep);
167 if (loopInfo.normalizedCc == CC_GE) {
168 minTest++;
169 }
170 if (static_cast<int64_t>(testValue) < minTest) {
171 // index may overflow
172 return std::nullopt;
173 }
174 std::swap(initValue, testValue);
175 }
176 if (static_cast<int64_t>(initValue) > static_cast<int64_t>(testValue)) {
177 return 0;
178 }
179 uint64_t diff = testValue - initValue;
180 uint64_t count = diff + loopInfo.constStep;
181 if (diff > std::numeric_limits<uint64_t>::max() - loopInfo.constStep) {
182 // count may overflow
183 return std::nullopt;
184 }
185 if (loopInfo.normalizedCc == CC_LT || loopInfo.normalizedCc == CC_GT) {
186 count--;
187 }
188 return count / loopInfo.constStep;
189 }
190
191 /*
192 * Check if instruction is Add or Sub with constant and phi inputs
193 */
IsInstIncOrDec(Inst * inst)194 bool CountableLoopParser::IsInstIncOrDec(Inst *inst)
195 {
196 if (!inst->IsAddSub()) {
197 return false;
198 }
199 ConstantInst *cnst = nullptr;
200 if (inst->GetInput(0).GetInst()->IsConst() && inst->GetInput(1).GetInst()->IsPhi()) {
201 cnst = inst->GetInput(0).GetInst()->CastToConstant();
202 } else if (inst->GetInput(1).GetInst()->IsConst() && inst->GetInput(0).GetInst()->IsPhi()) {
203 cnst = inst->GetInput(1).GetInst()->CastToConstant();
204 }
205 return cnst != nullptr;
206 }
207
208 // NOTE(a.popov) Suppot 'GetLoopExit()' method in the 'Loop' class
FindLoopExitBlock()209 BasicBlock *CountableLoopParser::FindLoopExitBlock()
210 {
211 auto outerLoop = loop_.GetOuterLoop();
212 for (auto block : loop_.GetBlocks()) {
213 const auto &succs = block->GetSuccsBlocks();
214 auto it = std::find_if(succs.begin(), succs.end(),
215 [&outerLoop](const BasicBlock *bb) { return bb->GetLoop() == outerLoop; });
216 if (it != succs.end()) {
217 return block;
218 }
219 }
220 UNREACHABLE();
221 return nullptr;
222 }
223
SetUpdateAndTestInputs()224 bool CountableLoopParser::SetUpdateAndTestInputs()
225 {
226 auto loopExitCmp = loopInfo_.ifImm->GetInput(0).GetInst();
227 ASSERT(loopExitCmp->GetOpcode() == Opcode::Compare);
228 loopInfo_.update = loopExitCmp->GetInput(0).GetInst();
229 loopInfo_.test = loopExitCmp->GetInput(1).GetInst();
230 if (isHeadLoopExit_) {
231 if (!loopInfo_.update->IsPhi()) {
232 std::swap(loopInfo_.update, loopInfo_.test);
233 }
234 ASSERT(loopInfo_.update->IsPhi());
235 if (loopInfo_.update->GetBasicBlock() != loop_.GetHeader()) {
236 return false;
237 }
238 auto backEdge {loop_.GetBackEdges()[0]};
239 loopInfo_.update = loopInfo_.update->CastToPhi()->GetPhiInput(backEdge);
240 } else {
241 if (!IsInstIncOrDec(loopInfo_.update)) {
242 std::swap(loopInfo_.update, loopInfo_.test);
243 }
244 }
245
246 return true;
247 }
248
SetIndexAndConstStep()249 void CountableLoopParser::SetIndexAndConstStep()
250 {
251 loopInfo_.index = loopInfo_.update->GetInput(0).GetInst();
252 auto constInst = loopInfo_.update->GetInput(1).GetInst();
253 if (loopInfo_.index->IsConst()) {
254 loopInfo_.index = loopInfo_.update->GetInput(1).GetInst();
255 constInst = loopInfo_.update->GetInput(0).GetInst();
256 }
257
258 ASSERT(constInst->GetType() == DataType::INT64);
259 auto cnst = constInst->CastToConstant()->GetIntValue();
260 const uint64_t mask = (1ULL << 63U);
261 auto isNeg = DataType::IsTypeSigned(loopInfo_.update->GetType()) && (cnst & mask) != 0;
262 loopInfo_.isInc = loopInfo_.update->IsAdd();
263 if (isNeg) {
264 cnst = ~cnst + 1;
265 loopInfo_.isInc = !loopInfo_.isInc;
266 }
267 loopInfo_.constStep = cnst;
268 }
269
SetNormalizedConditionCode()270 void CountableLoopParser::SetNormalizedConditionCode()
271 {
272 auto loopExit = loopInfo_.ifImm->GetBasicBlock();
273 ASSERT(loopExit != nullptr);
274 auto loopExitCmp = loopInfo_.ifImm->GetInput(0).GetInst();
275 ASSERT(loopExitCmp->GetOpcode() == Opcode::Compare);
276 auto cc = loopExitCmp->CastToCompare()->GetCc();
277 if (loopInfo_.test == loopExitCmp->GetInput(0).GetInst()) {
278 cc = SwapOperandsConditionCode(cc);
279 }
280 ASSERT(loopInfo_.ifImm->CastToIfImm()->GetImm() == 0);
281 if (loopInfo_.ifImm->CastToIfImm()->GetCc() == CC_EQ) {
282 cc = GetInverseConditionCode(cc);
283 } else {
284 ASSERT(loopInfo_.ifImm->CastToIfImm()->GetCc() == CC_NE);
285 }
286 auto loop = loopExit->GetLoop();
287 if (loopExit->GetFalseSuccessor()->GetLoop() == loop ||
288 loopExit->GetFalseSuccessor()->GetLoop()->GetOuterLoop() == loop) {
289 cc = GetInverseConditionCode(cc);
290 } else {
291 ASSERT(loopExit->GetTrueSuccessor()->GetLoop() == loop ||
292 loopExit->GetTrueSuccessor()->GetLoop()->GetOuterLoop() == loop);
293 }
294 loopInfo_.normalizedCc = cc;
295 }
296
IsConditionCodeAcceptable()297 bool CountableLoopParser::IsConditionCodeAcceptable()
298 {
299 auto cc = loopInfo_.normalizedCc;
300 // Condition should be: inc <= test | inc < test
301 if (loopInfo_.isInc && cc != CC_LE && cc != CC_LT) {
302 return false;
303 }
304 // Condition should be: dec >= test | dec > test
305 if (!loopInfo_.isInc && cc != CC_GE && cc != CC_GT) {
306 return false;
307 }
308 return true;
309 }
310 } // namespace ark::compiler
311