7 Dec 2001 23:38:39 -0500

Related articles |
---|

non recursive algorithm for depth first numbering jeremy.wright@merant.com (Jeremy Wright) (2001-12-03) |

Re: non recursive algorithm for depth first numbering vugluskr@unicorn.math.spbu.ru (2001-12-07) |

From: | vugluskr@unicorn.math.spbu.ru (Roman Shaposhnick) |

Newsgroups: | comp.compilers |

Date: | 7 Dec 2001 23:38:39 -0500 |

Organization: | St.Petersburg University |

References: | 01-12-011 |

Keywords: | analysis, comment |

Posted-Date: | 07 Dec 2001 23:38:39 EST |

X-Comment-To: | Jeremy Wright <jeremy.wright@merant.com> |

I don't know any details about what you're doing, but as a rule of

thumb -- you can always make recursion to be a loop. However, you

won't get rid of some sort of "storage" completely you can

significantly reduce amount of memory used by storing in a heap ( or

equivalent ) only those data items you really need, instead of wasting

stack for procedure's frame and "useless" local variables.

On the other hand, if you have such "deep" recursion you might want to

consider changing algorithm, as well. Again, it all depends on your

requirements.

Thanks,

Roman.

On 3 Dec 2001 20:25:39 -0500, Jeremy Wright wrote:

*>Is there a non recursive algorithm to do depth first numbering, or*

*>optimizations to the standard algorithm (as in Dragon 2, pp 662) that*

*>reduce the amount of recursion.*

*>*

*>The issue arises as I am processing the basic block graph for a*

*>perform range in Cobol. The graph can be extremely big. Additionally,*

*>perform statements occur in a basic block by themselves (to allow*

*>optimizations across performs, and into/out of perform ranges). This*

*>causes the depth of the graph to be orders of magnitude greater than*

*>would otherwise be the case.*

[Making the recursion stack explicit would certainly speed up the

recursion, but I suspect that in this case it'd be more productive to

look for ways to abstract stuff out at the paragraph level or higher

to avoid much of the recursion altogether. -John]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.