1 /*
2 * Copyright (c) 2023-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 #include "compiler_logger.h"
16 #include "optimizer/analysis/alias_analysis.h"
17 #include "optimizer/analysis/bounds_analysis.h"
18 #include "optimizer/analysis/dominators_tree.h"
19 #include "optimizer/ir/graph.h"
20 #include "optimizer/ir/loop_unswitcher.h"
21 #include "loop_unswitch.h"
22
23 namespace ark::compiler {
RunImpl()24 bool LoopUnswitch::RunImpl()
25 {
26 COMPILER_LOG(DEBUG, LOOP_TRANSFORM) << "Run " << GetPassName();
27 RunLoopsVisitor();
28 COMPILER_LOG(DEBUG, LOOP_TRANSFORM) << GetPassName() << " complete";
29 return isApplied_;
30 }
31
InvalidateAnalyses()32 void LoopUnswitch::InvalidateAnalyses()
33 {
34 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
35 GetGraph()->InvalidateAnalysis<AliasAnalysis>();
36 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
37 InvalidateBlocksOrderAnalyzes(GetGraph());
38 }
39
TransformLoop(Loop * loop)40 bool LoopUnswitch::TransformLoop(Loop *loop)
41 {
42 if (!loop->GetInnerLoops().empty()) {
43 COMPILER_LOG(DEBUG, LOOP_TRANSFORM)
44 << "Loop wasn't unswitched since it contains loops. Loop id = " << loop->GetId();
45 return false;
46 }
47 loops_.push(loop);
48
49 int64_t budget = maxInsns_;
50 for (uint32_t level = 0; !loops_.empty() && level < maxLevel_ && budget > 0; ++level) {
51 auto levelSize = loops_.size();
52 while (levelSize-- != 0) {
53 auto origLoop = loops_.front();
54 loops_.pop();
55
56 if (LoopUnswitcher::IsSmallLoop(origLoop)) {
57 COMPILER_LOG(DEBUG, LOOP_UNSWITCH)
58 << "Level #" << level << ": estimated loop iterations < 2, skip loop " << loop->GetId();
59 continue;
60 }
61 auto unswitchInst = LoopUnswitcher::FindUnswitchInst(origLoop);
62 if (unswitchInst == nullptr) {
63 COMPILER_LOG(DEBUG, LOOP_UNSWITCH)
64 << "Level #" << level << ": cannot find unswitch instruction, skip loop " << loop->GetId();
65 continue;
66 }
67
68 int64_t loopSize = 0;
69 int64_t trueCount = 0;
70 int64_t falseCount = 0;
71 LoopUnswitcher::EstimateInstructionsCount(loop, unswitchInst, &loopSize, &trueCount, &falseCount);
72 if (trueCount + falseCount >= budget + loopSize) {
73 break;
74 }
75
76 auto loopUnswitcher =
77 LoopUnswitcher(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator());
78 auto newLoop = loopUnswitcher.UnswitchLoop(origLoop, unswitchInst);
79 if (newLoop == nullptr) {
80 continue;
81 }
82
83 if (trueCount + falseCount > loopSize) {
84 budget -= trueCount + falseCount - loopSize;
85 }
86
87 COMPILER_LOG(DEBUG, LOOP_UNSWITCH)
88 << "Level #" << level << ": unswitch loop " << origLoop->GetId() << ", new loop " << newLoop->GetId();
89
90 loops_.push(origLoop);
91 loops_.push(newLoop);
92
93 isApplied_ = true;
94 }
95 }
96 return true;
97 }
98 } // namespace ark::compiler
99