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