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   DenseMap<Register, Register> Remaps;
46   auto InsertPt = NewBB->end();
47   for (MachineInstr &MI : *Loop) {
48     MachineInstr *NewMI = MF.CloneMachineInstr(&MI);
49     NewBB->insert(InsertPt, NewMI);
50     for (MachineOperand &MO : NewMI->defs()) {
51       Register OrigR = MO.getReg();
52       if (OrigR.isPhysical())
53         continue;
54       Register &R = Remaps[OrigR];
55       R = MRI.createVirtualRegister(MRI.getRegClass(OrigR));
56       MO.setReg(R);
57 
58       if (Direction == LPD_Back) {
59         // Replace all uses outside the original loop with the new register.
60         // FIXME: is the use_iterator stable enough to mutate register uses
61         // while iterating?
62         SmallVector<MachineOperand *, 4> Uses;
63         for (auto &Use : MRI.use_operands(OrigR))
64           if (Use.getParent()->getParent() != Loop)
65             Uses.push_back(&Use);
66         for (auto *Use : Uses) {
67           MRI.constrainRegClass(R, MRI.getRegClass(Use->getReg()));
68           Use->setReg(R);
69         }
70       }
71     }
72   }
73 
74   for (auto I = NewBB->getFirstNonPHI(); I != NewBB->end(); ++I)
75     for (MachineOperand &MO : I->uses())
76       if (MO.isReg() && Remaps.count(MO.getReg()))
77         MO.setReg(Remaps[MO.getReg()]);
78 
79   for (auto I = NewBB->begin(); I->isPHI(); ++I) {
80     MachineInstr &MI = *I;
81     unsigned LoopRegIdx = 3, InitRegIdx = 1;
82     if (MI.getOperand(2).getMBB() != Preheader)
83       std::swap(LoopRegIdx, InitRegIdx);
84     MachineInstr &OrigPhi = findEquivalentInstruction(MI, Loop);
85     assert(OrigPhi.isPHI());
86     if (Direction == LPD_Front) {
87       // When peeling front, we are only left with the initial value from the
88       // preheader.
89       Register R = MI.getOperand(LoopRegIdx).getReg();
90       if (Remaps.count(R))
91         R = Remaps[R];
92       OrigPhi.getOperand(InitRegIdx).setReg(R);
93       MI.RemoveOperand(LoopRegIdx + 1);
94       MI.RemoveOperand(LoopRegIdx + 0);
95     } else {
96       // When peeling back, the initial value is the loop-carried value from
97       // the original loop.
98       Register LoopReg = OrigPhi.getOperand(LoopRegIdx).getReg();
99       MI.getOperand(LoopRegIdx).setReg(LoopReg);
100       MI.RemoveOperand(InitRegIdx + 1);
101       MI.RemoveOperand(InitRegIdx + 0);
102     }
103   }
104 
105   DebugLoc DL;
106   if (Direction == LPD_Front) {
107     Preheader->replaceSuccessor(Loop, NewBB);
108     NewBB->addSuccessor(Loop);
109     Loop->replacePhiUsesWith(Preheader, NewBB);
110     if (TII->removeBranch(*Preheader) > 0)
111       TII->insertBranch(*Preheader, NewBB, nullptr, {}, DL);
112     TII->removeBranch(*NewBB);
113     TII->insertBranch(*NewBB, Loop, nullptr, {}, DL);
114   } else {
115     Loop->replaceSuccessor(Exit, NewBB);
116     Exit->replacePhiUsesWith(Loop, NewBB);
117     NewBB->addSuccessor(Exit);
118 
119     MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
120     SmallVector<MachineOperand, 4> Cond;
121     bool CanAnalyzeBr = !TII->analyzeBranch(*Loop, TBB, FBB, Cond);
122     (void)CanAnalyzeBr;
123     assert(CanAnalyzeBr && "Must be able to analyze the loop branch!");
124     TII->removeBranch(*Loop);
125     TII->insertBranch(*Loop, TBB == Exit ? NewBB : TBB,
126                       FBB == Exit ? NewBB : FBB, Cond, DL);
127     if (TII->removeBranch(*NewBB) > 0)
128       TII->insertBranch(*NewBB, Exit, nullptr, {}, DL);
129   }
130 
131   return NewBB;
132 }
133 
isRegLiveInExitBlocks(MachineLoop * Loop,int PhysReg)134 bool llvm::isRegLiveInExitBlocks(MachineLoop *Loop, int PhysReg) {
135   SmallVector<MachineBasicBlock *, 4> ExitBlocks;
136   Loop->getExitBlocks(ExitBlocks);
137 
138   for (auto *MBB : ExitBlocks)
139     if (MBB->isLiveIn(PhysReg))
140       return true;
141 
142   return false;
143 }
144