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 if (!loop->GetInnerLoops().empty()) {
112 COMPILER_LOG(DEBUG, LOOP_TRANSFORM)
113 << "Loop wasn't peeled since it contains loops. Loop id = " << loop->GetId();
114 return false;
115 }
116 auto header = loop->GetHeader();
117 // If header contains inlined call this call will be cloned and stay unpaired without `Return.inlined` instruction
118 if (HeaderHasInlinedCalls(header)) {
119 return false;
120 }
121 auto backEdge = loop->GetBackEdges()[0];
122 InsertPreLoop(loop);
123 auto movedInstCount = MoveLoopExitToBackEdge(header, backEdge);
124 CleanDeadPhis(header);
125 isAppied_ = true;
126 COMPILER_LOG(DEBUG, LOOP_TRANSFORM) << "Loop was peeled, id = " << loop->GetId();
127 GetGraph()->GetEventWriter().EventLoopPeeling(loop->GetId(), header->GetGuestPc(), backEdge->GetGuestPc(),
128 movedInstCount);
129 return true;
130 }
131
132 /// Clone the loop-header and insert before it
InsertPreLoop(Loop * loop)133 void LoopPeeling::InsertPreLoop(Loop *loop)
134 {
135 auto header = loop->GetHeader();
136 auto preHeader = loop->GetPreHeader();
137 auto graphCloner =
138 GraphCloner(header->GetGraph(), header->GetGraph()->GetAllocator(), header->GetGraph()->GetLocalAllocator());
139 graphCloner.CloneLoopHeader(header, GetLoopOuterBlock(header), preHeader);
140 }
141
142 /*
143 * Make back-edge loop-exit point
144 */
MoveLoopExitToBackEdge(BasicBlock * header,BasicBlock * backEdge)145 size_t LoopPeeling::MoveLoopExitToBackEdge(BasicBlock *header, BasicBlock *backEdge)
146 {
147 size_t movedInstCount = 0;
148 auto outerBlock = GetLoopOuterBlock(header);
149 size_t outerIdx = header->GetSuccBlockIndex(outerBlock);
150
151 // Create exit block
152 BasicBlock *exitBlock = nullptr;
153 if (header != backEdge) {
154 ASSERT(GetGraph()->IsAnalysisValid<DominatorsTree>());
155 exitBlock = backEdge->InsertNewBlockToSuccEdge(header);
156 outerBlock->ReplacePred(header, exitBlock);
157 header->RemoveSucc(outerBlock);
158 exitBlock->SetTry(header->IsTry());
159
160 auto loop = header->GetLoop();
161 loop->AppendBlock(exitBlock);
162 loop->ReplaceBackEdge(backEdge, exitBlock);
163
164 // Check the order of true-false successors
165 if (exitBlock->GetSuccBlockIndex(outerBlock) != outerIdx) {
166 exitBlock->SwapTrueFalseSuccessors();
167 }
168
169 // Fix Dominators info
170 auto &domTree = GetGraph()->GetAnalysis<DominatorsTree>();
171 domTree.SetValid(true);
172 domTree.SetDomPair(backEdge, exitBlock);
173 backEdge = exitBlock;
174 }
175
176 // Use reverse order to keep domination relation between instructions in the header-block
177 for (auto inst : header->InstsSafeReverse()) {
178 if (exitBlock != nullptr) {
179 header->EraseInst(inst);
180 exitBlock->PrependInst(inst);
181 movedInstCount++;
182 }
183 UpdateClonedInstInputs(inst, header, backEdge);
184 }
185
186 // Update outer phis
187 for (auto phi : outerBlock->PhiInsts()) {
188 size_t headerIdx = phi->CastToPhi()->GetPredBlockIndex(backEdge);
189 auto headerInst = phi->GetInput(headerIdx).GetInst();
190 if (headerInst->IsPhi()) {
191 phi->SetInput(headerIdx, headerInst->CastToPhi()->GetPhiInput(backEdge));
192 }
193 }
194
195 ssb_.FixPhisWithCheckInputs(header);
196 ssb_.FixPhisWithCheckInputs(exitBlock);
197 ssb_.FixPhisWithCheckInputs(outerBlock);
198
199 return movedInstCount;
200 }
201
UpdateClonedInstInputs(Inst * inst,BasicBlock * header,BasicBlock * backEdge)202 void LoopPeeling::UpdateClonedInstInputs(Inst *inst, BasicBlock *header, BasicBlock *backEdge)
203 {
204 for (size_t i = 0; i < inst->GetInputsCount(); ++i) {
205 auto inputInst = inst->GetInput(i).GetInst();
206 if (inputInst->IsPhi() && inputInst->GetBasicBlock() == header) {
207 auto phiInput = inputInst->CastToPhi()->GetPhiInput(backEdge);
208 // Replace phi by its input, if this input will NOT be moved to the exit block
209 bool isMoved = phiInput->GetBasicBlock() == header && !phiInput->IsPhi();
210 if (phiInput->IsDominate(inst) && !isMoved) {
211 inst->SetInput(i, phiInput);
212 }
213 }
214 }
215 }
216 } // namespace ark::compiler
217