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