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