Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp
Line
Count
Source (jump to first uncovered line)
1
//===-- HexagonISelDAGToDAGHVX.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 "Hexagon.h"
10
#include "HexagonISelDAGToDAG.h"
11
#include "HexagonISelLowering.h"
12
#include "HexagonTargetMachine.h"
13
#include "llvm/ADT/SetVector.h"
14
#include "llvm/CodeGen/MachineInstrBuilder.h"
15
#include "llvm/CodeGen/SelectionDAGISel.h"
16
#include "llvm/IR/Intrinsics.h"
17
#include "llvm/Support/CommandLine.h"
18
#include "llvm/Support/Debug.h"
19
20
#include <deque>
21
#include <map>
22
#include <set>
23
#include <utility>
24
#include <vector>
25
26
#define DEBUG_TYPE "hexagon-isel"
27
28
using namespace llvm;
29
30
namespace {
31
32
// --------------------------------------------------------------------
33
// Implementation of permutation networks.
34
35
// Implementation of the node routing through butterfly networks:
36
// - Forward delta.
37
// - Reverse delta.
38
// - Benes.
39
//
40
//
41
// Forward delta network consists of log(N) steps, where N is the number
42
// of inputs. In each step, an input can stay in place, or it can get
43
// routed to another position[1]. The step after that consists of two
44
// networks, each half in size in terms of the number of nodes. In those
45
// terms, in the given step, an input can go to either the upper or the
46
// lower network in the next step.
47
//
48
// [1] Hexagon's vdelta/vrdelta allow an element to be routed to both
49
// positions as long as there is no conflict.
50
51
// Here's a delta network for 8 inputs, only the switching routes are
52
// shown:
53
//
54
//         Steps:
55
//         |- 1 ---------------|- 2 -----|- 3 -|
56
//
57
// Inp[0] ***                 ***       ***   *** Out[0]
58
//           \               /   \     /   \ /
59
//            \             /     \   /     X
60
//             \           /       \ /     / \
61
// Inp[1] ***   \         /   ***   X   ***   *** Out[1]
62
//           \   \       /   /   \ / \ /
63
//            \   \     /   /     X   X
64
//             \   \   /   /     / \ / \
65
// Inp[2] ***   \   \ /   /   ***   X   ***   *** Out[2]
66
//           \   \   X   /   /     / \     \ /
67
//            \   \ / \ /   /     /   \     X
68
//             \   X   X   /     /     \   / \
69
// Inp[3] ***   \ / \ / \ /   ***       ***   *** Out[3]
70
//           \   X   X   X   /
71
//            \ / \ / \ / \ /
72
//             X   X   X   X
73
//            / \ / \ / \ / \
74
//           /   X   X   X   \
75
// Inp[4] ***   / \ / \ / \   ***       ***   *** Out[4]
76
//             /   X   X   \     \     /   \ /
77
//            /   / \ / \   \     \   /     X
78
//           /   /   X   \   \     \ /     / \
79
// Inp[5] ***   /   / \   \   ***   X   ***   *** Out[5]
80
//             /   /   \   \     \ / \ /
81
//            /   /     \   \     X   X
82
//           /   /       \   \   / \ / \
83
// Inp[6] ***   /         \   ***   X   ***   *** Out[6]
84
//             /           \       / \     \ /
85
//            /             \     /   \     X
86
//           /               \   /     \   / \
87
// Inp[7] ***                 ***       ***   *** Out[7]
88
//
89
//
90
// Reverse delta network is same as delta network, with the steps in
91
// the opposite order.
92
//
93
//
94
// Benes network is a forward delta network immediately followed by
95
// a reverse delta network.
96
97
enum class ColorKind { None, Red, Black };
98
99
// Graph coloring utility used to partition nodes into two groups:
100
// they will correspond to nodes routed to the upper and lower networks.
101
struct Coloring {
102
  using Node = int;
103
  using MapType = std::map<Node, ColorKind>;
104
  static constexpr Node Ignore = Node(-1);
105
106
656
  Coloring(ArrayRef<Node> Ord) : Order(Ord) {
107
656
    build();
108
656
    if (!color())
109
0
      Colors.clear();
110
656
  }
111
112
656
  const MapType &colors() const {
113
656
    return Colors;
114
656
  }
115
116
3.69k
  ColorKind other(ColorKind Color) {
117
3.69k
    if (Color == ColorKind::None)
118
2.08k
      return ColorKind::Red;
119
1.61k
    return Color == ColorKind::Red ? ColorKind::Black : 
ColorKind::Red0
;
120
1.61k
  }
121
122
  LLVM_DUMP_METHOD void dump() const;
123
124
private:
125
  ArrayRef<Node> Order;
126
  MapType Colors;
127
  std::set<Node> Needed;
128
129
  using NodeSet = std::set<Node>;
130
  std::map<Node,NodeSet> Edges;
131
132
12.6k
  Node conj(Node Pos) {
133
12.6k
    Node Num = Order.size();
134
12.6k
    return (Pos < Num/2) ? 
Pos + Num/26.33k
:
Pos - Num/26.28k
;
135
12.6k
  }
136
137
3.09k
  ColorKind getColor(Node N) {
138
3.09k
    auto F = Colors.find(N);
139
3.09k
    return F != Colors.end() ? 
F->second1.54k
:
ColorKind::None1.54k
;
140
3.09k
  }
141
142
  std::pair<bool, ColorKind> getUniqueColor(const NodeSet &Nodes);
143
144
  void build();
145
  bool color();
146
};
147
} // namespace
148
149
3.63k
std::pair<bool, ColorKind> Coloring::getUniqueColor(const NodeSet &Nodes) {
150
3.63k
  auto Color = ColorKind::None;
151
3.63k
  for (Node N : Nodes) {
152
3.09k
    ColorKind ColorN = getColor(N);
153
3.09k
    if (ColorN == ColorKind::None)
154
1.54k
      continue;
155
1.54k
    if (Color == ColorKind::None)
156
1.54k
      Color = ColorN;
157
0
    else if (Color != ColorKind::None && Color != ColorN)
158
0
      return { false, ColorKind::None };
159
1.54k
  }
160
3.63k
  return { true, Color };
161
3.63k
}
162
163
656
void Coloring::build() {
164
656
  // Add Order[P] and Order[conj(P)] to Edges.
165
7.00k
  for (unsigned P = 0; P != Order.size(); 
++P6.35k
) {
166
6.35k
    Node I = Order[P];
167
6.35k
    if (I != Ignore) {
168
5.36k
      Needed.insert(I);
169
5.36k
      Node PC = Order[conj(P)];
170
5.36k
      if (PC != Ignore && 
PC != I4.36k
)
171
1.02k
        Edges[I].insert(PC);
172
5.36k
    }
173
6.35k
  }
174
656
  // Add I and conj(I) to Edges.
175
7.00k
  for (unsigned I = 0; I != Order.size(); 
++I6.35k
) {
176
6.35k
    if (!Needed.count(I))
177
2.72k
      continue;
178
3.63k
    Node C = conj(I);
179
3.63k
    // This will create an entry in the edge table, even if I is not
180
3.63k
    // connected to any other node. This is necessary, because it still
181
3.63k
    // needs to be colored.
182
3.63k
    NodeSet &Is = Edges[I];
183
3.63k
    if (Needed.count(C))
184
3.09k
      Is.insert(C);
185
3.63k
  }
186
656
}
187
188
656
bool Coloring::color() {
189
656
  SetVector<Node> FirstQ;
190
3.63k
  auto Enqueue = [this,&FirstQ] (Node N) {
191
3.63k
    SetVector<Node> Q;
192
3.63k
    Q.insert(N);
193
10.3k
    for (unsigned I = 0; I != Q.size(); 
++I6.72k
) {
194
6.72k
      NodeSet &Ns = Edges[Q[I]];
195
6.72k
      Q.insert(Ns.begin(), Ns.end());
196
6.72k
    }
197
3.63k
    FirstQ.insert(Q.begin(), Q.end());
198
3.63k
  };
199
656
  for (Node N : Needed)
200
3.63k
    Enqueue(N);
201
656
202
3.63k
  for (Node N : FirstQ) {
203
3.63k
    if (Colors.count(N))
204
0
      continue;
205
3.63k
    NodeSet &Ns = Edges[N];
206
3.63k
    auto P = getUniqueColor(Ns);
207
3.63k
    if (!P.first)
208
0
      return false;
209
3.63k
    Colors[N] = other(P.second);
210
3.63k
  }
211
656
212
656
  // First, color nodes that don't have any dups.
213
3.63k
  
for (auto E : Edges)656
{
214
3.63k
    Node N = E.first;
215
3.63k
    if (!Needed.count(conj(N)) || 
Colors.count(N)3.09k
)
216
3.63k
      continue;
217
0
    auto P = getUniqueColor(E.second);
218
0
    if (!P.first)
219
0
      return false;
220
0
    Colors[N] = other(P.second);
221
0
  }
222
656
223
656
  // Now, nodes that are still uncolored. Since the graph can be modified
224
656
  // in this step, create a work queue.
225
656
  std::vector<Node> WorkQ;
226
3.63k
  for (auto E : Edges) {
227
3.63k
    Node N = E.first;
228
3.63k
    if (!Colors.count(N))
229
0
      WorkQ.push_back(N);
230
3.63k
  }
231
656
232
656
  for (unsigned I = 0; I < WorkQ.size(); 
++I0
) {
233
0
    Node N = WorkQ[I];
234
0
    NodeSet &Ns = Edges[N];
235
0
    auto P = getUniqueColor(Ns);
236
0
    if (P.first) {
237
0
      Colors[N] = other(P.second);
238
0
      continue;
239
0
    }
240
0
241
0
    // Coloring failed. Split this node.
242
0
    Node C = conj(N);
243
0
    ColorKind ColorN = other(ColorKind::None);
244
0
    ColorKind ColorC = other(ColorN);
245
0
    NodeSet &Cs = Edges[C];
246
0
    NodeSet CopyNs = Ns;
247
0
    for (Node M : CopyNs) {
248
0
      ColorKind ColorM = getColor(M);
249
0
      if (ColorM == ColorC) {
250
0
        // Connect M with C, disconnect M from N.
251
0
        Cs.insert(M);
252
0
        Edges[M].insert(C);
253
0
        Ns.erase(M);
254
0
        Edges[M].erase(N);
255
0
      }
256
0
    }
257
0
    Colors[N] = ColorN;
258
0
    Colors[C] = ColorC;
259
0
  }
260
656
261
656
  // Explicitly assign "None" to all uncolored nodes.
262
7.00k
  for (unsigned I = 0; I != Order.size(); 
++I6.35k
)
263
6.35k
    if (Colors.count(I) == 0)
264
2.72k
      Colors[I] = ColorKind::None;
265
656
266
656
  return true;
267
656
}
268
269
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
270
void Coloring::dump() const {
271
  dbgs() << "{ Order:   {";
272
  for (unsigned I = 0; I != Order.size(); ++I) {
273
    Node P = Order[I];
274
    if (P != Ignore)
275
      dbgs() << ' ' << P;
276
    else
277
      dbgs() << " -";
278
  }
279
  dbgs() << " }\n";
280
  dbgs() << "  Needed: {";
281
  for (Node N : Needed)
282
    dbgs() << ' ' << N;
283
  dbgs() << " }\n";
284
285
  dbgs() << "  Edges: {\n";
286
  for (auto E : Edges) {
287
    dbgs() << "    " << E.first << " -> {";
288
    for (auto N : E.second)
289
      dbgs() << ' ' << N;
290
    dbgs() << " }\n";
291
  }
292
  dbgs() << "  }\n";
293
294
  auto ColorKindToName = [](ColorKind C) {
295
    switch (C) {
296
    case ColorKind::None:
297
      return "None";
298
    case ColorKind::Red:
299
      return "Red";
300
    case ColorKind::Black:
301
      return "Black";
302
    }
303
    llvm_unreachable("all ColorKinds should be handled by the switch above");
304
  };
305
306
  dbgs() << "  Colors: {\n";
307
  for (auto C : Colors)
308
    dbgs() << "    " << C.first << " -> " << ColorKindToName(C.second) << "\n";
309
  dbgs() << "  }\n}\n";
310
}
311
#endif
312
313
namespace {
314
// Base class of for reordering networks. They don't strictly need to be
315
// permutations, as outputs with repeated occurrences of an input element
316
// are allowed.
317
struct PermNetwork {
318
  using Controls = std::vector<uint8_t>;
319
  using ElemType = int;
320
  static constexpr ElemType Ignore = ElemType(-1);
321
322
  enum : uint8_t {
323
    None,
324
    Pass,
325
    Switch
326
  };
327
  enum : uint8_t {
328
    Forward,
329
    Reverse
330
  };
331
332
139
  PermNetwork(ArrayRef<ElemType> Ord, unsigned Mult = 1) {
333
139
    Order.assign(Ord.data(), Ord.data()+Ord.size());
334
139
    Log = 0;
335
139
336
139
    unsigned S = Order.size();
337
1.01k
    while (S >>= 1)
338
871
      ++Log;
339
139
340
139
    Table.resize(Order.size());
341
139
    for (RowType &Row : Table)
342
11.2k
      Row.resize(Mult*Log, None);
343
139
  }
344
345
130
  void getControls(Controls &V, unsigned StartAt, uint8_t Dir) const {
346
130
    unsigned Size = Order.size();
347
130
    V.resize(Size);
348
10.3k
    for (unsigned I = 0; I != Size; 
++I10.1k
) {
349
10.1k
      unsigned W = 0;
350
74.9k
      for (unsigned L = 0; L != Log; 
++L64.7k
) {
351
64.7k
        unsigned C = ctl(I, StartAt+L) == Switch;
352
64.7k
        if (Dir == Forward)
353
57.2k
          W |= C << (Log-1-L);
354
7.55k
        else
355
7.55k
          W |= C << L;
356
64.7k
      }
357
10.1k
      assert(isUInt<8>(W));
358
10.1k
      V[I] = uint8_t(W);
359
10.1k
    }
360
130
  }
361
362
64.7k
  uint8_t ctl(ElemType Pos, unsigned Step) const {
363
64.7k
    return Table[Pos][Step];
364
64.7k
  }
365
139
  unsigned size() const {
366
139
    return Order.size();
367
139
  }
368
0
  unsigned steps() const {
369
0
    return Log;
370
0
  }
371
372
protected:
373
  unsigned Log;
374
  std::vector<ElemType> Order;
375
  using RowType = std::vector<uint8_t>;
376
  std::vector<RowType> Table;
377
};
378
379
struct ForwardDeltaNetwork : public PermNetwork {
380
130
  ForwardDeltaNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord) {}
381
382
130
  bool run(Controls &V) {
383
130
    if (!route(Order.data(), Table.data(), size(), 0))
384
9
      return false;
385
121
    getControls(V, 0, Forward);
386
121
    return true;
387
121
  }
388
389
private:
390
  bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);
