[new-allocator] ra-build changes & is_death

[new-allocator] ra-build changes & is_death

[Denis Chertykov]

This patch is not commited. I will wait approval or reject.
Main idea of changes in ra-build.c is fill regclass, add_hardregs, ...
fields of each web only after building all webs. This is a small step to
web_class side. web_class must be called before call to select_regclass.

ra-rewrite.c: symmetrically handling of defs and deaths.

I have successfully bootstrapped C with these changes.

If you approve patch then I will try to bootstrap c,c++,java,f77,objc
and commit patch only after success.

This patch required for integration pre-reload/web_class and
allocator.

Next patches will substitute all usage of max_normal_pseudo and
orig_max_uid to operation with bitmaps:
orig_max_uid -> bitmap_bit_p (emitted_by_spill, ...)
max_normal_pseudo -> bitmap_bit_p (spill_slot_regs, ...)
These needed for separate insns and pseudos generated by spill/rewrite
and generated by pre-reload/eliminate.

2002-07-19  Denis Chertykov  <denisc@overta.ru>

	* ra-build.c (remember_web_was_spilled): Removed.
	(init_one_web_common): Move initialization of regclass, add_hardregs,
	num_conflicts fields of web to select_regclass.
	(select_regclass): New function.
	(detect_spill_temps): Remove call to remember_web_was_spilled.
	(make_webs): Call select_regclass.

	* ra-rewrite.c (detect_deaths_in_bb, rewrite_program2,
	reloads_to_loads): Change calculation of is_death.


Index: ra-build.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ra-build.c,v
retrieving revision 1.1.2.3
diff -c -3 -p -r1.1.2.3 ra-build.c
*** ra-build.c	16 Jul 2002 19:52:44 -0000	1.1.2.3
--- ra-build.c	19 Jul 2002 13:15:06 -0000
*************** static void parts_to_webs PARAMS ((struc
*** 102,108 ****
  static void reset_conflicts PARAMS ((void));
  static void check_conflict_numbers PARAMS ((void));
  static void conflicts_between_webs PARAMS ((struct df *));
- static void remember_web_was_spilled PARAMS ((struct web *));
  static void detect_spill_temps PARAMS ((void));
  static int contains_pseudo PARAMS ((rtx));
  static int want_to_remat PARAMS ((rtx x));
--- 102,107 ----
*************** static void livethrough_conflicts_bb PAR
*** 117,122 ****
--- 116,122 ----
  static void init_bb_info PARAMS ((void));
  static void free_bb_info PARAMS ((void));
  static void build_web_parts_and_conflicts PARAMS ((struct df *));
+ static void select_regclass PARAMS ((void));
  
  
  /* A sbitmap of DF_REF_IDs of uses, which are live over an abnormal
*************** init_one_web_common (web, reg)
*** 1251,1273 ****
        web->dlink = (struct dlist *) ra_calloc (sizeof (struct dlist));
        DLIST_WEB (web->dlink) = web;
      }
-   /* XXX
-      the former (superunion) doesn't constrain the graph enough. E.g.
-      on x86 QImode _requires_ QI_REGS, but as alternate class usually
-      GENERAL_REGS is given.  So the graph is not constrained enough,
-      thinking it has more freedom then it really has, which leads
-      to repeated spill tryings.  OTOH the latter (only using preferred
-      class) is too constrained, as normally (e.g. with all SImode
-      pseudos), they can be allocated also in the alternate class.
-      What we really want, are the _exact_ hard regs allowed, not
-      just a class.  Later.  */
-   /*web->regclass = reg_class_superunion
- 		    [reg_preferred_class (web->regno)]
- 		    [reg_alternate_class (web->regno)];*/
-   /*web->regclass = reg_preferred_class (web->regno);*/
-   web->regclass = reg_class_subunion
-     [reg_preferred_class (web->regno)] [reg_alternate_class (web->regno)];
-   web->regclass = reg_preferred_class (web->regno);
    if (web->regno < FIRST_PSEUDO_REGISTER)
      {
        web->color = web->regno;
--- 1251,1256 ----
*************** init_one_web_common (web, reg)
*** 1280,1317 ****
      }
    else
      {
-       HARD_REG_SET alternate;
        web->color = -1;
        put_web (web, INITIAL);
!       /* add_hardregs is wrong in multi-length classes, e.g.
! 	 using a DFmode pseudo on x86 can result in class FLOAT_INT_REGS,
! 	 where, if it finally is allocated to GENERAL_REGS it needs two,
! 	 if allocated to FLOAT_REGS only one hardreg.  XXX */
!       web->add_hardregs =
! 	CLASS_MAX_NREGS (web->regclass, PSEUDO_REGNO_MODE (web->regno)) - 1;
!       web->num_conflicts = 0 * web->add_hardregs;
!       COPY_HARD_REG_SET (web->usable_regs,
! 			reg_class_contents[reg_preferred_class (web->regno)]);
!       COPY_HARD_REG_SET (alternate,
! 			reg_class_contents[reg_alternate_class (web->regno)]);
!       IOR_HARD_REG_SET (web->usable_regs, alternate);
!       /*IOR_HARD_REG_SET (web->usable_regs,
! 			reg_class_contents[reg_alternate_class
! 			(web->regno)]);*/
!       AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors);
!       prune_hardregs_for_mode (&web->usable_regs,
! 			       PSEUDO_REGNO_MODE (web->regno));
! #ifdef CLASS_CANNOT_CHANGE_MODE
!       if (web->mode_changed)
!         AND_COMPL_HARD_REG_SET (web->usable_regs, reg_class_contents[
! 			          (int) CLASS_CANNOT_CHANGE_MODE]);
! #endif
!       web->num_freedom = hard_regs_count (web->usable_regs);
!       web->num_freedom -= web->add_hardregs;
!       if (!web->num_freedom)
! 	abort();
      }
-   COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs);
  }
  
  /* Initializes WEBs members from REG or zero them.  */
