HDTenEightyP/NetNews huggingface dataset:
From: Paul Havlak <paco@cs.rice.edu>
Subject: Re: question on control dependence
Reply-To: Paul Havlak <paco@cs.rice.edu>
Organization: Center for Research on Parallel Computation
Date: Tue, 15 Dec 1992 19:13:56 GMT
Keywords: optimize, design, bibliography

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

    Looks to me like the algorithm should work.  I dislike it anyway
for two reasons:

	* It's not very general; many languages allow more than two
		branches out of a node.

	* It uses bit vectors.  Sure, you only require O(N) bit-vector
		steps for N nodes, but the bit vectors are O(N) long,
		so you're always paying O(N^2) time and space.

    My favorite algorithm for control dependence calculation is in [3].
It requires no data structures besides the control-flow graph and the
postdominator tree, as input, and the control dependence graph, as output.
The algorithm takes time linear in the number of control dependences,
which is usually linear in the number of nodes.
    First, build the postdominator tree using the method of [4]
(almost-linear) or [5] (linear).  Then to enumerate the set CD(X, L) [the
control dependence successors of a node X with label L], do the following:

	* CD(X, L) = {}

	* Assign Y = the sink of X's control-flow outedge with label L

	* While (Y != immediate postdominator of X)
		CD(X, L) += Y
		Assign Y = immediate postdominator of Y

	(where += denotes addition of member to set)

Note that this method can also be used in the construction of SSA form;
see [3] for details.

References:

[3]
@inproceedings{CFS:Compact,
   Author={R. Cytron and J. Ferrante and V. Sarkar},
   Title={Compact representations for control dependence},
   BookTitle=SIGPLAN90,
   Address={White Plains, New York},
   Pages={337--351},
   Month=Jun,
   Year={1990}}

[4]
@Article{LeTa:Dom,
        Author = {T. Lengauer and R. E. Tarjan},
        Title = {A fast algorithm for Finding Dominators in a flowgraph},
        Journal = TOPLAS,
        Volume = 1,
        Pages = {121--141},
        Year = 1979}

Actually, [3] cites another method for building the postdominator
tree which, I just realize, I've never looked up:

[5]
@inproceedings{Harel:Dom,
	Author = {Dov Harel},
	Title = {A linear-time algorithm for finding dominators in
		flow graphs and related problems},
	BookTitle = {Symposium on Theory of Computing},
	Month = May,
	Year = {1985}}
--
Paul Havlak			Dept. of Computer Science
Graduate Student		Rice University, Houston TX 77251-1892
PFC/ParaScope projects		(713) 527-8101 x2738 	paco@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: bwilson@shasta.stanford.edu (Bob Wilson)
Subject: Re: control dependence question
Reply-To: bwilson@shasta.stanford.edu (Bob Wilson)
Organization: Compilers Central
Date: Wed, 16 Dec 1992 21:09:45 GMT
Keywords: optimize, design

The following message which I posted was based on what I remembered from
reading the PTRAN report some time ago.

Carl McConnell writes:
> I've come up with a simple algorithm for computing control dependences, ...

I replied: 
> This sounds like the algorithm that was used in the PTRAN compiler.
> I think it's described in a research report by Vivek Sarkar:
> 
> "PTRAN - the IBM Parallel Translation System"
> IBM Research Division Report RC 16194
> 1990

I guess my memory of their control dependence analysis algorithm was a
little too fuzzy.  That algorithm is the same as the one described in the
paper "Compact Representations for Control Dependence" by Cytron et al.
in PLDI '90.  Instead of comparing the sets of postdominators as
McConnell's algorithm does, they build the postdominator tree and
determine the control dependences based on the immediate postdominators.
Sorry for the confusion.

Bob Wilson
bwilson@shasta.stanford.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: idacrd!desj@uunet.UU.NET (David desJardins)
Newsgroups: comp.compilers
Subject: Re: static estimation of conditional branches?
Keywords: optimize, performance
Date: 14 Dec 92 04:36:24 GMT
Article-I.D.: comp.92-12-058
Reply-To: idacrd!desj@uunet.UU.NET (David desJardins)
Organization: IDA Center for Communications Research, Princeton

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*.  ...

