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