lib/CodeGen/MachineLoopInfo.cpp

   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 INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",
  32                 "Machine Natural Loop Construction", true, true)
  33 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  34 INITIALIZE_PASS_END(MachineLoopInfo, "machine-loops",
  35                 "Machine Natural Loop Construction", true, true)
  36
  37 char &llvm::MachineLoopInfoID = MachineLoopInfo::ID;
  38
  39 bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
  40   releaseMemory();
  41   LI.analyze(getAnalysis<MachineDominatorTree>().getBase());
  42   return false;
  43 }
  44
  45 void MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
  46   AU.setPreservesAll();
  47   AU.addRequired<MachineDominatorTree>();
  48   MachineFunctionPass::getAnalysisUsage(AU);
  49 }
  50
  51 MachineBasicBlock *MachineLoop::getTopBlock() {
  52   MachineBasicBlock *TopMBB = getHeader();
  53   MachineFunction::iterator Begin = TopMBB->getParent()->begin();
  54   if (TopMBB->getIterator() != Begin) {
  55     MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
  56     while (contains(PriorMBB)) {
  57       TopMBB = PriorMBB;
  58       if (TopMBB->getIterator() == Begin)
  59         break;
  60       PriorMBB = &*std::prev(TopMBB->getIterator());
  61     }
  62   }
  63   return TopMBB;
  64 }
  65
  66 MachineBasicBlock *MachineLoop::getBottomBlock() {
  67   MachineBasicBlock *BotMBB = getHeader();
  68   MachineFunction::iterator End = BotMBB->getParent()->end();
  69   if (BotMBB->getIterator() != std::prev(End)) {
  70     MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
  71     while (contains(NextMBB)) {
  72       BotMBB = NextMBB;
  73       if (BotMBB == &*std::next(BotMBB->getIterator()))
  74         break;
  75       NextMBB = &*std::next(BotMBB->getIterator());
  76     }
  77   }
  78   return BotMBB;
  79 }
  80
  81 MachineBasicBlock *MachineLoop::findLoopControlBlock() {
  82   if (MachineBasicBlock *Latch = getLoopLatch()) {
  83     if (isLoopExiting(Latch))
  84       return Latch;
  85     else
  86       return getExitingBlock();
  87   }
  88   return nullptr;
  89 }
  90
  91 DebugLoc MachineLoop::getStartLoc() const {
  92   // Try the pre-header first.
  93   if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
  94     if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
  95       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     if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
 102       return HeadBB->getTerminator()->getDebugLoc();
 103
 104   return DebugLoc();
 105 }
 106
 107 MachineBasicBlock *
 108 MachineLoopInfo::findLoopPreheader(MachineLoop *L,
 109                                    bool SpeculativePreheader) const {
 110   if (MachineBasicBlock *PB = L->getLoopPreheader())
 111     return PB;
 112
 113   if (!SpeculativePreheader)
 114     return nullptr;
 115
 116   MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
 117   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   for (MachineBasicBlock *P : HB->predecessors()) {
 122     if (P == LB)
 123       continue;
 124     // Sanity.
 125     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   for (MachineBasicBlock *S : Preheader->successors()) {
 133     if (S == HB)
 134       continue;
 135     MachineLoop *T = getLoopFor(S);
 136     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