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 "peep.h"
17 #include "cg.h"
18 #include "mpl_logging.h"
19 #include "common_utils.h"
20 #if TARGAARCH64
21 #include "aarch64_peep.h"
22 #endif
23 #if defined TARGX86_64
24 #include "x64_peep.h"
25 #endif
26
27 namespace maplebe {
28 #if TARGAARCH64
29 /* Check if a regOpnd is live after insn. True if live, otherwise false. */
IfOperandIsLiveAfterInsn(const RegOperand ®Opnd, Insn &insn)30 bool CGPeepPattern::IfOperandIsLiveAfterInsn(const RegOperand ®Opnd, Insn &insn)
31 {
32 for (Insn *nextInsn = insn.GetNext(); nextInsn != nullptr; nextInsn = nextInsn->GetNext()) {
33 if (!nextInsn->IsMachineInstruction()) {
34 continue;
35 }
36 CHECK_FATAL(nextInsn->GetOperandSize() > 0, "must not be zero");
37 int32 lastOpndId = static_cast<int32>(nextInsn->GetOperandSize() - 1);
38 for (int32 i = lastOpndId; i >= 0; --i) {
39 Operand &opnd = nextInsn->GetOperand(static_cast<uint32>(i));
40 if (opnd.IsMemoryAccessOperand()) {
41 auto &mem = static_cast<MemOperand &>(opnd);
42 Operand *base = mem.GetBaseRegister();
43 Operand *offset = mem.GetOffset();
44
45 if (base != nullptr && base->IsRegister()) {
46 auto *tmpRegOpnd = static_cast<RegOperand *>(base);
47 if (tmpRegOpnd->GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
48 return true;
49 }
50 }
51 if (offset != nullptr && offset->IsRegister()) {
52 auto *tmpRegOpnd = static_cast<RegOperand *>(offset);
53 if (tmpRegOpnd->GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
54 return true;
55 }
56 }
57 } else if (opnd.IsList()) {
58 auto &opndList = static_cast<ListOperand &>(opnd).GetOperands();
59 if (find(opndList.begin(), opndList.end(), ®Opnd) != opndList.end()) {
60 return true;
61 }
62 }
63
64 if (!opnd.IsRegister()) {
65 continue;
66 }
67 auto &tmpRegOpnd = static_cast<RegOperand &>(opnd);
68 if (opnd.IsRegister() && tmpRegOpnd.GetRegisterNumber() != regOpnd.GetRegisterNumber()) {
69 continue;
70 }
71 const InsnDesc *md = nextInsn->GetDesc();
72 auto *regProp = (md->opndMD[static_cast<uint32>(i)]);
73 bool isUse = regProp->IsUse();
74 /* if noUse Redefined, no need to check live-out. */
75 return isUse;
76 }
77 }
78 /* Check if it is live-out. */
79 return FindRegLiveOut(regOpnd, *insn.GetBB());
80 }
81
82 /* entrance for find if a regOpnd is live-out. */
FindRegLiveOut(const RegOperand ®Opnd, const BB &bb)83 bool CGPeepPattern::FindRegLiveOut(const RegOperand ®Opnd, const BB &bb)
84 {
85 /*
86 * Each time use peephole, index is initialized by the constructor,
87 * and the internal_flags3 should be cleared.
88 */
89 if (PeepOptimizer::index == 0) {
90 FOR_ALL_BB(currbb, cgFunc)
91 {
92 currbb->SetInternalFlag3(0);
93 }
94 }
95 /* before each invoke check function, increase index. */
96 ++PeepOptimizer::index;
97 return CheckOpndLiveinSuccs(regOpnd, bb);
98 }
99
100 /* Check regOpnd in succs/ehSuccs. True is live-out, otherwise false. */
CheckOpndLiveinSuccs(const RegOperand ®Opnd, const BB &bb) const101 bool CGPeepPattern::CheckOpndLiveinSuccs(const RegOperand ®Opnd, const BB &bb) const
102 {
103 std::stack<BB *> bbStack;
104 bbStack.push(const_cast<BB *>(&bb));
105 while (!bbStack.empty()) {
106 BB *currentBB = bbStack.top();
107 bbStack.pop();
108 if (CheckRegLiveinReturnBB(regOpnd, *currentBB)) {
109 return true;
110 }
111 // The traversal order of sibling nodes in the iterative version
112 // is reversed compared to the recursive version
113 for (auto succ : currentBB->GetSuccs()) {
114 DEBUG_ASSERT(succ->GetInternalFlag3() <= PeepOptimizer::index, "internal error.");
115 if (succ->GetInternalFlag3() == PeepOptimizer::index) {
116 continue;
117 }
118 succ->SetInternalFlag3(PeepOptimizer::index);
119 ReturnType result = IsOpndLiveinBB(regOpnd, *succ);
120 if (result == kResNotFind) {
121 bbStack.push(succ);
122 } else if (result == kResUseFirst) {
123 return true;
124 } else if (result == kResDefFirst) {
125 // Do nothing, continue to process successors
126 }
127 }
128 }
129 return false;
130 }
131
132 /* Check if the reg is used in return BB */
CheckRegLiveinReturnBB(const RegOperand ®Opnd, const BB &bb) const133 bool CGPeepPattern::CheckRegLiveinReturnBB(const RegOperand ®Opnd, const BB &bb) const
134 {
135 #if TARGAARCH64 || TARGRISCV64
136 if (bb.GetKind() == BB::kBBReturn) {
137 regno_t regNO = regOpnd.GetRegisterNumber();
138 RegType regType = regOpnd.GetRegisterType();
139 if (regType == kRegTyVary) {
140 return false;
141 }
142 PrimType returnType = cgFunc->GetFunction().GetReturnType()->GetPrimType();
143 regno_t returnReg = R0;
144 if (IsPrimitiveFloat(returnType)) {
145 returnReg = V0;
146 } else if (IsPrimitiveInteger(returnType)) {
147 returnReg = R0;
148 }
149 if (regNO == returnReg) {
150 return true;
151 }
152 }
153 #endif
154 return false;
155 }
156
157 /*
158 * Check regNO in current bb:
159 * kResUseFirst:first find use point; kResDefFirst:first find define point;
160 * kResNotFind:cannot find regNO, need to continue searching.
161 */
IsOpndLiveinBB(const RegOperand ®Opnd, const BB &bb) const162 ReturnType CGPeepPattern::IsOpndLiveinBB(const RegOperand ®Opnd, const BB &bb) const
163 {
164 FOR_BB_INSNS_CONST(insn, &bb)
165 {
166 if (!insn->IsMachineInstruction()) {
167 continue;
168 }
169 const InsnDesc *md = insn->GetDesc();
170 int32 lastOpndId = static_cast<int32>(insn->GetOperandSize() - 1);
171 for (int32 i = lastOpndId; i >= 0; --i) {
172 Operand &opnd = insn->GetOperand(static_cast<uint32>(i));
173 auto *regProp = (md->opndMD[static_cast<uint32>(i)]);
174 if (opnd.IsConditionCode()) {
175 if (regOpnd.GetRegisterNumber() == kRFLAG) {
176 bool isUse = regProp->IsUse();
177 if (isUse) {
178 return kResUseFirst;
179 }
180 DEBUG_ASSERT(regProp->IsDef(), "register should be redefined.");
181 return kResDefFirst;
182 }
183 } else if (opnd.IsList()) {
184 auto &listOpnd = static_cast<ListOperand &>(opnd);
185 if (insn->GetMachineOpcode() == MOP_asm) {
186 if (static_cast<uint32>(i) == kAsmOutputListOpnd || static_cast<uint32>(i) == kAsmClobberListOpnd) {
187 for (const auto op : listOpnd.GetOperands()) {
188 if (op->GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
189 return kResDefFirst;
190 }
191 }
192 continue;
193 } else if (static_cast<uint32>(i) != kAsmInputListOpnd) {
194 continue;
195 }
196 /* fall thru for kAsmInputListOpnd */
197 }
198 for (const auto op : listOpnd.GetOperands()) {
199 if (op->GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
200 return kResUseFirst;
201 }
202 }
203 } else if (opnd.IsMemoryAccessOperand()) {
204 auto &mem = static_cast<MemOperand &>(opnd);
205 Operand *base = mem.GetBaseRegister();
206 Operand *offset = mem.GetOffset();
207
208 if (base != nullptr) {
209 DEBUG_ASSERT(base->IsRegister(), "internal error.");
210 auto *tmpRegOpnd = static_cast<RegOperand *>(base);
211 if (tmpRegOpnd->GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
212 return kResUseFirst;
213 }
214 }
215 if (offset != nullptr && offset->IsRegister()) {
216 auto *tmpRegOpnd = static_cast<RegOperand *>(offset);
217 if (tmpRegOpnd->GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
218 return kResUseFirst;
219 }
220 }
221 } else if (opnd.IsRegister()) {
222 auto &tmpRegOpnd = static_cast<RegOperand &>(opnd);
223 if (tmpRegOpnd.GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
224 bool isUse = regProp->IsUse();
225 if (isUse) {
226 return kResUseFirst;
227 }
228 DEBUG_ASSERT(regProp->IsDef(), "register should be redefined.");
229 return kResDefFirst;
230 }
231 }
232 }
233 }
234 return kResNotFind;
235 }
236
LogValueAtBase2(int64 val) const237 int PeepPattern::LogValueAtBase2(int64 val) const
238 {
239 return (__builtin_popcountll(static_cast<uint64>(val)) == 1) ? (__builtin_ffsll(val) - 1) : (-1);
240 }
241
242 /* Check if a regOpnd is live after insn. True if live, otherwise false. */
IfOperandIsLiveAfterInsn(const RegOperand ®Opnd, Insn &insn)243 bool PeepPattern::IfOperandIsLiveAfterInsn(const RegOperand ®Opnd, Insn &insn)
244 {
245 for (Insn *nextInsn = insn.GetNext(); nextInsn != nullptr; nextInsn = nextInsn->GetNext()) {
246 if (!nextInsn->IsMachineInstruction()) {
247 continue;
248 }
249 CHECK_FATAL(nextInsn->GetOperandSize() > 0, "must not be zero");
250 int32 lastOpndId = static_cast<int32>(nextInsn->GetOperandSize() - 1);
251 for (int32 i = lastOpndId; i >= 0; --i) {
252 Operand &opnd = nextInsn->GetOperand(static_cast<uint32>(i));
253 if (opnd.IsMemoryAccessOperand()) {
254 auto &mem = static_cast<MemOperand &>(opnd);
255 Operand *base = mem.GetBaseRegister();
256 Operand *offset = mem.GetOffset();
257
258 if (base != nullptr && base->IsRegister()) {
259 auto *tmpRegOpnd = static_cast<RegOperand *>(base);
260 if (tmpRegOpnd->GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
261 return true;
262 }
263 }
264 if (offset != nullptr && offset->IsRegister()) {
265 auto *tmpRegOpnd = static_cast<RegOperand *>(offset);
266 if (tmpRegOpnd->GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
267 return true;
268 }
269 }
270 } else if (opnd.IsList()) {
271 auto &opndList = static_cast<ListOperand &>(opnd).GetOperands();
272 if (find(opndList.begin(), opndList.end(), ®Opnd) != opndList.end()) {
273 return true;
274 }
275 }
276
277 if (!opnd.IsRegister()) {
278 continue;
279 }
280 auto &tmpRegOpnd = static_cast<RegOperand &>(opnd);
281 if (opnd.IsRegister() && tmpRegOpnd.GetRegisterNumber() != regOpnd.GetRegisterNumber()) {
282 continue;
283 }
284 const InsnDesc *md = nextInsn->GetDesc();
285 auto *regProp = (md->opndMD[static_cast<uint64>(i)]);
286 bool isUse = regProp->IsUse();
287 /* if noUse Redefined, no need to check live-out. */
288 return isUse;
289 }
290 }
291 /* Check if it is live-out. */
292 return FindRegLiveOut(regOpnd, *insn.GetBB());
293 }
294
295 /* entrance for find if a regOpnd is live-out. */
FindRegLiveOut(const RegOperand ®Opnd, const BB &bb)296 bool PeepPattern::FindRegLiveOut(const RegOperand ®Opnd, const BB &bb)
297 {
298 /*
299 * Each time use peephole, index is initialized by the constructor,
300 * and the internal_flags3 should be cleared.
301 */
302 if (PeepOptimizer::index == 0) {
303 FOR_ALL_BB(currbb, &cgFunc)
304 {
305 currbb->SetInternalFlag3(0);
306 }
307 }
308 /* before each invoke check function, increase index. */
309 ++PeepOptimizer::index;
310 return CheckOpndLiveinSuccs(regOpnd, bb);
311 }
312
313 /* Check regOpnd in succs/ehSuccs. True is live-out, otherwise false. */
CheckOpndLiveinSuccs(const RegOperand ®Opnd, const BB &bb) const314 bool PeepPattern::CheckOpndLiveinSuccs(const RegOperand ®Opnd, const BB &bb) const
315 {
316 std::stack<BB *> bbStack;
317 bbStack.push(const_cast<BB *>(&bb));
318 while (!bbStack.empty()) {
319 BB *currentBB = bbStack.top();
320 bbStack.pop();
321 if (CheckRegLiveinReturnBB(regOpnd, *currentBB)) {
322 return true;
323 }
324 // The traversal order of sibling nodes in the iterative version
325 // is reversed compared to the recursive version
326 for (auto succ : currentBB->GetSuccs()) {
327 DEBUG_ASSERT(succ->GetInternalFlag3() <= PeepOptimizer::index, "internal error.");
328 if (succ->GetInternalFlag3() == PeepOptimizer::index) {
329 continue;
330 }
331 succ->SetInternalFlag3(PeepOptimizer::index);
332 ReturnType result = IsOpndLiveinBB(regOpnd, *succ);
333 if (result == kResNotFind) {
334 bbStack.push(succ);
335 } else if (result == kResUseFirst) {
336 return true;
337 } else if (result == kResDefFirst) {
338 // Do nothing, continue to process successors
339 }
340 }
341 }
342 return false;
343 }
344
345 /* Check if the reg is used in return BB */
CheckRegLiveinReturnBB(const RegOperand ®Opnd, const BB &bb) const346 bool PeepPattern::CheckRegLiveinReturnBB(const RegOperand ®Opnd, const BB &bb) const
347 {
348 #if TARGAARCH64 || TARGRISCV64
349 if (bb.GetKind() == BB::kBBReturn) {
350 regno_t regNO = regOpnd.GetRegisterNumber();
351 RegType regType = regOpnd.GetRegisterType();
352 if (regType == kRegTyVary) {
353 return false;
354 }
355 PrimType returnType = cgFunc.GetFunction().GetReturnType()->GetPrimType();
356 regno_t returnReg = R0;
357 if (IsPrimitiveFloat(returnType)) {
358 returnReg = V0;
359 } else if (IsPrimitiveInteger(returnType)) {
360 returnReg = R0;
361 }
362 if (regNO == returnReg) {
363 return true;
364 }
365 }
366 #endif
367 return false;
368 }
369
370 /*
371 * Check regNO in current bb:
372 * kResUseFirst:first find use point; kResDefFirst:first find define point;
373 * kResNotFind:cannot find regNO, need to continue searching.
374 */
IsOpndLiveinBB(const RegOperand ®Opnd, const BB &bb) const375 ReturnType PeepPattern::IsOpndLiveinBB(const RegOperand ®Opnd, const BB &bb) const
376 {
377 FOR_BB_INSNS_CONST(insn, &bb)
378 {
379 if (!insn->IsMachineInstruction()) {
380 continue;
381 }
382 const InsnDesc *md = insn->GetDesc();
383 int32 lastOpndId = static_cast<int32>(insn->GetOperandSize() - 1);
384 for (int32 i = lastOpndId; i >= 0; --i) {
385 Operand &opnd = insn->GetOperand(static_cast<uint32>(i));
386 auto *regProp = (md->opndMD[static_cast<uint32>(i)]);
387 if (opnd.IsConditionCode()) {
388 if (regOpnd.GetRegisterNumber() == kRFLAG) {
389 bool isUse = regProp->IsUse();
390 if (isUse) {
391 return kResUseFirst;
392 }
393 DEBUG_ASSERT(regProp->IsDef(), "register should be redefined.");
394 return kResDefFirst;
395 }
396 } else if (opnd.IsList()) {
397 auto &listOpnd = static_cast<ListOperand &>(opnd);
398 if (insn->GetMachineOpcode() == MOP_asm) {
399 if (static_cast<uint32>(i) == kAsmOutputListOpnd || static_cast<uint32>(i) == kAsmClobberListOpnd) {
400 for (const auto op : listOpnd.GetOperands()) {
401 if (op->GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
402 return kResDefFirst;
403 }
404 }
405 continue;
406 } else if (static_cast<uint32>(i) != kAsmInputListOpnd) {
407 continue;
408 }
409 /* fall thru for kAsmInputListOpnd */
410 }
411 for (const auto op : listOpnd.GetOperands()) {
412 if (op->GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
413 return kResUseFirst;
414 }
415 }
416 } else if (opnd.IsMemoryAccessOperand()) {
417 auto &mem = static_cast<MemOperand &>(opnd);
418 Operand *base = mem.GetBaseRegister();
419 Operand *offset = mem.GetOffset();
420
421 if (base != nullptr) {
422 DEBUG_ASSERT(base->IsRegister(), "internal error.");
423 auto *tmpRegOpnd = static_cast<RegOperand *>(base);
424 if (tmpRegOpnd->GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
425 return kResUseFirst;
426 }
427 }
428 if (offset != nullptr && offset->IsRegister()) {
429 auto *tmpRegOpnd = static_cast<RegOperand *>(offset);
430 if (tmpRegOpnd->GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
431 return kResUseFirst;
432 }
433 }
434 } else if (opnd.IsRegister()) {
435 auto &tmpRegOpnd = static_cast<RegOperand &>(opnd);
436 if (tmpRegOpnd.GetRegisterNumber() == regOpnd.GetRegisterNumber()) {
437 bool isUse = regProp->IsUse();
438 if (isUse) {
439 return kResUseFirst;
440 }
441 DEBUG_ASSERT(regProp->IsDef(), "register should be redefined.");
442 return kResDefFirst;
443 }
444 }
445 }
446 }
447 return kResNotFind;
448 }
449
IsMemOperandOptPattern(const Insn &insn, Insn &nextInsn)450 bool PeepPattern::IsMemOperandOptPattern(const Insn &insn, Insn &nextInsn)
451 {
452 /* Check if base register of nextInsn and the dest operand of insn are identical. */
453 auto *memOpnd = static_cast<MemOperand *>(nextInsn.GetMemOpnd());
454 DEBUG_ASSERT(memOpnd != nullptr, "null ptr check");
455 /* Only for AddrMode_B_OI addressing mode. */
456 if (memOpnd->GetAddrMode() != MemOperand::kAddrModeBOi) {
457 return false;
458 }
459 /* Only for immediate is 0. */
460 if (memOpnd->GetOffsetImmediate()->GetOffsetValue() != 0) {
461 return false;
462 }
463 /* Only for intact memory addressing. */
464 if (!memOpnd->IsIntactIndexed()) {
465 return false;
466 }
467
468 auto &oldBaseOpnd = static_cast<RegOperand &>(insn.GetOperand(kInsnFirstOpnd));
469 /* Check if dest operand of insn is idential with base register of nextInsn. */
470 if (memOpnd->GetBaseRegister() != &oldBaseOpnd) {
471 return false;
472 }
473
474 #ifdef USE_32BIT_REF
475 if (nextInsn.IsAccessRefField() && nextInsn.GetOperand(kInsnFirstOpnd).GetSize() > k32BitSize) {
476 return false;
477 }
478 #endif
479 /* Check if x0 is used after ldr insn, and if it is in live-out. */
480 if (IfOperandIsLiveAfterInsn(oldBaseOpnd, nextInsn)) {
481 return false;
482 }
483 return true;
484 }
485
486 template <typename T>
Run()487 void PeepOptimizer::Run()
488 {
489 auto *patterMatcher = peepOptMemPool->New<T>(cgFunc, peepOptMemPool);
490 patterMatcher->InitOpts();
491 FOR_ALL_BB(bb, &cgFunc)
492 {
493 FOR_BB_INSNS_SAFE(insn, bb, nextInsn)
494 {
495 if (!insn->IsMachineInstruction()) {
496 continue;
497 }
498 patterMatcher->Run(*bb, *insn);
499 }
500 }
501 }
502
503 int32 PeepOptimizer::index = 0;
504
Peephole0()505 void PeepHoleOptimizer::Peephole0()
506 {
507 auto memPool = std::make_unique<ThreadLocalMemPool>(memPoolCtrler, "peepholeOptObj");
508 PeepOptimizer peepOptimizer(*cgFunc, memPool.get());
509 #if TARGAARCH64 || TARGRISCV64
510 peepOptimizer.Run<AArch64PeepHole0>();
511 #endif
512 }
513
PeepholeOpt()514 void PeepHoleOptimizer::PeepholeOpt()
515 {
516 auto memPool = std::make_unique<ThreadLocalMemPool>(memPoolCtrler, "peepholeOptObj");
517 PeepOptimizer peepOptimizer(*cgFunc, memPool.get());
518 #if TARGAARCH64 || TARGRISCV64
519 peepOptimizer.Run<AArch64PeepHole>();
520 #endif
521 }
522 #endif
523
524 /* === Physical Post Form === */
PhaseRun(maplebe::CGFunc &f)525 bool CgPostPeepHole::PhaseRun(maplebe::CGFunc &f)
526 {
527 MemPool *mp = GetPhaseMemPool();
528 CGPeepHole *cgpeep = f.GetCG()->CreateCGPeepHole(*mp, f);
529 CHECK_FATAL(cgpeep != nullptr, "PeepHoleOptimizer instance create failure");
530 cgpeep->Run();
531 return false;
532 }
533 MAPLE_TRANSFORM_PHASE_REGISTER_CANSKIP(CgPostPeepHole, cgpostpeephole)
534
535 #if TARGAARCH64
PhaseRun(maplebe::CGFunc &f)536 bool CgPeepHole0::PhaseRun(maplebe::CGFunc &f)
537 {
538 auto *peep = GetPhaseMemPool()->New<PeepHoleOptimizer>(&f);
539 CHECK_FATAL(peep != nullptr, "PeepHoleOptimizer instance create failure");
540 peep->Peephole0();
541 return false;
542 }
543 MAPLE_TRANSFORM_PHASE_REGISTER_CANSKIP(CgPeepHole0, peephole0)
544
PhaseRun(maplebe::CGFunc &f)545 bool CgPeepHole1::PhaseRun(maplebe::CGFunc &f)
546 {
547 auto *peep = GetPhaseMemPool()->New<PeepHoleOptimizer>(&f);
548 CHECK_FATAL(peep != nullptr, "PeepHoleOptimizer instance create failure");
549 peep->PeepholeOpt();
550 return false;
551 }
552 MAPLE_TRANSFORM_PHASE_REGISTER_CANSKIP(CgPeepHole1, peephole)
553 #endif
554
555 } /* namespace maplebe */
556