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 loops_.push(loop);
43
44 int64_t budget = maxInsns_;
45 for (uint32_t level = 0; !loops_.empty() && level < maxLevel_ && budget > 0; ++level) {
46 auto levelSize = loops_.size();
47 while (levelSize-- != 0) {
48 auto origLoop = loops_.front();
49 loops_.pop();
50
51 if (LoopUnswitcher::IsSmallLoop(origLoop)) {
52 COMPILER_LOG(DEBUG, LOOP_UNSWITCH)
53 << "Level #" << level << ": estimated loop iterations < 2, skip loop " << loop->GetId();
54 continue;
55 }
56 auto unswitchInst = LoopUnswitcher::FindUnswitchInst(origLoop);
57 if (unswitchInst == nullptr) {
58 COMPILER_LOG(DEBUG, LOOP_UNSWITCH)
59 << "Level #" << level << ": cannot find unswitch instruction, skip loop " << loop->GetId();
60 continue;
61 }
62
63 int64_t loopSize = 0;
64 int64_t trueCount = 0;
65 int64_t falseCount = 0;
66 LoopUnswitcher::EstimateInstructionsCount(loop, unswitchInst, &loopSize, &trueCount, &falseCount);
67 if (trueCount + falseCount >= budget + loopSize) {
68 break;
69 }
70
71 auto loopUnswitcher =
72 LoopUnswitcher(GetGraph(), GetGraph()->GetAllocator(), GetGraph()->GetLocalAllocator());
73 auto newLoop = loopUnswitcher.UnswitchLoop(origLoop, unswitchInst);
74 if (newLoop == nullptr) {
75 continue;
76 }
77
78 if (trueCount + falseCount > loopSize) {
79 budget -= trueCount + falseCount - loopSize;
80 }
81
82 COMPILER_LOG(DEBUG, LOOP_UNSWITCH)
83 << "Level #" << level << ": unswitch loop " << origLoop->GetId() << ", new loop " << newLoop->GetId();
84
85 loops_.push(origLoop);
86 loops_.push(newLoop);
87
88 isApplied_ = true;
89 }
90 }
91 return true;
92 }
93 } // namespace ark::compiler
94