PassManager Mysteries

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

PassManager Mysteries

dag-7
I've never been able to figure this one out:

llvm/lib/VMCore/PassManager.cpp:938: virtual void
llvm::PMDataManager::addLowerLevelRequiredPass(llvm::Pass*, llvm::Pass*):
Assertion `0 && "Unable to handle Pass that requires lower level Analysis
pass"' failed.

In the past, I've resolved this by disabling random addRequired calls in the
offending Pass, even when those dependencies are real.

So what does this assert mean, exactly?  How do I find out just what is wrong
with the Pass dependencies?

                                             -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: PassManager Mysteries

Devang Patel

On Jan 28, 2008, at 4:27 PM, David Greene wrote:

> I've never been able to figure this one out:
>
> llvm/lib/VMCore/PassManager.cpp:938: virtual void
> llvm::PMDataManager::addLowerLevelRequiredPass(llvm::Pass*,  
> llvm::Pass*):
> Assertion `0 && "Unable to handle Pass that requires lower level  
> Analysis
> pass"' failed.
>
> In the past, I've resolved this by disabling random addRequired  
> calls in the
> offending Pass, even when those dependencies are real.

If those dependencies were real then I expect that you won't be able  
to disable it because otherwise your pass won't work because of lack  
of required information ;)

> So what does this assert mean, exactly?

In simple word, pass manager is unable to fulfill your request.

>  How do I find out just what is wrong
> with the Pass dependencies?

Use -debug-pass=Details and find out which pass dependency is not  
handled.

-
Devang
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: PassManager Mysteries

Vikram S. Adve


On Jan 28, 2008, at 6:38 PM, Devang Patel wrote:


So what does this assert mean, exactly?

In simple word, pass manager is unable to fulfill your request.

Can you explain this one in complex words then? :^)  I've encountered the same problem.

--Vikram


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: PassManager Mysteries

Owen Anderson-2
From experience, an important point that is often forgotten is that the order of declaration of dependencies matter.  If you declare that you require pass A, and then pass B, and B doesn't preserve A, you'll get an error like this.

Just some advice from having had similar problems in the past.

--Owen

On Jan 28, 2008, at 9:01 PM, Vikram S. Adve wrote:



On Jan 28, 2008, at 6:38 PM, Devang Patel wrote:


So what does this assert mean, exactly?

In simple word, pass manager is unable to fulfill your request.

Can you explain this one in complex words then? :^)  I've encountered the same problem.

--Vikram

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

smime.p7s (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: PassManager Mysteries

greened
In reply to this post by Devang Patel
On Monday 28 January 2008 06:38:25 pm Devang Patel wrote:

> If those dependencies were real then I expect that you won't be able
> to disable it because otherwise your pass won't work because of lack
> of required information ;)

Not true.  If the information happens to be current (in my case it
always is), everyone's happy.

                                       -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: PassManager Mysteries

greened
In reply to this post by Owen Anderson-2
On Monday 28 January 2008 09:31:11 pm Owen Anderson wrote:
>  From experience, an important point that is often forgotten is that
> the order of declaration of dependencies matter.  If you declare that
> you require pass A, and then pass B, and B doesn't preserve A, you'll
> get an error like this.
>
> Just some advice from having had similar problems in the past.

I'll have to double-check my code, but I don't think I have this particular
problem.

But in any case, isn't the whole point of PassManager that it can handle
situations like this?  Why wouldn't it just run Pass A twice, or run it
in the correct order (after Pass B)?

This strikes me as rather fragile.  And my experience has been that
that is in fact exactly the case.

                                          -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: PassManager Mysteries

John Criswell-2
In reply to this post by Vikram S. Adve
Dear All,

I had a similar error back in December; there are a number of email
exchanges about it on llvmdev in December 2007; a search through the
archives might shed some light on my PassManager does this.

If you're updating a pass from pre-LLVM 2.0 to post-LLVM 2.0, you should
be aware that the pass manager in LLVM 2.x is used only for scheduling
dependent *analysis* passes.  If you need to ensure that transform
passes are run in a certain order or before an analysis pass, you need
to order that explicitly by adding the passes to the PassManager object
in the correct order.

