Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Path: utzoo!mnetor!seismo!mcvax!ukc!icdoc!cl-jenny!am From: am@cl.cam.ac.uk (Alan Mycroft) Newsgroups: comp.lang.c Subject: Re: Legal re-arrangement rules. Why they seem inconsistent. Message-ID: <683@jenny.cl.cam.ac.uk> Date: Wed, 18-Mar-87 05:48:09 EST Article-I.D.: jenny.683 Posted: Wed Mar 18 05:48:09 1987 Date-Received: Tue, 24-Mar-87 01:15:16 EST References: <844@wanginst.EDU> <4211@utcsri.UUCP> <609@viper.UUCP> <4315@utcsri.UUCP> <681@jenny.cl.cam.ac.uk> <4352@utcsri.UUCP> Reply-To: am@cl.cam.ac.uk (Alan Mycroft) Organization: U of Cambridge Comp Lab, UK Lines: 89 Keywords: associative commutative operations. Summary: there seems a common view that ANSI will sanction 'the sort of things that pdp-11/bsd/pcc compilers always did'. This is not necessarily the case. Anyone who believes the draft forbids something that (s)he would like to have a compiler do ought to read the draft and comment (I believe there is a second public review period). In article <4352@utcsri.UUCP> greg@utcsri.UUCP (Gregory Smith) writes: >In article <681@jenny.cl.cam.ac.uk> am@cl.cam.ac.uk (Alan Mycroft) writes: >>Summary: The re-assocation rules are at best arbitrary, often not >>identities and do not allow rearrangement that many users expect to be >>allowed. >>In article <4315@utcsri.UUCP> you [Greg] write: >>>I want my compiler to be free to change (i+3)*4+6 to i*4+18. >>I'm afraid neither ANSI nor K&R sanction this particular transformation. >>They allow re-arrangement of associative operators. Nothing is said about >>your wish that mathematical 'distributive' laws are applicable. >>Of course, if signed overflow is ignored ... 'as if' principle. If anyone wants the spec. to say this they had better lobby the committee. >>>It allows constants to be folded to the end (a+2)+(b+9)+4 = (a+b)+15. >>1.I disagree in principle that ANSI and K&R ought to allow this transformation >>if a & b are floating. Consider a=1e30, b=-1e30. Then the transformation is > >Agreed. I never meant to imply that any of this should be done for >floating point operations. BUT THE DRAFT (AND K&R) EXPLICITLY SAY THIS *CAN* BE DONE. >>2.Anyway, even if we concede that the spec. will/does allow this, we find that >>it can re-arrange ch+(-'a')+'A' but not the more natural ch-'a'+'A'. >>(Nothing is said about re-arranging thing with '-' in -- it is not assocative >>or commutative). > >A compiler may change ex-k1 to ex+k2 with a suitable change in the constant >k. Let us consider the draft spec. (or K&R) carefully. Yes, ex-k1 can often be changed to ex+k2 (muttering darkly about MIN_INT). On the other hand the compiler is NOT then at liberty to re-arrange ex-k1+k3 to ex+(k2+k3) by the rules (but again possibly by appeal to the 'as if' principle if overflow is ignored). >>>Multiple constants in running sums tend to pop up (1) from macro >>>expansions (2) in expressions like (p+3)->foo.y[i-1].abc ( after the >>>semantics have been applied ). >>But there is only one '+' in here so the compiler can't re-arrange it. >>(Ansi is unclear whether the '+' introduced by e1[e2] can be re-arranged - >>probably not since + on pointers is NOT assocative for type reasons). >>Certainly the + introduced by component selection is not re-arrangeable. > >But these optimizations are normally done after the expression has been >converted to a pure calculation, when the compiler has 'forgotten' >where things came from. >.... If you want to leglisate against such an optimization, >you better have a darn good reason. Groan. Yes, I know that is how some compilers work. Our compiler does NOT 'forget' where an expression came from. (Aside: it even justifies the oddity in Oct-86 ANSI draft that char *x = (1 ? 2-1-1 : 6) is valid, but not char *x = 1;) But the draft spec. really does not sanction this change. *I* do not wish to ban your transformation, but the spec. does. Maybe we both can agree that the draft could(should?) be changed here to allow this? >Why not reduce the whole expression to a homogenous tree and optimize >it 'wholesale' after the semantics have been applied? Fine - why don't you put it to ANSI? >>But the points I am trying to make are that ANSI/K&R do no allow them and >>that the re-arrangement rules seem inherently ill-thought out. >I can't say that K&R forbids this. A strict reading of section 7 in >the appendix tells me that they sort of maybe do forbid it. But the >version 7 compiler, written by K&R, does these transformations. >A language defined by its compilers. **** NO - it is then forbidden to build an optimising compiler **** or compiler for a new machine. >My attitude is a defensive-programming one: I probably believe these rules >to be rather more fuzzy and lenient than they really are. The whole point of an ANSI standard for C is to define a set of rules (a contract) minimal for programmers and maximal for implementors. This means that limits have to be placed on the re-arrangements of programs. (Hence the rules on sequence points and volatile variables). If a compiler oversteps the rules then it is not standard conforming. If a user oversteps the rules then his program may be conforming on one compiler, but not strictly conforming (i.e. portable). See ANSI rationale. My entry to this debate was building an optimising C compiler and discovering how many 'pcc always did this' optimisations were not sanctioned directly by the standard, and discovering that even simple desirable optimisation like re-arranging ch-'a'+'A' are not allowed (if ch is int).