1 //===-- PerfectShuffle.cpp - Perfect Shuffle Generator --------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Chris Lattner and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file computes an optimal sequence of instructions for doing all shuffles
11 // of two 4-element vectors. With a release build and when configured to emit
12 // an altivec instruction table, this takes about 30s to run on a 2.7Ghz
15 //===----------------------------------------------------------------------===//
22 // Masks are 4-nibble hex numbers. Values 0-7 in any nibble means that it takes
23 // an element from that value of the input vectors. A value of 8 means the
24 // entry is undefined.
26 // Mask manipulation functions.
27 static inline unsigned short MakeMask(unsigned V0, unsigned V1,
28 unsigned V2, unsigned V3) {
29 return (V0 << (3*4)) | (V1 << (2*4)) | (V2 << (1*4)) | (V3 << (0*4));
32 /// getMaskElt - Return element N of the specified mask.
33 static unsigned getMaskElt(unsigned Mask, unsigned Elt) {
34 return (Mask >> ((3-Elt)*4)) & 0xF;
37 static unsigned setMaskElt(unsigned Mask, unsigned Elt, unsigned NewVal) {
38 unsigned FieldShift = ((3-Elt)*4);
39 return (Mask & ~(0xF << FieldShift)) | (NewVal << FieldShift);
42 // Reject elements where the values are 9-15.
43 static bool isValidMask(unsigned short Mask) {
44 unsigned short UndefBits = Mask & 0x8888;
45 return (Mask & ((UndefBits >> 1)|(UndefBits>>2)|(UndefBits>>3))) == 0;
48 /// hasUndefElements - Return true if any of the elements in the mask are undefs
50 static bool hasUndefElements(unsigned short Mask) {
51 return (Mask & 0x8888) != 0;
54 /// isOnlyLHSMask - Return true if this mask only refers to its LHS, not
55 /// including undef values..
56 static bool isOnlyLHSMask(unsigned short Mask) {
57 return (Mask & 0x4444) == 0;
60 /// getLHSOnlyMask - Given a mask that refers to its LHS and RHS, modify it to
61 /// refer to the LHS only (for when one argument value is passed into the same
63 static unsigned short getLHSOnlyMask(unsigned short Mask) {
64 return Mask & 0xBBBB; // Keep only LHS and Undefs.
67 /// getCompressedMask - Turn a 16-bit uncompressed mask (where each elt uses 4
68 /// bits) into a compressed 13-bit mask, where each elt is multiplied by 9.
69 static unsigned getCompressedMask(unsigned short Mask) {
70 return getMaskElt(Mask, 0)*9*9*9 + getMaskElt(Mask, 1)*9*9 +
71 getMaskElt(Mask, 2)*9 + getMaskElt(Mask, 3);
74 static void PrintMask(unsigned i, std::ostream &OS) {
75 OS << "<" << (char)(getMaskElt(i, 0) == 8 ? 'u' : ('0'+getMaskElt(i, 0)))
76 << "," << (char)(getMaskElt(i, 1) == 8 ? 'u' : ('0'+getMaskElt(i, 1)))
77 << "," << (char)(getMaskElt(i, 2) == 8 ? 'u' : ('0'+getMaskElt(i, 2)))
78 << "," << (char)(getMaskElt(i, 3) == 8 ? 'u' : ('0'+getMaskElt(i, 3)))
82 /// ShuffleVal - This represents a shufflevector operation.
84 unsigned Cost; // Number of instrs used to generate this value.
85 Operator *Op; // The Operation used to generate this value.
86 unsigned short Arg0, Arg1; // Input operands for this value.
88 ShuffleVal() : Cost(1000000) {}
92 /// ShufTab - This is the actual shuffle table that we are trying to generate.
94 static ShuffleVal ShufTab[65536];
96 /// TheOperators - All of the operators that this target supports.
97 static std::vector<Operator*> TheOperators;
99 /// Operator - This is a vector operation that is available for use.
101 unsigned short ShuffleMask;
102 unsigned short OpNum;
105 Operator(unsigned short shufflemask, const char *name)
106 : ShuffleMask(shufflemask), Name(name) {
107 OpNum = TheOperators.size();
108 TheOperators.push_back(this);
111 assert(TheOperators.back() == this);
112 TheOperators.pop_back();
115 bool isOnlyLHSOperator() const {
116 return isOnlyLHSMask(ShuffleMask);
119 const char *getName() const { return Name; }
121 unsigned short getTransformedMask(unsigned short LHSMask, unsigned RHSMask) {
122 // Extract the elements from LHSMask and RHSMask, as appropriate.
124 for (unsigned i = 0; i != 4; ++i) {
125 unsigned SrcElt = (ShuffleMask >> (4*i)) & 0xF;
128 ResElt = getMaskElt(LHSMask, SrcElt);
130 ResElt = getMaskElt(RHSMask, SrcElt-4);
132 assert(SrcElt == 8 && "Bad src elt!");
135 Result |= ResElt << (4*i);
141 static const char *getZeroCostOpName(unsigned short Op) {
142 if (ShufTab[Op].Arg0 == 0x0123)
144 else if (ShufTab[Op].Arg0 == 0x4567)
147 assert(0 && "bad zero cost operation");
152 static void PrintOperation(unsigned ValNo, unsigned short Vals[]) {
153 unsigned short ThisOp = Vals[ValNo];
154 std::cerr << "t" << ValNo;
155 PrintMask(ThisOp, std::cerr);
156 std::cerr << " = " << ShufTab[ThisOp].Op->getName() << "(";
158 if (ShufTab[ShufTab[ThisOp].Arg0].Cost == 0) {
159 std::cerr << getZeroCostOpName(ShufTab[ThisOp].Arg0);
160 PrintMask(ShufTab[ThisOp].Arg0, std::cerr);
162 // Figure out what tmp # it is.
163 for (unsigned i = 0; ; ++i)
164 if (Vals[i] == ShufTab[ThisOp].Arg0) {
165 std::cerr << "t" << i;
170 if (!ShufTab[Vals[ValNo]].Op->isOnlyLHSOperator()) {
172 if (ShufTab[ShufTab[ThisOp].Arg1].Cost == 0) {
173 std::cerr << getZeroCostOpName(ShufTab[ThisOp].Arg1);
174 PrintMask(ShufTab[ThisOp].Arg1, std::cerr);
176 // Figure out what tmp # it is.
177 for (unsigned i = 0; ; ++i)
178 if (Vals[i] == ShufTab[ThisOp].Arg1) {
179 std::cerr << "t" << i;
187 static unsigned getNumEntered() {
189 for (unsigned i = 0; i != 65536; ++i)
190 Count += ShufTab[i].Cost < 100;
194 static void EvaluateOps(unsigned short Elt, unsigned short Vals[],
196 if (ShufTab[Elt].Cost == 0) return;
198 // If this value has already been evaluated, it is free. FIXME: match undefs.
199 for (unsigned i = 0, e = NumVals; i != e; ++i)
200 if (Vals[i] == Elt) return;
202 // Otherwise, get the operands of the value, then add it.
203 unsigned Arg0 = ShufTab[Elt].Arg0, Arg1 = ShufTab[Elt].Arg1;
204 if (ShufTab[Arg0].Cost)
205 EvaluateOps(Arg0, Vals, NumVals);
206 if (Arg0 != Arg1 && ShufTab[Arg1].Cost)
207 EvaluateOps(Arg1, Vals, NumVals);
209 Vals[NumVals++] = Elt;
214 // Seed the table with accesses to the LHS and RHS.
215 ShufTab[0x0123].Cost = 0;
216 ShufTab[0x0123].Op = 0;
217 ShufTab[0x0123].Arg0 = 0x0123;
218 ShufTab[0x4567].Cost = 0;
219 ShufTab[0x4567].Op = 0;
220 ShufTab[0x4567].Arg0 = 0x4567;
222 // Seed the first-level of shuffles, shuffles whose inputs are the input to
223 // the vectorshuffle operation.
224 bool MadeChange = true;
225 unsigned OpCount = 0;
229 std::cerr << "Starting iteration #" << OpCount << " with "
230 << getNumEntered() << " entries established.\n";
232 // Scan the table for two reasons: First, compute the maximum cost of any
233 // operation left in the table. Second, make sure that values with undefs
234 // have the cheapest alternative that they match.
235 unsigned MaxCost = ShufTab[0].Cost;
236 for (unsigned i = 1; i != 0x8889; ++i) {
237 if (!isValidMask(i)) continue;
238 if (ShufTab[i].Cost > MaxCost)
239 MaxCost = ShufTab[i].Cost;
241 // If this value has an undef, make it be computed the cheapest possible
242 // way of any of the things that it matches.
243 if (hasUndefElements(i)) {
244 // This code is a little bit tricky, so here's the idea: consider some
245 // permutation, like 7u4u. To compute the lowest cost for 7u4u, we
246 // need to take the minimum cost of all of 7[0-8]4[0-8], 81 entries. If
247 // there are 3 undefs, the number rises to 729 entries we have to scan,
248 // and for the 4 undef case, we have to scan the whole table.
250 // Instead of doing this huge amount of scanning, we process the table
251 // entries *in order*, and use the fact that 'u' is 8, larger than any
252 // valid index. Given an entry like 7u4u then, we only need to scan
253 // 7[0-7]4u - 8 entries. We can get away with this, because we already
254 // know that each of 704u, 714u, 724u, etc contain the minimum value of
255 // all of the 704[0-8], 714[0-8] and 724[0-8] entries respectively.
269 unsigned MinCost = ShufTab[i].Cost;
271 // Scan the 8 entries.
272 for (unsigned j = 0; j != 8; ++j) {
273 unsigned NewElt = setMaskElt(i, UndefIdx, j);
274 if (ShufTab[NewElt].Cost < MinCost) {
275 MinCost = ShufTab[NewElt].Cost;
280 // If we found something cheaper than what was here before, use it.
283 ShufTab[i] = ShufTab[MinVal];
288 for (unsigned LHS = 0; LHS != 0x8889; ++LHS) {
289 if (!isValidMask(LHS)) continue;
290 if (ShufTab[LHS].Cost > 1000) continue;
292 // If nothing involving this operand could possibly be cheaper than what
293 // we already have, don't consider it.
294 if (ShufTab[LHS].Cost + 1 >= MaxCost)
297 for (unsigned opnum = 0, e = TheOperators.size(); opnum != e; ++opnum) {
298 Operator *Op = TheOperators[opnum];
299 unsigned short Mask = Op->ShuffleMask;
301 // Evaluate op(LHS,LHS)
302 unsigned ResultMask = Op->getTransformedMask(LHS, LHS);
304 unsigned Cost = ShufTab[LHS].Cost + 1;
305 if (Cost < ShufTab[ResultMask].Cost) {
306 ShufTab[ResultMask].Cost = Cost;
307 ShufTab[ResultMask].Op = Op;
308 ShufTab[ResultMask].Arg0 = LHS;
309 ShufTab[ResultMask].Arg1 = LHS;
313 // If this is a two input instruction, include the op(x,y) cases. If
314 // this is a one input instruction, skip this.
315 if (Op->isOnlyLHSOperator()) continue;
317 for (unsigned RHS = 0; RHS != 0x8889; ++RHS) {
318 if (!isValidMask(RHS)) continue;
319 if (ShufTab[RHS].Cost > 1000) continue;
321 // If nothing involving this operand could possibly be cheaper than
322 // what we already have, don't consider it.
323 if (ShufTab[RHS].Cost + 1 >= MaxCost)
327 // Evaluate op(LHS,RHS)
328 unsigned ResultMask = Op->getTransformedMask(LHS, RHS);
330 if (ShufTab[ResultMask].Cost <= OpCount ||
331 ShufTab[ResultMask].Cost <= ShufTab[LHS].Cost ||
332 ShufTab[ResultMask].Cost <= ShufTab[RHS].Cost)
335 // Figure out the cost to evaluate this, knowing that CSE's only need
336 // to be evaluated once.
337 unsigned short Vals[30];
338 unsigned NumVals = 0;
339 EvaluateOps(LHS, Vals, NumVals);
340 EvaluateOps(RHS, Vals, NumVals);
342 unsigned Cost = NumVals + 1;
343 if (Cost < ShufTab[ResultMask].Cost) {
344 ShufTab[ResultMask].Cost = Cost;
345 ShufTab[ResultMask].Op = Op;
346 ShufTab[ResultMask].Arg0 = LHS;
347 ShufTab[ResultMask].Arg1 = RHS;
355 std::cerr << "Finished Table has " << getNumEntered()
356 << " entries established.\n";
358 unsigned CostArray[10] = { 0 };
360 // Compute a cost histogram.
361 for (unsigned i = 0; i != 65536; ++i) {
362 if (!isValidMask(i)) continue;
363 if (ShufTab[i].Cost > 9)
366 ++CostArray[ShufTab[i].Cost];
369 for (unsigned i = 0; i != 9; ++i)
371 std::cout << "// " << CostArray[i] << " entries have cost " << i << "\n";
373 std::cout << "// " << CostArray[9] << " entries have higher cost!\n";
376 // Build up the table to emit.
377 std::cout << "\n// This table is 6561*4 = 26244 bytes in size.\n";
378 std::cout << "static const unsigned PerfectShuffleTable[6561+1] = {\n";
380 for (unsigned i = 0; i != 0x8889; ++i) {
381 if (!isValidMask(i)) continue;
383 // CostSat - The cost of this operation saturated to two bits.
384 unsigned CostSat = ShufTab[i].Cost;
385 if (CostSat > 3) CostSat = 3;
387 unsigned OpNum = ShufTab[i].Op ? ShufTab[i].Op->OpNum : 0;
388 assert(OpNum < 16 && "Too few bits to encode operation!");
390 unsigned LHS = getCompressedMask(ShufTab[i].Arg0);
391 unsigned RHS = getCompressedMask(ShufTab[i].Arg1);
393 // Encode this as 2 bits of saturated cost, 4 bits of opcodes, 13 bits of
394 // LHS, and 13 bits of RHS = 32 bits.
395 unsigned Val = (CostSat << 30) | (OpNum << 27) | (LHS << 13) | RHS;
397 std::cout << " " << Val << "U,\t// ";
398 PrintMask(i, std::cout);
399 std::cout << ": Cost " << ShufTab[i].Cost;
400 std::cout << " " << (ShufTab[i].Op ? ShufTab[i].Op->getName() : "copy");
402 if (ShufTab[ShufTab[i].Arg0].Cost == 0) {
403 std::cout << getZeroCostOpName(ShufTab[i].Arg0);
405 PrintMask(ShufTab[i].Arg0, std::cout);
408 if (ShufTab[i].Op && !ShufTab[i].Op->isOnlyLHSOperator()) {
410 if (ShufTab[ShufTab[i].Arg1].Cost == 0) {
411 std::cout << getZeroCostOpName(ShufTab[i].Arg1);
413 PrintMask(ShufTab[i].Arg1, std::cout);
418 std::cout << " 0\n};\n";
421 // Print out the table.
422 for (unsigned i = 0; i != 0x8889; ++i) {
423 if (!isValidMask(i)) continue;
424 if (ShufTab[i].Cost < 1000) {
425 PrintMask(i, std::cerr);
426 std::cerr << " - Cost " << ShufTab[i].Cost << " - ";
428 unsigned short Vals[30];
429 unsigned NumVals = 0;
430 EvaluateOps(i, Vals, NumVals);
432 for (unsigned j = 0, e = NumVals; j != e; ++j)
433 PrintOperation(j, Vals);
442 ///===---------------------------------------------------------------------===//
443 /// The altivec instruction definitions. This is the altivec-specific part of
445 ///===---------------------------------------------------------------------===//
447 struct vmrghw : public Operator {
448 vmrghw() : Operator(0x0415, "vmrghw") {}
451 struct vmrglw : public Operator {
452 vmrglw() : Operator(0x2637, "vmrglw") {}
455 template<unsigned Elt>
456 struct vspltisw : public Operator {
457 vspltisw(const char *N) : Operator(MakeMask(Elt, Elt, Elt, Elt), N) {}
460 vspltisw<0> the_vspltisw0("vspltisw0");
461 vspltisw<1> the_vspltisw1("vspltisw1");
462 vspltisw<2> the_vspltisw2("vspltisw2");
463 vspltisw<3> the_vspltisw3("vspltisw3");
466 struct vsldoi : public Operator {
467 vsldoi(const char *n) : Operator(MakeMask(N&7, (N+1)&7, (N+2)&7, (N+3)&7), n){
471 vsldoi<1> the_vsldoi1("vsldoi4");
472 vsldoi<2> the_vsldoi2("vsldoi8");
473 vsldoi<3> the_vsldoi3("vsldoi12");