blob: 2bce59235057ed07c13462b2a43b7f2701ed3110 [file] [log] [blame]
//===- MachineLoopInfo.cpp - Natural Loop Calculator ----------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the MachineLoopInfo class that is used to identify natural
// loops and determine the loop depth of various nodes of the CFG. Note that
// the loops identified may actually be several natural loops that share the
// same header node... not just a single natural loop.
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/Analysis/LoopInfoImpl.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
using namespace llvm;
// Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
template class llvm::LoopBase<MachineBasicBlock, MachineLoop>;
template class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;
char MachineLoopInfo::ID = 0;
INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops",
"Machine Natural Loop Construction", true, true)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_END(MachineLoopInfo, "machine-loops",
"Machine Natural Loop Construction", true, true)
char &llvm::MachineLoopInfoID = MachineLoopInfo::ID;
bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
releaseMemory();
LI.analyze(getAnalysis<MachineDominatorTree>().getBase());
return false;
}
void MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
AU.addRequired<MachineDominatorTree>();
MachineFunctionPass::getAnalysisUsage(AU);
}
MachineBasicBlock *MachineLoop::getTopBlock() {
MachineBasicBlock *TopMBB = getHeader();
MachineFunction::iterator Begin = TopMBB->getParent()->begin();
if (TopMBB->getIterator() != Begin) {
MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
while (contains(PriorMBB)) {
TopMBB = PriorMBB;
if (TopMBB->getIterator() == Begin)
break;
PriorMBB = &*std::prev(TopMBB->getIterator());
}
}
return TopMBB;
}
MachineBasicBlock *MachineLoop::getBottomBlock() {
MachineBasicBlock *BotMBB = getHeader();
MachineFunction::iterator End = BotMBB->getParent()->end();
if (BotMBB->getIterator() != std::prev(End)) {
MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
while (contains(NextMBB)) {
BotMBB = NextMBB;
if (BotMBB == &*std::next(BotMBB->getIterator()))
break;
NextMBB = &*std::next(BotMBB->getIterator());
}
}
return BotMBB;
}
MachineBasicBlock *MachineLoop::findLoopControlBlock() {
if (MachineBasicBlock *Latch = getLoopLatch()) {
if (isLoopExiting(Latch))
return Latch;
else
return getExitingBlock();
}
return nullptr;
}
DebugLoc MachineLoop::getStartLoc() const {
// Try the pre-header first.
if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
return DL;
// If we have no pre-header or there are no instructions with debug
// info in it, try the header.
if (MachineBasicBlock *HeadMBB = getHeader())
if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
return HeadBB->getTerminator()->getDebugLoc();
return DebugLoc();
}
MachineBasicBlock *
MachineLoopInfo::findLoopPreheader(MachineLoop *L,
bool SpeculativePreheader) const {
if (MachineBasicBlock *PB = L->getLoopPreheader())
return PB;
if (!SpeculativePreheader)
return nullptr;
MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
if (HB->pred_size() != 2 || HB->hasAddressTaken())
return nullptr;
// Find the predecessor of the header that is not the latch block.
MachineBasicBlock *Preheader = nullptr;
for (MachineBasicBlock *P : HB->predecessors()) {
if (P == LB)
continue;
// Sanity.
if (Preheader)
return nullptr;
Preheader = P;
}
// Check if the preheader candidate is a successor of any other loop
// headers. We want to avoid having two loop setups in the same block.
for (MachineBasicBlock *S : Preheader->successors()) {
if (S == HB)
continue;
MachineLoop *T = getLoopFor(S);
if (T && T->getHeader() == S)
return nullptr;
}
return Preheader;
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void MachineLoop::dump() const {
print(dbgs());
}
#endif