• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 #if TARGAARCH64
17 #include "aarch64_reaching.h"
18 #include "aarch64_isa.h"
19 #elif TARGRISCV64
20 #include "riscv64_reaching.h"
21 #endif
22 #if TARGARM32
23 #include "arm32_reaching.h"
24 #endif
25 #include "cg_option.h"
26 #include "cgfunc.h"
27 #include "cg.h"
28 
29 /*
30  * This phase build bb->in and bb->out infomation for stack memOperand and RegOperand. each bit in DataInfo
31  * represent whether the register or memory is live or not. to save storage space, the offset of stack is divided
32  * by 4, since the offset is a multiple 4.
33  * this algorithm mainly include 2 parts:
34  *   1. initialize each BB
35  *     (1) insert pseudoInsns for function parameters, ehBB, and return R0/V0
36  *     (2) init bb->gen, bb->use, bb->out
37  *   2. build in and out
38  *     (1) In[BB] = Union all of out[Parents(bb)]
39  *     (2) Out[BB] = gen[BB] union in[BB]
40  * aditionally, this phase provide several commen funcfion about data flow. users can call these functions in
41  * optimization phase conveniently.
42  */
43 namespace maplebe {
ReachingDefinition(CGFunc & func,MemPool & memPool)44 ReachingDefinition::ReachingDefinition(CGFunc &func, MemPool &memPool)
45     : AnalysisResult(&memPool),
46       cgFunc(&func),
47       rdAlloc(&memPool),
48       stackMp(func.GetStackMemPool()),
49       pseudoInsns(rdAlloc.Adapter()),
50       kMaxBBNum(cgFunc->NumBBs() + 1),
51       normalBBSet(rdAlloc.Adapter()),
52       cleanUpBBSet(rdAlloc.Adapter())
53 {
54 }
55 
56 /* check whether the opnd is stack register or not */
IsFrameReg(const Operand & opnd) const57 bool ReachingDefinition::IsFrameReg(const Operand &opnd) const
58 {
59     if (!opnd.IsRegister()) {
60         return false;
61     }
62     auto &reg = static_cast<const RegOperand &>(opnd);
63     return cgFunc->IsFrameReg(reg);
64 }
65 
66 /* intialize bb->out, bb->out only include generated DataInfo */
InitOut(const BB & bb)67 void ReachingDefinition::InitOut(const BB &bb)
68 {
69     if (mode & kRDRegAnalysis) {
70         *regOut[bb.GetId()] = *regGen[bb.GetId()];
71     }
72     if (mode & kRDMemAnalysis) {
73         *memOut[bb.GetId()] = *memGen[bb.GetId()];
74     }
75 }
76 
77 /* when DataInfo will not be used later, they should be cleared. */
ClearDefUseInfo()78 void ReachingDefinition::ClearDefUseInfo()
79 {
80     for (auto insn : pseudoInsns) {
81         /* Keep return pseudo to extend the return register liveness to 'ret'.
82          * Backward propagation can move the return register definition far from the return.
83          */
84 #ifndef TARGX86_64
85         if (insn->GetMachineOpcode() == MOP_pseudo_ret_int || insn->GetMachineOpcode() == MOP_pseudo_ret_float) {
86             continue;
87         }
88 #endif
89         insn->GetBB()->RemoveInsn(*insn);
90     }
91     FOR_ALL_BB(bb, cgFunc) {
92         delete (regGen[bb->GetId()]);
93         regGen[bb->GetId()] = nullptr;
94         delete (regUse[bb->GetId()]);
95         regUse[bb->GetId()] = nullptr;
96         delete (regIn[bb->GetId()]);
97         regIn[bb->GetId()] = nullptr;
98         delete (regOut[bb->GetId()]);
99         regOut[bb->GetId()] = nullptr;
100         delete (memGen[bb->GetId()]);
101         memGen[bb->GetId()] = nullptr;
102         delete (memUse[bb->GetId()]);
103         memUse[bb->GetId()] = nullptr;
104         delete (memIn[bb->GetId()]);
105         memIn[bb->GetId()] = nullptr;
106         delete (memOut[bb->GetId()]);
107         memOut[bb->GetId()] = nullptr;
108     }
109     regGen.clear();
110     regGen.shrink_to_fit();
111     regUse.clear();
112     regUse.shrink_to_fit();
113     regIn.clear();
114     regIn.shrink_to_fit();
115     regOut.clear();
116     regOut.shrink_to_fit();
117     memGen.clear();
118     memGen.shrink_to_fit();
119     memUse.clear();
120     memUse.shrink_to_fit();
121     memIn.clear();
122     memIn.shrink_to_fit();
123     memOut.clear();
124     memOut.shrink_to_fit();
125     cgFunc->SetRD(nullptr);
126 }
127 
128 /*
129  * find used insns for register.
130  *  input:
131  *    insn: the insn in which register is defined
132  *    regNO: the No of register
133  *    isRegNO: this argument is used to form function overloading
134  *  return:
135  *    the set of used insns for register
136  */
FindUseForRegOpnd(Insn & insn,uint32 indexOrRegNO,bool isRegNO) const137 InsnSet ReachingDefinition::FindUseForRegOpnd(Insn &insn, uint32 indexOrRegNO, bool isRegNO) const
138 {
139     InsnSet useInsnSet;
140     uint32 regNO = indexOrRegNO;
141     if (!isRegNO) {
142         Operand &opnd = insn.GetOperand(indexOrRegNO);
143         auto &regOpnd = static_cast<RegOperand &>(opnd);
144         regNO = regOpnd.GetRegisterNumber();
145     }
146     /* register may be redefined in current bb */
147     bool findFinish = FindRegUseBetweenInsn(regNO, insn.GetNext(), insn.GetBB()->GetLastInsn(), useInsnSet);
148     std::vector<bool> visitedBB(kMaxBBNum, false);
149     if (findFinish || !regOut[insn.GetBB()->GetId()]->TestBit(regNO)) {
150         if (!insn.GetBB()->GetEhSuccs().empty()) {
151             DFSFindUseForRegOpnd(*insn.GetBB(), regNO, visitedBB, useInsnSet, true);
152         }
153     } else {
154         DFSFindUseForRegOpnd(*insn.GetBB(), regNO, visitedBB, useInsnSet, false);
155     }
156 
157     if (!insn.GetBB()->IsCleanup() && firstCleanUpBB != nullptr) {
158         if (regUse[firstCleanUpBB->GetId()]->TestBit(regNO)) {
159             findFinish =
160                 FindRegUseBetweenInsn(regNO, firstCleanUpBB->GetFirstInsn(), firstCleanUpBB->GetLastInsn(), useInsnSet);
161             if (findFinish || !regOut[firstCleanUpBB->GetId()]->TestBit(regNO)) {
162                 return useInsnSet;
163             }
164         }
165         DFSFindUseForRegOpnd(*firstCleanUpBB, regNO, visitedBB, useInsnSet, false);
166     }
167 
168     return useInsnSet;
169 }
170 
171 /*
172  * find used insns for register iteratively.
173  *  input:
174  *    startBB: find used insns starting from startBB
175  *    regNO: the No of register to be find
176  *    visitedBB: record these visited BB
177  *    useInsnSet: used insns of register is saved in this set
178  */
DFSFindUseForRegOpnd(const BB & startBB,uint32 regNO,std::vector<bool> & visitedBB,InsnSet & useInsnSet,bool onlyFindForEhSucc=false) const179 void ReachingDefinition::DFSFindUseForRegOpnd(const BB &startBB, uint32 regNO, std::vector<bool> &visitedBB,
180                                               InsnSet &useInsnSet, bool onlyFindForEhSucc = false) const
181 {
182     if (!onlyFindForEhSucc) {
183         for (auto succBB : startBB.GetSuccs()) {
184             if (!regIn[succBB->GetId()]->TestBit(regNO)) {
185                 continue;
186             }
187             if (visitedBB[succBB->GetId()]) {
188                 continue;
189             }
190             visitedBB[succBB->GetId()] = true;
191             bool findFinish = false;
192             if (regUse[succBB->GetId()]->TestBit(regNO)) {
193                 findFinish = FindRegUseBetweenInsn(regNO, succBB->GetFirstInsn(), succBB->GetLastInsn(), useInsnSet);
194             } else if (regGen[succBB->GetId()]->TestBit(regNO)) {
195                 findFinish = true;
196             }
197             if (!findFinish && regOut[succBB->GetId()]->TestBit(regNO)) {
198                 DFSFindUseForRegOpnd(*succBB, regNO, visitedBB, useInsnSet, false);
199             }
200         }
201     }
202 
203     for (auto ehSuccBB : startBB.GetEhSuccs()) {
204         if (!regIn[ehSuccBB->GetId()]->TestBit(regNO)) {
205             continue;
206         }
207         if (visitedBB[ehSuccBB->GetId()]) {
208             continue;
209         }
210         visitedBB[ehSuccBB->GetId()] = true;
211 
212         bool findFinish = false;
213         if (regUse[ehSuccBB->GetId()]->TestBit(regNO)) {
214             findFinish = FindRegUseBetweenInsn(regNO, ehSuccBB->GetFirstInsn(), ehSuccBB->GetLastInsn(), useInsnSet);
215         } else if (regGen[ehSuccBB->GetId()]->TestBit(regNO)) {
216             findFinish = true;
217         }
218         if (!findFinish && regOut[ehSuccBB->GetId()]->TestBit(regNO)) {
219             DFSFindUseForRegOpnd(*ehSuccBB, regNO, visitedBB, useInsnSet, false);
220         }
221     }
222 }
223 
224 /* check whether register defined in regDefInsn has used insns */
RegHasUsePoint(uint32 regNO,Insn & regDefInsn) const225 bool ReachingDefinition::RegHasUsePoint(uint32 regNO, Insn &regDefInsn) const
226 {
227     InsnSet useInsnSet;
228     bool findFinish = FindRegUseBetweenInsn(regNO, regDefInsn.GetNext(), regDefInsn.GetBB()->GetLastInsn(), useInsnSet);
229     if (!useInsnSet.empty()) {
230         return true;
231     }
232     if (!findFinish) {
233         std::vector<bool> visitedBB(kMaxBBNum, false);
234         return RegIsUsedInOtherBB(*regDefInsn.GetBB(), regNO, visitedBB);
235     }
236     return false;
237 }
238 
239 /* check whether register is used in other BB except startBB */
RegIsUsedInOtherBB(const BB & startBB,uint32 regNO,std::vector<bool> & visitedBB) const240 bool ReachingDefinition::RegIsUsedInOtherBB(const BB &startBB, uint32 regNO, std::vector<bool> &visitedBB) const
241 {
242     InsnSet useInsnSet;
243     for (auto succBB : startBB.GetSuccs()) {
244         if (!regIn[succBB->GetId()]->TestBit(regNO)) {
245             continue;
246         }
247         if (visitedBB[succBB->GetId()]) {
248             continue;
249         }
250         visitedBB[succBB->GetId()] = true;
251         bool findFinish = false;
252         if (regUse[succBB->GetId()]->TestBit(regNO)) {
253             if (!regGen[succBB->GetId()]->TestBit(regNO)) {
254                 return true;
255             }
256             useInsnSet.clear();
257             findFinish = FindRegUseBetweenInsn(regNO, succBB->GetFirstInsn(), succBB->GetLastInsn(), useInsnSet);
258             if (!useInsnSet.empty()) {
259                 return true;
260             }
261         } else if (regGen[succBB->GetId()]->TestBit(regNO)) {
262             findFinish = true;
263         }
264         if (!findFinish && regOut[succBB->GetId()]->TestBit(regNO)) {
265             if (RegIsUsedInOtherBB(*succBB, regNO, visitedBB)) {
266                 return true;
267             }
268         }
269     }
270 
271     for (auto ehSuccBB : startBB.GetEhSuccs()) {
272         if (!regIn[ehSuccBB->GetId()]->TestBit(regNO)) {
273             continue;
274         }
275         if (visitedBB[ehSuccBB->GetId()]) {
276             continue;
277         }
278         visitedBB[ehSuccBB->GetId()] = true;
279 
280         bool findFinish = false;
281         if (regUse[ehSuccBB->GetId()]->TestBit(regNO)) {
282             if (!regGen[ehSuccBB->GetId()]->TestBit(regNO)) {
283                 return true;
284             }
285             useInsnSet.clear();
286             findFinish = FindRegUseBetweenInsn(regNO, ehSuccBB->GetFirstInsn(), ehSuccBB->GetLastInsn(), useInsnSet);
287             if (!useInsnSet.empty()) {
288                 return true;
289             }
290         } else if (regGen[ehSuccBB->GetId()]->TestBit(regNO)) {
291             findFinish = true;
292         }
293         if (!findFinish && regOut[ehSuccBB->GetId()]->TestBit(regNO)) {
294             if (RegIsUsedInOtherBB(*ehSuccBB, regNO, visitedBB)) {
295                 return true;
296             }
297         }
298     }
299 
300     return false;
301 }
302 
RegIsUsedInCleanUpBB(uint32 regNO) const303 bool ReachingDefinition::RegIsUsedInCleanUpBB(uint32 regNO) const
304 {
305     if (firstCleanUpBB == nullptr) {
306         return false;
307     }
308     InsnSet useInsnSet;
309     if (regUse[firstCleanUpBB->GetId()]->TestBit(regNO)) {
310         bool findFinish =
311             FindRegUseBetweenInsn(regNO, firstCleanUpBB->GetFirstInsn(), firstCleanUpBB->GetLastInsn(), useInsnSet);
312         if (!useInsnSet.empty()) {
313             return true;
314         }
315         if (findFinish) {
316             return false;
317         }
318     }
319 
320     std::vector<bool> visitedBB(kMaxBBNum, false);
321     DFSFindUseForRegOpnd(*firstCleanUpBB, regNO, visitedBB, useInsnSet, false);
322     if (useInsnSet.empty()) {
323         return true;
324     }
325 
326     return false;
327 }
328 
329 /*
330  * find used insns for stack memory operand iteratively.
331  *  input:
332  *    startBB: find used insns starting from startBB
333  *    offset: the offset of memory to be find
334  *    visitedBB: record these visited BB
335  *    useInsnSet: used insns of stack memory operand is saved in this set
336  */
DFSFindUseForMemOpnd(const BB & startBB,uint32 offset,std::vector<bool> & visitedBB,InsnSet & useInsnSet,bool onlyFindForEhSucc=false) const337 void ReachingDefinition::DFSFindUseForMemOpnd(const BB &startBB, uint32 offset, std::vector<bool> &visitedBB,
338                                               InsnSet &useInsnSet, bool onlyFindForEhSucc = false) const
339 {
340     if (!onlyFindForEhSucc) {
341         for (auto succBB : startBB.GetSuccs()) {
342             if (!memIn[succBB->GetId()]->TestBit(offset / kMemZoomSize)) {
343                 continue;
344             }
345             if (visitedBB[succBB->GetId()]) {
346                 continue;
347             }
348             visitedBB[succBB->GetId()] = true;
349             bool findFinish = false;
350             if (memUse[succBB->GetId()]->TestBit(offset / kMemZoomSize)) {
351                 findFinish = FindMemUseBetweenInsn(offset, succBB->GetFirstInsn(), succBB->GetLastInsn(), useInsnSet);
352             } else if (memGen[succBB->GetId()]->TestBit(offset / kMemZoomSize)) {
353                 findFinish = true;
354             }
355             if (!findFinish && memOut[succBB->GetId()]->TestBit(offset / kMemZoomSize)) {
356                 DFSFindUseForMemOpnd(*succBB, offset, visitedBB, useInsnSet);
357             }
358         }
359     }
360 
361     for (auto ehSuccBB : startBB.GetEhSuccs()) {
362         if (!memIn[ehSuccBB->GetId()]->TestBit(offset / kMemZoomSize)) {
363             continue;
364         }
365         if (visitedBB[ehSuccBB->GetId()]) {
366             continue;
367         }
368         visitedBB[ehSuccBB->GetId()] = true;
369         bool findFinish = false;
370         if (memUse[ehSuccBB->GetId()]->TestBit(offset / kMemZoomSize)) {
371             findFinish = FindMemUseBetweenInsn(offset, ehSuccBB->GetFirstInsn(), ehSuccBB->GetLastInsn(), useInsnSet);
372         } else if (memGen[ehSuccBB->GetId()]->TestBit(offset / kMemZoomSize)) {
373             findFinish = true;
374         }
375         if (!findFinish && memOut[ehSuccBB->GetId()]->TestBit(offset / kMemZoomSize)) {
376             DFSFindUseForMemOpnd(*ehSuccBB, offset, visitedBB, useInsnSet);
377         }
378     }
379 }
380 
381 /* Out[BB] = gen[BB] union in[BB]. if bb->out changed, return true. */
GenerateOut(const BB & bb)382 bool ReachingDefinition::GenerateOut(const BB &bb)
383 {
384     bool outInfoChanged = false;
385     if (mode & kRDRegAnalysis) {
386         LocalMapleAllocator alloc(stackMp);
387         DataInfo &bbRegOutBak = regOut[bb.GetId()]->Clone(alloc);
388         *regOut[bb.GetId()] = *(regIn[bb.GetId()]);
389         regOut[bb.GetId()]->OrBits(*regGen[bb.GetId()]);
390         if (!regOut[bb.GetId()]->IsEqual(bbRegOutBak)) {
391             outInfoChanged = true;
392         }
393     }
394 
395     if (mode & kRDMemAnalysis) {
396         LocalMapleAllocator alloc(stackMp);
397         DataInfo &bbMemOutBak = memOut[bb.GetId()]->Clone(alloc);
398         *memOut[bb.GetId()] = *memIn[bb.GetId()];
399         memOut[bb.GetId()]->OrBits(*memGen[bb.GetId()]);
400         if (!memOut[bb.GetId()]->IsEqual(bbMemOutBak)) {
401             outInfoChanged = true;
402         }
403     }
404     return outInfoChanged;
405 }
406 
GenerateOut(const BB & bb,const std::set<uint32> & infoIndex,const bool isReg)407 bool ReachingDefinition::GenerateOut(const BB &bb, const std::set<uint32> &infoIndex, const bool isReg)
408 {
409     bool outInfoChanged = false;
410     if (isReg) {
411         for (auto index : infoIndex) {
412             uint64 bbRegOutBak = regOut[bb.GetId()]->GetElem(index);
413             regOut[bb.GetId()]->SetElem(index, regIn[bb.GetId()]->GetElem(index));
414             regOut[bb.GetId()]->OrDesignateBits(*regGen[bb.GetId()], index);
415             if (!outInfoChanged && (bbRegOutBak != regOut[bb.GetId()]->GetElem(index))) {
416                 outInfoChanged = true;
417             }
418         }
419     } else {
420         for (auto index : infoIndex) {
421             uint64 bbMemOutBak = memOut[bb.GetId()]->GetElem(index);
422             memOut[bb.GetId()]->SetElem(index, memIn[bb.GetId()]->GetElem(index));
423             memOut[bb.GetId()]->OrDesignateBits(*memGen[bb.GetId()], index);
424             if (bbMemOutBak != memOut[bb.GetId()]->GetElem(index)) {
425                 outInfoChanged = true;
426             }
427         }
428     }
429     return outInfoChanged;
430 }
431 
432 /* In[BB] = Union all of out[Parents(bb)]. return true if bb->in changed. */
GenerateIn(const BB & bb)433 bool ReachingDefinition::GenerateIn(const BB &bb)
434 {
435     bool inInfoChanged = false;
436     if (mode & kRDRegAnalysis) {
437         LocalMapleAllocator alloc(stackMp);
438         DataInfo &bbRegInBak = regIn[bb.GetId()]->Clone(alloc);
439         for (auto predBB : bb.GetPreds()) {
440             regIn[bb.GetId()]->OrBits(*regOut[predBB->GetId()]);
441         }
442         for (auto predEhBB : bb.GetEhPreds()) {
443             regIn[bb.GetId()]->OrBits(*regOut[predEhBB->GetId()]);
444         }
445 
446         if (!regIn[bb.GetId()]->IsEqual(bbRegInBak)) {
447             inInfoChanged = true;
448         }
449     }
450     if (mode & kRDMemAnalysis) {
451         LocalMapleAllocator alloc(stackMp);
452         DataInfo &memInBak = memIn[bb.GetId()]->Clone(alloc);
453         for (auto predBB : bb.GetPreds()) {
454             memIn[bb.GetId()]->OrBits(*memOut[predBB->GetId()]);
455         }
456         for (auto predEhBB : bb.GetEhPreds()) {
457             memIn[bb.GetId()]->OrBits(*memOut[predEhBB->GetId()]);
458         }
459 
460         if (!memIn[bb.GetId()]->IsEqual(memInBak)) {
461             inInfoChanged = true;
462         }
463     }
464     return inInfoChanged;
465 }
466 
467 /* In[BB] = Union all of out[Parents(bb)]. return true if bb->in changed. */
GenerateIn(const BB & bb,const std::set<uint32> & infoIndex,const bool isReg)468 bool ReachingDefinition::GenerateIn(const BB &bb, const std::set<uint32> &infoIndex, const bool isReg)
469 {
470     bool inInfoChanged = false;
471 
472     if (isReg) {
473         for (auto index : infoIndex) {
474             uint64 bbRegInBak = regIn[bb.GetId()]->GetElem(index);
475             regIn[bb.GetId()]->SetElem(index, 0ULL);
476             for (auto predBB : bb.GetPreds()) {
477                 regIn[bb.GetId()]->OrDesignateBits(*regOut[predBB->GetId()], index);
478             }
479             for (auto predEhBB : bb.GetEhPreds()) {
480                 regIn[bb.GetId()]->OrDesignateBits(*regOut[predEhBB->GetId()], index);
481             }
482 
483             if (bbRegInBak != regIn[bb.GetId()]->GetElem(index)) {
484                 inInfoChanged = true;
485             }
486         }
487     } else {
488         for (auto index : infoIndex) {
489             uint64 bbMemInBak = memIn[bb.GetId()]->GetElem(index);
490             memIn[bb.GetId()]->SetElem(index, 0ULL);
491             for (auto predBB : bb.GetPreds()) {
492                 memIn[bb.GetId()]->OrDesignateBits(*memOut[predBB->GetId()], index);
493             }
494             for (auto predEhBB : bb.GetEhPreds()) {
495                 memIn[bb.GetId()]->OrDesignateBits(*memOut[predEhBB->GetId()], index);
496             }
497 
498             if (bbMemInBak != memIn[bb.GetId()]->GetElem(index)) {
499                 inInfoChanged = true;
500             }
501         }
502     }
503     return inInfoChanged;
504 }
505 
506 /* In[firstCleanUpBB] = Union all of out[bbNormalSet] */
GenerateInForFirstCleanUpBB()507 bool ReachingDefinition::GenerateInForFirstCleanUpBB()
508 {
509     CHECK_NULL_FATAL(firstCleanUpBB);
510     if (mode & kRDRegAnalysis) {
511         regIn[firstCleanUpBB->GetId()]->ResetAllBit();
512     }
513     if (mode & kRDMemAnalysis) {
514         memIn[firstCleanUpBB->GetId()]->ResetAllBit();
515     }
516 
517     for (auto normalBB : normalBBSet) {
518         if (mode & kRDRegAnalysis) {
519             regIn[firstCleanUpBB->GetId()]->OrBits(*regOut[normalBB->GetId()]);
520         }
521 
522         if (mode & kRDMemAnalysis) {
523             memIn[firstCleanUpBB->GetId()]->OrBits(*memOut[normalBB->GetId()]);
524         }
525     }
526 
527     return ((regIn[firstCleanUpBB->GetId()] != nullptr && regIn[firstCleanUpBB->GetId()]->Size() > 0) ||
528             (memIn[firstCleanUpBB->GetId()] != nullptr && memIn[firstCleanUpBB->GetId()]->Size() > 0));
529 }
530 
GenerateInForFirstCleanUpBB(bool isReg,const std::set<uint32> & infoIndex)531 bool ReachingDefinition::GenerateInForFirstCleanUpBB(bool isReg, const std::set<uint32> &infoIndex)
532 {
533     CHECK_NULL_FATAL(firstCleanUpBB);
534     bool inInfoChanged = false;
535     if (isReg) {
536         for (auto index : infoIndex) {
537             uint64 regInElemBak = regIn[firstCleanUpBB->GetId()]->GetElem(index);
538             regIn[firstCleanUpBB->GetId()]->SetElem(index, 0ULL);
539             for (auto &normalBB : normalBBSet) {
540                 regIn[firstCleanUpBB->GetId()]->OrDesignateBits(*regOut[normalBB->GetId()], index);
541             }
542             if (!inInfoChanged && (regIn[firstCleanUpBB->GetId()]->GetElem(index) != regInElemBak)) {
543                 inInfoChanged = true;
544             }
545         }
546     } else {
547         for (auto index : infoIndex) {
548             uint64 memInElemBak = memIn[firstCleanUpBB->GetId()]->GetElem(index);
549             memIn[firstCleanUpBB->GetId()]->SetElem(index, 0ULL);
550             for (auto &normalBB : normalBBSet) {
551                 memIn[firstCleanUpBB->GetId()]->OrDesignateBits(*memOut[normalBB->GetId()], index);
552             }
553             if (!inInfoChanged && (memIn[firstCleanUpBB->GetId()]->GetElem(index) != memInElemBak)) {
554                 inInfoChanged = true;
555             }
556         }
557     }
558     return inInfoChanged;
559 }
560 
561 /* allocate memory for DataInfo of bb */
InitRegAndMemInfo(const BB & bb)562 void ReachingDefinition::InitRegAndMemInfo(const BB &bb)
563 {
564     if (mode & kRDRegAnalysis) {
565         const uint32 kMaxRegCount = cgFunc->GetMaxVReg();
566         regGen[bb.GetId()] = new DataInfo(kMaxRegCount, rdAlloc);
567         regUse[bb.GetId()] = new DataInfo(kMaxRegCount, rdAlloc);
568         regIn[bb.GetId()] = new DataInfo(kMaxRegCount, rdAlloc);
569         regOut[bb.GetId()] = new DataInfo(kMaxRegCount, rdAlloc);
570     }
571 
572     if (mode & kRDMemAnalysis) {
573         const int32 kStackSize = GetStackSize();
574         memGen[bb.GetId()] = new DataInfo((kStackSize / kMemZoomSize), rdAlloc);
575         memUse[bb.GetId()] = new DataInfo((kStackSize / kMemZoomSize), rdAlloc);
576         memIn[bb.GetId()] = new DataInfo((kStackSize / kMemZoomSize), rdAlloc);
577         memOut[bb.GetId()] = new DataInfo((kStackSize / kMemZoomSize), rdAlloc);
578     }
579 }
580 
581 /* insert pseudoInsns for function parameters, ehBB, and return R0/V0. init bb->gen, bb->use, bb->out */
Initialize()582 void ReachingDefinition::Initialize()
583 {
584     InitDataSize();
585     AddRetPseudoInsns();
586     FOR_ALL_BB(bb, cgFunc) {
587         InitRegAndMemInfo(*bb);
588     }
589     FOR_ALL_BB(bb, cgFunc) {
590         if (bb == cgFunc->GetFirstBB()) {
591             InitStartGen();
592         }
593         if (!bb->GetEhPreds().empty()) {
594             InitEhDefine(*bb);
595         }
596         InitGenUse(*bb);
597         InitOut(*bb);
598 
599         if (bb->IsCleanup()) {
600             if (bb->GetFirstStmt() == cgFunc->GetCleanupLabel()) {
601                 firstCleanUpBB = bb;
602             }
603             (void)cleanUpBBSet.insert(bb);
604         } else {
605             (void)normalBBSet.insert(bb);
606         }
607     }
608     maxInsnNO = 0;
609     FOR_ALL_BB(bb, cgFunc) {
610         FOR_BB_INSNS(insn, bb) {
611             insn->SetId(maxInsnNO);
612             maxInsnNO += kInsnNoInterval;
613         }
614     }
615 }
616 
InitDataSize()617 void ReachingDefinition::InitDataSize()
618 {
619     /* to visit vec[cgFunc->NumBBs()], size should be cgFunc->NumBBs() + 1 */
620     const uint32 dataSize = cgFunc->NumBBs() + 1;
621     regIn.resize(dataSize);
622     regOut.resize(dataSize);
623     regGen.resize(dataSize);
624     regUse.resize(dataSize);
625     memIn.resize(dataSize);
626     memOut.resize(dataSize);
627     memGen.resize(dataSize);
628     memUse.resize(dataSize);
629 }
630 
631 /* compute bb->in, bb->out for each BB execpt cleanup BB */
BuildInOutForFuncBody()632 void ReachingDefinition::BuildInOutForFuncBody()
633 {
634     std::unordered_set<BB *> normalBBSetBak(normalBBSet.begin(), normalBBSet.end());
635     std::unordered_set<BB *>::iterator setItr;
636     while (!normalBBSetBak.empty()) {
637         setItr = normalBBSetBak.begin();
638         BB *bb = *setItr;
639         DEBUG_ASSERT(bb != nullptr, "null ptr check");
640         (void)normalBBSetBak.erase(setItr);
641 
642         if (GenerateIn(*bb)) {
643             if (GenerateOut(*bb)) {
644                 for (auto succ : bb->GetSuccs()) {
645                     (void)normalBBSetBak.insert(succ);
646                 }
647 
648                 for (auto ehSucc : bb->GetEhSuccs()) {
649                     (void)normalBBSetBak.insert(ehSucc);
650                 }
651             }
652         }
653     }
654     DEBUG_ASSERT(normalBBSetBak.empty(), "CG internal error.");
655 }
656 
657 /* if bb->out changed, update in and out */
UpdateInOut(BB & changedBB)658 void ReachingDefinition::UpdateInOut(BB &changedBB)
659 {
660     InitGenUse(changedBB, false);
661     if (!GenerateOut(changedBB)) {
662         return;
663     }
664 
665     std::unordered_set<BB *> bbSet;
666     std::unordered_set<BB *>::iterator setItr;
667 
668     for (auto succ : changedBB.GetSuccs()) {
669         (void)bbSet.insert(succ);
670     }
671 
672     for (auto ehSucc : changedBB.GetEhSuccs()) {
673         (void)bbSet.insert(ehSucc);
674     }
675 
676     while (!bbSet.empty()) {
677         setItr = bbSet.begin();
678         BB *bb = *setItr;
679         DEBUG_ASSERT(bb != nullptr, "null ptr check");
680         bbSet.erase(setItr);
681 
682         if (GenerateIn(*bb)) {
683             if (GenerateOut(*bb)) {
684                 for (auto succ : bb->GetSuccs()) {
685                     (void)bbSet.insert(succ);
686                 }
687 
688                 for (auto ehSucc : bb->GetEhSuccs()) {
689                     (void)bbSet.insert(ehSucc);
690                 }
691             }
692         }
693     }
694 
695     if (!changedBB.IsCleanup() && firstCleanUpBB != nullptr) {
696         BuildInOutForCleanUpBB();
697     }
698 }
699 
UpdateInOut(BB & changedBB,bool isReg)700 void ReachingDefinition::UpdateInOut(BB &changedBB, bool isReg)
701 {
702     std::set<uint32> changedInfoIndex;
703     if (isReg) {
704         LocalMapleAllocator alloc(stackMp);
705         DataInfo &genInfoBak = regGen[changedBB.GetId()]->Clone(alloc);
706         InitGenUse(changedBB, false);
707         genInfoBak.EorBits(*regGen[changedBB.GetId()]);
708         genInfoBak.GetNonZeroElemsIndex(changedInfoIndex);
709     } else {
710         LocalMapleAllocator alloc(stackMp);
711         DataInfo &genInfoBak = memGen[changedBB.GetId()]->Clone(alloc);
712         InitGenUse(changedBB, false);
713         genInfoBak.EorBits(*memGen[changedBB.GetId()]);
714         genInfoBak.GetNonZeroElemsIndex(changedInfoIndex);
715     }
716     if (changedInfoIndex.empty()) {
717         return;
718     }
719     if (!GenerateOut(changedBB, changedInfoIndex, isReg)) {
720         return;
721     }
722     std::set<BB *, BBIdCmp> bbSet;
723     std::set<BB *, BBIdCmp>::iterator setItr;
724     for (auto &succ : changedBB.GetSuccs()) {
725         (void)bbSet.insert(succ);
726     }
727 
728     for (auto &ehSucc : changedBB.GetEhSuccs()) {
729         (void)bbSet.insert(ehSucc);
730     }
731     while (!bbSet.empty()) {
732         setItr = bbSet.begin();
733         BB *bb = *setItr;
734         bbSet.erase(setItr);
735         if (GenerateIn(*bb, changedInfoIndex, isReg)) {
736             if (GenerateOut(*bb, changedInfoIndex, isReg)) {
737                 for (auto &succ : bb->GetSuccs()) {
738                     (void)bbSet.insert(succ);
739                 }
740                 for (auto &ehSucc : bb->GetEhSuccs()) {
741                     (void)bbSet.insert(ehSucc);
742                 }
743             }
744         }
745     }
746 
747     if (!changedBB.IsCleanup() && firstCleanUpBB != nullptr) {
748         BuildInOutForCleanUpBB(isReg, changedInfoIndex);
749     }
750 }
751 
752 /* compute bb->in, bb->out for cleanup BBs */
BuildInOutForCleanUpBB()753 void ReachingDefinition::BuildInOutForCleanUpBB()
754 {
755     DEBUG_ASSERT(firstCleanUpBB != nullptr, "firstCleanUpBB must not be nullptr");
756     if (GenerateInForFirstCleanUpBB()) {
757         GenerateOut(*firstCleanUpBB);
758     }
759     std::unordered_set<BB *> cleanupBBSetBak(cleanUpBBSet.begin(), cleanUpBBSet.end());
760     std::unordered_set<BB *>::iterator setItr;
761 
762     while (!cleanupBBSetBak.empty()) {
763         setItr = cleanupBBSetBak.begin();
764         BB *bb = *setItr;
765         cleanupBBSetBak.erase(setItr);
766         if (GenerateIn(*bb)) {
767             if (GenerateOut(*bb)) {
768                 for (auto succ : bb->GetSuccs()) {
769                     (void)cleanupBBSetBak.insert(succ);
770                 }
771                 for (auto ehSucc : bb->GetEhSuccs()) {
772                     (void)cleanupBBSetBak.insert(ehSucc);
773                 }
774             }
775         }
776     }
777     DEBUG_ASSERT(cleanupBBSetBak.empty(), "CG internal error.");
778 }
779 
BuildInOutForCleanUpBB(bool isReg,const std::set<uint32> & index)780 void ReachingDefinition::BuildInOutForCleanUpBB(bool isReg, const std::set<uint32> &index)
781 {
782     DEBUG_ASSERT(firstCleanUpBB != nullptr, "firstCleanUpBB must not be nullptr");
783     if (GenerateInForFirstCleanUpBB(isReg, index)) {
784         GenerateOut(*firstCleanUpBB, index, isReg);
785     }
786     std::unordered_set<BB *> cleanupBBSetBak(cleanUpBBSet.begin(), cleanUpBBSet.end());
787     std::unordered_set<BB *>::iterator setItr;
788     while (!cleanupBBSetBak.empty()) {
789         setItr = cleanupBBSetBak.begin();
790         BB *bb = *setItr;
791         cleanupBBSetBak.erase(setItr);
792         if (GenerateIn(*bb, index, isReg)) {
793             if (GenerateOut(*bb, index, isReg)) {
794                 for (auto &succ : bb->GetSuccs()) {
795                     (void)cleanupBBSetBak.insert(succ);
796                 }
797                 for (auto &ehSucc : bb->GetEhSuccs()) {
798                     (void)cleanupBBSetBak.insert(ehSucc);
799                 }
800             }
801         }
802     }
803     DEBUG_ASSERT(cleanupBBSetBak.empty(), "CG internal error.");
804 }
805 
806 /* entry for ReachingDefinition Analysis, mode represent to analyze RegOperand, MemOperand or both of them */
AnalysisStart()807 void ReachingDefinition::AnalysisStart()
808 {
809     if (!cgFunc->GetFirstBB()) {
810         return;
811     }
812     Initialize();
813     /* Build in/out for function body first. (Except cleanup bb) */
814     BuildInOutForFuncBody();
815     /* If cleanup bb exists, build in/out for cleanup bbs. firstCleanUpBB->in = Union all non-cleanup bb's out. */
816     if (firstCleanUpBB != nullptr) {
817         BuildInOutForCleanUpBB();
818     }
819     cgFunc->SetRD(this);
820 }
821 
822 /* check whether currentBB can reach endBB according to control flow */
CanReachEndBBFromCurrentBB(const BB & currentBB,const BB & endBB,std::vector<bool> & traversedBBSet) const823 bool ReachingDefinition::CanReachEndBBFromCurrentBB(const BB &currentBB, const BB &endBB,
824                                                     std::vector<bool> &traversedBBSet) const
825 {
826     if (&currentBB == &endBB) {
827         return true;
828     }
829     for (auto predBB : endBB.GetPreds()) {
830         if (traversedBBSet[predBB->GetId()]) {
831             continue;
832         }
833         traversedBBSet[predBB->GetId()] = true;
834         if (predBB == &currentBB) {
835             return true;
836         }
837         if (CanReachEndBBFromCurrentBB(currentBB, *predBB, traversedBBSet)) {
838             return true;
839         }
840     }
841     for (auto ehPredBB : endBB.GetEhPreds()) {
842         if (traversedBBSet[ehPredBB->GetId()]) {
843             continue;
844         }
845         traversedBBSet[ehPredBB->GetId()] = true;
846         if (ehPredBB == &currentBB) {
847             return true;
848         }
849         if (CanReachEndBBFromCurrentBB(currentBB, *ehPredBB, traversedBBSet)) {
850             return true;
851         }
852     }
853     return false;
854 }
855 
856 /* check whether register may be redefined form startBB to endBB */
IsLiveInAllPathBB(uint32 regNO,const BB & startBB,const BB & endBB,std::vector<bool> & visitedBB,bool isFirstNo) const857 bool ReachingDefinition::IsLiveInAllPathBB(uint32 regNO, const BB &startBB, const BB &endBB,
858                                            std::vector<bool> &visitedBB, bool isFirstNo) const
859 {
860     for (auto succ : startBB.GetSuccs()) {
861         if (visitedBB[succ->GetId()]) {
862             continue;
863         }
864         visitedBB[succ->GetId()] = true;
865         if (isFirstNo && CheckRegLiveinReturnBB(regNO, *succ)) {
866             return false;
867         }
868         std::vector<bool> traversedPathSet(kMaxBBNum, false);
869         bool canReachEndBB = true;
870         if (regGen[succ->GetId()]->TestBit(regNO)) {
871             canReachEndBB = CanReachEndBBFromCurrentBB(*succ, endBB, traversedPathSet);
872             if (canReachEndBB) {
873                 return false;
874             }
875         }
876         if (!canReachEndBB) {
877             continue;
878         }
879         bool isLive = IsLiveInAllPathBB(regNO, *succ, endBB, visitedBB, isFirstNo);
880         if (!isLive) {
881             return false;
882         }
883     }
884 
885     for (auto ehSucc : startBB.GetEhSuccs()) {
886         if (visitedBB[ehSucc->GetId()]) {
887             continue;
888         }
889         visitedBB[ehSucc->GetId()] = true;
890         if (isFirstNo && CheckRegLiveinReturnBB(regNO, *ehSucc)) {
891             return false;
892         }
893         std::vector<bool> traversedPathSet(kMaxBBNum, false);
894         bool canReachEndBB = true;
895         if (regGen[ehSucc->GetId()]->TestBit(regNO)) {
896             canReachEndBB = CanReachEndBBFromCurrentBB(*ehSucc, endBB, traversedPathSet);
897             if (canReachEndBB) {
898                 return false;
899             }
900         }
901         if (!canReachEndBB) {
902             continue;
903         }
904         bool isLive = IsLiveInAllPathBB(regNO, *ehSucc, endBB, visitedBB, isFirstNo);
905         if (!isLive) {
906             return false;
907         }
908     }
909     return true;
910 }
911 
912 /* Check if the reg is used in return BB */
CheckRegLiveinReturnBB(uint32 regNO,const BB & bb) const913 bool ReachingDefinition::CheckRegLiveinReturnBB(uint32 regNO, const BB &bb) const
914 {
915 #if TARGAARCH64 || TARGRISCV64
916     if (bb.GetKind() == BB::kBBReturn) {
917         PrimType returnType = cgFunc->GetFunction().GetReturnType()->GetPrimType();
918         regno_t returnReg = R0;
919         if (IsPrimitiveFloat(returnType)) {
920             returnReg = V0;
921         } else if (IsPrimitiveInteger(returnType)) {
922             returnReg = R0;
923         }
924         if (regNO == returnReg) {
925             return true;
926         }
927     }
928 #endif
929     return false;
930 }
931 
RegIsUsedIncaller(uint32 regNO,Insn & startInsn,Insn & endInsn) const932 bool ReachingDefinition::RegIsUsedIncaller(uint32 regNO, Insn &startInsn, Insn &endInsn) const
933 {
934     if (startInsn.GetBB() != endInsn.GetBB()) {
935         return false;
936     }
937     if (startInsn.GetNext() == &endInsn || &startInsn == &endInsn) {
938         return false;
939     }
940     auto RegDefVec = FindRegDefBetweenInsn(regNO, startInsn.GetNext(), endInsn.GetPrev());
941     if (!RegDefVec.empty()) {
942         return false;
943     }
944     if (IsCallerSavedReg(regNO) && startInsn.GetNext() != nullptr &&
945         KilledByCallBetweenInsnInSameBB(*startInsn.GetNext(), *(startInsn.GetBB()->GetLastInsn()), regNO)) {
946         return true;
947     }
948     if (CheckRegLiveinReturnBB(regNO, *startInsn.GetBB())) {
949         return true;
950     }
951     return false;
952 }
953 
954 /* check whether control flow can reach endInsn from startInsn */
RegIsLiveBetweenInsn(uint32 regNO,Insn & startInsn,Insn & endInsn,bool isBack,bool isFirstNo) const955 bool ReachingDefinition::RegIsLiveBetweenInsn(uint32 regNO, Insn &startInsn, Insn &endInsn, bool isBack,
956                                               bool isFirstNo) const
957 {
958     DEBUG_ASSERT(&startInsn != &endInsn, "startInsn is not equal to endInsn");
959     if (startInsn.GetBB() == endInsn.GetBB()) {
960         /* register is difined more than once */
961         if (startInsn.GetId() > endInsn.GetId()) {
962             if (!isBack) {
963                 return false;
964             } else {
965                 return true;
966             }
967         }
968         if (startInsn.GetNext() == &endInsn) {
969             return true;
970         }
971         if (regGen[startInsn.GetBB()->GetId()]->TestBit(regNO)) {
972             std::vector<Insn *> RegDefVec;
973             if (isBack) {
974                 RegDefVec = FindRegDefBetweenInsn(regNO, startInsn.GetNext(), endInsn.GetPrev());
975             } else {
976                 RegDefVec = FindRegDefBetweenInsn(regNO, &startInsn, endInsn.GetPrev());
977             }
978             if (!RegDefVec.empty()) {
979                 return false;
980             }
981         }
982         if (IsCallerSavedReg(regNO) &&
983             KilledByCallBetweenInsnInSameBB(*startInsn.GetNext(), *endInsn.GetPrev(), regNO)) {
984             return false;
985         }
986         return true;
987     }
988 
989     if (&startInsn != startInsn.GetBB()->GetLastInsn() && regGen[startInsn.GetBB()->GetId()]->TestBit(regNO) &&
990         !FindRegDefBetweenInsn(regNO, startInsn.GetNext(), startInsn.GetBB()->GetLastInsn()).empty()) {
991         return false;
992     }
993 
994     if (&startInsn != startInsn.GetBB()->GetLastInsn() && IsCallerSavedReg(regNO) &&
995         KilledByCallBetweenInsnInSameBB(*startInsn.GetNext(), *startInsn.GetBB()->GetLastInsn(), regNO)) {
996         return false;
997     }
998 
999     if (&endInsn != endInsn.GetBB()->GetFirstInsn() && regGen[endInsn.GetBB()->GetId()]->TestBit(regNO) &&
1000         !FindRegDefBetweenInsn(regNO, endInsn.GetBB()->GetFirstInsn(), endInsn.GetPrev()).empty()) {
1001         return false;
1002     }
1003 
1004     if (&endInsn != endInsn.GetBB()->GetFirstInsn() && IsCallerSavedReg(regNO) &&
1005         KilledByCallBetweenInsnInSameBB(*endInsn.GetBB()->GetFirstInsn(), *endInsn.GetPrev(), regNO)) {
1006         return false;
1007     }
1008 
1009     std::vector<bool> visitedBB(kMaxBBNum, false);
1010     return IsLiveInAllPathBB(regNO, *startInsn.GetBB(), *endInsn.GetBB(), visitedBB, isFirstNo);
1011 }
1012 
SetDefInsnVecForAsm(Insn * insn,uint32 index,uint32 regNO,std::vector<Insn * > & defInsnVec)1013 static bool SetDefInsnVecForAsm(Insn *insn, uint32 index, uint32 regNO, std::vector<Insn *> &defInsnVec)
1014 {
1015     for (auto reg : static_cast<ListOperand &>(insn->GetOperand(index)).GetOperands()) {
1016         if (static_cast<RegOperand *>(reg)->GetRegisterNumber() == regNO) {
1017             defInsnVec.emplace_back(insn);
1018             return true;
1019         }
1020     }
1021     return false;
1022 }
1023 
FindRegDefBetweenInsn(uint32 regNO,Insn * startInsn,Insn * endInsn,bool findAll,bool analysisDone) const1024 std::vector<Insn *> ReachingDefinition::FindRegDefBetweenInsn(uint32 regNO, Insn *startInsn, Insn *endInsn,
1025                                                               bool findAll, bool analysisDone) const
1026 {
1027     std::vector<Insn *> defInsnVec;
1028     if (startInsn == nullptr || endInsn == nullptr) {
1029         return defInsnVec;
1030     }
1031 
1032     DEBUG_ASSERT(startInsn->GetBB() == endInsn->GetBB(), "two insns must be in a same BB");
1033     if (analysisDone && !regGen[startInsn->GetBB()->GetId()]->TestBit(regNO)) {
1034         return defInsnVec;
1035     }
1036 
1037     for (Insn *insn = endInsn; insn != nullptr && insn != startInsn->GetPrev(); insn = insn->GetPrev()) {
1038         if (!insn->IsMachineInstruction()) {
1039             continue;
1040         }
1041 
1042         if (insn->IsAsmInsn()) {
1043             if (SetDefInsnVecForAsm(insn, kAsmOutputListOpnd, regNO, defInsnVec) ||
1044                 SetDefInsnVecForAsm(insn, kAsmClobberListOpnd, regNO, defInsnVec)) {
1045                 if (findAll) {
1046                     defInsnVec.emplace_back(insn);
1047                 } else {
1048                     return defInsnVec;
1049                 }
1050             }
1051         }
1052         if (insn->IsCall() && IsRegKilledByCallInsn(*insn, regNO)) {
1053             defInsnVec.emplace_back(insn);
1054             if (!findAll) {
1055                 return defInsnVec;
1056             }
1057         }
1058         if (insn->IsRegDefined(regNO)) {
1059             defInsnVec.emplace_back(insn);
1060             if (!findAll) {
1061                 return defInsnVec;
1062             }
1063         }
1064     }
1065     return defInsnVec;
1066 }
1067 
RegIsUsedOrDefBetweenInsn(uint32 regNO,Insn & startInsn,Insn & endInsn) const1068 bool ReachingDefinition::RegIsUsedOrDefBetweenInsn(uint32 regNO, Insn &startInsn, Insn &endInsn) const
1069 {
1070     DEBUG_ASSERT(&startInsn != &endInsn, "startInsn is not equal to endInsn");
1071     if (startInsn.GetBB() == endInsn.GetBB()) {
1072         /* register is difined more than once */
1073         if (startInsn.GetId() > endInsn.GetId()) {
1074             return false;
1075         }
1076         if (startInsn.GetNext() == &endInsn) {
1077             return true;
1078         }
1079         if (regGen[startInsn.GetBB()->GetId()]->TestBit(regNO) &&
1080             !FindRegDefBetweenInsn(regNO, startInsn.GetNext(), endInsn.GetPrev()).empty()) {
1081             return false;
1082         }
1083         if (regUse[startInsn.GetBB()->GetId()]->TestBit(regNO)) {
1084             InsnSet useInsnSet;
1085             FindRegUseBetweenInsn(regNO, startInsn.GetNext(), endInsn.GetPrev(), useInsnSet);
1086             if (!useInsnSet.empty()) {
1087                 return false;
1088             }
1089         }
1090         if (IsCallerSavedReg(regNO) &&
1091             KilledByCallBetweenInsnInSameBB(*startInsn.GetNext(), *endInsn.GetPrev(), regNO)) {
1092             return false;
1093         }
1094         return true;
1095     }
1096 
1097     if (&startInsn != startInsn.GetBB()->GetLastInsn() && regGen[startInsn.GetBB()->GetId()]->TestBit(regNO) &&
1098         !FindRegDefBetweenInsn(regNO, startInsn.GetNext(), startInsn.GetBB()->GetLastInsn()).empty()) {
1099         return false;
1100     }
1101 
1102     if (regUse[startInsn.GetBB()->GetId()]->TestBit(regNO)) {
1103         InsnSet useInsnSet;
1104         FindRegUseBetweenInsn(regNO, startInsn.GetNext(), startInsn.GetBB()->GetLastInsn(), useInsnSet);
1105         if (!useInsnSet.empty()) {
1106             return false;
1107         }
1108     }
1109 
1110     if (&startInsn != startInsn.GetBB()->GetLastInsn() && IsCallerSavedReg(regNO) &&
1111         KilledByCallBetweenInsnInSameBB(*startInsn.GetNext(), *startInsn.GetBB()->GetLastInsn(), regNO)) {
1112         return false;
1113     }
1114 
1115     if (&endInsn != endInsn.GetBB()->GetFirstInsn() && regGen[endInsn.GetBB()->GetId()]->TestBit(regNO) &&
1116         !FindRegDefBetweenInsn(regNO, endInsn.GetBB()->GetFirstInsn(), endInsn.GetPrev()).empty()) {
1117         return false;
1118     }
1119 
1120     if (regUse[startInsn.GetBB()->GetId()]->TestBit(regNO)) {
1121         InsnSet useInsnSet;
1122         FindRegUseBetweenInsn(regNO, endInsn.GetBB()->GetFirstInsn(), endInsn.GetPrev(), useInsnSet);
1123         if (!useInsnSet.empty()) {
1124             return false;
1125         }
1126     }
1127 
1128     if (&endInsn != endInsn.GetBB()->GetFirstInsn() && IsCallerSavedReg(regNO) &&
1129         KilledByCallBetweenInsnInSameBB(*endInsn.GetBB()->GetFirstInsn(), *endInsn.GetPrev(), regNO)) {
1130         return false;
1131     }
1132 
1133     std::vector<bool> visitedBB(kMaxBBNum, false);
1134     return IsUseOrDefInAllPathBB(regNO, *startInsn.GetBB(), *endInsn.GetBB(), visitedBB);
1135 }
1136 
1137 /* check whether register may be redefined form in the same BB */
IsUseOrDefBetweenInsn(uint32 regNO,const BB & curBB,const Insn & startInsn,Insn & endInsn) const1138 bool ReachingDefinition::IsUseOrDefBetweenInsn(uint32 regNO, const BB &curBB, const Insn &startInsn,
1139                                                Insn &endInsn) const
1140 {
1141     if (regGen[curBB.GetId()]->TestBit(regNO)) {
1142         if (!FindRegDefBetweenInsn(regNO, startInsn.GetNext(), endInsn.GetPrev()).empty()) {
1143             return false;
1144         }
1145     }
1146     if (regUse[curBB.GetId()]->TestBit(regNO)) {
1147         InsnSet useInsnSet;
1148         FindRegUseBetweenInsn(regNO, startInsn.GetNext(), endInsn.GetPrev(), useInsnSet);
1149         if (!useInsnSet.empty()) {
1150             return false;
1151         }
1152     }
1153     return true;
1154 }
1155 
1156 /* check whether register may be redefined form startBB to endBB */
IsUseOrDefInAllPathBB(uint32 regNO,const BB & startBB,const BB & endBB,std::vector<bool> & visitedBB) const1157 bool ReachingDefinition::IsUseOrDefInAllPathBB(uint32 regNO, const BB &startBB, const BB &endBB,
1158                                                std::vector<bool> &visitedBB) const
1159 {
1160     for (auto succ : startBB.GetSuccs()) {
1161         if (visitedBB[succ->GetId()] || succ == &endBB) {
1162             continue;
1163         }
1164         visitedBB[succ->GetId()] = true;
1165         std::vector<bool> traversedPathSet(kMaxBBNum, false);
1166         bool canReachEndBB = true;
1167         if (regGen[succ->GetId()]->TestBit(regNO) || regUse[succ->GetId()]->TestBit(regNO) ||
1168             (succ->HasCall() && IsCallerSavedReg(regNO))) {
1169             canReachEndBB = CanReachEndBBFromCurrentBB(*succ, endBB, traversedPathSet);
1170             if (canReachEndBB) {
1171                 return false;
1172             }
1173         }
1174         if (!canReachEndBB) {
1175             continue;
1176         }
1177         bool isLive = IsUseOrDefInAllPathBB(regNO, *succ, endBB, visitedBB);
1178         if (!isLive) {
1179             return false;
1180         }
1181     }
1182 
1183     for (auto ehSucc : startBB.GetEhSuccs()) {
1184         if (visitedBB[ehSucc->GetId()]) {
1185             continue;
1186         }
1187         visitedBB[ehSucc->GetId()] = true;
1188         std::vector<bool> traversedPathSet(kMaxBBNum, false);
1189         bool canReachEndBB = true;
1190         if (regGen[ehSucc->GetId()]->TestBit(regNO) || regUse[ehSucc->GetId()]->TestBit(regNO)) {
1191             canReachEndBB = CanReachEndBBFromCurrentBB(*ehSucc, endBB, traversedPathSet);
1192             if (canReachEndBB) {
1193                 return false;
1194             }
1195         }
1196         if (!canReachEndBB) {
1197             continue;
1198         }
1199         bool isLive = IsUseOrDefInAllPathBB(regNO, *ehSucc, endBB, visitedBB);
1200         if (!isLive) {
1201             return false;
1202         }
1203     }
1204     return true;
1205 }
1206 
HasCallBetweenInsnInSameBB(const Insn & startInsn,const Insn & endInsn) const1207 bool ReachingDefinition::HasCallBetweenInsnInSameBB(const Insn &startInsn, const Insn &endInsn) const
1208 {
1209     DEBUG_ASSERT(startInsn.GetBB() == endInsn.GetBB(), "two insns must be in same bb");
1210     for (const Insn *insn = &startInsn; insn != endInsn.GetNext(); insn = insn->GetNext()) {
1211         if (insn->IsMachineInstruction() && insn->IsCall()) {
1212             return true;
1213         }
1214     }
1215     return false;
1216 }
1217 
1218 /* operand is only defined in startBB, and only used in endBB.
1219  * so traverse from endBB to startBB, all paths reach startBB finally.
1220  * startBB and endBB are different, and call insns in both of them are not counted.
1221  * whether startBB and endBB are in a loop is not counted.
1222  */
HasCallInPath(const BB & startBB,const BB & endBB,std::vector<bool> & visitedBB) const1223 bool ReachingDefinition::HasCallInPath(const BB &startBB, const BB &endBB, std::vector<bool> &visitedBB) const
1224 {
1225     DEBUG_ASSERT(&startBB != &endBB, "startBB and endBB are not counted");
1226     std::queue<const BB *> bbQueue;
1227     bbQueue.push(&endBB);
1228     visitedBB[endBB.GetId()] = true;
1229     while (!bbQueue.empty()) {
1230         const BB *bb = bbQueue.front();
1231         bbQueue.pop();
1232         for (auto predBB : bb->GetPreds()) {
1233             if (predBB == &startBB || visitedBB[predBB->GetId()]) {
1234                 continue;
1235             }
1236             if (predBB->HasCall()) {
1237                 return true;
1238             }
1239             visitedBB[predBB->GetId()] = true;
1240             bbQueue.push(predBB);
1241         }
1242         for (auto ehPredBB : bb->GetEhPreds()) {
1243             if (ehPredBB == &startBB || visitedBB[ehPredBB->GetId()]) {
1244                 continue;
1245             }
1246             if (ehPredBB->HasCall()) {
1247                 return true;
1248             }
1249             visitedBB[ehPredBB->GetId()] = true;
1250             bbQueue.push(ehPredBB);
1251         }
1252     }
1253     return false;
1254 }
1255 
1256 /* because of time cost, this function is not precise, BB in loop is not counted */
HasCallBetweenDefUse(const Insn & defInsn,const Insn & useInsn) const1257 bool ReachingDefinition::HasCallBetweenDefUse(const Insn &defInsn, const Insn &useInsn) const
1258 {
1259     if (defInsn.GetBB()->GetId() == useInsn.GetBB()->GetId()) {
1260         if (&useInsn == defInsn.GetNext()) {
1261             return false;
1262         }
1263         if (useInsn.GetId() > defInsn.GetId()) {
1264             return HasCallBetweenInsnInSameBB(defInsn, *useInsn.GetPrev());
1265         }
1266         /* useInsn is in front of defInsn, we think there is call insn between them conservatively */
1267         return true;
1268     }
1269     /* check defInsn->GetBB() */
1270     if (&defInsn != defInsn.GetBB()->GetLastInsn() && defInsn.GetBB()->HasCall() &&
1271         HasCallBetweenInsnInSameBB(*defInsn.GetNext(), *defInsn.GetBB()->GetLastInsn())) {
1272         return true;
1273     }
1274     /* check useInsn->GetBB() */
1275     if (&useInsn != useInsn.GetBB()->GetFirstInsn() && useInsn.GetBB()->HasCall() &&
1276         HasCallBetweenInsnInSameBB(*useInsn.GetBB()->GetFirstInsn(), *useInsn.GetPrev())) {
1277         return true;
1278     }
1279     std::vector<bool> visitedBB(kMaxBBNum, false);
1280     return HasCallInPath(*defInsn.GetBB(), *useInsn.GetBB(), visitedBB);
1281 }
1282 
EnlargeRegCapacity(uint32 size)1283 void ReachingDefinition::EnlargeRegCapacity(uint32 size)
1284 {
1285     FOR_ALL_BB(bb, cgFunc) {
1286         regIn[bb->GetId()]->EnlargeCapacityToAdaptSize(size);
1287         regOut[bb->GetId()]->EnlargeCapacityToAdaptSize(size);
1288         regGen[bb->GetId()]->EnlargeCapacityToAdaptSize(size);
1289         regUse[bb->GetId()]->EnlargeCapacityToAdaptSize(size);
1290     }
1291 }
1292 
DumpInfo(const BB & bb,DumpType flag) const1293 void ReachingDefinition::DumpInfo(const BB &bb, DumpType flag) const
1294 {
1295     const DataInfo *info = nullptr;
1296     switch (flag) {
1297         case kDumpRegGen:
1298             LogInfo::MapleLogger() << "    regGen:\n";
1299             info = regGen[bb.GetId()];
1300             break;
1301         case kDumpRegUse:
1302             LogInfo::MapleLogger() << "    regUse:\n";
1303             info = regUse[bb.GetId()];
1304             break;
1305         case kDumpRegIn:
1306             LogInfo::MapleLogger() << "    regIn:\n";
1307             info = regIn[bb.GetId()];
1308             break;
1309         case kDumpRegOut:
1310             LogInfo::MapleLogger() << "    regOut:\n";
1311             info = regOut[bb.GetId()];
1312             break;
1313         case kDumpMemGen:
1314             LogInfo::MapleLogger() << "    memGen:\n";
1315             info = memGen[bb.GetId()];
1316             break;
1317         case kDumpMemIn:
1318             LogInfo::MapleLogger() << "    memIn:\n";
1319             info = memIn[bb.GetId()];
1320             break;
1321         case kDumpMemOut:
1322             LogInfo::MapleLogger() << "    memOut:\n";
1323             info = memOut[bb.GetId()];
1324             break;
1325         case kDumpMemUse:
1326             LogInfo::MapleLogger() << "    memUse:\n";
1327             info = memUse[bb.GetId()];
1328             break;
1329         default:
1330             return;
1331     }
1332     DEBUG_ASSERT(info != nullptr, "null ptr check");
1333     uint32 count = 1;
1334     LogInfo::MapleLogger() << "        ";
1335     for (uint32 i = 0; i != info->Size(); ++i) {
1336         if (info->TestBit(i)) {
1337             count += 1;
1338             if (kDumpMemGen <= flag && flag <= kDumpMemUse) {
1339                 /* Each element i means a 4 byte stack slot. */
1340                 LogInfo::MapleLogger() << (i * 4) << " ";
1341             } else {
1342                 LogInfo::MapleLogger() << i << " ";
1343             }
1344             /* 10 output per line */
1345             if (count % 10 == 0) {
1346                 LogInfo::MapleLogger() << "\n";
1347                 LogInfo::MapleLogger() << "        ";
1348             }
1349         }
1350     }
1351 
1352     LogInfo::MapleLogger() << "\n";
1353 }
1354 
DumpBBCGIR(const BB & bb) const1355 void ReachingDefinition::DumpBBCGIR(const BB &bb) const
1356 {
1357     if (bb.IsCleanup()) {
1358         LogInfo::MapleLogger() << "[is_cleanup] ";
1359     }
1360     if (bb.IsUnreachable()) {
1361         LogInfo::MapleLogger() << "[unreachable] ";
1362     }
1363     if (bb.GetSuccs().size()) {
1364         LogInfo::MapleLogger() << "      succs: ";
1365         for (auto *succBB : bb.GetSuccs()) {
1366             LogInfo::MapleLogger() << succBB->GetId() << " ";
1367         }
1368     }
1369     if (bb.GetEhSuccs().size()) {
1370         LogInfo::MapleLogger() << "      eh_succs: ";
1371         for (auto *ehSuccBB : bb.GetEhSuccs()) {
1372             LogInfo::MapleLogger() << ehSuccBB->GetId() << " ";
1373         }
1374     }
1375     LogInfo::MapleLogger() << "\n";
1376 
1377     FOR_BB_INSNS_CONST(insn, &bb) {
1378         LogInfo::MapleLogger() << "        ";
1379         insn->Dump();
1380     }
1381     LogInfo::MapleLogger() << "\n";
1382 }
1383 
Dump(uint32 flag) const1384 void ReachingDefinition::Dump(uint32 flag) const
1385 {
1386     MIRSymbol *mirSymbol = GlobalTables::GetGsymTable().GetSymbolFromStidx(cgFunc->GetFunction().GetStIdx().Idx());
1387     DEBUG_ASSERT(mirSymbol != nullptr, "get symbol in function failed in ReachingDefinition::Dump");
1388     LogInfo::MapleLogger() << "\n----  Reaching definition analysis for " << mirSymbol->GetName();
1389     LogInfo::MapleLogger() << " ----\n";
1390     FOR_ALL_BB(bb, cgFunc) {
1391         LogInfo::MapleLogger() << "  === BB_" << bb->GetId() << " ===\n";
1392 
1393         if (flag & kDumpBBCGIR) {
1394             DumpBBCGIR(*bb);
1395         }
1396 
1397         if (flag & kDumpRegIn) {
1398             DumpInfo(*bb, kDumpRegIn);
1399         }
1400 
1401         if (flag & kDumpRegUse) {
1402             DumpInfo(*bb, kDumpRegUse);
1403         }
1404 
1405         if (flag & kDumpRegGen) {
1406             DumpInfo(*bb, kDumpRegGen);
1407         }
1408 
1409         if (flag & kDumpRegOut) {
1410             DumpInfo(*bb, kDumpRegOut);
1411         }
1412 
1413         if (flag & kDumpMemIn) {
1414             DumpInfo(*bb, kDumpMemIn);
1415         }
1416 
1417         if (flag & kDumpMemGen) {
1418             DumpInfo(*bb, kDumpMemGen);
1419         }
1420 
1421         if (flag & kDumpMemOut) {
1422             DumpInfo(*bb, kDumpMemOut);
1423         }
1424 
1425         if (flag & kDumpMemUse) {
1426             DumpInfo(*bb, kDumpMemUse);
1427         }
1428     }
1429     LogInfo::MapleLogger() << "------------------------------------------------------\n";
1430 }
1431 
PhaseRun(maplebe::CGFunc & f)1432 bool CgReachingDefinition::PhaseRun(maplebe::CGFunc &f)
1433 {
1434 #if TARGAARCH64 || TARGRISCV64
1435     reachingDef = GetPhaseAllocator()->New<AArch64ReachingDefinition>(f, *GetPhaseMemPool());
1436 #endif
1437 #if TARGARM32
1438     reachingDef = GetPhaseAllocator()->New<Arm32ReachingDefinition>(f, *GetPhaseMemPool());
1439 #endif
1440     reachingDef->SetAnalysisMode(kRDAllAnalysis);
1441     reachingDef->AnalysisStart();
1442     return false;
1443 }
MAPLE_ANALYSIS_PHASE_REGISTER(CgReachingDefinition,reachingdefinition)1444 MAPLE_ANALYSIS_PHASE_REGISTER(CgReachingDefinition, reachingdefinition)
1445 
1446 bool CgClearRDInfo::PhaseRun(maplebe::CGFunc &f)
1447 {
1448     if (f.GetRDStatus()) {
1449         f.GetRD()->ClearDefUseInfo();
1450     }
1451     return false;
1452 }
1453 MAPLE_TRANSFORM_PHASE_REGISTER(CgClearRDInfo, clearrdinfo)
1454 } /* namespace maplebe */
1455