--- 1263,1274 ----
      }
    else
      {
        web->color = -1;
        put_web (web, INITIAL);
!       web->num_conflicts = 0;
!       web->add_hardregs = 0;
!       web->num_freedom = 0;
      }
  }
  
  /* Initializes WEBs members from REG or zero them.  */
*************** conflicts_between_webs (df)
*** 2311,2397 ****
  #endif
  }
  
- /* Remember that a web was spilled, and change some characteristics
-    accordingly.  */
- 
- static void
- remember_web_was_spilled (web)
-      struct web *web;
- {
-   int i;
-   unsigned int found_size = 0;
-   int adjust;
-   web->spill_temp = 1;
- 
-   /* From now on don't use reg_pref/alt_class (regno) anymore for
-      this web, but instead  usable_regs.  We can't use spill_temp for
-      this, as it might get reset later, when we are coalesced to a
-      non-spill-temp.  In that case we still want to use usable_regs.  */
-   web->use_my_regs = 1;
- 
-   /* We don't constrain spill temporaries in any way for now.
-      It's wrong sometimes to have the same constraints or
-      preferences as the original pseudo, esp. if they were very narrow.
-      (E.g. there once was a reg wanting class AREG (only one register)
-      without alternative class.  As long, as also the spill-temps for
-      this pseudo had the same constraints it was spilled over and over.
-      Ideally we want some constraints also on spill-temps: Because they are
-      not only loaded/stored, but also worked with, any constraints from insn
-      alternatives needs applying.  Currently this is dealt with by reload, as
-      many other things, but at some time we want to integrate that
-      functionality into the allocator.  */
-   if (web->regno >= max_normal_pseudo)
-     {
-       COPY_HARD_REG_SET (web->usable_regs,
- 			reg_class_contents[reg_preferred_class (web->regno)]);
-       IOR_HARD_REG_SET (web->usable_regs,
- 			reg_class_contents[reg_alternate_class (web->regno)]);
-     }
-   else
-     COPY_HARD_REG_SET (web->usable_regs, reg_class_contents[(int) ALL_REGS]);
-   AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors);
-   prune_hardregs_for_mode (&web->usable_regs, PSEUDO_REGNO_MODE (web->regno));
- #ifdef CLASS_CANNOT_CHANGE_MODE
-   if (web->mode_changed)
-     AND_COMPL_HARD_REG_SET (web->usable_regs, reg_class_contents[
- 			      (int) CLASS_CANNOT_CHANGE_MODE]);
- #endif
-   web->num_freedom = hard_regs_count (web->usable_regs);
-   if (!web->num_freedom)
-     abort();
-   COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs);
-   /* Now look for a class, which is subset of our constraints, to
-      setup add_hardregs, and regclass for debug output.  */
-   web->regclass = NO_REGS;
-   for (i = (int) ALL_REGS - 1; i > 0; i--)
-     {
-       unsigned int size;
-       HARD_REG_SET test;
-       COPY_HARD_REG_SET (test, reg_class_contents[i]);
-       AND_COMPL_HARD_REG_SET (test, never_use_colors);
-       GO_IF_HARD_REG_SUBSET (test, web->usable_regs, found);
-       continue;
-     found:
-       /* Measure the actual number of bits which really are overlapping
- 	 the target regset, not just the reg_class_size.  */
-       size = hard_regs_count (test);
-       if (found_size < size)
- 	{
-           web->regclass = (enum reg_class) i;
- 	  found_size = size;
- 	}
-     }
- 
-   adjust = 0 * web->add_hardregs;
-   web->add_hardregs =
-     CLASS_MAX_NREGS (web->regclass, PSEUDO_REGNO_MODE (web->regno)) - 1;
-   web->num_freedom -= web->add_hardregs;
-   if (!web->num_freedom)
-     abort();
-   adjust -= 0 * web->add_hardregs;
-   web->num_conflicts -= adjust;
- }
- 
  /* Look at each web, if it is used as spill web.  Or better said,
     if it will be spillable in this pass.  */
  
