+/* Records the status of a data reference. This struct is attached to
+ each DR->aux field. */
+
+struct ifc_dr {
+ /* -1 when not initialized, 0 when false, 1 when true. */
+ int written_at_least_once;
+
+ /* -1 when not initialized, 0 when false, 1 when true. */
+ int rw_unconditionally;
+};
+
+#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 (data_reference_p, heap) *drs)
+{
+ int i, j;
+ data_reference_p a, b;
+ tree ca = bb_predicate (gimple_bb (stmt));
+
+ for (i = 0; VEC_iterate (data_reference_p, drs, 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; VEC_iterate (data_reference_p, drs, 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 (data_reference_p, heap) *drs)
+{
+ int i, j;
+ data_reference_p a, b;
+ tree ca = bb_predicate (gimple_bb (stmt));
+
+ for (i = 0; VEC_iterate (data_reference_p, drs, i, a); i++)
+ if (DR_STMT (a) == stmt
+ && DR_IS_WRITE (a))
+ {
+ bool found = false;
+ int x = DR_WRITTEN_AT_LEAST_ONCE (a);
+
+ if (x == 0)
+ return false;
+
+ if (x == 1)
+ continue;
+
+ for (j = 0; VEC_iterate (data_reference_p, drs, 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 (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 (!found)
+ {
+ DR_WRITTEN_AT_LEAST_ONCE (a) = 0;
+ return false;
+ }
+ }
+
+ return true;
+}
+
+/* Return true when the memory references of STMT won't trap in the
+ if-converted code. There are two things that we have to check for:
+
+ - writes to memory occur to writable memory: if-conversion of
+ memory writes transforms the conditional memory writes into
+ unconditional writes, i.e. "if (cond) A[i] = foo" is transformed
+ into "A[i] = cond ? foo : A[i]", and as the write to memory may not
+ be executed at all in the original code, it may be a readonly
+ memory. To check that A is not const-qualified, we check that
+ there exists at least an unconditional write to A in the current
+ function.
+
+ - reads or writes to memory are valid memory accesses for every
+ 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. */