Go to the documentation of this file.
13 #ifndef LLVM_ANALYSIS_DDG_H
14 #define LLVM_ANALYSIS_DDG_H
128 assert(!InstList.empty() &&
"Instruction List is empty.");
150 setKind((InstList.size() == 0 && Input.size() == 1)
156 appendInstructions(Input.getInstructions());
160 SmallVector<Instruction *, 2> InstList;
272 assert(
Root &&
"Root node is not available yet. Graph construction may "
273 "still be in progress\n");
337 PiBlockMapType PiBlockMap;
353 assert(
RN &&
"Failed to allocate memory for DDG root node.");
359 assert(SN &&
"Failed to allocate memory for simple DDG node.");
365 assert(Pi &&
"Failed to allocate memory for pi-block node.");
371 assert(
E &&
"Failed to allocate memory for edge");
377 assert(
E &&
"Failed to allocate memory for edge");
383 assert(
E &&
"Failed to allocate memory for edge");
384 assert(isa<RootDDGNode>(Src) &&
"Expected root node");
390 auto *PiNode = dyn_cast<const PiBlockDDGNode>(&
N);
391 assert(PiNode &&
"Expected a pi-block node.");
392 return PiNode->getNodes();
416 using Result = std::unique_ptr<DataDependenceGraph>;
439 template <
typename NodeType>
441 const NodeType &Src,
const NodeType &Dst,
DependenceList &Deps)
const {
442 assert(Deps.empty() &&
"Expected empty output list at the start.");
447 return I->mayReadOrWriteMemory();
449 Src.collectInstructions(isMemoryAccess, SrcIList);
450 Dst.collectInstructions(isMemoryAccess, DstIList);
452 for (
auto *SrcI : SrcIList)
453 for (
auto *DstI : DstIList)
458 return !Deps.empty();
461 template <
typename NodeType>
464 const NodeType &Dst)
const {
468 if (!getDependencies(Src, Dst, Deps))
474 if (OS.
str().back() ==
'\n')
490 return &
P->getTargetNode();
495 using ChildIteratorType =
530 return &
P->getTargetNode();
535 using ChildIteratorType =
570 #endif // LLVM_ANALYSIS_DDG_H
A set of analyses that are preserved following a run of a transformation pass.
DDGBuilder(DataDependenceGraph &G, DependenceInfo &D, const BasicBlockListType &BBs)
Encapsulate some common data and functionality needed for different variations of data dependence gra...
Subclass of DDGNode representing the root node of the graph.
NodeKind getKind() const
Getter for the kind of this node.
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
DDGEdge & operator=(DDGEdge &&E)
This is an optimization pass for GlobalISel generic memory operations.
static nodes_iterator nodes_begin(DataDependenceGraph *DG)
DataDependenceGraph::const_iterator nodes_iterator
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 ...
DDGEdge(DDGNode &N, EdgeKind K)
SimpleDDGNode & operator=(const SimpleDDGNode &N)=default
A CRTP mix-in to automatically provide informational APIs needed for passes.
Represents a single loop in the control flow graph.
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
A raw_ostream that writes to an std::string.
DDGNode & operator=(DDGNode &&N)
EdgeKind getKind() const
Get the edge kind.
Represent a node in the directed graph.
DDGNode::const_iterator ChildEdgeIteratorType
static const DDGNode * DDGGetTargetNode(const DGEdge< DDGNode, DDGEdge > *P)
static NodeRef getEntryNode(NodeRef N)
const_iterator begin() const
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
DDGNode(const NodeKind K)
static nodes_iterator nodes_end(const DataDependenceGraph *DG)
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
bool getDependencies(const NodeType &Src, const NodeType &Dst, DependenceList &Deps) const
Collect all the data dependency infos coming from any pair of memory accesses from Src to Dst,...
const NodeListType & getNodesInPiBlock(const DDGNode &N) final
static NodeRef getEntryNode(DataDependenceGraph *DG)
SmallVector< DDGNode *, 4 > PiNodeList
std::string getDependenceString(const NodeType &Src, const NodeType &Dst) const
Return a string representing the type of dependence that the dependence analysis identified between t...
DDGEdge & createRootedEdge(DDGNode &Src, DDGNode &Tgt) final
DDGEdge(DDGNode &N)=delete
static ChildEdgeIteratorType child_edge_end(NodeRef N)
bool isMemoryDependence() const
Return true if this is a memory dependence edge, and false otherwise.
DataDependenceGraph(DataDependenceGraph &&G)
static NodeRef getEntryNode(NodeRef N)
DependenceGraphInfo(const std::string &N, const DependenceInfo &DepInfo)
DDGNode & createPiBlock(const NodeListType &L) final
Create a pi-block node in the graph representing a group of nodes in an SCC of the graph.
DDGEdge & operator=(const DDGEdge &E)=default
typename NodeListTy::const_iterator const_iterator
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
const PiNodeList & getNodes() const
Get the list of nodes in this pi-block.
Data Dependency Graph Edge.
SimpleDDGNode & operator=(SimpleDDGNode &&N)
static nodes_iterator nodes_begin(const DataDependenceGraph *DG)
NodeType & getRoot() const
Return the root node of the graph.
DependenceInfo & DI
Dependence information used to create memory dependence edges in the graph.
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 bool classof(const SimpleDDGNode *N)
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
This class implements an extremely fast bulk output stream that can only output to a stream.
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
typename NodeListTy::iterator iterator
static ChildEdgeIteratorType child_edge_end(NodeRef N)
const_iterator end() const
DDGNode & createRootNode() final
Create the root node of the graph.
DDGAnalysisPrinterPass(raw_ostream &OS)
DataDependenceGraph()=delete
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
static ChildIteratorType child_begin(NodeRef N)
static DDGNode * DDGGetTargetNode(DGEdge< DDGNode, DDGEdge > *P)
static NodeRef getEntryNode(const DataDependenceGraph *DG)
An efficient, type-erasing, non-owning reference to a callable.
Subclass of DDGNode representing a pi-block.
DependenceInfo - This class is the main dependence-analysis driver.
PiBlockDDGNode & operator=(const PiBlockDDGNode &N)=default
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 ...
const versions of the grapth trait specializations for DDG
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.
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
bool shouldSimplify() const final
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
SmallVector< std::unique_ptr< Dependence >, 1 > DependenceList
A special type used by analysis passes to provide an address that identifies that particular analysis...
DDGNode::iterator ChildEdgeIteratorType
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
DGNode< NodeType, EdgeType > & operator=(const DGNode< NodeType, EdgeType > &N)
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
StringRef getName() const
Return the label that is used to name this graph.
DataDependenceGraph::iterator nodes_iterator
Textual printer pass for the DDG of a loop.
bool isDefUse() const
Return true if this is a def-use edge, and false otherwise.
A CRTP mix-in that provides informational APIs needed for analysis passes.
bool isRooted() const
Return true if this is an edge stemming from the root node, and false otherwise.
StringRef - Represent a constant reference to a string, i.e.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
DDGNode & createFineGrainedNode(Instruction &I) final
Create an atomic node in the graph given a single instruction.
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...
static nodes_iterator nodes_end(DataDependenceGraph *DG)
typename EdgeListTy::const_iterator const_iterator
RootDDGNode(RootDDGNode &&N)
InstructionListType & getInstructions()
DDGEdge & createDefUseEdge(DDGNode &Src, DDGNode &Tgt) final
bool shouldCreatePiBlocks() const final
Determine the kind of a node from its type.
static bool classof(const RootDDGNode *N)
Instruction * getLastInstruction() const
DDGEdge(const DDGEdge &E)
virtual ~DependenceGraphInfo()=default
static ChildIteratorType child_end(NodeRef N)
DependenceGraphInfo(DependenceGraphInfo &&G)
PiBlockDDGNode & operator=(PiBlockDDGNode &&N)
DDGEdge & createMemoryEdge(DDGNode &Src, DDGNode &Tgt) final
void mergeNodes(DDGNode &Src, DDGNode &Tgt) final
non-const versions of the grapth trait specializations for DDG
std::unique_ptr< Dependence > depends(Instruction *Src, Instruction *Dst, bool PossiblyLoopIndependent)
depends - Tests for a dependence between the Src and Dst instructions.
static ChildIteratorType child_begin(NodeRef N)
Data Dependence Graph Node The graph can represent the following types of nodes:
DGEdge< NodeType, EdgeType > & operator=(const DGEdge< NodeType, EdgeType > &E)
typename EdgeListTy::iterator iterator
Instruction * getFirstInstruction() const
Get the first/last instruction in the node.
A container for analyses that lazily runs them and caches their results.
SmallVector< Instruction *, 2 > InstructionListType
void setKind(NodeKind K)
Setter for the kind of this node.
Represent an edge in the directed graph.
It looks like we only need to define PPCfmarto for these because according to these instructions perform RTO on fma s src2 rnd ← FPSCR RN
Analysis pass that builds the DDG for a loop.
std::unique_ptr< DataDependenceGraph > Result
Concrete implementation of a pure data dependence graph builder.
static ChildIteratorType child_end(NodeRef N)
std::string & str()
Returns the string's reference.
DDGNode & operator=(const DDGNode &N)
static ChildEdgeIteratorType child_edge_begin(NodeRef N)
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.
DependenceGraphInfo()=delete
EdgeKind
The kind of edge in the DDG.
const InstructionListType & getInstructions() const
Get the list of instructions in this node.
static bool classof(const DDGNode *N)
Define classof to be able to use isa<>, cast<>, dyn_cast<>, etc.
DataDependenceGraph & Graph
Reference to the graph that gets built by a concrete implementation of this builder.