We were talking about branch prediction.  It is *much* easier for a
programmer to say how often a particular conditional branch is going to be
taken than it is for the programmer to say how much time is going to be
spent in a particular region of code.  Among several reasons for this is
that the former is independent of the machine, compiler, or optimizer,
while the latter is not.

                                        David desJardins
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
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:58:20 GMT
Keywords: design

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

>2.  Assume that each node in the flow graph has no more than 2 successors,
>and that if a node does have 2 successors, one is the "true" successor and
>the other the "false" successor.  For a given flow node X, let CD(X)
>denote the nodes that are control dependent on X.  If X has fewer than 2
>successors, CD(X) is empty.  Otherwise, we can find CD(X) as follows:
>    CD(X) = P(X-true) ^ P(X-false)
>where X-true and X-false are respectively the true and false successors,
>and "^" denotes symmetric difference (i.e., A ^ B = (A | B) - (A & B)).

The general case of more than 2 succesoors is handled like this...

	CD(X) = union(P(S)) - intersection(P(S)), for S in successors(X)

(This is a much simpler version of another answer I posted earlier)

cliffc@rice.edu (Cliff Click) writes:
>3) Your problem is 1-bounded; a single pass over the graph is
>sufficient.

Only for part 2.  For part 1 (computing post dominance), more than 1
pass may be required.

>4) Your problem requires O(N) bit-vectors, or
>   O(N^2) COMMON CASE but with a small constant.

That is, O(N^2) space, where N is the number of basic blocks.

>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.

McConnel's algorithm will require at least O(N^2) time (consider the bit
vectors to be initialized).  On the other hand, I believe it only requires
O(N^2) time worst-case.  Therefore, worst case, the algorithms are the
same.  Best case (and probably expected case , Cytron et al. are faster,
though perhaps only for very large N.

Preston Briggs
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: mcconnel@newta1.cs.uiuc.edu
Subject: question on control dependence
Reply-To: mcconnel@newta1.cs.uiuc.edu
Organization: Compilers Central
Date: Mon, 14 Dec 1992 23:42:03 GMT
Keywords: design

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:

=== Begin Algorithm ===

1.  For a given flow node X, let P(X) denote the nodes that post-dominate
X, along with X itself.  Compute P(X) by using any of the standard
techniques to solve the following backward data flow equations:
    P(X) = X | (P(Y1) & ... & P(Yn)),
    P(Stop) = {}
where Y1 ... Yn are the successors of X, "|" denotes set union, "&"
denotes set intersection, and Stop is a unique exit node for the flow
graph.  (This part is pretty much straight out of the red dragon book.)

2.  Assume that each node in the flow graph has no more than 2 successors,
and that if a node does have 2 successors, one is the "true" successor and
the other the "false" successor.  For a given flow node X, let CD(X)
denote the nodes that are control dependent on X.  If X has fewer than 2
successors, CD(X) is empty.  Otherwise, we can find CD(X) as follows:
    CD(X) = P(X-true) ^ P(X-false)
where X-true and X-false are respectively the true and false successors,
and "^" denotes symmetric difference (i.e., A ^ B = (A | B) - (A & B)).
Furthermore, the edges that should be labelled "true" in the control
dependence graph are the ones from X to the nodes in CD(X) & P(X-true);
and "false", the ones to the nodes in CD(X) & P(X-false).

=== End Algorithm ===

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.  This algorithm is asymptotically as efficient as
they are; for typical programs, it's probably more efficient than the
algorithm in [1].  My question is, has this algorithm been proposed
before?  (It seems too simple not to have been.)

    Carl McConnell
    Grad Student
    Department of Computer Science
    University of Illinois at Urbana-Champaign
    1304 W. Springfield Ave.
    Urbana, IL 61801-2987

-------------------

References:

[1]
@article{ferrante87,
  author="Jeanne Ferrante and Karl J. Ottenstein and Joe D. Warren",
  title="The Program Dependence Graph and Its Use in Optimization",
  journal=toplas,
  volume=9,
  number=3,
  month=jul,
  year=1987,
  pages="319-349"
}

[2]
@article{cytron91,
  author = 	"Ron Cytron and Jeanne Ferrante and Barry Rosen
		 and Mark Wegman and Kenneth Zadeck",
  title="Efficiently Computing Static Single Assignment Form and the 
      Control Dependence Graph",
  journal=toplas,
  volume=13,
  number=4,
  month=oct,
  year=1991,
  pages="451-490"
}
-- 
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: Fri, 18 Dec 1992 01:22:57 GMT
Keywords: design

Dave Gillespie <daveg@thymus.synaptics.com> writes:

   ...You can think of a spectrum of linguistic simplicity vs. ease of use by
   human programmers:

     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) and have a lot of redundancy in their grammars,

