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