GSoC topic: precise lifetimes in GIMPLE

GSoC topic: precise lifetimes in GIMPLE

[Alexander Monakov]

Hi,

following the conversation in PR 90348, I wonder if it would make sense
to suggest the idea presented there as a potential GSoC topic? Like this:

**Enhance GIMPLE IR to represent lifetimes explicitly**  At the moment,
GCC internal representation GIMPLE lacks precise lifetime information
for addressable variables: GIMPLE marks the end of the lifetime by the
so-called "GIMPLE clobber" statement, corresponding to the point where
the variable goes out of scope in the original program. However, the
event of the "birth" of a variable (where it appears in scope) is lost,
making the IR ambiguous and opening the door for invalid optimizations,
as shown in bug #90348. The project would entail inventing a way to
represent "lifetime start" in GIMPLE, adjusting front-ends to emit it,
implementing a verifier to check that optimizations do not move
references outside of the variable's lifetime, and potentially
enhancing optimizations to move lifetime markers, expanding the
lifetime, where necessary.

I know we already have good project ideas, and I suspect this idea may
be too complicated for GSoC, but on the other hand it sounds useful,
and gives an "experimental" topic that may be interesting for students.

What do you think?

Thanks.
Alexander

Re: GSoC topic: precise lifetimes in GIMPLE

[Richard Biener]

On Mon, 2 Mar 2020, Alexander Monakov wrote:

> Hi,
> 
> following the conversation in PR 90348, I wonder if it would make sense
> to suggest the idea presented there as a potential GSoC topic? Like this:
> 
> **Enhance GIMPLE IR to represent lifetimes explicitly**  At the moment,
> GCC internal representation GIMPLE lacks precise lifetime information
> for addressable variables: GIMPLE marks the end of the lifetime by the
> so-called "GIMPLE clobber" statement, corresponding to the point where
> the variable goes out of scope in the original program. However, the
> event of the "birth" of a variable (where it appears in scope) is lost,
> making the IR ambiguous and opening the door for invalid optimizations,
> as shown in bug #90348. The project would entail inventing a way to
> represent "lifetime start" in GIMPLE, adjusting front-ends to emit it,
> implementing a verifier to check that optimizations do not move
> references outside of the variable's lifetime, and potentially
> enhancing optimizations to move lifetime markers, expanding the
> lifetime, where necessary.
> 
> I know we already have good project ideas, and I suspect this idea may
> be too complicated for GSoC, but on the other hand it sounds useful,
> and gives an "experimental" topic that may be interesting for students.
> 
> What do you think?

PR90348 is certainly entertaining.  But I guess for a GSoC project
we need a more elaborate implementation plan.  The above suggesting
of a "lifetime start" is IMHO a no-go btw.  Instead I think the
only feasible way is to make all references indirect and thus
make both "allocation" and "deallocation" points explicit.  Then
there's a data dependence on the "allocation" statement which
provides upward safety and the "deallocation" statement would
need to act as a barrier in some to be determined way.  That is,
how to make optimizers preserve the lifetime end is still unsolved.

IMHO whatever we do should combine with the CLOBBERs we have now,
not be yet another mechanism.

Richard.

Re: GSoC topic: precise lifetimes in GIMPLE

[Alexander Monakov]

On Mon, 2 Mar 2020, Richard Biener wrote:

> PR90348 is certainly entertaining.  But I guess for a GSoC project
> we need a more elaborate implementation plan.  The above suggesting
> of a "lifetime start" is IMHO a no-go btw.  Instead I think the
> only feasible way is to make all references indirect and thus
> make both "allocation" and "deallocation" points explicit.  Then
> there's a data dependence on the "allocation" statement which
> provides upward safety and the "deallocation" statement would
> need to act as a barrier in some to be determined way.  That is,
> how to make optimizers preserve the lifetime end is still unsolved.

I think a verifier that ensures that all references are dominated by
"lifetime start" and post-dominated by clobbers/lifetime-end would
be a substantial step towards that.

Agreed that data dependence on allocation would automatically ensure
part of that verification, but then the problem with deallocation
remains, as you say.

> IMHO whatever we do should combine with the CLOBBERs we have now,
> not be yet another mechanism.

This seems contradictory with the ideas in your previous paragraph.
I agree though, CLOBBER-as-lifetime-end makes sense and does not
call for a replacement.

Thanks.
Alexander

Re: GSoC topic: precise lifetimes in GIMPLE

[Richard Biener]

On Mon, 2 Mar 2020, Alexander Monakov wrote:

> On Mon, 2 Mar 2020, Richard Biener wrote:
> 
> > PR90348 is certainly entertaining.  But I guess for a GSoC project
> > we need a more elaborate implementation plan.  The above suggesting
> > of a "lifetime start" is IMHO a no-go btw.  Instead I think the
> > only feasible way is to make all references indirect and thus
> > make both "allocation" and "deallocation" points explicit.  Then
> > there's a data dependence on the "allocation" statement which
> > provides upward safety and the "deallocation" statement would
> > need to act as a barrier in some to be determined way.  That is,
> > how to make optimizers preserve the lifetime end is still unsolved.
> 
> I think a verifier that ensures that all references are dominated by
> "lifetime start" and post-dominated by clobbers/lifetime-end would
> be a substantial step towards that.
> 
> Agreed that data dependence on allocation would automatically ensure
> part of that verification, but then the problem with deallocation
> remains, as you say.

Yes.

> > IMHO whatever we do should combine with the CLOBBERs we have now,
> > not be yet another mechanism.
> 
> This seems contradictory with the ideas in your previous paragraph.
> I agree though, CLOBBER-as-lifetime-end makes sense and does not
> call for a replacement.

CLOBBERs would just make content dead.  CLOBBERs and lifetime start
would be somewhat redundant if we continue to emit CLOBBERs everywhere
as we do now (the C++ FE emits them at lifetime start).

Richard.