Re: Reload patch to improve 386 code

[David S. Miller <davem@jenolan.rutgers.edu>]

   Date: Mon, 18 Aug 1997 11:17:38 -0400 (EDT)
   From: meissner@cygnus.com

   I think it is an horrible kludge that reload is run as a pass after
   global-alloc, and that it forces reload registers not to be used
   for any other purpose (which is murder on the x86 with each
   register being special purpose in some way).

Before this leaves my head, I wanted to point something out which
you've reminded me of.  When the scheduler (this applies to both the
original and Haifa versions equally) becomes aggressive, it produces a
large number of reloads in certain situations.  Reloads which would
not have happened if scheduling did not take place.  This happens
especially if register pressure is high already.  I noticed this
particularly on RISC platforms, seems in this case the more registers
available the worse things became when the register usage was
saturated.

Another thing I saw gcc do for a register constrained function was the
following.  Consider a function which references a lot of global data
structures, which it iterates over as a 3 level indirected table.  It
also references 2 or 3 global pieces of data in a few distinct places
within the iteration (the specific example is specifically the
function mm/memory.c:copy_page_range() on sparc64 in the Linux kernel)
A rough outline is:

inline copy_one_pte() {
	if(pte_none(pte))
		return;
	if(!pte_present(pte)) {
		duplicate_swap_information();
		return;
	}
	copy_pte_info_and_maybe_cow();
}

inline copy_pte_range() {
	for_all_ptes_in_this_pmd()
		copy_one_pte();
}

inline copy_pmd_range() {
	for_all_pmds_in_this_pgd()
		copy_pte_range();
}

copy_page_range() {
	for_all_pgds_in_this_range()
		copy_pmd_range();
}

Now, I have two global physical addresses I use for "null" page
tables, which is what newly allocated page tables point to before they
are set to point to anything specific.  There is heavy inlining done
here and on sparc64 it can end up allocating 300 or 400 bytes of stack
space.  Anyways, back to my main point, the two physical addresses for
the null page table pages live in two global variables
"null_pte_table" and "null_pmd_table".  The progression in the
produced code wrt. these two variables is:

copy_page_range:

	sethi	%hi(null_pte_table), %r
	or	%r, %lo(null_pte_table), %r
	stx	%r, [%sp + slot1]
	sethi	%hi(null_pmd_table), %r
	or	%r, %lo(null_pmd_table), %r
	stx	%r, [%sp + slot2]

...

main_loop:
	...
	/* we need to use null_pmd_table's value here */
	ldx	[%sp + slot1], %r
	ldx	[%r], %r2
	use it
	stx	%r2, [%sp + slot3]
	...
	/* we need to use null_pte_table's value here */
	ldx	[%sp + slot2], %r
	ldx	[%r], %r2
	use it
	stx	%r2, [%sp + %slot4]	
	...
	/* need again to use null_pmd_table's value */
	ldx	[%sp + slot3], %r
	use it
	...
	/* need again to use null_pte_table's value */
	ldx	[%sp + slot4], %r
	use it
	...
	b	main_loop

Anyways you get the picture, I see often these "gradual" reloads,
where final values are computed partially, given a stack slot for
reloading purposes, and then loaded back and computed further, then
given yet another stack slot.  On RISC systems this can account for a
significant portion of the stack slots taken up for a given function.

   Now, given it is a rather critical piece of the compiler, it may
   take months if not years to get it better than it currently is.

Well, perhaps it would be prudent to have people start now in the
background to get this work going?

Later,
David "Sparc" Miller
davem@caip.rutgers.edu