+/* Finds the outermost loop between OUTER and LOOP in that the memory reference
+ REF is independent. If REF is not independent in LOOP, NULL is returned
+ instead. */
+
+static struct loop *
+outermost_indep_loop (struct loop *outer, struct loop *loop, mem_ref_p ref)
+{
+ struct loop *aloop;
+
+ if (bitmap_bit_p (ref->stored, loop->num))
+ return NULL;
+
+ for (aloop = outer;
+ aloop != loop;
+ aloop = superloop_at_depth (loop, loop_depth (aloop) + 1))
+ if (!bitmap_bit_p (ref->stored, aloop->num)
+ && ref_indep_loop_p (aloop, ref))
+ return aloop;
+
+ if (ref_indep_loop_p (loop, ref))
+ return loop;
+ else
+ return NULL;
+}
+
+/* If there is a simple load or store to a memory reference in STMT, returns
+ the location of the memory reference, and sets IS_STORE according to whether
+ it is a store or load. Otherwise, returns NULL. */
+
+static tree *
+simple_mem_ref_in_stmt (gimple stmt, bool *is_store)
+{
+ tree *lhs;
+ enum tree_code code;
+
+ /* Recognize MEM = (SSA_NAME | invariant) and SSA_NAME = MEM patterns. */
+ if (gimple_code (stmt) != GIMPLE_ASSIGN)
+ return NULL;
+
+ code = gimple_assign_rhs_code (stmt);
+
+ lhs = gimple_assign_lhs_ptr (stmt);
+
+ if (TREE_CODE (*lhs) == SSA_NAME)
+ {
+ if (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS
+ || !is_gimple_addressable (gimple_assign_rhs1 (stmt)))
+ return NULL;
+
+ *is_store = false;
+ return gimple_assign_rhs1_ptr (stmt);
+ }
+ else if (code == SSA_NAME
+ || (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
+ && is_gimple_min_invariant (gimple_assign_rhs1 (stmt))))
+ {
+ *is_store = true;
+ return lhs;
+ }
+ else
+ return NULL;
+}
+
+/* Returns the memory reference contained in STMT. */
+
+static mem_ref_p
+mem_ref_in_stmt (gimple stmt)
+{
+ bool store;
+ tree *mem = simple_mem_ref_in_stmt (stmt, &store);
+ hashval_t hash;
+ mem_ref_p ref;
+
+ if (!mem)
+ return NULL;
+ gcc_assert (!store);
+
+ hash = iterative_hash_expr (*mem, 0);
+ ref = (mem_ref_p) htab_find_with_hash (memory_accesses.refs, *mem, hash);
+
+ gcc_assert (ref != NULL);
+ return ref;
+}
+
+/* From a controlling predicate in DOM determine the arguments from
+ the PHI node PHI that are chosen if the predicate evaluates to
+ true and false and store them to *TRUE_ARG_P and *FALSE_ARG_P if
+ they are non-NULL. Returns true if the arguments can be determined,
+ else return false. */
+
+static bool
+extract_true_false_args_from_phi (basic_block dom, gimple phi,
+ tree *true_arg_p, tree *false_arg_p)
+{
+ basic_block bb = gimple_bb (phi);
+ edge true_edge, false_edge, tem;
+ tree arg0 = NULL_TREE, arg1 = NULL_TREE;
+
+ /* We have to verify that one edge into the PHI node is dominated
+ by the true edge of the predicate block and the other edge
+ dominated by the false edge. This ensures that the PHI argument
+ we are going to take is completely determined by the path we
+ take from the predicate block.
+ We can only use BB dominance checks below if the destination of
+ the true/false edges are dominated by their edge, thus only
+ have a single predecessor. */
+ extract_true_false_edges_from_block (dom, &true_edge, &false_edge);
+ tem = EDGE_PRED (bb, 0);
+ if (tem == true_edge
+ || (single_pred_p (true_edge->dest)
+ && (tem->src == true_edge->dest
+ || dominated_by_p (CDI_DOMINATORS,
+ tem->src, true_edge->dest))))
+ arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
+ else if (tem == false_edge
+ || (single_pred_p (false_edge->dest)
+ && (tem->src == false_edge->dest
+ || dominated_by_p (CDI_DOMINATORS,
+ tem->src, false_edge->dest))))
+ arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
+ else
+ return false;
+ tem = EDGE_PRED (bb, 1);
+ if (tem == true_edge
+ || (single_pred_p (true_edge->dest)
+ && (tem->src == true_edge->dest
+ || dominated_by_p (CDI_DOMINATORS,
+ tem->src, true_edge->dest))))
+ arg0 = PHI_ARG_DEF (phi, tem->dest_idx);
+ else if (tem == false_edge
+ || (single_pred_p (false_edge->dest)
+ && (tem->src == false_edge->dest
+ || dominated_by_p (CDI_DOMINATORS,
+ tem->src, false_edge->dest))))
+ arg1 = PHI_ARG_DEF (phi, tem->dest_idx);
+ else
+ return false;
+ if (!arg0 || !arg1)
+ return false;
+
+ if (true_arg_p)
+ *true_arg_p = arg0;
+ if (false_arg_p)
+ *false_arg_p = arg1;
+
+ return true;
+}
+