In my case, SAFECode used the PassManager's dependency checking to
ensure that the Automatic Pool Allocation transform was run before the
SAFECode analysis and transform passes.  This worked in LLVM 1.9; it
doesn't work in LLVM 2.x.

-- John T.

Vikram S. Adve wrote:

>
>
> On Jan 28, 2008, at 6:38 PM, Devang Patel wrote:
>
>>>
>>> So what does this assert mean, exactly?
>>
>> In simple word, pass manager is unable to fulfill your request.
>
> Can you explain this one in complex words then? :^)  I've encountered
> the same problem.
>
> --Vikram
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: PassManager Mysteries

Owen Anderson-2
In reply to this post by greened

On Jan 28, 2008, at 9:55 PM, David A. Greene wrote:
> But in any case, isn't the whole point of PassManager that it can  
> handle
> situations like this?  Why wouldn't it just run Pass A twice, or run  
> it
> in the correct order (after Pass B)?

I assume there are situations in which a pass cannot be recomputed,  
but we really need Devang for that.  All I know is that, most of the  
times I've encountered this problem, it was fixable just by reordering  
the declarations.

--Owen
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

smime.p7s (3K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: PassManager Mysteries

dag-7
In reply to this post by greened
On Monday 28 January 2008 21:55, David A. Greene wrote:

> On Monday 28 January 2008 09:31:11 pm Owen Anderson wrote:
> >  From experience, an important point that is often forgotten is that
> > the order of declaration of dependencies matter.  If you declare that
> > you require pass A, and then pass B, and B doesn't preserve A, you'll
> > get an error like this.
> >
> > Just some advice from having had similar problems in the past.
>
> I'll have to double-check my code, but I don't think I have this particular
> problem.

Well, I was wrong.  I found the missing addPreserved and everything's
hunky-dorey.

BTW, -debug-pass=Details wasn't all that helpful.  An excerpt:

    Live Interval Analysis
    MachineDominator Tree Construction
    Machine Natural Loop Construction
    Iterated Register Coalescing
llvm/lib/VMCore/PassManager.cpp:938: virtual void
llvm::PMDataManager::addLowerLevelRequiredPass(llvm::Pass*, llvm::Pass*):
Assertion `0 && "Unable to handle Pass that requires lower level Analysis
pass"' failed.
ftn-2116 ftn: INTERNAL  

That doesn't say anything about which pass triggered the error or which
dependency was unavailable.  PassManager should be able to dump
this information.

                                          -Dave
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: PassManager Mysteries

Devang Patel
In reply to this post by John Criswell-2

On Jan 28, 2008, at 8:11 PM, John Criswell wrote:

> If you're updating a pass from pre-LLVM 2.0 to post-LLVM 2.0, you  
> should
> be aware that the pass manager in LLVM 2.x is used only for scheduling
> dependent *analysis* passes.

I believe that was the intention from day one otherwise original  
author would not have used term "analysis" everywhere in code and  
interface that deals with pass dependencies.

> If you need to ensure that transform
> passes are run in a certain order or before an analysis pass, you need
> to order that explicitly by adding the passes to the PassManager  
> object
> in the correct order.
>
> In my case, SAFECode used the PassManager's dependency checking to
> ensure that the Automatic Pool Allocation transform was run before the
> SAFECode analysis and transform passes.  This worked in LLVM 1.9; it
> doesn't work in LLVM 2.x.

On the other side, LLVM 2.x PassManager add much needed flexibility  
and new features.

-
Devang



_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: PassManager Mysteries

Devang Patel
In reply to this post by greened

On Jan 28, 2008, at 7:55 PM, David A. Greene wrote:

> On Monday 28 January 2008 09:31:11 pm Owen Anderson wrote:
>> From experience, an important point that is often forgotten is that
>> the order of declaration of dependencies matter.  If you declare that
>> you require pass A, and then pass B, and B doesn't preserve A, you'll
>> get an error like this.
>>
>> Just some advice from having had similar problems in the past.
>
> I'll have to double-check my code, but I don't think I have this  
> particular
> problem.
>
> But in any case, isn't the whole point of PassManager that it can  
> handle
> situations like this?  Why wouldn't it just run Pass A twice, or run  
> it
> in the correct order (after Pass B)?

If you realize that function level analysis pass only preserves and  
servers analysis info for one function at a time then current pass  
manager behavior is obvious. If you insert a module level pass between  
two function level passes then these two function level passes can not  
share analysis information.

Let's develop one example step by step to understand this.

----------------------------------------------------------------

- PM (Pass Manager) is asked to run function level pass F1.
        1) F1 requires function level analysis info A1.

PM will arrange a function level pass manager to handle this request.

        FPManager
                - execute A1 on function foo()
                - execute F1 on function foo()
                - execute A1 on function bar()
                - execute F1 on function bar()
        ...

----------------------------------------------------------------

- PM is asked to run function level pass F1.
        1) F1 requires function level analysis info A1.
                A1 requires and preserves Module level analysis info M1.

PM will arrange a module level pass manager to handle this request.

        MPManager
                - execute M1 on function foo(), bar()
                FPManager
                        - execute A1 on function foo()
                        - execute F1 on function foo()
                        - execute A1 on function bar()
                        - execute F1 on function bar()

----------------------------------------------------------------

Now if PM is asked to run function level pass F1.
        1) F1 requires function level analysis info A1.
                A1 requires Module level analysis info M1. A1 does not preserve M1.
        2) F1 requires function level analysis info A2.
                A2 does not preserve A1.

PM will try to arrange module level pass manager to handle this request.

        MPManager
                - execute M1 on function foo(), bar()
                FPManager
                        - execute A1 on function foo()
                        - execute A2 on function foo()
                        - execute F1 on function foo() /* oops, can not run F1, because A1  
for foo() is destroyed */

As you suggested, If after executing A2 function pass manager reorder  
A1 then following will happen

        MPManager
                - execute M1 on function foo(), bar()
                FPManager
                        - execute A1 on function foo()
                        - execute A2 on function foo()
                                /* Here, PM can not reorder A1 again for M1 for foo() is destroyed  
by previous A1 run*/
                                /* This means can not order F1 here because A1 is missing */
                        - execute A1 on function bar()
                        - execute A2 on function bar()
        /*And now, run reordered A1 before running F1 */
        MPManager
                - execute M1 on function foo(), bar()
                FPManager
                        - execute A1 on function foo()
                        - execute F1 on function foo() /* oops, A2 for foo() is not  
available. */

  If A2 is reordered again then A1 will have to be  re-reordered and  
now you are running in an infinite loop.  PM does not have ways to  
preserve analysis A1 for foo() and restore it back.

So the solution is to change order of required analysis.

- PM is asked to run function level pass F1.
        1) F1 requires function level analysis info A2.
                A2 does not preserve A1.
        2) F1 requires function level analysis info A1.
                A1 requires Module level analysis info M1. A1 does not preserve M1.

This will allow PM to order

        MPManager
                - execute M1 on function foo(), bar()
                FPManager
                        - execute A2 on function foo()
                        - execute A1 on function foo()
                        - execute F1 on function foo() <-- we can do this !
                        - execute A2 on function bar()
                        - execute A1 on function bar()
                        - execute F1 on function bar() <-- we can do this !

        ... and now world is a better place to live!

As always, I welcome patches to improve diagnosis in this area. IIRC,  
Owen added patches to dump PM state to clarify what is going on.

-
Devang
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: PassManager Mysteries

Vikram S. Adve
Ok, thanks!  I'm copying llvmdev again because others had asked about  
this as well.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.org/



On Jan 29, 2008, at 4:48 PM, Devang Patel wrote:

>
> On Jan 29, 2008, at 2:40 PM, Vikram S. Adve wrote:
>
>> Devang,
>>
>> I had asked earlier what the message about "lower level analysis
>> info" meant.  Can you please explain that in particular?  Thanks!
>
> Now, Module Level pass may required Function Level analysis info
> (dominator info). PM uses on the fly function pass manager to provide
> this on demand. In this situation, in PM terminology, module level
> pass is requiring lower level analysis info.
>
> When PM is not able to order required analysis info, PM checks whether
> any lower level manager will be able to provide this analysis info on
> demand or not.
> -
> Devang
>
>
>

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev