1//===- HexagonBitSimplify.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
9#include "BitTracker.h"
10#include "Hexagon.h"
11#include "HexagonBitTracker.h"
12#include "HexagonInstrInfo.h"
13#include "HexagonRegisterInfo.h"
14#include "HexagonSubtarget.h"
15#include "llvm/ADT/BitVector.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/StringRef.h"
18#include "llvm/CodeGen/MachineBasicBlock.h"
19#include "llvm/CodeGen/MachineDominators.h"
20#include "llvm/CodeGen/MachineFunction.h"
21#include "llvm/CodeGen/MachineFunctionPass.h"
22#include "llvm/CodeGen/MachineInstr.h"
23#include "llvm/CodeGen/MachineOperand.h"
24#include "llvm/CodeGen/MachineRegisterInfo.h"
25#include "llvm/CodeGen/TargetRegisterInfo.h"
26#include "llvm/IR/DebugLoc.h"
27#include "llvm/InitializePasses.h"
28#include "llvm/MC/MCInstrDesc.h"
29#include "llvm/Pass.h"
30#include "llvm/Support/Debug.h"
31#include "llvm/Support/raw_ostream.h"
32
33#define DEBUG_TYPE "hexbit"
34
35using namespace llvm;
36
37static cl::opt<bool> PreserveTiedOps("hexbit-keep-tied", cl::Hidden,
38 cl::init(Val: true), cl::desc("Preserve subregisters in tied operands"));
39static cl::opt<bool> GenExtract("hexbit-extract", cl::Hidden,
40 cl::init(Val: true), cl::desc("Generate extract instructions"));
41static cl::opt<bool> GenBitSplit("hexbit-bitsplit", cl::Hidden,
42 cl::init(Val: true), cl::desc("Generate bitsplit instructions"));
43
44static cl::opt<unsigned> MaxExtract("hexbit-max-extract", cl::Hidden,
45 cl::init(Val: std::numeric_limits<unsigned>::max()));
46static unsigned CountExtract = 0;
47static cl::opt<unsigned> MaxBitSplit("hexbit-max-bitsplit", cl::Hidden,
48 cl::init(Val: std::numeric_limits<unsigned>::max()));
49static unsigned CountBitSplit = 0;
50
51static cl::opt<unsigned> RegisterSetLimit("hexbit-registerset-limit",
52 cl::Hidden, cl::init(Val: 1000));
53
54namespace {
55
56 // Set of virtual registers, based on BitVector.
57 struct RegisterSet {
58 RegisterSet() = default;
59 explicit RegisterSet(unsigned s, bool t = false) : Bits(s, t) {}
60 RegisterSet(const RegisterSet &RS) = default;
61
62 void clear() {
63 Bits.clear();
64 LRU.clear();
65 }
66
67 unsigned count() const {
68 return Bits.count();
69 }
70
71 unsigned find_first() const {
72 int First = Bits.find_first();
73 if (First < 0)
74 return 0;
75 return x2v(x: First);
76 }
77
78 unsigned find_next(unsigned Prev) const {
79 int Next = Bits.find_next(Prev: v2x(v: Prev));
80 if (Next < 0)
81 return 0;
82 return x2v(x: Next);
83 }
84
85 RegisterSet &insert(unsigned R) {
86 unsigned Idx = v2x(v: R);
87 ensure(Idx);
88 bool Exists = Bits.test(Idx);
89 Bits.set(Idx);
90 if (!Exists) {
91 LRU.push_back(x: Idx);
92 if (LRU.size() > RegisterSetLimit) {
93 unsigned T = LRU.front();
94 Bits.reset(Idx: T);
95 LRU.pop_front();
96 }
97 }
98 return *this;
99 }
100 RegisterSet &remove(unsigned R) {
101 unsigned Idx = v2x(v: R);
102 if (Idx < Bits.size()) {
103 bool Exists = Bits.test(Idx);
104 Bits.reset(Idx);
105 if (Exists) {
106 auto F = llvm::find(Range&: LRU, Val: Idx);
107 assert(F != LRU.end());
108 LRU.erase(position: F);
109 }
110 }
111 return *this;
112 }
113
114 RegisterSet &insert(const RegisterSet &Rs) {
115 for (unsigned R = Rs.find_first(); R; R = Rs.find_next(Prev: R))
116 insert(R);
117 return *this;
118 }
119 RegisterSet &remove(const RegisterSet &Rs) {
120 for (unsigned R = Rs.find_first(); R; R = Rs.find_next(Prev: R))
121 remove(R);
122 return *this;
123 }
124
125 bool operator[](unsigned R) const {
126 unsigned Idx = v2x(v: R);
127 return Idx < Bits.size() ? Bits[Idx] : false;
128 }
129 bool has(unsigned R) const {
130 unsigned Idx = v2x(v: R);
131 if (Idx >= Bits.size())
132 return false;
133 return Bits.test(Idx);
134 }
135
136 bool empty() const {
137 return !Bits.any();
138 }
139 bool includes(const RegisterSet &Rs) const {
140 return Rs.Bits.subsetOf(RHS: Bits);
141 }
142 bool intersects(const RegisterSet &Rs) const {
143 return Bits.anyCommon(RHS: Rs.Bits);
144 }
145
146 private:
147 BitVector Bits;
148 std::deque<unsigned> LRU;
149
150 void ensure(unsigned Idx) {
151 if (Bits.size() <= Idx)
152 Bits.resize(N: std::max(a: Idx+1, b: 32U));
153 }
154
155 static inline unsigned v2x(unsigned v) {
156 return Register(v).virtRegIndex();
157 }
158
159 static inline unsigned x2v(unsigned x) {
160 return Register::index2VirtReg(Index: x);
161 }
162 };
163
164 struct PrintRegSet {
165 PrintRegSet(const RegisterSet &S, const TargetRegisterInfo *RI)
166 : RS(S), TRI(RI) {}
167
168 friend raw_ostream &operator<< (raw_ostream &OS,
169 const PrintRegSet &P);
170
171 private:
172 const RegisterSet &RS;
173 const TargetRegisterInfo *TRI;
174 };
175
176 [[maybe_unused]] raw_ostream &operator<<(raw_ostream &OS,
177 const PrintRegSet &P);
178 raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) {
179 OS << '{';
180 for (unsigned R = P.RS.find_first(); R; R = P.RS.find_next(Prev: R))
181 OS << ' ' << printReg(Reg: R, TRI: P.TRI);
182 OS << " }";
183 return OS;
184 }
185
186 class Transformation;
187
188 class HexagonBitSimplify : public MachineFunctionPass {
189 public:
190 static char ID;
191
192 HexagonBitSimplify() : MachineFunctionPass(ID) {}
193
194 StringRef getPassName() const override {
195 return "Hexagon bit simplification";
196 }
197
198 void getAnalysisUsage(AnalysisUsage &AU) const override {
199 AU.addRequired<MachineDominatorTreeWrapperPass>();
200 AU.addPreserved<MachineDominatorTreeWrapperPass>();
201 MachineFunctionPass::getAnalysisUsage(AU);
202 }
203
204 bool runOnMachineFunction(MachineFunction &MF) override;
205
206 static void getInstrDefs(const MachineInstr &MI, RegisterSet &Defs);
207 static void getInstrUses(const MachineInstr &MI, RegisterSet &Uses);
208 static bool isEqual(const BitTracker::RegisterCell &RC1, uint16_t B1,
209 const BitTracker::RegisterCell &RC2, uint16_t B2, uint16_t W);
210 static bool isZero(const BitTracker::RegisterCell &RC, uint16_t B,
211 uint16_t W);
212 static bool getConst(const BitTracker::RegisterCell &RC, uint16_t B,
213 uint16_t W, uint64_t &U);
214 static bool replaceReg(Register OldR, Register NewR,
215 MachineRegisterInfo &MRI);
216 static bool getSubregMask(const BitTracker::RegisterRef &RR,
217 unsigned &Begin, unsigned &Width, MachineRegisterInfo &MRI);
218 static bool replaceRegWithSub(Register OldR, Register NewR, unsigned NewSR,
219 MachineRegisterInfo &MRI);
220 static bool replaceSubWithSub(Register OldR, unsigned OldSR, Register NewR,
221 unsigned NewSR, MachineRegisterInfo &MRI);
222 static bool parseRegSequence(const MachineInstr &I,
223 BitTracker::RegisterRef &SL, BitTracker::RegisterRef &SH,
224 const MachineRegisterInfo &MRI);
225
226 static bool getUsedBitsInStore(unsigned Opc, BitVector &Bits,
227 uint16_t Begin);
228 static bool getUsedBits(unsigned Opc, unsigned OpN, BitVector &Bits,
229 uint16_t Begin, const HexagonInstrInfo &HII);
230
231 static const TargetRegisterClass *getFinalVRegClass(
232 const BitTracker::RegisterRef &RR, MachineRegisterInfo &MRI);
233 static bool isTransparentCopy(const BitTracker::RegisterRef &RD,
234 const BitTracker::RegisterRef &RS, MachineRegisterInfo &MRI);
235
236 private:
237 MachineDominatorTree *MDT = nullptr;
238
239 bool visitBlock(MachineBasicBlock &B, Transformation &T, RegisterSet &AVs);
240 static bool hasTiedUse(unsigned Reg, MachineRegisterInfo &MRI,
241 unsigned NewSub = Hexagon::NoSubRegister);
242 };
243
244 using HBS = HexagonBitSimplify;
245
246 // The purpose of this class is to provide a common facility to traverse
247 // the function top-down or bottom-up via the dominator tree, and keep
248 // track of the available registers.
249 class Transformation {
250 public:
251 bool TopDown;
252
253 Transformation(bool TD) : TopDown(TD) {}
254 virtual ~Transformation() = default;
255
256 virtual bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) = 0;
257 };
258
259} // end anonymous namespace
260
261char HexagonBitSimplify::ID = 0;
262
263INITIALIZE_PASS_BEGIN(HexagonBitSimplify, "hexagon-bit-simplify",
264 "Hexagon bit simplification", false, false)
265INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
266INITIALIZE_PASS_END(HexagonBitSimplify, "hexagon-bit-simplify",
267 "Hexagon bit simplification", false, false)
268
269bool HexagonBitSimplify::visitBlock(MachineBasicBlock &B, Transformation &T,
270 RegisterSet &AVs) {
271 bool Changed = false;
272
273 if (T.TopDown)
274 Changed = T.processBlock(B, AVs);
275
276 RegisterSet Defs;
277 for (auto &I : B)
278 getInstrDefs(MI: I, Defs);
279 RegisterSet NewAVs = AVs;
280 NewAVs.insert(Rs: Defs);
281
282 for (auto *DTN : children<MachineDomTreeNode*>(G: MDT->getNode(BB: &B)))
283 Changed |= visitBlock(B&: *(DTN->getBlock()), T, AVs&: NewAVs);
284
285 if (!T.TopDown)
286 Changed |= T.processBlock(B, AVs);
287
288 return Changed;
289}
290
291//
292// Utility functions:
293//
294void HexagonBitSimplify::getInstrDefs(const MachineInstr &MI,
295 RegisterSet &Defs) {
296 for (auto &Op : MI.operands()) {
297 if (!Op.isReg() || !Op.isDef())
298 continue;
299 Register R = Op.getReg();
300 if (!R.isVirtual())
301 continue;
302 Defs.insert(R);
303 }
304}
305
306void HexagonBitSimplify::getInstrUses(const MachineInstr &MI,
307 RegisterSet &Uses) {
308 for (auto &Op : MI.operands()) {
309 if (!Op.isReg() || !Op.isUse())
310 continue;
311 Register R = Op.getReg();
312 if (!R.isVirtual())
313 continue;
314 Uses.insert(R);
315 }
316}
317
318// Check if all the bits in range [B, E) in both cells are equal.
319bool HexagonBitSimplify::isEqual(const BitTracker::RegisterCell &RC1,
320 uint16_t B1, const BitTracker::RegisterCell &RC2, uint16_t B2,
321 uint16_t W) {
322 for (uint16_t i = 0; i < W; ++i) {
323 // If RC1[i] is "bottom", it cannot be proven equal to RC2[i].
324 if (RC1[B1+i].Type == BitTracker::BitValue::Ref && RC1[B1+i].RefI.Reg == 0)
325 return false;
326 // Same for RC2[i].
327 if (RC2[B2+i].Type == BitTracker::BitValue::Ref && RC2[B2+i].RefI.Reg == 0)
328 return false;
329 if (RC1[B1+i] != RC2[B2+i])
330 return false;
331 }
332 return true;
333}
334
335bool HexagonBitSimplify::isZero(const BitTracker::RegisterCell &RC,
336 uint16_t B, uint16_t W) {
337 assert(B < RC.width() && B+W <= RC.width());
338 for (uint16_t i = B; i < B+W; ++i)
339 if (!RC[i].is(T: 0))
340 return false;
341 return true;
342}
343
344bool HexagonBitSimplify::getConst(const BitTracker::RegisterCell &RC,
345 uint16_t B, uint16_t W, uint64_t &U) {
346 assert(B < RC.width() && B+W <= RC.width());
347 int64_t T = 0;
348 for (uint16_t i = B+W; i > B; --i) {
349 const BitTracker::BitValue &BV = RC[i-1];
350 T <<= 1;
351 if (BV.is(T: 1))
352 T |= 1;
353 else if (!BV.is(T: 0))
354 return false;
355 }
356 U = T;
357 return true;
358}
359
360bool HexagonBitSimplify::replaceReg(Register OldR, Register NewR,
361 MachineRegisterInfo &MRI) {
362 if (!OldR.isVirtual() || !NewR.isVirtual())
363 return false;
364 auto Begin = MRI.use_begin(RegNo: OldR), End = MRI.use_end();
365 decltype(End) NextI;
366 for (auto I = Begin; I != End; I = NextI) {
367 NextI = std::next(x: I);
368 I->setReg(NewR);
369 }
370 return Begin != End;
371}
372
373bool HexagonBitSimplify::replaceRegWithSub(Register OldR, Register NewR,
374 unsigned NewSR,
375 MachineRegisterInfo &MRI) {
376 if (!OldR.isVirtual() || !NewR.isVirtual())
377 return false;
378 if (hasTiedUse(Reg: OldR, MRI, NewSub: NewSR))
379 return false;
380 auto Begin = MRI.use_begin(RegNo: OldR), End = MRI.use_end();
381 decltype(End) NextI;
382 for (auto I = Begin; I != End; I = NextI) {
383 NextI = std::next(x: I);
384 I->setReg(NewR);
385 I->setSubReg(NewSR);
386 }
387 return Begin != End;
388}
389
390bool HexagonBitSimplify::replaceSubWithSub(Register OldR, unsigned OldSR,
391 Register NewR, unsigned NewSR,
392 MachineRegisterInfo &MRI) {
393 if (!OldR.isVirtual() || !NewR.isVirtual())
394 return false;
395 if (OldSR != NewSR && hasTiedUse(Reg: OldR, MRI, NewSub: NewSR))
396 return false;
397 auto Begin = MRI.use_begin(RegNo: OldR), End = MRI.use_end();
398 decltype(End) NextI;
399 for (auto I = Begin; I != End; I = NextI) {
400 NextI = std::next(x: I);
401 if (I->getSubReg() != OldSR)
402 continue;
403 I->setReg(NewR);
404 I->setSubReg(NewSR);
405 }
406 return Begin != End;
407}
408
409// For a register ref (pair Reg:Sub), set Begin to the position of the LSB
410// of Sub in Reg, and set Width to the size of Sub in bits. Return true,
411// if this succeeded, otherwise return false.
412bool HexagonBitSimplify::getSubregMask(const BitTracker::RegisterRef &RR,
413 unsigned &Begin, unsigned &Width, MachineRegisterInfo &MRI) {
414 const TargetRegisterClass *RC = MRI.getRegClass(Reg: RR.Reg);
415 if (RR.Sub == 0) {
416 Begin = 0;
417 Width = MRI.getTargetRegisterInfo()->getRegSizeInBits(RC: *RC);
418 return true;
419 }
420
421 Begin = 0;
422
423 switch (RC->getID()) {
424 case Hexagon::DoubleRegsRegClassID:
425 case Hexagon::HvxWRRegClassID:
426 Width = MRI.getTargetRegisterInfo()->getRegSizeInBits(RC: *RC) / 2;
427 if (RR.Sub == Hexagon::isub_hi || RR.Sub == Hexagon::vsub_hi)
428 Begin = Width;
429 break;
430 default:
431 return false;
432 }
433 return true;
434}
435
436
437// For a REG_SEQUENCE, set SL to the low subregister and SH to the high
438// subregister.
439bool HexagonBitSimplify::parseRegSequence(const MachineInstr &I,
440 BitTracker::RegisterRef &SL, BitTracker::RegisterRef &SH,
441 const MachineRegisterInfo &MRI) {
442 assert(I.getOpcode() == TargetOpcode::REG_SEQUENCE);
443 unsigned Sub1 = I.getOperand(i: 2).getImm(), Sub2 = I.getOperand(i: 4).getImm();
444 auto &DstRC = *MRI.getRegClass(Reg: I.getOperand(i: 0).getReg());
445 auto &HRI = static_cast<const HexagonRegisterInfo&>(
446 *MRI.getTargetRegisterInfo());
447 unsigned SubLo = HRI.getHexagonSubRegIndex(RC: DstRC, GenIdx: Hexagon::ps_sub_lo);
448 unsigned SubHi = HRI.getHexagonSubRegIndex(RC: DstRC, GenIdx: Hexagon::ps_sub_hi);
449 assert((Sub1 == SubLo && Sub2 == SubHi) || (Sub1 == SubHi && Sub2 == SubLo));
450 if (Sub1 == SubLo && Sub2 == SubHi) {
451 SL = I.getOperand(i: 1);
452 SH = I.getOperand(i: 3);
453 return true;
454 }
455 if (Sub1 == SubHi && Sub2 == SubLo) {
456 SH = I.getOperand(i: 1);
457 SL = I.getOperand(i: 3);
458 return true;
459 }
460 return false;
461}
462
463// All stores (except 64-bit stores) take a 32-bit register as the source
464// of the value to be stored. If the instruction stores into a location
465// that is shorter than 32 bits, some bits of the source register are not
466// used. For each store instruction, calculate the set of used bits in
467// the source register, and set appropriate bits in Bits. Return true if
468// the bits are calculated, false otherwise.
469bool HexagonBitSimplify::getUsedBitsInStore(unsigned Opc, BitVector &Bits,
470 uint16_t Begin) {
471 using namespace Hexagon;
472
473 switch (Opc) {
474 // Store byte
475 case S2_storerb_io: // memb(Rs32+#s11:0)=Rt32
476 case S2_storerbnew_io: // memb(Rs32+#s11:0)=Nt8.new
477 case S2_pstorerbt_io: // if (Pv4) memb(Rs32+#u6:0)=Rt32
478 case S2_pstorerbf_io: // if (!Pv4) memb(Rs32+#u6:0)=Rt32
479 case S4_pstorerbtnew_io: // if (Pv4.new) memb(Rs32+#u6:0)=Rt32
480 case S4_pstorerbfnew_io: // if (!Pv4.new) memb(Rs32+#u6:0)=Rt32
481 case S2_pstorerbnewt_io: // if (Pv4) memb(Rs32+#u6:0)=Nt8.new
482 case S2_pstorerbnewf_io: // if (!Pv4) memb(Rs32+#u6:0)=Nt8.new
483 case S4_pstorerbnewtnew_io: // if (Pv4.new) memb(Rs32+#u6:0)=Nt8.new
484 case S4_pstorerbnewfnew_io: // if (!Pv4.new) memb(Rs32+#u6:0)=Nt8.new
485 case S2_storerb_pi: // memb(Rx32++#s4:0)=Rt32
486 case S2_storerbnew_pi: // memb(Rx32++#s4:0)=Nt8.new
487 case S2_pstorerbt_pi: // if (Pv4) memb(Rx32++#s4:0)=Rt32
488 case S2_pstorerbf_pi: // if (!Pv4) memb(Rx32++#s4:0)=Rt32
489 case S2_pstorerbtnew_pi: // if (Pv4.new) memb(Rx32++#s4:0)=Rt32
490 case S2_pstorerbfnew_pi: // if (!Pv4.new) memb(Rx32++#s4:0)=Rt32
491 case S2_pstorerbnewt_pi: // if (Pv4) memb(Rx32++#s4:0)=Nt8.new
492 case S2_pstorerbnewf_pi: // if (!Pv4) memb(Rx32++#s4:0)=Nt8.new
493 case S2_pstorerbnewtnew_pi: // if (Pv4.new) memb(Rx32++#s4:0)=Nt8.new
494 case S2_pstorerbnewfnew_pi: // if (!Pv4.new) memb(Rx32++#s4:0)=Nt8.new
495 case S4_storerb_ap: // memb(Re32=#U6)=Rt32
496 case S4_storerbnew_ap: // memb(Re32=#U6)=Nt8.new
497 case S2_storerb_pr: // memb(Rx32++Mu2)=Rt32
498 case S2_storerbnew_pr: // memb(Rx32++Mu2)=Nt8.new
499 case S4_storerb_ur: // memb(Ru32<<#u2+#U6)=Rt32
500 case S4_storerbnew_ur: // memb(Ru32<<#u2+#U6)=Nt8.new
501 case S2_storerb_pbr: // memb(Rx32++Mu2:brev)=Rt32
502 case S2_storerbnew_pbr: // memb(Rx32++Mu2:brev)=Nt8.new
503 case S2_storerb_pci: // memb(Rx32++#s4:0:circ(Mu2))=Rt32
504 case S2_storerbnew_pci: // memb(Rx32++#s4:0:circ(Mu2))=Nt8.new
505 case S2_storerb_pcr: // memb(Rx32++I:circ(Mu2))=Rt32
506 case S2_storerbnew_pcr: // memb(Rx32++I:circ(Mu2))=Nt8.new
507 case S4_storerb_rr: // memb(Rs32+Ru32<<#u2)=Rt32
508 case S4_storerbnew_rr: // memb(Rs32+Ru32<<#u2)=Nt8.new
509 case S4_pstorerbt_rr: // if (Pv4) memb(Rs32+Ru32<<#u2)=Rt32
510 case S4_pstorerbf_rr: // if (!Pv4) memb(Rs32+Ru32<<#u2)=Rt32
511 case S4_pstorerbtnew_rr: // if (Pv4.new) memb(Rs32+Ru32<<#u2)=Rt32
512 case S4_pstorerbfnew_rr: // if (!Pv4.new) memb(Rs32+Ru32<<#u2)=Rt32
513 case S4_pstorerbnewt_rr: // if (Pv4) memb(Rs32+Ru32<<#u2)=Nt8.new
514 case S4_pstorerbnewf_rr: // if (!Pv4) memb(Rs32+Ru32<<#u2)=Nt8.new
515 case S4_pstorerbnewtnew_rr: // if (Pv4.new) memb(Rs32+Ru32<<#u2)=Nt8.new
516 case S4_pstorerbnewfnew_rr: // if (!Pv4.new) memb(Rs32+Ru32<<#u2)=Nt8.new
517 case S2_storerbgp: // memb(gp+#u16:0)=Rt32
518 case S2_storerbnewgp: // memb(gp+#u16:0)=Nt8.new
519 case S4_pstorerbt_abs: // if (Pv4) memb(#u6)=Rt32
520 case S4_pstorerbf_abs: // if (!Pv4) memb(#u6)=Rt32
521 case S4_pstorerbtnew_abs: // if (Pv4.new) memb(#u6)=Rt32
522 case S4_pstorerbfnew_abs: // if (!Pv4.new) memb(#u6)=Rt32
523 case S4_pstorerbnewt_abs: // if (Pv4) memb(#u6)=Nt8.new
524 case S4_pstorerbnewf_abs: // if (!Pv4) memb(#u6)=Nt8.new
525 case S4_pstorerbnewtnew_abs: // if (Pv4.new) memb(#u6)=Nt8.new
526 case S4_pstorerbnewfnew_abs: // if (!Pv4.new) memb(#u6)=Nt8.new
527 Bits.set(I: Begin, E: Begin+8);
528 return true;
529
530 // Store low half
531 case S2_storerh_io: // memh(Rs32+#s11:1)=Rt32
532 case S2_storerhnew_io: // memh(Rs32+#s11:1)=Nt8.new
533 case S2_pstorerht_io: // if (Pv4) memh(Rs32+#u6:1)=Rt32
534 case S2_pstorerhf_io: // if (!Pv4) memh(Rs32+#u6:1)=Rt32
535 case S4_pstorerhtnew_io: // if (Pv4.new) memh(Rs32+#u6:1)=Rt32
536 case S4_pstorerhfnew_io: // if (!Pv4.new) memh(Rs32+#u6:1)=Rt32
537 case S2_pstorerhnewt_io: // if (Pv4) memh(Rs32+#u6:1)=Nt8.new
538 case S2_pstorerhnewf_io: // if (!Pv4) memh(Rs32+#u6:1)=Nt8.new
539 case S4_pstorerhnewtnew_io: // if (Pv4.new) memh(Rs32+#u6:1)=Nt8.new
540 case S4_pstorerhnewfnew_io: // if (!Pv4.new) memh(Rs32+#u6:1)=Nt8.new
541 case S2_storerh_pi: // memh(Rx32++#s4:1)=Rt32
542 case S2_storerhnew_pi: // memh(Rx32++#s4:1)=Nt8.new
543 case S2_pstorerht_pi: // if (Pv4) memh(Rx32++#s4:1)=Rt32
544 case S2_pstorerhf_pi: // if (!Pv4) memh(Rx32++#s4:1)=Rt32
545 case S2_pstorerhtnew_pi: // if (Pv4.new) memh(Rx32++#s4:1)=Rt32
546 case S2_pstorerhfnew_pi: // if (!Pv4.new) memh(Rx32++#s4:1)=Rt32
547 case S2_pstorerhnewt_pi: // if (Pv4) memh(Rx32++#s4:1)=Nt8.new
548 case S2_pstorerhnewf_pi: // if (!Pv4) memh(Rx32++#s4:1)=Nt8.new
549 case S2_pstorerhnewtnew_pi: // if (Pv4.new) memh(Rx32++#s4:1)=Nt8.new
550 case S2_pstorerhnewfnew_pi: // if (!Pv4.new) memh(Rx32++#s4:1)=Nt8.new
551 case S4_storerh_ap: // memh(Re32=#U6)=Rt32
552 case S4_storerhnew_ap: // memh(Re32=#U6)=Nt8.new
553 case S2_storerh_pr: // memh(Rx32++Mu2)=Rt32
554 case S2_storerhnew_pr: // memh(Rx32++Mu2)=Nt8.new
555 case S4_storerh_ur: // memh(Ru32<<#u2+#U6)=Rt32
556 case S4_storerhnew_ur: // memh(Ru32<<#u2+#U6)=Nt8.new
557 case S2_storerh_pbr: // memh(Rx32++Mu2:brev)=Rt32
558 case S2_storerhnew_pbr: // memh(Rx32++Mu2:brev)=Nt8.new
559 case S2_storerh_pci: // memh(Rx32++#s4:1:circ(Mu2))=Rt32
560 case S2_storerhnew_pci: // memh(Rx32++#s4:1:circ(Mu2))=Nt8.new
561 case S2_storerh_pcr: // memh(Rx32++I:circ(Mu2))=Rt32
562 case S2_storerhnew_pcr: // memh(Rx32++I:circ(Mu2))=Nt8.new
563 case S4_storerh_rr: // memh(Rs32+Ru32<<#u2)=Rt32
564 case S4_pstorerht_rr: // if (Pv4) memh(Rs32+Ru32<<#u2)=Rt32
565 case S4_pstorerhf_rr: // if (!Pv4) memh(Rs32+Ru32<<#u2)=Rt32
566 case S4_pstorerhtnew_rr: // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Rt32
567 case S4_pstorerhfnew_rr: // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Rt32
568 case S4_storerhnew_rr: // memh(Rs32+Ru32<<#u2)=Nt8.new
569 case S4_pstorerhnewt_rr: // if (Pv4) memh(Rs32+Ru32<<#u2)=Nt8.new
570 case S4_pstorerhnewf_rr: // if (!Pv4) memh(Rs32+Ru32<<#u2)=Nt8.new
571 case S4_pstorerhnewtnew_rr: // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Nt8.new
572 case S4_pstorerhnewfnew_rr: // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Nt8.new
573 case S2_storerhgp: // memh(gp+#u16:1)=Rt32
574 case S2_storerhnewgp: // memh(gp+#u16:1)=Nt8.new
575 case S4_pstorerht_abs: // if (Pv4) memh(#u6)=Rt32
576 case S4_pstorerhf_abs: // if (!Pv4) memh(#u6)=Rt32
577 case S4_pstorerhtnew_abs: // if (Pv4.new) memh(#u6)=Rt32
578 case S4_pstorerhfnew_abs: // if (!Pv4.new) memh(#u6)=Rt32
579 case S4_pstorerhnewt_abs: // if (Pv4) memh(#u6)=Nt8.new
580 case S4_pstorerhnewf_abs: // if (!Pv4) memh(#u6)=Nt8.new
581 case S4_pstorerhnewtnew_abs: // if (Pv4.new) memh(#u6)=Nt8.new
582 case S4_pstorerhnewfnew_abs: // if (!Pv4.new) memh(#u6)=Nt8.new
583 Bits.set(I: Begin, E: Begin+16);
584 return true;
585
586 // Store high half
587 case S2_storerf_io: // memh(Rs32+#s11:1)=Rt.H32
588 case S2_pstorerft_io: // if (Pv4) memh(Rs32+#u6:1)=Rt.H32
589 case S2_pstorerff_io: // if (!Pv4) memh(Rs32+#u6:1)=Rt.H32
590 case S4_pstorerftnew_io: // if (Pv4.new) memh(Rs32+#u6:1)=Rt.H32
591 case S4_pstorerffnew_io: // if (!Pv4.new) memh(Rs32+#u6:1)=Rt.H32
592 case S2_storerf_pi: // memh(Rx32++#s4:1)=Rt.H32
593 case S2_pstorerft_pi: // if (Pv4) memh(Rx32++#s4:1)=Rt.H32
594 case S2_pstorerff_pi: // if (!Pv4) memh(Rx32++#s4:1)=Rt.H32
595 case S2_pstorerftnew_pi: // if (Pv4.new) memh(Rx32++#s4:1)=Rt.H32
596 case S2_pstorerffnew_pi: // if (!Pv4.new) memh(Rx32++#s4:1)=Rt.H32
597 case S4_storerf_ap: // memh(Re32=#U6)=Rt.H32
598 case S2_storerf_pr: // memh(Rx32++Mu2)=Rt.H32
599 case S4_storerf_ur: // memh(Ru32<<#u2+#U6)=Rt.H32
600 case S2_storerf_pbr: // memh(Rx32++Mu2:brev)=Rt.H32
601 case S2_storerf_pci: // memh(Rx32++#s4:1:circ(Mu2))=Rt.H32
602 case S2_storerf_pcr: // memh(Rx32++I:circ(Mu2))=Rt.H32
603 case S4_storerf_rr: // memh(Rs32+Ru32<<#u2)=Rt.H32
604 case S4_pstorerft_rr: // if (Pv4) memh(Rs32+Ru32<<#u2)=Rt.H32
605 case S4_pstorerff_rr: // if (!Pv4) memh(Rs32+Ru32<<#u2)=Rt.H32
606 case S4_pstorerftnew_rr: // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Rt.H32
607 case S4_pstorerffnew_rr: // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Rt.H32
608 case S2_storerfgp: // memh(gp+#u16:1)=Rt.H32
609 case S4_pstorerft_abs: // if (Pv4) memh(#u6)=Rt.H32
610 case S4_pstorerff_abs: // if (!Pv4) memh(#u6)=Rt.H32
611 case S4_pstorerftnew_abs: // if (Pv4.new) memh(#u6)=Rt.H32
612 case S4_pstorerffnew_abs: // if (!Pv4.new) memh(#u6)=Rt.H32
613 Bits.set(I: Begin+16, E: Begin+32);
614 return true;
615 }
616
617 return false;
618}
619
620// For an instruction with opcode Opc, calculate the set of bits that it
621// uses in a register in operand OpN. This only calculates the set of used
622// bits for cases where it does not depend on any operands (as is the case
623// in shifts, for example). For concrete instructions from a program, the
624// operand may be a subregister of a larger register, while Bits would
625// correspond to the larger register in its entirety. Because of that,
626// the parameter Begin can be used to indicate which bit of Bits should be
627// considered the LSB of the operand.
628bool HexagonBitSimplify::getUsedBits(unsigned Opc, unsigned OpN,
629 BitVector &Bits, uint16_t Begin, const HexagonInstrInfo &HII) {
630 using namespace Hexagon;
631
632 const MCInstrDesc &D = HII.get(Opcode: Opc);
633 if (D.mayStore()) {
634 if (OpN == D.getNumOperands()-1)
635 return getUsedBitsInStore(Opc, Bits, Begin);
636 return false;
637 }
638
639 switch (Opc) {
640 // One register source. Used bits: R1[0-7].
641 case A2_sxtb:
642 case A2_zxtb:
643 case A4_cmpbeqi:
644 case A4_cmpbgti:
645 case A4_cmpbgtui:
646 if (OpN == 1) {
647 Bits.set(I: Begin, E: Begin+8);
648 return true;
649 }
650 break;
651
652 // One register source. Used bits: R1[0-15].
653 case A2_aslh:
654 case A2_sxth:
655 case A2_zxth:
656 case A4_cmpheqi:
657 case A4_cmphgti:
658 case A4_cmphgtui:
659 if (OpN == 1) {
660 Bits.set(I: Begin, E: Begin+16);
661 return true;
662 }
663 break;
664
665 // One register source. Used bits: R1[16-31].
666 case A2_asrh:
667 if (OpN == 1) {
668 Bits.set(I: Begin+16, E: Begin+32);
669 return true;
670 }
671 break;
672
673 // Two register sources. Used bits: R1[0-7], R2[0-7].
674 case A4_cmpbeq:
675 case A4_cmpbgt:
676 case A4_cmpbgtu:
677 if (OpN == 1) {
678 Bits.set(I: Begin, E: Begin+8);
679 return true;
680 }
681 break;
682
683 // Two register sources. Used bits: R1[0-15], R2[0-15].
684 case A4_cmpheq:
685 case A4_cmphgt:
686 case A4_cmphgtu:
687 case A2_addh_h16_ll:
688 case A2_addh_h16_sat_ll:
689 case A2_addh_l16_ll:
690 case A2_addh_l16_sat_ll:
691 case A2_combine_ll:
692 case A2_subh_h16_ll:
693 case A2_subh_h16_sat_ll:
694 case A2_subh_l16_ll:
695 case A2_subh_l16_sat_ll:
696 case M2_mpy_acc_ll_s0:
697 case M2_mpy_acc_ll_s1:
698 case M2_mpy_acc_sat_ll_s0:
699 case M2_mpy_acc_sat_ll_s1:
700 case M2_mpy_ll_s0:
701 case M2_mpy_ll_s1:
702 case M2_mpy_nac_ll_s0:
703 case M2_mpy_nac_ll_s1:
704 case M2_mpy_nac_sat_ll_s0:
705 case M2_mpy_nac_sat_ll_s1:
706 case M2_mpy_rnd_ll_s0:
707 case M2_mpy_rnd_ll_s1:
708 case M2_mpy_sat_ll_s0:
709 case M2_mpy_sat_ll_s1:
710 case M2_mpy_sat_rnd_ll_s0:
711 case M2_mpy_sat_rnd_ll_s1:
712 case M2_mpyd_acc_ll_s0:
713 case M2_mpyd_acc_ll_s1:
714 case M2_mpyd_ll_s0:
715 case M2_mpyd_ll_s1:
716 case M2_mpyd_nac_ll_s0:
717 case M2_mpyd_nac_ll_s1:
718 case M2_mpyd_rnd_ll_s0:
719 case M2_mpyd_rnd_ll_s1:
720 case M2_mpyu_acc_ll_s0:
721 case M2_mpyu_acc_ll_s1:
722 case M2_mpyu_ll_s0:
723 case M2_mpyu_ll_s1:
724 case M2_mpyu_nac_ll_s0:
725 case M2_mpyu_nac_ll_s1:
726 case M2_mpyud_acc_ll_s0:
727 case M2_mpyud_acc_ll_s1:
728 case M2_mpyud_ll_s0:
729 case M2_mpyud_ll_s1:
730 case M2_mpyud_nac_ll_s0:
731 case M2_mpyud_nac_ll_s1:
732 if (OpN == 1 || OpN == 2) {
733 Bits.set(I: Begin, E: Begin+16);
734 return true;
735 }
736 break;
737
738 // Two register sources. Used bits: R1[0-15], R2[16-31].
739 case A2_addh_h16_lh:
740 case A2_addh_h16_sat_lh:
741 case A2_combine_lh:
742 case A2_subh_h16_lh:
743 case A2_subh_h16_sat_lh:
744 case M2_mpy_acc_lh_s0:
745 case M2_mpy_acc_lh_s1:
746 case M2_mpy_acc_sat_lh_s0:
747 case M2_mpy_acc_sat_lh_s1:
748 case M2_mpy_lh_s0:
749 case M2_mpy_lh_s1:
750 case M2_mpy_nac_lh_s0:
751 case M2_mpy_nac_lh_s1:
752 case M2_mpy_nac_sat_lh_s0:
753 case M2_mpy_nac_sat_lh_s1:
754 case M2_mpy_rnd_lh_s0:
755 case M2_mpy_rnd_lh_s1:
756 case M2_mpy_sat_lh_s0:
757 case M2_mpy_sat_lh_s1:
758 case M2_mpy_sat_rnd_lh_s0:
759 case M2_mpy_sat_rnd_lh_s1:
760 case M2_mpyd_acc_lh_s0:
761 case M2_mpyd_acc_lh_s1:
762 case M2_mpyd_lh_s0:
763 case M2_mpyd_lh_s1:
764 case M2_mpyd_nac_lh_s0:
765 case M2_mpyd_nac_lh_s1:
766 case M2_mpyd_rnd_lh_s0:
767 case M2_mpyd_rnd_lh_s1:
768 case M2_mpyu_acc_lh_s0:
769 case M2_mpyu_acc_lh_s1:
770 case M2_mpyu_lh_s0:
771 case M2_mpyu_lh_s1:
772 case M2_mpyu_nac_lh_s0:
773 case M2_mpyu_nac_lh_s1:
774 case M2_mpyud_acc_lh_s0:
775 case M2_mpyud_acc_lh_s1:
776 case M2_mpyud_lh_s0:
777 case M2_mpyud_lh_s1:
778 case M2_mpyud_nac_lh_s0:
779 case M2_mpyud_nac_lh_s1:
780 // These four are actually LH.
781 case A2_addh_l16_hl:
782 case A2_addh_l16_sat_hl:
783 case A2_subh_l16_hl:
784 case A2_subh_l16_sat_hl:
785 if (OpN == 1) {
786 Bits.set(I: Begin, E: Begin+16);
787 return true;
788 }
789 if (OpN == 2) {
790 Bits.set(I: Begin+16, E: Begin+32);
791 return true;
792 }
793 break;
794
795 // Two register sources, used bits: R1[16-31], R2[0-15].
796 case A2_addh_h16_hl:
797 case A2_addh_h16_sat_hl:
798 case A2_combine_hl:
799 case A2_subh_h16_hl:
800 case A2_subh_h16_sat_hl:
801 case M2_mpy_acc_hl_s0:
802 case M2_mpy_acc_hl_s1:
803 case M2_mpy_acc_sat_hl_s0:
804 case M2_mpy_acc_sat_hl_s1:
805 case M2_mpy_hl_s0:
806 case M2_mpy_hl_s1:
807 case M2_mpy_nac_hl_s0:
808 case M2_mpy_nac_hl_s1:
809 case M2_mpy_nac_sat_hl_s0:
810 case M2_mpy_nac_sat_hl_s1:
811 case M2_mpy_rnd_hl_s0:
812 case M2_mpy_rnd_hl_s1:
813 case M2_mpy_sat_hl_s0:
814 case M2_mpy_sat_hl_s1:
815 case M2_mpy_sat_rnd_hl_s0:
816 case M2_mpy_sat_rnd_hl_s1:
817 case M2_mpyd_acc_hl_s0:
818 case M2_mpyd_acc_hl_s1:
819 case M2_mpyd_hl_s0:
820 case M2_mpyd_hl_s1:
821 case M2_mpyd_nac_hl_s0:
822 case M2_mpyd_nac_hl_s1:
823 case M2_mpyd_rnd_hl_s0:
824 case M2_mpyd_rnd_hl_s1:
825 case M2_mpyu_acc_hl_s0:
826 case M2_mpyu_acc_hl_s1:
827 case M2_mpyu_hl_s0:
828 case M2_mpyu_hl_s1:
829 case M2_mpyu_nac_hl_s0:
830 case M2_mpyu_nac_hl_s1:
831 case M2_mpyud_acc_hl_s0:
832 case M2_mpyud_acc_hl_s1:
833 case M2_mpyud_hl_s0:
834 case M2_mpyud_hl_s1:
835 case M2_mpyud_nac_hl_s0:
836 case M2_mpyud_nac_hl_s1:
837 if (OpN == 1) {
838 Bits.set(I: Begin+16, E: Begin+32);
839 return true;
840 }
841 if (OpN == 2) {
842 Bits.set(I: Begin, E: Begin+16);
843 return true;
844 }
845 break;
846
847 // Two register sources, used bits: R1[16-31], R2[16-31].
848 case A2_addh_h16_hh:
849 case A2_addh_h16_sat_hh:
850 case A2_combine_hh:
851 case A2_subh_h16_hh:
852 case A2_subh_h16_sat_hh:
853 case M2_mpy_acc_hh_s0:
854 case M2_mpy_acc_hh_s1:
855 case M2_mpy_acc_sat_hh_s0:
856 case M2_mpy_acc_sat_hh_s1:
857 case M2_mpy_hh_s0:
858 case M2_mpy_hh_s1:
859 case M2_mpy_nac_hh_s0:
860 case M2_mpy_nac_hh_s1:
861 case M2_mpy_nac_sat_hh_s0:
862 case M2_mpy_nac_sat_hh_s1:
863 case M2_mpy_rnd_hh_s0:
864 case M2_mpy_rnd_hh_s1:
865 case M2_mpy_sat_hh_s0:
866 case M2_mpy_sat_hh_s1:
867 case M2_mpy_sat_rnd_hh_s0:
868 case M2_mpy_sat_rnd_hh_s1:
869 case M2_mpyd_acc_hh_s0:
870 case M2_mpyd_acc_hh_s1:
871 case M2_mpyd_hh_s0:
872 case M2_mpyd_hh_s1:
873 case M2_mpyd_nac_hh_s0:
874 case M2_mpyd_nac_hh_s1:
875 case M2_mpyd_rnd_hh_s0:
876 case M2_mpyd_rnd_hh_s1:
877 case M2_mpyu_acc_hh_s0:
878 case M2_mpyu_acc_hh_s1:
879 case M2_mpyu_hh_s0:
880 case M2_mpyu_hh_s1:
881 case M2_mpyu_nac_hh_s0:
882 case M2_mpyu_nac_hh_s1:
883 case M2_mpyud_acc_hh_s0:
884 case M2_mpyud_acc_hh_s1:
885 case M2_mpyud_hh_s0:
886 case M2_mpyud_hh_s1:
887 case M2_mpyud_nac_hh_s0:
888 case M2_mpyud_nac_hh_s1:
889 if (OpN == 1 || OpN == 2) {
890 Bits.set(I: Begin+16, E: Begin+32);
891 return true;
892 }
893 break;
894 }
895
896 return false;
897}
898
899// Calculate the register class that matches Reg:Sub. For example, if
900// %1 is a double register, then %1:isub_hi would match the "int"
901// register class.
902const TargetRegisterClass *HexagonBitSimplify::getFinalVRegClass(
903 const BitTracker::RegisterRef &RR, MachineRegisterInfo &MRI) {
904 if (!RR.Reg.isVirtual())
905 return nullptr;
906 auto *RC = MRI.getRegClass(Reg: RR.Reg);
907 if (RR.Sub == 0)
908 return RC;
909 auto &HRI = static_cast<const HexagonRegisterInfo&>(
910 *MRI.getTargetRegisterInfo());
911
912 auto VerifySR = [&HRI] (const TargetRegisterClass *RC, unsigned Sub) -> void {
913 (void)HRI;
914 assert(Sub == HRI.getHexagonSubRegIndex(*RC, Hexagon::ps_sub_lo) ||
915 Sub == HRI.getHexagonSubRegIndex(*RC, Hexagon::ps_sub_hi));
916 };
917
918 switch (RC->getID()) {
919 case Hexagon::DoubleRegsRegClassID:
920 VerifySR(RC, RR.Sub);
921 return &Hexagon::IntRegsRegClass;
922 case Hexagon::HvxWRRegClassID:
923 VerifySR(RC, RR.Sub);
924 return &Hexagon::HvxVRRegClass;
925 }
926 return nullptr;
927}
928
929// Check if RD could be replaced with RS at any possible use of RD.
930// For example a predicate register cannot be replaced with a integer
931// register, but a 64-bit register with a subregister can be replaced
932// with a 32-bit register.
933bool HexagonBitSimplify::isTransparentCopy(const BitTracker::RegisterRef &RD,
934 const BitTracker::RegisterRef &RS, MachineRegisterInfo &MRI) {
935 if (!RD.Reg.isVirtual() || !RS.Reg.isVirtual())
936 return false;
937 // Return false if one (or both) classes are nullptr.
938 auto *DRC = getFinalVRegClass(RR: RD, MRI);
939 if (!DRC)
940 return false;
941
942 return DRC == getFinalVRegClass(RR: RS, MRI);
943}
944
945bool HexagonBitSimplify::hasTiedUse(unsigned Reg, MachineRegisterInfo &MRI,
946 unsigned NewSub) {
947 if (!PreserveTiedOps)
948 return false;
949 return llvm::any_of(Range: MRI.use_operands(Reg),
950 P: [NewSub] (const MachineOperand &Op) -> bool {
951 return Op.getSubReg() != NewSub && Op.isTied();
952 });
953}
954
955namespace {
956
957 class DeadCodeElimination {
958 public:
959 DeadCodeElimination(MachineFunction &mf, MachineDominatorTree &mdt)
960 : MF(mf), HII(*MF.getSubtarget<HexagonSubtarget>().getInstrInfo()),
961 MDT(mdt), MRI(mf.getRegInfo()) {}
962
963 bool run() {
964 return runOnNode(N: MDT.getRootNode());
965 }
966
967 private:
968 bool isDead(unsigned R) const;
969 bool runOnNode(MachineDomTreeNode *N);
970
971 MachineFunction &MF;
972 const HexagonInstrInfo &HII;
973 MachineDominatorTree &MDT;
974 MachineRegisterInfo &MRI;
975 };
976
977} // end anonymous namespace
978
979bool DeadCodeElimination::isDead(unsigned R) const {
980 for (const MachineInstr &UseI : MRI.use_instructions(Reg: R)) {
981 if (UseI.isDebugInstr())
982 continue;
983 if (UseI.isPHI()) {
984 assert(!UseI.getOperand(0).getSubReg());
985 Register DR = UseI.getOperand(i: 0).getReg();
986 if (DR == R)
987 continue;
988 }
989 return false;
990 }
991 return true;
992}
993
994bool DeadCodeElimination::runOnNode(MachineDomTreeNode *N) {
995 bool Changed = false;
996
997 for (auto *DTN : children<MachineDomTreeNode*>(G: N))
998 Changed |= runOnNode(N: DTN);
999
1000 MachineBasicBlock *B = N->getBlock();
1001 std::vector<MachineInstr*> Instrs;
1002 for (MachineInstr &MI : llvm::reverse(C&: *B))
1003 Instrs.push_back(x: &MI);
1004
1005 for (auto *MI : Instrs) {
1006 unsigned Opc = MI->getOpcode();
1007 // Do not touch lifetime markers. This is why the target-independent DCE
1008 // cannot be used.
1009 if (Opc == TargetOpcode::LIFETIME_START ||
1010 Opc == TargetOpcode::LIFETIME_END)
1011 continue;
1012 bool Store = false;
1013 if (MI->isInlineAsm())
1014 continue;
1015 // Delete PHIs if possible.
1016 if (!MI->isPHI() && !MI->isSafeToMove(SawStore&: Store))
1017 continue;
1018
1019 bool AllDead = true;
1020 SmallVector<unsigned,2> Regs;
1021 for (auto &Op : MI->operands()) {
1022 if (!Op.isReg() || !Op.isDef())
1023 continue;
1024 Register R = Op.getReg();
1025 if (!R.isVirtual() || !isDead(R)) {
1026 AllDead = false;
1027 break;
1028 }
1029 Regs.push_back(Elt: R);
1030 }
1031 if (!AllDead)
1032 continue;
1033
1034 B->erase(I: MI);
1035 for (unsigned Reg : Regs)
1036 MRI.markUsesInDebugValueAsUndef(Reg);
1037 Changed = true;
1038 }
1039
1040 return Changed;
1041}
1042
1043namespace {
1044
1045// Eliminate redundant instructions
1046//
1047// This transformation will identify instructions where the output register
1048// is the same as one of its input registers. This only works on instructions
1049// that define a single register (unlike post-increment loads, for example).
1050// The equality check is actually more detailed: the code calculates which
1051// bits of the output are used, and only compares these bits with the input
1052// registers.
1053// If the output matches an input, the instruction is replaced with COPY.
1054// The copies will be removed by another transformation.
1055 class RedundantInstrElimination : public Transformation {
1056 public:
1057 RedundantInstrElimination(BitTracker &bt, const HexagonInstrInfo &hii,
1058 const HexagonRegisterInfo &hri, MachineRegisterInfo &mri)
1059 : Transformation(true), HII(hii), HRI(hri), MRI(mri), BT(bt) {}
1060
1061 bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1062
1063 private:
1064 bool isLossyShiftLeft(const MachineInstr &MI, unsigned OpN,
1065 unsigned &LostB, unsigned &LostE);
1066 bool isLossyShiftRight(const MachineInstr &MI, unsigned OpN,
1067 unsigned &LostB, unsigned &LostE);
1068 bool computeUsedBits(unsigned Reg, BitVector &Bits);
1069 bool computeUsedBits(const MachineInstr &MI, unsigned OpN, BitVector &Bits,
1070 uint16_t Begin);
1071 bool usedBitsEqual(BitTracker::RegisterRef RD, BitTracker::RegisterRef RS);
1072
1073 const HexagonInstrInfo &HII;
1074 const HexagonRegisterInfo &HRI;
1075 MachineRegisterInfo &MRI;
1076 BitTracker &BT;
1077 };
1078
1079} // end anonymous namespace
1080
1081// Check if the instruction is a lossy shift left, where the input being
1082// shifted is the operand OpN of MI. If true, [LostB, LostE) is the range
1083// of bit indices that are lost.
1084bool RedundantInstrElimination::isLossyShiftLeft(const MachineInstr &MI,
1085 unsigned OpN, unsigned &LostB, unsigned &LostE) {
1086 using namespace Hexagon;
1087
1088 unsigned Opc = MI.getOpcode();
1089 unsigned ImN, RegN, Width;
1090 switch (Opc) {
1091 case S2_asl_i_p:
1092 ImN = 2;
1093 RegN = 1;
1094 Width = 64;
1095 break;
1096 case S2_asl_i_p_acc:
1097 case S2_asl_i_p_and:
1098 case S2_asl_i_p_nac:
1099 case S2_asl_i_p_or:
1100 case S2_asl_i_p_xacc:
1101 ImN = 3;
1102 RegN = 2;
1103 Width = 64;
1104 break;
1105 case S2_asl_i_r:
1106 ImN = 2;
1107 RegN = 1;
1108 Width = 32;
1109 break;
1110 case S2_addasl_rrri:
1111 case S4_andi_asl_ri:
1112 case S4_ori_asl_ri:
1113 case S4_addi_asl_ri:
1114 case S4_subi_asl_ri:
1115 case S2_asl_i_r_acc:
1116 case S2_asl_i_r_and:
1117 case S2_asl_i_r_nac:
1118 case S2_asl_i_r_or:
1119 case S2_asl_i_r_sat:
1120 case S2_asl_i_r_xacc:
1121 ImN = 3;
1122 RegN = 2;
1123 Width = 32;
1124 break;
1125 default:
1126 return false;
1127 }
1128
1129 if (RegN != OpN)
1130 return false;
1131
1132 assert(MI.getOperand(ImN).isImm());
1133 unsigned S = MI.getOperand(i: ImN).getImm();
1134 if (S == 0)
1135 return false;
1136 LostB = Width-S;
1137 LostE = Width;
1138 return true;
1139}
1140
1141// Check if the instruction is a lossy shift right, where the input being
1142// shifted is the operand OpN of MI. If true, [LostB, LostE) is the range
1143// of bit indices that are lost.
1144bool RedundantInstrElimination::isLossyShiftRight(const MachineInstr &MI,
1145 unsigned OpN, unsigned &LostB, unsigned &LostE) {
1146 using namespace Hexagon;
1147
1148 unsigned Opc = MI.getOpcode();
1149 unsigned ImN, RegN;
1150 switch (Opc) {
1151 case S2_asr_i_p:
1152 case S2_lsr_i_p:
1153 ImN = 2;
1154 RegN = 1;
1155 break;
1156 case S2_asr_i_p_acc:
1157 case S2_asr_i_p_and:
1158 case S2_asr_i_p_nac:
1159 case S2_asr_i_p_or:
1160 case S2_lsr_i_p_acc:
1161 case S2_lsr_i_p_and:
1162 case S2_lsr_i_p_nac:
1163 case S2_lsr_i_p_or:
1164 case S2_lsr_i_p_xacc:
1165 ImN = 3;
1166 RegN = 2;
1167 break;
1168 case S2_asr_i_r:
1169 case S2_lsr_i_r:
1170 ImN = 2;
1171 RegN = 1;
1172 break;
1173 case S4_andi_lsr_ri:
1174 case S4_ori_lsr_ri:
1175 case S4_addi_lsr_ri:
1176 case S4_subi_lsr_ri:
1177 case S2_asr_i_r_acc:
1178 case S2_asr_i_r_and:
1179 case S2_asr_i_r_nac:
1180 case S2_asr_i_r_or:
1181 case S2_lsr_i_r_acc:
1182 case S2_lsr_i_r_and:
1183 case S2_lsr_i_r_nac:
1184 case S2_lsr_i_r_or:
1185 case S2_lsr_i_r_xacc:
1186 ImN = 3;
1187 RegN = 2;
1188 break;
1189
1190 default:
1191 return false;
1192 }
1193
1194 if (RegN != OpN)
1195 return false;
1196
1197 assert(MI.getOperand(ImN).isImm());
1198 unsigned S = MI.getOperand(i: ImN).getImm();
1199 LostB = 0;
1200 LostE = S;
1201 return true;
1202}
1203
1204// Calculate the bit vector that corresponds to the used bits of register Reg.
1205// The vector Bits has the same size, as the size of Reg in bits. If the cal-
1206// culation fails (i.e. the used bits are unknown), it returns false. Other-
1207// wise, it returns true and sets the corresponding bits in Bits.
1208bool RedundantInstrElimination::computeUsedBits(unsigned Reg, BitVector &Bits) {
1209 BitVector Used(Bits.size());
1210 RegisterSet Visited;
1211 std::vector<unsigned> Pending;
1212 Pending.push_back(x: Reg);
1213
1214 for (unsigned i = 0; i < Pending.size(); ++i) {
1215 unsigned R = Pending[i];
1216 if (Visited.has(R))
1217 continue;
1218 Visited.insert(R);
1219 for (auto I = MRI.use_begin(RegNo: R), E = MRI.use_end(); I != E; ++I) {
1220 BitTracker::RegisterRef UR = *I;
1221 unsigned B, W;
1222 if (!HBS::getSubregMask(RR: UR, Begin&: B, Width&: W, MRI))
1223 return false;
1224 MachineInstr &UseI = *I->getParent();
1225 if (UseI.isPHI() || UseI.isCopy()) {
1226 Register DefR = UseI.getOperand(i: 0).getReg();
1227 if (!DefR.isVirtual())
1228 return false;
1229 Pending.push_back(x: DefR);
1230 } else {
1231 if (!computeUsedBits(MI: UseI, OpN: I.getOperandNo(), Bits&: Used, Begin: B))
1232 return false;
1233 }
1234 }
1235 }
1236 Bits |= Used;
1237 return true;
1238}
1239
1240// Calculate the bits used by instruction MI in a register in operand OpN.
1241// Return true/false if the calculation succeeds/fails. If is succeeds, set
1242// used bits in Bits. This function does not reset any bits in Bits, so
1243// subsequent calls over different instructions will result in the union
1244// of the used bits in all these instructions.
1245// The register in question may be used with a sub-register, whereas Bits
1246// holds the bits for the entire register. To keep track of that, the
1247// argument Begin indicates where in Bits is the lowest-significant bit
1248// of the register used in operand OpN. For example, in instruction:
1249// %1 = S2_lsr_i_r %2:isub_hi, 10
1250// the operand 1 is a 32-bit register, which happens to be a subregister
1251// of the 64-bit register %2, and that subregister starts at position 32.
1252// In this case Begin=32, since Bits[32] would be the lowest-significant bit
1253// of %2:isub_hi.
1254bool RedundantInstrElimination::computeUsedBits(const MachineInstr &MI,
1255 unsigned OpN, BitVector &Bits, uint16_t Begin) {
1256 unsigned Opc = MI.getOpcode();
1257 BitVector T(Bits.size());
1258 bool GotBits = HBS::getUsedBits(Opc, OpN, Bits&: T, Begin, HII);
1259 // Even if we don't have bits yet, we could still provide some information
1260 // if the instruction is a lossy shift: the lost bits will be marked as
1261 // not used.
1262 unsigned LB, LE;
1263 if (isLossyShiftLeft(MI, OpN, LostB&: LB, LostE&: LE) || isLossyShiftRight(MI, OpN, LostB&: LB, LostE&: LE)) {
1264 assert(MI.getOperand(OpN).isReg());
1265 BitTracker::RegisterRef RR = MI.getOperand(i: OpN);
1266 const TargetRegisterClass *RC = HBS::getFinalVRegClass(RR, MRI);
1267 uint16_t Width = HRI.getRegSizeInBits(RC: *RC);
1268
1269 if (!GotBits)
1270 T.set(I: Begin, E: Begin+Width);
1271 assert(LB <= LE && LB < Width && LE <= Width);
1272 T.reset(I: Begin+LB, E: Begin+LE);
1273 GotBits = true;
1274 }
1275 if (GotBits)
1276 Bits |= T;
1277 return GotBits;
1278}
1279
1280// Calculates the used bits in RD ("defined register"), and checks if these
1281// bits in RS ("used register") and RD are identical.
1282bool RedundantInstrElimination::usedBitsEqual(BitTracker::RegisterRef RD,
1283 BitTracker::RegisterRef RS) {
1284 const BitTracker::RegisterCell &DC = BT.lookup(Reg: RD.Reg);
1285 const BitTracker::RegisterCell &SC = BT.lookup(Reg: RS.Reg);
1286
1287 unsigned DB, DW;
1288 if (!HBS::getSubregMask(RR: RD, Begin&: DB, Width&: DW, MRI))
1289 return false;
1290 unsigned SB, SW;
1291 if (!HBS::getSubregMask(RR: RS, Begin&: SB, Width&: SW, MRI))
1292 return false;
1293 if (SW != DW)
1294 return false;
1295
1296 BitVector Used(DC.width());
1297 if (!computeUsedBits(Reg: RD.Reg, Bits&: Used))
1298 return false;
1299
1300 for (unsigned i = 0; i != DW; ++i)
1301 if (Used[i+DB] && DC[DB+i] != SC[SB+i])
1302 return false;
1303 return true;
1304}
1305
1306bool RedundantInstrElimination::processBlock(MachineBasicBlock &B,
1307 const RegisterSet&) {
1308 if (!BT.reached(B: &B))
1309 return false;
1310 bool Changed = false;
1311
1312 for (auto I = B.begin(), E = B.end(); I != E; ++I) {
1313 MachineInstr *MI = &*I;
1314
1315 if (MI->getOpcode() == TargetOpcode::COPY)
1316 continue;
1317 if (MI->isPHI() || MI->hasUnmodeledSideEffects() || MI->isInlineAsm())
1318 continue;
1319 unsigned NumD = MI->getDesc().getNumDefs();
1320 if (NumD != 1)
1321 continue;
1322
1323 BitTracker::RegisterRef RD = MI->getOperand(i: 0);
1324 if (!BT.has(Reg: RD.Reg))
1325 continue;
1326 const BitTracker::RegisterCell &DC = BT.lookup(Reg: RD.Reg);
1327 auto At = MachineBasicBlock::iterator(MI);
1328
1329 // Find a source operand that is equal to the result.
1330 for (auto &Op : MI->uses()) {
1331 if (!Op.isReg())
1332 continue;
1333 BitTracker::RegisterRef RS = Op;
1334 if (!BT.has(Reg: RS.Reg))
1335 continue;
1336 if (!HBS::isTransparentCopy(RD, RS, MRI))
1337 continue;
1338
1339 unsigned BN, BW;
1340 if (!HBS::getSubregMask(RR: RS, Begin&: BN, Width&: BW, MRI))
1341 continue;
1342
1343 const BitTracker::RegisterCell &SC = BT.lookup(Reg: RS.Reg);
1344 if (!usedBitsEqual(RD, RS) && !HBS::isEqual(RC1: DC, B1: 0, RC2: SC, B2: BN, W: BW))
1345 continue;
1346
1347 // If found, replace the instruction with a COPY.
1348 const DebugLoc &DL = MI->getDebugLoc();
1349 const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RR: RD, MRI);
1350 Register NewR = MRI.createVirtualRegister(RegClass: FRC);
1351 MachineInstr *CopyI =
1352 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: TargetOpcode::COPY), DestReg: NewR)
1353 .addReg(RegNo: RS.Reg, Flags: {}, SubReg: RS.Sub);
1354 HBS::replaceSubWithSub(OldR: RD.Reg, OldSR: RD.Sub, NewR, NewSR: 0, MRI);
1355 // This pass can create copies between registers that don't have the
1356 // exact same values. Updating the tracker has to involve updating
1357 // all dependent cells. Example:
1358 // %1 = inst %2 ; %1 != %2, but used bits are equal
1359 //
1360 // %3 = copy %2 ; <- inserted
1361 // ... = %3 ; <- replaced from %2
1362 // Indirectly, we can create a "copy" between %1 and %2 even
1363 // though their exact values do not match.
1364 BT.visit(MI: *CopyI);
1365 Changed = true;
1366 break;
1367 }
1368 }
1369
1370 return Changed;
1371}
1372
1373namespace {
1374
1375// Recognize instructions that produce constant values known at compile-time.
1376// Replace them with register definitions that load these constants directly.
1377 class ConstGeneration : public Transformation {
1378 public:
1379 ConstGeneration(BitTracker &bt, const HexagonInstrInfo &hii,
1380 MachineRegisterInfo &mri)
1381 : Transformation(true), HII(hii), MRI(mri), BT(bt) {}
1382
1383 bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1384 static bool isTfrConst(const MachineInstr &MI);
1385
1386 private:
1387 Register genTfrConst(const TargetRegisterClass *RC, int64_t C,
1388 MachineBasicBlock &B, MachineBasicBlock::iterator At,
1389 DebugLoc &DL);
1390
1391 const HexagonInstrInfo &HII;
1392 MachineRegisterInfo &MRI;
1393 BitTracker &BT;
1394 };
1395
1396} // end anonymous namespace
1397
1398bool ConstGeneration::isTfrConst(const MachineInstr &MI) {
1399 unsigned Opc = MI.getOpcode();
1400 switch (Opc) {
1401 case Hexagon::A2_combineii:
1402 case Hexagon::A4_combineii:
1403 case Hexagon::A2_tfrsi:
1404 case Hexagon::A2_tfrpi:
1405 case Hexagon::PS_true:
1406 case Hexagon::PS_false:
1407 case Hexagon::CONST32:
1408 case Hexagon::CONST64:
1409 return true;
1410 }
1411 return false;
1412}
1413
1414// Generate a transfer-immediate instruction that is appropriate for the
1415// register class and the actual value being transferred.
1416Register ConstGeneration::genTfrConst(const TargetRegisterClass *RC, int64_t C,
1417 MachineBasicBlock &B,
1418 MachineBasicBlock::iterator At,
1419 DebugLoc &DL) {
1420 Register Reg = MRI.createVirtualRegister(RegClass: RC);
1421 if (RC == &Hexagon::IntRegsRegClass) {
1422 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: Hexagon::A2_tfrsi), DestReg: Reg)
1423 .addImm(Val: int32_t(C));
1424 return Reg;
1425 }
1426
1427 if (RC == &Hexagon::DoubleRegsRegClass) {
1428 if (isInt<8>(x: C)) {
1429 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: Hexagon::A2_tfrpi), DestReg: Reg)
1430 .addImm(Val: C);
1431 return Reg;
1432 }
1433
1434 unsigned Lo = Lo_32(Value: C), Hi = Hi_32(Value: C);
1435 if (isInt<8>(x: Lo) || isInt<8>(x: Hi)) {
1436 unsigned Opc = isInt<8>(x: Lo) ? Hexagon::A2_combineii
1437 : Hexagon::A4_combineii;
1438 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: Opc), DestReg: Reg)
1439 .addImm(Val: int32_t(Hi))
1440 .addImm(Val: int32_t(Lo));
1441 return Reg;
1442 }
1443 MachineFunction *MF = B.getParent();
1444 auto &HST = MF->getSubtarget<HexagonSubtarget>();
1445
1446 // Disable CONST64 for tiny core since it takes a LD resource.
1447 if (!HST.isTinyCore() ||
1448 MF->getFunction().hasOptSize()) {
1449 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: Hexagon::CONST64), DestReg: Reg)
1450 .addImm(Val: C);
1451 return Reg;
1452 }
1453 }
1454
1455 if (RC == &Hexagon::PredRegsRegClass) {
1456 unsigned Opc;
1457 if (C == 0)
1458 Opc = Hexagon::PS_false;
1459 else if ((C & 0xFF) == 0xFF)
1460 Opc = Hexagon::PS_true;
1461 else
1462 return 0;
1463 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: Opc), DestReg: Reg);
1464 return Reg;
1465 }
1466
1467 return 0;
1468}
1469
1470bool ConstGeneration::processBlock(MachineBasicBlock &B, const RegisterSet&) {
1471 if (!BT.reached(B: &B))
1472 return false;
1473 bool Changed = false;
1474 RegisterSet Defs;
1475
1476 for (auto I = B.begin(), E = B.end(); I != E; ++I) {
1477 if (isTfrConst(MI: *I))
1478 continue;
1479 Defs.clear();
1480 HBS::getInstrDefs(MI: *I, Defs);
1481 if (Defs.count() != 1)
1482 continue;
1483 Register DR = Defs.find_first();
1484 if (!DR.isVirtual())
1485 continue;
1486 uint64_t U;
1487 const BitTracker::RegisterCell &DRC = BT.lookup(Reg: DR);
1488 if (HBS::getConst(RC: DRC, B: 0, W: DRC.width(), U)) {
1489 int64_t C = U;
1490 DebugLoc DL = I->getDebugLoc();
1491 auto At = I->isPHI() ? B.getFirstNonPHI() : I;
1492 Register ImmReg = genTfrConst(RC: MRI.getRegClass(Reg: DR), C, B, At, DL);
1493 if (ImmReg) {
1494 HBS::replaceReg(OldR: DR, NewR: ImmReg, MRI);
1495 BT.put(RR: ImmReg, RC: DRC);
1496 Changed = true;
1497 }
1498 }
1499 }
1500 return Changed;
1501}
1502
1503namespace {
1504
1505// Identify pairs of available registers which hold identical values.
1506// In such cases, only one of them needs to be calculated, the other one
1507// will be defined as a copy of the first.
1508 class CopyGeneration : public Transformation {
1509 public:
1510 CopyGeneration(BitTracker &bt, const HexagonInstrInfo &hii,
1511 const HexagonRegisterInfo &hri, MachineRegisterInfo &mri)
1512 : Transformation(true), HII(hii), HRI(hri), MRI(mri), BT(bt) {}
1513
1514 bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1515
1516 private:
1517 bool findMatch(const BitTracker::RegisterRef &Inp,
1518 BitTracker::RegisterRef &Out, const RegisterSet &AVs);
1519
1520 const HexagonInstrInfo &HII;
1521 const HexagonRegisterInfo &HRI;
1522 MachineRegisterInfo &MRI;
1523 BitTracker &BT;
1524 RegisterSet Forbidden;
1525 };
1526
1527// Eliminate register copies RD = RS, by replacing the uses of RD with
1528// with uses of RS.
1529 class CopyPropagation : public Transformation {
1530 public:
1531 CopyPropagation(const HexagonRegisterInfo &hri, MachineRegisterInfo &mri)
1532 : Transformation(false), HRI(hri), MRI(mri) {}
1533
1534 bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1535
1536 static bool isCopyReg(unsigned Opc, bool NoConv);
1537
1538 private:
1539 bool propagateRegCopy(MachineInstr &MI);
1540
1541 const HexagonRegisterInfo &HRI;
1542 MachineRegisterInfo &MRI;
1543 };
1544
1545} // end anonymous namespace
1546
1547/// Check if there is a register in AVs that is identical to Inp. If so,
1548/// set Out to the found register. The output may be a pair Reg:Sub.
1549bool CopyGeneration::findMatch(const BitTracker::RegisterRef &Inp,
1550 BitTracker::RegisterRef &Out, const RegisterSet &AVs) {
1551 if (!BT.has(Reg: Inp.Reg))
1552 return false;
1553 const BitTracker::RegisterCell &InpRC = BT.lookup(Reg: Inp.Reg);
1554 auto *FRC = HBS::getFinalVRegClass(RR: Inp, MRI);
1555 unsigned B, W;
1556 if (!HBS::getSubregMask(RR: Inp, Begin&: B, Width&: W, MRI))
1557 return false;
1558
1559 for (Register R = AVs.find_first(); R; R = AVs.find_next(Prev: R)) {
1560 if (!BT.has(Reg: R) || Forbidden[R])
1561 continue;
1562 const BitTracker::RegisterCell &RC = BT.lookup(Reg: R);
1563 unsigned RW = RC.width();
1564 if (W == RW) {
1565 if (FRC != MRI.getRegClass(Reg: R))
1566 continue;
1567 if (!HBS::isTransparentCopy(RD: R, RS: Inp, MRI))
1568 continue;
1569 if (!HBS::isEqual(RC1: InpRC, B1: B, RC2: RC, B2: 0, W))
1570 continue;
1571 Out.Reg = R;
1572 Out.Sub = 0;
1573 return true;
1574 }
1575 // Check if there is a super-register, whose part (with a subregister)
1576 // is equal to the input.
1577 // Only do double registers for now.
1578 if (W*2 != RW)
1579 continue;
1580 if (MRI.getRegClass(Reg: R) != &Hexagon::DoubleRegsRegClass)
1581 continue;
1582
1583 if (HBS::isEqual(RC1: InpRC, B1: B, RC2: RC, B2: 0, W))
1584 Out.Sub = Hexagon::isub_lo;
1585 else if (HBS::isEqual(RC1: InpRC, B1: B, RC2: RC, B2: W, W))
1586 Out.Sub = Hexagon::isub_hi;
1587 else
1588 continue;
1589 Out.Reg = R;
1590 if (HBS::isTransparentCopy(RD: Out, RS: Inp, MRI))
1591 return true;
1592 }
1593 return false;
1594}
1595
1596bool CopyGeneration::processBlock(MachineBasicBlock &B,
1597 const RegisterSet &AVs) {
1598 if (!BT.reached(B: &B))
1599 return false;
1600 RegisterSet AVB(AVs);
1601 bool Changed = false;
1602 RegisterSet Defs;
1603
1604 for (auto I = B.begin(), E = B.end(); I != E; ++I, AVB.insert(Rs: Defs)) {
1605 Defs.clear();
1606 HBS::getInstrDefs(MI: *I, Defs);
1607
1608 unsigned Opc = I->getOpcode();
1609 if (CopyPropagation::isCopyReg(Opc, NoConv: false) ||
1610 ConstGeneration::isTfrConst(MI: *I))
1611 continue;
1612
1613 DebugLoc DL = I->getDebugLoc();
1614 auto At = I->isPHI() ? B.getFirstNonPHI() : I;
1615
1616 for (Register R = Defs.find_first(); R; R = Defs.find_next(Prev: R)) {
1617 BitTracker::RegisterRef MR;
1618 auto *FRC = HBS::getFinalVRegClass(RR: R, MRI);
1619
1620 if (findMatch(Inp: R, Out&: MR, AVs: AVB)) {
1621 Register NewR = MRI.createVirtualRegister(RegClass: FRC);
1622 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: TargetOpcode::COPY), DestReg: NewR)
1623 .addReg(RegNo: MR.Reg, Flags: {}, SubReg: MR.Sub);
1624 BT.put(RR: BitTracker::RegisterRef(NewR), RC: BT.get(RR: MR));
1625 HBS::replaceReg(OldR: R, NewR, MRI);
1626 Forbidden.insert(R);
1627 continue;
1628 }
1629
1630 if (FRC == &Hexagon::DoubleRegsRegClass ||
1631 FRC == &Hexagon::HvxWRRegClass) {
1632 // Try to generate REG_SEQUENCE.
1633 unsigned SubLo = HRI.getHexagonSubRegIndex(RC: *FRC, GenIdx: Hexagon::ps_sub_lo);
1634 unsigned SubHi = HRI.getHexagonSubRegIndex(RC: *FRC, GenIdx: Hexagon::ps_sub_hi);
1635 BitTracker::RegisterRef TL = { R, SubLo };
1636 BitTracker::RegisterRef TH = { R, SubHi };
1637 BitTracker::RegisterRef ML, MH;
1638 if (findMatch(Inp: TL, Out&: ML, AVs: AVB) && findMatch(Inp: TH, Out&: MH, AVs: AVB)) {
1639 auto *FRC = HBS::getFinalVRegClass(RR: R, MRI);
1640 Register NewR = MRI.createVirtualRegister(RegClass: FRC);
1641 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: TargetOpcode::REG_SEQUENCE), DestReg: NewR)
1642 .addReg(RegNo: ML.Reg, Flags: {}, SubReg: ML.Sub)
1643 .addImm(Val: SubLo)
1644 .addReg(RegNo: MH.Reg, Flags: {}, SubReg: MH.Sub)
1645 .addImm(Val: SubHi);
1646 BT.put(RR: BitTracker::RegisterRef(NewR), RC: BT.get(RR: R));
1647 HBS::replaceReg(OldR: R, NewR, MRI);
1648 Forbidden.insert(R);
1649 }
1650 }
1651 }
1652 }
1653
1654 return Changed;
1655}
1656
1657bool CopyPropagation::isCopyReg(unsigned Opc, bool NoConv) {
1658 switch (Opc) {
1659 case TargetOpcode::COPY:
1660 case TargetOpcode::REG_SEQUENCE:
1661 case Hexagon::A4_combineir:
1662 case Hexagon::A4_combineri:
1663 return true;
1664 case Hexagon::A2_tfr:
1665 case Hexagon::A2_tfrp:
1666 case Hexagon::A2_combinew:
1667 case Hexagon::V6_vcombine:
1668 return NoConv;
1669 default:
1670 break;
1671 }
1672 return false;
1673}
1674
1675bool CopyPropagation::propagateRegCopy(MachineInstr &MI) {
1676 bool Changed = false;
1677 unsigned Opc = MI.getOpcode();
1678 BitTracker::RegisterRef RD = MI.getOperand(i: 0);
1679 assert(MI.getOperand(0).getSubReg() == 0);
1680
1681 switch (Opc) {
1682 case TargetOpcode::COPY:
1683 case Hexagon::A2_tfr:
1684 case Hexagon::A2_tfrp: {
1685 BitTracker::RegisterRef RS = MI.getOperand(i: 1);
1686 if (!HBS::isTransparentCopy(RD, RS, MRI))
1687 break;
1688 if (RS.Sub != 0)
1689 Changed = HBS::replaceRegWithSub(OldR: RD.Reg, NewR: RS.Reg, NewSR: RS.Sub, MRI);
1690 else
1691 Changed = HBS::replaceReg(OldR: RD.Reg, NewR: RS.Reg, MRI);
1692 break;
1693 }
1694 case TargetOpcode::REG_SEQUENCE: {
1695 BitTracker::RegisterRef SL, SH;
1696 if (HBS::parseRegSequence(I: MI, SL, SH, MRI)) {
1697 const TargetRegisterClass &RC = *MRI.getRegClass(Reg: RD.Reg);
1698 unsigned SubLo = HRI.getHexagonSubRegIndex(RC, GenIdx: Hexagon::ps_sub_lo);
1699 unsigned SubHi = HRI.getHexagonSubRegIndex(RC, GenIdx: Hexagon::ps_sub_hi);
1700 Changed = HBS::replaceSubWithSub(OldR: RD.Reg, OldSR: SubLo, NewR: SL.Reg, NewSR: SL.Sub, MRI);
1701 Changed |= HBS::replaceSubWithSub(OldR: RD.Reg, OldSR: SubHi, NewR: SH.Reg, NewSR: SH.Sub, MRI);
1702 }
1703 break;
1704 }
1705 case Hexagon::A2_combinew:
1706 case Hexagon::V6_vcombine: {
1707 const TargetRegisterClass &RC = *MRI.getRegClass(Reg: RD.Reg);
1708 unsigned SubLo = HRI.getHexagonSubRegIndex(RC, GenIdx: Hexagon::ps_sub_lo);
1709 unsigned SubHi = HRI.getHexagonSubRegIndex(RC, GenIdx: Hexagon::ps_sub_hi);
1710 BitTracker::RegisterRef RH = MI.getOperand(i: 1), RL = MI.getOperand(i: 2);
1711 Changed = HBS::replaceSubWithSub(OldR: RD.Reg, OldSR: SubLo, NewR: RL.Reg, NewSR: RL.Sub, MRI);
1712 Changed |= HBS::replaceSubWithSub(OldR: RD.Reg, OldSR: SubHi, NewR: RH.Reg, NewSR: RH.Sub, MRI);
1713 break;
1714 }
1715 case Hexagon::A4_combineir:
1716 case Hexagon::A4_combineri: {
1717 unsigned SrcX = (Opc == Hexagon::A4_combineir) ? 2 : 1;
1718 unsigned Sub = (Opc == Hexagon::A4_combineir) ? Hexagon::isub_lo
1719 : Hexagon::isub_hi;
1720 BitTracker::RegisterRef RS = MI.getOperand(i: SrcX);
1721 Changed = HBS::replaceSubWithSub(OldR: RD.Reg, OldSR: Sub, NewR: RS.Reg, NewSR: RS.Sub, MRI);
1722 break;
1723 }
1724 }
1725 return Changed;
1726}
1727
1728bool CopyPropagation::processBlock(MachineBasicBlock &B, const RegisterSet&) {
1729 std::vector<MachineInstr*> Instrs;
1730 for (MachineInstr &MI : llvm::reverse(C&: B))
1731 Instrs.push_back(x: &MI);
1732
1733 bool Changed = false;
1734 for (auto *I : Instrs) {
1735 unsigned Opc = I->getOpcode();
1736 if (!CopyPropagation::isCopyReg(Opc, NoConv: true))
1737 continue;
1738 Changed |= propagateRegCopy(MI&: *I);
1739 }
1740
1741 return Changed;
1742}
1743
1744namespace {
1745
1746// Recognize patterns that can be simplified and replace them with the
1747// simpler forms.
1748// This is by no means complete
1749 class BitSimplification : public Transformation {
1750 public:
1751 BitSimplification(BitTracker &bt, const MachineDominatorTree &mdt,
1752 const HexagonInstrInfo &hii,
1753 const HexagonRegisterInfo &hri, MachineRegisterInfo &mri,
1754 MachineFunction &mf)
1755 : Transformation(true), MDT(mdt), HII(hii), HRI(hri), MRI(mri), BT(bt) {
1756 }
1757
1758 bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1759
1760 private:
1761 struct RegHalf : public BitTracker::RegisterRef {
1762 bool Low; // Low/High halfword.
1763 };
1764
1765 bool matchHalf(unsigned SelfR, const BitTracker::RegisterCell &RC,
1766 unsigned B, RegHalf &RH);
1767 bool validateReg(BitTracker::RegisterRef R, unsigned Opc, unsigned OpNum);
1768
1769 bool matchPackhl(unsigned SelfR, const BitTracker::RegisterCell &RC,
1770 BitTracker::RegisterRef &Rs, BitTracker::RegisterRef &Rt);
1771 unsigned getCombineOpcode(bool HLow, bool LLow);
1772
1773 bool genStoreUpperHalf(MachineInstr *MI);
1774 bool genStoreImmediate(MachineInstr *MI);
1775 bool genPackhl(MachineInstr *MI, BitTracker::RegisterRef RD,
1776 const BitTracker::RegisterCell &RC);
1777 bool genExtractHalf(MachineInstr *MI, BitTracker::RegisterRef RD,
1778 const BitTracker::RegisterCell &RC);
1779 bool genCombineHalf(MachineInstr *MI, BitTracker::RegisterRef RD,
1780 const BitTracker::RegisterCell &RC);
1781 bool genExtractLow(MachineInstr *MI, BitTracker::RegisterRef RD,
1782 const BitTracker::RegisterCell &RC);
1783 bool genBitSplit(MachineInstr *MI, BitTracker::RegisterRef RD,
1784 const BitTracker::RegisterCell &RC, const RegisterSet &AVs);
1785 bool simplifyTstbit(MachineInstr *MI, BitTracker::RegisterRef RD,
1786 const BitTracker::RegisterCell &RC);
1787 bool simplifyExtractLow(MachineInstr *MI, BitTracker::RegisterRef RD,
1788 const BitTracker::RegisterCell &RC, const RegisterSet &AVs);
1789 bool simplifyRCmp0(MachineInstr *MI, BitTracker::RegisterRef RD);
1790
1791 // Cache of created instructions to avoid creating duplicates.
1792 // XXX Currently only used by genBitSplit.
1793 std::vector<MachineInstr*> NewMIs;
1794
1795 const MachineDominatorTree &MDT;
1796 const HexagonInstrInfo &HII;
1797 [[maybe_unused]] const HexagonRegisterInfo &HRI;
1798 MachineRegisterInfo &MRI;
1799 BitTracker &BT;
1800 };
1801
1802} // end anonymous namespace
1803
1804// Check if the bits [B..B+16) in register cell RC form a valid halfword,
1805// i.e. [0..16), [16..32), etc. of some register. If so, return true and
1806// set the information about the found register in RH.
1807bool BitSimplification::matchHalf(unsigned SelfR,
1808 const BitTracker::RegisterCell &RC, unsigned B, RegHalf &RH) {
1809 // XXX This could be searching in the set of available registers, in case
1810 // the match is not exact.
1811
1812 // Match 16-bit chunks, where the RC[B..B+15] references exactly one
1813 // register and all the bits B..B+15 match between RC and the register.
1814 // This is meant to match "v1[0-15]", where v1 = { [0]:0 [1-15]:v1... },
1815 // and RC = { [0]:0 [1-15]:v1[1-15]... }.
1816 bool Low = false;
1817 unsigned I = B;
1818 while (I < B+16 && RC[I].num())
1819 I++;
1820 if (I == B+16)
1821 return false;
1822
1823 Register Reg = RC[I].RefI.Reg;
1824 unsigned P = RC[I].RefI.Pos; // The RefI.Pos will be advanced by I-B.
1825 if (P < I-B)
1826 return false;
1827 unsigned Pos = P - (I-B);
1828
1829 if (Reg == 0 || Reg == SelfR) // Don't match "self".
1830 return false;
1831 if (!Reg.isVirtual())
1832 return false;
1833 if (!BT.has(Reg))
1834 return false;
1835
1836 const BitTracker::RegisterCell &SC = BT.lookup(Reg);
1837 if (Pos+16 > SC.width())
1838 return false;
1839
1840 for (unsigned i = 0; i < 16; ++i) {
1841 const BitTracker::BitValue &RV = RC[i+B];
1842 if (RV.Type == BitTracker::BitValue::Ref) {
1843 if (RV.RefI.Reg != Reg)
1844 return false;
1845 if (RV.RefI.Pos != i+Pos)
1846 return false;
1847 continue;
1848 }
1849 if (RC[i+B] != SC[i+Pos])
1850 return false;
1851 }
1852
1853 unsigned Sub = 0;
1854 switch (Pos) {
1855 case 0:
1856 Sub = Hexagon::isub_lo;
1857 Low = true;
1858 break;
1859 case 16:
1860 Sub = Hexagon::isub_lo;
1861 Low = false;
1862 break;
1863 case 32:
1864 Sub = Hexagon::isub_hi;
1865 Low = true;
1866 break;
1867 case 48:
1868 Sub = Hexagon::isub_hi;
1869 Low = false;
1870 break;
1871 default:
1872 return false;
1873 }
1874
1875 RH.Reg = Reg;
1876 RH.Sub = Sub;
1877 RH.Low = Low;
1878 // If the subregister is not valid with the register, set it to 0.
1879 if (!HBS::getFinalVRegClass(RR: RH, MRI))
1880 RH.Sub = 0;
1881
1882 return true;
1883}
1884
1885bool BitSimplification::validateReg(BitTracker::RegisterRef R, unsigned Opc,
1886 unsigned OpNum) {
1887 auto *OpRC = HII.getRegClass(MCID: HII.get(Opcode: Opc), OpNum);
1888 auto *RRC = HBS::getFinalVRegClass(RR: R, MRI);
1889 return OpRC->hasSubClassEq(RC: RRC);
1890}
1891
1892// Check if RC matches the pattern of a S2_packhl. If so, return true and
1893// set the inputs Rs and Rt.
1894bool BitSimplification::matchPackhl(unsigned SelfR,
1895 const BitTracker::RegisterCell &RC, BitTracker::RegisterRef &Rs,
1896 BitTracker::RegisterRef &Rt) {
1897 RegHalf L1, H1, L2, H2;
1898
1899 if (!matchHalf(SelfR, RC, B: 0, RH&: L2) || !matchHalf(SelfR, RC, B: 16, RH&: L1))
1900 return false;
1901 if (!matchHalf(SelfR, RC, B: 32, RH&: H2) || !matchHalf(SelfR, RC, B: 48, RH&: H1))
1902 return false;
1903
1904 // Rs = H1.L1, Rt = H2.L2
1905 if (H1.Reg != L1.Reg || H1.Sub != L1.Sub || H1.Low || !L1.Low)
1906 return false;
1907 if (H2.Reg != L2.Reg || H2.Sub != L2.Sub || H2.Low || !L2.Low)
1908 return false;
1909
1910 Rs = H1;
1911 Rt = H2;
1912 return true;
1913}
1914
1915unsigned BitSimplification::getCombineOpcode(bool HLow, bool LLow) {
1916 return HLow ? LLow ? Hexagon::A2_combine_ll
1917 : Hexagon::A2_combine_lh
1918 : LLow ? Hexagon::A2_combine_hl
1919 : Hexagon::A2_combine_hh;
1920}
1921
1922// If MI stores the upper halfword of a register (potentially obtained via
1923// shifts or extracts), replace it with a storerf instruction. This could
1924// cause the "extraction" code to become dead.
1925bool BitSimplification::genStoreUpperHalf(MachineInstr *MI) {
1926 unsigned Opc = MI->getOpcode();
1927 if (Opc != Hexagon::S2_storerh_io)
1928 return false;
1929
1930 MachineOperand &ValOp = MI->getOperand(i: 2);
1931 BitTracker::RegisterRef RS = ValOp;
1932 if (!BT.has(Reg: RS.Reg))
1933 return false;
1934 const BitTracker::RegisterCell &RC = BT.lookup(Reg: RS.Reg);
1935 RegHalf H;
1936 unsigned B = (RS.Sub == Hexagon::isub_hi) ? 32 : 0;
1937 if (!matchHalf(SelfR: 0, RC, B, RH&: H))
1938 return false;
1939 if (H.Low)
1940 return false;
1941 MI->setDesc(HII.get(Opcode: Hexagon::S2_storerf_io));
1942 ValOp.setReg(H.Reg);
1943 ValOp.setSubReg(H.Sub);
1944 return true;
1945}
1946
1947// If MI stores a value known at compile-time, and the value is within a range
1948// that avoids using constant-extenders, replace it with a store-immediate.
1949bool BitSimplification::genStoreImmediate(MachineInstr *MI) {
1950 unsigned Opc = MI->getOpcode();
1951 unsigned Align = 0;
1952 switch (Opc) {
1953 case Hexagon::S2_storeri_io:
1954 Align++;
1955 [[fallthrough]];
1956 case Hexagon::S2_storerh_io:
1957 Align++;
1958 [[fallthrough]];
1959 case Hexagon::S2_storerb_io:
1960 break;
1961 default:
1962 return false;
1963 }
1964
1965 // Avoid stores to frame-indices (due to an unknown offset).
1966 if (!MI->getOperand(i: 0).isReg())
1967 return false;
1968 MachineOperand &OffOp = MI->getOperand(i: 1);
1969 if (!OffOp.isImm())
1970 return false;
1971
1972 int64_t Off = OffOp.getImm();
1973 // Offset is u6:a. Sadly, there is no isShiftedUInt(n,x).
1974 if (!isUIntN(N: 6+Align, x: Off) || (Off & ((1<<Align)-1)))
1975 return false;
1976 // Source register:
1977 BitTracker::RegisterRef RS = MI->getOperand(i: 2);
1978 if (!BT.has(Reg: RS.Reg))
1979 return false;
1980 const BitTracker::RegisterCell &RC = BT.lookup(Reg: RS.Reg);
1981 uint64_t U;
1982 if (!HBS::getConst(RC, B: 0, W: RC.width(), U))
1983 return false;
1984
1985 // Only consider 8-bit values to avoid constant-extenders.
1986 int V;
1987 switch (Opc) {
1988 case Hexagon::S2_storerb_io:
1989 V = int8_t(U);
1990 break;
1991 case Hexagon::S2_storerh_io:
1992 V = int16_t(U);
1993 break;
1994 case Hexagon::S2_storeri_io:
1995 V = int32_t(U);
1996 break;
1997 default:
1998 // Opc is already checked above to be one of the three store instructions.
1999 // This silences a -Wuninitialized false positive on GCC 5.4.
2000 llvm_unreachable("Unexpected store opcode");
2001 }
2002 if (!isInt<8>(x: V))
2003 return false;
2004
2005 MI->removeOperand(OpNo: 2);
2006 switch (Opc) {
2007 case Hexagon::S2_storerb_io:
2008 MI->setDesc(HII.get(Opcode: Hexagon::S4_storeirb_io));
2009 break;
2010 case Hexagon::S2_storerh_io:
2011 MI->setDesc(HII.get(Opcode: Hexagon::S4_storeirh_io));
2012 break;
2013 case Hexagon::S2_storeri_io:
2014 MI->setDesc(HII.get(Opcode: Hexagon::S4_storeiri_io));
2015 break;
2016 }
2017 MI->addOperand(Op: MachineOperand::CreateImm(Val: V));
2018 return true;
2019}
2020
2021// If MI is equivalent o S2_packhl, generate the S2_packhl. MI could be the
2022// last instruction in a sequence that results in something equivalent to
2023// the pack-halfwords. The intent is to cause the entire sequence to become
2024// dead.
2025bool BitSimplification::genPackhl(MachineInstr *MI,
2026 BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2027 unsigned Opc = MI->getOpcode();
2028 if (Opc == Hexagon::S2_packhl)
2029 return false;
2030 BitTracker::RegisterRef Rs, Rt;
2031 if (!matchPackhl(SelfR: RD.Reg, RC, Rs, Rt))
2032 return false;
2033 if (!validateReg(R: Rs, Opc: Hexagon::S2_packhl, OpNum: 1) ||
2034 !validateReg(R: Rt, Opc: Hexagon::S2_packhl, OpNum: 2))
2035 return false;
2036
2037 MachineBasicBlock &B = *MI->getParent();
2038 Register NewR = MRI.createVirtualRegister(RegClass: &Hexagon::DoubleRegsRegClass);
2039 DebugLoc DL = MI->getDebugLoc();
2040 auto At = MI->isPHI() ? B.getFirstNonPHI()
2041 : MachineBasicBlock::iterator(MI);
2042 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: Hexagon::S2_packhl), DestReg: NewR)
2043 .addReg(RegNo: Rs.Reg, Flags: {}, SubReg: Rs.Sub)
2044 .addReg(RegNo: Rt.Reg, Flags: {}, SubReg: Rt.Sub);
2045 HBS::replaceSubWithSub(OldR: RD.Reg, OldSR: RD.Sub, NewR, NewSR: 0, MRI);
2046 BT.put(RR: BitTracker::RegisterRef(NewR), RC);
2047 return true;
2048}
2049
2050// If MI produces halfword of the input in the low half of the output,
2051// replace it with zero-extend or extractu.
2052bool BitSimplification::genExtractHalf(MachineInstr *MI,
2053 BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2054 RegHalf L;
2055 // Check for halfword in low 16 bits, zeros elsewhere.
2056 if (!matchHalf(SelfR: RD.Reg, RC, B: 0, RH&: L) || !HBS::isZero(RC, B: 16, W: 16))
2057 return false;
2058
2059 unsigned Opc = MI->getOpcode();
2060 MachineBasicBlock &B = *MI->getParent();
2061 DebugLoc DL = MI->getDebugLoc();
2062
2063 // Prefer zxth, since zxth can go in any slot, while extractu only in
2064 // slots 2 and 3.
2065 unsigned NewR = 0;
2066 auto At = MI->isPHI() ? B.getFirstNonPHI()
2067 : MachineBasicBlock::iterator(MI);
2068 if (L.Low && Opc != Hexagon::A2_zxth) {
2069 if (validateReg(R: L, Opc: Hexagon::A2_zxth, OpNum: 1)) {
2070 NewR = MRI.createVirtualRegister(RegClass: &Hexagon::IntRegsRegClass);
2071 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: Hexagon::A2_zxth), DestReg: NewR)
2072 .addReg(RegNo: L.Reg, Flags: {}, SubReg: L.Sub);
2073 }
2074 } else if (!L.Low && Opc != Hexagon::S2_lsr_i_r) {
2075 if (validateReg(R: L, Opc: Hexagon::S2_lsr_i_r, OpNum: 1)) {
2076 NewR = MRI.createVirtualRegister(RegClass: &Hexagon::IntRegsRegClass);
2077 BuildMI(BB&: B, I: MI, MIMD: DL, MCID: HII.get(Opcode: Hexagon::S2_lsr_i_r), DestReg: NewR)
2078 .addReg(RegNo: L.Reg, Flags: {}, SubReg: L.Sub)
2079 .addImm(Val: 16);
2080 }
2081 }
2082 if (NewR == 0)
2083 return false;
2084 HBS::replaceSubWithSub(OldR: RD.Reg, OldSR: RD.Sub, NewR, NewSR: 0, MRI);
2085 BT.put(RR: BitTracker::RegisterRef(NewR), RC);
2086 return true;
2087}
2088
2089// If MI is equivalent to a combine(.L/.H, .L/.H) replace with with the
2090// combine.
2091bool BitSimplification::genCombineHalf(MachineInstr *MI,
2092 BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2093 RegHalf L, H;
2094 // Check for combine h/l
2095 if (!matchHalf(SelfR: RD.Reg, RC, B: 0, RH&: L) || !matchHalf(SelfR: RD.Reg, RC, B: 16, RH&: H))
2096 return false;
2097 // Do nothing if this is just a reg copy.
2098 if (L.Reg == H.Reg && L.Sub == H.Sub && !H.Low && L.Low)
2099 return false;
2100
2101 unsigned Opc = MI->getOpcode();
2102 unsigned COpc = getCombineOpcode(HLow: H.Low, LLow: L.Low);
2103 if (COpc == Opc)
2104 return false;
2105 if (!validateReg(R: H, Opc: COpc, OpNum: 1) || !validateReg(R: L, Opc: COpc, OpNum: 2))
2106 return false;
2107
2108 MachineBasicBlock &B = *MI->getParent();
2109 DebugLoc DL = MI->getDebugLoc();
2110 Register NewR = MRI.createVirtualRegister(RegClass: &Hexagon::IntRegsRegClass);
2111 auto At = MI->isPHI() ? B.getFirstNonPHI()
2112 : MachineBasicBlock::iterator(MI);
2113 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: COpc), DestReg: NewR)
2114 .addReg(RegNo: H.Reg, Flags: {}, SubReg: H.Sub)
2115 .addReg(RegNo: L.Reg, Flags: {}, SubReg: L.Sub);
2116 HBS::replaceSubWithSub(OldR: RD.Reg, OldSR: RD.Sub, NewR, NewSR: 0, MRI);
2117 BT.put(RR: BitTracker::RegisterRef(NewR), RC);
2118 return true;
2119}
2120
2121// If MI resets high bits of a register and keeps the lower ones, replace it
2122// with zero-extend byte/half, and-immediate, or extractu, as appropriate.
2123bool BitSimplification::genExtractLow(MachineInstr *MI,
2124 BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2125 unsigned Opc = MI->getOpcode();
2126 switch (Opc) {
2127 case Hexagon::A2_zxtb:
2128 case Hexagon::A2_zxth:
2129 case Hexagon::S2_extractu:
2130 return false;
2131 }
2132 if (Opc == Hexagon::A2_andir && MI->getOperand(i: 2).isImm()) {
2133 int32_t Imm = MI->getOperand(i: 2).getImm();
2134 if (isInt<10>(x: Imm))
2135 return false;
2136 }
2137
2138 if (MI->hasUnmodeledSideEffects() || MI->isInlineAsm())
2139 return false;
2140 unsigned W = RC.width();
2141 while (W > 0 && RC[W-1].is(T: 0))
2142 W--;
2143 if (W == 0 || W == RC.width())
2144 return false;
2145 unsigned NewOpc = (W == 8) ? Hexagon::A2_zxtb
2146 : (W == 16) ? Hexagon::A2_zxth
2147 : (W < 10) ? Hexagon::A2_andir
2148 : Hexagon::S2_extractu;
2149 MachineBasicBlock &B = *MI->getParent();
2150 DebugLoc DL = MI->getDebugLoc();
2151
2152 for (auto &Op : MI->uses()) {
2153 if (!Op.isReg())
2154 continue;
2155 BitTracker::RegisterRef RS = Op;
2156 if (!BT.has(Reg: RS.Reg))
2157 continue;
2158 const BitTracker::RegisterCell &SC = BT.lookup(Reg: RS.Reg);
2159 unsigned BN, BW;
2160 if (!HBS::getSubregMask(RR: RS, Begin&: BN, Width&: BW, MRI))
2161 continue;
2162 if (BW < W || !HBS::isEqual(RC1: RC, B1: 0, RC2: SC, B2: BN, W))
2163 continue;
2164 if (!validateReg(R: RS, Opc: NewOpc, OpNum: 1))
2165 continue;
2166
2167 Register NewR = MRI.createVirtualRegister(RegClass: &Hexagon::IntRegsRegClass);
2168 auto At = MI->isPHI() ? B.getFirstNonPHI()
2169 : MachineBasicBlock::iterator(MI);
2170 auto MIB =
2171 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: NewOpc), DestReg: NewR).addReg(RegNo: RS.Reg, Flags: {}, SubReg: RS.Sub);
2172 if (NewOpc == Hexagon::A2_andir)
2173 MIB.addImm(Val: (1 << W) - 1);
2174 else if (NewOpc == Hexagon::S2_extractu)
2175 MIB.addImm(Val: W).addImm(Val: 0);
2176 HBS::replaceSubWithSub(OldR: RD.Reg, OldSR: RD.Sub, NewR, NewSR: 0, MRI);
2177 BT.put(RR: BitTracker::RegisterRef(NewR), RC);
2178 return true;
2179 }
2180 return false;
2181}
2182
2183bool BitSimplification::genBitSplit(MachineInstr *MI,
2184 BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC,
2185 const RegisterSet &AVs) {
2186 if (!GenBitSplit)
2187 return false;
2188 if (MaxBitSplit.getNumOccurrences()) {
2189 if (CountBitSplit >= MaxBitSplit)
2190 return false;
2191 }
2192
2193 unsigned Opc = MI->getOpcode();
2194 switch (Opc) {
2195 case Hexagon::A4_bitsplit:
2196 case Hexagon::A4_bitspliti:
2197 return false;
2198 }
2199
2200 unsigned W = RC.width();
2201 if (W != 32)
2202 return false;
2203
2204 auto ctlz = [] (const BitTracker::RegisterCell &C) -> unsigned {
2205 unsigned Z = C.width();
2206 while (Z > 0 && C[Z-1].is(T: 0))
2207 --Z;
2208 return C.width() - Z;
2209 };
2210
2211 // Count the number of leading zeros in the target RC.
2212 unsigned Z = ctlz(RC);
2213 if (Z == 0 || Z == W)
2214 return false;
2215
2216 // A simplistic analysis: assume the source register (the one being split)
2217 // is fully unknown, and that all its bits are self-references.
2218 const BitTracker::BitValue &B0 = RC[0];
2219 if (B0.Type != BitTracker::BitValue::Ref)
2220 return false;
2221
2222 unsigned SrcR = B0.RefI.Reg;
2223 unsigned SrcSR = 0;
2224 unsigned Pos = B0.RefI.Pos;
2225
2226 // All the non-zero bits should be consecutive bits from the same register.
2227 for (unsigned i = 1; i < W-Z; ++i) {
2228 const BitTracker::BitValue &V = RC[i];
2229 if (V.Type != BitTracker::BitValue::Ref)
2230 return false;
2231 if (V.RefI.Reg != SrcR || V.RefI.Pos != Pos+i)
2232 return false;
2233 }
2234
2235 // Now, find the other bitfield among AVs.
2236 for (unsigned S = AVs.find_first(); S; S = AVs.find_next(Prev: S)) {
2237 // The number of leading zeros here should be the number of trailing
2238 // non-zeros in RC.
2239 unsigned SRC = MRI.getRegClass(Reg: S)->getID();
2240 if (SRC != Hexagon::IntRegsRegClassID &&
2241 SRC != Hexagon::DoubleRegsRegClassID)
2242 continue;
2243 if (!BT.has(Reg: S))
2244 continue;
2245 const BitTracker::RegisterCell &SC = BT.lookup(Reg: S);
2246 if (SC.width() != W || ctlz(SC) != W-Z)
2247 continue;
2248 // The Z lower bits should now match SrcR.
2249 const BitTracker::BitValue &S0 = SC[0];
2250 if (S0.Type != BitTracker::BitValue::Ref || S0.RefI.Reg != SrcR)
2251 continue;
2252 unsigned P = S0.RefI.Pos;
2253
2254 if (Pos <= P && (Pos + W-Z) != P)
2255 continue;
2256 if (P < Pos && (P + Z) != Pos)
2257 continue;
2258 // The starting bitfield position must be at a subregister boundary.
2259 if (std::min(a: P, b: Pos) != 0 && std::min(a: P, b: Pos) != 32)
2260 continue;
2261
2262 unsigned I;
2263 for (I = 1; I < Z; ++I) {
2264 const BitTracker::BitValue &V = SC[I];
2265 if (V.Type != BitTracker::BitValue::Ref)
2266 break;
2267 if (V.RefI.Reg != SrcR || V.RefI.Pos != P+I)
2268 break;
2269 }
2270 if (I != Z)
2271 continue;
2272
2273 // Generate bitsplit where S is defined.
2274 if (MaxBitSplit.getNumOccurrences())
2275 CountBitSplit++;
2276 MachineInstr *DefS = MRI.getVRegDef(Reg: S);
2277 assert(DefS != nullptr);
2278 DebugLoc DL = DefS->getDebugLoc();
2279 MachineBasicBlock &B = *DefS->getParent();
2280 auto At = DefS->isPHI() ? B.getFirstNonPHI()
2281 : MachineBasicBlock::iterator(DefS);
2282 if (MRI.getRegClass(Reg: SrcR)->getID() == Hexagon::DoubleRegsRegClassID)
2283 SrcSR = (std::min(a: Pos, b: P) == 32) ? Hexagon::isub_hi : Hexagon::isub_lo;
2284 if (!validateReg(R: {SrcR,SrcSR}, Opc: Hexagon::A4_bitspliti, OpNum: 1))
2285 continue;
2286 unsigned ImmOp = Pos <= P ? W-Z : Z;
2287
2288 // Find an existing bitsplit instruction if one already exists.
2289 unsigned NewR = 0;
2290 for (MachineInstr *In : NewMIs) {
2291 if (In->getOpcode() != Hexagon::A4_bitspliti)
2292 continue;
2293 MachineOperand &Op1 = In->getOperand(i: 1);
2294 if (Op1.getReg() != SrcR || Op1.getSubReg() != SrcSR)
2295 continue;
2296 if (In->getOperand(i: 2).getImm() != ImmOp)
2297 continue;
2298 // Check if the target register is available here.
2299 MachineOperand &Op0 = In->getOperand(i: 0);
2300 MachineInstr *DefI = MRI.getVRegDef(Reg: Op0.getReg());
2301 assert(DefI != nullptr);
2302 if (!MDT.dominates(A: DefI, B: &*At))
2303 continue;
2304
2305 // Found one that can be reused.
2306 assert(Op0.getSubReg() == 0);
2307 NewR = Op0.getReg();
2308 break;
2309 }
2310 if (!NewR) {
2311 NewR = MRI.createVirtualRegister(RegClass: &Hexagon::DoubleRegsRegClass);
2312 auto NewBS = BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: Hexagon::A4_bitspliti), DestReg: NewR)
2313 .addReg(RegNo: SrcR, Flags: {}, SubReg: SrcSR)
2314 .addImm(Val: ImmOp);
2315 NewMIs.push_back(x: NewBS);
2316 }
2317 if (Pos <= P) {
2318 HBS::replaceRegWithSub(OldR: RD.Reg, NewR, NewSR: Hexagon::isub_lo, MRI);
2319 HBS::replaceRegWithSub(OldR: S, NewR, NewSR: Hexagon::isub_hi, MRI);
2320 } else {
2321 HBS::replaceRegWithSub(OldR: S, NewR, NewSR: Hexagon::isub_lo, MRI);
2322 HBS::replaceRegWithSub(OldR: RD.Reg, NewR, NewSR: Hexagon::isub_hi, MRI);
2323 }
2324 return true;
2325 }
2326
2327 return false;
2328}
2329
2330// Check for tstbit simplification opportunity, where the bit being checked
2331// can be tracked back to another register. For example:
2332// %2 = S2_lsr_i_r %1, 5
2333// %3 = S2_tstbit_i %2, 0
2334// =>
2335// %3 = S2_tstbit_i %1, 5
2336bool BitSimplification::simplifyTstbit(MachineInstr *MI,
2337 BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2338 unsigned Opc = MI->getOpcode();
2339 if (Opc != Hexagon::S2_tstbit_i)
2340 return false;
2341
2342 unsigned BN = MI->getOperand(i: 2).getImm();
2343 BitTracker::RegisterRef RS = MI->getOperand(i: 1);
2344 unsigned F, W;
2345 DebugLoc DL = MI->getDebugLoc();
2346 if (!BT.has(Reg: RS.Reg) || !HBS::getSubregMask(RR: RS, Begin&: F, Width&: W, MRI))
2347 return false;
2348 MachineBasicBlock &B = *MI->getParent();
2349 auto At = MI->isPHI() ? B.getFirstNonPHI()
2350 : MachineBasicBlock::iterator(MI);
2351
2352 const BitTracker::RegisterCell &SC = BT.lookup(Reg: RS.Reg);
2353 const BitTracker::BitValue &V = SC[F+BN];
2354 if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg != RS.Reg) {
2355 const TargetRegisterClass *TC = MRI.getRegClass(Reg: V.RefI.Reg);
2356 // Need to map V.RefI.Reg to a 32-bit register, i.e. if it is
2357 // a double register, need to use a subregister and adjust bit
2358 // number.
2359 unsigned P = std::numeric_limits<unsigned>::max();
2360 BitTracker::RegisterRef RR(V.RefI.Reg, 0);
2361 if (TC == &Hexagon::DoubleRegsRegClass) {
2362 P = V.RefI.Pos;
2363 RR.Sub = Hexagon::isub_lo;
2364 if (P >= 32) {
2365 P -= 32;
2366 RR.Sub = Hexagon::isub_hi;
2367 }
2368 } else if (TC == &Hexagon::IntRegsRegClass) {
2369 P = V.RefI.Pos;
2370 }
2371 if (P != std::numeric_limits<unsigned>::max()) {
2372 Register NewR = MRI.createVirtualRegister(RegClass: &Hexagon::PredRegsRegClass);
2373 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: Hexagon::S2_tstbit_i), DestReg: NewR)
2374 .addReg(RegNo: RR.Reg, Flags: {}, SubReg: RR.Sub)
2375 .addImm(Val: P);
2376 HBS::replaceReg(OldR: RD.Reg, NewR, MRI);
2377 BT.put(RR: NewR, RC);
2378 return true;
2379 }
2380 } else if (V.is(T: 0) || V.is(T: 1)) {
2381 Register NewR = MRI.createVirtualRegister(RegClass: &Hexagon::PredRegsRegClass);
2382 unsigned NewOpc = V.is(T: 0) ? Hexagon::PS_false : Hexagon::PS_true;
2383 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: NewOpc), DestReg: NewR);
2384 HBS::replaceReg(OldR: RD.Reg, NewR, MRI);
2385 return true;
2386 }
2387
2388 return false;
2389}
2390
2391// Detect whether RD is a bitfield extract (sign- or zero-extended) of
2392// some register from the AVs set. Create a new corresponding instruction
2393// at the location of MI. The intent is to recognize situations where
2394// a sequence of instructions performs an operation that is equivalent to
2395// an extract operation, such as a shift left followed by a shift right.
2396bool BitSimplification::simplifyExtractLow(MachineInstr *MI,
2397 BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC,
2398 const RegisterSet &AVs) {
2399 if (!GenExtract)
2400 return false;
2401 if (MaxExtract.getNumOccurrences()) {
2402 if (CountExtract >= MaxExtract)
2403 return false;
2404 CountExtract++;
2405 }
2406
2407 unsigned W = RC.width();
2408 unsigned RW = W;
2409 unsigned Len;
2410 bool Signed;
2411
2412 // The code is mostly class-independent, except for the part that generates
2413 // the extract instruction, and establishes the source register (in case it
2414 // needs to use a subregister).
2415 const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RR: RD, MRI);
2416 if (FRC != &Hexagon::IntRegsRegClass && FRC != &Hexagon::DoubleRegsRegClass)
2417 return false;
2418 assert(RD.Sub == 0);
2419
2420 // Observation:
2421 // If the cell has a form of 00..0xx..x with k zeros and n remaining
2422 // bits, this could be an extractu of the n bits, but it could also be
2423 // an extractu of a longer field which happens to have 0s in the top
2424 // bit positions.
2425 // The same logic applies to sign-extended fields.
2426 //
2427 // Do not check for the extended extracts, since it would expand the
2428 // search space quite a bit. The search may be expensive as it is.
2429
2430 const BitTracker::BitValue &TopV = RC[W-1];
2431
2432 // Eliminate candidates that have self-referential bits, since they
2433 // cannot be extracts from other registers. Also, skip registers that
2434 // have compile-time constant values.
2435 bool IsConst = true;
2436 for (unsigned I = 0; I != W; ++I) {
2437 const BitTracker::BitValue &V = RC[I];
2438 if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg == RD.Reg)
2439 return false;
2440 IsConst = IsConst && (V.is(T: 0) || V.is(T: 1));
2441 }
2442 if (IsConst)
2443 return false;
2444
2445 if (TopV.is(T: 0) || TopV.is(T: 1)) {
2446 bool S = TopV.is(T: 1);
2447 for (--W; W > 0 && RC[W-1].is(T: S); --W)
2448 ;
2449 Len = W;
2450 Signed = S;
2451 // The sign bit must be a part of the field being extended.
2452 if (Signed)
2453 ++Len;
2454 } else {
2455 // This could still be a sign-extended extract.
2456 assert(TopV.Type == BitTracker::BitValue::Ref);
2457 if (TopV.RefI.Reg == RD.Reg || TopV.RefI.Pos == W-1)
2458 return false;
2459 for (--W; W > 0 && RC[W-1] == TopV; --W)
2460 ;
2461 // The top bits of RC are copies of TopV. One occurrence of TopV will
2462 // be a part of the field.
2463 Len = W + 1;
2464 Signed = true;
2465 }
2466
2467 // This would be just a copy. It should be handled elsewhere.
2468 if (Len == RW)
2469 return false;
2470
2471 LLVM_DEBUG({
2472 dbgs() << __func__ << " on reg: " << printReg(RD.Reg, &HRI, RD.Sub)
2473 << ", MI: " << *MI;
2474 dbgs() << "Cell: " << RC << '\n';
2475 dbgs() << "Expected bitfield size: " << Len << " bits, "
2476 << (Signed ? "sign" : "zero") << "-extended\n";
2477 });
2478
2479 bool Changed = false;
2480
2481 for (unsigned R = AVs.find_first(); R != 0; R = AVs.find_next(Prev: R)) {
2482 if (!BT.has(Reg: R))
2483 continue;
2484 const BitTracker::RegisterCell &SC = BT.lookup(Reg: R);
2485 unsigned SW = SC.width();
2486
2487 // The source can be longer than the destination, as long as its size is
2488 // a multiple of the size of the destination. Also, we would need to be
2489 // able to refer to the subregister in the source that would be of the
2490 // same size as the destination, but only check the sizes here.
2491 if (SW < RW || (SW % RW) != 0)
2492 continue;
2493
2494 // The field can start at any offset in SC as long as it contains Len
2495 // bits and does not cross subregister boundary (if the source register
2496 // is longer than the destination).
2497 unsigned Off = 0;
2498 while (Off <= SW-Len) {
2499 unsigned OE = (Off+Len)/RW;
2500 if (OE != Off/RW) {
2501 // The assumption here is that if the source (R) is longer than the
2502 // destination, then the destination is a sequence of words of
2503 // size RW, and each such word in R can be accessed via a subregister.
2504 //
2505 // If the beginning and the end of the field cross the subregister
2506 // boundary, advance to the next subregister.
2507 Off = OE*RW;
2508 continue;
2509 }
2510 if (HBS::isEqual(RC1: RC, B1: 0, RC2: SC, B2: Off, W: Len))
2511 break;
2512 ++Off;
2513 }
2514
2515 if (Off > SW-Len)
2516 continue;
2517
2518 // Found match.
2519 unsigned ExtOpc = 0;
2520 if (Off == 0) {
2521 if (Len == 8)
2522 ExtOpc = Signed ? Hexagon::A2_sxtb : Hexagon::A2_zxtb;
2523 else if (Len == 16)
2524 ExtOpc = Signed ? Hexagon::A2_sxth : Hexagon::A2_zxth;
2525 else if (Len < 10 && !Signed)
2526 ExtOpc = Hexagon::A2_andir;
2527 }
2528 if (ExtOpc == 0) {
2529 ExtOpc =
2530 Signed ? (RW == 32 ? Hexagon::S4_extract : Hexagon::S4_extractp)
2531 : (RW == 32 ? Hexagon::S2_extractu : Hexagon::S2_extractup);
2532 }
2533 unsigned SR = 0;
2534 // This only recognizes isub_lo and isub_hi.
2535 if (RW != SW && RW*2 != SW)
2536 continue;
2537 if (RW != SW)
2538 SR = (Off/RW == 0) ? Hexagon::isub_lo : Hexagon::isub_hi;
2539 Off = Off % RW;
2540
2541 if (!validateReg(R: {R,SR}, Opc: ExtOpc, OpNum: 1))
2542 continue;
2543
2544 // Don't generate the same instruction as the one being optimized.
2545 if (MI->getOpcode() == ExtOpc) {
2546 // All possible ExtOpc's have the source in operand(1).
2547 const MachineOperand &SrcOp = MI->getOperand(i: 1);
2548 if (SrcOp.getReg() == R)
2549 continue;
2550 }
2551
2552 DebugLoc DL = MI->getDebugLoc();
2553 MachineBasicBlock &B = *MI->getParent();
2554 Register NewR = MRI.createVirtualRegister(RegClass: FRC);
2555 auto At = MI->isPHI() ? B.getFirstNonPHI()
2556 : MachineBasicBlock::iterator(MI);
2557 auto MIB = BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: ExtOpc), DestReg: NewR).addReg(RegNo: R, Flags: {}, SubReg: SR);
2558 switch (ExtOpc) {
2559 case Hexagon::A2_sxtb:
2560 case Hexagon::A2_zxtb:
2561 case Hexagon::A2_sxth:
2562 case Hexagon::A2_zxth:
2563 break;
2564 case Hexagon::A2_andir:
2565 MIB.addImm(Val: (1u << Len) - 1);
2566 break;
2567 case Hexagon::S4_extract:
2568 case Hexagon::S2_extractu:
2569 case Hexagon::S4_extractp:
2570 case Hexagon::S2_extractup:
2571 MIB.addImm(Val: Len)
2572 .addImm(Val: Off);
2573 break;
2574 default:
2575 llvm_unreachable("Unexpected opcode");
2576 }
2577
2578 HBS::replaceReg(OldR: RD.Reg, NewR, MRI);
2579 BT.put(RR: BitTracker::RegisterRef(NewR), RC);
2580 Changed = true;
2581 break;
2582 }
2583
2584 return Changed;
2585}
2586
2587bool BitSimplification::simplifyRCmp0(MachineInstr *MI,
2588 BitTracker::RegisterRef RD) {
2589 unsigned Opc = MI->getOpcode();
2590 if (Opc != Hexagon::A4_rcmpeqi && Opc != Hexagon::A4_rcmpneqi)
2591 return false;
2592 MachineOperand &CmpOp = MI->getOperand(i: 2);
2593 if (!CmpOp.isImm() || CmpOp.getImm() != 0)
2594 return false;
2595
2596 const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RR: RD, MRI);
2597 if (FRC != &Hexagon::IntRegsRegClass && FRC != &Hexagon::DoubleRegsRegClass)
2598 return false;
2599 assert(RD.Sub == 0);
2600
2601 MachineBasicBlock &B = *MI->getParent();
2602 const DebugLoc &DL = MI->getDebugLoc();
2603 auto At = MI->isPHI() ? B.getFirstNonPHI()
2604 : MachineBasicBlock::iterator(MI);
2605 bool KnownZ = true;
2606 bool KnownNZ = false;
2607
2608 BitTracker::RegisterRef SR = MI->getOperand(i: 1);
2609 if (!BT.has(Reg: SR.Reg))
2610 return false;
2611 const BitTracker::RegisterCell &SC = BT.lookup(Reg: SR.Reg);
2612 unsigned F, W;
2613 if (!HBS::getSubregMask(RR: SR, Begin&: F, Width&: W, MRI))
2614 return false;
2615
2616 for (uint16_t I = F; I != F+W; ++I) {
2617 const BitTracker::BitValue &V = SC[I];
2618 if (!V.is(T: 0))
2619 KnownZ = false;
2620 if (V.is(T: 1))
2621 KnownNZ = true;
2622 }
2623
2624 auto ReplaceWithConst = [&](int C) {
2625 Register NewR = MRI.createVirtualRegister(RegClass: FRC);
2626 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: Hexagon::A2_tfrsi), DestReg: NewR)
2627 .addImm(Val: C);
2628 HBS::replaceReg(OldR: RD.Reg, NewR, MRI);
2629 BitTracker::RegisterCell NewRC(W);
2630 for (uint16_t I = 0; I != W; ++I) {
2631 NewRC[I] = BitTracker::BitValue(C & 1);
2632 C = unsigned(C) >> 1;
2633 }
2634 BT.put(RR: BitTracker::RegisterRef(NewR), RC: NewRC);
2635 return true;
2636 };
2637
2638 auto IsNonZero = [] (const MachineOperand &Op) {
2639 if (Op.isGlobal() || Op.isBlockAddress())
2640 return true;
2641 if (Op.isImm())
2642 return Op.getImm() != 0;
2643 if (Op.isCImm())
2644 return !Op.getCImm()->isZero();
2645 if (Op.isFPImm())
2646 return !Op.getFPImm()->isZero();
2647 return false;
2648 };
2649
2650 auto IsZero = [] (const MachineOperand &Op) {
2651 if (Op.isGlobal() || Op.isBlockAddress())
2652 return false;
2653 if (Op.isImm())
2654 return Op.getImm() == 0;
2655 if (Op.isCImm())
2656 return Op.getCImm()->isZero();
2657 if (Op.isFPImm())
2658 return Op.getFPImm()->isZero();
2659 return false;
2660 };
2661
2662 // If the source register is known to be 0 or non-0, the comparison can
2663 // be folded to a load of a constant.
2664 if (KnownZ || KnownNZ) {
2665 assert(KnownZ != KnownNZ && "Register cannot be both 0 and non-0");
2666 return ReplaceWithConst(KnownZ == (Opc == Hexagon::A4_rcmpeqi));
2667 }
2668
2669 // Special case: if the compare comes from a C2_muxii, then we know the
2670 // two possible constants that can be the source value.
2671 MachineInstr *InpDef = MRI.getVRegDef(Reg: SR.Reg);
2672 if (!InpDef)
2673 return false;
2674 if (SR.Sub == 0 && InpDef->getOpcode() == Hexagon::C2_muxii) {
2675 MachineOperand &Src1 = InpDef->getOperand(i: 2);
2676 MachineOperand &Src2 = InpDef->getOperand(i: 3);
2677 // Check if both are non-zero.
2678 bool KnownNZ1 = IsNonZero(Src1), KnownNZ2 = IsNonZero(Src2);
2679 if (KnownNZ1 && KnownNZ2)
2680 return ReplaceWithConst(Opc == Hexagon::A4_rcmpneqi);
2681 // Check if both are zero.
2682 bool KnownZ1 = IsZero(Src1), KnownZ2 = IsZero(Src2);
2683 if (KnownZ1 && KnownZ2)
2684 return ReplaceWithConst(Opc == Hexagon::A4_rcmpeqi);
2685
2686 // If for both operands we know that they are either 0 or non-0,
2687 // replace the comparison with a C2_muxii, using the same predicate
2688 // register, but with operands substituted with 0/1 accordingly.
2689 if ((KnownZ1 || KnownNZ1) && (KnownZ2 || KnownNZ2)) {
2690 Register NewR = MRI.createVirtualRegister(RegClass: FRC);
2691 BuildMI(BB&: B, I: At, MIMD: DL, MCID: HII.get(Opcode: Hexagon::C2_muxii), DestReg: NewR)
2692 .addReg(RegNo: InpDef->getOperand(i: 1).getReg())
2693 .addImm(Val: KnownZ1 == (Opc == Hexagon::A4_rcmpeqi))
2694 .addImm(Val: KnownZ2 == (Opc == Hexagon::A4_rcmpeqi));
2695 HBS::replaceReg(OldR: RD.Reg, NewR, MRI);
2696 // Create a new cell with only the least significant bit unknown.
2697 BitTracker::RegisterCell NewRC(W);
2698 NewRC[0] = BitTracker::BitValue::self();
2699 NewRC.fill(B: 1, E: W, V: BitTracker::BitValue::Zero);
2700 BT.put(RR: BitTracker::RegisterRef(NewR), RC: NewRC);
2701 return true;
2702 }
2703 }
2704
2705 return false;
2706}
2707
2708bool BitSimplification::processBlock(MachineBasicBlock &B,
2709 const RegisterSet &AVs) {
2710 if (!BT.reached(B: &B))
2711 return false;
2712 bool Changed = false;
2713 RegisterSet AVB = AVs;
2714 RegisterSet Defs;
2715
2716 for (auto I = B.begin(), E = B.end(); I != E; ++I, AVB.insert(Rs: Defs)) {
2717 MachineInstr *MI = &*I;
2718 Defs.clear();
2719 HBS::getInstrDefs(MI: *MI, Defs);
2720
2721 unsigned Opc = MI->getOpcode();
2722 if (Opc == TargetOpcode::COPY || Opc == TargetOpcode::REG_SEQUENCE)
2723 continue;
2724
2725 if (MI->mayStore()) {
2726 bool T = genStoreUpperHalf(MI);
2727 T = T || genStoreImmediate(MI);
2728 Changed |= T;
2729 continue;
2730 }
2731
2732 if (Defs.count() != 1)
2733 continue;
2734 const MachineOperand &Op0 = MI->getOperand(i: 0);
2735 if (!Op0.isReg() || !Op0.isDef())
2736 continue;
2737 BitTracker::RegisterRef RD = Op0;
2738 if (!BT.has(Reg: RD.Reg))
2739 continue;
2740 const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RR: RD, MRI);
2741 const BitTracker::RegisterCell &RC = BT.lookup(Reg: RD.Reg);
2742
2743 if (FRC->getID() == Hexagon::DoubleRegsRegClassID) {
2744 bool T = genPackhl(MI, RD, RC);
2745 T = T || simplifyExtractLow(MI, RD, RC, AVs: AVB);
2746 Changed |= T;
2747 continue;
2748 }
2749
2750 if (FRC->getID() == Hexagon::IntRegsRegClassID) {
2751 bool T = genBitSplit(MI, RD, RC, AVs: AVB);
2752 T = T || simplifyExtractLow(MI, RD, RC, AVs: AVB);
2753 T = T || genExtractHalf(MI, RD, RC);
2754 T = T || genCombineHalf(MI, RD, RC);
2755 T = T || genExtractLow(MI, RD, RC);
2756 T = T || simplifyRCmp0(MI, RD);
2757 Changed |= T;
2758 continue;
2759 }
2760
2761 if (FRC->getID() == Hexagon::PredRegsRegClassID) {
2762 bool T = simplifyTstbit(MI, RD, RC);
2763 Changed |= T;
2764 continue;
2765 }
2766 }
2767 return Changed;
2768}
2769
2770bool HexagonBitSimplify::runOnMachineFunction(MachineFunction &MF) {
2771 if (skipFunction(F: MF.getFunction()))
2772 return false;
2773
2774 auto &HST = MF.getSubtarget<HexagonSubtarget>();
2775 auto &HRI = *HST.getRegisterInfo();
2776 auto &HII = *HST.getInstrInfo();
2777
2778 MDT = &getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree();
2779 MachineRegisterInfo &MRI = MF.getRegInfo();
2780 bool Changed;
2781
2782 Changed = DeadCodeElimination(MF, *MDT).run();
2783
2784 const HexagonEvaluator HE(HRI, MRI, HII, MF);
2785 BitTracker BT(HE, MF);
2786 LLVM_DEBUG(BT.trace(true));
2787 BT.run();
2788
2789 MachineBasicBlock &Entry = MF.front();
2790
2791 RegisterSet AIG; // Available registers for IG.
2792 ConstGeneration ImmG(BT, HII, MRI);
2793 Changed |= visitBlock(B&: Entry, T&: ImmG, AVs&: AIG);
2794
2795 RegisterSet ARE; // Available registers for RIE.
2796 RedundantInstrElimination RIE(BT, HII, HRI, MRI);
2797 bool Ried = visitBlock(B&: Entry, T&: RIE, AVs&: ARE);
2798 if (Ried) {
2799 Changed = true;
2800 BT.run();
2801 }
2802
2803 RegisterSet ACG; // Available registers for CG.
2804 CopyGeneration CopyG(BT, HII, HRI, MRI);
2805 Changed |= visitBlock(B&: Entry, T&: CopyG, AVs&: ACG);
2806
2807 RegisterSet ACP; // Available registers for CP.
2808 CopyPropagation CopyP(HRI, MRI);
2809 Changed |= visitBlock(B&: Entry, T&: CopyP, AVs&: ACP);
2810
2811 Changed = DeadCodeElimination(MF, *MDT).run() || Changed;
2812
2813 BT.run();
2814 RegisterSet ABS; // Available registers for BS.
2815 BitSimplification BitS(BT, *MDT, HII, HRI, MRI, MF);
2816 Changed |= visitBlock(B&: Entry, T&: BitS, AVs&: ABS);
2817
2818 Changed = DeadCodeElimination(MF, *MDT).run() || Changed;
2819
2820 if (Changed) {
2821 for (auto &B : MF)
2822 for (auto &I : B)
2823 I.clearKillInfo();
2824 DeadCodeElimination(MF, *MDT).run();
2825 }
2826 return Changed;
2827}
2828
2829// Recognize loops where the code at the end of the loop matches the code
2830// before the entry of the loop, and the matching code is such that is can
2831// be simplified. This pass relies on the bit simplification above and only
2832// prepares code in a way that can be handled by the bit simplification.
2833//
2834// This is the motivating testcase (and explanation):
2835//
2836// {
2837// loop0(.LBB0_2, r1) // %for.body.preheader
2838// r5:4 = memd(r0++#8)
2839// }
2840// {
2841// r3 = lsr(r4, #16)
2842// r7:6 = combine(r5, r5)
2843// }
2844// {
2845// r3 = insert(r5, #16, #16)
2846// r7:6 = vlsrw(r7:6, #16)
2847// }
2848// .LBB0_2:
2849// {
2850// memh(r2+#4) = r5
2851// memh(r2+#6) = r6 # R6 is really R5.H
2852// }
2853// {
2854// r2 = add(r2, #8)
2855// memh(r2+#0) = r4
2856// memh(r2+#2) = r3 # R3 is really R4.H
2857// }
2858// {
2859// r5:4 = memd(r0++#8)
2860// }
2861// { # "Shuffling" code that sets up R3 and R6
2862// r3 = lsr(r4, #16) # so that their halves can be stored in the
2863// r7:6 = combine(r5, r5) # next iteration. This could be folded into
2864// } # the stores if the code was at the beginning
2865// { # of the loop iteration. Since the same code
2866// r3 = insert(r5, #16, #16) # precedes the loop, it can actually be moved
2867// r7:6 = vlsrw(r7:6, #16) # there.
2868// }:endloop0
2869//
2870//
2871// The outcome:
2872//
2873// {
2874// loop0(.LBB0_2, r1)
2875// r5:4 = memd(r0++#8)
2876// }
2877// .LBB0_2:
2878// {
2879// memh(r2+#4) = r5
2880// memh(r2+#6) = r5.h
2881// }
2882// {
2883// r2 = add(r2, #8)
2884// memh(r2+#0) = r4
2885// memh(r2+#2) = r4.h
2886// }
2887// {
2888// r5:4 = memd(r0++#8)
2889// }:endloop0
2890
2891namespace {
2892
2893 class HexagonLoopRescheduling : public MachineFunctionPass {
2894 public:
2895 static char ID;
2896
2897 HexagonLoopRescheduling() : MachineFunctionPass(ID) {}
2898
2899 bool runOnMachineFunction(MachineFunction &MF) override;
2900
2901 private:
2902 const HexagonInstrInfo *HII = nullptr;
2903 const HexagonRegisterInfo *HRI = nullptr;
2904 MachineRegisterInfo *MRI = nullptr;
2905 BitTracker *BTP = nullptr;
2906
2907 struct LoopCand {
2908 LoopCand(MachineBasicBlock *lb, MachineBasicBlock *pb,
2909 MachineBasicBlock *eb) : LB(lb), PB(pb), EB(eb) {}
2910
2911 MachineBasicBlock *LB, *PB, *EB;
2912 };
2913 using InstrList = std::vector<MachineInstr *>;
2914 struct InstrGroup {
2915 BitTracker::RegisterRef Inp, Out;
2916 InstrList Ins;
2917 };
2918 struct PhiInfo {
2919 PhiInfo(MachineInstr &P, MachineBasicBlock &B);
2920
2921 unsigned DefR;
2922 BitTracker::RegisterRef LR, PR; // Loop Register, Preheader Register
2923 MachineBasicBlock *LB, *PB; // Loop Block, Preheader Block
2924 };
2925
2926 static unsigned getDefReg(const MachineInstr *MI);
2927 bool isConst(unsigned Reg) const;
2928 bool isBitShuffle(const MachineInstr *MI, unsigned DefR) const;
2929 bool isStoreInput(const MachineInstr *MI, unsigned DefR) const;
2930 bool isShuffleOf(unsigned OutR, unsigned InpR) const;
2931 bool isSameShuffle(unsigned OutR1, unsigned InpR1, unsigned OutR2,
2932 unsigned &InpR2) const;
2933 void moveGroup(InstrGroup &G, MachineBasicBlock &LB, MachineBasicBlock &PB,
2934 MachineBasicBlock::iterator At, unsigned OldPhiR, unsigned NewPredR);
2935 bool processLoop(LoopCand &C);
2936 };
2937
2938} // end anonymous namespace
2939
2940char HexagonLoopRescheduling::ID = 0;
2941
2942INITIALIZE_PASS(HexagonLoopRescheduling, "hexagon-loop-resched-pass",
2943 "Hexagon Loop Rescheduling", false, false)
2944
2945HexagonLoopRescheduling::PhiInfo::PhiInfo(MachineInstr &P,
2946 MachineBasicBlock &B) {
2947 DefR = HexagonLoopRescheduling::getDefReg(MI: &P);
2948 LB = &B;
2949 PB = nullptr;
2950 for (unsigned i = 1, n = P.getNumOperands(); i < n; i += 2) {
2951 const MachineOperand &OpB = P.getOperand(i: i+1);
2952 if (OpB.getMBB() == &B) {
2953 LR = P.getOperand(i);
2954 continue;
2955 }
2956 PB = OpB.getMBB();
2957 PR = P.getOperand(i);
2958 }
2959}
2960
2961unsigned HexagonLoopRescheduling::getDefReg(const MachineInstr *MI) {
2962 RegisterSet Defs;
2963 HBS::getInstrDefs(MI: *MI, Defs);
2964 if (Defs.count() != 1)
2965 return 0;
2966 return Defs.find_first();
2967}
2968
2969bool HexagonLoopRescheduling::isConst(unsigned Reg) const {
2970 if (!BTP->has(Reg))
2971 return false;
2972 const BitTracker::RegisterCell &RC = BTP->lookup(Reg);
2973 for (unsigned i = 0, w = RC.width(); i < w; ++i) {
2974 const BitTracker::BitValue &V = RC[i];
2975 if (!V.is(T: 0) && !V.is(T: 1))
2976 return false;
2977 }
2978 return true;
2979}
2980
2981bool HexagonLoopRescheduling::isBitShuffle(const MachineInstr *MI,
2982 unsigned DefR) const {
2983 unsigned Opc = MI->getOpcode();
2984 switch (Opc) {
2985 case TargetOpcode::COPY:
2986 case Hexagon::S2_lsr_i_r:
2987 case Hexagon::S2_asr_i_r:
2988 case Hexagon::S2_asl_i_r:
2989 case Hexagon::S2_lsr_i_p:
2990 case Hexagon::S2_asr_i_p:
2991 case Hexagon::S2_asl_i_p:
2992 case Hexagon::S2_insert:
2993 case Hexagon::A2_or:
2994 case Hexagon::A2_orp:
2995 case Hexagon::A2_and:
2996 case Hexagon::A2_andp:
2997 case Hexagon::A2_combinew:
2998 case Hexagon::A4_combineri:
2999 case Hexagon::A4_combineir:
3000 case Hexagon::A2_combineii:
3001 case Hexagon::A4_combineii:
3002 case Hexagon::A2_combine_ll:
3003 case Hexagon::A2_combine_lh:
3004 case Hexagon::A2_combine_hl:
3005 case Hexagon::A2_combine_hh:
3006 return true;
3007 }
3008 return false;
3009}
3010
3011bool HexagonLoopRescheduling::isStoreInput(const MachineInstr *MI,
3012 unsigned InpR) const {
3013 for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
3014 const MachineOperand &Op = MI->getOperand(i);
3015 if (!Op.isReg())
3016 continue;
3017 if (Op.getReg() == InpR)
3018 return i == n-1;
3019 }
3020 return false;
3021}
3022
3023bool HexagonLoopRescheduling::isShuffleOf(unsigned OutR, unsigned InpR) const {
3024 if (!BTP->has(Reg: OutR) || !BTP->has(Reg: InpR))
3025 return false;
3026 const BitTracker::RegisterCell &OutC = BTP->lookup(Reg: OutR);
3027 for (unsigned i = 0, w = OutC.width(); i < w; ++i) {
3028 const BitTracker::BitValue &V = OutC[i];
3029 if (V.Type != BitTracker::BitValue::Ref)
3030 continue;
3031 if (V.RefI.Reg != InpR)
3032 return false;
3033 }
3034 return true;
3035}
3036
3037bool HexagonLoopRescheduling::isSameShuffle(unsigned OutR1, unsigned InpR1,
3038 unsigned OutR2, unsigned &InpR2) const {
3039 if (!BTP->has(Reg: OutR1) || !BTP->has(Reg: InpR1) || !BTP->has(Reg: OutR2))
3040 return false;
3041 const BitTracker::RegisterCell &OutC1 = BTP->lookup(Reg: OutR1);
3042 const BitTracker::RegisterCell &OutC2 = BTP->lookup(Reg: OutR2);
3043 unsigned W = OutC1.width();
3044 unsigned MatchR = 0;
3045 if (W != OutC2.width())
3046 return false;
3047 for (unsigned i = 0; i < W; ++i) {
3048 const BitTracker::BitValue &V1 = OutC1[i], &V2 = OutC2[i];
3049 if (V1.Type != V2.Type || V1.Type == BitTracker::BitValue::One)
3050 return false;
3051 if (V1.Type != BitTracker::BitValue::Ref)
3052 continue;
3053 if (V1.RefI.Pos != V2.RefI.Pos)
3054 return false;
3055 if (V1.RefI.Reg != InpR1)
3056 return false;
3057 if (V2.RefI.Reg == 0 || V2.RefI.Reg == OutR2)
3058 return false;
3059 if (!MatchR)
3060 MatchR = V2.RefI.Reg;
3061 else if (V2.RefI.Reg != MatchR)
3062 return false;
3063 }
3064 InpR2 = MatchR;
3065 return true;
3066}
3067
3068void HexagonLoopRescheduling::moveGroup(InstrGroup &G, MachineBasicBlock &LB,
3069 MachineBasicBlock &PB, MachineBasicBlock::iterator At, unsigned OldPhiR,
3070 unsigned NewPredR) {
3071 DenseMap<unsigned,unsigned> RegMap;
3072
3073 const TargetRegisterClass *PhiRC = MRI->getRegClass(Reg: NewPredR);
3074 Register PhiR = MRI->createVirtualRegister(RegClass: PhiRC);
3075 BuildMI(BB&: LB, I: At, MIMD: At->getDebugLoc(), MCID: HII->get(Opcode: TargetOpcode::PHI), DestReg: PhiR)
3076 .addReg(RegNo: NewPredR)
3077 .addMBB(MBB: &PB)
3078 .addReg(RegNo: G.Inp.Reg)
3079 .addMBB(MBB: &LB);
3080 RegMap.insert(KV: std::make_pair(x&: G.Inp.Reg, y&: PhiR));
3081
3082 for (const MachineInstr *SI : llvm::reverse(C&: G.Ins)) {
3083 unsigned DR = getDefReg(MI: SI);
3084 const TargetRegisterClass *RC = MRI->getRegClass(Reg: DR);
3085 Register NewDR = MRI->createVirtualRegister(RegClass: RC);
3086 DebugLoc DL = SI->getDebugLoc();
3087
3088 auto MIB = BuildMI(BB&: LB, I: At, MIMD: DL, MCID: HII->get(Opcode: SI->getOpcode()), DestReg: NewDR);
3089 for (const MachineOperand &Op : SI->operands()) {
3090 if (!Op.isReg()) {
3091 MIB.add(MO: Op);
3092 continue;
3093 }
3094 if (!Op.isUse())
3095 continue;
3096 unsigned UseR = RegMap[Op.getReg()];
3097 MIB.addReg(RegNo: UseR, Flags: {}, SubReg: Op.getSubReg());
3098 }
3099 RegMap.insert(KV: std::make_pair(x&: DR, y&: NewDR));
3100 }
3101
3102 HBS::replaceReg(OldR: OldPhiR, NewR: RegMap[G.Out.Reg], MRI&: *MRI);
3103}
3104
3105bool HexagonLoopRescheduling::processLoop(LoopCand &C) {
3106 LLVM_DEBUG(dbgs() << "Processing loop in " << printMBBReference(*C.LB)
3107 << "\n");
3108 std::vector<PhiInfo> Phis;
3109 for (auto &I : *C.LB) {
3110 if (!I.isPHI())
3111 break;
3112 unsigned PR = getDefReg(MI: &I);
3113 if (isConst(Reg: PR))
3114 continue;
3115 bool BadUse = false, GoodUse = false;
3116 for (const MachineInstr &UseI : MRI->use_instructions(Reg: PR)) {
3117 if (UseI.getParent() != C.LB) {
3118 BadUse = true;
3119 break;
3120 }
3121 if (isBitShuffle(MI: &UseI, DefR: PR) || isStoreInput(MI: &UseI, InpR: PR))
3122 GoodUse = true;
3123 }
3124 if (BadUse || !GoodUse)
3125 continue;
3126
3127 Phis.push_back(x: PhiInfo(I, *C.LB));
3128 }
3129
3130 LLVM_DEBUG({
3131 dbgs() << "Phis: {";
3132 for (auto &I : Phis) {
3133 dbgs() << ' ' << printReg(I.DefR, HRI) << "=phi("
3134 << printReg(I.PR.Reg, HRI, I.PR.Sub) << ":b" << I.PB->getNumber()
3135 << ',' << printReg(I.LR.Reg, HRI, I.LR.Sub) << ":b"
3136 << I.LB->getNumber() << ')';
3137 }
3138 dbgs() << " }\n";
3139 });
3140
3141 if (Phis.empty())
3142 return false;
3143
3144 bool Changed = false;
3145 InstrList ShufIns;
3146
3147 // Go backwards in the block: for each bit shuffling instruction, check
3148 // if that instruction could potentially be moved to the front of the loop:
3149 // the output of the loop cannot be used in a non-shuffling instruction
3150 // in this loop.
3151 for (MachineInstr &MI : llvm::reverse(C&: *C.LB)) {
3152 if (MI.isTerminator())
3153 continue;
3154 if (MI.isPHI())
3155 break;
3156
3157 RegisterSet Defs;
3158 HBS::getInstrDefs(MI, Defs);
3159 if (Defs.count() != 1)
3160 continue;
3161 Register DefR = Defs.find_first();
3162 if (!DefR.isVirtual())
3163 continue;
3164 if (!isBitShuffle(MI: &MI, DefR))
3165 continue;
3166
3167 bool BadUse = false;
3168 for (auto UI = MRI->use_begin(RegNo: DefR), UE = MRI->use_end(); UI != UE; ++UI) {
3169 MachineInstr *UseI = UI->getParent();
3170 if (UseI->getParent() == C.LB) {
3171 if (UseI->isPHI()) {
3172 // If the use is in a phi node in this loop, then it should be
3173 // the value corresponding to the back edge.
3174 unsigned Idx = UI.getOperandNo();
3175 if (UseI->getOperand(i: Idx+1).getMBB() != C.LB)
3176 BadUse = true;
3177 } else {
3178 if (!llvm::is_contained(Range&: ShufIns, Element: UseI))
3179 BadUse = true;
3180 }
3181 } else {
3182 // There is a use outside of the loop, but there is no epilog block
3183 // suitable for a copy-out.
3184 if (C.EB == nullptr)
3185 BadUse = true;
3186 }
3187 if (BadUse)
3188 break;
3189 }
3190
3191 if (BadUse)
3192 continue;
3193 ShufIns.push_back(x: &MI);
3194 }
3195
3196 // Partition the list of shuffling instructions into instruction groups,
3197 // where each group has to be moved as a whole (i.e. a group is a chain of
3198 // dependent instructions). A group produces a single live output register,
3199 // which is meant to be the input of the loop phi node (although this is
3200 // not checked here yet). It also uses a single register as its input,
3201 // which is some value produced in the loop body. After moving the group
3202 // to the beginning of the loop, that input register would need to be
3203 // the loop-carried register (through a phi node) instead of the (currently
3204 // loop-carried) output register.
3205 using InstrGroupList = std::vector<InstrGroup>;
3206 InstrGroupList Groups;
3207
3208 for (unsigned i = 0, n = ShufIns.size(); i < n; ++i) {
3209 MachineInstr *SI = ShufIns[i];
3210 if (SI == nullptr)
3211 continue;
3212
3213 InstrGroup G;
3214 G.Ins.push_back(x: SI);
3215 G.Out.Reg = getDefReg(MI: SI);
3216 RegisterSet Inputs;
3217 HBS::getInstrUses(MI: *SI, Uses&: Inputs);
3218
3219 for (unsigned j = i+1; j < n; ++j) {
3220 MachineInstr *MI = ShufIns[j];
3221 if (MI == nullptr)
3222 continue;
3223 RegisterSet Defs;
3224 HBS::getInstrDefs(MI: *MI, Defs);
3225 // If this instruction does not define any pending inputs, skip it.
3226 if (!Defs.intersects(Rs: Inputs))
3227 continue;
3228 // Otherwise, add it to the current group and remove the inputs that
3229 // are defined by MI.
3230 G.Ins.push_back(x: MI);
3231 Inputs.remove(Rs: Defs);
3232 // Then add all registers used by MI.
3233 HBS::getInstrUses(MI: *MI, Uses&: Inputs);
3234 ShufIns[j] = nullptr;
3235 }
3236
3237 // Only add a group if it requires at most one register.
3238 if (Inputs.count() > 1)
3239 continue;
3240 auto LoopInpEq = [G] (const PhiInfo &P) -> bool {
3241 return G.Out.Reg == P.LR.Reg;
3242 };
3243 if (llvm::none_of(Range&: Phis, P: LoopInpEq))
3244 continue;
3245
3246 G.Inp.Reg = Inputs.find_first();
3247 Groups.push_back(x: G);
3248 }
3249
3250 LLVM_DEBUG({
3251 for (unsigned i = 0, n = Groups.size(); i < n; ++i) {
3252 InstrGroup &G = Groups[i];
3253 dbgs() << "Group[" << i << "] inp: "
3254 << printReg(G.Inp.Reg, HRI, G.Inp.Sub)
3255 << " out: " << printReg(G.Out.Reg, HRI, G.Out.Sub) << "\n";
3256 for (const MachineInstr *MI : G.Ins)
3257 dbgs() << " " << MI;
3258 }
3259 });
3260
3261 for (InstrGroup &G : Groups) {
3262 if (!isShuffleOf(OutR: G.Out.Reg, InpR: G.Inp.Reg))
3263 continue;
3264 auto LoopInpEq = [G] (const PhiInfo &P) -> bool {
3265 return G.Out.Reg == P.LR.Reg;
3266 };
3267 auto F = llvm::find_if(Range&: Phis, P: LoopInpEq);
3268 if (F == Phis.end())
3269 continue;
3270 unsigned PrehR = 0;
3271 if (!isSameShuffle(OutR1: G.Out.Reg, InpR1: G.Inp.Reg, OutR2: F->PR.Reg, InpR2&: PrehR)) {
3272 const MachineInstr *DefPrehR = MRI->getVRegDef(Reg: F->PR.Reg);
3273 unsigned Opc = DefPrehR->getOpcode();
3274 if (Opc != Hexagon::A2_tfrsi && Opc != Hexagon::A2_tfrpi)
3275 continue;
3276 if (!DefPrehR->getOperand(i: 1).isImm())
3277 continue;
3278 if (DefPrehR->getOperand(i: 1).getImm() != 0)
3279 continue;
3280 const TargetRegisterClass *RC = MRI->getRegClass(Reg: G.Inp.Reg);
3281 if (RC != MRI->getRegClass(Reg: F->PR.Reg)) {
3282 PrehR = MRI->createVirtualRegister(RegClass: RC);
3283 unsigned TfrI = (RC == &Hexagon::IntRegsRegClass) ? Hexagon::A2_tfrsi
3284 : Hexagon::A2_tfrpi;
3285 auto T = C.PB->getFirstTerminator();
3286 DebugLoc DL = (T != C.PB->end()) ? T->getDebugLoc() : DebugLoc();
3287 BuildMI(BB&: *C.PB, I: T, MIMD: DL, MCID: HII->get(Opcode: TfrI), DestReg: PrehR)
3288 .addImm(Val: 0);
3289 } else {
3290 PrehR = F->PR.Reg;
3291 }
3292 }
3293 // isSameShuffle could match with PrehR being of a wider class than
3294 // G.Inp.Reg, for example if G shuffles the low 32 bits of its input,
3295 // it would match for the input being a 32-bit register, and PrehR
3296 // being a 64-bit register (where the low 32 bits match). This could
3297 // be handled, but for now skip these cases.
3298 if (MRI->getRegClass(Reg: PrehR) != MRI->getRegClass(Reg: G.Inp.Reg))
3299 continue;
3300 moveGroup(G, LB&: *F->LB, PB&: *F->PB, At: F->LB->getFirstNonPHI(), OldPhiR: F->DefR, NewPredR: PrehR);
3301 Changed = true;
3302 }
3303
3304 return Changed;
3305}
3306
3307bool HexagonLoopRescheduling::runOnMachineFunction(MachineFunction &MF) {
3308 if (skipFunction(F: MF.getFunction()))
3309 return false;
3310
3311 auto &HST = MF.getSubtarget<HexagonSubtarget>();
3312 HII = HST.getInstrInfo();
3313 HRI = HST.getRegisterInfo();
3314 MRI = &MF.getRegInfo();
3315 const HexagonEvaluator HE(*HRI, *MRI, *HII, MF);
3316 BitTracker BT(HE, MF);
3317 LLVM_DEBUG(BT.trace(true));
3318 BT.run();
3319 BTP = &BT;
3320
3321 std::vector<LoopCand> Cand;
3322
3323 for (auto &B : MF) {
3324 if (B.pred_size() != 2 || B.succ_size() != 2)
3325 continue;
3326 MachineBasicBlock *PB = nullptr;
3327 bool IsLoop = false;
3328 for (MachineBasicBlock *Pred : B.predecessors()) {
3329 if (Pred != &B)
3330 PB = Pred;
3331 else
3332 IsLoop = true;
3333 }
3334 if (!IsLoop)
3335 continue;
3336
3337 MachineBasicBlock *EB = nullptr;
3338 for (MachineBasicBlock *Succ : B.successors()) {
3339 if (Succ == &B)
3340 continue;
3341 // Set EP to the epilog block, if it has only 1 predecessor (i.e. the
3342 // edge from B to EP is non-critical.
3343 if (Succ->pred_size() == 1)
3344 EB = Succ;
3345 break;
3346 }
3347
3348 Cand.push_back(x: LoopCand(&B, PB, EB));
3349 }
3350
3351 bool Changed = false;
3352 for (auto &C : Cand)
3353 Changed |= processLoop(C);
3354
3355 return Changed;
3356}
3357
3358//===----------------------------------------------------------------------===//
3359// Public Constructor Functions
3360//===----------------------------------------------------------------------===//
3361
3362FunctionPass *llvm::createHexagonLoopRescheduling() {
3363 return new HexagonLoopRescheduling();
3364}
3365
3366FunctionPass *llvm::createHexagonBitSimplify() {
3367 return new HexagonBitSimplify();
3368}
3369