[llvm-dev] Liveness Analysis

[Björn Pettersson A via llvm-dev]

> -----Original Message-----
> From: Matthias Braun <matze at braunis.de>
> Sent: den 26 september 2018 19:25
> To: Björn Pettersson A <bjorn.a.pettersson at ericsson.com>
> Cc: Jason Ott <jott002 at ucr.edu>; llvm-dev at lists.llvm.org
> Subject: Re: [llvm-dev] Liveness Analysis
> 
> 
> 
> > On Sep 26, 2018, at 6:01 AM, Björn Pettersson A
> <bjorn.a.pettersson at ericsson.com> wrote:
> >
> > So what is the status about LiveVariables. Is there a plan to remove it?
> >
> > After searching in old lvm-dev-mails it is mentioned that LiveVariable
> > still exists due to one pass needing it. And a comment in
> > TargetPassConfig.cpp indicates that the pass in question is
> > TwoAddressInstruction:
> >
> >  // FIXME: Once TwoAddressInstruction pass no longer uses kill flags,
> >  // LiveVariables can be removed completely, and LiveIntervals can be
> directly
> >  // computed. (We still either need to regenerate kill flags after
> regalloc, or
> >  // preferably fix the scavenger to not depend on them).
> Yes as far as I know this is the last pass. PHIElimination uses it too
> today, but it supports both and actually works, while TwoAddress AFAIK is
> broken with LiveIntervals mostly because of target callbacks I think.
> I believe the talk about kill flags in the comment to not be true anymore
> (we regenerate the kill flags anyway in virtregrewrite which comes before
> the scavenger and I switch the scavenger to not rely on them anymore in
> nearly all cases).


Looks like TwoAddressInstructionPass::rescheduleKillAboveMI is the primary
user of liveness info in TwoAddressInstructionPass. Otherwise it mostly
seems to be about keeping the LiveVariables up-to-date while doing
transformations (unless there is some target that takes decisions
in the convertToThreeAddress hook).

It could be interesting to analyse how important the rescheduleKillAboveMI
transformation is nowadays. A more brutal solution (and really admitting
defeat) regarding liveness during SSA deconstruction would be to remove
the use of both LV and LIS in TwoAddressInstructionPass, and spend the
time on implementing other tranformations to compensate for the loss.


> 
> >
> >
> > When looking in TwoAddressInstructionPass.cpp it looks like the pass
> only
> > use/update LV when there is no LIS. And there seems to be an
> experimental
> > -early-live-intervals option to calculcate LIS before
> > TwoAddressInstructionPass.
> >
> > I also noticed that the -early-live-intervals option was added back in
> 2012.
> > So I assume that the plans to replace LiveVariables by LiveIntervals
> > in TwoAddressInstructionPass got some history.
> >
> > Has there been any evaluation (lately) from using -early-live-intervals?
> Unfortunately the work wasn’t finished in 2012 and As far as I know noone
> else really attempted it seriously since then.
> 
> >
> >
> > I got a feeling that the SSA deconstruction passes are overly
> complicated
> > right now, since for example PHIElimination tries to update both LV and
> > LIS conditionally depending on if the analyses are available or not.
> > But there are no test cases that set -early-live-intervals afaict, so
> > there is a bulk of code that seems to not be regression tested related
> > to LIS in PHIElimination and TwoAddressInstructionPass.
> >
> > Given that no one is still actively working on removing LiveVariables;
> > Maybe it is better to remove -early-live-intervals and the not
> > so well tested code regarding LIS in
> PHIElimination/TwoAddressInstructionPass.
> > And then we could say that LiveVariables should be used during SSA
> > deconstruction (instead of saying that it is deprecated).
> 
> Are you planning bigger changes to these passes? I feel like removing the
> LIS code is admitting defeat and cementing the worse system... On the
> other hand if it becomes in the way of making changes we could discuss
> dropping it...

Not really planning any bigger changes, but...

Lately I've been trouble shooting PHIElimination and ended up
writing this PR
  https://bugs.llvm.org/show_bug.cgi?id=39085
A fix might need to verify that it updates both LiveVariable and
LiveIntervals correctly.

I've also proposed some improvement/fixes to PHIElimination here:
  https://reviews.llvm.org/D52558
and here
  https://reviews.llvm.org/D52553
Those patches use the "deprecated" -livevars pass in the regression
tests. Unfortunate if LiveVariables is to be removed (but if there
has been no progress for the last six years, the maybe my new tests
will work for another six years at least...)

I also stumbled upon the LIS related code when looking at
  https://reviews.llvm.org/D36224
That patch should not have any impact on LV/LIS afaict. But the
code related to LIS is there, and it took me some time to understand
that it is an "untested code path" unless I use -early-live-intervals.

- Björn

> 
> - Matthias
> 
> >
> > /Björn
> >