path: root/lib/Analysis/RegionInfo.cpp

//===- RegionInfo.cpp - SESE region detection analysis --------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
// Detects single entry single exit regions in the control flow graph.
//===----------------------------------------------------------------------===//

#include "llvm/Analysis/RegionInfo.h"
#include "llvm/Analysis/RegionIterator.h"

#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/ErrorHandling.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Assembly/Writer.h"

#define DEBUG_TYPE "region"
#include "llvm/Support/Debug.h"

#include <set>
#include <algorithm>

using namespace llvm;

// Always verify if expensive checking is enabled.
#ifdef XDEBUG
static bool VerifyRegionInfo = true;
#else
static bool VerifyRegionInfo = false;
#endif

static cl::opt<bool,true>
VerifyRegionInfoX("verify-region-info", cl::location(VerifyRegionInfo),
                cl::desc("Verify region info (time consuming)"));

STATISTIC(numRegions,       "The # of regions");
STATISTIC(numSimpleRegions, "The # of simple regions");

static cl::opt<enum Region::PrintStyle> printStyle("print-region-style",
  cl::Hidden,
  cl::desc("style of printing regions"),
  cl::values(
    clEnumValN(Region::PrintNone, "none",  "print no details"),
    clEnumValN(Region::PrintBB, "bb",
               "print regions in detail with block_node_iterator"),
    clEnumValN(Region::PrintRN, "rn",
               "print regions in detail with element_iterator"),
    clEnumValEnd));
//===----------------------------------------------------------------------===//
/// Region Implementation
Region::Region(BasicBlock *Entry, BasicBlock *Exit, RegionInfo* RInfo,
               DominatorTree *dt, Region *Parent)
               : RegionNode(Parent, Entry, 1), RI(RInfo), DT(dt), exit(Exit) {}

Region::~Region() {
  // Free the cached nodes.
  for (BBNodeMapT::iterator it = BBNodeMap.begin(),
         ie = BBNodeMap.end(); it != ie; ++it)
    delete it->second;

  // Only clean the cache for this Region. Caches of child Regions will be
  // cleaned when the child Regions are deleted.
  BBNodeMap.clear();

  for (iterator I = begin(), E = end(); I != E; ++I)
    delete *I;
}

void Region::replaceEntry(BasicBlock *BB) {
  entry.setPointer(BB);
}

void Region::replaceExit(BasicBlock *BB) {
  assert(exit && "No exit to replace!");
  exit = BB;
}

bool Region::contains(const BasicBlock *B) const {
  BasicBlock *BB = const_cast<BasicBlock*>(B);

  assert(DT->getNode(BB) && "BB not part of the dominance tree");

  BasicBlock *entry = getEntry(), *exit = getExit();

  // Toplevel region.
  if (!exit)
    return true;

  return (DT->dominates(entry, BB)
    && !(DT->dominates(exit, BB) && DT->dominates(entry, exit)));
}

bool Region::contains(const Loop *L) const {
  // BBs that are not part of any loop are element of the Loop
  // described by the NULL pointer. This loop is not part of any region,
  // except if the region describes the whole function.
  if (L == 0)
    return getExit() == 0;

  if (!contains(L->getHeader()))
    return false;

  SmallVector<BasicBlock *, 8> ExitingBlocks;
  L->getExitingBlocks(ExitingBlocks);

  for (SmallVectorImpl<BasicBlock*>::iterator BI = ExitingBlocks.begin(),
       BE = ExitingBlocks.end(); BI != BE; ++BI)
    if (!contains(*BI))
      return false;

  return true;
}

Loop *Region::outermostLoopInRegion(Loop *L) const {
  if (!contains(L))
    return 0;

  while (L && contains(L->getParentLoop())) {
    L = L->getParentLoop();
  }

  return L;
}

Loop *Region::outermostLoopInRegion(LoopInfo *LI, BasicBlock* BB) const {
  assert(LI && BB && "LI and BB cannot be null!");
  Loop *L = LI->getLoopFor(BB);
  return outermostLoopInRegion(L);
}

BasicBlock *Region::getEnteringBlock() const {
  BasicBlock *entry = getEntry();
  BasicBlock *Pred;
  BasicBlock *enteringBlock = 0;

  for (pred_iterator PI = pred_begin(entry), PE = pred_end(entry); PI != PE;
       ++PI) {
    Pred = *PI;
    if (DT->getNode(Pred) && !contains(Pred)) {
      if (enteringBlock)
        return 0;

      enteringBlock = Pred;
    }
  }

  return enteringBlock;
}

BasicBlock *Region::getExitingBlock() const {