214 lines · cpp
1//===- RegionInfo.cpp - SESE region detection analysis --------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8// Detects single entry single exit regions in the control flow graph.9//===----------------------------------------------------------------------===//10 11#include "llvm/Analysis/RegionInfo.h"12#include "llvm/ADT/Statistic.h"13#include "llvm/Analysis/DominanceFrontier.h"14#include "llvm/InitializePasses.h"15#ifndef NDEBUG16#include "llvm/Analysis/RegionPrinter.h"17#endif18#include "llvm/Analysis/Passes.h"19#include "llvm/Analysis/RegionInfoImpl.h"20#include "llvm/Config/llvm-config.h"21#include "llvm/IR/Function.h"22#include "llvm/Support/CommandLine.h"23#include "llvm/Support/Compiler.h"24 25using namespace llvm;26 27#define DEBUG_TYPE "region"28 29namespace llvm {30 31template class RegionBase<RegionTraits<Function>>;32template class RegionNodeBase<RegionTraits<Function>>;33template class RegionInfoBase<RegionTraits<Function>>;34 35} // end namespace llvm36 37STATISTIC(numRegions, "The # of regions");38STATISTIC(numSimpleRegions, "The # of simple regions");39 40// Always verify if expensive checking is enabled.41 42static cl::opt<bool,true>43VerifyRegionInfoX(44 "verify-region-info",45 cl::location(RegionInfoBase<RegionTraits<Function>>::VerifyRegionInfo),46 cl::desc("Verify region info (time consuming)"));47 48static cl::opt<Region::PrintStyle, true> printStyleX("print-region-style",49 cl::location(RegionInfo::printStyle),50 cl::Hidden,51 cl::desc("style of printing regions"),52 cl::values(53 clEnumValN(Region::PrintNone, "none", "print no details"),54 clEnumValN(Region::PrintBB, "bb",55 "print regions in detail with block_iterator"),56 clEnumValN(Region::PrintRN, "rn",57 "print regions in detail with element_iterator")));58 59//===----------------------------------------------------------------------===//60// Region implementation61//62 63Region::Region(BasicBlock *Entry, BasicBlock *Exit,64 RegionInfo* RI,65 DominatorTree *DT, Region *Parent) :66 RegionBase<RegionTraits<Function>>(Entry, Exit, RI, DT, Parent) {67 68}69 70Region::~Region() = default;71 72//===----------------------------------------------------------------------===//73// RegionInfo implementation74//75 76RegionInfo::RegionInfo() = default;77 78RegionInfo::~RegionInfo() = default;79 80bool RegionInfo::invalidate(Function &F, const PreservedAnalyses &PA,81 FunctionAnalysisManager::Invalidator &) {82 // Check whether the analysis, all analyses on functions, or the function's83 // CFG has been preserved.84 auto PAC = PA.getChecker<RegionInfoAnalysis>();85 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||86 PAC.preservedSet<CFGAnalyses>());87}88 89void RegionInfo::updateStatistics(Region *R) {90 ++numRegions;91 92 // TODO: Slow. Should only be enabled if -stats is used.93 if (R->isSimple())94 ++numSimpleRegions;95}96 97void RegionInfo::recalculate(Function &F, DominatorTree *DT_,98 PostDominatorTree *PDT_, DominanceFrontier *DF_) {99 DT = DT_;100 PDT = PDT_;101 DF = DF_;102 103 TopLevelRegion = new Region(&F.getEntryBlock(), nullptr,104 this, DT, nullptr);105 updateStatistics(TopLevelRegion);106 calculate(F);107}108 109#ifndef NDEBUG110void RegionInfo::view() { viewRegion(this); }111 112void RegionInfo::viewOnly() { viewRegionOnly(this); }113#endif114 115//===----------------------------------------------------------------------===//116// RegionInfoPass implementation117//118 119RegionInfoPass::RegionInfoPass() : FunctionPass(ID) {}120 121RegionInfoPass::~RegionInfoPass() = default;122 123bool RegionInfoPass::runOnFunction(Function &F) {124 releaseMemory();125 126 auto DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();127 auto PDT = &getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();128 auto DF = &getAnalysis<DominanceFrontierWrapperPass>().getDominanceFrontier();129 130 RI.recalculate(F, DT, PDT, DF);131 return false;132}133 134void RegionInfoPass::releaseMemory() {135 RI.releaseMemory();136}137 138void RegionInfoPass::verifyAnalysis() const {139 RI.verifyAnalysis();140}141 142void RegionInfoPass::getAnalysisUsage(AnalysisUsage &AU) const {143 AU.setPreservesAll();144 AU.addRequiredTransitive<DominatorTreeWrapperPass>();145 AU.addRequired<PostDominatorTreeWrapperPass>();146 AU.addRequired<DominanceFrontierWrapperPass>();147}148 149void RegionInfoPass::print(raw_ostream &OS, const Module *) const {150 RI.print(OS);151}152 153#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)154LLVM_DUMP_METHOD void RegionInfoPass::dump() const {155 RI.dump();156}157#endif158 159char RegionInfoPass::ID = 0;160 161INITIALIZE_PASS_BEGIN(RegionInfoPass, "regions",162 "Detect single entry single exit regions", true, true)163INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)164INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)165INITIALIZE_PASS_DEPENDENCY(DominanceFrontierWrapperPass)166INITIALIZE_PASS_END(RegionInfoPass, "regions",167 "Detect single entry single exit regions", true, true)168 169// Create methods available outside of this file, to use them170// "include/llvm/LinkAllPasses.h". Otherwise the pass would be deleted by171// the link time optimization.172 173namespace llvm {174 175 FunctionPass *createRegionInfoPass() {176 return new RegionInfoPass();177 }178 179} // end namespace llvm180 181//===----------------------------------------------------------------------===//182// RegionInfoAnalysis implementation183//184 185AnalysisKey RegionInfoAnalysis::Key;186 187RegionInfo RegionInfoAnalysis::run(Function &F, FunctionAnalysisManager &AM) {188 RegionInfo RI;189 auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);190 auto *PDT = &AM.getResult<PostDominatorTreeAnalysis>(F);191 auto *DF = &AM.getResult<DominanceFrontierAnalysis>(F);192 193 RI.recalculate(F, DT, PDT, DF);194 return RI;195}196 197RegionInfoPrinterPass::RegionInfoPrinterPass(raw_ostream &OS)198 : OS(OS) {}199 200PreservedAnalyses RegionInfoPrinterPass::run(Function &F,201 FunctionAnalysisManager &AM) {202 OS << "Region Tree for function: " << F.getName() << "\n";203 AM.getResult<RegionInfoAnalysis>(F).print(OS);204 205 return PreservedAnalyses::all();206}207 208PreservedAnalyses RegionInfoVerifierPass::run(Function &F,209 FunctionAnalysisManager &AM) {210 AM.getResult<RegionInfoAnalysis>(F).verifyAnalysis();211 212 return PreservedAnalyses::all();213}214