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