298 lines · cpp
1//===- MachineLoopInfo.cpp - Natural Loop Calculator ----------------------===//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// This file defines the MachineLoopInfo class that is used to identify natural10// loops and determine the loop depth of various nodes of the CFG. Note that11// the loops identified may actually be several natural loops that share the12// same header node... not just a single natural loop.13//14//===----------------------------------------------------------------------===//15 16#include "llvm/CodeGen/MachineLoopInfo.h"17#include "llvm/CodeGen/MachineDominators.h"18#include "llvm/CodeGen/MachineRegisterInfo.h"19#include "llvm/CodeGen/TargetInstrInfo.h"20#include "llvm/CodeGen/TargetSubtargetInfo.h"21#include "llvm/Config/llvm-config.h"22#include "llvm/InitializePasses.h"23#include "llvm/Pass.h"24#include "llvm/PassRegistry.h"25#include "llvm/Support/Compiler.h"26#include "llvm/Support/GenericLoopInfoImpl.h"27 28using namespace llvm;29 30// Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.31template class LLVM_EXPORT_TEMPLATE32 llvm::LoopBase<MachineBasicBlock, MachineLoop>;33template class LLVM_EXPORT_TEMPLATE34 llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;35 36AnalysisKey MachineLoopAnalysis::Key;37 38MachineLoopAnalysis::Result39MachineLoopAnalysis::run(MachineFunction &MF,40 MachineFunctionAnalysisManager &MFAM) {41 return MachineLoopInfo(MFAM.getResult<MachineDominatorTreeAnalysis>(MF));42}43 44PreservedAnalyses45MachineLoopPrinterPass::run(MachineFunction &MF,46 MachineFunctionAnalysisManager &MFAM) {47 OS << "Machine loop info for machine function '" << MF.getName() << "':\n";48 MFAM.getResult<MachineLoopAnalysis>(MF).print(OS);49 return PreservedAnalyses::all();50}51 52char MachineLoopInfoWrapperPass::ID = 0;53MachineLoopInfoWrapperPass::MachineLoopInfoWrapperPass()54 : MachineFunctionPass(ID) {55 initializeMachineLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());56}57INITIALIZE_PASS_BEGIN(MachineLoopInfoWrapperPass, "machine-loops",58 "Machine Natural Loop Construction", true, true)59INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)60INITIALIZE_PASS_END(MachineLoopInfoWrapperPass, "machine-loops",61 "Machine Natural Loop Construction", true, true)62 63char &llvm::MachineLoopInfoID = MachineLoopInfoWrapperPass::ID;64 65bool MachineLoopInfoWrapperPass::runOnMachineFunction(MachineFunction &) {66 LI.calculate(getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree());67 return false;68}69 70bool MachineLoopInfo::invalidate(71 MachineFunction &, const PreservedAnalyses &PA,72 MachineFunctionAnalysisManager::Invalidator &) {73 // Check whether the analysis, all analyses on functions, or the function's74 // CFG have been preserved.75 auto PAC = PA.getChecker<MachineLoopAnalysis>();76 return !PAC.preserved() &&77 !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() &&78 !PAC.preservedSet<CFGAnalyses>();79}80 81void MachineLoopInfo::calculate(MachineDominatorTree &MDT) {82 releaseMemory();83 analyze(MDT);84}85 86void MachineLoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {87 AU.setPreservesAll();88 AU.addRequired<MachineDominatorTreeWrapperPass>();89 MachineFunctionPass::getAnalysisUsage(AU);90}91 92MachineBasicBlock *MachineLoop::getTopBlock() {93 MachineBasicBlock *TopMBB = getHeader();94 MachineFunction::iterator Begin = TopMBB->getParent()->begin();95 if (TopMBB->getIterator() != Begin) {96 MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());97 while (contains(PriorMBB)) {98 TopMBB = PriorMBB;99 if (TopMBB->getIterator() == Begin)100 break;101 PriorMBB = &*std::prev(TopMBB->getIterator());102 }103 }104 return TopMBB;105}106 107MachineBasicBlock *MachineLoop::getBottomBlock() {108 MachineBasicBlock *BotMBB = getHeader();109 MachineFunction::iterator End = BotMBB->getParent()->end();110 if (BotMBB->getIterator() != std::prev(End)) {111 MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());112 while (contains(NextMBB)) {113 BotMBB = NextMBB;114 if (BotMBB == &*std::next(BotMBB->getIterator()))115 break;116 NextMBB = &*std::next(BotMBB->getIterator());117 }118 }119 return BotMBB;120}121 122MachineBasicBlock *MachineLoop::findLoopControlBlock() const {123 if (MachineBasicBlock *Latch = getLoopLatch()) {124 if (isLoopExiting(Latch))125 return Latch;126 else127 return getExitingBlock();128 }129 return nullptr;130}131 132DebugLoc MachineLoop::getStartLoc() const {133 // Try the pre-header first.134 if (MachineBasicBlock *PHeadMBB = getLoopPreheader())135 if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())136 if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())137 return DL;138 139 // If we have no pre-header or there are no instructions with debug140 // info in it, try the header.141 if (MachineBasicBlock *HeadMBB = getHeader())142 if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())143 return HeadBB->getTerminator()->getDebugLoc();144 145 return DebugLoc();146}147 148MachineBasicBlock *149MachineLoopInfo::findLoopPreheader(MachineLoop *L, bool SpeculativePreheader,150 bool FindMultiLoopPreheader) const {151 if (MachineBasicBlock *PB = L->getLoopPreheader())152 return PB;153 154 if (!SpeculativePreheader)155 return nullptr;156 157 MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();158 if (HB->pred_size() != 2 || HB->hasAddressTaken())159 return nullptr;160 // Find the predecessor of the header that is not the latch block.161 MachineBasicBlock *Preheader = nullptr;162 for (MachineBasicBlock *P : HB->predecessors()) {163 if (P == LB)164 continue;165 // Sanity.166 if (Preheader)167 return nullptr;168 Preheader = P;169 }170 171 // Check if the preheader candidate is a successor of any other loop172 // headers. We want to avoid having two loop setups in the same block.173 if (!FindMultiLoopPreheader) {174 for (MachineBasicBlock *S : Preheader->successors()) {175 if (S == HB)176 continue;177 MachineLoop *T = getLoopFor(S);178 if (T && T->getHeader() == S)179 return nullptr;180 }181 }182 return Preheader;183}184 185MDNode *MachineLoop::getLoopID() const {186 MDNode *LoopID = nullptr;187 188 // Go through the latch blocks and check the terminator for the metadata189 SmallVector<MachineBasicBlock *, 4> LatchesBlocks;190 getLoopLatches(LatchesBlocks);191 for (const auto *MBB : LatchesBlocks) {192 const auto *BB = MBB->getBasicBlock();193 if (!BB)194 return nullptr;195 const auto *TI = BB->getTerminator();196 if (!TI)197 return nullptr;198 199 MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);200 if (!MD)201 return nullptr;202 203 if (!LoopID)204 LoopID = MD;205 else if (MD != LoopID)206 return nullptr;207 }208 209 if (!LoopID || LoopID->getNumOperands() == 0 ||210 LoopID->getOperand(0) != LoopID)211 return nullptr;212 213 return LoopID;214}215 216bool MachineLoop::isLoopInvariantImplicitPhysReg(Register Reg) const {217 MachineFunction *MF = getHeader()->getParent();218 MachineRegisterInfo *MRI = &MF->getRegInfo();219 220 if (MRI->isConstantPhysReg(Reg))221 return true;222 223 if (!MF->getSubtarget()224 .getRegisterInfo()225 ->shouldAnalyzePhysregInMachineLoopInfo(Reg))226 return false;227 228 return !llvm::any_of(229 MRI->def_instructions(Reg),230 [this](const MachineInstr &MI) { return this->contains(&MI); });231}232 233bool MachineLoop::isLoopInvariant(MachineInstr &I,234 const Register ExcludeReg) const {235 MachineFunction *MF = I.getParent()->getParent();236 MachineRegisterInfo *MRI = &MF->getRegInfo();237 const TargetSubtargetInfo &ST = MF->getSubtarget();238 const TargetRegisterInfo *TRI = ST.getRegisterInfo();239 const TargetInstrInfo *TII = ST.getInstrInfo();240 241 // The instruction is loop invariant if all of its operands are.242 for (const MachineOperand &MO : I.operands()) {243 if (!MO.isReg())244 continue;245 246 Register Reg = MO.getReg();247 if (Reg == 0) continue;248 249 if (ExcludeReg == Reg)250 continue;251 252 // An instruction that uses or defines a physical register can't e.g. be253 // hoisted, so mark this as not invariant.254 if (Reg.isPhysical()) {255 if (MO.isUse()) {256 // If the physreg has no defs anywhere, it's just an ambient register257 // and we can freely move its uses. Alternatively, if it's allocatable,258 // it could get allocated to something with a def during allocation.259 // However, if the physreg is known to always be caller saved/restored260 // then this use is safe to hoist.261 if (!isLoopInvariantImplicitPhysReg(Reg) &&262 !(TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *I.getMF())) &&263 !TII->isIgnorableUse(MO))264 return false;265 // Otherwise it's safe to move.266 continue;267 } else if (!MO.isDead()) {268 // A def that isn't dead can't be moved.269 return false;270 } else if (getHeader()->isLiveIn(Reg)) {271 // If the reg is live into the loop, we can't hoist an instruction272 // which would clobber it.273 return false;274 }275 }276 277 if (!MO.readsReg())278 continue;279 280 assert(MRI->getVRegDef(Reg) &&281 "Machine instr not mapped for this vreg?!");282 283 // If the loop contains the definition of an operand, then the instruction284 // isn't loop invariant.285 if (contains(MRI->getVRegDef(Reg)))286 return false;287 }288 289 // If we got this far, the instruction is loop invariant!290 return true;291}292 293#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)294LLVM_DUMP_METHOD void MachineLoop::dump() const {295 print(dbgs());296}297#endif298