Xref: utzoo comp.arch:20160 comp.lang.misc:6483 Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!mcsun!ukc!dcl-cs!aber-cs!athene!pcg From: pcg@cs.aber.ac.uk (Piercarlo Grandi) Newsgroups: comp.arch,comp.lang.misc Subject: Re: Register Count Message-ID: Date: 12 Jan 91 15:23:11 GMT References: <11538@pt.cs.cmu.edu> Sender: cho@aber-cs.UUCP Followup-To: comp.lang.misc Organization: Coleg Prifysgol Cymru Lines: 185 Nntp-Posting-Host: teachk In-reply-to: pcg@cs.aber.ac.uk's message of 10 Jan 91 19:44:01 GMT On 10 Jan 91 19:44:01 GMT, pcg@cs.aber.ac.uk (myself) said: [ ... how to reduce a multiple assignment to one or more sequences of signle assignments ... ] pcg> So that nobody asks me for the draft of the paper, here is an pcg> outline of the algorithm: build two boolean matrixes, LR for pcg> L-to-R(-to-L) dependencies, and LL for L-to-L dependencies, an pcg> element is true if there is a dependency[4] betwen the two pcg> expressions. pcg> [4] The usual wise guys will remark that this is undecidable. In pcg> practice any weaker predicate will do, and will generate, for the pcg> simple expressions likely to be found in practice, good results. Some of the usual wise guys have written to me to remark that aliasing may pose a problem. I had clearly hinted that this need not so, but it seems that discussing the alising issue throws up more interesting language and code generation issues, so here is a followup posting. Followups to this are redirected to comp.lang.misc, because the system architecture content is not that great here. There are *two* types of aliasing we might be interested in. Let's see a few examples: a, a := 1, 1; CO semantics well defined CO a, a := 2, 3; CO nondeterministic or illegal? CO a, a := b, c; CO either of the above CO This illustrates *value* aliasing. The first example is noncontroversial; the second is, because we have a choice of either faulting it as ambiguous, or of accepting a non deterministic result (my preference, but the compiler should issue a warning); the third is equivalent to either, depending on whether "b = c". a[i], a[j] := a[j], a[i]; a[i], a[j] := a[m], a[n]; This illustrates *lvalue* or reference aliasing. But the semantics of the first line are obviously well defined, for when "i = j" it is an identity assignment, and otherwise it is a swap. The second line is harder, as it involves *both* value, as maybe "i = j" but "a[m] /= a[n]", and lvalue (if "j = m" or "i = n", ...) aliasing. Three "solutions" are possible: 1) Using a suitably weak definition of the dependency predicate guarantees that all these cases are handled correctly, at the price of generating some temporaries that are unnecessary when aliasing does not occur dynamically. For example the examples above can be implemented as a, a := 1, 1; a := 1; a, a := 2, 3; a := 3; a, a := b, c; a := b; a[i], a[j] := a[j], a[i]; R0 := a[j]; a[j] := a[i]; a[i] := R0; a[i], a[j] := a[m], a[n]; R0 := a[m]; R1 := a[n]; a[i] := R0; a[j] := R1; 2) If the programmer knows something that cannot be possibly deduced by the code that implements the dependency predicate, such as aliasing information in languages like C, there is always the option of manually expanding the multiple assignment as single assignments. For example the programmer may _know_ that "j /= m" and thus rewrite: a[i], a[j] := a[m], a[n]; a[j] := a[n]; a[i] := a[m]; If the programmer knows that "i /= n" the other rewriting becomes possible: a[i], a[j] := a[m], a[n]; a[i] := a[m]; a[j] := a[n]; 3) A far more interesting solution is to add some cleverness to the compiler. I mean, real cleverness, not like current "optimizers". The idea is that compilers are symbolic reduction engines in the domain of code sequences -- let's exploit that and have the dependency predicate return not truth values but formulas with free variables. The dependency matrixes would then imply a family of actual dependency matrixes, and code could be generated for each. This we could call "Schroedinger's cat code generation". For example, the (pessimistic) dependency matrixes for a[i], a[j] := a[m], a[n]; would be LL 0 0 LR 0 1 0 0 1 0 while the symbolic/feline ones would be LL 0 0 LR 0 (i = n) 0 0 (j = m) 0 By exploding the symbolic LR matrix for the possible values of the formulas in it, we could have the code generator generate code for: a[i], a[j] := a[m], a[n]; as in: IF i = n THEN CO LR matrix collapses to: ((0,1),(j=m,0)) CO IF j = m THEN CO equivalent to: a[i], a[j] := a[j], a[i]; LR matrix is: ((0,1),(1,0)) CO R0 := a[j]; a[j] := a[i]; a[i] := R0 ELSE CO equivalent to: a[i], a[j] := a[m], a[i]; LR matrix is: ((0,1),(0,0)) CO a[j] := a[i]; a[i] := a[m]; FI ELSE C as above, mutatis mutandis C FI Note that by going really far, we could even turn "a := b" into something like "(a /= b | a := b)", which may even (improbably) make sense for some implementations of some architectures. Now some comments. Alternative 1) above is IMNHO perfectly adequate. I do expect that the vast majority of cases will involve no potential aliasing, so no possibly excessive temporaries will be used. And even when they are used, they will probably make little difference to runtime. Alternative 2) above will be used when speed is absolutely critical and the programmer wants to invest the mental effort of second guessing the code generator. Hardly ever necessary, I hope. Note that the frequent advice to C programmers to offer greater opportunities to the optimizers, in the (fortunate) absence of C ways to inform the optimizer of aliasing hazards, by using explicit temporaries, is equivalent to this alternative. Alternative 3) is intriguing, because it implies dynamic conditional compilation. For example the code sequences relative to aliasing, if it is expected to be rare, could be offlined to some remote code section, to improve locality. More than a hint of trace scheduling here, of course. Interesting avenues of research, only a few already explored (trace scheduling, lazy or speculative execution, on the fly code generation for BITBLT, the concept of a supercompiler, ...), would open considering interpretation and compiling as an experimental science, and execution and compilation as performing or setting up experiments to collapse the state vector. Deep thinking, man. ================================================================ Now a disclaimer that I feel required to make, after some comments on the "Summary:" line for the previous posting: All the research underpinning this and the previous postings has no relationship whatsoever to the research of the University College of Wales. The research that I discuss here is *entirely* the result of my own work, using my own funds, on my own time; its contents is my responsibility alone, and should not reflect on any assessment of the research or reputation of the University College of Wales. In particular the investigation of multiple assignment was done years before I had even heard of the University College of Wales existence. If the above disclaimer were not true, I would have had to seek written permission from my Head of Department before posting the multiple asignment technology, and it could have been (probably IMNHO) refused, as it would have been my contractual duty to point out that it was patentable subject matter susceptible of commercial exploitation. I wish to thank the University College of Wales for their generous permission to use without payment their News connection to discuss in this forum my own personal research (if any :->). -- Piercarlo Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.uk