This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]

Re: new-regalloc.c patch




On Fri, 2 Feb 2001, Denis Chertykov wrote:

>
> Thanks for applying parts of my previous patch.
It's funny, I had already written the exact same code meeself.
Weird how that works, no?
I looked at yours a little bit after i had finished mine.

>
>
> Fri Feb  2 00:30:43 2001  Denis Chertykov  <denisc@overta.ru>
>
> 	* new-regalloc.c (x_okay_in_direction): Renamed to
> 	`x_okay_all_hard_regs' because we don't use direction.
Fine.

> 	(edge_weight): Weight of edge between v1 and v2 equal to hard
> 	regs count in v2.

This is wrong.
The edge weight is dependent on the number of hard regs in both. The
reason i left out the other cases is because i couldn't figure them out in
my head, and they didn't seem to crop up.

edge_weight (v1,v2) is directly dependent on how much v2 can block
coloring of v1, and v1 can block coloring of v2.

Thus, if v1 needs 2 hard regs, and v2 needs one (or vice versa), it's 2,
because you block coloring twice as much as normal.
If they are both 1 reg, it's 1, because you have a normal blockage.

If you can have unaligned pairs, then if (hard_regs(v1) +
(hard_regs(v2))==4, you need an edge weight of three.

Think of edge weighting as an alternative to having multiple nodes, one
for each hard reg needed by the pseudo.
They would interfere with each other, and everything the pseudo interferes
with.

THe main problem with doing this is that it complicates the algorithms a
*lot* more, because usually those two nodes need two consecutive
registers, so to do it properly (IE without constraining coloring more
than you should) is very hard.

edge weighting is provably equivalent, but much easier to deal with,
algorithmically (it adds <30 lines, IIRC, including the edge_weight
function).

Get it?


 > 	(x_okay_in_direction):  Removed `HARD_REGNO_MODE_OK' from
> 	cycle. Because we can't test each hard regs in currReg for
> 	mode MODE.

