HDTenEightyP/NetNews huggingface dataset:
From: preston@dawn.cs.rice.edu (Preston Briggs)
Subject: Re: question on control dependence
Reply-To: preston@dawn.cs.rice.edu (Preston Briggs)
Organization: Rice University, Houston
Date: Tue, 15 Dec 1992 18:18:33 GMT
Keywords: design

mcconnel@newta1.cs.uiuc.edu writes:
>I've come up with a simple algorithm for computing control dependences, ...

This looks correct and I've never seen it presented before.  However, you
need to consider the case where a node has more than two successors.
These occur in most languages and have to be handled somehow. 

It looks like the correct solution for a node X with 3 successors, say A,
B, and C, would be

	CD(X) = (P(A) ^ (P(B) | P(C)))
	      | (P(B) ^ (P(A) | P(C)))
	      | (P(C) ^ (P(A) | P(B)))

The general form appears to be expensive.
	
>To me this algorithm seems much more intuitive and easier to program
>than the control-dependence algorithms in [1] and [2], since those
>algorithms are based on the post-dominator tree, which is more
>complicated to compute than P(X), and less suitable for computing
>control dependences.

It's more complex but much more efficient to use Lengauer and Tarjan's
approach to compute the dominator tree (versus the ordinary data-flow
solution given in step 1).

  title="A Fast Algorithm for Finding Dominators in a Flowgraph",
  author="Thomas Lengauer and Robert Endre Tarjan",
  journal=toplas,
  year=1979,
  month=jul,
  volume=1,
  number=1,
  pages="121--141"

The primary attraction (in my mind) of Cytron, et al. is for the efficient
computation of SSA; control dependence is just a fortuitous side effect
that I never use (though plenty of other people do).  Furthermore, I find
plenty of uses for the dominator tree, so the effort spent implementing
the efficient version is repaid many times.

Preston Briggs
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: cliffc@rice.edu (Cliff Click)
Newsgroups: comp.compilers
Subject: Re: question on control dependence
Keywords: optimize
Date: 15 Dec 92 16:24:51 GMT
Reply-To: cliffc@rice.edu (Cliff Click)
Organization: Center for Research on Parallel Computations

mcconnel@newta1.cs.uiuc.edu writes:

> I've come up with a simple algorithm for computing control dependences,
> and I was wondering if it was already known; I haven't seen it in the
> literature.  My algorithm uses straightforward data flow analysis, and
> works like so:

I am not the world's most knowledgeable dataflow expert, so Caveat Emptor!
With the disclaimer out of the way, here goes:

1) Your MEET operator is set intersection ("&").
2) Your transfer function for node Z is: f(x) = Z | x.
   (The "x" here is the MEET over the inputs.)
3) Your problem is 1-bounded; a single pass over the graph is sufficient.
4) Your problem requires O(N) bit-vectors, or
   O(N^2) COMMON CASE but with a small constant.

5) The authors in Cytron et al. claim O(N) in practice, although they admit
   to O(N^2) in the worst case.  Their algorithm will surely run with a 
   larger constant than yours.  I have implemented a variation of [2]
   and seen it run "fast enough" for my research compiler.

6) You don't say how to handle indirect jumps. 
   Real compilers gotta deal with this case.

7) With all that said, your algorithm is intuitive to me.


> My question is, has this algorithm been proposed before?  
> (It seems too simple not to have been.)

I've not seen it before.

Cliff
cliffc@cs.rice.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: zell@curtiss.SEAS.UCLA.EDU (Adam W. Zell)
Subject: DFA
Reply-To: zell@curtiss.SEAS.UCLA.EDU (Adam W. Zell)
Organization: Compilers Central
Date: Tue, 15 Dec 1992 20:02:40 GMT
Keywords: lex, question, comment

Just a quick question.  When I used flex a while back, I defined a
floating point number or integer as: 

number   [0-9]
exp         [Ee][+-]?{number}+
numtype {number}*\.?{number}+{exp}?

While flipping through the 2nd edition of Lex and Yacc, they use the
following definition:

number  [0-9]
exp        [Ee][+-]?{number}+
numtype ({number}+|{number}*\.{number}+)({exp})?

