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