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";
193 std::reverse(BBList.
begin(), BBList.
end());
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));
246 auto *Pi = PiBlockMap.
find(&
N)->second;
255 if (!
G.getPiBlock(*Node))
269 const auto *SimpleSrc = dyn_cast<const SimpleDDGNode>(&Src);
270 const auto *SimpleTgt = dyn_cast<const SimpleDDGNode>(&Tgt);
271 if (!SimpleSrc || !SimpleTgt)
274 return SimpleSrc->getLastInstruction()->getParent() ==
275 SimpleTgt->getFirstInstruction()->getParent();
281 "Expected A to have a single edge to B.");
282 assert(isa<SimpleDDGNode>(&
A) && isa<SimpleDDGNode>(&
B) &&
283 "Expected simple nodes");
286 cast<SimpleDDGNode>(&
A)->appendInstructions(*cast<SimpleDDGNode>(&
B));
292 A.removeEdge(EdgeToFold);
309 Function *
F = L.getHeader()->getParent();
311 return std::make_unique<DataDependenceGraph>(L, AR.
LI, DI);
318 OS <<
"'DDG' for loop '" << L.getHeader()->getName() <<
"':\n";
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static cl::opt< bool > CreatePiBlocks("ddg-pi-blocks", cl::init(true), cl::Hidden, cl::desc("Create pi-block nodes."))
static cl::opt< bool > SimplifyDDG("ddg-simplify", cl::init(true), cl::Hidden, cl::desc("Simplify DDG by merging nodes that have less interesting edges."))
static StringRef getName(Value *V)
This builds on the llvm/ADT/GraphTraits.h file to find the strongly connected components (SCCs) of a ...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
virtual void destroyEdge(EdgeType &E)
Deallocate memory of edge E.
virtual void destroyNode(NodeType &N)
Deallocate memory of node N.
DataDependenceGraph & Graph
Reference to the graph that gets built by a concrete implementation of this builder.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Analysis pass that builds the DDG for a loop.
Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)
DDG as a loop pass.
std::unique_ptr< DataDependenceGraph > Result
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...
bool shouldCreatePiBlocks() const final
Return true if creation of pi-blocks are supported and desired, and false otherwise.
bool shouldSimplify() const final
Return true if graph simplification step is requested, and false otherwise.
void mergeNodes(DDGNode &Src, DDGNode &Tgt) final
Data Dependency Graph Edge.
EdgeKind
The kind of edge in the DDG.
Data Dependence Graph Node The graph can represent the following types of nodes:
NodeKind getKind() const
Getter for the kind of this node.
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...
Represent an edge in the directed graph.
const NodeType & getTargetNode() const
Retrieve the target node this edge connects to.
Represent a node in the directed graph.
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.
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 ...
DataDependenceGraph()=delete
iterator find(const_arg_type_t< KeyT > Val)
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Encapsulate some common data and functionality needed for different variations of data dependence gra...
DependenceInfo - This class is the main dependence-analysis driver.
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 ...
bool addNode(NodeType &N)
Add the given node N to the graph if it is not already present.
bool removeNode(NodeType &N)
Remove the given node N from the graph.
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Store the result of a depth first search within basic blocks contained by a single loop.
RPOIterator beginRPO() const
Reverse iterate over the cached postorder blocks.
void perform(LoopInfo *LI)
Traverse the loop blocks and store the DFS result.
RPOIterator endRPO() const
Represents a single loop in the control flow graph.
Subclass of DDGNode representing a pi-block.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Subclass of DDGNode representing single or multi-instruction nodes.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
raw_ostream & indent(unsigned NumSpaces)
indent - Insert 'NumSpaces' spaces.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
initializer< Ty > init(const Ty &Val)
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.
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
scc_iterator< T > scc_end(const T &G)
Construct the end iterator for a deduced graph type T.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Determine the kind of a node from its type.
A special type used by analysis passes to provide an address that identifies that particular analysis...
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...