xref: /aosp_15_r20/external/llvm/lib/Target/Hexagon/HexagonBitSimplify.cpp (revision 9880d6810fe72a1726cb53787c6711e909410d58)
1*9880d681SAndroid Build Coastguard Worker //===--- HexagonBitSimplify.cpp -------------------------------------------===//
2*9880d681SAndroid Build Coastguard Worker //
3*9880d681SAndroid Build Coastguard Worker //                     The LLVM Compiler Infrastructure
4*9880d681SAndroid Build Coastguard Worker //
5*9880d681SAndroid Build Coastguard Worker // This file is distributed under the University of Illinois Open Source
6*9880d681SAndroid Build Coastguard Worker // License. See LICENSE.TXT for details.
7*9880d681SAndroid Build Coastguard Worker //
8*9880d681SAndroid Build Coastguard Worker //===----------------------------------------------------------------------===//
9*9880d681SAndroid Build Coastguard Worker 
10*9880d681SAndroid Build Coastguard Worker #define DEBUG_TYPE "hexbit"
11*9880d681SAndroid Build Coastguard Worker 
12*9880d681SAndroid Build Coastguard Worker #include "HexagonBitTracker.h"
13*9880d681SAndroid Build Coastguard Worker #include "HexagonTargetMachine.h"
14*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/MachineDominators.h"
15*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/MachineFunctionPass.h"
16*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/MachineInstrBuilder.h"
17*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/MachineRegisterInfo.h"
18*9880d681SAndroid Build Coastguard Worker #include "llvm/CodeGen/Passes.h"
19*9880d681SAndroid Build Coastguard Worker #include "llvm/Support/Debug.h"
20*9880d681SAndroid Build Coastguard Worker #include "llvm/Support/raw_ostream.h"
21*9880d681SAndroid Build Coastguard Worker #include "llvm/Target/TargetInstrInfo.h"
22*9880d681SAndroid Build Coastguard Worker #include "llvm/Target/TargetMachine.h"
23*9880d681SAndroid Build Coastguard Worker 
24*9880d681SAndroid Build Coastguard Worker using namespace llvm;
25*9880d681SAndroid Build Coastguard Worker 
26*9880d681SAndroid Build Coastguard Worker namespace llvm {
27*9880d681SAndroid Build Coastguard Worker   void initializeHexagonBitSimplifyPass(PassRegistry& Registry);
28*9880d681SAndroid Build Coastguard Worker   FunctionPass *createHexagonBitSimplify();
29*9880d681SAndroid Build Coastguard Worker }
30*9880d681SAndroid Build Coastguard Worker 
31*9880d681SAndroid Build Coastguard Worker namespace {
32*9880d681SAndroid Build Coastguard Worker   // Set of virtual registers, based on BitVector.
33*9880d681SAndroid Build Coastguard Worker   struct RegisterSet : private BitVector {
RegisterSet__anonb78d304d0111::RegisterSet34*9880d681SAndroid Build Coastguard Worker     RegisterSet() : BitVector() {}
RegisterSet__anonb78d304d0111::RegisterSet35*9880d681SAndroid Build Coastguard Worker     explicit RegisterSet(unsigned s, bool t = false) : BitVector(s, t) {}
RegisterSet__anonb78d304d0111::RegisterSet36*9880d681SAndroid Build Coastguard Worker     RegisterSet(const RegisterSet &RS) : BitVector(RS) {}
37*9880d681SAndroid Build Coastguard Worker 
38*9880d681SAndroid Build Coastguard Worker     using BitVector::clear;
39*9880d681SAndroid Build Coastguard Worker     using BitVector::count;
40*9880d681SAndroid Build Coastguard Worker 
find_first__anonb78d304d0111::RegisterSet41*9880d681SAndroid Build Coastguard Worker     unsigned find_first() const {
42*9880d681SAndroid Build Coastguard Worker       int First = BitVector::find_first();
43*9880d681SAndroid Build Coastguard Worker       if (First < 0)
44*9880d681SAndroid Build Coastguard Worker         return 0;
45*9880d681SAndroid Build Coastguard Worker       return x2v(First);
46*9880d681SAndroid Build Coastguard Worker     }
47*9880d681SAndroid Build Coastguard Worker 
find_next__anonb78d304d0111::RegisterSet48*9880d681SAndroid Build Coastguard Worker     unsigned find_next(unsigned Prev) const {
49*9880d681SAndroid Build Coastguard Worker       int Next = BitVector::find_next(v2x(Prev));
50*9880d681SAndroid Build Coastguard Worker       if (Next < 0)
51*9880d681SAndroid Build Coastguard Worker         return 0;
52*9880d681SAndroid Build Coastguard Worker       return x2v(Next);
53*9880d681SAndroid Build Coastguard Worker     }
54*9880d681SAndroid Build Coastguard Worker 
insert__anonb78d304d0111::RegisterSet55*9880d681SAndroid Build Coastguard Worker     RegisterSet &insert(unsigned R) {
56*9880d681SAndroid Build Coastguard Worker       unsigned Idx = v2x(R);
57*9880d681SAndroid Build Coastguard Worker       ensure(Idx);
58*9880d681SAndroid Build Coastguard Worker       return static_cast<RegisterSet&>(BitVector::set(Idx));
59*9880d681SAndroid Build Coastguard Worker     }
remove__anonb78d304d0111::RegisterSet60*9880d681SAndroid Build Coastguard Worker     RegisterSet &remove(unsigned R) {
61*9880d681SAndroid Build Coastguard Worker       unsigned Idx = v2x(R);
62*9880d681SAndroid Build Coastguard Worker       if (Idx >= size())
63*9880d681SAndroid Build Coastguard Worker         return *this;
64*9880d681SAndroid Build Coastguard Worker       return static_cast<RegisterSet&>(BitVector::reset(Idx));
65*9880d681SAndroid Build Coastguard Worker     }
66*9880d681SAndroid Build Coastguard Worker 
insert__anonb78d304d0111::RegisterSet67*9880d681SAndroid Build Coastguard Worker     RegisterSet &insert(const RegisterSet &Rs) {
68*9880d681SAndroid Build Coastguard Worker       return static_cast<RegisterSet&>(BitVector::operator|=(Rs));
69*9880d681SAndroid Build Coastguard Worker     }
remove__anonb78d304d0111::RegisterSet70*9880d681SAndroid Build Coastguard Worker     RegisterSet &remove(const RegisterSet &Rs) {
71*9880d681SAndroid Build Coastguard Worker       return static_cast<RegisterSet&>(BitVector::reset(Rs));
72*9880d681SAndroid Build Coastguard Worker     }
73*9880d681SAndroid Build Coastguard Worker 
operator []__anonb78d304d0111::RegisterSet74*9880d681SAndroid Build Coastguard Worker     reference operator[](unsigned R) {
75*9880d681SAndroid Build Coastguard Worker       unsigned Idx = v2x(R);
76*9880d681SAndroid Build Coastguard Worker       ensure(Idx);
77*9880d681SAndroid Build Coastguard Worker       return BitVector::operator[](Idx);
78*9880d681SAndroid Build Coastguard Worker     }
operator []__anonb78d304d0111::RegisterSet79*9880d681SAndroid Build Coastguard Worker     bool operator[](unsigned R) const {
80*9880d681SAndroid Build Coastguard Worker       unsigned Idx = v2x(R);
81*9880d681SAndroid Build Coastguard Worker       assert(Idx < size());
82*9880d681SAndroid Build Coastguard Worker       return BitVector::operator[](Idx);
83*9880d681SAndroid Build Coastguard Worker     }
has__anonb78d304d0111::RegisterSet84*9880d681SAndroid Build Coastguard Worker     bool has(unsigned R) const {
85*9880d681SAndroid Build Coastguard Worker       unsigned Idx = v2x(R);
86*9880d681SAndroid Build Coastguard Worker       if (Idx >= size())
87*9880d681SAndroid Build Coastguard Worker         return false;
88*9880d681SAndroid Build Coastguard Worker       return BitVector::test(Idx);
89*9880d681SAndroid Build Coastguard Worker     }
90*9880d681SAndroid Build Coastguard Worker 
empty__anonb78d304d0111::RegisterSet91*9880d681SAndroid Build Coastguard Worker     bool empty() const {
92*9880d681SAndroid Build Coastguard Worker       return !BitVector::any();
93*9880d681SAndroid Build Coastguard Worker     }
includes__anonb78d304d0111::RegisterSet94*9880d681SAndroid Build Coastguard Worker     bool includes(const RegisterSet &Rs) const {
95*9880d681SAndroid Build Coastguard Worker       // A.BitVector::test(B)  <=>  A-B != {}
96*9880d681SAndroid Build Coastguard Worker       return !Rs.BitVector::test(*this);
97*9880d681SAndroid Build Coastguard Worker     }
intersects__anonb78d304d0111::RegisterSet98*9880d681SAndroid Build Coastguard Worker     bool intersects(const RegisterSet &Rs) const {
99*9880d681SAndroid Build Coastguard Worker       return BitVector::anyCommon(Rs);
100*9880d681SAndroid Build Coastguard Worker     }
101*9880d681SAndroid Build Coastguard Worker 
102*9880d681SAndroid Build Coastguard Worker   private:
ensure__anonb78d304d0111::RegisterSet103*9880d681SAndroid Build Coastguard Worker     void ensure(unsigned Idx) {
104*9880d681SAndroid Build Coastguard Worker       if (size() <= Idx)
105*9880d681SAndroid Build Coastguard Worker         resize(std::max(Idx+1, 32U));
106*9880d681SAndroid Build Coastguard Worker     }
v2x__anonb78d304d0111::RegisterSet107*9880d681SAndroid Build Coastguard Worker     static inline unsigned v2x(unsigned v) {
108*9880d681SAndroid Build Coastguard Worker       return TargetRegisterInfo::virtReg2Index(v);
109*9880d681SAndroid Build Coastguard Worker     }
x2v__anonb78d304d0111::RegisterSet110*9880d681SAndroid Build Coastguard Worker     static inline unsigned x2v(unsigned x) {
111*9880d681SAndroid Build Coastguard Worker       return TargetRegisterInfo::index2VirtReg(x);
112*9880d681SAndroid Build Coastguard Worker     }
113*9880d681SAndroid Build Coastguard Worker   };
114*9880d681SAndroid Build Coastguard Worker 
115*9880d681SAndroid Build Coastguard Worker 
116*9880d681SAndroid Build Coastguard Worker   struct PrintRegSet {
PrintRegSet__anonb78d304d0111::PrintRegSet117*9880d681SAndroid Build Coastguard Worker     PrintRegSet(const RegisterSet &S, const TargetRegisterInfo *RI)
118*9880d681SAndroid Build Coastguard Worker       : RS(S), TRI(RI) {}
119*9880d681SAndroid Build Coastguard Worker     friend raw_ostream &operator<< (raw_ostream &OS,
120*9880d681SAndroid Build Coastguard Worker           const PrintRegSet &P);
121*9880d681SAndroid Build Coastguard Worker   private:
122*9880d681SAndroid Build Coastguard Worker     const RegisterSet &RS;
123*9880d681SAndroid Build Coastguard Worker     const TargetRegisterInfo *TRI;
124*9880d681SAndroid Build Coastguard Worker   };
125*9880d681SAndroid Build Coastguard Worker 
126*9880d681SAndroid Build Coastguard Worker   raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P)
127*9880d681SAndroid Build Coastguard Worker     LLVM_ATTRIBUTE_UNUSED;
operator <<(raw_ostream & OS,const PrintRegSet & P)128*9880d681SAndroid Build Coastguard Worker   raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) {
129*9880d681SAndroid Build Coastguard Worker     OS << '{';
130*9880d681SAndroid Build Coastguard Worker     for (unsigned R = P.RS.find_first(); R; R = P.RS.find_next(R))
131*9880d681SAndroid Build Coastguard Worker       OS << ' ' << PrintReg(R, P.TRI);
132*9880d681SAndroid Build Coastguard Worker     OS << " }";
133*9880d681SAndroid Build Coastguard Worker     return OS;
134*9880d681SAndroid Build Coastguard Worker   }
135*9880d681SAndroid Build Coastguard Worker }
136*9880d681SAndroid Build Coastguard Worker 
137*9880d681SAndroid Build Coastguard Worker 
138*9880d681SAndroid Build Coastguard Worker namespace {
139*9880d681SAndroid Build Coastguard Worker   class Transformation;
140*9880d681SAndroid Build Coastguard Worker 
141*9880d681SAndroid Build Coastguard Worker   class HexagonBitSimplify : public MachineFunctionPass {
142*9880d681SAndroid Build Coastguard Worker   public:
143*9880d681SAndroid Build Coastguard Worker     static char ID;
HexagonBitSimplify()144*9880d681SAndroid Build Coastguard Worker     HexagonBitSimplify() : MachineFunctionPass(ID), MDT(0) {
145*9880d681SAndroid Build Coastguard Worker       initializeHexagonBitSimplifyPass(*PassRegistry::getPassRegistry());
146*9880d681SAndroid Build Coastguard Worker     }
getPassName() const147*9880d681SAndroid Build Coastguard Worker     virtual const char *getPassName() const {
148*9880d681SAndroid Build Coastguard Worker       return "Hexagon bit simplification";
149*9880d681SAndroid Build Coastguard Worker     }
getAnalysisUsage(AnalysisUsage & AU) const150*9880d681SAndroid Build Coastguard Worker     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
151*9880d681SAndroid Build Coastguard Worker       AU.addRequired<MachineDominatorTree>();
152*9880d681SAndroid Build Coastguard Worker       AU.addPreserved<MachineDominatorTree>();
153*9880d681SAndroid Build Coastguard Worker       MachineFunctionPass::getAnalysisUsage(AU);
154*9880d681SAndroid Build Coastguard Worker     }
155*9880d681SAndroid Build Coastguard Worker     virtual bool runOnMachineFunction(MachineFunction &MF);
156*9880d681SAndroid Build Coastguard Worker 
157*9880d681SAndroid Build Coastguard Worker     static void getInstrDefs(const MachineInstr &MI, RegisterSet &Defs);
158*9880d681SAndroid Build Coastguard Worker     static void getInstrUses(const MachineInstr &MI, RegisterSet &Uses);
159*9880d681SAndroid Build Coastguard Worker     static bool isEqual(const BitTracker::RegisterCell &RC1, uint16_t B1,
160*9880d681SAndroid Build Coastguard Worker         const BitTracker::RegisterCell &RC2, uint16_t B2, uint16_t W);
161*9880d681SAndroid Build Coastguard Worker     static bool isZero(const BitTracker::RegisterCell &RC, uint16_t B,
162*9880d681SAndroid Build Coastguard Worker         uint16_t W);
163*9880d681SAndroid Build Coastguard Worker     static bool getConst(const BitTracker::RegisterCell &RC, uint16_t B,
164*9880d681SAndroid Build Coastguard Worker         uint16_t W, uint64_t &U);
165*9880d681SAndroid Build Coastguard Worker     static bool replaceReg(unsigned OldR, unsigned NewR,
166*9880d681SAndroid Build Coastguard Worker         MachineRegisterInfo &MRI);
167*9880d681SAndroid Build Coastguard Worker     static bool getSubregMask(const BitTracker::RegisterRef &RR,
168*9880d681SAndroid Build Coastguard Worker         unsigned &Begin, unsigned &Width, MachineRegisterInfo &MRI);
169*9880d681SAndroid Build Coastguard Worker     static bool replaceRegWithSub(unsigned OldR, unsigned NewR,
170*9880d681SAndroid Build Coastguard Worker         unsigned NewSR, MachineRegisterInfo &MRI);
171*9880d681SAndroid Build Coastguard Worker     static bool replaceSubWithSub(unsigned OldR, unsigned OldSR,
172*9880d681SAndroid Build Coastguard Worker         unsigned NewR, unsigned NewSR, MachineRegisterInfo &MRI);
173*9880d681SAndroid Build Coastguard Worker     static bool parseRegSequence(const MachineInstr &I,
174*9880d681SAndroid Build Coastguard Worker         BitTracker::RegisterRef &SL, BitTracker::RegisterRef &SH);
175*9880d681SAndroid Build Coastguard Worker 
176*9880d681SAndroid Build Coastguard Worker     static bool getUsedBitsInStore(unsigned Opc, BitVector &Bits,
177*9880d681SAndroid Build Coastguard Worker         uint16_t Begin);
178*9880d681SAndroid Build Coastguard Worker     static bool getUsedBits(unsigned Opc, unsigned OpN, BitVector &Bits,
179*9880d681SAndroid Build Coastguard Worker         uint16_t Begin, const HexagonInstrInfo &HII);
180*9880d681SAndroid Build Coastguard Worker 
181*9880d681SAndroid Build Coastguard Worker     static const TargetRegisterClass *getFinalVRegClass(
182*9880d681SAndroid Build Coastguard Worker         const BitTracker::RegisterRef &RR, MachineRegisterInfo &MRI);
183*9880d681SAndroid Build Coastguard Worker     static bool isTransparentCopy(const BitTracker::RegisterRef &RD,
184*9880d681SAndroid Build Coastguard Worker         const BitTracker::RegisterRef &RS, MachineRegisterInfo &MRI);
185*9880d681SAndroid Build Coastguard Worker 
186*9880d681SAndroid Build Coastguard Worker   private:
187*9880d681SAndroid Build Coastguard Worker     MachineDominatorTree *MDT;
188*9880d681SAndroid Build Coastguard Worker 
189*9880d681SAndroid Build Coastguard Worker     bool visitBlock(MachineBasicBlock &B, Transformation &T, RegisterSet &AVs);
190*9880d681SAndroid Build Coastguard Worker   };
191*9880d681SAndroid Build Coastguard Worker 
192*9880d681SAndroid Build Coastguard Worker   char HexagonBitSimplify::ID = 0;
193*9880d681SAndroid Build Coastguard Worker   typedef HexagonBitSimplify HBS;
194*9880d681SAndroid Build Coastguard Worker 
195*9880d681SAndroid Build Coastguard Worker 
196*9880d681SAndroid Build Coastguard Worker   // The purpose of this class is to provide a common facility to traverse
197*9880d681SAndroid Build Coastguard Worker   // the function top-down or bottom-up via the dominator tree, and keep
198*9880d681SAndroid Build Coastguard Worker   // track of the available registers.
199*9880d681SAndroid Build Coastguard Worker   class Transformation {
200*9880d681SAndroid Build Coastguard Worker   public:
201*9880d681SAndroid Build Coastguard Worker     bool TopDown;
Transformation(bool TD)202*9880d681SAndroid Build Coastguard Worker     Transformation(bool TD) : TopDown(TD) {}
203*9880d681SAndroid Build Coastguard Worker     virtual bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) = 0;
~Transformation()204*9880d681SAndroid Build Coastguard Worker     virtual ~Transformation() {}
205*9880d681SAndroid Build Coastguard Worker   };
206*9880d681SAndroid Build Coastguard Worker }
207*9880d681SAndroid Build Coastguard Worker 
208*9880d681SAndroid Build Coastguard Worker INITIALIZE_PASS_BEGIN(HexagonBitSimplify, "hexbit",
209*9880d681SAndroid Build Coastguard Worker       "Hexagon bit simplification", false, false)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)210*9880d681SAndroid Build Coastguard Worker INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
211*9880d681SAndroid Build Coastguard Worker INITIALIZE_PASS_END(HexagonBitSimplify, "hexbit",
212*9880d681SAndroid Build Coastguard Worker       "Hexagon bit simplification", false, false)
213*9880d681SAndroid Build Coastguard Worker 
214*9880d681SAndroid Build Coastguard Worker 
215*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::visitBlock(MachineBasicBlock &B, Transformation &T,
216*9880d681SAndroid Build Coastguard Worker       RegisterSet &AVs) {
217*9880d681SAndroid Build Coastguard Worker   MachineDomTreeNode *N = MDT->getNode(&B);
218*9880d681SAndroid Build Coastguard Worker   typedef GraphTraits<MachineDomTreeNode*> GTN;
219*9880d681SAndroid Build Coastguard Worker   bool Changed = false;
220*9880d681SAndroid Build Coastguard Worker 
221*9880d681SAndroid Build Coastguard Worker   if (T.TopDown)
222*9880d681SAndroid Build Coastguard Worker     Changed = T.processBlock(B, AVs);
223*9880d681SAndroid Build Coastguard Worker 
224*9880d681SAndroid Build Coastguard Worker   RegisterSet Defs;
225*9880d681SAndroid Build Coastguard Worker   for (auto &I : B)
226*9880d681SAndroid Build Coastguard Worker     getInstrDefs(I, Defs);
227*9880d681SAndroid Build Coastguard Worker   RegisterSet NewAVs = AVs;
228*9880d681SAndroid Build Coastguard Worker   NewAVs.insert(Defs);
229*9880d681SAndroid Build Coastguard Worker 
230*9880d681SAndroid Build Coastguard Worker   for (auto I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I) {
231*9880d681SAndroid Build Coastguard Worker     MachineBasicBlock *SB = (*I)->getBlock();
232*9880d681SAndroid Build Coastguard Worker     Changed |= visitBlock(*SB, T, NewAVs);
233*9880d681SAndroid Build Coastguard Worker   }
234*9880d681SAndroid Build Coastguard Worker   if (!T.TopDown)
235*9880d681SAndroid Build Coastguard Worker     Changed |= T.processBlock(B, AVs);
236*9880d681SAndroid Build Coastguard Worker 
237*9880d681SAndroid Build Coastguard Worker   return Changed;
238*9880d681SAndroid Build Coastguard Worker }
239*9880d681SAndroid Build Coastguard Worker 
240*9880d681SAndroid Build Coastguard Worker //
241*9880d681SAndroid Build Coastguard Worker // Utility functions:
242*9880d681SAndroid Build Coastguard Worker //
getInstrDefs(const MachineInstr & MI,RegisterSet & Defs)243*9880d681SAndroid Build Coastguard Worker void HexagonBitSimplify::getInstrDefs(const MachineInstr &MI,
244*9880d681SAndroid Build Coastguard Worker       RegisterSet &Defs) {
245*9880d681SAndroid Build Coastguard Worker   for (auto &Op : MI.operands()) {
246*9880d681SAndroid Build Coastguard Worker     if (!Op.isReg() || !Op.isDef())
247*9880d681SAndroid Build Coastguard Worker       continue;
248*9880d681SAndroid Build Coastguard Worker     unsigned R = Op.getReg();
249*9880d681SAndroid Build Coastguard Worker     if (!TargetRegisterInfo::isVirtualRegister(R))
250*9880d681SAndroid Build Coastguard Worker       continue;
251*9880d681SAndroid Build Coastguard Worker     Defs.insert(R);
252*9880d681SAndroid Build Coastguard Worker   }
253*9880d681SAndroid Build Coastguard Worker }
254*9880d681SAndroid Build Coastguard Worker 
getInstrUses(const MachineInstr & MI,RegisterSet & Uses)255*9880d681SAndroid Build Coastguard Worker void HexagonBitSimplify::getInstrUses(const MachineInstr &MI,
256*9880d681SAndroid Build Coastguard Worker       RegisterSet &Uses) {
257*9880d681SAndroid Build Coastguard Worker   for (auto &Op : MI.operands()) {
258*9880d681SAndroid Build Coastguard Worker     if (!Op.isReg() || !Op.isUse())
259*9880d681SAndroid Build Coastguard Worker       continue;
260*9880d681SAndroid Build Coastguard Worker     unsigned R = Op.getReg();
261*9880d681SAndroid Build Coastguard Worker     if (!TargetRegisterInfo::isVirtualRegister(R))
262*9880d681SAndroid Build Coastguard Worker       continue;
263*9880d681SAndroid Build Coastguard Worker     Uses.insert(R);
264*9880d681SAndroid Build Coastguard Worker   }
265*9880d681SAndroid Build Coastguard Worker }
266*9880d681SAndroid Build Coastguard Worker 
267*9880d681SAndroid Build Coastguard Worker // 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)268*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::isEqual(const BitTracker::RegisterCell &RC1,
269*9880d681SAndroid Build Coastguard Worker       uint16_t B1, const BitTracker::RegisterCell &RC2, uint16_t B2,
270*9880d681SAndroid Build Coastguard Worker       uint16_t W) {
271*9880d681SAndroid Build Coastguard Worker   for (uint16_t i = 0; i < W; ++i) {
272*9880d681SAndroid Build Coastguard Worker     // If RC1[i] is "bottom", it cannot be proven equal to RC2[i].
273*9880d681SAndroid Build Coastguard Worker     if (RC1[B1+i].Type == BitTracker::BitValue::Ref && RC1[B1+i].RefI.Reg == 0)
274*9880d681SAndroid Build Coastguard Worker       return false;
275*9880d681SAndroid Build Coastguard Worker     // Same for RC2[i].
276*9880d681SAndroid Build Coastguard Worker     if (RC2[B2+i].Type == BitTracker::BitValue::Ref && RC2[B2+i].RefI.Reg == 0)
277*9880d681SAndroid Build Coastguard Worker       return false;
278*9880d681SAndroid Build Coastguard Worker     if (RC1[B1+i] != RC2[B2+i])
279*9880d681SAndroid Build Coastguard Worker       return false;
280*9880d681SAndroid Build Coastguard Worker   }
281*9880d681SAndroid Build Coastguard Worker   return true;
282*9880d681SAndroid Build Coastguard Worker }
283*9880d681SAndroid Build Coastguard Worker 
isZero(const BitTracker::RegisterCell & RC,uint16_t B,uint16_t W)284*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::isZero(const BitTracker::RegisterCell &RC,
285*9880d681SAndroid Build Coastguard Worker       uint16_t B, uint16_t W) {
286*9880d681SAndroid Build Coastguard Worker   assert(B < RC.width() && B+W <= RC.width());
287*9880d681SAndroid Build Coastguard Worker   for (uint16_t i = B; i < B+W; ++i)
288*9880d681SAndroid Build Coastguard Worker     if (!RC[i].is(0))
289*9880d681SAndroid Build Coastguard Worker       return false;
290*9880d681SAndroid Build Coastguard Worker   return true;
291*9880d681SAndroid Build Coastguard Worker }
292*9880d681SAndroid Build Coastguard Worker 
293*9880d681SAndroid Build Coastguard Worker 
getConst(const BitTracker::RegisterCell & RC,uint16_t B,uint16_t W,uint64_t & U)294*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::getConst(const BitTracker::RegisterCell &RC,
295*9880d681SAndroid Build Coastguard Worker         uint16_t B, uint16_t W, uint64_t &U) {
296*9880d681SAndroid Build Coastguard Worker   assert(B < RC.width() && B+W <= RC.width());
297*9880d681SAndroid Build Coastguard Worker   int64_t T = 0;
298*9880d681SAndroid Build Coastguard Worker   for (uint16_t i = B+W; i > B; --i) {
299*9880d681SAndroid Build Coastguard Worker     const BitTracker::BitValue &BV = RC[i-1];
300*9880d681SAndroid Build Coastguard Worker     T <<= 1;
301*9880d681SAndroid Build Coastguard Worker     if (BV.is(1))
302*9880d681SAndroid Build Coastguard Worker       T |= 1;
303*9880d681SAndroid Build Coastguard Worker     else if (!BV.is(0))
304*9880d681SAndroid Build Coastguard Worker       return false;
305*9880d681SAndroid Build Coastguard Worker   }
306*9880d681SAndroid Build Coastguard Worker   U = T;
307*9880d681SAndroid Build Coastguard Worker   return true;
308*9880d681SAndroid Build Coastguard Worker }
309*9880d681SAndroid Build Coastguard Worker 
310*9880d681SAndroid Build Coastguard Worker 
replaceReg(unsigned OldR,unsigned NewR,MachineRegisterInfo & MRI)311*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::replaceReg(unsigned OldR, unsigned NewR,
312*9880d681SAndroid Build Coastguard Worker       MachineRegisterInfo &MRI) {
313*9880d681SAndroid Build Coastguard Worker   if (!TargetRegisterInfo::isVirtualRegister(OldR) ||
314*9880d681SAndroid Build Coastguard Worker       !TargetRegisterInfo::isVirtualRegister(NewR))
315*9880d681SAndroid Build Coastguard Worker     return false;
316*9880d681SAndroid Build Coastguard Worker   auto Begin = MRI.use_begin(OldR), End = MRI.use_end();
317*9880d681SAndroid Build Coastguard Worker   decltype(End) NextI;
318*9880d681SAndroid Build Coastguard Worker   for (auto I = Begin; I != End; I = NextI) {
319*9880d681SAndroid Build Coastguard Worker     NextI = std::next(I);
320*9880d681SAndroid Build Coastguard Worker     I->setReg(NewR);
321*9880d681SAndroid Build Coastguard Worker   }
322*9880d681SAndroid Build Coastguard Worker   return Begin != End;
323*9880d681SAndroid Build Coastguard Worker }
324*9880d681SAndroid Build Coastguard Worker 
325*9880d681SAndroid Build Coastguard Worker 
replaceRegWithSub(unsigned OldR,unsigned NewR,unsigned NewSR,MachineRegisterInfo & MRI)326*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::replaceRegWithSub(unsigned OldR, unsigned NewR,
327*9880d681SAndroid Build Coastguard Worker       unsigned NewSR, MachineRegisterInfo &MRI) {
328*9880d681SAndroid Build Coastguard Worker   if (!TargetRegisterInfo::isVirtualRegister(OldR) ||
329*9880d681SAndroid Build Coastguard Worker       !TargetRegisterInfo::isVirtualRegister(NewR))
330*9880d681SAndroid Build Coastguard Worker     return false;
331*9880d681SAndroid Build Coastguard Worker   auto Begin = MRI.use_begin(OldR), End = MRI.use_end();
332*9880d681SAndroid Build Coastguard Worker   decltype(End) NextI;
333*9880d681SAndroid Build Coastguard Worker   for (auto I = Begin; I != End; I = NextI) {
334*9880d681SAndroid Build Coastguard Worker     NextI = std::next(I);
335*9880d681SAndroid Build Coastguard Worker     I->setReg(NewR);
336*9880d681SAndroid Build Coastguard Worker     I->setSubReg(NewSR);
337*9880d681SAndroid Build Coastguard Worker   }
338*9880d681SAndroid Build Coastguard Worker   return Begin != End;
339*9880d681SAndroid Build Coastguard Worker }
340*9880d681SAndroid Build Coastguard Worker 
341*9880d681SAndroid Build Coastguard Worker 
replaceSubWithSub(unsigned OldR,unsigned OldSR,unsigned NewR,unsigned NewSR,MachineRegisterInfo & MRI)342*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::replaceSubWithSub(unsigned OldR, unsigned OldSR,
343*9880d681SAndroid Build Coastguard Worker       unsigned NewR, unsigned NewSR, MachineRegisterInfo &MRI) {
344*9880d681SAndroid Build Coastguard Worker   if (!TargetRegisterInfo::isVirtualRegister(OldR) ||
345*9880d681SAndroid Build Coastguard Worker       !TargetRegisterInfo::isVirtualRegister(NewR))
346*9880d681SAndroid Build Coastguard Worker     return false;
347*9880d681SAndroid Build Coastguard Worker   auto Begin = MRI.use_begin(OldR), End = MRI.use_end();
348*9880d681SAndroid Build Coastguard Worker   decltype(End) NextI;
349*9880d681SAndroid Build Coastguard Worker   for (auto I = Begin; I != End; I = NextI) {
350*9880d681SAndroid Build Coastguard Worker     NextI = std::next(I);
351*9880d681SAndroid Build Coastguard Worker     if (I->getSubReg() != OldSR)
352*9880d681SAndroid Build Coastguard Worker       continue;
353*9880d681SAndroid Build Coastguard Worker     I->setReg(NewR);
354*9880d681SAndroid Build Coastguard Worker     I->setSubReg(NewSR);
355*9880d681SAndroid Build Coastguard Worker   }
356*9880d681SAndroid Build Coastguard Worker   return Begin != End;
357*9880d681SAndroid Build Coastguard Worker }
358*9880d681SAndroid Build Coastguard Worker 
359*9880d681SAndroid Build Coastguard Worker 
360*9880d681SAndroid Build Coastguard Worker // For a register ref (pair Reg:Sub), set Begin to the position of the LSB
361*9880d681SAndroid Build Coastguard Worker // of Sub in Reg, and set Width to the size of Sub in bits. Return true,
362*9880d681SAndroid Build Coastguard Worker // if this succeeded, otherwise return false.
getSubregMask(const BitTracker::RegisterRef & RR,unsigned & Begin,unsigned & Width,MachineRegisterInfo & MRI)363*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::getSubregMask(const BitTracker::RegisterRef &RR,
364*9880d681SAndroid Build Coastguard Worker       unsigned &Begin, unsigned &Width, MachineRegisterInfo &MRI) {
365*9880d681SAndroid Build Coastguard Worker   const TargetRegisterClass *RC = MRI.getRegClass(RR.Reg);
366*9880d681SAndroid Build Coastguard Worker   if (RC == &Hexagon::IntRegsRegClass) {
367*9880d681SAndroid Build Coastguard Worker     assert(RR.Sub == 0);
368*9880d681SAndroid Build Coastguard Worker     Begin = 0;
369*9880d681SAndroid Build Coastguard Worker     Width = 32;
370*9880d681SAndroid Build Coastguard Worker     return true;
371*9880d681SAndroid Build Coastguard Worker   }
372*9880d681SAndroid Build Coastguard Worker   if (RC == &Hexagon::DoubleRegsRegClass) {
373*9880d681SAndroid Build Coastguard Worker     if (RR.Sub == 0) {
374*9880d681SAndroid Build Coastguard Worker       Begin = 0;
375*9880d681SAndroid Build Coastguard Worker       Width = 64;
376*9880d681SAndroid Build Coastguard Worker       return true;
377*9880d681SAndroid Build Coastguard Worker     }
378*9880d681SAndroid Build Coastguard Worker     assert(RR.Sub == Hexagon::subreg_loreg || RR.Sub == Hexagon::subreg_hireg);
379*9880d681SAndroid Build Coastguard Worker     Width = 32;
380*9880d681SAndroid Build Coastguard Worker     Begin = (RR.Sub == Hexagon::subreg_loreg ? 0 : 32);
381*9880d681SAndroid Build Coastguard Worker     return true;
382*9880d681SAndroid Build Coastguard Worker   }
383*9880d681SAndroid Build Coastguard Worker   return false;
384*9880d681SAndroid Build Coastguard Worker }
385*9880d681SAndroid Build Coastguard Worker 
386*9880d681SAndroid Build Coastguard Worker 
387*9880d681SAndroid Build Coastguard Worker // For a REG_SEQUENCE, set SL to the low subregister and SH to the high
388*9880d681SAndroid Build Coastguard Worker // subregister.
parseRegSequence(const MachineInstr & I,BitTracker::RegisterRef & SL,BitTracker::RegisterRef & SH)389*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::parseRegSequence(const MachineInstr &I,
390*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef &SL, BitTracker::RegisterRef &SH) {
391*9880d681SAndroid Build Coastguard Worker   assert(I.getOpcode() == TargetOpcode::REG_SEQUENCE);
392*9880d681SAndroid Build Coastguard Worker   unsigned Sub1 = I.getOperand(2).getImm(), Sub2 = I.getOperand(4).getImm();
393*9880d681SAndroid Build Coastguard Worker   assert(Sub1 != Sub2);
394*9880d681SAndroid Build Coastguard Worker   if (Sub1 == Hexagon::subreg_loreg && Sub2 == Hexagon::subreg_hireg) {
395*9880d681SAndroid Build Coastguard Worker     SL = I.getOperand(1);
396*9880d681SAndroid Build Coastguard Worker     SH = I.getOperand(3);
397*9880d681SAndroid Build Coastguard Worker     return true;
398*9880d681SAndroid Build Coastguard Worker   }
399*9880d681SAndroid Build Coastguard Worker   if (Sub1 == Hexagon::subreg_hireg && Sub2 == Hexagon::subreg_loreg) {
400*9880d681SAndroid Build Coastguard Worker     SH = I.getOperand(1);
401*9880d681SAndroid Build Coastguard Worker     SL = I.getOperand(3);
402*9880d681SAndroid Build Coastguard Worker     return true;
403*9880d681SAndroid Build Coastguard Worker   }
404*9880d681SAndroid Build Coastguard Worker   return false;
405*9880d681SAndroid Build Coastguard Worker }
406*9880d681SAndroid Build Coastguard Worker 
407*9880d681SAndroid Build Coastguard Worker 
408*9880d681SAndroid Build Coastguard Worker // All stores (except 64-bit stores) take a 32-bit register as the source
409*9880d681SAndroid Build Coastguard Worker // of the value to be stored. If the instruction stores into a location
410*9880d681SAndroid Build Coastguard Worker // that is shorter than 32 bits, some bits of the source register are not
411*9880d681SAndroid Build Coastguard Worker // used. For each store instruction, calculate the set of used bits in
412*9880d681SAndroid Build Coastguard Worker // the source register, and set appropriate bits in Bits. Return true if
413*9880d681SAndroid Build Coastguard Worker // the bits are calculated, false otherwise.
getUsedBitsInStore(unsigned Opc,BitVector & Bits,uint16_t Begin)414*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::getUsedBitsInStore(unsigned Opc, BitVector &Bits,
415*9880d681SAndroid Build Coastguard Worker       uint16_t Begin) {
416*9880d681SAndroid Build Coastguard Worker   using namespace Hexagon;
417*9880d681SAndroid Build Coastguard Worker 
418*9880d681SAndroid Build Coastguard Worker   switch (Opc) {
419*9880d681SAndroid Build Coastguard Worker     // Store byte
420*9880d681SAndroid Build Coastguard Worker     case S2_storerb_io:           // memb(Rs32+#s11:0)=Rt32
421*9880d681SAndroid Build Coastguard Worker     case S2_storerbnew_io:        // memb(Rs32+#s11:0)=Nt8.new
422*9880d681SAndroid Build Coastguard Worker     case S2_pstorerbt_io:         // if (Pv4) memb(Rs32+#u6:0)=Rt32
423*9880d681SAndroid Build Coastguard Worker     case S2_pstorerbf_io:         // if (!Pv4) memb(Rs32+#u6:0)=Rt32
424*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbtnew_io:      // if (Pv4.new) memb(Rs32+#u6:0)=Rt32
425*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbfnew_io:      // if (!Pv4.new) memb(Rs32+#u6:0)=Rt32
426*9880d681SAndroid Build Coastguard Worker     case S2_pstorerbnewt_io:      // if (Pv4) memb(Rs32+#u6:0)=Nt8.new
427*9880d681SAndroid Build Coastguard Worker     case S2_pstorerbnewf_io:      // if (!Pv4) memb(Rs32+#u6:0)=Nt8.new
428*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbnewtnew_io:   // if (Pv4.new) memb(Rs32+#u6:0)=Nt8.new
429*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbnewfnew_io:   // if (!Pv4.new) memb(Rs32+#u6:0)=Nt8.new
430*9880d681SAndroid Build Coastguard Worker     case S2_storerb_pi:           // memb(Rx32++#s4:0)=Rt32
431*9880d681SAndroid Build Coastguard Worker     case S2_storerbnew_pi:        // memb(Rx32++#s4:0)=Nt8.new
432*9880d681SAndroid Build Coastguard Worker     case S2_pstorerbt_pi:         // if (Pv4) memb(Rx32++#s4:0)=Rt32
433*9880d681SAndroid Build Coastguard Worker     case S2_pstorerbf_pi:         // if (!Pv4) memb(Rx32++#s4:0)=Rt32
434*9880d681SAndroid Build Coastguard Worker     case S2_pstorerbtnew_pi:      // if (Pv4.new) memb(Rx32++#s4:0)=Rt32
435*9880d681SAndroid Build Coastguard Worker     case S2_pstorerbfnew_pi:      // if (!Pv4.new) memb(Rx32++#s4:0)=Rt32
436*9880d681SAndroid Build Coastguard Worker     case S2_pstorerbnewt_pi:      // if (Pv4) memb(Rx32++#s4:0)=Nt8.new
437*9880d681SAndroid Build Coastguard Worker     case S2_pstorerbnewf_pi:      // if (!Pv4) memb(Rx32++#s4:0)=Nt8.new
438*9880d681SAndroid Build Coastguard Worker     case S2_pstorerbnewtnew_pi:   // if (Pv4.new) memb(Rx32++#s4:0)=Nt8.new
439*9880d681SAndroid Build Coastguard Worker     case S2_pstorerbnewfnew_pi:   // if (!Pv4.new) memb(Rx32++#s4:0)=Nt8.new
440*9880d681SAndroid Build Coastguard Worker     case S4_storerb_ap:           // memb(Re32=#U6)=Rt32
441*9880d681SAndroid Build Coastguard Worker     case S4_storerbnew_ap:        // memb(Re32=#U6)=Nt8.new
442*9880d681SAndroid Build Coastguard Worker     case S2_storerb_pr:           // memb(Rx32++Mu2)=Rt32
443*9880d681SAndroid Build Coastguard Worker     case S2_storerbnew_pr:        // memb(Rx32++Mu2)=Nt8.new
444*9880d681SAndroid Build Coastguard Worker     case S4_storerb_ur:           // memb(Ru32<<#u2+#U6)=Rt32
445*9880d681SAndroid Build Coastguard Worker     case S4_storerbnew_ur:        // memb(Ru32<<#u2+#U6)=Nt8.new
446*9880d681SAndroid Build Coastguard Worker     case S2_storerb_pbr:          // memb(Rx32++Mu2:brev)=Rt32
447*9880d681SAndroid Build Coastguard Worker     case S2_storerbnew_pbr:       // memb(Rx32++Mu2:brev)=Nt8.new
448*9880d681SAndroid Build Coastguard Worker     case S2_storerb_pci:          // memb(Rx32++#s4:0:circ(Mu2))=Rt32
449*9880d681SAndroid Build Coastguard Worker     case S2_storerbnew_pci:       // memb(Rx32++#s4:0:circ(Mu2))=Nt8.new
450*9880d681SAndroid Build Coastguard Worker     case S2_storerb_pcr:          // memb(Rx32++I:circ(Mu2))=Rt32
451*9880d681SAndroid Build Coastguard Worker     case S2_storerbnew_pcr:       // memb(Rx32++I:circ(Mu2))=Nt8.new
452*9880d681SAndroid Build Coastguard Worker     case S4_storerb_rr:           // memb(Rs32+Ru32<<#u2)=Rt32
453*9880d681SAndroid Build Coastguard Worker     case S4_storerbnew_rr:        // memb(Rs32+Ru32<<#u2)=Nt8.new
454*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbt_rr:         // if (Pv4) memb(Rs32+Ru32<<#u2)=Rt32
455*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbf_rr:         // if (!Pv4) memb(Rs32+Ru32<<#u2)=Rt32
456*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbtnew_rr:      // if (Pv4.new) memb(Rs32+Ru32<<#u2)=Rt32
457*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbfnew_rr:      // if (!Pv4.new) memb(Rs32+Ru32<<#u2)=Rt32
458*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbnewt_rr:      // if (Pv4) memb(Rs32+Ru32<<#u2)=Nt8.new
459*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbnewf_rr:      // if (!Pv4) memb(Rs32+Ru32<<#u2)=Nt8.new
460*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbnewtnew_rr:   // if (Pv4.new) memb(Rs32+Ru32<<#u2)=Nt8.new
461*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbnewfnew_rr:   // if (!Pv4.new) memb(Rs32+Ru32<<#u2)=Nt8.new
462*9880d681SAndroid Build Coastguard Worker     case S2_storerbgp:            // memb(gp+#u16:0)=Rt32
463*9880d681SAndroid Build Coastguard Worker     case S2_storerbnewgp:         // memb(gp+#u16:0)=Nt8.new
464*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbt_abs:        // if (Pv4) memb(#u6)=Rt32
465*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbf_abs:        // if (!Pv4) memb(#u6)=Rt32
466*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbtnew_abs:     // if (Pv4.new) memb(#u6)=Rt32
467*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbfnew_abs:     // if (!Pv4.new) memb(#u6)=Rt32
468*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbnewt_abs:     // if (Pv4) memb(#u6)=Nt8.new
469*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbnewf_abs:     // if (!Pv4) memb(#u6)=Nt8.new
470*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbnewtnew_abs:  // if (Pv4.new) memb(#u6)=Nt8.new
471*9880d681SAndroid Build Coastguard Worker     case S4_pstorerbnewfnew_abs:  // if (!Pv4.new) memb(#u6)=Nt8.new
472*9880d681SAndroid Build Coastguard Worker       Bits.set(Begin, Begin+8);
473*9880d681SAndroid Build Coastguard Worker       return true;
474*9880d681SAndroid Build Coastguard Worker 
475*9880d681SAndroid Build Coastguard Worker     // Store low half
476*9880d681SAndroid Build Coastguard Worker     case S2_storerh_io:           // memh(Rs32+#s11:1)=Rt32
477*9880d681SAndroid Build Coastguard Worker     case S2_storerhnew_io:        // memh(Rs32+#s11:1)=Nt8.new
478*9880d681SAndroid Build Coastguard Worker     case S2_pstorerht_io:         // if (Pv4) memh(Rs32+#u6:1)=Rt32
479*9880d681SAndroid Build Coastguard Worker     case S2_pstorerhf_io:         // if (!Pv4) memh(Rs32+#u6:1)=Rt32
480*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhtnew_io:      // if (Pv4.new) memh(Rs32+#u6:1)=Rt32
481*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhfnew_io:      // if (!Pv4.new) memh(Rs32+#u6:1)=Rt32
482*9880d681SAndroid Build Coastguard Worker     case S2_pstorerhnewt_io:      // if (Pv4) memh(Rs32+#u6:1)=Nt8.new
483*9880d681SAndroid Build Coastguard Worker     case S2_pstorerhnewf_io:      // if (!Pv4) memh(Rs32+#u6:1)=Nt8.new
484*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhnewtnew_io:   // if (Pv4.new) memh(Rs32+#u6:1)=Nt8.new
485*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhnewfnew_io:   // if (!Pv4.new) memh(Rs32+#u6:1)=Nt8.new
486*9880d681SAndroid Build Coastguard Worker     case S2_storerh_pi:           // memh(Rx32++#s4:1)=Rt32
487*9880d681SAndroid Build Coastguard Worker     case S2_storerhnew_pi:        // memh(Rx32++#s4:1)=Nt8.new
488*9880d681SAndroid Build Coastguard Worker     case S2_pstorerht_pi:         // if (Pv4) memh(Rx32++#s4:1)=Rt32
489*9880d681SAndroid Build Coastguard Worker     case S2_pstorerhf_pi:         // if (!Pv4) memh(Rx32++#s4:1)=Rt32
490*9880d681SAndroid Build Coastguard Worker     case S2_pstorerhtnew_pi:      // if (Pv4.new) memh(Rx32++#s4:1)=Rt32
491*9880d681SAndroid Build Coastguard Worker     case S2_pstorerhfnew_pi:      // if (!Pv4.new) memh(Rx32++#s4:1)=Rt32
492*9880d681SAndroid Build Coastguard Worker     case S2_pstorerhnewt_pi:      // if (Pv4) memh(Rx32++#s4:1)=Nt8.new
493*9880d681SAndroid Build Coastguard Worker     case S2_pstorerhnewf_pi:      // if (!Pv4) memh(Rx32++#s4:1)=Nt8.new
494*9880d681SAndroid Build Coastguard Worker     case S2_pstorerhnewtnew_pi:   // if (Pv4.new) memh(Rx32++#s4:1)=Nt8.new
495*9880d681SAndroid Build Coastguard Worker     case S2_pstorerhnewfnew_pi:   // if (!Pv4.new) memh(Rx32++#s4:1)=Nt8.new
496*9880d681SAndroid Build Coastguard Worker     case S4_storerh_ap:           // memh(Re32=#U6)=Rt32
497*9880d681SAndroid Build Coastguard Worker     case S4_storerhnew_ap:        // memh(Re32=#U6)=Nt8.new
498*9880d681SAndroid Build Coastguard Worker     case S2_storerh_pr:           // memh(Rx32++Mu2)=Rt32
499*9880d681SAndroid Build Coastguard Worker     case S2_storerhnew_pr:        // memh(Rx32++Mu2)=Nt8.new
500*9880d681SAndroid Build Coastguard Worker     case S4_storerh_ur:           // memh(Ru32<<#u2+#U6)=Rt32
501*9880d681SAndroid Build Coastguard Worker     case S4_storerhnew_ur:        // memh(Ru32<<#u2+#U6)=Nt8.new
502*9880d681SAndroid Build Coastguard Worker     case S2_storerh_pbr:          // memh(Rx32++Mu2:brev)=Rt32
503*9880d681SAndroid Build Coastguard Worker     case S2_storerhnew_pbr:       // memh(Rx32++Mu2:brev)=Nt8.new
504*9880d681SAndroid Build Coastguard Worker     case S2_storerh_pci:          // memh(Rx32++#s4:1:circ(Mu2))=Rt32
505*9880d681SAndroid Build Coastguard Worker     case S2_storerhnew_pci:       // memh(Rx32++#s4:1:circ(Mu2))=Nt8.new
506*9880d681SAndroid Build Coastguard Worker     case S2_storerh_pcr:          // memh(Rx32++I:circ(Mu2))=Rt32
507*9880d681SAndroid Build Coastguard Worker     case S2_storerhnew_pcr:       // memh(Rx32++I:circ(Mu2))=Nt8.new
508*9880d681SAndroid Build Coastguard Worker     case S4_storerh_rr:           // memh(Rs32+Ru32<<#u2)=Rt32
509*9880d681SAndroid Build Coastguard Worker     case S4_pstorerht_rr:         // if (Pv4) memh(Rs32+Ru32<<#u2)=Rt32
510*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhf_rr:         // if (!Pv4) memh(Rs32+Ru32<<#u2)=Rt32
511*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhtnew_rr:      // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Rt32
512*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhfnew_rr:      // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Rt32
513*9880d681SAndroid Build Coastguard Worker     case S4_storerhnew_rr:        // memh(Rs32+Ru32<<#u2)=Nt8.new
514*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhnewt_rr:      // if (Pv4) memh(Rs32+Ru32<<#u2)=Nt8.new
515*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhnewf_rr:      // if (!Pv4) memh(Rs32+Ru32<<#u2)=Nt8.new
516*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhnewtnew_rr:   // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Nt8.new
517*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhnewfnew_rr:   // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Nt8.new
518*9880d681SAndroid Build Coastguard Worker     case S2_storerhgp:            // memh(gp+#u16:1)=Rt32
519*9880d681SAndroid Build Coastguard Worker     case S2_storerhnewgp:         // memh(gp+#u16:1)=Nt8.new
520*9880d681SAndroid Build Coastguard Worker     case S4_pstorerht_abs:        // if (Pv4) memh(#u6)=Rt32
521*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhf_abs:        // if (!Pv4) memh(#u6)=Rt32
522*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhtnew_abs:     // if (Pv4.new) memh(#u6)=Rt32
523*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhfnew_abs:     // if (!Pv4.new) memh(#u6)=Rt32
524*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhnewt_abs:     // if (Pv4) memh(#u6)=Nt8.new
525*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhnewf_abs:     // if (!Pv4) memh(#u6)=Nt8.new
526*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhnewtnew_abs:  // if (Pv4.new) memh(#u6)=Nt8.new
527*9880d681SAndroid Build Coastguard Worker     case S4_pstorerhnewfnew_abs:  // if (!Pv4.new) memh(#u6)=Nt8.new
528*9880d681SAndroid Build Coastguard Worker       Bits.set(Begin, Begin+16);
529*9880d681SAndroid Build Coastguard Worker       return true;
530*9880d681SAndroid Build Coastguard Worker 
531*9880d681SAndroid Build Coastguard Worker     // Store high half
532*9880d681SAndroid Build Coastguard Worker     case S2_storerf_io:           // memh(Rs32+#s11:1)=Rt.H32
533*9880d681SAndroid Build Coastguard Worker     case S2_pstorerft_io:         // if (Pv4) memh(Rs32+#u6:1)=Rt.H32
534*9880d681SAndroid Build Coastguard Worker     case S2_pstorerff_io:         // if (!Pv4) memh(Rs32+#u6:1)=Rt.H32
535*9880d681SAndroid Build Coastguard Worker     case S4_pstorerftnew_io:      // if (Pv4.new) memh(Rs32+#u6:1)=Rt.H32
536*9880d681SAndroid Build Coastguard Worker     case S4_pstorerffnew_io:      // if (!Pv4.new) memh(Rs32+#u6:1)=Rt.H32
537*9880d681SAndroid Build Coastguard Worker     case S2_storerf_pi:           // memh(Rx32++#s4:1)=Rt.H32
538*9880d681SAndroid Build Coastguard Worker     case S2_pstorerft_pi:         // if (Pv4) memh(Rx32++#s4:1)=Rt.H32
539*9880d681SAndroid Build Coastguard Worker     case S2_pstorerff_pi:         // if (!Pv4) memh(Rx32++#s4:1)=Rt.H32
540*9880d681SAndroid Build Coastguard Worker     case S2_pstorerftnew_pi:      // if (Pv4.new) memh(Rx32++#s4:1)=Rt.H32
541*9880d681SAndroid Build Coastguard Worker     case S2_pstorerffnew_pi:      // if (!Pv4.new) memh(Rx32++#s4:1)=Rt.H32
542*9880d681SAndroid Build Coastguard Worker     case S4_storerf_ap:           // memh(Re32=#U6)=Rt.H32
543*9880d681SAndroid Build Coastguard Worker     case S2_storerf_pr:           // memh(Rx32++Mu2)=Rt.H32
544*9880d681SAndroid Build Coastguard Worker     case S4_storerf_ur:           // memh(Ru32<<#u2+#U6)=Rt.H32
545*9880d681SAndroid Build Coastguard Worker     case S2_storerf_pbr:          // memh(Rx32++Mu2:brev)=Rt.H32
546*9880d681SAndroid Build Coastguard Worker     case S2_storerf_pci:          // memh(Rx32++#s4:1:circ(Mu2))=Rt.H32
547*9880d681SAndroid Build Coastguard Worker     case S2_storerf_pcr:          // memh(Rx32++I:circ(Mu2))=Rt.H32
548*9880d681SAndroid Build Coastguard Worker     case S4_storerf_rr:           // memh(Rs32+Ru32<<#u2)=Rt.H32
549*9880d681SAndroid Build Coastguard Worker     case S4_pstorerft_rr:         // if (Pv4) memh(Rs32+Ru32<<#u2)=Rt.H32
550*9880d681SAndroid Build Coastguard Worker     case S4_pstorerff_rr:         // if (!Pv4) memh(Rs32+Ru32<<#u2)=Rt.H32
551*9880d681SAndroid Build Coastguard Worker     case S4_pstorerftnew_rr:      // if (Pv4.new) memh(Rs32+Ru32<<#u2)=Rt.H32
552*9880d681SAndroid Build Coastguard Worker     case S4_pstorerffnew_rr:      // if (!Pv4.new) memh(Rs32+Ru32<<#u2)=Rt.H32
553*9880d681SAndroid Build Coastguard Worker     case S2_storerfgp:            // memh(gp+#u16:1)=Rt.H32
554*9880d681SAndroid Build Coastguard Worker     case S4_pstorerft_abs:        // if (Pv4) memh(#u6)=Rt.H32
555*9880d681SAndroid Build Coastguard Worker     case S4_pstorerff_abs:        // if (!Pv4) memh(#u6)=Rt.H32
556*9880d681SAndroid Build Coastguard Worker     case S4_pstorerftnew_abs:     // if (Pv4.new) memh(#u6)=Rt.H32
557*9880d681SAndroid Build Coastguard Worker     case S4_pstorerffnew_abs:     // if (!Pv4.new) memh(#u6)=Rt.H32
558*9880d681SAndroid Build Coastguard Worker       Bits.set(Begin+16, Begin+32);
559*9880d681SAndroid Build Coastguard Worker       return true;
560*9880d681SAndroid Build Coastguard Worker   }
561*9880d681SAndroid Build Coastguard Worker 
562*9880d681SAndroid Build Coastguard Worker   return false;
563*9880d681SAndroid Build Coastguard Worker }
564*9880d681SAndroid Build Coastguard Worker 
565*9880d681SAndroid Build Coastguard Worker 
566*9880d681SAndroid Build Coastguard Worker // For an instruction with opcode Opc, calculate the set of bits that it
567*9880d681SAndroid Build Coastguard Worker // uses in a register in operand OpN. This only calculates the set of used
568*9880d681SAndroid Build Coastguard Worker // bits for cases where it does not depend on any operands (as is the case
569*9880d681SAndroid Build Coastguard Worker // in shifts, for example). For concrete instructions from a program, the
570*9880d681SAndroid Build Coastguard Worker // operand may be a subregister of a larger register, while Bits would
571*9880d681SAndroid Build Coastguard Worker // correspond to the larger register in its entirety. Because of that,
572*9880d681SAndroid Build Coastguard Worker // the parameter Begin can be used to indicate which bit of Bits should be
573*9880d681SAndroid Build Coastguard Worker // considered the LSB of of the operand.
getUsedBits(unsigned Opc,unsigned OpN,BitVector & Bits,uint16_t Begin,const HexagonInstrInfo & HII)574*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::getUsedBits(unsigned Opc, unsigned OpN,
575*9880d681SAndroid Build Coastguard Worker       BitVector &Bits, uint16_t Begin, const HexagonInstrInfo &HII) {
576*9880d681SAndroid Build Coastguard Worker   using namespace Hexagon;
577*9880d681SAndroid Build Coastguard Worker 
578*9880d681SAndroid Build Coastguard Worker   const MCInstrDesc &D = HII.get(Opc);
579*9880d681SAndroid Build Coastguard Worker   if (D.mayStore()) {
580*9880d681SAndroid Build Coastguard Worker     if (OpN == D.getNumOperands()-1)
581*9880d681SAndroid Build Coastguard Worker       return getUsedBitsInStore(Opc, Bits, Begin);
582*9880d681SAndroid Build Coastguard Worker     return false;
583*9880d681SAndroid Build Coastguard Worker   }
584*9880d681SAndroid Build Coastguard Worker 
585*9880d681SAndroid Build Coastguard Worker   switch (Opc) {
586*9880d681SAndroid Build Coastguard Worker     // One register source. Used bits: R1[0-7].
587*9880d681SAndroid Build Coastguard Worker     case A2_sxtb:
588*9880d681SAndroid Build Coastguard Worker     case A2_zxtb:
589*9880d681SAndroid Build Coastguard Worker     case A4_cmpbeqi:
590*9880d681SAndroid Build Coastguard Worker     case A4_cmpbgti:
591*9880d681SAndroid Build Coastguard Worker     case A4_cmpbgtui:
592*9880d681SAndroid Build Coastguard Worker       if (OpN == 1) {
593*9880d681SAndroid Build Coastguard Worker         Bits.set(Begin, Begin+8);
594*9880d681SAndroid Build Coastguard Worker         return true;
595*9880d681SAndroid Build Coastguard Worker       }
596*9880d681SAndroid Build Coastguard Worker       break;
597*9880d681SAndroid Build Coastguard Worker 
598*9880d681SAndroid Build Coastguard Worker     // One register source. Used bits: R1[0-15].
599*9880d681SAndroid Build Coastguard Worker     case A2_aslh:
600*9880d681SAndroid Build Coastguard Worker     case A2_sxth:
601*9880d681SAndroid Build Coastguard Worker     case A2_zxth:
602*9880d681SAndroid Build Coastguard Worker     case A4_cmpheqi:
603*9880d681SAndroid Build Coastguard Worker     case A4_cmphgti:
604*9880d681SAndroid Build Coastguard Worker     case A4_cmphgtui:
605*9880d681SAndroid Build Coastguard Worker       if (OpN == 1) {
606*9880d681SAndroid Build Coastguard Worker         Bits.set(Begin, Begin+16);
607*9880d681SAndroid Build Coastguard Worker         return true;
608*9880d681SAndroid Build Coastguard Worker       }
609*9880d681SAndroid Build Coastguard Worker       break;
610*9880d681SAndroid Build Coastguard Worker 
611*9880d681SAndroid Build Coastguard Worker     // One register source. Used bits: R1[16-31].
612*9880d681SAndroid Build Coastguard Worker     case A2_asrh:
613*9880d681SAndroid Build Coastguard Worker       if (OpN == 1) {
614*9880d681SAndroid Build Coastguard Worker         Bits.set(Begin+16, Begin+32);
615*9880d681SAndroid Build Coastguard Worker         return true;
616*9880d681SAndroid Build Coastguard Worker       }
617*9880d681SAndroid Build Coastguard Worker       break;
618*9880d681SAndroid Build Coastguard Worker 
619*9880d681SAndroid Build Coastguard Worker     // Two register sources. Used bits: R1[0-7], R2[0-7].
620*9880d681SAndroid Build Coastguard Worker     case A4_cmpbeq:
621*9880d681SAndroid Build Coastguard Worker     case A4_cmpbgt:
622*9880d681SAndroid Build Coastguard Worker     case A4_cmpbgtu:
623*9880d681SAndroid Build Coastguard Worker       if (OpN == 1) {
624*9880d681SAndroid Build Coastguard Worker         Bits.set(Begin, Begin+8);
625*9880d681SAndroid Build Coastguard Worker         return true;
626*9880d681SAndroid Build Coastguard Worker       }
627*9880d681SAndroid Build Coastguard Worker       break;
628*9880d681SAndroid Build Coastguard Worker 
629*9880d681SAndroid Build Coastguard Worker     // Two register sources. Used bits: R1[0-15], R2[0-15].
630*9880d681SAndroid Build Coastguard Worker     case A4_cmpheq:
631*9880d681SAndroid Build Coastguard Worker     case A4_cmphgt:
632*9880d681SAndroid Build Coastguard Worker     case A4_cmphgtu:
633*9880d681SAndroid Build Coastguard Worker     case A2_addh_h16_ll:
634*9880d681SAndroid Build Coastguard Worker     case A2_addh_h16_sat_ll:
635*9880d681SAndroid Build Coastguard Worker     case A2_addh_l16_ll:
636*9880d681SAndroid Build Coastguard Worker     case A2_addh_l16_sat_ll:
637*9880d681SAndroid Build Coastguard Worker     case A2_combine_ll:
638*9880d681SAndroid Build Coastguard Worker     case A2_subh_h16_ll:
639*9880d681SAndroid Build Coastguard Worker     case A2_subh_h16_sat_ll:
640*9880d681SAndroid Build Coastguard Worker     case A2_subh_l16_ll:
641*9880d681SAndroid Build Coastguard Worker     case A2_subh_l16_sat_ll:
642*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_ll_s0:
643*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_ll_s1:
644*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_sat_ll_s0:
645*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_sat_ll_s1:
646*9880d681SAndroid Build Coastguard Worker     case M2_mpy_ll_s0:
647*9880d681SAndroid Build Coastguard Worker     case M2_mpy_ll_s1:
648*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_ll_s0:
649*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_ll_s1:
650*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_sat_ll_s0:
651*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_sat_ll_s1:
652*9880d681SAndroid Build Coastguard Worker     case M2_mpy_rnd_ll_s0:
653*9880d681SAndroid Build Coastguard Worker     case M2_mpy_rnd_ll_s1:
654*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_ll_s0:
655*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_ll_s1:
656*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_rnd_ll_s0:
657*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_rnd_ll_s1:
658*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_acc_ll_s0:
659*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_acc_ll_s1:
660*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_ll_s0:
661*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_ll_s1:
662*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_nac_ll_s0:
663*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_nac_ll_s1:
664*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_rnd_ll_s0:
665*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_rnd_ll_s1:
666*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_acc_ll_s0:
667*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_acc_ll_s1:
668*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_ll_s0:
669*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_ll_s1:
670*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_nac_ll_s0:
671*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_nac_ll_s1:
672*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_acc_ll_s0:
673*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_acc_ll_s1:
674*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_ll_s0:
675*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_ll_s1:
676*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_nac_ll_s0:
677*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_nac_ll_s1:
678*9880d681SAndroid Build Coastguard Worker       if (OpN == 1 || OpN == 2) {
679*9880d681SAndroid Build Coastguard Worker         Bits.set(Begin, Begin+16);
680*9880d681SAndroid Build Coastguard Worker         return true;
681*9880d681SAndroid Build Coastguard Worker       }
682*9880d681SAndroid Build Coastguard Worker       break;
683*9880d681SAndroid Build Coastguard Worker 
684*9880d681SAndroid Build Coastguard Worker     // Two register sources. Used bits: R1[0-15], R2[16-31].
685*9880d681SAndroid Build Coastguard Worker     case A2_addh_h16_lh:
686*9880d681SAndroid Build Coastguard Worker     case A2_addh_h16_sat_lh:
687*9880d681SAndroid Build Coastguard Worker     case A2_combine_lh:
688*9880d681SAndroid Build Coastguard Worker     case A2_subh_h16_lh:
689*9880d681SAndroid Build Coastguard Worker     case A2_subh_h16_sat_lh:
690*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_lh_s0:
691*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_lh_s1:
692*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_sat_lh_s0:
693*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_sat_lh_s1:
694*9880d681SAndroid Build Coastguard Worker     case M2_mpy_lh_s0:
695*9880d681SAndroid Build Coastguard Worker     case M2_mpy_lh_s1:
696*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_lh_s0:
697*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_lh_s1:
698*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_sat_lh_s0:
699*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_sat_lh_s1:
700*9880d681SAndroid Build Coastguard Worker     case M2_mpy_rnd_lh_s0:
701*9880d681SAndroid Build Coastguard Worker     case M2_mpy_rnd_lh_s1:
702*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_lh_s0:
703*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_lh_s1:
704*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_rnd_lh_s0:
705*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_rnd_lh_s1:
706*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_acc_lh_s0:
707*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_acc_lh_s1:
708*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_lh_s0:
709*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_lh_s1:
710*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_nac_lh_s0:
711*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_nac_lh_s1:
712*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_rnd_lh_s0:
713*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_rnd_lh_s1:
714*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_acc_lh_s0:
715*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_acc_lh_s1:
716*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_lh_s0:
717*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_lh_s1:
718*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_nac_lh_s0:
719*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_nac_lh_s1:
720*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_acc_lh_s0:
721*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_acc_lh_s1:
722*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_lh_s0:
723*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_lh_s1:
724*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_nac_lh_s0:
725*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_nac_lh_s1:
726*9880d681SAndroid Build Coastguard Worker     // These four are actually LH.
727*9880d681SAndroid Build Coastguard Worker     case A2_addh_l16_hl:
728*9880d681SAndroid Build Coastguard Worker     case A2_addh_l16_sat_hl:
729*9880d681SAndroid Build Coastguard Worker     case A2_subh_l16_hl:
730*9880d681SAndroid Build Coastguard Worker     case A2_subh_l16_sat_hl:
731*9880d681SAndroid Build Coastguard Worker       if (OpN == 1) {
732*9880d681SAndroid Build Coastguard Worker         Bits.set(Begin, Begin+16);
733*9880d681SAndroid Build Coastguard Worker         return true;
734*9880d681SAndroid Build Coastguard Worker       }
735*9880d681SAndroid Build Coastguard Worker       if (OpN == 2) {
736*9880d681SAndroid Build Coastguard Worker         Bits.set(Begin+16, Begin+32);
737*9880d681SAndroid Build Coastguard Worker         return true;
738*9880d681SAndroid Build Coastguard Worker       }
739*9880d681SAndroid Build Coastguard Worker       break;
740*9880d681SAndroid Build Coastguard Worker 
741*9880d681SAndroid Build Coastguard Worker     // Two register sources, used bits: R1[16-31], R2[0-15].
742*9880d681SAndroid Build Coastguard Worker     case A2_addh_h16_hl:
743*9880d681SAndroid Build Coastguard Worker     case A2_addh_h16_sat_hl:
744*9880d681SAndroid Build Coastguard Worker     case A2_combine_hl:
745*9880d681SAndroid Build Coastguard Worker     case A2_subh_h16_hl:
746*9880d681SAndroid Build Coastguard Worker     case A2_subh_h16_sat_hl:
747*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_hl_s0:
748*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_hl_s1:
749*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_sat_hl_s0:
750*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_sat_hl_s1:
751*9880d681SAndroid Build Coastguard Worker     case M2_mpy_hl_s0:
752*9880d681SAndroid Build Coastguard Worker     case M2_mpy_hl_s1:
753*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_hl_s0:
754*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_hl_s1:
755*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_sat_hl_s0:
756*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_sat_hl_s1:
757*9880d681SAndroid Build Coastguard Worker     case M2_mpy_rnd_hl_s0:
758*9880d681SAndroid Build Coastguard Worker     case M2_mpy_rnd_hl_s1:
759*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_hl_s0:
760*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_hl_s1:
761*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_rnd_hl_s0:
762*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_rnd_hl_s1:
763*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_acc_hl_s0:
764*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_acc_hl_s1:
765*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_hl_s0:
766*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_hl_s1:
767*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_nac_hl_s0:
768*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_nac_hl_s1:
769*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_rnd_hl_s0:
770*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_rnd_hl_s1:
771*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_acc_hl_s0:
772*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_acc_hl_s1:
773*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_hl_s0:
774*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_hl_s1:
775*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_nac_hl_s0:
776*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_nac_hl_s1:
777*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_acc_hl_s0:
778*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_acc_hl_s1:
779*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_hl_s0:
780*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_hl_s1:
781*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_nac_hl_s0:
782*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_nac_hl_s1:
783*9880d681SAndroid Build Coastguard Worker       if (OpN == 1) {
784*9880d681SAndroid Build Coastguard Worker         Bits.set(Begin+16, Begin+32);
785*9880d681SAndroid Build Coastguard Worker         return true;
786*9880d681SAndroid Build Coastguard Worker       }
787*9880d681SAndroid Build Coastguard Worker       if (OpN == 2) {
788*9880d681SAndroid Build Coastguard Worker         Bits.set(Begin, Begin+16);
789*9880d681SAndroid Build Coastguard Worker         return true;
790*9880d681SAndroid Build Coastguard Worker       }
791*9880d681SAndroid Build Coastguard Worker       break;
792*9880d681SAndroid Build Coastguard Worker 
793*9880d681SAndroid Build Coastguard Worker     // Two register sources, used bits: R1[16-31], R2[16-31].
794*9880d681SAndroid Build Coastguard Worker     case A2_addh_h16_hh:
795*9880d681SAndroid Build Coastguard Worker     case A2_addh_h16_sat_hh:
796*9880d681SAndroid Build Coastguard Worker     case A2_combine_hh:
797*9880d681SAndroid Build Coastguard Worker     case A2_subh_h16_hh:
798*9880d681SAndroid Build Coastguard Worker     case A2_subh_h16_sat_hh:
799*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_hh_s0:
800*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_hh_s1:
801*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_sat_hh_s0:
802*9880d681SAndroid Build Coastguard Worker     case M2_mpy_acc_sat_hh_s1:
803*9880d681SAndroid Build Coastguard Worker     case M2_mpy_hh_s0:
804*9880d681SAndroid Build Coastguard Worker     case M2_mpy_hh_s1:
805*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_hh_s0:
806*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_hh_s1:
807*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_sat_hh_s0:
808*9880d681SAndroid Build Coastguard Worker     case M2_mpy_nac_sat_hh_s1:
809*9880d681SAndroid Build Coastguard Worker     case M2_mpy_rnd_hh_s0:
810*9880d681SAndroid Build Coastguard Worker     case M2_mpy_rnd_hh_s1:
811*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_hh_s0:
812*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_hh_s1:
813*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_rnd_hh_s0:
814*9880d681SAndroid Build Coastguard Worker     case M2_mpy_sat_rnd_hh_s1:
815*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_acc_hh_s0:
816*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_acc_hh_s1:
817*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_hh_s0:
818*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_hh_s1:
819*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_nac_hh_s0:
820*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_nac_hh_s1:
821*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_rnd_hh_s0:
822*9880d681SAndroid Build Coastguard Worker     case M2_mpyd_rnd_hh_s1:
823*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_acc_hh_s0:
824*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_acc_hh_s1:
825*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_hh_s0:
826*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_hh_s1:
827*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_nac_hh_s0:
828*9880d681SAndroid Build Coastguard Worker     case M2_mpyu_nac_hh_s1:
829*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_acc_hh_s0:
830*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_acc_hh_s1:
831*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_hh_s0:
832*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_hh_s1:
833*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_nac_hh_s0:
834*9880d681SAndroid Build Coastguard Worker     case M2_mpyud_nac_hh_s1:
835*9880d681SAndroid Build Coastguard Worker       if (OpN == 1 || OpN == 2) {
836*9880d681SAndroid Build Coastguard Worker         Bits.set(Begin+16, Begin+32);
837*9880d681SAndroid Build Coastguard Worker         return true;
838*9880d681SAndroid Build Coastguard Worker       }
839*9880d681SAndroid Build Coastguard Worker       break;
840*9880d681SAndroid Build Coastguard Worker   }
841*9880d681SAndroid Build Coastguard Worker 
842*9880d681SAndroid Build Coastguard Worker   return false;
843*9880d681SAndroid Build Coastguard Worker }
844*9880d681SAndroid Build Coastguard Worker 
845*9880d681SAndroid Build Coastguard Worker 
846*9880d681SAndroid Build Coastguard Worker // Calculate the register class that matches Reg:Sub. For example, if
847*9880d681SAndroid Build Coastguard Worker // vreg1 is a double register, then vreg1:subreg_hireg would match "int"
848*9880d681SAndroid Build Coastguard Worker // register class.
getFinalVRegClass(const BitTracker::RegisterRef & RR,MachineRegisterInfo & MRI)849*9880d681SAndroid Build Coastguard Worker const TargetRegisterClass *HexagonBitSimplify::getFinalVRegClass(
850*9880d681SAndroid Build Coastguard Worker       const BitTracker::RegisterRef &RR, MachineRegisterInfo &MRI) {
851*9880d681SAndroid Build Coastguard Worker   if (!TargetRegisterInfo::isVirtualRegister(RR.Reg))
852*9880d681SAndroid Build Coastguard Worker     return nullptr;
853*9880d681SAndroid Build Coastguard Worker   auto *RC = MRI.getRegClass(RR.Reg);
854*9880d681SAndroid Build Coastguard Worker   if (RR.Sub == 0)
855*9880d681SAndroid Build Coastguard Worker     return RC;
856*9880d681SAndroid Build Coastguard Worker 
857*9880d681SAndroid Build Coastguard Worker   auto VerifySR = [] (unsigned Sub) -> void {
858*9880d681SAndroid Build Coastguard Worker     assert(Sub == Hexagon::subreg_hireg || Sub == Hexagon::subreg_loreg);
859*9880d681SAndroid Build Coastguard Worker   };
860*9880d681SAndroid Build Coastguard Worker 
861*9880d681SAndroid Build Coastguard Worker   switch (RC->getID()) {
862*9880d681SAndroid Build Coastguard Worker     case Hexagon::DoubleRegsRegClassID:
863*9880d681SAndroid Build Coastguard Worker       VerifySR(RR.Sub);
864*9880d681SAndroid Build Coastguard Worker       return &Hexagon::IntRegsRegClass;
865*9880d681SAndroid Build Coastguard Worker     case Hexagon::VecDblRegsRegClassID:
866*9880d681SAndroid Build Coastguard Worker       VerifySR(RR.Sub);
867*9880d681SAndroid Build Coastguard Worker       return &Hexagon::VectorRegsRegClass;
868*9880d681SAndroid Build Coastguard Worker     case Hexagon::VecDblRegs128BRegClassID:
869*9880d681SAndroid Build Coastguard Worker       VerifySR(RR.Sub);
870*9880d681SAndroid Build Coastguard Worker       return &Hexagon::VectorRegs128BRegClass;
871*9880d681SAndroid Build Coastguard Worker   }
872*9880d681SAndroid Build Coastguard Worker   return nullptr;
873*9880d681SAndroid Build Coastguard Worker }
874*9880d681SAndroid Build Coastguard Worker 
875*9880d681SAndroid Build Coastguard Worker 
876*9880d681SAndroid Build Coastguard Worker // Check if RD could be replaced with RS at any possible use of RD.
877*9880d681SAndroid Build Coastguard Worker // For example a predicate register cannot be replaced with a integer
878*9880d681SAndroid Build Coastguard Worker // register, but a 64-bit register with a subregister can be replaced
879*9880d681SAndroid Build Coastguard Worker // with a 32-bit register.
isTransparentCopy(const BitTracker::RegisterRef & RD,const BitTracker::RegisterRef & RS,MachineRegisterInfo & MRI)880*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::isTransparentCopy(const BitTracker::RegisterRef &RD,
881*9880d681SAndroid Build Coastguard Worker       const BitTracker::RegisterRef &RS, MachineRegisterInfo &MRI) {
882*9880d681SAndroid Build Coastguard Worker   if (!TargetRegisterInfo::isVirtualRegister(RD.Reg) ||
883*9880d681SAndroid Build Coastguard Worker       !TargetRegisterInfo::isVirtualRegister(RS.Reg))
884*9880d681SAndroid Build Coastguard Worker     return false;
885*9880d681SAndroid Build Coastguard Worker   // Return false if one (or both) classes are nullptr.
886*9880d681SAndroid Build Coastguard Worker   auto *DRC = getFinalVRegClass(RD, MRI);
887*9880d681SAndroid Build Coastguard Worker   if (!DRC)
888*9880d681SAndroid Build Coastguard Worker     return false;
889*9880d681SAndroid Build Coastguard Worker 
890*9880d681SAndroid Build Coastguard Worker   return DRC == getFinalVRegClass(RS, MRI);
891*9880d681SAndroid Build Coastguard Worker }
892*9880d681SAndroid Build Coastguard Worker 
893*9880d681SAndroid Build Coastguard Worker 
894*9880d681SAndroid Build Coastguard Worker //
895*9880d681SAndroid Build Coastguard Worker // Dead code elimination
896*9880d681SAndroid Build Coastguard Worker //
897*9880d681SAndroid Build Coastguard Worker namespace {
898*9880d681SAndroid Build Coastguard Worker   class DeadCodeElimination {
899*9880d681SAndroid Build Coastguard Worker   public:
DeadCodeElimination(MachineFunction & mf,MachineDominatorTree & mdt)900*9880d681SAndroid Build Coastguard Worker     DeadCodeElimination(MachineFunction &mf, MachineDominatorTree &mdt)
901*9880d681SAndroid Build Coastguard Worker       : MF(mf), HII(*MF.getSubtarget<HexagonSubtarget>().getInstrInfo()),
902*9880d681SAndroid Build Coastguard Worker         MDT(mdt), MRI(mf.getRegInfo()) {}
903*9880d681SAndroid Build Coastguard Worker 
run()904*9880d681SAndroid Build Coastguard Worker     bool run() {
905*9880d681SAndroid Build Coastguard Worker       return runOnNode(MDT.getRootNode());
906*9880d681SAndroid Build Coastguard Worker     }
907*9880d681SAndroid Build Coastguard Worker 
908*9880d681SAndroid Build Coastguard Worker   private:
909*9880d681SAndroid Build Coastguard Worker     bool isDead(unsigned R) const;
910*9880d681SAndroid Build Coastguard Worker     bool runOnNode(MachineDomTreeNode *N);
911*9880d681SAndroid Build Coastguard Worker 
912*9880d681SAndroid Build Coastguard Worker     MachineFunction &MF;
913*9880d681SAndroid Build Coastguard Worker     const HexagonInstrInfo &HII;
914*9880d681SAndroid Build Coastguard Worker     MachineDominatorTree &MDT;
915*9880d681SAndroid Build Coastguard Worker     MachineRegisterInfo &MRI;
916*9880d681SAndroid Build Coastguard Worker   };
917*9880d681SAndroid Build Coastguard Worker }
918*9880d681SAndroid Build Coastguard Worker 
919*9880d681SAndroid Build Coastguard Worker 
isDead(unsigned R) const920*9880d681SAndroid Build Coastguard Worker bool DeadCodeElimination::isDead(unsigned R) const {
921*9880d681SAndroid Build Coastguard Worker   for (auto I = MRI.use_begin(R), E = MRI.use_end(); I != E; ++I) {
922*9880d681SAndroid Build Coastguard Worker     MachineInstr *UseI = I->getParent();
923*9880d681SAndroid Build Coastguard Worker     if (UseI->isDebugValue())
924*9880d681SAndroid Build Coastguard Worker       continue;
925*9880d681SAndroid Build Coastguard Worker     if (UseI->isPHI()) {
926*9880d681SAndroid Build Coastguard Worker       assert(!UseI->getOperand(0).getSubReg());
927*9880d681SAndroid Build Coastguard Worker       unsigned DR = UseI->getOperand(0).getReg();
928*9880d681SAndroid Build Coastguard Worker       if (DR == R)
929*9880d681SAndroid Build Coastguard Worker         continue;
930*9880d681SAndroid Build Coastguard Worker     }
931*9880d681SAndroid Build Coastguard Worker     return false;
932*9880d681SAndroid Build Coastguard Worker   }
933*9880d681SAndroid Build Coastguard Worker   return true;
934*9880d681SAndroid Build Coastguard Worker }
935*9880d681SAndroid Build Coastguard Worker 
936*9880d681SAndroid Build Coastguard Worker 
runOnNode(MachineDomTreeNode * N)937*9880d681SAndroid Build Coastguard Worker bool DeadCodeElimination::runOnNode(MachineDomTreeNode *N) {
938*9880d681SAndroid Build Coastguard Worker   bool Changed = false;
939*9880d681SAndroid Build Coastguard Worker   typedef GraphTraits<MachineDomTreeNode*> GTN;
940*9880d681SAndroid Build Coastguard Worker   for (auto I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I)
941*9880d681SAndroid Build Coastguard Worker     Changed |= runOnNode(*I);
942*9880d681SAndroid Build Coastguard Worker 
943*9880d681SAndroid Build Coastguard Worker   MachineBasicBlock *B = N->getBlock();
944*9880d681SAndroid Build Coastguard Worker   std::vector<MachineInstr*> Instrs;
945*9880d681SAndroid Build Coastguard Worker   for (auto I = B->rbegin(), E = B->rend(); I != E; ++I)
946*9880d681SAndroid Build Coastguard Worker     Instrs.push_back(&*I);
947*9880d681SAndroid Build Coastguard Worker 
948*9880d681SAndroid Build Coastguard Worker   for (auto MI : Instrs) {
949*9880d681SAndroid Build Coastguard Worker     unsigned Opc = MI->getOpcode();
950*9880d681SAndroid Build Coastguard Worker     // Do not touch lifetime markers. This is why the target-independent DCE
951*9880d681SAndroid Build Coastguard Worker     // cannot be used.
952*9880d681SAndroid Build Coastguard Worker     if (Opc == TargetOpcode::LIFETIME_START ||
953*9880d681SAndroid Build Coastguard Worker         Opc == TargetOpcode::LIFETIME_END)
954*9880d681SAndroid Build Coastguard Worker       continue;
955*9880d681SAndroid Build Coastguard Worker     bool Store = false;
956*9880d681SAndroid Build Coastguard Worker     if (MI->isInlineAsm())
957*9880d681SAndroid Build Coastguard Worker       continue;
958*9880d681SAndroid Build Coastguard Worker     // Delete PHIs if possible.
959*9880d681SAndroid Build Coastguard Worker     if (!MI->isPHI() && !MI->isSafeToMove(nullptr, Store))
960*9880d681SAndroid Build Coastguard Worker       continue;
961*9880d681SAndroid Build Coastguard Worker 
962*9880d681SAndroid Build Coastguard Worker     bool AllDead = true;
963*9880d681SAndroid Build Coastguard Worker     SmallVector<unsigned,2> Regs;
964*9880d681SAndroid Build Coastguard Worker     for (auto &Op : MI->operands()) {
965*9880d681SAndroid Build Coastguard Worker       if (!Op.isReg() || !Op.isDef())
966*9880d681SAndroid Build Coastguard Worker         continue;
967*9880d681SAndroid Build Coastguard Worker       unsigned R = Op.getReg();
968*9880d681SAndroid Build Coastguard Worker       if (!TargetRegisterInfo::isVirtualRegister(R) || !isDead(R)) {
969*9880d681SAndroid Build Coastguard Worker         AllDead = false;
970*9880d681SAndroid Build Coastguard Worker         break;
971*9880d681SAndroid Build Coastguard Worker       }
972*9880d681SAndroid Build Coastguard Worker       Regs.push_back(R);
973*9880d681SAndroid Build Coastguard Worker     }
974*9880d681SAndroid Build Coastguard Worker     if (!AllDead)
975*9880d681SAndroid Build Coastguard Worker       continue;
976*9880d681SAndroid Build Coastguard Worker 
977*9880d681SAndroid Build Coastguard Worker     B->erase(MI);
978*9880d681SAndroid Build Coastguard Worker     for (unsigned i = 0, n = Regs.size(); i != n; ++i)
979*9880d681SAndroid Build Coastguard Worker       MRI.markUsesInDebugValueAsUndef(Regs[i]);
980*9880d681SAndroid Build Coastguard Worker     Changed = true;
981*9880d681SAndroid Build Coastguard Worker   }
982*9880d681SAndroid Build Coastguard Worker 
983*9880d681SAndroid Build Coastguard Worker   return Changed;
984*9880d681SAndroid Build Coastguard Worker }
985*9880d681SAndroid Build Coastguard Worker 
986*9880d681SAndroid Build Coastguard Worker 
987*9880d681SAndroid Build Coastguard Worker //
988*9880d681SAndroid Build Coastguard Worker // Eliminate redundant instructions
989*9880d681SAndroid Build Coastguard Worker //
990*9880d681SAndroid Build Coastguard Worker // This transformation will identify instructions where the output register
991*9880d681SAndroid Build Coastguard Worker // is the same as one of its input registers. This only works on instructions
992*9880d681SAndroid Build Coastguard Worker // that define a single register (unlike post-increment loads, for example).
993*9880d681SAndroid Build Coastguard Worker // The equality check is actually more detailed: the code calculates which
994*9880d681SAndroid Build Coastguard Worker // bits of the output are used, and only compares these bits with the input
995*9880d681SAndroid Build Coastguard Worker // registers.
996*9880d681SAndroid Build Coastguard Worker // If the output matches an input, the instruction is replaced with COPY.
997*9880d681SAndroid Build Coastguard Worker // The copies will be removed by another transformation.
998*9880d681SAndroid Build Coastguard Worker namespace {
999*9880d681SAndroid Build Coastguard Worker   class RedundantInstrElimination : public Transformation {
1000*9880d681SAndroid Build Coastguard Worker   public:
RedundantInstrElimination(BitTracker & bt,const HexagonInstrInfo & hii,MachineRegisterInfo & mri)1001*9880d681SAndroid Build Coastguard Worker     RedundantInstrElimination(BitTracker &bt, const HexagonInstrInfo &hii,
1002*9880d681SAndroid Build Coastguard Worker           MachineRegisterInfo &mri)
1003*9880d681SAndroid Build Coastguard Worker         : Transformation(true), HII(hii), MRI(mri), BT(bt) {}
1004*9880d681SAndroid Build Coastguard Worker     bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1005*9880d681SAndroid Build Coastguard Worker   private:
1006*9880d681SAndroid Build Coastguard Worker     bool isLossyShiftLeft(const MachineInstr &MI, unsigned OpN,
1007*9880d681SAndroid Build Coastguard Worker           unsigned &LostB, unsigned &LostE);
1008*9880d681SAndroid Build Coastguard Worker     bool isLossyShiftRight(const MachineInstr &MI, unsigned OpN,
1009*9880d681SAndroid Build Coastguard Worker           unsigned &LostB, unsigned &LostE);
1010*9880d681SAndroid Build Coastguard Worker     bool computeUsedBits(unsigned Reg, BitVector &Bits);
1011*9880d681SAndroid Build Coastguard Worker     bool computeUsedBits(const MachineInstr &MI, unsigned OpN, BitVector &Bits,
1012*9880d681SAndroid Build Coastguard Worker           uint16_t Begin);
1013*9880d681SAndroid Build Coastguard Worker     bool usedBitsEqual(BitTracker::RegisterRef RD, BitTracker::RegisterRef RS);
1014*9880d681SAndroid Build Coastguard Worker 
1015*9880d681SAndroid Build Coastguard Worker     const HexagonInstrInfo &HII;
1016*9880d681SAndroid Build Coastguard Worker     MachineRegisterInfo &MRI;
1017*9880d681SAndroid Build Coastguard Worker     BitTracker &BT;
1018*9880d681SAndroid Build Coastguard Worker   };
1019*9880d681SAndroid Build Coastguard Worker }
1020*9880d681SAndroid Build Coastguard Worker 
1021*9880d681SAndroid Build Coastguard Worker 
1022*9880d681SAndroid Build Coastguard Worker // Check if the instruction is a lossy shift left, where the input being
1023*9880d681SAndroid Build Coastguard Worker // shifted is the operand OpN of MI. If true, [LostB, LostE) is the range
1024*9880d681SAndroid Build Coastguard Worker // of bit indices that are lost.
isLossyShiftLeft(const MachineInstr & MI,unsigned OpN,unsigned & LostB,unsigned & LostE)1025*9880d681SAndroid Build Coastguard Worker bool RedundantInstrElimination::isLossyShiftLeft(const MachineInstr &MI,
1026*9880d681SAndroid Build Coastguard Worker       unsigned OpN, unsigned &LostB, unsigned &LostE) {
1027*9880d681SAndroid Build Coastguard Worker   using namespace Hexagon;
1028*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI.getOpcode();
1029*9880d681SAndroid Build Coastguard Worker   unsigned ImN, RegN, Width;
1030*9880d681SAndroid Build Coastguard Worker   switch (Opc) {
1031*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_p:
1032*9880d681SAndroid Build Coastguard Worker       ImN = 2;
1033*9880d681SAndroid Build Coastguard Worker       RegN = 1;
1034*9880d681SAndroid Build Coastguard Worker       Width = 64;
1035*9880d681SAndroid Build Coastguard Worker       break;
1036*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_p_acc:
1037*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_p_and:
1038*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_p_nac:
1039*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_p_or:
1040*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_p_xacc:
1041*9880d681SAndroid Build Coastguard Worker       ImN = 3;
1042*9880d681SAndroid Build Coastguard Worker       RegN = 2;
1043*9880d681SAndroid Build Coastguard Worker       Width = 64;
1044*9880d681SAndroid Build Coastguard Worker       break;
1045*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_r:
1046*9880d681SAndroid Build Coastguard Worker       ImN = 2;
1047*9880d681SAndroid Build Coastguard Worker       RegN = 1;
1048*9880d681SAndroid Build Coastguard Worker       Width = 32;
1049*9880d681SAndroid Build Coastguard Worker       break;
1050*9880d681SAndroid Build Coastguard Worker     case S2_addasl_rrri:
1051*9880d681SAndroid Build Coastguard Worker     case S4_andi_asl_ri:
1052*9880d681SAndroid Build Coastguard Worker     case S4_ori_asl_ri:
1053*9880d681SAndroid Build Coastguard Worker     case S4_addi_asl_ri:
1054*9880d681SAndroid Build Coastguard Worker     case S4_subi_asl_ri:
1055*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_r_acc:
1056*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_r_and:
1057*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_r_nac:
1058*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_r_or:
1059*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_r_sat:
1060*9880d681SAndroid Build Coastguard Worker     case S2_asl_i_r_xacc:
1061*9880d681SAndroid Build Coastguard Worker       ImN = 3;
1062*9880d681SAndroid Build Coastguard Worker       RegN = 2;
1063*9880d681SAndroid Build Coastguard Worker       Width = 32;
1064*9880d681SAndroid Build Coastguard Worker       break;
1065*9880d681SAndroid Build Coastguard Worker     default:
1066*9880d681SAndroid Build Coastguard Worker       return false;
1067*9880d681SAndroid Build Coastguard Worker   }
1068*9880d681SAndroid Build Coastguard Worker 
1069*9880d681SAndroid Build Coastguard Worker   if (RegN != OpN)
1070*9880d681SAndroid Build Coastguard Worker     return false;
1071*9880d681SAndroid Build Coastguard Worker 
1072*9880d681SAndroid Build Coastguard Worker   assert(MI.getOperand(ImN).isImm());
1073*9880d681SAndroid Build Coastguard Worker   unsigned S = MI.getOperand(ImN).getImm();
1074*9880d681SAndroid Build Coastguard Worker   if (S == 0)
1075*9880d681SAndroid Build Coastguard Worker     return false;
1076*9880d681SAndroid Build Coastguard Worker   LostB = Width-S;
1077*9880d681SAndroid Build Coastguard Worker   LostE = Width;
1078*9880d681SAndroid Build Coastguard Worker   return true;
1079*9880d681SAndroid Build Coastguard Worker }
1080*9880d681SAndroid Build Coastguard Worker 
1081*9880d681SAndroid Build Coastguard Worker 
1082*9880d681SAndroid Build Coastguard Worker // Check if the instruction is a lossy shift right, where the input being
1083*9880d681SAndroid Build Coastguard Worker // shifted is the operand OpN of MI. If true, [LostB, LostE) is the range
1084*9880d681SAndroid Build Coastguard Worker // of bit indices that are lost.
isLossyShiftRight(const MachineInstr & MI,unsigned OpN,unsigned & LostB,unsigned & LostE)1085*9880d681SAndroid Build Coastguard Worker bool RedundantInstrElimination::isLossyShiftRight(const MachineInstr &MI,
1086*9880d681SAndroid Build Coastguard Worker       unsigned OpN, unsigned &LostB, unsigned &LostE) {
1087*9880d681SAndroid Build Coastguard Worker   using namespace Hexagon;
1088*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI.getOpcode();
1089*9880d681SAndroid Build Coastguard Worker   unsigned ImN, RegN;
1090*9880d681SAndroid Build Coastguard Worker   switch (Opc) {
1091*9880d681SAndroid Build Coastguard Worker     case S2_asr_i_p:
1092*9880d681SAndroid Build Coastguard Worker     case S2_lsr_i_p:
1093*9880d681SAndroid Build Coastguard Worker       ImN = 2;
1094*9880d681SAndroid Build Coastguard Worker       RegN = 1;
1095*9880d681SAndroid Build Coastguard Worker       break;
1096*9880d681SAndroid Build Coastguard Worker     case S2_asr_i_p_acc:
1097*9880d681SAndroid Build Coastguard Worker     case S2_asr_i_p_and:
1098*9880d681SAndroid Build Coastguard Worker     case S2_asr_i_p_nac:
1099*9880d681SAndroid Build Coastguard Worker     case S2_asr_i_p_or:
1100*9880d681SAndroid Build Coastguard Worker     case S2_lsr_i_p_acc:
1101*9880d681SAndroid Build Coastguard Worker     case S2_lsr_i_p_and:
1102*9880d681SAndroid Build Coastguard Worker     case S2_lsr_i_p_nac:
1103*9880d681SAndroid Build Coastguard Worker     case S2_lsr_i_p_or:
1104*9880d681SAndroid Build Coastguard Worker     case S2_lsr_i_p_xacc:
1105*9880d681SAndroid Build Coastguard Worker       ImN = 3;
1106*9880d681SAndroid Build Coastguard Worker       RegN = 2;
1107*9880d681SAndroid Build Coastguard Worker       break;
1108*9880d681SAndroid Build Coastguard Worker     case S2_asr_i_r:
1109*9880d681SAndroid Build Coastguard Worker     case S2_lsr_i_r:
1110*9880d681SAndroid Build Coastguard Worker       ImN = 2;
1111*9880d681SAndroid Build Coastguard Worker       RegN = 1;
1112*9880d681SAndroid Build Coastguard Worker       break;
1113*9880d681SAndroid Build Coastguard Worker     case S4_andi_lsr_ri:
1114*9880d681SAndroid Build Coastguard Worker     case S4_ori_lsr_ri:
1115*9880d681SAndroid Build Coastguard Worker     case S4_addi_lsr_ri:
1116*9880d681SAndroid Build Coastguard Worker     case S4_subi_lsr_ri:
1117*9880d681SAndroid Build Coastguard Worker     case S2_asr_i_r_acc:
1118*9880d681SAndroid Build Coastguard Worker     case S2_asr_i_r_and:
1119*9880d681SAndroid Build Coastguard Worker     case S2_asr_i_r_nac:
1120*9880d681SAndroid Build Coastguard Worker     case S2_asr_i_r_or:
1121*9880d681SAndroid Build Coastguard Worker     case S2_lsr_i_r_acc:
1122*9880d681SAndroid Build Coastguard Worker     case S2_lsr_i_r_and:
1123*9880d681SAndroid Build Coastguard Worker     case S2_lsr_i_r_nac:
1124*9880d681SAndroid Build Coastguard Worker     case S2_lsr_i_r_or:
1125*9880d681SAndroid Build Coastguard Worker     case S2_lsr_i_r_xacc:
1126*9880d681SAndroid Build Coastguard Worker       ImN = 3;
1127*9880d681SAndroid Build Coastguard Worker       RegN = 2;
1128*9880d681SAndroid Build Coastguard Worker       break;
1129*9880d681SAndroid Build Coastguard Worker 
1130*9880d681SAndroid Build Coastguard Worker     default:
1131*9880d681SAndroid Build Coastguard Worker       return false;
1132*9880d681SAndroid Build Coastguard Worker   }
1133*9880d681SAndroid Build Coastguard Worker 
1134*9880d681SAndroid Build Coastguard Worker   if (RegN != OpN)
1135*9880d681SAndroid Build Coastguard Worker     return false;
1136*9880d681SAndroid Build Coastguard Worker 
1137*9880d681SAndroid Build Coastguard Worker   assert(MI.getOperand(ImN).isImm());
1138*9880d681SAndroid Build Coastguard Worker   unsigned S = MI.getOperand(ImN).getImm();
1139*9880d681SAndroid Build Coastguard Worker   LostB = 0;
1140*9880d681SAndroid Build Coastguard Worker   LostE = S;
1141*9880d681SAndroid Build Coastguard Worker   return true;
1142*9880d681SAndroid Build Coastguard Worker }
1143*9880d681SAndroid Build Coastguard Worker 
1144*9880d681SAndroid Build Coastguard Worker 
1145*9880d681SAndroid Build Coastguard Worker // Calculate the bit vector that corresponds to the used bits of register Reg.
1146*9880d681SAndroid Build Coastguard Worker // The vector Bits has the same size, as the size of Reg in bits. If the cal-
1147*9880d681SAndroid Build Coastguard Worker // culation fails (i.e. the used bits are unknown), it returns false. Other-
1148*9880d681SAndroid Build Coastguard Worker // wise, it returns true and sets the corresponding bits in Bits.
computeUsedBits(unsigned Reg,BitVector & Bits)1149*9880d681SAndroid Build Coastguard Worker bool RedundantInstrElimination::computeUsedBits(unsigned Reg, BitVector &Bits) {
1150*9880d681SAndroid Build Coastguard Worker   BitVector Used(Bits.size());
1151*9880d681SAndroid Build Coastguard Worker   RegisterSet Visited;
1152*9880d681SAndroid Build Coastguard Worker   std::vector<unsigned> Pending;
1153*9880d681SAndroid Build Coastguard Worker   Pending.push_back(Reg);
1154*9880d681SAndroid Build Coastguard Worker 
1155*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 0; i < Pending.size(); ++i) {
1156*9880d681SAndroid Build Coastguard Worker     unsigned R = Pending[i];
1157*9880d681SAndroid Build Coastguard Worker     if (Visited.has(R))
1158*9880d681SAndroid Build Coastguard Worker       continue;
1159*9880d681SAndroid Build Coastguard Worker     Visited.insert(R);
1160*9880d681SAndroid Build Coastguard Worker     for (auto I = MRI.use_begin(R), E = MRI.use_end(); I != E; ++I) {
1161*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef UR = *I;
1162*9880d681SAndroid Build Coastguard Worker       unsigned B, W;
1163*9880d681SAndroid Build Coastguard Worker       if (!HBS::getSubregMask(UR, B, W, MRI))
1164*9880d681SAndroid Build Coastguard Worker         return false;
1165*9880d681SAndroid Build Coastguard Worker       MachineInstr &UseI = *I->getParent();
1166*9880d681SAndroid Build Coastguard Worker       if (UseI.isPHI() || UseI.isCopy()) {
1167*9880d681SAndroid Build Coastguard Worker         unsigned DefR = UseI.getOperand(0).getReg();
1168*9880d681SAndroid Build Coastguard Worker         if (!TargetRegisterInfo::isVirtualRegister(DefR))
1169*9880d681SAndroid Build Coastguard Worker           return false;
1170*9880d681SAndroid Build Coastguard Worker         Pending.push_back(DefR);
1171*9880d681SAndroid Build Coastguard Worker       } else {
1172*9880d681SAndroid Build Coastguard Worker         if (!computeUsedBits(UseI, I.getOperandNo(), Used, B))
1173*9880d681SAndroid Build Coastguard Worker           return false;
1174*9880d681SAndroid Build Coastguard Worker       }
1175*9880d681SAndroid Build Coastguard Worker     }
1176*9880d681SAndroid Build Coastguard Worker   }
1177*9880d681SAndroid Build Coastguard Worker   Bits |= Used;
1178*9880d681SAndroid Build Coastguard Worker   return true;
1179*9880d681SAndroid Build Coastguard Worker }
1180*9880d681SAndroid Build Coastguard Worker 
1181*9880d681SAndroid Build Coastguard Worker 
1182*9880d681SAndroid Build Coastguard Worker // Calculate the bits used by instruction MI in a register in operand OpN.
1183*9880d681SAndroid Build Coastguard Worker // Return true/false if the calculation succeeds/fails. If is succeeds, set
1184*9880d681SAndroid Build Coastguard Worker // used bits in Bits. This function does not reset any bits in Bits, so
1185*9880d681SAndroid Build Coastguard Worker // subsequent calls over different instructions will result in the union
1186*9880d681SAndroid Build Coastguard Worker // of the used bits in all these instructions.
1187*9880d681SAndroid Build Coastguard Worker // The register in question may be used with a sub-register, whereas Bits
1188*9880d681SAndroid Build Coastguard Worker // holds the bits for the entire register. To keep track of that, the
1189*9880d681SAndroid Build Coastguard Worker // argument Begin indicates where in Bits is the lowest-significant bit
1190*9880d681SAndroid Build Coastguard Worker // of the register used in operand OpN. For example, in instruction:
1191*9880d681SAndroid Build Coastguard Worker //   vreg1 = S2_lsr_i_r vreg2:subreg_hireg, 10
1192*9880d681SAndroid Build Coastguard Worker // the operand 1 is a 32-bit register, which happens to be a subregister
1193*9880d681SAndroid Build Coastguard Worker // of the 64-bit register vreg2, and that subregister starts at position 32.
1194*9880d681SAndroid Build Coastguard Worker // In this case Begin=32, since Bits[32] would be the lowest-significant bit
1195*9880d681SAndroid Build Coastguard Worker // of vreg2:subreg_hireg.
computeUsedBits(const MachineInstr & MI,unsigned OpN,BitVector & Bits,uint16_t Begin)1196*9880d681SAndroid Build Coastguard Worker bool RedundantInstrElimination::computeUsedBits(const MachineInstr &MI,
1197*9880d681SAndroid Build Coastguard Worker       unsigned OpN, BitVector &Bits, uint16_t Begin) {
1198*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI.getOpcode();
1199*9880d681SAndroid Build Coastguard Worker   BitVector T(Bits.size());
1200*9880d681SAndroid Build Coastguard Worker   bool GotBits = HBS::getUsedBits(Opc, OpN, T, Begin, HII);
1201*9880d681SAndroid Build Coastguard Worker   // Even if we don't have bits yet, we could still provide some information
1202*9880d681SAndroid Build Coastguard Worker   // if the instruction is a lossy shift: the lost bits will be marked as
1203*9880d681SAndroid Build Coastguard Worker   // not used.
1204*9880d681SAndroid Build Coastguard Worker   unsigned LB, LE;
1205*9880d681SAndroid Build Coastguard Worker   if (isLossyShiftLeft(MI, OpN, LB, LE) || isLossyShiftRight(MI, OpN, LB, LE)) {
1206*9880d681SAndroid Build Coastguard Worker     assert(MI.getOperand(OpN).isReg());
1207*9880d681SAndroid Build Coastguard Worker     BitTracker::RegisterRef RR = MI.getOperand(OpN);
1208*9880d681SAndroid Build Coastguard Worker     const TargetRegisterClass *RC = HBS::getFinalVRegClass(RR, MRI);
1209*9880d681SAndroid Build Coastguard Worker     uint16_t Width = RC->getSize()*8;
1210*9880d681SAndroid Build Coastguard Worker 
1211*9880d681SAndroid Build Coastguard Worker     if (!GotBits)
1212*9880d681SAndroid Build Coastguard Worker       T.set(Begin, Begin+Width);
1213*9880d681SAndroid Build Coastguard Worker     assert(LB <= LE && LB < Width && LE <= Width);
1214*9880d681SAndroid Build Coastguard Worker     T.reset(Begin+LB, Begin+LE);
1215*9880d681SAndroid Build Coastguard Worker     GotBits = true;
1216*9880d681SAndroid Build Coastguard Worker   }
1217*9880d681SAndroid Build Coastguard Worker   if (GotBits)
1218*9880d681SAndroid Build Coastguard Worker     Bits |= T;
1219*9880d681SAndroid Build Coastguard Worker   return GotBits;
1220*9880d681SAndroid Build Coastguard Worker }
1221*9880d681SAndroid Build Coastguard Worker 
1222*9880d681SAndroid Build Coastguard Worker 
1223*9880d681SAndroid Build Coastguard Worker // Calculates the used bits in RD ("defined register"), and checks if these
1224*9880d681SAndroid Build Coastguard Worker // bits in RS ("used register") and RD are identical.
usedBitsEqual(BitTracker::RegisterRef RD,BitTracker::RegisterRef RS)1225*9880d681SAndroid Build Coastguard Worker bool RedundantInstrElimination::usedBitsEqual(BitTracker::RegisterRef RD,
1226*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef RS) {
1227*9880d681SAndroid Build Coastguard Worker   const BitTracker::RegisterCell &DC = BT.lookup(RD.Reg);
1228*9880d681SAndroid Build Coastguard Worker   const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
1229*9880d681SAndroid Build Coastguard Worker 
1230*9880d681SAndroid Build Coastguard Worker   unsigned DB, DW;
1231*9880d681SAndroid Build Coastguard Worker   if (!HBS::getSubregMask(RD, DB, DW, MRI))
1232*9880d681SAndroid Build Coastguard Worker     return false;
1233*9880d681SAndroid Build Coastguard Worker   unsigned SB, SW;
1234*9880d681SAndroid Build Coastguard Worker   if (!HBS::getSubregMask(RS, SB, SW, MRI))
1235*9880d681SAndroid Build Coastguard Worker     return false;
1236*9880d681SAndroid Build Coastguard Worker   if (SW != DW)
1237*9880d681SAndroid Build Coastguard Worker     return false;
1238*9880d681SAndroid Build Coastguard Worker 
1239*9880d681SAndroid Build Coastguard Worker   BitVector Used(DC.width());
1240*9880d681SAndroid Build Coastguard Worker   if (!computeUsedBits(RD.Reg, Used))
1241*9880d681SAndroid Build Coastguard Worker     return false;
1242*9880d681SAndroid Build Coastguard Worker 
1243*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 0; i != DW; ++i)
1244*9880d681SAndroid Build Coastguard Worker     if (Used[i+DB] && DC[DB+i] != SC[SB+i])
1245*9880d681SAndroid Build Coastguard Worker       return false;
1246*9880d681SAndroid Build Coastguard Worker   return true;
1247*9880d681SAndroid Build Coastguard Worker }
1248*9880d681SAndroid Build Coastguard Worker 
1249*9880d681SAndroid Build Coastguard Worker 
processBlock(MachineBasicBlock & B,const RegisterSet &)1250*9880d681SAndroid Build Coastguard Worker bool RedundantInstrElimination::processBlock(MachineBasicBlock &B,
1251*9880d681SAndroid Build Coastguard Worker       const RegisterSet&) {
1252*9880d681SAndroid Build Coastguard Worker   bool Changed = false;
1253*9880d681SAndroid Build Coastguard Worker 
1254*9880d681SAndroid Build Coastguard Worker   for (auto I = B.begin(), E = B.end(), NextI = I; I != E; ++I) {
1255*9880d681SAndroid Build Coastguard Worker     NextI = std::next(I);
1256*9880d681SAndroid Build Coastguard Worker     MachineInstr *MI = &*I;
1257*9880d681SAndroid Build Coastguard Worker 
1258*9880d681SAndroid Build Coastguard Worker     if (MI->getOpcode() == TargetOpcode::COPY)
1259*9880d681SAndroid Build Coastguard Worker       continue;
1260*9880d681SAndroid Build Coastguard Worker     if (MI->hasUnmodeledSideEffects() || MI->isInlineAsm())
1261*9880d681SAndroid Build Coastguard Worker       continue;
1262*9880d681SAndroid Build Coastguard Worker     unsigned NumD = MI->getDesc().getNumDefs();
1263*9880d681SAndroid Build Coastguard Worker     if (NumD != 1)
1264*9880d681SAndroid Build Coastguard Worker       continue;
1265*9880d681SAndroid Build Coastguard Worker 
1266*9880d681SAndroid Build Coastguard Worker     BitTracker::RegisterRef RD = MI->getOperand(0);
1267*9880d681SAndroid Build Coastguard Worker     if (!BT.has(RD.Reg))
1268*9880d681SAndroid Build Coastguard Worker       continue;
1269*9880d681SAndroid Build Coastguard Worker     const BitTracker::RegisterCell &DC = BT.lookup(RD.Reg);
1270*9880d681SAndroid Build Coastguard Worker     auto At = MI->isPHI() ? B.getFirstNonPHI()
1271*9880d681SAndroid Build Coastguard Worker                           : MachineBasicBlock::iterator(MI);
1272*9880d681SAndroid Build Coastguard Worker 
1273*9880d681SAndroid Build Coastguard Worker     // Find a source operand that is equal to the result.
1274*9880d681SAndroid Build Coastguard Worker     for (auto &Op : MI->uses()) {
1275*9880d681SAndroid Build Coastguard Worker       if (!Op.isReg())
1276*9880d681SAndroid Build Coastguard Worker         continue;
1277*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef RS = Op;
1278*9880d681SAndroid Build Coastguard Worker       if (!BT.has(RS.Reg))
1279*9880d681SAndroid Build Coastguard Worker         continue;
1280*9880d681SAndroid Build Coastguard Worker       if (!HBS::isTransparentCopy(RD, RS, MRI))
1281*9880d681SAndroid Build Coastguard Worker         continue;
1282*9880d681SAndroid Build Coastguard Worker 
1283*9880d681SAndroid Build Coastguard Worker       unsigned BN, BW;
1284*9880d681SAndroid Build Coastguard Worker       if (!HBS::getSubregMask(RS, BN, BW, MRI))
1285*9880d681SAndroid Build Coastguard Worker         continue;
1286*9880d681SAndroid Build Coastguard Worker 
1287*9880d681SAndroid Build Coastguard Worker       const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
1288*9880d681SAndroid Build Coastguard Worker       if (!usedBitsEqual(RD, RS) && !HBS::isEqual(DC, 0, SC, BN, BW))
1289*9880d681SAndroid Build Coastguard Worker         continue;
1290*9880d681SAndroid Build Coastguard Worker 
1291*9880d681SAndroid Build Coastguard Worker       // If found, replace the instruction with a COPY.
1292*9880d681SAndroid Build Coastguard Worker       const DebugLoc &DL = MI->getDebugLoc();
1293*9880d681SAndroid Build Coastguard Worker       const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
1294*9880d681SAndroid Build Coastguard Worker       unsigned NewR = MRI.createVirtualRegister(FRC);
1295*9880d681SAndroid Build Coastguard Worker       BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
1296*9880d681SAndroid Build Coastguard Worker           .addReg(RS.Reg, 0, RS.Sub);
1297*9880d681SAndroid Build Coastguard Worker       HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
1298*9880d681SAndroid Build Coastguard Worker       BT.put(BitTracker::RegisterRef(NewR), SC);
1299*9880d681SAndroid Build Coastguard Worker       Changed = true;
1300*9880d681SAndroid Build Coastguard Worker       break;
1301*9880d681SAndroid Build Coastguard Worker     }
1302*9880d681SAndroid Build Coastguard Worker   }
1303*9880d681SAndroid Build Coastguard Worker 
1304*9880d681SAndroid Build Coastguard Worker   return Changed;
1305*9880d681SAndroid Build Coastguard Worker }
1306*9880d681SAndroid Build Coastguard Worker 
1307*9880d681SAndroid Build Coastguard Worker 
1308*9880d681SAndroid Build Coastguard Worker //
1309*9880d681SAndroid Build Coastguard Worker // Const generation
1310*9880d681SAndroid Build Coastguard Worker //
1311*9880d681SAndroid Build Coastguard Worker // Recognize instructions that produce constant values known at compile-time.
1312*9880d681SAndroid Build Coastguard Worker // Replace them with register definitions that load these constants directly.
1313*9880d681SAndroid Build Coastguard Worker namespace {
1314*9880d681SAndroid Build Coastguard Worker   class ConstGeneration : public Transformation {
1315*9880d681SAndroid Build Coastguard Worker   public:
ConstGeneration(BitTracker & bt,const HexagonInstrInfo & hii,MachineRegisterInfo & mri)1316*9880d681SAndroid Build Coastguard Worker     ConstGeneration(BitTracker &bt, const HexagonInstrInfo &hii,
1317*9880d681SAndroid Build Coastguard Worker         MachineRegisterInfo &mri)
1318*9880d681SAndroid Build Coastguard Worker       : Transformation(true), HII(hii), MRI(mri), BT(bt) {}
1319*9880d681SAndroid Build Coastguard Worker     bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1320*9880d681SAndroid Build Coastguard Worker   private:
1321*9880d681SAndroid Build Coastguard Worker     bool isTfrConst(const MachineInstr &MI) const;
1322*9880d681SAndroid Build Coastguard Worker     bool isConst(unsigned R, int64_t &V) const;
1323*9880d681SAndroid Build Coastguard Worker     unsigned genTfrConst(const TargetRegisterClass *RC, int64_t C,
1324*9880d681SAndroid Build Coastguard Worker         MachineBasicBlock &B, MachineBasicBlock::iterator At, DebugLoc &DL);
1325*9880d681SAndroid Build Coastguard Worker 
1326*9880d681SAndroid Build Coastguard Worker     const HexagonInstrInfo &HII;
1327*9880d681SAndroid Build Coastguard Worker     MachineRegisterInfo &MRI;
1328*9880d681SAndroid Build Coastguard Worker     BitTracker &BT;
1329*9880d681SAndroid Build Coastguard Worker   };
1330*9880d681SAndroid Build Coastguard Worker }
1331*9880d681SAndroid Build Coastguard Worker 
isConst(unsigned R,int64_t & C) const1332*9880d681SAndroid Build Coastguard Worker bool ConstGeneration::isConst(unsigned R, int64_t &C) const {
1333*9880d681SAndroid Build Coastguard Worker   if (!BT.has(R))
1334*9880d681SAndroid Build Coastguard Worker     return false;
1335*9880d681SAndroid Build Coastguard Worker   const BitTracker::RegisterCell &RC = BT.lookup(R);
1336*9880d681SAndroid Build Coastguard Worker   int64_t T = 0;
1337*9880d681SAndroid Build Coastguard Worker   for (unsigned i = RC.width(); i > 0; --i) {
1338*9880d681SAndroid Build Coastguard Worker     const BitTracker::BitValue &V = RC[i-1];
1339*9880d681SAndroid Build Coastguard Worker     T <<= 1;
1340*9880d681SAndroid Build Coastguard Worker     if (V.is(1))
1341*9880d681SAndroid Build Coastguard Worker       T |= 1;
1342*9880d681SAndroid Build Coastguard Worker     else if (!V.is(0))
1343*9880d681SAndroid Build Coastguard Worker       return false;
1344*9880d681SAndroid Build Coastguard Worker   }
1345*9880d681SAndroid Build Coastguard Worker   C = T;
1346*9880d681SAndroid Build Coastguard Worker   return true;
1347*9880d681SAndroid Build Coastguard Worker }
1348*9880d681SAndroid Build Coastguard Worker 
isTfrConst(const MachineInstr & MI) const1349*9880d681SAndroid Build Coastguard Worker bool ConstGeneration::isTfrConst(const MachineInstr &MI) const {
1350*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI.getOpcode();
1351*9880d681SAndroid Build Coastguard Worker   switch (Opc) {
1352*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_combineii:
1353*9880d681SAndroid Build Coastguard Worker     case Hexagon::A4_combineii:
1354*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_tfrsi:
1355*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_tfrpi:
1356*9880d681SAndroid Build Coastguard Worker     case Hexagon::TFR_PdTrue:
1357*9880d681SAndroid Build Coastguard Worker     case Hexagon::TFR_PdFalse:
1358*9880d681SAndroid Build Coastguard Worker     case Hexagon::CONST32_Int_Real:
1359*9880d681SAndroid Build Coastguard Worker     case Hexagon::CONST64_Int_Real:
1360*9880d681SAndroid Build Coastguard Worker       return true;
1361*9880d681SAndroid Build Coastguard Worker   }
1362*9880d681SAndroid Build Coastguard Worker   return false;
1363*9880d681SAndroid Build Coastguard Worker }
1364*9880d681SAndroid Build Coastguard Worker 
1365*9880d681SAndroid Build Coastguard Worker 
1366*9880d681SAndroid Build Coastguard Worker // Generate a transfer-immediate instruction that is appropriate for the
1367*9880d681SAndroid Build Coastguard Worker // register class and the actual value being transferred.
genTfrConst(const TargetRegisterClass * RC,int64_t C,MachineBasicBlock & B,MachineBasicBlock::iterator At,DebugLoc & DL)1368*9880d681SAndroid Build Coastguard Worker unsigned ConstGeneration::genTfrConst(const TargetRegisterClass *RC, int64_t C,
1369*9880d681SAndroid Build Coastguard Worker       MachineBasicBlock &B, MachineBasicBlock::iterator At, DebugLoc &DL) {
1370*9880d681SAndroid Build Coastguard Worker   unsigned Reg = MRI.createVirtualRegister(RC);
1371*9880d681SAndroid Build Coastguard Worker   if (RC == &Hexagon::IntRegsRegClass) {
1372*9880d681SAndroid Build Coastguard Worker     BuildMI(B, At, DL, HII.get(Hexagon::A2_tfrsi), Reg)
1373*9880d681SAndroid Build Coastguard Worker         .addImm(int32_t(C));
1374*9880d681SAndroid Build Coastguard Worker     return Reg;
1375*9880d681SAndroid Build Coastguard Worker   }
1376*9880d681SAndroid Build Coastguard Worker 
1377*9880d681SAndroid Build Coastguard Worker   if (RC == &Hexagon::DoubleRegsRegClass) {
1378*9880d681SAndroid Build Coastguard Worker     if (isInt<8>(C)) {
1379*9880d681SAndroid Build Coastguard Worker       BuildMI(B, At, DL, HII.get(Hexagon::A2_tfrpi), Reg)
1380*9880d681SAndroid Build Coastguard Worker           .addImm(C);
1381*9880d681SAndroid Build Coastguard Worker       return Reg;
1382*9880d681SAndroid Build Coastguard Worker     }
1383*9880d681SAndroid Build Coastguard Worker 
1384*9880d681SAndroid Build Coastguard Worker     unsigned Lo = Lo_32(C), Hi = Hi_32(C);
1385*9880d681SAndroid Build Coastguard Worker     if (isInt<8>(Lo) || isInt<8>(Hi)) {
1386*9880d681SAndroid Build Coastguard Worker       unsigned Opc = isInt<8>(Lo) ? Hexagon::A2_combineii
1387*9880d681SAndroid Build Coastguard Worker                                   : Hexagon::A4_combineii;
1388*9880d681SAndroid Build Coastguard Worker       BuildMI(B, At, DL, HII.get(Opc), Reg)
1389*9880d681SAndroid Build Coastguard Worker           .addImm(int32_t(Hi))
1390*9880d681SAndroid Build Coastguard Worker           .addImm(int32_t(Lo));
1391*9880d681SAndroid Build Coastguard Worker       return Reg;
1392*9880d681SAndroid Build Coastguard Worker     }
1393*9880d681SAndroid Build Coastguard Worker 
1394*9880d681SAndroid Build Coastguard Worker     BuildMI(B, At, DL, HII.get(Hexagon::CONST64_Int_Real), Reg)
1395*9880d681SAndroid Build Coastguard Worker         .addImm(C);
1396*9880d681SAndroid Build Coastguard Worker     return Reg;
1397*9880d681SAndroid Build Coastguard Worker   }
1398*9880d681SAndroid Build Coastguard Worker 
1399*9880d681SAndroid Build Coastguard Worker   if (RC == &Hexagon::PredRegsRegClass) {
1400*9880d681SAndroid Build Coastguard Worker     unsigned Opc;
1401*9880d681SAndroid Build Coastguard Worker     if (C == 0)
1402*9880d681SAndroid Build Coastguard Worker       Opc = Hexagon::TFR_PdFalse;
1403*9880d681SAndroid Build Coastguard Worker     else if ((C & 0xFF) == 0xFF)
1404*9880d681SAndroid Build Coastguard Worker       Opc = Hexagon::TFR_PdTrue;
1405*9880d681SAndroid Build Coastguard Worker     else
1406*9880d681SAndroid Build Coastguard Worker       return 0;
1407*9880d681SAndroid Build Coastguard Worker     BuildMI(B, At, DL, HII.get(Opc), Reg);
1408*9880d681SAndroid Build Coastguard Worker     return Reg;
1409*9880d681SAndroid Build Coastguard Worker   }
1410*9880d681SAndroid Build Coastguard Worker 
1411*9880d681SAndroid Build Coastguard Worker   return 0;
1412*9880d681SAndroid Build Coastguard Worker }
1413*9880d681SAndroid Build Coastguard Worker 
1414*9880d681SAndroid Build Coastguard Worker 
processBlock(MachineBasicBlock & B,const RegisterSet &)1415*9880d681SAndroid Build Coastguard Worker bool ConstGeneration::processBlock(MachineBasicBlock &B, const RegisterSet&) {
1416*9880d681SAndroid Build Coastguard Worker   bool Changed = false;
1417*9880d681SAndroid Build Coastguard Worker   RegisterSet Defs;
1418*9880d681SAndroid Build Coastguard Worker 
1419*9880d681SAndroid Build Coastguard Worker   for (auto I = B.begin(), E = B.end(); I != E; ++I) {
1420*9880d681SAndroid Build Coastguard Worker     if (isTfrConst(*I))
1421*9880d681SAndroid Build Coastguard Worker       continue;
1422*9880d681SAndroid Build Coastguard Worker     Defs.clear();
1423*9880d681SAndroid Build Coastguard Worker     HBS::getInstrDefs(*I, Defs);
1424*9880d681SAndroid Build Coastguard Worker     if (Defs.count() != 1)
1425*9880d681SAndroid Build Coastguard Worker       continue;
1426*9880d681SAndroid Build Coastguard Worker     unsigned DR = Defs.find_first();
1427*9880d681SAndroid Build Coastguard Worker     if (!TargetRegisterInfo::isVirtualRegister(DR))
1428*9880d681SAndroid Build Coastguard Worker       continue;
1429*9880d681SAndroid Build Coastguard Worker     int64_t C;
1430*9880d681SAndroid Build Coastguard Worker     if (isConst(DR, C)) {
1431*9880d681SAndroid Build Coastguard Worker       DebugLoc DL = I->getDebugLoc();
1432*9880d681SAndroid Build Coastguard Worker       auto At = I->isPHI() ? B.getFirstNonPHI() : I;
1433*9880d681SAndroid Build Coastguard Worker       unsigned ImmReg = genTfrConst(MRI.getRegClass(DR), C, B, At, DL);
1434*9880d681SAndroid Build Coastguard Worker       if (ImmReg) {
1435*9880d681SAndroid Build Coastguard Worker         HBS::replaceReg(DR, ImmReg, MRI);
1436*9880d681SAndroid Build Coastguard Worker         BT.put(ImmReg, BT.lookup(DR));
1437*9880d681SAndroid Build Coastguard Worker         Changed = true;
1438*9880d681SAndroid Build Coastguard Worker       }
1439*9880d681SAndroid Build Coastguard Worker     }
1440*9880d681SAndroid Build Coastguard Worker   }
1441*9880d681SAndroid Build Coastguard Worker   return Changed;
1442*9880d681SAndroid Build Coastguard Worker }
1443*9880d681SAndroid Build Coastguard Worker 
1444*9880d681SAndroid Build Coastguard Worker 
1445*9880d681SAndroid Build Coastguard Worker //
1446*9880d681SAndroid Build Coastguard Worker // Copy generation
1447*9880d681SAndroid Build Coastguard Worker //
1448*9880d681SAndroid Build Coastguard Worker // Identify pairs of available registers which hold identical values.
1449*9880d681SAndroid Build Coastguard Worker // In such cases, only one of them needs to be calculated, the other one
1450*9880d681SAndroid Build Coastguard Worker // will be defined as a copy of the first.
1451*9880d681SAndroid Build Coastguard Worker //
1452*9880d681SAndroid Build Coastguard Worker // Copy propagation
1453*9880d681SAndroid Build Coastguard Worker //
1454*9880d681SAndroid Build Coastguard Worker // Eliminate register copies RD = RS, by replacing the uses of RD with
1455*9880d681SAndroid Build Coastguard Worker // with uses of RS.
1456*9880d681SAndroid Build Coastguard Worker namespace {
1457*9880d681SAndroid Build Coastguard Worker   class CopyGeneration : public Transformation {
1458*9880d681SAndroid Build Coastguard Worker   public:
CopyGeneration(BitTracker & bt,const HexagonInstrInfo & hii,MachineRegisterInfo & mri)1459*9880d681SAndroid Build Coastguard Worker     CopyGeneration(BitTracker &bt, const HexagonInstrInfo &hii,
1460*9880d681SAndroid Build Coastguard Worker         MachineRegisterInfo &mri)
1461*9880d681SAndroid Build Coastguard Worker       : Transformation(true), HII(hii), MRI(mri), BT(bt) {}
1462*9880d681SAndroid Build Coastguard Worker     bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1463*9880d681SAndroid Build Coastguard Worker   private:
1464*9880d681SAndroid Build Coastguard Worker     bool findMatch(const BitTracker::RegisterRef &Inp,
1465*9880d681SAndroid Build Coastguard Worker         BitTracker::RegisterRef &Out, const RegisterSet &AVs);
1466*9880d681SAndroid Build Coastguard Worker 
1467*9880d681SAndroid Build Coastguard Worker     const HexagonInstrInfo &HII;
1468*9880d681SAndroid Build Coastguard Worker     MachineRegisterInfo &MRI;
1469*9880d681SAndroid Build Coastguard Worker     BitTracker &BT;
1470*9880d681SAndroid Build Coastguard Worker   };
1471*9880d681SAndroid Build Coastguard Worker 
1472*9880d681SAndroid Build Coastguard Worker   class CopyPropagation : public Transformation {
1473*9880d681SAndroid Build Coastguard Worker   public:
CopyPropagation(const HexagonRegisterInfo & hri,MachineRegisterInfo & mri)1474*9880d681SAndroid Build Coastguard Worker     CopyPropagation(const HexagonRegisterInfo &hri, MachineRegisterInfo &mri)
1475*9880d681SAndroid Build Coastguard Worker         : Transformation(false), MRI(mri) {}
1476*9880d681SAndroid Build Coastguard Worker     bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1477*9880d681SAndroid Build Coastguard Worker     static bool isCopyReg(unsigned Opc);
1478*9880d681SAndroid Build Coastguard Worker   private:
1479*9880d681SAndroid Build Coastguard Worker     bool propagateRegCopy(MachineInstr &MI);
1480*9880d681SAndroid Build Coastguard Worker 
1481*9880d681SAndroid Build Coastguard Worker     MachineRegisterInfo &MRI;
1482*9880d681SAndroid Build Coastguard Worker   };
1483*9880d681SAndroid Build Coastguard Worker 
1484*9880d681SAndroid Build Coastguard Worker }
1485*9880d681SAndroid Build Coastguard Worker 
1486*9880d681SAndroid Build Coastguard Worker 
1487*9880d681SAndroid Build Coastguard Worker /// Check if there is a register in AVs that is identical to Inp. If so,
1488*9880d681SAndroid Build Coastguard Worker /// 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)1489*9880d681SAndroid Build Coastguard Worker bool CopyGeneration::findMatch(const BitTracker::RegisterRef &Inp,
1490*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef &Out, const RegisterSet &AVs) {
1491*9880d681SAndroid Build Coastguard Worker   if (!BT.has(Inp.Reg))
1492*9880d681SAndroid Build Coastguard Worker     return false;
1493*9880d681SAndroid Build Coastguard Worker   const BitTracker::RegisterCell &InpRC = BT.lookup(Inp.Reg);
1494*9880d681SAndroid Build Coastguard Worker   unsigned B, W;
1495*9880d681SAndroid Build Coastguard Worker   if (!HBS::getSubregMask(Inp, B, W, MRI))
1496*9880d681SAndroid Build Coastguard Worker     return false;
1497*9880d681SAndroid Build Coastguard Worker 
1498*9880d681SAndroid Build Coastguard Worker   for (unsigned R = AVs.find_first(); R; R = AVs.find_next(R)) {
1499*9880d681SAndroid Build Coastguard Worker     if (!BT.has(R) || !HBS::isTransparentCopy(R, Inp, MRI))
1500*9880d681SAndroid Build Coastguard Worker       continue;
1501*9880d681SAndroid Build Coastguard Worker     const BitTracker::RegisterCell &RC = BT.lookup(R);
1502*9880d681SAndroid Build Coastguard Worker     unsigned RW = RC.width();
1503*9880d681SAndroid Build Coastguard Worker     if (W == RW) {
1504*9880d681SAndroid Build Coastguard Worker       if (MRI.getRegClass(Inp.Reg) != MRI.getRegClass(R))
1505*9880d681SAndroid Build Coastguard Worker         continue;
1506*9880d681SAndroid Build Coastguard Worker       if (!HBS::isEqual(InpRC, B, RC, 0, W))
1507*9880d681SAndroid Build Coastguard Worker         continue;
1508*9880d681SAndroid Build Coastguard Worker       Out.Reg = R;
1509*9880d681SAndroid Build Coastguard Worker       Out.Sub = 0;
1510*9880d681SAndroid Build Coastguard Worker       return true;
1511*9880d681SAndroid Build Coastguard Worker     }
1512*9880d681SAndroid Build Coastguard Worker     // Check if there is a super-register, whose part (with a subregister)
1513*9880d681SAndroid Build Coastguard Worker     // is equal to the input.
1514*9880d681SAndroid Build Coastguard Worker     // Only do double registers for now.
1515*9880d681SAndroid Build Coastguard Worker     if (W*2 != RW)
1516*9880d681SAndroid Build Coastguard Worker       continue;
1517*9880d681SAndroid Build Coastguard Worker     if (MRI.getRegClass(R) != &Hexagon::DoubleRegsRegClass)
1518*9880d681SAndroid Build Coastguard Worker       continue;
1519*9880d681SAndroid Build Coastguard Worker 
1520*9880d681SAndroid Build Coastguard Worker     if (HBS::isEqual(InpRC, B, RC, 0, W))
1521*9880d681SAndroid Build Coastguard Worker       Out.Sub = Hexagon::subreg_loreg;
1522*9880d681SAndroid Build Coastguard Worker     else if (HBS::isEqual(InpRC, B, RC, W, W))
1523*9880d681SAndroid Build Coastguard Worker       Out.Sub = Hexagon::subreg_hireg;
1524*9880d681SAndroid Build Coastguard Worker     else
1525*9880d681SAndroid Build Coastguard Worker       continue;
1526*9880d681SAndroid Build Coastguard Worker     Out.Reg = R;
1527*9880d681SAndroid Build Coastguard Worker     return true;
1528*9880d681SAndroid Build Coastguard Worker   }
1529*9880d681SAndroid Build Coastguard Worker   return false;
1530*9880d681SAndroid Build Coastguard Worker }
1531*9880d681SAndroid Build Coastguard Worker 
1532*9880d681SAndroid Build Coastguard Worker 
processBlock(MachineBasicBlock & B,const RegisterSet & AVs)1533*9880d681SAndroid Build Coastguard Worker bool CopyGeneration::processBlock(MachineBasicBlock &B,
1534*9880d681SAndroid Build Coastguard Worker       const RegisterSet &AVs) {
1535*9880d681SAndroid Build Coastguard Worker   RegisterSet AVB(AVs);
1536*9880d681SAndroid Build Coastguard Worker   bool Changed = false;
1537*9880d681SAndroid Build Coastguard Worker   RegisterSet Defs;
1538*9880d681SAndroid Build Coastguard Worker 
1539*9880d681SAndroid Build Coastguard Worker   for (auto I = B.begin(), E = B.end(), NextI = I; I != E;
1540*9880d681SAndroid Build Coastguard Worker        ++I, AVB.insert(Defs)) {
1541*9880d681SAndroid Build Coastguard Worker     NextI = std::next(I);
1542*9880d681SAndroid Build Coastguard Worker     Defs.clear();
1543*9880d681SAndroid Build Coastguard Worker     HBS::getInstrDefs(*I, Defs);
1544*9880d681SAndroid Build Coastguard Worker 
1545*9880d681SAndroid Build Coastguard Worker     unsigned Opc = I->getOpcode();
1546*9880d681SAndroid Build Coastguard Worker     if (CopyPropagation::isCopyReg(Opc))
1547*9880d681SAndroid Build Coastguard Worker       continue;
1548*9880d681SAndroid Build Coastguard Worker 
1549*9880d681SAndroid Build Coastguard Worker     for (unsigned R = Defs.find_first(); R; R = Defs.find_next(R)) {
1550*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef MR;
1551*9880d681SAndroid Build Coastguard Worker       if (!findMatch(R, MR, AVB))
1552*9880d681SAndroid Build Coastguard Worker         continue;
1553*9880d681SAndroid Build Coastguard Worker       DebugLoc DL = I->getDebugLoc();
1554*9880d681SAndroid Build Coastguard Worker       auto *FRC = HBS::getFinalVRegClass(MR, MRI);
1555*9880d681SAndroid Build Coastguard Worker       unsigned NewR = MRI.createVirtualRegister(FRC);
1556*9880d681SAndroid Build Coastguard Worker       auto At = I->isPHI() ? B.getFirstNonPHI() : I;
1557*9880d681SAndroid Build Coastguard Worker       BuildMI(B, At, DL, HII.get(TargetOpcode::COPY), NewR)
1558*9880d681SAndroid Build Coastguard Worker         .addReg(MR.Reg, 0, MR.Sub);
1559*9880d681SAndroid Build Coastguard Worker       BT.put(BitTracker::RegisterRef(NewR), BT.get(MR));
1560*9880d681SAndroid Build Coastguard Worker     }
1561*9880d681SAndroid Build Coastguard Worker   }
1562*9880d681SAndroid Build Coastguard Worker 
1563*9880d681SAndroid Build Coastguard Worker   return Changed;
1564*9880d681SAndroid Build Coastguard Worker }
1565*9880d681SAndroid Build Coastguard Worker 
1566*9880d681SAndroid Build Coastguard Worker 
isCopyReg(unsigned Opc)1567*9880d681SAndroid Build Coastguard Worker bool CopyPropagation::isCopyReg(unsigned Opc) {
1568*9880d681SAndroid Build Coastguard Worker   switch (Opc) {
1569*9880d681SAndroid Build Coastguard Worker     case TargetOpcode::COPY:
1570*9880d681SAndroid Build Coastguard Worker     case TargetOpcode::REG_SEQUENCE:
1571*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_tfr:
1572*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_tfrp:
1573*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_combinew:
1574*9880d681SAndroid Build Coastguard Worker     case Hexagon::A4_combineir:
1575*9880d681SAndroid Build Coastguard Worker     case Hexagon::A4_combineri:
1576*9880d681SAndroid Build Coastguard Worker       return true;
1577*9880d681SAndroid Build Coastguard Worker     default:
1578*9880d681SAndroid Build Coastguard Worker       break;
1579*9880d681SAndroid Build Coastguard Worker   }
1580*9880d681SAndroid Build Coastguard Worker   return false;
1581*9880d681SAndroid Build Coastguard Worker }
1582*9880d681SAndroid Build Coastguard Worker 
1583*9880d681SAndroid Build Coastguard Worker 
propagateRegCopy(MachineInstr & MI)1584*9880d681SAndroid Build Coastguard Worker bool CopyPropagation::propagateRegCopy(MachineInstr &MI) {
1585*9880d681SAndroid Build Coastguard Worker   bool Changed = false;
1586*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI.getOpcode();
1587*9880d681SAndroid Build Coastguard Worker   BitTracker::RegisterRef RD = MI.getOperand(0);
1588*9880d681SAndroid Build Coastguard Worker   assert(MI.getOperand(0).getSubReg() == 0);
1589*9880d681SAndroid Build Coastguard Worker 
1590*9880d681SAndroid Build Coastguard Worker   switch (Opc) {
1591*9880d681SAndroid Build Coastguard Worker     case TargetOpcode::COPY:
1592*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_tfr:
1593*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_tfrp: {
1594*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef RS = MI.getOperand(1);
1595*9880d681SAndroid Build Coastguard Worker       if (!HBS::isTransparentCopy(RD, RS, MRI))
1596*9880d681SAndroid Build Coastguard Worker         break;
1597*9880d681SAndroid Build Coastguard Worker       if (RS.Sub != 0)
1598*9880d681SAndroid Build Coastguard Worker         Changed = HBS::replaceRegWithSub(RD.Reg, RS.Reg, RS.Sub, MRI);
1599*9880d681SAndroid Build Coastguard Worker       else
1600*9880d681SAndroid Build Coastguard Worker         Changed = HBS::replaceReg(RD.Reg, RS.Reg, MRI);
1601*9880d681SAndroid Build Coastguard Worker       break;
1602*9880d681SAndroid Build Coastguard Worker     }
1603*9880d681SAndroid Build Coastguard Worker     case TargetOpcode::REG_SEQUENCE: {
1604*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef SL, SH;
1605*9880d681SAndroid Build Coastguard Worker       if (HBS::parseRegSequence(MI, SL, SH)) {
1606*9880d681SAndroid Build Coastguard Worker         Changed = HBS::replaceSubWithSub(RD.Reg, Hexagon::subreg_loreg,
1607*9880d681SAndroid Build Coastguard Worker                                          SL.Reg, SL.Sub, MRI);
1608*9880d681SAndroid Build Coastguard Worker         Changed |= HBS::replaceSubWithSub(RD.Reg, Hexagon::subreg_hireg,
1609*9880d681SAndroid Build Coastguard Worker                                           SH.Reg, SH.Sub, MRI);
1610*9880d681SAndroid Build Coastguard Worker       }
1611*9880d681SAndroid Build Coastguard Worker       break;
1612*9880d681SAndroid Build Coastguard Worker     }
1613*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_combinew: {
1614*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef RH = MI.getOperand(1), RL = MI.getOperand(2);
1615*9880d681SAndroid Build Coastguard Worker       Changed = HBS::replaceSubWithSub(RD.Reg, Hexagon::subreg_loreg,
1616*9880d681SAndroid Build Coastguard Worker                                        RL.Reg, RL.Sub, MRI);
1617*9880d681SAndroid Build Coastguard Worker       Changed |= HBS::replaceSubWithSub(RD.Reg, Hexagon::subreg_hireg,
1618*9880d681SAndroid Build Coastguard Worker                                         RH.Reg, RH.Sub, MRI);
1619*9880d681SAndroid Build Coastguard Worker       break;
1620*9880d681SAndroid Build Coastguard Worker     }
1621*9880d681SAndroid Build Coastguard Worker     case Hexagon::A4_combineir:
1622*9880d681SAndroid Build Coastguard Worker     case Hexagon::A4_combineri: {
1623*9880d681SAndroid Build Coastguard Worker       unsigned SrcX = (Opc == Hexagon::A4_combineir) ? 2 : 1;
1624*9880d681SAndroid Build Coastguard Worker       unsigned Sub = (Opc == Hexagon::A4_combineir) ? Hexagon::subreg_loreg
1625*9880d681SAndroid Build Coastguard Worker                                                     : Hexagon::subreg_hireg;
1626*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef RS = MI.getOperand(SrcX);
1627*9880d681SAndroid Build Coastguard Worker       Changed = HBS::replaceSubWithSub(RD.Reg, Sub, RS.Reg, RS.Sub, MRI);
1628*9880d681SAndroid Build Coastguard Worker       break;
1629*9880d681SAndroid Build Coastguard Worker     }
1630*9880d681SAndroid Build Coastguard Worker   }
1631*9880d681SAndroid Build Coastguard Worker   return Changed;
1632*9880d681SAndroid Build Coastguard Worker }
1633*9880d681SAndroid Build Coastguard Worker 
1634*9880d681SAndroid Build Coastguard Worker 
processBlock(MachineBasicBlock & B,const RegisterSet &)1635*9880d681SAndroid Build Coastguard Worker bool CopyPropagation::processBlock(MachineBasicBlock &B, const RegisterSet&) {
1636*9880d681SAndroid Build Coastguard Worker   std::vector<MachineInstr*> Instrs;
1637*9880d681SAndroid Build Coastguard Worker   for (auto I = B.rbegin(), E = B.rend(); I != E; ++I)
1638*9880d681SAndroid Build Coastguard Worker     Instrs.push_back(&*I);
1639*9880d681SAndroid Build Coastguard Worker 
1640*9880d681SAndroid Build Coastguard Worker   bool Changed = false;
1641*9880d681SAndroid Build Coastguard Worker   for (auto I : Instrs) {
1642*9880d681SAndroid Build Coastguard Worker     unsigned Opc = I->getOpcode();
1643*9880d681SAndroid Build Coastguard Worker     if (!CopyPropagation::isCopyReg(Opc))
1644*9880d681SAndroid Build Coastguard Worker       continue;
1645*9880d681SAndroid Build Coastguard Worker     Changed |= propagateRegCopy(*I);
1646*9880d681SAndroid Build Coastguard Worker   }
1647*9880d681SAndroid Build Coastguard Worker 
1648*9880d681SAndroid Build Coastguard Worker   return Changed;
1649*9880d681SAndroid Build Coastguard Worker }
1650*9880d681SAndroid Build Coastguard Worker 
1651*9880d681SAndroid Build Coastguard Worker 
1652*9880d681SAndroid Build Coastguard Worker //
1653*9880d681SAndroid Build Coastguard Worker // Bit simplification
1654*9880d681SAndroid Build Coastguard Worker //
1655*9880d681SAndroid Build Coastguard Worker // Recognize patterns that can be simplified and replace them with the
1656*9880d681SAndroid Build Coastguard Worker // simpler forms.
1657*9880d681SAndroid Build Coastguard Worker // This is by no means complete
1658*9880d681SAndroid Build Coastguard Worker namespace {
1659*9880d681SAndroid Build Coastguard Worker   class BitSimplification : public Transformation {
1660*9880d681SAndroid Build Coastguard Worker   public:
BitSimplification(BitTracker & bt,const HexagonInstrInfo & hii,MachineRegisterInfo & mri)1661*9880d681SAndroid Build Coastguard Worker     BitSimplification(BitTracker &bt, const HexagonInstrInfo &hii,
1662*9880d681SAndroid Build Coastguard Worker         MachineRegisterInfo &mri)
1663*9880d681SAndroid Build Coastguard Worker       : Transformation(true), HII(hii), MRI(mri), BT(bt) {}
1664*9880d681SAndroid Build Coastguard Worker     bool processBlock(MachineBasicBlock &B, const RegisterSet &AVs) override;
1665*9880d681SAndroid Build Coastguard Worker   private:
1666*9880d681SAndroid Build Coastguard Worker     struct RegHalf : public BitTracker::RegisterRef {
1667*9880d681SAndroid Build Coastguard Worker       bool Low;  // Low/High halfword.
1668*9880d681SAndroid Build Coastguard Worker     };
1669*9880d681SAndroid Build Coastguard Worker 
1670*9880d681SAndroid Build Coastguard Worker     bool matchHalf(unsigned SelfR, const BitTracker::RegisterCell &RC,
1671*9880d681SAndroid Build Coastguard Worker           unsigned B, RegHalf &RH);
1672*9880d681SAndroid Build Coastguard Worker 
1673*9880d681SAndroid Build Coastguard Worker     bool matchPackhl(unsigned SelfR, const BitTracker::RegisterCell &RC,
1674*9880d681SAndroid Build Coastguard Worker           BitTracker::RegisterRef &Rs, BitTracker::RegisterRef &Rt);
1675*9880d681SAndroid Build Coastguard Worker     unsigned getCombineOpcode(bool HLow, bool LLow);
1676*9880d681SAndroid Build Coastguard Worker 
1677*9880d681SAndroid Build Coastguard Worker     bool genStoreUpperHalf(MachineInstr *MI);
1678*9880d681SAndroid Build Coastguard Worker     bool genStoreImmediate(MachineInstr *MI);
1679*9880d681SAndroid Build Coastguard Worker     bool genPackhl(MachineInstr *MI, BitTracker::RegisterRef RD,
1680*9880d681SAndroid Build Coastguard Worker           const BitTracker::RegisterCell &RC);
1681*9880d681SAndroid Build Coastguard Worker     bool genExtractHalf(MachineInstr *MI, BitTracker::RegisterRef RD,
1682*9880d681SAndroid Build Coastguard Worker           const BitTracker::RegisterCell &RC);
1683*9880d681SAndroid Build Coastguard Worker     bool genCombineHalf(MachineInstr *MI, BitTracker::RegisterRef RD,
1684*9880d681SAndroid Build Coastguard Worker           const BitTracker::RegisterCell &RC);
1685*9880d681SAndroid Build Coastguard Worker     bool genExtractLow(MachineInstr *MI, BitTracker::RegisterRef RD,
1686*9880d681SAndroid Build Coastguard Worker           const BitTracker::RegisterCell &RC);
1687*9880d681SAndroid Build Coastguard Worker     bool simplifyTstbit(MachineInstr *MI, BitTracker::RegisterRef RD,
1688*9880d681SAndroid Build Coastguard Worker           const BitTracker::RegisterCell &RC);
1689*9880d681SAndroid Build Coastguard Worker 
1690*9880d681SAndroid Build Coastguard Worker     const HexagonInstrInfo &HII;
1691*9880d681SAndroid Build Coastguard Worker     MachineRegisterInfo &MRI;
1692*9880d681SAndroid Build Coastguard Worker     BitTracker &BT;
1693*9880d681SAndroid Build Coastguard Worker   };
1694*9880d681SAndroid Build Coastguard Worker }
1695*9880d681SAndroid Build Coastguard Worker 
1696*9880d681SAndroid Build Coastguard Worker 
1697*9880d681SAndroid Build Coastguard Worker // Check if the bits [B..B+16) in register cell RC form a valid halfword,
1698*9880d681SAndroid Build Coastguard Worker // i.e. [0..16), [16..32), etc. of some register. If so, return true and
1699*9880d681SAndroid Build Coastguard Worker // set the information about the found register in RH.
matchHalf(unsigned SelfR,const BitTracker::RegisterCell & RC,unsigned B,RegHalf & RH)1700*9880d681SAndroid Build Coastguard Worker bool BitSimplification::matchHalf(unsigned SelfR,
1701*9880d681SAndroid Build Coastguard Worker       const BitTracker::RegisterCell &RC, unsigned B, RegHalf &RH) {
1702*9880d681SAndroid Build Coastguard Worker   // XXX This could be searching in the set of available registers, in case
1703*9880d681SAndroid Build Coastguard Worker   // the match is not exact.
1704*9880d681SAndroid Build Coastguard Worker 
1705*9880d681SAndroid Build Coastguard Worker   // Match 16-bit chunks, where the RC[B..B+15] references exactly one
1706*9880d681SAndroid Build Coastguard Worker   // register and all the bits B..B+15 match between RC and the register.
1707*9880d681SAndroid Build Coastguard Worker   // This is meant to match "v1[0-15]", where v1 = { [0]:0 [1-15]:v1... },
1708*9880d681SAndroid Build Coastguard Worker   // and RC = { [0]:0 [1-15]:v1[1-15]... }.
1709*9880d681SAndroid Build Coastguard Worker   bool Low = false;
1710*9880d681SAndroid Build Coastguard Worker   unsigned I = B;
1711*9880d681SAndroid Build Coastguard Worker   while (I < B+16 && RC[I].num())
1712*9880d681SAndroid Build Coastguard Worker     I++;
1713*9880d681SAndroid Build Coastguard Worker   if (I == B+16)
1714*9880d681SAndroid Build Coastguard Worker     return false;
1715*9880d681SAndroid Build Coastguard Worker 
1716*9880d681SAndroid Build Coastguard Worker   unsigned Reg = RC[I].RefI.Reg;
1717*9880d681SAndroid Build Coastguard Worker   unsigned P = RC[I].RefI.Pos;    // The RefI.Pos will be advanced by I-B.
1718*9880d681SAndroid Build Coastguard Worker   if (P < I-B)
1719*9880d681SAndroid Build Coastguard Worker     return false;
1720*9880d681SAndroid Build Coastguard Worker   unsigned Pos = P - (I-B);
1721*9880d681SAndroid Build Coastguard Worker 
1722*9880d681SAndroid Build Coastguard Worker   if (Reg == 0 || Reg == SelfR)    // Don't match "self".
1723*9880d681SAndroid Build Coastguard Worker     return false;
1724*9880d681SAndroid Build Coastguard Worker   if (!TargetRegisterInfo::isVirtualRegister(Reg))
1725*9880d681SAndroid Build Coastguard Worker     return false;
1726*9880d681SAndroid Build Coastguard Worker   if (!BT.has(Reg))
1727*9880d681SAndroid Build Coastguard Worker     return false;
1728*9880d681SAndroid Build Coastguard Worker 
1729*9880d681SAndroid Build Coastguard Worker   const BitTracker::RegisterCell &SC = BT.lookup(Reg);
1730*9880d681SAndroid Build Coastguard Worker   if (Pos+16 > SC.width())
1731*9880d681SAndroid Build Coastguard Worker     return false;
1732*9880d681SAndroid Build Coastguard Worker 
1733*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 0; i < 16; ++i) {
1734*9880d681SAndroid Build Coastguard Worker     const BitTracker::BitValue &RV = RC[i+B];
1735*9880d681SAndroid Build Coastguard Worker     if (RV.Type == BitTracker::BitValue::Ref) {
1736*9880d681SAndroid Build Coastguard Worker       if (RV.RefI.Reg != Reg)
1737*9880d681SAndroid Build Coastguard Worker         return false;
1738*9880d681SAndroid Build Coastguard Worker       if (RV.RefI.Pos != i+Pos)
1739*9880d681SAndroid Build Coastguard Worker         return false;
1740*9880d681SAndroid Build Coastguard Worker       continue;
1741*9880d681SAndroid Build Coastguard Worker     }
1742*9880d681SAndroid Build Coastguard Worker     if (RC[i+B] != SC[i+Pos])
1743*9880d681SAndroid Build Coastguard Worker       return false;
1744*9880d681SAndroid Build Coastguard Worker   }
1745*9880d681SAndroid Build Coastguard Worker 
1746*9880d681SAndroid Build Coastguard Worker   unsigned Sub = 0;
1747*9880d681SAndroid Build Coastguard Worker   switch (Pos) {
1748*9880d681SAndroid Build Coastguard Worker     case 0:
1749*9880d681SAndroid Build Coastguard Worker       Sub = Hexagon::subreg_loreg;
1750*9880d681SAndroid Build Coastguard Worker       Low = true;
1751*9880d681SAndroid Build Coastguard Worker       break;
1752*9880d681SAndroid Build Coastguard Worker     case 16:
1753*9880d681SAndroid Build Coastguard Worker       Sub = Hexagon::subreg_loreg;
1754*9880d681SAndroid Build Coastguard Worker       Low = false;
1755*9880d681SAndroid Build Coastguard Worker       break;
1756*9880d681SAndroid Build Coastguard Worker     case 32:
1757*9880d681SAndroid Build Coastguard Worker       Sub = Hexagon::subreg_hireg;
1758*9880d681SAndroid Build Coastguard Worker       Low = true;
1759*9880d681SAndroid Build Coastguard Worker       break;
1760*9880d681SAndroid Build Coastguard Worker     case 48:
1761*9880d681SAndroid Build Coastguard Worker       Sub = Hexagon::subreg_hireg;
1762*9880d681SAndroid Build Coastguard Worker       Low = false;
1763*9880d681SAndroid Build Coastguard Worker       break;
1764*9880d681SAndroid Build Coastguard Worker     default:
1765*9880d681SAndroid Build Coastguard Worker       return false;
1766*9880d681SAndroid Build Coastguard Worker   }
1767*9880d681SAndroid Build Coastguard Worker 
1768*9880d681SAndroid Build Coastguard Worker   RH.Reg = Reg;
1769*9880d681SAndroid Build Coastguard Worker   RH.Sub = Sub;
1770*9880d681SAndroid Build Coastguard Worker   RH.Low = Low;
1771*9880d681SAndroid Build Coastguard Worker   // If the subregister is not valid with the register, set it to 0.
1772*9880d681SAndroid Build Coastguard Worker   if (!HBS::getFinalVRegClass(RH, MRI))
1773*9880d681SAndroid Build Coastguard Worker     RH.Sub = 0;
1774*9880d681SAndroid Build Coastguard Worker 
1775*9880d681SAndroid Build Coastguard Worker   return true;
1776*9880d681SAndroid Build Coastguard Worker }
1777*9880d681SAndroid Build Coastguard Worker 
1778*9880d681SAndroid Build Coastguard Worker 
1779*9880d681SAndroid Build Coastguard Worker // Check if RC matches the pattern of a S2_packhl. If so, return true and
1780*9880d681SAndroid Build Coastguard Worker // set the inputs Rs and Rt.
matchPackhl(unsigned SelfR,const BitTracker::RegisterCell & RC,BitTracker::RegisterRef & Rs,BitTracker::RegisterRef & Rt)1781*9880d681SAndroid Build Coastguard Worker bool BitSimplification::matchPackhl(unsigned SelfR,
1782*9880d681SAndroid Build Coastguard Worker       const BitTracker::RegisterCell &RC, BitTracker::RegisterRef &Rs,
1783*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef &Rt) {
1784*9880d681SAndroid Build Coastguard Worker   RegHalf L1, H1, L2, H2;
1785*9880d681SAndroid Build Coastguard Worker 
1786*9880d681SAndroid Build Coastguard Worker   if (!matchHalf(SelfR, RC, 0, L2)  || !matchHalf(SelfR, RC, 16, L1))
1787*9880d681SAndroid Build Coastguard Worker     return false;
1788*9880d681SAndroid Build Coastguard Worker   if (!matchHalf(SelfR, RC, 32, H2) || !matchHalf(SelfR, RC, 48, H1))
1789*9880d681SAndroid Build Coastguard Worker     return false;
1790*9880d681SAndroid Build Coastguard Worker 
1791*9880d681SAndroid Build Coastguard Worker   // Rs = H1.L1, Rt = H2.L2
1792*9880d681SAndroid Build Coastguard Worker   if (H1.Reg != L1.Reg || H1.Sub != L1.Sub || H1.Low || !L1.Low)
1793*9880d681SAndroid Build Coastguard Worker     return false;
1794*9880d681SAndroid Build Coastguard Worker   if (H2.Reg != L2.Reg || H2.Sub != L2.Sub || H2.Low || !L2.Low)
1795*9880d681SAndroid Build Coastguard Worker     return false;
1796*9880d681SAndroid Build Coastguard Worker 
1797*9880d681SAndroid Build Coastguard Worker   Rs = H1;
1798*9880d681SAndroid Build Coastguard Worker   Rt = H2;
1799*9880d681SAndroid Build Coastguard Worker   return true;
1800*9880d681SAndroid Build Coastguard Worker }
1801*9880d681SAndroid Build Coastguard Worker 
1802*9880d681SAndroid Build Coastguard Worker 
getCombineOpcode(bool HLow,bool LLow)1803*9880d681SAndroid Build Coastguard Worker unsigned BitSimplification::getCombineOpcode(bool HLow, bool LLow) {
1804*9880d681SAndroid Build Coastguard Worker   return HLow ? LLow ? Hexagon::A2_combine_ll
1805*9880d681SAndroid Build Coastguard Worker                      : Hexagon::A2_combine_lh
1806*9880d681SAndroid Build Coastguard Worker               : LLow ? Hexagon::A2_combine_hl
1807*9880d681SAndroid Build Coastguard Worker                      : Hexagon::A2_combine_hh;
1808*9880d681SAndroid Build Coastguard Worker }
1809*9880d681SAndroid Build Coastguard Worker 
1810*9880d681SAndroid Build Coastguard Worker 
1811*9880d681SAndroid Build Coastguard Worker // If MI stores the upper halfword of a register (potentially obtained via
1812*9880d681SAndroid Build Coastguard Worker // shifts or extracts), replace it with a storerf instruction. This could
1813*9880d681SAndroid Build Coastguard Worker // cause the "extraction" code to become dead.
genStoreUpperHalf(MachineInstr * MI)1814*9880d681SAndroid Build Coastguard Worker bool BitSimplification::genStoreUpperHalf(MachineInstr *MI) {
1815*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI->getOpcode();
1816*9880d681SAndroid Build Coastguard Worker   if (Opc != Hexagon::S2_storerh_io)
1817*9880d681SAndroid Build Coastguard Worker     return false;
1818*9880d681SAndroid Build Coastguard Worker 
1819*9880d681SAndroid Build Coastguard Worker   MachineOperand &ValOp = MI->getOperand(2);
1820*9880d681SAndroid Build Coastguard Worker   BitTracker::RegisterRef RS = ValOp;
1821*9880d681SAndroid Build Coastguard Worker   if (!BT.has(RS.Reg))
1822*9880d681SAndroid Build Coastguard Worker     return false;
1823*9880d681SAndroid Build Coastguard Worker   const BitTracker::RegisterCell &RC = BT.lookup(RS.Reg);
1824*9880d681SAndroid Build Coastguard Worker   RegHalf H;
1825*9880d681SAndroid Build Coastguard Worker   if (!matchHalf(0, RC, 0, H))
1826*9880d681SAndroid Build Coastguard Worker     return false;
1827*9880d681SAndroid Build Coastguard Worker   if (H.Low)
1828*9880d681SAndroid Build Coastguard Worker     return false;
1829*9880d681SAndroid Build Coastguard Worker   MI->setDesc(HII.get(Hexagon::S2_storerf_io));
1830*9880d681SAndroid Build Coastguard Worker   ValOp.setReg(H.Reg);
1831*9880d681SAndroid Build Coastguard Worker   ValOp.setSubReg(H.Sub);
1832*9880d681SAndroid Build Coastguard Worker   return true;
1833*9880d681SAndroid Build Coastguard Worker }
1834*9880d681SAndroid Build Coastguard Worker 
1835*9880d681SAndroid Build Coastguard Worker 
1836*9880d681SAndroid Build Coastguard Worker // If MI stores a value known at compile-time, and the value is within a range
1837*9880d681SAndroid Build Coastguard Worker // that avoids using constant-extenders, replace it with a store-immediate.
genStoreImmediate(MachineInstr * MI)1838*9880d681SAndroid Build Coastguard Worker bool BitSimplification::genStoreImmediate(MachineInstr *MI) {
1839*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI->getOpcode();
1840*9880d681SAndroid Build Coastguard Worker   unsigned Align = 0;
1841*9880d681SAndroid Build Coastguard Worker   switch (Opc) {
1842*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_storeri_io:
1843*9880d681SAndroid Build Coastguard Worker       Align++;
1844*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_storerh_io:
1845*9880d681SAndroid Build Coastguard Worker       Align++;
1846*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_storerb_io:
1847*9880d681SAndroid Build Coastguard Worker       break;
1848*9880d681SAndroid Build Coastguard Worker     default:
1849*9880d681SAndroid Build Coastguard Worker       return false;
1850*9880d681SAndroid Build Coastguard Worker   }
1851*9880d681SAndroid Build Coastguard Worker 
1852*9880d681SAndroid Build Coastguard Worker   // Avoid stores to frame-indices (due to an unknown offset).
1853*9880d681SAndroid Build Coastguard Worker   if (!MI->getOperand(0).isReg())
1854*9880d681SAndroid Build Coastguard Worker     return false;
1855*9880d681SAndroid Build Coastguard Worker   MachineOperand &OffOp = MI->getOperand(1);
1856*9880d681SAndroid Build Coastguard Worker   if (!OffOp.isImm())
1857*9880d681SAndroid Build Coastguard Worker     return false;
1858*9880d681SAndroid Build Coastguard Worker 
1859*9880d681SAndroid Build Coastguard Worker   int64_t Off = OffOp.getImm();
1860*9880d681SAndroid Build Coastguard Worker   // Offset is u6:a. Sadly, there is no isShiftedUInt(n,x).
1861*9880d681SAndroid Build Coastguard Worker   if (!isUIntN(6+Align, Off) || (Off & ((1<<Align)-1)))
1862*9880d681SAndroid Build Coastguard Worker     return false;
1863*9880d681SAndroid Build Coastguard Worker   // Source register:
1864*9880d681SAndroid Build Coastguard Worker   BitTracker::RegisterRef RS = MI->getOperand(2);
1865*9880d681SAndroid Build Coastguard Worker   if (!BT.has(RS.Reg))
1866*9880d681SAndroid Build Coastguard Worker     return false;
1867*9880d681SAndroid Build Coastguard Worker   const BitTracker::RegisterCell &RC = BT.lookup(RS.Reg);
1868*9880d681SAndroid Build Coastguard Worker   uint64_t U;
1869*9880d681SAndroid Build Coastguard Worker   if (!HBS::getConst(RC, 0, RC.width(), U))
1870*9880d681SAndroid Build Coastguard Worker     return false;
1871*9880d681SAndroid Build Coastguard Worker 
1872*9880d681SAndroid Build Coastguard Worker   // Only consider 8-bit values to avoid constant-extenders.
1873*9880d681SAndroid Build Coastguard Worker   int V;
1874*9880d681SAndroid Build Coastguard Worker   switch (Opc) {
1875*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_storerb_io:
1876*9880d681SAndroid Build Coastguard Worker       V = int8_t(U);
1877*9880d681SAndroid Build Coastguard Worker       break;
1878*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_storerh_io:
1879*9880d681SAndroid Build Coastguard Worker       V = int16_t(U);
1880*9880d681SAndroid Build Coastguard Worker       break;
1881*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_storeri_io:
1882*9880d681SAndroid Build Coastguard Worker       V = int32_t(U);
1883*9880d681SAndroid Build Coastguard Worker       break;
1884*9880d681SAndroid Build Coastguard Worker   }
1885*9880d681SAndroid Build Coastguard Worker   if (!isInt<8>(V))
1886*9880d681SAndroid Build Coastguard Worker     return false;
1887*9880d681SAndroid Build Coastguard Worker 
1888*9880d681SAndroid Build Coastguard Worker   MI->RemoveOperand(2);
1889*9880d681SAndroid Build Coastguard Worker   switch (Opc) {
1890*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_storerb_io:
1891*9880d681SAndroid Build Coastguard Worker       MI->setDesc(HII.get(Hexagon::S4_storeirb_io));
1892*9880d681SAndroid Build Coastguard Worker       break;
1893*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_storerh_io:
1894*9880d681SAndroid Build Coastguard Worker       MI->setDesc(HII.get(Hexagon::S4_storeirh_io));
1895*9880d681SAndroid Build Coastguard Worker       break;
1896*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_storeri_io:
1897*9880d681SAndroid Build Coastguard Worker       MI->setDesc(HII.get(Hexagon::S4_storeiri_io));
1898*9880d681SAndroid Build Coastguard Worker       break;
1899*9880d681SAndroid Build Coastguard Worker   }
1900*9880d681SAndroid Build Coastguard Worker   MI->addOperand(MachineOperand::CreateImm(V));
1901*9880d681SAndroid Build Coastguard Worker   return true;
1902*9880d681SAndroid Build Coastguard Worker }
1903*9880d681SAndroid Build Coastguard Worker 
1904*9880d681SAndroid Build Coastguard Worker 
1905*9880d681SAndroid Build Coastguard Worker // If MI is equivalent o S2_packhl, generate the S2_packhl. MI could be the
1906*9880d681SAndroid Build Coastguard Worker // last instruction in a sequence that results in something equivalent to
1907*9880d681SAndroid Build Coastguard Worker // the pack-halfwords. The intent is to cause the entire sequence to become
1908*9880d681SAndroid Build Coastguard Worker // dead.
genPackhl(MachineInstr * MI,BitTracker::RegisterRef RD,const BitTracker::RegisterCell & RC)1909*9880d681SAndroid Build Coastguard Worker bool BitSimplification::genPackhl(MachineInstr *MI,
1910*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
1911*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI->getOpcode();
1912*9880d681SAndroid Build Coastguard Worker   if (Opc == Hexagon::S2_packhl)
1913*9880d681SAndroid Build Coastguard Worker     return false;
1914*9880d681SAndroid Build Coastguard Worker   BitTracker::RegisterRef Rs, Rt;
1915*9880d681SAndroid Build Coastguard Worker   if (!matchPackhl(RD.Reg, RC, Rs, Rt))
1916*9880d681SAndroid Build Coastguard Worker     return false;
1917*9880d681SAndroid Build Coastguard Worker 
1918*9880d681SAndroid Build Coastguard Worker   MachineBasicBlock &B = *MI->getParent();
1919*9880d681SAndroid Build Coastguard Worker   unsigned NewR = MRI.createVirtualRegister(&Hexagon::DoubleRegsRegClass);
1920*9880d681SAndroid Build Coastguard Worker   DebugLoc DL = MI->getDebugLoc();
1921*9880d681SAndroid Build Coastguard Worker   auto At = MI->isPHI() ? B.getFirstNonPHI()
1922*9880d681SAndroid Build Coastguard Worker                         : MachineBasicBlock::iterator(MI);
1923*9880d681SAndroid Build Coastguard Worker   BuildMI(B, At, DL, HII.get(Hexagon::S2_packhl), NewR)
1924*9880d681SAndroid Build Coastguard Worker       .addReg(Rs.Reg, 0, Rs.Sub)
1925*9880d681SAndroid Build Coastguard Worker       .addReg(Rt.Reg, 0, Rt.Sub);
1926*9880d681SAndroid Build Coastguard Worker   HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
1927*9880d681SAndroid Build Coastguard Worker   BT.put(BitTracker::RegisterRef(NewR), RC);
1928*9880d681SAndroid Build Coastguard Worker   return true;
1929*9880d681SAndroid Build Coastguard Worker }
1930*9880d681SAndroid Build Coastguard Worker 
1931*9880d681SAndroid Build Coastguard Worker 
1932*9880d681SAndroid Build Coastguard Worker // If MI produces halfword of the input in the low half of the output,
1933*9880d681SAndroid Build Coastguard Worker // replace it with zero-extend or extractu.
genExtractHalf(MachineInstr * MI,BitTracker::RegisterRef RD,const BitTracker::RegisterCell & RC)1934*9880d681SAndroid Build Coastguard Worker bool BitSimplification::genExtractHalf(MachineInstr *MI,
1935*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
1936*9880d681SAndroid Build Coastguard Worker   RegHalf L;
1937*9880d681SAndroid Build Coastguard Worker   // Check for halfword in low 16 bits, zeros elsewhere.
1938*9880d681SAndroid Build Coastguard Worker   if (!matchHalf(RD.Reg, RC, 0, L) || !HBS::isZero(RC, 16, 16))
1939*9880d681SAndroid Build Coastguard Worker     return false;
1940*9880d681SAndroid Build Coastguard Worker 
1941*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI->getOpcode();
1942*9880d681SAndroid Build Coastguard Worker   MachineBasicBlock &B = *MI->getParent();
1943*9880d681SAndroid Build Coastguard Worker   DebugLoc DL = MI->getDebugLoc();
1944*9880d681SAndroid Build Coastguard Worker 
1945*9880d681SAndroid Build Coastguard Worker   // Prefer zxth, since zxth can go in any slot, while extractu only in
1946*9880d681SAndroid Build Coastguard Worker   // slots 2 and 3.
1947*9880d681SAndroid Build Coastguard Worker   unsigned NewR = 0;
1948*9880d681SAndroid Build Coastguard Worker   auto At = MI->isPHI() ? B.getFirstNonPHI()
1949*9880d681SAndroid Build Coastguard Worker                         : MachineBasicBlock::iterator(MI);
1950*9880d681SAndroid Build Coastguard Worker   if (L.Low && Opc != Hexagon::A2_zxth) {
1951*9880d681SAndroid Build Coastguard Worker     NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
1952*9880d681SAndroid Build Coastguard Worker     BuildMI(B, At, DL, HII.get(Hexagon::A2_zxth), NewR)
1953*9880d681SAndroid Build Coastguard Worker         .addReg(L.Reg, 0, L.Sub);
1954*9880d681SAndroid Build Coastguard Worker   } else if (!L.Low && Opc != Hexagon::S2_lsr_i_r) {
1955*9880d681SAndroid Build Coastguard Worker     NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
1956*9880d681SAndroid Build Coastguard Worker     BuildMI(B, MI, DL, HII.get(Hexagon::S2_lsr_i_r), NewR)
1957*9880d681SAndroid Build Coastguard Worker         .addReg(L.Reg, 0, L.Sub)
1958*9880d681SAndroid Build Coastguard Worker         .addImm(16);
1959*9880d681SAndroid Build Coastguard Worker   }
1960*9880d681SAndroid Build Coastguard Worker   if (NewR == 0)
1961*9880d681SAndroid Build Coastguard Worker     return false;
1962*9880d681SAndroid Build Coastguard Worker   HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
1963*9880d681SAndroid Build Coastguard Worker   BT.put(BitTracker::RegisterRef(NewR), RC);
1964*9880d681SAndroid Build Coastguard Worker   return true;
1965*9880d681SAndroid Build Coastguard Worker }
1966*9880d681SAndroid Build Coastguard Worker 
1967*9880d681SAndroid Build Coastguard Worker 
1968*9880d681SAndroid Build Coastguard Worker // If MI is equivalent to a combine(.L/.H, .L/.H) replace with with the
1969*9880d681SAndroid Build Coastguard Worker // combine.
genCombineHalf(MachineInstr * MI,BitTracker::RegisterRef RD,const BitTracker::RegisterCell & RC)1970*9880d681SAndroid Build Coastguard Worker bool BitSimplification::genCombineHalf(MachineInstr *MI,
1971*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
1972*9880d681SAndroid Build Coastguard Worker   RegHalf L, H;
1973*9880d681SAndroid Build Coastguard Worker   // Check for combine h/l
1974*9880d681SAndroid Build Coastguard Worker   if (!matchHalf(RD.Reg, RC, 0, L) || !matchHalf(RD.Reg, RC, 16, H))
1975*9880d681SAndroid Build Coastguard Worker     return false;
1976*9880d681SAndroid Build Coastguard Worker   // Do nothing if this is just a reg copy.
1977*9880d681SAndroid Build Coastguard Worker   if (L.Reg == H.Reg && L.Sub == H.Sub && !H.Low && L.Low)
1978*9880d681SAndroid Build Coastguard Worker     return false;
1979*9880d681SAndroid Build Coastguard Worker 
1980*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI->getOpcode();
1981*9880d681SAndroid Build Coastguard Worker   unsigned COpc = getCombineOpcode(H.Low, L.Low);
1982*9880d681SAndroid Build Coastguard Worker   if (COpc == Opc)
1983*9880d681SAndroid Build Coastguard Worker     return false;
1984*9880d681SAndroid Build Coastguard Worker 
1985*9880d681SAndroid Build Coastguard Worker   MachineBasicBlock &B = *MI->getParent();
1986*9880d681SAndroid Build Coastguard Worker   DebugLoc DL = MI->getDebugLoc();
1987*9880d681SAndroid Build Coastguard Worker   unsigned NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
1988*9880d681SAndroid Build Coastguard Worker   auto At = MI->isPHI() ? B.getFirstNonPHI()
1989*9880d681SAndroid Build Coastguard Worker                         : MachineBasicBlock::iterator(MI);
1990*9880d681SAndroid Build Coastguard Worker   BuildMI(B, At, DL, HII.get(COpc), NewR)
1991*9880d681SAndroid Build Coastguard Worker       .addReg(H.Reg, 0, H.Sub)
1992*9880d681SAndroid Build Coastguard Worker       .addReg(L.Reg, 0, L.Sub);
1993*9880d681SAndroid Build Coastguard Worker   HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
1994*9880d681SAndroid Build Coastguard Worker   BT.put(BitTracker::RegisterRef(NewR), RC);
1995*9880d681SAndroid Build Coastguard Worker   return true;
1996*9880d681SAndroid Build Coastguard Worker }
1997*9880d681SAndroid Build Coastguard Worker 
1998*9880d681SAndroid Build Coastguard Worker 
1999*9880d681SAndroid Build Coastguard Worker // If MI resets high bits of a register and keeps the lower ones, replace it
2000*9880d681SAndroid Build Coastguard Worker // with zero-extend byte/half, and-immediate, or extractu, as appropriate.
genExtractLow(MachineInstr * MI,BitTracker::RegisterRef RD,const BitTracker::RegisterCell & RC)2001*9880d681SAndroid Build Coastguard Worker bool BitSimplification::genExtractLow(MachineInstr *MI,
2002*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2003*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI->getOpcode();
2004*9880d681SAndroid Build Coastguard Worker   switch (Opc) {
2005*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_zxtb:
2006*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_zxth:
2007*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_extractu:
2008*9880d681SAndroid Build Coastguard Worker       return false;
2009*9880d681SAndroid Build Coastguard Worker   }
2010*9880d681SAndroid Build Coastguard Worker   if (Opc == Hexagon::A2_andir && MI->getOperand(2).isImm()) {
2011*9880d681SAndroid Build Coastguard Worker     int32_t Imm = MI->getOperand(2).getImm();
2012*9880d681SAndroid Build Coastguard Worker     if (isInt<10>(Imm))
2013*9880d681SAndroid Build Coastguard Worker       return false;
2014*9880d681SAndroid Build Coastguard Worker   }
2015*9880d681SAndroid Build Coastguard Worker 
2016*9880d681SAndroid Build Coastguard Worker   if (MI->hasUnmodeledSideEffects() || MI->isInlineAsm())
2017*9880d681SAndroid Build Coastguard Worker     return false;
2018*9880d681SAndroid Build Coastguard Worker   unsigned W = RC.width();
2019*9880d681SAndroid Build Coastguard Worker   while (W > 0 && RC[W-1].is(0))
2020*9880d681SAndroid Build Coastguard Worker     W--;
2021*9880d681SAndroid Build Coastguard Worker   if (W == 0 || W == RC.width())
2022*9880d681SAndroid Build Coastguard Worker     return false;
2023*9880d681SAndroid Build Coastguard Worker   unsigned NewOpc = (W == 8)  ? Hexagon::A2_zxtb
2024*9880d681SAndroid Build Coastguard Worker                   : (W == 16) ? Hexagon::A2_zxth
2025*9880d681SAndroid Build Coastguard Worker                   : (W < 10)  ? Hexagon::A2_andir
2026*9880d681SAndroid Build Coastguard Worker                   : Hexagon::S2_extractu;
2027*9880d681SAndroid Build Coastguard Worker   MachineBasicBlock &B = *MI->getParent();
2028*9880d681SAndroid Build Coastguard Worker   DebugLoc DL = MI->getDebugLoc();
2029*9880d681SAndroid Build Coastguard Worker 
2030*9880d681SAndroid Build Coastguard Worker   for (auto &Op : MI->uses()) {
2031*9880d681SAndroid Build Coastguard Worker     if (!Op.isReg())
2032*9880d681SAndroid Build Coastguard Worker       continue;
2033*9880d681SAndroid Build Coastguard Worker     BitTracker::RegisterRef RS = Op;
2034*9880d681SAndroid Build Coastguard Worker     if (!BT.has(RS.Reg))
2035*9880d681SAndroid Build Coastguard Worker       continue;
2036*9880d681SAndroid Build Coastguard Worker     const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
2037*9880d681SAndroid Build Coastguard Worker     unsigned BN, BW;
2038*9880d681SAndroid Build Coastguard Worker     if (!HBS::getSubregMask(RS, BN, BW, MRI))
2039*9880d681SAndroid Build Coastguard Worker       continue;
2040*9880d681SAndroid Build Coastguard Worker     if (BW < W || !HBS::isEqual(RC, 0, SC, BN, W))
2041*9880d681SAndroid Build Coastguard Worker       continue;
2042*9880d681SAndroid Build Coastguard Worker 
2043*9880d681SAndroid Build Coastguard Worker     unsigned NewR = MRI.createVirtualRegister(&Hexagon::IntRegsRegClass);
2044*9880d681SAndroid Build Coastguard Worker     auto At = MI->isPHI() ? B.getFirstNonPHI()
2045*9880d681SAndroid Build Coastguard Worker                           : MachineBasicBlock::iterator(MI);
2046*9880d681SAndroid Build Coastguard Worker     auto MIB = BuildMI(B, At, DL, HII.get(NewOpc), NewR)
2047*9880d681SAndroid Build Coastguard Worker                   .addReg(RS.Reg, 0, RS.Sub);
2048*9880d681SAndroid Build Coastguard Worker     if (NewOpc == Hexagon::A2_andir)
2049*9880d681SAndroid Build Coastguard Worker       MIB.addImm((1 << W) - 1);
2050*9880d681SAndroid Build Coastguard Worker     else if (NewOpc == Hexagon::S2_extractu)
2051*9880d681SAndroid Build Coastguard Worker       MIB.addImm(W).addImm(0);
2052*9880d681SAndroid Build Coastguard Worker     HBS::replaceSubWithSub(RD.Reg, RD.Sub, NewR, 0, MRI);
2053*9880d681SAndroid Build Coastguard Worker     BT.put(BitTracker::RegisterRef(NewR), RC);
2054*9880d681SAndroid Build Coastguard Worker     return true;
2055*9880d681SAndroid Build Coastguard Worker   }
2056*9880d681SAndroid Build Coastguard Worker   return false;
2057*9880d681SAndroid Build Coastguard Worker }
2058*9880d681SAndroid Build Coastguard Worker 
2059*9880d681SAndroid Build Coastguard Worker 
2060*9880d681SAndroid Build Coastguard Worker // Check for tstbit simplification opportunity, where the bit being checked
2061*9880d681SAndroid Build Coastguard Worker // can be tracked back to another register. For example:
2062*9880d681SAndroid Build Coastguard Worker //   vreg2 = S2_lsr_i_r  vreg1, 5
2063*9880d681SAndroid Build Coastguard Worker //   vreg3 = S2_tstbit_i vreg2, 0
2064*9880d681SAndroid Build Coastguard Worker // =>
2065*9880d681SAndroid Build Coastguard Worker //   vreg3 = S2_tstbit_i vreg1, 5
simplifyTstbit(MachineInstr * MI,BitTracker::RegisterRef RD,const BitTracker::RegisterCell & RC)2066*9880d681SAndroid Build Coastguard Worker bool BitSimplification::simplifyTstbit(MachineInstr *MI,
2067*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef RD, const BitTracker::RegisterCell &RC) {
2068*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI->getOpcode();
2069*9880d681SAndroid Build Coastguard Worker   if (Opc != Hexagon::S2_tstbit_i)
2070*9880d681SAndroid Build Coastguard Worker     return false;
2071*9880d681SAndroid Build Coastguard Worker 
2072*9880d681SAndroid Build Coastguard Worker   unsigned BN = MI->getOperand(2).getImm();
2073*9880d681SAndroid Build Coastguard Worker   BitTracker::RegisterRef RS = MI->getOperand(1);
2074*9880d681SAndroid Build Coastguard Worker   unsigned F, W;
2075*9880d681SAndroid Build Coastguard Worker   DebugLoc DL = MI->getDebugLoc();
2076*9880d681SAndroid Build Coastguard Worker   if (!BT.has(RS.Reg) || !HBS::getSubregMask(RS, F, W, MRI))
2077*9880d681SAndroid Build Coastguard Worker     return false;
2078*9880d681SAndroid Build Coastguard Worker   MachineBasicBlock &B = *MI->getParent();
2079*9880d681SAndroid Build Coastguard Worker   auto At = MI->isPHI() ? B.getFirstNonPHI()
2080*9880d681SAndroid Build Coastguard Worker                         : MachineBasicBlock::iterator(MI);
2081*9880d681SAndroid Build Coastguard Worker 
2082*9880d681SAndroid Build Coastguard Worker   const BitTracker::RegisterCell &SC = BT.lookup(RS.Reg);
2083*9880d681SAndroid Build Coastguard Worker   const BitTracker::BitValue &V = SC[F+BN];
2084*9880d681SAndroid Build Coastguard Worker   if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg != RS.Reg) {
2085*9880d681SAndroid Build Coastguard Worker     const TargetRegisterClass *TC = MRI.getRegClass(V.RefI.Reg);
2086*9880d681SAndroid Build Coastguard Worker     // Need to map V.RefI.Reg to a 32-bit register, i.e. if it is
2087*9880d681SAndroid Build Coastguard Worker     // a double register, need to use a subregister and adjust bit
2088*9880d681SAndroid Build Coastguard Worker     // number.
2089*9880d681SAndroid Build Coastguard Worker     unsigned P = UINT_MAX;
2090*9880d681SAndroid Build Coastguard Worker     BitTracker::RegisterRef RR(V.RefI.Reg, 0);
2091*9880d681SAndroid Build Coastguard Worker     if (TC == &Hexagon::DoubleRegsRegClass) {
2092*9880d681SAndroid Build Coastguard Worker       P = V.RefI.Pos;
2093*9880d681SAndroid Build Coastguard Worker       RR.Sub = Hexagon::subreg_loreg;
2094*9880d681SAndroid Build Coastguard Worker       if (P >= 32) {
2095*9880d681SAndroid Build Coastguard Worker         P -= 32;
2096*9880d681SAndroid Build Coastguard Worker         RR.Sub = Hexagon::subreg_hireg;
2097*9880d681SAndroid Build Coastguard Worker       }
2098*9880d681SAndroid Build Coastguard Worker     } else if (TC == &Hexagon::IntRegsRegClass) {
2099*9880d681SAndroid Build Coastguard Worker       P = V.RefI.Pos;
2100*9880d681SAndroid Build Coastguard Worker     }
2101*9880d681SAndroid Build Coastguard Worker     if (P != UINT_MAX) {
2102*9880d681SAndroid Build Coastguard Worker       unsigned NewR = MRI.createVirtualRegister(&Hexagon::PredRegsRegClass);
2103*9880d681SAndroid Build Coastguard Worker       BuildMI(B, At, DL, HII.get(Hexagon::S2_tstbit_i), NewR)
2104*9880d681SAndroid Build Coastguard Worker           .addReg(RR.Reg, 0, RR.Sub)
2105*9880d681SAndroid Build Coastguard Worker           .addImm(P);
2106*9880d681SAndroid Build Coastguard Worker       HBS::replaceReg(RD.Reg, NewR, MRI);
2107*9880d681SAndroid Build Coastguard Worker       BT.put(NewR, RC);
2108*9880d681SAndroid Build Coastguard Worker       return true;
2109*9880d681SAndroid Build Coastguard Worker     }
2110*9880d681SAndroid Build Coastguard Worker   } else if (V.is(0) || V.is(1)) {
2111*9880d681SAndroid Build Coastguard Worker     unsigned NewR = MRI.createVirtualRegister(&Hexagon::PredRegsRegClass);
2112*9880d681SAndroid Build Coastguard Worker     unsigned NewOpc = V.is(0) ? Hexagon::TFR_PdFalse : Hexagon::TFR_PdTrue;
2113*9880d681SAndroid Build Coastguard Worker     BuildMI(B, At, DL, HII.get(NewOpc), NewR);
2114*9880d681SAndroid Build Coastguard Worker     HBS::replaceReg(RD.Reg, NewR, MRI);
2115*9880d681SAndroid Build Coastguard Worker     return true;
2116*9880d681SAndroid Build Coastguard Worker   }
2117*9880d681SAndroid Build Coastguard Worker 
2118*9880d681SAndroid Build Coastguard Worker   return false;
2119*9880d681SAndroid Build Coastguard Worker }
2120*9880d681SAndroid Build Coastguard Worker 
2121*9880d681SAndroid Build Coastguard Worker 
processBlock(MachineBasicBlock & B,const RegisterSet & AVs)2122*9880d681SAndroid Build Coastguard Worker bool BitSimplification::processBlock(MachineBasicBlock &B,
2123*9880d681SAndroid Build Coastguard Worker       const RegisterSet &AVs) {
2124*9880d681SAndroid Build Coastguard Worker   bool Changed = false;
2125*9880d681SAndroid Build Coastguard Worker   RegisterSet AVB = AVs;
2126*9880d681SAndroid Build Coastguard Worker   RegisterSet Defs;
2127*9880d681SAndroid Build Coastguard Worker 
2128*9880d681SAndroid Build Coastguard Worker   for (auto I = B.begin(), E = B.end(); I != E; ++I, AVB.insert(Defs)) {
2129*9880d681SAndroid Build Coastguard Worker     MachineInstr *MI = &*I;
2130*9880d681SAndroid Build Coastguard Worker     Defs.clear();
2131*9880d681SAndroid Build Coastguard Worker     HBS::getInstrDefs(*MI, Defs);
2132*9880d681SAndroid Build Coastguard Worker 
2133*9880d681SAndroid Build Coastguard Worker     unsigned Opc = MI->getOpcode();
2134*9880d681SAndroid Build Coastguard Worker     if (Opc == TargetOpcode::COPY || Opc == TargetOpcode::REG_SEQUENCE)
2135*9880d681SAndroid Build Coastguard Worker       continue;
2136*9880d681SAndroid Build Coastguard Worker 
2137*9880d681SAndroid Build Coastguard Worker     if (MI->mayStore()) {
2138*9880d681SAndroid Build Coastguard Worker       bool T = genStoreUpperHalf(MI);
2139*9880d681SAndroid Build Coastguard Worker       T = T || genStoreImmediate(MI);
2140*9880d681SAndroid Build Coastguard Worker       Changed |= T;
2141*9880d681SAndroid Build Coastguard Worker       continue;
2142*9880d681SAndroid Build Coastguard Worker     }
2143*9880d681SAndroid Build Coastguard Worker 
2144*9880d681SAndroid Build Coastguard Worker     if (Defs.count() != 1)
2145*9880d681SAndroid Build Coastguard Worker       continue;
2146*9880d681SAndroid Build Coastguard Worker     const MachineOperand &Op0 = MI->getOperand(0);
2147*9880d681SAndroid Build Coastguard Worker     if (!Op0.isReg() || !Op0.isDef())
2148*9880d681SAndroid Build Coastguard Worker       continue;
2149*9880d681SAndroid Build Coastguard Worker     BitTracker::RegisterRef RD = Op0;
2150*9880d681SAndroid Build Coastguard Worker     if (!BT.has(RD.Reg))
2151*9880d681SAndroid Build Coastguard Worker       continue;
2152*9880d681SAndroid Build Coastguard Worker     const TargetRegisterClass *FRC = HBS::getFinalVRegClass(RD, MRI);
2153*9880d681SAndroid Build Coastguard Worker     const BitTracker::RegisterCell &RC = BT.lookup(RD.Reg);
2154*9880d681SAndroid Build Coastguard Worker 
2155*9880d681SAndroid Build Coastguard Worker     if (FRC->getID() == Hexagon::DoubleRegsRegClassID) {
2156*9880d681SAndroid Build Coastguard Worker       bool T = genPackhl(MI, RD, RC);
2157*9880d681SAndroid Build Coastguard Worker       Changed |= T;
2158*9880d681SAndroid Build Coastguard Worker       continue;
2159*9880d681SAndroid Build Coastguard Worker     }
2160*9880d681SAndroid Build Coastguard Worker 
2161*9880d681SAndroid Build Coastguard Worker     if (FRC->getID() == Hexagon::IntRegsRegClassID) {
2162*9880d681SAndroid Build Coastguard Worker       bool T = genExtractHalf(MI, RD, RC);
2163*9880d681SAndroid Build Coastguard Worker       T = T || genCombineHalf(MI, RD, RC);
2164*9880d681SAndroid Build Coastguard Worker       T = T || genExtractLow(MI, RD, RC);
2165*9880d681SAndroid Build Coastguard Worker       Changed |= T;
2166*9880d681SAndroid Build Coastguard Worker       continue;
2167*9880d681SAndroid Build Coastguard Worker     }
2168*9880d681SAndroid Build Coastguard Worker 
2169*9880d681SAndroid Build Coastguard Worker     if (FRC->getID() == Hexagon::PredRegsRegClassID) {
2170*9880d681SAndroid Build Coastguard Worker       bool T = simplifyTstbit(MI, RD, RC);
2171*9880d681SAndroid Build Coastguard Worker       Changed |= T;
2172*9880d681SAndroid Build Coastguard Worker       continue;
2173*9880d681SAndroid Build Coastguard Worker     }
2174*9880d681SAndroid Build Coastguard Worker   }
2175*9880d681SAndroid Build Coastguard Worker   return Changed;
2176*9880d681SAndroid Build Coastguard Worker }
2177*9880d681SAndroid Build Coastguard Worker 
2178*9880d681SAndroid Build Coastguard Worker 
runOnMachineFunction(MachineFunction & MF)2179*9880d681SAndroid Build Coastguard Worker bool HexagonBitSimplify::runOnMachineFunction(MachineFunction &MF) {
2180*9880d681SAndroid Build Coastguard Worker   if (skipFunction(*MF.getFunction()))
2181*9880d681SAndroid Build Coastguard Worker     return false;
2182*9880d681SAndroid Build Coastguard Worker 
2183*9880d681SAndroid Build Coastguard Worker   auto &HST = MF.getSubtarget<HexagonSubtarget>();
2184*9880d681SAndroid Build Coastguard Worker   auto &HRI = *HST.getRegisterInfo();
2185*9880d681SAndroid Build Coastguard Worker   auto &HII = *HST.getInstrInfo();
2186*9880d681SAndroid Build Coastguard Worker 
2187*9880d681SAndroid Build Coastguard Worker   MDT = &getAnalysis<MachineDominatorTree>();
2188*9880d681SAndroid Build Coastguard Worker   MachineRegisterInfo &MRI = MF.getRegInfo();
2189*9880d681SAndroid Build Coastguard Worker   bool Changed;
2190*9880d681SAndroid Build Coastguard Worker 
2191*9880d681SAndroid Build Coastguard Worker   Changed = DeadCodeElimination(MF, *MDT).run();
2192*9880d681SAndroid Build Coastguard Worker 
2193*9880d681SAndroid Build Coastguard Worker   const HexagonEvaluator HE(HRI, MRI, HII, MF);
2194*9880d681SAndroid Build Coastguard Worker   BitTracker BT(HE, MF);
2195*9880d681SAndroid Build Coastguard Worker   DEBUG(BT.trace(true));
2196*9880d681SAndroid Build Coastguard Worker   BT.run();
2197*9880d681SAndroid Build Coastguard Worker 
2198*9880d681SAndroid Build Coastguard Worker   MachineBasicBlock &Entry = MF.front();
2199*9880d681SAndroid Build Coastguard Worker 
2200*9880d681SAndroid Build Coastguard Worker   RegisterSet AIG;  // Available registers for IG.
2201*9880d681SAndroid Build Coastguard Worker   ConstGeneration ImmG(BT, HII, MRI);
2202*9880d681SAndroid Build Coastguard Worker   Changed |= visitBlock(Entry, ImmG, AIG);
2203*9880d681SAndroid Build Coastguard Worker 
2204*9880d681SAndroid Build Coastguard Worker   RegisterSet ARE;  // Available registers for RIE.
2205*9880d681SAndroid Build Coastguard Worker   RedundantInstrElimination RIE(BT, HII, MRI);
2206*9880d681SAndroid Build Coastguard Worker   Changed |= visitBlock(Entry, RIE, ARE);
2207*9880d681SAndroid Build Coastguard Worker 
2208*9880d681SAndroid Build Coastguard Worker   RegisterSet ACG;  // Available registers for CG.
2209*9880d681SAndroid Build Coastguard Worker   CopyGeneration CopyG(BT, HII, MRI);
2210*9880d681SAndroid Build Coastguard Worker   Changed |= visitBlock(Entry, CopyG, ACG);
2211*9880d681SAndroid Build Coastguard Worker 
2212*9880d681SAndroid Build Coastguard Worker   RegisterSet ACP;  // Available registers for CP.
2213*9880d681SAndroid Build Coastguard Worker   CopyPropagation CopyP(HRI, MRI);
2214*9880d681SAndroid Build Coastguard Worker   Changed |= visitBlock(Entry, CopyP, ACP);
2215*9880d681SAndroid Build Coastguard Worker 
2216*9880d681SAndroid Build Coastguard Worker   Changed = DeadCodeElimination(MF, *MDT).run() || Changed;
2217*9880d681SAndroid Build Coastguard Worker 
2218*9880d681SAndroid Build Coastguard Worker   BT.run();
2219*9880d681SAndroid Build Coastguard Worker   RegisterSet ABS;  // Available registers for BS.
2220*9880d681SAndroid Build Coastguard Worker   BitSimplification BitS(BT, HII, MRI);
2221*9880d681SAndroid Build Coastguard Worker   Changed |= visitBlock(Entry, BitS, ABS);
2222*9880d681SAndroid Build Coastguard Worker 
2223*9880d681SAndroid Build Coastguard Worker   Changed = DeadCodeElimination(MF, *MDT).run() || Changed;
2224*9880d681SAndroid Build Coastguard Worker 
2225*9880d681SAndroid Build Coastguard Worker   if (Changed) {
2226*9880d681SAndroid Build Coastguard Worker     for (auto &B : MF)
2227*9880d681SAndroid Build Coastguard Worker       for (auto &I : B)
2228*9880d681SAndroid Build Coastguard Worker         I.clearKillInfo();
2229*9880d681SAndroid Build Coastguard Worker     DeadCodeElimination(MF, *MDT).run();
2230*9880d681SAndroid Build Coastguard Worker   }
2231*9880d681SAndroid Build Coastguard Worker   return Changed;
2232*9880d681SAndroid Build Coastguard Worker }
2233*9880d681SAndroid Build Coastguard Worker 
2234*9880d681SAndroid Build Coastguard Worker 
2235*9880d681SAndroid Build Coastguard Worker // Recognize loops where the code at the end of the loop matches the code
2236*9880d681SAndroid Build Coastguard Worker // before the entry of the loop, and the matching code is such that is can
2237*9880d681SAndroid Build Coastguard Worker // be simplified. This pass relies on the bit simplification above and only
2238*9880d681SAndroid Build Coastguard Worker // prepares code in a way that can be handled by the bit simplifcation.
2239*9880d681SAndroid Build Coastguard Worker //
2240*9880d681SAndroid Build Coastguard Worker // This is the motivating testcase (and explanation):
2241*9880d681SAndroid Build Coastguard Worker //
2242*9880d681SAndroid Build Coastguard Worker // {
2243*9880d681SAndroid Build Coastguard Worker //   loop0(.LBB0_2, r1)      // %for.body.preheader
2244*9880d681SAndroid Build Coastguard Worker //   r5:4 = memd(r0++#8)
2245*9880d681SAndroid Build Coastguard Worker // }
2246*9880d681SAndroid Build Coastguard Worker // {
2247*9880d681SAndroid Build Coastguard Worker //   r3 = lsr(r4, #16)
2248*9880d681SAndroid Build Coastguard Worker //   r7:6 = combine(r5, r5)
2249*9880d681SAndroid Build Coastguard Worker // }
2250*9880d681SAndroid Build Coastguard Worker // {
2251*9880d681SAndroid Build Coastguard Worker //   r3 = insert(r5, #16, #16)
2252*9880d681SAndroid Build Coastguard Worker //   r7:6 = vlsrw(r7:6, #16)
2253*9880d681SAndroid Build Coastguard Worker // }
2254*9880d681SAndroid Build Coastguard Worker // .LBB0_2:
2255*9880d681SAndroid Build Coastguard Worker // {
2256*9880d681SAndroid Build Coastguard Worker //   memh(r2+#4) = r5
2257*9880d681SAndroid Build Coastguard Worker //   memh(r2+#6) = r6            # R6 is really R5.H
2258*9880d681SAndroid Build Coastguard Worker // }
2259*9880d681SAndroid Build Coastguard Worker // {
2260*9880d681SAndroid Build Coastguard Worker //   r2 = add(r2, #8)
2261*9880d681SAndroid Build Coastguard Worker //   memh(r2+#0) = r4
2262*9880d681SAndroid Build Coastguard Worker //   memh(r2+#2) = r3            # R3 is really R4.H
2263*9880d681SAndroid Build Coastguard Worker // }
2264*9880d681SAndroid Build Coastguard Worker // {
2265*9880d681SAndroid Build Coastguard Worker //   r5:4 = memd(r0++#8)
2266*9880d681SAndroid Build Coastguard Worker // }
2267*9880d681SAndroid Build Coastguard Worker // {                             # "Shuffling" code that sets up R3 and R6
2268*9880d681SAndroid Build Coastguard Worker //   r3 = lsr(r4, #16)           # so that their halves can be stored in the
2269*9880d681SAndroid Build Coastguard Worker //   r7:6 = combine(r5, r5)      # next iteration. This could be folded into
2270*9880d681SAndroid Build Coastguard Worker // }                             # the stores if the code was at the beginning
2271*9880d681SAndroid Build Coastguard Worker // {                             # of the loop iteration. Since the same code
2272*9880d681SAndroid Build Coastguard Worker //   r3 = insert(r5, #16, #16)   # precedes the loop, it can actually be moved
2273*9880d681SAndroid Build Coastguard Worker //   r7:6 = vlsrw(r7:6, #16)     # there.
2274*9880d681SAndroid Build Coastguard Worker // }:endloop0
2275*9880d681SAndroid Build Coastguard Worker //
2276*9880d681SAndroid Build Coastguard Worker //
2277*9880d681SAndroid Build Coastguard Worker // The outcome:
2278*9880d681SAndroid Build Coastguard Worker //
2279*9880d681SAndroid Build Coastguard Worker // {
2280*9880d681SAndroid Build Coastguard Worker //   loop0(.LBB0_2, r1)
2281*9880d681SAndroid Build Coastguard Worker //   r5:4 = memd(r0++#8)
2282*9880d681SAndroid Build Coastguard Worker // }
2283*9880d681SAndroid Build Coastguard Worker // .LBB0_2:
2284*9880d681SAndroid Build Coastguard Worker // {
2285*9880d681SAndroid Build Coastguard Worker //   memh(r2+#4) = r5
2286*9880d681SAndroid Build Coastguard Worker //   memh(r2+#6) = r5.h
2287*9880d681SAndroid Build Coastguard Worker // }
2288*9880d681SAndroid Build Coastguard Worker // {
2289*9880d681SAndroid Build Coastguard Worker //   r2 = add(r2, #8)
2290*9880d681SAndroid Build Coastguard Worker //   memh(r2+#0) = r4
2291*9880d681SAndroid Build Coastguard Worker //   memh(r2+#2) = r4.h
2292*9880d681SAndroid Build Coastguard Worker // }
2293*9880d681SAndroid Build Coastguard Worker // {
2294*9880d681SAndroid Build Coastguard Worker //   r5:4 = memd(r0++#8)
2295*9880d681SAndroid Build Coastguard Worker // }:endloop0
2296*9880d681SAndroid Build Coastguard Worker 
2297*9880d681SAndroid Build Coastguard Worker namespace llvm {
2298*9880d681SAndroid Build Coastguard Worker   FunctionPass *createHexagonLoopRescheduling();
2299*9880d681SAndroid Build Coastguard Worker   void initializeHexagonLoopReschedulingPass(PassRegistry&);
2300*9880d681SAndroid Build Coastguard Worker }
2301*9880d681SAndroid Build Coastguard Worker 
2302*9880d681SAndroid Build Coastguard Worker namespace {
2303*9880d681SAndroid Build Coastguard Worker   class HexagonLoopRescheduling : public MachineFunctionPass {
2304*9880d681SAndroid Build Coastguard Worker   public:
2305*9880d681SAndroid Build Coastguard Worker     static char ID;
HexagonLoopRescheduling()2306*9880d681SAndroid Build Coastguard Worker     HexagonLoopRescheduling() : MachineFunctionPass(ID),
2307*9880d681SAndroid Build Coastguard Worker         HII(0), HRI(0), MRI(0), BTP(0) {
2308*9880d681SAndroid Build Coastguard Worker       initializeHexagonLoopReschedulingPass(*PassRegistry::getPassRegistry());
2309*9880d681SAndroid Build Coastguard Worker     }
2310*9880d681SAndroid Build Coastguard Worker 
2311*9880d681SAndroid Build Coastguard Worker     bool runOnMachineFunction(MachineFunction &MF) override;
2312*9880d681SAndroid Build Coastguard Worker 
2313*9880d681SAndroid Build Coastguard Worker   private:
2314*9880d681SAndroid Build Coastguard Worker     const HexagonInstrInfo *HII;
2315*9880d681SAndroid Build Coastguard Worker     const HexagonRegisterInfo *HRI;
2316*9880d681SAndroid Build Coastguard Worker     MachineRegisterInfo *MRI;
2317*9880d681SAndroid Build Coastguard Worker     BitTracker *BTP;
2318*9880d681SAndroid Build Coastguard Worker 
2319*9880d681SAndroid Build Coastguard Worker     struct LoopCand {
LoopCand__anonb78d304d0911::HexagonLoopRescheduling::LoopCand2320*9880d681SAndroid Build Coastguard Worker       LoopCand(MachineBasicBlock *lb, MachineBasicBlock *pb,
2321*9880d681SAndroid Build Coastguard Worker             MachineBasicBlock *eb) : LB(lb), PB(pb), EB(eb) {}
2322*9880d681SAndroid Build Coastguard Worker       MachineBasicBlock *LB, *PB, *EB;
2323*9880d681SAndroid Build Coastguard Worker     };
2324*9880d681SAndroid Build Coastguard Worker     typedef std::vector<MachineInstr*> InstrList;
2325*9880d681SAndroid Build Coastguard Worker     struct InstrGroup {
2326*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef Inp, Out;
2327*9880d681SAndroid Build Coastguard Worker       InstrList Ins;
2328*9880d681SAndroid Build Coastguard Worker     };
2329*9880d681SAndroid Build Coastguard Worker     struct PhiInfo {
2330*9880d681SAndroid Build Coastguard Worker       PhiInfo(MachineInstr &P, MachineBasicBlock &B);
2331*9880d681SAndroid Build Coastguard Worker       unsigned DefR;
2332*9880d681SAndroid Build Coastguard Worker       BitTracker::RegisterRef LR, PR;
2333*9880d681SAndroid Build Coastguard Worker       MachineBasicBlock *LB, *PB;
2334*9880d681SAndroid Build Coastguard Worker     };
2335*9880d681SAndroid Build Coastguard Worker 
2336*9880d681SAndroid Build Coastguard Worker     static unsigned getDefReg(const MachineInstr *MI);
2337*9880d681SAndroid Build Coastguard Worker     bool isConst(unsigned Reg) const;
2338*9880d681SAndroid Build Coastguard Worker     bool isBitShuffle(const MachineInstr *MI, unsigned DefR) const;
2339*9880d681SAndroid Build Coastguard Worker     bool isStoreInput(const MachineInstr *MI, unsigned DefR) const;
2340*9880d681SAndroid Build Coastguard Worker     bool isShuffleOf(unsigned OutR, unsigned InpR) const;
2341*9880d681SAndroid Build Coastguard Worker     bool isSameShuffle(unsigned OutR1, unsigned InpR1, unsigned OutR2,
2342*9880d681SAndroid Build Coastguard Worker         unsigned &InpR2) const;
2343*9880d681SAndroid Build Coastguard Worker     void moveGroup(InstrGroup &G, MachineBasicBlock &LB, MachineBasicBlock &PB,
2344*9880d681SAndroid Build Coastguard Worker         MachineBasicBlock::iterator At, unsigned OldPhiR, unsigned NewPredR);
2345*9880d681SAndroid Build Coastguard Worker     bool processLoop(LoopCand &C);
2346*9880d681SAndroid Build Coastguard Worker   };
2347*9880d681SAndroid Build Coastguard Worker }
2348*9880d681SAndroid Build Coastguard Worker 
2349*9880d681SAndroid Build Coastguard Worker char HexagonLoopRescheduling::ID = 0;
2350*9880d681SAndroid Build Coastguard Worker 
2351*9880d681SAndroid Build Coastguard Worker INITIALIZE_PASS(HexagonLoopRescheduling, "hexagon-loop-resched",
2352*9880d681SAndroid Build Coastguard Worker   "Hexagon Loop Rescheduling", false, false)
2353*9880d681SAndroid Build Coastguard Worker 
2354*9880d681SAndroid Build Coastguard Worker 
PhiInfo(MachineInstr & P,MachineBasicBlock & B)2355*9880d681SAndroid Build Coastguard Worker HexagonLoopRescheduling::PhiInfo::PhiInfo(MachineInstr &P,
2356*9880d681SAndroid Build Coastguard Worker       MachineBasicBlock &B) {
2357*9880d681SAndroid Build Coastguard Worker   DefR = HexagonLoopRescheduling::getDefReg(&P);
2358*9880d681SAndroid Build Coastguard Worker   LB = &B;
2359*9880d681SAndroid Build Coastguard Worker   PB = nullptr;
2360*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 1, n = P.getNumOperands(); i < n; i += 2) {
2361*9880d681SAndroid Build Coastguard Worker     const MachineOperand &OpB = P.getOperand(i+1);
2362*9880d681SAndroid Build Coastguard Worker     if (OpB.getMBB() == &B) {
2363*9880d681SAndroid Build Coastguard Worker       LR = P.getOperand(i);
2364*9880d681SAndroid Build Coastguard Worker       continue;
2365*9880d681SAndroid Build Coastguard Worker     }
2366*9880d681SAndroid Build Coastguard Worker     PB = OpB.getMBB();
2367*9880d681SAndroid Build Coastguard Worker     PR = P.getOperand(i);
2368*9880d681SAndroid Build Coastguard Worker   }
2369*9880d681SAndroid Build Coastguard Worker }
2370*9880d681SAndroid Build Coastguard Worker 
2371*9880d681SAndroid Build Coastguard Worker 
getDefReg(const MachineInstr * MI)2372*9880d681SAndroid Build Coastguard Worker unsigned HexagonLoopRescheduling::getDefReg(const MachineInstr *MI) {
2373*9880d681SAndroid Build Coastguard Worker   RegisterSet Defs;
2374*9880d681SAndroid Build Coastguard Worker   HBS::getInstrDefs(*MI, Defs);
2375*9880d681SAndroid Build Coastguard Worker   if (Defs.count() != 1)
2376*9880d681SAndroid Build Coastguard Worker     return 0;
2377*9880d681SAndroid Build Coastguard Worker   return Defs.find_first();
2378*9880d681SAndroid Build Coastguard Worker }
2379*9880d681SAndroid Build Coastguard Worker 
2380*9880d681SAndroid Build Coastguard Worker 
isConst(unsigned Reg) const2381*9880d681SAndroid Build Coastguard Worker bool HexagonLoopRescheduling::isConst(unsigned Reg) const {
2382*9880d681SAndroid Build Coastguard Worker   if (!BTP->has(Reg))
2383*9880d681SAndroid Build Coastguard Worker     return false;
2384*9880d681SAndroid Build Coastguard Worker   const BitTracker::RegisterCell &RC = BTP->lookup(Reg);
2385*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 0, w = RC.width(); i < w; ++i) {
2386*9880d681SAndroid Build Coastguard Worker     const BitTracker::BitValue &V = RC[i];
2387*9880d681SAndroid Build Coastguard Worker     if (!V.is(0) && !V.is(1))
2388*9880d681SAndroid Build Coastguard Worker       return false;
2389*9880d681SAndroid Build Coastguard Worker   }
2390*9880d681SAndroid Build Coastguard Worker   return true;
2391*9880d681SAndroid Build Coastguard Worker }
2392*9880d681SAndroid Build Coastguard Worker 
2393*9880d681SAndroid Build Coastguard Worker 
isBitShuffle(const MachineInstr * MI,unsigned DefR) const2394*9880d681SAndroid Build Coastguard Worker bool HexagonLoopRescheduling::isBitShuffle(const MachineInstr *MI,
2395*9880d681SAndroid Build Coastguard Worker       unsigned DefR) const {
2396*9880d681SAndroid Build Coastguard Worker   unsigned Opc = MI->getOpcode();
2397*9880d681SAndroid Build Coastguard Worker   switch (Opc) {
2398*9880d681SAndroid Build Coastguard Worker     case TargetOpcode::COPY:
2399*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_lsr_i_r:
2400*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_asr_i_r:
2401*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_asl_i_r:
2402*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_lsr_i_p:
2403*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_asr_i_p:
2404*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_asl_i_p:
2405*9880d681SAndroid Build Coastguard Worker     case Hexagon::S2_insert:
2406*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_or:
2407*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_orp:
2408*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_and:
2409*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_andp:
2410*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_combinew:
2411*9880d681SAndroid Build Coastguard Worker     case Hexagon::A4_combineri:
2412*9880d681SAndroid Build Coastguard Worker     case Hexagon::A4_combineir:
2413*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_combineii:
2414*9880d681SAndroid Build Coastguard Worker     case Hexagon::A4_combineii:
2415*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_combine_ll:
2416*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_combine_lh:
2417*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_combine_hl:
2418*9880d681SAndroid Build Coastguard Worker     case Hexagon::A2_combine_hh:
2419*9880d681SAndroid Build Coastguard Worker       return true;
2420*9880d681SAndroid Build Coastguard Worker   }
2421*9880d681SAndroid Build Coastguard Worker   return false;
2422*9880d681SAndroid Build Coastguard Worker }
2423*9880d681SAndroid Build Coastguard Worker 
2424*9880d681SAndroid Build Coastguard Worker 
isStoreInput(const MachineInstr * MI,unsigned InpR) const2425*9880d681SAndroid Build Coastguard Worker bool HexagonLoopRescheduling::isStoreInput(const MachineInstr *MI,
2426*9880d681SAndroid Build Coastguard Worker       unsigned InpR) const {
2427*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
2428*9880d681SAndroid Build Coastguard Worker     const MachineOperand &Op = MI->getOperand(i);
2429*9880d681SAndroid Build Coastguard Worker     if (!Op.isReg())
2430*9880d681SAndroid Build Coastguard Worker       continue;
2431*9880d681SAndroid Build Coastguard Worker     if (Op.getReg() == InpR)
2432*9880d681SAndroid Build Coastguard Worker       return i == n-1;
2433*9880d681SAndroid Build Coastguard Worker   }
2434*9880d681SAndroid Build Coastguard Worker   return false;
2435*9880d681SAndroid Build Coastguard Worker }
2436*9880d681SAndroid Build Coastguard Worker 
2437*9880d681SAndroid Build Coastguard Worker 
isShuffleOf(unsigned OutR,unsigned InpR) const2438*9880d681SAndroid Build Coastguard Worker bool HexagonLoopRescheduling::isShuffleOf(unsigned OutR, unsigned InpR) const {
2439*9880d681SAndroid Build Coastguard Worker   if (!BTP->has(OutR) || !BTP->has(InpR))
2440*9880d681SAndroid Build Coastguard Worker     return false;
2441*9880d681SAndroid Build Coastguard Worker   const BitTracker::RegisterCell &OutC = BTP->lookup(OutR);
2442*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 0, w = OutC.width(); i < w; ++i) {
2443*9880d681SAndroid Build Coastguard Worker     const BitTracker::BitValue &V = OutC[i];
2444*9880d681SAndroid Build Coastguard Worker     if (V.Type != BitTracker::BitValue::Ref)
2445*9880d681SAndroid Build Coastguard Worker       continue;
2446*9880d681SAndroid Build Coastguard Worker     if (V.RefI.Reg != InpR)
2447*9880d681SAndroid Build Coastguard Worker       return false;
2448*9880d681SAndroid Build Coastguard Worker   }
2449*9880d681SAndroid Build Coastguard Worker   return true;
2450*9880d681SAndroid Build Coastguard Worker }
2451*9880d681SAndroid Build Coastguard Worker 
2452*9880d681SAndroid Build Coastguard Worker 
isSameShuffle(unsigned OutR1,unsigned InpR1,unsigned OutR2,unsigned & InpR2) const2453*9880d681SAndroid Build Coastguard Worker bool HexagonLoopRescheduling::isSameShuffle(unsigned OutR1, unsigned InpR1,
2454*9880d681SAndroid Build Coastguard Worker       unsigned OutR2, unsigned &InpR2) const {
2455*9880d681SAndroid Build Coastguard Worker   if (!BTP->has(OutR1) || !BTP->has(InpR1) || !BTP->has(OutR2))
2456*9880d681SAndroid Build Coastguard Worker     return false;
2457*9880d681SAndroid Build Coastguard Worker   const BitTracker::RegisterCell &OutC1 = BTP->lookup(OutR1);
2458*9880d681SAndroid Build Coastguard Worker   const BitTracker::RegisterCell &OutC2 = BTP->lookup(OutR2);
2459*9880d681SAndroid Build Coastguard Worker   unsigned W = OutC1.width();
2460*9880d681SAndroid Build Coastguard Worker   unsigned MatchR = 0;
2461*9880d681SAndroid Build Coastguard Worker   if (W != OutC2.width())
2462*9880d681SAndroid Build Coastguard Worker     return false;
2463*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 0; i < W; ++i) {
2464*9880d681SAndroid Build Coastguard Worker     const BitTracker::BitValue &V1 = OutC1[i], &V2 = OutC2[i];
2465*9880d681SAndroid Build Coastguard Worker     if (V1.Type != V2.Type || V1.Type == BitTracker::BitValue::One)
2466*9880d681SAndroid Build Coastguard Worker       return false;
2467*9880d681SAndroid Build Coastguard Worker     if (V1.Type != BitTracker::BitValue::Ref)
2468*9880d681SAndroid Build Coastguard Worker       continue;
2469*9880d681SAndroid Build Coastguard Worker     if (V1.RefI.Pos != V2.RefI.Pos)
2470*9880d681SAndroid Build Coastguard Worker       return false;
2471*9880d681SAndroid Build Coastguard Worker     if (V1.RefI.Reg != InpR1)
2472*9880d681SAndroid Build Coastguard Worker       return false;
2473*9880d681SAndroid Build Coastguard Worker     if (V2.RefI.Reg == 0 || V2.RefI.Reg == OutR2)
2474*9880d681SAndroid Build Coastguard Worker       return false;
2475*9880d681SAndroid Build Coastguard Worker     if (!MatchR)
2476*9880d681SAndroid Build Coastguard Worker       MatchR = V2.RefI.Reg;
2477*9880d681SAndroid Build Coastguard Worker     else if (V2.RefI.Reg != MatchR)
2478*9880d681SAndroid Build Coastguard Worker       return false;
2479*9880d681SAndroid Build Coastguard Worker   }
2480*9880d681SAndroid Build Coastguard Worker   InpR2 = MatchR;
2481*9880d681SAndroid Build Coastguard Worker   return true;
2482*9880d681SAndroid Build Coastguard Worker }
2483*9880d681SAndroid Build Coastguard Worker 
2484*9880d681SAndroid Build Coastguard Worker 
moveGroup(InstrGroup & G,MachineBasicBlock & LB,MachineBasicBlock & PB,MachineBasicBlock::iterator At,unsigned OldPhiR,unsigned NewPredR)2485*9880d681SAndroid Build Coastguard Worker void HexagonLoopRescheduling::moveGroup(InstrGroup &G, MachineBasicBlock &LB,
2486*9880d681SAndroid Build Coastguard Worker       MachineBasicBlock &PB, MachineBasicBlock::iterator At, unsigned OldPhiR,
2487*9880d681SAndroid Build Coastguard Worker       unsigned NewPredR) {
2488*9880d681SAndroid Build Coastguard Worker   DenseMap<unsigned,unsigned> RegMap;
2489*9880d681SAndroid Build Coastguard Worker 
2490*9880d681SAndroid Build Coastguard Worker   const TargetRegisterClass *PhiRC = MRI->getRegClass(NewPredR);
2491*9880d681SAndroid Build Coastguard Worker   unsigned PhiR = MRI->createVirtualRegister(PhiRC);
2492*9880d681SAndroid Build Coastguard Worker   BuildMI(LB, At, At->getDebugLoc(), HII->get(TargetOpcode::PHI), PhiR)
2493*9880d681SAndroid Build Coastguard Worker     .addReg(NewPredR)
2494*9880d681SAndroid Build Coastguard Worker     .addMBB(&PB)
2495*9880d681SAndroid Build Coastguard Worker     .addReg(G.Inp.Reg)
2496*9880d681SAndroid Build Coastguard Worker     .addMBB(&LB);
2497*9880d681SAndroid Build Coastguard Worker   RegMap.insert(std::make_pair(G.Inp.Reg, PhiR));
2498*9880d681SAndroid Build Coastguard Worker 
2499*9880d681SAndroid Build Coastguard Worker   for (unsigned i = G.Ins.size(); i > 0; --i) {
2500*9880d681SAndroid Build Coastguard Worker     const MachineInstr *SI = G.Ins[i-1];
2501*9880d681SAndroid Build Coastguard Worker     unsigned DR = getDefReg(SI);
2502*9880d681SAndroid Build Coastguard Worker     const TargetRegisterClass *RC = MRI->getRegClass(DR);
2503*9880d681SAndroid Build Coastguard Worker     unsigned NewDR = MRI->createVirtualRegister(RC);
2504*9880d681SAndroid Build Coastguard Worker     DebugLoc DL = SI->getDebugLoc();
2505*9880d681SAndroid Build Coastguard Worker 
2506*9880d681SAndroid Build Coastguard Worker     auto MIB = BuildMI(LB, At, DL, HII->get(SI->getOpcode()), NewDR);
2507*9880d681SAndroid Build Coastguard Worker     for (unsigned j = 0, m = SI->getNumOperands(); j < m; ++j) {
2508*9880d681SAndroid Build Coastguard Worker       const MachineOperand &Op = SI->getOperand(j);
2509*9880d681SAndroid Build Coastguard Worker       if (!Op.isReg()) {
2510*9880d681SAndroid Build Coastguard Worker         MIB.addOperand(Op);
2511*9880d681SAndroid Build Coastguard Worker         continue;
2512*9880d681SAndroid Build Coastguard Worker       }
2513*9880d681SAndroid Build Coastguard Worker       if (!Op.isUse())
2514*9880d681SAndroid Build Coastguard Worker         continue;
2515*9880d681SAndroid Build Coastguard Worker       unsigned UseR = RegMap[Op.getReg()];
2516*9880d681SAndroid Build Coastguard Worker       MIB.addReg(UseR, 0, Op.getSubReg());
2517*9880d681SAndroid Build Coastguard Worker     }
2518*9880d681SAndroid Build Coastguard Worker     RegMap.insert(std::make_pair(DR, NewDR));
2519*9880d681SAndroid Build Coastguard Worker   }
2520*9880d681SAndroid Build Coastguard Worker 
2521*9880d681SAndroid Build Coastguard Worker   HBS::replaceReg(OldPhiR, RegMap[G.Out.Reg], *MRI);
2522*9880d681SAndroid Build Coastguard Worker }
2523*9880d681SAndroid Build Coastguard Worker 
2524*9880d681SAndroid Build Coastguard Worker 
processLoop(LoopCand & C)2525*9880d681SAndroid Build Coastguard Worker bool HexagonLoopRescheduling::processLoop(LoopCand &C) {
2526*9880d681SAndroid Build Coastguard Worker   DEBUG(dbgs() << "Processing loop in BB#" << C.LB->getNumber() << "\n");
2527*9880d681SAndroid Build Coastguard Worker   std::vector<PhiInfo> Phis;
2528*9880d681SAndroid Build Coastguard Worker   for (auto &I : *C.LB) {
2529*9880d681SAndroid Build Coastguard Worker     if (!I.isPHI())
2530*9880d681SAndroid Build Coastguard Worker       break;
2531*9880d681SAndroid Build Coastguard Worker     unsigned PR = getDefReg(&I);
2532*9880d681SAndroid Build Coastguard Worker     if (isConst(PR))
2533*9880d681SAndroid Build Coastguard Worker       continue;
2534*9880d681SAndroid Build Coastguard Worker     bool BadUse = false, GoodUse = false;
2535*9880d681SAndroid Build Coastguard Worker     for (auto UI = MRI->use_begin(PR), UE = MRI->use_end(); UI != UE; ++UI) {
2536*9880d681SAndroid Build Coastguard Worker       MachineInstr *UseI = UI->getParent();
2537*9880d681SAndroid Build Coastguard Worker       if (UseI->getParent() != C.LB) {
2538*9880d681SAndroid Build Coastguard Worker         BadUse = true;
2539*9880d681SAndroid Build Coastguard Worker         break;
2540*9880d681SAndroid Build Coastguard Worker       }
2541*9880d681SAndroid Build Coastguard Worker       if (isBitShuffle(UseI, PR) || isStoreInput(UseI, PR))
2542*9880d681SAndroid Build Coastguard Worker         GoodUse = true;
2543*9880d681SAndroid Build Coastguard Worker     }
2544*9880d681SAndroid Build Coastguard Worker     if (BadUse || !GoodUse)
2545*9880d681SAndroid Build Coastguard Worker       continue;
2546*9880d681SAndroid Build Coastguard Worker 
2547*9880d681SAndroid Build Coastguard Worker     Phis.push_back(PhiInfo(I, *C.LB));
2548*9880d681SAndroid Build Coastguard Worker   }
2549*9880d681SAndroid Build Coastguard Worker 
2550*9880d681SAndroid Build Coastguard Worker   DEBUG({
2551*9880d681SAndroid Build Coastguard Worker     dbgs() << "Phis: {";
2552*9880d681SAndroid Build Coastguard Worker     for (auto &I : Phis) {
2553*9880d681SAndroid Build Coastguard Worker       dbgs() << ' ' << PrintReg(I.DefR, HRI) << "=phi("
2554*9880d681SAndroid Build Coastguard Worker              << PrintReg(I.PR.Reg, HRI, I.PR.Sub) << ":b" << I.PB->getNumber()
2555*9880d681SAndroid Build Coastguard Worker              << ',' << PrintReg(I.LR.Reg, HRI, I.LR.Sub) << ":b"
2556*9880d681SAndroid Build Coastguard Worker              << I.LB->getNumber() << ')';
2557*9880d681SAndroid Build Coastguard Worker     }
2558*9880d681SAndroid Build Coastguard Worker     dbgs() << " }\n";
2559*9880d681SAndroid Build Coastguard Worker   });
2560*9880d681SAndroid Build Coastguard Worker 
2561*9880d681SAndroid Build Coastguard Worker   if (Phis.empty())
2562*9880d681SAndroid Build Coastguard Worker     return false;
2563*9880d681SAndroid Build Coastguard Worker 
2564*9880d681SAndroid Build Coastguard Worker   bool Changed = false;
2565*9880d681SAndroid Build Coastguard Worker   InstrList ShufIns;
2566*9880d681SAndroid Build Coastguard Worker 
2567*9880d681SAndroid Build Coastguard Worker   // Go backwards in the block: for each bit shuffling instruction, check
2568*9880d681SAndroid Build Coastguard Worker   // if that instruction could potentially be moved to the front of the loop:
2569*9880d681SAndroid Build Coastguard Worker   // the output of the loop cannot be used in a non-shuffling instruction
2570*9880d681SAndroid Build Coastguard Worker   // in this loop.
2571*9880d681SAndroid Build Coastguard Worker   for (auto I = C.LB->rbegin(), E = C.LB->rend(); I != E; ++I) {
2572*9880d681SAndroid Build Coastguard Worker     if (I->isTerminator())
2573*9880d681SAndroid Build Coastguard Worker       continue;
2574*9880d681SAndroid Build Coastguard Worker     if (I->isPHI())
2575*9880d681SAndroid Build Coastguard Worker       break;
2576*9880d681SAndroid Build Coastguard Worker 
2577*9880d681SAndroid Build Coastguard Worker     RegisterSet Defs;
2578*9880d681SAndroid Build Coastguard Worker     HBS::getInstrDefs(*I, Defs);
2579*9880d681SAndroid Build Coastguard Worker     if (Defs.count() != 1)
2580*9880d681SAndroid Build Coastguard Worker       continue;
2581*9880d681SAndroid Build Coastguard Worker     unsigned DefR = Defs.find_first();
2582*9880d681SAndroid Build Coastguard Worker     if (!TargetRegisterInfo::isVirtualRegister(DefR))
2583*9880d681SAndroid Build Coastguard Worker       continue;
2584*9880d681SAndroid Build Coastguard Worker     if (!isBitShuffle(&*I, DefR))
2585*9880d681SAndroid Build Coastguard Worker       continue;
2586*9880d681SAndroid Build Coastguard Worker 
2587*9880d681SAndroid Build Coastguard Worker     bool BadUse = false;
2588*9880d681SAndroid Build Coastguard Worker     for (auto UI = MRI->use_begin(DefR), UE = MRI->use_end(); UI != UE; ++UI) {
2589*9880d681SAndroid Build Coastguard Worker       MachineInstr *UseI = UI->getParent();
2590*9880d681SAndroid Build Coastguard Worker       if (UseI->getParent() == C.LB) {
2591*9880d681SAndroid Build Coastguard Worker         if (UseI->isPHI()) {
2592*9880d681SAndroid Build Coastguard Worker           // If the use is in a phi node in this loop, then it should be
2593*9880d681SAndroid Build Coastguard Worker           // the value corresponding to the back edge.
2594*9880d681SAndroid Build Coastguard Worker           unsigned Idx = UI.getOperandNo();
2595*9880d681SAndroid Build Coastguard Worker           if (UseI->getOperand(Idx+1).getMBB() != C.LB)
2596*9880d681SAndroid Build Coastguard Worker             BadUse = true;
2597*9880d681SAndroid Build Coastguard Worker         } else {
2598*9880d681SAndroid Build Coastguard Worker           auto F = std::find(ShufIns.begin(), ShufIns.end(), UseI);
2599*9880d681SAndroid Build Coastguard Worker           if (F == ShufIns.end())
2600*9880d681SAndroid Build Coastguard Worker             BadUse = true;
2601*9880d681SAndroid Build Coastguard Worker         }
2602*9880d681SAndroid Build Coastguard Worker       } else {
2603*9880d681SAndroid Build Coastguard Worker         // There is a use outside of the loop, but there is no epilog block
2604*9880d681SAndroid Build Coastguard Worker         // suitable for a copy-out.
2605*9880d681SAndroid Build Coastguard Worker         if (C.EB == nullptr)
2606*9880d681SAndroid Build Coastguard Worker           BadUse = true;
2607*9880d681SAndroid Build Coastguard Worker       }
2608*9880d681SAndroid Build Coastguard Worker       if (BadUse)
2609*9880d681SAndroid Build Coastguard Worker         break;
2610*9880d681SAndroid Build Coastguard Worker     }
2611*9880d681SAndroid Build Coastguard Worker 
2612*9880d681SAndroid Build Coastguard Worker     if (BadUse)
2613*9880d681SAndroid Build Coastguard Worker       continue;
2614*9880d681SAndroid Build Coastguard Worker     ShufIns.push_back(&*I);
2615*9880d681SAndroid Build Coastguard Worker   }
2616*9880d681SAndroid Build Coastguard Worker 
2617*9880d681SAndroid Build Coastguard Worker   // Partition the list of shuffling instructions into instruction groups,
2618*9880d681SAndroid Build Coastguard Worker   // where each group has to be moved as a whole (i.e. a group is a chain of
2619*9880d681SAndroid Build Coastguard Worker   // dependent instructions). A group produces a single live output register,
2620*9880d681SAndroid Build Coastguard Worker   // which is meant to be the input of the loop phi node (although this is
2621*9880d681SAndroid Build Coastguard Worker   // not checked here yet). It also uses a single register as its input,
2622*9880d681SAndroid Build Coastguard Worker   // which is some value produced in the loop body. After moving the group
2623*9880d681SAndroid Build Coastguard Worker   // to the beginning of the loop, that input register would need to be
2624*9880d681SAndroid Build Coastguard Worker   // the loop-carried register (through a phi node) instead of the (currently
2625*9880d681SAndroid Build Coastguard Worker   // loop-carried) output register.
2626*9880d681SAndroid Build Coastguard Worker   typedef std::vector<InstrGroup> InstrGroupList;
2627*9880d681SAndroid Build Coastguard Worker   InstrGroupList Groups;
2628*9880d681SAndroid Build Coastguard Worker 
2629*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 0, n = ShufIns.size(); i < n; ++i) {
2630*9880d681SAndroid Build Coastguard Worker     MachineInstr *SI = ShufIns[i];
2631*9880d681SAndroid Build Coastguard Worker     if (SI == nullptr)
2632*9880d681SAndroid Build Coastguard Worker       continue;
2633*9880d681SAndroid Build Coastguard Worker 
2634*9880d681SAndroid Build Coastguard Worker     InstrGroup G;
2635*9880d681SAndroid Build Coastguard Worker     G.Ins.push_back(SI);
2636*9880d681SAndroid Build Coastguard Worker     G.Out.Reg = getDefReg(SI);
2637*9880d681SAndroid Build Coastguard Worker     RegisterSet Inputs;
2638*9880d681SAndroid Build Coastguard Worker     HBS::getInstrUses(*SI, Inputs);
2639*9880d681SAndroid Build Coastguard Worker 
2640*9880d681SAndroid Build Coastguard Worker     for (unsigned j = i+1; j < n; ++j) {
2641*9880d681SAndroid Build Coastguard Worker       MachineInstr *MI = ShufIns[j];
2642*9880d681SAndroid Build Coastguard Worker       if (MI == nullptr)
2643*9880d681SAndroid Build Coastguard Worker         continue;
2644*9880d681SAndroid Build Coastguard Worker       RegisterSet Defs;
2645*9880d681SAndroid Build Coastguard Worker       HBS::getInstrDefs(*MI, Defs);
2646*9880d681SAndroid Build Coastguard Worker       // If this instruction does not define any pending inputs, skip it.
2647*9880d681SAndroid Build Coastguard Worker       if (!Defs.intersects(Inputs))
2648*9880d681SAndroid Build Coastguard Worker         continue;
2649*9880d681SAndroid Build Coastguard Worker       // Otherwise, add it to the current group and remove the inputs that
2650*9880d681SAndroid Build Coastguard Worker       // are defined by MI.
2651*9880d681SAndroid Build Coastguard Worker       G.Ins.push_back(MI);
2652*9880d681SAndroid Build Coastguard Worker       Inputs.remove(Defs);
2653*9880d681SAndroid Build Coastguard Worker       // Then add all registers used by MI.
2654*9880d681SAndroid Build Coastguard Worker       HBS::getInstrUses(*MI, Inputs);
2655*9880d681SAndroid Build Coastguard Worker       ShufIns[j] = nullptr;
2656*9880d681SAndroid Build Coastguard Worker     }
2657*9880d681SAndroid Build Coastguard Worker 
2658*9880d681SAndroid Build Coastguard Worker     // Only add a group if it requires at most one register.
2659*9880d681SAndroid Build Coastguard Worker     if (Inputs.count() > 1)
2660*9880d681SAndroid Build Coastguard Worker       continue;
2661*9880d681SAndroid Build Coastguard Worker     auto LoopInpEq = [G] (const PhiInfo &P) -> bool {
2662*9880d681SAndroid Build Coastguard Worker       return G.Out.Reg == P.LR.Reg;
2663*9880d681SAndroid Build Coastguard Worker     };
2664*9880d681SAndroid Build Coastguard Worker     if (std::find_if(Phis.begin(), Phis.end(), LoopInpEq) == Phis.end())
2665*9880d681SAndroid Build Coastguard Worker       continue;
2666*9880d681SAndroid Build Coastguard Worker 
2667*9880d681SAndroid Build Coastguard Worker     G.Inp.Reg = Inputs.find_first();
2668*9880d681SAndroid Build Coastguard Worker     Groups.push_back(G);
2669*9880d681SAndroid Build Coastguard Worker   }
2670*9880d681SAndroid Build Coastguard Worker 
2671*9880d681SAndroid Build Coastguard Worker   DEBUG({
2672*9880d681SAndroid Build Coastguard Worker     for (unsigned i = 0, n = Groups.size(); i < n; ++i) {
2673*9880d681SAndroid Build Coastguard Worker       InstrGroup &G = Groups[i];
2674*9880d681SAndroid Build Coastguard Worker       dbgs() << "Group[" << i << "] inp: "
2675*9880d681SAndroid Build Coastguard Worker              << PrintReg(G.Inp.Reg, HRI, G.Inp.Sub)
2676*9880d681SAndroid Build Coastguard Worker              << "  out: " << PrintReg(G.Out.Reg, HRI, G.Out.Sub) << "\n";
2677*9880d681SAndroid Build Coastguard Worker       for (unsigned j = 0, m = G.Ins.size(); j < m; ++j)
2678*9880d681SAndroid Build Coastguard Worker         dbgs() << "  " << *G.Ins[j];
2679*9880d681SAndroid Build Coastguard Worker     }
2680*9880d681SAndroid Build Coastguard Worker   });
2681*9880d681SAndroid Build Coastguard Worker 
2682*9880d681SAndroid Build Coastguard Worker   for (unsigned i = 0, n = Groups.size(); i < n; ++i) {
2683*9880d681SAndroid Build Coastguard Worker     InstrGroup &G = Groups[i];
2684*9880d681SAndroid Build Coastguard Worker     if (!isShuffleOf(G.Out.Reg, G.Inp.Reg))
2685*9880d681SAndroid Build Coastguard Worker       continue;
2686*9880d681SAndroid Build Coastguard Worker     auto LoopInpEq = [G] (const PhiInfo &P) -> bool {
2687*9880d681SAndroid Build Coastguard Worker       return G.Out.Reg == P.LR.Reg;
2688*9880d681SAndroid Build Coastguard Worker     };
2689*9880d681SAndroid Build Coastguard Worker     auto F = std::find_if(Phis.begin(), Phis.end(), LoopInpEq);
2690*9880d681SAndroid Build Coastguard Worker     if (F == Phis.end())
2691*9880d681SAndroid Build Coastguard Worker       continue;
2692*9880d681SAndroid Build Coastguard Worker     unsigned PredR = 0;
2693*9880d681SAndroid Build Coastguard Worker     if (!isSameShuffle(G.Out.Reg, G.Inp.Reg, F->PR.Reg, PredR)) {
2694*9880d681SAndroid Build Coastguard Worker       const MachineInstr *DefPredR = MRI->getVRegDef(F->PR.Reg);
2695*9880d681SAndroid Build Coastguard Worker       unsigned Opc = DefPredR->getOpcode();
2696*9880d681SAndroid Build Coastguard Worker       if (Opc != Hexagon::A2_tfrsi && Opc != Hexagon::A2_tfrpi)
2697*9880d681SAndroid Build Coastguard Worker         continue;
2698*9880d681SAndroid Build Coastguard Worker       if (!DefPredR->getOperand(1).isImm())
2699*9880d681SAndroid Build Coastguard Worker         continue;
2700*9880d681SAndroid Build Coastguard Worker       if (DefPredR->getOperand(1).getImm() != 0)
2701*9880d681SAndroid Build Coastguard Worker         continue;
2702*9880d681SAndroid Build Coastguard Worker       const TargetRegisterClass *RC = MRI->getRegClass(G.Inp.Reg);
2703*9880d681SAndroid Build Coastguard Worker       if (RC != MRI->getRegClass(F->PR.Reg)) {
2704*9880d681SAndroid Build Coastguard Worker         PredR = MRI->createVirtualRegister(RC);
2705*9880d681SAndroid Build Coastguard Worker         unsigned TfrI = (RC == &Hexagon::IntRegsRegClass) ? Hexagon::A2_tfrsi
2706*9880d681SAndroid Build Coastguard Worker                                                           : Hexagon::A2_tfrpi;
2707*9880d681SAndroid Build Coastguard Worker         auto T = C.PB->getFirstTerminator();
2708*9880d681SAndroid Build Coastguard Worker         DebugLoc DL = (T != C.PB->end()) ? T->getDebugLoc() : DebugLoc();
2709*9880d681SAndroid Build Coastguard Worker         BuildMI(*C.PB, T, DL, HII->get(TfrI), PredR)
2710*9880d681SAndroid Build Coastguard Worker           .addImm(0);
2711*9880d681SAndroid Build Coastguard Worker       } else {
2712*9880d681SAndroid Build Coastguard Worker         PredR = F->PR.Reg;
2713*9880d681SAndroid Build Coastguard Worker       }
2714*9880d681SAndroid Build Coastguard Worker     }
2715*9880d681SAndroid Build Coastguard Worker     assert(MRI->getRegClass(PredR) == MRI->getRegClass(G.Inp.Reg));
2716*9880d681SAndroid Build Coastguard Worker     moveGroup(G, *F->LB, *F->PB, F->LB->getFirstNonPHI(), F->DefR, PredR);
2717*9880d681SAndroid Build Coastguard Worker     Changed = true;
2718*9880d681SAndroid Build Coastguard Worker   }
2719*9880d681SAndroid Build Coastguard Worker 
2720*9880d681SAndroid Build Coastguard Worker   return Changed;
2721*9880d681SAndroid Build Coastguard Worker }
2722*9880d681SAndroid Build Coastguard Worker 
2723*9880d681SAndroid Build Coastguard Worker 
runOnMachineFunction(MachineFunction & MF)2724*9880d681SAndroid Build Coastguard Worker bool HexagonLoopRescheduling::runOnMachineFunction(MachineFunction &MF) {
2725*9880d681SAndroid Build Coastguard Worker   if (skipFunction(*MF.getFunction()))
2726*9880d681SAndroid Build Coastguard Worker     return false;
2727*9880d681SAndroid Build Coastguard Worker 
2728*9880d681SAndroid Build Coastguard Worker   auto &HST = MF.getSubtarget<HexagonSubtarget>();
2729*9880d681SAndroid Build Coastguard Worker   HII = HST.getInstrInfo();
2730*9880d681SAndroid Build Coastguard Worker   HRI = HST.getRegisterInfo();
2731*9880d681SAndroid Build Coastguard Worker   MRI = &MF.getRegInfo();
2732*9880d681SAndroid Build Coastguard Worker   const HexagonEvaluator HE(*HRI, *MRI, *HII, MF);
2733*9880d681SAndroid Build Coastguard Worker   BitTracker BT(HE, MF);
2734*9880d681SAndroid Build Coastguard Worker   DEBUG(BT.trace(true));
2735*9880d681SAndroid Build Coastguard Worker   BT.run();
2736*9880d681SAndroid Build Coastguard Worker   BTP = &BT;
2737*9880d681SAndroid Build Coastguard Worker 
2738*9880d681SAndroid Build Coastguard Worker   std::vector<LoopCand> Cand;
2739*9880d681SAndroid Build Coastguard Worker 
2740*9880d681SAndroid Build Coastguard Worker   for (auto &B : MF) {
2741*9880d681SAndroid Build Coastguard Worker     if (B.pred_size() != 2 || B.succ_size() != 2)
2742*9880d681SAndroid Build Coastguard Worker       continue;
2743*9880d681SAndroid Build Coastguard Worker     MachineBasicBlock *PB = nullptr;
2744*9880d681SAndroid Build Coastguard Worker     bool IsLoop = false;
2745*9880d681SAndroid Build Coastguard Worker     for (auto PI = B.pred_begin(), PE = B.pred_end(); PI != PE; ++PI) {
2746*9880d681SAndroid Build Coastguard Worker       if (*PI != &B)
2747*9880d681SAndroid Build Coastguard Worker         PB = *PI;
2748*9880d681SAndroid Build Coastguard Worker       else
2749*9880d681SAndroid Build Coastguard Worker         IsLoop = true;
2750*9880d681SAndroid Build Coastguard Worker     }
2751*9880d681SAndroid Build Coastguard Worker     if (!IsLoop)
2752*9880d681SAndroid Build Coastguard Worker       continue;
2753*9880d681SAndroid Build Coastguard Worker 
2754*9880d681SAndroid Build Coastguard Worker     MachineBasicBlock *EB = nullptr;
2755*9880d681SAndroid Build Coastguard Worker     for (auto SI = B.succ_begin(), SE = B.succ_end(); SI != SE; ++SI) {
2756*9880d681SAndroid Build Coastguard Worker       if (*SI == &B)
2757*9880d681SAndroid Build Coastguard Worker         continue;
2758*9880d681SAndroid Build Coastguard Worker       // Set EP to the epilog block, if it has only 1 predecessor (i.e. the
2759*9880d681SAndroid Build Coastguard Worker       // edge from B to EP is non-critical.
2760*9880d681SAndroid Build Coastguard Worker       if ((*SI)->pred_size() == 1)
2761*9880d681SAndroid Build Coastguard Worker         EB = *SI;
2762*9880d681SAndroid Build Coastguard Worker       break;
2763*9880d681SAndroid Build Coastguard Worker     }
2764*9880d681SAndroid Build Coastguard Worker 
2765*9880d681SAndroid Build Coastguard Worker     Cand.push_back(LoopCand(&B, PB, EB));
2766*9880d681SAndroid Build Coastguard Worker   }
2767*9880d681SAndroid Build Coastguard Worker 
2768*9880d681SAndroid Build Coastguard Worker   bool Changed = false;
2769*9880d681SAndroid Build Coastguard Worker   for (auto &C : Cand)
2770*9880d681SAndroid Build Coastguard Worker     Changed |= processLoop(C);
2771*9880d681SAndroid Build Coastguard Worker 
2772*9880d681SAndroid Build Coastguard Worker   return Changed;
2773*9880d681SAndroid Build Coastguard Worker }
2774*9880d681SAndroid Build Coastguard Worker 
2775*9880d681SAndroid Build Coastguard Worker //===----------------------------------------------------------------------===//
2776*9880d681SAndroid Build Coastguard Worker //                         Public Constructor Functions
2777*9880d681SAndroid Build Coastguard Worker //===----------------------------------------------------------------------===//
2778*9880d681SAndroid Build Coastguard Worker 
createHexagonLoopRescheduling()2779*9880d681SAndroid Build Coastguard Worker FunctionPass *llvm::createHexagonLoopRescheduling() {
2780*9880d681SAndroid Build Coastguard Worker   return new HexagonLoopRescheduling();
2781*9880d681SAndroid Build Coastguard Worker }
2782*9880d681SAndroid Build Coastguard Worker 
createHexagonBitSimplify()2783*9880d681SAndroid Build Coastguard Worker FunctionPass *llvm::createHexagonBitSimplify() {
2784*9880d681SAndroid Build Coastguard Worker   return new HexagonBitSimplify();
2785*9880d681SAndroid Build Coastguard Worker }
2786*9880d681SAndroid Build Coastguard Worker 
2787