HDTenEightyP/NetNews huggingface dataset:
From: henry@zoo.toronto.edu (Henry Spencer)
Subject: Re: binary-compiler from Apple?
Keywords: translator, architecture
Reply-To: henry@zoo.toronto.edu (Henry Spencer)
Organization: U of Toronto Zoology
Date: Thu, 9 Apr 1992 02:05:48 GMT

In article <92-04-030@comp.compilers> taihou@iss.nus.sg (Tng Tai Hou) writes:
>Apple is doing a binary-compiler for its new line of PowerPC Macs. It
>takes in existing 680x0 code and translate opcodes for the PowerPC chip.
>Can anyone tell me if this is logical, or right approach?  Seems to be a
>great idea. Why hasn't anyone thought of it before?

It's been thought of many times, and has seen operational use.  You can
buy commercial products that do this for x86 code in particular.

The main problem is performance, and how serious it is depends on the
nature of the two machines.  Ideally, they should have the same byte
order, the "source" machine should have substantially fewer registers than
the "object" machine, and the "source" machine should not have condition
codes.  Wrong byte order, inadequate registers, or the need to simulate
condition codes can result in very bulky and very slow code, unless
perhaps you optimize heavily.  Mismatches in memory model can also be
troublesome; you'd really like addresses on the source machine to be
usable as-is on the object machine.  One area where nobody has found a
good solution (that I know of) is mapping branch addresses that the
program computes in complex ways; the usual brute-force solution is a
table, one entry per possible source-machine branch target (that's one
entry for each and every instruction!), used to map computed branch
targets into the real targets.
-- 
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.
From: samuel@nada.kth.se
Newsgroups: comp.compilers
Subject: Wanted: a program that calulates the maximal stack depth
Keywords: code, question
Date: 6 Apr 92 19:58:33 GMT
Reply-To: samuel@nada.kth.se
Organization: Compilers Central

Hi netters!

 I'm developing an application where the use of stack space is crucial.
The program almost only manipulates sequential structures and calls no
library functions. So what I need is a utility that calculates the maximal
used-up stack space for each function in the code. The output could
look something like:

                     size of call frame to main
                                   |
                                   V
    main : max(init, main_loop) + 10                       = 200
    init : max(init_a, init_b, init_c) + 12                = 190

(a recursive function, not called directly or indirectly by any of the above:)
    foo :  Recursive*12 + 12                               = Recursive*12+12

and so on. The program would probably work by building arithmetic trees and
then propagating the leaf values from the functions that don't call any other.
You would have to feed into it the size of the basic data types, the size of
calls, and the source code.

 If anybody has heard of such a program, please let me know!

 If there is no such thing anywhere, maybe someone could point me to a
PD C grammar that builds expression/statement trees. I'm happy for any hint 
I can get.
                                                    Sam


    	Samuel Cederlund, programming assistant  samuel@nada.kth.se
        Interaction and presentation lab
    	Dep. of computer science
        Royal Inst. of Technology
