1 /*
2 * Copyright (c) 2023 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #ifndef MAPLEBE_CG_INCLUDE_CG_SSA_H
17 #define MAPLEBE_CG_INCLUDE_CG_SSA_H
18
19 #include "cgfunc.h"
20 #include "cg_dominance.h"
21 #include "live.h"
22 #include "operand.h"
23 #include "visitor_common.h"
24
25 namespace maplebe {
26 class CGSSAInfo;
27 enum SSAOpndDefBy { kDefByNo, kDefByInsn, kDefByPhi };
28
29 /* precise def/use info in machine instrcution */
30 class DUInsnInfo {
31 public:
DUInsnInfo(Insn * cInsn,uint32 cIdx,MapleAllocator & alloc)32 DUInsnInfo(Insn *cInsn, uint32 cIdx, MapleAllocator &alloc) : insn(cInsn), DUInfo(alloc.Adapter())
33 {
34 IncreaseDU(cIdx);
35 }
IncreaseDU(uint32 idx)36 void IncreaseDU(uint32 idx)
37 {
38 if (!DUInfo.count(idx)) {
39 DUInfo[idx] = 0;
40 }
41 DUInfo[idx]++;
42 }
DecreaseDU(uint32 idx)43 void DecreaseDU(uint32 idx)
44 {
45 DEBUG_ASSERT(DUInfo[idx] > 0, "no def/use any more");
46 DUInfo[idx]--;
47 }
ClearDU(uint32 idx)48 void ClearDU(uint32 idx)
49 {
50 DEBUG_ASSERT(DUInfo.count(idx), "no def/use find");
51 DUInfo[idx] = 0;
52 }
HasNoDU()53 bool HasNoDU()
54 {
55 for (auto it : DUInfo) {
56 if (it.second != 0) {
57 return false;
58 }
59 }
60 return true;
61 }
GetInsn()62 Insn *GetInsn()
63 {
64 return insn;
65 }
GetOperands()66 MapleMap<uint32, uint32> &GetOperands()
67 {
68 return DUInfo;
69 }
70
71 private:
72 Insn *insn;
73 /* operand idx --- count */
74 MapleMap<uint32, uint32> DUInfo;
75 };
76
77 class VRegVersion {
78 public:
VRegVersion(const MapleAllocator & alloc,RegOperand & vReg,uint32 vIdx,regno_t vregNO)79 VRegVersion(const MapleAllocator &alloc, RegOperand &vReg, uint32 vIdx, regno_t vregNO)
80 : versionAlloc(alloc),
81 ssaRegOpnd(&vReg),
82 versionIdx(vIdx),
83 originalRegNO(vregNO),
84 useInsnInfos(versionAlloc.Adapter())
85 {
86 }
SetDefInsn(DUInsnInfo * duInfo,SSAOpndDefBy defTy)87 void SetDefInsn(DUInsnInfo *duInfo, SSAOpndDefBy defTy)
88 {
89 defInsnInfo = duInfo;
90 defType = defTy;
91 }
GetDefInsnInfo()92 DUInsnInfo *GetDefInsnInfo() const
93 {
94 return defInsnInfo;
95 }
GetDefType()96 SSAOpndDefBy GetDefType() const
97 {
98 return defType;
99 }
100 RegOperand *GetSSAvRegOpnd(bool isDef = true)
101 {
102 if (!isDef) {
103 return implicitCvtedRegOpnd;
104 }
105 return ssaRegOpnd;
106 }
GetVersionIdx()107 uint32 GetVersionIdx() const
108 {
109 return versionIdx;
110 }
GetOriginalRegNO()111 regno_t GetOriginalRegNO() const
112 {
113 return originalRegNO;
114 }
115 void AddUseInsn(CGSSAInfo &ssaInfo, Insn &useInsn, uint32 idx);
116 /* elimate dead use */
117 void CheckDeadUse(const Insn &useInsn);
118 void RemoveUseInsn(const Insn &useInsn, uint32 idx);
GetAllUseInsns()119 MapleUnorderedMap<uint32, DUInsnInfo *> &GetAllUseInsns()
120 {
121 return useInsnInfos;
122 }
MarkDeleted()123 void MarkDeleted()
124 {
125 deleted = true;
126 }
MarkRecovery()127 void MarkRecovery()
128 {
129 deleted = false;
130 }
IsDeleted()131 bool IsDeleted() const
132 {
133 return deleted;
134 }
SetImplicitCvt()135 void SetImplicitCvt()
136 {
137 hasImplicitCvt = true;
138 }
HasImplicitCvt()139 bool HasImplicitCvt() const
140 {
141 return hasImplicitCvt;
142 }
143
144 private:
145 MapleAllocator versionAlloc;
146 /* if this version has implicit conversion, it refers to def reg */
147 RegOperand *ssaRegOpnd;
148 RegOperand *implicitCvtedRegOpnd = nullptr;
149 uint32 versionIdx;
150 regno_t originalRegNO;
151 DUInsnInfo *defInsnInfo = nullptr;
152 SSAOpndDefBy defType = kDefByNo;
153 /* insn ID -> insn* & operand Idx */
154 // --> vector?
155 MapleUnorderedMap<uint32, DUInsnInfo *> useInsnInfos;
156 bool deleted = false;
157 /*
158 * def reg (size:64) or def reg (size:32) -->
159 * all use reg (size:32) all use reg (size:64)
160 * do not support single use which has implicit conversion yet
161 * support single use in DUInfo in future
162 */
163 bool hasImplicitCvt = false;
164 };
165
166 class CGSSAInfo {
167 public:
CGSSAInfo(CGFunc & f,DomAnalysis & da,MemPool & mp,MemPool & tmp)168 CGSSAInfo(CGFunc &f, DomAnalysis &da, MemPool &mp, MemPool &tmp)
169 : cgFunc(&f),
170 memPool(&mp),
171 tempMp(&tmp),
172 ssaAlloc(&mp),
173 domInfo(&da),
174 renamedBBs(ssaAlloc.Adapter()),
175 vRegDefCount(ssaAlloc.Adapter()),
176 vRegStk(ssaAlloc.Adapter()),
177 allSSAOperands(ssaAlloc.Adapter()),
178 noDefVRegs(ssaAlloc.Adapter()),
179 reversePostOrder(ssaAlloc.Adapter()),
180 safePropInsns(ssaAlloc.Adapter())
181 {
182 }
183 virtual ~CGSSAInfo() = default;
184 void ConstructSSA();
185 VRegVersion *FindSSAVersion(regno_t ssaRegNO); /* Get specific ssa info */
186 /* replace insn & update ssaInfo */
187 virtual void ReplaceInsn(Insn &oriInsn, Insn &newInsn) = 0;
188 virtual void ReplaceAllUse(VRegVersion *toBeReplaced, VRegVersion *newVersion) = 0;
189 virtual void CreateNewInsnSSAInfo(Insn &newInsn) = 0;
190 PhiOperand &CreatePhiOperand();
191
CreateDUInsnInfo(Insn * cInsn,uint32 idx)192 DUInsnInfo *CreateDUInsnInfo(Insn *cInsn, uint32 idx)
193 {
194 return memPool->New<DUInsnInfo>(cInsn, idx, ssaAlloc);
195 }
GetAllSSAOperands()196 const MapleUnorderedMap<regno_t, VRegVersion *> &GetAllSSAOperands() const
197 {
198 return allSSAOperands;
199 }
IsNoDefVReg(regno_t vRegNO)200 bool IsNoDefVReg(regno_t vRegNO) const
201 {
202 return noDefVRegs.find(vRegNO) != noDefVRegs.end();
203 }
GetVersionNOOfOriginalVreg(regno_t vRegNO)204 uint32 GetVersionNOOfOriginalVreg(regno_t vRegNO)
205 {
206 if (vRegDefCount.count(vRegNO)) {
207 return vRegDefCount[vRegNO];
208 }
209 DEBUG_ASSERT(false, " original vreg is not existed");
210 return 0;
211 }
GetReversePostOrder()212 MapleVector<uint32> &GetReversePostOrder()
213 {
214 return reversePostOrder;
215 }
InsertSafePropInsn(uint32 insnId)216 void InsertSafePropInsn(uint32 insnId)
217 {
218 (void)safePropInsns.emplace_back(insnId);
219 }
GetSafePropInsns()220 MapleVector<uint32> &GetSafePropInsns()
221 {
222 return safePropInsns;
223 }
224 Insn *GetDefInsn(const RegOperand &useReg);
225 void DumpFuncCGIRinSSAForm() const;
226 virtual void DumpInsnInSSAForm(const Insn &insn) const = 0;
227 static uint32 SSARegNObase;
228
229 protected:
230 VRegVersion *CreateNewVersion(RegOperand &virtualOpnd, Insn &defInsn, uint32 idx, bool isDefByPhi = false);
231 virtual RegOperand *CreateSSAOperand(RegOperand &virtualOpnd) = 0;
232 bool IncreaseSSAOperand(regno_t vRegNO, VRegVersion *vst);
233 uint32 IncreaseVregCount(regno_t vRegNO);
234 VRegVersion *GetVersion(const RegOperand &virtualOpnd);
GetPrivateAllSSAOperands()235 MapleUnorderedMap<regno_t, VRegVersion *> &GetPrivateAllSSAOperands()
236 {
237 return allSSAOperands;
238 }
AddNoDefVReg(regno_t noDefVregNO)239 void AddNoDefVReg(regno_t noDefVregNO)
240 {
241 DEBUG_ASSERT(!noDefVRegs.count(noDefVregNO), "duplicate no def Reg, please check");
242 noDefVRegs.emplace(noDefVregNO);
243 }
244 void MarkInsnsInSSA(Insn &insn);
245 CGFunc *cgFunc = nullptr;
246 MemPool *memPool = nullptr;
247 MemPool *tempMp = nullptr;
248 MapleAllocator ssaAlloc;
249
250 private:
251 void InsertPhiInsn();
252 void RenameVariablesForBB(uint32 bbID);
253 void RenameBB(BB &bb);
254 void RenamePhi(BB &bb);
255 virtual void RenameInsn(Insn &insn) = 0;
256 /* build ssa on virtual register only */
257 virtual RegOperand *GetRenamedOperand(RegOperand &vRegOpnd, bool isDef, Insn &curInsn, uint32 idx) = 0;
258 void RenameSuccPhiUse(const BB &bb);
259 void PrunedPhiInsertion(const BB &bb, RegOperand &virtualOpnd);
260
AddRenamedBB(uint32 bbID)261 void AddRenamedBB(uint32 bbID)
262 {
263 DEBUG_ASSERT(!renamedBBs.count(bbID), "cgbb has been renamed already");
264 renamedBBs.emplace(bbID);
265 }
IsBBRenamed(uint32 bbID)266 bool IsBBRenamed(uint32 bbID) const
267 {
268 return renamedBBs.count(bbID);
269 }
270 void SetReversePostOrder();
271
272 DomAnalysis *domInfo = nullptr;
273 MapleSet<uint32> renamedBBs;
274 /* original regNO - number of definitions (start from 0) */
275 MapleMap<regno_t, uint32> vRegDefCount;
276 /* original regNO - ssa version stk */
277 MapleMap<regno_t, MapleStack<VRegVersion *>> vRegStk;
278 /* ssa regNO - ssa virtual operand version */
279 MapleUnorderedMap<regno_t, VRegVersion *> allSSAOperands;
280 /* For virtual registers which do not have definition */
281 MapleSet<regno_t> noDefVRegs;
282 /* only save bb_id to reduce space */
283 MapleVector<uint32> reversePostOrder;
284 /* destSize < srcSize but can be propagated */
285 MapleVector<uint32> safePropInsns;
286 int32 insnCount = 0;
287 };
288
289 class SSAOperandVisitor : public OperandVisitorBase, public OperandVisitors<RegOperand, ListOperand, MemOperand> {
290 public:
SSAOperandVisitor(Insn & cInsn,const OpndDesc & cDes,uint32 idx)291 SSAOperandVisitor(Insn &cInsn, const OpndDesc &cDes, uint32 idx) : insn(&cInsn), opndDes(&cDes), idx(idx) {}
292 SSAOperandVisitor() = default;
293 virtual ~SSAOperandVisitor() = default;
SetInsnOpndInfo(Insn & cInsn,const OpndDesc & cDes,uint32 index)294 void SetInsnOpndInfo(Insn &cInsn, const OpndDesc &cDes, uint32 index)
295 {
296 insn = &cInsn;
297 opndDes = &cDes;
298 this->idx = index;
299 }
300
301 protected:
302 Insn *insn = nullptr;
303 const OpndDesc *opndDes = nullptr;
304 uint32 idx = 0;
305 };
306
307 class SSAOperandDumpVisitor : public OperandVisitorBase,
308 public OperandVisitors<RegOperand, ListOperand, MemOperand>,
309 public OperandVisitor<PhiOperand> {
310 public:
SSAOperandDumpVisitor(const MapleUnorderedMap<regno_t,VRegVersion * > & allssa)311 explicit SSAOperandDumpVisitor(const MapleUnorderedMap<regno_t, VRegVersion *> &allssa) : allSSAOperands(allssa) {}
312 virtual ~SSAOperandDumpVisitor() = default;
SetHasDumped()313 void SetHasDumped()
314 {
315 hasDumped = true;
316 }
HasDumped()317 bool HasDumped() const
318 {
319 return hasDumped;
320 }
321 bool hasDumped = false;
322
323 protected:
324 const MapleUnorderedMap<regno_t, VRegVersion *> &allSSAOperands;
325 };
326
327 MAPLE_FUNC_PHASE_DECLARE_BEGIN(CgSSAConstruct, maplebe::CGFunc);
GetResult()328 CGSSAInfo *GetResult()
329 {
330 return ssaInfo;
331 }
332 CGSSAInfo *ssaInfo = nullptr;
333
334 private:
335 void GetAnalysisDependence(maple::AnalysisDep &aDep) const override;
336 MAPLE_FUNC_PHASE_DECLARE_END
337 } // namespace maplebe
338
339 #endif // MAPLEBE_CG_INCLUDE_CG_SSA_H
340