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. 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 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