391
};
392
393
struct ReverseDeltaNetwork : public PermNetwork {
394
9
  ReverseDeltaNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord) {}
395
396
9
  bool run(Controls &V) {
397
9
    if (!route(Order.data(), Table.data(), size(), 0))
398
0
      return false;
399
9
    getControls(V, 0, Reverse);
400
9
    return true;
401
9
  }
402
403
private:
404
  bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);
405
};
406
407
struct BenesNetwork : public PermNetwork {
408
0
  BenesNetwork(ArrayRef<ElemType> Ord) : PermNetwork(Ord, 2) {}
409
410
0
  bool run(Controls &F, Controls &R) {
411
0
    if (!route(Order.data(), Table.data(), size(), 0))
412
0
      return false;
413
0
414
0
    getControls(F, 0, Forward);
415
0
    getControls(R, Log, Reverse);
416
0
    return true;
417
0
  }
418
419
private:
420
  bool route(ElemType *P, RowType *T, unsigned Size, unsigned Step);
421
};
422
} // namespace
423
424
bool ForwardDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size,
425
7.48k
                                unsigned Step) {
426
7.48k
  bool UseUp = false, UseDown = false;
427
7.48k
  ElemType Num = Size;
428
7.48k
429
7.48k
  // Cannot use coloring here, because coloring is used to determine
430
7.48k
  // the "big" switch, i.e. the one that changes halves, and in a forward
431
7.48k
  // network, a color can be simultaneously routed to both halves in the
432
7.48k
  // step we're working on.
433
60.7k
  for (ElemType J = 0; J != Num; 
++J53.2k
) {
434
53.2k
    ElemType I = P[J];
435
53.2k
    // I is the position in the input,
436
53.2k
    // J is the position in the output.
437
53.2k
    if (I == Ignore)
438
14.6k
      continue;
439
38.6k
    uint8_t S;
440
38.6k
    if (I < Num/2)
441
18.3k
      S = (J < Num/2) ? 
Pass9.39k
:
Switch8.97k
;
442
20.2k
    else
443
20.2k
      S = (J < Num/2) ? 
Switch9.89k
:
Pass10.3k
;
444
38.6k
445
38.6k
    // U is the element in the table that needs to be updated.
446
38.6k
    ElemType U = (S == Pass) ? 
I19.7k
:
(I < Num/2 18.8k
?
I+Num/28.97k
:
I-Num/29.89k
);
447
38.6k
    if (U < Num/2)
448
19.2k
      UseUp = true;
449
19.3k
    else
450
19.3k
      UseDown = true;
451
38.6k
    if (T[U][Step] != S && 
T[U][Step] != None21.9k
)
452
9
      return false;
453
38.5k
    T[U][Step] = S;
454
38.5k
  }
455
7.48k
456
60.2k
  
for (ElemType J = 0; 7.47k
J != Num;
++J52.7k
)
457
52.7k
    if (P[J] != Ignore && 
P[J] >= Num/238.3k
)
458
20.2k
      P[J] -= Num/2;
459
7.47k
460
7.47k
  if (Step+1 < Log) {
461
3.98k
    if (UseUp   && 
!route(P, T, Size/2, Step+1)3.66k
)
462
1
      return false;
463
3.98k
    if (UseDown && 
!route(P+Size/2, T+Size/2, Size/2, Step+1)3.69k
)
464
0
      return false;
465
7.47k
  }
466
7.47k
  return true;
467
7.47k
}
468
469
bool ReverseDeltaNetwork::route(ElemType *P, RowType *T, unsigned Size,
470
656
                                unsigned Step) {
471
656
  unsigned Pets = Log-1 - Step;
472
656
  bool UseUp = false, UseDown = false;
473
656
  ElemType Num = Size;
474
656
475
656
  // In this step half-switching occurs, so coloring can be used.
476
656
  Coloring G({P,Size});
477
656
  const Coloring::MapType &M = G.colors();
478
656
  if (M.empty())
479
0
    return false;
480
656
481
656
  ColorKind ColorUp = ColorKind::None;
482
7.00k
  for (ElemType J = 0; J != Num; 
++J6.35k
) {
483
6.35k
    ElemType I = P[J];
484
6.35k
    // I is the position in the input,
485
6.35k
    // J is the position in the output.
486
6.35k
    if (I == Ignore)
487
992
      continue;
488
5.36k
    ColorKind C = M.at(I);
489
5.36k
    if (C == ColorKind::None)
490
0
      continue;
491
5.36k
    // During "Step", inputs cannot switch halves, so if the "up" color
492
5.36k
    // is still unknown, make sure that it is selected in such a way that
493
5.36k
    // "I" will stay in the same half.
494
5.36k
    bool InpUp = I < Num/2;
495
5.36k
    if (ColorUp == ColorKind::None)
496
656
      ColorUp = InpUp ? 
C592
:
G.other(C)64
;
497
5.36k
    if ((C == ColorUp) != InpUp) {
498
0
      // If I should go to a different half than where is it now, give up.
499
0
      return false;
500
0
    }
501
5.36k
502
5.36k
    uint8_t S;
503
5.36k
    if (InpUp) {
504
2.73k
      S = (J < Num/2) ? 
Pass1.62k
:
Switch1.11k
;
505
2.73k
      UseUp = true;
506
2.73k
    } else {
507
2.62k
      S = (J < Num/2) ? 
Switch1.05k
:
Pass1.56k
;
508
2.62k
      UseDown = true;
509
2.62k
    }
510
5.36k
    T[J][Pets] = S;
511
5.36k
  }
512
656
513
656
  // Reorder the working permutation according to the computed switch table
514
656
  // for the last step (i.e. Pets).
515
3.83k
  
for (ElemType J = 0, E = Size / 2; 656
J != E;
++J3.17k
) {
516
3.17k
    ElemType PJ = P[J];         // Current values of P[J]
517
3.17k
    ElemType PC = P[J+Size/2];  // and P[conj(J)]
518
3.17k
    ElemType QJ = PJ;           // New values of P[J]
519
3.17k
    ElemType QC = PC;           // and P[conj(J)]
520
3.17k
    if (T[J][Pets] == Switch)
521
1.05k
      QC = PJ;
522
3.17k
    if (T[J+Size/2][Pets] == Switch)
523
1.11k
      QJ = PC;
524
3.17k
    P[J] = QJ;
525
3.17k
    P[J+Size/2] = QC;
526
3.17k
  }
527
656
528
7.00k
  for (ElemType J = 0; J != Num; 
++J6.35k
)
529
6.35k
    if (P[J] != Ignore && 
P[J] >= Num/25.85k
)
530
2.87k
      P[J] -= Num/2;
531
656
532
656
  if (Step+1 < Log) {
533
392
    if (UseUp && 
!route(P, T, Size/2, Step+1)328
)
534
0
      return false;
535
392
    if (UseDown && 
!route(P+Size/2, T+Size/2, Size/2, Step+1)319
)
536
0
      return false;
537
656
  }
538
656
  return true;
539
656
}
540
541
bool BenesNetwork::route(ElemType *P, RowType *T, unsigned Size,
542
0
                         unsigned Step) {
543
0
  Coloring G({P,Size});
544
0
  const Coloring::MapType &M = G.colors();
545
0
  if (M.empty())
546
0
    return false;
547
0
  ElemType Num = Size;
548
0
549
0
  unsigned Pets = 2*Log-1 - Step;
550
0
  bool UseUp = false, UseDown = false;
551
0
552
0
  // Both assignments, i.e. Red->Up and Red->Down are valid, but they will
553
0
  // result in different controls. Let's pick the one where the first
554
0
  // control will be "Pass".
555
0
  ColorKind ColorUp = ColorKind::None;
556
0
  for (ElemType J = 0; J != Num; ++J) {
557
0
    ElemType I = P[J];
558
0
    if (I == Ignore)
559
0
      continue;
560
0
    ColorKind C = M.at(I);
561
0
    if (C == ColorKind::None)
562
0
      continue;
563
0
    if (ColorUp == ColorKind::None) {
564
0
      ColorUp = (I < Num / 2) ? ColorKind::Red : ColorKind::Black;
565
0
    }
566
0
    unsigned CI = (I < Num/2) ? I+Num/2 : I-Num/2;
567
0
    if (C == ColorUp) {
568
0
      if (I < Num/2)
569
0
        T[I][Step] = Pass;
570
0
      else
571
0
        T[CI][Step] = Switch;
572
0
      T[J][Pets] = (J < Num/2) ? Pass : Switch;
573
0
      UseUp = true;
574
0
    } else { // Down
575
0
      if (I < Num/2)
576
0
        T[CI][Step] = Switch;
577
0
      else
578
0
        T[I][Step] = Pass;
579
0
      T[J][Pets] = (J < Num/2) ? Switch : Pass;
580
0
      UseDown = true;
581
0
    }
582
0
  }
583
0
584
0
  // Reorder the working permutation according to the computed switch table
585
0
  // for the last step (i.e. Pets).
586
0
  for (ElemType J = 0; J != Num/2; ++J) {
587
0
    ElemType PJ = P[J];         // Current values of P[J]
588
0
    ElemType PC = P[J+Num/2];   // and P[conj(J)]
589
0
    ElemType QJ = PJ;           // New values of P[J]
590
0
    ElemType QC = PC;           // and P[conj(J)]
591
0
    if (T[J][Pets] == Switch)
592
0
      QC = PJ;
593
0
    if (T[J+Num/2][Pets] == Switch)
594
0
      QJ = PC;
595
0
    P[J] = QJ;
596
0
    P[J+Num/2] = QC;
597
0
  }
598
0
599
0
  for (ElemType J = 0; J != Num; ++J)
600
0
    if (P[J] != Ignore && P[J] >= Num/2)
601
0
      P[J] -= Num/2;
602
0
603
0
  if (Step+1 < Log) {
604
0
    if (UseUp && !route(P, T, Size/2, Step+1))
605
0
      return false;
606
0
    if (UseDown && !route(P+Size/2, T+Size/2, Size/2, Step+1))
607
0
      return false;
608
0
  }
609
0
  return true;
610
0
}
611
612
// --------------------------------------------------------------------
613
// Support for building selection results (output instructions that are
614
// parts of the final selection).
615
616
namespace {
617
struct OpRef {
618
5.89k
  OpRef(SDValue V) : OpV(V) {}
619
19.5k
  bool isValue() const { return OpV.getNode() != nullptr; }
620
7.56k
  bool isValid() const { return isValue() || !(OpN & Invalid); }
621
5.14k
  static OpRef res(int N) { return OpRef(Whole | (N & Index)); }
622
1.28k
  static OpRef fail() { return OpRef(Invalid); }
623
624
1.87k
  static OpRef lo(const OpRef &R) {
625
1.87k
    assert(!R.isValue());
626
1.87k
    return OpRef(R.OpN & (Undef | Index | LoHalf));
627
1.87k
  }
628
1.87k
  static OpRef hi(const OpRef &R) {
629
1.87k
    assert(!R.isValue());
630
1.87k
    return OpRef(R.OpN & (Undef | Index | HiHalf));
631
1.87k
  }
632
1.32k
  static OpRef undef(MVT Ty) { return OpRef(Undef | Ty.SimpleTy); }
633
634
  // Direct value.
635
  SDValue OpV = SDValue();
636
637
  // Reference to the operand of the input node:
638
  // If the 31st bit is 1, it's undef, otherwise, bits 28..0 are the
639
  // operand index:
640
  // If bit 30 is set, it's the high half of the operand.
641
  // If bit 29 is set, it's the low half of the operand.
642
  unsigned OpN = 0;
643
644
  enum : unsigned {
645
    Invalid = 0x10000000,
646
    LoHalf  = 0x20000000,
647
    HiHalf  = 0x40000000,
648
    Whole   = LoHalf | HiHalf,
649
    Undef   = 0x80000000,
650
    Index   = 0x0FFFFFFF,  // Mask of the index value.
651
    IndexBits = 28,
652
  };
653
654
  LLVM_DUMP_METHOD
655
  void print(raw_ostream &OS, const SelectionDAG &G) const;
656
657
private:
658
11.5k
  OpRef(unsigned N) : OpN(N) {}
659
};
660
661
struct NodeTemplate {
662
6.17k
  NodeTemplate() = default;
663
  unsigned Opc = 0;
664
  MVT Ty = MVT::Other;
665
  std::vector<OpRef> Ops;
666
667
  LLVM_DUMP_METHOD void print(raw_ostream &OS, const SelectionDAG &G) const;
668
};
669
670
struct ResultStack {
671
  ResultStack(SDNode *Inp)
672
1.02k
    : InpNode(Inp), InpTy(Inp->getValueType(0).getSimpleVT()) {}
673
  SDNode *InpNode;
674
  MVT InpTy;
675
6.17k
  unsigned push(const NodeTemplate &Res) {
676
6.17k
    List.push_back(Res);
677
6.17k
    return List.size()-1;
678
6.17k
  }
679
5.66k
  unsigned push(unsigned Opc, MVT Ty, std::vector<OpRef> &&Ops) {
680
5.66k
    NodeTemplate Res;
681
5.66k
    Res.Opc = Opc;
682
5.66k
    Res.Ty = Ty;
683
5.66k
    Res.Ops = Ops;
684
5.66k
    return push(Res);
685
5.66k
  }
686
1.02k
  bool empty() const { return List.empty(); }
687
5.59k
  unsigned size() const { return List.size(); }
688
4.56k
  unsigned top() const { return size()-1; }
689
6.17k
  const NodeTemplate &operator[](unsigned I) const { return List[I]; }
690
0
  unsigned reset(unsigned NewTop) {
691
0
    List.resize(NewTop+1);
692
0
    return NewTop;
693
0
  }
694
695
  using BaseType = std::vector<NodeTemplate>;
696
0
  BaseType::iterator begin() { return List.begin(); }
697
0
  BaseType::iterator end()   { return List.end(); }
698
0
  BaseType::const_iterator begin() const { return List.begin(); }
699
0
  BaseType::const_iterator end() const   { return List.end(); }
700
701
  BaseType List;
702
703
  LLVM_DUMP_METHOD
704
  void print(raw_ostream &OS, const SelectionDAG &G) const;
705
};
706
} // namespace
707
708
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
709
void OpRef::print(raw_ostream &OS, const SelectionDAG &G) const {
710
  if (isValue()) {
711
    OpV.getNode()->print(OS, &G);
712
    return;
713
  }
714
  if (OpN & Invalid) {
715
    OS << "invalid";
716
    return;
717
  }
718
  if (OpN & Undef) {
719
    OS << "undef";
720
    return;
721
  }
722
  if ((OpN & Whole) != Whole) {
723
    assert((OpN & Whole) == LoHalf || (OpN & Whole) == HiHalf);
724
    if (OpN & LoHalf)
725
      OS << "lo ";
726
    else
727
      OS << "hi ";
728
  }
729
  OS << '#' << SignExtend32(OpN & Index, IndexBits);
730
}
731
732
void NodeTemplate::print(raw_ostream &OS, const SelectionDAG &G) const {
733
  const TargetInstrInfo &TII = *G.getSubtarget().getInstrInfo();
734
  OS << format("%8s", EVT(Ty).getEVTString().c_str()) << "  "
735
     << TII.getName(Opc);
736
  bool Comma = false;
737
  for (const auto &R : Ops) {
738
    if (Comma)
739
      OS << ',';
740
    Comma = true;
741
    OS << ' ';
742
    R.print(OS, G);
743
  }
744
}
745
746
void ResultStack::print(raw_ostream &OS, const SelectionDAG &G) const {
747
  OS << "Input node:\n";
748
#ifndef NDEBUG
749
  InpNode->dumpr(&G);
750
#endif
751
  OS << "Result templates:\n";
752
  for (unsigned I = 0, E = List.size(); I != E; ++I) {
753
    OS << '[' << I << "] ";
754
    List[I].print(OS, G);
755
    OS << '\n';
756
  }
757
}
758
#endif
759
760
namespace {
761
struct ShuffleMask {
762
2.81k
  ShuffleMask(ArrayRef<int> M) : Mask(M) {
763
447k
    for (unsigned I = 0, E = Mask.size(); I != E; 
++I444k
) {
764
444k
      int M = Mask[I];
765
444k
      if (M == -1)
766
122k
        continue;
767
322k
      MinSrc = (MinSrc == -1) ? 
M2.60k
:
std::min(MinSrc, M)320k
;
768
322k
      MaxSrc = (MaxSrc == -1) ? 
M2.60k
:
std::max(MaxSrc, M)320k
;
769
322k
    }
770
2.81k
  }
771
772
  ArrayRef<int> Mask;
773
  int MinSrc = -1, MaxSrc = -1;
774
775
238
  ShuffleMask lo() const {
776
238
    size_t H = Mask.size()/2;
777
238
    return ShuffleMask(Mask.take_front(H));
778
238
  }
779
238
  ShuffleMask hi() const {
780
238
    size_t H = Mask.size()/2;
781
238
    return ShuffleMask(Mask.take_back(H));
782
238
  }
783
784
0
  void print(raw_ostream &OS) const {
785
0
    OS << "MinSrc:" << MinSrc << ", MaxSrc:" << MaxSrc << " {";
786
0
    for (int M : Mask)
787
0
      OS << ' ' << M;
788
0
    OS << " }";
789
0
  }
790
};
791
} // namespace
792
793
// --------------------------------------------------------------------
794
// The HvxSelector class.
795
796
1.18k
static const HexagonTargetLowering &getHexagonLowering(SelectionDAG &G) {
797
1.18k
  return static_cast<const HexagonTargetLowering&>(G.getTargetLoweringInfo());
798
1.18k
}
799
1.18k
static const HexagonSubtarget &getHexagonSubtarget(SelectionDAG &G) {
800
1.18k
  return static_cast<const HexagonSubtarget&>(G.getSubtarget());
801
1.18k
}
802
803
namespace llvm {
804
  struct HvxSelector {
805
    const HexagonTargetLowering &Lower;
806
    HexagonDAGToDAGISel &ISel;
807
    SelectionDAG &DAG;
808
    const HexagonSubtarget &HST;
809
    const unsigned HwLen;
810
811
    HvxSelector(HexagonDAGToDAGISel &HS, SelectionDAG &G)
812
      : Lower(getHexagonLowering(G)),  ISel(HS), DAG(G),
813
1.18k
        HST(getHexagonSubtarget(G)), HwLen(HST.getVectorLength()) {}
814
815
2.78k
    MVT getSingleVT(MVT ElemTy) const {
816
2.78k
      unsigned NumElems = HwLen / (ElemTy.getSizeInBits()/8);
817
2.78k
      return MVT::getVectorVT(ElemTy, NumElems);
818
2.78k
    }
819
820
1.31k
    MVT getPairVT(MVT ElemTy) const {
821
1.31k
      unsigned NumElems = (2*HwLen) / (ElemTy.getSizeInBits()/8);
822
1.31k
      return MVT::getVectorVT(ElemTy, NumElems);
823
1.31k
    }
824
825
    void selectShuffle(SDNode *N);
826
    void selectRor(SDNode *N);
827
    void selectVAlign(SDNode *N);
828
829
  private:
830
    void materialize(const ResultStack &Results);
831
832
    SDValue getVectorConstant(ArrayRef<uint8_t> Data, const SDLoc &dl);
833
834
    enum : unsigned {
835
      None,
836
      PackMux,
837
    };
838
    OpRef concat(OpRef Va, OpRef Vb, ResultStack &Results);
839
    OpRef packs(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results,
840
                MutableArrayRef<int> NewMask, unsigned Options = None);
841
    OpRef packp(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results,
842
                MutableArrayRef<int> NewMask);
843
    OpRef vmuxs(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
844
                ResultStack &Results);
845
    OpRef vmuxp(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
846
                ResultStack &Results);
847
848
    OpRef shuffs1(ShuffleMask SM, OpRef Va, ResultStack &Results);
849
    OpRef shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);
850
    OpRef shuffp1(ShuffleMask SM, OpRef Va, ResultStack &Results);
851
    OpRef shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);
