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