Is there any advantage in using the Lex and Yacc definition?  Does it use
fewer DFA states?
[I don't see any compelling advantage either way, except that the first
example works differently (worse) in AT&T lex because there's no parens
around the {exp}.  We did it the way we did because we wanted an example
for the | operator and parenthesised patterns.  Note that neither version
accepts "123." which I'd call a bug. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: drw@euclid.mit.edu (Dale R. Worley)
Newsgroups: comp.compilers
Subject: Re: static estimation of conditional branches?
Keywords: design
Date: 14 Dec 92 04:41:01 GMT
Article-I.D.: comp.92-12-057
Reply-To: drw@euclid.mit.edu (Dale R. Worley)
Organization: MIT Dept. of Tetrapilotomy, Cambridge, MA, USA

hrubin@pop.stat.purdue.edu (Herman Rubin) writes:
   One should not design a language, or a compiler, so that a fool can use it
   "properly." In that case, it is quite likely that nobody can use it at a
   higher level than the fool.  Design it for the genius first, and then put
   in the cautions, etc., for the fool.

Perhaps your view is based on your field (numerical analysis).  Numerical
analysis tends to be done mostly by geniuses, because the fools quickly
wash out.  In the rest of the software world, geniuses are 1% or less of
the population, because fools can get more-or-less useful work done.  Read
comp.lang.c if you want to know what the real world is like.  Ugh!

Dale
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: TDARCOS@MCIMAIL.COM (Paul Robinson)
Newsgroups: comp.compilers
Subject: COBOL Language Interest Group
Keywords: Cobol, parse, comment
Date: 17 Dec 92 03:12:16 GMT
Reply-To: TDARCOS@MCIMAIL.COM (Paul Robinson)
Organization: Compilers Central

Some people on the compilers list have been interested in COBOL.  Anyone
that would like to be involved in writing a specification for COBOL should
let me know so I can obtain their input on the subject.

Part of the information should consist of what is a "minimum" standard,
i.e. what features of the Identification, Environment, Data and Procedure
divisions should be required in the initial specification.  What features
are the ones "you can't live without."

There are some features that are nice to have but aren't mandatory because
they are available elsewhere and could either be implemented by the
compiler or using alternate programs, i.e. Report Writer and Sort.

There are some features that it would be nice to have in COBOL that might
be specific to certain environments, i.e.  having a specification in a
COBOL program that indicates a particular file is a DBASE format file on a
PC or any other system that can support DBASE's .DBF file format.  This
would also include the DBASE index format.

Some people may want to support other file types for binary files and
other things, or the method of doing Packed Decimal (COMP-3).

Since I've heard a number of people are interested, I'd like to hear from
anyone who is interested in hearing about COBOL or wants to make
suggestions.  Please send responses to me at

    TDARCOS@MCIMAIL.COM

Thank You, Paul Robinson
[Many people have asked about a free yacc grammar for Cobol, but nobody's
offered one.  Other than hacking around some of the lexical oddities of
Cobol, I'd think that it'd be straightforward to do so long as you had a
version of yacc that could handle the enormous number of reserved words in
a Cobol grammar, such as Berkeley yacc. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: iwm@doc.ic.ac.uk (Ian W Moor)
Subject: Re: static estimation of conditional branches?
Reply-To: iwm@doc.ic.ac.uk (Ian W Moor)
Organization: Dept. of Computing, Imperial College, University of London, UK.
Date: Mon, 14 Dec 1992 13:43:04 GMT
Keywords: optimize, performance

Henry Spencer <henry@zoo.toronto.edu> writes:
|> When people first started implementing profilers and the like, they found
|> one striking result: human intuition about the locations of the hot spots
|> in a complex program was *consistently wrong*.  ...
|> 

To be worthwhile, any compiler which accepts user hints like frequency or
register has to have the following property:

A correct hint must make an improvement that is worth gathering the
information, and an incorrect hint must either be detectable or must not
reduce performance much. 

This seems contradictory.. I'd rather rely on a profiler or register
allocator.
-- 
Ian W. Moor		+44 71 589 5111 x 5039
iwm@doc.ic.ac.uk   Department of Computing, Imperial College.            
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: TDARCOS@MCIMAIL.COM (Paul Robinson)
Subject: About Cobol Compilers - Info Wanted
Reply-To: TDARCOS@MCIMAIL.COM (Paul Robinson)
Organization: Compilers Central
Date: Fri, 18 Dec 1992 01:35:46 GMT
Keywords: Cobol, syntax

I am interested in COBOL compilers and I'm trying to find out what
features are used on what machines.  Even if someone isn't interested in
the creation of one, some of the readers of Compilers might be able to
supply me with information about the particular compilers used on their
system.

One thing I'd like to ask for, especially from people using unusual or
rare computers, is to obtain the list of reserved words and the cobol
structure list for their computer's COBOL compiler so I can see who is
using what.

I'm especially interested in finding if there is anything for the CRAY
series computer, and a few others.  NCR, Cyber, Honeywell and AT&T would
be interesting too.

I'll be happy to pay for photocopying and mailing charges, as what I'm
talking about is a 3-page or so list of words which are reserved for that
compiler, and perhaps another 4 or 5 pages of syntax specifications.
These are usually either in the beginning of the COBOL manual or the
appendix.

Any assistance would be appreciated.

Paul Robinson -- TDARCOS@MCIMAIL.COM
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: macrakis@osf.org (Stavros Macrakis)
Subject: Re: Extension Languages
Reply-To: macrakis@osf.org (Stavros Macrakis)
Organization: OSF Research Institute
Date: Thu, 17 Dec 1992 21:34:26 GMT
Followup-To: alt.folklore.computers
Keywords: design

drw@kronecker.mit.edu (Dale R. Worley) writes:

   When it came time to port it to Multics and Tops-20,

Actually, the Tops-20 version of Emacs was identical to the ITS version,
that is, a set of Teco macros.  The underlying Teco was ITS Teco (not DEC
Teco) ported to the Tops-20 operating system--Teco was written in PDP-10
assembler, and the user mode instruction set was essentially identical
between the PDP-10 and the DecSystem-20.

   Emacs was rewritten using Lisp as the base language, because
   reimplementing Teco would be too gross, and Lisp was the only other
   high-level language at the AI Lab.

The Multics version of Emacs, in Lisp, was written by Bernie Greenberg,
who was also the author of Multics Maclisp (written in PL/I).  I'm not
sure of his exact motives, but I think partly it was a "neat hack", partly
it was a test of Multics Maclisp, and partly Bernie just wanted to have
Emacs, and as you say, reimplementing Teco would be too gross.  Bernie, by
the way, was not the M.I.T. A.I. Lab, but in the Multics group (I'm not
sure whether he was an M.I.T. Lab for Computer Science or a Honeywell
employee at the time).

I do not believe that any of Bernie's code made its way to GNU Emacs,
although it was certainly a good proof of concept.

   No doubt this is over-simplified, but I suspect that historical accident
   and the prejudices of AI people had a lot to do with it.

An interpreter was considered essential, in order to allow real-time
extension without a compile-load loop (note also that dynamic loading of
code was not supported by most environments at that time).  Lisp was the
default choice of interpretive environment.

	-s
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: un027705@wvnvms.wvnet.edu (Jon Beck)
Newsgroups: comp.compilers
Subject: Building a Lattice
Keywords: theory
Date: 15 Dec 92 12:10:14 GMT
Reply-To: un027705@wvnvms.wvnet.edu (Jon Beck)
Organization: West Virginia Network for Educational Telecomputing

Can anyone point me to an algorithm for building a lattice? I happen to be
specifically interested in a lattice whose meet is set intersection, whose
join is set union, and whose partial ordering function is subset, but of
course that shouldn't matter to the algorithm. I'm posting here because it
seems as though a compiler for a language which has multiple inheritance
should have such an algorithm for building the inheritance hierarchy,
which for multiple inheritance is a lattice.

I have an algorithm which works, but it's hairy and smells bad; I was
looking for something a bit prettier and which won't leave spots on the
rug.
-- 
Jon Beck, Research Assistant
Department of Statistics and Computer Science
West Virginia University
beck@cs.wvu.wvnet.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: Peter Ludemann <ludemann@quintus.com>
Subject: Re: Extension Languages 
Reply-To: Peter Ludemann <ludemann@quintus.com>
Organization: Compilers Central
Date: Thu, 17 Dec 1992 22:34:22 GMT
Keywords: design, interpreter

Dave Gillespie <daveg@thymus.synaptics.com> writes:
> 
>	notation:	infix		prefix		postfix
>	example:	C, Pascal	Lisp		Forth, PostScript
>	syntax:    parens, opers, ...	parentheses	"none"
>	humans:		easy		okay		hard
>	machines:	hard		okay		easy
> 
>Languages on the left end of this spectrum require a lot of parsing effort
>	(relatively speaking) ...

I once read an article describing REXX's interpreter (REXX is used as both
a "shell" language and an editor extension language), which states that
20-30% of the CPU time is spent in scanning for the next non-blank ---
something a parser for any language needs to do (this scanner loop is in
tightly coded assembler, by the way).  As the standard method of handling
infix languages is to push things onto a stack, the cost of interpreting
an infix language should be the same as for prefix and postfix languages.
[Sorry, I don't have a reference to the article handy; I think it was by
Auslander, describing a port of REXX from 370 to RT.]

[Side note: from my work on a Prolog parser, I can attest that also
allowing user-defined prefix, infix, and postfix operators does not unduly
complicate or slow down the parser.]

Let's not push this efficiency argument too far or else we'll see BASIC's
original 1- and 2-letter identifiers resurfacing ... we wouldn't want to
spend too much time in hashing identifiers, would we? :-) Similarly,
there's no reason for the Bourne shell's requirement that functions be
defined before use; REXX easily handles that by recording each function's
location and scanning forward if necessary.  And I strongly suspect that a
properly built interpreter for an infix language would have performance
within a few percent of that for a prefix/postfix language --- and no
question about which is easier to program in.

