Path: utzoo!utgpu!water!watmath!clyde!att!osu-cis!tut.cis.ohio-state.edu!bloom-beacon!bu-cs!purdue!decwrl!sun!imagen!atari!portal!cup.portal.com!bcase
From: bcase@cup.portal.com
Newsgroups: comp.arch
Subject: "interprocedural analysis useless for code optmization"
Message-ID: <9988@cup.portal.com>
Date: 12 Oct 88 19:01:27 GMT
Organization: The Portal System (TM)
Lines: 26
XPortal-User-Id: 1.1001.5156

There is a paper by S. Richardson and M. Ganapathi at Stanford that might be
of interest to those engaging in discussions that consider alias analysis a
problem (e.g., the machine-independent-intermediate language discussion).

"Interprocedural Analysis Useless for Code Optimization," Richardson &
Ganapathi, Stanford Tech. Report No.  CSL-TR-87-342, Nov. 1987.

At least for Pascal programs, the conclusion that not only is interprocedural
analysis pretty much useless for real programs, but "ALIAS information, which
is the most difficult to compute algorithmically, turns out to be the least
useful.  Our data show that only about 1% of the loads and stores in a given
program are susceptible to being potentially aliased to a var parameter, and
that the speedup gained by making such relationships explicit is almost nil."

Perhaps the case is different for C programs, but the old assumption (at
leat my assumption) that interprocedural optimization would be the next
important level of optimization technology, appears to be false.  Sigh.  [As
side note, I showed this paper to John Banning who, in '79, wrote a thesis
containing the "classic" algorithm for interproc. analysis.  He said "Damn,
if I'd known, I would have done something else." :-)]

The paper shows the speedups for 27 programs (some are small benchmarks);
the best that could be managed was a respectable 12%, but only *4* of the
programs showed any improvement; the other three speedups were 1%, 4%, and
7%.  Pure alias analysis contributed nothing to the speedups!  Wow.  Again,
maybe C programs provide more opportunities.  Any data out there?