1//=- MachineLoopUtils.cpp - Functions for manipulating loops ----------------=//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "llvm/CodeGen/MachineLoopUtils.h"
10#include "llvm/CodeGen/MachineBasicBlock.h"
11#include "llvm/CodeGen/MachineDomTreeUpdater.h"
12#include "llvm/CodeGen/MachineRegisterInfo.h"
13#include "llvm/CodeGen/TargetInstrInfo.h"
14#include <iterator>
15using namespace llvm;
16
17namespace {
18// MI's parent and BB are clones of each other. Find the equivalent copy of MI
19// in BB.
20MachineInstr &findEquivalentInstruction(MachineInstr &MI,
21 MachineBasicBlock *BB) {
22 MachineBasicBlock *PB = MI.getParent();
23 unsigned Offset = std::distance(first: PB->instr_begin(), last: MachineBasicBlock::instr_iterator(MI));
24 return *std::next(x: BB->instr_begin(), n: Offset);
25}
26} // namespace
27
28MachineBasicBlock *llvm::PeelSingleBlockLoop(LoopPeelDirection Direction,
29 MachineBasicBlock *Loop,
30 MachineRegisterInfo &MRI,
31 const TargetInstrInfo *TII,
32 MachineDomTreeUpdater *MDTU) {
33 MachineFunction &MF = *Loop->getParent();
34 MachineBasicBlock *Preheader = *Loop->pred_begin();
35 if (Preheader == Loop)
36 Preheader = *std::next(x: Loop->pred_begin());
37 MachineBasicBlock *Exit = *Loop->succ_begin();
38 if (Exit == Loop)
39 Exit = *std::next(x: Loop->succ_begin());
40
41 MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB: Loop->getBasicBlock());
42 if (Direction == LPD_Front)
43 MF.insert(MBBI: Loop->getIterator(), MBB: NewBB);
44 else
45 MF.insert(MBBI: std::next(x: Loop->getIterator()), MBB: NewBB);
46
47 DenseMap<Register, Register> Remaps;
48 auto InsertPt = NewBB->end();
49 for (MachineInstr &MI : *Loop) {
50 MachineInstr *NewMI = MF.CloneMachineInstr(Orig: &MI);
51 NewBB->insert(I: InsertPt, MI: NewMI);
52 for (MachineOperand &MO : NewMI->defs()) {
53 Register OrigR = MO.getReg();
54 if (OrigR.isPhysical())
55 continue;
56 Register &R = Remaps[OrigR];
57 R = MRI.createVirtualRegister(RegClass: MRI.getRegClass(Reg: OrigR));
58 MO.setReg(R);
59
60 if (Direction == LPD_Back) {
61 // Replace all uses outside the original loop with the new register.
62 // FIXME: is the use_iterator stable enough to mutate register uses
63 // while iterating?
64 SmallVector<MachineOperand *, 4> Uses;
65 for (auto &Use : MRI.use_operands(Reg: OrigR))
66 if (Use.getParent()->getParent() != Loop)
67 Uses.push_back(Elt: &Use);
68 for (auto *Use : Uses) {
69 const TargetRegisterClass *ConstrainRegClass =
70 MRI.constrainRegClass(Reg: R, RC: MRI.getRegClass(Reg: Use->getReg()));
71 assert(ConstrainRegClass &&
72 "Expected a valid constrained register class!");
73 (void)ConstrainRegClass;
74 Use->setReg(R);
75 }
76 }
77 }
78 }
79
80 for (auto I = NewBB->getFirstNonPHI(); I != NewBB->end(); ++I)
81 for (MachineOperand &MO : I->uses())
82 if (MO.isReg())
83 if (auto It = Remaps.find(Val: MO.getReg()); It != Remaps.end())
84 MO.setReg(It->second);
85
86 for (auto I = NewBB->begin(); I->isPHI(); ++I) {
87 MachineInstr &MI = *I;
88 unsigned LoopRegIdx = 3, InitRegIdx = 1;
89 if (MI.getOperand(i: 2).getMBB() != Preheader)
90 std::swap(a&: LoopRegIdx, b&: InitRegIdx);
91 MachineInstr &OrigPhi = findEquivalentInstruction(MI, BB: Loop);
92 assert(OrigPhi.isPHI());
93 if (Direction == LPD_Front) {
94 // When peeling front, we are only left with the initial value from the
95 // preheader.
96 Register R = MI.getOperand(i: LoopRegIdx).getReg();
97 if (auto It = Remaps.find(Val: R); It != Remaps.end())
98 R = It->second;
99 OrigPhi.getOperand(i: InitRegIdx).setReg(R);
100 MI.removeOperand(OpNo: LoopRegIdx + 1);
101 MI.removeOperand(OpNo: LoopRegIdx + 0);
102 } else {
103 // When peeling back, the initial value is the loop-carried value from
104 // the original loop.
105 Register LoopReg = OrigPhi.getOperand(i: LoopRegIdx).getReg();
106 MI.getOperand(i: LoopRegIdx).setReg(LoopReg);
107 MI.removeOperand(OpNo: InitRegIdx + 1);
108 MI.removeOperand(OpNo: InitRegIdx + 0);
109 }
110 }
111
112 DebugLoc DL;
113 if (Direction == LPD_Front) {
114 Preheader->ReplaceUsesOfBlockWith(Old: Loop, New: NewBB);
115 NewBB->addSuccessor(Succ: Loop);
116 if (MDTU)
117 MDTU->splitCriticalEdge(FromBB: Preheader, ToBB: Loop, NewBB);
118 Loop->replacePhiUsesWith(Old: Preheader, New: NewBB);
119 if (auto PreheaderLayoutSuccessor = std::next(x: Preheader->getIterator());
120 PreheaderLayoutSuccessor != Preheader->getParent()->end())
121 Preheader->updateTerminator(PreviousLayoutSuccessor: &*PreheaderLayoutSuccessor);
122 TII->removeBranch(MBB&: *NewBB);
123 TII->insertBranch(MBB&: *NewBB, TBB: Loop, FBB: nullptr, Cond: {}, DL);
124 } else {
125 Loop->replaceSuccessor(Old: Exit, New: NewBB);
126 Exit->replacePhiUsesWith(Old: Loop, New: NewBB);
127 NewBB->addSuccessor(Succ: Exit);
128 if (MDTU)
129 MDTU->splitCriticalEdge(FromBB: Loop, ToBB: Exit, NewBB);
130
131 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
132 SmallVector<MachineOperand, 4> Cond;
133 bool CanAnalyzeBr = !TII->analyzeBranch(MBB&: *Loop, TBB, FBB, Cond);
134 (void)CanAnalyzeBr;
135 assert(CanAnalyzeBr && "Must be able to analyze the loop branch!");
136 TII->removeBranch(MBB&: *Loop);
137 TII->insertBranch(MBB&: *Loop, TBB: TBB == Exit ? NewBB : TBB,
138 FBB: FBB == Exit ? NewBB : FBB, Cond, DL);
139 if (TII->removeBranch(MBB&: *NewBB) > 0)
140 TII->insertBranch(MBB&: *NewBB, TBB: Exit, FBB: nullptr, Cond: {}, DL);
141 }
142
143 return NewBB;
144}
145