gerda@kulcs.uucp (Gerda Janssens) (02/06/90)
The efficiency of 'X1 is X0 + 1' can substantially be increased if at compile time we known that it is actually destructive assignment and that we can safely reuse the memory cel of X0 for X1. This kind of information can be derived by doing global analysis of the PROLOG program. At our department a framework for abstract interpretation has been developed and one of the applications is concerned with detecting opportunities for compile time garbage collection, as is required for the example at hand. A. Mulkers, W. Winsborough and M. Bruynooghe, Analysis of Shared Data Structures for Compile-time Garbage Collection in Logic Programs, submitted for ICLP'90.
andrewt@cs.su.oz (Andrew Taylor) (02/08/90)
>The efficiency of 'X1 is X0 + 1' can substantially be increased >if at compile time we known that it is actually destructive assignment >and that we can safely reuse the memory cel of X0 for X1. >This kind of information can be derived by doing global analysis of the >PROLOG program. At our department a framework for abstract interpretation >has been developed and one of the applications is concerned with detecting >opportunities for compile time garbage collection, as is required for the >example at hand. I don't think this is relevant. Expressions like this can be compiled efficiently, re-using memory-locations/registers without global analaysis for compile-time garbage collection. This analysis becomes useful when compund terms are involved. Andrew
gerda@kulcs.uucp (Gerda Janssens) (02/12/90)
In <703@cluster.cs.su.oz> andrewt@cluster.cs.su.oz (Andrew Taylor) replies : > >The efficiency of 'X1 is X0 + 1' can substantially be increased > >if at compile time we known that it is actually destructive assignment > >and that we can safely reuse the memory cel of X0 for X1. > >This kind of information can be derived by doing global analysis of the > >PROLOG program. ... > I don't think this is relevant. Expressions like this can be compiled > efficiently, re-using memory-locations/registers without global > analaysis for compile-time garbage collection. This analysis > becomes useful when compund terms are involved. Actually, I was referring to the space efficiency of the 'X1 is X0 + 1' solution. In order to justify the impact of global analysis for compile-time garbage collection, we need the context in which the 'X1 is X0 + 1' expression occurs. 1) p(..) :- ... p(X0) :- X1 is X0 + 1 , p(X1). As X1 is a temporary variable, it is never stored in a memory cel (on the stack or on the heap). Obviously, in this case does not benefit from the above kind of global analysis. (Observe that we can only safely reduce 'X1 is X0 + 1' to an increment if we know that X0 is an integer. Therefore we need 'type'-information derivable by global analysis) 2) p( f(X0), f(X1)) :- X1 is X0 + 1 . Whether we can reuse the memory of the structure 'f(X0)' for 'f(X1)' is determined by the information provided by the global analysis for compile-time garbage collection : if the second argument of the call is free and the first argument is known to be DEAD, the structure 'f(X0)' can be reused for 'f(X1)'. Therefore, we need to overwrite 'X0' by 'X1'.