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 #define DEBUG_TYPE "opt-addr-mode"
14
15 #include "HexagonTargetMachine.h"
16 #include "RDFGraph.h"
17 #include "RDFLiveness.h"
18
19 #include "llvm/ADT/DenseSet.h"
20 #include "llvm/CodeGen/MachineBasicBlock.h"
21 #include "llvm/CodeGen/MachineDominanceFrontier.h"
22 #include "llvm/CodeGen/MachineDominators.h"
23 #include "llvm/CodeGen/MachineFunction.h"
24 #include "llvm/CodeGen/MachineInstrBuilder.h"
25 #include "llvm/CodeGen/MachineRegisterInfo.h"
26 #include "llvm/CodeGen/Passes.h"
27 #include "llvm/Support/CommandLine.h"
28 #include "llvm/Support/Debug.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include "llvm/Target/TargetInstrInfo.h"
31 #include "llvm/Target/TargetMachine.h"
32 #include "llvm/Target/TargetRegisterInfo.h"
33
34 static cl::opt<int> CodeGrowthLimit("hexagon-amode-growth-limit",
35 cl::Hidden, cl::init(0), cl::desc("Code growth limit for address mode "
36 "optimization"));
37
38 using namespace llvm;
39 using namespace rdf;
40
41 namespace llvm {
42 FunctionPass *createHexagonOptAddrMode();
43 void initializeHexagonOptAddrModePass(PassRegistry &);
44 }
45
46 namespace {
47 class HexagonOptAddrMode : public MachineFunctionPass {
48 public:
49 static char ID;
HexagonOptAddrMode()50 HexagonOptAddrMode()
51 : MachineFunctionPass(ID), HII(0), MDT(0), DFG(0), LV(0) {
52 PassRegistry &R = *PassRegistry::getPassRegistry();
53 initializeHexagonOptAddrModePass(R);
54 }
getPassName() const55 const char *getPassName() const override {
56 return "Optimize addressing mode of load/store";
57 }
getAnalysisUsage(AnalysisUsage & AU) const58 void getAnalysisUsage(AnalysisUsage &AU) const override {
59 MachineFunctionPass::getAnalysisUsage(AU);
60 AU.addRequired<MachineDominatorTree>();
61 AU.addRequired<MachineDominanceFrontier>();
62 AU.setPreservesAll();
63 }
64 bool runOnMachineFunction(MachineFunction &MF) override;
65
66 private:
67 typedef DenseSet<MachineInstr *> MISetType;
68 typedef DenseMap<MachineInstr *, bool> InstrEvalMap;
69 const HexagonInstrInfo *HII;
70 MachineDominatorTree *MDT;
71 DataFlowGraph *DFG;
72 DataFlowGraph::DefStackMap DefM;
73 std::map<RegisterRef, std::map<NodeId, NodeId>> RDefMap;
74 Liveness *LV;
75 MISetType Deleted;
76
77 bool processBlock(NodeAddr<BlockNode *> BA);
78 bool xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
79 NodeAddr<UseNode *> UseN, unsigned UseMOnum);
80 bool analyzeUses(unsigned DefR, const NodeList &UNodeList,
81 InstrEvalMap &InstrEvalResult, short &SizeInc);
82 bool hasRepForm(MachineInstr *MI, unsigned TfrDefR);
83 bool canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN, MachineInstr *MI,
84 const NodeList &UNodeList);
85 void getAllRealUses(NodeAddr<StmtNode *> SN, NodeList &UNodeList);
86 bool allValidCandidates(NodeAddr<StmtNode *> SA, NodeList &UNodeList);
87 short getBaseWithLongOffset(const MachineInstr *MI) const;
88 void updateMap(NodeAddr<InstrNode *> IA);
89 bool constructDefMap(MachineBasicBlock *B);
90 bool changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
91 unsigned ImmOpNum);
92 bool changeLoad(MachineInstr *OldMI, MachineOperand ImmOp, unsigned ImmOpNum);
93 bool changeAddAsl(NodeAddr<UseNode *> AddAslUN, MachineInstr *AddAslMI,
94 const MachineOperand &ImmOp, unsigned ImmOpNum);
95 };
96 }
97
98 char HexagonOptAddrMode::ID = 0;
99
100 INITIALIZE_PASS_BEGIN(HexagonOptAddrMode, "opt-amode",
101 "Optimize addressing mode", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)102 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
103 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
104 INITIALIZE_PASS_END(HexagonOptAddrMode, "opt-amode", "Optimize addressing mode",
105 false, false)
106
107 bool HexagonOptAddrMode::hasRepForm(MachineInstr *MI, unsigned TfrDefR) {
108 const MCInstrDesc &MID = MI->getDesc();
109
110 if ((!MID.mayStore() && !MID.mayLoad()) || HII->isPredicated(*MI))
111 return false;
112
113 if (MID.mayStore()) {
114 MachineOperand StOp = MI->getOperand(MI->getNumOperands() - 1);
115 if (StOp.isReg() && StOp.getReg() == TfrDefR)
116 return false;
117 }
118
119 if (HII->getAddrMode(MI) == HexagonII::BaseRegOffset)
120 // Tranform to Absolute plus register offset.
121 return (HII->getBaseWithLongOffset(MI) >= 0);
122 else if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset)
123 // Tranform to absolute addressing mode.
124 return (HII->getAbsoluteForm(MI) >= 0);
125
126 return false;
127 }
128
129 // Check if addasl instruction can be removed. This is possible only
130 // if it's feeding to only load/store instructions with base + register
131 // offset as these instruction can be tranformed to use 'absolute plus
132 // shifted register offset'.
133 // ex:
134 // Rs = ##foo
135 // Rx = addasl(Rs, Rt, #2)
136 // Rd = memw(Rx + #28)
137 // Above three instructions can be replaced with Rd = memw(Rt<<#2 + ##foo+28)
138
canRemoveAddasl(NodeAddr<StmtNode * > AddAslSN,MachineInstr * MI,const NodeList & UNodeList)139 bool HexagonOptAddrMode::canRemoveAddasl(NodeAddr<StmtNode *> AddAslSN,
140 MachineInstr *MI,
141 const NodeList &UNodeList) {
142 // check offset size in addasl. if 'offset > 3' return false
143 const MachineOperand &OffsetOp = MI->getOperand(3);
144 if (!OffsetOp.isImm() || OffsetOp.getImm() > 3)
145 return false;
146
147 unsigned OffsetReg = MI->getOperand(2).getReg();
148 RegisterRef OffsetRR;
149 NodeId OffsetRegRD = 0;
150 for (NodeAddr<UseNode *> UA : AddAslSN.Addr->members_if(DFG->IsUse, *DFG)) {
151 RegisterRef RR = UA.Addr->getRegRef();
152 if (OffsetReg == RR.Reg) {
153 OffsetRR = RR;
154 OffsetRegRD = UA.Addr->getReachingDef();
155 }
156 }
157
158 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
159 NodeAddr<UseNode *> UA = *I;
160 NodeAddr<InstrNode *> IA = UA.Addr->getOwner(*DFG);
161 if ((UA.Addr->getFlags() & NodeAttrs::PhiRef) ||
162 RDefMap[OffsetRR][IA.Id] != OffsetRegRD)
163 return false;
164
165 MachineInstr *UseMI = NodeAddr<StmtNode *>(IA).Addr->getCode();
166 NodeAddr<DefNode *> OffsetRegDN = DFG->addr<DefNode *>(OffsetRegRD);
167 // Reaching Def to an offset register can't be a phi.
168 if ((OffsetRegDN.Addr->getFlags() & NodeAttrs::PhiRef) &&
169 MI->getParent() != UseMI->getParent())
170 return false;
171
172 const MCInstrDesc &UseMID = UseMI->getDesc();
173 if ((!UseMID.mayLoad() && !UseMID.mayStore()) ||
174 HII->getAddrMode(UseMI) != HexagonII::BaseImmOffset ||
175 getBaseWithLongOffset(UseMI) < 0)
176 return false;
177
178 // Addasl output can't be a store value.
179 if (UseMID.mayStore() && UseMI->getOperand(2).isReg() &&
180 UseMI->getOperand(2).getReg() == MI->getOperand(0).getReg())
181 return false;
182
183 for (auto &Mo : UseMI->operands())
184 if (Mo.isFI())
185 return false;
186 }
187 return true;
188 }
189
allValidCandidates(NodeAddr<StmtNode * > SA,NodeList & UNodeList)190 bool HexagonOptAddrMode::allValidCandidates(NodeAddr<StmtNode *> SA,
191 NodeList &UNodeList) {
192 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
193 NodeAddr<UseNode *> UN = *I;
194 RegisterRef UR = UN.Addr->getRegRef();
195 NodeSet Visited, Defs;
196 const auto &ReachingDefs = LV->getAllReachingDefsRec(UR, UN, Visited, Defs);
197 if (ReachingDefs.size() > 1) {
198 DEBUG({
199 dbgs() << "*** Multiple Reaching Defs found!!! ***\n";
200 for (auto DI : ReachingDefs) {
201 NodeAddr<UseNode *> DA = DFG->addr<UseNode *>(DI);
202 NodeAddr<StmtNode *> TempIA = DA.Addr->getOwner(*DFG);
203 dbgs() << "\t\t[Reaching Def]: "
204 << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
205 }
206 });
207 return false;
208 }
209 }
210 return true;
211 }
212
getAllRealUses(NodeAddr<StmtNode * > SA,NodeList & UNodeList)213 void HexagonOptAddrMode::getAllRealUses(NodeAddr<StmtNode *> SA,
214 NodeList &UNodeList) {
215 for (NodeAddr<DefNode *> DA : SA.Addr->members_if(DFG->IsDef, *DFG)) {
216 DEBUG(dbgs() << "\t\t[DefNode]: " << Print<NodeAddr<DefNode *>>(DA, *DFG)
217 << "\n");
218 RegisterRef DR = DA.Addr->getRegRef();
219 auto UseSet = LV->getAllReachedUses(DR, DA);
220
221 for (auto UI : UseSet) {
222 NodeAddr<UseNode *> UA = DFG->addr<UseNode *>(UI);
223 DEBUG({
224 NodeAddr<StmtNode *> TempIA = UA.Addr->getOwner(*DFG);
225 dbgs() << "\t\t\t[Reached Use]: "
226 << Print<NodeAddr<InstrNode *>>(TempIA, *DFG) << "\n";
227 });
228
229 if (UA.Addr->getFlags() & NodeAttrs::PhiRef) {
230 NodeAddr<PhiNode *> PA = UA.Addr->getOwner(*DFG);
231 NodeId id = PA.Id;
232 const Liveness::RefMap &phiUse = LV->getRealUses(id);
233 DEBUG(dbgs() << "\t\t\t\tphi real Uses"
234 << Print<Liveness::RefMap>(phiUse, *DFG) << "\n");
235 if (phiUse.size() > 0) {
236 for (auto I : phiUse) {
237 if (DR != I.first)
238 continue;
239 auto phiUseSet = I.second;
240 for (auto phiUI : phiUseSet) {
241 NodeAddr<UseNode *> phiUA = DFG->addr<UseNode *>(phiUI);
242 UNodeList.push_back(phiUA);
243 }
244 }
245 }
246 } else
247 UNodeList.push_back(UA);
248 }
249 }
250 }
251
analyzeUses(unsigned tfrDefR,const NodeList & UNodeList,InstrEvalMap & InstrEvalResult,short & SizeInc)252 bool HexagonOptAddrMode::analyzeUses(unsigned tfrDefR,
253 const NodeList &UNodeList,
254 InstrEvalMap &InstrEvalResult,
255 short &SizeInc) {
256 bool KeepTfr = false;
257 bool HasRepInstr = false;
258 InstrEvalResult.clear();
259
260 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
261 bool CanBeReplaced = false;
262 NodeAddr<UseNode *> UN = *I;
263 NodeAddr<StmtNode *> SN = UN.Addr->getOwner(*DFG);
264 MachineInstr *MI = SN.Addr->getCode();
265 const MCInstrDesc &MID = MI->getDesc();
266 if ((MID.mayLoad() || MID.mayStore())) {
267 if (!hasRepForm(MI, tfrDefR)) {
268 KeepTfr = true;
269 continue;
270 }
271 SizeInc++;
272 CanBeReplaced = true;
273 } else if (MI->getOpcode() == Hexagon::S2_addasl_rrri) {
274 NodeList AddaslUseList;
275
276 DEBUG(dbgs() << "\nGetting ReachedUses for === " << *MI << "\n");
277 getAllRealUses(SN, AddaslUseList);
278 // Process phi nodes.
279 if (allValidCandidates(SN, AddaslUseList) &&
280 canRemoveAddasl(SN, MI, AddaslUseList)) {
281 SizeInc += AddaslUseList.size();
282 SizeInc -= 1; // Reduce size by 1 as addasl itself can be removed.
283 CanBeReplaced = true;
284 } else
285 SizeInc++;
286 } else
287 // Currently, only load/store and addasl are handled.
288 // Some other instructions to consider -
289 // A2_add -> A2_addi
290 // M4_mpyrr_addr -> M4_mpyrr_addi
291 KeepTfr = true;
292
293 InstrEvalResult[MI] = CanBeReplaced;
294 HasRepInstr |= CanBeReplaced;
295 }
296
297 // Reduce total size by 2 if original tfr can be deleted.
298 if (!KeepTfr)
299 SizeInc -= 2;
300
301 return HasRepInstr;
302 }
303
changeLoad(MachineInstr * OldMI,MachineOperand ImmOp,unsigned ImmOpNum)304 bool HexagonOptAddrMode::changeLoad(MachineInstr *OldMI, MachineOperand ImmOp,
305 unsigned ImmOpNum) {
306 bool Changed = false;
307 MachineBasicBlock *BB = OldMI->getParent();
308 auto UsePos = MachineBasicBlock::iterator(OldMI);
309 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
310 ++InsertPt;
311 unsigned OpStart;
312 unsigned OpEnd = OldMI->getNumOperands();
313 MachineInstrBuilder MIB;
314
315 if (ImmOpNum == 1) {
316 if (HII->getAddrMode(OldMI) == HexagonII::BaseRegOffset) {
317 short NewOpCode = HII->getBaseWithLongOffset(OldMI);
318 assert(NewOpCode >= 0 && "Invalid New opcode\n");
319 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
320 MIB.addOperand(OldMI->getOperand(0));
321 MIB.addOperand(OldMI->getOperand(2));
322 MIB.addOperand(OldMI->getOperand(3));
323 MIB.addOperand(ImmOp);
324 OpStart = 4;
325 Changed = true;
326 } else if (HII->getAddrMode(OldMI) == HexagonII::BaseImmOffset) {
327 short NewOpCode = HII->getAbsoluteForm(OldMI);
328 assert(NewOpCode >= 0 && "Invalid New opcode\n");
329 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode))
330 .addOperand(OldMI->getOperand(0));
331 const GlobalValue *GV = ImmOp.getGlobal();
332 int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(2).getImm();
333
334 MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
335 OpStart = 3;
336 Changed = true;
337 } else
338 Changed = false;
339
340 DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
341 DEBUG(dbgs() << "[TO]: " << MIB << "\n");
342 } else if (ImmOpNum == 2 && OldMI->getOperand(3).getImm() == 0) {
343 short NewOpCode = HII->xformRegToImmOffset(OldMI);
344 assert(NewOpCode >= 0 && "Invalid New opcode\n");
345 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
346 MIB.addOperand(OldMI->getOperand(0));
347 MIB.addOperand(OldMI->getOperand(1));
348 MIB.addOperand(ImmOp);
349 OpStart = 4;
350 Changed = true;
351 DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
352 DEBUG(dbgs() << "[TO]: " << MIB << "\n");
353 }
354
355 if (Changed)
356 for (unsigned i = OpStart; i < OpEnd; ++i)
357 MIB.addOperand(OldMI->getOperand(i));
358
359 return Changed;
360 }
361
changeStore(MachineInstr * OldMI,MachineOperand ImmOp,unsigned ImmOpNum)362 bool HexagonOptAddrMode::changeStore(MachineInstr *OldMI, MachineOperand ImmOp,
363 unsigned ImmOpNum) {
364 bool Changed = false;
365 unsigned OpStart;
366 unsigned OpEnd = OldMI->getNumOperands();
367 MachineBasicBlock *BB = OldMI->getParent();
368 auto UsePos = MachineBasicBlock::iterator(OldMI);
369 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
370 ++InsertPt;
371 MachineInstrBuilder MIB;
372 if (ImmOpNum == 0) {
373 if (HII->getAddrMode(OldMI) == HexagonII::BaseRegOffset) {
374 short NewOpCode = HII->getBaseWithLongOffset(OldMI);
375 assert(NewOpCode >= 0 && "Invalid New opcode\n");
376 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
377 MIB.addOperand(OldMI->getOperand(1));
378 MIB.addOperand(OldMI->getOperand(2));
379 MIB.addOperand(ImmOp);
380 MIB.addOperand(OldMI->getOperand(3));
381 OpStart = 4;
382 } else if (HII->getAddrMode(OldMI) == HexagonII::BaseImmOffset) {
383 short NewOpCode = HII->getAbsoluteForm(OldMI);
384 assert(NewOpCode >= 0 && "Invalid New opcode\n");
385 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
386 const GlobalValue *GV = ImmOp.getGlobal();
387 int64_t Offset = ImmOp.getOffset() + OldMI->getOperand(1).getImm();
388 MIB.addGlobalAddress(GV, Offset, ImmOp.getTargetFlags());
389 MIB.addOperand(OldMI->getOperand(2));
390 OpStart = 3;
391 }
392 Changed = true;
393 DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
394 DEBUG(dbgs() << "[TO]: " << MIB << "\n");
395 } else if (ImmOpNum == 1 && OldMI->getOperand(2).getImm() == 0) {
396 short NewOpCode = HII->xformRegToImmOffset(OldMI);
397 assert(NewOpCode >= 0 && "Invalid New opcode\n");
398 MIB = BuildMI(*BB, InsertPt, OldMI->getDebugLoc(), HII->get(NewOpCode));
399 MIB.addOperand(OldMI->getOperand(0));
400 MIB.addOperand(ImmOp);
401 MIB.addOperand(OldMI->getOperand(1));
402 OpStart = 2;
403 Changed = true;
404 DEBUG(dbgs() << "[Changing]: " << *OldMI << "\n");
405 DEBUG(dbgs() << "[TO]: " << MIB << "\n");
406 }
407 if (Changed)
408 for (unsigned i = OpStart; i < OpEnd; ++i)
409 MIB.addOperand(OldMI->getOperand(i));
410
411 return Changed;
412 }
413
getBaseWithLongOffset(const MachineInstr * MI) const414 short HexagonOptAddrMode::getBaseWithLongOffset(const MachineInstr *MI) const {
415 if (HII->getAddrMode(MI) == HexagonII::BaseImmOffset) {
416 short TempOpCode = HII->getBaseWithRegOffset(MI);
417 return HII->getBaseWithLongOffset(TempOpCode);
418 } else
419 return HII->getBaseWithLongOffset(MI);
420 }
421
changeAddAsl(NodeAddr<UseNode * > AddAslUN,MachineInstr * AddAslMI,const MachineOperand & ImmOp,unsigned ImmOpNum)422 bool HexagonOptAddrMode::changeAddAsl(NodeAddr<UseNode *> AddAslUN,
423 MachineInstr *AddAslMI,
424 const MachineOperand &ImmOp,
425 unsigned ImmOpNum) {
426 NodeAddr<StmtNode *> SA = AddAslUN.Addr->getOwner(*DFG);
427
428 DEBUG(dbgs() << "Processing addasl :" << *AddAslMI << "\n");
429
430 NodeList UNodeList;
431 getAllRealUses(SA, UNodeList);
432
433 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
434 NodeAddr<UseNode *> UseUN = *I;
435 assert(!(UseUN.Addr->getFlags() & NodeAttrs::PhiRef) &&
436 "Can't transform this 'AddAsl' instruction!");
437
438 NodeAddr<StmtNode *> UseIA = UseUN.Addr->getOwner(*DFG);
439 DEBUG(dbgs() << "[InstrNode]: " << Print<NodeAddr<InstrNode *>>(UseIA, *DFG)
440 << "\n");
441 MachineInstr *UseMI = UseIA.Addr->getCode();
442 DEBUG(dbgs() << "[MI <BB#" << UseMI->getParent()->getNumber()
443 << ">]: " << *UseMI << "\n");
444 const MCInstrDesc &UseMID = UseMI->getDesc();
445 assert(HII->getAddrMode(UseMI) == HexagonII::BaseImmOffset);
446
447 auto UsePos = MachineBasicBlock::iterator(UseMI);
448 MachineBasicBlock::instr_iterator InsertPt = UsePos.getInstrIterator();
449 short NewOpCode = getBaseWithLongOffset(UseMI);
450 assert(NewOpCode >= 0 && "Invalid New opcode\n");
451
452 unsigned OpStart;
453 unsigned OpEnd = UseMI->getNumOperands();
454
455 MachineBasicBlock *BB = UseMI->getParent();
456 MachineInstrBuilder MIB =
457 BuildMI(*BB, InsertPt, UseMI->getDebugLoc(), HII->get(NewOpCode));
458 // change mem(Rs + # ) -> mem(Rt << # + ##)
459 if (UseMID.mayLoad()) {
460 MIB.addOperand(UseMI->getOperand(0));
461 MIB.addOperand(AddAslMI->getOperand(2));
462 MIB.addOperand(AddAslMI->getOperand(3));
463 const GlobalValue *GV = ImmOp.getGlobal();
464 MIB.addGlobalAddress(GV, UseMI->getOperand(2).getImm(),
465 ImmOp.getTargetFlags());
466 OpStart = 3;
467 } else if (UseMID.mayStore()) {
468 MIB.addOperand(AddAslMI->getOperand(2));
469 MIB.addOperand(AddAslMI->getOperand(3));
470 const GlobalValue *GV = ImmOp.getGlobal();
471 MIB.addGlobalAddress(GV, UseMI->getOperand(1).getImm(),
472 ImmOp.getTargetFlags());
473 MIB.addOperand(UseMI->getOperand(2));
474 OpStart = 3;
475 } else
476 llvm_unreachable("Unhandled instruction");
477
478 for (unsigned i = OpStart; i < OpEnd; ++i)
479 MIB.addOperand(UseMI->getOperand(i));
480
481 Deleted.insert(UseMI);
482 }
483
484 return true;
485 }
486
xformUseMI(MachineInstr * TfrMI,MachineInstr * UseMI,NodeAddr<UseNode * > UseN,unsigned UseMOnum)487 bool HexagonOptAddrMode::xformUseMI(MachineInstr *TfrMI, MachineInstr *UseMI,
488 NodeAddr<UseNode *> UseN,
489 unsigned UseMOnum) {
490 const MachineOperand ImmOp = TfrMI->getOperand(1);
491 const MCInstrDesc &MID = UseMI->getDesc();
492 unsigned Changed = false;
493 if (MID.mayLoad())
494 Changed = changeLoad(UseMI, ImmOp, UseMOnum);
495 else if (MID.mayStore())
496 Changed = changeStore(UseMI, ImmOp, UseMOnum);
497 else if (UseMI->getOpcode() == Hexagon::S2_addasl_rrri)
498 Changed = changeAddAsl(UseN, UseMI, ImmOp, UseMOnum);
499
500 if (Changed)
501 Deleted.insert(UseMI);
502
503 return Changed;
504 }
505
processBlock(NodeAddr<BlockNode * > BA)506 bool HexagonOptAddrMode::processBlock(NodeAddr<BlockNode *> BA) {
507 bool Changed = false;
508
509 for (auto IA : BA.Addr->members(*DFG)) {
510 if (!DFG->IsCode<NodeAttrs::Stmt>(IA))
511 continue;
512
513 NodeAddr<StmtNode *> SA = IA;
514 MachineInstr *MI = SA.Addr->getCode();
515 if (MI->getOpcode() != Hexagon::A2_tfrsi ||
516 !MI->getOperand(1).isGlobal())
517 continue;
518
519 DEBUG(dbgs() << "[Analyzing A2_tfrsi]: " << *MI << "\n");
520 DEBUG(dbgs() << "\t[InstrNode]: " << Print<NodeAddr<InstrNode *>>(IA, *DFG)
521 << "\n");
522
523 NodeList UNodeList;
524 getAllRealUses(SA, UNodeList);
525
526 if (!allValidCandidates(SA, UNodeList))
527 continue;
528
529 short SizeInc = 0;
530 unsigned DefR = MI->getOperand(0).getReg();
531 InstrEvalMap InstrEvalResult;
532
533 // Analyze all uses and calculate increase in size. Perform the optimization
534 // only if there is no increase in size.
535 if (!analyzeUses(DefR, UNodeList, InstrEvalResult, SizeInc))
536 continue;
537 if (SizeInc > CodeGrowthLimit)
538 continue;
539
540 bool KeepTfr = false;
541
542 DEBUG(dbgs() << "\t[Total reached uses] : " << UNodeList.size() << "\n");
543 DEBUG(dbgs() << "\t[Processing Reached Uses] ===\n");
544 for (auto I = UNodeList.rbegin(), E = UNodeList.rend(); I != E; ++I) {
545 NodeAddr<UseNode *> UseN = *I;
546 assert(!(UseN.Addr->getFlags() & NodeAttrs::PhiRef) &&
547 "Found a PhiRef node as a real reached use!!");
548
549 NodeAddr<StmtNode *> OwnerN = UseN.Addr->getOwner(*DFG);
550 MachineInstr *UseMI = OwnerN.Addr->getCode();
551 DEBUG(dbgs() << "\t\t[MI <BB#" << UseMI->getParent()->getNumber()
552 << ">]: " << *UseMI << "\n");
553
554 int UseMOnum = -1;
555 unsigned NumOperands = UseMI->getNumOperands();
556 for (unsigned j = 0; j < NumOperands - 1; ++j) {
557 const MachineOperand &op = UseMI->getOperand(j);
558 if (op.isReg() && op.isUse() && DefR == op.getReg())
559 UseMOnum = j;
560 }
561 assert(UseMOnum >= 0 && "Invalid reached use!");
562
563 if (InstrEvalResult[UseMI])
564 // Change UseMI if replacement is possible.
565 Changed |= xformUseMI(MI, UseMI, UseN, UseMOnum);
566 else
567 KeepTfr = true;
568 }
569 if (!KeepTfr)
570 Deleted.insert(MI);
571 }
572 return Changed;
573 }
574
updateMap(NodeAddr<InstrNode * > IA)575 void HexagonOptAddrMode::updateMap(NodeAddr<InstrNode *> IA) {
576 RegisterSet RRs;
577 for (NodeAddr<RefNode *> RA : IA.Addr->members(*DFG))
578 RRs.insert(RA.Addr->getRegRef());
579 bool Common = false;
580 for (auto &R : RDefMap) {
581 if (!RRs.count(R.first))
582 continue;
583 Common = true;
584 break;
585 }
586 if (!Common)
587 return;
588
589 for (auto &R : RDefMap) {
590 auto F = DefM.find(R.first);
591 if (F == DefM.end() || F->second.empty())
592 continue;
593 R.second[IA.Id] = F->second.top()->Id;
594 }
595 }
596
constructDefMap(MachineBasicBlock * B)597 bool HexagonOptAddrMode::constructDefMap(MachineBasicBlock *B) {
598 bool Changed = false;
599 auto BA = DFG->getFunc().Addr->findBlock(B, *DFG);
600 DFG->markBlock(BA.Id, DefM);
601
602 for (NodeAddr<InstrNode *> IA : BA.Addr->members(*DFG)) {
603 updateMap(IA);
604 DFG->pushDefs(IA, DefM);
605 }
606
607 MachineDomTreeNode *N = MDT->getNode(B);
608 for (auto I : *N)
609 Changed |= constructDefMap(I->getBlock());
610
611 DFG->releaseBlock(BA.Id, DefM);
612 return Changed;
613 }
614
runOnMachineFunction(MachineFunction & MF)615 bool HexagonOptAddrMode::runOnMachineFunction(MachineFunction &MF) {
616 bool Changed = false;
617 auto &HST = MF.getSubtarget<HexagonSubtarget>();
618 auto &MRI = MF.getRegInfo();
619 HII = HST.getInstrInfo();
620 const auto &MDF = getAnalysis<MachineDominanceFrontier>();
621 MDT = &getAnalysis<MachineDominatorTree>();
622 const auto &TRI = *MF.getSubtarget().getRegisterInfo();
623 const TargetOperandInfo TOI(*HII);
624
625 RegisterAliasInfo RAI(TRI);
626 DataFlowGraph G(MF, *HII, TRI, *MDT, MDF, RAI, TOI);
627 G.build();
628 DFG = &G;
629
630 Liveness L(MRI, *DFG);
631 L.computePhiInfo();
632 LV = &L;
633
634 constructDefMap(&DFG->getMF().front());
635
636 Deleted.clear();
637 NodeAddr<FuncNode *> FA = DFG->getFunc();
638 DEBUG(dbgs() << "==== [RefMap#]=====:\n "
639 << Print<NodeAddr<FuncNode *>>(FA, *DFG) << "\n");
640
641 for (NodeAddr<BlockNode *> BA : FA.Addr->members(*DFG))
642 Changed |= processBlock(BA);
643
644 for (auto MI : Deleted)
645 MI->eraseFromParent();
646
647 if (Changed) {
648 G.build();
649 L.computeLiveIns();
650 L.resetLiveIns();
651 L.resetKills();
652 }
653
654 return Changed;
655 }
656
657 //===----------------------------------------------------------------------===//
658 // Public Constructor Functions
659 //===----------------------------------------------------------------------===//
660
createHexagonOptAddrMode()661 FunctionPass *llvm::createHexagonOptAddrMode() {
662 return new HexagonOptAddrMode();
663 }
664