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 "cg_pre.h"
17 #include "cg_dominance.h"
18 #include "aarch64_cg.h"
19
20 namespace maplebe {
21 /* Implement PRE in cgir */
ResetDS(CgPhiOcc * phiOcc)22 void CGPre::ResetDS(CgPhiOcc *phiOcc)
23 {
24 if (!phiOcc->IsDownSafe()) {
25 return;
26 }
27
28 phiOcc->SetIsDownSafe(false);
29 for (auto *phiOpnd : phiOcc->GetPhiOpnds()) {
30 auto *defOcc = phiOpnd->GetDef();
31 if (defOcc != nullptr && defOcc->GetOccType() == kOccPhiocc) {
32 ResetDS(static_cast<CgPhiOcc *>(defOcc));
33 }
34 }
35 }
36
ComputeDS()37 void CGPre::ComputeDS()
38 {
39 for (auto phiIt = phiOccs.rbegin(); phiIt != phiOccs.rend(); ++phiIt) {
40 auto *phiOcc = *phiIt;
41 if (phiOcc->IsDownSafe()) {
42 continue;
43 }
44 for (auto *phiOpnd : phiOcc->GetPhiOpnds()) {
45 if (phiOpnd->HasRealUse()) {
46 continue;
47 }
48 auto *defOcc = phiOpnd->GetDef();
49 if (defOcc != nullptr && defOcc->GetOccType() == kOccPhiocc) {
50 ResetDS(static_cast<CgPhiOcc *>(defOcc));
51 }
52 }
53 }
54 }
55
56 /* based on ssapre->workCand's realOccs and dfPhiDfns (which now privides all
57 the inserted phis), create the phi and phiOpnd occ nodes; link them all up in
58 order of dt_preorder in ssapre->allOccs; the phi occ nodes are in addition
59 provided in order of dt_preorder in ssapre->phiOccs */
CreateSortedOccs()60 void CGPre::CreateSortedOccs()
61 {
62 // merge varPhiDfns to dfPhiDfns
63 dfPhiDfns.insert(varPhiDfns.begin(), varPhiDfns.end());
64
65 auto comparator = [this](const CgPhiOpndOcc *occA, const CgPhiOpndOcc *occB) -> bool {
66 return dom->GetDtDfnItem(occA->GetBB()->GetId()) < dom->GetDtDfnItem(occB->GetBB()->GetId());
67 };
68
69 std::vector<CgPhiOpndOcc *> phiOpnds;
70 for (auto dfn : dfPhiDfns) {
71 uint32 bbId = dom->GetDtPreOrderItem(dfn);
72 BB *bb = GetBB(bbId);
73 auto *phiOcc = perCandMemPool->New<CgPhiOcc>(*bb, workCand->GetTheOperand(), perCandAllocator);
74 phiOccs.push_back(phiOcc);
75
76 for (BB *pred : bb->GetPreds()) {
77 auto phiOpnd = perCandMemPool->New<CgPhiOpndOcc>(pred, workCand->GetTheOperand(), phiOcc);
78 phiOpnds.push_back(phiOpnd);
79 phiOcc->AddPhiOpnd(*phiOpnd);
80 phiOpnd->SetPhiOcc(*phiOcc);
81 }
82 }
83 std::sort(phiOpnds.begin(), phiOpnds.end(), comparator);
84
85 auto realOccIt = workCand->GetRealOccs().begin();
86 auto exitOccIt = exitOccs.begin();
87 auto phiIt = phiOccs.begin();
88 auto phiOpndIt = phiOpnds.begin();
89
90 CgOccur *nextRealOcc = nullptr;
91 if (realOccIt != workCand->GetRealOccs().end()) {
92 nextRealOcc = *realOccIt;
93 }
94
95 CgOccur *nextExitOcc = nullptr;
96 if (exitOccIt != exitOccs.end()) {
97 nextExitOcc = *exitOccIt;
98 }
99
100 CgPhiOcc *nextPhiOcc = nullptr;
101 if (phiIt != phiOccs.end()) {
102 nextPhiOcc = *phiIt;
103 }
104
105 CgPhiOpndOcc *nextPhiOpndOcc = nullptr;
106 if (phiOpndIt != phiOpnds.end()) {
107 nextPhiOpndOcc = *phiOpndIt;
108 }
109
110 CgOccur *pickedOcc; // the next picked occ in order of preorder traveral of dominator tree
111 do {
112 pickedOcc = nullptr;
113 // the 4 kinds of occ must be checked in this order, so it will be right
114 // if more than 1 has the same dfn
115 if (nextPhiOcc != nullptr) {
116 pickedOcc = nextPhiOcc;
117 }
118 if (nextRealOcc != nullptr && (pickedOcc == nullptr || dom->GetDtDfnItem(nextRealOcc->GetBB()->GetId()) <
119 dom->GetDtDfnItem(pickedOcc->GetBB()->GetId()))) {
120 pickedOcc = nextRealOcc;
121 }
122 if (nextExitOcc != nullptr && (pickedOcc == nullptr || dom->GetDtDfnItem(nextExitOcc->GetBB()->GetId()) <
123 dom->GetDtDfnItem(pickedOcc->GetBB()->GetId()))) {
124 pickedOcc = nextExitOcc;
125 }
126 if (nextPhiOpndOcc != nullptr && (pickedOcc == nullptr || dom->GetDtDfnItem(nextPhiOpndOcc->GetBB()->GetId()) <
127 dom->GetDtDfnItem(pickedOcc->GetBB()->GetId()))) {
128 pickedOcc = nextPhiOpndOcc;
129 }
130 if (pickedOcc != nullptr) {
131 allOccs.push_back(pickedOcc);
132 switch (pickedOcc->GetOccType()) {
133 case kOccReal:
134 case kOccUse:
135 case kOccDef:
136 case kOccStore:
137 case kOccMembar: {
138 DEBUG_ASSERT(realOccIt != workCand->GetRealOccs().end(), "realOccIt should not be end");
139 ++realOccIt;
140 if (realOccIt != workCand->GetRealOccs().end()) {
141 nextRealOcc = *realOccIt;
142 } else {
143 nextRealOcc = nullptr;
144 }
145 break;
146 }
147 case kOccExit: {
148 DEBUG_ASSERT(exitOccIt != exitOccs.end(), "must be valid iterator");
149 ++exitOccIt;
150 if (exitOccIt != exitOccs.end()) {
151 nextExitOcc = *exitOccIt;
152 } else {
153 nextExitOcc = nullptr;
154 }
155 break;
156 }
157 case kOccPhiocc: {
158 DEBUG_ASSERT(phiIt != phiOccs.end(), "must be valid iterator");
159 ++phiIt;
160 if (phiIt != phiOccs.end()) {
161 nextPhiOcc = *phiIt;
162 } else {
163 nextPhiOcc = nullptr;
164 }
165 break;
166 }
167 case kOccPhiopnd: {
168 DEBUG_ASSERT(phiOpndIt != phiOpnds.end(), "phiOpndIt should not be end");
169 ++phiOpndIt;
170 if (phiOpndIt != phiOpnds.end()) {
171 nextPhiOpndOcc = *phiOpndIt;
172 } else {
173 nextPhiOpndOcc = nullptr;
174 }
175 break;
176 }
177 default:
178 DEBUG_ASSERT(false, "CreateSortedOccs: unexpected occty");
179 break;
180 }
181 }
182 } while (pickedOcc != nullptr);
183 }
184
CreateRealOcc(Insn & insn,Operand & opnd,OccType occType)185 CgOccur *CGPre::CreateRealOcc(Insn &insn, Operand &opnd, OccType occType)
186 {
187 uint64 hashIdx = PreWorkCandHashTable::ComputeWorkCandHashIndex(opnd);
188 PreWorkCand *wkCand = preWorkCandHashTable.GetWorkcandFromIndex(hashIdx);
189 while (wkCand != nullptr) {
190 Operand *currOpnd = wkCand->GetTheOperand();
191 DEBUG_ASSERT(currOpnd != nullptr, "CreateRealOcc: found workcand with theMeExpr as nullptr");
192 if (currOpnd == &opnd) {
193 break;
194 }
195 wkCand = static_cast<PreWorkCand *>(wkCand->GetNext());
196 }
197
198 CgOccur *newOcc = nullptr;
199 switch (occType) {
200 case kOccDef:
201 newOcc = ssaPreMemPool->New<CgDefOcc>(insn.GetBB(), &insn, &opnd);
202 break;
203 case kOccStore:
204 newOcc = ssaPreMemPool->New<CgStoreOcc>(insn.GetBB(), &insn, &opnd);
205 break;
206 case kOccUse:
207 newOcc = ssaPreMemPool->New<CgUseOcc>(insn.GetBB(), &insn, &opnd);
208 break;
209 default:
210 CHECK_FATAL(false, "unsupported occur type");
211 break;
212 }
213
214 if (wkCand != nullptr) {
215 wkCand->AddRealOccAsLast(*newOcc, GetPUIdx());
216 return newOcc;
217 }
218
219 // workcand not yet created; create a new one and add to worklist
220 wkCand = ssaPreMemPool->New<PreWorkCand>(ssaPreAllocator, &opnd, GetPUIdx());
221 workList.push_back(wkCand);
222 wkCand->AddRealOccAsLast(*newOcc, GetPUIdx());
223 // add to bucket at workcandHashTable[hashIdx]
224 wkCand->SetNext(*preWorkCandHashTable.GetWorkcandFromIndex(hashIdx));
225 preWorkCandHashTable.SetWorkCandAt(hashIdx, *wkCand);
226 return newOcc;
227 }
228 } // namespace maplebe
229