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