1e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson//===- MachineLoopInfo.cpp - Natural Loop Calculator ----------------------===// 2e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 3e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// The LLVM Compiler Infrastructure 4e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 8e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson//===----------------------------------------------------------------------===// 9e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 10e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// This file defines the MachineLoopInfo class that is used to identify natural 11e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// loops and determine the loop depth of various nodes of the CFG. Note that 12cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// the loops identified may actually be several natural loops that share the 13e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// same header node... not just a single natural loop. 14e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson// 15e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson//===----------------------------------------------------------------------===// 16e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 17e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson#include "llvm/CodeGen/MachineLoopInfo.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Analysis/LoopInfoImpl.h" 19e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson#include "llvm/CodeGen/MachineDominators.h" 2067d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling#include "llvm/CodeGen/Passes.h" 21dda30cd4af1c5f88fc00fd40b673f8e27c61379dDan Gohman#include "llvm/Support/Debug.h" 22e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Andersonusing namespace llvm; 23e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 24cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Trick// Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops. 25cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate class llvm::LoopBase<MachineBasicBlock, MachineLoop>; 26cbf24b4e58c2f621f480883c5bb1f2f2b2b8d497Andrew Tricktemplate class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>; 27e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 2819033bf7f8306131169e532c97e3ee4b745db221Chris Lattnerchar MachineLoopInfo::ID = 0; 292ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops", 302ab36d350293c77fc8941ce1023e4899df7e3a82Owen Anderson "Machine Natural Loop Construction", true, true) 312ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) 322ab36d350293c77fc8941ce1023e4899df7e3a82Owen AndersonINITIALIZE_PASS_END(MachineLoopInfo, "machine-loops", 33ce665bd2e2b581ab0858d1afe359192bac96b868Owen Anderson "Machine Natural Loop Construction", true, true) 3467d65bb69d5cad957cbb6d672dc0b4a19c211a42Bill Wendling 3590c579de5a383cee278acc3f7e7b9d0a656e6a35Owen Andersonchar &llvm::MachineLoopInfoID = MachineLoopInfo::ID; 36e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 37e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Andersonbool MachineLoopInfo::runOnMachineFunction(MachineFunction &) { 38e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson releaseMemory(); 39c9b1e25493b393013b28e5d457f2fb2845a4dd9fAndrew Trick LI.Analyze(getAnalysis<MachineDominatorTree>().getBase()); 40e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson return false; 41e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson} 42e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson 43e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Andersonvoid MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { 44e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson AU.setPreservesAll(); 45e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson AU.addRequired<MachineDominatorTree>(); 46ad2afc2a421a0e41603d5eee412d4d8c77e9bc1cDan Gohman MachineFunctionPass::getAnalysisUsage(AU); 47e4ad9c70e4a1261c212b11623d99e2477ef02783Owen Anderson} 4881b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman 4981b16a3558514481c61e7c68d19f84d7a69352cbDan GohmanMachineBasicBlock *MachineLoop::getTopBlock() { 5081b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman MachineBasicBlock *TopMBB = getHeader(); 5181b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman MachineFunction::iterator Begin = TopMBB->getParent()->begin(); 5281b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman if (TopMBB != Begin) { 5381b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman MachineBasicBlock *PriorMBB = prior(MachineFunction::iterator(TopMBB)); 5481b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman while (contains(PriorMBB)) { 5581b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman TopMBB = PriorMBB; 5681b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman if (TopMBB == Begin) break; 5781b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman PriorMBB = prior(MachineFunction::iterator(TopMBB)); 5881b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman } 5981b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman } 6081b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman return TopMBB; 6181b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman} 6281b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman 6381b16a3558514481c61e7c68d19f84d7a69352cbDan GohmanMachineBasicBlock *MachineLoop::getBottomBlock() { 6481b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman MachineBasicBlock *BotMBB = getHeader(); 6581b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman MachineFunction::iterator End = BotMBB->getParent()->end(); 6681b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman if (BotMBB != prior(End)) { 677896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner MachineBasicBlock *NextMBB = llvm::next(MachineFunction::iterator(BotMBB)); 6881b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman while (contains(NextMBB)) { 6981b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman BotMBB = NextMBB; 707896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner if (BotMBB == llvm::next(MachineFunction::iterator(BotMBB))) break; 717896c9f436a4eda5ec15e882a7505ba482a2fcd0Chris Lattner NextMBB = llvm::next(MachineFunction::iterator(BotMBB)); 7281b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman } 7381b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman } 7481b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman return BotMBB; 7581b16a3558514481c61e7c68d19f84d7a69352cbDan Gohman} 76dda30cd4af1c5f88fc00fd40b673f8e27c61379dDan Gohman 77b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 78dda30cd4af1c5f88fc00fd40b673f8e27c61379dDan Gohmanvoid MachineLoop::dump() const { 79dda30cd4af1c5f88fc00fd40b673f8e27c61379dDan Gohman print(dbgs()); 80dda30cd4af1c5f88fc00fd40b673f8e27c61379dDan Gohman} 8177e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 82