Re : incrementing values 
Author Message
 Re : incrementing values

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.



Sat, 25 Jul 1992 17:15:06 GMT  
 Re : incrementing values

Quote:
>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



Mon, 27 Jul 1992 07:11:29 GMT  
 Re : incrementing values


Quote:
> >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'.



Fri, 31 Jul 1992 18:03:50 GMT  
 
 [ 3 post ] 

 Relevant Pages 

1. How can I Increment values logarithmically?

2. auto increment value starting from n

3. incrementing values

4. incrementing slot value

5. Spin Box increments less than 1- from .0153 to .98438 w/.0153 increment changes

6. Generating a value from a VALUE ERROR

7. Comparing value in an input field to any value from another file

8. C4 - Autoincrementing default values for multi-valued template symbols

9. Copying one array value into subsequent array values

10. value dependent boolean to retain its sense when values would change boolean

11. how to set knobs to the dicreet values indicated and no values in between

12. sampling waveform values and writing corresponding time values

 

 
Powered by phpBB® Forum Software