MachineLoopInfo.cpp revision 360784
1118611Snjl//===- MachineLoopInfo.cpp - Natural Loop Calculator ----------------------===// 2118611Snjl// 3118611Snjl// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4118611Snjl// See https://llvm.org/LICENSE.txt for license information. 5118611Snjl// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6118611Snjl// 7217365Sjkim//===----------------------------------------------------------------------===// 8245582Sjkim// 9118611Snjl// This file defines the MachineLoopInfo class that is used to identify natural 10118611Snjl// loops and determine the loop depth of various nodes of the CFG. Note that 11217365Sjkim// the loops identified may actually be several natural loops that share the 12217365Sjkim// same header node... not just a single natural loop. 13217365Sjkim// 14217365Sjkim//===----------------------------------------------------------------------===// 15217365Sjkim 16217365Sjkim#include "llvm/CodeGen/MachineLoopInfo.h" 17217365Sjkim#include "llvm/Analysis/LoopInfoImpl.h" 18217365Sjkim#include "llvm/CodeGen/MachineDominators.h" 19217365Sjkim#include "llvm/CodeGen/Passes.h" 20217365Sjkim#include "llvm/Config/llvm-config.h" 21217365Sjkim#include "llvm/InitializePasses.h" 22217365Sjkim#include "llvm/Support/Debug.h" 23217365Sjkim#include "llvm/Support/raw_ostream.h" 24217365Sjkimusing namespace llvm; 25118611Snjl 26217365Sjkim// Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops. 27217365Sjkimtemplate class llvm::LoopBase<MachineBasicBlock, MachineLoop>; 28217365Sjkimtemplate class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>; 29118611Snjl 30217365Sjkimchar MachineLoopInfo::ID = 0; 31217365SjkimMachineLoopInfo::MachineLoopInfo() : MachineFunctionPass(ID) { 32217365Sjkim initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); 33217365Sjkim} 34217365SjkimINITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops", 35217365Sjkim "Machine Natural Loop Construction", true, true) 36217365SjkimINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 37217365SjkimINITIALIZE_PASS_END(MachineLoopInfo, "machine-loops", 38217365Sjkim "Machine Natural Loop Construction", true, true) 39217365Sjkim 40217365Sjkimchar &llvm::MachineLoopInfoID = MachineLoopInfo::ID; 41217365Sjkim 42217365Sjkimbool MachineLoopInfo::runOnMachineFunction(MachineFunction &) { 43118611Snjl calculate(getAnalysis<MachineDominatorTree>()); 44118611Snjl return false; 45151937Sjkim} 46118611Snjl 47209746Sjkimvoid MachineLoopInfo::calculate(MachineDominatorTree &MDT) { 48193529Sjkim releaseMemory(); 49193529Sjkim LI.analyze(MDT.getBase()); 50213806Sjkim} 51118611Snjl 52118611Snjlvoid MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { 53118611Snjl AU.setPreservesAll(); 54118611Snjl AU.addRequired<MachineDominatorTree>(); 55228110Sjkim MachineFunctionPass::getAnalysisUsage(AU); 56151937Sjkim} 57118611Snjl 58151937SjkimMachineBasicBlock *MachineLoop::getTopBlock() { 59151937Sjkim MachineBasicBlock *TopMBB = getHeader(); 60151937Sjkim MachineFunction::iterator Begin = TopMBB->getParent()->begin(); 61151937Sjkim if (TopMBB->getIterator() != Begin) { 62118611Snjl MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator()); 63151937Sjkim while (contains(PriorMBB)) { 64151937Sjkim TopMBB = PriorMBB; 65151937Sjkim if (TopMBB->getIterator() == Begin) 66151937Sjkim break; 67151937Sjkim PriorMBB = &*std::prev(TopMBB->getIterator()); 68151937Sjkim } 69118611Snjl } 70118611Snjl return TopMBB; 71209746Sjkim} 72209746Sjkim 73209746SjkimMachineBasicBlock *MachineLoop::getBottomBlock() { 74209746Sjkim MachineBasicBlock *BotMBB = getHeader(); 75209746Sjkim MachineFunction::iterator End = BotMBB->getParent()->end(); 76209746Sjkim if (BotMBB->getIterator() != std::prev(End)) { 77209746Sjkim MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator()); 78209746Sjkim while (contains(NextMBB)) { 79209746Sjkim BotMBB = NextMBB; 80209746Sjkim if (BotMBB == &*std::next(BotMBB->getIterator())) 81239340Sjkim break; 82239340Sjkim NextMBB = &*std::next(BotMBB->getIterator()); 83209746Sjkim } 84209746Sjkim } 85209746Sjkim return BotMBB; 86209746Sjkim} 87209746Sjkim 88239340SjkimMachineBasicBlock *MachineLoop::findLoopControlBlock() { 89209746Sjkim if (MachineBasicBlock *Latch = getLoopLatch()) { 90209746Sjkim if (isLoopExiting(Latch)) 91239340Sjkim return Latch; 92239340Sjkim else 93239340Sjkim return getExitingBlock(); 94209746Sjkim } 95209746Sjkim return nullptr; 96209746Sjkim} 97239340Sjkim 98239340SjkimDebugLoc MachineLoop::getStartLoc() const { 99239340Sjkim // Try the pre-header first. 100239340Sjkim if (MachineBasicBlock *PHeadMBB = getLoopPreheader()) 101239340Sjkim if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock()) 102209746Sjkim if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc()) 103209746Sjkim return DL; 104209746Sjkim 105239340Sjkim // If we have no pre-header or there are no instructions with debug 106239340Sjkim // info in it, try the header. 107209746Sjkim if (MachineBasicBlock *HeadMBB = getHeader()) 108239340Sjkim if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock()) 109209746Sjkim return HeadBB->getTerminator()->getDebugLoc(); 110209746Sjkim 111209746Sjkim return DebugLoc(); 112209746Sjkim} 113209746Sjkim 114209746SjkimMachineBasicBlock * 115237412SjkimMachineLoopInfo::findLoopPreheader(MachineLoop *L, 116118611Snjl bool SpeculativePreheader) const { 117118611Snjl if (MachineBasicBlock *PB = L->getLoopPreheader()) 118118611Snjl return PB; 119118611Snjl 120118611Snjl if (!SpeculativePreheader) 121118611Snjl return nullptr; 122118611Snjl 123118611Snjl MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch(); 124118611Snjl if (HB->pred_size() != 2 || HB->hasAddressTaken()) 125118611Snjl return nullptr; 126118611Snjl // Find the predecessor of the header that is not the latch block. 127118611Snjl MachineBasicBlock *Preheader = nullptr; 128118611Snjl for (MachineBasicBlock *P : HB->predecessors()) { 129167802Sjkim if (P == LB) 130118611Snjl continue; 131151937Sjkim // Sanity. 132118611Snjl if (Preheader) 133118611Snjl return nullptr; 134118611Snjl Preheader = P; 135118611Snjl } 136118611Snjl 137118611Snjl // Check if the preheader candidate is a successor of any other loop 138118611Snjl // headers. We want to avoid having two loop setups in the same block. 139118611Snjl for (MachineBasicBlock *S : Preheader->successors()) { 140118611Snjl if (S == HB) 141118611Snjl continue; 142118611Snjl MachineLoop *T = getLoopFor(S); 143118611Snjl if (T && T->getHeader() == S) 144118611Snjl return nullptr; 145118611Snjl } 146118611Snjl return Preheader; 147118611Snjl} 148237412Sjkim 149118611Snjl#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 150237412SjkimLLVM_DUMP_METHOD void MachineLoop::dump() const { 151118611Snjl print(dbgs()); 152237412Sjkim} 153118611Snjl#endif 154118611Snjl