forked from illumos/gcc
/
tree-scalar-evolution.c
2864 lines (2297 loc) · 80.5 KB
/
tree-scalar-evolution.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
/* Scalar evolution detector.
Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
Contributed by Sebastian Pop <s.pop@laposte.net>
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/>. */
/*
Description:
This pass analyzes the evolution of scalar variables in loop
structures. The algorithm is based on the SSA representation,
and on the loop hierarchy tree. This algorithm is not based on
the notion of versions of a variable, as it was the case for the
previous implementations of the scalar evolution algorithm, but
it assumes that each defined name is unique.
The notation used in this file is called "chains of recurrences",
and has been proposed by Eugene Zima, Robert Van Engelen, and
others for describing induction variables in programs. For example
"b -> {0, +, 2}_1" means that the scalar variable "b" is equal to 0
when entering in the loop_1 and has a step 2 in this loop, in other
words "for (b = 0; b < N; b+=2);". Note that the coefficients of
this chain of recurrence (or chrec [shrek]) can contain the name of
other variables, in which case they are called parametric chrecs.
For example, "b -> {a, +, 2}_1" means that the initial value of "b"
is the value of "a". In most of the cases these parametric chrecs
are fully instantiated before their use because symbolic names can
hide some difficult cases such as self-references described later
(see the Fibonacci example).
A short sketch of the algorithm is:
Given a scalar variable to be analyzed, follow the SSA edge to
its definition:
- When the definition is a GIMPLE_MODIFY_STMT: if the right hand side
(RHS) of the definition cannot be statically analyzed, the answer
of the analyzer is: "don't know".
Otherwise, for all the variables that are not yet analyzed in the
RHS, try to determine their evolution, and finally try to
evaluate the operation of the RHS that gives the evolution
function of the analyzed variable.
- When the definition is a condition-phi-node: determine the
evolution function for all the branches of the phi node, and
finally merge these evolutions (see chrec_merge).
- When the definition is a loop-phi-node: determine its initial
condition, that is the SSA edge defined in an outer loop, and
keep it symbolic. Then determine the SSA edges that are defined
in the body of the loop. Follow the inner edges until ending on
another loop-phi-node of the same analyzed loop. If the reached
loop-phi-node is not the starting loop-phi-node, then we keep
this definition under a symbolic form. If the reached
loop-phi-node is the same as the starting one, then we compute a
symbolic stride on the return path. The result is then the
symbolic chrec {initial_condition, +, symbolic_stride}_loop.
Examples:
Example 1: Illustration of the basic algorithm.
| a = 3
| loop_1
| b = phi (a, c)
| c = b + 1
| if (c > 10) exit_loop
| endloop
Suppose that we want to know the number of iterations of the
loop_1. The exit_loop is controlled by a COND_EXPR (c > 10). We
ask the scalar evolution analyzer two questions: what's the
scalar evolution (scev) of "c", and what's the scev of "10". For
"10" the answer is "10" since it is a scalar constant. For the
scalar variable "c", it follows the SSA edge to its definition,
"c = b + 1", and then asks again what's the scev of "b".
Following the SSA edge, we end on a loop-phi-node "b = phi (a,
c)", where the initial condition is "a", and the inner loop edge
is "c". The initial condition is kept under a symbolic form (it
may be the case that the copy constant propagation has done its
work and we end with the constant "3" as one of the edges of the
loop-phi-node). The update edge is followed to the end of the
loop, and until reaching again the starting loop-phi-node: b -> c
-> b. At this point we have drawn a path from "b" to "b" from
which we compute the stride in the loop: in this example it is
"+1". The resulting scev for "b" is "b -> {a, +, 1}_1". Now
that the scev for "b" is known, it is possible to compute the
scev for "c", that is "c -> {a + 1, +, 1}_1". In order to
determine the number of iterations in the loop_1, we have to
instantiate_parameters ({a + 1, +, 1}_1), that gives after some
more analysis the scev {4, +, 1}_1, or in other words, this is
the function "f (x) = x + 4", where x is the iteration count of
the loop_1. Now we have to solve the inequality "x + 4 > 10",
and take the smallest iteration number for which the loop is
exited: x = 7. This loop runs from x = 0 to x = 7, and in total
there are 8 iterations. In terms of loop normalization, we have
created a variable that is implicitly defined, "x" or just "_1",
and all the other analyzed scalars of the loop are defined in
function of this variable:
a -> 3
b -> {3, +, 1}_1
c -> {4, +, 1}_1
or in terms of a C program:
| a = 3
| for (x = 0; x <= 7; x++)
| {
| b = x + 3
| c = x + 4
| }
Example 2: Illustration of the algorithm on nested loops.
| loop_1
| a = phi (1, b)
| c = a + 2
| loop_2 10 times
| b = phi (c, d)
| d = b + 3
| endloop
| endloop
For analyzing the scalar evolution of "a", the algorithm follows
the SSA edge into the loop's body: "a -> b". "b" is an inner
loop-phi-node, and its analysis as in Example 1, gives:
b -> {c, +, 3}_2
d -> {c + 3, +, 3}_2
Following the SSA edge for the initial condition, we end on "c = a
+ 2", and then on the starting loop-phi-node "a". From this point,
the loop stride is computed: back on "c = a + 2" we get a "+2" in
the loop_1, then on the loop-phi-node "b" we compute the overall
effect of the inner loop that is "b = c + 30", and we get a "+30"
in the loop_1. That means that the overall stride in loop_1 is
equal to "+32", and the result is:
a -> {1, +, 32}_1
c -> {3, +, 32}_1
Example 3: Higher degree polynomials.
| loop_1
| a = phi (2, b)
| c = phi (5, d)
| b = a + 1
| d = c + a
| endloop
a -> {2, +, 1}_1
b -> {3, +, 1}_1
c -> {5, +, a}_1
d -> {5 + a, +, a}_1
instantiate_parameters ({5, +, a}_1) -> {5, +, 2, +, 1}_1
instantiate_parameters ({5 + a, +, a}_1) -> {7, +, 3, +, 1}_1
Example 4: Lucas, Fibonacci, or mixers in general.
| loop_1
| a = phi (1, b)
| c = phi (3, d)
| b = c
| d = c + a
| endloop
a -> (1, c)_1
c -> {3, +, a}_1
The syntax "(1, c)_1" stands for a PEELED_CHREC that has the
following semantics: during the first iteration of the loop_1, the
variable contains the value 1, and then it contains the value "c".
Note that this syntax is close to the syntax of the loop-phi-node:
"a -> (1, c)_1" vs. "a = phi (1, c)".
The symbolic chrec representation contains all the semantics of the
original code. What is more difficult is to use this information.
Example 5: Flip-flops, or exchangers.
| loop_1
| a = phi (1, b)
| c = phi (3, d)
| b = c
| d = a
| endloop
a -> (1, c)_1
c -> (3, a)_1
Based on these symbolic chrecs, it is possible to refine this
information into the more precise PERIODIC_CHRECs:
a -> |1, 3|_1
c -> |3, 1|_1
This transformation is not yet implemented.
Further readings:
You can find a more detailed description of the algorithm in:
http://icps.u-strasbg.fr/~pop/DEA_03_Pop.pdf
http://icps.u-strasbg.fr/~pop/DEA_03_Pop.ps.gz. But note that
this is a preliminary report and some of the details of the
algorithm have changed. I'm working on a research report that
updates the description of the algorithms to reflect the design
choices used in this implementation.
A set of slides show a high level overview of the algorithm and run
an example through the scalar evolution analyzer:
http://cri.ensmp.fr/~pop/gcc/mar04/slides.pdf
The slides that I have presented at the GCC Summit'04 are available
at: http://cri.ensmp.fr/~pop/gcc/20040604/gccsummit-lno-spop.pdf
*/
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "ggc.h"
#include "tree.h"
#include "real.h"
/* These RTL headers are needed for basic-block.h. */
#include "rtl.h"
#include "basic-block.h"
#include "diagnostic.h"
#include "tree-flow.h"
#include "tree-dump.h"
#include "timevar.h"
#include "cfgloop.h"
#include "tree-chrec.h"
#include "tree-scalar-evolution.h"
#include "tree-pass.h"
#include "flags.h"
#include "params.h"
static tree analyze_scalar_evolution_1 (struct loop *, tree, tree);
/* The cached information about a ssa name VAR, claiming that inside LOOP,
the value of VAR can be expressed as CHREC. */
struct scev_info_str GTY(())
{
tree var;
tree chrec;
};
/* Counters for the scev database. */
static unsigned nb_set_scev = 0;
static unsigned nb_get_scev = 0;
/* The following trees are unique elements. Thus the comparison of
another element to these elements should be done on the pointer to
these trees, and not on their value. */
/* The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE. */
tree chrec_not_analyzed_yet;
/* Reserved to the cases where the analyzer has detected an
undecidable property at compile time. */
tree chrec_dont_know;
/* When the analyzer has detected that a property will never
happen, then it qualifies it with chrec_known. */
tree chrec_known;
static bitmap already_instantiated;
static GTY ((param_is (struct scev_info_str))) htab_t scalar_evolution_info;
/* Constructs a new SCEV_INFO_STR structure. */
static inline struct scev_info_str *
new_scev_info_str (tree var)
{
struct scev_info_str *res;
res = GGC_NEW (struct scev_info_str);
res->var = var;
res->chrec = chrec_not_analyzed_yet;
return res;
}
/* Computes a hash function for database element ELT. */
static hashval_t
hash_scev_info (const void *elt)
{
return SSA_NAME_VERSION (((const struct scev_info_str *) elt)->var);
}
/* Compares database elements E1 and E2. */
static int
eq_scev_info (const void *e1, const void *e2)
{
const struct scev_info_str *elt1 = (const struct scev_info_str *) e1;
const struct scev_info_str *elt2 = (const struct scev_info_str *) e2;
return elt1->var == elt2->var;
}
/* Deletes database element E. */
static void
del_scev_info (void *e)
{
ggc_free (e);
}
/* Get the index corresponding to VAR in the current LOOP. If
it's the first time we ask for this VAR, then we return
chrec_not_analyzed_yet for this VAR and return its index. */
static tree *
find_var_scev_info (tree var)
{
struct scev_info_str *res;
struct scev_info_str tmp;
PTR *slot;
tmp.var = var;
slot = htab_find_slot (scalar_evolution_info, &tmp, INSERT);
if (!*slot)
*slot = new_scev_info_str (var);
res = (struct scev_info_str *) *slot;
return &res->chrec;
}
/* Return true when CHREC contains symbolic names defined in
LOOP_NB. */
bool
chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
{
int i, n;
if (chrec == NULL_TREE)
return false;
if (TREE_INVARIANT (chrec))
return false;
if (TREE_CODE (chrec) == VAR_DECL
|| TREE_CODE (chrec) == PARM_DECL
|| TREE_CODE (chrec) == FUNCTION_DECL
|| TREE_CODE (chrec) == LABEL_DECL
|| TREE_CODE (chrec) == RESULT_DECL
|| TREE_CODE (chrec) == FIELD_DECL)
return true;
if (TREE_CODE (chrec) == SSA_NAME)
{
tree def = SSA_NAME_DEF_STMT (chrec);
struct loop *def_loop = loop_containing_stmt (def);
struct loop *loop = get_loop (loop_nb);
if (def_loop == NULL)
return false;
if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
return true;
return false;
}
n = TREE_OPERAND_LENGTH (chrec);
for (i = 0; i < n; i++)
if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
loop_nb))
return true;
return false;
}
/* Return true when PHI is a loop-phi-node. */
static bool
loop_phi_node_p (tree phi)
{
/* The implementation of this function is based on the following
property: "all the loop-phi-nodes of a loop are contained in the
loop's header basic block". */
return loop_containing_stmt (phi)->header == bb_for_stmt (phi);
}
/* Compute the scalar evolution for EVOLUTION_FN after crossing LOOP.
In general, in the case of multivariate evolutions we want to get
the evolution in different loops. LOOP specifies the level for
which to get the evolution.
Example:
| for (j = 0; j < 100; j++)
| {
| for (k = 0; k < 100; k++)
| {
| i = k + j; - Here the value of i is a function of j, k.
| }
| ... = i - Here the value of i is a function of j.
| }
| ... = i - Here the value of i is a scalar.
Example:
| i_0 = ...
| loop_1 10 times
| i_1 = phi (i_0, i_2)
| i_2 = i_1 + 2
| endloop
This loop has the same effect as:
LOOP_1 has the same effect as:
| i_1 = i_0 + 20
The overall effect of the loop, "i_0 + 20" in the previous example,
is obtained by passing in the parameters: LOOP = 1,
EVOLUTION_FN = {i_0, +, 2}_1.
*/
static tree
compute_overall_effect_of_inner_loop (struct loop *loop, tree evolution_fn)
{
bool val = false;
if (evolution_fn == chrec_dont_know)
return chrec_dont_know;
else if (TREE_CODE (evolution_fn) == POLYNOMIAL_CHREC)
{
struct loop *inner_loop = get_chrec_loop (evolution_fn);
if (inner_loop == loop
|| flow_loop_nested_p (loop, inner_loop))
{
tree nb_iter = number_of_latch_executions (inner_loop);
if (nb_iter == chrec_dont_know)
return chrec_dont_know;
else
{
tree res;
/* evolution_fn is the evolution function in LOOP. Get
its value in the nb_iter-th iteration. */
res = chrec_apply (inner_loop->num, evolution_fn, nb_iter);
/* Continue the computation until ending on a parent of LOOP. */
return compute_overall_effect_of_inner_loop (loop, res);
}
}
else
return evolution_fn;
}
/* If the evolution function is an invariant, there is nothing to do. */
else if (no_evolution_in_loop_p (evolution_fn, loop->num, &val) && val)
return evolution_fn;
else
return chrec_dont_know;
}
/* Determine whether the CHREC is always positive/negative. If the expression
cannot be statically analyzed, return false, otherwise set the answer into
VALUE. */
bool
chrec_is_positive (tree chrec, bool *value)
{
bool value0, value1, value2;
tree end_value, nb_iter;
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
if (!chrec_is_positive (CHREC_LEFT (chrec), &value0)
|| !chrec_is_positive (CHREC_RIGHT (chrec), &value1))
return false;
/* FIXME -- overflows. */
if (value0 == value1)
{
*value = value0;
return true;
}
/* Otherwise the chrec is under the form: "{-197, +, 2}_1",
and the proof consists in showing that the sign never
changes during the execution of the loop, from 0 to
loop->nb_iterations. */
if (!evolution_function_is_affine_p (chrec))
return false;
nb_iter = number_of_latch_executions (get_chrec_loop (chrec));
if (chrec_contains_undetermined (nb_iter))
return false;
#if 0
/* TODO -- If the test is after the exit, we may decrease the number of
iterations by one. */
if (after_exit)
nb_iter = chrec_fold_minus (type, nb_iter, build_int_cst (type, 1));
#endif
end_value = chrec_apply (CHREC_VARIABLE (chrec), chrec, nb_iter);
if (!chrec_is_positive (end_value, &value2))
return false;
*value = value0;
return value0 == value1;
case INTEGER_CST:
*value = (tree_int_cst_sgn (chrec) == 1);
return true;
default:
return false;
}
}
/* Associate CHREC to SCALAR. */
static void
set_scalar_evolution (tree scalar, tree chrec)
{
tree *scalar_info;
if (TREE_CODE (scalar) != SSA_NAME)
return;
scalar_info = find_var_scev_info (scalar);
if (dump_file)
{
if (dump_flags & TDF_DETAILS)
{
fprintf (dump_file, "(set_scalar_evolution \n");
fprintf (dump_file, " (scalar = ");
print_generic_expr (dump_file, scalar, 0);
fprintf (dump_file, ")\n (scalar_evolution = ");
print_generic_expr (dump_file, chrec, 0);
fprintf (dump_file, "))\n");
}
if (dump_flags & TDF_STATS)
nb_set_scev++;
}
*scalar_info = chrec;
}
/* Retrieve the chrec associated to SCALAR in the LOOP. */
static tree
get_scalar_evolution (tree scalar)
{
tree res;
if (dump_file)
{
if (dump_flags & TDF_DETAILS)
{
fprintf (dump_file, "(get_scalar_evolution \n");
fprintf (dump_file, " (scalar = ");
print_generic_expr (dump_file, scalar, 0);
fprintf (dump_file, ")\n");
}
if (dump_flags & TDF_STATS)
nb_get_scev++;
}
switch (TREE_CODE (scalar))
{
case SSA_NAME:
res = *find_var_scev_info (scalar);
break;
case REAL_CST:
case FIXED_CST:
case INTEGER_CST:
res = scalar;
break;
default:
res = chrec_not_analyzed_yet;
break;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (scalar_evolution = ");
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, "))\n");
}
return res;
}
/* Helper function for add_to_evolution. Returns the evolution
function for an assignment of the form "a = b + c", where "a" and
"b" are on the strongly connected component. CHREC_BEFORE is the
information that we already have collected up to this point.
TO_ADD is the evolution of "c".
When CHREC_BEFORE has an evolution part in LOOP_NB, add to this
evolution the expression TO_ADD, otherwise construct an evolution
part for this loop. */
static tree
add_to_evolution_1 (unsigned loop_nb, tree chrec_before, tree to_add,
tree at_stmt)
{
tree type, left, right;
struct loop *loop = get_loop (loop_nb), *chloop;
switch (TREE_CODE (chrec_before))
{
case POLYNOMIAL_CHREC:
chloop = get_chrec_loop (chrec_before);
if (chloop == loop
|| flow_loop_nested_p (chloop, loop))
{
unsigned var;
type = chrec_type (chrec_before);
/* When there is no evolution part in this loop, build it. */
if (chloop != loop)
{
var = loop_nb;
left = chrec_before;
right = SCALAR_FLOAT_TYPE_P (type)
? build_real (type, dconst0)
: build_int_cst (type, 0);
}
else
{
var = CHREC_VARIABLE (chrec_before);
left = CHREC_LEFT (chrec_before);
right = CHREC_RIGHT (chrec_before);
}
to_add = chrec_convert (type, to_add, at_stmt);
right = chrec_convert_rhs (type, right, at_stmt);
right = chrec_fold_plus (chrec_type (right), right, to_add);
return build_polynomial_chrec (var, left, right);
}
else
{
gcc_assert (flow_loop_nested_p (loop, chloop));
/* Search the evolution in LOOP_NB. */
left = add_to_evolution_1 (loop_nb, CHREC_LEFT (chrec_before),
to_add, at_stmt);
right = CHREC_RIGHT (chrec_before);
right = chrec_convert_rhs (chrec_type (left), right, at_stmt);
return build_polynomial_chrec (CHREC_VARIABLE (chrec_before),
left, right);
}
default:
/* These nodes do not depend on a loop. */
if (chrec_before == chrec_dont_know)
return chrec_dont_know;
left = chrec_before;
right = chrec_convert_rhs (chrec_type (left), to_add, at_stmt);
return build_polynomial_chrec (loop_nb, left, right);
}
}
/* Add TO_ADD to the evolution part of CHREC_BEFORE in the dimension
of LOOP_NB.
Description (provided for completeness, for those who read code in
a plane, and for my poor 62 bytes brain that would have forgotten
all this in the next two or three months):
The algorithm of translation of programs from the SSA representation
into the chrecs syntax is based on a pattern matching. After having
reconstructed the overall tree expression for a loop, there are only
two cases that can arise:
1. a = loop-phi (init, a + expr)
2. a = loop-phi (init, expr)
where EXPR is either a scalar constant with respect to the analyzed
loop (this is a degree 0 polynomial), or an expression containing
other loop-phi definitions (these are higher degree polynomials).
Examples:
1.
| init = ...
| loop_1
| a = phi (init, a + 5)
| endloop
2.
| inita = ...
| initb = ...
| loop_1
| a = phi (inita, 2 * b + 3)
| b = phi (initb, b + 1)
| endloop
For the first case, the semantics of the SSA representation is:
| a (x) = init + \sum_{j = 0}^{x - 1} expr (j)
that is, there is a loop index "x" that determines the scalar value
of the variable during the loop execution. During the first
iteration, the value is that of the initial condition INIT, while
during the subsequent iterations, it is the sum of the initial
condition with the sum of all the values of EXPR from the initial
iteration to the before last considered iteration.
For the second case, the semantics of the SSA program is:
| a (x) = init, if x = 0;
| expr (x - 1), otherwise.
The second case corresponds to the PEELED_CHREC, whose syntax is
close to the syntax of a loop-phi-node:
| phi (init, expr) vs. (init, expr)_x
The proof of the translation algorithm for the first case is a
proof by structural induction based on the degree of EXPR.
Degree 0:
When EXPR is a constant with respect to the analyzed loop, or in
other words when EXPR is a polynomial of degree 0, the evolution of
the variable A in the loop is an affine function with an initial
condition INIT, and a step EXPR. In order to show this, we start
from the semantics of the SSA representation:
f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
and since "expr (j)" is a constant with respect to "j",
f (x) = init + x * expr
Finally, based on the semantics of the pure sum chrecs, by
identification we get the corresponding chrecs syntax:
f (x) = init * \binom{x}{0} + expr * \binom{x}{1}
f (x) -> {init, +, expr}_x
Higher degree:
Suppose that EXPR is a polynomial of degree N with respect to the
analyzed loop_x for which we have already determined that it is
written under the chrecs syntax:
| expr (x) -> {b_0, +, b_1, +, ..., +, b_{n-1}} (x)
We start from the semantics of the SSA program:
| f (x) = init + \sum_{j = 0}^{x - 1} expr (j)
|
| f (x) = init + \sum_{j = 0}^{x - 1}
| (b_0 * \binom{j}{0} + ... + b_{n-1} * \binom{j}{n-1})
|
| f (x) = init + \sum_{j = 0}^{x - 1}
| \sum_{k = 0}^{n - 1} (b_k * \binom{j}{k})
|
| f (x) = init + \sum_{k = 0}^{n - 1}
| (b_k * \sum_{j = 0}^{x - 1} \binom{j}{k})
|
| f (x) = init + \sum_{k = 0}^{n - 1}
| (b_k * \binom{x}{k + 1})
|
| f (x) = init + b_0 * \binom{x}{1} + ...
| + b_{n-1} * \binom{x}{n}
|
| f (x) = init * \binom{x}{0} + b_0 * \binom{x}{1} + ...
| + b_{n-1} * \binom{x}{n}
|
And finally from the definition of the chrecs syntax, we identify:
| f (x) -> {init, +, b_0, +, ..., +, b_{n-1}}_x
This shows the mechanism that stands behind the add_to_evolution
function. An important point is that the use of symbolic
parameters avoids the need of an analysis schedule.
Example:
| inita = ...
| initb = ...
| loop_1
| a = phi (inita, a + 2 + b)
| b = phi (initb, b + 1)
| endloop
When analyzing "a", the algorithm keeps "b" symbolically:
| a -> {inita, +, 2 + b}_1
Then, after instantiation, the analyzer ends on the evolution:
| a -> {inita, +, 2 + initb, +, 1}_1
*/
static tree
add_to_evolution (unsigned loop_nb, tree chrec_before, enum tree_code code,
tree to_add, tree at_stmt)
{
tree type = chrec_type (to_add);
tree res = NULL_TREE;
if (to_add == NULL_TREE)
return chrec_before;
/* TO_ADD is either a scalar, or a parameter. TO_ADD is not
instantiated at this point. */
if (TREE_CODE (to_add) == POLYNOMIAL_CHREC)
/* This should not happen. */
return chrec_dont_know;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "(add_to_evolution \n");
fprintf (dump_file, " (loop_nb = %d)\n", loop_nb);
fprintf (dump_file, " (chrec_before = ");
print_generic_expr (dump_file, chrec_before, 0);
fprintf (dump_file, ")\n (to_add = ");
print_generic_expr (dump_file, to_add, 0);
fprintf (dump_file, ")\n");
}
if (code == MINUS_EXPR)
to_add = chrec_fold_multiply (type, to_add, SCALAR_FLOAT_TYPE_P (type)
? build_real (type, dconstm1)
: build_int_cst_type (type, -1));
res = add_to_evolution_1 (loop_nb, chrec_before, to_add, at_stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (res = ");
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, "))\n");
}
return res;
}
/* Helper function. */
static inline tree
set_nb_iterations_in_loop (struct loop *loop,
tree res)
{
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, " (set_nb_iterations_in_loop = ");
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, "))\n");
}
loop->nb_iterations = res;
return res;
}
/* This section selects the loops that will be good candidates for the
scalar evolution analysis. For the moment, greedily select all the
loop nests we could analyze. */
/* Return true when it is possible to analyze the condition expression
EXPR. */
static bool
analyzable_condition (const_tree expr)
{
tree condition;
if (TREE_CODE (expr) != COND_EXPR)
return false;
condition = TREE_OPERAND (expr, 0);
switch (TREE_CODE (condition))
{
case SSA_NAME:
return true;
case LT_EXPR:
case LE_EXPR:
case GT_EXPR:
case GE_EXPR:
case EQ_EXPR:
case NE_EXPR:
return true;
default:
return false;
}
return false;
}
/* For a loop with a single exit edge, return the COND_EXPR that
guards the exit edge. If the expression is too difficult to
analyze, then give up. */
tree
get_loop_exit_condition (const struct loop *loop)
{
tree res = NULL_TREE;
edge exit_edge = single_exit (loop);
if (dump_file && (dump_flags & TDF_DETAILS))
fprintf (dump_file, "(get_loop_exit_condition \n ");
if (exit_edge)
{
tree expr;
expr = last_stmt (exit_edge->src);
if (analyzable_condition (expr))
res = expr;
}
if (dump_file && (dump_flags & TDF_DETAILS))
{
print_generic_expr (dump_file, res, 0);
fprintf (dump_file, ")\n");
}
return res;
}
/* Recursively determine and enqueue the exit conditions for a loop. */
static void
get_exit_conditions_rec (struct loop *loop,
VEC(tree,heap) **exit_conditions)
{
if (!loop)
return;
/* Recurse on the inner loops, then on the next (sibling) loops. */
get_exit_conditions_rec (loop->inner, exit_conditions);
get_exit_conditions_rec (loop->next, exit_conditions);
if (single_exit (loop))
{
tree loop_condition = get_loop_exit_condition (loop);
if (loop_condition)
VEC_safe_push (tree, heap, *exit_conditions, loop_condition);
}
}
/* Select the candidate loop nests for the analysis. This function
initializes the EXIT_CONDITIONS array. */
static void
select_loops_exit_conditions (VEC(tree,heap) **exit_conditions)
{
struct loop *function_body = current_loops->tree_root;
get_exit_conditions_rec (function_body->inner, exit_conditions);
}
/* Depth first search algorithm. */
typedef enum t_bool {
t_false,
t_true,
t_dont_know