Mercurial > hg > CbC > CbC_gcc
comparison gcc/gimple-ssa-strength-reduction.c @ 132:d34655255c78
update gcc-8.2
author | mir3636 |
---|---|
date | Thu, 25 Oct 2018 10:21:07 +0900 |
parents | 84e7813d76e9 |
children | 1830386684a0 |
comparison
equal
deleted
inserted
replaced
130:e108057fa461 | 132:d34655255c78 |
---|---|
1 /* Straight-line strength reduction. | 1 /* Straight-line strength reduction. |
2 Copyright (C) 2012-2017 Free Software Foundation, Inc. | 2 Copyright (C) 2012-2018 Free Software Foundation, Inc. |
3 Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com> | 3 Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com> |
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 |
53 #include "tree-cfg.h" | 53 #include "tree-cfg.h" |
54 #include "domwalk.h" | 54 #include "domwalk.h" |
55 #include "params.h" | 55 #include "params.h" |
56 #include "tree-ssa-address.h" | 56 #include "tree-ssa-address.h" |
57 #include "tree-affine.h" | 57 #include "tree-affine.h" |
58 #include "tree-eh.h" | |
58 #include "builtins.h" | 59 #include "builtins.h" |
59 | 60 |
60 /* Information about a strength reduction candidate. Each statement | 61 /* Information about a strength reduction candidate. Each statement |
61 in the candidate table represents an expression of one of the | 62 in the candidate table represents an expression of one of the |
62 following forms (the special case of CAND_REF will be described | 63 following forms (the special case of CAND_REF will be described |
263 A statement may be useful in more than one way (e.g., due to | 264 A statement may be useful in more than one way (e.g., due to |
264 commutativity). So we can have multiple "interpretations" | 265 commutativity). So we can have multiple "interpretations" |
265 of a statement. */ | 266 of a statement. */ |
266 cand_idx next_interp; | 267 cand_idx next_interp; |
267 | 268 |
269 /* Index of the first candidate record in a chain for the same | |
270 statement. */ | |
271 cand_idx first_interp; | |
272 | |
268 /* Index of the basis statement S0, if any, in the candidate vector. */ | 273 /* Index of the basis statement S0, if any, in the candidate vector. */ |
269 cand_idx basis; | 274 cand_idx basis; |
270 | 275 |
271 /* First candidate for which this candidate is a basis, if one exists. */ | 276 /* First candidate for which this candidate is a basis, if one exists. */ |
272 cand_idx dependent; | 277 cand_idx dependent; |
683 c->cand_type = ctype; | 688 c->cand_type = ctype; |
684 c->stride_type = stype; | 689 c->stride_type = stype; |
685 c->kind = kind; | 690 c->kind = kind; |
686 c->cand_num = cand_vec.length () + 1; | 691 c->cand_num = cand_vec.length () + 1; |
687 c->next_interp = 0; | 692 c->next_interp = 0; |
693 c->first_interp = c->cand_num; | |
688 c->dependent = 0; | 694 c->dependent = 0; |
689 c->sibling = 0; | 695 c->sibling = 0; |
690 c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0; | 696 c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0; |
691 c->dead_savings = savings; | 697 c->dead_savings = savings; |
692 c->visited = 0; | 698 c->visited = 0; |
968 { | 974 { |
969 tree base = *pbase, offset = *poffset; | 975 tree base = *pbase, offset = *poffset; |
970 widest_int index = *pindex; | 976 widest_int index = *pindex; |
971 tree mult_op0, t1, t2, type; | 977 tree mult_op0, t1, t2, type; |
972 widest_int c1, c2, c3, c4, c5; | 978 widest_int c1, c2, c3, c4, c5; |
979 offset_int mem_offset; | |
973 | 980 |
974 if (!base | 981 if (!base |
975 || !offset | 982 || !offset |
976 || TREE_CODE (base) != MEM_REF | 983 || TREE_CODE (base) != MEM_REF |
984 || !mem_ref_offset (base).is_constant (&mem_offset) | |
977 || TREE_CODE (offset) != MULT_EXPR | 985 || TREE_CODE (offset) != MULT_EXPR |
978 || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST | 986 || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST |
979 || wi::umod_floor (index, BITS_PER_UNIT) != 0) | 987 || wi::umod_floor (index, BITS_PER_UNIT) != 0) |
980 return false; | 988 return false; |
981 | 989 |
982 t1 = TREE_OPERAND (base, 0); | 990 t1 = TREE_OPERAND (base, 0); |
983 c1 = widest_int::from (mem_ref_offset (base), SIGNED); | 991 c1 = widest_int::from (mem_offset, SIGNED); |
984 type = TREE_TYPE (TREE_OPERAND (base, 1)); | 992 type = TREE_TYPE (TREE_OPERAND (base, 1)); |
985 | 993 |
986 mult_op0 = TREE_OPERAND (offset, 0); | 994 mult_op0 = TREE_OPERAND (offset, 0); |
987 c3 = wi::to_widest (TREE_OPERAND (offset, 1)); | 995 c3 = wi::to_widest (TREE_OPERAND (offset, 1)); |
988 | 996 |
1029 | 1037 |
1030 static void | 1038 static void |
1031 slsr_process_ref (gimple *gs) | 1039 slsr_process_ref (gimple *gs) |
1032 { | 1040 { |
1033 tree ref_expr, base, offset, type; | 1041 tree ref_expr, base, offset, type; |
1034 HOST_WIDE_INT bitsize, bitpos; | 1042 poly_int64 bitsize, bitpos; |
1035 machine_mode mode; | 1043 machine_mode mode; |
1036 int unsignedp, reversep, volatilep; | 1044 int unsignedp, reversep, volatilep; |
1037 slsr_cand_t c; | 1045 slsr_cand_t c; |
1038 | 1046 |
1039 if (gimple_vdef (gs)) | 1047 if (gimple_vdef (gs)) |
1047 && DECL_BIT_FIELD (TREE_OPERAND (ref_expr, 1)))) | 1055 && DECL_BIT_FIELD (TREE_OPERAND (ref_expr, 1)))) |
1048 return; | 1056 return; |
1049 | 1057 |
1050 base = get_inner_reference (ref_expr, &bitsize, &bitpos, &offset, &mode, | 1058 base = get_inner_reference (ref_expr, &bitsize, &bitpos, &offset, &mode, |
1051 &unsignedp, &reversep, &volatilep); | 1059 &unsignedp, &reversep, &volatilep); |
1052 if (reversep) | 1060 HOST_WIDE_INT cbitpos; |
1061 if (reversep || !bitpos.is_constant (&cbitpos)) | |
1053 return; | 1062 return; |
1054 widest_int index = bitpos; | 1063 widest_int index = cbitpos; |
1055 | 1064 |
1056 if (!restructure_reference (&base, &offset, &index, &type)) | 1065 if (!restructure_reference (&base, &offset, &index, &type)) |
1057 return; | 1066 return; |
1058 | 1067 |
1059 c = alloc_cand_and_find_basis (CAND_REF, gs, base, index, offset, | 1068 c = alloc_cand_and_find_basis (CAND_REF, gs, base, index, offset, |
1255 | 1264 |
1256 /* Record another interpretation of this statement assuming RHS1 | 1265 /* Record another interpretation of this statement assuming RHS1 |
1257 is the stride and RHS2 is the base expression. */ | 1266 is the stride and RHS2 is the base expression. */ |
1258 c2 = create_mul_ssa_cand (gs, rhs2, rhs1, speed); | 1267 c2 = create_mul_ssa_cand (gs, rhs2, rhs1, speed); |
1259 c->next_interp = c2->cand_num; | 1268 c->next_interp = c2->cand_num; |
1260 } | 1269 c2->first_interp = c->cand_num; |
1261 else | 1270 } |
1271 else if (TREE_CODE (rhs2) == INTEGER_CST) | |
1262 { | 1272 { |
1263 /* Record an interpretation for the multiply-immediate. */ | 1273 /* Record an interpretation for the multiply-immediate. */ |
1264 c = create_mul_imm_cand (gs, rhs1, rhs2, speed); | 1274 c = create_mul_imm_cand (gs, rhs1, rhs2, speed); |
1265 | 1275 |
1266 /* Add the interpretation to the statement-candidate mapping. */ | 1276 /* Add the interpretation to the statement-candidate mapping. */ |
1492 stride is not a pointer. */ | 1502 stride is not a pointer. */ |
1493 if (!POINTER_TYPE_P (TREE_TYPE (rhs1))) | 1503 if (!POINTER_TYPE_P (TREE_TYPE (rhs1))) |
1494 { | 1504 { |
1495 c2 = create_add_ssa_cand (gs, rhs2, rhs1, false, speed); | 1505 c2 = create_add_ssa_cand (gs, rhs2, rhs1, false, speed); |
1496 if (c) | 1506 if (c) |
1497 c->next_interp = c2->cand_num; | 1507 { |
1508 c->next_interp = c2->cand_num; | |
1509 c2->first_interp = c->cand_num; | |
1510 } | |
1498 else | 1511 else |
1499 add_cand_for_stmt (gs, c2); | 1512 add_cand_for_stmt (gs, c2); |
1500 } | 1513 } |
1501 } | 1514 } |
1502 else | 1515 else if (TREE_CODE (rhs2) == INTEGER_CST) |
1503 { | 1516 { |
1504 /* Record an interpretation for the add-immediate. */ | 1517 /* Record an interpretation for the add-immediate. */ |
1505 widest_int index = wi::to_widest (rhs2); | 1518 widest_int index = wi::to_widest (rhs2); |
1506 if (subtract_p) | 1519 if (subtract_p) |
1507 index = -index; | 1520 index = -index; |
1615 base_cand = base_cand_from_table (rhs1); | 1628 base_cand = base_cand_from_table (rhs1); |
1616 ctype = TREE_TYPE (lhs); | 1629 ctype = TREE_TYPE (lhs); |
1617 | 1630 |
1618 if (base_cand && base_cand->kind != CAND_PHI) | 1631 if (base_cand && base_cand->kind != CAND_PHI) |
1619 { | 1632 { |
1633 slsr_cand_t first_cand = NULL; | |
1634 | |
1620 while (base_cand) | 1635 while (base_cand) |
1621 { | 1636 { |
1622 /* Propagate all data from the base candidate except the type, | 1637 /* Propagate all data from the base candidate except the type, |
1623 which comes from the cast, and the base candidate's cast, | 1638 which comes from the cast, and the base candidate's cast, |
1624 which is no longer applicable. */ | 1639 which is no longer applicable. */ |
1629 c = alloc_cand_and_find_basis (base_cand->kind, gs, | 1644 c = alloc_cand_and_find_basis (base_cand->kind, gs, |
1630 base_cand->base_expr, | 1645 base_cand->base_expr, |
1631 base_cand->index, base_cand->stride, | 1646 base_cand->index, base_cand->stride, |
1632 ctype, base_cand->stride_type, | 1647 ctype, base_cand->stride_type, |
1633 savings); | 1648 savings); |
1649 if (!first_cand) | |
1650 first_cand = c; | |
1651 | |
1652 if (first_cand != c) | |
1653 c->first_interp = first_cand->cand_num; | |
1654 | |
1634 if (base_cand->next_interp) | 1655 if (base_cand->next_interp) |
1635 base_cand = lookup_cand (base_cand->next_interp); | 1656 base_cand = lookup_cand (base_cand->next_interp); |
1636 else | 1657 else |
1637 base_cand = NULL; | 1658 base_cand = NULL; |
1638 } | 1659 } |
1651 c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0, | 1672 c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0, |
1652 integer_one_node, ctype, sizetype, 0); | 1673 integer_one_node, ctype, sizetype, 0); |
1653 c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0, | 1674 c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0, |
1654 integer_one_node, ctype, sizetype, 0); | 1675 integer_one_node, ctype, sizetype, 0); |
1655 c->next_interp = c2->cand_num; | 1676 c->next_interp = c2->cand_num; |
1677 c2->first_interp = c->cand_num; | |
1656 } | 1678 } |
1657 | 1679 |
1658 /* Add the first (or only) interpretation to the statement-candidate | 1680 /* Add the first (or only) interpretation to the statement-candidate |
1659 mapping. */ | 1681 mapping. */ |
1660 add_cand_for_stmt (gs, c); | 1682 add_cand_for_stmt (gs, c); |
1675 | 1697 |
1676 base_cand = base_cand_from_table (rhs1); | 1698 base_cand = base_cand_from_table (rhs1); |
1677 | 1699 |
1678 if (base_cand && base_cand->kind != CAND_PHI) | 1700 if (base_cand && base_cand->kind != CAND_PHI) |
1679 { | 1701 { |
1702 slsr_cand_t first_cand = NULL; | |
1703 | |
1680 while (base_cand) | 1704 while (base_cand) |
1681 { | 1705 { |
1682 /* Propagate all data from the base candidate. */ | 1706 /* Propagate all data from the base candidate. */ |
1683 if (has_single_use (rhs1)) | 1707 if (has_single_use (rhs1)) |
1684 savings = (base_cand->dead_savings | 1708 savings = (base_cand->dead_savings |
1687 c = alloc_cand_and_find_basis (base_cand->kind, gs, | 1711 c = alloc_cand_and_find_basis (base_cand->kind, gs, |
1688 base_cand->base_expr, | 1712 base_cand->base_expr, |
1689 base_cand->index, base_cand->stride, | 1713 base_cand->index, base_cand->stride, |
1690 base_cand->cand_type, | 1714 base_cand->cand_type, |
1691 base_cand->stride_type, savings); | 1715 base_cand->stride_type, savings); |
1716 if (!first_cand) | |
1717 first_cand = c; | |
1718 | |
1719 if (first_cand != c) | |
1720 c->first_interp = first_cand->cand_num; | |
1721 | |
1692 if (base_cand->next_interp) | 1722 if (base_cand->next_interp) |
1693 base_cand = lookup_cand (base_cand->next_interp); | 1723 base_cand = lookup_cand (base_cand->next_interp); |
1694 else | 1724 else |
1695 base_cand = NULL; | 1725 base_cand = NULL; |
1696 } | 1726 } |
1711 sizetype, 0); | 1741 sizetype, 0); |
1712 c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0, | 1742 c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0, |
1713 integer_one_node, TREE_TYPE (rhs1), | 1743 integer_one_node, TREE_TYPE (rhs1), |
1714 sizetype, 0); | 1744 sizetype, 0); |
1715 c->next_interp = c2->cand_num; | 1745 c->next_interp = c2->cand_num; |
1746 c2->first_interp = c->cand_num; | |
1716 } | 1747 } |
1717 | 1748 |
1718 /* Add the first (or only) interpretation to the statement-candidate | 1749 /* Add the first (or only) interpretation to the statement-candidate |
1719 mapping. */ | 1750 mapping. */ |
1720 add_cand_for_stmt (gs, c); | 1751 add_cand_for_stmt (gs, c); |
1741 | 1772 |
1742 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); | 1773 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); |
1743 gsi_next (&gsi)) | 1774 gsi_next (&gsi)) |
1744 { | 1775 { |
1745 gimple *gs = gsi_stmt (gsi); | 1776 gimple *gs = gsi_stmt (gsi); |
1777 | |
1778 if (stmt_could_throw_p (cfun, gs)) | |
1779 continue; | |
1746 | 1780 |
1747 if (gimple_vuse (gs) && gimple_assign_single_p (gs)) | 1781 if (gimple_vuse (gs) && gimple_assign_single_p (gs)) |
1748 slsr_process_ref (gs); | 1782 slsr_process_ref (gs); |
1749 | 1783 |
1750 else if (is_gimple_assign (gs) | 1784 else if (is_gimple_assign (gs) |
1878 gcc_unreachable (); | 1912 gcc_unreachable (); |
1879 } | 1913 } |
1880 print_generic_expr (dump_file, c->cand_type); | 1914 print_generic_expr (dump_file, c->cand_type); |
1881 fprintf (dump_file, "\n basis: %d dependent: %d sibling: %d\n", | 1915 fprintf (dump_file, "\n basis: %d dependent: %d sibling: %d\n", |
1882 c->basis, c->dependent, c->sibling); | 1916 c->basis, c->dependent, c->sibling); |
1883 fprintf (dump_file, " next-interp: %d dead-savings: %d\n", | 1917 fprintf (dump_file, |
1884 c->next_interp, c->dead_savings); | 1918 " next-interp: %d first-interp: %d dead-savings: %d\n", |
1919 c->next_interp, c->first_interp, c->dead_savings); | |
1885 if (c->def_phi) | 1920 if (c->def_phi) |
1886 fprintf (dump_file, " phi: %d\n", c->def_phi); | 1921 fprintf (dump_file, " phi: %d\n", c->def_phi); |
1887 fputs ("\n", dump_file); | 1922 fputs ("\n", dump_file); |
1888 } | 1923 } |
1889 | 1924 |
2138 if (bump == 0) | 2173 if (bump == 0) |
2139 { | 2174 { |
2140 tree lhs = gimple_assign_lhs (c->cand_stmt); | 2175 tree lhs = gimple_assign_lhs (c->cand_stmt); |
2141 gassign *copy_stmt = gimple_build_assign (lhs, basis_name); | 2176 gassign *copy_stmt = gimple_build_assign (lhs, basis_name); |
2142 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); | 2177 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); |
2143 slsr_cand_t cc = c; | 2178 slsr_cand_t cc = lookup_cand (c->first_interp); |
2144 gimple_set_location (copy_stmt, gimple_location (c->cand_stmt)); | 2179 gimple_set_location (copy_stmt, gimple_location (c->cand_stmt)); |
2145 gsi_replace (&gsi, copy_stmt, false); | 2180 gsi_replace (&gsi, copy_stmt, false); |
2146 c->cand_stmt = copy_stmt; | 2181 while (cc) |
2147 while (cc->next_interp) | 2182 { |
2148 { | |
2149 cc = lookup_cand (cc->next_interp); | |
2150 cc->cand_stmt = copy_stmt; | 2183 cc->cand_stmt = copy_stmt; |
2184 cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL; | |
2151 } | 2185 } |
2152 if (dump_file && (dump_flags & TDF_DETAILS)) | 2186 if (dump_file && (dump_flags & TDF_DETAILS)) |
2153 stmt_to_print = copy_stmt; | 2187 stmt_to_print = copy_stmt; |
2154 } | 2188 } |
2155 else | 2189 else |
2172 } | 2206 } |
2173 } | 2207 } |
2174 else | 2208 else |
2175 { | 2209 { |
2176 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); | 2210 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); |
2177 slsr_cand_t cc = c; | 2211 slsr_cand_t cc = lookup_cand (c->first_interp); |
2178 gimple_assign_set_rhs_with_ops (&gsi, code, basis_name, bump_tree); | 2212 gimple_assign_set_rhs_with_ops (&gsi, code, basis_name, bump_tree); |
2179 update_stmt (gsi_stmt (gsi)); | 2213 update_stmt (gsi_stmt (gsi)); |
2180 c->cand_stmt = gsi_stmt (gsi); | 2214 while (cc) |
2181 while (cc->next_interp) | |
2182 { | 2215 { |
2183 cc = lookup_cand (cc->next_interp); | |
2184 cc->cand_stmt = gsi_stmt (gsi); | 2216 cc->cand_stmt = gsi_stmt (gsi); |
2217 cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL; | |
2185 } | 2218 } |
2186 if (dump_file && (dump_flags & TDF_DETAILS)) | 2219 if (dump_file && (dump_flags & TDF_DETAILS)) |
2187 stmt_to_print = gsi_stmt (gsi); | 2220 stmt_to_print = gsi_stmt (gsi); |
2188 } | 2221 } |
2189 } | 2222 } |
2744 phi_cand->visited = 1; | 2777 phi_cand->visited = 1; |
2745 | 2778 |
2746 for (i = 0; i < gimple_phi_num_args (phi); i++) | 2779 for (i = 0; i < gimple_phi_num_args (phi); i++) |
2747 { | 2780 { |
2748 tree arg = gimple_phi_arg_def (phi, i); | 2781 tree arg = gimple_phi_arg_def (phi, i); |
2749 | 2782 gimple *arg_def = SSA_NAME_DEF_STMT (arg); |
2750 if (!operand_equal_p (arg, phi_cand->base_expr, 0)) | 2783 |
2751 { | 2784 if (gimple_code (arg_def) == GIMPLE_PHI) |
2752 gimple *arg_def = SSA_NAME_DEF_STMT (arg); | 2785 record_phi_increments_1 (basis, arg_def); |
2753 | 2786 else |
2754 if (gimple_code (arg_def) == GIMPLE_PHI) | 2787 { |
2755 record_phi_increments_1 (basis, arg_def); | 2788 widest_int diff; |
2789 | |
2790 if (operand_equal_p (arg, phi_cand->base_expr, 0)) | |
2791 { | |
2792 diff = -basis->index; | |
2793 record_increment (phi_cand, diff, PHI_ADJUST); | |
2794 } | |
2756 else | 2795 else |
2757 { | 2796 { |
2758 slsr_cand_t arg_cand = base_cand_from_table (arg); | 2797 slsr_cand_t arg_cand = base_cand_from_table (arg); |
2759 widest_int diff = arg_cand->index - basis->index; | 2798 diff = arg_cand->index - basis->index; |
2760 record_increment (arg_cand, diff, PHI_ADJUST); | 2799 record_increment (arg_cand, diff, PHI_ADJUST); |
2761 } | 2800 } |
2762 } | 2801 } |
2763 } | 2802 } |
2764 } | 2803 } |
2829 phi_cand->visited = 1; | 2868 phi_cand->visited = 1; |
2830 | 2869 |
2831 for (i = 0; i < gimple_phi_num_args (phi); i++) | 2870 for (i = 0; i < gimple_phi_num_args (phi); i++) |
2832 { | 2871 { |
2833 tree arg = gimple_phi_arg_def (phi, i); | 2872 tree arg = gimple_phi_arg_def (phi, i); |
2834 | 2873 gimple *arg_def = SSA_NAME_DEF_STMT (arg); |
2835 if (!operand_equal_p (arg, phi_cand->base_expr, 0)) | 2874 |
2836 { | 2875 if (gimple_code (arg_def) == GIMPLE_PHI) |
2837 gimple *arg_def = SSA_NAME_DEF_STMT (arg); | 2876 { |
2838 | 2877 int feeding_savings = 0; |
2839 if (gimple_code (arg_def) == GIMPLE_PHI) | 2878 tree feeding_var = gimple_phi_result (arg_def); |
2879 cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings); | |
2880 if (uses_consumed_by_stmt (feeding_var, phi)) | |
2881 *savings += feeding_savings; | |
2882 } | |
2883 else | |
2884 { | |
2885 widest_int diff; | |
2886 slsr_cand_t arg_cand; | |
2887 | |
2888 /* When the PHI argument is just a pass-through to the base | |
2889 expression of the hidden basis, the difference is zero minus | |
2890 the index of the basis. There is no potential savings by | |
2891 eliminating a statement in this case. */ | |
2892 if (operand_equal_p (arg, phi_cand->base_expr, 0)) | |
2840 { | 2893 { |
2841 int feeding_savings = 0; | 2894 arg_cand = (slsr_cand_t)NULL; |
2842 tree feeding_var = gimple_phi_result (arg_def); | 2895 diff = -basis->index; |
2843 cost += phi_incr_cost_1 (c, incr, arg_def, &feeding_savings); | |
2844 if (uses_consumed_by_stmt (feeding_var, phi)) | |
2845 *savings += feeding_savings; | |
2846 } | 2896 } |
2847 else | 2897 else |
2848 { | 2898 { |
2849 slsr_cand_t arg_cand = base_cand_from_table (arg); | 2899 arg_cand = base_cand_from_table (arg); |
2850 widest_int diff = arg_cand->index - basis->index; | 2900 diff = arg_cand->index - basis->index; |
2851 | 2901 } |
2852 if (incr == diff) | 2902 |
2903 if (incr == diff) | |
2904 { | |
2905 tree basis_lhs = gimple_assign_lhs (basis->cand_stmt); | |
2906 cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs))); | |
2907 if (arg_cand) | |
2853 { | 2908 { |
2854 tree basis_lhs = gimple_assign_lhs (basis->cand_stmt); | |
2855 tree lhs = gimple_assign_lhs (arg_cand->cand_stmt); | 2909 tree lhs = gimple_assign_lhs (arg_cand->cand_stmt); |
2856 cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs))); | |
2857 if (uses_consumed_by_stmt (lhs, phi)) | 2910 if (uses_consumed_by_stmt (lhs, phi)) |
2858 *savings += stmt_cost (arg_cand->cand_stmt, true); | 2911 *savings += stmt_cost (arg_cand->cand_stmt, true); |
2859 } | 2912 } |
2860 } | 2913 } |
2861 } | 2914 } |
3081 size, instead calculate the total cost reduction from replacing | 3134 size, instead calculate the total cost reduction from replacing |
3082 all candidates with this increment. */ | 3135 all candidates with this increment. */ |
3083 else if (first_dep->kind == CAND_MULT) | 3136 else if (first_dep->kind == CAND_MULT) |
3084 { | 3137 { |
3085 int cost = mult_by_coeff_cost (incr, mode, speed); | 3138 int cost = mult_by_coeff_cost (incr, mode, speed); |
3086 int repl_savings = mul_cost (speed, mode) - add_cost (speed, mode); | 3139 int repl_savings; |
3140 | |
3141 if (tree_fits_shwi_p (first_dep->stride)) | |
3142 { | |
3143 HOST_WIDE_INT hwi_stride = tree_to_shwi (first_dep->stride); | |
3144 repl_savings = mult_by_coeff_cost (hwi_stride, mode, speed); | |
3145 } | |
3146 else | |
3147 repl_savings = mul_cost (speed, mode); | |
3148 repl_savings -= add_cost (speed, mode); | |
3149 | |
3087 if (speed) | 3150 if (speed) |
3088 cost = lowest_cost_path (cost, repl_savings, first_dep, | 3151 cost = lowest_cost_path (cost, repl_savings, first_dep, |
3089 incr_vec[i].incr, COUNT_PHIS); | 3152 incr_vec[i].incr, COUNT_PHIS); |
3090 else | 3153 else |
3091 cost -= total_savings (repl_savings, first_dep, incr_vec[i].incr, | 3154 cost -= total_savings (repl_savings, first_dep, incr_vec[i].incr, |
3183 slsr_cand_t phi_cand = *stmt_cand_map->get (phi); | 3246 slsr_cand_t phi_cand = *stmt_cand_map->get (phi); |
3184 | 3247 |
3185 for (i = 0; i < gimple_phi_num_args (phi); i++) | 3248 for (i = 0; i < gimple_phi_num_args (phi); i++) |
3186 { | 3249 { |
3187 tree arg = gimple_phi_arg_def (phi, i); | 3250 tree arg = gimple_phi_arg_def (phi, i); |
3188 | 3251 gimple *arg_def = SSA_NAME_DEF_STMT (arg); |
3189 if (!operand_equal_p (arg, phi_cand->base_expr, 0)) | 3252 |
3190 { | 3253 if (gimple_code (arg_def) == GIMPLE_PHI) |
3191 gimple *arg_def = SSA_NAME_DEF_STMT (arg); | 3254 ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd, where); |
3192 | 3255 else |
3193 if (gimple_code (arg_def) == GIMPLE_PHI) | 3256 { |
3194 ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd, | 3257 widest_int diff; |
3195 where); | 3258 |
3196 else | 3259 if (operand_equal_p (arg, phi_cand->base_expr, 0)) |
3260 diff = -basis->index; | |
3261 else | |
3197 { | 3262 { |
3198 slsr_cand_t arg_cand = base_cand_from_table (arg); | 3263 slsr_cand_t arg_cand = base_cand_from_table (arg); |
3199 widest_int diff = arg_cand->index - basis->index; | 3264 diff = arg_cand->index - basis->index; |
3200 basic_block pred = gimple_phi_arg_edge (phi, i)->src; | |
3201 | |
3202 if ((incr == diff) || (!address_arithmetic_p && incr == -diff)) | |
3203 ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where); | |
3204 } | 3265 } |
3266 | |
3267 basic_block pred = gimple_phi_arg_edge (phi, i)->src; | |
3268 | |
3269 if ((incr == diff) || (!address_arithmetic_p && incr == -diff)) | |
3270 ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where); | |
3205 } | 3271 } |
3206 } | 3272 } |
3207 | 3273 |
3208 return ncd; | 3274 return ncd; |
3209 } | 3275 } |
3334 if (dump_file && (dump_flags & TDF_DETAILS)) | 3400 if (dump_file && (dump_flags & TDF_DETAILS)) |
3335 { | 3401 { |
3336 fputs ("Using existing initializer: ", dump_file); | 3402 fputs ("Using existing initializer: ", dump_file); |
3337 print_gimple_stmt (dump_file, | 3403 print_gimple_stmt (dump_file, |
3338 SSA_NAME_DEF_STMT (incr_vec[i].initializer), | 3404 SSA_NAME_DEF_STMT (incr_vec[i].initializer), |
3339 0, 0); | 3405 0, TDF_NONE); |
3340 } | 3406 } |
3341 continue; | 3407 continue; |
3342 } | 3408 } |
3343 | 3409 |
3344 /* Find the block that most closely dominates all candidates | 3410 /* Find the block that most closely dominates all candidates |
3416 if (cast_stmt) | 3482 if (cast_stmt) |
3417 { | 3483 { |
3418 gsi_insert_after (&gsi, cast_stmt, GSI_NEW_STMT); | 3484 gsi_insert_after (&gsi, cast_stmt, GSI_NEW_STMT); |
3419 gimple_set_location (cast_stmt, loc); | 3485 gimple_set_location (cast_stmt, loc); |
3420 } | 3486 } |
3421 gsi_insert_after (&gsi, init_stmt, GSI_SAME_STMT); | 3487 gsi_insert_after (&gsi, init_stmt, GSI_NEW_STMT); |
3422 } | 3488 } |
3423 | 3489 |
3424 gimple_set_location (init_stmt, gimple_location (basis_stmt)); | 3490 gimple_set_location (init_stmt, gimple_location (basis_stmt)); |
3425 } | 3491 } |
3426 | 3492 |
3470 | 3536 |
3471 if (!dominated_by_p (CDI_DOMINATORS, pred_bb, basis_bb)) | 3537 if (!dominated_by_p (CDI_DOMINATORS, pred_bb, basis_bb)) |
3472 return false; | 3538 return false; |
3473 | 3539 |
3474 tree arg = gimple_phi_arg_def (phi, i); | 3540 tree arg = gimple_phi_arg_def (phi, i); |
3475 | 3541 gimple *arg_def = SSA_NAME_DEF_STMT (arg); |
3476 if (!operand_equal_p (arg, phi_cand->base_expr, 0)) | 3542 |
3477 { | 3543 if (gimple_code (arg_def) == GIMPLE_PHI) |
3478 gimple *arg_def = SSA_NAME_DEF_STMT (arg); | 3544 { |
3479 | 3545 if (!all_phi_incrs_profitable_1 (c, as_a <gphi *> (arg_def), spread) |
3480 if (gimple_code (arg_def) == GIMPLE_PHI) | 3546 || *spread > MAX_SPREAD) |
3481 { | 3547 return false; |
3482 if (!all_phi_incrs_profitable_1 (c, as_a <gphi *> (arg_def), | 3548 } |
3483 spread) | 3549 else |
3484 || *spread > MAX_SPREAD) | 3550 { |
3485 return false; | 3551 int j; |
3486 } | 3552 widest_int increment; |
3553 | |
3554 if (operand_equal_p (arg, phi_cand->base_expr, 0)) | |
3555 increment = -basis->index; | |
3487 else | 3556 else |
3488 { | 3557 { |
3489 int j; | |
3490 slsr_cand_t arg_cand = base_cand_from_table (arg); | 3558 slsr_cand_t arg_cand = base_cand_from_table (arg); |
3491 widest_int increment = arg_cand->index - basis->index; | 3559 increment = arg_cand->index - basis->index; |
3492 | |
3493 if (!address_arithmetic_p && wi::neg_p (increment)) | |
3494 increment = -increment; | |
3495 | |
3496 j = incr_vec_index (increment); | |
3497 | |
3498 if (dump_file && (dump_flags & TDF_DETAILS)) | |
3499 { | |
3500 fprintf (dump_file, " Conditional candidate %d, phi: ", | |
3501 c->cand_num); | |
3502 print_gimple_stmt (dump_file, phi, 0); | |
3503 fputs (" increment: ", dump_file); | |
3504 print_decs (increment, dump_file); | |
3505 if (j < 0) | |
3506 fprintf (dump_file, | |
3507 "\n Not replaced; incr_vec overflow.\n"); | |
3508 else { | |
3509 fprintf (dump_file, "\n cost: %d\n", incr_vec[j].cost); | |
3510 if (profitable_increment_p (j)) | |
3511 fputs (" Replacing...\n", dump_file); | |
3512 else | |
3513 fputs (" Not replaced.\n", dump_file); | |
3514 } | |
3515 } | |
3516 | |
3517 if (j < 0 || !profitable_increment_p (j)) | |
3518 return false; | |
3519 } | 3560 } |
3561 | |
3562 if (!address_arithmetic_p && wi::neg_p (increment)) | |
3563 increment = -increment; | |
3564 | |
3565 j = incr_vec_index (increment); | |
3566 | |
3567 if (dump_file && (dump_flags & TDF_DETAILS)) | |
3568 { | |
3569 fprintf (dump_file, " Conditional candidate %d, phi: ", | |
3570 c->cand_num); | |
3571 print_gimple_stmt (dump_file, phi, 0); | |
3572 fputs (" increment: ", dump_file); | |
3573 print_decs (increment, dump_file); | |
3574 if (j < 0) | |
3575 fprintf (dump_file, | |
3576 "\n Not replaced; incr_vec overflow.\n"); | |
3577 else { | |
3578 fprintf (dump_file, "\n cost: %d\n", incr_vec[j].cost); | |
3579 if (profitable_increment_p (j)) | |
3580 fputs (" Replacing...\n", dump_file); | |
3581 else | |
3582 fputs (" Not replaced.\n", dump_file); | |
3583 } | |
3584 } | |
3585 | |
3586 if (j < 0 || !profitable_increment_p (j)) | |
3587 return false; | |
3520 } | 3588 } |
3521 } | 3589 } |
3522 | 3590 |
3523 return true; | 3591 return true; |
3524 } | 3592 } |
3578 || !operand_equal_p (new_rhs2, old_rhs2, 0)) | 3646 || !operand_equal_p (new_rhs2, old_rhs2, 0)) |
3579 && (!operand_equal_p (new_rhs1, old_rhs2, 0) | 3647 && (!operand_equal_p (new_rhs1, old_rhs2, 0) |
3580 || !operand_equal_p (new_rhs2, old_rhs1, 0)))) | 3648 || !operand_equal_p (new_rhs2, old_rhs1, 0)))) |
3581 { | 3649 { |
3582 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); | 3650 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); |
3583 slsr_cand_t cc = c; | 3651 slsr_cand_t cc = lookup_cand (c->first_interp); |
3584 gimple_assign_set_rhs_with_ops (&gsi, new_code, new_rhs1, new_rhs2); | 3652 gimple_assign_set_rhs_with_ops (&gsi, new_code, new_rhs1, new_rhs2); |
3585 update_stmt (gsi_stmt (gsi)); | 3653 update_stmt (gsi_stmt (gsi)); |
3586 c->cand_stmt = gsi_stmt (gsi); | 3654 while (cc) |
3587 while (cc->next_interp) | 3655 { |
3588 { | |
3589 cc = lookup_cand (cc->next_interp); | |
3590 cc->cand_stmt = gsi_stmt (gsi); | 3656 cc->cand_stmt = gsi_stmt (gsi); |
3657 cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL; | |
3591 } | 3658 } |
3592 | 3659 |
3593 if (dump_file && (dump_flags & TDF_DETAILS)) | 3660 if (dump_file && (dump_flags & TDF_DETAILS)) |
3594 return gsi_stmt (gsi); | 3661 return gsi_stmt (gsi); |
3595 } | 3662 } |
3617 | 3684 |
3618 orig_code = gimple_assign_rhs_code (c->cand_stmt); | 3685 orig_code = gimple_assign_rhs_code (c->cand_stmt); |
3619 orig_rhs1 = gimple_assign_rhs1 (c->cand_stmt); | 3686 orig_rhs1 = gimple_assign_rhs1 (c->cand_stmt); |
3620 orig_rhs2 = gimple_assign_rhs2 (c->cand_stmt); | 3687 orig_rhs2 = gimple_assign_rhs2 (c->cand_stmt); |
3621 cand_incr = cand_increment (c); | 3688 cand_incr = cand_increment (c); |
3689 | |
3690 /* If orig_rhs2 is NULL, we have already replaced this in situ with | |
3691 a copy statement under another interpretation. */ | |
3692 if (!orig_rhs2) | |
3693 return; | |
3622 | 3694 |
3623 if (dump_file && (dump_flags & TDF_DETAILS)) | 3695 if (dump_file && (dump_flags & TDF_DETAILS)) |
3624 { | 3696 { |
3625 fputs ("Replacing: ", dump_file); | 3697 fputs ("Replacing: ", dump_file); |
3626 print_gimple_stmt (dump_file, c->cand_stmt, 0); | 3698 print_gimple_stmt (dump_file, c->cand_stmt, 0); |
3690 if (orig_code != MINUS_EXPR | 3762 if (orig_code != MINUS_EXPR |
3691 || !operand_equal_p (basis_name, orig_rhs1, 0) | 3763 || !operand_equal_p (basis_name, orig_rhs1, 0) |
3692 || !operand_equal_p (rhs2, orig_rhs2, 0)) | 3764 || !operand_equal_p (rhs2, orig_rhs2, 0)) |
3693 { | 3765 { |
3694 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); | 3766 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); |
3695 slsr_cand_t cc = c; | 3767 slsr_cand_t cc = lookup_cand (c->first_interp); |
3696 gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, basis_name, rhs2); | 3768 gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, basis_name, rhs2); |
3697 update_stmt (gsi_stmt (gsi)); | 3769 update_stmt (gsi_stmt (gsi)); |
3698 c->cand_stmt = gsi_stmt (gsi); | 3770 while (cc) |
3699 while (cc->next_interp) | |
3700 { | 3771 { |
3701 cc = lookup_cand (cc->next_interp); | |
3702 cc->cand_stmt = gsi_stmt (gsi); | 3772 cc->cand_stmt = gsi_stmt (gsi); |
3773 cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL; | |
3703 } | 3774 } |
3704 | 3775 |
3705 if (dump_file && (dump_flags & TDF_DETAILS)) | 3776 if (dump_file && (dump_flags & TDF_DETAILS)) |
3706 stmt_to_print = gsi_stmt (gsi); | 3777 stmt_to_print = gsi_stmt (gsi); |
3707 } | 3778 } |
3717 | 3788 |
3718 if (types_compatible_p (lhs_type, basis_type)) | 3789 if (types_compatible_p (lhs_type, basis_type)) |
3719 { | 3790 { |
3720 gassign *copy_stmt = gimple_build_assign (lhs, basis_name); | 3791 gassign *copy_stmt = gimple_build_assign (lhs, basis_name); |
3721 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); | 3792 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); |
3722 slsr_cand_t cc = c; | 3793 slsr_cand_t cc = lookup_cand (c->first_interp); |
3723 gimple_set_location (copy_stmt, gimple_location (c->cand_stmt)); | 3794 gimple_set_location (copy_stmt, gimple_location (c->cand_stmt)); |
3724 gsi_replace (&gsi, copy_stmt, false); | 3795 gsi_replace (&gsi, copy_stmt, false); |
3725 c->cand_stmt = copy_stmt; | 3796 while (cc) |
3726 while (cc->next_interp) | |
3727 { | 3797 { |
3728 cc = lookup_cand (cc->next_interp); | |
3729 cc->cand_stmt = copy_stmt; | 3798 cc->cand_stmt = copy_stmt; |
3799 cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL; | |
3730 } | 3800 } |
3731 | 3801 |
3732 if (dump_file && (dump_flags & TDF_DETAILS)) | 3802 if (dump_file && (dump_flags & TDF_DETAILS)) |
3733 stmt_to_print = copy_stmt; | 3803 stmt_to_print = copy_stmt; |
3734 } | 3804 } |
3735 else | 3805 else |
3736 { | 3806 { |
3737 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); | 3807 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt); |
3738 gassign *cast_stmt = gimple_build_assign (lhs, NOP_EXPR, basis_name); | 3808 gassign *cast_stmt = gimple_build_assign (lhs, NOP_EXPR, basis_name); |
3739 slsr_cand_t cc = c; | 3809 slsr_cand_t cc = lookup_cand (c->first_interp); |
3740 gimple_set_location (cast_stmt, gimple_location (c->cand_stmt)); | 3810 gimple_set_location (cast_stmt, gimple_location (c->cand_stmt)); |
3741 gsi_replace (&gsi, cast_stmt, false); | 3811 gsi_replace (&gsi, cast_stmt, false); |
3742 c->cand_stmt = cast_stmt; | 3812 while (cc) |
3743 while (cc->next_interp) | |
3744 { | 3813 { |
3745 cc = lookup_cand (cc->next_interp); | |
3746 cc->cand_stmt = cast_stmt; | 3814 cc->cand_stmt = cast_stmt; |
3815 cc = cc->next_interp ? lookup_cand (cc->next_interp) : NULL; | |
3747 } | 3816 } |
3748 | 3817 |
3749 if (dump_file && (dump_flags & TDF_DETAILS)) | 3818 if (dump_file && (dump_flags & TDF_DETAILS)) |
3750 stmt_to_print = cast_stmt; | 3819 stmt_to_print = cast_stmt; |
3751 } | 3820 } |