[I'd think that in many cases it might be easier to scan the generated
assembler code for instructions that change the stack pointer.  Several C
grammars are available, see the compilers FAQ. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: russw@cs.utexas.edu (Russ Williams)
Subject: Re: Wanted: a program that calulates the maximal stack depth
Keywords: storage
Reply-To: russw@cs.utexas.edu (Russ Williams)
Organization: Great Northern Hotel
Date: Thu, 9 Apr 1992 02:36:08 GMT

samuel writes:
> I'm developing an application where the use of stack space is crucial.

I can't help about getting exact stack usage for each function, but
I recently read a clever idea to empirically compute the stack space
used by the entire program: Add some (machine/language specific)
initialization code at start of your program to initialize all of
stack space with a random magic constant, then at end of program
look at stack space and see how far up it got overwritten.  This
isn't exact, of course, but may be good enough.

Russ
russw@cs.utexas.edu
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: lee@cadenza.rutgers.edu (Yong-fong Lee)
Newsgroups: comp.compilers
Subject: Data flow analysis
Keywords: dataflow, optimize, question
Date: 14 Apr 92 18:01:31 GMT
Article-I.D.: comp.92-04-057
Reply-To: lee@cadenza.rutgers.edu (Yong-fong Lee)
Organization: Rutgers Univ., New Brunswick, N.J.

If you have implemented data flow analysis algorithms for your systems
(for example, compilers), I would like to know any of the following
methods you used:

	1. iterative algorithms;
	2. Allen-Cocke interval analysis;
	3. Tarjan interval analysis;
	4. Hecht-Ullman T1-T2 analysis;
	5. Graham-Wegman S1-S2-S3 analysis;
	6. others, please specify.

Please respond by e-mail to lee@cs.rutgers.edu.  If there are many
responses, I'll post a statistical result later.

Yong-fong
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers,comp.programming,comp.lang.c
From: markt@harlqn.co.uk (Mark Tillotson)
Subject: Re: Is there a way of generating code for x/const without division?
Keywords: arithmetic, optimize
Reply-To: markt@harlqn.co.uk (Mark Tillotson)
Organization: Harlequin Limited, Cambridge, England
Date: Wed, 8 Apr 1992 11:53:34 GMT

jeremy@sw.oz.au (Jeremy Fitzhardinge) writes:

> I've been playing with a simple code generator for RISC CPUs.  One of the
> simple peephole optimisations it does is to replace multiplies by
> constants with a series of shift/adds rather than using the general
> multiplication.
> 
> I'm wondering whether a similar thing can be done for divide and modulo,
> such that they are implemented by the code generator as a sequence of
> simple instructions that is more efficient (in time) than the more general
> way of performing divide/modulo.

Well, for powers of two it is easy, a single shift, but there is also a
method for modulo by numbers which are close to a power of two, such as
3,5,7,9,15,17.  It only really pays off when division is expensive on the
processor (such as SPARC integer divide), or for the larger examples (such
as 0x200001)

The basic idea is to split to number up into groups of n bits, where the
desired modulus is close to 2^n, and then sum the sets of bit
appropriately so that the modulo of the sum is equal to the desired
result. This combination is done by series of shifts and adds/subtracts. 

Consider B = 2^7, then we can take a number A = c3*B^3 + c2*B^2 ... + c0
and note that the modulo of this by B-1 is the sum of the modulos of each
section, (modulo B-1), and that B^n modulo B-1 is always 1.  Thus we want
(c3+c2+c1+c0) modulo B-1, which is easy to calculate.

For a modulo of B+1, then  B^n modulo B+1 is  (-1)^n, so alternate
additions/subtractions are required.

Using a divide/conquer method to combine the chunks of bits enable an
instruction sequence of size log2 m, where m is the number of chunks in
the word, to combine the sets of bits.  Beware of overflow between
neighbouring chunks (there is always a guard chunk though).

Example in C:

long  module_by_127 (a)
  long a,;
{	
  long  tt ;
  tt  =  (a & 0xF01FC07F) + ((a >> 7) & 0xF01FC07F) ;
  tt  +=  (tt >> 14) & 0x3fff ;
  tt  +=  (tt >> 28) ;
  /* now repeat to compress the 9 bit result into 7 bits again */
  tt  =  (tt & 0x7F) + ((tt >> 7) & 0x7F) ;
  if (tt >= 0x7F)
  { tt  -= 0x7F ; }
  return (tt) ;
}
/* this is about 20 RISC instructions, as opposed to a loop of about 4
   instructions that gets executed 32 times */

Of course the fastest way to divide or modulo on such a RISC as the
SPARC is to use double floats....
--
M. Tillotson       Harlequin Ltd.
markt@uk.co.harlqn  Barrington Hall,
44 223 872522       Barrington, Cambridge CB2 5RG
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Xref: sparky comp.compilers:749 comp.arch:4791
From: moss@cs.umass.edu (Eliot Moss)
Newsgroups: comp.compilers,comp.arch
Subject: Re: Is there a way of generating code for x/const without division?
Keywords: optimize, arithmetic
Date: 3 Apr 92 14:04:06 GMT
Reply-To: moss@cs.umass.edu (Eliot Moss)
Followup-To: comp.compilers
Organization: Dept of Comp and Info Sci, Univ of Mass (Amherst)

The question was: if one is dividing by a constant or taking modulus by a
constant, might one do better than using a general divid instruction,
analogous to doing some shifts and adds to replace a multiply? The answer,
of course, is "yes, but the advisability depends a lot on the
architecture". In fact, there was recent discussion in one of the news
group (I think it was comp.arch, but it might have been comp.compilers) of
the divide track.  Basically, one replaces the division by multiplication
times the inverse.  Suppose we have 32 bit words and a multiply that can
generate a 64 bit result.  Then we can compute an inverse that has the
binary point at the high end of the word (this binary point is "in our
mind") and when we multiply, the high order word has the integer part and
the low order word the fraction. Careful calculation of the inverse value
will allow you to use the high order half as the result directly (i.e., no
rounding or adjustment required). Similarly, if we know the values are
bounded by say, 16 bits, we can carry all of this out using a multiply
that produces a 32 bit rather than 64 bit result. And finally (whew!) that
multiply could be done by shifts and adds. Whether or not this is
*profitable* depends strongly on the relative speeds of divide, multiply,
shift, add, etc., *and* on the constant value involved.

Concerning modulus, there are all kinds of tricks if the constant is
special.  Most compilers will mask if the constant is a power of two, for
example. If the constant is close to a power of two (e.g., +/- 1 from a
power of two), then repeated shifting, adding/subtracting, and maybe some
masking, will do the trick (if you learned it in school, mod 2^n-1 works
like "casting out nines" does in base 10).

Perhaps other respondents can provide citations in the literature that go
beyond my blathering .....

--

		J. Eliot B. Moss, Assistant Professor
		Department of Computer Science
		Lederle Graduate Research Center
		University of Massachusetts
		Amherst, MA  01003
		(413) 545-4206, 545-1249 (fax); Moss@cs.umass.edu

-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers,comp.theory,comp.lang.prolog
From: dekker@dutiba.tudelft.nl (Rene Dekker)
Subject: unification with evalution
Keywords: prolog, question
Reply-To: dekker@dutiba.tudelft.nl (Rene Dekker)
Organization: Delft University of Technology (TWI)
Date: Mon, 13 Apr 1992 14:23:28 GMT

Hello net,

I am looking for literature on unification, where part of the expressions
can be generated by function applications. For example, the following two
expressions should unify:

	Int -> Int
and
	f(Int)

where f(x) = x -> x.  The unification algorithm should also be able to
unify two applications, without actual evaluation of the expressions. For
example:

	f(Int)
should unify with
	T(Int)

where T is a variable. This is especially important in the context of
recursive functions.

Can anybody who knows about papers, books or other literature on this
subject please Email me. I'll summarise for the net if there is interest.

Rene.
-- 
Rene Dekker      Delft University of Technology       dekker@dutiba.tudelft.nl
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers,comp.parallel
From: bourne-linda@CS.YALE.EDU (Linda Bourne)
Subject: Alan J. Perlis Symposium at Yale, April 23
Keywords: conference, parallel
Reply-To: bourne-linda@CS.YALE.EDU (Linda Bourne)
Organization: Yale CS Mail/News Gateway
Date: Wed, 8 Apr 1992 20:07:04 GMT

ALAN J. PERLIS SYMPOSIUM:  Parallel Computers of the Future

Sponsored by the Department of Computer Science, Yale University

April 23, 1992

Sheffield-Sterling-Strathcona Hall
Room 114
Corner Grove and Prospect Streets
New Haven, Connecticut


Morning Session (9:30-11:00)

	Opening Remarks
		Drew McDermott
		Chairman, Yale CS

	"Dataflow Architectures:  From Monsoon to *T"
		Arvind
		Massachusetts Institute of Technology


Afternoon Session (1:30-4:30)

	"PRAMs:  Theory, Physical Design, and Application"
		Wolfgang Paul
		University of Saarbrucken

	"Will Parallel Architectures Converge?"
		H.T. Kung
		Carnegie-Mellon University



Following the last talk a public reception will be held at the
Department of Computer Science, Arthur K. Watson Hall.

All talks are free and open to the public.

For further information please call (203) 432-1246.
[Perlis was my thesis advisor and a personal friend.  He's sorely missed.
-John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
From: lins@Apple.COM (Chuck Lins )
Newsgroups: comp.compilers
Subject: Re: Recovering control flow information
Summary: Computed branch problems
Keywords: optimize, parallel
Date: 16 Apr 92 17:01:23 GMT
Reply-To: lins@Apple.COM (Chuck Lins )
Organization: Apple Computer Inc., Cupertino, CA

bwilson@shasta.Stanford.EDU (Bob Wilson) writes:
>Andrew Sao-Chun Huang <ahuang@faraday.ece.cmu.edu> writes:
>>2) Computed branches.  Sometimes 'switch' statements get compiled into a
>>computed branch where the targets are store in a table in data memory.  I
>>need to add control flow arcs from the basic block that contains the
>>computed branch to each of the target basic blocks. 
>
>This problem can be be solved by analyzing the assembly instructions used
>to compute the branch target address.  In some sense, you can just
>interpret the instructions at compile time.  All that you need to find are
>the starting address of the table and the number of entries in the table.

In the general case, I think this may require interprocedural analysis.
The variable used in the switch statement could be passed as a parameter,
and then you'll have a harder time determining the actual size of the
table. If the table is embedded in the object code, sometimes the offset
will look like instructions (if you're scanning the code to find the end
of the table).

Another problem area is function pointers.  Here the variable could be
stored with the procedure's address at any arbitrary place in the program.
Depending on the architecture, an indexed jump through a function pointer
might look like a case/switch statement.

We wanted to do something similar to this. Essentially, enhance the output
of IBM's compilers to provide relocations for all procedure calls and
subdivide the "per-module" csects into "per procedure" csects; strip the
TBT; and add TOC reload instructions for all procedure calls (the Apple
Linker would replace the reload with a nop as necessary). Note that this
was to be done on the compiler's output, so not all calls were necessarily
resolved at this point.

The simple cases were easy to handle. Switch statements, function
pointers, and similar stuff made us realize that we probably couldn't do
this without being unsafe in some cases. It was cheaper in time and effort
to just pay IBM to enhance their compilers the way we wanted. (Part of our
problem is that we were changing code length - which effects all those
branch offsets.)

Since Andrew's original goal seems in the area of code scheduling, in my
mind, it'd be better to hack on gcc to produce the schedules you want. All
the information is there, and if it isn't you can change the compiler to
synthesize it!
-- 
Chuck Lins, Apple Computer, Inc. Oberon-2 Paladin  lins@apple.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: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
Newsgroups: comp.compilers
Subject: Re: Wanted: a program that calulates the maximal stack depth
Keywords: code, storage
Date: 10 Apr 92 17:20:48 GMT
Article-I.D.: comp.92-04-047
Reply-To: eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig)
Organization: The Johns Hopkins University CS Department

In article <92-04-044@comp.compilers> hays@ssd.intel.com (Kirk Hays) writes:
>In article <92-04-029@comp.compilers>, samuel@nada.kth.se writes:
>|> ... I need a utility that calculates the maximal
>|> used-up stack space for each function in the code.
> ...
>What you need to do is to enumerate all instructions that
>change the top of stack (ENTER, EXIT, CALL, PUSH, POP, etc. as a
>hypothetical set), and all instructions that cause a change of flow of
>control.  That's all that you need to parse, and awk scripts are a fast
>and dirty way to implement the simple parsing that's needed.

	Sorry to rain on everyone's parade, but calculating the maximum
stack space used by a program is undecidable.  (More precisely, deciding
if a program uses less than k elements of the stack is undecidable.)
While, as Kirk points out, it's easy to determine how much stack space a
piece of _straight_line_ code uses, if a program is allowed to have
_single_ loop it is possible to code up a Turing machine, using the stack
as the tape.  If we could determine the maximum amount of stack space this
program could use, then we could determine if the machine would halt or
not.

	Of course, if we limit ourselves to programs without recursion, or
containing only loops that use zero stack space within the loop, this
problem goes away, but I don't think that these are very interesting
programs, or address the original poster's question.
[As with many undecidable or NP-complete questions, there are easily solvable
subsets that are often quite useful.  In this case, if you are trying to
ensure that your embedded application won't use more stack RAM than is
physically present in the system, both the program and and question can be
pretty interesting, at least to some people.  -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Xref: sparky comp.compilers:746 comp.programming:769 comp.lang.c:7315
From: suitti@ima.isc.com (Stephen Uitti)
Newsgroups: comp.compilers,comp.programming,comp.lang.c
Subject: Re: Is there a way of generating code for x/const without division?
Keywords: code, arithmetic, optimize
Date: 3 Apr 92 00:58:21 GMT
Reply-To: suitti@ima.isc.com (Stephen Uitti)
Organization: Interactive Systems, Cambridge, MA 02138-5302

In article <92-04-018@comp.compilers> jeremy@sw.oz.au (Jeremy Fitzhardinge) writes:
>I've been playing with a simple code generator for RISC CPUs.  One of the
>simple peephole optimisations it does is to replace multiplies by
>constants with a series of shift/adds rather than using the general
>multiplication.
>
>I'm wondering whether a similar thing can be done for divide and modulo,
>such that they are implemented by the code generator as a sequence of
>simple instructions that is more efficient (in time) than the more general
>way of performing divide/modulo.

The code to use will vary from CPU to CPU.  For a z80, divide is not
supplied.  Neither is multiply.  Divide can be very painful.  Ten years
ago, I implemented a 32 bit add, subtract, multiply & divide subroutine
set.  Later, I used it for printing decimal numbers.  Divide by ten using
the divide routine was so slow (on a 2 MHz z80) that it couldn't keep
ahead of a 180 cps printer.  I resorted to a table of constants: 10, 100,
1000, ..., 1000000000, and did adds and subtracts of these things,
counting the number of times needed to cross zero.  I even switched to 16
bit arithmetic when the result became 10,000 or less.  This was lots
faster, and certainly fast enough.  In my case it had the aditional
advantage of yielding digits sooner (left to right), so that they could be
entered into the output queue before the computation of the entire number
was completed.  However, with a CPU that has integer divide, even if
divide takes 30 times as long as add, it is still probably faster to do
the divide.

For unsigned integers, divide by constant-power-of-two can use right
shift.  This will probably be fastest on any CPU, even a z80.  One could
imagine, say, a vector computer that has vector multiply, but not vector
shift...

For Dec's Alpha, there is a double precision multiply that can be used for
divide-by-constant.  You multiply by some sort of reciprocal and the
answer is in half of the multiply's answer.  This might be handy for 16
bit divides where 32 bit multiplies are available.  I haven't seen anyone
do this for common workstation class CPUs.  It may be quicker even if both
multiply and divide are available in hardware, since multiply tends to be
faster than divide.  It may be a real win on, say, Sun's Spark machines,
since divides are "helped" by a "divide step" instruction, which must be
repeated multiple times.

If you can do a divide with multiply, you should be able to use another
multiply and subtract to get modulus.  Again, this may or may not be worth
it.

Stephen.
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers,comp.lang.functional
From: eigenstr@nyssa.cs.rose-hulman.edu (Todd R. Eigenschink)
Subject: Re: Compiler for Toy/Ada in SML/NJ
Keywords: ML, FTP, Ada
Reply-To: eigenstr@nyssa.cs.rose-hulman.edu (Todd R. Eigenschink)
Organization: Rose-Hulman Institute of Technology
Date: Tue, 7 Apr 1992 18:04:42 GMT

bhatiaa@polly.cs.rose-hulman.edu (Amit Bhatiani) writes:
>[ the Ada in ML compiler is at]  master.cs.rose-hulman.edy
>   137.112.40.10

Make that Master.CS.Rose-Hulman.Edu (still 137.112.40.10).  As if you
didn't guess that already...

For those of you who are interested, there's also a C version of
pretty much the same compiler (not as elaborate, and written by me :)
which I'll put there as well.

--
Todd Eigenschink (eigenstr@CS.Rose-Hulman.Edu)
Assistant System Manager, News Administrator
Rose-Hulman Institute of Technology, Terre Haute, IN
-- 
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@citr.uq.oz.au (Peter Klavins)
Subject: Re: Need -GOOD- 8051 C compiler ...
Keywords: C
Reply-To: peter@citr.uq.oz.au (Peter Klavins)
Organization: Prentice Centre, University of Queensland
Date: Tue, 14 Apr 1992 03:46:34 GMT

dwight@rock.concert.net (Dwight Frye -- Systems Development Group) writes:
>Basically .. I am looking for the -BEST- 8051 C compiler out there.

I have had experience with HiTech.  They provide cross-assemblers and
C-compilers for all sorts of platforms, from 8051 to 680x0 to 32-bit
80x86.  Their stuff is well respected.  Try clyde@hitech.com.au.  If that
doesn't work, I'll do a bit of digging in memory and phone book.
--
 Peter Klavins    Internet: peter@citr.uq.oz.au   Fidonet:    3:640/821
 Centre for Information Technology Research       Phone: +61 7 365 4321
 University of Queensland QLD 4072 Australia      Fax:   +61 7 365 4399
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.