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 #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/basicblock.h"
20 #include "optimizer/ir/graph.h"
21 #include "optimizer/ir/graph_cloner.h"
22 #include "optimizer/optimizations/loop_peeling.h"
23
24 namespace ark::compiler {
25 /**
26 * Loop-peeling optimization works with a loops with the following requirements:
27 * - loop is not irreducible;
28 * - there is only 1 back-edge;
29 * - loop-header is a single loop-exit point;
30 *
31 * [pre-header]
32 * |
33 * v
34 * /---->[header]--------\
35 * | | |
36 * | v v
37 * \----[back-edge] [outer]
38 *
39 * There are two stages of the algorithm
40 * 1 stage - insert pre-loop which is an if-block:
41 *
42 * [pre-header]
43 * |
44 * v
45 * [pre-loop]--------\
46 * | |
47 * v v
48 * /---->[header]-------->|
49 * | | |
50 * | v v
51 * \----[back-edge] [resolver]
52 * |
53 * v
54 * [outer]
55 *
56 * 2 stage - move exit-edge form the header to the back-edge block:
57 *
58 * [pre-header]
59 * |
60 * v
61 * [pre-loop]--------\
62 * | |
63 * v v
64 * /---->[header] |
65 * | | |
66 * | v v
67 * \----[back-edge]-->[resolver]
68 * |
69 * v
70 * [outer]
71 *
72 */
RunImpl()73 bool LoopPeeling::RunImpl()
74 {
75 COMPILER_LOG(DEBUG, LOOP_TRANSFORM) << "Run " << GetPassName();
76 RunLoopsVisitor();
77 COMPILER_LOG(DEBUG, LOOP_TRANSFORM) << GetPassName() << " complete";
78 return isAppied_;
79 }
80
InvalidateAnalyses()81 void LoopPeeling::InvalidateAnalyses()
82 {
83 GetGraph()->InvalidateAnalysis<BoundsAnalysis>();
84 GetGraph()->InvalidateAnalysis<AliasAnalysis>();
85 GetGraph()->InvalidateAnalysis<LoopAnalyzer>();
86 }
87
CleanDeadPhis(BasicBlock * block)88 static inline void CleanDeadPhis(BasicBlock *block)
89 {
90 for (auto phi : block->PhiInstsSafe()) {
91 if (!phi->HasUsers()) {
92 block->RemoveInst(phi);
93 }
94 }
95 }
96
HeaderHasInlinedCalls(const BasicBlock * header)97 static bool HeaderHasInlinedCalls(const BasicBlock *header)
98 {
99 auto checkInlinedCall = [](auto inst) {
100 return inst->IsCall() && static_cast<const CallInst *>(inst)->IsInlined();
101 };
102 auto insts = header->AllInsts();
103 return std::find_if(insts.begin(), insts.end(), checkInlinedCall) != insts.end();
104 }
105
TransformLoop(Loop * loop)106 bool LoopPeeling::TransformLoop(Loop *loop)
107 {
108 ASSERT(loop->GetBackEdges().size() == 1);
109 ASSERT(loop->GetHeader()->GetLastInst()->GetOpcode() == Opcode::IfImm ||
110 loop->GetHeader()->GetLastInst()->GetOpcode() == Opcode::If);
111 auto header = loop->GetHeader();
112 // If header contains inlined call this call will be cloned and stay unpaired without `Return.inlined` instruction
113 if (HeaderHasInlinedCalls(header)) {
114 return false;
115 }
116 auto backEdge = loop->GetBackEdges()[0];
117 InsertPreLoop(loop);
118 auto movedInstCount = MoveLoopExitToBackEdge(header, backEdge);
119 CleanDeadPhis(header);
120 isAppied_ = true;
121 COMPILER_LOG(DEBUG, LOOP_TRANSFORM) << "Loop was peeled, id = " << loop->GetId();
122 GetGraph()->GetEventWriter().EventLoopPeeling(loop->GetId(), header->GetGuestPc(), backEdge->GetGuestPc(),
123 movedInstCount);
124 return true;
125 }
126
127 /// Clone the loop-header and insert before it
InsertPreLoop(Loop * loop)128 void LoopPeeling::InsertPreLoop(Loop *loop)
129 {
130 auto header = loop->GetHeader();
131 auto preHeader = loop->GetPreHeader();
132 auto graphCloner =
133 GraphCloner(header->GetGraph(), header->GetGraph()->GetAllocator(), header->GetGraph()->GetLocalAllocator());
134 graphCloner.CloneLoopHeader(header, GetLoopOuterBlock(header), preHeader);
135 }
136
137 /*
138 * Make back-edge loop-exit point
139 */
MoveLoopExitToBackEdge(BasicBlock * header,BasicBlock * backEdge)140 size_t LoopPeeling::MoveLoopExitToBackEdge(BasicBlock *header, BasicBlock *backEdge)
141 {
142 size_t movedInstCount = 0;
143 auto outerBlock = GetLoopOuterBlock(header);
144 size_t outerIdx = header->GetSuccBlockIndex(outerBlock);
145
146 // Create exit block
147 BasicBlock *exitBlock = nullptr;
148 if (header != backEdge) {
149 ASSERT(GetGraph()->IsAnalysisValid<DominatorsTree>());
150 exitBlock = backEdge->InsertNewBlockToSuccEdge(header);
151 outerBlock->ReplacePred(header, exitBlock);
152 header->RemoveSucc(outerBlock);
153 exitBlock->SetTry(header->IsTry());
154
155 auto loop = header->GetLoop();
156 loop->AppendBlock(exitBlock);
157 loop->ReplaceBackEdge(backEdge, exitBlock);
158
159 // Check the order of true-false successors
160 if (exitBlock->GetSuccBlockIndex(outerBlock) != outerIdx) {
161 exitBlock->SwapTrueFalseSuccessors();
162 }
163
164 // Fix Dominators info
165 auto &domTree = GetGraph()->GetAnalysis<DominatorsTree>();
166 domTree.SetValid(true);
167 domTree.SetDomPair(backEdge, exitBlock);
168 backEdge = exitBlock;
169 }
170
171 // Use reverse order to keep domination relation between instructions in the header-block
172 for (auto inst : header->InstsSafeReverse()) {
173 if (exitBlock != nullptr) {
174 header->EraseInst(inst);
175 exitBlock->PrependInst(inst);
176 movedInstCount++;
177 }
178 UpdateClonedInstInputs(inst, header, backEdge);
179 }
180
181 // Update outer phis
182 for (auto phi : outerBlock->PhiInsts()) {
183 size_t headerIdx = phi->CastToPhi()->GetPredBlockIndex(backEdge);
184 auto headerInst = phi->GetInput(headerIdx).GetInst();
185 if (headerInst->IsPhi()) {
186 phi->SetInput(headerIdx, headerInst->CastToPhi()->GetPhiInput(backEdge));
187 }
188 }
189
190 ssb_.FixPhisWithCheckInputs(header);
191 ssb_.FixPhisWithCheckInputs(exitBlock);
192 ssb_.FixPhisWithCheckInputs(outerBlock);
193
194 return movedInstCount;
195 }
196
UpdateClonedInstInputs(Inst * inst,BasicBlock * header,BasicBlock * backEdge)197 void LoopPeeling::UpdateClonedInstInputs(Inst *inst, BasicBlock *header, BasicBlock *backEdge)
198 {
199 for (size_t i = 0; i < inst->GetInputsCount(); ++i) {
200 auto inputInst = inst->GetInput(i).GetInst();
201 if (inputInst->IsPhi() && inputInst->GetBasicBlock() == header) {
202 auto phiInput = inputInst->CastToPhi()->GetPhiInput(backEdge);
203 // Replace phi by its input, if this input will NOT be moved to the exit block
204 bool isMoved = phiInput->GetBasicBlock() == header && !phiInput->IsPhi();
205 if (phiInput->IsDominate(inst) && !isMoved) {
206 inst->SetInput(i, phiInput);
207 }
208 }
209 }
210 }
211 } // namespace ark::compiler
212