[LLVMdev] Dependency graphs supported by the pass manager

Christopher Wood chris.wood77 at hotmail.com
Wed Jun 10 13:08:31 PDT 2009

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090610/882369f9/attachment.html>

More information about the llvm-dev mailing list