1 /*
2 * Copyright (c) 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 "cfgo.h"
17 #include "cgbb.h"
18 #include "cg.h"
19 #include "loop.h"
20 #include "mpl_logging.h"
21
22 /*
23 * This phase traverses all basic block of cgFunc and finds special
24 * basic block patterns, like continuous fallthrough basic block, continuous
25 * uncondition jump basic block, unreachable basic block and empty basic block,
26 * then do basic mergering, basic block placement transformations,
27 * unnecessary jumps elimination, and remove unreachable or empty basic block.
28 * This optimization is done on control flow graph basis.
29 */
30 namespace maplebe {
31 using namespace maple;
32
33 #define CFGO_DUMP_NEWPM CG_DEBUG_FUNC(f)
34
35 // find for a BB that can fallthru to curBB, which has only one BB at most.
FindPredFallthruBB(const BB & curBB)36 static BB *FindPredFallthruBB(const BB &curBB)
37 {
38 for (auto *pred : curBB.GetPreds()) {
39 if (pred->GetKind() == BB::kBBFallthru) {
40 return pred;
41 }
42 }
43 return nullptr;
44 }
45
46 /* return true if to is put after from and there is no real insns between from and to, */
NoInsnBetween(const BB & from,const BB & to) const47 bool ChainingPattern::NoInsnBetween(const BB &from, const BB &to) const
48 {
49 const BB *bb = nullptr;
50 for (bb = from.GetNext(); bb != nullptr && bb != &to && bb != cgFunc->GetLastBB(); bb = bb->GetNext()) {
51 if (!bb->IsEmptyOrCommentOnly() || bb->IsUnreachable() || bb->GetKind() != BB::kBBFallthru) {
52 return false;
53 }
54 }
55 return (bb == &to);
56 }
57
58 /* return true if insns in bb1 and bb2 are the same except the last goto insn. */
DoSameThing(const BB & bb1,const Insn & last1,const BB & bb2,const Insn & last2) const59 bool ChainingPattern::DoSameThing(const BB &bb1, const Insn &last1, const BB &bb2, const Insn &last2) const
60 {
61 const Insn *insn1 = bb1.GetFirstMachineInsn();
62 const Insn *insn2 = bb2.GetFirstMachineInsn();
63 while (insn1 != nullptr && insn1 != last1.GetNextMachineInsn() && insn2 != nullptr &&
64 insn2 != last2.GetNextMachineInsn()) {
65 if (!insn1->IsMachineInstruction()) {
66 insn1 = insn1->GetNext();
67 continue;
68 }
69 if (!insn2->IsMachineInstruction()) {
70 insn2 = insn2->GetNext();
71 continue;
72 }
73 if (insn1->GetMachineOpcode() != insn2->GetMachineOpcode()) {
74 return false;
75 }
76 uint32 opndNum = insn1->GetOperandSize();
77 for (uint32 i = 0; i < opndNum; ++i) {
78 Operand &op1 = insn1->GetOperand(i);
79 Operand &op2 = insn2->GetOperand(i);
80 if (&op1 == &op2) {
81 continue;
82 }
83 if (!op1.Equals(op2)) {
84 return false;
85 }
86 }
87 insn1 = insn1->GetNextMachineInsn();
88 insn2 = insn2->GetNextMachineInsn();
89 }
90 return (insn1 == last1.GetNextMachineInsn() && insn2 == last2.GetNextMachineInsn());
91 }
92
93 /*
94 * BB2 can be merged into BB1, if
95 * 1. BB1's kind is fallthrough;
96 * 2. BB2 has only one predecessor which is BB1 and BB2 is not the lastbb
97 * 3. BB2 is neither catch BB nor switch case BB
98 */
MergeFallthuBB(BB & curBB)99 bool ChainingPattern::MergeFallthuBB(BB &curBB)
100 {
101 BB *sucBB = curBB.GetNext();
102 if (sucBB == nullptr || IsLabelInLSDAOrSwitchTable(sucBB->GetLabIdx()) ||
103 !cgFunc->GetTheCFG()->CanMerge(curBB, *sucBB)) {
104 return false;
105 }
106 if (curBB.IsAtomicBuiltInBB() || sucBB->IsAtomicBuiltInBB()) {
107 return false;
108 }
109 Log(curBB.GetId());
110 if (checkOnly) {
111 return false;
112 }
113 if (sucBB == cgFunc->GetLastBB()) {
114 cgFunc->SetLastBB(curBB);
115 }
116 cgFunc->GetTheCFG()->MergeBB(curBB, *sucBB, *cgFunc);
117 keepPosition = true;
118 return true;
119 }
120
MergeGotoBB(BB & curBB,BB & sucBB)121 bool ChainingPattern::MergeGotoBB(BB &curBB, BB &sucBB)
122 {
123 Log(curBB.GetId());
124 if (checkOnly) {
125 return false;
126 }
127 cgFunc->GetTheCFG()->MergeBB(curBB, sucBB, *cgFunc);
128 keepPosition = true;
129 return true;
130 }
131
MoveSuccBBAsCurBBNext(BB & curBB,BB & sucBB)132 bool ChainingPattern::MoveSuccBBAsCurBBNext(BB &curBB, BB &sucBB)
133 {
134 /*
135 * without the judge below, there is
136 * Assembler Error: CFI state restore without previous remember
137 */
138 if (sucBB.GetHasCfi() || (sucBB.GetFirstInsn() != nullptr && sucBB.GetFirstInsn()->IsCfiInsn())) {
139 return false;
140 }
141 Log(curBB.GetId());
142 if (checkOnly) {
143 return false;
144 }
145 /* put sucBB as curBB's next. */
146 DEBUG_ASSERT(sucBB.GetPrev() != nullptr, "the target of current goto BB will not be the first bb");
147 sucBB.GetPrev()->SetNext(sucBB.GetNext());
148 if (sucBB.GetNext() != nullptr) {
149 sucBB.GetNext()->SetPrev(sucBB.GetPrev());
150 }
151 sucBB.SetNext(curBB.GetNext());
152 DEBUG_ASSERT(curBB.GetNext() != nullptr, "current goto BB will not be the last bb");
153 curBB.GetNext()->SetPrev(&sucBB);
154 if (sucBB.GetId() == cgFunc->GetLastBB()->GetId()) {
155 cgFunc->SetLastBB(*(sucBB.GetPrev()));
156 } else if (curBB.GetId() == cgFunc->GetLastBB()->GetId()) {
157 cgFunc->SetLastBB(sucBB);
158 }
159 sucBB.SetPrev(&curBB);
160 curBB.SetNext(&sucBB);
161 if (curBB.GetLastMachineInsn() != nullptr) {
162 curBB.RemoveInsn(*curBB.GetLastMachineInsn());
163 }
164 curBB.SetKind(BB::kBBFallthru);
165 return true;
166 }
167
RemoveGotoInsn(BB & curBB,BB & sucBB)168 bool ChainingPattern::RemoveGotoInsn(BB &curBB, BB &sucBB)
169 {
170 Log(curBB.GetId());
171 if (checkOnly) {
172 return false;
173 }
174 if (&sucBB != curBB.GetNext()) {
175 DEBUG_ASSERT(curBB.GetNext() != nullptr, "nullptr check");
176 curBB.ReplaceSucc(sucBB, *curBB.GetNext());
177 curBB.GetNext()->PushBackPreds(curBB);
178 sucBB.RemovePreds(curBB);
179 }
180 if (curBB.GetLastMachineInsn() != nullptr) {
181 curBB.RemoveInsn(*curBB.GetLastMachineInsn());
182 }
183 curBB.SetKind(BB::kBBFallthru);
184 return true;
185 }
186
ClearCurBBAndResetTargetBB(BB & curBB,BB & sucBB)187 bool ChainingPattern::ClearCurBBAndResetTargetBB(BB &curBB, BB &sucBB)
188 {
189 if (curBB.GetHasCfi() || (curBB.GetFirstInsn() != nullptr && curBB.GetFirstInsn()->IsCfiInsn())) {
190 return false;
191 }
192 Insn *brInsn = nullptr;
193 for (brInsn = curBB.GetLastMachineInsn(); brInsn != nullptr; brInsn = brInsn->GetPrev()) {
194 if (brInsn->IsUnCondBranch()) {
195 break;
196 }
197 }
198 DEBUG_ASSERT(brInsn != nullptr, "goto BB has no branch");
199 BB *newTarget = sucBB.GetPrev();
200 DEBUG_ASSERT(newTarget != nullptr, "get prev bb failed in ChainingPattern::ClearCurBBAndResetTargetBB");
201 Insn *last1 = newTarget->GetLastMachineInsn();
202 if (newTarget->GetKind() == BB::kBBGoto) {
203 Insn *br = nullptr;
204 for (br = newTarget->GetLastMachineInsn();
205 newTarget->GetFirstInsn() != nullptr && br != newTarget->GetFirstInsn()->GetPrev(); br = br->GetPrev()) {
206 DEBUG_ASSERT(br != nullptr, "br should not be nullptr");
207 if (br->IsUnCondBranch()) {
208 break;
209 }
210 }
211 DEBUG_ASSERT(br != nullptr, "goto BB has no branch");
212 last1 = br->GetPreviousMachineInsn();
213 }
214 if (last1 == nullptr) {
215 return false;
216 }
217 ASSERT_NOT_NULL(brInsn);
218 if (brInsn->GetPreviousMachineInsn() &&
219 !DoSameThing(*newTarget, *last1, curBB, *brInsn->GetPreviousMachineInsn())) {
220 return false;
221 }
222
223 Log(curBB.GetId());
224 if (checkOnly) {
225 return false;
226 }
227
228 LabelIdx tgtLabIdx = newTarget->GetLabIdx();
229 if (newTarget->GetLabIdx() == MIRLabelTable::GetDummyLabel()) {
230 tgtLabIdx = cgFunc->CreateLabel();
231 newTarget->AddLabel(tgtLabIdx);
232 cgFunc->SetLab2BBMap(tgtLabIdx, *newTarget);
233 }
234 LabelOperand &brTarget = cgFunc->GetOrCreateLabelOperand(tgtLabIdx);
235 brInsn->SetOperand(0, brTarget);
236 curBB.RemoveInsnSequence(*curBB.GetFirstInsn(), *brInsn->GetPrev());
237
238 curBB.RemoveFromSuccessorList(sucBB);
239 curBB.PushBackSuccs(*newTarget);
240 sucBB.RemoveFromPredecessorList(curBB);
241 newTarget->PushBackPreds(curBB);
242
243 sucBB.GetPrev()->SetUnreachable(false);
244 keepPosition = true;
245 return true;
246 }
247
248 /*
249 * Following optimizations are performed:
250 * 1. Basic block merging
251 * 2. unnecessary jumps elimination
252 * 3. Remove duplicates Basic block.
253 */
Optimize(BB & curBB)254 bool ChainingPattern::Optimize(BB &curBB)
255 {
256 if (curBB.IsUnreachable()) {
257 return false;
258 }
259
260 if (curBB.GetKind() == BB::kBBFallthru) {
261 return MergeFallthuBB(curBB);
262 }
263
264 if (curBB.GetKind() == BB::kBBGoto && !curBB.IsEmpty()) {
265 Insn *last = curBB.GetLastMachineInsn();
266 if (last->IsTailCall()) {
267 return false;
268 }
269
270 BB *sucBB = CGCFG::GetTargetSuc(curBB);
271 /*
272 * BB2 can be merged into BB1, if
273 * 1. BB1 ends with a goto;
274 * 2. BB2 has only one predecessor which is BB1
275 * 3. BB2 is of goto kind. Otherwise, the original fall through will be broken
276 * 4. BB2 is neither catch BB nor switch case BB
277 */
278 if (sucBB == nullptr) {
279 return false;
280 }
281 if (sucBB->GetKind() == BB::kBBGoto && !IsLabelInLSDAOrSwitchTable(sucBB->GetLabIdx()) &&
282 cgFunc->GetTheCFG()->CanMerge(curBB, *sucBB)) {
283 // BB9(curBB) BB1
284 // \ /
285 // BB5(sucBB, gotoBB)
286 // for this case, should not merge BB5, BB9
287 if (sucBB->GetPreds().size() > 1) {
288 return false;
289 }
290 return MergeGotoBB(curBB, *sucBB);
291 } else if (sucBB != &curBB && curBB.GetNext() != sucBB && sucBB != cgFunc->GetLastBB() &&
292 !sucBB->IsPredecessor(*sucBB->GetPrev()) &&
293 !(sucBB->GetNext() != nullptr && sucBB->GetNext()->IsPredecessor(*sucBB)) &&
294 !IsLabelInLSDAOrSwitchTable(sucBB->GetLabIdx()) && sucBB->GetKind() != BB::kBBThrow &&
295 curBB.GetNext() != nullptr) {
296 return MoveSuccBBAsCurBBNext(curBB, *sucBB);
297 }
298 /*
299 * Last goto instruction can be removed, if:
300 * 1. The goto target is physically the next one to current BB.
301 */
302 else if (sucBB == curBB.GetNext() ||
303 (NoInsnBetween(curBB, *sucBB) && !IsLabelInLSDAOrSwitchTable(curBB.GetNext()->GetLabIdx()))) {
304 return RemoveGotoInsn(curBB, *sucBB);
305 }
306 /*
307 * Clear curBB and target it to sucBB->GetPrev()
308 * if sucBB->GetPrev() and curBB's insns are the same.
309 *
310 * curBB: curBB:
311 * insn_x0 b prevbb
312 * b sucBB ...
313 * ... ==> prevbb:
314 * prevbb: insn_x0
315 * insn_x0 sucBB:
316 * sucBB:
317 */
318 else if (sucBB != curBB.GetNext() && !curBB.IsSoloGoto() && !IsLabelInLSDAOrSwitchTable(curBB.GetLabIdx()) &&
319 sucBB->GetKind() == BB::kBBReturn && sucBB->GetPreds().size() > 1 && sucBB->GetPrev() != nullptr &&
320 sucBB->IsPredecessor(*sucBB->GetPrev()) &&
321 (sucBB->GetPrev()->GetKind() == BB::kBBFallthru || sucBB->GetPrev()->GetKind() == BB::kBBGoto)) {
322 return ClearCurBBAndResetTargetBB(curBB, *sucBB);
323 }
324 }
325 return false;
326 }
327
328 /*
329 * curBB: curBB:
330 * insn_x0 insn_x0
331 * b targetBB b BB
332 * ... ==> ...
333 * targetBB: targetBB:
334 * b BB b BB
335 * ... ...
336 * BB: BB:
337 * *------------------------------
338 * curBB: curBB:
339 * insn_x0 insn_x0
340 * cond_br brBB cond_br BB
341 * ... ...
342 * brBB: ==> brBB:
343 * b BB b BB
344 * ... ...
345 * BB: BB:
346 *
347 * conditions:
348 * 1. only goto and comment in brBB;
349 */
Optimize(BB & curBB)350 bool SequentialJumpPattern::Optimize(BB &curBB)
351 {
352 if (curBB.IsUnreachable()) {
353 return false;
354 }
355 if (curBB.GetKind() == BB::kBBGoto && !curBB.IsEmpty()) {
356 BB *sucBB = CGCFG::GetTargetSuc(curBB);
357 CHECK_FATAL(sucBB != nullptr, "sucBB is null in SequentialJumpPattern::Optimize");
358 BB *targetBB = CGCFG::GetTargetSuc(*sucBB);
359 if ((sucBB != &curBB) && sucBB->IsSoloGoto() && targetBB != nullptr && targetBB != sucBB &&
360 !HasInvalidPred(*sucBB)) {
361 Log(curBB.GetId());
362 if (checkOnly) {
363 return false;
364 }
365 cgFunc->GetTheCFG()->RetargetJump(*sucBB, curBB);
366 SkipSucBB(curBB, *sucBB);
367 return true;
368 }
369 } else if (curBB.GetKind() == BB::kBBIf) {
370 for (BB *sucBB : curBB.GetSuccs()) {
371 BB *sucTargetBB = CGCFG::GetTargetSuc(*sucBB);
372 if (sucBB != curBB.GetNext() && sucBB->IsSoloGoto() && sucTargetBB != nullptr && sucTargetBB != sucBB &&
373 !HasInvalidPred(*sucBB)) {
374 Log(curBB.GetId());
375 if (checkOnly) {
376 return false;
377 }
378 // e.g.
379 // BB12[if] (curBB)
380 // beq label:11
381 // / \
382 // / BB25[if] (label:11)
383 // \ /
384 // BB13[goto] (sucBB)
385 // |
386 // BB6[ft] (targetBB) (label: 6)
387 // For the above case, the ifBB can not modify the target label of the conditional jump insn,
388 // because the target of the conditional jump insn is the other succBB(BB25).
389 BB *ifTargetBB = CGCFG::GetTargetSuc(curBB);
390 CHECK_NULL_FATAL(ifTargetBB);
391 // In addition, if the targetBB(ifTargetBB) of the ifBB is not the gotoBB(sucBB), and the
392 // targetBB(sucTargetBB) of the sucBB is not its next, we can not do the optimization, because it will
393 // change the layout of the sucTargetBB, and it does not necessarily improve performance.
394 if (ifTargetBB != sucBB && sucBB->GetNext() != sucTargetBB) {
395 return false;
396 }
397 if (ifTargetBB == sucBB) {
398 cgFunc->GetTheCFG()->RetargetJump(*sucBB, curBB);
399 }
400 SkipSucBB(curBB, *sucBB);
401 return true;
402 }
403 }
404 } else if (curBB.GetKind() == BB::kBBRangeGoto) {
405 bool changed = false;
406 for (BB *sucBB : curBB.GetSuccs()) {
407 if (sucBB != curBB.GetNext() && sucBB->IsSoloGoto() && !HasInvalidPred(*sucBB) &&
408 CGCFG::GetTargetSuc(*sucBB) != nullptr) {
409 Log(curBB.GetId());
410 if (checkOnly) {
411 return false;
412 }
413 UpdateSwitchSucc(curBB, *sucBB);
414 cgFunc->GetTheCFG()->FlushUnReachableStatusAndRemoveRelations(*sucBB, *cgFunc);
415 changed = true;
416 }
417 }
418 return changed;
419 }
420 return false;
421 }
422
UpdateSwitchSucc(BB & curBB,BB & sucBB) const423 void SequentialJumpPattern::UpdateSwitchSucc(BB &curBB, BB &sucBB) const
424 {
425 BB *gotoTarget = CGCFG::GetTargetSuc(sucBB);
426 CHECK_FATAL(gotoTarget != nullptr, "gotoTarget is null in SequentialJumpPattern::UpdateSwitchSucc");
427 const MapleVector<LabelIdx> &labelVec = curBB.GetRangeGotoLabelVec();
428 bool isPred = false;
429 for (auto label : labelVec) {
430 if (label == gotoTarget->GetLabIdx()) {
431 isPred = true;
432 break;
433 }
434 }
435 for (size_t i = 0; i < labelVec.size(); ++i) {
436 if (labelVec[i] == sucBB.GetLabIdx()) {
437 curBB.SetRangeGotoLabel(static_cast<uint32>(i), gotoTarget->GetLabIdx());
438 }
439 }
440 cgFunc->UpdateEmitSt(curBB, sucBB.GetLabIdx(), gotoTarget->GetLabIdx());
441
442 /* connect curBB, gotoTarget */
443 for (auto it = gotoTarget->GetPredsBegin(); it != gotoTarget->GetPredsEnd(); ++it) {
444 if (*it == &sucBB) {
445 auto origIt = it;
446 if (isPred) {
447 break;
448 }
449 if (origIt != gotoTarget->GetPredsBegin()) {
450 --origIt;
451 gotoTarget->InsertPred(origIt, curBB);
452 } else {
453 gotoTarget->PushFrontPreds(curBB);
454 }
455 break;
456 }
457 }
458 for (auto it = curBB.GetSuccsBegin(); it != curBB.GetSuccsEnd(); ++it) {
459 if (*it == &sucBB) {
460 auto origIt = it;
461 curBB.EraseSuccs(it);
462 if (isPred) {
463 break;
464 }
465 if (origIt != curBB.GetSuccsBegin()) {
466 --origIt;
467 curBB.InsertSucc(origIt, *gotoTarget);
468 } else {
469 curBB.PushFrontSuccs(*gotoTarget);
470 }
471 break;
472 }
473 }
474 /* cut curBB -> sucBB */
475 for (auto it = sucBB.GetPredsBegin(); it != sucBB.GetPredsEnd(); ++it) {
476 if (*it == &curBB) {
477 sucBB.ErasePreds(it);
478 }
479 }
480 for (auto it = curBB.GetSuccsBegin(); it != curBB.GetSuccsEnd(); ++it) {
481 if (*it == &sucBB) {
482 curBB.EraseSuccs(it);
483 }
484 }
485 }
486
HasInvalidPred(BB & sucBB) const487 bool SequentialJumpPattern::HasInvalidPred(BB &sucBB) const
488 {
489 for (auto predIt = sucBB.GetPredsBegin(); predIt != sucBB.GetPredsEnd(); ++predIt) {
490 if ((*predIt)->GetKind() != BB::kBBGoto && (*predIt)->GetKind() != BB::kBBIf &&
491 (*predIt)->GetKind() != BB::kBBRangeGoto && (*predIt)->GetKind() != BB::kBBFallthru) {
492 return true;
493 }
494 if ((*predIt)->GetKind() == BB::kBBIf) {
495 BB *ifTargetBB = CGCFG::GetTargetSuc(**predIt);
496 CHECK_NULL_FATAL(ifTargetBB);
497 BB *sucTargetBB = CGCFG::GetTargetSuc(sucBB);
498 CHECK_NULL_FATAL(sucTargetBB);
499 if (ifTargetBB != &sucBB && sucBB.GetNext() != sucTargetBB) {
500 return true;
501 }
502 }
503 if ((*predIt)->GetKind() == BB::kBBIf || (*predIt)->GetKind() == BB::kBBRangeGoto) {
504 if ((*predIt)->GetNext() == &sucBB) {
505 return true;
506 }
507 } else if ((*predIt)->GetKind() == BB::kBBGoto) {
508 if (*predIt == &sucBB || (*predIt)->IsEmpty()) {
509 return true;
510 }
511 }
512 }
513 return false;
514 }
515
516 /*
517 * preCond:
518 * sucBB is one of curBB's successor.
519 *
520 * Change curBB's successor to sucBB's successor
521 */
SkipSucBB(BB & curBB,BB & sucBB) const522 void SequentialJumpPattern::SkipSucBB(BB &curBB, BB &sucBB) const
523 {
524 BB *gotoTarget = CGCFG::GetTargetSuc(sucBB);
525 CHECK_FATAL(gotoTarget != nullptr, "gotoTarget is null in SequentialJumpPattern::SkipSucBB");
526 curBB.ReplaceSucc(sucBB, *gotoTarget);
527 sucBB.RemovePreds(curBB);
528 gotoTarget->PushBackPreds(curBB);
529 // If the sucBB needs to be skipped, all preds of the sucBB must skip it and update cfg info.
530 // e.g.
531 // BB3[if] (curBB)
532 // / \
533 // / BB6[if] (not care)
534 // \ /
535 // BB10[goto] (sucBB)
536 // |
537 // BB8 (gotoTarget)
538 for (auto *predBB : sucBB.GetPreds()) {
539 if (predBB->GetKind() == BB::kBBGoto) {
540 cgFunc->GetTheCFG()->RetargetJump(sucBB, *predBB);
541 } else if (predBB->GetKind() == BB::kBBIf) {
542 BB *ifTargetBB = CGCFG::GetTargetSuc(*predBB);
543 if (ifTargetBB == &sucBB) {
544 cgFunc->GetTheCFG()->RetargetJump(sucBB, *predBB);
545 }
546 } else if (predBB->GetKind() == BB::kBBFallthru) {
547 // e.g.
548 // (curBB) BB70[goto] BB27[if]
549 // \ / \
550 // \ / \
551 // \ BB71[ft] (iterPredBB) \
552 // \ / \
553 // BB48[goto] (sucBB) BB28[ft]
554 // | /
555 // | /
556 // BB29[if] (gotoTarget)
557 ASSERT_NOT_NULL(cgFunc->GetTheCFG()->GetInsnModifier());
558 cgFunc->GetTheCFG()->GetInsnModifier()->ModifyFathruBBToGotoBB(*predBB, gotoTarget->GetLabIdx());
559 } else if (predBB->GetKind() == BB::kBBRangeGoto) {
560 UpdateSwitchSucc(*predBB, sucBB);
561 }
562 predBB->ReplaceSucc(sucBB, *gotoTarget);
563 sucBB.RemovePreds(*predBB);
564 gotoTarget->PushBackPreds(*predBB);
565 }
566 cgFunc->GetTheCFG()->FlushUnReachableStatusAndRemoveRelations(sucBB, *cgFunc);
567 // LastBB cannot be removed from the preds of succBB by FlushUnReachableStatusAndRemoveRelations, Why?
568 // We'll do a separate process below for the case that sucBB is LastBB.
569 if (sucBB.GetKind() == BB::kBBGoto && &sucBB == cgFunc->GetLastBB()) {
570 // gotoBB has only one succ.
571 DEBUG_ASSERT(sucBB.GetSuccsSize() == 1, "invalid gotoBB");
572 sucBB.SetUnreachable(true);
573 sucBB.SetFirstInsn(nullptr);
574 sucBB.SetLastInsn(nullptr);
575 gotoTarget->RemovePreds(sucBB);
576 sucBB.RemoveSuccs(*gotoTarget);
577 }
578 // Remove the unreachableBB which has been skipped
579 if (sucBB.IsUnreachable()) {
580 cgFunc->GetTheCFG()->RemoveBB(sucBB);
581 }
582 }
583
584 /*
585 * Found pattern
586 * curBB: curBB:
587 * ... ==> ...
588 * cond_br brBB cond1_br ftBB
589 * ftBB: brBB:
590 * bl throwfunc ...
591 * brBB: retBB:
592 * ... ...
593 * retBB: ftBB:
594 * ... bl throwfunc
595 */
RelocateThrowBB(BB & curBB)596 void FlipBRPattern::RelocateThrowBB(BB &curBB)
597 {
598 BB *ftBB = curBB.GetNext();
599 CHECK_FATAL(ftBB != nullptr, "ifBB has a fall through BB");
600 CGCFG *theCFG = cgFunc->GetTheCFG();
601 CHECK_FATAL(theCFG != nullptr, "nullptr check");
602 BB *retBB = theCFG->FindLastRetBB();
603 retBB = (retBB == nullptr ? cgFunc->GetLastBB() : retBB);
604 CHECK_FATAL(retBB != nullptr, "must have a return BB");
605 if (ftBB->GetKind() != BB::kBBThrow || IsLabelInLSDAOrSwitchTable(ftBB->GetLabIdx())) {
606 return;
607 }
608 BB *brBB = CGCFG::GetTargetSuc(curBB);
609 if (brBB != ftBB->GetNext()) {
610 return;
611 }
612 #ifndef ONLY_C
613 EHFunc *ehFunc = cgFunc->GetEHFunc();
614 if (ehFunc != nullptr && ehFunc->GetLSDACallSiteTable() != nullptr) {
615 const MapleVector<LSDACallSite *> &callsiteTable = ehFunc->GetLSDACallSiteTable()->GetCallSiteTable();
616 for (size_t i = 0; i < callsiteTable.size(); ++i) {
617 LSDACallSite *lsdaCallsite = callsiteTable[i];
618 BB *endTry = cgFunc->GetBBFromLab2BBMap(lsdaCallsite->csLength.GetEndOffset()->GetLabelIdx());
619 BB *startTry = cgFunc->GetBBFromLab2BBMap(lsdaCallsite->csLength.GetStartOffset()->GetLabelIdx());
620 if (retBB->GetId() >= startTry->GetId() && retBB->GetId() <= endTry->GetId()) {
621 if (retBB->GetNext()->GetId() < startTry->GetId() || retBB->GetNext()->GetId() > endTry->GetId() ||
622 curBB.GetId() < startTry->GetId() || curBB.GetId() > endTry->GetId()) {
623 return;
624 }
625 } else {
626 if ((retBB->GetNext()->GetId() >= startTry->GetId() && retBB->GetNext()->GetId() <= endTry->GetId()) ||
627 (curBB.GetId() >= startTry->GetId() && curBB.GetId() <= endTry->GetId())) {
628 return;
629 }
630 }
631 }
632 }
633 #endif
634 /* get branch insn of curBB */
635 Insn *curBBBranchInsn = theCFG->FindLastCondBrInsn(curBB);
636 CHECK_FATAL(curBBBranchInsn != nullptr, "curBB(it is a kBBif) has no branch");
637
638 /* Reverse the branch */
639 uint32 targetIdx = GetJumpTargetIdx(*curBBBranchInsn);
640 MOperator mOp = FlipConditionOp(curBBBranchInsn->GetMachineOpcode());
641 LabelOperand &brTarget = cgFunc->GetOrCreateLabelOperand(*ftBB);
642 curBBBranchInsn->SetMOP(cgFunc->GetCG()->GetTargetMd(mOp));
643 curBBBranchInsn->SetOperand(targetIdx, brTarget);
644
645 /* move ftBB after retBB */
646 curBB.SetNext(brBB);
647 CHECK_NULL_FATAL(brBB);
648 brBB->SetPrev(&curBB);
649
650 retBB->GetNext()->SetPrev(ftBB);
651 ftBB->SetNext(retBB->GetNext());
652 ftBB->SetPrev(retBB);
653 retBB->SetNext(ftBB);
654 }
655
656 /*
657 * 1. relocate goto BB
658 * Found pattern (1) ftBB->GetPreds().size() == 1
659 * curBB: curBB: cond1_br target
660 * ... ==> brBB:
661 * cond_br brBB ...
662 * ftBB: targetBB: (ftBB,targetBB)
663 * goto target (2) ftBB->GetPreds().size() > 1
664 * brBB: curBB : cond1_br ftBB
665 * ... brBB:
666 * targetBB ...
667 * ftBB
668 * targetBB
669 *
670 * 2. loopHeaderBB: loopHeaderBB:
671 * ... ...
672 * cond_br loopExit: cond_br loopHeaderBB
673 * ftBB: ftBB:
674 * goto loopHeaderBB: goto loopExit
675 *
676 * 3. relocate throw BB in RelocateThrowBB()
677 */
Optimize(BB & curBB)678 bool FlipBRPattern::Optimize(BB &curBB)
679 {
680 if (curBB.IsUnreachable()) {
681 return false;
682 }
683 if (curBB.GetKind() == BB::kBBIf && !curBB.IsEmpty()) {
684 BB *ftBB = curBB.GetNext();
685 DEBUG_ASSERT(ftBB != nullptr, "ftBB is null in FlipBRPattern::Optimize");
686 BB *brBB = CGCFG::GetTargetSuc(curBB);
687 DEBUG_ASSERT(brBB != nullptr, "brBB is null in FlipBRPattern::Optimize");
688 /* Check if it can be optimized */
689 if (ftBB->GetKind() == BB::kBBGoto && ftBB->GetNext() == brBB) {
690 Insn *curBBBranchInsn = nullptr;
691 for (curBBBranchInsn = curBB.GetLastMachineInsn(); curBBBranchInsn != nullptr;
692 curBBBranchInsn = curBBBranchInsn->GetPrev()) {
693 if (curBBBranchInsn->IsBranch()) {
694 break;
695 }
696 }
697 DEBUG_ASSERT(curBBBranchInsn != nullptr, "FlipBRPattern: curBB has no branch");
698 Insn *brInsn = nullptr;
699 for (brInsn = ftBB->GetLastMachineInsn(); brInsn != nullptr; brInsn = brInsn->GetPrev()) {
700 if (brInsn->IsUnCondBranch()) {
701 break;
702 }
703 }
704 DEBUG_ASSERT(brInsn != nullptr, "FlipBRPattern: ftBB has no branch");
705
706 /* Reverse the branch */
707 ASSERT_NOT_NULL(curBBBranchInsn);
708 uint32 targetIdx = GetJumpTargetIdx(*curBBBranchInsn);
709 MOperator mOp = FlipConditionOp(curBBBranchInsn->GetMachineOpcode());
710 if (mOp == 0) {
711 return false;
712 }
713 auto it = ftBB->GetSuccsBegin();
714 BB *tgtBB = *it;
715 if (ftBB->GetPreds().size() == 1 &&
716 (ftBB->IsSoloGoto() ||
717 (!IsLabelInLSDAOrSwitchTable(tgtBB->GetLabIdx()) && cgFunc->GetTheCFG()->CanMerge(*ftBB, *tgtBB)))) {
718 curBBBranchInsn->SetMOP(cgFunc->GetCG()->GetTargetMd(mOp));
719 ASSERT_NOT_NULL(brInsn);
720 Operand &brTarget = brInsn->GetOperand(GetJumpTargetIdx(*brInsn));
721 curBBBranchInsn->SetOperand(targetIdx, brTarget);
722 /* Insert ftBB's insn at the beginning of tgtBB. */
723 if (!ftBB->IsSoloGoto()) {
724 ftBB->RemoveInsn(*brInsn);
725 tgtBB->InsertAtBeginning(*ftBB);
726 }
727 /* Patch pred and succ lists */
728 ftBB->EraseSuccs(it);
729 ftBB->PushBackSuccs(*brBB);
730 it = curBB.GetSuccsBegin();
731 CHECK_FATAL(*it != nullptr, "nullptr check");
732 if (*it == brBB) {
733 curBB.ReplaceSucc(it, *tgtBB);
734 } else {
735 ++it;
736 curBB.ReplaceSucc(it, *tgtBB);
737 }
738 for (it = tgtBB->GetPredsBegin(); it != tgtBB->GetPredsEnd(); ++it) {
739 if (*it == ftBB) {
740 tgtBB->ErasePreds(it);
741 break;
742 }
743 }
744 tgtBB->PushBackPreds(curBB);
745 for (it = brBB->GetPredsBegin(); it != brBB->GetPredsEnd(); ++it) {
746 if (*it == &curBB) {
747 brBB->ErasePreds(it);
748 break;
749 }
750 }
751 brBB->PushFrontPreds(*ftBB);
752 /* Remove instructions from ftBB so curBB falls thru to brBB */
753 ftBB->SetFirstInsn(nullptr);
754 ftBB->SetLastInsn(nullptr);
755 ftBB->SetKind(BB::kBBFallthru);
756 } else if (!IsLabelInLSDAOrSwitchTable(ftBB->GetLabIdx()) && !tgtBB->IsPredecessor(*tgtBB->GetPrev())) {
757 curBBBranchInsn->SetMOP(cgFunc->GetCG()->GetTargetMd(mOp));
758 LabelIdx tgtLabIdx = ftBB->GetLabIdx();
759 if (ftBB->GetLabIdx() == MIRLabelTable::GetDummyLabel()) {
760 tgtLabIdx = cgFunc->CreateLabel();
761 ftBB->AddLabel(tgtLabIdx);
762 cgFunc->SetLab2BBMap(tgtLabIdx, *ftBB);
763 }
764 LabelOperand &brTarget = cgFunc->GetOrCreateLabelOperand(tgtLabIdx);
765 curBBBranchInsn->SetOperand(targetIdx, brTarget);
766 curBB.SetNext(brBB);
767 brBB->SetPrev(&curBB);
768 ftBB->SetPrev(tgtBB->GetPrev());
769 tgtBB->GetPrev()->SetNext(ftBB);
770 ftBB->SetNext(tgtBB);
771 tgtBB->SetPrev(ftBB);
772
773 ftBB->RemoveInsn(*brInsn);
774 ftBB->SetKind(BB::kBBFallthru);
775 }
776 } else if (GetPhase() == kCfgoPostRegAlloc && ftBB->GetKind() == BB::kBBGoto &&
777 loopInfo.GetBBLoopParent(curBB.GetId()) != nullptr &&
778 loopInfo.GetBBLoopParent(curBB.GetId()) == loopInfo.GetBBLoopParent(ftBB->GetId()) &&
779 ftBB->IsSoloGoto() &&
780 &(loopInfo.GetBBLoopParent(ftBB->GetId())->GetHeader()) == *(ftBB->GetSuccsBegin()) &&
781 !loopInfo.GetBBLoopParent(curBB.GetId())->Has(
782 (curBB.GetSuccs().front() == ftBB) ? *curBB.GetSuccs().back() : *curBB.GetSuccs().front())) {
783 Insn *curBBBranchInsn = nullptr;
784 for (curBBBranchInsn = curBB.GetLastMachineInsn(); curBBBranchInsn != nullptr;
785 curBBBranchInsn = curBBBranchInsn->GetPrev()) {
786 if (curBBBranchInsn->IsBranch()) {
787 break;
788 }
789 }
790 DEBUG_ASSERT(curBBBranchInsn != nullptr, "FlipBRPattern: curBB has no branch");
791 Insn *brInsn = nullptr;
792 for (brInsn = ftBB->GetLastMachineInsn(); brInsn != nullptr; brInsn = brInsn->GetPrev()) {
793 if (brInsn->IsUnCondBranch()) {
794 break;
795 }
796 }
797 DEBUG_ASSERT(brInsn != nullptr, "FlipBRPattern: ftBB has no branch");
798 uint32 condTargetIdx = GetJumpTargetIdx(*curBBBranchInsn);
799 LabelOperand &condTarget = static_cast<LabelOperand &>(curBBBranchInsn->GetOperand(condTargetIdx));
800 MOperator mOp = FlipConditionOp(curBBBranchInsn->GetMachineOpcode());
801 if (mOp == 0) {
802 return false;
803 }
804 uint32 gotoTargetIdx = GetJumpTargetIdx(*brInsn);
805 LabelOperand &gotoTarget = static_cast<LabelOperand &>(brInsn->GetOperand(gotoTargetIdx));
806 curBBBranchInsn->SetMOP(cgFunc->GetCG()->GetTargetMd(mOp));
807 curBBBranchInsn->SetOperand(condTargetIdx, gotoTarget);
808 brInsn->SetOperand(gotoTargetIdx, condTarget);
809 auto it = ftBB->GetSuccsBegin();
810 BB *loopHeadBB = *it;
811 curBB.ReplaceSucc(*brBB, *loopHeadBB);
812 brBB->RemovePreds(curBB);
813 ftBB->ReplaceSucc(*loopHeadBB, *brBB);
814 loopHeadBB->RemovePreds(*ftBB);
815
816 loopHeadBB->PushBackPreds(curBB);
817 brBB->PushBackPreds(*ftBB);
818 } else {
819 RelocateThrowBB(curBB);
820 }
821 }
822 return false;
823 }
824
825 /* remove a basic block that contains nothing */
Optimize(BB & curBB)826 bool EmptyBBPattern::Optimize(BB &curBB)
827 {
828 // Can not remove the BB whose address is referenced by adrp_label insn
829 if (curBB.IsUnreachable() || curBB.IsAdrpLabel()) {
830 return false;
831 }
832 /* Empty bb and it's not a cleanupBB/returnBB/lastBB/catchBB. */
833 if (curBB.GetPrev() == nullptr || curBB.IsCleanup() || &curBB == cgFunc->GetLastBB() ||
834 curBB.GetKind() == BB::kBBReturn || IsLabelInLSDAOrSwitchTable(curBB.GetLabIdx())) {
835 return false;
836 }
837 if (curBB.GetFirstInsn() == nullptr && curBB.GetLastInsn() == nullptr) {
838 // empty BB
839 Log(curBB.GetId());
840 if (checkOnly) {
841 return false;
842 }
843
844 BB *sucBB = CGCFG::GetTargetSuc(curBB);
845 if (sucBB == nullptr || sucBB->IsCleanup()) {
846 return false;
847 }
848 cgFunc->GetTheCFG()->RemoveBB(curBB);
849 /* removeBB may do nothing. since no need to repeat, always ret false here. */
850 return false;
851 } else if (!curBB.HasMachineInsn()) {
852 // BB only has dbg insn
853 Log(curBB.GetId());
854 if (checkOnly) {
855 return false;
856 }
857 BB *sucBB = CGCFG::GetTargetSuc(curBB);
858 if (sucBB == nullptr || sucBB->IsCleanup()) {
859 return false;
860 }
861 // For Now We try to sink first conservatively.
862 // All dbg insns should not be dropped. Later hoist or copy case should be considered.
863 if (curBB.NumSuccs() == 1) {
864 BB *succBB = curBB.GetSuccs().front();
865 succBB->InsertAtBeginning(curBB);
866 cgFunc->GetTheCFG()->RemoveBB(curBB);
867 }
868 return false;
869 }
870 return false;
871 }
872
873 /*
874 * remove unreachable BB
875 * condition:
876 * 1. unreachable BB can't have cfi instruction when postcfgo.
877 */
Optimize(BB & curBB)878 bool UnreachBBPattern::Optimize(BB &curBB)
879 {
880 if (curBB.IsUnreachable()) {
881 Log(curBB.GetId());
882 if (checkOnly) {
883 return false;
884 }
885 /* if curBB in exitbbsvec,return false. */
886 if (cgFunc->IsExitBB(curBB)) {
887 // In C some bb follow noreturn calls should remain unreachable
888 curBB.SetUnreachable(cgFunc->GetMirModule().GetSrcLang() == kSrcLangC);
889 return false;
890 }
891
892 if (curBB.GetHasCfi() || (curBB.GetFirstInsn() != nullptr && curBB.GetFirstInsn()->IsCfiInsn())) {
893 return false;
894 }
895
896 #ifndef ONLY_C
897 EHFunc *ehFunc = cgFunc->GetEHFunc();
898 /* if curBB InLSDA ,replace curBB's label with nextReachableBB before remove it. */
899 if (ehFunc != nullptr && ehFunc->NeedFullLSDA() && CGCFG::InLSDA(curBB.GetLabIdx(), ehFunc)) {
900 /* find nextReachableBB */
901 BB *nextReachableBB = nullptr;
902 for (BB *bb = &curBB; bb != nullptr; bb = bb->GetNext()) {
903 if (!bb->IsUnreachable()) {
904 nextReachableBB = bb;
905 break;
906 }
907 }
908 CHECK_FATAL(nextReachableBB != nullptr, "nextReachableBB not be nullptr");
909 if (nextReachableBB->GetLabIdx() == 0) {
910 LabelIdx labIdx = cgFunc->CreateLabel();
911 nextReachableBB->AddLabel(labIdx);
912 cgFunc->SetLab2BBMap(labIdx, *nextReachableBB);
913 }
914
915 ehFunc->GetLSDACallSiteTable()->UpdateCallSite(curBB, *nextReachableBB);
916 }
917 #endif
918
919 // Indicates whether the curBB is removed
920 bool isRemoved = true;
921 if (curBB.GetPrev() != nullptr) {
922 curBB.GetPrev()->SetNext(curBB.GetNext());
923 }
924 if (curBB.GetNext() != nullptr) {
925 curBB.GetNext()->SetPrev(curBB.GetPrev());
926 } else {
927 cgFunc->SetLastBB(*(curBB.GetPrev()));
928 }
929 if (cgFunc->GetFirstBB() == cgFunc->GetLastBB() && cgFunc->GetFirstBB() != nullptr) {
930 isRemoved = false;
931 }
932
933 /* flush after remove */
934 for (BB *bb : curBB.GetSuccs()) {
935 bb->RemovePreds(curBB);
936 cgFunc->GetTheCFG()->FlushUnReachableStatusAndRemoveRelations(*bb, *cgFunc);
937 }
938 curBB.ClearSuccs();
939 // return always be false
940 if (!isRemoved) {
941 return false;
942 }
943 }
944 return false;
945 }
946
947 /* BB_pred1: BB_pred1:
948 * b curBB insn_x0
949 * ... b BB2
950 * BB_pred2: ==> ...
951 * b curBB BB_pred2:
952 * ... insn_x0
953 * curBB: b BB2
954 * insn_x0 ...
955 * b BB2 curBB:
956 * insn_x0
957 * b BB2
958 * condition:
959 * 1. The number of instruct in curBB
960 * is less than THRESHOLD;
961 * 2. curBB can't have cfi instruction when postcfgo.
962 */
Optimize(BB & curBB)963 bool DuplicateBBPattern::Optimize(BB &curBB)
964 {
965 if (!cgFunc->IsAfterRegAlloc()) {
966 return false;
967 }
968 if (curBB.IsUnreachable()) {
969 return false;
970 }
971 if (CGOptions::IsNoDupBB() || CGOptions::OptimizeForSize()) {
972 return false;
973 }
974
975 /* curBB can't be in try block */
976 if (curBB.GetKind() != BB::kBBGoto || IsLabelInLSDAOrSwitchTable(curBB.GetLabIdx())) {
977 return false;
978 }
979
980 #if defined(TARGARM32) && TARGARM32
981 FOR_BB_INSNS(insn, (&curBB))
982 {
983 if (insn->IsPCLoad() || insn->IsClinit()) {
984 return false;
985 }
986 }
987 #endif
988 /* It is possible curBB jump to itself, no benefit from duplicate */
989 for (BB *bb : curBB.GetPreds()) {
990 if (bb == &curBB) {
991 return false;
992 }
993 }
994
995 uint32 numPreds = curBB.NumPreds();
996 if (numPreds > 1 && CGCFG::GetTargetSuc(curBB) != nullptr && CGCFG::GetTargetSuc(curBB)->NumPreds() > 1) {
997 std::vector<BB *> candidates;
998 for (BB *bb : curBB.GetPreds()) {
999 if (bb->GetKind() == BB::kBBGoto && bb->GetNext() != &curBB && bb != &curBB && !bb->IsEmpty()) {
1000 candidates.emplace_back(bb);
1001 }
1002 }
1003 if (candidates.empty()) {
1004 return false;
1005 }
1006 if (curBB.NumInsn() <= kThreshold) {
1007 if (curBB.GetHasCfi() || (curBB.GetFirstInsn() != nullptr && curBB.GetFirstInsn()->IsCfiInsn())) {
1008 return false;
1009 }
1010 Log(curBB.GetId());
1011 if (checkOnly) {
1012 return false;
1013 }
1014 bool changed = false;
1015 for (BB *bb : candidates) {
1016 bb->RemoveInsn(*bb->GetLastInsn());
1017 FOR_BB_INSNS(insn, (&curBB))
1018 {
1019 if (!insn->IsMachineInstruction() && !(bb->IsCloseTo(curBB) && insn->IsDbgLine())) {
1020 continue;
1021 }
1022 Insn *clonedInsn = cgFunc->GetTheCFG()->CloneInsn(*insn);
1023 clonedInsn->SetPrev(nullptr);
1024 clonedInsn->SetNext(nullptr);
1025 clonedInsn->SetBB(nullptr);
1026 bb->AppendInsn(*clonedInsn);
1027 }
1028 bb->RemoveSuccs(curBB);
1029 for (BB *item : curBB.GetSuccs()) {
1030 bb->PushBackSuccs(*item);
1031 item->PushBackPreds(*bb);
1032 }
1033 curBB.RemovePreds(*bb);
1034 changed = true;
1035 }
1036 cgFunc->GetTheCFG()->FlushUnReachableStatusAndRemoveRelations(curBB, *cgFunc);
1037 return changed;
1038 }
1039 }
1040 return false;
1041 }
1042
CheckBBInsnsMatch(BB & bb1,BB & bb2,Insn * & f1,Insn * & f2)1043 uint32 CrossJumpBBPattern::CheckBBInsnsMatch(BB &bb1, BB &bb2, Insn *&f1, Insn *&f2)
1044 {
1045 // skip jump insn, all jump insn is compared in CheckBBSuccMatch
1046 auto skipBBJumpInsn = [](BB &bb) {
1047 auto *insn = bb.GetLastMachineInsn();
1048 if (insn != nullptr && insn->IsBranch()) {
1049 insn = insn->GetPreviousMachineInsn();
1050 }
1051 return insn;
1052 };
1053 auto *insn1 = skipBBJumpInsn(bb1);
1054 auto *insn2 = skipBBJumpInsn(bb2);
1055
1056 uint32 ninsns = 0;
1057 Insn *last1 = nullptr;
1058 Insn *last2 = nullptr;
1059 while (insn1 != nullptr && insn2 != nullptr) {
1060 if (!insn1->Equals(*insn2)) {
1061 break;
1062 }
1063 ++ninsns;
1064 last1 = insn1;
1065 last2 = insn2;
1066 insn1 = insn1->GetPreviousMachineInsn();
1067 insn2 = insn2->GetPreviousMachineInsn();
1068 }
1069 if (ninsns != 0) {
1070 f1 = last1;
1071 f2 = last2;
1072 }
1073 return ninsns;
1074 }
1075
CheckBBSuccMatch(BB & bb1,BB & bb2)1076 bool CrossJumpBBPattern::CheckBBSuccMatch(BB &bb1, BB &bb2)
1077 {
1078 auto *brInsn1 = bb1.GetLastMachineInsn();
1079 auto *brInsn2 = bb2.GetLastMachineInsn();
1080 if (brInsn1 == nullptr || brInsn2 == nullptr) {
1081 return false;
1082 }
1083
1084 // When both bb1 and bb2 have only one successor, and bb has no jump instruction or
1085 // the jump instruction is a goto instruction, we can merge them directly.
1086 if (bb1.GetSuccsSize() == 1 &&
1087 (!brInsn1->IsBranch() || cgFunc->GetTheCFG()->GetInsnModifier()->IsSimpleJumpInsn(*brInsn1))) {
1088 return (bb2.GetSuccsSize() == 1 &&
1089 (!brInsn2->IsBranch() || cgFunc->GetTheCFG()->GetInsnModifier()->IsSimpleJumpInsn(*brInsn2)));
1090 }
1091
1092 // check conditional jumps
1093 if (bb1.GetSuccsSize() == BB::kBBIfSuccsSize && brInsn1->IsCondBranch() &&
1094 bb2.GetSuccsSize() == BB::kBBIfSuccsSize && brInsn2->IsCondBranch()) {
1095 auto *b1 = cgFunc->GetTheCFG()->GetTargetSuc(bb1);
1096 auto *b2 = cgFunc->GetTheCFG()->GetTargetSuc(bb2);
1097 auto *f1 = bb1.GetNext();
1098 auto *f2 = bb2.GetNext();
1099
1100 auto getSoloGotoTrueTarget = [this](BB &bb) {
1101 return (bb.IsSoloGoto() ? cgFunc->GetTheCFG()->GetTargetSuc(bb) : &bb);
1102 };
1103 f1 = getSoloGotoTrueTarget(*f1);
1104 f2 = getSoloGotoTrueTarget(*f2);
1105
1106 bool reverse = false;
1107 if (f1 == f2 && b1 == b2) {
1108 reverse = false;
1109 } else if (f1 == b2 && b1 == f2) {
1110 reverse = true;
1111 } else {
1112 return false;
1113 }
1114
1115 if (!reverse) {
1116 return brInsn1->Equals(*brInsn2);
1117 }
1118
1119 auto newCode = FlipConditionOp(brInsn2->GetMachineOpcode());
1120 if (newCode != brInsn1->GetMachineOpcode()) {
1121 return false;
1122 }
1123 auto targetIdx = GetJumpTargetIdx(*brInsn2);
1124 for (uint32 i = 0; i < brInsn1->GetOperandSize(); ++i) {
1125 if (i == targetIdx) {
1126 continue;
1127 }
1128 if (!brInsn1->GetOperand(i).Equals(brInsn2->GetOperand(i))) {
1129 return false;
1130 }
1131 }
1132 auto &tgtOpnd1 = brInsn1->GetOperand(targetIdx);
1133 auto &tgtOpnd2 = cgFunc->GetOrCreateLabelOperand(*f2);
1134 return tgtOpnd1.Equals(tgtOpnd2);
1135 }
1136 return false;
1137 }
1138
1139 // split srcBB at lastInsn, and set newBB is srcBB's fallthru
SplitBB(BB & srcBB,Insn & lastInsn)1140 BB &CrossJumpBBPattern::SplitBB(BB &srcBB, Insn &lastInsn)
1141 {
1142 auto &newBB = *cgFunc->CreateNewBB(false, srcBB.GetKind(), srcBB.GetFrequency());
1143
1144 std::vector<Insn *> splitInsns;
1145 for (auto *newInsn = lastInsn.GetNext(); newInsn != nullptr; newInsn = newInsn->GetNext()) {
1146 splitInsns.push_back(newInsn);
1147 }
1148 srcBB.RemoveInsnSequence(*lastInsn.GetNext(), *srcBB.GetLastInsn());
1149 for (auto *insn : splitInsns) {
1150 newBB.AppendInsn(*insn);
1151 }
1152
1153 for (auto *succ : srcBB.GetSuccs()) {
1154 newBB.PushBackSuccs(*succ, srcBB.GetEdgeProb(*succ));
1155 succ->RemovePreds(srcBB);
1156 succ->PushBackPreds(newBB);
1157 }
1158 srcBB.ClearSuccs();
1159 srcBB.PushBackSuccs(newBB);
1160 newBB.PushBackPreds(srcBB);
1161
1162 srcBB.SetKind(BB::kBBFallthru);
1163 newBB.SetNext(srcBB.GetNext());
1164 srcBB.GetNext()->SetPrev(&newBB);
1165 srcBB.SetNext(&newBB);
1166 newBB.SetPrev(&srcBB);
1167 return newBB;
1168 }
1169
GetMergeDirection(BB & bb1,BB & bb2,const Insn & f1,const Insn & f2,MergeDirection & dir)1170 void CrossJumpBBPattern::GetMergeDirection(BB &bb1, BB &bb2, const Insn &f1, const Insn &f2, MergeDirection &dir)
1171 {
1172 auto mergeDirection = [](MergeDirection dir1, MergeDirection dir2) {
1173 if (dir1 == dir2) {
1174 return dir1;
1175 }
1176 if (dir1 == kDirectionBoth) {
1177 return dir2;
1178 } else if (dir2 == kDirectionBoth) {
1179 return dir1;
1180 }
1181 return kDirectionNone;
1182 };
1183
1184 auto *brInsn1 = bb1.GetLastMachineInsn();
1185 auto *brInsn2 = bb2.GetLastMachineInsn();
1186 ASSERT_NOT_NULL(brInsn1);
1187 ASSERT_NOT_NULL(brInsn2);
1188 // check fallthru BB
1189 if (!brInsn1->IsBranch() && brInsn2->IsBranch()) { // need merge backward
1190 dir = mergeDirection(dir, kDirectionBackward);
1191 } else if (brInsn1->IsBranch() && !brInsn2->IsBranch()) { // need merge forward
1192 dir = mergeDirection(dir, kDirectionForward);
1193 } else { // all is branch
1194 auto checkAllMatchAndIsJumpTarget = [](const BB &bb, const Insn &f) {
1195 if (&f != bb.GetFirstMachineInsn()) {
1196 return false;
1197 }
1198 for (auto *pred : bb.GetPreds()) {
1199 if (pred->GetNext() == &bb) {
1200 return false;
1201 }
1202 }
1203 return true;
1204 };
1205 bool c1 = checkAllMatchAndIsJumpTarget(bb1, f1);
1206 bool c2 = checkAllMatchAndIsJumpTarget(bb2, f2);
1207 // When a BB's all instructions match and is the jump target, after this optimization,
1208 // it will become a solo goto BB and is deleted in other optimizations.
1209 if (c1 && c2) {
1210 dir = mergeDirection(dir, kDirectionBoth);
1211 } else if (c1) {
1212 dir = mergeDirection(dir, kDirectionForward);
1213 } else if (c2) {
1214 dir = mergeDirection(dir, kDirectionBackward);
1215 } else if (!CGOptions::GetInstance().OptimizeForSize()) {
1216 // Two BBs are partially matched. If CrossJump optimization is performed, a jump
1217 // instruction is introduced. Therefore, when the optimization is not for size,
1218 // this optimization is not performed.
1219 dir = kDirectionNone;
1220 } else {
1221 dir = mergeDirection(dir, kDirectionBoth);
1222 }
1223 }
1224 }
1225
MergeMemInfo(BB & bb1,Insn & newpos1,BB & redirectBB)1226 void CrossJumpBBPattern::MergeMemInfo(BB &bb1, Insn &newpos1, BB &redirectBB)
1227 {
1228 CHECK_FATAL(newpos1.GetBB() == &bb1, "NIY, insn must in bb");
1229 auto *insn1 = &newpos1;
1230 auto *insn2 = redirectBB.GetFirstMachineInsn();
1231 while (insn1 != nullptr && insn2 != nullptr && !insn1->IsBranch() && !insn2->IsBranch()) {
1232 DEBUG_ASSERT(insn1->Equals(*insn2), "NIY, insn must equal");
1233 insn2->MergeReferenceOsts(*insn1);
1234 insn1 = insn1->GetNextMachineInsn();
1235 insn2 = insn2->GetNextMachineInsn();
1236 }
1237 }
1238
1239 // try cross jump opt
TryCrossJumpBB(BB & bb1,BB & bb2,MergeDirection dir)1240 bool CrossJumpBBPattern::TryCrossJumpBB(BB &bb1, BB &bb2, MergeDirection dir)
1241 {
1242 // if bb is solo goto, we need to get its actual precursor bb.
1243 auto skipSoloGotoBB = [](BB &bb) {
1244 if (bb.IsSoloGoto() && bb.GetPredsSize() == 1) {
1245 return bb.GetPreds().front();
1246 }
1247 return &bb;
1248 };
1249 auto *src1 = skipSoloGotoBB(bb1);
1250 auto *src2 = skipSoloGotoBB(bb2);
1251 if (src1 == cgFunc->GetFirstBB() || src2 == cgFunc->GetFirstBB() || src1 == src2) {
1252 return false;
1253 }
1254 if (src1->IsUnreachable() || src2->IsUnreachable()) {
1255 return false;
1256 }
1257
1258 if (!CheckBBSuccMatch(*src1, *src2)) {
1259 return false;
1260 }
1261
1262 Insn *newpos1 = nullptr; // position in src1 that will be split
1263 Insn *newpos2 = nullptr; // position in src2 that will be split
1264 auto nmatch = CheckBBInsnsMatch(*src1, *src2, newpos1, newpos2);
1265 if (nmatch == 0 && (newpos1 == nullptr || newpos1 != src1->GetFirstMachineInsn())) {
1266 return false;
1267 }
1268 GetMergeDirection(bb1, bb2, *newpos1, *newpos2, dir);
1269 if (dir == kDirectionNone) {
1270 return false;
1271 } else if (dir == kDirectionBackward) { // backward merge, swap them
1272 std::swap(src1, src2);
1273 std::swap(newpos1, newpos2);
1274 }
1275
1276 auto *redirectBB = src2;
1277 if (newpos2 != src2->GetFirstMachineInsn()) {
1278 redirectBB = &SplitBB(*src2, *newpos2->GetPreviousMachineInsn());
1279 }
1280 MergeMemInfo(*src1, *newpos1, *redirectBB);
1281 src1->RemoveInsnSequence(*newpos1, *src1->GetLastInsn());
1282 auto &brTarget = cgFunc->GetOrCreateLabelOperand(*redirectBB);
1283 auto &uncondInsn = cgFunc->GetInsnBuilder()->BuildInsn(GetUnCondBranchMOP(), brTarget);
1284 src1->AppendInsn(uncondInsn);
1285 src1->SetKind(BB::kBBGoto);
1286 for (auto *succ : src1->GetSuccs()) {
1287 succ->RemovePreds(*src1);
1288 }
1289 src1->ClearSuccs();
1290 src1->PushBackSuccs(*redirectBB);
1291 redirectBB->PushBackPreds(*src1);
1292
1293 return true;
1294 }
1295
OptimizeOnce(const BB & curBB)1296 bool CrossJumpBBPattern::OptimizeOnce(const BB &curBB)
1297 {
1298 // Merge otherBB to fallthruBB is beneficial in most case, as that adds no
1299 // branches to the program. We'll try that combination first.
1300 auto *fallthru = FindPredFallthruBB(curBB);
1301 for (auto it1 = curBB.GetPreds().begin(); it1 != curBB.GetPreds().end(); ++it1) {
1302 auto *pred = *it1;
1303 if (fallthru != nullptr) {
1304 if (pred == fallthru) {
1305 continue;
1306 }
1307
1308 if (TryCrossJumpBB(*pred, *fallthru, kDirectionForward)) {
1309 return true; // Cross jump opt may modify preds or fallthruBB, so we can't continue.
1310 }
1311 }
1312
1313 for (auto it2 = it1; it2 != curBB.GetPreds().end(); ++it2) {
1314 auto *pred2 = *it2;
1315 if (pred == pred2 || pred2 == fallthru) {
1316 continue;
1317 }
1318 if (TryCrossJumpBB(*pred, *pred2, kDirectionBoth)) {
1319 return true; // Cross jump opt may modify preds or fallthruBB, so we can't continue.
1320 }
1321 }
1322 }
1323 return false;
1324 }
1325
Optimize(BB & curBB)1326 bool CrossJumpBBPattern::Optimize(BB &curBB)
1327 {
1328 if (!cgFunc->IsAfterRegAlloc() || curBB.IsUnreachable()) {
1329 return false;
1330 }
1331 if (curBB.GetPredsSize() < kMinCrossJumpPreds || curBB.GetPredsSize() >= kMaxCrossJumpPreds) {
1332 return false;
1333 }
1334
1335 bool cfgChanged = false;
1336 bool optimized = false;
1337 do {
1338 cfgChanged = false;
1339 cfgChanged = OptimizeOnce(curBB) || cfgChanged;
1340 optimized = cfgChanged || optimized;
1341 } while (cfgChanged);
1342
1343 return optimized;
1344 }
1345
1346 /* === new pm === */
GetAnalysisDependence(AnalysisDep & aDep) const1347 void CgPreCfgo::GetAnalysisDependence(AnalysisDep &aDep) const
1348 {
1349 aDep.AddRequired<CgLoopAnalysis>();
1350 }
1351
PhaseRun(maplebe::CGFunc & f)1352 bool CgPreCfgo::PhaseRun(maplebe::CGFunc &f)
1353 {
1354 auto *loopInfo = GET_ANALYSIS(CgLoopAnalysis, f);
1355 CFGOptimizer *cfgOptimizer = f.GetCG()->CreateCFGOptimizer(*GetPhaseMemPool(), f, *loopInfo);
1356 DEBUG_ASSERT(cfgOptimizer != nullptr, "nullptr check");
1357 const std::string &funcClass = f.GetFunction().GetBaseClassName();
1358 const std::string &funcName = f.GetFunction().GetBaseFuncName();
1359 const std::string &name = funcClass + funcName;
1360 if (CFGO_DUMP_NEWPM) {
1361 DotGenerator::GenerateDot("before-precfgo", f, f.GetMirModule());
1362 }
1363 cfgOptimizer->Run(name);
1364 if (CFGO_DUMP_NEWPM) {
1365 f.GetTheCFG()->CheckCFG();
1366 DotGenerator::GenerateDot("after-precfgo", f, f.GetMirModule());
1367 }
1368 return false;
1369 }
MAPLE_TRANSFORM_PHASE_REGISTER_CANSKIP(CgPreCfgo,precfgo)1370 MAPLE_TRANSFORM_PHASE_REGISTER_CANSKIP(CgPreCfgo, precfgo)
1371
1372 void CgCfgo::GetAnalysisDependence(AnalysisDep &aDep) const
1373 {
1374 aDep.AddRequired<CgLoopAnalysis>();
1375 }
1376
PhaseRun(maplebe::CGFunc & f)1377 bool CgCfgo::PhaseRun(maplebe::CGFunc &f)
1378 {
1379 auto *loopInfo = GET_ANALYSIS(CgLoopAnalysis, f);
1380 CFGOptimizer *cfgOptimizer = f.GetCG()->CreateCFGOptimizer(*GetPhaseMemPool(), f, *loopInfo);
1381 DEBUG_ASSERT(cfgOptimizer != nullptr, "nullptr check");
1382 if (f.IsAfterRegAlloc()) {
1383 cfgOptimizer->SetPhase(kCfgoPostRegAlloc);
1384 }
1385 const std::string &funcClass = f.GetFunction().GetBaseClassName();
1386 const std::string &funcName = f.GetFunction().GetBaseFuncName();
1387 const std::string &name = funcClass + funcName;
1388 if (CFGO_DUMP_NEWPM) {
1389 DotGenerator::GenerateDot("before-cfgo", f, f.GetMirModule());
1390 }
1391 cfgOptimizer->Run(name);
1392 if (CFGO_DUMP_NEWPM) {
1393 f.GetTheCFG()->CheckCFG();
1394 DotGenerator::GenerateDot("after-cfgo", f, f.GetMirModule());
1395 }
1396 return false;
1397 }
MAPLE_TRANSFORM_PHASE_REGISTER_CANSKIP(CgCfgo,cfgo)1398 MAPLE_TRANSFORM_PHASE_REGISTER_CANSKIP(CgCfgo, cfgo)
1399
1400 void CgPostCfgo::GetAnalysisDependence(AnalysisDep &aDep) const
1401 {
1402 aDep.AddRequired<CgLoopAnalysis>();
1403 }
1404
PhaseRun(maplebe::CGFunc & f)1405 bool CgPostCfgo::PhaseRun(maplebe::CGFunc &f)
1406 {
1407 auto *loopInfo = GET_ANALYSIS(CgLoopAnalysis, f);
1408 CFGOptimizer *cfgOptimizer = f.GetCG()->CreateCFGOptimizer(*GetPhaseMemPool(), f, *loopInfo);
1409 DEBUG_ASSERT(cfgOptimizer != nullptr, "nullptr check");
1410 const std::string &funcClass = f.GetFunction().GetBaseClassName();
1411 const std::string &funcName = f.GetFunction().GetBaseFuncName();
1412 const std::string &name = funcClass + funcName;
1413 cfgOptimizer->SetPhase(kPostCfgo);
1414 if (CFGO_DUMP_NEWPM) {
1415 DotGenerator::GenerateDot("before-postcfgo", f, f.GetMirModule());
1416 }
1417 cfgOptimizer->Run(name);
1418 if (CFGO_DUMP_NEWPM) {
1419 DotGenerator::GenerateDot("after-postcfgo", f, f.GetMirModule());
1420 }
1421 return false;
1422 }
1423 MAPLE_TRANSFORM_PHASE_REGISTER_CANSKIP(CgPostCfgo, postcfgo)
1424 } /* namespace maplebe */
1425