1 /*========================== begin_copyright_notice ============================
2 
3 Copyright (C) 2019-2021 Intel Corporation
4 
5 SPDX-License-Identifier: MIT
6 
7 ============================= end_copyright_notice ===========================*/
8 
9 #ifndef _VARSPLIT_H_
10 #define _VARSPLIT_H_
11 
12 #include "FlowGraph.h"
13 #include "BuildIR.h"
14 #include "RPE.h"
15 
16 namespace vISA
17 {
18 class LiveRange;
19 class GraphColor;
20 class RPE;
21 class GlobalRA;
22 
23 // store mapping of a split variable to original variable. if any split
24 // variable is spilled, we can reuse spill location of original variable.
25 // also store all instructions emitted in preheader, loop exit for each
26 // split variable. this helps eliminate those instruction in case the
27 // split variable itself spills.
28 class SplitResults
29 {
30 public:
31     G4_Declare* origDcl = nullptr;
32     std::unordered_map<G4_BB*, std::unordered_set<G4_INST*>> insts;
33 };
34 
35 class LoopVarSplit
36 {
37 public:
38     LoopVarSplit(G4_Kernel& k, GraphColor* c, RPE* r);
39 
40     void run();
41 
42     std::vector<G4_SrcRegRegion*> getReads(G4_Declare* dcl, Loop& loop);
43     std::vector<G4_DstRegRegion*> getWrites(G4_Declare* dcl, Loop& loop);
44     unsigned int getMaxRegPressureInLoop(Loop& loop);
45     void dump(std::ostream& of = std::cerr);
46 
47     static void removeSplitInsts(GlobalRA* gra, G4_Declare* spillDcl, G4_BB* bb);
48     static bool removeFromPreheader(GlobalRA* gra, G4_Declare* spillDcl, G4_BB* bb, INST_LIST_ITER filledInstIter);
49     static bool removeFromLoopExit(GlobalRA* gra, G4_Declare* spillDcl, G4_BB* bb, INST_LIST_ITER filledInstIter);
50     static const std::unordered_set<G4_INST*> getSplitInsts(GlobalRA* gra, G4_BB* bb);
51 
52 private:
53     bool split(G4_Declare* dcl, Loop& loop);
54     void copy(G4_BB* bb, G4_Declare* dst, G4_Declare* src, SplitResults* splitData, bool pushBack = true);
55     void replaceSrc(G4_SrcRegRegion* src, G4_Declare* dcl);
56     void replaceDst(G4_DstRegRegion* dst, G4_Declare* dcl);
57     G4_Declare* getNewDcl(G4_Declare* dcl1, G4_Declare* dcl2);
58     std::vector<Loop*> getLoopsToSplitAround(G4_Declare* dcl);
59 
60     G4_Kernel& kernel;
61     GraphColor* coloring = nullptr;
62     RPE* rpe = nullptr;
63     VarReferences references;
64 
65     // store set of dcls marked as spill in current RA iteration
66     std::unordered_set<G4_Declare*> spilledDclSet;
67 
68     // store spill cost for each dcl
69     std::map<G4_Declare*, float> dclSpillCost;
70 
71     std::unordered_map<G4_Declare*, G4_Declare*> oldNewDcl;
72 
73     std::unordered_map<Loop*, std::unordered_set<G4_Declare*>> splitsPerLoop;
74 
75     std::unordered_map<Loop*, unsigned int> maxRegPressureCache;
76 
77     // a spilled dcl may be split multiple times, once per loop
78     // store this information to uplevel to GlobalRA class so
79     // anytime we spill a split variable, we reuse spill location.
80     // Orig dcl, vector<Tmp Dcl, Loop>
81     std::unordered_map<G4_Declare*, std::vector<std::pair<G4_Declare*, Loop*>>> splitResults;
82 };
83 
84 class VarProperties
85 {
86 public:
87     enum class AccessGranularity
88     {
89         OneGrf = 1,
90         TwoGrf = 2,
91         Unknown = 3
92     };
93 
94     AccessGranularity ag = AccessGranularity::Unknown;
95     unsigned int numDefs = 0;
96     std::pair<G4_DstRegRegion*, G4_BB*> def;
97     std::vector<std::pair<G4_SrcRegRegion*, G4_BB*>> srcs;
98     bool candidateDef = false;
99     bool legitCandidate = true;
100 
101     // API to check whether variable is local or global
isDefUsesInSameBB()102     bool isDefUsesInSameBB()
103     {
104         auto defBB = def.second;
105         for (auto src : srcs)
106         {
107             if (src.second != defBB)
108                 return false;
109         }
110         return true;
111     }
112 
isPartDclUsed(unsigned int lb,unsigned int rb)113     bool isPartDclUsed(unsigned int lb, unsigned int rb)
114     {
115         // Return true if lb/rb is part of any src regions
116         for (auto& src : srcs)
117         {
118             if (src.first->getLeftBound() >= lb &&
119                 src.first->getRightBound() <= rb)
120                 return true;
121         }
122         return false;
123     }
124 };
125 
126 class VarSplitPass
127 {
128 public:
129     VarSplitPass(G4_Kernel&);
130 
131     void run();
132     void replaceIntrinsics();
133     G4_Declare* getParentDcl(G4_Declare*);
134     std::vector<G4_Declare*>* getChildren(G4_Declare*);
135     std::vector<G4_Declare*> getSiblings(G4_Declare*);
136     bool isSplitDcl(G4_Declare*);
137     bool isPartialDcl(G4_Declare*);
138     unsigned int getSiblingNum(G4_Declare*);
139     unsigned int getIdealAllocation(G4_Declare*, LiveRange**);
140     bool isChildDclUnused(G4_Declare*);
141     void writeHints(G4_Declare*, LiveRange**);
142     void undo(G4_Declare*);
143     bool reallocParent(G4_Declare*, LiveRange**);
144     bool isParentChildRelation(G4_Declare*, G4_Declare*);
145     bool isSplitVarLocal(G4_Declare*);
splitOccured()146     bool splitOccured() { return IRchanged; }
147 
148 private:
149     G4_Kernel& kernel;
150 
151     void findSplitCandidates();
152     void split();
153     std::unordered_map<G4_Declare*, VarProperties> splitVars;
154     // split dcl, parent dcl
155     std::unordered_map<G4_Declare*, G4_Declare*> splitParentDcl;
156     // parent dcl, vector<children>
157     std::unordered_map<G4_Declare*, std::vector<G4_Declare*>> splitChildren;
158     // Store child dcls that are never referenced in CFG
159     std::unordered_set<G4_Declare*> unusedDcls;
160     // Store pre-split regions for undo
161     // <new src/dst region, <old src inst, old src rgn, old src#>>
162     std::unordered_map<G4_Operand*, std::tuple<G4_INST*, G4_Operand*, unsigned int>> preSplit;
163     bool IRchanged = false;
164 
165 private:
166     // Split verification related declarations
167     void buildPreVerify();
168     void verify();
169     void verifyOverlap();
170 
171     class InstData
172     {
173     public:
174         G4_DstRegRegion* dst = nullptr;
175         unsigned int dstLb = 0;
176         unsigned int dstRb = 0;
177         G4_Operand* src[G4_MAX_SRCS];
178         unsigned int srcLb[G4_MAX_SRCS];
179         unsigned int srcRb[G4_MAX_SRCS];
180 
InstData()181         InstData()
182         {
183             for (unsigned int i = 0; i != G4_MAX_SRCS; i++)
184             {
185                 src[i] = nullptr;
186                 srcLb[i] = 0;
187                 srcRb[i] = 0;
188             }
189         }
190     };
191     std::unordered_map<G4_INST*, InstData> splitVerify;
192 };
193 };
194 #endif
195