+
+/* Insert extra phis to merge values that are fully available from
+ preds of BLOCK, but have no dominating representative coming from
+ block DOM. */
+
+static void
+insert_extra_phis (basic_block block, basic_block dom)
+{
+
+ if (!single_pred_p (block))
+ {
+ edge e;
+ edge_iterator ei;
+ bool first = true;
+ bitmap_set_t tempset = bitmap_set_new ();
+
+ FOR_EACH_EDGE (e, ei, block->preds)
+ {
+ /* We cannot handle abnormal incoming edges correctly. */
+ if (e->flags & EDGE_ABNORMAL)
+ return;
+
+ if (first)
+ {
+ bitmap_set_copy (tempset, AVAIL_OUT (e->src));
+ first = false;
+ }
+ else
+ bitmap_set_and (tempset, AVAIL_OUT (e->src));
+ }
+
+ if (dom)
+ bitmap_set_and_compl (tempset, AVAIL_OUT (dom));
+
+ if (!bitmap_set_empty_p (tempset))
+ {
+ unsigned int i;
+ bitmap_iterator bi;
+
+ EXECUTE_IF_SET_IN_BITMAP (tempset->expressions, 0, i, bi)
+ {
+ tree name = ssa_name (i);
+ tree val = get_value_handle (name);
+ tree temp;
+
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
+ continue;
+
+ if (!mergephitemp
+ || TREE_TYPE (name) != TREE_TYPE (mergephitemp))
+ {
+ mergephitemp = create_tmp_var (TREE_TYPE (name),
+ "mergephitmp");
+ get_var_ann (mergephitemp);
+ }
+ temp = mergephitemp;
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Creating phi ");
+ print_generic_expr (dump_file, temp, 0);
+ fprintf (dump_file, " to merge available but not dominating values ");
+ }
+
+ add_referenced_tmp_var (temp);
+ temp = create_phi_node (temp, block);
+ NECESSARY (temp) = 0;
+ VEC_safe_push (tree, heap, inserted_exprs, temp);
+
+ FOR_EACH_EDGE (e, ei, block->preds)
+ {
+ tree leader = bitmap_find_leader (AVAIL_OUT (e->src), val);
+
+ gcc_assert (leader);
+ add_phi_arg (temp, leader, e);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ print_generic_expr (dump_file, leader, 0);
+ fprintf (dump_file, " in block %d,", e->src->index);
+ }
+ }
+
+ vn_add (PHI_RESULT (temp), val);
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, "\n");
+ }
+ }
+ }
+}
+
+/* Given a statement STMT and its right hand side which is a load, try
+ to look for the expression stored in the location for the load, and
+ return true if a useful equivalence was recorded for LHS. */
+
+static bool
+try_look_through_load (tree lhs, tree mem_ref, tree stmt, basic_block block)
+{
+ tree store_stmt = NULL;
+ tree rhs;
+ ssa_op_iter i;
+ tree vuse;
+
+ FOR_EACH_SSA_TREE_OPERAND (vuse, stmt, i, SSA_OP_VIRTUAL_USES)
+ {
+ tree def_stmt;
+
+ gcc_assert (TREE_CODE (vuse) == SSA_NAME);
+ def_stmt = SSA_NAME_DEF_STMT (vuse);
+
+ /* If there is no useful statement for this VUSE, we'll not find a
+ useful expression to return either. Likewise, if there is a
+ statement but it is not a simple assignment or it has virtual
+ uses, we can stop right here. Note that this means we do
+ not look through PHI nodes, which is intentional. */
+ if (!def_stmt
+ || TREE_CODE (def_stmt) != MODIFY_EXPR
+ || !ZERO_SSA_OPERANDS (def_stmt, SSA_OP_VIRTUAL_USES))
+ return false;
+
+ /* If this is not the same statement as one we have looked at for
+ another VUSE of STMT already, we have two statements producing
+ something that reaches our STMT. */
+ if (store_stmt && store_stmt != def_stmt)
+ return false;
+ else
+ {
+ /* Is this a store to the exact same location as the one we are
+ loading from in STMT? */
+ if (!operand_equal_p (TREE_OPERAND (def_stmt, 0), mem_ref, 0))
+ return false;
+
+ /* Otherwise remember this statement and see if all other VUSEs
+ come from the same statement. */
+ store_stmt = def_stmt;
+ }
+ }
+
+ /* Alright then, we have visited all VUSEs of STMT and we've determined
+ that all of them come from the same statement STORE_STMT. See if there
+ is a useful expression we can deduce from STORE_STMT. */
+ rhs = TREE_OPERAND (store_stmt, 1);
+ if ((TREE_CODE (rhs) == SSA_NAME
+ && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs))
+ || is_gimple_min_invariant (rhs)
+ || TREE_CODE (rhs) == ADDR_EXPR
+ || TREE_INVARIANT (rhs))
+ {
+
+ /* Yay! Compute a value number for the RHS of the statement and
+ add its value to the AVAIL_OUT set for the block. Add the LHS
+ to TMP_GEN. */
+ add_to_sets (lhs, rhs, store_stmt, TMP_GEN (block), AVAIL_OUT (block));
+ if (TREE_CODE (rhs) == SSA_NAME
+ && !is_undefined_value (rhs))
+ value_insert_into_set (EXP_GEN (block), rhs);
+ return true;
+ }
+
+ return false;
+}
+
+/* Return a copy of NODE that is stored in the temporary alloc_pool's.
+ This is made recursively true, so that the operands are stored in
+ the pool as well. */
+
+static tree
+poolify_tree (tree node)
+{
+ switch (TREE_CODE (node))
+ {
+ case INDIRECT_REF:
+ {
+ tree temp = pool_alloc (reference_node_pool);
+ memcpy (temp, node, tree_size (node));
+ TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
+ return temp;
+ }
+ break;
+ case MODIFY_EXPR:
+ {
+ tree temp = pool_alloc (modify_expr_node_pool);
+ memcpy (temp, node, tree_size (node));
+ TREE_OPERAND (temp, 0) = poolify_tree (TREE_OPERAND (temp, 0));
+ TREE_OPERAND (temp, 1) = poolify_tree (TREE_OPERAND (temp, 1));
+ return temp;
+ }
+ break;
+ case SSA_NAME:
+ case INTEGER_CST:
+ case STRING_CST:
+ case REAL_CST:
+ case PARM_DECL:
+ case VAR_DECL:
+ case RESULT_DECL:
+ return node;
+ default:
+ gcc_unreachable ();
+ }
+}
+
+static tree modify_expr_template;
+
+/* Allocate a MODIFY_EXPR with TYPE, and operands OP1, OP2 in the
+ alloc pools and return it. */
+static tree
+poolify_modify_expr (tree type, tree op1, tree op2)
+{
+ if (modify_expr_template == NULL)
+ modify_expr_template = build2 (MODIFY_EXPR, type, op1, op2);
+
+ TREE_OPERAND (modify_expr_template, 0) = op1;
+ TREE_OPERAND (modify_expr_template, 1) = op2;
+ TREE_TYPE (modify_expr_template) = type;
+
+ return poolify_tree (modify_expr_template);
+}
+
+
+/* For each real store operation of the form
+ *a = <value> that we see, create a corresponding fake store of the
+ form storetmp_<version> = *a.
+
+ This enables AVAIL computation to mark the results of stores as
+ available. Without this, you'd need to do some computation to
+ mark the result of stores as ANTIC and AVAIL at all the right
+ points.
+ To save memory, we keep the store
+ statements pool allocated until we decide whether they are
+ necessary or not. */
+
+static void
+insert_fake_stores (void)
+{
+ basic_block block;
+
+ FOR_ALL_BB (block)
+ {
+ block_stmt_iterator bsi;
+ for (bsi = bsi_start (block); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+
+ /* We can't generate SSA names for stores that are complex
+ or aggregate. We also want to ignore things whose
+ virtual uses occur in abnormal phis. */
+
+ if (TREE_CODE (stmt) == MODIFY_EXPR
+ && TREE_CODE (TREE_OPERAND (stmt, 0)) == INDIRECT_REF
+ && !AGGREGATE_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 0)))
+ && TREE_CODE (TREE_TYPE (TREE_OPERAND (stmt, 0))) != COMPLEX_TYPE)
+ {
+ ssa_op_iter iter;
+ def_operand_p defp;
+ tree lhs = TREE_OPERAND (stmt, 0);
+ tree rhs = TREE_OPERAND (stmt, 1);
+ tree new;
+ bool notokay = false;
+
+ FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_VIRTUAL_DEFS)
+ {
+ tree defvar = DEF_FROM_PTR (defp);
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (defvar))
+ {
+ notokay = true;
+ break;
+ }
+ }
+
+ if (notokay)
+ continue;
+
+ if (!storetemp || TREE_TYPE (rhs) != TREE_TYPE (storetemp))
+ {
+ storetemp = create_tmp_var (TREE_TYPE (rhs), "storetmp");
+ get_var_ann (storetemp);
+ }
+
+ new = poolify_modify_expr (TREE_TYPE (stmt), storetemp, lhs);
+
+ lhs = make_ssa_name (storetemp, new);
+ TREE_OPERAND (new, 0) = lhs;
+ create_ssa_artficial_load_stmt (new, stmt);
+
+ NECESSARY (new) = 0;
+ VEC_safe_push (tree, heap, inserted_exprs, new);
+ VEC_safe_push (tree, heap, need_creation, new);
+ bsi_insert_after (&bsi, new, BSI_NEW_STMT);
+ }
+ }
+ }
+}
+
+/* Turn the pool allocated fake stores that we created back into real
+ GC allocated ones if they turned out to be necessary to PRE some
+ expressions. */
+
+static void
+realify_fake_stores (void)
+{
+ unsigned int i;
+ tree stmt;
+
+ for (i = 0; VEC_iterate (tree, need_creation, i, stmt); i++)
+ {
+ if (NECESSARY (stmt))
+ {
+ block_stmt_iterator bsi;
+ tree newstmt;
+
+ /* Mark the temp variable as referenced */
+ add_referenced_tmp_var (SSA_NAME_VAR (TREE_OPERAND (stmt, 0)));
+
+ /* Put the new statement in GC memory, fix up the annotation
+ and SSA_NAME_DEF_STMT on it, and then put it in place of
+ the old statement in the IR stream. */
+ newstmt = unshare_expr (stmt);
+ SSA_NAME_DEF_STMT (TREE_OPERAND (newstmt, 0)) = newstmt;
+
+ newstmt->common.ann = stmt->common.ann;
+
+ bsi = bsi_for_stmt (stmt);
+ bsi_replace (&bsi, newstmt, true);
+ }
+ else
+ release_defs (stmt);
+ }
+}
+
+