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 ++realOccIt;
139 if (realOccIt != workCand->GetRealOccs().end()) {
140 nextRealOcc = *realOccIt;
141 } else {
142 nextRealOcc = nullptr;
143 }
144 break;
145 }
146 case kOccExit: {
147 ++exitOccIt;
148 if (exitOccIt != exitOccs.end()) {
149 nextExitOcc = *exitOccIt;
150 } else {
151 nextExitOcc = nullptr;
152 }
153 break;
154 }
155 case kOccPhiocc: {
156 ++phiIt;
157 if (phiIt != phiOccs.end()) {
158 nextPhiOcc = *phiIt;
159 } else {
160 nextPhiOcc = nullptr;
161 }
162 break;
163 }
164 case kOccPhiopnd: {
165 ++phiOpndIt;
166 if (phiOpndIt != phiOpnds.end()) {
167 nextPhiOpndOcc = *phiOpndIt;
168 } else {
169 nextPhiOpndOcc = nullptr;
170 }
171 break;
172 }
173 default:
174 DEBUG_ASSERT(false, "CreateSortedOccs: unexpected occty");
175 break;
176 }
177 }
178 } while (pickedOcc != nullptr);
179 }
180
CreateRealOcc(Insn & insn,Operand & opnd,OccType occType)181 CgOccur *CGPre::CreateRealOcc(Insn &insn, Operand &opnd, OccType occType)
182 {
183 uint64 hashIdx = PreWorkCandHashTable::ComputeWorkCandHashIndex(opnd);
184 PreWorkCand *wkCand = preWorkCandHashTable.GetWorkcandFromIndex(hashIdx);
185 while (wkCand != nullptr) {
186 Operand *currOpnd = wkCand->GetTheOperand();
187 DEBUG_ASSERT(currOpnd != nullptr, "CreateRealOcc: found workcand with theMeExpr as nullptr");
188 if (currOpnd == &opnd) {
189 break;
190 }
191 wkCand = static_cast<PreWorkCand *>(wkCand->GetNext());
192 }
193
194 CgOccur *newOcc = nullptr;
195 switch (occType) {
196 case kOccDef:
197 newOcc = ssaPreMemPool->New<CgDefOcc>(insn.GetBB(), &insn, &opnd);
198 break;
199 case kOccStore:
200 newOcc = ssaPreMemPool->New<CgStoreOcc>(insn.GetBB(), &insn, &opnd);
201 break;
202 case kOccUse:
203 newOcc = ssaPreMemPool->New<CgUseOcc>(insn.GetBB(), &insn, &opnd);
204 break;
205 default:
206 CHECK_FATAL(false, "unsupported occur type");
207 break;
208 }
209
210 if (wkCand != nullptr) {
211 wkCand->AddRealOccAsLast(*newOcc, GetPUIdx());
212 return newOcc;
213 }
214
215 // workcand not yet created; create a new one and add to worklist
216 wkCand = ssaPreMemPool->New<PreWorkCand>(ssaPreAllocator, &opnd, GetPUIdx());
217 workList.push_back(wkCand);
218 wkCand->AddRealOccAsLast(*newOcc, GetPUIdx());
219 // add to bucket at workcandHashTable[hashIdx]
220 wkCand->SetNext(*preWorkCandHashTable.GetWorkcandFromIndex(hashIdx));
221 preWorkCandHashTable.SetWorkCandAt(hashIdx, *wkCand);
222 return newOcc;
223 }
224 } // namespace maplebe
225