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