Dependency graphs supported by the pass manager

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

  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.

  3. 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.

– Chris

Hi Christopher,

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)