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