+DEF_VEC_P(df_ref);
+DEF_VEC_ALLOC_P(df_ref,heap);
+static VEC(df_ref,heap) *use_def_ref;
+static VEC(df_ref,heap) *reg_defs;
+static VEC(df_ref,heap) *reg_defs_stack;
+
+/* The MD bitmaps are trimmed to include only live registers to cut
+ memory usage on testcases like insn-recog.c. Track live registers
+ in the basic block and do not perform forward propagation if the
+ destination is a dead pseudo occurring in a note. */
+static bitmap local_md;
+static bitmap local_lr;
+
+/* Return the only def in USE's use-def chain, or NULL if there is
+ more than one def in the chain. */
+
+static inline df_ref
+get_def_for_use (df_ref use)
+{
+ return VEC_index (df_ref, use_def_ref, DF_REF_ID (use));
+}
+
+
+/* Update the reg_defs vector with non-partial definitions in DEF_REC.
+ TOP_FLAG says which artificials uses should be used, when DEF_REC
+ is an artificial def vector. LOCAL_MD is modified as after a
+ df_md_simulate_* function; we do more or less the same processing
+ done there, so we do not use those functions. */
+
+#define DF_MD_GEN_FLAGS \
+ (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER)
+
+static void
+process_defs (df_ref *def_rec, int top_flag)
+{
+ df_ref def;
+ while ((def = *def_rec++) != NULL)
+ {
+ df_ref curr_def = VEC_index (df_ref, reg_defs, DF_REF_REGNO (def));
+ unsigned int dregno;
+
+ if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) != top_flag)
+ continue;
+
+ dregno = DF_REF_REGNO (def);
+ if (curr_def)
+ VEC_safe_push (df_ref, heap, reg_defs_stack, curr_def);
+ else
+ {
+ /* Do not store anything if "transitioning" from NULL to NULL. But
+ otherwise, push a special entry on the stack to tell the
+ leave_block callback that the entry in reg_defs was NULL. */
+ if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
+ ;
+ else
+ VEC_safe_push (df_ref, heap, reg_defs_stack, def);
+ }
+
+ if (DF_REF_FLAGS (def) & DF_MD_GEN_FLAGS)
+ {
+ bitmap_set_bit (local_md, dregno);
+ VEC_replace (df_ref, reg_defs, dregno, NULL);
+ }
+ else
+ {
+ bitmap_clear_bit (local_md, dregno);
+ VEC_replace (df_ref, reg_defs, dregno, def);
+ }
+ }
+}
+
+
+/* Fill the use_def_ref vector with values for the uses in USE_REC,
+ taking reaching definitions info from LOCAL_MD and REG_DEFS.
+ TOP_FLAG says which artificials uses should be used, when USE_REC
+ is an artificial use vector. */
+
+static void
+process_uses (df_ref *use_rec, int top_flag)
+{
+ df_ref use;
+ while ((use = *use_rec++) != NULL)
+ if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == top_flag)
+ {
+ unsigned int uregno = DF_REF_REGNO (use);
+ if (VEC_index (df_ref, reg_defs, uregno)
+ && !bitmap_bit_p (local_md, uregno)
+ && bitmap_bit_p (local_lr, uregno))
+ VEC_replace (df_ref, use_def_ref, DF_REF_ID (use),
+ VEC_index (df_ref, reg_defs, uregno));
+ }
+}
+
+
+static void
+single_def_use_enter_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb)
+{
+ int bb_index = bb->index;
+ struct df_md_bb_info *md_bb_info = df_md_get_bb_info (bb_index);
+ struct df_lr_bb_info *lr_bb_info = df_lr_get_bb_info (bb_index);
+ rtx insn;
+
+ bitmap_copy (local_md, &md_bb_info->in);
+ bitmap_copy (local_lr, &lr_bb_info->in);
+
+ /* Push a marker for the leave_block callback. */
+ VEC_safe_push (df_ref, heap, reg_defs_stack, NULL);
+
+ process_uses (df_get_artificial_uses (bb_index), DF_REF_AT_TOP);
+ process_defs (df_get_artificial_defs (bb_index), DF_REF_AT_TOP);
+
+ /* We don't call df_simulate_initialize_forwards, as it may overestimate
+ the live registers if there are unused artificial defs. We prefer
+ liveness to be underestimated. */
+
+ FOR_BB_INSNS (bb, insn)
+ if (INSN_P (insn))
+ {
+ unsigned int uid = INSN_UID (insn);
+ process_uses (DF_INSN_UID_USES (uid), 0);
+ process_uses (DF_INSN_UID_EQ_USES (uid), 0);
+ process_defs (DF_INSN_UID_DEFS (uid), 0);
+ df_simulate_one_insn_forwards (bb, insn, local_lr);
+ }
+
+ process_uses (df_get_artificial_uses (bb_index), 0);
+ process_defs (df_get_artificial_defs (bb_index), 0);
+}
+
+/* Pop the definitions created in this basic block when leaving its
+ dominated parts. */
+
+static void
+single_def_use_leave_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
+ basic_block bb ATTRIBUTE_UNUSED)
+{
+ df_ref saved_def;
+ while ((saved_def = VEC_pop (df_ref, reg_defs_stack)) != NULL)
+ {
+ unsigned int dregno = DF_REF_REGNO (saved_def);
+
+ /* See also process_defs. */
+ if (saved_def == VEC_index (df_ref, reg_defs, dregno))
+ VEC_replace (df_ref, reg_defs, dregno, NULL);
+ else
+ VEC_replace (df_ref, reg_defs, dregno, saved_def);
+ }
+}
+
+
+/* Build a vector holding the reaching definitions of uses reached by a
+ single dominating definition. */
+
+static void
+build_single_def_use_links (void)
+{
+ struct dom_walk_data walk_data;
+
+ /* We use the multiple definitions problem to compute our restricted
+ use-def chains. */
+ df_set_flags (DF_EQ_NOTES);
+ df_md_add_problem ();
+ df_note_add_problem ();
+ df_analyze ();
+ df_maybe_reorganize_use_refs (DF_REF_ORDER_BY_INSN_WITH_NOTES);
+
+ use_def_ref = VEC_alloc (df_ref, heap, DF_USES_TABLE_SIZE ());
+ VEC_safe_grow_cleared (df_ref, heap, use_def_ref, DF_USES_TABLE_SIZE ());
+
+ reg_defs = VEC_alloc (df_ref, heap, max_reg_num ());
+ VEC_safe_grow_cleared (df_ref, heap, reg_defs, max_reg_num ());
+
+ reg_defs_stack = VEC_alloc (df_ref, heap, n_basic_blocks * 10);
+ local_md = BITMAP_ALLOC (NULL);
+ local_lr = BITMAP_ALLOC (NULL);
+
+ /* Walk the dominator tree looking for single reaching definitions
+ dominating the uses. This is similar to how SSA form is built. */
+ walk_data.dom_direction = CDI_DOMINATORS;
+ walk_data.initialize_block_local_data = NULL;
+ walk_data.before_dom_children = single_def_use_enter_block;
+ walk_data.after_dom_children = single_def_use_leave_block;
+
+ init_walk_dominator_tree (&walk_data);
+ walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
+ fini_walk_dominator_tree (&walk_data);
+
+ BITMAP_FREE (local_lr);
+ BITMAP_FREE (local_md);
+ VEC_free (df_ref, heap, reg_defs);
+ VEC_free (df_ref, heap, reg_defs_stack);
+}
+