133 lines
4.9 KiB
C++
133 lines
4.9 KiB
C++
//=- MachineLoopUtils.cpp - Functions for manipulating loops ----------------=//
|
|
//
|
|
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
// See https://llvm.org/LICENSE.txt for license information.
|
|
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#include "llvm/CodeGen/MachineLoopInfo.h"
|
|
#include "llvm/CodeGen/MachineLoopUtils.h"
|
|
#include "llvm/CodeGen/MachineBasicBlock.h"
|
|
#include "llvm/CodeGen/MachineRegisterInfo.h"
|
|
#include "llvm/CodeGen/TargetInstrInfo.h"
|
|
using namespace llvm;
|
|
|
|
namespace {
|
|
// MI's parent and BB are clones of each other. Find the equivalent copy of MI
|
|
// in BB.
|
|
MachineInstr &findEquivalentInstruction(MachineInstr &MI,
|
|
MachineBasicBlock *BB) {
|
|
MachineBasicBlock *PB = MI.getParent();
|
|
unsigned Offset = std::distance(PB->instr_begin(), MachineBasicBlock::instr_iterator(MI));
|
|
return *std::next(BB->instr_begin(), Offset);
|
|
}
|
|
} // namespace
|
|
|
|
MachineBasicBlock *llvm::PeelSingleBlockLoop(LoopPeelDirection Direction,
|
|
MachineBasicBlock *Loop,
|
|
MachineRegisterInfo &MRI,
|
|
const TargetInstrInfo *TII) {
|
|
MachineFunction &MF = *Loop->getParent();
|
|
MachineBasicBlock *Preheader = *Loop->pred_begin();
|
|
if (Preheader == Loop)
|
|
Preheader = *std::next(Loop->pred_begin());
|
|
MachineBasicBlock *Exit = *Loop->succ_begin();
|
|
if (Exit == Loop)
|
|
Exit = *std::next(Loop->succ_begin());
|
|
|
|
MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(Loop->getBasicBlock());
|
|
if (Direction == LPD_Front)
|
|
MF.insert(Loop->getIterator(), NewBB);
|
|
else
|
|
MF.insert(std::next(Loop->getIterator()), NewBB);
|
|
|
|
DenseMap<Register, Register> Remaps;
|
|
auto InsertPt = NewBB->end();
|
|
for (MachineInstr &MI : *Loop) {
|
|
MachineInstr *NewMI = MF.CloneMachineInstr(&MI);
|
|
NewBB->insert(InsertPt, NewMI);
|
|
for (MachineOperand &MO : NewMI->defs()) {
|
|
Register OrigR = MO.getReg();
|
|
if (OrigR.isPhysical())
|
|
continue;
|
|
Register &R = Remaps[OrigR];
|
|
R = MRI.createVirtualRegister(MRI.getRegClass(OrigR));
|
|
MO.setReg(R);
|
|
|
|
if (Direction == LPD_Back) {
|
|
// Replace all uses outside the original loop with the new register.
|
|
// FIXME: is the use_iterator stable enough to mutate register uses
|
|
// while iterating?
|
|
SmallVector<MachineOperand *, 4> Uses;
|
|
for (auto &Use : MRI.use_operands(OrigR))
|
|
if (Use.getParent()->getParent() != Loop)
|
|
Uses.push_back(&Use);
|
|
for (auto *Use : Uses) {
|
|
MRI.constrainRegClass(R, MRI.getRegClass(Use->getReg()));
|
|
Use->setReg(R);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
for (auto I = NewBB->getFirstNonPHI(); I != NewBB->end(); ++I)
|
|
for (MachineOperand &MO : I->uses())
|
|
if (MO.isReg() && Remaps.count(MO.getReg()))
|
|
MO.setReg(Remaps[MO.getReg()]);
|
|
|
|
for (auto I = NewBB->begin(); I->isPHI(); ++I) {
|
|
MachineInstr &MI = *I;
|
|
unsigned LoopRegIdx = 3, InitRegIdx = 1;
|
|
if (MI.getOperand(2).getMBB() != Preheader)
|
|
std::swap(LoopRegIdx, InitRegIdx);
|
|
MachineInstr &OrigPhi = findEquivalentInstruction(MI, Loop);
|
|
assert(OrigPhi.isPHI());
|
|
if (Direction == LPD_Front) {
|
|
// When peeling front, we are only left with the initial value from the
|
|
// preheader.
|
|
Register R = MI.getOperand(LoopRegIdx).getReg();
|
|
if (Remaps.count(R))
|
|
R = Remaps[R];
|
|
OrigPhi.getOperand(InitRegIdx).setReg(R);
|
|
MI.RemoveOperand(LoopRegIdx + 1);
|
|
MI.RemoveOperand(LoopRegIdx + 0);
|
|
} else {
|
|
// When peeling back, the initial value is the loop-carried value from
|
|
// the original loop.
|
|
Register LoopReg = OrigPhi.getOperand(LoopRegIdx).getReg();
|
|
MI.getOperand(LoopRegIdx).setReg(LoopReg);
|
|
MI.RemoveOperand(InitRegIdx + 1);
|
|
MI.RemoveOperand(InitRegIdx + 0);
|
|
}
|
|
}
|
|
|
|
DebugLoc DL;
|
|
if (Direction == LPD_Front) {
|
|
Preheader->replaceSuccessor(Loop, NewBB);
|
|
NewBB->addSuccessor(Loop);
|
|
Loop->replacePhiUsesWith(Preheader, NewBB);
|
|
if (TII->removeBranch(*Preheader) > 0)
|
|
TII->insertBranch(*Preheader, NewBB, nullptr, {}, DL);
|
|
TII->removeBranch(*NewBB);
|
|
TII->insertBranch(*NewBB, Loop, nullptr, {}, DL);
|
|
} else {
|
|
Loop->replaceSuccessor(Exit, NewBB);
|
|
Exit->replacePhiUsesWith(Loop, NewBB);
|
|
NewBB->addSuccessor(Exit);
|
|
|
|
MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
|
|
SmallVector<MachineOperand, 4> Cond;
|
|
bool CanAnalyzeBr = !TII->analyzeBranch(*Loop, TBB, FBB, Cond);
|
|
(void)CanAnalyzeBr;
|
|
assert(CanAnalyzeBr && "Must be able to analyze the loop branch!");
|
|
TII->removeBranch(*Loop);
|
|
TII->insertBranch(*Loop, TBB == Exit ? NewBB : TBB,
|
|
FBB == Exit ? NewBB : FBB, Cond, DL);
|
|
if (TII->removeBranch(*NewBB) > 0)
|
|
TII->insertBranch(*NewBB, Exit, nullptr, {}, DL);
|
|
}
|
|
|
|
return NewBB;
|
|
}
|