gordan@maccs.UUCP (gordan) (04/29/88)
-In article <56@lakart.UUCP> dg@lakart.UUCP (David Goodenough) writes:
->So what does noalias do?
-
-Nothing. It has been removed from the proposed standard.
-Let's please save net bandwidth by dropping any further "noalias"
-discussion.
Before we consign noalias to the dustbin of history... a question.
In all the time noalias was discussed on comp.lang.c, just about no one
spoke up in favor of it. In the recent X3J11 meeting it was reportedly
voted down by well over the required (2/3 ?) majority.
And yet, it must have once gotten a similar majority in favor, not so
very long ago (January?).
So, like, who on X3J11 will admit to having voted for (or worse,
proposed) noalias in the first place? Why did it seem like a good idea
at the time, and what were the reasons for dropping it (apart from
universal opprobrium). Enquiring minds &c.
"Victory has a thousand fathers and defeat is an orphan"
-- JFK, after the Bay of Pigs
--
Gordan Palameta
uunet!mnetor!maccs!gordangwyn@brl-smoke.ARPA (Doug Gwyn ) (04/30/88)
In article <1164@maccs.UUCP> gordan@maccs.UUCP () writes: >So, like, who on X3J11 will admit to having voted for (or worse, >proposed) noalias in the first place? Why did it seem like a good idea >at the time, and what were the reasons for dropping it (apart from >universal opprobrium). Enquiring minds &c. Unofficially speaking... "noalias" was worked out by a special task force at the December X3J11 meeting (originally without that particular name, just as the concept) as a compromise position that could be supported by two opposed sides of the optimization vs. aliasing battle. On the first day of that meeting, in a non-binding "straw vote" it was decided to change the semantics of "const" (which admittedly were not all that clear) from meaning "readonly" to meaning "really constant", in fact to allocate the eventual "const noalias" semantics to just "const". AT&T and some others adamantly opposed this. The task force determined that really this was another instance of overloading semantics onto a keyword, and that there were three, not two, orthogonal qualifiers needed to cover all the useful cases via multiplexing of qualifiers. Thus the third qualifier, eventually named "noalias". In April, we basically had a choice between fixing "noalias" (we did fix "const"), removing "noalias" and making "const" mean what had been decided on December-Monday, or removing "noalias" and leaving "const" with its "readonly" meaning. The latter approach was adopted as the most acceptable at this stage, although the second approach might have been adopted had we not gone through the "noalias" detour. Certainly having Dennis Ritchie participating in the April-Monday discussion helped clarify the issues and shape our final decision. I think we will be able to support the latest position against further onslaughts, even though we have now left the optimizers without a handle for performing the optimizations they sought in standard-conforming C. Removing *all* qualifiers, as suggested in a public comment by Rob Pike, found little support and not even Dennis was asking for that.
scjones@sdrc.UUCP (Larry Jones) (04/30/88)
In article <1164@maccs.UUCP>, gordan@maccs.UUCP (gordan) writes: > In all the time noalias was discussed on comp.lang.c, just about no one > spoke up in favor of it. In the recent X3J11 meeting it was reportedly > voted down by well over the required (2/3 ?) majority. > > And yet, it must have once gotten a similar majority in favor, not so > very long ago (January?). December. > So, like, who on X3J11 will admit to having voted for (or worse, > proposed) noalias in the first place? Why did it seem like a good idea > at the time, and what were the reasons for dropping it (apart from > universal opprobrium). Enquiring minds &c. Well, being one of those fools who rush in where angels fear to tread, I will admit to having voted for noalias (before you start sending letter bombs, I also voted to remove it). How did noalias come to be? One of the committee's goals has been to define a language that will be broadly usefull. This has lead to all kinds of conflicting demands that have to be reconciled somehow. For instance, people using C for general programming want the compilers to optimize the heck out of everything so their programs run as fast as possible. People writing system software like memory mapped device drivers want no optimization at all. These conflicting demands eventually lead to the "volatile" keyword which turned out to be a double win -- the general types get the optimization they want and the system types get the control they want plus they get all of the optimizations for the parts of the code that aren't accessing hardware. One of the issues relating to optimization that the committee has wrestled with for a long time is the problem of aliasing. When you're trying to optimize generated code, it is, of course, necessary to make sure that the resulting code still gets the "right answer". To do that, you need to be very careful to keep track of exactly how and where the value of an expression can be changed. This is particularly important when you have some type of parallel processing since having multiple CPUs makes the benefits of changing the order in which things occur much greater since many things can be going on at the same time. Unfortunately, keeping track of what's going on in a C program is next to impossible. Most of the problems are caused by pointers -- although some pointers point are the only way to get to the object they point to, most pointers are aliases for objects that can be accessed in other ways as well. By doing global flow analysis of the entire program it is (theoretically) possible to figure out all the things that a pointer can possibly point to but this is extremely difficult. It is impossible given that C allows separate compilation since this means that the compiler can't look at the whole program. Traditionally, this has been dealt with by assuming that anything that has had its address taken or could have had its address taken (e.g. globals) is changed any time something is changed through a pointer. Similarly, changing any value through a pointer is assumed to change the values pointed to by all pointers. Although these pessimistic assumptions are quite safe, they prevent most optimizations. For instance, most users of vector processors are surprised that the following function: void addvec(double a[], double b[], double c[], int n) { int i; for (i = 0; i < n; i++) a[i] = b[i] + c[i]; } does not result in a single vector addition (especially since writing the "same" function in FORTRAN does). Actually, "angry" is probably a better term that "surprised" in this case. The reason for this is, of course, that in C there is nothing wrong with calling this function like: addvec(a+1, a, a+1, sizeof a / sizeof a[0] - 1); which sums the vector into its last element. This is invalid in FORTRAN which is why the FORTRAN version can vectorize but the C version can't. This turns out to be a major issue for every vendor with parallel hardware. Lest you think that this is a fairly esoteric group, just remember that every IBM PC with a math coprocessor is a parallel machine (although existing software doesn't make much use of the capability yet). Also note that this is not a specsmanship battle either -- users buy parallel machines to get performance and they get very hostile when they don't get it. Minor details like their language of choice not being suited to vectorization are not of interest. This is the atmosphere that existed at the December meeting. Many of the people with compilers for parallel machines were saying that the lack of a method for specifying aliasing was sufficient reason for a "no" vote on the standard and proposed a number of possible solutions. One was to change the meaning of parameters declared as arrays to be pointers to things that don't overlap each other. This was accepted fairly well except that there was concern that it might break existing code which uses array and pointer notation interchangably. A possible solution to this objection was to only assign the new meaning in prototypes, but that introduced an incompatibility between declarations in and out of prototypes that many people objected to. Other interesting variations on syntax were introduced and rejected for various reasons. Also, it was pointed out that this only solved the problem with function arguments, it did not solve the general problem. None of the proposals got the necessary 2/3 vote for adoption, but a clear majority of the committee was interested in finding a solution to the problem. Finally, the people who were most interested in the issue agreed to form a working group to try to concoct a solution which would be acceptable to the majority of the committee. On Friday, the working group presented the solution they had arrived at -- "noalias". What was presented was only the concept, the exact wording still had to be worked out. It seemed to be everything anyone could want: the default was that everything was aliased so no existing code would be broken, you could specify it on parameters to get the non-overlapping parameters (which all the library functions except memmove required - now we could specify the restriction in the prototypes instead of having a disclaimer in English!), and you could use it on pointers and objects just like "const" and "volatile" to solve the general problem. What more could anyone want? Well, there were a number of concerns, of course. We hadn't much time to look at it and think about the possible consequences. We were trying to get the draft out for the second (and last) public review. We didn't have the exact wording. Interestingly, noone brought up the problem that finally caused its downfall - it was too hard for mere mortals to get right; particularly in large programs and during maintenance. Guess we were all wearing our wizard hats when we should have been wearing our manager hats. Finally, since we had all agreed that we wanted to solve the problem and this looked like a good solution, we agreed to add it to the draft. If it really was a good solution (and it seemed like it was) then it would have been reviewed and, even if the words weren't quite right, we could just change them editorially without having to have another public review. Of course, having all those other people review it rather that just us would point out any problems we may have missed (did I just hear some ominous music in the background?). After that, you know what happened. It got mentioned here and in other forums as well. The reactionaries immediately flamed it, the rational expressed concern but reserved judgement pending the exact wording. The exact wording came and was judged incomprehensible. The rational, having carefully considered all the ramifications, denounced it. Dennis Ritchie, father of C, denounced it. Henry Spencer put Dennins's denouncement into his signature. Many people made quite persuasive, rational, arguments that it was not "a good thing". April came and the committee, burnt, blackened, covered with soot and smelling of smoke, reconvened. Although only a very few of the committee members are foolish enough to post things here and expose themselves to the direct ire of the net, many of them do read it. The rational arguments won. Although Dennis showed up in person for the first time in the history of the committee, most of the members had already made up their minds and noalias was summarily removed. There was a brief flurry of activity to try to fall back to one of the other proposals (most notably the array arguments may not overlap proposal), the committee was so gun-shy that even an attempt to simply declare array args an obsolescent feature so it could be changed in a future standard was defeated. And that's the way it was (at least that's the way I remember it, which may or may not have much to do with reality). ---- Larry Jones UUCP: ...!sdrc!scjones SDRC AT&T: (513) 576-2070 2000 Eastman Dr. BIX: ltl Milford, OH 45150 "When all else fails, read the directions."
norvell@utcsri.UUCP (Theodore Stevens Norvell) (05/01/88)
In article <1164@maccs.UUCP> gordan@maccs.UUCP () writes: >Before we consign noalias to the dustbin of history... a question. > >In all the time noalias was discussed on comp.lang.c, just about no one >spoke up in favor of it. In the recent X3J11 meeting it was reportedly >voted down by well over the required (2/3 ?) majority. > >And yet, it must have once gotten a similar majority in favor, not so >very long ago (January?). > >So, like, who on X3J11 will admit to having voted for (or worse, >proposed) noalias in the first place? Why did it seem like a good idea >at the time, and what were the reasons for dropping it (apart from >universal opprobrium). Enquiring minds &c. > Noalias was voted in last December. As I recall, only 2 organizations voted against it. I don't trust my memory well enough to name them. It was invented as an alternative to a rule proposed by Cray Research that arguments to parameters which were pointers to const qualified types could not point to aliased data (or something awful like that). The reason it seemed like a good idea at the time is that it was a good idea at the time. It is a clean way to convey useful information to the compiler -- information that the compiler can often not derive itself (short of inter-compilation-unit flow analysis). This information is required to ensure that certain optimizations are safe in the presence of pointer dereferences -- optimizations which include: common subexpression elimination, instruction scheduling, loop invariant removal, redundant instruction elimination, vectorization, and lots of others. Unlike other innovations of the ansi committee and the proposal from Cray, it would have broken no existing code (except that which used the word "noalias" as an identifier); unlike the idea of using pragma it would have been portable. I hope that sensible vendors will agree on a semi-standard pragma for it. As to why it was dropped, I do not know. Perhaps companies which did not offer optimizing compilers were scared that those that who did would suddenly start producing code that ran twice as fast for programs using noalias. Perhaps the committee was awed by Ritchie's oration. Perhaps it can be blamed on the Russians. Perhaps someone who knows could say. As an aside: One idea that has been circulating about noalias is particularly silly. That is that the purpose of noalias is to make the life of compiler writers easy. This is bunk. The more you add to a language the more special cases and interactions the compiler should handle in order to get the best code possible. The purpose of noalias is to allow the user to get the best code possible in a machine independent way by allowing the compiler to optimize in the 99% of the cases where the optimization is safe. Another aside: Noalias had some drawbacks. After the tremendous number of articles pointing this out, I don't feel compelled to repeat them. That would really be kicking the thing when its down. Theodore Norvell BITNET,CSNET: norvell@csri.toronto.edu CDNNET: norvell@csri.toronto.cdn UUCP: {alegra,cornell,decvax,linus,utzoo}!utcsri!norvell
walter@garth.UUCP (Walter Bays) (05/04/88)
In article <5995@utcsri.UUCP> norvell@utcsri.UUCP (Theodore Stevens Norvell) writes: >[Noalias] would have broken no existing code (except >that which used the word "noalias" as an identifier); unlike the >idea of using pragma it would have been portable. I hope that >sensible vendors will agree on a semi-standard pragma for it. How about the noalias supporters on the committee proposing a pragma here on the net? Or simply announcing what they're going to do? Users can only be hurt if we all go off in dozens of incompatible directions. -- ------------------------------------------------------------------------------ Any similarities between my opinions and those of the person who signs my paychecks is purely coincidental. E-Mail route: ...!pyramid!garth!walter USPS: Intergraph APD, 2400 Geng Road, Palo Alto, California 94303 Phone: (415) 852-2384 ------------------------------------------------------------------------------
mrd@sun.mcs.clarkson.edu (Michael R. DeCorte) (05/04/88)
In article <270@sdrc.UUCP> scjones@sdrc.UUCP (Larry Jones) writes:
<massive article deleted>
O.K. Now that I know how noalias came and went I have this sense of
dissatisfaction. I NEED something that will allow me to write a C
compiler that can vectorize and concurentize code. What should I do?
Tell my boss that he isn't going to get the compiler and tell everyone
to should stop hacking C and start hacking Fortran (yuck!)? Will
there be anything to resolve this problem? If there isn't I have only
one option, implement noalias. It is more standard than anything else
running about. Please don't take this as a flame, but a very
concerned question expressing a need for a solution that it is not
possible for me to solve as I am not a standard forming committee.
thankyougwyn@brl-smoke.ARPA (Doug Gwyn ) (05/05/88)
In article <871@sun.mcs.clarkson.edu> mrd@sun.mcs.clarkson.edu (Michael R. DeCorte) writes: >I NEED something that will allow me to write a C >compiler that can vectorize and concurentize code. What should I do? The first thing you need to realize is that C has always been capable of aliasing objects via pointers, and it has been (tacitly) assumed that all references to aliased objects will access the same thing, not distinct cached copies of the object. Thus, C has never permitted optimization along the lines that people expect for Fortran. To obtain such optimization it is incumbent on the programmer to take some special steps to flag those cases that can be optimized, unless his system provides really good global flow analysis across multiple translation units (source files). "noalias" is not the only possible mechanism for this; a less ambitious one would be a vendor-specific hook such as a compiler option, a magic /*comment*/, or even a __keyword that flags places where aliasing can safely be ignored. The obvious such place is at function interfaces, since it is extremely poor style for a function to be required to access the same object both directly as an extern and indirectly via a pointer parameter. It has been suggested that [] formal parameters have this special meaning, although they can't by default in a Standard-conforming implementation (you would have to enable the special treatment by a compiler option). There is some disagreement whether #pragma can be used to change such semantics. Both the Redactor (draft Standard editor) and I think not, but I've heard other X3J11 members voice contrary opinions. You should discuss this with your compiler vendor. First ask for good global data access analysis (although it's unlikely that you'll get it), then ask for a compiler flag for special treatment of [] parameters, then ask for a __keyword.
henry@utzoo.uucp (Henry Spencer) (05/06/88)
> ... Now that I know how noalias came and went I have this sense of > dissatisfaction. I NEED something that will allow me to write a C > compiler that can vectorize and concurentize code. What should I do? You are probably going to end up using #pragma. If you investigate the requirements in detail, you may well find that you end up having several different directives for controlling/enabling such optimizations; one technical objection to noalias was that it was too simplistic. > Will there be anything to resolve this problem? Almost certainly not from X3J11. The problem simply is not sufficiently well understood to try to standardize a solution (my opinion), and it is definitely too late in the C standardization process to try to do so now (almost everybody's opinion). > If there isn't I have only > one option, implement noalias... I would say that's a mistake, if only because nobody has ever been able to produce a precise and coherent definition of what noalias *did*. The right thing to do, I think, is to (a) plan on using #pragma, (b) start designing your compiler, and (c) let your #pragmas evolve as your compiler design becomes clear. I think it's a mistake to try to solve the problem in isolation from the implementation. Language design is harder than it looks. -- NASA is to spaceflight as | Henry Spencer @ U of Toronto Zoology the Post Office is to mail. | {ihnp4,decvax,uunet!mnetor}!utzoo!henry
throopw@xyzzy.UUCP (Wayne A. Throop) (05/06/88)
> gwyn@brl-smoke.ARPA (Doug Gwyn ) > we have now left the optimizers without a handle for > performing the optimizations they sought in standard-conforming C. Well, granted, no keyword handle, but I don't see why the optimizer freeks can't use sometype *var; #pragma noalias *var or #pragma noalias var to do the same thing the keyword was for, but without everybody having to worry about it until they had built up "existing practice" with the idea. -- Mrs. Robinson, you're trying to seduce me. Aren't you? --- Dustin Hoffman in "The Graduate" -- Wayne Throop <the-known-world>!mcnc!rti!xyzzy!throopw
karl@haddock.ISC.COM (Karl Heuer) (05/12/88)
In article <7832@brl-smoke.ARPA> gwyn@brl.arpa (Doug Gwyn (VLD/VMB) <gwyn>) writes: >[If you need noalias-style optimizations for vectorization] >You should discuss this with your compiler vendor. First ask for good >global data access analysis (although it's unlikely that you'll get it), >then ask for a compiler flag for special treatment of [] parameters, then >ask for a __keyword. Please, let's not have "int a[]" mean "int * noalias a" in formal parameters, even as a non-conforming extension. Logically, what that declaration should mean is "array of int", with the whole array passed by value%. Ask your vendor for a magic keyword, a pragma, a new flavor of assert(), or whatever, but let's reserve array notation for what it should have meant in the first place. Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint Followups to comp.std.c. ________ % Although to be meaningful, it would need an explicit size.
terry@wsccs.UUCP (Every system needs one) (05/14/88)
In article <5995@utcsri.UUCP>, norvell@utcsri.UUCP (Theodore Stevens Norvell) writes: | As an aside: One idea that has been circulating about noalias is | particularly silly. That is that the purpose of noalias is to | make the life of compiler writers easy. This is bunk. The more | you add to a language the more special cases and interactions the | compiler should handle in order to get the best code possible. | The purpose of noalias is to allow the user to get the best code | possible in a machine independent way by allowing the compiler | to optimize in the 99% of the cases where the optimization is | safe. This is not bunk, unless the optimizers are not considered as part of the compiler. If an optimizer IS part of the compiler, as is suggested by "optimizing compiler", then anything that makes writing the optimizer easier makes writing the compiler easier. The same applies to making volitile a keyword rather than a #pragma. terry@wsccs
bill@proxftl.UUCP (T. William Wells) (05/20/88)
Noalias is bad for a number of reasons, which I do not care to discuss; however, you, terry@wsccs, seem to have an exaggerated notion of what is possible for an optimizer to do. Noalias solves a problem which CANNOT be solved by an optimizer (yes, this is another problem which can be shown to be equivalent to a halting problem). Please, before you flame others for supporting things like this with comments like: "let the optimizer do it", why don't you find out whether it is actually possible for the compiler to do it? (Another unsolvable problem: when will the programmer stop flaming? :-)
dsill@nswc-oas.arpa (Dave Sill) (05/24/88)
From: "T. William Wells" <bill@proxftl.uucp> >Noalias is bad for a number of reasons, which I do not care to >discuss; however, you, terry@wsccs, seem to have an exaggerated >notion of what is possible for an optimizer to do. Noalias >solves a problem which CANNOT be solved by an optimizer (yes, >this is another problem which can be shown to be equivalent to a >halting problem). That's a new one on me. I'd like to see that reduction. However, even if the "noalias", or value caching, problem is unsolvable in general, that does not mean that an optimizer can never determine when it is safe to cache. >Please, before you flame others for supporting >things like this with comments like: "let the optimizer do it", >why don't you find out whether it is actually possible for the >compiler to do it? You are implying that programmers can solve unsolvable problems but that programs cannot, which is simply not true. The algorithm the programmer applies to determine when "noalias" can be used could be used by an optimizer. If this caching algorithm requires information not available to the optimizer, such as the ranges of all pointers (which may be limited by assumptions about the input to the program), then it's not safe. What happens when the input assumptions change? ========= The opinions expressed above are mine. "We must remove the TV-induced stupor that lies like a fog across the land." -- Ted Nelson
karl@haddock.ISC.COM (Karl Heuer) (05/25/88)
In article <14522@brl-adm.ARPA> dsill@nswc-oas.arpa (Dave Sill) writes: >[<bill@proxftl.uucp> (T. William Wells) says that the general aliasing >problem is unsolvable] > >You are implying that programmers can solve unsolvable problems but that >programs cannot, which is simply not true. The algorithm the programmer >applies to determine when "noalias" can be used could be used by an >optimizer. The programmer has more information. In hand-compiling the memcpy routine, I can look at the functional specification and know that it will never be legally called with overlapping arrays. The corresponding way for the compiler to have this information is via a keyword or #pragma or equivalent which is attached to the memcpy source code. Karl W. Z. Heuer (ima!haddock!karl or karl@haddock.isc.com), The Walking Lint
peter@athena.mit.edu (Peter J Desnoyers) (05/26/88)
In article <14522@brl-adm.ARPA> dsill@nswc-oas.arpa (Dave Sill) writes: >From: "T. William Wells" <bill@proxftl.uucp> >>Noalias >>solves a problem which CANNOT be solved by an optimizer (yes, >>this is another problem which can be shown to be equivalent to a >>halting problem). > >That's a new one on me. I'd like to see that reduction. Try add_vector( foo(x), bar(y), n). It looks uncommonly like the halting problem to me. >You are implying that programmers can solve unsolvable problems but >that programs cannot, which is simply not true. The algorithm the >programmer applies to determine when "noalias" can be used could be >used by an optimizer. You forget that programmers use often faulty and heuristic algorithms, and then debug their code. A compiler that generates bugs as often as I do (or any other programmer) would be worthless. Not only that, programmers do not use an algorithm to determine if a variable is noalias/volatile/whatever. They use coding practices to generate code that does not disobey such constraints. Then they debug their code to remove any unintentional aliasing or whatever. These are both procedures far out of the domain of any compiler. Peter Desnoyers peter@athena.mit.edu
turner@sdti.UUCP (Prescott K. Turner) (05/27/88)
In article <14522@brl-adm.ARPA> dsill@nswc-oas.arpa (Dave Sill) writes: >From: "T. William Wells" <bill@proxftl.uucp> >>Noalias solves a problem which CANNOT be solved by an optimizer (yes, >>this is another problem which can be shown to be equivalent to a >>halting problem). >That's a new one on me. I'd like to see that reduction. Such a reduction should be no surprise. >However, even if the "noalias", or value caching, problem is unsolvable in >general, that does not mean that an optimizer can never determine when >it is safe to cache. Yes, exactly. >You are implying that programmers can solve unsolvable problems but >that programs cannot, which is simply not true. The algorithm the >programmer applies to determine when "noalias" can be used could be >used by an optimizer. Your argument has some validity, but from a practical point of view, a compiler has no hope of determining all that the programmer knows about the program. The programmer does not have to apply an algorithm that determines where "noalias" can be used based on just the source code -- many design ideas and properties of the program are available to guide the programmer's verification that "noalias" is used correctly. By comparison, the compiler would have to start by proving all relevant properties of the program. >If this caching algorithm requires information >not available to the optimizer, such as the ranges of all pointers >(which may be limited by assumptions about the input to the program), >then it's not safe. What happens when the input assumptions change? OK, an optimizer has the potential to make use of all "safe" assumptions. But what real-life optimizer is going to make all the right assumptions about what happens when a program calls one of the standard library functions? The programmer has an advantage. There is a real need which "noalias" attempted to satisfy. Though as an implementer I was relieved to see it go. -- Prescott K. Turner, Jr. Software Development Technologies, Inc. 375 Dutton Rd., Sudbury, MA 01776 USA (617) 443-5779 UUCP:genrad!mrst!sdti!turner
dsill@nswc-oas.arpa (Dave Sill) (06/04/88)
From: Peter J Desnoyers <peter@athena.mit.edu> >In article <14522@brl-adm.ARPA> dsill@nswc-oas.arpa (Dave Sill) writes: >>From: "T. William Wells" <bill@proxftl.uucp> >>>Noalias >>>solves a problem which CANNOT be solved by an optimizer (yes, >>>this is another problem which can be shown to be equivalent to a >>>halting problem). >> >>That's a new one on me. I'd like to see that reduction. > >Try add_vector( foo(x), bar(y), n). It looks uncommonly like the >halting problem to me. I had something a little more rigorous in mind. What do foo(), bar(), and add_vector() do *exactly*? What are x, y, and n? In what *exact* context is add_vector() called? Let me have all the information the compiler would have, at least. If your point is that, in general, we can't tell if two pointers overlap, then I'll concede that point. But the fact that a problem is unsolvable in general does not mean that the problem can never be solved. We can't expect a compiler to determine with 100% accuracy if aliasing is occurring, but we can expect a compiler to spot 90% of the cases where aliasing can't occur, and to optimize them accordingly. >>You are implying that programmers can solve unsolvable problems but >>that programs cannot, which is simply not true. The algorithm the >>programmer applies to determine when "noalias" can be used could be >>used by an optimizer. > >You forget that programmers use often faulty and heuristic algorithms, >and then debug their code. A compiler that generates bugs as often as >I do (or any other programmer) would be worthless. Oh, good methodology! Write buggy code but debug it thoroughly. My point is that if the compiler can't make an optimization safely, then the optimization is unsafe. My next sentence, which you didn't include, says: >> If this caching algorithm requires information >>not available to the optimizer, such as the ranges of all pointers >>(which may be limited by assumptions about the input to the program), >>then it's not safe. What happens when the input assumptions change? Well? Should we let programmers make assumptions that may or may not be true? I'd rather require such assumptions be made explicit using the "assert" macro, #pragmas, or some other mechanism, so that the compiler could make use of them for optimization and error checking. There's no reason we should be withholding information from the compiler. >Not only that, programmers do not use an algorithm to determine if a >variable is noalias/volatile/whatever. They use coding practices to >generate code that does not disobey such constraints. Then they debug >their code to remove any unintentional aliasing or whatever. These are >both procedures far out of the domain of any compiler. And thank your local deity for that. I really can't believe you'd advocate such an approach. Programmers who don't use some sort algorithm for determining the storage requirements for their data deserve what they get. Do you start out by declaring all variables in your programs as ints and fixing the syntax errors? How can you ever be confidant that code is correct? Aren't you always wondering if there might be just one more undiscovered bug? ========= The opinions expressed above are mine. "We must remove the TV-induced stupor that lies like a fog across the land." -- Ted Nelson
bill@proxftl.UUCP (T. William Wells) (06/14/88)
In article <14522@brl-adm.ARPA>, dsill@nswc-oas.arpa (Dave Sill) writes: > You are implying that programmers can solve unsolvable problems but > that programs cannot, which is simply not true. Actually, you should keep your referents straight. I might be implying that humans can solve problems that are unsolvable by COMPUTERS. The truth of that is a matter of conjecture. This of course ignores the fact that aliasing is a property of the DESIGN of the program, not just of the program itself. It is entirely possible to design a program which has some particular aliasing property which can't be found by inspecting the code. Consider this contrived example: scanf("%d %d", &i, &j); p = &a[i]; q = &a[j]; Can p and q point to the same object? In the general case, yes. However, the programmer might intend this to be in a system where the two numbers can never be the same. So, the noalias keyword would add information that is not present in the program.
dsill@nswc-oas.arpa (Dave Sill) (06/21/88)
Peter J Desnoyers <peter@athena.mit.edu> writes: >I realize that you may be able to come up with an >approximation that is computable, but note that [you] must never fail to >detect aliasing when it exists. Yes, this is my point exactly. And it's very similar to what Chris has been saying about `volatile'. I'd rather take a slight performance hit to avoid a zillion modifiers like `volatile' and `noalias' (who knows what will be next?) that can introduce subtle bugs and complicate the language. I'm willing to wait until we have compilers that can tell when aliasing is not possible or when volatility is not possible, and optimize accordingly. >I merely mean to point out that >most programmers accomplish, through judicious foresight (and by >avoiding gruesome code which the compiler is required to accept) tasks >which the compiler must accomplish through extensive or even >impossible checking. Herein lies the difference in our opinions. My philosophy is that anything that can be done by the compiler to make the programmer's job easier or anything that can be done better by the compiler should be done by the compiler. Why require all programmers to be concerned with aliasing/volatility/etc when, let's face it, they are so likely to either not bother with it, or, if they do, to do it wrong? Probably better than 90% of all C programmers don't even have a good grasp on the simple pointers of K&R C. I've seen too many people do "char *p; ... strcpy (p, foo);", without pointing p at something reasonable first, to have any degree of confidence in their use of something like `noalias'. Should we pander to the least common denominator? No, but neither should we introduce keywords aimed at the very small number of C programmers that would actually use them correctly, especially when their misuse by the masses would be inevitable. ========= The opinions expressed above are mine. "We must remove the TV-induced stupor that lies like a fog across the land." -- Ted Nelson
hutchson@convex.UUCP (06/23/88)
For a less contrived example: for (i=n; i; i--) a[i]=i; /* each number in (i:n) occurs once in a. */ shuffle(a); /* randomly or not--doesn't matter. */ ... Now, the programmer knows full well that i!=j implies a[i]!=a[j]. But try explaining that to your favorite optimizer. Better hope it understands second-order logic. If you really want a challenge, try letting it figure it out for itself. Remember that this property of a is not created, but is maintained, by "shuffle". Such code would be found somewhere in, say, a blackjack simulation. I suspect that properties of permutations of arrays might be useful in more productive programs also.
nevin1@ihlpf.ATT.COM (00704a-Liber) (06/24/88)
In article <16244@brl-adm.ARPA> dsill@nswc-oas.arpa (Dave Sill) writes: >Peter J Desnoyers <peter@athena.mit.edu> writes: >Yes, this is my point exactly. And it's very similar to what Chris >has been saying about `volatile'. I'd rather take a slight >performance hit to avoid a zillion modifiers like `volatile' and >`noalias' (who knows what will be next?) that can introduce subtle >bugs and complicate the language. I'm willing to wait until we have >compilers that can tell when aliasing is not possible or when >volatility is not possible, and optimize accordingly. I am also willing to take a slight performance hit for not adding 'noalias', but 'volatile' is a whole different story. The alternative to not adding volatile to the language is to assume that all variables are volatile unless they can be proven otherwise (such as non-static local variables which never have their address taken). This means most C statements cannot be optimized AT ALL (other than optimizations such as constant folding). >Herein lies the difference in our opinions. My philosophy is that >anything that can be done by the compiler to make the programmer's job >easier or anything that can be done better by the compiler should be >done by the compiler. I agree with you here. However, at this point in time, compilers can't determine volatility without being ultra-conservative. >Why require all programmers to be concerned >with aliasing/volatility/etc when, let's face it, they are so likely >to either not bother with it, or, if they do, to do it wrong? If you are using anything that is volatile (implicitly or explicitly) you have to worry about it and know what you are doing. >Should we pander to the least common denominator? No, but neither >should we introduce keywords aimed at the very small number of C >programmers that would actually use them correctly, especially when >their misuse by the masses would be inevitable. But if you don't add the keyword, you are pandering to the least common denominator. I would rather have C assume that all variables are not volatile unless otherwise stated (an assumption that most people make when writing code) and get the performance gains than to take the conservative view and have lots of non-conforming compilers around to produce production-quality code. -- _ __ NEVIN J. LIBER ..!ihnp4!ihlpf!nevin1 (312) 510-6194 ' ) ) You are in a maze of twisting little / / _ , __o ____ email paths, all different. / (_</_\/ <__/ / <_ These are solely MY opinions, not AT&T's, blah blah blah