LLVM 18.0.0git
HexagonOptAddrMode.cpp
Go to the documentation of this file.
1//===- HexagonOptAddrMode.cpp ---------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8// This implements a Hexagon-specific pass to optimize addressing mode for
9// load/store instructions.
10//===----------------------------------------------------------------------===//
11
12#include "HexagonInstrInfo.h"
13#include "HexagonSubtarget.h"
15#include "llvm/ADT/DenseMap.h"
16#include "llvm/ADT/DenseSet.h"
17#include "llvm/ADT/StringRef.h"
32#include "llvm/MC/MCInstrDesc.h"
33#include "llvm/Pass.h"
35#include "llvm/Support/Debug.h"
38#include <cassert>
39#include <cstdint>
40
41#define DEBUG_TYPE "opt-addr-mode"
42
43using namespace llvm;
44using namespace rdf;
45
46static cl::opt<int> CodeGrowthLimit("hexagon-amode-growth-limit",
47 cl::Hidden, cl::init(0), cl::desc("Code growth limit for address mode "
48 "optimization"));
49
50namespace llvm {
51
54
55} // end namespace llvm
56
57namespace {
58
59class HexagonOptAddrMode : public MachineFunctionPass {
60public:
61 static char ID;
62
63 HexagonOptAddrMode() : MachineFunctionPass(ID) {}
64
65 StringRef getPassName() const override {
66 return "Optimize addressing mode of load/store";
67 }
68
69 void getAnalysisUsage(AnalysisUsage &AU) const override {
73 AU.setPreservesAll();
74 }
75
76 bool runOnMachineFunction(MachineFunction &MF) override;
77
78private:
79 using MISetType = DenseSet<MachineInstr *>;
80 using InstrEvalMap = DenseMap<MachineInstr *, bool>;
81
82 MachineRegisterInfo *MRI = nullptr;
83 const HexagonInstrInfo *HII = nullptr;
84 const HexagonRegisterInfo *HRI = nullptr;
85 MachineDominatorTree *MDT = nullptr;
86 DataFlowGraph *DFG = nullptr;
88 Liveness *LV = nullptr;
89 MISetType Deleted;
90
91 bool processBlock(NodeAddr<BlockNode *> BA);
92 bool xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
93 NodeAddr<UseNode *> UseN, unsigned UseMOnum);
94 bool processAddUses(NodeAddr<StmtNode *> AddSN, MachineInstr *AddMI,
95 const NodeList &UNodeList);
96 bool updateAddUses(MachineInstr *AddMI, MachineInstr *UseMI);
97 bool analyzeUses(unsigned DefR, const NodeList &UNodeList,
98 InstrEvalMap &InstrEvalResult, short &SizeInc);
99 bool hasRepForm(MachineInstr &MI, unsigned TfrDefR);
100 bool canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN, MachineInstr &MI,
101 const NodeList &UNodeList);
102 bool isSafeToExtLR(NodeAddr<StmtNode *> SN, MachineInstr *MI,
103 unsigned LRExtReg, const NodeList &UNodeList);
104 void getAllRealUses(NodeAddr<StmtNode *> SN, NodeList &UNodeList);
105 bool allValidCandidates(NodeAddr<StmtNode *> SA, NodeList &UNodeList);
106 short getBaseWithLongOffset(const MachineInstr &MI) const;
107 bool changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
108 unsigned ImmOpNum);
109 bool changeLoad(MachineInstr *OldMI, MachineOperand ImmOp, unsigned ImmOpNum);
110 bool changeAddAsl(NodeAddr<UseNode *> AddAslUN, MachineInstr *AddAslMI,
111 const MachineOperand &ImmOp, unsigned ImmOpNum);
112 bool isValidOffset(MachineInstr *MI, int Offset);
113 unsigned getBaseOpPosition(MachineInstr *MI);
114 unsigned getOffsetOpPosition(MachineInstr *MI);
115};
116
117} // end anonymous namespace
118
119char HexagonOptAddrMode::ID = 0;
120
121INITIALIZE_PASS_BEGIN(HexagonOptAddrMode, "amode-opt",
122 "Optimize addressing mode", false, false)
125INITIALIZE_PASS_END(HexagonOptAddrMode, "amode-opt", "Optimize addressing mode",
127
128bool HexagonOptAddrMode::hasRepForm(MachineInstr &MI, unsigned TfrDefR) {
129 const MCInstrDesc &MID = MI.getDesc();
130
131 if ((!MID.mayStore() && !MID.mayLoad()) || HII->isPredicated(MI))
132 return false;
133
134 if (MID.mayStore()) {
135 MachineOperand StOp = MI.getOperand(MI.getNumOperands() - 1);
136 if (StOp.isReg() && StOp.getReg() == TfrDefR)
137 return false;
138 }
139
140 if (HII->getAddrMode(MI) == HexagonII::BaseRegOffset)
141 // Tranform to Absolute plus register offset.
142 return (HII->changeAddrMode_rr_ur(MI) >= 0);
143 else if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset)
144 // Tranform to absolute addressing mode.
145 return (HII->changeAddrMode_io_abs(MI) >= 0);
146
147 return false;
148}
149
150// Check if addasl instruction can be removed. This is possible only
151// if it's feeding to only load/store instructions with base + register
152// offset as these instruction can be tranformed to use 'absolute plus
153// shifted register offset'.
154// ex:
155// Rs = ##foo
156// Rx = addasl(Rs, Rt, #2)
157// Rd = memw(Rx + #28)
158// Above three instructions can be replaced with Rd = memw(Rt<<#2 + ##foo+28)
159
160bool HexagonOptAddrMode::canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN,
162 const NodeList &UNodeList) {
163 // check offset size in addasl. if 'offset > 3' return false
164 const MachineOperand &OffsetOp = MI.getOperand(3);
165 if (!OffsetOp.isImm() || OffsetOp.getImm() > 3)
166 return false;
167
168 Register OffsetReg = MI.getOperand(2).getReg();
169 RegisterRef OffsetRR;
170 NodeId OffsetRegRD = 0;
171 for (NodeAddr<UseNode *> UA : AddAslSN.Addr->members_if(DFG->IsUse, *DFG)) {
172 RegisterRef RR = UA.Addr->getRegRef(*DFG);
173 if (OffsetReg == RR.Reg) {
174 OffsetRR = RR;
175 OffsetRegRD = UA.Addr->getReachingDef();
176 }
177 }
178
179 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
181 NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
182 if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
183 return false;
184 NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(OffsetRR, IA);
185 if ((DFG->IsDef(AA) && AA.Id != OffsetRegRD) ||
186 AA.Addr->getReachingDef() != OffsetRegRD)
187 return false;
188
189 MachineInstr &UseMI = *NodeAddr<StmtNode *>(IA).Addr->getCode();
190 NodeAddr<DefNode *> OffsetRegDN = DFG->addr<DefNode *>(OffsetRegRD);
191 // Reaching Def to an offset register can't be a phi.
192 if ((OffsetRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
193 MI.getParent() != UseMI.getParent())
194 return false;
195
196 const MCInstrDesc &UseMID = UseMI.getDesc();
197 if ((!UseMID.mayLoad() && !UseMID.mayStore()) ||
198 HII->getAddrMode(UseMI) != HexagonII::BaseImmOffset ||
199 getBaseWithLongOffset(UseMI) < 0)
200 return false;
201
202 // Addasl output can't be a store value.
203 if (UseMID.mayStore() && UseMI.getOperand(2).isReg() &&
204 UseMI.getOperand(2).getReg() == MI.getOperand(0).getReg())
205 return false;
206
207 for (auto &Mo : UseMI.operands())
208 if (Mo.isFI())
209 return false;
210 }
211 return true;
212}
213
214bool HexagonOptAddrMode::allValidCandidates(NodeAddr<StmtNode *> SA,
215 NodeList &UNodeList) {
216 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
218 RegisterRef UR = UN.Addr->getRegRef(*DFG);
219 NodeSet Visited, Defs;
220 const auto &P = LV->getAllReachingDefsRec(UR, UN, Visited, Defs);
221 if (!P.second) {
222 LLVM_DEBUG({
223 dbgs() << "*** Unable to collect all reaching defs for use ***\n"
224 << PrintNode<UseNode*>(UN, *DFG) << '\n'
225 << "The program's complexity may exceed the limits.\n";
226 });
227 return false;
228 }
229 const auto &ReachingDefs = P.first;
230 if (ReachingDefs.size() > 1) {
231 LLVM_DEBUG({
232 dbgs() << "*** Multiple Reaching Defs found!!! ***\n";
233 for (auto DI : ReachingDefs) {
234 NodeAddr<UseNode *> DA = DFG->addr<UseNode *>(DI);
235 NodeAddr<StmtNode *> TempIA = DA.Addr->getOwner(*DFG);
236 dbgs() << "\t\t[Reaching Def]: "
237 << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
238 }
239 });
240 return false;
241 }
242 }
243 return true;
244}
245
246void HexagonOptAddrMode::getAllRealUses(NodeAddr<StmtNode *> SA,
247 NodeList &UNodeList) {
248 for (NodeAddr<DefNode *> DA : SA.Addr->members_if(DFG->IsDef, *DFG)) {
249 LLVM_DEBUG(dbgs() << "\t\t[DefNode]: "
250 << Print<NodeAddr<DefNode *>>(DA, *DFG) << "\n");
251 RegisterRef DR = DA.Addr->getRegRef(*DFG);
252
253 auto UseSet = LV->getAllReachedUses(DR, DA);
254
255 for (auto UI : UseSet) {
256 NodeAddr<UseNode *> UA = DFG->addr<UseNode *>(UI);
257 LLVM_DEBUG({
258 NodeAddr<StmtNode *> TempIA = UA.Addr->getOwner(*DFG);
259 dbgs() << "\t\t\t[Reached Use]: "
260 << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
261 });
262
263 if (UA.Addr->getFlags() & NodeAttrs::PhiRef) {
264 NodeAddr<PhiNode *> PA = UA.Addr->getOwner(*DFG);
265 NodeId id = PA.Id;
266 const Liveness::RefMap &phiUse = LV->getRealUses(id);
267 LLVM_DEBUG(dbgs() << "\t\t\t\tphi real Uses"
268 << Print<Liveness::RefMap>(phiUse, *DFG) << "\n");
269 if (!phiUse.empty()) {
270 for (auto I : phiUse) {
271 if (!DFG->getPRI().alias(RegisterRef(I.first), DR))
272 continue;
273 auto phiUseSet = I.second;
274 for (auto phiUI : phiUseSet) {
275 NodeAddr<UseNode *> phiUA = DFG->addr<UseNode *>(phiUI.first);
276 UNodeList.push_back(phiUA);
277 }
278 }
279 }
280 } else
281 UNodeList.push_back(UA);
282 }
283 }
284}
285
286bool HexagonOptAddrMode::isSafeToExtLR(NodeAddr<StmtNode *> SN,
287 MachineInstr *MI, unsigned LRExtReg,
288 const NodeList &UNodeList) {
289 RegisterRef LRExtRR;
290 NodeId LRExtRegRD = 0;
291 // Iterate through all the UseNodes in SN and find the reaching def
292 // for the LRExtReg.
293 for (NodeAddr<UseNode *> UA : SN.Addr->members_if(DFG->IsUse, *DFG)) {
294 RegisterRef RR = UA.Addr->getRegRef(*DFG);
295 if (LRExtReg == RR.Reg) {
296 LRExtRR = RR;
297 LRExtRegRD = UA.Addr->getReachingDef();
298 }
299 }
300
301 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
303 NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
304 // The reaching def of LRExtRR at load/store node should be same as the
305 // one reaching at the SN.
306 if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
307 return false;
308 NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(LRExtRR, IA);
309 if ((DFG->IsDef(AA) && AA.Id != LRExtRegRD) ||
310 AA.Addr->getReachingDef() != LRExtRegRD) {
312 dbgs() << "isSafeToExtLR: Returning false; another reaching def\n");
313 return false;
314 }
315
316 // If the register is undefined (for example if it's a reserved register),
317 // it may still be possible to extend the range, but it's safer to be
318 // conservative and just punt.
319 if (LRExtRegRD == 0)
320 return false;
321
323 NodeAddr<DefNode *> LRExtRegDN = DFG->addr<DefNode *>(LRExtRegRD);
324 // Reaching Def to LRExtReg can't be a phi.
325 if ((LRExtRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
326 MI->getParent() != UseMI->getParent())
327 return false;
328 }
329 return true;
330}
331
332bool HexagonOptAddrMode::isValidOffset(MachineInstr *MI, int Offset) {
333 if (HII->isHVXVec(*MI)) {
334 // only HVX vgather instructions handled
335 // TODO: extend the pass to other vector load/store operations
336 switch (MI->getOpcode()) {
337 case Hexagon::V6_vgathermh_pseudo:
338 case Hexagon::V6_vgathermw_pseudo:
339 case Hexagon::V6_vgathermhw_pseudo:
340 case Hexagon::V6_vgathermhq_pseudo:
341 case Hexagon::V6_vgathermwq_pseudo:
342 case Hexagon::V6_vgathermhwq_pseudo:
343 return HII->isValidOffset(MI->getOpcode(), Offset, HRI, false);
344 default:
345 return false;
346 }
347 }
348
349 if (HII->getAddrMode(*MI) != HexagonII::BaseImmOffset)
350 return false;
351
352 unsigned AlignMask = 0;
353 switch (HII->getMemAccessSize(*MI)) {
354 case HexagonII::MemAccessSize::DoubleWordAccess:
355 AlignMask = 0x7;
356 break;
357 case HexagonII::MemAccessSize::WordAccess:
358 AlignMask = 0x3;
359 break;
360 case HexagonII::MemAccessSize::HalfWordAccess:
361 AlignMask = 0x1;
362 break;
363 case HexagonII::MemAccessSize::ByteAccess:
364 AlignMask = 0x0;
365 break;
366 default:
367 return false;
368 }
369
370 if ((AlignMask & Offset) != 0)
371 return false;
372 return HII->isValidOffset(MI->getOpcode(), Offset, HRI, false);
373}
374
375unsigned HexagonOptAddrMode::getBaseOpPosition(MachineInstr *MI) {
376 const MCInstrDesc &MID = MI->getDesc();
377 switch (MI->getOpcode()) {
378 // vgather pseudos are mayLoad and mayStore
379 // hence need to explicitly specify Base and
380 // Offset operand positions
381 case Hexagon::V6_vgathermh_pseudo:
382 case Hexagon::V6_vgathermw_pseudo:
383 case Hexagon::V6_vgathermhw_pseudo:
384 case Hexagon::V6_vgathermhq_pseudo:
385 case Hexagon::V6_vgathermwq_pseudo:
386 case Hexagon::V6_vgathermhwq_pseudo:
387 return 0;
388 default:
389 return MID.mayLoad() ? 1 : 0;
390 }
391}
392
393unsigned HexagonOptAddrMode::getOffsetOpPosition(MachineInstr *MI) {
394 assert(
395 (HII->getAddrMode(*MI) == HexagonII::BaseImmOffset) &&
396 "Looking for an offset in non-BaseImmOffset addressing mode instruction");
397
398 const MCInstrDesc &MID = MI->getDesc();
399 switch (MI->getOpcode()) {
400 // vgather pseudos are mayLoad and mayStore
401 // hence need to explicitly specify Base and
402 // Offset operand positions
403 case Hexagon::V6_vgathermh_pseudo:
404 case Hexagon::V6_vgathermw_pseudo:
405 case Hexagon::V6_vgathermhw_pseudo:
406 case Hexagon::V6_vgathermhq_pseudo:
407 case Hexagon::V6_vgathermwq_pseudo:
408 case Hexagon::V6_vgathermhwq_pseudo:
409 return 1;
410 default:
411 return MID.mayLoad() ? 2 : 1;
412 }
413}
414
415bool HexagonOptAddrMode::processAddUses(NodeAddr<StmtNode *> AddSN,
416 MachineInstr *AddMI,
417 const NodeList &UNodeList) {
418
419 Register AddDefR = AddMI->getOperand(0).getReg();
420 Register BaseReg = AddMI->getOperand(1).getReg();
421 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
423 NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
424 MachineInstr *MI = SN.Addr->getCode();
425 const MCInstrDesc &MID = MI->getDesc();
426 if ((!MID.mayLoad() && !MID.mayStore()) ||
427 HII->getAddrMode(*MI) != HexagonII::BaseImmOffset)
428 return false;
429
430 MachineOperand BaseOp = MI->getOperand(getBaseOpPosition(MI));
431
432 if (!BaseOp.isReg() || BaseOp.getReg() != AddDefR)
433 return false;
434
435 MachineOperand OffsetOp = MI->getOperand(getOffsetOpPosition(MI));
436 if (!OffsetOp.isImm())
437 return false;
438
439 int64_t newOffset = OffsetOp.getImm() + AddMI->getOperand(2).getImm();
440 if (!isValidOffset(MI, newOffset))
441 return false;
442
443 // Since we'll be extending the live range of Rt in the following example,
444 // make sure that is safe. another definition of Rt doesn't exist between 'add'
445 // and load/store instruction.
446 //
447 // Ex: Rx= add(Rt,#10)
448 // memw(Rx+#0) = Rs
449 // will be replaced with => memw(Rt+#10) = Rs
450 if (!isSafeToExtLR(AddSN, AddMI, BaseReg, UNodeList))
451 return false;
452 }
453
454 NodeId LRExtRegRD = 0;
455 // Iterate through all the UseNodes in SN and find the reaching def
456 // for the LRExtReg.
457 for (NodeAddr<UseNode *> UA : AddSN.Addr->members_if(DFG->IsUse, *DFG)) {
458 RegisterRef RR = UA.Addr->getRegRef(*DFG);
459 if (BaseReg == RR.Reg)
460 LRExtRegRD = UA.Addr->getReachingDef();
461 }
462
463 // Update all the uses of 'add' with the appropriate base and offset
464 // values.
465 bool Changed = false;
466 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
467 NodeAddr<UseNode *> UseN = *I;
468 assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
469 "Found a PhiRef node as a real reached use!!");
470
471 NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
472 MachineInstr *UseMI = OwnerN.Addr->getCode();
473 LLVM_DEBUG(dbgs() << "\t\t[MI <BB#" << UseMI->getParent()->getNumber()
474 << ">]: " << *UseMI << "\n");
475 Changed |= updateAddUses(AddMI, UseMI);
476
477 // Set the reachingDef for UseNode under consideration
478 // after updating the Add use. This local change is
479 // to avoid rebuilding of the RDF graph after update.
480 NodeAddr<DefNode *> LRExtRegDN = DFG->addr<DefNode *>(LRExtRegRD);
481 UseN.Addr->linkToDef(UseN.Id, LRExtRegDN);
482 }
483
484 if (Changed)
485 Deleted.insert(AddMI);
486
487 return Changed;
488}
489
490bool HexagonOptAddrMode::updateAddUses(MachineInstr *AddMI,
492 const MachineOperand ImmOp = AddMI->getOperand(2);
493 const MachineOperand AddRegOp = AddMI->getOperand(1);
494 Register NewReg = AddRegOp.getReg();
495
496 MachineOperand &BaseOp = UseMI->getOperand(getBaseOpPosition(UseMI));
497 MachineOperand &OffsetOp = UseMI->getOperand(getOffsetOpPosition(UseMI));
498 BaseOp.setReg(NewReg);
499 BaseOp.setIsUndef(AddRegOp.isUndef());
500 BaseOp.setImplicit(AddRegOp.isImplicit());
501 OffsetOp.setImm(ImmOp.getImm() + OffsetOp.getImm());
502 MRI->clearKillFlags(NewReg);
503
504 return true;
505}
506
507bool HexagonOptAddrMode::analyzeUses(unsigned tfrDefR,
508 const NodeList &UNodeList,
509 InstrEvalMap &InstrEvalResult,
510 short &SizeInc) {
511 bool KeepTfr = false;
512 bool HasRepInstr = false;
513 InstrEvalResult.clear();
514
515 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
516 bool CanBeReplaced = false;
518 NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
519 MachineInstr &MI = *SN.Addr->getCode();
520 const MCInstrDesc &MID = MI.getDesc();
521 if ((MID.mayLoad() || MID.mayStore())) {
522 if (!hasRepForm(MI, tfrDefR)) {
523 KeepTfr = true;
524 continue;
525 }
526 SizeInc++;
527 CanBeReplaced = true;
528 } else if (MI.getOpcode() == Hexagon::S2_addasl_rrri) {
529 NodeList AddaslUseList;
530
531 LLVM_DEBUG(dbgs() << "\nGetting ReachedUses for === " << MI << "\n");
532 getAllRealUses(SN, AddaslUseList);
533 // Process phi nodes.
534 if (allValidCandidates(SN, AddaslUseList) &&
535 canRemoveAddasl(SN, MI, AddaslUseList)) {
536 SizeInc += AddaslUseList.size();
537 SizeInc -= 1; // Reduce size by 1 as addasl itself can be removed.
538 CanBeReplaced = true;
539 } else
540 SizeInc++;
541 } else
542 // Currently, only load/store and addasl are handled.
543 // Some other instructions to consider -
544 // A2_add -> A2_addi
545 // M4_mpyrr_addr -> M4_mpyrr_addi
546 KeepTfr = true;
547
548 InstrEvalResult[&MI] = CanBeReplaced;
549 HasRepInstr |= CanBeReplaced;
550 }
551
552 // Reduce total size by 2 if original tfr can be deleted.
553 if (!KeepTfr)
554 SizeInc -= 2;
555
556 return HasRepInstr;
557}
558
559bool HexagonOptAddrMode::changeLoad(MachineInstr *OldMI, MachineOperand ImmOp,
560 unsigned ImmOpNum) {
561 bool Changed = false;
562 MachineBasicBlock *BB = OldMI->getParent();
563 auto UsePos = MachineBasicBlock::iterator(OldMI);
564 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
565 ++InsertPt;
566 unsigned OpStart;
567 unsigned OpEnd = OldMI->getNumOperands();
569
570 if (ImmOpNum == 1) {
571 if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
572 short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
573 assert(NewOpCode >= 0 && "Invalid New opcode\n");
574 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
575 MIB.add(OldMI->getOperand(0));
576 MIB.add(OldMI->getOperand(2));
577 MIB.add(OldMI->getOperand(3));
578 MIB.add(ImmOp);
579 OpStart = 4;
580 Changed = true;
581 } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset &&
582 OldMI->getOperand(2).isImm()) {
583 short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
584 assert(NewOpCode >= 0 && "Invalid New opcode\n");
585 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode))
586 .add(OldMI->getOperand(0));
587 const GlobalValue *GV = ImmOp.getGlobal();
588 int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(2).getImm();
589
590 MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
591 OpStart = 3;
592 Changed = true;
593 } else
594 Changed = false;
595
596 LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
597 LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
598 } else if (ImmOpNum == 2) {
599 if (OldMI->getOperand(3).isImm() && OldMI->getOperand(3).getImm() == 0) {
600 short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
601 assert(NewOpCode >= 0 && "Invalid New opcode\n");
602 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
603 MIB.add(OldMI->getOperand(0));
604 MIB.add(OldMI->getOperand(1));
605 MIB.add(ImmOp);
606 OpStart = 4;
607 Changed = true;
608 LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
609 LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
610 }
611 }
612
613 if (Changed)
614 for (unsigned i = OpStart; i < OpEnd; ++i)
615 MIB.add(OldMI->getOperand(i));
616
617 return Changed;
618}
619
620bool HexagonOptAddrMode::changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
621 unsigned ImmOpNum) {
622 bool Changed = false;
623 unsigned OpStart = 0;
624 unsigned OpEnd = OldMI->getNumOperands();
625 MachineBasicBlock *BB = OldMI->getParent();
626 auto UsePos = MachineBasicBlock::iterator(OldMI);
627 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
628 ++InsertPt;
630 if (ImmOpNum == 0) {
631 if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
632 short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
633 assert(NewOpCode >= 0 && "Invalid New opcode\n");
634 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
635 MIB.add(OldMI->getOperand(1));
636 MIB.add(OldMI->getOperand(2));
637 MIB.add(ImmOp);
638 MIB.add(OldMI->getOperand(3));
639 OpStart = 4;
640 Changed = true;
641 } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset) {
642 short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
643 assert(NewOpCode >= 0 && "Invalid New opcode\n");
644 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
645 const GlobalValue *GV = ImmOp.getGlobal();
646 int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(1).getImm();
647 MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
648 MIB.add(OldMI->getOperand(2));
649 OpStart = 3;
650 Changed = true;
651 }
652 } else if (ImmOpNum == 1 && OldMI->getOperand(2).getImm() == 0) {
653 short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
654 assert(NewOpCode >= 0 && "Invalid New opcode\n");
655 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
656 MIB.add(OldMI->getOperand(0));
657 MIB.add(ImmOp);
658 OpStart = 3;
659 Changed = true;
660 }
661 if (Changed) {
662 LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
663 LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
664
665 for (unsigned i = OpStart; i < OpEnd; ++i)
666 MIB.add(OldMI->getOperand(i));
667 }
668
669 return Changed;
670}
671
672short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr &MI) const {
673 if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset) {
674 short TempOpCode = HII->changeAddrMode_io_rr(MI);
675 return HII->changeAddrMode_rr_ur(TempOpCode);
676 }
677 return HII->changeAddrMode_rr_ur(MI);
678}
679
680bool HexagonOptAddrMode::changeAddAsl(NodeAddr<UseNode *> AddAslUN,
681 MachineInstr *AddAslMI,
682 const MachineOperand &ImmOp,
683 unsigned ImmOpNum) {
684 NodeAddr<StmtNode *> SA = AddAslUN.Addr->getOwner(*DFG);
685
686 LLVM_DEBUG(dbgs() << "Processing addasl :" << *AddAslMI << "\n");
687
688 NodeList UNodeList;
689 getAllRealUses(SA, UNodeList);
690
691 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
692 NodeAddr<UseNode *> UseUN = *I;
693 assert(!(UseUN.Addr->getFlags() & NodeAttrs::PhiRef) &&
694 "Can't transform this 'AddAsl' instruction!");
695
696 NodeAddr<StmtNode *> UseIA = UseUN.Addr->getOwner(*DFG);
697 LLVM_DEBUG(dbgs() << "[InstrNode]: "
698 << Print<NodeAddr<InstrNode *>>(UseIA, *DFG) << "\n");
699 MachineInstr *UseMI = UseIA.Addr->getCode();
700 LLVM_DEBUG(dbgs() << "[MI <" << printMBBReference(*UseMI->getParent())
701 << ">]: " << *UseMI << "\n");
702 const MCInstrDesc &UseMID = UseMI->getDesc();
703 assert(HII->getAddrMode(*UseMI) == HexagonII::BaseImmOffset);
704
705 auto UsePos = MachineBasicBlock::iterator(UseMI);
706 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
707 short NewOpCode = getBaseWithLongOffset(*UseMI);
708 assert(NewOpCode >= 0 && "Invalid New opcode\n");
709
710 unsigned OpStart;
711 unsigned OpEnd = UseMI->getNumOperands();
712
715 BuildMI(*BB, InsertPt, UseMI->getDebugLoc(), HII->get(NewOpCode));
716 // change mem(Rs + # ) -> mem(Rt << # + ##)
717 if (UseMID.mayLoad()) {
718 MIB.add(UseMI->getOperand(0));
719 MIB.add(AddAslMI->getOperand(2));
720 MIB.add(AddAslMI->getOperand(3));
721 const GlobalValue *GV = ImmOp.getGlobal();
722 MIB.addGlobalAddress(GV, UseMI->getOperand(2).getImm()+ImmOp.getOffset(),
723 ImmOp.getTargetFlags());
724 OpStart = 3;
725 } else if (UseMID.mayStore()) {
726 MIB.add(AddAslMI->getOperand(2));
727 MIB.add(AddAslMI->getOperand(3));
728 const GlobalValue *GV = ImmOp.getGlobal();
729 MIB.addGlobalAddress(GV, UseMI->getOperand(1).getImm()+ImmOp.getOffset(),
730 ImmOp.getTargetFlags());
731 MIB.add(UseMI->getOperand(2));
732 OpStart = 3;
733 } else
734 llvm_unreachable("Unhandled instruction");
735
736 for (unsigned i = OpStart; i < OpEnd; ++i)
737 MIB.add(UseMI->getOperand(i));
738
739 Deleted.insert(UseMI);
740 }
741
742 return true;
743}
744
745bool HexagonOptAddrMode::xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
747 unsigned UseMOnum) {
748 const MachineOperand ImmOp = TfrMI->getOperand(1);
749 const MCInstrDesc &MID = UseMI->getDesc();
750 unsigned Changed = false;
751 if (MID.mayLoad())
752 Changed = changeLoad(UseMI, ImmOp, UseMOnum);
753 else if (MID.mayStore())
754 Changed = changeStore(UseMI, ImmOp, UseMOnum);
755 else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri)
756 Changed = changeAddAsl(UseN, UseMI, ImmOp, UseMOnum);
757
758 if (Changed)
759 Deleted.insert(UseMI);
760
761 return Changed;
762}
763
764bool HexagonOptAddrMode::processBlock(NodeAddr<BlockNode *> BA) {
765 bool Changed = false;
766
767 for (auto IA : BA.Addr->members(*DFG)) {
768 if (!DFG->IsCode<NodeAttrs::Stmt>(IA))
769 continue;
770
772 MachineInstr *MI = SA.Addr->getCode();
773 if ((MI->getOpcode() != Hexagon::A2_tfrsi ||
774 !MI->getOperand(1).isGlobal()) &&
775 (MI->getOpcode() != Hexagon::A2_addi ||
776 !MI->getOperand(2).isImm() || HII->isConstExtended(*MI)))
777 continue;
778
779 LLVM_DEBUG(dbgs() << "[Analyzing " << HII->getName(MI->getOpcode())
780 << "]: " << *MI << "\n\t[InstrNode]: "
781 << Print<NodeAddr<InstrNode *>>(IA, *DFG) << '\n');
782
783 NodeList UNodeList;
784 getAllRealUses(SA, UNodeList);
785
786 if (!allValidCandidates(SA, UNodeList))
787 continue;
788
789 // Analyze all uses of 'add'. If the output of 'add' is used as an address
790 // in the base+immediate addressing mode load/store instructions, see if
791 // they can be updated to use the immediate value as an offet. Thus,
792 // providing us the opportunity to eliminate 'add'.
793 // Ex: Rx= add(Rt,#12)
794 // memw(Rx+#0) = Rs
795 // This can be replaced with memw(Rt+#12) = Rs
796 //
797 // This transformation is only performed if all uses can be updated and
798 // the offset isn't required to be constant extended.
799 if (MI->getOpcode() == Hexagon::A2_addi) {
800 Changed |= processAddUses(SA, MI, UNodeList);
801 continue;
802 }
803
804 short SizeInc = 0;
805 Register DefR = MI->getOperand(0).getReg();
806 InstrEvalMap InstrEvalResult;
807
808 // Analyze all uses and calculate increase in size. Perform the optimization
809 // only if there is no increase in size.
810 if (!analyzeUses(DefR, UNodeList, InstrEvalResult, SizeInc))
811 continue;
812 if (SizeInc > CodeGrowthLimit)
813 continue;
814
815 bool KeepTfr = false;
816
817 LLVM_DEBUG(dbgs() << "\t[Total reached uses] : " << UNodeList.size()
818 << "\n");
819 LLVM_DEBUG(dbgs() << "\t[Processing Reached Uses] ===\n");
820 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
821 NodeAddr<UseNode *> UseN = *I;
822 assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
823 "Found a PhiRef node as a real reached use!!");
824
825 NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
826 MachineInstr *UseMI = OwnerN.Addr->getCode();
827 LLVM_DEBUG(dbgs() << "\t\t[MI <" << printMBBReference(*UseMI->getParent())
828 << ">]: " << *UseMI << "\n");
829
830 int UseMOnum = -1;
831 unsigned NumOperands = UseMI->getNumOperands();
832 for (unsigned j = 0; j < NumOperands - 1; ++j) {
833 const MachineOperand &op = UseMI->getOperand(j);
834 if (op.isReg() && op.isUse() && DefR == op.getReg())
835 UseMOnum = j;
836 }
837 // It is possible that the register will not be found in any operand.
838 // This could happen, for example, when DefR = R4, but the used
839 // register is D2.
840
841 // Change UseMI if replacement is possible. If any replacement failed,
842 // or wasn't attempted, make sure to keep the TFR.
843 bool Xformed = false;
844 if (UseMOnum >= 0 && InstrEvalResult[UseMI])
845 Xformed = xformUseMI(MI, UseMI, UseN, UseMOnum);
846 Changed |= Xformed;
847 KeepTfr |= !Xformed;
848 }
849 if (!KeepTfr)
850 Deleted.insert(MI);
851 }
852 return Changed;
853}
854
855bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
856 if (skipFunction(MF.getFunction()))
857 return false;
858
859 bool Changed = false;
860 auto &HST = MF.getSubtarget<HexagonSubtarget>();
861 MRI = &MF.getRegInfo();
862 HII = HST.getInstrInfo();
863 HRI = HST.getRegisterInfo();
864 const auto &MDF = getAnalysis<MachineDominanceFrontier>();
865 MDT = &getAnalysis<MachineDominatorTree>();
866
867 DataFlowGraph G(MF, *HII, *HRI, *MDT, MDF);
868 // Need to keep dead phis because we can propagate uses of registers into
869 // nodes dominated by those would-be phis.
871 DFG = &G;
872
873 Liveness L(*MRI, *DFG);
874 L.computePhiInfo();
875 LV = &L;
876
877 Deleted.clear();
878 NodeAddr<FuncNode *> FA = DFG->getFunc();
879 LLVM_DEBUG(dbgs() << "==== [RefMap#]=====:\n "
880 << Print<NodeAddr<FuncNode *>>(FA, *DFG) << "\n");
881
882 for (NodeAddr<BlockNode *> BA : FA.Addr->members(*DFG))
883 Changed |= processBlock(BA);
884
885 for (auto *MI : Deleted)
886 MI->eraseFromParent();
887
888 if (Changed) {
889 G.build();
890 L.computeLiveIns();
891 L.resetLiveIns();
892 L.resetKills();
893 }
894
895 return Changed;
896}
897
898//===----------------------------------------------------------------------===//
899// Public Constructor Functions
900//===----------------------------------------------------------------------===//
901
903 return new HexagonOptAddrMode();
904}
unsigned const MachineRegisterInfo * MRI
MachineInstrBuilder & UseMI
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
#define op(i)
static cl::opt< int > CodeGrowthLimit("hexagon-amode-growth-limit", cl::Hidden, cl::init(0), cl::desc("Code growth limit for address mode " "optimization"))
amode opt
amode Optimize addressing mode
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
#define P(N)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
bool mayStore() const
Return true if this instruction could possibly modify memory.
Definition: MCInstrDesc.h:444
bool mayLoad() const
Return true if this instruction could possibly read memory.
Definition: MCInstrDesc.h:438
static MDTuple * get(LLVMContext &Context, ArrayRef< Metadata * > MDs)
Definition: Metadata.h:1416
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
MachineInstrBundleIterator< MachineInstr > iterator
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
Register getReg(unsigned Idx) const
Get the register for the operand index.
const MachineInstrBuilder & add(const MachineOperand &MO) const
const MachineInstrBuilder & addGlobalAddress(const GlobalValue *GV, int64_t Offset=0, unsigned TargetFlags=0) const
Representation of each machine instruction.
Definition: MachineInstr.h:68
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:543
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:326
unsigned getNumOperands() const
Retuns the total number of operands.
Definition: MachineInstr.h:546
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:540
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
Definition: MachineInstr.h:472
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:553
MachineOperand class - Representation of each machine instruction operand.
const GlobalValue * getGlobal() const
void setImplicit(bool Val=true)
void setImm(int64_t immVal)
int64_t getImm() const
bool isImplicit() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
void setReg(Register Reg)
Change the register this operand corresponds to.
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
unsigned getTargetFlags() const
void setIsUndef(bool Val=true)
Register getReg() const
getReg - Returns the register number.
int64_t getOffset() const
Return the offset from the symbol in this operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
A NodeSet contains a set of SUnit DAG nodes with additional information that assigns a priority to th...
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:37
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Iterator for intrusive lists based on ilist_node.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:440
void initializeHexagonOptAddrModePass(PassRegistry &)
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
FunctionPass * createHexagonOptAddrMode()
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
std::unordered_map< RegisterId, DefStack > DefStackMap
Definition: RDFGraph.h:772
std::unordered_map< RegisterId, NodeRefSet > RefMap
Definition: RDFLiveness.h:60