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 }