Re: Ada files now checked in

[Daniel Berlin <dan at cgsoftware dot com>]

On Sunday, October 7, 2001, at 02:26  PM, Diego Novillo wrote:

> On Sun, 07 Oct 2001, Daniel Berlin wrote:
>
>> ....
>>>   Building the FUD chains is like O(SxNxE) (could be wrong, I'm
>>>   quoting from memory).  There is a linear phi placing algorithm
>>>   which I plan to switch to.
>>
>> You meen Sreedhar and gao's?
>>
> Yes.  These two:
>
> @InProceedings{	  bib:johnson.ea-94,
>   title		= "The Program Structure Tree: Computing Control Regions in
> 		  Linear Time",
>   author	= "R. Johnson and D. Pearson and K. Pingali",
>   booktitle	= pldi94,
>   address	= "Orlando, Florida",
>   month		= jun,
>   year		= "1994",
>   pages		= "171--185"
> }
>
> @InProceedings{	  bib:sreedhar.ea-95,
>   author	= "V. C. Sreedhar and G. R. Gao",
>   title		= "A Linear Time Algorithm for Placing ${\phi}$-nodes",
>   pages		= "62--73",
>   isbn		= "0-89791-692-1",
>   booktitle	= popl95,
>   month		= jan,
>   publisher	= "ACM Press",
>   address	= "New York, NY, USA",
>   year		= "1995"
> }
>
>> If so, i've got it coded already for the tree ssa stuff.
>>
> Cool.  Mind submitting the patch?
>
It's not a single patch (functionally, anyway), but i'll submit it 
sometime soon.
I construct an explicit dominator tree (from the idoms), then augment it 
with the DJ graph info.
This is because APT ("APT: a data structure for optimal control 
dependence computation", 
http://www.acm.org/pubs/citations/proceedings/pldi/207110/p32-pingali/) 
uses a dominator tree augmented with info as well, so it didn't make 
sense to just make a dj-graph specific version.
It's of course, largely non-tree-ssa specific, however, i used it in 
doing loop optimizations for tree-ssa.

> Thanks.  Diego.