--- 2268,2273 ----
*************** detect_spill_temps ()
*** 2450,2456 ****
  	      int num_deaths = web->span_deaths;
  	      /* Mark webs involving at least one spill insn as
  		 spill temps.  */
! 	      remember_web_was_spilled (web);
  	      /* Search for insns which define and use the web in question
  		 at the same time, i.e. look for rmw insns.  If these insns
  		 are also deaths of other webs they might have been counted
--- 2326,2333 ----
  	      int num_deaths = web->span_deaths;
  	      /* Mark webs involving at least one spill insn as
  		 spill temps.  */
! 	      web->spill_temp = 1;
! 	      web->use_my_regs = 1;
  	      /* Search for insns which define and use the web in question
  		 at the same time, i.e. look for rmw insns.  If these insns
  		 are also deaths of other webs they might have been counted
*************** detect_webs_set_in_cond_jump ()
*** 2744,2749 ****
--- 2621,2681 ----
        }
  }
  
+ /* Select preferred regclass and fill the following web fields:
+      regclass,
+      add_hardregs,
+      num_freedom,
+      num_conflicts.  */
+ static void
+ select_regclass ()
+ {
+   unsigned int i;
+ 
+   for (i = 0; i < num_webs; ++i)
+     {
+       struct web *web = id2web[i];
+       struct web *w;
+ 
+       if (web->regno < FIRST_PSEUDO_REGISTER)
+ 	continue;
+ 
+       web->regclass = reg_preferred_class (web->regno);
+       if (web->regclass == NO_REGS)
+ 	abort ();
+       COPY_HARD_REG_SET (web->usable_regs, reg_class_contents[web->regclass]);
+       IOR_HARD_REG_SET (web->usable_regs,
+ 			reg_class_contents [reg_alternate_class (web->regno)]);
+       /* add_hardregs is wrong in multi-length classes, e.g.
+ 	 using a DFmode pseudo on x86 can result in class FLOAT_INT_REGS,
+ 	 where, if it finally is allocated to GENERAL_REGS it needs two,
+ 	 if allocated to FLOAT_REGS only one hardreg.  XXX */
+       web->add_hardregs =
+ 	CLASS_MAX_NREGS (web->regclass, PSEUDO_REGNO_MODE (web->regno)) - 1;
+       web->num_conflicts = 0 * web->add_hardregs;
+       AND_COMPL_HARD_REG_SET (web->usable_regs, never_use_colors);
+       prune_hardregs_for_mode (&web->usable_regs,
+ 			       PSEUDO_REGNO_MODE (web->regno));
+ #ifdef CLASS_CANNOT_CHANGE_MODE
+       if (web->mode_changed)
+         AND_COMPL_HARD_REG_SET (web->usable_regs, reg_class_contents
+ 				[(int) CLASS_CANNOT_CHANGE_MODE]);
+ #endif
+       web->num_freedom = hard_regs_count (web->usable_regs);
+       if (!web->num_freedom)
+ 	abort();
+ 
+       COPY_HARD_REG_SET (web->orig_usable_regs, web->usable_regs);
+ 
+       /* Adjust num_conflicts for subregs.  */
+       for (w = web->subreg_next; w && w != web; w = w->subreg_next)
+ 	{
+ 	  w->add_hardregs = CLASS_MAX_NREGS (web->regclass,
+ 					     GET_MODE (w->orig_x)) - 1;
+ 	  w->num_conflicts += 0 * w->add_hardregs;
+ 	}
+     }
+ }  
+ 
  /* Second top-level function of this file.
     Converts the connected web parts to full webs.  This means, it allocates
     all webs, and initializes all fields, including detecting spill
*************** make_webs (df)
*** 2760,2765 ****
--- 2692,2701 ----
    /* Now detect spill temporaries to initialize their usable_regs set.  */
    detect_spill_temps ();
    detect_webs_set_in_cond_jump ();
+   /* Select preferred regclass for each web and fill related fields of web
+      structure.  */
+   select_regclass ();
+ 
    /* And finally relate them to each other, meaning to record all possible
       conflicts between webs (see the comment there).  */
    conflicts_between_webs (df);