As Knuth, Morris, and Pratt said in their paper on fast pattern matching: 

    It is a curious fact that people often think the new algorithm will be
    slower than the naive one, even though it does less work.  Since the
    new algorithm is conceptually hard to understand at first, by
    comparison with other algorithms of the same length, we feel somehow
    that a computer will have conceptual difficulties too--we expect the
    machine to run more slowly when it gets to such subtle instructions!

Any of these notations are "easy for the machine", although some of the
tables will be larger for infix notation.

   ...There's nothing stopping you from doing a Lisp-like language that uses
   postfix operators, but people generally don't because the interpreter has
   an easier time of it if the operator comes first.

Two remarks:

1) You seem to assume that postfix syntax translates into difficulty of
   accessing the operator.  But the syntax doesn't tell you anything about
   the internal representation.

2) Many machine-oriented languages are postfix, precisely because they are
   EASIER to interpret.  The problem comes only with non-strict operators
   like "if", which such languages avoid by using explicit gotos.

   I've also seen languages which are Lisp-like in essence, but with C-like
   parsers added on top to make them more palatable.  In other words, they
   have a parser which reads "a+b" into the list "(+ a b)".

Yes, there are Lisp-like languages which provide an infix syntax, or even
Lisps which happen to have an infix reader as well.  But they are not
Lisp-like because they represent the program as a tree!  After all, many
language processors represent the program as a tree at some point....

Recall also that S-expressions were originally designed as a "machine
representation" for M-expressions, which were NOT parenthesized.  Lisp is
truly protean, n'est-ce pas?

	-s
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers
From: chased@rbbb.Eng.Sun.COM (David Chase)
Subject: Re: static estimation of conditional branches?
Reply-To: chased@rbbb.Eng.Sun.COM (David Chase)
Organization: SunPro
Date: Sat, 12 Dec 1992 20:15:16 GMT
Keywords: optimize

Henry Spencer <henry@zoo.toronto.edu> writes:
> The other problem that occurs with such facilities is that programmer
> intuition is notoriously unreliable about such things.

idacrd!desj@uunet.UU.NET (David desJardins) writes:
>I don't understand this statement in this context in this context.  I know
>it's fashionable in this group to claim that compilers are supergeniuses
>and humans are idiots.

Compilers are super-patient and humans are not.

>But any programmer who is making a serious effort to write high-
>performance code must know ...

You've got to be careful about confusing common-case and best-case.  If
80% of the programmers either don't bother or don't know 80% of the time,
then I'd call that "notoriously unreliable".  That still leaves plenty of
room for many people to occasionally know exactly what is happening.
However, those people are a distinct minority, and catering to their needs
is not likely to bring as large a reward as catering to the needs of the
common case.  (I.e., consider economics.)

>Of course, I too endorse the feedback of profiler information as a more
>convenient (to the user) way to achieve similar results.

Because it is more convenient, it is used by more people, and hence has a
bigger reward than special-case frequency hints.  Profiling feedback is
also useful because it does not require source code changes -- if you
discover that your training inputs are not typical, you merely get some
better ones, train, and recompile.  Source code changes are much more
costly because they involve more human interaction and can include the
possibility of introducing errors (even if only a typo).

