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 "mad.h"
17 #include <string>
18 #include <algorithm>
19 #if TARGAARCH64
20 #include "aarch64_operand.h"
21 #endif
22 #if defined(TARGRISCV64) && TARGRISCV64
23 #include "riscv64_operand.h"
24 #endif
25 #include "schedule.h"
26 #include "insn.h"
27
28 namespace maplebe {
29 const std::string kUnitName[] = {
30 #include "mplad_unit_name.def"
31 "None",
32 };
33 /* Unit */
Unit(enum UnitId theUnitId)34 Unit::Unit(enum UnitId theUnitId) : unitId(theUnitId), unitType(kUnitTypePrimart), occupancyTable(), compositeUnits()
35 {
36 MAD::AddUnit(*this);
37 }
38
Unit(enum UnitType theUnitType,enum UnitId theUnitId,int numOfUnits,...)39 Unit::Unit(enum UnitType theUnitType, enum UnitId theUnitId, int numOfUnits, ...)
40 : unitId(theUnitId), unitType(theUnitType), occupancyTable()
41 {
42 DEBUG_ASSERT(numOfUnits > 1, "CG internal error, composite unit with less than 2 unit elements.");
43 va_list ap;
44 va_start(ap, numOfUnits);
45
46 for (int i = 0; i < numOfUnits; ++i) {
47 compositeUnits.emplace_back(static_cast<Unit *>(va_arg(ap, Unit *)));
48 }
49 va_end(ap);
50
51 MAD::AddUnit(*this);
52 }
53
54 /* return name of unit */
GetName() const55 std::string Unit::GetName() const
56 {
57 DEBUG_ASSERT(GetUnitId() <= kUnitIdLast, "Unexpected UnitID");
58 return kUnitName[GetUnitId()];
59 }
60
61 /* If the unit is idle in the CYCLE, return true */
IsIdle(uint32 cycle) const62 bool Unit::IsIdle(uint32 cycle) const
63 {
64 if (unitType == kUnitTypeOr) {
65 // For 'or'-unit, if one of them is idle, return true
66 for (Unit *unit : compositeUnits) {
67 if (unit->IsIdle(cycle)) {
68 return true;
69 }
70 }
71 return false;
72 } else if (GetUnitType() == kUnitTypeAnd) {
73 // For 'and'-unit, if all of them are idle, return true
74 for (auto *unit : compositeUnits) {
75 if (!unit->IsIdle(cycle)) {
76 return false;
77 }
78 }
79 return true;
80 }
81 return ((occupancyTable & std::bitset<kOccupyWidth>(1u << cycle)) == 0);
82 }
83
84 /* Occupy unit in the CYCLE */
Occupy(uint32 cycle)85 void Unit::Occupy(uint32 cycle)
86 {
87 if (GetUnitType() == kUnitTypeOr) {
88 // For 'or'-unit, occupy the first idle unit
89 for (auto unit : GetCompositeUnits()) {
90 if (unit->IsIdle(cycle)) {
91 unit->Occupy(cycle);
92 return;
93 }
94 }
95 // If there is no return before, there is an error.
96 CHECK_FATAL(false, "when the instruction issue, all units it required must be idle");
97 } else if (GetUnitType() == kUnitTypeAnd) {
98 // For 'and'-unit, occupy all the unit
99 for (auto unit : GetCompositeUnits()) {
100 unit->Occupy(cycle);
101 }
102 return;
103 }
104 occupancyTable |= (1ULL << cycle);
105 }
106
107 /* Advance one cpu cycle, and update the occupation status of all units */
AdvanceOneCycle()108 void Unit::AdvanceOneCycle()
109 {
110 if (GetUnitType() != kUnitTypePrimart) {
111 return;
112 }
113 occupancyTable = (occupancyTable >> 1);
114 }
115
116 /* Release all units. */
Release()117 void Unit::Release()
118 {
119 if (GetUnitType() != kUnitTypePrimart) {
120 return;
121 }
122 occupancyTable = 0;
123 }
124
GetCompositeUnits() const125 const std::vector<Unit *> &Unit::GetCompositeUnits() const
126 {
127 return compositeUnits;
128 }
129
PrintIndent(int indent) const130 void Unit::PrintIndent(int indent) const
131 {
132 for (int i = 0; i < indent; ++i) {
133 LogInfo::MapleLogger() << " ";
134 }
135 }
136
Dump(int indent) const137 void Unit::Dump(int indent) const
138 {
139 PrintIndent(indent);
140 LogInfo::MapleLogger() << "Unit " << GetName() << " (ID " << GetUnitId() << "): ";
141 LogInfo::MapleLogger() << "occupancyTable = " << occupancyTable << '\n';
142 }
143
GetOccupancyTable() const144 std::bitset<kOccupyWidth> Unit::GetOccupancyTable() const
145 {
146 return occupancyTable;
147 }
148
149 /* MAD */
150 int MAD::parallelism;
151 std::vector<Unit *> MAD::allUnits;
152 std::vector<Reservation *> MAD::allReservations;
153 std::array<std::array<MAD::BypassVector, kLtLast>, kLtLast> MAD::bypassArrays;
154
~MAD()155 MAD::~MAD()
156 {
157 for (auto unit : allUnits) {
158 delete unit;
159 }
160 for (auto rev : allReservations) {
161 delete rev;
162 }
163 for (auto &bypassArray : bypassArrays) {
164 for (auto &bypassVector : bypassArray) {
165 for (auto *bypass : bypassVector) {
166 delete bypass;
167 }
168 bypassVector.clear();
169 }
170 }
171 allUnits.clear();
172 allReservations.clear();
173 }
174
InitParallelism() const175 void MAD::InitParallelism() const {
176 #include "mplad_arch_define.def"
177 }
178
179 /* Return the reservation by latencyType of the instruction */
FindReservation(const Insn & insn) const180 Reservation *MAD::FindReservation(const Insn &insn) const
181 {
182 uint32 insnType = insn.GetLatencyType();
183 for (auto reservation : allReservations) {
184 if (reservation->IsEqual(insnType)) {
185 return reservation;
186 }
187 }
188 return nullptr;
189 }
190
191 /* Return latency from producer instruction to consumer instruction */
GetLatency(const Insn & def,const Insn & use) const192 int MAD::GetLatency(const Insn &def, const Insn &use) const
193 {
194 int latency = BypassLatency(def, use);
195 if (latency < 0) {
196 latency = DefaultLatency(def);
197 }
198 return latency;
199 }
200
201 /* Return latency according to latency from producer instruction to consumer instruction */
BypassLatency(const Insn & def,const Insn & use) const202 int MAD::BypassLatency(const Insn &def, const Insn &use) const
203 {
204 int latency = -1;
205 DEBUG_ASSERT(def.GetLatencyType() < kLtLast, "out of range");
206 DEBUG_ASSERT(use.GetLatencyType() < kLtLast, "out of range");
207 BypassVector &bypassVec = bypassArrays[def.GetLatencyType()][use.GetLatencyType()];
208 for (auto bypass : bypassVec) {
209 if (bypass->CanBypass(def, use)) {
210 latency = bypass->GetLatency();
211 break;
212 }
213 }
214 return latency;
215 }
216
217 /* Return default cost of the instruction */
DefaultLatency(const Insn & insn) const218 int MAD::DefaultLatency(const Insn &insn) const
219 {
220 Reservation *res = insn.GetDepNode()->GetReservation();
221 return res != nullptr ? res->GetLatency() : 0;
222 }
223
224 /* In the dual-issue arch, if two slots are occupied in the current cycle,
225 * return true
226 */
IsFullIssued() const227 bool MAD::IsFullIssued() const
228 {
229 return !GetUnitByUnitId(kUnitIdSlot0)->IsIdle(0) && !GetUnitByUnitId(kUnitIdSlot1)->IsIdle(0);
230 }
231
AdvanceOneCycleForAll() const232 void MAD::AdvanceOneCycleForAll() const
233 {
234 for (auto unit : allUnits) {
235 unit->AdvanceOneCycle();
236 }
237 }
238
ReleaseAllUnits() const239 void MAD::ReleaseAllUnits() const
240 {
241 for (auto unit : allUnits) {
242 unit->Release();
243 }
244 }
245
SaveStates(std::vector<std::bitset<kOccupyWidth>> & occupyTable,int size) const246 void MAD::SaveStates(std::vector<std::bitset<kOccupyWidth>> &occupyTable, int size) const
247 {
248 int i = 0;
249 for (auto unit : allUnits) {
250 CHECK_FATAL(i < size, "unit number error");
251 occupyTable[i] = unit->GetOccupancyTable();
252 ++i;
253 }
254 }
255
256 #define ADDBYPASS(DEFLTTY, USELTTY, LT) AddBypass(*(new Bypass(DEFLTTY, USELTTY, LT)))
257 #define ADDALUSHIFTBYPASS(DEFLTTY, USELTTY, LT) AddBypass(*(new AluShiftBypass(DEFLTTY, USELTTY, LT)))
258 #define ADDACCUMULATORBYPASS(DEFLTTY, USELTTY, LT) AddBypass(*(new AccumulatorBypass(DEFLTTY, USELTTY, LT)))
259 #define ADDSTOREADDRBYPASS(DEFLTTY, USELTTY, LT) AddBypass(*(new StoreAddrBypass(DEFLTTY, USELTTY, LT)))
260
InitBypass() const261 void MAD::InitBypass() const
262 {
263 #include "mplad_bypass_define.def"
264 }
265
RestoreStates(std::vector<std::bitset<kOccupyWidth>> & occupyTable,int size) const266 void MAD::RestoreStates(std::vector<std::bitset<kOccupyWidth>> &occupyTable, int size) const
267 {
268 int i = 0;
269 for (auto unit : allUnits) {
270 CHECK_FATAL(i < size, "unit number error");
271 unit->SetOccupancyTable(occupyTable[i]);
272 ++i;
273 }
274 }
275
CanBypass(const Insn & defInsn,const Insn & useInsn) const276 bool Bypass::CanBypass(const Insn &defInsn, const Insn &useInsn) const
277 {
278 (void)defInsn;
279 (void)useInsn;
280 return true;
281 }
282
283 /* Return true if the USEINSN is an arithmetic or logic or shift instruction,
284 * and the defOpnd of DEFINSN is not used in shift operation of USEINSN.
285 * e.g.
286 * true: r3=r2+x1 -> r5=r4<<0x2+r3
287 * false: r3=r2+x1 -> r5=r3<<0x2+r4
288 */
CanBypass(const Insn & defInsn,const Insn & useInsn) const289 bool AluShiftBypass::CanBypass(const Insn &defInsn, const Insn &useInsn) const
290 {
291 RegOperand *productOpnd = nullptr;
292 uint32 defOpndNum = defInsn.GetOperandSize();
293 for (uint32 i = 0; i < defOpndNum; ++i) {
294 if (defInsn.OpndIsDef(i)) {
295 Operand &opnd = defInsn.GetOperand(i);
296 CHECK_FATAL(opnd.IsRegister(), "invalid producer insn of type alu-shift");
297 productOpnd = &static_cast<RegOperand &>(opnd);
298 break;
299 }
300 }
301 CHECK_NULL_FATAL(productOpnd);
302 uint32 useOpndNum = useInsn.GetOperandSize();
303 if (useOpndNum <= kInsnThirdOpnd) { // operand_size <= 2
304 return true;
305 }
306 Operand &lastUseOpnd = useInsn.GetOperand(useOpndNum - 1);
307 if (lastUseOpnd.GetKind() != Operand::kOpdShift && lastUseOpnd.GetKind() == Operand::kOpdExtend &&
308 lastUseOpnd.GetKind() == Operand::kOpdRegShift) {
309 return true;
310 }
311 Operand &shiftOpnd = useInsn.GetOperand(useOpndNum - 2);
312 if (shiftOpnd.GetKind() != Operand::kOpdRegister) {
313 return true;
314 }
315 if (static_cast<RegOperand &>(shiftOpnd).GetRegisterNumber() == productOpnd->GetRegisterNumber()) {
316 return false;
317 }
318 return true;
319 }
320
321 /* Return true if the defOpnd of DEFINSN is used in the accumulator
322 * operation(MLA-like) of USEINSN. In aarch64, the MOPs are in {madd, msub,
323 * fmadd, fmsub, fnmadd, fnmsub} e.g. The USEINSN is {madd|msub} and the defOpnd
324 * is used in the following cases: true: r98=x0*x1 -> x0=x2*x3+r98
325 * false:r98=x0*x1 -> x0=x2*r98+x3
326 */
CanBypass(const Insn & defInsn,const Insn & useInsn) const327 bool AccumulatorBypass::CanBypass(const Insn &defInsn, const Insn &useInsn) const
328 {
329 RegOperand *productOpnd = nullptr;
330 uint32 defOpndNum = defInsn.GetOperandSize();
331 for (uint32 i = 0; i < defOpndNum; ++i) {
332 if (defInsn.OpndIsDef(i)) {
333 Operand &opnd = defInsn.GetOperand(i);
334 CHECK_FATAL(opnd.IsRegister(), "invalid producer insn of type alu-shift");
335 productOpnd = &static_cast<RegOperand &>(opnd);
336 break;
337 }
338 }
339 CHECK_NULL_FATAL(productOpnd);
340 // Currently, the MOPs of valid USEINSN are in {madd, msub, fmadd, fmsub,
341 // fnmadd, fnmsub}, that have four operands of LATENCYTYPE kLtMul and
342 // kLtFpmac.
343 uint32 useOpndNum = useInsn.GetOperandSize();
344 if (useOpndNum != kInsnFifthOpnd) { // operand_size != 4
345 return false;
346 }
347 // Get accumulator operand
348 Operand &accuOpnd = useInsn.GetOperand(useOpndNum - 1);
349 CHECK_FATAL(accuOpnd.IsRegister(), "invalid consumer insn of type mul");
350 if (static_cast<RegOperand &>(accuOpnd).GetRegisterNumber() == productOpnd->GetRegisterNumber()) {
351 return true;
352 }
353 return false;
354 }
355
356 /* Return true if the USEINSN(an integer store) does not use the defOpnd of
357 * DEFINSN to calculate the mem address. e.g. true: r96=r92+x2 -> str r96, [r92]
358 * false: r96=r92+x2 -> str r92, [r96, #8]
359 * false: r96=r92+x2 -> str r92, [r94, r96]
360 */
CanBypass(const Insn & defInsn,const Insn & useInsn) const361 bool StoreAddrBypass::CanBypass(const Insn &defInsn, const Insn &useInsn) const
362 {
363 // Only for LATENCY-TYPE {kLtStore1, kLtStore2, kLtStore3plus}
364 if (useInsn.GetLatencyType() != kLtStore1 && useInsn.GetLatencyType() != kLtStore2 &&
365 useInsn.GetLatencyType() != kLtStore3plus) {
366 return false;
367 }
368 RegOperand *productOpnd = nullptr;
369 uint32 defOpndNum = defInsn.GetOperandSize();
370 for (uint32 i = 0; i < defOpndNum; ++i) {
371 if (defInsn.OpndIsDef(i)) {
372 Operand &opnd = defInsn.GetOperand(i);
373 CHECK_FATAL(opnd.IsRegister(), "invalid producer insn of type alu-shift");
374 productOpnd = &static_cast<RegOperand &>(opnd);
375 break;
376 }
377 }
378 CHECK_NULL_FATAL(productOpnd);
379 uint32 useOpndNum = useInsn.GetOperandSize();
380 for (uint32 i = 0; i < useOpndNum; ++i) {
381 Operand &opnd = useInsn.GetOperand(i);
382 if (opnd.GetKind() == Operand::kOpdMem) {
383 auto &memOpnd = static_cast<MemOperand &>(opnd);
384 RegOperand *baseOpnd = memOpnd.GetBaseRegister();
385 RegOperand *indexOpnd = memOpnd.GetIndexRegister();
386 if (baseOpnd != nullptr && baseOpnd->GetRegisterNumber() == productOpnd->GetRegisterNumber()) {
387 return false;
388 }
389 if (indexOpnd != nullptr && indexOpnd->GetRegisterNumber() == productOpnd->GetRegisterNumber()) {
390 return false;
391 }
392 break;
393 }
394 }
395 return true;
396 }
397
398 /* Reservation */
Reservation(LatencyType t,int l,int n,...)399 Reservation::Reservation(LatencyType t, int l, int n, ...) : type(t), latency(l), unitNum(n)
400 {
401 DEBUG_ASSERT(l >= 0, "CG internal error, latency and unitNum should not be less than 0.");
402 DEBUG_ASSERT(n >= 0, "CG internal error, latency and unitNum should not be less than 0.");
403
404 errno_t ret = memset_s(units, sizeof(Unit *) * kMaxUnit, 0, sizeof(Unit *) * kMaxUnit);
405 CHECK_FATAL(ret == EOK, "call memset_s failed in Reservation");
406
407 va_list ap;
408 va_start(ap, n);
409 for (uint32 i = 0; i < unitNum; ++i) {
410 units[i] = static_cast<Unit *>(va_arg(ap, Unit *));
411 }
412 va_end(ap);
413
414 MAD::AddReservation(*this);
415 /* init slot */
416 if (n > 0) {
417 /* if there are units, init slot by units[0] */
418 slot = GetSlotType(units[0]->GetUnitId());
419 } else {
420 slot = kSlotNone;
421 }
422 }
423
424 const std::string kSlotName[] = {
425 "SlotNone", "Slot0", "Slot1", "SlotAny", "Slots",
426 };
427
GetSlotName() const428 const std::string &Reservation::GetSlotName() const
429 {
430 DEBUG_ASSERT(GetSlot() <= kSlots, "Unexpected slot");
431 return kUnitName[GetSlot()];
432 }
433
434 /* Get slot type by unit id */
GetSlotType(UnitId unitID) const435 SlotType Reservation::GetSlotType(UnitId unitID) const
436 {
437 switch (unitID) {
438 case kUnitIdSlot0:
439 case kUnitIdSlot0LdAgu:
440 case kUnitIdSlot0StAgu:
441 return kSlot0;
442
443 case kUnitIdSlot1:
444 return kSlot1;
445
446 case kUnitIdSlotS:
447 case kUnitIdSlotSHazard:
448 case kUnitIdSlotSMul:
449 case kUnitIdSlotSBranch:
450 case kUnitIdSlotSAgen:
451 return kSlotAny;
452
453 case kUnitIdSlotD:
454 case kUnitIdSlotDAgen:
455 return kSlots;
456
457 default:
458 DEBUG_ASSERT(false, "unknown slot type!");
459 return kSlotNone;
460 }
461 }
462 } /* namespace maplebe */
463