llvm dev - Jul 2007 - [LLVMdev] PassManager Error

On Jul 26, 2007, at 11:25 AM, David Greene wrote:
> On Thursday 26 July 2007 11:48, Devang Patel wrote:
>
>> If in register allocator you have requested another higher level pass
>> after LiveVariableAnalysis pass then this may happen.
>
> Can you explain why this is so?  I would assume that I could  
> declare Pass
> dependencies in any order.  The manual certainly doesn't say  
> anything about
> restricions like this.  Shouldn't a Pass just be a Pass that can be  
> run?
A pass is not just a pass. It depends on the the level it operates  
on. A function level pass operates on all functions and a module  
level pass works on entire module. For example,

If pass sequence is - ModuleLevelPass A, FunctionLevelPass B,  
FunctionLevelPass C, ModuleLevelPass D then

For each Module
	run ModuleLevelPass A
	for each function in this module
		run FunctionLevelPass B
		run FunctionLevelPass C
	run ModuleLevelPass D
	

Now, if pass sequence is - ModuleLevelPass A, FunctionLevelPass B,   
ModuleLevelPass D, FunctionLevelPass C then

For each Module
	run ModuleLevelPass A
	for each function in this module
		run FunctionLevelPass B
	run ModuleLevelPass D
	for each function in this module
		run FunctionLevelPass C


In this situation, while processing 'foo' FunctionLevelPass C can not  
use analysis info generated by FunctionLevelPass B for 'foo'.

So if FunctionLevelPass C is requiring FunctionLevelPass B and  
ModuleLevelPass D in that order then you may see mentioned  
assertions. I just checked in patch to help investigate such  
failures. Add --debug-pass=Structure on the 'opt' command line to  
understand what is going on.

I welcome patches to update manual to explain this clearly.

-
Devang

On Friday 27 July 2007 15:15, Devang Patel wrote:
> Now, if pass sequence is - ModuleLevelPass A, FunctionLevelPass B,
> ModuleLevelPass D, FunctionLevelPass C then
>
> For each Module
> 	run ModuleLevelPass A
> 	for each function in this module
> 		run FunctionLevelPass B
> 	run ModuleLevelPass D
> 	for each function in this module
> 		run FunctionLevelPass C
>
>
> In this situation, while processing 'foo' FunctionLevelPass C can
not
> use analysis info generated by FunctionLevelPass B for 'foo'.
Why?  I expect the answer is something like, "because B doesn't exist 
anymore,"  or, "because you processed function 'bar' with B
after 'foo.'"
But why?  B doesn't _have_ to exist and it shouldn't necessarily matter
in what order PassManager processes functions.  Only the information
that pass B generates for foo need exist.

If you're running module-level passes anyway, you're probably burning a
bit
of memory to hold state, so maybe keeping around information for all functions
is feasible.  I don't know.

Yes, I understand that these questions imply rethinking how PassManager
works.  That's why I'm asking them.  I reordered my code and got things
to
work but it's always good to take a step back from time-to-time and ask
fundamental questions.  Even if no changes are immediately forthcoming,
it at least helps to identify areas of potential future work.

                                               -Dave

On Jul 27, 2007, at 3:39 PM, David Greene wrote:
> On Friday 27 July 2007 15:15, Devang Patel wrote:
>
>> Now, if pass sequence is - ModuleLevelPass A, FunctionLevelPass B,
>> ModuleLevelPass D, FunctionLevelPass C then
>>
>> For each Module
>> 	run ModuleLevelPass A
>> 	for each function in this module
>> 		run FunctionLevelPass B
>> 	run ModuleLevelPass D
>> 	for each function in this module
>> 		run FunctionLevelPass C
>>
>>
>> In this situation, while processing 'foo' FunctionLevelPass C
can not
>> use analysis info generated by FunctionLevelPass B for 'foo'.
>
> Why?  I expect the answer is something like, "because B doesn't
exist
> anymore,"  or, "because you processed function 'bar' with
B after
> 'foo.'"
> But why?  B doesn't _have_ to exist and it shouldn't necessarily  
> matter
> in what order PassManager processes functions.  Only the information
> that pass B generates for foo need exist.
That is not true in LLVM. For example, DominatorTree pass maintains  
Dominator
info.
> If you're running module-level passes anyway, you're probably  
> burning a bit
> of memory to hold state, so maybe keeping around information for  
> all functions
> is feasible.  I don't know.
In general, it is not a good idea to keep info for all components  
around all time for many reasons. Too many to list here.
> Yes, I understand that these questions imply rethinking how  
> PassManager
> works.  That's why I'm asking them.  I reordered my code and got  
> things to
> work but it's always good to take a step back from time-to-time and  
> ask
> fundamental questions.  Even if no changes are immediately  
> forthcoming,
> it at least helps to identify areas of potential future work.
It is not just pass manager, you're asking question regarding LLVM's  
core design.

-
Devang