This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug tree-optimization/69270] New: DOM should exploit range information to create more equivalences
- From: "law at redhat dot com" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: Thu, 14 Jan 2016 07:28:00 +0000
- Subject: [Bug tree-optimization/69270] New: DOM should exploit range information to create more equivalences
- Auto-submitted: auto-generated
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69270
Bug ID: 69270
Summary: DOM should exploit range information to create more
equivalences
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: law at redhat dot com
Target Milestone: ---
Given a conditional like
if (a != 0)
TRUE-ARM
else
FALSE-ARM
DOM will exploit the knowledge that A must have the value 0 in the FALSE arm of
the conditional. DOM can not be as aggressive in the TRUE arm because A could
have any value other than zero.
However, if we have range information for A which indicates its range is
[0..1], then DOM can exploit the fact that A must have the value 1 in the TRUE
arm of the conditional. DOM knows how to do this for booleans where the range
is implicit in the type, but isn't exploiting VRP information to do this on
larger integral types.
Opportunities show up in the adpcm benchmark when compiled with -fsplit-paths
as well as within GCC itself. Here's the greatly simplified adpcm code:
extern int *stepsizeTable;
void
adpcm_coder (signed char *outdata, int len)
{
signed char *outp;
int delta;
int outputbuffer;
int bufferstep = 0;
outp = (signed char *) outdata;
int step = 0;
int index = 0;
int diff = 0;
for (; len > 0; len--)
{
delta = 0;
if (diff >= step)
delta = 4;
step = stepsizeTable[index];
if (bufferstep)
outputbuffer = (delta << 4) & 0xf0;
else
*outp++ = (delta & 0x0f) | outputbuffer;
bufferstep = !bufferstep;
}
}
Path splitting essentially turns the loop into:
for (; len > 0; len--)
{
delta = 0;
if (diff >= step)
delta = 4;
step = stepsizeTable[index];
if (bufferstep)
{
outputbuffer = (delta << 4) & 0xf0;
bufferstep = !bufferstep;
}
else
{
*outp++ = (delta & 0x0f) | outputbuffer;
bufferstep = !bufferstep;
}
}
VRP can determine that the bufferstep has the range [0..1] so we can propagate
those constants into each arm of the conditional, causing the !bufferstep
expression to have a constant value. That's a win.
The astute reader will realize that we've got a flip-flop variable and that
unrolling the loop 1X would allow dramatic simplifications. In this example
there wouldn't be any code bloat, but in the real adpcm code the bloat would
likely be significant.