Index: ra-rewrite.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ra-rewrite.c,v
retrieving revision 1.1.2.3
diff -c -3 -p -r1.1.2.3 ra-rewrite.c
*** ra-rewrite.c	16 Jul 2002 19:52:44 -0000	1.1.2.3
--- ra-rewrite.c	19 Jul 2002 13:15:23 -0000
*************** detect_deaths_in_bb (bb, live, new_death
*** 1137,1144 ****
  	{
  	  struct web *web = use2web[DF_REF_ID (info.uses[n])];
  	  struct web *supweb = find_web_for_subweb (web);
! 	  int is_death = !TEST_BIT (live, supweb->id);
! 	  is_death &= !TEST_BIT (live, web->id);
  	  if (is_death)
  	    {
  	      bitmap_set_bit (new_deaths, INSN_UID (insn));
--- 1137,1143 ----
  	{
  	  struct web *web = use2web[DF_REF_ID (info.uses[n])];
  	  struct web *supweb = find_web_for_subweb (web);
! 	  int is_death = !TEST_BIT (live, web->id);
  	  if (is_death)
  	    {
  	      bitmap_set_bit (new_deaths, INSN_UID (insn));
*************** reloads_to_loads (ri, refs, num_refs, re
*** 1187,1194 ****
        /* Note, that if web (and supweb) are DEFs, we already cleared
  	 the corresponding bits in live.  I.e. is_death becomes true, which
  	 is what we want.  */
!       is_death = !TEST_BIT (ri->live, supweb->id);
!       is_death &= !TEST_BIT (ri->live, web->id);
        if (is_death)
  	{
  	  int old_num_r = num_reloads;
--- 1186,1192 ----
        /* Note, that if web (and supweb) are DEFs, we already cleared
  	 the corresponding bits in live.  I.e. is_death becomes true, which
  	 is what we want.  */
!       is_death = !TEST_BIT (ri->live, web->id);
        if (is_death)
  	{
  	  int old_num_r = num_reloads;
*************** rewrite_program2 (new_deaths)
*** 1466,1473 ****
  		if (supweb->type == PRECOLORED
  		    && TEST_HARD_REG_BIT (never_use_colors, supweb->color))
  		  continue;
! 		is_death = !TEST_BIT (ri.live, supweb->id);
! 		is_death &= !TEST_BIT (ri.live, web->id);
  		if (is_death)
  		  {
  		    ri.need_load = 1;
--- 1464,1470 ----
  		if (supweb->type == PRECOLORED
  		    && TEST_HARD_REG_BIT (never_use_colors, supweb->color))
  		  continue;
! 		is_death = !TEST_BIT (ri.live, web->id);
  		if (is_death)
  		  {
  		    ri.need_load = 1;

Re: [new-allocator] ra-build changes & is_death

[Michael Matz]

Hi,

On Fri, 19 Jul 2002, Denis Chertykov wrote:

> Main idea of changes in ra-build.c is fill regclass, add_hardregs, ...
> fields of each web only after building all webs. This is a small step to
> web_class side. web_class must be called before call to select_regclass.

This probably is Ok, although it temporarily introduces the problem of
possibly too narrow classes for spill temporaries.

> ra-rewrite.c: symmetrically handling of defs and deaths.

Ahh yes, sorry I didn't come back to you on that.  We somewhen need
another representation for which parts are live exactly in
rewrite_program2().  Until then your patch should help, at least the one
reloads_to_loads().  About the other I had not yet time to think about.  I
introduced the additional checks (which you remove in your patch) for a
reason: The problems begin, when there's a free mix of uses/defs of whole
pseudos and subregs of it in different modes, such as:

 p1:DI <= ...
 ... <= p1+0:SI
 p1+0:SI <= ...
   (1)
 p1+1:QI <= ...
   (2)
 ... <= p1+0:SI

The problem is, that only the indices are in the live bitmap, and the
indices of p1:SI, p1+1:QI are different, but they overlap.  That is,
basically it's difficult to represent what parts of p1 are live at the
point (1) marked above (it's all of p1 besides the second lowest byte).
Up to now I solved this by simply marking the whole web live, additionally
to also the subwebs.  In the above scenario, as p1+1:QI wasn't used
afterwards (in this exact form), only p1:DI and p1+0:SI are marked live.
So the define of p1+1:QI doesn't change the live bitset.  But it changes
the available colors.  I need to rethink all this.  Until then your change
is also Ok.

> If you approve patch then I will try to bootstrap c,c++,java,f77,objc
> and commit patch only after success.

I just tried to do this, and it fails when compiling libf2c with:
libf2c/libI77/wrtfmt.c: In function `wrt_IM':
gcc/libf2c/libI77/wrtfmt.c:217: internal compiler error: Internal compiler
error in reset_lists, at ra-colorize.c:259

This should be analyzed first, but I have to go to a party right now ;)


Ciao,
Michael.