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"
14using namespace llvm;
15
16namespace {
17// MI's parent and BB are clones of each other. Find the equivalent copy of MI
18// in BB.
19MachineInstr &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
27MachineBasicBlock *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
135bool 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