corbett@beatnix.UUCP (Bob Corbett) (06/27/89)
There have been articles posted to this group claiming that pointers
make optimization impossible and that the SET RANGE and IDENTIFY statements
would not affect optimization. Those claims are simply wrong.
Adding pointers will make optimization more difficult. Adding
functionality to a language almost always makes optimization more difficult.
Adding pointers will make alias detection more difficult. However, there
are good and well-publicized algorithms for performing alias detection in the
presence of pointers. See, for example, pages 647-653 of the book Compilers:
Principles, Techniques, and Tools by Aho, Sethi, and Ullman. Optimization of
codes that do not use pointers should be unaffected beyond the need to
detect that pointers are not used.
Many languages that provide pointers do not allow pointers to reference
named variables. Such a restriction makes alias detection easier. I would
be willing to accept that restriction in Fortran 8x.
The claim that the SET RANGE and IDENTIFY statements do not affect
optimization is bizarre. I cannot understand how anyone could think that
the IDENTIFY statement does not create an alias when the element named in the
IDENTIFY statement is required to have the ALIAS attribute. The aliasing
problem created by the SET RANGE statement is subtler. The SET RANGE
statement makes it more difficult to tell when references to array elements
overlap.
I suspect that some of those who think SET RANGE and IDENTIFY are more
benign than pointers missed the fact that SET RANGE and IDENTIFY are
executable statements, not declarations. For example, the code fragment
IF (P) THEN
IDENTIFY (X = A)
ELSE
IDENTIFY (X = B)
END IF
X = Z
was allowed. Thus, adding pointers does not make optimization harder than
the IDENTIFY statement would. However, pointers offer more functionality
than the IDENTITY statement.
Yours very truly,
Bob Corbettmccalpin@masig1.ocean.fsu.edu (John D. McCalpin) (06/27/89)
In article <2773@elxsi.UUCP> Bob Corbett writes: > There have been articles posted to this group claiming that pointers >make optimization impossible and that the SET RANGE and IDENTIFY statements >would not affect optimization. Those claims are simply wrong. I don't think that anyone (particularly me) claimed that that SET RANGE made no influence on optimization. What I did suggest is that using SET RANGE to define subarrays is much easier to optimize than using the current draft's POINTERs, since the kinds of things that can be done with SET RANGE are much more limited. Since the draft clearly allows POINTERs to point to arbitrary array sections (see the examples in the draft), I fully expect that many of those who wanted SET RANGE will go ahead and use POINTERs for this same purpose, with potentially negative optimization results. Bob pointed out that SET RANGE is an executable statement. This brings up the question of its domain of influence. I don't have my draft handy, but if SET RANGE has global influence then serious optimization trouble could result! For example: REAL, ARRAY(10,10),RANGE :: A,B,C ! syntax ? SET RANGE ( arguments ) CALL DUMMY ! dummy defines a different range for ! the same range group A = B+C ! what range is used here ? END On the other hand, IDENTIFY clearly has the same sort of aliasing problems as POINTER. I am not sure about ALIAS, but I seem to recall that it was even more limited.... -- John D. McCalpin - mccalpin@masig1.ocean.fsu.edu - mccalpin@nu.cs.fsu.edu
jlg@lanl.gov (Jim Giles) (06/28/89)
From article <2773@elxsi.UUCP>, by corbett@beatnix.UUCP (Bob Corbett): > There have been articles posted to this group claiming that pointers > make optimization impossible and that the SET RANGE and IDENTIFY statements > would not affect optimization. Those claims are simply wrong. I haven't seen any such articles. Could you forward them to me? I have made a comment that is roughly similar to the above claim: SET RANGE and IDENTIFY are _easier_ to optimize than the corresponding pointer usage. I have given demonstrations in _both_ these cases. My claim is that if what I want to do set a range limit, then I don't _need_ pointers, I would rather have _just_ SET RANGE. The same goes for identify: it what I want to do is identify, I don't _need_ the full power (and complexity to optimize) as pointers give, I would rather have _just_ IDENTIFY. > [...] The SET RANGE > statement makes it more difficult to tell when references to array elements > overlap. Read the old proposal again. The SET RANGE statement _CAN'T_ cause array elements to overlap! The SET RANGE statement causes _no_ form of aliasing _AT_ALL_! All it does is limit the visible elements of a single array: REAL, RANGE :: A(100,100) ... SET RANGE (2:99,2:99) A ... The reference A(3,60) still refers to the _same_ element after the SET RANGE statement as it did before. The only differrence is that A(1,1), for example, is out of bounds; and A as a whole array is now conformable to a 98 by 98 array. The SET RANGE statement did _not_ rename, remap, overlay, or alias _any_ part of A with any other part of A or with any othe data object. > [...] > IF (P) THEN > IDENTIFY (X = A) > ELSE > IDENTIFY (X = B) > END IF > > X = Z > > was allowed. Thus, adding pointers does not make optimization harder than > the IDENTIFY statement would. However, pointers offer more functionality > than the IDENTITY statement. Nothing comes for free. The additional functionality of pointers _does_ make optimization harder (or impossible) in contexts where IDENTIFY would not. Consider an example similar to yours: IF (P) THEN IDENTIFY (X = A) ELSE IDENTIFY (X = B) END IF CALL SUB(X,Z) X=Z Is X aliased to Z in any way? With IDENTIFY the answer can be determined _locally_. In the above, the answer is NO. The subroutine call CAN'T alter the definition of X (it can alter the value _only_). If the alias were accomplished with pointers, however, the answer could _NOT_ have been locally determined. This is because pointer assignment CAN be done within the subroutine. Only interprocedural analysis can determine the possibility of aliasing if pointers are involved. As a result (since Fortran is separately compiled), the version with pointers would _always_ have to assume that aliasing _had_ occured.
jlg@lanl.gov (Jim Giles) (06/28/89)
From article <MCCALPIN.89Jun27112226@masig1.ocean.fsu.edu>, by mccalpin@masig1.ocean.fsu.edu (John D. McCalpin): > [...] > On the other hand, IDENTIFY clearly has the same sort of aliasing > problems as POINTER. I am not sure about ALIAS, but I seem to recall > that it was even more limited.... ALIAS and IDENTIFY are related. IDENTIFY does not have the _same_ sort of aliasing problems as pointer. This is because POINTERs can be reassigned during a subroutine call. You can't reIDENTIFY something in a subroutine call though. See my previous posting.
hallidayd@yvax.byu.edu (06/29/89)
In message <2773@elxsi.UUCP> Bob Corbett (corbett@beatnix.UUCP) makes the statements > Thus, adding pointers does not make optimization harder than >the IDENTIFY statement would. However, pointers offer more functionality >than the IDENTITY statement. The first statement has already been adressed (the ALIASing provided by the ALIAS/IDENTIFY pair cannot be reIDENTIFYed in a subroutine, while that provided by POINTERs can). The second statement, that POINTERs offer more functionality than the IDENTIFY is false if we are considering only the ALIASing of array sections (POINTERs do provide the added functionality of recursive data structures, which the ALIAS/IDANTIFY pair was never intended to do). There is no way for the POINTER syntax to ALIAS arbitrary, functionally related, array elements as can be acomplished with ALIAS/IDENTIFY---try ALIASing the diagonal of an array with the present proposed POINTER syntax, it can't be done (as at least one other poster has stated). _____________________________________ / David Halliday \ | | | Internet: hallidayd@yvax.byu.edu | | BITNET: hallidayd@byuvax | | Us Mail: BYU Physics Department | | 296 ESC | | Provo, UT 84602 | \_____________________________________/
corbett@beatnix.UUCP (Bob Corbett) (07/08/89)
-In article <664hallidayd@yvax.byu.edu> hallidayd@yvax.byu.edu writes:
->In message <2773@elxsi.UUCP> Bob Corbett (corbett@beatnix.UUCP) makes the
->statements
->> Thus, adding pointers does not make optimization harder than
->>the IDENTIFY statement would. However, pointers offer more functionality
->>than the IDENTITY statement.
->
->The first statement has already been adressed (the ALIASing provided by the
->ALIAS/IDENTIFY pair cannot be reIDENTIFYed in a subroutine, while that provided
->by POINTERs can). The second statement, that POINTERs offer more functionality
->than the IDENTIFY is false if we are considering only the ALIASing of array
->sections (POINTERs do provide the added functionality of recursive data
->structures, which the ALIAS/IDANTIFY pair was never intended to do). There is
->no way for the POINTER syntax to ALIAS arbitrary, functionally related, array
->elements as can be acomplished with ALIAS/IDENTIFY---try ALIASing the diagonal
->of an array with the present proposed POINTER syntax, it can't be done (as at
->least one other poster has stated).
I concede that if the functionality pointers provide beyond ALIAS/IDENTIFY
is used, it will make alias analysis harder, though not much harder. But
please note that if pointers are used to provide the functionality of
ALIAS/IDENTIFY, it does not make alias analysis noticeably harder. The
example of a procedure call modifying the association of a pointer can occur
only if the pointer is external or the pointer is passed as a pointer
argument. Neither case can arise when pointers are used to emulate
ALIAS/IDENTIFY. Thus, the added functionality of pointers costs only
when it is used.
I had missed the fact that pointers cannot be used to ALIAS the diagonal
of an array. I regard this lack as a serious problem. Clearly, X3J3 should
extend the notation for array sections to add this capability.
Yours very truly,
Bob Corbett
uunet!elxsi!corbett
ucbvax!sun!elxsi!corbett