112 lines · cpp
1//===- PostDominators.cpp - Post-Dominator Calculation --------------------===//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//9// This file implements the post-dominator construction algorithms.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/Analysis/PostDominators.h"14#include "llvm/IR/Function.h"15#include "llvm/IR/Instructions.h"16#include "llvm/IR/PassManager.h"17#include "llvm/InitializePasses.h"18#include "llvm/Pass.h"19#include "llvm/Support/raw_ostream.h"20 21using namespace llvm;22 23#define DEBUG_TYPE "postdomtree"24 25#ifdef EXPENSIVE_CHECKS26static constexpr bool ExpensiveChecksEnabled = true;27#else28static constexpr bool ExpensiveChecksEnabled = false;29#endif30 31//===----------------------------------------------------------------------===//32// PostDominatorTree Implementation33//===----------------------------------------------------------------------===//34 35char PostDominatorTreeWrapperPass::ID = 0;36 37PostDominatorTreeWrapperPass::PostDominatorTreeWrapperPass()38 : FunctionPass(ID) {}39 40INITIALIZE_PASS(PostDominatorTreeWrapperPass, "postdomtree",41 "Post-Dominator Tree Construction", true, true)42 43bool PostDominatorTree::invalidate(Function &F, const PreservedAnalyses &PA,44 FunctionAnalysisManager::Invalidator &) {45 // Check whether the analysis, all analyses on functions, or the function's46 // CFG have been preserved.47 auto PAC = PA.getChecker<PostDominatorTreeAnalysis>();48 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||49 PAC.preservedSet<CFGAnalyses>());50}51 52bool PostDominatorTree::dominates(const Instruction *I1,53 const Instruction *I2) const {54 assert(I1 && I2 && "Expecting valid I1 and I2");55 56 const BasicBlock *BB1 = I1->getParent();57 const BasicBlock *BB2 = I2->getParent();58 59 if (BB1 != BB2)60 return Base::dominates(BB1, BB2);61 62 // PHINodes in a block are unordered.63 if (isa<PHINode>(I1) && isa<PHINode>(I2))64 return false;65 66 // Loop through the basic block until we find I1 or I2.67 BasicBlock::const_iterator I = BB1->begin();68 for (; &*I != I1 && &*I != I2; ++I)69 /*empty*/;70 71 return &*I == I2;72}73 74bool PostDominatorTreeWrapperPass::runOnFunction(Function &F) {75 DT.recalculate(F);76 return false;77}78 79void PostDominatorTreeWrapperPass::verifyAnalysis() const {80 if (VerifyDomInfo)81 assert(DT.verify(PostDominatorTree::VerificationLevel::Full));82 else if (ExpensiveChecksEnabled)83 assert(DT.verify(PostDominatorTree::VerificationLevel::Basic));84}85 86void PostDominatorTreeWrapperPass::print(raw_ostream &OS, const Module *) const {87 DT.print(OS);88}89 90FunctionPass* llvm::createPostDomTree() {91 return new PostDominatorTreeWrapperPass();92}93 94AnalysisKey PostDominatorTreeAnalysis::Key;95 96PostDominatorTree PostDominatorTreeAnalysis::run(Function &F,97 FunctionAnalysisManager &) {98 PostDominatorTree PDT(F);99 return PDT;100}101 102PostDominatorTreePrinterPass::PostDominatorTreePrinterPass(raw_ostream &OS)103 : OS(OS) {}104 105PreservedAnalyses106PostDominatorTreePrinterPass::run(Function &F, FunctionAnalysisManager &AM) {107 OS << "PostDominatorTree for function: " << F.getName() << "\n";108 AM.getResult<PostDominatorTreeAnalysis>(F).print(OS);109 110 return PreservedAnalyses::all();111}112