Bug 19507 - missed tree-optimization (constant for the rest of the function)
Summary: missed tree-optimization (constant for the rest of the function)
Status: RESOLVED DUPLICATE of bug 13397
Alias: None
Product: gcc
Classification: Unclassified
Component: tree-optimization (show other bugs)
Version: 4.0.0
: P2 enhancement
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords: alias, missed-optimization
Depends on:
Blocks:
 
Reported: 2005-01-18 16:19 UTC by Richard Biener
Modified: 2005-09-22 19:33 UTC (History)
1 user (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Richard Biener 2005-01-18 16:19:03 UTC
The following testcase:


class Flag {
public:
        Flag(bool f) : flag(f) {}
        bool test() const { return flag; }
private:
        const bool flag;
};

void bar(void);

void foo(const Flag& f)
{
        if (f.test())
                bar();
        if (f.test())
                bar();
}


Should from my point of view should generate exactly one test
and optimize the redundant one.  I miss what could be a not
ill-formed way of bar() modifying Flag::flag.

With mainline -O2 -S -fdump-tree-optimized-vops we get for
t63.optimized:

<bb 0>:
  if (f->flag != 0) goto <L1>; else goto <L2>;

<L1>:;
  #   TMT.2_17 = V_MAY_DEF <TMT.2_15>;
  bar ();

<L2>:;
  if (f->flag != 0) goto <L4>; else goto <L5>;

<L4>:;
  #   TMT.2_16 = V_MAY_DEF <TMT.2_14>;
  bar () [tail call];

<L5>:;
  return;


The RTL optimizers exploit a valid optimization, namely:

_Z3fooRK4Flag:
.LFB6:
        pushl   %ebx    #
.LCFI0:
        subl    $8, %esp        #,
.LCFI1:
        movl    16(%esp), %ebx  # f, f
        cmpb    $0, (%ebx)      # <variable>.flag
        jne     .L8     #,
.L6:
        addl    $8, %esp        #,
        popl    %ebx    #
        ret
        .p2align 4,,7
.L8:
        call    _Z3barv #
        cmpb    $0, (%ebx)      # <variable>.flag
        .p2align 4,,4
        je      .L6     #,
        addl    $8, %esp        #,
        popl    %ebx    #
        jmp     _Z3barv #


where you can see we optimized the function into the equivalent of

   if (!f.test())
     return;
   bar();
   if (!f.test())
     return;
   bar();

Who is supposed to apply the corresponding tree optimization here?

Of course, I think it is valid to omit the second test completely
as there is no valid way for bar() to change Flag::flag.

Note that this may be a frontend issue, as to the tree-optimizers
this may be no different than

void foo(const bool& f)
{
   if (f)
      bar();
   if (f)
      bar();
}

where there of course are valid ways for bar() to change f.
Comment 1 Richard Biener 2005-01-18 16:39:47 UTC
A C testcase with the missing jump threading(?):

void bar(void);

void foo(const _Bool *flag)
{
	if (*flag)
		bar();
	if (*flag)
		bar();
}


a testcase where we able to thread the jump:

extern long int random(void);

void foo(void)
{
	long int i = random();
	if (i)
		i = random();
	if (i)
		i = random();
}


the difference seems to be we use .GLOBAL_VAR_10 = V_MAY_DEF <.GLOBAL_VAR_9>;
in the latter while we use TMT.0_9 = V_MAY_DEF <TMT.0_7>; in the former.
Though, of course, I don't know what either means.
Comment 2 Andrew Pinski 2005-01-18 20:06:03 UTC
(In reply to comment #1)
> A C testcase with the missing jump threading(?):
> 
> void bar(void);
> 
> void foo(const _Bool *flag)
> {
>         if (*flag)
>                 bar();
>         if (*flag)
>                 bar();
> }

No this one cannot be optimizated because we can change what is in flag in bar();
For an example in C++  where we can change it:

struct a
{
  int i;
};

a b;

int f(void);

int g(const a &c) 
{
  int i = 0;
  if (c.i)
   i = f();
  if (c.i) // even though c is const&, we can still change it in f()
   i += f();
  return i;
}

int f(void)
{
  b.i=0;
  return 1;
}

extern "C" void abort (void);

int main(void)
{
  b.i = 1;
  if (g(b)!=1)
   abort ();
  return 0;
}

So we cannot do that since it will be an invalid transformation (unless you have IPA).
Comment 3 Andrew Pinski 2005-01-18 20:07:06 UTC
(In reply to comment #2)
> For an example in C++  where we can change it:
Obviosly I mean cannot change it.
Comment 4 Richard Biener 2005-01-18 20:10:18 UTC
Subject: Re:  missed tree-optimization

pinskia at gcc dot gnu dot org wrote:
> ------- Additional Comments From pinskia at gcc dot gnu dot org  2005-01-18 20:06 -------
> (In reply to comment #1)
> 
>>A C testcase with the missing jump threading(?):
>>
>>void bar(void);
>>
>>void foo(const _Bool *flag)
>>{
>>        if (*flag)
>>                bar();
>>        if (*flag)
>>                bar();
>>}
> 
> 
> No this one cannot be optimizated because we can change what is in flag in bar();

I meant this should be transformed to

if (!*flag)
   return;
bar();
if (*flag)
   bar();

this is done at RTL level, but not at tree level.  I should file a 
separate bug for this one, really.

Richard.

Comment 5 Andrew Pinski 2005-01-18 22:00:50 UTC
(In reply to comment #4)
> Subject: Re:  missed tree-optimization
> 
> this is done at RTL level, but not at tree level.  I should file a 
> separate bug for this one, really.
Yes because if we change flag to be int/short/char it works which is a little werid.
Comment 6 Richard Biener 2005-01-18 22:29:24 UTC
Done. PR19516.
Comment 7 Richard Biener 2005-05-11 09:35:17 UTC
Mainline now has

void foo(const Flag&) (f)
{
  const bool D.1718;
  int D.1717;
  struct Flag * const this;
  const bool D.1713;
  int D.1712;
  struct Flag * const this;
  bool D.1707;
  bool retval.1;
  bool D.1705;
  bool retval.0;
  int D.1716;
  int D.1711;

<bb 0>:
  if (f->flag != 0) goto <L1>; else goto <L5>;

<L1>:;
  bar ();
  if (f->flag != 0) goto <L4>; else goto <L5>;

<L4>:;
  bar () [tail call];

<L5>:;
  return;

}


I.e. the missing jump threading is done, but still f->flag is seen as
possibly clobbered by the call to bar().  Still a language lawyer has
to sneak in and tell this optimization would be indeed valid.  The key
is privateness or constness of Flag::flag.
Comment 8 Andrew Pinski 2005-09-22 19:33:00 UTC
This is a dup of bug 13397.

*** This bug has been marked as a duplicate of 13397 ***