From -4629421571619258845
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: f78e5,ccb764366ee3f529
X-Google-Attributes: gidf78e5,public
X-Google-ArrivalTime: 2002-04-08 18:37:08 PST
Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!kibo.news.demon.net!news.demon.co.uk!demon!mail2news.demon.co.uk!not-for-mail
From: thp@cs.ucr.edu
Newsgroups: comp.std.c++
Subject: Re: Proposal: allow code hoisting optimizatoin for "assert"
Date: Tue,  9 Apr 2002 01:36:54 GMT
Organization: University of California, Riverside
Approved: Fergus Henderson <fjh@cs.mu.oz.au>, moderator of comp.std.c++
Message-ID: <a8tfgj$eu4$1@glue.ucr.edu>
References: <3CB1290F.8000407@animats.com>
X-Trace: mail2news.demon.co.uk 1018316220 mail2news:20062 mail2news mail2news.demon.co.uk
X-Complaints-To: abuse@demon.net
X-Mail2News-Path: news.demon.net!mulga.cs.mu.oz.au
X-Authentication-Warning: mulga.cs.mu.OZ.AU: fjh set sender to devnull@stump.algebra.com using -f
X-Robomod: STUMP, ichudov@algebra.com (Igor Chudov)
NNTP-Posting-Date: Tue, 9 Apr 2002 01:18:11 +0000 (UTC)
User-Agent: tin/1.4.4-20000803 ("Vet for the Insane") (UNIX) (Linux/2.4.13-xfs (i686))
Lines: 80
Xref: archiver1.google.com comp.std.c++:10458

John Nagle <nagle@animats.com> wrote:
:     I'd like to propose that the following optimization
: be allowed.  Consider

: 	for (int i=0; i<n; i++)
: 	{	tab[i] = 0; }

: Now suppose that tab[i] is a class with subscript
: checking, implemented as an assert.  I'd like to
: allow the compiler to hoist that assert out of the
: loop.  Rather than performing

: 	assert(i < tab.size());

: every time through the loop, the compiler should
: be allowed, if it's smart enough, to do

: 	assert(n <= tab.size());

: at the beginning of the loop.

If you are confident that tab.size() will always return the same
value, you probably need to say so to the compiler:

        int temp = tab.size();
 	for ( int i=0; i<n; i++ ) {
          assert( i <= temp );
          tab[i] = 0; 
        }

I suspect that elimination of induction variables plus code hoisting
will optimize the this construct appropriately.

:     But right now, compilers can't do that.
: Hoisting the assert out of the loop makes it
: fail "early", which is an illegal optimization.

I'm not sure what you mean by "early" here.  As long as no externally
visible behavior takes place inside the loop, i.e., no I/O and/or
accesses of volatile objects, it makes no difference AFIK whether the
failure occurs inside or before the loop.

: I suggest making it a legal one, and allow the
: compiler to understand that "assert" is special.

:     Specifically,

:      A compiler should be allowed to recognize
: "assert" at compile time.

There should be nothing special about assert wrt hoisting.

:      An assertion failure may be detected any time
: after assertion failure becomes inevitable.
: The compiler is not required to consider the
: possibility that an exception will be raised
: which prevent the assertion from failing.

:      This lays the groundwork for efficient subscript,
: checking.  Old studies of Pascal programs indicated
: that 95% of subscript checks could be hoisted out of
: loops.  Subscript checking has been implemented for
: C++, but it's slow.  This allows implementations
: that do it fast.

:      Comments?

IIRC, Pascal's for-loop computes the upper limit only once.  In C/C++,
the upper limit can be a formula whose invariance may be difficult to
establish due to aliasing etc..  Other than that, I don't see what
advantages Pascal has wrt hoisting bounds checking out of a loop.

Tom Payne

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html                       ]