llvm dev - Jun 2009 - [LLVMdev] 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.

 

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.

 

-- Chris

_________________________________________________________________
Windows Live™ SkyDrive™: Get 25 GB of free online storage.
http://windowslive.com/online/skydrive?ocid=TXT_TAGLM_WL_SD_25GB_062009
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20090610/882369f9/attachment.html>

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