Path: utzoo!attcan!uunet!lll-winken!lll-tis!ames!sri-spam!sri-unix!garth!smryan
From: smryan@garth.UUCP (Steven Ryan)
Newsgroups: comp.lang.c
Subject: Re: volatile
Summary: Undecidable predicates.
Message-ID: <659@garth.UUCP>
Date: 18 May 88 19:36:23 GMT
References: <20345@pyramid.pyramid.com> <502@wsccs.UUCP> <51431@sun.uucp> <390@attila.weitek.UUCP> <11547@mimsy.UUCP>
Reply-To: smryan@garth.UUCP (S M Ryan)
Organization: INTERGRAPH (APD) -- Palo Alto, CA
Lines: 50
Posted: Wed May 18 12:36:23 1988

A compiler cannot crossreference all modules to detect "volatile":
    - this is enormously expensive.
    - it requires access to internals of other modules including 
      possible binary-only copyrighted libraries, et cetera.
    - it still won't work.

Besides the problem the memorymapped i/o, which can vary from configuration
to configuration even on the same processor, many operating systems set up
communication areas in user space which can be asynchronously modified.

For example, in CDC NOS, the CIO PP can modify fet fields and the buffer
while the user program is running in the same address space. IAF can set
an interrupt flag. RPV can be used to call an arbritrary routine during a
fault or interrupt.

A programmer has the options:
   - write a good machine independent algorithm and not attempt linear speedup
     with an optimiser.
   - handoptimise it for a specific machine or specific configuration.
   - give the compiler as much information as possible, in a machine
     independent fashion, so that it can optimise safely and effectively
     for a specific processor.

Optimisers face many internal predicates and usually they just cannot decide.
As an example of a different optimisation problem,

      INTEGER A(N),B(N),X(N)
      DO 1 I=1,N
    1  A(X(I)) = B(N)

is vectorisable on the CYBER FORTRAN 200 as is

      DO 2 I=1,N
    2  B(I) = A(X(I))

but
    
      DO 2 I=1,N
    2  A(X(I)) = A(X(I))

is not vectoriable. If X is not injection (Xi=Xj, i/=j), the last loop has
feedback. The optimiser does not generally know if X is injective, so that
it assumes feedback in all cases.

In summary, do not expect an optimiser to magically guess all relations of
a program. It has worse time understanding a program than the authour, and
we all know how hard it is to completely understand one of our own 
middling programs.

                                            Hafa an godne daege.
                                                         sm ryan