Mercurial > hg > CbC > CbC_gcc

comparison gcc/tree-ssa-reassoc.c @ 67:f6334be47118

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update gcc from gcc-4.6-20100522 to gcc-4.6-20110318
author nobuyasu <dimolto@cr.ie.u-ryukyu.ac.jp>
date Tue, 22 Mar 2011 17:18:12 +0900
parents b7f97abdc517
children 04ced10e8804
comparison
equal deleted inserted replaced
65:65488c3d617d 67:f6334be47118
22 #include "system.h" 22 #include "system.h"
23 #include "coretypes.h" 23 #include "coretypes.h"
24 #include "tm.h" 24 #include "tm.h"
25 #include "tree.h" 25 #include "tree.h"
26 #include "basic-block.h" 26 #include "basic-block.h"
27 #include "diagnostic.h"
28 #include "tree-pretty-print.h" 27 #include "tree-pretty-print.h"
29 #include "gimple-pretty-print.h" 28 #include "gimple-pretty-print.h"
30 #include "tree-inline.h" 29 #include "tree-inline.h"
31 #include "tree-flow.h" 30 #include "tree-flow.h"
32 #include "gimple.h" 31 #include "gimple.h"
466 465
467 if (VEC_length (operand_entry_t, *ops) == 2) 466 if (VEC_length (operand_entry_t, *ops) == 2)
468 { 467 {
469 VEC_free (operand_entry_t, heap, *ops); 468 VEC_free (operand_entry_t, heap, *ops);
470 *ops = NULL; 469 *ops = NULL;
471 add_to_ops_vec (ops, fold_convert (TREE_TYPE (last->op), 470 add_to_ops_vec (ops, build_zero_cst (TREE_TYPE (last->op)));
472 integer_zero_node));
473 *all_done = true; 471 *all_done = true;
474 } 472 }
475 else 473 else
476 { 474 {
477 VEC_ordered_remove (operand_entry_t, *ops, i-1); 475 VEC_ordered_remove (operand_entry_t, *ops, i-1);
534 print_generic_expr (dump_file, oe->op, 0); 532 print_generic_expr (dump_file, oe->op, 0);
535 fprintf (dump_file, " -> 0\n"); 533 fprintf (dump_file, " -> 0\n");
536 } 534 }
537 535
538 VEC_ordered_remove (operand_entry_t, *ops, i); 536 VEC_ordered_remove (operand_entry_t, *ops, i);
539 add_to_ops_vec (ops, fold_convert(TREE_TYPE (oe->op), 537 add_to_ops_vec (ops, build_zero_cst (TREE_TYPE (oe->op)));
540 integer_zero_node));
541 VEC_ordered_remove (operand_entry_t, *ops, currindex); 538 VEC_ordered_remove (operand_entry_t, *ops, currindex);
542 reassociate_stats.ops_eliminated ++; 539 reassociate_stats.ops_eliminated ++;
543 540
544 return true; 541 return true;
545 } 542 }
622 else if (opcode == BIT_IOR_EXPR) 619 else if (opcode == BIT_IOR_EXPR)
623 fprintf (dump_file, " -> -1\n"); 620 fprintf (dump_file, " -> -1\n");
624 } 621 }
625 622
626 if (opcode == BIT_AND_EXPR) 623 if (opcode == BIT_AND_EXPR)
627 oe->op = fold_convert (TREE_TYPE (oe->op), integer_zero_node); 624 oe->op = build_zero_cst (TREE_TYPE (oe->op));
628 else if (opcode == BIT_IOR_EXPR) 625 else if (opcode == BIT_IOR_EXPR)
629 oe->op = build_low_bits_mask (TREE_TYPE (oe->op), 626 oe->op = build_low_bits_mask (TREE_TYPE (oe->op),
630 TYPE_PRECISION (TREE_TYPE (oe->op))); 627 TYPE_PRECISION (TREE_TYPE (oe->op)));
631 628
632 reassociate_stats.ops_eliminated 629 reassociate_stats.ops_eliminated
1015 1012
1016 /* Build a list of candidates to process. */ 1013 /* Build a list of candidates to process. */
1017 candidates = sbitmap_alloc (length); 1014 candidates = sbitmap_alloc (length);
1018 sbitmap_zero (candidates); 1015 sbitmap_zero (candidates);
1019 nr_candidates = 0; 1016 nr_candidates = 0;
1020 for (i = 0; VEC_iterate (operand_entry_t, *ops, i, oe1); ++i) 1017 FOR_EACH_VEC_ELT (operand_entry_t, *ops, i, oe1)
1021 { 1018 {
1022 enum tree_code dcode; 1019 enum tree_code dcode;
1023 gimple oe1def; 1020 gimple oe1def;
1024 1021
1025 if (TREE_CODE (oe1->op) != SSA_NAME) 1022 if (TREE_CODE (oe1->op) != SSA_NAME)
1066 oedef = SSA_NAME_DEF_STMT (VEC_index (operand_entry_t, *ops, i)->op); 1063 oedef = SSA_NAME_DEF_STMT (VEC_index (operand_entry_t, *ops, i)->op);
1067 oecode = gimple_assign_rhs_code (oedef); 1064 oecode = gimple_assign_rhs_code (oedef);
1068 linearize_expr_tree (&subops[i], oedef, 1065 linearize_expr_tree (&subops[i], oedef,
1069 associative_tree_code (oecode), false); 1066 associative_tree_code (oecode), false);
1070 1067
1071 for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j) 1068 FOR_EACH_VEC_ELT (operand_entry_t, subops[i], j, oe1)
1072 { 1069 {
1073 oecount c; 1070 oecount c;
1074 void **slot; 1071 void **slot;
1075 size_t idx; 1072 size_t idx;
1076 c.oecode = oecode; 1073 c.oecode = oecode;
1092 } 1089 }
1093 } 1090 }
1094 htab_delete (ctable); 1091 htab_delete (ctable);
1095 1092
1096 /* Sort the counting table. */ 1093 /* Sort the counting table. */
1097 qsort (VEC_address (oecount, cvec), VEC_length (oecount, cvec), 1094 VEC_qsort (oecount, cvec, oecount_cmp);
1098 sizeof (oecount), oecount_cmp);
1099 1095
1100 if (dump_file && (dump_flags & TDF_DETAILS)) 1096 if (dump_file && (dump_flags & TDF_DETAILS))
1101 { 1097 {
1102 oecount *c; 1098 oecount *c;
1103 fprintf (dump_file, "Candidates:\n"); 1099 fprintf (dump_file, "Candidates:\n");
1104 for (j = 0; VEC_iterate (oecount, cvec, j, c); ++j) 1100 FOR_EACH_VEC_ELT (oecount, cvec, j, c)
1105 { 1101 {
1106 fprintf (dump_file, " %u %s: ", c->cnt, 1102 fprintf (dump_file, " %u %s: ", c->cnt,
1107 c->oecode == MULT_EXPR 1103 c->oecode == MULT_EXPR
1108 ? "*" : c->oecode == RDIV_EXPR ? "/" : "?"); 1104 ? "*" : c->oecode == RDIV_EXPR ? "/" : "?");
1109 print_generic_expr (dump_file, c->op, 0); 1105 print_generic_expr (dump_file, c->op, 0);
1138 oedef = SSA_NAME_DEF_STMT (op); 1134 oedef = SSA_NAME_DEF_STMT (op);
1139 oecode = gimple_assign_rhs_code (oedef); 1135 oecode = gimple_assign_rhs_code (oedef);
1140 if (oecode != c->oecode) 1136 if (oecode != c->oecode)
1141 continue; 1137 continue;
1142 1138
1143 for (j = 0; VEC_iterate (operand_entry_t, subops[i], j, oe1); ++j) 1139 FOR_EACH_VEC_ELT (operand_entry_t, subops[i], j, oe1)
1144 { 1140 {
1145 if (oe1->op == c->op) 1141 if (oe1->op == c->op)
1146 { 1142 {
1147 SET_BIT (candidates2, i); 1143 SET_BIT (candidates2, i);
1148 ++nr_candidates2; 1144 ++nr_candidates2;
1177 fprintf (dump_file, " + "); 1173 fprintf (dump_file, " + ");
1178 print_generic_expr (dump_file, oe2->op, 0); 1174 print_generic_expr (dump_file, oe2->op, 0);
1179 } 1175 }
1180 zero_one_operation (&oe2->op, c->oecode, c->op); 1176 zero_one_operation (&oe2->op, c->oecode, c->op);
1181 sum = build_and_add_sum (tmpvar, oe1->op, oe2->op, opcode); 1177 sum = build_and_add_sum (tmpvar, oe1->op, oe2->op, opcode);
1182 oe2->op = fold_convert (TREE_TYPE (oe2->op), integer_zero_node); 1178 oe2->op = build_zero_cst (TREE_TYPE (oe2->op));
1183 oe2->rank = 0; 1179 oe2->rank = 0;
1184 oe1->op = gimple_get_lhs (sum); 1180 oe1->op = gimple_get_lhs (sum);
1185 } 1181 }
1186 1182
1187 /* Apply the multiplication/division. */ 1183 /* Apply the multiplication/division. */
1260 if (!is_gimple_assign (def2)) 1256 if (!is_gimple_assign (def2))
1261 continue; 1257 continue;
1262 rcode = gimple_assign_rhs_code (def2); 1258 rcode = gimple_assign_rhs_code (def2);
1263 if (TREE_CODE_CLASS (rcode) != tcc_comparison) 1259 if (TREE_CODE_CLASS (rcode) != tcc_comparison)
1264 continue; 1260 continue;
1265 if (operand_equal_p (op1, gimple_assign_rhs1 (def2), 0)
1266 && operand_equal_p (op2, gimple_assign_rhs2 (def2), 0))
1267 ;
1268 else if (operand_equal_p (op1, gimple_assign_rhs2 (def2), 0)
1269 && operand_equal_p (op2, gimple_assign_rhs1 (def2), 0))
1270 rcode = swap_tree_comparison (rcode);
1271 else
1272 continue;
1273 1261
1274 /* If we got here, we have a match. See if we can combine the 1262 /* If we got here, we have a match. See if we can combine the
1275 two comparisons. */ 1263 two comparisons. */
1276 t = combine_comparisons (UNKNOWN_LOCATION, 1264 if (opcode == BIT_IOR_EXPR)
1277 (opcode == BIT_IOR_EXPR 1265 t = maybe_fold_or_comparisons (lcode, op1, op2,
1278 ? TRUTH_OR_EXPR : TRUTH_AND_EXPR), 1266 rcode, gimple_assign_rhs1 (def2),
1279 lcode, rcode, TREE_TYPE (curr->op), op1, op2); 1267 gimple_assign_rhs2 (def2));
1268 else
1269 t = maybe_fold_and_comparisons (lcode, op1, op2,
1270 rcode, gimple_assign_rhs1 (def2),
1271 gimple_assign_rhs2 (def2));
1280 if (!t) 1272 if (!t)
1281 continue; 1273 continue;
1274
1275 /* maybe_fold_and_comparisons and maybe_fold_or_comparisons
1276 always give us a boolean_type_node value back. If the original
1277 BIT_AND_EXPR or BIT_IOR_EXPR was of a wider integer type,
1278 we need to convert. */
1279 if (!useless_type_conversion_p (TREE_TYPE (curr->op), TREE_TYPE (t)))
1280 t = fold_convert (TREE_TYPE (curr->op), t);
1281
1282 if (dump_file && (dump_flags & TDF_DETAILS)) 1282 if (dump_file && (dump_flags & TDF_DETAILS))
1283 { 1283 {
1284 fprintf (dump_file, "Equivalence: "); 1284 fprintf (dump_file, "Equivalence: ");
1285 print_generic_expr (dump_file, curr->op, 0); 1285 print_generic_expr (dump_file, curr->op, 0);
1286 fprintf (dump_file, " %s ", op_symbol_code (opcode)); 1286 fprintf (dump_file, " %s ", op_symbol_code (opcode));
1302 if (TREE_CODE (t) == INTEGER_CST) 1302 if (TREE_CODE (t) == INTEGER_CST)
1303 { 1303 {
1304 VEC_ordered_remove (operand_entry_t, *ops, currindex); 1304 VEC_ordered_remove (operand_entry_t, *ops, currindex);
1305 add_to_ops_vec (ops, t); 1305 add_to_ops_vec (ops, t);
1306 } 1306 }
1307 else if (TREE_CODE (t) != lcode) 1307 else if (!operand_equal_p (t, curr->op, 0))
1308 { 1308 {
1309 tree tmpvar; 1309 tree tmpvar;
1310 gimple sum; 1310 gimple sum;
1311 enum tree_code subcode; 1311 enum tree_code subcode;
1312 tree newop1; 1312 tree newop1;
1313 tree newop2; 1313 tree newop2;
1314 gcc_assert (COMPARISON_CLASS_P (t));
1314 tmpvar = create_tmp_var (TREE_TYPE (t), NULL); 1315 tmpvar = create_tmp_var (TREE_TYPE (t), NULL);
1315 add_referenced_var (tmpvar); 1316 add_referenced_var (tmpvar);
1316 extract_ops_from_tree (t, &subcode, &newop1, &newop2); 1317 extract_ops_from_tree (t, &subcode, &newop1, &newop2);
1318 STRIP_USELESS_TYPE_CONVERSION (newop1);
1319 STRIP_USELESS_TYPE_CONVERSION (newop2);
1320 gcc_checking_assert (is_gimple_val (newop1)
1321 && is_gimple_val (newop2));
1317 sum = build_and_add_sum (tmpvar, newop1, newop2, subcode); 1322 sum = build_and_add_sum (tmpvar, newop1, newop2, subcode);
1318 curr->op = gimple_get_lhs (sum); 1323 curr->op = gimple_get_lhs (sum);
1319 } 1324 }
1320 return true; 1325 return true;
1321 } 1326 }
1779 gimple_set_visited (stmt, true); 1784 gimple_set_visited (stmt, true);
1780 1785
1781 if (TREE_CODE (binlhs) == SSA_NAME) 1786 if (TREE_CODE (binlhs) == SSA_NAME)
1782 { 1787 {
1783 binlhsdef = SSA_NAME_DEF_STMT (binlhs); 1788 binlhsdef = SSA_NAME_DEF_STMT (binlhs);
1784 binlhsisreassoc = is_reassociable_op (binlhsdef, rhscode, loop); 1789 binlhsisreassoc = (is_reassociable_op (binlhsdef, rhscode, loop)
1790 && !stmt_could_throw_p (binlhsdef));
1785 } 1791 }
1786 1792
1787 if (TREE_CODE (binrhs) == SSA_NAME) 1793 if (TREE_CODE (binrhs) == SSA_NAME)
1788 { 1794 {
1789 binrhsdef = SSA_NAME_DEF_STMT (binrhs); 1795 binrhsdef = SSA_NAME_DEF_STMT (binrhs);
1790 binrhsisreassoc = is_reassociable_op (binrhsdef, rhscode, loop); 1796 binrhsisreassoc = (is_reassociable_op (binrhsdef, rhscode, loop)
1797 && !stmt_could_throw_p (binrhsdef));
1791 } 1798 }
1792 1799
1793 /* If the LHS is not reassociable, but the RHS is, we need to swap 1800 /* If the LHS is not reassociable, but the RHS is, we need to swap
1794 them. If neither is reassociable, there is nothing we can do, so 1801 them. If neither is reassociable, there is nothing we can do, so
1795 just put them in the ops vector. If the LHS is reassociable, 1802 just put them in the ops vector. If the LHS is reassociable,
1859 repropagate_negates (void) 1866 repropagate_negates (void)
1860 { 1867 {
1861 unsigned int i = 0; 1868 unsigned int i = 0;
1862 tree negate; 1869 tree negate;
1863 1870
1864 for (i = 0; VEC_iterate (tree, plus_negates, i, negate); i++) 1871 FOR_EACH_VEC_ELT (tree, plus_negates, i, negate)
1865 { 1872 {
1866 gimple user = get_single_immediate_use (negate); 1873 gimple user = get_single_immediate_use (negate);
1867 1874
1868 if (!user || !is_gimple_assign (user)) 1875 if (!user || !is_gimple_assign (user))
1869 continue; 1876 continue;
1944 1951
1945 static bool 1952 static bool
1946 can_reassociate_p (tree op) 1953 can_reassociate_p (tree op)
1947 { 1954 {
1948 tree type = TREE_TYPE (op); 1955 tree type = TREE_TYPE (op);
1949 if (INTEGRAL_TYPE_P (type) 1956 if ((INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_WRAPS (type))
1950 || NON_SAT_FIXED_POINT_TYPE_P (type) 1957 || NON_SAT_FIXED_POINT_TYPE_P (type)
1951 || (flag_associative_math && FLOAT_TYPE_P (type))) 1958 || (flag_associative_math && FLOAT_TYPE_P (type)))
1952 return true; 1959 return true;
1953 return false; 1960 return false;
1954 } 1961 }
2020 2027
2021 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) 2028 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
2022 { 2029 {
2023 gimple stmt = gsi_stmt (gsi); 2030 gimple stmt = gsi_stmt (gsi);
2024 2031
2025 if (is_gimple_assign (stmt)) 2032 if (is_gimple_assign (stmt)
2033 && !stmt_could_throw_p (stmt))
2026 { 2034 {
2027 tree lhs, rhs1, rhs2; 2035 tree lhs, rhs1, rhs2;
2028 enum tree_code rhs_code = gimple_assign_rhs_code (stmt); 2036 enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
2029 2037
2030 /* If this is not a gimple binary expression, there is 2038 /* If this is not a gimple binary expression, there is
2060 2068
2061 lhs = gimple_assign_lhs (stmt); 2069 lhs = gimple_assign_lhs (stmt);
2062 rhs1 = gimple_assign_rhs1 (stmt); 2070 rhs1 = gimple_assign_rhs1 (stmt);
2063 rhs2 = gimple_assign_rhs2 (stmt); 2071 rhs2 = gimple_assign_rhs2 (stmt);
2064 2072
2065 if (!can_reassociate_p (lhs) 2073 /* For non-bit or min/max operations we can't associate
2066 || !can_reassociate_p (rhs1) 2074 all types. Verify that here. */
2067 || !can_reassociate_p (rhs2)) 2075 if (rhs_code != BIT_IOR_EXPR
2076 && rhs_code != BIT_AND_EXPR
2077 && rhs_code != BIT_XOR_EXPR
2078 && rhs_code != MIN_EXPR
2079 && rhs_code != MAX_EXPR
2080 && (!can_reassociate_p (lhs)
2081 || !can_reassociate_p (rhs1)
2082 || !can_reassociate_p (rhs2)))
2068 continue; 2083 continue;
2069 2084
2070 if (associative_tree_code (rhs_code)) 2085 if (associative_tree_code (rhs_code))
2071 { 2086 {
2072 VEC(operand_entry_t, heap) *ops = NULL; 2087 VEC(operand_entry_t, heap) *ops = NULL;
2076 if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs)) 2091 if (TREE_CODE (lhs) == SSA_NAME && has_zero_uses (lhs))
2077 continue; 2092 continue;
2078 2093
2079 gimple_set_visited (stmt, true); 2094 gimple_set_visited (stmt, true);
2080 linearize_expr_tree (&ops, stmt, true, true); 2095 linearize_expr_tree (&ops, stmt, true, true);
2081 qsort (VEC_address (operand_entry_t, ops), 2096 VEC_qsort (operand_entry_t, ops, sort_by_operand_rank);
2082 VEC_length (operand_entry_t, ops),
2083 sizeof (operand_entry_t),
2084 sort_by_operand_rank);
2085 optimize_ops_list (rhs_code, &ops); 2097 optimize_ops_list (rhs_code, &ops);
2086 if (undistribute_ops_list (rhs_code, &ops, 2098 if (undistribute_ops_list (rhs_code, &ops,
2087 loop_containing_stmt (stmt))) 2099 loop_containing_stmt (stmt)))
2088 { 2100 {
2089 qsort (VEC_address (operand_entry_t, ops), 2101 VEC_qsort (operand_entry_t, ops, sort_by_operand_rank);
2090 VEC_length (operand_entry_t, ops),
2091 sizeof (operand_entry_t),
2092 sort_by_operand_rank);
2093 optimize_ops_list (rhs_code, &ops); 2102 optimize_ops_list (rhs_code, &ops);
2094 } 2103 }
2095 2104
2096 if (VEC_length (operand_entry_t, ops) == 1) 2105 if (VEC_length (operand_entry_t, ops) == 1)
2097 { 2106 {
2136 dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops) 2145 dump_ops_vector (FILE *file, VEC (operand_entry_t, heap) *ops)
2137 { 2146 {
2138 operand_entry_t oe; 2147 operand_entry_t oe;
2139 unsigned int i; 2148 unsigned int i;
2140 2149
2141 for (i = 0; VEC_iterate (operand_entry_t, ops, i, oe); i++) 2150 FOR_EACH_VEC_ELT (operand_entry_t, ops, i, oe)
2142 { 2151 {
2143 fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank); 2152 fprintf (file, "Op %d -> rank: %d, tree: ", i, oe->rank);
2144 print_generic_expr (file, oe->op, 0); 2153 print_generic_expr (file, oe->op, 0);
2145 } 2154 }
2146 } 2155 }
2147 2156
2148 /* Dump the operand entry vector OPS to STDERR. */ 2157 /* Dump the operand entry vector OPS to STDERR. */
2149 2158
2150 void 2159 DEBUG_FUNCTION void
2151 debug_ops_vector (VEC (operand_entry_t, heap) *ops) 2160 debug_ops_vector (VEC (operand_entry_t, heap) *ops)
2152 { 2161 {
2153 dump_ops_vector (stderr, ops); 2162 dump_ops_vector (stderr, ops);
2154 } 2163 }
2155 2164
2187 operand_rank = pointer_map_create (); 2196 operand_rank = pointer_map_create ();
2188 2197
2189 /* Give each argument a distinct rank. */ 2198 /* Give each argument a distinct rank. */
2190 for (param = DECL_ARGUMENTS (current_function_decl); 2199 for (param = DECL_ARGUMENTS (current_function_decl);
2191 param; 2200 param;
2192 param = TREE_CHAIN (param)) 2201 param = DECL_CHAIN (param))
2193 { 2202 {
2194 if (gimple_default_def (cfun, param) != NULL) 2203 if (gimple_default_def (cfun, param) != NULL)
2195 { 2204 {
2196 tree def = gimple_default_def (cfun, param); 2205 tree def = gimple_default_def (cfun, param);
2197 insert_operand_rank (def, ++rank); 2206 insert_operand_rank (def, ++rank);
2271 TV_TREE_REASSOC, /* tv_id */ 2280 TV_TREE_REASSOC, /* tv_id */
2272 PROP_cfg | PROP_ssa, /* properties_required */ 2281 PROP_cfg | PROP_ssa, /* properties_required */
2273 0, /* properties_provided */ 2282 0, /* properties_provided */
2274 0, /* properties_destroyed */ 2283 0, /* properties_destroyed */
2275 0, /* todo_flags_start */ 2284 0, /* todo_flags_start */
2276 TODO_dump_func | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */ 2285 TODO_verify_ssa
2286 | TODO_verify_flow
2287 | TODO_dump_func
2288 | TODO_ggc_collect /* todo_flags_finish */
2277 } 2289 }
2278 }; 2290 };
2279 2291