RE: Compile Time Garbage Collection impossible?

Quinn Tyler Jackson <>
25 Sep 2006 01:12:45 -0400

          From comp.compilers

Related articles
Compile Time Garbage Collection impossible? (2006-09-22)
RE: Compile Time Garbage Collection impossible? (Quinn Tyler Jackson) (2006-09-25)
RE: Compile Time Garbage Collection impossible? (Daniele Terdina) (2006-09-25)
| List of all articles for this month |

From: Quinn Tyler Jackson <>
Newsgroups: comp.compilers
Date: 25 Sep 2006 01:12:45 -0400
Organization: Compilers Central
References: 06-09-119
Keywords: GC
Posted-Date: 25 Sep 2006 01:12:45 EDT asked:

> Why isn't Compile-Time-Garbage-Collection feasible? Consider a Java
> compiler which produces assembly code for a specific target instead of
> Java's bytecode cenario. The objective is to use Java without the need
> for a GC or VM.
> I'm asking why it isn't possible because otherwise there would be at
> least one compiler to use that technique, instead of having to run a
> GC in the VM.
> When a program is compiled, the compiler has to transverse all its
> code to ensure type safety (for safe languages), so what would be the
> problem in "freeing" objects after their scope, or even better, after
> the last reference in their scope?

The general case of static object lifetime analysis would imply a solution
to the Halting Problem.

Consider this case:

function foo (a is object_type_bar)

      if some_function(a) then
            // do nothing
      end if

end function

Static analysis of some_function (in the general case) cannot tell us
whether some_function will return TRUE or FALSE based upon input of the
object a. In the case where it returns TRUE -- a is added to a global
container (and therefore must not be destroyed). In the case where it
returns FALSE, a might have no other references to it upon returning from
foo, and may be destroyed "at will".

This is a very "informal" treatment of the problem. For further
enlightenment, see:

Which contains this statement:

"Determining whether an arbitrary piece of code is unreachable code is
equivalent to solving the halting problem. This means that it is not
possible to correctly locate unreachable code in all cases."

In particular, see this example:

double x = sqrt(2);
if (x > 2)

where we replace xyz with "add_to_some_global_container" and sqrt(2) with:


Where s is some arbitrary Collatz sequence. (Do all Collatz sequences


Quinn Tyler Jackson

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.