xref: /netbsd-src/external/gpl3/gcc/dist/libphobos/libdruntime/core/internal/array/operations.d (revision 0a3071956a3a9fdebdbf7f338cf2d439b45fc728)
1 /**
2  This module contains support array (vector) operations
3   Copyright: Copyright Digital Mars 2000 - 2019.
4   License: Distributed under the
5        $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0).
6      (See accompanying file LICENSE)
7   Source: $(DRUNTIMESRC core/_internal/_array/_operations.d)
8 */
9 module core.internal.array.operations;
10 import core.internal.traits : Filter, staticMap, Unqual;
11 
12 version (GNU) version = GNU_OR_LDC;
13 version (LDC) version = GNU_OR_LDC;
14 
15 /**
16  * Perform array (vector) operations and store the result in `res`.  Operand
17  * types and operations are passed as template arguments in Reverse Polish
18  * Notation (RPN).
19 
20  * Operands can be slices or scalar types. The element types of all
21  * slices and all scalar types must be implicitly convertible to `T`.
22  *
23  * Operations are encoded as strings, e.g. `"+"`, `"%"`, `"*="`. Unary
24  * operations are prefixed with "u", e.g. `"u-"`, `"u~"`. Only the last
25  * operation can and must be an assignment (`"="`) or op-assignment (`"op="`).
26  *
27  * All slice operands must have the same length as the result slice.
28  *
29  * Params: T[] = type of result slice
30  *        Args = operand types and operations in RPN
31  *         res = the slice in which to store the results
32  *        args = operand values
33  *
34  * Returns: the slice containing the result
35  */
36 T[] arrayOp(T : T[], Args...)(T[] res, Filter!(isType, Args) args) @trusted @nogc pure nothrow
37 {
38     alias scalarizedExp = staticMap!(toElementType, Args);
39     alias check = typeCheck!(true, T, scalarizedExp); // must support all scalar ops
40 
foreach(argsIdx,arg;typeof(args) )41     foreach (argsIdx, arg; typeof(args))
42     {
43         static if (is(arg == U[], U))
44         {
45             assert(res.length == args[argsIdx].length, "Mismatched array lengths for vector operation");
46         }
47     }
48 
49     size_t pos;
50     static if (vectorizeable!(T[], Args))
51     {
52         alias vec = .vec!T;
53         alias load = .load!(T, vec.length);
54         alias store = .store!(T, vec.length);
55 
56         // Given that there are at most as many scalars broadcast as there are
57         // operations in any `ary[] = ary[] op const op const`, it should always be
58         // worthwhile to choose vector operations.
59         if (!__ctfe && res.length >= vec.length)
60         {
61             mixin(initScalarVecs!Args);
62 
63             auto n = res.length / vec.length;
64             do
65             {
66                 mixin(vectorExp!Args ~ ";");
67                 pos += vec.length;
68             }
69             while (--n);
70         }
71     }
72     for (; pos < res.length; ++pos)
73         mixin(scalarExp!Args ~ ";");
74 
75     return res;
76 }
77 
78 private:
79 
80 // SIMD helpers
81 
version(DigitalMars)82 version (DigitalMars)
83 {
84     import core.simd;
85 
86     template vec(T)
87     {
88         enum regsz = 16; // SSE2
89         enum N = regsz / T.sizeof;
90         alias vec = __vector(T[N]);
91     }
92 
93     void store(T, size_t N)(T* p, const scope __vector(T[N]) val)
94     {
95         pragma(inline, true);
96         alias vec = __vector(T[N]);
97 
98         static if (is(T == float))
99             cast(void) __simd_sto(XMM.STOUPS, *cast(vec*) p, val);
100         else static if (is(T == double))
101             cast(void) __simd_sto(XMM.STOUPD, *cast(vec*) p, val);
102         else
103             cast(void) __simd_sto(XMM.STODQU, *cast(vec*) p, val);
104     }
105 
106     const(__vector(T[N])) load(T, size_t N)(const scope T* p)
107     {
108         import core.simd;
109 
110         pragma(inline, true);
111         alias vec = __vector(T[N]);
112 
113         static if (is(T == float))
114             return cast(typeof(return)) __simd(XMM.LODUPS, *cast(const vec*) p);
115         else static if (is(T == double))
116             return cast(typeof(return)) __simd(XMM.LODUPD, *cast(const vec*) p);
117         else
118             return cast(typeof(return)) __simd(XMM.LODDQU, *cast(const vec*) p);
119     }
120 
121     __vector(T[N]) binop(string op, T, size_t N)(const scope __vector(T[N]) a, const scope __vector(T[N]) b)
122     {
123         pragma(inline, true);
124         return mixin("a " ~ op ~ " b");
125     }
126 
127     __vector(T[N]) unaop(string op, T, size_t N)(const scope __vector(T[N]) a)
128             if (op[0] == 'u')
129     {
130         pragma(inline, true);
131         return mixin(op[1 .. $] ~ "a");
132     }
133 }
134 
135 // mixin gen
136 
137 /**
138 Check whether operations on operand types are supported.  This
139 template recursively reduces the expression tree and determines
140 intermediate types.
141 Type checking is done here rather than in the compiler to provide more
142 detailed error messages.
143 
144 Params:
145     fail = whether to fail (static assert) with a human-friendly error message
146        T = type of result
147     Args = operand types and operations in RPN
148 Returns:
149     The resulting type of the expression
150 See_Also:
151     $(LREF arrayOp)
152 */
typeCheck(bool fail,T,Args...)153 template typeCheck(bool fail, T, Args...)
154 {
155     enum idx = staticIndexOf!(not!isType, Args);
156     static if (isUnaryOp(Args[idx]))
157     {
158         alias UT = Args[idx - 1];
159         enum op = Args[idx][1 .. $];
160         static if (is(typeof((UT a) => mixin(op ~ "cast(int) a")) RT == return))
161             alias typeCheck = typeCheck!(fail, T, Args[0 .. idx - 1], RT, Args[idx + 1 .. $]);
162         else static if (fail)
163             static assert(0, "Unary `" ~ op ~ "` not supported for type `" ~ UT.stringof ~ "`.");
164     }
165     else static if (isBinaryOp(Args[idx]))
166     {
167         alias LHT = Args[idx - 2];
168         alias RHT = Args[idx - 1];
169         enum op = Args[idx];
170         static if (is(typeof((LHT a, RHT b) => mixin("a " ~ op ~ " b")) RT == return))
171             alias typeCheck = typeCheck!(fail, T, Args[0 .. idx - 2], RT, Args[idx + 1 .. $]);
172         else static if (fail)
173             static assert(0,
174                     "Binary `" ~ op ~ "` not supported for types `"
175                     ~ LHT.stringof ~ "` and `" ~ RHT.stringof ~ "`.");
176     }
177     else static if (Args[idx] == "=" || isBinaryAssignOp(Args[idx]))
178     {
179         alias RHT = Args[idx - 1];
180         enum op = Args[idx];
181         static if (is(T == __vector(ET[N]), ET, size_t N))
182         {
183             // no `cast(T)` before assignment for vectors
184             static if (is(typeof((T res, RHT b) => mixin("res " ~ op ~ " b")) RT == return)
185                     && // workaround https://issues.dlang.org/show_bug.cgi?id=17758
186                     (op != "=" || is(Unqual!T == Unqual!RHT)))
187                 alias typeCheck = typeCheck!(fail, T, Args[0 .. idx - 1], RT, Args[idx + 1 .. $]);
188             else static if (fail)
189                 static assert(0,
190                         "Binary op `" ~ op ~ "` not supported for types `"
191                         ~ T.stringof ~ "` and `" ~ RHT.stringof ~ "`.");
192         }
193         else
194         {
195             static if (is(typeof((RHT b) => mixin("cast(T) b"))))
196             {
197                 static if (is(typeof((T res, T b) => mixin("res " ~ op ~ " b")) RT == return))
198                     alias typeCheck = typeCheck!(fail, T, Args[0 .. idx - 1], RT, Args[idx + 1 .. $]);
199                 else static if (fail)
200                     static assert(0,
201                             "Binary op `" ~ op ~ "` not supported for types `"
202                             ~ T.stringof ~ "` and `" ~ T.stringof ~ "`.");
203             }
204             else static if (fail)
205                 static assert(0,
206                         "`cast(" ~ T.stringof ~ ")` not supported for type `" ~ RHT.stringof ~ "`.");
207         }
208     }
209     else
210         static assert(0);
211 }
212 /// ditto
typeCheck(bool fail,T,ResultType)213 template typeCheck(bool fail, T, ResultType)
214 {
215     alias typeCheck = ResultType;
216 }
217 
version(GNU_OR_LDC)218 version (GNU_OR_LDC)
219 {
220     // leave it to the auto-vectorizer
221     enum vectorizeable(E : E[], Args...) = false;
222 }
223 else
224 {
225     // check whether arrayOp is vectorizable
226     template vectorizeable(E : E[], Args...)
227     {
228         static if (is(vec!E))
229         {
230             // type check with vector types
231             enum vectorizeable = is(typeCheck!(false, vec!E, staticMap!(toVecType, Args)));
232         }
233         else
234             enum vectorizeable = false;
235     }
236 
version(X86_64)237     version (X86_64) unittest
238     {
239         static assert(vectorizeable!(double[], const(double)[], double[], "+", "="));
240         static assert(!vectorizeable!(double[], const(ulong)[], double[], "+", "="));
241         // Vector type are (atm.) not implicitly convertible and would require
242         // lots of SIMD intrinsics. Therefor leave mixed type array ops to
243         // GDC/LDC's auto-vectorizers.
244         static assert(!vectorizeable!(double[], const(uint)[], uint, "+", "="));
245     }
246 }
247 
isUnaryOp(scope string op)248 bool isUnaryOp(scope string op) pure nothrow @safe @nogc
249 {
250     return op[0] == 'u';
251 }
252 
isBinaryOp(scope string op)253 bool isBinaryOp(scope string op) pure nothrow @safe @nogc
254 {
255     if (op == "^^")
256         return true;
257     if (op.length != 1)
258         return false;
259     switch (op[0])
260     {
261     case '+', '-', '*', '/', '%', '|', '&', '^':
262         return true;
263     default:
264         return false;
265     }
266 }
267 
isBinaryAssignOp(string op)268 bool isBinaryAssignOp(string op)
269 {
270     return op.length >= 2 && op[$ - 1] == '=' && isBinaryOp(op[0 .. $ - 1]);
271 }
272 
273 // Generate mixin expression to perform scalar arrayOp loop expression, assumes
274 // `pos` to be the current slice index, `args` to contain operand values, and
275 // `res` the target slice.
scalarExp(Args...)276 enum scalarExp(Args...) =
277 (){
278     string[] stack;
279     size_t argsIdx;
280 
281     static if (is(Args[0] == U[], U))
282         alias Type = U;
283     else
284         alias Type = Args[0];
285 
286     foreach (i, arg; Args)
287     {
288         static if (is(arg == T[], T))
289             stack ~= "args[" ~ argsIdx++.toString ~ "][pos]";
290         else static if (is(arg))
291             stack ~= "args[" ~ argsIdx++.toString ~ "]";
292         else static if (isUnaryOp(arg))
293         {
294             auto op = arg[0] == 'u' ? arg[1 .. $] : arg;
295             // Explicitly use the old integral promotion rules
296             // See also: https://dlang.org/changelog/2.078.0.html#fix16997
297             static if (is(Type : int))
298                 stack[$ - 1] = "cast(typeof(" ~ stack[$ -1] ~ "))" ~ op ~ "cast(int)("~ stack[$ - 1] ~ ")";
299             else
300                 stack[$ - 1] = op ~ stack[$ - 1];
301         }
302         else static if (arg == "=")
303         {
304             stack[$ - 1] = "res[pos] = cast(T)(" ~ stack[$ - 1] ~ ")";
305         }
306         else static if (isBinaryAssignOp(arg))
307         {
308             stack[$ - 1] = "res[pos] " ~ arg ~ " cast(T)(" ~ stack[$ - 1] ~ ")";
309         }
310         else static if (isBinaryOp(arg))
311         {
312             stack[$ - 2] = "(" ~ stack[$ - 2] ~ " " ~ arg ~ " " ~ stack[$ - 1] ~ ")";
313             stack.length -= 1;
314         }
315         else
316             assert(0, "Unexpected op " ~ arg);
317     }
318     assert(stack.length == 1);
319     return stack[0];
320 }();
321 
322 // Generate mixin statement to perform vector loop initialization, assumes
323 // `args` to contain operand values.
initScalarVecs(Args...)324 enum initScalarVecs(Args...) =
325 () {
326     size_t scalarsIdx, argsIdx;
327     string res;
328     foreach (arg; Args)
329     {
330         static if (is(arg == T[], T))
331         {
332             ++argsIdx;
333         }
334         else static if (is(arg))
335             res ~= "immutable vec scalar" ~ scalarsIdx++.toString ~ " = args["
336                 ~ argsIdx++.toString ~ "];\n";
337     }
338     return res;
339 }();
340 
341 // Generate mixin expression to perform vector arrayOp loop expression, assumes
342 // `pos` to be the current slice index, `args` to contain operand values, and
343 // `res` the target slice.
vectorExp(Args...)344 enum vectorExp(Args...) =
345 () {
346     size_t scalarsIdx, argsIdx;
347     string[] stack;
348     foreach (arg; Args)
349     {
350         static if (is(arg == T[], T))
351             stack ~= "load(&args[" ~ argsIdx++.toString ~ "][pos])";
352         else static if (is(arg))
353         {
354             ++argsIdx;
355             stack ~= "scalar" ~ scalarsIdx++.toString;
356         }
357         else static if (isUnaryOp(arg))
358         {
359             auto op = arg[0] == 'u' ? arg[1 .. $] : arg;
360             stack[$ - 1] = "unaop!\"" ~ arg ~ "\"(" ~ stack[$ - 1] ~ ")";
361         }
362         else static if (arg == "=")
363         {
364             stack[$ - 1] = "store(&res[pos], " ~ stack[$ - 1] ~ ")";
365         }
366         else static if (isBinaryAssignOp(arg))
367         {
368             stack[$ - 1] = "store(&res[pos], binop!\"" ~ arg[0 .. $ - 1]
369                 ~ "\"(load(&res[pos]), " ~ stack[$ - 1] ~ "))";
370         }
371         else static if (isBinaryOp(arg))
372         {
373             stack[$ - 2] = "binop!\"" ~ arg ~ "\"(" ~ stack[$ - 2] ~ ", " ~ stack[$ - 1] ~ ")";
374             stack.length -= 1;
375         }
376         else
377             assert(0, "Unexpected op " ~ arg);
378     }
379     assert(stack.length == 1);
380     return stack[0];
381 }();
382 
383 // other helpers
384 
385 enum isType(T) = true;
386 enum isType(alias a) = false;
not(alias tmlp)387 template not(alias tmlp)
388 {
389     enum not(Args...) = !tmlp!Args;
390 }
391 /**
392 Find element in `haystack` for which `pred` is true.
393 
394 Params:
395     pred = the template predicate
396     haystack = elements to search
397 Returns:
398     The first index for which `pred!haystack[index]` is true or -1.
399  */
staticIndexOf(alias pred,haystack...)400 template staticIndexOf(alias pred, haystack...)
401 {
402     static if (pred!(haystack[0]))
403         enum staticIndexOf = 0;
404     else
405     {
406         enum next = staticIndexOf!(pred, haystack[1 .. $]);
407         enum staticIndexOf = next == -1 ? -1 : next + 1;
408     }
409 }
410 /// converts slice types to their element type, preserves anything else
411 alias toElementType(E : E[]) = E;
412 alias toElementType(S) = S;
413 alias toElementType(alias op) = op;
414 /// converts slice types to their element type, preserves anything else
415 alias toVecType(E : E[]) = vec!E;
416 alias toVecType(S) = vec!S;
417 alias toVecType(alias op) = op;
418 
toString(size_t num)419 string toString(size_t num)
420 {
421     import core.internal.string : unsignedToTempString;
422     version (D_BetterC)
423     {
424         // Workaround for https://issues.dlang.org/show_bug.cgi?id=19268
425         if (__ctfe)
426         {
427             char[20] fixedbuf = void;
428             char[] buf = unsignedToTempString(num, fixedbuf);
429             char[] result = new char[buf.length];
430             result[] = buf[];
431             return (() @trusted => cast(string) result)();
432         }
433         else
434         {
435             // Failing at execution rather than during compilation is
436             // not good, but this is in `core.internal` so it should
437             // not be used by the unwary.
438             assert(0, __FUNCTION__ ~ " not available in -betterC except during CTFE.");
439         }
440     }
441     else
442     {
443         char[20] buf = void;
444         return unsignedToTempString(num, buf).idup;
445     }
446 }
447 
contains(T)448 bool contains(T)(const scope T[] ary, const scope T[] vals...)
449 {
450     foreach (v1; ary)
451         foreach (v2; vals)
452             if (v1 == v2)
453                 return true;
454     return false;
455 }
456 
457 // tests
458 
version(CoreUnittest)459 version (CoreUnittest) template TT(T...)
460 {
461     alias TT = T;
462 }
463 
version(CoreUnittest)464 version (CoreUnittest) template _arrayOp(Args...)
465 {
466     alias _arrayOp = arrayOp!Args;
467 }
468 
469 unittest
470 {
check(string op,TA,TB,T,size_t N)471     static void check(string op, TA, TB, T, size_t N)(TA a, TB b, const scope ref T[N] exp)
472     {
473         T[N] res;
474         _arrayOp!(T[], TA, TB, op, "=")(res[], a, b);
475         foreach (i; 0 .. N)
476             assert(res[i] == exp[i]);
477     }
478 
check2(string unaOp,string binOp,TA,TB,T,size_t N)479     static void check2(string unaOp, string binOp, TA, TB, T, size_t N)(TA a, TB b, const scope ref T[N] exp)
480     {
481         T[N] res;
482         _arrayOp!(T[], TA, TB, unaOp, binOp, "=")(res[], a, b);
483         foreach (i; 0 .. N)
484             assert(res[i] == exp[i]);
485     }
486 
487     static void test(T, string op, size_t N = 16)(T a, T b, T exp)
488     {
489         T[N] va = a, vb = b, vexp = exp;
490 
491         check!op(va[], vb[], vexp);
492         check!op(va[], b, vexp);
493         check!op(a, vb[], vexp);
494     }
495 
496     static void test2(T, string unaOp, string binOp, size_t N = 16)(T a, T b, T exp)
497     {
498         T[N] va = a, vb = b, vexp = exp;
499 
500         check2!(unaOp, binOp)(va[], vb[], vexp);
501         check2!(unaOp, binOp)(va[], b, vexp);
502         check2!(unaOp, binOp)(a, vb[], vexp);
503     }
504 
505     alias UINTS = TT!(ubyte, ushort, uint, ulong);
506     alias INTS = TT!(byte, short, int, long);
507     alias FLOATS = TT!(float, double);
508 
509     foreach (T; TT!(UINTS, INTS, FLOATS))
510     {
511         test!(T, "+")(1, 2, 3);
512         test!(T, "-")(3, 2, 1);
513         static if (__traits(compiles, { import std.math; }))
514             test!(T, "^^")(2, 3, 8);
515 
516         test2!(T, "u-", "+")(3, 2, 1);
517     }
518 
519     foreach (T; TT!(UINTS, INTS))
520     {
521         test!(T, "|")(1, 2, 3);
522         test!(T, "&")(3, 1, 1);
523         test!(T, "^")(3, 1, 2);
524 
525         test2!(T, "u~", "+")(3, cast(T)~2, 5);
526     }
527 
528     foreach (T; TT!(INTS, FLOATS))
529     {
530         test!(T, "-")(1, 2, -1);
531         test2!(T, "u-", "+")(-3, -2, -1);
532         test2!(T, "u-", "*")(-3, -2, -6);
533     }
534 
535     foreach (T; TT!(UINTS, INTS, FLOATS))
536     {
537         test!(T, "*")(2, 3, 6);
538         test!(T, "/")(8, 4, 2);
539         test!(T, "%")(8, 6, 2);
540     }
541 }
542 
543 // test handling of v op= exp
544 unittest
545 {
546     uint[32] c;
547     arrayOp!(uint[], uint, "+=")(c[], 2);
548     foreach (v; c)
549         assert(v == 2);
550     static if (__traits(compiles, { import std.math; }))
551     {
552         arrayOp!(uint[], uint, "^^=")(c[], 3);
553         foreach (v; c)
554             assert(v == 8);
555     }
556 }
557 
558 // proper error message for UDT lacking certain ops
559 unittest
560 {
561     static assert(!is(typeof(&arrayOp!(int[4][], int[4], "+="))));
562     static assert(!is(typeof(&arrayOp!(int[4][], int[4], "u-", "="))));
563 
564     static struct S
565     {
566     }
567 
568     static assert(!is(typeof(&arrayOp!(S[], S, "+="))));
569     static assert(!is(typeof(&arrayOp!(S[], S[], "*", S, "+="))));
570     static struct S2
571     {
opBinaryS2572         S2 opBinary(string op)(in S2) @nogc pure nothrow
573         {
574             return this;
575         }
576 
opOpAssignS2577         ref S2 opOpAssign(string op)(in S2) @nogc pure nothrow
578         {
579             return this;
580         }
581     }
582 
583     static assert(is(typeof(&arrayOp!(S2[], S2[], S2[], S2, "*", "+", "="))));
584     static assert(is(typeof(&arrayOp!(S2[], S2[], S2, "*", "+="))));
585 }
586 
587 // test mixed type array op
588 unittest
589 {
590     uint[32] a = 0xF;
591     float[32] res = 2.0f;
592     arrayOp!(float[], const(uint)[], uint, "&", "*=")(res[], a[], 12);
593     foreach (v; res[])
594         assert(v == 24.0f);
595 }
596 
597 // test mixed type array op
598 unittest
599 {
600     static struct S
601     {
opBinaryS602         float opBinary(string op)(in S) @nogc const pure nothrow
603         {
604             return 2.0f;
605         }
606     }
607 
608     float[32] res = 24.0f;
609     S[32] s;
610     arrayOp!(float[], const(S)[], const(S)[], "+", "/=")(res[], s[], s[]);
611     foreach (v; res[])
612         assert(v == 12.0f);
613 }
614 
615 // test scalar after operation argument
616 unittest
617 {
618     float[32] res, a = 2, b = 3;
619     float c = 4;
620     arrayOp!(float[], const(float)[], const(float)[], "*", float, "+", "=")(res[], a[], b[], c);
621     foreach (v; res[])
622         assert(v == 2 * 3 + 4);
623 }
624 
625 unittest
626 {
627     // https://issues.dlang.org/show_bug.cgi?id=17964
bug()628     uint bug(){
629         uint[] a = [1, 2, 3, 5, 6, 7];
630         uint[] b = [1, 2, 3, 5, 6, 7];
631         a[] |= ~b[];
632         return a[1];
633     }
634     enum x = bug();
635 }
636 
637 // https://issues.dlang.org/show_bug.cgi?id=19796
638 unittest
639 {
640     double[] data = [0.5];
641     double[] result;
642     result.length = data.length;
643     result[] = -data[];
644     assert(result[0] == -0.5);
645 }
646 
647 // https://issues.dlang.org/show_bug.cgi?id=21110
648 unittest
649 {
650     import core.exception;
651 
652     static void assertThrown(T : Throwable, E)(lazy E expression, string msg)
653     {
654         try
655             expression;
656         catch (T)
657             return;
658         assert(0, "msg");
659     }
660 
661     int[] dst;
662     int[] a;
663     int[] b;
664     a.length = 3;
665     b.length = 3;
666     dst.length = 4;
667 
func()668     void func() { dst[] = a[] + b[]; }
669     assertThrown!AssertError(func(), "Array operations with mismatched lengths must throw an error");
670 }
671