1 /*========================== begin_copyright_notice ============================
2 
3 Copyright (C) 2021 Intel Corporation
4 
5 SPDX-License-Identifier: MIT
6 
7 ============================= end_copyright_notice ===========================*/
8 
9 #pragma once
10 
11 #include "G4_IR.hpp"
12 #include <vector>
13 #include <list>
14 #include <unordered_set>
15 
16 namespace vISA
17 {
18     class G4_BB;
19     class FlowGraph;
20 
21     // Top level Analysis class that each analysis needs to inherit.
22     // Each inherited class needs to implement their own reset() and
23     // run() classes.
24     class Analysis
25     {
26     public:
setStale()27         void setStale() { stale = true; }
setValid()28         void setValid() { stale = false; }
29 
isStale()30         bool isStale() const { return stale; }
31 
32         void recomputeIfStale();
33 
34         virtual void reset() = 0;
35         virtual void run() = 0;
36         virtual void dump(std::ostream& os = std::cerr) = 0;
37     private:
38         bool stale = true;
39         // flag to avoid re-triggering of analysis run when run is already in progress
40         bool inProgress = false;
41     };
42 
43     class Dominator : public Analysis
44     {
45     public:
Dominator(G4_Kernel & k)46         Dominator(G4_Kernel& k) : kernel(k)
47         {
48         }
49 
~Dominator()50         ~Dominator()
51         {
52         }
53 
54         std::unordered_set<G4_BB*>& getDom(G4_BB*);
55         void dumpDom(std::ostream& os = std::cerr);
56         bool dominates(G4_BB* bb1, G4_BB* bb2);
57 
58     private:
59         G4_Kernel& kernel;
60         G4_BB* entryBB = nullptr;
61         std::vector<std::unordered_set<G4_BB*>> Doms;
62 
63         void runDOM();
64 
65         void reset() override;
66         void run() override;
67         void dump(std::ostream& os = std::cerr) override;
68     };
69 
70     class ImmDominator : public Analysis
71     {
72     public:
ImmDominator(G4_Kernel & k)73         ImmDominator(G4_Kernel& k) : kernel(k)
74         {
75         }
76 
~ImmDominator()77         ~ImmDominator()
78         {
79 
80         }
81 
82         std::vector<G4_BB*>& getImmDom(G4_BB*);
83         G4_BB* getCommonImmDom(const std::unordered_set<G4_BB*>& bbs);
84         G4_BB* InterSect(G4_BB* bb, int i, int k);
85         void dumpImmDom(std::ostream& os = std::cerr);
86         const std::vector<G4_BB*>& getIDoms();
87 
88     private:
89         G4_Kernel& kernel;
90         G4_BB* entryBB = nullptr;
91         std::vector<G4_BB*> iDoms;
92         std::vector<std::vector<G4_BB*>> immDoms;
93 
94         void runIDOM();
95         void updateImmDom();
96 
97         void reset() override;
98         void run() override;
99         void dump(std::ostream& os = std::cerr) override;
100     };
101 
102     class PostDom : public Analysis
103     {
104     public:
105         PostDom(G4_Kernel&);
106         std::unordered_set<G4_BB*>& getPostDom(G4_BB*);
107         std::vector<G4_BB*>& getImmPostDom(G4_BB*);
108         void dumpImmDom(std::ostream& os = std::cerr);
109 
110         G4_BB* getCommonImmDom(std::unordered_set<G4_BB*>&);
111 
112     private:
113         G4_Kernel& kernel;
114         G4_BB* exitBB = nullptr;
115         std::vector<std::unordered_set<G4_BB*>> postDoms;
116         std::vector<std::vector<G4_BB*>> immPostDoms;
117 
118         void updateImmPostDom();
119 
120         void reset() override;
121         void run() override;
122         void dump(std::ostream& os = std::cerr) override { dumpImmDom(os); }
123     };
124 
125     // Computes and stores direct references of variables.
126     // Indirects references are not computed here.
127     // Doesnt include predicates/condition modifiers.
128     class VarReferences : public Analysis
129     {
130     public:
VarReferences(G4_Kernel & k)131         VarReferences(G4_Kernel& k) : kernel(k) {}
132 
133         // Defs -> vector[tuple<inst, bb, lb, rb>]
134         // Uses -> vector[tuple<inst, bb>]
135         using Defs = std::vector<std::tuple<G4_INST*, G4_BB*, unsigned int, unsigned int>>;
136         using Uses = std::vector<std::tuple<G4_INST*, G4_BB*>>;
137 
138         bool isUniqueDef(G4_DstRegRegion* dst);
139         unsigned int getDefCount(G4_Declare* dcl);
140         unsigned int getUseCount(G4_Declare* dcl);
141         const Defs* getDefs(G4_Declare* dcl);
142         const Uses* getUses(G4_Declare* dcl);
143 
144     private:
145         // Dcl -> vector[<inst, bb, lb, rb>]
146         // this data structure helps check whether a definition or part of it
147         // has multiple definitions in the program.
148         std::unordered_map<G4_Declare*, std::pair<Defs, Uses>> VarRefs;
149         G4_Kernel& kernel;
150 
151         void reset() override;
152         void run() override;
153         void dump(std::ostream& os = std::cerr) override;
154     };
155 
156     using BackEdge = std::pair<G4_BB*, G4_BB*>;
157     using BackEdges = std::vector<BackEdge>;
158 
159     class Loop
160     {
161     public:
Loop(BackEdge b)162         Loop(BackEdge b) : be(b) {}
163 
164         Loop* parent = nullptr;
165         G4_BB* preHeader = nullptr;
166         std::vector<Loop*> immNested;
167 
168         void addBBToLoopHierarchy(G4_BB* bb);
169         void addBBToLoop(G4_BB* bb);
170 
171         unsigned int id = 0;
172 
173         std::vector<Loop*> getAllSiblings(std::vector<Loop*>& topLoops);
174 
175         // BBs not in loop are considered to have nesting level of 0.
176         // BBs in outermost loop report nesting level 1.
177         // BB in loopn reports nesting level to be 1+it's parent nesting level.
178         unsigned int getNestingLevel();
179 
180         void dump(std::ostream& os = std::cerr);
181 
182         bool contains(const G4_BB*);
183 
getBBSize()184         unsigned int getBBSize() { return BBs.size(); }
185 
getHeader()186         G4_BB* getHeader() { return be.second; }
187 
188         bool fullSubset(Loop* other);
189         bool fullSuperset(Loop* other);
190 
191         Loop* getInnerMostLoop(const G4_BB* bb);
192 
193         std::vector<G4_BB*>& getLoopExits();
194 
getBBs()195         const std::vector<G4_BB*>& getBBs() { return BBs; }
196 
197     private:
198         std::vector<G4_BB*> BBs;
199         std::unordered_set<const G4_BB*> BBsLookup;
200         BackEdge be;
201         std::vector<G4_BB*> loopExits;
202     };
203 
204     class FuncInfo;
205 
206     class LoopDetection : public Analysis
207     {
208     public:
209         LoopDetection(G4_Kernel&);
210 
211         std::vector<Loop*> getTopLoops();
212         Loop* getInnerMostLoop(const G4_BB*);
213         void computePreheaders();
214 
215     private:
216         std::vector<Loop*> topLoops;
217         // list owns memory, so no need for dynamic allocation
218         std::list<Loop> allLoops;
219 
220         // store G4_BB -> <preId, rpostId>
221         std::unordered_map<const G4_BB*, std::pair<unsigned int, unsigned int>> PreIdRPostId;
222 
223         G4_Kernel& kernel;
224         FlowGraph& fg;
225 
226         void reset() override;
227         void run() override;
228         void dump(std::ostream& os = std::cerr) override;
229 
230         void DFSTraverse(const G4_BB* startBB, unsigned& preId, unsigned& postId, BackEdges& bes);
231         void findDominatingBackEdges(BackEdges& bes);
232         void populateLoop(BackEdge&);
233         void computeLoopTree();
234         void addLoop(Loop* newLoop, Loop* aParent);
235         G4_BB* getPreheader(Loop* loop);
236     };
237 }
238 
239