1 /*========================== begin_copyright_notice ============================
2
3 Copyright (C) 2021 Intel Corporation
4
5 SPDX-License-Identifier: MIT
6
7 ============================= end_copyright_notice ===========================*/
8
9 #include "SCCAnalysis.h"
10 #include "FlowGraph.h"
11
12 #include <algorithm>
13
14 using namespace vISA;
15
dump(std::ostream & os) const16 void SCCAnalysis::SCCNode::dump(std::ostream &os) const
17 {
18 os << "SCCNode: BB" << bb->getId() << ", (" << index << "," << lowLink << ")\n";
19 }
20
isMember(G4_BB * bb) const21 bool SCCAnalysis::SCC::isMember(G4_BB* bb) const {
22 return std::find(body.begin(), body.end(), bb) != body.end();
23 }
24
getEarliestBB() const25 G4_BB* SCCAnalysis::SCC::getEarliestBB() const
26 {
27 auto result = std::min_element(body.begin(), body.end(),
28 [](G4_BB* bb1, G4_BB* bb2) {return bb1->getId() < bb2->getId(); });
29 return *result;
30 }
31
dump(std::ostream & os) const32 void SCCAnalysis::SCC::dump(std::ostream &os) const
33 {
34 os << "SCC (root = BB" << root->getId() << ", size = " << getSize() << "):\t";
35 for (auto bodyBB : body)
36 {
37 os << "BB" << bodyBB->getId() << ", ";
38 }
39 os << "\n";
40 }
41
createSCCNode(G4_BB * bb)42 SCCAnalysis::SCCNode* SCCAnalysis::createSCCNode(G4_BB* bb)
43 {
44 assert(SCCNodes[bb->getId()] == nullptr && "SCCNode already exists");
45 SCCNode* newNode = new SCCNode(bb, curIndex++);
46 SCCNodes[bb->getId()] = newNode;
47 return newNode;
48 }
49
run()50 void SCCAnalysis::run()
51 {
52 SCCNodes.resize(cfg.getNumBB());
53 for (auto I = cfg.cbegin(), E = cfg.cend(); I != E; ++I)
54 {
55 auto BB = *I;
56 if (!SCCNodes[BB->getId()])
57 {
58 findSCC(createSCCNode(BB));
59 }
60 }
61 }
62
findSCC(SCCNode * node)63 void SCCAnalysis::findSCC(SCCNode* node)
64 {
65 SCCStack.push(node);
66 for (auto succBB : node->bb->Succs)
67 {
68 if (succBB == node->bb)
69 {
70 // no self loop
71 continue;
72 }
73 else if (node->bb->isEndWithCall())
74 {
75 // ignore call edges and replace it with physical succ instead
76 succBB = node->bb->getPhysicalSucc();
77 if (!succBB)
78 {
79 continue;
80 }
81 }
82 else if (node->bb->getBBType() & G4_BB_RETURN_TYPE)
83 {
84 // stop at return BB
85 // ToDo: do we generate (P) ret?
86 continue;
87 }
88 SCCNode* succNode = SCCNodes[succBB->getId()];
89 if (!succNode)
90 {
91 succNode = createSCCNode(succBB);
92 findSCC(succNode);
93 node->lowLink = std::min(node->lowLink, succNode->lowLink);
94 }
95 else if (succNode->isOnStack)
96 {
97 node->lowLink = std::min(node->lowLink, succNode->index);
98 }
99 }
100
101 // root of SCC
102 if (node->lowLink == node->index)
103 {
104 SCC newSCC(node->bb);
105 SCCNode* bodyNode = nullptr;
106 do
107 {
108 bodyNode = SCCStack.top();
109 SCCStack.pop();
110 bodyNode->isOnStack = false;
111 newSCC.addBB(bodyNode->bb);
112 } while (bodyNode != node);
113 SCCs.push_back(newSCC);
114 }
115 } // findSCC
116
dump(std::ostream & os) const117 void SCCAnalysis::dump(std::ostream &os) const
118 {
119 for (auto node : SCCNodes)
120 {
121 node->dump(os);
122 }
123 for (auto SCC : SCCs)
124 {
125 SCC.dump(os);
126 }
127 }
128