Line data    Source code

       1             : //===- MachineLoopInfo.cpp - Natural Loop Calculator ----------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This file defines the MachineLoopInfo class that is used to identify natural
      11             : // loops and determine the loop depth of various nodes of the CFG.  Note that
      12             : // the loops identified may actually be several natural loops that share the
      13             : // same header node... not just a single natural loop.
      14             : //
      15             : //===----------------------------------------------------------------------===//
      16             : 
      17             : #include "llvm/CodeGen/MachineLoopInfo.h"
      18             : #include "llvm/Analysis/LoopInfoImpl.h"
      19             : #include "llvm/CodeGen/MachineDominators.h"
      20             : #include "llvm/CodeGen/Passes.h"
      21             : #include "llvm/Config/llvm-config.h"
      22             : #include "llvm/Support/Debug.h"
      23             : #include "llvm/Support/raw_ostream.h"
      24             : using namespace llvm;
      25             : 
      26             : // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
      27             : template class llvm::LoopBase<MachineBasicBlock, MachineLoop>;
      28             : template class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;
      29             : 
      30             : char MachineLoopInfo::ID = 0;
      31       85394 : INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",
      32             :                 "Machine Natural Loop Construction", true, true)
      33       85394 : INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
      34     1561918 : INITIALIZE_PASS_END(MachineLoopInfo, "machine-loops",
      35             :                 "Machine Natural Loop Construction", true, true)
      36             : 
      37             : char &llvm::MachineLoopInfoID = MachineLoopInfo::ID;
      38             : 
      39      925337 : bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
      40      925337 :   releaseMemory();
      41      925337 :   LI.analyze(getAnalysis<MachineDominatorTree>().getBase());
      42      925337 :   return false;
      43             : }
      44             : 
      45       93950 : void MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
      46             :   AU.setPreservesAll();
      47             :   AU.addRequired<MachineDominatorTree>();
      48       93950 :   MachineFunctionPass::getAnalysisUsage(AU);
      49       93950 : }
      50             : 
      51         478 : MachineBasicBlock *MachineLoop::getTopBlock() {
      52             :   MachineBasicBlock *TopMBB = getHeader();
      53         478 :   MachineFunction::iterator Begin = TopMBB->getParent()->begin();
      54         478 :   if (TopMBB->getIterator() != Begin) {
      55             :     MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
      56         486 :     while (contains(PriorMBB)) {
      57             :       TopMBB = PriorMBB;
      58           8 :       if (TopMBB->getIterator() == Begin)
      59             :         break;
      60             :       PriorMBB = &*std::prev(TopMBB->getIterator());
      61             :     }
      62             :   }
      63         478 :   return TopMBB;
      64             : }
      65             : 
      66         333 : MachineBasicBlock *MachineLoop::getBottomBlock() {
      67             :   MachineBasicBlock *BotMBB = getHeader();
      68         333 :   MachineFunction::iterator End = BotMBB->getParent()->end();
      69         333 :   if (BotMBB->getIterator() != std::prev(End)) {
      70             :     MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
      71         302 :     while (contains(NextMBB)) {
      72             :       BotMBB = NextMBB;
      73           0 :       if (BotMBB == &*std::next(BotMBB->getIterator()))
      74             :         break;
      75             :       NextMBB = &*std::next(BotMBB->getIterator());
      76             :     }
      77             :   }
      78         333 :   return BotMBB;
      79             : }
      80             : 
      81        1491 : MachineBasicBlock *MachineLoop::findLoopControlBlock() {
      82        1491 :   if (MachineBasicBlock *Latch = getLoopLatch()) {
      83        1490 :     if (isLoopExiting(Latch))
      84             :       return Latch;
      85             :     else
      86          34 :       return getExitingBlock();
      87             :   }
      88             :   return nullptr;
      89             : }
      90             : 
      91          23 : DebugLoc MachineLoop::getStartLoc() const {
      92             :   // Try the pre-header first.
      93          23 :   if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
      94          23 :     if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
      95          39 :       if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
      96             :         return DL;
      97             : 
      98             :   // If we have no pre-header or there are no instructions with debug
      99             :   // info in it, try the header.
     100             :   if (MachineBasicBlock *HeadMBB = getHeader())
     101           7 :     if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
     102           7 :       return HeadBB->getTerminator()->getDebugLoc();
     103             : 
     104           0 :   return DebugLoc();
     105             : }
     106             : 
     107             : MachineBasicBlock *
     108         893 : MachineLoopInfo::findLoopPreheader(MachineLoop *L,
     109             :                                    bool SpeculativePreheader) const {
     110         893 :   if (MachineBasicBlock *PB = L->getLoopPreheader())
     111             :     return PB;
     112             : 
     113          26 :   if (!SpeculativePreheader)
     114             :     return nullptr;
     115             : 
     116           4 :   MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
     117           4 :   if (HB->pred_size() != 2 || HB->hasAddressTaken())
     118             :     return nullptr;
     119             :   // Find the predecessor of the header that is not the latch block.
     120             :   MachineBasicBlock *Preheader = nullptr;
     121          12 :   for (MachineBasicBlock *P : HB->predecessors()) {
     122           8 :     if (P == LB)
     123             :       continue;
     124             :     // Sanity.
     125           4 :     if (Preheader)
     126             :       return nullptr;
     127             :     Preheader = P;
     128             :   }
     129             : 
     130             :   // Check if the preheader candidate is a successor of any other loop
     131             :   // headers. We want to avoid having two loop setups in the same block.
     132          12 :   for (MachineBasicBlock *S : Preheader->successors()) {
     133           8 :     if (S == HB)
     134             :       continue;
     135             :     MachineLoop *T = getLoopFor(S);
     136           0 :     if (T && T->getHeader() == S)
     137             :       return nullptr;
     138             :   }
     139             :   return Preheader;
     140             : }
     141             : 
     142             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     143             : LLVM_DUMP_METHOD void MachineLoop::dump() const {
     144             :   print(dbgs());
     145             : }
     146             : #endif