Coverage Report

Created: 2019-07-24 05:18

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