136 lines · cpp
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-exception6//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"13using namespace llvm;14 15namespace {16// MI's parent and BB are clones of each other. Find the equivalent copy of MI17// in BB.18MachineInstr &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} // namespace25 26MachineBasicBlock *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 else42 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 uses60 // 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 the92 // 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 from101 // 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