diff mbox

allocate combine.c:LOG_LINKS in an obstack

Message ID 20110405135941.GA27880@nightcrawler
State New
Headers show

Commit Message

Nathan Froyd April 5, 2011, 1:59 p.m. UTC 
On Mon, Apr 04, 2011 at 02:49:54PM -0400, Nathan Froyd wrote:
> This patch does just what $SUBJECT suggests.

v2, now with obstacks!

Tested on x86_64-unknown-linux-gnu.  OK to commit?

-Nathan

	* combine.c: Include obstack.h
	(struct insn_link): Define.
	(uid_log_links): Adjust type.
	(FOR_EACH_LOG_LINK): New macro.
	(insn_link_obstack): Declare.
	(alloc_insn_link): Define.
	(create_log_links): Call it.  Use FOR_EACH_LOG_LINK and adjust
	type of link variables.
	(find_single_use, insn_a_feeds_b, combine_instructions): Likewise.
	(try_combine, record_promoted_values, distribute_notes): Likewise.
	(distribute_links): Likewise.  Tweak prototype.
	(clear_log_links): Delete.
	(adjust_for_new_dest): Call alloc_insn_link.
	* Makefile.in (combine.o): Depend on $(OBSTACK_H).

Comments

Richard Biener April 5, 2011, 2:11 p.m. UTC | #1 
On Tue, Apr 5, 2011 at 3:59 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
> On Mon, Apr 04, 2011 at 02:49:54PM -0400, Nathan Froyd wrote:
>> This patch does just what $SUBJECT suggests.
>
> v2, now with obstacks!
>
> Tested on x86_64-unknown-linux-gnu.  OK to commit?

Ok.

Thanks,
Richard.

