From f939586ac50948f6915dbee9bd5d425a1e3c2a7d Mon Sep 17 00:00:00 2001 From: Venkataramanan Kumar Date: Tue, 17 Nov 2015 07:41:08 +0000 Subject: [PATCH] Relax trap assumptions in tree if convert. 2015-11-17 Venkataramanan Kumar * tree-if-conv.c: Include varasm.h (ref_DR_map): Define. (baseref_DR_map): Like wise (struct ifc_dr): Add new tree predicate field. (hash_memrefs_baserefs_and_store_DRs_read_written_info): New function. (memrefs_read_or_written_unconditionally): Remove. (write_memrefs_written_at_least_once): Remove. (ifcvt_memrefs_wont_trap): Use hash maps to query unconditional read/written information. (if_convertible_loop_p_1): Initialize hash maps and predicates before hashing data references and delete hashmaps at the end. 2015-11-17 Venkataramanan Kumar * gcc.dg/tree-ssa/ifc-8.c: New test. From-SVN: r230454 --- gcc/ChangeLog | 14 ++ gcc/testsuite/ChangeLog | 4 + gcc/testsuite/gcc.dg/tree-ssa/ifc-8.c | 17 ++ gcc/tree-if-conv.c | 241 +++++++++++++------------- 4 files changed, 151 insertions(+), 125 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/ifc-8.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 43e2b58301e..6316ab6d122 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2015-11-17 Venkataramanan Kumar + + * tree-if-conv.c: Include varasm.h + (ref_DR_map): Define. + (baseref_DR_map): Like wise + (struct ifc_dr): Add new tree predicate field. + (hash_memrefs_baserefs_and_store_DRs_read_written_info): New function. + (memrefs_read_or_written_unconditionally): Remove. + (write_memrefs_written_at_least_once): Remove. + (ifcvt_memrefs_wont_trap): Use hash maps to query + unconditional read/written information. + (if_convertible_loop_p_1): Initialize hash maps and predicates + before hashing data references and delete hashmaps at the end. + 2015-11-16 Thomas Preud'homme PR 56036 diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 0f6a593c445..52112ea8dcd 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2015-11-17 Venkataramanan Kumar + + * gcc.dg/tree-ssa/ifc-8.c: New test. + 2015-11-16 Marek Polacek PR c++/68362 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ifc-8.c b/gcc/testsuite/gcc.dg/tree-ssa/ifc-8.c new file mode 100644 index 00000000000..89a34104a69 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ifc-8.c @@ -0,0 +1,17 @@ + +/* { dg-do compile } */ +/* { dg-options "-Ofast -fdump-tree-ifcvt-details -fno-common -ftree-loop-if-convert-stores" } */ + +#define LEN 4096 + __attribute__((aligned (32))) float array[LEN]; + +void test () +{ + for (int i = 0; i < LEN; i++) + { + if (array[i] > (float)0.) + array[i] = 3; + } +} + +/* { dg-final { scan-tree-dump-times "Applying if-conversion" 1 "ifcvt" } } */ diff --git a/gcc/tree-if-conv.c b/gcc/tree-if-conv.c index 88b6405a7be..01065cbf16e 100644 --- a/gcc/tree-if-conv.c +++ b/gcc/tree-if-conv.c @@ -110,6 +110,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-ssa-address.h" #include "dbgcnt.h" #include "tree-hash-traits.h" +#include "varasm.h" /* List of basic blocks in if-conversion-suitable order. */ static basic_block *ifc_bbs; @@ -117,6 +118,12 @@ static basic_block *ifc_bbs; /* Apply more aggressive (extended) if-conversion if true. */ static bool aggressive_if_conv; +/* Hash table to store references, DR pairs. */ +static hash_map *ref_DR_map; + +/* Hash table to store base reference, DR pairs. */ +static hash_map *baseref_DR_map; + /* Structure used to predicate basic blocks. This is attached to the ->aux field of the BBs in the loop to be if-converted. */ struct bb_predicate { @@ -580,139 +587,71 @@ struct ifc_dr { /* -1 when not initialized, 0 when false, 1 when true. */ int rw_unconditionally; + + tree predicate; }; #define IFC_DR(DR) ((struct ifc_dr *) (DR)->aux) #define DR_WRITTEN_AT_LEAST_ONCE(DR) (IFC_DR (DR)->written_at_least_once) #define DR_RW_UNCONDITIONALLY(DR) (IFC_DR (DR)->rw_unconditionally) -/* Returns true when the memory references of STMT are read or written - unconditionally. In other words, this function returns true when - for every data reference A in STMT there exist other accesses to - a data reference with the same base with predicates that add up (OR-up) to - the true predicate: this ensures that the data reference A is touched - (read or written) on every iteration of the if-converted loop. */ - -static bool -memrefs_read_or_written_unconditionally (gimple *stmt, - vec drs) -{ - int i, j; - data_reference_p a, b; - tree ca = bb_predicate (gimple_bb (stmt)); - - for (i = 0; drs.iterate (i, &a); i++) - if (DR_STMT (a) == stmt) - { - bool found = false; - int x = DR_RW_UNCONDITIONALLY (a); - - if (x == 0) - return false; - - if (x == 1) - continue; - - for (j = 0; drs.iterate (j, &b); j++) - { - tree ref_base_a = DR_REF (a); - tree ref_base_b = DR_REF (b); - - if (DR_STMT (b) == stmt) - continue; - - while (TREE_CODE (ref_base_a) == COMPONENT_REF - || TREE_CODE (ref_base_a) == IMAGPART_EXPR - || TREE_CODE (ref_base_a) == REALPART_EXPR) - ref_base_a = TREE_OPERAND (ref_base_a, 0); - - while (TREE_CODE (ref_base_b) == COMPONENT_REF - || TREE_CODE (ref_base_b) == IMAGPART_EXPR - || TREE_CODE (ref_base_b) == REALPART_EXPR) - ref_base_b = TREE_OPERAND (ref_base_b, 0); - - if (operand_equal_p (ref_base_a, ref_base_b, 0)) - { - tree cb = bb_predicate (gimple_bb (DR_STMT (b))); - - if (DR_RW_UNCONDITIONALLY (b) == 1 - || is_true_predicate (cb) - || is_true_predicate (ca - = fold_or_predicates (EXPR_LOCATION (cb), ca, cb))) - { - DR_RW_UNCONDITIONALLY (a) = 1; - DR_RW_UNCONDITIONALLY (b) = 1; - found = true; - break; - } - } - } - - if (!found) - { - DR_RW_UNCONDITIONALLY (a) = 0; - return false; - } - } - - return true; -} - -/* Returns true when the memory references of STMT are unconditionally - written. In other words, this function returns true when for every - data reference A written in STMT, there exist other writes to the - same data reference with predicates that add up (OR-up) to the true - predicate: this ensures that the data reference A is written on - every iteration of the if-converted loop. */ - -static bool -write_memrefs_written_at_least_once (gimple *stmt, - vec drs) +/* Iterates over DR's and stores refs, DR and base refs, DR pairs in + HASH tables. While storing them in HASH table, it checks if the + reference is unconditionally read or written and stores that as a flag + information. For base reference it checks if it is written atlest once + unconditionally and stores it as flag information along with DR. + In other words for every data reference A in STMT there exist other + accesses to a data reference with the same base with predicates that + add up (OR-up) to the true predicate: this ensures that the data + reference A is touched (read or written) on every iteration of the + if-converted loop. */ +static void +hash_memrefs_baserefs_and_store_DRs_read_written_info (data_reference_p a) { - int i, j; - data_reference_p a, b; - tree ca = bb_predicate (gimple_bb (stmt)); - for (i = 0; drs.iterate (i, &a); i++) - if (DR_STMT (a) == stmt - && DR_IS_WRITE (a)) - { - bool found = false; - int x = DR_WRITTEN_AT_LEAST_ONCE (a); + data_reference_p *master_dr, *base_master_dr; + tree ref = DR_REF (a); + tree base_ref = DR_BASE_OBJECT (a); + tree ca = bb_predicate (gimple_bb (DR_STMT (a))); + bool exist1, exist2; - if (x == 0) - return false; + while (TREE_CODE (ref) == COMPONENT_REF + || TREE_CODE (ref) == IMAGPART_EXPR + || TREE_CODE (ref) == REALPART_EXPR) + ref = TREE_OPERAND (ref, 0); - if (x == 1) - continue; + master_dr = &ref_DR_map->get_or_insert (ref, &exist1); - for (j = 0; drs.iterate (j, &b); j++) - if (DR_STMT (b) != stmt - && DR_IS_WRITE (b) - && same_data_refs_base_objects (a, b)) - { - tree cb = bb_predicate (gimple_bb (DR_STMT (b))); + if (!exist1) + { + IFC_DR (a)->predicate = ca; + *master_dr = a; + } + else + IFC_DR (*master_dr)->predicate + = fold_or_predicates + (EXPR_LOCATION (IFC_DR (*master_dr)->predicate), + ca, IFC_DR (*master_dr)->predicate); - if (DR_WRITTEN_AT_LEAST_ONCE (b) == 1 - || is_true_predicate (cb) - || is_true_predicate (ca = fold_or_predicates (EXPR_LOCATION (cb), - ca, cb))) - { - DR_WRITTEN_AT_LEAST_ONCE (a) = 1; - DR_WRITTEN_AT_LEAST_ONCE (b) = 1; - found = true; - break; - } - } + if (is_true_predicate (IFC_DR (*master_dr)->predicate)) + DR_RW_UNCONDITIONALLY (*master_dr) = 1; - if (!found) - { - DR_WRITTEN_AT_LEAST_ONCE (a) = 0; - return false; - } - } + base_master_dr = &baseref_DR_map->get_or_insert (base_ref,&exist2); - return true; + if (!exist2) + { + IFC_DR (a)->predicate = ca; + *base_master_dr = a; + } + else + IFC_DR (*base_master_dr)->predicate + = fold_or_predicates + (EXPR_LOCATION (IFC_DR (*base_master_dr)->predicate), + ca, IFC_DR (*base_master_dr)->predicate); + + if (DR_IS_WRITE (a) + && (is_true_predicate (IFC_DR (*base_master_dr)->predicate))) + DR_WRITTEN_AT_LEAST_ONCE (*base_master_dr) = 1; } /* Return true when the memory references of STMT won't trap in the @@ -731,13 +670,50 @@ write_memrefs_written_at_least_once (gimple *stmt, iteration. To check that the memory accesses are correctly formed and that we are allowed to read and write in these locations, we check that the memory accesses to be if-converted occur at every - iteration unconditionally. */ - + iteration unconditionally. + + Returns true for the memory reference in STMT, same memory reference + is read or written unconditionally atleast once and the base memory + reference is written unconditionally once. This is to check reference + will not write fault. Also retuns true if the memory reference is + unconditionally read once then we are conditionally writing to memory + which is defined as read and write and is bound to the definition + we are seeing. */ static bool -ifcvt_memrefs_wont_trap (gimple *stmt, vec refs) +ifcvt_memrefs_wont_trap (gimple *stmt, vec drs) { - return write_memrefs_written_at_least_once (stmt, refs) - && memrefs_read_or_written_unconditionally (stmt, refs); + data_reference_p *master_dr, *base_master_dr; + data_reference_p a = drs[gimple_uid (stmt) - 1]; + + tree ref_base_a = DR_REF (a); + tree base = DR_BASE_OBJECT (a); + + gcc_assert (DR_STMT (a) == stmt); + + while (TREE_CODE (ref_base_a) == COMPONENT_REF + || TREE_CODE (ref_base_a) == IMAGPART_EXPR + || TREE_CODE (ref_base_a) == REALPART_EXPR) + ref_base_a = TREE_OPERAND (ref_base_a, 0); + + master_dr = ref_DR_map->get (ref_base_a); + base_master_dr = baseref_DR_map->get (base); + + gcc_assert (master_dr != NULL && base_master_dr != NULL); + + if (DR_RW_UNCONDITIONALLY (*master_dr) == 1) + { + if (DR_WRITTEN_AT_LEAST_ONCE (*base_master_dr) == 1) + return true; + else + { + tree base_tree = get_base_address (DR_REF (a)); + if (DECL_P (base_tree) + && decl_binds_to_current_def_p (base_tree) + && !TREE_READONLY (base_tree)) + return true; + } + } + return false; } /* Wrapper around gimple_could_trap_p refined for the needs of the @@ -1280,6 +1256,7 @@ if_convertible_loop_p_1 (struct loop *loop, case GIMPLE_CALL: case GIMPLE_DEBUG: case GIMPLE_COND: + gimple_set_uid (gsi_stmt (gsi), 0); break; default: return false; @@ -1288,13 +1265,20 @@ if_convertible_loop_p_1 (struct loop *loop, data_reference_p dr; + ref_DR_map = new hash_map; + baseref_DR_map = new hash_map; + + predicate_bbs (loop); + for (i = 0; refs->iterate (i, &dr); i++) { dr->aux = XNEW (struct ifc_dr); DR_WRITTEN_AT_LEAST_ONCE (dr) = -1; DR_RW_UNCONDITIONALLY (dr) = -1; + if (gimple_uid (DR_STMT (dr)) == 0) + gimple_set_uid (DR_STMT (dr), i + 1); + hash_memrefs_baserefs_and_store_DRs_read_written_info (dr); } - predicate_bbs (loop); for (i = 0; i < loop->num_nodes; i++) { @@ -1391,6 +1375,13 @@ if_convertible_loop_p (struct loop *loop, bool *any_mask_load_store) free_data_refs (refs); free_dependence_relations (ddrs); + + delete ref_DR_map; + ref_DR_map = NULL; + + delete baseref_DR_map; + baseref_DR_map = NULL; + return res; } -- 2.30.2