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"
13 using namespace llvm;
14
15 namespace {
16 // MI's parent and BB are clones of each other. Find the equivalent copy of MI
17 // in BB.
findEquivalentInstruction(MachineInstr & MI,MachineBasicBlock * BB)18 MachineInstr &findEquivalentInstruction(MachineInstr &MI,
19 MachineBasicBlock *BB) {
20 MachineBasicBlock *PB = MI.getParent();
21 unsigned Offset = std::distance(PB->instr_begin(), MachineBasicBlock::instr_iterator(MI));
22 return *std::next(BB->instr_begin(), Offset);
23 }
24 } // namespace
25
PeelSingleBlockLoop(LoopPeelDirection Direction,MachineBasicBlock * Loop,MachineRegisterInfo & MRI,const TargetInstrInfo * TII)26 MachineBasicBlock *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(Loop->pred_begin());
34 MachineBasicBlock *Exit = *Loop->succ_begin();
35 if (Exit == Loop)
36 Exit = *std::next(Loop->succ_begin());
37
38 MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(Loop->getBasicBlock());
39 if (Direction == LPD_Front)
40 MF.insert(Loop->getIterator(), NewBB);
41 else
42 MF.insert(std::next(Loop->getIterator()), NewBB);
43
44 DenseMap<Register, Register> Remaps;
45 auto InsertPt = NewBB->end();
46 for (MachineInstr &MI : *Loop) {
47 MachineInstr *NewMI = MF.CloneMachineInstr(&MI);
48 NewBB->insert(InsertPt, 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(MRI.getRegClass(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(OrigR))
63 if (Use.getParent()->getParent() != Loop)
64 Uses.push_back(&Use);
65 for (auto *Use : Uses) {
66 const TargetRegisterClass *ConstrainRegClass =
67 MRI.constrainRegClass(R, MRI.getRegClass(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())
80 if (auto It = Remaps.find(MO.getReg()); It != Remaps.end())
81 MO.setReg(It->second);
82
83 for (auto I = NewBB->begin(); I->isPHI(); ++I) {
84 MachineInstr &MI = *I;
85 unsigned LoopRegIdx = 3, InitRegIdx = 1;
86 if (MI.getOperand(2).getMBB() != Preheader)
87 std::swap(LoopRegIdx, InitRegIdx);
88 MachineInstr &OrigPhi = findEquivalentInstruction(MI, Loop);
89 assert(OrigPhi.isPHI());
90 if (Direction == LPD_Front) {
91 // When peeling front, we are only left with the initial value from the
92 // preheader.
93 Register R = MI.getOperand(LoopRegIdx).getReg();
94 if (auto It = Remaps.find(R); It != Remaps.end())
95 R = It->second;
96 OrigPhi.getOperand(InitRegIdx).setReg(R);
97 MI.removeOperand(LoopRegIdx + 1);
98 MI.removeOperand(LoopRegIdx + 0);
99 } else {
100 // When peeling back, the initial value is the loop-carried value from
101 // the original loop.
102 Register LoopReg = OrigPhi.getOperand(LoopRegIdx).getReg();
103 MI.getOperand(LoopRegIdx).setReg(LoopReg);
104 MI.removeOperand(InitRegIdx + 1);
105 MI.removeOperand(InitRegIdx + 0);
106 }
107 }
108
109 DebugLoc DL;
110 if (Direction == LPD_Front) {
111 Preheader->ReplaceUsesOfBlockWith(Loop, NewBB);
112 NewBB->addSuccessor(Loop);
113 Loop->replacePhiUsesWith(Preheader, NewBB);
114 Preheader->updateTerminator(Loop);
115 TII->removeBranch(*NewBB);
116 TII->insertBranch(*NewBB, Loop, nullptr, {}, DL);
117 } else {
118 Loop->replaceSuccessor(Exit, NewBB);
119 Exit->replacePhiUsesWith(Loop, NewBB);
120 NewBB->addSuccessor(Exit);
121
122 MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
123 SmallVector<MachineOperand, 4> Cond;
124 bool CanAnalyzeBr = !TII->analyzeBranch(*Loop, TBB, FBB, Cond);
125 (void)CanAnalyzeBr;
126 assert(CanAnalyzeBr && "Must be able to analyze the loop branch!");
127 TII->removeBranch(*Loop);
128 TII->insertBranch(*Loop, TBB == Exit ? NewBB : TBB,
129 FBB == Exit ? NewBB : FBB, Cond, DL);
130 if (TII->removeBranch(*NewBB) > 0)
131 TII->insertBranch(*NewBB, Exit, nullptr, {}, DL);
132 }
133
134 return NewBB;
135 }
136