forked from illumos/gcc
-
Notifications
You must be signed in to change notification settings - Fork 1
/
tree-vect-data-refs.c
4717 lines (3986 loc) · 154 KB
/
tree-vect-data-refs.c
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
/* Data References Analysis and Manipulation Utilities for Vectorization.
Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011
Free Software Foundation, Inc.
Contributed by Dorit Naishlos <dorit@il.ibm.com>
and Ira Rosen <irar@il.ibm.com>
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
for more details.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3. If not see
<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "tree.h"
#include "tm_p.h"
#include "target.h"
#include "basic-block.h"
#include "tree-pretty-print.h"
#include "gimple-pretty-print.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "cfgloop.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
#include "tree-vectorizer.h"
#include "diagnostic-core.h"
/* Need to include rtl.h, expr.h, etc. for optabs. */
#include "expr.h"
#include "optabs.h"
/* Return true if load- or store-lanes optab OPTAB is implemented for
COUNT vectors of type VECTYPE. NAME is the name of OPTAB. */
static bool
vect_lanes_optab_supported_p (const char *name, convert_optab optab,
tree vectype, unsigned HOST_WIDE_INT count)
{
enum machine_mode mode, array_mode;
bool limit_p;
mode = TYPE_MODE (vectype);
limit_p = !targetm.array_mode_supported_p (mode, count);
array_mode = mode_for_size (count * GET_MODE_BITSIZE (mode),
MODE_INT, limit_p);
if (array_mode == BLKmode)
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "no array mode for %s[" HOST_WIDE_INT_PRINT_DEC "]",
GET_MODE_NAME (mode), count);
return false;
}
if (convert_optab_handler (optab, array_mode, mode) == CODE_FOR_nothing)
{
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "cannot use %s<%s><%s>",
name, GET_MODE_NAME (array_mode), GET_MODE_NAME (mode));
return false;
}
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "can use %s<%s><%s>",
name, GET_MODE_NAME (array_mode), GET_MODE_NAME (mode));
return true;
}
/* Return the smallest scalar part of STMT.
This is used to determine the vectype of the stmt. We generally set the
vectype according to the type of the result (lhs). For stmts whose
result-type is different than the type of the arguments (e.g., demotion,
promotion), vectype will be reset appropriately (later). Note that we have
to visit the smallest datatype in this function, because that determines the
VF. If the smallest datatype in the loop is present only as the rhs of a
promotion operation - we'd miss it.
Such a case, where a variable of this datatype does not appear in the lhs
anywhere in the loop, can only occur if it's an invariant: e.g.:
'int_x = (int) short_inv', which we'd expect to have been optimized away by
invariant motion. However, we cannot rely on invariant motion to always
take invariants out of the loop, and so in the case of promotion we also
have to check the rhs.
LHS_SIZE_UNIT and RHS_SIZE_UNIT contain the sizes of the corresponding
types. */
tree
vect_get_smallest_scalar_type (gimple stmt, HOST_WIDE_INT *lhs_size_unit,
HOST_WIDE_INT *rhs_size_unit)
{
tree scalar_type = gimple_expr_type (stmt);
HOST_WIDE_INT lhs, rhs;
lhs = rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (scalar_type));
if (is_gimple_assign (stmt)
&& (gimple_assign_cast_p (stmt)
|| gimple_assign_rhs_code (stmt) == WIDEN_MULT_EXPR
|| gimple_assign_rhs_code (stmt) == FLOAT_EXPR))
{
tree rhs_type = TREE_TYPE (gimple_assign_rhs1 (stmt));
rhs = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (rhs_type));
if (rhs < lhs)
scalar_type = rhs_type;
}
*lhs_size_unit = lhs;
*rhs_size_unit = rhs;
return scalar_type;
}
/* Find the place of the data-ref in STMT in the interleaving chain that starts
from FIRST_STMT. Return -1 if the data-ref is not a part of the chain. */
int
vect_get_place_in_interleaving_chain (gimple stmt, gimple first_stmt)
{
gimple next_stmt = first_stmt;
int result = 0;
if (first_stmt != GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt)))
return -1;
while (next_stmt && next_stmt != stmt)
{
result++;
next_stmt = GROUP_NEXT_ELEMENT (vinfo_for_stmt (next_stmt));
}
if (next_stmt)
return result;
else
return -1;
}
/* Function vect_insert_into_interleaving_chain.
Insert DRA into the interleaving chain of DRB according to DRA's INIT. */
static void
vect_insert_into_interleaving_chain (struct data_reference *dra,
struct data_reference *drb)
{
gimple prev, next;
tree next_init;
stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
prev = GROUP_FIRST_ELEMENT (stmtinfo_b);
next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
while (next)
{
next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
if (tree_int_cst_compare (next_init, DR_INIT (dra)) > 0)
{
/* Insert here. */
GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = DR_STMT (dra);
GROUP_NEXT_ELEMENT (stmtinfo_a) = next;
return;
}
prev = next;
next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
}
/* We got to the end of the list. Insert here. */
GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = DR_STMT (dra);
GROUP_NEXT_ELEMENT (stmtinfo_a) = NULL;
}
/* Function vect_update_interleaving_chain.
For two data-refs DRA and DRB that are a part of a chain interleaved data
accesses, update the interleaving chain. DRB's INIT is smaller than DRA's.
There are four possible cases:
1. New stmts - both DRA and DRB are not a part of any chain:
FIRST_DR = DRB
NEXT_DR (DRB) = DRA
2. DRB is a part of a chain and DRA is not:
no need to update FIRST_DR
no need to insert DRB
insert DRA according to init
3. DRA is a part of a chain and DRB is not:
if (init of FIRST_DR > init of DRB)
FIRST_DR = DRB
NEXT(FIRST_DR) = previous FIRST_DR
else
insert DRB according to its init
4. both DRA and DRB are in some interleaving chains:
choose the chain with the smallest init of FIRST_DR
insert the nodes of the second chain into the first one. */
static void
vect_update_interleaving_chain (struct data_reference *drb,
struct data_reference *dra)
{
stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
tree next_init, init_dra_chain, init_drb_chain;
gimple first_a, first_b;
tree node_init;
gimple node, prev, next, first_stmt;
/* 1. New stmts - both DRA and DRB are not a part of any chain. */
if (!GROUP_FIRST_ELEMENT (stmtinfo_a) && !GROUP_FIRST_ELEMENT (stmtinfo_b))
{
GROUP_FIRST_ELEMENT (stmtinfo_a) = DR_STMT (drb);
GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (drb);
GROUP_NEXT_ELEMENT (stmtinfo_b) = DR_STMT (dra);
return;
}
/* 2. DRB is a part of a chain and DRA is not. */
if (!GROUP_FIRST_ELEMENT (stmtinfo_a) && GROUP_FIRST_ELEMENT (stmtinfo_b))
{
GROUP_FIRST_ELEMENT (stmtinfo_a) = GROUP_FIRST_ELEMENT (stmtinfo_b);
/* Insert DRA into the chain of DRB. */
vect_insert_into_interleaving_chain (dra, drb);
return;
}
/* 3. DRA is a part of a chain and DRB is not. */
if (GROUP_FIRST_ELEMENT (stmtinfo_a) && !GROUP_FIRST_ELEMENT (stmtinfo_b))
{
gimple old_first_stmt = GROUP_FIRST_ELEMENT (stmtinfo_a);
tree init_old = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (
old_first_stmt)));
gimple tmp;
if (tree_int_cst_compare (init_old, DR_INIT (drb)) > 0)
{
/* DRB's init is smaller than the init of the stmt previously marked
as the first stmt of the interleaving chain of DRA. Therefore, we
update FIRST_STMT and put DRB in the head of the list. */
GROUP_FIRST_ELEMENT (stmtinfo_b) = DR_STMT (drb);
GROUP_NEXT_ELEMENT (stmtinfo_b) = old_first_stmt;
/* Update all the stmts in the list to point to the new FIRST_STMT. */
tmp = old_first_stmt;
while (tmp)
{
GROUP_FIRST_ELEMENT (vinfo_for_stmt (tmp)) = DR_STMT (drb);
tmp = GROUP_NEXT_ELEMENT (vinfo_for_stmt (tmp));
}
}
else
{
/* Insert DRB in the list of DRA. */
vect_insert_into_interleaving_chain (drb, dra);
GROUP_FIRST_ELEMENT (stmtinfo_b) = GROUP_FIRST_ELEMENT (stmtinfo_a);
}
return;
}
/* 4. both DRA and DRB are in some interleaving chains. */
first_a = GROUP_FIRST_ELEMENT (stmtinfo_a);
first_b = GROUP_FIRST_ELEMENT (stmtinfo_b);
if (first_a == first_b)
return;
init_dra_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_a)));
init_drb_chain = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (first_b)));
if (tree_int_cst_compare (init_dra_chain, init_drb_chain) > 0)
{
/* Insert the nodes of DRA chain into the DRB chain.
After inserting a node, continue from this node of the DRB chain (don't
start from the beginning. */
node = GROUP_FIRST_ELEMENT (stmtinfo_a);
prev = GROUP_FIRST_ELEMENT (stmtinfo_b);
first_stmt = first_b;
}
else
{
/* Insert the nodes of DRB chain into the DRA chain.
After inserting a node, continue from this node of the DRA chain (don't
start from the beginning. */
node = GROUP_FIRST_ELEMENT (stmtinfo_b);
prev = GROUP_FIRST_ELEMENT (stmtinfo_a);
first_stmt = first_a;
}
while (node)
{
node_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (node)));
next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
while (next)
{
next_init = DR_INIT (STMT_VINFO_DATA_REF (vinfo_for_stmt (next)));
if (tree_int_cst_compare (next_init, node_init) > 0)
{
/* Insert here. */
GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = node;
GROUP_NEXT_ELEMENT (vinfo_for_stmt (node)) = next;
prev = node;
break;
}
prev = next;
next = GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev));
}
if (!next)
{
/* We got to the end of the list. Insert here. */
GROUP_NEXT_ELEMENT (vinfo_for_stmt (prev)) = node;
GROUP_NEXT_ELEMENT (vinfo_for_stmt (node)) = NULL;
prev = node;
}
GROUP_FIRST_ELEMENT (vinfo_for_stmt (node)) = first_stmt;
node = GROUP_NEXT_ELEMENT (vinfo_for_stmt (node));
}
}
/* Check dependence between DRA and DRB for basic block vectorization.
If the accesses share same bases and offsets, we can compare their initial
constant offsets to decide whether they differ or not. In case of a read-
write dependence we check that the load is before the store to ensure that
vectorization will not change the order of the accesses. */
static bool
vect_drs_dependent_in_basic_block (struct data_reference *dra,
struct data_reference *drb)
{
HOST_WIDE_INT type_size_a, type_size_b, init_a, init_b;
gimple earlier_stmt;
/* We only call this function for pairs of loads and stores, but we verify
it here. */
if (DR_IS_READ (dra) == DR_IS_READ (drb))
{
if (DR_IS_READ (dra))
return false;
else
return true;
}
/* Check that the data-refs have same bases and offsets. If not, we can't
determine if they are dependent. */
if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
|| !dr_equal_offsets_p (dra, drb))
return true;
/* Check the types. */
type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
if (type_size_a != type_size_b
|| !types_compatible_p (TREE_TYPE (DR_REF (dra)),
TREE_TYPE (DR_REF (drb))))
return true;
init_a = TREE_INT_CST_LOW (DR_INIT (dra));
init_b = TREE_INT_CST_LOW (DR_INIT (drb));
/* Two different locations - no dependence. */
if (init_a != init_b)
return false;
/* We have a read-write dependence. Check that the load is before the store.
When we vectorize basic blocks, vector load can be only before
corresponding scalar load, and vector store can be only after its
corresponding scalar store. So the order of the acceses is preserved in
case the load is before the store. */
earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
if (DR_IS_READ (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
return false;
return true;
}
/* Function vect_check_interleaving.
Check if DRA and DRB are a part of interleaving. In case they are, insert
DRA and DRB in an interleaving chain. */
static bool
vect_check_interleaving (struct data_reference *dra,
struct data_reference *drb)
{
HOST_WIDE_INT type_size_a, type_size_b, diff_mod_size, step, init_a, init_b;
/* Check that the data-refs have same first location (except init) and they
are both either store or load (not load and store). */
if (!operand_equal_p (DR_BASE_ADDRESS (dra), DR_BASE_ADDRESS (drb), 0)
|| !dr_equal_offsets_p (dra, drb)
|| !tree_int_cst_compare (DR_INIT (dra), DR_INIT (drb))
|| DR_IS_READ (dra) != DR_IS_READ (drb))
return false;
/* Check:
1. data-refs are of the same type
2. their steps are equal
3. the step (if greater than zero) is greater than the difference between
data-refs' inits. */
type_size_a = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dra))));
type_size_b = TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (drb))));
if (type_size_a != type_size_b
|| tree_int_cst_compare (DR_STEP (dra), DR_STEP (drb))
|| !types_compatible_p (TREE_TYPE (DR_REF (dra)),
TREE_TYPE (DR_REF (drb))))
return false;
init_a = TREE_INT_CST_LOW (DR_INIT (dra));
init_b = TREE_INT_CST_LOW (DR_INIT (drb));
step = TREE_INT_CST_LOW (DR_STEP (dra));
if (init_a > init_b)
{
/* If init_a == init_b + the size of the type * k, we have an interleaving,
and DRB is accessed before DRA. */
diff_mod_size = (init_a - init_b) % type_size_a;
if (step && (init_a - init_b) > step)
return false;
if (diff_mod_size == 0)
{
vect_update_interleaving_chain (drb, dra);
if (vect_print_dump_info (REPORT_DR_DETAILS))
{
fprintf (vect_dump, "Detected interleaving ");
print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
fprintf (vect_dump, " and ");
print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
}
return true;
}
}
else
{
/* If init_b == init_a + the size of the type * k, we have an
interleaving, and DRA is accessed before DRB. */
diff_mod_size = (init_b - init_a) % type_size_a;
if (step && (init_b - init_a) > step)
return false;
if (diff_mod_size == 0)
{
vect_update_interleaving_chain (dra, drb);
if (vect_print_dump_info (REPORT_DR_DETAILS))
{
fprintf (vect_dump, "Detected interleaving ");
print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
fprintf (vect_dump, " and ");
print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
}
return true;
}
}
return false;
}
/* Check if data references pointed by DR_I and DR_J are same or
belong to same interleaving group. Return FALSE if drs are
different, otherwise return TRUE. */
static bool
vect_same_range_drs (data_reference_p dr_i, data_reference_p dr_j)
{
gimple stmt_i = DR_STMT (dr_i);
gimple stmt_j = DR_STMT (dr_j);
if (operand_equal_p (DR_REF (dr_i), DR_REF (dr_j), 0)
|| (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_i))
&& GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_j))
&& (GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_i))
== GROUP_FIRST_ELEMENT (vinfo_for_stmt (stmt_j)))))
return true;
else
return false;
}
/* If address ranges represented by DDR_I and DDR_J are equal,
return TRUE, otherwise return FALSE. */
static bool
vect_vfa_range_equal (ddr_p ddr_i, ddr_p ddr_j)
{
if ((vect_same_range_drs (DDR_A (ddr_i), DDR_A (ddr_j))
&& vect_same_range_drs (DDR_B (ddr_i), DDR_B (ddr_j)))
|| (vect_same_range_drs (DDR_A (ddr_i), DDR_B (ddr_j))
&& vect_same_range_drs (DDR_B (ddr_i), DDR_A (ddr_j))))
return true;
else
return false;
}
/* Insert DDR into LOOP_VINFO list of ddrs that may alias and need to be
tested at run-time. Return TRUE if DDR was successfully inserted.
Return false if versioning is not supported. */
static bool
vect_mark_for_runtime_alias_test (ddr_p ddr, loop_vec_info loop_vinfo)
{
struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
if ((unsigned) PARAM_VALUE (PARAM_VECT_MAX_VERSION_FOR_ALIAS_CHECKS) == 0)
return false;
if (vect_print_dump_info (REPORT_DR_DETAILS))
{
fprintf (vect_dump, "mark for run-time aliasing test between ");
print_generic_expr (vect_dump, DR_REF (DDR_A (ddr)), TDF_SLIM);
fprintf (vect_dump, " and ");
print_generic_expr (vect_dump, DR_REF (DDR_B (ddr)), TDF_SLIM);
}
if (optimize_loop_nest_for_size_p (loop))
{
if (vect_print_dump_info (REPORT_DR_DETAILS))
fprintf (vect_dump, "versioning not supported when optimizing for size.");
return false;
}
/* FORNOW: We don't support versioning with outer-loop vectorization. */
if (loop->inner)
{
if (vect_print_dump_info (REPORT_DR_DETAILS))
fprintf (vect_dump, "versioning not yet supported for outer-loops.");
return false;
}
VEC_safe_push (ddr_p, heap, LOOP_VINFO_MAY_ALIAS_DDRS (loop_vinfo), ddr);
return true;
}
/* Function vect_analyze_data_ref_dependence.
Return TRUE if there (might) exist a dependence between a memory-reference
DRA and a memory-reference DRB. When versioning for alias may check a
dependence at run-time, return FALSE. Adjust *MAX_VF according to
the data dependence. */
static bool
vect_analyze_data_ref_dependence (struct data_dependence_relation *ddr,
loop_vec_info loop_vinfo, int *max_vf)
{
unsigned int i;
struct loop *loop = NULL;
struct data_reference *dra = DDR_A (ddr);
struct data_reference *drb = DDR_B (ddr);
stmt_vec_info stmtinfo_a = vinfo_for_stmt (DR_STMT (dra));
stmt_vec_info stmtinfo_b = vinfo_for_stmt (DR_STMT (drb));
lambda_vector dist_v;
unsigned int loop_depth;
/* Don't bother to analyze statements marked as unvectorizable. */
if (!STMT_VINFO_VECTORIZABLE (stmtinfo_a)
|| !STMT_VINFO_VECTORIZABLE (stmtinfo_b))
return false;
if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
{
/* Independent data accesses. */
vect_check_interleaving (dra, drb);
return false;
}
if (loop_vinfo)
loop = LOOP_VINFO_LOOP (loop_vinfo);
if ((DR_IS_READ (dra) && DR_IS_READ (drb) && loop_vinfo) || dra == drb)
return false;
if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
{
gimple earlier_stmt;
if (loop_vinfo)
{
if (vect_print_dump_info (REPORT_DR_DETAILS))
{
fprintf (vect_dump, "versioning for alias required: "
"can't determine dependence between ");
print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
fprintf (vect_dump, " and ");
print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
}
/* Add to list of ddrs that need to be tested at run-time. */
return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
}
/* When vectorizing a basic block unknown depnedence can still mean
strided access. */
if (vect_check_interleaving (dra, drb))
return false;
/* Read-read is OK (we need this check here, after checking for
interleaving). */
if (DR_IS_READ (dra) && DR_IS_READ (drb))
return false;
if (vect_print_dump_info (REPORT_DR_DETAILS))
{
fprintf (vect_dump, "can't determine dependence between ");
print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
fprintf (vect_dump, " and ");
print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
}
/* We do not vectorize basic blocks with write-write dependencies. */
if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
return true;
/* Check that it's not a load-after-store dependence. */
earlier_stmt = get_earlier_stmt (DR_STMT (dra), DR_STMT (drb));
if (DR_IS_WRITE (STMT_VINFO_DATA_REF (vinfo_for_stmt (earlier_stmt))))
return true;
return false;
}
/* Versioning for alias is not yet supported for basic block SLP, and
dependence distance is unapplicable, hence, in case of known data
dependence, basic block vectorization is impossible for now. */
if (!loop_vinfo)
{
if (dra != drb && vect_check_interleaving (dra, drb))
return false;
if (vect_print_dump_info (REPORT_DR_DETAILS))
{
fprintf (vect_dump, "determined dependence between ");
print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
fprintf (vect_dump, " and ");
print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
}
/* Do not vectorize basic blcoks with write-write dependences. */
if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
return true;
/* Check if this dependence is allowed in basic block vectorization. */
return vect_drs_dependent_in_basic_block (dra, drb);
}
/* Loop-based vectorization and known data dependence. */
if (DDR_NUM_DIST_VECTS (ddr) == 0)
{
if (vect_print_dump_info (REPORT_DR_DETAILS))
{
fprintf (vect_dump, "versioning for alias required: bad dist vector for ");
print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
fprintf (vect_dump, " and ");
print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
}
/* Add to list of ddrs that need to be tested at run-time. */
return !vect_mark_for_runtime_alias_test (ddr, loop_vinfo);
}
loop_depth = index_in_loop_nest (loop->num, DDR_LOOP_NEST (ddr));
FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v)
{
int dist = dist_v[loop_depth];
if (vect_print_dump_info (REPORT_DR_DETAILS))
fprintf (vect_dump, "dependence distance = %d.", dist);
if (dist == 0)
{
if (vect_print_dump_info (REPORT_DR_DETAILS))
{
fprintf (vect_dump, "dependence distance == 0 between ");
print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
fprintf (vect_dump, " and ");
print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
}
/* For interleaving, mark that there is a read-write dependency if
necessary. We check before that one of the data-refs is store. */
if (DR_IS_READ (dra))
GROUP_READ_WRITE_DEPENDENCE (stmtinfo_a) = true;
else
{
if (DR_IS_READ (drb))
GROUP_READ_WRITE_DEPENDENCE (stmtinfo_b) = true;
}
continue;
}
if (dist > 0 && DDR_REVERSED_P (ddr))
{
/* If DDR_REVERSED_P the order of the data-refs in DDR was
reversed (to make distance vector positive), and the actual
distance is negative. */
if (vect_print_dump_info (REPORT_DR_DETAILS))
fprintf (vect_dump, "dependence distance negative.");
continue;
}
if (abs (dist) >= 2
&& abs (dist) < *max_vf)
{
/* The dependence distance requires reduction of the maximal
vectorization factor. */
*max_vf = abs (dist);
if (vect_print_dump_info (REPORT_DR_DETAILS))
fprintf (vect_dump, "adjusting maximal vectorization factor to %i",
*max_vf);
}
if (abs (dist) >= *max_vf)
{
/* Dependence distance does not create dependence, as far as
vectorization is concerned, in this case. */
if (vect_print_dump_info (REPORT_DR_DETAILS))
fprintf (vect_dump, "dependence distance >= VF.");
continue;
}
if (vect_print_dump_info (REPORT_UNVECTORIZED_LOCATIONS))
{
fprintf (vect_dump, "not vectorized, possible dependence "
"between data-refs ");
print_generic_expr (vect_dump, DR_REF (dra), TDF_SLIM);
fprintf (vect_dump, " and ");
print_generic_expr (vect_dump, DR_REF (drb), TDF_SLIM);
}
return true;
}
return false;
}
/* Function vect_analyze_data_ref_dependences.
Examine all the data references in the loop, and make sure there do not
exist any data dependences between them. Set *MAX_VF according to
the maximum vectorization factor the data dependences allow. */
bool
vect_analyze_data_ref_dependences (loop_vec_info loop_vinfo,
bb_vec_info bb_vinfo, int *max_vf)
{
unsigned int i;
VEC (ddr_p, heap) *ddrs = NULL;
struct data_dependence_relation *ddr;
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "=== vect_analyze_dependences ===");
if (loop_vinfo)
ddrs = LOOP_VINFO_DDRS (loop_vinfo);
else
ddrs = BB_VINFO_DDRS (bb_vinfo);
FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
if (vect_analyze_data_ref_dependence (ddr, loop_vinfo, max_vf))
return false;
return true;
}
/* Function vect_compute_data_ref_alignment
Compute the misalignment of the data reference DR.
Output:
1. If during the misalignment computation it is found that the data reference
cannot be vectorized then false is returned.
2. DR_MISALIGNMENT (DR) is defined.
FOR NOW: No analysis is actually performed. Misalignment is calculated
only for trivial cases. TODO. */
static bool
vect_compute_data_ref_alignment (struct data_reference *dr)
{
gimple stmt = DR_STMT (dr);
stmt_vec_info stmt_info = vinfo_for_stmt (stmt);
loop_vec_info loop_vinfo = STMT_VINFO_LOOP_VINFO (stmt_info);
struct loop *loop = NULL;
tree ref = DR_REF (dr);
tree vectype;
tree base, base_addr;
bool base_aligned;
tree misalign;
tree aligned_to, alignment;
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "vect_compute_data_ref_alignment:");
if (loop_vinfo)
loop = LOOP_VINFO_LOOP (loop_vinfo);
/* Initialize misalignment to unknown. */
SET_DR_MISALIGNMENT (dr, -1);
misalign = DR_INIT (dr);
aligned_to = DR_ALIGNED_TO (dr);
base_addr = DR_BASE_ADDRESS (dr);
vectype = STMT_VINFO_VECTYPE (stmt_info);
/* In case the dataref is in an inner-loop of the loop that is being
vectorized (LOOP), we use the base and misalignment information
relative to the outer-loop (LOOP). This is ok only if the misalignment
stays the same throughout the execution of the inner-loop, which is why
we have to check that the stride of the dataref in the inner-loop evenly
divides by the vector size. */
if (loop && nested_in_vect_loop_p (loop, stmt))
{
tree step = DR_STEP (dr);
HOST_WIDE_INT dr_step = TREE_INT_CST_LOW (step);
if (dr_step % GET_MODE_SIZE (TYPE_MODE (vectype)) == 0)
{
if (vect_print_dump_info (REPORT_ALIGNMENT))
fprintf (vect_dump, "inner step divides the vector-size.");
misalign = STMT_VINFO_DR_INIT (stmt_info);
aligned_to = STMT_VINFO_DR_ALIGNED_TO (stmt_info);
base_addr = STMT_VINFO_DR_BASE_ADDRESS (stmt_info);
}
else
{
if (vect_print_dump_info (REPORT_ALIGNMENT))
fprintf (vect_dump, "inner step doesn't divide the vector-size.");
misalign = NULL_TREE;
}
}
base = build_fold_indirect_ref (base_addr);
alignment = ssize_int (TYPE_ALIGN (vectype)/BITS_PER_UNIT);
if ((aligned_to && tree_int_cst_compare (aligned_to, alignment) < 0)
|| !misalign)
{
if (vect_print_dump_info (REPORT_ALIGNMENT))
{
fprintf (vect_dump, "Unknown alignment for access: ");
print_generic_expr (vect_dump, base, TDF_SLIM);
}
return true;
}
if ((DECL_P (base)
&& tree_int_cst_compare (ssize_int (DECL_ALIGN_UNIT (base)),
alignment) >= 0)
|| (TREE_CODE (base_addr) == SSA_NAME
&& tree_int_cst_compare (ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (
TREE_TYPE (base_addr)))),
alignment) >= 0)
|| (get_pointer_alignment (base_addr) >= TYPE_ALIGN (vectype)))
base_aligned = true;
else
base_aligned = false;
if (!base_aligned)
{
/* Do not change the alignment of global variables if
flag_section_anchors is enabled. */
if (!vect_can_force_dr_alignment_p (base, TYPE_ALIGN (vectype))
|| (TREE_STATIC (base) && flag_section_anchors))
{
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "can't force alignment of ref: ");
print_generic_expr (vect_dump, ref, TDF_SLIM);
}
return true;
}
/* Force the alignment of the decl.
NOTE: This is the only change to the code we make during
the analysis phase, before deciding to vectorize the loop. */
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "force alignment of ");
print_generic_expr (vect_dump, ref, TDF_SLIM);
}
DECL_ALIGN (base) = TYPE_ALIGN (vectype);
DECL_USER_ALIGN (base) = 1;
}
/* At this point we assume that the base is aligned. */
gcc_assert (base_aligned
|| (TREE_CODE (base) == VAR_DECL
&& DECL_ALIGN (base) >= TYPE_ALIGN (vectype)));
/* If this is a backward running DR then first access in the larger
vectype actually is N-1 elements before the address in the DR.
Adjust misalign accordingly. */
if (tree_int_cst_compare (DR_STEP (dr), size_zero_node) < 0)
{
tree offset = ssize_int (TYPE_VECTOR_SUBPARTS (vectype) - 1);
/* DR_STEP(dr) is the same as -TYPE_SIZE of the scalar type,
otherwise we wouldn't be here. */
offset = fold_build2 (MULT_EXPR, ssizetype, offset, DR_STEP (dr));
/* PLUS because DR_STEP was negative. */
misalign = size_binop (PLUS_EXPR, misalign, offset);
}
/* Modulo alignment. */
misalign = size_binop (FLOOR_MOD_EXPR, misalign, alignment);
if (!host_integerp (misalign, 1))
{
/* Negative or overflowed misalignment value. */
if (vect_print_dump_info (REPORT_DETAILS))
fprintf (vect_dump, "unexpected misalign value");
return false;
}
SET_DR_MISALIGNMENT (dr, TREE_INT_CST_LOW (misalign));
if (vect_print_dump_info (REPORT_DETAILS))
{
fprintf (vect_dump, "misalign = %d bytes of ref ", DR_MISALIGNMENT (dr));
print_generic_expr (vect_dump, ref, TDF_SLIM);
}
return true;
}
/* Function vect_compute_data_refs_alignment
Compute the misalignment of data references in the loop.
Return FALSE if a data reference is found that cannot be vectorized. */
static bool
vect_compute_data_refs_alignment (loop_vec_info loop_vinfo,
bb_vec_info bb_vinfo)
{
VEC (data_reference_p, heap) *datarefs;
struct data_reference *dr;
unsigned int i;
if (loop_vinfo)
datarefs = LOOP_VINFO_DATAREFS (loop_vinfo);
else
datarefs = BB_VINFO_DATAREFS (bb_vinfo);
FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
if (STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr)))
&& !vect_compute_data_ref_alignment (dr))
{
if (bb_vinfo)
{
/* Mark unsupported statement as unvectorizable. */
STMT_VINFO_VECTORIZABLE (vinfo_for_stmt (DR_STMT (dr))) = false;
continue;
}
else
return false;
}
return true;
}
/* Function vect_update_misalignment_for_peel
DR - the data reference whose misalignment is to be adjusted.
DR_PEEL - the data reference whose misalignment is being made
zero in the vector loop by the peel.
NPEEL - the number of iterations in the peel loop if the misalignment
of DR_PEEL is known at compile time. */
static void
vect_update_misalignment_for_peel (struct data_reference *dr,
struct data_reference *dr_peel, int npeel)
{
unsigned int i;
VEC(dr_p,heap) *same_align_drs;
struct data_reference *current_dr;
int dr_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr))));
int dr_peel_size = GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (DR_REF (dr_peel))));
stmt_vec_info stmt_info = vinfo_for_stmt (DR_STMT (dr));
stmt_vec_info peel_stmt_info = vinfo_for_stmt (DR_STMT (dr_peel));
/* For interleaved data accesses the step in the loop must be multiplied by
the size of the interleaving group. */
if (STMT_VINFO_STRIDED_ACCESS (stmt_info))