This repository was archived by the owner on Aug 14, 2022. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathtpopt2.html
More file actions
1297 lines (1215 loc) · 41 KB
/
Copy pathtpopt2.html
File metadata and controls
1297 lines (1215 loc) · 41 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!doctype html>
<html lang="en">
<head>
<meta charset="utf-8">
<title>Pragmatic optimization in modern programming</title>
<meta name="description" content="Pragmatic optimization in modern programming">
<meta name="author" content="geek">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, minimal-ui">
<link rel="stylesheet" href="css/reveal.css">
<link rel="stylesheet" href="css/theme/beige.css" id="theme">
<link rel="stylesheet" href="css/customization.css">
<!-- Code syntax highlighting -->
<link rel="stylesheet" href="lib/css/zenburn.css">
<!-- <link rel="shortcut icon" href="images/ico/favicon.ico"> -->
<!-- Printing and PDF exports -->
<script>
var link = document.createElement( 'link' );
link.rel = 'stylesheet';
link.type = 'text/css';
link.href = window.location.search.match( /print-pdf/gi ) ? 'css/print/pdf.css' : 'css/print/paper.css';
document.getElementsByTagName( 'head' )[0].appendChild( link );
</script>
<!--[if lt IE 9]>
<script src="lib/js/html5shiv.js"></script>
<![endif]-->
</head>
<body>
<div class="reveal">
<div class="slides">
<section>
<h1>Pragmatic optimization</h1>
<h2>In modern programming</h2>
<h3>Mastering compiler optimizations</h3>
<p>
<small>Created by
<a href="https://github.com/cuda-geek">Marina (geek) Kolpakova</a>
for
<a href="unn.ru">UNN</a>
/ 2015-2016
</small>
</p>
</section>
<section>
<h2>Course Topics</h2>
<ul>
<li>Ordering optimization approaches</li>
<li>Demystifying a compiler</li>
<li><b>Mastering compiler optimizations</b></li>
<li>Modern computer architectures concepts</li>
</ul>
</section>
<section>
<h2>Outline</h2>
<ul>
<li>Constant folding</li>
<li>Hoisting loop invariant code</li>
<li>Scalarization</li>
<li>Loop unswitching</li>
<li>Loop peeling and sentinels</li>
<li>Strength reduction</li>
<li>Loop-induction variable elimination</li>
<li>Auto-vectorization</li>
<li>Function body inlining</li>
<li>Built-in detection</li>
<li>Case study</li>
</ul>
</section>
<section>
<h2>Constant folding</h2>
<blockquote>evaluates expressions from constants in compile time</blockquote>
<p>It is one of the simplest and most widely used compiler transformations. Expressions could be quite
complicated, but absence of any kind of side effects is always to be considered.</p>
<pre><code class="cpp">double b = exp(sqrt(M_PI/2));</code></pre>
<p></p>
<pre><code class="armacm"> fldd d17, .L5
// other code
.L5:
.word 2911864813
.word 1074529267</code></pre>
<p>May be performed in global as well as local scope.<br> Applicable to any code pattern.</p>
</section>
<section>
<section>
<h2>Hoisting Loop Invariant Code</h2>
<blockquote>The goal of <b>hoisting</b> — also called <b>loop-invariant code motion</b> — is to avoid recomputing
loop-invariant code each time through the body of a loop.</blockquote>
<pre><code class="cpp">void scale(double* x, double* y, int len)
{
for (int i = 0; i < len; i++)
y[i] = x[i] * exp(sqrt(M_PI/2));
}</code></pre>
<p>... is the same as...</p>
<pre><code class="cpp">void scale(double* x, double *y, int len)
{
double factor = exp(sqrt(M_PI/2));
for (int i = 0; i < len; i++)
y[i] = x[i] * factor;
}</code></pre>
</section>
<section>
<h2>Hoisting Loop Invariant Code</h2>
<pre style="font-size: 0.95em;" class="console">$ gcc -march=armv7-a -mthumb -O1 -S -o 1.s\
-mfpu=neon-vfpv4 -mfloat-abi=softfp 1.c</pre>
<table class="simple" style="font-size:0.95em;">
<colgroup>
<col/>
<col/>
</colgroup>
<tbody>
<tr>
<td>
<pre><code class="armacm"> fldd d17, .L5
.L3:
fldmiad r3!, {d16}
fmuld d16, d16, d17
fstmiad r1!, {d16}
cmp r3, r0
bne .L3
.L1:
bx lr
.L5:
.word 2911864813
.word 1074529267</code></pre>
</td>
<td>
<pre><code class="armasm"> fldd d17, .L11
.L9:
fldmiad r3!, {d16}
fmuld d16, d16, d17
fstmiad r1!, {d16}
cmp r3, r0
bne .L9
.L7:
bx lr
.L11:
.word 2911864813
.word 1074529267</code></pre>
</td>
</tr>
</tbody>
</table>
</section>
<section>
<h2>Hoisting non-constants</h2>
<p>Let's make expression variable</p>
<pre><code class="cpp">void scale(double* x, double* y, int len)
{
for (int i = 0; i < len; i++)
y[i] = x[i] * exp(sqrt((double)len)/2.));
}</code></pre>
<pre><code class="cpp">void scale(double* x, double *y, int len)
{
double factor = exp(sqrt((double)len)/2.));
for (int i = 0; i < len; i++)
y[i] = x[i] * factor;
}</code></pre>
<pre style="font-size: 0.95em;" class="console">$ gcc -march=armv7-a -mthumb -O1 -S -o 1.s\
-mfpu=neon-vfpv4 -mfloat-abi=softfp 1.c</pre>
</section>
<section>
<h2>Hoisting non-constants</h2>
<table class="simple" style="font-size:0.95em;">
<colgroup>
<col/>
<col/>
</colgroup>
<tbody>
<tr>
<td>
<pre><code style="max-height: 490px;" class="armacm"> fmsr s15, r2 @ int
fsitod d9, s15
fsqrtd d9, d9
.L4:
fldmiad r6!, {d8}
fcpyd d16, d9
fcmpd d9, d9
fmstat
beq .L3
fmsr s15, r7 @ int
fsitod d16, s15
fmrrd r0, r1, d16
bl sqrt(PLT)
fmdrr d16, r0, r1
.L3:
fmuld d8, d8, d16
fstmiad r5!, {d8}
adds r4, r4, #1
cmp r4, r7
bne .L4</code></pre>
</td>
<td>
<pre><code style="max-height: 490px;" class="armasm"> fmsr s15, r2 @ int
fsitod d17, s15
fsqrtd d17, d17
fcmpd d17, d17
fmstat
beq .L9
fsitod d16, s15
fmrrd r0, r1, d16
bl sqrt(PLT)
fmdrr d17, r0, r1
.L9:
mov r3, r5
mov r1, r4
add r0, r5, r6, lsl #3
.L11:
fldmiad r3!, {d16}
fmuld d16, d16, d17
fstmiad r1!, {d16}
cmp r3, r0
bne .L11</code></pre>
</td>
</tr>
</tbody>
</table>
<strong>Compiler isn't sure that floating point flags aren't affected!</strong>
</section>
</section>
<section>
<h2>Scalarization</h2>
<blockquote><b>Scalarization</b> replaces branchy code with a branchless analogy</blockquote>
Usually it is performed on a branches inside a loop body to allow further optimization. Machine-independent, local.
<table>
<colgroup>
<col/>
<col/>
</colgroup>
<tbody>
<tr>
<td style="padding-top: 0; padding-bottom: 0">
<pre><code class="cpp">int branchy(int i)
{
if (i > 4 && i < 42) return 1;
return 0;
}</code></pre>
</td>
<td style="padding-top: 0; padding-bottom: 0">
<pre><code class="cpp">int branchless(int i)
{
return (((unsigned)i) - 5 < 36);
}
</code></pre>
</td>
</tr>
</tbody>
</table>
<pre style="font-size: 0.95em; margin-bottom: 0px; margin-top: 0px;" class="console">$ gcc -march=armv8-a+simd -O3 1.c -S -o 1.s</pre>
<table>
<colgroup>
<col/>
<col/>
</colgroup>
<tbody>
<tr>
<td style="padding-top: 0; padding-bottom: 0">
<pre><code class="asm">branchy:
sub w0, w0, #5
cmp w0, 36
cset w0, ls
ret</code></pre>
</td>
<td style="padding-top: 0; padding-bottom: 0">
<pre><code class="asm">branchless:
sub w0, w0, #5
cmp w0, 36
cset w0, ls
ret</code></pre>
</td>
</tr>
</tbody>
</table>
</section>
<section>
<section>
<h2>Loop unswitching</h2>
<blockquote>Moves loop-invariant conditionals or switches which are independent of the loop index out of
the loop. Increases <abbr title="instruction level parallelism">ILP</abbr>, enables further optimizations.</blockquote>
<table class="simple">
<colgroup>
<col/>
<col/>
</colgroup>
<tbody>
<tr>
<td style="width: 50%;">
<pre><code class="cpp">for (int i = 0; i < len; i++)
{
if (a > 32)
arr[i] = a;
else
arr[i] = 42;
}
</code></pre> </td>
<td style="width: 50%;">
<pre><code class="cpp">int i = 0;
if (a > 32)
for (; i < len; i++)
arr[i] = a;
else
for (; i < len; i++)
arr[i] = 42;</code></pre>
</td>
</tr>
</tbody>
</table>
<pre style="font-size: 0.95em;" class="console">$ gcc -march=armv8-a+simd -O3 -S -o 1.s \
-fno-tree-vectorize 1.c</pre>
<small>auto-vectorization is disabled just to make example readable.</small>
</section>
<section>
<h2>Loop unswitching</h2>
<pre><code style="max-height: 720px;" class="armasm"> cmp w1, wzr
ble .L1
cmp w2, 32
bgt .L6
mov x2, 0
mov w3, 42
.L4:
str w3,[x0,x2,lsl 2]
add x2, x2, 1
cmp w1, w2
bgt .L4
.L1:
ret
L6:
mov x3, 0
.L3:
str w2,[x0,x3,lsl 2]
add x3, x3, 1
cmp w1, w3
bgt .L3
ret</code></pre>
</section>
<section>
<h2>Loop peeling</h2>
<blockquote><b>Loop peeling</b> takes out of the loop and executes separately a small number of iterations
from the beginning or/and the end of a loop, which eliminates if-statements.</blockquote>
Can be done by a compiler under high optimization levels.
<table class="simple" style="font-size:0.85em;">
<colgroup>
<col/>
<col/>
</colgroup>
<tbody>
<tr>
<td style="padding:0; width:50%">
<pre><code class="cpp">for(int i=0; i<len; i++)
{
if (i == 0)
b[i] = a[i+1];
else if(i == len-1 )
b[i] = a[i-1];
else
b[i] = a[i+1]+a[i-1];
}</code></pre>
</td>
<td>
<pre><code class="cpp">b[0] = a[0];
for(int i=0; i<len; i++)
[i] = a[i+1]+a[i-1];
b[len-1] = a[len-1];
</code></pre>
</td>
</tr>
</tbody>
</table>
<small>For the example below both tested compilers: gcc 4.9 and clang 3.5
<strong>won't</strong> perform this optimization. Make sure that a compiler was able to apply optimization
to such a code pattern or do it manually.</small>
</section>
<section>
<h2>Advanced unswitching: Sentinels</h2>
<blockquote><b>Sentinels</b> are special dummy values placed in a data structure which are added to simplify
the logic of handling boundary conditions (in particular, handling of loop-exit tests
or elimination out-of-bound checks).</blockquote>
<p><strong>This optimization cannot be performed by the compiler <br/>because require changes in use of
data structures</strong></p>
</section>
<section>
<h2>Advanced unswitching: Sentinels</h2>
<p>Let's assume that array <strong><code>a</code></strong> contains two extra elements:
one — at the left <strong><code>a[-1]</code></strong>,
and one — at the right <strong><code>a[N]</code></strong>. With such assumptions the code can be
rewritten as follows.</p>
<table class="simple" style="font-size:0.85em;">
<colgroup>
<col/>
<col/>
</colgroup>
<tbody>
<tr>
<td style="padding:0;width:50%;">
<pre><code class="cpp">for(int i=0; i<len; i++)
{
if (i == 0)
b[i] = a[i+1];
else if(i == len-1 )
b[i] = a[i-1];
else
b[i] = a[i+1]+a[i-1];
}</code></pre>
</td>
<td>
<pre><code class="cpp">// setup boundaries
a[-1] = 0;
a[len] = 0;
for (int i=0; i<len; i++)
[i] = a[i+1] + a[i-1];
</code></pre>
</td>
</tr>
</tbody>
</table>
</section>
</section>
<section>
<section>
<h2>Strength Reduction</h2>
<blockquote>replaces complex expressions with a simpler analogy</blockquote>
<table>
<colgroup>
<col style="width: 50%;"/>
<col style="width: 50%;"/>
</colgroup>
<tbody>
<tr>
<td>
<pre style="font-size: 0.80em;"><code class="cpp" data-trim data-noescape>double usePow(double x)
{
return pow(x, 2.);
}</code></pre>
</td>
<td>
<pre style="font-size: 0.80em;"><code class="cpp" data-trim data-noescape>float usePowf(float x)
{
return powf(x, 2.f);
}</code></pre>
</td>
</tr>
</tbody>
</table>
<p>
<strong>Machine-independent transformation in most cases.</strong><br>
It may be machine-dependent in case if it relies on a specific feature set,
implemented in the HW (e.g. <i>built-in detection</i>)
</p>
</section>
<section>
<h2>Strength Reduction</h2>
<pre style="font-size: 0.95em;" class="console"><span>$ gcc -march=armv7-a -mthumb -O3 -S -o 1.s \
> -mfpu=neon-vfpv4 -mfloat-abi=softfp 1.c</span></pre>
<table>
<colgroup>
<col style="width: 50%;"/>
<col style="width: 50%;"/>
</colgroup>
<tbody>
<tr>
<td>
<pre style="font-size: 0.9em;"><code class="armasm" data-trim data-noescape>usePow:
<abbr title="Puts a pair of integer registers (that holds function parameters) into one double precision register">fmdrr</abbr> d16, r0, r1
<abbr title="Double precision multiply">fmuld</abbr> d16, d16, d16
<abbr title="Puts one double precision register into a pair of integer registers (to pass function result)">fmrrd</abbr> r0, r1, d16
<abbr title="Branch to the link register == subroutine return">bx</abbr> lr
</code></pre>
</td>
<td>
<pre style="font-size: 0.9em;"><code class="armasm" data-trim data-noescape>usePowf:
fmsr s15, r0
fmuls s15, s15, s15
fmrs r0, s15
bx lr</code></pre>
</td>
</tr>
</tbody>
</table>
<p>Usually it is performed in a local scope<br> for a dependency chain.</p>
</section>
<section>
<h2>Strength Reduction (advanced case)</h2>
<pre style="font-size: 0.9em;"><code class="cpp" data-trim data-noescape>float useManyPowf(float a, float b, float c,
float d, float e, float f, float x)
{
return
a * powf(x, 5.f) +
b * powf(x, 4.f) +
c * powf(x, 3.f) +
d * powf(x, 2.f) +
e * x + f;
}</code></pre>
<pre style="font-size: 0.95em;" class="console"><span>$ gcc -march=armv7-a -mthumb -O3 -S -o 1.s \
> -mfpu=neon-vfpv4 -mfloat-abi=softfp 1.c</span></pre>
</section>
<section>
<h2>Strength Reduction (advanced)</h2>
<table style="width: 100%" class="simple">
<colgroup>
<col style="width: 50%;"/>
<col style="width: 50%;"/>
</colgroup>
<tbody>
<tr>
<td style="width: 50%;">
<pre><code class="armasm">useManyPowf:
push {r3, lr}
flds s17, [sp, #56]
fmsr s24, r1
movs r1, #0
fmsr s22, r0
movt r1, 16544
fmrs r0, s17
fmsr s21, r2
fmsr s20, r3
flds s19, [sp, #48]
flds s18, [sp, #52]
bl powf(PLT)
mov r1, #1082130432
fmsr s23, r0
fmrs r0, s17
bl powf(PLT)
</code></pre>
</td>
<td>
<pre><code class="armasm"> movs r1, #0
movt r1, 16448
fmsr s16, r0
fmrs r0, s17
bl powf(PLT)
fmuls s16, s16, s24
vfma.f32 s16, s23, s22
fmsr s15, r0
vfma.f32 s16, s15, s21
fmuls s15, s17, s17
vfma.f32 s16, s20, s15
vfma.f32 s16, s19, s17
fadds s15, s16, s18
fldmfdd sp!, {d8-d12}
fmrs r0, s15
pop {r3, pc}</code></pre>
</td>
</tr>
</tbody>
</table>
Compiler was able just partly reduce the complexity and generate <strong><code>vfma</code></strong> there it is possible
</section>
<section>
<h2>Strength Reduction (manual)</h2>
<p>Let's further reduce latency by applying Horner rule.</p>
<pre style="font-size: 0.7em;"><code class="cpp">float applyHornerf(float a, float b, float c,
float d, float e, float f, float x)
{
return ((((a * x + b) * x + c) * x + d) * x + e) * x + f;
}</code></pre>
<pre style="font-size: 0.95em;" class="console"><span>$ gcc -march=armv7-a -mthumb -O3 -S -o 1.s \
> -mfpu=neon-vfpv4 -mfloat-abi=softfp 1.c</span></pre>
<p>Compiler is not capable of this optimization because it doesn't produce exact result with the original formula</p>
</section>
<section>
<h2>Strength Reduction (manual)</h2>
<pre><code class="armasm">applyHornerf:
flds s15, [sp, #8]
fmsr s11, r0
fmsr s12, r1
flds s14, [sp]
vfma.f32 s12, s11, s15
fmsr s11, r2
flds s13, [sp, #4]
vfma.f32 s11, s12, s15
fcpys s12, s11
fmsr s11, r3
vfma.f32 s11, s12, s15
vfma.f32 s14, s11, s15
vfma.f32 s13, s14, s15
fmrs r0, s13
bx lr</code></pre>
</section>
</section>
<section>
<section>
<h2>Loop-induction variable elimination</h2>
<blockquote>In most cases compiler is able to replace<br><i>address arithmetics</i> with <i>pointer arithmetics</i>.</blockquote>
<pre><code class="cpp">void function(int* arr, int len)
{
for (int i = 0; i < len; i++)
arr[i] = 1;
}</code></pre>
<pre><code class="cpp">void function(int* arr, int len)
{
for (int* p = arr; p < arr + len; p++)
*p = 1;
}</code></pre>
<pre style="font-size: 0.95em;" class="console"><span>$ gcc -march=armv7-a -mthumb -O1 -S -o 1.s \
> -mfpu=neon-vfpv4 -mfloat-abi=softfp 1.c</span></pre>
</section>
<section>
<h2>Loop-induction variable elimination</h2>
<table class="simple">
<colgroup>
<col/>
<col/>
</colgroup>
<tbody>
<tr>
<td style="padding:0; width: 50%;">
<pre><code class="armacm"> cmp r1, #0
ble .L1
mov r3,r0
add r0,r0,r1,lsl #2
movs r2, #1
.L3:
str r2, [r3], #4
cmp r3, r0
bne .L3
.L1:
bx lr</code></pre>
</td>
<td style="padding:0;" >
<pre><code class="armasm">
add r1,r0,r1,lsl #2
cmp r0, r1
bcs .L5
movs r3, #1
.L8:
str r3, [r0], #4
cmp r1, r0
bhi .L8
.L5:
bx lr</code></pre>
</td>
</tr>
</tbody>
</table>
<blockquote>Most hand-written <b>pointer optimizations</b> do not make sense with usage optimization levels
higher than O0.</blockquote>
</section>
</section>
<section>
<section>
<h2>Auto-vectorization</h2>
<blockquote><b>Auto-vectorization</b> is machine code generation<br> that takes an advantage of vector instructions.</blockquote>
<ul>
<li>Most of all modern architectures have vector extensions as a co-processor or as dedicated pipes
<ul>
<li>MMX, SSE, SSE2, SSE4, AVX, AVX-512</li>
<li>AltiVec, VSX</li>
<li>ASIMD (NEON), MSA</li>
</ul>
</li>
<li>Enabled by inlining, unrolling, fusion, software pipelining, inter-procedural optimization, and
other machine independent transformations.</li>
</ul>
</section>
<section>
<h2>Auto-vectorization</h2>
<pre><code class="cpp">void vectorizeMe(float *a, float *b, int len)
{
int i;
for (i = 0; i < len; i++)
a[i] += b[i];
}</code></pre>
<pre style="font-size: 0.95em;" class="console"><span>$ gcc -march=armv7-a -mthumb -O3 -S -o 1.s \
> -mfpu=neon-vfpv4 -mfloat-abi=softfp \
> -fopt-info-missed 1.c</span></pre>
<p>But, NEON does not support full IEEE 754,<br>so gcc cannot vectorize the loop, what it told us</p>
<pre style="font-size: 0.95em;" class="console"><span>1.c:64:3: note: not vectorized:
relevant stmt not supported:_13 =_9+_12;</span></pre>
</section>
<section>
<h2>Auto-vectorization</h2>
Here is a generated assembly
<pre><code class="armasm">.L3:
fldmias r1!, {s14}
flds s15, [r0]
fadds s15, s15, s14
fstmias r0!, {s15}
cmp r0, r2
bne .L3</code></pre>
<p>But armv8-a does support, let's check it!</p>
<pre style="font-size: 0.95em;" class="console">$ gcc -march=armv8-a+simd -O3 -S -o 1.s \
> -fopt-info-all 1.c</pre>
and... Here we are!
<pre style="font-size: 0.95em;" class="console">1.c:64:3: note: loop vectorized</pre>
</section>
<section>
<h2>Auto-vectorization</h2>
Here is a generated assembly and full optimizer's report
<pre><code class="armasm">.L6:
ldr q1, [x3],16
add w6, w6, 1
ldr q0, [x7],16
cmp w6, w4
fadd v0.4s, v0.4s, v1.4s
str q0, [x8],16
bcc .L6</code></pre>
<pre style="font-size: 0.54em;" class="console"><span>
1.c:66:3: note: loop <b>vectorized</b>
1.c:66:3: note: loop <b>versioned</b> for vectorization because of possible aliasing
1.c:66:3: note: loop <b>peeled</b> for vectorization to enhance alignment
1.c:66:3: note: loop with 3 iterations completely <b>unrolled</b>
1.c:61:6: note: loop with 3 iterations completely <b>unrolled</b>
</span></pre>
<strong>Compiler versions the loop to allow optimized paths<br/>in case of aligned and non-aliasing pointers</strong>
</section>
<section>
<h2>keywords</h2>
Let's follow the advice to put some keywords
<pre><code class="cpp">void vectorizeMe(float* __restrict a_, float* __restrict b_, int len)
{
float *a=__builtin_assume_aligned(a_, 16);
float *b=__builtin_assume_aligned(b_, 16);
for (int i = 0; i < len; i++)
a[i] += b[i];
}</code></pre>
Optimizer's report shrinks.
<pre style="font-size: 0.7em;" class="console" >
1.c:66:3: note: loop vectorized
1.c:66:3: note: loop with 3 iterations completely unrolled</pre>
<strong><b><code>__restrict</code></b> and <b><code>__builtin_assume_aligned</code></b> keywords only eliminate some loop
versioning, but are not very useful from the performance perspective</strong>
</section>
</section>
<section>
<section>
<h2>Function body inlining</h2>
<blockquote>Replaces functional call to function body itself.</blockquote>
<pre><code class="cpp">int square(int x) { return x*x; }
for (int i = 0; i < len; i++)
arr[i] = square(i);</code></pre>
<p>Becomes</p>
<pre><code class="cpp">for (int i = 0; i < len; i++)
arr[i] = i*i;</code></pre>
<p><strong>Enables all further optimizations.</strong><br>
Machine-independent, interprocedural.</p>
</section>
<section>
<h2>Function body inlining</h2>
<pre class="console" style="font-size: 0.95em;">gcc -march=armv8-a+nosimd -O3 -S -o 1.s 1.c</pre>
<pre><code class="armasm" data-trim data-noescape>.L2:
add x2, x4, :lo12:.LANCHOR0
mov x1, 34464
mul w3, w0, w0
<abbr title="Move 16-bit immediate into register, keeping other bits unchanged.">movk</abbr> x1, 0x1, lsl 16
str w3, [x2,x0,lsl 2]
add x0, x0, 1
cmp x0, x1
bne .L2</code></pre>
<p>Let's compile the code with vector extension enabled</p>
<pre style="font-size: 0.95em;" class="console">-march=armv8-a+simd</pre>
</section>
<section>
<h2>Function body inlining</h2>
<pre><code class="armasm"> add x0, x0, :lo12:.LANCHOR0
movi v2.4s, 0x4
ldr q0, [x1]
add x1, x0, 397312
add x1, x1, 2688
.L2:
mul v1.4s, v0.4s, v0.4s
add v0.4s, v0.4s, v2.4s
str q1, [x0],16
cmp x0, x1
bne .L2</code></pre>
<p>Auto-vectorization is enabled because of possibility<br> to inline function call inside a loop.</p>
</section>
</section>
<section>
<section>
<h2>Built-in detection</h2>
<p>Compiler automatically uses the library functions <code>memset</code> and <code>memcpy</code>
to initialize and copy memory blocks</p>
<pre style="font-size: 0.7em;"><code style="max-height:720px;" data-trim class="cpp" >static char a[100000];
static char b[100000];
static int at(int idx, char val)
{
if (idx>=0 && idx<100000)
a[idx] = val;
}
int main()
{
for (int i=0; i<100000; ++i) a[i]=42;
for (int i=0; i<100000; ++i) at(i,-1);
for (int i=0; i<100000; ++i) b[i] = a[i];
}</code></pre>
</section>
<section>
<h2>Filling/copying memory blocks</h2>
Compiler knows what you mean
<pre style="font-size: 0.55em;"><code style="max-height:720px;" class="x86asm">main:
.LFB1:
.cfi_startproc
subq $8, %rsp
.cfi_def_cfa_offset 16
movl $100000, %edx
movl $42, %esi
movl $a, %edi
call memset
movl $100000, %edx
movl $255, %esi
movl $a, %edi
call memset
movl $100000, %edx
movl $a, %esi
movl $b, %edi
call memcpy
addq $8, %rsp
.cfi_def_cfa_offset 8
ret</code></pre>
</section>
<section>
<h2>Filling/copying memory blocks</h2>
The same picture, if the code is compiled for ARM target
<pre style="font-size: 0.54em;"><code style="max-height:720px;" class="x86asm">main:
ldr r3, .L3
mov r1, #42
stmfd sp!, {r4, lr}
add r3, pc, r3
movw r4, #34464
movt r4, 1
mov r0, r3
mov r2, r4
bl memset(PLT)
mov r2, r4
mov r1, #255
bl memset(PLT)
mov r2, r4
mov r3, r0
ldr r0, .L3+4
mov r1, r3
add r0, pc, r0
add r0, r0, #1792
bl memcpy(PLT)
ldmfd sp!, {r4, pc}</code></pre>
</section>
</section>
<section>
<section>
<h2>Case Study: floating point</h2>
<pre style="font-size: 0.7em;"><code class="cpp">double power( double d, unsigned n)
{
double x = 1.0;
for (unsigned j = 1; j<=n; j++, x *= d) ;
return x;
}
int main ()
{
double a = 1./0x80000000U, sum = 0.0;
for (unsigned i=1; i<= 0x80000000U; i++)
sum += power( i*a, i % 8);
printf ("sum = %g\n", sum);
}</code></pre>
<small style="float:right;">
<a href="https://gist.github.com/cuda-geek/2be305eb6aa99dc55aa6#file-test-flags-dp-c">flags-dp.c</a>
</small>
</section>
<section>
<h2>Case Study: floating point</h2>
<ol style="width:90%">
<li>Compile it <b>without</b> optimization
<pre style="font-size: 0.8em;" class="console"><span>$ gcc -std=c99 -Wall -O0 flags-dp.c -o flags-dp
$ time ./flags-dp
sum = 7.29569e+08
real 0m24.550s</span></pre></li>
<li>Compile it with <b>O1</b>: <b>~3.26 speedup</b>
<pre style="font-size: 0.8em;" class="console"><span>$ gcc -std=c99 -Wall -O1 flags-dp.c -o flags-dp
$ time ./flags-dp
sum = 7.29569e+08
real 0m7.529s</span></pre></li>
</ol>
</section>
<section>
<h2>Case Study: floating point</h2>
<ol start="3" style="width:90%">
<li>Compile it with <b>O2</b>: <b>~1.24 speedup</b>
<pre style="font-size: 0.8em;" class="console"><span>$ gcc -std=c99 -Wall -O2 flags-dp.c -o flags-dp
$ time ./flags-dp
sum = 7.29569e+08
real 0m6.069s</span></pre></li>
<li>Compile it with <b>O3</b>: <b>~1.00 speedup</b>
<pre style="font-size: 0.8em;" class="console"><span>$ gcc -std=c99 -Wall -O3 flags-dp.c -o flags-dp
$ time ./flags-dp
sum = 7.29569e+08
real 0m6.067s</span></pre></li>
</ol>
<p><b>Total speedup is ~4.05</b></p>
</section>
</section>
<section>
<section>
<h2>Case Study: integer</h2>
<pre style="font-size: 0.7em;"><code class="cpp">int power( int d, unsigned n)
{
int x = 1;
for (unsigned j = 1; j<=n; j++, x*=d) ;
return x;
}
int main ()
{
int64_t sum = 0;
for (unsigned i=1; i<0x80000000U; i++)
sum += power( i, i % 8);
printf ("sum = %ld\n", sum);
}</code></pre>
<small style="float:right;">
<a href="https://gist.github.com/cuda-geek/2be305eb6aa99dc55aa6#file-test-flags-c">flags.c</a>
</small>
</section>
<section>
<h2>Case Study: integer</h2>
<ol style="width:90%">
<li>Compile it <b>without</b> optimization
<pre style="font-size: 0.8em;" class="console"><span>$ gcc -std=c99 -Wall -O0 flags.c -o flags
$ time ./flags
sum = 288231861405089791
real 0m18.750s</span></pre></li>
<li>Compile it with <b>O1</b>: <b>~2.64 speedup</b>
<pre style="font-size: 0.8em;" class="console"><span>$ gcc -std=c99 -Wall -O1 flag.c -o flags
$ time ./flags
sum = 288231861405089791
real 0m7.092s</span></pre></li>
</ol>
</section>
<section>
<h2>Case study: integer</h2>
<ol start="3" style="width:90%">
<li>Compile it with <b>O2</b>:<b>~0.97 speedup</b>
<pre style="font-size: 0.8em;" class="console"><span>$ gcc -std=c99 -Wall -O2 flags.c -o flags
$ time ./flags
sum = 288231861405089791
real 0m7.300s</span></pre></li>
<li>Compile it with <b>O3</b>: <b>~1.00 speedup</b>
<pre style="font-size: 0.8em;" class="console"><span>$ gcc -std=c99 -Wall -O3 flags.c -o flags
$ time ./flags
sum = 288231861405089791
real 0m7.082s</span></pre></li>