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
43using namespace llvm;
44using namespace rdf;
45
46static 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
50namespace llvm {
51
52  FunctionPass *createHexagonOptAddrMode();
53  void initializeHexagonOptAddrModePass(PassRegistry&);
54
55} // end namespace llvm
56
57namespace {
58
59class HexagonOptAddrMode : public MachineFunctionPass {
60public:
61  static char ID;
62
63  HexagonOptAddrMode() : MachineFunctionPass(ID) {}
64
65  StringRef getPassName() const override {
66    return "Optimize addressing mode of load/store";
67  }
68
69  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
78private:
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
117char HexagonOptAddrMode::ID = 0;
118
119INITIALIZE_PASS_BEGIN(HexagonOptAddrMode, "amode-opt",
120                      "Optimize addressing mode", false, false)
121INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
122INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
123INITIALIZE_PASS_END(HexagonOptAddrMode, "amode-opt", "Optimize addressing mode",
124                    false, false)
125
126bool 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
158bool 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  Register 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
212bool 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
244void 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
284bool 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
324bool 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
348bool HexagonOptAddrMode::processAddUses(NodeAddr<StmtNode *> AddSN,
349                                        MachineInstr *AddMI,
350                                        const NodeList &UNodeList) {
351
352  Register 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    Register 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
411bool HexagonOptAddrMode::updateAddUses(MachineInstr *AddMI,
412                                        MachineInstr *UseMI) {
413  const MachineOperand ImmOp = AddMI->getOperand(2);
414  const MachineOperand AddRegOp = AddMI->getOperand(1);
415  Register 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
431bool 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
483bool 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               OldMI->getOperand(2).isImm()) {
507      short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
508      assert(NewOpCode >= 0 && "Invalid New opcode\n");
509      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode))
510                .add(OldMI->getOperand(0));
511      const GlobalValue *GV = ImmOp.getGlobal();
512      int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(2).getImm();
513
514      MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
515      OpStart = 3;
516      Changed = true;
517    } else
518      Changed = false;
519
520    LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
521    LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
522  } else if (ImmOpNum == 2) {
523    if (OldMI->getOperand(3).isImm() && OldMI->getOperand(3).getImm() == 0) {
524      short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
525      assert(NewOpCode >= 0 && "Invalid New opcode\n");
526      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
527      MIB.add(OldMI->getOperand(0));
528      MIB.add(OldMI->getOperand(1));
529      MIB.add(ImmOp);
530      OpStart = 4;
531      Changed = true;
532      LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
533      LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
534    }
535  }
536
537  if (Changed)
538    for (unsigned i = OpStart; i < OpEnd; ++i)
539      MIB.add(OldMI->getOperand(i));
540
541  return Changed;
542}
543
544bool HexagonOptAddrMode::changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
545                                     unsigned ImmOpNum) {
546  bool Changed = false;
547  unsigned OpStart = 0;
548  unsigned OpEnd = OldMI->getNumOperands();
549  MachineBasicBlock *BB = OldMI->getParent();
550  auto UsePos = MachineBasicBlock::iterator(OldMI);
551  MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
552  ++InsertPt;
553  MachineInstrBuilder MIB;
554  if (ImmOpNum == 0) {
555    if (HII->getAddrMode(*OldMI) == HexagonII::BaseRegOffset) {
556      short NewOpCode = HII->changeAddrMode_rr_ur(*OldMI);
557      assert(NewOpCode >= 0 && "Invalid New opcode\n");
558      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
559      MIB.add(OldMI->getOperand(1));
560      MIB.add(OldMI->getOperand(2));
561      MIB.add(ImmOp);
562      MIB.add(OldMI->getOperand(3));
563      OpStart = 4;
564      Changed = true;
565    } else if (HII->getAddrMode(*OldMI) == HexagonII::BaseImmOffset) {
566      short NewOpCode = HII->changeAddrMode_io_abs(*OldMI);
567      assert(NewOpCode >= 0 && "Invalid New opcode\n");
568      MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
569      const GlobalValue *GV = ImmOp.getGlobal();
570      int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(1).getImm();
571      MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
572      MIB.add(OldMI->getOperand(2));
573      OpStart = 3;
574      Changed = true;
575    }
576  } else if (ImmOpNum == 1 && OldMI->getOperand(2).getImm() == 0) {
577    short NewOpCode = HII->changeAddrMode_rr_io(*OldMI);
578    assert(NewOpCode >= 0 && "Invalid New opcode\n");
579    MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
580    MIB.add(OldMI->getOperand(0));
581    MIB.add(ImmOp);
582    OpStart = 3;
583    Changed = true;
584  }
585  if (Changed) {
586    LLVM_DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
587    LLVM_DEBUG(dbgs() << "[TO]: " << *MIB << "\n");
588
589    for (unsigned i = OpStart; i < OpEnd; ++i)
590      MIB.add(OldMI->getOperand(i));
591  }
592
593  return Changed;
594}
595
596short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr &MI) const {
597  if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset) {
598    short TempOpCode = HII->changeAddrMode_io_rr(MI);
599    return HII->changeAddrMode_rr_ur(TempOpCode);
600  }
601  return HII->changeAddrMode_rr_ur(MI);
602}
603
604bool HexagonOptAddrMode::changeAddAsl(NodeAddr<UseNode *> AddAslUN,
605                                      MachineInstr *AddAslMI,
606                                      const MachineOperand &ImmOp,
607                                      unsigned ImmOpNum) {
608  NodeAddr<StmtNode *> SA = AddAslUN.Addr->getOwner(*DFG);
609
610  LLVM_DEBUG(dbgs() << "Processing addasl :" << *AddAslMI << "\n");
611
612  NodeList UNodeList;
613  getAllRealUses(SA, UNodeList);
614
615  for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
616    NodeAddr<UseNode *> UseUN = *I;
617    assert(!(UseUN.Addr->getFlags() & NodeAttrs::PhiRef) &&
618           "Can't transform this 'AddAsl' instruction!");
619
620    NodeAddr<StmtNode *> UseIA = UseUN.Addr->getOwner(*DFG);
621    LLVM_DEBUG(dbgs() << "[InstrNode]: "
622                      << Print<NodeAddr<InstrNode *>>(UseIA, *DFG) << "\n");
623    MachineInstr *UseMI = UseIA.Addr->getCode();
624    LLVM_DEBUG(dbgs() << "[MI <" << printMBBReference(*UseMI->getParent())
625                      << ">]: " << *UseMI << "\n");
626    const MCInstrDesc &UseMID = UseMI->getDesc();
627    assert(HII->getAddrMode(*UseMI) == HexagonII::BaseImmOffset);
628
629    auto UsePos = MachineBasicBlock::iterator(UseMI);
630    MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
631    short NewOpCode = getBaseWithLongOffset(*UseMI);
632    assert(NewOpCode >= 0 && "Invalid New opcode\n");
633
634    unsigned OpStart;
635    unsigned OpEnd = UseMI->getNumOperands();
636
637    MachineBasicBlock *BB = UseMI->getParent();
638    MachineInstrBuilder MIB =
639        BuildMI(*BB, InsertPt, UseMI->getDebugLoc(), HII->get(NewOpCode));
640    // change mem(Rs + # ) -> mem(Rt << # + ##)
641    if (UseMID.mayLoad()) {
642      MIB.add(UseMI->getOperand(0));
643      MIB.add(AddAslMI->getOperand(2));
644      MIB.add(AddAslMI->getOperand(3));
645      const GlobalValue *GV = ImmOp.getGlobal();
646      MIB.addGlobalAddress(GV, UseMI->getOperand(2).getImm()+ImmOp.getOffset(),
647                           ImmOp.getTargetFlags());
648      OpStart = 3;
649    } else if (UseMID.mayStore()) {
650      MIB.add(AddAslMI->getOperand(2));
651      MIB.add(AddAslMI->getOperand(3));
652      const GlobalValue *GV = ImmOp.getGlobal();
653      MIB.addGlobalAddress(GV, UseMI->getOperand(1).getImm()+ImmOp.getOffset(),
654                           ImmOp.getTargetFlags());
655      MIB.add(UseMI->getOperand(2));
656      OpStart = 3;
657    } else
658      llvm_unreachable("Unhandled instruction");
659
660    for (unsigned i = OpStart; i < OpEnd; ++i)
661      MIB.add(UseMI->getOperand(i));
662
663    Deleted.insert(UseMI);
664  }
665
666  return true;
667}
668
669bool HexagonOptAddrMode::xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
670                                    NodeAddr<UseNode *> UseN,
671                                    unsigned UseMOnum) {
672  const MachineOperand ImmOp = TfrMI->getOperand(1);
673  const MCInstrDesc &MID = UseMI->getDesc();
674  unsigned Changed = false;
675  if (MID.mayLoad())
676    Changed = changeLoad(UseMI, ImmOp, UseMOnum);
677  else if (MID.mayStore())
678    Changed = changeStore(UseMI, ImmOp, UseMOnum);
679  else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri)
680    Changed = changeAddAsl(UseN, UseMI, ImmOp, UseMOnum);
681
682  if (Changed)
683    Deleted.insert(UseMI);
684
685  return Changed;
686}
687
688bool HexagonOptAddrMode::processBlock(NodeAddr<BlockNode *> BA) {
689  bool Changed = false;
690
691  for (auto IA : BA.Addr->members(*DFG)) {
692    if (!DFG->IsCode<NodeAttrs::Stmt>(IA))
693      continue;
694
695    NodeAddr<StmtNode *> SA = IA;
696    MachineInstr *MI = SA.Addr->getCode();
697    if ((MI->getOpcode() != Hexagon::A2_tfrsi ||
698         !MI->getOperand(1).isGlobal()) &&
699        (MI->getOpcode() != Hexagon::A2_addi ||
700         !MI->getOperand(2).isImm() || HII->isConstExtended(*MI)))
701    continue;
702
703    LLVM_DEBUG(dbgs() << "[Analyzing " << HII->getName(MI->getOpcode())
704                      << "]: " << *MI << "\n\t[InstrNode]: "
705                      << Print<NodeAddr<InstrNode *>>(IA, *DFG) << '\n');
706
707    NodeList UNodeList;
708    getAllRealUses(SA, UNodeList);
709
710    if (!allValidCandidates(SA, UNodeList))
711      continue;
712
713    // Analyze all uses of 'add'. If the output of 'add' is used as an address
714    // in the base+immediate addressing mode load/store instructions, see if
715    // they can be updated to use the immediate value as an offet. Thus,
716    // providing us the opportunity to eliminate 'add'.
717    // Ex: Rx= add(Rt,#12)
718    //     memw(Rx+#0) = Rs
719    // This can be replaced with memw(Rt+#12) = Rs
720    //
721    // This transformation is only performed if all uses can be updated and
722    // the offset isn't required to be constant extended.
723    if (MI->getOpcode() == Hexagon::A2_addi) {
724      Changed |= processAddUses(SA, MI, UNodeList);
725      continue;
726    }
727
728    short SizeInc = 0;
729    Register DefR = MI->getOperand(0).getReg();
730    InstrEvalMap InstrEvalResult;
731
732    // Analyze all uses and calculate increase in size. Perform the optimization
733    // only if there is no increase in size.
734    if (!analyzeUses(DefR, UNodeList, InstrEvalResult, SizeInc))
735      continue;
736    if (SizeInc > CodeGrowthLimit)
737      continue;
738
739    bool KeepTfr = false;
740
741    LLVM_DEBUG(dbgs() << "\t[Total reached uses] : " << UNodeList.size()
742                      << "\n");
743    LLVM_DEBUG(dbgs() << "\t[Processing Reached Uses] ===\n");
744    for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
745      NodeAddr<UseNode *> UseN = *I;
746      assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
747             "Found a PhiRef node as a real reached use!!");
748
749      NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
750      MachineInstr *UseMI = OwnerN.Addr->getCode();
751      LLVM_DEBUG(dbgs() << "\t\t[MI <" << printMBBReference(*UseMI->getParent())
752                        << ">]: " << *UseMI << "\n");
753
754      int UseMOnum = -1;
755      unsigned NumOperands = UseMI->getNumOperands();
756      for (unsigned j = 0; j < NumOperands - 1; ++j) {
757        const MachineOperand &op = UseMI->getOperand(j);
758        if (op.isReg() && op.isUse() && DefR == op.getReg())
759          UseMOnum = j;
760      }
761      // It is possible that the register will not be found in any operand.
762      // This could happen, for example, when DefR = R4, but the used
763      // register is D2.
764
765      // Change UseMI if replacement is possible. If any replacement failed,
766      // or wasn't attempted, make sure to keep the TFR.
767      bool Xformed = false;
768      if (UseMOnum >= 0 && InstrEvalResult[UseMI])
769        Xformed = xformUseMI(MI, UseMI, UseN, UseMOnum);
770      Changed |=  Xformed;
771      KeepTfr |= !Xformed;
772    }
773    if (!KeepTfr)
774      Deleted.insert(MI);
775  }
776  return Changed;
777}
778
779bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
780  if (skipFunction(MF.getFunction()))
781    return false;
782
783  bool Changed = false;
784  auto &HST = MF.getSubtarget<HexagonSubtarget>();
785  MRI = &MF.getRegInfo();
786  HII = HST.getInstrInfo();
787  HRI = HST.getRegisterInfo();
788  const auto &MDF = getAnalysis<MachineDominanceFrontier>();
789  MDT = &getAnalysis<MachineDominatorTree>();
790  const TargetOperandInfo TOI(*HII);
791
792  DataFlowGraph G(MF, *HII, *HRI, *MDT, MDF, TOI);
793  // Need to keep dead phis because we can propagate uses of registers into
794  // nodes dominated by those would-be phis.
795  G.build(BuildOptions::KeepDeadPhis);
796  DFG = &G;
797
798  Liveness L(*MRI, *DFG);
799  L.computePhiInfo();
800  LV = &L;
801
802  Deleted.clear();
803  NodeAddr<FuncNode *> FA = DFG->getFunc();
804  LLVM_DEBUG(dbgs() << "==== [RefMap#]=====:\n "
805                    << Print<NodeAddr<FuncNode *>>(FA, *DFG) << "\n");
806
807  for (NodeAddr<BlockNode *> BA : FA.Addr->members(*DFG))
808    Changed |= processBlock(BA);
809
810  for (auto MI : Deleted)
811    MI->eraseFromParent();
812
813  if (Changed) {
814    G.build();
815    L.computeLiveIns();
816    L.resetLiveIns();
817    L.resetKills();
818  }
819
820  return Changed;
821}
822
823//===----------------------------------------------------------------------===//
824//                         Public Constructor Functions
825//===----------------------------------------------------------------------===//
826
827FunctionPass *llvm::createHexagonOptAddrMode() {
828  return new HexagonOptAddrMode();
829}
830