852
853
    OpRef butterfly(ShuffleMask SM, OpRef Va, ResultStack &Results);
854
    OpRef contracting(ShuffleMask SM, OpRef Va, OpRef Vb, ResultStack &Results);
855
    OpRef expanding(ShuffleMask SM, OpRef Va, ResultStack &Results);
856
    OpRef perfect(ShuffleMask SM, OpRef Va, ResultStack &Results);
857
858
    bool selectVectorConstants(SDNode *N);
859
    bool scalarizeShuffle(ArrayRef<int> Mask, const SDLoc &dl, MVT ResTy,
860
                          SDValue Va, SDValue Vb, SDNode *N);
861
862
  };
863
}
864
865
static void splitMask(ArrayRef<int> Mask, MutableArrayRef<int> MaskL,
866
50
                      MutableArrayRef<int> MaskR) {
867
50
  unsigned VecLen = Mask.size();
868
50
  assert(MaskL.size() == VecLen && MaskR.size() == VecLen);
869
3.82k
  for (unsigned I = 0; I != VecLen; 
++I3.77k
) {
870
3.77k
    int M = Mask[I];
871
3.77k
    if (M < 0) {
872
0
      MaskL[I] = MaskR[I] = -1;
873
3.77k
    } else if (unsigned(M) < VecLen) {
874
1.89k
      MaskL[I] = M;
875
1.89k
      MaskR[I] = -1;
876
1.89k
    } else {
877
1.88k
      MaskL[I] = -1;
878
1.88k
      MaskR[I] = M-VecLen;
879
1.88k
    }
880
3.77k
  }
881
50
}
882
883
static std::pair<int,unsigned> findStrip(ArrayRef<int> A, int Inc,
884
2.78k
                                         unsigned MaxLen) {
885
2.78k
  assert(A.size() > 0 && A.size() >= MaxLen);
886
2.78k
  int F = A[0];
887
2.78k
  int E = F;
888
40.5k
  for (unsigned I = 1; I != MaxLen; 
++I37.7k
) {
889
40.4k
    if (A[I] - E != Inc)
890
2.73k
      return { F, I };
891
37.7k
    E = A[I];
892
37.7k
  }
893
2.78k
  
return { F, MaxLen }43
;
894
2.78k
}
895
896
1.90k
static bool isUndef(ArrayRef<int> Mask) {
897
1.90k
  for (int Idx : Mask)
898
4.48k
    if (Idx != -1)
899
1.88k
      return false;
900
1.90k
  
return true18
;
901
1.90k
}
902
903
1.50k
static bool isIdentity(ArrayRef<int> Mask) {
904
78.6k
  for (int I = 0, E = Mask.size(); I != E; 
++I77.1k
) {
905
77.9k
    int M = Mask[I];
906
77.9k
    if (M >= 0 && 
M != I40.9k
)
907
792
      return false;
908
77.9k
  }
909
1.50k
  
return true713
;
910
1.50k
}
911
912
597
static bool isPermutation(ArrayRef<int> Mask) {
913
597
  // Check by adding all numbers only works if there is no overflow.
914
597
  assert(Mask.size() < 0x00007FFF && "Sanity failure");
915
597
  int Sum = 0;
916
97.8k
  for (int Idx : Mask) {
917
97.8k
    if (Idx == -1)
918
115
      return false;
919
97.6k
    Sum += Idx;
920
97.6k
  }
921
597
  int N = Mask.size();
922
482
  return 2*Sum == N*(N-1);
923
597
}
924
925
1.02k
bool HvxSelector::selectVectorConstants(SDNode *N) {
926
1.02k
  // Constant vectors are generated as loads from constant pools or as
927
1.02k
  // splats of a constant value. Since they are generated during the
928
1.02k
  // selection process, the main selection algorithm is not aware of them.
929
1.02k
  // Select them directly here.
930
1.02k
  SmallVector<SDNode*,4> Nodes;
931
1.02k
  SetVector<SDNode*> WorkQ;
932
1.02k
933
1.02k
  // The one-use test for VSPLATW's operand may fail due to dead nodes
934
1.02k
  // left over in the DAG.
935
1.02k
  DAG.RemoveDeadNodes();
936
1.02k
937
1.02k
  // The DAG can change (due to CSE) during selection, so cache all the
938
1.02k
  // unselected nodes first to avoid traversing a mutating DAG.
939
1.02k
940
13.3k
  auto IsNodeToSelect = [] (SDNode *N) {
941
13.3k
    if (N->isMachineOpcode())
942
5.90k
      return false;
943
7.43k
    switch (N->getOpcode()) {
944
7.43k
      case HexagonISD::VZERO:
945
18
      case HexagonISD::VSPLATW:
946
18
        return true;
947
253
      case ISD::LOAD: {
948
253
        SDValue Addr = cast<LoadSDNode>(N)->getBasePtr();
949
253
        unsigned AddrOpc = Addr.getOpcode();
950
253
        if (AddrOpc == HexagonISD::AT_PCREL || AddrOpc == HexagonISD::CP)
951
173
          if (Addr.getOperand(0).getOpcode() == ISD::TargetConstantPool)
952
173
            return true;
953
80
      }
954
80
      break;
955
7.23k
    }
956
7.23k
    // Make sure to select the operand of VSPLATW.
957
7.23k
    bool IsSplatOp = N->hasOneUse() &&
958
7.23k
                     
N->use_begin()->getOpcode() == HexagonISD::VSPLATW3.47k
;
959
7.23k
    return IsSplatOp;
960
7.23k
  };
961
1.02k
962
1.02k
  WorkQ.insert(N);
963
14.3k
  for (unsigned i = 0; i != WorkQ.size(); 
++i13.3k
) {
964
13.3k
    SDNode *W = WorkQ[i];
965
13.3k
    if (IsNodeToSelect(W))
966
202
      Nodes.push_back(W);
967
31.6k
    for (unsigned j = 0, f = W->getNumOperands(); j != f; 
++j18.3k
)
968
18.3k
      WorkQ.insert(W->getOperand(j).getNode());
969
13.3k
  }
970
1.02k
971
1.02k
  for (SDNode *L : Nodes)
972
202
    ISel.Select(L);
973
1.02k
974
1.02k
  return !Nodes.empty();
975
1.02k
}
976
977
1.02k
void HvxSelector::materialize(const ResultStack &Results) {
978
1.02k
  DEBUG_WITH_TYPE("isel", {
979
1.02k
    dbgs() << "Materializing\n";
980
1.02k
    Results.print(dbgs(), DAG);
981
1.02k
  });
982
1.02k
  if (Results.empty())
983
0
    return;
984
1.02k
  const SDLoc &dl(Results.InpNode);
985
1.02k
  std::vector<SDValue> Output;
986
1.02k
987
7.20k
  for (unsigned I = 0, E = Results.size(); I != E; 
++I6.17k
) {
988
6.17k
    const NodeTemplate &Node = Results[I];
989
6.17k
    std::vector<SDValue> Ops;
990
11.9k
    for (const OpRef &R : Node.Ops) {
991
11.9k
      assert(R.isValid());
992
11.9k
      if (R.isValue()) {
993
5.89k
        Ops.push_back(R.OpV);
994
5.89k
        continue;
995
5.89k
      }
996
6.06k
      if (R.OpN & OpRef::Undef) {
997
24
        MVT::SimpleValueType SVT = MVT::SimpleValueType(R.OpN & OpRef::Index);
998
24
        Ops.push_back(ISel.selectUndef(dl, MVT(SVT)));
999
24
        continue;
1000
24
      }
1001
6.04k
      // R is an index of a result.
1002
6.04k
      unsigned Part = R.OpN & OpRef::Whole;
1003
6.04k
      int Idx = SignExtend32(R.OpN & OpRef::Index, OpRef::IndexBits);
1004
6.04k
      if (Idx < 0)
1005
581
        Idx += I;
1006
6.04k
      assert(Idx >= 0 && unsigned(Idx) < Output.size());
1007
6.04k
      SDValue Op = Output[Idx];
1008
6.04k
      MVT OpTy = Op.getValueType().getSimpleVT();
1009
6.04k
      if (Part != OpRef::Whole) {
1010
2.78k
        assert(Part == OpRef::LoHalf || Part == OpRef::HiHalf);
1011
2.78k
        MVT HalfTy = MVT::getVectorVT(OpTy.getVectorElementType(),
1012
2.78k
                                      OpTy.getVectorNumElements()/2);
1013
2.78k
        unsigned Sub = (Part == OpRef::LoHalf) ? 
Hexagon::vsub_lo1.39k
1014
2.78k
                                               : 
Hexagon::vsub_hi1.38k
;
1015
2.78k
        Op = DAG.getTargetExtractSubreg(Sub, dl, HalfTy, Op);
1016
2.78k
      }
1017
6.04k
      Ops.push_back(Op);
1018
6.04k
    } // for (Node : Results)
1019
6.17k
1020
6.17k
    assert(Node.Ty != MVT::Other);
1021
6.17k
    SDNode *ResN = (Node.Opc == TargetOpcode::COPY)
1022
6.17k
                      ? 
Ops.front().getNode()3.08k
1023
6.17k
                      : 
DAG.getMachineNode(Node.Opc, dl, Node.Ty, Ops)3.08k
;
1024
6.17k
    Output.push_back(SDValue(ResN, 0));
1025
6.17k
  }
1026
1.02k
1027
1.02k
  SDNode *OutN = Output.back().getNode();
1028
1.02k
  SDNode *InpN = Results.InpNode;
1029
1.02k
  DEBUG_WITH_TYPE("isel", {
1030
1.02k
    dbgs() << "Generated node:\n";
1031
1.02k
    OutN->dumpr(&DAG);
1032
1.02k
  });
1033
1.02k
1034
1.02k
  ISel.ReplaceNode(InpN, OutN);
1035
1.02k
  selectVectorConstants(OutN);
1036
1.02k
  DAG.RemoveDeadNodes();
1037
1.02k
}
1038
1039
895
OpRef HvxSelector::concat(OpRef Lo, OpRef Hi, ResultStack &Results) {
1040
895
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1041
895
  const SDLoc &dl(Results.InpNode);
1042
895
  Results.push(TargetOpcode::REG_SEQUENCE, getPairVT(MVT::i8), {
1043
895
    DAG.getTargetConstant(Hexagon::HvxWRRegClassID, dl, MVT::i32),
1044
895
    Lo, DAG.getTargetConstant(Hexagon::vsub_lo, dl, MVT::i32),
1045
895
    Hi, DAG.getTargetConstant(Hexagon::vsub_hi, dl, MVT::i32),
1046
895
  });
1047
895
  return OpRef::res(Results.top());
1048
895
}
1049
1050
// Va, Vb are single vectors, SM can be arbitrarily long.
1051
OpRef HvxSelector::packs(ShuffleMask SM, OpRef Va, OpRef Vb,
1052
                         ResultStack &Results, MutableArrayRef<int> NewMask,
1053
1.06k
                         unsigned Options) {
1054
1.06k
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1055
1.06k
  if (!Va.isValid() || !Vb.isValid())
1056
0
    return OpRef::fail();
1057
1.06k
1058
1.06k
  int VecLen = SM.Mask.size();
1059
1.06k
  MVT Ty = getSingleVT(MVT::i8);
1060
1.06k
1061
1.06k
  auto IsExtSubvector = [] (ShuffleMask M) {
1062
527
    assert(M.MinSrc >= 0 && M.MaxSrc >= 0);
1063
73.0k
    for (int I = 0, E = M.Mask.size(); I != E; 
++I72.5k
) {
1064
72.5k
      if (M.Mask[I] >= 0 && 
M.Mask[I]-I != M.MinSrc36.6k
)
1065
34
        return false;
1066
72.5k
    }
1067
527
    
return true493
;
1068
527
  };
1069
1.06k
1070
1.06k
  if (SM.MaxSrc - SM.MinSrc < int(HwLen)) {
1071
556
    if (SM.MinSrc == 0 || 
SM.MinSrc == int(HwLen)533
||
!IsExtSubvector(SM)527
) {
1072
63
      // If the mask picks elements from only one of the operands, return
1073
63
      // that operand, and update the mask to use index 0 to refer to the
1074
63
      // first element of that operand.
1075
63
      // If the mask extracts a subvector, it will be handled below, so
1076
63
      // skip it here.
1077
63
      if (SM.MaxSrc < int(HwLen)) {
1078
57
        memcpy(NewMask.data(), SM.Mask.data(), sizeof(int)*VecLen);
1079
57
        return Va;
1080
57
      }
1081
6
      if (SM.MinSrc >= int(HwLen)) {
1082
390
        for (int I = 0; I != VecLen; 
++I384
) {
1083
384
          int M = SM.Mask[I];
1084
384
          if (M != -1)
1085
384
            M -= HwLen;
1086
384
          NewMask[I] = M;
1087
384
        }
1088
6
        return Vb;
1089
6
      }
1090
493
    }
1091
493
    int MinSrc = SM.MinSrc;
1092
493
    if (SM.MaxSrc < int(HwLen)) {
1093
205
      Vb = Va;
1094
288
    } else if (SM.MinSrc > int(HwLen)) {
1095
1
      Va = Vb;
1096
1
      MinSrc = SM.MinSrc - HwLen;
1097
1
    }
1098
493
    const SDLoc &dl(Results.InpNode);
1099
493
    if (isUInt<3>(MinSrc) || 
isUInt<3>(HwLen-MinSrc)447
) {
1100
74
      bool IsRight = isUInt<3>(MinSrc); // Right align.
1101
74
      SDValue S = DAG.getTargetConstant(IsRight ? 
MinSrc46
:
HwLen-MinSrc28
,
1102
74
                                        dl, MVT::i32);
1103
74
      unsigned Opc = IsRight ? 
Hexagon::V6_valignbi46
1104
74
                             : 
Hexagon::V6_vlalignbi28
;
1105
74
      Results.push(Opc, Ty, {Vb, Va, S});
1106
419
    } else {
1107
419
      SDValue S = DAG.getTargetConstant(MinSrc, dl, MVT::i32);
1108
419
      Results.push(Hexagon::A2_tfrsi, MVT::i32, {S});
1109
419
      unsigned Top = Results.top();
1110
419
      Results.push(Hexagon::V6_valignb, Ty, {Vb, Va, OpRef::res(Top)});
1111
419
    }
1112
72.9k
    for (int I = 0; I != VecLen; 
++I72.4k
) {
1113
72.4k
      int M = SM.Mask[I];
1114
72.4k
      if (M != -1)
1115
36.5k
        M -= SM.MinSrc;
1116
72.4k
      NewMask[I] = M;
1117
72.4k
    }
1118
493
    return OpRef::res(Results.top());
1119
493
  }
1120
506
1121
506
  if (Options & PackMux) {
1122
0
    // If elements picked from Va and Vb have all different (source) indexes
1123
0
    // (relative to the start of the argument), do a mux, and update the mask.
1124
0
    BitVector Picked(HwLen);
1125
0
    SmallVector<uint8_t,128> MuxBytes(HwLen);
1126
0
    bool CanMux = true;
1127
0
    for (int I = 0; I != VecLen; ++I) {
1128
0
      int M = SM.Mask[I];
1129
0
      if (M == -1)
1130
0
        continue;
1131
0
      if (M >= int(HwLen))
1132
0
        M -= HwLen;
1133
0
      else
1134
0
        MuxBytes[M] = 0xFF;
1135
0
      if (Picked[M]) {
1136
0
        CanMux = false;
1137
0
        break;
1138
0
      }
1139
0
      NewMask[I] = M;
1140
0
    }
1141
0
    if (CanMux)
1142
0
      return vmuxs(MuxBytes, Va, Vb, Results);
1143
506
  }
1144
506
1145
506
  return OpRef::fail();
1146
506
}
1147
1148
OpRef HvxSelector::packp(ShuffleMask SM, OpRef Va, OpRef Vb,
1149
655
                         ResultStack &Results, MutableArrayRef<int> NewMask) {
1150
655
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1151
655
  unsigned HalfMask = 0;
1152
655
  unsigned LogHw = Log2_32(HwLen);
1153
136k
  for (int M : SM.Mask) {
1154
136k
    if (M == -1)
1155
22.0k
      continue;
1156
114k
    HalfMask |= (1u << (M >> LogHw));
1157
114k
  }
1158
655
1159
655
  if (HalfMask == 0)
1160
0
    return OpRef::undef(getPairVT(MVT::i8));
1161
655
1162
655
  // If more than two halves are used, bail.
1163
655
  // TODO: be more aggressive here?
1164
655
  if (countPopulation(HalfMask) > 2)
1165
1
    return OpRef::fail();
1166
654
1167
654
  MVT HalfTy = getSingleVT(MVT::i8);
1168
654
1169
654
  OpRef Inp[2] = { Va, Vb };
1170
654
  OpRef Out[2] = { OpRef::undef(HalfTy), OpRef::undef(HalfTy) };
1171
654
1172
654
  uint8_t HalfIdx[4] = { 0xFF, 0xFF, 0xFF, 0xFF };
1173
654
  unsigned Idx = 0;
1174
3.27k
  for (unsigned I = 0; I != 4; 
++I2.61k
) {
1175
2.61k
    if ((HalfMask & (1u << I)) == 0)
1176
1.31k
      continue;
1177
1.30k
    assert(Idx < 2);
1178
1.30k
    OpRef Op = Inp[I/2];
1179
1.30k
    Out[Idx] = (I & 1) ? 
OpRef::hi(Op)652
:
OpRef::lo(Op)652
;
1180
1.30k
    HalfIdx[I] = Idx++;
1181
1.30k
  }
1182
654
1183
654
  int VecLen = SM.Mask.size();
1184
136k
  for (int I = 0; I != VecLen; 
++I136k
) {
1185
136k
    int M = SM.Mask[I];
1186
136k
    if (M >= 0) {
1187
114k
      uint8_t Idx = HalfIdx[M >> LogHw];
1188
114k
      assert(Idx == 0 || Idx == 1);
1189
114k
      M = (M & (HwLen-1)) + HwLen*Idx;
1190
114k
    }
1191
136k
    NewMask[I] = M;
1192
136k
  }
1193
654
1194
654
  return concat(Out[0], Out[1], Results);
1195
654
}
1196
1197
OpRef HvxSelector::vmuxs(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
1198
51
                         ResultStack &Results) {
1199
51
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1200
51
  MVT ByteTy = getSingleVT(MVT::i8);
1201
51
  MVT BoolTy = MVT::getVectorVT(MVT::i1, 8*HwLen); // XXX
1202
51
  const SDLoc &dl(Results.InpNode);
1203
51
  SDValue B = getVectorConstant(Bytes, dl);
1204
51
  Results.push(Hexagon::V6_vd0, ByteTy, {});
1205
51
  Results.push(Hexagon::V6_veqb, BoolTy, {OpRef(B), OpRef::res(-1)});
1206
51
  Results.push(Hexagon::V6_vmux, ByteTy, {OpRef::res(-1), Vb, Va});
1207
51
  return OpRef::res(Results.top());
1208
51
}
1209
1210
OpRef HvxSelector::vmuxp(ArrayRef<uint8_t> Bytes, OpRef Va, OpRef Vb,
1211
1
                         ResultStack &Results) {
1212
1
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1213
1
  size_t S = Bytes.size() / 2;
1214
1
  OpRef L = vmuxs(Bytes.take_front(S), OpRef::lo(Va), OpRef::lo(Vb), Results);
1215
1
  OpRef H = vmuxs(Bytes.drop_front(S), OpRef::hi(Va), OpRef::hi(Vb), Results);
1216
1
  return concat(L, H, Results);
1217
1
}
1218
1219
849
OpRef HvxSelector::shuffs1(ShuffleMask SM, OpRef Va, ResultStack &Results) {
1220
849
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1221
849
  unsigned VecLen = SM.Mask.size();
1222
849
  assert(HwLen == VecLen);
1223
849
  (void)VecLen;
1224
849
  assert(all_of(SM.Mask, [this](int M) { return M == -1 || M < int(HwLen); }));
1225
849
1226
849
  if (isIdentity(SM.Mask))
1227
709
    return Va;
1228
140
  if (isUndef(SM.Mask))
1229
0
    return OpRef::undef(getSingleVT(MVT::i8));
1230
140
1231
140
  OpRef P = perfect(SM, Va, Results);
1232
140
  if (P.isValid())
1233
10
    return P;
1234
130
  return butterfly(SM, Va, Results);
1235
130
}
1236
1237
OpRef HvxSelector::shuffs2(ShuffleMask SM, OpRef Va, OpRef Vb,
1238
460
                           ResultStack &Results) {
1239
460
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1240
460
  if (isUndef(SM.Mask))
1241
18
    return OpRef::undef(getSingleVT(MVT::i8));
1242
442
1243
442
  OpRef C = contracting(SM, Va, Vb, Results);
1244
442
  if (C.isValid())
1245
32
    return C;
1246
410
1247
410
  int VecLen = SM.Mask.size();
1248
410
  SmallVector<int,128> NewMask(VecLen);
1249
410
  OpRef P = packs(SM, Va, Vb, Results, NewMask);
1250
410
  if (P.isValid())
1251
361
    return shuffs1(ShuffleMask(NewMask), P, Results);
1252
49
1253
49
  SmallVector<int,128> MaskL(VecLen), MaskR(VecLen);
1254
49
  splitMask(SM.Mask, MaskL, MaskR);
1255
49
1256
49
  OpRef L = shuffs1(ShuffleMask(MaskL), Va, Results);
1257
49
  OpRef R = shuffs1(ShuffleMask(MaskR), Vb, Results);
1258
49
  if (!L.isValid() || !R.isValid())
1259
0
    return OpRef::fail();
1260
49
1261
49
  SmallVector<uint8_t,128> Bytes(VecLen);
1262
3.56k
  for (int I = 0; I != VecLen; 
++I3.52k
) {
1263
3.52k
    if (MaskL[I] != -1)
1264
1.63k
      Bytes[I] = 0xFF;
1265
3.52k
  }
1266
49
  return vmuxs(Bytes, L, R, Results);
1267
49
}
1268
1269
656
OpRef HvxSelector::shuffp1(ShuffleMask SM, OpRef Va, ResultStack &Results) {
1270
656
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1271
656
  int VecLen = SM.Mask.size();
1272
656
1273
656
  if (isIdentity(SM.Mask))
1274
4
    return Va;
1275
652
  if (isUndef(SM.Mask))
1276
0
    return OpRef::undef(getPairVT(MVT::i8));
1277
652
1278
652
  SmallVector<int,128> PackedMask(VecLen);
1279
652
  OpRef P = packs(SM, OpRef::lo(Va), OpRef::hi(Va), Results, PackedMask);
1280
652
  if (P.isValid()) {
1281
195
    ShuffleMask PM(PackedMask);
1282
195
    OpRef E = expanding(PM, P, Results);
1283
195
    if (E.isValid())
1284
0
      return E;
1285
195
1286
195
    OpRef L = shuffs1(PM.lo(), P, Results);
1287
195
    OpRef H = shuffs1(PM.hi(), P, Results);
1288
195
    if (L.isValid() && H.isValid())
1289
195
      return concat(L, H, Results);
1290
457
  }
1291
457
1292
457
  OpRef R = perfect(SM, Va, Results);
1293
457
  if (R.isValid())
1294
414
    return R;
1295
43
  // TODO commute the mask and try the opposite order of the halves.
1296
43
1297
43
  OpRef L = shuffs2(SM.lo(), OpRef::lo(Va), OpRef::hi(Va), Results);
1298
43
  OpRef H = shuffs2(SM.hi(), OpRef::lo(Va), OpRef::hi(Va), Results);
1299
43
  if (L.isValid() && H.isValid())
1300
43
    return concat(L, H, Results);
1301
0
1302
0
  return OpRef::fail();
1303
0
}
1304
1305
OpRef HvxSelector::shuffp2(ShuffleMask SM, OpRef Va, OpRef Vb,
1306
655
                           ResultStack &Results) {
1307
655
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1308
655
  if (isUndef(SM.Mask))
1309
0
    return OpRef::undef(getPairVT(MVT::i8));
1310
655
1311
655
  int VecLen = SM.Mask.size();
1312
655
  SmallVector<int,256> PackedMask(VecLen);
1313
655
  OpRef P = packp(SM, Va, Vb, Results, PackedMask);
1314
655
  if (P.isValid())
1315
654
    return shuffp1(ShuffleMask(PackedMask), P, Results);
1316
1
1317
1
  SmallVector<int,256> MaskL(VecLen), MaskR(VecLen);
1318
1
  splitMask(SM.Mask, MaskL, MaskR);
1319
1
1320
1
  OpRef L = shuffp1(ShuffleMask(MaskL), Va, Results);
1321
1
  OpRef R = shuffp1(ShuffleMask(MaskR), Vb, Results);
1322
1
  if (!L.isValid() || !R.isValid())
1323
0
    return OpRef::fail();
1324
1
1325
1
  // Mux the results.
1326
1
  SmallVector<uint8_t,256> Bytes(VecLen);
1327
257
  for (int I = 0; I != VecLen; 
++I256
) {
1328
256
    if (MaskL[I] != -1)
1329
254
      Bytes[I] = 0xFF;
1330
256
  }
1331
1
  return vmuxp(Bytes, L, R, Results);
1332
1
}
1333
1334
namespace {
1335
  struct Deleter : public SelectionDAG::DAGNodeDeletedListener {
1336
    template <typename T>
1337
    Deleter(SelectionDAG &D, T &C)
1338
0
      : SelectionDAG::DAGNodeDeletedListener(D, [&C] (SDNode *N, SDNode *E) {
1339
0
                                                  C.erase(N);
1340
0
                                                }) {}
Unexecuted instantiation: HexagonISelDAGToDAGHVX.cpp:(anonymous namespace)::Deleter::Deleter<llvm::DenseSet<llvm::SDNode*, llvm::DenseMapInfo<llvm::SDNode*> > >(llvm::SelectionDAG&, llvm::DenseSet<llvm::SDNode*, llvm::DenseMapInfo<llvm::SDNode*> >&)::'lambda'(llvm::SDNode*, llvm::SDNode*)::operator()(llvm::SDNode*, llvm::SDNode*) const
Unexecuted instantiation: HexagonISelDAGToDAGHVX.cpp:(anonymous namespace)::Deleter::Deleter<(anonymous namespace)::NullifyingVector<std::__1::vector<llvm::SDNode*, std::__1::allocator<llvm::SDNode*> > > >(llvm::SelectionDAG&, (anonymous namespace)::NullifyingVector<std::__1::vector<llvm::SDNode*, std::__1::allocator<llvm::SDNode*> > >&)::'lambda'(llvm::SDNode*, llvm::SDNode*)::operator()(llvm::SDNode*, llvm::SDNode*) const
Unexecuted instantiation: HexagonISelDAGToDAGHVX.cpp:(anonymous namespace)::Deleter::Deleter<llvm::DenseSet<llvm::SDNode*, llvm::DenseMapInfo<llvm::SDNode*> > >(llvm::SelectionDAG&, llvm::DenseSet<llvm::SDNode*, llvm::DenseMapInfo<llvm::SDNode*> >&)
Unexecuted instantiation: HexagonISelDAGToDAGHVX.cpp:(anonymous namespace)::Deleter::Deleter<(anonymous namespace)::NullifyingVector<std::__1::vector<llvm::SDNode*, std::__1::allocator<llvm::SDNode*> > > >(llvm::SelectionDAG&, (anonymous namespace)::NullifyingVector<std::__1::vector<llvm::SDNode*, std::__1::allocator<llvm::SDNode*> > >&)
1341
  };
1342
1343
  template <typename T>
1344
  struct NullifyingVector : public T {
1345
    DenseMap<SDNode*, SDNode**> Refs;
1346
0
    NullifyingVector(T &&V) : T(V) {
1347
0
      for (unsigned i = 0, e = T::size(); i != e; ++i) {
1348
0
        SDNode *&N = T::operator[](i);
1349
0
        Refs[N] = &N;
1350
0
      }
1351
0
    }
1352
0
    void erase(SDNode *N) {
1353
0
      auto F = Refs.find(N);
1354
0
      if (F != Refs.end())
1355
0
        *F->second = nullptr;
1356
0
    }
1357
  };
1358
}
1359
1360
bool HvxSelector::scalarizeShuffle(ArrayRef<int> Mask, const SDLoc &dl,
1361
                                   MVT ResTy, SDValue Va, SDValue Vb,
1362
0
                                   SDNode *N) {
1363
0
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1364
0
  MVT ElemTy = ResTy.getVectorElementType();
1365
0
  assert(ElemTy == MVT::i8);
1366
0
  unsigned VecLen = Mask.size();
1367
0
  bool HavePairs = (2*HwLen == VecLen);
1368
0
  MVT SingleTy = getSingleVT(MVT::i8);
1369
0
1370
0
  // The prior attempts to handle this shuffle may have left a bunch of
1371
0
  // dead nodes in the DAG (such as constants). These nodes will be added
1372
0
  // at the end of DAG's node list, which at that point had already been
1373
0
  // sorted topologically. In the main selection loop, the node list is
1374
0
  // traversed backwards from the root node, which means that any new
1375
0
  // nodes (from the end of the list) will not be visited.
1376
0
  // Scalarization will replace the shuffle node with the scalarized
1377
0
  // expression, and if that expression reused any if the leftoever (dead)
1378
0
  // nodes, these nodes would not be selected (since the "local" selection
1379
0
  // only visits nodes that are not in AllNodes).
1380
0
  // To avoid this issue, remove all dead nodes from the DAG now.
1381
0
  DAG.RemoveDeadNodes();
1382
0
  DenseSet<SDNode*> AllNodes;
1383
0
  for (SDNode &S : DAG.allnodes())
1384
0
    AllNodes.insert(&S);
1385
0
1386
0
  Deleter DUA(DAG, AllNodes);
1387
0
1388
0
  SmallVector<SDValue,128> Ops;
1389
0
  LLVMContext &Ctx = *DAG.getContext();
1390
0
  MVT LegalTy = Lower.getTypeToTransformTo(Ctx, ElemTy).getSimpleVT();
1391
0
  for (int I : Mask) {
1392
0
    if (I < 0) {
1393
0
      Ops.push_back(ISel.selectUndef(dl, LegalTy));
1394
0
      continue;
1395
0
    }
1396
0
    SDValue Vec;
1397
0
    unsigned M = I;
1398
0
    if (M < VecLen) {
1399
0
      Vec = Va;
1400
0
    } else {
1401
0
      Vec = Vb;
1402
0
      M -= VecLen;
1403
0
    }
1404
0
    if (HavePairs) {
1405
0
      if (M < HwLen) {
1406
0
        Vec = DAG.getTargetExtractSubreg(Hexagon::vsub_lo, dl, SingleTy, Vec);
1407
0
      } else {
1408
0
        Vec = DAG.getTargetExtractSubreg(Hexagon::vsub_hi, dl, SingleTy, Vec);
1409
0
        M -= HwLen;
1410
0
      }
1411
0
    }
1412
0
    SDValue Idx = DAG.getConstant(M, dl, MVT::i32);
1413
0
    SDValue Ex = DAG.getNode(ISD::EXTRACT_VECTOR_ELT, dl, LegalTy, {Vec, Idx});
1414
0
    SDValue L = Lower.LowerOperation(Ex, DAG);
1415
0
    assert(L.getNode());
1416
0
    Ops.push_back(L);
1417
0
  }
1418
0
1419
0
  SDValue LV;
1420
0
  if (2*HwLen == VecLen) {
1421
0
    SDValue B0 = DAG.getBuildVector(SingleTy, dl, {Ops.data(), HwLen});
1422
0
    SDValue L0 = Lower.LowerOperation(B0, DAG);
1423
0
    SDValue B1 = DAG.getBuildVector(SingleTy, dl, {Ops.data()+HwLen, HwLen});
1424
0
    SDValue L1 = Lower.LowerOperation(B1, DAG);
1425
0
    // XXX CONCAT_VECTORS is legal for HVX vectors. Legalizing (lowering)
1426
0
    // functions may expect to be called only for illegal operations, so
1427
0
    // make sure that they are not called for legal ones. Develop a better
1428
0
    // mechanism for dealing with this.
1429
0
    LV = DAG.getNode(ISD::CONCAT_VECTORS, dl, ResTy, {L0, L1});
1430
0
  } else {
1431
0
    SDValue BV = DAG.getBuildVector(ResTy, dl, Ops);
1432
0
    LV = Lower.LowerOperation(BV, DAG);
1433
0
  }
1434
0
1435
0
  assert(!N->use_empty());
1436
0
  ISel.ReplaceNode(N, LV.getNode());
1437
0
1438
0
  if (AllNodes.count(LV.getNode())) {
1439
0
    DAG.RemoveDeadNodes();
1440
0
    return true;
1441
0
  }
1442
0
1443
0
  // The lowered build-vector node will now need to be selected. It needs
1444
0
  // to be done here because this node and its submodes are not included
1445
0
  // in the main selection loop.
1446
0
  // Implement essentially the same topological ordering algorithm as is
1447
0
  // used in SelectionDAGISel.
1448
0
1449
0
  SetVector<SDNode*> SubNodes, TmpQ;
1450
0
  std::map<SDNode*,unsigned> NumOps;
1451
0
1452
0
  SubNodes.insert(LV.getNode());
1453
0
  for (unsigned I = 0; I != SubNodes.size(); ++I) {
1454
0
    unsigned OpN = 0;
1455
0
    SDNode *S = SubNodes[I];
1456
0
    for (SDValue Op : S->ops()) {
1457
0
      if (AllNodes.count(Op.getNode()))
1458
0
        continue;
1459
0
      SubNodes.insert(Op.getNode());
1460
0
      ++OpN;
1461
0
    }
1462
0
    NumOps.insert({S, OpN});
1463
0
    if (OpN == 0)
1464
0
      TmpQ.insert(S);
1465
0
  }
1466
0
1467
0
  for (unsigned I = 0; I != TmpQ.size(); ++I) {
1468
0
    SDNode *S = TmpQ[I];
1469
0
    for (SDNode *U : S->uses()) {
1470
0
      if (!SubNodes.count(U))
1471
0
        continue;
1472
0
      auto F = NumOps.find(U);
1473
0
      assert(F != NumOps.end());
1474
0
      assert(F->second > 0);
1475
0
      if (!--F->second)
1476
0
        TmpQ.insert(F->first);
1477
0
    }
1478
0
  }
1479
0
  assert(SubNodes.size() == TmpQ.size());
1480
0
  NullifyingVector<decltype(TmpQ)::vector_type> Queue(TmpQ.takeVector());
1481
0
1482
0
  Deleter DUQ(DAG, Queue);
1483
0
  for (SDNode *S : reverse(Queue))
1484
0
    if (S != nullptr)
1485
0
      ISel.Select(S);
1486
0
1487
0
  DAG.RemoveDeadNodes();
1488
0
  return true;
1489
0
}
1490
1491
OpRef HvxSelector::contracting(ShuffleMask SM, OpRef Va, OpRef Vb,
1492
442
                               ResultStack &Results) {
1493
442
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1494
442
  if (!Va.isValid() || !Vb.isValid())
1495
0
    return OpRef::fail();
1496
442
1497
442
  // Contracting shuffles, i.e. instructions that always discard some bytes
1498
442
  // from the operand vectors.
1499
442
  //
1500
442
  // V6_vshuff{e,o}b
1501
442
  // V6_vdealb4w
1502
442
  // V6_vpack{e,o}{b,h}
1503
442
1504
442
  int VecLen = SM.Mask.size();
1505
442
  std::pair<int,unsigned> Strip = findStrip(SM.Mask, 1, VecLen);
1506
442
  MVT ResTy = getSingleVT(MVT::i8);
1507
442
1508
442
  // The following shuffles only work for bytes and halfwords. This requires
1509
442
  // the strip length to be 1 or 2.
1510
442
  if (Strip.second != 1 && 
Strip.second != 2344
)
1511
324
    return OpRef::fail();
1512
118
1513
118
  // The patterns for the shuffles, in terms of the starting offsets of the
1514
118
  // consecutive strips (L = length of the strip, N = VecLen):
1515
118
  //
1516
118
  // vpacke:    0, 2L, 4L ... N+0, N+2L, N+4L ...      L = 1 or 2
1517
118
  // vpacko:    L, 3L, 5L ... N+L, N+3L, N+5L ...      L = 1 or 2
1518
118
  //
1519
118
  // vshuffe:   0, N+0, 2L, N+2L, 4L ...               L = 1 or 2
1520
118
  // vshuffo:   L, N+L, 3L, N+3L, 5L ...               L = 1 or 2
1521
118
  //
1522
118
  // vdealb4w:  0, 4, 8 ... 2, 6, 10 ... N+0, N+4, N+8 ... N+2, N+6, N+10 ...
1523
118
1524
118
  // The value of the element in the mask following the strip will decide
1525
118
  // what kind of a shuffle this can be.
1526
118
  int NextInMask = SM.Mask[Strip.second];
1527
118
1528
118
  // Check if NextInMask could be 2L, 3L or 4, i.e. if it could be a mask
1529
118
  // for vpack or vdealb4w. VecLen > 4, so NextInMask for vdealb4w would
1530
118
  // satisfy this.
1531
118
  if (NextInMask < VecLen) {
1532
78
    // vpack{e,o} or vdealb4w
1533
78
    if (Strip.first == 0 && 
Strip.second == 123
&&
NextInMask == 415
) {
1534
3
      int N = VecLen;
1535
3
      // Check if this is vdealb4w (L=1).
1536
59
      for (int I = 0; I != N/4; 
++I56
)
1537
57
        if (SM.Mask[I] != 4*I)
1538
1
          return OpRef::fail();
1539
50
      
for (int I = 0; 2
I != N/4;
++I48
)
1540
48
        if (SM.Mask[I+N/4] != 2 + 4*I)
1541
0
          return OpRef::fail();
1542
50
      
for (int I = 0; 2
I != N/4;
++I48
)
1543
48
        if (SM.Mask[I+N/2] != N + 4*I)
1544
0
          return OpRef::fail();
1545
50
      
for (int I = 0; 2
I != N/4;
++I48
)
1546
48
        if (SM.Mask[I+3*N/4] != N+2 + 4*I)
1547
0
          return OpRef::fail();
1548
2
      // Matched mask for vdealb4w.
1549
2
      Results.push(Hexagon::V6_vdealb4w, ResTy, {Vb, Va});
1550
2
      return OpRef::res(Results.top());
1551
75
    }
1552
75
1553
75
    // Check if this is vpack{e,o}.
1554
75
    int N = VecLen;
1555
75
    int L = Strip.second;
1556
75
    // Check if the first strip starts at 0 or at L.
1557
75
    if (Strip.first != 0 && 
Strip.first != L55
)
1558
44
      return OpRef::fail();
1559
31
    // Examine the rest of the mask.
1560
1.36k
    
for (int I = L; 31
I < N;
I += L1.33k
) {
1561
1.34k
      auto S = findStrip(SM.Mask.drop_front(I), 1, N-I);
1562
1.34k
      // Check whether the mask element at the beginning of each strip
1563
1.34k
      // increases by 2L each time.
1564
1.34k
      if (S.first - Strip.first != 2*I)
1565
11
        return OpRef::fail();
1566
1.33k
      // Check whether each strip is of the same length.
1567
1.33k
      if (S.second != unsigned(L))
1568
0
        return OpRef::fail();
1569
1.33k
    }
1570
31
1571
31
    // Strip.first == 0  =>  vpacke
1572
31
    // Strip.first == L  =>  vpacko
1573
31
    assert(Strip.first == 0 || Strip.first == L);
1574
20
    using namespace Hexagon;
1575
20
    NodeTemplate Res;
1576
20
    Res.Opc = Strip.second == 1 // Number of bytes.
1577
20
                  ? 
(Strip.first == 0 12
?
V6_vpackeb6
:
V6_vpackob6
)
1578
20
                  : 
(Strip.first == 0 8
?
V6_vpackeh4
:
V6_vpackoh4
);
1579
20
    Res.Ty = ResTy;
1580
20
    Res.Ops = { Vb, Va };
1581
20
    Results.push(Res);
1582
20
    return OpRef::res(Results.top());
1583
40
  }
1584
40
1585
40
  // Check if this is vshuff{e,o}.
1586
40
  int N = VecLen;
1587
40
  int L = Strip.second;
1588
40
  std::pair<int,unsigned> PrevS = Strip;
1589
40
  bool Flip = false;
1590
806
  for (int I = L; I < N; 
I += L766
) {
1591
796
    auto S = findStrip(SM.Mask.drop_front(I), 1, N-I);
1592
796
    if (S.second != PrevS.second)
1593
4
      return OpRef::fail();
1594
792
    int Diff = Flip ? 
PrevS.first - S.first + 2*L382
1595
792
                    : 
S.first - PrevS.first410
;
1596
792
    if (Diff != N)
1597
26
      return OpRef::fail();
1598
766
    Flip ^= true;
1599
766
    PrevS = S;
1600
766
  }
1601
40
  // Strip.first == 0  =>  vshuffe
1602
40
  // Strip.first == L  =>  vshuffo
1603
40
  assert(Strip.first == 0 || Strip.first == L);
1604
10
  using namespace Hexagon;
1605
10
  NodeTemplate Res;
1606
10
  Res.Opc = Strip.second == 1 // Number of bytes.
1607
10
                ? 
(Strip.first == 0 6
?
V6_vshuffeb4
:
V6_vshuffob2
)
1608
10
                : 
(Strip.first == 0 4
?
V6_vshufeh2
:
V6_vshufoh2
);
1609
10
  Res.Ty = ResTy;
1610
10
  Res.Ops = { Vb, Va };
1611
10
  Results.push(Res);
1612
10
  return OpRef::res(Results.top());
1613
40
}
1614
1615
195
OpRef HvxSelector::expanding(ShuffleMask SM, OpRef Va, ResultStack &Results) {
1616
195
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1617
195
  // Expanding shuffles (using all elements and inserting into larger vector):
1618
195
  //
1619
195
  // V6_vunpacku{b,h} [*]
1620
195
  //
1621
195
  // [*] Only if the upper elements (filled with 0s) are "don't care" in Mask.
1622
195
  //
1623
195
  // Note: V6_vunpacko{b,h} are or-ing the high byte/half in the result, so
1624
195
  // they are not shuffles.
1625
195
  //
1626
195
  // The argument is a single vector.
1627
195
1628
195
  int VecLen = SM.Mask.size();
1629
195
  assert(2*HwLen == unsigned(VecLen) && "Expecting vector-pair type");
1630
195
1631
195
  std::pair<int,unsigned> Strip = findStrip(SM.Mask, 1, VecLen);
1632
195
1633
195
  // The patterns for the unpacks, in terms of the starting offsets of the
1634
195
  // consecutive strips (L = length of the strip, N = VecLen):
1635
195
  //
1636
195
  // vunpacku:  0, -1, L, -1, 2L, -1 ...
1637
195
1638
195
  if (Strip.first != 0)
1639
1
    return OpRef::fail();
1640
194
1641
194
  // The vunpackus only handle byte and half-word.
1642
194
  if (Strip.second != 1 && Strip.second != 2)
1643
194
    return OpRef::fail();
1644
0
1645
0
  int N = VecLen;
1646
0
  int L = Strip.second;
1647
0
1648
0
  // First, check the non-ignored strips.
1649
0
  for (int I = 2*L; I < 2*N; I += 2*L) {
1650
0
    auto S = findStrip(SM.Mask.drop_front(I), 1, N-I);
1651
0
    if (S.second != unsigned(L))
1652
0
      return OpRef::fail();
1653
0
    if (2*S.first != I)
1654
0
      return OpRef::fail();
1655
0
  }
1656
0
  // Check the -1s.
1657
0
  for (int I = L; I < 2*N; I += 2*L) {
1658
0
    auto S = findStrip(SM.Mask.drop_front(I), 0, N-I);
1659
0
    if (S.first != -1 || S.second != unsigned(L))
1660
0
      return OpRef::fail();
1661
0
  }
1662
0
1663
0
  unsigned Opc = Strip.second == 1 ? Hexagon::V6_vunpackub
1664
0
                                   : Hexagon::V6_vunpackuh;
1665
0
  Results.push(Opc, getPairVT(MVT::i8), {Va});
1666
0
  return OpRef::res(Results.top());
1667
0
}
1668
1669
597
OpRef HvxSelector::perfect(ShuffleMask SM, OpRef Va, ResultStack &Results) {
1670
597
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1671
597
  // V6_vdeal{b,h}
1672
597
  // V6_vshuff{b,h}
1673
597
1674
597
  // V6_vshufoe{b,h}  those are quivalent to vshuffvdd(..,{1,2})
1675
597
  // V6_vshuffvdd (V6_vshuff)
1676
597
  // V6_dealvdd (V6_vdeal)
1677
597
1678
597
  int VecLen = SM.Mask.size();
1679
597
  assert(isPowerOf2_32(VecLen) && Log2_32(VecLen) <= 8);
1680
597
  unsigned LogLen = Log2_32(VecLen);
1681
597
  unsigned HwLog = Log2_32(HwLen);
1682
597
  // The result length must be the same as the length of a single vector,
1683
597
  // or a vector pair.
1684
597
  assert(LogLen == HwLog || LogLen == HwLog+1);
1685
597
  bool Extend = (LogLen == HwLog);
1686
597
1687
597
  if (!isPermutation(SM.Mask))
1688
164
    return OpRef::fail();
1689
433
1690
433
  SmallVector<unsigned,8> Perm(LogLen);
1691
433
1692
433
  // Check if this could be a perfect shuffle, or a combination of perfect
1693
433
  // shuffles.
1694
433
  //
1695
433
  // Consider this permutation (using hex digits to make the ASCII diagrams
1696
433
  // easier to read):
1697
433
  //   { 0, 8, 1, 9, 2, A, 3, B, 4, C, 5, D, 6, E, 7, F }.
1698
433
  // This is a "deal" operation: divide the input into two halves, and
1699
433
  // create the output by picking elements by alternating between these two
1700
433
  // halves:
1701
433
  //   0 1 2 3 4 5 6 7    -->    0 8 1 9 2 A 3 B 4 C 5 D 6 E 7 F  [*]
1702
433
  //   8 9 A B C D E F
1703
433
  //
1704
433
  // Aside from a few special explicit cases (V6_vdealb, etc.), HVX provides
1705
433
  // a somwehat different mechanism that could be used to perform shuffle/
1706
433
  // deal operations: a 2x2 transpose.
1707
433
  // Consider the halves of inputs again, they can be interpreted as a 2x8
1708
433
  // matrix. A 2x8 matrix can be looked at four 2x2 matrices concatenated
1709
433
  // together. Now, when considering 2 elements at a time, it will be a 2x4
1710
433
  // matrix (with elements 01, 23, 45, etc.), or two 2x2 matrices:
1711
433
  //   01 23  45 67
1712
433
  //   89 AB  CD EF
1713
433
  // With groups of 4, this will become a single 2x2 matrix, and so on.
1714
433
  //
1715
433
  // The 2x2 transpose instruction works by transposing each of the 2x2
1716
433
  // matrices (or "sub-matrices"), given a specific group size. For example,
1717
433
  // if the group size is 1 (i.e. each element is its own group), there
1718
433
  // will be four transposes of the four 2x2 matrices that form the 2x8.
1719
433
  // For example, with the inputs as above, the result will be:
1720
433
  //   0 8  2 A  4 C  6 E
1721
433
  //   1 9  3 B  5 D  7 F
1722
433
  // Now, this result can be tranposed again, but with the group size of 2:
1723
433
  //   08 19  4C 5D
1724
433
  //   2A 3B  6E 7F
1725
433
  // If we then transpose that result, but with the group size of 4, we get:
1726
433
  //   0819 2A3B
1727
433
  //   4C5D 6E7F
1728
433
  // If we concatenate these two rows, it will be
1729
433
  //   0 8 1 9 2 A 3 B 4 C 5 D 6 E 7 F
1730
433
  // which is the same as the "deal" [*] above.
1731
433
  //
1732
433
  // In general, a "deal" of individual elements is a series of 2x2 transposes,
1733
433
  // with changing group size. HVX has two instructions:
1734
433
  //   Vdd = V6_vdealvdd Vu, Vv, Rt
1735
433
  //   Vdd = V6_shufvdd  Vu, Vv, Rt
1736
433
  // that perform exactly that. The register Rt controls which transposes are
1737
433
  // going to happen: a bit at position n (counting from 0) indicates that a
1738
433
  // transpose with a group size of 2^n will take place. If multiple bits are
1739
433
  // set, multiple transposes will happen: vdealvdd will perform them starting
1740
433
  // with the largest group size, vshuffvdd will do them in the reverse order.
1741
433
  //
1742
433
  // The main observation is that each 2x2 transpose corresponds to swapping
1743
433
  // columns of bits in the binary representation of the values.
1744
433
  //
1745
433
  // The numbers {3,2,1,0} and the log2 of the number of contiguous 1 bits
1746
433
  // in a given column. The * denote the columns that will be swapped.
1747
433
  // The transpose with the group size 2^n corresponds to swapping columns
1748
433
  // 3 (the highest log) and log2(n):
1749
433
  //
1750
433
  //     3 2 1 0         0 2 1 3         0 2 3 1
1751
433
  //     *     *             * *           * *
1752
433
  //  0  0 0 0 0      0  0 0 0 0      0  0 0 0 0      0  0 0 0 0
1753
433
  //  1  0 0 0 1      8  1 0 0 0      8  1 0 0 0      8  1 0 0 0
1754
433
  //  2  0 0 1 0      2  0 0 1 0      1  0 0 0 1      1  0 0 0 1
1755
433
  //  3  0 0 1 1      A  1 0 1 0      9  1 0 0 1      9  1 0 0 1
1756
433
  //  4  0 1 0 0      4  0 1 0 0      4  0 1 0 0      2  0 0 1 0
1757
433
  //  5  0 1 0 1      C  1 1 0 0      C  1 1 0 0      A  1 0 1 0
1758
433
  //  6  0 1 1 0      6  0 1 1 0      5  0 1 0 1      3  0 0 1 1
1759
433
  //  7  0 1 1 1      E  1 1 1 0      D  1 1 0 1      B  1 0 1 1
1760
433
  //  8  1 0 0 0      1  0 0 0 1      2  0 0 1 0      4  0 1 0 0
1761
433
  //  9  1 0 0 1      9  1 0 0 1      A  1 0 1 0      C  1 1 0 0
1762
433
  //  A  1 0 1 0      3  0 0 1 1      3  0 0 1 1      5  0 1 0 1
1763
433
  //  B  1 0 1 1      B  1 0 1 1      B  1 0 1 1      D  1 1 0 1
1764
433
  //  C  1 1 0 0      5  0 1 0 1      6  0 1 1 0      6  0 1 1 0
1765
433
  //  D  1 1 0 1      D  1 1 0 1      E  1 1 1 0      E  1 1 1 0
1766
433
  //  E  1 1 1 0      7  0 1 1 1      7  0 1 1 1      7  0 1 1 1
1767
433
  //  F  1 1 1 1      F  1 1 1 1      F  1 1 1 1      F  1 1 1 1
1768
433
1769
88.3k
  auto XorPow2 = [] (ArrayRef<int> Mask, unsigned Num) {
1770
88.3k
    unsigned X = Mask[0] ^ Mask[Num/2];
1771
88.3k
    // Check that the first half has the X's bits clear.
1772
88.3k
    if ((Mask[0] & X) != 0)
1773
9
      return 0u;
1774
345k
    
for (unsigned I = 1; 88.3k
I != Num/2;
++I257k
) {
1775
257k
      if (unsigned(Mask[I] ^ Mask[I+Num/2]) != X)
1776
0
        return 0u;
1777
257k
      if ((Mask[I] & X) != 0)
1778
0
        return 0u;
1779
257k
    }
1780
88.3k
    return X;
1781
88.3k
  };
1782
433
1783
433
  // Create a vector of log2's for each column: Perm[i] corresponds to
1784
433
  // the i-th bit (lsb is 0).
1785
433
  assert(VecLen > 2);
1786
3.67k
  for (unsigned I = VecLen; I >= 2; 
I >>= 13.24k
) {
1787
3.24k
    // Examine the initial segment of Mask of size I.
1788
3.24k
    unsigned X = XorPow2(SM.Mask, I);
1789
3.24k
    if (!isPowerOf2_32(X))
1790
9
      return OpRef::fail();
1791
3.24k
    // Check the other segments of Mask.
1792
88.3k
    
for (int J = I; 3.24k
J < VecLen;
J += I85.1k
) {
1793
85.1k
      if (XorPow2(SM.Mask.slice(J, I), I) != X)
1794
0
        return OpRef::fail();
1795
85.1k
    }
1796
3.24k
    Perm[Log2_32(X)] = Log2_32(I)-1;
1797
3.24k
  }
1798
433
1799
433
  // Once we have Perm, represent it as cycles. Denote the maximum log2
1800
433
  // (equal to log2(VecLen)-1) as M. The cycle containing M can then be
1801
433
  // written as (M a1 a2 a3 ... an). That cycle can be broken up into
1802
433
  // simple swaps as (M a1)(M a2)(M a3)...(M an), with the composition
1803
433
  // order being from left to right. Any (contiguous) segment where the
1804
433
  // values ai, ai+1...aj are either all increasing or all decreasing,
1805
433
  // can be implemented via a single vshuffvdd/vdealvdd respectively.
1806
433
  //
1807
433
  // If there is a cycle (a1 a2 ... an) that does not involve M, it can
1808
433
  // be written as (M an)(a1 a2 ... an)(M a1). The first two cycles can
1809
433
  // then be folded to get (M a1 a2 ... an)(M a1), and the above procedure
1810
433
  // can be used to generate a sequence of vshuffvdd/vdealvdd.
1811
433
  //
1812
433
  // Example:
1813
433
  // Assume M = 4 and consider a permutation (0 1)(2 3). It can be written
1814
433
  // as (4 0 1)(4 0) composed with (4 2 3)(4 2), or simply
1815
433
  //   (4 0 1)(4 0)(4 2 3)(4 2).
1816
433
  // It can then be expanded into swaps as
1817
433
  //   (4 0)(4 1)(4 0)(4 2)(4 3)(4 2),
1818
433
  // and broken up into "increasing" segments as
1819
433
  //   [(4 0)(4 1)] [(4 0)(4 2)(4 3)] [(4 2)].
1820
433
  // This is equivalent to
1821
433
  //   (4 0 1)(4 0 2 3)(4 2),
1822
433
  // which can be implemented as 3 vshufvdd instructions.
1823
433
1824
433
  using CycleType = SmallVector<unsigned,8>;
1825
424
  std::set<CycleType> Cycles;
1826
424
  std::set<unsigned> All;
1827
424
1828
424
  for (unsigned I : Perm)
1829
3.23k
    All.insert(I);
1830
424
1831
424
  // If the cycle contains LogLen-1, move it to the front of the cycle.
1832
424
  // Otherwise, return the cycle unchanged.
1833
444
  auto canonicalize = [LogLen](const CycleType &C) -> CycleType {
1834
444
    unsigned LogPos, N = C.size();
1835
1.44k
    for (LogPos = 0; LogPos != N; 
++LogPos998
)
1836
1.41k
      if (C[LogPos] == LogLen-1)
1837
420
        break;
1838
444
    if (LogPos == N)
1839
24
      return C;
1840
420
1841
420
    CycleType NewC(C.begin()+LogPos, C.end());
1842
420
    NewC.append(C.begin(), C.begin()+LogPos);
1843
420
    return NewC;
1844
420
  };
1845
424
1846
424
  auto pfs = [](const std::set<CycleType> &Cs, unsigned Len) {
1847
10
    // Ordering: shuff: 5 0 1 2 3 4, deal: 5 4 3 2 1 0 (for Log=6),
1848
10
    // for bytes zero is included, for halfwords is not.
1849
10
    if (Cs.size() != 1)
1850
0
      return 0u;
1851
10
    const CycleType &C = *Cs.begin();
1852
10
    if (C[0] != Len-1)
1853
0
      return 0u;
1854
10
    int D = Len - C.size();
1855
10
    if (D != 0 && 
D != 16
)
1856
2
      return 0u;
1857
8
1858
8
    bool IsDeal = true, IsShuff = true;
1859
48
    for (unsigned I = 1; I != Len-D; 
++I40
) {
1860
40
      if (C[I] != Len-1-I)
1861
18
        IsDeal = false;
1862
40
      if (C[I] != I-(1-D))  // I-1, I
1863
18
        IsShuff = false;
1864
40
    }
1865
8
    // At most one, IsDeal or IsShuff, can be non-zero.
1866
8
    assert(!(IsDeal || IsShuff) || IsDeal != IsShuff);
1867
8
    static unsigned Deals[] = { Hexagon::V6_vdealb, Hexagon::V6_vdealh };
1868
8
    static unsigned Shufs[] = { Hexagon::V6_vshuffb, Hexagon::V6_vshuffh };
1869
8
    return IsDeal ? 
Deals[D]4
:
(IsShuff 4
?
Shufs[D]4
:
00
);
1870
8
  };
1871
424
1872
2.17k
  while (!All.empty()) {
1873
1.74k
    unsigned A = *All.begin();
1874
1.74k
    All.erase(A);
1875
1.74k
    CycleType C;
1876
1.74k
    C.push_back(A);
1877
3.23k
    for (unsigned B = Perm[A]; B != A; 
B = Perm[B]1.48k
) {
1878
1.48k
      C.push_back(B);
1879
1.48k
      All.erase(B);
1880
1.48k
    }
1881
1.74k
    if (C.size() <= 1)
1882
1.30k
      continue;
1883
444
    Cycles.insert(canonicalize(C));
1884
444
  }
1885
424
1886
424
  MVT SingleTy = getSingleVT(MVT::i8);
1887
424
  MVT PairTy = getPairVT(MVT::i8);
1888
424
1889
424
  // Recognize patterns for V6_vdeal{b,h} and V6_vshuff{b,h}.
1890
424
  if (unsigned(VecLen) == HwLen) {
1891
10
    if (unsigned SingleOpc = pfs(Cycles, LogLen)) {
1892
8
      Results.push(SingleOpc, SingleTy, {Va});
1893
8
      return OpRef::res(Results.top());
1894
8
    }
1895
416
  }
1896
416
1897
416
  SmallVector<unsigned,8> SwapElems;
1898
416
  if (HwLen == unsigned(VecLen))
1899
2
    SwapElems.push_back(LogLen-1);
1900
416
1901
436
  for (const CycleType &C : Cycles) {
1902
436
    unsigned First = (C[0] == LogLen-1) ? 
1412
:
024
;
1903
436
    SwapElems.append(C.begin()+First, C.end());
1904
436
    if (First == 0)
1905
24
      SwapElems.push_back(C[0]);
1906
436
  }
1907
416
1908
416
  const SDLoc &dl(Results.InpNode);
1909
416
  OpRef Arg = !Extend ? 
Va414
1910
416
                      : 
concat(Va, OpRef::undef(SingleTy), Results)2
;
1911
416
1912
895
  for (unsigned I = 0, E = SwapElems.size(); I != E; ) {
1913
479
    bool IsInc = I == E-1 || 
SwapElems[I] < SwapElems[I+1]444
;
1914
479
    unsigned S = (1u << SwapElems[I]);
1915
479
    if (I < E-1) {
1916
1.01k
      while (++I < E-1 && 
IsInc == (SwapElems[I] < SwapElems[I+1])637
)
1917
574
        S |= 1u << SwapElems[I];
1918
444
      // The above loop will not add a bit for the final SwapElems[I+1],
1919
444
      // so add it here.
1920
444
      S |= 1u << SwapElems[I];
1921
444
    }
1922
479
    ++I;
1923
479
1924
479
    NodeTemplate Res;
1925
479
    Results.push(Hexagon::A2_tfrsi, MVT::i32,
1926
479
                 { DAG.getTargetConstant(S, dl, MVT::i32) });
1927
479
    Res.Opc = IsInc ? 
Hexagon::V6_vshuffvdd260
:
Hexagon::V6_vdealvdd219
;
1928
479
    Res.Ty = PairTy;
1929
479
    Res.Ops = { OpRef::hi(Arg), OpRef::lo(Arg), OpRef::res(-1) };
1930
479
    Results.push(Res);
1931
479
    Arg = OpRef::res(Results.top());
1932
479
  }
1933
416
1934
416
  return !Extend ? 
Arg414
:
OpRef::lo(Arg)2
;
1935
416
}
1936
1937
130
OpRef HvxSelector::butterfly(ShuffleMask SM, OpRef Va, ResultStack &Results) {
1938
130
  DEBUG_WITH_TYPE("isel", {dbgs() << __func__ << '\n';});
1939
130
  // Butterfly shuffles.
1940
130
  //
1941
130
  // V6_vdelta
1942
130
  // V6_vrdelta
1943
130
  // V6_vror
1944
130
1945
130
  // The assumption here is that all elements picked by Mask are in the
1946
130
  // first operand to the vector_shuffle. This assumption is enforced
1947
130
  // by the caller.
1948
130
1949
130
  MVT ResTy = getSingleVT(MVT::i8);
1950
130
  PermNetwork::Controls FC, RC;
1951
130
  const SDLoc &dl(Results.InpNode);
1952
130
  int VecLen = SM.Mask.size();
1953
130
1954
10.1k
  for (int M : SM.Mask) {
1955
10.1k
    if (M != -1 && 
M >= VecLen6.57k
)
1956
0
      return OpRef::fail();
1957
10.1k
  }
1958
130
1959
130
  // Try the deltas/benes for both single vectors and vector pairs.
1960
130
  ForwardDeltaNetwork FN(SM.Mask);
1961
130
  if (FN.run(FC)) {
1962
121
    SDValue Ctl = getVectorConstant(FC, dl);
1963
121
    Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(Ctl)});