David Chase
Sun
-- 
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: Sun, 13 Dec 1992 05:09:24 GMT
Keywords: optimize

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

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...

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*.  All kinds of attention had
gone into optimizing things that weren't important, or even made things
worse in unforeseen ways.

>... It's a question of understanding what the code is doing: an
>understanding which is fundamental to optimization.

Indeed so.  And you get that sort of understanding only by measurement.
Guesswork, even informed guesswork, is known to be inadequate... but
people rely on it nevertheless.

If you've got the measurements, just supplying *them* direct to the
compiler works much better.  If nothing else, it avoids the temptation to
skip that annoying measurement step and just wing it.
-- 
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: glew@pdx007.intel.com (Andy Glew)
Subject: Re: static estimation of conditional branches?
Reply-To: glew@pdx007.intel.com (Andy Glew)
Organization: Intel Corp., Hillsboro, Oregon
Date: Sat, 12 Dec 1992 23:37:37 GMT
Keywords: optimize

> I surmised that the original poster was asking if there was any empirical
> data to say that "most if-tests are taken" or "most if-tests are not
> taken".  However, I would think that such conclusions would be heavily
> influenced by programming style and the programmer's personal preferences.

This does suggest a heuristic such as the following:

If one side of a conditional contains exit(nonzero), the word "error", or
an fprintf(stderr,...) or perror(), predict that side of the conditional
not to be taken.

Sure, it's dirty.  But it's better than annotating with a #pragma.  And
it's the sort of thing human programmers do all the time.
--
Andy Glew, glew@ichips.intel.com
Intel Corp., M/S JF1-19, 5200 NE Elam Young Pkwy, 
Hillsboro, Oregon 97124-6497
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: fcs$1224@altair.selu.edu
Newsgroups: comp.edu
Subject: CS Dissertation Abstract ftp site?
Date: 16 Dec 92 23:30:15 -0600
Organization: Southeastern Louisiana University

Does anyone maintain an anonymous ftp site for the
dissertation abstracts in Computer Science?  Or 
anything like it.

Thanks,

Tom

T. F. Higginbotham, Ph. D.
Professor of Computer Science
Southeastern Louisiana University
Hammond, Louisiana 70402 
Xref: sparky comp.edu:2233 comp.lang.scheme:2797 comp.lang.logo:370
From: caroma@ai.mit.edu (Carl R. Manning)
Newsgroups: comp.edu,comp.lang.scheme,comp.lang.logo
Subject: Spread of Scheme and SICP?
Date: 21 Dec 92 00:27:10
Organization: MIT Artificial Intelligence Laboratory
Distribution: usa
NNTP-Posting-Host: cookie-crisp.ai.mit.edu

Hi,

