LLVM 19.0.0git
PostDominators.cpp
Go to the documentation of this file.
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-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the post-dominator construction algorithms.
10//
11//===----------------------------------------------------------------------===//
12
14#include "llvm/IR/Function.h"
16#include "llvm/IR/PassManager.h"
18#include "llvm/Pass.h"
20
21using namespace llvm;
22
23#define DEBUG_TYPE "postdomtree"
24
25#ifdef EXPENSIVE_CHECKS
26static constexpr bool ExpensiveChecksEnabled = true;
27#else
28static constexpr bool ExpensiveChecksEnabled = false;
29#endif
30
31//===----------------------------------------------------------------------===//
32// PostDominatorTree Implementation
33//===----------------------------------------------------------------------===//
34
36
38 : FunctionPass(ID) {
40}
41
43 "Post-Dominator Tree Construction", true, true)
44
46 FunctionAnalysisManager::Invalidator &) {
47 // Check whether the analysis, all analyses on functions, or the function's
48 // CFG have been preserved.
49 auto PAC = PA.getChecker<PostDominatorTreeAnalysis>();
50 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
51 PAC.preservedSet<CFGAnalyses>());
52}
53
55 const Instruction *I2) const {
56 assert(I1 && I2 && "Expecting valid I1 and I2");
57
58 const BasicBlock *BB1 = I1->getParent();
59 const BasicBlock *BB2 = I2->getParent();
60
61 if (BB1 != BB2)
62 return Base::dominates(BB1, BB2);
63
64 // PHINodes in a block are unordered.
65 if (isa<PHINode>(I1) && isa<PHINode>(I2))
66 return false;
67
68 // Loop through the basic block until we find I1 or I2.
70 for (; &*I != I1 && &*I != I2; ++I)
71 /*empty*/;
72
73 return &*I == I2;
74}
75
78 return false;
79}
80
82 if (VerifyDomInfo)
86}
87
89 DT.print(OS);
90}
91
94}
95
96AnalysisKey PostDominatorTreeAnalysis::Key;
97
100 PostDominatorTree PDT(F);
101 return PDT;
102}
103
105 : OS(OS) {}
106
109 OS << "PostDominatorTree for function: " << F.getName() << "\n";
111
112 return PreservedAnalyses::all();
113}
aarch64 promote const
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
This header defines various interfaces for pass management in LLVM.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
static constexpr bool ExpensiveChecksEnabled
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: Analysis.h:47
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:429
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:165
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:70
void print(raw_ostream &O) const
print - Convert to human readable form
bool verify(VerificationLevel VL=VerificationLevel::Full) const
verify - checks if the tree is correct.
bool dominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
dominates - Returns true iff A dominates B.
void recalculate(ParentType &Func)
recalculate - compute a dominator tree for the given function
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
const BasicBlock * getParent() const
Definition: Instruction.h:152
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Analysis pass which computes a PostDominatorTree.
PostDominatorTree run(Function &F, FunctionAnalysisManager &)
Run the analysis pass over a function and produce a post dominator tree.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
FunctionPass * createPostDomTree()
void initializePostDominatorTreeWrapperPassPass(PassRegistry &)
bool VerifyDomInfo
Enables verification of dominator trees.
Definition: Dominators.cpp:40
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void print(raw_ostream &OS, const Module *) const override
print - Print out the internal state of the pass.
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...