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 MachineBasicBlock *
  91 MachineLoopInfo::findLoopPreheader(MachineLoop *L,
  92                                    bool SpeculativePreheader) const {
  93   if (MachineBasicBlock *PB = L->getLoopPreheader())
  94     return PB;
  95
  96   if (!SpeculativePreheader)
  97     return nullptr;
  98
  99   MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
 100   if (HB->pred_size() != 2 || HB->hasAddressTaken())
 101     return nullptr;
 102   // Find the predecessor of the header that is not the latch block.
 103   MachineBasicBlock *Preheader = nullptr;
 104   for (MachineBasicBlock *P : HB->predecessors()) {
 105     if (P == LB)
 106       continue;
 107     // Sanity.
 108     if (Preheader)
 109       return nullptr;
 110     Preheader = P;
 111   }
 112
 113   // Check if the preheader candidate is a successor of any other loop
 114   // headers. We want to avoid having two loop setups in the same block.
 115   for (MachineBasicBlock *S : Preheader->successors()) {
 116     if (S == HB)
 117       continue;
 118     MachineLoop *T = getLoopFor(S);
 119     if (T && T->getHeader() == S)
 120       return nullptr;
 121   }
 122   return Preheader;
 123 }
 124
 125 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 126 LLVM_DUMP_METHOD void MachineLoop::dump() const {
 127   print(dbgs());
 128 }
 129 #endif