PassManager and dependencies

Project Infrastructure LLVM Dev List Archives
1

I can't seem to figure out how to tell the PassManager that one Pass requires the results of two other Passes, in such a way that it will not crash itself. Attached file is the simplest possible example of Passes A, B, and C, such that C's getAnalysisUsage(AU) method calls AU.addRequired<A>() and AU.addRequired<B>().

When I try to run opt -load ... -opt-c, it tells me:

opt: PassManagerT.h:348: void PassManagerT<UnitType>::markPassUsed (const PassInfo *, Pass *) [with UnitType = Module]: Assertion `Parent != 0 && "Pass available but not found!"' failed.

I don't grok this error message. Of course, -opt-a and -opt-b both work fine in isolation.

duh.cpp (1008 Bytes)

2

Sorry in advance for taking so long to respond to this issue...

I can't seem to figure out how to tell the PassManager that one Pass
requires the results of two other Passes, in such a way that it will not
crash itself. Attached file is the simplest possible example of Passes

I don't grok this error message. Of course, -opt-a and -opt-b both work
fine in isolation.

You're right, this error message is terrible. As it turns out, all of
your passes invalidate all of the other passes, so C doesn't get A (which
is invalidated by B). The problem turns out to be a really trivial bug:

  virtual void getAnalysisUsage(AnalysisUsage& AU) const {
    AU.preservesAll(); // This is the accessor, not the setter
  }

which should call:
    AU.setPreservesAll();

On a different subject, I noticed that you tried to optimize out the
string overhead for the name() methods:

  virtual const string& name() const
  { static string a("B"); return a; }

instead of a simple:
  virtual const string& name() const { return "B"; }

Because you're trying to be as efficient as possible, here are a few
pointers:
  1. Static variables defined in a function or method impose quite a bit
     of overhead. These static variables are initialized the first time
     the function is executed... which implies that every time the
     function is executed, the check must be performed.
  2. Don't optimize things that don't have to be optimized. In general
     these methods aren't called enough, or only during debugging, so it
     is better to be clear than it is to save a few cycles. As a general
     rule, optimize for clarity, not performance. Often performance comes
     for free with clarity.
  3. If you REALLY want to be efficient, think about other short-cuts. In
     this case, a constant string is always returned. You could change
     the virtual method to always return a const char*, therefore avoiding
     a copy constructor call that may be unneccesary:

  virtual const char *name() const { return "B"; }

     ... but this obviously only works if all of the implementations ONLY
     return static strings.

Anyway, good luck with LLVM. It's good to know that you're digging into
the pass infrastructure stuff. I'll look into renaming the preservesAll
interface to something more obvious in the future. :slight_smile:

-Chris

http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

3

Chris Lattner wrote:

I don't grok this error message. Of course, -opt-a and -opt-b both work
fine in isolation.
   
You're right, this error message is terrible. As it turns out, all of
your passes invalidate all of the other passes, so C doesn't get A (which
is invalidated by B). The problem turns out to be a really trivial bug:

virtual void getAnalysisUsage(AnalysisUsage& AU) const {
   AU.preservesAll(); // This is the accessor, not the setter
}

which should call:
   AU.setPreservesAll();

Ouch. mea culpa. It would be a good idea for preservesAll and preservesCFG to have the same interface (since I, at least, thought that they did :wink:

On a different subject, I noticed that you tried to optimize out the
string overhead for the name() methods:

virtual const string& name() const
{ static string a("B"); return a; }

instead of a simple:
virtual const string& name() const { return "B"; }

Do you think it's a good idea to return a reference to a temporary?

Because you're trying to be as efficient as possible, here are a few
pointers:
1. Static variables defined in a function or method impose quite a bit
    of overhead. These static variables are initialized the first time
    the function is executed... which implies that every time the
    function is executed, the check must be performed.

Are you claiming that most compilers are so grossly inefficient that checking on every call is more expensive than creating the object on every call? If you're going to be passing around objects, they have to be created somewhere. By declaring things static (and preferably const as well), the compiler has the opportunity to optimize away the constructor call.

2. Don't optimize things that don't have to be optimized. In general
    these methods aren't called enough, or only during debugging, so it
    is better to be clear than it is to save a few cycles. As a general
    rule, optimize for clarity, not performance. Often performance comes
    for free with clarity.

What could be more clear than "static X x; return x;"?

3. If you REALLY want to be efficient, think about other short-cuts. In
    this case, a constant string is always returned. You could change
    the virtual method to always return a const char*, therefore avoiding
    a copy constructor call that may be unneccesary:

A good reference-counted string implementation should efficiently handle returning a const& as in this case. Of course, this is example code that I hacked out in about ten minutes just to illustrate the problem, so I would say that the goal is to optimize for speed of coding: I wrote it as it came to me.

4

Ouch. mea culpa. It would be a good idea for preservesAll and
preservesCFG to have the same interface (since I, at least, thought that
they did :wink:

Yup, I'll look into changing that when I have spare time (ha ha).

>instead of a simple:
> virtual const string& name() const { return "B"; }

Do you think it's a good idea to return a reference to a temporary?

Oops, sorry about that, I forgot to drop the reference:

virtual string name() const { return "B"; }

Are you claiming that most compilers are so grossly inefficient that
checking on every call is more expensive than creating the object on
every call? If you're going to be passing around objects, they have to
be created somewhere. By declaring things static (and preferably const
as well), the compiler has the opportunity to optimize away the
constructor call.

The compiler always has the opportunity to optimize away the constructor
call. Remember that if the compiler is thread-capable, that you don't
just have a simple test to see if it's initialized, you have to at least
have a second chance lock or atomic operation, which is slow and bigger.
Regardless of locking, accessing global variables (Which statics
effectively are) is a good way to stop the optimizer dead in its tracks,
especially with GCC.

To emphasize my main point though, I wasn't trying to say that the above
would be faster, my point is that it _doesn't need to be_ fast.
Premature optimization, evil, and all that.

> 2. Don't optimize things that don't have to be optimized. In general
> these methods aren't called enough, or only during debugging, so it
> is better to be clear than it is to save a few cycles. As a general
> rule, optimize for clarity, not performance. Often performance comes
> for free with clarity.

What could be more clear than "static X x; return x;"?

return X();

Remember you also need the initializer expression.

> 3. If you REALLY want to be efficient, think about other short-cuts. In
> this case, a constant string is always returned. You could change
> the virtual method to always return a const char*, therefore avoiding
> a copy constructor call that may be unneccesary:

A good reference-counted string implementation should efficiently handle
returning a const& as in this case. Of course, this is example code
that I hacked out in about ten minutes just to illustrate the problem,
so I would say that the goal is to optimize for speed of coding: I wrote
it as it came to me.

I understand that this wasn't meant to be the most optimal or thought out
code, I was just trying to get across the fact that it's not a good
default habit to get into for returning constant strings. As it stands,
returning a const char* (if you can) would be MUCH faster than without.

Again in the presence of possible threads, reference counted strings are
MUCH slower than always copying in some cases. A reasonable example of
this discussion is here, but there are many others:

http://www.gotw.ca/publications/optimizations.htm
http://www.gotw.ca/gotw/045.htm

The real point I was trying to make is that clear code is often efficient,
and only when you find that efficiency is actually a problem for a piece
of code should you resort to optimizations like this. Compiler optimizers
can be made smarter for a fixed cost (giving benefits to a wide variety of
codes), but code maintenance has a cost that grows with the complexity of
code (and individual optimizations like this only gives a benefit to one
particular part of the code). Increasing complexity for no real payoff
has no benefit.

-Chris

http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

5

Also sprach Casey Carter:
}
} > 2. Don't optimize things that don't have to be optimized. In general
} > these methods aren't called enough, or only during debugging, so it
} > is better to be clear than it is to save a few cycles. As a general
} > rule, optimize for clarity, not performance. Often performance comes
} > for free with clarity.
} >
} What could be more clear than "static X x; return x;"?
}
Well...actually, the above takes knowing that the "static" in a function
will preserve the variable between calls and only initialize once.
Depending upon the use, "return x" is clearer IMNSHO, especially in the
case you had (where it's a string) or, even better, simply to return the
const char *, as mentioned below.

Bill

} > 3. If you REALLY want to be efficient, think about other short-cuts. In
} > this case, a constant string is always returned. You could change
} > the virtual method to always return a const char*, therefore avoiding
} > a copy constructor call that may be unneccesary:
} >
} >
} A good reference-counted string implementation should efficiently handle
} returning a const& as in this case. Of course, this is example code
} that I hacked out in about ten minutes just to illustrate the problem,
} so I would say that the goal is to optimize for speed of coding: I wrote
} it as it came to me.
}