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 // 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 135 bool 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