1964
121
    return OpRef::res(Results.top());
1965
121
  }
1966
9
1967
9
  // Try reverse delta.
1968
9
  ReverseDeltaNetwork RN(SM.Mask);
1969
9
  if (RN.run(RC)) {
1970
9
    SDValue Ctl = getVectorConstant(RC, dl);
1971
9
    Results.push(Hexagon::V6_vrdelta, ResTy, {Va, OpRef(Ctl)});
1972
9
    return OpRef::res(Results.top());
1973
9
  }
1974
0
1975
0
  // Do Benes.
1976
0
  BenesNetwork BN(SM.Mask);
1977
0
  if (BN.run(FC, RC)) {
1978
0
    SDValue CtlF = getVectorConstant(FC, dl);
1979
0
    SDValue CtlR = getVectorConstant(RC, dl);
1980
0
    Results.push(Hexagon::V6_vdelta, ResTy, {Va, OpRef(CtlF)});
1981
0
    Results.push(Hexagon::V6_vrdelta, ResTy,
1982
0
                 {OpRef::res(-1), OpRef(CtlR)});
1983
0
    return OpRef::res(Results.top());
1984
0
  }
1985
0
1986
0
  return OpRef::fail();
1987
0
}
1988
1989
SDValue HvxSelector::getVectorConstant(ArrayRef<uint8_t> Data,
1990
181
                                       const SDLoc &dl) {
1991
181
  SmallVector<SDValue, 128> Elems;
1992
181
  for (uint8_t C : Data)
1993
13.9k
    Elems.push_back(DAG.getConstant(C, dl, MVT::i8));
1994
181
  MVT VecTy = MVT::getVectorVT(MVT::i8, Data.size());
1995
181
  SDValue BV = DAG.getBuildVector(VecTy, dl, Elems);
1996
181
  SDValue LV = Lower.LowerOperation(BV, DAG);
1997
181
  DAG.RemoveDeadNode(BV.getNode());
1998
181
  return LV;
1999
181
}
2000
2001
1.02k
void HvxSelector::selectShuffle(SDNode *N) {
2002
1.02k
  DEBUG_WITH_TYPE("isel", {
2003
1.02k
    dbgs() << "Starting " << __func__ << " on node:\n";
2004
1.02k
    N->dump(&DAG);
2005
1.02k
  });
2006
1.02k
  MVT ResTy = N->getValueType(0).getSimpleVT();
2007
1.02k
  // Assume that vector shuffles operate on vectors of bytes.
2008
1.02k
  assert(ResTy.isVector() && ResTy.getVectorElementType() == MVT::i8);
2009
1.02k
2010
1.02k
  auto *SN = cast<ShuffleVectorSDNode>(N);
2011
1.02k
  std::vector<int> Mask(SN->getMask().begin(), SN->getMask().end());
2012
1.02k
  // This shouldn't really be necessary. Is it?
2013
1.02k
  for (int &Idx : Mask)
2014
174k
    if (Idx != -1 && 
Idx < 0136k
)
2015
0
      Idx = -1;
2016
1.02k
2017
1.02k
  unsigned VecLen = Mask.size();
2018
1.02k
  bool HavePairs = (2*HwLen == VecLen);
2019
1.02k
  assert(ResTy.getSizeInBits() / 8 == VecLen);
2020
1.02k
2021
1.02k
  // Vd = vector_shuffle Va, Vb, Mask
2022
1.02k
  //
2023
1.02k
2024
1.02k
  bool UseLeft = false, UseRight = false;
2025
175k
  for (unsigned I = 0; I != VecLen; 
++I174k
) {
2026
174k
    if (Mask[I] == -1)
2027
37.7k
      continue;
2028
136k
    unsigned Idx = Mask[I];
2029
136k
    assert(Idx < 2*VecLen);
2030
136k
    if (Idx < VecLen)
2031
132k
      UseLeft = true;
2032
4.08k
    else
2033
4.08k
      UseRight = true;
2034
136k
  }
2035
1.02k
2036
1.02k
  DEBUG_WITH_TYPE("isel", {
2037
1.02k
    dbgs() << "VecLen=" << VecLen << " HwLen=" << HwLen << " UseLeft="
2038
1.02k
           << UseLeft << " UseRight=" << UseRight << " HavePairs="
2039
1.02k
           << HavePairs << '\n';
2040
1.02k
  });
2041
1.02k
  // If the mask is all -1's, generate "undef".
2042
1.02k
  if (!UseLeft && 
!UseRight0
) {
2043
0
    ISel.ReplaceNode(N, ISel.selectUndef(SDLoc(SN), ResTy).getNode());
2044
0
    return;
2045
0
  }
2046
1.02k
2047
1.02k
  SDValue Vec0 = N->getOperand(0);
2048
1.02k
  SDValue Vec1 = N->getOperand(1);
2049
1.02k
  ResultStack Results(SN);
2050
1.02k
  Results.push(TargetOpcode::COPY, ResTy, {Vec0});
2051
1.02k
  Results.push(TargetOpcode::COPY, ResTy, {Vec1});
2052
1.02k
  OpRef Va = OpRef::res(Results.top()-1);
2053
1.02k
  OpRef Vb = OpRef::res(Results.top());
2054
1.02k
2055
1.02k
  OpRef Res = !HavePairs ? 
shuffs2(ShuffleMask(Mask), Va, Vb, Results)374
2056
1.02k
                         : 
shuffp2(ShuffleMask(Mask), Va, Vb, Results)655
;
2057
1.02k
2058
1.02k
  bool Done = Res.isValid();
2059
1.02k
  if (Done) {
2060
1.02k
    // Make sure that Res is on the stack before materializing.
2061
1.02k
    Results.push(TargetOpcode::COPY, ResTy, {Res});
2062
1.02k
    materialize(Results);
2063
1.02k
  } else {
2064
0
    Done = scalarizeShuffle(Mask, SDLoc(N), ResTy, Vec0, Vec1, N);
2065
0
  }
2066
1.02k
2067
1.02k
  if (!Done) {
2068
#ifndef NDEBUG
2069
    dbgs() << "Unhandled shuffle:\n";
2070
    SN->dumpr(&DAG);
2071
#endif
2072
0
    llvm_unreachable("Failed to select vector shuffle");
2073
0
  }
2074
1.02k
}
2075
2076
150
void HvxSelector::selectRor(SDNode *N) {
2077
150
  // If this is a rotation by less than 8, use V6_valignbi.
2078
150
  MVT Ty = N->getValueType(0).getSimpleVT();
2079
150
  const SDLoc &dl(N);
2080
150
  SDValue VecV = N->getOperand(0);
2081
150
  SDValue RotV = N->getOperand(1);
2082
150
  SDNode *NewN = nullptr;
2083
150
2084
150
  if (auto *CN = dyn_cast<ConstantSDNode>(RotV.getNode())) {
2085
150
    unsigned S = CN->getZExtValue() % HST.getVectorLength();
2086
150
    if (S == 0) {
2087
0
      NewN = VecV.getNode();
2088
150
    } else if (isUInt<3>(S)) {
2089
110
      SDValue C = DAG.getTargetConstant(S, dl, MVT::i32);
2090
110
      NewN = DAG.getMachineNode(Hexagon::V6_valignbi, dl, Ty,
2091
110
                                {VecV, VecV, C});
2092
110
    }
2093
150
  }
2094
150
2095
150
  if (!NewN)
2096
40
    NewN = DAG.getMachineNode(Hexagon::V6_vror, dl, Ty, {VecV, RotV});
2097
150
2098
150
  ISel.ReplaceNode(N, NewN);
2099
150
}
2100
2101
3
void HvxSelector::selectVAlign(SDNode *N) {
2102
3
  SDValue Vv = N->getOperand(0);
2103
3
  SDValue Vu = N->getOperand(1);
2104
3
  SDValue Rt = N->getOperand(2);
2105
3
  SDNode *NewN = DAG.getMachineNode(Hexagon::V6_valignb, SDLoc(N),
2106
3
                                    N->getValueType(0), {Vv, Vu, Rt});
2107
3
  ISel.ReplaceNode(N, NewN);
2108
3
  DAG.RemoveDeadNode(N);
2109
3
}
2110
2111
1.02k
void HexagonDAGToDAGISel::SelectHvxShuffle(SDNode *N) {
2112
1.02k
  HvxSelector(*this, *CurDAG).selectShuffle(N);
2113
1.02k
}
2114
2115
150
void HexagonDAGToDAGISel::SelectHvxRor(SDNode *N) {
2116
150
  HvxSelector(*this, *CurDAG).selectRor(N);
2117
150
}
2118
2119
3
void HexagonDAGToDAGISel::SelectHvxVAlign(SDNode *N) {
2120
3
  HvxSelector(*this, *CurDAG).selectVAlign(N);
2121
3
}
2122
2123
6
void HexagonDAGToDAGISel::SelectV65GatherPred(SDNode *N) {
2124
6
  const SDLoc &dl(N);
2125
6
  SDValue Chain = N->getOperand(0);
2126
6
  SDValue Address = N->getOperand(2);
2127
6
  SDValue Predicate = N->getOperand(3);
2128
6
  SDValue Base = N->getOperand(4);
2129
6
  SDValue Modifier = N->getOperand(5);
2130
6
  SDValue Offset = N->getOperand(6);
2131
6
2132
6
  unsigned Opcode;
2133
6
  unsigned IntNo = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue();
2134
6
  switch (IntNo) {
2135
6
  default:
2136
0
    llvm_unreachable("Unexpected HVX gather intrinsic.");
2137
6
  case Intrinsic::hexagon_V6_vgathermhq:
2138
2
  case Intrinsic::hexagon_V6_vgathermhq_128B:
2139
2
    Opcode = Hexagon::V6_vgathermhq_pseudo;
2140
2
    break;
2141
2
  case Intrinsic::hexagon_V6_vgathermwq:
2142
2
  case Intrinsic::hexagon_V6_vgathermwq_128B:
2143
2
    Opcode = Hexagon::V6_vgathermwq_pseudo;
2144
2
    break;
2145
2
  case Intrinsic::hexagon_V6_vgathermhwq:
2146
2
  case Intrinsic::hexagon_V6_vgathermhwq_128B:
2147
2
    Opcode = Hexagon::V6_vgathermhwq_pseudo;
2148
2
    break;
2149
6
  }
2150
6
2151
6
  SDVTList VTs = CurDAG->getVTList(MVT::Other);
2152
6
  SDValue Ops[] = { Address, Predicate, Base, Modifier, Offset, Chain };
2153
6
  SDNode *Result = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);
