1 //===- HexagonGenInsert.cpp -----------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "BitTracker.h"
10 #include "HexagonBitTracker.h"
11 #include "HexagonInstrInfo.h"
12 #include "HexagonRegisterInfo.h"
13 #include "HexagonSubtarget.h"
14 #include "llvm/ADT/BitVector.h"
15 #include "llvm/ADT/DenseMap.h"
16 #include "llvm/ADT/GraphTraits.h"
17 #include "llvm/ADT/PostOrderIterator.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallSet.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/StringRef.h"
22 #include "llvm/CodeGen/MachineBasicBlock.h"
23 #include "llvm/CodeGen/MachineDominators.h"
24 #include "llvm/CodeGen/MachineFunction.h"
25 #include "llvm/CodeGen/MachineFunctionPass.h"
26 #include "llvm/CodeGen/MachineInstr.h"
27 #include "llvm/CodeGen/MachineInstrBuilder.h"
28 #include "llvm/CodeGen/MachineOperand.h"
29 #include "llvm/CodeGen/MachineRegisterInfo.h"
30 #include "llvm/CodeGen/TargetRegisterInfo.h"
31 #include "llvm/IR/DebugLoc.h"
32 #include "llvm/InitializePasses.h"
33 #include "llvm/Pass.h"
34 #include "llvm/Support/CommandLine.h"
35 #include "llvm/Support/Debug.h"
36 #include "llvm/Support/MathExtras.h"
37 #include "llvm/Support/Timer.h"
38 #include "llvm/Support/raw_ostream.h"
39 #include <algorithm>
40 #include <cassert>
41 #include <cstdint>
42 #include <iterator>
43 #include <utility>
44 #include <vector>
45
46 #define DEBUG_TYPE "hexinsert"
47
48 using namespace llvm;
49
50 static cl::opt<unsigned> VRegIndexCutoff("insert-vreg-cutoff", cl::init(~0U),
51 cl::Hidden, cl::ZeroOrMore, cl::desc("Vreg# cutoff for insert generation."));
52 // The distance cutoff is selected based on the precheckin-perf results:
53 // cutoffs 20, 25, 35, and 40 are worse than 30.
54 static cl::opt<unsigned> VRegDistCutoff("insert-dist-cutoff", cl::init(30U),
55 cl::Hidden, cl::ZeroOrMore, cl::desc("Vreg distance cutoff for insert "
56 "generation."));
57
58 // Limit the container sizes for extreme cases where we run out of memory.
59 static cl::opt<unsigned> MaxORLSize("insert-max-orl", cl::init(4096),
60 cl::Hidden, cl::ZeroOrMore, cl::desc("Maximum size of OrderedRegisterList"));
61 static cl::opt<unsigned> MaxIFMSize("insert-max-ifmap", cl::init(1024),
62 cl::Hidden, cl::ZeroOrMore, cl::desc("Maximum size of IFMap"));
63
64 static cl::opt<bool> OptTiming("insert-timing", cl::init(false), cl::Hidden,
65 cl::ZeroOrMore, cl::desc("Enable timing of insert generation"));
66 static cl::opt<bool> OptTimingDetail("insert-timing-detail", cl::init(false),
67 cl::Hidden, cl::ZeroOrMore, cl::desc("Enable detailed timing of insert "
68 "generation"));
69
70 static cl::opt<bool> OptSelectAll0("insert-all0", cl::init(false), cl::Hidden,
71 cl::ZeroOrMore);
72 static cl::opt<bool> OptSelectHas0("insert-has0", cl::init(false), cl::Hidden,
73 cl::ZeroOrMore);
74 // Whether to construct constant values via "insert". Could eliminate constant
75 // extenders, but often not practical.
76 static cl::opt<bool> OptConst("insert-const", cl::init(false), cl::Hidden,
77 cl::ZeroOrMore);
78
79 // The preprocessor gets confused when the DEBUG macro is passed larger
80 // chunks of code. Use this function to detect debugging.
isDebug()81 inline static bool isDebug() {
82 #ifndef NDEBUG
83 return DebugFlag && isCurrentDebugType(DEBUG_TYPE);
84 #else
85 return false;
86 #endif
87 }
88
89 namespace {
90
91 // Set of virtual registers, based on BitVector.
92 struct RegisterSet : private BitVector {
93 RegisterSet() = default;
RegisterSet__anon11a15ffe0111::RegisterSet94 explicit RegisterSet(unsigned s, bool t = false) : BitVector(s, t) {}
RegisterSet__anon11a15ffe0111::RegisterSet95 RegisterSet(const RegisterSet &RS) : BitVector(RS) {}
operator =__anon11a15ffe0111::RegisterSet96 RegisterSet &operator=(const RegisterSet &RS) {
97 BitVector::operator=(RS);
98 return *this;
99 }
100
101 using BitVector::clear;
102
find_first__anon11a15ffe0111::RegisterSet103 unsigned find_first() const {
104 int First = BitVector::find_first();
105 if (First < 0)
106 return 0;
107 return x2v(First);
108 }
109
find_next__anon11a15ffe0111::RegisterSet110 unsigned find_next(unsigned Prev) const {
111 int Next = BitVector::find_next(v2x(Prev));
112 if (Next < 0)
113 return 0;
114 return x2v(Next);
115 }
116
insert__anon11a15ffe0111::RegisterSet117 RegisterSet &insert(unsigned R) {
118 unsigned Idx = v2x(R);
119 ensure(Idx);
120 return static_cast<RegisterSet&>(BitVector::set(Idx));
121 }
remove__anon11a15ffe0111::RegisterSet122 RegisterSet &remove(unsigned R) {
123 unsigned Idx = v2x(R);
124 if (Idx >= size())
125 return *this;
126 return static_cast<RegisterSet&>(BitVector::reset(Idx));
127 }
128
insert__anon11a15ffe0111::RegisterSet129 RegisterSet &insert(const RegisterSet &Rs) {
130 return static_cast<RegisterSet&>(BitVector::operator|=(Rs));
131 }
remove__anon11a15ffe0111::RegisterSet132 RegisterSet &remove(const RegisterSet &Rs) {
133 return static_cast<RegisterSet&>(BitVector::reset(Rs));
134 }
135
operator []__anon11a15ffe0111::RegisterSet136 reference operator[](unsigned R) {
137 unsigned Idx = v2x(R);
138 ensure(Idx);
139 return BitVector::operator[](Idx);
140 }
operator []__anon11a15ffe0111::RegisterSet141 bool operator[](unsigned R) const {
142 unsigned Idx = v2x(R);
143 assert(Idx < size());
144 return BitVector::operator[](Idx);
145 }
has__anon11a15ffe0111::RegisterSet146 bool has(unsigned R) const {
147 unsigned Idx = v2x(R);
148 if (Idx >= size())
149 return false;
150 return BitVector::test(Idx);
151 }
152
empty__anon11a15ffe0111::RegisterSet153 bool empty() const {
154 return !BitVector::any();
155 }
includes__anon11a15ffe0111::RegisterSet156 bool includes(const RegisterSet &Rs) const {
157 // A.BitVector::test(B) <=> A-B != {}
158 return !Rs.BitVector::test(*this);
159 }
intersects__anon11a15ffe0111::RegisterSet160 bool intersects(const RegisterSet &Rs) const {
161 return BitVector::anyCommon(Rs);
162 }
163
164 private:
ensure__anon11a15ffe0111::RegisterSet165 void ensure(unsigned Idx) {
166 if (size() <= Idx)
167 resize(std::max(Idx+1, 32U));
168 }
169
v2x__anon11a15ffe0111::RegisterSet170 static inline unsigned v2x(unsigned v) {
171 return Register::virtReg2Index(v);
172 }
173
x2v__anon11a15ffe0111::RegisterSet174 static inline unsigned x2v(unsigned x) {
175 return Register::index2VirtReg(x);
176 }
177 };
178
179 struct PrintRegSet {
PrintRegSet__anon11a15ffe0111::PrintRegSet180 PrintRegSet(const RegisterSet &S, const TargetRegisterInfo *RI)
181 : RS(S), TRI(RI) {}
182
183 friend raw_ostream &operator<< (raw_ostream &OS,
184 const PrintRegSet &P);
185
186 private:
187 const RegisterSet &RS;
188 const TargetRegisterInfo *TRI;
189 };
190
operator <<(raw_ostream & OS,const PrintRegSet & P)191 raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) {
192 OS << '{';
193 for (unsigned R = P.RS.find_first(); R; R = P.RS.find_next(R))
194 OS << ' ' << printReg(R, P.TRI);
195 OS << " }";
196 return OS;
197 }
198
199 // A convenience class to associate unsigned numbers (such as virtual
200 // registers) with unsigned numbers.
201 struct UnsignedMap : public DenseMap<unsigned,unsigned> {
202 UnsignedMap() = default;
203
204 private:
205 using BaseType = DenseMap<unsigned, unsigned>;
206 };
207
208 // A utility to establish an ordering between virtual registers:
209 // VRegA < VRegB <=> RegisterOrdering[VRegA] < RegisterOrdering[VRegB]
210 // This is meant as a cache for the ordering of virtual registers defined
211 // by a potentially expensive comparison function, or obtained by a proce-
212 // dure that should not be repeated each time two registers are compared.
213 struct RegisterOrdering : public UnsignedMap {
214 RegisterOrdering() = default;
215
operator []__anon11a15ffe0111::RegisterOrdering216 unsigned operator[](unsigned VR) const {
217 const_iterator F = find(VR);
218 assert(F != end());
219 return F->second;
220 }
221
222 // Add operator(), so that objects of this class can be used as
223 // comparators in std::sort et al.
operator ()__anon11a15ffe0111::RegisterOrdering224 bool operator() (unsigned VR1, unsigned VR2) const {
225 return operator[](VR1) < operator[](VR2);
226 }
227 };
228
229 // Ordering of bit values. This class does not have operator[], but
230 // is supplies a comparison operator() for use in std:: algorithms.
231 // The order is as follows:
232 // - 0 < 1 < ref
233 // - ref1 < ref2, if ord(ref1.Reg) < ord(ref2.Reg),
234 // or ord(ref1.Reg) == ord(ref2.Reg), and ref1.Pos < ref2.Pos.
235 struct BitValueOrdering {
BitValueOrdering__anon11a15ffe0111::BitValueOrdering236 BitValueOrdering(const RegisterOrdering &RB) : BaseOrd(RB) {}
237
238 bool operator() (const BitTracker::BitValue &V1,
239 const BitTracker::BitValue &V2) const;
240
241 const RegisterOrdering &BaseOrd;
242 };
243
244 } // end anonymous namespace
245
operator ()(const BitTracker::BitValue & V1,const BitTracker::BitValue & V2) const246 bool BitValueOrdering::operator() (const BitTracker::BitValue &V1,
247 const BitTracker::BitValue &V2) const {
248 if (V1 == V2)
249 return false;
250 // V1==0 => true, V2==0 => false
251 if (V1.is(0) || V2.is(0))
252 return V1.is(0);
253 // Neither of V1,V2 is 0, and V1!=V2.
254 // V2==1 => false, V1==1 => true
255 if (V2.is(1) || V1.is(1))
256 return !V2.is(1);
257 // Both V1,V2 are refs.
258 unsigned Ind1 = BaseOrd[V1.RefI.Reg], Ind2 = BaseOrd[V2.RefI.Reg];
259 if (Ind1 != Ind2)
260 return Ind1 < Ind2;
261 // If V1.Pos==V2.Pos
262 assert(V1.RefI.Pos != V2.RefI.Pos && "Bit values should be different");
263 return V1.RefI.Pos < V2.RefI.Pos;
264 }
265
266 namespace {
267
268 // Cache for the BitTracker's cell map. Map lookup has a logarithmic
269 // complexity, this class will memoize the lookup results to reduce
270 // the access time for repeated lookups of the same cell.
271 struct CellMapShadow {
CellMapShadow__anon11a15ffe0211::CellMapShadow272 CellMapShadow(const BitTracker &T) : BT(T) {}
273
lookup__anon11a15ffe0211::CellMapShadow274 const BitTracker::RegisterCell &lookup(unsigned VR) {
275 unsigned RInd = Register::virtReg2Index(VR);
276 // Grow the vector to at least 32 elements.
277 if (RInd >= CVect.size())
278 CVect.resize(std::max(RInd+16, 32U), nullptr);
279 const BitTracker::RegisterCell *CP = CVect[RInd];
280 if (CP == nullptr)
281 CP = CVect[RInd] = &BT.lookup(VR);
282 return *CP;
283 }
284
285 const BitTracker &BT;
286
287 private:
288 using CellVectType = std::vector<const BitTracker::RegisterCell *>;
289
290 CellVectType CVect;
291 };
292
293 // Comparator class for lexicographic ordering of virtual registers
294 // according to the corresponding BitTracker::RegisterCell objects.
295 struct RegisterCellLexCompare {
RegisterCellLexCompare__anon11a15ffe0211::RegisterCellLexCompare296 RegisterCellLexCompare(const BitValueOrdering &BO, CellMapShadow &M)
297 : BitOrd(BO), CM(M) {}
298
299 bool operator() (unsigned VR1, unsigned VR2) const;
300
301 private:
302 const BitValueOrdering &BitOrd;
303 CellMapShadow &CM;
304 };
305
306 // Comparator class for lexicographic ordering of virtual registers
307 // according to the specified bits of the corresponding BitTracker::
308 // RegisterCell objects.
309 // Specifically, this class will be used to compare bit B of a register
310 // cell for a selected virtual register R with bit N of any register
311 // other than R.
312 struct RegisterCellBitCompareSel {
RegisterCellBitCompareSel__anon11a15ffe0211::RegisterCellBitCompareSel313 RegisterCellBitCompareSel(unsigned R, unsigned B, unsigned N,
314 const BitValueOrdering &BO, CellMapShadow &M)
315 : SelR(R), SelB(B), BitN(N), BitOrd(BO), CM(M) {}
316
317 bool operator() (unsigned VR1, unsigned VR2) const;
318
319 private:
320 const unsigned SelR, SelB;
321 const unsigned BitN;
322 const BitValueOrdering &BitOrd;
323 CellMapShadow &CM;
324 };
325
326 } // end anonymous namespace
327
operator ()(unsigned VR1,unsigned VR2) const328 bool RegisterCellLexCompare::operator() (unsigned VR1, unsigned VR2) const {
329 // Ordering of registers, made up from two given orderings:
330 // - the ordering of the register numbers, and
331 // - the ordering of register cells.
332 // Def. R1 < R2 if:
333 // - cell(R1) < cell(R2), or
334 // - cell(R1) == cell(R2), and index(R1) < index(R2).
335 //
336 // For register cells, the ordering is lexicographic, with index 0 being
337 // the most significant.
338 if (VR1 == VR2)
339 return false;
340
341 const BitTracker::RegisterCell &RC1 = CM.lookup(VR1), &RC2 = CM.lookup(VR2);
342 uint16_t W1 = RC1.width(), W2 = RC2.width();
343 for (uint16_t i = 0, w = std::min(W1, W2); i < w; ++i) {
344 const BitTracker::BitValue &V1 = RC1[i], &V2 = RC2[i];
345 if (V1 != V2)
346 return BitOrd(V1, V2);
347 }
348 // Cells are equal up until the common length.
349 if (W1 != W2)
350 return W1 < W2;
351
352 return BitOrd.BaseOrd[VR1] < BitOrd.BaseOrd[VR2];
353 }
354
operator ()(unsigned VR1,unsigned VR2) const355 bool RegisterCellBitCompareSel::operator() (unsigned VR1, unsigned VR2) const {
356 if (VR1 == VR2)
357 return false;
358 const BitTracker::RegisterCell &RC1 = CM.lookup(VR1);
359 const BitTracker::RegisterCell &RC2 = CM.lookup(VR2);
360 uint16_t W1 = RC1.width(), W2 = RC2.width();
361 uint16_t Bit1 = (VR1 == SelR) ? SelB : BitN;
362 uint16_t Bit2 = (VR2 == SelR) ? SelB : BitN;
363 // If Bit1 exceeds the width of VR1, then:
364 // - return false, if at the same time Bit2 exceeds VR2, or
365 // - return true, otherwise.
366 // (I.e. "a bit value that does not exist is less than any bit value
367 // that does exist".)
368 if (W1 <= Bit1)
369 return Bit2 < W2;
370 // If Bit1 is within VR1, but Bit2 is not within VR2, return false.
371 if (W2 <= Bit2)
372 return false;
373
374 const BitTracker::BitValue &V1 = RC1[Bit1], V2 = RC2[Bit2];
375 if (V1 != V2)
376 return BitOrd(V1, V2);
377 return false;
378 }
379
380 namespace {
381
382 class OrderedRegisterList {
383 using ListType = std::vector<unsigned>;
384 const unsigned MaxSize;
385
386 public:
OrderedRegisterList(const RegisterOrdering & RO)387 OrderedRegisterList(const RegisterOrdering &RO)
388 : MaxSize(MaxORLSize), Ord(RO) {}
389
390 void insert(unsigned VR);
391 void remove(unsigned VR);
392
operator [](unsigned Idx) const393 unsigned operator[](unsigned Idx) const {
394 assert(Idx < Seq.size());
395 return Seq[Idx];
396 }
397
size() const398 unsigned size() const {
399 return Seq.size();
400 }
401
402 using iterator = ListType::iterator;
403 using const_iterator = ListType::const_iterator;
404
begin()405 iterator begin() { return Seq.begin(); }
end()406 iterator end() { return Seq.end(); }
begin() const407 const_iterator begin() const { return Seq.begin(); }
end() const408 const_iterator end() const { return Seq.end(); }
409
410 // Convenience function to convert an iterator to the corresponding index.
idx(iterator It) const411 unsigned idx(iterator It) const { return It-begin(); }
412
413 private:
414 ListType Seq;
415 const RegisterOrdering &Ord;
416 };
417
418 struct PrintORL {
PrintORL__anon11a15ffe0311::PrintORL419 PrintORL(const OrderedRegisterList &L, const TargetRegisterInfo *RI)
420 : RL(L), TRI(RI) {}
421
422 friend raw_ostream &operator<< (raw_ostream &OS, const PrintORL &P);
423
424 private:
425 const OrderedRegisterList &RL;
426 const TargetRegisterInfo *TRI;
427 };
428
operator <<(raw_ostream & OS,const PrintORL & P)429 raw_ostream &operator<< (raw_ostream &OS, const PrintORL &P) {
430 OS << '(';
431 OrderedRegisterList::const_iterator B = P.RL.begin(), E = P.RL.end();
432 for (OrderedRegisterList::const_iterator I = B; I != E; ++I) {
433 if (I != B)
434 OS << ", ";
435 OS << printReg(*I, P.TRI);
436 }
437 OS << ')';
438 return OS;
439 }
440
441 } // end anonymous namespace
442
insert(unsigned VR)443 void OrderedRegisterList::insert(unsigned VR) {
444 iterator L = llvm::lower_bound(Seq, VR, Ord);
445 if (L == Seq.end())
446 Seq.push_back(VR);
447 else
448 Seq.insert(L, VR);
449
450 unsigned S = Seq.size();
451 if (S > MaxSize)
452 Seq.resize(MaxSize);
453 assert(Seq.size() <= MaxSize);
454 }
455
remove(unsigned VR)456 void OrderedRegisterList::remove(unsigned VR) {
457 iterator L = llvm::lower_bound(Seq, VR, Ord);
458 if (L != Seq.end())
459 Seq.erase(L);
460 }
461
462 namespace {
463
464 // A record of the insert form. The fields correspond to the operands
465 // of the "insert" instruction:
466 // ... = insert(SrcR, InsR, #Wdh, #Off)
467 struct IFRecord {
IFRecord__anon11a15ffe0411::IFRecord468 IFRecord(unsigned SR = 0, unsigned IR = 0, uint16_t W = 0, uint16_t O = 0)
469 : SrcR(SR), InsR(IR), Wdh(W), Off(O) {}
470
471 unsigned SrcR, InsR;
472 uint16_t Wdh, Off;
473 };
474
475 struct PrintIFR {
PrintIFR__anon11a15ffe0411::PrintIFR476 PrintIFR(const IFRecord &R, const TargetRegisterInfo *RI)
477 : IFR(R), TRI(RI) {}
478
479 private:
480 friend raw_ostream &operator<< (raw_ostream &OS, const PrintIFR &P);
481
482 const IFRecord &IFR;
483 const TargetRegisterInfo *TRI;
484 };
485
operator <<(raw_ostream & OS,const PrintIFR & P)486 raw_ostream &operator<< (raw_ostream &OS, const PrintIFR &P) {
487 unsigned SrcR = P.IFR.SrcR, InsR = P.IFR.InsR;
488 OS << '(' << printReg(SrcR, P.TRI) << ',' << printReg(InsR, P.TRI)
489 << ",#" << P.IFR.Wdh << ",#" << P.IFR.Off << ')';
490 return OS;
491 }
492
493 using IFRecordWithRegSet = std::pair<IFRecord, RegisterSet>;
494
495 } // end anonymous namespace
496
497 namespace llvm {
498
499 void initializeHexagonGenInsertPass(PassRegistry&);
500 FunctionPass *createHexagonGenInsert();
501
502 } // end namespace llvm
503
504 namespace {
505
506 class HexagonGenInsert : public MachineFunctionPass {
507 public:
508 static char ID;
509
HexagonGenInsert()510 HexagonGenInsert() : MachineFunctionPass(ID) {
511 initializeHexagonGenInsertPass(*PassRegistry::getPassRegistry());
512 }
513
getPassName() const514 StringRef getPassName() const override {
515 return "Hexagon generate \"insert\" instructions";
516 }
517
getAnalysisUsage(AnalysisUsage & AU) const518 void getAnalysisUsage(AnalysisUsage &AU) const override {
519 AU.addRequired<MachineDominatorTree>();
520 AU.addPreserved<MachineDominatorTree>();
521 MachineFunctionPass::getAnalysisUsage(AU);
522 }
523
524 bool runOnMachineFunction(MachineFunction &MF) override;
525
526 private:
527 using PairMapType = DenseMap<std::pair<unsigned, unsigned>, unsigned>;
528
529 void buildOrderingMF(RegisterOrdering &RO) const;
530 void buildOrderingBT(RegisterOrdering &RB, RegisterOrdering &RO) const;
531 bool isIntClass(const TargetRegisterClass *RC) const;
532 bool isConstant(unsigned VR) const;
533 bool isSmallConstant(unsigned VR) const;
534 bool isValidInsertForm(unsigned DstR, unsigned SrcR, unsigned InsR,
535 uint16_t L, uint16_t S) const;
536 bool findSelfReference(unsigned VR) const;
537 bool findNonSelfReference(unsigned VR) const;
538 void getInstrDefs(const MachineInstr *MI, RegisterSet &Defs) const;
539 void getInstrUses(const MachineInstr *MI, RegisterSet &Uses) const;
540 unsigned distance(const MachineBasicBlock *FromB,
541 const MachineBasicBlock *ToB, const UnsignedMap &RPO,
542 PairMapType &M) const;
543 unsigned distance(MachineBasicBlock::const_iterator FromI,
544 MachineBasicBlock::const_iterator ToI, const UnsignedMap &RPO,
545 PairMapType &M) const;
546 bool findRecordInsertForms(unsigned VR, OrderedRegisterList &AVs);
547 void collectInBlock(MachineBasicBlock *B, OrderedRegisterList &AVs);
548 void findRemovableRegisters(unsigned VR, IFRecord IF,
549 RegisterSet &RMs) const;
550 void computeRemovableRegisters();
551
552 void pruneEmptyLists();
553 void pruneCoveredSets(unsigned VR);
554 void pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO, PairMapType &M);
555 void pruneRegCopies(unsigned VR);
556 void pruneCandidates();
557 void selectCandidates();
558 bool generateInserts();
559
560 bool removeDeadCode(MachineDomTreeNode *N);
561
562 // IFRecord coupled with a set of potentially removable registers:
563 using IFListType = std::vector<IFRecordWithRegSet>;
564 using IFMapType = DenseMap<unsigned, IFListType>; // vreg -> IFListType
565
566 void dump_map() const;
567
568 const HexagonInstrInfo *HII = nullptr;
569 const HexagonRegisterInfo *HRI = nullptr;
570
571 MachineFunction *MFN;
572 MachineRegisterInfo *MRI;
573 MachineDominatorTree *MDT;
574 CellMapShadow *CMS;
575
576 RegisterOrdering BaseOrd;
577 RegisterOrdering CellOrd;
578 IFMapType IFMap;
579 };
580
581 } // end anonymous namespace
582
583 char HexagonGenInsert::ID = 0;
584
dump_map() const585 void HexagonGenInsert::dump_map() const {
586 using iterator = IFMapType::const_iterator;
587
588 for (iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
589 dbgs() << " " << printReg(I->first, HRI) << ":\n";
590 const IFListType &LL = I->second;
591 for (unsigned i = 0, n = LL.size(); i < n; ++i)
592 dbgs() << " " << PrintIFR(LL[i].first, HRI) << ", "
593 << PrintRegSet(LL[i].second, HRI) << '\n';
594 }
595 }
596
buildOrderingMF(RegisterOrdering & RO) const597 void HexagonGenInsert::buildOrderingMF(RegisterOrdering &RO) const {
598 unsigned Index = 0;
599
600 using mf_iterator = MachineFunction::const_iterator;
601
602 for (mf_iterator A = MFN->begin(), Z = MFN->end(); A != Z; ++A) {
603 const MachineBasicBlock &B = *A;
604 if (!CMS->BT.reached(&B))
605 continue;
606
607 using mb_iterator = MachineBasicBlock::const_iterator;
608
609 for (mb_iterator I = B.begin(), E = B.end(); I != E; ++I) {
610 const MachineInstr *MI = &*I;
611 for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
612 const MachineOperand &MO = MI->getOperand(i);
613 if (MO.isReg() && MO.isDef()) {
614 Register R = MO.getReg();
615 assert(MO.getSubReg() == 0 && "Unexpected subregister in definition");
616 if (Register::isVirtualRegister(R))
617 RO.insert(std::make_pair(R, Index++));
618 }
619 }
620 }
621 }
622 // Since some virtual registers may have had their def and uses eliminated,
623 // they are no longer referenced in the code, and so they will not appear
624 // in the map.
625 }
626
buildOrderingBT(RegisterOrdering & RB,RegisterOrdering & RO) const627 void HexagonGenInsert::buildOrderingBT(RegisterOrdering &RB,
628 RegisterOrdering &RO) const {
629 // Create a vector of all virtual registers (collect them from the base
630 // ordering RB), and then sort it using the RegisterCell comparator.
631 BitValueOrdering BVO(RB);
632 RegisterCellLexCompare LexCmp(BVO, *CMS);
633
634 using SortableVectorType = std::vector<unsigned>;
635
636 SortableVectorType VRs;
637 for (RegisterOrdering::iterator I = RB.begin(), E = RB.end(); I != E; ++I)
638 VRs.push_back(I->first);
639 llvm::sort(VRs, LexCmp);
640 // Transfer the results to the outgoing register ordering.
641 for (unsigned i = 0, n = VRs.size(); i < n; ++i)
642 RO.insert(std::make_pair(VRs[i], i));
643 }
644
isIntClass(const TargetRegisterClass * RC) const645 inline bool HexagonGenInsert::isIntClass(const TargetRegisterClass *RC) const {
646 return RC == &Hexagon::IntRegsRegClass || RC == &Hexagon::DoubleRegsRegClass;
647 }
648
isConstant(unsigned VR) const649 bool HexagonGenInsert::isConstant(unsigned VR) const {
650 const BitTracker::RegisterCell &RC = CMS->lookup(VR);
651 uint16_t W = RC.width();
652 for (uint16_t i = 0; i < W; ++i) {
653 const BitTracker::BitValue &BV = RC[i];
654 if (BV.is(0) || BV.is(1))
655 continue;
656 return false;
657 }
658 return true;
659 }
660
isSmallConstant(unsigned VR) const661 bool HexagonGenInsert::isSmallConstant(unsigned VR) const {
662 const BitTracker::RegisterCell &RC = CMS->lookup(VR);
663 uint16_t W = RC.width();
664 if (W > 64)
665 return false;
666 uint64_t V = 0, B = 1;
667 for (uint16_t i = 0; i < W; ++i) {
668 const BitTracker::BitValue &BV = RC[i];
669 if (BV.is(1))
670 V |= B;
671 else if (!BV.is(0))
672 return false;
673 B <<= 1;
674 }
675
676 // For 32-bit registers, consider: Rd = #s16.
677 if (W == 32)
678 return isInt<16>(V);
679
680 // For 64-bit registers, it's Rdd = #s8 or Rdd = combine(#s8,#s8)
681 return isInt<8>(Lo_32(V)) && isInt<8>(Hi_32(V));
682 }
683
isValidInsertForm(unsigned DstR,unsigned SrcR,unsigned InsR,uint16_t L,uint16_t S) const684 bool HexagonGenInsert::isValidInsertForm(unsigned DstR, unsigned SrcR,
685 unsigned InsR, uint16_t L, uint16_t S) const {
686 const TargetRegisterClass *DstRC = MRI->getRegClass(DstR);
687 const TargetRegisterClass *SrcRC = MRI->getRegClass(SrcR);
688 const TargetRegisterClass *InsRC = MRI->getRegClass(InsR);
689 // Only integet (32-/64-bit) register classes.
690 if (!isIntClass(DstRC) || !isIntClass(SrcRC) || !isIntClass(InsRC))
691 return false;
692 // The "source" register must be of the same class as DstR.
693 if (DstRC != SrcRC)
694 return false;
695 if (DstRC == InsRC)
696 return true;
697 // A 64-bit register can only be generated from other 64-bit registers.
698 if (DstRC == &Hexagon::DoubleRegsRegClass)
699 return false;
700 // Otherwise, the L and S cannot span 32-bit word boundary.
701 if (S < 32 && S+L > 32)
702 return false;
703 return true;
704 }
705
findSelfReference(unsigned VR) const706 bool HexagonGenInsert::findSelfReference(unsigned VR) const {
707 const BitTracker::RegisterCell &RC = CMS->lookup(VR);
708 for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
709 const BitTracker::BitValue &V = RC[i];
710 if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg == VR)
711 return true;
712 }
713 return false;
714 }
715
findNonSelfReference(unsigned VR) const716 bool HexagonGenInsert::findNonSelfReference(unsigned VR) const {
717 BitTracker::RegisterCell RC = CMS->lookup(VR);
718 for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
719 const BitTracker::BitValue &V = RC[i];
720 if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg != VR)
721 return true;
722 }
723 return false;
724 }
725
getInstrDefs(const MachineInstr * MI,RegisterSet & Defs) const726 void HexagonGenInsert::getInstrDefs(const MachineInstr *MI,
727 RegisterSet &Defs) const {
728 for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
729 const MachineOperand &MO = MI->getOperand(i);
730 if (!MO.isReg() || !MO.isDef())
731 continue;
732 Register R = MO.getReg();
733 if (!Register::isVirtualRegister(R))
734 continue;
735 Defs.insert(R);
736 }
737 }
738
getInstrUses(const MachineInstr * MI,RegisterSet & Uses) const739 void HexagonGenInsert::getInstrUses(const MachineInstr *MI,
740 RegisterSet &Uses) const {
741 for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
742 const MachineOperand &MO = MI->getOperand(i);
743 if (!MO.isReg() || !MO.isUse())
744 continue;
745 Register R = MO.getReg();
746 if (!Register::isVirtualRegister(R))
747 continue;
748 Uses.insert(R);
749 }
750 }
751
distance(const MachineBasicBlock * FromB,const MachineBasicBlock * ToB,const UnsignedMap & RPO,PairMapType & M) const752 unsigned HexagonGenInsert::distance(const MachineBasicBlock *FromB,
753 const MachineBasicBlock *ToB, const UnsignedMap &RPO,
754 PairMapType &M) const {
755 // Forward distance from the end of a block to the beginning of it does
756 // not make sense. This function should not be called with FromB == ToB.
757 assert(FromB != ToB);
758
759 unsigned FromN = FromB->getNumber(), ToN = ToB->getNumber();
760 // If we have already computed it, return the cached result.
761 PairMapType::iterator F = M.find(std::make_pair(FromN, ToN));
762 if (F != M.end())
763 return F->second;
764 unsigned ToRPO = RPO.lookup(ToN);
765
766 unsigned MaxD = 0;
767
768 using pred_iterator = MachineBasicBlock::const_pred_iterator;
769
770 for (pred_iterator I = ToB->pred_begin(), E = ToB->pred_end(); I != E; ++I) {
771 const MachineBasicBlock *PB = *I;
772 // Skip back edges. Also, if FromB is a predecessor of ToB, the distance
773 // along that path will be 0, and we don't need to do any calculations
774 // on it.
775 if (PB == FromB || RPO.lookup(PB->getNumber()) >= ToRPO)
776 continue;
777 unsigned D = PB->size() + distance(FromB, PB, RPO, M);
778 if (D > MaxD)
779 MaxD = D;
780 }
781
782 // Memoize the result for later lookup.
783 M.insert(std::make_pair(std::make_pair(FromN, ToN), MaxD));
784 return MaxD;
785 }
786
distance(MachineBasicBlock::const_iterator FromI,MachineBasicBlock::const_iterator ToI,const UnsignedMap & RPO,PairMapType & M) const787 unsigned HexagonGenInsert::distance(MachineBasicBlock::const_iterator FromI,
788 MachineBasicBlock::const_iterator ToI, const UnsignedMap &RPO,
789 PairMapType &M) const {
790 const MachineBasicBlock *FB = FromI->getParent(), *TB = ToI->getParent();
791 if (FB == TB)
792 return std::distance(FromI, ToI);
793 unsigned D1 = std::distance(TB->begin(), ToI);
794 unsigned D2 = distance(FB, TB, RPO, M);
795 unsigned D3 = std::distance(FromI, FB->end());
796 return D1+D2+D3;
797 }
798
findRecordInsertForms(unsigned VR,OrderedRegisterList & AVs)799 bool HexagonGenInsert::findRecordInsertForms(unsigned VR,
800 OrderedRegisterList &AVs) {
801 if (isDebug()) {
802 dbgs() << __func__ << ": " << printReg(VR, HRI)
803 << " AVs: " << PrintORL(AVs, HRI) << "\n";
804 }
805 if (AVs.size() == 0)
806 return false;
807
808 using iterator = OrderedRegisterList::iterator;
809
810 BitValueOrdering BVO(BaseOrd);
811 const BitTracker::RegisterCell &RC = CMS->lookup(VR);
812 uint16_t W = RC.width();
813
814 using RSRecord = std::pair<unsigned, uint16_t>; // (reg,shift)
815 using RSListType = std::vector<RSRecord>;
816 // Have a map, with key being the matching prefix length, and the value
817 // being the list of pairs (R,S), where R's prefix matches VR at S.
818 // (DenseMap<uint16_t,RSListType> fails to instantiate.)
819 using LRSMapType = DenseMap<unsigned, RSListType>;
820 LRSMapType LM;
821
822 // Conceptually, rotate the cell RC right (i.e. towards the LSB) by S,
823 // and find matching prefixes from AVs with the rotated RC. Such a prefix
824 // would match a string of bits (of length L) in RC starting at S.
825 for (uint16_t S = 0; S < W; ++S) {
826 iterator B = AVs.begin(), E = AVs.end();
827 // The registers in AVs are ordered according to the lexical order of
828 // the corresponding register cells. This means that the range of regis-
829 // ters in AVs that match a prefix of length L+1 will be contained in
830 // the range that matches a prefix of length L. This means that we can
831 // keep narrowing the search space as the prefix length goes up. This
832 // helps reduce the overall complexity of the search.
833 uint16_t L;
834 for (L = 0; L < W-S; ++L) {
835 // Compare against VR's bits starting at S, which emulates rotation
836 // of VR by S.
837 RegisterCellBitCompareSel RCB(VR, S+L, L, BVO, *CMS);
838 iterator NewB = std::lower_bound(B, E, VR, RCB);
839 iterator NewE = std::upper_bound(NewB, E, VR, RCB);
840 // For the registers that are eliminated from the next range, L is
841 // the longest prefix matching VR at position S (their prefixes
842 // differ from VR at S+L). If L>0, record this information for later
843 // use.
844 if (L > 0) {
845 for (iterator I = B; I != NewB; ++I)
846 LM[L].push_back(std::make_pair(*I, S));
847 for (iterator I = NewE; I != E; ++I)
848 LM[L].push_back(std::make_pair(*I, S));
849 }
850 B = NewB, E = NewE;
851 if (B == E)
852 break;
853 }
854 // Record the final register range. If this range is non-empty, then
855 // L=W-S.
856 assert(B == E || L == W-S);
857 if (B != E) {
858 for (iterator I = B; I != E; ++I)
859 LM[L].push_back(std::make_pair(*I, S));
860 // If B!=E, then we found a range of registers whose prefixes cover the
861 // rest of VR from position S. There is no need to further advance S.
862 break;
863 }
864 }
865
866 if (isDebug()) {
867 dbgs() << "Prefixes matching register " << printReg(VR, HRI) << "\n";
868 for (LRSMapType::iterator I = LM.begin(), E = LM.end(); I != E; ++I) {
869 dbgs() << " L=" << I->first << ':';
870 const RSListType &LL = I->second;
871 for (unsigned i = 0, n = LL.size(); i < n; ++i)
872 dbgs() << " (" << printReg(LL[i].first, HRI) << ",@"
873 << LL[i].second << ')';
874 dbgs() << '\n';
875 }
876 }
877
878 bool Recorded = false;
879
880 for (iterator I = AVs.begin(), E = AVs.end(); I != E; ++I) {
881 unsigned SrcR = *I;
882 int FDi = -1, LDi = -1; // First/last different bit.
883 const BitTracker::RegisterCell &AC = CMS->lookup(SrcR);
884 uint16_t AW = AC.width();
885 for (uint16_t i = 0, w = std::min(W, AW); i < w; ++i) {
886 if (RC[i] == AC[i])
887 continue;
888 if (FDi == -1)
889 FDi = i;
890 LDi = i;
891 }
892 if (FDi == -1)
893 continue; // TODO (future): Record identical registers.
894 // Look for a register whose prefix could patch the range [FD..LD]
895 // where VR and SrcR differ.
896 uint16_t FD = FDi, LD = LDi; // Switch to unsigned type.
897 uint16_t MinL = LD-FD+1;
898 for (uint16_t L = MinL; L < W; ++L) {
899 LRSMapType::iterator F = LM.find(L);
900 if (F == LM.end())
901 continue;
902 RSListType &LL = F->second;
903 for (unsigned i = 0, n = LL.size(); i < n; ++i) {
904 uint16_t S = LL[i].second;
905 // MinL is the minimum length of the prefix. Any length above MinL
906 // allows some flexibility as to where the prefix can start:
907 // given the extra length EL=L-MinL, the prefix must start between
908 // max(0,FD-EL) and FD.
909 if (S > FD) // Starts too late.
910 continue;
911 uint16_t EL = L-MinL;
912 uint16_t LowS = (EL < FD) ? FD-EL : 0;
913 if (S < LowS) // Starts too early.
914 continue;
915 unsigned InsR = LL[i].first;
916 if (!isValidInsertForm(VR, SrcR, InsR, L, S))
917 continue;
918 if (isDebug()) {
919 dbgs() << printReg(VR, HRI) << " = insert(" << printReg(SrcR, HRI)
920 << ',' << printReg(InsR, HRI) << ",#" << L << ",#"
921 << S << ")\n";
922 }
923 IFRecordWithRegSet RR(IFRecord(SrcR, InsR, L, S), RegisterSet());
924 IFMap[VR].push_back(RR);
925 Recorded = true;
926 }
927 }
928 }
929
930 return Recorded;
931 }
932
collectInBlock(MachineBasicBlock * B,OrderedRegisterList & AVs)933 void HexagonGenInsert::collectInBlock(MachineBasicBlock *B,
934 OrderedRegisterList &AVs) {
935 if (isDebug())
936 dbgs() << "visiting block " << printMBBReference(*B) << "\n";
937
938 // First, check if this block is reachable at all. If not, the bit tracker
939 // will not have any information about registers in it.
940 if (!CMS->BT.reached(B))
941 return;
942
943 bool DoConst = OptConst;
944 // Keep a separate set of registers defined in this block, so that we
945 // can remove them from the list of available registers once all DT
946 // successors have been processed.
947 RegisterSet BlockDefs, InsDefs;
948 for (MachineBasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) {
949 MachineInstr *MI = &*I;
950 InsDefs.clear();
951 getInstrDefs(MI, InsDefs);
952 // Leave those alone. They are more transparent than "insert".
953 bool Skip = MI->isCopy() || MI->isRegSequence();
954
955 if (!Skip) {
956 // Visit all defined registers, and attempt to find the corresponding
957 // "insert" representations.
958 for (unsigned VR = InsDefs.find_first(); VR; VR = InsDefs.find_next(VR)) {
959 // Do not collect registers that are known to be compile-time cons-
960 // tants, unless requested.
961 if (!DoConst && isConstant(VR))
962 continue;
963 // If VR's cell contains a reference to VR, then VR cannot be defined
964 // via "insert". If VR is a constant that can be generated in a single
965 // instruction (without constant extenders), generating it via insert
966 // makes no sense.
967 if (findSelfReference(VR) || isSmallConstant(VR))
968 continue;
969
970 findRecordInsertForms(VR, AVs);
971 // Stop if the map size is too large.
972 if (IFMap.size() > MaxIFMSize)
973 return;
974 }
975 }
976
977 // Insert the defined registers into the list of available registers
978 // after they have been processed.
979 for (unsigned VR = InsDefs.find_first(); VR; VR = InsDefs.find_next(VR))
980 AVs.insert(VR);
981 BlockDefs.insert(InsDefs);
982 }
983
984 for (auto *DTN : children<MachineDomTreeNode*>(MDT->getNode(B))) {
985 MachineBasicBlock *SB = DTN->getBlock();
986 collectInBlock(SB, AVs);
987 }
988
989 for (unsigned VR = BlockDefs.find_first(); VR; VR = BlockDefs.find_next(VR))
990 AVs.remove(VR);
991 }
992
findRemovableRegisters(unsigned VR,IFRecord IF,RegisterSet & RMs) const993 void HexagonGenInsert::findRemovableRegisters(unsigned VR, IFRecord IF,
994 RegisterSet &RMs) const {
995 // For a given register VR and a insert form, find the registers that are
996 // used by the current definition of VR, and which would no longer be
997 // needed for it after the definition of VR is replaced with the insert
998 // form. These are the registers that could potentially become dead.
999 RegisterSet Regs[2];
1000
1001 unsigned S = 0; // Register set selector.
1002 Regs[S].insert(VR);
1003
1004 while (!Regs[S].empty()) {
1005 // Breadth-first search.
1006 unsigned OtherS = 1-S;
1007 Regs[OtherS].clear();
1008 for (unsigned R = Regs[S].find_first(); R; R = Regs[S].find_next(R)) {
1009 Regs[S].remove(R);
1010 if (R == IF.SrcR || R == IF.InsR)
1011 continue;
1012 // Check if a given register has bits that are references to any other
1013 // registers. This is to detect situations where the instruction that
1014 // defines register R takes register Q as an operand, but R itself does
1015 // not contain any bits from Q. Loads are examples of how this could
1016 // happen:
1017 // R = load Q
1018 // In this case (assuming we do not have any knowledge about the loaded
1019 // value), we must not treat R as a "conveyance" of the bits from Q.
1020 // (The information in BT about R's bits would have them as constants,
1021 // in case of zero-extending loads, or refs to R.)
1022 if (!findNonSelfReference(R))
1023 continue;
1024 RMs.insert(R);
1025 const MachineInstr *DefI = MRI->getVRegDef(R);
1026 assert(DefI);
1027 // Do not iterate past PHI nodes to avoid infinite loops. This can
1028 // make the final set a bit less accurate, but the removable register
1029 // sets are an approximation anyway.
1030 if (DefI->isPHI())
1031 continue;
1032 getInstrUses(DefI, Regs[OtherS]);
1033 }
1034 S = OtherS;
1035 }
1036 // The register VR is added to the list as a side-effect of the algorithm,
1037 // but it is not "potentially removable". A potentially removable register
1038 // is one that may become unused (dead) after conversion to the insert form
1039 // IF, and obviously VR (or its replacement) will not become dead by apply-
1040 // ing IF.
1041 RMs.remove(VR);
1042 }
1043
computeRemovableRegisters()1044 void HexagonGenInsert::computeRemovableRegisters() {
1045 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1046 IFListType &LL = I->second;
1047 for (unsigned i = 0, n = LL.size(); i < n; ++i)
1048 findRemovableRegisters(I->first, LL[i].first, LL[i].second);
1049 }
1050 }
1051
pruneEmptyLists()1052 void HexagonGenInsert::pruneEmptyLists() {
1053 // Remove all entries from the map, where the register has no insert forms
1054 // associated with it.
1055 using IterListType = SmallVector<IFMapType::iterator, 16>;
1056 IterListType Prune;
1057 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1058 if (I->second.empty())
1059 Prune.push_back(I);
1060 }
1061 for (unsigned i = 0, n = Prune.size(); i < n; ++i)
1062 IFMap.erase(Prune[i]);
1063 }
1064
pruneCoveredSets(unsigned VR)1065 void HexagonGenInsert::pruneCoveredSets(unsigned VR) {
1066 IFMapType::iterator F = IFMap.find(VR);
1067 assert(F != IFMap.end());
1068 IFListType &LL = F->second;
1069
1070 // First, examine the IF candidates for register VR whose removable-regis-
1071 // ter sets are empty. This means that a given candidate will not help eli-
1072 // minate any registers, but since "insert" is not a constant-extendable
1073 // instruction, using such a candidate may reduce code size if the defini-
1074 // tion of VR is constant-extended.
1075 // If there exists a candidate with a non-empty set, the ones with empty
1076 // sets will not be used and can be removed.
1077 MachineInstr *DefVR = MRI->getVRegDef(VR);
1078 bool DefEx = HII->isConstExtended(*DefVR);
1079 bool HasNE = false;
1080 for (unsigned i = 0, n = LL.size(); i < n; ++i) {
1081 if (LL[i].second.empty())
1082 continue;
1083 HasNE = true;
1084 break;
1085 }
1086 if (!DefEx || HasNE) {
1087 // The definition of VR is not constant-extended, or there is a candidate
1088 // with a non-empty set. Remove all candidates with empty sets.
1089 auto IsEmpty = [] (const IFRecordWithRegSet &IR) -> bool {
1090 return IR.second.empty();
1091 };
1092 auto End = llvm::remove_if(LL, IsEmpty);
1093 if (End != LL.end())
1094 LL.erase(End, LL.end());
1095 } else {
1096 // The definition of VR is constant-extended, and all candidates have
1097 // empty removable-register sets. Pick the maximum candidate, and remove
1098 // all others. The "maximum" does not have any special meaning here, it
1099 // is only so that the candidate that will remain on the list is selec-
1100 // ted deterministically.
1101 IFRecord MaxIF = LL[0].first;
1102 for (unsigned i = 1, n = LL.size(); i < n; ++i) {
1103 // If LL[MaxI] < LL[i], then MaxI = i.
1104 const IFRecord &IF = LL[i].first;
1105 unsigned M0 = BaseOrd[MaxIF.SrcR], M1 = BaseOrd[MaxIF.InsR];
1106 unsigned R0 = BaseOrd[IF.SrcR], R1 = BaseOrd[IF.InsR];
1107 if (M0 > R0)
1108 continue;
1109 if (M0 == R0) {
1110 if (M1 > R1)
1111 continue;
1112 if (M1 == R1) {
1113 if (MaxIF.Wdh > IF.Wdh)
1114 continue;
1115 if (MaxIF.Wdh == IF.Wdh && MaxIF.Off >= IF.Off)
1116 continue;
1117 }
1118 }
1119 // MaxIF < IF.
1120 MaxIF = IF;
1121 }
1122 // Remove everything except the maximum candidate. All register sets
1123 // are empty, so no need to preserve anything.
1124 LL.clear();
1125 LL.push_back(std::make_pair(MaxIF, RegisterSet()));
1126 }
1127
1128 // Now, remove those whose sets of potentially removable registers are
1129 // contained in another IF candidate for VR. For example, given these
1130 // candidates for %45,
1131 // %45:
1132 // (%44,%41,#9,#8), { %42 }
1133 // (%43,%41,#9,#8), { %42 %44 }
1134 // remove the first one, since it is contained in the second one.
1135 for (unsigned i = 0, n = LL.size(); i < n; ) {
1136 const RegisterSet &RMi = LL[i].second;
1137 unsigned j = 0;
1138 while (j < n) {
1139 if (j != i && LL[j].second.includes(RMi))
1140 break;
1141 j++;
1142 }
1143 if (j == n) { // RMi not contained in anything else.
1144 i++;
1145 continue;
1146 }
1147 LL.erase(LL.begin()+i);
1148 n = LL.size();
1149 }
1150 }
1151
pruneUsesTooFar(unsigned VR,const UnsignedMap & RPO,PairMapType & M)1152 void HexagonGenInsert::pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO,
1153 PairMapType &M) {
1154 IFMapType::iterator F = IFMap.find(VR);
1155 assert(F != IFMap.end());
1156 IFListType &LL = F->second;
1157 unsigned Cutoff = VRegDistCutoff;
1158 const MachineInstr *DefV = MRI->getVRegDef(VR);
1159
1160 for (unsigned i = LL.size(); i > 0; --i) {
1161 unsigned SR = LL[i-1].first.SrcR, IR = LL[i-1].first.InsR;
1162 const MachineInstr *DefS = MRI->getVRegDef(SR);
1163 const MachineInstr *DefI = MRI->getVRegDef(IR);
1164 unsigned DSV = distance(DefS, DefV, RPO, M);
1165 if (DSV < Cutoff) {
1166 unsigned DIV = distance(DefI, DefV, RPO, M);
1167 if (DIV < Cutoff)
1168 continue;
1169 }
1170 LL.erase(LL.begin()+(i-1));
1171 }
1172 }
1173
pruneRegCopies(unsigned VR)1174 void HexagonGenInsert::pruneRegCopies(unsigned VR) {
1175 IFMapType::iterator F = IFMap.find(VR);
1176 assert(F != IFMap.end());
1177 IFListType &LL = F->second;
1178
1179 auto IsCopy = [] (const IFRecordWithRegSet &IR) -> bool {
1180 return IR.first.Wdh == 32 && (IR.first.Off == 0 || IR.first.Off == 32);
1181 };
1182 auto End = llvm::remove_if(LL, IsCopy);
1183 if (End != LL.end())
1184 LL.erase(End, LL.end());
1185 }
1186
pruneCandidates()1187 void HexagonGenInsert::pruneCandidates() {
1188 // Remove candidates that are not beneficial, regardless of the final
1189 // selection method.
1190 // First, remove candidates whose potentially removable set is a subset
1191 // of another candidate's set.
1192 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I)
1193 pruneCoveredSets(I->first);
1194
1195 UnsignedMap RPO;
1196
1197 using RPOTType = ReversePostOrderTraversal<const MachineFunction *>;
1198
1199 RPOTType RPOT(MFN);
1200 unsigned RPON = 0;
1201 for (RPOTType::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I)
1202 RPO[(*I)->getNumber()] = RPON++;
1203
1204 PairMapType Memo; // Memoization map for distance calculation.
1205 // Remove candidates that would use registers defined too far away.
1206 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I)
1207 pruneUsesTooFar(I->first, RPO, Memo);
1208
1209 pruneEmptyLists();
1210
1211 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I)
1212 pruneRegCopies(I->first);
1213 }
1214
1215 namespace {
1216
1217 // Class for comparing IF candidates for registers that have multiple of
1218 // them. The smaller the candidate, according to this ordering, the better.
1219 // First, compare the number of zeros in the associated potentially remova-
1220 // ble register sets. "Zero" indicates that the register is very likely to
1221 // become dead after this transformation.
1222 // Second, compare "averages", i.e. use-count per size. The lower wins.
1223 // After that, it does not really matter which one is smaller. Resolve
1224 // the tie in some deterministic way.
1225 struct IFOrdering {
IFOrdering__anon11a15ffe0811::IFOrdering1226 IFOrdering(const UnsignedMap &UC, const RegisterOrdering &BO)
1227 : UseC(UC), BaseOrd(BO) {}
1228
1229 bool operator() (const IFRecordWithRegSet &A,
1230 const IFRecordWithRegSet &B) const;
1231
1232 private:
1233 void stats(const RegisterSet &Rs, unsigned &Size, unsigned &Zero,
1234 unsigned &Sum) const;
1235
1236 const UnsignedMap &UseC;
1237 const RegisterOrdering &BaseOrd;
1238 };
1239
1240 } // end anonymous namespace
1241
operator ()(const IFRecordWithRegSet & A,const IFRecordWithRegSet & B) const1242 bool IFOrdering::operator() (const IFRecordWithRegSet &A,
1243 const IFRecordWithRegSet &B) const {
1244 unsigned SizeA = 0, ZeroA = 0, SumA = 0;
1245 unsigned SizeB = 0, ZeroB = 0, SumB = 0;
1246 stats(A.second, SizeA, ZeroA, SumA);
1247 stats(B.second, SizeB, ZeroB, SumB);
1248
1249 // We will pick the minimum element. The more zeros, the better.
1250 if (ZeroA != ZeroB)
1251 return ZeroA > ZeroB;
1252 // Compare SumA/SizeA with SumB/SizeB, lower is better.
1253 uint64_t AvgA = SumA*SizeB, AvgB = SumB*SizeA;
1254 if (AvgA != AvgB)
1255 return AvgA < AvgB;
1256
1257 // The sets compare identical so far. Resort to comparing the IF records.
1258 // The actual values don't matter, this is only for determinism.
1259 unsigned OSA = BaseOrd[A.first.SrcR], OSB = BaseOrd[B.first.SrcR];
1260 if (OSA != OSB)
1261 return OSA < OSB;
1262 unsigned OIA = BaseOrd[A.first.InsR], OIB = BaseOrd[B.first.InsR];
1263 if (OIA != OIB)
1264 return OIA < OIB;
1265 if (A.first.Wdh != B.first.Wdh)
1266 return A.first.Wdh < B.first.Wdh;
1267 return A.first.Off < B.first.Off;
1268 }
1269
stats(const RegisterSet & Rs,unsigned & Size,unsigned & Zero,unsigned & Sum) const1270 void IFOrdering::stats(const RegisterSet &Rs, unsigned &Size, unsigned &Zero,
1271 unsigned &Sum) const {
1272 for (unsigned R = Rs.find_first(); R; R = Rs.find_next(R)) {
1273 UnsignedMap::const_iterator F = UseC.find(R);
1274 assert(F != UseC.end());
1275 unsigned UC = F->second;
1276 if (UC == 0)
1277 Zero++;
1278 Sum += UC;
1279 Size++;
1280 }
1281 }
1282
selectCandidates()1283 void HexagonGenInsert::selectCandidates() {
1284 // Some registers may have multiple valid candidates. Pick the best one
1285 // (or decide not to use any).
1286
1287 // Compute the "removability" measure of R:
1288 // For each potentially removable register R, record the number of regis-
1289 // ters with IF candidates, where R appears in at least one set.
1290 RegisterSet AllRMs;
1291 UnsignedMap UseC, RemC;
1292 IFMapType::iterator End = IFMap.end();
1293
1294 for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
1295 const IFListType &LL = I->second;
1296 RegisterSet TT;
1297 for (unsigned i = 0, n = LL.size(); i < n; ++i)
1298 TT.insert(LL[i].second);
1299 for (unsigned R = TT.find_first(); R; R = TT.find_next(R))
1300 RemC[R]++;
1301 AllRMs.insert(TT);
1302 }
1303
1304 for (unsigned R = AllRMs.find_first(); R; R = AllRMs.find_next(R)) {
1305 using use_iterator = MachineRegisterInfo::use_nodbg_iterator;
1306 using InstrSet = SmallSet<const MachineInstr *, 16>;
1307
1308 InstrSet UIs;
1309 // Count as the number of instructions in which R is used, not the
1310 // number of operands.
1311 use_iterator E = MRI->use_nodbg_end();
1312 for (use_iterator I = MRI->use_nodbg_begin(R); I != E; ++I)
1313 UIs.insert(I->getParent());
1314 unsigned C = UIs.size();
1315 // Calculate a measure, which is the number of instructions using R,
1316 // minus the "removability" count computed earlier.
1317 unsigned D = RemC[R];
1318 UseC[R] = (C > D) ? C-D : 0; // doz
1319 }
1320
1321 bool SelectAll0 = OptSelectAll0, SelectHas0 = OptSelectHas0;
1322 if (!SelectAll0 && !SelectHas0)
1323 SelectAll0 = true;
1324
1325 // The smaller the number UseC for a given register R, the "less used"
1326 // R is aside from the opportunities for removal offered by generating
1327 // "insert" instructions.
1328 // Iterate over the IF map, and for those registers that have multiple
1329 // candidates, pick the minimum one according to IFOrdering.
1330 IFOrdering IFO(UseC, BaseOrd);
1331 for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
1332 IFListType &LL = I->second;
1333 if (LL.empty())
1334 continue;
1335 // Get the minimum element, remember it and clear the list. If the
1336 // element found is adequate, we will put it back on the list, other-
1337 // wise the list will remain empty, and the entry for this register
1338 // will be removed (i.e. this register will not be replaced by insert).
1339 IFListType::iterator MinI = std::min_element(LL.begin(), LL.end(), IFO);
1340 assert(MinI != LL.end());
1341 IFRecordWithRegSet M = *MinI;
1342 LL.clear();
1343
1344 // We want to make sure that this replacement will have a chance to be
1345 // beneficial, and that means that we want to have indication that some
1346 // register will be removed. The most likely registers to be eliminated
1347 // are the use operands in the definition of I->first. Accept/reject a
1348 // candidate based on how many of its uses it can potentially eliminate.
1349
1350 RegisterSet Us;
1351 const MachineInstr *DefI = MRI->getVRegDef(I->first);
1352 getInstrUses(DefI, Us);
1353 bool Accept = false;
1354
1355 if (SelectAll0) {
1356 bool All0 = true;
1357 for (unsigned R = Us.find_first(); R; R = Us.find_next(R)) {
1358 if (UseC[R] == 0)
1359 continue;
1360 All0 = false;
1361 break;
1362 }
1363 Accept = All0;
1364 } else if (SelectHas0) {
1365 bool Has0 = false;
1366 for (unsigned R = Us.find_first(); R; R = Us.find_next(R)) {
1367 if (UseC[R] != 0)
1368 continue;
1369 Has0 = true;
1370 break;
1371 }
1372 Accept = Has0;
1373 }
1374 if (Accept)
1375 LL.push_back(M);
1376 }
1377
1378 // Remove candidates that add uses of removable registers, unless the
1379 // removable registers are among replacement candidates.
1380 // Recompute the removable registers, since some candidates may have
1381 // been eliminated.
1382 AllRMs.clear();
1383 for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
1384 const IFListType &LL = I->second;
1385 if (!LL.empty())
1386 AllRMs.insert(LL[0].second);
1387 }
1388 for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
1389 IFListType &LL = I->second;
1390 if (LL.empty())
1391 continue;
1392 unsigned SR = LL[0].first.SrcR, IR = LL[0].first.InsR;
1393 if (AllRMs[SR] || AllRMs[IR])
1394 LL.clear();
1395 }
1396
1397 pruneEmptyLists();
1398 }
1399
generateInserts()1400 bool HexagonGenInsert::generateInserts() {
1401 // Create a new register for each one from IFMap, and store them in the
1402 // map.
1403 UnsignedMap RegMap;
1404 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1405 unsigned VR = I->first;
1406 const TargetRegisterClass *RC = MRI->getRegClass(VR);
1407 Register NewVR = MRI->createVirtualRegister(RC);
1408 RegMap[VR] = NewVR;
1409 }
1410
1411 // We can generate the "insert" instructions using potentially stale re-
1412 // gisters: SrcR and InsR for a given VR may be among other registers that
1413 // are also replaced. This is fine, we will do the mass "rauw" a bit later.
1414 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1415 MachineInstr *MI = MRI->getVRegDef(I->first);
1416 MachineBasicBlock &B = *MI->getParent();
1417 DebugLoc DL = MI->getDebugLoc();
1418 unsigned NewR = RegMap[I->first];
1419 bool R32 = MRI->getRegClass(NewR) == &Hexagon::IntRegsRegClass;
1420 const MCInstrDesc &D = R32 ? HII->get(Hexagon::S2_insert)
1421 : HII->get(Hexagon::S2_insertp);
1422 IFRecord IF = I->second[0].first;
1423 unsigned Wdh = IF.Wdh, Off = IF.Off;
1424 unsigned InsS = 0;
1425 if (R32 && MRI->getRegClass(IF.InsR) == &Hexagon::DoubleRegsRegClass) {
1426 InsS = Hexagon::isub_lo;
1427 if (Off >= 32) {
1428 InsS = Hexagon::isub_hi;
1429 Off -= 32;
1430 }
1431 }
1432 // Advance to the proper location for inserting instructions. This could
1433 // be B.end().
1434 MachineBasicBlock::iterator At = MI;
1435 if (MI->isPHI())
1436 At = B.getFirstNonPHI();
1437
1438 BuildMI(B, At, DL, D, NewR)
1439 .addReg(IF.SrcR)
1440 .addReg(IF.InsR, 0, InsS)
1441 .addImm(Wdh)
1442 .addImm(Off);
1443
1444 MRI->clearKillFlags(IF.SrcR);
1445 MRI->clearKillFlags(IF.InsR);
1446 }
1447
1448 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1449 MachineInstr *DefI = MRI->getVRegDef(I->first);
1450 MRI->replaceRegWith(I->first, RegMap[I->first]);
1451 DefI->eraseFromParent();
1452 }
1453
1454 return true;
1455 }
1456
removeDeadCode(MachineDomTreeNode * N)1457 bool HexagonGenInsert::removeDeadCode(MachineDomTreeNode *N) {
1458 bool Changed = false;
1459
1460 for (auto *DTN : children<MachineDomTreeNode*>(N))
1461 Changed |= removeDeadCode(DTN);
1462
1463 MachineBasicBlock *B = N->getBlock();
1464 std::vector<MachineInstr*> Instrs;
1465 for (auto I = B->rbegin(), E = B->rend(); I != E; ++I)
1466 Instrs.push_back(&*I);
1467
1468 for (auto I = Instrs.begin(), E = Instrs.end(); I != E; ++I) {
1469 MachineInstr *MI = *I;
1470 unsigned Opc = MI->getOpcode();
1471 // Do not touch lifetime markers. This is why the target-independent DCE
1472 // cannot be used.
1473 if (Opc == TargetOpcode::LIFETIME_START ||
1474 Opc == TargetOpcode::LIFETIME_END)
1475 continue;
1476 bool Store = false;
1477 if (MI->isInlineAsm() || !MI->isSafeToMove(nullptr, Store))
1478 continue;
1479
1480 bool AllDead = true;
1481 SmallVector<unsigned,2> Regs;
1482 for (const MachineOperand &MO : MI->operands()) {
1483 if (!MO.isReg() || !MO.isDef())
1484 continue;
1485 Register R = MO.getReg();
1486 if (!Register::isVirtualRegister(R) || !MRI->use_nodbg_empty(R)) {
1487 AllDead = false;
1488 break;
1489 }
1490 Regs.push_back(R);
1491 }
1492 if (!AllDead)
1493 continue;
1494
1495 B->erase(MI);
1496 for (unsigned I = 0, N = Regs.size(); I != N; ++I)
1497 MRI->markUsesInDebugValueAsUndef(Regs[I]);
1498 Changed = true;
1499 }
1500
1501 return Changed;
1502 }
1503
runOnMachineFunction(MachineFunction & MF)1504 bool HexagonGenInsert::runOnMachineFunction(MachineFunction &MF) {
1505 if (skipFunction(MF.getFunction()))
1506 return false;
1507
1508 bool Timing = OptTiming, TimingDetail = Timing && OptTimingDetail;
1509 bool Changed = false;
1510
1511 // Sanity check: one, but not both.
1512 assert(!OptSelectAll0 || !OptSelectHas0);
1513
1514 IFMap.clear();
1515 BaseOrd.clear();
1516 CellOrd.clear();
1517
1518 const auto &ST = MF.getSubtarget<HexagonSubtarget>();
1519 HII = ST.getInstrInfo();
1520 HRI = ST.getRegisterInfo();
1521 MFN = &MF;
1522 MRI = &MF.getRegInfo();
1523 MDT = &getAnalysis<MachineDominatorTree>();
1524
1525 // Clean up before any further processing, so that dead code does not
1526 // get used in a newly generated "insert" instruction. Have a custom
1527 // version of DCE that preserves lifetime markers. Without it, merging
1528 // of stack objects can fail to recognize and merge disjoint objects
1529 // leading to unnecessary stack growth.
1530 Changed = removeDeadCode(MDT->getRootNode());
1531
1532 const HexagonEvaluator HE(*HRI, *MRI, *HII, MF);
1533 BitTracker BTLoc(HE, MF);
1534 BTLoc.trace(isDebug());
1535 BTLoc.run();
1536 CellMapShadow MS(BTLoc);
1537 CMS = &MS;
1538
1539 buildOrderingMF(BaseOrd);
1540 buildOrderingBT(BaseOrd, CellOrd);
1541
1542 if (isDebug()) {
1543 dbgs() << "Cell ordering:\n";
1544 for (RegisterOrdering::iterator I = CellOrd.begin(), E = CellOrd.end();
1545 I != E; ++I) {
1546 unsigned VR = I->first, Pos = I->second;
1547 dbgs() << printReg(VR, HRI) << " -> " << Pos << "\n";
1548 }
1549 }
1550
1551 // Collect candidates for conversion into the insert forms.
1552 MachineBasicBlock *RootB = MDT->getRoot();
1553 OrderedRegisterList AvailR(CellOrd);
1554
1555 const char *const TGName = "hexinsert";
1556 const char *const TGDesc = "Generate Insert Instructions";
1557
1558 {
1559 NamedRegionTimer _T("collection", "collection", TGName, TGDesc,
1560 TimingDetail);
1561 collectInBlock(RootB, AvailR);
1562 // Complete the information gathered in IFMap.
1563 computeRemovableRegisters();
1564 }
1565
1566 if (isDebug()) {
1567 dbgs() << "Candidates after collection:\n";
1568 dump_map();
1569 }
1570
1571 if (IFMap.empty())
1572 return Changed;
1573
1574 {
1575 NamedRegionTimer _T("pruning", "pruning", TGName, TGDesc, TimingDetail);
1576 pruneCandidates();
1577 }
1578
1579 if (isDebug()) {
1580 dbgs() << "Candidates after pruning:\n";
1581 dump_map();
1582 }
1583
1584 if (IFMap.empty())
1585 return Changed;
1586
1587 {
1588 NamedRegionTimer _T("selection", "selection", TGName, TGDesc, TimingDetail);
1589 selectCandidates();
1590 }
1591
1592 if (isDebug()) {
1593 dbgs() << "Candidates after selection:\n";
1594 dump_map();
1595 }
1596
1597 // Filter out vregs beyond the cutoff.
1598 if (VRegIndexCutoff.getPosition()) {
1599 unsigned Cutoff = VRegIndexCutoff;
1600
1601 using IterListType = SmallVector<IFMapType::iterator, 16>;
1602
1603 IterListType Out;
1604 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1605 unsigned Idx = Register::virtReg2Index(I->first);
1606 if (Idx >= Cutoff)
1607 Out.push_back(I);
1608 }
1609 for (unsigned i = 0, n = Out.size(); i < n; ++i)
1610 IFMap.erase(Out[i]);
1611 }
1612 if (IFMap.empty())
1613 return Changed;
1614
1615 {
1616 NamedRegionTimer _T("generation", "generation", TGName, TGDesc,
1617 TimingDetail);
1618 generateInserts();
1619 }
1620
1621 return true;
1622 }
1623
createHexagonGenInsert()1624 FunctionPass *llvm::createHexagonGenInsert() {
1625 return new HexagonGenInsert();
1626 }
1627
1628 //===----------------------------------------------------------------------===//
1629 // Public Constructor Functions
1630 //===----------------------------------------------------------------------===//
1631
1632 INITIALIZE_PASS_BEGIN(HexagonGenInsert, "hexinsert",
1633 "Hexagon generate \"insert\" instructions", false, false)
1634 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
1635 INITIALIZE_PASS_END(HexagonGenInsert, "hexinsert",
1636 "Hexagon generate \"insert\" instructions", false, false)
1637