1 #define LLVM_LIBC_USE_BUILTIN_MEMCPY_INLINE 0
2 #define LLVM_LIBC_USE_BUILTIN_MEMSET_INLINE 0
3 
4 #include "utils/UnitTest/Test.h"
5 #include <src/__support/CPP/Array.h>
6 #include <src/string/memory_utils/algorithm.h>
7 #include <src/string/memory_utils/backends.h>
8 
9 #include <sstream>
10 
11 namespace __llvm_libc {
12 
13 struct alignas(64) Buffer : cpp::Array<char, 128> {
14   bool contains(const char *ptr) const {
15     return ptr >= data() && ptr < (data() + size());
16   }
17   size_t getOffset(const char *ptr) const { return ptr - data(); }
18   void fill(char c) {
19     for (auto itr = begin(); itr != end(); ++itr)
20       *itr = c;
21   }
22 };
23 
24 static Buffer buffer1;
25 static Buffer buffer2;
26 static std::ostringstream LOG;
27 
28 struct TestBackend {
29   static constexpr bool IS_BACKEND_TYPE = true;
30 
31   template <typename T> static void log(const char *Action, const char *ptr) {
32     LOG << Action << "<" << sizeof(T) << "> ";
33     if (buffer1.contains(ptr))
34       LOG << "a[" << buffer1.getOffset(ptr) << "]";
35     else if (buffer2.contains(ptr))
36       LOG << "b[" << buffer2.getOffset(ptr) << "]";
37     LOG << "\n";
38   }
39 
40   template <typename T, Temporality TS, Aligned AS>
41   static T load(const T *src) {
42     log<T>((AS == Aligned::YES ? "LdA" : "LdU"),
43            reinterpret_cast<const char *>(src));
44     return Scalar64BitBackend::load<T, TS, AS>(src);
45   }
46 
47   template <typename T, Temporality TS, Aligned AS>
48   static void store(T *dst, T value) {
49     log<T>((AS == Aligned::YES ? "StA" : "StU"),
50            reinterpret_cast<const char *>(dst));
51     Scalar64BitBackend::store<T, TS, AS>(dst, value);
52   }
53 
54   template <typename T> static inline T splat(ubyte value) {
55     LOG << "Splat<" << sizeof(T) << "> " << (unsigned)value << '\n';
56     return Scalar64BitBackend::splat<T>(value);
57   }
58 
59   template <typename T> static inline uint64_t notEquals(T v1, T v2) {
60     LOG << "Neq<" << sizeof(T) << ">\n";
61     return Scalar64BitBackend::notEquals<T>(v1, v2);
62   }
63 
64   template <typename T> static inline int32_t threeWayCmp(T v1, T v2) {
65     LOG << "Diff<" << sizeof(T) << ">\n";
66     return Scalar64BitBackend::threeWayCmp<T>(v1, v2);
67   }
68 
69   template <size_t Size>
70   using getNextType = Scalar64BitBackend::getNextType<Size>;
71 };
72 
73 struct LlvmLibcAlgorithm : public testing::Test {
74   void SetUp() override {
75     LOG = std::ostringstream();
76     LOG << '\n';
77   }
78 
79   void fillEqual() {
80     buffer1.fill('a');
81     buffer2.fill('a');
82   }
83 
84   void fillDifferent() {
85     buffer1.fill('a');
86     buffer2.fill('b');
87   }
88 
89   const char *getTrace() {
90     trace_ = LOG.str();
91     return trace_.c_str();
92   }
93 
94   const char *stripComments(const char *expected) {
95     expected_.clear();
96     std::stringstream ss(expected);
97     std::string line;
98     while (std::getline(ss, line, '\n')) {
99       const auto pos = line.find('#');
100       if (pos == std::string::npos) {
101         expected_ += line;
102       } else {
103         auto log = line.substr(0, pos);
104         while (!log.empty() && std::isspace(log.back()))
105           log.pop_back();
106         expected_ += log;
107       }
108       expected_ += '\n';
109     }
110     return expected_.c_str();
111   }
112 
113   template <size_t Align = 1> SrcAddr<Align> buf1(size_t offset = 0) const {
114     return buffer1.data() + offset;
115   }
116   template <size_t Align = 1> SrcAddr<Align> buf2(size_t offset = 0) const {
117     return buffer2.data() + offset;
118   }
119   template <size_t Align = 1> DstAddr<Align> dst(size_t offset = 0) const {
120     return buffer1.data() + offset;
121   }
122   template <size_t Align = 1> SrcAddr<Align> src(size_t offset = 0) const {
123     return buffer2.data() + offset;
124   }
125 
126 private:
127   std::string trace_;
128   std::string expected_;
129 };
130 
131 using _8 = SizedOp<TestBackend, 8>;
132 
133 ///////////////////////////////////////////////////////////////////////////////
134 //// Testing fixed fized forward operations
135 ///////////////////////////////////////////////////////////////////////////////
136 
137 ///////////////////////////////////////////////////////////////////////////////
138 // Copy
139 
140 TEST_F(LlvmLibcAlgorithm, copy_1) {
141   SizedOp<TestBackend, 1>::copy(dst(), src());
142   EXPECT_STREQ(getTrace(), stripComments(R"(
143 LdU<1> b[0]
144 StU<1> a[0]
145 )"));
146 }
147 
148 TEST_F(LlvmLibcAlgorithm, copy_15) {
149   SizedOp<TestBackend, 15>::copy(dst(), src());
150   EXPECT_STREQ(getTrace(), stripComments(R"(
151 LdU<8> b[0]
152 StU<8> a[0]
153 LdU<4> b[8]
154 StU<4> a[8]
155 LdU<2> b[12]
156 StU<2> a[12]
157 LdU<1> b[14]
158 StU<1> a[14]
159 )"));
160 }
161 
162 TEST_F(LlvmLibcAlgorithm, copy_16) {
163   SizedOp<TestBackend, 16>::copy(dst(), src());
164   EXPECT_STREQ(getTrace(), stripComments(R"(
165 LdU<8> b[0]
166 StU<8> a[0]
167 LdU<8> b[8]
168 StU<8> a[8]
169 )"));
170 }
171 
172 ///////////////////////////////////////////////////////////////////////////////
173 // Move
174 
175 TEST_F(LlvmLibcAlgorithm, move_1) {
176   SizedOp<TestBackend, 1>::move(dst(), src());
177   EXPECT_STREQ(getTrace(), stripComments(R"(
178 LdU<1> b[0]
179 StU<1> a[0]
180 )"));
181 }
182 
183 TEST_F(LlvmLibcAlgorithm, move_15) {
184   SizedOp<TestBackend, 15>::move(dst(), src());
185   EXPECT_STREQ(getTrace(), stripComments(R"(
186 LdU<8> b[0]
187 LdU<4> b[8]
188 LdU<2> b[12]
189 LdU<1> b[14]
190 StU<1> a[14]
191 StU<2> a[12]
192 StU<4> a[8]
193 StU<8> a[0]
194 )"));
195 }
196 
197 TEST_F(LlvmLibcAlgorithm, move_16) {
198   SizedOp<TestBackend, 16>::move(dst(), src());
199   EXPECT_STREQ(getTrace(), stripComments(R"(
200 LdU<8> b[0]
201 LdU<8> b[8]
202 StU<8> a[8]
203 StU<8> a[0]
204 )"));
205 }
206 
207 ///////////////////////////////////////////////////////////////////////////////
208 // set
209 
210 TEST_F(LlvmLibcAlgorithm, set_1) {
211   SizedOp<TestBackend, 1>::set(dst(), ubyte{42});
212   EXPECT_STREQ(getTrace(), stripComments(R"(
213 Splat<1> 42
214 StU<1> a[0]
215 )"));
216 }
217 
218 TEST_F(LlvmLibcAlgorithm, set_15) {
219   SizedOp<TestBackend, 15>::set(dst(), ubyte{42});
220   EXPECT_STREQ(getTrace(), stripComments(R"(
221 Splat<8> 42
222 StU<8> a[0]
223 Splat<4> 42
224 StU<4> a[8]
225 Splat<2> 42
226 StU<2> a[12]
227 Splat<1> 42
228 StU<1> a[14]
229 )"));
230 }
231 
232 TEST_F(LlvmLibcAlgorithm, set_16) {
233   SizedOp<TestBackend, 16>::set(dst(), ubyte{42});
234   EXPECT_STREQ(getTrace(), stripComments(R"(
235 Splat<8> 42
236 StU<8> a[0]
237 Splat<8> 42
238 StU<8> a[8]
239 )"));
240 }
241 
242 ///////////////////////////////////////////////////////////////////////////////
243 // different
244 
245 TEST_F(LlvmLibcAlgorithm, different_1) {
246   fillEqual();
247   SizedOp<TestBackend, 1>::isDifferent(buf1(), buf2());
248   EXPECT_STREQ(getTrace(), stripComments(R"(
249 LdU<1> a[0]
250 LdU<1> b[0]
251 Neq<1>
252 )"));
253 }
254 
255 TEST_F(LlvmLibcAlgorithm, different_15) {
256   fillEqual();
257   SizedOp<TestBackend, 15>::isDifferent(buf1(), buf2());
258   EXPECT_STREQ(getTrace(), stripComments(R"(
259 LdU<8> a[0]
260 LdU<8> b[0]
261 Neq<8>
262 LdU<4> a[8]
263 LdU<4> b[8]
264 Neq<4>
265 LdU<2> a[12]
266 LdU<2> b[12]
267 Neq<2>
268 LdU<1> a[14]
269 LdU<1> b[14]
270 Neq<1>
271 )"));
272 }
273 
274 TEST_F(LlvmLibcAlgorithm, different_15_no_shortcircuit) {
275   fillDifferent();
276   SizedOp<TestBackend, 15>::isDifferent(buf1(), buf2());
277   // If buffer compare isDifferent we continue to aggregate.
278   EXPECT_STREQ(getTrace(), stripComments(R"(
279 LdU<8> a[0]
280 LdU<8> b[0]
281 Neq<8>
282 LdU<4> a[8]
283 LdU<4> b[8]
284 Neq<4>
285 LdU<2> a[12]
286 LdU<2> b[12]
287 Neq<2>
288 LdU<1> a[14]
289 LdU<1> b[14]
290 Neq<1>
291 )"));
292 }
293 
294 TEST_F(LlvmLibcAlgorithm, different_16) {
295   fillEqual();
296   SizedOp<TestBackend, 16>::isDifferent(buf1(), buf2());
297   EXPECT_STREQ(getTrace(), stripComments(R"(
298 LdU<8> a[0]
299 LdU<8> b[0]
300 Neq<8>
301 LdU<8> a[8]
302 LdU<8> b[8]
303 Neq<8>
304 )"));
305 }
306 
307 ///////////////////////////////////////////////////////////////////////////////
308 // three_way_cmp
309 
310 TEST_F(LlvmLibcAlgorithm, three_way_cmp_eq_1) {
311   fillEqual();
312   SizedOp<TestBackend, 1>::threeWayCmp(buf1(), buf2());
313   // Buffer compare equal, returning 0 and no call to Diff.
314   EXPECT_STREQ(getTrace(), stripComments(R"(
315 LdU<1> a[0]
316 LdU<1> b[0]
317 Diff<1>
318 )"));
319 }
320 
321 TEST_F(LlvmLibcAlgorithm, three_way_cmp_eq_15) {
322   fillEqual();
323   SizedOp<TestBackend, 15>::threeWayCmp(buf1(), buf2());
324   // Buffer compare equal, returning 0 and no call to Diff.
325   EXPECT_STREQ(getTrace(), stripComments(R"(
326 LdU<8> a[0]
327 LdU<8> b[0]
328 Diff<8>
329 LdU<4> a[8]
330 LdU<4> b[8]
331 Diff<4>
332 LdU<2> a[12]
333 LdU<2> b[12]
334 Diff<2>
335 LdU<1> a[14]
336 LdU<1> b[14]
337 Diff<1>
338 )"));
339 }
340 
341 TEST_F(LlvmLibcAlgorithm, three_way_cmp_neq_15_shortcircuit) {
342   fillDifferent();
343   SizedOp<TestBackend, 16>::threeWayCmp(buf1(), buf2());
344   // If buffer compare isDifferent we stop early.
345   EXPECT_STREQ(getTrace(), stripComments(R"(
346 LdU<8> a[0]
347 LdU<8> b[0]
348 Diff<8>
349 )"));
350 }
351 
352 TEST_F(LlvmLibcAlgorithm, three_way_cmp_eq_16) {
353   fillEqual();
354   SizedOp<TestBackend, 16>::threeWayCmp(buf1(), buf2());
355   // Buffer compare equal, returning 0 and no call to Diff.
356   EXPECT_STREQ(getTrace(), stripComments(R"(
357 LdU<8> a[0]
358 LdU<8> b[0]
359 Diff<8>
360 LdU<8> a[8]
361 LdU<8> b[8]
362 Diff<8>
363 )"));
364 }
365 
366 ///////////////////////////////////////////////////////////////////////////////
367 //// Testing skip operations
368 ///////////////////////////////////////////////////////////////////////////////
369 
370 TEST_F(LlvmLibcAlgorithm, skip_and_set) {
371   Skip<11>::Then<SizedOp<TestBackend, 1>>::set(dst(), ubyte{42});
372   EXPECT_STREQ(getTrace(), stripComments(R"(
373 Splat<1> 42
374 StU<1> a[11]
375 )"));
376 }
377 
378 TEST_F(LlvmLibcAlgorithm, skip_and_different_1) {
379   Skip<11>::Then<SizedOp<TestBackend, 1>>::isDifferent(buf1(), buf2());
380   EXPECT_STREQ(getTrace(), stripComments(R"(
381 LdU<1> a[11]
382 LdU<1> b[11]
383 Neq<1>
384 )"));
385 }
386 
387 TEST_F(LlvmLibcAlgorithm, skip_and_three_way_cmp_8) {
388   Skip<11>::Then<SizedOp<TestBackend, 1>>::threeWayCmp(buf1(), buf2());
389   EXPECT_STREQ(getTrace(), stripComments(R"(
390 LdU<1> a[11]
391 LdU<1> b[11]
392 Diff<1>
393 )"));
394 }
395 
396 ///////////////////////////////////////////////////////////////////////////////
397 //// Testing tail operations
398 ///////////////////////////////////////////////////////////////////////////////
399 
400 TEST_F(LlvmLibcAlgorithm, tail_copy_8) {
401   Tail<_8>::copy(dst(), src(), 16);
402   EXPECT_STREQ(getTrace(), stripComments(R"(
403 LdU<8> b[8]
404 StU<8> a[8]
405 )"));
406 }
407 
408 TEST_F(LlvmLibcAlgorithm, tail_move_8) {
409   Tail<_8>::move(dst(), src(), 16);
410   EXPECT_STREQ(getTrace(), stripComments(R"(
411 LdU<8> b[8]
412 StU<8> a[8]
413 )"));
414 }
415 
416 TEST_F(LlvmLibcAlgorithm, tail_set_8) {
417   Tail<_8>::set(dst(), ubyte{42}, 16);
418   EXPECT_STREQ(getTrace(), stripComments(R"(
419 Splat<8> 42
420 StU<8> a[8]
421 )"));
422 }
423 
424 TEST_F(LlvmLibcAlgorithm, tail_different_8) {
425   fillEqual();
426   Tail<_8>::isDifferent(buf1(), buf2(), 16);
427   EXPECT_STREQ(getTrace(), stripComments(R"(
428 LdU<8> a[8]
429 LdU<8> b[8]
430 Neq<8>
431 )"));
432 }
433 
434 TEST_F(LlvmLibcAlgorithm, tail_three_way_cmp_8) {
435   fillEqual();
436   Tail<_8>::threeWayCmp(buf1(), buf2(), 16);
437   EXPECT_STREQ(getTrace(), stripComments(R"(
438 LdU<8> a[8]
439 LdU<8> b[8]
440 Diff<8>
441 )"));
442 }
443 
444 ///////////////////////////////////////////////////////////////////////////////
445 //// Testing HeadTail operations
446 ///////////////////////////////////////////////////////////////////////////////
447 
448 TEST_F(LlvmLibcAlgorithm, head_tail_copy_8) {
449   HeadTail<_8>::copy(dst(), src(), 16);
450   EXPECT_STREQ(getTrace(), stripComments(R"(
451 LdU<8> b[0]
452 StU<8> a[0]
453 LdU<8> b[8]
454 StU<8> a[8]
455 )"));
456 }
457 
458 ///////////////////////////////////////////////////////////////////////////////
459 //// Testing Loop operations
460 ///////////////////////////////////////////////////////////////////////////////
461 
462 TEST_F(LlvmLibcAlgorithm, loop_copy_one_iteration_and_tail) {
463   Loop<_8>::copy(dst(), src(), 10);
464   EXPECT_STREQ(getTrace(), stripComments(R"(
465 LdU<8> b[0]
466 StU<8> a[0] # covers 0-7
467 LdU<8> b[2]
468 StU<8> a[2] # covers 2-9
469 )"));
470 }
471 
472 TEST_F(LlvmLibcAlgorithm, loop_copy_two_iteration_and_tail) {
473   Loop<_8>::copy(dst(), src(), 17);
474   EXPECT_STREQ(getTrace(), stripComments(R"(
475 LdU<8> b[0]
476 StU<8> a[0] # covers 0-7
477 LdU<8> b[8]
478 StU<8> a[8] # covers 8-15
479 LdU<8> b[9]
480 StU<8> a[9] # covers 9-16
481 )"));
482 }
483 
484 TEST_F(LlvmLibcAlgorithm, loop_with_one_turn_is_inefficient_but_ok) {
485   Loop<_8>::copy(dst(), src(), 8);
486   EXPECT_STREQ(getTrace(), stripComments(R"(
487 LdU<8> b[0]
488 StU<8> a[0] # first iteration covers 0-7
489 LdU<8> b[0] # tail also covers 0-7 but since Loop is supposed to be used
490 StU<8> a[0] # with a sufficient number of iterations the tail cost is amortised
491 )"));
492 }
493 
494 TEST_F(LlvmLibcAlgorithm, loop_with_round_number_of_turn) {
495   Loop<_8>::copy(dst(), src(), 24);
496   EXPECT_STREQ(getTrace(), stripComments(R"(
497 LdU<8> b[0]
498 StU<8> a[0] # first iteration covers 0-7
499 LdU<8> b[8]
500 StU<8> a[8] # second iteration covers 8-15
501 LdU<8> b[16]
502 StU<8> a[16]
503 )"));
504 }
505 
506 TEST_F(LlvmLibcAlgorithm, dst_aligned_loop) {
507   Loop<_8>::copy(dst<16>(), src(), 23);
508   EXPECT_STREQ(getTrace(), stripComments(R"(
509 LdU<8> b[0]
510 StA<8> a[0] # store is aligned on 16B
511 LdU<8> b[8]
512 StA<8> a[8] # subsequent stores are aligned
513 LdU<8> b[15]
514 StU<8> a[15] # Tail is always unaligned
515 )"));
516 }
517 
518 TEST_F(LlvmLibcAlgorithm, aligned_loop) {
519   Loop<_8>::copy(dst<16>(), src<8>(), 23);
520   EXPECT_STREQ(getTrace(), stripComments(R"(
521 LdA<8> b[0] # load is aligned on 8B
522 StA<8> a[0] # store is aligned on 16B
523 LdA<8> b[8] # subsequent loads are aligned
524 StA<8> a[8] # subsequent stores are aligned
525 LdU<8> b[15] # Tail is always unaligned
526 StU<8> a[15] # Tail is always unaligned
527 )"));
528 }
529 
530 ///////////////////////////////////////////////////////////////////////////////
531 //// Testing Align operations
532 ///////////////////////////////////////////////////////////////////////////////
533 
534 TEST_F(LlvmLibcAlgorithm, align_dst_copy_8) {
535   Align<_8, Arg::Dst>::Then<Loop<_8>>::copy(dst(2), src(3), 31);
536   EXPECT_STREQ(getTrace(), stripComments(R"(
537 LdU<8> b[3]
538 StU<8> a[2] # First store covers unaligned bytes
539 LdU<8> b[9]
540 StA<8> a[8] # First aligned store
541 LdU<8> b[17]
542 StA<8> a[16] # Subsequent stores are aligned
543 LdU<8> b[25]
544 StA<8> a[24] # Subsequent stores are aligned
545 LdU<8> b[26]
546 StU<8> a[25] # Last store covers remaining bytes
547 )"));
548 }
549 
550 TEST_F(LlvmLibcAlgorithm, align_src_copy_8) {
551   Align<_8, Arg::Src>::Then<Loop<_8>>::copy(dst(2), src(3), 31);
552   EXPECT_STREQ(getTrace(), stripComments(R"(
553 LdU<8> b[3] # First load covers unaligned bytes
554 StU<8> a[2]
555 LdA<8> b[8] # First aligned load
556 StU<8> a[7]
557 LdA<8> b[16] # Subsequent loads are aligned
558 StU<8> a[15]
559 LdA<8> b[24] # Subsequent loads are aligned
560 StU<8> a[23]
561 LdU<8> b[26] # Last load covers remaining bytes
562 StU<8> a[25]
563 )"));
564 }
565 
566 } // namespace __llvm_libc
567