2154
6
2155
6
  MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(N)->getMemOperand();
2156
6
  CurDAG->setNodeMemRefs(cast<MachineSDNode>(Result), {MemOp});
2157
6
2158
6
  ReplaceNode(N, Result);
2159
6
}
2160
2161
10
void HexagonDAGToDAGISel::SelectV65Gather(SDNode *N) {
2162
10
  const SDLoc &dl(N);
2163
10
  SDValue Chain = N->getOperand(0);
2164
10
  SDValue Address = N->getOperand(2);
2165
10
  SDValue Base = N->getOperand(3);
2166
10
  SDValue Modifier = N->getOperand(4);
2167
10
  SDValue Offset = N->getOperand(5);
2168
10
2169
10
  unsigned Opcode;
2170
10
  unsigned IntNo = cast<ConstantSDNode>(N->getOperand(1))->getZExtValue();
2171
10
  switch (IntNo) {
2172
10
  default:
2173
0
    llvm_unreachable("Unexpected HVX gather intrinsic.");
2174
10
  case Intrinsic::hexagon_V6_vgathermh:
2175
5
  case Intrinsic::hexagon_V6_vgathermh_128B:
2176
5
    Opcode = Hexagon::V6_vgathermh_pseudo;
2177
5
    break;
2178
5
  case Intrinsic::hexagon_V6_vgathermw:
2179
3
  case Intrinsic::hexagon_V6_vgathermw_128B:
2180
3
    Opcode = Hexagon::V6_vgathermw_pseudo;
2181
3
    break;
2182
3
  case Intrinsic::hexagon_V6_vgathermhw:
2183
2
  case Intrinsic::hexagon_V6_vgathermhw_128B:
2184
2
    Opcode = Hexagon::V6_vgathermhw_pseudo;
2185
2
    break;
2186
10
  }
2187
10
2188
10
  SDVTList VTs = CurDAG->getVTList(MVT::Other);
2189
10
  SDValue Ops[] = { Address, Base, Modifier, Offset, Chain };
2190
10
  SDNode *Result = CurDAG->getMachineNode(Opcode, dl, VTs, Ops);
2191
10
2192
10
  MachineMemOperand *MemOp = cast<MemIntrinsicSDNode>(N)->getMemOperand();
2193
10
  CurDAG->setNodeMemRefs(cast<MachineSDNode>(Result), {MemOp});
2194
10
2195
10
  ReplaceNode(N, Result);
2196
10
}
2197
2198
4
void HexagonDAGToDAGISel::SelectHVXDualOutput(SDNode *N) {
2199
4
  unsigned IID = cast<ConstantSDNode>(N->getOperand(0))->getZExtValue();
2200
4
  SDNode *Result;
2201
4
  switch (IID) {
2202
4
  case Intrinsic::hexagon_V6_vaddcarry: {
2203
1
    SmallVector<SDValue, 3> Ops = { N->getOperand(1), N->getOperand(2),
2204
1
                                    N->getOperand(3) };
2205
1
    SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v512i1);
2206
1
    Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops);
2207
1
    break;
2208
4
  }
