[LLVMdev] Dependency graphs supported by the pass manager

[Devang Patel]

Hi Christopher,

On Wed, Jun 10, 2009 at 1:08 PM, Christopher
Wood<chris.wood77 at hotmail.com> wrote:
> Hi all:
>
> I apologize if this is a stupid question, but I haven't found a direct
> statement of what kinds of requirements the Pass Manager imposes on pass
> dependency graphs.  I found a number of bug reports related to unschedulable
> passes (e.g. "Unable to schedule pass" asserts from the pass manager), but
> it isn't always clear if these are true bugs in the scheduling algorithm or
> expected behavior.
>
> Specifically, can anyone tell me what the intended behavior of the Pass
> Manager is in the following scenarios.  In cases I've tested I've included
> the behavior I've seen--I'm using LLVM 2.4.
>
> In all my cases, I'm describing strictly relationships between Function
> Passes.
>
> 1) Cycles in the dependency graph (e.g., schedule A when A depends on B; B
> depends on A)
> In tests the Pass Manager overflows the stack and crashes

The pass manager should raise appropriate assertion here.
>
> 2) A dependency requires rescheduling (e.g. schedule A when A depends on B
> and C; C depends on B; but C doesn't preserve B)
> The Pass Manager should arrive at the sequence B C B A.  Instead I get the
> "Unable to schedule pass" assertion from
> PMDataManager::addLowerLevelRequiredPass.

Here, the work around is to required C before B in pass A.

> 2) A pass depends on mutually exclusive graphs (i.e., schedule C when A
> invalidates B; B invalidates A; C depends on both A and B)
> I haven't tried this yet.
>

I think this is similar to case 1)
-
Devang