Complexity of control flow graphs?

[Peter B. Kessler]

Mostly, intellectual curiosity.  More immediately, we are reusing the server compiler for something new and our constraints are different enough (way simpler) that we are thinking of rewriting the scheduler.  So I was looking at how the current code works and where it might make sense to apply different assumptions or simplify things.  The performance geek in me likes the trail from Lengauer-Tarjan from 1979 through Cooper-Harvey-Kennedy to Georgiadis-Tarjan-Werneck in 2006 as people learned what matters.  My favorite quote is

    We have not included linear-time algorithms in our study; they are
    significantly more complex and thus unlikely to be faster than LT
    or SLT in practice.

Maybe just knowing "It's not the tallest nail" is enough of an answer.  Thanks.

			... peter

Tom Rodriguez wrote:
> I don't think anyone has looked at this code in a long time.  It's not 
> the tallest nail compile time wise and we haven't seen any bugs so it's 
> just been left alone.  Why the interest?
> 
> tom
> 
> On Aug 12, 2009, at 11:40 AM, Peter B. Kessler wrote:
> 
>> Does anyone have a sense of the complexity of the control flow graphs 
>> seen by the HotSpot compiler?  For example, how many nodes and edges 
>> are examined by PhaseCFG::Dominators (or PhaseIdealLoop::Dominators)?
>>
>> In light of
>>
>>   http://jgaa.info/accepted/2006/GeorgiadisTarjanWerneck2006.10.1.pdf
>>
>> is there any point (other than reducing complexity!) in changing the 
>> LINK and EVAL methods to only do path compression, and not try to 
>> balance the trees used by LINK?
>>
>> Has anyone tried other dominator algorithms in there, e.g.,
>>
>>   http://www.cs.rice.edu/~keith/EMBED/dom.pdf
>>
>> to see if it matters?
>>
>> Thanks for any insights you have on this issue.
>>
>>             ... peter
>