+/* Auxiliary functions to determine the set of memory accesses which
+ can't trap because they are preceded by accesses to the same memory
+ portion. We do that for MEM_REFs, so we only need to track
+ the SSA_NAME of the pointer indirectly referenced. The algorithm
+ simply is a walk over all instructions in dominator order. When
+ we see an MEM_REF we determine if we've already seen a same
+ ref anywhere up to the root of the dominator tree. If we do the
+ current access can't trap. If we don't see any dominating access
+ the current access might trap, but might also make later accesses
+ non-trapping, so we remember it. We need to be careful with loads
+ or stores, for instance a load might not trap, while a store would,
+ so if we see a dominating read access this doesn't mean that a later
+ write access would not trap. Hence we also need to differentiate the
+ type of access(es) seen.
+
+ ??? We currently are very conservative and assume that a load might
+ trap even if a store doesn't (write-only memory). This probably is
+ overly conservative. */
+
+/* A hash-table of SSA_NAMEs, and in which basic block an MEM_REF
+ through it was seen, which would constitute a no-trap region for
+ same accesses. */
+struct name_to_bb
+{
+ tree ssa_name;
+ basic_block bb;
+ unsigned store : 1;
+};
+
+/* The hash table for remembering what we've seen. */
+static htab_t seen_ssa_names;
+
+/* The set of MEM_REFs which can't trap. */
+static struct pointer_set_t *nontrap_set;
+
+/* The hash function, based on the pointer to the pointer SSA_NAME. */
+static hashval_t
+name_to_bb_hash (const void *p)
+{
+ const_tree n = ((const struct name_to_bb *)p)->ssa_name;
+ return htab_hash_pointer (n) ^ ((const struct name_to_bb *)p)->store;
+}
+
+/* The equality function of *P1 and *P2. SSA_NAMEs are shared, so
+ it's enough to simply compare them for equality. */
+static int
+name_to_bb_eq (const void *p1, const void *p2)
+{
+ const struct name_to_bb *n1 = (const struct name_to_bb *)p1;
+ const struct name_to_bb *n2 = (const struct name_to_bb *)p2;
+
+ return n1->ssa_name == n2->ssa_name && n1->store == n2->store;
+}
+
+/* We see the expression EXP in basic block BB. If it's an interesting
+ expression (an MEM_REF through an SSA_NAME) possibly insert the
+ expression into the set NONTRAP or the hash table of seen expressions.
+ STORE is true if this expression is on the LHS, otherwise it's on
+ the RHS. */
+static void
+add_or_mark_expr (basic_block bb, tree exp,
+ struct pointer_set_t *nontrap, bool store)
+{
+ if (TREE_CODE (exp) == MEM_REF
+ && TREE_CODE (TREE_OPERAND (exp, 0)) == SSA_NAME)
+ {
+ tree name = TREE_OPERAND (exp, 0);
+ struct name_to_bb map;
+ void **slot;
+ struct name_to_bb *n2bb;
+ basic_block found_bb = 0;
+
+ /* Try to find the last seen MEM_REF through the same
+ SSA_NAME, which can trap. */
+ map.ssa_name = name;
+ map.bb = 0;
+ map.store = store;
+ slot = htab_find_slot (seen_ssa_names, &map, INSERT);
+ n2bb = (struct name_to_bb *) *slot;
+ if (n2bb)
+ found_bb = n2bb->bb;
+
+ /* If we've found a trapping MEM_REF, _and_ it dominates EXP
+ (it's in a basic block on the path from us to the dominator root)
+ then we can't trap. */
+ if (found_bb && found_bb->aux == (void *)1)
+ {
+ pointer_set_insert (nontrap, exp);
+ }
+ else
+ {
+ /* EXP might trap, so insert it into the hash table. */
+ if (n2bb)
+ {
+ n2bb->bb = bb;
+ }
+ else
+ {
+ n2bb = XNEW (struct name_to_bb);
+ n2bb->ssa_name = name;
+ n2bb->bb = bb;
+ n2bb->store = store;
+ *slot = n2bb;
+ }
+ }
+ }
+}
+
+/* Called by walk_dominator_tree, when entering the block BB. */
+static void
+nt_init_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
+{
+ gimple_stmt_iterator gsi;
+ /* Mark this BB as being on the path to dominator root. */
+ bb->aux = (void*)1;
+
+ /* And walk the statements in order. */
+ for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+ {
+ gimple stmt = gsi_stmt (gsi);
+
+ if (is_gimple_assign (stmt))
+ {
+ add_or_mark_expr (bb, gimple_assign_lhs (stmt), nontrap_set, true);
+ add_or_mark_expr (bb, gimple_assign_rhs1 (stmt), nontrap_set, false);
+ if (get_gimple_rhs_num_ops (gimple_assign_rhs_code (stmt)) > 1)
+ add_or_mark_expr (bb, gimple_assign_rhs2 (stmt), nontrap_set,
+ false);
+ }
+ }
+}
+
+/* Called by walk_dominator_tree, when basic block BB is exited. */
+static void
+nt_fini_block (struct dom_walk_data *data ATTRIBUTE_UNUSED, basic_block bb)
+{
+ /* This BB isn't on the path to dominator root anymore. */
+ bb->aux = NULL;
+}
+
+/* This is the entry point of gathering non trapping memory accesses.
+ It will do a dominator walk over the whole function, and it will
+ make use of the bb->aux pointers. It returns a set of trees
+ (the MEM_REFs itself) which can't trap. */
+static struct pointer_set_t *
+get_non_trapping (void)
+{
+ struct pointer_set_t *nontrap;
+ struct dom_walk_data walk_data;
+
+ nontrap = pointer_set_create ();
+ seen_ssa_names = htab_create (128, name_to_bb_hash, name_to_bb_eq,
+ free);
+ /* We're going to do a dominator walk, so ensure that we have
+ dominance information. */
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ /* Setup callbacks for the generic dominator tree walker. */
+ nontrap_set = nontrap;
+ walk_data.dom_direction = CDI_DOMINATORS;
+ walk_data.initialize_block_local_data = NULL;
+ walk_data.before_dom_children = nt_init_block;
+ walk_data.after_dom_children = nt_fini_block;
+ walk_data.global_data = NULL;
+ walk_data.block_local_data_size = 0;
+
+ init_walk_dominator_tree (&walk_data);
+ walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+ fini_walk_dominator_tree (&walk_data);
+ htab_delete (seen_ssa_names);
+
+ return nontrap;
+}
+
+/* Do the main work of conditional store replacement. We already know
+ that the recognized pattern looks like so:
+
+ split:
+ if (cond) goto MIDDLE_BB; else goto JOIN_BB (edge E1)
+ MIDDLE_BB:
+ something
+ fallthrough (edge E0)
+ JOIN_BB:
+ some more
+
+ We check that MIDDLE_BB contains only one store, that that store
+ doesn't trap (not via NOTRAP, but via checking if an access to the same
+ memory location dominates us) and that the store has a "simple" RHS. */
+
+static bool
+cond_store_replacement (basic_block middle_bb, basic_block join_bb,
+ edge e0, edge e1, struct pointer_set_t *nontrap)
+{
+ gimple assign = last_and_only_stmt (middle_bb);
+ tree lhs, rhs, name;
+ gimple newphi, new_stmt;
+ gimple_stmt_iterator gsi;
+ source_location locus;
+
+ /* Check if middle_bb contains of only one store. */
+ if (!assign
+ || !gimple_assign_single_p (assign))
+ return false;
+
+ locus = gimple_location (assign);
+ lhs = gimple_assign_lhs (assign);
+ rhs = gimple_assign_rhs1 (assign);
+ if (TREE_CODE (lhs) != MEM_REF
+ || TREE_CODE (TREE_OPERAND (lhs, 0)) != SSA_NAME
+ || !is_gimple_reg_type (TREE_TYPE (lhs)))
+ return false;
+
+ /* Prove that we can move the store down. We could also check
+ TREE_THIS_NOTRAP here, but in that case we also could move stores,
+ whose value is not available readily, which we want to avoid. */
+ if (!pointer_set_contains (nontrap, lhs))
+ return false;
+
+ /* Now we've checked the constraints, so do the transformation:
+ 1) Remove the single store. */
+ gsi = gsi_for_stmt (assign);
+ unlink_stmt_vdef (assign);
+ gsi_remove (&gsi, true);
+ release_defs (assign);
+
+ /* 2) Create a temporary where we can store the old content
+ of the memory touched by the store, if we need to. */
+ if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp))
+ condstoretemp = create_tmp_reg (TREE_TYPE (lhs), "cstore");
+ add_referenced_var (condstoretemp);
+
+ /* 3) Insert a load from the memory of the store to the temporary
+ on the edge which did not contain the store. */
+ lhs = unshare_expr (lhs);
+ new_stmt = gimple_build_assign (condstoretemp, lhs);
+ name = make_ssa_name (condstoretemp, new_stmt);
+ gimple_assign_set_lhs (new_stmt, name);
+ gimple_set_location (new_stmt, locus);
+ gsi_insert_on_edge (e1, new_stmt);
+
+ /* 4) Create a PHI node at the join block, with one argument
+ holding the old RHS, and the other holding the temporary
+ where we stored the old memory contents. */
+ newphi = create_phi_node (condstoretemp, join_bb);
+ add_phi_arg (newphi, rhs, e0, locus);
+ add_phi_arg (newphi, name, e1, locus);
+
+ lhs = unshare_expr (lhs);
+ new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
+
+ /* 5) Insert that PHI node. */
+ gsi = gsi_after_labels (join_bb);
+ if (gsi_end_p (gsi))
+ {
+ gsi = gsi_last_bb (join_bb);
+ gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
+ }
+ else
+ gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
+
+ return true;
+}
+
+/* Do the main work of conditional store replacement. */
+
+static bool
+cond_if_else_store_replacement_1 (basic_block then_bb, basic_block else_bb,
+ basic_block join_bb, gimple then_assign,
+ gimple else_assign)
+{
+ tree lhs_base, lhs, then_rhs, else_rhs;
+ source_location then_locus, else_locus;
+ gimple_stmt_iterator gsi;
+ gimple newphi, new_stmt;
+
+ if (then_assign == NULL
+ || !gimple_assign_single_p (then_assign)
+ || gimple_clobber_p (then_assign)
+ || else_assign == NULL
+ || !gimple_assign_single_p (else_assign)
+ || gimple_clobber_p (else_assign))
+ return false;
+
+ lhs = gimple_assign_lhs (then_assign);
+ if (!is_gimple_reg_type (TREE_TYPE (lhs))
+ || !operand_equal_p (lhs, gimple_assign_lhs (else_assign), 0))
+ return false;
+
+ lhs_base = get_base_address (lhs);
+ if (lhs_base == NULL_TREE
+ || (!DECL_P (lhs_base) && TREE_CODE (lhs_base) != MEM_REF))
+ return false;
+
+ then_rhs = gimple_assign_rhs1 (then_assign);
+ else_rhs = gimple_assign_rhs1 (else_assign);
+ then_locus = gimple_location (then_assign);
+ else_locus = gimple_location (else_assign);
+
+ /* Now we've checked the constraints, so do the transformation:
+ 1) Remove the stores. */
+ gsi = gsi_for_stmt (then_assign);
+ unlink_stmt_vdef (then_assign);
+ gsi_remove (&gsi, true);
+ release_defs (then_assign);
+
+ gsi = gsi_for_stmt (else_assign);
+ unlink_stmt_vdef (else_assign);
+ gsi_remove (&gsi, true);
+ release_defs (else_assign);
+
+ /* 2) Create a temporary where we can store the old content
+ of the memory touched by the store, if we need to. */
+ if (!condstoretemp || TREE_TYPE (lhs) != TREE_TYPE (condstoretemp))
+ condstoretemp = create_tmp_reg (TREE_TYPE (lhs), "cstore");
+ add_referenced_var (condstoretemp);
+
+ /* 3) Create a PHI node at the join block, with one argument
+ holding the old RHS, and the other holding the temporary
+ where we stored the old memory contents. */
+ newphi = create_phi_node (condstoretemp, join_bb);
+ add_phi_arg (newphi, then_rhs, EDGE_SUCC (then_bb, 0), then_locus);
+ add_phi_arg (newphi, else_rhs, EDGE_SUCC (else_bb, 0), else_locus);
+
+ new_stmt = gimple_build_assign (lhs, PHI_RESULT (newphi));
+
+ /* 4) Insert that PHI node. */
+ gsi = gsi_after_labels (join_bb);
+ if (gsi_end_p (gsi))
+ {
+ gsi = gsi_last_bb (join_bb);
+ gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
+ }
+ else
+ gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
+
+ return true;
+}
+
+/* Conditional store replacement. We already know
+ that the recognized pattern looks like so:
+
+ split:
+ if (cond) goto THEN_BB; else goto ELSE_BB (edge E1)
+ THEN_BB:
+ ...
+ X = Y;
+ ...
+ goto JOIN_BB;
+ ELSE_BB:
+ ...
+ X = Z;
+ ...
+ fallthrough (edge E0)
+ JOIN_BB:
+ some more
+
+ We check that it is safe to sink the store to JOIN_BB by verifying that
+ there are no read-after-write or write-after-write dependencies in
+ THEN_BB and ELSE_BB. */
+
+static bool
+cond_if_else_store_replacement (basic_block then_bb, basic_block else_bb,
+ basic_block join_bb)
+{
+ gimple then_assign = last_and_only_stmt (then_bb);
+ gimple else_assign = last_and_only_stmt (else_bb);
+ VEC (data_reference_p, heap) *then_datarefs, *else_datarefs;
+ VEC (ddr_p, heap) *then_ddrs, *else_ddrs;
+ gimple then_store, else_store;
+ bool found, ok = false, res;
+ struct data_dependence_relation *ddr;
+ data_reference_p then_dr, else_dr;
+ int i, j;
+ tree then_lhs, else_lhs;
+ VEC (gimple, heap) *then_stores, *else_stores;
+ basic_block blocks[3];
+
+ if (MAX_STORES_TO_SINK == 0)
+ return false;
+
+ /* Handle the case with single statement in THEN_BB and ELSE_BB. */
+ if (then_assign && else_assign)
+ return cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
+ then_assign, else_assign);
+
+ /* Find data references. */
+ then_datarefs = VEC_alloc (data_reference_p, heap, 1);
+ else_datarefs = VEC_alloc (data_reference_p, heap, 1);
+ if ((find_data_references_in_bb (NULL, then_bb, &then_datarefs)
+ == chrec_dont_know)
+ || !VEC_length (data_reference_p, then_datarefs)
+ || (find_data_references_in_bb (NULL, else_bb, &else_datarefs)
+ == chrec_dont_know)
+ || !VEC_length (data_reference_p, else_datarefs))
+ {
+ free_data_refs (then_datarefs);
+ free_data_refs (else_datarefs);
+ return false;
+ }
+
+ /* Find pairs of stores with equal LHS. */
+ then_stores = VEC_alloc (gimple, heap, 1);
+ else_stores = VEC_alloc (gimple, heap, 1);
+ FOR_EACH_VEC_ELT (data_reference_p, then_datarefs, i, then_dr)
+ {
+ if (DR_IS_READ (then_dr))
+ continue;
+
+ then_store = DR_STMT (then_dr);
+ then_lhs = gimple_get_lhs (then_store);
+ found = false;
+
+ FOR_EACH_VEC_ELT (data_reference_p, else_datarefs, j, else_dr)
+ {
+ if (DR_IS_READ (else_dr))
+ continue;
+
+ else_store = DR_STMT (else_dr);
+ else_lhs = gimple_get_lhs (else_store);
+
+ if (operand_equal_p (then_lhs, else_lhs, 0))
+ {
+ found = true;
+ break;
+ }
+ }
+
+ if (!found)
+ continue;
+
+ VEC_safe_push (gimple, heap, then_stores, then_store);
+ VEC_safe_push (gimple, heap, else_stores, else_store);
+ }
+
+ /* No pairs of stores found. */
+ if (!VEC_length (gimple, then_stores)
+ || VEC_length (gimple, then_stores) > (unsigned) MAX_STORES_TO_SINK)
+ {
+ free_data_refs (then_datarefs);
+ free_data_refs (else_datarefs);
+ VEC_free (gimple, heap, then_stores);
+ VEC_free (gimple, heap, else_stores);
+ return false;
+ }
+
+ /* Compute and check data dependencies in both basic blocks. */
+ then_ddrs = VEC_alloc (ddr_p, heap, 1);
+ else_ddrs = VEC_alloc (ddr_p, heap, 1);
+ compute_all_dependences (then_datarefs, &then_ddrs, NULL, false);
+ compute_all_dependences (else_datarefs, &else_ddrs, NULL, false);
+ blocks[0] = then_bb;
+ blocks[1] = else_bb;
+ blocks[2] = join_bb;
+ renumber_gimple_stmt_uids_in_blocks (blocks, 3);
+
+ /* Check that there are no read-after-write or write-after-write dependencies
+ in THEN_BB. */
+ FOR_EACH_VEC_ELT (ddr_p, then_ddrs, i, ddr)
+ {
+ struct data_reference *dra = DDR_A (ddr);
+ struct data_reference *drb = DDR_B (ddr);
+
+ if (DDR_ARE_DEPENDENT (ddr) != chrec_known
+ && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
+ && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
+ || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
+ && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
+ || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
+ {
+ free_dependence_relations (then_ddrs);
+ free_dependence_relations (else_ddrs);
+ free_data_refs (then_datarefs);
+ free_data_refs (else_datarefs);
+ VEC_free (gimple, heap, then_stores);
+ VEC_free (gimple, heap, else_stores);
+ return false;
+ }
+ }
+
+ /* Check that there are no read-after-write or write-after-write dependencies
+ in ELSE_BB. */
+ FOR_EACH_VEC_ELT (ddr_p, else_ddrs, i, ddr)
+ {
+ struct data_reference *dra = DDR_A (ddr);
+ struct data_reference *drb = DDR_B (ddr);
+
+ if (DDR_ARE_DEPENDENT (ddr) != chrec_known
+ && ((DR_IS_READ (dra) && DR_IS_WRITE (drb)
+ && gimple_uid (DR_STMT (dra)) > gimple_uid (DR_STMT (drb)))
+ || (DR_IS_READ (drb) && DR_IS_WRITE (dra)
+ && gimple_uid (DR_STMT (drb)) > gimple_uid (DR_STMT (dra)))
+ || (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))))
+ {
+ free_dependence_relations (then_ddrs);
+ free_dependence_relations (else_ddrs);
+ free_data_refs (then_datarefs);
+ free_data_refs (else_datarefs);
+ VEC_free (gimple, heap, then_stores);
+ VEC_free (gimple, heap, else_stores);
+ return false;
+ }
+ }
+
+ /* Sink stores with same LHS. */
+ FOR_EACH_VEC_ELT (gimple, then_stores, i, then_store)
+ {
+ else_store = VEC_index (gimple, else_stores, i);
+ res = cond_if_else_store_replacement_1 (then_bb, else_bb, join_bb,
+ then_store, else_store);
+ ok = ok || res;
+ }
+
+ free_dependence_relations (then_ddrs);
+ free_dependence_relations (else_ddrs);
+ free_data_refs (then_datarefs);
+ free_data_refs (else_datarefs);
+ VEC_free (gimple, heap, then_stores);
+ VEC_free (gimple, heap, else_stores);
+
+ return ok;
+}