If you want to see REXX's implementation, find somebody who has IBM's CMS
operating system; the interpreter source is included.  [The source for the
compiler and for the OS/2 implementation aren't.]

Incidentally, REXX is also evidence that powerful languages don't need to
be cryptic and that they can be used well by both beginners and experts
(REXX has roughly the expressivity of ksh+awk or perl, but with a syntax
like "BASIC done right").

-----

Peter Ludemann
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: henry@zoo.toronto.edu (Henry Spencer)
Subject: Re: static estimation of conditional branches?
Reply-To: henry@zoo.toronto.edu (Henry Spencer)
Organization: U of Toronto Zoology
Date: Fri, 11 Dec 1992 17:41:18 GMT
Keywords: optimize, design

hrubin@pop.stat.purdue.edu (Herman Rubin) writes:
>... the programmer should have some way of communicating this, and other,
>frequency considerations to the compiler.  As far as I know, this has not
>been done since the "FREQUENCY" statement in fairly early Fortran.
>[As I recall, Fortran II dropped FREQUENCY because it was infrequently
>used and made little difference.  I've heard that it may even have been
>implemented backwards and nobody noticed. -John]

The other problem that occurs with such facilities is that programmer
intuition is notoriously unreliable about such things.

Now, if you amend Herman's statement to "the *profiler* should have some
way of communicating this...", I'd agree... and observe that there are
already compilers that will accept profiler data and exploit it for
optimization.  I don't know whether they do this particular optimization,
but I wouldn't be surprised.
-- 
Henry Spencer @ U of Toronto Zoology, henry@zoo.toronto.edu  utzoo!henry
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: drw@kronecker.mit.edu (Dale R. Worley)
Subject: Re: Extension Languages
Reply-To: drw@kronecker.mit.edu (Dale R. Worley)
Organization: MIT Dept. of Tetrapilotomy, Cambridge, MA, USA
Date: Wed, 16 Dec 1992 22:47:28 GMT
Keywords: design, Lisp

Dave Gillespie <daveg@thymus.synaptics.com> writes:
   I think Emacs uses Lisp as its base language because Lisp is so well
   adapted to running interpretively and in a constantly changing
   environment.

Historically, the development of Emacs' extension language is more like
this:

The first Emacs was written as a set of extensions to the MIT AI Lab's
Teco, so all extensions were written in Teco.

When it came time to port it to Multics and Tops-20, Emacs was rewritten
using Lisp as the base language, because reimplementing Teco would be too
gross, and Lisp was the only other high-level language at the AI Lab.

No doubt this is over-simplified, but I suspect that historical accident
and the prejudices of AI people had a lot to do with it.

Dale
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: johnl@iecc.cambridge.ma.us (John R. Levine)
Newsgroups: comp.compilers
Subject: Compilers 1991 annual: legend or myth?
Keywords: administrivia, books
Date: 17 Dec 92 16:12:49 GMT
Reply-To: John R. Levine <johnl@iecc.cambridge.ma.us>
Organization: Compilers Central

Some comp.compilers readers may be wondering where the printed 1991
compilers annual is.  Here's the story:

For the 1990 annual, I sorted all the messages and printed them just as
they'd appear on a screen, 80 columns across with typewriter type.  This
minimized the editorial work required, but came up with a 600 page book
which was pretty bulky.  For 1991, there were far more messages, so a
similar approach would have produced a 1000 page book or maybe a pair of
500 page ones, either way it'd be expensive and unwieldy.

So to save space (and also make a more readable book) I had to typeset it,
meaning each message has to be marked up to indicate what is plain text,
what it computer font, and so forth.  This required considerably extra
work, so I talked to some real publishers about having them publish it,
still with my editing, since a publisher's economies of scale would allow
better book quality at lower cost and also make possible CD-ROMs.  I've
found a publisher, but it got so late in the year that a a 1991 volume
couldn't be issued until sometime in 1993, which is kind of late.
Basically, I screwed up.  Sorry.

So unless a lot of people (more than 80) tell me that they'd still pay $50
for a 1991 printed volume even if they couldn't get it until April of
1993, I'll drop the 1991 edition and pick up with a timely 1992 edition in
the spring of 1993.

By the way, the full text of all of the 1991 messages is as always
available for FTP at primost.cs.wisc.edu with no restrictions on
redistribution, so if someone else wants to print all or part of the 1991
messages, be my guest.

Regards,
John Levine, comp.compilers moderator
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: hrubin@pop.stat.purdue.edu (Herman Rubin)
Newsgroups: comp.compilers
Subject: Re: static estimation of conditional branches?
Keywords: optimize, comment
Date: 13 Dec 92 18:20:49 GMT
Article-I.D.: comp.92-12-055
Reply-To: hrubin@pop.stat.purdue.edu (Herman Rubin)
Organization: Purdue University Statistics Department


idacrd!desj@uunet.UU.NET (David desJardins) writes:
>... any programmer who is making a serious effort to write high-
>performance code must know approximately how often each of the conditional
>branches in critical sections is taken...

henry@zoo.toronto.edu (Henry Spencer) writes:
>I agree with this statement, with one crucial substitution: for "must"
>read "should", in the sense of "you should stay below the speed limit".

>When people first started implementing profilers and the like, they found
>one striking result: human intuition about the locations of the hot spots
>in a complex program was *consistently wrong*.  ...

There are many stiuations in which one KNOWS how often branches are taken,
even if one does not know, for various reasons, how much time is spent in
a given kind of operation.  When I post an algorithm for generating a kind
of non-uniform random variable, if my reasoned estimates of how often each
branch is done is off by more than roundoff, it is because the uniform
input is not random.  If profiling finds anything different, either I have
miscalculated or the input uniform random numbers do not have the
properties they are supposed to have.

There are many other cases of this.  In numerical work, one might easily
misguess on which major class of cases is most common, but one is not
likely to be far off on what is happening locally.  Even someone fairly
adept at numerical analysis will recognize what is known and what is not.

One should not design a language, or a compiler, so that a fool can use it
"properly." In that case, it is quite likely that nobody can use it at a
higher level than the fool.  Design it for the genius first, and then put
in the cautions, etc., for the fool.
-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054 hrubin@snap.stat.purdue.edu (Internet, bitnet)  
{purdue,pur-ee}!snap.stat!hrubin(UUCP)
[I'd go the other way.  Geniuses are a lot more flexible than fools. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers