[PATCH] Fix PR optimization/6713

[PATCH] Fix PR optimization/6713

[Eric Botcazou]

[-- Attachment #1: Type: text/plain, Size: 1976 bytes --]

I build up the following analysis on Glen Nakamura's findings:
http://gcc.gnu.org/ml/gcc-bugs/2002-05/msg00897.html

insn 482 should have been deleted by cse.c:delete_trivially_dead_insns
under normal circumstances, i.e if insn 482 was either:
- a "regular" SET insn that defines a giv (i.e not via a NOTE), or
- a SET insn that defines a giv via a NOTE, but with a SET_SRC not being
itself another giv that gets combined with the first one.

Now the situation is the following when loop_optimize is called for
the first time:

insn #1:  giv2 <-- (biv+1)
insn #2:  giv1 <-- giv2 (REQ_EQUAL: (biv+1))
insn #3:  biv  <-- giv1

GCC is smart enough to detect that:
- the biv is incremented by 1 at insn #3,
- giv2 can be combined ("replaced") with giv1,
- the biv can be eliminated.

Actually giv2 is not directly "replaced" by giv1, but both are merged
into a third register, giv3, in the following way:
- giv3 is moved to giv1 with a new instruction:

insn #1:  giv2 <-- (biv+1)
insn #2:  giv1 <-- giv2 (REQ_EQUAL: (biv+1))
insn #4:  giv1 <-- giv3
insn #3:  biv  <-- giv1

I think the code expects insn #2 to be deleted by
delete_trivially_dead_insns, but...

- giv2 is scheduled to be replaced by giv3 at the end of the pass (only SRC
operands)

insn #1:  giv2 <-- (biv+1)
insn #2:  giv1 <-- giv3 (REQ_EQUAL: (biv+1))
insn #4:  giv1 <-- giv3
insn #3:  biv  <-- giv1

delete_trivially_dead_insns deletes insn #1, but not insn #2, likely because
of the note:

insn #2:  giv1 <-- giv3 (REQ_EQUAL: (biv+1))
insn #4:  giv1 <-- giv3
insn #3:  biv  <-- giv1


The proposed fix is to explicitly delete insn #2 when issuing insn #4.
Bootstrapped/regtested (C/C++) on i586-pc-linux-gnu (gcc-3_1-branch).


2002-06-17  Eric Botcazou <ebotcazou@multimania.com>
            Glen Nakamura <glen@imodulo.com>

 PR optimization/6713
 * loop.c (loop_givs_rescan): Explicitly delete the insn that
 sets a non-replaceable giv after issuing the new one.

--
Eric Botcazou
ebotcazou@multimania.com

[-- Attachment #2: loop.diff --]
[-- Type: application/octet-stream, Size: 1121 bytes --]

*** gcc/loop.c.orig	Mon Jun 17 12:06:38 2002
--- gcc/loop.c	Mon Jun 17 13:21:09 2002
***************
*** 4784,4793 ****
  	}
        else
  	{
  	  /* Not replaceable; emit an insn to set the original giv reg from
  	     the reduced giv, same as above.  */
! 	  loop_insn_emit_after (loop, 0, v->insn,
  				gen_move_insn (v->dest_reg, v->new_reg));
  	}
  
        /* When a loop is reversed, givs which depend on the reversed
--- 4784,4801 ----
  	}
        else
  	{
+ 	  rtx original_insn = v->insn;
+ 
  	  /* Not replaceable; emit an insn to set the original giv reg from
  	     the reduced giv, same as above.  */
! 	  v->insn = loop_insn_emit_after (loop, 0, v->insn,
  				gen_move_insn (v->dest_reg, v->new_reg));
+ 
+ 	  /* Also delete the original insn that sets the giv because it may
+ 	     become identical with the newly generated one after all the
+ 	     register substitutions scheduled in REG_MAP and carry a note
+ 	     referring to the biv, thus preventing cse from deleting it.  */
+ 	  delete_insn (original_insn);
  	}
  
        /* When a loop is reversed, givs which depend on the reversed

Re: [PATCH] Fix PR optimization/6713

[Neil Booth]

Eric Botcazou wrote:-

> I build up the following analysis on Glen Nakamura's findings:
> http://gcc.gnu.org/ml/gcc-bugs/2002-05/msg00897.html

Please include a testcase for the testsuite when fixing bugs.

Thanks,

Neil.

Re: [PATCH] Fix PR optimization/6713

[Eric Botcazou]

> Please include a testcase for the testsuite when fixing bugs.

Ah! yes, sorry about that. Unfortunately I'm not very used to distilling
self-contained C++ testcases from standalone programs using big templates,
so this may take a little time (I already tried the naïve approach of
writing a stripped down class, but unsuccessfully so far).

--
Eric Botcazou
ebotcazou@multimania.com

Re: [PATCH] Fix PR optimization/6713

[Eric Botcazou]

> Please include a testcase for the testsuite when fixing bugs.

Fortunately I was cautious... because I still haven't managed to write a
self-contained testcase :-( After several unsuccessful attempts with the
original preprocessed C++ file, I'm back to good old C.

I have the structure of the testcase, but I need to trigger a REG_EQUAL note
for two consecutive insns just after GCSE (pass #10, -dG):

    insn #1: reg2 <-- (reg1+1)
    insn #2: reg3 <-- reg2 (REQ_EQUAL: (reg1+1))

How should I do that ? Up to now the tricks I've used were either caught too
early by the TREE-based optimizations or not caught (early enough) by the
RTL-based ones.

--
Eric Botcazou
ebotcazou@multimania.com

Re: [PATCH] Fix PR optimization/6713

[Eric Botcazou]

[-- Attachment #1: Type: text/plain, Size: 118 bytes --]

> Please include a testcase for the testsuite when fixing bugs.

Attached.

--
Eric Botcazou
ebotcazou@multimania.com

[-- Attachment #2: pr6713.C --]
[-- Type: application/octet-stream, Size: 2432 bytes --]

// PR optimization/6713
// This testcase segfaulted on x86 because a REG_EQUAL note
// prevented CSE from removing the original insn that set a
// giv after a replacement insn was issued.
// { dg-do run }
// { dg-options "-O2" }

template<typename _CharT> class basic_iterator
{
  public:
    basic_iterator(_CharT* _p) : _M_current(_p) {}
    basic_iterator& operator++() { ++_M_current; return *this; }
    _CharT& operator*() const { return *_M_current; }
    bool operator!=(basic_iterator &_rhs) { return _M_current != _rhs._M_current; }

  private:
    _CharT* _M_current;
};

template<typename _CharT> class basic_string
{
  public:
    typedef unsigned int size_type;
    typedef basic_iterator<_CharT> iterator;

  private:
    struct _Rep
    {
      size_type _M_length;
      size_type _M_capacity;
      int _M_references;

      bool _M_is_leaked() const { return _M_references < 0; }
      bool _M_is_shared() const { return _M_references > 0; }
      void _M_set_leaked() { _M_references = -1; }
      void _M_set_sharable() { _M_references = 0; }
    };

    struct _Rep _M_rep;

    struct _Alloc_hider
    {
      _CharT _raw[16];
      _CharT* _M_p;
    };

    mutable _Alloc_hider _M_dataplus;

    _CharT* _M_data() const { return _M_dataplus._M_p; }

    void _M_leak() { if (!_M_rep._M_is_leaked()) _M_leak_hard(); }

    static int count;

    static void _M_leak_hard();

  public:
    explicit basic_string(const _CharT* __s);

    iterator begin() { _M_leak(); return iterator(_M_data()); }

    iterator end() { _M_leak(); return iterator(_M_data() + this->size()); }

    size_type size() const { return _M_rep._M_length; }
};

template<typename _CharT> basic_string<_CharT>::
basic_string(const _CharT* __s)
{
  int i;

  for (i=0; i<15; i++) {
    if (!__s[i])
      break;

    _M_dataplus._raw[i] = __s[i];
  }

  _M_dataplus._raw[i] = 0;
  _M_dataplus._M_p = _M_dataplus._raw;

  _M_rep._M_length = i;
  _M_rep._M_capacity = i;
  _M_rep._M_references = 1;
}     

template<typename _CharT> int basic_string<_CharT>::count = 0;

template<typename _CharT> void basic_string<_CharT>::
_M_leak_hard()
{
  count++;
}

typedef basic_string<char> string;


int isspa(int ch)
{
  return 0;
}

void foo(string& str)
{
  string::iterator it = str.begin();
  string::iterator stop = str.end();

  for (; it != stop; ++it)
    if (isspa(*it))
      break;
}

int main()
{
  string str("test");
  foo(str);
}

Re: [PATCH] Fix PR optimization/6713

[Richard Henderson]

On Mon, Jun 17, 2002 at 09:55:45PM +0200, Eric Botcazou wrote:
> The proposed fix is to explicitly delete insn #2 when issuing insn #4.
> Bootstrapped/regtested (C/C++) on i586-pc-linux-gnu (gcc-3_1-branch).

The analysis is nearly, but not quite correct.  The problem
is not that delete_trivially_dead_insns did or did not remove
the instruction.  The problem is that REG_EQUAL means that 
the source is set exactly once, and is valid across the entire
function.  Which isn't true anymore, since we've just added
a second set.

I thought about removing just the note.  That does in fact
solve the problem, but we know for a fact that the insn is
dead and the two sets confuses the rest of the loop optimizer.

So I'm considering the following adjustment of the commentary.

Unfortunately, the given test case doesn't go through this 
path on mainline and so passes for completely different reasons.
I'm going to go ahead and apply the patch there anyway, since
I don't see anything that invalidates the analysis.

Mark, ok for 3.1?


r~



Index: loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.389.2.7
diff -c -p -d -r1.389.2.7 loop.c
*** loop.c	15 Jun 2002 01:12:04 -0000	1.389.2.7
--- loop.c	17 Jul 2002 00:27:24 -0000
*************** loop_givs_rescan (loop, bl, reg_map)
*** 4784,4793 ****
  	}
        else
  	{
  	  /* Not replaceable; emit an insn to set the original giv reg from
  	     the reduced giv, same as above.  */
! 	  loop_insn_emit_after (loop, 0, v->insn,
! 				gen_move_insn (v->dest_reg, v->new_reg));
  	}
  
        /* When a loop is reversed, givs which depend on the reversed
--- 4784,4803 ----
  	}
        else
  	{
+ 	  rtx original_insn = v->insn;
+ 
  	  /* Not replaceable; emit an insn to set the original giv reg from
  	     the reduced giv, same as above.  */
! 	  v->insn = loop_insn_emit_after (loop, 0, original_insn,
! 					  gen_move_insn (v->dest_reg,
! 							 v->new_reg));
! 
! 	  /* The original insn may have a REG_EQUAL note.  This note is
! 	     now incorrect and may result in invalid substitutions later.
! 	     We could just delete the note, but we know that the entire
! 	     insn is dead, so we might as well save ourselves the bother
! 	     and remove the whole thing.  */
! 	  delete_insn (original_insn);
  	}
  
        /* When a loop is reversed, givs which depend on the reversed

Re: [PATCH] Fix PR optimization/6713 (testsuite failure)

[David Edelsohn]

	The testcase for this bug which was added to the G++ testsuite
fails on systems without weak symbols because of implicit template
instantiation.  The following patch adds the explicit instantiation on
!__GXX_WEAK__ systems.

	Okay to commit?

Thanks, David


	* g++.dg/opt/pr6713.C: Add instantiation.

Index: pr6713.C
===================================================================
RCS file: /cvs/gcc/egcs/gcc/testsuite/g++.dg/opt/pr6713.C,v
retrieving revision 1.1
diff -c -p -r1.1 pr6713.C
*** pr6713.C	17 Jul 2002 18:00:35 -0000	1.1
--- pr6713.C	18 Jul 2002 22:50:45 -0000
*************** _M_leak_hard()
*** 93,98 ****
--- 93,103 ----
  
  typedef basic_string<char> string;
  
+ #if !__GXX_WEAK__
+ // Explicitly instantiate for systems with no COMDAT or weak support.
+ template int basic_string<char>::count;
+ #endif
+ 
  
  int isspa(int ch)
  {

Re: [PATCH] Fix PR optimization/6713 (testsuite failure)

[Richard Henderson]

On Thu, Jul 18, 2002 at 07:05:58PM -0400, David Edelsohn wrote:
> 	* g++.dg/opt/pr6713.C: Add instantiation.

Oops.  Should work even without checking __GXX_WEAK__, no?


r~

Re: [PATCH] Fix PR optimization/6713 (testsuite failure)

[David Edelsohn]

>>>>> Richard Henderson writes:

Richard> On Thu, Jul 18, 2002 at 07:05:58PM -0400, David Edelsohn wrote:
>> * g++.dg/opt/pr6713.C: Add instantiation.

Richard> Oops.  Should work even without checking __GXX_WEAK__, no?

	Yes, I can instantiate it unconditionally.  I am not sure what
precedent the g++ testsuite uses.  The libstdc++ testsuite tests that
macro.

Thanks, David

Re: [PATCH] Fix PR optimization/6713 (testsuite failure)

[David Edelsohn]

>>>>> Richard Henderson writes:

Richard> Oops.  Should work even without checking __GXX_WEAK__, no?

	The only example I find is

g++.other/instan1.C

explicitly instantiating such a template, but it also explicitly invokes
g++ with -fno-implicit-templates.

	In which form should I check in the patch:

1) with __GXX_WEAK__ test?
2) without __GXX_WEAK__ test?
3) without __GXX_WEAK__ test and with -fno-implicit-templates?

Thanks, David

Re: [PATCH] Fix PR optimization/6713 (testsuite failure)

[Richard Henderson]

On Thu, Jul 18, 2002 at 07:35:39PM -0400, David Edelsohn wrote:
> 2) without __GXX_WEAK__ test?

This one, probably.


r~

Re: [PATCH] Fix PR optimization/6713 (testsuite failure)

[Mark Mitchell]

--On Thursday, July 18, 2002 07:35:39 PM -0400 David Edelsohn 
<dje@watson.ibm.com> wrote:

>>>>>> Richard Henderson writes:
>
> Richard> Oops.  Should work even without checking __GXX_WEAK__, no?
>
> 	The only example I find is
>
> g++.other/instan1.C
>
> explicitly instantiating such a template, but it also explicitly invokes
> g++ with -fno-implicit-templates.
>
> 	In which form should I check in the patch:
>
> 1) with __GXX_WEAK__ test?
> 2) without __GXX_WEAK__ test?
> 3) without __GXX_WEAK__ test and with -fno-implicit-templates?

The idea motivating the libstdc++ decision was that the library tests
should test the library in the mode most likely to be used by the
user on the target system.

So, on systems without weak symbols, libstdc++ tests use explicit
instantiation -- that's what users on those systems do.  On the other
hand, on systems with weak symbols, the libstdc++ tests use implicit
instantiations -- that's what users on those systems usually do.

For the compiler tests, I think we should generally use the same
mechanism for a particular test, independent of the platform.

The point is not to test the library -- it's to test the compiler.  If
instantiation isn't the point of the test, but rather we are trying to
test some *other* aspect of the compiler, then we should probably use
explicit instantiation so that whether or not we are on a system with
weak symbols does not bias the test.

--
Mark Mitchell                   mark@codesourcery.com
CodeSourcery, LLC               http://www.codesourcery.com