public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug optimization/13876] loop not fully optimized
2004-01-27 6:06 [Bug optimization/13876] New: loop not fully optimized pinskia at gcc dot gnu dot org
@ 2004-01-27 6:06 ` pinskia at gcc dot gnu dot org
2004-01-27 6:07 ` pinskia at gcc dot gnu dot org
` (4 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-01-27 6:06 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-01-27 06:06 -------
This should be able to be done on the tree-ssa.
--
What |Removed |Added
----------------------------------------------------------------------------
Known to fail| |2.97 3.0 3.0.1 3.0.2 3.0.3
| |3.0.4 3.1 3.1.1 3.1.2 3.2
| |3.2.1 3.2.2 3.2.3 3.3 3.3.1
| |3.3.2 3.3.3 3.4.0 3.5.0
Target Milestone|--- |tree-ssa
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13876
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug optimization/13876] New: loop not fully optimized
@ 2004-01-27 6:06 pinskia at gcc dot gnu dot org
2004-01-27 6:06 ` [Bug optimization/13876] " pinskia at gcc dot gnu dot org
` (5 more replies)
0 siblings, 6 replies; 7+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-01-27 6:06 UTC (permalink / raw)
To: gcc-bugs
Basically these two functions should produce the same code, the check for NotFound is not needed
at all.
void g(); void h(); void o();
void t(int l, int *y)
{
int i;
int NotFound;
o();
for(i = 0, NotFound = 1;NotFound && i<l;i++)
{ if (y[i]) { NotFound = 0; g(); } }
h();
}
void t1(int l, int *y)
{
int i;
int NotFound;
o();
for(i = 0, NotFound = 1;NotFound && i<l;i++)
{ if (y[i]) { NotFound = 0; g(); break; } }
h();
}
--
Summary: loop not fully optimized
Product: gcc
Version: tree-ssa
Status: UNCONFIRMED
Keywords: pessimizes-code
Severity: enhancement
Priority: P2
Component: optimization
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: pinskia at gcc dot gnu dot org
CC: dann at godzilla dot ics dot uci dot edu,gcc-bugs at gcc
dot gnu dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13876
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug optimization/13876] loop not fully optimized
2004-01-27 6:06 [Bug optimization/13876] New: loop not fully optimized pinskia at gcc dot gnu dot org
2004-01-27 6:06 ` [Bug optimization/13876] " pinskia at gcc dot gnu dot org
@ 2004-01-27 6:07 ` pinskia at gcc dot gnu dot org
2004-01-28 22:03 ` pinskia at gcc dot gnu dot org
` (3 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-01-27 6:07 UTC (permalink / raw)
To: gcc-bugs
--
What |Removed |Added
----------------------------------------------------------------------------
CC| |dalej at gcc dot gnu dot org
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13876
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug optimization/13876] loop not fully optimized
2004-01-27 6:06 [Bug optimization/13876] New: loop not fully optimized pinskia at gcc dot gnu dot org
2004-01-27 6:06 ` [Bug optimization/13876] " pinskia at gcc dot gnu dot org
2004-01-27 6:07 ` pinskia at gcc dot gnu dot org
@ 2004-01-28 22:03 ` pinskia at gcc dot gnu dot org
2004-01-29 22:14 ` law at redhat dot com
` (2 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-01-28 22:03 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2004-01-28 22:03 -------
This is a problem with jump threading as if you change the fcuntion t to be:
void t(int l, int *y)
{
int i;
int NotFound;
o();
for(i = 0, NotFound = 1;i<l;i++)
{
if (y[i])
{
NotFound = 0;
g();
}
if (!NotFound)
break;
}
h(NotFound);
}
It works correctly but changing it to:
void t(int l, int *y)
{
int i;
int NotFound;
o();
for(i = 0, NotFound = 1;i<l;i++)
{
if (!NotFound)
break;
if (y[i])
{
NotFound = 0;
g();
}
}
h(NotFound);
}
It does not.
--
What |Removed |Added
----------------------------------------------------------------------------
CC| |law at gcc dot gnu dot org
Status|UNCONFIRMED |NEW
Ever Confirmed| |1
Last reconfirmed|0000-00-00 00:00:00 |2004-01-28 22:03:27
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13876
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug optimization/13876] loop not fully optimized
2004-01-27 6:06 [Bug optimization/13876] New: loop not fully optimized pinskia at gcc dot gnu dot org
` (2 preceding siblings ...)
2004-01-28 22:03 ` pinskia at gcc dot gnu dot org
@ 2004-01-29 22:14 ` law at redhat dot com
2004-05-24 15:19 ` [Bug tree-optimization/13876] " pinskia at gcc dot gnu dot org
2005-05-07 18:53 ` pinskia at gcc dot gnu dot org
5 siblings, 0 replies; 7+ messages in thread
From: law at redhat dot com @ 2004-01-29 22:14 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From law at redhat dot com 2004-01-29 22:14 -------
Subject: Re: loop not fully optimized
In message <20040128220328.24048.qmail@sources.redhat.com>, "pinskia at gcc dot
gnu dot org" writes:
>
>------- Additional Comments From pinskia at gcc dot gnu dot org 2004-01-28 2
>2:03 -------
>This is a problem with jump threading as if you change the fcuntion t to be:
>void t(int l, int *y)
>{
> int i;
> int NotFound;
> o();
> for(i = 0, NotFound = 1;i<l;i++)
> {
> if (y[i])
> {
> NotFound = 0;
> g();
> }
> if (!NotFound)
> break;
> }
> h(NotFound);
>}
>
>It works correctly but changing it to:
>void t(int l, int *y)
>{
> int i;
> int NotFound;
> o();
> for(i = 0, NotFound = 1;i<l;i++)
> {
> if (!NotFound)
> break;
> if (y[i])
> {
> NotFound = 0;
> g();
> }
> }
> h(NotFound);
>}
>It does not.
Right. This is actually something I had already started looking at and
addressing it is going to be a reasonable amount of work.
To correctly handle this we need to record temporary equivalences for
every PHI we pass through during the dominator walk so that a temporary
equivalence created by a PHI in an earlier block can be used to thread
through a later block. Right now we only record temporary equivalences
for the PHI in the block we want to thread through.
If we look at the dump if your code we have:
# BLOCK 0
# PRED: ENTRY [100.0%] (fallthru,exec)
# MT.4_17 = VDEF <MT.4_16>;
o ();
goto <bb 5> (<L4>);
# SUCC: 5 [100.0%] (fallthru,exec)
# BLOCK 1
# PRED: 5 [95.0%] (true,exec)
<L0>:;
if (NotFound_3 == 0) goto <L5>; else goto <L1>;
# SUCC: 2 [95.0%] (false,exec) 6 [5.0%] (true,exec)
# BLOCK 2
# PRED: 1 [95.0%] (false,exec)
<L1>:;
i.0_7 = (unsigned int)i_1;
T.1_8 = i.0_7 * 4;
T.2_10 = T.1_8 + y_9;
# VUSE <MT.4_15>;
T.3_11 = *T.2_10;
if (T.3_11 != 0) goto <L2>; else goto <L3>;
# SUCC: 4 [70.0%] (false,exec) 3 [30.0%] (true,exec)
# BLOCK 3
# PRED: 2 [30.0%] (true,exec)
<L2>:;
# MT.4_19 = VDEF <MT.4_15>;
g ();
# SUCC: 4 [100.0%] (fallthru,exec)
# BLOCK 4
# PRED: 2 [70.0%] (false,exec) 3 [100.0%] (fallthru,exec)
# MT.4_14 = PHI <MT.4_15(2), MT.4_19(3)>;
# NotFound_2 = PHI <NotFound_3(2), 0(3)>;
<L3>:;
i_12 = i_1 + 1;
# SUCC: 5 [100.0%] (fallthru,dfs_back,exec)
# BLOCK 5
# PRED: 4 [100.0%] (fallthru,dfs_back,exec) 0 [100.0%] (fallthru,exec)
# MT.4_15 = PHI <MT.4_17(0), MT.4_14(4)>;
# NotFound_3 = PHI <1(0), NotFound_2(4)>;
# i_1 = PHI <0(0), i_12(4)>;
<L4>:;
if (i_1 < l_6) goto <L0>; else goto <L5>;
# SUCC: 6 [5.0%] (false,exec) 1 [95.0%] (true,exec)
# BLOCK 6
# PRED: 5 [5.0%] (false,exec) 1 [5.0%] (true,exec)
<L5>:;
# MT.4_18 = VDEF <MT.4_15>;
h (NotFound_3);
return;
# SUCC: EXIT [100.0%]
}
We need to record a temporary equivalence NotFound_3 = 0 when we start
processing block #5 so that we can use that equivalence to eliminate
the test in block #1.
To do this effectively we really need a temporary equivalence table which
is maintained through the dominator walk for the sole use by the jump
threader -- these equivalences can't be used for const/copy propagation
for example since they are specific to a particular path through the
dominator tree.
Note this will not fix the first testcase you mention in the PR -- something
more complex is necessary to analyze the behavior of NotFound. See "Beyond
Induction Variables" from Gerlek, Stolz & Wolfe -- IIRC their analysis would
be able to determine the behavior of NotFound in the loop and optimize
the code appropriately. I think everyone would agree that having the kind of
analysis mentioned in that paper needs to be on the "plan".
jeff
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13876
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug tree-optimization/13876] loop not fully optimized
2004-01-27 6:06 [Bug optimization/13876] New: loop not fully optimized pinskia at gcc dot gnu dot org
` (3 preceding siblings ...)
2004-01-29 22:14 ` law at redhat dot com
@ 2004-05-24 15:19 ` pinskia at gcc dot gnu dot org
2005-05-07 18:53 ` pinskia at gcc dot gnu dot org
5 siblings, 0 replies; 7+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2004-05-24 15:19 UTC (permalink / raw)
To: gcc-bugs
--
What |Removed |Added
----------------------------------------------------------------------------
Target Milestone|3.5.0 |---
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13876
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug tree-optimization/13876] loop not fully optimized
2004-01-27 6:06 [Bug optimization/13876] New: loop not fully optimized pinskia at gcc dot gnu dot org
` (4 preceding siblings ...)
2004-05-24 15:19 ` [Bug tree-optimization/13876] " pinskia at gcc dot gnu dot org
@ 2005-05-07 18:53 ` pinskia at gcc dot gnu dot org
5 siblings, 0 replies; 7+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2005-05-07 18:53 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pinskia at gcc dot gnu dot org 2005-05-07 18:52 -------
The orginal testcase in comment #0 is fixed now but not the one in comment #2.
--
What |Removed |Added
----------------------------------------------------------------------------
Last reconfirmed|2005-04-16 17:31:17 |2005-05-07 18:52:59
date| |
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13876
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2005-05-07 18:53 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2004-01-27 6:06 [Bug optimization/13876] New: loop not fully optimized pinskia at gcc dot gnu dot org
2004-01-27 6:06 ` [Bug optimization/13876] " pinskia at gcc dot gnu dot org
2004-01-27 6:07 ` pinskia at gcc dot gnu dot org
2004-01-28 22:03 ` pinskia at gcc dot gnu dot org
2004-01-29 22:14 ` law at redhat dot com
2004-05-24 15:19 ` [Bug tree-optimization/13876] " pinskia at gcc dot gnu dot org
2005-05-07 18:53 ` pinskia at gcc dot gnu dot org
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).