Hi,
I originally posted a patch improving code generation for alias check in
vectorizer at https://gcc.gnu.org/ml/gcc-patches/2016-06/msg00929.html. Here
it's the 2nd version (better) patch. It detects data reference pair in which
the two references are only different to each other wrto index. In this case
the patch generates intersect range checks based on index of address of
reference, rather than the address of reference. Take example from patch's
comment, given below two data references:
DR_A DR_B
data-ref arr[i] arr[j]
base_object arr arr
index {i_0, +, 1}_loop {j_0, +, 1}_loop
The addresses and their index can be depicted as:
|<- ADDR_A ->| |<- ADDR_B ->|
------------------------------------------------------->
| | | | | | | | | |
------------------------------------------------------->
i_0 ... i_0+4 j_0 ... j_0+4
We can create expression based on index rather than address: (i_0 + 4 < j_0 ||
j_0 + 4 < i_0).
Also take example from spec2k/200.sixtrack/DACOP, gcc needs to generate alias
check for three pairs:
//pair 1
dr_a:
(Data Ref:
bb: 8
stmt: _92 = da.cc[_27];
ref: da.cc[_27];
)
dr_b:
(Data Ref:
bb: 8
stmt: da.cc[_93] = _92;
ref: da.cc[_93];
)
//pair 2
dr_a:
(Data Ref:
bb: 8
stmt: pretmp_29 = da.i2[_27];
ref: da.i2[_27];
)
dr_b:
(Data Ref:
bb: 8
stmt: da.i2[_93] = pretmp_29;
ref: da.i2[_93];
)
//pair 3
dr_a:
(Data Ref:
bb: 8
stmt: pretmp_28 = da.i1[_27];
ref: da.i1[_27];
)
dr_b:
(Data Ref:
bb: 8
stmt: da.i1[_93] = pretmp_28;
ref: da.i1[_93];
)
With this patch, code can be improved to:
<bb 7>:
_37 = (unsigned int) _6;
_106 = (unsigned int) _52;
_107 = _37 - _106;
_108 = _107 > 7;
_109 = (integer(kind=8)) _2;
_110 = _109 + 3;
_111 = (integer(kind=8)) _52;
_112 = _111 + -1;
_113 = _110 < _112;
_114 = (integer(kind=8)) _52;
_115 = _114 + 2;
_116 = (integer(kind=8)) _2;
_117 = _115 < _116;
_118 = _113 | _117;
_119 = _108 & _118;
_120 = (integer(kind=8)) _2;
_121 = _120 + 3;
_122 = (integer(kind=8)) _52;
_123 = _122 + -1;
_124 = _121 < _123;
_125 = (integer(kind=8)) _52;
_126 = _125 + 2;
_127 = (integer(kind=8)) _2;
_128 = _126 < _127;
_129 = _124 | _128;
_130 = _119 & _129;
_131 = (integer(kind=8)) _2;
_132 = _131 + 3;
_133 = (integer(kind=8)) _52;
_134 = _133 + -1;
_135 = _132 < _134;
_136 = (integer(kind=8)) _52;
_137 = _136 + 2;
_138 = (integer(kind=8)) _2;
_139 = _137 < _138;
_140 = _135 | _139;
_141 = _130 & _140;
if (_141 != 0)
goto <bb 8>;
else
goto <bb 20>;
Note this patch doesn't do local CSE, and common sub-expressions will be
optimized by later passes. I think this is OK because the redundancy is far
away from loops thus won't have bad effect (there is an opposite example/PR).
Bootstrap and test on x86_64 and AArch64, is it OK?
Thanks,
bin
2016-09-19 Bin Cheng <bin.ch...@arm.com>
* tree-vect-loop-manip.c (create_intersect_range_checks_index): New.
(create_intersect_range_checks): New.
(vect_create_cond_for_alias_checks): Call above function.diff --git a/gcc/tree-vect-loop-manip.c b/gcc/tree-vect-loop-manip.c
index 01d6bb1..c7d130e 100644
--- a/gcc/tree-vect-loop-manip.c
+++ b/gcc/tree-vect-loop-manip.c
@@ -2263,6 +2263,179 @@ vect_create_cond_for_align_checks (loop_vec_info
loop_vinfo,
*cond_expr = part_cond_expr;
}
+/* Given two data references and segment lengths described by DR_A and DR_B,
+ create expression checking if the two addresses ranges intersect with
+ each other based on index of the two addresses. This can only be done
+ if DR_A and DR_B referring to the same (array) object and the index is
+ the only difference. For example:
+
+ DR_A DR_B
+ data-ref arr[i] arr[j]
+ base_object arr arr
+ index {i_0, +, 1}_loop {j_0, +, 1}_loop
+
+ The addresses and their index are like:
+
+ |<- ADDR_A ->| |<- ADDR_B ->|
+ ------------------------------------------------------->
+ | | | | | | | | | |
+ ------------------------------------------------------->
+ i_0 ... i_0+4 j_0 ... j_0+4
+
+ We can create expression based on index rather than address:
+ (i_0 + 4 < j_0 || j_0 + 4 < i_0). */
+
+static bool
+create_intersect_range_checks_index (loop_vec_info loop_vinfo, tree *cond_expr,
+ const dr_with_seg_len& dr_a,
+ const dr_with_seg_len& dr_b)
+{
+ if (integer_zerop (DR_STEP (dr_a.dr))
+ || integer_zerop (DR_STEP (dr_b.dr))
+ || DR_NUM_DIMENSIONS (dr_a.dr) != DR_NUM_DIMENSIONS (dr_b.dr))
+ return false;
+
+ if (!tree_fits_uhwi_p (dr_a.seg_len) || !tree_fits_uhwi_p (dr_b.seg_len))
+ return false;
+
+ if (!operand_equal_p (DR_BASE_OBJECT (dr_a.dr), DR_BASE_OBJECT (dr_b.dr), 0))
+ return false;
+
+ if (!operand_equal_p (DR_STEP (dr_a.dr), DR_STEP (dr_b.dr), 0))
+ return false;
+
+ gcc_assert (TREE_CODE (DR_STEP (dr_a.dr)) == INTEGER_CST);
+
+ bool neg_step = tree_int_cst_compare (DR_STEP (dr_a.dr), size_zero_node) < 0;
+ unsigned HOST_WIDE_INT abs_step = tree_to_uhwi (DR_STEP (dr_a.dr));
+ if (neg_step)
+ abs_step = -abs_step;
+
+ unsigned HOST_WIDE_INT seg_len1 = tree_to_uhwi (dr_a.seg_len);
+ unsigned HOST_WIDE_INT seg_len2 = tree_to_uhwi (dr_b.seg_len);
+ /* Infer index length from segment length. */
+ unsigned HOST_WIDE_INT idx_len1 = (seg_len1 + abs_step - 1) / abs_step;
+ unsigned HOST_WIDE_INT idx_len2 = (seg_len2 + abs_step - 1) / abs_step;
+
+ unsigned int i;
+ struct loop *loop = LOOP_VINFO_LOOP (loop_vinfo);
+ for (i = 0; i < DR_NUM_DIMENSIONS (dr_a.dr); i++)
+ {
+ tree access1 = DR_ACCESS_FN (dr_a.dr, i);
+ tree access2 = DR_ACCESS_FN (dr_b.dr, i);
+ /* Two index must be the same if they are not scev. */
+ if (TREE_CODE (access1) != POLYNOMIAL_CHREC
+ || TREE_CODE (access2) != POLYNOMIAL_CHREC)
+ {
+ if (operand_equal_p (access1, access2, 0))
+ continue;
+
+ return false;
+ }
+ /* Two index must be the same if they are not scev wrto current loop. */
+ if (CHREC_VARIABLE (access1) != (unsigned)loop->num
+ || CHREC_VARIABLE (access2) != (unsigned)loop->num)
+ {
+ if (operand_equal_p (access1, access2, 0))
+ continue;
+
+ return false;
+ }
+ /* Two index must have the same step. */
+ if (!operand_equal_p (CHREC_RIGHT (access1), CHREC_RIGHT (access2), 0))
+ return false;
+
+ tree min1 = CHREC_LEFT (access1);
+ tree min2 = CHREC_LEFT (access2);
+ if (!types_compatible_p (TREE_TYPE (min1), TREE_TYPE (min2)))
+ return false;
+
+ tree max1 = fold_build2 (PLUS_EXPR, TREE_TYPE (min1), min1,
+ build_int_cst (TREE_TYPE (min1), idx_len1));
+ tree max2 = fold_build2 (PLUS_EXPR, TREE_TYPE (min2), min2,
+ build_int_cst (TREE_TYPE (min2), idx_len2));
+ /* Adjust ranges for negative step. */
+ if (neg_step)
+ {
+ min1 = fold_build2 (MINUS_EXPR, TREE_TYPE (min1), max1,
+ build_int_cst (TREE_TYPE (min1), 1));
+ max1 = fold_build2 (PLUS_EXPR, TREE_TYPE (min1),
+ CHREC_LEFT (access1),
+ build_int_cst (TREE_TYPE (min1), 1));
+ min2 = fold_build2 (MINUS_EXPR, TREE_TYPE (min2), max2,
+ build_int_cst (TREE_TYPE (min2), 1));
+ max2 = fold_build2 (PLUS_EXPR, TREE_TYPE (min2),
+ CHREC_LEFT (access2),
+ build_int_cst (TREE_TYPE (min2), 1));
+ }
+ tree part_cond_expr
+ = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
+ fold_build2 (LE_EXPR, boolean_type_node, max1, min2),
+ fold_build2 (LE_EXPR, boolean_type_node, max2, min1));
+ if (*cond_expr)
+ *cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
+ *cond_expr, part_cond_expr);
+ else
+ *cond_expr = part_cond_expr;
+ }
+ return true;
+}
+
+/* Given two data references and segment lengths described by DR_A and DR_B,
+ create expression checking if the two addresses ranges intersect with
+ each other:
+
+ ((DR_A_addr_0 + DR_A_segment_length_0) <= DR_B_addr_0)
+ || (DR_B_addr_0 + DER_B_segment_length_0) <= DR_A_addr_0)) */
+
+static void
+create_intersect_range_checks (loop_vec_info loop_vinfo, tree *cond_expr,
+ const dr_with_seg_len& dr_a,
+ const dr_with_seg_len& dr_b)
+{
+ *cond_expr = NULL_TREE;
+ if (create_intersect_range_checks_index (loop_vinfo, cond_expr, dr_a, dr_b))
+ return;
+
+ tree segment_length_a = dr_a.seg_len;
+ tree segment_length_b = dr_b.seg_len;
+ tree addr_base_a = DR_BASE_ADDRESS (dr_a.dr);
+ tree addr_base_b = DR_BASE_ADDRESS (dr_b.dr);
+ tree offset_a = DR_OFFSET (dr_a.dr), offset_b = DR_OFFSET (dr_b.dr);
+
+ offset_a = fold_build2 (PLUS_EXPR, TREE_TYPE (offset_a),
+ offset_a, DR_INIT (dr_a.dr));
+ offset_b = fold_build2 (PLUS_EXPR, TREE_TYPE (offset_b),
+ offset_b, DR_INIT (dr_b.dr));
+ addr_base_a = fold_build_pointer_plus (addr_base_a, offset_a);
+ addr_base_b = fold_build_pointer_plus (addr_base_b, offset_b);
+
+ tree seg_a_min = addr_base_a;
+ tree seg_a_max = fold_build_pointer_plus (addr_base_a, segment_length_a);
+ /* For negative step, we need to adjust address range by TYPE_SIZE_UNIT
+ bytes, e.g., int a[3] -> a[1] range is [a+4, a+16) instead of
+ [a, a+12) */
+ if (tree_int_cst_compare (DR_STEP (dr_a.dr), size_zero_node) < 0)
+ {
+ tree unit_size = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a.dr)));
+ seg_a_min = fold_build_pointer_plus (seg_a_max, unit_size);
+ seg_a_max = fold_build_pointer_plus (addr_base_a, unit_size);
+ }
+
+ tree seg_b_min = addr_base_b;
+ tree seg_b_max = fold_build_pointer_plus (addr_base_b, segment_length_b);
+ if (tree_int_cst_compare (DR_STEP (dr_b.dr), size_zero_node) < 0)
+ {
+ tree unit_size = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_b.dr)));
+ seg_b_min = fold_build_pointer_plus (seg_b_max, unit_size);
+ seg_b_max = fold_build_pointer_plus (addr_base_b, unit_size);
+ }
+ *cond_expr
+ = fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
+ fold_build2 (LE_EXPR, boolean_type_node, seg_a_max, seg_b_min),
+ fold_build2 (LE_EXPR, boolean_type_node, seg_b_max, seg_a_min));
+}
+
/* Function vect_create_cond_for_alias_checks.
Create a conditional expression that represents the run-time checks for
@@ -2290,15 +2463,6 @@ vect_create_cond_for_alias_checks (loop_vec_info
loop_vinfo, tree * cond_expr)
LOOP_VINFO_COMP_ALIAS_DDRS (loop_vinfo);
tree part_cond_expr;
- /* Create expression
- ((store_ptr_0 + store_segment_length_0) <= load_ptr_0)
- || (load_ptr_0 + load_segment_length_0) <= store_ptr_0))
- &&
- ...
- &&
- ((store_ptr_n + store_segment_length_n) <= load_ptr_n)
- || (load_ptr_n + load_segment_length_n) <= store_ptr_n)) */
-
if (comp_alias_ddrs.is_empty ())
return;
@@ -2306,18 +2470,6 @@ vect_create_cond_for_alias_checks (loop_vec_info
loop_vinfo, tree * cond_expr)
{
const dr_with_seg_len& dr_a = comp_alias_ddrs[i].first;
const dr_with_seg_len& dr_b = comp_alias_ddrs[i].second;
- tree segment_length_a = dr_a.seg_len;
- tree segment_length_b = dr_b.seg_len;
- tree addr_base_a = DR_BASE_ADDRESS (dr_a.dr);
- tree addr_base_b = DR_BASE_ADDRESS (dr_b.dr);
- tree offset_a = DR_OFFSET (dr_a.dr), offset_b = DR_OFFSET (dr_b.dr);
-
- offset_a = fold_build2 (PLUS_EXPR, TREE_TYPE (offset_a),
- offset_a, DR_INIT (dr_a.dr));
- offset_b = fold_build2 (PLUS_EXPR, TREE_TYPE (offset_b),
- offset_b, DR_INIT (dr_b.dr));
- addr_base_a = fold_build_pointer_plus (addr_base_a, offset_a);
- addr_base_b = fold_build_pointer_plus (addr_base_b, offset_b);
if (dump_enabled_p ())
{
@@ -2329,32 +2481,8 @@ vect_create_cond_for_alias_checks (loop_vec_info
loop_vinfo, tree * cond_expr)
dump_printf (MSG_NOTE, "\n");
}
- tree seg_a_min = addr_base_a;
- tree seg_a_max = fold_build_pointer_plus (addr_base_a, segment_length_a);
- /* For negative step, we need to adjust address range by TYPE_SIZE_UNIT
- bytes, e.g., int a[3] -> a[1] range is [a+4, a+16) instead of
- [a, a+12) */
- if (tree_int_cst_compare (DR_STEP (dr_a.dr), size_zero_node) < 0)
- {
- tree unit_size = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_a.dr)));
- seg_a_min = fold_build_pointer_plus (seg_a_max, unit_size);
- seg_a_max = fold_build_pointer_plus (addr_base_a, unit_size);
- }
-
- tree seg_b_min = addr_base_b;
- tree seg_b_max = fold_build_pointer_plus (addr_base_b, segment_length_b);
- if (tree_int_cst_compare (DR_STEP (dr_b.dr), size_zero_node) < 0)
- {
- tree unit_size = TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr_b.dr)));
- seg_b_min = fold_build_pointer_plus (seg_b_max, unit_size);
- seg_b_max = fold_build_pointer_plus (addr_base_b, unit_size);
- }
-
- part_cond_expr =
- fold_build2 (TRUTH_OR_EXPR, boolean_type_node,
- fold_build2 (LE_EXPR, boolean_type_node, seg_a_max, seg_b_min),
- fold_build2 (LE_EXPR, boolean_type_node, seg_b_max, seg_a_min));
-
+ /* Create condition expression for each pair data references. */
+ create_intersect_range_checks (loop_vinfo, &part_cond_expr, dr_a, dr_b);
if (*cond_expr)
*cond_expr = fold_build2 (TRUTH_AND_EXPR, boolean_type_node,
*cond_expr, part_cond_expr);
