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