> -Nathan
>
>        * combine.c: Include obstack.h
>        (struct insn_link): Define.
>        (uid_log_links): Adjust type.
>        (FOR_EACH_LOG_LINK): New macro.
>        (insn_link_obstack): Declare.
>        (alloc_insn_link): Define.
>        (create_log_links): Call it.  Use FOR_EACH_LOG_LINK and adjust
>        type of link variables.
>        (find_single_use, insn_a_feeds_b, combine_instructions): Likewise.
>        (try_combine, record_promoted_values, distribute_notes): Likewise.
>        (distribute_links): Likewise.  Tweak prototype.
>        (clear_log_links): Delete.
>        (adjust_for_new_dest): Call alloc_insn_link.
>        * Makefile.in (combine.o): Depend on $(OBSTACK_H).
>
> diff --git a/gcc/Makefile.in b/gcc/Makefile.in
> index 16779bd..d47a69e 100644
> --- a/gcc/Makefile.in
> +++ b/gcc/Makefile.in
> @@ -3247,7 +3247,8 @@ combine.o : combine.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
>    $(FLAGS_H) $(FUNCTION_H) insn-config.h $(INSN_ATTR_H) $(REGS_H) $(EXPR_H) \
>    rtlhooks-def.h $(BASIC_BLOCK_H) $(RECOG_H) hard-reg-set.h \
>    $(DIAGNOSTIC_CORE_H) $(TM_P_H) $(TREE_H) $(TARGET_H) output.h $(PARAMS_H) $(OPTABS_H) \
> -   insn-codes.h $(TIMEVAR_H) $(TREE_PASS_H) $(DF_H) vecprim.h $(CGRAPH_H)
> +   insn-codes.h $(TIMEVAR_H) $(TREE_PASS_H) $(DF_H) vecprim.h $(CGRAPH_H) \
> +   $(OBSTACK_H)
>  reginfo.o : reginfo.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
>    hard-reg-set.h $(FLAGS_H) $(BASIC_BLOCK_H) addresses.h $(REGS_H) \
>    insn-config.h $(RECOG_H) reload.h $(DIAGNOSTIC_CORE_H) \
> diff --git a/gcc/combine.c b/gcc/combine.c
> index 37236cc..30b7fdd 100644
> --- a/gcc/combine.c
> +++ b/gcc/combine.c
> @@ -104,6 +104,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "tree-pass.h"
>  #include "df.h"
>  #include "cgraph.h"
> +#include "obstack.h"
>
>  /* Number of attempts to combine instructions in this function.  */
>
> @@ -309,13 +310,38 @@ static int max_uid_known;
>  static int *uid_insn_cost;
>
>  /* The following array records the LOG_LINKS for every insn in the
> -   instruction stream as an INSN_LIST rtx.  */
> +   instruction stream as struct insn_link pointers.  */
>
> -static rtx *uid_log_links;
> +struct insn_link {
> +  rtx insn;
> +  struct insn_link *next;
> +};
> +
> +static struct insn_link **uid_log_links;
>
>  #define INSN_COST(INSN)                (uid_insn_cost[INSN_UID (INSN)])
>  #define LOG_LINKS(INSN)                (uid_log_links[INSN_UID (INSN)])
>
> +#define FOR_EACH_LOG_LINK(L, INSN)                             \
> +  for ((L) = LOG_LINKS (INSN); (L); (L) = (L)->next)
> +
> +/* Links for LOG_LINKS are allocated from this obstack.  */
> +
> +static struct obstack insn_link_obstack;
> +
> +/* Allocate a link.  */
> +
> +static inline struct insn_link *
> +alloc_insn_link (rtx insn, struct insn_link *next)
> +{
> +  struct insn_link *l
> +    = (struct insn_link *) obstack_alloc (&insn_link_obstack,
> +                                         sizeof (struct insn_link));
> +  l->insn = insn;
> +  l->next = next;
> +  return l;
> +}
> +
>  /* Incremented for each basic block.  */
>
>  static int label_tick;
> @@ -438,7 +464,7 @@ static int reg_dead_at_p (rtx, rtx);
>  static void move_deaths (rtx, rtx, int, rtx, rtx *);
>  static int reg_bitfield_target_p (rtx, rtx);
>  static void distribute_notes (rtx, rtx, rtx, rtx, rtx, rtx, rtx);
> -static void distribute_links (rtx);
> +static void distribute_links (struct insn_link *);
>  static void mark_used_regs_combine (rtx);
>  static void record_promoted_value (rtx, rtx);
>  static int unmentioned_reg_p_1 (rtx *, void *);
> @@ -609,7 +635,7 @@ find_single_use (rtx dest, rtx insn, rtx *ploc)
>   basic_block bb;
>   rtx next;
>   rtx *result;
> -  rtx link;
> +  struct insn_link *link;
>
>  #ifdef HAVE_cc0
>   if (dest == cc0_rtx)
> @@ -635,8 +661,8 @@ find_single_use (rtx dest, rtx insn, rtx *ploc)
>        next = NEXT_INSN (next))
>     if (INSN_P (next) && dead_or_set_p (next, dest))
>       {
> -       for (link = LOG_LINKS (next); link; link = XEXP (link, 1))
> -         if (XEXP (link, 0) == insn)
> +       FOR_EACH_LOG_LINK (link, next)
> +         if (link->insn == insn)
>            break;
>
>        if (link)
> @@ -985,15 +1011,14 @@ create_log_links (void)
>                       || asm_noperands (PATTERN (use_insn)) < 0)
>                    {
>                      /* Don't add duplicate links between instructions.  */
> -                     rtx links;
> -                     for (links = LOG_LINKS (use_insn); links;
> -                          links = XEXP (links, 1))
> -                       if (insn == XEXP (links, 0))
> +                     struct insn_link *links;
> +                     FOR_EACH_LOG_LINK (links, use_insn)
> +                       if (insn == links->insn)
>                          break;
>
>                      if (!links)
> -                       LOG_LINKS (use_insn) =
> -                         alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
> +                       LOG_LINKS (use_insn)
> +                         = alloc_insn_link (insn, LOG_LINKS (use_insn));
>                    }
>                 }
>               next_use[regno] = NULL_RTX;
> @@ -1017,18 +1042,6 @@ create_log_links (void)
>   free (next_use);
>  }
>
> -/* Clear LOG_LINKS fields of insns.  */
> -
> -static void
> -clear_log_links (void)
> -{
> -  rtx insn;
> -
> -  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
> -    if (INSN_P (insn))
> -      free_INSN_LIST_list (&LOG_LINKS (insn));
> -}
> -
>  /* Walk the LOG_LINKS of insn B to see if we find a reference to A.  Return
>    true if we found a LOG_LINK that proves that A feeds B.  This only works
>    if there are no instructions between A and B which could have a link
> @@ -1039,9 +1052,9 @@ clear_log_links (void)
>  static bool
>  insn_a_feeds_b (rtx a, rtx b)
>  {
> -  rtx links;
> -  for (links = LOG_LINKS (b); links; links = XEXP (links, 1))
> -    if (XEXP (links, 0) == a)
> +  struct insn_link *links;
> +  FOR_EACH_LOG_LINK (links, b)
> +    if (links->insn == a)
>       return true;
>  #ifdef HAVE_cc0
>   if (sets_cc0_p (a))
> @@ -1062,7 +1075,7 @@ combine_instructions (rtx f, unsigned int nregs)
>  #ifdef HAVE_cc0
>   rtx prev;
>  #endif
> -  rtx links, nextlinks;
> +  struct insn_link *links, *nextlinks;
>   rtx first;
>   basic_block last_bb;
>
> @@ -1086,8 +1099,9 @@ combine_instructions (rtx f, unsigned int nregs)
>
>   /* Allocate array for insn info.  */
>   max_uid_known = get_max_uid ();
> -  uid_log_links = XCNEWVEC (rtx, max_uid_known + 1);
> +  uid_log_links = XCNEWVEC (struct insn_link *, max_uid_known + 1);
>   uid_insn_cost = XCNEWVEC (int, max_uid_known + 1);
> +  gcc_obstack_init (&insn_link_obstack);
>
>   nonzero_bits_mode = mode_for_size (HOST_BITS_PER_WIDE_INT, MODE_INT, 0);
>
> @@ -1188,26 +1202,24 @@ combine_instructions (rtx f, unsigned int nregs)
>
>              /* Try this insn with each insn it links back to.  */
>
> -             for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
> -               if ((next = try_combine (insn, XEXP (links, 0), NULL_RTX,
> +             FOR_EACH_LOG_LINK (links, insn)
> +               if ((next = try_combine (insn, links->insn, NULL_RTX,
>                                         NULL_RTX, &new_direct_jump_p)) != 0)
>                  goto retry;
>
>              /* Try each sequence of three linked insns ending with this one.  */
>
> -             for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
> +             FOR_EACH_LOG_LINK (links, insn)
>                {
> -                 rtx link = XEXP (links, 0);
> +                 rtx link = links->insn;
>
>                  /* If the linked insn has been replaced by a note, then there
>                     is no point in pursuing this chain any further.  */
>                  if (NOTE_P (link))
>                    continue;
>
> -                 for (nextlinks = LOG_LINKS (link);
> -                      nextlinks;
> -                      nextlinks = XEXP (nextlinks, 1))
> -                   if ((next = try_combine (insn, link, XEXP (nextlinks, 0),
> +                 FOR_EACH_LOG_LINK (nextlinks, link)
> +                   if ((next = try_combine (insn, link, nextlinks->insn,
>                                             NULL_RTX,
>                                             &new_direct_jump_p)) != 0)
>                      goto retry;
> @@ -1230,9 +1242,8 @@ combine_instructions (rtx f, unsigned int nregs)
>                                           &new_direct_jump_p)) != 0)
>                    goto retry;
>
> -                 for (nextlinks = LOG_LINKS (prev); nextlinks;
> -                      nextlinks = XEXP (nextlinks, 1))
> -                   if ((next = try_combine (insn, prev, XEXP (nextlinks, 0),
> +                 FOR_EACH_LOG_LINK (nextlinks, prev)
> +                   if ((next = try_combine (insn, prev, nextlinks->insn,
>                                             NULL_RTX,
>                                             &new_direct_jump_p)) != 0)
>                      goto retry;
> @@ -1250,9 +1261,8 @@ combine_instructions (rtx f, unsigned int nregs)
>                                           &new_direct_jump_p)) != 0)
>                    goto retry;
>
> -                 for (nextlinks = LOG_LINKS (prev); nextlinks;
> -                      nextlinks = XEXP (nextlinks, 1))
> -                   if ((next = try_combine (insn, prev, XEXP (nextlinks, 0),
> +                 FOR_EACH_LOG_LINK (nextlinks, prev)
> +                   if ((next = try_combine (insn, prev, nextlinks->insn,
>                                             NULL_RTX,
>                                             &new_direct_jump_p)) != 0)
>                      goto retry;
> @@ -1261,14 +1271,14 @@ combine_instructions (rtx f, unsigned int nregs)
>              /* Finally, see if any of the insns that this insn links to
>                 explicitly references CC0.  If so, try this insn, that insn,
>                 and its predecessor if it sets CC0.  */
> -             for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
> -               if (NONJUMP_INSN_P (XEXP (links, 0))
> -                   && GET_CODE (PATTERN (XEXP (links, 0))) == SET
> -                   && reg_mentioned_p (cc0_rtx, SET_SRC (PATTERN (XEXP (links, 0))))
> -                   && (prev = prev_nonnote_insn (XEXP (links, 0))) != 0
> +             FOR_EACH_LOG_LINK (links, insn)
> +               if (NONJUMP_INSN_P (links->insn)
> +                   && GET_CODE (PATTERN (links->insn)) == SET
> +                   && reg_mentioned_p (cc0_rtx, SET_SRC (PATTERN (links->insn)))
> +                   && (prev = prev_nonnote_insn (links->insn)) != 0
>                    && NONJUMP_INSN_P (prev)
>                    && sets_cc0_p (PATTERN (prev))
> -                   && (next = try_combine (insn, XEXP (links, 0),
> +                   && (next = try_combine (insn, links->insn,
>                                            prev, NULL_RTX,
>                                            &new_direct_jump_p)) != 0)
>                  goto retry;
> @@ -1276,73 +1286,70 @@ combine_instructions (rtx f, unsigned int nregs)
>
>              /* Try combining an insn with two different insns whose results it
>                 uses.  */
> -             for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
> -               for (nextlinks = XEXP (links, 1); nextlinks;
> -                    nextlinks = XEXP (nextlinks, 1))
> -                 if ((next = try_combine (insn, XEXP (links, 0),
> -                                          XEXP (nextlinks, 0), NULL_RTX,
> +             FOR_EACH_LOG_LINK (links, insn)
> +               for (nextlinks = links->next; nextlinks;
> +                    nextlinks = nextlinks->next)
> +                 if ((next = try_combine (insn, links->insn,
> +                                          nextlinks->insn, NULL_RTX,
>                                           &new_direct_jump_p)) != 0)
>                    goto retry;
>
>              /* Try four-instruction combinations.  */
> -             for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
> +             FOR_EACH_LOG_LINK (links, insn)
>                {
> -                 rtx next1;
> -                 rtx link = XEXP (links, 0);
> +                 struct insn_link *next1;
> +                 rtx link = links->insn;
>
>                  /* If the linked insn has been replaced by a note, then there
>                     is no point in pursuing this chain any further.  */
>                  if (NOTE_P (link))
>                    continue;
>
> -                 for (next1 = LOG_LINKS (link); next1; next1 = XEXP (next1, 1))
> +                 FOR_EACH_LOG_LINK (next1, link)
>                    {
> -                     rtx link1 = XEXP (next1, 0);
> +                     rtx link1 = next1->insn;
>                      if (NOTE_P (link1))
>                        continue;
>                      /* I0 -> I1 -> I2 -> I3.  */
> -                     for (nextlinks = LOG_LINKS (link1); nextlinks;
> -                          nextlinks = XEXP (nextlinks, 1))
> +                     FOR_EACH_LOG_LINK (nextlinks, link1)
>                        if ((next = try_combine (insn, link, link1,
> -                                                XEXP (nextlinks, 0),
> +                                                nextlinks->insn,
>                                                 &new_direct_jump_p)) != 0)
>                          goto retry;
>                      /* I0, I1 -> I2, I2 -> I3.  */
> -                     for (nextlinks = XEXP (next1, 1); nextlinks;
> -                          nextlinks = XEXP (nextlinks, 1))
> +                     for (nextlinks = next1->next; nextlinks;
> +                          nextlinks = nextlinks->next)
>                        if ((next = try_combine (insn, link, link1,
> -                                                XEXP (nextlinks, 0),
> +                                                nextlinks->insn,
>                                                 &new_direct_jump_p)) != 0)
>                          goto retry;
>                    }
>
> -                 for (next1 = XEXP (links, 1); next1; next1 = XEXP (next1, 1))
> +                 for (next1 = links->next; next1; next1 = next1->next)
>                    {
> -                     rtx link1 = XEXP (next1, 0);
> +                     rtx link1 = next1->insn;
>                      if (NOTE_P (link1))
>                        continue;
>                      /* I0 -> I2; I1, I2 -> I3.  */
> -                     for (nextlinks = LOG_LINKS (link); nextlinks;
> -                          nextlinks = XEXP (nextlinks, 1))
> +                     FOR_EACH_LOG_LINK (nextlinks, link)
>                        if ((next = try_combine (insn, link, link1,
> -                                                XEXP (nextlinks, 0),
> +                                                nextlinks->insn,
>                                                 &new_direct_jump_p)) != 0)
>                          goto retry;
>                      /* I0 -> I1; I1, I2 -> I3.  */
> -                     for (nextlinks = LOG_LINKS (link1); nextlinks;
> -                          nextlinks = XEXP (nextlinks, 1))
> +                     FOR_EACH_LOG_LINK (nextlinks, link1)
>                        if ((next = try_combine (insn, link, link1,
> -                                                XEXP (nextlinks, 0),
> +                                                nextlinks->insn,
>                                                 &new_direct_jump_p)) != 0)
>                          goto retry;
>                    }
>                }
>
>              /* Try this insn with each REG_EQUAL note it links back to.  */
> -             for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
> +             FOR_EACH_LOG_LINK (links, insn)
>                {
>                  rtx set, note;
> -                 rtx temp = XEXP (links, 0);
> +                 rtx temp = links->insn;
>                  if ((set = single_set (temp)) != 0
>                      && (note = find_reg_equal_equiv_note (temp)) != 0
>                      && (note = XEXP (note, 0), GET_CODE (note)) != EXPR_LIST
> @@ -1380,12 +1387,12 @@ combine_instructions (rtx f, unsigned int nregs)
>     }
>
>   default_rtl_profile ();
> -  clear_log_links ();
>   clear_bb_flags ();
>   new_direct_jump_p |= purge_all_dead_edges ();
>   delete_noop_moves ();
>
>   /* Clean up.  */
> +  obstack_free (&insn_link_obstack, NULL);
>   free (uid_log_links);
>   free (uid_insn_cost);
>   VEC_free (reg_stat_type, heap, reg_stat);
> @@ -1556,13 +1563,11 @@ set_nonzero_bits_and_sign_copies (rtx x, const_rtx set, void *data)
>          && !REGNO_REG_SET_P (DF_LR_IN (BLOCK_FOR_INSN (insn)),
>                               REGNO (x)))
>        {
> -         rtx link;
> +         struct insn_link *link;
>
> -         for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
> -           {
> -             if (dead_or_set_p (XEXP (link, 0), x))
> -               break;
> -           }
> +         FOR_EACH_LOG_LINK (link, insn)
> +           if (dead_or_set_p (link->insn, x))
> +             break;
>          if (!link)
>            {
>              rsp->nonzero_bits = GET_MODE_MASK (GET_MODE (x));
> @@ -2248,7 +2253,7 @@ adjust_for_new_dest (rtx insn)
>   /* The new insn will have a destination that was previously the destination
>      of an insn just above it.  Call distribute_links to make a LOG_LINK from
>      the next use of that destination.  */
> -  distribute_links (gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX));
> +  distribute_links (alloc_insn_link (insn, NULL));
>
>   df_insn_rescan (insn);
>  }
> @@ -2547,7 +2552,7 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
>
>   int maxreg;
>   rtx temp;
> -  rtx link;
> +  struct insn_link *link;
>   rtx other_pat = 0;
>   rtx new_other_notes;
>   int i;
> @@ -3929,7 +3934,7 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
>   if (swap_i2i3)
>     {
>       rtx insn;
> -      rtx link;
> +      struct insn_link *link;
>       rtx ni2dest;
>
>       /* I3 now uses what used to be its destination and which is now
> @@ -3959,10 +3964,9 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
>        {
>          if (INSN_P (insn) && reg_referenced_p (ni2dest, PATTERN (insn)))
>            {
> -             for (link = LOG_LINKS (insn); link;
> -                  link = XEXP (link, 1))
> -               if (XEXP (link, 0) == i3)
> -                 XEXP (link, 0) = i1;
> +             FOR_EACH_LOG_LINK (link, insn)
> +               if (link->insn == i3)
> +                 link->insn = i1;
>
>              break;
>            }
> @@ -3971,7 +3975,7 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
>
>   {
>     rtx i3notes, i2notes, i1notes = 0, i0notes = 0;
> -    rtx i3links, i2links, i1links = 0, i0links = 0;
> +    struct insn_link *i3links, *i2links, *i1links = 0, *i0links = 0;
>     rtx midnotes = 0;
>     int from_luid;
>     /* Compute which registers we expect to eliminate.  newi2pat may be setting
> @@ -4074,9 +4078,9 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
>                          || BB_HEAD (this_basic_block) != temp);
>                 temp = NEXT_INSN (temp))
>              if (temp != i3 && INSN_P (temp))
> -               for (link = LOG_LINKS (temp); link; link = XEXP (link, 1))
> -                 if (XEXP (link, 0) == i2)
> -                   XEXP (link, 0) = i3;
> +               FOR_EACH_LOG_LINK (link, temp)
> +                 if (link->insn == i2)
> +                   link->insn = i3;
>
>        if (i3notes)
>          {
> @@ -4090,9 +4094,9 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
>        i2notes = 0;
>       }
>
> -    LOG_LINKS (i3) = 0;
> +    LOG_LINKS (i3) = NULL;
>     REG_NOTES (i3) = 0;
> -    LOG_LINKS (i2) = 0;
> +    LOG_LINKS (i2) = NULL;
>     REG_NOTES (i2) = 0;
>
>     if (newi2pat)
> @@ -4111,7 +4115,7 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
>
>     if (i1)
>       {
> -       LOG_LINKS (i1) = 0;
> +       LOG_LINKS (i1) = NULL;
>        REG_NOTES (i1) = 0;
>        if (MAY_HAVE_DEBUG_INSNS)
>          propagate_for_debug (i1, i3, i1dest, i1src);
> @@ -4120,7 +4124,7 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
>
>     if (i0)
>       {
> -       LOG_LINKS (i0) = 0;
> +       LOG_LINKS (i0) = NULL;
>        REG_NOTES (i0) = 0;
>        if (MAY_HAVE_DEBUG_INSNS)
>          propagate_for_debug (i0, i3, i0dest, i0src);
> @@ -4231,7 +4235,8 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
>
>     if (REG_P (i2dest))
>       {
> -       rtx link, i2_insn = 0, i2_val = 0, set;
> +       struct insn_link *link;
> +       rtx i2_insn = 0, i2_val = 0, set;
>
>        /* The insn that used to set this register doesn't exist, and
>           this life of the register may not exist either.  See if one of
> @@ -4240,10 +4245,10 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
>           this and I2 set the register to a value that depended on its old
>           contents, we will get confused.  If this insn is used, thing
>           will be set correctly in combine_instructions.  */
> -       for (link = LOG_LINKS (i3); link; link = XEXP (link, 1))
> -         if ((set = single_set (XEXP (link, 0))) != 0
> +       FOR_EACH_LOG_LINK (link, i3)
> +         if ((set = single_set (link->insn)) != 0
>              && rtx_equal_p (i2dest, SET_DEST (set)))
> -           i2_insn = XEXP (link, 0), i2_val = SET_SRC (set);
> +           i2_insn = link->insn, i2_val = SET_SRC (set);
>
>        record_value_for_reg (i2dest, i2_insn, i2_val);
>
> @@ -4257,12 +4262,13 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
>
>     if (i1 && REG_P (i1dest))
>       {
> -       rtx link, i1_insn = 0, i1_val = 0, set;
> +       struct insn_link *link;
> +       rtx i1_insn = 0, i1_val = 0, set;
>
> -       for (link = LOG_LINKS (i3); link; link = XEXP (link, 1))
> -         if ((set = single_set (XEXP (link, 0))) != 0
> +       FOR_EACH_LOG_LINK (link, i3)
> +         if ((set = single_set (link->insn)) != 0
>              && rtx_equal_p (i1dest, SET_DEST (set)))
> -           i1_insn = XEXP (link, 0), i1_val = SET_SRC (set);
> +           i1_insn = link->insn, i1_val = SET_SRC (set);
>
>        record_value_for_reg (i1dest, i1_insn, i1_val);
>
> @@ -4272,12 +4278,13 @@ try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
>
>     if (i0 && REG_P (i0dest))
>       {
> -       rtx link, i0_insn = 0, i0_val = 0, set;
> +       struct insn_link *link;
> +       rtx i0_insn = 0, i0_val = 0, set;
>
> -       for (link = LOG_LINKS (i3); link; link = XEXP (link, 1))
> -         if ((set = single_set (XEXP (link, 0))) != 0
> +       FOR_EACH_LOG_LINK (link, i3)
> +         if ((set = single_set (link->insn)) != 0
>              && rtx_equal_p (i0dest, SET_DEST (set)))
> -           i0_insn = XEXP (link, 0), i0_val = SET_SRC (set);
> +           i0_insn = link->insn, i0_val = SET_SRC (set);
>
>        record_value_for_reg (i0dest, i0_insn, i0_val);
>
> @@ -12349,7 +12356,8 @@ record_dead_and_set_regs (rtx insn)
>  static void
>  record_promoted_value (rtx insn, rtx subreg)
>  {
> -  rtx links, set;
> +  struct insn_link *links;
> +  rtx set;
>   unsigned int regno = REGNO (SUBREG_REG (subreg));
>   enum machine_mode mode = GET_MODE (subreg);
>
> @@ -12360,14 +12368,14 @@ record_promoted_value (rtx insn, rtx subreg)
>     {
>       reg_stat_type *rsp;
>
> -      insn = XEXP (links, 0);
> +      insn = links->insn;
>       set = single_set (insn);
>
>       if (! set || !REG_P (SET_DEST (set))
>          || REGNO (SET_DEST (set)) != regno
>          || GET_MODE (SET_DEST (set)) != GET_MODE (SUBREG_REG (subreg)))
>        {
> -         links = XEXP (links, 1);
> +         links = links->next;
>          continue;
>        }
>
> @@ -13500,8 +13508,8 @@ distribute_notes (rtx notes, rtx from_insn, rtx i3, rtx i2, rtx elim_i2,
>                          && DF_INSN_LUID (from_insn) > DF_INSN_LUID (i2)
>                          && reg_referenced_p (XEXP (note, 0), PATTERN (i2)))
>                        {
> -                         rtx links = LOG_LINKS (place);
> -                         LOG_LINKS (place) = 0;
> +                         struct insn_link *links = LOG_LINKS (place);
> +                         LOG_LINKS (place) = NULL;
>                          distribute_links (links);
>                        }
>                      break;
> @@ -13632,9 +13640,9 @@ distribute_notes (rtx notes, rtx from_insn, rtx i3, rtx i2, rtx elim_i2,
>    pointing at I3 when I3's destination is changed.  */
>
>  static void
> -distribute_links (rtx links)
> +distribute_links (struct insn_link *links)
>  {
> -  rtx link, next_link;
> +  struct insn_link *link, *next_link;
>
>   for (link = links; link; link = next_link)
>     {
> @@ -13642,7 +13650,7 @@ distribute_links (rtx links)
>       rtx insn;
>       rtx set, reg;
>
> -      next_link = XEXP (link, 1);
> +      next_link = link->next;
>
>       /* If the insn that this link points to is a NOTE or isn't a single
>         set, ignore it.  In the latter case, it isn't clear what we
> @@ -13655,8 +13663,8 @@ distribute_links (rtx links)
>         replace I3, I2, and I1 by I3 and I2.  But in that case the
>         destination of I2 also remains unchanged.  */
>
> -      if (NOTE_P (XEXP (link, 0))
> -         || (set = single_set (XEXP (link, 0))) == 0)
> +      if (NOTE_P (link->insn)
> +         || (set = single_set (link->insn)) == 0)
>        continue;
>
>       reg = SET_DEST (set);
> @@ -13673,7 +13681,7 @@ distribute_links (rtx links)
>         I3 to I2.  Also note that not much searching is typically done here
>         since most links don't point very far away.  */
>
> -      for (insn = NEXT_INSN (XEXP (link, 0));
> +      for (insn = NEXT_INSN (link->insn);
>           (insn && (this_basic_block->next_bb == EXIT_BLOCK_PTR
>                     || BB_HEAD (this_basic_block->next_bb) != insn));
>           insn = NEXT_INSN (insn))
> @@ -13699,15 +13707,15 @@ distribute_links (rtx links)
>
>       if (place)
>        {
> -         rtx link2;
> +         struct insn_link *link2;
>
> -         for (link2 = LOG_LINKS (place); link2; link2 = XEXP (link2, 1))
> -           if (XEXP (link2, 0) == XEXP (link, 0))
> +         FOR_EACH_LOG_LINK (link2, place)
> +           if (link2->insn == link->insn)
>              break;
>
> -         if (link2 == 0)
> +         if (link2 == NULL)
>            {
> -             XEXP (link, 1) = LOG_LINKS (place);
> +             link->next = LOG_LINKS (place);
>              LOG_LINKS (place) = link;
>
>              /* Set added_links_insn to the earliest insn we added a
>
Steven Bosscher April 5, 2011, 2:42 p.m. UTC | #2 
On Tue, Apr 5, 2011 at 3:59 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
> On Mon, Apr 04, 2011 at 02:49:54PM -0400, Nathan Froyd wrote:
>> This patch does just what $SUBJECT suggests.
>
> v2, now with obstacks!

Still one TODO in doc/rtl.texi:

@findex LOG_LINKS
@item LOG_LINKS (@var{i})
A list (chain of @code{insn_list} expressions) giving information about
dependencies between instructions within a basic block.  Neither a jump
nor a label may come between the related insns.  These are only used by
the schedulers and by combine.  This is a deprecated data structure.
Def-use and use-def chains are now preferred.

Ciao!
Steven
Nathan Froyd April 5, 2011, 2:51 p.m. UTC | #3 
On Tue, Apr 05, 2011 at 04:42:27PM +0200, Steven Bosscher wrote:
> On Tue, Apr 5, 2011 at 3:59 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
> > v2, now with obstacks!
> 
> @findex LOG_LINKS
> @item LOG_LINKS (@var{i})
> A list (chain of @code{insn_list} expressions) giving information about
> dependencies between instructions within a basic block.  Neither a jump
> nor a label may come between the related insns.  These are only used by
> the schedulers and by combine.  This is a deprecated data structure.
> Def-use and use-def chains are now preferred.

So, being somewhat RTL-ignorant, is this patch going in the wrong
direction?  Should combine be using DF instead of constructing
LOG_LINKS?

-Nathan
Steven Bosscher April 5, 2011, 3:07 p.m. UTC | #4 
On Tue, Apr 5, 2011 at 4:51 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
> On Tue, Apr 05, 2011 at 04:42:27PM +0200, Steven Bosscher wrote:
>> On Tue, Apr 5, 2011 at 3:59 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
>> > v2, now with obstacks!
>>
>> @findex LOG_LINKS
>> @item LOG_LINKS (@var{i})
>> A list (chain of @code{insn_list} expressions) giving information about
>> dependencies between instructions within a basic block.  Neither a jump
>> nor a label may come between the related insns.  These are only used by
>> the schedulers and by combine.  This is a deprecated data structure.
>> Def-use and use-def chains are now preferred.
>
> So, being somewhat RTL-ignorant, is this patch going in the wrong
> direction?

Oh, not at all. Just documentation that needs updating! :)

Ciao!
Steven
Jeff Law April 5, 2011, 4:13 p.m. UTC | #5 
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On 04/05/11 08:51, Nathan Froyd wrote:
> On Tue, Apr 05, 2011 at 04:42:27PM +0200, Steven Bosscher wrote:
>> On Tue, Apr 5, 2011 at 3:59 PM, Nathan Froyd <froydnj@codesourcery.com> wrote:
>>> v2, now with obstacks!
>>
>> @findex LOG_LINKS
>> @item LOG_LINKS (@var{i})
>> A list (chain of @code{insn_list} expressions) giving information about
>> dependencies between instructions within a basic block.  Neither a jump
>> nor a label may come between the related insns.  These are only used by
>> the schedulers and by combine.  This is a deprecated data structure.
>> Def-use and use-def chains are now preferred.
> 
> So, being somewhat RTL-ignorant, is this patch going in the wrong
> direction?  Should combine be using DF instead of constructing
> LOG_LINKS?
Ideally, we'd like to get rid of LOG_LINKS in favor of DF; however, I
don't think anyone has looked at what would be needed to make that
happen for combine.c or at what the memory & compile-time implications
might be for such a change.

I still think your patch is a step forward as it should reduce the load
on the garbage collector.

Jeff
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
Comment: Using GnuPG with Fedora - http://enigmail.mozdev.org/

iQEcBAEBAgAGBQJNmz+iAAoJEBRtltQi2kC7NQAH/0GKXSsi3aOoZ/TCYYa2FIpI
CfFPLaE9lXfXkFLNIXrVKcWC+NkqbLcFxEQFLusyfQAU4Aqcc0sxFEg69hSCJLPG
EWCUBhLqd3YbHpv3pLkykV0nOrd8wBqt24NCbLKaALsNkyvWUGx/hsM3O2lUUbAJ
YnUmuyAzx2e5fSQ1WZvfNVb2/GXe7/p0QEDCq/yWf1l/6Pide4EtjWy4NPCbx1C9
AI+P+sqHWwmd6wPzTZTLamOlFCg0QNXwhSJ5eYL0WBkLjuxE9M4EHPiVuyta1Y8c
xkCOspGxsq6UdNycM6aGprlHS8uX8O5s4i//lTx/xq5U4n5USKLe3SbLn3Qk9MM=
=h8QI
-----END PGP SIGNATURE-----
Nathan Froyd April 5, 2011, 6:22 p.m. UTC | #6 
On Tue, Apr 05, 2011 at 09:59:43AM -0400, Nathan Froyd wrote:
> On Mon, Apr 04, 2011 at 02:49:54PM -0400, Nathan Froyd wrote:
> > This patch does just what $SUBJECT suggests.
> 
> v2, now with obstacks!

This broke compilation on AUTO_INC_DEC targets.  Currently putting
together a fix and testing via cross to powerpc-eabispe.

-Nathan
diff mbox

Patch

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 16779bd..d47a69e 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -3247,7 +3247,8 @@  combine.o : combine.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    $(FLAGS_H) $(FUNCTION_H) insn-config.h $(INSN_ATTR_H) $(REGS_H) $(EXPR_H) \
    rtlhooks-def.h $(BASIC_BLOCK_H) $(RECOG_H) hard-reg-set.h \
    $(DIAGNOSTIC_CORE_H) $(TM_P_H) $(TREE_H) $(TARGET_H) output.h $(PARAMS_H) $(OPTABS_H) \
-   insn-codes.h $(TIMEVAR_H) $(TREE_PASS_H) $(DF_H) vecprim.h $(CGRAPH_H)
+   insn-codes.h $(TIMEVAR_H) $(TREE_PASS_H) $(DF_H) vecprim.h $(CGRAPH_H) \
+   $(OBSTACK_H)
 reginfo.o : reginfo.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
    hard-reg-set.h $(FLAGS_H) $(BASIC_BLOCK_H) addresses.h $(REGS_H) \
    insn-config.h $(RECOG_H) reload.h $(DIAGNOSTIC_CORE_H) \
diff --git a/gcc/combine.c b/gcc/combine.c
index 37236cc..30b7fdd 100644
--- a/gcc/combine.c
+++ b/gcc/combine.c
@@ -104,6 +104,7 @@  along with GCC; see the file COPYING3.  If not see
 #include "tree-pass.h"
 #include "df.h"
 #include "cgraph.h"
+#include "obstack.h"
 
 /* Number of attempts to combine instructions in this function.  */
 
@@ -309,13 +310,38 @@  static int max_uid_known;
 static int *uid_insn_cost;
 
 /* The following array records the LOG_LINKS for every insn in the
-   instruction stream as an INSN_LIST rtx.  */
+   instruction stream as struct insn_link pointers.  */
 
-static rtx *uid_log_links;
+struct insn_link {
+  rtx insn;
+  struct insn_link *next;
+};
+
+static struct insn_link **uid_log_links;
 
 #define INSN_COST(INSN)		(uid_insn_cost[INSN_UID (INSN)])
 #define LOG_LINKS(INSN)		(uid_log_links[INSN_UID (INSN)])
 
+#define FOR_EACH_LOG_LINK(L, INSN)				\
+  for ((L) = LOG_LINKS (INSN); (L); (L) = (L)->next)
+
+/* Links for LOG_LINKS are allocated from this obstack.  */
+
+static struct obstack insn_link_obstack;
+
+/* Allocate a link.  */
+
+static inline struct insn_link *
+alloc_insn_link (rtx insn, struct insn_link *next)
+{
+  struct insn_link *l
+    = (struct insn_link *) obstack_alloc (&insn_link_obstack,
+					  sizeof (struct insn_link));
+  l->insn = insn;
+  l->next = next;
+  return l;
+}
+
 /* Incremented for each basic block.  */
 
 static int label_tick;
@@ -438,7 +464,7 @@  static int reg_dead_at_p (rtx, rtx);
 static void move_deaths (rtx, rtx, int, rtx, rtx *);
 static int reg_bitfield_target_p (rtx, rtx);
 static void distribute_notes (rtx, rtx, rtx, rtx, rtx, rtx, rtx);
-static void distribute_links (rtx);
+static void distribute_links (struct insn_link *);
 static void mark_used_regs_combine (rtx);
 static void record_promoted_value (rtx, rtx);
 static int unmentioned_reg_p_1 (rtx *, void *);
@@ -609,7 +635,7 @@  find_single_use (rtx dest, rtx insn, rtx *ploc)
   basic_block bb;
   rtx next;
   rtx *result;
-  rtx link;
+  struct insn_link *link;
 
 #ifdef HAVE_cc0
   if (dest == cc0_rtx)
@@ -635,8 +661,8 @@  find_single_use (rtx dest, rtx insn, rtx *ploc)
        next = NEXT_INSN (next))
     if (INSN_P (next) && dead_or_set_p (next, dest))
       {
-	for (link = LOG_LINKS (next); link; link = XEXP (link, 1))
-	  if (XEXP (link, 0) == insn)
+	FOR_EACH_LOG_LINK (link, next)
+	  if (link->insn == insn)
 	    break;
 
 	if (link)
@@ -985,15 +1011,14 @@  create_log_links (void)
                       || asm_noperands (PATTERN (use_insn)) < 0)
 		    {
 		      /* Don't add duplicate links between instructions.  */
-		      rtx links;
-		      for (links = LOG_LINKS (use_insn); links;
-			   links = XEXP (links, 1))
-		        if (insn == XEXP (links, 0))
+		      struct insn_link *links;
+		      FOR_EACH_LOG_LINK (links, use_insn)
+		        if (insn == links->insn)
 			  break;
 
 		      if (!links)
-			LOG_LINKS (use_insn) =
-			  alloc_INSN_LIST (insn, LOG_LINKS (use_insn));
+			LOG_LINKS (use_insn)
+			  = alloc_insn_link (insn, LOG_LINKS (use_insn));
 		    }
                 }
               next_use[regno] = NULL_RTX;
@@ -1017,18 +1042,6 @@  create_log_links (void)
   free (next_use);
 }
 
-/* Clear LOG_LINKS fields of insns.  */
-
-static void
-clear_log_links (void)
-{
-  rtx insn;
-
-  for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
-    if (INSN_P (insn))
-      free_INSN_LIST_list (&LOG_LINKS (insn));
-}
-
 /* Walk the LOG_LINKS of insn B to see if we find a reference to A.  Return
    true if we found a LOG_LINK that proves that A feeds B.  This only works
    if there are no instructions between A and B which could have a link
@@ -1039,9 +1052,9 @@  clear_log_links (void)
 static bool
 insn_a_feeds_b (rtx a, rtx b)
 {
-  rtx links;
-  for (links = LOG_LINKS (b); links; links = XEXP (links, 1))
-    if (XEXP (links, 0) == a)
+  struct insn_link *links;
+  FOR_EACH_LOG_LINK (links, b)
+    if (links->insn == a)
       return true;
 #ifdef HAVE_cc0
   if (sets_cc0_p (a))
@@ -1062,7 +1075,7 @@  combine_instructions (rtx f, unsigned int nregs)
 #ifdef HAVE_cc0
   rtx prev;
 #endif
-  rtx links, nextlinks;
+  struct insn_link *links, *nextlinks;
   rtx first;
   basic_block last_bb;
 
@@ -1086,8 +1099,9 @@  combine_instructions (rtx f, unsigned int nregs)
 
   /* Allocate array for insn info.  */
   max_uid_known = get_max_uid ();
-  uid_log_links = XCNEWVEC (rtx, max_uid_known + 1);
+  uid_log_links = XCNEWVEC (struct insn_link *, max_uid_known + 1);
   uid_insn_cost = XCNEWVEC (int, max_uid_known + 1);
+  gcc_obstack_init (&insn_link_obstack);
 
   nonzero_bits_mode = mode_for_size (HOST_BITS_PER_WIDE_INT, MODE_INT, 0);
 
@@ -1188,26 +1202,24 @@  combine_instructions (rtx f, unsigned int nregs)
 
 	      /* Try this insn with each insn it links back to.  */
 
-	      for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
-		if ((next = try_combine (insn, XEXP (links, 0), NULL_RTX,
+	      FOR_EACH_LOG_LINK (links, insn)
+		if ((next = try_combine (insn, links->insn, NULL_RTX,
 					 NULL_RTX, &new_direct_jump_p)) != 0)
 		  goto retry;
 
 	      /* Try each sequence of three linked insns ending with this one.  */
 
-	      for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
+	      FOR_EACH_LOG_LINK (links, insn)
 		{
-		  rtx link = XEXP (links, 0);
+		  rtx link = links->insn;
 
 		  /* If the linked insn has been replaced by a note, then there
 		     is no point in pursuing this chain any further.  */
 		  if (NOTE_P (link))
 		    continue;
 
-		  for (nextlinks = LOG_LINKS (link);
-		       nextlinks;
-		       nextlinks = XEXP (nextlinks, 1))
-		    if ((next = try_combine (insn, link, XEXP (nextlinks, 0),
+		  FOR_EACH_LOG_LINK (nextlinks, link)
+		    if ((next = try_combine (insn, link, nextlinks->insn,
 					     NULL_RTX,
 					     &new_direct_jump_p)) != 0)
 		      goto retry;
@@ -1230,9 +1242,8 @@  combine_instructions (rtx f, unsigned int nregs)
 					   &new_direct_jump_p)) != 0)
 		    goto retry;
 
-		  for (nextlinks = LOG_LINKS (prev); nextlinks;
-		       nextlinks = XEXP (nextlinks, 1))
-		    if ((next = try_combine (insn, prev, XEXP (nextlinks, 0),
+		  FOR_EACH_LOG_LINK (nextlinks, prev)
+		    if ((next = try_combine (insn, prev, nextlinks->insn,
 					     NULL_RTX,
 					     &new_direct_jump_p)) != 0)
 		      goto retry;
@@ -1250,9 +1261,8 @@  combine_instructions (rtx f, unsigned int nregs)
 					   &new_direct_jump_p)) != 0)
 		    goto retry;
 
-		  for (nextlinks = LOG_LINKS (prev); nextlinks;
-		       nextlinks = XEXP (nextlinks, 1))
-		    if ((next = try_combine (insn, prev, XEXP (nextlinks, 0),
+		  FOR_EACH_LOG_LINK (nextlinks, prev)
+		    if ((next = try_combine (insn, prev, nextlinks->insn,
 					     NULL_RTX,
 					     &new_direct_jump_p)) != 0)
 		      goto retry;
@@ -1261,14 +1271,14 @@  combine_instructions (rtx f, unsigned int nregs)
 	      /* Finally, see if any of the insns that this insn links to
 		 explicitly references CC0.  If so, try this insn, that insn,
 		 and its predecessor if it sets CC0.  */
-	      for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
-		if (NONJUMP_INSN_P (XEXP (links, 0))
-		    && GET_CODE (PATTERN (XEXP (links, 0))) == SET
-		    && reg_mentioned_p (cc0_rtx, SET_SRC (PATTERN (XEXP (links, 0))))
-		    && (prev = prev_nonnote_insn (XEXP (links, 0))) != 0
+	      FOR_EACH_LOG_LINK (links, insn)
+		if (NONJUMP_INSN_P (links->insn)
+		    && GET_CODE (PATTERN (links->insn)) == SET
+		    && reg_mentioned_p (cc0_rtx, SET_SRC (PATTERN (links->insn)))
+		    && (prev = prev_nonnote_insn (links->insn)) != 0
 		    && NONJUMP_INSN_P (prev)
 		    && sets_cc0_p (PATTERN (prev))
-		    && (next = try_combine (insn, XEXP (links, 0),
+		    && (next = try_combine (insn, links->insn,
 					    prev, NULL_RTX,
 					    &new_direct_jump_p)) != 0)
 		  goto retry;
@@ -1276,73 +1286,70 @@  combine_instructions (rtx f, unsigned int nregs)
 
 	      /* Try combining an insn with two different insns whose results it
 		 uses.  */
-	      for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
-		for (nextlinks = XEXP (links, 1); nextlinks;
-		     nextlinks = XEXP (nextlinks, 1))
-		  if ((next = try_combine (insn, XEXP (links, 0),
-					   XEXP (nextlinks, 0), NULL_RTX,
+	      FOR_EACH_LOG_LINK (links, insn)
+		for (nextlinks = links->next; nextlinks;
+		     nextlinks = nextlinks->next)
+		  if ((next = try_combine (insn, links->insn,
+					   nextlinks->insn, NULL_RTX,
 					   &new_direct_jump_p)) != 0)
 		    goto retry;
 
 	      /* Try four-instruction combinations.  */
-	      for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
+	      FOR_EACH_LOG_LINK (links, insn)
 		{
-		  rtx next1;
-		  rtx link = XEXP (links, 0);
+		  struct insn_link *next1;
+		  rtx link = links->insn;
 
 		  /* If the linked insn has been replaced by a note, then there
 		     is no point in pursuing this chain any further.  */
 		  if (NOTE_P (link))
 		    continue;
 
-		  for (next1 = LOG_LINKS (link); next1; next1 = XEXP (next1, 1))
+		  FOR_EACH_LOG_LINK (next1, link)
 		    {
-		      rtx link1 = XEXP (next1, 0);
+		      rtx link1 = next1->insn;
 		      if (NOTE_P (link1))
 			continue;
 		      /* I0 -> I1 -> I2 -> I3.  */
-		      for (nextlinks = LOG_LINKS (link1); nextlinks;
-			   nextlinks = XEXP (nextlinks, 1))
+		      FOR_EACH_LOG_LINK (nextlinks, link1)
 			if ((next = try_combine (insn, link, link1,
-						 XEXP (nextlinks, 0),
+						 nextlinks->insn,
 						 &new_direct_jump_p)) != 0)
 			  goto retry;
 		      /* I0, I1 -> I2, I2 -> I3.  */
-		      for (nextlinks = XEXP (next1, 1); nextlinks;
-			   nextlinks = XEXP (nextlinks, 1))
+		      for (nextlinks = next1->next; nextlinks;
+			   nextlinks = nextlinks->next)
 			if ((next = try_combine (insn, link, link1,
-						 XEXP (nextlinks, 0),
+						 nextlinks->insn,
 						 &new_direct_jump_p)) != 0)
 			  goto retry;
 		    }
 
-		  for (next1 = XEXP (links, 1); next1; next1 = XEXP (next1, 1))
+		  for (next1 = links->next; next1; next1 = next1->next)
 		    {
-		      rtx link1 = XEXP (next1, 0);
+		      rtx link1 = next1->insn;
 		      if (NOTE_P (link1))
 			continue;
 		      /* I0 -> I2; I1, I2 -> I3.  */
-		      for (nextlinks = LOG_LINKS (link); nextlinks;
-			   nextlinks = XEXP (nextlinks, 1))
+		      FOR_EACH_LOG_LINK (nextlinks, link)
 			if ((next = try_combine (insn, link, link1,
-						 XEXP (nextlinks, 0),
+						 nextlinks->insn,
 						 &new_direct_jump_p)) != 0)
 			  goto retry;
 		      /* I0 -> I1; I1, I2 -> I3.  */
-		      for (nextlinks = LOG_LINKS (link1); nextlinks;
-			   nextlinks = XEXP (nextlinks, 1))
+		      FOR_EACH_LOG_LINK (nextlinks, link1)
 			if ((next = try_combine (insn, link, link1,
-						 XEXP (nextlinks, 0),
+						 nextlinks->insn,
 						 &new_direct_jump_p)) != 0)
 			  goto retry;
 		    }
 		}
 
 	      /* Try this insn with each REG_EQUAL note it links back to.  */
-	      for (links = LOG_LINKS (insn); links; links = XEXP (links, 1))
+	      FOR_EACH_LOG_LINK (links, insn)
 		{
 		  rtx set, note;
-		  rtx temp = XEXP (links, 0);
+		  rtx temp = links->insn;
 		  if ((set = single_set (temp)) != 0
 		      && (note = find_reg_equal_equiv_note (temp)) != 0
 		      && (note = XEXP (note, 0), GET_CODE (note)) != EXPR_LIST
@@ -1380,12 +1387,12 @@  combine_instructions (rtx f, unsigned int nregs)
     }
 
   default_rtl_profile ();
-  clear_log_links ();
   clear_bb_flags ();
   new_direct_jump_p |= purge_all_dead_edges ();
   delete_noop_moves ();
 
   /* Clean up.  */
+  obstack_free (&insn_link_obstack, NULL);
   free (uid_log_links);
   free (uid_insn_cost);
   VEC_free (reg_stat_type, heap, reg_stat);
@@ -1556,13 +1563,11 @@  set_nonzero_bits_and_sign_copies (rtx x, const_rtx set, void *data)
 	  && !REGNO_REG_SET_P (DF_LR_IN (BLOCK_FOR_INSN (insn)),
 			       REGNO (x)))
 	{
-	  rtx link;
+	  struct insn_link *link;
 
-	  for (link = LOG_LINKS (insn); link; link = XEXP (link, 1))
-	    {
-	      if (dead_or_set_p (XEXP (link, 0), x))
-		break;
-	    }
+	  FOR_EACH_LOG_LINK (link, insn)
+	    if (dead_or_set_p (link->insn, x))
+	      break;
 	  if (!link)
 	    {
 	      rsp->nonzero_bits = GET_MODE_MASK (GET_MODE (x));
@@ -2248,7 +2253,7 @@  adjust_for_new_dest (rtx insn)
   /* The new insn will have a destination that was previously the destination
      of an insn just above it.  Call distribute_links to make a LOG_LINK from
      the next use of that destination.  */
-  distribute_links (gen_rtx_INSN_LIST (VOIDmode, insn, NULL_RTX));
+  distribute_links (alloc_insn_link (insn, NULL));
 
   df_insn_rescan (insn);
 }
@@ -2547,7 +2552,7 @@  try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
 
   int maxreg;
   rtx temp;
-  rtx link;
+  struct insn_link *link;
   rtx other_pat = 0;
   rtx new_other_notes;
   int i;
@@ -3929,7 +3934,7 @@  try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
   if (swap_i2i3)
     {
       rtx insn;
-      rtx link;
+      struct insn_link *link;
       rtx ni2dest;
 
       /* I3 now uses what used to be its destination and which is now
@@ -3959,10 +3964,9 @@  try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
 	{
 	  if (INSN_P (insn) && reg_referenced_p (ni2dest, PATTERN (insn)))
 	    {
-	      for (link = LOG_LINKS (insn); link;
-		   link = XEXP (link, 1))
-		if (XEXP (link, 0) == i3)
-		  XEXP (link, 0) = i1;
+	      FOR_EACH_LOG_LINK (link, insn)
+		if (link->insn == i3)
+		  link->insn = i1;
 
 	      break;
 	    }
@@ -3971,7 +3975,7 @@  try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
 
   {
     rtx i3notes, i2notes, i1notes = 0, i0notes = 0;
-    rtx i3links, i2links, i1links = 0, i0links = 0;
+    struct insn_link *i3links, *i2links, *i1links = 0, *i0links = 0;
     rtx midnotes = 0;
     int from_luid;
     /* Compute which registers we expect to eliminate.  newi2pat may be setting
@@ -4074,9 +4078,9 @@  try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
 			  || BB_HEAD (this_basic_block) != temp);
 		 temp = NEXT_INSN (temp))
 	      if (temp != i3 && INSN_P (temp))
-		for (link = LOG_LINKS (temp); link; link = XEXP (link, 1))
-		  if (XEXP (link, 0) == i2)
-		    XEXP (link, 0) = i3;
+		FOR_EACH_LOG_LINK (link, temp)
+		  if (link->insn == i2)
+		    link->insn = i3;
 
 	if (i3notes)
 	  {
@@ -4090,9 +4094,9 @@  try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
 	i2notes = 0;
       }
 
-    LOG_LINKS (i3) = 0;
+    LOG_LINKS (i3) = NULL;
     REG_NOTES (i3) = 0;
-    LOG_LINKS (i2) = 0;
+    LOG_LINKS (i2) = NULL;
     REG_NOTES (i2) = 0;
 
     if (newi2pat)
@@ -4111,7 +4115,7 @@  try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
 
     if (i1)
       {
-	LOG_LINKS (i1) = 0;
+	LOG_LINKS (i1) = NULL;
 	REG_NOTES (i1) = 0;
 	if (MAY_HAVE_DEBUG_INSNS)
 	  propagate_for_debug (i1, i3, i1dest, i1src);
@@ -4120,7 +4124,7 @@  try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
 
     if (i0)
       {
-	LOG_LINKS (i0) = 0;
+	LOG_LINKS (i0) = NULL;
 	REG_NOTES (i0) = 0;
 	if (MAY_HAVE_DEBUG_INSNS)
 	  propagate_for_debug (i0, i3, i0dest, i0src);
@@ -4231,7 +4235,8 @@  try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
 
     if (REG_P (i2dest))
       {
-	rtx link, i2_insn = 0, i2_val = 0, set;
+	struct insn_link *link;
+	rtx i2_insn = 0, i2_val = 0, set;
 
 	/* The insn that used to set this register doesn't exist, and
 	   this life of the register may not exist either.  See if one of
@@ -4240,10 +4245,10 @@  try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
 	   this and I2 set the register to a value that depended on its old
 	   contents, we will get confused.  If this insn is used, thing
 	   will be set correctly in combine_instructions.  */
-	for (link = LOG_LINKS (i3); link; link = XEXP (link, 1))
-	  if ((set = single_set (XEXP (link, 0))) != 0
+	FOR_EACH_LOG_LINK (link, i3)
+	  if ((set = single_set (link->insn)) != 0
 	      && rtx_equal_p (i2dest, SET_DEST (set)))
-	    i2_insn = XEXP (link, 0), i2_val = SET_SRC (set);
+	    i2_insn = link->insn, i2_val = SET_SRC (set);
 
 	record_value_for_reg (i2dest, i2_insn, i2_val);
 
@@ -4257,12 +4262,13 @@  try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
 
     if (i1 && REG_P (i1dest))
       {
-	rtx link, i1_insn = 0, i1_val = 0, set;
+	struct insn_link *link;
+	rtx i1_insn = 0, i1_val = 0, set;
 
-	for (link = LOG_LINKS (i3); link; link = XEXP (link, 1))
-	  if ((set = single_set (XEXP (link, 0))) != 0
+	FOR_EACH_LOG_LINK (link, i3)
+	  if ((set = single_set (link->insn)) != 0
 	      && rtx_equal_p (i1dest, SET_DEST (set)))
-	    i1_insn = XEXP (link, 0), i1_val = SET_SRC (set);
+	    i1_insn = link->insn, i1_val = SET_SRC (set);
 
 	record_value_for_reg (i1dest, i1_insn, i1_val);
 
@@ -4272,12 +4278,13 @@  try_combine (rtx i3, rtx i2, rtx i1, rtx i0, int *new_direct_jump_p)
 
     if (i0 && REG_P (i0dest))
       {
-	rtx link, i0_insn = 0, i0_val = 0, set;
+	struct insn_link *link;
+	rtx i0_insn = 0, i0_val = 0, set;
 
-	for (link = LOG_LINKS (i3); link; link = XEXP (link, 1))
-	  if ((set = single_set (XEXP (link, 0))) != 0
+	FOR_EACH_LOG_LINK (link, i3)
+	  if ((set = single_set (link->insn)) != 0
 	      && rtx_equal_p (i0dest, SET_DEST (set)))
-	    i0_insn = XEXP (link, 0), i0_val = SET_SRC (set);
+	    i0_insn = link->insn, i0_val = SET_SRC (set);
 
 	record_value_for_reg (i0dest, i0_insn, i0_val);
 
@@ -12349,7 +12356,8 @@  record_dead_and_set_regs (rtx insn)
 static void
 record_promoted_value (rtx insn, rtx subreg)
 {
-  rtx links, set;
+  struct insn_link *links;
+  rtx set;
   unsigned int regno = REGNO (SUBREG_REG (subreg));
   enum machine_mode mode = GET_MODE (subreg);
 
@@ -12360,14 +12368,14 @@  record_promoted_value (rtx insn, rtx subreg)
     {
       reg_stat_type *rsp;
 
-      insn = XEXP (links, 0);
+      insn = links->insn;
       set = single_set (insn);
 
       if (! set || !REG_P (SET_DEST (set))
 	  || REGNO (SET_DEST (set)) != regno
 	  || GET_MODE (SET_DEST (set)) != GET_MODE (SUBREG_REG (subreg)))
 	{
-	  links = XEXP (links, 1);
+	  links = links->next;
 	  continue;
 	}
 
@@ -13500,8 +13508,8 @@  distribute_notes (rtx notes, rtx from_insn, rtx i3, rtx i2, rtx elim_i2,
 			  && DF_INSN_LUID (from_insn) > DF_INSN_LUID (i2)
 			  && reg_referenced_p (XEXP (note, 0), PATTERN (i2)))
 			{
-			  rtx links = LOG_LINKS (place);
-			  LOG_LINKS (place) = 0;
+			  struct insn_link *links = LOG_LINKS (place);
+			  LOG_LINKS (place) = NULL;
 			  distribute_links (links);
 			}
 		      break;
@@ -13632,9 +13640,9 @@  distribute_notes (rtx notes, rtx from_insn, rtx i3, rtx i2, rtx elim_i2,
    pointing at I3 when I3's destination is changed.  */
 
 static void
-distribute_links (rtx links)
+distribute_links (struct insn_link *links)
 {
-  rtx link, next_link;
+  struct insn_link *link, *next_link;
 
   for (link = links; link; link = next_link)
     {
@@ -13642,7 +13650,7 @@  distribute_links (rtx links)
       rtx insn;
       rtx set, reg;
 
-      next_link = XEXP (link, 1);
+      next_link = link->next;
 
       /* If the insn that this link points to is a NOTE or isn't a single
 	 set, ignore it.  In the latter case, it isn't clear what we
@@ -13655,8 +13663,8 @@  distribute_links (rtx links)
 	 replace I3, I2, and I1 by I3 and I2.  But in that case the
 	 destination of I2 also remains unchanged.  */
 
-      if (NOTE_P (XEXP (link, 0))
-	  || (set = single_set (XEXP (link, 0))) == 0)
+      if (NOTE_P (link->insn)
+	  || (set = single_set (link->insn)) == 0)
 	continue;
 
       reg = SET_DEST (set);
@@ -13673,7 +13681,7 @@  distribute_links (rtx links)
 	 I3 to I2.  Also note that not much searching is typically done here
 	 since most links don't point very far away.  */
 
-      for (insn = NEXT_INSN (XEXP (link, 0));
+      for (insn = NEXT_INSN (link->insn);
 	   (insn && (this_basic_block->next_bb == EXIT_BLOCK_PTR
 		     || BB_HEAD (this_basic_block->next_bb) != insn));
 	   insn = NEXT_INSN (insn))
@@ -13699,15 +13707,15 @@  distribute_links (rtx links)
 
       if (place)
 	{
-	  rtx link2;
+	  struct insn_link *link2;
 
-	  for (link2 = LOG_LINKS (place); link2; link2 = XEXP (link2, 1))
-	    if (XEXP (link2, 0) == XEXP (link, 0))
+	  FOR_EACH_LOG_LINK (link2, place)
+	    if (link2->insn == link->insn)
 	      break;
 
-	  if (link2 == 0)
+	  if (link2 == NULL)
 	    {
-	      XEXP (link, 1) = LOG_LINKS (place);
+	      link->next = LOG_LINKS (place);
 	      LOG_LINKS (place) = link;
 
 	      /* Set added_links_insn to the earliest insn we added a