contrib/llvm/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/Support/Debug.h"
  22 #include "llvm/Support/raw_ostream.h"
  23 using namespace llvm;
  24
  25 // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
  26 template class llvm::LoopBase<MachineBasicBlock, MachineLoop>;
  27 template class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;
  28
  29 char MachineLoopInfo::ID = 0;
  30 INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",
  31                 "Machine Natural Loop Construction", true, true)
  32 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  33 INITIALIZE_PASS_END(MachineLoopInfo, "machine-loops",
  34                 "Machine Natural Loop Construction", true, true)
  35
  36 char &llvm::MachineLoopInfoID = MachineLoopInfo::ID;
  37
  38 bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
  39   releaseMemory();
  40   LI.analyze(getAnalysis<MachineDominatorTree>().getBase());
  41   return false;
  42 }
  43
  44 void MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
  45   AU.setPreservesAll();
  46   AU.addRequired<MachineDominatorTree>();
  47   MachineFunctionPass::getAnalysisUsage(AU);
  48 }
  49
  50 MachineBasicBlock *MachineLoop::getTopBlock() {
  51   MachineBasicBlock *TopMBB = getHeader();
  52   MachineFunction::iterator Begin = TopMBB->getParent()->begin();
  53   if (TopMBB->getIterator() != Begin) {
  54     MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
  55     while (contains(PriorMBB)) {
  56       TopMBB = PriorMBB;
  57       if (TopMBB->getIterator() == Begin)
  58         break;
  59       PriorMBB = &*std::prev(TopMBB->getIterator());
  60     }
  61   }
  62   return TopMBB;
  63 }
  64
  65 MachineBasicBlock *MachineLoop::getBottomBlock() {
  66   MachineBasicBlock *BotMBB = getHeader();
  67   MachineFunction::iterator End = BotMBB->getParent()->end();
  68   if (BotMBB->getIterator() != std::prev(End)) {
  69     MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
  70     while (contains(NextMBB)) {
  71       BotMBB = NextMBB;
  72       if (BotMBB == &*std::next(BotMBB->getIterator()))
  73         break;
  74       NextMBB = &*std::next(BotMBB->getIterator());
  75     }
  76   }
  77   return BotMBB;
  78 }
  79
  80 MachineBasicBlock *MachineLoop::findLoopControlBlock() {
  81   if (MachineBasicBlock *Latch = getLoopLatch()) {
  82     if (isLoopExiting(Latch))
  83       return Latch;
  84     else
  85       return getExitingBlock();
  86   }
  87   return nullptr;
  88 }
  89
  90 DebugLoc MachineLoop::getStartLoc() const {
  91   // Try the pre-header first.
  92   if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
  93     if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
  94       if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
  95         return DL;
  96
  97   // If we have no pre-header or there are no instructions with debug
  98   // info in it, try the header.
  99   if (MachineBasicBlock *HeadMBB = getHeader())
 100     if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
 101       return HeadBB->getTerminator()->getDebugLoc();
 102
 103   return DebugLoc();
 104 }
 105
 106 MachineBasicBlock *
 107 MachineLoopInfo::findLoopPreheader(MachineLoop *L,
 108                                    bool SpeculativePreheader) const {
 109   if (MachineBasicBlock *PB = L->getLoopPreheader())
 110     return PB;
 111
 112   if (!SpeculativePreheader)
 113     return nullptr;
 114
 115   MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
 116   if (HB->pred_size() != 2 || HB->hasAddressTaken())
 117     return nullptr;
 118   // Find the predecessor of the header that is not the latch block.
 119   MachineBasicBlock *Preheader = nullptr;
 120   for (MachineBasicBlock *P : HB->predecessors()) {
 121     if (P == LB)
 122       continue;
 123     // Sanity.
 124     if (Preheader)
 125       return nullptr;
 126     Preheader = P;
 127   }
 128
 129   // Check if the preheader candidate is a successor of any other loop
 130   // headers. We want to avoid having two loop setups in the same block.
 131   for (MachineBasicBlock *S : Preheader->successors()) {
 132     if (S == HB)
 133       continue;
 134     MachineLoop *T = getLoopFor(S);
 135     if (T && T->getHeader() == S)
 136       return nullptr;
 137   }
 138   return Preheader;
 139 }
 140
 141 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 142 LLVM_DUMP_METHOD void MachineLoop::dump() const {
 143   print(dbgs());
 144 }
 145 #endif