Liveness Analysis

Where is the liveness analysis pass? I have been looking for days but cannot find anything.

I just want to know transfer variables in and out of basic blocks, that are calculated using simple data flow equations.

Thanks!

Assuming you talk about the machine representation:
- The register allocators use the LiveIntervals analysis (there is also LiveVariables but that is deprecated, please don't use it).
- When register allocation is done we keep the block live-in lists around and you can use LivePhysReg or LiveRegUnits to recompute the liveness information in the middle of a basic block when necessary.
- The RDF framework in lib/Target/Hexagon performs a dataflow analysis post-regalloc to determine values in physical registers.

- Matthias

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).

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?

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).

/Björn

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).

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...

- Matthias

From: Matthias Braun <matze@braunis.de>
Sent: den 26 september 2018 19:25
To: Björn Pettersson A <bjorn.a.pettersson@ericsson.com>
Cc: Jason Ott <jott002@ucr.edu>; llvm-dev@lists.llvm.org
Subject: Re: [llvm-dev] Liveness Analysis

>
> 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

From: Matthias Braun <matze@braunis.de>
Sent: den 26 september 2018 19:25
To: Björn Pettersson A <bjorn.a.pettersson@ericsson.com>
Cc: Jason Ott <jott002@ucr.edu>; llvm-dev@lists.llvm.org
Subject: Re: [llvm-dev] Liveness Analysis

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).

If I remember correctly (though it was 3-4 years ago when I looked at this), I think the main problem was target callbacks doing trickier things in their commutation callbacks did not update liveness information.

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.

Last time I looked (again 3-4 years ago) this was definitely important for the quality of the generated code and could not simply be dropped at least.

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

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…)

Embarassingly the machine verifier is disabled for a couple passes that never got fixed (the addPass() call in TargetPassConfig has the 2nd argument false). TwoAddressElimination and PHIElimination being two of them…

Well… Thanks for bringing this whole discussion up again, we really should do something about the whole topic, the question is just who would be willing to do the work :-/

In any case I won’t stop any patches just because they don’t update LiveIntervals properly…

  • Matthias