22#define DEBUG_TYPE "dgb"
24STATISTIC(TotalGraphs,
"Number of dependence graphs created.");
25STATISTIC(TotalDefUseEdges,
"Number of def-use edges created.");
26STATISTIC(TotalMemoryEdges,
"Number of memory dependence edges created.");
27STATISTIC(TotalFineGrainedNodes,
"Number of fine-grained nodes created.");
28STATISTIC(TotalPiBlockNodes,
"Number of pi-block nodes created.");
30 "Number of confused memory dependencies between two nodes.");
32 "Number of times the source and sink of dependence was reversed to "
33 "expose cycles in the graph.");
44 size_t NextOrdinal = 1;
45 for (
auto *BB : BBList)
47 InstOrdinalMap.insert(std::make_pair(&
I, NextOrdinal++));
53 assert(IMap.empty() &&
"Expected empty instruction map at start");
56 auto &NewNode = createFineGrainedNode(
I);
57 IMap.insert(std::make_pair(&
I, &NewNode));
58 NodeOrdinalMap.insert(std::make_pair(&NewNode, getOrdinal(
I)));
59 ++TotalFineGrainedNodes;
80 auto &RootNode = createRootNode();
82 for (
auto *
N : Graph) {
87 createRootedEdge(RootNode, *
N);
92 if (!shouldCreatePiBlocks())
118 for (NodeListType &
NL : ListOfSCCs) {
120 <<
" nodes in it.\n");
126 return getOrdinal(*LHS) < getOrdinal(*RHS);
129 NodeType &PiNode = createPiBlock(
NL);
138 for (NodeType *
N : Graph) {
141 if (*
N == PiNode || NodesInSCC.count(
N))
158 using EdgeKind =
typename EdgeType::EdgeKind;
165 case EdgeKind::RegisterDefUse:
166 createDefUseEdge(Src, Dst);
168 case EdgeKind::MemoryDependence:
169 createMemoryEdge(Src, Dst);
171 case EdgeKind::Rooted:
172 createRootedEdge(Src, Dst);
181 if (!Src->hasEdgeTo(*Dst))
184 dbgs() <<
"reconnecting("
185 << (Dir == Direction::Incoming ?
"incoming)" :
"outgoing)")
186 <<
":\nSrc:" << *Src <<
"\nDst:" << *Dst <<
"\nNew:" << *New
188 assert((Dir == Direction::Incoming || Dir == Direction::Outgoing) &&
189 "Invalid direction.");
192 Src->findEdgesTo(*Dst, EL);
193 for (EdgeType *OldEdge : EL) {
194 EdgeKind
Kind = OldEdge->getKind();
195 if (!EdgeAlreadyCreated[Dir][Kind]) {
196 if (Dir == Direction::Incoming) {
197 createEdgeOfKind(*Src, *New, Kind);
199 }
else if (Dir == Direction::Outgoing) {
200 createEdgeOfKind(*New, *Dst, Kind);
203 EdgeAlreadyCreated[Dir][
Kind] =
true;
205 Src->removeEdge(*OldEdge);
206 destroyEdge(*OldEdge);
207 LLVM_DEBUG(
dbgs() <<
"removed old edge between Src and Dst.\n\n");
211 for (NodeType *SCCNode :
NL) {
213 reconnectEdges(
N, SCCNode, &PiNode, Direction::Incoming);
216 reconnectEdges(SCCNode,
N, &PiNode, Direction::Outgoing);
222 InstOrdinalMap.clear();
223 NodeOrdinalMap.clear();
229 for (NodeType *
N : Graph) {
231 N->collectInstructions([](
const Instruction *
I) {
return true; }, SrcIList);
239 for (
User *U :
II->users()) {
243 NodeType *DstNode =
nullptr;
244 if (IMap.find(UI) != IMap.end())
245 DstNode = IMap.find(UI)->second;
254 <<
"skipped def-use edge since the sink" << *UI
255 <<
" is outside the range of instructions being considered.\n");
263 <<
"skipped def-use edge since the sink and the source ("
264 <<
N <<
") are the same.\n");
268 if (VisitedTargets.
insert(DstNode).second) {
269 createDefUseEdge(*
N, *DstNode);
279 using DGIterator =
typename G::iterator;
281 return I->mayReadOrWriteMemory();
283 for (DGIterator SrcIt = Graph.begin(), E = Graph.end(); SrcIt != E; ++SrcIt) {
285 (*SrcIt)->collectInstructions(isMemoryAccess, SrcIList);
286 if (SrcIList.
empty())
289 for (DGIterator DstIt = SrcIt; DstIt != E; ++DstIt) {
290 if (**SrcIt == **DstIt)
293 (*DstIt)->collectInstructions(isMemoryAccess, DstIList);
294 if (DstIList.
empty())
296 bool ForwardEdgeCreated =
false;
297 bool BackwardEdgeCreated =
false;
300 auto D = DI.depends(ISrc, IDst,
true);
310 auto createConfusedEdges = [&](NodeType &Src, NodeType &Dst) {
311 if (!ForwardEdgeCreated) {
312 createMemoryEdge(Src, Dst);
315 if (!BackwardEdgeCreated) {
316 createMemoryEdge(Dst, Src);
319 ForwardEdgeCreated = BackwardEdgeCreated =
true;
320 ++TotalConfusedEdges;
323 auto createForwardEdge = [&](NodeType &Src, NodeType &Dst) {
324 if (!ForwardEdgeCreated) {
325 createMemoryEdge(Src, Dst);
328 ForwardEdgeCreated =
true;
331 auto createBackwardEdge = [&](NodeType &Src, NodeType &Dst) {
332 if (!BackwardEdgeCreated) {
333 createMemoryEdge(Dst, Src);
336 BackwardEdgeCreated =
true;
340 createConfusedEdges(**SrcIt, **DstIt);
341 else if (
D->isOrdered() && !
D->isLoopIndependent()) {
342 bool ReversedEdge =
false;
343 for (
unsigned Level = 1; Level <=
D->getLevels(); ++Level) {
347 createBackwardEdge(**SrcIt, **DstIt);
349 ++TotalEdgeReversals;
354 createConfusedEdges(**SrcIt, **DstIt);
359 createForwardEdge(**SrcIt, **DstIt);
361 createForwardEdge(**SrcIt, **DstIt);
364 if (ForwardEdgeCreated && BackwardEdgeCreated)
371 if (ForwardEdgeCreated && BackwardEdgeCreated)
379 if (!shouldSimplify())
394 for (NodeType *
N : Graph) {
395 if (
N->getEdges().size() != 1)
397 EdgeType &Edge =
N->back();
398 if (!Edge.isDefUse())
400 CandidateSourceNodes.
insert(
N);
404 TargetInDegreeMap.
insert({&Edge.getTargetNode(), 0});
408 dbgs() <<
"Size of candidate src node list:" << CandidateSourceNodes.
size()
409 <<
"\nNode with single outgoing def-use edge:\n";
410 for (NodeType *
N : CandidateSourceNodes) {
415 for (NodeType *
N : Graph) {
416 for (EdgeType *E : *
N) {
417 NodeType *Tgt = &E->getTargetNode();
418 auto TgtIT = TargetInDegreeMap.
find(Tgt);
419 if (TgtIT != TargetInDegreeMap.
end())
425 dbgs() <<
"Size of target in-degree map:" << TargetInDegreeMap.
size()
426 <<
"\nContent of in-degree map:\n";
427 for (
auto &
I : TargetInDegreeMap) {
428 dbgs() <<
I.first <<
" --> " <<
I.second <<
"\n";
433 CandidateSourceNodes.
end());
434 while (!Worklist.empty()) {
435 NodeType &Src = *Worklist.pop_back_val();
438 if (!CandidateSourceNodes.
erase(&Src))
441 assert(Src.getEdges().size() == 1 &&
442 "Expected a single edge from the candidate src node.");
443 NodeType &Tgt = Src.back().getTargetNode();
444 assert(TargetInDegreeMap.
find(&Tgt) != TargetInDegreeMap.
end() &&
445 "Expected target to be in the in-degree map.");
447 if (TargetInDegreeMap[&Tgt] != 1)
450 if (!areNodesMergeable(Src, Tgt))
455 if (Tgt.hasEdgeTo(Src))
458 LLVM_DEBUG(
dbgs() <<
"Merging:" << Src <<
"\nWith:" << Tgt <<
"\n");
460 mergeNodes(Src, Tgt);
472 if (CandidateSourceNodes.
erase(&Tgt)) {
473 Worklist.push_back(&Src);
474 CandidateSourceNodes.
insert(&Src);
475 LLVM_DEBUG(
dbgs() <<
"Putting " << &Src <<
" back in the worklist.\n");
485 if (!shouldCreatePiBlocks())
489 using NodeKind =
typename NodeType::NodeKind;
491 if (
N->getKind() == NodeKind::PiBlock) {
500 size_t OldSize = Graph.Nodes.size();
503 if (Graph.Nodes.size() != OldSize)
505 "Expected the number of nodes to stay the same after the sort");
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
This file builds on the ADT/GraphTraits.h file to build generic depth first graph iterator.
This file defines an array type that can be indexed using scoped enum values.
uint64_t IntrinsicInst * II
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
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())
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
This abstract builder class defines a set of high-level steps for creating DDG-like graphs.
void createAndConnectRootNode()
Create a root node and add edges such that each node in the graph is reachable from the root.
void computeInstructionOrdinals()
Compute ordinal numbers for each instruction and store them in a map for future look up.
void sortNodesTopologically()
Topologically sort the graph nodes.
void createFineGrainedNodes()
Create fine grained nodes.
void createMemoryDependencyEdges()
Analyze data dependencies that exist between memory loads or stores, in the graph nodes and create ed...
void simplify()
Go through all the nodes in the graph and collapse any two nodes 'a' and 'b' if all of the following ...
void createDefUseEdges()
Analyze the def-use chains and create edges from the nodes containing definitions to the nodes contai...
void createPiBlocks()
Apply graph abstraction to groups of nodes that belong to a strongly connected component of the graph...
LLVM Basic Block Representation.
iterator find(const_arg_type_t< KeyT > Val)
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...
bool erase(PtrType Ptr)
Remove pointer from the set.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
reference emplace_back(ArgTypes &&... Args)
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
NodeType
ISD::NodeType enum - This enum defines the target-independent operators for a SelectionDAG.
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< df_ext_iterator< T, SetTy > > depth_first_ext(const T &G, SetTy &S)
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 range R to container C.
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
iterator_range< po_iterator< T > > post_order(const T &G)
auto reverse(ContainerTy &&C)
void sort(IteratorTy Start, IteratorTy End)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
scc_iterator< T > scc_end(const T &G)
Construct the end iterator for a deduced graph type T.
Incoming for lane maks phi as machine instruction, incoming register Reg and incoming block Block are...
Direction
An enum for the direction of the loop.