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 "Hexagon.h"
13#include "HexagonInstrInfo.h"
14#include "HexagonSubtarget.h"
15#include "MCTargetDesc/HexagonBaseInfo.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseSet.h"
18#include "llvm/ADT/PostOrderIterator.h"
19#include "llvm/ADT/StringRef.h"
20#include "llvm/CodeGen/LivePhysRegs.h"
21#include "llvm/CodeGen/MachineBasicBlock.h"
22#include "llvm/CodeGen/MachineDominanceFrontier.h"
23#include "llvm/CodeGen/MachineDominators.h"
24#include "llvm/CodeGen/MachineFunction.h"
25#include "llvm/CodeGen/MachineFunctionPass.h"
26#include "llvm/CodeGen/MachineInstr.h"
27#include "llvm/CodeGen/MachineInstrBuilder.h"
28#include "llvm/CodeGen/MachineOperand.h"
29#include "llvm/CodeGen/MachineRegisterInfo.h"
30#include "llvm/CodeGen/RDFGraph.h"
31#include "llvm/CodeGen/RDFLiveness.h"
32#include "llvm/CodeGen/RDFRegisters.h"
33#include "llvm/CodeGen/TargetSubtargetInfo.h"
34#include "llvm/InitializePasses.h"
35#include "llvm/MC/MCInstrDesc.h"
36#include "llvm/Pass.h"
37#include "llvm/Support/CommandLine.h"
38#include "llvm/Support/Debug.h"
39#include "llvm/Support/ErrorHandling.h"
40#include "llvm/Support/raw_ostream.h"
41#include <cassert>
42#include <cstdint>
43
44#define DEBUG_TYPE "opt-addr-mode"
45
46using namespace llvm;
47using namespace rdf;
48
49static cl::opt<int> CodeGrowthLimit("hexagon-amode-growth-limit",
50 cl::Hidden, cl::init(Val: 0), cl::desc("Code growth limit for address mode "
51 "optimization"));
52
53extern cl::opt<unsigned> RDFFuncBlockLimit;
54
55namespace {
56
57class HexagonOptAddrMode : public MachineFunctionPass {
58public:
59 static char ID;
60
61 HexagonOptAddrMode() : MachineFunctionPass(ID) {}
62
63 StringRef getPassName() const override {
64 return "Optimize addressing mode of load/store";
65 }
66
67 void getAnalysisUsage(AnalysisUsage &AU) const override {
68 MachineFunctionPass::getAnalysisUsage(AU);
69 AU.addRequired<MachineDominatorTreeWrapperPass>();
70 AU.addRequired<MachineDominanceFrontierWrapperPass>();
71 AU.setPreservesAll();
72 }
73
74 bool runOnMachineFunction(MachineFunction &MF) override;
75
76private:
77 using MISetType = DenseSet<MachineInstr *>;
78 using InstrEvalMap = DenseMap<MachineInstr *, bool>;
79 DenseSet<MachineInstr *> ProcessedAddiInsts;
80
81 MachineRegisterInfo *MRI = nullptr;
82 const TargetRegisterInfo *TRI = nullptr;
83 const HexagonInstrInfo *HII = nullptr;
84 const HexagonRegisterInfo *HRI = nullptr;
85 MachineDominatorTree *MDT = nullptr;
86 DataFlowGraph *DFG = nullptr;
87 Liveness *LV = nullptr;
88 MISetType Deleted;
89
90 bool processBlock(NodeAddr<BlockNode *> BA);
91 bool xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
92 NodeAddr<UseNode *> UseN, unsigned UseMOnum);
93 bool processAddBases(NodeAddr<StmtNode *> AddSN, MachineInstr *AddMI);
94 bool usedInLoadStore(NodeAddr<StmtNode *> CurrentInstSN, int64_t NewOffset);
95 bool findFirstReachedInst(
96 MachineInstr *AddMI,
97 std::vector<std::pair<NodeAddr<StmtNode *>, NodeAddr<UseNode *>>>
98 &AddiList,
99 NodeAddr<StmtNode *> &UseSN);
100 bool updateAddBases(MachineInstr *CurrentMI, MachineInstr *FirstReachedMI,
101 int64_t NewOffset);
102 bool processAddUses(NodeAddr<StmtNode *> AddSN, MachineInstr *AddMI,
103 const NodeList &UNodeList);
104 bool updateAddUses(MachineInstr *AddMI, MachineInstr *UseMI);
105 bool analyzeUses(unsigned DefR, const NodeList &UNodeList,
106 InstrEvalMap &InstrEvalResult, short &SizeInc);
107 bool hasRepForm(MachineInstr &MI, unsigned TfrDefR);
108 bool canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN, MachineInstr &MI,
109 const NodeList &UNodeList);
110 bool isSafeToExtLR(NodeAddr<StmtNode *> SN, MachineInstr *MI,
111 Register LRExtReg, const NodeList &UNodeList);
112 void getAllRealUses(NodeAddr<StmtNode *> SN, NodeList &UNodeList);
113 bool allValidCandidates(NodeAddr<StmtNode *> SA, NodeList &UNodeList);
114 short getBaseWithLongOffset(const MachineInstr &MI) const;
115 bool changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
116 unsigned ImmOpNum);
117 bool changeLoad(MachineInstr *OldMI, MachineOperand ImmOp, unsigned ImmOpNum);
118 bool changeAddAsl(NodeAddr<UseNode *> AddAslUN, MachineInstr *AddAslMI,
119 const MachineOperand &ImmOp, unsigned ImmOpNum);
120 bool isValidOffset(MachineInstr *MI, int Offset);
121 unsigned getBaseOpPosition(MachineInstr *MI);
122 unsigned getOffsetOpPosition(MachineInstr *MI);
123};
124
125} // end anonymous namespace
126
127char HexagonOptAddrMode::ID = 0;
128
129INITIALIZE_PASS_BEGIN(HexagonOptAddrMode, "amode-opt",
130 "Optimize addressing mode", false, false)
131INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
132INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontierWrapperPass)
133INITIALIZE_PASS_END(HexagonOptAddrMode, "amode-opt", "Optimize addressing mode",
134 false, false)
135
136bool HexagonOptAddrMode::hasRepForm(MachineInstr &MI, unsigned TfrDefR) {
137 const MCInstrDesc &MID = MI.getDesc();
138
139 if ((!MID.mayStore() && !MID.mayLoad()) || HII->isPredicated(MI))
140 return false;
141
142 if (MID.mayStore()) {
143 MachineOperand StOp = MI.getOperand(i: MI.getNumOperands() - 1);
144 if (StOp.isReg() && StOp.getReg() == TfrDefR)
145 return false;
146 }
147
148 if (HII->getAddrMode(MI) == HexagonII::BaseRegOffset)
149 // Transform to Absolute plus register offset.
150 return (HII->changeAddrMode_rr_ur(MI) >= 0);
151 else if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset)
152 // Transform to absolute addressing mode.
153 return (HII->changeAddrMode_io_abs(MI) >= 0);
154
155 return false;
156}
157
158// Check if addasl instruction can be removed. This is possible only
159// if it's feeding to only load/store instructions with base + register
160// offset as these instruction can be transformed to use 'absolute plus
161// shifted register offset'.
162// ex:
163// Rs = ##foo
164// Rx = addasl(Rs, Rt, #2)
165// Rd = memw(Rx + #28)
166// Above three instructions can be replaced with Rd = memw(Rt<<#2 + ##foo+28)
167
168bool HexagonOptAddrMode::canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN,
169 MachineInstr &MI,
170 const NodeList &UNodeList) {
171 // check offset size in addasl. if 'offset > 3' return false
172 const MachineOperand &OffsetOp = MI.getOperand(i: 3);
173 if (!OffsetOp.isImm() || OffsetOp.getImm() > 3)
174 return false;
175
176 Register OffsetReg = MI.getOperand(i: 2).getReg();
177 RegisterRef OffsetRR;
178 NodeId OffsetRegRD = 0;
179 for (NodeAddr<UseNode *> UA : AddAslSN.Addr->members_if(P: DFG->IsUse, G: *DFG)) {
180 RegisterRef RR = UA.Addr->getRegRef(G: *DFG);
181 if (OffsetReg == RR.asMCReg()) {
182 OffsetRR = RR;
183 OffsetRegRD = UA.Addr->getReachingDef();
184 }
185 }
186
187 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
188 NodeAddr<UseNode *> UA = *I;
189 NodeAddr<InstrNode *> IA = UA.Addr->getOwner(G: *DFG);
190 if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
191 return false;
192 NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(RefRR: OffsetRR, IA);
193 if ((DFG->IsDef(BA: AA) && AA.Id != OffsetRegRD) ||
194 AA.Addr->getReachingDef() != OffsetRegRD)
195 return false;
196
197 MachineInstr &UseMI = *NodeAddr<StmtNode *>(IA).Addr->getCode();
198 NodeAddr<DefNode *> OffsetRegDN = DFG->addr<DefNode *>(N: OffsetRegRD);
199 // Reaching Def to an offset register can't be a phi.
200 if ((OffsetRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
201 MI.getParent() != UseMI.getParent())
202 return false;
203
204 const MCInstrDesc &UseMID = UseMI.getDesc();
205 if ((!UseMID.mayLoad() && !UseMID.mayStore()) ||
206 HII->getAddrMode(MI: UseMI) != HexagonII::BaseImmOffset ||
207 getBaseWithLongOffset(MI: UseMI) < 0)
208 return false;
209
210 // Addasl output can't be a store value.
211 if (UseMID.mayStore() && UseMI.getOperand(i: 2).isReg() &&
212 UseMI.getOperand(i: 2).getReg() == MI.getOperand(i: 0).getReg())
213 return false;
214
215 for (auto &Mo : UseMI.operands())
216 // Is it a frame index?
217 if (Mo.isFI())
218 return false;
219 // Is the OffsetReg definition actually reaches UseMI?
220 if (!UseMI.getParent()->isLiveIn(Reg: OffsetReg) &&
221 MI.getParent() != UseMI.getParent()) {
222 LLVM_DEBUG(dbgs() << " The offset reg " << printReg(OffsetReg, TRI)
223 << " is NOT live in to MBB "
224 << UseMI.getParent()->getName() << "\n");
225 return false;
226 }
227 }
228 return true;
229}
230
231bool HexagonOptAddrMode::allValidCandidates(NodeAddr<StmtNode *> SA,
232 NodeList &UNodeList) {
233 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
234 NodeAddr<UseNode *> UN = *I;
235 RegisterRef UR = UN.Addr->getRegRef(G: *DFG);
236 NodeSet Visited, Defs;
237 const auto &P = LV->getAllReachingDefsRec(RefRR: UR, RefA: UN, Visited, Defs);
238 if (!P.second) {
239 LLVM_DEBUG({
240 dbgs() << "*** Unable to collect all reaching defs for use ***\n"
241 << PrintNode<UseNode*>(UN, *DFG) << '\n'
242 << "The program's complexity may exceed the limits.\n";
243 });
244 return false;
245 }
246 const auto &ReachingDefs = P.first;
247 if (ReachingDefs.size() > 1) {
248 LLVM_DEBUG({
249 dbgs() << "*** Multiple Reaching Defs found!!! ***\n";
250 for (auto DI : ReachingDefs) {
251 NodeAddr<UseNode *> DA = DFG->addr<UseNode *>(DI);
252 NodeAddr<StmtNode *> TempIA = DA.Addr->getOwner(*DFG);
253 dbgs() << "\t\t[Reaching Def]: "
254 << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
255 }
256 });
257 return false;
258 }
259 }
260 return true;
261}
262
263void HexagonOptAddrMode::getAllRealUses(NodeAddr<StmtNode *> SA,
264 NodeList &UNodeList) {
265 for (NodeAddr<DefNode *> DA : SA.Addr->members_if(P: DFG->IsDef, G: *DFG)) {
266 LLVM_DEBUG(dbgs() << "\t\t[DefNode]: "
267 << Print<NodeAddr<DefNode *>>(DA, *DFG) << "\n");
268 RegisterRef DR = DA.Addr->getRegRef(G: *DFG);
269
270 auto UseSet = LV->getAllReachedUses(RefRR: DR, DefA: DA);
271
272 for (auto UI : UseSet) {
273 NodeAddr<UseNode *> UA = DFG->addr<UseNode *>(N: UI);
274 LLVM_DEBUG({
275 NodeAddr<StmtNode *> TempIA = UA.Addr->getOwner(*DFG);
276 dbgs() << "\t\t\t[Reached Use]: "
277 << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
278 });
279
280 if (UA.Addr->getFlags() & NodeAttrs::PhiRef) {
281 NodeAddr<PhiNode *> PA = UA.Addr->getOwner(G: *DFG);
282 NodeId id = PA.Id;
283 const Liveness::RefMap &phiUse = LV->getRealUses(P: id);
284 LLVM_DEBUG(dbgs() << "\t\t\t\tphi real Uses"
285 << Print<Liveness::RefMap>(phiUse, *DFG) << "\n");
286 if (!phiUse.empty()) {
287 for (auto I : phiUse) {
288 if (!DFG->getPRI().alias(RA: RegisterRef(I.first), RB: DR))
289 continue;
290 auto phiUseSet = I.second;
291 for (auto phiUI : phiUseSet) {
292 NodeAddr<UseNode *> phiUA = DFG->addr<UseNode *>(N: phiUI.first);
293 UNodeList.push_back(Elt: phiUA);
294 }
295 }
296 }
297 } else
298 UNodeList.push_back(Elt: UA);
299 }
300 }
301}
302
303bool HexagonOptAddrMode::isSafeToExtLR(NodeAddr<StmtNode *> SN,
304 MachineInstr *MI, Register LRExtReg,
305 const NodeList &UNodeList) {
306 RegisterRef LRExtRR;
307 NodeId LRExtRegRD = 0;
308 // Iterate through all the UseNodes in SN and find the reaching def
309 // for the LRExtReg.
310 for (NodeAddr<UseNode *> UA : SN.Addr->members_if(P: DFG->IsUse, G: *DFG)) {
311 RegisterRef RR = UA.Addr->getRegRef(G: *DFG);
312 if (LRExtReg == RR.asMCReg()) {
313 LRExtRR = RR;
314 LRExtRegRD = UA.Addr->getReachingDef();
315 }
316 }
317
318 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
319 NodeAddr<UseNode *> UA = *I;
320 NodeAddr<InstrNode *> IA = UA.Addr->getOwner(G: *DFG);
321 // The reaching def of LRExtRR at load/store node should be same as the
322 // one reaching at the SN.
323 if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
324 return false;
325 NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(RefRR: LRExtRR, IA);
326 if ((DFG->IsDef(BA: AA) && AA.Id != LRExtRegRD) ||
327 AA.Addr->getReachingDef() != LRExtRegRD) {
328 LLVM_DEBUG(
329 dbgs() << "isSafeToExtLR: Returning false; another reaching def\n");
330 return false;
331 }
332
333 // If the register is undefined (for example if it's a reserved register),
334 // it may still be possible to extend the range, but it's safer to be
335 // conservative and just punt.
336 if (LRExtRegRD == 0)
337 return false;
338
339 MachineInstr *UseMI = NodeAddr<StmtNode *>(IA).Addr->getCode();
340 NodeAddr<DefNode *> LRExtRegDN = DFG->addr<DefNode *>(N: LRExtRegRD);
341 // Reaching Def to LRExtReg can't be a phi.
342 if ((LRExtRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
343 MI->getParent() != UseMI->getParent())
344 return false;
345 // Is the OffsetReg definition actually reaches UseMI?
346 if (!UseMI->getParent()->isLiveIn(Reg: LRExtReg) &&
347 MI->getParent() != UseMI->getParent()) {
348 LLVM_DEBUG(dbgs() << " The LRExtReg reg " << printReg(LRExtReg, TRI)
349 << " is NOT live in to MBB "
350 << UseMI->getParent()->getName() << "\n");
351 return false;
352 }
353 }
354 return true;
355}
356
357bool HexagonOptAddrMode::isValidOffset(MachineInstr *MI, int Offset) {
358 if (HII->isHVXVec(MI: *MI)) {
359 // only HVX vgather instructions handled
360 // TODO: extend the pass to other vector load/store operations
361 switch (MI->getOpcode()) {
362 case Hexagon::V6_vgathermh_pseudo:
363 case Hexagon::V6_vgathermw_pseudo:
364 case Hexagon::V6_vgathermhw_pseudo:
365 case Hexagon::V6_vgathermhq_pseudo:
366 case Hexagon::V6_vgathermwq_pseudo:
367 case Hexagon::V6_vgathermhwq_pseudo:
368 return HII->isValidOffset(Opcode: MI->getOpcode(), Offset, Extend: false);
369 default:
370 if (HII->getAddrMode(MI: *MI) == HexagonII::BaseImmOffset) {
371 // The immediates are mentioned in multiples of vector counts
372 unsigned AlignMask = HII->getMemAccessSize(MI: *MI) - 1;
373 if ((AlignMask & Offset) == 0)
374 return HII->isValidOffset(Opcode: MI->getOpcode(), Offset, Extend: false);
375 }
376 return false;
377 }
378 }
379
380 if (HII->getAddrMode(MI: *MI) != HexagonII::BaseImmOffset)
381 return false;
382
383 unsigned AlignMask = 0;
384 switch (HII->getMemAccessSize(MI: *MI)) {
385 case HexagonII::MemAccessSize::DoubleWordAccess:
386 AlignMask = 0x7;
387 break;
388 case HexagonII::MemAccessSize::WordAccess:
389 AlignMask = 0x3;
390 break;
391 case HexagonII::MemAccessSize::HalfWordAccess:
392 AlignMask = 0x1;
393 break;
394 case HexagonII::MemAccessSize::ByteAccess:
395 AlignMask = 0x0;
396 break;
397 default:
398 return false;
399 }
400
401 if ((AlignMask & Offset) != 0)
402 return false;
403 return HII->isValidOffset(Opcode: MI->getOpcode(), Offset, Extend: false);
404}
405
406unsigned HexagonOptAddrMode::getBaseOpPosition(MachineInstr *MI) {
407 const MCInstrDesc &MID = MI->getDesc();
408 switch (MI->getOpcode()) {
409 // vgather pseudos are mayLoad and mayStore
410 // hence need to explicitly specify Base and
411 // Offset operand positions
412 case Hexagon::V6_vgathermh_pseudo:
413 case Hexagon::V6_vgathermw_pseudo:
414 case Hexagon::V6_vgathermhw_pseudo:
415 case Hexagon::V6_vgathermhq_pseudo:
416 case Hexagon::V6_vgathermwq_pseudo:
417 case Hexagon::V6_vgathermhwq_pseudo:
418 return 0;
419 default:
420 return MID.mayLoad() ? 1 : 0;
421 }
422}
423
424unsigned HexagonOptAddrMode::getOffsetOpPosition(MachineInstr *MI) {
425 assert(
426 (HII->getAddrMode(*MI) == HexagonII::BaseImmOffset) &&
427 "Looking for an offset in non-BaseImmOffset addressing mode instruction");
428
429 const MCInstrDesc &MID = MI->getDesc();
430 switch (MI->getOpcode()) {
431 // vgather pseudos are mayLoad and mayStore
432 // hence need to explicitly specify Base and
433 // Offset operand positions
434 case Hexagon::V6_vgathermh_pseudo:
435 case Hexagon::V6_vgathermw_pseudo:
436 case Hexagon::V6_vgathermhw_pseudo:
437 case Hexagon::V6_vgathermhq_pseudo:
438 case Hexagon::V6_vgathermwq_pseudo:
439 case Hexagon::V6_vgathermhwq_pseudo:
440 return 1;
441 default:
442 return MID.mayLoad() ? 2 : 1;
443 }
444}
445
446bool HexagonOptAddrMode::usedInLoadStore(NodeAddr<StmtNode *> CurrentInstSN,
447 int64_t NewOffset) {
448 NodeList LoadStoreUseList;
449
450 getAllRealUses(SA: CurrentInstSN, UNodeList&: LoadStoreUseList);
451 bool FoundLoadStoreUse = false;
452 for (NodeAddr<UseNode *> UN : LoadStoreUseList) {
453 NodeAddr<StmtNode *> SN = UN.Addr->getOwner(G: *DFG);
454 MachineInstr *LoadStoreMI = SN.Addr->getCode();
455 const MCInstrDesc &MID = LoadStoreMI->getDesc();
456 if ((MID.mayLoad() || MID.mayStore()) &&
457 isValidOffset(MI: LoadStoreMI, Offset: NewOffset)) {
458 FoundLoadStoreUse = true;
459 break;
460 }
461 }
462 return FoundLoadStoreUse;
463}
464
465bool HexagonOptAddrMode::findFirstReachedInst(
466 MachineInstr *AddMI,
467 std::vector<std::pair<NodeAddr<StmtNode *>, NodeAddr<UseNode *>>> &AddiList,
468 NodeAddr<StmtNode *> &UseSN) {
469 // Find the very first Addi instruction in the current basic block among the
470 // AddiList This is the Addi that should be preserved so that we do not need
471 // to handle the complexity of moving instructions
472 //
473 // TODO: find Addi instructions across basic blocks
474 //
475 // TODO: Try to remove this and add a solution that optimizes the number of
476 // Addi instructions that can be modified.
477 // This change requires choosing the Addi with the median offset value, but
478 // would also require moving that instruction above the others. Since this
479 // pass runs after register allocation, there might be multiple cases that
480 // need to be handled if we move instructions around
481 MachineBasicBlock *CurrentMBB = AddMI->getParent();
482 for (auto &InstIter : *CurrentMBB) {
483 // If the instruction is an Addi and is in the AddiList
484 if (InstIter.getOpcode() == Hexagon::A2_addi) {
485 auto Iter = llvm::find_if(Range&: AddiList, P: [&InstIter](const auto &SUPair) {
486 return SUPair.first.Addr->getCode() == &InstIter;
487 });
488 if (Iter != AddiList.end()) {
489 UseSN = Iter->first;
490 return true;
491 }
492 }
493 }
494 return false;
495}
496
497// This function tries to modify the immediate value in Hexagon::Addi
498// instructions, so that the immediates could then be moved into a load/store
499// instruction with offset and the add removed completely when we call
500// processAddUses
501//
502// For Example, If we have the below sequence of instructions:
503//
504// r1 = add(r2,#1024)
505// ...
506// r3 = add(r2,#1152)
507// ...
508// r4 = add(r2,#1280)
509//
510// Where the register r2 has the same reaching definition, They get modified to
511// the below sequence:
512//
513// r1 = add(r2,#1024)
514// ...
515// r3 = add(r1,#128)
516// ...
517// r4 = add(r1,#256)
518//
519// The below change helps the processAddUses method to later move the
520// immediates #128 and #256 into a load/store instruction that can take an
521// offset, like the Vd = mem(Rt+#s4)
522bool HexagonOptAddrMode::processAddBases(NodeAddr<StmtNode *> AddSN,
523 MachineInstr *AddMI) {
524
525 bool Changed = false;
526
527 LLVM_DEBUG(dbgs() << "\n\t\t[Processing Addi]: " << *AddMI << "\n");
528
529 auto Processed =
530 [](const MachineInstr *MI,
531 const DenseSet<MachineInstr *> &ProcessedAddiInsts) -> bool {
532 // If we've already processed this Addi, just return
533 if (ProcessedAddiInsts.contains(V: MI)) {
534 LLVM_DEBUG(dbgs() << "\t\t\tAddi already found in ProcessedAddiInsts: "
535 << *MI << "\n\t\t\tSkipping...");
536 return true;
537 }
538 return false;
539 };
540
541 if (Processed(AddMI, ProcessedAddiInsts))
542 return Changed;
543 ProcessedAddiInsts.insert(V: AddMI);
544
545 // Get the base register that would be shared by other Addi Instructions
546 Register BaseReg = AddMI->getOperand(i: 1).getReg();
547
548 // Store a list of all Addi instructions that share the above common base
549 // register
550 std::vector<std::pair<NodeAddr<StmtNode *>, NodeAddr<UseNode *>>> AddiList;
551
552 NodeId UAReachingDefID;
553 // Find the UseNode that contains the base register and it's reachingDef
554 for (NodeAddr<UseNode *> UA : AddSN.Addr->members_if(P: DFG->IsUse, G: *DFG)) {
555 RegisterRef URR = UA.Addr->getRegRef(G: *DFG);
556 if (BaseReg != URR.asMCReg())
557 continue;
558
559 UAReachingDefID = UA.Addr->getReachingDef();
560 NodeAddr<DefNode *> UADef = DFG->addr<DefNode *>(N: UAReachingDefID);
561 if (!UAReachingDefID || UADef.Addr->getFlags() & NodeAttrs::PhiRef) {
562 LLVM_DEBUG(dbgs() << "\t\t\t Could not find reachingDef. Skipping...\n");
563 return false;
564 }
565 }
566
567 NodeAddr<DefNode *> UAReachingDef = DFG->addr<DefNode *>(N: UAReachingDefID);
568 NodeAddr<StmtNode *> ReachingDefStmt = UAReachingDef.Addr->getOwner(G: *DFG);
569
570 // If the reaching definition is a predicated instruction, this might not be
571 // the only definition of our base register, so return immediately.
572 MachineInstr *ReachingDefInstr = ReachingDefStmt.Addr->getCode();
573 if (HII->isPredicated(MI: *ReachingDefInstr))
574 return false;
575
576 NodeList AddiUseList;
577
578 // Find all Addi instructions that share the same base register and add them
579 // to the AddiList
580 getAllRealUses(SA: ReachingDefStmt, UNodeList&: AddiUseList);
581 for (NodeAddr<UseNode *> UN : AddiUseList) {
582 NodeAddr<StmtNode *> SN = UN.Addr->getOwner(G: *DFG);
583 MachineInstr *MI = SN.Addr->getCode();
584
585 // Only add instructions if it's an Addi and it's not already processed.
586 if (MI->getOpcode() == Hexagon::A2_addi &&
587 !(MI != AddMI && Processed(MI, ProcessedAddiInsts))) {
588 AddiList.push_back(x: {SN, UN});
589
590 // This ensures that we process each instruction only once
591 ProcessedAddiInsts.insert(V: MI);
592 }
593 }
594
595 // If there's only one Addi instruction, nothing to do here
596 if (AddiList.size() <= 1)
597 return Changed;
598
599 NodeAddr<StmtNode *> FirstReachedUseSN;
600 // Find the first reached use of Addi instruction from the list
601 if (!findFirstReachedInst(AddMI, AddiList, UseSN&: FirstReachedUseSN))
602 return Changed;
603
604 // If we reach this point we know that the StmtNode FirstReachedUseSN is for
605 // an Addi instruction. So, we're guaranteed to have just one DefNode, and
606 // hence we can access the front() directly without checks
607 NodeAddr<DefNode *> FirstReachedUseDN =
608 FirstReachedUseSN.Addr->members_if(P: DFG->IsDef, G: *DFG).front();
609
610 MachineInstr *FirstReachedMI = FirstReachedUseSN.Addr->getCode();
611 const MachineOperand FirstReachedMIImmOp = FirstReachedMI->getOperand(i: 2);
612 if (!FirstReachedMIImmOp.isImm())
613 return Changed;
614
615 for (auto &I : AddiList) {
616 NodeAddr<StmtNode *> CurrentInstSN = I.first;
617 NodeAddr<UseNode *> CurrentInstUN = I.second;
618
619 MachineInstr *CurrentMI = CurrentInstSN.Addr->getCode();
620 MachineOperand &CurrentMIImmOp = CurrentMI->getOperand(i: 2);
621
622 int64_t NewOffset;
623
624 // Even though we know it's an Addi instruction, the second operand could be
625 // a global value and not an immediate
626 if (!CurrentMIImmOp.isImm())
627 continue;
628
629 NewOffset = CurrentMIImmOp.getImm() - FirstReachedMIImmOp.getImm();
630
631 // This is the first occurring Addi, so skip modifying this
632 if (CurrentMI == FirstReachedMI) {
633 continue;
634 }
635
636 if (CurrentMI->getParent() != FirstReachedMI->getParent())
637 continue;
638
639 // Modify the Addi instruction only if it could be used to modify a
640 // future load/store instruction and get removed
641 //
642 // This check is needed because, if we modify the current Addi instruction
643 // we create RAW dependence between the FirstReached Addi and the current
644 // one, which could result in extra packets. So we only do this change if
645 // we know the current Addi would get removed later
646 if (!usedInLoadStore(CurrentInstSN, NewOffset))
647 return Changed;
648
649 // Verify whether the First Addi's definition register is still live when
650 // we reach the current Addi
651 RegisterRef FirstReachedDefRR = FirstReachedUseDN.Addr->getRegRef(G: *DFG);
652 NodeAddr<InstrNode *> CurrentAddiIN = CurrentInstUN.Addr->getOwner(G: *DFG);
653 NodeAddr<RefNode *> NearestAA =
654 LV->getNearestAliasedRef(RefRR: FirstReachedDefRR, IA: CurrentAddiIN);
655 if ((DFG->IsDef(BA: NearestAA) && NearestAA.Id != FirstReachedUseDN.Id) ||
656 (!DFG->IsDef(BA: NearestAA) &&
657 NearestAA.Addr->getReachingDef() != FirstReachedUseDN.Id)) {
658 // Found another definition of FirstReachedDef
659 LLVM_DEBUG(dbgs() << "\t\t\tCould not modify below Addi since the first "
660 "defined Addi register was redefined\n");
661 continue;
662 }
663
664 MachineOperand CurrentMIBaseOp = CurrentMI->getOperand(i: 1);
665 if (CurrentMIBaseOp.getReg() != FirstReachedMI->getOperand(i: 1).getReg()) {
666 continue;
667 }
668
669 // If we reached this point, then we can modify MI to use the result of
670 // FirstReachedMI
671 Changed |= updateAddBases(CurrentMI, FirstReachedMI, NewOffset);
672
673 // Update the reachingDef of the Current AddI use after change
674 CurrentInstUN.Addr->linkToDef(Self: CurrentInstUN.Id, DA: FirstReachedUseDN);
675 }
676
677 return Changed;
678}
679
680bool HexagonOptAddrMode::updateAddBases(MachineInstr *CurrentMI,
681 MachineInstr *FirstReachedMI,
682 int64_t NewOffset) {
683 LLVM_DEBUG(dbgs() << "[About to modify the Addi]: " << *CurrentMI << "\n");
684 const MachineOperand FirstReachedDef = FirstReachedMI->getOperand(i: 0);
685 Register FirstDefRegister = FirstReachedDef.getReg();
686
687 MachineOperand &CurrentMIBaseOp = CurrentMI->getOperand(i: 1);
688 MachineOperand &CurrentMIImmOp = CurrentMI->getOperand(i: 2);
689
690 CurrentMIBaseOp.setReg(FirstDefRegister);
691 CurrentMIBaseOp.setIsUndef(FirstReachedDef.isUndef());
692 CurrentMIBaseOp.setImplicit(FirstReachedDef.isImplicit());
693 CurrentMIImmOp.setImm(NewOffset);
694
695 // CurrentMI now reads FirstReachedMI's definition register, so that register
696 // has to stay live until CurrentMI. An earlier use of it (e.g. the previous
697 // base of CurrentMI being folded away) may have been marked as the last use
698 // with a kill flag, which would leave this new use reading a dead register.
699 // Clear any such kill flags between the two instructions. Both are in the
700 // same basic block (verified by the caller).
701 for (MachineBasicBlock::iterator I = FirstReachedMI->getIterator(),
702 E = CurrentMI->getIterator();
703 I != E; ++I)
704 I->clearRegisterKills(Reg: FirstDefRegister, RegInfo: TRI);
705
706 ProcessedAddiInsts.insert(V: CurrentMI);
707 return true;
708}
709
710bool HexagonOptAddrMode::processAddUses(NodeAddr<StmtNode *> AddSN,
711 MachineInstr *AddMI,
712 const NodeList &UNodeList) {
713
714 Register AddDefR = AddMI->getOperand(i: 0).getReg();
715 Register BaseReg = AddMI->getOperand(i: 1).getReg();
716 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
717 NodeAddr<UseNode *> UN = *I;
718 NodeAddr<StmtNode *> SN = UN.Addr->getOwner(G: *DFG);
719 MachineInstr *MI = SN.Addr->getCode();
720 const MCInstrDesc &MID = MI->getDesc();
721 if ((!MID.mayLoad() && !MID.mayStore()) ||
722 HII->getAddrMode(MI: *MI) != HexagonII::BaseImmOffset)
723 return false;
724
725 MachineOperand BaseOp = MI->getOperand(i: getBaseOpPosition(MI));
726
727 if (!BaseOp.isReg() || BaseOp.getReg() != AddDefR)
728 return false;
729
730 MachineOperand OffsetOp = MI->getOperand(i: getOffsetOpPosition(MI));
731 if (!OffsetOp.isImm())
732 return false;
733
734 int64_t newOffset = OffsetOp.getImm() + AddMI->getOperand(i: 2).getImm();
735 if (!isValidOffset(MI, Offset: newOffset))
736 return false;
737 }
738
739 // Since we'll be extending the live range of Rt in the following example,
740 // make sure that is safe. another definition of Rt doesn't exist between
741 // 'add' and load/store instruction.
742 //
743 // Ex: Rx= add(Rt,#10)
744 // memw(Rx+#0) = Rs
745 // will be replaced with => memw(Rt+#10) = Rs
746 // Note: isSafeToExtLR arguments are loop-invariant; call it once after
747 // validating all uses to avoid O(N^2) behavior when UNodeList is large.
748 if (!isSafeToExtLR(SN: AddSN, MI: AddMI, LRExtReg: BaseReg, UNodeList))
749 return false;
750
751 NodeId LRExtRegRD = 0;
752 // Iterate through all the UseNodes in SN and find the reaching def
753 // for the LRExtReg.
754 for (NodeAddr<UseNode *> UA : AddSN.Addr->members_if(P: DFG->IsUse, G: *DFG)) {
755 RegisterRef RR = UA.Addr->getRegRef(G: *DFG);
756 if (BaseReg == RR.asMCReg())
757 LRExtRegRD = UA.Addr->getReachingDef();
758 }
759
760 // Update all the uses of 'add' with the appropriate base and offset
761 // values.
762 bool Changed = false;
763 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
764 NodeAddr<UseNode *> UseN = *I;
765 assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
766 "Found a PhiRef node as a real reached use!!");
767
768 NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(G: *DFG);
769 MachineInstr *UseMI = OwnerN.Addr->getCode();
770 LLVM_DEBUG(dbgs() << "\t\t[MI <BB#" << UseMI->getParent()->getNumber()
771 << ">]: " << *UseMI << "\n");
772 Changed |= updateAddUses(AddMI, UseMI);
773
774 // Set the reachingDef for UseNode under consideration
775 // after updating the Add use. This local change is
776 // to avoid rebuilding of the RDF graph after update.
777 NodeAddr<DefNode *> LRExtRegDN = DFG->addr<DefNode *>(N: LRExtRegRD);
778 UseN.Addr->linkToDef(Self: UseN.Id, DA: LRExtRegDN);
779 }
780
781 if (Changed)
782 Deleted.insert(V: AddMI);
783
784 return Changed;
785}
786
787bool HexagonOptAddrMode::updateAddUses(MachineInstr *AddMI,
788 MachineInstr *UseMI) {
789 const MachineOperand ImmOp = AddMI->getOperand(i: 2);
790 const MachineOperand AddRegOp = AddMI->getOperand(i: 1);
791 Register NewReg = AddRegOp.getReg();
792
793 MachineOperand &BaseOp = UseMI->getOperand(i: getBaseOpPosition(MI: UseMI));
794 MachineOperand &OffsetOp = UseMI->getOperand(i: getOffsetOpPosition(MI: UseMI));
795 BaseOp.setReg(NewReg);
796 BaseOp.setIsUndef(AddRegOp.isUndef());
797 BaseOp.setImplicit(AddRegOp.isImplicit());
798 OffsetOp.setImm(ImmOp.getImm() + OffsetOp.getImm());
799
800 return true;
801}
802
803bool HexagonOptAddrMode::analyzeUses(unsigned tfrDefR,
804 const NodeList &UNodeList,
805 InstrEvalMap &InstrEvalResult,
806 short &SizeInc) {
807 bool KeepTfr = false;
808 bool HasRepInstr = false;
809 InstrEvalResult.clear();
810
811 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
812 bool CanBeReplaced = false;
813 NodeAddr<UseNode *> UN = *I;
814 NodeAddr<StmtNode *> SN = UN.Addr->getOwner(G: *DFG);
815 MachineInstr &MI = *SN.Addr->getCode();
816 const MCInstrDesc &MID = MI.getDesc();
817 if ((MID.mayLoad() || MID.mayStore())) {
818 if (!hasRepForm(MI, TfrDefR: tfrDefR)) {
819 KeepTfr = true;
820 continue;
821 }
822 SizeInc++;
823 CanBeReplaced = true;
824 } else if (MI.getOpcode() == Hexagon::S2_addasl_rrri) {
825 NodeList AddaslUseList;
826
827 LLVM_DEBUG(dbgs() << "\nGetting ReachedUses for === " << MI << "\n");
828 getAllRealUses(SA: SN, UNodeList&: AddaslUseList);
829 // Process phi nodes.
830 if (allValidCandidates(SA: SN, UNodeList&: AddaslUseList) &&
831 canRemoveAddasl(AddAslSN: SN, MI, UNodeList: AddaslUseList)) {
832 SizeInc += AddaslUseList.size();
833 SizeInc -= 1; // Reduce size by 1 as addasl itself can be removed.
834 CanBeReplaced = true;
835 } else
836 SizeInc++;
837 } else
838 // Currently, only load/store and addasl are handled.
839 // Some other instructions to consider -
840 // A2_add -> A2_addi
841 // M4_mpyrr_addr -> M4_mpyrr_addi
842 KeepTfr = true;
843
844 InstrEvalResult[&MI] = CanBeReplaced;
845 HasRepInstr |= CanBeReplaced;
846 }
847
848 // Reduce total size by 2 if original tfr can be deleted.
849 if (!KeepTfr)
850 SizeInc -= 2;
851
852 return HasRepInstr;
853}
854
855bool HexagonOptAddrMode::changeLoad(MachineInstr *OldMI, MachineOperand ImmOp,
856 unsigned ImmOpNum) {
857 bool Changed = false;
858 MachineBasicBlock *BB = OldMI->getParent();
859 auto UsePos = MachineBasicBlock::iterator(OldMI);
860 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
861 ++InsertPt;
862 unsigned OpStart;
863 unsigned OpEnd = OldMI->getNumOperands();
864 MachineInstrBuilder MIB;
865
866 if (ImmOpNum == 1) {
867 if (HII->getAddrMode(MI: *OldMI) == HexagonII::BaseRegOffset) {
868 short NewOpCode = HII->changeAddrMode_rr_ur(MI: *OldMI);
869 assert(NewOpCode >= 0 && "Invalid New opcode\n");
870 MIB = BuildMI(BB&: *BB, I: InsertPt, MIMD: OldMI->getDebugLoc(), MCID: HII->get(Opcode: NewOpCode));
871 MIB.add(MO: OldMI->getOperand(i: 0));
872 MIB.add(MO: OldMI->getOperand(i: 2));
873 MIB.add(MO: OldMI->getOperand(i: 3));
874 MIB.add(MO: ImmOp);
875 OpStart = 4;
876 Changed = true;
877 } else if (HII->getAddrMode(MI: *OldMI) == HexagonII::BaseImmOffset &&
878 OldMI->getOperand(i: 2).isImm()) {
879 short NewOpCode = HII->changeAddrMode_io_abs(MI: *OldMI);
880 assert(NewOpCode >= 0 && "Invalid New opcode\n");
881 MIB = BuildMI(BB&: *BB, I: InsertPt, MIMD: OldMI->getDebugLoc(), MCID: HII->get(Opcode: NewOpCode))
882 .add(MO: OldMI->getOperand(i: 0));
883 const GlobalValue *GV = ImmOp.getGlobal();
884 int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(i: 2).getImm();
885
886 MIB.addGlobalAddress(GV, Offset, TargetFlags: ImmOp.getTargetFlags());
887 OpStart = 3;
888 Changed = true;
889 } else
890 Changed = false;
891
892 LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
893 LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
894 } else if (ImmOpNum == 2) {
895 if (OldMI->getOperand(i: 3).isImm() && OldMI->getOperand(i: 3).getImm() == 0) {
896 short NewOpCode = HII->changeAddrMode_rr_io(MI: *OldMI);
897 assert(NewOpCode >= 0 && "Invalid New opcode\n");
898 MIB = BuildMI(BB&: *BB, I: InsertPt, MIMD: OldMI->getDebugLoc(), MCID: HII->get(Opcode: NewOpCode));
899 MIB.add(MO: OldMI->getOperand(i: 0));
900 MIB.add(MO: OldMI->getOperand(i: 1));
901 MIB.add(MO: ImmOp);
902 OpStart = 4;
903 Changed = true;
904 LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
905 LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
906 }
907 }
908
909 if (Changed)
910 for (unsigned i = OpStart; i < OpEnd; ++i)
911 MIB.add(MO: OldMI->getOperand(i));
912
913 return Changed;
914}
915
916bool HexagonOptAddrMode::changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
917 unsigned ImmOpNum) {
918 bool Changed = false;
919 unsigned OpStart = 0;
920 unsigned OpEnd = OldMI->getNumOperands();
921 MachineBasicBlock *BB = OldMI->getParent();
922 auto UsePos = MachineBasicBlock::iterator(OldMI);
923 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
924 ++InsertPt;
925 MachineInstrBuilder MIB;
926 if (ImmOpNum == 0) {
927 if (HII->getAddrMode(MI: *OldMI) == HexagonII::BaseRegOffset) {
928 short NewOpCode = HII->changeAddrMode_rr_ur(MI: *OldMI);
929 assert(NewOpCode >= 0 && "Invalid New opcode\n");
930 MIB = BuildMI(BB&: *BB, I: InsertPt, MIMD: OldMI->getDebugLoc(), MCID: HII->get(Opcode: NewOpCode));
931 MIB.add(MO: OldMI->getOperand(i: 1));
932 MIB.add(MO: OldMI->getOperand(i: 2));
933 MIB.add(MO: ImmOp);
934 MIB.add(MO: OldMI->getOperand(i: 3));
935 OpStart = 4;
936 Changed = true;
937 } else if (HII->getAddrMode(MI: *OldMI) == HexagonII::BaseImmOffset) {
938 short NewOpCode = HII->changeAddrMode_io_abs(MI: *OldMI);
939 assert(NewOpCode >= 0 && "Invalid New opcode\n");
940 MIB = BuildMI(BB&: *BB, I: InsertPt, MIMD: OldMI->getDebugLoc(), MCID: HII->get(Opcode: NewOpCode));
941 const GlobalValue *GV = ImmOp.getGlobal();
942 int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(i: 1).getImm();
943 MIB.addGlobalAddress(GV, Offset, TargetFlags: ImmOp.getTargetFlags());
944 MIB.add(MO: OldMI->getOperand(i: 2));
945 OpStart = 3;
946 Changed = true;
947 }
948 } else if (ImmOpNum == 1 && OldMI->getOperand(i: 2).getImm() == 0) {
949 short NewOpCode = HII->changeAddrMode_rr_io(MI: *OldMI);
950 assert(NewOpCode >= 0 && "Invalid New opcode\n");
951 MIB = BuildMI(BB&: *BB, I: InsertPt, MIMD: OldMI->getDebugLoc(), MCID: HII->get(Opcode: NewOpCode));
952 MIB.add(MO: OldMI->getOperand(i: 0));
953 MIB.add(MO: ImmOp);
954 OpStart = 3;
955 Changed = true;
956 }
957 if (Changed) {
958 LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
959 LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
960
961 for (unsigned i = OpStart; i < OpEnd; ++i)
962 MIB.add(MO: OldMI->getOperand(i));
963 }
964
965 return Changed;
966}
967
968short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr &MI) const {
969 if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset) {
970 short TempOpCode = HII->changeAddrMode_io_rr(MI);
971 return HII->changeAddrMode_rr_ur(Opc: TempOpCode);
972 }
973 return HII->changeAddrMode_rr_ur(MI);
974}
975
976bool HexagonOptAddrMode::changeAddAsl(NodeAddr<UseNode *> AddAslUN,
977 MachineInstr *AddAslMI,
978 const MachineOperand &ImmOp,
979 unsigned ImmOpNum) {
980 NodeAddr<StmtNode *> SA = AddAslUN.Addr->getOwner(G: *DFG);
981
982 LLVM_DEBUG(dbgs() << "Processing addasl :" << *AddAslMI << "\n");
983
984 NodeList UNodeList;
985 getAllRealUses(SA, UNodeList);
986
987 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
988 NodeAddr<UseNode *> UseUN = *I;
989 assert(!(UseUN.Addr->getFlags() & NodeAttrs::PhiRef) &&
990 "Can't transform this 'AddAsl' instruction!");
991
992 NodeAddr<StmtNode *> UseIA = UseUN.Addr->getOwner(G: *DFG);
993 LLVM_DEBUG(dbgs() << "[InstrNode]: "
994 << Print<NodeAddr<InstrNode *>>(UseIA, *DFG) << "\n");
995 MachineInstr *UseMI = UseIA.Addr->getCode();
996 LLVM_DEBUG(dbgs() << "[MI <" << printMBBReference(*UseMI->getParent())
997 << ">]: " << *UseMI << "\n");
998 const MCInstrDesc &UseMID = UseMI->getDesc();
999 assert(HII->getAddrMode(*UseMI) == HexagonII::BaseImmOffset);
1000
1001 auto UsePos = MachineBasicBlock::iterator(UseMI);
1002 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
1003 short NewOpCode = getBaseWithLongOffset(MI: *UseMI);
1004 assert(NewOpCode >= 0 && "Invalid New opcode\n");
1005
1006 unsigned OpStart;
1007 unsigned OpEnd = UseMI->getNumOperands();
1008
1009 MachineBasicBlock *BB = UseMI->getParent();
1010 MachineInstrBuilder MIB =
1011 BuildMI(BB&: *BB, I: InsertPt, MIMD: UseMI->getDebugLoc(), MCID: HII->get(Opcode: NewOpCode));
1012 // change mem(Rs + # ) -> mem(Rt << # + ##)
1013 if (UseMID.mayLoad()) {
1014 MIB.add(MO: UseMI->getOperand(i: 0));
1015 MIB.add(MO: AddAslMI->getOperand(i: 2));
1016 MIB.add(MO: AddAslMI->getOperand(i: 3));
1017 const GlobalValue *GV = ImmOp.getGlobal();
1018 MIB.addGlobalAddress(GV, Offset: UseMI->getOperand(i: 2).getImm()+ImmOp.getOffset(),
1019 TargetFlags: ImmOp.getTargetFlags());
1020 OpStart = 3;
1021 } else if (UseMID.mayStore()) {
1022 MIB.add(MO: AddAslMI->getOperand(i: 2));
1023 MIB.add(MO: AddAslMI->getOperand(i: 3));
1024 const GlobalValue *GV = ImmOp.getGlobal();
1025 MIB.addGlobalAddress(GV, Offset: UseMI->getOperand(i: 1).getImm()+ImmOp.getOffset(),
1026 TargetFlags: ImmOp.getTargetFlags());
1027 MIB.add(MO: UseMI->getOperand(i: 2));
1028 OpStart = 3;
1029 } else
1030 llvm_unreachable("Unhandled instruction");
1031
1032 for (unsigned i = OpStart; i < OpEnd; ++i)
1033 MIB.add(MO: UseMI->getOperand(i));
1034 Deleted.insert(V: UseMI);
1035 }
1036
1037 return true;
1038}
1039
1040bool HexagonOptAddrMode::xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
1041 NodeAddr<UseNode *> UseN,
1042 unsigned UseMOnum) {
1043 const MachineOperand ImmOp = TfrMI->getOperand(i: 1);
1044 const MCInstrDesc &MID = UseMI->getDesc();
1045 unsigned Changed = false;
1046 if (MID.mayLoad())
1047 Changed = changeLoad(OldMI: UseMI, ImmOp, ImmOpNum: UseMOnum);
1048 else if (MID.mayStore())
1049 Changed = changeStore(OldMI: UseMI, ImmOp, ImmOpNum: UseMOnum);
1050 else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri)
1051 Changed = changeAddAsl(AddAslUN: UseN, AddAslMI: UseMI, ImmOp, ImmOpNum: UseMOnum);
1052
1053 if (Changed)
1054 Deleted.insert(V: UseMI);
1055
1056 return Changed;
1057}
1058
1059bool HexagonOptAddrMode::processBlock(NodeAddr<BlockNode *> BA) {
1060 bool Changed = false;
1061
1062 for (auto IA : BA.Addr->members(G: *DFG)) {
1063 if (!DFG->IsCode<NodeAttrs::Stmt>(BA: IA))
1064 continue;
1065
1066 NodeAddr<StmtNode *> SA = IA;
1067 MachineInstr *MI = SA.Addr->getCode();
1068 if ((MI->getOpcode() != Hexagon::A2_tfrsi ||
1069 !MI->getOperand(i: 1).isGlobal()) &&
1070 (MI->getOpcode() != Hexagon::A2_addi ||
1071 !MI->getOperand(i: 2).isImm() || HII->isConstExtended(MI: *MI)))
1072 continue;
1073
1074 LLVM_DEBUG(dbgs() << "[Analyzing " << HII->getName(MI->getOpcode())
1075 << "]: " << *MI << "\n\t[InstrNode]: "
1076 << Print<NodeAddr<InstrNode *>>(IA, *DFG) << '\n');
1077
1078 if (MI->getOpcode() == Hexagon::A2_addi)
1079 Changed |= processAddBases(AddSN: SA, AddMI: MI);
1080 NodeList UNodeList;
1081 getAllRealUses(SA, UNodeList);
1082
1083 if (!allValidCandidates(SA, UNodeList))
1084 continue;
1085
1086 // Analyze all uses of 'add'. If the output of 'add' is used as an address
1087 // in the base+immediate addressing mode load/store instructions, see if
1088 // they can be updated to use the immediate value as an offset. Thus,
1089 // providing us the opportunity to eliminate 'add'.
1090 // Ex: Rx= add(Rt,#12)
1091 // memw(Rx+#0) = Rs
1092 // This can be replaced with memw(Rt+#12) = Rs
1093 //
1094 // This transformation is only performed if all uses can be updated and
1095 // the offset isn't required to be constant extended.
1096 if (MI->getOpcode() == Hexagon::A2_addi) {
1097 Changed |= processAddUses(AddSN: SA, AddMI: MI, UNodeList);
1098 continue;
1099 }
1100
1101 short SizeInc = 0;
1102 Register DefR = MI->getOperand(i: 0).getReg();
1103 InstrEvalMap InstrEvalResult;
1104
1105 // Analyze all uses and calculate increase in size. Perform the optimization
1106 // only if there is no increase in size.
1107 if (!analyzeUses(tfrDefR: DefR, UNodeList, InstrEvalResult, SizeInc))
1108 continue;
1109 if (SizeInc > CodeGrowthLimit)
1110 continue;
1111
1112 bool KeepTfr = false;
1113
1114 LLVM_DEBUG(dbgs() << "\t[Total reached uses] : " << UNodeList.size()
1115 << "\n");
1116 LLVM_DEBUG(dbgs() << "\t[Processing Reached Uses] ===\n");
1117 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
1118 NodeAddr<UseNode *> UseN = *I;
1119 assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
1120 "Found a PhiRef node as a real reached use!!");
1121
1122 NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(G: *DFG);
1123 MachineInstr *UseMI = OwnerN.Addr->getCode();
1124 LLVM_DEBUG(dbgs() << "\t\t[MI <" << printMBBReference(*UseMI->getParent())
1125 << ">]: " << *UseMI << "\n");
1126
1127 int UseMOnum = -1;
1128 unsigned NumOperands = UseMI->getNumOperands();
1129 for (unsigned j = 0; j < NumOperands - 1; ++j) {
1130 const MachineOperand &op = UseMI->getOperand(i: j);
1131 if (op.isReg() && op.isUse() && DefR == op.getReg())
1132 UseMOnum = j;
1133 }
1134 // It is possible that the register will not be found in any operand.
1135 // This could happen, for example, when DefR = R4, but the used
1136 // register is D2.
1137
1138 // Change UseMI if replacement is possible. If any replacement failed,
1139 // or wasn't attempted, make sure to keep the TFR.
1140 bool Xformed = false;
1141 if (UseMOnum >= 0 && InstrEvalResult[UseMI])
1142 Xformed = xformUseMI(TfrMI: MI, UseMI, UseN, UseMOnum);
1143 Changed |= Xformed;
1144 KeepTfr |= !Xformed;
1145 }
1146 if (!KeepTfr)
1147 Deleted.insert(V: MI);
1148 }
1149 return Changed;
1150}
1151
1152bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
1153 if (skipFunction(F: MF.getFunction()))
1154 return false;
1155
1156 // Perform RDF optimizations only if number of basic blocks in the
1157 // function is less than the limit
1158 if (MF.size() > RDFFuncBlockLimit) {
1159 LLVM_DEBUG(dbgs() << "Skipping " << getPassName()
1160 << ": too many basic blocks\n");
1161 return false;
1162 }
1163
1164 bool Changed = false;
1165 auto &HST = MF.getSubtarget<HexagonSubtarget>();
1166 MRI = &MF.getRegInfo();
1167 TRI = MF.getSubtarget().getRegisterInfo();
1168 HII = HST.getInstrInfo();
1169 HRI = HST.getRegisterInfo();
1170 const auto &MDF = getAnalysis<MachineDominanceFrontierWrapperPass>().getMDF();
1171 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
1172
1173 DataFlowGraph G(MF, *HII, *HRI, *MDT, MDF);
1174 // Need to keep dead phis because we can propagate uses of registers into
1175 // nodes dominated by those would-be phis.
1176 G.build(config: BuildOptions::KeepDeadPhis);
1177 DFG = &G;
1178
1179 Liveness L(*MRI, *DFG);
1180 L.computePhiInfo();
1181 LV = &L;
1182
1183 Deleted.clear();
1184 ProcessedAddiInsts.clear();
1185 NodeAddr<FuncNode *> FA = DFG->getFunc();
1186 LLVM_DEBUG(dbgs() << "==== [RefMap#]=====:\n "
1187 << Print<NodeAddr<FuncNode *>>(FA, *DFG) << "\n");
1188
1189 for (NodeAddr<BlockNode *> BA : FA.Addr->members(G: *DFG))
1190 Changed |= processBlock(BA);
1191
1192 for (auto *MI : Deleted)
1193 MI->eraseFromParent();
1194
1195 if (Changed) {
1196 G.build();
1197 L.computeLiveIns();
1198 L.resetLiveIns();
1199
1200 // The RDF-based recomputation can leave stale (over-approximate) live-ins,
1201 // which later confuses passes like IfConversion into inserting incorrect
1202 // implicit-use operands. Correct them with a conventional backward
1203 // recomputation in post-order (successors before predecessors). Skip the
1204 // entry block (its calling-convention live-ins were set from the RDF
1205 // LiveMap by resetLiveIns() and can't be recovered by a backward walk) and
1206 // EH pads (exception pointer/selector are runtime-established).
1207 SmallVector<MachineBasicBlock *, 16> Candidates;
1208 for (MachineBasicBlock *MBB : post_order(G: &MF))
1209 if (!MBB->isEntryBlock() && !MBB->isEHPad())
1210 Candidates.push_back(Elt: MBB);
1211
1212 // Repeat while live-ins change (predecessors may need updating), bounded
1213 // to keep compile time in check.
1214 constexpr unsigned MaxLiveInSweeps = 8;
1215 for (unsigned Sweep = 0; Sweep != MaxLiveInSweeps; ++Sweep) {
1216 bool AnyChanged = false;
1217 for (MachineBasicBlock *MBB : Candidates)
1218 AnyChanged |= recomputeLiveIns(MBB&: *MBB);
1219 if (!AnyChanged)
1220 break;
1221 }
1222
1223 L.resetKills();
1224 }
1225
1226 return Changed;
1227}
1228
1229//===----------------------------------------------------------------------===//
1230// Public Constructor Functions
1231//===----------------------------------------------------------------------===//
1232
1233FunctionPass *llvm::createHexagonOptAddrMode() {
1234 return new HexagonOptAddrMode();
1235}
1236