Local Dead Store Elimination

January 18, 1999

Christian Bruel and Jeff Law have contributed a significant improvement to the local dead store elimination performed by GCC.

Previously GCC would not detect a pair of memory stores (dead store candidates) as dead if they were separated by any memory reference which did not use the exact same address as the dead store candidates.

GCC now tracks loads and stores more accurately within each basic block. GCC also uses alias analysis to detect when the dead store candidates can not reference the same memory locations as the memory references between the dead store candidates. This allows more dead stores to be eliminated.

To see the utility of this new optimization, consider the following function:

int t1;
int t2;
void dead_stores ()
{
  t1 += 1 ; t2 += 1;
  t1 += 2 ; t2 += 2;
  t1 += 3 ; t2 += 3; 
}

Without the new optimization, the code generated for this function on a sparc looked like:

	sethi %hi(t1),%o3
	ld [%o3+%lo(t1)],%g2
	sethi %hi(t2),%o4
	ld [%o4+%lo(t2)],%g3
	add %g2,1,%o0
	st %o0,[%o3+%lo(t1)]
	add %g3,1,%o1
	st %o1,[%o4+%lo(t2)]
	add %g2,3,%o2
	add %g3,3,%o0
	st %o2,[%o3+%lo(t1)]
	st %o0,[%o4+%lo(t2)]
	add %g2,6,%g2
	add %g3,6,%g3
	st %g2,[%o3+%lo(t1)]
	retl
	st %g3,[%o4+%lo(t2)]

With the optimization, the code generated for the function looks like:

	sethi %hi(t1),%o0
	sethi %hi(t2),%o1
	ld [%o0+%lo(t1)],%g2
	ld [%o1+%lo(t2)],%g3
	add %g2,6,%g2
	add %g3,6,%g3
	st %g2,[%o0+%lo(t1)]
	retl
	st %g3,[%o1+%lo(t2)]

Note that 4 store operations have been eliminated. Elimination of those store operations also allows 4 add operations to be eliminated.

Please send FSF & GNU inquiries & questions to gnu@gnu.org. There are also other ways to contact the FSF.

These pages are maintained by the GCC team.

For questions related to the use of GCC, please consult these web pages and the GCC manuals. If that fails, the gcc-help@gcc.gnu.org mailing list might help.
Please send comments on these web pages and the development of GCC to our developer mailing list at gcc@gnu.org or gcc@gcc.gnu.org. All of our lists have public archives.

Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved.

Last modified 2006-06-21