contrib/llvm/lib/Target/Hexagon/HexagonISelDAGToDAGHVX.cpp

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