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