Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-chrec.c @ 145:1830386684a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-9.2.0
author anatofuz
date Thu, 13 Feb 2020 11:34:05 +0900
parents 84e7813d76e9
children
comparison
equal deleted inserted replaced
131:84e7813d76e9 145:1830386684a0
1 /* Chains of recurrences. 1 /* Chains of recurrences.
2 Copyright (C) 2003-2018 Free Software Foundation, Inc. 2 Copyright (C) 2003-2020 Free Software Foundation, Inc.
3 Contributed by Sebastian Pop <pop@cri.ensmp.fr> 3 Contributed by Sebastian Pop <pop@cri.ensmp.fr>
4 4
5 This file is part of GCC. 5 This file is part of GCC.
6 6
7 GCC is free software; you can redistribute it and/or modify it under 7 GCC is free software; you can redistribute it and/or modify it under
33 #include "fold-const.h" 33 #include "fold-const.h"
34 #include "cfgloop.h" 34 #include "cfgloop.h"
35 #include "tree-ssa-loop-ivopts.h" 35 #include "tree-ssa-loop-ivopts.h"
36 #include "tree-ssa-loop-niter.h" 36 #include "tree-ssa-loop-niter.h"
37 #include "tree-chrec.h" 37 #include "tree-chrec.h"
38 #include "gimple.h"
39 #include "tree-ssa-loop.h"
38 #include "dumpfile.h" 40 #include "dumpfile.h"
39 #include "params.h"
40 #include "tree-scalar-evolution.h" 41 #include "tree-scalar-evolution.h"
41 42
42 /* Extended folder for chrecs. */ 43 /* Extended folder for chrecs. */
43 44
44 /* Fold the addition of two polynomial functions. */ 45 /* Fold the addition of two polynomial functions. */
48 tree type, 49 tree type,
49 tree poly0, 50 tree poly0,
50 tree poly1) 51 tree poly1)
51 { 52 {
52 tree left, right; 53 tree left, right;
53 struct loop *loop0 = get_chrec_loop (poly0); 54 class loop *loop0 = get_chrec_loop (poly0);
54 struct loop *loop1 = get_chrec_loop (poly1); 55 class loop *loop1 = get_chrec_loop (poly1);
55 tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type; 56 tree rtype = code == POINTER_PLUS_EXPR ? chrec_type (poly1) : type;
56 57
57 gcc_assert (poly0); 58 gcc_assert (poly0);
58 gcc_assert (poly1); 59 gcc_assert (poly1);
59 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); 60 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
140 tree poly0, 141 tree poly0,
141 tree poly1) 142 tree poly1)
142 { 143 {
143 tree t0, t1, t2; 144 tree t0, t1, t2;
144 int var; 145 int var;
145 struct loop *loop0 = get_chrec_loop (poly0); 146 class loop *loop0 = get_chrec_loop (poly0);
146 struct loop *loop1 = get_chrec_loop (poly1); 147 class loop *loop1 = get_chrec_loop (poly1);
147 148
148 gcc_assert (poly0); 149 gcc_assert (poly0);
149 gcc_assert (poly1); 150 gcc_assert (poly1);
150 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC); 151 gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
151 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); 152 gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
329 default: 330 default:
330 { 331 {
331 int size = 0; 332 int size = 0;
332 if ((tree_contains_chrecs (op0, &size) 333 if ((tree_contains_chrecs (op0, &size)
333 || tree_contains_chrecs (op1, &size)) 334 || tree_contains_chrecs (op1, &size))
334 && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 335 && size < param_scev_max_expr_size)
335 return build2 (code, type, op0, op1); 336 return build2 (code, type, op0, op1);
336 else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE)) 337 else if (size < param_scev_max_expr_size)
337 { 338 {
338 if (code == POINTER_PLUS_EXPR) 339 if (code == POINTER_PLUS_EXPR)
339 return fold_build_pointer_plus (fold_convert (type, op0), 340 return fold_build_pointer_plus (fold_convert (type, op0),
340 op1); 341 op1);
341 else 342 else
535 static tree 536 static tree
536 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k) 537 chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
537 { 538 {
538 tree arg0, arg1, binomial_n_k; 539 tree arg0, arg1, binomial_n_k;
539 tree type = TREE_TYPE (chrec); 540 tree type = TREE_TYPE (chrec);
540 struct loop *var_loop = get_loop (cfun, var); 541 class loop *var_loop = get_loop (cfun, var);
541 542
542 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC 543 while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
543 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec))) 544 && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
544 chrec = CHREC_LEFT (chrec); 545 chrec = CHREC_LEFT (chrec);
545 546
716 717
717 tree 718 tree
718 hide_evolution_in_other_loops_than_loop (tree chrec, 719 hide_evolution_in_other_loops_than_loop (tree chrec,
719 unsigned loop_num) 720 unsigned loop_num)
720 { 721 {
721 struct loop *loop = get_loop (cfun, loop_num), *chloop; 722 class loop *loop = get_loop (cfun, loop_num), *chloop;
722 if (automatically_generated_chrec_p (chrec)) 723 if (automatically_generated_chrec_p (chrec))
723 return chrec; 724 return chrec;
724 725
725 switch (TREE_CODE (chrec)) 726 switch (TREE_CODE (chrec))
726 { 727 {
757 chrec_component_in_loop_num (tree chrec, 758 chrec_component_in_loop_num (tree chrec,
758 unsigned loop_num, 759 unsigned loop_num,
759 bool right) 760 bool right)
760 { 761 {
761 tree component; 762 tree component;
762 struct loop *loop = get_loop (cfun, loop_num), *chloop; 763 class loop *loop = get_loop (cfun, loop_num), *chloop;
763 764
764 if (automatically_generated_chrec_p (chrec)) 765 if (automatically_generated_chrec_p (chrec))
765 return chrec; 766 return chrec;
766 767
767 switch (TREE_CODE (chrec)) 768 switch (TREE_CODE (chrec))
839 tree 840 tree
840 reset_evolution_in_loop (unsigned loop_num, 841 reset_evolution_in_loop (unsigned loop_num,
841 tree chrec, 842 tree chrec,
842 tree new_evol) 843 tree new_evol)
843 { 844 {
844 struct loop *loop = get_loop (cfun, loop_num); 845 class loop *loop = get_loop (cfun, loop_num);
845 846
846 if (POINTER_TYPE_P (chrec_type (chrec))) 847 if (POINTER_TYPE_P (chrec_type (chrec)))
847 gcc_assert (ptrofftype_p (chrec_type (new_evol))); 848 gcc_assert (ptrofftype_p (chrec_type (new_evol)));
848 else 849 else
849 gcc_assert (chrec_type (chrec) == chrec_type (new_evol)); 850 gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
930 CHREC_VARIABLE (chrec))); 931 CHREC_VARIABLE (chrec)));
931 else 932 else
932 return false; 933 return false;
933 } 934 }
934 935
935 /* Determines whether the chrec contains symbolic names or not. */ 936 /* Determines whether the chrec contains symbolic names or not. If LOOP isn't
936 937 NULL, we also consider chrec wrto outer loops of LOOP as symbol. */
937 bool 938
938 chrec_contains_symbols (const_tree chrec) 939 static bool
940 chrec_contains_symbols (const_tree chrec, hash_set<const_tree> &visited,
941 class loop *loop)
939 { 942 {
940 int i, n; 943 int i, n;
941 944
942 if (chrec == NULL_TREE) 945 if (chrec == NULL_TREE)
943 return false; 946 return false;
950 || TREE_CODE (chrec) == LABEL_DECL 953 || TREE_CODE (chrec) == LABEL_DECL
951 || TREE_CODE (chrec) == RESULT_DECL 954 || TREE_CODE (chrec) == RESULT_DECL
952 || TREE_CODE (chrec) == FIELD_DECL) 955 || TREE_CODE (chrec) == FIELD_DECL)
953 return true; 956 return true;
954 957
958 if (loop != NULL
959 && TREE_CODE (chrec) == POLYNOMIAL_CHREC
960 && flow_loop_nested_p (get_chrec_loop (chrec), loop))
961 return true;
962
963 if (visited.add (chrec))
964 return false;
965
955 n = TREE_OPERAND_LENGTH (chrec); 966 n = TREE_OPERAND_LENGTH (chrec);
956 for (i = 0; i < n; i++) 967 for (i = 0; i < n; i++)
957 if (chrec_contains_symbols (TREE_OPERAND (chrec, i))) 968 if (chrec_contains_symbols (TREE_OPERAND (chrec, i), visited, loop))
958 return true; 969 return true;
959 return false; 970 return false;
960 } 971 }
961 972
973 /* Return true if CHREC contains any symbols. If LOOP is not NULL, check if
974 CHREC contains any chrec which is invariant wrto the loop (nest), in other
975 words, chrec defined by outer loops of loop, so from LOOP's point of view,
976 the chrec is considered as a SYMBOL. */
977
978 bool
979 chrec_contains_symbols (const_tree chrec, class loop* loop)
980 {
981 hash_set<const_tree> visited;
982 return chrec_contains_symbols (chrec, visited, loop);
983 }
984
985 /* Return true when CHREC contains symbolic names defined in
986 LOOP_NB. */
987
988 static bool
989 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb,
990 hash_set<const_tree> &visited)
991 {
992 int i, n;
993
994 if (chrec == NULL_TREE)
995 return false;
996
997 if (is_gimple_min_invariant (chrec))
998 return false;
999
1000 if (TREE_CODE (chrec) == SSA_NAME)
1001 {
1002 gimple *def;
1003 loop_p def_loop, loop;
1004
1005 if (SSA_NAME_IS_DEFAULT_DEF (chrec))
1006 return false;
1007
1008 def = SSA_NAME_DEF_STMT (chrec);
1009 def_loop = loop_containing_stmt (def);
1010 loop = get_loop (cfun, loop_nb);
1011
1012 if (def_loop == NULL)
1013 return false;
1014
1015 if (loop == def_loop || flow_loop_nested_p (loop, def_loop))
1016 return true;
1017
1018 return false;
1019 }
1020
1021 if (visited.add (chrec))
1022 return false;
1023
1024 n = TREE_OPERAND_LENGTH (chrec);
1025 for (i = 0; i < n; i++)
1026 if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (chrec, i),
1027 loop_nb, visited))
1028 return true;
1029 return false;
1030 }
1031
1032 /* Return true when CHREC contains symbolic names defined in
1033 LOOP_NB. */
1034
1035 bool
1036 chrec_contains_symbols_defined_in_loop (const_tree chrec, unsigned loop_nb)
1037 {
1038 hash_set<const_tree> visited;
1039 return chrec_contains_symbols_defined_in_loop (chrec, loop_nb, visited);
1040 }
1041
962 /* Determines whether the chrec contains undetermined coefficients. */ 1042 /* Determines whether the chrec contains undetermined coefficients. */
1043
1044 static bool
1045 chrec_contains_undetermined (const_tree chrec, hash_set<const_tree> &visited)
1046 {
1047 int i, n;
1048
1049 if (chrec == chrec_dont_know)
1050 return true;
1051
1052 if (chrec == NULL_TREE)
1053 return false;
1054
1055 if (visited.add (chrec))
1056 return false;
1057
1058 n = TREE_OPERAND_LENGTH (chrec);
1059 for (i = 0; i < n; i++)
1060 if (chrec_contains_undetermined (TREE_OPERAND (chrec, i), visited))
1061 return true;
1062 return false;
1063 }
963 1064
964 bool 1065 bool
965 chrec_contains_undetermined (const_tree chrec) 1066 chrec_contains_undetermined (const_tree chrec)
966 { 1067 {
967 int i, n; 1068 hash_set<const_tree> visited;
968 1069 return chrec_contains_undetermined (chrec, visited);
969 if (chrec == chrec_dont_know)
970 return true;
971
972 if (chrec == NULL_TREE)
973 return false;
974
975 n = TREE_OPERAND_LENGTH (chrec);
976 for (i = 0; i < n; i++)
977 if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
978 return true;
979 return false;
980 } 1070 }
981 1071
982 /* Determines whether the tree EXPR contains chrecs, and increment 1072 /* Determines whether the tree EXPR contains chrecs, and increment
983 SIZE if it is not a NULL pointer by an estimation of the depth of 1073 SIZE if it is not a NULL pointer by an estimation of the depth of
984 the tree. */ 1074 the tree. */
985 1075
1076 static bool
1077 tree_contains_chrecs (const_tree expr, int *size, hash_set<const_tree> &visited)
1078 {
1079 int i, n;
1080
1081 if (expr == NULL_TREE)
1082 return false;
1083
1084 if (size)
1085 (*size)++;
1086
1087 if (tree_is_chrec (expr))
1088 return true;
1089
1090 if (visited.add (expr))
1091 return false;
1092
1093 n = TREE_OPERAND_LENGTH (expr);
1094 for (i = 0; i < n; i++)
1095 if (tree_contains_chrecs (TREE_OPERAND (expr, i), size, visited))
1096 return true;
1097 return false;
1098 }
1099
986 bool 1100 bool
987 tree_contains_chrecs (const_tree expr, int *size) 1101 tree_contains_chrecs (const_tree expr, int *size)
988 { 1102 {
989 int i, n; 1103 hash_set<const_tree> visited;
990 1104 return tree_contains_chrecs (expr, size, visited);
991 if (expr == NULL_TREE) 1105 }
992 return false; 1106
993
994 if (size)
995 (*size)++;
996
997 if (tree_is_chrec (expr))
998 return true;
999
1000 n = TREE_OPERAND_LENGTH (expr);
1001 for (i = 0; i < n; i++)
1002 if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
1003 return true;
1004 return false;
1005 }
1006 1107
1007 /* Recursive helper function. */ 1108 /* Recursive helper function. */
1008 1109
1009 static bool 1110 static bool
1010 evolution_function_is_invariant_rec_p (tree chrec, int loopnum) 1111 evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
1103 return false; 1204 return false;
1104 } 1205 }
1105 } 1206 }
1106 1207
1107 /* Determine whether the given tree is a function in zero or one 1208 /* Determine whether the given tree is a function in zero or one
1108 variables. */ 1209 variables with respect to loop specified by LOOPNUM. Note only positive
1210 LOOPNUM stands for a real loop. */
1109 1211
1110 bool 1212 bool
1111 evolution_function_is_univariate_p (const_tree chrec) 1213 evolution_function_is_univariate_p (const_tree chrec, int loopnum)
1112 { 1214 {
1113 if (chrec == NULL_TREE) 1215 if (chrec == NULL_TREE)
1114 return true; 1216 return true;
1115 1217
1218 tree sub_chrec;
1116 switch (TREE_CODE (chrec)) 1219 switch (TREE_CODE (chrec))
1117 { 1220 {
1118 case POLYNOMIAL_CHREC: 1221 case POLYNOMIAL_CHREC:
1119 switch (TREE_CODE (CHREC_LEFT (chrec))) 1222 switch (TREE_CODE (CHREC_LEFT (chrec)))
1120 { 1223 {
1121 case POLYNOMIAL_CHREC: 1224 case POLYNOMIAL_CHREC:
1122 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_LEFT (chrec))) 1225 sub_chrec = CHREC_LEFT (chrec);
1226 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1227 && (loopnum <= 0
1228 || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1229 || flow_loop_nested_p (get_loop (cfun, loopnum),
1230 get_chrec_loop (sub_chrec))))
1123 return false; 1231 return false;
1124 if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec))) 1232 if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1125 return false; 1233 return false;
1126 break; 1234 break;
1127 1235
1128 default: 1236 default:
1129 if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL)) 1237 if (tree_contains_chrecs (CHREC_LEFT (chrec), NULL))
1132 } 1240 }
1133 1241
1134 switch (TREE_CODE (CHREC_RIGHT (chrec))) 1242 switch (TREE_CODE (CHREC_RIGHT (chrec)))
1135 { 1243 {
1136 case POLYNOMIAL_CHREC: 1244 case POLYNOMIAL_CHREC:
1137 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (CHREC_RIGHT (chrec))) 1245 sub_chrec = CHREC_RIGHT (chrec);
1246 if (CHREC_VARIABLE (chrec) != CHREC_VARIABLE (sub_chrec)
1247 && (loopnum <= 0
1248 || CHREC_VARIABLE (sub_chrec) == (unsigned) loopnum
1249 || flow_loop_nested_p (get_loop (cfun, loopnum),
1250 get_chrec_loop (sub_chrec))))
1138 return false; 1251 return false;
1139 if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec))) 1252 if (!evolution_function_is_univariate_p (sub_chrec, loopnum))
1140 return false; 1253 return false;
1141 break; 1254 break;
1142 1255
1143 default: 1256 default:
1144 if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL)) 1257 if (tree_contains_chrecs (CHREC_RIGHT (chrec), NULL))
1180 unnecessary tests, but also to enforce that the result follows them. 1293 unnecessary tests, but also to enforce that the result follows them.
1181 FROM is the source variable converted if it's not NULL. Returns true if 1294 FROM is the source variable converted if it's not NULL. Returns true if
1182 the conversion succeeded, false otherwise. */ 1295 the conversion succeeded, false otherwise. */
1183 1296
1184 bool 1297 bool
1185 convert_affine_scev (struct loop *loop, tree type, 1298 convert_affine_scev (class loop *loop, tree type,
1186 tree *base, tree *step, gimple *at_stmt, 1299 tree *base, tree *step, gimple *at_stmt,
1187 bool use_overflow_semantics, tree from) 1300 bool use_overflow_semantics, tree from)
1188 { 1301 {
1189 tree ct = TREE_TYPE (*step); 1302 tree ct = TREE_TYPE (*step);
1190 bool enforce_overflow_semantics; 1303 bool enforce_overflow_semantics;
1311 chrec_convert_1 (tree type, tree chrec, gimple *at_stmt, 1424 chrec_convert_1 (tree type, tree chrec, gimple *at_stmt,
1312 bool use_overflow_semantics, tree from) 1425 bool use_overflow_semantics, tree from)
1313 { 1426 {
1314 tree ct, res; 1427 tree ct, res;
1315 tree base, step; 1428 tree base, step;
1316 struct loop *loop; 1429 class loop *loop;
1317 1430
1318 if (automatically_generated_chrec_p (chrec)) 1431 if (automatically_generated_chrec_p (chrec))
1319 return chrec; 1432 return chrec;
1320 1433
1321 ct = chrec_type (chrec); 1434 ct = chrec_type (chrec);
1447 return NULL_TREE; 1560 return NULL_TREE;
1448 1561
1449 if (!*fold_conversions && evolution_function_is_affine_p (chrec)) 1562 if (!*fold_conversions && evolution_function_is_affine_p (chrec))
1450 { 1563 {
1451 tree base, step; 1564 tree base, step;
1452 struct loop *loop; 1565 class loop *loop;
1453 1566
1454 loop = get_chrec_loop (chrec); 1567 loop = get_chrec_loop (chrec);
1455 base = CHREC_LEFT (chrec); 1568 base = CHREC_LEFT (chrec);
1456 step = CHREC_RIGHT (chrec); 1569 step = CHREC_RIGHT (chrec);
1457 if (convert_affine_scev (loop, type, &base, &step, NULL, true)) 1570 if (convert_affine_scev (loop, type, &base, &step, NULL, true))