I was wondering if anyone is keeping track of how widely Scheme and
SICP (Abelson and Sussman's Structure and Interpretation of Computer
Programs) is being used in universities.  I'm trying to help someone
who is trying to make an argument for a high school district to
(continue to) allow teaching Logo rather than being restricted to
Basic and Pascal.  One argument has been that many (better)
universities have been starting to use Scheme and SICP, and teaching
H.S. programming with Logo (e.g., using Brian Harvey's books) serves
as a better preparation for the students than teaching Basic or
Pascal.  Thus, information on the spreading use of Scheme and SICP to
universities can be helpful supporting evidence.  Has anyone been
keeping track of this spread?  Pointers to papers, etc., on this topic
also appreciated.

(I don't check these newsgroups regularly, so email replies
preferred.)

Thank you in advance,

Carl R. Manning
caroma@ai.mit.edu

Xref: sparky comp.edu:2194 comp.lang.misc:4022 comp.software-eng:4918
Newsgroups: comp.edu,comp.lang.misc,comp.software-eng
Subject: Re: Programming language selection criteria
From: jhowatt@eeyore.stcloud.msus.edu (Jim Howatt)
Date: 13 Dec 92 09:45:51 -0600
Followup-To: comp.edu comp.software-eng
Distribution: world
Organization: St. Cloud State Univ., MN

john@jlc.mv.com (John Leslie) replies to my post:

> > jhowatt@eeyore.stcloud.msus.edu (Jim Howatt) writes:

   [ .. stuff deleted .. ]

> > In the first chapter [Sebesta] lists several language selection/evaluation
> > criteria; but the list "feels" uncomfortably incomplete and subjective.
> 
>    In the real world, the list of criteria has one item -- politics.
> 
> > In view of the flame wars that we often see among proponents of
> > different languages, I'd like to present my students with a set of
> > reasonably objective criteria for selecting a language for a given task.
>     [ .. more stuff deleted .. ] 
>    I've seen literally hundreds of criteria, most often generated after
> the fact to justify a (usually reasonable) choice already made.  

Would you share these criteria with us?  This is what I'm looking for.
Even if they're after-the-fact, if they're reasonable, let's hear them!

>                                                                 I think
> such a list is nearly useless, unless it has stood the fire of flame-wars
> on the Net.  I _would_ welcome some submissions, open to flaming, because 
> we _might_ be ready to reach consensus on a few criteria...

Please post your list so we can all take part in the flaming.

> [ ... ]  I really think you're barking up the wrong tree.  [ ... ] 
> The point _shouldn't_ be that Algorithm A
> is best programmed in Language L; rather students should get a feeling
> for tradeoffs -- Language Q may not be ideal for Algorithm A, but the
> penalty is in the neighborhood of H hours, which might be made up elsewhere
> in the project.
>    Students should leave your course with a feeling that most times the
> savings from choosing the right language are less than the time they'd
> spend fighting the political battle to use it.

This is the kind of input I'm looking for. 
 
> John Leslie <john@jlc.mv.com>
> 
> PS: I've set followup to comp.edu, where I think the discussion belongs.

  I disagree.  The reason I posted to comp.software-eng was to get input
  from practitioners.  I can find all the academic criteria I want in texts.

Jim
Organization: Middle East Technical University - Computer Center
Date: Wednesday, 16 Dec 1992 11:38:47 TUR
From: <E59387@TRMETU.BITNET>
Newsgroups: comp.edu
Subject: WANTED: Programs about physical experiments


    HI,

    I NEED SOURCE CODE OF SOME PHYSICAL EXPERIMENTS SUCH AS MOMENTUM,

  PROJECTILE MOTION.IF YOU CAN POINT ME A SITE WHERE CAN I FIND SUCH

  PROGRAMS. I'LL BE VERY GLAD.

    OR CAN YOU HELP ME ABOUT HOW CAN I DO ANIMATION OR SIMULATION OF

  THESE MOTION SUCH AS PROJECTILE MOTION , COLLISION OF TWO oBJECTS

  IN MOMENTUM CALCULATIONS ON GRAPHICS.


  THANKS IN ADVANCE.
From: rpiercy@casbah.acns.nwu.edu (Rogers Piercy)
Newsgroups: comp.edu
Subject: computers & medicine
Date: 13 Dec 92 18:18:16 GMT
Article-I.D.: elvex34.rpiercy-131292121909
Organization: Northwestern University

Physicians & Computers (journal mailed to 90,000 physicians at no charge.)
is soliciting manuscripts that will describe changes brought about by the
direct use of computers in the practice of medicine during the decade of
the 1990's. Papers addressing various computer application in research,
imaging and other contributions which advance or illuminates medical
science with the direct use of computers are encouraged.  Physician
authored materials preferred.  Examples include: 
% Computerized Diagnosis--(various medical 
JJJdisciplines)
% Decision Making
% Physican Authored Medical Software% Handheld Computers--Patient
History/Charting
% Medical Practice Networking 			
% Notebook Computers in Clinical Research
% Computerized Reimbursement
% Developming Trends in Clinical Computing
% Computerized Medical Records
% Pen Computing/Physician Uses