rang@cs.wisc.edu (Anton Rang) (11/19/90)
Another thread I probably should avoid....
Suppose that I have a FORTRAN subroutine which takes two parameters
which it may modify, X and Y. Assume that the array A is declared
somehow; exactly how isn't important. Suppose you have the code:
SUBROUTINE BLAH(X,Y)
INTEGER X,Y
X = 3
Y = 2
IF (A(X) .EQ. 0) ...
Translating this to C, you get:
blah(int *x, int *y)
{
*x = 3;
*y = 2;
if (a(*x) == 0) ...
A compiler for FORTRAN can optimize the test to be A(3) since it
knows that the assignment to Y can never change X. A compiler for C,
in the absence of interprocedural aliasing information, cannot do the
same.
The interprocedural aliasing problem is NP-hard in the presence of
multi-level pointers or reference parameters (sorry, my refs are at
home right now, but if any cares e-mail me), and so various
approximation algorithms are used. For any approximation algorithm, I
can write (pathological) FORTRAN code which will result in worse code
being generated by the C compiler.
Anton
+---------------------------+------------------+-------------+
| Anton Rang (grad student) | rang@cs.wisc.edu | UW--Madison |
+---------------------------+------------------+-------------+ccml@levels.sait.edu.au (11/21/90)
In article <RANG.90Nov18160113@nexus.cs.wisc.edu>, rang@cs.wisc.edu (Anton Rang) writes: > Another thread I probably should avoid.... ditto :-) > > Suppose that I have a FORTRAN subroutine which takes two parameters > which it may modify, X and Y. Assume that the array A is declared > somehow; exactly how isn't important. Suppose you have the code: > > SUBROUTINE BLAH(X,Y) > INTEGER X,Y > X = 3 > Y = 2 > IF (A(X) .EQ. 0) ... > > Translating this to C, you get: [c example deleted] > > A compiler for FORTRAN can optimize the test to be A(3) since it > knows that the assignment to Y can never change X. A compiler for C, > in the absence of interprocedural aliasing information, cannot do the > same. Assuming that there was no 'EQUIVALENCE (a,b)' in the routine which does the 'CALL BLAH(a,b)'! I would argue that a compiler can easily optimize that test to A(3) if the subroutine contained 'PARAMETER X=3' but other circumstances need care. That would of course be pretty close to C's '#define'. Martin Leadbeater Acad. Computing Service S.A. Institute of Tehcnology > > The interprocedural aliasing problem is NP-hard in the presence of > multi-level pointers or reference parameters (sorry, my refs are at > home right now, but if any cares e-mail me), and so various > approximation algorithms are used. For any approximation algorithm, I > can write (pathological) FORTRAN code which will result in worse code > being generated by the C compiler. > > Anton > > +---------------------------+------------------+-------------+ > | Anton Rang (grad student) | rang@cs.wisc.edu | UW--Madison | > +---------------------------+------------------+-------------+
rang@cs.wisc.edu (Anton Rang) (11/22/90)
In article <15704.274a7509@levels.sait.edu.au> ccml@levels.sait.edu.au writes: >I wrote: >> SUBROUTINE BLAH(X,Y) >> INTEGER X,Y >> X = 3 >> Y = 2 >> IF (A(X) .EQ. 0) ... >> >> [edited down] >> A compiler for FORTRAN can optimize the test to be A(3) since it >> knows that the assignment to Y can never change X. A compiler for C, >> in the absence of interprocedural aliasing information, cannot do the >> same. > >Assuming that there was no 'EQUIVALENCE (a,b)' in the routine >which does the 'CALL BLAH(a,b)'! If there was, then the program is erroneous (not legal FORTRAN, I'm not sure if 'erroneous' is the term ANSI uses in the FORTRAN spec). In a legal FORTRAN program, X and Y can never be aliased (strictly speaking, program execution can not depend on whether X and Y are aliased or not). Anton +---------------------------+------------------+-------------+ | Anton Rang (grad student) | rang@cs.wisc.edu | UW--Madison | +---------------------------+------------------+-------------+
bglenden@mandrill.cv.nrao.edu (Brian Glendenning) (11/22/90)
In article <RANG.90Nov21115939@nexus.cs.wisc.edu> rang@cs.wisc.edu (Anton Rang) writes: In article <15704.274a7509@levels.sait.edu.au> ccml@levels.sait.edu.au writes: >I wrote: >> SUBROUTINE BLAH(X,Y) >> INTEGER X,Y >> X = 3 >> Y = 2 >> IF (A(X) .EQ. 0) ... >> >> [edited down] >> A compiler for FORTRAN can optimize the test to be A(3) since it >> knows that the assignment to Y can never change X. A compiler for C, >> in the absence of interprocedural aliasing information, cannot do the >> same. > >Assuming that there was no 'EQUIVALENCE (a,b)' in the routine >which does the 'CALL BLAH(a,b)'! If there was, then the program is erroneous (not legal FORTRAN, I'm not sure if 'erroneous' is the term ANSI uses in the FORTRAN spec). In a legal FORTRAN program, X and Y can never be aliased (strictly speaking, program execution can not depend on whether X and Y are aliased or not). Do real compilers ever complain about this? Or do FORTRAN compilers just assume that that users will never alias subroutine arguments? Brian -- Brian Glendenning - National Radio Astronomy Observatory bglenden@nrao.edu bglenden@nrao.bitnet (804) 296-0286
rang@cs.wisc.edu (Anton Rang) (11/27/90)
In article <BGLENDEN.90Nov21142152@mandrill.cv.nrao.edu> bglenden@mandrill.cv.nrao.edu (Brian Glendenning) writes: >Do real compilers ever complain about [aliasing]? Or do FORTRAN compilers >just assume that that users will never alias subroutine arguments? I haven't seen one which complained, but there may be some out there. Of course, detecting aliasing in general is a hard problem; it's quite possible the compiler simply assumes the user knows what he's doing, and doesn't try to detect the special cases. I'm also not sure if the FORTRAN standard allows parameters to be aliased if they aren't changed in the called subroutine; I've seen a lot of FORTRAN code which looks like CALL X(A,N,N) for instance. Since the intent seems to be to allow either pass-by-reference or pass-by-value-result, I have a hard time coming up with a scenario where this *wouldn't* work (assuming, of course, that the two formal parameters are used in a read-only way)...but it might not be legal. Anton +---------------------------+------------------+-------------+ | Anton Rang (grad student) | rang@cs.wisc.edu | UW--Madison | +---------------------------+------------------+-------------+
jlg@lanl.gov (Jim Giles) (11/29/90)
From article <15704.274a7509@levels.sait.edu.au>, by ccml@levels.sait.edu.au:
< In article <RANG.90Nov18160113@nexus.cs.wisc.edu>, rang@cs.wisc.edu (Anton Rang) writes:
<> [...]
<> SUBROUTINE BLAH(X,Y)
<> INTEGER X,Y
<> X = 3
<> Y = 2
<> IF (A(X) .EQ. 0) ...
<> [...]
<> A compiler for FORTRAN can optimize the test to be A(3) since it
<> knows that the assignment to Y can never change X. A compiler for C,
<> in the absence of interprocedural aliasing information, cannot do the
<> same.
< Assuming that there was no 'EQUIVALENCE (a,b)' in the routine
< which does the 'CALL BLAH(a,b)'!
Yes, that is the assumption being made. It is a valid assumption.
An EQUIVALENCE (a,b) in the context you mention is _illegal_, so
the compiler is perfectly free to assume it didn't happen. Now, it
_is_ true that most Fortran implementations don't actually test to
make sure that the illegal aliasing didn't occur - but _many_ available
Fortran analysis tools can discover these for you.
J. Giles