1 //===--- HexagonGenInsert.cpp ---------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #define DEBUG_TYPE "hexinsert"
12 #include "BitTracker.h"
13 #include "HexagonBitTracker.h"
14 #include "HexagonInstrInfo.h"
15 #include "HexagonRegisterInfo.h"
16 #include "HexagonSubtarget.h"
17 #include "llvm/ADT/BitVector.h"
18 #include "llvm/ADT/DenseMap.h"
19 #include "llvm/ADT/PostOrderIterator.h"
20 #include "llvm/ADT/SmallSet.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/STLExtras.h"
23 #include "llvm/ADT/StringRef.h"
24 #include "llvm/CodeGen/MachineBasicBlock.h"
25 #include "llvm/CodeGen/MachineDominators.h"
26 #include "llvm/CodeGen/MachineFunction.h"
27 #include "llvm/CodeGen/MachineFunctionPass.h"
28 #include "llvm/CodeGen/MachineInstr.h"
29 #include "llvm/CodeGen/MachineInstrBuilder.h"
30 #include "llvm/CodeGen/MachineOperand.h"
31 #include "llvm/CodeGen/MachineRegisterInfo.h"
32 #include "llvm/IR/DebugLoc.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/raw_ostream.h"
38 #include "llvm/Support/Timer.h"
39 #include "llvm/Target/TargetRegisterInfo.h"
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 "
57 static cl::opt<bool> OptTiming("insert-timing", cl::init(false), cl::Hidden,
58 cl::ZeroOrMore, cl::desc("Enable timing of insert generation"));
59 static cl::opt<bool> OptTimingDetail("insert-timing-detail", cl::init(false),
60 cl::Hidden, cl::ZeroOrMore, cl::desc("Enable detailed timing of insert "
63 static cl::opt<bool> OptSelectAll0("insert-all0", cl::init(false), cl::Hidden,
65 static cl::opt<bool> OptSelectHas0("insert-has0", cl::init(false), cl::Hidden,
67 // Whether to construct constant values via "insert". Could eliminate constant
68 // extenders, but often not practical.
69 static cl::opt<bool> OptConst("insert-const", cl::init(false), cl::Hidden,
72 // The preprocessor gets confused when the DEBUG macro is passed larger
73 // chunks of code. Use this function to detect debugging.
74 inline static bool isDebug() {
76 return DebugFlag && isCurrentDebugType(DEBUG_TYPE);
84 // Set of virtual registers, based on BitVector.
85 struct RegisterSet : private BitVector {
86 RegisterSet() = default;
87 explicit RegisterSet(unsigned s, bool t = false) : BitVector(s, t) {}
89 using BitVector::clear;
91 unsigned find_first() const {
92 int First = BitVector::find_first();
98 unsigned find_next(unsigned Prev) const {
99 int Next = BitVector::find_next(v2x(Prev));
105 RegisterSet &insert(unsigned R) {
106 unsigned Idx = v2x(R);
108 return static_cast<RegisterSet&>(BitVector::set(Idx));
110 RegisterSet &remove(unsigned R) {
111 unsigned Idx = v2x(R);
114 return static_cast<RegisterSet&>(BitVector::reset(Idx));
117 RegisterSet &insert(const RegisterSet &Rs) {
118 return static_cast<RegisterSet&>(BitVector::operator|=(Rs));
120 RegisterSet &remove(const RegisterSet &Rs) {
121 return static_cast<RegisterSet&>(BitVector::reset(Rs));
124 reference operator[](unsigned R) {
125 unsigned Idx = v2x(R);
127 return BitVector::operator[](Idx);
129 bool operator[](unsigned R) const {
130 unsigned Idx = v2x(R);
131 assert(Idx < size());
132 return BitVector::operator[](Idx);
134 bool has(unsigned R) const {
135 unsigned Idx = v2x(R);
138 return BitVector::test(Idx);
142 return !BitVector::any();
144 bool includes(const RegisterSet &Rs) const {
145 // A.BitVector::test(B) <=> A-B != {}
146 return !Rs.BitVector::test(*this);
148 bool intersects(const RegisterSet &Rs) const {
149 return BitVector::anyCommon(Rs);
153 void ensure(unsigned Idx) {
155 resize(std::max(Idx+1, 32U));
158 static inline unsigned v2x(unsigned v) {
159 return TargetRegisterInfo::virtReg2Index(v);
162 static inline unsigned x2v(unsigned x) {
163 return TargetRegisterInfo::index2VirtReg(x);
168 PrintRegSet(const RegisterSet &S, const TargetRegisterInfo *RI)
171 friend raw_ostream &operator<< (raw_ostream &OS,
172 const PrintRegSet &P);
175 const RegisterSet &RS;
176 const TargetRegisterInfo *TRI;
179 raw_ostream &operator<< (raw_ostream &OS, const PrintRegSet &P) {
181 for (unsigned R = P.RS.find_first(); R; R = P.RS.find_next(R))
182 OS << ' ' << PrintReg(R, P.TRI);
187 // A convenience class to associate unsigned numbers (such as virtual
188 // registers) with unsigned numbers.
189 struct UnsignedMap : public DenseMap<unsigned,unsigned> {
190 UnsignedMap() = default;
193 typedef DenseMap<unsigned,unsigned> BaseType;
196 // A utility to establish an ordering between virtual registers:
197 // VRegA < VRegB <=> RegisterOrdering[VRegA] < RegisterOrdering[VRegB]
198 // This is meant as a cache for the ordering of virtual registers defined
199 // by a potentially expensive comparison function, or obtained by a proce-
200 // dure that should not be repeated each time two registers are compared.
201 struct RegisterOrdering : public UnsignedMap {
202 RegisterOrdering() = default;
204 unsigned operator[](unsigned VR) const {
205 const_iterator F = find(VR);
210 // Add operator(), so that objects of this class can be used as
211 // comparators in std::sort et al.
212 bool operator() (unsigned VR1, unsigned VR2) const {
213 return operator[](VR1) < operator[](VR2);
217 // Ordering of bit values. This class does not have operator[], but
218 // is supplies a comparison operator() for use in std:: algorithms.
219 // The order is as follows:
221 // - ref1 < ref2, if ord(ref1.Reg) < ord(ref2.Reg),
222 // or ord(ref1.Reg) == ord(ref2.Reg), and ref1.Pos < ref2.Pos.
223 struct BitValueOrdering {
224 BitValueOrdering(const RegisterOrdering &RB) : BaseOrd(RB) {}
226 bool operator() (const BitTracker::BitValue &V1,
227 const BitTracker::BitValue &V2) const;
229 const RegisterOrdering &BaseOrd;
232 } // end anonymous namespace
234 bool BitValueOrdering::operator() (const BitTracker::BitValue &V1,
235 const BitTracker::BitValue &V2) const {
238 // V1==0 => true, V2==0 => false
239 if (V1.is(0) || V2.is(0))
241 // Neither of V1,V2 is 0, and V1!=V2.
242 // V2==1 => false, V1==1 => true
243 if (V2.is(1) || V1.is(1))
245 // Both V1,V2 are refs.
246 unsigned Ind1 = BaseOrd[V1.RefI.Reg], Ind2 = BaseOrd[V2.RefI.Reg];
250 assert(V1.RefI.Pos != V2.RefI.Pos && "Bit values should be different");
251 return V1.RefI.Pos < V2.RefI.Pos;
256 // Cache for the BitTracker's cell map. Map lookup has a logarithmic
257 // complexity, this class will memoize the lookup results to reduce
258 // the access time for repeated lookups of the same cell.
259 struct CellMapShadow {
260 CellMapShadow(const BitTracker &T) : BT(T) {}
262 const BitTracker::RegisterCell &lookup(unsigned VR) {
263 unsigned RInd = TargetRegisterInfo::virtReg2Index(VR);
264 // Grow the vector to at least 32 elements.
265 if (RInd >= CVect.size())
266 CVect.resize(std::max(RInd+16, 32U), nullptr);
267 const BitTracker::RegisterCell *CP = CVect[RInd];
269 CP = CVect[RInd] = &BT.lookup(VR);
273 const BitTracker &BT;
276 typedef std::vector<const BitTracker::RegisterCell*> CellVectType;
280 // Comparator class for lexicographic ordering of virtual registers
281 // according to the corresponding BitTracker::RegisterCell objects.
282 struct RegisterCellLexCompare {
283 RegisterCellLexCompare(const BitValueOrdering &BO, CellMapShadow &M)
284 : BitOrd(BO), CM(M) {}
286 bool operator() (unsigned VR1, unsigned VR2) const;
289 const BitValueOrdering &BitOrd;
293 // Comparator class for lexicographic ordering of virtual registers
294 // according to the specified bits of the corresponding BitTracker::
295 // RegisterCell objects.
296 // Specifically, this class will be used to compare bit B of a register
297 // cell for a selected virtual register R with bit N of any register
299 struct RegisterCellBitCompareSel {
300 RegisterCellBitCompareSel(unsigned R, unsigned B, unsigned N,
301 const BitValueOrdering &BO, CellMapShadow &M)
302 : SelR(R), SelB(B), BitN(N), BitOrd(BO), CM(M) {}
304 bool operator() (unsigned VR1, unsigned VR2) const;
307 const unsigned SelR, SelB;
309 const BitValueOrdering &BitOrd;
313 } // end anonymous namespace
315 bool RegisterCellLexCompare::operator() (unsigned VR1, unsigned VR2) const {
316 // Ordering of registers, made up from two given orderings:
317 // - the ordering of the register numbers, and
318 // - the ordering of register cells.
320 // - cell(R1) < cell(R2), or
321 // - cell(R1) == cell(R2), and index(R1) < index(R2).
323 // For register cells, the ordering is lexicographic, with index 0 being
324 // the most significant.
328 const BitTracker::RegisterCell &RC1 = CM.lookup(VR1), &RC2 = CM.lookup(VR2);
329 uint16_t W1 = RC1.width(), W2 = RC2.width();
330 for (uint16_t i = 0, w = std::min(W1, W2); i < w; ++i) {
331 const BitTracker::BitValue &V1 = RC1[i], &V2 = RC2[i];
333 return BitOrd(V1, V2);
335 // Cells are equal up until the common length.
339 return BitOrd.BaseOrd[VR1] < BitOrd.BaseOrd[VR2];
342 bool RegisterCellBitCompareSel::operator() (unsigned VR1, unsigned VR2) const {
345 const BitTracker::RegisterCell &RC1 = CM.lookup(VR1);
346 const BitTracker::RegisterCell &RC2 = CM.lookup(VR2);
347 uint16_t W1 = RC1.width(), W2 = RC2.width();
348 uint16_t Bit1 = (VR1 == SelR) ? SelB : BitN;
349 uint16_t Bit2 = (VR2 == SelR) ? SelB : BitN;
350 // If Bit1 exceeds the width of VR1, then:
351 // - return false, if at the same time Bit2 exceeds VR2, or
352 // - return true, otherwise.
353 // (I.e. "a bit value that does not exist is less than any bit value
354 // that does exist".)
357 // If Bit1 is within VR1, but Bit2 is not within VR2, return false.
361 const BitTracker::BitValue &V1 = RC1[Bit1], V2 = RC2[Bit2];
363 return BitOrd(V1, V2);
369 class OrderedRegisterList {
370 typedef std::vector<unsigned> ListType;
373 OrderedRegisterList(const RegisterOrdering &RO) : Ord(RO) {}
375 void insert(unsigned VR);
376 void remove(unsigned VR);
378 unsigned operator[](unsigned Idx) const {
379 assert(Idx < Seq.size());
383 unsigned size() const {
387 typedef ListType::iterator iterator;
388 typedef ListType::const_iterator const_iterator;
389 iterator begin() { return Seq.begin(); }
390 iterator end() { return Seq.end(); }
391 const_iterator begin() const { return Seq.begin(); }
392 const_iterator end() const { return Seq.end(); }
394 // Convenience function to convert an iterator to the corresponding index.
395 unsigned idx(iterator It) const { return It-begin(); }
399 const RegisterOrdering &Ord;
403 PrintORL(const OrderedRegisterList &L, const TargetRegisterInfo *RI)
406 friend raw_ostream &operator<< (raw_ostream &OS, const PrintORL &P);
409 const OrderedRegisterList &RL;
410 const TargetRegisterInfo *TRI;
413 raw_ostream &operator<< (raw_ostream &OS, const PrintORL &P) {
415 OrderedRegisterList::const_iterator B = P.RL.begin(), E = P.RL.end();
416 for (OrderedRegisterList::const_iterator I = B; I != E; ++I) {
419 OS << PrintReg(*I, P.TRI);
425 } // end anonymous namespace
427 void OrderedRegisterList::insert(unsigned VR) {
428 iterator L = std::lower_bound(Seq.begin(), Seq.end(), VR, Ord);
435 void OrderedRegisterList::remove(unsigned VR) {
436 iterator L = std::lower_bound(Seq.begin(), Seq.end(), VR, Ord);
437 assert(L != Seq.end());
443 // A record of the insert form. The fields correspond to the operands
444 // of the "insert" instruction:
445 // ... = insert(SrcR, InsR, #Wdh, #Off)
447 IFRecord(unsigned SR = 0, unsigned IR = 0, uint16_t W = 0, uint16_t O = 0)
448 : SrcR(SR), InsR(IR), Wdh(W), Off(O) {}
455 PrintIFR(const IFRecord &R, const TargetRegisterInfo *RI)
459 friend raw_ostream &operator<< (raw_ostream &OS, const PrintIFR &P);
462 const TargetRegisterInfo *TRI;
465 raw_ostream &operator<< (raw_ostream &OS, const PrintIFR &P) {
466 unsigned SrcR = P.IFR.SrcR, InsR = P.IFR.InsR;
467 OS << '(' << PrintReg(SrcR, P.TRI) << ',' << PrintReg(InsR, P.TRI)
468 << ",#" << P.IFR.Wdh << ",#" << P.IFR.Off << ')';
472 typedef std::pair<IFRecord,RegisterSet> IFRecordWithRegSet;
474 } // end anonymous namespace
478 void initializeHexagonGenInsertPass(PassRegistry&);
479 FunctionPass *createHexagonGenInsert();
481 } // end namespace llvm
485 class HexagonGenInsert : public MachineFunctionPass {
489 HexagonGenInsert() : MachineFunctionPass(ID), HII(nullptr), HRI(nullptr) {
490 initializeHexagonGenInsertPass(*PassRegistry::getPassRegistry());
493 StringRef getPassName() const override {
494 return "Hexagon generate \"insert\" instructions";
497 void getAnalysisUsage(AnalysisUsage &AU) const override {
498 AU.addRequired<MachineDominatorTree>();
499 AU.addPreserved<MachineDominatorTree>();
500 MachineFunctionPass::getAnalysisUsage(AU);
503 bool runOnMachineFunction(MachineFunction &MF) override;
506 typedef DenseMap<std::pair<unsigned,unsigned>,unsigned> PairMapType;
508 void buildOrderingMF(RegisterOrdering &RO) const;
509 void buildOrderingBT(RegisterOrdering &RB, RegisterOrdering &RO) const;
510 bool isIntClass(const TargetRegisterClass *RC) const;
511 bool isConstant(unsigned VR) const;
512 bool isSmallConstant(unsigned VR) const;
513 bool isValidInsertForm(unsigned DstR, unsigned SrcR, unsigned InsR,
514 uint16_t L, uint16_t S) const;
515 bool findSelfReference(unsigned VR) const;
516 bool findNonSelfReference(unsigned VR) const;
517 void getInstrDefs(const MachineInstr *MI, RegisterSet &Defs) const;
518 void getInstrUses(const MachineInstr *MI, RegisterSet &Uses) const;
519 unsigned distance(const MachineBasicBlock *FromB,
520 const MachineBasicBlock *ToB, const UnsignedMap &RPO,
521 PairMapType &M) const;
522 unsigned distance(MachineBasicBlock::const_iterator FromI,
523 MachineBasicBlock::const_iterator ToI, const UnsignedMap &RPO,
524 PairMapType &M) const;
525 bool findRecordInsertForms(unsigned VR, OrderedRegisterList &AVs);
526 void collectInBlock(MachineBasicBlock *B, OrderedRegisterList &AVs);
527 void findRemovableRegisters(unsigned VR, IFRecord IF,
528 RegisterSet &RMs) const;
529 void computeRemovableRegisters();
531 void pruneEmptyLists();
532 void pruneCoveredSets(unsigned VR);
533 void pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO, PairMapType &M);
534 void pruneRegCopies(unsigned VR);
535 void pruneCandidates();
536 void selectCandidates();
537 bool generateInserts();
539 bool removeDeadCode(MachineDomTreeNode *N);
541 // IFRecord coupled with a set of potentially removable registers:
542 typedef std::vector<IFRecordWithRegSet> IFListType;
543 typedef DenseMap<unsigned,IFListType> IFMapType; // vreg -> IFListType
545 void dump_map() const;
547 const HexagonInstrInfo *HII;
548 const HexagonRegisterInfo *HRI;
550 MachineFunction *MFN;
551 MachineRegisterInfo *MRI;
552 MachineDominatorTree *MDT;
555 RegisterOrdering BaseOrd;
556 RegisterOrdering CellOrd;
560 char HexagonGenInsert::ID = 0;
562 } // end anonymous namespace
564 void HexagonGenInsert::dump_map() const {
565 typedef IFMapType::const_iterator iterator;
566 for (iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
567 dbgs() << " " << PrintReg(I->first, HRI) << ":\n";
568 const IFListType &LL = I->second;
569 for (unsigned i = 0, n = LL.size(); i < n; ++i)
570 dbgs() << " " << PrintIFR(LL[i].first, HRI) << ", "
571 << PrintRegSet(LL[i].second, HRI) << '\n';
575 void HexagonGenInsert::buildOrderingMF(RegisterOrdering &RO) const {
577 typedef MachineFunction::const_iterator mf_iterator;
578 for (mf_iterator A = MFN->begin(), Z = MFN->end(); A != Z; ++A) {
579 const MachineBasicBlock &B = *A;
580 if (!CMS->BT.reached(&B))
582 typedef MachineBasicBlock::const_iterator mb_iterator;
583 for (mb_iterator I = B.begin(), E = B.end(); I != E; ++I) {
584 const MachineInstr *MI = &*I;
585 for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
586 const MachineOperand &MO = MI->getOperand(i);
587 if (MO.isReg() && MO.isDef()) {
588 unsigned R = MO.getReg();
589 assert(MO.getSubReg() == 0 && "Unexpected subregister in definition");
590 if (TargetRegisterInfo::isVirtualRegister(R))
591 RO.insert(std::make_pair(R, Index++));
596 // Since some virtual registers may have had their def and uses eliminated,
597 // they are no longer referenced in the code, and so they will not appear
601 void HexagonGenInsert::buildOrderingBT(RegisterOrdering &RB,
602 RegisterOrdering &RO) const {
603 // Create a vector of all virtual registers (collect them from the base
604 // ordering RB), and then sort it using the RegisterCell comparator.
605 BitValueOrdering BVO(RB);
606 RegisterCellLexCompare LexCmp(BVO, *CMS);
607 typedef std::vector<unsigned> SortableVectorType;
608 SortableVectorType VRs;
609 for (RegisterOrdering::iterator I = RB.begin(), E = RB.end(); I != E; ++I)
610 VRs.push_back(I->first);
611 std::sort(VRs.begin(), VRs.end(), LexCmp);
612 // Transfer the results to the outgoing register ordering.
613 for (unsigned i = 0, n = VRs.size(); i < n; ++i)
614 RO.insert(std::make_pair(VRs[i], i));
617 inline bool HexagonGenInsert::isIntClass(const TargetRegisterClass *RC) const {
618 return RC == &Hexagon::IntRegsRegClass || RC == &Hexagon::DoubleRegsRegClass;
621 bool HexagonGenInsert::isConstant(unsigned VR) const {
622 const BitTracker::RegisterCell &RC = CMS->lookup(VR);
623 uint16_t W = RC.width();
624 for (uint16_t i = 0; i < W; ++i) {
625 const BitTracker::BitValue &BV = RC[i];
626 if (BV.is(0) || BV.is(1))
633 bool HexagonGenInsert::isSmallConstant(unsigned VR) const {
634 const BitTracker::RegisterCell &RC = CMS->lookup(VR);
635 uint16_t W = RC.width();
638 uint64_t V = 0, B = 1;
639 for (uint16_t i = 0; i < W; ++i) {
640 const BitTracker::BitValue &BV = RC[i];
648 // For 32-bit registers, consider: Rd = #s16.
652 // For 64-bit registers, it's Rdd = #s8 or Rdd = combine(#s8,#s8)
653 return isInt<8>(Lo_32(V)) && isInt<8>(Hi_32(V));
656 bool HexagonGenInsert::isValidInsertForm(unsigned DstR, unsigned SrcR,
657 unsigned InsR, uint16_t L, uint16_t S) const {
658 const TargetRegisterClass *DstRC = MRI->getRegClass(DstR);
659 const TargetRegisterClass *SrcRC = MRI->getRegClass(SrcR);
660 const TargetRegisterClass *InsRC = MRI->getRegClass(InsR);
661 // Only integet (32-/64-bit) register classes.
662 if (!isIntClass(DstRC) || !isIntClass(SrcRC) || !isIntClass(InsRC))
664 // The "source" register must be of the same class as DstR.
669 // A 64-bit register can only be generated from other 64-bit registers.
670 if (DstRC == &Hexagon::DoubleRegsRegClass)
672 // Otherwise, the L and S cannot span 32-bit word boundary.
673 if (S < 32 && S+L > 32)
678 bool HexagonGenInsert::findSelfReference(unsigned VR) const {
679 const BitTracker::RegisterCell &RC = CMS->lookup(VR);
680 for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
681 const BitTracker::BitValue &V = RC[i];
682 if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg == VR)
688 bool HexagonGenInsert::findNonSelfReference(unsigned VR) const {
689 BitTracker::RegisterCell RC = CMS->lookup(VR);
690 for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
691 const BitTracker::BitValue &V = RC[i];
692 if (V.Type == BitTracker::BitValue::Ref && V.RefI.Reg != VR)
698 void HexagonGenInsert::getInstrDefs(const MachineInstr *MI,
699 RegisterSet &Defs) const {
700 for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
701 const MachineOperand &MO = MI->getOperand(i);
702 if (!MO.isReg() || !MO.isDef())
704 unsigned R = MO.getReg();
705 if (!TargetRegisterInfo::isVirtualRegister(R))
711 void HexagonGenInsert::getInstrUses(const MachineInstr *MI,
712 RegisterSet &Uses) const {
713 for (unsigned i = 0, n = MI->getNumOperands(); i < n; ++i) {
714 const MachineOperand &MO = MI->getOperand(i);
715 if (!MO.isReg() || !MO.isUse())
717 unsigned R = MO.getReg();
718 if (!TargetRegisterInfo::isVirtualRegister(R))
724 unsigned HexagonGenInsert::distance(const MachineBasicBlock *FromB,
725 const MachineBasicBlock *ToB, const UnsignedMap &RPO,
726 PairMapType &M) const {
727 // Forward distance from the end of a block to the beginning of it does
728 // not make sense. This function should not be called with FromB == ToB.
729 assert(FromB != ToB);
731 unsigned FromN = FromB->getNumber(), ToN = ToB->getNumber();
732 // If we have already computed it, return the cached result.
733 PairMapType::iterator F = M.find(std::make_pair(FromN, ToN));
736 unsigned ToRPO = RPO.lookup(ToN);
739 typedef MachineBasicBlock::const_pred_iterator pred_iterator;
740 for (pred_iterator I = ToB->pred_begin(), E = ToB->pred_end(); I != E; ++I) {
741 const MachineBasicBlock *PB = *I;
742 // Skip back edges. Also, if FromB is a predecessor of ToB, the distance
743 // along that path will be 0, and we don't need to do any calculations
745 if (PB == FromB || RPO.lookup(PB->getNumber()) >= ToRPO)
747 unsigned D = PB->size() + distance(FromB, PB, RPO, M);
752 // Memoize the result for later lookup.
753 M.insert(std::make_pair(std::make_pair(FromN, ToN), MaxD));
757 unsigned HexagonGenInsert::distance(MachineBasicBlock::const_iterator FromI,
758 MachineBasicBlock::const_iterator ToI, const UnsignedMap &RPO,
759 PairMapType &M) const {
760 const MachineBasicBlock *FB = FromI->getParent(), *TB = ToI->getParent();
762 return std::distance(FromI, ToI);
763 unsigned D1 = std::distance(TB->begin(), ToI);
764 unsigned D2 = distance(FB, TB, RPO, M);
765 unsigned D3 = std::distance(FromI, FB->end());
769 bool HexagonGenInsert::findRecordInsertForms(unsigned VR,
770 OrderedRegisterList &AVs) {
772 dbgs() << __func__ << ": " << PrintReg(VR, HRI)
773 << " AVs: " << PrintORL(AVs, HRI) << "\n";
778 typedef OrderedRegisterList::iterator iterator;
779 BitValueOrdering BVO(BaseOrd);
780 const BitTracker::RegisterCell &RC = CMS->lookup(VR);
781 uint16_t W = RC.width();
783 typedef std::pair<unsigned,uint16_t> RSRecord; // (reg,shift)
784 typedef std::vector<RSRecord> RSListType;
785 // Have a map, with key being the matching prefix length, and the value
786 // being the list of pairs (R,S), where R's prefix matches VR at S.
787 // (DenseMap<uint16_t,RSListType> fails to instantiate.)
788 typedef DenseMap<unsigned,RSListType> LRSMapType;
791 // Conceptually, rotate the cell RC right (i.e. towards the LSB) by S,
792 // and find matching prefixes from AVs with the rotated RC. Such a prefix
793 // would match a string of bits (of length L) in RC starting at S.
794 for (uint16_t S = 0; S < W; ++S) {
795 iterator B = AVs.begin(), E = AVs.end();
796 // The registers in AVs are ordered according to the lexical order of
797 // the corresponding register cells. This means that the range of regis-
798 // ters in AVs that match a prefix of length L+1 will be contained in
799 // the range that matches a prefix of length L. This means that we can
800 // keep narrowing the search space as the prefix length goes up. This
801 // helps reduce the overall complexity of the search.
803 for (L = 0; L < W-S; ++L) {
804 // Compare against VR's bits starting at S, which emulates rotation
806 RegisterCellBitCompareSel RCB(VR, S+L, L, BVO, *CMS);
807 iterator NewB = std::lower_bound(B, E, VR, RCB);
808 iterator NewE = std::upper_bound(NewB, E, VR, RCB);
809 // For the registers that are eliminated from the next range, L is
810 // the longest prefix matching VR at position S (their prefixes
811 // differ from VR at S+L). If L>0, record this information for later
814 for (iterator I = B; I != NewB; ++I)
815 LM[L].push_back(std::make_pair(*I, S));
816 for (iterator I = NewE; I != E; ++I)
817 LM[L].push_back(std::make_pair(*I, S));
823 // Record the final register range. If this range is non-empty, then
825 assert(B == E || L == W-S);
827 for (iterator I = B; I != E; ++I)
828 LM[L].push_back(std::make_pair(*I, S));
829 // If B!=E, then we found a range of registers whose prefixes cover the
830 // rest of VR from position S. There is no need to further advance S.
836 dbgs() << "Prefixes matching register " << PrintReg(VR, HRI) << "\n";
837 for (LRSMapType::iterator I = LM.begin(), E = LM.end(); I != E; ++I) {
838 dbgs() << " L=" << I->first << ':';
839 const RSListType &LL = I->second;
840 for (unsigned i = 0, n = LL.size(); i < n; ++i)
841 dbgs() << " (" << PrintReg(LL[i].first, HRI) << ",@"
842 << LL[i].second << ')';
847 bool Recorded = false;
849 for (iterator I = AVs.begin(), E = AVs.end(); I != E; ++I) {
851 int FDi = -1, LDi = -1; // First/last different bit.
852 const BitTracker::RegisterCell &AC = CMS->lookup(SrcR);
853 uint16_t AW = AC.width();
854 for (uint16_t i = 0, w = std::min(W, AW); i < w; ++i) {
862 continue; // TODO (future): Record identical registers.
863 // Look for a register whose prefix could patch the range [FD..LD]
864 // where VR and SrcR differ.
865 uint16_t FD = FDi, LD = LDi; // Switch to unsigned type.
866 uint16_t MinL = LD-FD+1;
867 for (uint16_t L = MinL; L < W; ++L) {
868 LRSMapType::iterator F = LM.find(L);
871 RSListType &LL = F->second;
872 for (unsigned i = 0, n = LL.size(); i < n; ++i) {
873 uint16_t S = LL[i].second;
874 // MinL is the minimum length of the prefix. Any length above MinL
875 // allows some flexibility as to where the prefix can start:
876 // given the extra length EL=L-MinL, the prefix must start between
877 // max(0,FD-EL) and FD.
878 if (S > FD) // Starts too late.
880 uint16_t EL = L-MinL;
881 uint16_t LowS = (EL < FD) ? FD-EL : 0;
882 if (S < LowS) // Starts too early.
884 unsigned InsR = LL[i].first;
885 if (!isValidInsertForm(VR, SrcR, InsR, L, S))
888 dbgs() << PrintReg(VR, HRI) << " = insert(" << PrintReg(SrcR, HRI)
889 << ',' << PrintReg(InsR, HRI) << ",#" << L << ",#"
892 IFRecordWithRegSet RR(IFRecord(SrcR, InsR, L, S), RegisterSet());
893 IFMap[VR].push_back(RR);
902 void HexagonGenInsert::collectInBlock(MachineBasicBlock *B,
903 OrderedRegisterList &AVs) {
905 dbgs() << "visiting block BB#" << B->getNumber() << "\n";
907 // First, check if this block is reachable at all. If not, the bit tracker
908 // will not have any information about registers in it.
909 if (!CMS->BT.reached(B))
912 bool DoConst = OptConst;
913 // Keep a separate set of registers defined in this block, so that we
914 // can remove them from the list of available registers once all DT
915 // successors have been processed.
916 RegisterSet BlockDefs, InsDefs;
917 for (MachineBasicBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) {
918 MachineInstr *MI = &*I;
920 getInstrDefs(MI, InsDefs);
921 // Leave those alone. They are more transparent than "insert".
922 bool Skip = MI->isCopy() || MI->isRegSequence();
925 // Visit all defined registers, and attempt to find the corresponding
926 // "insert" representations.
927 for (unsigned VR = InsDefs.find_first(); VR; VR = InsDefs.find_next(VR)) {
928 // Do not collect registers that are known to be compile-time cons-
929 // tants, unless requested.
930 if (!DoConst && isConstant(VR))
932 // If VR's cell contains a reference to VR, then VR cannot be defined
933 // via "insert". If VR is a constant that can be generated in a single
934 // instruction (without constant extenders), generating it via insert
936 if (findSelfReference(VR) || isSmallConstant(VR))
939 findRecordInsertForms(VR, AVs);
943 // Insert the defined registers into the list of available registers
944 // after they have been processed.
945 for (unsigned VR = InsDefs.find_first(); VR; VR = InsDefs.find_next(VR))
947 BlockDefs.insert(InsDefs);
950 MachineDomTreeNode *N = MDT->getNode(B);
951 typedef GraphTraits<MachineDomTreeNode*> GTN;
952 typedef GTN::ChildIteratorType ChildIter;
953 for (ChildIter I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I) {
954 MachineBasicBlock *SB = (*I)->getBlock();
955 collectInBlock(SB, AVs);
958 for (unsigned VR = BlockDefs.find_first(); VR; VR = BlockDefs.find_next(VR))
962 void HexagonGenInsert::findRemovableRegisters(unsigned VR, IFRecord IF,
963 RegisterSet &RMs) const {
964 // For a given register VR and a insert form, find the registers that are
965 // used by the current definition of VR, and which would no longer be
966 // needed for it after the definition of VR is replaced with the insert
967 // form. These are the registers that could potentially become dead.
970 unsigned S = 0; // Register set selector.
973 while (!Regs[S].empty()) {
974 // Breadth-first search.
975 unsigned OtherS = 1-S;
976 Regs[OtherS].clear();
977 for (unsigned R = Regs[S].find_first(); R; R = Regs[S].find_next(R)) {
979 if (R == IF.SrcR || R == IF.InsR)
981 // Check if a given register has bits that are references to any other
982 // registers. This is to detect situations where the instruction that
983 // defines register R takes register Q as an operand, but R itself does
984 // not contain any bits from Q. Loads are examples of how this could
987 // In this case (assuming we do not have any knowledge about the loaded
988 // value), we must not treat R as a "conveyance" of the bits from Q.
989 // (The information in BT about R's bits would have them as constants,
990 // in case of zero-extending loads, or refs to R.)
991 if (!findNonSelfReference(R))
994 const MachineInstr *DefI = MRI->getVRegDef(R);
996 // Do not iterate past PHI nodes to avoid infinite loops. This can
997 // make the final set a bit less accurate, but the removable register
998 // sets are an approximation anyway.
1001 getInstrUses(DefI, Regs[OtherS]);
1005 // The register VR is added to the list as a side-effect of the algorithm,
1006 // but it is not "potentially removable". A potentially removable register
1007 // is one that may become unused (dead) after conversion to the insert form
1008 // IF, and obviously VR (or its replacement) will not become dead by apply-
1013 void HexagonGenInsert::computeRemovableRegisters() {
1014 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1015 IFListType &LL = I->second;
1016 for (unsigned i = 0, n = LL.size(); i < n; ++i)
1017 findRemovableRegisters(I->first, LL[i].first, LL[i].second);
1021 void HexagonGenInsert::pruneEmptyLists() {
1022 // Remove all entries from the map, where the register has no insert forms
1023 // associated with it.
1024 typedef SmallVector<IFMapType::iterator,16> IterListType;
1026 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1027 if (I->second.empty())
1030 for (unsigned i = 0, n = Prune.size(); i < n; ++i)
1031 IFMap.erase(Prune[i]);
1034 void HexagonGenInsert::pruneCoveredSets(unsigned VR) {
1035 IFMapType::iterator F = IFMap.find(VR);
1036 assert(F != IFMap.end());
1037 IFListType &LL = F->second;
1039 // First, examine the IF candidates for register VR whose removable-regis-
1040 // ter sets are empty. This means that a given candidate will not help eli-
1041 // minate any registers, but since "insert" is not a constant-extendable
1042 // instruction, using such a candidate may reduce code size if the defini-
1043 // tion of VR is constant-extended.
1044 // If there exists a candidate with a non-empty set, the ones with empty
1045 // sets will not be used and can be removed.
1046 MachineInstr *DefVR = MRI->getVRegDef(VR);
1047 bool DefEx = HII->isConstExtended(*DefVR);
1049 for (unsigned i = 0, n = LL.size(); i < n; ++i) {
1050 if (LL[i].second.empty())
1055 if (!DefEx || HasNE) {
1056 // The definition of VR is not constant-extended, or there is a candidate
1057 // with a non-empty set. Remove all candidates with empty sets.
1058 auto IsEmpty = [] (const IFRecordWithRegSet &IR) -> bool {
1059 return IR.second.empty();
1061 auto End = llvm::remove_if(LL, IsEmpty);
1062 if (End != LL.end())
1063 LL.erase(End, LL.end());
1065 // The definition of VR is constant-extended, and all candidates have
1066 // empty removable-register sets. Pick the maximum candidate, and remove
1067 // all others. The "maximum" does not have any special meaning here, it
1068 // is only so that the candidate that will remain on the list is selec-
1069 // ted deterministically.
1070 IFRecord MaxIF = LL[0].first;
1071 for (unsigned i = 1, n = LL.size(); i < n; ++i) {
1072 // If LL[MaxI] < LL[i], then MaxI = i.
1073 const IFRecord &IF = LL[i].first;
1074 unsigned M0 = BaseOrd[MaxIF.SrcR], M1 = BaseOrd[MaxIF.InsR];
1075 unsigned R0 = BaseOrd[IF.SrcR], R1 = BaseOrd[IF.InsR];
1082 if (MaxIF.Wdh > IF.Wdh)
1084 if (MaxIF.Wdh == IF.Wdh && MaxIF.Off >= IF.Off)
1091 // Remove everything except the maximum candidate. All register sets
1092 // are empty, so no need to preserve anything.
1094 LL.push_back(std::make_pair(MaxIF, RegisterSet()));
1097 // Now, remove those whose sets of potentially removable registers are
1098 // contained in another IF candidate for VR. For example, given these
1099 // candidates for vreg45,
1101 // (%vreg44,%vreg41,#9,#8), { %vreg42 }
1102 // (%vreg43,%vreg41,#9,#8), { %vreg42 %vreg44 }
1103 // remove the first one, since it is contained in the second one.
1104 for (unsigned i = 0, n = LL.size(); i < n; ) {
1105 const RegisterSet &RMi = LL[i].second;
1108 if (j != i && LL[j].second.includes(RMi))
1112 if (j == n) { // RMi not contained in anything else.
1116 LL.erase(LL.begin()+i);
1121 void HexagonGenInsert::pruneUsesTooFar(unsigned VR, const UnsignedMap &RPO,
1123 IFMapType::iterator F = IFMap.find(VR);
1124 assert(F != IFMap.end());
1125 IFListType &LL = F->second;
1126 unsigned Cutoff = VRegDistCutoff;
1127 const MachineInstr *DefV = MRI->getVRegDef(VR);
1129 for (unsigned i = LL.size(); i > 0; --i) {
1130 unsigned SR = LL[i-1].first.SrcR, IR = LL[i-1].first.InsR;
1131 const MachineInstr *DefS = MRI->getVRegDef(SR);
1132 const MachineInstr *DefI = MRI->getVRegDef(IR);
1133 unsigned DSV = distance(DefS, DefV, RPO, M);
1135 unsigned DIV = distance(DefI, DefV, RPO, M);
1139 LL.erase(LL.begin()+(i-1));
1143 void HexagonGenInsert::pruneRegCopies(unsigned VR) {
1144 IFMapType::iterator F = IFMap.find(VR);
1145 assert(F != IFMap.end());
1146 IFListType &LL = F->second;
1148 auto IsCopy = [] (const IFRecordWithRegSet &IR) -> bool {
1149 return IR.first.Wdh == 32 && (IR.first.Off == 0 || IR.first.Off == 32);
1151 auto End = llvm::remove_if(LL, IsCopy);
1152 if (End != LL.end())
1153 LL.erase(End, LL.end());
1156 void HexagonGenInsert::pruneCandidates() {
1157 // Remove candidates that are not beneficial, regardless of the final
1158 // selection method.
1159 // First, remove candidates whose potentially removable set is a subset
1160 // of another candidate's set.
1161 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I)
1162 pruneCoveredSets(I->first);
1165 typedef ReversePostOrderTraversal<const MachineFunction*> RPOTType;
1168 for (RPOTType::rpo_iterator I = RPOT.begin(), E = RPOT.end(); I != E; ++I)
1169 RPO[(*I)->getNumber()] = RPON++;
1171 PairMapType Memo; // Memoization map for distance calculation.
1172 // Remove candidates that would use registers defined too far away.
1173 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I)
1174 pruneUsesTooFar(I->first, RPO, Memo);
1178 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I)
1179 pruneRegCopies(I->first);
1184 // Class for comparing IF candidates for registers that have multiple of
1185 // them. The smaller the candidate, according to this ordering, the better.
1186 // First, compare the number of zeros in the associated potentially remova-
1187 // ble register sets. "Zero" indicates that the register is very likely to
1188 // become dead after this transformation.
1189 // Second, compare "averages", i.e. use-count per size. The lower wins.
1190 // After that, it does not really matter which one is smaller. Resolve
1191 // the tie in some deterministic way.
1193 IFOrdering(const UnsignedMap &UC, const RegisterOrdering &BO)
1194 : UseC(UC), BaseOrd(BO) {}
1196 bool operator() (const IFRecordWithRegSet &A,
1197 const IFRecordWithRegSet &B) const;
1200 void stats(const RegisterSet &Rs, unsigned &Size, unsigned &Zero,
1201 unsigned &Sum) const;
1203 const UnsignedMap &UseC;
1204 const RegisterOrdering &BaseOrd;
1207 } // end anonymous namespace
1209 bool IFOrdering::operator() (const IFRecordWithRegSet &A,
1210 const IFRecordWithRegSet &B) const {
1211 unsigned SizeA = 0, ZeroA = 0, SumA = 0;
1212 unsigned SizeB = 0, ZeroB = 0, SumB = 0;
1213 stats(A.second, SizeA, ZeroA, SumA);
1214 stats(B.second, SizeB, ZeroB, SumB);
1216 // We will pick the minimum element. The more zeros, the better.
1218 return ZeroA > ZeroB;
1219 // Compare SumA/SizeA with SumB/SizeB, lower is better.
1220 uint64_t AvgA = SumA*SizeB, AvgB = SumB*SizeA;
1224 // The sets compare identical so far. Resort to comparing the IF records.
1225 // The actual values don't matter, this is only for determinism.
1226 unsigned OSA = BaseOrd[A.first.SrcR], OSB = BaseOrd[B.first.SrcR];
1229 unsigned OIA = BaseOrd[A.first.InsR], OIB = BaseOrd[B.first.InsR];
1232 if (A.first.Wdh != B.first.Wdh)
1233 return A.first.Wdh < B.first.Wdh;
1234 return A.first.Off < B.first.Off;
1237 void IFOrdering::stats(const RegisterSet &Rs, unsigned &Size, unsigned &Zero,
1238 unsigned &Sum) const {
1239 for (unsigned R = Rs.find_first(); R; R = Rs.find_next(R)) {
1240 UnsignedMap::const_iterator F = UseC.find(R);
1241 assert(F != UseC.end());
1242 unsigned UC = F->second;
1250 void HexagonGenInsert::selectCandidates() {
1251 // Some registers may have multiple valid candidates. Pick the best one
1252 // (or decide not to use any).
1254 // Compute the "removability" measure of R:
1255 // For each potentially removable register R, record the number of regis-
1256 // ters with IF candidates, where R appears in at least one set.
1258 UnsignedMap UseC, RemC;
1259 IFMapType::iterator End = IFMap.end();
1261 for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
1262 const IFListType &LL = I->second;
1264 for (unsigned i = 0, n = LL.size(); i < n; ++i)
1265 TT.insert(LL[i].second);
1266 for (unsigned R = TT.find_first(); R; R = TT.find_next(R))
1271 for (unsigned R = AllRMs.find_first(); R; R = AllRMs.find_next(R)) {
1272 typedef MachineRegisterInfo::use_nodbg_iterator use_iterator;
1273 typedef SmallSet<const MachineInstr*,16> InstrSet;
1275 // Count as the number of instructions in which R is used, not the
1276 // number of operands.
1277 use_iterator E = MRI->use_nodbg_end();
1278 for (use_iterator I = MRI->use_nodbg_begin(R); I != E; ++I)
1279 UIs.insert(I->getParent());
1280 unsigned C = UIs.size();
1281 // Calculate a measure, which is the number of instructions using R,
1282 // minus the "removability" count computed earlier.
1283 unsigned D = RemC[R];
1284 UseC[R] = (C > D) ? C-D : 0; // doz
1287 bool SelectAll0 = OptSelectAll0, SelectHas0 = OptSelectHas0;
1288 if (!SelectAll0 && !SelectHas0)
1291 // The smaller the number UseC for a given register R, the "less used"
1292 // R is aside from the opportunities for removal offered by generating
1293 // "insert" instructions.
1294 // Iterate over the IF map, and for those registers that have multiple
1295 // candidates, pick the minimum one according to IFOrdering.
1296 IFOrdering IFO(UseC, BaseOrd);
1297 for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
1298 IFListType &LL = I->second;
1301 // Get the minimum element, remember it and clear the list. If the
1302 // element found is adequate, we will put it back on the list, other-
1303 // wise the list will remain empty, and the entry for this register
1304 // will be removed (i.e. this register will not be replaced by insert).
1305 IFListType::iterator MinI = std::min_element(LL.begin(), LL.end(), IFO);
1306 assert(MinI != LL.end());
1307 IFRecordWithRegSet M = *MinI;
1310 // We want to make sure that this replacement will have a chance to be
1311 // beneficial, and that means that we want to have indication that some
1312 // register will be removed. The most likely registers to be eliminated
1313 // are the use operands in the definition of I->first. Accept/reject a
1314 // candidate based on how many of its uses it can potentially eliminate.
1317 const MachineInstr *DefI = MRI->getVRegDef(I->first);
1318 getInstrUses(DefI, Us);
1319 bool Accept = false;
1323 for (unsigned R = Us.find_first(); R; R = Us.find_next(R)) {
1330 } else if (SelectHas0) {
1332 for (unsigned R = Us.find_first(); R; R = Us.find_next(R)) {
1344 // Remove candidates that add uses of removable registers, unless the
1345 // removable registers are among replacement candidates.
1346 // Recompute the removable registers, since some candidates may have
1349 for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
1350 const IFListType &LL = I->second;
1352 AllRMs.insert(LL[0].second);
1354 for (IFMapType::iterator I = IFMap.begin(); I != End; ++I) {
1355 IFListType &LL = I->second;
1358 unsigned SR = LL[0].first.SrcR, IR = LL[0].first.InsR;
1359 if (AllRMs[SR] || AllRMs[IR])
1366 bool HexagonGenInsert::generateInserts() {
1367 // Create a new register for each one from IFMap, and store them in the
1370 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1371 unsigned VR = I->first;
1372 const TargetRegisterClass *RC = MRI->getRegClass(VR);
1373 unsigned NewVR = MRI->createVirtualRegister(RC);
1377 // We can generate the "insert" instructions using potentially stale re-
1378 // gisters: SrcR and InsR for a given VR may be among other registers that
1379 // are also replaced. This is fine, we will do the mass "rauw" a bit later.
1380 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1381 MachineInstr *MI = MRI->getVRegDef(I->first);
1382 MachineBasicBlock &B = *MI->getParent();
1383 DebugLoc DL = MI->getDebugLoc();
1384 unsigned NewR = RegMap[I->first];
1385 bool R32 = MRI->getRegClass(NewR) == &Hexagon::IntRegsRegClass;
1386 const MCInstrDesc &D = R32 ? HII->get(Hexagon::S2_insert)
1387 : HII->get(Hexagon::S2_insertp);
1388 IFRecord IF = I->second[0].first;
1389 unsigned Wdh = IF.Wdh, Off = IF.Off;
1391 if (R32 && MRI->getRegClass(IF.InsR) == &Hexagon::DoubleRegsRegClass) {
1392 InsS = Hexagon::isub_lo;
1394 InsS = Hexagon::isub_hi;
1398 // Advance to the proper location for inserting instructions. This could
1400 MachineBasicBlock::iterator At = MI;
1402 At = B.getFirstNonPHI();
1404 BuildMI(B, At, DL, D, NewR)
1406 .addReg(IF.InsR, 0, InsS)
1410 MRI->clearKillFlags(IF.SrcR);
1411 MRI->clearKillFlags(IF.InsR);
1414 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1415 MachineInstr *DefI = MRI->getVRegDef(I->first);
1416 MRI->replaceRegWith(I->first, RegMap[I->first]);
1417 DefI->eraseFromParent();
1423 bool HexagonGenInsert::removeDeadCode(MachineDomTreeNode *N) {
1424 bool Changed = false;
1425 typedef GraphTraits<MachineDomTreeNode*> GTN;
1426 for (auto I = GTN::child_begin(N), E = GTN::child_end(N); I != E; ++I)
1427 Changed |= removeDeadCode(*I);
1429 MachineBasicBlock *B = N->getBlock();
1430 std::vector<MachineInstr*> Instrs;
1431 for (auto I = B->rbegin(), E = B->rend(); I != E; ++I)
1432 Instrs.push_back(&*I);
1434 for (auto I = Instrs.begin(), E = Instrs.end(); I != E; ++I) {
1435 MachineInstr *MI = *I;
1436 unsigned Opc = MI->getOpcode();
1437 // Do not touch lifetime markers. This is why the target-independent DCE
1439 if (Opc == TargetOpcode::LIFETIME_START ||
1440 Opc == TargetOpcode::LIFETIME_END)
1443 if (MI->isInlineAsm() || !MI->isSafeToMove(nullptr, Store))
1446 bool AllDead = true;
1447 SmallVector<unsigned,2> Regs;
1448 for (const MachineOperand &MO : MI->operands()) {
1449 if (!MO.isReg() || !MO.isDef())
1451 unsigned R = MO.getReg();
1452 if (!TargetRegisterInfo::isVirtualRegister(R) ||
1453 !MRI->use_nodbg_empty(R)) {
1463 for (unsigned I = 0, N = Regs.size(); I != N; ++I)
1464 MRI->markUsesInDebugValueAsUndef(Regs[I]);
1471 bool HexagonGenInsert::runOnMachineFunction(MachineFunction &MF) {
1472 if (skipFunction(*MF.getFunction()))
1475 bool Timing = OptTiming, TimingDetail = Timing && OptTimingDetail;
1476 bool Changed = false;
1478 // Sanity check: one, but not both.
1479 assert(!OptSelectAll0 || !OptSelectHas0);
1485 const auto &ST = MF.getSubtarget<HexagonSubtarget>();
1486 HII = ST.getInstrInfo();
1487 HRI = ST.getRegisterInfo();
1489 MRI = &MF.getRegInfo();
1490 MDT = &getAnalysis<MachineDominatorTree>();
1492 // Clean up before any further processing, so that dead code does not
1493 // get used in a newly generated "insert" instruction. Have a custom
1494 // version of DCE that preserves lifetime markers. Without it, merging
1495 // of stack objects can fail to recognize and merge disjoint objects
1496 // leading to unnecessary stack growth.
1497 Changed = removeDeadCode(MDT->getRootNode());
1499 const HexagonEvaluator HE(*HRI, *MRI, *HII, MF);
1500 BitTracker BTLoc(HE, MF);
1501 BTLoc.trace(isDebug());
1503 CellMapShadow MS(BTLoc);
1506 buildOrderingMF(BaseOrd);
1507 buildOrderingBT(BaseOrd, CellOrd);
1510 dbgs() << "Cell ordering:\n";
1511 for (RegisterOrdering::iterator I = CellOrd.begin(), E = CellOrd.end();
1513 unsigned VR = I->first, Pos = I->second;
1514 dbgs() << PrintReg(VR, HRI) << " -> " << Pos << "\n";
1518 // Collect candidates for conversion into the insert forms.
1519 MachineBasicBlock *RootB = MDT->getRoot();
1520 OrderedRegisterList AvailR(CellOrd);
1522 const char *const TGName = "hexinsert";
1523 const char *const TGDesc = "Generate Insert Instructions";
1526 NamedRegionTimer _T("collection", "collection", TGName, TGDesc,
1528 collectInBlock(RootB, AvailR);
1529 // Complete the information gathered in IFMap.
1530 computeRemovableRegisters();
1534 dbgs() << "Candidates after collection:\n";
1542 NamedRegionTimer _T("pruning", "pruning", TGName, TGDesc, TimingDetail);
1547 dbgs() << "Candidates after pruning:\n";
1555 NamedRegionTimer _T("selection", "selection", TGName, TGDesc, TimingDetail);
1560 dbgs() << "Candidates after selection:\n";
1564 // Filter out vregs beyond the cutoff.
1565 if (VRegIndexCutoff.getPosition()) {
1566 unsigned Cutoff = VRegIndexCutoff;
1567 typedef SmallVector<IFMapType::iterator,16> IterListType;
1569 for (IFMapType::iterator I = IFMap.begin(), E = IFMap.end(); I != E; ++I) {
1570 unsigned Idx = TargetRegisterInfo::virtReg2Index(I->first);
1574 for (unsigned i = 0, n = Out.size(); i < n; ++i)
1575 IFMap.erase(Out[i]);
1581 NamedRegionTimer _T("generation", "generation", TGName, TGDesc,
1589 FunctionPass *llvm::createHexagonGenInsert() {
1590 return new HexagonGenInsert();
1593 //===----------------------------------------------------------------------===//
1594 // Public Constructor Functions
1595 //===----------------------------------------------------------------------===//
1597 INITIALIZE_PASS_BEGIN(HexagonGenInsert, "hexinsert",
1598 "Hexagon generate \"insert\" instructions", false, false)
1599 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
1600 INITIALIZE_PASS_END(HexagonGenInsert, "hexinsert",
1601 "Hexagon generate \"insert\" instructions", false, false)