Go to the documentation of this file.
22 "Simplify DDG by merging nodes that have less interesting edges."));
27 #define DEBUG_TYPE "ddg"
41 assert(IList.empty() &&
"Expected the IList to be empty on entry.");
42 if (isa<SimpleDDGNode>(
this)) {
43 for (
Instruction *
I : cast<const SimpleDDGNode>(
this)->getInstructions())
46 }
else if (isa<PiBlockDDGNode>(
this)) {
47 for (
const DDGNode *PN : cast<const PiBlockDDGNode>(
this)->getNodes()) {
48 assert(!isa<PiBlockDDGNode>(PN) &&
"Nested PiBlocks are not supported.");
50 PN->collectInstructions(Pred, TmpIList);
55 return !IList.empty();
62 Out =
"single-instruction";
65 Out =
"multi-instruction";
82 OS <<
"Node Address:" << &
N <<
":" <<
N.getKind() <<
"\n";
83 if (isa<SimpleDDGNode>(
N)) {
84 OS <<
" Instructions:\n";
85 for (
const Instruction *
I : cast<const SimpleDDGNode>(
N).getInstructions())
87 }
else if (isa<PiBlockDDGNode>(&
N)) {
88 OS <<
"--- start of nodes in pi-block ---\n";
89 auto &Nodes = cast<const PiBlockDDGNode>(&
N)->getNodes();
92 OS << *
N << (++Count == Nodes.size() ?
"" :
"\n");
93 OS <<
"--- end of nodes in pi-block ---\n";
94 }
else if (!isa<RootDDGNode>(
N))
97 OS << (
N.getEdges().empty() ?
" Edges:none!\n" :
" Edges:\n");
98 for (
const auto &
E :
N.getEdges())
109 assert(InstList.empty() &&
"Expected empty list.");
110 InstList.push_back(&
I);
117 "constructing from invalid simple node.");
124 "constructing from invalid simple node.");
135 assert(!
NodeList.empty() &&
"pi-block node constructed with an empty list.");
141 "constructing from invalid pi-block node.");
147 "constructing from invalid pi-block node.");
177 OS <<
"[" <<
E.getKind() <<
"] to " << &
E.getTargetNode() <<
"\n";
229 auto *Pi = dyn_cast<PiBlockDDGNode>(&
N);
231 "Root node is already added. No more nodes can be added.");
233 if (isa<RootDDGNode>(
N))
237 for (
DDGNode *NI : Pi->getNodes())
238 PiBlockMap.
insert(std::make_pair(NI, Pi));
244 if (PiBlockMap.
find(&
N) == PiBlockMap.
end())
246 auto *Pi = PiBlockMap.
find(&
N)->second;
248 "Nested pi-blocks detected.");
256 if (!
G.getPiBlock(*Node))
270 const auto *SimpleSrc = dyn_cast<const SimpleDDGNode>(&Src);
271 const auto *SimpleTgt = dyn_cast<const SimpleDDGNode>(&Tgt);
272 if (!SimpleSrc || !SimpleTgt)
275 return SimpleSrc->getLastInstruction()->getParent() ==
276 SimpleTgt->getFirstInstruction()->getParent();
282 "Expected A to have a single edge to B.");
283 assert(isa<SimpleDDGNode>(&
A) && isa<SimpleDDGNode>(&
B) &&
284 "Expected simple nodes");
287 cast<SimpleDDGNode>(&
A)->appendInstructions(*cast<SimpleDDGNode>(&
B));
293 A.removeEdge(EdgeToFold);
312 return std::make_unique<DataDependenceGraph>(L, AR.
LI, DI);
A set of analyses that are preserved following a run of a transformation pass.
Encapsulate some common data and functionality needed for different variations of data dependence gra...
static StringRef getName(Value *V)
NodeKind getKind() const
Getter for the kind of this node.
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
bool connect(NodeType &Src, NodeType &Dst, EdgeType &E)
Assuming nodes Src and Dst are already in the graph, connect node Src to node Dst using the provided ...
const Function * getParent() const
Return the enclosing method, or null if none.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represents a single loop in the control flow graph.
Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
DDG as a loop pass.
Represent a node in the directed graph.
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
static cl::opt< bool > CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::desc("Create pi-block nodes."))
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
virtual void destroyNode(NodeType &N)
Deallocate memory of node N.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Data Dependency Graph Edge.
bool areNodesMergeable(const DDGNode &Src, const DDGNode &Tgt) const final
Return true if the two nodes \pSrc and \pTgt are both simple nodes and the consecutive instructions a...
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
RPOIterator endRPO() const
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
DataDependenceGraph()=delete
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
An efficient, type-erasing, non-owning reference to a callable.
Store the result of a depth first search within basic blocks contained by a single loop.
Subclass of DDGNode representing a pi-block.
DependenceInfo - This class is the main dependence-analysis driver.
bool addNode(NodeType &N)
Add node N to the graph, if it's not added yet, and keep track of the root node as well as pi-blocks ...
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Subclass of DDGNode representing single or multi-instruction nodes.
bool shouldSimplify() const final
A special type used by analysis passes to provide an address that identifies that particular analysis...
initializer< Ty > init(const Ty &Val)
const NodeType & getTargetNode() const
Retrieve the target node this edge connects to.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
static cl::opt< bool > SimplifyDDG("ddg-simplify", cl::init(true), cl::Hidden, cl::desc("Simplify DDG by merging nodes that have less interesting edges."))
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
static const Function * getParent(const Value *V)
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
bool collectInstructions(llvm::function_ref< bool(Instruction *)> const &Pred, InstructionListType &IList) const
Collect a list of instructions, in IList, for which predicate Pred evaluates to true when iterating o...
StringRef getName() const
Return a constant reference to the value's name.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
bool shouldCreatePiBlocks() const final
Determine the kind of a node from its type.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
virtual void destroyEdge(EdgeType &E)
Deallocate memory of edge E.
BlockT * getHeader() const
void mergeNodes(DDGNode &Src, DDGNode &Tgt) final
bool addNode(NodeType &N)
Add the given node N to the graph if it is not already present.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
Data Dependence Graph Node The graph can represent the following types of nodes:
bool removeNode(NodeType &N)
Remove the given node N from the graph.
auto reverse(ContainerTy &&C)
A container for analyses that lazily runs them and caches their results.
scc_iterator< T > scc_end(const T &G)
Construct the end iterator for a deduced graph type T.
Represent an edge in the directed graph.
Analysis pass that builds the DDG for a loop.
std::unique_ptr< DataDependenceGraph > Result
const PiBlockDDGNode * getPiBlock(const NodeType &N) const
If node N belongs to a pi-block return a pointer to the pi-block, otherwise return null.
EdgeKind
The kind of edge in the DDG.
DataDependenceGraph & Graph
Reference to the graph that gets built by a concrete implementation of this builder.