From: Steven Sharp (sharp@cadence.com)
Date: Thu Aug 15 2002 - 17:30:15 PDT
Precedence: bulk
The following reply was made to PR errata/84; it has been noted by GNATS.
From: Steven Sharp <sharp@cadence.com>
To: etf-bugs@boyd.com
Cc:
Subject: Re: errata/84: Should @* include delay controls?
Date: Thu, 15 Aug 2002 20:24:21 -0400 (EDT)
> > > In the general case, I believe that the question of
> > > whether a variable is guaranteed to be assigned before being
> > > used can be reduced to the halting problem, and is therefore
> > > uncomputable.
>
> Come now, this is absolutely not true.
I am afraid that you are incorrect about this. It is impossible to
write an algorithm that can determine this about an arbitrary piece
of code. With a little more thought, I was able to produce a proof
of the fact, similar to the proof that the halting problem is
uncomputable.
> Education on Def Use chaining has been an integral part of every
> compiler class at a university for the past 25 years and the basic
> depth first search iterative algorithms were described in a survey
> paper, sumerizing past work, by Jeffery Ullman and and John Kam in
> the Journal of the ACM in 1976.
Education on computability has been a part of the curriculum too, and
Alan Turing demonstrated that the halting problem was uncomputable
in 1936. I have been educated in all of these areas.
> Over the the last 25 years these techniques have been refined (I like
> the papers by Jeanne Ferrante in 1991, "Automatic constructions of
> sparse data flow evaluation graphs."
These algorithms can only compute approximations of the desired result.
In many cases, they can guarantee that a variable will be assigned before
being read. In others, they cannot be sure, and must assume the worst
case. Different algorithms may differ in what they can get exact answers
for, but none of them can do so for arbitrary code.
> Fundamentally if what you said was true, synthesis tools would not
> work, and optimizing compilers would not work.
Not all code is accepted by synthesis tools, and optimizing compilers
have the option of not applying an optimization if they are not sure
it is legal. Conservative approximations are adequate for these uses.
We cannot define the behavior of the language in terms of an algorithm
that does not and cannot exist. That leaves several choices:
1. Leave the sensitivity list independent of whether variables could
get values from outside the block. That is how it is now.
2. Specify the exact algorithm to be used to approximate the computation
of whether a variable can get its value from outside the block.
3. Specify that simulators can leave variables out of the sensitivity
list if they can determine that they never get a value from outside
the block, by whatever algorithm they like. This could result in
different simulators producing different results if the block has
side effects.
Note that if the block has no visible side effects (which should be true
of any truly combinational code), a simulator can already optimize the
sensitivity list if it likes, using whatever conservative approximation
it likes. Its behavior would be equivalent to the standard behavior and
therefore legal. The only advantage of option 3 above is if there are a
significant number of blocks which have side effects or which the compiler
can't be sure don't have side effects (since this is uncomputable too).
I don't know how common this will be.
Steven Sharp
sharp@cadence.com
This archive was generated by hypermail 2.1.4
: Thu Oct 10 2002 - 09:24:28 PDT
and
sponsored by Boyd Technology, Inc.