[llvm-dev] Liveness Analysis

Thu Sep 27 10:01:25 PDT 2018

> On Sep 27, 2018, at 6:40 AM, Björn Pettersson A via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> 
>> -----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).
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
>> 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 <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 <https://reviews.llvm.org/D52558>
> and here
>  https://reviews.llvm.org/D52553 <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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20180927/ac89dcbd/attachment.html>