I don't get this.
I need to rename currReg in that funciton (speaking of which, i'm about to
rename all the functions/varaibles to conform to standards, since i'm
sufficiently convinced i've implemented the basic algorithm right, and
thus, don't need to check it against the paper anymore).  We are trying to
figure out whether the current hard register is okay to store this mode
in.
currReg is not a pseudo.


> 	(find_reg_given_constraints): `alt_reg' Removed.
> 	Use `x_okay_all_hard_regs'. Use only `prefReg' as return value.
Fine.

>
>
> etIndex: new-regalloc.c
> ===================================================================
> RCS file: /cvs/gcc/egcs/gcc/Attic/new-regalloc.c,v
> retrieving revision 1.1.2.8
> diff -c -3 -p -r1.1.2.8 new-regalloc.c
> *** new-regalloc.c	2001/02/01 17:14:22	1.1.2.8
> --- new-regalloc.c	2001/02/01 21:35:16
> *************** static void freeze_moves PARAMS ((unsign
> *** 192,199 ****
>   static void freeze PARAMS ((void));
>   static float default_heuristic PARAMS ((unsigned int));
>   static void select_spill PARAMS ((void));
> ! static int x_okay_in_direction PARAMS ((HARD_REG_SET, int, int,
> ! 					enum machine_mode));
>
>   static void assign_regs PARAMS ((void));
>   static void rewrite_program PARAMS ((int));
> --- 192,198 ----
>   static void freeze PARAMS ((void));
>   static float default_heuristic PARAMS ((unsigned int));
>   static void select_spill PARAMS ((void));
> ! static int x_okay_all_hard_regs PARAMS ((HARD_REG_SET, int, int));
>
>   static void assign_regs PARAMS ((void));
>   static void rewrite_program PARAMS ((int));
> *************** is_candidate_move (insn, candidates)
> *** 530,559 ****
>   /* Determine the edge weight from reg v1 to reg v2.  */
>   static int
>   edge_weight (v1, v2)
> !      unsigned int v1;
>        unsigned int v2;
>   {
> !   int w1 = 0, w2 = 0;
>
> -   if (! TEST_BIT (precolored, v1))
> -     w1 = CLASS_MAX_NREGS (reg_preferred_class (v1), PSEUDO_REGNO_MODE (v1));
>     if (! TEST_BIT (precolored, v2))
>       w2 = CLASS_MAX_NREGS (reg_preferred_class (v2), PSEUDO_REGNO_MODE (v2));
>
> !   switch (w1 + w2)
> !     {
> !     case 0:
> !     case 1:
> !     case 2:
> !       return 1;
> !     case 3:
> !       return 2;
> !     case 4:
> !       /* FIXME: Test for unaligned pairs.  */
> !       return 2;
> !     default:
> !       abort();
> !     }
>   }
>
>   /* Add an interference edge from reg v1 to reg v2 */
> --- 529,543 ----
>   /* Determine the edge weight from reg v1 to reg v2.  */
>   static int
>   edge_weight (v1, v2)
> !      unsigned int v1 ATTRIBUTE_UNUSED;
>        unsigned int v2;
>   {
> !   int w2 = 0;
>
>     if (! TEST_BIT (precolored, v2))
>       w2 = CLASS_MAX_NREGS (reg_preferred_class (v2), PSEUDO_REGNO_MODE (v2));
>
> !   return w2;
>   }
>
>   /* Add an interference edge from reg v1 to reg v2 */
> *************** select_spill()
> *** 1227,1248 ****
>     } while(0)
>
>   static int
> ! x_okay_in_direction(okay, currReg, numRegs, mode)
>        HARD_REG_SET okay;
>        int currReg;
>        int numRegs;
> -      enum machine_mode mode;
>   {
>     int k;
>
>     for (k = 1; k < numRegs; k++)
> !     {
> !       int regno = currReg + k;
> !       if (regno < 0
> ! 	  || ! TEST_HARD_REG_BIT (okay, regno)
> ! 	  || ! HARD_REGNO_MODE_OK (regno, mode))
> ! 	return 0;
> !     }
>     return 1;
>   }
>
> --- 1211,1227 ----
>     } while(0)
>
>   static int
> ! x_okay_all_hard_regs (okay, currReg, numRegs)
>        HARD_REG_SET okay;
>        int currReg;
>        int numRegs;
>   {
>     int k;
>
>     for (k = 1; k < numRegs; k++)
> !     if (! TEST_HARD_REG_BIT (okay, currReg + k))
> !       return 0;
> !
>     return 1;
>   }
>
> *************** find_reg_given_constraints (okay, currRe
> *** 1253,1261 ****
>   {
>     int i;
>     int prefReg = -1;
> -   int alt_reg = -1;
>     int prefRegOrder = INT_MAX;
> !   unsigned int numRegs = 0;
>     enum machine_mode reg_mode = PSEUDO_REGNO_MODE (currReg);
>
>     /* Watch as we attempt to handle the preference, and the number of hard
> --- 1232,1239 ----
>   {
>     int i;
>     int prefReg = -1;
>     int prefRegOrder = INT_MAX;
> !   unsigned int numRegs;
>     enum machine_mode reg_mode = PSEUDO_REGNO_MODE (currReg);
>
>     /* Watch as we attempt to handle the preference, and the number of hard
> *************** find_reg_given_constraints (okay, currRe
> *** 1266,1272 ****
>        FIXME: Just use a simple scoring, to get rid of this ugliness? Or
>        maybe just ask the arch dependent code to tell us what it prefers?  */
>
> -   numRegs = 1;
>     for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
>       {
>         if (! TEST_HARD_REG_BIT (okay, i))
> --- 1244,1249 ----
> *************** find_reg_given_constraints (okay, currRe
> *** 1277,1284 ****
>
>         /* The number of hard regs required depends on the hard reg tested.  */
>         numRegs = HARD_REGNO_NREGS (i, reg_mode);
> !       if (numRegs > 1
> ! 	  && ! x_okay_in_direction (okay, i, numRegs, reg_mode))
>   	continue;
>
>         if (inv_reg_alloc_order[i] < prefRegOrder)
> --- 1254,1260 ----
>
>         /* The number of hard regs required depends on the hard reg tested.  */
>         numRegs = HARD_REGNO_NREGS (i, reg_mode);
> !       if (numRegs > 1 && ! x_okay_all_hard_regs (okay, i, numRegs))
>   	continue;
>
>         if (inv_reg_alloc_order[i] < prefRegOrder)
> *************** find_reg_given_constraints (okay, currRe
> *** 1287,1301 ****
>   	  prefRegOrder = inv_reg_alloc_order[i];
>   	}
>       }
> -   if (prefReg == -1)
> -     return -1;
> -
> -   /* Get right value for the preferred register.  */
> -   numRegs = HARD_REGNO_NREGS (prefReg, reg_mode);
> -   alt_reg = prefReg + (numRegs - 1);
> -
> -   if (HARD_REGNO_MODE_OK (alt_reg, reg_mode))
> -     prefReg = MIN (prefReg, alt_reg);
>
>     return prefReg;
>   }
> --- 1263,1268 ----
>
>
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]