1 /*========================== begin_copyright_notice ============================
2 
3 Copyright (C) 2021 Intel Corporation
4 
5 SPDX-License-Identifier: MIT
6 
7 ============================= end_copyright_notice ===========================*/
8 
9 #ifndef SCC_ANALYSIS
10 #define SCC_ANALYSIS
11 
12 #include "FlowGraph.h"
13 
14 #include <ostream>
15 #include <stack>
16 #include <vector>
17 
18 namespace vISA
19 {
20 class SCCAnalysis
21 {
22     //
23     // implements Tarjan's SCC algorithm
24     //
25     const FlowGraph& cfg;
26 
27     // node used during the SCC algorithm
28     struct SCCNode
29     {
30         G4_BB* bb;
31         int index;
32         int lowLink;
33         bool isOnStack;
34 
SCCNodeSCCNode35         SCCNode(G4_BB* newBB, int curIndex)
36             : bb(newBB), index(curIndex), lowLink(curIndex), isOnStack(true) { }
37         void dump(std::ostream &os = std::cerr) const;
38     };
39 
40     int curIndex = 0;
41 
42     std::stack<SCCNode*> SCCStack;
43     std::vector<SCCNode*> SCCNodes; // 1:1 mapping between SCCNode and BB, indexed by BBId
44 
45     class SCC
46     {
47         G4_BB* root;
48         // list of BBs belonging to the SCC (including root as last BB)
49         // assumption is SCC is small (10s of BBs) so membership test is cheap
50         std::vector<G4_BB*> body;
51 
52     public:
SCC(G4_BB * bb)53         SCC(G4_BB* bb) : root(bb) {} // root gets pushed to body just like other BBs in SCC
addBB(G4_BB * bb)54         void addBB(G4_BB* bb) { body.push_back(bb); }
body_begin()55         std::vector<G4_BB*>::iterator body_begin() { return body.begin(); }
body_end()56         std::vector<G4_BB*>::iterator body_end() { return body.end(); }
getSize()57         size_t getSize() const { return body.size(); }
58         bool isMember(G4_BB* bb) const;
59         // get earliest BB in program order (this is not necessarily the root depending on DFS order)
60         // assumption is reassingBBId() is called
61         G4_BB* getEarliestBB() const;
62         void dump(std::ostream &os = std::cerr) const;
63     }; // SCC
64 
65     std::vector<SCC> SCCs;
66 
67 public:
SCCAnalysis(const FlowGraph & fg)68     SCCAnalysis(const FlowGraph& fg) : cfg(fg) { }
~SCCAnalysis()69     ~SCCAnalysis() {for (auto node : SCCNodes) {delete node;}}
70 
71     void run();
72     void findSCC(SCCNode* node);
73 
74     SCCNode* createSCCNode(G4_BB* bb);
75 
SCC_begin()76     std::vector<SCC>::iterator SCC_begin() { return SCCs.begin(); }
SCC_end()77     std::vector<SCC>::iterator SCC_end() { return SCCs.end(); }
getNumSCC()78     size_t getNumSCC() const { return SCCs.size(); }
79 
80     void dump(std::ostream &os = std::cerr) const;
81 }; // class SCCAnalysis
82 }
83 #endif // SCC_ANALYSIS
84