Inlining and virtualization in Clang/LLVM

Project Infrastructure LLVM Dev List Archives
#1

I'm not sure whether this is the exact problem at hand in your example,
but one of the major hurdles llvm suffers when trying to devirtualize
is the second point you made: it doesn't see the invariance of the
table pointer post construction. In your specific example the
constructors are trivial and inlinable so it I'm not sure why llvm
would be having trouble proving the value of the vptr &
devirtualizing. , perhaps due to them being static so the
initialization is contingent on it being the first call (& llvm doesn't
know that the vptr is constant after construction until destruction
begins) & doesn't see the connection across all calls.

So there are a few issues that need to be addressed to help this.

One is some kind of constant range where the front end can promise not
to modify certain values for a range (this might not be correct though
- I remember some argument as to whether it was valid to destroy and
then placement new the same type into that memory before the object
goes out of scope - if so, then it's not obvious if the vptr is
constant in any range) & secondly (at least for the case of non inline
constructors) the ability to provide some kind of assert that, post
construction, the vptr is equal to some known constant. (this assertion
is currently possible with a branch to unreachable, except llvm throws
out the unreachable code in SimplyCFG before any optimizations run - so
we need to see if we can keep them around longer - there are some PRs
filed for this but I haven't made much progress on it

#2

Hello David,

I have been thinking a bit more about this and as I find the problem
quite interesting.

If I get down one level (and revert to implementing objects in C):

#include <stdio.h>

typedef void (*Function)();

void print() { printf("Hello, World!"); }
void nothing() {}

Function get(int i) {
  if (i % 2 == 0) { return &print; }
  return &nothing;
}

int main() {
  Function f = get(2);
  (*f)();
  return 0;
}

Which is admittedly quite similar, generates the following main:

define i32 @main() nounwind uwtable {
  %1 = tail call i32 (i8*, ...)* @printf(i8* getelementptr inbounds
([14 x i8]* @.str, i64 0, i64 0)) nounwind
  ret i32 0
}

This falls out naturally from SSA form, I think. No "constification"
is necessary.

However in our case, it seems that the SSA form (which only references
the pointer to the structure itself, not the v-table pointer), is not
sufficient therefore to allow the optimizer to remember which value
the pointer should have.

Of course, in general I agree that the compiler should be told
explicitly that the value cannot change (otherwise it would not know
that opaque calls are not accessing that particular value within the
structure); at least until the start of the destructor.

I remember a discussion a while ago involving the design and
implementation of those "const-ranges" within the LLVM IR, do you
happen to know where it's at ?

-- Matthieu

#3

I'm not sure where that is, but I've +nlewycky because he's been
thinking about this recently & there are some wrinkles as I alluded to
in my reply. Saying that the vtable pointer is const from
post-construction to pre-destruction isn't quite correct & would break
certain obscure but valid programs. That being said, there is some
kind of lifetime marker we could create & use to indicate the
semantics of the vtable pointer without breaking those programs. (key
here is that C++ cares about how you derive the pointer to the object,
not just its value - if you explicitly destroy an object then
placement new another object over the same space, the implementation
is allowed to assume that the old pointers you had to the object still
point to the same kind of object - but the one returned from placement
new isn't, even though those pointers may have the same value...
that's my understanding/vague description of the issue)

- David

#4

In compilers like Open64, oracle code is put in to retain program functionality.

If (object type == compiler inferred type) direct call of type's method; else virtual call

The question is if the types are inferable. Then it would not be bad if the direct call got inlined and the savings from inlining offset the cost of the condition check.

#5

Right. I’ve got a proposal in PR13940 that Chris has asked me to mail out to llvmdev. I should do that soon, but I wanted to wait until I would have the time to reply to the comments that came up and possibly even implement the result.

Nick

#6

@David: Thanks for bringing Nick here! Indeed I had not considered the
(aweful) placement new issue. Aliasing rules do not really help us
here, since they only consider the dynamic type of the object, and by
calling the destructor explicitly then using placement new we end the
lifetime of the object and then create a new object. I do wonder
though if keeping a reference/pointer to that alive-dead-alive object
is allowed.

@Nick: I believe that your proposal could really help indeed.
Ultimately, it might help trimming the devirtualization method in
Clang to only take care about the "final" attribute.

-- Matthieu

#7

@David: I asked about this in

Regarding your example I believe that it would be illegal to retain a
reference or pointer to an object that is "killed", because that
reference is stale, and the fact that you recreated another (similar)
object in its stead does not matter: after all the allocation routines
reuse storage quite often.

We'll see what the SO folks come up with, I tried but failed to locate
a full explanation in the Standard.

-- Matthieu

#8

Okay, so thanks to the SO folks two different excerpts from the
Standard came up (I am using n3337 here):

In [basic.life]: 3.8/7

If, after the lifetime of an object has ended and before the storage
which the object occupied is reused or
released, a new object is created at the storage location which the
original object occupied, a pointer that
pointed to the original object, a reference that referred to the
original object, or the name of the original
object will automatically refer to the new object and, once the
lifetime of the new object has started, can
be used to manipulate the new object, if:
— the storage for the new object exactly overlays the storage location
which the original object occupied,
and
— the new object is of the same type as the original object (ignoring
the top-level cv-qualifiers), and
— the type of the original object is not const-qualified, and, if a
class type, does not contain any non-static
data member whose type is const-qualified or a reference type, and
— the original object was a most derived object (1.8) of type T and
the new object is a most derived
object of type T (that is, they are not base class subobjects).

=> replacing an object while preserving references to it is okay as
long as the new object is of the exact same type, the v-ptr may thus
have changed in-between but is back to the same value.

=> on the other hand, I envision a difficulty with caching the pointer
to a virtual base, should an implementation dynamically allocate it (I
do not think it is the case in the Itanium ABI thankfully).

In [dcl.init.ref]: 8.5.3/2

A reference cannot be changed to refer to another object after
initialization. [...] Argument passing (5.2.2) and function value
return (6.6.3) are initializations.

=> In direct contradiction with the previous paragraph as far as I can
see, but no allowing v-ptrs to change either.

Did you have more specific concerns or ideas regarding v-ptr
invalidation ? My only concern here would be modelling the semantics
of construction/destruction properly (as according to the Itanium ABI
the v-ptr evolves during those and LLVM as no specific marker for
setup/tearup phases).

-- Matthieu