1 module core.internal.arrayop;
2 import core.internal.traits : Filter, Unqual;
3
4 version (GNU) version = GNU_OR_LDC;
5 version (LDC) version = GNU_OR_LDC;
6
7 /**
8 * Perform array (vector) operations and store the result in `res`. Operand
9 * types and operations are passed as template arguments in Reverse Polish
10 * Notation (RPN).
11
12 * Operands can be slices or scalar types. The unqualified element types of all
13 * slices must be `T`, scalar types must be implicitly convertible to `T`.
14 *
15 * Operations are encoded as strings, e.g. `"+"`, `"%"`, `"*="`. Unary
16 * operations are prefixed with "u", e.g. `"u-"`, `"u~"`. Only the last
17 * operation can and must be an assignment (`"="`) or op-assignment (`"op="`).
18 *
19 * All slice operands must have the same length as the result slice.
20 *
21 * Params: T[] = type of result slice
22 * Args = operand types and operations in RPN
23 * res = the slice in which to store the results
24 * args = operand values
25 *
26 * Returns: the slice containing the result
27 */
28 T[] arrayOp(T : T[], Args...)(T[] res, Filter!(isType, Args) args) @trusted @nogc pure nothrow
29 {
30 enum check = opsSupported!(true, T, Filter!(not!isType, Args)); // must support all scalar ops
31
32 size_t pos;
33 static if (vectorizeable!(T[], Args))
34 {
35 alias vec = .vec!T;
36 alias load = .load!(T, vec.length);
37 alias store = .store!(T, vec.length);
38
39 // Given that there are at most as many scalars broadcast as there are
40 // operations in any `ary[] = ary[] op const op const`, it should always be
41 // worthwhile to choose vector operations.
42 if (res.length >= vec.length)
43 {
44 mixin(initScalarVecs!Args);
45
46 auto n = res.length / vec.length;
47 do
48 {
49 mixin(vectorExp!Args ~ ";");
50 pos += vec.length;
51 }
52 while (--n);
53 }
54 }
55 for (; pos < res.length; ++pos)
56 mixin(scalarExp!Args ~ ";");
57
58 return res;
59 }
60
61 private:
62
63 // SIMD helpers
64
version(DigitalMars)65 version (DigitalMars)
66 {
67 import core.simd;
68
69 template vec(T)
70 {
71 enum regsz = 16; // SSE2
72 enum N = regsz / T.sizeof;
73 alias vec = __vector(T[N]);
74 }
75
76 void store(T, size_t N)(T* p, in __vector(T[N]) val)
77 {
78 pragma(inline, true);
79 alias vec = __vector(T[N]);
80
81 static if (is(T == float))
82 cast(void) __simd_sto(XMM.STOUPS, *cast(vec*) p, val);
83 else static if (is(T == double))
84 cast(void) __simd_sto(XMM.STOUPD, *cast(vec*) p, val);
85 else
86 cast(void) __simd_sto(XMM.STODQU, *cast(vec*) p, val);
87 }
88
89 const(__vector(T[N])) load(T, size_t N)(in T* p)
90 {
91 import core.simd;
92
93 pragma(inline, true);
94 alias vec = __vector(T[N]);
95
96 static if (is(T == float))
97 return __simd(XMM.LODUPS, *cast(const vec*) p);
98 else static if (is(T == double))
99 return __simd(XMM.LODUPD, *cast(const vec*) p);
100 else
101 return __simd(XMM.LODDQU, *cast(const vec*) p);
102 }
103
104 __vector(T[N]) binop(string op, T, size_t N)(in __vector(T[N]) a, in __vector(T[N]) b)
105 {
106 pragma(inline, true);
107 return mixin("a " ~ op ~ " b");
108 }
109
110 __vector(T[N]) unaop(string op, T, size_t N)(in __vector(T[N]) a)
111 if (op[0] == 'u')
112 {
113 pragma(inline, true);
114 return mixin(op[1 .. $] ~ "a");
115 }
116 }
117
118 // mixin gen
119
120 // Check whether operations `ops` are supported for type `T`. Fails with a human-friendly static assert message, if `fail` is true.
121 template opsSupported(bool fail, T, ops...) if (ops.length > 1)
122 {
123 enum opsSupported = opsSupported!(fail, T, ops[0 .. $ / 2])
124 && opsSupported!(fail, T, ops[$ / 2 .. $]);
125 }
126
opsSupported(bool fail,T,string op)127 template opsSupported(bool fail, T, string op)
128 {
129 static if (isUnaryOp(op))
130 {
131 enum opsSupported = is(typeof((T a) => mixin(op[1 .. $] ~ " a")));
132 static assert(!fail || opsSupported,
133 "Unary op `" ~ op[1 .. $] ~ "` not supported for element type " ~ T.stringof ~ ".");
134 }
135 else
136 {
137 enum opsSupported = is(typeof((T a, T b) => mixin("a " ~ op ~ " b")));
138 static assert(!fail || opsSupported,
139 "Binary op `" ~ op ~ "` not supported for element type " ~ T.stringof ~ ".");
140 }
141 }
142
143 // check whether slices have the unqualified element type `E` and scalars are implicitly convertible to `E`
144 // i.e. filter out things like float[] = float[] / size_t[]
145 enum compatibleVecTypes(E, T : T[]) = is(Unqual!T == Unqual!E); // array elem types must be same (maybe add cvtpi2ps)
146 enum compatibleVecTypes(E, T) = is(T : E); // scalar must be convertible to target elem type
147 enum compatibleVecTypes(E, Types...) = compatibleVecTypes!(E, Types[0 .. $ / 2])
148 && compatibleVecTypes!(E, Types[$ / 2 .. $]);
149
version(GNU_OR_LDC)150 version (GNU_OR_LDC)
151 {
152 // leave it to the auto-vectorizer
153 enum vectorizeable(E : E[], Args...) = false;
154 }
155 else
156 {
157 // check whether arrayOp is vectorizable
158 template vectorizeable(E : E[], Args...)
159 {
160 static if (is(vec!E))
161 enum vectorizeable = opsSupported!(false, vec!E, Filter!(not!isType, Args))
162 && compatibleVecTypes!(E, Filter!(isType, Args));
163 else
164 enum vectorizeable = false;
165 }
166
version(X86_64)167 version (X86_64) unittest
168 {
169 static assert(vectorizeable!(double[], const(double)[], double[], "+", "="));
170 static assert(!vectorizeable!(double[], const(ulong)[], double[], "+", "="));
171 }
172 }
173
isUnaryOp(string op)174 bool isUnaryOp(string op)
175 {
176 return op[0] == 'u';
177 }
178
isBinaryOp(string op)179 bool isBinaryOp(string op)
180 {
181 if (op == "^^")
182 return true;
183 if (op.length != 1)
184 return false;
185 switch (op[0])
186 {
187 case '+', '-', '*', '/', '%', '|', '&', '^':
188 return true;
189 default:
190 return false;
191 }
192 }
193
isBinaryAssignOp(string op)194 bool isBinaryAssignOp(string op)
195 {
196 return op.length >= 2 && op[$ - 1] == '=' && isBinaryOp(op[0 .. $ - 1]);
197 }
198
199 // Generate mixin expression to perform scalar arrayOp loop expression, assumes
200 // `pos` to be the current slice index, `args` to contain operand values, and
201 // `res` the target slice.
scalarExp(Args...)202 string scalarExp(Args...)()
203 {
204 string[] stack;
205 size_t argsIdx;
206 foreach (i, arg; Args)
207 {
208 static if (is(arg == T[], T))
209 stack ~= "args[" ~ argsIdx++.toString ~ "][pos]";
210 else static if (is(arg))
211 stack ~= "args[" ~ argsIdx++.toString ~ "]";
212 else static if (isUnaryOp(arg))
213 {
214 auto op = arg[0] == 'u' ? arg[1 .. $] : arg;
215 stack[$ - 1] = op ~ stack[$ - 1];
216 }
217 else static if (arg == "=")
218 {
219 stack[$ - 1] = "res[pos] = cast(T)(" ~ stack[$ - 1] ~ ")";
220 }
221 else static if (isBinaryAssignOp(arg))
222 {
223 stack[$ - 1] = "res[pos] " ~ arg ~ " cast(T)(" ~ stack[$ - 1] ~ ")";
224 }
225 else static if (isBinaryOp(arg))
226 {
227 stack[$ - 2] = "(cast(T)(" ~ stack[$ - 2] ~ " " ~ arg ~ " " ~ stack[$ - 1] ~ "))";
228 stack.length -= 1;
229 }
230 else
231 assert(0, "Unexpected op " ~ arg);
232 }
233 assert(stack.length == 1);
234 return stack[0];
235 }
236
237 // Generate mixin statement to perform vector loop initialization, assumes
238 // `args` to contain operand values.
initScalarVecs(Args...)239 string initScalarVecs(Args...)()
240 {
241 size_t scalarsIdx;
242 string res;
243 foreach (aidx, arg; Args)
244 {
245 static if (is(arg == T[], T))
246 {
247 }
248 else static if (is(arg))
249 res ~= "immutable vec scalar" ~ scalarsIdx++.toString ~ " = args["
250 ~ aidx.toString ~ "];\n";
251 }
252 return res;
253 }
254
255 // Generate mixin expression to perform vector arrayOp loop expression, assumes
256 // `pos` to be the current slice index, `args` to contain operand values, and
257 // `res` the target slice.
vectorExp(Args...)258 string vectorExp(Args...)()
259 {
260 size_t scalarsIdx, argsIdx;
261 string[] stack;
262 foreach (i, arg; Args)
263 {
264 static if (is(arg == T[], T))
265 stack ~= "load(&args[" ~ argsIdx++.toString ~ "][pos])";
266 else static if (is(arg))
267 {
268 ++argsIdx;
269 stack ~= "scalar" ~ scalarsIdx++.toString;
270 }
271 else static if (isUnaryOp(arg))
272 {
273 auto op = arg[0] == 'u' ? arg[1 .. $] : arg;
274 stack[$ - 1] = "unaop!\"" ~ arg ~ "\"(" ~ stack[$ - 1] ~ ")";
275 }
276 else static if (arg == "=")
277 {
278 stack[$ - 1] = "store(&res[pos], " ~ stack[$ - 1] ~ ")";
279 }
280 else static if (isBinaryAssignOp(arg))
281 {
282 stack[$ - 1] = "store(&res[pos], binop!\"" ~ arg[0 .. $ - 1]
283 ~ "\"(load(&res[pos]), " ~ stack[$ - 1] ~ "))";
284 }
285 else static if (isBinaryOp(arg))
286 {
287 stack[$ - 2] = "binop!\"" ~ arg ~ "\"(" ~ stack[$ - 2] ~ ", " ~ stack[$ - 1] ~ ")";
288 stack.length -= 1;
289 }
290 else
291 assert(0, "Unexpected op " ~ arg);
292 }
293 assert(stack.length == 1);
294 return stack[0];
295 }
296
297 // other helpers
298
299 enum isType(T) = true;
300 enum isType(alias a) = false;
not(alias tmlp)301 template not(alias tmlp)
302 {
303 enum not(Args...) = !tmlp!Args;
304 }
305
toString(size_t num)306 string toString(size_t num)
307 {
308 import core.internal.string : unsignedToTempString;
309
310 char[20] buf = void;
311 return unsignedToTempString(num, buf).idup;
312 }
313
contains(T)314 bool contains(T)(in T[] ary, in T[] vals...)
315 {
316 foreach (v1; ary)
317 foreach (v2; vals)
318 if (v1 == v2)
319 return true;
320 return false;
321 }
322
323 // tests
324
version(unittest)325 version (unittest) template TT(T...)
326 {
327 alias TT = T;
328 }
329
version(unittest)330 version (unittest) template _arrayOp(Args...)
331 {
332 alias _arrayOp = arrayOp!Args;
333 }
334
335 unittest
336 {
check(string op,TA,TB,T,size_t N)337 static void check(string op, TA, TB, T, size_t N)(TA a, TB b, in ref T[N] exp)
338 {
339 T[N] res;
340 _arrayOp!(T[], TA, TB, op, "=")(res[], a, b);
341 foreach (i; 0 .. N)
342 assert(res[i] == exp[i]);
343 }
344
check2(string unaOp,string binOp,TA,TB,T,size_t N)345 static void check2(string unaOp, string binOp, TA, TB, T, size_t N)(TA a, TB b, in ref T[N] exp)
346 {
347 T[N] res;
348 _arrayOp!(T[], TA, TB, unaOp, binOp, "=")(res[], a, b);
349 foreach (i; 0 .. N)
350 assert(res[i] == exp[i]);
351 }
352
353 static void test(T, string op, size_t N = 16)(T a, T b, T exp)
354 {
355 T[N] va = a, vb = b, vexp = exp;
356
357 check!op(va[], vb[], vexp);
358 check!op(va[], b, vexp);
359 check!op(a, vb[], vexp);
360 }
361
362 static void test2(T, string unaOp, string binOp, size_t N = 16)(T a, T b, T exp)
363 {
364 T[N] va = a, vb = b, vexp = exp;
365
366 check2!(unaOp, binOp)(va[], vb[], vexp);
367 check2!(unaOp, binOp)(va[], b, vexp);
368 check2!(unaOp, binOp)(a, vb[], vexp);
369 }
370
371 alias UINTS = TT!(ubyte, ushort, uint, ulong);
372 alias INTS = TT!(byte, short, int, long);
373 alias FLOATS = TT!(float, double);
374
375 foreach (T; TT!(UINTS, INTS, FLOATS))
376 {
377 test!(T, "+")(1, 2, 3);
378 test!(T, "-")(3, 2, 1);
379 static if (__traits(compiles, { import std.math; }))
380 test!(T, "^^")(2, 3, 8);
381
382 test2!(T, "u-", "+")(3, 2, 1);
383 }
384
385 foreach (T; TT!(UINTS, INTS))
386 {
387 test!(T, "|")(1, 2, 3);
388 test!(T, "&")(3, 1, 1);
389 test!(T, "^")(3, 1, 2);
390
391 test2!(T, "u~", "+")(3, cast(T)~2, 5);
392 }
393
394 foreach (T; TT!(INTS, FLOATS))
395 {
396 test!(T, "-")(1, 2, -1);
397 test2!(T, "u-", "+")(-3, -2, -1);
398 test2!(T, "u-", "*")(-3, -2, -6);
399 }
400
401 foreach (T; TT!(UINTS, INTS, FLOATS))
402 {
403 test!(T, "*")(2, 3, 6);
404 test!(T, "/")(8, 4, 2);
405 test!(T, "%")(8, 6, 2);
406 }
407 }
408
409 // test handling of v op= exp
410 unittest
411 {
412 uint[32] c;
413 arrayOp!(uint[], uint, "+=")(c[], 2);
414 foreach (v; c)
415 assert(v == 2);
416 static if (__traits(compiles, { import std.math; }))
417 {
418 arrayOp!(uint[], uint, "^^=")(c[], 3);
419 foreach (v; c)
420 assert(v == 8);
421 }
422 }
423
424 // proper error message for UDT lacking certain ops
425 unittest
426 {
427 static assert(!is(typeof(&arrayOp!(int[4][], int[4], "+="))));
428 static assert(!is(typeof(&arrayOp!(int[4][], int[4], "u-", "="))));
429
430 static struct S
431 {
432 }
433
434 static assert(!is(typeof(&arrayOp!(S[], S, "+="))));
435 static assert(!is(typeof(&arrayOp!(S[], S[], "*", S, "+="))));
436 static struct S2
437 {
opBinaryS2438 S2 opBinary(string op)(in S2) @nogc pure nothrow
439 {
440 return this;
441 }
442
opOpAssignS2443 ref S2 opOpAssign(string op)(in S2) @nogc pure nothrow
444 {
445 return this;
446 }
447 }
448
449 static assert(is(typeof(&arrayOp!(S2[], S2[], S2[], S2, "*", "+", "="))));
450 static assert(is(typeof(&arrayOp!(S2[], S2[], S2, "*", "+="))));
451 }
452