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 #include "live.h"
17 #include <set>
18 #include "cg.h"
19 #include "cg_option.h"
20 #include "cgfunc.h"
21 
22 /*
23  * This phase build two sets: liveOutRegno and liveInRegno of each BB.
24  * This algorithm mainly include 3 parts:
25  * 1. initialize and get def[]/use[] of each BB;
26  * 2. build live_in and live_out based on this algorithm
27  *   Out[B] = U In[S] //S means B's successor;
28  *   In[B] = use[B] U (Out[B]-def[B]);
29  * 3. deal with cleanup BB.
30  */
31 namespace maplebe {
32 #define LIVE_ANALYZE_DUMP_NEWPM CG_DEBUG_FUNC(f)
33 
InitAndGetDefUse()34 void LiveAnalysis::InitAndGetDefUse()
35 {
36     FOR_ALL_BB(bb, cgFunc)
37     {
38         InitBB(*bb);
39         GetBBDefUse(*bb);
40     }
41 }
42 
RemovePhiLiveInFromSuccNotFromThisBB(BB &curBB, BB &succBB) const43 bool LiveAnalysis::RemovePhiLiveInFromSuccNotFromThisBB(BB &curBB, BB &succBB) const
44 {
45     if (succBB.GetPhiInsns().empty()) {
46         return false;
47     }
48     LocalMapleAllocator allocator(cgFunc->GetStackMemPool());
49     SparseDataInfo tempPhiIn(succBB.GetLiveIn()->GetMaxRegNum(), allocator);
50     tempPhiIn.ResetAllBit();
51     for (auto phiInsnIt : succBB.GetPhiInsns()) {
52         auto &phiList = static_cast<PhiOperand &>(phiInsnIt.second->GetOperand(kInsnSecondOpnd));
53         for (auto phiOpndIt : phiList.GetOperands()) {
54             uint32 fBBId = phiOpndIt.first;
55             DEBUG_ASSERT(fBBId != 0, "GetFromBBID = 0");
56             if (fBBId != curBB.GetId()) {
57                 regno_t regNo = phiOpndIt.second->GetRegisterNumber();
58                 tempPhiIn.SetBit(regNo);
59             }
60         }
61     }
62     return curBB.GetLiveOut()->Difference(tempPhiIn);
63 }
64 
65 /* Out[BB] = Union all of In[Succs(BB)]
66  *
67  * in ssa form
68  * Out[BB] = Union all of In[Succs(BB)] Except Phi use reg dont from this BB
69  */
GenerateLiveOut(BB &bb) const70 bool LiveAnalysis::GenerateLiveOut(BB &bb) const
71 {
72     bool isChanged = false;
73     for (auto succBB : bb.GetSuccs()) {
74         if (succBB->GetLiveInChange() && !succBB->GetLiveIn()->NoneBit()) {
75             isChanged = bb.LiveOutOrBits(*succBB->GetLiveIn()) || isChanged;
76             isChanged = RemovePhiLiveInFromSuccNotFromThisBB(bb, *succBB) || isChanged;
77         }
78     }
79     return isChanged;
80 }
81 
82 /* In[BB] = use[BB] Union (Out[BB]-def[BB]) */
GenerateLiveIn(BB &bb)83 bool LiveAnalysis::GenerateLiveIn(BB &bb)
84 {
85     bool isChanged = false;
86     LocalMapleAllocator allocator(cgFunc->GetStackMemPool());
87     if (!bb.GetInsertUse()) {
88         if (!bb.GetLiveIn()->IsEqual(*bb.GetUse())) {
89             bb.SetLiveInInfo(*bb.GetUse());
90             isChanged = true;
91         }
92         bb.SetInsertUse(true);
93     }
94     SparseDataInfo &bbLiveOut = bb.GetLiveOut()->Clone(allocator);
95     if (!bbLiveOut.NoneBit()) {
96         bbLiveOut.Difference(*bb.GetDef());
97         isChanged = bb.LiveInOrBits(bbLiveOut) || isChanged;
98     }
99     return isChanged;
100 }
101 
GenerateLiveInByDefUse(SparseDataInfo &liveOut, SparseDataInfo &use, SparseDataInfo &def)102 SparseDataInfo *LiveAnalysis::GenerateLiveInByDefUse(SparseDataInfo &liveOut, SparseDataInfo &use, SparseDataInfo &def)
103 {
104     SparseDataInfo *liveIn = &use;
105     LocalMapleAllocator allocator(cgFunc->GetStackMemPool());
106     SparseDataInfo *tmpLiveOut = memPool->New<SparseDataInfo>(liveOut, allocator);
107     if (!liveOut.NoneBit()) {
108         tmpLiveOut->Difference(def);
109         liveIn->OrBits(*tmpLiveOut);
110     }
111     return liveIn;
112 }
113 
GenerateStackMapLiveIn()114 void LiveAnalysis::GenerateStackMapLiveIn()
115 {
116     const auto &stackMapInsns = cgFunc->GetStackMapInsns();
117     for (auto *insn : stackMapInsns) {
118         BB *curBB = insn->GetBB();
119         SparseDataInfo *liveIn =
120             GenerateLiveInByDefUse(*curBB->GetLiveOut(), *insn->GetStackMapUse(), *insn->GetStackMapDef());
121         insn->SetStackMapLiveIn(*liveIn);
122     }
123 }
124 /* building liveIn and liveOut of each BB. */
BuildInOutforFunc()125 void LiveAnalysis::BuildInOutforFunc()
126 {
127     iteration = 0;
128     bool hasChange;
129     do {
130         ++iteration;
131         hasChange = false;
132         FOR_ALL_BB_REV(bb, cgFunc)
133         {
134             if (!bb || bb->IsUnreachable() || !bb->GetLiveOut() || !bb->GetLiveIn()) {
135                 continue;
136             }
137             if (!GenerateLiveOut(*bb) && bb->GetInsertUse()) {
138                 continue;
139             }
140             if (GenerateLiveIn(*bb)) {
141                 bb->SetLiveInChange(true);
142                 hasChange = true;
143             } else {
144                 bb->SetLiveInChange(false);
145             }
146         }
147     } while (hasChange);
148 }
149 
150 /*  reset to liveout/in_regno */
ResetLiveSet()151 void LiveAnalysis::ResetLiveSet()
152 {
153     FOR_ALL_BB(bb, cgFunc)
154     {
155         bb->GetLiveIn()->GetBitsOfInfo<MapleSet<uint32>>(bb->GetLiveInRegNO());
156         bb->GetLiveOut()->GetBitsOfInfo<MapleSet<uint32>>(bb->GetLiveOutRegNO());
157     }
158 }
159 
160 /* entry function for LiveAnalysis */
AnalysisLive()161 void LiveAnalysis::AnalysisLive()
162 {
163     InitAndGetDefUse();
164     BuildInOutforFunc();
165     if (!cgFunc->IsStackMapComputed()) {
166         GenerateStackMapLiveIn();
167     }
168 }
169 
MarkStackMapInsn(Insn &insn, BB &bb) const170 void LiveAnalysis::MarkStackMapInsn(Insn &insn, BB &bb) const
171 {
172     if (insn.GetStackMap() != nullptr) {
173         for (auto [deoptVreg, opnd] : insn.GetStackMap()->GetDeoptInfo().GetDeoptBundleInfo()) {
174             CollectLiveInfo(bb, *opnd, false, true);
175         }
176     }
177     insn.SetStackMapDef(*NewDef(*bb.GetDef()));
178     insn.SetStackMapUse(*NewUse(*bb.GetUse()));
179 }
180 
181 /*
182  * entry of get def/use of bb.
183  * getting the def or use info of each regopnd as parameters of CollectLiveInfo().
184  */
GetBBDefUse(BB &bb) const185 void LiveAnalysis::GetBBDefUse(BB &bb) const
186 {
187     if (bb.GetKind() == BB::kBBReturn) {
188         GenerateReturnBBDefUse(bb);
189     }
190     if (!bb.HasMachineInsn()) {
191         return;
192     }
193     bb.DefResetAllBit();
194     bb.UseResetAllBit();
195 
196     FOR_BB_INSNS_REV(insn, &bb)
197     {
198         if (!insn->IsMachineInstruction()) {
199             continue;
200         }
201 
202         if (insn->IsCall() && !cgFunc->IsStackMapComputed()) {
203             MarkStackMapInsn(*insn, bb);
204         }
205 
206         bool isAsm = insn->IsAsmInsn();
207         const InsnDesc *md = insn->GetDesc();
208         if (insn->IsCall() || insn->IsTailCall()) {
209             ProcessCallInsnParam(bb, *insn);
210         }
211         uint32 opndNum = insn->GetOperandSize();
212         for (uint32 i = 0; i < opndNum; ++i) {
213             const OpndDesc *opndDesc = md->GetOpndDes(i);
214             DEBUG_ASSERT(opndDesc != nullptr, "null ptr check");
215             Operand &opnd = insn->GetOperand(i);
216             if (opnd.IsList()) {
217                 if (isAsm) {
218                     ProcessAsmListOpnd(bb, opnd, i);
219                 } else {
220                     ProcessListOpnd(bb, opnd, opndDesc->IsDef());
221                 }
222             } else if (opnd.IsMemoryAccessOperand()) {
223                 ProcessMemOpnd(bb, opnd);
224             } else if (opnd.IsConditionCode()) {
225                 ProcessCondOpnd(bb);
226             } else if (opnd.IsPhi()) {
227                 auto &phiOpnd = static_cast<PhiOperand &>(opnd);
228                 for (auto opIt : phiOpnd.GetOperands()) {
229                     CollectLiveInfo(bb, *opIt.second, false, true);
230                 }
231             } else {
232                 bool isDef = opndDesc->IsRegDef();
233                 bool isUse = opndDesc->IsRegUse();
234                 CollectLiveInfo(bb, opnd, isDef, isUse);
235             }
236         }
237     }
238 }
239 
240 /* build use and def sets of each BB according to the type of regOpnd. */
CollectLiveInfo(BB &bb, const Operand &opnd, bool isDef, bool isUse) const241 void LiveAnalysis::CollectLiveInfo(BB &bb, const Operand &opnd, bool isDef, bool isUse) const
242 {
243     if (!opnd.IsRegister()) {
244         return;
245     }
246     auto &regOpnd = static_cast<const RegOperand &>(opnd);
247     regno_t regNO = regOpnd.GetRegisterNumber();
248     RegType regType = regOpnd.GetRegisterType();
249     if (regType == kRegTyVary) {
250         return;
251     }
252     if (isDef) {
253         bb.SetDefBit(regNO);
254         if (!isUse) {
255             bb.UseResetBit(regNO);
256         }
257     }
258     if (isUse) {
259         bb.SetUseBit(regNO);
260         bb.DefResetBit(regNO);
261     }
262     if (!cgFunc->IsStackMapComputed() && regOpnd.GetBaseRefOpnd() != nullptr) {
263         const RegOperand &baseOpnd = *regOpnd.GetBaseRefOpnd();
264         regno_t baseRegNO = baseOpnd.GetRegisterNumber();
265         bb.SetUseBit(baseRegNO);
266         bb.DefResetBit(baseRegNO);
267     }
268 }
269 
ProcessAsmListOpnd(BB &bb, Operand &opnd, uint32 idx) const270 void LiveAnalysis::ProcessAsmListOpnd(BB &bb, Operand &opnd, uint32 idx) const
271 {
272     bool isDef = false;
273     bool isUse = false;
274     switch (idx) {
275         case kAsmOutputListOpnd:
276         case kAsmClobberListOpnd: {
277             isDef = true;
278             break;
279         }
280         case kAsmInputListOpnd: {
281             isUse = true;
282             break;
283         }
284         default:
285             return;
286     }
287     ListOperand &listOpnd = static_cast<ListOperand &>(opnd);
288     for (auto op : listOpnd.GetOperands()) {
289         CollectLiveInfo(bb, *op, isDef, isUse);
290     }
291 }
292 
ProcessListOpnd(BB &bb, Operand &opnd, bool isDef) const293 void LiveAnalysis::ProcessListOpnd(BB &bb, Operand &opnd, bool isDef) const
294 {
295     ListOperand &listOpnd = static_cast<ListOperand &>(opnd);
296     for (auto op : listOpnd.GetOperands()) {
297         CollectLiveInfo(bb, *op, isDef, !isDef);
298     }
299 }
300 
ProcessMemOpnd(BB &bb, Operand &opnd) const301 void LiveAnalysis::ProcessMemOpnd(BB &bb, Operand &opnd) const
302 {
303     auto &memOpnd = static_cast<MemOperand &>(opnd);
304     Operand *base = memOpnd.GetBaseRegister();
305     Operand *offset = memOpnd.GetIndexRegister();
306     if (base != nullptr) {
307         CollectLiveInfo(bb, *base, !memOpnd.IsIntactIndexed(), true);
308     }
309     if (offset != nullptr) {
310         CollectLiveInfo(bb, *offset, false, true);
311     }
312 }
313 
ProcessCondOpnd(BB &bb) const314 void LiveAnalysis::ProcessCondOpnd(BB &bb) const
315 {
316     Operand &rflag = cgFunc->GetOrCreateRflag();
317     CollectLiveInfo(bb, rflag, false, true);
318 }
319 
320 /* dump the current info of def/use/livein/liveout */
Dump() const321 void LiveAnalysis::Dump() const
322 {
323     MIRSymbol *funcSt = GlobalTables::GetGsymTable().GetSymbolFromStidx(cgFunc->GetFunction().GetStIdx().Idx());
324     DEBUG_ASSERT(funcSt != nullptr, "null ptr check");
325     LogInfo::MapleLogger() << "\n---------  liveness for " << funcSt->GetName() << "  iteration ";
326     LogInfo::MapleLogger() << iteration << " ---------\n";
327     FOR_ALL_BB(bb, cgFunc)
328     {
329         LogInfo::MapleLogger() << "  === BB_" << bb->GetId() << " (" << std::hex << bb << ") " << std::dec << " <"
330                                << bb->GetKindName();
331         if (bb->GetLabIdx() != MIRLabelTable::GetDummyLabel()) {
332             LogInfo::MapleLogger() << "[labeled with " << bb->GetLabIdx() << "]";
333         }
334         LogInfo::MapleLogger() << "> idx " << bb->GetId() << " ===\n";
335 
336         if (!bb->GetPreds().empty()) {
337             LogInfo::MapleLogger() << "    pred [ ";
338             for (auto *pred : bb->GetPreds()) {
339                 LogInfo::MapleLogger() << pred->GetId() << " (" << std::hex << pred << ") " << std::dec << " ";
340             }
341             LogInfo::MapleLogger() << "]\n";
342         }
343         if (!bb->GetSuccs().empty()) {
344             LogInfo::MapleLogger() << "    succ [ ";
345             for (auto *succ : bb->GetSuccs()) {
346                 LogInfo::MapleLogger() << succ->GetId() << " (" << std::hex << succ << ") " << std::dec << " ";
347             }
348             LogInfo::MapleLogger() << "]\n";
349         }
350 
351         const SparseDataInfo *infoDef = nullptr;
352         LogInfo::MapleLogger() << "    DEF: ";
353         infoDef = bb->GetDef();
354         DumpInfo(*infoDef);
355 
356         const SparseDataInfo *infoUse = nullptr;
357         LogInfo::MapleLogger() << "\n    USE: ";
358         infoUse = bb->GetUse();
359         DumpInfo(*infoUse);
360 
361         const SparseDataInfo *infoLiveIn = nullptr;
362         LogInfo::MapleLogger() << "\n    Live IN: ";
363         infoLiveIn = bb->GetLiveIn();
364         DumpInfo(*infoLiveIn);
365 
366         const SparseDataInfo *infoLiveOut = nullptr;
367         LogInfo::MapleLogger() << "\n    Live OUT: ";
368         infoLiveOut = bb->GetLiveOut();
369         DumpInfo(*infoLiveOut);
370         LogInfo::MapleLogger() << "\n";
371     }
372     LogInfo::MapleLogger() << "---------------------------\n";
373 }
374 
DumpInfo(const SparseDataInfo &info) const375 void LiveAnalysis::DumpInfo(const SparseDataInfo &info) const
376 {
377     uint32 count = 1;
378     std::set<uint32> res;
379     info.GetInfo().ConvertToSet(res);
380     for (uint32 x : res) {
381         LogInfo::MapleLogger() << x << " ";
382         ++count;
383         /* 20 output one line */
384         if ((count % 20) == 0) {
385             LogInfo::MapleLogger() << "\n";
386         }
387     }
388     LogInfo::MapleLogger() << '\n';
389 }
390 
391 /* initialize dependent info and container of BB. */
InitBB(BB &bb)392 void LiveAnalysis::InitBB(BB &bb)
393 {
394     bb.SetLiveInChange(true);
395     bb.SetInsertUse(false);
396     bb.ClearLiveInRegNO();
397     bb.ClearLiveOutRegNO();
398     const uint32 maxRegCount = cgFunc->GetMaxVReg();
399     bb.SetLiveIn(*NewLiveIn(maxRegCount));
400     bb.SetLiveOut(*NewLiveOut(maxRegCount));
401     bb.SetDef(*NewDef(maxRegCount));
402     bb.SetUse(*NewUse(maxRegCount));
403 }
404 
GetAnalysisDependence(AnalysisDep &aDep) const405 void CgLiveAnalysis::GetAnalysisDependence(AnalysisDep &aDep) const
406 {
407 #if TARGX86_64
408     if (Triple::GetTriple().GetArch() == Triple::ArchType::x64) {
409         aDep.AddRequired<CgHandleCFG>();
410     }
411 #endif
412     aDep.SetPreservedAll();
413 }
414 
PhaseRun(maplebe::CGFunc &f)415 bool CgLiveAnalysis::PhaseRun(maplebe::CGFunc &f)
416 {
417     MemPool *liveMemPool = GetPhaseMemPool();
418     live = f.GetCG()->CreateLiveAnalysis(*liveMemPool, f);
419     CHECK_FATAL(live != nullptr, "NIY");
420     live->AnalysisLive();
421     if (LIVE_ANALYZE_DUMP_NEWPM) {
422         live->Dump();
423     }
424     live->ResetLiveSet();
425     return false;
426 }
427 MAPLE_ANALYSIS_PHASE_REGISTER(CgLiveAnalysis, liveanalysis)
428 } /* namespace maplebe */
429