2209
4
  case Intrinsic::hexagon_V6_vaddcarry_128B: {
2210
1
    SmallVector<SDValue, 3> Ops = { N->getOperand(1), N->getOperand(2),
2211
1
                                    N->getOperand(3) };
2212
1
    SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v1024i1);
2213
1
    Result = CurDAG->getMachineNode(Hexagon::V6_vaddcarry, SDLoc(N), VTs, Ops);
2214
1
    break;
2215
4
  }
2216
4
  case Intrinsic::hexagon_V6_vsubcarry: {
2217
1
    SmallVector<SDValue, 3> Ops = { N->getOperand(1), N->getOperand(2),
2218
1
                                    N->getOperand(3) };
2219
1
    SDVTList VTs = CurDAG->getVTList(MVT::v16i32, MVT::v512i1);
2220
1
    Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops);
2221
1
    break;
2222
4
  }
2223
4
  case Intrinsic::hexagon_V6_vsubcarry_128B: {
2224
1
    SmallVector<SDValue, 3> Ops = { N->getOperand(1), N->getOperand(2),
2225
1
                                    N->getOperand(3) };
2226
1
    SDVTList VTs = CurDAG->getVTList(MVT::v32i32, MVT::v1024i1);
2227
1
    Result = CurDAG->getMachineNode(Hexagon::V6_vsubcarry, SDLoc(N), VTs, Ops);
2228
1
    break;
2229
4
  }
2230
4
  default:
2231
0
    llvm_unreachable("Unexpected HVX dual output intrinsic.");
2232
4
  }
2233
4
  ReplaceUses(N, Result);
2234
4
  ReplaceUses(SDValue(N, 0), SDValue(Result, 0));
2235
4
  ReplaceUses(SDValue(N, 1), SDValue(Result, 1));
2236
4
  CurDAG->RemoveDeadNode(N);
2237
4
}