LLVM 24.0.0git
HexagonOptAddrMode.cpp
Go to the documentation of this file.
1//===- HexagonOptAddrMode.cpp ---------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8// This implements a Hexagon-specific pass to optimize addressing mode for
9// load/store instructions.
10//===----------------------------------------------------------------------===//
11
12#include "Hexagon.h"
13#include "HexagonInstrInfo.h"
14#include "HexagonSubtarget.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/DenseSet.h"
19#include "llvm/ADT/StringRef.h"
35#include "llvm/MC/MCInstrDesc.h"
36#include "llvm/Pass.h"
38#include "llvm/Support/Debug.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(0), cl::desc("Code growth limit for address mode "
51 "optimization"));
52
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 {
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)
133INITIALIZE_PASS_END(HexagonOptAddrMode, "amode-opt", "Optimize addressing mode",
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(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,
170 const NodeList &UNodeList) {
171 // check offset size in addasl. if 'offset > 3' return false
172 const MachineOperand &OffsetOp = MI.getOperand(3);
173 if (!OffsetOp.isImm() || OffsetOp.getImm() > 3)
174 return false;
175
176 Register OffsetReg = MI.getOperand(2).getReg();
177 RegisterRef OffsetRR;
178 NodeId OffsetRegRD = 0;
179 for (NodeAddr<UseNode *> UA : AddAslSN.Addr->members_if(DFG->IsUse, *DFG)) {
180 RegisterRef RR = UA.Addr->getRegRef(*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(*DFG);
190 if (UA.Addr->getFlags() & NodeAttrs::PhiRef)
191 return false;
192 NodeAddr<RefNode*> AA = LV->getNearestAliasedRef(OffsetRR, IA);
193 if ((DFG->IsDef(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 *>(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()) ||
207 getBaseWithLongOffset(UseMI) < 0)
208 return false;
209
210 // Addasl output can't be a store value.
211 if (UseMID.mayStore() && UseMI.getOperand(2).isReg() &&
212 UseMI.getOperand(2).getReg() == MI.getOperand(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(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(*DFG);
236 NodeSet Visited, Defs;
237 const auto &P = LV->getAllReachingDefsRec(UR, 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(DFG->IsDef, *DFG)) {
266 LLVM_DEBUG(dbgs() << "\t\t[DefNode]: "
267 << Print<NodeAddr<DefNode *>>(DA, *DFG) << "\n");
268 RegisterRef DR = DA.Addr->getRegRef(*DFG);
269
270 auto UseSet = LV->getAllReachedUses(DR, DA);
271
272 for (auto UI : UseSet) {
273 NodeAddr<UseNode *> UA = DFG->addr<UseNode *>(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(*DFG);
282 NodeId id = PA.Id;
283 const Liveness::RefMap &phiUse = LV->getRealUses(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(RegisterRef(I.first), DR))
289 continue;
290 auto phiUseSet = I.second;
291 for (auto phiUI : phiUseSet) {
292 NodeAddr<UseNode *> phiUA = DFG->addr<UseNode *>(phiUI.first);
293 UNodeList.push_back(phiUA);
294 }
295 }
296 }
297 } else
298 UNodeList.push_back(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(DFG->IsUse, *DFG)) {
311 RegisterRef RR = UA.Addr->getRegRef(*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(*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(LRExtRR, IA);
326 if ((DFG->IsDef(AA) && AA.Id != LRExtRegRD) ||
327 AA.Addr->getReachingDef() != LRExtRegRD) {
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 *>(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(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)) {
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(MI->getOpcode(), Offset, false);
369 default:
371 // The immediates are mentioned in multiples of vector counts
372 unsigned AlignMask = HII->getMemAccessSize(*MI) - 1;
373 if ((AlignMask & Offset) == 0)
374 return HII->isValidOffset(MI->getOpcode(), Offset, false);
375 }
376 return false;
377 }
378 }
379
381 return false;
382
383 unsigned AlignMask = 0;
384 switch (HII->getMemAccessSize(*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(MI->getOpcode(), Offset, 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(
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(CurrentInstSN, LoadStoreUseList);
451 bool FoundLoadStoreUse = false;
452 for (NodeAddr<UseNode *> UN : LoadStoreUseList) {
453 NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
454 MachineInstr *LoadStoreMI = SN.Addr->getCode();
455 const MCInstrDesc &MID = LoadStoreMI->getDesc();
456 if ((MID.mayLoad() || MID.mayStore()) &&
457 isValidOffset(LoadStoreMI, 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(AddiList, [&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(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(AddMI);
544
545 // Get the base register that would be shared by other Addi Instructions
546 Register BaseReg = AddMI->getOperand(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(DFG->IsUse, *DFG)) {
555 RegisterRef URR = UA.Addr->getRegRef(*DFG);
556 if (BaseReg != URR.asMCReg())
557 continue;
558
559 UAReachingDefID = UA.Addr->getReachingDef();
560 NodeAddr<DefNode *> UADef = DFG->addr<DefNode *>(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 *>(UAReachingDefID);
568 NodeAddr<StmtNode *> ReachingDefStmt = UAReachingDef.Addr->getOwner(*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(*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(ReachingDefStmt, AddiUseList);
581 for (NodeAddr<UseNode *> UN : AddiUseList) {
582 NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*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({SN, UN});
589
590 // This ensures that we process each instruction only once
591 ProcessedAddiInsts.insert(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, 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(DFG->IsDef, *DFG).front();
609
610 MachineInstr *FirstReachedMI = FirstReachedUseSN.Addr->getCode();
611 const MachineOperand FirstReachedMIImmOp = FirstReachedMI->getOperand(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(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(*DFG);
652 NodeAddr<InstrNode *> CurrentAddiIN = CurrentInstUN.Addr->getOwner(*DFG);
653 NodeAddr<RefNode *> NearestAA =
654 LV->getNearestAliasedRef(FirstReachedDefRR, CurrentAddiIN);
655 if ((DFG->IsDef(NearestAA) && NearestAA.Id != FirstReachedUseDN.Id) ||
656 (!DFG->IsDef(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(1);
665 if (CurrentMIBaseOp.getReg() != FirstReachedMI->getOperand(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(CurrentInstUN.Id, 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(0);
685 Register FirstDefRegister = FirstReachedDef.getReg();
686
687 MachineOperand &CurrentMIBaseOp = CurrentMI->getOperand(1);
688 MachineOperand &CurrentMIImmOp = CurrentMI->getOperand(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(FirstDefRegister, TRI);
705
706 ProcessedAddiInsts.insert(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(0).getReg();
715 Register BaseReg = AddMI->getOperand(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(*DFG);
719 MachineInstr *MI = SN.Addr->getCode();
720 const MCInstrDesc &MID = MI->getDesc();
721 if ((!MID.mayLoad() && !MID.mayStore()) ||
723 return false;
724
725 MachineOperand BaseOp = MI->getOperand(getBaseOpPosition(MI));
726
727 if (!BaseOp.isReg() || BaseOp.getReg() != AddDefR)
728 return false;
729
730 MachineOperand OffsetOp = MI->getOperand(getOffsetOpPosition(MI));
731 if (!OffsetOp.isImm())
732 return false;
733
734 int64_t newOffset = OffsetOp.getImm() + AddMI->getOperand(2).getImm();
735 if (!isValidOffset(MI, 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(AddSN, AddMI, 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(DFG->IsUse, *DFG)) {
755 RegisterRef RR = UA.Addr->getRegRef(*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(*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 *>(LRExtRegRD);
778 UseN.Addr->linkToDef(UseN.Id, LRExtRegDN);
779 }
780
781 if (Changed)
782 Deleted.insert(AddMI);
783
784 return Changed;
785}
786
787bool HexagonOptAddrMode::updateAddUses(MachineInstr *AddMI,
788 MachineInstr *UseMI) {
789 const MachineOperand ImmOp = AddMI->getOperand(2);
790 const MachineOperand AddRegOp = AddMI->getOperand(1);
791 Register NewReg = AddRegOp.getReg();
792
793 MachineOperand &BaseOp = UseMI->getOperand(getBaseOpPosition(UseMI));
794 MachineOperand &OffsetOp = UseMI->getOperand(getOffsetOpPosition(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(*DFG);
815 MachineInstr &MI = *SN.Addr->getCode();
816 const MCInstrDesc &MID = MI.getDesc();
817 if ((MID.mayLoad() || MID.mayStore())) {
818 if (!hasRepForm(MI, 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(SN, AddaslUseList);
829 // Process phi nodes.
830 if (allValidCandidates(SN, AddaslUseList) &&
831 canRemoveAddasl(SN, MI, 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(*OldMI) == HexagonII::BaseRegOffset) {
868 short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
869 assert(NewOpCode >= 0 && "Invalid New opcode\n");
870 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
871 MIB.add(OldMI->getOperand(0));
872 MIB.add(OldMI->getOperand(2));
873 MIB.add(OldMI->getOperand(3));
874 MIB.add(ImmOp);
875 OpStart = 4;
876 Changed = true;
877 } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset &&
878 OldMI->getOperand(2).isImm()) {
879 short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
880 assert(NewOpCode >= 0 && "Invalid New opcode\n");
881 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode))
882 .add(OldMI->getOperand(0));
883 const GlobalValue *GV = ImmOp.getGlobal();
884 int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(2).getImm();
885
886 MIB.addGlobalAddress(GV, Offset, 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(3).isImm() && OldMI->getOperand(3).getImm() == 0) {
896 short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
897 assert(NewOpCode >= 0 && "Invalid New opcode\n");
898 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
899 MIB.add(OldMI->getOperand(0));
900 MIB.add(OldMI->getOperand(1));
901 MIB.add(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(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(*OldMI) == HexagonII::BaseRegOffset) {
928 short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
929 assert(NewOpCode >= 0 && "Invalid New opcode\n");
930 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
931 MIB.add(OldMI->getOperand(1));
932 MIB.add(OldMI->getOperand(2));
933 MIB.add(ImmOp);
934 MIB.add(OldMI->getOperand(3));
935 OpStart = 4;
936 Changed = true;
937 } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset) {
938 short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
939 assert(NewOpCode >= 0 && "Invalid New opcode\n");
940 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
941 const GlobalValue *GV = ImmOp.getGlobal();
942 int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(1).getImm();
943 MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
944 MIB.add(OldMI->getOperand(2));
945 OpStart = 3;
946 Changed = true;
947 }
948 } else if (ImmOpNum == 1 && OldMI->getOperand(2).getImm() == 0) {
949 short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
950 assert(NewOpCode >= 0 && "Invalid New opcode\n");
951 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
952 MIB.add(OldMI->getOperand(0));
953 MIB.add(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(OldMI->getOperand(i));
963 }
964
965 return Changed;
966}
967
968short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr &MI) const {
970 short TempOpCode = HII->changeAddrMode_io_rr(MI);
971 return HII->changeAddrMode_rr_ur(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(*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(*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();
1000
1001 auto UsePos = MachineBasicBlock::iterator(UseMI);
1002 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
1003 short NewOpCode = getBaseWithLongOffset(*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, InsertPt, UseMI->getDebugLoc(), HII->get(NewOpCode));
1012 // change mem(Rs + # ) -> mem(Rt << # + ##)
1013 if (UseMID.mayLoad()) {
1014 MIB.add(UseMI->getOperand(0));
1015 MIB.add(AddAslMI->getOperand(2));
1016 MIB.add(AddAslMI->getOperand(3));
1017 const GlobalValue *GV = ImmOp.getGlobal();
1018 MIB.addGlobalAddress(GV, UseMI->getOperand(2).getImm()+ImmOp.getOffset(),
1019 ImmOp.getTargetFlags());
1020 OpStart = 3;
1021 } else if (UseMID.mayStore()) {
1022 MIB.add(AddAslMI->getOperand(2));
1023 MIB.add(AddAslMI->getOperand(3));
1024 const GlobalValue *GV = ImmOp.getGlobal();
1025 MIB.addGlobalAddress(GV, UseMI->getOperand(1).getImm()+ImmOp.getOffset(),
1026 ImmOp.getTargetFlags());
1027 MIB.add(UseMI->getOperand(2));
1028 OpStart = 3;
1029 } else
1030 llvm_unreachable("Unhandled instruction");
1031
1032 for (unsigned i = OpStart; i < OpEnd; ++i)
1033 MIB.add(UseMI->getOperand(i));
1034 Deleted.insert(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(1);
1044 const MCInstrDesc &MID = UseMI->getDesc();
1045 unsigned Changed = false;
1046 if (MID.mayLoad())
1047 Changed = changeLoad(UseMI, ImmOp, UseMOnum);
1048 else if (MID.mayStore())
1049 Changed = changeStore(UseMI, ImmOp, UseMOnum);
1050 else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri)
1051 Changed = changeAddAsl(UseN, UseMI, ImmOp, UseMOnum);
1052
1053 if (Changed)
1054 Deleted.insert(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(*DFG)) {
1063 if (!DFG->IsCode<NodeAttrs::Stmt>(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(1).isGlobal()) &&
1070 (MI->getOpcode() != Hexagon::A2_addi ||
1071 !MI->getOperand(2).isImm() || HII->isConstExtended(*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(SA, 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(SA, MI, UNodeList);
1098 continue;
1099 }
1100
1101 short SizeInc = 0;
1102 Register DefR = MI->getOperand(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(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(*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(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(MI, UseMI, UseN, UseMOnum);
1143 Changed |= Xformed;
1144 KeepTfr |= !Xformed;
1145 }
1146 if (!KeepTfr)
1147 Deleted.insert(MI);
1148 }
1149 return Changed;
1150}
1151
1152bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
1153 if (skipFunction(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();
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.
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(*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).
1208 for (MachineBasicBlock *MBB : post_order(&MF))
1209 if (!MBB->isEntryBlock() && !MBB->isEHPad())
1210 Candidates.push_back(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);
1219 if (!AnyChanged)
1220 break;
1221 }
1222
1223 L.resetKills();
1224 }
1225
1226 return Changed;
1227}
1228
1229//===----------------------------------------------------------------------===//
1230// Public Constructor Functions
1231//===----------------------------------------------------------------------===//
1232
1234 return new HexagonOptAddrMode();
1235}
MachineInstrBuilder & UseMI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock & MBB
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
#define op(i)
static cl::opt< int > CodeGrowthLimit("hexagon-amode-growth-limit", cl::Hidden, cl::init(0), cl::desc("Code growth limit for address mode " "optimization"))
cl::opt< unsigned > RDFFuncBlockLimit
static void getAllRealUses(NodeAddr< DefNode * > DA, NodeSet &UNodeSet, Liveness *L, DataFlowGraph *G, bool comprehensive=false)
IRTranslator LLVM IR MI
std::pair< Instruction::BinaryOps, Value * > OffsetOp
Find all possible pairs (BinOp, RHS) that BinOp V, RHS can be simplified.
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
#define I(x, y, z)
Definition MD5.cpp:57
#define G(x, y, z)
Definition MD5.cpp:55
Register const TargetRegisterInfo * TRI
Promote Memory to Register
Definition Mem2Reg.cpp:110
#define P(N)
if(PassOpts->AAPipeline)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
MachineRegisterInfo & MRI
#define LLVM_DEBUG(...)
Definition Debug.h:119
static bool processBlock(MachineBasicBlock &MBB, const SystemZInstrInfo *TII, const TargetRegisterInfo *TRI)
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
bool empty() const
Definition DenseMap.h:716
FunctionPass class - This class is used to implement most global optimizations.
Definition Pass.h:312
bool isPredicated(const MachineInstr &MI) const override
Returns true if the instruction is already predicated.
unsigned getAddrMode(const MachineInstr &MI) const
bool isConstExtended(const MachineInstr &MI) const
short changeAddrMode_rr_ur(short Opc) const
unsigned getMemAccessSize(const MachineInstr &MI) const
short changeAddrMode_io_abs(short Opc) const
short changeAddrMode_rr_io(short Opc) const
bool isHVXVec(const MachineInstr &MI) const
short changeAddrMode_io_rr(short Opc) const
bool isValidOffset(unsigned Opcode, int Offset, bool Extend=true) const
Describe properties that are true of each instruction in the target description file.
bool mayStore() const
Return true if this instruction could possibly modify memory.
bool mayLoad() const
Return true if this instruction could possibly read memory.
bool isEHPad() const
Returns true if the block is a landing pad.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
LLVM_ABI bool isEntryBlock() const
Returns true if this is the entry block of the function.
Instructions::iterator instr_iterator
MachineInstrBundleIterator< MachineInstr > iterator
LLVM_ABI StringRef getName() const
Return the name of the corresponding LLVM basic block, or an empty string.
LLVM_ABI bool isLiveIn(MCRegister Reg, LaneBitmask LaneMask=LaneBitmask::getAll()) const
Return true if the specified register is in the live in set.
Analysis pass which computes a MachineDominatorTree.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
Register getReg(unsigned Idx) const
Get the register for the operand index.
const MachineInstrBuilder & add(const MachineOperand &MO) const
const MachineInstrBuilder & addGlobalAddress(const GlobalValue *GV, int64_t Offset=0, unsigned TargetFlags=0) const
Representation of each machine instruction.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
const MachineBasicBlock * getParent() const
unsigned getNumOperands() const
Retuns the total number of operands.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
const DebugLoc & getDebugLoc() const
Returns the debug location id of this MachineInstr.
const MachineOperand & getOperand(unsigned i) const
const GlobalValue * getGlobal() const
void setImplicit(bool Val=true)
void setImm(int64_t immVal)
int64_t getImm() const
bool isReg() const
isReg - Tests if this is a MO_Register operand.
LLVM_ABI void setReg(Register Reg)
Change the register this operand corresponds to.
bool isImm() const
isImm - Tests if this is a MO_Immediate operand.
unsigned getTargetFlags() const
void setIsUndef(bool Val=true)
Register getReg() const
getReg - Returns the register number.
int64_t getOffset() const
Return the offset from the symbol in this operand.
void push_back(const T &Elt)
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
std::pair< iterator, bool > insert(const ValueT &V)
Definition DenseSet.h:210
bool contains(const_arg_type_t< ValueT > V) const
Check if the set contains the given element.
Definition DenseSet.h:183
self_iterator getIterator()
Definition ilist_node.h:123
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
initializer< Ty > init(const Ty &Val)
Print(const T &, const DataFlowGraph &) -> Print< T >
uint32_t NodeId
Definition RDFGraph.h:262
std::set< NodeId > NodeSet
Definition RDFGraph.h:551
SmallVector< Node, 4 > NodeList
Definition RDFGraph.h:550
BaseReg
Stack frame base register. Bit 0 of FREInfo.Info.
Definition SFrame.h:77
This is an optimization pass for GlobalISel generic memory operations.
@ Offset
Definition DWP.cpp:577
MachineInstrBuilder BuildMI(MachineFunction &MF, const MIMetadata &MIMD, const MCInstrDesc &MCID)
Builder interface. Specify how to create the initial instruction itself.
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
auto post_order(const T &G)
Post-order traversal of a graph.
FunctionPass * createHexagonOptAddrMode()
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Definition STLExtras.h:1788
LLVM_ABI Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
LLVM_ABI Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
static bool recomputeLiveIns(MachineBasicBlock &MBB)
Convenience function for recomputing live-in's for a MBB.
static bool IsDef(const Node BA)
Definition RDFGraph.h:827
static bool IsUse(const Node BA)
Definition RDFGraph.h:832
const PhysicalRegisterInfo & getPRI() const
Definition RDFGraph.h:700
static bool IsCode(const Node BA)
Definition RDFGraph.h:823
NodeAddr< T > addr(NodeId N) const
Definition RDFGraph.h:692
const RefMap & getRealUses(NodeId P) const
Definition RDFLiveness.h:97
LLVM_ABI NodeAddr< RefNode * > getNearestAliasedRef(RegisterRef RefRR, NodeAddr< InstrNode * > IA)
Find the nearest ref node aliased to RefRR, going upwards in the data flow, starting from the instruc...
DenseMap< RegisterId, NodeRefSet > RefMap
Definition RDFLiveness.h:59
LLVM_ABI std::pair< NodeSet, bool > getAllReachingDefsRec(RegisterRef RefRR, NodeAddr< RefNode * > RefA, NodeSet &Visited, const NodeSet &Defs)
LLVM_ABI NodeSet getAllReachedUses(RegisterRef RefRR, NodeAddr< DefNode * > DefA, const RegisterAggr &DefRRs)
LLVM_ABI bool alias(RegisterRef RA, RegisterRef RB) const
constexpr MCRegister asMCReg() const